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"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// isScalarToVector - Return true if the specified node is a
200 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
201 /// element is not an undef.
202 bool ISD::isScalarToVector(const SDNode *N) {
203 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
206 if (N->getOpcode() != ISD::BUILD_VECTOR)
208 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
210 unsigned NumElems = N->getNumOperands();
213 for (unsigned i = 1; i < NumElems; ++i) {
214 SDValue V = N->getOperand(i);
215 if (V.getOpcode() != ISD::UNDEF)
221 /// allOperandsUndef - Return true if the node has at least one operand
222 /// and all operands of the specified node are ISD::UNDEF.
223 bool ISD::allOperandsUndef(const SDNode *N) {
224 // Return false if the node has no operands.
225 // This is "logically inconsistent" with the definition of "all" but
226 // is probably the desired behavior.
227 if (N->getNumOperands() == 0)
230 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
231 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
237 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
240 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
242 return ISD::SIGN_EXTEND;
244 return ISD::ZERO_EXTEND;
249 llvm_unreachable("Invalid LoadExtType");
252 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
253 /// when given the operation for (X op Y).
254 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
255 // To perform this operation, we just need to swap the L and G bits of the
257 unsigned OldL = (Operation >> 2) & 1;
258 unsigned OldG = (Operation >> 1) & 1;
259 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
260 (OldL << 1) | // New G bit
261 (OldG << 2)); // New L bit.
264 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
265 /// 'op' is a valid SetCC operation.
266 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
267 unsigned Operation = Op;
269 Operation ^= 7; // Flip L, G, E bits, but not U.
271 Operation ^= 15; // Flip all of the condition bits.
273 if (Operation > ISD::SETTRUE2)
274 Operation &= ~8; // Don't let N and U bits get set.
276 return ISD::CondCode(Operation);
280 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
281 /// signed operation and 2 if the result is an unsigned comparison. Return zero
282 /// if the operation does not depend on the sign of the input (setne and seteq).
283 static int isSignedOp(ISD::CondCode Opcode) {
285 default: llvm_unreachable("Illegal integer setcc operation!");
287 case ISD::SETNE: return 0;
291 case ISD::SETGE: return 1;
295 case ISD::SETUGE: return 2;
299 /// getSetCCOrOperation - Return the result of a logical OR between different
300 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
301 /// returns SETCC_INVALID if it is not possible to represent the resultant
303 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
305 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
306 // Cannot fold a signed integer setcc with an unsigned integer setcc.
307 return ISD::SETCC_INVALID;
309 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
311 // If the N and U bits get set then the resultant comparison DOES suddenly
312 // care about orderedness, and is true when ordered.
313 if (Op > ISD::SETTRUE2)
314 Op &= ~16; // Clear the U bit if the N bit is set.
316 // Canonicalize illegal integer setcc's.
317 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
320 return ISD::CondCode(Op);
323 /// getSetCCAndOperation - Return the result of a logical AND between different
324 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
325 /// function returns zero if it is not possible to represent the resultant
327 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
329 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
330 // Cannot fold a signed setcc with an unsigned setcc.
331 return ISD::SETCC_INVALID;
333 // Combine all of the condition bits.
334 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
336 // Canonicalize illegal integer setcc's.
340 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
341 case ISD::SETOEQ: // SETEQ & SETU[LG]E
342 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
343 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
344 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
351 //===----------------------------------------------------------------------===//
352 // SDNode Profile Support
353 //===----------------------------------------------------------------------===//
355 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
357 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
361 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
362 /// solely with their pointer.
363 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
364 ID.AddPointer(VTList.VTs);
367 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
369 static void AddNodeIDOperands(FoldingSetNodeID &ID,
370 ArrayRef<SDValue> Ops) {
371 for (auto& Op : Ops) {
372 ID.AddPointer(Op.getNode());
373 ID.AddInteger(Op.getResNo());
377 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
379 static void AddNodeIDOperands(FoldingSetNodeID &ID,
380 ArrayRef<SDUse> Ops) {
381 for (auto& Op : Ops) {
382 ID.AddPointer(Op.getNode());
383 ID.AddInteger(Op.getResNo());
387 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
391 ID.AddBoolean(exact);
394 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
395 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
396 bool nuw, bool nsw, bool exact) {
397 if (isBinOpWithFlags(Opcode))
398 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
401 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
402 SDVTList VTList, ArrayRef<SDValue> OpList) {
403 AddNodeIDOpcode(ID, OpC);
404 AddNodeIDValueTypes(ID, VTList);
405 AddNodeIDOperands(ID, OpList);
408 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
410 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
411 switch (N->getOpcode()) {
412 case ISD::TargetExternalSymbol:
413 case ISD::ExternalSymbol:
414 llvm_unreachable("Should only be used on nodes with operands");
415 default: break; // Normal nodes don't need extra info.
416 case ISD::TargetConstant:
417 case ISD::Constant: {
418 const ConstantSDNode *C = cast<ConstantSDNode>(N);
419 ID.AddPointer(C->getConstantIntValue());
420 ID.AddBoolean(C->isOpaque());
423 case ISD::TargetConstantFP:
424 case ISD::ConstantFP: {
425 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
428 case ISD::TargetGlobalAddress:
429 case ISD::GlobalAddress:
430 case ISD::TargetGlobalTLSAddress:
431 case ISD::GlobalTLSAddress: {
432 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
433 ID.AddPointer(GA->getGlobal());
434 ID.AddInteger(GA->getOffset());
435 ID.AddInteger(GA->getTargetFlags());
436 ID.AddInteger(GA->getAddressSpace());
439 case ISD::BasicBlock:
440 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
443 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
445 case ISD::RegisterMask:
446 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
449 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
451 case ISD::FrameIndex:
452 case ISD::TargetFrameIndex:
453 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
456 case ISD::TargetJumpTable:
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
458 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
460 case ISD::ConstantPool:
461 case ISD::TargetConstantPool: {
462 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
463 ID.AddInteger(CP->getAlignment());
464 ID.AddInteger(CP->getOffset());
465 if (CP->isMachineConstantPoolEntry())
466 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
468 ID.AddPointer(CP->getConstVal());
469 ID.AddInteger(CP->getTargetFlags());
472 case ISD::TargetIndex: {
473 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
474 ID.AddInteger(TI->getIndex());
475 ID.AddInteger(TI->getOffset());
476 ID.AddInteger(TI->getTargetFlags());
480 const LoadSDNode *LD = cast<LoadSDNode>(N);
481 ID.AddInteger(LD->getMemoryVT().getRawBits());
482 ID.AddInteger(LD->getRawSubclassData());
483 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
487 const StoreSDNode *ST = cast<StoreSDNode>(N);
488 ID.AddInteger(ST->getMemoryVT().getRawBits());
489 ID.AddInteger(ST->getRawSubclassData());
490 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
501 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
502 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
503 BinNode->hasNoSignedWrap(), BinNode->isExact());
506 case ISD::ATOMIC_CMP_SWAP:
507 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
508 case ISD::ATOMIC_SWAP:
509 case ISD::ATOMIC_LOAD_ADD:
510 case ISD::ATOMIC_LOAD_SUB:
511 case ISD::ATOMIC_LOAD_AND:
512 case ISD::ATOMIC_LOAD_OR:
513 case ISD::ATOMIC_LOAD_XOR:
514 case ISD::ATOMIC_LOAD_NAND:
515 case ISD::ATOMIC_LOAD_MIN:
516 case ISD::ATOMIC_LOAD_MAX:
517 case ISD::ATOMIC_LOAD_UMIN:
518 case ISD::ATOMIC_LOAD_UMAX:
519 case ISD::ATOMIC_LOAD:
520 case ISD::ATOMIC_STORE: {
521 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
522 ID.AddInteger(AT->getMemoryVT().getRawBits());
523 ID.AddInteger(AT->getRawSubclassData());
524 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
527 case ISD::PREFETCH: {
528 const MemSDNode *PF = cast<MemSDNode>(N);
529 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
532 case ISD::VECTOR_SHUFFLE: {
533 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
534 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
536 ID.AddInteger(SVN->getMaskElt(i));
539 case ISD::TargetBlockAddress:
540 case ISD::BlockAddress: {
541 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
542 ID.AddPointer(BA->getBlockAddress());
543 ID.AddInteger(BA->getOffset());
544 ID.AddInteger(BA->getTargetFlags());
547 } // end switch (N->getOpcode())
549 // Target specific memory nodes could also have address spaces to check.
550 if (N->isTargetMemoryOpcode())
551 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
554 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
556 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
557 AddNodeIDOpcode(ID, N->getOpcode());
558 // Add the return value info.
559 AddNodeIDValueTypes(ID, N->getVTList());
560 // Add the operand info.
561 AddNodeIDOperands(ID, N->ops());
563 // Handle SDNode leafs with special info.
564 AddNodeIDCustom(ID, N);
567 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
568 /// the CSE map that carries volatility, temporalness, indexing mode, and
569 /// extension/truncation information.
571 static inline unsigned
572 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
573 bool isNonTemporal, bool isInvariant) {
574 assert((ConvType & 3) == ConvType &&
575 "ConvType may not require more than 2 bits!");
576 assert((AM & 7) == AM &&
577 "AM may not require more than 3 bits!");
581 (isNonTemporal << 6) |
585 //===----------------------------------------------------------------------===//
586 // SelectionDAG Class
587 //===----------------------------------------------------------------------===//
589 /// doNotCSE - Return true if CSE should not be performed for this node.
590 static bool doNotCSE(SDNode *N) {
591 if (N->getValueType(0) == MVT::Glue)
592 return true; // Never CSE anything that produces a flag.
594 switch (N->getOpcode()) {
596 case ISD::HANDLENODE:
598 return true; // Never CSE these nodes.
601 // Check that remaining values produced are not flags.
602 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
603 if (N->getValueType(i) == MVT::Glue)
604 return true; // Never CSE anything that produces a flag.
609 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
611 void SelectionDAG::RemoveDeadNodes() {
612 // Create a dummy node (which is not added to allnodes), that adds a reference
613 // to the root node, preventing it from being deleted.
614 HandleSDNode Dummy(getRoot());
616 SmallVector<SDNode*, 128> DeadNodes;
618 // Add all obviously-dead nodes to the DeadNodes worklist.
619 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
621 DeadNodes.push_back(I);
623 RemoveDeadNodes(DeadNodes);
625 // If the root changed (e.g. it was a dead load, update the root).
626 setRoot(Dummy.getValue());
629 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
630 /// given list, and any nodes that become unreachable as a result.
631 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
633 // Process the worklist, deleting the nodes and adding their uses to the
635 while (!DeadNodes.empty()) {
636 SDNode *N = DeadNodes.pop_back_val();
638 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
639 DUL->NodeDeleted(N, nullptr);
641 // Take the node out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Next, brutally remove the operand list. This is safe to do, as there are
645 // no cycles in the graph.
646 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
648 SDNode *Operand = Use.getNode();
651 // Now that we removed this operand, see if there are no uses of it left.
652 if (Operand->use_empty())
653 DeadNodes.push_back(Operand);
660 void SelectionDAG::RemoveDeadNode(SDNode *N){
661 SmallVector<SDNode*, 16> DeadNodes(1, N);
663 // Create a dummy node that adds a reference to the root node, preventing
664 // it from being deleted. (This matters if the root is an operand of the
666 HandleSDNode Dummy(getRoot());
668 RemoveDeadNodes(DeadNodes);
671 void SelectionDAG::DeleteNode(SDNode *N) {
672 // First take this out of the appropriate CSE map.
673 RemoveNodeFromCSEMaps(N);
675 // Finally, remove uses due to operands of this node, remove from the
676 // AllNodes list, and delete the node.
677 DeleteNodeNotInCSEMaps(N);
680 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
681 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
682 assert(N->use_empty() && "Cannot delete a node that is not dead!");
684 // Drop all of the operands and decrement used node's use counts.
690 void SDDbgInfo::erase(const SDNode *Node) {
691 DbgValMapType::iterator I = DbgValMap.find(Node);
692 if (I == DbgValMap.end())
694 for (auto &Val: I->second)
695 Val->setIsInvalidated();
699 void SelectionDAG::DeallocateNode(SDNode *N) {
700 if (N->OperandsNeedDelete)
701 delete[] N->OperandList;
703 // Set the opcode to DELETED_NODE to help catch bugs when node
704 // memory is reallocated.
705 N->NodeType = ISD::DELETED_NODE;
707 NodeAllocator.Deallocate(AllNodes.remove(N));
709 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
710 // them and forget about that node.
715 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
716 static void VerifySDNode(SDNode *N) {
717 switch (N->getOpcode()) {
720 case ISD::BUILD_PAIR: {
721 EVT VT = N->getValueType(0);
722 assert(N->getNumValues() == 1 && "Too many results!");
723 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
724 "Wrong return type!");
725 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
726 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
727 "Mismatched operand types!");
728 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
729 "Wrong operand type!");
730 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
731 "Wrong return type size");
734 case ISD::BUILD_VECTOR: {
735 assert(N->getNumValues() == 1 && "Too many results!");
736 assert(N->getValueType(0).isVector() && "Wrong return type!");
737 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
738 "Wrong number of operands!");
739 EVT EltVT = N->getValueType(0).getVectorElementType();
740 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
741 assert((I->getValueType() == EltVT ||
742 (EltVT.isInteger() && I->getValueType().isInteger() &&
743 EltVT.bitsLE(I->getValueType()))) &&
744 "Wrong operand type!");
745 assert(I->getValueType() == N->getOperand(0).getValueType() &&
746 "Operands must all have the same type");
754 /// \brief Insert a newly allocated node into the DAG.
756 /// Handles insertion into the all nodes list and CSE map, as well as
757 /// verification and other common operations when a new node is allocated.
758 void SelectionDAG::InsertNode(SDNode *N) {
759 AllNodes.push_back(N);
765 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
766 /// correspond to it. This is useful when we're about to delete or repurpose
767 /// the node. We don't want future request for structurally identical nodes
768 /// to return N anymore.
769 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
771 switch (N->getOpcode()) {
772 case ISD::HANDLENODE: return false; // noop.
774 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
775 "Cond code doesn't exist!");
776 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
777 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
779 case ISD::ExternalSymbol:
780 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
782 case ISD::TargetExternalSymbol: {
783 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
784 Erased = TargetExternalSymbols.erase(
785 std::pair<std::string,unsigned char>(ESN->getSymbol(),
786 ESN->getTargetFlags()));
789 case ISD::VALUETYPE: {
790 EVT VT = cast<VTSDNode>(N)->getVT();
791 if (VT.isExtended()) {
792 Erased = ExtendedValueTypeNodes.erase(VT);
794 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
795 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
800 // Remove it from the CSE Map.
801 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
802 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
803 Erased = CSEMap.RemoveNode(N);
807 // Verify that the node was actually in one of the CSE maps, unless it has a
808 // flag result (which cannot be CSE'd) or is one of the special cases that are
809 // not subject to CSE.
810 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
811 !N->isMachineOpcode() && !doNotCSE(N)) {
814 llvm_unreachable("Node is not in map!");
820 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
821 /// maps and modified in place. Add it back to the CSE maps, unless an identical
822 /// node already exists, in which case transfer all its users to the existing
823 /// node. This transfer can potentially trigger recursive merging.
826 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
827 // For node types that aren't CSE'd, just act as if no identical node
830 SDNode *Existing = CSEMap.GetOrInsertNode(N);
832 // If there was already an existing matching node, use ReplaceAllUsesWith
833 // to replace the dead one with the existing one. This can cause
834 // recursive merging of other unrelated nodes down the line.
835 ReplaceAllUsesWith(N, Existing);
837 // N is now dead. Inform the listeners and delete it.
838 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
839 DUL->NodeDeleted(N, Existing);
840 DeleteNodeNotInCSEMaps(N);
845 // If the node doesn't already exist, we updated it. Inform listeners.
846 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
850 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
851 /// were replaced with those specified. If this node is never memoized,
852 /// return null, otherwise return a pointer to the slot it would take. If a
853 /// node already exists with these operands, the slot will be non-null.
854 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
859 SDValue Ops[] = { Op };
861 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
862 AddNodeIDCustom(ID, N);
863 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified. If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take. If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
872 SDValue Op1, SDValue Op2,
877 SDValue Ops[] = { Op1, Op2 };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
886 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
887 /// were replaced with those specified. If this node is never memoized,
888 /// return null, otherwise return a pointer to the slot it would take. If a
889 /// node already exists with these operands, the slot will be non-null.
890 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
896 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897 AddNodeIDCustom(ID, N);
898 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
902 /// getEVTAlignment - Compute the default alignment value for the
905 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
906 Type *Ty = VT == MVT::iPTR ?
907 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
908 VT.getTypeForEVT(*getContext());
910 return TLI->getDataLayout()->getABITypeAlignment(Ty);
913 // EntryNode could meaningfully have debug info if we can find it...
914 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
915 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
916 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
917 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
918 UpdateListeners(nullptr) {
919 AllNodes.push_back(&EntryNode);
920 DbgInfo = new SDDbgInfo();
923 void SelectionDAG::init(MachineFunction &mf) {
925 TLI = getSubtarget().getTargetLowering();
926 TSI = getSubtarget().getSelectionDAGInfo();
927 Context = &mf.getFunction()->getContext();
930 SelectionDAG::~SelectionDAG() {
931 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
936 void SelectionDAG::allnodes_clear() {
937 assert(&*AllNodes.begin() == &EntryNode);
938 AllNodes.remove(AllNodes.begin());
939 while (!AllNodes.empty())
940 DeallocateNode(AllNodes.begin());
943 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
944 SDVTList VTs, SDValue N1,
945 SDValue N2, bool nuw, bool nsw,
947 if (isBinOpWithFlags(Opcode)) {
948 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
949 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
950 FN->setHasNoUnsignedWrap(nuw);
951 FN->setHasNoSignedWrap(nsw);
952 FN->setIsExact(exact);
957 BinarySDNode *N = new (NodeAllocator)
958 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
962 void SelectionDAG::clear() {
964 OperandAllocator.Reset();
967 ExtendedValueTypeNodes.clear();
968 ExternalSymbols.clear();
969 TargetExternalSymbols.clear();
970 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
971 static_cast<CondCodeSDNode*>(nullptr));
972 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
973 static_cast<SDNode*>(nullptr));
975 EntryNode.UseList = nullptr;
976 AllNodes.push_back(&EntryNode);
977 Root = getEntryNode();
981 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
982 return VT.bitsGT(Op.getValueType()) ?
983 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
984 getNode(ISD::TRUNCATE, DL, VT, Op);
987 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
988 return VT.bitsGT(Op.getValueType()) ?
989 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
990 getNode(ISD::TRUNCATE, DL, VT, Op);
993 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
994 return VT.bitsGT(Op.getValueType()) ?
995 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
996 getNode(ISD::TRUNCATE, DL, VT, Op);
999 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1001 if (VT.bitsLE(Op.getValueType()))
1002 return getNode(ISD::TRUNCATE, SL, VT, Op);
1004 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1005 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1008 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1009 assert(!VT.isVector() &&
1010 "getZeroExtendInReg should use the vector element type instead of "
1011 "the vector type!");
1012 if (Op.getValueType() == VT) return Op;
1013 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1014 APInt Imm = APInt::getLowBitsSet(BitWidth,
1015 VT.getSizeInBits());
1016 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1017 getConstant(Imm, Op.getValueType()));
1020 SDValue SelectionDAG::getAnyExtendVectorInReg(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::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1030 SDValue SelectionDAG::getSignExtendVectorInReg(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::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1040 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1041 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1042 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1043 "The sizes of the input and result must match in order to perform the "
1044 "extend in-register.");
1045 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1046 "The destination vector type must have fewer lanes than the input.");
1047 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1050 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1052 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1053 EVT EltVT = VT.getScalarType();
1055 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1056 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1059 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1060 EVT EltVT = VT.getScalarType();
1062 switch (TLI->getBooleanContents(VT)) {
1063 case TargetLowering::ZeroOrOneBooleanContent:
1064 case TargetLowering::UndefinedBooleanContent:
1065 TrueValue = getConstant(1, VT);
1067 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1068 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1072 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1075 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1076 EVT EltVT = VT.getScalarType();
1077 assert((EltVT.getSizeInBits() >= 64 ||
1078 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1079 "getConstant with a uint64_t value that doesn't fit in the type!");
1080 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1083 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1085 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1088 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1090 assert(VT.isInteger() && "Cannot create FP integer constant!");
1092 EVT EltVT = VT.getScalarType();
1093 const ConstantInt *Elt = &Val;
1095 // In some cases the vector type is legal but the element type is illegal and
1096 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1097 // inserted value (the type does not need to match the vector element type).
1098 // Any extra bits introduced will be truncated away.
1099 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1100 TargetLowering::TypePromoteInteger) {
1101 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1102 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1103 Elt = ConstantInt::get(*getContext(), NewVal);
1105 // In other cases the element type is illegal and needs to be expanded, for
1106 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1107 // the value into n parts and use a vector type with n-times the elements.
1108 // Then bitcast to the type requested.
1109 // Legalizing constants too early makes the DAGCombiner's job harder so we
1110 // only legalize if the DAG tells us we must produce legal types.
1111 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1112 TLI->getTypeAction(*getContext(), EltVT) ==
1113 TargetLowering::TypeExpandInteger) {
1114 APInt NewVal = Elt->getValue();
1115 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1116 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1117 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1118 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1120 // Check the temporary vector is the correct size. If this fails then
1121 // getTypeToTransformTo() probably returned a type whose size (in bits)
1122 // isn't a power-of-2 factor of the requested type size.
1123 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1125 SmallVector<SDValue, 2> EltParts;
1126 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1127 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1128 .trunc(ViaEltSizeInBits),
1129 ViaEltVT, isT, isO));
1132 // EltParts is currently in little endian order. If we actually want
1133 // big-endian order then reverse it now.
1134 if (TLI->isBigEndian())
1135 std::reverse(EltParts.begin(), EltParts.end());
1137 // The elements must be reversed when the element order is different
1138 // to the endianness of the elements (because the BITCAST is itself a
1139 // vector shuffle in this situation). However, we do not need any code to
1140 // perform this reversal because getConstant() is producing a vector
1142 // This situation occurs in MIPS MSA.
1144 SmallVector<SDValue, 8> Ops;
1145 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1146 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1148 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1149 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1154 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1155 "APInt size does not match type size!");
1156 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1157 FoldingSetNodeID ID;
1158 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1162 SDNode *N = nullptr;
1163 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1165 return SDValue(N, 0);
1168 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1169 CSEMap.InsertNode(N, IP);
1173 SDValue Result(N, 0);
1174 if (VT.isVector()) {
1175 SmallVector<SDValue, 8> Ops;
1176 Ops.assign(VT.getVectorNumElements(), Result);
1177 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1182 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1183 return getConstant(Val, TLI->getPointerTy(), isTarget);
1187 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1188 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1191 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1192 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1194 EVT EltVT = VT.getScalarType();
1196 // Do the map lookup using the actual bit pattern for the floating point
1197 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1198 // we don't have issues with SNANs.
1199 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1200 FoldingSetNodeID ID;
1201 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1204 SDNode *N = nullptr;
1205 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1207 return SDValue(N, 0);
1210 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1211 CSEMap.InsertNode(N, IP);
1215 SDValue Result(N, 0);
1216 if (VT.isVector()) {
1217 SmallVector<SDValue, 8> Ops;
1218 Ops.assign(VT.getVectorNumElements(), Result);
1219 // FIXME SDLoc info might be appropriate here
1220 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1225 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1226 EVT EltVT = VT.getScalarType();
1227 if (EltVT==MVT::f32)
1228 return getConstantFP(APFloat((float)Val), VT, isTarget);
1229 else if (EltVT==MVT::f64)
1230 return getConstantFP(APFloat(Val), VT, isTarget);
1231 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1234 APFloat apf = APFloat(Val);
1235 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1237 return getConstantFP(apf, VT, isTarget);
1239 llvm_unreachable("Unsupported type in getConstantFP");
1242 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1243 EVT VT, int64_t Offset,
1245 unsigned char TargetFlags) {
1246 assert((TargetFlags == 0 || isTargetGA) &&
1247 "Cannot set target flags on target-independent globals");
1249 // Truncate (with sign-extension) the offset value to the pointer size.
1250 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1252 Offset = SignExtend64(Offset, BitWidth);
1255 if (GV->isThreadLocal())
1256 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1258 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1260 FoldingSetNodeID ID;
1261 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1263 ID.AddInteger(Offset);
1264 ID.AddInteger(TargetFlags);
1265 ID.AddInteger(GV->getType()->getAddressSpace());
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1271 DL.getDebugLoc(), GV, VT,
1272 Offset, TargetFlags);
1273 CSEMap.InsertNode(N, IP);
1275 return SDValue(N, 0);
1278 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1279 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1284 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1285 return SDValue(E, 0);
1287 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1288 CSEMap.InsertNode(N, IP);
1290 return SDValue(N, 0);
1293 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1294 unsigned char TargetFlags) {
1295 assert((TargetFlags == 0 || isTarget) &&
1296 "Cannot set target flags on target-independent jump tables");
1297 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1298 FoldingSetNodeID ID;
1299 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1301 ID.AddInteger(TargetFlags);
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1308 CSEMap.InsertNode(N, IP);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1314 unsigned Alignment, int Offset,
1316 unsigned char TargetFlags) {
1317 assert((TargetFlags == 0 || isTarget) &&
1318 "Cannot set target flags on target-independent globals");
1320 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1321 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1322 FoldingSetNodeID ID;
1323 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1324 ID.AddInteger(Alignment);
1325 ID.AddInteger(Offset);
1327 ID.AddInteger(TargetFlags);
1329 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1330 return SDValue(E, 0);
1332 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1333 Alignment, TargetFlags);
1334 CSEMap.InsertNode(N, IP);
1336 return SDValue(N, 0);
1340 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1341 unsigned Alignment, int Offset,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent globals");
1347 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1348 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1349 FoldingSetNodeID ID;
1350 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1351 ID.AddInteger(Alignment);
1352 ID.AddInteger(Offset);
1353 C->addSelectionDAGCSEId(ID);
1354 ID.AddInteger(TargetFlags);
1356 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1357 return SDValue(E, 0);
1359 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1360 Alignment, TargetFlags);
1361 CSEMap.InsertNode(N, IP);
1363 return SDValue(N, 0);
1366 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1367 unsigned char TargetFlags) {
1368 FoldingSetNodeID ID;
1369 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1370 ID.AddInteger(Index);
1371 ID.AddInteger(Offset);
1372 ID.AddInteger(TargetFlags);
1374 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1375 return SDValue(E, 0);
1377 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1379 CSEMap.InsertNode(N, IP);
1381 return SDValue(N, 0);
1384 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1385 FoldingSetNodeID ID;
1386 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1390 return SDValue(E, 0);
1392 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1393 CSEMap.InsertNode(N, IP);
1395 return SDValue(N, 0);
1398 SDValue SelectionDAG::getValueType(EVT VT) {
1399 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1400 ValueTypeNodes.size())
1401 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1403 SDNode *&N = VT.isExtended() ?
1404 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1406 if (N) return SDValue(N, 0);
1407 N = new (NodeAllocator) VTSDNode(VT);
1409 return SDValue(N, 0);
1412 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1413 SDNode *&N = ExternalSymbols[Sym];
1414 if (N) return SDValue(N, 0);
1415 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1417 return SDValue(N, 0);
1420 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1421 unsigned char TargetFlags) {
1423 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1425 if (N) return SDValue(N, 0);
1426 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1428 return SDValue(N, 0);
1431 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1432 if ((unsigned)Cond >= CondCodeNodes.size())
1433 CondCodeNodes.resize(Cond+1);
1435 if (!CondCodeNodes[Cond]) {
1436 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1437 CondCodeNodes[Cond] = N;
1441 return SDValue(CondCodeNodes[Cond], 0);
1444 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1445 // the shuffle mask M that point at N1 to point at N2, and indices that point
1446 // N2 to point at N1.
1447 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1449 ShuffleVectorSDNode::commuteMask(M);
1452 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1453 SDValue N2, const int *Mask) {
1454 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1455 "Invalid VECTOR_SHUFFLE");
1457 // Canonicalize shuffle undef, undef -> undef
1458 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1459 return getUNDEF(VT);
1461 // Validate that all indices in Mask are within the range of the elements
1462 // input to the shuffle.
1463 unsigned NElts = VT.getVectorNumElements();
1464 SmallVector<int, 8> MaskVec;
1465 for (unsigned i = 0; i != NElts; ++i) {
1466 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1467 MaskVec.push_back(Mask[i]);
1470 // Canonicalize shuffle v, v -> v, undef
1473 for (unsigned i = 0; i != NElts; ++i)
1474 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1477 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1478 if (N1.getOpcode() == ISD::UNDEF)
1479 commuteShuffle(N1, N2, MaskVec);
1481 // If shuffling a splat, try to blend the splat instead. We do this here so
1482 // that even when this arises during lowering we don't have to re-handle it.
1483 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1484 BitVector UndefElements;
1485 SDValue Splat = BV->getSplatValue(&UndefElements);
1489 for (int i = 0; i < (int)NElts; ++i) {
1490 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1493 // If this input comes from undef, mark it as such.
1494 if (UndefElements[MaskVec[i] - Offset]) {
1499 // If we can blend a non-undef lane, use that instead.
1500 if (!UndefElements[i])
1501 MaskVec[i] = i + Offset;
1504 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1505 BlendSplat(N1BV, 0);
1506 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1507 BlendSplat(N2BV, NElts);
1509 // Canonicalize all index into lhs, -> shuffle lhs, undef
1510 // Canonicalize all index into rhs, -> shuffle rhs, undef
1511 bool AllLHS = true, AllRHS = true;
1512 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1513 for (unsigned i = 0; i != NElts; ++i) {
1514 if (MaskVec[i] >= (int)NElts) {
1519 } else if (MaskVec[i] >= 0) {
1523 if (AllLHS && AllRHS)
1524 return getUNDEF(VT);
1525 if (AllLHS && !N2Undef)
1529 commuteShuffle(N1, N2, MaskVec);
1531 // Reset our undef status after accounting for the mask.
1532 N2Undef = N2.getOpcode() == ISD::UNDEF;
1533 // Re-check whether both sides ended up undef.
1534 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1535 return getUNDEF(VT);
1537 // If Identity shuffle return that node.
1538 bool Identity = true, AllSame = true;
1539 for (unsigned i = 0; i != NElts; ++i) {
1540 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1541 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1543 if (Identity && NElts)
1546 // Shuffling a constant splat doesn't change the result.
1550 // Look through any bitcasts. We check that these don't change the number
1551 // (and size) of elements and just changes their types.
1552 while (V.getOpcode() == ISD::BITCAST)
1553 V = V->getOperand(0);
1555 // A splat should always show up as a build vector node.
1556 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1557 BitVector UndefElements;
1558 SDValue Splat = BV->getSplatValue(&UndefElements);
1559 // If this is a splat of an undef, shuffling it is also undef.
1560 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1561 return getUNDEF(VT);
1564 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1566 // We only have a splat which can skip shuffles if there is a splatted
1567 // value and no undef lanes rearranged by the shuffle.
1568 if (Splat && UndefElements.none()) {
1569 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1570 // number of elements match or the value splatted is a zero constant.
1573 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1574 if (C->isNullValue())
1578 // If the shuffle itself creates a splat, build the vector directly.
1579 if (AllSame && SameNumElts) {
1580 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1581 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1583 EVT BuildVT = BV->getValueType(0);
1584 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1586 // We may have jumped through bitcasts, so the type of the
1587 // BUILD_VECTOR may not match the type of the shuffle.
1589 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1595 FoldingSetNodeID ID;
1596 SDValue Ops[2] = { N1, N2 };
1597 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1598 for (unsigned i = 0; i != NElts; ++i)
1599 ID.AddInteger(MaskVec[i]);
1602 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1603 return SDValue(E, 0);
1605 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1606 // SDNode doesn't have access to it. This memory will be "leaked" when
1607 // the node is deallocated, but recovered when the NodeAllocator is released.
1608 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1609 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1611 ShuffleVectorSDNode *N =
1612 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1613 dl.getDebugLoc(), N1, N2,
1615 CSEMap.InsertNode(N, IP);
1617 return SDValue(N, 0);
1620 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1621 MVT VT = SV.getSimpleValueType(0);
1622 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1623 ShuffleVectorSDNode::commuteMask(MaskVec);
1625 SDValue Op0 = SV.getOperand(0);
1626 SDValue Op1 = SV.getOperand(1);
1627 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1630 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1631 SDValue Val, SDValue DTy,
1632 SDValue STy, SDValue Rnd, SDValue Sat,
1633 ISD::CvtCode Code) {
1634 // If the src and dest types are the same and the conversion is between
1635 // integer types of the same sign or two floats, no conversion is necessary.
1637 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1640 FoldingSetNodeID ID;
1641 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1642 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1644 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1645 return SDValue(E, 0);
1647 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1650 CSEMap.InsertNode(N, IP);
1652 return SDValue(N, 0);
1655 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1656 FoldingSetNodeID ID;
1657 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1658 ID.AddInteger(RegNo);
1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661 return SDValue(E, 0);
1663 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1664 CSEMap.InsertNode(N, IP);
1666 return SDValue(N, 0);
1669 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1670 FoldingSetNodeID ID;
1671 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1672 ID.AddPointer(RegMask);
1674 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1675 return SDValue(E, 0);
1677 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1678 CSEMap.InsertNode(N, IP);
1680 return SDValue(N, 0);
1683 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1684 FoldingSetNodeID ID;
1685 SDValue Ops[] = { Root };
1686 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1687 ID.AddPointer(Label);
1689 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1690 return SDValue(E, 0);
1692 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1693 dl.getDebugLoc(), Root, Label);
1694 CSEMap.InsertNode(N, IP);
1696 return SDValue(N, 0);
1700 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1703 unsigned char TargetFlags) {
1704 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1706 FoldingSetNodeID ID;
1707 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1709 ID.AddInteger(Offset);
1710 ID.AddInteger(TargetFlags);
1712 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1713 return SDValue(E, 0);
1715 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1717 CSEMap.InsertNode(N, IP);
1719 return SDValue(N, 0);
1722 SDValue SelectionDAG::getSrcValue(const Value *V) {
1723 assert((!V || V->getType()->isPointerTy()) &&
1724 "SrcValue is not a pointer?");
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1731 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1741 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1742 FoldingSetNodeID ID;
1743 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1747 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1748 return SDValue(E, 0);
1750 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1756 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1757 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1758 unsigned SrcAS, unsigned DestAS) {
1759 SDValue Ops[] = {Ptr};
1760 FoldingSetNodeID ID;
1761 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1762 ID.AddInteger(SrcAS);
1763 ID.AddInteger(DestAS);
1766 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1767 return SDValue(E, 0);
1769 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1771 VT, Ptr, SrcAS, DestAS);
1772 CSEMap.InsertNode(N, IP);
1774 return SDValue(N, 0);
1777 /// getShiftAmountOperand - Return the specified value casted to
1778 /// the target's desired shift amount type.
1779 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1780 EVT OpTy = Op.getValueType();
1781 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1782 if (OpTy == ShTy || OpTy.isVector()) return Op;
1784 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1785 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1788 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1789 /// specified value type.
1790 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1791 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1792 unsigned ByteSize = VT.getStoreSize();
1793 Type *Ty = VT.getTypeForEVT(*getContext());
1794 unsigned StackAlign =
1795 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1797 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1798 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1801 /// CreateStackTemporary - Create a stack temporary suitable for holding
1802 /// either of the specified value types.
1803 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1804 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1805 VT2.getStoreSizeInBits())/8;
1806 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1807 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1808 const DataLayout *TD = TLI->getDataLayout();
1809 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1810 TD->getPrefTypeAlignment(Ty2));
1812 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1813 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1814 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1817 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1818 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1819 // These setcc operations always fold.
1823 case ISD::SETFALSE2: return getConstant(0, VT);
1825 case ISD::SETTRUE2: {
1826 TargetLowering::BooleanContent Cnt =
1827 TLI->getBooleanContents(N1->getValueType(0));
1829 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1842 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1846 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1847 const APInt &C2 = N2C->getAPIntValue();
1848 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1849 const APInt &C1 = N1C->getAPIntValue();
1852 default: llvm_unreachable("Unknown integer setcc!");
1853 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1854 case ISD::SETNE: return getConstant(C1 != C2, VT);
1855 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1856 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1857 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1858 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1859 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1860 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1861 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1862 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1866 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1867 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1868 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1871 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1872 return getUNDEF(VT);
1874 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1875 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1876 return getUNDEF(VT);
1878 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1879 R==APFloat::cmpLessThan, VT);
1880 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1881 return getUNDEF(VT);
1883 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1884 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1885 return getUNDEF(VT);
1887 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1888 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1889 return getUNDEF(VT);
1891 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1892 R==APFloat::cmpEqual, VT);
1893 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1894 return getUNDEF(VT);
1896 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1897 R==APFloat::cmpEqual, VT);
1898 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1899 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1900 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1901 R==APFloat::cmpEqual, VT);
1902 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1903 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1904 R==APFloat::cmpLessThan, VT);
1905 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1906 R==APFloat::cmpUnordered, VT);
1907 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1908 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1911 // Ensure that the constant occurs on the RHS.
1912 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1913 MVT CompVT = N1.getValueType().getSimpleVT();
1914 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1917 return getSetCC(dl, VT, N2, N1, SwappedCond);
1921 // Could not fold it.
1925 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1926 /// use this predicate to simplify operations downstream.
1927 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1928 // This predicate is not safe for vector operations.
1929 if (Op.getValueType().isVector())
1932 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1933 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1936 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1937 /// this predicate to simplify operations downstream. Mask is known to be zero
1938 /// for bits that V cannot have.
1939 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1940 unsigned Depth) const {
1941 APInt KnownZero, KnownOne;
1942 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1943 return (KnownZero & Mask) == Mask;
1946 /// Determine which bits of Op are known to be either zero or one and return
1947 /// them in the KnownZero/KnownOne bitsets.
1948 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1949 APInt &KnownOne, unsigned Depth) const {
1950 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1952 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1954 return; // Limit search depth.
1956 APInt KnownZero2, KnownOne2;
1958 switch (Op.getOpcode()) {
1960 // We know all of the bits for a constant!
1961 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1962 KnownZero = ~KnownOne;
1965 // If either the LHS or the RHS are Zero, the result is zero.
1966 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1967 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1969 // Output known-1 bits are only known if set in both the LHS & RHS.
1970 KnownOne &= KnownOne2;
1971 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1972 KnownZero |= KnownZero2;
1975 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1976 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1978 // Output known-0 bits are only known if clear in both the LHS & RHS.
1979 KnownZero &= KnownZero2;
1980 // Output known-1 are known to be set if set in either the LHS | RHS.
1981 KnownOne |= KnownOne2;
1984 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1985 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1987 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1988 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1989 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1990 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1991 KnownZero = KnownZeroOut;
1995 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1996 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1998 // If low bits are zero in either operand, output low known-0 bits.
1999 // Also compute a conserative estimate for high known-0 bits.
2000 // More trickiness is possible, but this is sufficient for the
2001 // interesting case of alignment computation.
2002 KnownOne.clearAllBits();
2003 unsigned TrailZ = KnownZero.countTrailingOnes() +
2004 KnownZero2.countTrailingOnes();
2005 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2006 KnownZero2.countLeadingOnes(),
2007 BitWidth) - BitWidth;
2009 TrailZ = std::min(TrailZ, BitWidth);
2010 LeadZ = std::min(LeadZ, BitWidth);
2011 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2012 APInt::getHighBitsSet(BitWidth, LeadZ);
2016 // For the purposes of computing leading zeros we can conservatively
2017 // treat a udiv as a logical right shift by the power of 2 known to
2018 // be less than the denominator.
2019 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2020 unsigned LeadZ = KnownZero2.countLeadingOnes();
2022 KnownOne2.clearAllBits();
2023 KnownZero2.clearAllBits();
2024 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2025 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2026 if (RHSUnknownLeadingOnes != BitWidth)
2027 LeadZ = std::min(BitWidth,
2028 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2030 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2034 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2035 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2037 // Only known if known in both the LHS and RHS.
2038 KnownOne &= KnownOne2;
2039 KnownZero &= KnownZero2;
2041 case ISD::SELECT_CC:
2042 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2043 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2045 // Only known if known in both the LHS and RHS.
2046 KnownOne &= KnownOne2;
2047 KnownZero &= KnownZero2;
2055 if (Op.getResNo() != 1)
2057 // The boolean result conforms to getBooleanContents.
2058 // If we know the result of a setcc has the top bits zero, use this info.
2059 // We know that we have an integer-based boolean since these operations
2060 // are only available for integer.
2061 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2062 TargetLowering::ZeroOrOneBooleanContent &&
2064 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2067 // If we know the result of a setcc has the top bits zero, use this info.
2068 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2069 TargetLowering::ZeroOrOneBooleanContent &&
2071 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2074 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2075 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2076 unsigned ShAmt = SA->getZExtValue();
2078 // If the shift count is an invalid immediate, don't do anything.
2079 if (ShAmt >= BitWidth)
2082 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2083 KnownZero <<= ShAmt;
2085 // low bits known zero.
2086 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2090 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2091 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2092 unsigned ShAmt = SA->getZExtValue();
2094 // If the shift count is an invalid immediate, don't do anything.
2095 if (ShAmt >= BitWidth)
2098 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2099 KnownZero = KnownZero.lshr(ShAmt);
2100 KnownOne = KnownOne.lshr(ShAmt);
2102 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2103 KnownZero |= HighBits; // High bits known zero.
2107 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2108 unsigned ShAmt = SA->getZExtValue();
2110 // If the shift count is an invalid immediate, don't do anything.
2111 if (ShAmt >= BitWidth)
2114 // If any of the demanded bits are produced by the sign extension, we also
2115 // demand the input sign bit.
2116 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2118 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2119 KnownZero = KnownZero.lshr(ShAmt);
2120 KnownOne = KnownOne.lshr(ShAmt);
2122 // Handle the sign bits.
2123 APInt SignBit = APInt::getSignBit(BitWidth);
2124 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2126 if (KnownZero.intersects(SignBit)) {
2127 KnownZero |= HighBits; // New bits are known zero.
2128 } else if (KnownOne.intersects(SignBit)) {
2129 KnownOne |= HighBits; // New bits are known one.
2133 case ISD::SIGN_EXTEND_INREG: {
2134 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2135 unsigned EBits = EVT.getScalarType().getSizeInBits();
2137 // Sign extension. Compute the demanded bits in the result that are not
2138 // present in the input.
2139 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2141 APInt InSignBit = APInt::getSignBit(EBits);
2142 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2144 // If the sign extended bits are demanded, we know that the sign
2146 InSignBit = InSignBit.zext(BitWidth);
2147 if (NewBits.getBoolValue())
2148 InputDemandedBits |= InSignBit;
2150 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2151 KnownOne &= InputDemandedBits;
2152 KnownZero &= InputDemandedBits;
2154 // If the sign bit of the input is known set or clear, then we know the
2155 // top bits of the result.
2156 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2157 KnownZero |= NewBits;
2158 KnownOne &= ~NewBits;
2159 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2160 KnownOne |= NewBits;
2161 KnownZero &= ~NewBits;
2162 } else { // Input sign bit unknown
2163 KnownZero &= ~NewBits;
2164 KnownOne &= ~NewBits;
2169 case ISD::CTTZ_ZERO_UNDEF:
2171 case ISD::CTLZ_ZERO_UNDEF:
2173 unsigned LowBits = Log2_32(BitWidth)+1;
2174 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2175 KnownOne.clearAllBits();
2179 LoadSDNode *LD = cast<LoadSDNode>(Op);
2180 // If this is a ZEXTLoad and we are looking at the loaded value.
2181 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2182 EVT VT = LD->getMemoryVT();
2183 unsigned MemBits = VT.getScalarType().getSizeInBits();
2184 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2185 } else if (const MDNode *Ranges = LD->getRanges()) {
2186 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2190 case ISD::ZERO_EXTEND: {
2191 EVT InVT = Op.getOperand(0).getValueType();
2192 unsigned InBits = InVT.getScalarType().getSizeInBits();
2193 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2194 KnownZero = KnownZero.trunc(InBits);
2195 KnownOne = KnownOne.trunc(InBits);
2196 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2197 KnownZero = KnownZero.zext(BitWidth);
2198 KnownOne = KnownOne.zext(BitWidth);
2199 KnownZero |= NewBits;
2202 case ISD::SIGN_EXTEND: {
2203 EVT InVT = Op.getOperand(0).getValueType();
2204 unsigned InBits = InVT.getScalarType().getSizeInBits();
2205 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2207 KnownZero = KnownZero.trunc(InBits);
2208 KnownOne = KnownOne.trunc(InBits);
2209 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 // Note if the sign bit is known to be zero or one.
2212 bool SignBitKnownZero = KnownZero.isNegative();
2213 bool SignBitKnownOne = KnownOne.isNegative();
2215 KnownZero = KnownZero.zext(BitWidth);
2216 KnownOne = KnownOne.zext(BitWidth);
2218 // If the sign bit is known zero or one, the top bits match.
2219 if (SignBitKnownZero)
2220 KnownZero |= NewBits;
2221 else if (SignBitKnownOne)
2222 KnownOne |= NewBits;
2225 case ISD::ANY_EXTEND: {
2226 EVT InVT = Op.getOperand(0).getValueType();
2227 unsigned InBits = InVT.getScalarType().getSizeInBits();
2228 KnownZero = KnownZero.trunc(InBits);
2229 KnownOne = KnownOne.trunc(InBits);
2230 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2231 KnownZero = KnownZero.zext(BitWidth);
2232 KnownOne = KnownOne.zext(BitWidth);
2235 case ISD::TRUNCATE: {
2236 EVT InVT = Op.getOperand(0).getValueType();
2237 unsigned InBits = InVT.getScalarType().getSizeInBits();
2238 KnownZero = KnownZero.zext(InBits);
2239 KnownOne = KnownOne.zext(InBits);
2240 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2241 KnownZero = KnownZero.trunc(BitWidth);
2242 KnownOne = KnownOne.trunc(BitWidth);
2245 case ISD::AssertZext: {
2246 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2247 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2248 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2249 KnownZero |= (~InMask);
2250 KnownOne &= (~KnownZero);
2254 // All bits are zero except the low bit.
2255 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2259 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2260 // We know that the top bits of C-X are clear if X contains less bits
2261 // than C (i.e. no wrap-around can happen). For example, 20-X is
2262 // positive if we can prove that X is >= 0 and < 16.
2263 if (CLHS->getAPIntValue().isNonNegative()) {
2264 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2265 // NLZ can't be BitWidth with no sign bit
2266 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2267 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2269 // If all of the MaskV bits are known to be zero, then we know the
2270 // output top bits are zero, because we now know that the output is
2272 if ((KnownZero2 & MaskV) == MaskV) {
2273 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2274 // Top bits known zero.
2275 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2283 // Output known-0 bits are known if clear or set in both the low clear bits
2284 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2285 // low 3 bits clear.
2286 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2287 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2289 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2290 KnownZeroOut = std::min(KnownZeroOut,
2291 KnownZero2.countTrailingOnes());
2293 if (Op.getOpcode() == ISD::ADD) {
2294 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2298 // With ADDE, a carry bit may be added in, so we can only use this
2299 // information if we know (at least) that the low two bits are clear. We
2300 // then return to the caller that the low bit is unknown but that other bits
2302 if (KnownZeroOut >= 2) // ADDE
2303 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2307 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2308 const APInt &RA = Rem->getAPIntValue().abs();
2309 if (RA.isPowerOf2()) {
2310 APInt LowBits = RA - 1;
2311 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2313 // The low bits of the first operand are unchanged by the srem.
2314 KnownZero = KnownZero2 & LowBits;
2315 KnownOne = KnownOne2 & LowBits;
2317 // If the first operand is non-negative or has all low bits zero, then
2318 // the upper bits are all zero.
2319 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2320 KnownZero |= ~LowBits;
2322 // If the first operand is negative and not all low bits are zero, then
2323 // the upper bits are all one.
2324 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2325 KnownOne |= ~LowBits;
2326 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2331 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2332 const APInt &RA = Rem->getAPIntValue();
2333 if (RA.isPowerOf2()) {
2334 APInt LowBits = (RA - 1);
2335 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2337 // The upper bits are all zero, the lower ones are unchanged.
2338 KnownZero = KnownZero2 | ~LowBits;
2339 KnownOne = KnownOne2 & LowBits;
2344 // Since the result is less than or equal to either operand, any leading
2345 // zero bits in either operand must also exist in the result.
2346 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2347 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2349 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2350 KnownZero2.countLeadingOnes());
2351 KnownOne.clearAllBits();
2352 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2355 case ISD::EXTRACT_ELEMENT: {
2356 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2357 const unsigned Index =
2358 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2359 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2361 // Remove low part of known bits mask
2362 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2363 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2365 // Remove high part of known bit mask
2366 KnownZero = KnownZero.trunc(BitWidth);
2367 KnownOne = KnownOne.trunc(BitWidth);
2370 case ISD::FrameIndex:
2371 case ISD::TargetFrameIndex:
2372 if (unsigned Align = InferPtrAlignment(Op)) {
2373 // The low bits are known zero if the pointer is aligned.
2374 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2380 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2383 case ISD::INTRINSIC_WO_CHAIN:
2384 case ISD::INTRINSIC_W_CHAIN:
2385 case ISD::INTRINSIC_VOID:
2386 // Allow the target to implement this method for its nodes.
2387 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2391 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2394 /// ComputeNumSignBits - Return the number of times the sign bit of the
2395 /// register is replicated into the other bits. We know that at least 1 bit
2396 /// is always equal to the sign bit (itself), but other cases can give us
2397 /// information. For example, immediately after an "SRA X, 2", we know that
2398 /// the top 3 bits are all equal to each other, so we return 3.
2399 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2400 EVT VT = Op.getValueType();
2401 assert(VT.isInteger() && "Invalid VT!");
2402 unsigned VTBits = VT.getScalarType().getSizeInBits();
2404 unsigned FirstAnswer = 1;
2407 return 1; // Limit search depth.
2409 switch (Op.getOpcode()) {
2411 case ISD::AssertSext:
2412 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2413 return VTBits-Tmp+1;
2414 case ISD::AssertZext:
2415 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2418 case ISD::Constant: {
2419 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2420 return Val.getNumSignBits();
2423 case ISD::SIGN_EXTEND:
2425 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2426 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2428 case ISD::SIGN_EXTEND_INREG:
2429 // Max of the input and what this extends.
2431 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2434 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2435 return std::max(Tmp, Tmp2);
2438 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2439 // SRA X, C -> adds C sign bits.
2440 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2441 Tmp += C->getZExtValue();
2442 if (Tmp > VTBits) Tmp = VTBits;
2446 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2447 // shl destroys sign bits.
2448 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2449 if (C->getZExtValue() >= VTBits || // Bad shift.
2450 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2451 return Tmp - C->getZExtValue();
2456 case ISD::XOR: // NOT is handled here.
2457 // Logical binary ops preserve the number of sign bits at the worst.
2458 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2460 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2461 FirstAnswer = std::min(Tmp, Tmp2);
2462 // We computed what we know about the sign bits as our first
2463 // answer. Now proceed to the generic code that uses
2464 // computeKnownBits, and pick whichever answer is better.
2469 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2470 if (Tmp == 1) return 1; // Early out.
2471 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2472 return std::min(Tmp, Tmp2);
2480 if (Op.getResNo() != 1)
2482 // The boolean result conforms to getBooleanContents. Fall through.
2483 // If setcc returns 0/-1, all bits are sign bits.
2484 // We know that we have an integer-based boolean since these operations
2485 // are only available for integer.
2486 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2487 TargetLowering::ZeroOrNegativeOneBooleanContent)
2491 // If setcc returns 0/-1, all bits are sign bits.
2492 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2493 TargetLowering::ZeroOrNegativeOneBooleanContent)
2498 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2499 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2501 // Handle rotate right by N like a rotate left by 32-N.
2502 if (Op.getOpcode() == ISD::ROTR)
2503 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2505 // If we aren't rotating out all of the known-in sign bits, return the
2506 // number that are left. This handles rotl(sext(x), 1) for example.
2507 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2508 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2512 // Add can have at most one carry bit. Thus we know that the output
2513 // is, at worst, one more bit than the inputs.
2514 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2515 if (Tmp == 1) return 1; // Early out.
2517 // Special case decrementing a value (ADD X, -1):
2518 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2519 if (CRHS->isAllOnesValue()) {
2520 APInt KnownZero, KnownOne;
2521 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2523 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2525 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2528 // If we are subtracting one from a positive number, there is no carry
2529 // out of the result.
2530 if (KnownZero.isNegative())
2534 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2535 if (Tmp2 == 1) return 1;
2536 return std::min(Tmp, Tmp2)-1;
2539 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2540 if (Tmp2 == 1) return 1;
2543 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2544 if (CLHS->isNullValue()) {
2545 APInt KnownZero, KnownOne;
2546 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2547 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2549 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2552 // If the input is known to be positive (the sign bit is known clear),
2553 // the output of the NEG has the same number of sign bits as the input.
2554 if (KnownZero.isNegative())
2557 // Otherwise, we treat this like a SUB.
2560 // Sub can have at most one carry bit. Thus we know that the output
2561 // is, at worst, one more bit than the inputs.
2562 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2563 if (Tmp == 1) return 1; // Early out.
2564 return std::min(Tmp, Tmp2)-1;
2566 // FIXME: it's tricky to do anything useful for this, but it is an important
2567 // case for targets like X86.
2569 case ISD::EXTRACT_ELEMENT: {
2570 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2571 const int BitWidth = Op.getValueType().getSizeInBits();
2573 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2575 // Get reverse index (starting from 1), Op1 value indexes elements from
2576 // little end. Sign starts at big end.
2577 const int rIndex = Items - 1 -
2578 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2580 // If the sign portion ends in our element the substraction gives correct
2581 // result. Otherwise it gives either negative or > bitwidth result
2582 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2586 // If we are looking at the loaded value of the SDNode.
2587 if (Op.getResNo() == 0) {
2588 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2589 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2590 unsigned ExtType = LD->getExtensionType();
2593 case ISD::SEXTLOAD: // '17' bits known
2594 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2595 return VTBits-Tmp+1;
2596 case ISD::ZEXTLOAD: // '16' bits known
2597 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2603 // Allow the target to implement this method for its nodes.
2604 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2605 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2606 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2607 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2608 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2609 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2612 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2613 // use this information.
2614 APInt KnownZero, KnownOne;
2615 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2618 if (KnownZero.isNegative()) { // sign bit is 0
2620 } else if (KnownOne.isNegative()) { // sign bit is 1;
2627 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2628 // the number of identical bits in the top of the input value.
2630 Mask <<= Mask.getBitWidth()-VTBits;
2631 // Return # leading zeros. We use 'min' here in case Val was zero before
2632 // shifting. We don't want to return '64' as for an i32 "0".
2633 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2636 /// isBaseWithConstantOffset - Return true if the specified operand is an
2637 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2638 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2639 /// semantics as an ADD. This handles the equivalence:
2640 /// X|Cst == X+Cst iff X&Cst = 0.
2641 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2642 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2643 !isa<ConstantSDNode>(Op.getOperand(1)))
2646 if (Op.getOpcode() == ISD::OR &&
2647 !MaskedValueIsZero(Op.getOperand(0),
2648 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2655 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2656 // If we're told that NaNs won't happen, assume they won't.
2657 if (getTarget().Options.NoNaNsFPMath)
2660 // If the value is a constant, we can obviously see if it is a NaN or not.
2661 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2662 return !C->getValueAPF().isNaN();
2664 // TODO: Recognize more cases here.
2669 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2670 // If the value is a constant, we can obviously see if it is a zero or not.
2671 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2672 return !C->isZero();
2674 // TODO: Recognize more cases here.
2675 switch (Op.getOpcode()) {
2678 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2679 return !C->isNullValue();
2686 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2687 // Check the obvious case.
2688 if (A == B) return true;
2690 // For for negative and positive zero.
2691 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2692 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2693 if (CA->isZero() && CB->isZero()) return true;
2695 // Otherwise they may not be equal.
2699 /// getNode - Gets or creates the specified node.
2701 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2702 FoldingSetNodeID ID;
2703 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2705 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2706 return SDValue(E, 0);
2708 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2709 DL.getDebugLoc(), getVTList(VT));
2710 CSEMap.InsertNode(N, IP);
2713 return SDValue(N, 0);
2716 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2717 EVT VT, SDValue Operand) {
2718 // Constant fold unary operations with an integer constant operand. Even
2719 // opaque constant will be folded, because the folding of unary operations
2720 // doesn't create new constants with different values. Nevertheless, the
2721 // opaque flag is preserved during folding to prevent future folding with
2723 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2724 const APInt &Val = C->getAPIntValue();
2727 case ISD::SIGN_EXTEND:
2728 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2729 C->isTargetOpcode(), C->isOpaque());
2730 case ISD::ANY_EXTEND:
2731 case ISD::ZERO_EXTEND:
2733 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2734 C->isTargetOpcode(), C->isOpaque());
2735 case ISD::UINT_TO_FP:
2736 case ISD::SINT_TO_FP: {
2737 APFloat apf(EVTToAPFloatSemantics(VT),
2738 APInt::getNullValue(VT.getSizeInBits()));
2739 (void)apf.convertFromAPInt(Val,
2740 Opcode==ISD::SINT_TO_FP,
2741 APFloat::rmNearestTiesToEven);
2742 return getConstantFP(apf, VT);
2745 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2746 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2747 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2748 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2749 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2750 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2753 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2756 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2759 case ISD::CTLZ_ZERO_UNDEF:
2760 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2763 case ISD::CTTZ_ZERO_UNDEF:
2764 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2769 // Constant fold unary operations with a floating point constant operand.
2770 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2771 APFloat V = C->getValueAPF(); // make copy
2775 return getConstantFP(V, VT);
2778 return getConstantFP(V, VT);
2780 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2781 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2782 return getConstantFP(V, VT);
2786 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2787 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2788 return getConstantFP(V, VT);
2792 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2793 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2794 return getConstantFP(V, VT);
2797 case ISD::FP_EXTEND: {
2799 // This can return overflow, underflow, or inexact; we don't care.
2800 // FIXME need to be more flexible about rounding mode.
2801 (void)V.convert(EVTToAPFloatSemantics(VT),
2802 APFloat::rmNearestTiesToEven, &ignored);
2803 return getConstantFP(V, VT);
2805 case ISD::FP_TO_SINT:
2806 case ISD::FP_TO_UINT: {
2809 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2810 // FIXME need to be more flexible about rounding mode.
2811 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2812 Opcode==ISD::FP_TO_SINT,
2813 APFloat::rmTowardZero, &ignored);
2814 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2816 APInt api(VT.getSizeInBits(), x);
2817 return getConstant(api, VT);
2820 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2821 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2822 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2823 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2824 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2825 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2830 // Constant fold unary operations with a vector integer operand.
2831 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2832 if (BV->isConstant()) {
2835 // FIXME: Entirely reasonable to perform folding of other unary
2836 // operations here as the need arises.
2838 case ISD::UINT_TO_FP:
2839 case ISD::SINT_TO_FP: {
2840 SmallVector<SDValue, 8> Ops;
2841 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2842 SDValue OpN = BV->getOperand(i);
2843 // Let the above scalar folding handle the conversion of each
2845 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2849 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2855 unsigned OpOpcode = Operand.getNode()->getOpcode();
2857 case ISD::TokenFactor:
2858 case ISD::MERGE_VALUES:
2859 case ISD::CONCAT_VECTORS:
2860 return Operand; // Factor, merge or concat of one node? No need.
2861 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2862 case ISD::FP_EXTEND:
2863 assert(VT.isFloatingPoint() &&
2864 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2865 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2866 assert((!VT.isVector() ||
2867 VT.getVectorNumElements() ==
2868 Operand.getValueType().getVectorNumElements()) &&
2869 "Vector element count mismatch!");
2870 if (Operand.getOpcode() == ISD::UNDEF)
2871 return getUNDEF(VT);
2873 case ISD::SIGN_EXTEND:
2874 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2875 "Invalid SIGN_EXTEND!");
2876 if (Operand.getValueType() == VT) return Operand; // noop extension
2877 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2878 "Invalid sext node, dst < src!");
2879 assert((!VT.isVector() ||
2880 VT.getVectorNumElements() ==
2881 Operand.getValueType().getVectorNumElements()) &&
2882 "Vector element count mismatch!");
2883 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2884 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2885 else if (OpOpcode == ISD::UNDEF)
2886 // sext(undef) = 0, because the top bits will all be the same.
2887 return getConstant(0, VT);
2889 case ISD::ZERO_EXTEND:
2890 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2891 "Invalid ZERO_EXTEND!");
2892 if (Operand.getValueType() == VT) return Operand; // noop extension
2893 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2894 "Invalid zext node, dst < src!");
2895 assert((!VT.isVector() ||
2896 VT.getVectorNumElements() ==
2897 Operand.getValueType().getVectorNumElements()) &&
2898 "Vector element count mismatch!");
2899 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2900 return getNode(ISD::ZERO_EXTEND, DL, VT,
2901 Operand.getNode()->getOperand(0));
2902 else if (OpOpcode == ISD::UNDEF)
2903 // zext(undef) = 0, because the top bits will be zero.
2904 return getConstant(0, VT);
2906 case ISD::ANY_EXTEND:
2907 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2908 "Invalid ANY_EXTEND!");
2909 if (Operand.getValueType() == VT) return Operand; // noop extension
2910 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2911 "Invalid anyext node, dst < src!");
2912 assert((!VT.isVector() ||
2913 VT.getVectorNumElements() ==
2914 Operand.getValueType().getVectorNumElements()) &&
2915 "Vector element count mismatch!");
2917 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2918 OpOpcode == ISD::ANY_EXTEND)
2919 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2920 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2921 else if (OpOpcode == ISD::UNDEF)
2922 return getUNDEF(VT);
2924 // (ext (trunx x)) -> x
2925 if (OpOpcode == ISD::TRUNCATE) {
2926 SDValue OpOp = Operand.getNode()->getOperand(0);
2927 if (OpOp.getValueType() == VT)
2932 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2933 "Invalid TRUNCATE!");
2934 if (Operand.getValueType() == VT) return Operand; // noop truncate
2935 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2936 "Invalid truncate node, src < dst!");
2937 assert((!VT.isVector() ||
2938 VT.getVectorNumElements() ==
2939 Operand.getValueType().getVectorNumElements()) &&
2940 "Vector element count mismatch!");
2941 if (OpOpcode == ISD::TRUNCATE)
2942 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2943 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2944 OpOpcode == ISD::ANY_EXTEND) {
2945 // If the source is smaller than the dest, we still need an extend.
2946 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2947 .bitsLT(VT.getScalarType()))
2948 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2949 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2950 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2951 return Operand.getNode()->getOperand(0);
2953 if (OpOpcode == ISD::UNDEF)
2954 return getUNDEF(VT);
2957 // Basic sanity checking.
2958 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2959 && "Cannot BITCAST between types of different sizes!");
2960 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2961 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2962 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2963 if (OpOpcode == ISD::UNDEF)
2964 return getUNDEF(VT);
2966 case ISD::SCALAR_TO_VECTOR:
2967 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2968 (VT.getVectorElementType() == Operand.getValueType() ||
2969 (VT.getVectorElementType().isInteger() &&
2970 Operand.getValueType().isInteger() &&
2971 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2972 "Illegal SCALAR_TO_VECTOR node!");
2973 if (OpOpcode == ISD::UNDEF)
2974 return getUNDEF(VT);
2975 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2976 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2977 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2978 Operand.getConstantOperandVal(1) == 0 &&
2979 Operand.getOperand(0).getValueType() == VT)
2980 return Operand.getOperand(0);
2983 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2984 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2985 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2986 Operand.getNode()->getOperand(0));
2987 if (OpOpcode == ISD::FNEG) // --X -> X
2988 return Operand.getNode()->getOperand(0);
2991 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2992 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2997 SDVTList VTs = getVTList(VT);
2998 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2999 FoldingSetNodeID ID;
3000 SDValue Ops[1] = { Operand };
3001 AddNodeIDNode(ID, Opcode, VTs, Ops);
3003 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3004 return SDValue(E, 0);
3006 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3007 DL.getDebugLoc(), VTs, Operand);
3008 CSEMap.InsertNode(N, IP);
3010 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3011 DL.getDebugLoc(), VTs, Operand);
3015 return SDValue(N, 0);
3018 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3019 SDNode *Cst1, SDNode *Cst2) {
3020 // If the opcode is a target-specific ISD node, there's nothing we can
3021 // do here and the operand rules may not line up with the below, so
3023 if (Opcode >= ISD::BUILTIN_OP_END)
3026 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3027 SmallVector<SDValue, 4> Outputs;
3028 EVT SVT = VT.getScalarType();
3030 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3031 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3032 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3035 if (Scalar1 && Scalar2)
3036 // Scalar instruction.
3037 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3039 // For vectors extract each constant element into Inputs so we can constant
3040 // fold them individually.
3041 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3042 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3046 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3048 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3049 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3050 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3051 if (!V1 || !V2) // Not a constant, bail.
3054 if (V1->isOpaque() || V2->isOpaque())
3057 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3058 // FIXME: This is valid and could be handled by truncating the APInts.
3059 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3062 Inputs.push_back(std::make_pair(V1, V2));
3066 // We have a number of constant values, constant fold them element by element.
3067 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3068 const APInt &C1 = Inputs[I].first->getAPIntValue();
3069 const APInt &C2 = Inputs[I].second->getAPIntValue();
3073 Outputs.push_back(getConstant(C1 + C2, SVT));
3076 Outputs.push_back(getConstant(C1 - C2, SVT));
3079 Outputs.push_back(getConstant(C1 * C2, SVT));
3082 if (!C2.getBoolValue())
3084 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3087 if (!C2.getBoolValue())
3089 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3092 if (!C2.getBoolValue())
3094 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3097 if (!C2.getBoolValue())
3099 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3102 Outputs.push_back(getConstant(C1 & C2, SVT));
3105 Outputs.push_back(getConstant(C1 | C2, SVT));
3108 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3111 Outputs.push_back(getConstant(C1 << C2, SVT));
3114 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3117 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3120 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3123 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3130 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3131 "Expected a scalar or vector!"));
3133 // Handle the scalar case first.
3135 return Outputs.back();
3137 // We may have a vector type but a scalar result. Create a splat.
3138 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3140 // Build a big vector out of the scalar elements we generated.
3141 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3144 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3145 SDValue N2, bool nuw, bool nsw, bool exact) {
3146 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3147 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3150 case ISD::TokenFactor:
3151 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3152 N2.getValueType() == MVT::Other && "Invalid token factor!");
3153 // Fold trivial token factors.
3154 if (N1.getOpcode() == ISD::EntryToken) return N2;
3155 if (N2.getOpcode() == ISD::EntryToken) return N1;
3156 if (N1 == N2) return N1;
3158 case ISD::CONCAT_VECTORS:
3159 // Concat of UNDEFs is UNDEF.
3160 if (N1.getOpcode() == ISD::UNDEF &&
3161 N2.getOpcode() == ISD::UNDEF)
3162 return getUNDEF(VT);
3164 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3165 // one big BUILD_VECTOR.
3166 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3167 N2.getOpcode() == ISD::BUILD_VECTOR) {
3168 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3169 N1.getNode()->op_end());
3170 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3171 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3175 assert(VT.isInteger() && "This operator does not apply to FP types!");
3176 assert(N1.getValueType() == N2.getValueType() &&
3177 N1.getValueType() == VT && "Binary operator types must match!");
3178 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3179 // worth handling here.
3180 if (N2C && N2C->isNullValue())
3182 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3189 assert(VT.isInteger() && "This operator does not apply to FP types!");
3190 assert(N1.getValueType() == N2.getValueType() &&
3191 N1.getValueType() == VT && "Binary operator types must match!");
3192 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3193 // it's worth handling here.
3194 if (N2C && N2C->isNullValue())
3204 assert(VT.isInteger() && "This operator does not apply to FP types!");
3205 assert(N1.getValueType() == N2.getValueType() &&
3206 N1.getValueType() == VT && "Binary operator types must match!");
3213 if (getTarget().Options.UnsafeFPMath) {
3214 if (Opcode == ISD::FADD) {
3216 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3217 if (CFP->getValueAPF().isZero())
3220 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3221 if (CFP->getValueAPF().isZero())
3223 } else if (Opcode == ISD::FSUB) {
3225 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3226 if (CFP->getValueAPF().isZero())
3228 } else if (Opcode == ISD::FMUL) {
3229 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3232 // If the first operand isn't the constant, try the second
3234 CFP = dyn_cast<ConstantFPSDNode>(N2);
3241 return SDValue(CFP,0);
3243 if (CFP->isExactlyValue(1.0))
3248 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3249 assert(N1.getValueType() == N2.getValueType() &&
3250 N1.getValueType() == VT && "Binary operator types must match!");
3252 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3253 assert(N1.getValueType() == VT &&
3254 N1.getValueType().isFloatingPoint() &&
3255 N2.getValueType().isFloatingPoint() &&
3256 "Invalid FCOPYSIGN!");
3263 assert(VT == N1.getValueType() &&
3264 "Shift operators return type must be the same as their first arg");
3265 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3266 "Shifts only work on integers");
3267 assert((!VT.isVector() || VT == N2.getValueType()) &&
3268 "Vector shift amounts must be in the same as their first arg");
3269 // Verify that the shift amount VT is bit enough to hold valid shift
3270 // amounts. This catches things like trying to shift an i1024 value by an
3271 // i8, which is easy to fall into in generic code that uses
3272 // TLI.getShiftAmount().
3273 assert(N2.getValueType().getSizeInBits() >=
3274 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3275 "Invalid use of small shift amount with oversized value!");
3277 // Always fold shifts of i1 values so the code generator doesn't need to
3278 // handle them. Since we know the size of the shift has to be less than the
3279 // size of the value, the shift/rotate count is guaranteed to be zero.
3282 if (N2C && N2C->isNullValue())
3285 case ISD::FP_ROUND_INREG: {
3286 EVT EVT = cast<VTSDNode>(N2)->getVT();
3287 assert(VT == N1.getValueType() && "Not an inreg round!");
3288 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3289 "Cannot FP_ROUND_INREG integer types");
3290 assert(EVT.isVector() == VT.isVector() &&
3291 "FP_ROUND_INREG type should be vector iff the operand "
3293 assert((!EVT.isVector() ||
3294 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3295 "Vector element counts must match in FP_ROUND_INREG");
3296 assert(EVT.bitsLE(VT) && "Not rounding down!");
3298 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3302 assert(VT.isFloatingPoint() &&
3303 N1.getValueType().isFloatingPoint() &&
3304 VT.bitsLE(N1.getValueType()) &&
3305 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3306 if (N1.getValueType() == VT) return N1; // noop conversion.
3308 case ISD::AssertSext:
3309 case ISD::AssertZext: {
3310 EVT EVT = cast<VTSDNode>(N2)->getVT();
3311 assert(VT == N1.getValueType() && "Not an inreg extend!");
3312 assert(VT.isInteger() && EVT.isInteger() &&
3313 "Cannot *_EXTEND_INREG FP types");
3314 assert(!EVT.isVector() &&
3315 "AssertSExt/AssertZExt type should be the vector element type "
3316 "rather than the vector type!");
3317 assert(EVT.bitsLE(VT) && "Not extending!");
3318 if (VT == EVT) return N1; // noop assertion.
3321 case ISD::SIGN_EXTEND_INREG: {
3322 EVT EVT = cast<VTSDNode>(N2)->getVT();
3323 assert(VT == N1.getValueType() && "Not an inreg extend!");
3324 assert(VT.isInteger() && EVT.isInteger() &&
3325 "Cannot *_EXTEND_INREG FP types");
3326 assert(EVT.isVector() == VT.isVector() &&
3327 "SIGN_EXTEND_INREG type should be vector iff the operand "
3329 assert((!EVT.isVector() ||
3330 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3331 "Vector element counts must match in SIGN_EXTEND_INREG");
3332 assert(EVT.bitsLE(VT) && "Not extending!");
3333 if (EVT == VT) return N1; // Not actually extending
3336 APInt Val = N1C->getAPIntValue();
3337 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3338 Val <<= Val.getBitWidth()-FromBits;
3339 Val = Val.ashr(Val.getBitWidth()-FromBits);
3340 return getConstant(Val, VT);
3344 case ISD::EXTRACT_VECTOR_ELT:
3345 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3346 if (N1.getOpcode() == ISD::UNDEF)
3347 return getUNDEF(VT);
3349 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3350 // expanding copies of large vectors from registers.
3352 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3353 N1.getNumOperands() > 0) {
3355 N1.getOperand(0).getValueType().getVectorNumElements();
3356 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3357 N1.getOperand(N2C->getZExtValue() / Factor),
3358 getConstant(N2C->getZExtValue() % Factor,
3359 N2.getValueType()));
3362 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3363 // expanding large vector constants.
3364 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3365 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3367 if (VT != Elt.getValueType())
3368 // If the vector element type is not legal, the BUILD_VECTOR operands
3369 // are promoted and implicitly truncated, and the result implicitly
3370 // extended. Make that explicit here.
3371 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3376 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3377 // operations are lowered to scalars.
3378 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3379 // If the indices are the same, return the inserted element else
3380 // if the indices are known different, extract the element from
3381 // the original vector.
3382 SDValue N1Op2 = N1.getOperand(2);
3383 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3385 if (N1Op2C && N2C) {
3386 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3387 if (VT == N1.getOperand(1).getValueType())
3388 return N1.getOperand(1);
3390 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3393 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3397 case ISD::EXTRACT_ELEMENT:
3398 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3399 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3400 (N1.getValueType().isInteger() == VT.isInteger()) &&
3401 N1.getValueType() != VT &&
3402 "Wrong types for EXTRACT_ELEMENT!");
3404 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3405 // 64-bit integers into 32-bit parts. Instead of building the extract of
3406 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3407 if (N1.getOpcode() == ISD::BUILD_PAIR)
3408 return N1.getOperand(N2C->getZExtValue());
3410 // EXTRACT_ELEMENT of a constant int is also very common.
3411 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3412 unsigned ElementSize = VT.getSizeInBits();
3413 unsigned Shift = ElementSize * N2C->getZExtValue();
3414 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3415 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3418 case ISD::EXTRACT_SUBVECTOR: {
3420 if (VT.isSimple() && N1.getValueType().isSimple()) {
3421 assert(VT.isVector() && N1.getValueType().isVector() &&
3422 "Extract subvector VTs must be a vectors!");
3423 assert(VT.getVectorElementType() ==
3424 N1.getValueType().getVectorElementType() &&
3425 "Extract subvector VTs must have the same element type!");
3426 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3427 "Extract subvector must be from larger vector to smaller vector!");
3429 if (isa<ConstantSDNode>(Index.getNode())) {
3430 assert((VT.getVectorNumElements() +
3431 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3432 <= N1.getValueType().getVectorNumElements())
3433 && "Extract subvector overflow!");
3436 // Trivial extraction.
3437 if (VT.getSimpleVT() == N1.getSimpleValueType())
3444 // Perform trivial constant folding.
3446 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3449 // Canonicalize constant to RHS if commutative.
3450 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3451 std::swap(N1C, N2C);
3455 // Constant fold FP operations.
3456 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3457 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3458 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3460 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3461 // Canonicalize constant to RHS if commutative.
3462 std::swap(N1CFP, N2CFP);
3465 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3466 APFloat::opStatus s;
3469 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3470 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3471 return getConstantFP(V1, VT);
3474 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3475 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3476 return getConstantFP(V1, VT);
3479 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3480 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3481 return getConstantFP(V1, VT);
3484 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3485 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3486 s!=APFloat::opDivByZero)) {
3487 return getConstantFP(V1, VT);
3491 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3492 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3493 s!=APFloat::opDivByZero)) {
3494 return getConstantFP(V1, VT);
3497 case ISD::FCOPYSIGN:
3499 return getConstantFP(V1, VT);
3504 if (Opcode == ISD::FP_ROUND) {
3505 APFloat V = N1CFP->getValueAPF(); // make copy
3507 // This can return overflow, underflow, or inexact; we don't care.
3508 // FIXME need to be more flexible about rounding mode.
3509 (void)V.convert(EVTToAPFloatSemantics(VT),
3510 APFloat::rmNearestTiesToEven, &ignored);
3511 return getConstantFP(V, VT);
3515 // Canonicalize an UNDEF to the RHS, even over a constant.
3516 if (N1.getOpcode() == ISD::UNDEF) {
3517 if (isCommutativeBinOp(Opcode)) {
3521 case ISD::FP_ROUND_INREG:
3522 case ISD::SIGN_EXTEND_INREG:
3528 return N1; // fold op(undef, arg2) -> undef
3536 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3537 // For vectors, we can't easily build an all zero vector, just return
3544 // Fold a bunch of operators when the RHS is undef.
3545 if (N2.getOpcode() == ISD::UNDEF) {
3548 if (N1.getOpcode() == ISD::UNDEF)
3549 // Handle undef ^ undef -> 0 special case. This is a common
3551 return getConstant(0, VT);
3561 return N2; // fold op(arg1, undef) -> undef
3567 if (getTarget().Options.UnsafeFPMath)
3575 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3576 // For vectors, we can't easily build an all zero vector, just return
3581 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3582 // For vectors, we can't easily build an all one vector, just return
3590 // Memoize this node if possible.
3592 SDVTList VTs = getVTList(VT);
3593 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3594 if (VT != MVT::Glue) {
3595 SDValue Ops[] = {N1, N2};
3596 FoldingSetNodeID ID;
3597 AddNodeIDNode(ID, Opcode, VTs, Ops);
3599 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3601 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3602 return SDValue(E, 0);
3604 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3606 CSEMap.InsertNode(N, IP);
3609 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3613 return SDValue(N, 0);
3616 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3617 SDValue N1, SDValue N2, SDValue N3) {
3618 // Perform various simplifications.
3619 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3622 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3623 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3624 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3625 if (N1CFP && N2CFP && N3CFP) {
3626 APFloat V1 = N1CFP->getValueAPF();
3627 const APFloat &V2 = N2CFP->getValueAPF();
3628 const APFloat &V3 = N3CFP->getValueAPF();
3629 APFloat::opStatus s =
3630 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3631 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3632 return getConstantFP(V1, VT);
3636 case ISD::CONCAT_VECTORS:
3637 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3638 // one big BUILD_VECTOR.
3639 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3640 N2.getOpcode() == ISD::BUILD_VECTOR &&
3641 N3.getOpcode() == ISD::BUILD_VECTOR) {
3642 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3643 N1.getNode()->op_end());
3644 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3645 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3646 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3650 // Use FoldSetCC to simplify SETCC's.
3651 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3652 if (Simp.getNode()) return Simp;
3657 if (N1C->getZExtValue())
3658 return N2; // select true, X, Y -> X
3659 return N3; // select false, X, Y -> Y
3662 if (N2 == N3) return N2; // select C, X, X -> X
3664 case ISD::VECTOR_SHUFFLE:
3665 llvm_unreachable("should use getVectorShuffle constructor!");
3666 case ISD::INSERT_SUBVECTOR: {
3668 if (VT.isSimple() && N1.getValueType().isSimple()
3669 && N2.getValueType().isSimple()) {
3670 assert(VT.isVector() && N1.getValueType().isVector() &&
3671 N2.getValueType().isVector() &&
3672 "Insert subvector VTs must be a vectors");
3673 assert(VT == N1.getValueType() &&
3674 "Dest and insert subvector source types must match!");
3675 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3676 "Insert subvector must be from smaller vector to larger vector!");
3677 if (isa<ConstantSDNode>(Index.getNode())) {
3678 assert((N2.getValueType().getVectorNumElements() +
3679 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3680 <= VT.getVectorNumElements())
3681 && "Insert subvector overflow!");
3684 // Trivial insertion.
3685 if (VT.getSimpleVT() == N2.getSimpleValueType())
3691 // Fold bit_convert nodes from a type to themselves.
3692 if (N1.getValueType() == VT)
3697 // Memoize node if it doesn't produce a flag.
3699 SDVTList VTs = getVTList(VT);
3700 if (VT != MVT::Glue) {
3701 SDValue Ops[] = { N1, N2, N3 };
3702 FoldingSetNodeID ID;
3703 AddNodeIDNode(ID, Opcode, VTs, Ops);
3705 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3706 return SDValue(E, 0);
3708 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3709 DL.getDebugLoc(), VTs, N1, N2, N3);
3710 CSEMap.InsertNode(N, IP);
3712 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3713 DL.getDebugLoc(), VTs, N1, N2, N3);
3717 return SDValue(N, 0);
3720 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3721 SDValue N1, SDValue N2, SDValue N3,
3723 SDValue Ops[] = { N1, N2, N3, N4 };
3724 return getNode(Opcode, DL, VT, Ops);
3727 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3728 SDValue N1, SDValue N2, SDValue N3,
3729 SDValue N4, SDValue N5) {
3730 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3731 return getNode(Opcode, DL, VT, Ops);
3734 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3735 /// the incoming stack arguments to be loaded from the stack.
3736 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3737 SmallVector<SDValue, 8> ArgChains;
3739 // Include the original chain at the beginning of the list. When this is
3740 // used by target LowerCall hooks, this helps legalize find the
3741 // CALLSEQ_BEGIN node.
3742 ArgChains.push_back(Chain);
3744 // Add a chain value for each stack argument.
3745 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3746 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3747 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3748 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3749 if (FI->getIndex() < 0)
3750 ArgChains.push_back(SDValue(L, 1));
3752 // Build a tokenfactor for all the chains.
3753 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3756 /// getMemsetValue - Vectorized representation of the memset value
3758 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3760 assert(Value.getOpcode() != ISD::UNDEF);
3762 unsigned NumBits = VT.getScalarType().getSizeInBits();
3763 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3764 assert(C->getAPIntValue().getBitWidth() == 8);
3765 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3767 return DAG.getConstant(Val, VT);
3768 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3771 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3773 // Use a multiplication with 0x010101... to extend the input to the
3775 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3776 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3782 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3783 /// used when a memcpy is turned into a memset when the source is a constant
3785 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3786 const TargetLowering &TLI, StringRef Str) {
3787 // Handle vector with all elements zero.
3790 return DAG.getConstant(0, VT);
3791 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3792 return DAG.getConstantFP(0.0, VT);
3793 else if (VT.isVector()) {
3794 unsigned NumElts = VT.getVectorNumElements();
3795 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3796 return DAG.getNode(ISD::BITCAST, dl, VT,
3797 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3800 llvm_unreachable("Expected type!");
3803 assert(!VT.isVector() && "Can't handle vector type here!");
3804 unsigned NumVTBits = VT.getSizeInBits();
3805 unsigned NumVTBytes = NumVTBits / 8;
3806 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3808 APInt Val(NumVTBits, 0);
3809 if (TLI.isLittleEndian()) {
3810 for (unsigned i = 0; i != NumBytes; ++i)
3811 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3813 for (unsigned i = 0; i != NumBytes; ++i)
3814 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3817 // If the "cost" of materializing the integer immediate is less than the cost
3818 // of a load, then it is cost effective to turn the load into the immediate.
3819 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3820 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3821 return DAG.getConstant(Val, VT);
3822 return SDValue(nullptr, 0);
3825 /// getMemBasePlusOffset - Returns base and offset node for the
3827 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3828 SelectionDAG &DAG) {
3829 EVT VT = Base.getValueType();
3830 return DAG.getNode(ISD::ADD, dl,
3831 VT, Base, DAG.getConstant(Offset, VT));
3834 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3836 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3837 unsigned SrcDelta = 0;
3838 GlobalAddressSDNode *G = nullptr;
3839 if (Src.getOpcode() == ISD::GlobalAddress)
3840 G = cast<GlobalAddressSDNode>(Src);
3841 else if (Src.getOpcode() == ISD::ADD &&
3842 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3843 Src.getOperand(1).getOpcode() == ISD::Constant) {
3844 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3845 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3850 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3853 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3854 /// to replace the memset / memcpy. Return true if the number of memory ops
3855 /// is below the threshold. It returns the types of the sequence of
3856 /// memory ops to perform memset / memcpy by reference.
3857 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3858 unsigned Limit, uint64_t Size,
3859 unsigned DstAlign, unsigned SrcAlign,
3865 const TargetLowering &TLI) {
3866 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3867 "Expecting memcpy / memset source to meet alignment requirement!");
3868 // If 'SrcAlign' is zero, that means the memory operation does not need to
3869 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3870 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3871 // is the specified alignment of the memory operation. If it is zero, that
3872 // means it's possible to change the alignment of the destination.
3873 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3874 // not need to be loaded.
3875 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3876 IsMemset, ZeroMemset, MemcpyStrSrc,
3877 DAG.getMachineFunction());
3879 if (VT == MVT::Other) {
3881 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3882 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3883 VT = TLI.getPointerTy();
3885 switch (DstAlign & 7) {
3886 case 0: VT = MVT::i64; break;
3887 case 4: VT = MVT::i32; break;
3888 case 2: VT = MVT::i16; break;
3889 default: VT = MVT::i8; break;
3894 while (!TLI.isTypeLegal(LVT))
3895 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3896 assert(LVT.isInteger());
3902 unsigned NumMemOps = 0;
3904 unsigned VTSize = VT.getSizeInBits() / 8;
3905 while (VTSize > Size) {
3906 // For now, only use non-vector load / store's for the left-over pieces.
3911 if (VT.isVector() || VT.isFloatingPoint()) {
3912 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3913 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3914 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3916 else if (NewVT == MVT::i64 &&
3917 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3918 TLI.isSafeMemOpType(MVT::f64)) {
3919 // i64 is usually not legal on 32-bit targets, but f64 may be.
3927 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3928 if (NewVT == MVT::i8)
3930 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3932 NewVTSize = NewVT.getSizeInBits() / 8;
3934 // If the new VT cannot cover all of the remaining bits, then consider
3935 // issuing a (or a pair of) unaligned and overlapping load / store.
3936 // FIXME: Only does this for 64-bit or more since we don't have proper
3937 // cost model for unaligned load / store.
3940 if (NumMemOps && AllowOverlap &&
3941 VTSize >= 8 && NewVTSize < Size &&
3942 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3950 if (++NumMemOps > Limit)
3953 MemOps.push_back(VT);
3960 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3961 SDValue Chain, SDValue Dst,
3962 SDValue Src, uint64_t Size,
3963 unsigned Align, bool isVol,
3965 MachinePointerInfo DstPtrInfo,
3966 MachinePointerInfo SrcPtrInfo) {
3967 // Turn a memcpy of undef to nop.
3968 if (Src.getOpcode() == ISD::UNDEF)
3971 // Expand memcpy to a series of load and store ops if the size operand falls
3972 // below a certain threshold.
3973 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3974 // rather than maybe a humongous number of loads and stores.
3975 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3976 std::vector<EVT> MemOps;
3977 bool DstAlignCanChange = false;
3978 MachineFunction &MF = DAG.getMachineFunction();
3979 MachineFrameInfo *MFI = MF.getFrameInfo();
3980 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
3981 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3982 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3983 DstAlignCanChange = true;
3984 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3985 if (Align > SrcAlign)
3988 bool CopyFromStr = isMemSrcFromString(Src, Str);
3989 bool isZeroStr = CopyFromStr && Str.empty();
3990 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3992 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3993 (DstAlignCanChange ? 0 : Align),
3994 (isZeroStr ? 0 : SrcAlign),
3995 false, false, CopyFromStr, true, DAG, TLI))
3998 if (DstAlignCanChange) {
3999 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4000 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4002 // Don't promote to an alignment that would require dynamic stack
4004 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4005 if (!TRI->needsStackRealignment(MF))
4006 while (NewAlign > Align &&
4007 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4010 if (NewAlign > Align) {
4011 // Give the stack frame object a larger alignment if needed.
4012 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4013 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4018 SmallVector<SDValue, 8> OutChains;
4019 unsigned NumMemOps = MemOps.size();
4020 uint64_t SrcOff = 0, DstOff = 0;
4021 for (unsigned i = 0; i != NumMemOps; ++i) {
4023 unsigned VTSize = VT.getSizeInBits() / 8;
4024 SDValue Value, Store;
4026 if (VTSize > Size) {
4027 // Issuing an unaligned load / store pair that overlaps with the previous
4028 // pair. Adjust the offset accordingly.
4029 assert(i == NumMemOps-1 && i != 0);
4030 SrcOff -= VTSize - Size;
4031 DstOff -= VTSize - Size;
4035 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4036 // It's unlikely a store of a vector immediate can be done in a single
4037 // instruction. It would require a load from a constantpool first.
4038 // We only handle zero vectors here.
4039 // FIXME: Handle other cases where store of vector immediate is done in
4040 // a single instruction.
4041 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4042 if (Value.getNode())
4043 Store = DAG.getStore(Chain, dl, Value,
4044 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4045 DstPtrInfo.getWithOffset(DstOff), isVol,
4049 if (!Store.getNode()) {
4050 // The type might not be legal for the target. This should only happen
4051 // if the type is smaller than a legal type, as on PPC, so the right
4052 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4053 // to Load/Store if NVT==VT.
4054 // FIXME does the case above also need this?
4055 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4056 assert(NVT.bitsGE(VT));
4057 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4058 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4059 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4060 false, MinAlign(SrcAlign, SrcOff));
4061 Store = DAG.getTruncStore(Chain, dl, Value,
4062 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4063 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4066 OutChains.push_back(Store);
4072 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4075 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4076 SDValue Chain, SDValue Dst,
4077 SDValue Src, uint64_t Size,
4078 unsigned Align, bool isVol,
4080 MachinePointerInfo DstPtrInfo,
4081 MachinePointerInfo SrcPtrInfo) {
4082 // Turn a memmove of undef to nop.
4083 if (Src.getOpcode() == ISD::UNDEF)
4086 // Expand memmove to a series of load and store ops if the size operand falls
4087 // below a certain threshold.
4088 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4089 std::vector<EVT> MemOps;
4090 bool DstAlignCanChange = false;
4091 MachineFunction &MF = DAG.getMachineFunction();
4092 MachineFrameInfo *MFI = MF.getFrameInfo();
4093 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4094 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4095 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4096 DstAlignCanChange = true;
4097 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4098 if (Align > SrcAlign)
4100 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4102 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4103 (DstAlignCanChange ? 0 : Align), SrcAlign,
4104 false, false, false, false, DAG, TLI))
4107 if (DstAlignCanChange) {
4108 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4109 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4110 if (NewAlign > Align) {
4111 // Give the stack frame object a larger alignment if needed.
4112 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4113 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4118 uint64_t SrcOff = 0, DstOff = 0;
4119 SmallVector<SDValue, 8> LoadValues;
4120 SmallVector<SDValue, 8> LoadChains;
4121 SmallVector<SDValue, 8> OutChains;
4122 unsigned NumMemOps = MemOps.size();
4123 for (unsigned i = 0; i < NumMemOps; i++) {
4125 unsigned VTSize = VT.getSizeInBits() / 8;
4128 Value = DAG.getLoad(VT, dl, Chain,
4129 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4130 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4131 false, false, SrcAlign);
4132 LoadValues.push_back(Value);
4133 LoadChains.push_back(Value.getValue(1));
4136 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4138 for (unsigned i = 0; i < NumMemOps; i++) {
4140 unsigned VTSize = VT.getSizeInBits() / 8;
4143 Store = DAG.getStore(Chain, dl, LoadValues[i],
4144 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4145 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4146 OutChains.push_back(Store);
4150 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4153 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4156 /// \param DAG Selection DAG where lowered code is placed.
4157 /// \param dl Link to corresponding IR location.
4158 /// \param Chain Control flow dependency.
4159 /// \param Dst Pointer to destination memory location.
4160 /// \param Src Value of byte to write into the memory.
4161 /// \param Size Number of bytes to write.
4162 /// \param Align Alignment of the destination in bytes.
4163 /// \param isVol True if destination is volatile.
4164 /// \param DstPtrInfo IR information on the memory pointer.
4165 /// \returns New head in the control flow, if lowering was successful, empty
4166 /// SDValue otherwise.
4168 /// The function tries to replace 'llvm.memset' intrinsic with several store
4169 /// operations and value calculation code. This is usually profitable for small
4171 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4172 SDValue Chain, SDValue Dst,
4173 SDValue Src, uint64_t Size,
4174 unsigned Align, bool isVol,
4175 MachinePointerInfo DstPtrInfo) {
4176 // Turn a memset of undef to nop.
4177 if (Src.getOpcode() == ISD::UNDEF)
4180 // Expand memset to a series of load/store ops if the size operand
4181 // falls below a certain threshold.
4182 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4183 std::vector<EVT> MemOps;
4184 bool DstAlignCanChange = false;
4185 MachineFunction &MF = DAG.getMachineFunction();
4186 MachineFrameInfo *MFI = MF.getFrameInfo();
4187 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4188 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4189 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4190 DstAlignCanChange = true;
4192 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4193 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4194 Size, (DstAlignCanChange ? 0 : Align), 0,
4195 true, IsZeroVal, false, true, DAG, TLI))
4198 if (DstAlignCanChange) {
4199 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4200 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4201 if (NewAlign > Align) {
4202 // Give the stack frame object a larger alignment if needed.
4203 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4204 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4209 SmallVector<SDValue, 8> OutChains;
4210 uint64_t DstOff = 0;
4211 unsigned NumMemOps = MemOps.size();
4213 // Find the largest store and generate the bit pattern for it.
4214 EVT LargestVT = MemOps[0];
4215 for (unsigned i = 1; i < NumMemOps; i++)
4216 if (MemOps[i].bitsGT(LargestVT))
4217 LargestVT = MemOps[i];
4218 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4220 for (unsigned i = 0; i < NumMemOps; i++) {
4222 unsigned VTSize = VT.getSizeInBits() / 8;
4223 if (VTSize > Size) {
4224 // Issuing an unaligned load / store pair that overlaps with the previous
4225 // pair. Adjust the offset accordingly.
4226 assert(i == NumMemOps-1 && i != 0);
4227 DstOff -= VTSize - Size;
4230 // If this store is smaller than the largest store see whether we can get
4231 // the smaller value for free with a truncate.
4232 SDValue Value = MemSetValue;
4233 if (VT.bitsLT(LargestVT)) {
4234 if (!LargestVT.isVector() && !VT.isVector() &&
4235 TLI.isTruncateFree(LargestVT, VT))
4236 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4238 Value = getMemsetValue(Src, VT, DAG, dl);
4240 assert(Value.getValueType() == VT && "Value with wrong type.");
4241 SDValue Store = DAG.getStore(Chain, dl, Value,
4242 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4243 DstPtrInfo.getWithOffset(DstOff),
4244 isVol, false, Align);
4245 OutChains.push_back(Store);
4246 DstOff += VT.getSizeInBits() / 8;
4250 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4253 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4254 SDValue Src, SDValue Size,
4255 unsigned Align, bool isVol, bool AlwaysInline,
4256 MachinePointerInfo DstPtrInfo,
4257 MachinePointerInfo SrcPtrInfo) {
4258 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4260 // Check to see if we should lower the memcpy to loads and stores first.
4261 // For cases within the target-specified limits, this is the best choice.
4262 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4264 // Memcpy with size zero? Just return the original chain.
4265 if (ConstantSize->isNullValue())
4268 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4269 ConstantSize->getZExtValue(),Align,
4270 isVol, false, DstPtrInfo, SrcPtrInfo);
4271 if (Result.getNode())
4275 // Then check to see if we should lower the memcpy with target-specific
4276 // code. If the target chooses to do this, this is the next best.
4278 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4279 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4280 DstPtrInfo, SrcPtrInfo);
4281 if (Result.getNode())
4285 // If we really need inline code and the target declined to provide it,
4286 // use a (potentially long) sequence of loads and stores.
4288 assert(ConstantSize && "AlwaysInline requires a constant size!");
4289 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4290 ConstantSize->getZExtValue(), Align, isVol,
4291 true, DstPtrInfo, SrcPtrInfo);
4294 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4295 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4296 // respect volatile, so they may do things like read or write memory
4297 // beyond the given memory regions. But fixing this isn't easy, and most
4298 // people don't care.
4300 // Emit a library call.
4301 TargetLowering::ArgListTy Args;
4302 TargetLowering::ArgListEntry Entry;
4303 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4304 Entry.Node = Dst; Args.push_back(Entry);
4305 Entry.Node = Src; Args.push_back(Entry);
4306 Entry.Node = Size; Args.push_back(Entry);
4307 // FIXME: pass in SDLoc
4308 TargetLowering::CallLoweringInfo CLI(*this);
4309 CLI.setDebugLoc(dl).setChain(Chain)
4310 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4311 Type::getVoidTy(*getContext()),
4312 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4313 TLI->getPointerTy()), std::move(Args), 0)
4314 .setDiscardResult();
4315 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4317 return CallResult.second;
4320 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4321 SDValue Src, SDValue Size,
4322 unsigned Align, bool isVol,
4323 MachinePointerInfo DstPtrInfo,
4324 MachinePointerInfo SrcPtrInfo) {
4325 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4327 // Check to see if we should lower the memmove to loads and stores first.
4328 // For cases within the target-specified limits, this is the best choice.
4329 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4331 // Memmove with size zero? Just return the original chain.
4332 if (ConstantSize->isNullValue())
4336 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4337 ConstantSize->getZExtValue(), Align, isVol,
4338 false, DstPtrInfo, SrcPtrInfo);
4339 if (Result.getNode())
4343 // Then check to see if we should lower the memmove with target-specific
4344 // code. If the target chooses to do this, this is the next best.
4346 SDValue Result = TSI->EmitTargetCodeForMemmove(
4347 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4348 if (Result.getNode())
4352 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4353 // not be safe. See memcpy above for more details.
4355 // Emit a library call.
4356 TargetLowering::ArgListTy Args;
4357 TargetLowering::ArgListEntry Entry;
4358 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4359 Entry.Node = Dst; Args.push_back(Entry);
4360 Entry.Node = Src; Args.push_back(Entry);
4361 Entry.Node = Size; Args.push_back(Entry);
4362 // FIXME: pass in SDLoc
4363 TargetLowering::CallLoweringInfo CLI(*this);
4364 CLI.setDebugLoc(dl).setChain(Chain)
4365 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4366 Type::getVoidTy(*getContext()),
4367 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4368 TLI->getPointerTy()), std::move(Args), 0)
4369 .setDiscardResult();
4370 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4372 return CallResult.second;
4375 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4376 SDValue Src, SDValue Size,
4377 unsigned Align, bool isVol,
4378 MachinePointerInfo DstPtrInfo) {
4379 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4381 // Check to see if we should lower the memset to stores first.
4382 // For cases within the target-specified limits, this is the best choice.
4383 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4385 // Memset with size zero? Just return the original chain.
4386 if (ConstantSize->isNullValue())
4390 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4391 Align, isVol, DstPtrInfo);
4393 if (Result.getNode())
4397 // Then check to see if we should lower the memset with target-specific
4398 // code. If the target chooses to do this, this is the next best.
4400 SDValue Result = TSI->EmitTargetCodeForMemset(
4401 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4402 if (Result.getNode())
4406 // Emit a library call.
4407 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4408 TargetLowering::ArgListTy Args;
4409 TargetLowering::ArgListEntry Entry;
4410 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4411 Args.push_back(Entry);
4413 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4414 Args.push_back(Entry);
4416 Entry.Ty = IntPtrTy;
4417 Args.push_back(Entry);
4419 // FIXME: pass in SDLoc
4420 TargetLowering::CallLoweringInfo CLI(*this);
4421 CLI.setDebugLoc(dl).setChain(Chain)
4422 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4423 Type::getVoidTy(*getContext()),
4424 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4425 TLI->getPointerTy()), std::move(Args), 0)
4426 .setDiscardResult();
4428 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4429 return CallResult.second;
4432 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4433 SDVTList VTList, ArrayRef<SDValue> Ops,
4434 MachineMemOperand *MMO,
4435 AtomicOrdering SuccessOrdering,
4436 AtomicOrdering FailureOrdering,
4437 SynchronizationScope SynchScope) {
4438 FoldingSetNodeID ID;
4439 ID.AddInteger(MemVT.getRawBits());
4440 AddNodeIDNode(ID, Opcode, VTList, Ops);
4441 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4443 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4444 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4445 return SDValue(E, 0);
4448 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4449 // SDNode doesn't have access to it. This memory will be "leaked" when
4450 // the node is deallocated, but recovered when the allocator is released.
4451 // If the number of operands is less than 5 we use AtomicSDNode's internal
4453 unsigned NumOps = Ops.size();
4454 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4457 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4458 dl.getDebugLoc(), VTList, MemVT,
4459 Ops.data(), DynOps, NumOps, MMO,
4460 SuccessOrdering, FailureOrdering,
4462 CSEMap.InsertNode(N, IP);
4464 return SDValue(N, 0);
4467 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4468 SDVTList VTList, ArrayRef<SDValue> Ops,
4469 MachineMemOperand *MMO,
4470 AtomicOrdering Ordering,
4471 SynchronizationScope SynchScope) {
4472 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4473 Ordering, SynchScope);
4476 SDValue SelectionDAG::getAtomicCmpSwap(
4477 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4478 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4479 unsigned Alignment, AtomicOrdering SuccessOrdering,
4480 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4481 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4482 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4483 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4485 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4486 Alignment = getEVTAlignment(MemVT);
4488 MachineFunction &MF = getMachineFunction();
4490 // FIXME: Volatile isn't really correct; we should keep track of atomic
4491 // orderings in the memoperand.
4492 unsigned Flags = MachineMemOperand::MOVolatile;
4493 Flags |= MachineMemOperand::MOLoad;
4494 Flags |= MachineMemOperand::MOStore;
4496 MachineMemOperand *MMO =
4497 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4499 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4500 SuccessOrdering, FailureOrdering, SynchScope);
4503 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4504 SDVTList VTs, SDValue Chain, SDValue Ptr,
4505 SDValue Cmp, SDValue Swp,
4506 MachineMemOperand *MMO,
4507 AtomicOrdering SuccessOrdering,
4508 AtomicOrdering FailureOrdering,
4509 SynchronizationScope SynchScope) {
4510 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4511 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4512 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4514 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4515 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4516 SuccessOrdering, FailureOrdering, SynchScope);
4519 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4521 SDValue Ptr, SDValue Val,
4522 const Value* PtrVal,
4524 AtomicOrdering Ordering,
4525 SynchronizationScope SynchScope) {
4526 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4527 Alignment = getEVTAlignment(MemVT);
4529 MachineFunction &MF = getMachineFunction();
4530 // An atomic store does not load. An atomic load does not store.
4531 // (An atomicrmw obviously both loads and stores.)
4532 // For now, atomics are considered to be volatile always, and they are
4534 // FIXME: Volatile isn't really correct; we should keep track of atomic
4535 // orderings in the memoperand.
4536 unsigned Flags = MachineMemOperand::MOVolatile;
4537 if (Opcode != ISD::ATOMIC_STORE)
4538 Flags |= MachineMemOperand::MOLoad;
4539 if (Opcode != ISD::ATOMIC_LOAD)
4540 Flags |= MachineMemOperand::MOStore;
4542 MachineMemOperand *MMO =
4543 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4544 MemVT.getStoreSize(), Alignment);
4546 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4547 Ordering, SynchScope);
4550 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4552 SDValue Ptr, SDValue Val,
4553 MachineMemOperand *MMO,
4554 AtomicOrdering Ordering,
4555 SynchronizationScope SynchScope) {
4556 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4557 Opcode == ISD::ATOMIC_LOAD_SUB ||
4558 Opcode == ISD::ATOMIC_LOAD_AND ||
4559 Opcode == ISD::ATOMIC_LOAD_OR ||
4560 Opcode == ISD::ATOMIC_LOAD_XOR ||
4561 Opcode == ISD::ATOMIC_LOAD_NAND ||
4562 Opcode == ISD::ATOMIC_LOAD_MIN ||
4563 Opcode == ISD::ATOMIC_LOAD_MAX ||
4564 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4565 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4566 Opcode == ISD::ATOMIC_SWAP ||
4567 Opcode == ISD::ATOMIC_STORE) &&
4568 "Invalid Atomic Op");
4570 EVT VT = Val.getValueType();
4572 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4573 getVTList(VT, MVT::Other);
4574 SDValue Ops[] = {Chain, Ptr, Val};
4575 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4578 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4579 EVT VT, SDValue Chain,
4581 MachineMemOperand *MMO,
4582 AtomicOrdering Ordering,
4583 SynchronizationScope SynchScope) {
4584 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4586 SDVTList VTs = getVTList(VT, MVT::Other);
4587 SDValue Ops[] = {Chain, Ptr};
4588 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4591 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4592 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4593 if (Ops.size() == 1)
4596 SmallVector<EVT, 4> VTs;
4597 VTs.reserve(Ops.size());
4598 for (unsigned i = 0; i < Ops.size(); ++i)
4599 VTs.push_back(Ops[i].getValueType());
4600 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4604 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4605 ArrayRef<SDValue> Ops,
4606 EVT MemVT, MachinePointerInfo PtrInfo,
4607 unsigned Align, bool Vol,
4608 bool ReadMem, bool WriteMem, unsigned Size) {
4609 if (Align == 0) // Ensure that codegen never sees alignment 0
4610 Align = getEVTAlignment(MemVT);
4612 MachineFunction &MF = getMachineFunction();
4615 Flags |= MachineMemOperand::MOStore;
4617 Flags |= MachineMemOperand::MOLoad;
4619 Flags |= MachineMemOperand::MOVolatile;
4621 Size = MemVT.getStoreSize();
4622 MachineMemOperand *MMO =
4623 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4625 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4629 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4630 ArrayRef<SDValue> Ops, EVT MemVT,
4631 MachineMemOperand *MMO) {
4632 assert((Opcode == ISD::INTRINSIC_VOID ||
4633 Opcode == ISD::INTRINSIC_W_CHAIN ||
4634 Opcode == ISD::PREFETCH ||
4635 Opcode == ISD::LIFETIME_START ||
4636 Opcode == ISD::LIFETIME_END ||
4637 (Opcode <= INT_MAX &&
4638 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4639 "Opcode is not a memory-accessing opcode!");
4641 // Memoize the node unless it returns a flag.
4642 MemIntrinsicSDNode *N;
4643 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4644 FoldingSetNodeID ID;
4645 AddNodeIDNode(ID, Opcode, VTList, Ops);
4646 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4648 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4649 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4650 return SDValue(E, 0);
4653 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4654 dl.getDebugLoc(), VTList, Ops,
4656 CSEMap.InsertNode(N, IP);
4658 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4659 dl.getDebugLoc(), VTList, Ops,
4663 return SDValue(N, 0);
4666 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4667 /// MachinePointerInfo record from it. This is particularly useful because the
4668 /// code generator has many cases where it doesn't bother passing in a
4669 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4670 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4671 // If this is FI+Offset, we can model it.
4672 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4673 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4675 // If this is (FI+Offset1)+Offset2, we can model it.
4676 if (Ptr.getOpcode() != ISD::ADD ||
4677 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4678 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4679 return MachinePointerInfo();
4681 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4682 return MachinePointerInfo::getFixedStack(FI, Offset+
4683 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4686 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4687 /// MachinePointerInfo record from it. This is particularly useful because the
4688 /// code generator has many cases where it doesn't bother passing in a
4689 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4690 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4691 // If the 'Offset' value isn't a constant, we can't handle this.
4692 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4693 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4694 if (OffsetOp.getOpcode() == ISD::UNDEF)
4695 return InferPointerInfo(Ptr);
4696 return MachinePointerInfo();
4701 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4702 EVT VT, SDLoc dl, SDValue Chain,
4703 SDValue Ptr, SDValue Offset,
4704 MachinePointerInfo PtrInfo, EVT MemVT,
4705 bool isVolatile, bool isNonTemporal, bool isInvariant,
4706 unsigned Alignment, const AAMDNodes &AAInfo,
4707 const MDNode *Ranges) {
4708 assert(Chain.getValueType() == MVT::Other &&
4709 "Invalid chain type");
4710 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4711 Alignment = getEVTAlignment(VT);
4713 unsigned Flags = MachineMemOperand::MOLoad;
4715 Flags |= MachineMemOperand::MOVolatile;
4717 Flags |= MachineMemOperand::MONonTemporal;
4719 Flags |= MachineMemOperand::MOInvariant;
4721 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4723 if (PtrInfo.V.isNull())
4724 PtrInfo = InferPointerInfo(Ptr, Offset);
4726 MachineFunction &MF = getMachineFunction();
4727 MachineMemOperand *MMO =
4728 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4730 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4734 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4735 EVT VT, SDLoc dl, SDValue Chain,
4736 SDValue Ptr, SDValue Offset, EVT MemVT,
4737 MachineMemOperand *MMO) {
4739 ExtType = ISD::NON_EXTLOAD;
4740 } else if (ExtType == ISD::NON_EXTLOAD) {
4741 assert(VT == MemVT && "Non-extending load from different memory type!");
4744 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4745 "Should only be an extending load, not truncating!");
4746 assert(VT.isInteger() == MemVT.isInteger() &&
4747 "Cannot convert from FP to Int or Int -> FP!");
4748 assert(VT.isVector() == MemVT.isVector() &&
4749 "Cannot use an ext load to convert to or from a vector!");
4750 assert((!VT.isVector() ||
4751 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4752 "Cannot use an ext load to change the number of vector elements!");
4755 bool Indexed = AM != ISD::UNINDEXED;
4756 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4757 "Unindexed load with an offset!");
4759 SDVTList VTs = Indexed ?
4760 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4761 SDValue Ops[] = { Chain, Ptr, Offset };
4762 FoldingSetNodeID ID;
4763 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4764 ID.AddInteger(MemVT.getRawBits());
4765 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4766 MMO->isNonTemporal(),
4767 MMO->isInvariant()));
4768 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4770 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4771 cast<LoadSDNode>(E)->refineAlignment(MMO);
4772 return SDValue(E, 0);
4774 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4775 dl.getDebugLoc(), VTs, AM, ExtType,
4777 CSEMap.InsertNode(N, IP);
4779 return SDValue(N, 0);
4782 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4783 SDValue Chain, SDValue Ptr,
4784 MachinePointerInfo PtrInfo,
4785 bool isVolatile, bool isNonTemporal,
4786 bool isInvariant, unsigned Alignment,
4787 const AAMDNodes &AAInfo,
4788 const MDNode *Ranges) {
4789 SDValue Undef = getUNDEF(Ptr.getValueType());
4790 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4791 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4795 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4796 SDValue Chain, SDValue Ptr,
4797 MachineMemOperand *MMO) {
4798 SDValue Undef = getUNDEF(Ptr.getValueType());
4799 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4803 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4804 SDValue Chain, SDValue Ptr,
4805 MachinePointerInfo PtrInfo, EVT MemVT,
4806 bool isVolatile, bool isNonTemporal,
4807 bool isInvariant, unsigned Alignment,
4808 const AAMDNodes &AAInfo) {
4809 SDValue Undef = getUNDEF(Ptr.getValueType());
4810 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4811 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4816 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4817 SDValue Chain, SDValue Ptr, EVT MemVT,
4818 MachineMemOperand *MMO) {
4819 SDValue Undef = getUNDEF(Ptr.getValueType());
4820 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4825 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4826 SDValue Offset, ISD::MemIndexedMode AM) {
4827 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4828 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4829 "Load is already a indexed load!");
4830 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4831 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4832 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4833 false, LD->getAlignment());
4836 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4837 SDValue Ptr, MachinePointerInfo PtrInfo,
4838 bool isVolatile, bool isNonTemporal,
4839 unsigned Alignment, const AAMDNodes &AAInfo) {
4840 assert(Chain.getValueType() == MVT::Other &&
4841 "Invalid chain type");
4842 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4843 Alignment = getEVTAlignment(Val.getValueType());
4845 unsigned Flags = MachineMemOperand::MOStore;
4847 Flags |= MachineMemOperand::MOVolatile;
4849 Flags |= MachineMemOperand::MONonTemporal;
4851 if (PtrInfo.V.isNull())
4852 PtrInfo = InferPointerInfo(Ptr);
4854 MachineFunction &MF = getMachineFunction();
4855 MachineMemOperand *MMO =
4856 MF.getMachineMemOperand(PtrInfo, Flags,
4857 Val.getValueType().getStoreSize(), Alignment,
4860 return getStore(Chain, dl, Val, Ptr, MMO);
4863 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4864 SDValue Ptr, MachineMemOperand *MMO) {
4865 assert(Chain.getValueType() == MVT::Other &&
4866 "Invalid chain type");
4867 EVT VT = Val.getValueType();
4868 SDVTList VTs = getVTList(MVT::Other);
4869 SDValue Undef = getUNDEF(Ptr.getValueType());
4870 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4871 FoldingSetNodeID ID;
4872 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4873 ID.AddInteger(VT.getRawBits());
4874 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4875 MMO->isNonTemporal(), MMO->isInvariant()));
4876 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4878 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4879 cast<StoreSDNode>(E)->refineAlignment(MMO);
4880 return SDValue(E, 0);
4882 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4883 dl.getDebugLoc(), VTs,
4884 ISD::UNINDEXED, false, VT, MMO);
4885 CSEMap.InsertNode(N, IP);
4887 return SDValue(N, 0);
4890 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4891 SDValue Ptr, MachinePointerInfo PtrInfo,
4892 EVT SVT,bool isVolatile, bool isNonTemporal,
4894 const AAMDNodes &AAInfo) {
4895 assert(Chain.getValueType() == MVT::Other &&
4896 "Invalid chain type");
4897 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4898 Alignment = getEVTAlignment(SVT);
4900 unsigned Flags = MachineMemOperand::MOStore;
4902 Flags |= MachineMemOperand::MOVolatile;
4904 Flags |= MachineMemOperand::MONonTemporal;
4906 if (PtrInfo.V.isNull())
4907 PtrInfo = InferPointerInfo(Ptr);
4909 MachineFunction &MF = getMachineFunction();
4910 MachineMemOperand *MMO =
4911 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4914 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4917 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4918 SDValue Ptr, EVT SVT,
4919 MachineMemOperand *MMO) {
4920 EVT VT = Val.getValueType();
4922 assert(Chain.getValueType() == MVT::Other &&
4923 "Invalid chain type");
4925 return getStore(Chain, dl, Val, Ptr, MMO);
4927 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4928 "Should only be a truncating store, not extending!");
4929 assert(VT.isInteger() == SVT.isInteger() &&
4930 "Can't do FP-INT conversion!");
4931 assert(VT.isVector() == SVT.isVector() &&
4932 "Cannot use trunc store to convert to or from a vector!");
4933 assert((!VT.isVector() ||
4934 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4935 "Cannot use trunc store to change the number of vector elements!");
4937 SDVTList VTs = getVTList(MVT::Other);
4938 SDValue Undef = getUNDEF(Ptr.getValueType());
4939 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4940 FoldingSetNodeID ID;
4941 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4942 ID.AddInteger(SVT.getRawBits());
4943 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4944 MMO->isNonTemporal(), MMO->isInvariant()));
4945 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4947 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4948 cast<StoreSDNode>(E)->refineAlignment(MMO);
4949 return SDValue(E, 0);
4951 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4952 dl.getDebugLoc(), VTs,
4953 ISD::UNINDEXED, true, SVT, MMO);
4954 CSEMap.InsertNode(N, IP);
4956 return SDValue(N, 0);
4960 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4961 SDValue Offset, ISD::MemIndexedMode AM) {
4962 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4963 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4964 "Store is already a indexed store!");
4965 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4966 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4967 FoldingSetNodeID ID;
4968 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4969 ID.AddInteger(ST->getMemoryVT().getRawBits());
4970 ID.AddInteger(ST->getRawSubclassData());
4971 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4973 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4974 return SDValue(E, 0);
4976 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4977 dl.getDebugLoc(), VTs, AM,
4978 ST->isTruncatingStore(),
4980 ST->getMemOperand());
4981 CSEMap.InsertNode(N, IP);
4983 return SDValue(N, 0);
4987 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
4988 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
4989 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
4991 SDVTList VTs = getVTList(VT, MVT::Other);
4992 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
4993 FoldingSetNodeID ID;
4994 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
4995 ID.AddInteger(VT.getRawBits());
4996 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
4998 MMO->isNonTemporal(),
4999 MMO->isInvariant()));
5000 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5002 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5003 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5004 return SDValue(E, 0);
5006 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5007 dl.getDebugLoc(), Ops, 4, VTs,
5009 CSEMap.InsertNode(N, IP);
5011 return SDValue(N, 0);
5014 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5015 SDValue Ptr, SDValue Mask, EVT MemVT,
5016 MachineMemOperand *MMO, bool isTrunc) {
5017 assert(Chain.getValueType() == MVT::Other &&
5018 "Invalid chain type");
5019 EVT VT = Val.getValueType();
5020 SDVTList VTs = getVTList(MVT::Other);
5021 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5022 FoldingSetNodeID ID;
5023 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5024 ID.AddInteger(VT.getRawBits());
5025 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5026 MMO->isNonTemporal(), MMO->isInvariant()));
5027 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5029 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5030 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5031 return SDValue(E, 0);
5033 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5034 dl.getDebugLoc(), Ops, 4,
5035 VTs, isTrunc, MemVT, MMO);
5036 CSEMap.InsertNode(N, IP);
5038 return SDValue(N, 0);
5041 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5042 SDValue Chain, SDValue Ptr,
5045 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5046 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5049 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5050 ArrayRef<SDUse> Ops) {
5051 switch (Ops.size()) {
5052 case 0: return getNode(Opcode, DL, VT);
5053 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5054 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5055 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5059 // Copy from an SDUse array into an SDValue array for use with
5060 // the regular getNode logic.
5061 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5062 return getNode(Opcode, DL, VT, NewOps);
5065 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5066 ArrayRef<SDValue> Ops) {
5067 unsigned NumOps = Ops.size();
5069 case 0: return getNode(Opcode, DL, VT);
5070 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5071 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5072 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5078 case ISD::SELECT_CC: {
5079 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5080 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5081 "LHS and RHS of condition must have same type!");
5082 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5083 "True and False arms of SelectCC must have same type!");
5084 assert(Ops[2].getValueType() == VT &&
5085 "select_cc node must be of same type as true and false value!");
5089 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5090 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5091 "LHS/RHS of comparison should match types!");
5098 SDVTList VTs = getVTList(VT);
5100 if (VT != MVT::Glue) {
5101 FoldingSetNodeID ID;
5102 AddNodeIDNode(ID, Opcode, VTs, Ops);
5105 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5106 return SDValue(E, 0);
5108 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5110 CSEMap.InsertNode(N, IP);
5112 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5117 return SDValue(N, 0);
5120 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5121 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5122 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5125 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5126 ArrayRef<SDValue> Ops) {
5127 if (VTList.NumVTs == 1)
5128 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5132 // FIXME: figure out how to safely handle things like
5133 // int foo(int x) { return 1 << (x & 255); }
5134 // int bar() { return foo(256); }
5135 case ISD::SRA_PARTS:
5136 case ISD::SRL_PARTS:
5137 case ISD::SHL_PARTS:
5138 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5139 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5140 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5141 else if (N3.getOpcode() == ISD::AND)
5142 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5143 // If the and is only masking out bits that cannot effect the shift,
5144 // eliminate the and.
5145 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5146 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5147 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5153 // Memoize the node unless it returns a flag.
5155 unsigned NumOps = Ops.size();
5156 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5157 FoldingSetNodeID ID;
5158 AddNodeIDNode(ID, Opcode, VTList, Ops);
5160 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5161 return SDValue(E, 0);
5164 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5165 DL.getDebugLoc(), VTList, Ops[0]);
5166 } else if (NumOps == 2) {
5167 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5168 DL.getDebugLoc(), VTList, Ops[0],
5170 } else if (NumOps == 3) {
5171 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5172 DL.getDebugLoc(), VTList, Ops[0],
5175 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5178 CSEMap.InsertNode(N, IP);
5181 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5182 DL.getDebugLoc(), VTList, Ops[0]);
5183 } else if (NumOps == 2) {
5184 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5185 DL.getDebugLoc(), VTList, Ops[0],
5187 } else if (NumOps == 3) {
5188 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5189 DL.getDebugLoc(), VTList, Ops[0],
5192 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5197 return SDValue(N, 0);
5200 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5201 return getNode(Opcode, DL, VTList, None);
5204 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5206 SDValue Ops[] = { N1 };
5207 return getNode(Opcode, DL, VTList, Ops);
5210 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5211 SDValue N1, SDValue N2) {
5212 SDValue Ops[] = { N1, N2 };
5213 return getNode(Opcode, DL, VTList, Ops);
5216 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5217 SDValue N1, SDValue N2, SDValue N3) {
5218 SDValue Ops[] = { N1, N2, N3 };
5219 return getNode(Opcode, DL, VTList, Ops);
5222 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5223 SDValue N1, SDValue N2, SDValue N3,
5225 SDValue Ops[] = { N1, N2, N3, N4 };
5226 return getNode(Opcode, DL, VTList, Ops);
5229 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5230 SDValue N1, SDValue N2, SDValue N3,
5231 SDValue N4, SDValue N5) {
5232 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5233 return getNode(Opcode, DL, VTList, Ops);
5236 SDVTList SelectionDAG::getVTList(EVT VT) {
5237 return makeVTList(SDNode::getValueTypeList(VT), 1);
5240 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5241 FoldingSetNodeID ID;
5243 ID.AddInteger(VT1.getRawBits());
5244 ID.AddInteger(VT2.getRawBits());
5247 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5249 EVT *Array = Allocator.Allocate<EVT>(2);
5252 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5253 VTListMap.InsertNode(Result, IP);
5255 return Result->getSDVTList();
5258 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5259 FoldingSetNodeID ID;
5261 ID.AddInteger(VT1.getRawBits());
5262 ID.AddInteger(VT2.getRawBits());
5263 ID.AddInteger(VT3.getRawBits());
5266 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5268 EVT *Array = Allocator.Allocate<EVT>(3);
5272 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5273 VTListMap.InsertNode(Result, IP);
5275 return Result->getSDVTList();
5278 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5279 FoldingSetNodeID ID;
5281 ID.AddInteger(VT1.getRawBits());
5282 ID.AddInteger(VT2.getRawBits());
5283 ID.AddInteger(VT3.getRawBits());
5284 ID.AddInteger(VT4.getRawBits());
5287 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5289 EVT *Array = Allocator.Allocate<EVT>(4);
5294 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5295 VTListMap.InsertNode(Result, IP);
5297 return Result->getSDVTList();
5300 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5301 unsigned NumVTs = VTs.size();
5302 FoldingSetNodeID ID;
5303 ID.AddInteger(NumVTs);
5304 for (unsigned index = 0; index < NumVTs; index++) {
5305 ID.AddInteger(VTs[index].getRawBits());
5309 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5311 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5312 std::copy(VTs.begin(), VTs.end(), Array);
5313 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5314 VTListMap.InsertNode(Result, IP);
5316 return Result->getSDVTList();
5320 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5321 /// specified operands. If the resultant node already exists in the DAG,
5322 /// this does not modify the specified node, instead it returns the node that
5323 /// already exists. If the resultant node does not exist in the DAG, the
5324 /// input node is returned. As a degenerate case, if you specify the same
5325 /// input operands as the node already has, the input node is returned.
5326 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5327 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5329 // Check to see if there is no change.
5330 if (Op == N->getOperand(0)) return N;
5332 // See if the modified node already exists.
5333 void *InsertPos = nullptr;
5334 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5337 // Nope it doesn't. Remove the node from its current place in the maps.
5339 if (!RemoveNodeFromCSEMaps(N))
5340 InsertPos = nullptr;
5342 // Now we update the operands.
5343 N->OperandList[0].set(Op);
5345 // If this gets put into a CSE map, add it.
5346 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5350 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5351 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5353 // Check to see if there is no change.
5354 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5355 return N; // No operands changed, just return the input node.
5357 // See if the modified node already exists.
5358 void *InsertPos = nullptr;
5359 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5362 // Nope it doesn't. Remove the node from its current place in the maps.
5364 if (!RemoveNodeFromCSEMaps(N))
5365 InsertPos = nullptr;
5367 // Now we update the operands.
5368 if (N->OperandList[0] != Op1)
5369 N->OperandList[0].set(Op1);
5370 if (N->OperandList[1] != Op2)
5371 N->OperandList[1].set(Op2);
5373 // If this gets put into a CSE map, add it.
5374 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5378 SDNode *SelectionDAG::
5379 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5380 SDValue Ops[] = { Op1, Op2, Op3 };
5381 return UpdateNodeOperands(N, Ops);
5384 SDNode *SelectionDAG::
5385 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5386 SDValue Op3, SDValue Op4) {
5387 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5388 return UpdateNodeOperands(N, Ops);
5391 SDNode *SelectionDAG::
5392 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5393 SDValue Op3, SDValue Op4, SDValue Op5) {
5394 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5395 return UpdateNodeOperands(N, Ops);
5398 SDNode *SelectionDAG::
5399 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5400 unsigned NumOps = Ops.size();
5401 assert(N->getNumOperands() == NumOps &&
5402 "Update with wrong number of operands");
5404 // If no operands changed just return the input node.
5405 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5408 // See if the modified node already exists.
5409 void *InsertPos = nullptr;
5410 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5413 // Nope it doesn't. Remove the node from its current place in the maps.
5415 if (!RemoveNodeFromCSEMaps(N))
5416 InsertPos = nullptr;
5418 // Now we update the operands.
5419 for (unsigned i = 0; i != NumOps; ++i)
5420 if (N->OperandList[i] != Ops[i])
5421 N->OperandList[i].set(Ops[i]);
5423 // If this gets put into a CSE map, add it.
5424 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5428 /// DropOperands - Release the operands and set this node to have
5430 void SDNode::DropOperands() {
5431 // Unlike the code in MorphNodeTo that does this, we don't need to
5432 // watch for dead nodes here.
5433 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5439 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5442 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5444 SDVTList VTs = getVTList(VT);
5445 return SelectNodeTo(N, MachineOpc, VTs, None);
5448 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5449 EVT VT, SDValue Op1) {
5450 SDVTList VTs = getVTList(VT);
5451 SDValue Ops[] = { Op1 };
5452 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5455 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5456 EVT VT, SDValue Op1,
5458 SDVTList VTs = getVTList(VT);
5459 SDValue Ops[] = { Op1, Op2 };
5460 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5463 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5464 EVT VT, SDValue Op1,
5465 SDValue Op2, SDValue Op3) {
5466 SDVTList VTs = getVTList(VT);
5467 SDValue Ops[] = { Op1, Op2, Op3 };
5468 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5471 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5472 EVT VT, ArrayRef<SDValue> Ops) {
5473 SDVTList VTs = getVTList(VT);
5474 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5477 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5478 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5479 SDVTList VTs = getVTList(VT1, VT2);
5480 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5483 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5485 SDVTList VTs = getVTList(VT1, VT2);
5486 return SelectNodeTo(N, MachineOpc, VTs, None);
5489 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5490 EVT VT1, EVT VT2, EVT VT3,
5491 ArrayRef<SDValue> Ops) {
5492 SDVTList VTs = getVTList(VT1, VT2, VT3);
5493 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5496 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5497 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5498 ArrayRef<SDValue> Ops) {
5499 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5500 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5503 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5506 SDVTList VTs = getVTList(VT1, VT2);
5507 SDValue Ops[] = { Op1 };
5508 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5511 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5513 SDValue Op1, SDValue Op2) {
5514 SDVTList VTs = getVTList(VT1, VT2);
5515 SDValue Ops[] = { Op1, Op2 };
5516 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5519 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5521 SDValue Op1, SDValue Op2,
5523 SDVTList VTs = getVTList(VT1, VT2);
5524 SDValue Ops[] = { Op1, Op2, Op3 };
5525 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5528 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5529 EVT VT1, EVT VT2, EVT VT3,
5530 SDValue Op1, SDValue Op2,
5532 SDVTList VTs = getVTList(VT1, VT2, VT3);
5533 SDValue Ops[] = { Op1, Op2, Op3 };
5534 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5537 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5538 SDVTList VTs,ArrayRef<SDValue> Ops) {
5539 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5540 // Reset the NodeID to -1.
5545 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5546 /// the line number information on the merged node since it is not possible to
5547 /// preserve the information that operation is associated with multiple lines.
5548 /// This will make the debugger working better at -O0, were there is a higher
5549 /// probability having other instructions associated with that line.
5551 /// For IROrder, we keep the smaller of the two
5552 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5553 DebugLoc NLoc = N->getDebugLoc();
5554 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5555 (OLoc.getDebugLoc() != NLoc)) {
5556 N->setDebugLoc(DebugLoc());
5558 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5559 N->setIROrder(Order);
5563 /// MorphNodeTo - This *mutates* the specified node to have the specified
5564 /// return type, opcode, and operands.
5566 /// Note that MorphNodeTo returns the resultant node. If there is already a
5567 /// node of the specified opcode and operands, it returns that node instead of
5568 /// the current one. Note that the SDLoc need not be the same.
5570 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5571 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5572 /// node, and because it doesn't require CSE recalculation for any of
5573 /// the node's users.
5575 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5576 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5577 /// the legalizer which maintain worklists that would need to be updated when
5578 /// deleting things.
5579 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5580 SDVTList VTs, ArrayRef<SDValue> Ops) {
5581 unsigned NumOps = Ops.size();
5582 // If an identical node already exists, use it.
5584 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5585 FoldingSetNodeID ID;
5586 AddNodeIDNode(ID, Opc, VTs, Ops);
5587 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5588 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5591 if (!RemoveNodeFromCSEMaps(N))
5594 // Start the morphing.
5596 N->ValueList = VTs.VTs;
5597 N->NumValues = VTs.NumVTs;
5599 // Clear the operands list, updating used nodes to remove this from their
5600 // use list. Keep track of any operands that become dead as a result.
5601 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5602 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5604 SDNode *Used = Use.getNode();
5606 if (Used->use_empty())
5607 DeadNodeSet.insert(Used);
5610 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5611 // Initialize the memory references information.
5612 MN->setMemRefs(nullptr, nullptr);
5613 // If NumOps is larger than the # of operands we can have in a
5614 // MachineSDNode, reallocate the operand list.
5615 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5616 if (MN->OperandsNeedDelete)
5617 delete[] MN->OperandList;
5618 if (NumOps > array_lengthof(MN->LocalOperands))
5619 // We're creating a final node that will live unmorphed for the
5620 // remainder of the current SelectionDAG iteration, so we can allocate
5621 // the operands directly out of a pool with no recycling metadata.
5622 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5623 Ops.data(), NumOps);
5625 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5626 MN->OperandsNeedDelete = false;
5628 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5630 // If NumOps is larger than the # of operands we currently have, reallocate
5631 // the operand list.
5632 if (NumOps > N->NumOperands) {
5633 if (N->OperandsNeedDelete)
5634 delete[] N->OperandList;
5635 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5636 N->OperandsNeedDelete = true;
5638 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5641 // Delete any nodes that are still dead after adding the uses for the
5643 if (!DeadNodeSet.empty()) {
5644 SmallVector<SDNode *, 16> DeadNodes;
5645 for (SDNode *N : DeadNodeSet)
5647 DeadNodes.push_back(N);
5648 RemoveDeadNodes(DeadNodes);
5652 CSEMap.InsertNode(N, IP); // Memoize the new node.
5657 /// getMachineNode - These are used for target selectors to create a new node
5658 /// with specified return type(s), MachineInstr opcode, and operands.
5660 /// Note that getMachineNode returns the resultant node. If there is already a
5661 /// node of the specified opcode and operands, it returns that node instead of
5662 /// the current one.
5664 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5665 SDVTList VTs = getVTList(VT);
5666 return getMachineNode(Opcode, dl, VTs, None);
5670 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5671 SDVTList VTs = getVTList(VT);
5672 SDValue Ops[] = { Op1 };
5673 return getMachineNode(Opcode, dl, VTs, Ops);
5677 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5678 SDValue Op1, SDValue Op2) {
5679 SDVTList VTs = getVTList(VT);
5680 SDValue Ops[] = { Op1, Op2 };
5681 return getMachineNode(Opcode, dl, VTs, Ops);
5685 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5686 SDValue Op1, SDValue Op2, SDValue Op3) {
5687 SDVTList VTs = getVTList(VT);
5688 SDValue Ops[] = { Op1, Op2, Op3 };
5689 return getMachineNode(Opcode, dl, VTs, Ops);
5693 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5694 ArrayRef<SDValue> Ops) {
5695 SDVTList VTs = getVTList(VT);
5696 return getMachineNode(Opcode, dl, VTs, Ops);
5700 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5701 SDVTList VTs = getVTList(VT1, VT2);
5702 return getMachineNode(Opcode, dl, VTs, None);
5706 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5707 EVT VT1, EVT VT2, SDValue Op1) {
5708 SDVTList VTs = getVTList(VT1, VT2);
5709 SDValue Ops[] = { Op1 };
5710 return getMachineNode(Opcode, dl, VTs, Ops);
5714 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5715 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5716 SDVTList VTs = getVTList(VT1, VT2);
5717 SDValue Ops[] = { Op1, Op2 };
5718 return getMachineNode(Opcode, dl, VTs, Ops);
5722 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5723 EVT VT1, EVT VT2, SDValue Op1,
5724 SDValue Op2, SDValue Op3) {
5725 SDVTList VTs = getVTList(VT1, VT2);
5726 SDValue Ops[] = { Op1, Op2, Op3 };
5727 return getMachineNode(Opcode, dl, VTs, Ops);
5731 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5733 ArrayRef<SDValue> Ops) {
5734 SDVTList VTs = getVTList(VT1, VT2);
5735 return getMachineNode(Opcode, dl, VTs, Ops);
5739 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5740 EVT VT1, EVT VT2, EVT VT3,
5741 SDValue Op1, SDValue Op2) {
5742 SDVTList VTs = getVTList(VT1, VT2, VT3);
5743 SDValue Ops[] = { Op1, Op2 };
5744 return getMachineNode(Opcode, dl, VTs, Ops);
5748 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5749 EVT VT1, EVT VT2, EVT VT3,
5750 SDValue Op1, SDValue Op2, SDValue Op3) {
5751 SDVTList VTs = getVTList(VT1, VT2, VT3);
5752 SDValue Ops[] = { Op1, Op2, Op3 };
5753 return getMachineNode(Opcode, dl, VTs, Ops);
5757 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5758 EVT VT1, EVT VT2, EVT VT3,
5759 ArrayRef<SDValue> Ops) {
5760 SDVTList VTs = getVTList(VT1, VT2, VT3);
5761 return getMachineNode(Opcode, dl, VTs, Ops);
5765 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5766 EVT VT2, EVT VT3, EVT VT4,
5767 ArrayRef<SDValue> Ops) {
5768 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5769 return getMachineNode(Opcode, dl, VTs, Ops);
5773 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5774 ArrayRef<EVT> ResultTys,
5775 ArrayRef<SDValue> Ops) {
5776 SDVTList VTs = getVTList(ResultTys);
5777 return getMachineNode(Opcode, dl, VTs, Ops);
5781 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5782 ArrayRef<SDValue> OpsArray) {
5783 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5786 const SDValue *Ops = OpsArray.data();
5787 unsigned NumOps = OpsArray.size();
5790 FoldingSetNodeID ID;
5791 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5793 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5794 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5798 // Allocate a new MachineSDNode.
5799 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5800 DL.getDebugLoc(), VTs);
5802 // Initialize the operands list.
5803 if (NumOps > array_lengthof(N->LocalOperands))
5804 // We're creating a final node that will live unmorphed for the
5805 // remainder of the current SelectionDAG iteration, so we can allocate
5806 // the operands directly out of a pool with no recycling metadata.
5807 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5810 N->InitOperands(N->LocalOperands, Ops, NumOps);
5811 N->OperandsNeedDelete = false;
5814 CSEMap.InsertNode(N, IP);
5820 /// getTargetExtractSubreg - A convenience function for creating
5821 /// TargetOpcode::EXTRACT_SUBREG nodes.
5823 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5825 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5826 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5827 VT, Operand, SRIdxVal);
5828 return SDValue(Subreg, 0);
5831 /// getTargetInsertSubreg - A convenience function for creating
5832 /// TargetOpcode::INSERT_SUBREG nodes.
5834 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5835 SDValue Operand, SDValue Subreg) {
5836 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5837 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5838 VT, Operand, Subreg, SRIdxVal);
5839 return SDValue(Result, 0);
5842 /// getNodeIfExists - Get the specified node if it's already available, or
5843 /// else return NULL.
5844 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5845 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5847 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5848 FoldingSetNodeID ID;
5849 AddNodeIDNode(ID, Opcode, VTList, Ops);
5850 if (isBinOpWithFlags(Opcode))
5851 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5853 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5859 /// getDbgValue - Creates a SDDbgValue node.
5862 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5863 unsigned R, bool IsIndirect, uint64_t Off,
5864 DebugLoc DL, unsigned O) {
5865 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5869 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5870 const Value *C, uint64_t Off,
5871 DebugLoc DL, unsigned O) {
5872 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5876 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5877 unsigned FI, uint64_t Off,
5878 DebugLoc DL, unsigned O) {
5879 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5884 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5885 /// pointed to by a use iterator is deleted, increment the use iterator
5886 /// so that it doesn't dangle.
5888 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5889 SDNode::use_iterator &UI;
5890 SDNode::use_iterator &UE;
5892 void NodeDeleted(SDNode *N, SDNode *E) override {
5893 // Increment the iterator as needed.
5894 while (UI != UE && N == *UI)
5899 RAUWUpdateListener(SelectionDAG &d,
5900 SDNode::use_iterator &ui,
5901 SDNode::use_iterator &ue)
5902 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5907 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5908 /// This can cause recursive merging of nodes in the DAG.
5910 /// This version assumes From has a single result value.
5912 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5913 SDNode *From = FromN.getNode();
5914 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5915 "Cannot replace with this method!");
5916 assert(From != To.getNode() && "Cannot replace uses of with self");
5918 // Iterate over all the existing uses of From. New uses will be added
5919 // to the beginning of the use list, which we avoid visiting.
5920 // This specifically avoids visiting uses of From that arise while the
5921 // replacement is happening, because any such uses would be the result
5922 // of CSE: If an existing node looks like From after one of its operands
5923 // is replaced by To, we don't want to replace of all its users with To
5924 // too. See PR3018 for more info.
5925 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5926 RAUWUpdateListener Listener(*this, UI, UE);
5930 // This node is about to morph, remove its old self from the CSE maps.
5931 RemoveNodeFromCSEMaps(User);
5933 // A user can appear in a use list multiple times, and when this
5934 // happens the uses are usually next to each other in the list.
5935 // To help reduce the number of CSE recomputations, process all
5936 // the uses of this user that we can find this way.
5938 SDUse &Use = UI.getUse();
5941 } while (UI != UE && *UI == User);
5943 // Now that we have modified User, add it back to the CSE maps. If it
5944 // already exists there, recursively merge the results together.
5945 AddModifiedNodeToCSEMaps(User);
5948 // If we just RAUW'd the root, take note.
5949 if (FromN == getRoot())
5953 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5954 /// This can cause recursive merging of nodes in the DAG.
5956 /// This version assumes that for each value of From, there is a
5957 /// corresponding value in To in the same position with the same type.
5959 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5961 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5962 assert((!From->hasAnyUseOfValue(i) ||
5963 From->getValueType(i) == To->getValueType(i)) &&
5964 "Cannot use this version of ReplaceAllUsesWith!");
5967 // Handle the trivial case.
5971 // Iterate over just the existing users of From. See the comments in
5972 // the ReplaceAllUsesWith above.
5973 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5974 RAUWUpdateListener Listener(*this, UI, UE);
5978 // This node is about to morph, remove its old self from the CSE maps.
5979 RemoveNodeFromCSEMaps(User);
5981 // A user can appear in a use list multiple times, and when this
5982 // happens the uses are usually next to each other in the list.
5983 // To help reduce the number of CSE recomputations, process all
5984 // the uses of this user that we can find this way.
5986 SDUse &Use = UI.getUse();
5989 } while (UI != UE && *UI == User);
5991 // Now that we have modified User, add it back to the CSE maps. If it
5992 // already exists there, recursively merge the results together.
5993 AddModifiedNodeToCSEMaps(User);
5996 // If we just RAUW'd the root, take note.
5997 if (From == getRoot().getNode())
5998 setRoot(SDValue(To, getRoot().getResNo()));
6001 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6002 /// This can cause recursive merging of nodes in the DAG.
6004 /// This version can replace From with any result values. To must match the
6005 /// number and types of values returned by From.
6006 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6007 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6008 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6010 // Iterate over just the existing users of From. See the comments in
6011 // the ReplaceAllUsesWith above.
6012 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6013 RAUWUpdateListener Listener(*this, UI, UE);
6017 // This node is about to morph, remove its old self from the CSE maps.
6018 RemoveNodeFromCSEMaps(User);
6020 // A user can appear in a use list multiple times, and when this
6021 // happens the uses are usually next to each other in the list.
6022 // To help reduce the number of CSE recomputations, process all
6023 // the uses of this user that we can find this way.
6025 SDUse &Use = UI.getUse();
6026 const SDValue &ToOp = To[Use.getResNo()];
6029 } while (UI != UE && *UI == User);
6031 // Now that we have modified User, add it back to the CSE maps. If it
6032 // already exists there, recursively merge the results together.
6033 AddModifiedNodeToCSEMaps(User);
6036 // If we just RAUW'd the root, take note.
6037 if (From == getRoot().getNode())
6038 setRoot(SDValue(To[getRoot().getResNo()]));
6041 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6042 /// uses of other values produced by From.getNode() alone. The Deleted
6043 /// vector is handled the same way as for ReplaceAllUsesWith.
6044 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6045 // Handle the really simple, really trivial case efficiently.
6046 if (From == To) return;
6048 // Handle the simple, trivial, case efficiently.
6049 if (From.getNode()->getNumValues() == 1) {
6050 ReplaceAllUsesWith(From, To);
6054 // Iterate over just the existing users of From. See the comments in
6055 // the ReplaceAllUsesWith above.
6056 SDNode::use_iterator UI = From.getNode()->use_begin(),
6057 UE = From.getNode()->use_end();
6058 RAUWUpdateListener Listener(*this, UI, UE);
6061 bool UserRemovedFromCSEMaps = false;
6063 // A user can appear in a use list multiple times, and when this
6064 // happens the uses are usually next to each other in the list.
6065 // To help reduce the number of CSE recomputations, process all
6066 // the uses of this user that we can find this way.
6068 SDUse &Use = UI.getUse();
6070 // Skip uses of different values from the same node.
6071 if (Use.getResNo() != From.getResNo()) {
6076 // If this node hasn't been modified yet, it's still in the CSE maps,
6077 // so remove its old self from the CSE maps.
6078 if (!UserRemovedFromCSEMaps) {
6079 RemoveNodeFromCSEMaps(User);
6080 UserRemovedFromCSEMaps = true;
6085 } while (UI != UE && *UI == User);
6087 // We are iterating over all uses of the From node, so if a use
6088 // doesn't use the specific value, no changes are made.
6089 if (!UserRemovedFromCSEMaps)
6092 // Now that we have modified User, add it back to the CSE maps. If it
6093 // already exists there, recursively merge the results together.
6094 AddModifiedNodeToCSEMaps(User);
6097 // If we just RAUW'd the root, take note.
6098 if (From == getRoot())
6103 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6104 /// to record information about a use.
6111 /// operator< - Sort Memos by User.
6112 bool operator<(const UseMemo &L, const UseMemo &R) {
6113 return (intptr_t)L.User < (intptr_t)R.User;
6117 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6118 /// uses of other values produced by From.getNode() alone. The same value
6119 /// may appear in both the From and To list. The Deleted vector is
6120 /// handled the same way as for ReplaceAllUsesWith.
6121 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6124 // Handle the simple, trivial case efficiently.
6126 return ReplaceAllUsesOfValueWith(*From, *To);
6128 // Read up all the uses and make records of them. This helps
6129 // processing new uses that are introduced during the
6130 // replacement process.
6131 SmallVector<UseMemo, 4> Uses;
6132 for (unsigned i = 0; i != Num; ++i) {
6133 unsigned FromResNo = From[i].getResNo();
6134 SDNode *FromNode = From[i].getNode();
6135 for (SDNode::use_iterator UI = FromNode->use_begin(),
6136 E = FromNode->use_end(); UI != E; ++UI) {
6137 SDUse &Use = UI.getUse();
6138 if (Use.getResNo() == FromResNo) {
6139 UseMemo Memo = { *UI, i, &Use };
6140 Uses.push_back(Memo);
6145 // Sort the uses, so that all the uses from a given User are together.
6146 std::sort(Uses.begin(), Uses.end());
6148 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6149 UseIndex != UseIndexEnd; ) {
6150 // We know that this user uses some value of From. If it is the right
6151 // value, update it.
6152 SDNode *User = Uses[UseIndex].User;
6154 // This node is about to morph, remove its old self from the CSE maps.
6155 RemoveNodeFromCSEMaps(User);
6157 // The Uses array is sorted, so all the uses for a given User
6158 // are next to each other in the list.
6159 // To help reduce the number of CSE recomputations, process all
6160 // the uses of this user that we can find this way.
6162 unsigned i = Uses[UseIndex].Index;
6163 SDUse &Use = *Uses[UseIndex].Use;
6167 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6169 // Now that we have modified User, add it back to the CSE maps. If it
6170 // already exists there, recursively merge the results together.
6171 AddModifiedNodeToCSEMaps(User);
6175 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6176 /// based on their topological order. It returns the maximum id and a vector
6177 /// of the SDNodes* in assigned order by reference.
6178 unsigned SelectionDAG::AssignTopologicalOrder() {
6180 unsigned DAGSize = 0;
6182 // SortedPos tracks the progress of the algorithm. Nodes before it are
6183 // sorted, nodes after it are unsorted. When the algorithm completes
6184 // it is at the end of the list.
6185 allnodes_iterator SortedPos = allnodes_begin();
6187 // Visit all the nodes. Move nodes with no operands to the front of
6188 // the list immediately. Annotate nodes that do have operands with their
6189 // operand count. Before we do this, the Node Id fields of the nodes
6190 // may contain arbitrary values. After, the Node Id fields for nodes
6191 // before SortedPos will contain the topological sort index, and the
6192 // Node Id fields for nodes At SortedPos and after will contain the
6193 // count of outstanding operands.
6194 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6196 checkForCycles(N, this);
6197 unsigned Degree = N->getNumOperands();
6199 // A node with no uses, add it to the result array immediately.
6200 N->setNodeId(DAGSize++);
6201 allnodes_iterator Q = N;
6203 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6204 assert(SortedPos != AllNodes.end() && "Overran node list");
6207 // Temporarily use the Node Id as scratch space for the degree count.
6208 N->setNodeId(Degree);
6212 // Visit all the nodes. As we iterate, move nodes into sorted order,
6213 // such that by the time the end is reached all nodes will be sorted.
6214 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6216 checkForCycles(N, this);
6217 // N is in sorted position, so all its uses have one less operand
6218 // that needs to be sorted.
6219 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6222 unsigned Degree = P->getNodeId();
6223 assert(Degree != 0 && "Invalid node degree");
6226 // All of P's operands are sorted, so P may sorted now.
6227 P->setNodeId(DAGSize++);
6229 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6230 assert(SortedPos != AllNodes.end() && "Overran node list");
6233 // Update P's outstanding operand count.
6234 P->setNodeId(Degree);
6237 if (I == SortedPos) {
6240 dbgs() << "Overran sorted position:\n";
6241 S->dumprFull(this); dbgs() << "\n";
6242 dbgs() << "Checking if this is due to cycles\n";
6243 checkForCycles(this, true);
6245 llvm_unreachable(nullptr);
6249 assert(SortedPos == AllNodes.end() &&
6250 "Topological sort incomplete!");
6251 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6252 "First node in topological sort is not the entry token!");
6253 assert(AllNodes.front().getNodeId() == 0 &&
6254 "First node in topological sort has non-zero id!");
6255 assert(AllNodes.front().getNumOperands() == 0 &&
6256 "First node in topological sort has operands!");
6257 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6258 "Last node in topologic sort has unexpected id!");
6259 assert(AllNodes.back().use_empty() &&
6260 "Last node in topologic sort has users!");
6261 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6265 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6266 /// value is produced by SD.
6267 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6269 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6270 SD->setHasDebugValue(true);
6272 DbgInfo->add(DB, SD, isParameter);
6275 /// TransferDbgValues - Transfer SDDbgValues.
6276 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6277 if (From == To || !From.getNode()->getHasDebugValue())
6279 SDNode *FromNode = From.getNode();
6280 SDNode *ToNode = To.getNode();
6281 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6282 SmallVector<SDDbgValue *, 2> ClonedDVs;
6283 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6285 SDDbgValue *Dbg = *I;
6286 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6288 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6289 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6290 Dbg->getDebugLoc(), Dbg->getOrder());
6291 ClonedDVs.push_back(Clone);
6294 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6295 E = ClonedDVs.end(); I != E; ++I)
6296 AddDbgValue(*I, ToNode, false);
6299 //===----------------------------------------------------------------------===//
6301 //===----------------------------------------------------------------------===//
6303 HandleSDNode::~HandleSDNode() {
6307 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6308 DebugLoc DL, const GlobalValue *GA,
6309 EVT VT, int64_t o, unsigned char TF)
6310 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6314 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6315 SDValue X, unsigned SrcAS,
6317 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6318 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6320 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6321 EVT memvt, MachineMemOperand *mmo)
6322 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6323 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6324 MMO->isNonTemporal(), MMO->isInvariant());
6325 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6326 assert(isNonTemporal() == MMO->isNonTemporal() &&
6327 "Non-temporal encoding error!");
6328 // We check here that the size of the memory operand fits within the size of
6329 // the MMO. This is because the MMO might indicate only a possible address
6330 // range instead of specifying the affected memory addresses precisely.
6331 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6334 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6335 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6336 : SDNode(Opc, Order, dl, VTs, Ops),
6337 MemoryVT(memvt), MMO(mmo) {
6338 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6339 MMO->isNonTemporal(), MMO->isInvariant());
6340 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6341 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6344 /// Profile - Gather unique data for the node.
6346 void SDNode::Profile(FoldingSetNodeID &ID) const {
6347 AddNodeIDNode(ID, this);
6352 std::vector<EVT> VTs;
6355 VTs.reserve(MVT::LAST_VALUETYPE);
6356 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6357 VTs.push_back(MVT((MVT::SimpleValueType)i));
6362 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6363 static ManagedStatic<EVTArray> SimpleVTArray;
6364 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6366 /// getValueTypeList - Return a pointer to the specified value type.
6368 const EVT *SDNode::getValueTypeList(EVT VT) {
6369 if (VT.isExtended()) {
6370 sys::SmartScopedLock<true> Lock(*VTMutex);
6371 return &(*EVTs->insert(VT).first);
6373 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6374 "Value type out of range!");
6375 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6379 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6380 /// indicated value. This method ignores uses of other values defined by this
6382 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6383 assert(Value < getNumValues() && "Bad value!");
6385 // TODO: Only iterate over uses of a given value of the node
6386 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6387 if (UI.getUse().getResNo() == Value) {
6394 // Found exactly the right number of uses?
6399 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6400 /// value. This method ignores uses of other values defined by this operation.
6401 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6402 assert(Value < getNumValues() && "Bad value!");
6404 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6405 if (UI.getUse().getResNo() == Value)
6412 /// isOnlyUserOf - Return true if this node is the only use of N.
6414 bool SDNode::isOnlyUserOf(SDNode *N) const {
6416 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6427 /// isOperand - Return true if this node is an operand of N.
6429 bool SDValue::isOperandOf(SDNode *N) const {
6430 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6431 if (*this == N->getOperand(i))
6436 bool SDNode::isOperandOf(SDNode *N) const {
6437 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6438 if (this == N->OperandList[i].getNode())
6443 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6444 /// be a chain) reaches the specified operand without crossing any
6445 /// side-effecting instructions on any chain path. In practice, this looks
6446 /// through token factors and non-volatile loads. In order to remain efficient,
6447 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6448 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6449 unsigned Depth) const {
6450 if (*this == Dest) return true;
6452 // Don't search too deeply, we just want to be able to see through
6453 // TokenFactor's etc.
6454 if (Depth == 0) return false;
6456 // If this is a token factor, all inputs to the TF happen in parallel. If any
6457 // of the operands of the TF does not reach dest, then we cannot do the xform.
6458 if (getOpcode() == ISD::TokenFactor) {
6459 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6460 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6465 // Loads don't have side effects, look through them.
6466 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6467 if (!Ld->isVolatile())
6468 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6473 /// hasPredecessor - Return true if N is a predecessor of this node.
6474 /// N is either an operand of this node, or can be reached by recursively
6475 /// traversing up the operands.
6476 /// NOTE: This is an expensive method. Use it carefully.
6477 bool SDNode::hasPredecessor(const SDNode *N) const {
6478 SmallPtrSet<const SDNode *, 32> Visited;
6479 SmallVector<const SDNode *, 16> Worklist;
6480 return hasPredecessorHelper(N, Visited, Worklist);
6484 SDNode::hasPredecessorHelper(const SDNode *N,
6485 SmallPtrSetImpl<const SDNode *> &Visited,
6486 SmallVectorImpl<const SDNode *> &Worklist) const {
6487 if (Visited.empty()) {
6488 Worklist.push_back(this);
6490 // Take a look in the visited set. If we've already encountered this node
6491 // we needn't search further.
6492 if (Visited.count(N))
6496 // Haven't visited N yet. Continue the search.
6497 while (!Worklist.empty()) {
6498 const SDNode *M = Worklist.pop_back_val();
6499 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6500 SDNode *Op = M->getOperand(i).getNode();
6501 if (Visited.insert(Op).second)
6502 Worklist.push_back(Op);
6511 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6512 assert(Num < NumOperands && "Invalid child # of SDNode!");
6513 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6516 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6517 assert(N->getNumValues() == 1 &&
6518 "Can't unroll a vector with multiple results!");
6520 EVT VT = N->getValueType(0);
6521 unsigned NE = VT.getVectorNumElements();
6522 EVT EltVT = VT.getVectorElementType();
6525 SmallVector<SDValue, 8> Scalars;
6526 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6528 // If ResNE is 0, fully unroll the vector op.
6531 else if (NE > ResNE)
6535 for (i= 0; i != NE; ++i) {
6536 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6537 SDValue Operand = N->getOperand(j);
6538 EVT OperandVT = Operand.getValueType();
6539 if (OperandVT.isVector()) {
6540 // A vector operand; extract a single element.
6541 EVT OperandEltVT = OperandVT.getVectorElementType();
6542 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6545 getConstant(i, TLI->getVectorIdxTy()));
6547 // A scalar operand; just use it as is.
6548 Operands[j] = Operand;
6552 switch (N->getOpcode()) {
6554 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6557 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6564 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6565 getShiftAmountOperand(Operands[0].getValueType(),
6568 case ISD::SIGN_EXTEND_INREG:
6569 case ISD::FP_ROUND_INREG: {
6570 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6571 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6573 getValueType(ExtVT)));
6578 for (; i < ResNE; ++i)
6579 Scalars.push_back(getUNDEF(EltVT));
6581 return getNode(ISD::BUILD_VECTOR, dl,
6582 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6586 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6587 /// location that is 'Dist' units away from the location that the 'Base' load
6588 /// is loading from.
6589 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6590 unsigned Bytes, int Dist) const {
6591 if (LD->getChain() != Base->getChain())
6593 EVT VT = LD->getValueType(0);
6594 if (VT.getSizeInBits() / 8 != Bytes)
6597 SDValue Loc = LD->getOperand(1);
6598 SDValue BaseLoc = Base->getOperand(1);
6599 if (Loc.getOpcode() == ISD::FrameIndex) {
6600 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6602 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6603 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6604 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6605 int FS = MFI->getObjectSize(FI);
6606 int BFS = MFI->getObjectSize(BFI);
6607 if (FS != BFS || FS != (int)Bytes) return false;
6608 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6612 if (isBaseWithConstantOffset(Loc)) {
6613 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6614 if (Loc.getOperand(0) == BaseLoc) {
6615 // If the base location is a simple address with no offset itself, then
6616 // the second load's first add operand should be the base address.
6617 if (LocOffset == Dist * (int)Bytes)
6619 } else if (isBaseWithConstantOffset(BaseLoc)) {
6620 // The base location itself has an offset, so subtract that value from the
6621 // second load's offset before comparing to distance * size.
6623 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6624 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6625 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6630 const GlobalValue *GV1 = nullptr;
6631 const GlobalValue *GV2 = nullptr;
6632 int64_t Offset1 = 0;
6633 int64_t Offset2 = 0;
6634 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6635 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6636 if (isGA1 && isGA2 && GV1 == GV2)
6637 return Offset1 == (Offset2 + Dist*Bytes);
6642 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6643 /// it cannot be inferred.
6644 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6645 // If this is a GlobalAddress + cst, return the alignment.
6646 const GlobalValue *GV;
6647 int64_t GVOffset = 0;
6648 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6649 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6650 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6651 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6652 TLI->getDataLayout());
6653 unsigned AlignBits = KnownZero.countTrailingOnes();
6654 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6656 return MinAlign(Align, GVOffset);
6659 // If this is a direct reference to a stack slot, use information about the
6660 // stack slot's alignment.
6661 int FrameIdx = 1 << 31;
6662 int64_t FrameOffset = 0;
6663 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6664 FrameIdx = FI->getIndex();
6665 } else if (isBaseWithConstantOffset(Ptr) &&
6666 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6668 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6669 FrameOffset = Ptr.getConstantOperandVal(1);
6672 if (FrameIdx != (1 << 31)) {
6673 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6674 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6682 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6683 /// which is split (or expanded) into two not necessarily identical pieces.
6684 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6685 // Currently all types are split in half.
6687 if (!VT.isVector()) {
6688 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6690 unsigned NumElements = VT.getVectorNumElements();
6691 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6692 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6695 return std::make_pair(LoVT, HiVT);
6698 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6700 std::pair<SDValue, SDValue>
6701 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6703 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6704 N.getValueType().getVectorNumElements() &&
6705 "More vector elements requested than available!");
6707 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6708 getConstant(0, TLI->getVectorIdxTy()));
6709 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6710 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6711 return std::make_pair(Lo, Hi);
6714 void SelectionDAG::ExtractVectorElements(SDValue Op,
6715 SmallVectorImpl<SDValue> &Args,
6716 unsigned Start, unsigned Count) {
6717 EVT VT = Op.getValueType();
6719 Count = VT.getVectorNumElements();
6721 EVT EltVT = VT.getVectorElementType();
6722 EVT IdxTy = TLI->getVectorIdxTy();
6724 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6725 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6726 Op, getConstant(i, IdxTy)));
6730 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6731 unsigned GlobalAddressSDNode::getAddressSpace() const {
6732 return getGlobal()->getType()->getAddressSpace();
6736 Type *ConstantPoolSDNode::getType() const {
6737 if (isMachineConstantPoolEntry())
6738 return Val.MachineCPVal->getType();
6739 return Val.ConstVal->getType();
6742 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6744 unsigned &SplatBitSize,
6746 unsigned MinSplatBits,
6747 bool isBigEndian) const {
6748 EVT VT = getValueType(0);
6749 assert(VT.isVector() && "Expected a vector type");
6750 unsigned sz = VT.getSizeInBits();
6751 if (MinSplatBits > sz)
6754 SplatValue = APInt(sz, 0);
6755 SplatUndef = APInt(sz, 0);
6757 // Get the bits. Bits with undefined values (when the corresponding element
6758 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6759 // in SplatValue. If any of the values are not constant, give up and return
6761 unsigned int nOps = getNumOperands();
6762 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6763 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6765 for (unsigned j = 0; j < nOps; ++j) {
6766 unsigned i = isBigEndian ? nOps-1-j : j;
6767 SDValue OpVal = getOperand(i);
6768 unsigned BitPos = j * EltBitSize;
6770 if (OpVal.getOpcode() == ISD::UNDEF)
6771 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6772 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6773 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6774 zextOrTrunc(sz) << BitPos;
6775 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6776 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6781 // The build_vector is all constants or undefs. Find the smallest element
6782 // size that splats the vector.
6784 HasAnyUndefs = (SplatUndef != 0);
6787 unsigned HalfSize = sz / 2;
6788 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6789 APInt LowValue = SplatValue.trunc(HalfSize);
6790 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6791 APInt LowUndef = SplatUndef.trunc(HalfSize);
6793 // If the two halves do not match (ignoring undef bits), stop here.
6794 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6795 MinSplatBits > HalfSize)
6798 SplatValue = HighValue | LowValue;
6799 SplatUndef = HighUndef & LowUndef;
6808 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6809 if (UndefElements) {
6810 UndefElements->clear();
6811 UndefElements->resize(getNumOperands());
6814 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6815 SDValue Op = getOperand(i);
6816 if (Op.getOpcode() == ISD::UNDEF) {
6818 (*UndefElements)[i] = true;
6819 } else if (!Splatted) {
6821 } else if (Splatted != Op) {
6827 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6828 "Can only have a splat without a constant for all undefs.");
6829 return getOperand(0);
6836 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6837 return dyn_cast_or_null<ConstantSDNode>(
6838 getSplatValue(UndefElements).getNode());
6842 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6843 return dyn_cast_or_null<ConstantFPSDNode>(
6844 getSplatValue(UndefElements).getNode());
6847 bool BuildVectorSDNode::isConstant() const {
6848 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6849 unsigned Opc = getOperand(i).getOpcode();
6850 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6856 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6857 // Find the first non-undef value in the shuffle mask.
6859 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6862 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6864 // Make sure all remaining elements are either undef or the same as the first
6866 for (int Idx = Mask[i]; i != e; ++i)
6867 if (Mask[i] >= 0 && Mask[i] != Idx)
6873 static void checkForCyclesHelper(const SDNode *N,
6874 SmallPtrSetImpl<const SDNode*> &Visited,
6875 SmallPtrSetImpl<const SDNode*> &Checked,
6876 const llvm::SelectionDAG *DAG) {
6877 // If this node has already been checked, don't check it again.
6878 if (Checked.count(N))
6881 // If a node has already been visited on this depth-first walk, reject it as
6883 if (!Visited.insert(N).second) {
6884 errs() << "Detected cycle in SelectionDAG\n";
6885 dbgs() << "Offending node:\n";
6886 N->dumprFull(DAG); dbgs() << "\n";
6890 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6891 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6898 void llvm::checkForCycles(const llvm::SDNode *N,
6899 const llvm::SelectionDAG *DAG,
6907 assert(N && "Checking nonexistent SDNode");
6908 SmallPtrSet<const SDNode*, 32> visited;
6909 SmallPtrSet<const SDNode*, 32> checked;
6910 checkForCyclesHelper(N, visited, checked, DAG);
6915 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6916 checkForCycles(DAG->getRoot().getNode(), DAG, force);