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 int NElts = M.size();
1450 for (int i = 0; i != NElts; ++i) {
1458 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1459 SDValue N2, const int *Mask) {
1460 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1461 "Invalid VECTOR_SHUFFLE");
1463 // Canonicalize shuffle undef, undef -> undef
1464 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1465 return getUNDEF(VT);
1467 // Validate that all indices in Mask are within the range of the elements
1468 // input to the shuffle.
1469 unsigned NElts = VT.getVectorNumElements();
1470 SmallVector<int, 8> MaskVec;
1471 for (unsigned i = 0; i != NElts; ++i) {
1472 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1473 MaskVec.push_back(Mask[i]);
1476 // Canonicalize shuffle v, v -> v, undef
1479 for (unsigned i = 0; i != NElts; ++i)
1480 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1483 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1484 if (N1.getOpcode() == ISD::UNDEF)
1485 commuteShuffle(N1, N2, MaskVec);
1487 // If shuffling a splat, try to blend the splat instead. We do this here so
1488 // that even when this arises during lowering we don't have to re-handle it.
1489 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1490 BitVector UndefElements;
1491 SDValue Splat = BV->getSplatValue(&UndefElements);
1495 for (int i = 0; i < (int)NElts; ++i) {
1496 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1499 // If this input comes from undef, mark it as such.
1500 if (UndefElements[MaskVec[i] - Offset]) {
1505 // If we can blend a non-undef lane, use that instead.
1506 if (!UndefElements[i])
1507 MaskVec[i] = i + Offset;
1510 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1511 BlendSplat(N1BV, 0);
1512 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1513 BlendSplat(N2BV, NElts);
1515 // Canonicalize all index into lhs, -> shuffle lhs, undef
1516 // Canonicalize all index into rhs, -> shuffle rhs, undef
1517 bool AllLHS = true, AllRHS = true;
1518 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1519 for (unsigned i = 0; i != NElts; ++i) {
1520 if (MaskVec[i] >= (int)NElts) {
1525 } else if (MaskVec[i] >= 0) {
1529 if (AllLHS && AllRHS)
1530 return getUNDEF(VT);
1531 if (AllLHS && !N2Undef)
1535 commuteShuffle(N1, N2, MaskVec);
1537 // Reset our undef status after accounting for the mask.
1538 N2Undef = N2.getOpcode() == ISD::UNDEF;
1539 // Re-check whether both sides ended up undef.
1540 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1541 return getUNDEF(VT);
1543 // If Identity shuffle return that node.
1544 bool Identity = true, AllSame = true;
1545 for (unsigned i = 0; i != NElts; ++i) {
1546 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1547 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1549 if (Identity && NElts)
1552 // Shuffling a constant splat doesn't change the result.
1556 // Look through any bitcasts. We check that these don't change the number
1557 // (and size) of elements and just changes their types.
1558 while (V.getOpcode() == ISD::BITCAST)
1559 V = V->getOperand(0);
1561 // A splat should always show up as a build vector node.
1562 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1563 BitVector UndefElements;
1564 SDValue Splat = BV->getSplatValue(&UndefElements);
1565 // If this is a splat of an undef, shuffling it is also undef.
1566 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1567 return getUNDEF(VT);
1570 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1572 // We only have a splat which can skip shuffles if there is a splatted
1573 // value and no undef lanes rearranged by the shuffle.
1574 if (Splat && UndefElements.none()) {
1575 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1576 // number of elements match or the value splatted is a zero constant.
1579 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1580 if (C->isNullValue())
1584 // If the shuffle itself creates a splat, build the vector directly.
1585 if (AllSame && SameNumElts) {
1586 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1587 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1589 EVT BuildVT = BV->getValueType(0);
1590 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1592 // We may have jumped through bitcasts, so the type of the
1593 // BUILD_VECTOR may not match the type of the shuffle.
1595 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1601 FoldingSetNodeID ID;
1602 SDValue Ops[2] = { N1, N2 };
1603 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1604 for (unsigned i = 0; i != NElts; ++i)
1605 ID.AddInteger(MaskVec[i]);
1608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1609 return SDValue(E, 0);
1611 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1612 // SDNode doesn't have access to it. This memory will be "leaked" when
1613 // the node is deallocated, but recovered when the NodeAllocator is released.
1614 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1615 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1617 ShuffleVectorSDNode *N =
1618 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1619 dl.getDebugLoc(), N1, N2,
1621 CSEMap.InsertNode(N, IP);
1623 return SDValue(N, 0);
1626 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1627 MVT VT = SV.getSimpleValueType(0);
1628 unsigned NumElems = VT.getVectorNumElements();
1629 SmallVector<int, 8> MaskVec;
1631 for (unsigned i = 0; i != NumElems; ++i) {
1632 int Idx = SV.getMaskElt(i);
1634 if (Idx < (int)NumElems)
1639 MaskVec.push_back(Idx);
1642 SDValue Op0 = SV.getOperand(0);
1643 SDValue Op1 = SV.getOperand(1);
1644 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1647 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1648 SDValue Val, SDValue DTy,
1649 SDValue STy, SDValue Rnd, SDValue Sat,
1650 ISD::CvtCode Code) {
1651 // If the src and dest types are the same and the conversion is between
1652 // integer types of the same sign or two floats, no conversion is necessary.
1654 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1657 FoldingSetNodeID ID;
1658 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1659 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1661 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1662 return SDValue(E, 0);
1664 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1667 CSEMap.InsertNode(N, IP);
1669 return SDValue(N, 0);
1672 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1673 FoldingSetNodeID ID;
1674 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1675 ID.AddInteger(RegNo);
1677 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1678 return SDValue(E, 0);
1680 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1681 CSEMap.InsertNode(N, IP);
1683 return SDValue(N, 0);
1686 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1687 FoldingSetNodeID ID;
1688 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1689 ID.AddPointer(RegMask);
1691 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1692 return SDValue(E, 0);
1694 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1695 CSEMap.InsertNode(N, IP);
1697 return SDValue(N, 0);
1700 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1701 FoldingSetNodeID ID;
1702 SDValue Ops[] = { Root };
1703 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1704 ID.AddPointer(Label);
1706 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1707 return SDValue(E, 0);
1709 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1710 dl.getDebugLoc(), Root, Label);
1711 CSEMap.InsertNode(N, IP);
1713 return SDValue(N, 0);
1717 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1720 unsigned char TargetFlags) {
1721 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1723 FoldingSetNodeID ID;
1724 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1726 ID.AddInteger(Offset);
1727 ID.AddInteger(TargetFlags);
1729 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1730 return SDValue(E, 0);
1732 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1734 CSEMap.InsertNode(N, IP);
1736 return SDValue(N, 0);
1739 SDValue SelectionDAG::getSrcValue(const Value *V) {
1740 assert((!V || V->getType()->isPointerTy()) &&
1741 "SrcValue is not a pointer?");
1743 FoldingSetNodeID ID;
1744 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1748 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1749 return SDValue(E, 0);
1751 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1752 CSEMap.InsertNode(N, IP);
1754 return SDValue(N, 0);
1757 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1758 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1759 FoldingSetNodeID ID;
1760 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1764 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1765 return SDValue(E, 0);
1767 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1768 CSEMap.InsertNode(N, IP);
1770 return SDValue(N, 0);
1773 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1774 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1775 unsigned SrcAS, unsigned DestAS) {
1776 SDValue Ops[] = {Ptr};
1777 FoldingSetNodeID ID;
1778 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1779 ID.AddInteger(SrcAS);
1780 ID.AddInteger(DestAS);
1783 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1784 return SDValue(E, 0);
1786 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1788 VT, Ptr, SrcAS, DestAS);
1789 CSEMap.InsertNode(N, IP);
1791 return SDValue(N, 0);
1794 /// getShiftAmountOperand - Return the specified value casted to
1795 /// the target's desired shift amount type.
1796 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1797 EVT OpTy = Op.getValueType();
1798 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1799 if (OpTy == ShTy || OpTy.isVector()) return Op;
1801 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1802 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1805 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1806 /// specified value type.
1807 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1808 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1809 unsigned ByteSize = VT.getStoreSize();
1810 Type *Ty = VT.getTypeForEVT(*getContext());
1811 unsigned StackAlign =
1812 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1814 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1815 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1818 /// CreateStackTemporary - Create a stack temporary suitable for holding
1819 /// either of the specified value types.
1820 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1821 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1822 VT2.getStoreSizeInBits())/8;
1823 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1824 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1825 const DataLayout *TD = TLI->getDataLayout();
1826 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1827 TD->getPrefTypeAlignment(Ty2));
1829 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1830 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1831 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1834 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1835 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1836 // These setcc operations always fold.
1840 case ISD::SETFALSE2: return getConstant(0, VT);
1842 case ISD::SETTRUE2: {
1843 TargetLowering::BooleanContent Cnt =
1844 TLI->getBooleanContents(N1->getValueType(0));
1846 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1859 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1863 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1864 const APInt &C2 = N2C->getAPIntValue();
1865 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1866 const APInt &C1 = N1C->getAPIntValue();
1869 default: llvm_unreachable("Unknown integer setcc!");
1870 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1871 case ISD::SETNE: return getConstant(C1 != C2, VT);
1872 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1873 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1874 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1875 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1876 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1877 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1878 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1879 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1883 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1884 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1885 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1888 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1889 return getUNDEF(VT);
1891 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1892 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1893 return getUNDEF(VT);
1895 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1896 R==APFloat::cmpLessThan, VT);
1897 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1898 return getUNDEF(VT);
1900 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1901 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1902 return getUNDEF(VT);
1904 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1905 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1906 return getUNDEF(VT);
1908 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1909 R==APFloat::cmpEqual, VT);
1910 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1911 return getUNDEF(VT);
1913 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1914 R==APFloat::cmpEqual, VT);
1915 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1916 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1917 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1918 R==APFloat::cmpEqual, VT);
1919 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1920 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1921 R==APFloat::cmpLessThan, VT);
1922 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1923 R==APFloat::cmpUnordered, VT);
1924 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1925 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1928 // Ensure that the constant occurs on the RHS.
1929 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1930 MVT CompVT = N1.getValueType().getSimpleVT();
1931 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1934 return getSetCC(dl, VT, N2, N1, SwappedCond);
1938 // Could not fold it.
1942 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1943 /// use this predicate to simplify operations downstream.
1944 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1945 // This predicate is not safe for vector operations.
1946 if (Op.getValueType().isVector())
1949 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1950 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1953 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1954 /// this predicate to simplify operations downstream. Mask is known to be zero
1955 /// for bits that V cannot have.
1956 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1957 unsigned Depth) const {
1958 APInt KnownZero, KnownOne;
1959 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1960 return (KnownZero & Mask) == Mask;
1963 /// Determine which bits of Op are known to be either zero or one and return
1964 /// them in the KnownZero/KnownOne bitsets.
1965 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1966 APInt &KnownOne, unsigned Depth) const {
1967 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1969 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1971 return; // Limit search depth.
1973 APInt KnownZero2, KnownOne2;
1975 switch (Op.getOpcode()) {
1977 // We know all of the bits for a constant!
1978 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1979 KnownZero = ~KnownOne;
1982 // If either the LHS or the RHS are Zero, the result is zero.
1983 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1984 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1986 // Output known-1 bits are only known if set in both the LHS & RHS.
1987 KnownOne &= KnownOne2;
1988 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1989 KnownZero |= KnownZero2;
1992 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1993 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1995 // Output known-0 bits are only known if clear in both the LHS & RHS.
1996 KnownZero &= KnownZero2;
1997 // Output known-1 are known to be set if set in either the LHS | RHS.
1998 KnownOne |= KnownOne2;
2001 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2002 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2004 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2005 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2006 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2007 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2008 KnownZero = KnownZeroOut;
2012 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2013 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2015 // If low bits are zero in either operand, output low known-0 bits.
2016 // Also compute a conserative estimate for high known-0 bits.
2017 // More trickiness is possible, but this is sufficient for the
2018 // interesting case of alignment computation.
2019 KnownOne.clearAllBits();
2020 unsigned TrailZ = KnownZero.countTrailingOnes() +
2021 KnownZero2.countTrailingOnes();
2022 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2023 KnownZero2.countLeadingOnes(),
2024 BitWidth) - BitWidth;
2026 TrailZ = std::min(TrailZ, BitWidth);
2027 LeadZ = std::min(LeadZ, BitWidth);
2028 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2029 APInt::getHighBitsSet(BitWidth, LeadZ);
2033 // For the purposes of computing leading zeros we can conservatively
2034 // treat a udiv as a logical right shift by the power of 2 known to
2035 // be less than the denominator.
2036 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2037 unsigned LeadZ = KnownZero2.countLeadingOnes();
2039 KnownOne2.clearAllBits();
2040 KnownZero2.clearAllBits();
2041 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2042 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2043 if (RHSUnknownLeadingOnes != BitWidth)
2044 LeadZ = std::min(BitWidth,
2045 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2047 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2051 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2052 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2054 // Only known if known in both the LHS and RHS.
2055 KnownOne &= KnownOne2;
2056 KnownZero &= KnownZero2;
2058 case ISD::SELECT_CC:
2059 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2060 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2062 // Only known if known in both the LHS and RHS.
2063 KnownOne &= KnownOne2;
2064 KnownZero &= KnownZero2;
2072 if (Op.getResNo() != 1)
2074 // The boolean result conforms to getBooleanContents.
2075 // If we know the result of a setcc has the top bits zero, use this info.
2076 // We know that we have an integer-based boolean since these operations
2077 // are only available for integer.
2078 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2079 TargetLowering::ZeroOrOneBooleanContent &&
2081 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2084 // If we know the result of a setcc has the top bits zero, use this info.
2085 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2086 TargetLowering::ZeroOrOneBooleanContent &&
2088 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2091 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2092 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2093 unsigned ShAmt = SA->getZExtValue();
2095 // If the shift count is an invalid immediate, don't do anything.
2096 if (ShAmt >= BitWidth)
2099 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2100 KnownZero <<= ShAmt;
2102 // low bits known zero.
2103 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2107 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2108 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2109 unsigned ShAmt = SA->getZExtValue();
2111 // If the shift count is an invalid immediate, don't do anything.
2112 if (ShAmt >= BitWidth)
2115 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2116 KnownZero = KnownZero.lshr(ShAmt);
2117 KnownOne = KnownOne.lshr(ShAmt);
2119 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2120 KnownZero |= HighBits; // High bits known zero.
2124 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2125 unsigned ShAmt = SA->getZExtValue();
2127 // If the shift count is an invalid immediate, don't do anything.
2128 if (ShAmt >= BitWidth)
2131 // If any of the demanded bits are produced by the sign extension, we also
2132 // demand the input sign bit.
2133 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2135 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2136 KnownZero = KnownZero.lshr(ShAmt);
2137 KnownOne = KnownOne.lshr(ShAmt);
2139 // Handle the sign bits.
2140 APInt SignBit = APInt::getSignBit(BitWidth);
2141 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2143 if (KnownZero.intersects(SignBit)) {
2144 KnownZero |= HighBits; // New bits are known zero.
2145 } else if (KnownOne.intersects(SignBit)) {
2146 KnownOne |= HighBits; // New bits are known one.
2150 case ISD::SIGN_EXTEND_INREG: {
2151 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2152 unsigned EBits = EVT.getScalarType().getSizeInBits();
2154 // Sign extension. Compute the demanded bits in the result that are not
2155 // present in the input.
2156 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2158 APInt InSignBit = APInt::getSignBit(EBits);
2159 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2161 // If the sign extended bits are demanded, we know that the sign
2163 InSignBit = InSignBit.zext(BitWidth);
2164 if (NewBits.getBoolValue())
2165 InputDemandedBits |= InSignBit;
2167 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2168 KnownOne &= InputDemandedBits;
2169 KnownZero &= InputDemandedBits;
2171 // If the sign bit of the input is known set or clear, then we know the
2172 // top bits of the result.
2173 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2174 KnownZero |= NewBits;
2175 KnownOne &= ~NewBits;
2176 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2177 KnownOne |= NewBits;
2178 KnownZero &= ~NewBits;
2179 } else { // Input sign bit unknown
2180 KnownZero &= ~NewBits;
2181 KnownOne &= ~NewBits;
2186 case ISD::CTTZ_ZERO_UNDEF:
2188 case ISD::CTLZ_ZERO_UNDEF:
2190 unsigned LowBits = Log2_32(BitWidth)+1;
2191 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2192 KnownOne.clearAllBits();
2196 LoadSDNode *LD = cast<LoadSDNode>(Op);
2197 // If this is a ZEXTLoad and we are looking at the loaded value.
2198 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2199 EVT VT = LD->getMemoryVT();
2200 unsigned MemBits = VT.getScalarType().getSizeInBits();
2201 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2202 } else if (const MDNode *Ranges = LD->getRanges()) {
2203 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2207 case ISD::ZERO_EXTEND: {
2208 EVT InVT = Op.getOperand(0).getValueType();
2209 unsigned InBits = InVT.getScalarType().getSizeInBits();
2210 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2211 KnownZero = KnownZero.trunc(InBits);
2212 KnownOne = KnownOne.trunc(InBits);
2213 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2214 KnownZero = KnownZero.zext(BitWidth);
2215 KnownOne = KnownOne.zext(BitWidth);
2216 KnownZero |= NewBits;
2219 case ISD::SIGN_EXTEND: {
2220 EVT InVT = Op.getOperand(0).getValueType();
2221 unsigned InBits = InVT.getScalarType().getSizeInBits();
2222 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2224 KnownZero = KnownZero.trunc(InBits);
2225 KnownOne = KnownOne.trunc(InBits);
2226 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2228 // Note if the sign bit is known to be zero or one.
2229 bool SignBitKnownZero = KnownZero.isNegative();
2230 bool SignBitKnownOne = KnownOne.isNegative();
2232 KnownZero = KnownZero.zext(BitWidth);
2233 KnownOne = KnownOne.zext(BitWidth);
2235 // If the sign bit is known zero or one, the top bits match.
2236 if (SignBitKnownZero)
2237 KnownZero |= NewBits;
2238 else if (SignBitKnownOne)
2239 KnownOne |= NewBits;
2242 case ISD::ANY_EXTEND: {
2243 EVT InVT = Op.getOperand(0).getValueType();
2244 unsigned InBits = InVT.getScalarType().getSizeInBits();
2245 KnownZero = KnownZero.trunc(InBits);
2246 KnownOne = KnownOne.trunc(InBits);
2247 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2248 KnownZero = KnownZero.zext(BitWidth);
2249 KnownOne = KnownOne.zext(BitWidth);
2252 case ISD::TRUNCATE: {
2253 EVT InVT = Op.getOperand(0).getValueType();
2254 unsigned InBits = InVT.getScalarType().getSizeInBits();
2255 KnownZero = KnownZero.zext(InBits);
2256 KnownOne = KnownOne.zext(InBits);
2257 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2258 KnownZero = KnownZero.trunc(BitWidth);
2259 KnownOne = KnownOne.trunc(BitWidth);
2262 case ISD::AssertZext: {
2263 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2264 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2265 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2266 KnownZero |= (~InMask);
2267 KnownOne &= (~KnownZero);
2271 // All bits are zero except the low bit.
2272 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2276 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2277 // We know that the top bits of C-X are clear if X contains less bits
2278 // than C (i.e. no wrap-around can happen). For example, 20-X is
2279 // positive if we can prove that X is >= 0 and < 16.
2280 if (CLHS->getAPIntValue().isNonNegative()) {
2281 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2282 // NLZ can't be BitWidth with no sign bit
2283 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2284 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2286 // If all of the MaskV bits are known to be zero, then we know the
2287 // output top bits are zero, because we now know that the output is
2289 if ((KnownZero2 & MaskV) == MaskV) {
2290 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2291 // Top bits known zero.
2292 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2300 // Output known-0 bits are known if clear or set in both the low clear bits
2301 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2302 // low 3 bits clear.
2303 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2304 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2306 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2307 KnownZeroOut = std::min(KnownZeroOut,
2308 KnownZero2.countTrailingOnes());
2310 if (Op.getOpcode() == ISD::ADD) {
2311 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2315 // With ADDE, a carry bit may be added in, so we can only use this
2316 // information if we know (at least) that the low two bits are clear. We
2317 // then return to the caller that the low bit is unknown but that other bits
2319 if (KnownZeroOut >= 2) // ADDE
2320 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2324 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2325 const APInt &RA = Rem->getAPIntValue().abs();
2326 if (RA.isPowerOf2()) {
2327 APInt LowBits = RA - 1;
2328 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2330 // The low bits of the first operand are unchanged by the srem.
2331 KnownZero = KnownZero2 & LowBits;
2332 KnownOne = KnownOne2 & LowBits;
2334 // If the first operand is non-negative or has all low bits zero, then
2335 // the upper bits are all zero.
2336 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2337 KnownZero |= ~LowBits;
2339 // If the first operand is negative and not all low bits are zero, then
2340 // the upper bits are all one.
2341 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2342 KnownOne |= ~LowBits;
2343 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2348 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2349 const APInt &RA = Rem->getAPIntValue();
2350 if (RA.isPowerOf2()) {
2351 APInt LowBits = (RA - 1);
2352 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2354 // The upper bits are all zero, the lower ones are unchanged.
2355 KnownZero = KnownZero2 | ~LowBits;
2356 KnownOne = KnownOne2 & LowBits;
2361 // Since the result is less than or equal to either operand, any leading
2362 // zero bits in either operand must also exist in the result.
2363 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2364 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2366 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2367 KnownZero2.countLeadingOnes());
2368 KnownOne.clearAllBits();
2369 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2372 case ISD::EXTRACT_ELEMENT: {
2373 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2374 const unsigned Index =
2375 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2376 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2378 // Remove low part of known bits mask
2379 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2380 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2382 // Remove high part of known bit mask
2383 KnownZero = KnownZero.trunc(BitWidth);
2384 KnownOne = KnownOne.trunc(BitWidth);
2387 case ISD::FrameIndex:
2388 case ISD::TargetFrameIndex:
2389 if (unsigned Align = InferPtrAlignment(Op)) {
2390 // The low bits are known zero if the pointer is aligned.
2391 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2397 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2400 case ISD::INTRINSIC_WO_CHAIN:
2401 case ISD::INTRINSIC_W_CHAIN:
2402 case ISD::INTRINSIC_VOID:
2403 // Allow the target to implement this method for its nodes.
2404 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2408 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2411 /// ComputeNumSignBits - Return the number of times the sign bit of the
2412 /// register is replicated into the other bits. We know that at least 1 bit
2413 /// is always equal to the sign bit (itself), but other cases can give us
2414 /// information. For example, immediately after an "SRA X, 2", we know that
2415 /// the top 3 bits are all equal to each other, so we return 3.
2416 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2417 EVT VT = Op.getValueType();
2418 assert(VT.isInteger() && "Invalid VT!");
2419 unsigned VTBits = VT.getScalarType().getSizeInBits();
2421 unsigned FirstAnswer = 1;
2424 return 1; // Limit search depth.
2426 switch (Op.getOpcode()) {
2428 case ISD::AssertSext:
2429 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2430 return VTBits-Tmp+1;
2431 case ISD::AssertZext:
2432 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2435 case ISD::Constant: {
2436 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2437 return Val.getNumSignBits();
2440 case ISD::SIGN_EXTEND:
2442 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2443 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2445 case ISD::SIGN_EXTEND_INREG:
2446 // Max of the input and what this extends.
2448 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2451 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2452 return std::max(Tmp, Tmp2);
2455 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2456 // SRA X, C -> adds C sign bits.
2457 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2458 Tmp += C->getZExtValue();
2459 if (Tmp > VTBits) Tmp = VTBits;
2463 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2464 // shl destroys sign bits.
2465 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2466 if (C->getZExtValue() >= VTBits || // Bad shift.
2467 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2468 return Tmp - C->getZExtValue();
2473 case ISD::XOR: // NOT is handled here.
2474 // Logical binary ops preserve the number of sign bits at the worst.
2475 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2477 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2478 FirstAnswer = std::min(Tmp, Tmp2);
2479 // We computed what we know about the sign bits as our first
2480 // answer. Now proceed to the generic code that uses
2481 // computeKnownBits, and pick whichever answer is better.
2486 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2487 if (Tmp == 1) return 1; // Early out.
2488 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2489 return std::min(Tmp, Tmp2);
2497 if (Op.getResNo() != 1)
2499 // The boolean result conforms to getBooleanContents. Fall through.
2500 // If setcc returns 0/-1, all bits are sign bits.
2501 // We know that we have an integer-based boolean since these operations
2502 // are only available for integer.
2503 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2504 TargetLowering::ZeroOrNegativeOneBooleanContent)
2508 // If setcc returns 0/-1, all bits are sign bits.
2509 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2510 TargetLowering::ZeroOrNegativeOneBooleanContent)
2515 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2516 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2518 // Handle rotate right by N like a rotate left by 32-N.
2519 if (Op.getOpcode() == ISD::ROTR)
2520 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2522 // If we aren't rotating out all of the known-in sign bits, return the
2523 // number that are left. This handles rotl(sext(x), 1) for example.
2524 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2525 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2529 // Add can have at most one carry bit. Thus we know that the output
2530 // is, at worst, one more bit than the inputs.
2531 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2532 if (Tmp == 1) return 1; // Early out.
2534 // Special case decrementing a value (ADD X, -1):
2535 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2536 if (CRHS->isAllOnesValue()) {
2537 APInt KnownZero, KnownOne;
2538 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2540 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2542 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2545 // If we are subtracting one from a positive number, there is no carry
2546 // out of the result.
2547 if (KnownZero.isNegative())
2551 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2552 if (Tmp2 == 1) return 1;
2553 return std::min(Tmp, Tmp2)-1;
2556 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2557 if (Tmp2 == 1) return 1;
2560 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2561 if (CLHS->isNullValue()) {
2562 APInt KnownZero, KnownOne;
2563 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2564 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2566 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2569 // If the input is known to be positive (the sign bit is known clear),
2570 // the output of the NEG has the same number of sign bits as the input.
2571 if (KnownZero.isNegative())
2574 // Otherwise, we treat this like a SUB.
2577 // Sub can have at most one carry bit. Thus we know that the output
2578 // is, at worst, one more bit than the inputs.
2579 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2580 if (Tmp == 1) return 1; // Early out.
2581 return std::min(Tmp, Tmp2)-1;
2583 // FIXME: it's tricky to do anything useful for this, but it is an important
2584 // case for targets like X86.
2586 case ISD::EXTRACT_ELEMENT: {
2587 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2588 const int BitWidth = Op.getValueType().getSizeInBits();
2590 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2592 // Get reverse index (starting from 1), Op1 value indexes elements from
2593 // little end. Sign starts at big end.
2594 const int rIndex = Items - 1 -
2595 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2597 // If the sign portion ends in our element the substraction gives correct
2598 // result. Otherwise it gives either negative or > bitwidth result
2599 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2603 // If we are looking at the loaded value of the SDNode.
2604 if (Op.getResNo() == 0) {
2605 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2606 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2607 unsigned ExtType = LD->getExtensionType();
2610 case ISD::SEXTLOAD: // '17' bits known
2611 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2612 return VTBits-Tmp+1;
2613 case ISD::ZEXTLOAD: // '16' bits known
2614 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2620 // Allow the target to implement this method for its nodes.
2621 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2622 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2623 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2624 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2625 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2626 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2629 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2630 // use this information.
2631 APInt KnownZero, KnownOne;
2632 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2635 if (KnownZero.isNegative()) { // sign bit is 0
2637 } else if (KnownOne.isNegative()) { // sign bit is 1;
2644 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2645 // the number of identical bits in the top of the input value.
2647 Mask <<= Mask.getBitWidth()-VTBits;
2648 // Return # leading zeros. We use 'min' here in case Val was zero before
2649 // shifting. We don't want to return '64' as for an i32 "0".
2650 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2653 /// isBaseWithConstantOffset - Return true if the specified operand is an
2654 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2655 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2656 /// semantics as an ADD. This handles the equivalence:
2657 /// X|Cst == X+Cst iff X&Cst = 0.
2658 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2659 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2660 !isa<ConstantSDNode>(Op.getOperand(1)))
2663 if (Op.getOpcode() == ISD::OR &&
2664 !MaskedValueIsZero(Op.getOperand(0),
2665 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2672 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2673 // If we're told that NaNs won't happen, assume they won't.
2674 if (getTarget().Options.NoNaNsFPMath)
2677 // If the value is a constant, we can obviously see if it is a NaN or not.
2678 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2679 return !C->getValueAPF().isNaN();
2681 // TODO: Recognize more cases here.
2686 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2687 // If the value is a constant, we can obviously see if it is a zero or not.
2688 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2689 return !C->isZero();
2691 // TODO: Recognize more cases here.
2692 switch (Op.getOpcode()) {
2695 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2696 return !C->isNullValue();
2703 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2704 // Check the obvious case.
2705 if (A == B) return true;
2707 // For for negative and positive zero.
2708 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2709 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2710 if (CA->isZero() && CB->isZero()) return true;
2712 // Otherwise they may not be equal.
2716 /// getNode - Gets or creates the specified node.
2718 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2719 FoldingSetNodeID ID;
2720 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2722 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2723 return SDValue(E, 0);
2725 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2726 DL.getDebugLoc(), getVTList(VT));
2727 CSEMap.InsertNode(N, IP);
2730 return SDValue(N, 0);
2733 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2734 EVT VT, SDValue Operand) {
2735 // Constant fold unary operations with an integer constant operand. Even
2736 // opaque constant will be folded, because the folding of unary operations
2737 // doesn't create new constants with different values. Nevertheless, the
2738 // opaque flag is preserved during folding to prevent future folding with
2740 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2741 const APInt &Val = C->getAPIntValue();
2744 case ISD::SIGN_EXTEND:
2745 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2746 C->isTargetOpcode(), C->isOpaque());
2747 case ISD::ANY_EXTEND:
2748 case ISD::ZERO_EXTEND:
2750 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2751 C->isTargetOpcode(), C->isOpaque());
2752 case ISD::UINT_TO_FP:
2753 case ISD::SINT_TO_FP: {
2754 APFloat apf(EVTToAPFloatSemantics(VT),
2755 APInt::getNullValue(VT.getSizeInBits()));
2756 (void)apf.convertFromAPInt(Val,
2757 Opcode==ISD::SINT_TO_FP,
2758 APFloat::rmNearestTiesToEven);
2759 return getConstantFP(apf, VT);
2762 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2763 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2764 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2765 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2766 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2767 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2770 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2773 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2776 case ISD::CTLZ_ZERO_UNDEF:
2777 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2780 case ISD::CTTZ_ZERO_UNDEF:
2781 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2786 // Constant fold unary operations with a floating point constant operand.
2787 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2788 APFloat V = C->getValueAPF(); // make copy
2792 return getConstantFP(V, VT);
2795 return getConstantFP(V, VT);
2797 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2798 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2799 return getConstantFP(V, VT);
2803 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2804 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2805 return getConstantFP(V, VT);
2809 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2810 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2811 return getConstantFP(V, VT);
2814 case ISD::FP_EXTEND: {
2816 // This can return overflow, underflow, or inexact; we don't care.
2817 // FIXME need to be more flexible about rounding mode.
2818 (void)V.convert(EVTToAPFloatSemantics(VT),
2819 APFloat::rmNearestTiesToEven, &ignored);
2820 return getConstantFP(V, VT);
2822 case ISD::FP_TO_SINT:
2823 case ISD::FP_TO_UINT: {
2826 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2827 // FIXME need to be more flexible about rounding mode.
2828 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2829 Opcode==ISD::FP_TO_SINT,
2830 APFloat::rmTowardZero, &ignored);
2831 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2833 APInt api(VT.getSizeInBits(), x);
2834 return getConstant(api, VT);
2837 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2838 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2839 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2840 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2841 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2842 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2847 // Constant fold unary operations with a vector integer operand.
2848 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2849 if (BV->isConstant()) {
2852 // FIXME: Entirely reasonable to perform folding of other unary
2853 // operations here as the need arises.
2855 case ISD::UINT_TO_FP:
2856 case ISD::SINT_TO_FP: {
2857 SmallVector<SDValue, 8> Ops;
2858 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2859 SDValue OpN = BV->getOperand(i);
2860 // Let the above scalar folding handle the conversion of each
2862 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2866 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2872 unsigned OpOpcode = Operand.getNode()->getOpcode();
2874 case ISD::TokenFactor:
2875 case ISD::MERGE_VALUES:
2876 case ISD::CONCAT_VECTORS:
2877 return Operand; // Factor, merge or concat of one node? No need.
2878 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2879 case ISD::FP_EXTEND:
2880 assert(VT.isFloatingPoint() &&
2881 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2882 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2883 assert((!VT.isVector() ||
2884 VT.getVectorNumElements() ==
2885 Operand.getValueType().getVectorNumElements()) &&
2886 "Vector element count mismatch!");
2887 if (Operand.getOpcode() == ISD::UNDEF)
2888 return getUNDEF(VT);
2890 case ISD::SIGN_EXTEND:
2891 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2892 "Invalid SIGN_EXTEND!");
2893 if (Operand.getValueType() == VT) return Operand; // noop extension
2894 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2895 "Invalid sext node, dst < src!");
2896 assert((!VT.isVector() ||
2897 VT.getVectorNumElements() ==
2898 Operand.getValueType().getVectorNumElements()) &&
2899 "Vector element count mismatch!");
2900 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2901 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2902 else if (OpOpcode == ISD::UNDEF)
2903 // sext(undef) = 0, because the top bits will all be the same.
2904 return getConstant(0, VT);
2906 case ISD::ZERO_EXTEND:
2907 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2908 "Invalid ZERO_EXTEND!");
2909 if (Operand.getValueType() == VT) return Operand; // noop extension
2910 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2911 "Invalid zext node, dst < src!");
2912 assert((!VT.isVector() ||
2913 VT.getVectorNumElements() ==
2914 Operand.getValueType().getVectorNumElements()) &&
2915 "Vector element count mismatch!");
2916 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2917 return getNode(ISD::ZERO_EXTEND, DL, VT,
2918 Operand.getNode()->getOperand(0));
2919 else if (OpOpcode == ISD::UNDEF)
2920 // zext(undef) = 0, because the top bits will be zero.
2921 return getConstant(0, VT);
2923 case ISD::ANY_EXTEND:
2924 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2925 "Invalid ANY_EXTEND!");
2926 if (Operand.getValueType() == VT) return Operand; // noop extension
2927 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2928 "Invalid anyext node, dst < src!");
2929 assert((!VT.isVector() ||
2930 VT.getVectorNumElements() ==
2931 Operand.getValueType().getVectorNumElements()) &&
2932 "Vector element count mismatch!");
2934 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2935 OpOpcode == ISD::ANY_EXTEND)
2936 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2937 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2938 else if (OpOpcode == ISD::UNDEF)
2939 return getUNDEF(VT);
2941 // (ext (trunx x)) -> x
2942 if (OpOpcode == ISD::TRUNCATE) {
2943 SDValue OpOp = Operand.getNode()->getOperand(0);
2944 if (OpOp.getValueType() == VT)
2949 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2950 "Invalid TRUNCATE!");
2951 if (Operand.getValueType() == VT) return Operand; // noop truncate
2952 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2953 "Invalid truncate node, src < dst!");
2954 assert((!VT.isVector() ||
2955 VT.getVectorNumElements() ==
2956 Operand.getValueType().getVectorNumElements()) &&
2957 "Vector element count mismatch!");
2958 if (OpOpcode == ISD::TRUNCATE)
2959 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2960 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2961 OpOpcode == ISD::ANY_EXTEND) {
2962 // If the source is smaller than the dest, we still need an extend.
2963 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2964 .bitsLT(VT.getScalarType()))
2965 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2966 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2967 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2968 return Operand.getNode()->getOperand(0);
2970 if (OpOpcode == ISD::UNDEF)
2971 return getUNDEF(VT);
2974 // Basic sanity checking.
2975 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2976 && "Cannot BITCAST between types of different sizes!");
2977 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2978 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2979 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2980 if (OpOpcode == ISD::UNDEF)
2981 return getUNDEF(VT);
2983 case ISD::SCALAR_TO_VECTOR:
2984 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2985 (VT.getVectorElementType() == Operand.getValueType() ||
2986 (VT.getVectorElementType().isInteger() &&
2987 Operand.getValueType().isInteger() &&
2988 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2989 "Illegal SCALAR_TO_VECTOR node!");
2990 if (OpOpcode == ISD::UNDEF)
2991 return getUNDEF(VT);
2992 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2993 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2994 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2995 Operand.getConstantOperandVal(1) == 0 &&
2996 Operand.getOperand(0).getValueType() == VT)
2997 return Operand.getOperand(0);
3000 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3001 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3002 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3003 Operand.getNode()->getOperand(0));
3004 if (OpOpcode == ISD::FNEG) // --X -> X
3005 return Operand.getNode()->getOperand(0);
3008 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3009 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3014 SDVTList VTs = getVTList(VT);
3015 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3016 FoldingSetNodeID ID;
3017 SDValue Ops[1] = { Operand };
3018 AddNodeIDNode(ID, Opcode, VTs, Ops);
3020 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3021 return SDValue(E, 0);
3023 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3024 DL.getDebugLoc(), VTs, Operand);
3025 CSEMap.InsertNode(N, IP);
3027 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3028 DL.getDebugLoc(), VTs, Operand);
3032 return SDValue(N, 0);
3035 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3036 SDNode *Cst1, SDNode *Cst2) {
3037 // If the opcode is a target-specific ISD node, there's nothing we can
3038 // do here and the operand rules may not line up with the below, so
3040 if (Opcode >= ISD::BUILTIN_OP_END)
3043 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3044 SmallVector<SDValue, 4> Outputs;
3045 EVT SVT = VT.getScalarType();
3047 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3048 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3049 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3052 if (Scalar1 && Scalar2)
3053 // Scalar instruction.
3054 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3056 // For vectors extract each constant element into Inputs so we can constant
3057 // fold them individually.
3058 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3059 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3063 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3065 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3066 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3067 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3068 if (!V1 || !V2) // Not a constant, bail.
3071 if (V1->isOpaque() || V2->isOpaque())
3074 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3075 // FIXME: This is valid and could be handled by truncating the APInts.
3076 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3079 Inputs.push_back(std::make_pair(V1, V2));
3083 // We have a number of constant values, constant fold them element by element.
3084 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3085 const APInt &C1 = Inputs[I].first->getAPIntValue();
3086 const APInt &C2 = Inputs[I].second->getAPIntValue();
3090 Outputs.push_back(getConstant(C1 + C2, SVT));
3093 Outputs.push_back(getConstant(C1 - C2, SVT));
3096 Outputs.push_back(getConstant(C1 * C2, SVT));
3099 if (!C2.getBoolValue())
3101 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3104 if (!C2.getBoolValue())
3106 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3109 if (!C2.getBoolValue())
3111 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3114 if (!C2.getBoolValue())
3116 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3119 Outputs.push_back(getConstant(C1 & C2, SVT));
3122 Outputs.push_back(getConstant(C1 | C2, SVT));
3125 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3128 Outputs.push_back(getConstant(C1 << C2, SVT));
3131 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3134 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3137 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3140 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3147 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3148 "Expected a scalar or vector!"));
3150 // Handle the scalar case first.
3152 return Outputs.back();
3154 // We may have a vector type but a scalar result. Create a splat.
3155 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3157 // Build a big vector out of the scalar elements we generated.
3158 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3161 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3162 SDValue N2, bool nuw, bool nsw, bool exact) {
3163 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3164 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3167 case ISD::TokenFactor:
3168 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3169 N2.getValueType() == MVT::Other && "Invalid token factor!");
3170 // Fold trivial token factors.
3171 if (N1.getOpcode() == ISD::EntryToken) return N2;
3172 if (N2.getOpcode() == ISD::EntryToken) return N1;
3173 if (N1 == N2) return N1;
3175 case ISD::CONCAT_VECTORS:
3176 // Concat of UNDEFs is UNDEF.
3177 if (N1.getOpcode() == ISD::UNDEF &&
3178 N2.getOpcode() == ISD::UNDEF)
3179 return getUNDEF(VT);
3181 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3182 // one big BUILD_VECTOR.
3183 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3184 N2.getOpcode() == ISD::BUILD_VECTOR) {
3185 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3186 N1.getNode()->op_end());
3187 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3188 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3192 assert(VT.isInteger() && "This operator does not apply to FP types!");
3193 assert(N1.getValueType() == N2.getValueType() &&
3194 N1.getValueType() == VT && "Binary operator types must match!");
3195 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3196 // worth handling here.
3197 if (N2C && N2C->isNullValue())
3199 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3206 assert(VT.isInteger() && "This operator does not apply to FP types!");
3207 assert(N1.getValueType() == N2.getValueType() &&
3208 N1.getValueType() == VT && "Binary operator types must match!");
3209 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3210 // it's worth handling here.
3211 if (N2C && N2C->isNullValue())
3221 assert(VT.isInteger() && "This operator does not apply to FP types!");
3222 assert(N1.getValueType() == N2.getValueType() &&
3223 N1.getValueType() == VT && "Binary operator types must match!");
3230 if (getTarget().Options.UnsafeFPMath) {
3231 if (Opcode == ISD::FADD) {
3233 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3234 if (CFP->getValueAPF().isZero())
3237 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3238 if (CFP->getValueAPF().isZero())
3240 } else if (Opcode == ISD::FSUB) {
3242 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3243 if (CFP->getValueAPF().isZero())
3245 } else if (Opcode == ISD::FMUL) {
3246 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3249 // If the first operand isn't the constant, try the second
3251 CFP = dyn_cast<ConstantFPSDNode>(N2);
3258 return SDValue(CFP,0);
3260 if (CFP->isExactlyValue(1.0))
3265 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3266 assert(N1.getValueType() == N2.getValueType() &&
3267 N1.getValueType() == VT && "Binary operator types must match!");
3269 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3270 assert(N1.getValueType() == VT &&
3271 N1.getValueType().isFloatingPoint() &&
3272 N2.getValueType().isFloatingPoint() &&
3273 "Invalid FCOPYSIGN!");
3280 assert(VT == N1.getValueType() &&
3281 "Shift operators return type must be the same as their first arg");
3282 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3283 "Shifts only work on integers");
3284 assert((!VT.isVector() || VT == N2.getValueType()) &&
3285 "Vector shift amounts must be in the same as their first arg");
3286 // Verify that the shift amount VT is bit enough to hold valid shift
3287 // amounts. This catches things like trying to shift an i1024 value by an
3288 // i8, which is easy to fall into in generic code that uses
3289 // TLI.getShiftAmount().
3290 assert(N2.getValueType().getSizeInBits() >=
3291 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3292 "Invalid use of small shift amount with oversized value!");
3294 // Always fold shifts of i1 values so the code generator doesn't need to
3295 // handle them. Since we know the size of the shift has to be less than the
3296 // size of the value, the shift/rotate count is guaranteed to be zero.
3299 if (N2C && N2C->isNullValue())
3302 case ISD::FP_ROUND_INREG: {
3303 EVT EVT = cast<VTSDNode>(N2)->getVT();
3304 assert(VT == N1.getValueType() && "Not an inreg round!");
3305 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3306 "Cannot FP_ROUND_INREG integer types");
3307 assert(EVT.isVector() == VT.isVector() &&
3308 "FP_ROUND_INREG type should be vector iff the operand "
3310 assert((!EVT.isVector() ||
3311 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3312 "Vector element counts must match in FP_ROUND_INREG");
3313 assert(EVT.bitsLE(VT) && "Not rounding down!");
3315 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3319 assert(VT.isFloatingPoint() &&
3320 N1.getValueType().isFloatingPoint() &&
3321 VT.bitsLE(N1.getValueType()) &&
3322 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3323 if (N1.getValueType() == VT) return N1; // noop conversion.
3325 case ISD::AssertSext:
3326 case ISD::AssertZext: {
3327 EVT EVT = cast<VTSDNode>(N2)->getVT();
3328 assert(VT == N1.getValueType() && "Not an inreg extend!");
3329 assert(VT.isInteger() && EVT.isInteger() &&
3330 "Cannot *_EXTEND_INREG FP types");
3331 assert(!EVT.isVector() &&
3332 "AssertSExt/AssertZExt type should be the vector element type "
3333 "rather than the vector type!");
3334 assert(EVT.bitsLE(VT) && "Not extending!");
3335 if (VT == EVT) return N1; // noop assertion.
3338 case ISD::SIGN_EXTEND_INREG: {
3339 EVT EVT = cast<VTSDNode>(N2)->getVT();
3340 assert(VT == N1.getValueType() && "Not an inreg extend!");
3341 assert(VT.isInteger() && EVT.isInteger() &&
3342 "Cannot *_EXTEND_INREG FP types");
3343 assert(EVT.isVector() == VT.isVector() &&
3344 "SIGN_EXTEND_INREG type should be vector iff the operand "
3346 assert((!EVT.isVector() ||
3347 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3348 "Vector element counts must match in SIGN_EXTEND_INREG");
3349 assert(EVT.bitsLE(VT) && "Not extending!");
3350 if (EVT == VT) return N1; // Not actually extending
3353 APInt Val = N1C->getAPIntValue();
3354 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3355 Val <<= Val.getBitWidth()-FromBits;
3356 Val = Val.ashr(Val.getBitWidth()-FromBits);
3357 return getConstant(Val, VT);
3361 case ISD::EXTRACT_VECTOR_ELT:
3362 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3363 if (N1.getOpcode() == ISD::UNDEF)
3364 return getUNDEF(VT);
3366 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3367 // expanding copies of large vectors from registers.
3369 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3370 N1.getNumOperands() > 0) {
3372 N1.getOperand(0).getValueType().getVectorNumElements();
3373 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3374 N1.getOperand(N2C->getZExtValue() / Factor),
3375 getConstant(N2C->getZExtValue() % Factor,
3376 N2.getValueType()));
3379 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3380 // expanding large vector constants.
3381 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3382 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3384 if (VT != Elt.getValueType())
3385 // If the vector element type is not legal, the BUILD_VECTOR operands
3386 // are promoted and implicitly truncated, and the result implicitly
3387 // extended. Make that explicit here.
3388 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3393 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3394 // operations are lowered to scalars.
3395 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3396 // If the indices are the same, return the inserted element else
3397 // if the indices are known different, extract the element from
3398 // the original vector.
3399 SDValue N1Op2 = N1.getOperand(2);
3400 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3402 if (N1Op2C && N2C) {
3403 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3404 if (VT == N1.getOperand(1).getValueType())
3405 return N1.getOperand(1);
3407 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3410 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3414 case ISD::EXTRACT_ELEMENT:
3415 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3416 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3417 (N1.getValueType().isInteger() == VT.isInteger()) &&
3418 N1.getValueType() != VT &&
3419 "Wrong types for EXTRACT_ELEMENT!");
3421 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3422 // 64-bit integers into 32-bit parts. Instead of building the extract of
3423 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3424 if (N1.getOpcode() == ISD::BUILD_PAIR)
3425 return N1.getOperand(N2C->getZExtValue());
3427 // EXTRACT_ELEMENT of a constant int is also very common.
3428 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3429 unsigned ElementSize = VT.getSizeInBits();
3430 unsigned Shift = ElementSize * N2C->getZExtValue();
3431 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3432 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3435 case ISD::EXTRACT_SUBVECTOR: {
3437 if (VT.isSimple() && N1.getValueType().isSimple()) {
3438 assert(VT.isVector() && N1.getValueType().isVector() &&
3439 "Extract subvector VTs must be a vectors!");
3440 assert(VT.getVectorElementType() ==
3441 N1.getValueType().getVectorElementType() &&
3442 "Extract subvector VTs must have the same element type!");
3443 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3444 "Extract subvector must be from larger vector to smaller vector!");
3446 if (isa<ConstantSDNode>(Index.getNode())) {
3447 assert((VT.getVectorNumElements() +
3448 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3449 <= N1.getValueType().getVectorNumElements())
3450 && "Extract subvector overflow!");
3453 // Trivial extraction.
3454 if (VT.getSimpleVT() == N1.getSimpleValueType())
3461 // Perform trivial constant folding.
3463 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3466 // Canonicalize constant to RHS if commutative.
3467 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3468 std::swap(N1C, N2C);
3472 // Constant fold FP operations.
3473 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3474 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3475 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3477 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3478 // Canonicalize constant to RHS if commutative.
3479 std::swap(N1CFP, N2CFP);
3482 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3483 APFloat::opStatus s;
3486 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3487 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3488 return getConstantFP(V1, VT);
3491 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3492 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3493 return getConstantFP(V1, VT);
3496 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3497 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3498 return getConstantFP(V1, VT);
3501 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3502 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3503 s!=APFloat::opDivByZero)) {
3504 return getConstantFP(V1, VT);
3508 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3509 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3510 s!=APFloat::opDivByZero)) {
3511 return getConstantFP(V1, VT);
3514 case ISD::FCOPYSIGN:
3516 return getConstantFP(V1, VT);
3521 if (Opcode == ISD::FP_ROUND) {
3522 APFloat V = N1CFP->getValueAPF(); // make copy
3524 // This can return overflow, underflow, or inexact; we don't care.
3525 // FIXME need to be more flexible about rounding mode.
3526 (void)V.convert(EVTToAPFloatSemantics(VT),
3527 APFloat::rmNearestTiesToEven, &ignored);
3528 return getConstantFP(V, VT);
3532 // Canonicalize an UNDEF to the RHS, even over a constant.
3533 if (N1.getOpcode() == ISD::UNDEF) {
3534 if (isCommutativeBinOp(Opcode)) {
3538 case ISD::FP_ROUND_INREG:
3539 case ISD::SIGN_EXTEND_INREG:
3545 return N1; // fold op(undef, arg2) -> undef
3553 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3554 // For vectors, we can't easily build an all zero vector, just return
3561 // Fold a bunch of operators when the RHS is undef.
3562 if (N2.getOpcode() == ISD::UNDEF) {
3565 if (N1.getOpcode() == ISD::UNDEF)
3566 // Handle undef ^ undef -> 0 special case. This is a common
3568 return getConstant(0, VT);
3578 return N2; // fold op(arg1, undef) -> undef
3584 if (getTarget().Options.UnsafeFPMath)
3592 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3593 // For vectors, we can't easily build an all zero vector, just return
3598 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3599 // For vectors, we can't easily build an all one vector, just return
3607 // Memoize this node if possible.
3609 SDVTList VTs = getVTList(VT);
3610 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3611 if (VT != MVT::Glue) {
3612 SDValue Ops[] = {N1, N2};
3613 FoldingSetNodeID ID;
3614 AddNodeIDNode(ID, Opcode, VTs, Ops);
3616 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3618 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3619 return SDValue(E, 0);
3621 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3623 CSEMap.InsertNode(N, IP);
3626 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3630 return SDValue(N, 0);
3633 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3634 SDValue N1, SDValue N2, SDValue N3) {
3635 // Perform various simplifications.
3636 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3639 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3640 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3641 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3642 if (N1CFP && N2CFP && N3CFP) {
3643 APFloat V1 = N1CFP->getValueAPF();
3644 const APFloat &V2 = N2CFP->getValueAPF();
3645 const APFloat &V3 = N3CFP->getValueAPF();
3646 APFloat::opStatus s =
3647 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3648 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3649 return getConstantFP(V1, VT);
3653 case ISD::CONCAT_VECTORS:
3654 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3655 // one big BUILD_VECTOR.
3656 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3657 N2.getOpcode() == ISD::BUILD_VECTOR &&
3658 N3.getOpcode() == ISD::BUILD_VECTOR) {
3659 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3660 N1.getNode()->op_end());
3661 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3662 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3663 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3667 // Use FoldSetCC to simplify SETCC's.
3668 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3669 if (Simp.getNode()) return Simp;
3674 if (N1C->getZExtValue())
3675 return N2; // select true, X, Y -> X
3676 return N3; // select false, X, Y -> Y
3679 if (N2 == N3) return N2; // select C, X, X -> X
3681 case ISD::VECTOR_SHUFFLE:
3682 llvm_unreachable("should use getVectorShuffle constructor!");
3683 case ISD::INSERT_SUBVECTOR: {
3685 if (VT.isSimple() && N1.getValueType().isSimple()
3686 && N2.getValueType().isSimple()) {
3687 assert(VT.isVector() && N1.getValueType().isVector() &&
3688 N2.getValueType().isVector() &&
3689 "Insert subvector VTs must be a vectors");
3690 assert(VT == N1.getValueType() &&
3691 "Dest and insert subvector source types must match!");
3692 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3693 "Insert subvector must be from smaller vector to larger vector!");
3694 if (isa<ConstantSDNode>(Index.getNode())) {
3695 assert((N2.getValueType().getVectorNumElements() +
3696 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3697 <= VT.getVectorNumElements())
3698 && "Insert subvector overflow!");
3701 // Trivial insertion.
3702 if (VT.getSimpleVT() == N2.getSimpleValueType())
3708 // Fold bit_convert nodes from a type to themselves.
3709 if (N1.getValueType() == VT)
3714 // Memoize node if it doesn't produce a flag.
3716 SDVTList VTs = getVTList(VT);
3717 if (VT != MVT::Glue) {
3718 SDValue Ops[] = { N1, N2, N3 };
3719 FoldingSetNodeID ID;
3720 AddNodeIDNode(ID, Opcode, VTs, Ops);
3722 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3723 return SDValue(E, 0);
3725 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3726 DL.getDebugLoc(), VTs, N1, N2, N3);
3727 CSEMap.InsertNode(N, IP);
3729 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3730 DL.getDebugLoc(), VTs, N1, N2, N3);
3734 return SDValue(N, 0);
3737 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3738 SDValue N1, SDValue N2, SDValue N3,
3740 SDValue Ops[] = { N1, N2, N3, N4 };
3741 return getNode(Opcode, DL, VT, Ops);
3744 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3745 SDValue N1, SDValue N2, SDValue N3,
3746 SDValue N4, SDValue N5) {
3747 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3748 return getNode(Opcode, DL, VT, Ops);
3751 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3752 /// the incoming stack arguments to be loaded from the stack.
3753 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3754 SmallVector<SDValue, 8> ArgChains;
3756 // Include the original chain at the beginning of the list. When this is
3757 // used by target LowerCall hooks, this helps legalize find the
3758 // CALLSEQ_BEGIN node.
3759 ArgChains.push_back(Chain);
3761 // Add a chain value for each stack argument.
3762 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3763 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3764 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3765 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3766 if (FI->getIndex() < 0)
3767 ArgChains.push_back(SDValue(L, 1));
3769 // Build a tokenfactor for all the chains.
3770 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3773 /// getMemsetValue - Vectorized representation of the memset value
3775 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3777 assert(Value.getOpcode() != ISD::UNDEF);
3779 unsigned NumBits = VT.getScalarType().getSizeInBits();
3780 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3781 assert(C->getAPIntValue().getBitWidth() == 8);
3782 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3784 return DAG.getConstant(Val, VT);
3785 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3788 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3790 // Use a multiplication with 0x010101... to extend the input to the
3792 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3793 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3799 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3800 /// used when a memcpy is turned into a memset when the source is a constant
3802 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3803 const TargetLowering &TLI, StringRef Str) {
3804 // Handle vector with all elements zero.
3807 return DAG.getConstant(0, VT);
3808 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3809 return DAG.getConstantFP(0.0, VT);
3810 else if (VT.isVector()) {
3811 unsigned NumElts = VT.getVectorNumElements();
3812 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3813 return DAG.getNode(ISD::BITCAST, dl, VT,
3814 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3817 llvm_unreachable("Expected type!");
3820 assert(!VT.isVector() && "Can't handle vector type here!");
3821 unsigned NumVTBits = VT.getSizeInBits();
3822 unsigned NumVTBytes = NumVTBits / 8;
3823 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3825 APInt Val(NumVTBits, 0);
3826 if (TLI.isLittleEndian()) {
3827 for (unsigned i = 0; i != NumBytes; ++i)
3828 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3830 for (unsigned i = 0; i != NumBytes; ++i)
3831 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3834 // If the "cost" of materializing the integer immediate is less than the cost
3835 // of a load, then it is cost effective to turn the load into the immediate.
3836 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3837 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3838 return DAG.getConstant(Val, VT);
3839 return SDValue(nullptr, 0);
3842 /// getMemBasePlusOffset - Returns base and offset node for the
3844 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3845 SelectionDAG &DAG) {
3846 EVT VT = Base.getValueType();
3847 return DAG.getNode(ISD::ADD, dl,
3848 VT, Base, DAG.getConstant(Offset, VT));
3851 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3853 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3854 unsigned SrcDelta = 0;
3855 GlobalAddressSDNode *G = nullptr;
3856 if (Src.getOpcode() == ISD::GlobalAddress)
3857 G = cast<GlobalAddressSDNode>(Src);
3858 else if (Src.getOpcode() == ISD::ADD &&
3859 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3860 Src.getOperand(1).getOpcode() == ISD::Constant) {
3861 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3862 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3867 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3870 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3871 /// to replace the memset / memcpy. Return true if the number of memory ops
3872 /// is below the threshold. It returns the types of the sequence of
3873 /// memory ops to perform memset / memcpy by reference.
3874 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3875 unsigned Limit, uint64_t Size,
3876 unsigned DstAlign, unsigned SrcAlign,
3882 const TargetLowering &TLI) {
3883 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3884 "Expecting memcpy / memset source to meet alignment requirement!");
3885 // If 'SrcAlign' is zero, that means the memory operation does not need to
3886 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3887 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3888 // is the specified alignment of the memory operation. If it is zero, that
3889 // means it's possible to change the alignment of the destination.
3890 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3891 // not need to be loaded.
3892 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3893 IsMemset, ZeroMemset, MemcpyStrSrc,
3894 DAG.getMachineFunction());
3896 if (VT == MVT::Other) {
3898 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3899 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3900 VT = TLI.getPointerTy();
3902 switch (DstAlign & 7) {
3903 case 0: VT = MVT::i64; break;
3904 case 4: VT = MVT::i32; break;
3905 case 2: VT = MVT::i16; break;
3906 default: VT = MVT::i8; break;
3911 while (!TLI.isTypeLegal(LVT))
3912 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3913 assert(LVT.isInteger());
3919 unsigned NumMemOps = 0;
3921 unsigned VTSize = VT.getSizeInBits() / 8;
3922 while (VTSize > Size) {
3923 // For now, only use non-vector load / store's for the left-over pieces.
3928 if (VT.isVector() || VT.isFloatingPoint()) {
3929 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3930 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3931 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3933 else if (NewVT == MVT::i64 &&
3934 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3935 TLI.isSafeMemOpType(MVT::f64)) {
3936 // i64 is usually not legal on 32-bit targets, but f64 may be.
3944 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3945 if (NewVT == MVT::i8)
3947 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3949 NewVTSize = NewVT.getSizeInBits() / 8;
3951 // If the new VT cannot cover all of the remaining bits, then consider
3952 // issuing a (or a pair of) unaligned and overlapping load / store.
3953 // FIXME: Only does this for 64-bit or more since we don't have proper
3954 // cost model for unaligned load / store.
3957 if (NumMemOps && AllowOverlap &&
3958 VTSize >= 8 && NewVTSize < Size &&
3959 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3967 if (++NumMemOps > Limit)
3970 MemOps.push_back(VT);
3977 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3978 SDValue Chain, SDValue Dst,
3979 SDValue Src, uint64_t Size,
3980 unsigned Align, bool isVol,
3982 MachinePointerInfo DstPtrInfo,
3983 MachinePointerInfo SrcPtrInfo) {
3984 // Turn a memcpy of undef to nop.
3985 if (Src.getOpcode() == ISD::UNDEF)
3988 // Expand memcpy to a series of load and store ops if the size operand falls
3989 // below a certain threshold.
3990 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3991 // rather than maybe a humongous number of loads and stores.
3992 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3993 std::vector<EVT> MemOps;
3994 bool DstAlignCanChange = false;
3995 MachineFunction &MF = DAG.getMachineFunction();
3996 MachineFrameInfo *MFI = MF.getFrameInfo();
3997 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
3998 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3999 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4000 DstAlignCanChange = true;
4001 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4002 if (Align > SrcAlign)
4005 bool CopyFromStr = isMemSrcFromString(Src, Str);
4006 bool isZeroStr = CopyFromStr && Str.empty();
4007 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4009 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4010 (DstAlignCanChange ? 0 : Align),
4011 (isZeroStr ? 0 : SrcAlign),
4012 false, false, CopyFromStr, true, DAG, TLI))
4015 if (DstAlignCanChange) {
4016 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4017 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4019 // Don't promote to an alignment that would require dynamic stack
4021 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4022 if (!TRI->needsStackRealignment(MF))
4023 while (NewAlign > Align &&
4024 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4027 if (NewAlign > Align) {
4028 // Give the stack frame object a larger alignment if needed.
4029 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4030 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4035 SmallVector<SDValue, 8> OutChains;
4036 unsigned NumMemOps = MemOps.size();
4037 uint64_t SrcOff = 0, DstOff = 0;
4038 for (unsigned i = 0; i != NumMemOps; ++i) {
4040 unsigned VTSize = VT.getSizeInBits() / 8;
4041 SDValue Value, Store;
4043 if (VTSize > Size) {
4044 // Issuing an unaligned load / store pair that overlaps with the previous
4045 // pair. Adjust the offset accordingly.
4046 assert(i == NumMemOps-1 && i != 0);
4047 SrcOff -= VTSize - Size;
4048 DstOff -= VTSize - Size;
4052 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4053 // It's unlikely a store of a vector immediate can be done in a single
4054 // instruction. It would require a load from a constantpool first.
4055 // We only handle zero vectors here.
4056 // FIXME: Handle other cases where store of vector immediate is done in
4057 // a single instruction.
4058 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4059 if (Value.getNode())
4060 Store = DAG.getStore(Chain, dl, Value,
4061 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4062 DstPtrInfo.getWithOffset(DstOff), isVol,
4066 if (!Store.getNode()) {
4067 // The type might not be legal for the target. This should only happen
4068 // if the type is smaller than a legal type, as on PPC, so the right
4069 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4070 // to Load/Store if NVT==VT.
4071 // FIXME does the case above also need this?
4072 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4073 assert(NVT.bitsGE(VT));
4074 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4075 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4076 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4077 false, MinAlign(SrcAlign, SrcOff));
4078 Store = DAG.getTruncStore(Chain, dl, Value,
4079 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4080 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4083 OutChains.push_back(Store);
4089 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4092 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4093 SDValue Chain, SDValue Dst,
4094 SDValue Src, uint64_t Size,
4095 unsigned Align, bool isVol,
4097 MachinePointerInfo DstPtrInfo,
4098 MachinePointerInfo SrcPtrInfo) {
4099 // Turn a memmove of undef to nop.
4100 if (Src.getOpcode() == ISD::UNDEF)
4103 // Expand memmove to a series of load and store ops if the size operand falls
4104 // below a certain threshold.
4105 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4106 std::vector<EVT> MemOps;
4107 bool DstAlignCanChange = false;
4108 MachineFunction &MF = DAG.getMachineFunction();
4109 MachineFrameInfo *MFI = MF.getFrameInfo();
4110 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4111 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4112 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4113 DstAlignCanChange = true;
4114 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4115 if (Align > SrcAlign)
4117 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4119 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4120 (DstAlignCanChange ? 0 : Align), SrcAlign,
4121 false, false, false, false, DAG, TLI))
4124 if (DstAlignCanChange) {
4125 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4126 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4127 if (NewAlign > Align) {
4128 // Give the stack frame object a larger alignment if needed.
4129 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4130 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4135 uint64_t SrcOff = 0, DstOff = 0;
4136 SmallVector<SDValue, 8> LoadValues;
4137 SmallVector<SDValue, 8> LoadChains;
4138 SmallVector<SDValue, 8> OutChains;
4139 unsigned NumMemOps = MemOps.size();
4140 for (unsigned i = 0; i < NumMemOps; i++) {
4142 unsigned VTSize = VT.getSizeInBits() / 8;
4145 Value = DAG.getLoad(VT, dl, Chain,
4146 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4147 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4148 false, false, SrcAlign);
4149 LoadValues.push_back(Value);
4150 LoadChains.push_back(Value.getValue(1));
4153 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4155 for (unsigned i = 0; i < NumMemOps; i++) {
4157 unsigned VTSize = VT.getSizeInBits() / 8;
4160 Store = DAG.getStore(Chain, dl, LoadValues[i],
4161 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4162 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4163 OutChains.push_back(Store);
4167 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4170 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4173 /// \param DAG Selection DAG where lowered code is placed.
4174 /// \param dl Link to corresponding IR location.
4175 /// \param Chain Control flow dependency.
4176 /// \param Dst Pointer to destination memory location.
4177 /// \param Src Value of byte to write into the memory.
4178 /// \param Size Number of bytes to write.
4179 /// \param Align Alignment of the destination in bytes.
4180 /// \param isVol True if destination is volatile.
4181 /// \param DstPtrInfo IR information on the memory pointer.
4182 /// \returns New head in the control flow, if lowering was successful, empty
4183 /// SDValue otherwise.
4185 /// The function tries to replace 'llvm.memset' intrinsic with several store
4186 /// operations and value calculation code. This is usually profitable for small
4188 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4189 SDValue Chain, SDValue Dst,
4190 SDValue Src, uint64_t Size,
4191 unsigned Align, bool isVol,
4192 MachinePointerInfo DstPtrInfo) {
4193 // Turn a memset of undef to nop.
4194 if (Src.getOpcode() == ISD::UNDEF)
4197 // Expand memset to a series of load/store ops if the size operand
4198 // falls below a certain threshold.
4199 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4200 std::vector<EVT> MemOps;
4201 bool DstAlignCanChange = false;
4202 MachineFunction &MF = DAG.getMachineFunction();
4203 MachineFrameInfo *MFI = MF.getFrameInfo();
4204 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4205 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4206 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4207 DstAlignCanChange = true;
4209 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4210 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4211 Size, (DstAlignCanChange ? 0 : Align), 0,
4212 true, IsZeroVal, false, true, DAG, TLI))
4215 if (DstAlignCanChange) {
4216 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4217 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4218 if (NewAlign > Align) {
4219 // Give the stack frame object a larger alignment if needed.
4220 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4221 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4226 SmallVector<SDValue, 8> OutChains;
4227 uint64_t DstOff = 0;
4228 unsigned NumMemOps = MemOps.size();
4230 // Find the largest store and generate the bit pattern for it.
4231 EVT LargestVT = MemOps[0];
4232 for (unsigned i = 1; i < NumMemOps; i++)
4233 if (MemOps[i].bitsGT(LargestVT))
4234 LargestVT = MemOps[i];
4235 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4237 for (unsigned i = 0; i < NumMemOps; i++) {
4239 unsigned VTSize = VT.getSizeInBits() / 8;
4240 if (VTSize > Size) {
4241 // Issuing an unaligned load / store pair that overlaps with the previous
4242 // pair. Adjust the offset accordingly.
4243 assert(i == NumMemOps-1 && i != 0);
4244 DstOff -= VTSize - Size;
4247 // If this store is smaller than the largest store see whether we can get
4248 // the smaller value for free with a truncate.
4249 SDValue Value = MemSetValue;
4250 if (VT.bitsLT(LargestVT)) {
4251 if (!LargestVT.isVector() && !VT.isVector() &&
4252 TLI.isTruncateFree(LargestVT, VT))
4253 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4255 Value = getMemsetValue(Src, VT, DAG, dl);
4257 assert(Value.getValueType() == VT && "Value with wrong type.");
4258 SDValue Store = DAG.getStore(Chain, dl, Value,
4259 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4260 DstPtrInfo.getWithOffset(DstOff),
4261 isVol, false, Align);
4262 OutChains.push_back(Store);
4263 DstOff += VT.getSizeInBits() / 8;
4267 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4270 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4271 SDValue Src, SDValue Size,
4272 unsigned Align, bool isVol, bool AlwaysInline,
4273 MachinePointerInfo DstPtrInfo,
4274 MachinePointerInfo SrcPtrInfo) {
4275 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4277 // Check to see if we should lower the memcpy to loads and stores first.
4278 // For cases within the target-specified limits, this is the best choice.
4279 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4281 // Memcpy with size zero? Just return the original chain.
4282 if (ConstantSize->isNullValue())
4285 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4286 ConstantSize->getZExtValue(),Align,
4287 isVol, false, DstPtrInfo, SrcPtrInfo);
4288 if (Result.getNode())
4292 // Then check to see if we should lower the memcpy with target-specific
4293 // code. If the target chooses to do this, this is the next best.
4295 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4296 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4297 DstPtrInfo, SrcPtrInfo);
4298 if (Result.getNode())
4302 // If we really need inline code and the target declined to provide it,
4303 // use a (potentially long) sequence of loads and stores.
4305 assert(ConstantSize && "AlwaysInline requires a constant size!");
4306 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4307 ConstantSize->getZExtValue(), Align, isVol,
4308 true, DstPtrInfo, SrcPtrInfo);
4311 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4312 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4313 // respect volatile, so they may do things like read or write memory
4314 // beyond the given memory regions. But fixing this isn't easy, and most
4315 // people don't care.
4317 // Emit a library call.
4318 TargetLowering::ArgListTy Args;
4319 TargetLowering::ArgListEntry Entry;
4320 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4321 Entry.Node = Dst; Args.push_back(Entry);
4322 Entry.Node = Src; Args.push_back(Entry);
4323 Entry.Node = Size; Args.push_back(Entry);
4324 // FIXME: pass in SDLoc
4325 TargetLowering::CallLoweringInfo CLI(*this);
4326 CLI.setDebugLoc(dl).setChain(Chain)
4327 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4328 Type::getVoidTy(*getContext()),
4329 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4330 TLI->getPointerTy()), std::move(Args), 0)
4331 .setDiscardResult();
4332 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4334 return CallResult.second;
4337 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4338 SDValue Src, SDValue Size,
4339 unsigned Align, bool isVol,
4340 MachinePointerInfo DstPtrInfo,
4341 MachinePointerInfo SrcPtrInfo) {
4342 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4344 // Check to see if we should lower the memmove to loads and stores first.
4345 // For cases within the target-specified limits, this is the best choice.
4346 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4348 // Memmove with size zero? Just return the original chain.
4349 if (ConstantSize->isNullValue())
4353 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4354 ConstantSize->getZExtValue(), Align, isVol,
4355 false, DstPtrInfo, SrcPtrInfo);
4356 if (Result.getNode())
4360 // Then check to see if we should lower the memmove with target-specific
4361 // code. If the target chooses to do this, this is the next best.
4363 SDValue Result = TSI->EmitTargetCodeForMemmove(
4364 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4365 if (Result.getNode())
4369 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4370 // not be safe. See memcpy above for more details.
4372 // Emit a library call.
4373 TargetLowering::ArgListTy Args;
4374 TargetLowering::ArgListEntry Entry;
4375 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4376 Entry.Node = Dst; Args.push_back(Entry);
4377 Entry.Node = Src; Args.push_back(Entry);
4378 Entry.Node = Size; Args.push_back(Entry);
4379 // FIXME: pass in SDLoc
4380 TargetLowering::CallLoweringInfo CLI(*this);
4381 CLI.setDebugLoc(dl).setChain(Chain)
4382 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4383 Type::getVoidTy(*getContext()),
4384 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4385 TLI->getPointerTy()), std::move(Args), 0)
4386 .setDiscardResult();
4387 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4389 return CallResult.second;
4392 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4393 SDValue Src, SDValue Size,
4394 unsigned Align, bool isVol,
4395 MachinePointerInfo DstPtrInfo) {
4396 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4398 // Check to see if we should lower the memset to stores first.
4399 // For cases within the target-specified limits, this is the best choice.
4400 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4402 // Memset with size zero? Just return the original chain.
4403 if (ConstantSize->isNullValue())
4407 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4408 Align, isVol, DstPtrInfo);
4410 if (Result.getNode())
4414 // Then check to see if we should lower the memset with target-specific
4415 // code. If the target chooses to do this, this is the next best.
4417 SDValue Result = TSI->EmitTargetCodeForMemset(
4418 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4419 if (Result.getNode())
4423 // Emit a library call.
4424 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4425 TargetLowering::ArgListTy Args;
4426 TargetLowering::ArgListEntry Entry;
4427 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4428 Args.push_back(Entry);
4430 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4431 Args.push_back(Entry);
4433 Entry.Ty = IntPtrTy;
4434 Args.push_back(Entry);
4436 // FIXME: pass in SDLoc
4437 TargetLowering::CallLoweringInfo CLI(*this);
4438 CLI.setDebugLoc(dl).setChain(Chain)
4439 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4440 Type::getVoidTy(*getContext()),
4441 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4442 TLI->getPointerTy()), std::move(Args), 0)
4443 .setDiscardResult();
4445 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4446 return CallResult.second;
4449 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4450 SDVTList VTList, ArrayRef<SDValue> Ops,
4451 MachineMemOperand *MMO,
4452 AtomicOrdering SuccessOrdering,
4453 AtomicOrdering FailureOrdering,
4454 SynchronizationScope SynchScope) {
4455 FoldingSetNodeID ID;
4456 ID.AddInteger(MemVT.getRawBits());
4457 AddNodeIDNode(ID, Opcode, VTList, Ops);
4458 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4460 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4461 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4462 return SDValue(E, 0);
4465 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4466 // SDNode doesn't have access to it. This memory will be "leaked" when
4467 // the node is deallocated, but recovered when the allocator is released.
4468 // If the number of operands is less than 5 we use AtomicSDNode's internal
4470 unsigned NumOps = Ops.size();
4471 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4474 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4475 dl.getDebugLoc(), VTList, MemVT,
4476 Ops.data(), DynOps, NumOps, MMO,
4477 SuccessOrdering, FailureOrdering,
4479 CSEMap.InsertNode(N, IP);
4481 return SDValue(N, 0);
4484 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4485 SDVTList VTList, ArrayRef<SDValue> Ops,
4486 MachineMemOperand *MMO,
4487 AtomicOrdering Ordering,
4488 SynchronizationScope SynchScope) {
4489 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4490 Ordering, SynchScope);
4493 SDValue SelectionDAG::getAtomicCmpSwap(
4494 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4495 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4496 unsigned Alignment, AtomicOrdering SuccessOrdering,
4497 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4498 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4499 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4500 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4502 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4503 Alignment = getEVTAlignment(MemVT);
4505 MachineFunction &MF = getMachineFunction();
4507 // FIXME: Volatile isn't really correct; we should keep track of atomic
4508 // orderings in the memoperand.
4509 unsigned Flags = MachineMemOperand::MOVolatile;
4510 Flags |= MachineMemOperand::MOLoad;
4511 Flags |= MachineMemOperand::MOStore;
4513 MachineMemOperand *MMO =
4514 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4516 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4517 SuccessOrdering, FailureOrdering, SynchScope);
4520 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4521 SDVTList VTs, SDValue Chain, SDValue Ptr,
4522 SDValue Cmp, SDValue Swp,
4523 MachineMemOperand *MMO,
4524 AtomicOrdering SuccessOrdering,
4525 AtomicOrdering FailureOrdering,
4526 SynchronizationScope SynchScope) {
4527 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4528 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4529 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4531 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4532 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4533 SuccessOrdering, FailureOrdering, SynchScope);
4536 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4538 SDValue Ptr, SDValue Val,
4539 const Value* PtrVal,
4541 AtomicOrdering Ordering,
4542 SynchronizationScope SynchScope) {
4543 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4544 Alignment = getEVTAlignment(MemVT);
4546 MachineFunction &MF = getMachineFunction();
4547 // An atomic store does not load. An atomic load does not store.
4548 // (An atomicrmw obviously both loads and stores.)
4549 // For now, atomics are considered to be volatile always, and they are
4551 // FIXME: Volatile isn't really correct; we should keep track of atomic
4552 // orderings in the memoperand.
4553 unsigned Flags = MachineMemOperand::MOVolatile;
4554 if (Opcode != ISD::ATOMIC_STORE)
4555 Flags |= MachineMemOperand::MOLoad;
4556 if (Opcode != ISD::ATOMIC_LOAD)
4557 Flags |= MachineMemOperand::MOStore;
4559 MachineMemOperand *MMO =
4560 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4561 MemVT.getStoreSize(), Alignment);
4563 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4564 Ordering, SynchScope);
4567 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4569 SDValue Ptr, SDValue Val,
4570 MachineMemOperand *MMO,
4571 AtomicOrdering Ordering,
4572 SynchronizationScope SynchScope) {
4573 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4574 Opcode == ISD::ATOMIC_LOAD_SUB ||
4575 Opcode == ISD::ATOMIC_LOAD_AND ||
4576 Opcode == ISD::ATOMIC_LOAD_OR ||
4577 Opcode == ISD::ATOMIC_LOAD_XOR ||
4578 Opcode == ISD::ATOMIC_LOAD_NAND ||
4579 Opcode == ISD::ATOMIC_LOAD_MIN ||
4580 Opcode == ISD::ATOMIC_LOAD_MAX ||
4581 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4582 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4583 Opcode == ISD::ATOMIC_SWAP ||
4584 Opcode == ISD::ATOMIC_STORE) &&
4585 "Invalid Atomic Op");
4587 EVT VT = Val.getValueType();
4589 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4590 getVTList(VT, MVT::Other);
4591 SDValue Ops[] = {Chain, Ptr, Val};
4592 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4595 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4596 EVT VT, SDValue Chain,
4598 MachineMemOperand *MMO,
4599 AtomicOrdering Ordering,
4600 SynchronizationScope SynchScope) {
4601 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4603 SDVTList VTs = getVTList(VT, MVT::Other);
4604 SDValue Ops[] = {Chain, Ptr};
4605 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4608 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4609 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4610 if (Ops.size() == 1)
4613 SmallVector<EVT, 4> VTs;
4614 VTs.reserve(Ops.size());
4615 for (unsigned i = 0; i < Ops.size(); ++i)
4616 VTs.push_back(Ops[i].getValueType());
4617 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4621 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4622 ArrayRef<SDValue> Ops,
4623 EVT MemVT, MachinePointerInfo PtrInfo,
4624 unsigned Align, bool Vol,
4625 bool ReadMem, bool WriteMem, unsigned Size) {
4626 if (Align == 0) // Ensure that codegen never sees alignment 0
4627 Align = getEVTAlignment(MemVT);
4629 MachineFunction &MF = getMachineFunction();
4632 Flags |= MachineMemOperand::MOStore;
4634 Flags |= MachineMemOperand::MOLoad;
4636 Flags |= MachineMemOperand::MOVolatile;
4638 Size = MemVT.getStoreSize();
4639 MachineMemOperand *MMO =
4640 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4642 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4646 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4647 ArrayRef<SDValue> Ops, EVT MemVT,
4648 MachineMemOperand *MMO) {
4649 assert((Opcode == ISD::INTRINSIC_VOID ||
4650 Opcode == ISD::INTRINSIC_W_CHAIN ||
4651 Opcode == ISD::PREFETCH ||
4652 Opcode == ISD::LIFETIME_START ||
4653 Opcode == ISD::LIFETIME_END ||
4654 (Opcode <= INT_MAX &&
4655 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4656 "Opcode is not a memory-accessing opcode!");
4658 // Memoize the node unless it returns a flag.
4659 MemIntrinsicSDNode *N;
4660 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4661 FoldingSetNodeID ID;
4662 AddNodeIDNode(ID, Opcode, VTList, Ops);
4663 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4665 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4666 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4667 return SDValue(E, 0);
4670 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4671 dl.getDebugLoc(), VTList, Ops,
4673 CSEMap.InsertNode(N, IP);
4675 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4676 dl.getDebugLoc(), VTList, Ops,
4680 return SDValue(N, 0);
4683 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4684 /// MachinePointerInfo record from it. This is particularly useful because the
4685 /// code generator has many cases where it doesn't bother passing in a
4686 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4687 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4688 // If this is FI+Offset, we can model it.
4689 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4690 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4692 // If this is (FI+Offset1)+Offset2, we can model it.
4693 if (Ptr.getOpcode() != ISD::ADD ||
4694 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4695 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4696 return MachinePointerInfo();
4698 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4699 return MachinePointerInfo::getFixedStack(FI, Offset+
4700 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4703 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4704 /// MachinePointerInfo record from it. This is particularly useful because the
4705 /// code generator has many cases where it doesn't bother passing in a
4706 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4707 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4708 // If the 'Offset' value isn't a constant, we can't handle this.
4709 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4710 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4711 if (OffsetOp.getOpcode() == ISD::UNDEF)
4712 return InferPointerInfo(Ptr);
4713 return MachinePointerInfo();
4718 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4719 EVT VT, SDLoc dl, SDValue Chain,
4720 SDValue Ptr, SDValue Offset,
4721 MachinePointerInfo PtrInfo, EVT MemVT,
4722 bool isVolatile, bool isNonTemporal, bool isInvariant,
4723 unsigned Alignment, const AAMDNodes &AAInfo,
4724 const MDNode *Ranges) {
4725 assert(Chain.getValueType() == MVT::Other &&
4726 "Invalid chain type");
4727 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4728 Alignment = getEVTAlignment(VT);
4730 unsigned Flags = MachineMemOperand::MOLoad;
4732 Flags |= MachineMemOperand::MOVolatile;
4734 Flags |= MachineMemOperand::MONonTemporal;
4736 Flags |= MachineMemOperand::MOInvariant;
4738 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4740 if (PtrInfo.V.isNull())
4741 PtrInfo = InferPointerInfo(Ptr, Offset);
4743 MachineFunction &MF = getMachineFunction();
4744 MachineMemOperand *MMO =
4745 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4747 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4751 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4752 EVT VT, SDLoc dl, SDValue Chain,
4753 SDValue Ptr, SDValue Offset, EVT MemVT,
4754 MachineMemOperand *MMO) {
4756 ExtType = ISD::NON_EXTLOAD;
4757 } else if (ExtType == ISD::NON_EXTLOAD) {
4758 assert(VT == MemVT && "Non-extending load from different memory type!");
4761 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4762 "Should only be an extending load, not truncating!");
4763 assert(VT.isInteger() == MemVT.isInteger() &&
4764 "Cannot convert from FP to Int or Int -> FP!");
4765 assert(VT.isVector() == MemVT.isVector() &&
4766 "Cannot use an ext load to convert to or from a vector!");
4767 assert((!VT.isVector() ||
4768 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4769 "Cannot use an ext load to change the number of vector elements!");
4772 bool Indexed = AM != ISD::UNINDEXED;
4773 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4774 "Unindexed load with an offset!");
4776 SDVTList VTs = Indexed ?
4777 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4778 SDValue Ops[] = { Chain, Ptr, Offset };
4779 FoldingSetNodeID ID;
4780 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4781 ID.AddInteger(MemVT.getRawBits());
4782 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4783 MMO->isNonTemporal(),
4784 MMO->isInvariant()));
4785 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4787 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4788 cast<LoadSDNode>(E)->refineAlignment(MMO);
4789 return SDValue(E, 0);
4791 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4792 dl.getDebugLoc(), VTs, AM, ExtType,
4794 CSEMap.InsertNode(N, IP);
4796 return SDValue(N, 0);
4799 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4800 SDValue Chain, SDValue Ptr,
4801 MachinePointerInfo PtrInfo,
4802 bool isVolatile, bool isNonTemporal,
4803 bool isInvariant, unsigned Alignment,
4804 const AAMDNodes &AAInfo,
4805 const MDNode *Ranges) {
4806 SDValue Undef = getUNDEF(Ptr.getValueType());
4807 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4808 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4812 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4813 SDValue Chain, SDValue Ptr,
4814 MachineMemOperand *MMO) {
4815 SDValue Undef = getUNDEF(Ptr.getValueType());
4816 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4820 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4821 SDValue Chain, SDValue Ptr,
4822 MachinePointerInfo PtrInfo, EVT MemVT,
4823 bool isVolatile, bool isNonTemporal,
4824 bool isInvariant, unsigned Alignment,
4825 const AAMDNodes &AAInfo) {
4826 SDValue Undef = getUNDEF(Ptr.getValueType());
4827 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4828 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4833 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4834 SDValue Chain, SDValue Ptr, EVT MemVT,
4835 MachineMemOperand *MMO) {
4836 SDValue Undef = getUNDEF(Ptr.getValueType());
4837 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4842 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4843 SDValue Offset, ISD::MemIndexedMode AM) {
4844 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4845 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4846 "Load is already a indexed load!");
4847 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4848 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4849 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4850 false, LD->getAlignment());
4853 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4854 SDValue Ptr, MachinePointerInfo PtrInfo,
4855 bool isVolatile, bool isNonTemporal,
4856 unsigned Alignment, const AAMDNodes &AAInfo) {
4857 assert(Chain.getValueType() == MVT::Other &&
4858 "Invalid chain type");
4859 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4860 Alignment = getEVTAlignment(Val.getValueType());
4862 unsigned Flags = MachineMemOperand::MOStore;
4864 Flags |= MachineMemOperand::MOVolatile;
4866 Flags |= MachineMemOperand::MONonTemporal;
4868 if (PtrInfo.V.isNull())
4869 PtrInfo = InferPointerInfo(Ptr);
4871 MachineFunction &MF = getMachineFunction();
4872 MachineMemOperand *MMO =
4873 MF.getMachineMemOperand(PtrInfo, Flags,
4874 Val.getValueType().getStoreSize(), Alignment,
4877 return getStore(Chain, dl, Val, Ptr, MMO);
4880 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4881 SDValue Ptr, MachineMemOperand *MMO) {
4882 assert(Chain.getValueType() == MVT::Other &&
4883 "Invalid chain type");
4884 EVT VT = Val.getValueType();
4885 SDVTList VTs = getVTList(MVT::Other);
4886 SDValue Undef = getUNDEF(Ptr.getValueType());
4887 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4888 FoldingSetNodeID ID;
4889 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4890 ID.AddInteger(VT.getRawBits());
4891 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4892 MMO->isNonTemporal(), MMO->isInvariant()));
4893 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4895 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4896 cast<StoreSDNode>(E)->refineAlignment(MMO);
4897 return SDValue(E, 0);
4899 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4900 dl.getDebugLoc(), VTs,
4901 ISD::UNINDEXED, false, VT, MMO);
4902 CSEMap.InsertNode(N, IP);
4904 return SDValue(N, 0);
4907 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4908 SDValue Ptr, MachinePointerInfo PtrInfo,
4909 EVT SVT,bool isVolatile, bool isNonTemporal,
4911 const AAMDNodes &AAInfo) {
4912 assert(Chain.getValueType() == MVT::Other &&
4913 "Invalid chain type");
4914 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4915 Alignment = getEVTAlignment(SVT);
4917 unsigned Flags = MachineMemOperand::MOStore;
4919 Flags |= MachineMemOperand::MOVolatile;
4921 Flags |= MachineMemOperand::MONonTemporal;
4923 if (PtrInfo.V.isNull())
4924 PtrInfo = InferPointerInfo(Ptr);
4926 MachineFunction &MF = getMachineFunction();
4927 MachineMemOperand *MMO =
4928 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4931 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4934 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4935 SDValue Ptr, EVT SVT,
4936 MachineMemOperand *MMO) {
4937 EVT VT = Val.getValueType();
4939 assert(Chain.getValueType() == MVT::Other &&
4940 "Invalid chain type");
4942 return getStore(Chain, dl, Val, Ptr, MMO);
4944 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4945 "Should only be a truncating store, not extending!");
4946 assert(VT.isInteger() == SVT.isInteger() &&
4947 "Can't do FP-INT conversion!");
4948 assert(VT.isVector() == SVT.isVector() &&
4949 "Cannot use trunc store to convert to or from a vector!");
4950 assert((!VT.isVector() ||
4951 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4952 "Cannot use trunc store to change the number of vector elements!");
4954 SDVTList VTs = getVTList(MVT::Other);
4955 SDValue Undef = getUNDEF(Ptr.getValueType());
4956 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4957 FoldingSetNodeID ID;
4958 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4959 ID.AddInteger(SVT.getRawBits());
4960 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4961 MMO->isNonTemporal(), MMO->isInvariant()));
4962 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4964 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4965 cast<StoreSDNode>(E)->refineAlignment(MMO);
4966 return SDValue(E, 0);
4968 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4969 dl.getDebugLoc(), VTs,
4970 ISD::UNINDEXED, true, SVT, MMO);
4971 CSEMap.InsertNode(N, IP);
4973 return SDValue(N, 0);
4977 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4978 SDValue Offset, ISD::MemIndexedMode AM) {
4979 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4980 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4981 "Store is already a indexed store!");
4982 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4983 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4984 FoldingSetNodeID ID;
4985 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4986 ID.AddInteger(ST->getMemoryVT().getRawBits());
4987 ID.AddInteger(ST->getRawSubclassData());
4988 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4990 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4991 return SDValue(E, 0);
4993 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4994 dl.getDebugLoc(), VTs, AM,
4995 ST->isTruncatingStore(),
4997 ST->getMemOperand());
4998 CSEMap.InsertNode(N, IP);
5000 return SDValue(N, 0);
5004 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5005 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5006 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5008 SDVTList VTs = getVTList(VT, MVT::Other);
5009 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5010 FoldingSetNodeID ID;
5011 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5012 ID.AddInteger(VT.getRawBits());
5013 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5015 MMO->isNonTemporal(),
5016 MMO->isInvariant()));
5017 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5019 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5020 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5021 return SDValue(E, 0);
5023 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5024 dl.getDebugLoc(), Ops, 4, VTs,
5026 CSEMap.InsertNode(N, IP);
5028 return SDValue(N, 0);
5031 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5032 SDValue Ptr, SDValue Mask, EVT MemVT,
5033 MachineMemOperand *MMO, bool isTrunc) {
5034 assert(Chain.getValueType() == MVT::Other &&
5035 "Invalid chain type");
5036 EVT VT = Val.getValueType();
5037 SDVTList VTs = getVTList(MVT::Other);
5038 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5039 FoldingSetNodeID ID;
5040 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5041 ID.AddInteger(VT.getRawBits());
5042 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5043 MMO->isNonTemporal(), MMO->isInvariant()));
5044 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5046 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5047 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5048 return SDValue(E, 0);
5050 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5051 dl.getDebugLoc(), Ops, 4,
5052 VTs, isTrunc, MemVT, MMO);
5053 CSEMap.InsertNode(N, IP);
5055 return SDValue(N, 0);
5058 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5059 SDValue Chain, SDValue Ptr,
5062 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5063 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5066 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5067 ArrayRef<SDUse> Ops) {
5068 switch (Ops.size()) {
5069 case 0: return getNode(Opcode, DL, VT);
5070 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(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]);
5076 // Copy from an SDUse array into an SDValue array for use with
5077 // the regular getNode logic.
5078 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5079 return getNode(Opcode, DL, VT, NewOps);
5082 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5083 ArrayRef<SDValue> Ops) {
5084 unsigned NumOps = Ops.size();
5086 case 0: return getNode(Opcode, DL, VT);
5087 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5088 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5089 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5095 case ISD::SELECT_CC: {
5096 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5097 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5098 "LHS and RHS of condition must have same type!");
5099 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5100 "True and False arms of SelectCC must have same type!");
5101 assert(Ops[2].getValueType() == VT &&
5102 "select_cc node must be of same type as true and false value!");
5106 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5107 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5108 "LHS/RHS of comparison should match types!");
5115 SDVTList VTs = getVTList(VT);
5117 if (VT != MVT::Glue) {
5118 FoldingSetNodeID ID;
5119 AddNodeIDNode(ID, Opcode, VTs, Ops);
5122 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5123 return SDValue(E, 0);
5125 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5127 CSEMap.InsertNode(N, IP);
5129 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5134 return SDValue(N, 0);
5137 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5138 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5139 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5142 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5143 ArrayRef<SDValue> Ops) {
5144 if (VTList.NumVTs == 1)
5145 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5149 // FIXME: figure out how to safely handle things like
5150 // int foo(int x) { return 1 << (x & 255); }
5151 // int bar() { return foo(256); }
5152 case ISD::SRA_PARTS:
5153 case ISD::SRL_PARTS:
5154 case ISD::SHL_PARTS:
5155 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5156 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5157 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5158 else if (N3.getOpcode() == ISD::AND)
5159 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5160 // If the and is only masking out bits that cannot effect the shift,
5161 // eliminate the and.
5162 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5163 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5164 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5170 // Memoize the node unless it returns a flag.
5172 unsigned NumOps = Ops.size();
5173 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5174 FoldingSetNodeID ID;
5175 AddNodeIDNode(ID, Opcode, VTList, Ops);
5177 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5178 return SDValue(E, 0);
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(),
5195 CSEMap.InsertNode(N, IP);
5198 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5199 DL.getDebugLoc(), VTList, Ops[0]);
5200 } else if (NumOps == 2) {
5201 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5202 DL.getDebugLoc(), VTList, Ops[0],
5204 } else if (NumOps == 3) {
5205 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5206 DL.getDebugLoc(), VTList, Ops[0],
5209 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5214 return SDValue(N, 0);
5217 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5218 return getNode(Opcode, DL, VTList, None);
5221 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5223 SDValue Ops[] = { N1 };
5224 return getNode(Opcode, DL, VTList, Ops);
5227 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5228 SDValue N1, SDValue N2) {
5229 SDValue Ops[] = { N1, N2 };
5230 return getNode(Opcode, DL, VTList, Ops);
5233 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5234 SDValue N1, SDValue N2, SDValue N3) {
5235 SDValue Ops[] = { N1, N2, N3 };
5236 return getNode(Opcode, DL, VTList, Ops);
5239 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5240 SDValue N1, SDValue N2, SDValue N3,
5242 SDValue Ops[] = { N1, N2, N3, N4 };
5243 return getNode(Opcode, DL, VTList, Ops);
5246 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5247 SDValue N1, SDValue N2, SDValue N3,
5248 SDValue N4, SDValue N5) {
5249 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5250 return getNode(Opcode, DL, VTList, Ops);
5253 SDVTList SelectionDAG::getVTList(EVT VT) {
5254 return makeVTList(SDNode::getValueTypeList(VT), 1);
5257 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5258 FoldingSetNodeID ID;
5260 ID.AddInteger(VT1.getRawBits());
5261 ID.AddInteger(VT2.getRawBits());
5264 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5266 EVT *Array = Allocator.Allocate<EVT>(2);
5269 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5270 VTListMap.InsertNode(Result, IP);
5272 return Result->getSDVTList();
5275 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5276 FoldingSetNodeID ID;
5278 ID.AddInteger(VT1.getRawBits());
5279 ID.AddInteger(VT2.getRawBits());
5280 ID.AddInteger(VT3.getRawBits());
5283 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5285 EVT *Array = Allocator.Allocate<EVT>(3);
5289 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5290 VTListMap.InsertNode(Result, IP);
5292 return Result->getSDVTList();
5295 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5296 FoldingSetNodeID ID;
5298 ID.AddInteger(VT1.getRawBits());
5299 ID.AddInteger(VT2.getRawBits());
5300 ID.AddInteger(VT3.getRawBits());
5301 ID.AddInteger(VT4.getRawBits());
5304 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5306 EVT *Array = Allocator.Allocate<EVT>(4);
5311 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5312 VTListMap.InsertNode(Result, IP);
5314 return Result->getSDVTList();
5317 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5318 unsigned NumVTs = VTs.size();
5319 FoldingSetNodeID ID;
5320 ID.AddInteger(NumVTs);
5321 for (unsigned index = 0; index < NumVTs; index++) {
5322 ID.AddInteger(VTs[index].getRawBits());
5326 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5328 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5329 std::copy(VTs.begin(), VTs.end(), Array);
5330 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5331 VTListMap.InsertNode(Result, IP);
5333 return Result->getSDVTList();
5337 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5338 /// specified operands. If the resultant node already exists in the DAG,
5339 /// this does not modify the specified node, instead it returns the node that
5340 /// already exists. If the resultant node does not exist in the DAG, the
5341 /// input node is returned. As a degenerate case, if you specify the same
5342 /// input operands as the node already has, the input node is returned.
5343 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5344 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5346 // Check to see if there is no change.
5347 if (Op == N->getOperand(0)) return N;
5349 // See if the modified node already exists.
5350 void *InsertPos = nullptr;
5351 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5354 // Nope it doesn't. Remove the node from its current place in the maps.
5356 if (!RemoveNodeFromCSEMaps(N))
5357 InsertPos = nullptr;
5359 // Now we update the operands.
5360 N->OperandList[0].set(Op);
5362 // If this gets put into a CSE map, add it.
5363 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5367 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5368 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5370 // Check to see if there is no change.
5371 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5372 return N; // No operands changed, just return the input node.
5374 // See if the modified node already exists.
5375 void *InsertPos = nullptr;
5376 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5379 // Nope it doesn't. Remove the node from its current place in the maps.
5381 if (!RemoveNodeFromCSEMaps(N))
5382 InsertPos = nullptr;
5384 // Now we update the operands.
5385 if (N->OperandList[0] != Op1)
5386 N->OperandList[0].set(Op1);
5387 if (N->OperandList[1] != Op2)
5388 N->OperandList[1].set(Op2);
5390 // If this gets put into a CSE map, add it.
5391 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5395 SDNode *SelectionDAG::
5396 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5397 SDValue Ops[] = { Op1, Op2, Op3 };
5398 return UpdateNodeOperands(N, Ops);
5401 SDNode *SelectionDAG::
5402 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5403 SDValue Op3, SDValue Op4) {
5404 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5405 return UpdateNodeOperands(N, Ops);
5408 SDNode *SelectionDAG::
5409 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5410 SDValue Op3, SDValue Op4, SDValue Op5) {
5411 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5412 return UpdateNodeOperands(N, Ops);
5415 SDNode *SelectionDAG::
5416 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5417 unsigned NumOps = Ops.size();
5418 assert(N->getNumOperands() == NumOps &&
5419 "Update with wrong number of operands");
5421 // Check to see if there is no change.
5422 bool AnyChange = false;
5423 for (unsigned i = 0; i != NumOps; ++i) {
5424 if (Ops[i] != N->getOperand(i)) {
5430 // No operands changed, just return the input node.
5431 if (!AnyChange) return N;
5433 // See if the modified node already exists.
5434 void *InsertPos = nullptr;
5435 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5438 // Nope it doesn't. Remove the node from its current place in the maps.
5440 if (!RemoveNodeFromCSEMaps(N))
5441 InsertPos = nullptr;
5443 // Now we update the operands.
5444 for (unsigned i = 0; i != NumOps; ++i)
5445 if (N->OperandList[i] != Ops[i])
5446 N->OperandList[i].set(Ops[i]);
5448 // If this gets put into a CSE map, add it.
5449 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5453 /// DropOperands - Release the operands and set this node to have
5455 void SDNode::DropOperands() {
5456 // Unlike the code in MorphNodeTo that does this, we don't need to
5457 // watch for dead nodes here.
5458 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5464 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5467 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5469 SDVTList VTs = getVTList(VT);
5470 return SelectNodeTo(N, MachineOpc, VTs, None);
5473 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5474 EVT VT, SDValue Op1) {
5475 SDVTList VTs = getVTList(VT);
5476 SDValue Ops[] = { Op1 };
5477 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5480 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5481 EVT VT, SDValue Op1,
5483 SDVTList VTs = getVTList(VT);
5484 SDValue Ops[] = { Op1, Op2 };
5485 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5488 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5489 EVT VT, SDValue Op1,
5490 SDValue Op2, SDValue Op3) {
5491 SDVTList VTs = getVTList(VT);
5492 SDValue Ops[] = { Op1, Op2, Op3 };
5493 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5496 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5497 EVT VT, ArrayRef<SDValue> Ops) {
5498 SDVTList VTs = getVTList(VT);
5499 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5502 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5503 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5504 SDVTList VTs = getVTList(VT1, VT2);
5505 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5508 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5510 SDVTList VTs = getVTList(VT1, VT2);
5511 return SelectNodeTo(N, MachineOpc, VTs, None);
5514 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5515 EVT VT1, EVT VT2, EVT VT3,
5516 ArrayRef<SDValue> Ops) {
5517 SDVTList VTs = getVTList(VT1, VT2, VT3);
5518 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5521 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5522 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5523 ArrayRef<SDValue> Ops) {
5524 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5525 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5528 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5531 SDVTList VTs = getVTList(VT1, VT2);
5532 SDValue Ops[] = { Op1 };
5533 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5536 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5538 SDValue Op1, SDValue Op2) {
5539 SDVTList VTs = getVTList(VT1, VT2);
5540 SDValue Ops[] = { Op1, Op2 };
5541 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5544 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5546 SDValue Op1, SDValue Op2,
5548 SDVTList VTs = getVTList(VT1, VT2);
5549 SDValue Ops[] = { Op1, Op2, Op3 };
5550 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5553 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5554 EVT VT1, EVT VT2, EVT VT3,
5555 SDValue Op1, SDValue Op2,
5557 SDVTList VTs = getVTList(VT1, VT2, VT3);
5558 SDValue Ops[] = { Op1, Op2, Op3 };
5559 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5562 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5563 SDVTList VTs,ArrayRef<SDValue> Ops) {
5564 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5565 // Reset the NodeID to -1.
5570 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5571 /// the line number information on the merged node since it is not possible to
5572 /// preserve the information that operation is associated with multiple lines.
5573 /// This will make the debugger working better at -O0, were there is a higher
5574 /// probability having other instructions associated with that line.
5576 /// For IROrder, we keep the smaller of the two
5577 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5578 DebugLoc NLoc = N->getDebugLoc();
5579 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5580 (OLoc.getDebugLoc() != NLoc)) {
5581 N->setDebugLoc(DebugLoc());
5583 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5584 N->setIROrder(Order);
5588 /// MorphNodeTo - This *mutates* the specified node to have the specified
5589 /// return type, opcode, and operands.
5591 /// Note that MorphNodeTo returns the resultant node. If there is already a
5592 /// node of the specified opcode and operands, it returns that node instead of
5593 /// the current one. Note that the SDLoc need not be the same.
5595 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5596 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5597 /// node, and because it doesn't require CSE recalculation for any of
5598 /// the node's users.
5600 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5601 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5602 /// the legalizer which maintain worklists that would need to be updated when
5603 /// deleting things.
5604 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5605 SDVTList VTs, ArrayRef<SDValue> Ops) {
5606 unsigned NumOps = Ops.size();
5607 // If an identical node already exists, use it.
5609 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5610 FoldingSetNodeID ID;
5611 AddNodeIDNode(ID, Opc, VTs, Ops);
5612 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5613 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5616 if (!RemoveNodeFromCSEMaps(N))
5619 // Start the morphing.
5621 N->ValueList = VTs.VTs;
5622 N->NumValues = VTs.NumVTs;
5624 // Clear the operands list, updating used nodes to remove this from their
5625 // use list. Keep track of any operands that become dead as a result.
5626 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5627 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5629 SDNode *Used = Use.getNode();
5631 if (Used->use_empty())
5632 DeadNodeSet.insert(Used);
5635 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5636 // Initialize the memory references information.
5637 MN->setMemRefs(nullptr, nullptr);
5638 // If NumOps is larger than the # of operands we can have in a
5639 // MachineSDNode, reallocate the operand list.
5640 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5641 if (MN->OperandsNeedDelete)
5642 delete[] MN->OperandList;
5643 if (NumOps > array_lengthof(MN->LocalOperands))
5644 // We're creating a final node that will live unmorphed for the
5645 // remainder of the current SelectionDAG iteration, so we can allocate
5646 // the operands directly out of a pool with no recycling metadata.
5647 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5648 Ops.data(), NumOps);
5650 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5651 MN->OperandsNeedDelete = false;
5653 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5655 // If NumOps is larger than the # of operands we currently have, reallocate
5656 // the operand list.
5657 if (NumOps > N->NumOperands) {
5658 if (N->OperandsNeedDelete)
5659 delete[] N->OperandList;
5660 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5661 N->OperandsNeedDelete = true;
5663 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5666 // Delete any nodes that are still dead after adding the uses for the
5668 if (!DeadNodeSet.empty()) {
5669 SmallVector<SDNode *, 16> DeadNodes;
5670 for (SDNode *N : DeadNodeSet)
5672 DeadNodes.push_back(N);
5673 RemoveDeadNodes(DeadNodes);
5677 CSEMap.InsertNode(N, IP); // Memoize the new node.
5682 /// getMachineNode - These are used for target selectors to create a new node
5683 /// with specified return type(s), MachineInstr opcode, and operands.
5685 /// Note that getMachineNode returns the resultant node. If there is already a
5686 /// node of the specified opcode and operands, it returns that node instead of
5687 /// the current one.
5689 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5690 SDVTList VTs = getVTList(VT);
5691 return getMachineNode(Opcode, dl, VTs, None);
5695 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5696 SDVTList VTs = getVTList(VT);
5697 SDValue Ops[] = { Op1 };
5698 return getMachineNode(Opcode, dl, VTs, Ops);
5702 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5703 SDValue Op1, SDValue Op2) {
5704 SDVTList VTs = getVTList(VT);
5705 SDValue Ops[] = { Op1, Op2 };
5706 return getMachineNode(Opcode, dl, VTs, Ops);
5710 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5711 SDValue Op1, SDValue Op2, SDValue Op3) {
5712 SDVTList VTs = getVTList(VT);
5713 SDValue Ops[] = { Op1, Op2, Op3 };
5714 return getMachineNode(Opcode, dl, VTs, Ops);
5718 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5719 ArrayRef<SDValue> Ops) {
5720 SDVTList VTs = getVTList(VT);
5721 return getMachineNode(Opcode, dl, VTs, Ops);
5725 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5726 SDVTList VTs = getVTList(VT1, VT2);
5727 return getMachineNode(Opcode, dl, VTs, None);
5731 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5732 EVT VT1, EVT VT2, SDValue Op1) {
5733 SDVTList VTs = getVTList(VT1, VT2);
5734 SDValue Ops[] = { Op1 };
5735 return getMachineNode(Opcode, dl, VTs, Ops);
5739 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5740 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5741 SDVTList VTs = getVTList(VT1, VT2);
5742 SDValue Ops[] = { Op1, Op2 };
5743 return getMachineNode(Opcode, dl, VTs, Ops);
5747 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5748 EVT VT1, EVT VT2, SDValue Op1,
5749 SDValue Op2, SDValue Op3) {
5750 SDVTList VTs = getVTList(VT1, VT2);
5751 SDValue Ops[] = { Op1, Op2, Op3 };
5752 return getMachineNode(Opcode, dl, VTs, Ops);
5756 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5758 ArrayRef<SDValue> Ops) {
5759 SDVTList VTs = getVTList(VT1, VT2);
5760 return getMachineNode(Opcode, dl, VTs, Ops);
5764 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5765 EVT VT1, EVT VT2, EVT VT3,
5766 SDValue Op1, SDValue Op2) {
5767 SDVTList VTs = getVTList(VT1, VT2, VT3);
5768 SDValue Ops[] = { Op1, Op2 };
5769 return getMachineNode(Opcode, dl, VTs, Ops);
5773 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5774 EVT VT1, EVT VT2, EVT VT3,
5775 SDValue Op1, SDValue Op2, SDValue Op3) {
5776 SDVTList VTs = getVTList(VT1, VT2, VT3);
5777 SDValue Ops[] = { Op1, Op2, Op3 };
5778 return getMachineNode(Opcode, dl, VTs, Ops);
5782 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5783 EVT VT1, EVT VT2, EVT VT3,
5784 ArrayRef<SDValue> Ops) {
5785 SDVTList VTs = getVTList(VT1, VT2, VT3);
5786 return getMachineNode(Opcode, dl, VTs, Ops);
5790 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5791 EVT VT2, EVT VT3, EVT VT4,
5792 ArrayRef<SDValue> Ops) {
5793 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5794 return getMachineNode(Opcode, dl, VTs, Ops);
5798 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5799 ArrayRef<EVT> ResultTys,
5800 ArrayRef<SDValue> Ops) {
5801 SDVTList VTs = getVTList(ResultTys);
5802 return getMachineNode(Opcode, dl, VTs, Ops);
5806 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5807 ArrayRef<SDValue> OpsArray) {
5808 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5811 const SDValue *Ops = OpsArray.data();
5812 unsigned NumOps = OpsArray.size();
5815 FoldingSetNodeID ID;
5816 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5818 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5819 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5823 // Allocate a new MachineSDNode.
5824 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5825 DL.getDebugLoc(), VTs);
5827 // Initialize the operands list.
5828 if (NumOps > array_lengthof(N->LocalOperands))
5829 // We're creating a final node that will live unmorphed for the
5830 // remainder of the current SelectionDAG iteration, so we can allocate
5831 // the operands directly out of a pool with no recycling metadata.
5832 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5835 N->InitOperands(N->LocalOperands, Ops, NumOps);
5836 N->OperandsNeedDelete = false;
5839 CSEMap.InsertNode(N, IP);
5845 /// getTargetExtractSubreg - A convenience function for creating
5846 /// TargetOpcode::EXTRACT_SUBREG nodes.
5848 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5850 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5851 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5852 VT, Operand, SRIdxVal);
5853 return SDValue(Subreg, 0);
5856 /// getTargetInsertSubreg - A convenience function for creating
5857 /// TargetOpcode::INSERT_SUBREG nodes.
5859 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5860 SDValue Operand, SDValue Subreg) {
5861 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5862 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5863 VT, Operand, Subreg, SRIdxVal);
5864 return SDValue(Result, 0);
5867 /// getNodeIfExists - Get the specified node if it's already available, or
5868 /// else return NULL.
5869 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5870 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5872 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5873 FoldingSetNodeID ID;
5874 AddNodeIDNode(ID, Opcode, VTList, Ops);
5875 if (isBinOpWithFlags(Opcode))
5876 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5878 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5884 /// getDbgValue - Creates a SDDbgValue node.
5887 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5888 unsigned R, bool IsIndirect, uint64_t Off,
5889 DebugLoc DL, unsigned O) {
5890 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5894 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5895 const Value *C, uint64_t Off,
5896 DebugLoc DL, unsigned O) {
5897 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5901 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5902 unsigned FI, uint64_t Off,
5903 DebugLoc DL, unsigned O) {
5904 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5909 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5910 /// pointed to by a use iterator is deleted, increment the use iterator
5911 /// so that it doesn't dangle.
5913 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5914 SDNode::use_iterator &UI;
5915 SDNode::use_iterator &UE;
5917 void NodeDeleted(SDNode *N, SDNode *E) override {
5918 // Increment the iterator as needed.
5919 while (UI != UE && N == *UI)
5924 RAUWUpdateListener(SelectionDAG &d,
5925 SDNode::use_iterator &ui,
5926 SDNode::use_iterator &ue)
5927 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5932 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5933 /// This can cause recursive merging of nodes in the DAG.
5935 /// This version assumes From has a single result value.
5937 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5938 SDNode *From = FromN.getNode();
5939 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5940 "Cannot replace with this method!");
5941 assert(From != To.getNode() && "Cannot replace uses of with self");
5943 // Iterate over all the existing uses of From. New uses will be added
5944 // to the beginning of the use list, which we avoid visiting.
5945 // This specifically avoids visiting uses of From that arise while the
5946 // replacement is happening, because any such uses would be the result
5947 // of CSE: If an existing node looks like From after one of its operands
5948 // is replaced by To, we don't want to replace of all its users with To
5949 // too. See PR3018 for more info.
5950 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5951 RAUWUpdateListener Listener(*this, UI, UE);
5955 // This node is about to morph, remove its old self from the CSE maps.
5956 RemoveNodeFromCSEMaps(User);
5958 // A user can appear in a use list multiple times, and when this
5959 // happens the uses are usually next to each other in the list.
5960 // To help reduce the number of CSE recomputations, process all
5961 // the uses of this user that we can find this way.
5963 SDUse &Use = UI.getUse();
5966 } while (UI != UE && *UI == User);
5968 // Now that we have modified User, add it back to the CSE maps. If it
5969 // already exists there, recursively merge the results together.
5970 AddModifiedNodeToCSEMaps(User);
5973 // If we just RAUW'd the root, take note.
5974 if (FromN == getRoot())
5978 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5979 /// This can cause recursive merging of nodes in the DAG.
5981 /// This version assumes that for each value of From, there is a
5982 /// corresponding value in To in the same position with the same type.
5984 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5986 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5987 assert((!From->hasAnyUseOfValue(i) ||
5988 From->getValueType(i) == To->getValueType(i)) &&
5989 "Cannot use this version of ReplaceAllUsesWith!");
5992 // Handle the trivial case.
5996 // Iterate over just the existing users of From. See the comments in
5997 // the ReplaceAllUsesWith above.
5998 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5999 RAUWUpdateListener Listener(*this, UI, UE);
6003 // This node is about to morph, remove its old self from the CSE maps.
6004 RemoveNodeFromCSEMaps(User);
6006 // A user can appear in a use list multiple times, and when this
6007 // happens the uses are usually next to each other in the list.
6008 // To help reduce the number of CSE recomputations, process all
6009 // the uses of this user that we can find this way.
6011 SDUse &Use = UI.getUse();
6014 } while (UI != UE && *UI == User);
6016 // Now that we have modified User, add it back to the CSE maps. If it
6017 // already exists there, recursively merge the results together.
6018 AddModifiedNodeToCSEMaps(User);
6021 // If we just RAUW'd the root, take note.
6022 if (From == getRoot().getNode())
6023 setRoot(SDValue(To, getRoot().getResNo()));
6026 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6027 /// This can cause recursive merging of nodes in the DAG.
6029 /// This version can replace From with any result values. To must match the
6030 /// number and types of values returned by From.
6031 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6032 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6033 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6035 // Iterate over just the existing users of From. See the comments in
6036 // the ReplaceAllUsesWith above.
6037 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6038 RAUWUpdateListener Listener(*this, UI, UE);
6042 // This node is about to morph, remove its old self from the CSE maps.
6043 RemoveNodeFromCSEMaps(User);
6045 // A user can appear in a use list multiple times, and when this
6046 // happens the uses are usually next to each other in the list.
6047 // To help reduce the number of CSE recomputations, process all
6048 // the uses of this user that we can find this way.
6050 SDUse &Use = UI.getUse();
6051 const SDValue &ToOp = To[Use.getResNo()];
6054 } while (UI != UE && *UI == User);
6056 // Now that we have modified User, add it back to the CSE maps. If it
6057 // already exists there, recursively merge the results together.
6058 AddModifiedNodeToCSEMaps(User);
6061 // If we just RAUW'd the root, take note.
6062 if (From == getRoot().getNode())
6063 setRoot(SDValue(To[getRoot().getResNo()]));
6066 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6067 /// uses of other values produced by From.getNode() alone. The Deleted
6068 /// vector is handled the same way as for ReplaceAllUsesWith.
6069 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6070 // Handle the really simple, really trivial case efficiently.
6071 if (From == To) return;
6073 // Handle the simple, trivial, case efficiently.
6074 if (From.getNode()->getNumValues() == 1) {
6075 ReplaceAllUsesWith(From, To);
6079 // Iterate over just the existing users of From. See the comments in
6080 // the ReplaceAllUsesWith above.
6081 SDNode::use_iterator UI = From.getNode()->use_begin(),
6082 UE = From.getNode()->use_end();
6083 RAUWUpdateListener Listener(*this, UI, UE);
6086 bool UserRemovedFromCSEMaps = false;
6088 // A user can appear in a use list multiple times, and when this
6089 // happens the uses are usually next to each other in the list.
6090 // To help reduce the number of CSE recomputations, process all
6091 // the uses of this user that we can find this way.
6093 SDUse &Use = UI.getUse();
6095 // Skip uses of different values from the same node.
6096 if (Use.getResNo() != From.getResNo()) {
6101 // If this node hasn't been modified yet, it's still in the CSE maps,
6102 // so remove its old self from the CSE maps.
6103 if (!UserRemovedFromCSEMaps) {
6104 RemoveNodeFromCSEMaps(User);
6105 UserRemovedFromCSEMaps = true;
6110 } while (UI != UE && *UI == User);
6112 // We are iterating over all uses of the From node, so if a use
6113 // doesn't use the specific value, no changes are made.
6114 if (!UserRemovedFromCSEMaps)
6117 // Now that we have modified User, add it back to the CSE maps. If it
6118 // already exists there, recursively merge the results together.
6119 AddModifiedNodeToCSEMaps(User);
6122 // If we just RAUW'd the root, take note.
6123 if (From == getRoot())
6128 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6129 /// to record information about a use.
6136 /// operator< - Sort Memos by User.
6137 bool operator<(const UseMemo &L, const UseMemo &R) {
6138 return (intptr_t)L.User < (intptr_t)R.User;
6142 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6143 /// uses of other values produced by From.getNode() alone. The same value
6144 /// may appear in both the From and To list. The Deleted vector is
6145 /// handled the same way as for ReplaceAllUsesWith.
6146 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6149 // Handle the simple, trivial case efficiently.
6151 return ReplaceAllUsesOfValueWith(*From, *To);
6153 // Read up all the uses and make records of them. This helps
6154 // processing new uses that are introduced during the
6155 // replacement process.
6156 SmallVector<UseMemo, 4> Uses;
6157 for (unsigned i = 0; i != Num; ++i) {
6158 unsigned FromResNo = From[i].getResNo();
6159 SDNode *FromNode = From[i].getNode();
6160 for (SDNode::use_iterator UI = FromNode->use_begin(),
6161 E = FromNode->use_end(); UI != E; ++UI) {
6162 SDUse &Use = UI.getUse();
6163 if (Use.getResNo() == FromResNo) {
6164 UseMemo Memo = { *UI, i, &Use };
6165 Uses.push_back(Memo);
6170 // Sort the uses, so that all the uses from a given User are together.
6171 std::sort(Uses.begin(), Uses.end());
6173 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6174 UseIndex != UseIndexEnd; ) {
6175 // We know that this user uses some value of From. If it is the right
6176 // value, update it.
6177 SDNode *User = Uses[UseIndex].User;
6179 // This node is about to morph, remove its old self from the CSE maps.
6180 RemoveNodeFromCSEMaps(User);
6182 // The Uses array is sorted, so all the uses for a given User
6183 // are next to each other in the list.
6184 // To help reduce the number of CSE recomputations, process all
6185 // the uses of this user that we can find this way.
6187 unsigned i = Uses[UseIndex].Index;
6188 SDUse &Use = *Uses[UseIndex].Use;
6192 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6194 // Now that we have modified User, add it back to the CSE maps. If it
6195 // already exists there, recursively merge the results together.
6196 AddModifiedNodeToCSEMaps(User);
6200 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6201 /// based on their topological order. It returns the maximum id and a vector
6202 /// of the SDNodes* in assigned order by reference.
6203 unsigned SelectionDAG::AssignTopologicalOrder() {
6205 unsigned DAGSize = 0;
6207 // SortedPos tracks the progress of the algorithm. Nodes before it are
6208 // sorted, nodes after it are unsorted. When the algorithm completes
6209 // it is at the end of the list.
6210 allnodes_iterator SortedPos = allnodes_begin();
6212 // Visit all the nodes. Move nodes with no operands to the front of
6213 // the list immediately. Annotate nodes that do have operands with their
6214 // operand count. Before we do this, the Node Id fields of the nodes
6215 // may contain arbitrary values. After, the Node Id fields for nodes
6216 // before SortedPos will contain the topological sort index, and the
6217 // Node Id fields for nodes At SortedPos and after will contain the
6218 // count of outstanding operands.
6219 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6221 checkForCycles(N, this);
6222 unsigned Degree = N->getNumOperands();
6224 // A node with no uses, add it to the result array immediately.
6225 N->setNodeId(DAGSize++);
6226 allnodes_iterator Q = N;
6228 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6229 assert(SortedPos != AllNodes.end() && "Overran node list");
6232 // Temporarily use the Node Id as scratch space for the degree count.
6233 N->setNodeId(Degree);
6237 // Visit all the nodes. As we iterate, move nodes into sorted order,
6238 // such that by the time the end is reached all nodes will be sorted.
6239 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6241 checkForCycles(N, this);
6242 // N is in sorted position, so all its uses have one less operand
6243 // that needs to be sorted.
6244 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6247 unsigned Degree = P->getNodeId();
6248 assert(Degree != 0 && "Invalid node degree");
6251 // All of P's operands are sorted, so P may sorted now.
6252 P->setNodeId(DAGSize++);
6254 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6255 assert(SortedPos != AllNodes.end() && "Overran node list");
6258 // Update P's outstanding operand count.
6259 P->setNodeId(Degree);
6262 if (I == SortedPos) {
6265 dbgs() << "Overran sorted position:\n";
6266 S->dumprFull(this); dbgs() << "\n";
6267 dbgs() << "Checking if this is due to cycles\n";
6268 checkForCycles(this, true);
6270 llvm_unreachable(nullptr);
6274 assert(SortedPos == AllNodes.end() &&
6275 "Topological sort incomplete!");
6276 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6277 "First node in topological sort is not the entry token!");
6278 assert(AllNodes.front().getNodeId() == 0 &&
6279 "First node in topological sort has non-zero id!");
6280 assert(AllNodes.front().getNumOperands() == 0 &&
6281 "First node in topological sort has operands!");
6282 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6283 "Last node in topologic sort has unexpected id!");
6284 assert(AllNodes.back().use_empty() &&
6285 "Last node in topologic sort has users!");
6286 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6290 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6291 /// value is produced by SD.
6292 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6294 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6295 SD->setHasDebugValue(true);
6297 DbgInfo->add(DB, SD, isParameter);
6300 /// TransferDbgValues - Transfer SDDbgValues.
6301 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6302 if (From == To || !From.getNode()->getHasDebugValue())
6304 SDNode *FromNode = From.getNode();
6305 SDNode *ToNode = To.getNode();
6306 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6307 SmallVector<SDDbgValue *, 2> ClonedDVs;
6308 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6310 SDDbgValue *Dbg = *I;
6311 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6313 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6314 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6315 Dbg->getDebugLoc(), Dbg->getOrder());
6316 ClonedDVs.push_back(Clone);
6319 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6320 E = ClonedDVs.end(); I != E; ++I)
6321 AddDbgValue(*I, ToNode, false);
6324 //===----------------------------------------------------------------------===//
6326 //===----------------------------------------------------------------------===//
6328 HandleSDNode::~HandleSDNode() {
6332 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6333 DebugLoc DL, const GlobalValue *GA,
6334 EVT VT, int64_t o, unsigned char TF)
6335 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6339 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6340 SDValue X, unsigned SrcAS,
6342 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6343 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6345 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6346 EVT memvt, MachineMemOperand *mmo)
6347 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6348 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6349 MMO->isNonTemporal(), MMO->isInvariant());
6350 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6351 assert(isNonTemporal() == MMO->isNonTemporal() &&
6352 "Non-temporal encoding error!");
6353 // We check here that the size of the memory operand fits within the size of
6354 // the MMO. This is because the MMO might indicate only a possible address
6355 // range instead of specifying the affected memory addresses precisely.
6356 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6359 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6360 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6361 : SDNode(Opc, Order, dl, VTs, Ops),
6362 MemoryVT(memvt), MMO(mmo) {
6363 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6364 MMO->isNonTemporal(), MMO->isInvariant());
6365 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6366 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6369 /// Profile - Gather unique data for the node.
6371 void SDNode::Profile(FoldingSetNodeID &ID) const {
6372 AddNodeIDNode(ID, this);
6377 std::vector<EVT> VTs;
6380 VTs.reserve(MVT::LAST_VALUETYPE);
6381 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6382 VTs.push_back(MVT((MVT::SimpleValueType)i));
6387 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6388 static ManagedStatic<EVTArray> SimpleVTArray;
6389 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6391 /// getValueTypeList - Return a pointer to the specified value type.
6393 const EVT *SDNode::getValueTypeList(EVT VT) {
6394 if (VT.isExtended()) {
6395 sys::SmartScopedLock<true> Lock(*VTMutex);
6396 return &(*EVTs->insert(VT).first);
6398 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6399 "Value type out of range!");
6400 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6404 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6405 /// indicated value. This method ignores uses of other values defined by this
6407 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6408 assert(Value < getNumValues() && "Bad value!");
6410 // TODO: Only iterate over uses of a given value of the node
6411 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6412 if (UI.getUse().getResNo() == Value) {
6419 // Found exactly the right number of uses?
6424 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6425 /// value. This method ignores uses of other values defined by this operation.
6426 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6427 assert(Value < getNumValues() && "Bad value!");
6429 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6430 if (UI.getUse().getResNo() == Value)
6437 /// isOnlyUserOf - Return true if this node is the only use of N.
6439 bool SDNode::isOnlyUserOf(SDNode *N) const {
6441 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6452 /// isOperand - Return true if this node is an operand of N.
6454 bool SDValue::isOperandOf(SDNode *N) const {
6455 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6456 if (*this == N->getOperand(i))
6461 bool SDNode::isOperandOf(SDNode *N) const {
6462 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6463 if (this == N->OperandList[i].getNode())
6468 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6469 /// be a chain) reaches the specified operand without crossing any
6470 /// side-effecting instructions on any chain path. In practice, this looks
6471 /// through token factors and non-volatile loads. In order to remain efficient,
6472 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6473 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6474 unsigned Depth) const {
6475 if (*this == Dest) return true;
6477 // Don't search too deeply, we just want to be able to see through
6478 // TokenFactor's etc.
6479 if (Depth == 0) return false;
6481 // If this is a token factor, all inputs to the TF happen in parallel. If any
6482 // of the operands of the TF does not reach dest, then we cannot do the xform.
6483 if (getOpcode() == ISD::TokenFactor) {
6484 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6485 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6490 // Loads don't have side effects, look through them.
6491 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6492 if (!Ld->isVolatile())
6493 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6498 /// hasPredecessor - Return true if N is a predecessor of this node.
6499 /// N is either an operand of this node, or can be reached by recursively
6500 /// traversing up the operands.
6501 /// NOTE: This is an expensive method. Use it carefully.
6502 bool SDNode::hasPredecessor(const SDNode *N) const {
6503 SmallPtrSet<const SDNode *, 32> Visited;
6504 SmallVector<const SDNode *, 16> Worklist;
6505 return hasPredecessorHelper(N, Visited, Worklist);
6509 SDNode::hasPredecessorHelper(const SDNode *N,
6510 SmallPtrSetImpl<const SDNode *> &Visited,
6511 SmallVectorImpl<const SDNode *> &Worklist) const {
6512 if (Visited.empty()) {
6513 Worklist.push_back(this);
6515 // Take a look in the visited set. If we've already encountered this node
6516 // we needn't search further.
6517 if (Visited.count(N))
6521 // Haven't visited N yet. Continue the search.
6522 while (!Worklist.empty()) {
6523 const SDNode *M = Worklist.pop_back_val();
6524 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6525 SDNode *Op = M->getOperand(i).getNode();
6526 if (Visited.insert(Op).second)
6527 Worklist.push_back(Op);
6536 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6537 assert(Num < NumOperands && "Invalid child # of SDNode!");
6538 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6541 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6542 assert(N->getNumValues() == 1 &&
6543 "Can't unroll a vector with multiple results!");
6545 EVT VT = N->getValueType(0);
6546 unsigned NE = VT.getVectorNumElements();
6547 EVT EltVT = VT.getVectorElementType();
6550 SmallVector<SDValue, 8> Scalars;
6551 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6553 // If ResNE is 0, fully unroll the vector op.
6556 else if (NE > ResNE)
6560 for (i= 0; i != NE; ++i) {
6561 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6562 SDValue Operand = N->getOperand(j);
6563 EVT OperandVT = Operand.getValueType();
6564 if (OperandVT.isVector()) {
6565 // A vector operand; extract a single element.
6566 EVT OperandEltVT = OperandVT.getVectorElementType();
6567 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6570 getConstant(i, TLI->getVectorIdxTy()));
6572 // A scalar operand; just use it as is.
6573 Operands[j] = Operand;
6577 switch (N->getOpcode()) {
6579 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6582 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6589 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6590 getShiftAmountOperand(Operands[0].getValueType(),
6593 case ISD::SIGN_EXTEND_INREG:
6594 case ISD::FP_ROUND_INREG: {
6595 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6596 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6598 getValueType(ExtVT)));
6603 for (; i < ResNE; ++i)
6604 Scalars.push_back(getUNDEF(EltVT));
6606 return getNode(ISD::BUILD_VECTOR, dl,
6607 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6611 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6612 /// location that is 'Dist' units away from the location that the 'Base' load
6613 /// is loading from.
6614 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6615 unsigned Bytes, int Dist) const {
6616 if (LD->getChain() != Base->getChain())
6618 EVT VT = LD->getValueType(0);
6619 if (VT.getSizeInBits() / 8 != Bytes)
6622 SDValue Loc = LD->getOperand(1);
6623 SDValue BaseLoc = Base->getOperand(1);
6624 if (Loc.getOpcode() == ISD::FrameIndex) {
6625 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6627 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6628 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6629 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6630 int FS = MFI->getObjectSize(FI);
6631 int BFS = MFI->getObjectSize(BFI);
6632 if (FS != BFS || FS != (int)Bytes) return false;
6633 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6637 if (isBaseWithConstantOffset(Loc)) {
6638 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6639 if (Loc.getOperand(0) == BaseLoc) {
6640 // If the base location is a simple address with no offset itself, then
6641 // the second load's first add operand should be the base address.
6642 if (LocOffset == Dist * (int)Bytes)
6644 } else if (isBaseWithConstantOffset(BaseLoc)) {
6645 // The base location itself has an offset, so subtract that value from the
6646 // second load's offset before comparing to distance * size.
6648 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6649 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6650 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6655 const GlobalValue *GV1 = nullptr;
6656 const GlobalValue *GV2 = nullptr;
6657 int64_t Offset1 = 0;
6658 int64_t Offset2 = 0;
6659 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6660 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6661 if (isGA1 && isGA2 && GV1 == GV2)
6662 return Offset1 == (Offset2 + Dist*Bytes);
6667 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6668 /// it cannot be inferred.
6669 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6670 // If this is a GlobalAddress + cst, return the alignment.
6671 const GlobalValue *GV;
6672 int64_t GVOffset = 0;
6673 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6674 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6675 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6676 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6677 TLI->getDataLayout());
6678 unsigned AlignBits = KnownZero.countTrailingOnes();
6679 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6681 return MinAlign(Align, GVOffset);
6684 // If this is a direct reference to a stack slot, use information about the
6685 // stack slot's alignment.
6686 int FrameIdx = 1 << 31;
6687 int64_t FrameOffset = 0;
6688 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6689 FrameIdx = FI->getIndex();
6690 } else if (isBaseWithConstantOffset(Ptr) &&
6691 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6693 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6694 FrameOffset = Ptr.getConstantOperandVal(1);
6697 if (FrameIdx != (1 << 31)) {
6698 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6699 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6707 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6708 /// which is split (or expanded) into two not necessarily identical pieces.
6709 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6710 // Currently all types are split in half.
6712 if (!VT.isVector()) {
6713 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6715 unsigned NumElements = VT.getVectorNumElements();
6716 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6717 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6720 return std::make_pair(LoVT, HiVT);
6723 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6725 std::pair<SDValue, SDValue>
6726 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6728 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6729 N.getValueType().getVectorNumElements() &&
6730 "More vector elements requested than available!");
6732 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6733 getConstant(0, TLI->getVectorIdxTy()));
6734 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6735 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6736 return std::make_pair(Lo, Hi);
6739 void SelectionDAG::ExtractVectorElements(SDValue Op,
6740 SmallVectorImpl<SDValue> &Args,
6741 unsigned Start, unsigned Count) {
6742 EVT VT = Op.getValueType();
6744 Count = VT.getVectorNumElements();
6746 EVT EltVT = VT.getVectorElementType();
6747 EVT IdxTy = TLI->getVectorIdxTy();
6749 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6750 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6751 Op, getConstant(i, IdxTy)));
6755 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6756 unsigned GlobalAddressSDNode::getAddressSpace() const {
6757 return getGlobal()->getType()->getAddressSpace();
6761 Type *ConstantPoolSDNode::getType() const {
6762 if (isMachineConstantPoolEntry())
6763 return Val.MachineCPVal->getType();
6764 return Val.ConstVal->getType();
6767 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6769 unsigned &SplatBitSize,
6771 unsigned MinSplatBits,
6772 bool isBigEndian) const {
6773 EVT VT = getValueType(0);
6774 assert(VT.isVector() && "Expected a vector type");
6775 unsigned sz = VT.getSizeInBits();
6776 if (MinSplatBits > sz)
6779 SplatValue = APInt(sz, 0);
6780 SplatUndef = APInt(sz, 0);
6782 // Get the bits. Bits with undefined values (when the corresponding element
6783 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6784 // in SplatValue. If any of the values are not constant, give up and return
6786 unsigned int nOps = getNumOperands();
6787 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6788 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6790 for (unsigned j = 0; j < nOps; ++j) {
6791 unsigned i = isBigEndian ? nOps-1-j : j;
6792 SDValue OpVal = getOperand(i);
6793 unsigned BitPos = j * EltBitSize;
6795 if (OpVal.getOpcode() == ISD::UNDEF)
6796 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6797 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6798 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6799 zextOrTrunc(sz) << BitPos;
6800 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6801 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6806 // The build_vector is all constants or undefs. Find the smallest element
6807 // size that splats the vector.
6809 HasAnyUndefs = (SplatUndef != 0);
6812 unsigned HalfSize = sz / 2;
6813 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6814 APInt LowValue = SplatValue.trunc(HalfSize);
6815 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6816 APInt LowUndef = SplatUndef.trunc(HalfSize);
6818 // If the two halves do not match (ignoring undef bits), stop here.
6819 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6820 MinSplatBits > HalfSize)
6823 SplatValue = HighValue | LowValue;
6824 SplatUndef = HighUndef & LowUndef;
6833 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6834 if (UndefElements) {
6835 UndefElements->clear();
6836 UndefElements->resize(getNumOperands());
6839 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6840 SDValue Op = getOperand(i);
6841 if (Op.getOpcode() == ISD::UNDEF) {
6843 (*UndefElements)[i] = true;
6844 } else if (!Splatted) {
6846 } else if (Splatted != Op) {
6852 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6853 "Can only have a splat without a constant for all undefs.");
6854 return getOperand(0);
6861 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6862 return dyn_cast_or_null<ConstantSDNode>(
6863 getSplatValue(UndefElements).getNode());
6867 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6868 return dyn_cast_or_null<ConstantFPSDNode>(
6869 getSplatValue(UndefElements).getNode());
6872 bool BuildVectorSDNode::isConstant() const {
6873 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6874 unsigned Opc = getOperand(i).getOpcode();
6875 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6881 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6882 // Find the first non-undef value in the shuffle mask.
6884 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6887 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6889 // Make sure all remaining elements are either undef or the same as the first
6891 for (int Idx = Mask[i]; i != e; ++i)
6892 if (Mask[i] >= 0 && Mask[i] != Idx)
6898 static void checkForCyclesHelper(const SDNode *N,
6899 SmallPtrSetImpl<const SDNode*> &Visited,
6900 SmallPtrSetImpl<const SDNode*> &Checked,
6901 const llvm::SelectionDAG *DAG) {
6902 // If this node has already been checked, don't check it again.
6903 if (Checked.count(N))
6906 // If a node has already been visited on this depth-first walk, reject it as
6908 if (!Visited.insert(N).second) {
6909 errs() << "Detected cycle in SelectionDAG\n";
6910 dbgs() << "Offending node:\n";
6911 N->dumprFull(DAG); dbgs() << "\n";
6915 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6916 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6923 void llvm::checkForCycles(const llvm::SDNode *N,
6924 const llvm::SelectionDAG *DAG,
6932 assert(N && "Checking nonexistent SDNode");
6933 SmallPtrSet<const SDNode*, 32> visited;
6934 SmallPtrSet<const SDNode*, 32> checked;
6935 checkForCyclesHelper(N, visited, checked, DAG);
6940 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6941 checkForCycles(DAG->getRoot().getNode(), DAG, force);