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);
2439 APInt Op0Zero, Op0One;
2440 APInt Op1Zero, Op1One;
2441 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2442 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2444 KnownZero = Op0Zero & Op1Zero;
2445 KnownOne = Op0One & Op1One;
2448 case ISD::FrameIndex:
2449 case ISD::TargetFrameIndex:
2450 if (unsigned Align = InferPtrAlignment(Op)) {
2451 // The low bits are known zero if the pointer is aligned.
2452 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2458 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2461 case ISD::INTRINSIC_WO_CHAIN:
2462 case ISD::INTRINSIC_W_CHAIN:
2463 case ISD::INTRINSIC_VOID:
2464 // Allow the target to implement this method for its nodes.
2465 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2469 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2472 /// ComputeNumSignBits - Return the number of times the sign bit of the
2473 /// register is replicated into the other bits. We know that at least 1 bit
2474 /// is always equal to the sign bit (itself), but other cases can give us
2475 /// information. For example, immediately after an "SRA X, 2", we know that
2476 /// the top 3 bits are all equal to each other, so we return 3.
2477 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2478 EVT VT = Op.getValueType();
2479 assert(VT.isInteger() && "Invalid VT!");
2480 unsigned VTBits = VT.getScalarType().getSizeInBits();
2482 unsigned FirstAnswer = 1;
2485 return 1; // Limit search depth.
2487 switch (Op.getOpcode()) {
2489 case ISD::AssertSext:
2490 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2491 return VTBits-Tmp+1;
2492 case ISD::AssertZext:
2493 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2496 case ISD::Constant: {
2497 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2498 return Val.getNumSignBits();
2501 case ISD::SIGN_EXTEND:
2503 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2504 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2506 case ISD::SIGN_EXTEND_INREG:
2507 // Max of the input and what this extends.
2509 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2512 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2513 return std::max(Tmp, Tmp2);
2516 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2517 // SRA X, C -> adds C sign bits.
2518 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2519 Tmp += C->getZExtValue();
2520 if (Tmp > VTBits) Tmp = VTBits;
2524 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2525 // shl destroys sign bits.
2526 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2527 if (C->getZExtValue() >= VTBits || // Bad shift.
2528 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2529 return Tmp - C->getZExtValue();
2534 case ISD::XOR: // NOT is handled here.
2535 // Logical binary ops preserve the number of sign bits at the worst.
2536 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2538 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2539 FirstAnswer = std::min(Tmp, Tmp2);
2540 // We computed what we know about the sign bits as our first
2541 // answer. Now proceed to the generic code that uses
2542 // computeKnownBits, and pick whichever answer is better.
2547 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2548 if (Tmp == 1) return 1; // Early out.
2549 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2550 return std::min(Tmp, Tmp2);
2555 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2557 return 1; // Early out.
2558 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2559 return std::min(Tmp, Tmp2);
2566 if (Op.getResNo() != 1)
2568 // The boolean result conforms to getBooleanContents. Fall through.
2569 // If setcc returns 0/-1, all bits are sign bits.
2570 // We know that we have an integer-based boolean since these operations
2571 // are only available for integer.
2572 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2573 TargetLowering::ZeroOrNegativeOneBooleanContent)
2577 // If setcc returns 0/-1, all bits are sign bits.
2578 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2579 TargetLowering::ZeroOrNegativeOneBooleanContent)
2584 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2585 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2587 // Handle rotate right by N like a rotate left by 32-N.
2588 if (Op.getOpcode() == ISD::ROTR)
2589 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2591 // If we aren't rotating out all of the known-in sign bits, return the
2592 // number that are left. This handles rotl(sext(x), 1) for example.
2593 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2594 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2598 // Add can have at most one carry bit. Thus we know that the output
2599 // is, at worst, one more bit than the inputs.
2600 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2601 if (Tmp == 1) return 1; // Early out.
2603 // Special case decrementing a value (ADD X, -1):
2604 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2605 if (CRHS->isAllOnesValue()) {
2606 APInt KnownZero, KnownOne;
2607 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2609 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2611 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2614 // If we are subtracting one from a positive number, there is no carry
2615 // out of the result.
2616 if (KnownZero.isNegative())
2620 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2621 if (Tmp2 == 1) return 1;
2622 return std::min(Tmp, Tmp2)-1;
2625 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2626 if (Tmp2 == 1) return 1;
2629 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2630 if (CLHS->isNullValue()) {
2631 APInt KnownZero, KnownOne;
2632 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2633 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2635 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2638 // If the input is known to be positive (the sign bit is known clear),
2639 // the output of the NEG has the same number of sign bits as the input.
2640 if (KnownZero.isNegative())
2643 // Otherwise, we treat this like a SUB.
2646 // Sub can have at most one carry bit. Thus we know that the output
2647 // is, at worst, one more bit than the inputs.
2648 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2649 if (Tmp == 1) return 1; // Early out.
2650 return std::min(Tmp, Tmp2)-1;
2652 // FIXME: it's tricky to do anything useful for this, but it is an important
2653 // case for targets like X86.
2655 case ISD::EXTRACT_ELEMENT: {
2656 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2657 const int BitWidth = Op.getValueType().getSizeInBits();
2659 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2661 // Get reverse index (starting from 1), Op1 value indexes elements from
2662 // little end. Sign starts at big end.
2663 const int rIndex = Items - 1 -
2664 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2666 // If the sign portion ends in our element the substraction gives correct
2667 // result. Otherwise it gives either negative or > bitwidth result
2668 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2672 // If we are looking at the loaded value of the SDNode.
2673 if (Op.getResNo() == 0) {
2674 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2675 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2676 unsigned ExtType = LD->getExtensionType();
2679 case ISD::SEXTLOAD: // '17' bits known
2680 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2681 return VTBits-Tmp+1;
2682 case ISD::ZEXTLOAD: // '16' bits known
2683 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2689 // Allow the target to implement this method for its nodes.
2690 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2691 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2692 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2693 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2694 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2695 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2698 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2699 // use this information.
2700 APInt KnownZero, KnownOne;
2701 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2704 if (KnownZero.isNegative()) { // sign bit is 0
2706 } else if (KnownOne.isNegative()) { // sign bit is 1;
2713 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2714 // the number of identical bits in the top of the input value.
2716 Mask <<= Mask.getBitWidth()-VTBits;
2717 // Return # leading zeros. We use 'min' here in case Val was zero before
2718 // shifting. We don't want to return '64' as for an i32 "0".
2719 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2722 /// isBaseWithConstantOffset - Return true if the specified operand is an
2723 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2724 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2725 /// semantics as an ADD. This handles the equivalence:
2726 /// X|Cst == X+Cst iff X&Cst = 0.
2727 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2728 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2729 !isa<ConstantSDNode>(Op.getOperand(1)))
2732 if (Op.getOpcode() == ISD::OR &&
2733 !MaskedValueIsZero(Op.getOperand(0),
2734 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2741 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2742 // If we're told that NaNs won't happen, assume they won't.
2743 if (getTarget().Options.NoNaNsFPMath)
2746 // If the value is a constant, we can obviously see if it is a NaN or not.
2747 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2748 return !C->getValueAPF().isNaN();
2750 // TODO: Recognize more cases here.
2755 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2756 // If the value is a constant, we can obviously see if it is a zero or not.
2757 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2758 return !C->isZero();
2760 // TODO: Recognize more cases here.
2761 switch (Op.getOpcode()) {
2764 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2765 return !C->isNullValue();
2772 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2773 // Check the obvious case.
2774 if (A == B) return true;
2776 // For for negative and positive zero.
2777 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2778 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2779 if (CA->isZero() && CB->isZero()) return true;
2781 // Otherwise they may not be equal.
2785 /// getNode - Gets or creates the specified node.
2787 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2788 FoldingSetNodeID ID;
2789 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2791 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2792 return SDValue(E, 0);
2794 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2795 DL.getDebugLoc(), getVTList(VT));
2796 CSEMap.InsertNode(N, IP);
2799 return SDValue(N, 0);
2802 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2803 EVT VT, SDValue Operand) {
2804 // Constant fold unary operations with an integer constant operand. Even
2805 // opaque constant will be folded, because the folding of unary operations
2806 // doesn't create new constants with different values. Nevertheless, the
2807 // opaque flag is preserved during folding to prevent future folding with
2809 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2810 const APInt &Val = C->getAPIntValue();
2813 case ISD::SIGN_EXTEND:
2814 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2815 C->isTargetOpcode(), C->isOpaque());
2816 case ISD::ANY_EXTEND:
2817 case ISD::ZERO_EXTEND:
2819 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2820 C->isTargetOpcode(), C->isOpaque());
2821 case ISD::UINT_TO_FP:
2822 case ISD::SINT_TO_FP: {
2823 APFloat apf(EVTToAPFloatSemantics(VT),
2824 APInt::getNullValue(VT.getSizeInBits()));
2825 (void)apf.convertFromAPInt(Val,
2826 Opcode==ISD::SINT_TO_FP,
2827 APFloat::rmNearestTiesToEven);
2828 return getConstantFP(apf, DL, VT);
2831 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2832 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2833 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2834 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2835 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2836 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2839 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2842 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2845 case ISD::CTLZ_ZERO_UNDEF:
2846 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2849 case ISD::CTTZ_ZERO_UNDEF:
2850 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2855 // Constant fold unary operations with a floating point constant operand.
2856 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2857 APFloat V = C->getValueAPF(); // make copy
2861 return getConstantFP(V, DL, VT);
2864 return getConstantFP(V, DL, VT);
2866 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2867 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2868 return getConstantFP(V, DL, VT);
2872 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2873 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2874 return getConstantFP(V, DL, VT);
2878 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2879 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2880 return getConstantFP(V, DL, VT);
2883 case ISD::FP_EXTEND: {
2885 // This can return overflow, underflow, or inexact; we don't care.
2886 // FIXME need to be more flexible about rounding mode.
2887 (void)V.convert(EVTToAPFloatSemantics(VT),
2888 APFloat::rmNearestTiesToEven, &ignored);
2889 return getConstantFP(V, DL, VT);
2891 case ISD::FP_TO_SINT:
2892 case ISD::FP_TO_UINT: {
2895 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2896 // FIXME need to be more flexible about rounding mode.
2897 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2898 Opcode==ISD::FP_TO_SINT,
2899 APFloat::rmTowardZero, &ignored);
2900 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2902 APInt api(VT.getSizeInBits(), x);
2903 return getConstant(api, DL, VT);
2906 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2907 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2908 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2909 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2910 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2911 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2916 // Constant fold unary operations with a vector integer or float operand.
2917 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2918 if (BV->isConstant()) {
2921 // FIXME: Entirely reasonable to perform folding of other unary
2922 // operations here as the need arises.
2929 case ISD::FP_EXTEND:
2930 case ISD::FP_TO_SINT:
2931 case ISD::FP_TO_UINT:
2933 case ISD::UINT_TO_FP:
2934 case ISD::SINT_TO_FP:
2936 case ISD::CTLZ_ZERO_UNDEF:
2938 case ISD::CTTZ_ZERO_UNDEF:
2940 EVT SVT = VT.getScalarType();
2941 EVT InVT = BV->getValueType(0);
2942 EVT InSVT = InVT.getScalarType();
2944 // Find legal integer scalar type for constant promotion and
2945 // ensure that its scalar size is at least as large as source.
2947 if (SVT.isInteger()) {
2948 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2949 if (LegalSVT.bitsLT(SVT)) break;
2952 // Let the above scalar folding handle the folding of each element.
2953 SmallVector<SDValue, 8> Ops;
2954 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2955 SDValue OpN = BV->getOperand(i);
2956 EVT OpVT = OpN.getValueType();
2958 // Build vector (integer) scalar operands may need implicit
2959 // truncation - do this before constant folding.
2960 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2961 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2963 OpN = getNode(Opcode, DL, SVT, OpN);
2965 // Legalize the (integer) scalar constant if necessary.
2966 if (LegalSVT != SVT)
2967 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2969 if (OpN.getOpcode() != ISD::UNDEF &&
2970 OpN.getOpcode() != ISD::Constant &&
2971 OpN.getOpcode() != ISD::ConstantFP)
2975 if (Ops.size() == VT.getVectorNumElements())
2976 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2983 unsigned OpOpcode = Operand.getNode()->getOpcode();
2985 case ISD::TokenFactor:
2986 case ISD::MERGE_VALUES:
2987 case ISD::CONCAT_VECTORS:
2988 return Operand; // Factor, merge or concat of one node? No need.
2989 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2990 case ISD::FP_EXTEND:
2991 assert(VT.isFloatingPoint() &&
2992 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2993 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2994 assert((!VT.isVector() ||
2995 VT.getVectorNumElements() ==
2996 Operand.getValueType().getVectorNumElements()) &&
2997 "Vector element count mismatch!");
2998 if (Operand.getOpcode() == ISD::UNDEF)
2999 return getUNDEF(VT);
3001 case ISD::SIGN_EXTEND:
3002 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3003 "Invalid SIGN_EXTEND!");
3004 if (Operand.getValueType() == VT) return Operand; // noop extension
3005 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3006 "Invalid sext node, dst < src!");
3007 assert((!VT.isVector() ||
3008 VT.getVectorNumElements() ==
3009 Operand.getValueType().getVectorNumElements()) &&
3010 "Vector element count mismatch!");
3011 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3012 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3013 else if (OpOpcode == ISD::UNDEF)
3014 // sext(undef) = 0, because the top bits will all be the same.
3015 return getConstant(0, DL, VT);
3017 case ISD::ZERO_EXTEND:
3018 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3019 "Invalid ZERO_EXTEND!");
3020 if (Operand.getValueType() == VT) return Operand; // noop extension
3021 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3022 "Invalid zext node, dst < src!");
3023 assert((!VT.isVector() ||
3024 VT.getVectorNumElements() ==
3025 Operand.getValueType().getVectorNumElements()) &&
3026 "Vector element count mismatch!");
3027 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3028 return getNode(ISD::ZERO_EXTEND, DL, VT,
3029 Operand.getNode()->getOperand(0));
3030 else if (OpOpcode == ISD::UNDEF)
3031 // zext(undef) = 0, because the top bits will be zero.
3032 return getConstant(0, DL, VT);
3034 case ISD::ANY_EXTEND:
3035 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3036 "Invalid ANY_EXTEND!");
3037 if (Operand.getValueType() == VT) return Operand; // noop extension
3038 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3039 "Invalid anyext node, dst < src!");
3040 assert((!VT.isVector() ||
3041 VT.getVectorNumElements() ==
3042 Operand.getValueType().getVectorNumElements()) &&
3043 "Vector element count mismatch!");
3045 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3046 OpOpcode == ISD::ANY_EXTEND)
3047 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3048 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3049 else if (OpOpcode == ISD::UNDEF)
3050 return getUNDEF(VT);
3052 // (ext (trunx x)) -> x
3053 if (OpOpcode == ISD::TRUNCATE) {
3054 SDValue OpOp = Operand.getNode()->getOperand(0);
3055 if (OpOp.getValueType() == VT)
3060 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3061 "Invalid TRUNCATE!");
3062 if (Operand.getValueType() == VT) return Operand; // noop truncate
3063 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3064 "Invalid truncate node, src < dst!");
3065 assert((!VT.isVector() ||
3066 VT.getVectorNumElements() ==
3067 Operand.getValueType().getVectorNumElements()) &&
3068 "Vector element count mismatch!");
3069 if (OpOpcode == ISD::TRUNCATE)
3070 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3071 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3072 OpOpcode == ISD::ANY_EXTEND) {
3073 // If the source is smaller than the dest, we still need an extend.
3074 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3075 .bitsLT(VT.getScalarType()))
3076 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3077 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3078 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3079 return Operand.getNode()->getOperand(0);
3081 if (OpOpcode == ISD::UNDEF)
3082 return getUNDEF(VT);
3085 // Basic sanity checking.
3086 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3087 && "Cannot BITCAST between types of different sizes!");
3088 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3089 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3090 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3091 if (OpOpcode == ISD::UNDEF)
3092 return getUNDEF(VT);
3094 case ISD::SCALAR_TO_VECTOR:
3095 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3096 (VT.getVectorElementType() == Operand.getValueType() ||
3097 (VT.getVectorElementType().isInteger() &&
3098 Operand.getValueType().isInteger() &&
3099 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3100 "Illegal SCALAR_TO_VECTOR node!");
3101 if (OpOpcode == ISD::UNDEF)
3102 return getUNDEF(VT);
3103 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3104 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3105 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3106 Operand.getConstantOperandVal(1) == 0 &&
3107 Operand.getOperand(0).getValueType() == VT)
3108 return Operand.getOperand(0);
3111 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3112 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3113 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3114 Operand.getNode()->getOperand(0));
3115 if (OpOpcode == ISD::FNEG) // --X -> X
3116 return Operand.getNode()->getOperand(0);
3119 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3120 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3125 SDVTList VTs = getVTList(VT);
3126 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3127 FoldingSetNodeID ID;
3128 SDValue Ops[1] = { Operand };
3129 AddNodeIDNode(ID, Opcode, VTs, Ops);
3131 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3132 return SDValue(E, 0);
3134 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3135 DL.getDebugLoc(), VTs, Operand);
3136 CSEMap.InsertNode(N, IP);
3138 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3139 DL.getDebugLoc(), VTs, Operand);
3143 return SDValue(N, 0);
3146 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3149 case ISD::ADD: return std::make_pair(C1 + C2, true);
3150 case ISD::SUB: return std::make_pair(C1 - C2, true);
3151 case ISD::MUL: return std::make_pair(C1 * C2, true);
3152 case ISD::AND: return std::make_pair(C1 & C2, true);
3153 case ISD::OR: return std::make_pair(C1 | C2, true);
3154 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3155 case ISD::SHL: return std::make_pair(C1 << C2, true);
3156 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3157 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3158 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3159 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3161 if (!C2.getBoolValue())
3163 return std::make_pair(C1.udiv(C2), true);
3165 if (!C2.getBoolValue())
3167 return std::make_pair(C1.urem(C2), true);
3169 if (!C2.getBoolValue())
3171 return std::make_pair(C1.sdiv(C2), true);
3173 if (!C2.getBoolValue())
3175 return std::make_pair(C1.srem(C2), true);
3177 return std::make_pair(APInt(1, 0), false);
3180 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3181 const ConstantSDNode *Cst1,
3182 const ConstantSDNode *Cst2) {
3183 if (Cst1->isOpaque() || Cst2->isOpaque())
3186 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3187 Cst2->getAPIntValue());
3190 return getConstant(Folded.first, DL, VT);
3193 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3194 SDNode *Cst1, SDNode *Cst2) {
3195 // If the opcode is a target-specific ISD node, there's nothing we can
3196 // do here and the operand rules may not line up with the below, so
3198 if (Opcode >= ISD::BUILTIN_OP_END)
3201 // Handle the case of two scalars.
3202 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3203 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3204 if (SDValue Folded =
3205 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3208 SmallVector<SDValue, 4> Outputs;
3209 // We may have a vector type but a scalar result. Create a splat.
3210 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3211 // Build a big vector out of the scalar elements we generated.
3212 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3219 // For vectors extract each constant element into Inputs so we can constant
3220 // fold them individually.
3221 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3222 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3226 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3228 EVT SVT = VT.getScalarType();
3229 SmallVector<SDValue, 4> Outputs;
3230 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3231 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3232 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3233 if (!V1 || !V2) // Not a constant, bail.
3236 if (V1->isOpaque() || V2->isOpaque())
3239 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3240 // FIXME: This is valid and could be handled by truncating the APInts.
3241 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3244 // Fold one vector element.
3245 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3246 V2->getAPIntValue());
3249 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3252 assert(VT.getVectorNumElements() == Outputs.size() &&
3253 "Vector size mismatch!");
3255 // We may have a vector type but a scalar result. Create a splat.
3256 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3258 // Build a big vector out of the scalar elements we generated.
3259 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3262 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3263 SDValue N2, bool nuw, bool nsw, bool exact) {
3264 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3265 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3268 case ISD::TokenFactor:
3269 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3270 N2.getValueType() == MVT::Other && "Invalid token factor!");
3271 // Fold trivial token factors.
3272 if (N1.getOpcode() == ISD::EntryToken) return N2;
3273 if (N2.getOpcode() == ISD::EntryToken) return N1;
3274 if (N1 == N2) return N1;
3276 case ISD::CONCAT_VECTORS:
3277 // Concat of UNDEFs is UNDEF.
3278 if (N1.getOpcode() == ISD::UNDEF &&
3279 N2.getOpcode() == ISD::UNDEF)
3280 return getUNDEF(VT);
3282 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3283 // one big BUILD_VECTOR.
3284 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3285 N2.getOpcode() == ISD::BUILD_VECTOR) {
3286 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3287 N1.getNode()->op_end());
3288 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3290 // BUILD_VECTOR requires all inputs to be of the same type, find the
3291 // maximum type and extend them all.
3292 EVT SVT = VT.getScalarType();
3293 for (SDValue Op : Elts)
3294 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3295 if (SVT.bitsGT(VT.getScalarType()))
3296 for (SDValue &Op : Elts)
3297 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3298 ? getZExtOrTrunc(Op, DL, SVT)
3299 : getSExtOrTrunc(Op, DL, SVT);
3301 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3305 assert(VT.isInteger() && "This operator does not apply to FP types!");
3306 assert(N1.getValueType() == N2.getValueType() &&
3307 N1.getValueType() == VT && "Binary operator types must match!");
3308 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3309 // worth handling here.
3310 if (N2C && N2C->isNullValue())
3312 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3319 assert(VT.isInteger() && "This operator does not apply to FP types!");
3320 assert(N1.getValueType() == N2.getValueType() &&
3321 N1.getValueType() == VT && "Binary operator types must match!");
3322 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3323 // it's worth handling here.
3324 if (N2C && N2C->isNullValue())
3334 assert(VT.isInteger() && "This operator does not apply to FP types!");
3335 assert(N1.getValueType() == N2.getValueType() &&
3336 N1.getValueType() == VT && "Binary operator types must match!");
3343 if (getTarget().Options.UnsafeFPMath) {
3344 if (Opcode == ISD::FADD) {
3346 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3347 if (CFP->getValueAPF().isZero())
3350 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3351 if (CFP->getValueAPF().isZero())
3353 } else if (Opcode == ISD::FSUB) {
3355 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3356 if (CFP->getValueAPF().isZero())
3358 } else if (Opcode == ISD::FMUL) {
3359 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3362 // If the first operand isn't the constant, try the second
3364 CFP = dyn_cast<ConstantFPSDNode>(N2);
3371 return SDValue(CFP,0);
3373 if (CFP->isExactlyValue(1.0))
3378 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3379 assert(N1.getValueType() == N2.getValueType() &&
3380 N1.getValueType() == VT && "Binary operator types must match!");
3382 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3383 assert(N1.getValueType() == VT &&
3384 N1.getValueType().isFloatingPoint() &&
3385 N2.getValueType().isFloatingPoint() &&
3386 "Invalid FCOPYSIGN!");
3393 assert(VT == N1.getValueType() &&
3394 "Shift operators return type must be the same as their first arg");
3395 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3396 "Shifts only work on integers");
3397 assert((!VT.isVector() || VT == N2.getValueType()) &&
3398 "Vector shift amounts must be in the same as their first arg");
3399 // Verify that the shift amount VT is bit enough to hold valid shift
3400 // amounts. This catches things like trying to shift an i1024 value by an
3401 // i8, which is easy to fall into in generic code that uses
3402 // TLI.getShiftAmount().
3403 assert(N2.getValueType().getSizeInBits() >=
3404 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3405 "Invalid use of small shift amount with oversized value!");
3407 // Always fold shifts of i1 values so the code generator doesn't need to
3408 // handle them. Since we know the size of the shift has to be less than the
3409 // size of the value, the shift/rotate count is guaranteed to be zero.
3412 if (N2C && N2C->isNullValue())
3415 case ISD::FP_ROUND_INREG: {
3416 EVT EVT = cast<VTSDNode>(N2)->getVT();
3417 assert(VT == N1.getValueType() && "Not an inreg round!");
3418 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3419 "Cannot FP_ROUND_INREG integer types");
3420 assert(EVT.isVector() == VT.isVector() &&
3421 "FP_ROUND_INREG type should be vector iff the operand "
3423 assert((!EVT.isVector() ||
3424 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3425 "Vector element counts must match in FP_ROUND_INREG");
3426 assert(EVT.bitsLE(VT) && "Not rounding down!");
3428 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3432 assert(VT.isFloatingPoint() &&
3433 N1.getValueType().isFloatingPoint() &&
3434 VT.bitsLE(N1.getValueType()) &&
3435 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3436 if (N1.getValueType() == VT) return N1; // noop conversion.
3438 case ISD::AssertSext:
3439 case ISD::AssertZext: {
3440 EVT EVT = cast<VTSDNode>(N2)->getVT();
3441 assert(VT == N1.getValueType() && "Not an inreg extend!");
3442 assert(VT.isInteger() && EVT.isInteger() &&
3443 "Cannot *_EXTEND_INREG FP types");
3444 assert(!EVT.isVector() &&
3445 "AssertSExt/AssertZExt type should be the vector element type "
3446 "rather than the vector type!");
3447 assert(EVT.bitsLE(VT) && "Not extending!");
3448 if (VT == EVT) return N1; // noop assertion.
3451 case ISD::SIGN_EXTEND_INREG: {
3452 EVT EVT = cast<VTSDNode>(N2)->getVT();
3453 assert(VT == N1.getValueType() && "Not an inreg extend!");
3454 assert(VT.isInteger() && EVT.isInteger() &&
3455 "Cannot *_EXTEND_INREG FP types");
3456 assert(EVT.isVector() == VT.isVector() &&
3457 "SIGN_EXTEND_INREG type should be vector iff the operand "
3459 assert((!EVT.isVector() ||
3460 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3461 "Vector element counts must match in SIGN_EXTEND_INREG");
3462 assert(EVT.bitsLE(VT) && "Not extending!");
3463 if (EVT == VT) return N1; // Not actually extending
3465 auto SignExtendInReg = [&](APInt Val) {
3466 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3467 Val <<= Val.getBitWidth() - FromBits;
3468 Val = Val.ashr(Val.getBitWidth() - FromBits);
3469 return getConstant(Val, DL, VT.getScalarType());
3473 APInt Val = N1C->getAPIntValue();
3474 return SignExtendInReg(Val);
3476 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3477 SmallVector<SDValue, 8> Ops;
3478 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3479 SDValue Op = N1.getOperand(i);
3480 if (Op.getValueType() != VT.getScalarType()) break;
3481 if (Op.getOpcode() == ISD::UNDEF) {
3485 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3486 APInt Val = C->getAPIntValue();
3487 Ops.push_back(SignExtendInReg(Val));
3492 if (Ops.size() == VT.getVectorNumElements())
3493 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3497 case ISD::EXTRACT_VECTOR_ELT:
3498 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3499 if (N1.getOpcode() == ISD::UNDEF)
3500 return getUNDEF(VT);
3502 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3503 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3504 return getUNDEF(VT);
3506 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3507 // expanding copies of large vectors from registers.
3509 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3510 N1.getNumOperands() > 0) {
3512 N1.getOperand(0).getValueType().getVectorNumElements();
3513 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3514 N1.getOperand(N2C->getZExtValue() / Factor),
3515 getConstant(N2C->getZExtValue() % Factor, DL,
3516 N2.getValueType()));
3519 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3520 // expanding large vector constants.
3521 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3522 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3524 if (VT != Elt.getValueType())
3525 // If the vector element type is not legal, the BUILD_VECTOR operands
3526 // are promoted and implicitly truncated, and the result implicitly
3527 // extended. Make that explicit here.
3528 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3533 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3534 // operations are lowered to scalars.
3535 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3536 // If the indices are the same, return the inserted element else
3537 // if the indices are known different, extract the element from
3538 // the original vector.
3539 SDValue N1Op2 = N1.getOperand(2);
3540 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3542 if (N1Op2C && N2C) {
3543 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3544 if (VT == N1.getOperand(1).getValueType())
3545 return N1.getOperand(1);
3547 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3550 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3554 case ISD::EXTRACT_ELEMENT:
3555 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3556 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3557 (N1.getValueType().isInteger() == VT.isInteger()) &&
3558 N1.getValueType() != VT &&
3559 "Wrong types for EXTRACT_ELEMENT!");
3561 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3562 // 64-bit integers into 32-bit parts. Instead of building the extract of
3563 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3564 if (N1.getOpcode() == ISD::BUILD_PAIR)
3565 return N1.getOperand(N2C->getZExtValue());
3567 // EXTRACT_ELEMENT of a constant int is also very common.
3568 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3569 unsigned ElementSize = VT.getSizeInBits();
3570 unsigned Shift = ElementSize * N2C->getZExtValue();
3571 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3572 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3575 case ISD::EXTRACT_SUBVECTOR: {
3577 if (VT.isSimple() && N1.getValueType().isSimple()) {
3578 assert(VT.isVector() && N1.getValueType().isVector() &&
3579 "Extract subvector VTs must be a vectors!");
3580 assert(VT.getVectorElementType() ==
3581 N1.getValueType().getVectorElementType() &&
3582 "Extract subvector VTs must have the same element type!");
3583 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3584 "Extract subvector must be from larger vector to smaller vector!");
3586 if (isa<ConstantSDNode>(Index.getNode())) {
3587 assert((VT.getVectorNumElements() +
3588 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3589 <= N1.getValueType().getVectorNumElements())
3590 && "Extract subvector overflow!");
3593 // Trivial extraction.
3594 if (VT.getSimpleVT() == N1.getSimpleValueType())
3601 // Perform trivial constant folding.
3603 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3606 // Canonicalize constant to RHS if commutative.
3607 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3608 std::swap(N1C, N2C);
3612 // Constant fold FP operations.
3613 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3614 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3615 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3617 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3618 // Canonicalize constant to RHS if commutative.
3619 std::swap(N1CFP, N2CFP);
3622 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3623 APFloat::opStatus s;
3626 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3627 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3628 return getConstantFP(V1, DL, VT);
3631 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3632 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3633 return getConstantFP(V1, DL, VT);
3636 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3637 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3638 return getConstantFP(V1, DL, VT);
3641 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3642 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3643 s!=APFloat::opDivByZero)) {
3644 return getConstantFP(V1, DL, VT);
3648 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3649 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3650 s!=APFloat::opDivByZero)) {
3651 return getConstantFP(V1, DL, VT);
3654 case ISD::FCOPYSIGN:
3656 return getConstantFP(V1, DL, VT);
3661 if (Opcode == ISD::FP_ROUND) {
3662 APFloat V = N1CFP->getValueAPF(); // make copy
3664 // This can return overflow, underflow, or inexact; we don't care.
3665 // FIXME need to be more flexible about rounding mode.
3666 (void)V.convert(EVTToAPFloatSemantics(VT),
3667 APFloat::rmNearestTiesToEven, &ignored);
3668 return getConstantFP(V, DL, VT);
3672 // Canonicalize an UNDEF to the RHS, even over a constant.
3673 if (N1.getOpcode() == ISD::UNDEF) {
3674 if (isCommutativeBinOp(Opcode)) {
3678 case ISD::FP_ROUND_INREG:
3679 case ISD::SIGN_EXTEND_INREG:
3685 return N1; // fold op(undef, arg2) -> undef
3693 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3694 // For vectors, we can't easily build an all zero vector, just return
3701 // Fold a bunch of operators when the RHS is undef.
3702 if (N2.getOpcode() == ISD::UNDEF) {
3705 if (N1.getOpcode() == ISD::UNDEF)
3706 // Handle undef ^ undef -> 0 special case. This is a common
3708 return getConstant(0, DL, VT);
3718 return N2; // fold op(arg1, undef) -> undef
3724 if (getTarget().Options.UnsafeFPMath)
3732 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3733 // For vectors, we can't easily build an all zero vector, just return
3738 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3739 // For vectors, we can't easily build an all one vector, just return
3747 // Memoize this node if possible.
3749 SDVTList VTs = getVTList(VT);
3750 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3751 if (VT != MVT::Glue) {
3752 SDValue Ops[] = {N1, N2};
3753 FoldingSetNodeID ID;
3754 AddNodeIDNode(ID, Opcode, VTs, Ops);
3756 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3758 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3759 return SDValue(E, 0);
3761 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3763 CSEMap.InsertNode(N, IP);
3765 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3769 return SDValue(N, 0);
3772 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3773 SDValue N1, SDValue N2, SDValue N3) {
3774 // Perform various simplifications.
3775 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3778 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3779 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3780 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3781 if (N1CFP && N2CFP && N3CFP) {
3782 APFloat V1 = N1CFP->getValueAPF();
3783 const APFloat &V2 = N2CFP->getValueAPF();
3784 const APFloat &V3 = N3CFP->getValueAPF();
3785 APFloat::opStatus s =
3786 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3787 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3788 return getConstantFP(V1, DL, VT);
3792 case ISD::CONCAT_VECTORS:
3793 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3794 // one big BUILD_VECTOR.
3795 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3796 N2.getOpcode() == ISD::BUILD_VECTOR &&
3797 N3.getOpcode() == ISD::BUILD_VECTOR) {
3798 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3799 N1.getNode()->op_end());
3800 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3801 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3802 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3806 // Use FoldSetCC to simplify SETCC's.
3807 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3808 if (Simp.getNode()) return Simp;
3813 if (N1C->getZExtValue())
3814 return N2; // select true, X, Y -> X
3815 return N3; // select false, X, Y -> Y
3818 if (N2 == N3) return N2; // select C, X, X -> X
3820 case ISD::VECTOR_SHUFFLE:
3821 llvm_unreachable("should use getVectorShuffle constructor!");
3822 case ISD::INSERT_SUBVECTOR: {
3824 if (VT.isSimple() && N1.getValueType().isSimple()
3825 && N2.getValueType().isSimple()) {
3826 assert(VT.isVector() && N1.getValueType().isVector() &&
3827 N2.getValueType().isVector() &&
3828 "Insert subvector VTs must be a vectors");
3829 assert(VT == N1.getValueType() &&
3830 "Dest and insert subvector source types must match!");
3831 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3832 "Insert subvector must be from smaller vector to larger vector!");
3833 if (isa<ConstantSDNode>(Index.getNode())) {
3834 assert((N2.getValueType().getVectorNumElements() +
3835 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3836 <= VT.getVectorNumElements())
3837 && "Insert subvector overflow!");
3840 // Trivial insertion.
3841 if (VT.getSimpleVT() == N2.getSimpleValueType())
3847 // Fold bit_convert nodes from a type to themselves.
3848 if (N1.getValueType() == VT)
3853 // Memoize node if it doesn't produce a flag.
3855 SDVTList VTs = getVTList(VT);
3856 if (VT != MVT::Glue) {
3857 SDValue Ops[] = { N1, N2, N3 };
3858 FoldingSetNodeID ID;
3859 AddNodeIDNode(ID, Opcode, VTs, Ops);
3861 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3862 return SDValue(E, 0);
3864 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3865 DL.getDebugLoc(), VTs, N1, N2, N3);
3866 CSEMap.InsertNode(N, IP);
3868 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3869 DL.getDebugLoc(), VTs, N1, N2, N3);
3873 return SDValue(N, 0);
3876 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3877 SDValue N1, SDValue N2, SDValue N3,
3879 SDValue Ops[] = { N1, N2, N3, N4 };
3880 return getNode(Opcode, DL, VT, Ops);
3883 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3884 SDValue N1, SDValue N2, SDValue N3,
3885 SDValue N4, SDValue N5) {
3886 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3887 return getNode(Opcode, DL, VT, Ops);
3890 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3891 /// the incoming stack arguments to be loaded from the stack.
3892 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3893 SmallVector<SDValue, 8> ArgChains;
3895 // Include the original chain at the beginning of the list. When this is
3896 // used by target LowerCall hooks, this helps legalize find the
3897 // CALLSEQ_BEGIN node.
3898 ArgChains.push_back(Chain);
3900 // Add a chain value for each stack argument.
3901 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3902 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3903 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3904 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3905 if (FI->getIndex() < 0)
3906 ArgChains.push_back(SDValue(L, 1));
3908 // Build a tokenfactor for all the chains.
3909 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3912 /// getMemsetValue - Vectorized representation of the memset value
3914 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3916 assert(Value.getOpcode() != ISD::UNDEF);
3918 unsigned NumBits = VT.getScalarType().getSizeInBits();
3919 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3920 assert(C->getAPIntValue().getBitWidth() == 8);
3921 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3923 return DAG.getConstant(Val, dl, VT);
3924 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3928 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3929 EVT IntVT = VT.getScalarType();
3930 if (!IntVT.isInteger())
3931 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3933 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3935 // Use a multiplication with 0x010101... to extend the input to the
3937 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3938 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3939 DAG.getConstant(Magic, dl, IntVT));
3942 if (VT != Value.getValueType() && !VT.isInteger())
3943 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3944 if (VT != Value.getValueType()) {
3945 assert(VT.getVectorElementType() == Value.getValueType() &&
3946 "value type should be one vector element here");
3947 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3948 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3954 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3955 /// used when a memcpy is turned into a memset when the source is a constant
3957 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3958 const TargetLowering &TLI, StringRef Str) {
3959 // Handle vector with all elements zero.
3962 return DAG.getConstant(0, dl, VT);
3963 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3964 return DAG.getConstantFP(0.0, dl, VT);
3965 else if (VT.isVector()) {
3966 unsigned NumElts = VT.getVectorNumElements();
3967 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3968 return DAG.getNode(ISD::BITCAST, dl, VT,
3969 DAG.getConstant(0, dl,
3970 EVT::getVectorVT(*DAG.getContext(),
3973 llvm_unreachable("Expected type!");
3976 assert(!VT.isVector() && "Can't handle vector type here!");
3977 unsigned NumVTBits = VT.getSizeInBits();
3978 unsigned NumVTBytes = NumVTBits / 8;
3979 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3981 APInt Val(NumVTBits, 0);
3982 if (TLI.isLittleEndian()) {
3983 for (unsigned i = 0; i != NumBytes; ++i)
3984 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3986 for (unsigned i = 0; i != NumBytes; ++i)
3987 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3990 // If the "cost" of materializing the integer immediate is less than the cost
3991 // of a load, then it is cost effective to turn the load into the immediate.
3992 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3993 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3994 return DAG.getConstant(Val, dl, VT);
3995 return SDValue(nullptr, 0);
3998 /// getMemBasePlusOffset - Returns base and offset node for the
4000 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4001 SelectionDAG &DAG) {
4002 EVT VT = Base.getValueType();
4003 return DAG.getNode(ISD::ADD, dl,
4004 VT, Base, DAG.getConstant(Offset, dl, VT));
4007 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4009 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4010 unsigned SrcDelta = 0;
4011 GlobalAddressSDNode *G = nullptr;
4012 if (Src.getOpcode() == ISD::GlobalAddress)
4013 G = cast<GlobalAddressSDNode>(Src);
4014 else if (Src.getOpcode() == ISD::ADD &&
4015 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4016 Src.getOperand(1).getOpcode() == ISD::Constant) {
4017 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4018 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4023 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4026 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
4027 /// to replace the memset / memcpy. Return true if the number of memory ops
4028 /// is below the threshold. It returns the types of the sequence of
4029 /// memory ops to perform memset / memcpy by reference.
4030 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4031 unsigned Limit, uint64_t Size,
4032 unsigned DstAlign, unsigned SrcAlign,
4038 const TargetLowering &TLI) {
4039 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4040 "Expecting memcpy / memset source to meet alignment requirement!");
4041 // If 'SrcAlign' is zero, that means the memory operation does not need to
4042 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4043 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4044 // is the specified alignment of the memory operation. If it is zero, that
4045 // means it's possible to change the alignment of the destination.
4046 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4047 // not need to be loaded.
4048 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4049 IsMemset, ZeroMemset, MemcpyStrSrc,
4050 DAG.getMachineFunction());
4052 if (VT == MVT::Other) {
4054 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4055 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4056 VT = TLI.getPointerTy();
4058 switch (DstAlign & 7) {
4059 case 0: VT = MVT::i64; break;
4060 case 4: VT = MVT::i32; break;
4061 case 2: VT = MVT::i16; break;
4062 default: VT = MVT::i8; break;
4067 while (!TLI.isTypeLegal(LVT))
4068 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4069 assert(LVT.isInteger());
4075 unsigned NumMemOps = 0;
4077 unsigned VTSize = VT.getSizeInBits() / 8;
4078 while (VTSize > Size) {
4079 // For now, only use non-vector load / store's for the left-over pieces.
4084 if (VT.isVector() || VT.isFloatingPoint()) {
4085 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4086 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4087 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4089 else if (NewVT == MVT::i64 &&
4090 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4091 TLI.isSafeMemOpType(MVT::f64)) {
4092 // i64 is usually not legal on 32-bit targets, but f64 may be.
4100 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4101 if (NewVT == MVT::i8)
4103 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4105 NewVTSize = NewVT.getSizeInBits() / 8;
4107 // If the new VT cannot cover all of the remaining bits, then consider
4108 // issuing a (or a pair of) unaligned and overlapping load / store.
4109 // FIXME: Only does this for 64-bit or more since we don't have proper
4110 // cost model for unaligned load / store.
4113 if (NumMemOps && AllowOverlap &&
4114 VTSize >= 8 && NewVTSize < Size &&
4115 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4123 if (++NumMemOps > Limit)
4126 MemOps.push_back(VT);
4133 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4134 SDValue Chain, SDValue Dst,
4135 SDValue Src, uint64_t Size,
4136 unsigned Align, bool isVol,
4138 MachinePointerInfo DstPtrInfo,
4139 MachinePointerInfo SrcPtrInfo) {
4140 // Turn a memcpy of undef to nop.
4141 if (Src.getOpcode() == ISD::UNDEF)
4144 // Expand memcpy to a series of load and store ops if the size operand falls
4145 // below a certain threshold.
4146 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4147 // rather than maybe a humongous number of loads and stores.
4148 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4149 std::vector<EVT> MemOps;
4150 bool DstAlignCanChange = false;
4151 MachineFunction &MF = DAG.getMachineFunction();
4152 MachineFrameInfo *MFI = MF.getFrameInfo();
4153 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4154 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4155 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4156 DstAlignCanChange = true;
4157 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4158 if (Align > SrcAlign)
4161 bool CopyFromStr = isMemSrcFromString(Src, Str);
4162 bool isZeroStr = CopyFromStr && Str.empty();
4163 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4165 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4166 (DstAlignCanChange ? 0 : Align),
4167 (isZeroStr ? 0 : SrcAlign),
4168 false, false, CopyFromStr, true, DAG, TLI))
4171 if (DstAlignCanChange) {
4172 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4173 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4175 // Don't promote to an alignment that would require dynamic stack
4177 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4178 if (!TRI->needsStackRealignment(MF))
4179 while (NewAlign > Align &&
4180 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4183 if (NewAlign > Align) {
4184 // Give the stack frame object a larger alignment if needed.
4185 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4186 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4191 SmallVector<SDValue, 8> OutChains;
4192 unsigned NumMemOps = MemOps.size();
4193 uint64_t SrcOff = 0, DstOff = 0;
4194 for (unsigned i = 0; i != NumMemOps; ++i) {
4196 unsigned VTSize = VT.getSizeInBits() / 8;
4197 SDValue Value, Store;
4199 if (VTSize > Size) {
4200 // Issuing an unaligned load / store pair that overlaps with the previous
4201 // pair. Adjust the offset accordingly.
4202 assert(i == NumMemOps-1 && i != 0);
4203 SrcOff -= VTSize - Size;
4204 DstOff -= VTSize - Size;
4208 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4209 // It's unlikely a store of a vector immediate can be done in a single
4210 // instruction. It would require a load from a constantpool first.
4211 // We only handle zero vectors here.
4212 // FIXME: Handle other cases where store of vector immediate is done in
4213 // a single instruction.
4214 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4215 if (Value.getNode())
4216 Store = DAG.getStore(Chain, dl, Value,
4217 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4218 DstPtrInfo.getWithOffset(DstOff), isVol,
4222 if (!Store.getNode()) {
4223 // The type might not be legal for the target. This should only happen
4224 // if the type is smaller than a legal type, as on PPC, so the right
4225 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4226 // to Load/Store if NVT==VT.
4227 // FIXME does the case above also need this?
4228 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4229 assert(NVT.bitsGE(VT));
4230 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4231 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4232 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4233 false, MinAlign(SrcAlign, SrcOff));
4234 Store = DAG.getTruncStore(Chain, dl, Value,
4235 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4236 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4239 OutChains.push_back(Store);
4245 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4248 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4249 SDValue Chain, SDValue Dst,
4250 SDValue Src, uint64_t Size,
4251 unsigned Align, bool isVol,
4253 MachinePointerInfo DstPtrInfo,
4254 MachinePointerInfo SrcPtrInfo) {
4255 // Turn a memmove of undef to nop.
4256 if (Src.getOpcode() == ISD::UNDEF)
4259 // Expand memmove to a series of load and store ops if the size operand falls
4260 // below a certain threshold.
4261 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4262 std::vector<EVT> MemOps;
4263 bool DstAlignCanChange = false;
4264 MachineFunction &MF = DAG.getMachineFunction();
4265 MachineFrameInfo *MFI = MF.getFrameInfo();
4266 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4267 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4268 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4269 DstAlignCanChange = true;
4270 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4271 if (Align > SrcAlign)
4273 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4275 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4276 (DstAlignCanChange ? 0 : Align), SrcAlign,
4277 false, false, false, false, DAG, TLI))
4280 if (DstAlignCanChange) {
4281 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4282 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4283 if (NewAlign > Align) {
4284 // Give the stack frame object a larger alignment if needed.
4285 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4286 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4291 uint64_t SrcOff = 0, DstOff = 0;
4292 SmallVector<SDValue, 8> LoadValues;
4293 SmallVector<SDValue, 8> LoadChains;
4294 SmallVector<SDValue, 8> OutChains;
4295 unsigned NumMemOps = MemOps.size();
4296 for (unsigned i = 0; i < NumMemOps; i++) {
4298 unsigned VTSize = VT.getSizeInBits() / 8;
4301 Value = DAG.getLoad(VT, dl, Chain,
4302 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4303 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4304 false, false, SrcAlign);
4305 LoadValues.push_back(Value);
4306 LoadChains.push_back(Value.getValue(1));
4309 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4311 for (unsigned i = 0; i < NumMemOps; i++) {
4313 unsigned VTSize = VT.getSizeInBits() / 8;
4316 Store = DAG.getStore(Chain, dl, LoadValues[i],
4317 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4318 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4319 OutChains.push_back(Store);
4323 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4326 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4329 /// \param DAG Selection DAG where lowered code is placed.
4330 /// \param dl Link to corresponding IR location.
4331 /// \param Chain Control flow dependency.
4332 /// \param Dst Pointer to destination memory location.
4333 /// \param Src Value of byte to write into the memory.
4334 /// \param Size Number of bytes to write.
4335 /// \param Align Alignment of the destination in bytes.
4336 /// \param isVol True if destination is volatile.
4337 /// \param DstPtrInfo IR information on the memory pointer.
4338 /// \returns New head in the control flow, if lowering was successful, empty
4339 /// SDValue otherwise.
4341 /// The function tries to replace 'llvm.memset' intrinsic with several store
4342 /// operations and value calculation code. This is usually profitable for small
4344 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4345 SDValue Chain, SDValue Dst,
4346 SDValue Src, uint64_t Size,
4347 unsigned Align, bool isVol,
4348 MachinePointerInfo DstPtrInfo) {
4349 // Turn a memset of undef to nop.
4350 if (Src.getOpcode() == ISD::UNDEF)
4353 // Expand memset to a series of load/store ops if the size operand
4354 // falls below a certain threshold.
4355 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4356 std::vector<EVT> MemOps;
4357 bool DstAlignCanChange = false;
4358 MachineFunction &MF = DAG.getMachineFunction();
4359 MachineFrameInfo *MFI = MF.getFrameInfo();
4360 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4361 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4362 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4363 DstAlignCanChange = true;
4365 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4366 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4367 Size, (DstAlignCanChange ? 0 : Align), 0,
4368 true, IsZeroVal, false, true, DAG, TLI))
4371 if (DstAlignCanChange) {
4372 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4373 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4374 if (NewAlign > Align) {
4375 // Give the stack frame object a larger alignment if needed.
4376 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4377 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4382 SmallVector<SDValue, 8> OutChains;
4383 uint64_t DstOff = 0;
4384 unsigned NumMemOps = MemOps.size();
4386 // Find the largest store and generate the bit pattern for it.
4387 EVT LargestVT = MemOps[0];
4388 for (unsigned i = 1; i < NumMemOps; i++)
4389 if (MemOps[i].bitsGT(LargestVT))
4390 LargestVT = MemOps[i];
4391 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4393 for (unsigned i = 0; i < NumMemOps; i++) {
4395 unsigned VTSize = VT.getSizeInBits() / 8;
4396 if (VTSize > Size) {
4397 // Issuing an unaligned load / store pair that overlaps with the previous
4398 // pair. Adjust the offset accordingly.
4399 assert(i == NumMemOps-1 && i != 0);
4400 DstOff -= VTSize - Size;
4403 // If this store is smaller than the largest store see whether we can get
4404 // the smaller value for free with a truncate.
4405 SDValue Value = MemSetValue;
4406 if (VT.bitsLT(LargestVT)) {
4407 if (!LargestVT.isVector() && !VT.isVector() &&
4408 TLI.isTruncateFree(LargestVT, VT))
4409 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4411 Value = getMemsetValue(Src, VT, DAG, dl);
4413 assert(Value.getValueType() == VT && "Value with wrong type.");
4414 SDValue Store = DAG.getStore(Chain, dl, Value,
4415 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4416 DstPtrInfo.getWithOffset(DstOff),
4417 isVol, false, Align);
4418 OutChains.push_back(Store);
4419 DstOff += VT.getSizeInBits() / 8;
4423 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4426 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4427 SDValue Src, SDValue Size,
4428 unsigned Align, bool isVol, bool AlwaysInline,
4429 bool isTailCall, MachinePointerInfo DstPtrInfo,
4430 MachinePointerInfo SrcPtrInfo) {
4431 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4433 // Check to see if we should lower the memcpy to loads and stores first.
4434 // For cases within the target-specified limits, this is the best choice.
4435 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4437 // Memcpy with size zero? Just return the original chain.
4438 if (ConstantSize->isNullValue())
4441 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4442 ConstantSize->getZExtValue(),Align,
4443 isVol, false, DstPtrInfo, SrcPtrInfo);
4444 if (Result.getNode())
4448 // Then check to see if we should lower the memcpy with target-specific
4449 // code. If the target chooses to do this, this is the next best.
4451 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4452 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4453 DstPtrInfo, SrcPtrInfo);
4454 if (Result.getNode())
4458 // If we really need inline code and the target declined to provide it,
4459 // use a (potentially long) sequence of loads and stores.
4461 assert(ConstantSize && "AlwaysInline requires a constant size!");
4462 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4463 ConstantSize->getZExtValue(), Align, isVol,
4464 true, DstPtrInfo, SrcPtrInfo);
4467 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4468 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4469 // respect volatile, so they may do things like read or write memory
4470 // beyond the given memory regions. But fixing this isn't easy, and most
4471 // people don't care.
4473 // Emit a library call.
4474 TargetLowering::ArgListTy Args;
4475 TargetLowering::ArgListEntry Entry;
4476 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4477 Entry.Node = Dst; Args.push_back(Entry);
4478 Entry.Node = Src; Args.push_back(Entry);
4479 Entry.Node = Size; Args.push_back(Entry);
4480 // FIXME: pass in SDLoc
4481 TargetLowering::CallLoweringInfo CLI(*this);
4482 CLI.setDebugLoc(dl).setChain(Chain)
4483 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4484 Type::getVoidTy(*getContext()),
4485 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4486 TLI->getPointerTy()), std::move(Args), 0)
4488 .setTailCall(isTailCall);
4490 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4491 return CallResult.second;
4494 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4495 SDValue Src, SDValue Size,
4496 unsigned Align, bool isVol, bool isTailCall,
4497 MachinePointerInfo DstPtrInfo,
4498 MachinePointerInfo SrcPtrInfo) {
4499 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4501 // Check to see if we should lower the memmove to loads and stores first.
4502 // For cases within the target-specified limits, this is the best choice.
4503 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4505 // Memmove with size zero? Just return the original chain.
4506 if (ConstantSize->isNullValue())
4510 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4511 ConstantSize->getZExtValue(), Align, isVol,
4512 false, DstPtrInfo, SrcPtrInfo);
4513 if (Result.getNode())
4517 // Then check to see if we should lower the memmove with target-specific
4518 // code. If the target chooses to do this, this is the next best.
4520 SDValue Result = TSI->EmitTargetCodeForMemmove(
4521 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4522 if (Result.getNode())
4526 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4527 // not be safe. See memcpy above for more details.
4529 // Emit a library call.
4530 TargetLowering::ArgListTy Args;
4531 TargetLowering::ArgListEntry Entry;
4532 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4533 Entry.Node = Dst; Args.push_back(Entry);
4534 Entry.Node = Src; Args.push_back(Entry);
4535 Entry.Node = Size; Args.push_back(Entry);
4536 // FIXME: pass in SDLoc
4537 TargetLowering::CallLoweringInfo CLI(*this);
4538 CLI.setDebugLoc(dl).setChain(Chain)
4539 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4540 Type::getVoidTy(*getContext()),
4541 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4542 TLI->getPointerTy()), std::move(Args), 0)
4544 .setTailCall(isTailCall);
4546 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4547 return CallResult.second;
4550 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4551 SDValue Src, SDValue Size,
4552 unsigned Align, bool isVol, bool isTailCall,
4553 MachinePointerInfo DstPtrInfo) {
4554 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4556 // Check to see if we should lower the memset to stores first.
4557 // For cases within the target-specified limits, this is the best choice.
4558 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4560 // Memset with size zero? Just return the original chain.
4561 if (ConstantSize->isNullValue())
4565 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4566 Align, isVol, DstPtrInfo);
4568 if (Result.getNode())
4572 // Then check to see if we should lower the memset with target-specific
4573 // code. If the target chooses to do this, this is the next best.
4575 SDValue Result = TSI->EmitTargetCodeForMemset(
4576 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4577 if (Result.getNode())
4581 // Emit a library call.
4582 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4583 TargetLowering::ArgListTy Args;
4584 TargetLowering::ArgListEntry Entry;
4585 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4586 Args.push_back(Entry);
4588 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4589 Args.push_back(Entry);
4591 Entry.Ty = IntPtrTy;
4592 Args.push_back(Entry);
4594 // FIXME: pass in SDLoc
4595 TargetLowering::CallLoweringInfo CLI(*this);
4596 CLI.setDebugLoc(dl).setChain(Chain)
4597 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4598 Type::getVoidTy(*getContext()),
4599 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4600 TLI->getPointerTy()), std::move(Args), 0)
4602 .setTailCall(isTailCall);
4604 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4605 return CallResult.second;
4608 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4609 SDVTList VTList, ArrayRef<SDValue> Ops,
4610 MachineMemOperand *MMO,
4611 AtomicOrdering SuccessOrdering,
4612 AtomicOrdering FailureOrdering,
4613 SynchronizationScope SynchScope) {
4614 FoldingSetNodeID ID;
4615 ID.AddInteger(MemVT.getRawBits());
4616 AddNodeIDNode(ID, Opcode, VTList, Ops);
4617 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4619 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4620 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4621 return SDValue(E, 0);
4624 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4625 // SDNode doesn't have access to it. This memory will be "leaked" when
4626 // the node is deallocated, but recovered when the allocator is released.
4627 // If the number of operands is less than 5 we use AtomicSDNode's internal
4629 unsigned NumOps = Ops.size();
4630 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4633 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4634 dl.getDebugLoc(), VTList, MemVT,
4635 Ops.data(), DynOps, NumOps, MMO,
4636 SuccessOrdering, FailureOrdering,
4638 CSEMap.InsertNode(N, IP);
4640 return SDValue(N, 0);
4643 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4644 SDVTList VTList, ArrayRef<SDValue> Ops,
4645 MachineMemOperand *MMO,
4646 AtomicOrdering Ordering,
4647 SynchronizationScope SynchScope) {
4648 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4649 Ordering, SynchScope);
4652 SDValue SelectionDAG::getAtomicCmpSwap(
4653 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4654 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4655 unsigned Alignment, AtomicOrdering SuccessOrdering,
4656 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4657 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4658 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4659 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4661 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4662 Alignment = getEVTAlignment(MemVT);
4664 MachineFunction &MF = getMachineFunction();
4666 // FIXME: Volatile isn't really correct; we should keep track of atomic
4667 // orderings in the memoperand.
4668 unsigned Flags = MachineMemOperand::MOVolatile;
4669 Flags |= MachineMemOperand::MOLoad;
4670 Flags |= MachineMemOperand::MOStore;
4672 MachineMemOperand *MMO =
4673 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4675 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4676 SuccessOrdering, FailureOrdering, SynchScope);
4679 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4680 SDVTList VTs, SDValue Chain, SDValue Ptr,
4681 SDValue Cmp, SDValue Swp,
4682 MachineMemOperand *MMO,
4683 AtomicOrdering SuccessOrdering,
4684 AtomicOrdering FailureOrdering,
4685 SynchronizationScope SynchScope) {
4686 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4687 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4688 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4690 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4691 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4692 SuccessOrdering, FailureOrdering, SynchScope);
4695 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4697 SDValue Ptr, SDValue Val,
4698 const Value* PtrVal,
4700 AtomicOrdering Ordering,
4701 SynchronizationScope SynchScope) {
4702 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4703 Alignment = getEVTAlignment(MemVT);
4705 MachineFunction &MF = getMachineFunction();
4706 // An atomic store does not load. An atomic load does not store.
4707 // (An atomicrmw obviously both loads and stores.)
4708 // For now, atomics are considered to be volatile always, and they are
4710 // FIXME: Volatile isn't really correct; we should keep track of atomic
4711 // orderings in the memoperand.
4712 unsigned Flags = MachineMemOperand::MOVolatile;
4713 if (Opcode != ISD::ATOMIC_STORE)
4714 Flags |= MachineMemOperand::MOLoad;
4715 if (Opcode != ISD::ATOMIC_LOAD)
4716 Flags |= MachineMemOperand::MOStore;
4718 MachineMemOperand *MMO =
4719 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4720 MemVT.getStoreSize(), Alignment);
4722 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4723 Ordering, SynchScope);
4726 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4728 SDValue Ptr, SDValue Val,
4729 MachineMemOperand *MMO,
4730 AtomicOrdering Ordering,
4731 SynchronizationScope SynchScope) {
4732 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4733 Opcode == ISD::ATOMIC_LOAD_SUB ||
4734 Opcode == ISD::ATOMIC_LOAD_AND ||
4735 Opcode == ISD::ATOMIC_LOAD_OR ||
4736 Opcode == ISD::ATOMIC_LOAD_XOR ||
4737 Opcode == ISD::ATOMIC_LOAD_NAND ||
4738 Opcode == ISD::ATOMIC_LOAD_MIN ||
4739 Opcode == ISD::ATOMIC_LOAD_MAX ||
4740 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4741 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4742 Opcode == ISD::ATOMIC_SWAP ||
4743 Opcode == ISD::ATOMIC_STORE) &&
4744 "Invalid Atomic Op");
4746 EVT VT = Val.getValueType();
4748 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4749 getVTList(VT, MVT::Other);
4750 SDValue Ops[] = {Chain, Ptr, Val};
4751 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4754 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4755 EVT VT, SDValue Chain,
4757 MachineMemOperand *MMO,
4758 AtomicOrdering Ordering,
4759 SynchronizationScope SynchScope) {
4760 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4762 SDVTList VTs = getVTList(VT, MVT::Other);
4763 SDValue Ops[] = {Chain, Ptr};
4764 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4767 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4768 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4769 if (Ops.size() == 1)
4772 SmallVector<EVT, 4> VTs;
4773 VTs.reserve(Ops.size());
4774 for (unsigned i = 0; i < Ops.size(); ++i)
4775 VTs.push_back(Ops[i].getValueType());
4776 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4780 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4781 ArrayRef<SDValue> Ops,
4782 EVT MemVT, MachinePointerInfo PtrInfo,
4783 unsigned Align, bool Vol,
4784 bool ReadMem, bool WriteMem, unsigned Size) {
4785 if (Align == 0) // Ensure that codegen never sees alignment 0
4786 Align = getEVTAlignment(MemVT);
4788 MachineFunction &MF = getMachineFunction();
4791 Flags |= MachineMemOperand::MOStore;
4793 Flags |= MachineMemOperand::MOLoad;
4795 Flags |= MachineMemOperand::MOVolatile;
4797 Size = MemVT.getStoreSize();
4798 MachineMemOperand *MMO =
4799 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4801 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4805 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4806 ArrayRef<SDValue> Ops, EVT MemVT,
4807 MachineMemOperand *MMO) {
4808 assert((Opcode == ISD::INTRINSIC_VOID ||
4809 Opcode == ISD::INTRINSIC_W_CHAIN ||
4810 Opcode == ISD::PREFETCH ||
4811 Opcode == ISD::LIFETIME_START ||
4812 Opcode == ISD::LIFETIME_END ||
4813 (Opcode <= INT_MAX &&
4814 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4815 "Opcode is not a memory-accessing opcode!");
4817 // Memoize the node unless it returns a flag.
4818 MemIntrinsicSDNode *N;
4819 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4820 FoldingSetNodeID ID;
4821 AddNodeIDNode(ID, Opcode, VTList, Ops);
4822 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4824 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4825 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4826 return SDValue(E, 0);
4829 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4830 dl.getDebugLoc(), VTList, Ops,
4832 CSEMap.InsertNode(N, IP);
4834 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4835 dl.getDebugLoc(), VTList, Ops,
4839 return SDValue(N, 0);
4842 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4843 /// MachinePointerInfo record from it. This is particularly useful because the
4844 /// code generator has many cases where it doesn't bother passing in a
4845 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4846 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4847 // If this is FI+Offset, we can model it.
4848 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4849 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4851 // If this is (FI+Offset1)+Offset2, we can model it.
4852 if (Ptr.getOpcode() != ISD::ADD ||
4853 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4854 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4855 return MachinePointerInfo();
4857 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4858 return MachinePointerInfo::getFixedStack(FI, Offset+
4859 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4862 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4863 /// MachinePointerInfo record from it. This is particularly useful because the
4864 /// code generator has many cases where it doesn't bother passing in a
4865 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4866 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4867 // If the 'Offset' value isn't a constant, we can't handle this.
4868 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4869 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4870 if (OffsetOp.getOpcode() == ISD::UNDEF)
4871 return InferPointerInfo(Ptr);
4872 return MachinePointerInfo();
4877 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4878 EVT VT, SDLoc dl, SDValue Chain,
4879 SDValue Ptr, SDValue Offset,
4880 MachinePointerInfo PtrInfo, EVT MemVT,
4881 bool isVolatile, bool isNonTemporal, bool isInvariant,
4882 unsigned Alignment, const AAMDNodes &AAInfo,
4883 const MDNode *Ranges) {
4884 assert(Chain.getValueType() == MVT::Other &&
4885 "Invalid chain type");
4886 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4887 Alignment = getEVTAlignment(VT);
4889 unsigned Flags = MachineMemOperand::MOLoad;
4891 Flags |= MachineMemOperand::MOVolatile;
4893 Flags |= MachineMemOperand::MONonTemporal;
4895 Flags |= MachineMemOperand::MOInvariant;
4897 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4899 if (PtrInfo.V.isNull())
4900 PtrInfo = InferPointerInfo(Ptr, Offset);
4902 MachineFunction &MF = getMachineFunction();
4903 MachineMemOperand *MMO =
4904 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4906 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4910 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4911 EVT VT, SDLoc dl, SDValue Chain,
4912 SDValue Ptr, SDValue Offset, EVT MemVT,
4913 MachineMemOperand *MMO) {
4915 ExtType = ISD::NON_EXTLOAD;
4916 } else if (ExtType == ISD::NON_EXTLOAD) {
4917 assert(VT == MemVT && "Non-extending load from different memory type!");
4920 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4921 "Should only be an extending load, not truncating!");
4922 assert(VT.isInteger() == MemVT.isInteger() &&
4923 "Cannot convert from FP to Int or Int -> FP!");
4924 assert(VT.isVector() == MemVT.isVector() &&
4925 "Cannot use an ext load to convert to or from a vector!");
4926 assert((!VT.isVector() ||
4927 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4928 "Cannot use an ext load to change the number of vector elements!");
4931 bool Indexed = AM != ISD::UNINDEXED;
4932 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4933 "Unindexed load with an offset!");
4935 SDVTList VTs = Indexed ?
4936 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4937 SDValue Ops[] = { Chain, Ptr, Offset };
4938 FoldingSetNodeID ID;
4939 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4940 ID.AddInteger(MemVT.getRawBits());
4941 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4942 MMO->isNonTemporal(),
4943 MMO->isInvariant()));
4944 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4946 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4947 cast<LoadSDNode>(E)->refineAlignment(MMO);
4948 return SDValue(E, 0);
4950 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4951 dl.getDebugLoc(), VTs, AM, ExtType,
4953 CSEMap.InsertNode(N, IP);
4955 return SDValue(N, 0);
4958 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4959 SDValue Chain, SDValue Ptr,
4960 MachinePointerInfo PtrInfo,
4961 bool isVolatile, bool isNonTemporal,
4962 bool isInvariant, unsigned Alignment,
4963 const AAMDNodes &AAInfo,
4964 const MDNode *Ranges) {
4965 SDValue Undef = getUNDEF(Ptr.getValueType());
4966 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4967 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4971 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4972 SDValue Chain, SDValue Ptr,
4973 MachineMemOperand *MMO) {
4974 SDValue Undef = getUNDEF(Ptr.getValueType());
4975 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4979 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4980 SDValue Chain, SDValue Ptr,
4981 MachinePointerInfo PtrInfo, EVT MemVT,
4982 bool isVolatile, bool isNonTemporal,
4983 bool isInvariant, unsigned Alignment,
4984 const AAMDNodes &AAInfo) {
4985 SDValue Undef = getUNDEF(Ptr.getValueType());
4986 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4987 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4992 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4993 SDValue Chain, SDValue Ptr, EVT MemVT,
4994 MachineMemOperand *MMO) {
4995 SDValue Undef = getUNDEF(Ptr.getValueType());
4996 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5001 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5002 SDValue Offset, ISD::MemIndexedMode AM) {
5003 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5004 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5005 "Load is already a indexed load!");
5006 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5007 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5008 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5009 false, LD->getAlignment());
5012 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5013 SDValue Ptr, MachinePointerInfo PtrInfo,
5014 bool isVolatile, bool isNonTemporal,
5015 unsigned Alignment, const AAMDNodes &AAInfo) {
5016 assert(Chain.getValueType() == MVT::Other &&
5017 "Invalid chain type");
5018 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5019 Alignment = getEVTAlignment(Val.getValueType());
5021 unsigned Flags = MachineMemOperand::MOStore;
5023 Flags |= MachineMemOperand::MOVolatile;
5025 Flags |= MachineMemOperand::MONonTemporal;
5027 if (PtrInfo.V.isNull())
5028 PtrInfo = InferPointerInfo(Ptr);
5030 MachineFunction &MF = getMachineFunction();
5031 MachineMemOperand *MMO =
5032 MF.getMachineMemOperand(PtrInfo, Flags,
5033 Val.getValueType().getStoreSize(), Alignment,
5036 return getStore(Chain, dl, Val, Ptr, MMO);
5039 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5040 SDValue Ptr, MachineMemOperand *MMO) {
5041 assert(Chain.getValueType() == MVT::Other &&
5042 "Invalid chain type");
5043 EVT VT = Val.getValueType();
5044 SDVTList VTs = getVTList(MVT::Other);
5045 SDValue Undef = getUNDEF(Ptr.getValueType());
5046 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5047 FoldingSetNodeID ID;
5048 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5049 ID.AddInteger(VT.getRawBits());
5050 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5051 MMO->isNonTemporal(), MMO->isInvariant()));
5052 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5054 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5055 cast<StoreSDNode>(E)->refineAlignment(MMO);
5056 return SDValue(E, 0);
5058 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5059 dl.getDebugLoc(), VTs,
5060 ISD::UNINDEXED, false, VT, MMO);
5061 CSEMap.InsertNode(N, IP);
5063 return SDValue(N, 0);
5066 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5067 SDValue Ptr, MachinePointerInfo PtrInfo,
5068 EVT SVT,bool isVolatile, bool isNonTemporal,
5070 const AAMDNodes &AAInfo) {
5071 assert(Chain.getValueType() == MVT::Other &&
5072 "Invalid chain type");
5073 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5074 Alignment = getEVTAlignment(SVT);
5076 unsigned Flags = MachineMemOperand::MOStore;
5078 Flags |= MachineMemOperand::MOVolatile;
5080 Flags |= MachineMemOperand::MONonTemporal;
5082 if (PtrInfo.V.isNull())
5083 PtrInfo = InferPointerInfo(Ptr);
5085 MachineFunction &MF = getMachineFunction();
5086 MachineMemOperand *MMO =
5087 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5090 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5093 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5094 SDValue Ptr, EVT SVT,
5095 MachineMemOperand *MMO) {
5096 EVT VT = Val.getValueType();
5098 assert(Chain.getValueType() == MVT::Other &&
5099 "Invalid chain type");
5101 return getStore(Chain, dl, Val, Ptr, MMO);
5103 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5104 "Should only be a truncating store, not extending!");
5105 assert(VT.isInteger() == SVT.isInteger() &&
5106 "Can't do FP-INT conversion!");
5107 assert(VT.isVector() == SVT.isVector() &&
5108 "Cannot use trunc store to convert to or from a vector!");
5109 assert((!VT.isVector() ||
5110 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5111 "Cannot use trunc store to change the number of vector elements!");
5113 SDVTList VTs = getVTList(MVT::Other);
5114 SDValue Undef = getUNDEF(Ptr.getValueType());
5115 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5116 FoldingSetNodeID ID;
5117 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5118 ID.AddInteger(SVT.getRawBits());
5119 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5120 MMO->isNonTemporal(), MMO->isInvariant()));
5121 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5123 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5124 cast<StoreSDNode>(E)->refineAlignment(MMO);
5125 return SDValue(E, 0);
5127 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5128 dl.getDebugLoc(), VTs,
5129 ISD::UNINDEXED, true, SVT, MMO);
5130 CSEMap.InsertNode(N, IP);
5132 return SDValue(N, 0);
5136 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5137 SDValue Offset, ISD::MemIndexedMode AM) {
5138 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5139 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5140 "Store is already a indexed store!");
5141 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5142 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5143 FoldingSetNodeID ID;
5144 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5145 ID.AddInteger(ST->getMemoryVT().getRawBits());
5146 ID.AddInteger(ST->getRawSubclassData());
5147 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5149 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5150 return SDValue(E, 0);
5152 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5153 dl.getDebugLoc(), VTs, AM,
5154 ST->isTruncatingStore(),
5156 ST->getMemOperand());
5157 CSEMap.InsertNode(N, IP);
5159 return SDValue(N, 0);
5163 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5164 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5165 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5167 SDVTList VTs = getVTList(VT, MVT::Other);
5168 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5169 FoldingSetNodeID ID;
5170 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5171 ID.AddInteger(VT.getRawBits());
5172 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5174 MMO->isNonTemporal(),
5175 MMO->isInvariant()));
5176 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5178 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5179 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5180 return SDValue(E, 0);
5182 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5183 dl.getDebugLoc(), Ops, 4, VTs,
5185 CSEMap.InsertNode(N, IP);
5187 return SDValue(N, 0);
5190 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5191 SDValue Ptr, SDValue Mask, EVT MemVT,
5192 MachineMemOperand *MMO, bool isTrunc) {
5193 assert(Chain.getValueType() == MVT::Other &&
5194 "Invalid chain type");
5195 EVT VT = Val.getValueType();
5196 SDVTList VTs = getVTList(MVT::Other);
5197 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5198 FoldingSetNodeID ID;
5199 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5200 ID.AddInteger(VT.getRawBits());
5201 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5202 MMO->isNonTemporal(), MMO->isInvariant()));
5203 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5205 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5206 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5207 return SDValue(E, 0);
5209 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5210 dl.getDebugLoc(), Ops, 4,
5211 VTs, isTrunc, MemVT, MMO);
5212 CSEMap.InsertNode(N, IP);
5214 return SDValue(N, 0);
5218 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5219 ArrayRef<SDValue> Ops,
5220 MachineMemOperand *MMO) {
5222 FoldingSetNodeID ID;
5223 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5224 ID.AddInteger(VT.getRawBits());
5225 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5227 MMO->isNonTemporal(),
5228 MMO->isInvariant()));
5229 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5231 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5232 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5233 return SDValue(E, 0);
5235 MaskedGatherSDNode *N =
5236 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5238 CSEMap.InsertNode(N, IP);
5240 return SDValue(N, 0);
5243 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5244 ArrayRef<SDValue> Ops,
5245 MachineMemOperand *MMO) {
5246 FoldingSetNodeID ID;
5247 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5248 ID.AddInteger(VT.getRawBits());
5249 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5250 MMO->isNonTemporal(),
5251 MMO->isInvariant()));
5252 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5254 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5255 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5256 return SDValue(E, 0);
5259 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5261 CSEMap.InsertNode(N, IP);
5263 return SDValue(N, 0);
5266 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5267 SDValue Chain, SDValue Ptr,
5270 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5271 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5274 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5275 ArrayRef<SDUse> Ops) {
5276 switch (Ops.size()) {
5277 case 0: return getNode(Opcode, DL, VT);
5278 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5279 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5280 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5284 // Copy from an SDUse array into an SDValue array for use with
5285 // the regular getNode logic.
5286 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5287 return getNode(Opcode, DL, VT, NewOps);
5290 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5291 ArrayRef<SDValue> Ops) {
5292 unsigned NumOps = Ops.size();
5294 case 0: return getNode(Opcode, DL, VT);
5295 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5296 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5297 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5303 case ISD::SELECT_CC: {
5304 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5305 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5306 "LHS and RHS of condition must have same type!");
5307 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5308 "True and False arms of SelectCC must have same type!");
5309 assert(Ops[2].getValueType() == VT &&
5310 "select_cc node must be of same type as true and false value!");
5314 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5315 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5316 "LHS/RHS of comparison should match types!");
5323 SDVTList VTs = getVTList(VT);
5325 if (VT != MVT::Glue) {
5326 FoldingSetNodeID ID;
5327 AddNodeIDNode(ID, Opcode, VTs, Ops);
5330 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5331 return SDValue(E, 0);
5333 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5335 CSEMap.InsertNode(N, IP);
5337 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5342 return SDValue(N, 0);
5345 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5346 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5347 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5350 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5351 ArrayRef<SDValue> Ops) {
5352 if (VTList.NumVTs == 1)
5353 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5357 // FIXME: figure out how to safely handle things like
5358 // int foo(int x) { return 1 << (x & 255); }
5359 // int bar() { return foo(256); }
5360 case ISD::SRA_PARTS:
5361 case ISD::SRL_PARTS:
5362 case ISD::SHL_PARTS:
5363 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5364 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5365 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5366 else if (N3.getOpcode() == ISD::AND)
5367 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5368 // If the and is only masking out bits that cannot effect the shift,
5369 // eliminate the and.
5370 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5371 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5372 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5378 // Memoize the node unless it returns a flag.
5380 unsigned NumOps = Ops.size();
5381 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5382 FoldingSetNodeID ID;
5383 AddNodeIDNode(ID, Opcode, VTList, Ops);
5385 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5386 return SDValue(E, 0);
5389 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5390 DL.getDebugLoc(), VTList, Ops[0]);
5391 } else if (NumOps == 2) {
5392 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5393 DL.getDebugLoc(), VTList, Ops[0],
5395 } else if (NumOps == 3) {
5396 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5397 DL.getDebugLoc(), VTList, Ops[0],
5400 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5403 CSEMap.InsertNode(N, IP);
5406 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5407 DL.getDebugLoc(), VTList, Ops[0]);
5408 } else if (NumOps == 2) {
5409 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5410 DL.getDebugLoc(), VTList, Ops[0],
5412 } else if (NumOps == 3) {
5413 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5414 DL.getDebugLoc(), VTList, Ops[0],
5417 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5422 return SDValue(N, 0);
5425 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5426 return getNode(Opcode, DL, VTList, None);
5429 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5431 SDValue Ops[] = { N1 };
5432 return getNode(Opcode, DL, VTList, Ops);
5435 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5436 SDValue N1, SDValue N2) {
5437 SDValue Ops[] = { N1, N2 };
5438 return getNode(Opcode, DL, VTList, Ops);
5441 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5442 SDValue N1, SDValue N2, SDValue N3) {
5443 SDValue Ops[] = { N1, N2, N3 };
5444 return getNode(Opcode, DL, VTList, Ops);
5447 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5448 SDValue N1, SDValue N2, SDValue N3,
5450 SDValue Ops[] = { N1, N2, N3, N4 };
5451 return getNode(Opcode, DL, VTList, Ops);
5454 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5455 SDValue N1, SDValue N2, SDValue N3,
5456 SDValue N4, SDValue N5) {
5457 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5458 return getNode(Opcode, DL, VTList, Ops);
5461 SDVTList SelectionDAG::getVTList(EVT VT) {
5462 return makeVTList(SDNode::getValueTypeList(VT), 1);
5465 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5466 FoldingSetNodeID ID;
5468 ID.AddInteger(VT1.getRawBits());
5469 ID.AddInteger(VT2.getRawBits());
5472 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5474 EVT *Array = Allocator.Allocate<EVT>(2);
5477 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5478 VTListMap.InsertNode(Result, IP);
5480 return Result->getSDVTList();
5483 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5484 FoldingSetNodeID ID;
5486 ID.AddInteger(VT1.getRawBits());
5487 ID.AddInteger(VT2.getRawBits());
5488 ID.AddInteger(VT3.getRawBits());
5491 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5493 EVT *Array = Allocator.Allocate<EVT>(3);
5497 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5498 VTListMap.InsertNode(Result, IP);
5500 return Result->getSDVTList();
5503 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5504 FoldingSetNodeID ID;
5506 ID.AddInteger(VT1.getRawBits());
5507 ID.AddInteger(VT2.getRawBits());
5508 ID.AddInteger(VT3.getRawBits());
5509 ID.AddInteger(VT4.getRawBits());
5512 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5514 EVT *Array = Allocator.Allocate<EVT>(4);
5519 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5520 VTListMap.InsertNode(Result, IP);
5522 return Result->getSDVTList();
5525 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5526 unsigned NumVTs = VTs.size();
5527 FoldingSetNodeID ID;
5528 ID.AddInteger(NumVTs);
5529 for (unsigned index = 0; index < NumVTs; index++) {
5530 ID.AddInteger(VTs[index].getRawBits());
5534 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5536 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5537 std::copy(VTs.begin(), VTs.end(), Array);
5538 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5539 VTListMap.InsertNode(Result, IP);
5541 return Result->getSDVTList();
5545 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5546 /// specified operands. If the resultant node already exists in the DAG,
5547 /// this does not modify the specified node, instead it returns the node that
5548 /// already exists. If the resultant node does not exist in the DAG, the
5549 /// input node is returned. As a degenerate case, if you specify the same
5550 /// input operands as the node already has, the input node is returned.
5551 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5552 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5554 // Check to see if there is no change.
5555 if (Op == N->getOperand(0)) return N;
5557 // See if the modified node already exists.
5558 void *InsertPos = nullptr;
5559 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, 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 N->OperandList[0].set(Op);
5570 // If this gets put into a CSE map, add it.
5571 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5575 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5576 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5578 // Check to see if there is no change.
5579 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5580 return N; // No operands changed, just return the input node.
5582 // See if the modified node already exists.
5583 void *InsertPos = nullptr;
5584 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5587 // Nope it doesn't. Remove the node from its current place in the maps.
5589 if (!RemoveNodeFromCSEMaps(N))
5590 InsertPos = nullptr;
5592 // Now we update the operands.
5593 if (N->OperandList[0] != Op1)
5594 N->OperandList[0].set(Op1);
5595 if (N->OperandList[1] != Op2)
5596 N->OperandList[1].set(Op2);
5598 // If this gets put into a CSE map, add it.
5599 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5603 SDNode *SelectionDAG::
5604 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5605 SDValue Ops[] = { Op1, Op2, Op3 };
5606 return UpdateNodeOperands(N, Ops);
5609 SDNode *SelectionDAG::
5610 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5611 SDValue Op3, SDValue Op4) {
5612 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5613 return UpdateNodeOperands(N, Ops);
5616 SDNode *SelectionDAG::
5617 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5618 SDValue Op3, SDValue Op4, SDValue Op5) {
5619 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5620 return UpdateNodeOperands(N, Ops);
5623 SDNode *SelectionDAG::
5624 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5625 unsigned NumOps = Ops.size();
5626 assert(N->getNumOperands() == NumOps &&
5627 "Update with wrong number of operands");
5629 // If no operands changed just return the input node.
5630 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5633 // See if the modified node already exists.
5634 void *InsertPos = nullptr;
5635 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5638 // Nope it doesn't. Remove the node from its current place in the maps.
5640 if (!RemoveNodeFromCSEMaps(N))
5641 InsertPos = nullptr;
5643 // Now we update the operands.
5644 for (unsigned i = 0; i != NumOps; ++i)
5645 if (N->OperandList[i] != Ops[i])
5646 N->OperandList[i].set(Ops[i]);
5648 // If this gets put into a CSE map, add it.
5649 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5653 /// DropOperands - Release the operands and set this node to have
5655 void SDNode::DropOperands() {
5656 // Unlike the code in MorphNodeTo that does this, we don't need to
5657 // watch for dead nodes here.
5658 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5664 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5667 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5669 SDVTList VTs = getVTList(VT);
5670 return SelectNodeTo(N, MachineOpc, VTs, None);
5673 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5674 EVT VT, SDValue Op1) {
5675 SDVTList VTs = getVTList(VT);
5676 SDValue Ops[] = { Op1 };
5677 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5680 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5681 EVT VT, SDValue Op1,
5683 SDVTList VTs = getVTList(VT);
5684 SDValue Ops[] = { Op1, Op2 };
5685 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5688 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5689 EVT VT, SDValue Op1,
5690 SDValue Op2, SDValue Op3) {
5691 SDVTList VTs = getVTList(VT);
5692 SDValue Ops[] = { Op1, Op2, Op3 };
5693 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5696 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5697 EVT VT, ArrayRef<SDValue> Ops) {
5698 SDVTList VTs = getVTList(VT);
5699 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5702 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5703 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5704 SDVTList VTs = getVTList(VT1, VT2);
5705 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5708 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5710 SDVTList VTs = getVTList(VT1, VT2);
5711 return SelectNodeTo(N, MachineOpc, VTs, None);
5714 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5715 EVT VT1, EVT VT2, EVT VT3,
5716 ArrayRef<SDValue> Ops) {
5717 SDVTList VTs = getVTList(VT1, VT2, VT3);
5718 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5721 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5722 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5723 ArrayRef<SDValue> Ops) {
5724 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5725 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5728 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5731 SDVTList VTs = getVTList(VT1, VT2);
5732 SDValue Ops[] = { Op1 };
5733 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5736 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5738 SDValue Op1, SDValue Op2) {
5739 SDVTList VTs = getVTList(VT1, VT2);
5740 SDValue Ops[] = { Op1, Op2 };
5741 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5744 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5746 SDValue Op1, SDValue Op2,
5748 SDVTList VTs = getVTList(VT1, VT2);
5749 SDValue Ops[] = { Op1, Op2, Op3 };
5750 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5753 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5754 EVT VT1, EVT VT2, EVT VT3,
5755 SDValue Op1, SDValue Op2,
5757 SDVTList VTs = getVTList(VT1, VT2, VT3);
5758 SDValue Ops[] = { Op1, Op2, Op3 };
5759 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5762 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5763 SDVTList VTs,ArrayRef<SDValue> Ops) {
5764 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5765 // Reset the NodeID to -1.
5770 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5771 /// the line number information on the merged node since it is not possible to
5772 /// preserve the information that operation is associated with multiple lines.
5773 /// This will make the debugger working better at -O0, were there is a higher
5774 /// probability having other instructions associated with that line.
5776 /// For IROrder, we keep the smaller of the two
5777 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5778 DebugLoc NLoc = N->getDebugLoc();
5779 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5780 N->setDebugLoc(DebugLoc());
5782 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5783 N->setIROrder(Order);
5787 /// MorphNodeTo - This *mutates* the specified node to have the specified
5788 /// return type, opcode, and operands.
5790 /// Note that MorphNodeTo returns the resultant node. If there is already a
5791 /// node of the specified opcode and operands, it returns that node instead of
5792 /// the current one. Note that the SDLoc need not be the same.
5794 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5795 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5796 /// node, and because it doesn't require CSE recalculation for any of
5797 /// the node's users.
5799 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5800 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5801 /// the legalizer which maintain worklists that would need to be updated when
5802 /// deleting things.
5803 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5804 SDVTList VTs, ArrayRef<SDValue> Ops) {
5805 unsigned NumOps = Ops.size();
5806 // If an identical node already exists, use it.
5808 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5809 FoldingSetNodeID ID;
5810 AddNodeIDNode(ID, Opc, VTs, Ops);
5811 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5812 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5815 if (!RemoveNodeFromCSEMaps(N))
5818 // Start the morphing.
5820 N->ValueList = VTs.VTs;
5821 N->NumValues = VTs.NumVTs;
5823 // Clear the operands list, updating used nodes to remove this from their
5824 // use list. Keep track of any operands that become dead as a result.
5825 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5826 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5828 SDNode *Used = Use.getNode();
5830 if (Used->use_empty())
5831 DeadNodeSet.insert(Used);
5834 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5835 // Initialize the memory references information.
5836 MN->setMemRefs(nullptr, nullptr);
5837 // If NumOps is larger than the # of operands we can have in a
5838 // MachineSDNode, reallocate the operand list.
5839 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5840 if (MN->OperandsNeedDelete)
5841 delete[] MN->OperandList;
5842 if (NumOps > array_lengthof(MN->LocalOperands))
5843 // We're creating a final node that will live unmorphed for the
5844 // remainder of the current SelectionDAG iteration, so we can allocate
5845 // the operands directly out of a pool with no recycling metadata.
5846 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5847 Ops.data(), NumOps);
5849 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5850 MN->OperandsNeedDelete = false;
5852 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5854 // If NumOps is larger than the # of operands we currently have, reallocate
5855 // the operand list.
5856 if (NumOps > N->NumOperands) {
5857 if (N->OperandsNeedDelete)
5858 delete[] N->OperandList;
5859 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5860 N->OperandsNeedDelete = true;
5862 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5865 // Delete any nodes that are still dead after adding the uses for the
5867 if (!DeadNodeSet.empty()) {
5868 SmallVector<SDNode *, 16> DeadNodes;
5869 for (SDNode *N : DeadNodeSet)
5871 DeadNodes.push_back(N);
5872 RemoveDeadNodes(DeadNodes);
5876 CSEMap.InsertNode(N, IP); // Memoize the new node.
5881 /// getMachineNode - These are used for target selectors to create a new node
5882 /// with specified return type(s), MachineInstr opcode, and operands.
5884 /// Note that getMachineNode returns the resultant node. If there is already a
5885 /// node of the specified opcode and operands, it returns that node instead of
5886 /// the current one.
5888 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5889 SDVTList VTs = getVTList(VT);
5890 return getMachineNode(Opcode, dl, VTs, None);
5894 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5895 SDVTList VTs = getVTList(VT);
5896 SDValue Ops[] = { Op1 };
5897 return getMachineNode(Opcode, dl, VTs, Ops);
5901 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5902 SDValue Op1, SDValue Op2) {
5903 SDVTList VTs = getVTList(VT);
5904 SDValue Ops[] = { Op1, Op2 };
5905 return getMachineNode(Opcode, dl, VTs, Ops);
5909 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5910 SDValue Op1, SDValue Op2, SDValue Op3) {
5911 SDVTList VTs = getVTList(VT);
5912 SDValue Ops[] = { Op1, Op2, Op3 };
5913 return getMachineNode(Opcode, dl, VTs, Ops);
5917 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5918 ArrayRef<SDValue> Ops) {
5919 SDVTList VTs = getVTList(VT);
5920 return getMachineNode(Opcode, dl, VTs, Ops);
5924 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5925 SDVTList VTs = getVTList(VT1, VT2);
5926 return getMachineNode(Opcode, dl, VTs, None);
5930 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5931 EVT VT1, EVT VT2, SDValue Op1) {
5932 SDVTList VTs = getVTList(VT1, VT2);
5933 SDValue Ops[] = { Op1 };
5934 return getMachineNode(Opcode, dl, VTs, Ops);
5938 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5939 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5940 SDVTList VTs = getVTList(VT1, VT2);
5941 SDValue Ops[] = { Op1, Op2 };
5942 return getMachineNode(Opcode, dl, VTs, Ops);
5946 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5947 EVT VT1, EVT VT2, SDValue Op1,
5948 SDValue Op2, SDValue Op3) {
5949 SDVTList VTs = getVTList(VT1, VT2);
5950 SDValue Ops[] = { Op1, Op2, Op3 };
5951 return getMachineNode(Opcode, dl, VTs, Ops);
5955 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5957 ArrayRef<SDValue> Ops) {
5958 SDVTList VTs = getVTList(VT1, VT2);
5959 return getMachineNode(Opcode, dl, VTs, Ops);
5963 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5964 EVT VT1, EVT VT2, EVT VT3,
5965 SDValue Op1, SDValue Op2) {
5966 SDVTList VTs = getVTList(VT1, VT2, VT3);
5967 SDValue Ops[] = { Op1, Op2 };
5968 return getMachineNode(Opcode, dl, VTs, Ops);
5972 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5973 EVT VT1, EVT VT2, EVT VT3,
5974 SDValue Op1, SDValue Op2, SDValue Op3) {
5975 SDVTList VTs = getVTList(VT1, VT2, VT3);
5976 SDValue Ops[] = { Op1, Op2, Op3 };
5977 return getMachineNode(Opcode, dl, VTs, Ops);
5981 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5982 EVT VT1, EVT VT2, EVT VT3,
5983 ArrayRef<SDValue> Ops) {
5984 SDVTList VTs = getVTList(VT1, VT2, VT3);
5985 return getMachineNode(Opcode, dl, VTs, Ops);
5989 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5990 EVT VT2, EVT VT3, EVT VT4,
5991 ArrayRef<SDValue> Ops) {
5992 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5993 return getMachineNode(Opcode, dl, VTs, Ops);
5997 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5998 ArrayRef<EVT> ResultTys,
5999 ArrayRef<SDValue> Ops) {
6000 SDVTList VTs = getVTList(ResultTys);
6001 return getMachineNode(Opcode, dl, VTs, Ops);
6005 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6006 ArrayRef<SDValue> OpsArray) {
6007 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6010 const SDValue *Ops = OpsArray.data();
6011 unsigned NumOps = OpsArray.size();
6014 FoldingSetNodeID ID;
6015 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6017 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6018 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6022 // Allocate a new MachineSDNode.
6023 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6024 DL.getDebugLoc(), VTs);
6026 // Initialize the operands list.
6027 if (NumOps > array_lengthof(N->LocalOperands))
6028 // We're creating a final node that will live unmorphed for the
6029 // remainder of the current SelectionDAG iteration, so we can allocate
6030 // the operands directly out of a pool with no recycling metadata.
6031 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6034 N->InitOperands(N->LocalOperands, Ops, NumOps);
6035 N->OperandsNeedDelete = false;
6038 CSEMap.InsertNode(N, IP);
6044 /// getTargetExtractSubreg - A convenience function for creating
6045 /// TargetOpcode::EXTRACT_SUBREG nodes.
6047 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6049 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6050 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6051 VT, Operand, SRIdxVal);
6052 return SDValue(Subreg, 0);
6055 /// getTargetInsertSubreg - A convenience function for creating
6056 /// TargetOpcode::INSERT_SUBREG nodes.
6058 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6059 SDValue Operand, SDValue Subreg) {
6060 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6061 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6062 VT, Operand, Subreg, SRIdxVal);
6063 return SDValue(Result, 0);
6066 /// getNodeIfExists - Get the specified node if it's already available, or
6067 /// else return NULL.
6068 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6069 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6071 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6072 FoldingSetNodeID ID;
6073 AddNodeIDNode(ID, Opcode, VTList, Ops);
6074 if (isBinOpWithFlags(Opcode))
6075 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6077 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6083 /// getDbgValue - Creates a SDDbgValue node.
6086 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6087 unsigned R, bool IsIndirect, uint64_t Off,
6088 DebugLoc DL, unsigned O) {
6089 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6090 "Expected inlined-at fields to agree");
6091 return new (DbgInfo->getAlloc())
6092 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6096 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6097 const Value *C, uint64_t Off,
6098 DebugLoc DL, unsigned O) {
6099 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6100 "Expected inlined-at fields to agree");
6101 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6105 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6106 unsigned FI, uint64_t Off,
6107 DebugLoc DL, unsigned O) {
6108 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6109 "Expected inlined-at fields to agree");
6110 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6115 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6116 /// pointed to by a use iterator is deleted, increment the use iterator
6117 /// so that it doesn't dangle.
6119 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6120 SDNode::use_iterator &UI;
6121 SDNode::use_iterator &UE;
6123 void NodeDeleted(SDNode *N, SDNode *E) override {
6124 // Increment the iterator as needed.
6125 while (UI != UE && N == *UI)
6130 RAUWUpdateListener(SelectionDAG &d,
6131 SDNode::use_iterator &ui,
6132 SDNode::use_iterator &ue)
6133 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6138 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6139 /// This can cause recursive merging of nodes in the DAG.
6141 /// This version assumes From has a single result value.
6143 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6144 SDNode *From = FromN.getNode();
6145 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6146 "Cannot replace with this method!");
6147 assert(From != To.getNode() && "Cannot replace uses of with self");
6149 // Iterate over all the existing uses of From. New uses will be added
6150 // to the beginning of the use list, which we avoid visiting.
6151 // This specifically avoids visiting uses of From that arise while the
6152 // replacement is happening, because any such uses would be the result
6153 // of CSE: If an existing node looks like From after one of its operands
6154 // is replaced by To, we don't want to replace of all its users with To
6155 // too. See PR3018 for more info.
6156 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6157 RAUWUpdateListener Listener(*this, UI, UE);
6161 // This node is about to morph, remove its old self from the CSE maps.
6162 RemoveNodeFromCSEMaps(User);
6164 // A user can appear in a use list multiple times, and when this
6165 // happens the uses are usually next to each other in the list.
6166 // To help reduce the number of CSE recomputations, process all
6167 // the uses of this user that we can find this way.
6169 SDUse &Use = UI.getUse();
6172 } while (UI != UE && *UI == User);
6174 // Now that we have modified User, add it back to the CSE maps. If it
6175 // already exists there, recursively merge the results together.
6176 AddModifiedNodeToCSEMaps(User);
6179 // If we just RAUW'd the root, take note.
6180 if (FromN == getRoot())
6184 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6185 /// This can cause recursive merging of nodes in the DAG.
6187 /// This version assumes that for each value of From, there is a
6188 /// corresponding value in To in the same position with the same type.
6190 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6192 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6193 assert((!From->hasAnyUseOfValue(i) ||
6194 From->getValueType(i) == To->getValueType(i)) &&
6195 "Cannot use this version of ReplaceAllUsesWith!");
6198 // Handle the trivial case.
6202 // Iterate over just the existing users of From. See the comments in
6203 // the ReplaceAllUsesWith above.
6204 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6205 RAUWUpdateListener Listener(*this, UI, UE);
6209 // This node is about to morph, remove its old self from the CSE maps.
6210 RemoveNodeFromCSEMaps(User);
6212 // A user can appear in a use list multiple times, and when this
6213 // happens the uses are usually next to each other in the list.
6214 // To help reduce the number of CSE recomputations, process all
6215 // the uses of this user that we can find this way.
6217 SDUse &Use = UI.getUse();
6220 } while (UI != UE && *UI == User);
6222 // Now that we have modified User, add it back to the CSE maps. If it
6223 // already exists there, recursively merge the results together.
6224 AddModifiedNodeToCSEMaps(User);
6227 // If we just RAUW'd the root, take note.
6228 if (From == getRoot().getNode())
6229 setRoot(SDValue(To, getRoot().getResNo()));
6232 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6233 /// This can cause recursive merging of nodes in the DAG.
6235 /// This version can replace From with any result values. To must match the
6236 /// number and types of values returned by From.
6237 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6238 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6239 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6241 // Iterate over just the existing users of From. See the comments in
6242 // the ReplaceAllUsesWith above.
6243 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6244 RAUWUpdateListener Listener(*this, UI, UE);
6248 // This node is about to morph, remove its old self from the CSE maps.
6249 RemoveNodeFromCSEMaps(User);
6251 // A user can appear in a use list multiple times, and when this
6252 // happens the uses are usually next to each other in the list.
6253 // To help reduce the number of CSE recomputations, process all
6254 // the uses of this user that we can find this way.
6256 SDUse &Use = UI.getUse();
6257 const SDValue &ToOp = To[Use.getResNo()];
6260 } while (UI != UE && *UI == User);
6262 // Now that we have modified User, add it back to the CSE maps. If it
6263 // already exists there, recursively merge the results together.
6264 AddModifiedNodeToCSEMaps(User);
6267 // If we just RAUW'd the root, take note.
6268 if (From == getRoot().getNode())
6269 setRoot(SDValue(To[getRoot().getResNo()]));
6272 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6273 /// uses of other values produced by From.getNode() alone. The Deleted
6274 /// vector is handled the same way as for ReplaceAllUsesWith.
6275 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6276 // Handle the really simple, really trivial case efficiently.
6277 if (From == To) return;
6279 // Handle the simple, trivial, case efficiently.
6280 if (From.getNode()->getNumValues() == 1) {
6281 ReplaceAllUsesWith(From, To);
6285 // Iterate over just the existing users of From. See the comments in
6286 // the ReplaceAllUsesWith above.
6287 SDNode::use_iterator UI = From.getNode()->use_begin(),
6288 UE = From.getNode()->use_end();
6289 RAUWUpdateListener Listener(*this, UI, UE);
6292 bool UserRemovedFromCSEMaps = false;
6294 // A user can appear in a use list multiple times, and when this
6295 // happens the uses are usually next to each other in the list.
6296 // To help reduce the number of CSE recomputations, process all
6297 // the uses of this user that we can find this way.
6299 SDUse &Use = UI.getUse();
6301 // Skip uses of different values from the same node.
6302 if (Use.getResNo() != From.getResNo()) {
6307 // If this node hasn't been modified yet, it's still in the CSE maps,
6308 // so remove its old self from the CSE maps.
6309 if (!UserRemovedFromCSEMaps) {
6310 RemoveNodeFromCSEMaps(User);
6311 UserRemovedFromCSEMaps = true;
6316 } while (UI != UE && *UI == User);
6318 // We are iterating over all uses of the From node, so if a use
6319 // doesn't use the specific value, no changes are made.
6320 if (!UserRemovedFromCSEMaps)
6323 // Now that we have modified User, add it back to the CSE maps. If it
6324 // already exists there, recursively merge the results together.
6325 AddModifiedNodeToCSEMaps(User);
6328 // If we just RAUW'd the root, take note.
6329 if (From == getRoot())
6334 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6335 /// to record information about a use.
6342 /// operator< - Sort Memos by User.
6343 bool operator<(const UseMemo &L, const UseMemo &R) {
6344 return (intptr_t)L.User < (intptr_t)R.User;
6348 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6349 /// uses of other values produced by From.getNode() alone. The same value
6350 /// may appear in both the From and To list. The Deleted vector is
6351 /// handled the same way as for ReplaceAllUsesWith.
6352 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6355 // Handle the simple, trivial case efficiently.
6357 return ReplaceAllUsesOfValueWith(*From, *To);
6359 // Read up all the uses and make records of them. This helps
6360 // processing new uses that are introduced during the
6361 // replacement process.
6362 SmallVector<UseMemo, 4> Uses;
6363 for (unsigned i = 0; i != Num; ++i) {
6364 unsigned FromResNo = From[i].getResNo();
6365 SDNode *FromNode = From[i].getNode();
6366 for (SDNode::use_iterator UI = FromNode->use_begin(),
6367 E = FromNode->use_end(); UI != E; ++UI) {
6368 SDUse &Use = UI.getUse();
6369 if (Use.getResNo() == FromResNo) {
6370 UseMemo Memo = { *UI, i, &Use };
6371 Uses.push_back(Memo);
6376 // Sort the uses, so that all the uses from a given User are together.
6377 std::sort(Uses.begin(), Uses.end());
6379 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6380 UseIndex != UseIndexEnd; ) {
6381 // We know that this user uses some value of From. If it is the right
6382 // value, update it.
6383 SDNode *User = Uses[UseIndex].User;
6385 // This node is about to morph, remove its old self from the CSE maps.
6386 RemoveNodeFromCSEMaps(User);
6388 // The Uses array is sorted, so all the uses for a given User
6389 // are next to each other in the list.
6390 // To help reduce the number of CSE recomputations, process all
6391 // the uses of this user that we can find this way.
6393 unsigned i = Uses[UseIndex].Index;
6394 SDUse &Use = *Uses[UseIndex].Use;
6398 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6400 // Now that we have modified User, add it back to the CSE maps. If it
6401 // already exists there, recursively merge the results together.
6402 AddModifiedNodeToCSEMaps(User);
6406 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6407 /// based on their topological order. It returns the maximum id and a vector
6408 /// of the SDNodes* in assigned order by reference.
6409 unsigned SelectionDAG::AssignTopologicalOrder() {
6411 unsigned DAGSize = 0;
6413 // SortedPos tracks the progress of the algorithm. Nodes before it are
6414 // sorted, nodes after it are unsorted. When the algorithm completes
6415 // it is at the end of the list.
6416 allnodes_iterator SortedPos = allnodes_begin();
6418 // Visit all the nodes. Move nodes with no operands to the front of
6419 // the list immediately. Annotate nodes that do have operands with their
6420 // operand count. Before we do this, the Node Id fields of the nodes
6421 // may contain arbitrary values. After, the Node Id fields for nodes
6422 // before SortedPos will contain the topological sort index, and the
6423 // Node Id fields for nodes At SortedPos and after will contain the
6424 // count of outstanding operands.
6425 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6427 checkForCycles(N, this);
6428 unsigned Degree = N->getNumOperands();
6430 // A node with no uses, add it to the result array immediately.
6431 N->setNodeId(DAGSize++);
6432 allnodes_iterator Q = N;
6434 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6435 assert(SortedPos != AllNodes.end() && "Overran node list");
6438 // Temporarily use the Node Id as scratch space for the degree count.
6439 N->setNodeId(Degree);
6443 // Visit all the nodes. As we iterate, move nodes into sorted order,
6444 // such that by the time the end is reached all nodes will be sorted.
6445 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6447 checkForCycles(N, this);
6448 // N is in sorted position, so all its uses have one less operand
6449 // that needs to be sorted.
6450 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6453 unsigned Degree = P->getNodeId();
6454 assert(Degree != 0 && "Invalid node degree");
6457 // All of P's operands are sorted, so P may sorted now.
6458 P->setNodeId(DAGSize++);
6460 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6461 assert(SortedPos != AllNodes.end() && "Overran node list");
6464 // Update P's outstanding operand count.
6465 P->setNodeId(Degree);
6468 if (I == SortedPos) {
6471 dbgs() << "Overran sorted position:\n";
6472 S->dumprFull(this); dbgs() << "\n";
6473 dbgs() << "Checking if this is due to cycles\n";
6474 checkForCycles(this, true);
6476 llvm_unreachable(nullptr);
6480 assert(SortedPos == AllNodes.end() &&
6481 "Topological sort incomplete!");
6482 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6483 "First node in topological sort is not the entry token!");
6484 assert(AllNodes.front().getNodeId() == 0 &&
6485 "First node in topological sort has non-zero id!");
6486 assert(AllNodes.front().getNumOperands() == 0 &&
6487 "First node in topological sort has operands!");
6488 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6489 "Last node in topologic sort has unexpected id!");
6490 assert(AllNodes.back().use_empty() &&
6491 "Last node in topologic sort has users!");
6492 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6496 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6497 /// value is produced by SD.
6498 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6500 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6501 SD->setHasDebugValue(true);
6503 DbgInfo->add(DB, SD, isParameter);
6506 /// TransferDbgValues - Transfer SDDbgValues.
6507 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6508 if (From == To || !From.getNode()->getHasDebugValue())
6510 SDNode *FromNode = From.getNode();
6511 SDNode *ToNode = To.getNode();
6512 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6513 SmallVector<SDDbgValue *, 2> ClonedDVs;
6514 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6516 SDDbgValue *Dbg = *I;
6517 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6519 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6520 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6521 Dbg->getDebugLoc(), Dbg->getOrder());
6522 ClonedDVs.push_back(Clone);
6525 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6526 E = ClonedDVs.end(); I != E; ++I)
6527 AddDbgValue(*I, ToNode, false);
6530 //===----------------------------------------------------------------------===//
6532 //===----------------------------------------------------------------------===//
6534 HandleSDNode::~HandleSDNode() {
6538 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6539 DebugLoc DL, const GlobalValue *GA,
6540 EVT VT, int64_t o, unsigned char TF)
6541 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6545 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6546 SDValue X, unsigned SrcAS,
6548 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6549 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6551 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6552 EVT memvt, MachineMemOperand *mmo)
6553 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6554 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6555 MMO->isNonTemporal(), MMO->isInvariant());
6556 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6557 assert(isNonTemporal() == MMO->isNonTemporal() &&
6558 "Non-temporal encoding error!");
6559 // We check here that the size of the memory operand fits within the size of
6560 // the MMO. This is because the MMO might indicate only a possible address
6561 // range instead of specifying the affected memory addresses precisely.
6562 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6565 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6566 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6567 : SDNode(Opc, Order, dl, VTs, Ops),
6568 MemoryVT(memvt), MMO(mmo) {
6569 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6570 MMO->isNonTemporal(), MMO->isInvariant());
6571 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6572 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6575 /// Profile - Gather unique data for the node.
6577 void SDNode::Profile(FoldingSetNodeID &ID) const {
6578 AddNodeIDNode(ID, this);
6583 std::vector<EVT> VTs;
6586 VTs.reserve(MVT::LAST_VALUETYPE);
6587 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6588 VTs.push_back(MVT((MVT::SimpleValueType)i));
6593 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6594 static ManagedStatic<EVTArray> SimpleVTArray;
6595 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6597 /// getValueTypeList - Return a pointer to the specified value type.
6599 const EVT *SDNode::getValueTypeList(EVT VT) {
6600 if (VT.isExtended()) {
6601 sys::SmartScopedLock<true> Lock(*VTMutex);
6602 return &(*EVTs->insert(VT).first);
6604 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6605 "Value type out of range!");
6606 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6610 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6611 /// indicated value. This method ignores uses of other values defined by this
6613 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6614 assert(Value < getNumValues() && "Bad value!");
6616 // TODO: Only iterate over uses of a given value of the node
6617 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6618 if (UI.getUse().getResNo() == Value) {
6625 // Found exactly the right number of uses?
6630 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6631 /// value. This method ignores uses of other values defined by this operation.
6632 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6633 assert(Value < getNumValues() && "Bad value!");
6635 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6636 if (UI.getUse().getResNo() == Value)
6643 /// isOnlyUserOf - Return true if this node is the only use of N.
6645 bool SDNode::isOnlyUserOf(SDNode *N) const {
6647 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6658 /// isOperand - Return true if this node is an operand of N.
6660 bool SDValue::isOperandOf(SDNode *N) const {
6661 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6662 if (*this == N->getOperand(i))
6667 bool SDNode::isOperandOf(SDNode *N) const {
6668 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6669 if (this == N->OperandList[i].getNode())
6674 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6675 /// be a chain) reaches the specified operand without crossing any
6676 /// side-effecting instructions on any chain path. In practice, this looks
6677 /// through token factors and non-volatile loads. In order to remain efficient,
6678 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6679 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6680 unsigned Depth) const {
6681 if (*this == Dest) return true;
6683 // Don't search too deeply, we just want to be able to see through
6684 // TokenFactor's etc.
6685 if (Depth == 0) return false;
6687 // If this is a token factor, all inputs to the TF happen in parallel. If any
6688 // of the operands of the TF does not reach dest, then we cannot do the xform.
6689 if (getOpcode() == ISD::TokenFactor) {
6690 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6691 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6696 // Loads don't have side effects, look through them.
6697 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6698 if (!Ld->isVolatile())
6699 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6704 /// hasPredecessor - Return true if N is a predecessor of this node.
6705 /// N is either an operand of this node, or can be reached by recursively
6706 /// traversing up the operands.
6707 /// NOTE: This is an expensive method. Use it carefully.
6708 bool SDNode::hasPredecessor(const SDNode *N) const {
6709 SmallPtrSet<const SDNode *, 32> Visited;
6710 SmallVector<const SDNode *, 16> Worklist;
6711 return hasPredecessorHelper(N, Visited, Worklist);
6715 SDNode::hasPredecessorHelper(const SDNode *N,
6716 SmallPtrSetImpl<const SDNode *> &Visited,
6717 SmallVectorImpl<const SDNode *> &Worklist) const {
6718 if (Visited.empty()) {
6719 Worklist.push_back(this);
6721 // Take a look in the visited set. If we've already encountered this node
6722 // we needn't search further.
6723 if (Visited.count(N))
6727 // Haven't visited N yet. Continue the search.
6728 while (!Worklist.empty()) {
6729 const SDNode *M = Worklist.pop_back_val();
6730 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6731 SDNode *Op = M->getOperand(i).getNode();
6732 if (Visited.insert(Op).second)
6733 Worklist.push_back(Op);
6742 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6743 assert(Num < NumOperands && "Invalid child # of SDNode!");
6744 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6747 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6748 assert(N->getNumValues() == 1 &&
6749 "Can't unroll a vector with multiple results!");
6751 EVT VT = N->getValueType(0);
6752 unsigned NE = VT.getVectorNumElements();
6753 EVT EltVT = VT.getVectorElementType();
6756 SmallVector<SDValue, 8> Scalars;
6757 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6759 // If ResNE is 0, fully unroll the vector op.
6762 else if (NE > ResNE)
6766 for (i= 0; i != NE; ++i) {
6767 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6768 SDValue Operand = N->getOperand(j);
6769 EVT OperandVT = Operand.getValueType();
6770 if (OperandVT.isVector()) {
6771 // A vector operand; extract a single element.
6772 EVT OperandEltVT = OperandVT.getVectorElementType();
6773 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6776 getConstant(i, dl, TLI->getVectorIdxTy()));
6778 // A scalar operand; just use it as is.
6779 Operands[j] = Operand;
6783 switch (N->getOpcode()) {
6785 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6788 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6795 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6796 getShiftAmountOperand(Operands[0].getValueType(),
6799 case ISD::SIGN_EXTEND_INREG:
6800 case ISD::FP_ROUND_INREG: {
6801 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6802 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6804 getValueType(ExtVT)));
6809 for (; i < ResNE; ++i)
6810 Scalars.push_back(getUNDEF(EltVT));
6812 return getNode(ISD::BUILD_VECTOR, dl,
6813 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6817 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6818 /// location that is 'Dist' units away from the location that the 'Base' load
6819 /// is loading from.
6820 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6821 unsigned Bytes, int Dist) const {
6822 if (LD->getChain() != Base->getChain())
6824 EVT VT = LD->getValueType(0);
6825 if (VT.getSizeInBits() / 8 != Bytes)
6828 SDValue Loc = LD->getOperand(1);
6829 SDValue BaseLoc = Base->getOperand(1);
6830 if (Loc.getOpcode() == ISD::FrameIndex) {
6831 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6833 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6834 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6835 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6836 int FS = MFI->getObjectSize(FI);
6837 int BFS = MFI->getObjectSize(BFI);
6838 if (FS != BFS || FS != (int)Bytes) return false;
6839 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6843 if (isBaseWithConstantOffset(Loc)) {
6844 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6845 if (Loc.getOperand(0) == BaseLoc) {
6846 // If the base location is a simple address with no offset itself, then
6847 // the second load's first add operand should be the base address.
6848 if (LocOffset == Dist * (int)Bytes)
6850 } else if (isBaseWithConstantOffset(BaseLoc)) {
6851 // The base location itself has an offset, so subtract that value from the
6852 // second load's offset before comparing to distance * size.
6854 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6855 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6856 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6861 const GlobalValue *GV1 = nullptr;
6862 const GlobalValue *GV2 = nullptr;
6863 int64_t Offset1 = 0;
6864 int64_t Offset2 = 0;
6865 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6866 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6867 if (isGA1 && isGA2 && GV1 == GV2)
6868 return Offset1 == (Offset2 + Dist*Bytes);
6873 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6874 /// it cannot be inferred.
6875 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6876 // If this is a GlobalAddress + cst, return the alignment.
6877 const GlobalValue *GV;
6878 int64_t GVOffset = 0;
6879 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6880 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6881 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6882 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6883 *TLI->getDataLayout());
6884 unsigned AlignBits = KnownZero.countTrailingOnes();
6885 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6887 return MinAlign(Align, GVOffset);
6890 // If this is a direct reference to a stack slot, use information about the
6891 // stack slot's alignment.
6892 int FrameIdx = 1 << 31;
6893 int64_t FrameOffset = 0;
6894 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6895 FrameIdx = FI->getIndex();
6896 } else if (isBaseWithConstantOffset(Ptr) &&
6897 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6899 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6900 FrameOffset = Ptr.getConstantOperandVal(1);
6903 if (FrameIdx != (1 << 31)) {
6904 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6905 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6913 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6914 /// which is split (or expanded) into two not necessarily identical pieces.
6915 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6916 // Currently all types are split in half.
6918 if (!VT.isVector()) {
6919 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6921 unsigned NumElements = VT.getVectorNumElements();
6922 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6923 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6926 return std::make_pair(LoVT, HiVT);
6929 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6931 std::pair<SDValue, SDValue>
6932 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6934 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6935 N.getValueType().getVectorNumElements() &&
6936 "More vector elements requested than available!");
6938 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6939 getConstant(0, DL, TLI->getVectorIdxTy()));
6940 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6941 getConstant(LoVT.getVectorNumElements(), DL,
6942 TLI->getVectorIdxTy()));
6943 return std::make_pair(Lo, Hi);
6946 void SelectionDAG::ExtractVectorElements(SDValue Op,
6947 SmallVectorImpl<SDValue> &Args,
6948 unsigned Start, unsigned Count) {
6949 EVT VT = Op.getValueType();
6951 Count = VT.getVectorNumElements();
6953 EVT EltVT = VT.getVectorElementType();
6954 EVT IdxTy = TLI->getVectorIdxTy();
6956 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6957 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6958 Op, getConstant(i, SL, IdxTy)));
6962 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6963 unsigned GlobalAddressSDNode::getAddressSpace() const {
6964 return getGlobal()->getType()->getAddressSpace();
6968 Type *ConstantPoolSDNode::getType() const {
6969 if (isMachineConstantPoolEntry())
6970 return Val.MachineCPVal->getType();
6971 return Val.ConstVal->getType();
6974 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6976 unsigned &SplatBitSize,
6978 unsigned MinSplatBits,
6979 bool isBigEndian) const {
6980 EVT VT = getValueType(0);
6981 assert(VT.isVector() && "Expected a vector type");
6982 unsigned sz = VT.getSizeInBits();
6983 if (MinSplatBits > sz)
6986 SplatValue = APInt(sz, 0);
6987 SplatUndef = APInt(sz, 0);
6989 // Get the bits. Bits with undefined values (when the corresponding element
6990 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6991 // in SplatValue. If any of the values are not constant, give up and return
6993 unsigned int nOps = getNumOperands();
6994 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6995 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6997 for (unsigned j = 0; j < nOps; ++j) {
6998 unsigned i = isBigEndian ? nOps-1-j : j;
6999 SDValue OpVal = getOperand(i);
7000 unsigned BitPos = j * EltBitSize;
7002 if (OpVal.getOpcode() == ISD::UNDEF)
7003 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7004 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7005 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7006 zextOrTrunc(sz) << BitPos;
7007 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7008 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7013 // The build_vector is all constants or undefs. Find the smallest element
7014 // size that splats the vector.
7016 HasAnyUndefs = (SplatUndef != 0);
7019 unsigned HalfSize = sz / 2;
7020 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7021 APInt LowValue = SplatValue.trunc(HalfSize);
7022 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7023 APInt LowUndef = SplatUndef.trunc(HalfSize);
7025 // If the two halves do not match (ignoring undef bits), stop here.
7026 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7027 MinSplatBits > HalfSize)
7030 SplatValue = HighValue | LowValue;
7031 SplatUndef = HighUndef & LowUndef;
7040 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7041 if (UndefElements) {
7042 UndefElements->clear();
7043 UndefElements->resize(getNumOperands());
7046 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7047 SDValue Op = getOperand(i);
7048 if (Op.getOpcode() == ISD::UNDEF) {
7050 (*UndefElements)[i] = true;
7051 } else if (!Splatted) {
7053 } else if (Splatted != Op) {
7059 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7060 "Can only have a splat without a constant for all undefs.");
7061 return getOperand(0);
7068 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7069 return dyn_cast_or_null<ConstantSDNode>(
7070 getSplatValue(UndefElements).getNode());
7074 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7075 return dyn_cast_or_null<ConstantFPSDNode>(
7076 getSplatValue(UndefElements).getNode());
7079 bool BuildVectorSDNode::isConstant() const {
7080 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7081 unsigned Opc = getOperand(i).getOpcode();
7082 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7088 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7089 // Find the first non-undef value in the shuffle mask.
7091 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7094 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7096 // Make sure all remaining elements are either undef or the same as the first
7098 for (int Idx = Mask[i]; i != e; ++i)
7099 if (Mask[i] >= 0 && Mask[i] != Idx)
7105 static void checkForCyclesHelper(const SDNode *N,
7106 SmallPtrSetImpl<const SDNode*> &Visited,
7107 SmallPtrSetImpl<const SDNode*> &Checked,
7108 const llvm::SelectionDAG *DAG) {
7109 // If this node has already been checked, don't check it again.
7110 if (Checked.count(N))
7113 // If a node has already been visited on this depth-first walk, reject it as
7115 if (!Visited.insert(N).second) {
7116 errs() << "Detected cycle in SelectionDAG\n";
7117 dbgs() << "Offending node:\n";
7118 N->dumprFull(DAG); dbgs() << "\n";
7122 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7123 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7130 void llvm::checkForCycles(const llvm::SDNode *N,
7131 const llvm::SelectionDAG *DAG,
7139 assert(N && "Checking nonexistent SDNode");
7140 SmallPtrSet<const SDNode*, 32> visited;
7141 SmallPtrSet<const SDNode*, 32> checked;
7142 checkForCyclesHelper(N, visited, checked, DAG);
7147 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7148 checkForCycles(DAG->getRoot().getNode(), DAG, force);