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:
2915 EVT SVT = VT.getScalarType();
2916 EVT InVT = BV->getValueType(0);
2917 EVT InSVT = InVT.getScalarType();
2919 // Find legal integer scalar type for constant promotion and
2920 // ensure that its scalar size is at least as large as source.
2922 if (SVT.isInteger()) {
2923 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2924 if (LegalSVT.bitsLT(SVT)) break;
2927 // Let the above scalar folding handle the folding of each element.
2928 SmallVector<SDValue, 8> Ops;
2929 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2930 SDValue OpN = BV->getOperand(i);
2931 EVT OpVT = OpN.getValueType();
2933 // Build vector (integer) scalar operands may need implicit
2934 // truncation - do this before constant folding.
2935 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2936 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2938 OpN = getNode(Opcode, DL, SVT, OpN);
2940 // Legalize the (integer) scalar constant if necessary.
2941 if (LegalSVT != SVT)
2942 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2944 if (OpN.getOpcode() != ISD::UNDEF &&
2945 OpN.getOpcode() != ISD::Constant &&
2946 OpN.getOpcode() != ISD::ConstantFP)
2950 if (Ops.size() == VT.getVectorNumElements())
2951 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2958 unsigned OpOpcode = Operand.getNode()->getOpcode();
2960 case ISD::TokenFactor:
2961 case ISD::MERGE_VALUES:
2962 case ISD::CONCAT_VECTORS:
2963 return Operand; // Factor, merge or concat of one node? No need.
2964 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2965 case ISD::FP_EXTEND:
2966 assert(VT.isFloatingPoint() &&
2967 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2968 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2969 assert((!VT.isVector() ||
2970 VT.getVectorNumElements() ==
2971 Operand.getValueType().getVectorNumElements()) &&
2972 "Vector element count mismatch!");
2973 if (Operand.getOpcode() == ISD::UNDEF)
2974 return getUNDEF(VT);
2976 case ISD::SIGN_EXTEND:
2977 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2978 "Invalid SIGN_EXTEND!");
2979 if (Operand.getValueType() == VT) return Operand; // noop extension
2980 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2981 "Invalid sext node, dst < src!");
2982 assert((!VT.isVector() ||
2983 VT.getVectorNumElements() ==
2984 Operand.getValueType().getVectorNumElements()) &&
2985 "Vector element count mismatch!");
2986 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2987 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2988 else if (OpOpcode == ISD::UNDEF)
2989 // sext(undef) = 0, because the top bits will all be the same.
2990 return getConstant(0, DL, VT);
2992 case ISD::ZERO_EXTEND:
2993 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2994 "Invalid ZERO_EXTEND!");
2995 if (Operand.getValueType() == VT) return Operand; // noop extension
2996 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2997 "Invalid zext node, dst < src!");
2998 assert((!VT.isVector() ||
2999 VT.getVectorNumElements() ==
3000 Operand.getValueType().getVectorNumElements()) &&
3001 "Vector element count mismatch!");
3002 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3003 return getNode(ISD::ZERO_EXTEND, DL, VT,
3004 Operand.getNode()->getOperand(0));
3005 else if (OpOpcode == ISD::UNDEF)
3006 // zext(undef) = 0, because the top bits will be zero.
3007 return getConstant(0, DL, VT);
3009 case ISD::ANY_EXTEND:
3010 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3011 "Invalid ANY_EXTEND!");
3012 if (Operand.getValueType() == VT) return Operand; // noop extension
3013 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3014 "Invalid anyext node, dst < src!");
3015 assert((!VT.isVector() ||
3016 VT.getVectorNumElements() ==
3017 Operand.getValueType().getVectorNumElements()) &&
3018 "Vector element count mismatch!");
3020 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3021 OpOpcode == ISD::ANY_EXTEND)
3022 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3023 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3024 else if (OpOpcode == ISD::UNDEF)
3025 return getUNDEF(VT);
3027 // (ext (trunx x)) -> x
3028 if (OpOpcode == ISD::TRUNCATE) {
3029 SDValue OpOp = Operand.getNode()->getOperand(0);
3030 if (OpOp.getValueType() == VT)
3035 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3036 "Invalid TRUNCATE!");
3037 if (Operand.getValueType() == VT) return Operand; // noop truncate
3038 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3039 "Invalid truncate node, src < dst!");
3040 assert((!VT.isVector() ||
3041 VT.getVectorNumElements() ==
3042 Operand.getValueType().getVectorNumElements()) &&
3043 "Vector element count mismatch!");
3044 if (OpOpcode == ISD::TRUNCATE)
3045 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3046 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3047 OpOpcode == ISD::ANY_EXTEND) {
3048 // If the source is smaller than the dest, we still need an extend.
3049 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3050 .bitsLT(VT.getScalarType()))
3051 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3052 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3053 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3054 return Operand.getNode()->getOperand(0);
3056 if (OpOpcode == ISD::UNDEF)
3057 return getUNDEF(VT);
3060 // Basic sanity checking.
3061 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3062 && "Cannot BITCAST between types of different sizes!");
3063 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3064 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3065 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3066 if (OpOpcode == ISD::UNDEF)
3067 return getUNDEF(VT);
3069 case ISD::SCALAR_TO_VECTOR:
3070 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3071 (VT.getVectorElementType() == Operand.getValueType() ||
3072 (VT.getVectorElementType().isInteger() &&
3073 Operand.getValueType().isInteger() &&
3074 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3075 "Illegal SCALAR_TO_VECTOR node!");
3076 if (OpOpcode == ISD::UNDEF)
3077 return getUNDEF(VT);
3078 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3079 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3080 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3081 Operand.getConstantOperandVal(1) == 0 &&
3082 Operand.getOperand(0).getValueType() == VT)
3083 return Operand.getOperand(0);
3086 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3087 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3088 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3089 Operand.getNode()->getOperand(0));
3090 if (OpOpcode == ISD::FNEG) // --X -> X
3091 return Operand.getNode()->getOperand(0);
3094 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3095 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3100 SDVTList VTs = getVTList(VT);
3101 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3102 FoldingSetNodeID ID;
3103 SDValue Ops[1] = { Operand };
3104 AddNodeIDNode(ID, Opcode, VTs, Ops);
3106 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3107 return SDValue(E, 0);
3109 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3110 DL.getDebugLoc(), VTs, Operand);
3111 CSEMap.InsertNode(N, IP);
3113 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3114 DL.getDebugLoc(), VTs, Operand);
3118 return SDValue(N, 0);
3121 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3124 case ISD::ADD: return std::make_pair(C1 + C2, true);
3125 case ISD::SUB: return std::make_pair(C1 - C2, true);
3126 case ISD::MUL: return std::make_pair(C1 * C2, true);
3127 case ISD::AND: return std::make_pair(C1 & C2, true);
3128 case ISD::OR: return std::make_pair(C1 | C2, true);
3129 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3130 case ISD::SHL: return std::make_pair(C1 << C2, true);
3131 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3132 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3133 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3134 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3136 if (!C2.getBoolValue())
3138 return std::make_pair(C1.udiv(C2), true);
3140 if (!C2.getBoolValue())
3142 return std::make_pair(C1.urem(C2), true);
3144 if (!C2.getBoolValue())
3146 return std::make_pair(C1.sdiv(C2), true);
3148 if (!C2.getBoolValue())
3150 return std::make_pair(C1.srem(C2), true);
3152 return std::make_pair(APInt(1, 0), false);
3155 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3156 const ConstantSDNode *Cst1,
3157 const ConstantSDNode *Cst2) {
3158 if (Cst1->isOpaque() || Cst2->isOpaque())
3161 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3162 Cst2->getAPIntValue());
3165 return getConstant(Folded.first, DL, VT);
3168 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3169 SDNode *Cst1, SDNode *Cst2) {
3170 // If the opcode is a target-specific ISD node, there's nothing we can
3171 // do here and the operand rules may not line up with the below, so
3173 if (Opcode >= ISD::BUILTIN_OP_END)
3176 // Handle the case of two scalars.
3177 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3178 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3179 if (SDValue Folded =
3180 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3183 SmallVector<SDValue, 4> Outputs;
3184 // We may have a vector type but a scalar result. Create a splat.
3185 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3186 // Build a big vector out of the scalar elements we generated.
3187 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3194 // For vectors extract each constant element into Inputs so we can constant
3195 // fold them individually.
3196 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3197 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3201 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3203 EVT SVT = VT.getScalarType();
3204 SmallVector<SDValue, 4> Outputs;
3205 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3206 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3207 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3208 if (!V1 || !V2) // Not a constant, bail.
3211 if (V1->isOpaque() || V2->isOpaque())
3214 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3215 // FIXME: This is valid and could be handled by truncating the APInts.
3216 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3219 // Fold one vector element.
3220 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3221 V2->getAPIntValue());
3224 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3227 assert(VT.getVectorNumElements() == Outputs.size() &&
3228 "Vector size mismatch!");
3230 // We may have a vector type but a scalar result. Create a splat.
3231 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3233 // Build a big vector out of the scalar elements we generated.
3234 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3237 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3238 SDValue N2, bool nuw, bool nsw, bool exact) {
3239 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3240 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3243 case ISD::TokenFactor:
3244 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3245 N2.getValueType() == MVT::Other && "Invalid token factor!");
3246 // Fold trivial token factors.
3247 if (N1.getOpcode() == ISD::EntryToken) return N2;
3248 if (N2.getOpcode() == ISD::EntryToken) return N1;
3249 if (N1 == N2) return N1;
3251 case ISD::CONCAT_VECTORS:
3252 // Concat of UNDEFs is UNDEF.
3253 if (N1.getOpcode() == ISD::UNDEF &&
3254 N2.getOpcode() == ISD::UNDEF)
3255 return getUNDEF(VT);
3257 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3258 // one big BUILD_VECTOR.
3259 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3260 N2.getOpcode() == ISD::BUILD_VECTOR) {
3261 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3262 N1.getNode()->op_end());
3263 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3265 // BUILD_VECTOR requires all inputs to be of the same type, find the
3266 // maximum type and extend them all.
3267 EVT SVT = VT.getScalarType();
3268 for (SDValue Op : Elts)
3269 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3270 if (SVT.bitsGT(VT.getScalarType()))
3271 for (SDValue &Op : Elts)
3272 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3273 ? getZExtOrTrunc(Op, DL, SVT)
3274 : getSExtOrTrunc(Op, DL, SVT);
3276 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3280 assert(VT.isInteger() && "This operator does not apply to FP types!");
3281 assert(N1.getValueType() == N2.getValueType() &&
3282 N1.getValueType() == VT && "Binary operator types must match!");
3283 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3284 // worth handling here.
3285 if (N2C && N2C->isNullValue())
3287 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3294 assert(VT.isInteger() && "This operator does not apply to FP types!");
3295 assert(N1.getValueType() == N2.getValueType() &&
3296 N1.getValueType() == VT && "Binary operator types must match!");
3297 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3298 // it's worth handling here.
3299 if (N2C && N2C->isNullValue())
3309 assert(VT.isInteger() && "This operator does not apply to FP types!");
3310 assert(N1.getValueType() == N2.getValueType() &&
3311 N1.getValueType() == VT && "Binary operator types must match!");
3318 if (getTarget().Options.UnsafeFPMath) {
3319 if (Opcode == ISD::FADD) {
3321 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3322 if (CFP->getValueAPF().isZero())
3325 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3326 if (CFP->getValueAPF().isZero())
3328 } else if (Opcode == ISD::FSUB) {
3330 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3331 if (CFP->getValueAPF().isZero())
3333 } else if (Opcode == ISD::FMUL) {
3334 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3337 // If the first operand isn't the constant, try the second
3339 CFP = dyn_cast<ConstantFPSDNode>(N2);
3346 return SDValue(CFP,0);
3348 if (CFP->isExactlyValue(1.0))
3353 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3354 assert(N1.getValueType() == N2.getValueType() &&
3355 N1.getValueType() == VT && "Binary operator types must match!");
3357 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3358 assert(N1.getValueType() == VT &&
3359 N1.getValueType().isFloatingPoint() &&
3360 N2.getValueType().isFloatingPoint() &&
3361 "Invalid FCOPYSIGN!");
3368 assert(VT == N1.getValueType() &&
3369 "Shift operators return type must be the same as their first arg");
3370 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3371 "Shifts only work on integers");
3372 assert((!VT.isVector() || VT == N2.getValueType()) &&
3373 "Vector shift amounts must be in the same as their first arg");
3374 // Verify that the shift amount VT is bit enough to hold valid shift
3375 // amounts. This catches things like trying to shift an i1024 value by an
3376 // i8, which is easy to fall into in generic code that uses
3377 // TLI.getShiftAmount().
3378 assert(N2.getValueType().getSizeInBits() >=
3379 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3380 "Invalid use of small shift amount with oversized value!");
3382 // Always fold shifts of i1 values so the code generator doesn't need to
3383 // handle them. Since we know the size of the shift has to be less than the
3384 // size of the value, the shift/rotate count is guaranteed to be zero.
3387 if (N2C && N2C->isNullValue())
3390 case ISD::FP_ROUND_INREG: {
3391 EVT EVT = cast<VTSDNode>(N2)->getVT();
3392 assert(VT == N1.getValueType() && "Not an inreg round!");
3393 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3394 "Cannot FP_ROUND_INREG integer types");
3395 assert(EVT.isVector() == VT.isVector() &&
3396 "FP_ROUND_INREG type should be vector iff the operand "
3398 assert((!EVT.isVector() ||
3399 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3400 "Vector element counts must match in FP_ROUND_INREG");
3401 assert(EVT.bitsLE(VT) && "Not rounding down!");
3403 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3407 assert(VT.isFloatingPoint() &&
3408 N1.getValueType().isFloatingPoint() &&
3409 VT.bitsLE(N1.getValueType()) &&
3410 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3411 if (N1.getValueType() == VT) return N1; // noop conversion.
3413 case ISD::AssertSext:
3414 case ISD::AssertZext: {
3415 EVT EVT = cast<VTSDNode>(N2)->getVT();
3416 assert(VT == N1.getValueType() && "Not an inreg extend!");
3417 assert(VT.isInteger() && EVT.isInteger() &&
3418 "Cannot *_EXTEND_INREG FP types");
3419 assert(!EVT.isVector() &&
3420 "AssertSExt/AssertZExt type should be the vector element type "
3421 "rather than the vector type!");
3422 assert(EVT.bitsLE(VT) && "Not extending!");
3423 if (VT == EVT) return N1; // noop assertion.
3426 case ISD::SIGN_EXTEND_INREG: {
3427 EVT EVT = cast<VTSDNode>(N2)->getVT();
3428 assert(VT == N1.getValueType() && "Not an inreg extend!");
3429 assert(VT.isInteger() && EVT.isInteger() &&
3430 "Cannot *_EXTEND_INREG FP types");
3431 assert(EVT.isVector() == VT.isVector() &&
3432 "SIGN_EXTEND_INREG type should be vector iff the operand "
3434 assert((!EVT.isVector() ||
3435 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3436 "Vector element counts must match in SIGN_EXTEND_INREG");
3437 assert(EVT.bitsLE(VT) && "Not extending!");
3438 if (EVT == VT) return N1; // Not actually extending
3440 auto SignExtendInReg = [&](APInt Val) {
3441 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3442 Val <<= Val.getBitWidth() - FromBits;
3443 Val = Val.ashr(Val.getBitWidth() - FromBits);
3444 return getConstant(Val, DL, VT.getScalarType());
3448 APInt Val = N1C->getAPIntValue();
3449 return SignExtendInReg(Val);
3451 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3452 SmallVector<SDValue, 8> Ops;
3453 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3454 SDValue Op = N1.getOperand(i);
3455 if (Op.getValueType() != VT.getScalarType()) break;
3456 if (Op.getOpcode() == ISD::UNDEF) {
3460 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3461 APInt Val = C->getAPIntValue();
3462 Ops.push_back(SignExtendInReg(Val));
3467 if (Ops.size() == VT.getVectorNumElements())
3468 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3472 case ISD::EXTRACT_VECTOR_ELT:
3473 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3474 if (N1.getOpcode() == ISD::UNDEF)
3475 return getUNDEF(VT);
3477 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3478 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3479 return getUNDEF(VT);
3481 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3482 // expanding copies of large vectors from registers.
3484 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3485 N1.getNumOperands() > 0) {
3487 N1.getOperand(0).getValueType().getVectorNumElements();
3488 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3489 N1.getOperand(N2C->getZExtValue() / Factor),
3490 getConstant(N2C->getZExtValue() % Factor, DL,
3491 N2.getValueType()));
3494 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3495 // expanding large vector constants.
3496 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3497 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3499 if (VT != Elt.getValueType())
3500 // If the vector element type is not legal, the BUILD_VECTOR operands
3501 // are promoted and implicitly truncated, and the result implicitly
3502 // extended. Make that explicit here.
3503 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3508 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3509 // operations are lowered to scalars.
3510 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3511 // If the indices are the same, return the inserted element else
3512 // if the indices are known different, extract the element from
3513 // the original vector.
3514 SDValue N1Op2 = N1.getOperand(2);
3515 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3517 if (N1Op2C && N2C) {
3518 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3519 if (VT == N1.getOperand(1).getValueType())
3520 return N1.getOperand(1);
3522 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3525 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3529 case ISD::EXTRACT_ELEMENT:
3530 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3531 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3532 (N1.getValueType().isInteger() == VT.isInteger()) &&
3533 N1.getValueType() != VT &&
3534 "Wrong types for EXTRACT_ELEMENT!");
3536 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3537 // 64-bit integers into 32-bit parts. Instead of building the extract of
3538 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3539 if (N1.getOpcode() == ISD::BUILD_PAIR)
3540 return N1.getOperand(N2C->getZExtValue());
3542 // EXTRACT_ELEMENT of a constant int is also very common.
3543 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3544 unsigned ElementSize = VT.getSizeInBits();
3545 unsigned Shift = ElementSize * N2C->getZExtValue();
3546 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3547 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3550 case ISD::EXTRACT_SUBVECTOR: {
3552 if (VT.isSimple() && N1.getValueType().isSimple()) {
3553 assert(VT.isVector() && N1.getValueType().isVector() &&
3554 "Extract subvector VTs must be a vectors!");
3555 assert(VT.getVectorElementType() ==
3556 N1.getValueType().getVectorElementType() &&
3557 "Extract subvector VTs must have the same element type!");
3558 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3559 "Extract subvector must be from larger vector to smaller vector!");
3561 if (isa<ConstantSDNode>(Index.getNode())) {
3562 assert((VT.getVectorNumElements() +
3563 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3564 <= N1.getValueType().getVectorNumElements())
3565 && "Extract subvector overflow!");
3568 // Trivial extraction.
3569 if (VT.getSimpleVT() == N1.getSimpleValueType())
3576 // Perform trivial constant folding.
3578 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3581 // Canonicalize constant to RHS if commutative.
3582 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3583 std::swap(N1C, N2C);
3587 // Constant fold FP operations.
3588 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3589 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3590 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3592 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3593 // Canonicalize constant to RHS if commutative.
3594 std::swap(N1CFP, N2CFP);
3597 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3598 APFloat::opStatus s;
3601 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3602 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3603 return getConstantFP(V1, DL, VT);
3606 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3607 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3608 return getConstantFP(V1, DL, VT);
3611 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3612 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3613 return getConstantFP(V1, DL, VT);
3616 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3617 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3618 s!=APFloat::opDivByZero)) {
3619 return getConstantFP(V1, DL, VT);
3623 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3624 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3625 s!=APFloat::opDivByZero)) {
3626 return getConstantFP(V1, DL, VT);
3629 case ISD::FCOPYSIGN:
3631 return getConstantFP(V1, DL, VT);
3636 if (Opcode == ISD::FP_ROUND) {
3637 APFloat V = N1CFP->getValueAPF(); // make copy
3639 // This can return overflow, underflow, or inexact; we don't care.
3640 // FIXME need to be more flexible about rounding mode.
3641 (void)V.convert(EVTToAPFloatSemantics(VT),
3642 APFloat::rmNearestTiesToEven, &ignored);
3643 return getConstantFP(V, DL, VT);
3647 // Canonicalize an UNDEF to the RHS, even over a constant.
3648 if (N1.getOpcode() == ISD::UNDEF) {
3649 if (isCommutativeBinOp(Opcode)) {
3653 case ISD::FP_ROUND_INREG:
3654 case ISD::SIGN_EXTEND_INREG:
3660 return N1; // fold op(undef, arg2) -> undef
3668 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3669 // For vectors, we can't easily build an all zero vector, just return
3676 // Fold a bunch of operators when the RHS is undef.
3677 if (N2.getOpcode() == ISD::UNDEF) {
3680 if (N1.getOpcode() == ISD::UNDEF)
3681 // Handle undef ^ undef -> 0 special case. This is a common
3683 return getConstant(0, DL, VT);
3693 return N2; // fold op(arg1, undef) -> undef
3699 if (getTarget().Options.UnsafeFPMath)
3707 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3708 // For vectors, we can't easily build an all zero vector, just return
3713 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3714 // For vectors, we can't easily build an all one vector, just return
3722 // Memoize this node if possible.
3724 SDVTList VTs = getVTList(VT);
3725 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3726 if (VT != MVT::Glue) {
3727 SDValue Ops[] = {N1, N2};
3728 FoldingSetNodeID ID;
3729 AddNodeIDNode(ID, Opcode, VTs, Ops);
3731 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3733 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3734 return SDValue(E, 0);
3736 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3738 CSEMap.InsertNode(N, IP);
3740 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3744 return SDValue(N, 0);
3747 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3748 SDValue N1, SDValue N2, SDValue N3) {
3749 // Perform various simplifications.
3750 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3753 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3754 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3755 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3756 if (N1CFP && N2CFP && N3CFP) {
3757 APFloat V1 = N1CFP->getValueAPF();
3758 const APFloat &V2 = N2CFP->getValueAPF();
3759 const APFloat &V3 = N3CFP->getValueAPF();
3760 APFloat::opStatus s =
3761 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3762 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3763 return getConstantFP(V1, DL, VT);
3767 case ISD::CONCAT_VECTORS:
3768 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3769 // one big BUILD_VECTOR.
3770 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3771 N2.getOpcode() == ISD::BUILD_VECTOR &&
3772 N3.getOpcode() == ISD::BUILD_VECTOR) {
3773 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3774 N1.getNode()->op_end());
3775 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3776 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3777 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3781 // Use FoldSetCC to simplify SETCC's.
3782 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3783 if (Simp.getNode()) return Simp;
3788 if (N1C->getZExtValue())
3789 return N2; // select true, X, Y -> X
3790 return N3; // select false, X, Y -> Y
3793 if (N2 == N3) return N2; // select C, X, X -> X
3795 case ISD::VECTOR_SHUFFLE:
3796 llvm_unreachable("should use getVectorShuffle constructor!");
3797 case ISD::INSERT_SUBVECTOR: {
3799 if (VT.isSimple() && N1.getValueType().isSimple()
3800 && N2.getValueType().isSimple()) {
3801 assert(VT.isVector() && N1.getValueType().isVector() &&
3802 N2.getValueType().isVector() &&
3803 "Insert subvector VTs must be a vectors");
3804 assert(VT == N1.getValueType() &&
3805 "Dest and insert subvector source types must match!");
3806 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3807 "Insert subvector must be from smaller vector to larger vector!");
3808 if (isa<ConstantSDNode>(Index.getNode())) {
3809 assert((N2.getValueType().getVectorNumElements() +
3810 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3811 <= VT.getVectorNumElements())
3812 && "Insert subvector overflow!");
3815 // Trivial insertion.
3816 if (VT.getSimpleVT() == N2.getSimpleValueType())
3822 // Fold bit_convert nodes from a type to themselves.
3823 if (N1.getValueType() == VT)
3828 // Memoize node if it doesn't produce a flag.
3830 SDVTList VTs = getVTList(VT);
3831 if (VT != MVT::Glue) {
3832 SDValue Ops[] = { N1, N2, N3 };
3833 FoldingSetNodeID ID;
3834 AddNodeIDNode(ID, Opcode, VTs, Ops);
3836 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3837 return SDValue(E, 0);
3839 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3840 DL.getDebugLoc(), VTs, N1, N2, N3);
3841 CSEMap.InsertNode(N, IP);
3843 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3844 DL.getDebugLoc(), VTs, N1, N2, N3);
3848 return SDValue(N, 0);
3851 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3852 SDValue N1, SDValue N2, SDValue N3,
3854 SDValue Ops[] = { N1, N2, N3, N4 };
3855 return getNode(Opcode, DL, VT, Ops);
3858 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3859 SDValue N1, SDValue N2, SDValue N3,
3860 SDValue N4, SDValue N5) {
3861 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3862 return getNode(Opcode, DL, VT, Ops);
3865 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3866 /// the incoming stack arguments to be loaded from the stack.
3867 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3868 SmallVector<SDValue, 8> ArgChains;
3870 // Include the original chain at the beginning of the list. When this is
3871 // used by target LowerCall hooks, this helps legalize find the
3872 // CALLSEQ_BEGIN node.
3873 ArgChains.push_back(Chain);
3875 // Add a chain value for each stack argument.
3876 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3877 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3878 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3879 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3880 if (FI->getIndex() < 0)
3881 ArgChains.push_back(SDValue(L, 1));
3883 // Build a tokenfactor for all the chains.
3884 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3887 /// getMemsetValue - Vectorized representation of the memset value
3889 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3891 assert(Value.getOpcode() != ISD::UNDEF);
3893 unsigned NumBits = VT.getScalarType().getSizeInBits();
3894 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3895 assert(C->getAPIntValue().getBitWidth() == 8);
3896 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3898 return DAG.getConstant(Val, dl, VT);
3899 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3903 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3904 EVT IntVT = VT.getScalarType();
3905 if (!IntVT.isInteger())
3906 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3908 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3910 // Use a multiplication with 0x010101... to extend the input to the
3912 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3913 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3914 DAG.getConstant(Magic, dl, IntVT));
3917 if (VT != Value.getValueType() && !VT.isInteger())
3918 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3919 if (VT != Value.getValueType()) {
3920 assert(VT.getVectorElementType() == Value.getValueType() &&
3921 "value type should be one vector element here");
3922 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3923 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3929 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3930 /// used when a memcpy is turned into a memset when the source is a constant
3932 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3933 const TargetLowering &TLI, StringRef Str) {
3934 // Handle vector with all elements zero.
3937 return DAG.getConstant(0, dl, VT);
3938 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3939 return DAG.getConstantFP(0.0, dl, VT);
3940 else if (VT.isVector()) {
3941 unsigned NumElts = VT.getVectorNumElements();
3942 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3943 return DAG.getNode(ISD::BITCAST, dl, VT,
3944 DAG.getConstant(0, dl,
3945 EVT::getVectorVT(*DAG.getContext(),
3948 llvm_unreachable("Expected type!");
3951 assert(!VT.isVector() && "Can't handle vector type here!");
3952 unsigned NumVTBits = VT.getSizeInBits();
3953 unsigned NumVTBytes = NumVTBits / 8;
3954 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3956 APInt Val(NumVTBits, 0);
3957 if (TLI.isLittleEndian()) {
3958 for (unsigned i = 0; i != NumBytes; ++i)
3959 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3961 for (unsigned i = 0; i != NumBytes; ++i)
3962 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3965 // If the "cost" of materializing the integer immediate is less than the cost
3966 // of a load, then it is cost effective to turn the load into the immediate.
3967 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3968 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3969 return DAG.getConstant(Val, dl, VT);
3970 return SDValue(nullptr, 0);
3973 /// getMemBasePlusOffset - Returns base and offset node for the
3975 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3976 SelectionDAG &DAG) {
3977 EVT VT = Base.getValueType();
3978 return DAG.getNode(ISD::ADD, dl,
3979 VT, Base, DAG.getConstant(Offset, dl, VT));
3982 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3984 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3985 unsigned SrcDelta = 0;
3986 GlobalAddressSDNode *G = nullptr;
3987 if (Src.getOpcode() == ISD::GlobalAddress)
3988 G = cast<GlobalAddressSDNode>(Src);
3989 else if (Src.getOpcode() == ISD::ADD &&
3990 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3991 Src.getOperand(1).getOpcode() == ISD::Constant) {
3992 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3993 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3998 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4001 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
4002 /// to replace the memset / memcpy. Return true if the number of memory ops
4003 /// is below the threshold. It returns the types of the sequence of
4004 /// memory ops to perform memset / memcpy by reference.
4005 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4006 unsigned Limit, uint64_t Size,
4007 unsigned DstAlign, unsigned SrcAlign,
4013 const TargetLowering &TLI) {
4014 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4015 "Expecting memcpy / memset source to meet alignment requirement!");
4016 // If 'SrcAlign' is zero, that means the memory operation does not need to
4017 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4018 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4019 // is the specified alignment of the memory operation. If it is zero, that
4020 // means it's possible to change the alignment of the destination.
4021 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4022 // not need to be loaded.
4023 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4024 IsMemset, ZeroMemset, MemcpyStrSrc,
4025 DAG.getMachineFunction());
4027 if (VT == MVT::Other) {
4029 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4030 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4031 VT = TLI.getPointerTy();
4033 switch (DstAlign & 7) {
4034 case 0: VT = MVT::i64; break;
4035 case 4: VT = MVT::i32; break;
4036 case 2: VT = MVT::i16; break;
4037 default: VT = MVT::i8; break;
4042 while (!TLI.isTypeLegal(LVT))
4043 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4044 assert(LVT.isInteger());
4050 unsigned NumMemOps = 0;
4052 unsigned VTSize = VT.getSizeInBits() / 8;
4053 while (VTSize > Size) {
4054 // For now, only use non-vector load / store's for the left-over pieces.
4059 if (VT.isVector() || VT.isFloatingPoint()) {
4060 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4061 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4062 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4064 else if (NewVT == MVT::i64 &&
4065 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4066 TLI.isSafeMemOpType(MVT::f64)) {
4067 // i64 is usually not legal on 32-bit targets, but f64 may be.
4075 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4076 if (NewVT == MVT::i8)
4078 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4080 NewVTSize = NewVT.getSizeInBits() / 8;
4082 // If the new VT cannot cover all of the remaining bits, then consider
4083 // issuing a (or a pair of) unaligned and overlapping load / store.
4084 // FIXME: Only does this for 64-bit or more since we don't have proper
4085 // cost model for unaligned load / store.
4088 if (NumMemOps && AllowOverlap &&
4089 VTSize >= 8 && NewVTSize < Size &&
4090 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4098 if (++NumMemOps > Limit)
4101 MemOps.push_back(VT);
4108 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4109 SDValue Chain, SDValue Dst,
4110 SDValue Src, uint64_t Size,
4111 unsigned Align, bool isVol,
4113 MachinePointerInfo DstPtrInfo,
4114 MachinePointerInfo SrcPtrInfo) {
4115 // Turn a memcpy of undef to nop.
4116 if (Src.getOpcode() == ISD::UNDEF)
4119 // Expand memcpy to a series of load and store ops if the size operand falls
4120 // below a certain threshold.
4121 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4122 // rather than maybe a humongous number of loads and stores.
4123 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4124 std::vector<EVT> MemOps;
4125 bool DstAlignCanChange = false;
4126 MachineFunction &MF = DAG.getMachineFunction();
4127 MachineFrameInfo *MFI = MF.getFrameInfo();
4128 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4129 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4130 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4131 DstAlignCanChange = true;
4132 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4133 if (Align > SrcAlign)
4136 bool CopyFromStr = isMemSrcFromString(Src, Str);
4137 bool isZeroStr = CopyFromStr && Str.empty();
4138 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4140 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4141 (DstAlignCanChange ? 0 : Align),
4142 (isZeroStr ? 0 : SrcAlign),
4143 false, false, CopyFromStr, true, DAG, TLI))
4146 if (DstAlignCanChange) {
4147 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4148 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4150 // Don't promote to an alignment that would require dynamic stack
4152 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4153 if (!TRI->needsStackRealignment(MF))
4154 while (NewAlign > Align &&
4155 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4158 if (NewAlign > Align) {
4159 // Give the stack frame object a larger alignment if needed.
4160 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4161 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4166 SmallVector<SDValue, 8> OutChains;
4167 unsigned NumMemOps = MemOps.size();
4168 uint64_t SrcOff = 0, DstOff = 0;
4169 for (unsigned i = 0; i != NumMemOps; ++i) {
4171 unsigned VTSize = VT.getSizeInBits() / 8;
4172 SDValue Value, Store;
4174 if (VTSize > Size) {
4175 // Issuing an unaligned load / store pair that overlaps with the previous
4176 // pair. Adjust the offset accordingly.
4177 assert(i == NumMemOps-1 && i != 0);
4178 SrcOff -= VTSize - Size;
4179 DstOff -= VTSize - Size;
4183 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4184 // It's unlikely a store of a vector immediate can be done in a single
4185 // instruction. It would require a load from a constantpool first.
4186 // We only handle zero vectors here.
4187 // FIXME: Handle other cases where store of vector immediate is done in
4188 // a single instruction.
4189 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4190 if (Value.getNode())
4191 Store = DAG.getStore(Chain, dl, Value,
4192 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4193 DstPtrInfo.getWithOffset(DstOff), isVol,
4197 if (!Store.getNode()) {
4198 // The type might not be legal for the target. This should only happen
4199 // if the type is smaller than a legal type, as on PPC, so the right
4200 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4201 // to Load/Store if NVT==VT.
4202 // FIXME does the case above also need this?
4203 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4204 assert(NVT.bitsGE(VT));
4205 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4206 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4207 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4208 false, MinAlign(SrcAlign, SrcOff));
4209 Store = DAG.getTruncStore(Chain, dl, Value,
4210 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4211 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4214 OutChains.push_back(Store);
4220 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4223 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4224 SDValue Chain, SDValue Dst,
4225 SDValue Src, uint64_t Size,
4226 unsigned Align, bool isVol,
4228 MachinePointerInfo DstPtrInfo,
4229 MachinePointerInfo SrcPtrInfo) {
4230 // Turn a memmove of undef to nop.
4231 if (Src.getOpcode() == ISD::UNDEF)
4234 // Expand memmove to a series of load and store ops if the size operand falls
4235 // below a certain threshold.
4236 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4237 std::vector<EVT> MemOps;
4238 bool DstAlignCanChange = false;
4239 MachineFunction &MF = DAG.getMachineFunction();
4240 MachineFrameInfo *MFI = MF.getFrameInfo();
4241 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4242 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4243 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4244 DstAlignCanChange = true;
4245 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4246 if (Align > SrcAlign)
4248 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4250 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4251 (DstAlignCanChange ? 0 : Align), SrcAlign,
4252 false, false, false, false, DAG, TLI))
4255 if (DstAlignCanChange) {
4256 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4257 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4258 if (NewAlign > Align) {
4259 // Give the stack frame object a larger alignment if needed.
4260 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4261 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4266 uint64_t SrcOff = 0, DstOff = 0;
4267 SmallVector<SDValue, 8> LoadValues;
4268 SmallVector<SDValue, 8> LoadChains;
4269 SmallVector<SDValue, 8> OutChains;
4270 unsigned NumMemOps = MemOps.size();
4271 for (unsigned i = 0; i < NumMemOps; i++) {
4273 unsigned VTSize = VT.getSizeInBits() / 8;
4276 Value = DAG.getLoad(VT, dl, Chain,
4277 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4278 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4279 false, false, SrcAlign);
4280 LoadValues.push_back(Value);
4281 LoadChains.push_back(Value.getValue(1));
4284 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4286 for (unsigned i = 0; i < NumMemOps; i++) {
4288 unsigned VTSize = VT.getSizeInBits() / 8;
4291 Store = DAG.getStore(Chain, dl, LoadValues[i],
4292 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4293 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4294 OutChains.push_back(Store);
4298 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4301 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4304 /// \param DAG Selection DAG where lowered code is placed.
4305 /// \param dl Link to corresponding IR location.
4306 /// \param Chain Control flow dependency.
4307 /// \param Dst Pointer to destination memory location.
4308 /// \param Src Value of byte to write into the memory.
4309 /// \param Size Number of bytes to write.
4310 /// \param Align Alignment of the destination in bytes.
4311 /// \param isVol True if destination is volatile.
4312 /// \param DstPtrInfo IR information on the memory pointer.
4313 /// \returns New head in the control flow, if lowering was successful, empty
4314 /// SDValue otherwise.
4316 /// The function tries to replace 'llvm.memset' intrinsic with several store
4317 /// operations and value calculation code. This is usually profitable for small
4319 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4320 SDValue Chain, SDValue Dst,
4321 SDValue Src, uint64_t Size,
4322 unsigned Align, bool isVol,
4323 MachinePointerInfo DstPtrInfo) {
4324 // Turn a memset of undef to nop.
4325 if (Src.getOpcode() == ISD::UNDEF)
4328 // Expand memset to a series of load/store ops if the size operand
4329 // falls below a certain threshold.
4330 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4331 std::vector<EVT> MemOps;
4332 bool DstAlignCanChange = false;
4333 MachineFunction &MF = DAG.getMachineFunction();
4334 MachineFrameInfo *MFI = MF.getFrameInfo();
4335 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4336 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4337 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4338 DstAlignCanChange = true;
4340 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4341 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4342 Size, (DstAlignCanChange ? 0 : Align), 0,
4343 true, IsZeroVal, false, true, DAG, TLI))
4346 if (DstAlignCanChange) {
4347 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4348 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4349 if (NewAlign > Align) {
4350 // Give the stack frame object a larger alignment if needed.
4351 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4352 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4357 SmallVector<SDValue, 8> OutChains;
4358 uint64_t DstOff = 0;
4359 unsigned NumMemOps = MemOps.size();
4361 // Find the largest store and generate the bit pattern for it.
4362 EVT LargestVT = MemOps[0];
4363 for (unsigned i = 1; i < NumMemOps; i++)
4364 if (MemOps[i].bitsGT(LargestVT))
4365 LargestVT = MemOps[i];
4366 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4368 for (unsigned i = 0; i < NumMemOps; i++) {
4370 unsigned VTSize = VT.getSizeInBits() / 8;
4371 if (VTSize > Size) {
4372 // Issuing an unaligned load / store pair that overlaps with the previous
4373 // pair. Adjust the offset accordingly.
4374 assert(i == NumMemOps-1 && i != 0);
4375 DstOff -= VTSize - Size;
4378 // If this store is smaller than the largest store see whether we can get
4379 // the smaller value for free with a truncate.
4380 SDValue Value = MemSetValue;
4381 if (VT.bitsLT(LargestVT)) {
4382 if (!LargestVT.isVector() && !VT.isVector() &&
4383 TLI.isTruncateFree(LargestVT, VT))
4384 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4386 Value = getMemsetValue(Src, VT, DAG, dl);
4388 assert(Value.getValueType() == VT && "Value with wrong type.");
4389 SDValue Store = DAG.getStore(Chain, dl, Value,
4390 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4391 DstPtrInfo.getWithOffset(DstOff),
4392 isVol, false, Align);
4393 OutChains.push_back(Store);
4394 DstOff += VT.getSizeInBits() / 8;
4398 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4401 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4402 SDValue Src, SDValue Size,
4403 unsigned Align, bool isVol, bool AlwaysInline,
4404 bool isTailCall, MachinePointerInfo DstPtrInfo,
4405 MachinePointerInfo SrcPtrInfo) {
4406 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4408 // Check to see if we should lower the memcpy to loads and stores first.
4409 // For cases within the target-specified limits, this is the best choice.
4410 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4412 // Memcpy with size zero? Just return the original chain.
4413 if (ConstantSize->isNullValue())
4416 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4417 ConstantSize->getZExtValue(),Align,
4418 isVol, false, DstPtrInfo, SrcPtrInfo);
4419 if (Result.getNode())
4423 // Then check to see if we should lower the memcpy with target-specific
4424 // code. If the target chooses to do this, this is the next best.
4426 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4427 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4428 DstPtrInfo, SrcPtrInfo);
4429 if (Result.getNode())
4433 // If we really need inline code and the target declined to provide it,
4434 // use a (potentially long) sequence of loads and stores.
4436 assert(ConstantSize && "AlwaysInline requires a constant size!");
4437 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4438 ConstantSize->getZExtValue(), Align, isVol,
4439 true, DstPtrInfo, SrcPtrInfo);
4442 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4443 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4444 // respect volatile, so they may do things like read or write memory
4445 // beyond the given memory regions. But fixing this isn't easy, and most
4446 // people don't care.
4448 // Emit a library call.
4449 TargetLowering::ArgListTy Args;
4450 TargetLowering::ArgListEntry Entry;
4451 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4452 Entry.Node = Dst; Args.push_back(Entry);
4453 Entry.Node = Src; Args.push_back(Entry);
4454 Entry.Node = Size; Args.push_back(Entry);
4455 // FIXME: pass in SDLoc
4456 TargetLowering::CallLoweringInfo CLI(*this);
4457 CLI.setDebugLoc(dl).setChain(Chain)
4458 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4459 Type::getVoidTy(*getContext()),
4460 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4461 TLI->getPointerTy()), std::move(Args), 0)
4463 .setTailCall(isTailCall);
4465 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4466 return CallResult.second;
4469 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4470 SDValue Src, SDValue Size,
4471 unsigned Align, bool isVol, bool isTailCall,
4472 MachinePointerInfo DstPtrInfo,
4473 MachinePointerInfo SrcPtrInfo) {
4474 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4476 // Check to see if we should lower the memmove to loads and stores first.
4477 // For cases within the target-specified limits, this is the best choice.
4478 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4480 // Memmove with size zero? Just return the original chain.
4481 if (ConstantSize->isNullValue())
4485 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4486 ConstantSize->getZExtValue(), Align, isVol,
4487 false, DstPtrInfo, SrcPtrInfo);
4488 if (Result.getNode())
4492 // Then check to see if we should lower the memmove with target-specific
4493 // code. If the target chooses to do this, this is the next best.
4495 SDValue Result = TSI->EmitTargetCodeForMemmove(
4496 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4497 if (Result.getNode())
4501 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4502 // not be safe. See memcpy above for more details.
4504 // Emit a library call.
4505 TargetLowering::ArgListTy Args;
4506 TargetLowering::ArgListEntry Entry;
4507 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4508 Entry.Node = Dst; Args.push_back(Entry);
4509 Entry.Node = Src; Args.push_back(Entry);
4510 Entry.Node = Size; Args.push_back(Entry);
4511 // FIXME: pass in SDLoc
4512 TargetLowering::CallLoweringInfo CLI(*this);
4513 CLI.setDebugLoc(dl).setChain(Chain)
4514 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4515 Type::getVoidTy(*getContext()),
4516 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4517 TLI->getPointerTy()), std::move(Args), 0)
4519 .setTailCall(isTailCall);
4521 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4522 return CallResult.second;
4525 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4526 SDValue Src, SDValue Size,
4527 unsigned Align, bool isVol, bool isTailCall,
4528 MachinePointerInfo DstPtrInfo) {
4529 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4531 // Check to see if we should lower the memset to stores first.
4532 // For cases within the target-specified limits, this is the best choice.
4533 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4535 // Memset with size zero? Just return the original chain.
4536 if (ConstantSize->isNullValue())
4540 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4541 Align, isVol, DstPtrInfo);
4543 if (Result.getNode())
4547 // Then check to see if we should lower the memset with target-specific
4548 // code. If the target chooses to do this, this is the next best.
4550 SDValue Result = TSI->EmitTargetCodeForMemset(
4551 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4552 if (Result.getNode())
4556 // Emit a library call.
4557 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4558 TargetLowering::ArgListTy Args;
4559 TargetLowering::ArgListEntry Entry;
4560 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4561 Args.push_back(Entry);
4563 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4564 Args.push_back(Entry);
4566 Entry.Ty = IntPtrTy;
4567 Args.push_back(Entry);
4569 // FIXME: pass in SDLoc
4570 TargetLowering::CallLoweringInfo CLI(*this);
4571 CLI.setDebugLoc(dl).setChain(Chain)
4572 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4573 Type::getVoidTy(*getContext()),
4574 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4575 TLI->getPointerTy()), std::move(Args), 0)
4577 .setTailCall(isTailCall);
4579 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4580 return CallResult.second;
4583 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4584 SDVTList VTList, ArrayRef<SDValue> Ops,
4585 MachineMemOperand *MMO,
4586 AtomicOrdering SuccessOrdering,
4587 AtomicOrdering FailureOrdering,
4588 SynchronizationScope SynchScope) {
4589 FoldingSetNodeID ID;
4590 ID.AddInteger(MemVT.getRawBits());
4591 AddNodeIDNode(ID, Opcode, VTList, Ops);
4592 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4594 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4595 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4596 return SDValue(E, 0);
4599 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4600 // SDNode doesn't have access to it. This memory will be "leaked" when
4601 // the node is deallocated, but recovered when the allocator is released.
4602 // If the number of operands is less than 5 we use AtomicSDNode's internal
4604 unsigned NumOps = Ops.size();
4605 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4608 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4609 dl.getDebugLoc(), VTList, MemVT,
4610 Ops.data(), DynOps, NumOps, MMO,
4611 SuccessOrdering, FailureOrdering,
4613 CSEMap.InsertNode(N, IP);
4615 return SDValue(N, 0);
4618 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4619 SDVTList VTList, ArrayRef<SDValue> Ops,
4620 MachineMemOperand *MMO,
4621 AtomicOrdering Ordering,
4622 SynchronizationScope SynchScope) {
4623 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4624 Ordering, SynchScope);
4627 SDValue SelectionDAG::getAtomicCmpSwap(
4628 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4629 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4630 unsigned Alignment, AtomicOrdering SuccessOrdering,
4631 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4632 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4633 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4634 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4636 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4637 Alignment = getEVTAlignment(MemVT);
4639 MachineFunction &MF = getMachineFunction();
4641 // FIXME: Volatile isn't really correct; we should keep track of atomic
4642 // orderings in the memoperand.
4643 unsigned Flags = MachineMemOperand::MOVolatile;
4644 Flags |= MachineMemOperand::MOLoad;
4645 Flags |= MachineMemOperand::MOStore;
4647 MachineMemOperand *MMO =
4648 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4650 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4651 SuccessOrdering, FailureOrdering, SynchScope);
4654 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4655 SDVTList VTs, SDValue Chain, SDValue Ptr,
4656 SDValue Cmp, SDValue Swp,
4657 MachineMemOperand *MMO,
4658 AtomicOrdering SuccessOrdering,
4659 AtomicOrdering FailureOrdering,
4660 SynchronizationScope SynchScope) {
4661 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4662 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4663 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4665 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4666 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4667 SuccessOrdering, FailureOrdering, SynchScope);
4670 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4672 SDValue Ptr, SDValue Val,
4673 const Value* PtrVal,
4675 AtomicOrdering Ordering,
4676 SynchronizationScope SynchScope) {
4677 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4678 Alignment = getEVTAlignment(MemVT);
4680 MachineFunction &MF = getMachineFunction();
4681 // An atomic store does not load. An atomic load does not store.
4682 // (An atomicrmw obviously both loads and stores.)
4683 // For now, atomics are considered to be volatile always, and they are
4685 // FIXME: Volatile isn't really correct; we should keep track of atomic
4686 // orderings in the memoperand.
4687 unsigned Flags = MachineMemOperand::MOVolatile;
4688 if (Opcode != ISD::ATOMIC_STORE)
4689 Flags |= MachineMemOperand::MOLoad;
4690 if (Opcode != ISD::ATOMIC_LOAD)
4691 Flags |= MachineMemOperand::MOStore;
4693 MachineMemOperand *MMO =
4694 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4695 MemVT.getStoreSize(), Alignment);
4697 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4698 Ordering, SynchScope);
4701 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4703 SDValue Ptr, SDValue Val,
4704 MachineMemOperand *MMO,
4705 AtomicOrdering Ordering,
4706 SynchronizationScope SynchScope) {
4707 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4708 Opcode == ISD::ATOMIC_LOAD_SUB ||
4709 Opcode == ISD::ATOMIC_LOAD_AND ||
4710 Opcode == ISD::ATOMIC_LOAD_OR ||
4711 Opcode == ISD::ATOMIC_LOAD_XOR ||
4712 Opcode == ISD::ATOMIC_LOAD_NAND ||
4713 Opcode == ISD::ATOMIC_LOAD_MIN ||
4714 Opcode == ISD::ATOMIC_LOAD_MAX ||
4715 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4716 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4717 Opcode == ISD::ATOMIC_SWAP ||
4718 Opcode == ISD::ATOMIC_STORE) &&
4719 "Invalid Atomic Op");
4721 EVT VT = Val.getValueType();
4723 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4724 getVTList(VT, MVT::Other);
4725 SDValue Ops[] = {Chain, Ptr, Val};
4726 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4729 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4730 EVT VT, SDValue Chain,
4732 MachineMemOperand *MMO,
4733 AtomicOrdering Ordering,
4734 SynchronizationScope SynchScope) {
4735 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4737 SDVTList VTs = getVTList(VT, MVT::Other);
4738 SDValue Ops[] = {Chain, Ptr};
4739 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4742 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4743 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4744 if (Ops.size() == 1)
4747 SmallVector<EVT, 4> VTs;
4748 VTs.reserve(Ops.size());
4749 for (unsigned i = 0; i < Ops.size(); ++i)
4750 VTs.push_back(Ops[i].getValueType());
4751 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4755 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4756 ArrayRef<SDValue> Ops,
4757 EVT MemVT, MachinePointerInfo PtrInfo,
4758 unsigned Align, bool Vol,
4759 bool ReadMem, bool WriteMem, unsigned Size) {
4760 if (Align == 0) // Ensure that codegen never sees alignment 0
4761 Align = getEVTAlignment(MemVT);
4763 MachineFunction &MF = getMachineFunction();
4766 Flags |= MachineMemOperand::MOStore;
4768 Flags |= MachineMemOperand::MOLoad;
4770 Flags |= MachineMemOperand::MOVolatile;
4772 Size = MemVT.getStoreSize();
4773 MachineMemOperand *MMO =
4774 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4776 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4780 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4781 ArrayRef<SDValue> Ops, EVT MemVT,
4782 MachineMemOperand *MMO) {
4783 assert((Opcode == ISD::INTRINSIC_VOID ||
4784 Opcode == ISD::INTRINSIC_W_CHAIN ||
4785 Opcode == ISD::PREFETCH ||
4786 Opcode == ISD::LIFETIME_START ||
4787 Opcode == ISD::LIFETIME_END ||
4788 (Opcode <= INT_MAX &&
4789 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4790 "Opcode is not a memory-accessing opcode!");
4792 // Memoize the node unless it returns a flag.
4793 MemIntrinsicSDNode *N;
4794 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4795 FoldingSetNodeID ID;
4796 AddNodeIDNode(ID, Opcode, VTList, Ops);
4797 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4799 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4800 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4801 return SDValue(E, 0);
4804 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4805 dl.getDebugLoc(), VTList, Ops,
4807 CSEMap.InsertNode(N, IP);
4809 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4810 dl.getDebugLoc(), VTList, Ops,
4814 return SDValue(N, 0);
4817 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4818 /// MachinePointerInfo record from it. This is particularly useful because the
4819 /// code generator has many cases where it doesn't bother passing in a
4820 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4821 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4822 // If this is FI+Offset, we can model it.
4823 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4824 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4826 // If this is (FI+Offset1)+Offset2, we can model it.
4827 if (Ptr.getOpcode() != ISD::ADD ||
4828 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4829 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4830 return MachinePointerInfo();
4832 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4833 return MachinePointerInfo::getFixedStack(FI, Offset+
4834 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4837 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4838 /// MachinePointerInfo record from it. This is particularly useful because the
4839 /// code generator has many cases where it doesn't bother passing in a
4840 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4841 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4842 // If the 'Offset' value isn't a constant, we can't handle this.
4843 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4844 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4845 if (OffsetOp.getOpcode() == ISD::UNDEF)
4846 return InferPointerInfo(Ptr);
4847 return MachinePointerInfo();
4852 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4853 EVT VT, SDLoc dl, SDValue Chain,
4854 SDValue Ptr, SDValue Offset,
4855 MachinePointerInfo PtrInfo, EVT MemVT,
4856 bool isVolatile, bool isNonTemporal, bool isInvariant,
4857 unsigned Alignment, const AAMDNodes &AAInfo,
4858 const MDNode *Ranges) {
4859 assert(Chain.getValueType() == MVT::Other &&
4860 "Invalid chain type");
4861 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4862 Alignment = getEVTAlignment(VT);
4864 unsigned Flags = MachineMemOperand::MOLoad;
4866 Flags |= MachineMemOperand::MOVolatile;
4868 Flags |= MachineMemOperand::MONonTemporal;
4870 Flags |= MachineMemOperand::MOInvariant;
4872 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4874 if (PtrInfo.V.isNull())
4875 PtrInfo = InferPointerInfo(Ptr, Offset);
4877 MachineFunction &MF = getMachineFunction();
4878 MachineMemOperand *MMO =
4879 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4881 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4885 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4886 EVT VT, SDLoc dl, SDValue Chain,
4887 SDValue Ptr, SDValue Offset, EVT MemVT,
4888 MachineMemOperand *MMO) {
4890 ExtType = ISD::NON_EXTLOAD;
4891 } else if (ExtType == ISD::NON_EXTLOAD) {
4892 assert(VT == MemVT && "Non-extending load from different memory type!");
4895 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4896 "Should only be an extending load, not truncating!");
4897 assert(VT.isInteger() == MemVT.isInteger() &&
4898 "Cannot convert from FP to Int or Int -> FP!");
4899 assert(VT.isVector() == MemVT.isVector() &&
4900 "Cannot use an ext load to convert to or from a vector!");
4901 assert((!VT.isVector() ||
4902 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4903 "Cannot use an ext load to change the number of vector elements!");
4906 bool Indexed = AM != ISD::UNINDEXED;
4907 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4908 "Unindexed load with an offset!");
4910 SDVTList VTs = Indexed ?
4911 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4912 SDValue Ops[] = { Chain, Ptr, Offset };
4913 FoldingSetNodeID ID;
4914 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4915 ID.AddInteger(MemVT.getRawBits());
4916 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4917 MMO->isNonTemporal(),
4918 MMO->isInvariant()));
4919 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4921 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4922 cast<LoadSDNode>(E)->refineAlignment(MMO);
4923 return SDValue(E, 0);
4925 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4926 dl.getDebugLoc(), VTs, AM, ExtType,
4928 CSEMap.InsertNode(N, IP);
4930 return SDValue(N, 0);
4933 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4934 SDValue Chain, SDValue Ptr,
4935 MachinePointerInfo PtrInfo,
4936 bool isVolatile, bool isNonTemporal,
4937 bool isInvariant, unsigned Alignment,
4938 const AAMDNodes &AAInfo,
4939 const MDNode *Ranges) {
4940 SDValue Undef = getUNDEF(Ptr.getValueType());
4941 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4942 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4946 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4947 SDValue Chain, SDValue Ptr,
4948 MachineMemOperand *MMO) {
4949 SDValue Undef = getUNDEF(Ptr.getValueType());
4950 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4954 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4955 SDValue Chain, SDValue Ptr,
4956 MachinePointerInfo PtrInfo, EVT MemVT,
4957 bool isVolatile, bool isNonTemporal,
4958 bool isInvariant, unsigned Alignment,
4959 const AAMDNodes &AAInfo) {
4960 SDValue Undef = getUNDEF(Ptr.getValueType());
4961 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4962 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4967 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4968 SDValue Chain, SDValue Ptr, EVT MemVT,
4969 MachineMemOperand *MMO) {
4970 SDValue Undef = getUNDEF(Ptr.getValueType());
4971 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4976 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4977 SDValue Offset, ISD::MemIndexedMode AM) {
4978 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4979 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4980 "Load is already a indexed load!");
4981 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4982 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4983 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4984 false, LD->getAlignment());
4987 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4988 SDValue Ptr, MachinePointerInfo PtrInfo,
4989 bool isVolatile, bool isNonTemporal,
4990 unsigned Alignment, const AAMDNodes &AAInfo) {
4991 assert(Chain.getValueType() == MVT::Other &&
4992 "Invalid chain type");
4993 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4994 Alignment = getEVTAlignment(Val.getValueType());
4996 unsigned Flags = MachineMemOperand::MOStore;
4998 Flags |= MachineMemOperand::MOVolatile;
5000 Flags |= MachineMemOperand::MONonTemporal;
5002 if (PtrInfo.V.isNull())
5003 PtrInfo = InferPointerInfo(Ptr);
5005 MachineFunction &MF = getMachineFunction();
5006 MachineMemOperand *MMO =
5007 MF.getMachineMemOperand(PtrInfo, Flags,
5008 Val.getValueType().getStoreSize(), Alignment,
5011 return getStore(Chain, dl, Val, Ptr, MMO);
5014 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5015 SDValue Ptr, MachineMemOperand *MMO) {
5016 assert(Chain.getValueType() == MVT::Other &&
5017 "Invalid chain type");
5018 EVT VT = Val.getValueType();
5019 SDVTList VTs = getVTList(MVT::Other);
5020 SDValue Undef = getUNDEF(Ptr.getValueType());
5021 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5022 FoldingSetNodeID ID;
5023 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5024 ID.AddInteger(VT.getRawBits());
5025 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5026 MMO->isNonTemporal(), MMO->isInvariant()));
5027 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5029 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5030 cast<StoreSDNode>(E)->refineAlignment(MMO);
5031 return SDValue(E, 0);
5033 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5034 dl.getDebugLoc(), VTs,
5035 ISD::UNINDEXED, false, VT, MMO);
5036 CSEMap.InsertNode(N, IP);
5038 return SDValue(N, 0);
5041 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5042 SDValue Ptr, MachinePointerInfo PtrInfo,
5043 EVT SVT,bool isVolatile, bool isNonTemporal,
5045 const AAMDNodes &AAInfo) {
5046 assert(Chain.getValueType() == MVT::Other &&
5047 "Invalid chain type");
5048 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5049 Alignment = getEVTAlignment(SVT);
5051 unsigned Flags = MachineMemOperand::MOStore;
5053 Flags |= MachineMemOperand::MOVolatile;
5055 Flags |= MachineMemOperand::MONonTemporal;
5057 if (PtrInfo.V.isNull())
5058 PtrInfo = InferPointerInfo(Ptr);
5060 MachineFunction &MF = getMachineFunction();
5061 MachineMemOperand *MMO =
5062 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5065 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5068 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5069 SDValue Ptr, EVT SVT,
5070 MachineMemOperand *MMO) {
5071 EVT VT = Val.getValueType();
5073 assert(Chain.getValueType() == MVT::Other &&
5074 "Invalid chain type");
5076 return getStore(Chain, dl, Val, Ptr, MMO);
5078 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5079 "Should only be a truncating store, not extending!");
5080 assert(VT.isInteger() == SVT.isInteger() &&
5081 "Can't do FP-INT conversion!");
5082 assert(VT.isVector() == SVT.isVector() &&
5083 "Cannot use trunc store to convert to or from a vector!");
5084 assert((!VT.isVector() ||
5085 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5086 "Cannot use trunc store to change the number of vector elements!");
5088 SDVTList VTs = getVTList(MVT::Other);
5089 SDValue Undef = getUNDEF(Ptr.getValueType());
5090 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5091 FoldingSetNodeID ID;
5092 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5093 ID.AddInteger(SVT.getRawBits());
5094 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5095 MMO->isNonTemporal(), MMO->isInvariant()));
5096 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5098 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5099 cast<StoreSDNode>(E)->refineAlignment(MMO);
5100 return SDValue(E, 0);
5102 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5103 dl.getDebugLoc(), VTs,
5104 ISD::UNINDEXED, true, SVT, MMO);
5105 CSEMap.InsertNode(N, IP);
5107 return SDValue(N, 0);
5111 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5112 SDValue Offset, ISD::MemIndexedMode AM) {
5113 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5114 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5115 "Store is already a indexed store!");
5116 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5117 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5118 FoldingSetNodeID ID;
5119 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5120 ID.AddInteger(ST->getMemoryVT().getRawBits());
5121 ID.AddInteger(ST->getRawSubclassData());
5122 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5124 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5125 return SDValue(E, 0);
5127 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5128 dl.getDebugLoc(), VTs, AM,
5129 ST->isTruncatingStore(),
5131 ST->getMemOperand());
5132 CSEMap.InsertNode(N, IP);
5134 return SDValue(N, 0);
5138 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5139 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5140 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5142 SDVTList VTs = getVTList(VT, MVT::Other);
5143 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5144 FoldingSetNodeID ID;
5145 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5146 ID.AddInteger(VT.getRawBits());
5147 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5149 MMO->isNonTemporal(),
5150 MMO->isInvariant()));
5151 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5153 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5154 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5155 return SDValue(E, 0);
5157 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5158 dl.getDebugLoc(), Ops, 4, VTs,
5160 CSEMap.InsertNode(N, IP);
5162 return SDValue(N, 0);
5165 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5166 SDValue Ptr, SDValue Mask, EVT MemVT,
5167 MachineMemOperand *MMO, bool isTrunc) {
5168 assert(Chain.getValueType() == MVT::Other &&
5169 "Invalid chain type");
5170 EVT VT = Val.getValueType();
5171 SDVTList VTs = getVTList(MVT::Other);
5172 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5173 FoldingSetNodeID ID;
5174 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5175 ID.AddInteger(VT.getRawBits());
5176 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5177 MMO->isNonTemporal(), MMO->isInvariant()));
5178 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5180 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5181 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5182 return SDValue(E, 0);
5184 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5185 dl.getDebugLoc(), Ops, 4,
5186 VTs, isTrunc, MemVT, MMO);
5187 CSEMap.InsertNode(N, IP);
5189 return SDValue(N, 0);
5193 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5194 ArrayRef<SDValue> Ops,
5195 MachineMemOperand *MMO) {
5197 FoldingSetNodeID ID;
5198 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5199 ID.AddInteger(VT.getRawBits());
5200 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5202 MMO->isNonTemporal(),
5203 MMO->isInvariant()));
5204 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5206 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5207 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5208 return SDValue(E, 0);
5210 MaskedGatherSDNode *N =
5211 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5213 CSEMap.InsertNode(N, IP);
5215 return SDValue(N, 0);
5218 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5219 ArrayRef<SDValue> Ops,
5220 MachineMemOperand *MMO) {
5221 FoldingSetNodeID ID;
5222 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5223 ID.AddInteger(VT.getRawBits());
5224 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5225 MMO->isNonTemporal(),
5226 MMO->isInvariant()));
5227 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5229 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5230 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5231 return SDValue(E, 0);
5234 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5236 CSEMap.InsertNode(N, IP);
5238 return SDValue(N, 0);
5241 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5242 SDValue Chain, SDValue Ptr,
5245 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5246 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5249 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5250 ArrayRef<SDUse> Ops) {
5251 switch (Ops.size()) {
5252 case 0: return getNode(Opcode, DL, VT);
5253 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5254 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5255 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5259 // Copy from an SDUse array into an SDValue array for use with
5260 // the regular getNode logic.
5261 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5262 return getNode(Opcode, DL, VT, NewOps);
5265 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5266 ArrayRef<SDValue> Ops) {
5267 unsigned NumOps = Ops.size();
5269 case 0: return getNode(Opcode, DL, VT);
5270 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5271 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5272 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5278 case ISD::SELECT_CC: {
5279 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5280 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5281 "LHS and RHS of condition must have same type!");
5282 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5283 "True and False arms of SelectCC must have same type!");
5284 assert(Ops[2].getValueType() == VT &&
5285 "select_cc node must be of same type as true and false value!");
5289 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5290 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5291 "LHS/RHS of comparison should match types!");
5298 SDVTList VTs = getVTList(VT);
5300 if (VT != MVT::Glue) {
5301 FoldingSetNodeID ID;
5302 AddNodeIDNode(ID, Opcode, VTs, Ops);
5305 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5306 return SDValue(E, 0);
5308 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5310 CSEMap.InsertNode(N, IP);
5312 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5317 return SDValue(N, 0);
5320 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5321 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5322 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5325 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5326 ArrayRef<SDValue> Ops) {
5327 if (VTList.NumVTs == 1)
5328 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5332 // FIXME: figure out how to safely handle things like
5333 // int foo(int x) { return 1 << (x & 255); }
5334 // int bar() { return foo(256); }
5335 case ISD::SRA_PARTS:
5336 case ISD::SRL_PARTS:
5337 case ISD::SHL_PARTS:
5338 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5339 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5340 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5341 else if (N3.getOpcode() == ISD::AND)
5342 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5343 // If the and is only masking out bits that cannot effect the shift,
5344 // eliminate the and.
5345 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5346 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5347 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5353 // Memoize the node unless it returns a flag.
5355 unsigned NumOps = Ops.size();
5356 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5357 FoldingSetNodeID ID;
5358 AddNodeIDNode(ID, Opcode, VTList, Ops);
5360 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5361 return SDValue(E, 0);
5364 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5365 DL.getDebugLoc(), VTList, Ops[0]);
5366 } else if (NumOps == 2) {
5367 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5368 DL.getDebugLoc(), VTList, Ops[0],
5370 } else if (NumOps == 3) {
5371 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5372 DL.getDebugLoc(), VTList, Ops[0],
5375 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5378 CSEMap.InsertNode(N, IP);
5381 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5382 DL.getDebugLoc(), VTList, Ops[0]);
5383 } else if (NumOps == 2) {
5384 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5385 DL.getDebugLoc(), VTList, Ops[0],
5387 } else if (NumOps == 3) {
5388 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5389 DL.getDebugLoc(), VTList, Ops[0],
5392 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5397 return SDValue(N, 0);
5400 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5401 return getNode(Opcode, DL, VTList, None);
5404 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5406 SDValue Ops[] = { N1 };
5407 return getNode(Opcode, DL, VTList, Ops);
5410 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5411 SDValue N1, SDValue N2) {
5412 SDValue Ops[] = { N1, N2 };
5413 return getNode(Opcode, DL, VTList, Ops);
5416 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5417 SDValue N1, SDValue N2, SDValue N3) {
5418 SDValue Ops[] = { N1, N2, N3 };
5419 return getNode(Opcode, DL, VTList, Ops);
5422 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5423 SDValue N1, SDValue N2, SDValue N3,
5425 SDValue Ops[] = { N1, N2, N3, N4 };
5426 return getNode(Opcode, DL, VTList, Ops);
5429 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5430 SDValue N1, SDValue N2, SDValue N3,
5431 SDValue N4, SDValue N5) {
5432 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5433 return getNode(Opcode, DL, VTList, Ops);
5436 SDVTList SelectionDAG::getVTList(EVT VT) {
5437 return makeVTList(SDNode::getValueTypeList(VT), 1);
5440 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5441 FoldingSetNodeID ID;
5443 ID.AddInteger(VT1.getRawBits());
5444 ID.AddInteger(VT2.getRawBits());
5447 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5449 EVT *Array = Allocator.Allocate<EVT>(2);
5452 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5453 VTListMap.InsertNode(Result, IP);
5455 return Result->getSDVTList();
5458 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5459 FoldingSetNodeID ID;
5461 ID.AddInteger(VT1.getRawBits());
5462 ID.AddInteger(VT2.getRawBits());
5463 ID.AddInteger(VT3.getRawBits());
5466 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5468 EVT *Array = Allocator.Allocate<EVT>(3);
5472 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5473 VTListMap.InsertNode(Result, IP);
5475 return Result->getSDVTList();
5478 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5479 FoldingSetNodeID ID;
5481 ID.AddInteger(VT1.getRawBits());
5482 ID.AddInteger(VT2.getRawBits());
5483 ID.AddInteger(VT3.getRawBits());
5484 ID.AddInteger(VT4.getRawBits());
5487 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5489 EVT *Array = Allocator.Allocate<EVT>(4);
5494 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5495 VTListMap.InsertNode(Result, IP);
5497 return Result->getSDVTList();
5500 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5501 unsigned NumVTs = VTs.size();
5502 FoldingSetNodeID ID;
5503 ID.AddInteger(NumVTs);
5504 for (unsigned index = 0; index < NumVTs; index++) {
5505 ID.AddInteger(VTs[index].getRawBits());
5509 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5511 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5512 std::copy(VTs.begin(), VTs.end(), Array);
5513 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5514 VTListMap.InsertNode(Result, IP);
5516 return Result->getSDVTList();
5520 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5521 /// specified operands. If the resultant node already exists in the DAG,
5522 /// this does not modify the specified node, instead it returns the node that
5523 /// already exists. If the resultant node does not exist in the DAG, the
5524 /// input node is returned. As a degenerate case, if you specify the same
5525 /// input operands as the node already has, the input node is returned.
5526 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5527 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5529 // Check to see if there is no change.
5530 if (Op == N->getOperand(0)) return N;
5532 // See if the modified node already exists.
5533 void *InsertPos = nullptr;
5534 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5537 // Nope it doesn't. Remove the node from its current place in the maps.
5539 if (!RemoveNodeFromCSEMaps(N))
5540 InsertPos = nullptr;
5542 // Now we update the operands.
5543 N->OperandList[0].set(Op);
5545 // If this gets put into a CSE map, add it.
5546 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5550 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5551 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5553 // Check to see if there is no change.
5554 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5555 return N; // No operands changed, just return the input node.
5557 // See if the modified node already exists.
5558 void *InsertPos = nullptr;
5559 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5562 // Nope it doesn't. Remove the node from its current place in the maps.
5564 if (!RemoveNodeFromCSEMaps(N))
5565 InsertPos = nullptr;
5567 // Now we update the operands.
5568 if (N->OperandList[0] != Op1)
5569 N->OperandList[0].set(Op1);
5570 if (N->OperandList[1] != Op2)
5571 N->OperandList[1].set(Op2);
5573 // If this gets put into a CSE map, add it.
5574 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5578 SDNode *SelectionDAG::
5579 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5580 SDValue Ops[] = { Op1, Op2, Op3 };
5581 return UpdateNodeOperands(N, Ops);
5584 SDNode *SelectionDAG::
5585 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5586 SDValue Op3, SDValue Op4) {
5587 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5588 return UpdateNodeOperands(N, Ops);
5591 SDNode *SelectionDAG::
5592 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5593 SDValue Op3, SDValue Op4, SDValue Op5) {
5594 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5595 return UpdateNodeOperands(N, Ops);
5598 SDNode *SelectionDAG::
5599 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5600 unsigned NumOps = Ops.size();
5601 assert(N->getNumOperands() == NumOps &&
5602 "Update with wrong number of operands");
5604 // If no operands changed just return the input node.
5605 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5608 // See if the modified node already exists.
5609 void *InsertPos = nullptr;
5610 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5613 // Nope it doesn't. Remove the node from its current place in the maps.
5615 if (!RemoveNodeFromCSEMaps(N))
5616 InsertPos = nullptr;
5618 // Now we update the operands.
5619 for (unsigned i = 0; i != NumOps; ++i)
5620 if (N->OperandList[i] != Ops[i])
5621 N->OperandList[i].set(Ops[i]);
5623 // If this gets put into a CSE map, add it.
5624 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5628 /// DropOperands - Release the operands and set this node to have
5630 void SDNode::DropOperands() {
5631 // Unlike the code in MorphNodeTo that does this, we don't need to
5632 // watch for dead nodes here.
5633 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5639 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5642 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5644 SDVTList VTs = getVTList(VT);
5645 return SelectNodeTo(N, MachineOpc, VTs, None);
5648 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5649 EVT VT, SDValue Op1) {
5650 SDVTList VTs = getVTList(VT);
5651 SDValue Ops[] = { Op1 };
5652 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5655 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5656 EVT VT, SDValue Op1,
5658 SDVTList VTs = getVTList(VT);
5659 SDValue Ops[] = { Op1, Op2 };
5660 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5663 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5664 EVT VT, SDValue Op1,
5665 SDValue Op2, SDValue Op3) {
5666 SDVTList VTs = getVTList(VT);
5667 SDValue Ops[] = { Op1, Op2, Op3 };
5668 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5671 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5672 EVT VT, ArrayRef<SDValue> Ops) {
5673 SDVTList VTs = getVTList(VT);
5674 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5677 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5678 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5679 SDVTList VTs = getVTList(VT1, VT2);
5680 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5683 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5685 SDVTList VTs = getVTList(VT1, VT2);
5686 return SelectNodeTo(N, MachineOpc, VTs, None);
5689 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5690 EVT VT1, EVT VT2, EVT VT3,
5691 ArrayRef<SDValue> Ops) {
5692 SDVTList VTs = getVTList(VT1, VT2, VT3);
5693 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5696 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5697 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5698 ArrayRef<SDValue> Ops) {
5699 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5700 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5703 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5706 SDVTList VTs = getVTList(VT1, VT2);
5707 SDValue Ops[] = { Op1 };
5708 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5711 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5713 SDValue Op1, SDValue Op2) {
5714 SDVTList VTs = getVTList(VT1, VT2);
5715 SDValue Ops[] = { Op1, Op2 };
5716 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5719 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5721 SDValue Op1, SDValue Op2,
5723 SDVTList VTs = getVTList(VT1, VT2);
5724 SDValue Ops[] = { Op1, Op2, Op3 };
5725 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5728 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5729 EVT VT1, EVT VT2, EVT VT3,
5730 SDValue Op1, SDValue Op2,
5732 SDVTList VTs = getVTList(VT1, VT2, VT3);
5733 SDValue Ops[] = { Op1, Op2, Op3 };
5734 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5737 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5738 SDVTList VTs,ArrayRef<SDValue> Ops) {
5739 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5740 // Reset the NodeID to -1.
5745 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5746 /// the line number information on the merged node since it is not possible to
5747 /// preserve the information that operation is associated with multiple lines.
5748 /// This will make the debugger working better at -O0, were there is a higher
5749 /// probability having other instructions associated with that line.
5751 /// For IROrder, we keep the smaller of the two
5752 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5753 DebugLoc NLoc = N->getDebugLoc();
5754 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5755 N->setDebugLoc(DebugLoc());
5757 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5758 N->setIROrder(Order);
5762 /// MorphNodeTo - This *mutates* the specified node to have the specified
5763 /// return type, opcode, and operands.
5765 /// Note that MorphNodeTo returns the resultant node. If there is already a
5766 /// node of the specified opcode and operands, it returns that node instead of
5767 /// the current one. Note that the SDLoc need not be the same.
5769 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5770 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5771 /// node, and because it doesn't require CSE recalculation for any of
5772 /// the node's users.
5774 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5775 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5776 /// the legalizer which maintain worklists that would need to be updated when
5777 /// deleting things.
5778 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5779 SDVTList VTs, ArrayRef<SDValue> Ops) {
5780 unsigned NumOps = Ops.size();
5781 // If an identical node already exists, use it.
5783 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5784 FoldingSetNodeID ID;
5785 AddNodeIDNode(ID, Opc, VTs, Ops);
5786 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5787 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5790 if (!RemoveNodeFromCSEMaps(N))
5793 // Start the morphing.
5795 N->ValueList = VTs.VTs;
5796 N->NumValues = VTs.NumVTs;
5798 // Clear the operands list, updating used nodes to remove this from their
5799 // use list. Keep track of any operands that become dead as a result.
5800 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5801 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5803 SDNode *Used = Use.getNode();
5805 if (Used->use_empty())
5806 DeadNodeSet.insert(Used);
5809 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5810 // Initialize the memory references information.
5811 MN->setMemRefs(nullptr, nullptr);
5812 // If NumOps is larger than the # of operands we can have in a
5813 // MachineSDNode, reallocate the operand list.
5814 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5815 if (MN->OperandsNeedDelete)
5816 delete[] MN->OperandList;
5817 if (NumOps > array_lengthof(MN->LocalOperands))
5818 // We're creating a final node that will live unmorphed for the
5819 // remainder of the current SelectionDAG iteration, so we can allocate
5820 // the operands directly out of a pool with no recycling metadata.
5821 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5822 Ops.data(), NumOps);
5824 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5825 MN->OperandsNeedDelete = false;
5827 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5829 // If NumOps is larger than the # of operands we currently have, reallocate
5830 // the operand list.
5831 if (NumOps > N->NumOperands) {
5832 if (N->OperandsNeedDelete)
5833 delete[] N->OperandList;
5834 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5835 N->OperandsNeedDelete = true;
5837 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5840 // Delete any nodes that are still dead after adding the uses for the
5842 if (!DeadNodeSet.empty()) {
5843 SmallVector<SDNode *, 16> DeadNodes;
5844 for (SDNode *N : DeadNodeSet)
5846 DeadNodes.push_back(N);
5847 RemoveDeadNodes(DeadNodes);
5851 CSEMap.InsertNode(N, IP); // Memoize the new node.
5856 /// getMachineNode - These are used for target selectors to create a new node
5857 /// with specified return type(s), MachineInstr opcode, and operands.
5859 /// Note that getMachineNode returns the resultant node. If there is already a
5860 /// node of the specified opcode and operands, it returns that node instead of
5861 /// the current one.
5863 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5864 SDVTList VTs = getVTList(VT);
5865 return getMachineNode(Opcode, dl, VTs, None);
5869 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5870 SDVTList VTs = getVTList(VT);
5871 SDValue Ops[] = { Op1 };
5872 return getMachineNode(Opcode, dl, VTs, Ops);
5876 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5877 SDValue Op1, SDValue Op2) {
5878 SDVTList VTs = getVTList(VT);
5879 SDValue Ops[] = { Op1, Op2 };
5880 return getMachineNode(Opcode, dl, VTs, Ops);
5884 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5885 SDValue Op1, SDValue Op2, SDValue Op3) {
5886 SDVTList VTs = getVTList(VT);
5887 SDValue Ops[] = { Op1, Op2, Op3 };
5888 return getMachineNode(Opcode, dl, VTs, Ops);
5892 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5893 ArrayRef<SDValue> Ops) {
5894 SDVTList VTs = getVTList(VT);
5895 return getMachineNode(Opcode, dl, VTs, Ops);
5899 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5900 SDVTList VTs = getVTList(VT1, VT2);
5901 return getMachineNode(Opcode, dl, VTs, None);
5905 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5906 EVT VT1, EVT VT2, SDValue Op1) {
5907 SDVTList VTs = getVTList(VT1, VT2);
5908 SDValue Ops[] = { Op1 };
5909 return getMachineNode(Opcode, dl, VTs, Ops);
5913 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5914 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5915 SDVTList VTs = getVTList(VT1, VT2);
5916 SDValue Ops[] = { Op1, Op2 };
5917 return getMachineNode(Opcode, dl, VTs, Ops);
5921 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5922 EVT VT1, EVT VT2, SDValue Op1,
5923 SDValue Op2, SDValue Op3) {
5924 SDVTList VTs = getVTList(VT1, VT2);
5925 SDValue Ops[] = { Op1, Op2, Op3 };
5926 return getMachineNode(Opcode, dl, VTs, Ops);
5930 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5932 ArrayRef<SDValue> Ops) {
5933 SDVTList VTs = getVTList(VT1, VT2);
5934 return getMachineNode(Opcode, dl, VTs, Ops);
5938 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5939 EVT VT1, EVT VT2, EVT VT3,
5940 SDValue Op1, SDValue Op2) {
5941 SDVTList VTs = getVTList(VT1, VT2, VT3);
5942 SDValue Ops[] = { Op1, Op2 };
5943 return getMachineNode(Opcode, dl, VTs, Ops);
5947 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5948 EVT VT1, EVT VT2, EVT VT3,
5949 SDValue Op1, SDValue Op2, SDValue Op3) {
5950 SDVTList VTs = getVTList(VT1, VT2, VT3);
5951 SDValue Ops[] = { Op1, Op2, Op3 };
5952 return getMachineNode(Opcode, dl, VTs, Ops);
5956 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5957 EVT VT1, EVT VT2, EVT VT3,
5958 ArrayRef<SDValue> Ops) {
5959 SDVTList VTs = getVTList(VT1, VT2, VT3);
5960 return getMachineNode(Opcode, dl, VTs, Ops);
5964 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5965 EVT VT2, EVT VT3, EVT VT4,
5966 ArrayRef<SDValue> Ops) {
5967 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5968 return getMachineNode(Opcode, dl, VTs, Ops);
5972 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5973 ArrayRef<EVT> ResultTys,
5974 ArrayRef<SDValue> Ops) {
5975 SDVTList VTs = getVTList(ResultTys);
5976 return getMachineNode(Opcode, dl, VTs, Ops);
5980 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5981 ArrayRef<SDValue> OpsArray) {
5982 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5985 const SDValue *Ops = OpsArray.data();
5986 unsigned NumOps = OpsArray.size();
5989 FoldingSetNodeID ID;
5990 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5992 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5993 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5997 // Allocate a new MachineSDNode.
5998 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5999 DL.getDebugLoc(), VTs);
6001 // Initialize the operands list.
6002 if (NumOps > array_lengthof(N->LocalOperands))
6003 // We're creating a final node that will live unmorphed for the
6004 // remainder of the current SelectionDAG iteration, so we can allocate
6005 // the operands directly out of a pool with no recycling metadata.
6006 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6009 N->InitOperands(N->LocalOperands, Ops, NumOps);
6010 N->OperandsNeedDelete = false;
6013 CSEMap.InsertNode(N, IP);
6019 /// getTargetExtractSubreg - A convenience function for creating
6020 /// TargetOpcode::EXTRACT_SUBREG nodes.
6022 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6024 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6025 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6026 VT, Operand, SRIdxVal);
6027 return SDValue(Subreg, 0);
6030 /// getTargetInsertSubreg - A convenience function for creating
6031 /// TargetOpcode::INSERT_SUBREG nodes.
6033 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6034 SDValue Operand, SDValue Subreg) {
6035 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6036 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6037 VT, Operand, Subreg, SRIdxVal);
6038 return SDValue(Result, 0);
6041 /// getNodeIfExists - Get the specified node if it's already available, or
6042 /// else return NULL.
6043 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6044 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6046 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6047 FoldingSetNodeID ID;
6048 AddNodeIDNode(ID, Opcode, VTList, Ops);
6049 if (isBinOpWithFlags(Opcode))
6050 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6052 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6058 /// getDbgValue - Creates a SDDbgValue node.
6061 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6062 unsigned R, bool IsIndirect, uint64_t Off,
6063 DebugLoc DL, unsigned O) {
6064 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6065 "Expected inlined-at fields to agree");
6066 return new (DbgInfo->getAlloc())
6067 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6071 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6072 const Value *C, uint64_t Off,
6073 DebugLoc DL, unsigned O) {
6074 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6075 "Expected inlined-at fields to agree");
6076 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6080 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6081 unsigned FI, uint64_t Off,
6082 DebugLoc DL, unsigned O) {
6083 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6084 "Expected inlined-at fields to agree");
6085 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6090 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6091 /// pointed to by a use iterator is deleted, increment the use iterator
6092 /// so that it doesn't dangle.
6094 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6095 SDNode::use_iterator &UI;
6096 SDNode::use_iterator &UE;
6098 void NodeDeleted(SDNode *N, SDNode *E) override {
6099 // Increment the iterator as needed.
6100 while (UI != UE && N == *UI)
6105 RAUWUpdateListener(SelectionDAG &d,
6106 SDNode::use_iterator &ui,
6107 SDNode::use_iterator &ue)
6108 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6113 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6114 /// This can cause recursive merging of nodes in the DAG.
6116 /// This version assumes From has a single result value.
6118 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6119 SDNode *From = FromN.getNode();
6120 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6121 "Cannot replace with this method!");
6122 assert(From != To.getNode() && "Cannot replace uses of with self");
6124 // Iterate over all the existing uses of From. New uses will be added
6125 // to the beginning of the use list, which we avoid visiting.
6126 // This specifically avoids visiting uses of From that arise while the
6127 // replacement is happening, because any such uses would be the result
6128 // of CSE: If an existing node looks like From after one of its operands
6129 // is replaced by To, we don't want to replace of all its users with To
6130 // too. See PR3018 for more info.
6131 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6132 RAUWUpdateListener Listener(*this, UI, UE);
6136 // This node is about to morph, remove its old self from the CSE maps.
6137 RemoveNodeFromCSEMaps(User);
6139 // A user can appear in a use list multiple times, and when this
6140 // happens the uses are usually next to each other in the list.
6141 // To help reduce the number of CSE recomputations, process all
6142 // the uses of this user that we can find this way.
6144 SDUse &Use = UI.getUse();
6147 } while (UI != UE && *UI == User);
6149 // Now that we have modified User, add it back to the CSE maps. If it
6150 // already exists there, recursively merge the results together.
6151 AddModifiedNodeToCSEMaps(User);
6154 // If we just RAUW'd the root, take note.
6155 if (FromN == getRoot())
6159 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6160 /// This can cause recursive merging of nodes in the DAG.
6162 /// This version assumes that for each value of From, there is a
6163 /// corresponding value in To in the same position with the same type.
6165 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6167 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6168 assert((!From->hasAnyUseOfValue(i) ||
6169 From->getValueType(i) == To->getValueType(i)) &&
6170 "Cannot use this version of ReplaceAllUsesWith!");
6173 // Handle the trivial case.
6177 // Iterate over just the existing users of From. See the comments in
6178 // the ReplaceAllUsesWith above.
6179 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6180 RAUWUpdateListener Listener(*this, UI, UE);
6184 // This node is about to morph, remove its old self from the CSE maps.
6185 RemoveNodeFromCSEMaps(User);
6187 // A user can appear in a use list multiple times, and when this
6188 // happens the uses are usually next to each other in the list.
6189 // To help reduce the number of CSE recomputations, process all
6190 // the uses of this user that we can find this way.
6192 SDUse &Use = UI.getUse();
6195 } while (UI != UE && *UI == User);
6197 // Now that we have modified User, add it back to the CSE maps. If it
6198 // already exists there, recursively merge the results together.
6199 AddModifiedNodeToCSEMaps(User);
6202 // If we just RAUW'd the root, take note.
6203 if (From == getRoot().getNode())
6204 setRoot(SDValue(To, getRoot().getResNo()));
6207 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6208 /// This can cause recursive merging of nodes in the DAG.
6210 /// This version can replace From with any result values. To must match the
6211 /// number and types of values returned by From.
6212 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6213 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6214 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6216 // Iterate over just the existing users of From. See the comments in
6217 // the ReplaceAllUsesWith above.
6218 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6219 RAUWUpdateListener Listener(*this, UI, UE);
6223 // This node is about to morph, remove its old self from the CSE maps.
6224 RemoveNodeFromCSEMaps(User);
6226 // A user can appear in a use list multiple times, and when this
6227 // happens the uses are usually next to each other in the list.
6228 // To help reduce the number of CSE recomputations, process all
6229 // the uses of this user that we can find this way.
6231 SDUse &Use = UI.getUse();
6232 const SDValue &ToOp = To[Use.getResNo()];
6235 } while (UI != UE && *UI == User);
6237 // Now that we have modified User, add it back to the CSE maps. If it
6238 // already exists there, recursively merge the results together.
6239 AddModifiedNodeToCSEMaps(User);
6242 // If we just RAUW'd the root, take note.
6243 if (From == getRoot().getNode())
6244 setRoot(SDValue(To[getRoot().getResNo()]));
6247 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6248 /// uses of other values produced by From.getNode() alone. The Deleted
6249 /// vector is handled the same way as for ReplaceAllUsesWith.
6250 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6251 // Handle the really simple, really trivial case efficiently.
6252 if (From == To) return;
6254 // Handle the simple, trivial, case efficiently.
6255 if (From.getNode()->getNumValues() == 1) {
6256 ReplaceAllUsesWith(From, To);
6260 // Iterate over just the existing users of From. See the comments in
6261 // the ReplaceAllUsesWith above.
6262 SDNode::use_iterator UI = From.getNode()->use_begin(),
6263 UE = From.getNode()->use_end();
6264 RAUWUpdateListener Listener(*this, UI, UE);
6267 bool UserRemovedFromCSEMaps = false;
6269 // A user can appear in a use list multiple times, and when this
6270 // happens the uses are usually next to each other in the list.
6271 // To help reduce the number of CSE recomputations, process all
6272 // the uses of this user that we can find this way.
6274 SDUse &Use = UI.getUse();
6276 // Skip uses of different values from the same node.
6277 if (Use.getResNo() != From.getResNo()) {
6282 // If this node hasn't been modified yet, it's still in the CSE maps,
6283 // so remove its old self from the CSE maps.
6284 if (!UserRemovedFromCSEMaps) {
6285 RemoveNodeFromCSEMaps(User);
6286 UserRemovedFromCSEMaps = true;
6291 } while (UI != UE && *UI == User);
6293 // We are iterating over all uses of the From node, so if a use
6294 // doesn't use the specific value, no changes are made.
6295 if (!UserRemovedFromCSEMaps)
6298 // Now that we have modified User, add it back to the CSE maps. If it
6299 // already exists there, recursively merge the results together.
6300 AddModifiedNodeToCSEMaps(User);
6303 // If we just RAUW'd the root, take note.
6304 if (From == getRoot())
6309 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6310 /// to record information about a use.
6317 /// operator< - Sort Memos by User.
6318 bool operator<(const UseMemo &L, const UseMemo &R) {
6319 return (intptr_t)L.User < (intptr_t)R.User;
6323 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6324 /// uses of other values produced by From.getNode() alone. The same value
6325 /// may appear in both the From and To list. The Deleted vector is
6326 /// handled the same way as for ReplaceAllUsesWith.
6327 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6330 // Handle the simple, trivial case efficiently.
6332 return ReplaceAllUsesOfValueWith(*From, *To);
6334 // Read up all the uses and make records of them. This helps
6335 // processing new uses that are introduced during the
6336 // replacement process.
6337 SmallVector<UseMemo, 4> Uses;
6338 for (unsigned i = 0; i != Num; ++i) {
6339 unsigned FromResNo = From[i].getResNo();
6340 SDNode *FromNode = From[i].getNode();
6341 for (SDNode::use_iterator UI = FromNode->use_begin(),
6342 E = FromNode->use_end(); UI != E; ++UI) {
6343 SDUse &Use = UI.getUse();
6344 if (Use.getResNo() == FromResNo) {
6345 UseMemo Memo = { *UI, i, &Use };
6346 Uses.push_back(Memo);
6351 // Sort the uses, so that all the uses from a given User are together.
6352 std::sort(Uses.begin(), Uses.end());
6354 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6355 UseIndex != UseIndexEnd; ) {
6356 // We know that this user uses some value of From. If it is the right
6357 // value, update it.
6358 SDNode *User = Uses[UseIndex].User;
6360 // This node is about to morph, remove its old self from the CSE maps.
6361 RemoveNodeFromCSEMaps(User);
6363 // The Uses array is sorted, so all the uses for a given User
6364 // are next to each other in the list.
6365 // To help reduce the number of CSE recomputations, process all
6366 // the uses of this user that we can find this way.
6368 unsigned i = Uses[UseIndex].Index;
6369 SDUse &Use = *Uses[UseIndex].Use;
6373 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6375 // Now that we have modified User, add it back to the CSE maps. If it
6376 // already exists there, recursively merge the results together.
6377 AddModifiedNodeToCSEMaps(User);
6381 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6382 /// based on their topological order. It returns the maximum id and a vector
6383 /// of the SDNodes* in assigned order by reference.
6384 unsigned SelectionDAG::AssignTopologicalOrder() {
6386 unsigned DAGSize = 0;
6388 // SortedPos tracks the progress of the algorithm. Nodes before it are
6389 // sorted, nodes after it are unsorted. When the algorithm completes
6390 // it is at the end of the list.
6391 allnodes_iterator SortedPos = allnodes_begin();
6393 // Visit all the nodes. Move nodes with no operands to the front of
6394 // the list immediately. Annotate nodes that do have operands with their
6395 // operand count. Before we do this, the Node Id fields of the nodes
6396 // may contain arbitrary values. After, the Node Id fields for nodes
6397 // before SortedPos will contain the topological sort index, and the
6398 // Node Id fields for nodes At SortedPos and after will contain the
6399 // count of outstanding operands.
6400 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6402 checkForCycles(N, this);
6403 unsigned Degree = N->getNumOperands();
6405 // A node with no uses, add it to the result array immediately.
6406 N->setNodeId(DAGSize++);
6407 allnodes_iterator Q = N;
6409 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6410 assert(SortedPos != AllNodes.end() && "Overran node list");
6413 // Temporarily use the Node Id as scratch space for the degree count.
6414 N->setNodeId(Degree);
6418 // Visit all the nodes. As we iterate, move nodes into sorted order,
6419 // such that by the time the end is reached all nodes will be sorted.
6420 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6422 checkForCycles(N, this);
6423 // N is in sorted position, so all its uses have one less operand
6424 // that needs to be sorted.
6425 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6428 unsigned Degree = P->getNodeId();
6429 assert(Degree != 0 && "Invalid node degree");
6432 // All of P's operands are sorted, so P may sorted now.
6433 P->setNodeId(DAGSize++);
6435 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6436 assert(SortedPos != AllNodes.end() && "Overran node list");
6439 // Update P's outstanding operand count.
6440 P->setNodeId(Degree);
6443 if (I == SortedPos) {
6446 dbgs() << "Overran sorted position:\n";
6447 S->dumprFull(this); dbgs() << "\n";
6448 dbgs() << "Checking if this is due to cycles\n";
6449 checkForCycles(this, true);
6451 llvm_unreachable(nullptr);
6455 assert(SortedPos == AllNodes.end() &&
6456 "Topological sort incomplete!");
6457 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6458 "First node in topological sort is not the entry token!");
6459 assert(AllNodes.front().getNodeId() == 0 &&
6460 "First node in topological sort has non-zero id!");
6461 assert(AllNodes.front().getNumOperands() == 0 &&
6462 "First node in topological sort has operands!");
6463 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6464 "Last node in topologic sort has unexpected id!");
6465 assert(AllNodes.back().use_empty() &&
6466 "Last node in topologic sort has users!");
6467 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6471 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6472 /// value is produced by SD.
6473 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6475 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6476 SD->setHasDebugValue(true);
6478 DbgInfo->add(DB, SD, isParameter);
6481 /// TransferDbgValues - Transfer SDDbgValues.
6482 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6483 if (From == To || !From.getNode()->getHasDebugValue())
6485 SDNode *FromNode = From.getNode();
6486 SDNode *ToNode = To.getNode();
6487 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6488 SmallVector<SDDbgValue *, 2> ClonedDVs;
6489 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6491 SDDbgValue *Dbg = *I;
6492 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6494 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6495 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6496 Dbg->getDebugLoc(), Dbg->getOrder());
6497 ClonedDVs.push_back(Clone);
6500 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6501 E = ClonedDVs.end(); I != E; ++I)
6502 AddDbgValue(*I, ToNode, false);
6505 //===----------------------------------------------------------------------===//
6507 //===----------------------------------------------------------------------===//
6509 HandleSDNode::~HandleSDNode() {
6513 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6514 DebugLoc DL, const GlobalValue *GA,
6515 EVT VT, int64_t o, unsigned char TF)
6516 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6520 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6521 SDValue X, unsigned SrcAS,
6523 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6524 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6526 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6527 EVT memvt, MachineMemOperand *mmo)
6528 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6529 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6530 MMO->isNonTemporal(), MMO->isInvariant());
6531 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6532 assert(isNonTemporal() == MMO->isNonTemporal() &&
6533 "Non-temporal encoding error!");
6534 // We check here that the size of the memory operand fits within the size of
6535 // the MMO. This is because the MMO might indicate only a possible address
6536 // range instead of specifying the affected memory addresses precisely.
6537 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6540 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6541 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6542 : SDNode(Opc, Order, dl, VTs, Ops),
6543 MemoryVT(memvt), MMO(mmo) {
6544 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6545 MMO->isNonTemporal(), MMO->isInvariant());
6546 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6547 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6550 /// Profile - Gather unique data for the node.
6552 void SDNode::Profile(FoldingSetNodeID &ID) const {
6553 AddNodeIDNode(ID, this);
6558 std::vector<EVT> VTs;
6561 VTs.reserve(MVT::LAST_VALUETYPE);
6562 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6563 VTs.push_back(MVT((MVT::SimpleValueType)i));
6568 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6569 static ManagedStatic<EVTArray> SimpleVTArray;
6570 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6572 /// getValueTypeList - Return a pointer to the specified value type.
6574 const EVT *SDNode::getValueTypeList(EVT VT) {
6575 if (VT.isExtended()) {
6576 sys::SmartScopedLock<true> Lock(*VTMutex);
6577 return &(*EVTs->insert(VT).first);
6579 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6580 "Value type out of range!");
6581 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6585 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6586 /// indicated value. This method ignores uses of other values defined by this
6588 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6589 assert(Value < getNumValues() && "Bad value!");
6591 // TODO: Only iterate over uses of a given value of the node
6592 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6593 if (UI.getUse().getResNo() == Value) {
6600 // Found exactly the right number of uses?
6605 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6606 /// value. This method ignores uses of other values defined by this operation.
6607 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6608 assert(Value < getNumValues() && "Bad value!");
6610 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6611 if (UI.getUse().getResNo() == Value)
6618 /// isOnlyUserOf - Return true if this node is the only use of N.
6620 bool SDNode::isOnlyUserOf(SDNode *N) const {
6622 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6633 /// isOperand - Return true if this node is an operand of N.
6635 bool SDValue::isOperandOf(SDNode *N) const {
6636 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6637 if (*this == N->getOperand(i))
6642 bool SDNode::isOperandOf(SDNode *N) const {
6643 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6644 if (this == N->OperandList[i].getNode())
6649 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6650 /// be a chain) reaches the specified operand without crossing any
6651 /// side-effecting instructions on any chain path. In practice, this looks
6652 /// through token factors and non-volatile loads. In order to remain efficient,
6653 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6654 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6655 unsigned Depth) const {
6656 if (*this == Dest) return true;
6658 // Don't search too deeply, we just want to be able to see through
6659 // TokenFactor's etc.
6660 if (Depth == 0) return false;
6662 // If this is a token factor, all inputs to the TF happen in parallel. If any
6663 // of the operands of the TF does not reach dest, then we cannot do the xform.
6664 if (getOpcode() == ISD::TokenFactor) {
6665 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6666 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6671 // Loads don't have side effects, look through them.
6672 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6673 if (!Ld->isVolatile())
6674 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6679 /// hasPredecessor - Return true if N is a predecessor of this node.
6680 /// N is either an operand of this node, or can be reached by recursively
6681 /// traversing up the operands.
6682 /// NOTE: This is an expensive method. Use it carefully.
6683 bool SDNode::hasPredecessor(const SDNode *N) const {
6684 SmallPtrSet<const SDNode *, 32> Visited;
6685 SmallVector<const SDNode *, 16> Worklist;
6686 return hasPredecessorHelper(N, Visited, Worklist);
6690 SDNode::hasPredecessorHelper(const SDNode *N,
6691 SmallPtrSetImpl<const SDNode *> &Visited,
6692 SmallVectorImpl<const SDNode *> &Worklist) const {
6693 if (Visited.empty()) {
6694 Worklist.push_back(this);
6696 // Take a look in the visited set. If we've already encountered this node
6697 // we needn't search further.
6698 if (Visited.count(N))
6702 // Haven't visited N yet. Continue the search.
6703 while (!Worklist.empty()) {
6704 const SDNode *M = Worklist.pop_back_val();
6705 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6706 SDNode *Op = M->getOperand(i).getNode();
6707 if (Visited.insert(Op).second)
6708 Worklist.push_back(Op);
6717 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6718 assert(Num < NumOperands && "Invalid child # of SDNode!");
6719 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6722 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6723 assert(N->getNumValues() == 1 &&
6724 "Can't unroll a vector with multiple results!");
6726 EVT VT = N->getValueType(0);
6727 unsigned NE = VT.getVectorNumElements();
6728 EVT EltVT = VT.getVectorElementType();
6731 SmallVector<SDValue, 8> Scalars;
6732 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6734 // If ResNE is 0, fully unroll the vector op.
6737 else if (NE > ResNE)
6741 for (i= 0; i != NE; ++i) {
6742 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6743 SDValue Operand = N->getOperand(j);
6744 EVT OperandVT = Operand.getValueType();
6745 if (OperandVT.isVector()) {
6746 // A vector operand; extract a single element.
6747 EVT OperandEltVT = OperandVT.getVectorElementType();
6748 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6751 getConstant(i, dl, TLI->getVectorIdxTy()));
6753 // A scalar operand; just use it as is.
6754 Operands[j] = Operand;
6758 switch (N->getOpcode()) {
6760 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6763 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6770 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6771 getShiftAmountOperand(Operands[0].getValueType(),
6774 case ISD::SIGN_EXTEND_INREG:
6775 case ISD::FP_ROUND_INREG: {
6776 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6777 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6779 getValueType(ExtVT)));
6784 for (; i < ResNE; ++i)
6785 Scalars.push_back(getUNDEF(EltVT));
6787 return getNode(ISD::BUILD_VECTOR, dl,
6788 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6792 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6793 /// location that is 'Dist' units away from the location that the 'Base' load
6794 /// is loading from.
6795 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6796 unsigned Bytes, int Dist) const {
6797 if (LD->getChain() != Base->getChain())
6799 EVT VT = LD->getValueType(0);
6800 if (VT.getSizeInBits() / 8 != Bytes)
6803 SDValue Loc = LD->getOperand(1);
6804 SDValue BaseLoc = Base->getOperand(1);
6805 if (Loc.getOpcode() == ISD::FrameIndex) {
6806 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6808 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6809 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6810 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6811 int FS = MFI->getObjectSize(FI);
6812 int BFS = MFI->getObjectSize(BFI);
6813 if (FS != BFS || FS != (int)Bytes) return false;
6814 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6818 if (isBaseWithConstantOffset(Loc)) {
6819 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6820 if (Loc.getOperand(0) == BaseLoc) {
6821 // If the base location is a simple address with no offset itself, then
6822 // the second load's first add operand should be the base address.
6823 if (LocOffset == Dist * (int)Bytes)
6825 } else if (isBaseWithConstantOffset(BaseLoc)) {
6826 // The base location itself has an offset, so subtract that value from the
6827 // second load's offset before comparing to distance * size.
6829 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6830 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6831 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6836 const GlobalValue *GV1 = nullptr;
6837 const GlobalValue *GV2 = nullptr;
6838 int64_t Offset1 = 0;
6839 int64_t Offset2 = 0;
6840 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6841 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6842 if (isGA1 && isGA2 && GV1 == GV2)
6843 return Offset1 == (Offset2 + Dist*Bytes);
6848 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6849 /// it cannot be inferred.
6850 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6851 // If this is a GlobalAddress + cst, return the alignment.
6852 const GlobalValue *GV;
6853 int64_t GVOffset = 0;
6854 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6855 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6856 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6857 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6858 *TLI->getDataLayout());
6859 unsigned AlignBits = KnownZero.countTrailingOnes();
6860 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6862 return MinAlign(Align, GVOffset);
6865 // If this is a direct reference to a stack slot, use information about the
6866 // stack slot's alignment.
6867 int FrameIdx = 1 << 31;
6868 int64_t FrameOffset = 0;
6869 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6870 FrameIdx = FI->getIndex();
6871 } else if (isBaseWithConstantOffset(Ptr) &&
6872 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6874 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6875 FrameOffset = Ptr.getConstantOperandVal(1);
6878 if (FrameIdx != (1 << 31)) {
6879 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6880 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6888 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6889 /// which is split (or expanded) into two not necessarily identical pieces.
6890 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6891 // Currently all types are split in half.
6893 if (!VT.isVector()) {
6894 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6896 unsigned NumElements = VT.getVectorNumElements();
6897 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6898 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6901 return std::make_pair(LoVT, HiVT);
6904 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6906 std::pair<SDValue, SDValue>
6907 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6909 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6910 N.getValueType().getVectorNumElements() &&
6911 "More vector elements requested than available!");
6913 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6914 getConstant(0, DL, TLI->getVectorIdxTy()));
6915 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6916 getConstant(LoVT.getVectorNumElements(), DL,
6917 TLI->getVectorIdxTy()));
6918 return std::make_pair(Lo, Hi);
6921 void SelectionDAG::ExtractVectorElements(SDValue Op,
6922 SmallVectorImpl<SDValue> &Args,
6923 unsigned Start, unsigned Count) {
6924 EVT VT = Op.getValueType();
6926 Count = VT.getVectorNumElements();
6928 EVT EltVT = VT.getVectorElementType();
6929 EVT IdxTy = TLI->getVectorIdxTy();
6931 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6932 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6933 Op, getConstant(i, SL, IdxTy)));
6937 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6938 unsigned GlobalAddressSDNode::getAddressSpace() const {
6939 return getGlobal()->getType()->getAddressSpace();
6943 Type *ConstantPoolSDNode::getType() const {
6944 if (isMachineConstantPoolEntry())
6945 return Val.MachineCPVal->getType();
6946 return Val.ConstVal->getType();
6949 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6951 unsigned &SplatBitSize,
6953 unsigned MinSplatBits,
6954 bool isBigEndian) const {
6955 EVT VT = getValueType(0);
6956 assert(VT.isVector() && "Expected a vector type");
6957 unsigned sz = VT.getSizeInBits();
6958 if (MinSplatBits > sz)
6961 SplatValue = APInt(sz, 0);
6962 SplatUndef = APInt(sz, 0);
6964 // Get the bits. Bits with undefined values (when the corresponding element
6965 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6966 // in SplatValue. If any of the values are not constant, give up and return
6968 unsigned int nOps = getNumOperands();
6969 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6970 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6972 for (unsigned j = 0; j < nOps; ++j) {
6973 unsigned i = isBigEndian ? nOps-1-j : j;
6974 SDValue OpVal = getOperand(i);
6975 unsigned BitPos = j * EltBitSize;
6977 if (OpVal.getOpcode() == ISD::UNDEF)
6978 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6979 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6980 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6981 zextOrTrunc(sz) << BitPos;
6982 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6983 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6988 // The build_vector is all constants or undefs. Find the smallest element
6989 // size that splats the vector.
6991 HasAnyUndefs = (SplatUndef != 0);
6994 unsigned HalfSize = sz / 2;
6995 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6996 APInt LowValue = SplatValue.trunc(HalfSize);
6997 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6998 APInt LowUndef = SplatUndef.trunc(HalfSize);
7000 // If the two halves do not match (ignoring undef bits), stop here.
7001 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7002 MinSplatBits > HalfSize)
7005 SplatValue = HighValue | LowValue;
7006 SplatUndef = HighUndef & LowUndef;
7015 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7016 if (UndefElements) {
7017 UndefElements->clear();
7018 UndefElements->resize(getNumOperands());
7021 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7022 SDValue Op = getOperand(i);
7023 if (Op.getOpcode() == ISD::UNDEF) {
7025 (*UndefElements)[i] = true;
7026 } else if (!Splatted) {
7028 } else if (Splatted != Op) {
7034 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7035 "Can only have a splat without a constant for all undefs.");
7036 return getOperand(0);
7043 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7044 return dyn_cast_or_null<ConstantSDNode>(
7045 getSplatValue(UndefElements).getNode());
7049 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7050 return dyn_cast_or_null<ConstantFPSDNode>(
7051 getSplatValue(UndefElements).getNode());
7054 bool BuildVectorSDNode::isConstant() const {
7055 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7056 unsigned Opc = getOperand(i).getOpcode();
7057 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7063 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7064 // Find the first non-undef value in the shuffle mask.
7066 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7069 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7071 // Make sure all remaining elements are either undef or the same as the first
7073 for (int Idx = Mask[i]; i != e; ++i)
7074 if (Mask[i] >= 0 && Mask[i] != Idx)
7080 static void checkForCyclesHelper(const SDNode *N,
7081 SmallPtrSetImpl<const SDNode*> &Visited,
7082 SmallPtrSetImpl<const SDNode*> &Checked,
7083 const llvm::SelectionDAG *DAG) {
7084 // If this node has already been checked, don't check it again.
7085 if (Checked.count(N))
7088 // If a node has already been visited on this depth-first walk, reject it as
7090 if (!Visited.insert(N).second) {
7091 errs() << "Detected cycle in SelectionDAG\n";
7092 dbgs() << "Offending node:\n";
7093 N->dumprFull(DAG); dbgs() << "\n";
7097 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7098 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7105 void llvm::checkForCycles(const llvm::SDNode *N,
7106 const llvm::SelectionDAG *DAG,
7114 assert(N && "Checking nonexistent SDNode");
7115 SmallPtrSet<const SDNode*, 32> visited;
7116 SmallPtrSet<const SDNode*, 32> checked;
7117 checkForCyclesHelper(N, visited, checked, DAG);
7122 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7123 checkForCycles(DAG->getRoot().getNode(), DAG, force);