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 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1814 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1815 unsigned SrcAS, unsigned DestAS) {
1816 SDValue Ops[] = {Ptr};
1817 FoldingSetNodeID ID;
1818 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1819 ID.AddInteger(SrcAS);
1820 ID.AddInteger(DestAS);
1823 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1824 return SDValue(E, 0);
1826 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1828 VT, Ptr, SrcAS, DestAS);
1829 CSEMap.InsertNode(N, IP);
1831 return SDValue(N, 0);
1834 /// getShiftAmountOperand - Return the specified value casted to
1835 /// the target's desired shift amount type.
1836 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1837 EVT OpTy = Op.getValueType();
1838 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1839 if (OpTy == ShTy || OpTy.isVector()) return Op;
1841 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1842 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1845 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1846 /// specified value type.
1847 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1848 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1849 unsigned ByteSize = VT.getStoreSize();
1850 Type *Ty = VT.getTypeForEVT(*getContext());
1851 unsigned StackAlign =
1852 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1854 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1855 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1858 /// CreateStackTemporary - Create a stack temporary suitable for holding
1859 /// either of the specified value types.
1860 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1861 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1862 VT2.getStoreSizeInBits())/8;
1863 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1864 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1865 const DataLayout *TD = TLI->getDataLayout();
1866 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1867 TD->getPrefTypeAlignment(Ty2));
1869 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1870 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1871 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1874 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1875 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1876 // These setcc operations always fold.
1880 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1882 case ISD::SETTRUE2: {
1883 TargetLowering::BooleanContent Cnt =
1884 TLI->getBooleanContents(N1->getValueType(0));
1886 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1900 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1904 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1905 const APInt &C2 = N2C->getAPIntValue();
1906 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1907 const APInt &C1 = N1C->getAPIntValue();
1910 default: llvm_unreachable("Unknown integer setcc!");
1911 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1912 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1913 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1914 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1915 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1916 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1917 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1918 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1919 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1920 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1924 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1925 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1926 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1929 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1930 return getUNDEF(VT);
1932 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1933 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1934 return getUNDEF(VT);
1936 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1937 R==APFloat::cmpLessThan, dl, VT);
1938 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1939 return getUNDEF(VT);
1941 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1942 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1943 return getUNDEF(VT);
1945 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1946 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1947 return getUNDEF(VT);
1949 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1950 R==APFloat::cmpEqual, dl, VT);
1951 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1952 return getUNDEF(VT);
1954 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1955 R==APFloat::cmpEqual, dl, VT);
1956 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1957 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1958 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1959 R==APFloat::cmpEqual, dl, VT);
1960 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1961 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1962 R==APFloat::cmpLessThan, dl, VT);
1963 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1964 R==APFloat::cmpUnordered, dl, VT);
1965 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1966 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1969 // Ensure that the constant occurs on the RHS.
1970 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1971 MVT CompVT = N1.getValueType().getSimpleVT();
1972 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1975 return getSetCC(dl, VT, N2, N1, SwappedCond);
1979 // Could not fold it.
1983 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1984 /// use this predicate to simplify operations downstream.
1985 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1986 // This predicate is not safe for vector operations.
1987 if (Op.getValueType().isVector())
1990 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1991 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1994 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1995 /// this predicate to simplify operations downstream. Mask is known to be zero
1996 /// for bits that V cannot have.
1997 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1998 unsigned Depth) const {
1999 APInt KnownZero, KnownOne;
2000 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2001 return (KnownZero & Mask) == Mask;
2004 /// Determine which bits of Op are known to be either zero or one and return
2005 /// them in the KnownZero/KnownOne bitsets.
2006 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2007 APInt &KnownOne, unsigned Depth) const {
2008 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2010 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2012 return; // Limit search depth.
2014 APInt KnownZero2, KnownOne2;
2016 switch (Op.getOpcode()) {
2018 // We know all of the bits for a constant!
2019 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2020 KnownZero = ~KnownOne;
2023 // If either the LHS or the RHS are Zero, the result is zero.
2024 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2025 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2027 // Output known-1 bits are only known if set in both the LHS & RHS.
2028 KnownOne &= KnownOne2;
2029 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2030 KnownZero |= KnownZero2;
2033 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2034 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2036 // Output known-0 bits are only known if clear in both the LHS & RHS.
2037 KnownZero &= KnownZero2;
2038 // Output known-1 are known to be set if set in either the LHS | RHS.
2039 KnownOne |= KnownOne2;
2042 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2043 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2045 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2046 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2047 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2048 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2049 KnownZero = KnownZeroOut;
2053 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2054 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2056 // If low bits are zero in either operand, output low known-0 bits.
2057 // Also compute a conserative estimate for high known-0 bits.
2058 // More trickiness is possible, but this is sufficient for the
2059 // interesting case of alignment computation.
2060 KnownOne.clearAllBits();
2061 unsigned TrailZ = KnownZero.countTrailingOnes() +
2062 KnownZero2.countTrailingOnes();
2063 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2064 KnownZero2.countLeadingOnes(),
2065 BitWidth) - BitWidth;
2067 TrailZ = std::min(TrailZ, BitWidth);
2068 LeadZ = std::min(LeadZ, BitWidth);
2069 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2070 APInt::getHighBitsSet(BitWidth, LeadZ);
2074 // For the purposes of computing leading zeros we can conservatively
2075 // treat a udiv as a logical right shift by the power of 2 known to
2076 // be less than the denominator.
2077 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2078 unsigned LeadZ = KnownZero2.countLeadingOnes();
2080 KnownOne2.clearAllBits();
2081 KnownZero2.clearAllBits();
2082 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2083 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2084 if (RHSUnknownLeadingOnes != BitWidth)
2085 LeadZ = std::min(BitWidth,
2086 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2088 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2092 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2093 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2095 // Only known if known in both the LHS and RHS.
2096 KnownOne &= KnownOne2;
2097 KnownZero &= KnownZero2;
2099 case ISD::SELECT_CC:
2100 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2101 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2103 // Only known if known in both the LHS and RHS.
2104 KnownOne &= KnownOne2;
2105 KnownZero &= KnownZero2;
2113 if (Op.getResNo() != 1)
2115 // The boolean result conforms to getBooleanContents.
2116 // If we know the result of a setcc has the top bits zero, use this info.
2117 // We know that we have an integer-based boolean since these operations
2118 // are only available for integer.
2119 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2120 TargetLowering::ZeroOrOneBooleanContent &&
2122 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2125 // If we know the result of a setcc has the top bits zero, use this info.
2126 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2127 TargetLowering::ZeroOrOneBooleanContent &&
2129 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2132 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2133 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2134 unsigned ShAmt = SA->getZExtValue();
2136 // If the shift count is an invalid immediate, don't do anything.
2137 if (ShAmt >= BitWidth)
2140 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141 KnownZero <<= ShAmt;
2143 // low bits known zero.
2144 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2148 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2149 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2150 unsigned ShAmt = SA->getZExtValue();
2152 // If the shift count is an invalid immediate, don't do anything.
2153 if (ShAmt >= BitWidth)
2156 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2157 KnownZero = KnownZero.lshr(ShAmt);
2158 KnownOne = KnownOne.lshr(ShAmt);
2160 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2161 KnownZero |= HighBits; // High bits known zero.
2165 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2166 unsigned ShAmt = SA->getZExtValue();
2168 // If the shift count is an invalid immediate, don't do anything.
2169 if (ShAmt >= BitWidth)
2172 // If any of the demanded bits are produced by the sign extension, we also
2173 // demand the input sign bit.
2174 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2176 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2177 KnownZero = KnownZero.lshr(ShAmt);
2178 KnownOne = KnownOne.lshr(ShAmt);
2180 // Handle the sign bits.
2181 APInt SignBit = APInt::getSignBit(BitWidth);
2182 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2184 if (KnownZero.intersects(SignBit)) {
2185 KnownZero |= HighBits; // New bits are known zero.
2186 } else if (KnownOne.intersects(SignBit)) {
2187 KnownOne |= HighBits; // New bits are known one.
2191 case ISD::SIGN_EXTEND_INREG: {
2192 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2193 unsigned EBits = EVT.getScalarType().getSizeInBits();
2195 // Sign extension. Compute the demanded bits in the result that are not
2196 // present in the input.
2197 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2199 APInt InSignBit = APInt::getSignBit(EBits);
2200 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2202 // If the sign extended bits are demanded, we know that the sign
2204 InSignBit = InSignBit.zext(BitWidth);
2205 if (NewBits.getBoolValue())
2206 InputDemandedBits |= InSignBit;
2208 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2209 KnownOne &= InputDemandedBits;
2210 KnownZero &= InputDemandedBits;
2212 // If the sign bit of the input is known set or clear, then we know the
2213 // top bits of the result.
2214 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2215 KnownZero |= NewBits;
2216 KnownOne &= ~NewBits;
2217 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2218 KnownOne |= NewBits;
2219 KnownZero &= ~NewBits;
2220 } else { // Input sign bit unknown
2221 KnownZero &= ~NewBits;
2222 KnownOne &= ~NewBits;
2227 case ISD::CTTZ_ZERO_UNDEF:
2229 case ISD::CTLZ_ZERO_UNDEF:
2231 unsigned LowBits = Log2_32(BitWidth)+1;
2232 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2233 KnownOne.clearAllBits();
2237 LoadSDNode *LD = cast<LoadSDNode>(Op);
2238 // If this is a ZEXTLoad and we are looking at the loaded value.
2239 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2240 EVT VT = LD->getMemoryVT();
2241 unsigned MemBits = VT.getScalarType().getSizeInBits();
2242 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2243 } else if (const MDNode *Ranges = LD->getRanges()) {
2244 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2248 case ISD::ZERO_EXTEND: {
2249 EVT InVT = Op.getOperand(0).getValueType();
2250 unsigned InBits = InVT.getScalarType().getSizeInBits();
2251 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2252 KnownZero = KnownZero.trunc(InBits);
2253 KnownOne = KnownOne.trunc(InBits);
2254 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2255 KnownZero = KnownZero.zext(BitWidth);
2256 KnownOne = KnownOne.zext(BitWidth);
2257 KnownZero |= NewBits;
2260 case ISD::SIGN_EXTEND: {
2261 EVT InVT = Op.getOperand(0).getValueType();
2262 unsigned InBits = InVT.getScalarType().getSizeInBits();
2263 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2265 KnownZero = KnownZero.trunc(InBits);
2266 KnownOne = KnownOne.trunc(InBits);
2267 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2269 // Note if the sign bit is known to be zero or one.
2270 bool SignBitKnownZero = KnownZero.isNegative();
2271 bool SignBitKnownOne = KnownOne.isNegative();
2273 KnownZero = KnownZero.zext(BitWidth);
2274 KnownOne = KnownOne.zext(BitWidth);
2276 // If the sign bit is known zero or one, the top bits match.
2277 if (SignBitKnownZero)
2278 KnownZero |= NewBits;
2279 else if (SignBitKnownOne)
2280 KnownOne |= NewBits;
2283 case ISD::ANY_EXTEND: {
2284 EVT InVT = Op.getOperand(0).getValueType();
2285 unsigned InBits = InVT.getScalarType().getSizeInBits();
2286 KnownZero = KnownZero.trunc(InBits);
2287 KnownOne = KnownOne.trunc(InBits);
2288 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2289 KnownZero = KnownZero.zext(BitWidth);
2290 KnownOne = KnownOne.zext(BitWidth);
2293 case ISD::TRUNCATE: {
2294 EVT InVT = Op.getOperand(0).getValueType();
2295 unsigned InBits = InVT.getScalarType().getSizeInBits();
2296 KnownZero = KnownZero.zext(InBits);
2297 KnownOne = KnownOne.zext(InBits);
2298 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2299 KnownZero = KnownZero.trunc(BitWidth);
2300 KnownOne = KnownOne.trunc(BitWidth);
2303 case ISD::AssertZext: {
2304 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2305 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2306 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2307 KnownZero |= (~InMask);
2308 KnownOne &= (~KnownZero);
2312 // All bits are zero except the low bit.
2313 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2317 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2318 // We know that the top bits of C-X are clear if X contains less bits
2319 // than C (i.e. no wrap-around can happen). For example, 20-X is
2320 // positive if we can prove that X is >= 0 and < 16.
2321 if (CLHS->getAPIntValue().isNonNegative()) {
2322 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2323 // NLZ can't be BitWidth with no sign bit
2324 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2325 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2327 // If all of the MaskV bits are known to be zero, then we know the
2328 // output top bits are zero, because we now know that the output is
2330 if ((KnownZero2 & MaskV) == MaskV) {
2331 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2332 // Top bits known zero.
2333 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2341 // Output known-0 bits are known if clear or set in both the low clear bits
2342 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2343 // low 3 bits clear.
2344 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2345 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2347 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2348 KnownZeroOut = std::min(KnownZeroOut,
2349 KnownZero2.countTrailingOnes());
2351 if (Op.getOpcode() == ISD::ADD) {
2352 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2356 // With ADDE, a carry bit may be added in, so we can only use this
2357 // information if we know (at least) that the low two bits are clear. We
2358 // then return to the caller that the low bit is unknown but that other bits
2360 if (KnownZeroOut >= 2) // ADDE
2361 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2365 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2366 const APInt &RA = Rem->getAPIntValue().abs();
2367 if (RA.isPowerOf2()) {
2368 APInt LowBits = RA - 1;
2369 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2371 // The low bits of the first operand are unchanged by the srem.
2372 KnownZero = KnownZero2 & LowBits;
2373 KnownOne = KnownOne2 & LowBits;
2375 // If the first operand is non-negative or has all low bits zero, then
2376 // the upper bits are all zero.
2377 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2378 KnownZero |= ~LowBits;
2380 // If the first operand is negative and not all low bits are zero, then
2381 // the upper bits are all one.
2382 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2383 KnownOne |= ~LowBits;
2384 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2389 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2390 const APInt &RA = Rem->getAPIntValue();
2391 if (RA.isPowerOf2()) {
2392 APInt LowBits = (RA - 1);
2393 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2395 // The upper bits are all zero, the lower ones are unchanged.
2396 KnownZero = KnownZero2 | ~LowBits;
2397 KnownOne = KnownOne2 & LowBits;
2402 // Since the result is less than or equal to either operand, any leading
2403 // zero bits in either operand must also exist in the result.
2404 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2405 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2407 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2408 KnownZero2.countLeadingOnes());
2409 KnownOne.clearAllBits();
2410 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2413 case ISD::EXTRACT_ELEMENT: {
2414 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2415 const unsigned Index =
2416 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2417 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2419 // Remove low part of known bits mask
2420 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2421 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2423 // Remove high part of known bit mask
2424 KnownZero = KnownZero.trunc(BitWidth);
2425 KnownOne = KnownOne.trunc(BitWidth);
2428 case ISD::FrameIndex:
2429 case ISD::TargetFrameIndex:
2430 if (unsigned Align = InferPtrAlignment(Op)) {
2431 // The low bits are known zero if the pointer is aligned.
2432 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2438 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2441 case ISD::INTRINSIC_WO_CHAIN:
2442 case ISD::INTRINSIC_W_CHAIN:
2443 case ISD::INTRINSIC_VOID:
2444 // Allow the target to implement this method for its nodes.
2445 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2449 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2452 /// ComputeNumSignBits - Return the number of times the sign bit of the
2453 /// register is replicated into the other bits. We know that at least 1 bit
2454 /// is always equal to the sign bit (itself), but other cases can give us
2455 /// information. For example, immediately after an "SRA X, 2", we know that
2456 /// the top 3 bits are all equal to each other, so we return 3.
2457 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2458 EVT VT = Op.getValueType();
2459 assert(VT.isInteger() && "Invalid VT!");
2460 unsigned VTBits = VT.getScalarType().getSizeInBits();
2462 unsigned FirstAnswer = 1;
2465 return 1; // Limit search depth.
2467 switch (Op.getOpcode()) {
2469 case ISD::AssertSext:
2470 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2471 return VTBits-Tmp+1;
2472 case ISD::AssertZext:
2473 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2476 case ISD::Constant: {
2477 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2478 return Val.getNumSignBits();
2481 case ISD::SIGN_EXTEND:
2483 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2484 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2486 case ISD::SIGN_EXTEND_INREG:
2487 // Max of the input and what this extends.
2489 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2492 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2493 return std::max(Tmp, Tmp2);
2496 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2497 // SRA X, C -> adds C sign bits.
2498 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2499 Tmp += C->getZExtValue();
2500 if (Tmp > VTBits) Tmp = VTBits;
2504 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2505 // shl destroys sign bits.
2506 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2507 if (C->getZExtValue() >= VTBits || // Bad shift.
2508 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2509 return Tmp - C->getZExtValue();
2514 case ISD::XOR: // NOT is handled here.
2515 // Logical binary ops preserve the number of sign bits at the worst.
2516 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2518 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2519 FirstAnswer = std::min(Tmp, Tmp2);
2520 // We computed what we know about the sign bits as our first
2521 // answer. Now proceed to the generic code that uses
2522 // computeKnownBits, and pick whichever answer is better.
2527 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2528 if (Tmp == 1) return 1; // Early out.
2529 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2530 return std::min(Tmp, Tmp2);
2538 if (Op.getResNo() != 1)
2540 // The boolean result conforms to getBooleanContents. Fall through.
2541 // If setcc returns 0/-1, all bits are sign bits.
2542 // We know that we have an integer-based boolean since these operations
2543 // are only available for integer.
2544 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2545 TargetLowering::ZeroOrNegativeOneBooleanContent)
2549 // If setcc returns 0/-1, all bits are sign bits.
2550 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2551 TargetLowering::ZeroOrNegativeOneBooleanContent)
2556 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2557 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2559 // Handle rotate right by N like a rotate left by 32-N.
2560 if (Op.getOpcode() == ISD::ROTR)
2561 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2563 // If we aren't rotating out all of the known-in sign bits, return the
2564 // number that are left. This handles rotl(sext(x), 1) for example.
2565 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2566 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2570 // Add can have at most one carry bit. Thus we know that the output
2571 // is, at worst, one more bit than the inputs.
2572 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2573 if (Tmp == 1) return 1; // Early out.
2575 // Special case decrementing a value (ADD X, -1):
2576 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2577 if (CRHS->isAllOnesValue()) {
2578 APInt KnownZero, KnownOne;
2579 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2581 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2583 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2586 // If we are subtracting one from a positive number, there is no carry
2587 // out of the result.
2588 if (KnownZero.isNegative())
2592 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2593 if (Tmp2 == 1) return 1;
2594 return std::min(Tmp, Tmp2)-1;
2597 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2598 if (Tmp2 == 1) return 1;
2601 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2602 if (CLHS->isNullValue()) {
2603 APInt KnownZero, KnownOne;
2604 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2605 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2607 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2610 // If the input is known to be positive (the sign bit is known clear),
2611 // the output of the NEG has the same number of sign bits as the input.
2612 if (KnownZero.isNegative())
2615 // Otherwise, we treat this like a SUB.
2618 // Sub can have at most one carry bit. Thus we know that the output
2619 // is, at worst, one more bit than the inputs.
2620 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2621 if (Tmp == 1) return 1; // Early out.
2622 return std::min(Tmp, Tmp2)-1;
2624 // FIXME: it's tricky to do anything useful for this, but it is an important
2625 // case for targets like X86.
2627 case ISD::EXTRACT_ELEMENT: {
2628 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2629 const int BitWidth = Op.getValueType().getSizeInBits();
2631 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2633 // Get reverse index (starting from 1), Op1 value indexes elements from
2634 // little end. Sign starts at big end.
2635 const int rIndex = Items - 1 -
2636 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2638 // If the sign portion ends in our element the substraction gives correct
2639 // result. Otherwise it gives either negative or > bitwidth result
2640 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2644 // If we are looking at the loaded value of the SDNode.
2645 if (Op.getResNo() == 0) {
2646 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2647 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2648 unsigned ExtType = LD->getExtensionType();
2651 case ISD::SEXTLOAD: // '17' bits known
2652 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2653 return VTBits-Tmp+1;
2654 case ISD::ZEXTLOAD: // '16' bits known
2655 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2661 // Allow the target to implement this method for its nodes.
2662 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2663 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2664 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2665 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2666 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2667 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2670 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2671 // use this information.
2672 APInt KnownZero, KnownOne;
2673 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2676 if (KnownZero.isNegative()) { // sign bit is 0
2678 } else if (KnownOne.isNegative()) { // sign bit is 1;
2685 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2686 // the number of identical bits in the top of the input value.
2688 Mask <<= Mask.getBitWidth()-VTBits;
2689 // Return # leading zeros. We use 'min' here in case Val was zero before
2690 // shifting. We don't want to return '64' as for an i32 "0".
2691 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2694 /// isBaseWithConstantOffset - Return true if the specified operand is an
2695 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2696 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2697 /// semantics as an ADD. This handles the equivalence:
2698 /// X|Cst == X+Cst iff X&Cst = 0.
2699 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2700 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2701 !isa<ConstantSDNode>(Op.getOperand(1)))
2704 if (Op.getOpcode() == ISD::OR &&
2705 !MaskedValueIsZero(Op.getOperand(0),
2706 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2713 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2714 // If we're told that NaNs won't happen, assume they won't.
2715 if (getTarget().Options.NoNaNsFPMath)
2718 // If the value is a constant, we can obviously see if it is a NaN or not.
2719 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2720 return !C->getValueAPF().isNaN();
2722 // TODO: Recognize more cases here.
2727 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2728 // If the value is a constant, we can obviously see if it is a zero or not.
2729 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2730 return !C->isZero();
2732 // TODO: Recognize more cases here.
2733 switch (Op.getOpcode()) {
2736 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2737 return !C->isNullValue();
2744 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2745 // Check the obvious case.
2746 if (A == B) return true;
2748 // For for negative and positive zero.
2749 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2750 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2751 if (CA->isZero() && CB->isZero()) return true;
2753 // Otherwise they may not be equal.
2757 /// getNode - Gets or creates the specified node.
2759 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2760 FoldingSetNodeID ID;
2761 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2763 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2764 return SDValue(E, 0);
2766 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2767 DL.getDebugLoc(), getVTList(VT));
2768 CSEMap.InsertNode(N, IP);
2771 return SDValue(N, 0);
2774 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2775 EVT VT, SDValue Operand) {
2776 // Constant fold unary operations with an integer constant operand. Even
2777 // opaque constant will be folded, because the folding of unary operations
2778 // doesn't create new constants with different values. Nevertheless, the
2779 // opaque flag is preserved during folding to prevent future folding with
2781 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2782 const APInt &Val = C->getAPIntValue();
2785 case ISD::SIGN_EXTEND:
2786 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2787 C->isTargetOpcode(), C->isOpaque());
2788 case ISD::ANY_EXTEND:
2789 case ISD::ZERO_EXTEND:
2791 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2792 C->isTargetOpcode(), C->isOpaque());
2793 case ISD::UINT_TO_FP:
2794 case ISD::SINT_TO_FP: {
2795 APFloat apf(EVTToAPFloatSemantics(VT),
2796 APInt::getNullValue(VT.getSizeInBits()));
2797 (void)apf.convertFromAPInt(Val,
2798 Opcode==ISD::SINT_TO_FP,
2799 APFloat::rmNearestTiesToEven);
2800 return getConstantFP(apf, DL, VT);
2803 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2804 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2805 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2806 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2807 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2808 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2811 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2814 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2817 case ISD::CTLZ_ZERO_UNDEF:
2818 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2821 case ISD::CTTZ_ZERO_UNDEF:
2822 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2827 // Constant fold unary operations with a floating point constant operand.
2828 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2829 APFloat V = C->getValueAPF(); // make copy
2833 return getConstantFP(V, DL, VT);
2836 return getConstantFP(V, DL, VT);
2838 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2839 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2840 return getConstantFP(V, DL, VT);
2844 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2845 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2846 return getConstantFP(V, DL, VT);
2850 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2851 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2852 return getConstantFP(V, DL, VT);
2855 case ISD::FP_EXTEND: {
2857 // This can return overflow, underflow, or inexact; we don't care.
2858 // FIXME need to be more flexible about rounding mode.
2859 (void)V.convert(EVTToAPFloatSemantics(VT),
2860 APFloat::rmNearestTiesToEven, &ignored);
2861 return getConstantFP(V, DL, VT);
2863 case ISD::FP_TO_SINT:
2864 case ISD::FP_TO_UINT: {
2867 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2868 // FIXME need to be more flexible about rounding mode.
2869 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2870 Opcode==ISD::FP_TO_SINT,
2871 APFloat::rmTowardZero, &ignored);
2872 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2874 APInt api(VT.getSizeInBits(), x);
2875 return getConstant(api, DL, VT);
2878 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2879 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2880 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2881 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2882 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2883 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2888 // Constant fold unary operations with a vector integer or float operand.
2889 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2890 if (BV->isConstant()) {
2893 // FIXME: Entirely reasonable to perform folding of other unary
2894 // operations here as the need arises.
2901 case ISD::FP_EXTEND:
2902 case ISD::FP_TO_SINT:
2903 case ISD::FP_TO_UINT:
2905 case ISD::UINT_TO_FP:
2906 case ISD::SINT_TO_FP: {
2907 EVT SVT = VT.getScalarType();
2908 EVT InVT = BV->getValueType(0);
2909 EVT InSVT = InVT.getScalarType();
2911 // Find legal integer scalar type for constant promotion and
2912 // ensure that its scalar size is at least as large as source.
2914 if (SVT.isInteger()) {
2915 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2916 if (LegalSVT.bitsLT(SVT)) break;
2919 // Let the above scalar folding handle the folding of each element.
2920 SmallVector<SDValue, 8> Ops;
2921 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2922 SDValue OpN = BV->getOperand(i);
2923 EVT OpVT = OpN.getValueType();
2925 // Build vector (integer) scalar operands may need implicit
2926 // truncation - do this before constant folding.
2927 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2928 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2930 OpN = getNode(Opcode, DL, SVT, OpN);
2932 // Legalize the (integer) scalar constant if necessary.
2933 if (LegalSVT != SVT)
2934 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2936 if (OpN.getOpcode() != ISD::UNDEF &&
2937 OpN.getOpcode() != ISD::Constant &&
2938 OpN.getOpcode() != ISD::ConstantFP)
2942 if (Ops.size() == VT.getVectorNumElements())
2943 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2950 unsigned OpOpcode = Operand.getNode()->getOpcode();
2952 case ISD::TokenFactor:
2953 case ISD::MERGE_VALUES:
2954 case ISD::CONCAT_VECTORS:
2955 return Operand; // Factor, merge or concat of one node? No need.
2956 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2957 case ISD::FP_EXTEND:
2958 assert(VT.isFloatingPoint() &&
2959 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2960 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2961 assert((!VT.isVector() ||
2962 VT.getVectorNumElements() ==
2963 Operand.getValueType().getVectorNumElements()) &&
2964 "Vector element count mismatch!");
2965 if (Operand.getOpcode() == ISD::UNDEF)
2966 return getUNDEF(VT);
2968 case ISD::SIGN_EXTEND:
2969 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2970 "Invalid SIGN_EXTEND!");
2971 if (Operand.getValueType() == VT) return Operand; // noop extension
2972 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2973 "Invalid sext node, dst < src!");
2974 assert((!VT.isVector() ||
2975 VT.getVectorNumElements() ==
2976 Operand.getValueType().getVectorNumElements()) &&
2977 "Vector element count mismatch!");
2978 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2979 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2980 else if (OpOpcode == ISD::UNDEF)
2981 // sext(undef) = 0, because the top bits will all be the same.
2982 return getConstant(0, DL, VT);
2984 case ISD::ZERO_EXTEND:
2985 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2986 "Invalid ZERO_EXTEND!");
2987 if (Operand.getValueType() == VT) return Operand; // noop extension
2988 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2989 "Invalid zext node, dst < src!");
2990 assert((!VT.isVector() ||
2991 VT.getVectorNumElements() ==
2992 Operand.getValueType().getVectorNumElements()) &&
2993 "Vector element count mismatch!");
2994 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2995 return getNode(ISD::ZERO_EXTEND, DL, VT,
2996 Operand.getNode()->getOperand(0));
2997 else if (OpOpcode == ISD::UNDEF)
2998 // zext(undef) = 0, because the top bits will be zero.
2999 return getConstant(0, DL, VT);
3001 case ISD::ANY_EXTEND:
3002 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3003 "Invalid ANY_EXTEND!");
3004 if (Operand.getValueType() == VT) return Operand; // noop extension
3005 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3006 "Invalid anyext node, dst < src!");
3007 assert((!VT.isVector() ||
3008 VT.getVectorNumElements() ==
3009 Operand.getValueType().getVectorNumElements()) &&
3010 "Vector element count mismatch!");
3012 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3013 OpOpcode == ISD::ANY_EXTEND)
3014 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3015 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3016 else if (OpOpcode == ISD::UNDEF)
3017 return getUNDEF(VT);
3019 // (ext (trunx x)) -> x
3020 if (OpOpcode == ISD::TRUNCATE) {
3021 SDValue OpOp = Operand.getNode()->getOperand(0);
3022 if (OpOp.getValueType() == VT)
3027 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3028 "Invalid TRUNCATE!");
3029 if (Operand.getValueType() == VT) return Operand; // noop truncate
3030 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3031 "Invalid truncate node, src < dst!");
3032 assert((!VT.isVector() ||
3033 VT.getVectorNumElements() ==
3034 Operand.getValueType().getVectorNumElements()) &&
3035 "Vector element count mismatch!");
3036 if (OpOpcode == ISD::TRUNCATE)
3037 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3038 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3039 OpOpcode == ISD::ANY_EXTEND) {
3040 // If the source is smaller than the dest, we still need an extend.
3041 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3042 .bitsLT(VT.getScalarType()))
3043 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3044 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3045 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3046 return Operand.getNode()->getOperand(0);
3048 if (OpOpcode == ISD::UNDEF)
3049 return getUNDEF(VT);
3052 // Basic sanity checking.
3053 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3054 && "Cannot BITCAST between types of different sizes!");
3055 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3056 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3057 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3058 if (OpOpcode == ISD::UNDEF)
3059 return getUNDEF(VT);
3061 case ISD::SCALAR_TO_VECTOR:
3062 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3063 (VT.getVectorElementType() == Operand.getValueType() ||
3064 (VT.getVectorElementType().isInteger() &&
3065 Operand.getValueType().isInteger() &&
3066 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3067 "Illegal SCALAR_TO_VECTOR node!");
3068 if (OpOpcode == ISD::UNDEF)
3069 return getUNDEF(VT);
3070 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3071 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3072 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3073 Operand.getConstantOperandVal(1) == 0 &&
3074 Operand.getOperand(0).getValueType() == VT)
3075 return Operand.getOperand(0);
3078 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3079 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3080 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3081 Operand.getNode()->getOperand(0));
3082 if (OpOpcode == ISD::FNEG) // --X -> X
3083 return Operand.getNode()->getOperand(0);
3086 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3087 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3092 SDVTList VTs = getVTList(VT);
3093 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3094 FoldingSetNodeID ID;
3095 SDValue Ops[1] = { Operand };
3096 AddNodeIDNode(ID, Opcode, VTs, Ops);
3098 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3099 return SDValue(E, 0);
3101 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3102 DL.getDebugLoc(), VTs, Operand);
3103 CSEMap.InsertNode(N, IP);
3105 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3106 DL.getDebugLoc(), VTs, Operand);
3110 return SDValue(N, 0);
3113 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3116 case ISD::ADD: return std::make_pair(C1 + C2, true);
3117 case ISD::SUB: return std::make_pair(C1 - C2, true);
3118 case ISD::MUL: return std::make_pair(C1 * C2, true);
3119 case ISD::AND: return std::make_pair(C1 & C2, true);
3120 case ISD::OR: return std::make_pair(C1 | C2, true);
3121 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3122 case ISD::SHL: return std::make_pair(C1 << C2, true);
3123 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3124 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3125 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3126 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3128 if (!C2.getBoolValue())
3130 return std::make_pair(C1.udiv(C2), true);
3132 if (!C2.getBoolValue())
3134 return std::make_pair(C1.urem(C2), true);
3136 if (!C2.getBoolValue())
3138 return std::make_pair(C1.sdiv(C2), true);
3140 if (!C2.getBoolValue())
3142 return std::make_pair(C1.srem(C2), true);
3144 return std::make_pair(APInt(1, 0), false);
3147 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3148 const ConstantSDNode *Cst1,
3149 const ConstantSDNode *Cst2) {
3150 if (Cst1->isOpaque() || Cst2->isOpaque())
3153 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3154 Cst2->getAPIntValue());
3157 return getConstant(Folded.first, DL, VT);
3160 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3161 SDNode *Cst1, SDNode *Cst2) {
3162 // If the opcode is a target-specific ISD node, there's nothing we can
3163 // do here and the operand rules may not line up with the below, so
3165 if (Opcode >= ISD::BUILTIN_OP_END)
3168 // Handle the case of two scalars.
3169 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3170 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3171 if (SDValue Folded =
3172 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3175 SmallVector<SDValue, 4> Outputs;
3176 // We may have a vector type but a scalar result. Create a splat.
3177 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3178 // Build a big vector out of the scalar elements we generated.
3179 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3186 // For vectors extract each constant element into Inputs so we can constant
3187 // fold them individually.
3188 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3189 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3193 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3195 EVT SVT = VT.getScalarType();
3196 SmallVector<SDValue, 4> Outputs;
3197 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3198 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3199 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3200 if (!V1 || !V2) // Not a constant, bail.
3203 if (V1->isOpaque() || V2->isOpaque())
3206 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3207 // FIXME: This is valid and could be handled by truncating the APInts.
3208 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3211 // Fold one vector element.
3212 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3213 V2->getAPIntValue());
3216 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3219 assert(VT.getVectorNumElements() == Outputs.size() &&
3220 "Vector size mismatch!");
3222 // We may have a vector type but a scalar result. Create a splat.
3223 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3225 // Build a big vector out of the scalar elements we generated.
3226 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3229 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3230 SDValue N2, bool nuw, bool nsw, bool exact) {
3231 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3232 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3235 case ISD::TokenFactor:
3236 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3237 N2.getValueType() == MVT::Other && "Invalid token factor!");
3238 // Fold trivial token factors.
3239 if (N1.getOpcode() == ISD::EntryToken) return N2;
3240 if (N2.getOpcode() == ISD::EntryToken) return N1;
3241 if (N1 == N2) return N1;
3243 case ISD::CONCAT_VECTORS:
3244 // Concat of UNDEFs is UNDEF.
3245 if (N1.getOpcode() == ISD::UNDEF &&
3246 N2.getOpcode() == ISD::UNDEF)
3247 return getUNDEF(VT);
3249 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3250 // one big BUILD_VECTOR.
3251 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3252 N2.getOpcode() == ISD::BUILD_VECTOR) {
3253 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3254 N1.getNode()->op_end());
3255 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3257 // BUILD_VECTOR requires all inputs to be of the same type, find the
3258 // maximum type and extend them all.
3259 EVT SVT = VT.getScalarType();
3260 for (SDValue Op : Elts)
3261 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3262 if (SVT.bitsGT(VT.getScalarType()))
3263 for (SDValue &Op : Elts)
3264 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3265 ? getZExtOrTrunc(Op, DL, SVT)
3266 : getSExtOrTrunc(Op, DL, SVT);
3268 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3272 assert(VT.isInteger() && "This operator does not apply to FP types!");
3273 assert(N1.getValueType() == N2.getValueType() &&
3274 N1.getValueType() == VT && "Binary operator types must match!");
3275 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3276 // worth handling here.
3277 if (N2C && N2C->isNullValue())
3279 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3286 assert(VT.isInteger() && "This operator does not apply to FP types!");
3287 assert(N1.getValueType() == N2.getValueType() &&
3288 N1.getValueType() == VT && "Binary operator types must match!");
3289 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3290 // it's worth handling here.
3291 if (N2C && N2C->isNullValue())
3301 assert(VT.isInteger() && "This operator does not apply to FP types!");
3302 assert(N1.getValueType() == N2.getValueType() &&
3303 N1.getValueType() == VT && "Binary operator types must match!");
3310 if (getTarget().Options.UnsafeFPMath) {
3311 if (Opcode == ISD::FADD) {
3313 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3314 if (CFP->getValueAPF().isZero())
3317 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3318 if (CFP->getValueAPF().isZero())
3320 } else if (Opcode == ISD::FSUB) {
3322 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3323 if (CFP->getValueAPF().isZero())
3325 } else if (Opcode == ISD::FMUL) {
3326 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3329 // If the first operand isn't the constant, try the second
3331 CFP = dyn_cast<ConstantFPSDNode>(N2);
3338 return SDValue(CFP,0);
3340 if (CFP->isExactlyValue(1.0))
3345 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3346 assert(N1.getValueType() == N2.getValueType() &&
3347 N1.getValueType() == VT && "Binary operator types must match!");
3349 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3350 assert(N1.getValueType() == VT &&
3351 N1.getValueType().isFloatingPoint() &&
3352 N2.getValueType().isFloatingPoint() &&
3353 "Invalid FCOPYSIGN!");
3360 assert(VT == N1.getValueType() &&
3361 "Shift operators return type must be the same as their first arg");
3362 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3363 "Shifts only work on integers");
3364 assert((!VT.isVector() || VT == N2.getValueType()) &&
3365 "Vector shift amounts must be in the same as their first arg");
3366 // Verify that the shift amount VT is bit enough to hold valid shift
3367 // amounts. This catches things like trying to shift an i1024 value by an
3368 // i8, which is easy to fall into in generic code that uses
3369 // TLI.getShiftAmount().
3370 assert(N2.getValueType().getSizeInBits() >=
3371 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3372 "Invalid use of small shift amount with oversized value!");
3374 // Always fold shifts of i1 values so the code generator doesn't need to
3375 // handle them. Since we know the size of the shift has to be less than the
3376 // size of the value, the shift/rotate count is guaranteed to be zero.
3379 if (N2C && N2C->isNullValue())
3382 case ISD::FP_ROUND_INREG: {
3383 EVT EVT = cast<VTSDNode>(N2)->getVT();
3384 assert(VT == N1.getValueType() && "Not an inreg round!");
3385 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3386 "Cannot FP_ROUND_INREG integer types");
3387 assert(EVT.isVector() == VT.isVector() &&
3388 "FP_ROUND_INREG type should be vector iff the operand "
3390 assert((!EVT.isVector() ||
3391 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3392 "Vector element counts must match in FP_ROUND_INREG");
3393 assert(EVT.bitsLE(VT) && "Not rounding down!");
3395 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3399 assert(VT.isFloatingPoint() &&
3400 N1.getValueType().isFloatingPoint() &&
3401 VT.bitsLE(N1.getValueType()) &&
3402 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3403 if (N1.getValueType() == VT) return N1; // noop conversion.
3405 case ISD::AssertSext:
3406 case ISD::AssertZext: {
3407 EVT EVT = cast<VTSDNode>(N2)->getVT();
3408 assert(VT == N1.getValueType() && "Not an inreg extend!");
3409 assert(VT.isInteger() && EVT.isInteger() &&
3410 "Cannot *_EXTEND_INREG FP types");
3411 assert(!EVT.isVector() &&
3412 "AssertSExt/AssertZExt type should be the vector element type "
3413 "rather than the vector type!");
3414 assert(EVT.bitsLE(VT) && "Not extending!");
3415 if (VT == EVT) return N1; // noop assertion.
3418 case ISD::SIGN_EXTEND_INREG: {
3419 EVT EVT = cast<VTSDNode>(N2)->getVT();
3420 assert(VT == N1.getValueType() && "Not an inreg extend!");
3421 assert(VT.isInteger() && EVT.isInteger() &&
3422 "Cannot *_EXTEND_INREG FP types");
3423 assert(EVT.isVector() == VT.isVector() &&
3424 "SIGN_EXTEND_INREG type should be vector iff the operand "
3426 assert((!EVT.isVector() ||
3427 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3428 "Vector element counts must match in SIGN_EXTEND_INREG");
3429 assert(EVT.bitsLE(VT) && "Not extending!");
3430 if (EVT == VT) return N1; // Not actually extending
3432 auto SignExtendInReg = [&](APInt Val) {
3433 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3434 Val <<= Val.getBitWidth() - FromBits;
3435 Val = Val.ashr(Val.getBitWidth() - FromBits);
3436 return getConstant(Val, DL, VT.getScalarType());
3440 APInt Val = N1C->getAPIntValue();
3441 return SignExtendInReg(Val);
3443 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3444 SmallVector<SDValue, 8> Ops;
3445 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3446 SDValue Op = N1.getOperand(i);
3447 if (Op.getValueType() != VT.getScalarType()) break;
3448 if (Op.getOpcode() == ISD::UNDEF) {
3452 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3453 APInt Val = C->getAPIntValue();
3454 Ops.push_back(SignExtendInReg(Val));
3459 if (Ops.size() == VT.getVectorNumElements())
3460 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3464 case ISD::EXTRACT_VECTOR_ELT:
3465 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3466 if (N1.getOpcode() == ISD::UNDEF)
3467 return getUNDEF(VT);
3469 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3470 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3471 return getUNDEF(VT);
3473 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3474 // expanding copies of large vectors from registers.
3476 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3477 N1.getNumOperands() > 0) {
3479 N1.getOperand(0).getValueType().getVectorNumElements();
3480 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3481 N1.getOperand(N2C->getZExtValue() / Factor),
3482 getConstant(N2C->getZExtValue() % Factor, DL,
3483 N2.getValueType()));
3486 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3487 // expanding large vector constants.
3488 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3489 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3491 if (VT != Elt.getValueType())
3492 // If the vector element type is not legal, the BUILD_VECTOR operands
3493 // are promoted and implicitly truncated, and the result implicitly
3494 // extended. Make that explicit here.
3495 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3500 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3501 // operations are lowered to scalars.
3502 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3503 // If the indices are the same, return the inserted element else
3504 // if the indices are known different, extract the element from
3505 // the original vector.
3506 SDValue N1Op2 = N1.getOperand(2);
3507 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3509 if (N1Op2C && N2C) {
3510 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3511 if (VT == N1.getOperand(1).getValueType())
3512 return N1.getOperand(1);
3514 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3517 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3521 case ISD::EXTRACT_ELEMENT:
3522 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3523 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3524 (N1.getValueType().isInteger() == VT.isInteger()) &&
3525 N1.getValueType() != VT &&
3526 "Wrong types for EXTRACT_ELEMENT!");
3528 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3529 // 64-bit integers into 32-bit parts. Instead of building the extract of
3530 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3531 if (N1.getOpcode() == ISD::BUILD_PAIR)
3532 return N1.getOperand(N2C->getZExtValue());
3534 // EXTRACT_ELEMENT of a constant int is also very common.
3535 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3536 unsigned ElementSize = VT.getSizeInBits();
3537 unsigned Shift = ElementSize * N2C->getZExtValue();
3538 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3539 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3542 case ISD::EXTRACT_SUBVECTOR: {
3544 if (VT.isSimple() && N1.getValueType().isSimple()) {
3545 assert(VT.isVector() && N1.getValueType().isVector() &&
3546 "Extract subvector VTs must be a vectors!");
3547 assert(VT.getVectorElementType() ==
3548 N1.getValueType().getVectorElementType() &&
3549 "Extract subvector VTs must have the same element type!");
3550 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3551 "Extract subvector must be from larger vector to smaller vector!");
3553 if (isa<ConstantSDNode>(Index.getNode())) {
3554 assert((VT.getVectorNumElements() +
3555 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3556 <= N1.getValueType().getVectorNumElements())
3557 && "Extract subvector overflow!");
3560 // Trivial extraction.
3561 if (VT.getSimpleVT() == N1.getSimpleValueType())
3568 // Perform trivial constant folding.
3570 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3573 // Canonicalize constant to RHS if commutative.
3574 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3575 std::swap(N1C, N2C);
3579 // Constant fold FP operations.
3580 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3581 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3582 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3584 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3585 // Canonicalize constant to RHS if commutative.
3586 std::swap(N1CFP, N2CFP);
3589 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3590 APFloat::opStatus s;
3593 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3594 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3595 return getConstantFP(V1, DL, VT);
3598 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3599 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3600 return getConstantFP(V1, DL, VT);
3603 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3604 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3605 return getConstantFP(V1, DL, VT);
3608 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3609 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3610 s!=APFloat::opDivByZero)) {
3611 return getConstantFP(V1, DL, VT);
3615 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3616 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3617 s!=APFloat::opDivByZero)) {
3618 return getConstantFP(V1, DL, VT);
3621 case ISD::FCOPYSIGN:
3623 return getConstantFP(V1, DL, VT);
3628 if (Opcode == ISD::FP_ROUND) {
3629 APFloat V = N1CFP->getValueAPF(); // make copy
3631 // This can return overflow, underflow, or inexact; we don't care.
3632 // FIXME need to be more flexible about rounding mode.
3633 (void)V.convert(EVTToAPFloatSemantics(VT),
3634 APFloat::rmNearestTiesToEven, &ignored);
3635 return getConstantFP(V, DL, VT);
3639 // Canonicalize an UNDEF to the RHS, even over a constant.
3640 if (N1.getOpcode() == ISD::UNDEF) {
3641 if (isCommutativeBinOp(Opcode)) {
3645 case ISD::FP_ROUND_INREG:
3646 case ISD::SIGN_EXTEND_INREG:
3652 return N1; // fold op(undef, arg2) -> undef
3660 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3661 // For vectors, we can't easily build an all zero vector, just return
3668 // Fold a bunch of operators when the RHS is undef.
3669 if (N2.getOpcode() == ISD::UNDEF) {
3672 if (N1.getOpcode() == ISD::UNDEF)
3673 // Handle undef ^ undef -> 0 special case. This is a common
3675 return getConstant(0, DL, VT);
3685 return N2; // fold op(arg1, undef) -> undef
3691 if (getTarget().Options.UnsafeFPMath)
3699 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3700 // For vectors, we can't easily build an all zero vector, just return
3705 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3706 // For vectors, we can't easily build an all one vector, just return
3714 // Memoize this node if possible.
3716 SDVTList VTs = getVTList(VT);
3717 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3718 if (VT != MVT::Glue) {
3719 SDValue Ops[] = {N1, N2};
3720 FoldingSetNodeID ID;
3721 AddNodeIDNode(ID, Opcode, VTs, Ops);
3723 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3725 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3726 return SDValue(E, 0);
3728 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3730 CSEMap.InsertNode(N, IP);
3732 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3736 return SDValue(N, 0);
3739 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3740 SDValue N1, SDValue N2, SDValue N3) {
3741 // Perform various simplifications.
3742 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3745 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3746 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3747 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3748 if (N1CFP && N2CFP && N3CFP) {
3749 APFloat V1 = N1CFP->getValueAPF();
3750 const APFloat &V2 = N2CFP->getValueAPF();
3751 const APFloat &V3 = N3CFP->getValueAPF();
3752 APFloat::opStatus s =
3753 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3754 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3755 return getConstantFP(V1, DL, VT);
3759 case ISD::CONCAT_VECTORS:
3760 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3761 // one big BUILD_VECTOR.
3762 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3763 N2.getOpcode() == ISD::BUILD_VECTOR &&
3764 N3.getOpcode() == ISD::BUILD_VECTOR) {
3765 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3766 N1.getNode()->op_end());
3767 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3768 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3769 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3773 // Use FoldSetCC to simplify SETCC's.
3774 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3775 if (Simp.getNode()) return Simp;
3780 if (N1C->getZExtValue())
3781 return N2; // select true, X, Y -> X
3782 return N3; // select false, X, Y -> Y
3785 if (N2 == N3) return N2; // select C, X, X -> X
3787 case ISD::VECTOR_SHUFFLE:
3788 llvm_unreachable("should use getVectorShuffle constructor!");
3789 case ISD::INSERT_SUBVECTOR: {
3791 if (VT.isSimple() && N1.getValueType().isSimple()
3792 && N2.getValueType().isSimple()) {
3793 assert(VT.isVector() && N1.getValueType().isVector() &&
3794 N2.getValueType().isVector() &&
3795 "Insert subvector VTs must be a vectors");
3796 assert(VT == N1.getValueType() &&
3797 "Dest and insert subvector source types must match!");
3798 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3799 "Insert subvector must be from smaller vector to larger vector!");
3800 if (isa<ConstantSDNode>(Index.getNode())) {
3801 assert((N2.getValueType().getVectorNumElements() +
3802 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3803 <= VT.getVectorNumElements())
3804 && "Insert subvector overflow!");
3807 // Trivial insertion.
3808 if (VT.getSimpleVT() == N2.getSimpleValueType())
3814 // Fold bit_convert nodes from a type to themselves.
3815 if (N1.getValueType() == VT)
3820 // Memoize node if it doesn't produce a flag.
3822 SDVTList VTs = getVTList(VT);
3823 if (VT != MVT::Glue) {
3824 SDValue Ops[] = { N1, N2, N3 };
3825 FoldingSetNodeID ID;
3826 AddNodeIDNode(ID, Opcode, VTs, Ops);
3828 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3829 return SDValue(E, 0);
3831 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3832 DL.getDebugLoc(), VTs, N1, N2, N3);
3833 CSEMap.InsertNode(N, IP);
3835 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3836 DL.getDebugLoc(), VTs, N1, N2, N3);
3840 return SDValue(N, 0);
3843 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3844 SDValue N1, SDValue N2, SDValue N3,
3846 SDValue Ops[] = { N1, N2, N3, N4 };
3847 return getNode(Opcode, DL, VT, Ops);
3850 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3851 SDValue N1, SDValue N2, SDValue N3,
3852 SDValue N4, SDValue N5) {
3853 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3854 return getNode(Opcode, DL, VT, Ops);
3857 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3858 /// the incoming stack arguments to be loaded from the stack.
3859 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3860 SmallVector<SDValue, 8> ArgChains;
3862 // Include the original chain at the beginning of the list. When this is
3863 // used by target LowerCall hooks, this helps legalize find the
3864 // CALLSEQ_BEGIN node.
3865 ArgChains.push_back(Chain);
3867 // Add a chain value for each stack argument.
3868 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3869 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3870 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3871 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3872 if (FI->getIndex() < 0)
3873 ArgChains.push_back(SDValue(L, 1));
3875 // Build a tokenfactor for all the chains.
3876 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3879 /// getMemsetValue - Vectorized representation of the memset value
3881 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3883 assert(Value.getOpcode() != ISD::UNDEF);
3885 unsigned NumBits = VT.getScalarType().getSizeInBits();
3886 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3887 assert(C->getAPIntValue().getBitWidth() == 8);
3888 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3890 return DAG.getConstant(Val, dl, VT);
3891 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3895 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3896 EVT IntVT = VT.getScalarType();
3897 if (!IntVT.isInteger())
3898 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3900 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3902 // Use a multiplication with 0x010101... to extend the input to the
3904 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3905 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3906 DAG.getConstant(Magic, dl, IntVT));
3909 if (VT != Value.getValueType() && !VT.isInteger())
3910 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3911 if (VT != Value.getValueType()) {
3912 assert(VT.getVectorElementType() == Value.getValueType() &&
3913 "value type should be one vector element here");
3914 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3915 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3921 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3922 /// used when a memcpy is turned into a memset when the source is a constant
3924 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3925 const TargetLowering &TLI, StringRef Str) {
3926 // Handle vector with all elements zero.
3929 return DAG.getConstant(0, dl, VT);
3930 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3931 return DAG.getConstantFP(0.0, dl, VT);
3932 else if (VT.isVector()) {
3933 unsigned NumElts = VT.getVectorNumElements();
3934 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3935 return DAG.getNode(ISD::BITCAST, dl, VT,
3936 DAG.getConstant(0, dl,
3937 EVT::getVectorVT(*DAG.getContext(),
3940 llvm_unreachable("Expected type!");
3943 assert(!VT.isVector() && "Can't handle vector type here!");
3944 unsigned NumVTBits = VT.getSizeInBits();
3945 unsigned NumVTBytes = NumVTBits / 8;
3946 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3948 APInt Val(NumVTBits, 0);
3949 if (TLI.isLittleEndian()) {
3950 for (unsigned i = 0; i != NumBytes; ++i)
3951 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3953 for (unsigned i = 0; i != NumBytes; ++i)
3954 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3957 // If the "cost" of materializing the integer immediate is less than the cost
3958 // of a load, then it is cost effective to turn the load into the immediate.
3959 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3960 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3961 return DAG.getConstant(Val, dl, VT);
3962 return SDValue(nullptr, 0);
3965 /// getMemBasePlusOffset - Returns base and offset node for the
3967 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3968 SelectionDAG &DAG) {
3969 EVT VT = Base.getValueType();
3970 return DAG.getNode(ISD::ADD, dl,
3971 VT, Base, DAG.getConstant(Offset, dl, VT));
3974 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3976 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3977 unsigned SrcDelta = 0;
3978 GlobalAddressSDNode *G = nullptr;
3979 if (Src.getOpcode() == ISD::GlobalAddress)
3980 G = cast<GlobalAddressSDNode>(Src);
3981 else if (Src.getOpcode() == ISD::ADD &&
3982 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3983 Src.getOperand(1).getOpcode() == ISD::Constant) {
3984 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3985 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3990 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3993 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3994 /// to replace the memset / memcpy. Return true if the number of memory ops
3995 /// is below the threshold. It returns the types of the sequence of
3996 /// memory ops to perform memset / memcpy by reference.
3997 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3998 unsigned Limit, uint64_t Size,
3999 unsigned DstAlign, unsigned SrcAlign,
4005 const TargetLowering &TLI) {
4006 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4007 "Expecting memcpy / memset source to meet alignment requirement!");
4008 // If 'SrcAlign' is zero, that means the memory operation does not need to
4009 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4010 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4011 // is the specified alignment of the memory operation. If it is zero, that
4012 // means it's possible to change the alignment of the destination.
4013 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4014 // not need to be loaded.
4015 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4016 IsMemset, ZeroMemset, MemcpyStrSrc,
4017 DAG.getMachineFunction());
4019 if (VT == MVT::Other) {
4021 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4022 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4023 VT = TLI.getPointerTy();
4025 switch (DstAlign & 7) {
4026 case 0: VT = MVT::i64; break;
4027 case 4: VT = MVT::i32; break;
4028 case 2: VT = MVT::i16; break;
4029 default: VT = MVT::i8; break;
4034 while (!TLI.isTypeLegal(LVT))
4035 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4036 assert(LVT.isInteger());
4042 unsigned NumMemOps = 0;
4044 unsigned VTSize = VT.getSizeInBits() / 8;
4045 while (VTSize > Size) {
4046 // For now, only use non-vector load / store's for the left-over pieces.
4051 if (VT.isVector() || VT.isFloatingPoint()) {
4052 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4053 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4054 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4056 else if (NewVT == MVT::i64 &&
4057 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4058 TLI.isSafeMemOpType(MVT::f64)) {
4059 // i64 is usually not legal on 32-bit targets, but f64 may be.
4067 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4068 if (NewVT == MVT::i8)
4070 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4072 NewVTSize = NewVT.getSizeInBits() / 8;
4074 // If the new VT cannot cover all of the remaining bits, then consider
4075 // issuing a (or a pair of) unaligned and overlapping load / store.
4076 // FIXME: Only does this for 64-bit or more since we don't have proper
4077 // cost model for unaligned load / store.
4080 if (NumMemOps && AllowOverlap &&
4081 VTSize >= 8 && NewVTSize < Size &&
4082 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4090 if (++NumMemOps > Limit)
4093 MemOps.push_back(VT);
4100 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4101 SDValue Chain, SDValue Dst,
4102 SDValue Src, uint64_t Size,
4103 unsigned Align, bool isVol,
4105 MachinePointerInfo DstPtrInfo,
4106 MachinePointerInfo SrcPtrInfo) {
4107 // Turn a memcpy of undef to nop.
4108 if (Src.getOpcode() == ISD::UNDEF)
4111 // Expand memcpy to a series of load and store ops if the size operand falls
4112 // below a certain threshold.
4113 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4114 // rather than maybe a humongous number of loads and stores.
4115 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4116 std::vector<EVT> MemOps;
4117 bool DstAlignCanChange = false;
4118 MachineFunction &MF = DAG.getMachineFunction();
4119 MachineFrameInfo *MFI = MF.getFrameInfo();
4120 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4121 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4122 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4123 DstAlignCanChange = true;
4124 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4125 if (Align > SrcAlign)
4128 bool CopyFromStr = isMemSrcFromString(Src, Str);
4129 bool isZeroStr = CopyFromStr && Str.empty();
4130 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4132 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4133 (DstAlignCanChange ? 0 : Align),
4134 (isZeroStr ? 0 : SrcAlign),
4135 false, false, CopyFromStr, true, DAG, TLI))
4138 if (DstAlignCanChange) {
4139 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4140 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4142 // Don't promote to an alignment that would require dynamic stack
4144 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4145 if (!TRI->needsStackRealignment(MF))
4146 while (NewAlign > Align &&
4147 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4150 if (NewAlign > Align) {
4151 // Give the stack frame object a larger alignment if needed.
4152 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4153 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4158 SmallVector<SDValue, 8> OutChains;
4159 unsigned NumMemOps = MemOps.size();
4160 uint64_t SrcOff = 0, DstOff = 0;
4161 for (unsigned i = 0; i != NumMemOps; ++i) {
4163 unsigned VTSize = VT.getSizeInBits() / 8;
4164 SDValue Value, Store;
4166 if (VTSize > Size) {
4167 // Issuing an unaligned load / store pair that overlaps with the previous
4168 // pair. Adjust the offset accordingly.
4169 assert(i == NumMemOps-1 && i != 0);
4170 SrcOff -= VTSize - Size;
4171 DstOff -= VTSize - Size;
4175 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4176 // It's unlikely a store of a vector immediate can be done in a single
4177 // instruction. It would require a load from a constantpool first.
4178 // We only handle zero vectors here.
4179 // FIXME: Handle other cases where store of vector immediate is done in
4180 // a single instruction.
4181 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4182 if (Value.getNode())
4183 Store = DAG.getStore(Chain, dl, Value,
4184 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4185 DstPtrInfo.getWithOffset(DstOff), isVol,
4189 if (!Store.getNode()) {
4190 // The type might not be legal for the target. This should only happen
4191 // if the type is smaller than a legal type, as on PPC, so the right
4192 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4193 // to Load/Store if NVT==VT.
4194 // FIXME does the case above also need this?
4195 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4196 assert(NVT.bitsGE(VT));
4197 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4198 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4199 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4200 false, MinAlign(SrcAlign, SrcOff));
4201 Store = DAG.getTruncStore(Chain, dl, Value,
4202 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4203 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4206 OutChains.push_back(Store);
4212 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4215 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4216 SDValue Chain, SDValue Dst,
4217 SDValue Src, uint64_t Size,
4218 unsigned Align, bool isVol,
4220 MachinePointerInfo DstPtrInfo,
4221 MachinePointerInfo SrcPtrInfo) {
4222 // Turn a memmove of undef to nop.
4223 if (Src.getOpcode() == ISD::UNDEF)
4226 // Expand memmove to a series of load and store ops if the size operand falls
4227 // below a certain threshold.
4228 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4229 std::vector<EVT> MemOps;
4230 bool DstAlignCanChange = false;
4231 MachineFunction &MF = DAG.getMachineFunction();
4232 MachineFrameInfo *MFI = MF.getFrameInfo();
4233 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4234 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4235 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4236 DstAlignCanChange = true;
4237 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4238 if (Align > SrcAlign)
4240 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4242 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4243 (DstAlignCanChange ? 0 : Align), SrcAlign,
4244 false, false, false, false, DAG, TLI))
4247 if (DstAlignCanChange) {
4248 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4249 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4250 if (NewAlign > Align) {
4251 // Give the stack frame object a larger alignment if needed.
4252 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4253 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4258 uint64_t SrcOff = 0, DstOff = 0;
4259 SmallVector<SDValue, 8> LoadValues;
4260 SmallVector<SDValue, 8> LoadChains;
4261 SmallVector<SDValue, 8> OutChains;
4262 unsigned NumMemOps = MemOps.size();
4263 for (unsigned i = 0; i < NumMemOps; i++) {
4265 unsigned VTSize = VT.getSizeInBits() / 8;
4268 Value = DAG.getLoad(VT, dl, Chain,
4269 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4270 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4271 false, false, SrcAlign);
4272 LoadValues.push_back(Value);
4273 LoadChains.push_back(Value.getValue(1));
4276 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4278 for (unsigned i = 0; i < NumMemOps; i++) {
4280 unsigned VTSize = VT.getSizeInBits() / 8;
4283 Store = DAG.getStore(Chain, dl, LoadValues[i],
4284 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4285 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4286 OutChains.push_back(Store);
4290 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4293 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4296 /// \param DAG Selection DAG where lowered code is placed.
4297 /// \param dl Link to corresponding IR location.
4298 /// \param Chain Control flow dependency.
4299 /// \param Dst Pointer to destination memory location.
4300 /// \param Src Value of byte to write into the memory.
4301 /// \param Size Number of bytes to write.
4302 /// \param Align Alignment of the destination in bytes.
4303 /// \param isVol True if destination is volatile.
4304 /// \param DstPtrInfo IR information on the memory pointer.
4305 /// \returns New head in the control flow, if lowering was successful, empty
4306 /// SDValue otherwise.
4308 /// The function tries to replace 'llvm.memset' intrinsic with several store
4309 /// operations and value calculation code. This is usually profitable for small
4311 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4312 SDValue Chain, SDValue Dst,
4313 SDValue Src, uint64_t Size,
4314 unsigned Align, bool isVol,
4315 MachinePointerInfo DstPtrInfo) {
4316 // Turn a memset of undef to nop.
4317 if (Src.getOpcode() == ISD::UNDEF)
4320 // Expand memset to a series of load/store ops if the size operand
4321 // falls below a certain threshold.
4322 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4323 std::vector<EVT> MemOps;
4324 bool DstAlignCanChange = false;
4325 MachineFunction &MF = DAG.getMachineFunction();
4326 MachineFrameInfo *MFI = MF.getFrameInfo();
4327 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4328 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4329 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4330 DstAlignCanChange = true;
4332 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4333 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4334 Size, (DstAlignCanChange ? 0 : Align), 0,
4335 true, IsZeroVal, false, true, DAG, TLI))
4338 if (DstAlignCanChange) {
4339 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4340 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4341 if (NewAlign > Align) {
4342 // Give the stack frame object a larger alignment if needed.
4343 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4344 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4349 SmallVector<SDValue, 8> OutChains;
4350 uint64_t DstOff = 0;
4351 unsigned NumMemOps = MemOps.size();
4353 // Find the largest store and generate the bit pattern for it.
4354 EVT LargestVT = MemOps[0];
4355 for (unsigned i = 1; i < NumMemOps; i++)
4356 if (MemOps[i].bitsGT(LargestVT))
4357 LargestVT = MemOps[i];
4358 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4360 for (unsigned i = 0; i < NumMemOps; i++) {
4362 unsigned VTSize = VT.getSizeInBits() / 8;
4363 if (VTSize > Size) {
4364 // Issuing an unaligned load / store pair that overlaps with the previous
4365 // pair. Adjust the offset accordingly.
4366 assert(i == NumMemOps-1 && i != 0);
4367 DstOff -= VTSize - Size;
4370 // If this store is smaller than the largest store see whether we can get
4371 // the smaller value for free with a truncate.
4372 SDValue Value = MemSetValue;
4373 if (VT.bitsLT(LargestVT)) {
4374 if (!LargestVT.isVector() && !VT.isVector() &&
4375 TLI.isTruncateFree(LargestVT, VT))
4376 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4378 Value = getMemsetValue(Src, VT, DAG, dl);
4380 assert(Value.getValueType() == VT && "Value with wrong type.");
4381 SDValue Store = DAG.getStore(Chain, dl, Value,
4382 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4383 DstPtrInfo.getWithOffset(DstOff),
4384 isVol, false, Align);
4385 OutChains.push_back(Store);
4386 DstOff += VT.getSizeInBits() / 8;
4390 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4393 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4394 SDValue Src, SDValue Size,
4395 unsigned Align, bool isVol, bool AlwaysInline,
4396 bool isTailCall, MachinePointerInfo DstPtrInfo,
4397 MachinePointerInfo SrcPtrInfo) {
4398 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4400 // Check to see if we should lower the memcpy to loads and stores first.
4401 // For cases within the target-specified limits, this is the best choice.
4402 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4404 // Memcpy with size zero? Just return the original chain.
4405 if (ConstantSize->isNullValue())
4408 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4409 ConstantSize->getZExtValue(),Align,
4410 isVol, false, DstPtrInfo, SrcPtrInfo);
4411 if (Result.getNode())
4415 // Then check to see if we should lower the memcpy with target-specific
4416 // code. If the target chooses to do this, this is the next best.
4418 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4419 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4420 DstPtrInfo, SrcPtrInfo);
4421 if (Result.getNode())
4425 // If we really need inline code and the target declined to provide it,
4426 // use a (potentially long) sequence of loads and stores.
4428 assert(ConstantSize && "AlwaysInline requires a constant size!");
4429 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4430 ConstantSize->getZExtValue(), Align, isVol,
4431 true, DstPtrInfo, SrcPtrInfo);
4434 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4435 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4436 // respect volatile, so they may do things like read or write memory
4437 // beyond the given memory regions. But fixing this isn't easy, and most
4438 // people don't care.
4440 // Emit a library call.
4441 TargetLowering::ArgListTy Args;
4442 TargetLowering::ArgListEntry Entry;
4443 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4444 Entry.Node = Dst; Args.push_back(Entry);
4445 Entry.Node = Src; Args.push_back(Entry);
4446 Entry.Node = Size; Args.push_back(Entry);
4447 // FIXME: pass in SDLoc
4448 TargetLowering::CallLoweringInfo CLI(*this);
4449 CLI.setDebugLoc(dl).setChain(Chain)
4450 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4451 Type::getVoidTy(*getContext()),
4452 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4453 TLI->getPointerTy()), std::move(Args), 0)
4455 .setTailCall(isTailCall);
4457 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4458 return CallResult.second;
4461 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4462 SDValue Src, SDValue Size,
4463 unsigned Align, bool isVol, bool isTailCall,
4464 MachinePointerInfo DstPtrInfo,
4465 MachinePointerInfo SrcPtrInfo) {
4466 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4468 // Check to see if we should lower the memmove to loads and stores first.
4469 // For cases within the target-specified limits, this is the best choice.
4470 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4472 // Memmove with size zero? Just return the original chain.
4473 if (ConstantSize->isNullValue())
4477 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4478 ConstantSize->getZExtValue(), Align, isVol,
4479 false, DstPtrInfo, SrcPtrInfo);
4480 if (Result.getNode())
4484 // Then check to see if we should lower the memmove with target-specific
4485 // code. If the target chooses to do this, this is the next best.
4487 SDValue Result = TSI->EmitTargetCodeForMemmove(
4488 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4489 if (Result.getNode())
4493 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4494 // not be safe. See memcpy above for more details.
4496 // Emit a library call.
4497 TargetLowering::ArgListTy Args;
4498 TargetLowering::ArgListEntry Entry;
4499 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4500 Entry.Node = Dst; Args.push_back(Entry);
4501 Entry.Node = Src; Args.push_back(Entry);
4502 Entry.Node = Size; Args.push_back(Entry);
4503 // FIXME: pass in SDLoc
4504 TargetLowering::CallLoweringInfo CLI(*this);
4505 CLI.setDebugLoc(dl).setChain(Chain)
4506 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4507 Type::getVoidTy(*getContext()),
4508 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4509 TLI->getPointerTy()), std::move(Args), 0)
4511 .setTailCall(isTailCall);
4513 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4514 return CallResult.second;
4517 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4518 SDValue Src, SDValue Size,
4519 unsigned Align, bool isVol, bool isTailCall,
4520 MachinePointerInfo DstPtrInfo) {
4521 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4523 // Check to see if we should lower the memset to stores first.
4524 // For cases within the target-specified limits, this is the best choice.
4525 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4527 // Memset with size zero? Just return the original chain.
4528 if (ConstantSize->isNullValue())
4532 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4533 Align, isVol, DstPtrInfo);
4535 if (Result.getNode())
4539 // Then check to see if we should lower the memset with target-specific
4540 // code. If the target chooses to do this, this is the next best.
4542 SDValue Result = TSI->EmitTargetCodeForMemset(
4543 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4544 if (Result.getNode())
4548 // Emit a library call.
4549 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4550 TargetLowering::ArgListTy Args;
4551 TargetLowering::ArgListEntry Entry;
4552 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4553 Args.push_back(Entry);
4555 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4556 Args.push_back(Entry);
4558 Entry.Ty = IntPtrTy;
4559 Args.push_back(Entry);
4561 // FIXME: pass in SDLoc
4562 TargetLowering::CallLoweringInfo CLI(*this);
4563 CLI.setDebugLoc(dl).setChain(Chain)
4564 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4565 Type::getVoidTy(*getContext()),
4566 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4567 TLI->getPointerTy()), std::move(Args), 0)
4569 .setTailCall(isTailCall);
4571 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4572 return CallResult.second;
4575 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4576 SDVTList VTList, ArrayRef<SDValue> Ops,
4577 MachineMemOperand *MMO,
4578 AtomicOrdering SuccessOrdering,
4579 AtomicOrdering FailureOrdering,
4580 SynchronizationScope SynchScope) {
4581 FoldingSetNodeID ID;
4582 ID.AddInteger(MemVT.getRawBits());
4583 AddNodeIDNode(ID, Opcode, VTList, Ops);
4584 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4586 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4587 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4588 return SDValue(E, 0);
4591 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4592 // SDNode doesn't have access to it. This memory will be "leaked" when
4593 // the node is deallocated, but recovered when the allocator is released.
4594 // If the number of operands is less than 5 we use AtomicSDNode's internal
4596 unsigned NumOps = Ops.size();
4597 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4600 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4601 dl.getDebugLoc(), VTList, MemVT,
4602 Ops.data(), DynOps, NumOps, MMO,
4603 SuccessOrdering, FailureOrdering,
4605 CSEMap.InsertNode(N, IP);
4607 return SDValue(N, 0);
4610 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4611 SDVTList VTList, ArrayRef<SDValue> Ops,
4612 MachineMemOperand *MMO,
4613 AtomicOrdering Ordering,
4614 SynchronizationScope SynchScope) {
4615 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4616 Ordering, SynchScope);
4619 SDValue SelectionDAG::getAtomicCmpSwap(
4620 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4621 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4622 unsigned Alignment, AtomicOrdering SuccessOrdering,
4623 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4624 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4625 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4626 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4628 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4629 Alignment = getEVTAlignment(MemVT);
4631 MachineFunction &MF = getMachineFunction();
4633 // FIXME: Volatile isn't really correct; we should keep track of atomic
4634 // orderings in the memoperand.
4635 unsigned Flags = MachineMemOperand::MOVolatile;
4636 Flags |= MachineMemOperand::MOLoad;
4637 Flags |= MachineMemOperand::MOStore;
4639 MachineMemOperand *MMO =
4640 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4642 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4643 SuccessOrdering, FailureOrdering, SynchScope);
4646 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4647 SDVTList VTs, SDValue Chain, SDValue Ptr,
4648 SDValue Cmp, SDValue Swp,
4649 MachineMemOperand *MMO,
4650 AtomicOrdering SuccessOrdering,
4651 AtomicOrdering FailureOrdering,
4652 SynchronizationScope SynchScope) {
4653 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4654 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4655 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4657 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4658 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4659 SuccessOrdering, FailureOrdering, SynchScope);
4662 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4664 SDValue Ptr, SDValue Val,
4665 const Value* PtrVal,
4667 AtomicOrdering Ordering,
4668 SynchronizationScope SynchScope) {
4669 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4670 Alignment = getEVTAlignment(MemVT);
4672 MachineFunction &MF = getMachineFunction();
4673 // An atomic store does not load. An atomic load does not store.
4674 // (An atomicrmw obviously both loads and stores.)
4675 // For now, atomics are considered to be volatile always, and they are
4677 // FIXME: Volatile isn't really correct; we should keep track of atomic
4678 // orderings in the memoperand.
4679 unsigned Flags = MachineMemOperand::MOVolatile;
4680 if (Opcode != ISD::ATOMIC_STORE)
4681 Flags |= MachineMemOperand::MOLoad;
4682 if (Opcode != ISD::ATOMIC_LOAD)
4683 Flags |= MachineMemOperand::MOStore;
4685 MachineMemOperand *MMO =
4686 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4687 MemVT.getStoreSize(), Alignment);
4689 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4690 Ordering, SynchScope);
4693 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4695 SDValue Ptr, SDValue Val,
4696 MachineMemOperand *MMO,
4697 AtomicOrdering Ordering,
4698 SynchronizationScope SynchScope) {
4699 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4700 Opcode == ISD::ATOMIC_LOAD_SUB ||
4701 Opcode == ISD::ATOMIC_LOAD_AND ||
4702 Opcode == ISD::ATOMIC_LOAD_OR ||
4703 Opcode == ISD::ATOMIC_LOAD_XOR ||
4704 Opcode == ISD::ATOMIC_LOAD_NAND ||
4705 Opcode == ISD::ATOMIC_LOAD_MIN ||
4706 Opcode == ISD::ATOMIC_LOAD_MAX ||
4707 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4708 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4709 Opcode == ISD::ATOMIC_SWAP ||
4710 Opcode == ISD::ATOMIC_STORE) &&
4711 "Invalid Atomic Op");
4713 EVT VT = Val.getValueType();
4715 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4716 getVTList(VT, MVT::Other);
4717 SDValue Ops[] = {Chain, Ptr, Val};
4718 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4721 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4722 EVT VT, SDValue Chain,
4724 MachineMemOperand *MMO,
4725 AtomicOrdering Ordering,
4726 SynchronizationScope SynchScope) {
4727 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4729 SDVTList VTs = getVTList(VT, MVT::Other);
4730 SDValue Ops[] = {Chain, Ptr};
4731 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4734 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4735 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4736 if (Ops.size() == 1)
4739 SmallVector<EVT, 4> VTs;
4740 VTs.reserve(Ops.size());
4741 for (unsigned i = 0; i < Ops.size(); ++i)
4742 VTs.push_back(Ops[i].getValueType());
4743 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4747 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4748 ArrayRef<SDValue> Ops,
4749 EVT MemVT, MachinePointerInfo PtrInfo,
4750 unsigned Align, bool Vol,
4751 bool ReadMem, bool WriteMem, unsigned Size) {
4752 if (Align == 0) // Ensure that codegen never sees alignment 0
4753 Align = getEVTAlignment(MemVT);
4755 MachineFunction &MF = getMachineFunction();
4758 Flags |= MachineMemOperand::MOStore;
4760 Flags |= MachineMemOperand::MOLoad;
4762 Flags |= MachineMemOperand::MOVolatile;
4764 Size = MemVT.getStoreSize();
4765 MachineMemOperand *MMO =
4766 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4768 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4772 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4773 ArrayRef<SDValue> Ops, EVT MemVT,
4774 MachineMemOperand *MMO) {
4775 assert((Opcode == ISD::INTRINSIC_VOID ||
4776 Opcode == ISD::INTRINSIC_W_CHAIN ||
4777 Opcode == ISD::PREFETCH ||
4778 Opcode == ISD::LIFETIME_START ||
4779 Opcode == ISD::LIFETIME_END ||
4780 (Opcode <= INT_MAX &&
4781 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4782 "Opcode is not a memory-accessing opcode!");
4784 // Memoize the node unless it returns a flag.
4785 MemIntrinsicSDNode *N;
4786 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4787 FoldingSetNodeID ID;
4788 AddNodeIDNode(ID, Opcode, VTList, Ops);
4789 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4791 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4792 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4793 return SDValue(E, 0);
4796 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4797 dl.getDebugLoc(), VTList, Ops,
4799 CSEMap.InsertNode(N, IP);
4801 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4802 dl.getDebugLoc(), VTList, Ops,
4806 return SDValue(N, 0);
4809 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4810 /// MachinePointerInfo record from it. This is particularly useful because the
4811 /// code generator has many cases where it doesn't bother passing in a
4812 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4813 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4814 // If this is FI+Offset, we can model it.
4815 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4816 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4818 // If this is (FI+Offset1)+Offset2, we can model it.
4819 if (Ptr.getOpcode() != ISD::ADD ||
4820 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4821 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4822 return MachinePointerInfo();
4824 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4825 return MachinePointerInfo::getFixedStack(FI, Offset+
4826 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4829 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4830 /// MachinePointerInfo record from it. This is particularly useful because the
4831 /// code generator has many cases where it doesn't bother passing in a
4832 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4833 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4834 // If the 'Offset' value isn't a constant, we can't handle this.
4835 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4836 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4837 if (OffsetOp.getOpcode() == ISD::UNDEF)
4838 return InferPointerInfo(Ptr);
4839 return MachinePointerInfo();
4844 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4845 EVT VT, SDLoc dl, SDValue Chain,
4846 SDValue Ptr, SDValue Offset,
4847 MachinePointerInfo PtrInfo, EVT MemVT,
4848 bool isVolatile, bool isNonTemporal, bool isInvariant,
4849 unsigned Alignment, const AAMDNodes &AAInfo,
4850 const MDNode *Ranges) {
4851 assert(Chain.getValueType() == MVT::Other &&
4852 "Invalid chain type");
4853 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4854 Alignment = getEVTAlignment(VT);
4856 unsigned Flags = MachineMemOperand::MOLoad;
4858 Flags |= MachineMemOperand::MOVolatile;
4860 Flags |= MachineMemOperand::MONonTemporal;
4862 Flags |= MachineMemOperand::MOInvariant;
4864 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4866 if (PtrInfo.V.isNull())
4867 PtrInfo = InferPointerInfo(Ptr, Offset);
4869 MachineFunction &MF = getMachineFunction();
4870 MachineMemOperand *MMO =
4871 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4873 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4877 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4878 EVT VT, SDLoc dl, SDValue Chain,
4879 SDValue Ptr, SDValue Offset, EVT MemVT,
4880 MachineMemOperand *MMO) {
4882 ExtType = ISD::NON_EXTLOAD;
4883 } else if (ExtType == ISD::NON_EXTLOAD) {
4884 assert(VT == MemVT && "Non-extending load from different memory type!");
4887 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4888 "Should only be an extending load, not truncating!");
4889 assert(VT.isInteger() == MemVT.isInteger() &&
4890 "Cannot convert from FP to Int or Int -> FP!");
4891 assert(VT.isVector() == MemVT.isVector() &&
4892 "Cannot use an ext load to convert to or from a vector!");
4893 assert((!VT.isVector() ||
4894 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4895 "Cannot use an ext load to change the number of vector elements!");
4898 bool Indexed = AM != ISD::UNINDEXED;
4899 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4900 "Unindexed load with an offset!");
4902 SDVTList VTs = Indexed ?
4903 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4904 SDValue Ops[] = { Chain, Ptr, Offset };
4905 FoldingSetNodeID ID;
4906 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4907 ID.AddInteger(MemVT.getRawBits());
4908 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4909 MMO->isNonTemporal(),
4910 MMO->isInvariant()));
4911 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4913 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4914 cast<LoadSDNode>(E)->refineAlignment(MMO);
4915 return SDValue(E, 0);
4917 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4918 dl.getDebugLoc(), VTs, AM, ExtType,
4920 CSEMap.InsertNode(N, IP);
4922 return SDValue(N, 0);
4925 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4926 SDValue Chain, SDValue Ptr,
4927 MachinePointerInfo PtrInfo,
4928 bool isVolatile, bool isNonTemporal,
4929 bool isInvariant, unsigned Alignment,
4930 const AAMDNodes &AAInfo,
4931 const MDNode *Ranges) {
4932 SDValue Undef = getUNDEF(Ptr.getValueType());
4933 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4934 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4938 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4939 SDValue Chain, SDValue Ptr,
4940 MachineMemOperand *MMO) {
4941 SDValue Undef = getUNDEF(Ptr.getValueType());
4942 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4946 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4947 SDValue Chain, SDValue Ptr,
4948 MachinePointerInfo PtrInfo, EVT MemVT,
4949 bool isVolatile, bool isNonTemporal,
4950 bool isInvariant, unsigned Alignment,
4951 const AAMDNodes &AAInfo) {
4952 SDValue Undef = getUNDEF(Ptr.getValueType());
4953 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4954 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4959 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4960 SDValue Chain, SDValue Ptr, EVT MemVT,
4961 MachineMemOperand *MMO) {
4962 SDValue Undef = getUNDEF(Ptr.getValueType());
4963 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4968 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4969 SDValue Offset, ISD::MemIndexedMode AM) {
4970 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4971 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4972 "Load is already a indexed load!");
4973 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4974 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4975 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4976 false, LD->getAlignment());
4979 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4980 SDValue Ptr, MachinePointerInfo PtrInfo,
4981 bool isVolatile, bool isNonTemporal,
4982 unsigned Alignment, const AAMDNodes &AAInfo) {
4983 assert(Chain.getValueType() == MVT::Other &&
4984 "Invalid chain type");
4985 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4986 Alignment = getEVTAlignment(Val.getValueType());
4988 unsigned Flags = MachineMemOperand::MOStore;
4990 Flags |= MachineMemOperand::MOVolatile;
4992 Flags |= MachineMemOperand::MONonTemporal;
4994 if (PtrInfo.V.isNull())
4995 PtrInfo = InferPointerInfo(Ptr);
4997 MachineFunction &MF = getMachineFunction();
4998 MachineMemOperand *MMO =
4999 MF.getMachineMemOperand(PtrInfo, Flags,
5000 Val.getValueType().getStoreSize(), Alignment,
5003 return getStore(Chain, dl, Val, Ptr, MMO);
5006 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5007 SDValue Ptr, MachineMemOperand *MMO) {
5008 assert(Chain.getValueType() == MVT::Other &&
5009 "Invalid chain type");
5010 EVT VT = Val.getValueType();
5011 SDVTList VTs = getVTList(MVT::Other);
5012 SDValue Undef = getUNDEF(Ptr.getValueType());
5013 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5014 FoldingSetNodeID ID;
5015 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5016 ID.AddInteger(VT.getRawBits());
5017 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5018 MMO->isNonTemporal(), MMO->isInvariant()));
5019 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5021 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5022 cast<StoreSDNode>(E)->refineAlignment(MMO);
5023 return SDValue(E, 0);
5025 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5026 dl.getDebugLoc(), VTs,
5027 ISD::UNINDEXED, false, VT, MMO);
5028 CSEMap.InsertNode(N, IP);
5030 return SDValue(N, 0);
5033 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5034 SDValue Ptr, MachinePointerInfo PtrInfo,
5035 EVT SVT,bool isVolatile, bool isNonTemporal,
5037 const AAMDNodes &AAInfo) {
5038 assert(Chain.getValueType() == MVT::Other &&
5039 "Invalid chain type");
5040 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5041 Alignment = getEVTAlignment(SVT);
5043 unsigned Flags = MachineMemOperand::MOStore;
5045 Flags |= MachineMemOperand::MOVolatile;
5047 Flags |= MachineMemOperand::MONonTemporal;
5049 if (PtrInfo.V.isNull())
5050 PtrInfo = InferPointerInfo(Ptr);
5052 MachineFunction &MF = getMachineFunction();
5053 MachineMemOperand *MMO =
5054 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5057 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5060 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5061 SDValue Ptr, EVT SVT,
5062 MachineMemOperand *MMO) {
5063 EVT VT = Val.getValueType();
5065 assert(Chain.getValueType() == MVT::Other &&
5066 "Invalid chain type");
5068 return getStore(Chain, dl, Val, Ptr, MMO);
5070 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5071 "Should only be a truncating store, not extending!");
5072 assert(VT.isInteger() == SVT.isInteger() &&
5073 "Can't do FP-INT conversion!");
5074 assert(VT.isVector() == SVT.isVector() &&
5075 "Cannot use trunc store to convert to or from a vector!");
5076 assert((!VT.isVector() ||
5077 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5078 "Cannot use trunc store to change the number of vector elements!");
5080 SDVTList VTs = getVTList(MVT::Other);
5081 SDValue Undef = getUNDEF(Ptr.getValueType());
5082 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5083 FoldingSetNodeID ID;
5084 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5085 ID.AddInteger(SVT.getRawBits());
5086 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5087 MMO->isNonTemporal(), MMO->isInvariant()));
5088 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5090 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5091 cast<StoreSDNode>(E)->refineAlignment(MMO);
5092 return SDValue(E, 0);
5094 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5095 dl.getDebugLoc(), VTs,
5096 ISD::UNINDEXED, true, SVT, MMO);
5097 CSEMap.InsertNode(N, IP);
5099 return SDValue(N, 0);
5103 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5104 SDValue Offset, ISD::MemIndexedMode AM) {
5105 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5106 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5107 "Store is already a indexed store!");
5108 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5109 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5110 FoldingSetNodeID ID;
5111 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5112 ID.AddInteger(ST->getMemoryVT().getRawBits());
5113 ID.AddInteger(ST->getRawSubclassData());
5114 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5116 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5117 return SDValue(E, 0);
5119 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5120 dl.getDebugLoc(), VTs, AM,
5121 ST->isTruncatingStore(),
5123 ST->getMemOperand());
5124 CSEMap.InsertNode(N, IP);
5126 return SDValue(N, 0);
5130 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5131 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5132 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5134 SDVTList VTs = getVTList(VT, MVT::Other);
5135 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5136 FoldingSetNodeID ID;
5137 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5138 ID.AddInteger(VT.getRawBits());
5139 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5141 MMO->isNonTemporal(),
5142 MMO->isInvariant()));
5143 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5145 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5146 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5147 return SDValue(E, 0);
5149 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5150 dl.getDebugLoc(), Ops, 4, VTs,
5152 CSEMap.InsertNode(N, IP);
5154 return SDValue(N, 0);
5157 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5158 SDValue Ptr, SDValue Mask, EVT MemVT,
5159 MachineMemOperand *MMO, bool isTrunc) {
5160 assert(Chain.getValueType() == MVT::Other &&
5161 "Invalid chain type");
5162 EVT VT = Val.getValueType();
5163 SDVTList VTs = getVTList(MVT::Other);
5164 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5165 FoldingSetNodeID ID;
5166 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5167 ID.AddInteger(VT.getRawBits());
5168 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5169 MMO->isNonTemporal(), MMO->isInvariant()));
5170 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5172 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5173 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5174 return SDValue(E, 0);
5176 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5177 dl.getDebugLoc(), Ops, 4,
5178 VTs, isTrunc, MemVT, MMO);
5179 CSEMap.InsertNode(N, IP);
5181 return SDValue(N, 0);
5185 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5186 ArrayRef<SDValue> Ops,
5187 MachineMemOperand *MMO) {
5189 FoldingSetNodeID ID;
5190 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5191 ID.AddInteger(VT.getRawBits());
5192 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5194 MMO->isNonTemporal(),
5195 MMO->isInvariant()));
5196 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5198 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5199 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5200 return SDValue(E, 0);
5202 MaskedGatherSDNode *N =
5203 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5205 CSEMap.InsertNode(N, IP);
5207 return SDValue(N, 0);
5210 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5211 ArrayRef<SDValue> Ops,
5212 MachineMemOperand *MMO) {
5213 FoldingSetNodeID ID;
5214 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5215 ID.AddInteger(VT.getRawBits());
5216 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5217 MMO->isNonTemporal(),
5218 MMO->isInvariant()));
5219 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5221 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5222 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5223 return SDValue(E, 0);
5226 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5228 CSEMap.InsertNode(N, IP);
5230 return SDValue(N, 0);
5233 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5234 SDValue Chain, SDValue Ptr,
5237 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5238 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5241 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5242 ArrayRef<SDUse> Ops) {
5243 switch (Ops.size()) {
5244 case 0: return getNode(Opcode, DL, VT);
5245 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5246 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5247 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5251 // Copy from an SDUse array into an SDValue array for use with
5252 // the regular getNode logic.
5253 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5254 return getNode(Opcode, DL, VT, NewOps);
5257 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5258 ArrayRef<SDValue> Ops) {
5259 unsigned NumOps = Ops.size();
5261 case 0: return getNode(Opcode, DL, VT);
5262 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5263 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5264 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5270 case ISD::SELECT_CC: {
5271 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5272 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5273 "LHS and RHS of condition must have same type!");
5274 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5275 "True and False arms of SelectCC must have same type!");
5276 assert(Ops[2].getValueType() == VT &&
5277 "select_cc node must be of same type as true and false value!");
5281 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5282 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5283 "LHS/RHS of comparison should match types!");
5290 SDVTList VTs = getVTList(VT);
5292 if (VT != MVT::Glue) {
5293 FoldingSetNodeID ID;
5294 AddNodeIDNode(ID, Opcode, VTs, Ops);
5297 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5298 return SDValue(E, 0);
5300 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5302 CSEMap.InsertNode(N, IP);
5304 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5309 return SDValue(N, 0);
5312 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5313 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5314 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5317 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5318 ArrayRef<SDValue> Ops) {
5319 if (VTList.NumVTs == 1)
5320 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5324 // FIXME: figure out how to safely handle things like
5325 // int foo(int x) { return 1 << (x & 255); }
5326 // int bar() { return foo(256); }
5327 case ISD::SRA_PARTS:
5328 case ISD::SRL_PARTS:
5329 case ISD::SHL_PARTS:
5330 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5331 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5332 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5333 else if (N3.getOpcode() == ISD::AND)
5334 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5335 // If the and is only masking out bits that cannot effect the shift,
5336 // eliminate the and.
5337 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5338 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5339 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5345 // Memoize the node unless it returns a flag.
5347 unsigned NumOps = Ops.size();
5348 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5349 FoldingSetNodeID ID;
5350 AddNodeIDNode(ID, Opcode, VTList, Ops);
5352 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5353 return SDValue(E, 0);
5356 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5357 DL.getDebugLoc(), VTList, Ops[0]);
5358 } else if (NumOps == 2) {
5359 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5360 DL.getDebugLoc(), VTList, Ops[0],
5362 } else if (NumOps == 3) {
5363 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5364 DL.getDebugLoc(), VTList, Ops[0],
5367 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5370 CSEMap.InsertNode(N, IP);
5373 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5374 DL.getDebugLoc(), VTList, Ops[0]);
5375 } else if (NumOps == 2) {
5376 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5377 DL.getDebugLoc(), VTList, Ops[0],
5379 } else if (NumOps == 3) {
5380 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5381 DL.getDebugLoc(), VTList, Ops[0],
5384 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5389 return SDValue(N, 0);
5392 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5393 return getNode(Opcode, DL, VTList, None);
5396 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5398 SDValue Ops[] = { N1 };
5399 return getNode(Opcode, DL, VTList, Ops);
5402 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5403 SDValue N1, SDValue N2) {
5404 SDValue Ops[] = { N1, N2 };
5405 return getNode(Opcode, DL, VTList, Ops);
5408 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5409 SDValue N1, SDValue N2, SDValue N3) {
5410 SDValue Ops[] = { N1, N2, N3 };
5411 return getNode(Opcode, DL, VTList, Ops);
5414 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5415 SDValue N1, SDValue N2, SDValue N3,
5417 SDValue Ops[] = { N1, N2, N3, N4 };
5418 return getNode(Opcode, DL, VTList, Ops);
5421 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5422 SDValue N1, SDValue N2, SDValue N3,
5423 SDValue N4, SDValue N5) {
5424 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5425 return getNode(Opcode, DL, VTList, Ops);
5428 SDVTList SelectionDAG::getVTList(EVT VT) {
5429 return makeVTList(SDNode::getValueTypeList(VT), 1);
5432 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5433 FoldingSetNodeID ID;
5435 ID.AddInteger(VT1.getRawBits());
5436 ID.AddInteger(VT2.getRawBits());
5439 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5441 EVT *Array = Allocator.Allocate<EVT>(2);
5444 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5445 VTListMap.InsertNode(Result, IP);
5447 return Result->getSDVTList();
5450 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5451 FoldingSetNodeID ID;
5453 ID.AddInteger(VT1.getRawBits());
5454 ID.AddInteger(VT2.getRawBits());
5455 ID.AddInteger(VT3.getRawBits());
5458 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5460 EVT *Array = Allocator.Allocate<EVT>(3);
5464 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5465 VTListMap.InsertNode(Result, IP);
5467 return Result->getSDVTList();
5470 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5471 FoldingSetNodeID ID;
5473 ID.AddInteger(VT1.getRawBits());
5474 ID.AddInteger(VT2.getRawBits());
5475 ID.AddInteger(VT3.getRawBits());
5476 ID.AddInteger(VT4.getRawBits());
5479 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5481 EVT *Array = Allocator.Allocate<EVT>(4);
5486 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5487 VTListMap.InsertNode(Result, IP);
5489 return Result->getSDVTList();
5492 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5493 unsigned NumVTs = VTs.size();
5494 FoldingSetNodeID ID;
5495 ID.AddInteger(NumVTs);
5496 for (unsigned index = 0; index < NumVTs; index++) {
5497 ID.AddInteger(VTs[index].getRawBits());
5501 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5503 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5504 std::copy(VTs.begin(), VTs.end(), Array);
5505 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5506 VTListMap.InsertNode(Result, IP);
5508 return Result->getSDVTList();
5512 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5513 /// specified operands. If the resultant node already exists in the DAG,
5514 /// this does not modify the specified node, instead it returns the node that
5515 /// already exists. If the resultant node does not exist in the DAG, the
5516 /// input node is returned. As a degenerate case, if you specify the same
5517 /// input operands as the node already has, the input node is returned.
5518 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5519 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5521 // Check to see if there is no change.
5522 if (Op == N->getOperand(0)) return N;
5524 // See if the modified node already exists.
5525 void *InsertPos = nullptr;
5526 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5529 // Nope it doesn't. Remove the node from its current place in the maps.
5531 if (!RemoveNodeFromCSEMaps(N))
5532 InsertPos = nullptr;
5534 // Now we update the operands.
5535 N->OperandList[0].set(Op);
5537 // If this gets put into a CSE map, add it.
5538 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5542 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5543 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5545 // Check to see if there is no change.
5546 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5547 return N; // No operands changed, just return the input node.
5549 // See if the modified node already exists.
5550 void *InsertPos = nullptr;
5551 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5554 // Nope it doesn't. Remove the node from its current place in the maps.
5556 if (!RemoveNodeFromCSEMaps(N))
5557 InsertPos = nullptr;
5559 // Now we update the operands.
5560 if (N->OperandList[0] != Op1)
5561 N->OperandList[0].set(Op1);
5562 if (N->OperandList[1] != Op2)
5563 N->OperandList[1].set(Op2);
5565 // If this gets put into a CSE map, add it.
5566 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5570 SDNode *SelectionDAG::
5571 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5572 SDValue Ops[] = { Op1, Op2, Op3 };
5573 return UpdateNodeOperands(N, Ops);
5576 SDNode *SelectionDAG::
5577 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5578 SDValue Op3, SDValue Op4) {
5579 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5580 return UpdateNodeOperands(N, Ops);
5583 SDNode *SelectionDAG::
5584 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5585 SDValue Op3, SDValue Op4, SDValue Op5) {
5586 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5587 return UpdateNodeOperands(N, Ops);
5590 SDNode *SelectionDAG::
5591 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5592 unsigned NumOps = Ops.size();
5593 assert(N->getNumOperands() == NumOps &&
5594 "Update with wrong number of operands");
5596 // If no operands changed just return the input node.
5597 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5600 // See if the modified node already exists.
5601 void *InsertPos = nullptr;
5602 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5605 // Nope it doesn't. Remove the node from its current place in the maps.
5607 if (!RemoveNodeFromCSEMaps(N))
5608 InsertPos = nullptr;
5610 // Now we update the operands.
5611 for (unsigned i = 0; i != NumOps; ++i)
5612 if (N->OperandList[i] != Ops[i])
5613 N->OperandList[i].set(Ops[i]);
5615 // If this gets put into a CSE map, add it.
5616 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5620 /// DropOperands - Release the operands and set this node to have
5622 void SDNode::DropOperands() {
5623 // Unlike the code in MorphNodeTo that does this, we don't need to
5624 // watch for dead nodes here.
5625 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5631 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5634 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5636 SDVTList VTs = getVTList(VT);
5637 return SelectNodeTo(N, MachineOpc, VTs, None);
5640 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5641 EVT VT, SDValue Op1) {
5642 SDVTList VTs = getVTList(VT);
5643 SDValue Ops[] = { Op1 };
5644 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5647 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5648 EVT VT, SDValue Op1,
5650 SDVTList VTs = getVTList(VT);
5651 SDValue Ops[] = { Op1, Op2 };
5652 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5655 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5656 EVT VT, SDValue Op1,
5657 SDValue Op2, SDValue Op3) {
5658 SDVTList VTs = getVTList(VT);
5659 SDValue Ops[] = { Op1, Op2, Op3 };
5660 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5663 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5664 EVT VT, ArrayRef<SDValue> Ops) {
5665 SDVTList VTs = getVTList(VT);
5666 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5669 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5670 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5671 SDVTList VTs = getVTList(VT1, VT2);
5672 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5675 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5677 SDVTList VTs = getVTList(VT1, VT2);
5678 return SelectNodeTo(N, MachineOpc, VTs, None);
5681 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5682 EVT VT1, EVT VT2, EVT VT3,
5683 ArrayRef<SDValue> Ops) {
5684 SDVTList VTs = getVTList(VT1, VT2, VT3);
5685 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5688 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5689 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5690 ArrayRef<SDValue> Ops) {
5691 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5692 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5695 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698 SDVTList VTs = getVTList(VT1, VT2);
5699 SDValue Ops[] = { Op1 };
5700 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5703 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5705 SDValue Op1, SDValue Op2) {
5706 SDVTList VTs = getVTList(VT1, VT2);
5707 SDValue Ops[] = { Op1, Op2 };
5708 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5711 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5713 SDValue Op1, SDValue Op2,
5715 SDVTList VTs = getVTList(VT1, VT2);
5716 SDValue Ops[] = { Op1, Op2, Op3 };
5717 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5720 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5721 EVT VT1, EVT VT2, EVT VT3,
5722 SDValue Op1, SDValue Op2,
5724 SDVTList VTs = getVTList(VT1, VT2, VT3);
5725 SDValue Ops[] = { Op1, Op2, Op3 };
5726 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5729 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5730 SDVTList VTs,ArrayRef<SDValue> Ops) {
5731 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5732 // Reset the NodeID to -1.
5737 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5738 /// the line number information on the merged node since it is not possible to
5739 /// preserve the information that operation is associated with multiple lines.
5740 /// This will make the debugger working better at -O0, were there is a higher
5741 /// probability having other instructions associated with that line.
5743 /// For IROrder, we keep the smaller of the two
5744 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5745 DebugLoc NLoc = N->getDebugLoc();
5746 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5747 N->setDebugLoc(DebugLoc());
5749 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5750 N->setIROrder(Order);
5754 /// MorphNodeTo - This *mutates* the specified node to have the specified
5755 /// return type, opcode, and operands.
5757 /// Note that MorphNodeTo returns the resultant node. If there is already a
5758 /// node of the specified opcode and operands, it returns that node instead of
5759 /// the current one. Note that the SDLoc need not be the same.
5761 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5762 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5763 /// node, and because it doesn't require CSE recalculation for any of
5764 /// the node's users.
5766 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5767 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5768 /// the legalizer which maintain worklists that would need to be updated when
5769 /// deleting things.
5770 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5771 SDVTList VTs, ArrayRef<SDValue> Ops) {
5772 unsigned NumOps = Ops.size();
5773 // If an identical node already exists, use it.
5775 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5776 FoldingSetNodeID ID;
5777 AddNodeIDNode(ID, Opc, VTs, Ops);
5778 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5779 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5782 if (!RemoveNodeFromCSEMaps(N))
5785 // Start the morphing.
5787 N->ValueList = VTs.VTs;
5788 N->NumValues = VTs.NumVTs;
5790 // Clear the operands list, updating used nodes to remove this from their
5791 // use list. Keep track of any operands that become dead as a result.
5792 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5793 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5795 SDNode *Used = Use.getNode();
5797 if (Used->use_empty())
5798 DeadNodeSet.insert(Used);
5801 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5802 // Initialize the memory references information.
5803 MN->setMemRefs(nullptr, nullptr);
5804 // If NumOps is larger than the # of operands we can have in a
5805 // MachineSDNode, reallocate the operand list.
5806 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5807 if (MN->OperandsNeedDelete)
5808 delete[] MN->OperandList;
5809 if (NumOps > array_lengthof(MN->LocalOperands))
5810 // We're creating a final node that will live unmorphed for the
5811 // remainder of the current SelectionDAG iteration, so we can allocate
5812 // the operands directly out of a pool with no recycling metadata.
5813 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5814 Ops.data(), NumOps);
5816 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5817 MN->OperandsNeedDelete = false;
5819 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5821 // If NumOps is larger than the # of operands we currently have, reallocate
5822 // the operand list.
5823 if (NumOps > N->NumOperands) {
5824 if (N->OperandsNeedDelete)
5825 delete[] N->OperandList;
5826 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5827 N->OperandsNeedDelete = true;
5829 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5832 // Delete any nodes that are still dead after adding the uses for the
5834 if (!DeadNodeSet.empty()) {
5835 SmallVector<SDNode *, 16> DeadNodes;
5836 for (SDNode *N : DeadNodeSet)
5838 DeadNodes.push_back(N);
5839 RemoveDeadNodes(DeadNodes);
5843 CSEMap.InsertNode(N, IP); // Memoize the new node.
5848 /// getMachineNode - These are used for target selectors to create a new node
5849 /// with specified return type(s), MachineInstr opcode, and operands.
5851 /// Note that getMachineNode returns the resultant node. If there is already a
5852 /// node of the specified opcode and operands, it returns that node instead of
5853 /// the current one.
5855 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5856 SDVTList VTs = getVTList(VT);
5857 return getMachineNode(Opcode, dl, VTs, None);
5861 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5862 SDVTList VTs = getVTList(VT);
5863 SDValue Ops[] = { Op1 };
5864 return getMachineNode(Opcode, dl, VTs, Ops);
5868 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5869 SDValue Op1, SDValue Op2) {
5870 SDVTList VTs = getVTList(VT);
5871 SDValue Ops[] = { Op1, Op2 };
5872 return getMachineNode(Opcode, dl, VTs, Ops);
5876 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5877 SDValue Op1, SDValue Op2, SDValue Op3) {
5878 SDVTList VTs = getVTList(VT);
5879 SDValue Ops[] = { Op1, Op2, Op3 };
5880 return getMachineNode(Opcode, dl, VTs, Ops);
5884 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5885 ArrayRef<SDValue> Ops) {
5886 SDVTList VTs = getVTList(VT);
5887 return getMachineNode(Opcode, dl, VTs, Ops);
5891 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5892 SDVTList VTs = getVTList(VT1, VT2);
5893 return getMachineNode(Opcode, dl, VTs, None);
5897 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5898 EVT VT1, EVT VT2, SDValue Op1) {
5899 SDVTList VTs = getVTList(VT1, VT2);
5900 SDValue Ops[] = { Op1 };
5901 return getMachineNode(Opcode, dl, VTs, Ops);
5905 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5906 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5907 SDVTList VTs = getVTList(VT1, VT2);
5908 SDValue Ops[] = { Op1, Op2 };
5909 return getMachineNode(Opcode, dl, VTs, Ops);
5913 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5914 EVT VT1, EVT VT2, SDValue Op1,
5915 SDValue Op2, SDValue Op3) {
5916 SDVTList VTs = getVTList(VT1, VT2);
5917 SDValue Ops[] = { Op1, Op2, Op3 };
5918 return getMachineNode(Opcode, dl, VTs, Ops);
5922 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5924 ArrayRef<SDValue> Ops) {
5925 SDVTList VTs = getVTList(VT1, VT2);
5926 return getMachineNode(Opcode, dl, VTs, Ops);
5930 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5931 EVT VT1, EVT VT2, EVT VT3,
5932 SDValue Op1, SDValue Op2) {
5933 SDVTList VTs = getVTList(VT1, VT2, VT3);
5934 SDValue Ops[] = { Op1, Op2 };
5935 return getMachineNode(Opcode, dl, VTs, Ops);
5939 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5940 EVT VT1, EVT VT2, EVT VT3,
5941 SDValue Op1, SDValue Op2, SDValue Op3) {
5942 SDVTList VTs = getVTList(VT1, VT2, VT3);
5943 SDValue Ops[] = { Op1, Op2, Op3 };
5944 return getMachineNode(Opcode, dl, VTs, Ops);
5948 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5949 EVT VT1, EVT VT2, EVT VT3,
5950 ArrayRef<SDValue> Ops) {
5951 SDVTList VTs = getVTList(VT1, VT2, VT3);
5952 return getMachineNode(Opcode, dl, VTs, Ops);
5956 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5957 EVT VT2, EVT VT3, EVT VT4,
5958 ArrayRef<SDValue> Ops) {
5959 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5960 return getMachineNode(Opcode, dl, VTs, Ops);
5964 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5965 ArrayRef<EVT> ResultTys,
5966 ArrayRef<SDValue> Ops) {
5967 SDVTList VTs = getVTList(ResultTys);
5968 return getMachineNode(Opcode, dl, VTs, Ops);
5972 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5973 ArrayRef<SDValue> OpsArray) {
5974 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5977 const SDValue *Ops = OpsArray.data();
5978 unsigned NumOps = OpsArray.size();
5981 FoldingSetNodeID ID;
5982 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5984 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5985 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5989 // Allocate a new MachineSDNode.
5990 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5991 DL.getDebugLoc(), VTs);
5993 // Initialize the operands list.
5994 if (NumOps > array_lengthof(N->LocalOperands))
5995 // We're creating a final node that will live unmorphed for the
5996 // remainder of the current SelectionDAG iteration, so we can allocate
5997 // the operands directly out of a pool with no recycling metadata.
5998 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6001 N->InitOperands(N->LocalOperands, Ops, NumOps);
6002 N->OperandsNeedDelete = false;
6005 CSEMap.InsertNode(N, IP);
6011 /// getTargetExtractSubreg - A convenience function for creating
6012 /// TargetOpcode::EXTRACT_SUBREG nodes.
6014 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6016 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6017 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6018 VT, Operand, SRIdxVal);
6019 return SDValue(Subreg, 0);
6022 /// getTargetInsertSubreg - A convenience function for creating
6023 /// TargetOpcode::INSERT_SUBREG nodes.
6025 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6026 SDValue Operand, SDValue Subreg) {
6027 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6028 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6029 VT, Operand, Subreg, SRIdxVal);
6030 return SDValue(Result, 0);
6033 /// getNodeIfExists - Get the specified node if it's already available, or
6034 /// else return NULL.
6035 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6036 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6038 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6039 FoldingSetNodeID ID;
6040 AddNodeIDNode(ID, Opcode, VTList, Ops);
6041 if (isBinOpWithFlags(Opcode))
6042 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6044 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6050 /// getDbgValue - Creates a SDDbgValue node.
6053 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6054 unsigned R, bool IsIndirect, uint64_t Off,
6055 DebugLoc DL, unsigned O) {
6056 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6057 "Expected inlined-at fields to agree");
6058 return new (DbgInfo->getAlloc())
6059 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6063 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6064 const Value *C, uint64_t Off,
6065 DebugLoc DL, unsigned O) {
6066 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6067 "Expected inlined-at fields to agree");
6068 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6072 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6073 unsigned FI, uint64_t Off,
6074 DebugLoc DL, unsigned O) {
6075 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6076 "Expected inlined-at fields to agree");
6077 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6082 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6083 /// pointed to by a use iterator is deleted, increment the use iterator
6084 /// so that it doesn't dangle.
6086 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6087 SDNode::use_iterator &UI;
6088 SDNode::use_iterator &UE;
6090 void NodeDeleted(SDNode *N, SDNode *E) override {
6091 // Increment the iterator as needed.
6092 while (UI != UE && N == *UI)
6097 RAUWUpdateListener(SelectionDAG &d,
6098 SDNode::use_iterator &ui,
6099 SDNode::use_iterator &ue)
6100 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6105 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6106 /// This can cause recursive merging of nodes in the DAG.
6108 /// This version assumes From has a single result value.
6110 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6111 SDNode *From = FromN.getNode();
6112 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6113 "Cannot replace with this method!");
6114 assert(From != To.getNode() && "Cannot replace uses of with self");
6116 // Iterate over all the existing uses of From. New uses will be added
6117 // to the beginning of the use list, which we avoid visiting.
6118 // This specifically avoids visiting uses of From that arise while the
6119 // replacement is happening, because any such uses would be the result
6120 // of CSE: If an existing node looks like From after one of its operands
6121 // is replaced by To, we don't want to replace of all its users with To
6122 // too. See PR3018 for more info.
6123 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6124 RAUWUpdateListener Listener(*this, UI, UE);
6128 // This node is about to morph, remove its old self from the CSE maps.
6129 RemoveNodeFromCSEMaps(User);
6131 // A user can appear in a use list multiple times, and when this
6132 // happens the uses are usually next to each other in the list.
6133 // To help reduce the number of CSE recomputations, process all
6134 // the uses of this user that we can find this way.
6136 SDUse &Use = UI.getUse();
6139 } while (UI != UE && *UI == User);
6141 // Now that we have modified User, add it back to the CSE maps. If it
6142 // already exists there, recursively merge the results together.
6143 AddModifiedNodeToCSEMaps(User);
6146 // If we just RAUW'd the root, take note.
6147 if (FromN == getRoot())
6151 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6152 /// This can cause recursive merging of nodes in the DAG.
6154 /// This version assumes that for each value of From, there is a
6155 /// corresponding value in To in the same position with the same type.
6157 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6159 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6160 assert((!From->hasAnyUseOfValue(i) ||
6161 From->getValueType(i) == To->getValueType(i)) &&
6162 "Cannot use this version of ReplaceAllUsesWith!");
6165 // Handle the trivial case.
6169 // Iterate over just the existing users of From. See the comments in
6170 // the ReplaceAllUsesWith above.
6171 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6172 RAUWUpdateListener Listener(*this, UI, UE);
6176 // This node is about to morph, remove its old self from the CSE maps.
6177 RemoveNodeFromCSEMaps(User);
6179 // A user can appear in a use list multiple times, and when this
6180 // happens the uses are usually next to each other in the list.
6181 // To help reduce the number of CSE recomputations, process all
6182 // the uses of this user that we can find this way.
6184 SDUse &Use = UI.getUse();
6187 } while (UI != UE && *UI == User);
6189 // Now that we have modified User, add it back to the CSE maps. If it
6190 // already exists there, recursively merge the results together.
6191 AddModifiedNodeToCSEMaps(User);
6194 // If we just RAUW'd the root, take note.
6195 if (From == getRoot().getNode())
6196 setRoot(SDValue(To, getRoot().getResNo()));
6199 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6200 /// This can cause recursive merging of nodes in the DAG.
6202 /// This version can replace From with any result values. To must match the
6203 /// number and types of values returned by From.
6204 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6205 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6206 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6208 // Iterate over just the existing users of From. See the comments in
6209 // the ReplaceAllUsesWith above.
6210 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6211 RAUWUpdateListener Listener(*this, UI, UE);
6215 // This node is about to morph, remove its old self from the CSE maps.
6216 RemoveNodeFromCSEMaps(User);
6218 // A user can appear in a use list multiple times, and when this
6219 // happens the uses are usually next to each other in the list.
6220 // To help reduce the number of CSE recomputations, process all
6221 // the uses of this user that we can find this way.
6223 SDUse &Use = UI.getUse();
6224 const SDValue &ToOp = To[Use.getResNo()];
6227 } while (UI != UE && *UI == User);
6229 // Now that we have modified User, add it back to the CSE maps. If it
6230 // already exists there, recursively merge the results together.
6231 AddModifiedNodeToCSEMaps(User);
6234 // If we just RAUW'd the root, take note.
6235 if (From == getRoot().getNode())
6236 setRoot(SDValue(To[getRoot().getResNo()]));
6239 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6240 /// uses of other values produced by From.getNode() alone. The Deleted
6241 /// vector is handled the same way as for ReplaceAllUsesWith.
6242 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6243 // Handle the really simple, really trivial case efficiently.
6244 if (From == To) return;
6246 // Handle the simple, trivial, case efficiently.
6247 if (From.getNode()->getNumValues() == 1) {
6248 ReplaceAllUsesWith(From, To);
6252 // Iterate over just the existing users of From. See the comments in
6253 // the ReplaceAllUsesWith above.
6254 SDNode::use_iterator UI = From.getNode()->use_begin(),
6255 UE = From.getNode()->use_end();
6256 RAUWUpdateListener Listener(*this, UI, UE);
6259 bool UserRemovedFromCSEMaps = false;
6261 // A user can appear in a use list multiple times, and when this
6262 // happens the uses are usually next to each other in the list.
6263 // To help reduce the number of CSE recomputations, process all
6264 // the uses of this user that we can find this way.
6266 SDUse &Use = UI.getUse();
6268 // Skip uses of different values from the same node.
6269 if (Use.getResNo() != From.getResNo()) {
6274 // If this node hasn't been modified yet, it's still in the CSE maps,
6275 // so remove its old self from the CSE maps.
6276 if (!UserRemovedFromCSEMaps) {
6277 RemoveNodeFromCSEMaps(User);
6278 UserRemovedFromCSEMaps = true;
6283 } while (UI != UE && *UI == User);
6285 // We are iterating over all uses of the From node, so if a use
6286 // doesn't use the specific value, no changes are made.
6287 if (!UserRemovedFromCSEMaps)
6290 // Now that we have modified User, add it back to the CSE maps. If it
6291 // already exists there, recursively merge the results together.
6292 AddModifiedNodeToCSEMaps(User);
6295 // If we just RAUW'd the root, take note.
6296 if (From == getRoot())
6301 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6302 /// to record information about a use.
6309 /// operator< - Sort Memos by User.
6310 bool operator<(const UseMemo &L, const UseMemo &R) {
6311 return (intptr_t)L.User < (intptr_t)R.User;
6315 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6316 /// uses of other values produced by From.getNode() alone. The same value
6317 /// may appear in both the From and To list. The Deleted vector is
6318 /// handled the same way as for ReplaceAllUsesWith.
6319 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6322 // Handle the simple, trivial case efficiently.
6324 return ReplaceAllUsesOfValueWith(*From, *To);
6326 // Read up all the uses and make records of them. This helps
6327 // processing new uses that are introduced during the
6328 // replacement process.
6329 SmallVector<UseMemo, 4> Uses;
6330 for (unsigned i = 0; i != Num; ++i) {
6331 unsigned FromResNo = From[i].getResNo();
6332 SDNode *FromNode = From[i].getNode();
6333 for (SDNode::use_iterator UI = FromNode->use_begin(),
6334 E = FromNode->use_end(); UI != E; ++UI) {
6335 SDUse &Use = UI.getUse();
6336 if (Use.getResNo() == FromResNo) {
6337 UseMemo Memo = { *UI, i, &Use };
6338 Uses.push_back(Memo);
6343 // Sort the uses, so that all the uses from a given User are together.
6344 std::sort(Uses.begin(), Uses.end());
6346 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6347 UseIndex != UseIndexEnd; ) {
6348 // We know that this user uses some value of From. If it is the right
6349 // value, update it.
6350 SDNode *User = Uses[UseIndex].User;
6352 // This node is about to morph, remove its old self from the CSE maps.
6353 RemoveNodeFromCSEMaps(User);
6355 // The Uses array is sorted, so all the uses for a given User
6356 // are next to each other in the list.
6357 // To help reduce the number of CSE recomputations, process all
6358 // the uses of this user that we can find this way.
6360 unsigned i = Uses[UseIndex].Index;
6361 SDUse &Use = *Uses[UseIndex].Use;
6365 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6367 // Now that we have modified User, add it back to the CSE maps. If it
6368 // already exists there, recursively merge the results together.
6369 AddModifiedNodeToCSEMaps(User);
6373 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6374 /// based on their topological order. It returns the maximum id and a vector
6375 /// of the SDNodes* in assigned order by reference.
6376 unsigned SelectionDAG::AssignTopologicalOrder() {
6378 unsigned DAGSize = 0;
6380 // SortedPos tracks the progress of the algorithm. Nodes before it are
6381 // sorted, nodes after it are unsorted. When the algorithm completes
6382 // it is at the end of the list.
6383 allnodes_iterator SortedPos = allnodes_begin();
6385 // Visit all the nodes. Move nodes with no operands to the front of
6386 // the list immediately. Annotate nodes that do have operands with their
6387 // operand count. Before we do this, the Node Id fields of the nodes
6388 // may contain arbitrary values. After, the Node Id fields for nodes
6389 // before SortedPos will contain the topological sort index, and the
6390 // Node Id fields for nodes At SortedPos and after will contain the
6391 // count of outstanding operands.
6392 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6394 checkForCycles(N, this);
6395 unsigned Degree = N->getNumOperands();
6397 // A node with no uses, add it to the result array immediately.
6398 N->setNodeId(DAGSize++);
6399 allnodes_iterator Q = N;
6401 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6402 assert(SortedPos != AllNodes.end() && "Overran node list");
6405 // Temporarily use the Node Id as scratch space for the degree count.
6406 N->setNodeId(Degree);
6410 // Visit all the nodes. As we iterate, move nodes into sorted order,
6411 // such that by the time the end is reached all nodes will be sorted.
6412 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6414 checkForCycles(N, this);
6415 // N is in sorted position, so all its uses have one less operand
6416 // that needs to be sorted.
6417 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6420 unsigned Degree = P->getNodeId();
6421 assert(Degree != 0 && "Invalid node degree");
6424 // All of P's operands are sorted, so P may sorted now.
6425 P->setNodeId(DAGSize++);
6427 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6428 assert(SortedPos != AllNodes.end() && "Overran node list");
6431 // Update P's outstanding operand count.
6432 P->setNodeId(Degree);
6435 if (I == SortedPos) {
6438 dbgs() << "Overran sorted position:\n";
6439 S->dumprFull(this); dbgs() << "\n";
6440 dbgs() << "Checking if this is due to cycles\n";
6441 checkForCycles(this, true);
6443 llvm_unreachable(nullptr);
6447 assert(SortedPos == AllNodes.end() &&
6448 "Topological sort incomplete!");
6449 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6450 "First node in topological sort is not the entry token!");
6451 assert(AllNodes.front().getNodeId() == 0 &&
6452 "First node in topological sort has non-zero id!");
6453 assert(AllNodes.front().getNumOperands() == 0 &&
6454 "First node in topological sort has operands!");
6455 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6456 "Last node in topologic sort has unexpected id!");
6457 assert(AllNodes.back().use_empty() &&
6458 "Last node in topologic sort has users!");
6459 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6463 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6464 /// value is produced by SD.
6465 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6467 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6468 SD->setHasDebugValue(true);
6470 DbgInfo->add(DB, SD, isParameter);
6473 /// TransferDbgValues - Transfer SDDbgValues.
6474 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6475 if (From == To || !From.getNode()->getHasDebugValue())
6477 SDNode *FromNode = From.getNode();
6478 SDNode *ToNode = To.getNode();
6479 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6480 SmallVector<SDDbgValue *, 2> ClonedDVs;
6481 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6483 SDDbgValue *Dbg = *I;
6484 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6486 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6487 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6488 Dbg->getDebugLoc(), Dbg->getOrder());
6489 ClonedDVs.push_back(Clone);
6492 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6493 E = ClonedDVs.end(); I != E; ++I)
6494 AddDbgValue(*I, ToNode, false);
6497 //===----------------------------------------------------------------------===//
6499 //===----------------------------------------------------------------------===//
6501 HandleSDNode::~HandleSDNode() {
6505 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6506 DebugLoc DL, const GlobalValue *GA,
6507 EVT VT, int64_t o, unsigned char TF)
6508 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6512 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6513 SDValue X, unsigned SrcAS,
6515 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6516 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6518 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6519 EVT memvt, MachineMemOperand *mmo)
6520 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6521 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6522 MMO->isNonTemporal(), MMO->isInvariant());
6523 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6524 assert(isNonTemporal() == MMO->isNonTemporal() &&
6525 "Non-temporal encoding error!");
6526 // We check here that the size of the memory operand fits within the size of
6527 // the MMO. This is because the MMO might indicate only a possible address
6528 // range instead of specifying the affected memory addresses precisely.
6529 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6532 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6533 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6534 : SDNode(Opc, Order, dl, VTs, Ops),
6535 MemoryVT(memvt), MMO(mmo) {
6536 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6537 MMO->isNonTemporal(), MMO->isInvariant());
6538 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6539 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6542 /// Profile - Gather unique data for the node.
6544 void SDNode::Profile(FoldingSetNodeID &ID) const {
6545 AddNodeIDNode(ID, this);
6550 std::vector<EVT> VTs;
6553 VTs.reserve(MVT::LAST_VALUETYPE);
6554 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6555 VTs.push_back(MVT((MVT::SimpleValueType)i));
6560 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6561 static ManagedStatic<EVTArray> SimpleVTArray;
6562 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6564 /// getValueTypeList - Return a pointer to the specified value type.
6566 const EVT *SDNode::getValueTypeList(EVT VT) {
6567 if (VT.isExtended()) {
6568 sys::SmartScopedLock<true> Lock(*VTMutex);
6569 return &(*EVTs->insert(VT).first);
6571 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6572 "Value type out of range!");
6573 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6577 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6578 /// indicated value. This method ignores uses of other values defined by this
6580 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6581 assert(Value < getNumValues() && "Bad value!");
6583 // TODO: Only iterate over uses of a given value of the node
6584 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6585 if (UI.getUse().getResNo() == Value) {
6592 // Found exactly the right number of uses?
6597 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6598 /// value. This method ignores uses of other values defined by this operation.
6599 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6600 assert(Value < getNumValues() && "Bad value!");
6602 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6603 if (UI.getUse().getResNo() == Value)
6610 /// isOnlyUserOf - Return true if this node is the only use of N.
6612 bool SDNode::isOnlyUserOf(SDNode *N) const {
6614 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6625 /// isOperand - Return true if this node is an operand of N.
6627 bool SDValue::isOperandOf(SDNode *N) const {
6628 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6629 if (*this == N->getOperand(i))
6634 bool SDNode::isOperandOf(SDNode *N) const {
6635 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6636 if (this == N->OperandList[i].getNode())
6641 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6642 /// be a chain) reaches the specified operand without crossing any
6643 /// side-effecting instructions on any chain path. In practice, this looks
6644 /// through token factors and non-volatile loads. In order to remain efficient,
6645 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6646 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6647 unsigned Depth) const {
6648 if (*this == Dest) return true;
6650 // Don't search too deeply, we just want to be able to see through
6651 // TokenFactor's etc.
6652 if (Depth == 0) return false;
6654 // If this is a token factor, all inputs to the TF happen in parallel. If any
6655 // of the operands of the TF does not reach dest, then we cannot do the xform.
6656 if (getOpcode() == ISD::TokenFactor) {
6657 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6658 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6663 // Loads don't have side effects, look through them.
6664 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6665 if (!Ld->isVolatile())
6666 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6671 /// hasPredecessor - Return true if N is a predecessor of this node.
6672 /// N is either an operand of this node, or can be reached by recursively
6673 /// traversing up the operands.
6674 /// NOTE: This is an expensive method. Use it carefully.
6675 bool SDNode::hasPredecessor(const SDNode *N) const {
6676 SmallPtrSet<const SDNode *, 32> Visited;
6677 SmallVector<const SDNode *, 16> Worklist;
6678 return hasPredecessorHelper(N, Visited, Worklist);
6682 SDNode::hasPredecessorHelper(const SDNode *N,
6683 SmallPtrSetImpl<const SDNode *> &Visited,
6684 SmallVectorImpl<const SDNode *> &Worklist) const {
6685 if (Visited.empty()) {
6686 Worklist.push_back(this);
6688 // Take a look in the visited set. If we've already encountered this node
6689 // we needn't search further.
6690 if (Visited.count(N))
6694 // Haven't visited N yet. Continue the search.
6695 while (!Worklist.empty()) {
6696 const SDNode *M = Worklist.pop_back_val();
6697 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6698 SDNode *Op = M->getOperand(i).getNode();
6699 if (Visited.insert(Op).second)
6700 Worklist.push_back(Op);
6709 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6710 assert(Num < NumOperands && "Invalid child # of SDNode!");
6711 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6714 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6715 assert(N->getNumValues() == 1 &&
6716 "Can't unroll a vector with multiple results!");
6718 EVT VT = N->getValueType(0);
6719 unsigned NE = VT.getVectorNumElements();
6720 EVT EltVT = VT.getVectorElementType();
6723 SmallVector<SDValue, 8> Scalars;
6724 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6726 // If ResNE is 0, fully unroll the vector op.
6729 else if (NE > ResNE)
6733 for (i= 0; i != NE; ++i) {
6734 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6735 SDValue Operand = N->getOperand(j);
6736 EVT OperandVT = Operand.getValueType();
6737 if (OperandVT.isVector()) {
6738 // A vector operand; extract a single element.
6739 EVT OperandEltVT = OperandVT.getVectorElementType();
6740 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6743 getConstant(i, dl, TLI->getVectorIdxTy()));
6745 // A scalar operand; just use it as is.
6746 Operands[j] = Operand;
6750 switch (N->getOpcode()) {
6752 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6755 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6762 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6763 getShiftAmountOperand(Operands[0].getValueType(),
6766 case ISD::SIGN_EXTEND_INREG:
6767 case ISD::FP_ROUND_INREG: {
6768 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6769 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6771 getValueType(ExtVT)));
6776 for (; i < ResNE; ++i)
6777 Scalars.push_back(getUNDEF(EltVT));
6779 return getNode(ISD::BUILD_VECTOR, dl,
6780 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6784 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6785 /// location that is 'Dist' units away from the location that the 'Base' load
6786 /// is loading from.
6787 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6788 unsigned Bytes, int Dist) const {
6789 if (LD->getChain() != Base->getChain())
6791 EVT VT = LD->getValueType(0);
6792 if (VT.getSizeInBits() / 8 != Bytes)
6795 SDValue Loc = LD->getOperand(1);
6796 SDValue BaseLoc = Base->getOperand(1);
6797 if (Loc.getOpcode() == ISD::FrameIndex) {
6798 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6800 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6801 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6802 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6803 int FS = MFI->getObjectSize(FI);
6804 int BFS = MFI->getObjectSize(BFI);
6805 if (FS != BFS || FS != (int)Bytes) return false;
6806 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6810 if (isBaseWithConstantOffset(Loc)) {
6811 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6812 if (Loc.getOperand(0) == BaseLoc) {
6813 // If the base location is a simple address with no offset itself, then
6814 // the second load's first add operand should be the base address.
6815 if (LocOffset == Dist * (int)Bytes)
6817 } else if (isBaseWithConstantOffset(BaseLoc)) {
6818 // The base location itself has an offset, so subtract that value from the
6819 // second load's offset before comparing to distance * size.
6821 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6822 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6823 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6828 const GlobalValue *GV1 = nullptr;
6829 const GlobalValue *GV2 = nullptr;
6830 int64_t Offset1 = 0;
6831 int64_t Offset2 = 0;
6832 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6833 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6834 if (isGA1 && isGA2 && GV1 == GV2)
6835 return Offset1 == (Offset2 + Dist*Bytes);
6840 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6841 /// it cannot be inferred.
6842 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6843 // If this is a GlobalAddress + cst, return the alignment.
6844 const GlobalValue *GV;
6845 int64_t GVOffset = 0;
6846 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6847 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6848 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6849 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6850 *TLI->getDataLayout());
6851 unsigned AlignBits = KnownZero.countTrailingOnes();
6852 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6854 return MinAlign(Align, GVOffset);
6857 // If this is a direct reference to a stack slot, use information about the
6858 // stack slot's alignment.
6859 int FrameIdx = 1 << 31;
6860 int64_t FrameOffset = 0;
6861 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6862 FrameIdx = FI->getIndex();
6863 } else if (isBaseWithConstantOffset(Ptr) &&
6864 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6866 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6867 FrameOffset = Ptr.getConstantOperandVal(1);
6870 if (FrameIdx != (1 << 31)) {
6871 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6872 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6880 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6881 /// which is split (or expanded) into two not necessarily identical pieces.
6882 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6883 // Currently all types are split in half.
6885 if (!VT.isVector()) {
6886 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6888 unsigned NumElements = VT.getVectorNumElements();
6889 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6890 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6893 return std::make_pair(LoVT, HiVT);
6896 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6898 std::pair<SDValue, SDValue>
6899 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6901 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6902 N.getValueType().getVectorNumElements() &&
6903 "More vector elements requested than available!");
6905 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6906 getConstant(0, DL, TLI->getVectorIdxTy()));
6907 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6908 getConstant(LoVT.getVectorNumElements(), DL,
6909 TLI->getVectorIdxTy()));
6910 return std::make_pair(Lo, Hi);
6913 void SelectionDAG::ExtractVectorElements(SDValue Op,
6914 SmallVectorImpl<SDValue> &Args,
6915 unsigned Start, unsigned Count) {
6916 EVT VT = Op.getValueType();
6918 Count = VT.getVectorNumElements();
6920 EVT EltVT = VT.getVectorElementType();
6921 EVT IdxTy = TLI->getVectorIdxTy();
6923 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6924 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6925 Op, getConstant(i, SL, IdxTy)));
6929 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6930 unsigned GlobalAddressSDNode::getAddressSpace() const {
6931 return getGlobal()->getType()->getAddressSpace();
6935 Type *ConstantPoolSDNode::getType() const {
6936 if (isMachineConstantPoolEntry())
6937 return Val.MachineCPVal->getType();
6938 return Val.ConstVal->getType();
6941 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6943 unsigned &SplatBitSize,
6945 unsigned MinSplatBits,
6946 bool isBigEndian) const {
6947 EVT VT = getValueType(0);
6948 assert(VT.isVector() && "Expected a vector type");
6949 unsigned sz = VT.getSizeInBits();
6950 if (MinSplatBits > sz)
6953 SplatValue = APInt(sz, 0);
6954 SplatUndef = APInt(sz, 0);
6956 // Get the bits. Bits with undefined values (when the corresponding element
6957 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6958 // in SplatValue. If any of the values are not constant, give up and return
6960 unsigned int nOps = getNumOperands();
6961 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6962 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6964 for (unsigned j = 0; j < nOps; ++j) {
6965 unsigned i = isBigEndian ? nOps-1-j : j;
6966 SDValue OpVal = getOperand(i);
6967 unsigned BitPos = j * EltBitSize;
6969 if (OpVal.getOpcode() == ISD::UNDEF)
6970 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6971 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6972 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6973 zextOrTrunc(sz) << BitPos;
6974 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6975 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6980 // The build_vector is all constants or undefs. Find the smallest element
6981 // size that splats the vector.
6983 HasAnyUndefs = (SplatUndef != 0);
6986 unsigned HalfSize = sz / 2;
6987 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6988 APInt LowValue = SplatValue.trunc(HalfSize);
6989 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6990 APInt LowUndef = SplatUndef.trunc(HalfSize);
6992 // If the two halves do not match (ignoring undef bits), stop here.
6993 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6994 MinSplatBits > HalfSize)
6997 SplatValue = HighValue | LowValue;
6998 SplatUndef = HighUndef & LowUndef;
7007 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7008 if (UndefElements) {
7009 UndefElements->clear();
7010 UndefElements->resize(getNumOperands());
7013 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7014 SDValue Op = getOperand(i);
7015 if (Op.getOpcode() == ISD::UNDEF) {
7017 (*UndefElements)[i] = true;
7018 } else if (!Splatted) {
7020 } else if (Splatted != Op) {
7026 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7027 "Can only have a splat without a constant for all undefs.");
7028 return getOperand(0);
7035 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7036 return dyn_cast_or_null<ConstantSDNode>(
7037 getSplatValue(UndefElements).getNode());
7041 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7042 return dyn_cast_or_null<ConstantFPSDNode>(
7043 getSplatValue(UndefElements).getNode());
7046 bool BuildVectorSDNode::isConstant() const {
7047 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7048 unsigned Opc = getOperand(i).getOpcode();
7049 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7055 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7056 // Find the first non-undef value in the shuffle mask.
7058 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7061 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7063 // Make sure all remaining elements are either undef or the same as the first
7065 for (int Idx = Mask[i]; i != e; ++i)
7066 if (Mask[i] >= 0 && Mask[i] != Idx)
7072 static void checkForCyclesHelper(const SDNode *N,
7073 SmallPtrSetImpl<const SDNode*> &Visited,
7074 SmallPtrSetImpl<const SDNode*> &Checked,
7075 const llvm::SelectionDAG *DAG) {
7076 // If this node has already been checked, don't check it again.
7077 if (Checked.count(N))
7080 // If a node has already been visited on this depth-first walk, reject it as
7082 if (!Visited.insert(N).second) {
7083 errs() << "Detected cycle in SelectionDAG\n";
7084 dbgs() << "Offending node:\n";
7085 N->dumprFull(DAG); dbgs() << "\n";
7089 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7090 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7097 void llvm::checkForCycles(const llvm::SDNode *N,
7098 const llvm::SelectionDAG *DAG,
7106 assert(N && "Checking nonexistent SDNode");
7107 SmallPtrSet<const SDNode*, 32> visited;
7108 SmallPtrSet<const SDNode*, 32> checked;
7109 checkForCyclesHelper(N, visited, checked, DAG);
7114 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7115 checkForCycles(DAG->getRoot().getNode(), DAG, force);