1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
54 /// makeVTList - Return an instance of the SDVTList struct initialized with the
55 /// specified members.
56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
57 SDVTList Res = {VTs, NumVTs};
61 // Default null implementations of the callbacks.
62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
65 //===----------------------------------------------------------------------===//
66 // ConstantFPSDNode Class
67 //===----------------------------------------------------------------------===//
69 /// isExactlyValue - We don't rely on operator== working on double values, as
70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
71 /// As such, this method can be used to do an exact bit-for-bit comparison of
72 /// two floating point values.
73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
74 return getValueAPF().bitwiseIsEqual(V);
77 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 assert(VT.isFloatingPoint() && "Can only convert between FP types");
81 // convert modifies in place, so make a copy.
82 APFloat Val2 = APFloat(Val);
84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
85 APFloat::rmNearestTiesToEven,
90 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
94 /// isBuildVectorAllOnes - Return true if the specified node is a
95 /// BUILD_VECTOR where all of the elements are ~0 or undef.
96 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
97 // Look through a bit convert.
98 if (N->getOpcode() == ISD::BITCAST)
99 N = N->getOperand(0).getNode();
101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
103 unsigned i = 0, e = N->getNumOperands();
105 // Skip over all of the undef values.
106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109 // Do not accept an all-undef vector.
110 if (i == e) return false;
112 // Do not accept build_vectors that aren't all constants or which have non-~0
113 // elements. We have to be a bit careful here, as the type of the constant
114 // may not be the same as the type of the vector elements due to type
115 // legalization (the elements are promoted to a legal type for the target and
116 // a vector of a type may be legal when the base element type is not).
117 // We only want to check enough bits to cover the vector elements, because
118 // we care if the resultant vector is all ones, not whether the individual
120 SDValue NotZero = N->getOperand(i);
121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
123 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
131 // Okay, we have at least one ~0 value, check to see if the rest match or are
132 // undefs. Even with the above element type twiddling, this should be OK, as
133 // the same type legalization should have applied to all the elements.
134 for (++i; i != e; ++i)
135 if (N->getOperand(i) != NotZero &&
136 N->getOperand(i).getOpcode() != ISD::UNDEF)
142 /// isBuildVectorAllZeros - Return true if the specified node is a
143 /// BUILD_VECTOR where all of the elements are 0 or undef.
144 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
145 // Look through a bit convert.
146 if (N->getOpcode() == ISD::BITCAST)
147 N = N->getOperand(0).getNode();
149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
151 bool IsAllUndef = true;
152 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
153 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept build_vectors that aren't all constants or which have non-0
157 // elements. We have to be a bit careful here, as the type of the constant
158 // may not be the same as the type of the vector elements due to type
159 // legalization (the elements are promoted to a legal type for the target
160 // and a vector of a type may be legal when the base element type is not).
161 // We only want to check enough bits to cover the vector elements, because
162 // we care if the resultant vector is all zeros, not whether the individual
164 SDValue Zero = N->getOperand(i);
165 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
166 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
167 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
170 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
176 // Do not accept an all-undef vector.
182 /// \brief Return true if the specified node is a BUILD_VECTOR node of
183 /// all ConstantSDNode or undef.
184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
185 if (N->getOpcode() != ISD::BUILD_VECTOR)
188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
189 SDValue Op = N->getOperand(i);
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// isScalarToVector - Return true if the specified node is a
199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
200 /// element is not an undef.
201 bool ISD::isScalarToVector(const SDNode *N) {
202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
205 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 unsigned NumElems = N->getNumOperands();
212 for (unsigned i = 1; i < NumElems; ++i) {
213 SDValue V = N->getOperand(i);
214 if (V.getOpcode() != ISD::UNDEF)
220 /// allOperandsUndef - Return true if the node has at least one operand
221 /// and all operands of the specified node are ISD::UNDEF.
222 bool ISD::allOperandsUndef(const SDNode *N) {
223 // Return false if the node has no operands.
224 // This is "logically inconsistent" with the definition of "all" but
225 // is probably the desired behavior.
226 if (N->getNumOperands() == 0)
229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
230 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
236 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
239 return ISD::ANY_EXTEND;
241 return ISD::SIGN_EXTEND;
243 return ISD::ZERO_EXTEND;
248 llvm_unreachable("Invalid LoadExtType");
251 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
252 /// when given the operation for (X op Y).
253 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
254 // To perform this operation, we just need to swap the L and G bits of the
256 unsigned OldL = (Operation >> 2) & 1;
257 unsigned OldG = (Operation >> 1) & 1;
258 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
259 (OldL << 1) | // New G bit
260 (OldG << 2)); // New L bit.
263 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
264 /// 'op' is a valid SetCC operation.
265 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
266 unsigned Operation = Op;
268 Operation ^= 7; // Flip L, G, E bits, but not U.
270 Operation ^= 15; // Flip all of the condition bits.
272 if (Operation > ISD::SETTRUE2)
273 Operation &= ~8; // Don't let N and U bits get set.
275 return ISD::CondCode(Operation);
279 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
280 /// signed operation and 2 if the result is an unsigned comparison. Return zero
281 /// if the operation does not depend on the sign of the input (setne and seteq).
282 static int isSignedOp(ISD::CondCode Opcode) {
284 default: llvm_unreachable("Illegal integer setcc operation!");
286 case ISD::SETNE: return 0;
290 case ISD::SETGE: return 1;
294 case ISD::SETUGE: return 2;
298 /// getSetCCOrOperation - Return the result of a logical OR between different
299 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
300 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
305 // Cannot fold a signed integer setcc with an unsigned integer setcc.
306 return ISD::SETCC_INVALID;
308 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
310 // If the N and U bits get set then the resultant comparison DOES suddenly
311 // care about orderedness, and is true when ordered.
312 if (Op > ISD::SETTRUE2)
313 Op &= ~16; // Clear the U bit if the N bit is set.
315 // Canonicalize illegal integer setcc's.
316 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
319 return ISD::CondCode(Op);
322 /// getSetCCAndOperation - Return the result of a logical AND between different
323 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
324 /// function returns zero if it is not possible to represent the resultant
326 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
329 // Cannot fold a signed setcc with an unsigned setcc.
330 return ISD::SETCC_INVALID;
332 // Combine all of the condition bits.
333 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
335 // Canonicalize illegal integer setcc's.
339 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
340 case ISD::SETOEQ: // SETEQ & SETU[LG]E
341 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
342 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
343 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
350 //===----------------------------------------------------------------------===//
351 // SDNode Profile Support
352 //===----------------------------------------------------------------------===//
354 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
360 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
361 /// solely with their pointer.
362 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
363 ID.AddPointer(VTList.VTs);
366 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 static void AddNodeIDOperands(FoldingSetNodeID &ID,
369 ArrayRef<SDValue> Ops) {
370 for (auto& Op : Ops) {
371 ID.AddPointer(Op.getNode());
372 ID.AddInteger(Op.getResNo());
376 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 static void AddNodeIDOperands(FoldingSetNodeID &ID,
379 ArrayRef<SDUse> Ops) {
380 for (auto& Op : Ops) {
381 ID.AddPointer(Op.getNode());
382 ID.AddInteger(Op.getResNo());
386 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
390 ID.AddBoolean(exact);
393 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
394 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
395 bool nuw, bool nsw, bool exact) {
396 if (isBinOpWithFlags(Opcode))
397 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
400 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
401 SDVTList VTList, ArrayRef<SDValue> OpList) {
402 AddNodeIDOpcode(ID, OpC);
403 AddNodeIDValueTypes(ID, VTList);
404 AddNodeIDOperands(ID, OpList);
407 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
410 switch (N->getOpcode()) {
411 case ISD::TargetExternalSymbol:
412 case ISD::ExternalSymbol:
413 llvm_unreachable("Should only be used on nodes with operands");
414 default: break; // Normal nodes don't need extra info.
415 case ISD::TargetConstant:
416 case ISD::Constant: {
417 const ConstantSDNode *C = cast<ConstantSDNode>(N);
418 ID.AddPointer(C->getConstantIntValue());
419 ID.AddBoolean(C->isOpaque());
422 case ISD::TargetConstantFP:
423 case ISD::ConstantFP: {
424 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
427 case ISD::TargetGlobalAddress:
428 case ISD::GlobalAddress:
429 case ISD::TargetGlobalTLSAddress:
430 case ISD::GlobalTLSAddress: {
431 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
432 ID.AddPointer(GA->getGlobal());
433 ID.AddInteger(GA->getOffset());
434 ID.AddInteger(GA->getTargetFlags());
435 ID.AddInteger(GA->getAddressSpace());
438 case ISD::BasicBlock:
439 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
442 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444 case ISD::RegisterMask:
445 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
448 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450 case ISD::FrameIndex:
451 case ISD::TargetFrameIndex:
452 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
455 case ISD::TargetJumpTable:
456 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459 case ISD::ConstantPool:
460 case ISD::TargetConstantPool: {
461 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
462 ID.AddInteger(CP->getAlignment());
463 ID.AddInteger(CP->getOffset());
464 if (CP->isMachineConstantPoolEntry())
465 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467 ID.AddPointer(CP->getConstVal());
468 ID.AddInteger(CP->getTargetFlags());
471 case ISD::TargetIndex: {
472 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
473 ID.AddInteger(TI->getIndex());
474 ID.AddInteger(TI->getOffset());
475 ID.AddInteger(TI->getTargetFlags());
479 const LoadSDNode *LD = cast<LoadSDNode>(N);
480 ID.AddInteger(LD->getMemoryVT().getRawBits());
481 ID.AddInteger(LD->getRawSubclassData());
482 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
486 const StoreSDNode *ST = cast<StoreSDNode>(N);
487 ID.AddInteger(ST->getMemoryVT().getRawBits());
488 ID.AddInteger(ST->getRawSubclassData());
489 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
500 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
501 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
502 BinNode->hasNoSignedWrap(), BinNode->isExact());
505 case ISD::ATOMIC_CMP_SWAP:
506 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
507 case ISD::ATOMIC_SWAP:
508 case ISD::ATOMIC_LOAD_ADD:
509 case ISD::ATOMIC_LOAD_SUB:
510 case ISD::ATOMIC_LOAD_AND:
511 case ISD::ATOMIC_LOAD_OR:
512 case ISD::ATOMIC_LOAD_XOR:
513 case ISD::ATOMIC_LOAD_NAND:
514 case ISD::ATOMIC_LOAD_MIN:
515 case ISD::ATOMIC_LOAD_MAX:
516 case ISD::ATOMIC_LOAD_UMIN:
517 case ISD::ATOMIC_LOAD_UMAX:
518 case ISD::ATOMIC_LOAD:
519 case ISD::ATOMIC_STORE: {
520 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
521 ID.AddInteger(AT->getMemoryVT().getRawBits());
522 ID.AddInteger(AT->getRawSubclassData());
523 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
526 case ISD::PREFETCH: {
527 const MemSDNode *PF = cast<MemSDNode>(N);
528 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
531 case ISD::VECTOR_SHUFFLE: {
532 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
533 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535 ID.AddInteger(SVN->getMaskElt(i));
538 case ISD::TargetBlockAddress:
539 case ISD::BlockAddress: {
540 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
541 ID.AddPointer(BA->getBlockAddress());
542 ID.AddInteger(BA->getOffset());
543 ID.AddInteger(BA->getTargetFlags());
546 } // end switch (N->getOpcode())
548 // Target specific memory nodes could also have address spaces to check.
549 if (N->isTargetMemoryOpcode())
550 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
553 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
556 AddNodeIDOpcode(ID, N->getOpcode());
557 // Add the return value info.
558 AddNodeIDValueTypes(ID, N->getVTList());
559 // Add the operand info.
560 AddNodeIDOperands(ID, N->ops());
562 // Handle SDNode leafs with special info.
563 AddNodeIDCustom(ID, N);
566 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
567 /// the CSE map that carries volatility, temporalness, indexing mode, and
568 /// extension/truncation information.
570 static inline unsigned
571 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
572 bool isNonTemporal, bool isInvariant) {
573 assert((ConvType & 3) == ConvType &&
574 "ConvType may not require more than 2 bits!");
575 assert((AM & 7) == AM &&
576 "AM may not require more than 3 bits!");
580 (isNonTemporal << 6) |
584 //===----------------------------------------------------------------------===//
585 // SelectionDAG Class
586 //===----------------------------------------------------------------------===//
588 /// doNotCSE - Return true if CSE should not be performed for this node.
589 static bool doNotCSE(SDNode *N) {
590 if (N->getValueType(0) == MVT::Glue)
591 return true; // Never CSE anything that produces a flag.
593 switch (N->getOpcode()) {
595 case ISD::HANDLENODE:
597 return true; // Never CSE these nodes.
600 // Check that remaining values produced are not flags.
601 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
602 if (N->getValueType(i) == MVT::Glue)
603 return true; // Never CSE anything that produces a flag.
608 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 void SelectionDAG::RemoveDeadNodes() {
611 // Create a dummy node (which is not added to allnodes), that adds a reference
612 // to the root node, preventing it from being deleted.
613 HandleSDNode Dummy(getRoot());
615 SmallVector<SDNode*, 128> DeadNodes;
617 // Add all obviously-dead nodes to the DeadNodes worklist.
618 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620 DeadNodes.push_back(I);
622 RemoveDeadNodes(DeadNodes);
624 // If the root changed (e.g. it was a dead load, update the root).
625 setRoot(Dummy.getValue());
628 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
629 /// given list, and any nodes that become unreachable as a result.
630 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
632 // Process the worklist, deleting the nodes and adding their uses to the
634 while (!DeadNodes.empty()) {
635 SDNode *N = DeadNodes.pop_back_val();
637 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
638 DUL->NodeDeleted(N, nullptr);
640 // Take the node out of the appropriate CSE map.
641 RemoveNodeFromCSEMaps(N);
643 // Next, brutally remove the operand list. This is safe to do, as there are
644 // no cycles in the graph.
645 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647 SDNode *Operand = Use.getNode();
650 // Now that we removed this operand, see if there are no uses of it left.
651 if (Operand->use_empty())
652 DeadNodes.push_back(Operand);
659 void SelectionDAG::RemoveDeadNode(SDNode *N){
660 SmallVector<SDNode*, 16> DeadNodes(1, N);
662 // Create a dummy node that adds a reference to the root node, preventing
663 // it from being deleted. (This matters if the root is an operand of the
665 HandleSDNode Dummy(getRoot());
667 RemoveDeadNodes(DeadNodes);
670 void SelectionDAG::DeleteNode(SDNode *N) {
671 // First take this out of the appropriate CSE map.
672 RemoveNodeFromCSEMaps(N);
674 // Finally, remove uses due to operands of this node, remove from the
675 // AllNodes list, and delete the node.
676 DeleteNodeNotInCSEMaps(N);
679 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
680 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
681 assert(N->use_empty() && "Cannot delete a node that is not dead!");
683 // Drop all of the operands and decrement used node's use counts.
689 void SelectionDAG::DeallocateNode(SDNode *N) {
690 if (N->OperandsNeedDelete)
691 delete[] N->OperandList;
693 // Set the opcode to DELETED_NODE to help catch bugs when node
694 // memory is reallocated.
695 N->NodeType = ISD::DELETED_NODE;
697 NodeAllocator.Deallocate(AllNodes.remove(N));
699 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
700 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
701 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
702 DbgVals[i]->setIsInvalidated();
706 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
707 static void VerifySDNode(SDNode *N) {
708 switch (N->getOpcode()) {
711 case ISD::BUILD_PAIR: {
712 EVT VT = N->getValueType(0);
713 assert(N->getNumValues() == 1 && "Too many results!");
714 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
715 "Wrong return type!");
716 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
717 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
718 "Mismatched operand types!");
719 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
720 "Wrong operand type!");
721 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
722 "Wrong return type size");
725 case ISD::BUILD_VECTOR: {
726 assert(N->getNumValues() == 1 && "Too many results!");
727 assert(N->getValueType(0).isVector() && "Wrong return type!");
728 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
729 "Wrong number of operands!");
730 EVT EltVT = N->getValueType(0).getVectorElementType();
731 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
732 assert((I->getValueType() == EltVT ||
733 (EltVT.isInteger() && I->getValueType().isInteger() &&
734 EltVT.bitsLE(I->getValueType()))) &&
735 "Wrong operand type!");
736 assert(I->getValueType() == N->getOperand(0).getValueType() &&
737 "Operands must all have the same type");
745 /// \brief Insert a newly allocated node into the DAG.
747 /// Handles insertion into the all nodes list and CSE map, as well as
748 /// verification and other common operations when a new node is allocated.
749 void SelectionDAG::InsertNode(SDNode *N) {
750 AllNodes.push_back(N);
756 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
757 /// correspond to it. This is useful when we're about to delete or repurpose
758 /// the node. We don't want future request for structurally identical nodes
759 /// to return N anymore.
760 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
762 switch (N->getOpcode()) {
763 case ISD::HANDLENODE: return false; // noop.
765 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
766 "Cond code doesn't exist!");
767 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
768 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
770 case ISD::ExternalSymbol:
771 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
773 case ISD::TargetExternalSymbol: {
774 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
775 Erased = TargetExternalSymbols.erase(
776 std::pair<std::string,unsigned char>(ESN->getSymbol(),
777 ESN->getTargetFlags()));
780 case ISD::VALUETYPE: {
781 EVT VT = cast<VTSDNode>(N)->getVT();
782 if (VT.isExtended()) {
783 Erased = ExtendedValueTypeNodes.erase(VT);
785 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
786 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
791 // Remove it from the CSE Map.
792 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
793 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
794 Erased = CSEMap.RemoveNode(N);
798 // Verify that the node was actually in one of the CSE maps, unless it has a
799 // flag result (which cannot be CSE'd) or is one of the special cases that are
800 // not subject to CSE.
801 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
802 !N->isMachineOpcode() && !doNotCSE(N)) {
805 llvm_unreachable("Node is not in map!");
811 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
812 /// maps and modified in place. Add it back to the CSE maps, unless an identical
813 /// node already exists, in which case transfer all its users to the existing
814 /// node. This transfer can potentially trigger recursive merging.
817 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
818 // For node types that aren't CSE'd, just act as if no identical node
821 SDNode *Existing = CSEMap.GetOrInsertNode(N);
823 // If there was already an existing matching node, use ReplaceAllUsesWith
824 // to replace the dead one with the existing one. This can cause
825 // recursive merging of other unrelated nodes down the line.
826 ReplaceAllUsesWith(N, Existing);
828 // N is now dead. Inform the listeners and delete it.
829 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
830 DUL->NodeDeleted(N, Existing);
831 DeleteNodeNotInCSEMaps(N);
836 // If the node doesn't already exist, we updated it. Inform listeners.
837 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
841 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
842 /// were replaced with those specified. If this node is never memoized,
843 /// return null, otherwise return a pointer to the slot it would take. If a
844 /// node already exists with these operands, the slot will be non-null.
845 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
850 SDValue Ops[] = { Op };
852 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
853 AddNodeIDCustom(ID, N);
854 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
858 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
859 /// were replaced with those specified. If this node is never memoized,
860 /// return null, otherwise return a pointer to the slot it would take. If a
861 /// node already exists with these operands, the slot will be non-null.
862 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
863 SDValue Op1, SDValue Op2,
868 SDValue Ops[] = { Op1, Op2 };
870 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
871 AddNodeIDCustom(ID, N);
872 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
877 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
878 /// were replaced with those specified. If this node is never memoized,
879 /// return null, otherwise return a pointer to the slot it would take. If a
880 /// node already exists with these operands, the slot will be non-null.
881 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
887 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
888 AddNodeIDCustom(ID, N);
889 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
893 /// getEVTAlignment - Compute the default alignment value for the
896 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
897 Type *Ty = VT == MVT::iPTR ?
898 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
899 VT.getTypeForEVT(*getContext());
901 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
904 // EntryNode could meaningfully have debug info if we can find it...
905 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
906 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
907 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
908 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
909 UpdateListeners(nullptr) {
910 AllNodes.push_back(&EntryNode);
911 DbgInfo = new SDDbgInfo();
914 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
917 Context = &mf.getFunction()->getContext();
920 SelectionDAG::~SelectionDAG() {
921 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
926 void SelectionDAG::allnodes_clear() {
927 assert(&*AllNodes.begin() == &EntryNode);
928 AllNodes.remove(AllNodes.begin());
929 while (!AllNodes.empty())
930 DeallocateNode(AllNodes.begin());
933 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
934 SDVTList VTs, SDValue N1,
935 SDValue N2, bool nuw, bool nsw,
937 if (isBinOpWithFlags(Opcode)) {
938 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
939 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
940 FN->setHasNoUnsignedWrap(nuw);
941 FN->setHasNoSignedWrap(nsw);
942 FN->setIsExact(exact);
947 BinarySDNode *N = new (NodeAllocator)
948 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
952 void SelectionDAG::clear() {
954 OperandAllocator.Reset();
957 ExtendedValueTypeNodes.clear();
958 ExternalSymbols.clear();
959 TargetExternalSymbols.clear();
960 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
961 static_cast<CondCodeSDNode*>(nullptr));
962 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
963 static_cast<SDNode*>(nullptr));
965 EntryNode.UseList = nullptr;
966 AllNodes.push_back(&EntryNode);
967 Root = getEntryNode();
971 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
972 return VT.bitsGT(Op.getValueType()) ?
973 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
974 getNode(ISD::TRUNCATE, DL, VT, Op);
977 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
978 return VT.bitsGT(Op.getValueType()) ?
979 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
980 getNode(ISD::TRUNCATE, DL, VT, Op);
983 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
984 return VT.bitsGT(Op.getValueType()) ?
985 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
986 getNode(ISD::TRUNCATE, DL, VT, Op);
989 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
991 if (VT.bitsLE(Op.getValueType()))
992 return getNode(ISD::TRUNCATE, SL, VT, Op);
994 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
995 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
998 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
999 assert(!VT.isVector() &&
1000 "getZeroExtendInReg should use the vector element type instead of "
1001 "the vector type!");
1002 if (Op.getValueType() == VT) return Op;
1003 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1004 APInt Imm = APInt::getLowBitsSet(BitWidth,
1005 VT.getSizeInBits());
1006 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1007 getConstant(Imm, Op.getValueType()));
1010 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1011 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1012 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1013 "The sizes of the input and result must match in order to perform the "
1014 "extend in-register.");
1015 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1016 "The destination vector type must have fewer lanes than the input.");
1017 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1020 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1021 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1022 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1023 "The sizes of the input and result must match in order to perform the "
1024 "extend in-register.");
1025 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1026 "The destination vector type must have fewer lanes than the input.");
1027 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1030 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1031 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1032 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1033 "The sizes of the input and result must match in order to perform the "
1034 "extend in-register.");
1035 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1036 "The destination vector type must have fewer lanes than the input.");
1037 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1040 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1042 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1043 EVT EltVT = VT.getScalarType();
1045 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1046 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1049 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1050 EVT EltVT = VT.getScalarType();
1052 switch (TLI->getBooleanContents(VT)) {
1053 case TargetLowering::ZeroOrOneBooleanContent:
1054 case TargetLowering::UndefinedBooleanContent:
1055 TrueValue = getConstant(1, VT);
1057 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1058 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1062 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1065 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1066 EVT EltVT = VT.getScalarType();
1067 assert((EltVT.getSizeInBits() >= 64 ||
1068 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1069 "getConstant with a uint64_t value that doesn't fit in the type!");
1070 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1073 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1075 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1078 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1080 assert(VT.isInteger() && "Cannot create FP integer constant!");
1082 EVT EltVT = VT.getScalarType();
1083 const ConstantInt *Elt = &Val;
1085 const TargetLowering *TLI = TM.getTargetLowering();
1087 // In some cases the vector type is legal but the element type is illegal and
1088 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1089 // inserted value (the type does not need to match the vector element type).
1090 // Any extra bits introduced will be truncated away.
1091 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1092 TargetLowering::TypePromoteInteger) {
1093 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1094 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1095 Elt = ConstantInt::get(*getContext(), NewVal);
1097 // In other cases the element type is illegal and needs to be expanded, for
1098 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1099 // the value into n parts and use a vector type with n-times the elements.
1100 // Then bitcast to the type requested.
1101 // Legalizing constants too early makes the DAGCombiner's job harder so we
1102 // only legalize if the DAG tells us we must produce legal types.
1103 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1104 TLI->getTypeAction(*getContext(), EltVT) ==
1105 TargetLowering::TypeExpandInteger) {
1106 APInt NewVal = Elt->getValue();
1107 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1108 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1109 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1110 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1112 // Check the temporary vector is the correct size. If this fails then
1113 // getTypeToTransformTo() probably returned a type whose size (in bits)
1114 // isn't a power-of-2 factor of the requested type size.
1115 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1117 SmallVector<SDValue, 2> EltParts;
1118 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1119 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1120 .trunc(ViaEltSizeInBits),
1121 ViaEltVT, isT, isO));
1124 // EltParts is currently in little endian order. If we actually want
1125 // big-endian order then reverse it now.
1126 if (TLI->isBigEndian())
1127 std::reverse(EltParts.begin(), EltParts.end());
1129 // The elements must be reversed when the element order is different
1130 // to the endianness of the elements (because the BITCAST is itself a
1131 // vector shuffle in this situation). However, we do not need any code to
1132 // perform this reversal because getConstant() is producing a vector
1134 // This situation occurs in MIPS MSA.
1136 SmallVector<SDValue, 8> Ops;
1137 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1138 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1140 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1141 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1146 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1147 "APInt size does not match type size!");
1148 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1149 FoldingSetNodeID ID;
1150 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1154 SDNode *N = nullptr;
1155 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1157 return SDValue(N, 0);
1160 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1161 CSEMap.InsertNode(N, IP);
1165 SDValue Result(N, 0);
1166 if (VT.isVector()) {
1167 SmallVector<SDValue, 8> Ops;
1168 Ops.assign(VT.getVectorNumElements(), Result);
1169 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1174 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1175 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1179 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1180 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1183 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1184 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1186 EVT EltVT = VT.getScalarType();
1188 // Do the map lookup using the actual bit pattern for the floating point
1189 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1190 // we don't have issues with SNANs.
1191 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1192 FoldingSetNodeID ID;
1193 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1196 SDNode *N = nullptr;
1197 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1199 return SDValue(N, 0);
1202 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1203 CSEMap.InsertNode(N, IP);
1207 SDValue Result(N, 0);
1208 if (VT.isVector()) {
1209 SmallVector<SDValue, 8> Ops;
1210 Ops.assign(VT.getVectorNumElements(), Result);
1211 // FIXME SDLoc info might be appropriate here
1212 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1217 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1218 EVT EltVT = VT.getScalarType();
1219 if (EltVT==MVT::f32)
1220 return getConstantFP(APFloat((float)Val), VT, isTarget);
1221 else if (EltVT==MVT::f64)
1222 return getConstantFP(APFloat(Val), VT, isTarget);
1223 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1226 APFloat apf = APFloat(Val);
1227 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1229 return getConstantFP(apf, VT, isTarget);
1231 llvm_unreachable("Unsupported type in getConstantFP");
1234 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1235 EVT VT, int64_t Offset,
1237 unsigned char TargetFlags) {
1238 assert((TargetFlags == 0 || isTargetGA) &&
1239 "Cannot set target flags on target-independent globals");
1240 const TargetLowering *TLI = TM.getTargetLowering();
1242 // Truncate (with sign-extension) the offset value to the pointer size.
1243 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1245 Offset = SignExtend64(Offset, BitWidth);
1248 if (GV->isThreadLocal())
1249 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1251 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1253 FoldingSetNodeID ID;
1254 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1256 ID.AddInteger(Offset);
1257 ID.AddInteger(TargetFlags);
1258 ID.AddInteger(GV->getType()->getAddressSpace());
1260 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1261 return SDValue(E, 0);
1263 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1264 DL.getDebugLoc(), GV, VT,
1265 Offset, TargetFlags);
1266 CSEMap.InsertNode(N, IP);
1268 return SDValue(N, 0);
1271 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1272 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1273 FoldingSetNodeID ID;
1274 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1277 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1278 return SDValue(E, 0);
1280 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1281 CSEMap.InsertNode(N, IP);
1283 return SDValue(N, 0);
1286 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1287 unsigned char TargetFlags) {
1288 assert((TargetFlags == 0 || isTarget) &&
1289 "Cannot set target flags on target-independent jump tables");
1290 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1291 FoldingSetNodeID ID;
1292 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1294 ID.AddInteger(TargetFlags);
1296 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1297 return SDValue(E, 0);
1299 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1301 CSEMap.InsertNode(N, IP);
1303 return SDValue(N, 0);
1306 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1307 unsigned Alignment, int Offset,
1309 unsigned char TargetFlags) {
1310 assert((TargetFlags == 0 || isTarget) &&
1311 "Cannot set target flags on target-independent globals");
1314 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1315 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1318 ID.AddInteger(Alignment);
1319 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1323 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1327 Alignment, TargetFlags);
1328 CSEMap.InsertNode(N, IP);
1330 return SDValue(N, 0);
1334 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1335 unsigned Alignment, int Offset,
1337 unsigned char TargetFlags) {
1338 assert((TargetFlags == 0 || isTarget) &&
1339 "Cannot set target flags on target-independent globals");
1342 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1343 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1344 FoldingSetNodeID ID;
1345 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1346 ID.AddInteger(Alignment);
1347 ID.AddInteger(Offset);
1348 C->addSelectionDAGCSEId(ID);
1349 ID.AddInteger(TargetFlags);
1351 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1352 return SDValue(E, 0);
1354 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1355 Alignment, TargetFlags);
1356 CSEMap.InsertNode(N, IP);
1358 return SDValue(N, 0);
1361 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1362 unsigned char TargetFlags) {
1363 FoldingSetNodeID ID;
1364 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1365 ID.AddInteger(Index);
1366 ID.AddInteger(Offset);
1367 ID.AddInteger(TargetFlags);
1369 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1370 return SDValue(E, 0);
1372 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1374 CSEMap.InsertNode(N, IP);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1380 FoldingSetNodeID ID;
1381 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1384 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1385 return SDValue(E, 0);
1387 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1388 CSEMap.InsertNode(N, IP);
1390 return SDValue(N, 0);
1393 SDValue SelectionDAG::getValueType(EVT VT) {
1394 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1395 ValueTypeNodes.size())
1396 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1398 SDNode *&N = VT.isExtended() ?
1399 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1401 if (N) return SDValue(N, 0);
1402 N = new (NodeAllocator) VTSDNode(VT);
1404 return SDValue(N, 0);
1407 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1408 SDNode *&N = ExternalSymbols[Sym];
1409 if (N) return SDValue(N, 0);
1410 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1412 return SDValue(N, 0);
1415 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1416 unsigned char TargetFlags) {
1418 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1420 if (N) return SDValue(N, 0);
1421 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1423 return SDValue(N, 0);
1426 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1427 if ((unsigned)Cond >= CondCodeNodes.size())
1428 CondCodeNodes.resize(Cond+1);
1430 if (!CondCodeNodes[Cond]) {
1431 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1432 CondCodeNodes[Cond] = N;
1436 return SDValue(CondCodeNodes[Cond], 0);
1439 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1440 // the shuffle mask M that point at N1 to point at N2, and indices that point
1441 // N2 to point at N1.
1442 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1444 int NElts = M.size();
1445 for (int i = 0; i != NElts; ++i) {
1453 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1454 SDValue N2, const int *Mask) {
1455 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1456 "Invalid VECTOR_SHUFFLE");
1458 // Canonicalize shuffle undef, undef -> undef
1459 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1460 return getUNDEF(VT);
1462 // Validate that all indices in Mask are within the range of the elements
1463 // input to the shuffle.
1464 unsigned NElts = VT.getVectorNumElements();
1465 SmallVector<int, 8> MaskVec;
1466 for (unsigned i = 0; i != NElts; ++i) {
1467 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1468 MaskVec.push_back(Mask[i]);
1471 // Canonicalize shuffle v, v -> v, undef
1474 for (unsigned i = 0; i != NElts; ++i)
1475 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1478 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1479 if (N1.getOpcode() == ISD::UNDEF)
1480 commuteShuffle(N1, N2, MaskVec);
1482 // Canonicalize all index into lhs, -> shuffle lhs, undef
1483 // Canonicalize all index into rhs, -> shuffle rhs, undef
1484 bool AllLHS = true, AllRHS = true;
1485 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1486 for (unsigned i = 0; i != NElts; ++i) {
1487 if (MaskVec[i] >= (int)NElts) {
1492 } else if (MaskVec[i] >= 0) {
1496 if (AllLHS && AllRHS)
1497 return getUNDEF(VT);
1498 if (AllLHS && !N2Undef)
1502 commuteShuffle(N1, N2, MaskVec);
1504 // Reset our undef status after accounting for the mask.
1505 N2Undef = N2.getOpcode() == ISD::UNDEF;
1506 // Re-check whether both sides ended up undef.
1507 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1508 return getUNDEF(VT);
1510 // If Identity shuffle return that node.
1511 bool Identity = true;
1512 for (unsigned i = 0; i != NElts; ++i) {
1513 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1515 if (Identity && NElts)
1518 // Shuffling a constant splat doesn't change the result.
1522 // Look through any bitcasts. We check that these don't change the number
1523 // (and size) of elements and just changes their types.
1524 while (V.getOpcode() == ISD::BITCAST)
1525 V = V->getOperand(0);
1527 // A splat should always show up as a build vector node.
1528 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1529 BitVector UndefElements;
1530 SDValue Splat = BV->getSplatValue(&UndefElements);
1531 // If this is a splat of an undef, shuffling it is also undef.
1532 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1533 return getUNDEF(VT);
1535 // We only have a splat which can skip shuffles if there is a splatted
1536 // value and no undef lanes rearranged by the shuffle.
1537 if (Splat && UndefElements.none()) {
1538 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1539 // number of elements match or the value splatted is a zero constant.
1540 if (V.getValueType().getVectorNumElements() ==
1541 VT.getVectorNumElements())
1543 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1544 if (C->isNullValue())
1550 FoldingSetNodeID ID;
1551 SDValue Ops[2] = { N1, N2 };
1552 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1553 for (unsigned i = 0; i != NElts; ++i)
1554 ID.AddInteger(MaskVec[i]);
1557 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1558 return SDValue(E, 0);
1560 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1561 // SDNode doesn't have access to it. This memory will be "leaked" when
1562 // the node is deallocated, but recovered when the NodeAllocator is released.
1563 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1564 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1566 ShuffleVectorSDNode *N =
1567 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1568 dl.getDebugLoc(), N1, N2,
1570 CSEMap.InsertNode(N, IP);
1572 return SDValue(N, 0);
1575 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1576 MVT VT = SV.getSimpleValueType(0);
1577 unsigned NumElems = VT.getVectorNumElements();
1578 SmallVector<int, 8> MaskVec;
1580 for (unsigned i = 0; i != NumElems; ++i) {
1581 int Idx = SV.getMaskElt(i);
1583 if (Idx < (int)NumElems)
1588 MaskVec.push_back(Idx);
1591 SDValue Op0 = SV.getOperand(0);
1592 SDValue Op1 = SV.getOperand(1);
1593 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1596 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1597 SDValue Val, SDValue DTy,
1598 SDValue STy, SDValue Rnd, SDValue Sat,
1599 ISD::CvtCode Code) {
1600 // If the src and dest types are the same and the conversion is between
1601 // integer types of the same sign or two floats, no conversion is necessary.
1603 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1606 FoldingSetNodeID ID;
1607 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1608 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1610 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1611 return SDValue(E, 0);
1613 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1616 CSEMap.InsertNode(N, IP);
1618 return SDValue(N, 0);
1621 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1622 FoldingSetNodeID ID;
1623 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1624 ID.AddInteger(RegNo);
1626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1627 return SDValue(E, 0);
1629 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1630 CSEMap.InsertNode(N, IP);
1632 return SDValue(N, 0);
1635 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1636 FoldingSetNodeID ID;
1637 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1638 ID.AddPointer(RegMask);
1640 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1641 return SDValue(E, 0);
1643 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1644 CSEMap.InsertNode(N, IP);
1646 return SDValue(N, 0);
1649 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1650 FoldingSetNodeID ID;
1651 SDValue Ops[] = { Root };
1652 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1653 ID.AddPointer(Label);
1655 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1656 return SDValue(E, 0);
1658 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1659 dl.getDebugLoc(), Root, Label);
1660 CSEMap.InsertNode(N, IP);
1662 return SDValue(N, 0);
1666 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1669 unsigned char TargetFlags) {
1670 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1672 FoldingSetNodeID ID;
1673 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1675 ID.AddInteger(Offset);
1676 ID.AddInteger(TargetFlags);
1678 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1679 return SDValue(E, 0);
1681 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1683 CSEMap.InsertNode(N, IP);
1685 return SDValue(N, 0);
1688 SDValue SelectionDAG::getSrcValue(const Value *V) {
1689 assert((!V || V->getType()->isPointerTy()) &&
1690 "SrcValue is not a pointer?");
1692 FoldingSetNodeID ID;
1693 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1697 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1698 return SDValue(E, 0);
1700 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1701 CSEMap.InsertNode(N, IP);
1703 return SDValue(N, 0);
1706 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1707 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1708 FoldingSetNodeID ID;
1709 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1713 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1714 return SDValue(E, 0);
1716 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1717 CSEMap.InsertNode(N, IP);
1719 return SDValue(N, 0);
1722 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1723 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1724 unsigned SrcAS, unsigned DestAS) {
1725 SDValue Ops[] = {Ptr};
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1728 ID.AddInteger(SrcAS);
1729 ID.AddInteger(DestAS);
1732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1733 return SDValue(E, 0);
1735 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1737 VT, Ptr, SrcAS, DestAS);
1738 CSEMap.InsertNode(N, IP);
1740 return SDValue(N, 0);
1743 /// getShiftAmountOperand - Return the specified value casted to
1744 /// the target's desired shift amount type.
1745 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1746 EVT OpTy = Op.getValueType();
1747 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1748 if (OpTy == ShTy || OpTy.isVector()) return Op;
1750 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1751 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1754 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1755 /// specified value type.
1756 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1757 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1758 unsigned ByteSize = VT.getStoreSize();
1759 Type *Ty = VT.getTypeForEVT(*getContext());
1760 const TargetLowering *TLI = TM.getTargetLowering();
1761 unsigned StackAlign =
1762 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1764 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1765 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1768 /// CreateStackTemporary - Create a stack temporary suitable for holding
1769 /// either of the specified value types.
1770 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1771 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1772 VT2.getStoreSizeInBits())/8;
1773 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1774 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1775 const TargetLowering *TLI = TM.getTargetLowering();
1776 const DataLayout *TD = TLI->getDataLayout();
1777 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1778 TD->getPrefTypeAlignment(Ty2));
1780 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1781 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1782 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1785 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1786 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1787 // These setcc operations always fold.
1791 case ISD::SETFALSE2: return getConstant(0, VT);
1793 case ISD::SETTRUE2: {
1794 const TargetLowering *TLI = TM.getTargetLowering();
1795 TargetLowering::BooleanContent Cnt =
1796 TLI->getBooleanContents(N1->getValueType(0));
1798 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1811 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1815 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1816 const APInt &C2 = N2C->getAPIntValue();
1817 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1818 const APInt &C1 = N1C->getAPIntValue();
1821 default: llvm_unreachable("Unknown integer setcc!");
1822 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1823 case ISD::SETNE: return getConstant(C1 != C2, VT);
1824 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1825 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1826 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1827 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1828 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1829 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1830 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1831 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1835 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1836 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1837 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1840 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1841 return getUNDEF(VT);
1843 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1844 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1845 return getUNDEF(VT);
1847 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1848 R==APFloat::cmpLessThan, VT);
1849 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1850 return getUNDEF(VT);
1852 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1853 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1854 return getUNDEF(VT);
1856 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1857 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1858 return getUNDEF(VT);
1860 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1861 R==APFloat::cmpEqual, VT);
1862 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1863 return getUNDEF(VT);
1865 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1866 R==APFloat::cmpEqual, VT);
1867 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1868 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1869 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1870 R==APFloat::cmpEqual, VT);
1871 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1872 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1873 R==APFloat::cmpLessThan, VT);
1874 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1875 R==APFloat::cmpUnordered, VT);
1876 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1877 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1880 // Ensure that the constant occurs on the RHS.
1881 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1882 MVT CompVT = N1.getValueType().getSimpleVT();
1883 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1886 return getSetCC(dl, VT, N2, N1, SwappedCond);
1890 // Could not fold it.
1894 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1895 /// use this predicate to simplify operations downstream.
1896 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1897 // This predicate is not safe for vector operations.
1898 if (Op.getValueType().isVector())
1901 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1902 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1905 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1906 /// this predicate to simplify operations downstream. Mask is known to be zero
1907 /// for bits that V cannot have.
1908 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1909 unsigned Depth) const {
1910 APInt KnownZero, KnownOne;
1911 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1912 return (KnownZero & Mask) == Mask;
1915 /// Determine which bits of Op are known to be either zero or one and return
1916 /// them in the KnownZero/KnownOne bitsets.
1917 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1918 APInt &KnownOne, unsigned Depth) const {
1919 const TargetLowering *TLI = TM.getTargetLowering();
1920 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1922 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1924 return; // Limit search depth.
1926 APInt KnownZero2, KnownOne2;
1928 switch (Op.getOpcode()) {
1930 // We know all of the bits for a constant!
1931 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1932 KnownZero = ~KnownOne;
1935 // If either the LHS or the RHS are Zero, the result is zero.
1936 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1937 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1939 // Output known-1 bits are only known if set in both the LHS & RHS.
1940 KnownOne &= KnownOne2;
1941 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1942 KnownZero |= KnownZero2;
1945 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1946 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1948 // Output known-0 bits are only known if clear in both the LHS & RHS.
1949 KnownZero &= KnownZero2;
1950 // Output known-1 are known to be set if set in either the LHS | RHS.
1951 KnownOne |= KnownOne2;
1954 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1955 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1957 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1958 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1959 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1960 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1961 KnownZero = KnownZeroOut;
1965 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1966 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1968 // If low bits are zero in either operand, output low known-0 bits.
1969 // Also compute a conserative estimate for high known-0 bits.
1970 // More trickiness is possible, but this is sufficient for the
1971 // interesting case of alignment computation.
1972 KnownOne.clearAllBits();
1973 unsigned TrailZ = KnownZero.countTrailingOnes() +
1974 KnownZero2.countTrailingOnes();
1975 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1976 KnownZero2.countLeadingOnes(),
1977 BitWidth) - BitWidth;
1979 TrailZ = std::min(TrailZ, BitWidth);
1980 LeadZ = std::min(LeadZ, BitWidth);
1981 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1982 APInt::getHighBitsSet(BitWidth, LeadZ);
1986 // For the purposes of computing leading zeros we can conservatively
1987 // treat a udiv as a logical right shift by the power of 2 known to
1988 // be less than the denominator.
1989 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1990 unsigned LeadZ = KnownZero2.countLeadingOnes();
1992 KnownOne2.clearAllBits();
1993 KnownZero2.clearAllBits();
1994 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1995 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1996 if (RHSUnknownLeadingOnes != BitWidth)
1997 LeadZ = std::min(BitWidth,
1998 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2000 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2004 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2005 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2007 // Only known if known in both the LHS and RHS.
2008 KnownOne &= KnownOne2;
2009 KnownZero &= KnownZero2;
2011 case ISD::SELECT_CC:
2012 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2013 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2015 // Only known if known in both the LHS and RHS.
2016 KnownOne &= KnownOne2;
2017 KnownZero &= KnownZero2;
2025 if (Op.getResNo() != 1)
2027 // The boolean result conforms to getBooleanContents.
2028 // If we know the result of a setcc has the top bits zero, use this info.
2029 // We know that we have an integer-based boolean since these operations
2030 // are only available for integer.
2031 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2032 TargetLowering::ZeroOrOneBooleanContent &&
2034 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2037 // If we know the result of a setcc has the top bits zero, use this info.
2038 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2039 TargetLowering::ZeroOrOneBooleanContent &&
2041 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2044 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2045 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2046 unsigned ShAmt = SA->getZExtValue();
2048 // If the shift count is an invalid immediate, don't do anything.
2049 if (ShAmt >= BitWidth)
2052 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2053 KnownZero <<= ShAmt;
2055 // low bits known zero.
2056 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2060 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2061 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2062 unsigned ShAmt = SA->getZExtValue();
2064 // If the shift count is an invalid immediate, don't do anything.
2065 if (ShAmt >= BitWidth)
2068 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2069 KnownZero = KnownZero.lshr(ShAmt);
2070 KnownOne = KnownOne.lshr(ShAmt);
2072 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2073 KnownZero |= HighBits; // High bits known zero.
2077 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2078 unsigned ShAmt = SA->getZExtValue();
2080 // If the shift count is an invalid immediate, don't do anything.
2081 if (ShAmt >= BitWidth)
2084 // If any of the demanded bits are produced by the sign extension, we also
2085 // demand the input sign bit.
2086 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2088 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2089 KnownZero = KnownZero.lshr(ShAmt);
2090 KnownOne = KnownOne.lshr(ShAmt);
2092 // Handle the sign bits.
2093 APInt SignBit = APInt::getSignBit(BitWidth);
2094 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2096 if (KnownZero.intersects(SignBit)) {
2097 KnownZero |= HighBits; // New bits are known zero.
2098 } else if (KnownOne.intersects(SignBit)) {
2099 KnownOne |= HighBits; // New bits are known one.
2103 case ISD::SIGN_EXTEND_INREG: {
2104 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2105 unsigned EBits = EVT.getScalarType().getSizeInBits();
2107 // Sign extension. Compute the demanded bits in the result that are not
2108 // present in the input.
2109 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2111 APInt InSignBit = APInt::getSignBit(EBits);
2112 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2114 // If the sign extended bits are demanded, we know that the sign
2116 InSignBit = InSignBit.zext(BitWidth);
2117 if (NewBits.getBoolValue())
2118 InputDemandedBits |= InSignBit;
2120 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2121 KnownOne &= InputDemandedBits;
2122 KnownZero &= InputDemandedBits;
2124 // If the sign bit of the input is known set or clear, then we know the
2125 // top bits of the result.
2126 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2127 KnownZero |= NewBits;
2128 KnownOne &= ~NewBits;
2129 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2130 KnownOne |= NewBits;
2131 KnownZero &= ~NewBits;
2132 } else { // Input sign bit unknown
2133 KnownZero &= ~NewBits;
2134 KnownOne &= ~NewBits;
2139 case ISD::CTTZ_ZERO_UNDEF:
2141 case ISD::CTLZ_ZERO_UNDEF:
2143 unsigned LowBits = Log2_32(BitWidth)+1;
2144 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2145 KnownOne.clearAllBits();
2149 LoadSDNode *LD = cast<LoadSDNode>(Op);
2150 // If this is a ZEXTLoad and we are looking at the loaded value.
2151 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2152 EVT VT = LD->getMemoryVT();
2153 unsigned MemBits = VT.getScalarType().getSizeInBits();
2154 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2155 } else if (const MDNode *Ranges = LD->getRanges()) {
2156 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2160 case ISD::ZERO_EXTEND: {
2161 EVT InVT = Op.getOperand(0).getValueType();
2162 unsigned InBits = InVT.getScalarType().getSizeInBits();
2163 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2164 KnownZero = KnownZero.trunc(InBits);
2165 KnownOne = KnownOne.trunc(InBits);
2166 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2167 KnownZero = KnownZero.zext(BitWidth);
2168 KnownOne = KnownOne.zext(BitWidth);
2169 KnownZero |= NewBits;
2172 case ISD::SIGN_EXTEND: {
2173 EVT InVT = Op.getOperand(0).getValueType();
2174 unsigned InBits = InVT.getScalarType().getSizeInBits();
2175 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2177 KnownZero = KnownZero.trunc(InBits);
2178 KnownOne = KnownOne.trunc(InBits);
2179 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2181 // Note if the sign bit is known to be zero or one.
2182 bool SignBitKnownZero = KnownZero.isNegative();
2183 bool SignBitKnownOne = KnownOne.isNegative();
2185 KnownZero = KnownZero.zext(BitWidth);
2186 KnownOne = KnownOne.zext(BitWidth);
2188 // If the sign bit is known zero or one, the top bits match.
2189 if (SignBitKnownZero)
2190 KnownZero |= NewBits;
2191 else if (SignBitKnownOne)
2192 KnownOne |= NewBits;
2195 case ISD::ANY_EXTEND: {
2196 EVT InVT = Op.getOperand(0).getValueType();
2197 unsigned InBits = InVT.getScalarType().getSizeInBits();
2198 KnownZero = KnownZero.trunc(InBits);
2199 KnownOne = KnownOne.trunc(InBits);
2200 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2201 KnownZero = KnownZero.zext(BitWidth);
2202 KnownOne = KnownOne.zext(BitWidth);
2205 case ISD::TRUNCATE: {
2206 EVT InVT = Op.getOperand(0).getValueType();
2207 unsigned InBits = InVT.getScalarType().getSizeInBits();
2208 KnownZero = KnownZero.zext(InBits);
2209 KnownOne = KnownOne.zext(InBits);
2210 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 KnownZero = KnownZero.trunc(BitWidth);
2212 KnownOne = KnownOne.trunc(BitWidth);
2215 case ISD::AssertZext: {
2216 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2217 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2218 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2219 KnownZero |= (~InMask);
2220 KnownOne &= (~KnownZero);
2224 // All bits are zero except the low bit.
2225 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2229 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2230 // We know that the top bits of C-X are clear if X contains less bits
2231 // than C (i.e. no wrap-around can happen). For example, 20-X is
2232 // positive if we can prove that X is >= 0 and < 16.
2233 if (CLHS->getAPIntValue().isNonNegative()) {
2234 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2235 // NLZ can't be BitWidth with no sign bit
2236 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2237 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2239 // If all of the MaskV bits are known to be zero, then we know the
2240 // output top bits are zero, because we now know that the output is
2242 if ((KnownZero2 & MaskV) == MaskV) {
2243 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2244 // Top bits known zero.
2245 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2253 // Output known-0 bits are known if clear or set in both the low clear bits
2254 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2255 // low 3 bits clear.
2256 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2257 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2259 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2260 KnownZeroOut = std::min(KnownZeroOut,
2261 KnownZero2.countTrailingOnes());
2263 if (Op.getOpcode() == ISD::ADD) {
2264 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2268 // With ADDE, a carry bit may be added in, so we can only use this
2269 // information if we know (at least) that the low two bits are clear. We
2270 // then return to the caller that the low bit is unknown but that other bits
2272 if (KnownZeroOut >= 2) // ADDE
2273 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2277 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2278 const APInt &RA = Rem->getAPIntValue().abs();
2279 if (RA.isPowerOf2()) {
2280 APInt LowBits = RA - 1;
2281 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2283 // The low bits of the first operand are unchanged by the srem.
2284 KnownZero = KnownZero2 & LowBits;
2285 KnownOne = KnownOne2 & LowBits;
2287 // If the first operand is non-negative or has all low bits zero, then
2288 // the upper bits are all zero.
2289 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2290 KnownZero |= ~LowBits;
2292 // If the first operand is negative and not all low bits are zero, then
2293 // the upper bits are all one.
2294 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2295 KnownOne |= ~LowBits;
2296 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2301 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2302 const APInt &RA = Rem->getAPIntValue();
2303 if (RA.isPowerOf2()) {
2304 APInt LowBits = (RA - 1);
2305 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2307 // The upper bits are all zero, the lower ones are unchanged.
2308 KnownZero = KnownZero2 | ~LowBits;
2309 KnownOne = KnownOne2 & LowBits;
2314 // Since the result is less than or equal to either operand, any leading
2315 // zero bits in either operand must also exist in the result.
2316 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2317 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2319 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2320 KnownZero2.countLeadingOnes());
2321 KnownOne.clearAllBits();
2322 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2325 case ISD::FrameIndex:
2326 case ISD::TargetFrameIndex:
2327 if (unsigned Align = InferPtrAlignment(Op)) {
2328 // The low bits are known zero if the pointer is aligned.
2329 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2335 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2338 case ISD::INTRINSIC_WO_CHAIN:
2339 case ISD::INTRINSIC_W_CHAIN:
2340 case ISD::INTRINSIC_VOID:
2341 // Allow the target to implement this method for its nodes.
2342 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2346 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2349 /// ComputeNumSignBits - Return the number of times the sign bit of the
2350 /// register is replicated into the other bits. We know that at least 1 bit
2351 /// is always equal to the sign bit (itself), but other cases can give us
2352 /// information. For example, immediately after an "SRA X, 2", we know that
2353 /// the top 3 bits are all equal to each other, so we return 3.
2354 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2355 const TargetLowering *TLI = TM.getTargetLowering();
2356 EVT VT = Op.getValueType();
2357 assert(VT.isInteger() && "Invalid VT!");
2358 unsigned VTBits = VT.getScalarType().getSizeInBits();
2360 unsigned FirstAnswer = 1;
2363 return 1; // Limit search depth.
2365 switch (Op.getOpcode()) {
2367 case ISD::AssertSext:
2368 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2369 return VTBits-Tmp+1;
2370 case ISD::AssertZext:
2371 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2374 case ISD::Constant: {
2375 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2376 return Val.getNumSignBits();
2379 case ISD::SIGN_EXTEND:
2381 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2382 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2384 case ISD::SIGN_EXTEND_INREG:
2385 // Max of the input and what this extends.
2387 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2390 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2391 return std::max(Tmp, Tmp2);
2394 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395 // SRA X, C -> adds C sign bits.
2396 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397 Tmp += C->getZExtValue();
2398 if (Tmp > VTBits) Tmp = VTBits;
2402 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2403 // shl destroys sign bits.
2404 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2405 if (C->getZExtValue() >= VTBits || // Bad shift.
2406 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2407 return Tmp - C->getZExtValue();
2412 case ISD::XOR: // NOT is handled here.
2413 // Logical binary ops preserve the number of sign bits at the worst.
2414 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2416 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2417 FirstAnswer = std::min(Tmp, Tmp2);
2418 // We computed what we know about the sign bits as our first
2419 // answer. Now proceed to the generic code that uses
2420 // computeKnownBits, and pick whichever answer is better.
2425 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2426 if (Tmp == 1) return 1; // Early out.
2427 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2428 return std::min(Tmp, Tmp2);
2436 if (Op.getResNo() != 1)
2438 // The boolean result conforms to getBooleanContents. Fall through.
2439 // If setcc returns 0/-1, all bits are sign bits.
2440 // We know that we have an integer-based boolean since these operations
2441 // are only available for integer.
2442 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2443 TargetLowering::ZeroOrNegativeOneBooleanContent)
2447 // If setcc returns 0/-1, all bits are sign bits.
2448 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2449 TargetLowering::ZeroOrNegativeOneBooleanContent)
2454 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2455 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2457 // Handle rotate right by N like a rotate left by 32-N.
2458 if (Op.getOpcode() == ISD::ROTR)
2459 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2461 // If we aren't rotating out all of the known-in sign bits, return the
2462 // number that are left. This handles rotl(sext(x), 1) for example.
2463 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2464 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2468 // Add can have at most one carry bit. Thus we know that the output
2469 // is, at worst, one more bit than the inputs.
2470 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471 if (Tmp == 1) return 1; // Early out.
2473 // Special case decrementing a value (ADD X, -1):
2474 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2475 if (CRHS->isAllOnesValue()) {
2476 APInt KnownZero, KnownOne;
2477 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2479 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2481 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2484 // If we are subtracting one from a positive number, there is no carry
2485 // out of the result.
2486 if (KnownZero.isNegative())
2490 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2491 if (Tmp2 == 1) return 1;
2492 return std::min(Tmp, Tmp2)-1;
2495 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2496 if (Tmp2 == 1) return 1;
2499 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2500 if (CLHS->isNullValue()) {
2501 APInt KnownZero, KnownOne;
2502 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2503 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2505 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2508 // If the input is known to be positive (the sign bit is known clear),
2509 // the output of the NEG has the same number of sign bits as the input.
2510 if (KnownZero.isNegative())
2513 // Otherwise, we treat this like a SUB.
2516 // Sub can have at most one carry bit. Thus we know that the output
2517 // is, at worst, one more bit than the inputs.
2518 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2519 if (Tmp == 1) return 1; // Early out.
2520 return std::min(Tmp, Tmp2)-1;
2522 // FIXME: it's tricky to do anything useful for this, but it is an important
2523 // case for targets like X86.
2527 // If we are looking at the loaded value of the SDNode.
2528 if (Op.getResNo() == 0) {
2529 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2530 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2531 unsigned ExtType = LD->getExtensionType();
2534 case ISD::SEXTLOAD: // '17' bits known
2535 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2536 return VTBits-Tmp+1;
2537 case ISD::ZEXTLOAD: // '16' bits known
2538 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2544 // Allow the target to implement this method for its nodes.
2545 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2546 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2547 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2548 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2549 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2550 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2553 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2554 // use this information.
2555 APInt KnownZero, KnownOne;
2556 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2559 if (KnownZero.isNegative()) { // sign bit is 0
2561 } else if (KnownOne.isNegative()) { // sign bit is 1;
2568 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2569 // the number of identical bits in the top of the input value.
2571 Mask <<= Mask.getBitWidth()-VTBits;
2572 // Return # leading zeros. We use 'min' here in case Val was zero before
2573 // shifting. We don't want to return '64' as for an i32 "0".
2574 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2577 /// isBaseWithConstantOffset - Return true if the specified operand is an
2578 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2579 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2580 /// semantics as an ADD. This handles the equivalence:
2581 /// X|Cst == X+Cst iff X&Cst = 0.
2582 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2583 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2584 !isa<ConstantSDNode>(Op.getOperand(1)))
2587 if (Op.getOpcode() == ISD::OR &&
2588 !MaskedValueIsZero(Op.getOperand(0),
2589 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2596 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2597 // If we're told that NaNs won't happen, assume they won't.
2598 if (getTarget().Options.NoNaNsFPMath)
2601 // If the value is a constant, we can obviously see if it is a NaN or not.
2602 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2603 return !C->getValueAPF().isNaN();
2605 // TODO: Recognize more cases here.
2610 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2611 // If the value is a constant, we can obviously see if it is a zero or not.
2612 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2613 return !C->isZero();
2615 // TODO: Recognize more cases here.
2616 switch (Op.getOpcode()) {
2619 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2620 return !C->isNullValue();
2627 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2628 // Check the obvious case.
2629 if (A == B) return true;
2631 // For for negative and positive zero.
2632 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2633 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2634 if (CA->isZero() && CB->isZero()) return true;
2636 // Otherwise they may not be equal.
2640 /// getNode - Gets or creates the specified node.
2642 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2643 FoldingSetNodeID ID;
2644 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2647 return SDValue(E, 0);
2649 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2650 DL.getDebugLoc(), getVTList(VT));
2651 CSEMap.InsertNode(N, IP);
2654 return SDValue(N, 0);
2657 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2658 EVT VT, SDValue Operand) {
2659 // Constant fold unary operations with an integer constant operand. Even
2660 // opaque constant will be folded, because the folding of unary operations
2661 // doesn't create new constants with different values. Nevertheless, the
2662 // opaque flag is preserved during folding to prevent future folding with
2664 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2665 const APInt &Val = C->getAPIntValue();
2668 case ISD::SIGN_EXTEND:
2669 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2670 C->isTargetOpcode(), C->isOpaque());
2671 case ISD::ANY_EXTEND:
2672 case ISD::ZERO_EXTEND:
2674 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2675 C->isTargetOpcode(), C->isOpaque());
2676 case ISD::UINT_TO_FP:
2677 case ISD::SINT_TO_FP: {
2678 APFloat apf(EVTToAPFloatSemantics(VT),
2679 APInt::getNullValue(VT.getSizeInBits()));
2680 (void)apf.convertFromAPInt(Val,
2681 Opcode==ISD::SINT_TO_FP,
2682 APFloat::rmNearestTiesToEven);
2683 return getConstantFP(apf, VT);
2686 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2687 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2688 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2689 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2692 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2695 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2698 case ISD::CTLZ_ZERO_UNDEF:
2699 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2702 case ISD::CTTZ_ZERO_UNDEF:
2703 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2708 // Constant fold unary operations with a floating point constant operand.
2709 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2710 APFloat V = C->getValueAPF(); // make copy
2714 return getConstantFP(V, VT);
2717 return getConstantFP(V, VT);
2719 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2720 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2721 return getConstantFP(V, VT);
2725 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2726 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2727 return getConstantFP(V, VT);
2731 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2732 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2733 return getConstantFP(V, VT);
2736 case ISD::FP_EXTEND: {
2738 // This can return overflow, underflow, or inexact; we don't care.
2739 // FIXME need to be more flexible about rounding mode.
2740 (void)V.convert(EVTToAPFloatSemantics(VT),
2741 APFloat::rmNearestTiesToEven, &ignored);
2742 return getConstantFP(V, VT);
2744 case ISD::FP_TO_SINT:
2745 case ISD::FP_TO_UINT: {
2748 assert(integerPartWidth >= 64);
2749 // FIXME need to be more flexible about rounding mode.
2750 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2751 Opcode==ISD::FP_TO_SINT,
2752 APFloat::rmTowardZero, &ignored);
2753 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2755 APInt api(VT.getSizeInBits(), x);
2756 return getConstant(api, VT);
2759 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2760 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2761 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2762 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2767 // Constant fold unary operations with a vector integer operand.
2768 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2771 unsigned SplatBitSize;
2772 bool DummyHasUndefs;
2773 if (BV->isConstantSplat(Val, DummyUndefs, SplatBitSize, DummyHasUndefs)) {
2776 // FIXME: Entirely reasonable to perform folding of other unary
2777 // operations here as the need arises.
2779 case ISD::UINT_TO_FP:
2780 case ISD::SINT_TO_FP: {
2782 EVTToAPFloatSemantics(VT.getVectorElementType()),
2783 APInt::getNullValue(VT.getVectorElementType().getSizeInBits()));
2784 (void)APF.convertFromAPInt(Val, Opcode == ISD::SINT_TO_FP,
2785 APFloat::rmNearestTiesToEven);
2787 return getConstantFP(APF, VT);
2793 unsigned OpOpcode = Operand.getNode()->getOpcode();
2795 case ISD::TokenFactor:
2796 case ISD::MERGE_VALUES:
2797 case ISD::CONCAT_VECTORS:
2798 return Operand; // Factor, merge or concat of one node? No need.
2799 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2800 case ISD::FP_EXTEND:
2801 assert(VT.isFloatingPoint() &&
2802 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2803 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2804 assert((!VT.isVector() ||
2805 VT.getVectorNumElements() ==
2806 Operand.getValueType().getVectorNumElements()) &&
2807 "Vector element count mismatch!");
2808 if (Operand.getOpcode() == ISD::UNDEF)
2809 return getUNDEF(VT);
2811 case ISD::SIGN_EXTEND:
2812 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2813 "Invalid SIGN_EXTEND!");
2814 if (Operand.getValueType() == VT) return Operand; // noop extension
2815 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2816 "Invalid sext node, dst < src!");
2817 assert((!VT.isVector() ||
2818 VT.getVectorNumElements() ==
2819 Operand.getValueType().getVectorNumElements()) &&
2820 "Vector element count mismatch!");
2821 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2822 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2823 else if (OpOpcode == ISD::UNDEF)
2824 // sext(undef) = 0, because the top bits will all be the same.
2825 return getConstant(0, VT);
2827 case ISD::ZERO_EXTEND:
2828 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2829 "Invalid ZERO_EXTEND!");
2830 if (Operand.getValueType() == VT) return Operand; // noop extension
2831 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2832 "Invalid zext node, dst < src!");
2833 assert((!VT.isVector() ||
2834 VT.getVectorNumElements() ==
2835 Operand.getValueType().getVectorNumElements()) &&
2836 "Vector element count mismatch!");
2837 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2838 return getNode(ISD::ZERO_EXTEND, DL, VT,
2839 Operand.getNode()->getOperand(0));
2840 else if (OpOpcode == ISD::UNDEF)
2841 // zext(undef) = 0, because the top bits will be zero.
2842 return getConstant(0, VT);
2844 case ISD::ANY_EXTEND:
2845 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2846 "Invalid ANY_EXTEND!");
2847 if (Operand.getValueType() == VT) return Operand; // noop extension
2848 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2849 "Invalid anyext node, dst < src!");
2850 assert((!VT.isVector() ||
2851 VT.getVectorNumElements() ==
2852 Operand.getValueType().getVectorNumElements()) &&
2853 "Vector element count mismatch!");
2855 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2856 OpOpcode == ISD::ANY_EXTEND)
2857 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2858 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2859 else if (OpOpcode == ISD::UNDEF)
2860 return getUNDEF(VT);
2862 // (ext (trunx x)) -> x
2863 if (OpOpcode == ISD::TRUNCATE) {
2864 SDValue OpOp = Operand.getNode()->getOperand(0);
2865 if (OpOp.getValueType() == VT)
2870 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2871 "Invalid TRUNCATE!");
2872 if (Operand.getValueType() == VT) return Operand; // noop truncate
2873 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2874 "Invalid truncate node, src < dst!");
2875 assert((!VT.isVector() ||
2876 VT.getVectorNumElements() ==
2877 Operand.getValueType().getVectorNumElements()) &&
2878 "Vector element count mismatch!");
2879 if (OpOpcode == ISD::TRUNCATE)
2880 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2881 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2882 OpOpcode == ISD::ANY_EXTEND) {
2883 // If the source is smaller than the dest, we still need an extend.
2884 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2885 .bitsLT(VT.getScalarType()))
2886 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2887 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2888 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2889 return Operand.getNode()->getOperand(0);
2891 if (OpOpcode == ISD::UNDEF)
2892 return getUNDEF(VT);
2895 // Basic sanity checking.
2896 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2897 && "Cannot BITCAST between types of different sizes!");
2898 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2899 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2900 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2901 if (OpOpcode == ISD::UNDEF)
2902 return getUNDEF(VT);
2904 case ISD::SCALAR_TO_VECTOR:
2905 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2906 (VT.getVectorElementType() == Operand.getValueType() ||
2907 (VT.getVectorElementType().isInteger() &&
2908 Operand.getValueType().isInteger() &&
2909 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2910 "Illegal SCALAR_TO_VECTOR node!");
2911 if (OpOpcode == ISD::UNDEF)
2912 return getUNDEF(VT);
2913 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2914 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2915 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2916 Operand.getConstantOperandVal(1) == 0 &&
2917 Operand.getOperand(0).getValueType() == VT)
2918 return Operand.getOperand(0);
2921 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2922 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2923 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2924 Operand.getNode()->getOperand(0));
2925 if (OpOpcode == ISD::FNEG) // --X -> X
2926 return Operand.getNode()->getOperand(0);
2929 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2930 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2935 SDVTList VTs = getVTList(VT);
2936 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2937 FoldingSetNodeID ID;
2938 SDValue Ops[1] = { Operand };
2939 AddNodeIDNode(ID, Opcode, VTs, Ops);
2941 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2942 return SDValue(E, 0);
2944 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2945 DL.getDebugLoc(), VTs, Operand);
2946 CSEMap.InsertNode(N, IP);
2948 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2949 DL.getDebugLoc(), VTs, Operand);
2953 return SDValue(N, 0);
2956 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2957 SDNode *Cst1, SDNode *Cst2) {
2958 // If the opcode is a target-specific ISD node, there's nothing we can
2959 // do here and the operand rules may not line up with the below, so
2961 if (Opcode >= ISD::BUILTIN_OP_END)
2964 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2965 SmallVector<SDValue, 4> Outputs;
2966 EVT SVT = VT.getScalarType();
2968 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2969 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2970 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2973 if (Scalar1 && Scalar2)
2974 // Scalar instruction.
2975 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2977 // For vectors extract each constant element into Inputs so we can constant
2978 // fold them individually.
2979 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2980 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2984 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2986 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2987 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2988 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2989 if (!V1 || !V2) // Not a constant, bail.
2992 if (V1->isOpaque() || V2->isOpaque())
2995 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2996 // FIXME: This is valid and could be handled by truncating the APInts.
2997 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3000 Inputs.push_back(std::make_pair(V1, V2));
3004 // We have a number of constant values, constant fold them element by element.
3005 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3006 const APInt &C1 = Inputs[I].first->getAPIntValue();
3007 const APInt &C2 = Inputs[I].second->getAPIntValue();
3011 Outputs.push_back(getConstant(C1 + C2, SVT));
3014 Outputs.push_back(getConstant(C1 - C2, SVT));
3017 Outputs.push_back(getConstant(C1 * C2, SVT));
3020 if (!C2.getBoolValue())
3022 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3025 if (!C2.getBoolValue())
3027 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3030 if (!C2.getBoolValue())
3032 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3035 if (!C2.getBoolValue())
3037 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3040 Outputs.push_back(getConstant(C1 & C2, SVT));
3043 Outputs.push_back(getConstant(C1 | C2, SVT));
3046 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3049 Outputs.push_back(getConstant(C1 << C2, SVT));
3052 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3055 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3058 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3061 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3068 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3069 "Expected a scalar or vector!"));
3071 // Handle the scalar case first.
3073 return Outputs.back();
3075 // We may have a vector type but a scalar result. Create a splat.
3076 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3078 // Build a big vector out of the scalar elements we generated.
3079 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3082 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3083 SDValue N2, bool nuw, bool nsw, bool exact) {
3084 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3085 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3088 case ISD::TokenFactor:
3089 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3090 N2.getValueType() == MVT::Other && "Invalid token factor!");
3091 // Fold trivial token factors.
3092 if (N1.getOpcode() == ISD::EntryToken) return N2;
3093 if (N2.getOpcode() == ISD::EntryToken) return N1;
3094 if (N1 == N2) return N1;
3096 case ISD::CONCAT_VECTORS:
3097 // Concat of UNDEFs is UNDEF.
3098 if (N1.getOpcode() == ISD::UNDEF &&
3099 N2.getOpcode() == ISD::UNDEF)
3100 return getUNDEF(VT);
3102 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3103 // one big BUILD_VECTOR.
3104 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3105 N2.getOpcode() == ISD::BUILD_VECTOR) {
3106 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3107 N1.getNode()->op_end());
3108 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3109 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3113 assert(VT.isInteger() && "This operator does not apply to FP types!");
3114 assert(N1.getValueType() == N2.getValueType() &&
3115 N1.getValueType() == VT && "Binary operator types must match!");
3116 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3117 // worth handling here.
3118 if (N2C && N2C->isNullValue())
3120 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3127 assert(VT.isInteger() && "This operator does not apply to FP types!");
3128 assert(N1.getValueType() == N2.getValueType() &&
3129 N1.getValueType() == VT && "Binary operator types must match!");
3130 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3131 // it's worth handling here.
3132 if (N2C && N2C->isNullValue())
3142 assert(VT.isInteger() && "This operator does not apply to FP types!");
3143 assert(N1.getValueType() == N2.getValueType() &&
3144 N1.getValueType() == VT && "Binary operator types must match!");
3151 if (getTarget().Options.UnsafeFPMath) {
3152 if (Opcode == ISD::FADD) {
3154 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3155 if (CFP->getValueAPF().isZero())
3158 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3159 if (CFP->getValueAPF().isZero())
3161 } else if (Opcode == ISD::FSUB) {
3163 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3164 if (CFP->getValueAPF().isZero())
3166 } else if (Opcode == ISD::FMUL) {
3167 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3170 // If the first operand isn't the constant, try the second
3172 CFP = dyn_cast<ConstantFPSDNode>(N2);
3179 return SDValue(CFP,0);
3181 if (CFP->isExactlyValue(1.0))
3186 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3187 assert(N1.getValueType() == N2.getValueType() &&
3188 N1.getValueType() == VT && "Binary operator types must match!");
3190 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3191 assert(N1.getValueType() == VT &&
3192 N1.getValueType().isFloatingPoint() &&
3193 N2.getValueType().isFloatingPoint() &&
3194 "Invalid FCOPYSIGN!");
3201 assert(VT == N1.getValueType() &&
3202 "Shift operators return type must be the same as their first arg");
3203 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3204 "Shifts only work on integers");
3205 assert((!VT.isVector() || VT == N2.getValueType()) &&
3206 "Vector shift amounts must be in the same as their first arg");
3207 // Verify that the shift amount VT is bit enough to hold valid shift
3208 // amounts. This catches things like trying to shift an i1024 value by an
3209 // i8, which is easy to fall into in generic code that uses
3210 // TLI.getShiftAmount().
3211 assert(N2.getValueType().getSizeInBits() >=
3212 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3213 "Invalid use of small shift amount with oversized value!");
3215 // Always fold shifts of i1 values so the code generator doesn't need to
3216 // handle them. Since we know the size of the shift has to be less than the
3217 // size of the value, the shift/rotate count is guaranteed to be zero.
3220 if (N2C && N2C->isNullValue())
3223 case ISD::FP_ROUND_INREG: {
3224 EVT EVT = cast<VTSDNode>(N2)->getVT();
3225 assert(VT == N1.getValueType() && "Not an inreg round!");
3226 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3227 "Cannot FP_ROUND_INREG integer types");
3228 assert(EVT.isVector() == VT.isVector() &&
3229 "FP_ROUND_INREG type should be vector iff the operand "
3231 assert((!EVT.isVector() ||
3232 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3233 "Vector element counts must match in FP_ROUND_INREG");
3234 assert(EVT.bitsLE(VT) && "Not rounding down!");
3236 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3240 assert(VT.isFloatingPoint() &&
3241 N1.getValueType().isFloatingPoint() &&
3242 VT.bitsLE(N1.getValueType()) &&
3243 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3244 if (N1.getValueType() == VT) return N1; // noop conversion.
3246 case ISD::AssertSext:
3247 case ISD::AssertZext: {
3248 EVT EVT = cast<VTSDNode>(N2)->getVT();
3249 assert(VT == N1.getValueType() && "Not an inreg extend!");
3250 assert(VT.isInteger() && EVT.isInteger() &&
3251 "Cannot *_EXTEND_INREG FP types");
3252 assert(!EVT.isVector() &&
3253 "AssertSExt/AssertZExt type should be the vector element type "
3254 "rather than the vector type!");
3255 assert(EVT.bitsLE(VT) && "Not extending!");
3256 if (VT == EVT) return N1; // noop assertion.
3259 case ISD::SIGN_EXTEND_INREG: {
3260 EVT EVT = cast<VTSDNode>(N2)->getVT();
3261 assert(VT == N1.getValueType() && "Not an inreg extend!");
3262 assert(VT.isInteger() && EVT.isInteger() &&
3263 "Cannot *_EXTEND_INREG FP types");
3264 assert(EVT.isVector() == VT.isVector() &&
3265 "SIGN_EXTEND_INREG type should be vector iff the operand "
3267 assert((!EVT.isVector() ||
3268 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3269 "Vector element counts must match in SIGN_EXTEND_INREG");
3270 assert(EVT.bitsLE(VT) && "Not extending!");
3271 if (EVT == VT) return N1; // Not actually extending
3274 APInt Val = N1C->getAPIntValue();
3275 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3276 Val <<= Val.getBitWidth()-FromBits;
3277 Val = Val.ashr(Val.getBitWidth()-FromBits);
3278 return getConstant(Val, VT);
3282 case ISD::EXTRACT_VECTOR_ELT:
3283 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3284 if (N1.getOpcode() == ISD::UNDEF)
3285 return getUNDEF(VT);
3287 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3288 // expanding copies of large vectors from registers.
3290 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3291 N1.getNumOperands() > 0) {
3293 N1.getOperand(0).getValueType().getVectorNumElements();
3294 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3295 N1.getOperand(N2C->getZExtValue() / Factor),
3296 getConstant(N2C->getZExtValue() % Factor,
3297 N2.getValueType()));
3300 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3301 // expanding large vector constants.
3302 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3303 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3305 if (VT != Elt.getValueType())
3306 // If the vector element type is not legal, the BUILD_VECTOR operands
3307 // are promoted and implicitly truncated, and the result implicitly
3308 // extended. Make that explicit here.
3309 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3314 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3315 // operations are lowered to scalars.
3316 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3317 // If the indices are the same, return the inserted element else
3318 // if the indices are known different, extract the element from
3319 // the original vector.
3320 SDValue N1Op2 = N1.getOperand(2);
3321 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3323 if (N1Op2C && N2C) {
3324 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3325 if (VT == N1.getOperand(1).getValueType())
3326 return N1.getOperand(1);
3328 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3331 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3335 case ISD::EXTRACT_ELEMENT:
3336 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3337 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3338 (N1.getValueType().isInteger() == VT.isInteger()) &&
3339 N1.getValueType() != VT &&
3340 "Wrong types for EXTRACT_ELEMENT!");
3342 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3343 // 64-bit integers into 32-bit parts. Instead of building the extract of
3344 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3345 if (N1.getOpcode() == ISD::BUILD_PAIR)
3346 return N1.getOperand(N2C->getZExtValue());
3348 // EXTRACT_ELEMENT of a constant int is also very common.
3349 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3350 unsigned ElementSize = VT.getSizeInBits();
3351 unsigned Shift = ElementSize * N2C->getZExtValue();
3352 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3353 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3356 case ISD::EXTRACT_SUBVECTOR: {
3358 if (VT.isSimple() && N1.getValueType().isSimple()) {
3359 assert(VT.isVector() && N1.getValueType().isVector() &&
3360 "Extract subvector VTs must be a vectors!");
3361 assert(VT.getVectorElementType() ==
3362 N1.getValueType().getVectorElementType() &&
3363 "Extract subvector VTs must have the same element type!");
3364 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3365 "Extract subvector must be from larger vector to smaller vector!");
3367 if (isa<ConstantSDNode>(Index.getNode())) {
3368 assert((VT.getVectorNumElements() +
3369 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3370 <= N1.getValueType().getVectorNumElements())
3371 && "Extract subvector overflow!");
3374 // Trivial extraction.
3375 if (VT.getSimpleVT() == N1.getSimpleValueType())
3382 // Perform trivial constant folding.
3383 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3384 if (SV.getNode()) return SV;
3386 // Canonicalize constant to RHS if commutative.
3387 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3388 std::swap(N1C, N2C);
3392 // Constant fold FP operations.
3393 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3394 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3396 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3397 // Canonicalize constant to RHS if commutative.
3398 std::swap(N1CFP, N2CFP);
3401 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3402 APFloat::opStatus s;
3405 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3406 if (s != APFloat::opInvalidOp)
3407 return getConstantFP(V1, VT);
3410 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3411 if (s!=APFloat::opInvalidOp)
3412 return getConstantFP(V1, VT);
3415 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3416 if (s!=APFloat::opInvalidOp)
3417 return getConstantFP(V1, VT);
3420 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3421 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3422 return getConstantFP(V1, VT);
3425 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3426 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3427 return getConstantFP(V1, VT);
3429 case ISD::FCOPYSIGN:
3431 return getConstantFP(V1, VT);
3436 if (Opcode == ISD::FP_ROUND) {
3437 APFloat V = N1CFP->getValueAPF(); // make copy
3439 // This can return overflow, underflow, or inexact; we don't care.
3440 // FIXME need to be more flexible about rounding mode.
3441 (void)V.convert(EVTToAPFloatSemantics(VT),
3442 APFloat::rmNearestTiesToEven, &ignored);
3443 return getConstantFP(V, VT);
3447 // Canonicalize an UNDEF to the RHS, even over a constant.
3448 if (N1.getOpcode() == ISD::UNDEF) {
3449 if (isCommutativeBinOp(Opcode)) {
3453 case ISD::FP_ROUND_INREG:
3454 case ISD::SIGN_EXTEND_INREG:
3460 return N1; // fold op(undef, arg2) -> undef
3468 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3469 // For vectors, we can't easily build an all zero vector, just return
3476 // Fold a bunch of operators when the RHS is undef.
3477 if (N2.getOpcode() == ISD::UNDEF) {
3480 if (N1.getOpcode() == ISD::UNDEF)
3481 // Handle undef ^ undef -> 0 special case. This is a common
3483 return getConstant(0, VT);
3493 return N2; // fold op(arg1, undef) -> undef
3499 if (getTarget().Options.UnsafeFPMath)
3507 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3508 // For vectors, we can't easily build an all zero vector, just return
3513 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3514 // For vectors, we can't easily build an all one vector, just return
3522 // Memoize this node if possible.
3524 SDVTList VTs = getVTList(VT);
3525 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3526 if (VT != MVT::Glue) {
3527 SDValue Ops[] = {N1, N2};
3528 FoldingSetNodeID ID;
3529 AddNodeIDNode(ID, Opcode, VTs, Ops);
3531 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3533 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3534 return SDValue(E, 0);
3536 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3538 CSEMap.InsertNode(N, IP);
3541 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3545 return SDValue(N, 0);
3548 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3549 SDValue N1, SDValue N2, SDValue N3) {
3550 // Perform various simplifications.
3551 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3554 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3555 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3556 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3557 if (N1CFP && N2CFP && N3CFP) {
3558 APFloat V1 = N1CFP->getValueAPF();
3559 const APFloat &V2 = N2CFP->getValueAPF();
3560 const APFloat &V3 = N3CFP->getValueAPF();
3561 APFloat::opStatus s =
3562 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3563 if (s != APFloat::opInvalidOp)
3564 return getConstantFP(V1, VT);
3568 case ISD::CONCAT_VECTORS:
3569 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3570 // one big BUILD_VECTOR.
3571 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3572 N2.getOpcode() == ISD::BUILD_VECTOR &&
3573 N3.getOpcode() == ISD::BUILD_VECTOR) {
3574 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3575 N1.getNode()->op_end());
3576 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3577 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3578 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3582 // Use FoldSetCC to simplify SETCC's.
3583 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3584 if (Simp.getNode()) return Simp;
3589 if (N1C->getZExtValue())
3590 return N2; // select true, X, Y -> X
3591 return N3; // select false, X, Y -> Y
3594 if (N2 == N3) return N2; // select C, X, X -> X
3596 case ISD::VECTOR_SHUFFLE:
3597 llvm_unreachable("should use getVectorShuffle constructor!");
3598 case ISD::INSERT_SUBVECTOR: {
3600 if (VT.isSimple() && N1.getValueType().isSimple()
3601 && N2.getValueType().isSimple()) {
3602 assert(VT.isVector() && N1.getValueType().isVector() &&
3603 N2.getValueType().isVector() &&
3604 "Insert subvector VTs must be a vectors");
3605 assert(VT == N1.getValueType() &&
3606 "Dest and insert subvector source types must match!");
3607 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3608 "Insert subvector must be from smaller vector to larger vector!");
3609 if (isa<ConstantSDNode>(Index.getNode())) {
3610 assert((N2.getValueType().getVectorNumElements() +
3611 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3612 <= VT.getVectorNumElements())
3613 && "Insert subvector overflow!");
3616 // Trivial insertion.
3617 if (VT.getSimpleVT() == N2.getSimpleValueType())
3623 // Fold bit_convert nodes from a type to themselves.
3624 if (N1.getValueType() == VT)
3629 // Memoize node if it doesn't produce a flag.
3631 SDVTList VTs = getVTList(VT);
3632 if (VT != MVT::Glue) {
3633 SDValue Ops[] = { N1, N2, N3 };
3634 FoldingSetNodeID ID;
3635 AddNodeIDNode(ID, Opcode, VTs, Ops);
3637 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3638 return SDValue(E, 0);
3640 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3641 DL.getDebugLoc(), VTs, N1, N2, N3);
3642 CSEMap.InsertNode(N, IP);
3644 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3645 DL.getDebugLoc(), VTs, N1, N2, N3);
3649 return SDValue(N, 0);
3652 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3653 SDValue N1, SDValue N2, SDValue N3,
3655 SDValue Ops[] = { N1, N2, N3, N4 };
3656 return getNode(Opcode, DL, VT, Ops);
3659 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3660 SDValue N1, SDValue N2, SDValue N3,
3661 SDValue N4, SDValue N5) {
3662 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3663 return getNode(Opcode, DL, VT, Ops);
3666 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3667 /// the incoming stack arguments to be loaded from the stack.
3668 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3669 SmallVector<SDValue, 8> ArgChains;
3671 // Include the original chain at the beginning of the list. When this is
3672 // used by target LowerCall hooks, this helps legalize find the
3673 // CALLSEQ_BEGIN node.
3674 ArgChains.push_back(Chain);
3676 // Add a chain value for each stack argument.
3677 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3678 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3679 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3680 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3681 if (FI->getIndex() < 0)
3682 ArgChains.push_back(SDValue(L, 1));
3684 // Build a tokenfactor for all the chains.
3685 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3688 /// getMemsetValue - Vectorized representation of the memset value
3690 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3692 assert(Value.getOpcode() != ISD::UNDEF);
3694 unsigned NumBits = VT.getScalarType().getSizeInBits();
3695 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3696 assert(C->getAPIntValue().getBitWidth() == 8);
3697 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3699 return DAG.getConstant(Val, VT);
3700 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3703 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3705 // Use a multiplication with 0x010101... to extend the input to the
3707 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3708 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3714 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3715 /// used when a memcpy is turned into a memset when the source is a constant
3717 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3718 const TargetLowering &TLI, StringRef Str) {
3719 // Handle vector with all elements zero.
3722 return DAG.getConstant(0, VT);
3723 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3724 return DAG.getConstantFP(0.0, VT);
3725 else if (VT.isVector()) {
3726 unsigned NumElts = VT.getVectorNumElements();
3727 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3728 return DAG.getNode(ISD::BITCAST, dl, VT,
3729 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3732 llvm_unreachable("Expected type!");
3735 assert(!VT.isVector() && "Can't handle vector type here!");
3736 unsigned NumVTBits = VT.getSizeInBits();
3737 unsigned NumVTBytes = NumVTBits / 8;
3738 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3740 APInt Val(NumVTBits, 0);
3741 if (TLI.isLittleEndian()) {
3742 for (unsigned i = 0; i != NumBytes; ++i)
3743 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3745 for (unsigned i = 0; i != NumBytes; ++i)
3746 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3749 // If the "cost" of materializing the integer immediate is less than the cost
3750 // of a load, then it is cost effective to turn the load into the immediate.
3751 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3752 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3753 return DAG.getConstant(Val, VT);
3754 return SDValue(nullptr, 0);
3757 /// getMemBasePlusOffset - Returns base and offset node for the
3759 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3760 SelectionDAG &DAG) {
3761 EVT VT = Base.getValueType();
3762 return DAG.getNode(ISD::ADD, dl,
3763 VT, Base, DAG.getConstant(Offset, VT));
3766 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3768 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3769 unsigned SrcDelta = 0;
3770 GlobalAddressSDNode *G = nullptr;
3771 if (Src.getOpcode() == ISD::GlobalAddress)
3772 G = cast<GlobalAddressSDNode>(Src);
3773 else if (Src.getOpcode() == ISD::ADD &&
3774 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3775 Src.getOperand(1).getOpcode() == ISD::Constant) {
3776 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3777 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3782 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3785 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3786 /// to replace the memset / memcpy. Return true if the number of memory ops
3787 /// is below the threshold. It returns the types of the sequence of
3788 /// memory ops to perform memset / memcpy by reference.
3789 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3790 unsigned Limit, uint64_t Size,
3791 unsigned DstAlign, unsigned SrcAlign,
3797 const TargetLowering &TLI) {
3798 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3799 "Expecting memcpy / memset source to meet alignment requirement!");
3800 // If 'SrcAlign' is zero, that means the memory operation does not need to
3801 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3802 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3803 // is the specified alignment of the memory operation. If it is zero, that
3804 // means it's possible to change the alignment of the destination.
3805 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3806 // not need to be loaded.
3807 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3808 IsMemset, ZeroMemset, MemcpyStrSrc,
3809 DAG.getMachineFunction());
3811 if (VT == MVT::Other) {
3813 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3814 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3815 VT = TLI.getPointerTy();
3817 switch (DstAlign & 7) {
3818 case 0: VT = MVT::i64; break;
3819 case 4: VT = MVT::i32; break;
3820 case 2: VT = MVT::i16; break;
3821 default: VT = MVT::i8; break;
3826 while (!TLI.isTypeLegal(LVT))
3827 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3828 assert(LVT.isInteger());
3834 unsigned NumMemOps = 0;
3836 unsigned VTSize = VT.getSizeInBits() / 8;
3837 while (VTSize > Size) {
3838 // For now, only use non-vector load / store's for the left-over pieces.
3843 if (VT.isVector() || VT.isFloatingPoint()) {
3844 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3845 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3846 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3848 else if (NewVT == MVT::i64 &&
3849 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3850 TLI.isSafeMemOpType(MVT::f64)) {
3851 // i64 is usually not legal on 32-bit targets, but f64 may be.
3859 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3860 if (NewVT == MVT::i8)
3862 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3864 NewVTSize = NewVT.getSizeInBits() / 8;
3866 // If the new VT cannot cover all of the remaining bits, then consider
3867 // issuing a (or a pair of) unaligned and overlapping load / store.
3868 // FIXME: Only does this for 64-bit or more since we don't have proper
3869 // cost model for unaligned load / store.
3872 if (NumMemOps && AllowOverlap &&
3873 VTSize >= 8 && NewVTSize < Size &&
3874 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3882 if (++NumMemOps > Limit)
3885 MemOps.push_back(VT);
3892 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3893 SDValue Chain, SDValue Dst,
3894 SDValue Src, uint64_t Size,
3895 unsigned Align, bool isVol,
3897 MachinePointerInfo DstPtrInfo,
3898 MachinePointerInfo SrcPtrInfo) {
3899 // Turn a memcpy of undef to nop.
3900 if (Src.getOpcode() == ISD::UNDEF)
3903 // Expand memcpy to a series of load and store ops if the size operand falls
3904 // below a certain threshold.
3905 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3906 // rather than maybe a humongous number of loads and stores.
3907 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3908 std::vector<EVT> MemOps;
3909 bool DstAlignCanChange = false;
3910 MachineFunction &MF = DAG.getMachineFunction();
3911 MachineFrameInfo *MFI = MF.getFrameInfo();
3913 MF.getFunction()->getAttributes().
3914 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3915 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3916 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3917 DstAlignCanChange = true;
3918 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3919 if (Align > SrcAlign)
3922 bool CopyFromStr = isMemSrcFromString(Src, Str);
3923 bool isZeroStr = CopyFromStr && Str.empty();
3924 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3926 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3927 (DstAlignCanChange ? 0 : Align),
3928 (isZeroStr ? 0 : SrcAlign),
3929 false, false, CopyFromStr, true, DAG, TLI))
3932 if (DstAlignCanChange) {
3933 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3934 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3936 // Don't promote to an alignment that would require dynamic stack
3938 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3939 if (!TRI->needsStackRealignment(MF))
3940 while (NewAlign > Align &&
3941 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3944 if (NewAlign > Align) {
3945 // Give the stack frame object a larger alignment if needed.
3946 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3947 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3952 SmallVector<SDValue, 8> OutChains;
3953 unsigned NumMemOps = MemOps.size();
3954 uint64_t SrcOff = 0, DstOff = 0;
3955 for (unsigned i = 0; i != NumMemOps; ++i) {
3957 unsigned VTSize = VT.getSizeInBits() / 8;
3958 SDValue Value, Store;
3960 if (VTSize > Size) {
3961 // Issuing an unaligned load / store pair that overlaps with the previous
3962 // pair. Adjust the offset accordingly.
3963 assert(i == NumMemOps-1 && i != 0);
3964 SrcOff -= VTSize - Size;
3965 DstOff -= VTSize - Size;
3969 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3970 // It's unlikely a store of a vector immediate can be done in a single
3971 // instruction. It would require a load from a constantpool first.
3972 // We only handle zero vectors here.
3973 // FIXME: Handle other cases where store of vector immediate is done in
3974 // a single instruction.
3975 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3976 if (Value.getNode())
3977 Store = DAG.getStore(Chain, dl, Value,
3978 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3979 DstPtrInfo.getWithOffset(DstOff), isVol,
3983 if (!Store.getNode()) {
3984 // The type might not be legal for the target. This should only happen
3985 // if the type is smaller than a legal type, as on PPC, so the right
3986 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3987 // to Load/Store if NVT==VT.
3988 // FIXME does the case above also need this?
3989 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3990 assert(NVT.bitsGE(VT));
3991 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3992 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3993 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3994 MinAlign(SrcAlign, SrcOff));
3995 Store = DAG.getTruncStore(Chain, dl, Value,
3996 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3997 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4000 OutChains.push_back(Store);
4006 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4009 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4010 SDValue Chain, SDValue Dst,
4011 SDValue Src, uint64_t Size,
4012 unsigned Align, bool isVol,
4014 MachinePointerInfo DstPtrInfo,
4015 MachinePointerInfo SrcPtrInfo) {
4016 // Turn a memmove of undef to nop.
4017 if (Src.getOpcode() == ISD::UNDEF)
4020 // Expand memmove to a series of load and store ops if the size operand falls
4021 // below a certain threshold.
4022 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4023 std::vector<EVT> MemOps;
4024 bool DstAlignCanChange = false;
4025 MachineFunction &MF = DAG.getMachineFunction();
4026 MachineFrameInfo *MFI = MF.getFrameInfo();
4027 bool OptSize = MF.getFunction()->getAttributes().
4028 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4029 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4030 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4031 DstAlignCanChange = true;
4032 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4033 if (Align > SrcAlign)
4035 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4037 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4038 (DstAlignCanChange ? 0 : Align), SrcAlign,
4039 false, false, false, false, DAG, TLI))
4042 if (DstAlignCanChange) {
4043 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4044 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4045 if (NewAlign > Align) {
4046 // Give the stack frame object a larger alignment if needed.
4047 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4048 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4053 uint64_t SrcOff = 0, DstOff = 0;
4054 SmallVector<SDValue, 8> LoadValues;
4055 SmallVector<SDValue, 8> LoadChains;
4056 SmallVector<SDValue, 8> OutChains;
4057 unsigned NumMemOps = MemOps.size();
4058 for (unsigned i = 0; i < NumMemOps; i++) {
4060 unsigned VTSize = VT.getSizeInBits() / 8;
4063 Value = DAG.getLoad(VT, dl, Chain,
4064 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4065 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4066 false, false, SrcAlign);
4067 LoadValues.push_back(Value);
4068 LoadChains.push_back(Value.getValue(1));
4071 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4073 for (unsigned i = 0; i < NumMemOps; i++) {
4075 unsigned VTSize = VT.getSizeInBits() / 8;
4078 Store = DAG.getStore(Chain, dl, LoadValues[i],
4079 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4080 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4081 OutChains.push_back(Store);
4085 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4088 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4091 /// \param DAG Selection DAG where lowered code is placed.
4092 /// \param dl Link to corresponding IR location.
4093 /// \param Chain Control flow dependency.
4094 /// \param Dst Pointer to destination memory location.
4095 /// \param Src Value of byte to write into the memory.
4096 /// \param Size Number of bytes to write.
4097 /// \param Align Alignment of the destination in bytes.
4098 /// \param isVol True if destination is volatile.
4099 /// \param DstPtrInfo IR information on the memory pointer.
4100 /// \returns New head in the control flow, if lowering was successful, empty
4101 /// SDValue otherwise.
4103 /// The function tries to replace 'llvm.memset' intrinsic with several store
4104 /// operations and value calculation code. This is usually profitable for small
4106 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4107 SDValue Chain, SDValue Dst,
4108 SDValue Src, uint64_t Size,
4109 unsigned Align, bool isVol,
4110 MachinePointerInfo DstPtrInfo) {
4111 // Turn a memset of undef to nop.
4112 if (Src.getOpcode() == ISD::UNDEF)
4115 // Expand memset to a series of load/store ops if the size operand
4116 // falls below a certain threshold.
4117 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4118 std::vector<EVT> MemOps;
4119 bool DstAlignCanChange = false;
4120 MachineFunction &MF = DAG.getMachineFunction();
4121 MachineFrameInfo *MFI = MF.getFrameInfo();
4122 bool OptSize = MF.getFunction()->getAttributes().
4123 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4124 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4125 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4126 DstAlignCanChange = true;
4128 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4129 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4130 Size, (DstAlignCanChange ? 0 : Align), 0,
4131 true, IsZeroVal, false, true, DAG, TLI))
4134 if (DstAlignCanChange) {
4135 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4136 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4137 if (NewAlign > Align) {
4138 // Give the stack frame object a larger alignment if needed.
4139 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4140 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4145 SmallVector<SDValue, 8> OutChains;
4146 uint64_t DstOff = 0;
4147 unsigned NumMemOps = MemOps.size();
4149 // Find the largest store and generate the bit pattern for it.
4150 EVT LargestVT = MemOps[0];
4151 for (unsigned i = 1; i < NumMemOps; i++)
4152 if (MemOps[i].bitsGT(LargestVT))
4153 LargestVT = MemOps[i];
4154 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4156 for (unsigned i = 0; i < NumMemOps; i++) {
4158 unsigned VTSize = VT.getSizeInBits() / 8;
4159 if (VTSize > Size) {
4160 // Issuing an unaligned load / store pair that overlaps with the previous
4161 // pair. Adjust the offset accordingly.
4162 assert(i == NumMemOps-1 && i != 0);
4163 DstOff -= VTSize - Size;
4166 // If this store is smaller than the largest store see whether we can get
4167 // the smaller value for free with a truncate.
4168 SDValue Value = MemSetValue;
4169 if (VT.bitsLT(LargestVT)) {
4170 if (!LargestVT.isVector() && !VT.isVector() &&
4171 TLI.isTruncateFree(LargestVT, VT))
4172 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4174 Value = getMemsetValue(Src, VT, DAG, dl);
4176 assert(Value.getValueType() == VT && "Value with wrong type.");
4177 SDValue Store = DAG.getStore(Chain, dl, Value,
4178 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4179 DstPtrInfo.getWithOffset(DstOff),
4180 isVol, false, Align);
4181 OutChains.push_back(Store);
4182 DstOff += VT.getSizeInBits() / 8;
4186 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4189 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4190 SDValue Src, SDValue Size,
4191 unsigned Align, bool isVol, bool AlwaysInline,
4192 MachinePointerInfo DstPtrInfo,
4193 MachinePointerInfo SrcPtrInfo) {
4194 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4196 // Check to see if we should lower the memcpy to loads and stores first.
4197 // For cases within the target-specified limits, this is the best choice.
4198 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4200 // Memcpy with size zero? Just return the original chain.
4201 if (ConstantSize->isNullValue())
4204 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4205 ConstantSize->getZExtValue(),Align,
4206 isVol, false, DstPtrInfo, SrcPtrInfo);
4207 if (Result.getNode())
4211 // Then check to see if we should lower the memcpy with target-specific
4212 // code. If the target chooses to do this, this is the next best.
4214 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4215 isVol, AlwaysInline,
4216 DstPtrInfo, SrcPtrInfo);
4217 if (Result.getNode())
4220 // If we really need inline code and the target declined to provide it,
4221 // use a (potentially long) sequence of loads and stores.
4223 assert(ConstantSize && "AlwaysInline requires a constant size!");
4224 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4225 ConstantSize->getZExtValue(), Align, isVol,
4226 true, DstPtrInfo, SrcPtrInfo);
4229 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4230 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4231 // respect volatile, so they may do things like read or write memory
4232 // beyond the given memory regions. But fixing this isn't easy, and most
4233 // people don't care.
4235 const TargetLowering *TLI = TM.getTargetLowering();
4237 // Emit a library call.
4238 TargetLowering::ArgListTy Args;
4239 TargetLowering::ArgListEntry Entry;
4240 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4241 Entry.Node = Dst; Args.push_back(Entry);
4242 Entry.Node = Src; Args.push_back(Entry);
4243 Entry.Node = Size; Args.push_back(Entry);
4244 // FIXME: pass in SDLoc
4245 TargetLowering::CallLoweringInfo CLI(*this);
4246 CLI.setDebugLoc(dl).setChain(Chain)
4247 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4248 Type::getVoidTy(*getContext()),
4249 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4250 TLI->getPointerTy()), std::move(Args), 0)
4251 .setDiscardResult();
4252 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4254 return CallResult.second;
4257 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4258 SDValue Src, SDValue Size,
4259 unsigned Align, bool isVol,
4260 MachinePointerInfo DstPtrInfo,
4261 MachinePointerInfo SrcPtrInfo) {
4262 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4264 // Check to see if we should lower the memmove to loads and stores first.
4265 // For cases within the target-specified limits, this is the best choice.
4266 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4268 // Memmove with size zero? Just return the original chain.
4269 if (ConstantSize->isNullValue())
4273 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4274 ConstantSize->getZExtValue(), Align, isVol,
4275 false, DstPtrInfo, SrcPtrInfo);
4276 if (Result.getNode())
4280 // Then check to see if we should lower the memmove with target-specific
4281 // code. If the target chooses to do this, this is the next best.
4283 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4284 DstPtrInfo, SrcPtrInfo);
4285 if (Result.getNode())
4288 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4289 // not be safe. See memcpy above for more details.
4291 const TargetLowering *TLI = TM.getTargetLowering();
4293 // Emit a library call.
4294 TargetLowering::ArgListTy Args;
4295 TargetLowering::ArgListEntry Entry;
4296 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4297 Entry.Node = Dst; Args.push_back(Entry);
4298 Entry.Node = Src; Args.push_back(Entry);
4299 Entry.Node = Size; Args.push_back(Entry);
4300 // FIXME: pass in SDLoc
4301 TargetLowering::CallLoweringInfo CLI(*this);
4302 CLI.setDebugLoc(dl).setChain(Chain)
4303 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4304 Type::getVoidTy(*getContext()),
4305 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4306 TLI->getPointerTy()), std::move(Args), 0)
4307 .setDiscardResult();
4308 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4310 return CallResult.second;
4313 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4314 SDValue Src, SDValue Size,
4315 unsigned Align, bool isVol,
4316 MachinePointerInfo DstPtrInfo) {
4317 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4319 // Check to see if we should lower the memset to stores first.
4320 // For cases within the target-specified limits, this is the best choice.
4321 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4323 // Memset with size zero? Just return the original chain.
4324 if (ConstantSize->isNullValue())
4328 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4329 Align, isVol, DstPtrInfo);
4331 if (Result.getNode())
4335 // Then check to see if we should lower the memset with target-specific
4336 // code. If the target chooses to do this, this is the next best.
4338 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4340 if (Result.getNode())
4343 // Emit a library call.
4344 const TargetLowering *TLI = TM.getTargetLowering();
4345 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4346 TargetLowering::ArgListTy Args;
4347 TargetLowering::ArgListEntry Entry;
4348 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4349 Args.push_back(Entry);
4350 // Extend or truncate the argument to be an i32 value for the call.
4351 if (Src.getValueType().bitsGT(MVT::i32))
4352 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4354 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4356 Entry.Ty = Type::getInt32Ty(*getContext());
4357 Entry.isSExt = true;
4358 Args.push_back(Entry);
4360 Entry.Ty = IntPtrTy;
4361 Entry.isSExt = false;
4362 Args.push_back(Entry);
4364 // FIXME: pass in SDLoc
4365 TargetLowering::CallLoweringInfo CLI(*this);
4366 CLI.setDebugLoc(dl).setChain(Chain)
4367 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4368 Type::getVoidTy(*getContext()),
4369 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4370 TLI->getPointerTy()), std::move(Args), 0)
4371 .setDiscardResult();
4373 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4374 return CallResult.second;
4377 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4378 SDVTList VTList, ArrayRef<SDValue> Ops,
4379 MachineMemOperand *MMO,
4380 AtomicOrdering SuccessOrdering,
4381 AtomicOrdering FailureOrdering,
4382 SynchronizationScope SynchScope) {
4383 FoldingSetNodeID ID;
4384 ID.AddInteger(MemVT.getRawBits());
4385 AddNodeIDNode(ID, Opcode, VTList, Ops);
4386 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4388 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4389 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4390 return SDValue(E, 0);
4393 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4394 // SDNode doesn't have access to it. This memory will be "leaked" when
4395 // the node is deallocated, but recovered when the allocator is released.
4396 // If the number of operands is less than 5 we use AtomicSDNode's internal
4398 unsigned NumOps = Ops.size();
4399 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4402 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4403 dl.getDebugLoc(), VTList, MemVT,
4404 Ops.data(), DynOps, NumOps, MMO,
4405 SuccessOrdering, FailureOrdering,
4407 CSEMap.InsertNode(N, IP);
4409 return SDValue(N, 0);
4412 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4413 SDVTList VTList, ArrayRef<SDValue> Ops,
4414 MachineMemOperand *MMO,
4415 AtomicOrdering Ordering,
4416 SynchronizationScope SynchScope) {
4417 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4418 Ordering, SynchScope);
4421 SDValue SelectionDAG::getAtomicCmpSwap(
4422 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4423 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4424 unsigned Alignment, AtomicOrdering SuccessOrdering,
4425 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4426 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4427 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4428 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4430 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4431 Alignment = getEVTAlignment(MemVT);
4433 MachineFunction &MF = getMachineFunction();
4435 // FIXME: Volatile isn't really correct; we should keep track of atomic
4436 // orderings in the memoperand.
4437 unsigned Flags = MachineMemOperand::MOVolatile;
4438 Flags |= MachineMemOperand::MOLoad;
4439 Flags |= MachineMemOperand::MOStore;
4441 MachineMemOperand *MMO =
4442 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4444 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4445 SuccessOrdering, FailureOrdering, SynchScope);
4448 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4449 SDVTList VTs, SDValue Chain, SDValue Ptr,
4450 SDValue Cmp, SDValue Swp,
4451 MachineMemOperand *MMO,
4452 AtomicOrdering SuccessOrdering,
4453 AtomicOrdering FailureOrdering,
4454 SynchronizationScope SynchScope) {
4455 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4456 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4457 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4459 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4460 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4461 SuccessOrdering, FailureOrdering, SynchScope);
4464 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4466 SDValue Ptr, SDValue Val,
4467 const Value* PtrVal,
4469 AtomicOrdering Ordering,
4470 SynchronizationScope SynchScope) {
4471 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4472 Alignment = getEVTAlignment(MemVT);
4474 MachineFunction &MF = getMachineFunction();
4475 // An atomic store does not load. An atomic load does not store.
4476 // (An atomicrmw obviously both loads and stores.)
4477 // For now, atomics are considered to be volatile always, and they are
4479 // FIXME: Volatile isn't really correct; we should keep track of atomic
4480 // orderings in the memoperand.
4481 unsigned Flags = MachineMemOperand::MOVolatile;
4482 if (Opcode != ISD::ATOMIC_STORE)
4483 Flags |= MachineMemOperand::MOLoad;
4484 if (Opcode != ISD::ATOMIC_LOAD)
4485 Flags |= MachineMemOperand::MOStore;
4487 MachineMemOperand *MMO =
4488 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4489 MemVT.getStoreSize(), Alignment);
4491 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4492 Ordering, SynchScope);
4495 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4497 SDValue Ptr, SDValue Val,
4498 MachineMemOperand *MMO,
4499 AtomicOrdering Ordering,
4500 SynchronizationScope SynchScope) {
4501 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4502 Opcode == ISD::ATOMIC_LOAD_SUB ||
4503 Opcode == ISD::ATOMIC_LOAD_AND ||
4504 Opcode == ISD::ATOMIC_LOAD_OR ||
4505 Opcode == ISD::ATOMIC_LOAD_XOR ||
4506 Opcode == ISD::ATOMIC_LOAD_NAND ||
4507 Opcode == ISD::ATOMIC_LOAD_MIN ||
4508 Opcode == ISD::ATOMIC_LOAD_MAX ||
4509 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4510 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4511 Opcode == ISD::ATOMIC_SWAP ||
4512 Opcode == ISD::ATOMIC_STORE) &&
4513 "Invalid Atomic Op");
4515 EVT VT = Val.getValueType();
4517 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4518 getVTList(VT, MVT::Other);
4519 SDValue Ops[] = {Chain, Ptr, Val};
4520 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4523 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4524 EVT VT, SDValue Chain,
4526 MachineMemOperand *MMO,
4527 AtomicOrdering Ordering,
4528 SynchronizationScope SynchScope) {
4529 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4531 SDVTList VTs = getVTList(VT, MVT::Other);
4532 SDValue Ops[] = {Chain, Ptr};
4533 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4536 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4537 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4538 if (Ops.size() == 1)
4541 SmallVector<EVT, 4> VTs;
4542 VTs.reserve(Ops.size());
4543 for (unsigned i = 0; i < Ops.size(); ++i)
4544 VTs.push_back(Ops[i].getValueType());
4545 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4549 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4550 ArrayRef<SDValue> Ops,
4551 EVT MemVT, MachinePointerInfo PtrInfo,
4552 unsigned Align, bool Vol,
4553 bool ReadMem, bool WriteMem) {
4554 if (Align == 0) // Ensure that codegen never sees alignment 0
4555 Align = getEVTAlignment(MemVT);
4557 MachineFunction &MF = getMachineFunction();
4560 Flags |= MachineMemOperand::MOStore;
4562 Flags |= MachineMemOperand::MOLoad;
4564 Flags |= MachineMemOperand::MOVolatile;
4565 MachineMemOperand *MMO =
4566 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4568 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4572 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4573 ArrayRef<SDValue> Ops, EVT MemVT,
4574 MachineMemOperand *MMO) {
4575 assert((Opcode == ISD::INTRINSIC_VOID ||
4576 Opcode == ISD::INTRINSIC_W_CHAIN ||
4577 Opcode == ISD::PREFETCH ||
4578 Opcode == ISD::LIFETIME_START ||
4579 Opcode == ISD::LIFETIME_END ||
4580 (Opcode <= INT_MAX &&
4581 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4582 "Opcode is not a memory-accessing opcode!");
4584 // Memoize the node unless it returns a flag.
4585 MemIntrinsicSDNode *N;
4586 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4587 FoldingSetNodeID ID;
4588 AddNodeIDNode(ID, Opcode, VTList, Ops);
4589 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4591 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4592 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4593 return SDValue(E, 0);
4596 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4597 dl.getDebugLoc(), VTList, Ops,
4599 CSEMap.InsertNode(N, IP);
4601 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4602 dl.getDebugLoc(), VTList, Ops,
4606 return SDValue(N, 0);
4609 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4610 /// MachinePointerInfo record from it. This is particularly useful because the
4611 /// code generator has many cases where it doesn't bother passing in a
4612 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4613 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4614 // If this is FI+Offset, we can model it.
4615 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4616 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4618 // If this is (FI+Offset1)+Offset2, we can model it.
4619 if (Ptr.getOpcode() != ISD::ADD ||
4620 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4621 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4622 return MachinePointerInfo();
4624 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4625 return MachinePointerInfo::getFixedStack(FI, Offset+
4626 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4629 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4630 /// MachinePointerInfo record from it. This is particularly useful because the
4631 /// code generator has many cases where it doesn't bother passing in a
4632 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4633 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4634 // If the 'Offset' value isn't a constant, we can't handle this.
4635 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4636 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4637 if (OffsetOp.getOpcode() == ISD::UNDEF)
4638 return InferPointerInfo(Ptr);
4639 return MachinePointerInfo();
4644 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4645 EVT VT, SDLoc dl, SDValue Chain,
4646 SDValue Ptr, SDValue Offset,
4647 MachinePointerInfo PtrInfo, EVT MemVT,
4648 bool isVolatile, bool isNonTemporal, bool isInvariant,
4649 unsigned Alignment, const MDNode *TBAAInfo,
4650 const MDNode *Ranges) {
4651 assert(Chain.getValueType() == MVT::Other &&
4652 "Invalid chain type");
4653 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4654 Alignment = getEVTAlignment(VT);
4656 unsigned Flags = MachineMemOperand::MOLoad;
4658 Flags |= MachineMemOperand::MOVolatile;
4660 Flags |= MachineMemOperand::MONonTemporal;
4662 Flags |= MachineMemOperand::MOInvariant;
4664 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4666 if (PtrInfo.V.isNull())
4667 PtrInfo = InferPointerInfo(Ptr, Offset);
4669 MachineFunction &MF = getMachineFunction();
4670 MachineMemOperand *MMO =
4671 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4673 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4677 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4678 EVT VT, SDLoc dl, SDValue Chain,
4679 SDValue Ptr, SDValue Offset, EVT MemVT,
4680 MachineMemOperand *MMO) {
4682 ExtType = ISD::NON_EXTLOAD;
4683 } else if (ExtType == ISD::NON_EXTLOAD) {
4684 assert(VT == MemVT && "Non-extending load from different memory type!");
4687 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4688 "Should only be an extending load, not truncating!");
4689 assert(VT.isInteger() == MemVT.isInteger() &&
4690 "Cannot convert from FP to Int or Int -> FP!");
4691 assert(VT.isVector() == MemVT.isVector() &&
4692 "Cannot use trunc store to convert to or from a vector!");
4693 assert((!VT.isVector() ||
4694 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4695 "Cannot use trunc store to change the number of vector elements!");
4698 bool Indexed = AM != ISD::UNINDEXED;
4699 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4700 "Unindexed load with an offset!");
4702 SDVTList VTs = Indexed ?
4703 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4704 SDValue Ops[] = { Chain, Ptr, Offset };
4705 FoldingSetNodeID ID;
4706 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4707 ID.AddInteger(MemVT.getRawBits());
4708 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4709 MMO->isNonTemporal(),
4710 MMO->isInvariant()));
4711 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4713 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4714 cast<LoadSDNode>(E)->refineAlignment(MMO);
4715 return SDValue(E, 0);
4717 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4718 dl.getDebugLoc(), VTs, AM, ExtType,
4720 CSEMap.InsertNode(N, IP);
4722 return SDValue(N, 0);
4725 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4726 SDValue Chain, SDValue Ptr,
4727 MachinePointerInfo PtrInfo,
4728 bool isVolatile, bool isNonTemporal,
4729 bool isInvariant, unsigned Alignment,
4730 const MDNode *TBAAInfo,
4731 const MDNode *Ranges) {
4732 SDValue Undef = getUNDEF(Ptr.getValueType());
4733 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4734 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4738 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4739 SDValue Chain, SDValue Ptr,
4740 MachineMemOperand *MMO) {
4741 SDValue Undef = getUNDEF(Ptr.getValueType());
4742 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4746 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4747 SDValue Chain, SDValue Ptr,
4748 MachinePointerInfo PtrInfo, EVT MemVT,
4749 bool isVolatile, bool isNonTemporal,
4750 unsigned Alignment, const MDNode *TBAAInfo) {
4751 SDValue Undef = getUNDEF(Ptr.getValueType());
4752 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4753 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4758 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4759 SDValue Chain, SDValue Ptr, EVT MemVT,
4760 MachineMemOperand *MMO) {
4761 SDValue Undef = getUNDEF(Ptr.getValueType());
4762 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4767 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4768 SDValue Offset, ISD::MemIndexedMode AM) {
4769 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4770 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4771 "Load is already a indexed load!");
4772 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4773 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4774 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4775 false, LD->getAlignment());
4778 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4779 SDValue Ptr, MachinePointerInfo PtrInfo,
4780 bool isVolatile, bool isNonTemporal,
4781 unsigned Alignment, const MDNode *TBAAInfo) {
4782 assert(Chain.getValueType() == MVT::Other &&
4783 "Invalid chain type");
4784 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4785 Alignment = getEVTAlignment(Val.getValueType());
4787 unsigned Flags = MachineMemOperand::MOStore;
4789 Flags |= MachineMemOperand::MOVolatile;
4791 Flags |= MachineMemOperand::MONonTemporal;
4793 if (PtrInfo.V.isNull())
4794 PtrInfo = InferPointerInfo(Ptr);
4796 MachineFunction &MF = getMachineFunction();
4797 MachineMemOperand *MMO =
4798 MF.getMachineMemOperand(PtrInfo, Flags,
4799 Val.getValueType().getStoreSize(), Alignment,
4802 return getStore(Chain, dl, Val, Ptr, MMO);
4805 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4806 SDValue Ptr, MachineMemOperand *MMO) {
4807 assert(Chain.getValueType() == MVT::Other &&
4808 "Invalid chain type");
4809 EVT VT = Val.getValueType();
4810 SDVTList VTs = getVTList(MVT::Other);
4811 SDValue Undef = getUNDEF(Ptr.getValueType());
4812 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4813 FoldingSetNodeID ID;
4814 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4815 ID.AddInteger(VT.getRawBits());
4816 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4817 MMO->isNonTemporal(), MMO->isInvariant()));
4818 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4820 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4821 cast<StoreSDNode>(E)->refineAlignment(MMO);
4822 return SDValue(E, 0);
4824 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4825 dl.getDebugLoc(), VTs,
4826 ISD::UNINDEXED, false, VT, MMO);
4827 CSEMap.InsertNode(N, IP);
4829 return SDValue(N, 0);
4832 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4833 SDValue Ptr, MachinePointerInfo PtrInfo,
4834 EVT SVT,bool isVolatile, bool isNonTemporal,
4836 const MDNode *TBAAInfo) {
4837 assert(Chain.getValueType() == MVT::Other &&
4838 "Invalid chain type");
4839 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4840 Alignment = getEVTAlignment(SVT);
4842 unsigned Flags = MachineMemOperand::MOStore;
4844 Flags |= MachineMemOperand::MOVolatile;
4846 Flags |= MachineMemOperand::MONonTemporal;
4848 if (PtrInfo.V.isNull())
4849 PtrInfo = InferPointerInfo(Ptr);
4851 MachineFunction &MF = getMachineFunction();
4852 MachineMemOperand *MMO =
4853 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4856 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4859 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4860 SDValue Ptr, EVT SVT,
4861 MachineMemOperand *MMO) {
4862 EVT VT = Val.getValueType();
4864 assert(Chain.getValueType() == MVT::Other &&
4865 "Invalid chain type");
4867 return getStore(Chain, dl, Val, Ptr, MMO);
4869 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4870 "Should only be a truncating store, not extending!");
4871 assert(VT.isInteger() == SVT.isInteger() &&
4872 "Can't do FP-INT conversion!");
4873 assert(VT.isVector() == SVT.isVector() &&
4874 "Cannot use trunc store to convert to or from a vector!");
4875 assert((!VT.isVector() ||
4876 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4877 "Cannot use trunc store to change the number of vector elements!");
4879 SDVTList VTs = getVTList(MVT::Other);
4880 SDValue Undef = getUNDEF(Ptr.getValueType());
4881 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4882 FoldingSetNodeID ID;
4883 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4884 ID.AddInteger(SVT.getRawBits());
4885 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4886 MMO->isNonTemporal(), MMO->isInvariant()));
4887 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4889 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4890 cast<StoreSDNode>(E)->refineAlignment(MMO);
4891 return SDValue(E, 0);
4893 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4894 dl.getDebugLoc(), VTs,
4895 ISD::UNINDEXED, true, SVT, MMO);
4896 CSEMap.InsertNode(N, IP);
4898 return SDValue(N, 0);
4902 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4903 SDValue Offset, ISD::MemIndexedMode AM) {
4904 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4905 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4906 "Store is already a indexed store!");
4907 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4908 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4909 FoldingSetNodeID ID;
4910 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4911 ID.AddInteger(ST->getMemoryVT().getRawBits());
4912 ID.AddInteger(ST->getRawSubclassData());
4913 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4915 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4916 return SDValue(E, 0);
4918 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4919 dl.getDebugLoc(), VTs, AM,
4920 ST->isTruncatingStore(),
4922 ST->getMemOperand());
4923 CSEMap.InsertNode(N, IP);
4925 return SDValue(N, 0);
4928 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4929 SDValue Chain, SDValue Ptr,
4932 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4933 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4936 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4937 ArrayRef<SDUse> Ops) {
4938 switch (Ops.size()) {
4939 case 0: return getNode(Opcode, DL, VT);
4940 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4941 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4942 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4946 // Copy from an SDUse array into an SDValue array for use with
4947 // the regular getNode logic.
4948 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4949 return getNode(Opcode, DL, VT, NewOps);
4952 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4953 ArrayRef<SDValue> Ops) {
4954 unsigned NumOps = Ops.size();
4956 case 0: return getNode(Opcode, DL, VT);
4957 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4958 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4959 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4965 case ISD::SELECT_CC: {
4966 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4967 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4968 "LHS and RHS of condition must have same type!");
4969 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4970 "True and False arms of SelectCC must have same type!");
4971 assert(Ops[2].getValueType() == VT &&
4972 "select_cc node must be of same type as true and false value!");
4976 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4977 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4978 "LHS/RHS of comparison should match types!");
4985 SDVTList VTs = getVTList(VT);
4987 if (VT != MVT::Glue) {
4988 FoldingSetNodeID ID;
4989 AddNodeIDNode(ID, Opcode, VTs, Ops);
4992 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4993 return SDValue(E, 0);
4995 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4997 CSEMap.InsertNode(N, IP);
4999 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5004 return SDValue(N, 0);
5007 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5008 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5009 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5012 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5013 ArrayRef<SDValue> Ops) {
5014 if (VTList.NumVTs == 1)
5015 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5019 // FIXME: figure out how to safely handle things like
5020 // int foo(int x) { return 1 << (x & 255); }
5021 // int bar() { return foo(256); }
5022 case ISD::SRA_PARTS:
5023 case ISD::SRL_PARTS:
5024 case ISD::SHL_PARTS:
5025 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5026 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5027 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5028 else if (N3.getOpcode() == ISD::AND)
5029 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5030 // If the and is only masking out bits that cannot effect the shift,
5031 // eliminate the and.
5032 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5033 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5034 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5040 // Memoize the node unless it returns a flag.
5042 unsigned NumOps = Ops.size();
5043 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5044 FoldingSetNodeID ID;
5045 AddNodeIDNode(ID, Opcode, VTList, Ops);
5047 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5048 return SDValue(E, 0);
5051 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5052 DL.getDebugLoc(), VTList, Ops[0]);
5053 } else if (NumOps == 2) {
5054 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5055 DL.getDebugLoc(), VTList, Ops[0],
5057 } else if (NumOps == 3) {
5058 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5059 DL.getDebugLoc(), VTList, Ops[0],
5062 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5065 CSEMap.InsertNode(N, IP);
5068 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5069 DL.getDebugLoc(), VTList, Ops[0]);
5070 } else if (NumOps == 2) {
5071 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5072 DL.getDebugLoc(), VTList, Ops[0],
5074 } else if (NumOps == 3) {
5075 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5076 DL.getDebugLoc(), VTList, Ops[0],
5079 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5084 return SDValue(N, 0);
5087 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5088 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5091 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5093 SDValue Ops[] = { N1 };
5094 return getNode(Opcode, DL, VTList, Ops);
5097 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5098 SDValue N1, SDValue N2) {
5099 SDValue Ops[] = { N1, N2 };
5100 return getNode(Opcode, DL, VTList, Ops);
5103 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5104 SDValue N1, SDValue N2, SDValue N3) {
5105 SDValue Ops[] = { N1, N2, N3 };
5106 return getNode(Opcode, DL, VTList, Ops);
5109 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5110 SDValue N1, SDValue N2, SDValue N3,
5112 SDValue Ops[] = { N1, N2, N3, N4 };
5113 return getNode(Opcode, DL, VTList, Ops);
5116 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5117 SDValue N1, SDValue N2, SDValue N3,
5118 SDValue N4, SDValue N5) {
5119 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5120 return getNode(Opcode, DL, VTList, Ops);
5123 SDVTList SelectionDAG::getVTList(EVT VT) {
5124 return makeVTList(SDNode::getValueTypeList(VT), 1);
5127 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5128 FoldingSetNodeID ID;
5130 ID.AddInteger(VT1.getRawBits());
5131 ID.AddInteger(VT2.getRawBits());
5134 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5136 EVT *Array = Allocator.Allocate<EVT>(2);
5139 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5140 VTListMap.InsertNode(Result, IP);
5142 return Result->getSDVTList();
5145 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5146 FoldingSetNodeID ID;
5148 ID.AddInteger(VT1.getRawBits());
5149 ID.AddInteger(VT2.getRawBits());
5150 ID.AddInteger(VT3.getRawBits());
5153 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5155 EVT *Array = Allocator.Allocate<EVT>(3);
5159 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5160 VTListMap.InsertNode(Result, IP);
5162 return Result->getSDVTList();
5165 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5166 FoldingSetNodeID ID;
5168 ID.AddInteger(VT1.getRawBits());
5169 ID.AddInteger(VT2.getRawBits());
5170 ID.AddInteger(VT3.getRawBits());
5171 ID.AddInteger(VT4.getRawBits());
5174 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5176 EVT *Array = Allocator.Allocate<EVT>(4);
5181 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5182 VTListMap.InsertNode(Result, IP);
5184 return Result->getSDVTList();
5187 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5188 unsigned NumVTs = VTs.size();
5189 FoldingSetNodeID ID;
5190 ID.AddInteger(NumVTs);
5191 for (unsigned index = 0; index < NumVTs; index++) {
5192 ID.AddInteger(VTs[index].getRawBits());
5196 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5198 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5199 std::copy(VTs.begin(), VTs.end(), Array);
5200 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5201 VTListMap.InsertNode(Result, IP);
5203 return Result->getSDVTList();
5207 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5208 /// specified operands. If the resultant node already exists in the DAG,
5209 /// this does not modify the specified node, instead it returns the node that
5210 /// already exists. If the resultant node does not exist in the DAG, the
5211 /// input node is returned. As a degenerate case, if you specify the same
5212 /// input operands as the node already has, the input node is returned.
5213 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5214 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5216 // Check to see if there is no change.
5217 if (Op == N->getOperand(0)) return N;
5219 // See if the modified node already exists.
5220 void *InsertPos = nullptr;
5221 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5224 // Nope it doesn't. Remove the node from its current place in the maps.
5226 if (!RemoveNodeFromCSEMaps(N))
5227 InsertPos = nullptr;
5229 // Now we update the operands.
5230 N->OperandList[0].set(Op);
5232 // If this gets put into a CSE map, add it.
5233 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5237 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5238 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5240 // Check to see if there is no change.
5241 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5242 return N; // No operands changed, just return the input node.
5244 // See if the modified node already exists.
5245 void *InsertPos = nullptr;
5246 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5249 // Nope it doesn't. Remove the node from its current place in the maps.
5251 if (!RemoveNodeFromCSEMaps(N))
5252 InsertPos = nullptr;
5254 // Now we update the operands.
5255 if (N->OperandList[0] != Op1)
5256 N->OperandList[0].set(Op1);
5257 if (N->OperandList[1] != Op2)
5258 N->OperandList[1].set(Op2);
5260 // If this gets put into a CSE map, add it.
5261 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5265 SDNode *SelectionDAG::
5266 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5267 SDValue Ops[] = { Op1, Op2, Op3 };
5268 return UpdateNodeOperands(N, Ops);
5271 SDNode *SelectionDAG::
5272 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5273 SDValue Op3, SDValue Op4) {
5274 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5275 return UpdateNodeOperands(N, Ops);
5278 SDNode *SelectionDAG::
5279 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5280 SDValue Op3, SDValue Op4, SDValue Op5) {
5281 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5282 return UpdateNodeOperands(N, Ops);
5285 SDNode *SelectionDAG::
5286 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5287 unsigned NumOps = Ops.size();
5288 assert(N->getNumOperands() == NumOps &&
5289 "Update with wrong number of operands");
5291 // Check to see if there is no change.
5292 bool AnyChange = false;
5293 for (unsigned i = 0; i != NumOps; ++i) {
5294 if (Ops[i] != N->getOperand(i)) {
5300 // No operands changed, just return the input node.
5301 if (!AnyChange) return N;
5303 // See if the modified node already exists.
5304 void *InsertPos = nullptr;
5305 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5308 // Nope it doesn't. Remove the node from its current place in the maps.
5310 if (!RemoveNodeFromCSEMaps(N))
5311 InsertPos = nullptr;
5313 // Now we update the operands.
5314 for (unsigned i = 0; i != NumOps; ++i)
5315 if (N->OperandList[i] != Ops[i])
5316 N->OperandList[i].set(Ops[i]);
5318 // If this gets put into a CSE map, add it.
5319 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5323 /// DropOperands - Release the operands and set this node to have
5325 void SDNode::DropOperands() {
5326 // Unlike the code in MorphNodeTo that does this, we don't need to
5327 // watch for dead nodes here.
5328 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5334 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5337 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5339 SDVTList VTs = getVTList(VT);
5340 return SelectNodeTo(N, MachineOpc, VTs, None);
5343 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5344 EVT VT, SDValue Op1) {
5345 SDVTList VTs = getVTList(VT);
5346 SDValue Ops[] = { Op1 };
5347 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5350 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5351 EVT VT, SDValue Op1,
5353 SDVTList VTs = getVTList(VT);
5354 SDValue Ops[] = { Op1, Op2 };
5355 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5358 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5359 EVT VT, SDValue Op1,
5360 SDValue Op2, SDValue Op3) {
5361 SDVTList VTs = getVTList(VT);
5362 SDValue Ops[] = { Op1, Op2, Op3 };
5363 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5366 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5367 EVT VT, ArrayRef<SDValue> Ops) {
5368 SDVTList VTs = getVTList(VT);
5369 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5372 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5373 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5374 SDVTList VTs = getVTList(VT1, VT2);
5375 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5378 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5380 SDVTList VTs = getVTList(VT1, VT2);
5381 return SelectNodeTo(N, MachineOpc, VTs, None);
5384 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5385 EVT VT1, EVT VT2, EVT VT3,
5386 ArrayRef<SDValue> Ops) {
5387 SDVTList VTs = getVTList(VT1, VT2, VT3);
5388 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5391 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5392 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5393 ArrayRef<SDValue> Ops) {
5394 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5395 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5398 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5401 SDVTList VTs = getVTList(VT1, VT2);
5402 SDValue Ops[] = { Op1 };
5403 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5406 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5408 SDValue Op1, SDValue Op2) {
5409 SDVTList VTs = getVTList(VT1, VT2);
5410 SDValue Ops[] = { Op1, Op2 };
5411 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5414 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5416 SDValue Op1, SDValue Op2,
5418 SDVTList VTs = getVTList(VT1, VT2);
5419 SDValue Ops[] = { Op1, Op2, Op3 };
5420 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5423 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5424 EVT VT1, EVT VT2, EVT VT3,
5425 SDValue Op1, SDValue Op2,
5427 SDVTList VTs = getVTList(VT1, VT2, VT3);
5428 SDValue Ops[] = { Op1, Op2, Op3 };
5429 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5432 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5433 SDVTList VTs,ArrayRef<SDValue> Ops) {
5434 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5435 // Reset the NodeID to -1.
5440 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5441 /// the line number information on the merged node since it is not possible to
5442 /// preserve the information that operation is associated with multiple lines.
5443 /// This will make the debugger working better at -O0, were there is a higher
5444 /// probability having other instructions associated with that line.
5446 /// For IROrder, we keep the smaller of the two
5447 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5448 DebugLoc NLoc = N->getDebugLoc();
5449 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5450 (OLoc.getDebugLoc() != NLoc)) {
5451 N->setDebugLoc(DebugLoc());
5453 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5454 N->setIROrder(Order);
5458 /// MorphNodeTo - This *mutates* the specified node to have the specified
5459 /// return type, opcode, and operands.
5461 /// Note that MorphNodeTo returns the resultant node. If there is already a
5462 /// node of the specified opcode and operands, it returns that node instead of
5463 /// the current one. Note that the SDLoc need not be the same.
5465 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5466 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5467 /// node, and because it doesn't require CSE recalculation for any of
5468 /// the node's users.
5470 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5471 SDVTList VTs, ArrayRef<SDValue> Ops) {
5472 unsigned NumOps = Ops.size();
5473 // If an identical node already exists, use it.
5475 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5476 FoldingSetNodeID ID;
5477 AddNodeIDNode(ID, Opc, VTs, Ops);
5478 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5479 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5482 if (!RemoveNodeFromCSEMaps(N))
5485 // Start the morphing.
5487 N->ValueList = VTs.VTs;
5488 N->NumValues = VTs.NumVTs;
5490 // Clear the operands list, updating used nodes to remove this from their
5491 // use list. Keep track of any operands that become dead as a result.
5492 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5493 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5495 SDNode *Used = Use.getNode();
5497 if (Used->use_empty())
5498 DeadNodeSet.insert(Used);
5501 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5502 // Initialize the memory references information.
5503 MN->setMemRefs(nullptr, nullptr);
5504 // If NumOps is larger than the # of operands we can have in a
5505 // MachineSDNode, reallocate the operand list.
5506 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5507 if (MN->OperandsNeedDelete)
5508 delete[] MN->OperandList;
5509 if (NumOps > array_lengthof(MN->LocalOperands))
5510 // We're creating a final node that will live unmorphed for the
5511 // remainder of the current SelectionDAG iteration, so we can allocate
5512 // the operands directly out of a pool with no recycling metadata.
5513 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5514 Ops.data(), NumOps);
5516 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5517 MN->OperandsNeedDelete = false;
5519 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5521 // If NumOps is larger than the # of operands we currently have, reallocate
5522 // the operand list.
5523 if (NumOps > N->NumOperands) {
5524 if (N->OperandsNeedDelete)
5525 delete[] N->OperandList;
5526 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5527 N->OperandsNeedDelete = true;
5529 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5532 // Delete any nodes that are still dead after adding the uses for the
5534 if (!DeadNodeSet.empty()) {
5535 SmallVector<SDNode *, 16> DeadNodes;
5536 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5537 E = DeadNodeSet.end(); I != E; ++I)
5538 if ((*I)->use_empty())
5539 DeadNodes.push_back(*I);
5540 RemoveDeadNodes(DeadNodes);
5544 CSEMap.InsertNode(N, IP); // Memoize the new node.
5549 /// getMachineNode - These are used for target selectors to create a new node
5550 /// with specified return type(s), MachineInstr opcode, and operands.
5552 /// Note that getMachineNode returns the resultant node. If there is already a
5553 /// node of the specified opcode and operands, it returns that node instead of
5554 /// the current one.
5556 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5557 SDVTList VTs = getVTList(VT);
5558 return getMachineNode(Opcode, dl, VTs, None);
5562 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5563 SDVTList VTs = getVTList(VT);
5564 SDValue Ops[] = { Op1 };
5565 return getMachineNode(Opcode, dl, VTs, Ops);
5569 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5570 SDValue Op1, SDValue Op2) {
5571 SDVTList VTs = getVTList(VT);
5572 SDValue Ops[] = { Op1, Op2 };
5573 return getMachineNode(Opcode, dl, VTs, Ops);
5577 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5578 SDValue Op1, SDValue Op2, SDValue Op3) {
5579 SDVTList VTs = getVTList(VT);
5580 SDValue Ops[] = { Op1, Op2, Op3 };
5581 return getMachineNode(Opcode, dl, VTs, Ops);
5585 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5586 ArrayRef<SDValue> Ops) {
5587 SDVTList VTs = getVTList(VT);
5588 return getMachineNode(Opcode, dl, VTs, Ops);
5592 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5593 SDVTList VTs = getVTList(VT1, VT2);
5594 return getMachineNode(Opcode, dl, VTs, None);
5598 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5599 EVT VT1, EVT VT2, SDValue Op1) {
5600 SDVTList VTs = getVTList(VT1, VT2);
5601 SDValue Ops[] = { Op1 };
5602 return getMachineNode(Opcode, dl, VTs, Ops);
5606 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5607 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5608 SDVTList VTs = getVTList(VT1, VT2);
5609 SDValue Ops[] = { Op1, Op2 };
5610 return getMachineNode(Opcode, dl, VTs, Ops);
5614 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5615 EVT VT1, EVT VT2, SDValue Op1,
5616 SDValue Op2, SDValue Op3) {
5617 SDVTList VTs = getVTList(VT1, VT2);
5618 SDValue Ops[] = { Op1, Op2, Op3 };
5619 return getMachineNode(Opcode, dl, VTs, Ops);
5623 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5625 ArrayRef<SDValue> Ops) {
5626 SDVTList VTs = getVTList(VT1, VT2);
5627 return getMachineNode(Opcode, dl, VTs, Ops);
5631 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5632 EVT VT1, EVT VT2, EVT VT3,
5633 SDValue Op1, SDValue Op2) {
5634 SDVTList VTs = getVTList(VT1, VT2, VT3);
5635 SDValue Ops[] = { Op1, Op2 };
5636 return getMachineNode(Opcode, dl, VTs, Ops);
5640 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5641 EVT VT1, EVT VT2, EVT VT3,
5642 SDValue Op1, SDValue Op2, SDValue Op3) {
5643 SDVTList VTs = getVTList(VT1, VT2, VT3);
5644 SDValue Ops[] = { Op1, Op2, Op3 };
5645 return getMachineNode(Opcode, dl, VTs, Ops);
5649 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5650 EVT VT1, EVT VT2, EVT VT3,
5651 ArrayRef<SDValue> Ops) {
5652 SDVTList VTs = getVTList(VT1, VT2, VT3);
5653 return getMachineNode(Opcode, dl, VTs, Ops);
5657 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5658 EVT VT2, EVT VT3, EVT VT4,
5659 ArrayRef<SDValue> Ops) {
5660 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5661 return getMachineNode(Opcode, dl, VTs, Ops);
5665 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5666 ArrayRef<EVT> ResultTys,
5667 ArrayRef<SDValue> Ops) {
5668 SDVTList VTs = getVTList(ResultTys);
5669 return getMachineNode(Opcode, dl, VTs, Ops);
5673 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5674 ArrayRef<SDValue> OpsArray) {
5675 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5678 const SDValue *Ops = OpsArray.data();
5679 unsigned NumOps = OpsArray.size();
5682 FoldingSetNodeID ID;
5683 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5685 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5686 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5690 // Allocate a new MachineSDNode.
5691 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5692 DL.getDebugLoc(), VTs);
5694 // Initialize the operands list.
5695 if (NumOps > array_lengthof(N->LocalOperands))
5696 // We're creating a final node that will live unmorphed for the
5697 // remainder of the current SelectionDAG iteration, so we can allocate
5698 // the operands directly out of a pool with no recycling metadata.
5699 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5702 N->InitOperands(N->LocalOperands, Ops, NumOps);
5703 N->OperandsNeedDelete = false;
5706 CSEMap.InsertNode(N, IP);
5712 /// getTargetExtractSubreg - A convenience function for creating
5713 /// TargetOpcode::EXTRACT_SUBREG nodes.
5715 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5717 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5718 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5719 VT, Operand, SRIdxVal);
5720 return SDValue(Subreg, 0);
5723 /// getTargetInsertSubreg - A convenience function for creating
5724 /// TargetOpcode::INSERT_SUBREG nodes.
5726 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5727 SDValue Operand, SDValue Subreg) {
5728 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5729 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5730 VT, Operand, Subreg, SRIdxVal);
5731 return SDValue(Result, 0);
5734 /// getNodeIfExists - Get the specified node if it's already available, or
5735 /// else return NULL.
5736 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5737 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5739 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5740 FoldingSetNodeID ID;
5741 AddNodeIDNode(ID, Opcode, VTList, Ops);
5742 if (isBinOpWithFlags(Opcode))
5743 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5745 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5751 /// getDbgValue - Creates a SDDbgValue node.
5755 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5756 bool IsIndirect, uint64_t Off,
5757 DebugLoc DL, unsigned O) {
5758 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5763 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5765 DebugLoc DL, unsigned O) {
5766 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5771 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5772 DebugLoc DL, unsigned O) {
5773 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5778 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5779 /// pointed to by a use iterator is deleted, increment the use iterator
5780 /// so that it doesn't dangle.
5782 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5783 SDNode::use_iterator &UI;
5784 SDNode::use_iterator &UE;
5786 void NodeDeleted(SDNode *N, SDNode *E) override {
5787 // Increment the iterator as needed.
5788 while (UI != UE && N == *UI)
5793 RAUWUpdateListener(SelectionDAG &d,
5794 SDNode::use_iterator &ui,
5795 SDNode::use_iterator &ue)
5796 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5801 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5802 /// This can cause recursive merging of nodes in the DAG.
5804 /// This version assumes From has a single result value.
5806 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5807 SDNode *From = FromN.getNode();
5808 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5809 "Cannot replace with this method!");
5810 assert(From != To.getNode() && "Cannot replace uses of with self");
5812 // Iterate over all the existing uses of From. New uses will be added
5813 // to the beginning of the use list, which we avoid visiting.
5814 // This specifically avoids visiting uses of From that arise while the
5815 // replacement is happening, because any such uses would be the result
5816 // of CSE: If an existing node looks like From after one of its operands
5817 // is replaced by To, we don't want to replace of all its users with To
5818 // too. See PR3018 for more info.
5819 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5820 RAUWUpdateListener Listener(*this, UI, UE);
5824 // This node is about to morph, remove its old self from the CSE maps.
5825 RemoveNodeFromCSEMaps(User);
5827 // A user can appear in a use list multiple times, and when this
5828 // happens the uses are usually next to each other in the list.
5829 // To help reduce the number of CSE recomputations, process all
5830 // the uses of this user that we can find this way.
5832 SDUse &Use = UI.getUse();
5835 } while (UI != UE && *UI == User);
5837 // Now that we have modified User, add it back to the CSE maps. If it
5838 // already exists there, recursively merge the results together.
5839 AddModifiedNodeToCSEMaps(User);
5842 // If we just RAUW'd the root, take note.
5843 if (FromN == getRoot())
5847 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5848 /// This can cause recursive merging of nodes in the DAG.
5850 /// This version assumes that for each value of From, there is a
5851 /// corresponding value in To in the same position with the same type.
5853 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5855 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5856 assert((!From->hasAnyUseOfValue(i) ||
5857 From->getValueType(i) == To->getValueType(i)) &&
5858 "Cannot use this version of ReplaceAllUsesWith!");
5861 // Handle the trivial case.
5865 // Iterate over just the existing users of From. See the comments in
5866 // the ReplaceAllUsesWith above.
5867 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5868 RAUWUpdateListener Listener(*this, UI, UE);
5872 // This node is about to morph, remove its old self from the CSE maps.
5873 RemoveNodeFromCSEMaps(User);
5875 // A user can appear in a use list multiple times, and when this
5876 // happens the uses are usually next to each other in the list.
5877 // To help reduce the number of CSE recomputations, process all
5878 // the uses of this user that we can find this way.
5880 SDUse &Use = UI.getUse();
5883 } while (UI != UE && *UI == User);
5885 // Now that we have modified User, add it back to the CSE maps. If it
5886 // already exists there, recursively merge the results together.
5887 AddModifiedNodeToCSEMaps(User);
5890 // If we just RAUW'd the root, take note.
5891 if (From == getRoot().getNode())
5892 setRoot(SDValue(To, getRoot().getResNo()));
5895 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5896 /// This can cause recursive merging of nodes in the DAG.
5898 /// This version can replace From with any result values. To must match the
5899 /// number and types of values returned by From.
5900 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5901 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5902 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5904 // Iterate over just the existing users of From. See the comments in
5905 // the ReplaceAllUsesWith above.
5906 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5907 RAUWUpdateListener Listener(*this, UI, UE);
5911 // This node is about to morph, remove its old self from the CSE maps.
5912 RemoveNodeFromCSEMaps(User);
5914 // A user can appear in a use list multiple times, and when this
5915 // happens the uses are usually next to each other in the list.
5916 // To help reduce the number of CSE recomputations, process all
5917 // the uses of this user that we can find this way.
5919 SDUse &Use = UI.getUse();
5920 const SDValue &ToOp = To[Use.getResNo()];
5923 } while (UI != UE && *UI == User);
5925 // Now that we have modified User, add it back to the CSE maps. If it
5926 // already exists there, recursively merge the results together.
5927 AddModifiedNodeToCSEMaps(User);
5930 // If we just RAUW'd the root, take note.
5931 if (From == getRoot().getNode())
5932 setRoot(SDValue(To[getRoot().getResNo()]));
5935 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5936 /// uses of other values produced by From.getNode() alone. The Deleted
5937 /// vector is handled the same way as for ReplaceAllUsesWith.
5938 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5939 // Handle the really simple, really trivial case efficiently.
5940 if (From == To) return;
5942 // Handle the simple, trivial, case efficiently.
5943 if (From.getNode()->getNumValues() == 1) {
5944 ReplaceAllUsesWith(From, To);
5948 // Iterate over just the existing users of From. See the comments in
5949 // the ReplaceAllUsesWith above.
5950 SDNode::use_iterator UI = From.getNode()->use_begin(),
5951 UE = From.getNode()->use_end();
5952 RAUWUpdateListener Listener(*this, UI, UE);
5955 bool UserRemovedFromCSEMaps = false;
5957 // A user can appear in a use list multiple times, and when this
5958 // happens the uses are usually next to each other in the list.
5959 // To help reduce the number of CSE recomputations, process all
5960 // the uses of this user that we can find this way.
5962 SDUse &Use = UI.getUse();
5964 // Skip uses of different values from the same node.
5965 if (Use.getResNo() != From.getResNo()) {
5970 // If this node hasn't been modified yet, it's still in the CSE maps,
5971 // so remove its old self from the CSE maps.
5972 if (!UserRemovedFromCSEMaps) {
5973 RemoveNodeFromCSEMaps(User);
5974 UserRemovedFromCSEMaps = true;
5979 } while (UI != UE && *UI == User);
5981 // We are iterating over all uses of the From node, so if a use
5982 // doesn't use the specific value, no changes are made.
5983 if (!UserRemovedFromCSEMaps)
5986 // Now that we have modified User, add it back to the CSE maps. If it
5987 // already exists there, recursively merge the results together.
5988 AddModifiedNodeToCSEMaps(User);
5991 // If we just RAUW'd the root, take note.
5992 if (From == getRoot())
5997 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5998 /// to record information about a use.
6005 /// operator< - Sort Memos by User.
6006 bool operator<(const UseMemo &L, const UseMemo &R) {
6007 return (intptr_t)L.User < (intptr_t)R.User;
6011 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6012 /// uses of other values produced by From.getNode() alone. The same value
6013 /// may appear in both the From and To list. The Deleted vector is
6014 /// handled the same way as for ReplaceAllUsesWith.
6015 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6018 // Handle the simple, trivial case efficiently.
6020 return ReplaceAllUsesOfValueWith(*From, *To);
6022 // Read up all the uses and make records of them. This helps
6023 // processing new uses that are introduced during the
6024 // replacement process.
6025 SmallVector<UseMemo, 4> Uses;
6026 for (unsigned i = 0; i != Num; ++i) {
6027 unsigned FromResNo = From[i].getResNo();
6028 SDNode *FromNode = From[i].getNode();
6029 for (SDNode::use_iterator UI = FromNode->use_begin(),
6030 E = FromNode->use_end(); UI != E; ++UI) {
6031 SDUse &Use = UI.getUse();
6032 if (Use.getResNo() == FromResNo) {
6033 UseMemo Memo = { *UI, i, &Use };
6034 Uses.push_back(Memo);
6039 // Sort the uses, so that all the uses from a given User are together.
6040 std::sort(Uses.begin(), Uses.end());
6042 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6043 UseIndex != UseIndexEnd; ) {
6044 // We know that this user uses some value of From. If it is the right
6045 // value, update it.
6046 SDNode *User = Uses[UseIndex].User;
6048 // This node is about to morph, remove its old self from the CSE maps.
6049 RemoveNodeFromCSEMaps(User);
6051 // The Uses array is sorted, so all the uses for a given User
6052 // are next to each other in the list.
6053 // To help reduce the number of CSE recomputations, process all
6054 // the uses of this user that we can find this way.
6056 unsigned i = Uses[UseIndex].Index;
6057 SDUse &Use = *Uses[UseIndex].Use;
6061 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6063 // Now that we have modified User, add it back to the CSE maps. If it
6064 // already exists there, recursively merge the results together.
6065 AddModifiedNodeToCSEMaps(User);
6069 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6070 /// based on their topological order. It returns the maximum id and a vector
6071 /// of the SDNodes* in assigned order by reference.
6072 unsigned SelectionDAG::AssignTopologicalOrder() {
6074 unsigned DAGSize = 0;
6076 // SortedPos tracks the progress of the algorithm. Nodes before it are
6077 // sorted, nodes after it are unsorted. When the algorithm completes
6078 // it is at the end of the list.
6079 allnodes_iterator SortedPos = allnodes_begin();
6081 // Visit all the nodes. Move nodes with no operands to the front of
6082 // the list immediately. Annotate nodes that do have operands with their
6083 // operand count. Before we do this, the Node Id fields of the nodes
6084 // may contain arbitrary values. After, the Node Id fields for nodes
6085 // before SortedPos will contain the topological sort index, and the
6086 // Node Id fields for nodes At SortedPos and after will contain the
6087 // count of outstanding operands.
6088 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6090 checkForCycles(N, this);
6091 unsigned Degree = N->getNumOperands();
6093 // A node with no uses, add it to the result array immediately.
6094 N->setNodeId(DAGSize++);
6095 allnodes_iterator Q = N;
6097 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6098 assert(SortedPos != AllNodes.end() && "Overran node list");
6101 // Temporarily use the Node Id as scratch space for the degree count.
6102 N->setNodeId(Degree);
6106 // Visit all the nodes. As we iterate, move nodes into sorted order,
6107 // such that by the time the end is reached all nodes will be sorted.
6108 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6110 checkForCycles(N, this);
6111 // N is in sorted position, so all its uses have one less operand
6112 // that needs to be sorted.
6113 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6116 unsigned Degree = P->getNodeId();
6117 assert(Degree != 0 && "Invalid node degree");
6120 // All of P's operands are sorted, so P may sorted now.
6121 P->setNodeId(DAGSize++);
6123 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6124 assert(SortedPos != AllNodes.end() && "Overran node list");
6127 // Update P's outstanding operand count.
6128 P->setNodeId(Degree);
6131 if (I == SortedPos) {
6134 dbgs() << "Overran sorted position:\n";
6135 S->dumprFull(this); dbgs() << "\n";
6136 dbgs() << "Checking if this is due to cycles\n";
6137 checkForCycles(this, true);
6139 llvm_unreachable(nullptr);
6143 assert(SortedPos == AllNodes.end() &&
6144 "Topological sort incomplete!");
6145 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6146 "First node in topological sort is not the entry token!");
6147 assert(AllNodes.front().getNodeId() == 0 &&
6148 "First node in topological sort has non-zero id!");
6149 assert(AllNodes.front().getNumOperands() == 0 &&
6150 "First node in topological sort has operands!");
6151 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6152 "Last node in topologic sort has unexpected id!");
6153 assert(AllNodes.back().use_empty() &&
6154 "Last node in topologic sort has users!");
6155 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6159 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6160 /// value is produced by SD.
6161 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6162 DbgInfo->add(DB, SD, isParameter);
6164 SD->setHasDebugValue(true);
6167 /// TransferDbgValues - Transfer SDDbgValues.
6168 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6169 if (From == To || !From.getNode()->getHasDebugValue())
6171 SDNode *FromNode = From.getNode();
6172 SDNode *ToNode = To.getNode();
6173 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6174 SmallVector<SDDbgValue *, 2> ClonedDVs;
6175 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6177 SDDbgValue *Dbg = *I;
6178 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6179 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6181 Dbg->getOffset(), Dbg->getDebugLoc(),
6183 ClonedDVs.push_back(Clone);
6186 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6187 E = ClonedDVs.end(); I != E; ++I)
6188 AddDbgValue(*I, ToNode, false);
6191 //===----------------------------------------------------------------------===//
6193 //===----------------------------------------------------------------------===//
6195 HandleSDNode::~HandleSDNode() {
6199 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6200 DebugLoc DL, const GlobalValue *GA,
6201 EVT VT, int64_t o, unsigned char TF)
6202 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6206 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6207 SDValue X, unsigned SrcAS,
6209 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6210 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6212 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6213 EVT memvt, MachineMemOperand *mmo)
6214 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6215 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6216 MMO->isNonTemporal(), MMO->isInvariant());
6217 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6218 assert(isNonTemporal() == MMO->isNonTemporal() &&
6219 "Non-temporal encoding error!");
6220 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6223 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6224 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6225 : SDNode(Opc, Order, dl, VTs, Ops),
6226 MemoryVT(memvt), MMO(mmo) {
6227 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6228 MMO->isNonTemporal(), MMO->isInvariant());
6229 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6230 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6233 /// Profile - Gather unique data for the node.
6235 void SDNode::Profile(FoldingSetNodeID &ID) const {
6236 AddNodeIDNode(ID, this);
6241 std::vector<EVT> VTs;
6244 VTs.reserve(MVT::LAST_VALUETYPE);
6245 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6246 VTs.push_back(MVT((MVT::SimpleValueType)i));
6251 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6252 static ManagedStatic<EVTArray> SimpleVTArray;
6253 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6255 /// getValueTypeList - Return a pointer to the specified value type.
6257 const EVT *SDNode::getValueTypeList(EVT VT) {
6258 if (VT.isExtended()) {
6259 sys::SmartScopedLock<true> Lock(*VTMutex);
6260 return &(*EVTs->insert(VT).first);
6262 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6263 "Value type out of range!");
6264 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6268 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6269 /// indicated value. This method ignores uses of other values defined by this
6271 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6272 assert(Value < getNumValues() && "Bad value!");
6274 // TODO: Only iterate over uses of a given value of the node
6275 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6276 if (UI.getUse().getResNo() == Value) {
6283 // Found exactly the right number of uses?
6288 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6289 /// value. This method ignores uses of other values defined by this operation.
6290 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6291 assert(Value < getNumValues() && "Bad value!");
6293 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6294 if (UI.getUse().getResNo() == Value)
6301 /// isOnlyUserOf - Return true if this node is the only use of N.
6303 bool SDNode::isOnlyUserOf(SDNode *N) const {
6305 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6316 /// isOperand - Return true if this node is an operand of N.
6318 bool SDValue::isOperandOf(SDNode *N) const {
6319 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6320 if (*this == N->getOperand(i))
6325 bool SDNode::isOperandOf(SDNode *N) const {
6326 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6327 if (this == N->OperandList[i].getNode())
6332 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6333 /// be a chain) reaches the specified operand without crossing any
6334 /// side-effecting instructions on any chain path. In practice, this looks
6335 /// through token factors and non-volatile loads. In order to remain efficient,
6336 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6337 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6338 unsigned Depth) const {
6339 if (*this == Dest) return true;
6341 // Don't search too deeply, we just want to be able to see through
6342 // TokenFactor's etc.
6343 if (Depth == 0) return false;
6345 // If this is a token factor, all inputs to the TF happen in parallel. If any
6346 // of the operands of the TF does not reach dest, then we cannot do the xform.
6347 if (getOpcode() == ISD::TokenFactor) {
6348 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6349 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6354 // Loads don't have side effects, look through them.
6355 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6356 if (!Ld->isVolatile())
6357 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6362 /// hasPredecessor - Return true if N is a predecessor of this node.
6363 /// N is either an operand of this node, or can be reached by recursively
6364 /// traversing up the operands.
6365 /// NOTE: This is an expensive method. Use it carefully.
6366 bool SDNode::hasPredecessor(const SDNode *N) const {
6367 SmallPtrSet<const SDNode *, 32> Visited;
6368 SmallVector<const SDNode *, 16> Worklist;
6369 return hasPredecessorHelper(N, Visited, Worklist);
6373 SDNode::hasPredecessorHelper(const SDNode *N,
6374 SmallPtrSet<const SDNode *, 32> &Visited,
6375 SmallVectorImpl<const SDNode *> &Worklist) const {
6376 if (Visited.empty()) {
6377 Worklist.push_back(this);
6379 // Take a look in the visited set. If we've already encountered this node
6380 // we needn't search further.
6381 if (Visited.count(N))
6385 // Haven't visited N yet. Continue the search.
6386 while (!Worklist.empty()) {
6387 const SDNode *M = Worklist.pop_back_val();
6388 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6389 SDNode *Op = M->getOperand(i).getNode();
6390 if (Visited.insert(Op))
6391 Worklist.push_back(Op);
6400 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6401 assert(Num < NumOperands && "Invalid child # of SDNode!");
6402 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6405 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6406 assert(N->getNumValues() == 1 &&
6407 "Can't unroll a vector with multiple results!");
6409 EVT VT = N->getValueType(0);
6410 unsigned NE = VT.getVectorNumElements();
6411 EVT EltVT = VT.getVectorElementType();
6414 SmallVector<SDValue, 8> Scalars;
6415 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6417 // If ResNE is 0, fully unroll the vector op.
6420 else if (NE > ResNE)
6424 for (i= 0; i != NE; ++i) {
6425 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6426 SDValue Operand = N->getOperand(j);
6427 EVT OperandVT = Operand.getValueType();
6428 if (OperandVT.isVector()) {
6429 // A vector operand; extract a single element.
6430 const TargetLowering *TLI = TM.getTargetLowering();
6431 EVT OperandEltVT = OperandVT.getVectorElementType();
6432 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6435 getConstant(i, TLI->getVectorIdxTy()));
6437 // A scalar operand; just use it as is.
6438 Operands[j] = Operand;
6442 switch (N->getOpcode()) {
6444 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6447 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6454 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6455 getShiftAmountOperand(Operands[0].getValueType(),
6458 case ISD::SIGN_EXTEND_INREG:
6459 case ISD::FP_ROUND_INREG: {
6460 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6461 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6463 getValueType(ExtVT)));
6468 for (; i < ResNE; ++i)
6469 Scalars.push_back(getUNDEF(EltVT));
6471 return getNode(ISD::BUILD_VECTOR, dl,
6472 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6476 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6477 /// location that is 'Dist' units away from the location that the 'Base' load
6478 /// is loading from.
6479 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6480 unsigned Bytes, int Dist) const {
6481 if (LD->getChain() != Base->getChain())
6483 EVT VT = LD->getValueType(0);
6484 if (VT.getSizeInBits() / 8 != Bytes)
6487 SDValue Loc = LD->getOperand(1);
6488 SDValue BaseLoc = Base->getOperand(1);
6489 if (Loc.getOpcode() == ISD::FrameIndex) {
6490 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6492 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6493 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6494 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6495 int FS = MFI->getObjectSize(FI);
6496 int BFS = MFI->getObjectSize(BFI);
6497 if (FS != BFS || FS != (int)Bytes) return false;
6498 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6502 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6503 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6506 const GlobalValue *GV1 = nullptr;
6507 const GlobalValue *GV2 = nullptr;
6508 int64_t Offset1 = 0;
6509 int64_t Offset2 = 0;
6510 const TargetLowering *TLI = TM.getTargetLowering();
6511 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6512 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6513 if (isGA1 && isGA2 && GV1 == GV2)
6514 return Offset1 == (Offset2 + Dist*Bytes);
6519 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6520 /// it cannot be inferred.
6521 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6522 // If this is a GlobalAddress + cst, return the alignment.
6523 const GlobalValue *GV;
6524 int64_t GVOffset = 0;
6525 const TargetLowering *TLI = TM.getTargetLowering();
6526 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6527 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6528 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6529 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6530 TLI->getDataLayout());
6531 unsigned AlignBits = KnownZero.countTrailingOnes();
6532 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6534 return MinAlign(Align, GVOffset);
6537 // If this is a direct reference to a stack slot, use information about the
6538 // stack slot's alignment.
6539 int FrameIdx = 1 << 31;
6540 int64_t FrameOffset = 0;
6541 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6542 FrameIdx = FI->getIndex();
6543 } else if (isBaseWithConstantOffset(Ptr) &&
6544 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6546 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6547 FrameOffset = Ptr.getConstantOperandVal(1);
6550 if (FrameIdx != (1 << 31)) {
6551 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6552 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6560 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6561 /// which is split (or expanded) into two not necessarily identical pieces.
6562 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6563 // Currently all types are split in half.
6565 if (!VT.isVector()) {
6566 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6568 unsigned NumElements = VT.getVectorNumElements();
6569 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6570 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6573 return std::make_pair(LoVT, HiVT);
6576 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6578 std::pair<SDValue, SDValue>
6579 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6581 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6582 N.getValueType().getVectorNumElements() &&
6583 "More vector elements requested than available!");
6585 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6586 getConstant(0, TLI->getVectorIdxTy()));
6587 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6588 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6589 return std::make_pair(Lo, Hi);
6592 void SelectionDAG::ExtractVectorElements(SDValue Op,
6593 SmallVectorImpl<SDValue> &Args,
6594 unsigned Start, unsigned Count) {
6595 EVT VT = Op.getValueType();
6597 Count = VT.getVectorNumElements();
6599 EVT EltVT = VT.getVectorElementType();
6600 EVT IdxTy = TLI->getVectorIdxTy();
6602 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6603 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6604 Op, getConstant(i, IdxTy)));
6608 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6609 unsigned GlobalAddressSDNode::getAddressSpace() const {
6610 return getGlobal()->getType()->getAddressSpace();
6614 Type *ConstantPoolSDNode::getType() const {
6615 if (isMachineConstantPoolEntry())
6616 return Val.MachineCPVal->getType();
6617 return Val.ConstVal->getType();
6620 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6622 unsigned &SplatBitSize,
6624 unsigned MinSplatBits,
6625 bool isBigEndian) const {
6626 EVT VT = getValueType(0);
6627 assert(VT.isVector() && "Expected a vector type");
6628 unsigned sz = VT.getSizeInBits();
6629 if (MinSplatBits > sz)
6632 SplatValue = APInt(sz, 0);
6633 SplatUndef = APInt(sz, 0);
6635 // Get the bits. Bits with undefined values (when the corresponding element
6636 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6637 // in SplatValue. If any of the values are not constant, give up and return
6639 unsigned int nOps = getNumOperands();
6640 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6641 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6643 for (unsigned j = 0; j < nOps; ++j) {
6644 unsigned i = isBigEndian ? nOps-1-j : j;
6645 SDValue OpVal = getOperand(i);
6646 unsigned BitPos = j * EltBitSize;
6648 if (OpVal.getOpcode() == ISD::UNDEF)
6649 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6650 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6651 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6652 zextOrTrunc(sz) << BitPos;
6653 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6654 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6659 // The build_vector is all constants or undefs. Find the smallest element
6660 // size that splats the vector.
6662 HasAnyUndefs = (SplatUndef != 0);
6665 unsigned HalfSize = sz / 2;
6666 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6667 APInt LowValue = SplatValue.trunc(HalfSize);
6668 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6669 APInt LowUndef = SplatUndef.trunc(HalfSize);
6671 // If the two halves do not match (ignoring undef bits), stop here.
6672 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6673 MinSplatBits > HalfSize)
6676 SplatValue = HighValue | LowValue;
6677 SplatUndef = HighUndef & LowUndef;
6686 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6687 if (UndefElements) {
6688 UndefElements->clear();
6689 UndefElements->resize(getNumOperands());
6692 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6693 SDValue Op = getOperand(i);
6694 if (Op.getOpcode() == ISD::UNDEF) {
6696 (*UndefElements)[i] = true;
6697 } else if (!Splatted) {
6699 } else if (Splatted != Op) {
6705 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6706 "Can only have a splat without a constant for all undefs.");
6707 return getOperand(0);
6714 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6715 return dyn_cast_or_null<ConstantSDNode>(
6716 getSplatValue(UndefElements).getNode());
6720 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6721 return dyn_cast_or_null<ConstantFPSDNode>(
6722 getSplatValue(UndefElements).getNode());
6725 bool BuildVectorSDNode::isConstant() const {
6726 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6727 unsigned Opc = getOperand(i).getOpcode();
6728 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6734 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6735 // Find the first non-undef value in the shuffle mask.
6737 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6740 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6742 // Make sure all remaining elements are either undef or the same as the first
6744 for (int Idx = Mask[i]; i != e; ++i)
6745 if (Mask[i] >= 0 && Mask[i] != Idx)
6751 static void checkForCyclesHelper(const SDNode *N,
6752 SmallPtrSet<const SDNode*, 32> &Visited,
6753 SmallPtrSet<const SDNode*, 32> &Checked,
6754 const llvm::SelectionDAG *DAG) {
6755 // If this node has already been checked, don't check it again.
6756 if (Checked.count(N))
6759 // If a node has already been visited on this depth-first walk, reject it as
6761 if (!Visited.insert(N)) {
6762 errs() << "Detected cycle in SelectionDAG\n";
6763 dbgs() << "Offending node:\n";
6764 N->dumprFull(DAG); dbgs() << "\n";
6768 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6769 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6776 void llvm::checkForCycles(const llvm::SDNode *N,
6777 const llvm::SelectionDAG *DAG,
6785 assert(N && "Checking nonexistent SDNode");
6786 SmallPtrSet<const SDNode*, 32> visited;
6787 SmallPtrSet<const SDNode*, 32> checked;
6788 checkForCyclesHelper(N, visited, checked, DAG);
6793 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6794 checkForCycles(DAG->getRoot().getNode(), DAG, force);