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;
1590 for (unsigned i = 0; i != NElts; ++i)
1591 Ops.push_back(Splatted);
1594 getNode(ISD::BUILD_VECTOR, dl, BV->getValueType(0), Ops);
1596 // We may have jumped through bitcasts, so the type of the
1597 // BUILD_VECTOR may not match the type of the shuffle.
1598 if (BV->getValueType(0) != VT)
1599 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1606 FoldingSetNodeID ID;
1607 SDValue Ops[2] = { N1, N2 };
1608 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1609 for (unsigned i = 0; i != NElts; ++i)
1610 ID.AddInteger(MaskVec[i]);
1613 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1614 return SDValue(E, 0);
1616 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1617 // SDNode doesn't have access to it. This memory will be "leaked" when
1618 // the node is deallocated, but recovered when the NodeAllocator is released.
1619 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1620 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1622 ShuffleVectorSDNode *N =
1623 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1624 dl.getDebugLoc(), N1, N2,
1626 CSEMap.InsertNode(N, IP);
1628 return SDValue(N, 0);
1631 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1632 MVT VT = SV.getSimpleValueType(0);
1633 unsigned NumElems = VT.getVectorNumElements();
1634 SmallVector<int, 8> MaskVec;
1636 for (unsigned i = 0; i != NumElems; ++i) {
1637 int Idx = SV.getMaskElt(i);
1639 if (Idx < (int)NumElems)
1644 MaskVec.push_back(Idx);
1647 SDValue Op0 = SV.getOperand(0);
1648 SDValue Op1 = SV.getOperand(1);
1649 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1652 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1653 SDValue Val, SDValue DTy,
1654 SDValue STy, SDValue Rnd, SDValue Sat,
1655 ISD::CvtCode Code) {
1656 // If the src and dest types are the same and the conversion is between
1657 // integer types of the same sign or two floats, no conversion is necessary.
1659 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1662 FoldingSetNodeID ID;
1663 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1664 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1667 return SDValue(E, 0);
1669 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1678 FoldingSetNodeID ID;
1679 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1680 ID.AddInteger(RegNo);
1682 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1683 return SDValue(E, 0);
1685 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1686 CSEMap.InsertNode(N, IP);
1688 return SDValue(N, 0);
1691 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1692 FoldingSetNodeID ID;
1693 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1694 ID.AddPointer(RegMask);
1696 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1697 return SDValue(E, 0);
1699 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1700 CSEMap.InsertNode(N, IP);
1702 return SDValue(N, 0);
1705 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1706 FoldingSetNodeID ID;
1707 SDValue Ops[] = { Root };
1708 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1709 ID.AddPointer(Label);
1711 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1712 return SDValue(E, 0);
1714 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1715 dl.getDebugLoc(), Root, Label);
1716 CSEMap.InsertNode(N, IP);
1718 return SDValue(N, 0);
1722 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1725 unsigned char TargetFlags) {
1726 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1728 FoldingSetNodeID ID;
1729 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1731 ID.AddInteger(Offset);
1732 ID.AddInteger(TargetFlags);
1734 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1735 return SDValue(E, 0);
1737 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1739 CSEMap.InsertNode(N, IP);
1741 return SDValue(N, 0);
1744 SDValue SelectionDAG::getSrcValue(const Value *V) {
1745 assert((!V || V->getType()->isPointerTy()) &&
1746 "SrcValue is not a pointer?");
1748 FoldingSetNodeID ID;
1749 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1753 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1754 return SDValue(E, 0);
1756 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1757 CSEMap.InsertNode(N, IP);
1759 return SDValue(N, 0);
1762 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1763 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1764 FoldingSetNodeID ID;
1765 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1769 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1772 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1773 CSEMap.InsertNode(N, IP);
1775 return SDValue(N, 0);
1778 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1779 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1780 unsigned SrcAS, unsigned DestAS) {
1781 SDValue Ops[] = {Ptr};
1782 FoldingSetNodeID ID;
1783 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1784 ID.AddInteger(SrcAS);
1785 ID.AddInteger(DestAS);
1788 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1789 return SDValue(E, 0);
1791 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1793 VT, Ptr, SrcAS, DestAS);
1794 CSEMap.InsertNode(N, IP);
1796 return SDValue(N, 0);
1799 /// getShiftAmountOperand - Return the specified value casted to
1800 /// the target's desired shift amount type.
1801 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1802 EVT OpTy = Op.getValueType();
1803 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1804 if (OpTy == ShTy || OpTy.isVector()) return Op;
1806 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1807 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1810 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1811 /// specified value type.
1812 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1813 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1814 unsigned ByteSize = VT.getStoreSize();
1815 Type *Ty = VT.getTypeForEVT(*getContext());
1816 unsigned StackAlign =
1817 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1819 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1820 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1823 /// CreateStackTemporary - Create a stack temporary suitable for holding
1824 /// either of the specified value types.
1825 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1826 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1827 VT2.getStoreSizeInBits())/8;
1828 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1829 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1830 const DataLayout *TD = TLI->getDataLayout();
1831 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1832 TD->getPrefTypeAlignment(Ty2));
1834 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1835 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1836 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1839 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1840 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1841 // These setcc operations always fold.
1845 case ISD::SETFALSE2: return getConstant(0, VT);
1847 case ISD::SETTRUE2: {
1848 TargetLowering::BooleanContent Cnt =
1849 TLI->getBooleanContents(N1->getValueType(0));
1851 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1864 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1868 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1869 const APInt &C2 = N2C->getAPIntValue();
1870 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1871 const APInt &C1 = N1C->getAPIntValue();
1874 default: llvm_unreachable("Unknown integer setcc!");
1875 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1876 case ISD::SETNE: return getConstant(C1 != C2, VT);
1877 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1878 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1879 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1880 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1881 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1882 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1883 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1884 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1888 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1889 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1890 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1893 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1894 return getUNDEF(VT);
1896 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1897 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1898 return getUNDEF(VT);
1900 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1901 R==APFloat::cmpLessThan, VT);
1902 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1903 return getUNDEF(VT);
1905 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1906 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1907 return getUNDEF(VT);
1909 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1910 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1911 return getUNDEF(VT);
1913 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1914 R==APFloat::cmpEqual, VT);
1915 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1916 return getUNDEF(VT);
1918 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1919 R==APFloat::cmpEqual, VT);
1920 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1921 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1922 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1923 R==APFloat::cmpEqual, VT);
1924 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1925 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1926 R==APFloat::cmpLessThan, VT);
1927 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1928 R==APFloat::cmpUnordered, VT);
1929 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1930 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1933 // Ensure that the constant occurs on the RHS.
1934 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1935 MVT CompVT = N1.getValueType().getSimpleVT();
1936 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1939 return getSetCC(dl, VT, N2, N1, SwappedCond);
1943 // Could not fold it.
1947 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1948 /// use this predicate to simplify operations downstream.
1949 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1950 // This predicate is not safe for vector operations.
1951 if (Op.getValueType().isVector())
1954 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1955 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1958 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1959 /// this predicate to simplify operations downstream. Mask is known to be zero
1960 /// for bits that V cannot have.
1961 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1962 unsigned Depth) const {
1963 APInt KnownZero, KnownOne;
1964 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1965 return (KnownZero & Mask) == Mask;
1968 /// Determine which bits of Op are known to be either zero or one and return
1969 /// them in the KnownZero/KnownOne bitsets.
1970 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1971 APInt &KnownOne, unsigned Depth) const {
1972 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1974 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1976 return; // Limit search depth.
1978 APInt KnownZero2, KnownOne2;
1980 switch (Op.getOpcode()) {
1982 // We know all of the bits for a constant!
1983 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1984 KnownZero = ~KnownOne;
1987 // If either the LHS or the RHS are Zero, the result is zero.
1988 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1989 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1991 // Output known-1 bits are only known if set in both the LHS & RHS.
1992 KnownOne &= KnownOne2;
1993 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1994 KnownZero |= KnownZero2;
1997 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1998 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2000 // Output known-0 bits are only known if clear in both the LHS & RHS.
2001 KnownZero &= KnownZero2;
2002 // Output known-1 are known to be set if set in either the LHS | RHS.
2003 KnownOne |= KnownOne2;
2006 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2007 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2009 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2010 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2011 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2012 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2013 KnownZero = KnownZeroOut;
2017 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2018 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2020 // If low bits are zero in either operand, output low known-0 bits.
2021 // Also compute a conserative estimate for high known-0 bits.
2022 // More trickiness is possible, but this is sufficient for the
2023 // interesting case of alignment computation.
2024 KnownOne.clearAllBits();
2025 unsigned TrailZ = KnownZero.countTrailingOnes() +
2026 KnownZero2.countTrailingOnes();
2027 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2028 KnownZero2.countLeadingOnes(),
2029 BitWidth) - BitWidth;
2031 TrailZ = std::min(TrailZ, BitWidth);
2032 LeadZ = std::min(LeadZ, BitWidth);
2033 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2034 APInt::getHighBitsSet(BitWidth, LeadZ);
2038 // For the purposes of computing leading zeros we can conservatively
2039 // treat a udiv as a logical right shift by the power of 2 known to
2040 // be less than the denominator.
2041 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2042 unsigned LeadZ = KnownZero2.countLeadingOnes();
2044 KnownOne2.clearAllBits();
2045 KnownZero2.clearAllBits();
2046 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2047 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2048 if (RHSUnknownLeadingOnes != BitWidth)
2049 LeadZ = std::min(BitWidth,
2050 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2052 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2056 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2057 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2059 // Only known if known in both the LHS and RHS.
2060 KnownOne &= KnownOne2;
2061 KnownZero &= KnownZero2;
2063 case ISD::SELECT_CC:
2064 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2065 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2067 // Only known if known in both the LHS and RHS.
2068 KnownOne &= KnownOne2;
2069 KnownZero &= KnownZero2;
2077 if (Op.getResNo() != 1)
2079 // The boolean result conforms to getBooleanContents.
2080 // If we know the result of a setcc has the top bits zero, use this info.
2081 // We know that we have an integer-based boolean since these operations
2082 // are only available for integer.
2083 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2084 TargetLowering::ZeroOrOneBooleanContent &&
2086 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2089 // If we know the result of a setcc has the top bits zero, use this info.
2090 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2091 TargetLowering::ZeroOrOneBooleanContent &&
2093 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2096 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2097 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2098 unsigned ShAmt = SA->getZExtValue();
2100 // If the shift count is an invalid immediate, don't do anything.
2101 if (ShAmt >= BitWidth)
2104 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2105 KnownZero <<= ShAmt;
2107 // low bits known zero.
2108 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2112 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2113 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2114 unsigned ShAmt = SA->getZExtValue();
2116 // If the shift count is an invalid immediate, don't do anything.
2117 if (ShAmt >= BitWidth)
2120 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2121 KnownZero = KnownZero.lshr(ShAmt);
2122 KnownOne = KnownOne.lshr(ShAmt);
2124 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2125 KnownZero |= HighBits; // High bits known zero.
2129 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2130 unsigned ShAmt = SA->getZExtValue();
2132 // If the shift count is an invalid immediate, don't do anything.
2133 if (ShAmt >= BitWidth)
2136 // If any of the demanded bits are produced by the sign extension, we also
2137 // demand the input sign bit.
2138 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2140 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141 KnownZero = KnownZero.lshr(ShAmt);
2142 KnownOne = KnownOne.lshr(ShAmt);
2144 // Handle the sign bits.
2145 APInt SignBit = APInt::getSignBit(BitWidth);
2146 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2148 if (KnownZero.intersects(SignBit)) {
2149 KnownZero |= HighBits; // New bits are known zero.
2150 } else if (KnownOne.intersects(SignBit)) {
2151 KnownOne |= HighBits; // New bits are known one.
2155 case ISD::SIGN_EXTEND_INREG: {
2156 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2157 unsigned EBits = EVT.getScalarType().getSizeInBits();
2159 // Sign extension. Compute the demanded bits in the result that are not
2160 // present in the input.
2161 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2163 APInt InSignBit = APInt::getSignBit(EBits);
2164 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2166 // If the sign extended bits are demanded, we know that the sign
2168 InSignBit = InSignBit.zext(BitWidth);
2169 if (NewBits.getBoolValue())
2170 InputDemandedBits |= InSignBit;
2172 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2173 KnownOne &= InputDemandedBits;
2174 KnownZero &= InputDemandedBits;
2176 // If the sign bit of the input is known set or clear, then we know the
2177 // top bits of the result.
2178 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2179 KnownZero |= NewBits;
2180 KnownOne &= ~NewBits;
2181 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2182 KnownOne |= NewBits;
2183 KnownZero &= ~NewBits;
2184 } else { // Input sign bit unknown
2185 KnownZero &= ~NewBits;
2186 KnownOne &= ~NewBits;
2191 case ISD::CTTZ_ZERO_UNDEF:
2193 case ISD::CTLZ_ZERO_UNDEF:
2195 unsigned LowBits = Log2_32(BitWidth)+1;
2196 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2197 KnownOne.clearAllBits();
2201 LoadSDNode *LD = cast<LoadSDNode>(Op);
2202 // If this is a ZEXTLoad and we are looking at the loaded value.
2203 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2204 EVT VT = LD->getMemoryVT();
2205 unsigned MemBits = VT.getScalarType().getSizeInBits();
2206 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2207 } else if (const MDNode *Ranges = LD->getRanges()) {
2208 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2212 case ISD::ZERO_EXTEND: {
2213 EVT InVT = Op.getOperand(0).getValueType();
2214 unsigned InBits = InVT.getScalarType().getSizeInBits();
2215 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2216 KnownZero = KnownZero.trunc(InBits);
2217 KnownOne = KnownOne.trunc(InBits);
2218 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2219 KnownZero = KnownZero.zext(BitWidth);
2220 KnownOne = KnownOne.zext(BitWidth);
2221 KnownZero |= NewBits;
2224 case ISD::SIGN_EXTEND: {
2225 EVT InVT = Op.getOperand(0).getValueType();
2226 unsigned InBits = InVT.getScalarType().getSizeInBits();
2227 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2229 KnownZero = KnownZero.trunc(InBits);
2230 KnownOne = KnownOne.trunc(InBits);
2231 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2233 // Note if the sign bit is known to be zero or one.
2234 bool SignBitKnownZero = KnownZero.isNegative();
2235 bool SignBitKnownOne = KnownOne.isNegative();
2237 KnownZero = KnownZero.zext(BitWidth);
2238 KnownOne = KnownOne.zext(BitWidth);
2240 // If the sign bit is known zero or one, the top bits match.
2241 if (SignBitKnownZero)
2242 KnownZero |= NewBits;
2243 else if (SignBitKnownOne)
2244 KnownOne |= NewBits;
2247 case ISD::ANY_EXTEND: {
2248 EVT InVT = Op.getOperand(0).getValueType();
2249 unsigned InBits = InVT.getScalarType().getSizeInBits();
2250 KnownZero = KnownZero.trunc(InBits);
2251 KnownOne = KnownOne.trunc(InBits);
2252 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2253 KnownZero = KnownZero.zext(BitWidth);
2254 KnownOne = KnownOne.zext(BitWidth);
2257 case ISD::TRUNCATE: {
2258 EVT InVT = Op.getOperand(0).getValueType();
2259 unsigned InBits = InVT.getScalarType().getSizeInBits();
2260 KnownZero = KnownZero.zext(InBits);
2261 KnownOne = KnownOne.zext(InBits);
2262 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2263 KnownZero = KnownZero.trunc(BitWidth);
2264 KnownOne = KnownOne.trunc(BitWidth);
2267 case ISD::AssertZext: {
2268 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2269 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2270 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2271 KnownZero |= (~InMask);
2272 KnownOne &= (~KnownZero);
2276 // All bits are zero except the low bit.
2277 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2281 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2282 // We know that the top bits of C-X are clear if X contains less bits
2283 // than C (i.e. no wrap-around can happen). For example, 20-X is
2284 // positive if we can prove that X is >= 0 and < 16.
2285 if (CLHS->getAPIntValue().isNonNegative()) {
2286 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2287 // NLZ can't be BitWidth with no sign bit
2288 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2289 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2291 // If all of the MaskV bits are known to be zero, then we know the
2292 // output top bits are zero, because we now know that the output is
2294 if ((KnownZero2 & MaskV) == MaskV) {
2295 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2296 // Top bits known zero.
2297 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2305 // Output known-0 bits are known if clear or set in both the low clear bits
2306 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2307 // low 3 bits clear.
2308 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2309 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2311 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2312 KnownZeroOut = std::min(KnownZeroOut,
2313 KnownZero2.countTrailingOnes());
2315 if (Op.getOpcode() == ISD::ADD) {
2316 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2320 // With ADDE, a carry bit may be added in, so we can only use this
2321 // information if we know (at least) that the low two bits are clear. We
2322 // then return to the caller that the low bit is unknown but that other bits
2324 if (KnownZeroOut >= 2) // ADDE
2325 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2329 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2330 const APInt &RA = Rem->getAPIntValue().abs();
2331 if (RA.isPowerOf2()) {
2332 APInt LowBits = RA - 1;
2333 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2335 // The low bits of the first operand are unchanged by the srem.
2336 KnownZero = KnownZero2 & LowBits;
2337 KnownOne = KnownOne2 & LowBits;
2339 // If the first operand is non-negative or has all low bits zero, then
2340 // the upper bits are all zero.
2341 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2342 KnownZero |= ~LowBits;
2344 // If the first operand is negative and not all low bits are zero, then
2345 // the upper bits are all one.
2346 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2347 KnownOne |= ~LowBits;
2348 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2353 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2354 const APInt &RA = Rem->getAPIntValue();
2355 if (RA.isPowerOf2()) {
2356 APInt LowBits = (RA - 1);
2357 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2359 // The upper bits are all zero, the lower ones are unchanged.
2360 KnownZero = KnownZero2 | ~LowBits;
2361 KnownOne = KnownOne2 & LowBits;
2366 // Since the result is less than or equal to either operand, any leading
2367 // zero bits in either operand must also exist in the result.
2368 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2369 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2371 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2372 KnownZero2.countLeadingOnes());
2373 KnownOne.clearAllBits();
2374 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2377 case ISD::EXTRACT_ELEMENT: {
2378 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2379 const unsigned Index =
2380 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2381 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2383 // Remove low part of known bits mask
2384 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2385 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2387 // Remove high part of known bit mask
2388 KnownZero = KnownZero.trunc(BitWidth);
2389 KnownOne = KnownOne.trunc(BitWidth);
2392 case ISD::FrameIndex:
2393 case ISD::TargetFrameIndex:
2394 if (unsigned Align = InferPtrAlignment(Op)) {
2395 // The low bits are known zero if the pointer is aligned.
2396 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2402 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2405 case ISD::INTRINSIC_WO_CHAIN:
2406 case ISD::INTRINSIC_W_CHAIN:
2407 case ISD::INTRINSIC_VOID:
2408 // Allow the target to implement this method for its nodes.
2409 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2413 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2416 /// ComputeNumSignBits - Return the number of times the sign bit of the
2417 /// register is replicated into the other bits. We know that at least 1 bit
2418 /// is always equal to the sign bit (itself), but other cases can give us
2419 /// information. For example, immediately after an "SRA X, 2", we know that
2420 /// the top 3 bits are all equal to each other, so we return 3.
2421 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2422 EVT VT = Op.getValueType();
2423 assert(VT.isInteger() && "Invalid VT!");
2424 unsigned VTBits = VT.getScalarType().getSizeInBits();
2426 unsigned FirstAnswer = 1;
2429 return 1; // Limit search depth.
2431 switch (Op.getOpcode()) {
2433 case ISD::AssertSext:
2434 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2435 return VTBits-Tmp+1;
2436 case ISD::AssertZext:
2437 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2440 case ISD::Constant: {
2441 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2442 return Val.getNumSignBits();
2445 case ISD::SIGN_EXTEND:
2447 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2448 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2450 case ISD::SIGN_EXTEND_INREG:
2451 // Max of the input and what this extends.
2453 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2456 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2457 return std::max(Tmp, Tmp2);
2460 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2461 // SRA X, C -> adds C sign bits.
2462 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2463 Tmp += C->getZExtValue();
2464 if (Tmp > VTBits) Tmp = VTBits;
2468 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2469 // shl destroys sign bits.
2470 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471 if (C->getZExtValue() >= VTBits || // Bad shift.
2472 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2473 return Tmp - C->getZExtValue();
2478 case ISD::XOR: // NOT is handled here.
2479 // Logical binary ops preserve the number of sign bits at the worst.
2480 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2482 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2483 FirstAnswer = std::min(Tmp, Tmp2);
2484 // We computed what we know about the sign bits as our first
2485 // answer. Now proceed to the generic code that uses
2486 // computeKnownBits, and pick whichever answer is better.
2491 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2492 if (Tmp == 1) return 1; // Early out.
2493 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2494 return std::min(Tmp, Tmp2);
2502 if (Op.getResNo() != 1)
2504 // The boolean result conforms to getBooleanContents. Fall through.
2505 // If setcc returns 0/-1, all bits are sign bits.
2506 // We know that we have an integer-based boolean since these operations
2507 // are only available for integer.
2508 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2509 TargetLowering::ZeroOrNegativeOneBooleanContent)
2513 // If setcc returns 0/-1, all bits are sign bits.
2514 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2515 TargetLowering::ZeroOrNegativeOneBooleanContent)
2520 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2521 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2523 // Handle rotate right by N like a rotate left by 32-N.
2524 if (Op.getOpcode() == ISD::ROTR)
2525 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2527 // If we aren't rotating out all of the known-in sign bits, return the
2528 // number that are left. This handles rotl(sext(x), 1) for example.
2529 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2530 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2534 // Add can have at most one carry bit. Thus we know that the output
2535 // is, at worst, one more bit than the inputs.
2536 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2537 if (Tmp == 1) return 1; // Early out.
2539 // Special case decrementing a value (ADD X, -1):
2540 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2541 if (CRHS->isAllOnesValue()) {
2542 APInt KnownZero, KnownOne;
2543 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2545 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2547 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2550 // If we are subtracting one from a positive number, there is no carry
2551 // out of the result.
2552 if (KnownZero.isNegative())
2556 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2557 if (Tmp2 == 1) return 1;
2558 return std::min(Tmp, Tmp2)-1;
2561 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2562 if (Tmp2 == 1) return 1;
2565 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2566 if (CLHS->isNullValue()) {
2567 APInt KnownZero, KnownOne;
2568 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2569 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2571 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2574 // If the input is known to be positive (the sign bit is known clear),
2575 // the output of the NEG has the same number of sign bits as the input.
2576 if (KnownZero.isNegative())
2579 // Otherwise, we treat this like a SUB.
2582 // Sub can have at most one carry bit. Thus we know that the output
2583 // is, at worst, one more bit than the inputs.
2584 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2585 if (Tmp == 1) return 1; // Early out.
2586 return std::min(Tmp, Tmp2)-1;
2588 // FIXME: it's tricky to do anything useful for this, but it is an important
2589 // case for targets like X86.
2591 case ISD::EXTRACT_ELEMENT: {
2592 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2593 const int BitWidth = Op.getValueType().getSizeInBits();
2595 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2597 // Get reverse index (starting from 1), Op1 value indexes elements from
2598 // little end. Sign starts at big end.
2599 const int rIndex = Items - 1 -
2600 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2602 // If the sign portion ends in our element the substraction gives correct
2603 // result. Otherwise it gives either negative or > bitwidth result
2604 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2608 // If we are looking at the loaded value of the SDNode.
2609 if (Op.getResNo() == 0) {
2610 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2611 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2612 unsigned ExtType = LD->getExtensionType();
2615 case ISD::SEXTLOAD: // '17' bits known
2616 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2617 return VTBits-Tmp+1;
2618 case ISD::ZEXTLOAD: // '16' bits known
2619 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2625 // Allow the target to implement this method for its nodes.
2626 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2627 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2628 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2629 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2630 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2631 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2634 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2635 // use this information.
2636 APInt KnownZero, KnownOne;
2637 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2640 if (KnownZero.isNegative()) { // sign bit is 0
2642 } else if (KnownOne.isNegative()) { // sign bit is 1;
2649 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2650 // the number of identical bits in the top of the input value.
2652 Mask <<= Mask.getBitWidth()-VTBits;
2653 // Return # leading zeros. We use 'min' here in case Val was zero before
2654 // shifting. We don't want to return '64' as for an i32 "0".
2655 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2658 /// isBaseWithConstantOffset - Return true if the specified operand is an
2659 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2660 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2661 /// semantics as an ADD. This handles the equivalence:
2662 /// X|Cst == X+Cst iff X&Cst = 0.
2663 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2664 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2665 !isa<ConstantSDNode>(Op.getOperand(1)))
2668 if (Op.getOpcode() == ISD::OR &&
2669 !MaskedValueIsZero(Op.getOperand(0),
2670 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2677 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2678 // If we're told that NaNs won't happen, assume they won't.
2679 if (getTarget().Options.NoNaNsFPMath)
2682 // If the value is a constant, we can obviously see if it is a NaN or not.
2683 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2684 return !C->getValueAPF().isNaN();
2686 // TODO: Recognize more cases here.
2691 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2692 // If the value is a constant, we can obviously see if it is a zero or not.
2693 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2694 return !C->isZero();
2696 // TODO: Recognize more cases here.
2697 switch (Op.getOpcode()) {
2700 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2701 return !C->isNullValue();
2708 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2709 // Check the obvious case.
2710 if (A == B) return true;
2712 // For for negative and positive zero.
2713 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2714 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2715 if (CA->isZero() && CB->isZero()) return true;
2717 // Otherwise they may not be equal.
2721 /// getNode - Gets or creates the specified node.
2723 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2724 FoldingSetNodeID ID;
2725 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2727 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2728 return SDValue(E, 0);
2730 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2731 DL.getDebugLoc(), getVTList(VT));
2732 CSEMap.InsertNode(N, IP);
2735 return SDValue(N, 0);
2738 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2739 EVT VT, SDValue Operand) {
2740 // Constant fold unary operations with an integer constant operand. Even
2741 // opaque constant will be folded, because the folding of unary operations
2742 // doesn't create new constants with different values. Nevertheless, the
2743 // opaque flag is preserved during folding to prevent future folding with
2745 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2746 const APInt &Val = C->getAPIntValue();
2749 case ISD::SIGN_EXTEND:
2750 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2751 C->isTargetOpcode(), C->isOpaque());
2752 case ISD::ANY_EXTEND:
2753 case ISD::ZERO_EXTEND:
2755 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2756 C->isTargetOpcode(), C->isOpaque());
2757 case ISD::UINT_TO_FP:
2758 case ISD::SINT_TO_FP: {
2759 APFloat apf(EVTToAPFloatSemantics(VT),
2760 APInt::getNullValue(VT.getSizeInBits()));
2761 (void)apf.convertFromAPInt(Val,
2762 Opcode==ISD::SINT_TO_FP,
2763 APFloat::rmNearestTiesToEven);
2764 return getConstantFP(apf, VT);
2767 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2768 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2769 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2770 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2771 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2772 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2775 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2778 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2781 case ISD::CTLZ_ZERO_UNDEF:
2782 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2785 case ISD::CTTZ_ZERO_UNDEF:
2786 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2791 // Constant fold unary operations with a floating point constant operand.
2792 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2793 APFloat V = C->getValueAPF(); // make copy
2797 return getConstantFP(V, VT);
2800 return getConstantFP(V, VT);
2802 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2803 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2804 return getConstantFP(V, VT);
2808 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2809 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2810 return getConstantFP(V, VT);
2814 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2815 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2816 return getConstantFP(V, VT);
2819 case ISD::FP_EXTEND: {
2821 // This can return overflow, underflow, or inexact; we don't care.
2822 // FIXME need to be more flexible about rounding mode.
2823 (void)V.convert(EVTToAPFloatSemantics(VT),
2824 APFloat::rmNearestTiesToEven, &ignored);
2825 return getConstantFP(V, VT);
2827 case ISD::FP_TO_SINT:
2828 case ISD::FP_TO_UINT: {
2831 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2832 // FIXME need to be more flexible about rounding mode.
2833 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2834 Opcode==ISD::FP_TO_SINT,
2835 APFloat::rmTowardZero, &ignored);
2836 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2838 APInt api(VT.getSizeInBits(), x);
2839 return getConstant(api, VT);
2842 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2843 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2844 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2845 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2846 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2847 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2852 // Constant fold unary operations with a vector integer operand.
2853 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2854 if (BV->isConstant()) {
2857 // FIXME: Entirely reasonable to perform folding of other unary
2858 // operations here as the need arises.
2860 case ISD::UINT_TO_FP:
2861 case ISD::SINT_TO_FP: {
2862 SmallVector<SDValue, 8> Ops;
2863 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2864 SDValue OpN = BV->getOperand(i);
2865 // Let the above scalar folding handle the conversion of each
2867 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2871 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2877 unsigned OpOpcode = Operand.getNode()->getOpcode();
2879 case ISD::TokenFactor:
2880 case ISD::MERGE_VALUES:
2881 case ISD::CONCAT_VECTORS:
2882 return Operand; // Factor, merge or concat of one node? No need.
2883 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2884 case ISD::FP_EXTEND:
2885 assert(VT.isFloatingPoint() &&
2886 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2887 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2888 assert((!VT.isVector() ||
2889 VT.getVectorNumElements() ==
2890 Operand.getValueType().getVectorNumElements()) &&
2891 "Vector element count mismatch!");
2892 if (Operand.getOpcode() == ISD::UNDEF)
2893 return getUNDEF(VT);
2895 case ISD::SIGN_EXTEND:
2896 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2897 "Invalid SIGN_EXTEND!");
2898 if (Operand.getValueType() == VT) return Operand; // noop extension
2899 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2900 "Invalid sext node, dst < src!");
2901 assert((!VT.isVector() ||
2902 VT.getVectorNumElements() ==
2903 Operand.getValueType().getVectorNumElements()) &&
2904 "Vector element count mismatch!");
2905 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2906 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2907 else if (OpOpcode == ISD::UNDEF)
2908 // sext(undef) = 0, because the top bits will all be the same.
2909 return getConstant(0, VT);
2911 case ISD::ZERO_EXTEND:
2912 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2913 "Invalid ZERO_EXTEND!");
2914 if (Operand.getValueType() == VT) return Operand; // noop extension
2915 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2916 "Invalid zext node, dst < src!");
2917 assert((!VT.isVector() ||
2918 VT.getVectorNumElements() ==
2919 Operand.getValueType().getVectorNumElements()) &&
2920 "Vector element count mismatch!");
2921 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2922 return getNode(ISD::ZERO_EXTEND, DL, VT,
2923 Operand.getNode()->getOperand(0));
2924 else if (OpOpcode == ISD::UNDEF)
2925 // zext(undef) = 0, because the top bits will be zero.
2926 return getConstant(0, VT);
2928 case ISD::ANY_EXTEND:
2929 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2930 "Invalid ANY_EXTEND!");
2931 if (Operand.getValueType() == VT) return Operand; // noop extension
2932 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2933 "Invalid anyext node, dst < src!");
2934 assert((!VT.isVector() ||
2935 VT.getVectorNumElements() ==
2936 Operand.getValueType().getVectorNumElements()) &&
2937 "Vector element count mismatch!");
2939 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2940 OpOpcode == ISD::ANY_EXTEND)
2941 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2942 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2943 else if (OpOpcode == ISD::UNDEF)
2944 return getUNDEF(VT);
2946 // (ext (trunx x)) -> x
2947 if (OpOpcode == ISD::TRUNCATE) {
2948 SDValue OpOp = Operand.getNode()->getOperand(0);
2949 if (OpOp.getValueType() == VT)
2954 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2955 "Invalid TRUNCATE!");
2956 if (Operand.getValueType() == VT) return Operand; // noop truncate
2957 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2958 "Invalid truncate node, src < dst!");
2959 assert((!VT.isVector() ||
2960 VT.getVectorNumElements() ==
2961 Operand.getValueType().getVectorNumElements()) &&
2962 "Vector element count mismatch!");
2963 if (OpOpcode == ISD::TRUNCATE)
2964 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2965 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2966 OpOpcode == ISD::ANY_EXTEND) {
2967 // If the source is smaller than the dest, we still need an extend.
2968 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2969 .bitsLT(VT.getScalarType()))
2970 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2971 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2972 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2973 return Operand.getNode()->getOperand(0);
2975 if (OpOpcode == ISD::UNDEF)
2976 return getUNDEF(VT);
2979 // Basic sanity checking.
2980 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2981 && "Cannot BITCAST between types of different sizes!");
2982 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2983 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2984 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2985 if (OpOpcode == ISD::UNDEF)
2986 return getUNDEF(VT);
2988 case ISD::SCALAR_TO_VECTOR:
2989 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2990 (VT.getVectorElementType() == Operand.getValueType() ||
2991 (VT.getVectorElementType().isInteger() &&
2992 Operand.getValueType().isInteger() &&
2993 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2994 "Illegal SCALAR_TO_VECTOR node!");
2995 if (OpOpcode == ISD::UNDEF)
2996 return getUNDEF(VT);
2997 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2998 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2999 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3000 Operand.getConstantOperandVal(1) == 0 &&
3001 Operand.getOperand(0).getValueType() == VT)
3002 return Operand.getOperand(0);
3005 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3006 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3007 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3008 Operand.getNode()->getOperand(0));
3009 if (OpOpcode == ISD::FNEG) // --X -> X
3010 return Operand.getNode()->getOperand(0);
3013 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3014 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3019 SDVTList VTs = getVTList(VT);
3020 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3021 FoldingSetNodeID ID;
3022 SDValue Ops[1] = { Operand };
3023 AddNodeIDNode(ID, Opcode, VTs, Ops);
3025 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3026 return SDValue(E, 0);
3028 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3029 DL.getDebugLoc(), VTs, Operand);
3030 CSEMap.InsertNode(N, IP);
3032 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3033 DL.getDebugLoc(), VTs, Operand);
3037 return SDValue(N, 0);
3040 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3041 SDNode *Cst1, SDNode *Cst2) {
3042 // If the opcode is a target-specific ISD node, there's nothing we can
3043 // do here and the operand rules may not line up with the below, so
3045 if (Opcode >= ISD::BUILTIN_OP_END)
3048 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3049 SmallVector<SDValue, 4> Outputs;
3050 EVT SVT = VT.getScalarType();
3052 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3053 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3054 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3057 if (Scalar1 && Scalar2)
3058 // Scalar instruction.
3059 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3061 // For vectors extract each constant element into Inputs so we can constant
3062 // fold them individually.
3063 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3064 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3068 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3070 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3071 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3072 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3073 if (!V1 || !V2) // Not a constant, bail.
3076 if (V1->isOpaque() || V2->isOpaque())
3079 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3080 // FIXME: This is valid and could be handled by truncating the APInts.
3081 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3084 Inputs.push_back(std::make_pair(V1, V2));
3088 // We have a number of constant values, constant fold them element by element.
3089 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3090 const APInt &C1 = Inputs[I].first->getAPIntValue();
3091 const APInt &C2 = Inputs[I].second->getAPIntValue();
3095 Outputs.push_back(getConstant(C1 + C2, SVT));
3098 Outputs.push_back(getConstant(C1 - C2, SVT));
3101 Outputs.push_back(getConstant(C1 * C2, SVT));
3104 if (!C2.getBoolValue())
3106 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3109 if (!C2.getBoolValue())
3111 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3114 if (!C2.getBoolValue())
3116 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3119 if (!C2.getBoolValue())
3121 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3124 Outputs.push_back(getConstant(C1 & C2, SVT));
3127 Outputs.push_back(getConstant(C1 | C2, SVT));
3130 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3133 Outputs.push_back(getConstant(C1 << C2, SVT));
3136 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3139 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3142 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3145 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3152 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3153 "Expected a scalar or vector!"));
3155 // Handle the scalar case first.
3157 return Outputs.back();
3159 // We may have a vector type but a scalar result. Create a splat.
3160 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3162 // Build a big vector out of the scalar elements we generated.
3163 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3166 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3167 SDValue N2, bool nuw, bool nsw, bool exact) {
3168 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3169 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3172 case ISD::TokenFactor:
3173 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3174 N2.getValueType() == MVT::Other && "Invalid token factor!");
3175 // Fold trivial token factors.
3176 if (N1.getOpcode() == ISD::EntryToken) return N2;
3177 if (N2.getOpcode() == ISD::EntryToken) return N1;
3178 if (N1 == N2) return N1;
3180 case ISD::CONCAT_VECTORS:
3181 // Concat of UNDEFs is UNDEF.
3182 if (N1.getOpcode() == ISD::UNDEF &&
3183 N2.getOpcode() == ISD::UNDEF)
3184 return getUNDEF(VT);
3186 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3187 // one big BUILD_VECTOR.
3188 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3189 N2.getOpcode() == ISD::BUILD_VECTOR) {
3190 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3191 N1.getNode()->op_end());
3192 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3193 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3197 assert(VT.isInteger() && "This operator does not apply to FP types!");
3198 assert(N1.getValueType() == N2.getValueType() &&
3199 N1.getValueType() == VT && "Binary operator types must match!");
3200 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3201 // worth handling here.
3202 if (N2C && N2C->isNullValue())
3204 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3211 assert(VT.isInteger() && "This operator does not apply to FP types!");
3212 assert(N1.getValueType() == N2.getValueType() &&
3213 N1.getValueType() == VT && "Binary operator types must match!");
3214 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3215 // it's worth handling here.
3216 if (N2C && N2C->isNullValue())
3226 assert(VT.isInteger() && "This operator does not apply to FP types!");
3227 assert(N1.getValueType() == N2.getValueType() &&
3228 N1.getValueType() == VT && "Binary operator types must match!");
3235 if (getTarget().Options.UnsafeFPMath) {
3236 if (Opcode == ISD::FADD) {
3238 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3239 if (CFP->getValueAPF().isZero())
3242 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3243 if (CFP->getValueAPF().isZero())
3245 } else if (Opcode == ISD::FSUB) {
3247 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3248 if (CFP->getValueAPF().isZero())
3250 } else if (Opcode == ISD::FMUL) {
3251 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3254 // If the first operand isn't the constant, try the second
3256 CFP = dyn_cast<ConstantFPSDNode>(N2);
3263 return SDValue(CFP,0);
3265 if (CFP->isExactlyValue(1.0))
3270 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3271 assert(N1.getValueType() == N2.getValueType() &&
3272 N1.getValueType() == VT && "Binary operator types must match!");
3274 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3275 assert(N1.getValueType() == VT &&
3276 N1.getValueType().isFloatingPoint() &&
3277 N2.getValueType().isFloatingPoint() &&
3278 "Invalid FCOPYSIGN!");
3285 assert(VT == N1.getValueType() &&
3286 "Shift operators return type must be the same as their first arg");
3287 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3288 "Shifts only work on integers");
3289 assert((!VT.isVector() || VT == N2.getValueType()) &&
3290 "Vector shift amounts must be in the same as their first arg");
3291 // Verify that the shift amount VT is bit enough to hold valid shift
3292 // amounts. This catches things like trying to shift an i1024 value by an
3293 // i8, which is easy to fall into in generic code that uses
3294 // TLI.getShiftAmount().
3295 assert(N2.getValueType().getSizeInBits() >=
3296 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3297 "Invalid use of small shift amount with oversized value!");
3299 // Always fold shifts of i1 values so the code generator doesn't need to
3300 // handle them. Since we know the size of the shift has to be less than the
3301 // size of the value, the shift/rotate count is guaranteed to be zero.
3304 if (N2C && N2C->isNullValue())
3307 case ISD::FP_ROUND_INREG: {
3308 EVT EVT = cast<VTSDNode>(N2)->getVT();
3309 assert(VT == N1.getValueType() && "Not an inreg round!");
3310 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3311 "Cannot FP_ROUND_INREG integer types");
3312 assert(EVT.isVector() == VT.isVector() &&
3313 "FP_ROUND_INREG type should be vector iff the operand "
3315 assert((!EVT.isVector() ||
3316 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3317 "Vector element counts must match in FP_ROUND_INREG");
3318 assert(EVT.bitsLE(VT) && "Not rounding down!");
3320 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3324 assert(VT.isFloatingPoint() &&
3325 N1.getValueType().isFloatingPoint() &&
3326 VT.bitsLE(N1.getValueType()) &&
3327 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3328 if (N1.getValueType() == VT) return N1; // noop conversion.
3330 case ISD::AssertSext:
3331 case ISD::AssertZext: {
3332 EVT EVT = cast<VTSDNode>(N2)->getVT();
3333 assert(VT == N1.getValueType() && "Not an inreg extend!");
3334 assert(VT.isInteger() && EVT.isInteger() &&
3335 "Cannot *_EXTEND_INREG FP types");
3336 assert(!EVT.isVector() &&
3337 "AssertSExt/AssertZExt type should be the vector element type "
3338 "rather than the vector type!");
3339 assert(EVT.bitsLE(VT) && "Not extending!");
3340 if (VT == EVT) return N1; // noop assertion.
3343 case ISD::SIGN_EXTEND_INREG: {
3344 EVT EVT = cast<VTSDNode>(N2)->getVT();
3345 assert(VT == N1.getValueType() && "Not an inreg extend!");
3346 assert(VT.isInteger() && EVT.isInteger() &&
3347 "Cannot *_EXTEND_INREG FP types");
3348 assert(EVT.isVector() == VT.isVector() &&
3349 "SIGN_EXTEND_INREG type should be vector iff the operand "
3351 assert((!EVT.isVector() ||
3352 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3353 "Vector element counts must match in SIGN_EXTEND_INREG");
3354 assert(EVT.bitsLE(VT) && "Not extending!");
3355 if (EVT == VT) return N1; // Not actually extending
3358 APInt Val = N1C->getAPIntValue();
3359 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3360 Val <<= Val.getBitWidth()-FromBits;
3361 Val = Val.ashr(Val.getBitWidth()-FromBits);
3362 return getConstant(Val, VT);
3366 case ISD::EXTRACT_VECTOR_ELT:
3367 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3368 if (N1.getOpcode() == ISD::UNDEF)
3369 return getUNDEF(VT);
3371 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3372 // expanding copies of large vectors from registers.
3374 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3375 N1.getNumOperands() > 0) {
3377 N1.getOperand(0).getValueType().getVectorNumElements();
3378 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3379 N1.getOperand(N2C->getZExtValue() / Factor),
3380 getConstant(N2C->getZExtValue() % Factor,
3381 N2.getValueType()));
3384 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3385 // expanding large vector constants.
3386 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3387 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3389 if (VT != Elt.getValueType())
3390 // If the vector element type is not legal, the BUILD_VECTOR operands
3391 // are promoted and implicitly truncated, and the result implicitly
3392 // extended. Make that explicit here.
3393 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3398 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3399 // operations are lowered to scalars.
3400 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3401 // If the indices are the same, return the inserted element else
3402 // if the indices are known different, extract the element from
3403 // the original vector.
3404 SDValue N1Op2 = N1.getOperand(2);
3405 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3407 if (N1Op2C && N2C) {
3408 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3409 if (VT == N1.getOperand(1).getValueType())
3410 return N1.getOperand(1);
3412 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3415 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3419 case ISD::EXTRACT_ELEMENT:
3420 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3421 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3422 (N1.getValueType().isInteger() == VT.isInteger()) &&
3423 N1.getValueType() != VT &&
3424 "Wrong types for EXTRACT_ELEMENT!");
3426 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3427 // 64-bit integers into 32-bit parts. Instead of building the extract of
3428 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3429 if (N1.getOpcode() == ISD::BUILD_PAIR)
3430 return N1.getOperand(N2C->getZExtValue());
3432 // EXTRACT_ELEMENT of a constant int is also very common.
3433 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3434 unsigned ElementSize = VT.getSizeInBits();
3435 unsigned Shift = ElementSize * N2C->getZExtValue();
3436 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3437 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3440 case ISD::EXTRACT_SUBVECTOR: {
3442 if (VT.isSimple() && N1.getValueType().isSimple()) {
3443 assert(VT.isVector() && N1.getValueType().isVector() &&
3444 "Extract subvector VTs must be a vectors!");
3445 assert(VT.getVectorElementType() ==
3446 N1.getValueType().getVectorElementType() &&
3447 "Extract subvector VTs must have the same element type!");
3448 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3449 "Extract subvector must be from larger vector to smaller vector!");
3451 if (isa<ConstantSDNode>(Index.getNode())) {
3452 assert((VT.getVectorNumElements() +
3453 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3454 <= N1.getValueType().getVectorNumElements())
3455 && "Extract subvector overflow!");
3458 // Trivial extraction.
3459 if (VT.getSimpleVT() == N1.getSimpleValueType())
3466 // Perform trivial constant folding.
3468 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3471 // Canonicalize constant to RHS if commutative.
3472 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3473 std::swap(N1C, N2C);
3477 // Constant fold FP operations.
3478 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3479 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3480 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3482 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3483 // Canonicalize constant to RHS if commutative.
3484 std::swap(N1CFP, N2CFP);
3487 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3488 APFloat::opStatus s;
3491 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3492 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3493 return getConstantFP(V1, VT);
3496 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3497 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3498 return getConstantFP(V1, VT);
3501 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3502 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3503 return getConstantFP(V1, VT);
3506 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3507 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3508 s!=APFloat::opDivByZero)) {
3509 return getConstantFP(V1, VT);
3513 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3514 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3515 s!=APFloat::opDivByZero)) {
3516 return getConstantFP(V1, VT);
3519 case ISD::FCOPYSIGN:
3521 return getConstantFP(V1, VT);
3526 if (Opcode == ISD::FP_ROUND) {
3527 APFloat V = N1CFP->getValueAPF(); // make copy
3529 // This can return overflow, underflow, or inexact; we don't care.
3530 // FIXME need to be more flexible about rounding mode.
3531 (void)V.convert(EVTToAPFloatSemantics(VT),
3532 APFloat::rmNearestTiesToEven, &ignored);
3533 return getConstantFP(V, VT);
3537 // Canonicalize an UNDEF to the RHS, even over a constant.
3538 if (N1.getOpcode() == ISD::UNDEF) {
3539 if (isCommutativeBinOp(Opcode)) {
3543 case ISD::FP_ROUND_INREG:
3544 case ISD::SIGN_EXTEND_INREG:
3550 return N1; // fold op(undef, arg2) -> undef
3558 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3559 // For vectors, we can't easily build an all zero vector, just return
3566 // Fold a bunch of operators when the RHS is undef.
3567 if (N2.getOpcode() == ISD::UNDEF) {
3570 if (N1.getOpcode() == ISD::UNDEF)
3571 // Handle undef ^ undef -> 0 special case. This is a common
3573 return getConstant(0, VT);
3583 return N2; // fold op(arg1, undef) -> undef
3589 if (getTarget().Options.UnsafeFPMath)
3597 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3598 // For vectors, we can't easily build an all zero vector, just return
3603 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3604 // For vectors, we can't easily build an all one vector, just return
3612 // Memoize this node if possible.
3614 SDVTList VTs = getVTList(VT);
3615 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3616 if (VT != MVT::Glue) {
3617 SDValue Ops[] = {N1, N2};
3618 FoldingSetNodeID ID;
3619 AddNodeIDNode(ID, Opcode, VTs, Ops);
3621 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3623 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3624 return SDValue(E, 0);
3626 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3628 CSEMap.InsertNode(N, IP);
3631 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3635 return SDValue(N, 0);
3638 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3639 SDValue N1, SDValue N2, SDValue N3) {
3640 // Perform various simplifications.
3641 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3644 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3645 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3646 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3647 if (N1CFP && N2CFP && N3CFP) {
3648 APFloat V1 = N1CFP->getValueAPF();
3649 const APFloat &V2 = N2CFP->getValueAPF();
3650 const APFloat &V3 = N3CFP->getValueAPF();
3651 APFloat::opStatus s =
3652 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3653 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3654 return getConstantFP(V1, VT);
3658 case ISD::CONCAT_VECTORS:
3659 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3660 // one big BUILD_VECTOR.
3661 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3662 N2.getOpcode() == ISD::BUILD_VECTOR &&
3663 N3.getOpcode() == ISD::BUILD_VECTOR) {
3664 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3665 N1.getNode()->op_end());
3666 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3667 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3668 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3672 // Use FoldSetCC to simplify SETCC's.
3673 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3674 if (Simp.getNode()) return Simp;
3679 if (N1C->getZExtValue())
3680 return N2; // select true, X, Y -> X
3681 return N3; // select false, X, Y -> Y
3684 if (N2 == N3) return N2; // select C, X, X -> X
3686 case ISD::VECTOR_SHUFFLE:
3687 llvm_unreachable("should use getVectorShuffle constructor!");
3688 case ISD::INSERT_SUBVECTOR: {
3690 if (VT.isSimple() && N1.getValueType().isSimple()
3691 && N2.getValueType().isSimple()) {
3692 assert(VT.isVector() && N1.getValueType().isVector() &&
3693 N2.getValueType().isVector() &&
3694 "Insert subvector VTs must be a vectors");
3695 assert(VT == N1.getValueType() &&
3696 "Dest and insert subvector source types must match!");
3697 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3698 "Insert subvector must be from smaller vector to larger vector!");
3699 if (isa<ConstantSDNode>(Index.getNode())) {
3700 assert((N2.getValueType().getVectorNumElements() +
3701 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3702 <= VT.getVectorNumElements())
3703 && "Insert subvector overflow!");
3706 // Trivial insertion.
3707 if (VT.getSimpleVT() == N2.getSimpleValueType())
3713 // Fold bit_convert nodes from a type to themselves.
3714 if (N1.getValueType() == VT)
3719 // Memoize node if it doesn't produce a flag.
3721 SDVTList VTs = getVTList(VT);
3722 if (VT != MVT::Glue) {
3723 SDValue Ops[] = { N1, N2, N3 };
3724 FoldingSetNodeID ID;
3725 AddNodeIDNode(ID, Opcode, VTs, Ops);
3727 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3728 return SDValue(E, 0);
3730 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3731 DL.getDebugLoc(), VTs, N1, N2, N3);
3732 CSEMap.InsertNode(N, IP);
3734 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3735 DL.getDebugLoc(), VTs, N1, N2, N3);
3739 return SDValue(N, 0);
3742 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3743 SDValue N1, SDValue N2, SDValue N3,
3745 SDValue Ops[] = { N1, N2, N3, N4 };
3746 return getNode(Opcode, DL, VT, Ops);
3749 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3750 SDValue N1, SDValue N2, SDValue N3,
3751 SDValue N4, SDValue N5) {
3752 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3753 return getNode(Opcode, DL, VT, Ops);
3756 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3757 /// the incoming stack arguments to be loaded from the stack.
3758 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3759 SmallVector<SDValue, 8> ArgChains;
3761 // Include the original chain at the beginning of the list. When this is
3762 // used by target LowerCall hooks, this helps legalize find the
3763 // CALLSEQ_BEGIN node.
3764 ArgChains.push_back(Chain);
3766 // Add a chain value for each stack argument.
3767 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3768 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3769 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3770 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3771 if (FI->getIndex() < 0)
3772 ArgChains.push_back(SDValue(L, 1));
3774 // Build a tokenfactor for all the chains.
3775 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3778 /// getMemsetValue - Vectorized representation of the memset value
3780 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3782 assert(Value.getOpcode() != ISD::UNDEF);
3784 unsigned NumBits = VT.getScalarType().getSizeInBits();
3785 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3786 assert(C->getAPIntValue().getBitWidth() == 8);
3787 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3789 return DAG.getConstant(Val, VT);
3790 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3793 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3795 // Use a multiplication with 0x010101... to extend the input to the
3797 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3798 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3804 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3805 /// used when a memcpy is turned into a memset when the source is a constant
3807 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3808 const TargetLowering &TLI, StringRef Str) {
3809 // Handle vector with all elements zero.
3812 return DAG.getConstant(0, VT);
3813 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3814 return DAG.getConstantFP(0.0, VT);
3815 else if (VT.isVector()) {
3816 unsigned NumElts = VT.getVectorNumElements();
3817 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3818 return DAG.getNode(ISD::BITCAST, dl, VT,
3819 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3822 llvm_unreachable("Expected type!");
3825 assert(!VT.isVector() && "Can't handle vector type here!");
3826 unsigned NumVTBits = VT.getSizeInBits();
3827 unsigned NumVTBytes = NumVTBits / 8;
3828 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3830 APInt Val(NumVTBits, 0);
3831 if (TLI.isLittleEndian()) {
3832 for (unsigned i = 0; i != NumBytes; ++i)
3833 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3835 for (unsigned i = 0; i != NumBytes; ++i)
3836 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3839 // If the "cost" of materializing the integer immediate is less than the cost
3840 // of a load, then it is cost effective to turn the load into the immediate.
3841 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3842 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3843 return DAG.getConstant(Val, VT);
3844 return SDValue(nullptr, 0);
3847 /// getMemBasePlusOffset - Returns base and offset node for the
3849 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3850 SelectionDAG &DAG) {
3851 EVT VT = Base.getValueType();
3852 return DAG.getNode(ISD::ADD, dl,
3853 VT, Base, DAG.getConstant(Offset, VT));
3856 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3858 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3859 unsigned SrcDelta = 0;
3860 GlobalAddressSDNode *G = nullptr;
3861 if (Src.getOpcode() == ISD::GlobalAddress)
3862 G = cast<GlobalAddressSDNode>(Src);
3863 else if (Src.getOpcode() == ISD::ADD &&
3864 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3865 Src.getOperand(1).getOpcode() == ISD::Constant) {
3866 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3867 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3872 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3875 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3876 /// to replace the memset / memcpy. Return true if the number of memory ops
3877 /// is below the threshold. It returns the types of the sequence of
3878 /// memory ops to perform memset / memcpy by reference.
3879 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3880 unsigned Limit, uint64_t Size,
3881 unsigned DstAlign, unsigned SrcAlign,
3887 const TargetLowering &TLI) {
3888 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3889 "Expecting memcpy / memset source to meet alignment requirement!");
3890 // If 'SrcAlign' is zero, that means the memory operation does not need to
3891 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3892 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3893 // is the specified alignment of the memory operation. If it is zero, that
3894 // means it's possible to change the alignment of the destination.
3895 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3896 // not need to be loaded.
3897 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3898 IsMemset, ZeroMemset, MemcpyStrSrc,
3899 DAG.getMachineFunction());
3901 if (VT == MVT::Other) {
3903 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3904 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3905 VT = TLI.getPointerTy();
3907 switch (DstAlign & 7) {
3908 case 0: VT = MVT::i64; break;
3909 case 4: VT = MVT::i32; break;
3910 case 2: VT = MVT::i16; break;
3911 default: VT = MVT::i8; break;
3916 while (!TLI.isTypeLegal(LVT))
3917 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3918 assert(LVT.isInteger());
3924 unsigned NumMemOps = 0;
3926 unsigned VTSize = VT.getSizeInBits() / 8;
3927 while (VTSize > Size) {
3928 // For now, only use non-vector load / store's for the left-over pieces.
3933 if (VT.isVector() || VT.isFloatingPoint()) {
3934 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3935 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3936 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3938 else if (NewVT == MVT::i64 &&
3939 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3940 TLI.isSafeMemOpType(MVT::f64)) {
3941 // i64 is usually not legal on 32-bit targets, but f64 may be.
3949 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3950 if (NewVT == MVT::i8)
3952 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3954 NewVTSize = NewVT.getSizeInBits() / 8;
3956 // If the new VT cannot cover all of the remaining bits, then consider
3957 // issuing a (or a pair of) unaligned and overlapping load / store.
3958 // FIXME: Only does this for 64-bit or more since we don't have proper
3959 // cost model for unaligned load / store.
3962 if (NumMemOps && AllowOverlap &&
3963 VTSize >= 8 && NewVTSize < Size &&
3964 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3972 if (++NumMemOps > Limit)
3975 MemOps.push_back(VT);
3982 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3983 SDValue Chain, SDValue Dst,
3984 SDValue Src, uint64_t Size,
3985 unsigned Align, bool isVol,
3987 MachinePointerInfo DstPtrInfo,
3988 MachinePointerInfo SrcPtrInfo) {
3989 // Turn a memcpy of undef to nop.
3990 if (Src.getOpcode() == ISD::UNDEF)
3993 // Expand memcpy to a series of load and store ops if the size operand falls
3994 // below a certain threshold.
3995 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3996 // rather than maybe a humongous number of loads and stores.
3997 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3998 std::vector<EVT> MemOps;
3999 bool DstAlignCanChange = false;
4000 MachineFunction &MF = DAG.getMachineFunction();
4001 MachineFrameInfo *MFI = MF.getFrameInfo();
4002 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4003 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4004 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4005 DstAlignCanChange = true;
4006 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4007 if (Align > SrcAlign)
4010 bool CopyFromStr = isMemSrcFromString(Src, Str);
4011 bool isZeroStr = CopyFromStr && Str.empty();
4012 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4014 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4015 (DstAlignCanChange ? 0 : Align),
4016 (isZeroStr ? 0 : SrcAlign),
4017 false, false, CopyFromStr, true, DAG, TLI))
4020 if (DstAlignCanChange) {
4021 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4022 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4024 // Don't promote to an alignment that would require dynamic stack
4026 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4027 if (!TRI->needsStackRealignment(MF))
4028 while (NewAlign > Align &&
4029 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4032 if (NewAlign > Align) {
4033 // Give the stack frame object a larger alignment if needed.
4034 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4035 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4040 SmallVector<SDValue, 8> OutChains;
4041 unsigned NumMemOps = MemOps.size();
4042 uint64_t SrcOff = 0, DstOff = 0;
4043 for (unsigned i = 0; i != NumMemOps; ++i) {
4045 unsigned VTSize = VT.getSizeInBits() / 8;
4046 SDValue Value, Store;
4048 if (VTSize > Size) {
4049 // Issuing an unaligned load / store pair that overlaps with the previous
4050 // pair. Adjust the offset accordingly.
4051 assert(i == NumMemOps-1 && i != 0);
4052 SrcOff -= VTSize - Size;
4053 DstOff -= VTSize - Size;
4057 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4058 // It's unlikely a store of a vector immediate can be done in a single
4059 // instruction. It would require a load from a constantpool first.
4060 // We only handle zero vectors here.
4061 // FIXME: Handle other cases where store of vector immediate is done in
4062 // a single instruction.
4063 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4064 if (Value.getNode())
4065 Store = DAG.getStore(Chain, dl, Value,
4066 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4067 DstPtrInfo.getWithOffset(DstOff), isVol,
4071 if (!Store.getNode()) {
4072 // The type might not be legal for the target. This should only happen
4073 // if the type is smaller than a legal type, as on PPC, so the right
4074 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4075 // to Load/Store if NVT==VT.
4076 // FIXME does the case above also need this?
4077 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4078 assert(NVT.bitsGE(VT));
4079 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4080 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4081 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4082 false, MinAlign(SrcAlign, SrcOff));
4083 Store = DAG.getTruncStore(Chain, dl, Value,
4084 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4085 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4088 OutChains.push_back(Store);
4094 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4097 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4098 SDValue Chain, SDValue Dst,
4099 SDValue Src, uint64_t Size,
4100 unsigned Align, bool isVol,
4102 MachinePointerInfo DstPtrInfo,
4103 MachinePointerInfo SrcPtrInfo) {
4104 // Turn a memmove of undef to nop.
4105 if (Src.getOpcode() == ISD::UNDEF)
4108 // Expand memmove to a series of load and store ops if the size operand falls
4109 // below a certain threshold.
4110 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4111 std::vector<EVT> MemOps;
4112 bool DstAlignCanChange = false;
4113 MachineFunction &MF = DAG.getMachineFunction();
4114 MachineFrameInfo *MFI = MF.getFrameInfo();
4115 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4116 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4117 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4118 DstAlignCanChange = true;
4119 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4120 if (Align > SrcAlign)
4122 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4124 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4125 (DstAlignCanChange ? 0 : Align), SrcAlign,
4126 false, false, false, false, DAG, TLI))
4129 if (DstAlignCanChange) {
4130 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4131 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4132 if (NewAlign > Align) {
4133 // Give the stack frame object a larger alignment if needed.
4134 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4135 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4140 uint64_t SrcOff = 0, DstOff = 0;
4141 SmallVector<SDValue, 8> LoadValues;
4142 SmallVector<SDValue, 8> LoadChains;
4143 SmallVector<SDValue, 8> OutChains;
4144 unsigned NumMemOps = MemOps.size();
4145 for (unsigned i = 0; i < NumMemOps; i++) {
4147 unsigned VTSize = VT.getSizeInBits() / 8;
4150 Value = DAG.getLoad(VT, dl, Chain,
4151 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4152 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4153 false, false, SrcAlign);
4154 LoadValues.push_back(Value);
4155 LoadChains.push_back(Value.getValue(1));
4158 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4160 for (unsigned i = 0; i < NumMemOps; i++) {
4162 unsigned VTSize = VT.getSizeInBits() / 8;
4165 Store = DAG.getStore(Chain, dl, LoadValues[i],
4166 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4167 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4168 OutChains.push_back(Store);
4172 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4175 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4178 /// \param DAG Selection DAG where lowered code is placed.
4179 /// \param dl Link to corresponding IR location.
4180 /// \param Chain Control flow dependency.
4181 /// \param Dst Pointer to destination memory location.
4182 /// \param Src Value of byte to write into the memory.
4183 /// \param Size Number of bytes to write.
4184 /// \param Align Alignment of the destination in bytes.
4185 /// \param isVol True if destination is volatile.
4186 /// \param DstPtrInfo IR information on the memory pointer.
4187 /// \returns New head in the control flow, if lowering was successful, empty
4188 /// SDValue otherwise.
4190 /// The function tries to replace 'llvm.memset' intrinsic with several store
4191 /// operations and value calculation code. This is usually profitable for small
4193 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4194 SDValue Chain, SDValue Dst,
4195 SDValue Src, uint64_t Size,
4196 unsigned Align, bool isVol,
4197 MachinePointerInfo DstPtrInfo) {
4198 // Turn a memset of undef to nop.
4199 if (Src.getOpcode() == ISD::UNDEF)
4202 // Expand memset to a series of load/store ops if the size operand
4203 // falls below a certain threshold.
4204 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4205 std::vector<EVT> MemOps;
4206 bool DstAlignCanChange = false;
4207 MachineFunction &MF = DAG.getMachineFunction();
4208 MachineFrameInfo *MFI = MF.getFrameInfo();
4209 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4210 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4211 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4212 DstAlignCanChange = true;
4214 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4215 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4216 Size, (DstAlignCanChange ? 0 : Align), 0,
4217 true, IsZeroVal, false, true, DAG, TLI))
4220 if (DstAlignCanChange) {
4221 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4222 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4223 if (NewAlign > Align) {
4224 // Give the stack frame object a larger alignment if needed.
4225 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4226 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4231 SmallVector<SDValue, 8> OutChains;
4232 uint64_t DstOff = 0;
4233 unsigned NumMemOps = MemOps.size();
4235 // Find the largest store and generate the bit pattern for it.
4236 EVT LargestVT = MemOps[0];
4237 for (unsigned i = 1; i < NumMemOps; i++)
4238 if (MemOps[i].bitsGT(LargestVT))
4239 LargestVT = MemOps[i];
4240 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4242 for (unsigned i = 0; i < NumMemOps; i++) {
4244 unsigned VTSize = VT.getSizeInBits() / 8;
4245 if (VTSize > Size) {
4246 // Issuing an unaligned load / store pair that overlaps with the previous
4247 // pair. Adjust the offset accordingly.
4248 assert(i == NumMemOps-1 && i != 0);
4249 DstOff -= VTSize - Size;
4252 // If this store is smaller than the largest store see whether we can get
4253 // the smaller value for free with a truncate.
4254 SDValue Value = MemSetValue;
4255 if (VT.bitsLT(LargestVT)) {
4256 if (!LargestVT.isVector() && !VT.isVector() &&
4257 TLI.isTruncateFree(LargestVT, VT))
4258 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4260 Value = getMemsetValue(Src, VT, DAG, dl);
4262 assert(Value.getValueType() == VT && "Value with wrong type.");
4263 SDValue Store = DAG.getStore(Chain, dl, Value,
4264 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4265 DstPtrInfo.getWithOffset(DstOff),
4266 isVol, false, Align);
4267 OutChains.push_back(Store);
4268 DstOff += VT.getSizeInBits() / 8;
4272 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4275 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4276 SDValue Src, SDValue Size,
4277 unsigned Align, bool isVol, bool AlwaysInline,
4278 MachinePointerInfo DstPtrInfo,
4279 MachinePointerInfo SrcPtrInfo) {
4280 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4282 // Check to see if we should lower the memcpy to loads and stores first.
4283 // For cases within the target-specified limits, this is the best choice.
4284 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4286 // Memcpy with size zero? Just return the original chain.
4287 if (ConstantSize->isNullValue())
4290 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4291 ConstantSize->getZExtValue(),Align,
4292 isVol, false, DstPtrInfo, SrcPtrInfo);
4293 if (Result.getNode())
4297 // Then check to see if we should lower the memcpy with target-specific
4298 // code. If the target chooses to do this, this is the next best.
4300 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4301 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4302 DstPtrInfo, SrcPtrInfo);
4303 if (Result.getNode())
4307 // If we really need inline code and the target declined to provide it,
4308 // use a (potentially long) sequence of loads and stores.
4310 assert(ConstantSize && "AlwaysInline requires a constant size!");
4311 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4312 ConstantSize->getZExtValue(), Align, isVol,
4313 true, DstPtrInfo, SrcPtrInfo);
4316 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4317 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4318 // respect volatile, so they may do things like read or write memory
4319 // beyond the given memory regions. But fixing this isn't easy, and most
4320 // people don't care.
4322 // Emit a library call.
4323 TargetLowering::ArgListTy Args;
4324 TargetLowering::ArgListEntry Entry;
4325 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4326 Entry.Node = Dst; Args.push_back(Entry);
4327 Entry.Node = Src; Args.push_back(Entry);
4328 Entry.Node = Size; Args.push_back(Entry);
4329 // FIXME: pass in SDLoc
4330 TargetLowering::CallLoweringInfo CLI(*this);
4331 CLI.setDebugLoc(dl).setChain(Chain)
4332 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4333 Type::getVoidTy(*getContext()),
4334 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4335 TLI->getPointerTy()), std::move(Args), 0)
4336 .setDiscardResult();
4337 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4339 return CallResult.second;
4342 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4343 SDValue Src, SDValue Size,
4344 unsigned Align, bool isVol,
4345 MachinePointerInfo DstPtrInfo,
4346 MachinePointerInfo SrcPtrInfo) {
4347 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4349 // Check to see if we should lower the memmove to loads and stores first.
4350 // For cases within the target-specified limits, this is the best choice.
4351 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4353 // Memmove with size zero? Just return the original chain.
4354 if (ConstantSize->isNullValue())
4358 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4359 ConstantSize->getZExtValue(), Align, isVol,
4360 false, DstPtrInfo, SrcPtrInfo);
4361 if (Result.getNode())
4365 // Then check to see if we should lower the memmove with target-specific
4366 // code. If the target chooses to do this, this is the next best.
4368 SDValue Result = TSI->EmitTargetCodeForMemmove(
4369 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4370 if (Result.getNode())
4374 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4375 // not be safe. See memcpy above for more details.
4377 // Emit a library call.
4378 TargetLowering::ArgListTy Args;
4379 TargetLowering::ArgListEntry Entry;
4380 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4381 Entry.Node = Dst; Args.push_back(Entry);
4382 Entry.Node = Src; Args.push_back(Entry);
4383 Entry.Node = Size; Args.push_back(Entry);
4384 // FIXME: pass in SDLoc
4385 TargetLowering::CallLoweringInfo CLI(*this);
4386 CLI.setDebugLoc(dl).setChain(Chain)
4387 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4388 Type::getVoidTy(*getContext()),
4389 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4390 TLI->getPointerTy()), std::move(Args), 0)
4391 .setDiscardResult();
4392 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4394 return CallResult.second;
4397 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4398 SDValue Src, SDValue Size,
4399 unsigned Align, bool isVol,
4400 MachinePointerInfo DstPtrInfo) {
4401 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4403 // Check to see if we should lower the memset to stores first.
4404 // For cases within the target-specified limits, this is the best choice.
4405 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4407 // Memset with size zero? Just return the original chain.
4408 if (ConstantSize->isNullValue())
4412 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4413 Align, isVol, DstPtrInfo);
4415 if (Result.getNode())
4419 // Then check to see if we should lower the memset with target-specific
4420 // code. If the target chooses to do this, this is the next best.
4422 SDValue Result = TSI->EmitTargetCodeForMemset(
4423 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4424 if (Result.getNode())
4428 // Emit a library call.
4429 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4430 TargetLowering::ArgListTy Args;
4431 TargetLowering::ArgListEntry Entry;
4432 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4433 Args.push_back(Entry);
4435 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4436 Args.push_back(Entry);
4438 Entry.Ty = IntPtrTy;
4439 Args.push_back(Entry);
4441 // FIXME: pass in SDLoc
4442 TargetLowering::CallLoweringInfo CLI(*this);
4443 CLI.setDebugLoc(dl).setChain(Chain)
4444 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4445 Type::getVoidTy(*getContext()),
4446 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4447 TLI->getPointerTy()), std::move(Args), 0)
4448 .setDiscardResult();
4450 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4451 return CallResult.second;
4454 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4455 SDVTList VTList, ArrayRef<SDValue> Ops,
4456 MachineMemOperand *MMO,
4457 AtomicOrdering SuccessOrdering,
4458 AtomicOrdering FailureOrdering,
4459 SynchronizationScope SynchScope) {
4460 FoldingSetNodeID ID;
4461 ID.AddInteger(MemVT.getRawBits());
4462 AddNodeIDNode(ID, Opcode, VTList, Ops);
4463 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4465 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4466 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4467 return SDValue(E, 0);
4470 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4471 // SDNode doesn't have access to it. This memory will be "leaked" when
4472 // the node is deallocated, but recovered when the allocator is released.
4473 // If the number of operands is less than 5 we use AtomicSDNode's internal
4475 unsigned NumOps = Ops.size();
4476 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4479 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4480 dl.getDebugLoc(), VTList, MemVT,
4481 Ops.data(), DynOps, NumOps, MMO,
4482 SuccessOrdering, FailureOrdering,
4484 CSEMap.InsertNode(N, IP);
4486 return SDValue(N, 0);
4489 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4490 SDVTList VTList, ArrayRef<SDValue> Ops,
4491 MachineMemOperand *MMO,
4492 AtomicOrdering Ordering,
4493 SynchronizationScope SynchScope) {
4494 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4495 Ordering, SynchScope);
4498 SDValue SelectionDAG::getAtomicCmpSwap(
4499 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4500 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4501 unsigned Alignment, AtomicOrdering SuccessOrdering,
4502 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4503 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4504 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4505 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4507 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4508 Alignment = getEVTAlignment(MemVT);
4510 MachineFunction &MF = getMachineFunction();
4512 // FIXME: Volatile isn't really correct; we should keep track of atomic
4513 // orderings in the memoperand.
4514 unsigned Flags = MachineMemOperand::MOVolatile;
4515 Flags |= MachineMemOperand::MOLoad;
4516 Flags |= MachineMemOperand::MOStore;
4518 MachineMemOperand *MMO =
4519 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4521 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4522 SuccessOrdering, FailureOrdering, SynchScope);
4525 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4526 SDVTList VTs, SDValue Chain, SDValue Ptr,
4527 SDValue Cmp, SDValue Swp,
4528 MachineMemOperand *MMO,
4529 AtomicOrdering SuccessOrdering,
4530 AtomicOrdering FailureOrdering,
4531 SynchronizationScope SynchScope) {
4532 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4533 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4534 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4536 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4537 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4538 SuccessOrdering, FailureOrdering, SynchScope);
4541 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4543 SDValue Ptr, SDValue Val,
4544 const Value* PtrVal,
4546 AtomicOrdering Ordering,
4547 SynchronizationScope SynchScope) {
4548 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4549 Alignment = getEVTAlignment(MemVT);
4551 MachineFunction &MF = getMachineFunction();
4552 // An atomic store does not load. An atomic load does not store.
4553 // (An atomicrmw obviously both loads and stores.)
4554 // For now, atomics are considered to be volatile always, and they are
4556 // FIXME: Volatile isn't really correct; we should keep track of atomic
4557 // orderings in the memoperand.
4558 unsigned Flags = MachineMemOperand::MOVolatile;
4559 if (Opcode != ISD::ATOMIC_STORE)
4560 Flags |= MachineMemOperand::MOLoad;
4561 if (Opcode != ISD::ATOMIC_LOAD)
4562 Flags |= MachineMemOperand::MOStore;
4564 MachineMemOperand *MMO =
4565 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4566 MemVT.getStoreSize(), Alignment);
4568 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4569 Ordering, SynchScope);
4572 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4574 SDValue Ptr, SDValue Val,
4575 MachineMemOperand *MMO,
4576 AtomicOrdering Ordering,
4577 SynchronizationScope SynchScope) {
4578 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4579 Opcode == ISD::ATOMIC_LOAD_SUB ||
4580 Opcode == ISD::ATOMIC_LOAD_AND ||
4581 Opcode == ISD::ATOMIC_LOAD_OR ||
4582 Opcode == ISD::ATOMIC_LOAD_XOR ||
4583 Opcode == ISD::ATOMIC_LOAD_NAND ||
4584 Opcode == ISD::ATOMIC_LOAD_MIN ||
4585 Opcode == ISD::ATOMIC_LOAD_MAX ||
4586 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4587 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4588 Opcode == ISD::ATOMIC_SWAP ||
4589 Opcode == ISD::ATOMIC_STORE) &&
4590 "Invalid Atomic Op");
4592 EVT VT = Val.getValueType();
4594 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4595 getVTList(VT, MVT::Other);
4596 SDValue Ops[] = {Chain, Ptr, Val};
4597 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4600 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4601 EVT VT, SDValue Chain,
4603 MachineMemOperand *MMO,
4604 AtomicOrdering Ordering,
4605 SynchronizationScope SynchScope) {
4606 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4608 SDVTList VTs = getVTList(VT, MVT::Other);
4609 SDValue Ops[] = {Chain, Ptr};
4610 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4613 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4614 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4615 if (Ops.size() == 1)
4618 SmallVector<EVT, 4> VTs;
4619 VTs.reserve(Ops.size());
4620 for (unsigned i = 0; i < Ops.size(); ++i)
4621 VTs.push_back(Ops[i].getValueType());
4622 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4626 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4627 ArrayRef<SDValue> Ops,
4628 EVT MemVT, MachinePointerInfo PtrInfo,
4629 unsigned Align, bool Vol,
4630 bool ReadMem, bool WriteMem, unsigned Size) {
4631 if (Align == 0) // Ensure that codegen never sees alignment 0
4632 Align = getEVTAlignment(MemVT);
4634 MachineFunction &MF = getMachineFunction();
4637 Flags |= MachineMemOperand::MOStore;
4639 Flags |= MachineMemOperand::MOLoad;
4641 Flags |= MachineMemOperand::MOVolatile;
4643 Size = MemVT.getStoreSize();
4644 MachineMemOperand *MMO =
4645 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4647 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4651 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4652 ArrayRef<SDValue> Ops, EVT MemVT,
4653 MachineMemOperand *MMO) {
4654 assert((Opcode == ISD::INTRINSIC_VOID ||
4655 Opcode == ISD::INTRINSIC_W_CHAIN ||
4656 Opcode == ISD::PREFETCH ||
4657 Opcode == ISD::LIFETIME_START ||
4658 Opcode == ISD::LIFETIME_END ||
4659 (Opcode <= INT_MAX &&
4660 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4661 "Opcode is not a memory-accessing opcode!");
4663 // Memoize the node unless it returns a flag.
4664 MemIntrinsicSDNode *N;
4665 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4666 FoldingSetNodeID ID;
4667 AddNodeIDNode(ID, Opcode, VTList, Ops);
4668 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4670 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4671 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4672 return SDValue(E, 0);
4675 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4676 dl.getDebugLoc(), VTList, Ops,
4678 CSEMap.InsertNode(N, IP);
4680 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4681 dl.getDebugLoc(), VTList, Ops,
4685 return SDValue(N, 0);
4688 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4689 /// MachinePointerInfo record from it. This is particularly useful because the
4690 /// code generator has many cases where it doesn't bother passing in a
4691 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4692 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4693 // If this is FI+Offset, we can model it.
4694 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4695 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4697 // If this is (FI+Offset1)+Offset2, we can model it.
4698 if (Ptr.getOpcode() != ISD::ADD ||
4699 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4700 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4701 return MachinePointerInfo();
4703 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4704 return MachinePointerInfo::getFixedStack(FI, Offset+
4705 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4708 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4709 /// MachinePointerInfo record from it. This is particularly useful because the
4710 /// code generator has many cases where it doesn't bother passing in a
4711 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4712 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4713 // If the 'Offset' value isn't a constant, we can't handle this.
4714 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4715 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4716 if (OffsetOp.getOpcode() == ISD::UNDEF)
4717 return InferPointerInfo(Ptr);
4718 return MachinePointerInfo();
4723 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4724 EVT VT, SDLoc dl, SDValue Chain,
4725 SDValue Ptr, SDValue Offset,
4726 MachinePointerInfo PtrInfo, EVT MemVT,
4727 bool isVolatile, bool isNonTemporal, bool isInvariant,
4728 unsigned Alignment, const AAMDNodes &AAInfo,
4729 const MDNode *Ranges) {
4730 assert(Chain.getValueType() == MVT::Other &&
4731 "Invalid chain type");
4732 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4733 Alignment = getEVTAlignment(VT);
4735 unsigned Flags = MachineMemOperand::MOLoad;
4737 Flags |= MachineMemOperand::MOVolatile;
4739 Flags |= MachineMemOperand::MONonTemporal;
4741 Flags |= MachineMemOperand::MOInvariant;
4743 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4745 if (PtrInfo.V.isNull())
4746 PtrInfo = InferPointerInfo(Ptr, Offset);
4748 MachineFunction &MF = getMachineFunction();
4749 MachineMemOperand *MMO =
4750 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4752 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4756 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4757 EVT VT, SDLoc dl, SDValue Chain,
4758 SDValue Ptr, SDValue Offset, EVT MemVT,
4759 MachineMemOperand *MMO) {
4761 ExtType = ISD::NON_EXTLOAD;
4762 } else if (ExtType == ISD::NON_EXTLOAD) {
4763 assert(VT == MemVT && "Non-extending load from different memory type!");
4766 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4767 "Should only be an extending load, not truncating!");
4768 assert(VT.isInteger() == MemVT.isInteger() &&
4769 "Cannot convert from FP to Int or Int -> FP!");
4770 assert(VT.isVector() == MemVT.isVector() &&
4771 "Cannot use an ext load to convert to or from a vector!");
4772 assert((!VT.isVector() ||
4773 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4774 "Cannot use an ext load to change the number of vector elements!");
4777 bool Indexed = AM != ISD::UNINDEXED;
4778 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4779 "Unindexed load with an offset!");
4781 SDVTList VTs = Indexed ?
4782 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4783 SDValue Ops[] = { Chain, Ptr, Offset };
4784 FoldingSetNodeID ID;
4785 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4786 ID.AddInteger(MemVT.getRawBits());
4787 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4788 MMO->isNonTemporal(),
4789 MMO->isInvariant()));
4790 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4792 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4793 cast<LoadSDNode>(E)->refineAlignment(MMO);
4794 return SDValue(E, 0);
4796 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4797 dl.getDebugLoc(), VTs, AM, ExtType,
4799 CSEMap.InsertNode(N, IP);
4801 return SDValue(N, 0);
4804 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4805 SDValue Chain, SDValue Ptr,
4806 MachinePointerInfo PtrInfo,
4807 bool isVolatile, bool isNonTemporal,
4808 bool isInvariant, unsigned Alignment,
4809 const AAMDNodes &AAInfo,
4810 const MDNode *Ranges) {
4811 SDValue Undef = getUNDEF(Ptr.getValueType());
4812 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4813 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4817 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4818 SDValue Chain, SDValue Ptr,
4819 MachineMemOperand *MMO) {
4820 SDValue Undef = getUNDEF(Ptr.getValueType());
4821 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4825 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4826 SDValue Chain, SDValue Ptr,
4827 MachinePointerInfo PtrInfo, EVT MemVT,
4828 bool isVolatile, bool isNonTemporal,
4829 bool isInvariant, unsigned Alignment,
4830 const AAMDNodes &AAInfo) {
4831 SDValue Undef = getUNDEF(Ptr.getValueType());
4832 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4833 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4838 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4839 SDValue Chain, SDValue Ptr, EVT MemVT,
4840 MachineMemOperand *MMO) {
4841 SDValue Undef = getUNDEF(Ptr.getValueType());
4842 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4847 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4848 SDValue Offset, ISD::MemIndexedMode AM) {
4849 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4850 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4851 "Load is already a indexed load!");
4852 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4853 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4854 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4855 false, LD->getAlignment());
4858 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4859 SDValue Ptr, MachinePointerInfo PtrInfo,
4860 bool isVolatile, bool isNonTemporal,
4861 unsigned Alignment, const AAMDNodes &AAInfo) {
4862 assert(Chain.getValueType() == MVT::Other &&
4863 "Invalid chain type");
4864 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4865 Alignment = getEVTAlignment(Val.getValueType());
4867 unsigned Flags = MachineMemOperand::MOStore;
4869 Flags |= MachineMemOperand::MOVolatile;
4871 Flags |= MachineMemOperand::MONonTemporal;
4873 if (PtrInfo.V.isNull())
4874 PtrInfo = InferPointerInfo(Ptr);
4876 MachineFunction &MF = getMachineFunction();
4877 MachineMemOperand *MMO =
4878 MF.getMachineMemOperand(PtrInfo, Flags,
4879 Val.getValueType().getStoreSize(), Alignment,
4882 return getStore(Chain, dl, Val, Ptr, MMO);
4885 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4886 SDValue Ptr, MachineMemOperand *MMO) {
4887 assert(Chain.getValueType() == MVT::Other &&
4888 "Invalid chain type");
4889 EVT VT = Val.getValueType();
4890 SDVTList VTs = getVTList(MVT::Other);
4891 SDValue Undef = getUNDEF(Ptr.getValueType());
4892 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4893 FoldingSetNodeID ID;
4894 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4895 ID.AddInteger(VT.getRawBits());
4896 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4897 MMO->isNonTemporal(), MMO->isInvariant()));
4898 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4900 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4901 cast<StoreSDNode>(E)->refineAlignment(MMO);
4902 return SDValue(E, 0);
4904 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4905 dl.getDebugLoc(), VTs,
4906 ISD::UNINDEXED, false, VT, MMO);
4907 CSEMap.InsertNode(N, IP);
4909 return SDValue(N, 0);
4912 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4913 SDValue Ptr, MachinePointerInfo PtrInfo,
4914 EVT SVT,bool isVolatile, bool isNonTemporal,
4916 const AAMDNodes &AAInfo) {
4917 assert(Chain.getValueType() == MVT::Other &&
4918 "Invalid chain type");
4919 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4920 Alignment = getEVTAlignment(SVT);
4922 unsigned Flags = MachineMemOperand::MOStore;
4924 Flags |= MachineMemOperand::MOVolatile;
4926 Flags |= MachineMemOperand::MONonTemporal;
4928 if (PtrInfo.V.isNull())
4929 PtrInfo = InferPointerInfo(Ptr);
4931 MachineFunction &MF = getMachineFunction();
4932 MachineMemOperand *MMO =
4933 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4936 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4939 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4940 SDValue Ptr, EVT SVT,
4941 MachineMemOperand *MMO) {
4942 EVT VT = Val.getValueType();
4944 assert(Chain.getValueType() == MVT::Other &&
4945 "Invalid chain type");
4947 return getStore(Chain, dl, Val, Ptr, MMO);
4949 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4950 "Should only be a truncating store, not extending!");
4951 assert(VT.isInteger() == SVT.isInteger() &&
4952 "Can't do FP-INT conversion!");
4953 assert(VT.isVector() == SVT.isVector() &&
4954 "Cannot use trunc store to convert to or from a vector!");
4955 assert((!VT.isVector() ||
4956 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4957 "Cannot use trunc store to change the number of vector elements!");
4959 SDVTList VTs = getVTList(MVT::Other);
4960 SDValue Undef = getUNDEF(Ptr.getValueType());
4961 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4962 FoldingSetNodeID ID;
4963 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4964 ID.AddInteger(SVT.getRawBits());
4965 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4966 MMO->isNonTemporal(), MMO->isInvariant()));
4967 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4969 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4970 cast<StoreSDNode>(E)->refineAlignment(MMO);
4971 return SDValue(E, 0);
4973 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4974 dl.getDebugLoc(), VTs,
4975 ISD::UNINDEXED, true, SVT, MMO);
4976 CSEMap.InsertNode(N, IP);
4978 return SDValue(N, 0);
4982 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4983 SDValue Offset, ISD::MemIndexedMode AM) {
4984 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4985 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4986 "Store is already a indexed store!");
4987 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4988 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4989 FoldingSetNodeID ID;
4990 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4991 ID.AddInteger(ST->getMemoryVT().getRawBits());
4992 ID.AddInteger(ST->getRawSubclassData());
4993 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4995 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4996 return SDValue(E, 0);
4998 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4999 dl.getDebugLoc(), VTs, AM,
5000 ST->isTruncatingStore(),
5002 ST->getMemOperand());
5003 CSEMap.InsertNode(N, IP);
5005 return SDValue(N, 0);
5009 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5010 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5011 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5013 SDVTList VTs = getVTList(VT, MVT::Other);
5014 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5015 FoldingSetNodeID ID;
5016 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5017 ID.AddInteger(VT.getRawBits());
5018 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5020 MMO->isNonTemporal(),
5021 MMO->isInvariant()));
5022 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5024 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5025 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5026 return SDValue(E, 0);
5028 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5029 dl.getDebugLoc(), Ops, 4, VTs,
5031 CSEMap.InsertNode(N, IP);
5033 return SDValue(N, 0);
5036 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5037 SDValue Ptr, SDValue Mask, EVT MemVT,
5038 MachineMemOperand *MMO, bool isTrunc) {
5039 assert(Chain.getValueType() == MVT::Other &&
5040 "Invalid chain type");
5041 EVT VT = Val.getValueType();
5042 SDVTList VTs = getVTList(MVT::Other);
5043 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5044 FoldingSetNodeID ID;
5045 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5046 ID.AddInteger(VT.getRawBits());
5047 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5048 MMO->isNonTemporal(), MMO->isInvariant()));
5049 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5051 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5052 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5053 return SDValue(E, 0);
5055 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5056 dl.getDebugLoc(), Ops, 4,
5057 VTs, isTrunc, MemVT, MMO);
5058 CSEMap.InsertNode(N, IP);
5060 return SDValue(N, 0);
5063 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5064 SDValue Chain, SDValue Ptr,
5067 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5068 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5071 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5072 ArrayRef<SDUse> Ops) {
5073 switch (Ops.size()) {
5074 case 0: return getNode(Opcode, DL, VT);
5075 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5076 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5077 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5081 // Copy from an SDUse array into an SDValue array for use with
5082 // the regular getNode logic.
5083 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5084 return getNode(Opcode, DL, VT, NewOps);
5087 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5088 ArrayRef<SDValue> Ops) {
5089 unsigned NumOps = Ops.size();
5091 case 0: return getNode(Opcode, DL, VT);
5092 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5093 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5094 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5100 case ISD::SELECT_CC: {
5101 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5102 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5103 "LHS and RHS of condition must have same type!");
5104 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5105 "True and False arms of SelectCC must have same type!");
5106 assert(Ops[2].getValueType() == VT &&
5107 "select_cc node must be of same type as true and false value!");
5111 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5112 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5113 "LHS/RHS of comparison should match types!");
5120 SDVTList VTs = getVTList(VT);
5122 if (VT != MVT::Glue) {
5123 FoldingSetNodeID ID;
5124 AddNodeIDNode(ID, Opcode, VTs, Ops);
5127 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5128 return SDValue(E, 0);
5130 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5132 CSEMap.InsertNode(N, IP);
5134 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5139 return SDValue(N, 0);
5142 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5143 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5144 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5147 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5148 ArrayRef<SDValue> Ops) {
5149 if (VTList.NumVTs == 1)
5150 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5154 // FIXME: figure out how to safely handle things like
5155 // int foo(int x) { return 1 << (x & 255); }
5156 // int bar() { return foo(256); }
5157 case ISD::SRA_PARTS:
5158 case ISD::SRL_PARTS:
5159 case ISD::SHL_PARTS:
5160 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5161 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5162 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5163 else if (N3.getOpcode() == ISD::AND)
5164 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5165 // If the and is only masking out bits that cannot effect the shift,
5166 // eliminate the and.
5167 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5168 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5169 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5175 // Memoize the node unless it returns a flag.
5177 unsigned NumOps = Ops.size();
5178 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5179 FoldingSetNodeID ID;
5180 AddNodeIDNode(ID, Opcode, VTList, Ops);
5182 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5183 return SDValue(E, 0);
5186 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5187 DL.getDebugLoc(), VTList, Ops[0]);
5188 } else if (NumOps == 2) {
5189 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5190 DL.getDebugLoc(), VTList, Ops[0],
5192 } else if (NumOps == 3) {
5193 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5194 DL.getDebugLoc(), VTList, Ops[0],
5197 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5200 CSEMap.InsertNode(N, IP);
5203 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5204 DL.getDebugLoc(), VTList, Ops[0]);
5205 } else if (NumOps == 2) {
5206 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5207 DL.getDebugLoc(), VTList, Ops[0],
5209 } else if (NumOps == 3) {
5210 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5211 DL.getDebugLoc(), VTList, Ops[0],
5214 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5219 return SDValue(N, 0);
5222 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5223 return getNode(Opcode, DL, VTList, None);
5226 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5228 SDValue Ops[] = { N1 };
5229 return getNode(Opcode, DL, VTList, Ops);
5232 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5233 SDValue N1, SDValue N2) {
5234 SDValue Ops[] = { N1, N2 };
5235 return getNode(Opcode, DL, VTList, Ops);
5238 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5239 SDValue N1, SDValue N2, SDValue N3) {
5240 SDValue Ops[] = { N1, N2, N3 };
5241 return getNode(Opcode, DL, VTList, Ops);
5244 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5245 SDValue N1, SDValue N2, SDValue N3,
5247 SDValue Ops[] = { N1, N2, N3, N4 };
5248 return getNode(Opcode, DL, VTList, Ops);
5251 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5252 SDValue N1, SDValue N2, SDValue N3,
5253 SDValue N4, SDValue N5) {
5254 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5255 return getNode(Opcode, DL, VTList, Ops);
5258 SDVTList SelectionDAG::getVTList(EVT VT) {
5259 return makeVTList(SDNode::getValueTypeList(VT), 1);
5262 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5263 FoldingSetNodeID ID;
5265 ID.AddInteger(VT1.getRawBits());
5266 ID.AddInteger(VT2.getRawBits());
5269 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5271 EVT *Array = Allocator.Allocate<EVT>(2);
5274 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5275 VTListMap.InsertNode(Result, IP);
5277 return Result->getSDVTList();
5280 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5281 FoldingSetNodeID ID;
5283 ID.AddInteger(VT1.getRawBits());
5284 ID.AddInteger(VT2.getRawBits());
5285 ID.AddInteger(VT3.getRawBits());
5288 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5290 EVT *Array = Allocator.Allocate<EVT>(3);
5294 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5295 VTListMap.InsertNode(Result, IP);
5297 return Result->getSDVTList();
5300 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5301 FoldingSetNodeID ID;
5303 ID.AddInteger(VT1.getRawBits());
5304 ID.AddInteger(VT2.getRawBits());
5305 ID.AddInteger(VT3.getRawBits());
5306 ID.AddInteger(VT4.getRawBits());
5309 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5311 EVT *Array = Allocator.Allocate<EVT>(4);
5316 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5317 VTListMap.InsertNode(Result, IP);
5319 return Result->getSDVTList();
5322 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5323 unsigned NumVTs = VTs.size();
5324 FoldingSetNodeID ID;
5325 ID.AddInteger(NumVTs);
5326 for (unsigned index = 0; index < NumVTs; index++) {
5327 ID.AddInteger(VTs[index].getRawBits());
5331 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5333 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5334 std::copy(VTs.begin(), VTs.end(), Array);
5335 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5336 VTListMap.InsertNode(Result, IP);
5338 return Result->getSDVTList();
5342 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5343 /// specified operands. If the resultant node already exists in the DAG,
5344 /// this does not modify the specified node, instead it returns the node that
5345 /// already exists. If the resultant node does not exist in the DAG, the
5346 /// input node is returned. As a degenerate case, if you specify the same
5347 /// input operands as the node already has, the input node is returned.
5348 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5349 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5351 // Check to see if there is no change.
5352 if (Op == N->getOperand(0)) return N;
5354 // See if the modified node already exists.
5355 void *InsertPos = nullptr;
5356 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5359 // Nope it doesn't. Remove the node from its current place in the maps.
5361 if (!RemoveNodeFromCSEMaps(N))
5362 InsertPos = nullptr;
5364 // Now we update the operands.
5365 N->OperandList[0].set(Op);
5367 // If this gets put into a CSE map, add it.
5368 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5372 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5373 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5375 // Check to see if there is no change.
5376 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5377 return N; // No operands changed, just return the input node.
5379 // See if the modified node already exists.
5380 void *InsertPos = nullptr;
5381 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5384 // Nope it doesn't. Remove the node from its current place in the maps.
5386 if (!RemoveNodeFromCSEMaps(N))
5387 InsertPos = nullptr;
5389 // Now we update the operands.
5390 if (N->OperandList[0] != Op1)
5391 N->OperandList[0].set(Op1);
5392 if (N->OperandList[1] != Op2)
5393 N->OperandList[1].set(Op2);
5395 // If this gets put into a CSE map, add it.
5396 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5400 SDNode *SelectionDAG::
5401 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5402 SDValue Ops[] = { Op1, Op2, Op3 };
5403 return UpdateNodeOperands(N, Ops);
5406 SDNode *SelectionDAG::
5407 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5408 SDValue Op3, SDValue Op4) {
5409 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5410 return UpdateNodeOperands(N, Ops);
5413 SDNode *SelectionDAG::
5414 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5415 SDValue Op3, SDValue Op4, SDValue Op5) {
5416 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5417 return UpdateNodeOperands(N, Ops);
5420 SDNode *SelectionDAG::
5421 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5422 unsigned NumOps = Ops.size();
5423 assert(N->getNumOperands() == NumOps &&
5424 "Update with wrong number of operands");
5426 // Check to see if there is no change.
5427 bool AnyChange = false;
5428 for (unsigned i = 0; i != NumOps; ++i) {
5429 if (Ops[i] != N->getOperand(i)) {
5435 // No operands changed, just return the input node.
5436 if (!AnyChange) return N;
5438 // See if the modified node already exists.
5439 void *InsertPos = nullptr;
5440 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5443 // Nope it doesn't. Remove the node from its current place in the maps.
5445 if (!RemoveNodeFromCSEMaps(N))
5446 InsertPos = nullptr;
5448 // Now we update the operands.
5449 for (unsigned i = 0; i != NumOps; ++i)
5450 if (N->OperandList[i] != Ops[i])
5451 N->OperandList[i].set(Ops[i]);
5453 // If this gets put into a CSE map, add it.
5454 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5458 /// DropOperands - Release the operands and set this node to have
5460 void SDNode::DropOperands() {
5461 // Unlike the code in MorphNodeTo that does this, we don't need to
5462 // watch for dead nodes here.
5463 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5469 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5472 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5474 SDVTList VTs = getVTList(VT);
5475 return SelectNodeTo(N, MachineOpc, VTs, None);
5478 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5479 EVT VT, SDValue Op1) {
5480 SDVTList VTs = getVTList(VT);
5481 SDValue Ops[] = { Op1 };
5482 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5485 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5486 EVT VT, SDValue Op1,
5488 SDVTList VTs = getVTList(VT);
5489 SDValue Ops[] = { Op1, Op2 };
5490 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5493 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5494 EVT VT, SDValue Op1,
5495 SDValue Op2, SDValue Op3) {
5496 SDVTList VTs = getVTList(VT);
5497 SDValue Ops[] = { Op1, Op2, Op3 };
5498 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5501 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5502 EVT VT, ArrayRef<SDValue> Ops) {
5503 SDVTList VTs = getVTList(VT);
5504 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5507 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5508 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5509 SDVTList VTs = getVTList(VT1, VT2);
5510 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5513 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5515 SDVTList VTs = getVTList(VT1, VT2);
5516 return SelectNodeTo(N, MachineOpc, VTs, None);
5519 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5520 EVT VT1, EVT VT2, EVT VT3,
5521 ArrayRef<SDValue> Ops) {
5522 SDVTList VTs = getVTList(VT1, VT2, VT3);
5523 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5526 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5527 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5528 ArrayRef<SDValue> Ops) {
5529 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5530 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5533 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5536 SDVTList VTs = getVTList(VT1, VT2);
5537 SDValue Ops[] = { Op1 };
5538 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5541 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5543 SDValue Op1, SDValue Op2) {
5544 SDVTList VTs = getVTList(VT1, VT2);
5545 SDValue Ops[] = { Op1, Op2 };
5546 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5549 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5551 SDValue Op1, SDValue Op2,
5553 SDVTList VTs = getVTList(VT1, VT2);
5554 SDValue Ops[] = { Op1, Op2, Op3 };
5555 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5558 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5559 EVT VT1, EVT VT2, EVT VT3,
5560 SDValue Op1, SDValue Op2,
5562 SDVTList VTs = getVTList(VT1, VT2, VT3);
5563 SDValue Ops[] = { Op1, Op2, Op3 };
5564 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5567 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5568 SDVTList VTs,ArrayRef<SDValue> Ops) {
5569 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5570 // Reset the NodeID to -1.
5575 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5576 /// the line number information on the merged node since it is not possible to
5577 /// preserve the information that operation is associated with multiple lines.
5578 /// This will make the debugger working better at -O0, were there is a higher
5579 /// probability having other instructions associated with that line.
5581 /// For IROrder, we keep the smaller of the two
5582 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5583 DebugLoc NLoc = N->getDebugLoc();
5584 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5585 (OLoc.getDebugLoc() != NLoc)) {
5586 N->setDebugLoc(DebugLoc());
5588 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5589 N->setIROrder(Order);
5593 /// MorphNodeTo - This *mutates* the specified node to have the specified
5594 /// return type, opcode, and operands.
5596 /// Note that MorphNodeTo returns the resultant node. If there is already a
5597 /// node of the specified opcode and operands, it returns that node instead of
5598 /// the current one. Note that the SDLoc need not be the same.
5600 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5601 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5602 /// node, and because it doesn't require CSE recalculation for any of
5603 /// the node's users.
5605 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5606 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5607 /// the legalizer which maintain worklists that would need to be updated when
5608 /// deleting things.
5609 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5610 SDVTList VTs, ArrayRef<SDValue> Ops) {
5611 unsigned NumOps = Ops.size();
5612 // If an identical node already exists, use it.
5614 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5615 FoldingSetNodeID ID;
5616 AddNodeIDNode(ID, Opc, VTs, Ops);
5617 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5618 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5621 if (!RemoveNodeFromCSEMaps(N))
5624 // Start the morphing.
5626 N->ValueList = VTs.VTs;
5627 N->NumValues = VTs.NumVTs;
5629 // Clear the operands list, updating used nodes to remove this from their
5630 // use list. Keep track of any operands that become dead as a result.
5631 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5632 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5634 SDNode *Used = Use.getNode();
5636 if (Used->use_empty())
5637 DeadNodeSet.insert(Used);
5640 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5641 // Initialize the memory references information.
5642 MN->setMemRefs(nullptr, nullptr);
5643 // If NumOps is larger than the # of operands we can have in a
5644 // MachineSDNode, reallocate the operand list.
5645 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5646 if (MN->OperandsNeedDelete)
5647 delete[] MN->OperandList;
5648 if (NumOps > array_lengthof(MN->LocalOperands))
5649 // We're creating a final node that will live unmorphed for the
5650 // remainder of the current SelectionDAG iteration, so we can allocate
5651 // the operands directly out of a pool with no recycling metadata.
5652 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5653 Ops.data(), NumOps);
5655 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5656 MN->OperandsNeedDelete = false;
5658 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5660 // If NumOps is larger than the # of operands we currently have, reallocate
5661 // the operand list.
5662 if (NumOps > N->NumOperands) {
5663 if (N->OperandsNeedDelete)
5664 delete[] N->OperandList;
5665 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5666 N->OperandsNeedDelete = true;
5668 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5671 // Delete any nodes that are still dead after adding the uses for the
5673 if (!DeadNodeSet.empty()) {
5674 SmallVector<SDNode *, 16> DeadNodes;
5675 for (SDNode *N : DeadNodeSet)
5677 DeadNodes.push_back(N);
5678 RemoveDeadNodes(DeadNodes);
5682 CSEMap.InsertNode(N, IP); // Memoize the new node.
5687 /// getMachineNode - These are used for target selectors to create a new node
5688 /// with specified return type(s), MachineInstr opcode, and operands.
5690 /// Note that getMachineNode returns the resultant node. If there is already a
5691 /// node of the specified opcode and operands, it returns that node instead of
5692 /// the current one.
5694 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5695 SDVTList VTs = getVTList(VT);
5696 return getMachineNode(Opcode, dl, VTs, None);
5700 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5701 SDVTList VTs = getVTList(VT);
5702 SDValue Ops[] = { Op1 };
5703 return getMachineNode(Opcode, dl, VTs, Ops);
5707 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5708 SDValue Op1, SDValue Op2) {
5709 SDVTList VTs = getVTList(VT);
5710 SDValue Ops[] = { Op1, Op2 };
5711 return getMachineNode(Opcode, dl, VTs, Ops);
5715 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5716 SDValue Op1, SDValue Op2, SDValue Op3) {
5717 SDVTList VTs = getVTList(VT);
5718 SDValue Ops[] = { Op1, Op2, Op3 };
5719 return getMachineNode(Opcode, dl, VTs, Ops);
5723 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5724 ArrayRef<SDValue> Ops) {
5725 SDVTList VTs = getVTList(VT);
5726 return getMachineNode(Opcode, dl, VTs, Ops);
5730 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5731 SDVTList VTs = getVTList(VT1, VT2);
5732 return getMachineNode(Opcode, dl, VTs, None);
5736 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5737 EVT VT1, EVT VT2, SDValue Op1) {
5738 SDVTList VTs = getVTList(VT1, VT2);
5739 SDValue Ops[] = { Op1 };
5740 return getMachineNode(Opcode, dl, VTs, Ops);
5744 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5745 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5746 SDVTList VTs = getVTList(VT1, VT2);
5747 SDValue Ops[] = { Op1, Op2 };
5748 return getMachineNode(Opcode, dl, VTs, Ops);
5752 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5753 EVT VT1, EVT VT2, SDValue Op1,
5754 SDValue Op2, SDValue Op3) {
5755 SDVTList VTs = getVTList(VT1, VT2);
5756 SDValue Ops[] = { Op1, Op2, Op3 };
5757 return getMachineNode(Opcode, dl, VTs, Ops);
5761 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5763 ArrayRef<SDValue> Ops) {
5764 SDVTList VTs = getVTList(VT1, VT2);
5765 return getMachineNode(Opcode, dl, VTs, Ops);
5769 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5770 EVT VT1, EVT VT2, EVT VT3,
5771 SDValue Op1, SDValue Op2) {
5772 SDVTList VTs = getVTList(VT1, VT2, VT3);
5773 SDValue Ops[] = { Op1, Op2 };
5774 return getMachineNode(Opcode, dl, VTs, Ops);
5778 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5779 EVT VT1, EVT VT2, EVT VT3,
5780 SDValue Op1, SDValue Op2, SDValue Op3) {
5781 SDVTList VTs = getVTList(VT1, VT2, VT3);
5782 SDValue Ops[] = { Op1, Op2, Op3 };
5783 return getMachineNode(Opcode, dl, VTs, Ops);
5787 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5788 EVT VT1, EVT VT2, EVT VT3,
5789 ArrayRef<SDValue> Ops) {
5790 SDVTList VTs = getVTList(VT1, VT2, VT3);
5791 return getMachineNode(Opcode, dl, VTs, Ops);
5795 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5796 EVT VT2, EVT VT3, EVT VT4,
5797 ArrayRef<SDValue> Ops) {
5798 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5799 return getMachineNode(Opcode, dl, VTs, Ops);
5803 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5804 ArrayRef<EVT> ResultTys,
5805 ArrayRef<SDValue> Ops) {
5806 SDVTList VTs = getVTList(ResultTys);
5807 return getMachineNode(Opcode, dl, VTs, Ops);
5811 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5812 ArrayRef<SDValue> OpsArray) {
5813 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5816 const SDValue *Ops = OpsArray.data();
5817 unsigned NumOps = OpsArray.size();
5820 FoldingSetNodeID ID;
5821 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5823 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5824 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5828 // Allocate a new MachineSDNode.
5829 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5830 DL.getDebugLoc(), VTs);
5832 // Initialize the operands list.
5833 if (NumOps > array_lengthof(N->LocalOperands))
5834 // We're creating a final node that will live unmorphed for the
5835 // remainder of the current SelectionDAG iteration, so we can allocate
5836 // the operands directly out of a pool with no recycling metadata.
5837 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5840 N->InitOperands(N->LocalOperands, Ops, NumOps);
5841 N->OperandsNeedDelete = false;
5844 CSEMap.InsertNode(N, IP);
5850 /// getTargetExtractSubreg - A convenience function for creating
5851 /// TargetOpcode::EXTRACT_SUBREG nodes.
5853 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5855 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5856 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5857 VT, Operand, SRIdxVal);
5858 return SDValue(Subreg, 0);
5861 /// getTargetInsertSubreg - A convenience function for creating
5862 /// TargetOpcode::INSERT_SUBREG nodes.
5864 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5865 SDValue Operand, SDValue Subreg) {
5866 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5867 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5868 VT, Operand, Subreg, SRIdxVal);
5869 return SDValue(Result, 0);
5872 /// getNodeIfExists - Get the specified node if it's already available, or
5873 /// else return NULL.
5874 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5875 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5877 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5878 FoldingSetNodeID ID;
5879 AddNodeIDNode(ID, Opcode, VTList, Ops);
5880 if (isBinOpWithFlags(Opcode))
5881 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5883 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5889 /// getDbgValue - Creates a SDDbgValue node.
5892 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5893 unsigned R, bool IsIndirect, uint64_t Off,
5894 DebugLoc DL, unsigned O) {
5895 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5899 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5900 const Value *C, uint64_t Off,
5901 DebugLoc DL, unsigned O) {
5902 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5906 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5907 unsigned FI, uint64_t Off,
5908 DebugLoc DL, unsigned O) {
5909 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5914 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5915 /// pointed to by a use iterator is deleted, increment the use iterator
5916 /// so that it doesn't dangle.
5918 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5919 SDNode::use_iterator &UI;
5920 SDNode::use_iterator &UE;
5922 void NodeDeleted(SDNode *N, SDNode *E) override {
5923 // Increment the iterator as needed.
5924 while (UI != UE && N == *UI)
5929 RAUWUpdateListener(SelectionDAG &d,
5930 SDNode::use_iterator &ui,
5931 SDNode::use_iterator &ue)
5932 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5937 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5938 /// This can cause recursive merging of nodes in the DAG.
5940 /// This version assumes From has a single result value.
5942 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5943 SDNode *From = FromN.getNode();
5944 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5945 "Cannot replace with this method!");
5946 assert(From != To.getNode() && "Cannot replace uses of with self");
5948 // Iterate over all the existing uses of From. New uses will be added
5949 // to the beginning of the use list, which we avoid visiting.
5950 // This specifically avoids visiting uses of From that arise while the
5951 // replacement is happening, because any such uses would be the result
5952 // of CSE: If an existing node looks like From after one of its operands
5953 // is replaced by To, we don't want to replace of all its users with To
5954 // too. See PR3018 for more info.
5955 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5956 RAUWUpdateListener Listener(*this, UI, UE);
5960 // This node is about to morph, remove its old self from the CSE maps.
5961 RemoveNodeFromCSEMaps(User);
5963 // A user can appear in a use list multiple times, and when this
5964 // happens the uses are usually next to each other in the list.
5965 // To help reduce the number of CSE recomputations, process all
5966 // the uses of this user that we can find this way.
5968 SDUse &Use = UI.getUse();
5971 } while (UI != UE && *UI == User);
5973 // Now that we have modified User, add it back to the CSE maps. If it
5974 // already exists there, recursively merge the results together.
5975 AddModifiedNodeToCSEMaps(User);
5978 // If we just RAUW'd the root, take note.
5979 if (FromN == getRoot())
5983 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5984 /// This can cause recursive merging of nodes in the DAG.
5986 /// This version assumes that for each value of From, there is a
5987 /// corresponding value in To in the same position with the same type.
5989 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5991 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5992 assert((!From->hasAnyUseOfValue(i) ||
5993 From->getValueType(i) == To->getValueType(i)) &&
5994 "Cannot use this version of ReplaceAllUsesWith!");
5997 // Handle the trivial case.
6001 // Iterate over just the existing users of From. See the comments in
6002 // the ReplaceAllUsesWith above.
6003 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6004 RAUWUpdateListener Listener(*this, UI, UE);
6008 // This node is about to morph, remove its old self from the CSE maps.
6009 RemoveNodeFromCSEMaps(User);
6011 // A user can appear in a use list multiple times, and when this
6012 // happens the uses are usually next to each other in the list.
6013 // To help reduce the number of CSE recomputations, process all
6014 // the uses of this user that we can find this way.
6016 SDUse &Use = UI.getUse();
6019 } while (UI != UE && *UI == User);
6021 // Now that we have modified User, add it back to the CSE maps. If it
6022 // already exists there, recursively merge the results together.
6023 AddModifiedNodeToCSEMaps(User);
6026 // If we just RAUW'd the root, take note.
6027 if (From == getRoot().getNode())
6028 setRoot(SDValue(To, getRoot().getResNo()));
6031 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6032 /// This can cause recursive merging of nodes in the DAG.
6034 /// This version can replace From with any result values. To must match the
6035 /// number and types of values returned by From.
6036 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6037 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6038 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6040 // Iterate over just the existing users of From. See the comments in
6041 // the ReplaceAllUsesWith above.
6042 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6043 RAUWUpdateListener Listener(*this, UI, UE);
6047 // This node is about to morph, remove its old self from the CSE maps.
6048 RemoveNodeFromCSEMaps(User);
6050 // A user can appear in a use list multiple times, and when this
6051 // happens the uses are usually next to each other in the list.
6052 // To help reduce the number of CSE recomputations, process all
6053 // the uses of this user that we can find this way.
6055 SDUse &Use = UI.getUse();
6056 const SDValue &ToOp = To[Use.getResNo()];
6059 } while (UI != UE && *UI == User);
6061 // Now that we have modified User, add it back to the CSE maps. If it
6062 // already exists there, recursively merge the results together.
6063 AddModifiedNodeToCSEMaps(User);
6066 // If we just RAUW'd the root, take note.
6067 if (From == getRoot().getNode())
6068 setRoot(SDValue(To[getRoot().getResNo()]));
6071 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6072 /// uses of other values produced by From.getNode() alone. The Deleted
6073 /// vector is handled the same way as for ReplaceAllUsesWith.
6074 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6075 // Handle the really simple, really trivial case efficiently.
6076 if (From == To) return;
6078 // Handle the simple, trivial, case efficiently.
6079 if (From.getNode()->getNumValues() == 1) {
6080 ReplaceAllUsesWith(From, To);
6084 // Iterate over just the existing users of From. See the comments in
6085 // the ReplaceAllUsesWith above.
6086 SDNode::use_iterator UI = From.getNode()->use_begin(),
6087 UE = From.getNode()->use_end();
6088 RAUWUpdateListener Listener(*this, UI, UE);
6091 bool UserRemovedFromCSEMaps = false;
6093 // A user can appear in a use list multiple times, and when this
6094 // happens the uses are usually next to each other in the list.
6095 // To help reduce the number of CSE recomputations, process all
6096 // the uses of this user that we can find this way.
6098 SDUse &Use = UI.getUse();
6100 // Skip uses of different values from the same node.
6101 if (Use.getResNo() != From.getResNo()) {
6106 // If this node hasn't been modified yet, it's still in the CSE maps,
6107 // so remove its old self from the CSE maps.
6108 if (!UserRemovedFromCSEMaps) {
6109 RemoveNodeFromCSEMaps(User);
6110 UserRemovedFromCSEMaps = true;
6115 } while (UI != UE && *UI == User);
6117 // We are iterating over all uses of the From node, so if a use
6118 // doesn't use the specific value, no changes are made.
6119 if (!UserRemovedFromCSEMaps)
6122 // Now that we have modified User, add it back to the CSE maps. If it
6123 // already exists there, recursively merge the results together.
6124 AddModifiedNodeToCSEMaps(User);
6127 // If we just RAUW'd the root, take note.
6128 if (From == getRoot())
6133 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6134 /// to record information about a use.
6141 /// operator< - Sort Memos by User.
6142 bool operator<(const UseMemo &L, const UseMemo &R) {
6143 return (intptr_t)L.User < (intptr_t)R.User;
6147 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6148 /// uses of other values produced by From.getNode() alone. The same value
6149 /// may appear in both the From and To list. The Deleted vector is
6150 /// handled the same way as for ReplaceAllUsesWith.
6151 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6154 // Handle the simple, trivial case efficiently.
6156 return ReplaceAllUsesOfValueWith(*From, *To);
6158 // Read up all the uses and make records of them. This helps
6159 // processing new uses that are introduced during the
6160 // replacement process.
6161 SmallVector<UseMemo, 4> Uses;
6162 for (unsigned i = 0; i != Num; ++i) {
6163 unsigned FromResNo = From[i].getResNo();
6164 SDNode *FromNode = From[i].getNode();
6165 for (SDNode::use_iterator UI = FromNode->use_begin(),
6166 E = FromNode->use_end(); UI != E; ++UI) {
6167 SDUse &Use = UI.getUse();
6168 if (Use.getResNo() == FromResNo) {
6169 UseMemo Memo = { *UI, i, &Use };
6170 Uses.push_back(Memo);
6175 // Sort the uses, so that all the uses from a given User are together.
6176 std::sort(Uses.begin(), Uses.end());
6178 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6179 UseIndex != UseIndexEnd; ) {
6180 // We know that this user uses some value of From. If it is the right
6181 // value, update it.
6182 SDNode *User = Uses[UseIndex].User;
6184 // This node is about to morph, remove its old self from the CSE maps.
6185 RemoveNodeFromCSEMaps(User);
6187 // The Uses array is sorted, so all the uses for a given User
6188 // are next to each other in the list.
6189 // To help reduce the number of CSE recomputations, process all
6190 // the uses of this user that we can find this way.
6192 unsigned i = Uses[UseIndex].Index;
6193 SDUse &Use = *Uses[UseIndex].Use;
6197 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6199 // Now that we have modified User, add it back to the CSE maps. If it
6200 // already exists there, recursively merge the results together.
6201 AddModifiedNodeToCSEMaps(User);
6205 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6206 /// based on their topological order. It returns the maximum id and a vector
6207 /// of the SDNodes* in assigned order by reference.
6208 unsigned SelectionDAG::AssignTopologicalOrder() {
6210 unsigned DAGSize = 0;
6212 // SortedPos tracks the progress of the algorithm. Nodes before it are
6213 // sorted, nodes after it are unsorted. When the algorithm completes
6214 // it is at the end of the list.
6215 allnodes_iterator SortedPos = allnodes_begin();
6217 // Visit all the nodes. Move nodes with no operands to the front of
6218 // the list immediately. Annotate nodes that do have operands with their
6219 // operand count. Before we do this, the Node Id fields of the nodes
6220 // may contain arbitrary values. After, the Node Id fields for nodes
6221 // before SortedPos will contain the topological sort index, and the
6222 // Node Id fields for nodes At SortedPos and after will contain the
6223 // count of outstanding operands.
6224 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6226 checkForCycles(N, this);
6227 unsigned Degree = N->getNumOperands();
6229 // A node with no uses, add it to the result array immediately.
6230 N->setNodeId(DAGSize++);
6231 allnodes_iterator Q = N;
6233 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6234 assert(SortedPos != AllNodes.end() && "Overran node list");
6237 // Temporarily use the Node Id as scratch space for the degree count.
6238 N->setNodeId(Degree);
6242 // Visit all the nodes. As we iterate, move nodes into sorted order,
6243 // such that by the time the end is reached all nodes will be sorted.
6244 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6246 checkForCycles(N, this);
6247 // N is in sorted position, so all its uses have one less operand
6248 // that needs to be sorted.
6249 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6252 unsigned Degree = P->getNodeId();
6253 assert(Degree != 0 && "Invalid node degree");
6256 // All of P's operands are sorted, so P may sorted now.
6257 P->setNodeId(DAGSize++);
6259 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6260 assert(SortedPos != AllNodes.end() && "Overran node list");
6263 // Update P's outstanding operand count.
6264 P->setNodeId(Degree);
6267 if (I == SortedPos) {
6270 dbgs() << "Overran sorted position:\n";
6271 S->dumprFull(this); dbgs() << "\n";
6272 dbgs() << "Checking if this is due to cycles\n";
6273 checkForCycles(this, true);
6275 llvm_unreachable(nullptr);
6279 assert(SortedPos == AllNodes.end() &&
6280 "Topological sort incomplete!");
6281 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6282 "First node in topological sort is not the entry token!");
6283 assert(AllNodes.front().getNodeId() == 0 &&
6284 "First node in topological sort has non-zero id!");
6285 assert(AllNodes.front().getNumOperands() == 0 &&
6286 "First node in topological sort has operands!");
6287 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6288 "Last node in topologic sort has unexpected id!");
6289 assert(AllNodes.back().use_empty() &&
6290 "Last node in topologic sort has users!");
6291 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6295 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6296 /// value is produced by SD.
6297 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6299 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6300 SD->setHasDebugValue(true);
6302 DbgInfo->add(DB, SD, isParameter);
6305 /// TransferDbgValues - Transfer SDDbgValues.
6306 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6307 if (From == To || !From.getNode()->getHasDebugValue())
6309 SDNode *FromNode = From.getNode();
6310 SDNode *ToNode = To.getNode();
6311 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6312 SmallVector<SDDbgValue *, 2> ClonedDVs;
6313 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6315 SDDbgValue *Dbg = *I;
6316 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6318 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6319 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6320 Dbg->getDebugLoc(), Dbg->getOrder());
6321 ClonedDVs.push_back(Clone);
6324 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6325 E = ClonedDVs.end(); I != E; ++I)
6326 AddDbgValue(*I, ToNode, false);
6329 //===----------------------------------------------------------------------===//
6331 //===----------------------------------------------------------------------===//
6333 HandleSDNode::~HandleSDNode() {
6337 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6338 DebugLoc DL, const GlobalValue *GA,
6339 EVT VT, int64_t o, unsigned char TF)
6340 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6344 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6345 SDValue X, unsigned SrcAS,
6347 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6348 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6350 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6351 EVT memvt, MachineMemOperand *mmo)
6352 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6353 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6354 MMO->isNonTemporal(), MMO->isInvariant());
6355 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6356 assert(isNonTemporal() == MMO->isNonTemporal() &&
6357 "Non-temporal encoding error!");
6358 // We check here that the size of the memory operand fits within the size of
6359 // the MMO. This is because the MMO might indicate only a possible address
6360 // range instead of specifying the affected memory addresses precisely.
6361 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6364 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6365 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6366 : SDNode(Opc, Order, dl, VTs, Ops),
6367 MemoryVT(memvt), MMO(mmo) {
6368 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6369 MMO->isNonTemporal(), MMO->isInvariant());
6370 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6371 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6374 /// Profile - Gather unique data for the node.
6376 void SDNode::Profile(FoldingSetNodeID &ID) const {
6377 AddNodeIDNode(ID, this);
6382 std::vector<EVT> VTs;
6385 VTs.reserve(MVT::LAST_VALUETYPE);
6386 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6387 VTs.push_back(MVT((MVT::SimpleValueType)i));
6392 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6393 static ManagedStatic<EVTArray> SimpleVTArray;
6394 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6396 /// getValueTypeList - Return a pointer to the specified value type.
6398 const EVT *SDNode::getValueTypeList(EVT VT) {
6399 if (VT.isExtended()) {
6400 sys::SmartScopedLock<true> Lock(*VTMutex);
6401 return &(*EVTs->insert(VT).first);
6403 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6404 "Value type out of range!");
6405 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6409 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6410 /// indicated value. This method ignores uses of other values defined by this
6412 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6413 assert(Value < getNumValues() && "Bad value!");
6415 // TODO: Only iterate over uses of a given value of the node
6416 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6417 if (UI.getUse().getResNo() == Value) {
6424 // Found exactly the right number of uses?
6429 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6430 /// value. This method ignores uses of other values defined by this operation.
6431 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6432 assert(Value < getNumValues() && "Bad value!");
6434 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6435 if (UI.getUse().getResNo() == Value)
6442 /// isOnlyUserOf - Return true if this node is the only use of N.
6444 bool SDNode::isOnlyUserOf(SDNode *N) const {
6446 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6457 /// isOperand - Return true if this node is an operand of N.
6459 bool SDValue::isOperandOf(SDNode *N) const {
6460 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6461 if (*this == N->getOperand(i))
6466 bool SDNode::isOperandOf(SDNode *N) const {
6467 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6468 if (this == N->OperandList[i].getNode())
6473 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6474 /// be a chain) reaches the specified operand without crossing any
6475 /// side-effecting instructions on any chain path. In practice, this looks
6476 /// through token factors and non-volatile loads. In order to remain efficient,
6477 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6478 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6479 unsigned Depth) const {
6480 if (*this == Dest) return true;
6482 // Don't search too deeply, we just want to be able to see through
6483 // TokenFactor's etc.
6484 if (Depth == 0) return false;
6486 // If this is a token factor, all inputs to the TF happen in parallel. If any
6487 // of the operands of the TF does not reach dest, then we cannot do the xform.
6488 if (getOpcode() == ISD::TokenFactor) {
6489 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6490 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6495 // Loads don't have side effects, look through them.
6496 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6497 if (!Ld->isVolatile())
6498 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6503 /// hasPredecessor - Return true if N is a predecessor of this node.
6504 /// N is either an operand of this node, or can be reached by recursively
6505 /// traversing up the operands.
6506 /// NOTE: This is an expensive method. Use it carefully.
6507 bool SDNode::hasPredecessor(const SDNode *N) const {
6508 SmallPtrSet<const SDNode *, 32> Visited;
6509 SmallVector<const SDNode *, 16> Worklist;
6510 return hasPredecessorHelper(N, Visited, Worklist);
6514 SDNode::hasPredecessorHelper(const SDNode *N,
6515 SmallPtrSetImpl<const SDNode *> &Visited,
6516 SmallVectorImpl<const SDNode *> &Worklist) const {
6517 if (Visited.empty()) {
6518 Worklist.push_back(this);
6520 // Take a look in the visited set. If we've already encountered this node
6521 // we needn't search further.
6522 if (Visited.count(N))
6526 // Haven't visited N yet. Continue the search.
6527 while (!Worklist.empty()) {
6528 const SDNode *M = Worklist.pop_back_val();
6529 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6530 SDNode *Op = M->getOperand(i).getNode();
6531 if (Visited.insert(Op).second)
6532 Worklist.push_back(Op);
6541 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6542 assert(Num < NumOperands && "Invalid child # of SDNode!");
6543 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6546 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6547 assert(N->getNumValues() == 1 &&
6548 "Can't unroll a vector with multiple results!");
6550 EVT VT = N->getValueType(0);
6551 unsigned NE = VT.getVectorNumElements();
6552 EVT EltVT = VT.getVectorElementType();
6555 SmallVector<SDValue, 8> Scalars;
6556 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6558 // If ResNE is 0, fully unroll the vector op.
6561 else if (NE > ResNE)
6565 for (i= 0; i != NE; ++i) {
6566 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6567 SDValue Operand = N->getOperand(j);
6568 EVT OperandVT = Operand.getValueType();
6569 if (OperandVT.isVector()) {
6570 // A vector operand; extract a single element.
6571 EVT OperandEltVT = OperandVT.getVectorElementType();
6572 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6575 getConstant(i, TLI->getVectorIdxTy()));
6577 // A scalar operand; just use it as is.
6578 Operands[j] = Operand;
6582 switch (N->getOpcode()) {
6584 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6587 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6594 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6595 getShiftAmountOperand(Operands[0].getValueType(),
6598 case ISD::SIGN_EXTEND_INREG:
6599 case ISD::FP_ROUND_INREG: {
6600 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6601 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6603 getValueType(ExtVT)));
6608 for (; i < ResNE; ++i)
6609 Scalars.push_back(getUNDEF(EltVT));
6611 return getNode(ISD::BUILD_VECTOR, dl,
6612 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6616 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6617 /// location that is 'Dist' units away from the location that the 'Base' load
6618 /// is loading from.
6619 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6620 unsigned Bytes, int Dist) const {
6621 if (LD->getChain() != Base->getChain())
6623 EVT VT = LD->getValueType(0);
6624 if (VT.getSizeInBits() / 8 != Bytes)
6627 SDValue Loc = LD->getOperand(1);
6628 SDValue BaseLoc = Base->getOperand(1);
6629 if (Loc.getOpcode() == ISD::FrameIndex) {
6630 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6632 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6633 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6634 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6635 int FS = MFI->getObjectSize(FI);
6636 int BFS = MFI->getObjectSize(BFI);
6637 if (FS != BFS || FS != (int)Bytes) return false;
6638 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6642 if (isBaseWithConstantOffset(Loc)) {
6643 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6644 if (Loc.getOperand(0) == BaseLoc) {
6645 // If the base location is a simple address with no offset itself, then
6646 // the second load's first add operand should be the base address.
6647 if (LocOffset == Dist * (int)Bytes)
6649 } else if (isBaseWithConstantOffset(BaseLoc)) {
6650 // The base location itself has an offset, so subtract that value from the
6651 // second load's offset before comparing to distance * size.
6653 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6654 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6655 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6660 const GlobalValue *GV1 = nullptr;
6661 const GlobalValue *GV2 = nullptr;
6662 int64_t Offset1 = 0;
6663 int64_t Offset2 = 0;
6664 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6665 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6666 if (isGA1 && isGA2 && GV1 == GV2)
6667 return Offset1 == (Offset2 + Dist*Bytes);
6672 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6673 /// it cannot be inferred.
6674 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6675 // If this is a GlobalAddress + cst, return the alignment.
6676 const GlobalValue *GV;
6677 int64_t GVOffset = 0;
6678 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6679 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6680 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6681 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6682 TLI->getDataLayout());
6683 unsigned AlignBits = KnownZero.countTrailingOnes();
6684 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6686 return MinAlign(Align, GVOffset);
6689 // If this is a direct reference to a stack slot, use information about the
6690 // stack slot's alignment.
6691 int FrameIdx = 1 << 31;
6692 int64_t FrameOffset = 0;
6693 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6694 FrameIdx = FI->getIndex();
6695 } else if (isBaseWithConstantOffset(Ptr) &&
6696 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6698 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6699 FrameOffset = Ptr.getConstantOperandVal(1);
6702 if (FrameIdx != (1 << 31)) {
6703 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6704 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6712 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6713 /// which is split (or expanded) into two not necessarily identical pieces.
6714 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6715 // Currently all types are split in half.
6717 if (!VT.isVector()) {
6718 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6720 unsigned NumElements = VT.getVectorNumElements();
6721 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6722 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6725 return std::make_pair(LoVT, HiVT);
6728 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6730 std::pair<SDValue, SDValue>
6731 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6733 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6734 N.getValueType().getVectorNumElements() &&
6735 "More vector elements requested than available!");
6737 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6738 getConstant(0, TLI->getVectorIdxTy()));
6739 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6740 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6741 return std::make_pair(Lo, Hi);
6744 void SelectionDAG::ExtractVectorElements(SDValue Op,
6745 SmallVectorImpl<SDValue> &Args,
6746 unsigned Start, unsigned Count) {
6747 EVT VT = Op.getValueType();
6749 Count = VT.getVectorNumElements();
6751 EVT EltVT = VT.getVectorElementType();
6752 EVT IdxTy = TLI->getVectorIdxTy();
6754 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6755 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6756 Op, getConstant(i, IdxTy)));
6760 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6761 unsigned GlobalAddressSDNode::getAddressSpace() const {
6762 return getGlobal()->getType()->getAddressSpace();
6766 Type *ConstantPoolSDNode::getType() const {
6767 if (isMachineConstantPoolEntry())
6768 return Val.MachineCPVal->getType();
6769 return Val.ConstVal->getType();
6772 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6774 unsigned &SplatBitSize,
6776 unsigned MinSplatBits,
6777 bool isBigEndian) const {
6778 EVT VT = getValueType(0);
6779 assert(VT.isVector() && "Expected a vector type");
6780 unsigned sz = VT.getSizeInBits();
6781 if (MinSplatBits > sz)
6784 SplatValue = APInt(sz, 0);
6785 SplatUndef = APInt(sz, 0);
6787 // Get the bits. Bits with undefined values (when the corresponding element
6788 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6789 // in SplatValue. If any of the values are not constant, give up and return
6791 unsigned int nOps = getNumOperands();
6792 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6793 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6795 for (unsigned j = 0; j < nOps; ++j) {
6796 unsigned i = isBigEndian ? nOps-1-j : j;
6797 SDValue OpVal = getOperand(i);
6798 unsigned BitPos = j * EltBitSize;
6800 if (OpVal.getOpcode() == ISD::UNDEF)
6801 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6802 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6803 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6804 zextOrTrunc(sz) << BitPos;
6805 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6806 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6811 // The build_vector is all constants or undefs. Find the smallest element
6812 // size that splats the vector.
6814 HasAnyUndefs = (SplatUndef != 0);
6817 unsigned HalfSize = sz / 2;
6818 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6819 APInt LowValue = SplatValue.trunc(HalfSize);
6820 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6821 APInt LowUndef = SplatUndef.trunc(HalfSize);
6823 // If the two halves do not match (ignoring undef bits), stop here.
6824 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6825 MinSplatBits > HalfSize)
6828 SplatValue = HighValue | LowValue;
6829 SplatUndef = HighUndef & LowUndef;
6838 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6839 if (UndefElements) {
6840 UndefElements->clear();
6841 UndefElements->resize(getNumOperands());
6844 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6845 SDValue Op = getOperand(i);
6846 if (Op.getOpcode() == ISD::UNDEF) {
6848 (*UndefElements)[i] = true;
6849 } else if (!Splatted) {
6851 } else if (Splatted != Op) {
6857 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6858 "Can only have a splat without a constant for all undefs.");
6859 return getOperand(0);
6866 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6867 return dyn_cast_or_null<ConstantSDNode>(
6868 getSplatValue(UndefElements).getNode());
6872 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6873 return dyn_cast_or_null<ConstantFPSDNode>(
6874 getSplatValue(UndefElements).getNode());
6877 bool BuildVectorSDNode::isConstant() const {
6878 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6879 unsigned Opc = getOperand(i).getOpcode();
6880 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6886 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6887 // Find the first non-undef value in the shuffle mask.
6889 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6892 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6894 // Make sure all remaining elements are either undef or the same as the first
6896 for (int Idx = Mask[i]; i != e; ++i)
6897 if (Mask[i] >= 0 && Mask[i] != Idx)
6903 static void checkForCyclesHelper(const SDNode *N,
6904 SmallPtrSetImpl<const SDNode*> &Visited,
6905 SmallPtrSetImpl<const SDNode*> &Checked,
6906 const llvm::SelectionDAG *DAG) {
6907 // If this node has already been checked, don't check it again.
6908 if (Checked.count(N))
6911 // If a node has already been visited on this depth-first walk, reject it as
6913 if (!Visited.insert(N).second) {
6914 errs() << "Detected cycle in SelectionDAG\n";
6915 dbgs() << "Offending node:\n";
6916 N->dumprFull(DAG); dbgs() << "\n";
6920 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6921 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6928 void llvm::checkForCycles(const llvm::SDNode *N,
6929 const llvm::SelectionDAG *DAG,
6937 assert(N && "Checking nonexistent SDNode");
6938 SmallPtrSet<const SDNode*, 32> visited;
6939 SmallPtrSet<const SDNode*, 32> checked;
6940 checkForCyclesHelper(N, visited, checked, DAG);
6945 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6946 checkForCycles(DAG->getRoot().getNode(), DAG, force);