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"
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59 SDVTList Res = {VTs, NumVTs};
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67 //===----------------------------------------------------------------------===//
68 // ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76 return getValueAPF().bitwiseIsEqual(V);
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
81 assert(VT.isFloatingPoint() && "Can only convert between FP types");
83 // convert modifies in place, so make a copy.
84 APFloat Val2 = APFloat(Val);
86 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87 APFloat::rmNearestTiesToEven,
92 //===----------------------------------------------------------------------===//
94 //===----------------------------------------------------------------------===//
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99 // Look through a bit convert.
100 while (N->getOpcode() == ISD::BITCAST)
101 N = N->getOperand(0).getNode();
103 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105 unsigned i = 0, e = N->getNumOperands();
107 // Skip over all of the undef values.
108 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111 // Do not accept an all-undef vector.
112 if (i == e) return false;
114 // Do not accept build_vectors that aren't all constants or which have non-~0
115 // elements. We have to be a bit careful here, as the type of the constant
116 // may not be the same as the type of the vector elements due to type
117 // legalization (the elements are promoted to a legal type for the target and
118 // a vector of a type may be legal when the base element type is not).
119 // We only want to check enough bits to cover the vector elements, because
120 // we care if the resultant vector is all ones, not whether the individual
122 SDValue NotZero = N->getOperand(i);
123 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133 // Okay, we have at least one ~0 value, check to see if the rest match or are
134 // undefs. Even with the above element type twiddling, this should be OK, as
135 // the same type legalization should have applied to all the elements.
136 for (++i; i != e; ++i)
137 if (N->getOperand(i) != NotZero &&
138 N->getOperand(i).getOpcode() != ISD::UNDEF)
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147 // Look through a bit convert.
148 while (N->getOpcode() == ISD::BITCAST)
149 N = N->getOperand(0).getNode();
151 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153 bool IsAllUndef = true;
154 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept build_vectors that aren't all constants or which have non-0
159 // elements. We have to be a bit careful here, as the type of the constant
160 // may not be the same as the type of the vector elements due to type
161 // legalization (the elements are promoted to a legal type for the target
162 // and a vector of a type may be legal when the base element type is not).
163 // We only want to check enough bits to cover the vector elements, because
164 // we care if the resultant vector is all zeros, not whether the individual
166 SDValue Zero = N->getOperand(i);
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
191 SDValue Op = N->getOperand(i);
192 if (Op.getOpcode() == ISD::UNDEF)
194 if (!isa<ConstantSDNode>(Op))
200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
201 /// all ConstantFPSDNode or undef.
202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
207 SDValue Op = N->getOperand(i);
208 if (Op.getOpcode() == ISD::UNDEF)
210 if (!isa<ConstantFPSDNode>(Op))
216 /// isScalarToVector - Return true if the specified node is a
217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
218 /// element is not an undef.
219 bool ISD::isScalarToVector(const SDNode *N) {
220 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
223 if (N->getOpcode() != ISD::BUILD_VECTOR)
225 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
227 unsigned NumElems = N->getNumOperands();
230 for (unsigned i = 1; i < NumElems; ++i) {
231 SDValue V = N->getOperand(i);
232 if (V.getOpcode() != ISD::UNDEF)
238 /// allOperandsUndef - Return true if the node has at least one operand
239 /// and all operands of the specified node are ISD::UNDEF.
240 bool ISD::allOperandsUndef(const SDNode *N) {
241 // Return false if the node has no operands.
242 // This is "logically inconsistent" with the definition of "all" but
243 // is probably the desired behavior.
244 if (N->getNumOperands() == 0)
247 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
248 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
257 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
259 return ISD::SIGN_EXTEND;
261 return ISD::ZERO_EXTEND;
266 llvm_unreachable("Invalid LoadExtType");
269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
270 /// when given the operation for (X op Y).
271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
272 // To perform this operation, we just need to swap the L and G bits of the
274 unsigned OldL = (Operation >> 2) & 1;
275 unsigned OldG = (Operation >> 1) & 1;
276 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
277 (OldL << 1) | // New G bit
278 (OldG << 2)); // New L bit.
281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
282 /// 'op' is a valid SetCC operation.
283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
284 unsigned Operation = Op;
286 Operation ^= 7; // Flip L, G, E bits, but not U.
288 Operation ^= 15; // Flip all of the condition bits.
290 if (Operation > ISD::SETTRUE2)
291 Operation &= ~8; // Don't let N and U bits get set.
293 return ISD::CondCode(Operation);
297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
298 /// signed operation and 2 if the result is an unsigned comparison. Return zero
299 /// if the operation does not depend on the sign of the input (setne and seteq).
300 static int isSignedOp(ISD::CondCode Opcode) {
302 default: llvm_unreachable("Illegal integer setcc operation!");
304 case ISD::SETNE: return 0;
308 case ISD::SETGE: return 1;
312 case ISD::SETUGE: return 2;
316 /// getSetCCOrOperation - Return the result of a logical OR between different
317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
318 /// returns SETCC_INVALID if it is not possible to represent the resultant
320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
322 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323 // Cannot fold a signed integer setcc with an unsigned integer setcc.
324 return ISD::SETCC_INVALID;
326 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
328 // If the N and U bits get set then the resultant comparison DOES suddenly
329 // care about orderedness, and is true when ordered.
330 if (Op > ISD::SETTRUE2)
331 Op &= ~16; // Clear the U bit if the N bit is set.
333 // Canonicalize illegal integer setcc's.
334 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
337 return ISD::CondCode(Op);
340 /// getSetCCAndOperation - Return the result of a logical AND between different
341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
342 /// function returns zero if it is not possible to represent the resultant
344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
346 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
347 // Cannot fold a signed setcc with an unsigned setcc.
348 return ISD::SETCC_INVALID;
350 // Combine all of the condition bits.
351 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
353 // Canonicalize illegal integer setcc's.
357 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
358 case ISD::SETOEQ: // SETEQ & SETU[LG]E
359 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
360 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
361 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
368 //===----------------------------------------------------------------------===//
369 // SDNode Profile Support
370 //===----------------------------------------------------------------------===//
372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
379 /// solely with their pointer.
380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
381 ID.AddPointer(VTList.VTs);
384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
387 ArrayRef<SDValue> Ops) {
388 for (auto& Op : Ops) {
389 ID.AddPointer(Op.getNode());
390 ID.AddInteger(Op.getResNo());
394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
397 ArrayRef<SDUse> Ops) {
398 for (auto& Op : Ops) {
399 ID.AddPointer(Op.getNode());
400 ID.AddInteger(Op.getResNo());
404 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
408 ID.AddBoolean(exact);
411 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
412 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
413 bool nuw, bool nsw, bool exact) {
414 if (isBinOpWithFlags(Opcode))
415 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
419 SDVTList VTList, ArrayRef<SDValue> OpList) {
420 AddNodeIDOpcode(ID, OpC);
421 AddNodeIDValueTypes(ID, VTList);
422 AddNodeIDOperands(ID, OpList);
425 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
427 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
428 switch (N->getOpcode()) {
429 case ISD::TargetExternalSymbol:
430 case ISD::ExternalSymbol:
431 llvm_unreachable("Should only be used on nodes with operands");
432 default: break; // Normal nodes don't need extra info.
433 case ISD::TargetConstant:
434 case ISD::Constant: {
435 const ConstantSDNode *C = cast<ConstantSDNode>(N);
436 ID.AddPointer(C->getConstantIntValue());
437 ID.AddBoolean(C->isOpaque());
440 case ISD::TargetConstantFP:
441 case ISD::ConstantFP: {
442 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
445 case ISD::TargetGlobalAddress:
446 case ISD::GlobalAddress:
447 case ISD::TargetGlobalTLSAddress:
448 case ISD::GlobalTLSAddress: {
449 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
450 ID.AddPointer(GA->getGlobal());
451 ID.AddInteger(GA->getOffset());
452 ID.AddInteger(GA->getTargetFlags());
453 ID.AddInteger(GA->getAddressSpace());
456 case ISD::BasicBlock:
457 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
460 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
462 case ISD::RegisterMask:
463 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
466 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
468 case ISD::FrameIndex:
469 case ISD::TargetFrameIndex:
470 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
473 case ISD::TargetJumpTable:
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
475 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
477 case ISD::ConstantPool:
478 case ISD::TargetConstantPool: {
479 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
480 ID.AddInteger(CP->getAlignment());
481 ID.AddInteger(CP->getOffset());
482 if (CP->isMachineConstantPoolEntry())
483 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
485 ID.AddPointer(CP->getConstVal());
486 ID.AddInteger(CP->getTargetFlags());
489 case ISD::TargetIndex: {
490 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
491 ID.AddInteger(TI->getIndex());
492 ID.AddInteger(TI->getOffset());
493 ID.AddInteger(TI->getTargetFlags());
497 const LoadSDNode *LD = cast<LoadSDNode>(N);
498 ID.AddInteger(LD->getMemoryVT().getRawBits());
499 ID.AddInteger(LD->getRawSubclassData());
500 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
504 const StoreSDNode *ST = cast<StoreSDNode>(N);
505 ID.AddInteger(ST->getMemoryVT().getRawBits());
506 ID.AddInteger(ST->getRawSubclassData());
507 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
518 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
519 AddBinaryNodeIDCustom(
520 ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
521 BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
524 case ISD::ATOMIC_CMP_SWAP:
525 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
526 case ISD::ATOMIC_SWAP:
527 case ISD::ATOMIC_LOAD_ADD:
528 case ISD::ATOMIC_LOAD_SUB:
529 case ISD::ATOMIC_LOAD_AND:
530 case ISD::ATOMIC_LOAD_OR:
531 case ISD::ATOMIC_LOAD_XOR:
532 case ISD::ATOMIC_LOAD_NAND:
533 case ISD::ATOMIC_LOAD_MIN:
534 case ISD::ATOMIC_LOAD_MAX:
535 case ISD::ATOMIC_LOAD_UMIN:
536 case ISD::ATOMIC_LOAD_UMAX:
537 case ISD::ATOMIC_LOAD:
538 case ISD::ATOMIC_STORE: {
539 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
540 ID.AddInteger(AT->getMemoryVT().getRawBits());
541 ID.AddInteger(AT->getRawSubclassData());
542 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
545 case ISD::PREFETCH: {
546 const MemSDNode *PF = cast<MemSDNode>(N);
547 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
550 case ISD::VECTOR_SHUFFLE: {
551 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
552 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
554 ID.AddInteger(SVN->getMaskElt(i));
557 case ISD::TargetBlockAddress:
558 case ISD::BlockAddress: {
559 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
560 ID.AddPointer(BA->getBlockAddress());
561 ID.AddInteger(BA->getOffset());
562 ID.AddInteger(BA->getTargetFlags());
565 } // end switch (N->getOpcode())
567 // Target specific memory nodes could also have address spaces to check.
568 if (N->isTargetMemoryOpcode())
569 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
575 AddNodeIDOpcode(ID, N->getOpcode());
576 // Add the return value info.
577 AddNodeIDValueTypes(ID, N->getVTList());
578 // Add the operand info.
579 AddNodeIDOperands(ID, N->ops());
581 // Handle SDNode leafs with special info.
582 AddNodeIDCustom(ID, N);
585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
586 /// the CSE map that carries volatility, temporalness, indexing mode, and
587 /// extension/truncation information.
589 static inline unsigned
590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
591 bool isNonTemporal, bool isInvariant) {
592 assert((ConvType & 3) == ConvType &&
593 "ConvType may not require more than 2 bits!");
594 assert((AM & 7) == AM &&
595 "AM may not require more than 3 bits!");
599 (isNonTemporal << 6) |
603 //===----------------------------------------------------------------------===//
604 // SelectionDAG Class
605 //===----------------------------------------------------------------------===//
607 /// doNotCSE - Return true if CSE should not be performed for this node.
608 static bool doNotCSE(SDNode *N) {
609 if (N->getValueType(0) == MVT::Glue)
610 return true; // Never CSE anything that produces a flag.
612 switch (N->getOpcode()) {
614 case ISD::HANDLENODE:
616 return true; // Never CSE these nodes.
619 // Check that remaining values produced are not flags.
620 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
621 if (N->getValueType(i) == MVT::Glue)
622 return true; // Never CSE anything that produces a flag.
627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
629 void SelectionDAG::RemoveDeadNodes() {
630 // Create a dummy node (which is not added to allnodes), that adds a reference
631 // to the root node, preventing it from being deleted.
632 HandleSDNode Dummy(getRoot());
634 SmallVector<SDNode*, 128> DeadNodes;
636 // Add all obviously-dead nodes to the DeadNodes worklist.
637 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
639 DeadNodes.push_back(I);
641 RemoveDeadNodes(DeadNodes);
643 // If the root changed (e.g. it was a dead load, update the root).
644 setRoot(Dummy.getValue());
647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
648 /// given list, and any nodes that become unreachable as a result.
649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
651 // Process the worklist, deleting the nodes and adding their uses to the
653 while (!DeadNodes.empty()) {
654 SDNode *N = DeadNodes.pop_back_val();
656 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
657 DUL->NodeDeleted(N, nullptr);
659 // Take the node out of the appropriate CSE map.
660 RemoveNodeFromCSEMaps(N);
662 // Next, brutally remove the operand list. This is safe to do, as there are
663 // no cycles in the graph.
664 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
666 SDNode *Operand = Use.getNode();
669 // Now that we removed this operand, see if there are no uses of it left.
670 if (Operand->use_empty())
671 DeadNodes.push_back(Operand);
678 void SelectionDAG::RemoveDeadNode(SDNode *N){
679 SmallVector<SDNode*, 16> DeadNodes(1, N);
681 // Create a dummy node that adds a reference to the root node, preventing
682 // it from being deleted. (This matters if the root is an operand of the
684 HandleSDNode Dummy(getRoot());
686 RemoveDeadNodes(DeadNodes);
689 void SelectionDAG::DeleteNode(SDNode *N) {
690 // First take this out of the appropriate CSE map.
691 RemoveNodeFromCSEMaps(N);
693 // Finally, remove uses due to operands of this node, remove from the
694 // AllNodes list, and delete the node.
695 DeleteNodeNotInCSEMaps(N);
698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
699 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
700 assert(N->use_empty() && "Cannot delete a node that is not dead!");
702 // Drop all of the operands and decrement used node's use counts.
708 void SDDbgInfo::erase(const SDNode *Node) {
709 DbgValMapType::iterator I = DbgValMap.find(Node);
710 if (I == DbgValMap.end())
712 for (auto &Val: I->second)
713 Val->setIsInvalidated();
717 void SelectionDAG::DeallocateNode(SDNode *N) {
718 if (N->OperandsNeedDelete)
719 delete[] N->OperandList;
721 // Set the opcode to DELETED_NODE to help catch bugs when node
722 // memory is reallocated.
723 N->NodeType = ISD::DELETED_NODE;
725 NodeAllocator.Deallocate(AllNodes.remove(N));
727 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
728 // them and forget about that node.
733 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
734 static void VerifySDNode(SDNode *N) {
735 switch (N->getOpcode()) {
738 case ISD::BUILD_PAIR: {
739 EVT VT = N->getValueType(0);
740 assert(N->getNumValues() == 1 && "Too many results!");
741 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
742 "Wrong return type!");
743 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
744 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
745 "Mismatched operand types!");
746 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
747 "Wrong operand type!");
748 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
749 "Wrong return type size");
752 case ISD::BUILD_VECTOR: {
753 assert(N->getNumValues() == 1 && "Too many results!");
754 assert(N->getValueType(0).isVector() && "Wrong return type!");
755 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
756 "Wrong number of operands!");
757 EVT EltVT = N->getValueType(0).getVectorElementType();
758 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
759 assert((I->getValueType() == EltVT ||
760 (EltVT.isInteger() && I->getValueType().isInteger() &&
761 EltVT.bitsLE(I->getValueType()))) &&
762 "Wrong operand type!");
763 assert(I->getValueType() == N->getOperand(0).getValueType() &&
764 "Operands must all have the same type");
772 /// \brief Insert a newly allocated node into the DAG.
774 /// Handles insertion into the all nodes list and CSE map, as well as
775 /// verification and other common operations when a new node is allocated.
776 void SelectionDAG::InsertNode(SDNode *N) {
777 AllNodes.push_back(N);
783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
784 /// correspond to it. This is useful when we're about to delete or repurpose
785 /// the node. We don't want future request for structurally identical nodes
786 /// to return N anymore.
787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
789 switch (N->getOpcode()) {
790 case ISD::HANDLENODE: return false; // noop.
792 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
793 "Cond code doesn't exist!");
794 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
795 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
797 case ISD::ExternalSymbol:
798 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
800 case ISD::TargetExternalSymbol: {
801 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
802 Erased = TargetExternalSymbols.erase(
803 std::pair<std::string,unsigned char>(ESN->getSymbol(),
804 ESN->getTargetFlags()));
807 case ISD::VALUETYPE: {
808 EVT VT = cast<VTSDNode>(N)->getVT();
809 if (VT.isExtended()) {
810 Erased = ExtendedValueTypeNodes.erase(VT);
812 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
813 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
818 // Remove it from the CSE Map.
819 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
820 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
821 Erased = CSEMap.RemoveNode(N);
825 // Verify that the node was actually in one of the CSE maps, unless it has a
826 // flag result (which cannot be CSE'd) or is one of the special cases that are
827 // not subject to CSE.
828 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
829 !N->isMachineOpcode() && !doNotCSE(N)) {
832 llvm_unreachable("Node is not in map!");
838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
840 /// node already exists, in which case transfer all its users to the existing
841 /// node. This transfer can potentially trigger recursive merging.
844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
845 // For node types that aren't CSE'd, just act as if no identical node
848 SDNode *Existing = CSEMap.GetOrInsertNode(N);
850 // If there was already an existing matching node, use ReplaceAllUsesWith
851 // to replace the dead one with the existing one. This can cause
852 // recursive merging of other unrelated nodes down the line.
853 ReplaceAllUsesWith(N, Existing);
855 // N is now dead. Inform the listeners and delete it.
856 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
857 DUL->NodeDeleted(N, Existing);
858 DeleteNodeNotInCSEMaps(N);
863 // If the node doesn't already exist, we updated it. Inform listeners.
864 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
869 /// were replaced with those specified. If this node is never memoized,
870 /// return null, otherwise return a pointer to the slot it would take. If a
871 /// node already exists with these operands, the slot will be non-null.
872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
877 SDValue Ops[] = { Op };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
886 /// were replaced with those specified. If this node is never memoized,
887 /// return null, otherwise return a pointer to the slot it would take. If a
888 /// node already exists with these operands, the slot will be non-null.
889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
890 SDValue Op1, SDValue Op2,
895 SDValue Ops[] = { Op1, Op2 };
897 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
898 AddNodeIDCustom(ID, N);
899 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
905 /// were replaced with those specified. If this node is never memoized,
906 /// return null, otherwise return a pointer to the slot it would take. If a
907 /// node already exists with these operands, the slot will be non-null.
908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
914 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
915 AddNodeIDCustom(ID, N);
916 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
920 /// getEVTAlignment - Compute the default alignment value for the
923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
924 Type *Ty = VT == MVT::iPTR ?
925 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
926 VT.getTypeForEVT(*getContext());
928 return TLI->getDataLayout()->getABITypeAlignment(Ty);
931 // EntryNode could meaningfully have debug info if we can find it...
932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
933 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
934 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
935 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
936 UpdateListeners(nullptr) {
937 AllNodes.push_back(&EntryNode);
938 DbgInfo = new SDDbgInfo();
941 void SelectionDAG::init(MachineFunction &mf) {
943 TLI = getSubtarget().getTargetLowering();
944 TSI = getSubtarget().getSelectionDAGInfo();
945 Context = &mf.getFunction()->getContext();
948 SelectionDAG::~SelectionDAG() {
949 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
954 void SelectionDAG::allnodes_clear() {
955 assert(&*AllNodes.begin() == &EntryNode);
956 AllNodes.remove(AllNodes.begin());
957 while (!AllNodes.empty())
958 DeallocateNode(AllNodes.begin());
961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
962 SDVTList VTs, SDValue N1,
963 SDValue N2, bool nuw, bool nsw,
965 if (isBinOpWithFlags(Opcode)) {
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
968 FN->Flags.setNoUnsignedWrap(nuw);
969 FN->Flags.setNoSignedWrap(nsw);
970 FN->Flags.setExact(exact);
975 BinarySDNode *N = new (NodeAllocator)
976 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
982 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
984 switch (N->getOpcode()) {
987 case ISD::ConstantFP:
988 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
989 "debug location. Use another overload.");
995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
996 DebugLoc DL, void *&InsertPos) {
997 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
999 switch (N->getOpcode()) {
1000 default: break; // Process only regular (non-target) constant nodes.
1002 case ISD::ConstantFP:
1003 // Erase debug location from the node if the node is used at several
1004 // different places to do not propagate one location to all uses as it
1005 // leads to incorrect debug info.
1006 if (N->getDebugLoc() != DL)
1007 N->setDebugLoc(DebugLoc());
1014 void SelectionDAG::clear() {
1016 OperandAllocator.Reset();
1019 ExtendedValueTypeNodes.clear();
1020 ExternalSymbols.clear();
1021 TargetExternalSymbols.clear();
1022 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1023 static_cast<CondCodeSDNode*>(nullptr));
1024 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1025 static_cast<SDNode*>(nullptr));
1027 EntryNode.UseList = nullptr;
1028 AllNodes.push_back(&EntryNode);
1029 Root = getEntryNode();
1033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1034 return VT.bitsGT(Op.getValueType()) ?
1035 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1036 getNode(ISD::TRUNCATE, DL, VT, Op);
1039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1040 return VT.bitsGT(Op.getValueType()) ?
1041 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1042 getNode(ISD::TRUNCATE, DL, VT, Op);
1045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1046 return VT.bitsGT(Op.getValueType()) ?
1047 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1048 getNode(ISD::TRUNCATE, DL, VT, Op);
1051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1053 if (VT.bitsLE(Op.getValueType()))
1054 return getNode(ISD::TRUNCATE, SL, VT, Op);
1056 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1057 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1061 assert(!VT.isVector() &&
1062 "getZeroExtendInReg should use the vector element type instead of "
1063 "the vector type!");
1064 if (Op.getValueType() == VT) return Op;
1065 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1066 APInt Imm = APInt::getLowBitsSet(BitWidth,
1067 VT.getSizeInBits());
1068 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1069 getConstant(Imm, DL, Op.getValueType()));
1072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1073 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1074 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1075 "The sizes of the input and result must match in order to perform the "
1076 "extend in-register.");
1077 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1078 "The destination vector type must have fewer lanes than the input.");
1079 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1083 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1084 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1085 "The sizes of the input and result must match in order to perform the "
1086 "extend in-register.");
1087 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1088 "The destination vector type must have fewer lanes than the input.");
1089 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1093 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1094 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1095 "The sizes of the input and result must match in order to perform the "
1096 "extend in-register.");
1097 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1098 "The destination vector type must have fewer lanes than the input.");
1099 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1105 EVT EltVT = VT.getScalarType();
1107 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1108 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1112 EVT EltVT = VT.getScalarType();
1114 switch (TLI->getBooleanContents(VT)) {
1115 case TargetLowering::ZeroOrOneBooleanContent:
1116 case TargetLowering::UndefinedBooleanContent:
1117 TrueValue = getConstant(1, DL, VT);
1119 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1120 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1124 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1129 EVT EltVT = VT.getScalarType();
1130 assert((EltVT.getSizeInBits() >= 64 ||
1131 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1132 "getConstant with a uint64_t value that doesn't fit in the type!");
1133 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1139 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1143 bool isT, bool isO) {
1144 assert(VT.isInteger() && "Cannot create FP integer constant!");
1146 EVT EltVT = VT.getScalarType();
1147 const ConstantInt *Elt = &Val;
1149 // In some cases the vector type is legal but the element type is illegal and
1150 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1151 // inserted value (the type does not need to match the vector element type).
1152 // Any extra bits introduced will be truncated away.
1153 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1154 TargetLowering::TypePromoteInteger) {
1155 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1156 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1157 Elt = ConstantInt::get(*getContext(), NewVal);
1159 // In other cases the element type is illegal and needs to be expanded, for
1160 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1161 // the value into n parts and use a vector type with n-times the elements.
1162 // Then bitcast to the type requested.
1163 // Legalizing constants too early makes the DAGCombiner's job harder so we
1164 // only legalize if the DAG tells us we must produce legal types.
1165 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1166 TLI->getTypeAction(*getContext(), EltVT) ==
1167 TargetLowering::TypeExpandInteger) {
1168 APInt NewVal = Elt->getValue();
1169 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1170 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1171 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1172 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1174 // Check the temporary vector is the correct size. If this fails then
1175 // getTypeToTransformTo() probably returned a type whose size (in bits)
1176 // isn't a power-of-2 factor of the requested type size.
1177 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1179 SmallVector<SDValue, 2> EltParts;
1180 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1181 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1182 .trunc(ViaEltSizeInBits), DL,
1183 ViaEltVT, isT, isO));
1186 // EltParts is currently in little endian order. If we actually want
1187 // big-endian order then reverse it now.
1188 if (TLI->isBigEndian())
1189 std::reverse(EltParts.begin(), EltParts.end());
1191 // The elements must be reversed when the element order is different
1192 // to the endianness of the elements (because the BITCAST is itself a
1193 // vector shuffle in this situation). However, we do not need any code to
1194 // perform this reversal because getConstant() is producing a vector
1196 // This situation occurs in MIPS MSA.
1198 SmallVector<SDValue, 8> Ops;
1199 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1200 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1202 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1203 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1208 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1209 "APInt size does not match type size!");
1210 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1211 FoldingSetNodeID ID;
1212 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1216 SDNode *N = nullptr;
1217 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1219 return SDValue(N, 0);
1222 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1224 CSEMap.InsertNode(N, IP);
1228 SDValue Result(N, 0);
1229 if (VT.isVector()) {
1230 SmallVector<SDValue, 8> Ops;
1231 Ops.assign(VT.getVectorNumElements(), Result);
1232 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1238 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1243 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1248 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1250 EVT EltVT = VT.getScalarType();
1252 // Do the map lookup using the actual bit pattern for the floating point
1253 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1254 // we don't have issues with SNANs.
1255 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1256 FoldingSetNodeID ID;
1257 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1260 SDNode *N = nullptr;
1261 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1263 return SDValue(N, 0);
1266 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1268 CSEMap.InsertNode(N, IP);
1272 SDValue Result(N, 0);
1273 if (VT.isVector()) {
1274 SmallVector<SDValue, 8> Ops;
1275 Ops.assign(VT.getVectorNumElements(), Result);
1276 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1283 EVT EltVT = VT.getScalarType();
1284 if (EltVT==MVT::f32)
1285 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f64)
1287 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1288 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1291 APFloat apf = APFloat(Val);
1292 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1294 return getConstantFP(apf, DL, VT, isTarget);
1296 llvm_unreachable("Unsupported type in getConstantFP");
1299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1300 EVT VT, int64_t Offset,
1302 unsigned char TargetFlags) {
1303 assert((TargetFlags == 0 || isTargetGA) &&
1304 "Cannot set target flags on target-independent globals");
1306 // Truncate (with sign-extension) the offset value to the pointer size.
1307 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1309 Offset = SignExtend64(Offset, BitWidth);
1312 if (GV->isThreadLocal())
1313 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1315 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1320 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1322 ID.AddInteger(GV->getType()->getAddressSpace());
1324 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1325 return SDValue(E, 0);
1327 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1328 DL.getDebugLoc(), GV, VT,
1329 Offset, TargetFlags);
1330 CSEMap.InsertNode(N, IP);
1332 return SDValue(N, 0);
1335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1336 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1337 FoldingSetNodeID ID;
1338 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1342 return SDValue(E, 0);
1344 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1345 CSEMap.InsertNode(N, IP);
1347 return SDValue(N, 0);
1350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1351 unsigned char TargetFlags) {
1352 assert((TargetFlags == 0 || isTarget) &&
1353 "Cannot set target flags on target-independent jump tables");
1354 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1355 FoldingSetNodeID ID;
1356 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1358 ID.AddInteger(TargetFlags);
1360 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1361 return SDValue(E, 0);
1363 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1365 CSEMap.InsertNode(N, IP);
1367 return SDValue(N, 0);
1370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1371 unsigned Alignment, int Offset,
1373 unsigned char TargetFlags) {
1374 assert((TargetFlags == 0 || isTarget) &&
1375 "Cannot set target flags on target-independent globals");
1377 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1378 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1379 FoldingSetNodeID ID;
1380 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1381 ID.AddInteger(Alignment);
1382 ID.AddInteger(Offset);
1384 ID.AddInteger(TargetFlags);
1386 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1387 return SDValue(E, 0);
1389 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1390 Alignment, TargetFlags);
1391 CSEMap.InsertNode(N, IP);
1393 return SDValue(N, 0);
1397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1398 unsigned Alignment, int Offset,
1400 unsigned char TargetFlags) {
1401 assert((TargetFlags == 0 || isTarget) &&
1402 "Cannot set target flags on target-independent globals");
1404 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1405 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1408 ID.AddInteger(Alignment);
1409 ID.AddInteger(Offset);
1410 C->addSelectionDAGCSEId(ID);
1411 ID.AddInteger(TargetFlags);
1413 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1414 return SDValue(E, 0);
1416 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1417 Alignment, TargetFlags);
1418 CSEMap.InsertNode(N, IP);
1420 return SDValue(N, 0);
1423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1424 unsigned char TargetFlags) {
1425 FoldingSetNodeID ID;
1426 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1427 ID.AddInteger(Index);
1428 ID.AddInteger(Offset);
1429 ID.AddInteger(TargetFlags);
1431 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1432 return SDValue(E, 0);
1434 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1436 CSEMap.InsertNode(N, IP);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1442 FoldingSetNodeID ID;
1443 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1446 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1447 return SDValue(E, 0);
1449 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1450 CSEMap.InsertNode(N, IP);
1452 return SDValue(N, 0);
1455 SDValue SelectionDAG::getValueType(EVT VT) {
1456 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1457 ValueTypeNodes.size())
1458 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1460 SDNode *&N = VT.isExtended() ?
1461 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1463 if (N) return SDValue(N, 0);
1464 N = new (NodeAllocator) VTSDNode(VT);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1470 SDNode *&N = ExternalSymbols[Sym];
1471 if (N) return SDValue(N, 0);
1472 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1474 return SDValue(N, 0);
1477 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1478 unsigned char TargetFlags) {
1480 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1482 if (N) return SDValue(N, 0);
1483 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1485 return SDValue(N, 0);
1488 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1489 if ((unsigned)Cond >= CondCodeNodes.size())
1490 CondCodeNodes.resize(Cond+1);
1492 if (!CondCodeNodes[Cond]) {
1493 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1494 CondCodeNodes[Cond] = N;
1498 return SDValue(CondCodeNodes[Cond], 0);
1501 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1502 // the shuffle mask M that point at N1 to point at N2, and indices that point
1503 // N2 to point at N1.
1504 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1506 ShuffleVectorSDNode::commuteMask(M);
1509 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1510 SDValue N2, const int *Mask) {
1511 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1512 "Invalid VECTOR_SHUFFLE");
1514 // Canonicalize shuffle undef, undef -> undef
1515 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1516 return getUNDEF(VT);
1518 // Validate that all indices in Mask are within the range of the elements
1519 // input to the shuffle.
1520 unsigned NElts = VT.getVectorNumElements();
1521 SmallVector<int, 8> MaskVec;
1522 for (unsigned i = 0; i != NElts; ++i) {
1523 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1524 MaskVec.push_back(Mask[i]);
1527 // Canonicalize shuffle v, v -> v, undef
1530 for (unsigned i = 0; i != NElts; ++i)
1531 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1534 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1535 if (N1.getOpcode() == ISD::UNDEF)
1536 commuteShuffle(N1, N2, MaskVec);
1538 // If shuffling a splat, try to blend the splat instead. We do this here so
1539 // that even when this arises during lowering we don't have to re-handle it.
1540 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1541 BitVector UndefElements;
1542 SDValue Splat = BV->getSplatValue(&UndefElements);
1546 for (int i = 0; i < (int)NElts; ++i) {
1547 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1550 // If this input comes from undef, mark it as such.
1551 if (UndefElements[MaskVec[i] - Offset]) {
1556 // If we can blend a non-undef lane, use that instead.
1557 if (!UndefElements[i])
1558 MaskVec[i] = i + Offset;
1561 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1562 BlendSplat(N1BV, 0);
1563 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1564 BlendSplat(N2BV, NElts);
1566 // Canonicalize all index into lhs, -> shuffle lhs, undef
1567 // Canonicalize all index into rhs, -> shuffle rhs, undef
1568 bool AllLHS = true, AllRHS = true;
1569 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1570 for (unsigned i = 0; i != NElts; ++i) {
1571 if (MaskVec[i] >= (int)NElts) {
1576 } else if (MaskVec[i] >= 0) {
1580 if (AllLHS && AllRHS)
1581 return getUNDEF(VT);
1582 if (AllLHS && !N2Undef)
1586 commuteShuffle(N1, N2, MaskVec);
1588 // Reset our undef status after accounting for the mask.
1589 N2Undef = N2.getOpcode() == ISD::UNDEF;
1590 // Re-check whether both sides ended up undef.
1591 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1592 return getUNDEF(VT);
1594 // If Identity shuffle return that node.
1595 bool Identity = true, AllSame = true;
1596 for (unsigned i = 0; i != NElts; ++i) {
1597 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1598 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1600 if (Identity && NElts)
1603 // Shuffling a constant splat doesn't change the result.
1607 // Look through any bitcasts. We check that these don't change the number
1608 // (and size) of elements and just changes their types.
1609 while (V.getOpcode() == ISD::BITCAST)
1610 V = V->getOperand(0);
1612 // A splat should always show up as a build vector node.
1613 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1614 BitVector UndefElements;
1615 SDValue Splat = BV->getSplatValue(&UndefElements);
1616 // If this is a splat of an undef, shuffling it is also undef.
1617 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1618 return getUNDEF(VT);
1621 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1623 // We only have a splat which can skip shuffles if there is a splatted
1624 // value and no undef lanes rearranged by the shuffle.
1625 if (Splat && UndefElements.none()) {
1626 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1627 // number of elements match or the value splatted is a zero constant.
1630 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1631 if (C->isNullValue())
1635 // If the shuffle itself creates a splat, build the vector directly.
1636 if (AllSame && SameNumElts) {
1637 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1638 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1640 EVT BuildVT = BV->getValueType(0);
1641 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1643 // We may have jumped through bitcasts, so the type of the
1644 // BUILD_VECTOR may not match the type of the shuffle.
1646 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1652 FoldingSetNodeID ID;
1653 SDValue Ops[2] = { N1, N2 };
1654 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1655 for (unsigned i = 0; i != NElts; ++i)
1656 ID.AddInteger(MaskVec[i]);
1659 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1660 return SDValue(E, 0);
1662 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1663 // SDNode doesn't have access to it. This memory will be "leaked" when
1664 // the node is deallocated, but recovered when the NodeAllocator is released.
1665 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1666 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1668 ShuffleVectorSDNode *N =
1669 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1670 dl.getDebugLoc(), N1, N2,
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1678 MVT VT = SV.getSimpleValueType(0);
1679 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1680 ShuffleVectorSDNode::commuteMask(MaskVec);
1682 SDValue Op0 = SV.getOperand(0);
1683 SDValue Op1 = SV.getOperand(1);
1684 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1687 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1688 SDValue Val, SDValue DTy,
1689 SDValue STy, SDValue Rnd, SDValue Sat,
1690 ISD::CvtCode Code) {
1691 // If the src and dest types are the same and the conversion is between
1692 // integer types of the same sign or two floats, no conversion is necessary.
1694 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1697 FoldingSetNodeID ID;
1698 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1699 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1701 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1702 return SDValue(E, 0);
1704 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1707 CSEMap.InsertNode(N, IP);
1709 return SDValue(N, 0);
1712 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1713 FoldingSetNodeID ID;
1714 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1715 ID.AddInteger(RegNo);
1717 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1718 return SDValue(E, 0);
1720 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1721 CSEMap.InsertNode(N, IP);
1723 return SDValue(N, 0);
1726 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1727 FoldingSetNodeID ID;
1728 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1729 ID.AddPointer(RegMask);
1731 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1741 FoldingSetNodeID ID;
1742 SDValue Ops[] = { Root };
1743 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1744 ID.AddPointer(Label);
1746 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1747 return SDValue(E, 0);
1749 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1750 dl.getDebugLoc(), Root, Label);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1757 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1760 unsigned char TargetFlags) {
1761 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1763 FoldingSetNodeID ID;
1764 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1766 ID.AddInteger(Offset);
1767 ID.AddInteger(TargetFlags);
1769 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1772 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1774 CSEMap.InsertNode(N, IP);
1776 return SDValue(N, 0);
1779 SDValue SelectionDAG::getSrcValue(const Value *V) {
1780 assert((!V || V->getType()->isPointerTy()) &&
1781 "SrcValue is not a pointer?");
1783 FoldingSetNodeID ID;
1784 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1788 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1789 return SDValue(E, 0);
1791 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1792 CSEMap.InsertNode(N, IP);
1794 return SDValue(N, 0);
1797 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1798 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1799 FoldingSetNodeID ID;
1800 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1804 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1805 return SDValue(E, 0);
1807 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1808 CSEMap.InsertNode(N, IP);
1810 return SDValue(N, 0);
1813 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1814 if (VT == V.getValueType())
1817 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1820 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1821 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1822 unsigned SrcAS, unsigned DestAS) {
1823 SDValue Ops[] = {Ptr};
1824 FoldingSetNodeID ID;
1825 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1826 ID.AddInteger(SrcAS);
1827 ID.AddInteger(DestAS);
1830 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1831 return SDValue(E, 0);
1833 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1835 VT, Ptr, SrcAS, DestAS);
1836 CSEMap.InsertNode(N, IP);
1838 return SDValue(N, 0);
1841 /// getShiftAmountOperand - Return the specified value casted to
1842 /// the target's desired shift amount type.
1843 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1844 EVT OpTy = Op.getValueType();
1845 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1846 if (OpTy == ShTy || OpTy.isVector()) return Op;
1848 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1849 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1852 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1853 /// specified value type.
1854 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1855 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1856 unsigned ByteSize = VT.getStoreSize();
1857 Type *Ty = VT.getTypeForEVT(*getContext());
1858 unsigned StackAlign =
1859 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1861 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1862 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1865 /// CreateStackTemporary - Create a stack temporary suitable for holding
1866 /// either of the specified value types.
1867 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1868 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1869 VT2.getStoreSizeInBits())/8;
1870 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1871 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1872 const DataLayout *TD = TLI->getDataLayout();
1873 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1874 TD->getPrefTypeAlignment(Ty2));
1876 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1877 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1878 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1881 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1882 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1883 // These setcc operations always fold.
1887 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1889 case ISD::SETTRUE2: {
1890 TargetLowering::BooleanContent Cnt =
1891 TLI->getBooleanContents(N1->getValueType(0));
1893 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1907 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1911 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1912 const APInt &C2 = N2C->getAPIntValue();
1913 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1914 const APInt &C1 = N1C->getAPIntValue();
1917 default: llvm_unreachable("Unknown integer setcc!");
1918 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1919 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1920 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1921 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1922 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1923 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1924 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1925 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1926 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1927 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1931 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1932 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1933 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1936 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1937 return getUNDEF(VT);
1939 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1940 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1941 return getUNDEF(VT);
1943 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1944 R==APFloat::cmpLessThan, dl, VT);
1945 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1946 return getUNDEF(VT);
1948 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1949 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1950 return getUNDEF(VT);
1952 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1953 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1954 return getUNDEF(VT);
1956 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1957 R==APFloat::cmpEqual, dl, VT);
1958 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1959 return getUNDEF(VT);
1961 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1962 R==APFloat::cmpEqual, dl, VT);
1963 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1964 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1965 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1966 R==APFloat::cmpEqual, dl, VT);
1967 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1968 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1969 R==APFloat::cmpLessThan, dl, VT);
1970 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1971 R==APFloat::cmpUnordered, dl, VT);
1972 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1973 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1976 // Ensure that the constant occurs on the RHS.
1977 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1978 MVT CompVT = N1.getValueType().getSimpleVT();
1979 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1982 return getSetCC(dl, VT, N2, N1, SwappedCond);
1986 // Could not fold it.
1990 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1991 /// use this predicate to simplify operations downstream.
1992 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1993 // This predicate is not safe for vector operations.
1994 if (Op.getValueType().isVector())
1997 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1998 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2001 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2002 /// this predicate to simplify operations downstream. Mask is known to be zero
2003 /// for bits that V cannot have.
2004 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2005 unsigned Depth) const {
2006 APInt KnownZero, KnownOne;
2007 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2008 return (KnownZero & Mask) == Mask;
2011 /// Determine which bits of Op are known to be either zero or one and return
2012 /// them in the KnownZero/KnownOne bitsets.
2013 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2014 APInt &KnownOne, unsigned Depth) const {
2015 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2017 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2019 return; // Limit search depth.
2021 APInt KnownZero2, KnownOne2;
2023 switch (Op.getOpcode()) {
2025 // We know all of the bits for a constant!
2026 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2027 KnownZero = ~KnownOne;
2030 // If either the LHS or the RHS are Zero, the result is zero.
2031 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2032 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2034 // Output known-1 bits are only known if set in both the LHS & RHS.
2035 KnownOne &= KnownOne2;
2036 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2037 KnownZero |= KnownZero2;
2040 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2041 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2043 // Output known-0 bits are only known if clear in both the LHS & RHS.
2044 KnownZero &= KnownZero2;
2045 // Output known-1 are known to be set if set in either the LHS | RHS.
2046 KnownOne |= KnownOne2;
2049 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2050 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2052 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2053 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2054 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2055 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2056 KnownZero = KnownZeroOut;
2060 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2061 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2063 // If low bits are zero in either operand, output low known-0 bits.
2064 // Also compute a conserative estimate for high known-0 bits.
2065 // More trickiness is possible, but this is sufficient for the
2066 // interesting case of alignment computation.
2067 KnownOne.clearAllBits();
2068 unsigned TrailZ = KnownZero.countTrailingOnes() +
2069 KnownZero2.countTrailingOnes();
2070 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2071 KnownZero2.countLeadingOnes(),
2072 BitWidth) - BitWidth;
2074 TrailZ = std::min(TrailZ, BitWidth);
2075 LeadZ = std::min(LeadZ, BitWidth);
2076 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2077 APInt::getHighBitsSet(BitWidth, LeadZ);
2081 // For the purposes of computing leading zeros we can conservatively
2082 // treat a udiv as a logical right shift by the power of 2 known to
2083 // be less than the denominator.
2084 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2085 unsigned LeadZ = KnownZero2.countLeadingOnes();
2087 KnownOne2.clearAllBits();
2088 KnownZero2.clearAllBits();
2089 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2090 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2091 if (RHSUnknownLeadingOnes != BitWidth)
2092 LeadZ = std::min(BitWidth,
2093 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2095 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2099 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2100 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2102 // Only known if known in both the LHS and RHS.
2103 KnownOne &= KnownOne2;
2104 KnownZero &= KnownZero2;
2106 case ISD::SELECT_CC:
2107 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2108 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2110 // Only known if known in both the LHS and RHS.
2111 KnownOne &= KnownOne2;
2112 KnownZero &= KnownZero2;
2120 if (Op.getResNo() != 1)
2122 // The boolean result conforms to getBooleanContents.
2123 // If we know the result of a setcc has the top bits zero, use this info.
2124 // We know that we have an integer-based boolean since these operations
2125 // are only available for integer.
2126 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2127 TargetLowering::ZeroOrOneBooleanContent &&
2129 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2132 // If we know the result of a setcc has the top bits zero, use this info.
2133 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2134 TargetLowering::ZeroOrOneBooleanContent &&
2136 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2139 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2140 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2141 unsigned ShAmt = SA->getZExtValue();
2143 // If the shift count is an invalid immediate, don't do anything.
2144 if (ShAmt >= BitWidth)
2147 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2148 KnownZero <<= ShAmt;
2150 // low bits known zero.
2151 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2155 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2156 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2157 unsigned ShAmt = SA->getZExtValue();
2159 // If the shift count is an invalid immediate, don't do anything.
2160 if (ShAmt >= BitWidth)
2163 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2164 KnownZero = KnownZero.lshr(ShAmt);
2165 KnownOne = KnownOne.lshr(ShAmt);
2167 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2168 KnownZero |= HighBits; // High bits known zero.
2172 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2173 unsigned ShAmt = SA->getZExtValue();
2175 // If the shift count is an invalid immediate, don't do anything.
2176 if (ShAmt >= BitWidth)
2179 // If any of the demanded bits are produced by the sign extension, we also
2180 // demand the input sign bit.
2181 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2183 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2184 KnownZero = KnownZero.lshr(ShAmt);
2185 KnownOne = KnownOne.lshr(ShAmt);
2187 // Handle the sign bits.
2188 APInt SignBit = APInt::getSignBit(BitWidth);
2189 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2191 if (KnownZero.intersects(SignBit)) {
2192 KnownZero |= HighBits; // New bits are known zero.
2193 } else if (KnownOne.intersects(SignBit)) {
2194 KnownOne |= HighBits; // New bits are known one.
2198 case ISD::SIGN_EXTEND_INREG: {
2199 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2200 unsigned EBits = EVT.getScalarType().getSizeInBits();
2202 // Sign extension. Compute the demanded bits in the result that are not
2203 // present in the input.
2204 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2206 APInt InSignBit = APInt::getSignBit(EBits);
2207 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2209 // If the sign extended bits are demanded, we know that the sign
2211 InSignBit = InSignBit.zext(BitWidth);
2212 if (NewBits.getBoolValue())
2213 InputDemandedBits |= InSignBit;
2215 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2216 KnownOne &= InputDemandedBits;
2217 KnownZero &= InputDemandedBits;
2219 // If the sign bit of the input is known set or clear, then we know the
2220 // top bits of the result.
2221 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2222 KnownZero |= NewBits;
2223 KnownOne &= ~NewBits;
2224 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2225 KnownOne |= NewBits;
2226 KnownZero &= ~NewBits;
2227 } else { // Input sign bit unknown
2228 KnownZero &= ~NewBits;
2229 KnownOne &= ~NewBits;
2234 case ISD::CTTZ_ZERO_UNDEF:
2236 case ISD::CTLZ_ZERO_UNDEF:
2238 unsigned LowBits = Log2_32(BitWidth)+1;
2239 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2240 KnownOne.clearAllBits();
2244 LoadSDNode *LD = cast<LoadSDNode>(Op);
2245 // If this is a ZEXTLoad and we are looking at the loaded value.
2246 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2247 EVT VT = LD->getMemoryVT();
2248 unsigned MemBits = VT.getScalarType().getSizeInBits();
2249 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2250 } else if (const MDNode *Ranges = LD->getRanges()) {
2251 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2255 case ISD::ZERO_EXTEND: {
2256 EVT InVT = Op.getOperand(0).getValueType();
2257 unsigned InBits = InVT.getScalarType().getSizeInBits();
2258 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2259 KnownZero = KnownZero.trunc(InBits);
2260 KnownOne = KnownOne.trunc(InBits);
2261 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2262 KnownZero = KnownZero.zext(BitWidth);
2263 KnownOne = KnownOne.zext(BitWidth);
2264 KnownZero |= NewBits;
2267 case ISD::SIGN_EXTEND: {
2268 EVT InVT = Op.getOperand(0).getValueType();
2269 unsigned InBits = InVT.getScalarType().getSizeInBits();
2270 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2272 KnownZero = KnownZero.trunc(InBits);
2273 KnownOne = KnownOne.trunc(InBits);
2274 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2276 // Note if the sign bit is known to be zero or one.
2277 bool SignBitKnownZero = KnownZero.isNegative();
2278 bool SignBitKnownOne = KnownOne.isNegative();
2280 KnownZero = KnownZero.zext(BitWidth);
2281 KnownOne = KnownOne.zext(BitWidth);
2283 // If the sign bit is known zero or one, the top bits match.
2284 if (SignBitKnownZero)
2285 KnownZero |= NewBits;
2286 else if (SignBitKnownOne)
2287 KnownOne |= NewBits;
2290 case ISD::ANY_EXTEND: {
2291 EVT InVT = Op.getOperand(0).getValueType();
2292 unsigned InBits = InVT.getScalarType().getSizeInBits();
2293 KnownZero = KnownZero.trunc(InBits);
2294 KnownOne = KnownOne.trunc(InBits);
2295 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2296 KnownZero = KnownZero.zext(BitWidth);
2297 KnownOne = KnownOne.zext(BitWidth);
2300 case ISD::TRUNCATE: {
2301 EVT InVT = Op.getOperand(0).getValueType();
2302 unsigned InBits = InVT.getScalarType().getSizeInBits();
2303 KnownZero = KnownZero.zext(InBits);
2304 KnownOne = KnownOne.zext(InBits);
2305 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2306 KnownZero = KnownZero.trunc(BitWidth);
2307 KnownOne = KnownOne.trunc(BitWidth);
2310 case ISD::AssertZext: {
2311 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2312 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2313 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2314 KnownZero |= (~InMask);
2315 KnownOne &= (~KnownZero);
2319 // All bits are zero except the low bit.
2320 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2324 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2325 // We know that the top bits of C-X are clear if X contains less bits
2326 // than C (i.e. no wrap-around can happen). For example, 20-X is
2327 // positive if we can prove that X is >= 0 and < 16.
2328 if (CLHS->getAPIntValue().isNonNegative()) {
2329 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2330 // NLZ can't be BitWidth with no sign bit
2331 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2332 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2334 // If all of the MaskV bits are known to be zero, then we know the
2335 // output top bits are zero, because we now know that the output is
2337 if ((KnownZero2 & MaskV) == MaskV) {
2338 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2339 // Top bits known zero.
2340 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2348 // Output known-0 bits are known if clear or set in both the low clear bits
2349 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2350 // low 3 bits clear.
2351 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2352 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2354 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2355 KnownZeroOut = std::min(KnownZeroOut,
2356 KnownZero2.countTrailingOnes());
2358 if (Op.getOpcode() == ISD::ADD) {
2359 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2363 // With ADDE, a carry bit may be added in, so we can only use this
2364 // information if we know (at least) that the low two bits are clear. We
2365 // then return to the caller that the low bit is unknown but that other bits
2367 if (KnownZeroOut >= 2) // ADDE
2368 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2372 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2373 const APInt &RA = Rem->getAPIntValue().abs();
2374 if (RA.isPowerOf2()) {
2375 APInt LowBits = RA - 1;
2376 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2378 // The low bits of the first operand are unchanged by the srem.
2379 KnownZero = KnownZero2 & LowBits;
2380 KnownOne = KnownOne2 & LowBits;
2382 // If the first operand is non-negative or has all low bits zero, then
2383 // the upper bits are all zero.
2384 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2385 KnownZero |= ~LowBits;
2387 // If the first operand is negative and not all low bits are zero, then
2388 // the upper bits are all one.
2389 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2390 KnownOne |= ~LowBits;
2391 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2396 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397 const APInt &RA = Rem->getAPIntValue();
2398 if (RA.isPowerOf2()) {
2399 APInt LowBits = (RA - 1);
2400 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2402 // The upper bits are all zero, the lower ones are unchanged.
2403 KnownZero = KnownZero2 | ~LowBits;
2404 KnownOne = KnownOne2 & LowBits;
2409 // Since the result is less than or equal to either operand, any leading
2410 // zero bits in either operand must also exist in the result.
2411 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2412 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2414 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2415 KnownZero2.countLeadingOnes());
2416 KnownOne.clearAllBits();
2417 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2420 case ISD::EXTRACT_ELEMENT: {
2421 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2422 const unsigned Index =
2423 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2424 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2426 // Remove low part of known bits mask
2427 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2428 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2430 // Remove high part of known bit mask
2431 KnownZero = KnownZero.trunc(BitWidth);
2432 KnownOne = KnownOne.trunc(BitWidth);
2435 case ISD::FrameIndex:
2436 case ISD::TargetFrameIndex:
2437 if (unsigned Align = InferPtrAlignment(Op)) {
2438 // The low bits are known zero if the pointer is aligned.
2439 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2445 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2448 case ISD::INTRINSIC_WO_CHAIN:
2449 case ISD::INTRINSIC_W_CHAIN:
2450 case ISD::INTRINSIC_VOID:
2451 // Allow the target to implement this method for its nodes.
2452 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2456 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2459 /// ComputeNumSignBits - Return the number of times the sign bit of the
2460 /// register is replicated into the other bits. We know that at least 1 bit
2461 /// is always equal to the sign bit (itself), but other cases can give us
2462 /// information. For example, immediately after an "SRA X, 2", we know that
2463 /// the top 3 bits are all equal to each other, so we return 3.
2464 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2465 EVT VT = Op.getValueType();
2466 assert(VT.isInteger() && "Invalid VT!");
2467 unsigned VTBits = VT.getScalarType().getSizeInBits();
2469 unsigned FirstAnswer = 1;
2472 return 1; // Limit search depth.
2474 switch (Op.getOpcode()) {
2476 case ISD::AssertSext:
2477 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2478 return VTBits-Tmp+1;
2479 case ISD::AssertZext:
2480 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2483 case ISD::Constant: {
2484 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2485 return Val.getNumSignBits();
2488 case ISD::SIGN_EXTEND:
2490 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2491 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2493 case ISD::SIGN_EXTEND_INREG:
2494 // Max of the input and what this extends.
2496 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2499 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2500 return std::max(Tmp, Tmp2);
2503 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2504 // SRA X, C -> adds C sign bits.
2505 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2506 Tmp += C->getZExtValue();
2507 if (Tmp > VTBits) Tmp = VTBits;
2511 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2512 // shl destroys sign bits.
2513 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2514 if (C->getZExtValue() >= VTBits || // Bad shift.
2515 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2516 return Tmp - C->getZExtValue();
2521 case ISD::XOR: // NOT is handled here.
2522 // Logical binary ops preserve the number of sign bits at the worst.
2523 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2525 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2526 FirstAnswer = std::min(Tmp, Tmp2);
2527 // We computed what we know about the sign bits as our first
2528 // answer. Now proceed to the generic code that uses
2529 // computeKnownBits, and pick whichever answer is better.
2534 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2535 if (Tmp == 1) return 1; // Early out.
2536 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2537 return std::min(Tmp, Tmp2);
2545 if (Op.getResNo() != 1)
2547 // The boolean result conforms to getBooleanContents. Fall through.
2548 // If setcc returns 0/-1, all bits are sign bits.
2549 // We know that we have an integer-based boolean since these operations
2550 // are only available for integer.
2551 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2552 TargetLowering::ZeroOrNegativeOneBooleanContent)
2556 // If setcc returns 0/-1, all bits are sign bits.
2557 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2558 TargetLowering::ZeroOrNegativeOneBooleanContent)
2563 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2564 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2566 // Handle rotate right by N like a rotate left by 32-N.
2567 if (Op.getOpcode() == ISD::ROTR)
2568 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2570 // If we aren't rotating out all of the known-in sign bits, return the
2571 // number that are left. This handles rotl(sext(x), 1) for example.
2572 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2573 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2577 // Add can have at most one carry bit. Thus we know that the output
2578 // is, at worst, one more bit than the inputs.
2579 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2580 if (Tmp == 1) return 1; // Early out.
2582 // Special case decrementing a value (ADD X, -1):
2583 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2584 if (CRHS->isAllOnesValue()) {
2585 APInt KnownZero, KnownOne;
2586 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2588 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2590 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2593 // If we are subtracting one from a positive number, there is no carry
2594 // out of the result.
2595 if (KnownZero.isNegative())
2599 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2600 if (Tmp2 == 1) return 1;
2601 return std::min(Tmp, Tmp2)-1;
2604 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2605 if (Tmp2 == 1) return 1;
2608 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2609 if (CLHS->isNullValue()) {
2610 APInt KnownZero, KnownOne;
2611 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2612 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2614 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2617 // If the input is known to be positive (the sign bit is known clear),
2618 // the output of the NEG has the same number of sign bits as the input.
2619 if (KnownZero.isNegative())
2622 // Otherwise, we treat this like a SUB.
2625 // Sub can have at most one carry bit. Thus we know that the output
2626 // is, at worst, one more bit than the inputs.
2627 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2628 if (Tmp == 1) return 1; // Early out.
2629 return std::min(Tmp, Tmp2)-1;
2631 // FIXME: it's tricky to do anything useful for this, but it is an important
2632 // case for targets like X86.
2634 case ISD::EXTRACT_ELEMENT: {
2635 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2636 const int BitWidth = Op.getValueType().getSizeInBits();
2638 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2640 // Get reverse index (starting from 1), Op1 value indexes elements from
2641 // little end. Sign starts at big end.
2642 const int rIndex = Items - 1 -
2643 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2645 // If the sign portion ends in our element the substraction gives correct
2646 // result. Otherwise it gives either negative or > bitwidth result
2647 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2651 // If we are looking at the loaded value of the SDNode.
2652 if (Op.getResNo() == 0) {
2653 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2654 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2655 unsigned ExtType = LD->getExtensionType();
2658 case ISD::SEXTLOAD: // '17' bits known
2659 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2660 return VTBits-Tmp+1;
2661 case ISD::ZEXTLOAD: // '16' bits known
2662 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2668 // Allow the target to implement this method for its nodes.
2669 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2670 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2671 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2672 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2673 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2674 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2677 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2678 // use this information.
2679 APInt KnownZero, KnownOne;
2680 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2683 if (KnownZero.isNegative()) { // sign bit is 0
2685 } else if (KnownOne.isNegative()) { // sign bit is 1;
2692 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2693 // the number of identical bits in the top of the input value.
2695 Mask <<= Mask.getBitWidth()-VTBits;
2696 // Return # leading zeros. We use 'min' here in case Val was zero before
2697 // shifting. We don't want to return '64' as for an i32 "0".
2698 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2701 /// isBaseWithConstantOffset - Return true if the specified operand is an
2702 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2703 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2704 /// semantics as an ADD. This handles the equivalence:
2705 /// X|Cst == X+Cst iff X&Cst = 0.
2706 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2707 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2708 !isa<ConstantSDNode>(Op.getOperand(1)))
2711 if (Op.getOpcode() == ISD::OR &&
2712 !MaskedValueIsZero(Op.getOperand(0),
2713 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2720 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2721 // If we're told that NaNs won't happen, assume they won't.
2722 if (getTarget().Options.NoNaNsFPMath)
2725 // If the value is a constant, we can obviously see if it is a NaN or not.
2726 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2727 return !C->getValueAPF().isNaN();
2729 // TODO: Recognize more cases here.
2734 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2735 // If the value is a constant, we can obviously see if it is a zero or not.
2736 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2737 return !C->isZero();
2739 // TODO: Recognize more cases here.
2740 switch (Op.getOpcode()) {
2743 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2744 return !C->isNullValue();
2751 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2752 // Check the obvious case.
2753 if (A == B) return true;
2755 // For for negative and positive zero.
2756 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2757 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2758 if (CA->isZero() && CB->isZero()) return true;
2760 // Otherwise they may not be equal.
2764 /// getNode - Gets or creates the specified node.
2766 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2767 FoldingSetNodeID ID;
2768 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2770 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2771 return SDValue(E, 0);
2773 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2774 DL.getDebugLoc(), getVTList(VT));
2775 CSEMap.InsertNode(N, IP);
2778 return SDValue(N, 0);
2781 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2782 EVT VT, SDValue Operand) {
2783 // Constant fold unary operations with an integer constant operand. Even
2784 // opaque constant will be folded, because the folding of unary operations
2785 // doesn't create new constants with different values. Nevertheless, the
2786 // opaque flag is preserved during folding to prevent future folding with
2788 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2789 const APInt &Val = C->getAPIntValue();
2792 case ISD::SIGN_EXTEND:
2793 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2794 C->isTargetOpcode(), C->isOpaque());
2795 case ISD::ANY_EXTEND:
2796 case ISD::ZERO_EXTEND:
2798 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2799 C->isTargetOpcode(), C->isOpaque());
2800 case ISD::UINT_TO_FP:
2801 case ISD::SINT_TO_FP: {
2802 APFloat apf(EVTToAPFloatSemantics(VT),
2803 APInt::getNullValue(VT.getSizeInBits()));
2804 (void)apf.convertFromAPInt(Val,
2805 Opcode==ISD::SINT_TO_FP,
2806 APFloat::rmNearestTiesToEven);
2807 return getConstantFP(apf, DL, VT);
2810 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2811 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2812 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2813 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2814 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2815 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2818 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2821 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2824 case ISD::CTLZ_ZERO_UNDEF:
2825 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2828 case ISD::CTTZ_ZERO_UNDEF:
2829 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2834 // Constant fold unary operations with a floating point constant operand.
2835 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2836 APFloat V = C->getValueAPF(); // make copy
2840 return getConstantFP(V, DL, VT);
2843 return getConstantFP(V, DL, VT);
2845 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2846 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2847 return getConstantFP(V, DL, VT);
2851 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2852 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2853 return getConstantFP(V, DL, VT);
2857 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2858 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2859 return getConstantFP(V, DL, VT);
2862 case ISD::FP_EXTEND: {
2864 // This can return overflow, underflow, or inexact; we don't care.
2865 // FIXME need to be more flexible about rounding mode.
2866 (void)V.convert(EVTToAPFloatSemantics(VT),
2867 APFloat::rmNearestTiesToEven, &ignored);
2868 return getConstantFP(V, DL, VT);
2870 case ISD::FP_TO_SINT:
2871 case ISD::FP_TO_UINT: {
2874 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2875 // FIXME need to be more flexible about rounding mode.
2876 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2877 Opcode==ISD::FP_TO_SINT,
2878 APFloat::rmTowardZero, &ignored);
2879 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2881 APInt api(VT.getSizeInBits(), x);
2882 return getConstant(api, DL, VT);
2885 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2886 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2887 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2888 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2889 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2890 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2895 // Constant fold unary operations with a vector integer or float operand.
2896 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2897 if (BV->isConstant()) {
2900 // FIXME: Entirely reasonable to perform folding of other unary
2901 // operations here as the need arises.
2908 case ISD::FP_EXTEND:
2909 case ISD::FP_TO_SINT:
2910 case ISD::FP_TO_UINT:
2912 case ISD::UINT_TO_FP:
2913 case ISD::SINT_TO_FP: {
2914 EVT SVT = VT.getScalarType();
2915 EVT InVT = BV->getValueType(0);
2916 EVT InSVT = InVT.getScalarType();
2918 // Find legal integer scalar type for constant promotion and
2919 // ensure that its scalar size is at least as large as source.
2921 if (SVT.isInteger()) {
2922 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2923 if (LegalSVT.bitsLT(SVT)) break;
2926 // Let the above scalar folding handle the folding of each element.
2927 SmallVector<SDValue, 8> Ops;
2928 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2929 SDValue OpN = BV->getOperand(i);
2930 EVT OpVT = OpN.getValueType();
2932 // Build vector (integer) scalar operands may need implicit
2933 // truncation - do this before constant folding.
2934 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2935 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2937 OpN = getNode(Opcode, DL, SVT, OpN);
2939 // Legalize the (integer) scalar constant if necessary.
2940 if (LegalSVT != SVT)
2941 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2943 if (OpN.getOpcode() != ISD::UNDEF &&
2944 OpN.getOpcode() != ISD::Constant &&
2945 OpN.getOpcode() != ISD::ConstantFP)
2949 if (Ops.size() == VT.getVectorNumElements())
2950 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2957 unsigned OpOpcode = Operand.getNode()->getOpcode();
2959 case ISD::TokenFactor:
2960 case ISD::MERGE_VALUES:
2961 case ISD::CONCAT_VECTORS:
2962 return Operand; // Factor, merge or concat of one node? No need.
2963 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2964 case ISD::FP_EXTEND:
2965 assert(VT.isFloatingPoint() &&
2966 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2967 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2968 assert((!VT.isVector() ||
2969 VT.getVectorNumElements() ==
2970 Operand.getValueType().getVectorNumElements()) &&
2971 "Vector element count mismatch!");
2972 if (Operand.getOpcode() == ISD::UNDEF)
2973 return getUNDEF(VT);
2975 case ISD::SIGN_EXTEND:
2976 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2977 "Invalid SIGN_EXTEND!");
2978 if (Operand.getValueType() == VT) return Operand; // noop extension
2979 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2980 "Invalid sext node, dst < src!");
2981 assert((!VT.isVector() ||
2982 VT.getVectorNumElements() ==
2983 Operand.getValueType().getVectorNumElements()) &&
2984 "Vector element count mismatch!");
2985 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2986 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2987 else if (OpOpcode == ISD::UNDEF)
2988 // sext(undef) = 0, because the top bits will all be the same.
2989 return getConstant(0, DL, VT);
2991 case ISD::ZERO_EXTEND:
2992 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2993 "Invalid ZERO_EXTEND!");
2994 if (Operand.getValueType() == VT) return Operand; // noop extension
2995 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2996 "Invalid zext node, dst < src!");
2997 assert((!VT.isVector() ||
2998 VT.getVectorNumElements() ==
2999 Operand.getValueType().getVectorNumElements()) &&
3000 "Vector element count mismatch!");
3001 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3002 return getNode(ISD::ZERO_EXTEND, DL, VT,
3003 Operand.getNode()->getOperand(0));
3004 else if (OpOpcode == ISD::UNDEF)
3005 // zext(undef) = 0, because the top bits will be zero.
3006 return getConstant(0, DL, VT);
3008 case ISD::ANY_EXTEND:
3009 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3010 "Invalid ANY_EXTEND!");
3011 if (Operand.getValueType() == VT) return Operand; // noop extension
3012 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3013 "Invalid anyext node, dst < src!");
3014 assert((!VT.isVector() ||
3015 VT.getVectorNumElements() ==
3016 Operand.getValueType().getVectorNumElements()) &&
3017 "Vector element count mismatch!");
3019 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3020 OpOpcode == ISD::ANY_EXTEND)
3021 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3022 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3023 else if (OpOpcode == ISD::UNDEF)
3024 return getUNDEF(VT);
3026 // (ext (trunx x)) -> x
3027 if (OpOpcode == ISD::TRUNCATE) {
3028 SDValue OpOp = Operand.getNode()->getOperand(0);
3029 if (OpOp.getValueType() == VT)
3034 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3035 "Invalid TRUNCATE!");
3036 if (Operand.getValueType() == VT) return Operand; // noop truncate
3037 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3038 "Invalid truncate node, src < dst!");
3039 assert((!VT.isVector() ||
3040 VT.getVectorNumElements() ==
3041 Operand.getValueType().getVectorNumElements()) &&
3042 "Vector element count mismatch!");
3043 if (OpOpcode == ISD::TRUNCATE)
3044 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3045 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3046 OpOpcode == ISD::ANY_EXTEND) {
3047 // If the source is smaller than the dest, we still need an extend.
3048 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3049 .bitsLT(VT.getScalarType()))
3050 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3051 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3052 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3053 return Operand.getNode()->getOperand(0);
3055 if (OpOpcode == ISD::UNDEF)
3056 return getUNDEF(VT);
3059 // Basic sanity checking.
3060 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3061 && "Cannot BITCAST between types of different sizes!");
3062 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3063 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3064 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3065 if (OpOpcode == ISD::UNDEF)
3066 return getUNDEF(VT);
3068 case ISD::SCALAR_TO_VECTOR:
3069 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3070 (VT.getVectorElementType() == Operand.getValueType() ||
3071 (VT.getVectorElementType().isInteger() &&
3072 Operand.getValueType().isInteger() &&
3073 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3074 "Illegal SCALAR_TO_VECTOR node!");
3075 if (OpOpcode == ISD::UNDEF)
3076 return getUNDEF(VT);
3077 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3078 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3079 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3080 Operand.getConstantOperandVal(1) == 0 &&
3081 Operand.getOperand(0).getValueType() == VT)
3082 return Operand.getOperand(0);
3085 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3086 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3087 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3088 Operand.getNode()->getOperand(0));
3089 if (OpOpcode == ISD::FNEG) // --X -> X
3090 return Operand.getNode()->getOperand(0);
3093 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3094 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3099 SDVTList VTs = getVTList(VT);
3100 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3101 FoldingSetNodeID ID;
3102 SDValue Ops[1] = { Operand };
3103 AddNodeIDNode(ID, Opcode, VTs, Ops);
3105 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3106 return SDValue(E, 0);
3108 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3109 DL.getDebugLoc(), VTs, Operand);
3110 CSEMap.InsertNode(N, IP);
3112 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3113 DL.getDebugLoc(), VTs, Operand);
3117 return SDValue(N, 0);
3120 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3123 case ISD::ADD: return std::make_pair(C1 + C2, true);
3124 case ISD::SUB: return std::make_pair(C1 - C2, true);
3125 case ISD::MUL: return std::make_pair(C1 * C2, true);
3126 case ISD::AND: return std::make_pair(C1 & C2, true);
3127 case ISD::OR: return std::make_pair(C1 | C2, true);
3128 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3129 case ISD::SHL: return std::make_pair(C1 << C2, true);
3130 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3131 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3132 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3133 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3135 if (!C2.getBoolValue())
3137 return std::make_pair(C1.udiv(C2), true);
3139 if (!C2.getBoolValue())
3141 return std::make_pair(C1.urem(C2), true);
3143 if (!C2.getBoolValue())
3145 return std::make_pair(C1.sdiv(C2), true);
3147 if (!C2.getBoolValue())
3149 return std::make_pair(C1.srem(C2), true);
3151 return std::make_pair(APInt(1, 0), false);
3154 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3155 const ConstantSDNode *Cst1,
3156 const ConstantSDNode *Cst2) {
3157 if (Cst1->isOpaque() || Cst2->isOpaque())
3160 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3161 Cst2->getAPIntValue());
3164 return getConstant(Folded.first, DL, VT);
3167 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3168 SDNode *Cst1, SDNode *Cst2) {
3169 // If the opcode is a target-specific ISD node, there's nothing we can
3170 // do here and the operand rules may not line up with the below, so
3172 if (Opcode >= ISD::BUILTIN_OP_END)
3175 // Handle the case of two scalars.
3176 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3177 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3178 if (SDValue Folded =
3179 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3182 SmallVector<SDValue, 4> Outputs;
3183 // We may have a vector type but a scalar result. Create a splat.
3184 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3185 // Build a big vector out of the scalar elements we generated.
3186 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3193 // For vectors extract each constant element into Inputs so we can constant
3194 // fold them individually.
3195 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3196 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3200 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3202 EVT SVT = VT.getScalarType();
3203 SmallVector<SDValue, 4> Outputs;
3204 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3205 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3206 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3207 if (!V1 || !V2) // Not a constant, bail.
3210 if (V1->isOpaque() || V2->isOpaque())
3213 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3214 // FIXME: This is valid and could be handled by truncating the APInts.
3215 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3218 // Fold one vector element.
3219 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3220 V2->getAPIntValue());
3223 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3226 assert(VT.getVectorNumElements() == Outputs.size() &&
3227 "Vector size mismatch!");
3229 // We may have a vector type but a scalar result. Create a splat.
3230 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3232 // Build a big vector out of the scalar elements we generated.
3233 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3236 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3237 SDValue N2, bool nuw, bool nsw, bool exact) {
3238 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3239 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3242 case ISD::TokenFactor:
3243 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3244 N2.getValueType() == MVT::Other && "Invalid token factor!");
3245 // Fold trivial token factors.
3246 if (N1.getOpcode() == ISD::EntryToken) return N2;
3247 if (N2.getOpcode() == ISD::EntryToken) return N1;
3248 if (N1 == N2) return N1;
3250 case ISD::CONCAT_VECTORS:
3251 // Concat of UNDEFs is UNDEF.
3252 if (N1.getOpcode() == ISD::UNDEF &&
3253 N2.getOpcode() == ISD::UNDEF)
3254 return getUNDEF(VT);
3256 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3257 // one big BUILD_VECTOR.
3258 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3259 N2.getOpcode() == ISD::BUILD_VECTOR) {
3260 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3261 N1.getNode()->op_end());
3262 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3264 // BUILD_VECTOR requires all inputs to be of the same type, find the
3265 // maximum type and extend them all.
3266 EVT SVT = VT.getScalarType();
3267 for (SDValue Op : Elts)
3268 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3269 if (SVT.bitsGT(VT.getScalarType()))
3270 for (SDValue &Op : Elts)
3271 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3272 ? getZExtOrTrunc(Op, DL, SVT)
3273 : getSExtOrTrunc(Op, DL, SVT);
3275 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3279 assert(VT.isInteger() && "This operator does not apply to FP types!");
3280 assert(N1.getValueType() == N2.getValueType() &&
3281 N1.getValueType() == VT && "Binary operator types must match!");
3282 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3283 // worth handling here.
3284 if (N2C && N2C->isNullValue())
3286 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3293 assert(VT.isInteger() && "This operator does not apply to FP types!");
3294 assert(N1.getValueType() == N2.getValueType() &&
3295 N1.getValueType() == VT && "Binary operator types must match!");
3296 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3297 // it's worth handling here.
3298 if (N2C && N2C->isNullValue())
3308 assert(VT.isInteger() && "This operator does not apply to FP types!");
3309 assert(N1.getValueType() == N2.getValueType() &&
3310 N1.getValueType() == VT && "Binary operator types must match!");
3317 if (getTarget().Options.UnsafeFPMath) {
3318 if (Opcode == ISD::FADD) {
3320 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3321 if (CFP->getValueAPF().isZero())
3324 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3325 if (CFP->getValueAPF().isZero())
3327 } else if (Opcode == ISD::FSUB) {
3329 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3330 if (CFP->getValueAPF().isZero())
3332 } else if (Opcode == ISD::FMUL) {
3333 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3336 // If the first operand isn't the constant, try the second
3338 CFP = dyn_cast<ConstantFPSDNode>(N2);
3345 return SDValue(CFP,0);
3347 if (CFP->isExactlyValue(1.0))
3352 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3353 assert(N1.getValueType() == N2.getValueType() &&
3354 N1.getValueType() == VT && "Binary operator types must match!");
3356 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3357 assert(N1.getValueType() == VT &&
3358 N1.getValueType().isFloatingPoint() &&
3359 N2.getValueType().isFloatingPoint() &&
3360 "Invalid FCOPYSIGN!");
3367 assert(VT == N1.getValueType() &&
3368 "Shift operators return type must be the same as their first arg");
3369 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3370 "Shifts only work on integers");
3371 assert((!VT.isVector() || VT == N2.getValueType()) &&
3372 "Vector shift amounts must be in the same as their first arg");
3373 // Verify that the shift amount VT is bit enough to hold valid shift
3374 // amounts. This catches things like trying to shift an i1024 value by an
3375 // i8, which is easy to fall into in generic code that uses
3376 // TLI.getShiftAmount().
3377 assert(N2.getValueType().getSizeInBits() >=
3378 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3379 "Invalid use of small shift amount with oversized value!");
3381 // Always fold shifts of i1 values so the code generator doesn't need to
3382 // handle them. Since we know the size of the shift has to be less than the
3383 // size of the value, the shift/rotate count is guaranteed to be zero.
3386 if (N2C && N2C->isNullValue())
3389 case ISD::FP_ROUND_INREG: {
3390 EVT EVT = cast<VTSDNode>(N2)->getVT();
3391 assert(VT == N1.getValueType() && "Not an inreg round!");
3392 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3393 "Cannot FP_ROUND_INREG integer types");
3394 assert(EVT.isVector() == VT.isVector() &&
3395 "FP_ROUND_INREG type should be vector iff the operand "
3397 assert((!EVT.isVector() ||
3398 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3399 "Vector element counts must match in FP_ROUND_INREG");
3400 assert(EVT.bitsLE(VT) && "Not rounding down!");
3402 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3406 assert(VT.isFloatingPoint() &&
3407 N1.getValueType().isFloatingPoint() &&
3408 VT.bitsLE(N1.getValueType()) &&
3409 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3410 if (N1.getValueType() == VT) return N1; // noop conversion.
3412 case ISD::AssertSext:
3413 case ISD::AssertZext: {
3414 EVT EVT = cast<VTSDNode>(N2)->getVT();
3415 assert(VT == N1.getValueType() && "Not an inreg extend!");
3416 assert(VT.isInteger() && EVT.isInteger() &&
3417 "Cannot *_EXTEND_INREG FP types");
3418 assert(!EVT.isVector() &&
3419 "AssertSExt/AssertZExt type should be the vector element type "
3420 "rather than the vector type!");
3421 assert(EVT.bitsLE(VT) && "Not extending!");
3422 if (VT == EVT) return N1; // noop assertion.
3425 case ISD::SIGN_EXTEND_INREG: {
3426 EVT EVT = cast<VTSDNode>(N2)->getVT();
3427 assert(VT == N1.getValueType() && "Not an inreg extend!");
3428 assert(VT.isInteger() && EVT.isInteger() &&
3429 "Cannot *_EXTEND_INREG FP types");
3430 assert(EVT.isVector() == VT.isVector() &&
3431 "SIGN_EXTEND_INREG type should be vector iff the operand "
3433 assert((!EVT.isVector() ||
3434 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3435 "Vector element counts must match in SIGN_EXTEND_INREG");
3436 assert(EVT.bitsLE(VT) && "Not extending!");
3437 if (EVT == VT) return N1; // Not actually extending
3439 auto SignExtendInReg = [&](APInt Val) {
3440 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3441 Val <<= Val.getBitWidth() - FromBits;
3442 Val = Val.ashr(Val.getBitWidth() - FromBits);
3443 return getConstant(Val, DL, VT.getScalarType());
3447 APInt Val = N1C->getAPIntValue();
3448 return SignExtendInReg(Val);
3450 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3451 SmallVector<SDValue, 8> Ops;
3452 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3453 SDValue Op = N1.getOperand(i);
3454 if (Op.getValueType() != VT.getScalarType()) break;
3455 if (Op.getOpcode() == ISD::UNDEF) {
3459 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3460 APInt Val = C->getAPIntValue();
3461 Ops.push_back(SignExtendInReg(Val));
3466 if (Ops.size() == VT.getVectorNumElements())
3467 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3471 case ISD::EXTRACT_VECTOR_ELT:
3472 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3473 if (N1.getOpcode() == ISD::UNDEF)
3474 return getUNDEF(VT);
3476 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3477 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3478 return getUNDEF(VT);
3480 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3481 // expanding copies of large vectors from registers.
3483 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3484 N1.getNumOperands() > 0) {
3486 N1.getOperand(0).getValueType().getVectorNumElements();
3487 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3488 N1.getOperand(N2C->getZExtValue() / Factor),
3489 getConstant(N2C->getZExtValue() % Factor, DL,
3490 N2.getValueType()));
3493 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3494 // expanding large vector constants.
3495 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3496 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3498 if (VT != Elt.getValueType())
3499 // If the vector element type is not legal, the BUILD_VECTOR operands
3500 // are promoted and implicitly truncated, and the result implicitly
3501 // extended. Make that explicit here.
3502 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3507 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3508 // operations are lowered to scalars.
3509 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3510 // If the indices are the same, return the inserted element else
3511 // if the indices are known different, extract the element from
3512 // the original vector.
3513 SDValue N1Op2 = N1.getOperand(2);
3514 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3516 if (N1Op2C && N2C) {
3517 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3518 if (VT == N1.getOperand(1).getValueType())
3519 return N1.getOperand(1);
3521 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3524 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3528 case ISD::EXTRACT_ELEMENT:
3529 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3530 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3531 (N1.getValueType().isInteger() == VT.isInteger()) &&
3532 N1.getValueType() != VT &&
3533 "Wrong types for EXTRACT_ELEMENT!");
3535 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3536 // 64-bit integers into 32-bit parts. Instead of building the extract of
3537 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3538 if (N1.getOpcode() == ISD::BUILD_PAIR)
3539 return N1.getOperand(N2C->getZExtValue());
3541 // EXTRACT_ELEMENT of a constant int is also very common.
3542 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3543 unsigned ElementSize = VT.getSizeInBits();
3544 unsigned Shift = ElementSize * N2C->getZExtValue();
3545 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3546 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3549 case ISD::EXTRACT_SUBVECTOR: {
3551 if (VT.isSimple() && N1.getValueType().isSimple()) {
3552 assert(VT.isVector() && N1.getValueType().isVector() &&
3553 "Extract subvector VTs must be a vectors!");
3554 assert(VT.getVectorElementType() ==
3555 N1.getValueType().getVectorElementType() &&
3556 "Extract subvector VTs must have the same element type!");
3557 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3558 "Extract subvector must be from larger vector to smaller vector!");
3560 if (isa<ConstantSDNode>(Index.getNode())) {
3561 assert((VT.getVectorNumElements() +
3562 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3563 <= N1.getValueType().getVectorNumElements())
3564 && "Extract subvector overflow!");
3567 // Trivial extraction.
3568 if (VT.getSimpleVT() == N1.getSimpleValueType())
3575 // Perform trivial constant folding.
3577 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3580 // Canonicalize constant to RHS if commutative.
3581 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3582 std::swap(N1C, N2C);
3586 // Constant fold FP operations.
3587 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3588 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3589 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3591 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3592 // Canonicalize constant to RHS if commutative.
3593 std::swap(N1CFP, N2CFP);
3596 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3597 APFloat::opStatus s;
3600 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3601 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3602 return getConstantFP(V1, DL, VT);
3605 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3606 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3607 return getConstantFP(V1, DL, VT);
3610 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3611 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3612 return getConstantFP(V1, DL, VT);
3615 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3616 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3617 s!=APFloat::opDivByZero)) {
3618 return getConstantFP(V1, DL, VT);
3622 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3623 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3624 s!=APFloat::opDivByZero)) {
3625 return getConstantFP(V1, DL, VT);
3628 case ISD::FCOPYSIGN:
3630 return getConstantFP(V1, DL, VT);
3635 if (Opcode == ISD::FP_ROUND) {
3636 APFloat V = N1CFP->getValueAPF(); // make copy
3638 // This can return overflow, underflow, or inexact; we don't care.
3639 // FIXME need to be more flexible about rounding mode.
3640 (void)V.convert(EVTToAPFloatSemantics(VT),
3641 APFloat::rmNearestTiesToEven, &ignored);
3642 return getConstantFP(V, DL, VT);
3646 // Canonicalize an UNDEF to the RHS, even over a constant.
3647 if (N1.getOpcode() == ISD::UNDEF) {
3648 if (isCommutativeBinOp(Opcode)) {
3652 case ISD::FP_ROUND_INREG:
3653 case ISD::SIGN_EXTEND_INREG:
3659 return N1; // fold op(undef, arg2) -> undef
3667 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3668 // For vectors, we can't easily build an all zero vector, just return
3675 // Fold a bunch of operators when the RHS is undef.
3676 if (N2.getOpcode() == ISD::UNDEF) {
3679 if (N1.getOpcode() == ISD::UNDEF)
3680 // Handle undef ^ undef -> 0 special case. This is a common
3682 return getConstant(0, DL, VT);
3692 return N2; // fold op(arg1, undef) -> undef
3698 if (getTarget().Options.UnsafeFPMath)
3706 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3707 // For vectors, we can't easily build an all zero vector, just return
3712 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3713 // For vectors, we can't easily build an all one vector, just return
3721 // Memoize this node if possible.
3723 SDVTList VTs = getVTList(VT);
3724 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3725 if (VT != MVT::Glue) {
3726 SDValue Ops[] = {N1, N2};
3727 FoldingSetNodeID ID;
3728 AddNodeIDNode(ID, Opcode, VTs, Ops);
3730 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3732 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3733 return SDValue(E, 0);
3735 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3737 CSEMap.InsertNode(N, IP);
3739 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3743 return SDValue(N, 0);
3746 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3747 SDValue N1, SDValue N2, SDValue N3) {
3748 // Perform various simplifications.
3749 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3752 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3753 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3754 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3755 if (N1CFP && N2CFP && N3CFP) {
3756 APFloat V1 = N1CFP->getValueAPF();
3757 const APFloat &V2 = N2CFP->getValueAPF();
3758 const APFloat &V3 = N3CFP->getValueAPF();
3759 APFloat::opStatus s =
3760 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3761 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3762 return getConstantFP(V1, DL, VT);
3766 case ISD::CONCAT_VECTORS:
3767 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3768 // one big BUILD_VECTOR.
3769 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3770 N2.getOpcode() == ISD::BUILD_VECTOR &&
3771 N3.getOpcode() == ISD::BUILD_VECTOR) {
3772 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3773 N1.getNode()->op_end());
3774 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3775 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3776 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3780 // Use FoldSetCC to simplify SETCC's.
3781 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3782 if (Simp.getNode()) return Simp;
3787 if (N1C->getZExtValue())
3788 return N2; // select true, X, Y -> X
3789 return N3; // select false, X, Y -> Y
3792 if (N2 == N3) return N2; // select C, X, X -> X
3794 case ISD::VECTOR_SHUFFLE:
3795 llvm_unreachable("should use getVectorShuffle constructor!");
3796 case ISD::INSERT_SUBVECTOR: {
3798 if (VT.isSimple() && N1.getValueType().isSimple()
3799 && N2.getValueType().isSimple()) {
3800 assert(VT.isVector() && N1.getValueType().isVector() &&
3801 N2.getValueType().isVector() &&
3802 "Insert subvector VTs must be a vectors");
3803 assert(VT == N1.getValueType() &&
3804 "Dest and insert subvector source types must match!");
3805 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3806 "Insert subvector must be from smaller vector to larger vector!");
3807 if (isa<ConstantSDNode>(Index.getNode())) {
3808 assert((N2.getValueType().getVectorNumElements() +
3809 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3810 <= VT.getVectorNumElements())
3811 && "Insert subvector overflow!");
3814 // Trivial insertion.
3815 if (VT.getSimpleVT() == N2.getSimpleValueType())
3821 // Fold bit_convert nodes from a type to themselves.
3822 if (N1.getValueType() == VT)
3827 // Memoize node if it doesn't produce a flag.
3829 SDVTList VTs = getVTList(VT);
3830 if (VT != MVT::Glue) {
3831 SDValue Ops[] = { N1, N2, N3 };
3832 FoldingSetNodeID ID;
3833 AddNodeIDNode(ID, Opcode, VTs, Ops);
3835 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3836 return SDValue(E, 0);
3838 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3839 DL.getDebugLoc(), VTs, N1, N2, N3);
3840 CSEMap.InsertNode(N, IP);
3842 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3843 DL.getDebugLoc(), VTs, N1, N2, N3);
3847 return SDValue(N, 0);
3850 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3851 SDValue N1, SDValue N2, SDValue N3,
3853 SDValue Ops[] = { N1, N2, N3, N4 };
3854 return getNode(Opcode, DL, VT, Ops);
3857 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3858 SDValue N1, SDValue N2, SDValue N3,
3859 SDValue N4, SDValue N5) {
3860 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3861 return getNode(Opcode, DL, VT, Ops);
3864 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3865 /// the incoming stack arguments to be loaded from the stack.
3866 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3867 SmallVector<SDValue, 8> ArgChains;
3869 // Include the original chain at the beginning of the list. When this is
3870 // used by target LowerCall hooks, this helps legalize find the
3871 // CALLSEQ_BEGIN node.
3872 ArgChains.push_back(Chain);
3874 // Add a chain value for each stack argument.
3875 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3876 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3877 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3878 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3879 if (FI->getIndex() < 0)
3880 ArgChains.push_back(SDValue(L, 1));
3882 // Build a tokenfactor for all the chains.
3883 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3886 /// getMemsetValue - Vectorized representation of the memset value
3888 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3890 assert(Value.getOpcode() != ISD::UNDEF);
3892 unsigned NumBits = VT.getScalarType().getSizeInBits();
3893 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3894 assert(C->getAPIntValue().getBitWidth() == 8);
3895 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3897 return DAG.getConstant(Val, dl, VT);
3898 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3902 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3903 EVT IntVT = VT.getScalarType();
3904 if (!IntVT.isInteger())
3905 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3907 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3909 // Use a multiplication with 0x010101... to extend the input to the
3911 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3912 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3913 DAG.getConstant(Magic, dl, IntVT));
3916 if (VT != Value.getValueType() && !VT.isInteger())
3917 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3918 if (VT != Value.getValueType()) {
3919 assert(VT.getVectorElementType() == Value.getValueType() &&
3920 "value type should be one vector element here");
3921 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3922 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3928 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3929 /// used when a memcpy is turned into a memset when the source is a constant
3931 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3932 const TargetLowering &TLI, StringRef Str) {
3933 // Handle vector with all elements zero.
3936 return DAG.getConstant(0, dl, VT);
3937 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3938 return DAG.getConstantFP(0.0, dl, VT);
3939 else if (VT.isVector()) {
3940 unsigned NumElts = VT.getVectorNumElements();
3941 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3942 return DAG.getNode(ISD::BITCAST, dl, VT,
3943 DAG.getConstant(0, dl,
3944 EVT::getVectorVT(*DAG.getContext(),
3947 llvm_unreachable("Expected type!");
3950 assert(!VT.isVector() && "Can't handle vector type here!");
3951 unsigned NumVTBits = VT.getSizeInBits();
3952 unsigned NumVTBytes = NumVTBits / 8;
3953 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3955 APInt Val(NumVTBits, 0);
3956 if (TLI.isLittleEndian()) {
3957 for (unsigned i = 0; i != NumBytes; ++i)
3958 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3960 for (unsigned i = 0; i != NumBytes; ++i)
3961 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3964 // If the "cost" of materializing the integer immediate is less than the cost
3965 // of a load, then it is cost effective to turn the load into the immediate.
3966 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3967 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3968 return DAG.getConstant(Val, dl, VT);
3969 return SDValue(nullptr, 0);
3972 /// getMemBasePlusOffset - Returns base and offset node for the
3974 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3975 SelectionDAG &DAG) {
3976 EVT VT = Base.getValueType();
3977 return DAG.getNode(ISD::ADD, dl,
3978 VT, Base, DAG.getConstant(Offset, dl, VT));
3981 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3983 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3984 unsigned SrcDelta = 0;
3985 GlobalAddressSDNode *G = nullptr;
3986 if (Src.getOpcode() == ISD::GlobalAddress)
3987 G = cast<GlobalAddressSDNode>(Src);
3988 else if (Src.getOpcode() == ISD::ADD &&
3989 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3990 Src.getOperand(1).getOpcode() == ISD::Constant) {
3991 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3992 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3997 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4000 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
4001 /// to replace the memset / memcpy. Return true if the number of memory ops
4002 /// is below the threshold. It returns the types of the sequence of
4003 /// memory ops to perform memset / memcpy by reference.
4004 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4005 unsigned Limit, uint64_t Size,
4006 unsigned DstAlign, unsigned SrcAlign,
4012 const TargetLowering &TLI) {
4013 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4014 "Expecting memcpy / memset source to meet alignment requirement!");
4015 // If 'SrcAlign' is zero, that means the memory operation does not need to
4016 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4017 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4018 // is the specified alignment of the memory operation. If it is zero, that
4019 // means it's possible to change the alignment of the destination.
4020 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4021 // not need to be loaded.
4022 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4023 IsMemset, ZeroMemset, MemcpyStrSrc,
4024 DAG.getMachineFunction());
4026 if (VT == MVT::Other) {
4028 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4029 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4030 VT = TLI.getPointerTy();
4032 switch (DstAlign & 7) {
4033 case 0: VT = MVT::i64; break;
4034 case 4: VT = MVT::i32; break;
4035 case 2: VT = MVT::i16; break;
4036 default: VT = MVT::i8; break;
4041 while (!TLI.isTypeLegal(LVT))
4042 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4043 assert(LVT.isInteger());
4049 unsigned NumMemOps = 0;
4051 unsigned VTSize = VT.getSizeInBits() / 8;
4052 while (VTSize > Size) {
4053 // For now, only use non-vector load / store's for the left-over pieces.
4058 if (VT.isVector() || VT.isFloatingPoint()) {
4059 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4060 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4061 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4063 else if (NewVT == MVT::i64 &&
4064 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4065 TLI.isSafeMemOpType(MVT::f64)) {
4066 // i64 is usually not legal on 32-bit targets, but f64 may be.
4074 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4075 if (NewVT == MVT::i8)
4077 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4079 NewVTSize = NewVT.getSizeInBits() / 8;
4081 // If the new VT cannot cover all of the remaining bits, then consider
4082 // issuing a (or a pair of) unaligned and overlapping load / store.
4083 // FIXME: Only does this for 64-bit or more since we don't have proper
4084 // cost model for unaligned load / store.
4087 if (NumMemOps && AllowOverlap &&
4088 VTSize >= 8 && NewVTSize < Size &&
4089 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4097 if (++NumMemOps > Limit)
4100 MemOps.push_back(VT);
4107 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4108 SDValue Chain, SDValue Dst,
4109 SDValue Src, uint64_t Size,
4110 unsigned Align, bool isVol,
4112 MachinePointerInfo DstPtrInfo,
4113 MachinePointerInfo SrcPtrInfo) {
4114 // Turn a memcpy of undef to nop.
4115 if (Src.getOpcode() == ISD::UNDEF)
4118 // Expand memcpy to a series of load and store ops if the size operand falls
4119 // below a certain threshold.
4120 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4121 // rather than maybe a humongous number of loads and stores.
4122 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4123 std::vector<EVT> MemOps;
4124 bool DstAlignCanChange = false;
4125 MachineFunction &MF = DAG.getMachineFunction();
4126 MachineFrameInfo *MFI = MF.getFrameInfo();
4127 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4128 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4129 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4130 DstAlignCanChange = true;
4131 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4132 if (Align > SrcAlign)
4135 bool CopyFromStr = isMemSrcFromString(Src, Str);
4136 bool isZeroStr = CopyFromStr && Str.empty();
4137 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4139 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4140 (DstAlignCanChange ? 0 : Align),
4141 (isZeroStr ? 0 : SrcAlign),
4142 false, false, CopyFromStr, true, DAG, TLI))
4145 if (DstAlignCanChange) {
4146 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4147 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4149 // Don't promote to an alignment that would require dynamic stack
4151 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4152 if (!TRI->needsStackRealignment(MF))
4153 while (NewAlign > Align &&
4154 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4157 if (NewAlign > Align) {
4158 // Give the stack frame object a larger alignment if needed.
4159 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4160 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4165 SmallVector<SDValue, 8> OutChains;
4166 unsigned NumMemOps = MemOps.size();
4167 uint64_t SrcOff = 0, DstOff = 0;
4168 for (unsigned i = 0; i != NumMemOps; ++i) {
4170 unsigned VTSize = VT.getSizeInBits() / 8;
4171 SDValue Value, Store;
4173 if (VTSize > Size) {
4174 // Issuing an unaligned load / store pair that overlaps with the previous
4175 // pair. Adjust the offset accordingly.
4176 assert(i == NumMemOps-1 && i != 0);
4177 SrcOff -= VTSize - Size;
4178 DstOff -= VTSize - Size;
4182 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4183 // It's unlikely a store of a vector immediate can be done in a single
4184 // instruction. It would require a load from a constantpool first.
4185 // We only handle zero vectors here.
4186 // FIXME: Handle other cases where store of vector immediate is done in
4187 // a single instruction.
4188 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4189 if (Value.getNode())
4190 Store = DAG.getStore(Chain, dl, Value,
4191 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4192 DstPtrInfo.getWithOffset(DstOff), isVol,
4196 if (!Store.getNode()) {
4197 // The type might not be legal for the target. This should only happen
4198 // if the type is smaller than a legal type, as on PPC, so the right
4199 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4200 // to Load/Store if NVT==VT.
4201 // FIXME does the case above also need this?
4202 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4203 assert(NVT.bitsGE(VT));
4204 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4205 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4206 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4207 false, MinAlign(SrcAlign, SrcOff));
4208 Store = DAG.getTruncStore(Chain, dl, Value,
4209 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4210 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4213 OutChains.push_back(Store);
4219 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4222 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4223 SDValue Chain, SDValue Dst,
4224 SDValue Src, uint64_t Size,
4225 unsigned Align, bool isVol,
4227 MachinePointerInfo DstPtrInfo,
4228 MachinePointerInfo SrcPtrInfo) {
4229 // Turn a memmove of undef to nop.
4230 if (Src.getOpcode() == ISD::UNDEF)
4233 // Expand memmove to a series of load and store ops if the size operand falls
4234 // below a certain threshold.
4235 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4236 std::vector<EVT> MemOps;
4237 bool DstAlignCanChange = false;
4238 MachineFunction &MF = DAG.getMachineFunction();
4239 MachineFrameInfo *MFI = MF.getFrameInfo();
4240 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4241 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4242 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4243 DstAlignCanChange = true;
4244 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4245 if (Align > SrcAlign)
4247 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4249 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4250 (DstAlignCanChange ? 0 : Align), SrcAlign,
4251 false, false, false, false, DAG, TLI))
4254 if (DstAlignCanChange) {
4255 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4256 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4257 if (NewAlign > Align) {
4258 // Give the stack frame object a larger alignment if needed.
4259 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4260 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4265 uint64_t SrcOff = 0, DstOff = 0;
4266 SmallVector<SDValue, 8> LoadValues;
4267 SmallVector<SDValue, 8> LoadChains;
4268 SmallVector<SDValue, 8> OutChains;
4269 unsigned NumMemOps = MemOps.size();
4270 for (unsigned i = 0; i < NumMemOps; i++) {
4272 unsigned VTSize = VT.getSizeInBits() / 8;
4275 Value = DAG.getLoad(VT, dl, Chain,
4276 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4277 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4278 false, false, SrcAlign);
4279 LoadValues.push_back(Value);
4280 LoadChains.push_back(Value.getValue(1));
4283 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4285 for (unsigned i = 0; i < NumMemOps; i++) {
4287 unsigned VTSize = VT.getSizeInBits() / 8;
4290 Store = DAG.getStore(Chain, dl, LoadValues[i],
4291 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4292 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4293 OutChains.push_back(Store);
4297 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4300 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4303 /// \param DAG Selection DAG where lowered code is placed.
4304 /// \param dl Link to corresponding IR location.
4305 /// \param Chain Control flow dependency.
4306 /// \param Dst Pointer to destination memory location.
4307 /// \param Src Value of byte to write into the memory.
4308 /// \param Size Number of bytes to write.
4309 /// \param Align Alignment of the destination in bytes.
4310 /// \param isVol True if destination is volatile.
4311 /// \param DstPtrInfo IR information on the memory pointer.
4312 /// \returns New head in the control flow, if lowering was successful, empty
4313 /// SDValue otherwise.
4315 /// The function tries to replace 'llvm.memset' intrinsic with several store
4316 /// operations and value calculation code. This is usually profitable for small
4318 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4319 SDValue Chain, SDValue Dst,
4320 SDValue Src, uint64_t Size,
4321 unsigned Align, bool isVol,
4322 MachinePointerInfo DstPtrInfo) {
4323 // Turn a memset of undef to nop.
4324 if (Src.getOpcode() == ISD::UNDEF)
4327 // Expand memset to a series of load/store ops if the size operand
4328 // falls below a certain threshold.
4329 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4330 std::vector<EVT> MemOps;
4331 bool DstAlignCanChange = false;
4332 MachineFunction &MF = DAG.getMachineFunction();
4333 MachineFrameInfo *MFI = MF.getFrameInfo();
4334 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4335 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4336 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4337 DstAlignCanChange = true;
4339 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4340 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4341 Size, (DstAlignCanChange ? 0 : Align), 0,
4342 true, IsZeroVal, false, true, DAG, TLI))
4345 if (DstAlignCanChange) {
4346 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4347 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4348 if (NewAlign > Align) {
4349 // Give the stack frame object a larger alignment if needed.
4350 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4351 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4356 SmallVector<SDValue, 8> OutChains;
4357 uint64_t DstOff = 0;
4358 unsigned NumMemOps = MemOps.size();
4360 // Find the largest store and generate the bit pattern for it.
4361 EVT LargestVT = MemOps[0];
4362 for (unsigned i = 1; i < NumMemOps; i++)
4363 if (MemOps[i].bitsGT(LargestVT))
4364 LargestVT = MemOps[i];
4365 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4367 for (unsigned i = 0; i < NumMemOps; i++) {
4369 unsigned VTSize = VT.getSizeInBits() / 8;
4370 if (VTSize > Size) {
4371 // Issuing an unaligned load / store pair that overlaps with the previous
4372 // pair. Adjust the offset accordingly.
4373 assert(i == NumMemOps-1 && i != 0);
4374 DstOff -= VTSize - Size;
4377 // If this store is smaller than the largest store see whether we can get
4378 // the smaller value for free with a truncate.
4379 SDValue Value = MemSetValue;
4380 if (VT.bitsLT(LargestVT)) {
4381 if (!LargestVT.isVector() && !VT.isVector() &&
4382 TLI.isTruncateFree(LargestVT, VT))
4383 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4385 Value = getMemsetValue(Src, VT, DAG, dl);
4387 assert(Value.getValueType() == VT && "Value with wrong type.");
4388 SDValue Store = DAG.getStore(Chain, dl, Value,
4389 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4390 DstPtrInfo.getWithOffset(DstOff),
4391 isVol, false, Align);
4392 OutChains.push_back(Store);
4393 DstOff += VT.getSizeInBits() / 8;
4397 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4400 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4401 SDValue Src, SDValue Size,
4402 unsigned Align, bool isVol, bool AlwaysInline,
4403 bool isTailCall, MachinePointerInfo DstPtrInfo,
4404 MachinePointerInfo SrcPtrInfo) {
4405 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4407 // Check to see if we should lower the memcpy to loads and stores first.
4408 // For cases within the target-specified limits, this is the best choice.
4409 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4411 // Memcpy with size zero? Just return the original chain.
4412 if (ConstantSize->isNullValue())
4415 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4416 ConstantSize->getZExtValue(),Align,
4417 isVol, false, DstPtrInfo, SrcPtrInfo);
4418 if (Result.getNode())
4422 // Then check to see if we should lower the memcpy with target-specific
4423 // code. If the target chooses to do this, this is the next best.
4425 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4426 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4427 DstPtrInfo, SrcPtrInfo);
4428 if (Result.getNode())
4432 // If we really need inline code and the target declined to provide it,
4433 // use a (potentially long) sequence of loads and stores.
4435 assert(ConstantSize && "AlwaysInline requires a constant size!");
4436 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4437 ConstantSize->getZExtValue(), Align, isVol,
4438 true, DstPtrInfo, SrcPtrInfo);
4441 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4442 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4443 // respect volatile, so they may do things like read or write memory
4444 // beyond the given memory regions. But fixing this isn't easy, and most
4445 // people don't care.
4447 // Emit a library call.
4448 TargetLowering::ArgListTy Args;
4449 TargetLowering::ArgListEntry Entry;
4450 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4451 Entry.Node = Dst; Args.push_back(Entry);
4452 Entry.Node = Src; Args.push_back(Entry);
4453 Entry.Node = Size; Args.push_back(Entry);
4454 // FIXME: pass in SDLoc
4455 TargetLowering::CallLoweringInfo CLI(*this);
4456 CLI.setDebugLoc(dl).setChain(Chain)
4457 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4458 Type::getVoidTy(*getContext()),
4459 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4460 TLI->getPointerTy()), std::move(Args), 0)
4462 .setTailCall(isTailCall);
4464 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4465 return CallResult.second;
4468 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4469 SDValue Src, SDValue Size,
4470 unsigned Align, bool isVol, bool isTailCall,
4471 MachinePointerInfo DstPtrInfo,
4472 MachinePointerInfo SrcPtrInfo) {
4473 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4475 // Check to see if we should lower the memmove to loads and stores first.
4476 // For cases within the target-specified limits, this is the best choice.
4477 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4479 // Memmove with size zero? Just return the original chain.
4480 if (ConstantSize->isNullValue())
4484 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4485 ConstantSize->getZExtValue(), Align, isVol,
4486 false, DstPtrInfo, SrcPtrInfo);
4487 if (Result.getNode())
4491 // Then check to see if we should lower the memmove with target-specific
4492 // code. If the target chooses to do this, this is the next best.
4494 SDValue Result = TSI->EmitTargetCodeForMemmove(
4495 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4496 if (Result.getNode())
4500 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4501 // not be safe. See memcpy above for more details.
4503 // Emit a library call.
4504 TargetLowering::ArgListTy Args;
4505 TargetLowering::ArgListEntry Entry;
4506 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4507 Entry.Node = Dst; Args.push_back(Entry);
4508 Entry.Node = Src; Args.push_back(Entry);
4509 Entry.Node = Size; Args.push_back(Entry);
4510 // FIXME: pass in SDLoc
4511 TargetLowering::CallLoweringInfo CLI(*this);
4512 CLI.setDebugLoc(dl).setChain(Chain)
4513 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4514 Type::getVoidTy(*getContext()),
4515 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4516 TLI->getPointerTy()), std::move(Args), 0)
4518 .setTailCall(isTailCall);
4520 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4521 return CallResult.second;
4524 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4525 SDValue Src, SDValue Size,
4526 unsigned Align, bool isVol, bool isTailCall,
4527 MachinePointerInfo DstPtrInfo) {
4528 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4530 // Check to see if we should lower the memset to stores first.
4531 // For cases within the target-specified limits, this is the best choice.
4532 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4534 // Memset with size zero? Just return the original chain.
4535 if (ConstantSize->isNullValue())
4539 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4540 Align, isVol, DstPtrInfo);
4542 if (Result.getNode())
4546 // Then check to see if we should lower the memset with target-specific
4547 // code. If the target chooses to do this, this is the next best.
4549 SDValue Result = TSI->EmitTargetCodeForMemset(
4550 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4551 if (Result.getNode())
4555 // Emit a library call.
4556 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4557 TargetLowering::ArgListTy Args;
4558 TargetLowering::ArgListEntry Entry;
4559 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4560 Args.push_back(Entry);
4562 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4563 Args.push_back(Entry);
4565 Entry.Ty = IntPtrTy;
4566 Args.push_back(Entry);
4568 // FIXME: pass in SDLoc
4569 TargetLowering::CallLoweringInfo CLI(*this);
4570 CLI.setDebugLoc(dl).setChain(Chain)
4571 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4572 Type::getVoidTy(*getContext()),
4573 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4574 TLI->getPointerTy()), std::move(Args), 0)
4576 .setTailCall(isTailCall);
4578 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4579 return CallResult.second;
4582 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4583 SDVTList VTList, ArrayRef<SDValue> Ops,
4584 MachineMemOperand *MMO,
4585 AtomicOrdering SuccessOrdering,
4586 AtomicOrdering FailureOrdering,
4587 SynchronizationScope SynchScope) {
4588 FoldingSetNodeID ID;
4589 ID.AddInteger(MemVT.getRawBits());
4590 AddNodeIDNode(ID, Opcode, VTList, Ops);
4591 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4593 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4594 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4595 return SDValue(E, 0);
4598 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4599 // SDNode doesn't have access to it. This memory will be "leaked" when
4600 // the node is deallocated, but recovered when the allocator is released.
4601 // If the number of operands is less than 5 we use AtomicSDNode's internal
4603 unsigned NumOps = Ops.size();
4604 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4607 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4608 dl.getDebugLoc(), VTList, MemVT,
4609 Ops.data(), DynOps, NumOps, MMO,
4610 SuccessOrdering, FailureOrdering,
4612 CSEMap.InsertNode(N, IP);
4614 return SDValue(N, 0);
4617 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4618 SDVTList VTList, ArrayRef<SDValue> Ops,
4619 MachineMemOperand *MMO,
4620 AtomicOrdering Ordering,
4621 SynchronizationScope SynchScope) {
4622 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4623 Ordering, SynchScope);
4626 SDValue SelectionDAG::getAtomicCmpSwap(
4627 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4628 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4629 unsigned Alignment, AtomicOrdering SuccessOrdering,
4630 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4631 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4632 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4633 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4635 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4636 Alignment = getEVTAlignment(MemVT);
4638 MachineFunction &MF = getMachineFunction();
4640 // FIXME: Volatile isn't really correct; we should keep track of atomic
4641 // orderings in the memoperand.
4642 unsigned Flags = MachineMemOperand::MOVolatile;
4643 Flags |= MachineMemOperand::MOLoad;
4644 Flags |= MachineMemOperand::MOStore;
4646 MachineMemOperand *MMO =
4647 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4649 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4650 SuccessOrdering, FailureOrdering, SynchScope);
4653 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4654 SDVTList VTs, SDValue Chain, SDValue Ptr,
4655 SDValue Cmp, SDValue Swp,
4656 MachineMemOperand *MMO,
4657 AtomicOrdering SuccessOrdering,
4658 AtomicOrdering FailureOrdering,
4659 SynchronizationScope SynchScope) {
4660 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4661 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4662 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4664 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4665 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4666 SuccessOrdering, FailureOrdering, SynchScope);
4669 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4671 SDValue Ptr, SDValue Val,
4672 const Value* PtrVal,
4674 AtomicOrdering Ordering,
4675 SynchronizationScope SynchScope) {
4676 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4677 Alignment = getEVTAlignment(MemVT);
4679 MachineFunction &MF = getMachineFunction();
4680 // An atomic store does not load. An atomic load does not store.
4681 // (An atomicrmw obviously both loads and stores.)
4682 // For now, atomics are considered to be volatile always, and they are
4684 // FIXME: Volatile isn't really correct; we should keep track of atomic
4685 // orderings in the memoperand.
4686 unsigned Flags = MachineMemOperand::MOVolatile;
4687 if (Opcode != ISD::ATOMIC_STORE)
4688 Flags |= MachineMemOperand::MOLoad;
4689 if (Opcode != ISD::ATOMIC_LOAD)
4690 Flags |= MachineMemOperand::MOStore;
4692 MachineMemOperand *MMO =
4693 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4694 MemVT.getStoreSize(), Alignment);
4696 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4697 Ordering, SynchScope);
4700 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4702 SDValue Ptr, SDValue Val,
4703 MachineMemOperand *MMO,
4704 AtomicOrdering Ordering,
4705 SynchronizationScope SynchScope) {
4706 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4707 Opcode == ISD::ATOMIC_LOAD_SUB ||
4708 Opcode == ISD::ATOMIC_LOAD_AND ||
4709 Opcode == ISD::ATOMIC_LOAD_OR ||
4710 Opcode == ISD::ATOMIC_LOAD_XOR ||
4711 Opcode == ISD::ATOMIC_LOAD_NAND ||
4712 Opcode == ISD::ATOMIC_LOAD_MIN ||
4713 Opcode == ISD::ATOMIC_LOAD_MAX ||
4714 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4715 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4716 Opcode == ISD::ATOMIC_SWAP ||
4717 Opcode == ISD::ATOMIC_STORE) &&
4718 "Invalid Atomic Op");
4720 EVT VT = Val.getValueType();
4722 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4723 getVTList(VT, MVT::Other);
4724 SDValue Ops[] = {Chain, Ptr, Val};
4725 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4728 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4729 EVT VT, SDValue Chain,
4731 MachineMemOperand *MMO,
4732 AtomicOrdering Ordering,
4733 SynchronizationScope SynchScope) {
4734 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4736 SDVTList VTs = getVTList(VT, MVT::Other);
4737 SDValue Ops[] = {Chain, Ptr};
4738 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4741 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4742 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4743 if (Ops.size() == 1)
4746 SmallVector<EVT, 4> VTs;
4747 VTs.reserve(Ops.size());
4748 for (unsigned i = 0; i < Ops.size(); ++i)
4749 VTs.push_back(Ops[i].getValueType());
4750 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4754 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4755 ArrayRef<SDValue> Ops,
4756 EVT MemVT, MachinePointerInfo PtrInfo,
4757 unsigned Align, bool Vol,
4758 bool ReadMem, bool WriteMem, unsigned Size) {
4759 if (Align == 0) // Ensure that codegen never sees alignment 0
4760 Align = getEVTAlignment(MemVT);
4762 MachineFunction &MF = getMachineFunction();
4765 Flags |= MachineMemOperand::MOStore;
4767 Flags |= MachineMemOperand::MOLoad;
4769 Flags |= MachineMemOperand::MOVolatile;
4771 Size = MemVT.getStoreSize();
4772 MachineMemOperand *MMO =
4773 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4775 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4779 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4780 ArrayRef<SDValue> Ops, EVT MemVT,
4781 MachineMemOperand *MMO) {
4782 assert((Opcode == ISD::INTRINSIC_VOID ||
4783 Opcode == ISD::INTRINSIC_W_CHAIN ||
4784 Opcode == ISD::PREFETCH ||
4785 Opcode == ISD::LIFETIME_START ||
4786 Opcode == ISD::LIFETIME_END ||
4787 (Opcode <= INT_MAX &&
4788 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4789 "Opcode is not a memory-accessing opcode!");
4791 // Memoize the node unless it returns a flag.
4792 MemIntrinsicSDNode *N;
4793 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4794 FoldingSetNodeID ID;
4795 AddNodeIDNode(ID, Opcode, VTList, Ops);
4796 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4798 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4799 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4800 return SDValue(E, 0);
4803 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4804 dl.getDebugLoc(), VTList, Ops,
4806 CSEMap.InsertNode(N, IP);
4808 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4809 dl.getDebugLoc(), VTList, Ops,
4813 return SDValue(N, 0);
4816 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4817 /// MachinePointerInfo record from it. This is particularly useful because the
4818 /// code generator has many cases where it doesn't bother passing in a
4819 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4820 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4821 // If this is FI+Offset, we can model it.
4822 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4823 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4825 // If this is (FI+Offset1)+Offset2, we can model it.
4826 if (Ptr.getOpcode() != ISD::ADD ||
4827 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4828 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4829 return MachinePointerInfo();
4831 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4832 return MachinePointerInfo::getFixedStack(FI, Offset+
4833 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4836 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4837 /// MachinePointerInfo record from it. This is particularly useful because the
4838 /// code generator has many cases where it doesn't bother passing in a
4839 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4840 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4841 // If the 'Offset' value isn't a constant, we can't handle this.
4842 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4843 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4844 if (OffsetOp.getOpcode() == ISD::UNDEF)
4845 return InferPointerInfo(Ptr);
4846 return MachinePointerInfo();
4851 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4852 EVT VT, SDLoc dl, SDValue Chain,
4853 SDValue Ptr, SDValue Offset,
4854 MachinePointerInfo PtrInfo, EVT MemVT,
4855 bool isVolatile, bool isNonTemporal, bool isInvariant,
4856 unsigned Alignment, const AAMDNodes &AAInfo,
4857 const MDNode *Ranges) {
4858 assert(Chain.getValueType() == MVT::Other &&
4859 "Invalid chain type");
4860 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4861 Alignment = getEVTAlignment(VT);
4863 unsigned Flags = MachineMemOperand::MOLoad;
4865 Flags |= MachineMemOperand::MOVolatile;
4867 Flags |= MachineMemOperand::MONonTemporal;
4869 Flags |= MachineMemOperand::MOInvariant;
4871 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4873 if (PtrInfo.V.isNull())
4874 PtrInfo = InferPointerInfo(Ptr, Offset);
4876 MachineFunction &MF = getMachineFunction();
4877 MachineMemOperand *MMO =
4878 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4880 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4884 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4885 EVT VT, SDLoc dl, SDValue Chain,
4886 SDValue Ptr, SDValue Offset, EVT MemVT,
4887 MachineMemOperand *MMO) {
4889 ExtType = ISD::NON_EXTLOAD;
4890 } else if (ExtType == ISD::NON_EXTLOAD) {
4891 assert(VT == MemVT && "Non-extending load from different memory type!");
4894 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4895 "Should only be an extending load, not truncating!");
4896 assert(VT.isInteger() == MemVT.isInteger() &&
4897 "Cannot convert from FP to Int or Int -> FP!");
4898 assert(VT.isVector() == MemVT.isVector() &&
4899 "Cannot use an ext load to convert to or from a vector!");
4900 assert((!VT.isVector() ||
4901 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4902 "Cannot use an ext load to change the number of vector elements!");
4905 bool Indexed = AM != ISD::UNINDEXED;
4906 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4907 "Unindexed load with an offset!");
4909 SDVTList VTs = Indexed ?
4910 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4911 SDValue Ops[] = { Chain, Ptr, Offset };
4912 FoldingSetNodeID ID;
4913 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4914 ID.AddInteger(MemVT.getRawBits());
4915 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4916 MMO->isNonTemporal(),
4917 MMO->isInvariant()));
4918 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4920 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4921 cast<LoadSDNode>(E)->refineAlignment(MMO);
4922 return SDValue(E, 0);
4924 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4925 dl.getDebugLoc(), VTs, AM, ExtType,
4927 CSEMap.InsertNode(N, IP);
4929 return SDValue(N, 0);
4932 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4933 SDValue Chain, SDValue Ptr,
4934 MachinePointerInfo PtrInfo,
4935 bool isVolatile, bool isNonTemporal,
4936 bool isInvariant, unsigned Alignment,
4937 const AAMDNodes &AAInfo,
4938 const MDNode *Ranges) {
4939 SDValue Undef = getUNDEF(Ptr.getValueType());
4940 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4941 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4945 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4946 SDValue Chain, SDValue Ptr,
4947 MachineMemOperand *MMO) {
4948 SDValue Undef = getUNDEF(Ptr.getValueType());
4949 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4953 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4954 SDValue Chain, SDValue Ptr,
4955 MachinePointerInfo PtrInfo, EVT MemVT,
4956 bool isVolatile, bool isNonTemporal,
4957 bool isInvariant, unsigned Alignment,
4958 const AAMDNodes &AAInfo) {
4959 SDValue Undef = getUNDEF(Ptr.getValueType());
4960 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4961 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4966 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4967 SDValue Chain, SDValue Ptr, EVT MemVT,
4968 MachineMemOperand *MMO) {
4969 SDValue Undef = getUNDEF(Ptr.getValueType());
4970 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4975 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4976 SDValue Offset, ISD::MemIndexedMode AM) {
4977 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4978 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4979 "Load is already a indexed load!");
4980 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4981 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4982 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4983 false, LD->getAlignment());
4986 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4987 SDValue Ptr, MachinePointerInfo PtrInfo,
4988 bool isVolatile, bool isNonTemporal,
4989 unsigned Alignment, const AAMDNodes &AAInfo) {
4990 assert(Chain.getValueType() == MVT::Other &&
4991 "Invalid chain type");
4992 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4993 Alignment = getEVTAlignment(Val.getValueType());
4995 unsigned Flags = MachineMemOperand::MOStore;
4997 Flags |= MachineMemOperand::MOVolatile;
4999 Flags |= MachineMemOperand::MONonTemporal;
5001 if (PtrInfo.V.isNull())
5002 PtrInfo = InferPointerInfo(Ptr);
5004 MachineFunction &MF = getMachineFunction();
5005 MachineMemOperand *MMO =
5006 MF.getMachineMemOperand(PtrInfo, Flags,
5007 Val.getValueType().getStoreSize(), Alignment,
5010 return getStore(Chain, dl, Val, Ptr, MMO);
5013 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5014 SDValue Ptr, MachineMemOperand *MMO) {
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5017 EVT VT = Val.getValueType();
5018 SDVTList VTs = getVTList(MVT::Other);
5019 SDValue Undef = getUNDEF(Ptr.getValueType());
5020 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5021 FoldingSetNodeID ID;
5022 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5023 ID.AddInteger(VT.getRawBits());
5024 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5025 MMO->isNonTemporal(), MMO->isInvariant()));
5026 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5028 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5029 cast<StoreSDNode>(E)->refineAlignment(MMO);
5030 return SDValue(E, 0);
5032 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5033 dl.getDebugLoc(), VTs,
5034 ISD::UNINDEXED, false, VT, MMO);
5035 CSEMap.InsertNode(N, IP);
5037 return SDValue(N, 0);
5040 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5041 SDValue Ptr, MachinePointerInfo PtrInfo,
5042 EVT SVT,bool isVolatile, bool isNonTemporal,
5044 const AAMDNodes &AAInfo) {
5045 assert(Chain.getValueType() == MVT::Other &&
5046 "Invalid chain type");
5047 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5048 Alignment = getEVTAlignment(SVT);
5050 unsigned Flags = MachineMemOperand::MOStore;
5052 Flags |= MachineMemOperand::MOVolatile;
5054 Flags |= MachineMemOperand::MONonTemporal;
5056 if (PtrInfo.V.isNull())
5057 PtrInfo = InferPointerInfo(Ptr);
5059 MachineFunction &MF = getMachineFunction();
5060 MachineMemOperand *MMO =
5061 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5064 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5067 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5068 SDValue Ptr, EVT SVT,
5069 MachineMemOperand *MMO) {
5070 EVT VT = Val.getValueType();
5072 assert(Chain.getValueType() == MVT::Other &&
5073 "Invalid chain type");
5075 return getStore(Chain, dl, Val, Ptr, MMO);
5077 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5078 "Should only be a truncating store, not extending!");
5079 assert(VT.isInteger() == SVT.isInteger() &&
5080 "Can't do FP-INT conversion!");
5081 assert(VT.isVector() == SVT.isVector() &&
5082 "Cannot use trunc store to convert to or from a vector!");
5083 assert((!VT.isVector() ||
5084 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5085 "Cannot use trunc store to change the number of vector elements!");
5087 SDVTList VTs = getVTList(MVT::Other);
5088 SDValue Undef = getUNDEF(Ptr.getValueType());
5089 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5090 FoldingSetNodeID ID;
5091 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5092 ID.AddInteger(SVT.getRawBits());
5093 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5094 MMO->isNonTemporal(), MMO->isInvariant()));
5095 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5097 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5098 cast<StoreSDNode>(E)->refineAlignment(MMO);
5099 return SDValue(E, 0);
5101 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5102 dl.getDebugLoc(), VTs,
5103 ISD::UNINDEXED, true, SVT, MMO);
5104 CSEMap.InsertNode(N, IP);
5106 return SDValue(N, 0);
5110 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5111 SDValue Offset, ISD::MemIndexedMode AM) {
5112 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5113 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5114 "Store is already a indexed store!");
5115 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5116 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5117 FoldingSetNodeID ID;
5118 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5119 ID.AddInteger(ST->getMemoryVT().getRawBits());
5120 ID.AddInteger(ST->getRawSubclassData());
5121 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5123 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5124 return SDValue(E, 0);
5126 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5127 dl.getDebugLoc(), VTs, AM,
5128 ST->isTruncatingStore(),
5130 ST->getMemOperand());
5131 CSEMap.InsertNode(N, IP);
5133 return SDValue(N, 0);
5137 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5138 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5139 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5141 SDVTList VTs = getVTList(VT, MVT::Other);
5142 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5143 FoldingSetNodeID ID;
5144 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5145 ID.AddInteger(VT.getRawBits());
5146 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5148 MMO->isNonTemporal(),
5149 MMO->isInvariant()));
5150 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5152 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5153 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5154 return SDValue(E, 0);
5156 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5157 dl.getDebugLoc(), Ops, 4, VTs,
5159 CSEMap.InsertNode(N, IP);
5161 return SDValue(N, 0);
5164 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5165 SDValue Ptr, SDValue Mask, EVT MemVT,
5166 MachineMemOperand *MMO, bool isTrunc) {
5167 assert(Chain.getValueType() == MVT::Other &&
5168 "Invalid chain type");
5169 EVT VT = Val.getValueType();
5170 SDVTList VTs = getVTList(MVT::Other);
5171 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5172 FoldingSetNodeID ID;
5173 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5174 ID.AddInteger(VT.getRawBits());
5175 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5176 MMO->isNonTemporal(), MMO->isInvariant()));
5177 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5179 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5180 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5181 return SDValue(E, 0);
5183 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5184 dl.getDebugLoc(), Ops, 4,
5185 VTs, isTrunc, MemVT, MMO);
5186 CSEMap.InsertNode(N, IP);
5188 return SDValue(N, 0);
5192 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5193 ArrayRef<SDValue> Ops,
5194 MachineMemOperand *MMO) {
5196 FoldingSetNodeID ID;
5197 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5198 ID.AddInteger(VT.getRawBits());
5199 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5201 MMO->isNonTemporal(),
5202 MMO->isInvariant()));
5203 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5205 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5206 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5207 return SDValue(E, 0);
5209 MaskedGatherSDNode *N =
5210 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5212 CSEMap.InsertNode(N, IP);
5214 return SDValue(N, 0);
5217 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5218 ArrayRef<SDValue> Ops,
5219 MachineMemOperand *MMO) {
5220 FoldingSetNodeID ID;
5221 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5222 ID.AddInteger(VT.getRawBits());
5223 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5224 MMO->isNonTemporal(),
5225 MMO->isInvariant()));
5226 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5228 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5229 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5230 return SDValue(E, 0);
5233 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5235 CSEMap.InsertNode(N, IP);
5237 return SDValue(N, 0);
5240 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5241 SDValue Chain, SDValue Ptr,
5244 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5245 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5248 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5249 ArrayRef<SDUse> Ops) {
5250 switch (Ops.size()) {
5251 case 0: return getNode(Opcode, DL, VT);
5252 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5253 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5254 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5258 // Copy from an SDUse array into an SDValue array for use with
5259 // the regular getNode logic.
5260 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5261 return getNode(Opcode, DL, VT, NewOps);
5264 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5265 ArrayRef<SDValue> Ops) {
5266 unsigned NumOps = Ops.size();
5268 case 0: return getNode(Opcode, DL, VT);
5269 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5270 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5271 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5277 case ISD::SELECT_CC: {
5278 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5279 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5280 "LHS and RHS of condition must have same type!");
5281 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5282 "True and False arms of SelectCC must have same type!");
5283 assert(Ops[2].getValueType() == VT &&
5284 "select_cc node must be of same type as true and false value!");
5288 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5289 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5290 "LHS/RHS of comparison should match types!");
5297 SDVTList VTs = getVTList(VT);
5299 if (VT != MVT::Glue) {
5300 FoldingSetNodeID ID;
5301 AddNodeIDNode(ID, Opcode, VTs, Ops);
5304 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5305 return SDValue(E, 0);
5307 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5309 CSEMap.InsertNode(N, IP);
5311 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5316 return SDValue(N, 0);
5319 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5320 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5321 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5324 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5325 ArrayRef<SDValue> Ops) {
5326 if (VTList.NumVTs == 1)
5327 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5331 // FIXME: figure out how to safely handle things like
5332 // int foo(int x) { return 1 << (x & 255); }
5333 // int bar() { return foo(256); }
5334 case ISD::SRA_PARTS:
5335 case ISD::SRL_PARTS:
5336 case ISD::SHL_PARTS:
5337 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5338 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5339 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5340 else if (N3.getOpcode() == ISD::AND)
5341 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5342 // If the and is only masking out bits that cannot effect the shift,
5343 // eliminate the and.
5344 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5345 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5346 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5352 // Memoize the node unless it returns a flag.
5354 unsigned NumOps = Ops.size();
5355 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5356 FoldingSetNodeID ID;
5357 AddNodeIDNode(ID, Opcode, VTList, Ops);
5359 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5360 return SDValue(E, 0);
5363 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5364 DL.getDebugLoc(), VTList, Ops[0]);
5365 } else if (NumOps == 2) {
5366 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5367 DL.getDebugLoc(), VTList, Ops[0],
5369 } else if (NumOps == 3) {
5370 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5371 DL.getDebugLoc(), VTList, Ops[0],
5374 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5377 CSEMap.InsertNode(N, IP);
5380 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5381 DL.getDebugLoc(), VTList, Ops[0]);
5382 } else if (NumOps == 2) {
5383 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5384 DL.getDebugLoc(), VTList, Ops[0],
5386 } else if (NumOps == 3) {
5387 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5388 DL.getDebugLoc(), VTList, Ops[0],
5391 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5396 return SDValue(N, 0);
5399 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5400 return getNode(Opcode, DL, VTList, None);
5403 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5405 SDValue Ops[] = { N1 };
5406 return getNode(Opcode, DL, VTList, Ops);
5409 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5410 SDValue N1, SDValue N2) {
5411 SDValue Ops[] = { N1, N2 };
5412 return getNode(Opcode, DL, VTList, Ops);
5415 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5416 SDValue N1, SDValue N2, SDValue N3) {
5417 SDValue Ops[] = { N1, N2, N3 };
5418 return getNode(Opcode, DL, VTList, Ops);
5421 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5422 SDValue N1, SDValue N2, SDValue N3,
5424 SDValue Ops[] = { N1, N2, N3, N4 };
5425 return getNode(Opcode, DL, VTList, Ops);
5428 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5429 SDValue N1, SDValue N2, SDValue N3,
5430 SDValue N4, SDValue N5) {
5431 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5432 return getNode(Opcode, DL, VTList, Ops);
5435 SDVTList SelectionDAG::getVTList(EVT VT) {
5436 return makeVTList(SDNode::getValueTypeList(VT), 1);
5439 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5440 FoldingSetNodeID ID;
5442 ID.AddInteger(VT1.getRawBits());
5443 ID.AddInteger(VT2.getRawBits());
5446 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5448 EVT *Array = Allocator.Allocate<EVT>(2);
5451 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5452 VTListMap.InsertNode(Result, IP);
5454 return Result->getSDVTList();
5457 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5458 FoldingSetNodeID ID;
5460 ID.AddInteger(VT1.getRawBits());
5461 ID.AddInteger(VT2.getRawBits());
5462 ID.AddInteger(VT3.getRawBits());
5465 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5467 EVT *Array = Allocator.Allocate<EVT>(3);
5471 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5472 VTListMap.InsertNode(Result, IP);
5474 return Result->getSDVTList();
5477 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5478 FoldingSetNodeID ID;
5480 ID.AddInteger(VT1.getRawBits());
5481 ID.AddInteger(VT2.getRawBits());
5482 ID.AddInteger(VT3.getRawBits());
5483 ID.AddInteger(VT4.getRawBits());
5486 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5488 EVT *Array = Allocator.Allocate<EVT>(4);
5493 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5494 VTListMap.InsertNode(Result, IP);
5496 return Result->getSDVTList();
5499 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5500 unsigned NumVTs = VTs.size();
5501 FoldingSetNodeID ID;
5502 ID.AddInteger(NumVTs);
5503 for (unsigned index = 0; index < NumVTs; index++) {
5504 ID.AddInteger(VTs[index].getRawBits());
5508 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5510 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5511 std::copy(VTs.begin(), VTs.end(), Array);
5512 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5513 VTListMap.InsertNode(Result, IP);
5515 return Result->getSDVTList();
5519 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5520 /// specified operands. If the resultant node already exists in the DAG,
5521 /// this does not modify the specified node, instead it returns the node that
5522 /// already exists. If the resultant node does not exist in the DAG, the
5523 /// input node is returned. As a degenerate case, if you specify the same
5524 /// input operands as the node already has, the input node is returned.
5525 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5526 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5528 // Check to see if there is no change.
5529 if (Op == N->getOperand(0)) return N;
5531 // See if the modified node already exists.
5532 void *InsertPos = nullptr;
5533 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5536 // Nope it doesn't. Remove the node from its current place in the maps.
5538 if (!RemoveNodeFromCSEMaps(N))
5539 InsertPos = nullptr;
5541 // Now we update the operands.
5542 N->OperandList[0].set(Op);
5544 // If this gets put into a CSE map, add it.
5545 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5549 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5550 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5552 // Check to see if there is no change.
5553 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5554 return N; // No operands changed, just return the input node.
5556 // See if the modified node already exists.
5557 void *InsertPos = nullptr;
5558 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5561 // Nope it doesn't. Remove the node from its current place in the maps.
5563 if (!RemoveNodeFromCSEMaps(N))
5564 InsertPos = nullptr;
5566 // Now we update the operands.
5567 if (N->OperandList[0] != Op1)
5568 N->OperandList[0].set(Op1);
5569 if (N->OperandList[1] != Op2)
5570 N->OperandList[1].set(Op2);
5572 // If this gets put into a CSE map, add it.
5573 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5577 SDNode *SelectionDAG::
5578 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5579 SDValue Ops[] = { Op1, Op2, Op3 };
5580 return UpdateNodeOperands(N, Ops);
5583 SDNode *SelectionDAG::
5584 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5585 SDValue Op3, SDValue Op4) {
5586 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5587 return UpdateNodeOperands(N, Ops);
5590 SDNode *SelectionDAG::
5591 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5592 SDValue Op3, SDValue Op4, SDValue Op5) {
5593 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5594 return UpdateNodeOperands(N, Ops);
5597 SDNode *SelectionDAG::
5598 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5599 unsigned NumOps = Ops.size();
5600 assert(N->getNumOperands() == NumOps &&
5601 "Update with wrong number of operands");
5603 // If no operands changed just return the input node.
5604 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5607 // See if the modified node already exists.
5608 void *InsertPos = nullptr;
5609 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5612 // Nope it doesn't. Remove the node from its current place in the maps.
5614 if (!RemoveNodeFromCSEMaps(N))
5615 InsertPos = nullptr;
5617 // Now we update the operands.
5618 for (unsigned i = 0; i != NumOps; ++i)
5619 if (N->OperandList[i] != Ops[i])
5620 N->OperandList[i].set(Ops[i]);
5622 // If this gets put into a CSE map, add it.
5623 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5627 /// DropOperands - Release the operands and set this node to have
5629 void SDNode::DropOperands() {
5630 // Unlike the code in MorphNodeTo that does this, we don't need to
5631 // watch for dead nodes here.
5632 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5638 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5641 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5643 SDVTList VTs = getVTList(VT);
5644 return SelectNodeTo(N, MachineOpc, VTs, None);
5647 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5648 EVT VT, SDValue Op1) {
5649 SDVTList VTs = getVTList(VT);
5650 SDValue Ops[] = { Op1 };
5651 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5654 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5655 EVT VT, SDValue Op1,
5657 SDVTList VTs = getVTList(VT);
5658 SDValue Ops[] = { Op1, Op2 };
5659 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5662 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5663 EVT VT, SDValue Op1,
5664 SDValue Op2, SDValue Op3) {
5665 SDVTList VTs = getVTList(VT);
5666 SDValue Ops[] = { Op1, Op2, Op3 };
5667 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5670 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5671 EVT VT, ArrayRef<SDValue> Ops) {
5672 SDVTList VTs = getVTList(VT);
5673 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5676 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5677 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5678 SDVTList VTs = getVTList(VT1, VT2);
5679 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5682 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5684 SDVTList VTs = getVTList(VT1, VT2);
5685 return SelectNodeTo(N, MachineOpc, VTs, None);
5688 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5689 EVT VT1, EVT VT2, EVT VT3,
5690 ArrayRef<SDValue> Ops) {
5691 SDVTList VTs = getVTList(VT1, VT2, VT3);
5692 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5695 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5696 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5697 ArrayRef<SDValue> Ops) {
5698 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5699 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5702 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5705 SDVTList VTs = getVTList(VT1, VT2);
5706 SDValue Ops[] = { Op1 };
5707 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5710 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5712 SDValue Op1, SDValue Op2) {
5713 SDVTList VTs = getVTList(VT1, VT2);
5714 SDValue Ops[] = { Op1, Op2 };
5715 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5718 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5720 SDValue Op1, SDValue Op2,
5722 SDVTList VTs = getVTList(VT1, VT2);
5723 SDValue Ops[] = { Op1, Op2, Op3 };
5724 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5727 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5728 EVT VT1, EVT VT2, EVT VT3,
5729 SDValue Op1, SDValue Op2,
5731 SDVTList VTs = getVTList(VT1, VT2, VT3);
5732 SDValue Ops[] = { Op1, Op2, Op3 };
5733 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5736 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5737 SDVTList VTs,ArrayRef<SDValue> Ops) {
5738 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5739 // Reset the NodeID to -1.
5744 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5745 /// the line number information on the merged node since it is not possible to
5746 /// preserve the information that operation is associated with multiple lines.
5747 /// This will make the debugger working better at -O0, were there is a higher
5748 /// probability having other instructions associated with that line.
5750 /// For IROrder, we keep the smaller of the two
5751 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5752 DebugLoc NLoc = N->getDebugLoc();
5753 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5754 N->setDebugLoc(DebugLoc());
5756 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5757 N->setIROrder(Order);
5761 /// MorphNodeTo - This *mutates* the specified node to have the specified
5762 /// return type, opcode, and operands.
5764 /// Note that MorphNodeTo returns the resultant node. If there is already a
5765 /// node of the specified opcode and operands, it returns that node instead of
5766 /// the current one. Note that the SDLoc need not be the same.
5768 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5769 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5770 /// node, and because it doesn't require CSE recalculation for any of
5771 /// the node's users.
5773 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5774 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5775 /// the legalizer which maintain worklists that would need to be updated when
5776 /// deleting things.
5777 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5778 SDVTList VTs, ArrayRef<SDValue> Ops) {
5779 unsigned NumOps = Ops.size();
5780 // If an identical node already exists, use it.
5782 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5783 FoldingSetNodeID ID;
5784 AddNodeIDNode(ID, Opc, VTs, Ops);
5785 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5786 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5789 if (!RemoveNodeFromCSEMaps(N))
5792 // Start the morphing.
5794 N->ValueList = VTs.VTs;
5795 N->NumValues = VTs.NumVTs;
5797 // Clear the operands list, updating used nodes to remove this from their
5798 // use list. Keep track of any operands that become dead as a result.
5799 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5800 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5802 SDNode *Used = Use.getNode();
5804 if (Used->use_empty())
5805 DeadNodeSet.insert(Used);
5808 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5809 // Initialize the memory references information.
5810 MN->setMemRefs(nullptr, nullptr);
5811 // If NumOps is larger than the # of operands we can have in a
5812 // MachineSDNode, reallocate the operand list.
5813 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5814 if (MN->OperandsNeedDelete)
5815 delete[] MN->OperandList;
5816 if (NumOps > array_lengthof(MN->LocalOperands))
5817 // We're creating a final node that will live unmorphed for the
5818 // remainder of the current SelectionDAG iteration, so we can allocate
5819 // the operands directly out of a pool with no recycling metadata.
5820 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5821 Ops.data(), NumOps);
5823 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5824 MN->OperandsNeedDelete = false;
5826 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5828 // If NumOps is larger than the # of operands we currently have, reallocate
5829 // the operand list.
5830 if (NumOps > N->NumOperands) {
5831 if (N->OperandsNeedDelete)
5832 delete[] N->OperandList;
5833 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5834 N->OperandsNeedDelete = true;
5836 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5839 // Delete any nodes that are still dead after adding the uses for the
5841 if (!DeadNodeSet.empty()) {
5842 SmallVector<SDNode *, 16> DeadNodes;
5843 for (SDNode *N : DeadNodeSet)
5845 DeadNodes.push_back(N);
5846 RemoveDeadNodes(DeadNodes);
5850 CSEMap.InsertNode(N, IP); // Memoize the new node.
5855 /// getMachineNode - These are used for target selectors to create a new node
5856 /// with specified return type(s), MachineInstr opcode, and operands.
5858 /// Note that getMachineNode returns the resultant node. If there is already a
5859 /// node of the specified opcode and operands, it returns that node instead of
5860 /// the current one.
5862 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5863 SDVTList VTs = getVTList(VT);
5864 return getMachineNode(Opcode, dl, VTs, None);
5868 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5869 SDVTList VTs = getVTList(VT);
5870 SDValue Ops[] = { Op1 };
5871 return getMachineNode(Opcode, dl, VTs, Ops);
5875 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5876 SDValue Op1, SDValue Op2) {
5877 SDVTList VTs = getVTList(VT);
5878 SDValue Ops[] = { Op1, Op2 };
5879 return getMachineNode(Opcode, dl, VTs, Ops);
5883 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5884 SDValue Op1, SDValue Op2, SDValue Op3) {
5885 SDVTList VTs = getVTList(VT);
5886 SDValue Ops[] = { Op1, Op2, Op3 };
5887 return getMachineNode(Opcode, dl, VTs, Ops);
5891 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5892 ArrayRef<SDValue> Ops) {
5893 SDVTList VTs = getVTList(VT);
5894 return getMachineNode(Opcode, dl, VTs, Ops);
5898 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5899 SDVTList VTs = getVTList(VT1, VT2);
5900 return getMachineNode(Opcode, dl, VTs, None);
5904 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5905 EVT VT1, EVT VT2, SDValue Op1) {
5906 SDVTList VTs = getVTList(VT1, VT2);
5907 SDValue Ops[] = { Op1 };
5908 return getMachineNode(Opcode, dl, VTs, Ops);
5912 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5913 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5914 SDVTList VTs = getVTList(VT1, VT2);
5915 SDValue Ops[] = { Op1, Op2 };
5916 return getMachineNode(Opcode, dl, VTs, Ops);
5920 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5921 EVT VT1, EVT VT2, SDValue Op1,
5922 SDValue Op2, SDValue Op3) {
5923 SDVTList VTs = getVTList(VT1, VT2);
5924 SDValue Ops[] = { Op1, Op2, Op3 };
5925 return getMachineNode(Opcode, dl, VTs, Ops);
5929 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5931 ArrayRef<SDValue> Ops) {
5932 SDVTList VTs = getVTList(VT1, VT2);
5933 return getMachineNode(Opcode, dl, VTs, Ops);
5937 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5938 EVT VT1, EVT VT2, EVT VT3,
5939 SDValue Op1, SDValue Op2) {
5940 SDVTList VTs = getVTList(VT1, VT2, VT3);
5941 SDValue Ops[] = { Op1, Op2 };
5942 return getMachineNode(Opcode, dl, VTs, Ops);
5946 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5947 EVT VT1, EVT VT2, EVT VT3,
5948 SDValue Op1, SDValue Op2, SDValue Op3) {
5949 SDVTList VTs = getVTList(VT1, VT2, VT3);
5950 SDValue Ops[] = { Op1, Op2, Op3 };
5951 return getMachineNode(Opcode, dl, VTs, Ops);
5955 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5956 EVT VT1, EVT VT2, EVT VT3,
5957 ArrayRef<SDValue> Ops) {
5958 SDVTList VTs = getVTList(VT1, VT2, VT3);
5959 return getMachineNode(Opcode, dl, VTs, Ops);
5963 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5964 EVT VT2, EVT VT3, EVT VT4,
5965 ArrayRef<SDValue> Ops) {
5966 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5967 return getMachineNode(Opcode, dl, VTs, Ops);
5971 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5972 ArrayRef<EVT> ResultTys,
5973 ArrayRef<SDValue> Ops) {
5974 SDVTList VTs = getVTList(ResultTys);
5975 return getMachineNode(Opcode, dl, VTs, Ops);
5979 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5980 ArrayRef<SDValue> OpsArray) {
5981 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5984 const SDValue *Ops = OpsArray.data();
5985 unsigned NumOps = OpsArray.size();
5988 FoldingSetNodeID ID;
5989 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5991 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5992 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5996 // Allocate a new MachineSDNode.
5997 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5998 DL.getDebugLoc(), VTs);
6000 // Initialize the operands list.
6001 if (NumOps > array_lengthof(N->LocalOperands))
6002 // We're creating a final node that will live unmorphed for the
6003 // remainder of the current SelectionDAG iteration, so we can allocate
6004 // the operands directly out of a pool with no recycling metadata.
6005 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6008 N->InitOperands(N->LocalOperands, Ops, NumOps);
6009 N->OperandsNeedDelete = false;
6012 CSEMap.InsertNode(N, IP);
6018 /// getTargetExtractSubreg - A convenience function for creating
6019 /// TargetOpcode::EXTRACT_SUBREG nodes.
6021 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6023 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6024 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6025 VT, Operand, SRIdxVal);
6026 return SDValue(Subreg, 0);
6029 /// getTargetInsertSubreg - A convenience function for creating
6030 /// TargetOpcode::INSERT_SUBREG nodes.
6032 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6033 SDValue Operand, SDValue Subreg) {
6034 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6035 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6036 VT, Operand, Subreg, SRIdxVal);
6037 return SDValue(Result, 0);
6040 /// getNodeIfExists - Get the specified node if it's already available, or
6041 /// else return NULL.
6042 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6043 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6045 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6046 FoldingSetNodeID ID;
6047 AddNodeIDNode(ID, Opcode, VTList, Ops);
6048 if (isBinOpWithFlags(Opcode))
6049 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6051 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6057 /// getDbgValue - Creates a SDDbgValue node.
6060 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6061 unsigned R, bool IsIndirect, uint64_t Off,
6062 DebugLoc DL, unsigned O) {
6063 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6064 "Expected inlined-at fields to agree");
6065 return new (DbgInfo->getAlloc())
6066 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6070 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6071 const Value *C, uint64_t Off,
6072 DebugLoc DL, unsigned O) {
6073 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6074 "Expected inlined-at fields to agree");
6075 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6079 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6080 unsigned FI, uint64_t Off,
6081 DebugLoc DL, unsigned O) {
6082 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6083 "Expected inlined-at fields to agree");
6084 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6089 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6090 /// pointed to by a use iterator is deleted, increment the use iterator
6091 /// so that it doesn't dangle.
6093 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6094 SDNode::use_iterator &UI;
6095 SDNode::use_iterator &UE;
6097 void NodeDeleted(SDNode *N, SDNode *E) override {
6098 // Increment the iterator as needed.
6099 while (UI != UE && N == *UI)
6104 RAUWUpdateListener(SelectionDAG &d,
6105 SDNode::use_iterator &ui,
6106 SDNode::use_iterator &ue)
6107 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6112 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6113 /// This can cause recursive merging of nodes in the DAG.
6115 /// This version assumes From has a single result value.
6117 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6118 SDNode *From = FromN.getNode();
6119 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6120 "Cannot replace with this method!");
6121 assert(From != To.getNode() && "Cannot replace uses of with self");
6123 // Iterate over all the existing uses of From. New uses will be added
6124 // to the beginning of the use list, which we avoid visiting.
6125 // This specifically avoids visiting uses of From that arise while the
6126 // replacement is happening, because any such uses would be the result
6127 // of CSE: If an existing node looks like From after one of its operands
6128 // is replaced by To, we don't want to replace of all its users with To
6129 // too. See PR3018 for more info.
6130 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6131 RAUWUpdateListener Listener(*this, UI, UE);
6135 // This node is about to morph, remove its old self from the CSE maps.
6136 RemoveNodeFromCSEMaps(User);
6138 // A user can appear in a use list multiple times, and when this
6139 // happens the uses are usually next to each other in the list.
6140 // To help reduce the number of CSE recomputations, process all
6141 // the uses of this user that we can find this way.
6143 SDUse &Use = UI.getUse();
6146 } while (UI != UE && *UI == User);
6148 // Now that we have modified User, add it back to the CSE maps. If it
6149 // already exists there, recursively merge the results together.
6150 AddModifiedNodeToCSEMaps(User);
6153 // If we just RAUW'd the root, take note.
6154 if (FromN == getRoot())
6158 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6159 /// This can cause recursive merging of nodes in the DAG.
6161 /// This version assumes that for each value of From, there is a
6162 /// corresponding value in To in the same position with the same type.
6164 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6166 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6167 assert((!From->hasAnyUseOfValue(i) ||
6168 From->getValueType(i) == To->getValueType(i)) &&
6169 "Cannot use this version of ReplaceAllUsesWith!");
6172 // Handle the trivial case.
6176 // Iterate over just the existing users of From. See the comments in
6177 // the ReplaceAllUsesWith above.
6178 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6179 RAUWUpdateListener Listener(*this, UI, UE);
6183 // This node is about to morph, remove its old self from the CSE maps.
6184 RemoveNodeFromCSEMaps(User);
6186 // A user can appear in a use list multiple times, and when this
6187 // happens the uses are usually next to each other in the list.
6188 // To help reduce the number of CSE recomputations, process all
6189 // the uses of this user that we can find this way.
6191 SDUse &Use = UI.getUse();
6194 } while (UI != UE && *UI == User);
6196 // Now that we have modified User, add it back to the CSE maps. If it
6197 // already exists there, recursively merge the results together.
6198 AddModifiedNodeToCSEMaps(User);
6201 // If we just RAUW'd the root, take note.
6202 if (From == getRoot().getNode())
6203 setRoot(SDValue(To, getRoot().getResNo()));
6206 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6207 /// This can cause recursive merging of nodes in the DAG.
6209 /// This version can replace From with any result values. To must match the
6210 /// number and types of values returned by From.
6211 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6212 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6213 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6215 // Iterate over just the existing users of From. See the comments in
6216 // the ReplaceAllUsesWith above.
6217 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6218 RAUWUpdateListener Listener(*this, UI, UE);
6222 // This node is about to morph, remove its old self from the CSE maps.
6223 RemoveNodeFromCSEMaps(User);
6225 // A user can appear in a use list multiple times, and when this
6226 // happens the uses are usually next to each other in the list.
6227 // To help reduce the number of CSE recomputations, process all
6228 // the uses of this user that we can find this way.
6230 SDUse &Use = UI.getUse();
6231 const SDValue &ToOp = To[Use.getResNo()];
6234 } while (UI != UE && *UI == User);
6236 // Now that we have modified User, add it back to the CSE maps. If it
6237 // already exists there, recursively merge the results together.
6238 AddModifiedNodeToCSEMaps(User);
6241 // If we just RAUW'd the root, take note.
6242 if (From == getRoot().getNode())
6243 setRoot(SDValue(To[getRoot().getResNo()]));
6246 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6247 /// uses of other values produced by From.getNode() alone. The Deleted
6248 /// vector is handled the same way as for ReplaceAllUsesWith.
6249 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6250 // Handle the really simple, really trivial case efficiently.
6251 if (From == To) return;
6253 // Handle the simple, trivial, case efficiently.
6254 if (From.getNode()->getNumValues() == 1) {
6255 ReplaceAllUsesWith(From, To);
6259 // Iterate over just the existing users of From. See the comments in
6260 // the ReplaceAllUsesWith above.
6261 SDNode::use_iterator UI = From.getNode()->use_begin(),
6262 UE = From.getNode()->use_end();
6263 RAUWUpdateListener Listener(*this, UI, UE);
6266 bool UserRemovedFromCSEMaps = false;
6268 // A user can appear in a use list multiple times, and when this
6269 // happens the uses are usually next to each other in the list.
6270 // To help reduce the number of CSE recomputations, process all
6271 // the uses of this user that we can find this way.
6273 SDUse &Use = UI.getUse();
6275 // Skip uses of different values from the same node.
6276 if (Use.getResNo() != From.getResNo()) {
6281 // If this node hasn't been modified yet, it's still in the CSE maps,
6282 // so remove its old self from the CSE maps.
6283 if (!UserRemovedFromCSEMaps) {
6284 RemoveNodeFromCSEMaps(User);
6285 UserRemovedFromCSEMaps = true;
6290 } while (UI != UE && *UI == User);
6292 // We are iterating over all uses of the From node, so if a use
6293 // doesn't use the specific value, no changes are made.
6294 if (!UserRemovedFromCSEMaps)
6297 // Now that we have modified User, add it back to the CSE maps. If it
6298 // already exists there, recursively merge the results together.
6299 AddModifiedNodeToCSEMaps(User);
6302 // If we just RAUW'd the root, take note.
6303 if (From == getRoot())
6308 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6309 /// to record information about a use.
6316 /// operator< - Sort Memos by User.
6317 bool operator<(const UseMemo &L, const UseMemo &R) {
6318 return (intptr_t)L.User < (intptr_t)R.User;
6322 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6323 /// uses of other values produced by From.getNode() alone. The same value
6324 /// may appear in both the From and To list. The Deleted vector is
6325 /// handled the same way as for ReplaceAllUsesWith.
6326 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6329 // Handle the simple, trivial case efficiently.
6331 return ReplaceAllUsesOfValueWith(*From, *To);
6333 // Read up all the uses and make records of them. This helps
6334 // processing new uses that are introduced during the
6335 // replacement process.
6336 SmallVector<UseMemo, 4> Uses;
6337 for (unsigned i = 0; i != Num; ++i) {
6338 unsigned FromResNo = From[i].getResNo();
6339 SDNode *FromNode = From[i].getNode();
6340 for (SDNode::use_iterator UI = FromNode->use_begin(),
6341 E = FromNode->use_end(); UI != E; ++UI) {
6342 SDUse &Use = UI.getUse();
6343 if (Use.getResNo() == FromResNo) {
6344 UseMemo Memo = { *UI, i, &Use };
6345 Uses.push_back(Memo);
6350 // Sort the uses, so that all the uses from a given User are together.
6351 std::sort(Uses.begin(), Uses.end());
6353 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6354 UseIndex != UseIndexEnd; ) {
6355 // We know that this user uses some value of From. If it is the right
6356 // value, update it.
6357 SDNode *User = Uses[UseIndex].User;
6359 // This node is about to morph, remove its old self from the CSE maps.
6360 RemoveNodeFromCSEMaps(User);
6362 // The Uses array is sorted, so all the uses for a given User
6363 // are next to each other in the list.
6364 // To help reduce the number of CSE recomputations, process all
6365 // the uses of this user that we can find this way.
6367 unsigned i = Uses[UseIndex].Index;
6368 SDUse &Use = *Uses[UseIndex].Use;
6372 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6374 // Now that we have modified User, add it back to the CSE maps. If it
6375 // already exists there, recursively merge the results together.
6376 AddModifiedNodeToCSEMaps(User);
6380 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6381 /// based on their topological order. It returns the maximum id and a vector
6382 /// of the SDNodes* in assigned order by reference.
6383 unsigned SelectionDAG::AssignTopologicalOrder() {
6385 unsigned DAGSize = 0;
6387 // SortedPos tracks the progress of the algorithm. Nodes before it are
6388 // sorted, nodes after it are unsorted. When the algorithm completes
6389 // it is at the end of the list.
6390 allnodes_iterator SortedPos = allnodes_begin();
6392 // Visit all the nodes. Move nodes with no operands to the front of
6393 // the list immediately. Annotate nodes that do have operands with their
6394 // operand count. Before we do this, the Node Id fields of the nodes
6395 // may contain arbitrary values. After, the Node Id fields for nodes
6396 // before SortedPos will contain the topological sort index, and the
6397 // Node Id fields for nodes At SortedPos and after will contain the
6398 // count of outstanding operands.
6399 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6401 checkForCycles(N, this);
6402 unsigned Degree = N->getNumOperands();
6404 // A node with no uses, add it to the result array immediately.
6405 N->setNodeId(DAGSize++);
6406 allnodes_iterator Q = N;
6408 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6409 assert(SortedPos != AllNodes.end() && "Overran node list");
6412 // Temporarily use the Node Id as scratch space for the degree count.
6413 N->setNodeId(Degree);
6417 // Visit all the nodes. As we iterate, move nodes into sorted order,
6418 // such that by the time the end is reached all nodes will be sorted.
6419 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6421 checkForCycles(N, this);
6422 // N is in sorted position, so all its uses have one less operand
6423 // that needs to be sorted.
6424 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6427 unsigned Degree = P->getNodeId();
6428 assert(Degree != 0 && "Invalid node degree");
6431 // All of P's operands are sorted, so P may sorted now.
6432 P->setNodeId(DAGSize++);
6434 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6435 assert(SortedPos != AllNodes.end() && "Overran node list");
6438 // Update P's outstanding operand count.
6439 P->setNodeId(Degree);
6442 if (I == SortedPos) {
6445 dbgs() << "Overran sorted position:\n";
6446 S->dumprFull(this); dbgs() << "\n";
6447 dbgs() << "Checking if this is due to cycles\n";
6448 checkForCycles(this, true);
6450 llvm_unreachable(nullptr);
6454 assert(SortedPos == AllNodes.end() &&
6455 "Topological sort incomplete!");
6456 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6457 "First node in topological sort is not the entry token!");
6458 assert(AllNodes.front().getNodeId() == 0 &&
6459 "First node in topological sort has non-zero id!");
6460 assert(AllNodes.front().getNumOperands() == 0 &&
6461 "First node in topological sort has operands!");
6462 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6463 "Last node in topologic sort has unexpected id!");
6464 assert(AllNodes.back().use_empty() &&
6465 "Last node in topologic sort has users!");
6466 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6470 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6471 /// value is produced by SD.
6472 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6474 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6475 SD->setHasDebugValue(true);
6477 DbgInfo->add(DB, SD, isParameter);
6480 /// TransferDbgValues - Transfer SDDbgValues.
6481 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6482 if (From == To || !From.getNode()->getHasDebugValue())
6484 SDNode *FromNode = From.getNode();
6485 SDNode *ToNode = To.getNode();
6486 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6487 SmallVector<SDDbgValue *, 2> ClonedDVs;
6488 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6490 SDDbgValue *Dbg = *I;
6491 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6493 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6494 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6495 Dbg->getDebugLoc(), Dbg->getOrder());
6496 ClonedDVs.push_back(Clone);
6499 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6500 E = ClonedDVs.end(); I != E; ++I)
6501 AddDbgValue(*I, ToNode, false);
6504 //===----------------------------------------------------------------------===//
6506 //===----------------------------------------------------------------------===//
6508 HandleSDNode::~HandleSDNode() {
6512 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6513 DebugLoc DL, const GlobalValue *GA,
6514 EVT VT, int64_t o, unsigned char TF)
6515 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6519 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6520 SDValue X, unsigned SrcAS,
6522 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6523 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6525 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6526 EVT memvt, MachineMemOperand *mmo)
6527 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6528 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6529 MMO->isNonTemporal(), MMO->isInvariant());
6530 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6531 assert(isNonTemporal() == MMO->isNonTemporal() &&
6532 "Non-temporal encoding error!");
6533 // We check here that the size of the memory operand fits within the size of
6534 // the MMO. This is because the MMO might indicate only a possible address
6535 // range instead of specifying the affected memory addresses precisely.
6536 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6539 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6540 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6541 : SDNode(Opc, Order, dl, VTs, Ops),
6542 MemoryVT(memvt), MMO(mmo) {
6543 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6544 MMO->isNonTemporal(), MMO->isInvariant());
6545 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6546 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6549 /// Profile - Gather unique data for the node.
6551 void SDNode::Profile(FoldingSetNodeID &ID) const {
6552 AddNodeIDNode(ID, this);
6557 std::vector<EVT> VTs;
6560 VTs.reserve(MVT::LAST_VALUETYPE);
6561 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6562 VTs.push_back(MVT((MVT::SimpleValueType)i));
6567 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6568 static ManagedStatic<EVTArray> SimpleVTArray;
6569 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6571 /// getValueTypeList - Return a pointer to the specified value type.
6573 const EVT *SDNode::getValueTypeList(EVT VT) {
6574 if (VT.isExtended()) {
6575 sys::SmartScopedLock<true> Lock(*VTMutex);
6576 return &(*EVTs->insert(VT).first);
6578 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6579 "Value type out of range!");
6580 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6584 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6585 /// indicated value. This method ignores uses of other values defined by this
6587 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6588 assert(Value < getNumValues() && "Bad value!");
6590 // TODO: Only iterate over uses of a given value of the node
6591 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6592 if (UI.getUse().getResNo() == Value) {
6599 // Found exactly the right number of uses?
6604 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6605 /// value. This method ignores uses of other values defined by this operation.
6606 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6607 assert(Value < getNumValues() && "Bad value!");
6609 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6610 if (UI.getUse().getResNo() == Value)
6617 /// isOnlyUserOf - Return true if this node is the only use of N.
6619 bool SDNode::isOnlyUserOf(SDNode *N) const {
6621 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6632 /// isOperand - Return true if this node is an operand of N.
6634 bool SDValue::isOperandOf(SDNode *N) const {
6635 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6636 if (*this == N->getOperand(i))
6641 bool SDNode::isOperandOf(SDNode *N) const {
6642 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6643 if (this == N->OperandList[i].getNode())
6648 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6649 /// be a chain) reaches the specified operand without crossing any
6650 /// side-effecting instructions on any chain path. In practice, this looks
6651 /// through token factors and non-volatile loads. In order to remain efficient,
6652 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6653 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6654 unsigned Depth) const {
6655 if (*this == Dest) return true;
6657 // Don't search too deeply, we just want to be able to see through
6658 // TokenFactor's etc.
6659 if (Depth == 0) return false;
6661 // If this is a token factor, all inputs to the TF happen in parallel. If any
6662 // of the operands of the TF does not reach dest, then we cannot do the xform.
6663 if (getOpcode() == ISD::TokenFactor) {
6664 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6665 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6670 // Loads don't have side effects, look through them.
6671 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6672 if (!Ld->isVolatile())
6673 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6678 /// hasPredecessor - Return true if N is a predecessor of this node.
6679 /// N is either an operand of this node, or can be reached by recursively
6680 /// traversing up the operands.
6681 /// NOTE: This is an expensive method. Use it carefully.
6682 bool SDNode::hasPredecessor(const SDNode *N) const {
6683 SmallPtrSet<const SDNode *, 32> Visited;
6684 SmallVector<const SDNode *, 16> Worklist;
6685 return hasPredecessorHelper(N, Visited, Worklist);
6689 SDNode::hasPredecessorHelper(const SDNode *N,
6690 SmallPtrSetImpl<const SDNode *> &Visited,
6691 SmallVectorImpl<const SDNode *> &Worklist) const {
6692 if (Visited.empty()) {
6693 Worklist.push_back(this);
6695 // Take a look in the visited set. If we've already encountered this node
6696 // we needn't search further.
6697 if (Visited.count(N))
6701 // Haven't visited N yet. Continue the search.
6702 while (!Worklist.empty()) {
6703 const SDNode *M = Worklist.pop_back_val();
6704 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6705 SDNode *Op = M->getOperand(i).getNode();
6706 if (Visited.insert(Op).second)
6707 Worklist.push_back(Op);
6716 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6717 assert(Num < NumOperands && "Invalid child # of SDNode!");
6718 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6721 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6722 assert(N->getNumValues() == 1 &&
6723 "Can't unroll a vector with multiple results!");
6725 EVT VT = N->getValueType(0);
6726 unsigned NE = VT.getVectorNumElements();
6727 EVT EltVT = VT.getVectorElementType();
6730 SmallVector<SDValue, 8> Scalars;
6731 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6733 // If ResNE is 0, fully unroll the vector op.
6736 else if (NE > ResNE)
6740 for (i= 0; i != NE; ++i) {
6741 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6742 SDValue Operand = N->getOperand(j);
6743 EVT OperandVT = Operand.getValueType();
6744 if (OperandVT.isVector()) {
6745 // A vector operand; extract a single element.
6746 EVT OperandEltVT = OperandVT.getVectorElementType();
6747 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6750 getConstant(i, dl, TLI->getVectorIdxTy()));
6752 // A scalar operand; just use it as is.
6753 Operands[j] = Operand;
6757 switch (N->getOpcode()) {
6759 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6762 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6769 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6770 getShiftAmountOperand(Operands[0].getValueType(),
6773 case ISD::SIGN_EXTEND_INREG:
6774 case ISD::FP_ROUND_INREG: {
6775 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6776 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6778 getValueType(ExtVT)));
6783 for (; i < ResNE; ++i)
6784 Scalars.push_back(getUNDEF(EltVT));
6786 return getNode(ISD::BUILD_VECTOR, dl,
6787 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6791 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6792 /// location that is 'Dist' units away from the location that the 'Base' load
6793 /// is loading from.
6794 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6795 unsigned Bytes, int Dist) const {
6796 if (LD->getChain() != Base->getChain())
6798 EVT VT = LD->getValueType(0);
6799 if (VT.getSizeInBits() / 8 != Bytes)
6802 SDValue Loc = LD->getOperand(1);
6803 SDValue BaseLoc = Base->getOperand(1);
6804 if (Loc.getOpcode() == ISD::FrameIndex) {
6805 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6807 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6808 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6809 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6810 int FS = MFI->getObjectSize(FI);
6811 int BFS = MFI->getObjectSize(BFI);
6812 if (FS != BFS || FS != (int)Bytes) return false;
6813 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6817 if (isBaseWithConstantOffset(Loc)) {
6818 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6819 if (Loc.getOperand(0) == BaseLoc) {
6820 // If the base location is a simple address with no offset itself, then
6821 // the second load's first add operand should be the base address.
6822 if (LocOffset == Dist * (int)Bytes)
6824 } else if (isBaseWithConstantOffset(BaseLoc)) {
6825 // The base location itself has an offset, so subtract that value from the
6826 // second load's offset before comparing to distance * size.
6828 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6829 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6830 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6835 const GlobalValue *GV1 = nullptr;
6836 const GlobalValue *GV2 = nullptr;
6837 int64_t Offset1 = 0;
6838 int64_t Offset2 = 0;
6839 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6840 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6841 if (isGA1 && isGA2 && GV1 == GV2)
6842 return Offset1 == (Offset2 + Dist*Bytes);
6847 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6848 /// it cannot be inferred.
6849 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6850 // If this is a GlobalAddress + cst, return the alignment.
6851 const GlobalValue *GV;
6852 int64_t GVOffset = 0;
6853 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6854 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6855 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6856 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6857 *TLI->getDataLayout());
6858 unsigned AlignBits = KnownZero.countTrailingOnes();
6859 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6861 return MinAlign(Align, GVOffset);
6864 // If this is a direct reference to a stack slot, use information about the
6865 // stack slot's alignment.
6866 int FrameIdx = 1 << 31;
6867 int64_t FrameOffset = 0;
6868 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6869 FrameIdx = FI->getIndex();
6870 } else if (isBaseWithConstantOffset(Ptr) &&
6871 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6873 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6874 FrameOffset = Ptr.getConstantOperandVal(1);
6877 if (FrameIdx != (1 << 31)) {
6878 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6879 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6887 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6888 /// which is split (or expanded) into two not necessarily identical pieces.
6889 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6890 // Currently all types are split in half.
6892 if (!VT.isVector()) {
6893 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6895 unsigned NumElements = VT.getVectorNumElements();
6896 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6897 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6900 return std::make_pair(LoVT, HiVT);
6903 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6905 std::pair<SDValue, SDValue>
6906 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6908 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6909 N.getValueType().getVectorNumElements() &&
6910 "More vector elements requested than available!");
6912 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6913 getConstant(0, DL, TLI->getVectorIdxTy()));
6914 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6915 getConstant(LoVT.getVectorNumElements(), DL,
6916 TLI->getVectorIdxTy()));
6917 return std::make_pair(Lo, Hi);
6920 void SelectionDAG::ExtractVectorElements(SDValue Op,
6921 SmallVectorImpl<SDValue> &Args,
6922 unsigned Start, unsigned Count) {
6923 EVT VT = Op.getValueType();
6925 Count = VT.getVectorNumElements();
6927 EVT EltVT = VT.getVectorElementType();
6928 EVT IdxTy = TLI->getVectorIdxTy();
6930 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6931 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6932 Op, getConstant(i, SL, IdxTy)));
6936 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6937 unsigned GlobalAddressSDNode::getAddressSpace() const {
6938 return getGlobal()->getType()->getAddressSpace();
6942 Type *ConstantPoolSDNode::getType() const {
6943 if (isMachineConstantPoolEntry())
6944 return Val.MachineCPVal->getType();
6945 return Val.ConstVal->getType();
6948 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6950 unsigned &SplatBitSize,
6952 unsigned MinSplatBits,
6953 bool isBigEndian) const {
6954 EVT VT = getValueType(0);
6955 assert(VT.isVector() && "Expected a vector type");
6956 unsigned sz = VT.getSizeInBits();
6957 if (MinSplatBits > sz)
6960 SplatValue = APInt(sz, 0);
6961 SplatUndef = APInt(sz, 0);
6963 // Get the bits. Bits with undefined values (when the corresponding element
6964 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6965 // in SplatValue. If any of the values are not constant, give up and return
6967 unsigned int nOps = getNumOperands();
6968 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6969 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6971 for (unsigned j = 0; j < nOps; ++j) {
6972 unsigned i = isBigEndian ? nOps-1-j : j;
6973 SDValue OpVal = getOperand(i);
6974 unsigned BitPos = j * EltBitSize;
6976 if (OpVal.getOpcode() == ISD::UNDEF)
6977 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6978 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6979 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6980 zextOrTrunc(sz) << BitPos;
6981 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6982 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6987 // The build_vector is all constants or undefs. Find the smallest element
6988 // size that splats the vector.
6990 HasAnyUndefs = (SplatUndef != 0);
6993 unsigned HalfSize = sz / 2;
6994 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6995 APInt LowValue = SplatValue.trunc(HalfSize);
6996 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6997 APInt LowUndef = SplatUndef.trunc(HalfSize);
6999 // If the two halves do not match (ignoring undef bits), stop here.
7000 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7001 MinSplatBits > HalfSize)
7004 SplatValue = HighValue | LowValue;
7005 SplatUndef = HighUndef & LowUndef;
7014 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7015 if (UndefElements) {
7016 UndefElements->clear();
7017 UndefElements->resize(getNumOperands());
7020 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7021 SDValue Op = getOperand(i);
7022 if (Op.getOpcode() == ISD::UNDEF) {
7024 (*UndefElements)[i] = true;
7025 } else if (!Splatted) {
7027 } else if (Splatted != Op) {
7033 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7034 "Can only have a splat without a constant for all undefs.");
7035 return getOperand(0);
7042 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7043 return dyn_cast_or_null<ConstantSDNode>(
7044 getSplatValue(UndefElements).getNode());
7048 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7049 return dyn_cast_or_null<ConstantFPSDNode>(
7050 getSplatValue(UndefElements).getNode());
7053 bool BuildVectorSDNode::isConstant() const {
7054 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7055 unsigned Opc = getOperand(i).getOpcode();
7056 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7062 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7063 // Find the first non-undef value in the shuffle mask.
7065 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7068 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7070 // Make sure all remaining elements are either undef or the same as the first
7072 for (int Idx = Mask[i]; i != e; ++i)
7073 if (Mask[i] >= 0 && Mask[i] != Idx)
7079 static void checkForCyclesHelper(const SDNode *N,
7080 SmallPtrSetImpl<const SDNode*> &Visited,
7081 SmallPtrSetImpl<const SDNode*> &Checked,
7082 const llvm::SelectionDAG *DAG) {
7083 // If this node has already been checked, don't check it again.
7084 if (Checked.count(N))
7087 // If a node has already been visited on this depth-first walk, reject it as
7089 if (!Visited.insert(N).second) {
7090 errs() << "Detected cycle in SelectionDAG\n";
7091 dbgs() << "Offending node:\n";
7092 N->dumprFull(DAG); dbgs() << "\n";
7096 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7097 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7104 void llvm::checkForCycles(const llvm::SDNode *N,
7105 const llvm::SelectionDAG *DAG,
7113 assert(N && "Checking nonexistent SDNode");
7114 SmallPtrSet<const SDNode*, 32> visited;
7115 SmallPtrSet<const SDNode*, 32> checked;
7116 checkForCyclesHelper(N, visited, checked, DAG);
7121 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7122 checkForCycles(DAG->getRoot().getNode(), DAG, force);