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 constant splat, build the vector
1586 if (AllSame && SameNumElts) {
1587 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1588 if (isa<ConstantSDNode>(Splatted) || isa<ConstantFPSDNode>(Splatted)) {
1589 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1592 getNode(ISD::BUILD_VECTOR, dl, BV->getValueType(0), Ops);
1594 // We may have jumped through bitcasts, so the type of the
1595 // BUILD_VECTOR may not match the type of the shuffle.
1596 if (BV->getValueType(0) != VT)
1597 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1604 FoldingSetNodeID ID;
1605 SDValue Ops[2] = { N1, N2 };
1606 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1607 for (unsigned i = 0; i != NElts; ++i)
1608 ID.AddInteger(MaskVec[i]);
1611 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1612 return SDValue(E, 0);
1614 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1615 // SDNode doesn't have access to it. This memory will be "leaked" when
1616 // the node is deallocated, but recovered when the NodeAllocator is released.
1617 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1618 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1620 ShuffleVectorSDNode *N =
1621 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1622 dl.getDebugLoc(), N1, N2,
1624 CSEMap.InsertNode(N, IP);
1626 return SDValue(N, 0);
1629 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1630 MVT VT = SV.getSimpleValueType(0);
1631 unsigned NumElems = VT.getVectorNumElements();
1632 SmallVector<int, 8> MaskVec;
1634 for (unsigned i = 0; i != NumElems; ++i) {
1635 int Idx = SV.getMaskElt(i);
1637 if (Idx < (int)NumElems)
1642 MaskVec.push_back(Idx);
1645 SDValue Op0 = SV.getOperand(0);
1646 SDValue Op1 = SV.getOperand(1);
1647 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1650 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1651 SDValue Val, SDValue DTy,
1652 SDValue STy, SDValue Rnd, SDValue Sat,
1653 ISD::CvtCode Code) {
1654 // If the src and dest types are the same and the conversion is between
1655 // integer types of the same sign or two floats, no conversion is necessary.
1657 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1660 FoldingSetNodeID ID;
1661 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1662 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1664 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1665 return SDValue(E, 0);
1667 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1670 CSEMap.InsertNode(N, IP);
1672 return SDValue(N, 0);
1675 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1676 FoldingSetNodeID ID;
1677 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1678 ID.AddInteger(RegNo);
1680 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1681 return SDValue(E, 0);
1683 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1684 CSEMap.InsertNode(N, IP);
1686 return SDValue(N, 0);
1689 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1690 FoldingSetNodeID ID;
1691 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1692 ID.AddPointer(RegMask);
1694 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1695 return SDValue(E, 0);
1697 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1698 CSEMap.InsertNode(N, IP);
1700 return SDValue(N, 0);
1703 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1704 FoldingSetNodeID ID;
1705 SDValue Ops[] = { Root };
1706 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1707 ID.AddPointer(Label);
1709 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1710 return SDValue(E, 0);
1712 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1713 dl.getDebugLoc(), Root, Label);
1714 CSEMap.InsertNode(N, IP);
1716 return SDValue(N, 0);
1720 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1723 unsigned char TargetFlags) {
1724 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1729 ID.AddInteger(Offset);
1730 ID.AddInteger(TargetFlags);
1732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1733 return SDValue(E, 0);
1735 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1737 CSEMap.InsertNode(N, IP);
1739 return SDValue(N, 0);
1742 SDValue SelectionDAG::getSrcValue(const Value *V) {
1743 assert((!V || V->getType()->isPointerTy()) &&
1744 "SrcValue is not a pointer?");
1746 FoldingSetNodeID ID;
1747 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1751 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1752 return SDValue(E, 0);
1754 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1755 CSEMap.InsertNode(N, IP);
1757 return SDValue(N, 0);
1760 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1761 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1762 FoldingSetNodeID ID;
1763 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1767 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1768 return SDValue(E, 0);
1770 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1771 CSEMap.InsertNode(N, IP);
1773 return SDValue(N, 0);
1776 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1777 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1778 unsigned SrcAS, unsigned DestAS) {
1779 SDValue Ops[] = {Ptr};
1780 FoldingSetNodeID ID;
1781 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1782 ID.AddInteger(SrcAS);
1783 ID.AddInteger(DestAS);
1786 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1787 return SDValue(E, 0);
1789 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1791 VT, Ptr, SrcAS, DestAS);
1792 CSEMap.InsertNode(N, IP);
1794 return SDValue(N, 0);
1797 /// getShiftAmountOperand - Return the specified value casted to
1798 /// the target's desired shift amount type.
1799 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1800 EVT OpTy = Op.getValueType();
1801 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1802 if (OpTy == ShTy || OpTy.isVector()) return Op;
1804 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1805 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1808 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1809 /// specified value type.
1810 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1811 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1812 unsigned ByteSize = VT.getStoreSize();
1813 Type *Ty = VT.getTypeForEVT(*getContext());
1814 unsigned StackAlign =
1815 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1817 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1818 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1821 /// CreateStackTemporary - Create a stack temporary suitable for holding
1822 /// either of the specified value types.
1823 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1824 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1825 VT2.getStoreSizeInBits())/8;
1826 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1827 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1828 const DataLayout *TD = TLI->getDataLayout();
1829 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1830 TD->getPrefTypeAlignment(Ty2));
1832 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1833 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1834 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1837 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1838 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1839 // These setcc operations always fold.
1843 case ISD::SETFALSE2: return getConstant(0, VT);
1845 case ISD::SETTRUE2: {
1846 TargetLowering::BooleanContent Cnt =
1847 TLI->getBooleanContents(N1->getValueType(0));
1849 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1862 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1866 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1867 const APInt &C2 = N2C->getAPIntValue();
1868 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1869 const APInt &C1 = N1C->getAPIntValue();
1872 default: llvm_unreachable("Unknown integer setcc!");
1873 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1874 case ISD::SETNE: return getConstant(C1 != C2, VT);
1875 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1876 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1877 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1878 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1879 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1880 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1881 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1882 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1886 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1887 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1888 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1891 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1892 return getUNDEF(VT);
1894 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1895 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1896 return getUNDEF(VT);
1898 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1899 R==APFloat::cmpLessThan, VT);
1900 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1901 return getUNDEF(VT);
1903 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1904 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1905 return getUNDEF(VT);
1907 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1908 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1909 return getUNDEF(VT);
1911 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1912 R==APFloat::cmpEqual, VT);
1913 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1914 return getUNDEF(VT);
1916 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1917 R==APFloat::cmpEqual, VT);
1918 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1919 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1920 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1921 R==APFloat::cmpEqual, VT);
1922 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1923 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1924 R==APFloat::cmpLessThan, VT);
1925 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1926 R==APFloat::cmpUnordered, VT);
1927 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1928 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1931 // Ensure that the constant occurs on the RHS.
1932 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1933 MVT CompVT = N1.getValueType().getSimpleVT();
1934 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1937 return getSetCC(dl, VT, N2, N1, SwappedCond);
1941 // Could not fold it.
1945 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1946 /// use this predicate to simplify operations downstream.
1947 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1948 // This predicate is not safe for vector operations.
1949 if (Op.getValueType().isVector())
1952 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1953 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1956 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1957 /// this predicate to simplify operations downstream. Mask is known to be zero
1958 /// for bits that V cannot have.
1959 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1960 unsigned Depth) const {
1961 APInt KnownZero, KnownOne;
1962 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1963 return (KnownZero & Mask) == Mask;
1966 /// Determine which bits of Op are known to be either zero or one and return
1967 /// them in the KnownZero/KnownOne bitsets.
1968 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1969 APInt &KnownOne, unsigned Depth) const {
1970 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1972 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1974 return; // Limit search depth.
1976 APInt KnownZero2, KnownOne2;
1978 switch (Op.getOpcode()) {
1980 // We know all of the bits for a constant!
1981 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1982 KnownZero = ~KnownOne;
1985 // If either the LHS or the RHS are Zero, the result is zero.
1986 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1987 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1989 // Output known-1 bits are only known if set in both the LHS & RHS.
1990 KnownOne &= KnownOne2;
1991 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1992 KnownZero |= KnownZero2;
1995 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1996 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1998 // Output known-0 bits are only known if clear in both the LHS & RHS.
1999 KnownZero &= KnownZero2;
2000 // Output known-1 are known to be set if set in either the LHS | RHS.
2001 KnownOne |= KnownOne2;
2004 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2005 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2007 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2008 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2009 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2010 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2011 KnownZero = KnownZeroOut;
2015 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2016 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2018 // If low bits are zero in either operand, output low known-0 bits.
2019 // Also compute a conserative estimate for high known-0 bits.
2020 // More trickiness is possible, but this is sufficient for the
2021 // interesting case of alignment computation.
2022 KnownOne.clearAllBits();
2023 unsigned TrailZ = KnownZero.countTrailingOnes() +
2024 KnownZero2.countTrailingOnes();
2025 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2026 KnownZero2.countLeadingOnes(),
2027 BitWidth) - BitWidth;
2029 TrailZ = std::min(TrailZ, BitWidth);
2030 LeadZ = std::min(LeadZ, BitWidth);
2031 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2032 APInt::getHighBitsSet(BitWidth, LeadZ);
2036 // For the purposes of computing leading zeros we can conservatively
2037 // treat a udiv as a logical right shift by the power of 2 known to
2038 // be less than the denominator.
2039 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2040 unsigned LeadZ = KnownZero2.countLeadingOnes();
2042 KnownOne2.clearAllBits();
2043 KnownZero2.clearAllBits();
2044 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2045 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2046 if (RHSUnknownLeadingOnes != BitWidth)
2047 LeadZ = std::min(BitWidth,
2048 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2050 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2054 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2055 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2057 // Only known if known in both the LHS and RHS.
2058 KnownOne &= KnownOne2;
2059 KnownZero &= KnownZero2;
2061 case ISD::SELECT_CC:
2062 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2063 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2065 // Only known if known in both the LHS and RHS.
2066 KnownOne &= KnownOne2;
2067 KnownZero &= KnownZero2;
2075 if (Op.getResNo() != 1)
2077 // The boolean result conforms to getBooleanContents.
2078 // If we know the result of a setcc has the top bits zero, use this info.
2079 // We know that we have an integer-based boolean since these operations
2080 // are only available for integer.
2081 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2082 TargetLowering::ZeroOrOneBooleanContent &&
2084 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2087 // If we know the result of a setcc has the top bits zero, use this info.
2088 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2089 TargetLowering::ZeroOrOneBooleanContent &&
2091 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2094 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2095 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2096 unsigned ShAmt = SA->getZExtValue();
2098 // If the shift count is an invalid immediate, don't do anything.
2099 if (ShAmt >= BitWidth)
2102 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2103 KnownZero <<= ShAmt;
2105 // low bits known zero.
2106 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2110 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2111 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2112 unsigned ShAmt = SA->getZExtValue();
2114 // If the shift count is an invalid immediate, don't do anything.
2115 if (ShAmt >= BitWidth)
2118 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2119 KnownZero = KnownZero.lshr(ShAmt);
2120 KnownOne = KnownOne.lshr(ShAmt);
2122 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2123 KnownZero |= HighBits; // High bits known zero.
2127 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2128 unsigned ShAmt = SA->getZExtValue();
2130 // If the shift count is an invalid immediate, don't do anything.
2131 if (ShAmt >= BitWidth)
2134 // If any of the demanded bits are produced by the sign extension, we also
2135 // demand the input sign bit.
2136 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2138 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2139 KnownZero = KnownZero.lshr(ShAmt);
2140 KnownOne = KnownOne.lshr(ShAmt);
2142 // Handle the sign bits.
2143 APInt SignBit = APInt::getSignBit(BitWidth);
2144 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2146 if (KnownZero.intersects(SignBit)) {
2147 KnownZero |= HighBits; // New bits are known zero.
2148 } else if (KnownOne.intersects(SignBit)) {
2149 KnownOne |= HighBits; // New bits are known one.
2153 case ISD::SIGN_EXTEND_INREG: {
2154 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2155 unsigned EBits = EVT.getScalarType().getSizeInBits();
2157 // Sign extension. Compute the demanded bits in the result that are not
2158 // present in the input.
2159 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2161 APInt InSignBit = APInt::getSignBit(EBits);
2162 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2164 // If the sign extended bits are demanded, we know that the sign
2166 InSignBit = InSignBit.zext(BitWidth);
2167 if (NewBits.getBoolValue())
2168 InputDemandedBits |= InSignBit;
2170 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2171 KnownOne &= InputDemandedBits;
2172 KnownZero &= InputDemandedBits;
2174 // If the sign bit of the input is known set or clear, then we know the
2175 // top bits of the result.
2176 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2177 KnownZero |= NewBits;
2178 KnownOne &= ~NewBits;
2179 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2180 KnownOne |= NewBits;
2181 KnownZero &= ~NewBits;
2182 } else { // Input sign bit unknown
2183 KnownZero &= ~NewBits;
2184 KnownOne &= ~NewBits;
2189 case ISD::CTTZ_ZERO_UNDEF:
2191 case ISD::CTLZ_ZERO_UNDEF:
2193 unsigned LowBits = Log2_32(BitWidth)+1;
2194 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2195 KnownOne.clearAllBits();
2199 LoadSDNode *LD = cast<LoadSDNode>(Op);
2200 // If this is a ZEXTLoad and we are looking at the loaded value.
2201 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2202 EVT VT = LD->getMemoryVT();
2203 unsigned MemBits = VT.getScalarType().getSizeInBits();
2204 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2205 } else if (const MDNode *Ranges = LD->getRanges()) {
2206 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2210 case ISD::ZERO_EXTEND: {
2211 EVT InVT = Op.getOperand(0).getValueType();
2212 unsigned InBits = InVT.getScalarType().getSizeInBits();
2213 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2214 KnownZero = KnownZero.trunc(InBits);
2215 KnownOne = KnownOne.trunc(InBits);
2216 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2217 KnownZero = KnownZero.zext(BitWidth);
2218 KnownOne = KnownOne.zext(BitWidth);
2219 KnownZero |= NewBits;
2222 case ISD::SIGN_EXTEND: {
2223 EVT InVT = Op.getOperand(0).getValueType();
2224 unsigned InBits = InVT.getScalarType().getSizeInBits();
2225 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2227 KnownZero = KnownZero.trunc(InBits);
2228 KnownOne = KnownOne.trunc(InBits);
2229 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2231 // Note if the sign bit is known to be zero or one.
2232 bool SignBitKnownZero = KnownZero.isNegative();
2233 bool SignBitKnownOne = KnownOne.isNegative();
2235 KnownZero = KnownZero.zext(BitWidth);
2236 KnownOne = KnownOne.zext(BitWidth);
2238 // If the sign bit is known zero or one, the top bits match.
2239 if (SignBitKnownZero)
2240 KnownZero |= NewBits;
2241 else if (SignBitKnownOne)
2242 KnownOne |= NewBits;
2245 case ISD::ANY_EXTEND: {
2246 EVT InVT = Op.getOperand(0).getValueType();
2247 unsigned InBits = InVT.getScalarType().getSizeInBits();
2248 KnownZero = KnownZero.trunc(InBits);
2249 KnownOne = KnownOne.trunc(InBits);
2250 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2251 KnownZero = KnownZero.zext(BitWidth);
2252 KnownOne = KnownOne.zext(BitWidth);
2255 case ISD::TRUNCATE: {
2256 EVT InVT = Op.getOperand(0).getValueType();
2257 unsigned InBits = InVT.getScalarType().getSizeInBits();
2258 KnownZero = KnownZero.zext(InBits);
2259 KnownOne = KnownOne.zext(InBits);
2260 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2261 KnownZero = KnownZero.trunc(BitWidth);
2262 KnownOne = KnownOne.trunc(BitWidth);
2265 case ISD::AssertZext: {
2266 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2267 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2268 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2269 KnownZero |= (~InMask);
2270 KnownOne &= (~KnownZero);
2274 // All bits are zero except the low bit.
2275 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2279 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2280 // We know that the top bits of C-X are clear if X contains less bits
2281 // than C (i.e. no wrap-around can happen). For example, 20-X is
2282 // positive if we can prove that X is >= 0 and < 16.
2283 if (CLHS->getAPIntValue().isNonNegative()) {
2284 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2285 // NLZ can't be BitWidth with no sign bit
2286 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2287 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2289 // If all of the MaskV bits are known to be zero, then we know the
2290 // output top bits are zero, because we now know that the output is
2292 if ((KnownZero2 & MaskV) == MaskV) {
2293 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2294 // Top bits known zero.
2295 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2303 // Output known-0 bits are known if clear or set in both the low clear bits
2304 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2305 // low 3 bits clear.
2306 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2307 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2309 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2310 KnownZeroOut = std::min(KnownZeroOut,
2311 KnownZero2.countTrailingOnes());
2313 if (Op.getOpcode() == ISD::ADD) {
2314 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2318 // With ADDE, a carry bit may be added in, so we can only use this
2319 // information if we know (at least) that the low two bits are clear. We
2320 // then return to the caller that the low bit is unknown but that other bits
2322 if (KnownZeroOut >= 2) // ADDE
2323 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2327 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2328 const APInt &RA = Rem->getAPIntValue().abs();
2329 if (RA.isPowerOf2()) {
2330 APInt LowBits = RA - 1;
2331 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2333 // The low bits of the first operand are unchanged by the srem.
2334 KnownZero = KnownZero2 & LowBits;
2335 KnownOne = KnownOne2 & LowBits;
2337 // If the first operand is non-negative or has all low bits zero, then
2338 // the upper bits are all zero.
2339 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2340 KnownZero |= ~LowBits;
2342 // If the first operand is negative and not all low bits are zero, then
2343 // the upper bits are all one.
2344 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2345 KnownOne |= ~LowBits;
2346 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2351 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2352 const APInt &RA = Rem->getAPIntValue();
2353 if (RA.isPowerOf2()) {
2354 APInt LowBits = (RA - 1);
2355 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2357 // The upper bits are all zero, the lower ones are unchanged.
2358 KnownZero = KnownZero2 | ~LowBits;
2359 KnownOne = KnownOne2 & LowBits;
2364 // Since the result is less than or equal to either operand, any leading
2365 // zero bits in either operand must also exist in the result.
2366 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2367 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2369 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2370 KnownZero2.countLeadingOnes());
2371 KnownOne.clearAllBits();
2372 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2375 case ISD::EXTRACT_ELEMENT: {
2376 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2377 const unsigned Index =
2378 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2379 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2381 // Remove low part of known bits mask
2382 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2383 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2385 // Remove high part of known bit mask
2386 KnownZero = KnownZero.trunc(BitWidth);
2387 KnownOne = KnownOne.trunc(BitWidth);
2390 case ISD::FrameIndex:
2391 case ISD::TargetFrameIndex:
2392 if (unsigned Align = InferPtrAlignment(Op)) {
2393 // The low bits are known zero if the pointer is aligned.
2394 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2400 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2403 case ISD::INTRINSIC_WO_CHAIN:
2404 case ISD::INTRINSIC_W_CHAIN:
2405 case ISD::INTRINSIC_VOID:
2406 // Allow the target to implement this method for its nodes.
2407 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2411 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2414 /// ComputeNumSignBits - Return the number of times the sign bit of the
2415 /// register is replicated into the other bits. We know that at least 1 bit
2416 /// is always equal to the sign bit (itself), but other cases can give us
2417 /// information. For example, immediately after an "SRA X, 2", we know that
2418 /// the top 3 bits are all equal to each other, so we return 3.
2419 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2420 EVT VT = Op.getValueType();
2421 assert(VT.isInteger() && "Invalid VT!");
2422 unsigned VTBits = VT.getScalarType().getSizeInBits();
2424 unsigned FirstAnswer = 1;
2427 return 1; // Limit search depth.
2429 switch (Op.getOpcode()) {
2431 case ISD::AssertSext:
2432 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2433 return VTBits-Tmp+1;
2434 case ISD::AssertZext:
2435 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2438 case ISD::Constant: {
2439 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2440 return Val.getNumSignBits();
2443 case ISD::SIGN_EXTEND:
2445 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2446 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2448 case ISD::SIGN_EXTEND_INREG:
2449 // Max of the input and what this extends.
2451 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2454 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2455 return std::max(Tmp, Tmp2);
2458 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2459 // SRA X, C -> adds C sign bits.
2460 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2461 Tmp += C->getZExtValue();
2462 if (Tmp > VTBits) Tmp = VTBits;
2466 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2467 // shl destroys sign bits.
2468 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2469 if (C->getZExtValue() >= VTBits || // Bad shift.
2470 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2471 return Tmp - C->getZExtValue();
2476 case ISD::XOR: // NOT is handled here.
2477 // Logical binary ops preserve the number of sign bits at the worst.
2478 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2480 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2481 FirstAnswer = std::min(Tmp, Tmp2);
2482 // We computed what we know about the sign bits as our first
2483 // answer. Now proceed to the generic code that uses
2484 // computeKnownBits, and pick whichever answer is better.
2489 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2490 if (Tmp == 1) return 1; // Early out.
2491 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2492 return std::min(Tmp, Tmp2);
2500 if (Op.getResNo() != 1)
2502 // The boolean result conforms to getBooleanContents. Fall through.
2503 // If setcc returns 0/-1, all bits are sign bits.
2504 // We know that we have an integer-based boolean since these operations
2505 // are only available for integer.
2506 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2507 TargetLowering::ZeroOrNegativeOneBooleanContent)
2511 // If setcc returns 0/-1, all bits are sign bits.
2512 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2513 TargetLowering::ZeroOrNegativeOneBooleanContent)
2518 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2519 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2521 // Handle rotate right by N like a rotate left by 32-N.
2522 if (Op.getOpcode() == ISD::ROTR)
2523 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2525 // If we aren't rotating out all of the known-in sign bits, return the
2526 // number that are left. This handles rotl(sext(x), 1) for example.
2527 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2528 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2532 // Add can have at most one carry bit. Thus we know that the output
2533 // is, at worst, one more bit than the inputs.
2534 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2535 if (Tmp == 1) return 1; // Early out.
2537 // Special case decrementing a value (ADD X, -1):
2538 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2539 if (CRHS->isAllOnesValue()) {
2540 APInt KnownZero, KnownOne;
2541 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2543 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2545 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2548 // If we are subtracting one from a positive number, there is no carry
2549 // out of the result.
2550 if (KnownZero.isNegative())
2554 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2555 if (Tmp2 == 1) return 1;
2556 return std::min(Tmp, Tmp2)-1;
2559 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2560 if (Tmp2 == 1) return 1;
2563 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2564 if (CLHS->isNullValue()) {
2565 APInt KnownZero, KnownOne;
2566 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2567 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2569 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2572 // If the input is known to be positive (the sign bit is known clear),
2573 // the output of the NEG has the same number of sign bits as the input.
2574 if (KnownZero.isNegative())
2577 // Otherwise, we treat this like a SUB.
2580 // Sub can have at most one carry bit. Thus we know that the output
2581 // is, at worst, one more bit than the inputs.
2582 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2583 if (Tmp == 1) return 1; // Early out.
2584 return std::min(Tmp, Tmp2)-1;
2586 // FIXME: it's tricky to do anything useful for this, but it is an important
2587 // case for targets like X86.
2589 case ISD::EXTRACT_ELEMENT: {
2590 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2591 const int BitWidth = Op.getValueType().getSizeInBits();
2593 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2595 // Get reverse index (starting from 1), Op1 value indexes elements from
2596 // little end. Sign starts at big end.
2597 const int rIndex = Items - 1 -
2598 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2600 // If the sign portion ends in our element the substraction gives correct
2601 // result. Otherwise it gives either negative or > bitwidth result
2602 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2606 // If we are looking at the loaded value of the SDNode.
2607 if (Op.getResNo() == 0) {
2608 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2609 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2610 unsigned ExtType = LD->getExtensionType();
2613 case ISD::SEXTLOAD: // '17' bits known
2614 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2615 return VTBits-Tmp+1;
2616 case ISD::ZEXTLOAD: // '16' bits known
2617 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2623 // Allow the target to implement this method for its nodes.
2624 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2625 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2626 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2627 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2628 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2629 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2632 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2633 // use this information.
2634 APInt KnownZero, KnownOne;
2635 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2638 if (KnownZero.isNegative()) { // sign bit is 0
2640 } else if (KnownOne.isNegative()) { // sign bit is 1;
2647 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2648 // the number of identical bits in the top of the input value.
2650 Mask <<= Mask.getBitWidth()-VTBits;
2651 // Return # leading zeros. We use 'min' here in case Val was zero before
2652 // shifting. We don't want to return '64' as for an i32 "0".
2653 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2656 /// isBaseWithConstantOffset - Return true if the specified operand is an
2657 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2658 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2659 /// semantics as an ADD. This handles the equivalence:
2660 /// X|Cst == X+Cst iff X&Cst = 0.
2661 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2662 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2663 !isa<ConstantSDNode>(Op.getOperand(1)))
2666 if (Op.getOpcode() == ISD::OR &&
2667 !MaskedValueIsZero(Op.getOperand(0),
2668 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2675 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2676 // If we're told that NaNs won't happen, assume they won't.
2677 if (getTarget().Options.NoNaNsFPMath)
2680 // If the value is a constant, we can obviously see if it is a NaN or not.
2681 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2682 return !C->getValueAPF().isNaN();
2684 // TODO: Recognize more cases here.
2689 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2690 // If the value is a constant, we can obviously see if it is a zero or not.
2691 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2692 return !C->isZero();
2694 // TODO: Recognize more cases here.
2695 switch (Op.getOpcode()) {
2698 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2699 return !C->isNullValue();
2706 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2707 // Check the obvious case.
2708 if (A == B) return true;
2710 // For for negative and positive zero.
2711 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2712 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2713 if (CA->isZero() && CB->isZero()) return true;
2715 // Otherwise they may not be equal.
2719 /// getNode - Gets or creates the specified node.
2721 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2722 FoldingSetNodeID ID;
2723 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2725 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2726 return SDValue(E, 0);
2728 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2729 DL.getDebugLoc(), getVTList(VT));
2730 CSEMap.InsertNode(N, IP);
2733 return SDValue(N, 0);
2736 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2737 EVT VT, SDValue Operand) {
2738 // Constant fold unary operations with an integer constant operand. Even
2739 // opaque constant will be folded, because the folding of unary operations
2740 // doesn't create new constants with different values. Nevertheless, the
2741 // opaque flag is preserved during folding to prevent future folding with
2743 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2744 const APInt &Val = C->getAPIntValue();
2747 case ISD::SIGN_EXTEND:
2748 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2749 C->isTargetOpcode(), C->isOpaque());
2750 case ISD::ANY_EXTEND:
2751 case ISD::ZERO_EXTEND:
2753 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2754 C->isTargetOpcode(), C->isOpaque());
2755 case ISD::UINT_TO_FP:
2756 case ISD::SINT_TO_FP: {
2757 APFloat apf(EVTToAPFloatSemantics(VT),
2758 APInt::getNullValue(VT.getSizeInBits()));
2759 (void)apf.convertFromAPInt(Val,
2760 Opcode==ISD::SINT_TO_FP,
2761 APFloat::rmNearestTiesToEven);
2762 return getConstantFP(apf, VT);
2765 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2766 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2767 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2768 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2769 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2770 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2773 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2776 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2779 case ISD::CTLZ_ZERO_UNDEF:
2780 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2783 case ISD::CTTZ_ZERO_UNDEF:
2784 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2789 // Constant fold unary operations with a floating point constant operand.
2790 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2791 APFloat V = C->getValueAPF(); // make copy
2795 return getConstantFP(V, VT);
2798 return getConstantFP(V, VT);
2800 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2801 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2802 return getConstantFP(V, VT);
2806 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2807 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2808 return getConstantFP(V, VT);
2812 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2813 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2814 return getConstantFP(V, VT);
2817 case ISD::FP_EXTEND: {
2819 // This can return overflow, underflow, or inexact; we don't care.
2820 // FIXME need to be more flexible about rounding mode.
2821 (void)V.convert(EVTToAPFloatSemantics(VT),
2822 APFloat::rmNearestTiesToEven, &ignored);
2823 return getConstantFP(V, VT);
2825 case ISD::FP_TO_SINT:
2826 case ISD::FP_TO_UINT: {
2829 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2830 // FIXME need to be more flexible about rounding mode.
2831 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2832 Opcode==ISD::FP_TO_SINT,
2833 APFloat::rmTowardZero, &ignored);
2834 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2836 APInt api(VT.getSizeInBits(), x);
2837 return getConstant(api, VT);
2840 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2841 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2842 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2843 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2844 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2845 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2850 // Constant fold unary operations with a vector integer operand.
2851 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2852 if (BV->isConstant()) {
2855 // FIXME: Entirely reasonable to perform folding of other unary
2856 // operations here as the need arises.
2858 case ISD::UINT_TO_FP:
2859 case ISD::SINT_TO_FP: {
2860 SmallVector<SDValue, 8> Ops;
2861 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2862 SDValue OpN = BV->getOperand(i);
2863 // Let the above scalar folding handle the conversion of each
2865 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2869 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2875 unsigned OpOpcode = Operand.getNode()->getOpcode();
2877 case ISD::TokenFactor:
2878 case ISD::MERGE_VALUES:
2879 case ISD::CONCAT_VECTORS:
2880 return Operand; // Factor, merge or concat of one node? No need.
2881 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2882 case ISD::FP_EXTEND:
2883 assert(VT.isFloatingPoint() &&
2884 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2885 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2886 assert((!VT.isVector() ||
2887 VT.getVectorNumElements() ==
2888 Operand.getValueType().getVectorNumElements()) &&
2889 "Vector element count mismatch!");
2890 if (Operand.getOpcode() == ISD::UNDEF)
2891 return getUNDEF(VT);
2893 case ISD::SIGN_EXTEND:
2894 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2895 "Invalid SIGN_EXTEND!");
2896 if (Operand.getValueType() == VT) return Operand; // noop extension
2897 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2898 "Invalid sext node, dst < src!");
2899 assert((!VT.isVector() ||
2900 VT.getVectorNumElements() ==
2901 Operand.getValueType().getVectorNumElements()) &&
2902 "Vector element count mismatch!");
2903 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2904 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2905 else if (OpOpcode == ISD::UNDEF)
2906 // sext(undef) = 0, because the top bits will all be the same.
2907 return getConstant(0, VT);
2909 case ISD::ZERO_EXTEND:
2910 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2911 "Invalid ZERO_EXTEND!");
2912 if (Operand.getValueType() == VT) return Operand; // noop extension
2913 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2914 "Invalid zext node, dst < src!");
2915 assert((!VT.isVector() ||
2916 VT.getVectorNumElements() ==
2917 Operand.getValueType().getVectorNumElements()) &&
2918 "Vector element count mismatch!");
2919 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2920 return getNode(ISD::ZERO_EXTEND, DL, VT,
2921 Operand.getNode()->getOperand(0));
2922 else if (OpOpcode == ISD::UNDEF)
2923 // zext(undef) = 0, because the top bits will be zero.
2924 return getConstant(0, VT);
2926 case ISD::ANY_EXTEND:
2927 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2928 "Invalid ANY_EXTEND!");
2929 if (Operand.getValueType() == VT) return Operand; // noop extension
2930 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2931 "Invalid anyext node, dst < src!");
2932 assert((!VT.isVector() ||
2933 VT.getVectorNumElements() ==
2934 Operand.getValueType().getVectorNumElements()) &&
2935 "Vector element count mismatch!");
2937 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2938 OpOpcode == ISD::ANY_EXTEND)
2939 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2940 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2941 else if (OpOpcode == ISD::UNDEF)
2942 return getUNDEF(VT);
2944 // (ext (trunx x)) -> x
2945 if (OpOpcode == ISD::TRUNCATE) {
2946 SDValue OpOp = Operand.getNode()->getOperand(0);
2947 if (OpOp.getValueType() == VT)
2952 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2953 "Invalid TRUNCATE!");
2954 if (Operand.getValueType() == VT) return Operand; // noop truncate
2955 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2956 "Invalid truncate node, src < dst!");
2957 assert((!VT.isVector() ||
2958 VT.getVectorNumElements() ==
2959 Operand.getValueType().getVectorNumElements()) &&
2960 "Vector element count mismatch!");
2961 if (OpOpcode == ISD::TRUNCATE)
2962 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2963 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2964 OpOpcode == ISD::ANY_EXTEND) {
2965 // If the source is smaller than the dest, we still need an extend.
2966 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2967 .bitsLT(VT.getScalarType()))
2968 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2969 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2970 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2971 return Operand.getNode()->getOperand(0);
2973 if (OpOpcode == ISD::UNDEF)
2974 return getUNDEF(VT);
2977 // Basic sanity checking.
2978 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2979 && "Cannot BITCAST between types of different sizes!");
2980 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2981 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2982 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2983 if (OpOpcode == ISD::UNDEF)
2984 return getUNDEF(VT);
2986 case ISD::SCALAR_TO_VECTOR:
2987 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2988 (VT.getVectorElementType() == Operand.getValueType() ||
2989 (VT.getVectorElementType().isInteger() &&
2990 Operand.getValueType().isInteger() &&
2991 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2992 "Illegal SCALAR_TO_VECTOR node!");
2993 if (OpOpcode == ISD::UNDEF)
2994 return getUNDEF(VT);
2995 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2996 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2997 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2998 Operand.getConstantOperandVal(1) == 0 &&
2999 Operand.getOperand(0).getValueType() == VT)
3000 return Operand.getOperand(0);
3003 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3004 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3005 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3006 Operand.getNode()->getOperand(0));
3007 if (OpOpcode == ISD::FNEG) // --X -> X
3008 return Operand.getNode()->getOperand(0);
3011 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3012 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3017 SDVTList VTs = getVTList(VT);
3018 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3019 FoldingSetNodeID ID;
3020 SDValue Ops[1] = { Operand };
3021 AddNodeIDNode(ID, Opcode, VTs, Ops);
3023 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3024 return SDValue(E, 0);
3026 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3027 DL.getDebugLoc(), VTs, Operand);
3028 CSEMap.InsertNode(N, IP);
3030 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3031 DL.getDebugLoc(), VTs, Operand);
3035 return SDValue(N, 0);
3038 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3039 SDNode *Cst1, SDNode *Cst2) {
3040 // If the opcode is a target-specific ISD node, there's nothing we can
3041 // do here and the operand rules may not line up with the below, so
3043 if (Opcode >= ISD::BUILTIN_OP_END)
3046 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3047 SmallVector<SDValue, 4> Outputs;
3048 EVT SVT = VT.getScalarType();
3050 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3051 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3052 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3055 if (Scalar1 && Scalar2)
3056 // Scalar instruction.
3057 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3059 // For vectors extract each constant element into Inputs so we can constant
3060 // fold them individually.
3061 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3062 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3066 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3068 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3069 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3070 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3071 if (!V1 || !V2) // Not a constant, bail.
3074 if (V1->isOpaque() || V2->isOpaque())
3077 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3078 // FIXME: This is valid and could be handled by truncating the APInts.
3079 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3082 Inputs.push_back(std::make_pair(V1, V2));
3086 // We have a number of constant values, constant fold them element by element.
3087 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3088 const APInt &C1 = Inputs[I].first->getAPIntValue();
3089 const APInt &C2 = Inputs[I].second->getAPIntValue();
3093 Outputs.push_back(getConstant(C1 + C2, SVT));
3096 Outputs.push_back(getConstant(C1 - C2, SVT));
3099 Outputs.push_back(getConstant(C1 * C2, SVT));
3102 if (!C2.getBoolValue())
3104 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3107 if (!C2.getBoolValue())
3109 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3112 if (!C2.getBoolValue())
3114 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3117 if (!C2.getBoolValue())
3119 Outputs.push_back(getConstant(C1.srem(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 << C2, SVT));
3134 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3137 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3140 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3143 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3150 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3151 "Expected a scalar or vector!"));
3153 // Handle the scalar case first.
3155 return Outputs.back();
3157 // We may have a vector type but a scalar result. Create a splat.
3158 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3160 // Build a big vector out of the scalar elements we generated.
3161 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3164 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3165 SDValue N2, bool nuw, bool nsw, bool exact) {
3166 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3167 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3170 case ISD::TokenFactor:
3171 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3172 N2.getValueType() == MVT::Other && "Invalid token factor!");
3173 // Fold trivial token factors.
3174 if (N1.getOpcode() == ISD::EntryToken) return N2;
3175 if (N2.getOpcode() == ISD::EntryToken) return N1;
3176 if (N1 == N2) return N1;
3178 case ISD::CONCAT_VECTORS:
3179 // Concat of UNDEFs is UNDEF.
3180 if (N1.getOpcode() == ISD::UNDEF &&
3181 N2.getOpcode() == ISD::UNDEF)
3182 return getUNDEF(VT);
3184 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3185 // one big BUILD_VECTOR.
3186 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3187 N2.getOpcode() == ISD::BUILD_VECTOR) {
3188 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3189 N1.getNode()->op_end());
3190 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3191 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3195 assert(VT.isInteger() && "This operator does not apply to FP types!");
3196 assert(N1.getValueType() == N2.getValueType() &&
3197 N1.getValueType() == VT && "Binary operator types must match!");
3198 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3199 // worth handling here.
3200 if (N2C && N2C->isNullValue())
3202 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3209 assert(VT.isInteger() && "This operator does not apply to FP types!");
3210 assert(N1.getValueType() == N2.getValueType() &&
3211 N1.getValueType() == VT && "Binary operator types must match!");
3212 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3213 // it's worth handling here.
3214 if (N2C && N2C->isNullValue())
3224 assert(VT.isInteger() && "This operator does not apply to FP types!");
3225 assert(N1.getValueType() == N2.getValueType() &&
3226 N1.getValueType() == VT && "Binary operator types must match!");
3233 if (getTarget().Options.UnsafeFPMath) {
3234 if (Opcode == ISD::FADD) {
3236 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3237 if (CFP->getValueAPF().isZero())
3240 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3241 if (CFP->getValueAPF().isZero())
3243 } else if (Opcode == ISD::FSUB) {
3245 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3246 if (CFP->getValueAPF().isZero())
3248 } else if (Opcode == ISD::FMUL) {
3249 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3252 // If the first operand isn't the constant, try the second
3254 CFP = dyn_cast<ConstantFPSDNode>(N2);
3261 return SDValue(CFP,0);
3263 if (CFP->isExactlyValue(1.0))
3268 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3269 assert(N1.getValueType() == N2.getValueType() &&
3270 N1.getValueType() == VT && "Binary operator types must match!");
3272 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3273 assert(N1.getValueType() == VT &&
3274 N1.getValueType().isFloatingPoint() &&
3275 N2.getValueType().isFloatingPoint() &&
3276 "Invalid FCOPYSIGN!");
3283 assert(VT == N1.getValueType() &&
3284 "Shift operators return type must be the same as their first arg");
3285 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3286 "Shifts only work on integers");
3287 assert((!VT.isVector() || VT == N2.getValueType()) &&
3288 "Vector shift amounts must be in the same as their first arg");
3289 // Verify that the shift amount VT is bit enough to hold valid shift
3290 // amounts. This catches things like trying to shift an i1024 value by an
3291 // i8, which is easy to fall into in generic code that uses
3292 // TLI.getShiftAmount().
3293 assert(N2.getValueType().getSizeInBits() >=
3294 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3295 "Invalid use of small shift amount with oversized value!");
3297 // Always fold shifts of i1 values so the code generator doesn't need to
3298 // handle them. Since we know the size of the shift has to be less than the
3299 // size of the value, the shift/rotate count is guaranteed to be zero.
3302 if (N2C && N2C->isNullValue())
3305 case ISD::FP_ROUND_INREG: {
3306 EVT EVT = cast<VTSDNode>(N2)->getVT();
3307 assert(VT == N1.getValueType() && "Not an inreg round!");
3308 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3309 "Cannot FP_ROUND_INREG integer types");
3310 assert(EVT.isVector() == VT.isVector() &&
3311 "FP_ROUND_INREG type should be vector iff the operand "
3313 assert((!EVT.isVector() ||
3314 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3315 "Vector element counts must match in FP_ROUND_INREG");
3316 assert(EVT.bitsLE(VT) && "Not rounding down!");
3318 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3322 assert(VT.isFloatingPoint() &&
3323 N1.getValueType().isFloatingPoint() &&
3324 VT.bitsLE(N1.getValueType()) &&
3325 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3326 if (N1.getValueType() == VT) return N1; // noop conversion.
3328 case ISD::AssertSext:
3329 case ISD::AssertZext: {
3330 EVT EVT = cast<VTSDNode>(N2)->getVT();
3331 assert(VT == N1.getValueType() && "Not an inreg extend!");
3332 assert(VT.isInteger() && EVT.isInteger() &&
3333 "Cannot *_EXTEND_INREG FP types");
3334 assert(!EVT.isVector() &&
3335 "AssertSExt/AssertZExt type should be the vector element type "
3336 "rather than the vector type!");
3337 assert(EVT.bitsLE(VT) && "Not extending!");
3338 if (VT == EVT) return N1; // noop assertion.
3341 case ISD::SIGN_EXTEND_INREG: {
3342 EVT EVT = cast<VTSDNode>(N2)->getVT();
3343 assert(VT == N1.getValueType() && "Not an inreg extend!");
3344 assert(VT.isInteger() && EVT.isInteger() &&
3345 "Cannot *_EXTEND_INREG FP types");
3346 assert(EVT.isVector() == VT.isVector() &&
3347 "SIGN_EXTEND_INREG type should be vector iff the operand "
3349 assert((!EVT.isVector() ||
3350 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3351 "Vector element counts must match in SIGN_EXTEND_INREG");
3352 assert(EVT.bitsLE(VT) && "Not extending!");
3353 if (EVT == VT) return N1; // Not actually extending
3356 APInt Val = N1C->getAPIntValue();
3357 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3358 Val <<= Val.getBitWidth()-FromBits;
3359 Val = Val.ashr(Val.getBitWidth()-FromBits);
3360 return getConstant(Val, VT);
3364 case ISD::EXTRACT_VECTOR_ELT:
3365 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3366 if (N1.getOpcode() == ISD::UNDEF)
3367 return getUNDEF(VT);
3369 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3370 // expanding copies of large vectors from registers.
3372 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3373 N1.getNumOperands() > 0) {
3375 N1.getOperand(0).getValueType().getVectorNumElements();
3376 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3377 N1.getOperand(N2C->getZExtValue() / Factor),
3378 getConstant(N2C->getZExtValue() % Factor,
3379 N2.getValueType()));
3382 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3383 // expanding large vector constants.
3384 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3385 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3387 if (VT != Elt.getValueType())
3388 // If the vector element type is not legal, the BUILD_VECTOR operands
3389 // are promoted and implicitly truncated, and the result implicitly
3390 // extended. Make that explicit here.
3391 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3396 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3397 // operations are lowered to scalars.
3398 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3399 // If the indices are the same, return the inserted element else
3400 // if the indices are known different, extract the element from
3401 // the original vector.
3402 SDValue N1Op2 = N1.getOperand(2);
3403 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3405 if (N1Op2C && N2C) {
3406 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3407 if (VT == N1.getOperand(1).getValueType())
3408 return N1.getOperand(1);
3410 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3413 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3417 case ISD::EXTRACT_ELEMENT:
3418 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3419 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3420 (N1.getValueType().isInteger() == VT.isInteger()) &&
3421 N1.getValueType() != VT &&
3422 "Wrong types for EXTRACT_ELEMENT!");
3424 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3425 // 64-bit integers into 32-bit parts. Instead of building the extract of
3426 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3427 if (N1.getOpcode() == ISD::BUILD_PAIR)
3428 return N1.getOperand(N2C->getZExtValue());
3430 // EXTRACT_ELEMENT of a constant int is also very common.
3431 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3432 unsigned ElementSize = VT.getSizeInBits();
3433 unsigned Shift = ElementSize * N2C->getZExtValue();
3434 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3435 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3438 case ISD::EXTRACT_SUBVECTOR: {
3440 if (VT.isSimple() && N1.getValueType().isSimple()) {
3441 assert(VT.isVector() && N1.getValueType().isVector() &&
3442 "Extract subvector VTs must be a vectors!");
3443 assert(VT.getVectorElementType() ==
3444 N1.getValueType().getVectorElementType() &&
3445 "Extract subvector VTs must have the same element type!");
3446 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3447 "Extract subvector must be from larger vector to smaller vector!");
3449 if (isa<ConstantSDNode>(Index.getNode())) {
3450 assert((VT.getVectorNumElements() +
3451 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3452 <= N1.getValueType().getVectorNumElements())
3453 && "Extract subvector overflow!");
3456 // Trivial extraction.
3457 if (VT.getSimpleVT() == N1.getSimpleValueType())
3464 // Perform trivial constant folding.
3466 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3469 // Canonicalize constant to RHS if commutative.
3470 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3471 std::swap(N1C, N2C);
3475 // Constant fold FP operations.
3476 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3477 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3478 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3480 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3481 // Canonicalize constant to RHS if commutative.
3482 std::swap(N1CFP, N2CFP);
3485 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3486 APFloat::opStatus s;
3489 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3490 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3491 return getConstantFP(V1, VT);
3494 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3495 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3496 return getConstantFP(V1, VT);
3499 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3500 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3501 return getConstantFP(V1, VT);
3504 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3505 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3506 s!=APFloat::opDivByZero)) {
3507 return getConstantFP(V1, VT);
3511 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3512 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3513 s!=APFloat::opDivByZero)) {
3514 return getConstantFP(V1, VT);
3517 case ISD::FCOPYSIGN:
3519 return getConstantFP(V1, VT);
3524 if (Opcode == ISD::FP_ROUND) {
3525 APFloat V = N1CFP->getValueAPF(); // make copy
3527 // This can return overflow, underflow, or inexact; we don't care.
3528 // FIXME need to be more flexible about rounding mode.
3529 (void)V.convert(EVTToAPFloatSemantics(VT),
3530 APFloat::rmNearestTiesToEven, &ignored);
3531 return getConstantFP(V, VT);
3535 // Canonicalize an UNDEF to the RHS, even over a constant.
3536 if (N1.getOpcode() == ISD::UNDEF) {
3537 if (isCommutativeBinOp(Opcode)) {
3541 case ISD::FP_ROUND_INREG:
3542 case ISD::SIGN_EXTEND_INREG:
3548 return N1; // fold op(undef, arg2) -> undef
3556 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3557 // For vectors, we can't easily build an all zero vector, just return
3564 // Fold a bunch of operators when the RHS is undef.
3565 if (N2.getOpcode() == ISD::UNDEF) {
3568 if (N1.getOpcode() == ISD::UNDEF)
3569 // Handle undef ^ undef -> 0 special case. This is a common
3571 return getConstant(0, VT);
3581 return N2; // fold op(arg1, undef) -> undef
3587 if (getTarget().Options.UnsafeFPMath)
3595 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3596 // For vectors, we can't easily build an all zero vector, just return
3601 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3602 // For vectors, we can't easily build an all one vector, just return
3610 // Memoize this node if possible.
3612 SDVTList VTs = getVTList(VT);
3613 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3614 if (VT != MVT::Glue) {
3615 SDValue Ops[] = {N1, N2};
3616 FoldingSetNodeID ID;
3617 AddNodeIDNode(ID, Opcode, VTs, Ops);
3619 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3621 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3622 return SDValue(E, 0);
3624 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3626 CSEMap.InsertNode(N, IP);
3629 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3633 return SDValue(N, 0);
3636 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3637 SDValue N1, SDValue N2, SDValue N3) {
3638 // Perform various simplifications.
3639 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3642 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3643 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3644 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3645 if (N1CFP && N2CFP && N3CFP) {
3646 APFloat V1 = N1CFP->getValueAPF();
3647 const APFloat &V2 = N2CFP->getValueAPF();
3648 const APFloat &V3 = N3CFP->getValueAPF();
3649 APFloat::opStatus s =
3650 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3651 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3652 return getConstantFP(V1, VT);
3656 case ISD::CONCAT_VECTORS:
3657 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3658 // one big BUILD_VECTOR.
3659 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3660 N2.getOpcode() == ISD::BUILD_VECTOR &&
3661 N3.getOpcode() == ISD::BUILD_VECTOR) {
3662 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3663 N1.getNode()->op_end());
3664 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3665 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3666 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3670 // Use FoldSetCC to simplify SETCC's.
3671 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3672 if (Simp.getNode()) return Simp;
3677 if (N1C->getZExtValue())
3678 return N2; // select true, X, Y -> X
3679 return N3; // select false, X, Y -> Y
3682 if (N2 == N3) return N2; // select C, X, X -> X
3684 case ISD::VECTOR_SHUFFLE:
3685 llvm_unreachable("should use getVectorShuffle constructor!");
3686 case ISD::INSERT_SUBVECTOR: {
3688 if (VT.isSimple() && N1.getValueType().isSimple()
3689 && N2.getValueType().isSimple()) {
3690 assert(VT.isVector() && N1.getValueType().isVector() &&
3691 N2.getValueType().isVector() &&
3692 "Insert subvector VTs must be a vectors");
3693 assert(VT == N1.getValueType() &&
3694 "Dest and insert subvector source types must match!");
3695 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3696 "Insert subvector must be from smaller vector to larger vector!");
3697 if (isa<ConstantSDNode>(Index.getNode())) {
3698 assert((N2.getValueType().getVectorNumElements() +
3699 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3700 <= VT.getVectorNumElements())
3701 && "Insert subvector overflow!");
3704 // Trivial insertion.
3705 if (VT.getSimpleVT() == N2.getSimpleValueType())
3711 // Fold bit_convert nodes from a type to themselves.
3712 if (N1.getValueType() == VT)
3717 // Memoize node if it doesn't produce a flag.
3719 SDVTList VTs = getVTList(VT);
3720 if (VT != MVT::Glue) {
3721 SDValue Ops[] = { N1, N2, N3 };
3722 FoldingSetNodeID ID;
3723 AddNodeIDNode(ID, Opcode, VTs, Ops);
3725 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3726 return SDValue(E, 0);
3728 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3729 DL.getDebugLoc(), VTs, N1, N2, N3);
3730 CSEMap.InsertNode(N, IP);
3732 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3733 DL.getDebugLoc(), VTs, N1, N2, N3);
3737 return SDValue(N, 0);
3740 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3741 SDValue N1, SDValue N2, SDValue N3,
3743 SDValue Ops[] = { N1, N2, N3, N4 };
3744 return getNode(Opcode, DL, VT, Ops);
3747 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3748 SDValue N1, SDValue N2, SDValue N3,
3749 SDValue N4, SDValue N5) {
3750 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3751 return getNode(Opcode, DL, VT, Ops);
3754 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3755 /// the incoming stack arguments to be loaded from the stack.
3756 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3757 SmallVector<SDValue, 8> ArgChains;
3759 // Include the original chain at the beginning of the list. When this is
3760 // used by target LowerCall hooks, this helps legalize find the
3761 // CALLSEQ_BEGIN node.
3762 ArgChains.push_back(Chain);
3764 // Add a chain value for each stack argument.
3765 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3766 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3767 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3768 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3769 if (FI->getIndex() < 0)
3770 ArgChains.push_back(SDValue(L, 1));
3772 // Build a tokenfactor for all the chains.
3773 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3776 /// getMemsetValue - Vectorized representation of the memset value
3778 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3780 assert(Value.getOpcode() != ISD::UNDEF);
3782 unsigned NumBits = VT.getScalarType().getSizeInBits();
3783 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3784 assert(C->getAPIntValue().getBitWidth() == 8);
3785 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3787 return DAG.getConstant(Val, VT);
3788 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3791 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3793 // Use a multiplication with 0x010101... to extend the input to the
3795 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3796 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3802 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3803 /// used when a memcpy is turned into a memset when the source is a constant
3805 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3806 const TargetLowering &TLI, StringRef Str) {
3807 // Handle vector with all elements zero.
3810 return DAG.getConstant(0, VT);
3811 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3812 return DAG.getConstantFP(0.0, VT);
3813 else if (VT.isVector()) {
3814 unsigned NumElts = VT.getVectorNumElements();
3815 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3816 return DAG.getNode(ISD::BITCAST, dl, VT,
3817 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3820 llvm_unreachable("Expected type!");
3823 assert(!VT.isVector() && "Can't handle vector type here!");
3824 unsigned NumVTBits = VT.getSizeInBits();
3825 unsigned NumVTBytes = NumVTBits / 8;
3826 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3828 APInt Val(NumVTBits, 0);
3829 if (TLI.isLittleEndian()) {
3830 for (unsigned i = 0; i != NumBytes; ++i)
3831 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3833 for (unsigned i = 0; i != NumBytes; ++i)
3834 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3837 // If the "cost" of materializing the integer immediate is less than the cost
3838 // of a load, then it is cost effective to turn the load into the immediate.
3839 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3840 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3841 return DAG.getConstant(Val, VT);
3842 return SDValue(nullptr, 0);
3845 /// getMemBasePlusOffset - Returns base and offset node for the
3847 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3848 SelectionDAG &DAG) {
3849 EVT VT = Base.getValueType();
3850 return DAG.getNode(ISD::ADD, dl,
3851 VT, Base, DAG.getConstant(Offset, VT));
3854 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3856 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3857 unsigned SrcDelta = 0;
3858 GlobalAddressSDNode *G = nullptr;
3859 if (Src.getOpcode() == ISD::GlobalAddress)
3860 G = cast<GlobalAddressSDNode>(Src);
3861 else if (Src.getOpcode() == ISD::ADD &&
3862 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3863 Src.getOperand(1).getOpcode() == ISD::Constant) {
3864 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3865 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3870 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3873 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3874 /// to replace the memset / memcpy. Return true if the number of memory ops
3875 /// is below the threshold. It returns the types of the sequence of
3876 /// memory ops to perform memset / memcpy by reference.
3877 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3878 unsigned Limit, uint64_t Size,
3879 unsigned DstAlign, unsigned SrcAlign,
3885 const TargetLowering &TLI) {
3886 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3887 "Expecting memcpy / memset source to meet alignment requirement!");
3888 // If 'SrcAlign' is zero, that means the memory operation does not need to
3889 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3890 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3891 // is the specified alignment of the memory operation. If it is zero, that
3892 // means it's possible to change the alignment of the destination.
3893 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3894 // not need to be loaded.
3895 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3896 IsMemset, ZeroMemset, MemcpyStrSrc,
3897 DAG.getMachineFunction());
3899 if (VT == MVT::Other) {
3901 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3902 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3903 VT = TLI.getPointerTy();
3905 switch (DstAlign & 7) {
3906 case 0: VT = MVT::i64; break;
3907 case 4: VT = MVT::i32; break;
3908 case 2: VT = MVT::i16; break;
3909 default: VT = MVT::i8; break;
3914 while (!TLI.isTypeLegal(LVT))
3915 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3916 assert(LVT.isInteger());
3922 unsigned NumMemOps = 0;
3924 unsigned VTSize = VT.getSizeInBits() / 8;
3925 while (VTSize > Size) {
3926 // For now, only use non-vector load / store's for the left-over pieces.
3931 if (VT.isVector() || VT.isFloatingPoint()) {
3932 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3933 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3934 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3936 else if (NewVT == MVT::i64 &&
3937 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3938 TLI.isSafeMemOpType(MVT::f64)) {
3939 // i64 is usually not legal on 32-bit targets, but f64 may be.
3947 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3948 if (NewVT == MVT::i8)
3950 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3952 NewVTSize = NewVT.getSizeInBits() / 8;
3954 // If the new VT cannot cover all of the remaining bits, then consider
3955 // issuing a (or a pair of) unaligned and overlapping load / store.
3956 // FIXME: Only does this for 64-bit or more since we don't have proper
3957 // cost model for unaligned load / store.
3960 if (NumMemOps && AllowOverlap &&
3961 VTSize >= 8 && NewVTSize < Size &&
3962 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3970 if (++NumMemOps > Limit)
3973 MemOps.push_back(VT);
3980 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3981 SDValue Chain, SDValue Dst,
3982 SDValue Src, uint64_t Size,
3983 unsigned Align, bool isVol,
3985 MachinePointerInfo DstPtrInfo,
3986 MachinePointerInfo SrcPtrInfo) {
3987 // Turn a memcpy of undef to nop.
3988 if (Src.getOpcode() == ISD::UNDEF)
3991 // Expand memcpy to a series of load and store ops if the size operand falls
3992 // below a certain threshold.
3993 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3994 // rather than maybe a humongous number of loads and stores.
3995 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3996 std::vector<EVT> MemOps;
3997 bool DstAlignCanChange = false;
3998 MachineFunction &MF = DAG.getMachineFunction();
3999 MachineFrameInfo *MFI = MF.getFrameInfo();
4000 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4001 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4002 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4003 DstAlignCanChange = true;
4004 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4005 if (Align > SrcAlign)
4008 bool CopyFromStr = isMemSrcFromString(Src, Str);
4009 bool isZeroStr = CopyFromStr && Str.empty();
4010 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4012 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4013 (DstAlignCanChange ? 0 : Align),
4014 (isZeroStr ? 0 : SrcAlign),
4015 false, false, CopyFromStr, true, DAG, TLI))
4018 if (DstAlignCanChange) {
4019 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4020 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4022 // Don't promote to an alignment that would require dynamic stack
4024 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4025 if (!TRI->needsStackRealignment(MF))
4026 while (NewAlign > Align &&
4027 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4030 if (NewAlign > Align) {
4031 // Give the stack frame object a larger alignment if needed.
4032 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4033 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4038 SmallVector<SDValue, 8> OutChains;
4039 unsigned NumMemOps = MemOps.size();
4040 uint64_t SrcOff = 0, DstOff = 0;
4041 for (unsigned i = 0; i != NumMemOps; ++i) {
4043 unsigned VTSize = VT.getSizeInBits() / 8;
4044 SDValue Value, Store;
4046 if (VTSize > Size) {
4047 // Issuing an unaligned load / store pair that overlaps with the previous
4048 // pair. Adjust the offset accordingly.
4049 assert(i == NumMemOps-1 && i != 0);
4050 SrcOff -= VTSize - Size;
4051 DstOff -= VTSize - Size;
4055 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4056 // It's unlikely a store of a vector immediate can be done in a single
4057 // instruction. It would require a load from a constantpool first.
4058 // We only handle zero vectors here.
4059 // FIXME: Handle other cases where store of vector immediate is done in
4060 // a single instruction.
4061 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4062 if (Value.getNode())
4063 Store = DAG.getStore(Chain, dl, Value,
4064 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4065 DstPtrInfo.getWithOffset(DstOff), isVol,
4069 if (!Store.getNode()) {
4070 // The type might not be legal for the target. This should only happen
4071 // if the type is smaller than a legal type, as on PPC, so the right
4072 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4073 // to Load/Store if NVT==VT.
4074 // FIXME does the case above also need this?
4075 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4076 assert(NVT.bitsGE(VT));
4077 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4078 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4079 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4080 false, MinAlign(SrcAlign, SrcOff));
4081 Store = DAG.getTruncStore(Chain, dl, Value,
4082 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4083 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4086 OutChains.push_back(Store);
4092 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4095 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4096 SDValue Chain, SDValue Dst,
4097 SDValue Src, uint64_t Size,
4098 unsigned Align, bool isVol,
4100 MachinePointerInfo DstPtrInfo,
4101 MachinePointerInfo SrcPtrInfo) {
4102 // Turn a memmove of undef to nop.
4103 if (Src.getOpcode() == ISD::UNDEF)
4106 // Expand memmove to a series of load and store ops if the size operand falls
4107 // below a certain threshold.
4108 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4109 std::vector<EVT> MemOps;
4110 bool DstAlignCanChange = false;
4111 MachineFunction &MF = DAG.getMachineFunction();
4112 MachineFrameInfo *MFI = MF.getFrameInfo();
4113 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4114 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4115 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4116 DstAlignCanChange = true;
4117 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4118 if (Align > SrcAlign)
4120 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4122 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4123 (DstAlignCanChange ? 0 : Align), SrcAlign,
4124 false, false, false, false, DAG, TLI))
4127 if (DstAlignCanChange) {
4128 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4129 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4130 if (NewAlign > Align) {
4131 // Give the stack frame object a larger alignment if needed.
4132 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4133 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4138 uint64_t SrcOff = 0, DstOff = 0;
4139 SmallVector<SDValue, 8> LoadValues;
4140 SmallVector<SDValue, 8> LoadChains;
4141 SmallVector<SDValue, 8> OutChains;
4142 unsigned NumMemOps = MemOps.size();
4143 for (unsigned i = 0; i < NumMemOps; i++) {
4145 unsigned VTSize = VT.getSizeInBits() / 8;
4148 Value = DAG.getLoad(VT, dl, Chain,
4149 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4150 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4151 false, false, SrcAlign);
4152 LoadValues.push_back(Value);
4153 LoadChains.push_back(Value.getValue(1));
4156 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4158 for (unsigned i = 0; i < NumMemOps; i++) {
4160 unsigned VTSize = VT.getSizeInBits() / 8;
4163 Store = DAG.getStore(Chain, dl, LoadValues[i],
4164 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4165 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4166 OutChains.push_back(Store);
4170 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4173 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4176 /// \param DAG Selection DAG where lowered code is placed.
4177 /// \param dl Link to corresponding IR location.
4178 /// \param Chain Control flow dependency.
4179 /// \param Dst Pointer to destination memory location.
4180 /// \param Src Value of byte to write into the memory.
4181 /// \param Size Number of bytes to write.
4182 /// \param Align Alignment of the destination in bytes.
4183 /// \param isVol True if destination is volatile.
4184 /// \param DstPtrInfo IR information on the memory pointer.
4185 /// \returns New head in the control flow, if lowering was successful, empty
4186 /// SDValue otherwise.
4188 /// The function tries to replace 'llvm.memset' intrinsic with several store
4189 /// operations and value calculation code. This is usually profitable for small
4191 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4192 SDValue Chain, SDValue Dst,
4193 SDValue Src, uint64_t Size,
4194 unsigned Align, bool isVol,
4195 MachinePointerInfo DstPtrInfo) {
4196 // Turn a memset of undef to nop.
4197 if (Src.getOpcode() == ISD::UNDEF)
4200 // Expand memset to a series of load/store ops if the size operand
4201 // falls below a certain threshold.
4202 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4203 std::vector<EVT> MemOps;
4204 bool DstAlignCanChange = false;
4205 MachineFunction &MF = DAG.getMachineFunction();
4206 MachineFrameInfo *MFI = MF.getFrameInfo();
4207 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4208 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4209 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4210 DstAlignCanChange = true;
4212 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4213 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4214 Size, (DstAlignCanChange ? 0 : Align), 0,
4215 true, IsZeroVal, false, true, DAG, TLI))
4218 if (DstAlignCanChange) {
4219 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4220 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4221 if (NewAlign > Align) {
4222 // Give the stack frame object a larger alignment if needed.
4223 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4224 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4229 SmallVector<SDValue, 8> OutChains;
4230 uint64_t DstOff = 0;
4231 unsigned NumMemOps = MemOps.size();
4233 // Find the largest store and generate the bit pattern for it.
4234 EVT LargestVT = MemOps[0];
4235 for (unsigned i = 1; i < NumMemOps; i++)
4236 if (MemOps[i].bitsGT(LargestVT))
4237 LargestVT = MemOps[i];
4238 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4240 for (unsigned i = 0; i < NumMemOps; i++) {
4242 unsigned VTSize = VT.getSizeInBits() / 8;
4243 if (VTSize > Size) {
4244 // Issuing an unaligned load / store pair that overlaps with the previous
4245 // pair. Adjust the offset accordingly.
4246 assert(i == NumMemOps-1 && i != 0);
4247 DstOff -= VTSize - Size;
4250 // If this store is smaller than the largest store see whether we can get
4251 // the smaller value for free with a truncate.
4252 SDValue Value = MemSetValue;
4253 if (VT.bitsLT(LargestVT)) {
4254 if (!LargestVT.isVector() && !VT.isVector() &&
4255 TLI.isTruncateFree(LargestVT, VT))
4256 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4258 Value = getMemsetValue(Src, VT, DAG, dl);
4260 assert(Value.getValueType() == VT && "Value with wrong type.");
4261 SDValue Store = DAG.getStore(Chain, dl, Value,
4262 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4263 DstPtrInfo.getWithOffset(DstOff),
4264 isVol, false, Align);
4265 OutChains.push_back(Store);
4266 DstOff += VT.getSizeInBits() / 8;
4270 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4273 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4274 SDValue Src, SDValue Size,
4275 unsigned Align, bool isVol, bool AlwaysInline,
4276 MachinePointerInfo DstPtrInfo,
4277 MachinePointerInfo SrcPtrInfo) {
4278 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4280 // Check to see if we should lower the memcpy to loads and stores first.
4281 // For cases within the target-specified limits, this is the best choice.
4282 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4284 // Memcpy with size zero? Just return the original chain.
4285 if (ConstantSize->isNullValue())
4288 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4289 ConstantSize->getZExtValue(),Align,
4290 isVol, false, DstPtrInfo, SrcPtrInfo);
4291 if (Result.getNode())
4295 // Then check to see if we should lower the memcpy with target-specific
4296 // code. If the target chooses to do this, this is the next best.
4298 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4299 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4300 DstPtrInfo, SrcPtrInfo);
4301 if (Result.getNode())
4305 // If we really need inline code and the target declined to provide it,
4306 // use a (potentially long) sequence of loads and stores.
4308 assert(ConstantSize && "AlwaysInline requires a constant size!");
4309 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4310 ConstantSize->getZExtValue(), Align, isVol,
4311 true, DstPtrInfo, SrcPtrInfo);
4314 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4315 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4316 // respect volatile, so they may do things like read or write memory
4317 // beyond the given memory regions. But fixing this isn't easy, and most
4318 // people don't care.
4320 // Emit a library call.
4321 TargetLowering::ArgListTy Args;
4322 TargetLowering::ArgListEntry Entry;
4323 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4324 Entry.Node = Dst; Args.push_back(Entry);
4325 Entry.Node = Src; Args.push_back(Entry);
4326 Entry.Node = Size; Args.push_back(Entry);
4327 // FIXME: pass in SDLoc
4328 TargetLowering::CallLoweringInfo CLI(*this);
4329 CLI.setDebugLoc(dl).setChain(Chain)
4330 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4331 Type::getVoidTy(*getContext()),
4332 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4333 TLI->getPointerTy()), std::move(Args), 0)
4334 .setDiscardResult();
4335 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4337 return CallResult.second;
4340 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4341 SDValue Src, SDValue Size,
4342 unsigned Align, bool isVol,
4343 MachinePointerInfo DstPtrInfo,
4344 MachinePointerInfo SrcPtrInfo) {
4345 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4347 // Check to see if we should lower the memmove to loads and stores first.
4348 // For cases within the target-specified limits, this is the best choice.
4349 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4351 // Memmove with size zero? Just return the original chain.
4352 if (ConstantSize->isNullValue())
4356 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4357 ConstantSize->getZExtValue(), Align, isVol,
4358 false, DstPtrInfo, SrcPtrInfo);
4359 if (Result.getNode())
4363 // Then check to see if we should lower the memmove with target-specific
4364 // code. If the target chooses to do this, this is the next best.
4366 SDValue Result = TSI->EmitTargetCodeForMemmove(
4367 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4368 if (Result.getNode())
4372 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4373 // not be safe. See memcpy above for more details.
4375 // Emit a library call.
4376 TargetLowering::ArgListTy Args;
4377 TargetLowering::ArgListEntry Entry;
4378 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4379 Entry.Node = Dst; Args.push_back(Entry);
4380 Entry.Node = Src; Args.push_back(Entry);
4381 Entry.Node = Size; Args.push_back(Entry);
4382 // FIXME: pass in SDLoc
4383 TargetLowering::CallLoweringInfo CLI(*this);
4384 CLI.setDebugLoc(dl).setChain(Chain)
4385 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4386 Type::getVoidTy(*getContext()),
4387 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4388 TLI->getPointerTy()), std::move(Args), 0)
4389 .setDiscardResult();
4390 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4392 return CallResult.second;
4395 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4396 SDValue Src, SDValue Size,
4397 unsigned Align, bool isVol,
4398 MachinePointerInfo DstPtrInfo) {
4399 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4401 // Check to see if we should lower the memset to stores first.
4402 // For cases within the target-specified limits, this is the best choice.
4403 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4405 // Memset with size zero? Just return the original chain.
4406 if (ConstantSize->isNullValue())
4410 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4411 Align, isVol, DstPtrInfo);
4413 if (Result.getNode())
4417 // Then check to see if we should lower the memset with target-specific
4418 // code. If the target chooses to do this, this is the next best.
4420 SDValue Result = TSI->EmitTargetCodeForMemset(
4421 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4422 if (Result.getNode())
4426 // Emit a library call.
4427 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4428 TargetLowering::ArgListTy Args;
4429 TargetLowering::ArgListEntry Entry;
4430 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4431 Args.push_back(Entry);
4433 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4434 Args.push_back(Entry);
4436 Entry.Ty = IntPtrTy;
4437 Args.push_back(Entry);
4439 // FIXME: pass in SDLoc
4440 TargetLowering::CallLoweringInfo CLI(*this);
4441 CLI.setDebugLoc(dl).setChain(Chain)
4442 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4443 Type::getVoidTy(*getContext()),
4444 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4445 TLI->getPointerTy()), std::move(Args), 0)
4446 .setDiscardResult();
4448 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4449 return CallResult.second;
4452 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4453 SDVTList VTList, ArrayRef<SDValue> Ops,
4454 MachineMemOperand *MMO,
4455 AtomicOrdering SuccessOrdering,
4456 AtomicOrdering FailureOrdering,
4457 SynchronizationScope SynchScope) {
4458 FoldingSetNodeID ID;
4459 ID.AddInteger(MemVT.getRawBits());
4460 AddNodeIDNode(ID, Opcode, VTList, Ops);
4461 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4463 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4464 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4465 return SDValue(E, 0);
4468 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4469 // SDNode doesn't have access to it. This memory will be "leaked" when
4470 // the node is deallocated, but recovered when the allocator is released.
4471 // If the number of operands is less than 5 we use AtomicSDNode's internal
4473 unsigned NumOps = Ops.size();
4474 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4477 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4478 dl.getDebugLoc(), VTList, MemVT,
4479 Ops.data(), DynOps, NumOps, MMO,
4480 SuccessOrdering, FailureOrdering,
4482 CSEMap.InsertNode(N, IP);
4484 return SDValue(N, 0);
4487 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4488 SDVTList VTList, ArrayRef<SDValue> Ops,
4489 MachineMemOperand *MMO,
4490 AtomicOrdering Ordering,
4491 SynchronizationScope SynchScope) {
4492 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4493 Ordering, SynchScope);
4496 SDValue SelectionDAG::getAtomicCmpSwap(
4497 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4498 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4499 unsigned Alignment, AtomicOrdering SuccessOrdering,
4500 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4501 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4502 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4503 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4505 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4506 Alignment = getEVTAlignment(MemVT);
4508 MachineFunction &MF = getMachineFunction();
4510 // FIXME: Volatile isn't really correct; we should keep track of atomic
4511 // orderings in the memoperand.
4512 unsigned Flags = MachineMemOperand::MOVolatile;
4513 Flags |= MachineMemOperand::MOLoad;
4514 Flags |= MachineMemOperand::MOStore;
4516 MachineMemOperand *MMO =
4517 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4519 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4520 SuccessOrdering, FailureOrdering, SynchScope);
4523 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4524 SDVTList VTs, SDValue Chain, SDValue Ptr,
4525 SDValue Cmp, SDValue Swp,
4526 MachineMemOperand *MMO,
4527 AtomicOrdering SuccessOrdering,
4528 AtomicOrdering FailureOrdering,
4529 SynchronizationScope SynchScope) {
4530 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4531 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4532 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4534 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4535 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4536 SuccessOrdering, FailureOrdering, SynchScope);
4539 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4541 SDValue Ptr, SDValue Val,
4542 const Value* PtrVal,
4544 AtomicOrdering Ordering,
4545 SynchronizationScope SynchScope) {
4546 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4547 Alignment = getEVTAlignment(MemVT);
4549 MachineFunction &MF = getMachineFunction();
4550 // An atomic store does not load. An atomic load does not store.
4551 // (An atomicrmw obviously both loads and stores.)
4552 // For now, atomics are considered to be volatile always, and they are
4554 // FIXME: Volatile isn't really correct; we should keep track of atomic
4555 // orderings in the memoperand.
4556 unsigned Flags = MachineMemOperand::MOVolatile;
4557 if (Opcode != ISD::ATOMIC_STORE)
4558 Flags |= MachineMemOperand::MOLoad;
4559 if (Opcode != ISD::ATOMIC_LOAD)
4560 Flags |= MachineMemOperand::MOStore;
4562 MachineMemOperand *MMO =
4563 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4564 MemVT.getStoreSize(), Alignment);
4566 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4567 Ordering, SynchScope);
4570 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4572 SDValue Ptr, SDValue Val,
4573 MachineMemOperand *MMO,
4574 AtomicOrdering Ordering,
4575 SynchronizationScope SynchScope) {
4576 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4577 Opcode == ISD::ATOMIC_LOAD_SUB ||
4578 Opcode == ISD::ATOMIC_LOAD_AND ||
4579 Opcode == ISD::ATOMIC_LOAD_OR ||
4580 Opcode == ISD::ATOMIC_LOAD_XOR ||
4581 Opcode == ISD::ATOMIC_LOAD_NAND ||
4582 Opcode == ISD::ATOMIC_LOAD_MIN ||
4583 Opcode == ISD::ATOMIC_LOAD_MAX ||
4584 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4585 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4586 Opcode == ISD::ATOMIC_SWAP ||
4587 Opcode == ISD::ATOMIC_STORE) &&
4588 "Invalid Atomic Op");
4590 EVT VT = Val.getValueType();
4592 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4593 getVTList(VT, MVT::Other);
4594 SDValue Ops[] = {Chain, Ptr, Val};
4595 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4598 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4599 EVT VT, SDValue Chain,
4601 MachineMemOperand *MMO,
4602 AtomicOrdering Ordering,
4603 SynchronizationScope SynchScope) {
4604 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4606 SDVTList VTs = getVTList(VT, MVT::Other);
4607 SDValue Ops[] = {Chain, Ptr};
4608 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4611 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4612 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4613 if (Ops.size() == 1)
4616 SmallVector<EVT, 4> VTs;
4617 VTs.reserve(Ops.size());
4618 for (unsigned i = 0; i < Ops.size(); ++i)
4619 VTs.push_back(Ops[i].getValueType());
4620 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4624 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4625 ArrayRef<SDValue> Ops,
4626 EVT MemVT, MachinePointerInfo PtrInfo,
4627 unsigned Align, bool Vol,
4628 bool ReadMem, bool WriteMem, unsigned Size) {
4629 if (Align == 0) // Ensure that codegen never sees alignment 0
4630 Align = getEVTAlignment(MemVT);
4632 MachineFunction &MF = getMachineFunction();
4635 Flags |= MachineMemOperand::MOStore;
4637 Flags |= MachineMemOperand::MOLoad;
4639 Flags |= MachineMemOperand::MOVolatile;
4641 Size = MemVT.getStoreSize();
4642 MachineMemOperand *MMO =
4643 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4645 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4649 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4650 ArrayRef<SDValue> Ops, EVT MemVT,
4651 MachineMemOperand *MMO) {
4652 assert((Opcode == ISD::INTRINSIC_VOID ||
4653 Opcode == ISD::INTRINSIC_W_CHAIN ||
4654 Opcode == ISD::PREFETCH ||
4655 Opcode == ISD::LIFETIME_START ||
4656 Opcode == ISD::LIFETIME_END ||
4657 (Opcode <= INT_MAX &&
4658 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4659 "Opcode is not a memory-accessing opcode!");
4661 // Memoize the node unless it returns a flag.
4662 MemIntrinsicSDNode *N;
4663 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4664 FoldingSetNodeID ID;
4665 AddNodeIDNode(ID, Opcode, VTList, Ops);
4666 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4668 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4669 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4670 return SDValue(E, 0);
4673 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4674 dl.getDebugLoc(), VTList, Ops,
4676 CSEMap.InsertNode(N, IP);
4678 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4679 dl.getDebugLoc(), VTList, Ops,
4683 return SDValue(N, 0);
4686 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4687 /// MachinePointerInfo record from it. This is particularly useful because the
4688 /// code generator has many cases where it doesn't bother passing in a
4689 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4690 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4691 // If this is FI+Offset, we can model it.
4692 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4693 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4695 // If this is (FI+Offset1)+Offset2, we can model it.
4696 if (Ptr.getOpcode() != ISD::ADD ||
4697 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4698 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4699 return MachinePointerInfo();
4701 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4702 return MachinePointerInfo::getFixedStack(FI, Offset+
4703 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4706 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4707 /// MachinePointerInfo record from it. This is particularly useful because the
4708 /// code generator has many cases where it doesn't bother passing in a
4709 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4710 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4711 // If the 'Offset' value isn't a constant, we can't handle this.
4712 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4713 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4714 if (OffsetOp.getOpcode() == ISD::UNDEF)
4715 return InferPointerInfo(Ptr);
4716 return MachinePointerInfo();
4721 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4722 EVT VT, SDLoc dl, SDValue Chain,
4723 SDValue Ptr, SDValue Offset,
4724 MachinePointerInfo PtrInfo, EVT MemVT,
4725 bool isVolatile, bool isNonTemporal, bool isInvariant,
4726 unsigned Alignment, const AAMDNodes &AAInfo,
4727 const MDNode *Ranges) {
4728 assert(Chain.getValueType() == MVT::Other &&
4729 "Invalid chain type");
4730 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4731 Alignment = getEVTAlignment(VT);
4733 unsigned Flags = MachineMemOperand::MOLoad;
4735 Flags |= MachineMemOperand::MOVolatile;
4737 Flags |= MachineMemOperand::MONonTemporal;
4739 Flags |= MachineMemOperand::MOInvariant;
4741 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4743 if (PtrInfo.V.isNull())
4744 PtrInfo = InferPointerInfo(Ptr, Offset);
4746 MachineFunction &MF = getMachineFunction();
4747 MachineMemOperand *MMO =
4748 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4750 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4754 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4755 EVT VT, SDLoc dl, SDValue Chain,
4756 SDValue Ptr, SDValue Offset, EVT MemVT,
4757 MachineMemOperand *MMO) {
4759 ExtType = ISD::NON_EXTLOAD;
4760 } else if (ExtType == ISD::NON_EXTLOAD) {
4761 assert(VT == MemVT && "Non-extending load from different memory type!");
4764 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4765 "Should only be an extending load, not truncating!");
4766 assert(VT.isInteger() == MemVT.isInteger() &&
4767 "Cannot convert from FP to Int or Int -> FP!");
4768 assert(VT.isVector() == MemVT.isVector() &&
4769 "Cannot use an ext load to convert to or from a vector!");
4770 assert((!VT.isVector() ||
4771 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4772 "Cannot use an ext load to change the number of vector elements!");
4775 bool Indexed = AM != ISD::UNINDEXED;
4776 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4777 "Unindexed load with an offset!");
4779 SDVTList VTs = Indexed ?
4780 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4781 SDValue Ops[] = { Chain, Ptr, Offset };
4782 FoldingSetNodeID ID;
4783 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4784 ID.AddInteger(MemVT.getRawBits());
4785 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4786 MMO->isNonTemporal(),
4787 MMO->isInvariant()));
4788 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4790 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4791 cast<LoadSDNode>(E)->refineAlignment(MMO);
4792 return SDValue(E, 0);
4794 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4795 dl.getDebugLoc(), VTs, AM, ExtType,
4797 CSEMap.InsertNode(N, IP);
4799 return SDValue(N, 0);
4802 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4803 SDValue Chain, SDValue Ptr,
4804 MachinePointerInfo PtrInfo,
4805 bool isVolatile, bool isNonTemporal,
4806 bool isInvariant, unsigned Alignment,
4807 const AAMDNodes &AAInfo,
4808 const MDNode *Ranges) {
4809 SDValue Undef = getUNDEF(Ptr.getValueType());
4810 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4811 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4815 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4816 SDValue Chain, SDValue Ptr,
4817 MachineMemOperand *MMO) {
4818 SDValue Undef = getUNDEF(Ptr.getValueType());
4819 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4823 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4824 SDValue Chain, SDValue Ptr,
4825 MachinePointerInfo PtrInfo, EVT MemVT,
4826 bool isVolatile, bool isNonTemporal,
4827 bool isInvariant, unsigned Alignment,
4828 const AAMDNodes &AAInfo) {
4829 SDValue Undef = getUNDEF(Ptr.getValueType());
4830 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4831 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4836 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4837 SDValue Chain, SDValue Ptr, EVT MemVT,
4838 MachineMemOperand *MMO) {
4839 SDValue Undef = getUNDEF(Ptr.getValueType());
4840 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4845 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4846 SDValue Offset, ISD::MemIndexedMode AM) {
4847 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4848 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4849 "Load is already a indexed load!");
4850 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4851 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4852 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4853 false, LD->getAlignment());
4856 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4857 SDValue Ptr, MachinePointerInfo PtrInfo,
4858 bool isVolatile, bool isNonTemporal,
4859 unsigned Alignment, const AAMDNodes &AAInfo) {
4860 assert(Chain.getValueType() == MVT::Other &&
4861 "Invalid chain type");
4862 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4863 Alignment = getEVTAlignment(Val.getValueType());
4865 unsigned Flags = MachineMemOperand::MOStore;
4867 Flags |= MachineMemOperand::MOVolatile;
4869 Flags |= MachineMemOperand::MONonTemporal;
4871 if (PtrInfo.V.isNull())
4872 PtrInfo = InferPointerInfo(Ptr);
4874 MachineFunction &MF = getMachineFunction();
4875 MachineMemOperand *MMO =
4876 MF.getMachineMemOperand(PtrInfo, Flags,
4877 Val.getValueType().getStoreSize(), Alignment,
4880 return getStore(Chain, dl, Val, Ptr, MMO);
4883 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4884 SDValue Ptr, MachineMemOperand *MMO) {
4885 assert(Chain.getValueType() == MVT::Other &&
4886 "Invalid chain type");
4887 EVT VT = Val.getValueType();
4888 SDVTList VTs = getVTList(MVT::Other);
4889 SDValue Undef = getUNDEF(Ptr.getValueType());
4890 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4891 FoldingSetNodeID ID;
4892 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4893 ID.AddInteger(VT.getRawBits());
4894 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4895 MMO->isNonTemporal(), MMO->isInvariant()));
4896 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4898 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4899 cast<StoreSDNode>(E)->refineAlignment(MMO);
4900 return SDValue(E, 0);
4902 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4903 dl.getDebugLoc(), VTs,
4904 ISD::UNINDEXED, false, VT, MMO);
4905 CSEMap.InsertNode(N, IP);
4907 return SDValue(N, 0);
4910 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4911 SDValue Ptr, MachinePointerInfo PtrInfo,
4912 EVT SVT,bool isVolatile, bool isNonTemporal,
4914 const AAMDNodes &AAInfo) {
4915 assert(Chain.getValueType() == MVT::Other &&
4916 "Invalid chain type");
4917 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4918 Alignment = getEVTAlignment(SVT);
4920 unsigned Flags = MachineMemOperand::MOStore;
4922 Flags |= MachineMemOperand::MOVolatile;
4924 Flags |= MachineMemOperand::MONonTemporal;
4926 if (PtrInfo.V.isNull())
4927 PtrInfo = InferPointerInfo(Ptr);
4929 MachineFunction &MF = getMachineFunction();
4930 MachineMemOperand *MMO =
4931 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4934 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4937 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4938 SDValue Ptr, EVT SVT,
4939 MachineMemOperand *MMO) {
4940 EVT VT = Val.getValueType();
4942 assert(Chain.getValueType() == MVT::Other &&
4943 "Invalid chain type");
4945 return getStore(Chain, dl, Val, Ptr, MMO);
4947 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4948 "Should only be a truncating store, not extending!");
4949 assert(VT.isInteger() == SVT.isInteger() &&
4950 "Can't do FP-INT conversion!");
4951 assert(VT.isVector() == SVT.isVector() &&
4952 "Cannot use trunc store to convert to or from a vector!");
4953 assert((!VT.isVector() ||
4954 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4955 "Cannot use trunc store to change the number of vector elements!");
4957 SDVTList VTs = getVTList(MVT::Other);
4958 SDValue Undef = getUNDEF(Ptr.getValueType());
4959 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4960 FoldingSetNodeID ID;
4961 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4962 ID.AddInteger(SVT.getRawBits());
4963 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4964 MMO->isNonTemporal(), MMO->isInvariant()));
4965 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4967 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4968 cast<StoreSDNode>(E)->refineAlignment(MMO);
4969 return SDValue(E, 0);
4971 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4972 dl.getDebugLoc(), VTs,
4973 ISD::UNINDEXED, true, SVT, MMO);
4974 CSEMap.InsertNode(N, IP);
4976 return SDValue(N, 0);
4980 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4981 SDValue Offset, ISD::MemIndexedMode AM) {
4982 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4983 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4984 "Store is already a indexed store!");
4985 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4986 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4987 FoldingSetNodeID ID;
4988 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4989 ID.AddInteger(ST->getMemoryVT().getRawBits());
4990 ID.AddInteger(ST->getRawSubclassData());
4991 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4993 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4994 return SDValue(E, 0);
4996 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4997 dl.getDebugLoc(), VTs, AM,
4998 ST->isTruncatingStore(),
5000 ST->getMemOperand());
5001 CSEMap.InsertNode(N, IP);
5003 return SDValue(N, 0);
5007 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5008 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5009 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5011 SDVTList VTs = getVTList(VT, MVT::Other);
5012 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5013 FoldingSetNodeID ID;
5014 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5015 ID.AddInteger(VT.getRawBits());
5016 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5018 MMO->isNonTemporal(),
5019 MMO->isInvariant()));
5020 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5022 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5023 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5024 return SDValue(E, 0);
5026 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5027 dl.getDebugLoc(), Ops, 4, VTs,
5029 CSEMap.InsertNode(N, IP);
5031 return SDValue(N, 0);
5034 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5035 SDValue Ptr, SDValue Mask, EVT MemVT,
5036 MachineMemOperand *MMO, bool isTrunc) {
5037 assert(Chain.getValueType() == MVT::Other &&
5038 "Invalid chain type");
5039 EVT VT = Val.getValueType();
5040 SDVTList VTs = getVTList(MVT::Other);
5041 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5042 FoldingSetNodeID ID;
5043 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5044 ID.AddInteger(VT.getRawBits());
5045 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5046 MMO->isNonTemporal(), MMO->isInvariant()));
5047 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5049 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5050 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5051 return SDValue(E, 0);
5053 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5054 dl.getDebugLoc(), Ops, 4,
5055 VTs, isTrunc, MemVT, MMO);
5056 CSEMap.InsertNode(N, IP);
5058 return SDValue(N, 0);
5061 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5062 SDValue Chain, SDValue Ptr,
5065 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5066 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5069 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5070 ArrayRef<SDUse> Ops) {
5071 switch (Ops.size()) {
5072 case 0: return getNode(Opcode, DL, VT);
5073 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5074 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5075 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5079 // Copy from an SDUse array into an SDValue array for use with
5080 // the regular getNode logic.
5081 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5082 return getNode(Opcode, DL, VT, NewOps);
5085 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5086 ArrayRef<SDValue> Ops) {
5087 unsigned NumOps = Ops.size();
5089 case 0: return getNode(Opcode, DL, VT);
5090 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5091 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5092 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5098 case ISD::SELECT_CC: {
5099 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5100 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5101 "LHS and RHS of condition must have same type!");
5102 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5103 "True and False arms of SelectCC must have same type!");
5104 assert(Ops[2].getValueType() == VT &&
5105 "select_cc node must be of same type as true and false value!");
5109 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5110 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5111 "LHS/RHS of comparison should match types!");
5118 SDVTList VTs = getVTList(VT);
5120 if (VT != MVT::Glue) {
5121 FoldingSetNodeID ID;
5122 AddNodeIDNode(ID, Opcode, VTs, Ops);
5125 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5126 return SDValue(E, 0);
5128 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5130 CSEMap.InsertNode(N, IP);
5132 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5137 return SDValue(N, 0);
5140 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5141 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5142 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5145 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5146 ArrayRef<SDValue> Ops) {
5147 if (VTList.NumVTs == 1)
5148 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5152 // FIXME: figure out how to safely handle things like
5153 // int foo(int x) { return 1 << (x & 255); }
5154 // int bar() { return foo(256); }
5155 case ISD::SRA_PARTS:
5156 case ISD::SRL_PARTS:
5157 case ISD::SHL_PARTS:
5158 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5159 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5160 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5161 else if (N3.getOpcode() == ISD::AND)
5162 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5163 // If the and is only masking out bits that cannot effect the shift,
5164 // eliminate the and.
5165 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5166 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5167 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5173 // Memoize the node unless it returns a flag.
5175 unsigned NumOps = Ops.size();
5176 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5177 FoldingSetNodeID ID;
5178 AddNodeIDNode(ID, Opcode, VTList, Ops);
5180 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5181 return SDValue(E, 0);
5184 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5185 DL.getDebugLoc(), VTList, Ops[0]);
5186 } else if (NumOps == 2) {
5187 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5188 DL.getDebugLoc(), VTList, Ops[0],
5190 } else if (NumOps == 3) {
5191 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5192 DL.getDebugLoc(), VTList, Ops[0],
5195 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5198 CSEMap.InsertNode(N, IP);
5201 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5202 DL.getDebugLoc(), VTList, Ops[0]);
5203 } else if (NumOps == 2) {
5204 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5205 DL.getDebugLoc(), VTList, Ops[0],
5207 } else if (NumOps == 3) {
5208 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5209 DL.getDebugLoc(), VTList, Ops[0],
5212 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5217 return SDValue(N, 0);
5220 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5221 return getNode(Opcode, DL, VTList, None);
5224 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5226 SDValue Ops[] = { N1 };
5227 return getNode(Opcode, DL, VTList, Ops);
5230 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5231 SDValue N1, SDValue N2) {
5232 SDValue Ops[] = { N1, N2 };
5233 return getNode(Opcode, DL, VTList, Ops);
5236 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5237 SDValue N1, SDValue N2, SDValue N3) {
5238 SDValue Ops[] = { N1, N2, N3 };
5239 return getNode(Opcode, DL, VTList, Ops);
5242 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5243 SDValue N1, SDValue N2, SDValue N3,
5245 SDValue Ops[] = { N1, N2, N3, N4 };
5246 return getNode(Opcode, DL, VTList, Ops);
5249 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5250 SDValue N1, SDValue N2, SDValue N3,
5251 SDValue N4, SDValue N5) {
5252 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5253 return getNode(Opcode, DL, VTList, Ops);
5256 SDVTList SelectionDAG::getVTList(EVT VT) {
5257 return makeVTList(SDNode::getValueTypeList(VT), 1);
5260 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5261 FoldingSetNodeID ID;
5263 ID.AddInteger(VT1.getRawBits());
5264 ID.AddInteger(VT2.getRawBits());
5267 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5269 EVT *Array = Allocator.Allocate<EVT>(2);
5272 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5273 VTListMap.InsertNode(Result, IP);
5275 return Result->getSDVTList();
5278 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5279 FoldingSetNodeID ID;
5281 ID.AddInteger(VT1.getRawBits());
5282 ID.AddInteger(VT2.getRawBits());
5283 ID.AddInteger(VT3.getRawBits());
5286 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5288 EVT *Array = Allocator.Allocate<EVT>(3);
5292 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5293 VTListMap.InsertNode(Result, IP);
5295 return Result->getSDVTList();
5298 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5299 FoldingSetNodeID ID;
5301 ID.AddInteger(VT1.getRawBits());
5302 ID.AddInteger(VT2.getRawBits());
5303 ID.AddInteger(VT3.getRawBits());
5304 ID.AddInteger(VT4.getRawBits());
5307 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5309 EVT *Array = Allocator.Allocate<EVT>(4);
5314 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5315 VTListMap.InsertNode(Result, IP);
5317 return Result->getSDVTList();
5320 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5321 unsigned NumVTs = VTs.size();
5322 FoldingSetNodeID ID;
5323 ID.AddInteger(NumVTs);
5324 for (unsigned index = 0; index < NumVTs; index++) {
5325 ID.AddInteger(VTs[index].getRawBits());
5329 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5331 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5332 std::copy(VTs.begin(), VTs.end(), Array);
5333 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5334 VTListMap.InsertNode(Result, IP);
5336 return Result->getSDVTList();
5340 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5341 /// specified operands. If the resultant node already exists in the DAG,
5342 /// this does not modify the specified node, instead it returns the node that
5343 /// already exists. If the resultant node does not exist in the DAG, the
5344 /// input node is returned. As a degenerate case, if you specify the same
5345 /// input operands as the node already has, the input node is returned.
5346 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5347 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5349 // Check to see if there is no change.
5350 if (Op == N->getOperand(0)) return N;
5352 // See if the modified node already exists.
5353 void *InsertPos = nullptr;
5354 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5357 // Nope it doesn't. Remove the node from its current place in the maps.
5359 if (!RemoveNodeFromCSEMaps(N))
5360 InsertPos = nullptr;
5362 // Now we update the operands.
5363 N->OperandList[0].set(Op);
5365 // If this gets put into a CSE map, add it.
5366 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5370 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5371 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5373 // Check to see if there is no change.
5374 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5375 return N; // No operands changed, just return the input node.
5377 // See if the modified node already exists.
5378 void *InsertPos = nullptr;
5379 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5382 // Nope it doesn't. Remove the node from its current place in the maps.
5384 if (!RemoveNodeFromCSEMaps(N))
5385 InsertPos = nullptr;
5387 // Now we update the operands.
5388 if (N->OperandList[0] != Op1)
5389 N->OperandList[0].set(Op1);
5390 if (N->OperandList[1] != Op2)
5391 N->OperandList[1].set(Op2);
5393 // If this gets put into a CSE map, add it.
5394 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5398 SDNode *SelectionDAG::
5399 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5400 SDValue Ops[] = { Op1, Op2, Op3 };
5401 return UpdateNodeOperands(N, Ops);
5404 SDNode *SelectionDAG::
5405 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5406 SDValue Op3, SDValue Op4) {
5407 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5408 return UpdateNodeOperands(N, Ops);
5411 SDNode *SelectionDAG::
5412 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5413 SDValue Op3, SDValue Op4, SDValue Op5) {
5414 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5415 return UpdateNodeOperands(N, Ops);
5418 SDNode *SelectionDAG::
5419 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5420 unsigned NumOps = Ops.size();
5421 assert(N->getNumOperands() == NumOps &&
5422 "Update with wrong number of operands");
5424 // Check to see if there is no change.
5425 bool AnyChange = false;
5426 for (unsigned i = 0; i != NumOps; ++i) {
5427 if (Ops[i] != N->getOperand(i)) {
5433 // No operands changed, just return the input node.
5434 if (!AnyChange) return N;
5436 // See if the modified node already exists.
5437 void *InsertPos = nullptr;
5438 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5441 // Nope it doesn't. Remove the node from its current place in the maps.
5443 if (!RemoveNodeFromCSEMaps(N))
5444 InsertPos = nullptr;
5446 // Now we update the operands.
5447 for (unsigned i = 0; i != NumOps; ++i)
5448 if (N->OperandList[i] != Ops[i])
5449 N->OperandList[i].set(Ops[i]);
5451 // If this gets put into a CSE map, add it.
5452 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5456 /// DropOperands - Release the operands and set this node to have
5458 void SDNode::DropOperands() {
5459 // Unlike the code in MorphNodeTo that does this, we don't need to
5460 // watch for dead nodes here.
5461 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5467 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5470 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5472 SDVTList VTs = getVTList(VT);
5473 return SelectNodeTo(N, MachineOpc, VTs, None);
5476 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5477 EVT VT, SDValue Op1) {
5478 SDVTList VTs = getVTList(VT);
5479 SDValue Ops[] = { Op1 };
5480 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5483 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5484 EVT VT, SDValue Op1,
5486 SDVTList VTs = getVTList(VT);
5487 SDValue Ops[] = { Op1, Op2 };
5488 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5491 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5492 EVT VT, SDValue Op1,
5493 SDValue Op2, SDValue Op3) {
5494 SDVTList VTs = getVTList(VT);
5495 SDValue Ops[] = { Op1, Op2, Op3 };
5496 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5499 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5500 EVT VT, ArrayRef<SDValue> Ops) {
5501 SDVTList VTs = getVTList(VT);
5502 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5505 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5506 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5507 SDVTList VTs = getVTList(VT1, VT2);
5508 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5511 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5513 SDVTList VTs = getVTList(VT1, VT2);
5514 return SelectNodeTo(N, MachineOpc, VTs, None);
5517 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5518 EVT VT1, EVT VT2, EVT VT3,
5519 ArrayRef<SDValue> Ops) {
5520 SDVTList VTs = getVTList(VT1, VT2, VT3);
5521 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5524 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5525 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5526 ArrayRef<SDValue> Ops) {
5527 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5528 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5531 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5534 SDVTList VTs = getVTList(VT1, VT2);
5535 SDValue Ops[] = { Op1 };
5536 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5539 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5541 SDValue Op1, SDValue Op2) {
5542 SDVTList VTs = getVTList(VT1, VT2);
5543 SDValue Ops[] = { Op1, Op2 };
5544 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5547 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5549 SDValue Op1, SDValue Op2,
5551 SDVTList VTs = getVTList(VT1, VT2);
5552 SDValue Ops[] = { Op1, Op2, Op3 };
5553 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5556 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5557 EVT VT1, EVT VT2, EVT VT3,
5558 SDValue Op1, SDValue Op2,
5560 SDVTList VTs = getVTList(VT1, VT2, VT3);
5561 SDValue Ops[] = { Op1, Op2, Op3 };
5562 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5565 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5566 SDVTList VTs,ArrayRef<SDValue> Ops) {
5567 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5568 // Reset the NodeID to -1.
5573 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5574 /// the line number information on the merged node since it is not possible to
5575 /// preserve the information that operation is associated with multiple lines.
5576 /// This will make the debugger working better at -O0, were there is a higher
5577 /// probability having other instructions associated with that line.
5579 /// For IROrder, we keep the smaller of the two
5580 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5581 DebugLoc NLoc = N->getDebugLoc();
5582 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5583 (OLoc.getDebugLoc() != NLoc)) {
5584 N->setDebugLoc(DebugLoc());
5586 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5587 N->setIROrder(Order);
5591 /// MorphNodeTo - This *mutates* the specified node to have the specified
5592 /// return type, opcode, and operands.
5594 /// Note that MorphNodeTo returns the resultant node. If there is already a
5595 /// node of the specified opcode and operands, it returns that node instead of
5596 /// the current one. Note that the SDLoc need not be the same.
5598 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5599 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5600 /// node, and because it doesn't require CSE recalculation for any of
5601 /// the node's users.
5603 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5604 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5605 /// the legalizer which maintain worklists that would need to be updated when
5606 /// deleting things.
5607 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5608 SDVTList VTs, ArrayRef<SDValue> Ops) {
5609 unsigned NumOps = Ops.size();
5610 // If an identical node already exists, use it.
5612 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5613 FoldingSetNodeID ID;
5614 AddNodeIDNode(ID, Opc, VTs, Ops);
5615 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5616 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5619 if (!RemoveNodeFromCSEMaps(N))
5622 // Start the morphing.
5624 N->ValueList = VTs.VTs;
5625 N->NumValues = VTs.NumVTs;
5627 // Clear the operands list, updating used nodes to remove this from their
5628 // use list. Keep track of any operands that become dead as a result.
5629 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5630 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5632 SDNode *Used = Use.getNode();
5634 if (Used->use_empty())
5635 DeadNodeSet.insert(Used);
5638 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5639 // Initialize the memory references information.
5640 MN->setMemRefs(nullptr, nullptr);
5641 // If NumOps is larger than the # of operands we can have in a
5642 // MachineSDNode, reallocate the operand list.
5643 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5644 if (MN->OperandsNeedDelete)
5645 delete[] MN->OperandList;
5646 if (NumOps > array_lengthof(MN->LocalOperands))
5647 // We're creating a final node that will live unmorphed for the
5648 // remainder of the current SelectionDAG iteration, so we can allocate
5649 // the operands directly out of a pool with no recycling metadata.
5650 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5651 Ops.data(), NumOps);
5653 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5654 MN->OperandsNeedDelete = false;
5656 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5658 // If NumOps is larger than the # of operands we currently have, reallocate
5659 // the operand list.
5660 if (NumOps > N->NumOperands) {
5661 if (N->OperandsNeedDelete)
5662 delete[] N->OperandList;
5663 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5664 N->OperandsNeedDelete = true;
5666 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5669 // Delete any nodes that are still dead after adding the uses for the
5671 if (!DeadNodeSet.empty()) {
5672 SmallVector<SDNode *, 16> DeadNodes;
5673 for (SDNode *N : DeadNodeSet)
5675 DeadNodes.push_back(N);
5676 RemoveDeadNodes(DeadNodes);
5680 CSEMap.InsertNode(N, IP); // Memoize the new node.
5685 /// getMachineNode - These are used for target selectors to create a new node
5686 /// with specified return type(s), MachineInstr opcode, and operands.
5688 /// Note that getMachineNode returns the resultant node. If there is already a
5689 /// node of the specified opcode and operands, it returns that node instead of
5690 /// the current one.
5692 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5693 SDVTList VTs = getVTList(VT);
5694 return getMachineNode(Opcode, dl, VTs, None);
5698 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5699 SDVTList VTs = getVTList(VT);
5700 SDValue Ops[] = { Op1 };
5701 return getMachineNode(Opcode, dl, VTs, Ops);
5705 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5706 SDValue Op1, SDValue Op2) {
5707 SDVTList VTs = getVTList(VT);
5708 SDValue Ops[] = { Op1, Op2 };
5709 return getMachineNode(Opcode, dl, VTs, Ops);
5713 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5714 SDValue Op1, SDValue Op2, SDValue Op3) {
5715 SDVTList VTs = getVTList(VT);
5716 SDValue Ops[] = { Op1, Op2, Op3 };
5717 return getMachineNode(Opcode, dl, VTs, Ops);
5721 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5722 ArrayRef<SDValue> Ops) {
5723 SDVTList VTs = getVTList(VT);
5724 return getMachineNode(Opcode, dl, VTs, Ops);
5728 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5729 SDVTList VTs = getVTList(VT1, VT2);
5730 return getMachineNode(Opcode, dl, VTs, None);
5734 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5735 EVT VT1, EVT VT2, SDValue Op1) {
5736 SDVTList VTs = getVTList(VT1, VT2);
5737 SDValue Ops[] = { Op1 };
5738 return getMachineNode(Opcode, dl, VTs, Ops);
5742 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5743 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5744 SDVTList VTs = getVTList(VT1, VT2);
5745 SDValue Ops[] = { Op1, Op2 };
5746 return getMachineNode(Opcode, dl, VTs, Ops);
5750 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5751 EVT VT1, EVT VT2, SDValue Op1,
5752 SDValue Op2, SDValue Op3) {
5753 SDVTList VTs = getVTList(VT1, VT2);
5754 SDValue Ops[] = { Op1, Op2, Op3 };
5755 return getMachineNode(Opcode, dl, VTs, Ops);
5759 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5761 ArrayRef<SDValue> Ops) {
5762 SDVTList VTs = getVTList(VT1, VT2);
5763 return getMachineNode(Opcode, dl, VTs, Ops);
5767 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5768 EVT VT1, EVT VT2, EVT VT3,
5769 SDValue Op1, SDValue Op2) {
5770 SDVTList VTs = getVTList(VT1, VT2, VT3);
5771 SDValue Ops[] = { Op1, Op2 };
5772 return getMachineNode(Opcode, dl, VTs, Ops);
5776 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5777 EVT VT1, EVT VT2, EVT VT3,
5778 SDValue Op1, SDValue Op2, SDValue Op3) {
5779 SDVTList VTs = getVTList(VT1, VT2, VT3);
5780 SDValue Ops[] = { Op1, Op2, Op3 };
5781 return getMachineNode(Opcode, dl, VTs, Ops);
5785 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5786 EVT VT1, EVT VT2, EVT VT3,
5787 ArrayRef<SDValue> Ops) {
5788 SDVTList VTs = getVTList(VT1, VT2, VT3);
5789 return getMachineNode(Opcode, dl, VTs, Ops);
5793 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5794 EVT VT2, EVT VT3, EVT VT4,
5795 ArrayRef<SDValue> Ops) {
5796 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5797 return getMachineNode(Opcode, dl, VTs, Ops);
5801 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5802 ArrayRef<EVT> ResultTys,
5803 ArrayRef<SDValue> Ops) {
5804 SDVTList VTs = getVTList(ResultTys);
5805 return getMachineNode(Opcode, dl, VTs, Ops);
5809 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5810 ArrayRef<SDValue> OpsArray) {
5811 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5814 const SDValue *Ops = OpsArray.data();
5815 unsigned NumOps = OpsArray.size();
5818 FoldingSetNodeID ID;
5819 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5821 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5822 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5826 // Allocate a new MachineSDNode.
5827 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5828 DL.getDebugLoc(), VTs);
5830 // Initialize the operands list.
5831 if (NumOps > array_lengthof(N->LocalOperands))
5832 // We're creating a final node that will live unmorphed for the
5833 // remainder of the current SelectionDAG iteration, so we can allocate
5834 // the operands directly out of a pool with no recycling metadata.
5835 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5838 N->InitOperands(N->LocalOperands, Ops, NumOps);
5839 N->OperandsNeedDelete = false;
5842 CSEMap.InsertNode(N, IP);
5848 /// getTargetExtractSubreg - A convenience function for creating
5849 /// TargetOpcode::EXTRACT_SUBREG nodes.
5851 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5853 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5854 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5855 VT, Operand, SRIdxVal);
5856 return SDValue(Subreg, 0);
5859 /// getTargetInsertSubreg - A convenience function for creating
5860 /// TargetOpcode::INSERT_SUBREG nodes.
5862 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5863 SDValue Operand, SDValue Subreg) {
5864 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5865 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5866 VT, Operand, Subreg, SRIdxVal);
5867 return SDValue(Result, 0);
5870 /// getNodeIfExists - Get the specified node if it's already available, or
5871 /// else return NULL.
5872 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5873 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5875 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5876 FoldingSetNodeID ID;
5877 AddNodeIDNode(ID, Opcode, VTList, Ops);
5878 if (isBinOpWithFlags(Opcode))
5879 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5881 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5887 /// getDbgValue - Creates a SDDbgValue node.
5890 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5891 unsigned R, bool IsIndirect, uint64_t Off,
5892 DebugLoc DL, unsigned O) {
5893 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5897 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5898 const Value *C, uint64_t Off,
5899 DebugLoc DL, unsigned O) {
5900 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5904 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5905 unsigned FI, uint64_t Off,
5906 DebugLoc DL, unsigned O) {
5907 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5912 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5913 /// pointed to by a use iterator is deleted, increment the use iterator
5914 /// so that it doesn't dangle.
5916 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5917 SDNode::use_iterator &UI;
5918 SDNode::use_iterator &UE;
5920 void NodeDeleted(SDNode *N, SDNode *E) override {
5921 // Increment the iterator as needed.
5922 while (UI != UE && N == *UI)
5927 RAUWUpdateListener(SelectionDAG &d,
5928 SDNode::use_iterator &ui,
5929 SDNode::use_iterator &ue)
5930 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5935 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5936 /// This can cause recursive merging of nodes in the DAG.
5938 /// This version assumes From has a single result value.
5940 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5941 SDNode *From = FromN.getNode();
5942 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5943 "Cannot replace with this method!");
5944 assert(From != To.getNode() && "Cannot replace uses of with self");
5946 // Iterate over all the existing uses of From. New uses will be added
5947 // to the beginning of the use list, which we avoid visiting.
5948 // This specifically avoids visiting uses of From that arise while the
5949 // replacement is happening, because any such uses would be the result
5950 // of CSE: If an existing node looks like From after one of its operands
5951 // is replaced by To, we don't want to replace of all its users with To
5952 // too. See PR3018 for more info.
5953 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5954 RAUWUpdateListener Listener(*this, UI, UE);
5958 // This node is about to morph, remove its old self from the CSE maps.
5959 RemoveNodeFromCSEMaps(User);
5961 // A user can appear in a use list multiple times, and when this
5962 // happens the uses are usually next to each other in the list.
5963 // To help reduce the number of CSE recomputations, process all
5964 // the uses of this user that we can find this way.
5966 SDUse &Use = UI.getUse();
5969 } while (UI != UE && *UI == User);
5971 // Now that we have modified User, add it back to the CSE maps. If it
5972 // already exists there, recursively merge the results together.
5973 AddModifiedNodeToCSEMaps(User);
5976 // If we just RAUW'd the root, take note.
5977 if (FromN == getRoot())
5981 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5982 /// This can cause recursive merging of nodes in the DAG.
5984 /// This version assumes that for each value of From, there is a
5985 /// corresponding value in To in the same position with the same type.
5987 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5989 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5990 assert((!From->hasAnyUseOfValue(i) ||
5991 From->getValueType(i) == To->getValueType(i)) &&
5992 "Cannot use this version of ReplaceAllUsesWith!");
5995 // Handle the trivial case.
5999 // Iterate over just the existing users of From. See the comments in
6000 // the ReplaceAllUsesWith above.
6001 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6002 RAUWUpdateListener Listener(*this, UI, UE);
6006 // This node is about to morph, remove its old self from the CSE maps.
6007 RemoveNodeFromCSEMaps(User);
6009 // A user can appear in a use list multiple times, and when this
6010 // happens the uses are usually next to each other in the list.
6011 // To help reduce the number of CSE recomputations, process all
6012 // the uses of this user that we can find this way.
6014 SDUse &Use = UI.getUse();
6017 } while (UI != UE && *UI == User);
6019 // Now that we have modified User, add it back to the CSE maps. If it
6020 // already exists there, recursively merge the results together.
6021 AddModifiedNodeToCSEMaps(User);
6024 // If we just RAUW'd the root, take note.
6025 if (From == getRoot().getNode())
6026 setRoot(SDValue(To, getRoot().getResNo()));
6029 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6030 /// This can cause recursive merging of nodes in the DAG.
6032 /// This version can replace From with any result values. To must match the
6033 /// number and types of values returned by From.
6034 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6035 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6036 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6038 // Iterate over just the existing users of From. See the comments in
6039 // the ReplaceAllUsesWith above.
6040 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6041 RAUWUpdateListener Listener(*this, UI, UE);
6045 // This node is about to morph, remove its old self from the CSE maps.
6046 RemoveNodeFromCSEMaps(User);
6048 // A user can appear in a use list multiple times, and when this
6049 // happens the uses are usually next to each other in the list.
6050 // To help reduce the number of CSE recomputations, process all
6051 // the uses of this user that we can find this way.
6053 SDUse &Use = UI.getUse();
6054 const SDValue &ToOp = To[Use.getResNo()];
6057 } while (UI != UE && *UI == User);
6059 // Now that we have modified User, add it back to the CSE maps. If it
6060 // already exists there, recursively merge the results together.
6061 AddModifiedNodeToCSEMaps(User);
6064 // If we just RAUW'd the root, take note.
6065 if (From == getRoot().getNode())
6066 setRoot(SDValue(To[getRoot().getResNo()]));
6069 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6070 /// uses of other values produced by From.getNode() alone. The Deleted
6071 /// vector is handled the same way as for ReplaceAllUsesWith.
6072 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6073 // Handle the really simple, really trivial case efficiently.
6074 if (From == To) return;
6076 // Handle the simple, trivial, case efficiently.
6077 if (From.getNode()->getNumValues() == 1) {
6078 ReplaceAllUsesWith(From, To);
6082 // Iterate over just the existing users of From. See the comments in
6083 // the ReplaceAllUsesWith above.
6084 SDNode::use_iterator UI = From.getNode()->use_begin(),
6085 UE = From.getNode()->use_end();
6086 RAUWUpdateListener Listener(*this, UI, UE);
6089 bool UserRemovedFromCSEMaps = false;
6091 // A user can appear in a use list multiple times, and when this
6092 // happens the uses are usually next to each other in the list.
6093 // To help reduce the number of CSE recomputations, process all
6094 // the uses of this user that we can find this way.
6096 SDUse &Use = UI.getUse();
6098 // Skip uses of different values from the same node.
6099 if (Use.getResNo() != From.getResNo()) {
6104 // If this node hasn't been modified yet, it's still in the CSE maps,
6105 // so remove its old self from the CSE maps.
6106 if (!UserRemovedFromCSEMaps) {
6107 RemoveNodeFromCSEMaps(User);
6108 UserRemovedFromCSEMaps = true;
6113 } while (UI != UE && *UI == User);
6115 // We are iterating over all uses of the From node, so if a use
6116 // doesn't use the specific value, no changes are made.
6117 if (!UserRemovedFromCSEMaps)
6120 // Now that we have modified User, add it back to the CSE maps. If it
6121 // already exists there, recursively merge the results together.
6122 AddModifiedNodeToCSEMaps(User);
6125 // If we just RAUW'd the root, take note.
6126 if (From == getRoot())
6131 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6132 /// to record information about a use.
6139 /// operator< - Sort Memos by User.
6140 bool operator<(const UseMemo &L, const UseMemo &R) {
6141 return (intptr_t)L.User < (intptr_t)R.User;
6145 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6146 /// uses of other values produced by From.getNode() alone. The same value
6147 /// may appear in both the From and To list. The Deleted vector is
6148 /// handled the same way as for ReplaceAllUsesWith.
6149 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6152 // Handle the simple, trivial case efficiently.
6154 return ReplaceAllUsesOfValueWith(*From, *To);
6156 // Read up all the uses and make records of them. This helps
6157 // processing new uses that are introduced during the
6158 // replacement process.
6159 SmallVector<UseMemo, 4> Uses;
6160 for (unsigned i = 0; i != Num; ++i) {
6161 unsigned FromResNo = From[i].getResNo();
6162 SDNode *FromNode = From[i].getNode();
6163 for (SDNode::use_iterator UI = FromNode->use_begin(),
6164 E = FromNode->use_end(); UI != E; ++UI) {
6165 SDUse &Use = UI.getUse();
6166 if (Use.getResNo() == FromResNo) {
6167 UseMemo Memo = { *UI, i, &Use };
6168 Uses.push_back(Memo);
6173 // Sort the uses, so that all the uses from a given User are together.
6174 std::sort(Uses.begin(), Uses.end());
6176 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6177 UseIndex != UseIndexEnd; ) {
6178 // We know that this user uses some value of From. If it is the right
6179 // value, update it.
6180 SDNode *User = Uses[UseIndex].User;
6182 // This node is about to morph, remove its old self from the CSE maps.
6183 RemoveNodeFromCSEMaps(User);
6185 // The Uses array is sorted, so all the uses for a given User
6186 // are next to each other in the list.
6187 // To help reduce the number of CSE recomputations, process all
6188 // the uses of this user that we can find this way.
6190 unsigned i = Uses[UseIndex].Index;
6191 SDUse &Use = *Uses[UseIndex].Use;
6195 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6197 // Now that we have modified User, add it back to the CSE maps. If it
6198 // already exists there, recursively merge the results together.
6199 AddModifiedNodeToCSEMaps(User);
6203 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6204 /// based on their topological order. It returns the maximum id and a vector
6205 /// of the SDNodes* in assigned order by reference.
6206 unsigned SelectionDAG::AssignTopologicalOrder() {
6208 unsigned DAGSize = 0;
6210 // SortedPos tracks the progress of the algorithm. Nodes before it are
6211 // sorted, nodes after it are unsorted. When the algorithm completes
6212 // it is at the end of the list.
6213 allnodes_iterator SortedPos = allnodes_begin();
6215 // Visit all the nodes. Move nodes with no operands to the front of
6216 // the list immediately. Annotate nodes that do have operands with their
6217 // operand count. Before we do this, the Node Id fields of the nodes
6218 // may contain arbitrary values. After, the Node Id fields for nodes
6219 // before SortedPos will contain the topological sort index, and the
6220 // Node Id fields for nodes At SortedPos and after will contain the
6221 // count of outstanding operands.
6222 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6224 checkForCycles(N, this);
6225 unsigned Degree = N->getNumOperands();
6227 // A node with no uses, add it to the result array immediately.
6228 N->setNodeId(DAGSize++);
6229 allnodes_iterator Q = N;
6231 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6232 assert(SortedPos != AllNodes.end() && "Overran node list");
6235 // Temporarily use the Node Id as scratch space for the degree count.
6236 N->setNodeId(Degree);
6240 // Visit all the nodes. As we iterate, move nodes into sorted order,
6241 // such that by the time the end is reached all nodes will be sorted.
6242 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6244 checkForCycles(N, this);
6245 // N is in sorted position, so all its uses have one less operand
6246 // that needs to be sorted.
6247 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6250 unsigned Degree = P->getNodeId();
6251 assert(Degree != 0 && "Invalid node degree");
6254 // All of P's operands are sorted, so P may sorted now.
6255 P->setNodeId(DAGSize++);
6257 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6258 assert(SortedPos != AllNodes.end() && "Overran node list");
6261 // Update P's outstanding operand count.
6262 P->setNodeId(Degree);
6265 if (I == SortedPos) {
6268 dbgs() << "Overran sorted position:\n";
6269 S->dumprFull(this); dbgs() << "\n";
6270 dbgs() << "Checking if this is due to cycles\n";
6271 checkForCycles(this, true);
6273 llvm_unreachable(nullptr);
6277 assert(SortedPos == AllNodes.end() &&
6278 "Topological sort incomplete!");
6279 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6280 "First node in topological sort is not the entry token!");
6281 assert(AllNodes.front().getNodeId() == 0 &&
6282 "First node in topological sort has non-zero id!");
6283 assert(AllNodes.front().getNumOperands() == 0 &&
6284 "First node in topological sort has operands!");
6285 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6286 "Last node in topologic sort has unexpected id!");
6287 assert(AllNodes.back().use_empty() &&
6288 "Last node in topologic sort has users!");
6289 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6293 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6294 /// value is produced by SD.
6295 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6297 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6298 SD->setHasDebugValue(true);
6300 DbgInfo->add(DB, SD, isParameter);
6303 /// TransferDbgValues - Transfer SDDbgValues.
6304 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6305 if (From == To || !From.getNode()->getHasDebugValue())
6307 SDNode *FromNode = From.getNode();
6308 SDNode *ToNode = To.getNode();
6309 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6310 SmallVector<SDDbgValue *, 2> ClonedDVs;
6311 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6313 SDDbgValue *Dbg = *I;
6314 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6316 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6317 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6318 Dbg->getDebugLoc(), Dbg->getOrder());
6319 ClonedDVs.push_back(Clone);
6322 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6323 E = ClonedDVs.end(); I != E; ++I)
6324 AddDbgValue(*I, ToNode, false);
6327 //===----------------------------------------------------------------------===//
6329 //===----------------------------------------------------------------------===//
6331 HandleSDNode::~HandleSDNode() {
6335 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6336 DebugLoc DL, const GlobalValue *GA,
6337 EVT VT, int64_t o, unsigned char TF)
6338 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6342 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6343 SDValue X, unsigned SrcAS,
6345 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6346 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6348 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6349 EVT memvt, MachineMemOperand *mmo)
6350 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6351 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6352 MMO->isNonTemporal(), MMO->isInvariant());
6353 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6354 assert(isNonTemporal() == MMO->isNonTemporal() &&
6355 "Non-temporal encoding error!");
6356 // We check here that the size of the memory operand fits within the size of
6357 // the MMO. This is because the MMO might indicate only a possible address
6358 // range instead of specifying the affected memory addresses precisely.
6359 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6362 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6363 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6364 : SDNode(Opc, Order, dl, VTs, Ops),
6365 MemoryVT(memvt), MMO(mmo) {
6366 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6367 MMO->isNonTemporal(), MMO->isInvariant());
6368 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6369 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6372 /// Profile - Gather unique data for the node.
6374 void SDNode::Profile(FoldingSetNodeID &ID) const {
6375 AddNodeIDNode(ID, this);
6380 std::vector<EVT> VTs;
6383 VTs.reserve(MVT::LAST_VALUETYPE);
6384 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6385 VTs.push_back(MVT((MVT::SimpleValueType)i));
6390 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6391 static ManagedStatic<EVTArray> SimpleVTArray;
6392 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6394 /// getValueTypeList - Return a pointer to the specified value type.
6396 const EVT *SDNode::getValueTypeList(EVT VT) {
6397 if (VT.isExtended()) {
6398 sys::SmartScopedLock<true> Lock(*VTMutex);
6399 return &(*EVTs->insert(VT).first);
6401 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6402 "Value type out of range!");
6403 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6407 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6408 /// indicated value. This method ignores uses of other values defined by this
6410 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6411 assert(Value < getNumValues() && "Bad value!");
6413 // TODO: Only iterate over uses of a given value of the node
6414 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6415 if (UI.getUse().getResNo() == Value) {
6422 // Found exactly the right number of uses?
6427 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6428 /// value. This method ignores uses of other values defined by this operation.
6429 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6430 assert(Value < getNumValues() && "Bad value!");
6432 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6433 if (UI.getUse().getResNo() == Value)
6440 /// isOnlyUserOf - Return true if this node is the only use of N.
6442 bool SDNode::isOnlyUserOf(SDNode *N) const {
6444 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6455 /// isOperand - Return true if this node is an operand of N.
6457 bool SDValue::isOperandOf(SDNode *N) const {
6458 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6459 if (*this == N->getOperand(i))
6464 bool SDNode::isOperandOf(SDNode *N) const {
6465 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6466 if (this == N->OperandList[i].getNode())
6471 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6472 /// be a chain) reaches the specified operand without crossing any
6473 /// side-effecting instructions on any chain path. In practice, this looks
6474 /// through token factors and non-volatile loads. In order to remain efficient,
6475 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6476 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6477 unsigned Depth) const {
6478 if (*this == Dest) return true;
6480 // Don't search too deeply, we just want to be able to see through
6481 // TokenFactor's etc.
6482 if (Depth == 0) return false;
6484 // If this is a token factor, all inputs to the TF happen in parallel. If any
6485 // of the operands of the TF does not reach dest, then we cannot do the xform.
6486 if (getOpcode() == ISD::TokenFactor) {
6487 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6488 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6493 // Loads don't have side effects, look through them.
6494 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6495 if (!Ld->isVolatile())
6496 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6501 /// hasPredecessor - Return true if N is a predecessor of this node.
6502 /// N is either an operand of this node, or can be reached by recursively
6503 /// traversing up the operands.
6504 /// NOTE: This is an expensive method. Use it carefully.
6505 bool SDNode::hasPredecessor(const SDNode *N) const {
6506 SmallPtrSet<const SDNode *, 32> Visited;
6507 SmallVector<const SDNode *, 16> Worklist;
6508 return hasPredecessorHelper(N, Visited, Worklist);
6512 SDNode::hasPredecessorHelper(const SDNode *N,
6513 SmallPtrSetImpl<const SDNode *> &Visited,
6514 SmallVectorImpl<const SDNode *> &Worklist) const {
6515 if (Visited.empty()) {
6516 Worklist.push_back(this);
6518 // Take a look in the visited set. If we've already encountered this node
6519 // we needn't search further.
6520 if (Visited.count(N))
6524 // Haven't visited N yet. Continue the search.
6525 while (!Worklist.empty()) {
6526 const SDNode *M = Worklist.pop_back_val();
6527 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6528 SDNode *Op = M->getOperand(i).getNode();
6529 if (Visited.insert(Op).second)
6530 Worklist.push_back(Op);
6539 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6540 assert(Num < NumOperands && "Invalid child # of SDNode!");
6541 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6544 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6545 assert(N->getNumValues() == 1 &&
6546 "Can't unroll a vector with multiple results!");
6548 EVT VT = N->getValueType(0);
6549 unsigned NE = VT.getVectorNumElements();
6550 EVT EltVT = VT.getVectorElementType();
6553 SmallVector<SDValue, 8> Scalars;
6554 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6556 // If ResNE is 0, fully unroll the vector op.
6559 else if (NE > ResNE)
6563 for (i= 0; i != NE; ++i) {
6564 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6565 SDValue Operand = N->getOperand(j);
6566 EVT OperandVT = Operand.getValueType();
6567 if (OperandVT.isVector()) {
6568 // A vector operand; extract a single element.
6569 EVT OperandEltVT = OperandVT.getVectorElementType();
6570 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6573 getConstant(i, TLI->getVectorIdxTy()));
6575 // A scalar operand; just use it as is.
6576 Operands[j] = Operand;
6580 switch (N->getOpcode()) {
6582 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6585 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6592 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6593 getShiftAmountOperand(Operands[0].getValueType(),
6596 case ISD::SIGN_EXTEND_INREG:
6597 case ISD::FP_ROUND_INREG: {
6598 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6599 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6601 getValueType(ExtVT)));
6606 for (; i < ResNE; ++i)
6607 Scalars.push_back(getUNDEF(EltVT));
6609 return getNode(ISD::BUILD_VECTOR, dl,
6610 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6614 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6615 /// location that is 'Dist' units away from the location that the 'Base' load
6616 /// is loading from.
6617 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6618 unsigned Bytes, int Dist) const {
6619 if (LD->getChain() != Base->getChain())
6621 EVT VT = LD->getValueType(0);
6622 if (VT.getSizeInBits() / 8 != Bytes)
6625 SDValue Loc = LD->getOperand(1);
6626 SDValue BaseLoc = Base->getOperand(1);
6627 if (Loc.getOpcode() == ISD::FrameIndex) {
6628 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6630 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6631 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6632 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6633 int FS = MFI->getObjectSize(FI);
6634 int BFS = MFI->getObjectSize(BFI);
6635 if (FS != BFS || FS != (int)Bytes) return false;
6636 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6640 if (isBaseWithConstantOffset(Loc)) {
6641 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6642 if (Loc.getOperand(0) == BaseLoc) {
6643 // If the base location is a simple address with no offset itself, then
6644 // the second load's first add operand should be the base address.
6645 if (LocOffset == Dist * (int)Bytes)
6647 } else if (isBaseWithConstantOffset(BaseLoc)) {
6648 // The base location itself has an offset, so subtract that value from the
6649 // second load's offset before comparing to distance * size.
6651 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6652 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6653 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6658 const GlobalValue *GV1 = nullptr;
6659 const GlobalValue *GV2 = nullptr;
6660 int64_t Offset1 = 0;
6661 int64_t Offset2 = 0;
6662 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6663 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6664 if (isGA1 && isGA2 && GV1 == GV2)
6665 return Offset1 == (Offset2 + Dist*Bytes);
6670 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6671 /// it cannot be inferred.
6672 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6673 // If this is a GlobalAddress + cst, return the alignment.
6674 const GlobalValue *GV;
6675 int64_t GVOffset = 0;
6676 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6677 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6678 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6679 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6680 TLI->getDataLayout());
6681 unsigned AlignBits = KnownZero.countTrailingOnes();
6682 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6684 return MinAlign(Align, GVOffset);
6687 // If this is a direct reference to a stack slot, use information about the
6688 // stack slot's alignment.
6689 int FrameIdx = 1 << 31;
6690 int64_t FrameOffset = 0;
6691 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6692 FrameIdx = FI->getIndex();
6693 } else if (isBaseWithConstantOffset(Ptr) &&
6694 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6696 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6697 FrameOffset = Ptr.getConstantOperandVal(1);
6700 if (FrameIdx != (1 << 31)) {
6701 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6702 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6710 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6711 /// which is split (or expanded) into two not necessarily identical pieces.
6712 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6713 // Currently all types are split in half.
6715 if (!VT.isVector()) {
6716 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6718 unsigned NumElements = VT.getVectorNumElements();
6719 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6720 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6723 return std::make_pair(LoVT, HiVT);
6726 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6728 std::pair<SDValue, SDValue>
6729 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6731 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6732 N.getValueType().getVectorNumElements() &&
6733 "More vector elements requested than available!");
6735 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6736 getConstant(0, TLI->getVectorIdxTy()));
6737 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6738 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6739 return std::make_pair(Lo, Hi);
6742 void SelectionDAG::ExtractVectorElements(SDValue Op,
6743 SmallVectorImpl<SDValue> &Args,
6744 unsigned Start, unsigned Count) {
6745 EVT VT = Op.getValueType();
6747 Count = VT.getVectorNumElements();
6749 EVT EltVT = VT.getVectorElementType();
6750 EVT IdxTy = TLI->getVectorIdxTy();
6752 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6753 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6754 Op, getConstant(i, IdxTy)));
6758 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6759 unsigned GlobalAddressSDNode::getAddressSpace() const {
6760 return getGlobal()->getType()->getAddressSpace();
6764 Type *ConstantPoolSDNode::getType() const {
6765 if (isMachineConstantPoolEntry())
6766 return Val.MachineCPVal->getType();
6767 return Val.ConstVal->getType();
6770 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6772 unsigned &SplatBitSize,
6774 unsigned MinSplatBits,
6775 bool isBigEndian) const {
6776 EVT VT = getValueType(0);
6777 assert(VT.isVector() && "Expected a vector type");
6778 unsigned sz = VT.getSizeInBits();
6779 if (MinSplatBits > sz)
6782 SplatValue = APInt(sz, 0);
6783 SplatUndef = APInt(sz, 0);
6785 // Get the bits. Bits with undefined values (when the corresponding element
6786 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6787 // in SplatValue. If any of the values are not constant, give up and return
6789 unsigned int nOps = getNumOperands();
6790 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6791 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6793 for (unsigned j = 0; j < nOps; ++j) {
6794 unsigned i = isBigEndian ? nOps-1-j : j;
6795 SDValue OpVal = getOperand(i);
6796 unsigned BitPos = j * EltBitSize;
6798 if (OpVal.getOpcode() == ISD::UNDEF)
6799 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6800 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6801 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6802 zextOrTrunc(sz) << BitPos;
6803 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6804 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6809 // The build_vector is all constants or undefs. Find the smallest element
6810 // size that splats the vector.
6812 HasAnyUndefs = (SplatUndef != 0);
6815 unsigned HalfSize = sz / 2;
6816 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6817 APInt LowValue = SplatValue.trunc(HalfSize);
6818 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6819 APInt LowUndef = SplatUndef.trunc(HalfSize);
6821 // If the two halves do not match (ignoring undef bits), stop here.
6822 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6823 MinSplatBits > HalfSize)
6826 SplatValue = HighValue | LowValue;
6827 SplatUndef = HighUndef & LowUndef;
6836 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6837 if (UndefElements) {
6838 UndefElements->clear();
6839 UndefElements->resize(getNumOperands());
6842 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6843 SDValue Op = getOperand(i);
6844 if (Op.getOpcode() == ISD::UNDEF) {
6846 (*UndefElements)[i] = true;
6847 } else if (!Splatted) {
6849 } else if (Splatted != Op) {
6855 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6856 "Can only have a splat without a constant for all undefs.");
6857 return getOperand(0);
6864 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6865 return dyn_cast_or_null<ConstantSDNode>(
6866 getSplatValue(UndefElements).getNode());
6870 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6871 return dyn_cast_or_null<ConstantFPSDNode>(
6872 getSplatValue(UndefElements).getNode());
6875 bool BuildVectorSDNode::isConstant() const {
6876 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6877 unsigned Opc = getOperand(i).getOpcode();
6878 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6884 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6885 // Find the first non-undef value in the shuffle mask.
6887 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6890 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6892 // Make sure all remaining elements are either undef or the same as the first
6894 for (int Idx = Mask[i]; i != e; ++i)
6895 if (Mask[i] >= 0 && Mask[i] != Idx)
6901 static void checkForCyclesHelper(const SDNode *N,
6902 SmallPtrSetImpl<const SDNode*> &Visited,
6903 SmallPtrSetImpl<const SDNode*> &Checked,
6904 const llvm::SelectionDAG *DAG) {
6905 // If this node has already been checked, don't check it again.
6906 if (Checked.count(N))
6909 // If a node has already been visited on this depth-first walk, reject it as
6911 if (!Visited.insert(N).second) {
6912 errs() << "Detected cycle in SelectionDAG\n";
6913 dbgs() << "Offending node:\n";
6914 N->dumprFull(DAG); dbgs() << "\n";
6918 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6919 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6926 void llvm::checkForCycles(const llvm::SDNode *N,
6927 const llvm::SelectionDAG *DAG,
6935 assert(N && "Checking nonexistent SDNode");
6936 SmallPtrSet<const SDNode*, 32> visited;
6937 SmallPtrSet<const SDNode*, 32> checked;
6938 checkForCyclesHelper(N, visited, checked, DAG);
6943 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6944 checkForCycles(DAG->getRoot().getNode(), DAG, force);