1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59 SDVTList Res = {VTs, NumVTs};
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67 //===----------------------------------------------------------------------===//
68 // ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76 return getValueAPF().bitwiseIsEqual(V);
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
81 assert(VT.isFloatingPoint() && "Can only convert between FP types");
83 // convert modifies in place, so make a copy.
84 APFloat Val2 = APFloat(Val);
86 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87 APFloat::rmNearestTiesToEven,
92 //===----------------------------------------------------------------------===//
94 //===----------------------------------------------------------------------===//
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99 // Look through a bit convert.
100 while (N->getOpcode() == ISD::BITCAST)
101 N = N->getOperand(0).getNode();
103 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105 unsigned i = 0, e = N->getNumOperands();
107 // Skip over all of the undef values.
108 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111 // Do not accept an all-undef vector.
112 if (i == e) return false;
114 // Do not accept build_vectors that aren't all constants or which have non-~0
115 // elements. We have to be a bit careful here, as the type of the constant
116 // may not be the same as the type of the vector elements due to type
117 // legalization (the elements are promoted to a legal type for the target and
118 // a vector of a type may be legal when the base element type is not).
119 // We only want to check enough bits to cover the vector elements, because
120 // we care if the resultant vector is all ones, not whether the individual
122 SDValue NotZero = N->getOperand(i);
123 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133 // Okay, we have at least one ~0 value, check to see if the rest match or are
134 // undefs. Even with the above element type twiddling, this should be OK, as
135 // the same type legalization should have applied to all the elements.
136 for (++i; i != e; ++i)
137 if (N->getOperand(i) != NotZero &&
138 N->getOperand(i).getOpcode() != ISD::UNDEF)
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147 // Look through a bit convert.
148 while (N->getOpcode() == ISD::BITCAST)
149 N = N->getOperand(0).getNode();
151 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153 bool IsAllUndef = true;
154 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept build_vectors that aren't all constants or which have non-0
159 // elements. We have to be a bit careful here, as the type of the constant
160 // may not be the same as the type of the vector elements due to type
161 // legalization (the elements are promoted to a legal type for the target
162 // and a vector of a type may be legal when the base element type is not).
163 // We only want to check enough bits to cover the vector elements, because
164 // we care if the resultant vector is all zeros, not whether the individual
166 SDValue Zero = N->getOperand(i);
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
191 SDValue Op = N->getOperand(i);
192 if (Op.getOpcode() == ISD::UNDEF)
194 if (!isa<ConstantSDNode>(Op))
200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
201 /// all ConstantFPSDNode or undef.
202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
207 SDValue Op = N->getOperand(i);
208 if (Op.getOpcode() == ISD::UNDEF)
210 if (!isa<ConstantFPSDNode>(Op))
216 /// isScalarToVector - Return true if the specified node is a
217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
218 /// element is not an undef.
219 bool ISD::isScalarToVector(const SDNode *N) {
220 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
223 if (N->getOpcode() != ISD::BUILD_VECTOR)
225 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
227 unsigned NumElems = N->getNumOperands();
230 for (unsigned i = 1; i < NumElems; ++i) {
231 SDValue V = N->getOperand(i);
232 if (V.getOpcode() != ISD::UNDEF)
238 /// allOperandsUndef - Return true if the node has at least one operand
239 /// and all operands of the specified node are ISD::UNDEF.
240 bool ISD::allOperandsUndef(const SDNode *N) {
241 // Return false if the node has no operands.
242 // This is "logically inconsistent" with the definition of "all" but
243 // is probably the desired behavior.
244 if (N->getNumOperands() == 0)
247 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
248 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
257 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
259 return ISD::SIGN_EXTEND;
261 return ISD::ZERO_EXTEND;
266 llvm_unreachable("Invalid LoadExtType");
269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
270 /// when given the operation for (X op Y).
271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
272 // To perform this operation, we just need to swap the L and G bits of the
274 unsigned OldL = (Operation >> 2) & 1;
275 unsigned OldG = (Operation >> 1) & 1;
276 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
277 (OldL << 1) | // New G bit
278 (OldG << 2)); // New L bit.
281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
282 /// 'op' is a valid SetCC operation.
283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
284 unsigned Operation = Op;
286 Operation ^= 7; // Flip L, G, E bits, but not U.
288 Operation ^= 15; // Flip all of the condition bits.
290 if (Operation > ISD::SETTRUE2)
291 Operation &= ~8; // Don't let N and U bits get set.
293 return ISD::CondCode(Operation);
297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
298 /// signed operation and 2 if the result is an unsigned comparison. Return zero
299 /// if the operation does not depend on the sign of the input (setne and seteq).
300 static int isSignedOp(ISD::CondCode Opcode) {
302 default: llvm_unreachable("Illegal integer setcc operation!");
304 case ISD::SETNE: return 0;
308 case ISD::SETGE: return 1;
312 case ISD::SETUGE: return 2;
316 /// getSetCCOrOperation - Return the result of a logical OR between different
317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
318 /// returns SETCC_INVALID if it is not possible to represent the resultant
320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
322 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323 // Cannot fold a signed integer setcc with an unsigned integer setcc.
324 return ISD::SETCC_INVALID;
326 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
328 // If the N and U bits get set then the resultant comparison DOES suddenly
329 // care about orderedness, and is true when ordered.
330 if (Op > ISD::SETTRUE2)
331 Op &= ~16; // Clear the U bit if the N bit is set.
333 // Canonicalize illegal integer setcc's.
334 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
337 return ISD::CondCode(Op);
340 /// getSetCCAndOperation - Return the result of a logical AND between different
341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
342 /// function returns zero if it is not possible to represent the resultant
344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
346 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
347 // Cannot fold a signed setcc with an unsigned setcc.
348 return ISD::SETCC_INVALID;
350 // Combine all of the condition bits.
351 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
353 // Canonicalize illegal integer setcc's.
357 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
358 case ISD::SETOEQ: // SETEQ & SETU[LG]E
359 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
360 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
361 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
368 //===----------------------------------------------------------------------===//
369 // SDNode Profile Support
370 //===----------------------------------------------------------------------===//
372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
379 /// solely with their pointer.
380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
381 ID.AddPointer(VTList.VTs);
384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
387 ArrayRef<SDValue> Ops) {
388 for (auto& Op : Ops) {
389 ID.AddPointer(Op.getNode());
390 ID.AddInteger(Op.getResNo());
394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
397 ArrayRef<SDUse> Ops) {
398 for (auto& Op : Ops) {
399 ID.AddPointer(Op.getNode());
400 ID.AddInteger(Op.getResNo());
404 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
408 ID.AddBoolean(exact);
411 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
412 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
413 bool nuw, bool nsw, bool exact) {
414 if (isBinOpWithFlags(Opcode))
415 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
419 SDVTList VTList, ArrayRef<SDValue> OpList) {
420 AddNodeIDOpcode(ID, OpC);
421 AddNodeIDValueTypes(ID, VTList);
422 AddNodeIDOperands(ID, OpList);
425 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
427 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
428 switch (N->getOpcode()) {
429 case ISD::TargetExternalSymbol:
430 case ISD::ExternalSymbol:
431 llvm_unreachable("Should only be used on nodes with operands");
432 default: break; // Normal nodes don't need extra info.
433 case ISD::TargetConstant:
434 case ISD::Constant: {
435 const ConstantSDNode *C = cast<ConstantSDNode>(N);
436 ID.AddPointer(C->getConstantIntValue());
437 ID.AddBoolean(C->isOpaque());
440 case ISD::TargetConstantFP:
441 case ISD::ConstantFP: {
442 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
445 case ISD::TargetGlobalAddress:
446 case ISD::GlobalAddress:
447 case ISD::TargetGlobalTLSAddress:
448 case ISD::GlobalTLSAddress: {
449 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
450 ID.AddPointer(GA->getGlobal());
451 ID.AddInteger(GA->getOffset());
452 ID.AddInteger(GA->getTargetFlags());
453 ID.AddInteger(GA->getAddressSpace());
456 case ISD::BasicBlock:
457 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
460 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
462 case ISD::RegisterMask:
463 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
466 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
468 case ISD::FrameIndex:
469 case ISD::TargetFrameIndex:
470 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
473 case ISD::TargetJumpTable:
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
475 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
477 case ISD::ConstantPool:
478 case ISD::TargetConstantPool: {
479 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
480 ID.AddInteger(CP->getAlignment());
481 ID.AddInteger(CP->getOffset());
482 if (CP->isMachineConstantPoolEntry())
483 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
485 ID.AddPointer(CP->getConstVal());
486 ID.AddInteger(CP->getTargetFlags());
489 case ISD::TargetIndex: {
490 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
491 ID.AddInteger(TI->getIndex());
492 ID.AddInteger(TI->getOffset());
493 ID.AddInteger(TI->getTargetFlags());
497 const LoadSDNode *LD = cast<LoadSDNode>(N);
498 ID.AddInteger(LD->getMemoryVT().getRawBits());
499 ID.AddInteger(LD->getRawSubclassData());
500 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
504 const StoreSDNode *ST = cast<StoreSDNode>(N);
505 ID.AddInteger(ST->getMemoryVT().getRawBits());
506 ID.AddInteger(ST->getRawSubclassData());
507 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
518 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
519 AddBinaryNodeIDCustom(
520 ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
521 BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
524 case ISD::ATOMIC_CMP_SWAP:
525 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
526 case ISD::ATOMIC_SWAP:
527 case ISD::ATOMIC_LOAD_ADD:
528 case ISD::ATOMIC_LOAD_SUB:
529 case ISD::ATOMIC_LOAD_AND:
530 case ISD::ATOMIC_LOAD_OR:
531 case ISD::ATOMIC_LOAD_XOR:
532 case ISD::ATOMIC_LOAD_NAND:
533 case ISD::ATOMIC_LOAD_MIN:
534 case ISD::ATOMIC_LOAD_MAX:
535 case ISD::ATOMIC_LOAD_UMIN:
536 case ISD::ATOMIC_LOAD_UMAX:
537 case ISD::ATOMIC_LOAD:
538 case ISD::ATOMIC_STORE: {
539 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
540 ID.AddInteger(AT->getMemoryVT().getRawBits());
541 ID.AddInteger(AT->getRawSubclassData());
542 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
545 case ISD::PREFETCH: {
546 const MemSDNode *PF = cast<MemSDNode>(N);
547 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
550 case ISD::VECTOR_SHUFFLE: {
551 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
552 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
554 ID.AddInteger(SVN->getMaskElt(i));
557 case ISD::TargetBlockAddress:
558 case ISD::BlockAddress: {
559 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
560 ID.AddPointer(BA->getBlockAddress());
561 ID.AddInteger(BA->getOffset());
562 ID.AddInteger(BA->getTargetFlags());
565 } // end switch (N->getOpcode())
567 // Target specific memory nodes could also have address spaces to check.
568 if (N->isTargetMemoryOpcode())
569 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
575 AddNodeIDOpcode(ID, N->getOpcode());
576 // Add the return value info.
577 AddNodeIDValueTypes(ID, N->getVTList());
578 // Add the operand info.
579 AddNodeIDOperands(ID, N->ops());
581 // Handle SDNode leafs with special info.
582 AddNodeIDCustom(ID, N);
585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
586 /// the CSE map that carries volatility, temporalness, indexing mode, and
587 /// extension/truncation information.
589 static inline unsigned
590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
591 bool isNonTemporal, bool isInvariant) {
592 assert((ConvType & 3) == ConvType &&
593 "ConvType may not require more than 2 bits!");
594 assert((AM & 7) == AM &&
595 "AM may not require more than 3 bits!");
599 (isNonTemporal << 6) |
603 //===----------------------------------------------------------------------===//
604 // SelectionDAG Class
605 //===----------------------------------------------------------------------===//
607 /// doNotCSE - Return true if CSE should not be performed for this node.
608 static bool doNotCSE(SDNode *N) {
609 if (N->getValueType(0) == MVT::Glue)
610 return true; // Never CSE anything that produces a flag.
612 switch (N->getOpcode()) {
614 case ISD::HANDLENODE:
616 return true; // Never CSE these nodes.
619 // Check that remaining values produced are not flags.
620 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
621 if (N->getValueType(i) == MVT::Glue)
622 return true; // Never CSE anything that produces a flag.
627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
629 void SelectionDAG::RemoveDeadNodes() {
630 // Create a dummy node (which is not added to allnodes), that adds a reference
631 // to the root node, preventing it from being deleted.
632 HandleSDNode Dummy(getRoot());
634 SmallVector<SDNode*, 128> DeadNodes;
636 // Add all obviously-dead nodes to the DeadNodes worklist.
637 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
639 DeadNodes.push_back(I);
641 RemoveDeadNodes(DeadNodes);
643 // If the root changed (e.g. it was a dead load, update the root).
644 setRoot(Dummy.getValue());
647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
648 /// given list, and any nodes that become unreachable as a result.
649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
651 // Process the worklist, deleting the nodes and adding their uses to the
653 while (!DeadNodes.empty()) {
654 SDNode *N = DeadNodes.pop_back_val();
656 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
657 DUL->NodeDeleted(N, nullptr);
659 // Take the node out of the appropriate CSE map.
660 RemoveNodeFromCSEMaps(N);
662 // Next, brutally remove the operand list. This is safe to do, as there are
663 // no cycles in the graph.
664 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
666 SDNode *Operand = Use.getNode();
669 // Now that we removed this operand, see if there are no uses of it left.
670 if (Operand->use_empty())
671 DeadNodes.push_back(Operand);
678 void SelectionDAG::RemoveDeadNode(SDNode *N){
679 SmallVector<SDNode*, 16> DeadNodes(1, N);
681 // Create a dummy node that adds a reference to the root node, preventing
682 // it from being deleted. (This matters if the root is an operand of the
684 HandleSDNode Dummy(getRoot());
686 RemoveDeadNodes(DeadNodes);
689 void SelectionDAG::DeleteNode(SDNode *N) {
690 // First take this out of the appropriate CSE map.
691 RemoveNodeFromCSEMaps(N);
693 // Finally, remove uses due to operands of this node, remove from the
694 // AllNodes list, and delete the node.
695 DeleteNodeNotInCSEMaps(N);
698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
699 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
700 assert(N->use_empty() && "Cannot delete a node that is not dead!");
702 // Drop all of the operands and decrement used node's use counts.
708 void SDDbgInfo::erase(const SDNode *Node) {
709 DbgValMapType::iterator I = DbgValMap.find(Node);
710 if (I == DbgValMap.end())
712 for (auto &Val: I->second)
713 Val->setIsInvalidated();
717 void SelectionDAG::DeallocateNode(SDNode *N) {
718 if (N->OperandsNeedDelete)
719 delete[] N->OperandList;
721 // Set the opcode to DELETED_NODE to help catch bugs when node
722 // memory is reallocated.
723 N->NodeType = ISD::DELETED_NODE;
725 NodeAllocator.Deallocate(AllNodes.remove(N));
727 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
728 // them and forget about that node.
733 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
734 static void VerifySDNode(SDNode *N) {
735 switch (N->getOpcode()) {
738 case ISD::BUILD_PAIR: {
739 EVT VT = N->getValueType(0);
740 assert(N->getNumValues() == 1 && "Too many results!");
741 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
742 "Wrong return type!");
743 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
744 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
745 "Mismatched operand types!");
746 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
747 "Wrong operand type!");
748 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
749 "Wrong return type size");
752 case ISD::BUILD_VECTOR: {
753 assert(N->getNumValues() == 1 && "Too many results!");
754 assert(N->getValueType(0).isVector() && "Wrong return type!");
755 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
756 "Wrong number of operands!");
757 EVT EltVT = N->getValueType(0).getVectorElementType();
758 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
759 assert((I->getValueType() == EltVT ||
760 (EltVT.isInteger() && I->getValueType().isInteger() &&
761 EltVT.bitsLE(I->getValueType()))) &&
762 "Wrong operand type!");
763 assert(I->getValueType() == N->getOperand(0).getValueType() &&
764 "Operands must all have the same type");
772 /// \brief Insert a newly allocated node into the DAG.
774 /// Handles insertion into the all nodes list and CSE map, as well as
775 /// verification and other common operations when a new node is allocated.
776 void SelectionDAG::InsertNode(SDNode *N) {
777 AllNodes.push_back(N);
783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
784 /// correspond to it. This is useful when we're about to delete or repurpose
785 /// the node. We don't want future request for structurally identical nodes
786 /// to return N anymore.
787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
789 switch (N->getOpcode()) {
790 case ISD::HANDLENODE: return false; // noop.
792 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
793 "Cond code doesn't exist!");
794 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
795 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
797 case ISD::ExternalSymbol:
798 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
800 case ISD::TargetExternalSymbol: {
801 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
802 Erased = TargetExternalSymbols.erase(
803 std::pair<std::string,unsigned char>(ESN->getSymbol(),
804 ESN->getTargetFlags()));
807 case ISD::VALUETYPE: {
808 EVT VT = cast<VTSDNode>(N)->getVT();
809 if (VT.isExtended()) {
810 Erased = ExtendedValueTypeNodes.erase(VT);
812 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
813 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
818 // Remove it from the CSE Map.
819 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
820 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
821 Erased = CSEMap.RemoveNode(N);
825 // Verify that the node was actually in one of the CSE maps, unless it has a
826 // flag result (which cannot be CSE'd) or is one of the special cases that are
827 // not subject to CSE.
828 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
829 !N->isMachineOpcode() && !doNotCSE(N)) {
832 llvm_unreachable("Node is not in map!");
838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
840 /// node already exists, in which case transfer all its users to the existing
841 /// node. This transfer can potentially trigger recursive merging.
844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
845 // For node types that aren't CSE'd, just act as if no identical node
848 SDNode *Existing = CSEMap.GetOrInsertNode(N);
850 // If there was already an existing matching node, use ReplaceAllUsesWith
851 // to replace the dead one with the existing one. This can cause
852 // recursive merging of other unrelated nodes down the line.
853 ReplaceAllUsesWith(N, Existing);
855 // N is now dead. Inform the listeners and delete it.
856 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
857 DUL->NodeDeleted(N, Existing);
858 DeleteNodeNotInCSEMaps(N);
863 // If the node doesn't already exist, we updated it. Inform listeners.
864 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
869 /// were replaced with those specified. If this node is never memoized,
870 /// return null, otherwise return a pointer to the slot it would take. If a
871 /// node already exists with these operands, the slot will be non-null.
872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
877 SDValue Ops[] = { Op };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
886 /// were replaced with those specified. If this node is never memoized,
887 /// return null, otherwise return a pointer to the slot it would take. If a
888 /// node already exists with these operands, the slot will be non-null.
889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
890 SDValue Op1, SDValue Op2,
895 SDValue Ops[] = { Op1, Op2 };
897 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
898 AddNodeIDCustom(ID, N);
899 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
905 /// were replaced with those specified. If this node is never memoized,
906 /// return null, otherwise return a pointer to the slot it would take. If a
907 /// node already exists with these operands, the slot will be non-null.
908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
914 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
915 AddNodeIDCustom(ID, N);
916 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
920 /// getEVTAlignment - Compute the default alignment value for the
923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
924 Type *Ty = VT == MVT::iPTR ?
925 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
926 VT.getTypeForEVT(*getContext());
928 return TLI->getDataLayout()->getABITypeAlignment(Ty);
931 // EntryNode could meaningfully have debug info if we can find it...
932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
933 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
934 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
935 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
936 UpdateListeners(nullptr) {
937 AllNodes.push_back(&EntryNode);
938 DbgInfo = new SDDbgInfo();
941 void SelectionDAG::init(MachineFunction &mf) {
943 TLI = getSubtarget().getTargetLowering();
944 TSI = getSubtarget().getSelectionDAGInfo();
945 Context = &mf.getFunction()->getContext();
948 SelectionDAG::~SelectionDAG() {
949 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
954 void SelectionDAG::allnodes_clear() {
955 assert(&*AllNodes.begin() == &EntryNode);
956 AllNodes.remove(AllNodes.begin());
957 while (!AllNodes.empty())
958 DeallocateNode(AllNodes.begin());
961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
962 SDVTList VTs, SDValue N1,
963 SDValue N2, bool nuw, bool nsw,
965 if (isBinOpWithFlags(Opcode)) {
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
968 FN->Flags.setNoUnsignedWrap(nuw);
969 FN->Flags.setNoSignedWrap(nsw);
970 FN->Flags.setExact(exact);
975 BinarySDNode *N = new (NodeAllocator)
976 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
982 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
984 switch (N->getOpcode()) {
987 case ISD::ConstantFP:
988 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
989 "debug location. Use another overload.");
995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
996 DebugLoc DL, void *&InsertPos) {
997 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
999 switch (N->getOpcode()) {
1000 default: break; // Process only regular (non-target) constant nodes.
1002 case ISD::ConstantFP:
1003 // Erase debug location from the node if the node is used at several
1004 // different places to do not propagate one location to all uses as it
1005 // leads to incorrect debug info.
1006 if (N->getDebugLoc() != DL)
1007 N->setDebugLoc(DebugLoc());
1014 void SelectionDAG::clear() {
1016 OperandAllocator.Reset();
1019 ExtendedValueTypeNodes.clear();
1020 ExternalSymbols.clear();
1021 TargetExternalSymbols.clear();
1022 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1023 static_cast<CondCodeSDNode*>(nullptr));
1024 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1025 static_cast<SDNode*>(nullptr));
1027 EntryNode.UseList = nullptr;
1028 AllNodes.push_back(&EntryNode);
1029 Root = getEntryNode();
1033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1034 return VT.bitsGT(Op.getValueType()) ?
1035 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1036 getNode(ISD::TRUNCATE, DL, VT, Op);
1039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1040 return VT.bitsGT(Op.getValueType()) ?
1041 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1042 getNode(ISD::TRUNCATE, DL, VT, Op);
1045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1046 return VT.bitsGT(Op.getValueType()) ?
1047 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1048 getNode(ISD::TRUNCATE, DL, VT, Op);
1051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1053 if (VT.bitsLE(Op.getValueType()))
1054 return getNode(ISD::TRUNCATE, SL, VT, Op);
1056 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1057 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1061 assert(!VT.isVector() &&
1062 "getZeroExtendInReg should use the vector element type instead of "
1063 "the vector type!");
1064 if (Op.getValueType() == VT) return Op;
1065 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1066 APInt Imm = APInt::getLowBitsSet(BitWidth,
1067 VT.getSizeInBits());
1068 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1069 getConstant(Imm, DL, Op.getValueType()));
1072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1073 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1074 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1075 "The sizes of the input and result must match in order to perform the "
1076 "extend in-register.");
1077 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1078 "The destination vector type must have fewer lanes than the input.");
1079 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1083 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1084 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1085 "The sizes of the input and result must match in order to perform the "
1086 "extend in-register.");
1087 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1088 "The destination vector type must have fewer lanes than the input.");
1089 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1093 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1094 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1095 "The sizes of the input and result must match in order to perform the "
1096 "extend in-register.");
1097 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1098 "The destination vector type must have fewer lanes than the input.");
1099 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1105 EVT EltVT = VT.getScalarType();
1107 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1108 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1112 EVT EltVT = VT.getScalarType();
1114 switch (TLI->getBooleanContents(VT)) {
1115 case TargetLowering::ZeroOrOneBooleanContent:
1116 case TargetLowering::UndefinedBooleanContent:
1117 TrueValue = getConstant(1, DL, VT);
1119 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1120 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1124 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1129 EVT EltVT = VT.getScalarType();
1130 assert((EltVT.getSizeInBits() >= 64 ||
1131 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1132 "getConstant with a uint64_t value that doesn't fit in the type!");
1133 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1139 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1143 bool isT, bool isO) {
1144 assert(VT.isInteger() && "Cannot create FP integer constant!");
1146 EVT EltVT = VT.getScalarType();
1147 const ConstantInt *Elt = &Val;
1149 // In some cases the vector type is legal but the element type is illegal and
1150 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1151 // inserted value (the type does not need to match the vector element type).
1152 // Any extra bits introduced will be truncated away.
1153 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1154 TargetLowering::TypePromoteInteger) {
1155 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1156 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1157 Elt = ConstantInt::get(*getContext(), NewVal);
1159 // In other cases the element type is illegal and needs to be expanded, for
1160 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1161 // the value into n parts and use a vector type with n-times the elements.
1162 // Then bitcast to the type requested.
1163 // Legalizing constants too early makes the DAGCombiner's job harder so we
1164 // only legalize if the DAG tells us we must produce legal types.
1165 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1166 TLI->getTypeAction(*getContext(), EltVT) ==
1167 TargetLowering::TypeExpandInteger) {
1168 APInt NewVal = Elt->getValue();
1169 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1170 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1171 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1172 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1174 // Check the temporary vector is the correct size. If this fails then
1175 // getTypeToTransformTo() probably returned a type whose size (in bits)
1176 // isn't a power-of-2 factor of the requested type size.
1177 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1179 SmallVector<SDValue, 2> EltParts;
1180 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1181 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1182 .trunc(ViaEltSizeInBits), DL,
1183 ViaEltVT, isT, isO));
1186 // EltParts is currently in little endian order. If we actually want
1187 // big-endian order then reverse it now.
1188 if (TLI->isBigEndian())
1189 std::reverse(EltParts.begin(), EltParts.end());
1191 // The elements must be reversed when the element order is different
1192 // to the endianness of the elements (because the BITCAST is itself a
1193 // vector shuffle in this situation). However, we do not need any code to
1194 // perform this reversal because getConstant() is producing a vector
1196 // This situation occurs in MIPS MSA.
1198 SmallVector<SDValue, 8> Ops;
1199 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1200 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1202 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1203 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1208 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1209 "APInt size does not match type size!");
1210 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1211 FoldingSetNodeID ID;
1212 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1216 SDNode *N = nullptr;
1217 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1219 return SDValue(N, 0);
1222 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1224 CSEMap.InsertNode(N, IP);
1228 SDValue Result(N, 0);
1229 if (VT.isVector()) {
1230 SmallVector<SDValue, 8> Ops;
1231 Ops.assign(VT.getVectorNumElements(), Result);
1232 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1238 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1243 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1248 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1250 EVT EltVT = VT.getScalarType();
1252 // Do the map lookup using the actual bit pattern for the floating point
1253 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1254 // we don't have issues with SNANs.
1255 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1256 FoldingSetNodeID ID;
1257 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1260 SDNode *N = nullptr;
1261 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1263 return SDValue(N, 0);
1266 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1268 CSEMap.InsertNode(N, IP);
1272 SDValue Result(N, 0);
1273 if (VT.isVector()) {
1274 SmallVector<SDValue, 8> Ops;
1275 Ops.assign(VT.getVectorNumElements(), Result);
1276 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1283 EVT EltVT = VT.getScalarType();
1284 if (EltVT==MVT::f32)
1285 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f64)
1287 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1288 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1291 APFloat apf = APFloat(Val);
1292 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1294 return getConstantFP(apf, DL, VT, isTarget);
1296 llvm_unreachable("Unsupported type in getConstantFP");
1299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1300 EVT VT, int64_t Offset,
1302 unsigned char TargetFlags) {
1303 assert((TargetFlags == 0 || isTargetGA) &&
1304 "Cannot set target flags on target-independent globals");
1306 // Truncate (with sign-extension) the offset value to the pointer size.
1307 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1309 Offset = SignExtend64(Offset, BitWidth);
1312 if (GV->isThreadLocal())
1313 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1315 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1320 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1322 ID.AddInteger(GV->getType()->getAddressSpace());
1324 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1325 return SDValue(E, 0);
1327 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1328 DL.getDebugLoc(), GV, VT,
1329 Offset, TargetFlags);
1330 CSEMap.InsertNode(N, IP);
1332 return SDValue(N, 0);
1335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1336 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1337 FoldingSetNodeID ID;
1338 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1342 return SDValue(E, 0);
1344 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1345 CSEMap.InsertNode(N, IP);
1347 return SDValue(N, 0);
1350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1351 unsigned char TargetFlags) {
1352 assert((TargetFlags == 0 || isTarget) &&
1353 "Cannot set target flags on target-independent jump tables");
1354 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1355 FoldingSetNodeID ID;
1356 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1358 ID.AddInteger(TargetFlags);
1360 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1361 return SDValue(E, 0);
1363 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1365 CSEMap.InsertNode(N, IP);
1367 return SDValue(N, 0);
1370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1371 unsigned Alignment, int Offset,
1373 unsigned char TargetFlags) {
1374 assert((TargetFlags == 0 || isTarget) &&
1375 "Cannot set target flags on target-independent globals");
1377 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1378 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1379 FoldingSetNodeID ID;
1380 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1381 ID.AddInteger(Alignment);
1382 ID.AddInteger(Offset);
1384 ID.AddInteger(TargetFlags);
1386 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1387 return SDValue(E, 0);
1389 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1390 Alignment, TargetFlags);
1391 CSEMap.InsertNode(N, IP);
1393 return SDValue(N, 0);
1397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1398 unsigned Alignment, int Offset,
1400 unsigned char TargetFlags) {
1401 assert((TargetFlags == 0 || isTarget) &&
1402 "Cannot set target flags on target-independent globals");
1404 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1405 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1408 ID.AddInteger(Alignment);
1409 ID.AddInteger(Offset);
1410 C->addSelectionDAGCSEId(ID);
1411 ID.AddInteger(TargetFlags);
1413 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1414 return SDValue(E, 0);
1416 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1417 Alignment, TargetFlags);
1418 CSEMap.InsertNode(N, IP);
1420 return SDValue(N, 0);
1423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1424 unsigned char TargetFlags) {
1425 FoldingSetNodeID ID;
1426 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1427 ID.AddInteger(Index);
1428 ID.AddInteger(Offset);
1429 ID.AddInteger(TargetFlags);
1431 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1432 return SDValue(E, 0);
1434 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1436 CSEMap.InsertNode(N, IP);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1442 FoldingSetNodeID ID;
1443 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1446 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1447 return SDValue(E, 0);
1449 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1450 CSEMap.InsertNode(N, IP);
1452 return SDValue(N, 0);
1455 SDValue SelectionDAG::getValueType(EVT VT) {
1456 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1457 ValueTypeNodes.size())
1458 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1460 SDNode *&N = VT.isExtended() ?
1461 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1463 if (N) return SDValue(N, 0);
1464 N = new (NodeAllocator) VTSDNode(VT);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1470 SDNode *&N = ExternalSymbols[Sym];
1471 if (N) return SDValue(N, 0);
1472 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1474 return SDValue(N, 0);
1477 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1478 unsigned char TargetFlags) {
1480 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1482 if (N) return SDValue(N, 0);
1483 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1485 return SDValue(N, 0);
1488 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1489 if ((unsigned)Cond >= CondCodeNodes.size())
1490 CondCodeNodes.resize(Cond+1);
1492 if (!CondCodeNodes[Cond]) {
1493 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1494 CondCodeNodes[Cond] = N;
1498 return SDValue(CondCodeNodes[Cond], 0);
1501 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1502 // the shuffle mask M that point at N1 to point at N2, and indices that point
1503 // N2 to point at N1.
1504 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1506 ShuffleVectorSDNode::commuteMask(M);
1509 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1510 SDValue N2, const int *Mask) {
1511 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1512 "Invalid VECTOR_SHUFFLE");
1514 // Canonicalize shuffle undef, undef -> undef
1515 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1516 return getUNDEF(VT);
1518 // Validate that all indices in Mask are within the range of the elements
1519 // input to the shuffle.
1520 unsigned NElts = VT.getVectorNumElements();
1521 SmallVector<int, 8> MaskVec;
1522 for (unsigned i = 0; i != NElts; ++i) {
1523 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1524 MaskVec.push_back(Mask[i]);
1527 // Canonicalize shuffle v, v -> v, undef
1530 for (unsigned i = 0; i != NElts; ++i)
1531 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1534 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1535 if (N1.getOpcode() == ISD::UNDEF)
1536 commuteShuffle(N1, N2, MaskVec);
1538 // If shuffling a splat, try to blend the splat instead. We do this here so
1539 // that even when this arises during lowering we don't have to re-handle it.
1540 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1541 BitVector UndefElements;
1542 SDValue Splat = BV->getSplatValue(&UndefElements);
1546 for (int i = 0; i < (int)NElts; ++i) {
1547 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1550 // If this input comes from undef, mark it as such.
1551 if (UndefElements[MaskVec[i] - Offset]) {
1556 // If we can blend a non-undef lane, use that instead.
1557 if (!UndefElements[i])
1558 MaskVec[i] = i + Offset;
1561 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1562 BlendSplat(N1BV, 0);
1563 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1564 BlendSplat(N2BV, NElts);
1566 // Canonicalize all index into lhs, -> shuffle lhs, undef
1567 // Canonicalize all index into rhs, -> shuffle rhs, undef
1568 bool AllLHS = true, AllRHS = true;
1569 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1570 for (unsigned i = 0; i != NElts; ++i) {
1571 if (MaskVec[i] >= (int)NElts) {
1576 } else if (MaskVec[i] >= 0) {
1580 if (AllLHS && AllRHS)
1581 return getUNDEF(VT);
1582 if (AllLHS && !N2Undef)
1586 commuteShuffle(N1, N2, MaskVec);
1588 // Reset our undef status after accounting for the mask.
1589 N2Undef = N2.getOpcode() == ISD::UNDEF;
1590 // Re-check whether both sides ended up undef.
1591 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1592 return getUNDEF(VT);
1594 // If Identity shuffle return that node.
1595 bool Identity = true, AllSame = true;
1596 for (unsigned i = 0; i != NElts; ++i) {
1597 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1598 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1600 if (Identity && NElts)
1603 // Shuffling a constant splat doesn't change the result.
1607 // Look through any bitcasts. We check that these don't change the number
1608 // (and size) of elements and just changes their types.
1609 while (V.getOpcode() == ISD::BITCAST)
1610 V = V->getOperand(0);
1612 // A splat should always show up as a build vector node.
1613 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1614 BitVector UndefElements;
1615 SDValue Splat = BV->getSplatValue(&UndefElements);
1616 // If this is a splat of an undef, shuffling it is also undef.
1617 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1618 return getUNDEF(VT);
1621 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1623 // We only have a splat which can skip shuffles if there is a splatted
1624 // value and no undef lanes rearranged by the shuffle.
1625 if (Splat && UndefElements.none()) {
1626 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1627 // number of elements match or the value splatted is a zero constant.
1630 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1631 if (C->isNullValue())
1635 // If the shuffle itself creates a splat, build the vector directly.
1636 if (AllSame && SameNumElts) {
1637 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1638 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1640 EVT BuildVT = BV->getValueType(0);
1641 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1643 // We may have jumped through bitcasts, so the type of the
1644 // BUILD_VECTOR may not match the type of the shuffle.
1646 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1652 FoldingSetNodeID ID;
1653 SDValue Ops[2] = { N1, N2 };
1654 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1655 for (unsigned i = 0; i != NElts; ++i)
1656 ID.AddInteger(MaskVec[i]);
1659 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1660 return SDValue(E, 0);
1662 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1663 // SDNode doesn't have access to it. This memory will be "leaked" when
1664 // the node is deallocated, but recovered when the NodeAllocator is released.
1665 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1666 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1668 ShuffleVectorSDNode *N =
1669 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1670 dl.getDebugLoc(), N1, N2,
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1678 MVT VT = SV.getSimpleValueType(0);
1679 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1680 ShuffleVectorSDNode::commuteMask(MaskVec);
1682 SDValue Op0 = SV.getOperand(0);
1683 SDValue Op1 = SV.getOperand(1);
1684 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1687 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1688 SDValue Val, SDValue DTy,
1689 SDValue STy, SDValue Rnd, SDValue Sat,
1690 ISD::CvtCode Code) {
1691 // If the src and dest types are the same and the conversion is between
1692 // integer types of the same sign or two floats, no conversion is necessary.
1694 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1697 FoldingSetNodeID ID;
1698 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1699 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1701 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1702 return SDValue(E, 0);
1704 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1707 CSEMap.InsertNode(N, IP);
1709 return SDValue(N, 0);
1712 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1713 FoldingSetNodeID ID;
1714 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1715 ID.AddInteger(RegNo);
1717 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1718 return SDValue(E, 0);
1720 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1721 CSEMap.InsertNode(N, IP);
1723 return SDValue(N, 0);
1726 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1727 FoldingSetNodeID ID;
1728 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1729 ID.AddPointer(RegMask);
1731 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1741 FoldingSetNodeID ID;
1742 SDValue Ops[] = { Root };
1743 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1744 ID.AddPointer(Label);
1746 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1747 return SDValue(E, 0);
1749 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1750 dl.getDebugLoc(), Root, Label);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1757 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1760 unsigned char TargetFlags) {
1761 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1763 FoldingSetNodeID ID;
1764 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1766 ID.AddInteger(Offset);
1767 ID.AddInteger(TargetFlags);
1769 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1772 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1774 CSEMap.InsertNode(N, IP);
1776 return SDValue(N, 0);
1779 SDValue SelectionDAG::getSrcValue(const Value *V) {
1780 assert((!V || V->getType()->isPointerTy()) &&
1781 "SrcValue is not a pointer?");
1783 FoldingSetNodeID ID;
1784 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1788 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1789 return SDValue(E, 0);
1791 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1792 CSEMap.InsertNode(N, IP);
1794 return SDValue(N, 0);
1797 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1798 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1799 FoldingSetNodeID ID;
1800 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1804 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1805 return SDValue(E, 0);
1807 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1808 CSEMap.InsertNode(N, IP);
1810 return SDValue(N, 0);
1813 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1814 if (VT == V.getValueType())
1817 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1820 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1821 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1822 unsigned SrcAS, unsigned DestAS) {
1823 SDValue Ops[] = {Ptr};
1824 FoldingSetNodeID ID;
1825 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1826 ID.AddInteger(SrcAS);
1827 ID.AddInteger(DestAS);
1830 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1831 return SDValue(E, 0);
1833 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1835 VT, Ptr, SrcAS, DestAS);
1836 CSEMap.InsertNode(N, IP);
1838 return SDValue(N, 0);
1841 /// getShiftAmountOperand - Return the specified value casted to
1842 /// the target's desired shift amount type.
1843 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1844 EVT OpTy = Op.getValueType();
1845 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1846 if (OpTy == ShTy || OpTy.isVector()) return Op;
1848 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1849 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1852 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1853 /// specified value type.
1854 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1855 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1856 unsigned ByteSize = VT.getStoreSize();
1857 Type *Ty = VT.getTypeForEVT(*getContext());
1858 unsigned StackAlign =
1859 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1861 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1862 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1865 /// CreateStackTemporary - Create a stack temporary suitable for holding
1866 /// either of the specified value types.
1867 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1868 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1869 VT2.getStoreSizeInBits())/8;
1870 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1871 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1872 const DataLayout *TD = TLI->getDataLayout();
1873 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1874 TD->getPrefTypeAlignment(Ty2));
1876 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1877 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1878 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1881 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1882 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1883 // These setcc operations always fold.
1887 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1889 case ISD::SETTRUE2: {
1890 TargetLowering::BooleanContent Cnt =
1891 TLI->getBooleanContents(N1->getValueType(0));
1893 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1907 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1911 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1912 const APInt &C2 = N2C->getAPIntValue();
1913 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1914 const APInt &C1 = N1C->getAPIntValue();
1917 default: llvm_unreachable("Unknown integer setcc!");
1918 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1919 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1920 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1921 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1922 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1923 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1924 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1925 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1926 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1927 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1931 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1932 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1933 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1936 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1937 return getUNDEF(VT);
1939 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1940 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1941 return getUNDEF(VT);
1943 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1944 R==APFloat::cmpLessThan, dl, VT);
1945 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1946 return getUNDEF(VT);
1948 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1949 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1950 return getUNDEF(VT);
1952 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1953 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1954 return getUNDEF(VT);
1956 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1957 R==APFloat::cmpEqual, dl, VT);
1958 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1959 return getUNDEF(VT);
1961 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1962 R==APFloat::cmpEqual, dl, VT);
1963 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1964 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1965 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1966 R==APFloat::cmpEqual, dl, VT);
1967 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1968 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1969 R==APFloat::cmpLessThan, dl, VT);
1970 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1971 R==APFloat::cmpUnordered, dl, VT);
1972 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1973 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1976 // Ensure that the constant occurs on the RHS.
1977 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1978 MVT CompVT = N1.getValueType().getSimpleVT();
1979 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1982 return getSetCC(dl, VT, N2, N1, SwappedCond);
1986 // Could not fold it.
1990 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1991 /// use this predicate to simplify operations downstream.
1992 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1993 // This predicate is not safe for vector operations.
1994 if (Op.getValueType().isVector())
1997 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1998 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2001 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2002 /// this predicate to simplify operations downstream. Mask is known to be zero
2003 /// for bits that V cannot have.
2004 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2005 unsigned Depth) const {
2006 APInt KnownZero, KnownOne;
2007 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2008 return (KnownZero & Mask) == Mask;
2011 /// Determine which bits of Op are known to be either zero or one and return
2012 /// them in the KnownZero/KnownOne bitsets.
2013 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2014 APInt &KnownOne, unsigned Depth) const {
2015 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2017 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2019 return; // Limit search depth.
2021 APInt KnownZero2, KnownOne2;
2023 switch (Op.getOpcode()) {
2025 // We know all of the bits for a constant!
2026 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2027 KnownZero = ~KnownOne;
2030 // If either the LHS or the RHS are Zero, the result is zero.
2031 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2032 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2034 // Output known-1 bits are only known if set in both the LHS & RHS.
2035 KnownOne &= KnownOne2;
2036 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2037 KnownZero |= KnownZero2;
2040 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2041 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2043 // Output known-0 bits are only known if clear in both the LHS & RHS.
2044 KnownZero &= KnownZero2;
2045 // Output known-1 are known to be set if set in either the LHS | RHS.
2046 KnownOne |= KnownOne2;
2049 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2050 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2052 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2053 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2054 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2055 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2056 KnownZero = KnownZeroOut;
2060 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2061 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2063 // If low bits are zero in either operand, output low known-0 bits.
2064 // Also compute a conserative estimate for high known-0 bits.
2065 // More trickiness is possible, but this is sufficient for the
2066 // interesting case of alignment computation.
2067 KnownOne.clearAllBits();
2068 unsigned TrailZ = KnownZero.countTrailingOnes() +
2069 KnownZero2.countTrailingOnes();
2070 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2071 KnownZero2.countLeadingOnes(),
2072 BitWidth) - BitWidth;
2074 TrailZ = std::min(TrailZ, BitWidth);
2075 LeadZ = std::min(LeadZ, BitWidth);
2076 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2077 APInt::getHighBitsSet(BitWidth, LeadZ);
2081 // For the purposes of computing leading zeros we can conservatively
2082 // treat a udiv as a logical right shift by the power of 2 known to
2083 // be less than the denominator.
2084 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2085 unsigned LeadZ = KnownZero2.countLeadingOnes();
2087 KnownOne2.clearAllBits();
2088 KnownZero2.clearAllBits();
2089 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2090 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2091 if (RHSUnknownLeadingOnes != BitWidth)
2092 LeadZ = std::min(BitWidth,
2093 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2095 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2099 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2100 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2102 // Only known if known in both the LHS and RHS.
2103 KnownOne &= KnownOne2;
2104 KnownZero &= KnownZero2;
2106 case ISD::SELECT_CC:
2107 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2108 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2110 // Only known if known in both the LHS and RHS.
2111 KnownOne &= KnownOne2;
2112 KnownZero &= KnownZero2;
2120 if (Op.getResNo() != 1)
2122 // The boolean result conforms to getBooleanContents.
2123 // If we know the result of a setcc has the top bits zero, use this info.
2124 // We know that we have an integer-based boolean since these operations
2125 // are only available for integer.
2126 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2127 TargetLowering::ZeroOrOneBooleanContent &&
2129 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2132 // If we know the result of a setcc has the top bits zero, use this info.
2133 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2134 TargetLowering::ZeroOrOneBooleanContent &&
2136 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2139 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2140 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2141 unsigned ShAmt = SA->getZExtValue();
2143 // If the shift count is an invalid immediate, don't do anything.
2144 if (ShAmt >= BitWidth)
2147 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2148 KnownZero <<= ShAmt;
2150 // low bits known zero.
2151 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2155 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2156 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2157 unsigned ShAmt = SA->getZExtValue();
2159 // If the shift count is an invalid immediate, don't do anything.
2160 if (ShAmt >= BitWidth)
2163 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2164 KnownZero = KnownZero.lshr(ShAmt);
2165 KnownOne = KnownOne.lshr(ShAmt);
2167 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2168 KnownZero |= HighBits; // High bits known zero.
2172 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2173 unsigned ShAmt = SA->getZExtValue();
2175 // If the shift count is an invalid immediate, don't do anything.
2176 if (ShAmt >= BitWidth)
2179 // If any of the demanded bits are produced by the sign extension, we also
2180 // demand the input sign bit.
2181 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2183 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2184 KnownZero = KnownZero.lshr(ShAmt);
2185 KnownOne = KnownOne.lshr(ShAmt);
2187 // Handle the sign bits.
2188 APInt SignBit = APInt::getSignBit(BitWidth);
2189 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2191 if (KnownZero.intersects(SignBit)) {
2192 KnownZero |= HighBits; // New bits are known zero.
2193 } else if (KnownOne.intersects(SignBit)) {
2194 KnownOne |= HighBits; // New bits are known one.
2198 case ISD::SIGN_EXTEND_INREG: {
2199 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2200 unsigned EBits = EVT.getScalarType().getSizeInBits();
2202 // Sign extension. Compute the demanded bits in the result that are not
2203 // present in the input.
2204 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2206 APInt InSignBit = APInt::getSignBit(EBits);
2207 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2209 // If the sign extended bits are demanded, we know that the sign
2211 InSignBit = InSignBit.zext(BitWidth);
2212 if (NewBits.getBoolValue())
2213 InputDemandedBits |= InSignBit;
2215 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2216 KnownOne &= InputDemandedBits;
2217 KnownZero &= InputDemandedBits;
2219 // If the sign bit of the input is known set or clear, then we know the
2220 // top bits of the result.
2221 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2222 KnownZero |= NewBits;
2223 KnownOne &= ~NewBits;
2224 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2225 KnownOne |= NewBits;
2226 KnownZero &= ~NewBits;
2227 } else { // Input sign bit unknown
2228 KnownZero &= ~NewBits;
2229 KnownOne &= ~NewBits;
2234 case ISD::CTTZ_ZERO_UNDEF:
2236 case ISD::CTLZ_ZERO_UNDEF:
2238 unsigned LowBits = Log2_32(BitWidth)+1;
2239 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2240 KnownOne.clearAllBits();
2244 LoadSDNode *LD = cast<LoadSDNode>(Op);
2245 // If this is a ZEXTLoad and we are looking at the loaded value.
2246 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2247 EVT VT = LD->getMemoryVT();
2248 unsigned MemBits = VT.getScalarType().getSizeInBits();
2249 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2250 } else if (const MDNode *Ranges = LD->getRanges()) {
2251 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2255 case ISD::ZERO_EXTEND: {
2256 EVT InVT = Op.getOperand(0).getValueType();
2257 unsigned InBits = InVT.getScalarType().getSizeInBits();
2258 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2259 KnownZero = KnownZero.trunc(InBits);
2260 KnownOne = KnownOne.trunc(InBits);
2261 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2262 KnownZero = KnownZero.zext(BitWidth);
2263 KnownOne = KnownOne.zext(BitWidth);
2264 KnownZero |= NewBits;
2267 case ISD::SIGN_EXTEND: {
2268 EVT InVT = Op.getOperand(0).getValueType();
2269 unsigned InBits = InVT.getScalarType().getSizeInBits();
2270 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2272 KnownZero = KnownZero.trunc(InBits);
2273 KnownOne = KnownOne.trunc(InBits);
2274 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2276 // Note if the sign bit is known to be zero or one.
2277 bool SignBitKnownZero = KnownZero.isNegative();
2278 bool SignBitKnownOne = KnownOne.isNegative();
2280 KnownZero = KnownZero.zext(BitWidth);
2281 KnownOne = KnownOne.zext(BitWidth);
2283 // If the sign bit is known zero or one, the top bits match.
2284 if (SignBitKnownZero)
2285 KnownZero |= NewBits;
2286 else if (SignBitKnownOne)
2287 KnownOne |= NewBits;
2290 case ISD::ANY_EXTEND: {
2291 EVT InVT = Op.getOperand(0).getValueType();
2292 unsigned InBits = InVT.getScalarType().getSizeInBits();
2293 KnownZero = KnownZero.trunc(InBits);
2294 KnownOne = KnownOne.trunc(InBits);
2295 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2296 KnownZero = KnownZero.zext(BitWidth);
2297 KnownOne = KnownOne.zext(BitWidth);
2300 case ISD::TRUNCATE: {
2301 EVT InVT = Op.getOperand(0).getValueType();
2302 unsigned InBits = InVT.getScalarType().getSizeInBits();
2303 KnownZero = KnownZero.zext(InBits);
2304 KnownOne = KnownOne.zext(InBits);
2305 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2306 KnownZero = KnownZero.trunc(BitWidth);
2307 KnownOne = KnownOne.trunc(BitWidth);
2310 case ISD::AssertZext: {
2311 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2312 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2313 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2314 KnownZero |= (~InMask);
2315 KnownOne &= (~KnownZero);
2319 // All bits are zero except the low bit.
2320 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2324 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2325 // We know that the top bits of C-X are clear if X contains less bits
2326 // than C (i.e. no wrap-around can happen). For example, 20-X is
2327 // positive if we can prove that X is >= 0 and < 16.
2328 if (CLHS->getAPIntValue().isNonNegative()) {
2329 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2330 // NLZ can't be BitWidth with no sign bit
2331 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2332 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2334 // If all of the MaskV bits are known to be zero, then we know the
2335 // output top bits are zero, because we now know that the output is
2337 if ((KnownZero2 & MaskV) == MaskV) {
2338 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2339 // Top bits known zero.
2340 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2348 // Output known-0 bits are known if clear or set in both the low clear bits
2349 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2350 // low 3 bits clear.
2351 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2352 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2354 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2355 KnownZeroOut = std::min(KnownZeroOut,
2356 KnownZero2.countTrailingOnes());
2358 if (Op.getOpcode() == ISD::ADD) {
2359 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2363 // With ADDE, a carry bit may be added in, so we can only use this
2364 // information if we know (at least) that the low two bits are clear. We
2365 // then return to the caller that the low bit is unknown but that other bits
2367 if (KnownZeroOut >= 2) // ADDE
2368 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2372 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2373 const APInt &RA = Rem->getAPIntValue().abs();
2374 if (RA.isPowerOf2()) {
2375 APInt LowBits = RA - 1;
2376 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2378 // The low bits of the first operand are unchanged by the srem.
2379 KnownZero = KnownZero2 & LowBits;
2380 KnownOne = KnownOne2 & LowBits;
2382 // If the first operand is non-negative or has all low bits zero, then
2383 // the upper bits are all zero.
2384 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2385 KnownZero |= ~LowBits;
2387 // If the first operand is negative and not all low bits are zero, then
2388 // the upper bits are all one.
2389 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2390 KnownOne |= ~LowBits;
2391 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2396 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397 const APInt &RA = Rem->getAPIntValue();
2398 if (RA.isPowerOf2()) {
2399 APInt LowBits = (RA - 1);
2400 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2402 // The upper bits are all zero, the lower ones are unchanged.
2403 KnownZero = KnownZero2 | ~LowBits;
2404 KnownOne = KnownOne2 & LowBits;
2409 // Since the result is less than or equal to either operand, any leading
2410 // zero bits in either operand must also exist in the result.
2411 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2412 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2414 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2415 KnownZero2.countLeadingOnes());
2416 KnownOne.clearAllBits();
2417 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2420 case ISD::EXTRACT_ELEMENT: {
2421 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2422 const unsigned Index =
2423 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2424 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2426 // Remove low part of known bits mask
2427 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2428 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2430 // Remove high part of known bit mask
2431 KnownZero = KnownZero.trunc(BitWidth);
2432 KnownOne = KnownOne.trunc(BitWidth);
2439 APInt Op0Zero, Op0One;
2440 APInt Op1Zero, Op1One;
2441 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2442 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2444 KnownZero = Op0Zero & Op1Zero;
2445 KnownOne = Op0One & Op1One;
2448 case ISD::FrameIndex:
2449 case ISD::TargetFrameIndex:
2450 if (unsigned Align = InferPtrAlignment(Op)) {
2451 // The low bits are known zero if the pointer is aligned.
2452 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2458 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2461 case ISD::INTRINSIC_WO_CHAIN:
2462 case ISD::INTRINSIC_W_CHAIN:
2463 case ISD::INTRINSIC_VOID:
2464 // Allow the target to implement this method for its nodes.
2465 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2469 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2472 /// ComputeNumSignBits - Return the number of times the sign bit of the
2473 /// register is replicated into the other bits. We know that at least 1 bit
2474 /// is always equal to the sign bit (itself), but other cases can give us
2475 /// information. For example, immediately after an "SRA X, 2", we know that
2476 /// the top 3 bits are all equal to each other, so we return 3.
2477 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2478 EVT VT = Op.getValueType();
2479 assert(VT.isInteger() && "Invalid VT!");
2480 unsigned VTBits = VT.getScalarType().getSizeInBits();
2482 unsigned FirstAnswer = 1;
2485 return 1; // Limit search depth.
2487 switch (Op.getOpcode()) {
2489 case ISD::AssertSext:
2490 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2491 return VTBits-Tmp+1;
2492 case ISD::AssertZext:
2493 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2496 case ISD::Constant: {
2497 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2498 return Val.getNumSignBits();
2501 case ISD::SIGN_EXTEND:
2503 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2504 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2506 case ISD::SIGN_EXTEND_INREG:
2507 // Max of the input and what this extends.
2509 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2512 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2513 return std::max(Tmp, Tmp2);
2516 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2517 // SRA X, C -> adds C sign bits.
2518 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2519 Tmp += C->getZExtValue();
2520 if (Tmp > VTBits) Tmp = VTBits;
2524 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2525 // shl destroys sign bits.
2526 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2527 if (C->getZExtValue() >= VTBits || // Bad shift.
2528 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2529 return Tmp - C->getZExtValue();
2534 case ISD::XOR: // NOT is handled here.
2535 // Logical binary ops preserve the number of sign bits at the worst.
2536 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2538 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2539 FirstAnswer = std::min(Tmp, Tmp2);
2540 // We computed what we know about the sign bits as our first
2541 // answer. Now proceed to the generic code that uses
2542 // computeKnownBits, and pick whichever answer is better.
2547 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2548 if (Tmp == 1) return 1; // Early out.
2549 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2550 return std::min(Tmp, Tmp2);
2555 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2557 return 1; // Early out.
2558 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2559 return std::min(Tmp, Tmp2);
2566 if (Op.getResNo() != 1)
2568 // The boolean result conforms to getBooleanContents. Fall through.
2569 // If setcc returns 0/-1, all bits are sign bits.
2570 // We know that we have an integer-based boolean since these operations
2571 // are only available for integer.
2572 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2573 TargetLowering::ZeroOrNegativeOneBooleanContent)
2577 // If setcc returns 0/-1, all bits are sign bits.
2578 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2579 TargetLowering::ZeroOrNegativeOneBooleanContent)
2584 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2585 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2587 // Handle rotate right by N like a rotate left by 32-N.
2588 if (Op.getOpcode() == ISD::ROTR)
2589 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2591 // If we aren't rotating out all of the known-in sign bits, return the
2592 // number that are left. This handles rotl(sext(x), 1) for example.
2593 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2594 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2598 // Add can have at most one carry bit. Thus we know that the output
2599 // is, at worst, one more bit than the inputs.
2600 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2601 if (Tmp == 1) return 1; // Early out.
2603 // Special case decrementing a value (ADD X, -1):
2604 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2605 if (CRHS->isAllOnesValue()) {
2606 APInt KnownZero, KnownOne;
2607 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2609 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2611 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2614 // If we are subtracting one from a positive number, there is no carry
2615 // out of the result.
2616 if (KnownZero.isNegative())
2620 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2621 if (Tmp2 == 1) return 1;
2622 return std::min(Tmp, Tmp2)-1;
2625 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2626 if (Tmp2 == 1) return 1;
2629 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2630 if (CLHS->isNullValue()) {
2631 APInt KnownZero, KnownOne;
2632 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2633 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2635 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2638 // If the input is known to be positive (the sign bit is known clear),
2639 // the output of the NEG has the same number of sign bits as the input.
2640 if (KnownZero.isNegative())
2643 // Otherwise, we treat this like a SUB.
2646 // Sub can have at most one carry bit. Thus we know that the output
2647 // is, at worst, one more bit than the inputs.
2648 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2649 if (Tmp == 1) return 1; // Early out.
2650 return std::min(Tmp, Tmp2)-1;
2652 // FIXME: it's tricky to do anything useful for this, but it is an important
2653 // case for targets like X86.
2655 case ISD::EXTRACT_ELEMENT: {
2656 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2657 const int BitWidth = Op.getValueType().getSizeInBits();
2659 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2661 // Get reverse index (starting from 1), Op1 value indexes elements from
2662 // little end. Sign starts at big end.
2663 const int rIndex = Items - 1 -
2664 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2666 // If the sign portion ends in our element the substraction gives correct
2667 // result. Otherwise it gives either negative or > bitwidth result
2668 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2672 // If we are looking at the loaded value of the SDNode.
2673 if (Op.getResNo() == 0) {
2674 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2675 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2676 unsigned ExtType = LD->getExtensionType();
2679 case ISD::SEXTLOAD: // '17' bits known
2680 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2681 return VTBits-Tmp+1;
2682 case ISD::ZEXTLOAD: // '16' bits known
2683 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2689 // Allow the target to implement this method for its nodes.
2690 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2691 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2692 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2693 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2694 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2695 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2698 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2699 // use this information.
2700 APInt KnownZero, KnownOne;
2701 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2704 if (KnownZero.isNegative()) { // sign bit is 0
2706 } else if (KnownOne.isNegative()) { // sign bit is 1;
2713 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2714 // the number of identical bits in the top of the input value.
2716 Mask <<= Mask.getBitWidth()-VTBits;
2717 // Return # leading zeros. We use 'min' here in case Val was zero before
2718 // shifting. We don't want to return '64' as for an i32 "0".
2719 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2722 /// isBaseWithConstantOffset - Return true if the specified operand is an
2723 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2724 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2725 /// semantics as an ADD. This handles the equivalence:
2726 /// X|Cst == X+Cst iff X&Cst = 0.
2727 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2728 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2729 !isa<ConstantSDNode>(Op.getOperand(1)))
2732 if (Op.getOpcode() == ISD::OR &&
2733 !MaskedValueIsZero(Op.getOperand(0),
2734 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2741 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2742 // If we're told that NaNs won't happen, assume they won't.
2743 if (getTarget().Options.NoNaNsFPMath)
2746 // If the value is a constant, we can obviously see if it is a NaN or not.
2747 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2748 return !C->getValueAPF().isNaN();
2750 // TODO: Recognize more cases here.
2755 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2756 // If the value is a constant, we can obviously see if it is a zero or not.
2757 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2758 return !C->isZero();
2760 // TODO: Recognize more cases here.
2761 switch (Op.getOpcode()) {
2764 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2765 return !C->isNullValue();
2772 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2773 // Check the obvious case.
2774 if (A == B) return true;
2776 // For for negative and positive zero.
2777 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2778 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2779 if (CA->isZero() && CB->isZero()) return true;
2781 // Otherwise they may not be equal.
2785 /// getNode - Gets or creates the specified node.
2787 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2788 FoldingSetNodeID ID;
2789 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2791 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2792 return SDValue(E, 0);
2794 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2795 DL.getDebugLoc(), getVTList(VT));
2796 CSEMap.InsertNode(N, IP);
2799 return SDValue(N, 0);
2802 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2803 EVT VT, SDValue Operand) {
2804 // Constant fold unary operations with an integer constant operand. Even
2805 // opaque constant will be folded, because the folding of unary operations
2806 // doesn't create new constants with different values. Nevertheless, the
2807 // opaque flag is preserved during folding to prevent future folding with
2809 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2810 const APInt &Val = C->getAPIntValue();
2813 case ISD::SIGN_EXTEND:
2814 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2815 C->isTargetOpcode(), C->isOpaque());
2816 case ISD::ANY_EXTEND:
2817 case ISD::ZERO_EXTEND:
2819 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2820 C->isTargetOpcode(), C->isOpaque());
2821 case ISD::UINT_TO_FP:
2822 case ISD::SINT_TO_FP: {
2823 APFloat apf(EVTToAPFloatSemantics(VT),
2824 APInt::getNullValue(VT.getSizeInBits()));
2825 (void)apf.convertFromAPInt(Val,
2826 Opcode==ISD::SINT_TO_FP,
2827 APFloat::rmNearestTiesToEven);
2828 return getConstantFP(apf, DL, VT);
2831 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2832 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2833 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2834 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2835 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2836 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2839 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2842 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2845 case ISD::CTLZ_ZERO_UNDEF:
2846 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2849 case ISD::CTTZ_ZERO_UNDEF:
2850 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2855 // Constant fold unary operations with a floating point constant operand.
2856 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2857 APFloat V = C->getValueAPF(); // make copy
2861 return getConstantFP(V, DL, VT);
2864 return getConstantFP(V, DL, VT);
2866 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2867 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2868 return getConstantFP(V, DL, VT);
2872 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2873 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2874 return getConstantFP(V, DL, VT);
2878 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2879 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2880 return getConstantFP(V, DL, VT);
2883 case ISD::FP_EXTEND: {
2885 // This can return overflow, underflow, or inexact; we don't care.
2886 // FIXME need to be more flexible about rounding mode.
2887 (void)V.convert(EVTToAPFloatSemantics(VT),
2888 APFloat::rmNearestTiesToEven, &ignored);
2889 return getConstantFP(V, DL, VT);
2891 case ISD::FP_TO_SINT:
2892 case ISD::FP_TO_UINT: {
2895 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2896 // FIXME need to be more flexible about rounding mode.
2897 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2898 Opcode==ISD::FP_TO_SINT,
2899 APFloat::rmTowardZero, &ignored);
2900 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2902 APInt api(VT.getSizeInBits(), x);
2903 return getConstant(api, DL, VT);
2906 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2907 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2908 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2909 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2910 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2911 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2916 // Constant fold unary operations with a vector integer or float operand.
2917 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2918 if (BV->isConstant()) {
2921 // FIXME: Entirely reasonable to perform folding of other unary
2922 // operations here as the need arises.
2929 case ISD::FP_EXTEND:
2930 case ISD::FP_TO_SINT:
2931 case ISD::FP_TO_UINT:
2933 case ISD::UINT_TO_FP:
2934 case ISD::SINT_TO_FP:
2937 case ISD::CTLZ_ZERO_UNDEF:
2939 case ISD::CTTZ_ZERO_UNDEF:
2941 EVT SVT = VT.getScalarType();
2942 EVT InVT = BV->getValueType(0);
2943 EVT InSVT = InVT.getScalarType();
2945 // Find legal integer scalar type for constant promotion and
2946 // ensure that its scalar size is at least as large as source.
2948 if (SVT.isInteger()) {
2949 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2950 if (LegalSVT.bitsLT(SVT)) break;
2953 // Let the above scalar folding handle the folding of each element.
2954 SmallVector<SDValue, 8> Ops;
2955 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2956 SDValue OpN = BV->getOperand(i);
2957 EVT OpVT = OpN.getValueType();
2959 // Build vector (integer) scalar operands may need implicit
2960 // truncation - do this before constant folding.
2961 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2962 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2964 OpN = getNode(Opcode, DL, SVT, OpN);
2966 // Legalize the (integer) scalar constant if necessary.
2967 if (LegalSVT != SVT)
2968 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2970 if (OpN.getOpcode() != ISD::UNDEF &&
2971 OpN.getOpcode() != ISD::Constant &&
2972 OpN.getOpcode() != ISD::ConstantFP)
2976 if (Ops.size() == VT.getVectorNumElements())
2977 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2984 unsigned OpOpcode = Operand.getNode()->getOpcode();
2986 case ISD::TokenFactor:
2987 case ISD::MERGE_VALUES:
2988 case ISD::CONCAT_VECTORS:
2989 return Operand; // Factor, merge or concat of one node? No need.
2990 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2991 case ISD::FP_EXTEND:
2992 assert(VT.isFloatingPoint() &&
2993 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2994 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2995 assert((!VT.isVector() ||
2996 VT.getVectorNumElements() ==
2997 Operand.getValueType().getVectorNumElements()) &&
2998 "Vector element count mismatch!");
2999 if (Operand.getOpcode() == ISD::UNDEF)
3000 return getUNDEF(VT);
3002 case ISD::SIGN_EXTEND:
3003 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3004 "Invalid SIGN_EXTEND!");
3005 if (Operand.getValueType() == VT) return Operand; // noop extension
3006 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3007 "Invalid sext node, dst < src!");
3008 assert((!VT.isVector() ||
3009 VT.getVectorNumElements() ==
3010 Operand.getValueType().getVectorNumElements()) &&
3011 "Vector element count mismatch!");
3012 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3013 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3014 else if (OpOpcode == ISD::UNDEF)
3015 // sext(undef) = 0, because the top bits will all be the same.
3016 return getConstant(0, DL, VT);
3018 case ISD::ZERO_EXTEND:
3019 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3020 "Invalid ZERO_EXTEND!");
3021 if (Operand.getValueType() == VT) return Operand; // noop extension
3022 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3023 "Invalid zext node, dst < src!");
3024 assert((!VT.isVector() ||
3025 VT.getVectorNumElements() ==
3026 Operand.getValueType().getVectorNumElements()) &&
3027 "Vector element count mismatch!");
3028 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3029 return getNode(ISD::ZERO_EXTEND, DL, VT,
3030 Operand.getNode()->getOperand(0));
3031 else if (OpOpcode == ISD::UNDEF)
3032 // zext(undef) = 0, because the top bits will be zero.
3033 return getConstant(0, DL, VT);
3035 case ISD::ANY_EXTEND:
3036 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3037 "Invalid ANY_EXTEND!");
3038 if (Operand.getValueType() == VT) return Operand; // noop extension
3039 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3040 "Invalid anyext node, dst < src!");
3041 assert((!VT.isVector() ||
3042 VT.getVectorNumElements() ==
3043 Operand.getValueType().getVectorNumElements()) &&
3044 "Vector element count mismatch!");
3046 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3047 OpOpcode == ISD::ANY_EXTEND)
3048 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3049 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3050 else if (OpOpcode == ISD::UNDEF)
3051 return getUNDEF(VT);
3053 // (ext (trunx x)) -> x
3054 if (OpOpcode == ISD::TRUNCATE) {
3055 SDValue OpOp = Operand.getNode()->getOperand(0);
3056 if (OpOp.getValueType() == VT)
3061 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3062 "Invalid TRUNCATE!");
3063 if (Operand.getValueType() == VT) return Operand; // noop truncate
3064 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3065 "Invalid truncate node, src < dst!");
3066 assert((!VT.isVector() ||
3067 VT.getVectorNumElements() ==
3068 Operand.getValueType().getVectorNumElements()) &&
3069 "Vector element count mismatch!");
3070 if (OpOpcode == ISD::TRUNCATE)
3071 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3072 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3073 OpOpcode == ISD::ANY_EXTEND) {
3074 // If the source is smaller than the dest, we still need an extend.
3075 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3076 .bitsLT(VT.getScalarType()))
3077 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3078 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3079 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3080 return Operand.getNode()->getOperand(0);
3082 if (OpOpcode == ISD::UNDEF)
3083 return getUNDEF(VT);
3086 assert(VT.isInteger() && VT == Operand.getValueType() &&
3088 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3089 "BSWAP types must be a multiple of 16 bits!");
3090 if (OpOpcode == ISD::UNDEF)
3091 return getUNDEF(VT);
3094 // Basic sanity checking.
3095 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3096 && "Cannot BITCAST between types of different sizes!");
3097 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3098 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3099 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3100 if (OpOpcode == ISD::UNDEF)
3101 return getUNDEF(VT);
3103 case ISD::SCALAR_TO_VECTOR:
3104 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3105 (VT.getVectorElementType() == Operand.getValueType() ||
3106 (VT.getVectorElementType().isInteger() &&
3107 Operand.getValueType().isInteger() &&
3108 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3109 "Illegal SCALAR_TO_VECTOR node!");
3110 if (OpOpcode == ISD::UNDEF)
3111 return getUNDEF(VT);
3112 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3113 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3114 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3115 Operand.getConstantOperandVal(1) == 0 &&
3116 Operand.getOperand(0).getValueType() == VT)
3117 return Operand.getOperand(0);
3120 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3121 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3122 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3123 Operand.getNode()->getOperand(0));
3124 if (OpOpcode == ISD::FNEG) // --X -> X
3125 return Operand.getNode()->getOperand(0);
3128 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3129 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3134 SDVTList VTs = getVTList(VT);
3135 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3136 FoldingSetNodeID ID;
3137 SDValue Ops[1] = { Operand };
3138 AddNodeIDNode(ID, Opcode, VTs, Ops);
3140 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3141 return SDValue(E, 0);
3143 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3144 DL.getDebugLoc(), VTs, Operand);
3145 CSEMap.InsertNode(N, IP);
3147 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3148 DL.getDebugLoc(), VTs, Operand);
3152 return SDValue(N, 0);
3155 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3158 case ISD::ADD: return std::make_pair(C1 + C2, true);
3159 case ISD::SUB: return std::make_pair(C1 - C2, true);
3160 case ISD::MUL: return std::make_pair(C1 * C2, true);
3161 case ISD::AND: return std::make_pair(C1 & C2, true);
3162 case ISD::OR: return std::make_pair(C1 | C2, true);
3163 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3164 case ISD::SHL: return std::make_pair(C1 << C2, true);
3165 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3166 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3167 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3168 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3170 if (!C2.getBoolValue())
3172 return std::make_pair(C1.udiv(C2), true);
3174 if (!C2.getBoolValue())
3176 return std::make_pair(C1.urem(C2), true);
3178 if (!C2.getBoolValue())
3180 return std::make_pair(C1.sdiv(C2), true);
3182 if (!C2.getBoolValue())
3184 return std::make_pair(C1.srem(C2), true);
3186 return std::make_pair(APInt(1, 0), false);
3189 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3190 const ConstantSDNode *Cst1,
3191 const ConstantSDNode *Cst2) {
3192 if (Cst1->isOpaque() || Cst2->isOpaque())
3195 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3196 Cst2->getAPIntValue());
3199 return getConstant(Folded.first, DL, VT);
3202 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3203 SDNode *Cst1, SDNode *Cst2) {
3204 // If the opcode is a target-specific ISD node, there's nothing we can
3205 // do here and the operand rules may not line up with the below, so
3207 if (Opcode >= ISD::BUILTIN_OP_END)
3210 // Handle the case of two scalars.
3211 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3212 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3213 if (SDValue Folded =
3214 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3217 SmallVector<SDValue, 4> Outputs;
3218 // We may have a vector type but a scalar result. Create a splat.
3219 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3220 // Build a big vector out of the scalar elements we generated.
3221 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3228 // For vectors extract each constant element into Inputs so we can constant
3229 // fold them individually.
3230 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3231 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3235 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3237 EVT SVT = VT.getScalarType();
3238 SmallVector<SDValue, 4> Outputs;
3239 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3240 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3241 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3242 if (!V1 || !V2) // Not a constant, bail.
3245 if (V1->isOpaque() || V2->isOpaque())
3248 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3249 // FIXME: This is valid and could be handled by truncating the APInts.
3250 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3253 // Fold one vector element.
3254 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3255 V2->getAPIntValue());
3258 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3261 assert(VT.getVectorNumElements() == Outputs.size() &&
3262 "Vector size mismatch!");
3264 // We may have a vector type but a scalar result. Create a splat.
3265 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3267 // Build a big vector out of the scalar elements we generated.
3268 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3271 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3272 SDValue N2, bool nuw, bool nsw, bool exact) {
3273 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3274 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3277 case ISD::TokenFactor:
3278 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3279 N2.getValueType() == MVT::Other && "Invalid token factor!");
3280 // Fold trivial token factors.
3281 if (N1.getOpcode() == ISD::EntryToken) return N2;
3282 if (N2.getOpcode() == ISD::EntryToken) return N1;
3283 if (N1 == N2) return N1;
3285 case ISD::CONCAT_VECTORS:
3286 // Concat of UNDEFs is UNDEF.
3287 if (N1.getOpcode() == ISD::UNDEF &&
3288 N2.getOpcode() == ISD::UNDEF)
3289 return getUNDEF(VT);
3291 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3292 // one big BUILD_VECTOR.
3293 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3294 N2.getOpcode() == ISD::BUILD_VECTOR) {
3295 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3296 N1.getNode()->op_end());
3297 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3299 // BUILD_VECTOR requires all inputs to be of the same type, find the
3300 // maximum type and extend them all.
3301 EVT SVT = VT.getScalarType();
3302 for (SDValue Op : Elts)
3303 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3304 if (SVT.bitsGT(VT.getScalarType()))
3305 for (SDValue &Op : Elts)
3306 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3307 ? getZExtOrTrunc(Op, DL, SVT)
3308 : getSExtOrTrunc(Op, DL, SVT);
3310 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3314 assert(VT.isInteger() && "This operator does not apply to FP types!");
3315 assert(N1.getValueType() == N2.getValueType() &&
3316 N1.getValueType() == VT && "Binary operator types must match!");
3317 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3318 // worth handling here.
3319 if (N2C && N2C->isNullValue())
3321 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3328 assert(VT.isInteger() && "This operator does not apply to FP types!");
3329 assert(N1.getValueType() == N2.getValueType() &&
3330 N1.getValueType() == VT && "Binary operator types must match!");
3331 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3332 // it's worth handling here.
3333 if (N2C && N2C->isNullValue())
3343 assert(VT.isInteger() && "This operator does not apply to FP types!");
3344 assert(N1.getValueType() == N2.getValueType() &&
3345 N1.getValueType() == VT && "Binary operator types must match!");
3352 if (getTarget().Options.UnsafeFPMath) {
3353 if (Opcode == ISD::FADD) {
3355 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3356 if (CFP->getValueAPF().isZero())
3359 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3360 if (CFP->getValueAPF().isZero())
3362 } else if (Opcode == ISD::FSUB) {
3364 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3365 if (CFP->getValueAPF().isZero())
3367 } else if (Opcode == ISD::FMUL) {
3368 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3371 // If the first operand isn't the constant, try the second
3373 CFP = dyn_cast<ConstantFPSDNode>(N2);
3380 return SDValue(CFP,0);
3382 if (CFP->isExactlyValue(1.0))
3387 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3388 assert(N1.getValueType() == N2.getValueType() &&
3389 N1.getValueType() == VT && "Binary operator types must match!");
3391 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3392 assert(N1.getValueType() == VT &&
3393 N1.getValueType().isFloatingPoint() &&
3394 N2.getValueType().isFloatingPoint() &&
3395 "Invalid FCOPYSIGN!");
3402 assert(VT == N1.getValueType() &&
3403 "Shift operators return type must be the same as their first arg");
3404 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3405 "Shifts only work on integers");
3406 assert((!VT.isVector() || VT == N2.getValueType()) &&
3407 "Vector shift amounts must be in the same as their first arg");
3408 // Verify that the shift amount VT is bit enough to hold valid shift
3409 // amounts. This catches things like trying to shift an i1024 value by an
3410 // i8, which is easy to fall into in generic code that uses
3411 // TLI.getShiftAmount().
3412 assert(N2.getValueType().getSizeInBits() >=
3413 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3414 "Invalid use of small shift amount with oversized value!");
3416 // Always fold shifts of i1 values so the code generator doesn't need to
3417 // handle them. Since we know the size of the shift has to be less than the
3418 // size of the value, the shift/rotate count is guaranteed to be zero.
3421 if (N2C && N2C->isNullValue())
3424 case ISD::FP_ROUND_INREG: {
3425 EVT EVT = cast<VTSDNode>(N2)->getVT();
3426 assert(VT == N1.getValueType() && "Not an inreg round!");
3427 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3428 "Cannot FP_ROUND_INREG integer types");
3429 assert(EVT.isVector() == VT.isVector() &&
3430 "FP_ROUND_INREG type should be vector iff the operand "
3432 assert((!EVT.isVector() ||
3433 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3434 "Vector element counts must match in FP_ROUND_INREG");
3435 assert(EVT.bitsLE(VT) && "Not rounding down!");
3437 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3441 assert(VT.isFloatingPoint() &&
3442 N1.getValueType().isFloatingPoint() &&
3443 VT.bitsLE(N1.getValueType()) &&
3444 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3445 if (N1.getValueType() == VT) return N1; // noop conversion.
3447 case ISD::AssertSext:
3448 case ISD::AssertZext: {
3449 EVT EVT = cast<VTSDNode>(N2)->getVT();
3450 assert(VT == N1.getValueType() && "Not an inreg extend!");
3451 assert(VT.isInteger() && EVT.isInteger() &&
3452 "Cannot *_EXTEND_INREG FP types");
3453 assert(!EVT.isVector() &&
3454 "AssertSExt/AssertZExt type should be the vector element type "
3455 "rather than the vector type!");
3456 assert(EVT.bitsLE(VT) && "Not extending!");
3457 if (VT == EVT) return N1; // noop assertion.
3460 case ISD::SIGN_EXTEND_INREG: {
3461 EVT EVT = cast<VTSDNode>(N2)->getVT();
3462 assert(VT == N1.getValueType() && "Not an inreg extend!");
3463 assert(VT.isInteger() && EVT.isInteger() &&
3464 "Cannot *_EXTEND_INREG FP types");
3465 assert(EVT.isVector() == VT.isVector() &&
3466 "SIGN_EXTEND_INREG type should be vector iff the operand "
3468 assert((!EVT.isVector() ||
3469 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3470 "Vector element counts must match in SIGN_EXTEND_INREG");
3471 assert(EVT.bitsLE(VT) && "Not extending!");
3472 if (EVT == VT) return N1; // Not actually extending
3474 auto SignExtendInReg = [&](APInt Val) {
3475 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3476 Val <<= Val.getBitWidth() - FromBits;
3477 Val = Val.ashr(Val.getBitWidth() - FromBits);
3478 return getConstant(Val, DL, VT.getScalarType());
3482 APInt Val = N1C->getAPIntValue();
3483 return SignExtendInReg(Val);
3485 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3486 SmallVector<SDValue, 8> Ops;
3487 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3488 SDValue Op = N1.getOperand(i);
3489 if (Op.getValueType() != VT.getScalarType()) break;
3490 if (Op.getOpcode() == ISD::UNDEF) {
3494 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3495 APInt Val = C->getAPIntValue();
3496 Ops.push_back(SignExtendInReg(Val));
3501 if (Ops.size() == VT.getVectorNumElements())
3502 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3506 case ISD::EXTRACT_VECTOR_ELT:
3507 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3508 if (N1.getOpcode() == ISD::UNDEF)
3509 return getUNDEF(VT);
3511 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3512 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3513 return getUNDEF(VT);
3515 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3516 // expanding copies of large vectors from registers.
3518 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3519 N1.getNumOperands() > 0) {
3521 N1.getOperand(0).getValueType().getVectorNumElements();
3522 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3523 N1.getOperand(N2C->getZExtValue() / Factor),
3524 getConstant(N2C->getZExtValue() % Factor, DL,
3525 N2.getValueType()));
3528 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3529 // expanding large vector constants.
3530 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3531 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3533 if (VT != Elt.getValueType())
3534 // If the vector element type is not legal, the BUILD_VECTOR operands
3535 // are promoted and implicitly truncated, and the result implicitly
3536 // extended. Make that explicit here.
3537 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3542 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3543 // operations are lowered to scalars.
3544 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3545 // If the indices are the same, return the inserted element else
3546 // if the indices are known different, extract the element from
3547 // the original vector.
3548 SDValue N1Op2 = N1.getOperand(2);
3549 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3551 if (N1Op2C && N2C) {
3552 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3553 if (VT == N1.getOperand(1).getValueType())
3554 return N1.getOperand(1);
3556 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3559 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3563 case ISD::EXTRACT_ELEMENT:
3564 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3565 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3566 (N1.getValueType().isInteger() == VT.isInteger()) &&
3567 N1.getValueType() != VT &&
3568 "Wrong types for EXTRACT_ELEMENT!");
3570 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3571 // 64-bit integers into 32-bit parts. Instead of building the extract of
3572 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3573 if (N1.getOpcode() == ISD::BUILD_PAIR)
3574 return N1.getOperand(N2C->getZExtValue());
3576 // EXTRACT_ELEMENT of a constant int is also very common.
3577 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3578 unsigned ElementSize = VT.getSizeInBits();
3579 unsigned Shift = ElementSize * N2C->getZExtValue();
3580 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3581 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3584 case ISD::EXTRACT_SUBVECTOR: {
3586 if (VT.isSimple() && N1.getValueType().isSimple()) {
3587 assert(VT.isVector() && N1.getValueType().isVector() &&
3588 "Extract subvector VTs must be a vectors!");
3589 assert(VT.getVectorElementType() ==
3590 N1.getValueType().getVectorElementType() &&
3591 "Extract subvector VTs must have the same element type!");
3592 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3593 "Extract subvector must be from larger vector to smaller vector!");
3595 if (isa<ConstantSDNode>(Index.getNode())) {
3596 assert((VT.getVectorNumElements() +
3597 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3598 <= N1.getValueType().getVectorNumElements())
3599 && "Extract subvector overflow!");
3602 // Trivial extraction.
3603 if (VT.getSimpleVT() == N1.getSimpleValueType())
3610 // Perform trivial constant folding.
3612 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3615 // Canonicalize constant to RHS if commutative.
3616 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3617 std::swap(N1C, N2C);
3621 // Constant fold FP operations.
3622 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3623 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3624 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3626 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3627 // Canonicalize constant to RHS if commutative.
3628 std::swap(N1CFP, N2CFP);
3631 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3632 APFloat::opStatus s;
3635 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3636 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3637 return getConstantFP(V1, DL, VT);
3640 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3641 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3642 return getConstantFP(V1, DL, VT);
3645 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3646 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3647 return getConstantFP(V1, DL, VT);
3650 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3651 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3652 s!=APFloat::opDivByZero)) {
3653 return getConstantFP(V1, DL, VT);
3657 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3658 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3659 s!=APFloat::opDivByZero)) {
3660 return getConstantFP(V1, DL, VT);
3663 case ISD::FCOPYSIGN:
3665 return getConstantFP(V1, DL, VT);
3670 if (Opcode == ISD::FP_ROUND) {
3671 APFloat V = N1CFP->getValueAPF(); // make copy
3673 // This can return overflow, underflow, or inexact; we don't care.
3674 // FIXME need to be more flexible about rounding mode.
3675 (void)V.convert(EVTToAPFloatSemantics(VT),
3676 APFloat::rmNearestTiesToEven, &ignored);
3677 return getConstantFP(V, DL, VT);
3681 // Canonicalize an UNDEF to the RHS, even over a constant.
3682 if (N1.getOpcode() == ISD::UNDEF) {
3683 if (isCommutativeBinOp(Opcode)) {
3687 case ISD::FP_ROUND_INREG:
3688 case ISD::SIGN_EXTEND_INREG:
3694 return N1; // fold op(undef, arg2) -> undef
3702 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3703 // For vectors, we can't easily build an all zero vector, just return
3710 // Fold a bunch of operators when the RHS is undef.
3711 if (N2.getOpcode() == ISD::UNDEF) {
3714 if (N1.getOpcode() == ISD::UNDEF)
3715 // Handle undef ^ undef -> 0 special case. This is a common
3717 return getConstant(0, DL, VT);
3727 return N2; // fold op(arg1, undef) -> undef
3733 if (getTarget().Options.UnsafeFPMath)
3741 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3742 // For vectors, we can't easily build an all zero vector, just return
3747 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3748 // For vectors, we can't easily build an all one vector, just return
3756 // Memoize this node if possible.
3758 SDVTList VTs = getVTList(VT);
3759 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3760 if (VT != MVT::Glue) {
3761 SDValue Ops[] = {N1, N2};
3762 FoldingSetNodeID ID;
3763 AddNodeIDNode(ID, Opcode, VTs, Ops);
3765 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3767 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3768 return SDValue(E, 0);
3770 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3772 CSEMap.InsertNode(N, IP);
3774 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3778 return SDValue(N, 0);
3781 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3782 SDValue N1, SDValue N2, SDValue N3) {
3783 // Perform various simplifications.
3784 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3787 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3788 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3789 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3790 if (N1CFP && N2CFP && N3CFP) {
3791 APFloat V1 = N1CFP->getValueAPF();
3792 const APFloat &V2 = N2CFP->getValueAPF();
3793 const APFloat &V3 = N3CFP->getValueAPF();
3794 APFloat::opStatus s =
3795 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3796 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3797 return getConstantFP(V1, DL, VT);
3801 case ISD::CONCAT_VECTORS:
3802 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3803 // one big BUILD_VECTOR.
3804 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3805 N2.getOpcode() == ISD::BUILD_VECTOR &&
3806 N3.getOpcode() == ISD::BUILD_VECTOR) {
3807 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3808 N1.getNode()->op_end());
3809 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3810 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3811 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3815 // Use FoldSetCC to simplify SETCC's.
3816 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3817 if (Simp.getNode()) return Simp;
3822 if (N1C->getZExtValue())
3823 return N2; // select true, X, Y -> X
3824 return N3; // select false, X, Y -> Y
3827 if (N2 == N3) return N2; // select C, X, X -> X
3829 case ISD::VECTOR_SHUFFLE:
3830 llvm_unreachable("should use getVectorShuffle constructor!");
3831 case ISD::INSERT_SUBVECTOR: {
3833 if (VT.isSimple() && N1.getValueType().isSimple()
3834 && N2.getValueType().isSimple()) {
3835 assert(VT.isVector() && N1.getValueType().isVector() &&
3836 N2.getValueType().isVector() &&
3837 "Insert subvector VTs must be a vectors");
3838 assert(VT == N1.getValueType() &&
3839 "Dest and insert subvector source types must match!");
3840 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3841 "Insert subvector must be from smaller vector to larger vector!");
3842 if (isa<ConstantSDNode>(Index.getNode())) {
3843 assert((N2.getValueType().getVectorNumElements() +
3844 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3845 <= VT.getVectorNumElements())
3846 && "Insert subvector overflow!");
3849 // Trivial insertion.
3850 if (VT.getSimpleVT() == N2.getSimpleValueType())
3856 // Fold bit_convert nodes from a type to themselves.
3857 if (N1.getValueType() == VT)
3862 // Memoize node if it doesn't produce a flag.
3864 SDVTList VTs = getVTList(VT);
3865 if (VT != MVT::Glue) {
3866 SDValue Ops[] = { N1, N2, N3 };
3867 FoldingSetNodeID ID;
3868 AddNodeIDNode(ID, Opcode, VTs, Ops);
3870 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3871 return SDValue(E, 0);
3873 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3874 DL.getDebugLoc(), VTs, N1, N2, N3);
3875 CSEMap.InsertNode(N, IP);
3877 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3878 DL.getDebugLoc(), VTs, N1, N2, N3);
3882 return SDValue(N, 0);
3885 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3886 SDValue N1, SDValue N2, SDValue N3,
3888 SDValue Ops[] = { N1, N2, N3, N4 };
3889 return getNode(Opcode, DL, VT, Ops);
3892 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3893 SDValue N1, SDValue N2, SDValue N3,
3894 SDValue N4, SDValue N5) {
3895 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3896 return getNode(Opcode, DL, VT, Ops);
3899 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3900 /// the incoming stack arguments to be loaded from the stack.
3901 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3902 SmallVector<SDValue, 8> ArgChains;
3904 // Include the original chain at the beginning of the list. When this is
3905 // used by target LowerCall hooks, this helps legalize find the
3906 // CALLSEQ_BEGIN node.
3907 ArgChains.push_back(Chain);
3909 // Add a chain value for each stack argument.
3910 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3911 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3912 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3913 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3914 if (FI->getIndex() < 0)
3915 ArgChains.push_back(SDValue(L, 1));
3917 // Build a tokenfactor for all the chains.
3918 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3921 /// getMemsetValue - Vectorized representation of the memset value
3923 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3925 assert(Value.getOpcode() != ISD::UNDEF);
3927 unsigned NumBits = VT.getScalarType().getSizeInBits();
3928 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3929 assert(C->getAPIntValue().getBitWidth() == 8);
3930 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3932 return DAG.getConstant(Val, dl, VT);
3933 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3937 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3938 EVT IntVT = VT.getScalarType();
3939 if (!IntVT.isInteger())
3940 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3942 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3944 // Use a multiplication with 0x010101... to extend the input to the
3946 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3947 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3948 DAG.getConstant(Magic, dl, IntVT));
3951 if (VT != Value.getValueType() && !VT.isInteger())
3952 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3953 if (VT != Value.getValueType()) {
3954 assert(VT.getVectorElementType() == Value.getValueType() &&
3955 "value type should be one vector element here");
3956 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3957 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3963 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3964 /// used when a memcpy is turned into a memset when the source is a constant
3966 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3967 const TargetLowering &TLI, StringRef Str) {
3968 // Handle vector with all elements zero.
3971 return DAG.getConstant(0, dl, VT);
3972 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3973 return DAG.getConstantFP(0.0, dl, VT);
3974 else if (VT.isVector()) {
3975 unsigned NumElts = VT.getVectorNumElements();
3976 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3977 return DAG.getNode(ISD::BITCAST, dl, VT,
3978 DAG.getConstant(0, dl,
3979 EVT::getVectorVT(*DAG.getContext(),
3982 llvm_unreachable("Expected type!");
3985 assert(!VT.isVector() && "Can't handle vector type here!");
3986 unsigned NumVTBits = VT.getSizeInBits();
3987 unsigned NumVTBytes = NumVTBits / 8;
3988 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3990 APInt Val(NumVTBits, 0);
3991 if (TLI.isLittleEndian()) {
3992 for (unsigned i = 0; i != NumBytes; ++i)
3993 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3995 for (unsigned i = 0; i != NumBytes; ++i)
3996 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3999 // If the "cost" of materializing the integer immediate is less than the cost
4000 // of a load, then it is cost effective to turn the load into the immediate.
4001 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4002 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4003 return DAG.getConstant(Val, dl, VT);
4004 return SDValue(nullptr, 0);
4007 /// getMemBasePlusOffset - Returns base and offset node for the
4009 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4010 SelectionDAG &DAG) {
4011 EVT VT = Base.getValueType();
4012 return DAG.getNode(ISD::ADD, dl,
4013 VT, Base, DAG.getConstant(Offset, dl, VT));
4016 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4018 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4019 unsigned SrcDelta = 0;
4020 GlobalAddressSDNode *G = nullptr;
4021 if (Src.getOpcode() == ISD::GlobalAddress)
4022 G = cast<GlobalAddressSDNode>(Src);
4023 else if (Src.getOpcode() == ISD::ADD &&
4024 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4025 Src.getOperand(1).getOpcode() == ISD::Constant) {
4026 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4027 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4032 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4035 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
4036 /// to replace the memset / memcpy. Return true if the number of memory ops
4037 /// is below the threshold. It returns the types of the sequence of
4038 /// memory ops to perform memset / memcpy by reference.
4039 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4040 unsigned Limit, uint64_t Size,
4041 unsigned DstAlign, unsigned SrcAlign,
4047 const TargetLowering &TLI) {
4048 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4049 "Expecting memcpy / memset source to meet alignment requirement!");
4050 // If 'SrcAlign' is zero, that means the memory operation does not need to
4051 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4052 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4053 // is the specified alignment of the memory operation. If it is zero, that
4054 // means it's possible to change the alignment of the destination.
4055 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4056 // not need to be loaded.
4057 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4058 IsMemset, ZeroMemset, MemcpyStrSrc,
4059 DAG.getMachineFunction());
4061 if (VT == MVT::Other) {
4063 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4064 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4065 VT = TLI.getPointerTy();
4067 switch (DstAlign & 7) {
4068 case 0: VT = MVT::i64; break;
4069 case 4: VT = MVT::i32; break;
4070 case 2: VT = MVT::i16; break;
4071 default: VT = MVT::i8; break;
4076 while (!TLI.isTypeLegal(LVT))
4077 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4078 assert(LVT.isInteger());
4084 unsigned NumMemOps = 0;
4086 unsigned VTSize = VT.getSizeInBits() / 8;
4087 while (VTSize > Size) {
4088 // For now, only use non-vector load / store's for the left-over pieces.
4093 if (VT.isVector() || VT.isFloatingPoint()) {
4094 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4095 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4096 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4098 else if (NewVT == MVT::i64 &&
4099 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4100 TLI.isSafeMemOpType(MVT::f64)) {
4101 // i64 is usually not legal on 32-bit targets, but f64 may be.
4109 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4110 if (NewVT == MVT::i8)
4112 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4114 NewVTSize = NewVT.getSizeInBits() / 8;
4116 // If the new VT cannot cover all of the remaining bits, then consider
4117 // issuing a (or a pair of) unaligned and overlapping load / store.
4118 // FIXME: Only does this for 64-bit or more since we don't have proper
4119 // cost model for unaligned load / store.
4122 if (NumMemOps && AllowOverlap &&
4123 VTSize >= 8 && NewVTSize < Size &&
4124 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4132 if (++NumMemOps > Limit)
4135 MemOps.push_back(VT);
4142 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4143 SDValue Chain, SDValue Dst,
4144 SDValue Src, uint64_t Size,
4145 unsigned Align, bool isVol,
4147 MachinePointerInfo DstPtrInfo,
4148 MachinePointerInfo SrcPtrInfo) {
4149 // Turn a memcpy of undef to nop.
4150 if (Src.getOpcode() == ISD::UNDEF)
4153 // Expand memcpy to a series of load and store ops if the size operand falls
4154 // below a certain threshold.
4155 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4156 // rather than maybe a humongous number of loads and stores.
4157 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4158 std::vector<EVT> MemOps;
4159 bool DstAlignCanChange = false;
4160 MachineFunction &MF = DAG.getMachineFunction();
4161 MachineFrameInfo *MFI = MF.getFrameInfo();
4162 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4163 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4164 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4165 DstAlignCanChange = true;
4166 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4167 if (Align > SrcAlign)
4170 bool CopyFromStr = isMemSrcFromString(Src, Str);
4171 bool isZeroStr = CopyFromStr && Str.empty();
4172 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4174 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4175 (DstAlignCanChange ? 0 : Align),
4176 (isZeroStr ? 0 : SrcAlign),
4177 false, false, CopyFromStr, true, DAG, TLI))
4180 if (DstAlignCanChange) {
4181 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4182 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4184 // Don't promote to an alignment that would require dynamic stack
4186 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4187 if (!TRI->needsStackRealignment(MF))
4188 while (NewAlign > Align &&
4189 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4192 if (NewAlign > Align) {
4193 // Give the stack frame object a larger alignment if needed.
4194 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4195 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4200 SmallVector<SDValue, 8> OutChains;
4201 unsigned NumMemOps = MemOps.size();
4202 uint64_t SrcOff = 0, DstOff = 0;
4203 for (unsigned i = 0; i != NumMemOps; ++i) {
4205 unsigned VTSize = VT.getSizeInBits() / 8;
4206 SDValue Value, Store;
4208 if (VTSize > Size) {
4209 // Issuing an unaligned load / store pair that overlaps with the previous
4210 // pair. Adjust the offset accordingly.
4211 assert(i == NumMemOps-1 && i != 0);
4212 SrcOff -= VTSize - Size;
4213 DstOff -= VTSize - Size;
4217 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4218 // It's unlikely a store of a vector immediate can be done in a single
4219 // instruction. It would require a load from a constantpool first.
4220 // We only handle zero vectors here.
4221 // FIXME: Handle other cases where store of vector immediate is done in
4222 // a single instruction.
4223 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4224 if (Value.getNode())
4225 Store = DAG.getStore(Chain, dl, Value,
4226 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4227 DstPtrInfo.getWithOffset(DstOff), isVol,
4231 if (!Store.getNode()) {
4232 // The type might not be legal for the target. This should only happen
4233 // if the type is smaller than a legal type, as on PPC, so the right
4234 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4235 // to Load/Store if NVT==VT.
4236 // FIXME does the case above also need this?
4237 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4238 assert(NVT.bitsGE(VT));
4239 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4240 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4241 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4242 false, MinAlign(SrcAlign, SrcOff));
4243 Store = DAG.getTruncStore(Chain, dl, Value,
4244 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4245 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4248 OutChains.push_back(Store);
4254 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4257 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4258 SDValue Chain, SDValue Dst,
4259 SDValue Src, uint64_t Size,
4260 unsigned Align, bool isVol,
4262 MachinePointerInfo DstPtrInfo,
4263 MachinePointerInfo SrcPtrInfo) {
4264 // Turn a memmove of undef to nop.
4265 if (Src.getOpcode() == ISD::UNDEF)
4268 // Expand memmove to a series of load and store ops if the size operand falls
4269 // below a certain threshold.
4270 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4271 std::vector<EVT> MemOps;
4272 bool DstAlignCanChange = false;
4273 MachineFunction &MF = DAG.getMachineFunction();
4274 MachineFrameInfo *MFI = MF.getFrameInfo();
4275 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4276 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4277 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4278 DstAlignCanChange = true;
4279 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4280 if (Align > SrcAlign)
4282 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4284 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4285 (DstAlignCanChange ? 0 : Align), SrcAlign,
4286 false, false, false, false, DAG, TLI))
4289 if (DstAlignCanChange) {
4290 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4291 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4292 if (NewAlign > Align) {
4293 // Give the stack frame object a larger alignment if needed.
4294 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4295 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4300 uint64_t SrcOff = 0, DstOff = 0;
4301 SmallVector<SDValue, 8> LoadValues;
4302 SmallVector<SDValue, 8> LoadChains;
4303 SmallVector<SDValue, 8> OutChains;
4304 unsigned NumMemOps = MemOps.size();
4305 for (unsigned i = 0; i < NumMemOps; i++) {
4307 unsigned VTSize = VT.getSizeInBits() / 8;
4310 Value = DAG.getLoad(VT, dl, Chain,
4311 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4312 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4313 false, false, SrcAlign);
4314 LoadValues.push_back(Value);
4315 LoadChains.push_back(Value.getValue(1));
4318 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4320 for (unsigned i = 0; i < NumMemOps; i++) {
4322 unsigned VTSize = VT.getSizeInBits() / 8;
4325 Store = DAG.getStore(Chain, dl, LoadValues[i],
4326 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4327 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4328 OutChains.push_back(Store);
4332 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4335 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4338 /// \param DAG Selection DAG where lowered code is placed.
4339 /// \param dl Link to corresponding IR location.
4340 /// \param Chain Control flow dependency.
4341 /// \param Dst Pointer to destination memory location.
4342 /// \param Src Value of byte to write into the memory.
4343 /// \param Size Number of bytes to write.
4344 /// \param Align Alignment of the destination in bytes.
4345 /// \param isVol True if destination is volatile.
4346 /// \param DstPtrInfo IR information on the memory pointer.
4347 /// \returns New head in the control flow, if lowering was successful, empty
4348 /// SDValue otherwise.
4350 /// The function tries to replace 'llvm.memset' intrinsic with several store
4351 /// operations and value calculation code. This is usually profitable for small
4353 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4354 SDValue Chain, SDValue Dst,
4355 SDValue Src, uint64_t Size,
4356 unsigned Align, bool isVol,
4357 MachinePointerInfo DstPtrInfo) {
4358 // Turn a memset of undef to nop.
4359 if (Src.getOpcode() == ISD::UNDEF)
4362 // Expand memset to a series of load/store ops if the size operand
4363 // falls below a certain threshold.
4364 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4365 std::vector<EVT> MemOps;
4366 bool DstAlignCanChange = false;
4367 MachineFunction &MF = DAG.getMachineFunction();
4368 MachineFrameInfo *MFI = MF.getFrameInfo();
4369 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4370 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4371 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4372 DstAlignCanChange = true;
4374 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4375 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4376 Size, (DstAlignCanChange ? 0 : Align), 0,
4377 true, IsZeroVal, false, true, DAG, TLI))
4380 if (DstAlignCanChange) {
4381 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4382 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4383 if (NewAlign > Align) {
4384 // Give the stack frame object a larger alignment if needed.
4385 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4386 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4391 SmallVector<SDValue, 8> OutChains;
4392 uint64_t DstOff = 0;
4393 unsigned NumMemOps = MemOps.size();
4395 // Find the largest store and generate the bit pattern for it.
4396 EVT LargestVT = MemOps[0];
4397 for (unsigned i = 1; i < NumMemOps; i++)
4398 if (MemOps[i].bitsGT(LargestVT))
4399 LargestVT = MemOps[i];
4400 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4402 for (unsigned i = 0; i < NumMemOps; i++) {
4404 unsigned VTSize = VT.getSizeInBits() / 8;
4405 if (VTSize > Size) {
4406 // Issuing an unaligned load / store pair that overlaps with the previous
4407 // pair. Adjust the offset accordingly.
4408 assert(i == NumMemOps-1 && i != 0);
4409 DstOff -= VTSize - Size;
4412 // If this store is smaller than the largest store see whether we can get
4413 // the smaller value for free with a truncate.
4414 SDValue Value = MemSetValue;
4415 if (VT.bitsLT(LargestVT)) {
4416 if (!LargestVT.isVector() && !VT.isVector() &&
4417 TLI.isTruncateFree(LargestVT, VT))
4418 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4420 Value = getMemsetValue(Src, VT, DAG, dl);
4422 assert(Value.getValueType() == VT && "Value with wrong type.");
4423 SDValue Store = DAG.getStore(Chain, dl, Value,
4424 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4425 DstPtrInfo.getWithOffset(DstOff),
4426 isVol, false, Align);
4427 OutChains.push_back(Store);
4428 DstOff += VT.getSizeInBits() / 8;
4432 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4435 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4436 SDValue Src, SDValue Size,
4437 unsigned Align, bool isVol, bool AlwaysInline,
4438 bool isTailCall, MachinePointerInfo DstPtrInfo,
4439 MachinePointerInfo SrcPtrInfo) {
4440 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4442 // Check to see if we should lower the memcpy to loads and stores first.
4443 // For cases within the target-specified limits, this is the best choice.
4444 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4446 // Memcpy with size zero? Just return the original chain.
4447 if (ConstantSize->isNullValue())
4450 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4451 ConstantSize->getZExtValue(),Align,
4452 isVol, false, DstPtrInfo, SrcPtrInfo);
4453 if (Result.getNode())
4457 // Then check to see if we should lower the memcpy with target-specific
4458 // code. If the target chooses to do this, this is the next best.
4460 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4461 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4462 DstPtrInfo, SrcPtrInfo);
4463 if (Result.getNode())
4467 // If we really need inline code and the target declined to provide it,
4468 // use a (potentially long) sequence of loads and stores.
4470 assert(ConstantSize && "AlwaysInline requires a constant size!");
4471 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4472 ConstantSize->getZExtValue(), Align, isVol,
4473 true, DstPtrInfo, SrcPtrInfo);
4476 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4477 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4478 // respect volatile, so they may do things like read or write memory
4479 // beyond the given memory regions. But fixing this isn't easy, and most
4480 // people don't care.
4482 // Emit a library call.
4483 TargetLowering::ArgListTy Args;
4484 TargetLowering::ArgListEntry Entry;
4485 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4486 Entry.Node = Dst; Args.push_back(Entry);
4487 Entry.Node = Src; Args.push_back(Entry);
4488 Entry.Node = Size; Args.push_back(Entry);
4489 // FIXME: pass in SDLoc
4490 TargetLowering::CallLoweringInfo CLI(*this);
4491 CLI.setDebugLoc(dl).setChain(Chain)
4492 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4493 Type::getVoidTy(*getContext()),
4494 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4495 TLI->getPointerTy()), std::move(Args), 0)
4497 .setTailCall(isTailCall);
4499 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4500 return CallResult.second;
4503 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4504 SDValue Src, SDValue Size,
4505 unsigned Align, bool isVol, bool isTailCall,
4506 MachinePointerInfo DstPtrInfo,
4507 MachinePointerInfo SrcPtrInfo) {
4508 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4510 // Check to see if we should lower the memmove to loads and stores first.
4511 // For cases within the target-specified limits, this is the best choice.
4512 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4514 // Memmove with size zero? Just return the original chain.
4515 if (ConstantSize->isNullValue())
4519 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4520 ConstantSize->getZExtValue(), Align, isVol,
4521 false, DstPtrInfo, SrcPtrInfo);
4522 if (Result.getNode())
4526 // Then check to see if we should lower the memmove with target-specific
4527 // code. If the target chooses to do this, this is the next best.
4529 SDValue Result = TSI->EmitTargetCodeForMemmove(
4530 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4531 if (Result.getNode())
4535 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4536 // not be safe. See memcpy above for more details.
4538 // Emit a library call.
4539 TargetLowering::ArgListTy Args;
4540 TargetLowering::ArgListEntry Entry;
4541 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4542 Entry.Node = Dst; Args.push_back(Entry);
4543 Entry.Node = Src; Args.push_back(Entry);
4544 Entry.Node = Size; Args.push_back(Entry);
4545 // FIXME: pass in SDLoc
4546 TargetLowering::CallLoweringInfo CLI(*this);
4547 CLI.setDebugLoc(dl).setChain(Chain)
4548 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4549 Type::getVoidTy(*getContext()),
4550 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4551 TLI->getPointerTy()), std::move(Args), 0)
4553 .setTailCall(isTailCall);
4555 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4556 return CallResult.second;
4559 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4560 SDValue Src, SDValue Size,
4561 unsigned Align, bool isVol, bool isTailCall,
4562 MachinePointerInfo DstPtrInfo) {
4563 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4565 // Check to see if we should lower the memset to stores first.
4566 // For cases within the target-specified limits, this is the best choice.
4567 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4569 // Memset with size zero? Just return the original chain.
4570 if (ConstantSize->isNullValue())
4574 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4575 Align, isVol, DstPtrInfo);
4577 if (Result.getNode())
4581 // Then check to see if we should lower the memset with target-specific
4582 // code. If the target chooses to do this, this is the next best.
4584 SDValue Result = TSI->EmitTargetCodeForMemset(
4585 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4586 if (Result.getNode())
4590 // Emit a library call.
4591 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4592 TargetLowering::ArgListTy Args;
4593 TargetLowering::ArgListEntry Entry;
4594 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4595 Args.push_back(Entry);
4597 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4598 Args.push_back(Entry);
4600 Entry.Ty = IntPtrTy;
4601 Args.push_back(Entry);
4603 // FIXME: pass in SDLoc
4604 TargetLowering::CallLoweringInfo CLI(*this);
4605 CLI.setDebugLoc(dl).setChain(Chain)
4606 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4607 Type::getVoidTy(*getContext()),
4608 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4609 TLI->getPointerTy()), std::move(Args), 0)
4611 .setTailCall(isTailCall);
4613 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4614 return CallResult.second;
4617 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4618 SDVTList VTList, ArrayRef<SDValue> Ops,
4619 MachineMemOperand *MMO,
4620 AtomicOrdering SuccessOrdering,
4621 AtomicOrdering FailureOrdering,
4622 SynchronizationScope SynchScope) {
4623 FoldingSetNodeID ID;
4624 ID.AddInteger(MemVT.getRawBits());
4625 AddNodeIDNode(ID, Opcode, VTList, Ops);
4626 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4628 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4629 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4630 return SDValue(E, 0);
4633 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4634 // SDNode doesn't have access to it. This memory will be "leaked" when
4635 // the node is deallocated, but recovered when the allocator is released.
4636 // If the number of operands is less than 5 we use AtomicSDNode's internal
4638 unsigned NumOps = Ops.size();
4639 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4642 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4643 dl.getDebugLoc(), VTList, MemVT,
4644 Ops.data(), DynOps, NumOps, MMO,
4645 SuccessOrdering, FailureOrdering,
4647 CSEMap.InsertNode(N, IP);
4649 return SDValue(N, 0);
4652 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4653 SDVTList VTList, ArrayRef<SDValue> Ops,
4654 MachineMemOperand *MMO,
4655 AtomicOrdering Ordering,
4656 SynchronizationScope SynchScope) {
4657 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4658 Ordering, SynchScope);
4661 SDValue SelectionDAG::getAtomicCmpSwap(
4662 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4663 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4664 unsigned Alignment, AtomicOrdering SuccessOrdering,
4665 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4666 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4667 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4668 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4670 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4671 Alignment = getEVTAlignment(MemVT);
4673 MachineFunction &MF = getMachineFunction();
4675 // FIXME: Volatile isn't really correct; we should keep track of atomic
4676 // orderings in the memoperand.
4677 unsigned Flags = MachineMemOperand::MOVolatile;
4678 Flags |= MachineMemOperand::MOLoad;
4679 Flags |= MachineMemOperand::MOStore;
4681 MachineMemOperand *MMO =
4682 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4684 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4685 SuccessOrdering, FailureOrdering, SynchScope);
4688 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4689 SDVTList VTs, SDValue Chain, SDValue Ptr,
4690 SDValue Cmp, SDValue Swp,
4691 MachineMemOperand *MMO,
4692 AtomicOrdering SuccessOrdering,
4693 AtomicOrdering FailureOrdering,
4694 SynchronizationScope SynchScope) {
4695 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4696 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4697 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4699 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4700 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4701 SuccessOrdering, FailureOrdering, SynchScope);
4704 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4706 SDValue Ptr, SDValue Val,
4707 const Value* PtrVal,
4709 AtomicOrdering Ordering,
4710 SynchronizationScope SynchScope) {
4711 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4712 Alignment = getEVTAlignment(MemVT);
4714 MachineFunction &MF = getMachineFunction();
4715 // An atomic store does not load. An atomic load does not store.
4716 // (An atomicrmw obviously both loads and stores.)
4717 // For now, atomics are considered to be volatile always, and they are
4719 // FIXME: Volatile isn't really correct; we should keep track of atomic
4720 // orderings in the memoperand.
4721 unsigned Flags = MachineMemOperand::MOVolatile;
4722 if (Opcode != ISD::ATOMIC_STORE)
4723 Flags |= MachineMemOperand::MOLoad;
4724 if (Opcode != ISD::ATOMIC_LOAD)
4725 Flags |= MachineMemOperand::MOStore;
4727 MachineMemOperand *MMO =
4728 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4729 MemVT.getStoreSize(), Alignment);
4731 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4732 Ordering, SynchScope);
4735 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4737 SDValue Ptr, SDValue Val,
4738 MachineMemOperand *MMO,
4739 AtomicOrdering Ordering,
4740 SynchronizationScope SynchScope) {
4741 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4742 Opcode == ISD::ATOMIC_LOAD_SUB ||
4743 Opcode == ISD::ATOMIC_LOAD_AND ||
4744 Opcode == ISD::ATOMIC_LOAD_OR ||
4745 Opcode == ISD::ATOMIC_LOAD_XOR ||
4746 Opcode == ISD::ATOMIC_LOAD_NAND ||
4747 Opcode == ISD::ATOMIC_LOAD_MIN ||
4748 Opcode == ISD::ATOMIC_LOAD_MAX ||
4749 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4750 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4751 Opcode == ISD::ATOMIC_SWAP ||
4752 Opcode == ISD::ATOMIC_STORE) &&
4753 "Invalid Atomic Op");
4755 EVT VT = Val.getValueType();
4757 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4758 getVTList(VT, MVT::Other);
4759 SDValue Ops[] = {Chain, Ptr, Val};
4760 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4763 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4764 EVT VT, SDValue Chain,
4766 MachineMemOperand *MMO,
4767 AtomicOrdering Ordering,
4768 SynchronizationScope SynchScope) {
4769 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4771 SDVTList VTs = getVTList(VT, MVT::Other);
4772 SDValue Ops[] = {Chain, Ptr};
4773 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4776 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4777 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4778 if (Ops.size() == 1)
4781 SmallVector<EVT, 4> VTs;
4782 VTs.reserve(Ops.size());
4783 for (unsigned i = 0; i < Ops.size(); ++i)
4784 VTs.push_back(Ops[i].getValueType());
4785 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4789 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4790 ArrayRef<SDValue> Ops,
4791 EVT MemVT, MachinePointerInfo PtrInfo,
4792 unsigned Align, bool Vol,
4793 bool ReadMem, bool WriteMem, unsigned Size) {
4794 if (Align == 0) // Ensure that codegen never sees alignment 0
4795 Align = getEVTAlignment(MemVT);
4797 MachineFunction &MF = getMachineFunction();
4800 Flags |= MachineMemOperand::MOStore;
4802 Flags |= MachineMemOperand::MOLoad;
4804 Flags |= MachineMemOperand::MOVolatile;
4806 Size = MemVT.getStoreSize();
4807 MachineMemOperand *MMO =
4808 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4810 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4814 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4815 ArrayRef<SDValue> Ops, EVT MemVT,
4816 MachineMemOperand *MMO) {
4817 assert((Opcode == ISD::INTRINSIC_VOID ||
4818 Opcode == ISD::INTRINSIC_W_CHAIN ||
4819 Opcode == ISD::PREFETCH ||
4820 Opcode == ISD::LIFETIME_START ||
4821 Opcode == ISD::LIFETIME_END ||
4822 (Opcode <= INT_MAX &&
4823 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4824 "Opcode is not a memory-accessing opcode!");
4826 // Memoize the node unless it returns a flag.
4827 MemIntrinsicSDNode *N;
4828 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4829 FoldingSetNodeID ID;
4830 AddNodeIDNode(ID, Opcode, VTList, Ops);
4831 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4833 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4834 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4835 return SDValue(E, 0);
4838 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4839 dl.getDebugLoc(), VTList, Ops,
4841 CSEMap.InsertNode(N, IP);
4843 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4844 dl.getDebugLoc(), VTList, Ops,
4848 return SDValue(N, 0);
4851 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4852 /// MachinePointerInfo record from it. This is particularly useful because the
4853 /// code generator has many cases where it doesn't bother passing in a
4854 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4855 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4856 // If this is FI+Offset, we can model it.
4857 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4858 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4860 // If this is (FI+Offset1)+Offset2, we can model it.
4861 if (Ptr.getOpcode() != ISD::ADD ||
4862 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4863 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4864 return MachinePointerInfo();
4866 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4867 return MachinePointerInfo::getFixedStack(FI, Offset+
4868 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4871 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4872 /// MachinePointerInfo record from it. This is particularly useful because the
4873 /// code generator has many cases where it doesn't bother passing in a
4874 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4875 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4876 // If the 'Offset' value isn't a constant, we can't handle this.
4877 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4878 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4879 if (OffsetOp.getOpcode() == ISD::UNDEF)
4880 return InferPointerInfo(Ptr);
4881 return MachinePointerInfo();
4886 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4887 EVT VT, SDLoc dl, SDValue Chain,
4888 SDValue Ptr, SDValue Offset,
4889 MachinePointerInfo PtrInfo, EVT MemVT,
4890 bool isVolatile, bool isNonTemporal, bool isInvariant,
4891 unsigned Alignment, const AAMDNodes &AAInfo,
4892 const MDNode *Ranges) {
4893 assert(Chain.getValueType() == MVT::Other &&
4894 "Invalid chain type");
4895 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4896 Alignment = getEVTAlignment(VT);
4898 unsigned Flags = MachineMemOperand::MOLoad;
4900 Flags |= MachineMemOperand::MOVolatile;
4902 Flags |= MachineMemOperand::MONonTemporal;
4904 Flags |= MachineMemOperand::MOInvariant;
4906 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4908 if (PtrInfo.V.isNull())
4909 PtrInfo = InferPointerInfo(Ptr, Offset);
4911 MachineFunction &MF = getMachineFunction();
4912 MachineMemOperand *MMO =
4913 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4915 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4919 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4920 EVT VT, SDLoc dl, SDValue Chain,
4921 SDValue Ptr, SDValue Offset, EVT MemVT,
4922 MachineMemOperand *MMO) {
4924 ExtType = ISD::NON_EXTLOAD;
4925 } else if (ExtType == ISD::NON_EXTLOAD) {
4926 assert(VT == MemVT && "Non-extending load from different memory type!");
4929 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4930 "Should only be an extending load, not truncating!");
4931 assert(VT.isInteger() == MemVT.isInteger() &&
4932 "Cannot convert from FP to Int or Int -> FP!");
4933 assert(VT.isVector() == MemVT.isVector() &&
4934 "Cannot use an ext load to convert to or from a vector!");
4935 assert((!VT.isVector() ||
4936 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4937 "Cannot use an ext load to change the number of vector elements!");
4940 bool Indexed = AM != ISD::UNINDEXED;
4941 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4942 "Unindexed load with an offset!");
4944 SDVTList VTs = Indexed ?
4945 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4946 SDValue Ops[] = { Chain, Ptr, Offset };
4947 FoldingSetNodeID ID;
4948 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4949 ID.AddInteger(MemVT.getRawBits());
4950 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4951 MMO->isNonTemporal(),
4952 MMO->isInvariant()));
4953 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4955 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4956 cast<LoadSDNode>(E)->refineAlignment(MMO);
4957 return SDValue(E, 0);
4959 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4960 dl.getDebugLoc(), VTs, AM, ExtType,
4962 CSEMap.InsertNode(N, IP);
4964 return SDValue(N, 0);
4967 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4968 SDValue Chain, SDValue Ptr,
4969 MachinePointerInfo PtrInfo,
4970 bool isVolatile, bool isNonTemporal,
4971 bool isInvariant, unsigned Alignment,
4972 const AAMDNodes &AAInfo,
4973 const MDNode *Ranges) {
4974 SDValue Undef = getUNDEF(Ptr.getValueType());
4975 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4976 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4980 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4981 SDValue Chain, SDValue Ptr,
4982 MachineMemOperand *MMO) {
4983 SDValue Undef = getUNDEF(Ptr.getValueType());
4984 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4988 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4989 SDValue Chain, SDValue Ptr,
4990 MachinePointerInfo PtrInfo, EVT MemVT,
4991 bool isVolatile, bool isNonTemporal,
4992 bool isInvariant, unsigned Alignment,
4993 const AAMDNodes &AAInfo) {
4994 SDValue Undef = getUNDEF(Ptr.getValueType());
4995 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4996 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5001 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5002 SDValue Chain, SDValue Ptr, EVT MemVT,
5003 MachineMemOperand *MMO) {
5004 SDValue Undef = getUNDEF(Ptr.getValueType());
5005 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5010 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5011 SDValue Offset, ISD::MemIndexedMode AM) {
5012 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5013 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5014 "Load is already a indexed load!");
5015 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5016 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5017 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5018 false, LD->getAlignment());
5021 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5022 SDValue Ptr, MachinePointerInfo PtrInfo,
5023 bool isVolatile, bool isNonTemporal,
5024 unsigned Alignment, const AAMDNodes &AAInfo) {
5025 assert(Chain.getValueType() == MVT::Other &&
5026 "Invalid chain type");
5027 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5028 Alignment = getEVTAlignment(Val.getValueType());
5030 unsigned Flags = MachineMemOperand::MOStore;
5032 Flags |= MachineMemOperand::MOVolatile;
5034 Flags |= MachineMemOperand::MONonTemporal;
5036 if (PtrInfo.V.isNull())
5037 PtrInfo = InferPointerInfo(Ptr);
5039 MachineFunction &MF = getMachineFunction();
5040 MachineMemOperand *MMO =
5041 MF.getMachineMemOperand(PtrInfo, Flags,
5042 Val.getValueType().getStoreSize(), Alignment,
5045 return getStore(Chain, dl, Val, Ptr, MMO);
5048 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5049 SDValue Ptr, MachineMemOperand *MMO) {
5050 assert(Chain.getValueType() == MVT::Other &&
5051 "Invalid chain type");
5052 EVT VT = Val.getValueType();
5053 SDVTList VTs = getVTList(MVT::Other);
5054 SDValue Undef = getUNDEF(Ptr.getValueType());
5055 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5056 FoldingSetNodeID ID;
5057 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5058 ID.AddInteger(VT.getRawBits());
5059 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5060 MMO->isNonTemporal(), MMO->isInvariant()));
5061 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5063 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5064 cast<StoreSDNode>(E)->refineAlignment(MMO);
5065 return SDValue(E, 0);
5067 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5068 dl.getDebugLoc(), VTs,
5069 ISD::UNINDEXED, false, VT, MMO);
5070 CSEMap.InsertNode(N, IP);
5072 return SDValue(N, 0);
5075 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5076 SDValue Ptr, MachinePointerInfo PtrInfo,
5077 EVT SVT,bool isVolatile, bool isNonTemporal,
5079 const AAMDNodes &AAInfo) {
5080 assert(Chain.getValueType() == MVT::Other &&
5081 "Invalid chain type");
5082 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5083 Alignment = getEVTAlignment(SVT);
5085 unsigned Flags = MachineMemOperand::MOStore;
5087 Flags |= MachineMemOperand::MOVolatile;
5089 Flags |= MachineMemOperand::MONonTemporal;
5091 if (PtrInfo.V.isNull())
5092 PtrInfo = InferPointerInfo(Ptr);
5094 MachineFunction &MF = getMachineFunction();
5095 MachineMemOperand *MMO =
5096 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5099 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5102 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5103 SDValue Ptr, EVT SVT,
5104 MachineMemOperand *MMO) {
5105 EVT VT = Val.getValueType();
5107 assert(Chain.getValueType() == MVT::Other &&
5108 "Invalid chain type");
5110 return getStore(Chain, dl, Val, Ptr, MMO);
5112 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5113 "Should only be a truncating store, not extending!");
5114 assert(VT.isInteger() == SVT.isInteger() &&
5115 "Can't do FP-INT conversion!");
5116 assert(VT.isVector() == SVT.isVector() &&
5117 "Cannot use trunc store to convert to or from a vector!");
5118 assert((!VT.isVector() ||
5119 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5120 "Cannot use trunc store to change the number of vector elements!");
5122 SDVTList VTs = getVTList(MVT::Other);
5123 SDValue Undef = getUNDEF(Ptr.getValueType());
5124 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5125 FoldingSetNodeID ID;
5126 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5127 ID.AddInteger(SVT.getRawBits());
5128 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5129 MMO->isNonTemporal(), MMO->isInvariant()));
5130 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5132 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5133 cast<StoreSDNode>(E)->refineAlignment(MMO);
5134 return SDValue(E, 0);
5136 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5137 dl.getDebugLoc(), VTs,
5138 ISD::UNINDEXED, true, SVT, MMO);
5139 CSEMap.InsertNode(N, IP);
5141 return SDValue(N, 0);
5145 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5146 SDValue Offset, ISD::MemIndexedMode AM) {
5147 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5148 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5149 "Store is already a indexed store!");
5150 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5151 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5152 FoldingSetNodeID ID;
5153 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5154 ID.AddInteger(ST->getMemoryVT().getRawBits());
5155 ID.AddInteger(ST->getRawSubclassData());
5156 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5158 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5159 return SDValue(E, 0);
5161 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5162 dl.getDebugLoc(), VTs, AM,
5163 ST->isTruncatingStore(),
5165 ST->getMemOperand());
5166 CSEMap.InsertNode(N, IP);
5168 return SDValue(N, 0);
5172 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5173 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5174 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5176 SDVTList VTs = getVTList(VT, MVT::Other);
5177 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5178 FoldingSetNodeID ID;
5179 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5180 ID.AddInteger(VT.getRawBits());
5181 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5183 MMO->isNonTemporal(),
5184 MMO->isInvariant()));
5185 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5187 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5188 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5189 return SDValue(E, 0);
5191 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5192 dl.getDebugLoc(), Ops, 4, VTs,
5194 CSEMap.InsertNode(N, IP);
5196 return SDValue(N, 0);
5199 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5200 SDValue Ptr, SDValue Mask, EVT MemVT,
5201 MachineMemOperand *MMO, bool isTrunc) {
5202 assert(Chain.getValueType() == MVT::Other &&
5203 "Invalid chain type");
5204 EVT VT = Val.getValueType();
5205 SDVTList VTs = getVTList(MVT::Other);
5206 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5207 FoldingSetNodeID ID;
5208 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5209 ID.AddInteger(VT.getRawBits());
5210 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5211 MMO->isNonTemporal(), MMO->isInvariant()));
5212 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5214 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5215 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5216 return SDValue(E, 0);
5218 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5219 dl.getDebugLoc(), Ops, 4,
5220 VTs, isTrunc, MemVT, MMO);
5221 CSEMap.InsertNode(N, IP);
5223 return SDValue(N, 0);
5227 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5228 ArrayRef<SDValue> Ops,
5229 MachineMemOperand *MMO) {
5231 FoldingSetNodeID ID;
5232 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5233 ID.AddInteger(VT.getRawBits());
5234 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5236 MMO->isNonTemporal(),
5237 MMO->isInvariant()));
5238 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5240 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5241 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5242 return SDValue(E, 0);
5244 MaskedGatherSDNode *N =
5245 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5247 CSEMap.InsertNode(N, IP);
5249 return SDValue(N, 0);
5252 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5253 ArrayRef<SDValue> Ops,
5254 MachineMemOperand *MMO) {
5255 FoldingSetNodeID ID;
5256 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5257 ID.AddInteger(VT.getRawBits());
5258 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5259 MMO->isNonTemporal(),
5260 MMO->isInvariant()));
5261 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5263 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5264 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5265 return SDValue(E, 0);
5268 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5270 CSEMap.InsertNode(N, IP);
5272 return SDValue(N, 0);
5275 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5276 SDValue Chain, SDValue Ptr,
5279 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5280 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5283 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5284 ArrayRef<SDUse> Ops) {
5285 switch (Ops.size()) {
5286 case 0: return getNode(Opcode, DL, VT);
5287 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5288 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5289 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5293 // Copy from an SDUse array into an SDValue array for use with
5294 // the regular getNode logic.
5295 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5296 return getNode(Opcode, DL, VT, NewOps);
5299 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5300 ArrayRef<SDValue> Ops) {
5301 unsigned NumOps = Ops.size();
5303 case 0: return getNode(Opcode, DL, VT);
5304 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5305 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5306 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5312 case ISD::SELECT_CC: {
5313 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5314 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5315 "LHS and RHS of condition must have same type!");
5316 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5317 "True and False arms of SelectCC must have same type!");
5318 assert(Ops[2].getValueType() == VT &&
5319 "select_cc node must be of same type as true and false value!");
5323 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5324 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5325 "LHS/RHS of comparison should match types!");
5332 SDVTList VTs = getVTList(VT);
5334 if (VT != MVT::Glue) {
5335 FoldingSetNodeID ID;
5336 AddNodeIDNode(ID, Opcode, VTs, Ops);
5339 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5340 return SDValue(E, 0);
5342 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5344 CSEMap.InsertNode(N, IP);
5346 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5351 return SDValue(N, 0);
5354 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5355 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5356 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5359 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5360 ArrayRef<SDValue> Ops) {
5361 if (VTList.NumVTs == 1)
5362 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5366 // FIXME: figure out how to safely handle things like
5367 // int foo(int x) { return 1 << (x & 255); }
5368 // int bar() { return foo(256); }
5369 case ISD::SRA_PARTS:
5370 case ISD::SRL_PARTS:
5371 case ISD::SHL_PARTS:
5372 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5373 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5374 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5375 else if (N3.getOpcode() == ISD::AND)
5376 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5377 // If the and is only masking out bits that cannot effect the shift,
5378 // eliminate the and.
5379 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5380 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5381 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5387 // Memoize the node unless it returns a flag.
5389 unsigned NumOps = Ops.size();
5390 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5391 FoldingSetNodeID ID;
5392 AddNodeIDNode(ID, Opcode, VTList, Ops);
5394 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5395 return SDValue(E, 0);
5398 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5399 DL.getDebugLoc(), VTList, Ops[0]);
5400 } else if (NumOps == 2) {
5401 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5402 DL.getDebugLoc(), VTList, Ops[0],
5404 } else if (NumOps == 3) {
5405 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5406 DL.getDebugLoc(), VTList, Ops[0],
5409 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5412 CSEMap.InsertNode(N, IP);
5415 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5416 DL.getDebugLoc(), VTList, Ops[0]);
5417 } else if (NumOps == 2) {
5418 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5419 DL.getDebugLoc(), VTList, Ops[0],
5421 } else if (NumOps == 3) {
5422 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5423 DL.getDebugLoc(), VTList, Ops[0],
5426 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5431 return SDValue(N, 0);
5434 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5435 return getNode(Opcode, DL, VTList, None);
5438 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5440 SDValue Ops[] = { N1 };
5441 return getNode(Opcode, DL, VTList, Ops);
5444 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5445 SDValue N1, SDValue N2) {
5446 SDValue Ops[] = { N1, N2 };
5447 return getNode(Opcode, DL, VTList, Ops);
5450 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5451 SDValue N1, SDValue N2, SDValue N3) {
5452 SDValue Ops[] = { N1, N2, N3 };
5453 return getNode(Opcode, DL, VTList, Ops);
5456 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5457 SDValue N1, SDValue N2, SDValue N3,
5459 SDValue Ops[] = { N1, N2, N3, N4 };
5460 return getNode(Opcode, DL, VTList, Ops);
5463 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5464 SDValue N1, SDValue N2, SDValue N3,
5465 SDValue N4, SDValue N5) {
5466 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5467 return getNode(Opcode, DL, VTList, Ops);
5470 SDVTList SelectionDAG::getVTList(EVT VT) {
5471 return makeVTList(SDNode::getValueTypeList(VT), 1);
5474 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5475 FoldingSetNodeID ID;
5477 ID.AddInteger(VT1.getRawBits());
5478 ID.AddInteger(VT2.getRawBits());
5481 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5483 EVT *Array = Allocator.Allocate<EVT>(2);
5486 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5487 VTListMap.InsertNode(Result, IP);
5489 return Result->getSDVTList();
5492 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5493 FoldingSetNodeID ID;
5495 ID.AddInteger(VT1.getRawBits());
5496 ID.AddInteger(VT2.getRawBits());
5497 ID.AddInteger(VT3.getRawBits());
5500 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5502 EVT *Array = Allocator.Allocate<EVT>(3);
5506 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5507 VTListMap.InsertNode(Result, IP);
5509 return Result->getSDVTList();
5512 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5513 FoldingSetNodeID ID;
5515 ID.AddInteger(VT1.getRawBits());
5516 ID.AddInteger(VT2.getRawBits());
5517 ID.AddInteger(VT3.getRawBits());
5518 ID.AddInteger(VT4.getRawBits());
5521 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5523 EVT *Array = Allocator.Allocate<EVT>(4);
5528 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5529 VTListMap.InsertNode(Result, IP);
5531 return Result->getSDVTList();
5534 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5535 unsigned NumVTs = VTs.size();
5536 FoldingSetNodeID ID;
5537 ID.AddInteger(NumVTs);
5538 for (unsigned index = 0; index < NumVTs; index++) {
5539 ID.AddInteger(VTs[index].getRawBits());
5543 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5545 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5546 std::copy(VTs.begin(), VTs.end(), Array);
5547 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5548 VTListMap.InsertNode(Result, IP);
5550 return Result->getSDVTList();
5554 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5555 /// specified operands. If the resultant node already exists in the DAG,
5556 /// this does not modify the specified node, instead it returns the node that
5557 /// already exists. If the resultant node does not exist in the DAG, the
5558 /// input node is returned. As a degenerate case, if you specify the same
5559 /// input operands as the node already has, the input node is returned.
5560 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5561 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5563 // Check to see if there is no change.
5564 if (Op == N->getOperand(0)) return N;
5566 // See if the modified node already exists.
5567 void *InsertPos = nullptr;
5568 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5571 // Nope it doesn't. Remove the node from its current place in the maps.
5573 if (!RemoveNodeFromCSEMaps(N))
5574 InsertPos = nullptr;
5576 // Now we update the operands.
5577 N->OperandList[0].set(Op);
5579 // If this gets put into a CSE map, add it.
5580 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5584 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5585 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5587 // Check to see if there is no change.
5588 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5589 return N; // No operands changed, just return the input node.
5591 // See if the modified node already exists.
5592 void *InsertPos = nullptr;
5593 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5596 // Nope it doesn't. Remove the node from its current place in the maps.
5598 if (!RemoveNodeFromCSEMaps(N))
5599 InsertPos = nullptr;
5601 // Now we update the operands.
5602 if (N->OperandList[0] != Op1)
5603 N->OperandList[0].set(Op1);
5604 if (N->OperandList[1] != Op2)
5605 N->OperandList[1].set(Op2);
5607 // If this gets put into a CSE map, add it.
5608 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5612 SDNode *SelectionDAG::
5613 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5614 SDValue Ops[] = { Op1, Op2, Op3 };
5615 return UpdateNodeOperands(N, Ops);
5618 SDNode *SelectionDAG::
5619 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5620 SDValue Op3, SDValue Op4) {
5621 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5622 return UpdateNodeOperands(N, Ops);
5625 SDNode *SelectionDAG::
5626 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5627 SDValue Op3, SDValue Op4, SDValue Op5) {
5628 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5629 return UpdateNodeOperands(N, Ops);
5632 SDNode *SelectionDAG::
5633 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5634 unsigned NumOps = Ops.size();
5635 assert(N->getNumOperands() == NumOps &&
5636 "Update with wrong number of operands");
5638 // If no operands changed just return the input node.
5639 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5642 // See if the modified node already exists.
5643 void *InsertPos = nullptr;
5644 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5647 // Nope it doesn't. Remove the node from its current place in the maps.
5649 if (!RemoveNodeFromCSEMaps(N))
5650 InsertPos = nullptr;
5652 // Now we update the operands.
5653 for (unsigned i = 0; i != NumOps; ++i)
5654 if (N->OperandList[i] != Ops[i])
5655 N->OperandList[i].set(Ops[i]);
5657 // If this gets put into a CSE map, add it.
5658 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5662 /// DropOperands - Release the operands and set this node to have
5664 void SDNode::DropOperands() {
5665 // Unlike the code in MorphNodeTo that does this, we don't need to
5666 // watch for dead nodes here.
5667 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5673 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5676 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5678 SDVTList VTs = getVTList(VT);
5679 return SelectNodeTo(N, MachineOpc, VTs, None);
5682 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5683 EVT VT, SDValue Op1) {
5684 SDVTList VTs = getVTList(VT);
5685 SDValue Ops[] = { Op1 };
5686 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5689 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5690 EVT VT, SDValue Op1,
5692 SDVTList VTs = getVTList(VT);
5693 SDValue Ops[] = { Op1, Op2 };
5694 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698 EVT VT, SDValue Op1,
5699 SDValue Op2, SDValue Op3) {
5700 SDVTList VTs = getVTList(VT);
5701 SDValue Ops[] = { Op1, Op2, Op3 };
5702 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5705 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5706 EVT VT, ArrayRef<SDValue> Ops) {
5707 SDVTList VTs = getVTList(VT);
5708 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5711 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5712 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5713 SDVTList VTs = getVTList(VT1, VT2);
5714 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5717 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5719 SDVTList VTs = getVTList(VT1, VT2);
5720 return SelectNodeTo(N, MachineOpc, VTs, None);
5723 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5724 EVT VT1, EVT VT2, EVT VT3,
5725 ArrayRef<SDValue> Ops) {
5726 SDVTList VTs = getVTList(VT1, VT2, VT3);
5727 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5730 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5731 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5732 ArrayRef<SDValue> Ops) {
5733 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5734 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5737 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5740 SDVTList VTs = getVTList(VT1, VT2);
5741 SDValue Ops[] = { Op1 };
5742 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5745 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5747 SDValue Op1, SDValue Op2) {
5748 SDVTList VTs = getVTList(VT1, VT2);
5749 SDValue Ops[] = { Op1, Op2 };
5750 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5753 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5755 SDValue Op1, SDValue Op2,
5757 SDVTList VTs = getVTList(VT1, VT2);
5758 SDValue Ops[] = { Op1, Op2, Op3 };
5759 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5762 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5763 EVT VT1, EVT VT2, EVT VT3,
5764 SDValue Op1, SDValue Op2,
5766 SDVTList VTs = getVTList(VT1, VT2, VT3);
5767 SDValue Ops[] = { Op1, Op2, Op3 };
5768 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5771 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5772 SDVTList VTs,ArrayRef<SDValue> Ops) {
5773 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5774 // Reset the NodeID to -1.
5779 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5780 /// the line number information on the merged node since it is not possible to
5781 /// preserve the information that operation is associated with multiple lines.
5782 /// This will make the debugger working better at -O0, were there is a higher
5783 /// probability having other instructions associated with that line.
5785 /// For IROrder, we keep the smaller of the two
5786 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5787 DebugLoc NLoc = N->getDebugLoc();
5788 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5789 N->setDebugLoc(DebugLoc());
5791 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5792 N->setIROrder(Order);
5796 /// MorphNodeTo - This *mutates* the specified node to have the specified
5797 /// return type, opcode, and operands.
5799 /// Note that MorphNodeTo returns the resultant node. If there is already a
5800 /// node of the specified opcode and operands, it returns that node instead of
5801 /// the current one. Note that the SDLoc need not be the same.
5803 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5804 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5805 /// node, and because it doesn't require CSE recalculation for any of
5806 /// the node's users.
5808 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5809 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5810 /// the legalizer which maintain worklists that would need to be updated when
5811 /// deleting things.
5812 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5813 SDVTList VTs, ArrayRef<SDValue> Ops) {
5814 unsigned NumOps = Ops.size();
5815 // If an identical node already exists, use it.
5817 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5818 FoldingSetNodeID ID;
5819 AddNodeIDNode(ID, Opc, VTs, Ops);
5820 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5821 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5824 if (!RemoveNodeFromCSEMaps(N))
5827 // Start the morphing.
5829 N->ValueList = VTs.VTs;
5830 N->NumValues = VTs.NumVTs;
5832 // Clear the operands list, updating used nodes to remove this from their
5833 // use list. Keep track of any operands that become dead as a result.
5834 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5835 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5837 SDNode *Used = Use.getNode();
5839 if (Used->use_empty())
5840 DeadNodeSet.insert(Used);
5843 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5844 // Initialize the memory references information.
5845 MN->setMemRefs(nullptr, nullptr);
5846 // If NumOps is larger than the # of operands we can have in a
5847 // MachineSDNode, reallocate the operand list.
5848 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5849 if (MN->OperandsNeedDelete)
5850 delete[] MN->OperandList;
5851 if (NumOps > array_lengthof(MN->LocalOperands))
5852 // We're creating a final node that will live unmorphed for the
5853 // remainder of the current SelectionDAG iteration, so we can allocate
5854 // the operands directly out of a pool with no recycling metadata.
5855 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5856 Ops.data(), NumOps);
5858 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5859 MN->OperandsNeedDelete = false;
5861 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5863 // If NumOps is larger than the # of operands we currently have, reallocate
5864 // the operand list.
5865 if (NumOps > N->NumOperands) {
5866 if (N->OperandsNeedDelete)
5867 delete[] N->OperandList;
5868 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5869 N->OperandsNeedDelete = true;
5871 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5874 // Delete any nodes that are still dead after adding the uses for the
5876 if (!DeadNodeSet.empty()) {
5877 SmallVector<SDNode *, 16> DeadNodes;
5878 for (SDNode *N : DeadNodeSet)
5880 DeadNodes.push_back(N);
5881 RemoveDeadNodes(DeadNodes);
5885 CSEMap.InsertNode(N, IP); // Memoize the new node.
5890 /// getMachineNode - These are used for target selectors to create a new node
5891 /// with specified return type(s), MachineInstr opcode, and operands.
5893 /// Note that getMachineNode returns the resultant node. If there is already a
5894 /// node of the specified opcode and operands, it returns that node instead of
5895 /// the current one.
5897 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5898 SDVTList VTs = getVTList(VT);
5899 return getMachineNode(Opcode, dl, VTs, None);
5903 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5904 SDVTList VTs = getVTList(VT);
5905 SDValue Ops[] = { Op1 };
5906 return getMachineNode(Opcode, dl, VTs, Ops);
5910 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5911 SDValue Op1, SDValue Op2) {
5912 SDVTList VTs = getVTList(VT);
5913 SDValue Ops[] = { Op1, Op2 };
5914 return getMachineNode(Opcode, dl, VTs, Ops);
5918 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5919 SDValue Op1, SDValue Op2, SDValue Op3) {
5920 SDVTList VTs = getVTList(VT);
5921 SDValue Ops[] = { Op1, Op2, Op3 };
5922 return getMachineNode(Opcode, dl, VTs, Ops);
5926 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5927 ArrayRef<SDValue> Ops) {
5928 SDVTList VTs = getVTList(VT);
5929 return getMachineNode(Opcode, dl, VTs, Ops);
5933 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5934 SDVTList VTs = getVTList(VT1, VT2);
5935 return getMachineNode(Opcode, dl, VTs, None);
5939 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5940 EVT VT1, EVT VT2, SDValue Op1) {
5941 SDVTList VTs = getVTList(VT1, VT2);
5942 SDValue Ops[] = { Op1 };
5943 return getMachineNode(Opcode, dl, VTs, Ops);
5947 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5948 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5949 SDVTList VTs = getVTList(VT1, VT2);
5950 SDValue Ops[] = { Op1, Op2 };
5951 return getMachineNode(Opcode, dl, VTs, Ops);
5955 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5956 EVT VT1, EVT VT2, SDValue Op1,
5957 SDValue Op2, SDValue Op3) {
5958 SDVTList VTs = getVTList(VT1, VT2);
5959 SDValue Ops[] = { Op1, Op2, Op3 };
5960 return getMachineNode(Opcode, dl, VTs, Ops);
5964 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5966 ArrayRef<SDValue> Ops) {
5967 SDVTList VTs = getVTList(VT1, VT2);
5968 return getMachineNode(Opcode, dl, VTs, Ops);
5972 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5973 EVT VT1, EVT VT2, EVT VT3,
5974 SDValue Op1, SDValue Op2) {
5975 SDVTList VTs = getVTList(VT1, VT2, VT3);
5976 SDValue Ops[] = { Op1, Op2 };
5977 return getMachineNode(Opcode, dl, VTs, Ops);
5981 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5982 EVT VT1, EVT VT2, EVT VT3,
5983 SDValue Op1, SDValue Op2, SDValue Op3) {
5984 SDVTList VTs = getVTList(VT1, VT2, VT3);
5985 SDValue Ops[] = { Op1, Op2, Op3 };
5986 return getMachineNode(Opcode, dl, VTs, Ops);
5990 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5991 EVT VT1, EVT VT2, EVT VT3,
5992 ArrayRef<SDValue> Ops) {
5993 SDVTList VTs = getVTList(VT1, VT2, VT3);
5994 return getMachineNode(Opcode, dl, VTs, Ops);
5998 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5999 EVT VT2, EVT VT3, EVT VT4,
6000 ArrayRef<SDValue> Ops) {
6001 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6002 return getMachineNode(Opcode, dl, VTs, Ops);
6006 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6007 ArrayRef<EVT> ResultTys,
6008 ArrayRef<SDValue> Ops) {
6009 SDVTList VTs = getVTList(ResultTys);
6010 return getMachineNode(Opcode, dl, VTs, Ops);
6014 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6015 ArrayRef<SDValue> OpsArray) {
6016 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6019 const SDValue *Ops = OpsArray.data();
6020 unsigned NumOps = OpsArray.size();
6023 FoldingSetNodeID ID;
6024 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6026 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6027 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6031 // Allocate a new MachineSDNode.
6032 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6033 DL.getDebugLoc(), VTs);
6035 // Initialize the operands list.
6036 if (NumOps > array_lengthof(N->LocalOperands))
6037 // We're creating a final node that will live unmorphed for the
6038 // remainder of the current SelectionDAG iteration, so we can allocate
6039 // the operands directly out of a pool with no recycling metadata.
6040 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6043 N->InitOperands(N->LocalOperands, Ops, NumOps);
6044 N->OperandsNeedDelete = false;
6047 CSEMap.InsertNode(N, IP);
6053 /// getTargetExtractSubreg - A convenience function for creating
6054 /// TargetOpcode::EXTRACT_SUBREG nodes.
6056 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6058 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6059 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6060 VT, Operand, SRIdxVal);
6061 return SDValue(Subreg, 0);
6064 /// getTargetInsertSubreg - A convenience function for creating
6065 /// TargetOpcode::INSERT_SUBREG nodes.
6067 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6068 SDValue Operand, SDValue Subreg) {
6069 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6070 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6071 VT, Operand, Subreg, SRIdxVal);
6072 return SDValue(Result, 0);
6075 /// getNodeIfExists - Get the specified node if it's already available, or
6076 /// else return NULL.
6077 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6078 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6080 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6081 FoldingSetNodeID ID;
6082 AddNodeIDNode(ID, Opcode, VTList, Ops);
6083 if (isBinOpWithFlags(Opcode))
6084 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6086 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6092 /// getDbgValue - Creates a SDDbgValue node.
6095 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6096 unsigned R, bool IsIndirect, uint64_t Off,
6097 DebugLoc DL, unsigned O) {
6098 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6099 "Expected inlined-at fields to agree");
6100 return new (DbgInfo->getAlloc())
6101 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6105 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6106 const Value *C, uint64_t Off,
6107 DebugLoc DL, unsigned O) {
6108 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6109 "Expected inlined-at fields to agree");
6110 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6114 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6115 unsigned FI, uint64_t Off,
6116 DebugLoc DL, unsigned O) {
6117 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6118 "Expected inlined-at fields to agree");
6119 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6124 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6125 /// pointed to by a use iterator is deleted, increment the use iterator
6126 /// so that it doesn't dangle.
6128 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6129 SDNode::use_iterator &UI;
6130 SDNode::use_iterator &UE;
6132 void NodeDeleted(SDNode *N, SDNode *E) override {
6133 // Increment the iterator as needed.
6134 while (UI != UE && N == *UI)
6139 RAUWUpdateListener(SelectionDAG &d,
6140 SDNode::use_iterator &ui,
6141 SDNode::use_iterator &ue)
6142 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6147 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6148 /// This can cause recursive merging of nodes in the DAG.
6150 /// This version assumes From has a single result value.
6152 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6153 SDNode *From = FromN.getNode();
6154 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6155 "Cannot replace with this method!");
6156 assert(From != To.getNode() && "Cannot replace uses of with self");
6158 // Iterate over all the existing uses of From. New uses will be added
6159 // to the beginning of the use list, which we avoid visiting.
6160 // This specifically avoids visiting uses of From that arise while the
6161 // replacement is happening, because any such uses would be the result
6162 // of CSE: If an existing node looks like From after one of its operands
6163 // is replaced by To, we don't want to replace of all its users with To
6164 // too. See PR3018 for more info.
6165 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6166 RAUWUpdateListener Listener(*this, UI, UE);
6170 // This node is about to morph, remove its old self from the CSE maps.
6171 RemoveNodeFromCSEMaps(User);
6173 // A user can appear in a use list multiple times, and when this
6174 // happens the uses are usually next to each other in the list.
6175 // To help reduce the number of CSE recomputations, process all
6176 // the uses of this user that we can find this way.
6178 SDUse &Use = UI.getUse();
6181 } while (UI != UE && *UI == User);
6183 // Now that we have modified User, add it back to the CSE maps. If it
6184 // already exists there, recursively merge the results together.
6185 AddModifiedNodeToCSEMaps(User);
6188 // If we just RAUW'd the root, take note.
6189 if (FromN == getRoot())
6193 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6194 /// This can cause recursive merging of nodes in the DAG.
6196 /// This version assumes that for each value of From, there is a
6197 /// corresponding value in To in the same position with the same type.
6199 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6201 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6202 assert((!From->hasAnyUseOfValue(i) ||
6203 From->getValueType(i) == To->getValueType(i)) &&
6204 "Cannot use this version of ReplaceAllUsesWith!");
6207 // Handle the trivial case.
6211 // Iterate over just the existing users of From. See the comments in
6212 // the ReplaceAllUsesWith above.
6213 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6214 RAUWUpdateListener Listener(*this, UI, UE);
6218 // This node is about to morph, remove its old self from the CSE maps.
6219 RemoveNodeFromCSEMaps(User);
6221 // A user can appear in a use list multiple times, and when this
6222 // happens the uses are usually next to each other in the list.
6223 // To help reduce the number of CSE recomputations, process all
6224 // the uses of this user that we can find this way.
6226 SDUse &Use = UI.getUse();
6229 } while (UI != UE && *UI == User);
6231 // Now that we have modified User, add it back to the CSE maps. If it
6232 // already exists there, recursively merge the results together.
6233 AddModifiedNodeToCSEMaps(User);
6236 // If we just RAUW'd the root, take note.
6237 if (From == getRoot().getNode())
6238 setRoot(SDValue(To, getRoot().getResNo()));
6241 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6242 /// This can cause recursive merging of nodes in the DAG.
6244 /// This version can replace From with any result values. To must match the
6245 /// number and types of values returned by From.
6246 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6247 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6248 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6250 // Iterate over just the existing users of From. See the comments in
6251 // the ReplaceAllUsesWith above.
6252 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6253 RAUWUpdateListener Listener(*this, UI, UE);
6257 // This node is about to morph, remove its old self from the CSE maps.
6258 RemoveNodeFromCSEMaps(User);
6260 // A user can appear in a use list multiple times, and when this
6261 // happens the uses are usually next to each other in the list.
6262 // To help reduce the number of CSE recomputations, process all
6263 // the uses of this user that we can find this way.
6265 SDUse &Use = UI.getUse();
6266 const SDValue &ToOp = To[Use.getResNo()];
6269 } while (UI != UE && *UI == User);
6271 // Now that we have modified User, add it back to the CSE maps. If it
6272 // already exists there, recursively merge the results together.
6273 AddModifiedNodeToCSEMaps(User);
6276 // If we just RAUW'd the root, take note.
6277 if (From == getRoot().getNode())
6278 setRoot(SDValue(To[getRoot().getResNo()]));
6281 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6282 /// uses of other values produced by From.getNode() alone. The Deleted
6283 /// vector is handled the same way as for ReplaceAllUsesWith.
6284 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6285 // Handle the really simple, really trivial case efficiently.
6286 if (From == To) return;
6288 // Handle the simple, trivial, case efficiently.
6289 if (From.getNode()->getNumValues() == 1) {
6290 ReplaceAllUsesWith(From, To);
6294 // Iterate over just the existing users of From. See the comments in
6295 // the ReplaceAllUsesWith above.
6296 SDNode::use_iterator UI = From.getNode()->use_begin(),
6297 UE = From.getNode()->use_end();
6298 RAUWUpdateListener Listener(*this, UI, UE);
6301 bool UserRemovedFromCSEMaps = false;
6303 // A user can appear in a use list multiple times, and when this
6304 // happens the uses are usually next to each other in the list.
6305 // To help reduce the number of CSE recomputations, process all
6306 // the uses of this user that we can find this way.
6308 SDUse &Use = UI.getUse();
6310 // Skip uses of different values from the same node.
6311 if (Use.getResNo() != From.getResNo()) {
6316 // If this node hasn't been modified yet, it's still in the CSE maps,
6317 // so remove its old self from the CSE maps.
6318 if (!UserRemovedFromCSEMaps) {
6319 RemoveNodeFromCSEMaps(User);
6320 UserRemovedFromCSEMaps = true;
6325 } while (UI != UE && *UI == User);
6327 // We are iterating over all uses of the From node, so if a use
6328 // doesn't use the specific value, no changes are made.
6329 if (!UserRemovedFromCSEMaps)
6332 // Now that we have modified User, add it back to the CSE maps. If it
6333 // already exists there, recursively merge the results together.
6334 AddModifiedNodeToCSEMaps(User);
6337 // If we just RAUW'd the root, take note.
6338 if (From == getRoot())
6343 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6344 /// to record information about a use.
6351 /// operator< - Sort Memos by User.
6352 bool operator<(const UseMemo &L, const UseMemo &R) {
6353 return (intptr_t)L.User < (intptr_t)R.User;
6357 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6358 /// uses of other values produced by From.getNode() alone. The same value
6359 /// may appear in both the From and To list. The Deleted vector is
6360 /// handled the same way as for ReplaceAllUsesWith.
6361 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6364 // Handle the simple, trivial case efficiently.
6366 return ReplaceAllUsesOfValueWith(*From, *To);
6368 // Read up all the uses and make records of them. This helps
6369 // processing new uses that are introduced during the
6370 // replacement process.
6371 SmallVector<UseMemo, 4> Uses;
6372 for (unsigned i = 0; i != Num; ++i) {
6373 unsigned FromResNo = From[i].getResNo();
6374 SDNode *FromNode = From[i].getNode();
6375 for (SDNode::use_iterator UI = FromNode->use_begin(),
6376 E = FromNode->use_end(); UI != E; ++UI) {
6377 SDUse &Use = UI.getUse();
6378 if (Use.getResNo() == FromResNo) {
6379 UseMemo Memo = { *UI, i, &Use };
6380 Uses.push_back(Memo);
6385 // Sort the uses, so that all the uses from a given User are together.
6386 std::sort(Uses.begin(), Uses.end());
6388 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6389 UseIndex != UseIndexEnd; ) {
6390 // We know that this user uses some value of From. If it is the right
6391 // value, update it.
6392 SDNode *User = Uses[UseIndex].User;
6394 // This node is about to morph, remove its old self from the CSE maps.
6395 RemoveNodeFromCSEMaps(User);
6397 // The Uses array is sorted, so all the uses for a given User
6398 // are next to each other in the list.
6399 // To help reduce the number of CSE recomputations, process all
6400 // the uses of this user that we can find this way.
6402 unsigned i = Uses[UseIndex].Index;
6403 SDUse &Use = *Uses[UseIndex].Use;
6407 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6409 // Now that we have modified User, add it back to the CSE maps. If it
6410 // already exists there, recursively merge the results together.
6411 AddModifiedNodeToCSEMaps(User);
6415 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6416 /// based on their topological order. It returns the maximum id and a vector
6417 /// of the SDNodes* in assigned order by reference.
6418 unsigned SelectionDAG::AssignTopologicalOrder() {
6420 unsigned DAGSize = 0;
6422 // SortedPos tracks the progress of the algorithm. Nodes before it are
6423 // sorted, nodes after it are unsorted. When the algorithm completes
6424 // it is at the end of the list.
6425 allnodes_iterator SortedPos = allnodes_begin();
6427 // Visit all the nodes. Move nodes with no operands to the front of
6428 // the list immediately. Annotate nodes that do have operands with their
6429 // operand count. Before we do this, the Node Id fields of the nodes
6430 // may contain arbitrary values. After, the Node Id fields for nodes
6431 // before SortedPos will contain the topological sort index, and the
6432 // Node Id fields for nodes At SortedPos and after will contain the
6433 // count of outstanding operands.
6434 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6436 checkForCycles(N, this);
6437 unsigned Degree = N->getNumOperands();
6439 // A node with no uses, add it to the result array immediately.
6440 N->setNodeId(DAGSize++);
6441 allnodes_iterator Q = N;
6443 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6444 assert(SortedPos != AllNodes.end() && "Overran node list");
6447 // Temporarily use the Node Id as scratch space for the degree count.
6448 N->setNodeId(Degree);
6452 // Visit all the nodes. As we iterate, move nodes into sorted order,
6453 // such that by the time the end is reached all nodes will be sorted.
6454 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6456 checkForCycles(N, this);
6457 // N is in sorted position, so all its uses have one less operand
6458 // that needs to be sorted.
6459 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6462 unsigned Degree = P->getNodeId();
6463 assert(Degree != 0 && "Invalid node degree");
6466 // All of P's operands are sorted, so P may sorted now.
6467 P->setNodeId(DAGSize++);
6469 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6470 assert(SortedPos != AllNodes.end() && "Overran node list");
6473 // Update P's outstanding operand count.
6474 P->setNodeId(Degree);
6477 if (I == SortedPos) {
6480 dbgs() << "Overran sorted position:\n";
6481 S->dumprFull(this); dbgs() << "\n";
6482 dbgs() << "Checking if this is due to cycles\n";
6483 checkForCycles(this, true);
6485 llvm_unreachable(nullptr);
6489 assert(SortedPos == AllNodes.end() &&
6490 "Topological sort incomplete!");
6491 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6492 "First node in topological sort is not the entry token!");
6493 assert(AllNodes.front().getNodeId() == 0 &&
6494 "First node in topological sort has non-zero id!");
6495 assert(AllNodes.front().getNumOperands() == 0 &&
6496 "First node in topological sort has operands!");
6497 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6498 "Last node in topologic sort has unexpected id!");
6499 assert(AllNodes.back().use_empty() &&
6500 "Last node in topologic sort has users!");
6501 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6505 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6506 /// value is produced by SD.
6507 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6509 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6510 SD->setHasDebugValue(true);
6512 DbgInfo->add(DB, SD, isParameter);
6515 /// TransferDbgValues - Transfer SDDbgValues.
6516 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6517 if (From == To || !From.getNode()->getHasDebugValue())
6519 SDNode *FromNode = From.getNode();
6520 SDNode *ToNode = To.getNode();
6521 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6522 SmallVector<SDDbgValue *, 2> ClonedDVs;
6523 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6525 SDDbgValue *Dbg = *I;
6526 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6528 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6529 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6530 Dbg->getDebugLoc(), Dbg->getOrder());
6531 ClonedDVs.push_back(Clone);
6534 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6535 E = ClonedDVs.end(); I != E; ++I)
6536 AddDbgValue(*I, ToNode, false);
6539 //===----------------------------------------------------------------------===//
6541 //===----------------------------------------------------------------------===//
6543 HandleSDNode::~HandleSDNode() {
6547 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6548 DebugLoc DL, const GlobalValue *GA,
6549 EVT VT, int64_t o, unsigned char TF)
6550 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6554 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6555 SDValue X, unsigned SrcAS,
6557 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6558 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6560 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6561 EVT memvt, MachineMemOperand *mmo)
6562 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6563 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6564 MMO->isNonTemporal(), MMO->isInvariant());
6565 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6566 assert(isNonTemporal() == MMO->isNonTemporal() &&
6567 "Non-temporal encoding error!");
6568 // We check here that the size of the memory operand fits within the size of
6569 // the MMO. This is because the MMO might indicate only a possible address
6570 // range instead of specifying the affected memory addresses precisely.
6571 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6574 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6575 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6576 : SDNode(Opc, Order, dl, VTs, Ops),
6577 MemoryVT(memvt), MMO(mmo) {
6578 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6579 MMO->isNonTemporal(), MMO->isInvariant());
6580 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6581 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6584 /// Profile - Gather unique data for the node.
6586 void SDNode::Profile(FoldingSetNodeID &ID) const {
6587 AddNodeIDNode(ID, this);
6592 std::vector<EVT> VTs;
6595 VTs.reserve(MVT::LAST_VALUETYPE);
6596 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6597 VTs.push_back(MVT((MVT::SimpleValueType)i));
6602 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6603 static ManagedStatic<EVTArray> SimpleVTArray;
6604 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6606 /// getValueTypeList - Return a pointer to the specified value type.
6608 const EVT *SDNode::getValueTypeList(EVT VT) {
6609 if (VT.isExtended()) {
6610 sys::SmartScopedLock<true> Lock(*VTMutex);
6611 return &(*EVTs->insert(VT).first);
6613 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6614 "Value type out of range!");
6615 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6619 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6620 /// indicated value. This method ignores uses of other values defined by this
6622 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6623 assert(Value < getNumValues() && "Bad value!");
6625 // TODO: Only iterate over uses of a given value of the node
6626 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6627 if (UI.getUse().getResNo() == Value) {
6634 // Found exactly the right number of uses?
6639 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6640 /// value. This method ignores uses of other values defined by this operation.
6641 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6642 assert(Value < getNumValues() && "Bad value!");
6644 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6645 if (UI.getUse().getResNo() == Value)
6652 /// isOnlyUserOf - Return true if this node is the only use of N.
6654 bool SDNode::isOnlyUserOf(SDNode *N) const {
6656 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6667 /// isOperand - Return true if this node is an operand of N.
6669 bool SDValue::isOperandOf(SDNode *N) const {
6670 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6671 if (*this == N->getOperand(i))
6676 bool SDNode::isOperandOf(SDNode *N) const {
6677 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6678 if (this == N->OperandList[i].getNode())
6683 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6684 /// be a chain) reaches the specified operand without crossing any
6685 /// side-effecting instructions on any chain path. In practice, this looks
6686 /// through token factors and non-volatile loads. In order to remain efficient,
6687 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6688 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6689 unsigned Depth) const {
6690 if (*this == Dest) return true;
6692 // Don't search too deeply, we just want to be able to see through
6693 // TokenFactor's etc.
6694 if (Depth == 0) return false;
6696 // If this is a token factor, all inputs to the TF happen in parallel. If any
6697 // of the operands of the TF does not reach dest, then we cannot do the xform.
6698 if (getOpcode() == ISD::TokenFactor) {
6699 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6700 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6705 // Loads don't have side effects, look through them.
6706 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6707 if (!Ld->isVolatile())
6708 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6713 /// hasPredecessor - Return true if N is a predecessor of this node.
6714 /// N is either an operand of this node, or can be reached by recursively
6715 /// traversing up the operands.
6716 /// NOTE: This is an expensive method. Use it carefully.
6717 bool SDNode::hasPredecessor(const SDNode *N) const {
6718 SmallPtrSet<const SDNode *, 32> Visited;
6719 SmallVector<const SDNode *, 16> Worklist;
6720 return hasPredecessorHelper(N, Visited, Worklist);
6724 SDNode::hasPredecessorHelper(const SDNode *N,
6725 SmallPtrSetImpl<const SDNode *> &Visited,
6726 SmallVectorImpl<const SDNode *> &Worklist) const {
6727 if (Visited.empty()) {
6728 Worklist.push_back(this);
6730 // Take a look in the visited set. If we've already encountered this node
6731 // we needn't search further.
6732 if (Visited.count(N))
6736 // Haven't visited N yet. Continue the search.
6737 while (!Worklist.empty()) {
6738 const SDNode *M = Worklist.pop_back_val();
6739 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6740 SDNode *Op = M->getOperand(i).getNode();
6741 if (Visited.insert(Op).second)
6742 Worklist.push_back(Op);
6751 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6752 assert(Num < NumOperands && "Invalid child # of SDNode!");
6753 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6756 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6757 assert(N->getNumValues() == 1 &&
6758 "Can't unroll a vector with multiple results!");
6760 EVT VT = N->getValueType(0);
6761 unsigned NE = VT.getVectorNumElements();
6762 EVT EltVT = VT.getVectorElementType();
6765 SmallVector<SDValue, 8> Scalars;
6766 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6768 // If ResNE is 0, fully unroll the vector op.
6771 else if (NE > ResNE)
6775 for (i= 0; i != NE; ++i) {
6776 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6777 SDValue Operand = N->getOperand(j);
6778 EVT OperandVT = Operand.getValueType();
6779 if (OperandVT.isVector()) {
6780 // A vector operand; extract a single element.
6781 EVT OperandEltVT = OperandVT.getVectorElementType();
6782 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6785 getConstant(i, dl, TLI->getVectorIdxTy()));
6787 // A scalar operand; just use it as is.
6788 Operands[j] = Operand;
6792 switch (N->getOpcode()) {
6794 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6797 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6804 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6805 getShiftAmountOperand(Operands[0].getValueType(),
6808 case ISD::SIGN_EXTEND_INREG:
6809 case ISD::FP_ROUND_INREG: {
6810 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6811 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6813 getValueType(ExtVT)));
6818 for (; i < ResNE; ++i)
6819 Scalars.push_back(getUNDEF(EltVT));
6821 return getNode(ISD::BUILD_VECTOR, dl,
6822 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6826 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6827 /// location that is 'Dist' units away from the location that the 'Base' load
6828 /// is loading from.
6829 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6830 unsigned Bytes, int Dist) const {
6831 if (LD->getChain() != Base->getChain())
6833 EVT VT = LD->getValueType(0);
6834 if (VT.getSizeInBits() / 8 != Bytes)
6837 SDValue Loc = LD->getOperand(1);
6838 SDValue BaseLoc = Base->getOperand(1);
6839 if (Loc.getOpcode() == ISD::FrameIndex) {
6840 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6842 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6843 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6844 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6845 int FS = MFI->getObjectSize(FI);
6846 int BFS = MFI->getObjectSize(BFI);
6847 if (FS != BFS || FS != (int)Bytes) return false;
6848 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6852 if (isBaseWithConstantOffset(Loc)) {
6853 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6854 if (Loc.getOperand(0) == BaseLoc) {
6855 // If the base location is a simple address with no offset itself, then
6856 // the second load's first add operand should be the base address.
6857 if (LocOffset == Dist * (int)Bytes)
6859 } else if (isBaseWithConstantOffset(BaseLoc)) {
6860 // The base location itself has an offset, so subtract that value from the
6861 // second load's offset before comparing to distance * size.
6863 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6864 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6865 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6870 const GlobalValue *GV1 = nullptr;
6871 const GlobalValue *GV2 = nullptr;
6872 int64_t Offset1 = 0;
6873 int64_t Offset2 = 0;
6874 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6875 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6876 if (isGA1 && isGA2 && GV1 == GV2)
6877 return Offset1 == (Offset2 + Dist*Bytes);
6882 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6883 /// it cannot be inferred.
6884 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6885 // If this is a GlobalAddress + cst, return the alignment.
6886 const GlobalValue *GV;
6887 int64_t GVOffset = 0;
6888 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6889 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6890 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6891 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6892 *TLI->getDataLayout());
6893 unsigned AlignBits = KnownZero.countTrailingOnes();
6894 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6896 return MinAlign(Align, GVOffset);
6899 // If this is a direct reference to a stack slot, use information about the
6900 // stack slot's alignment.
6901 int FrameIdx = 1 << 31;
6902 int64_t FrameOffset = 0;
6903 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6904 FrameIdx = FI->getIndex();
6905 } else if (isBaseWithConstantOffset(Ptr) &&
6906 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6908 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6909 FrameOffset = Ptr.getConstantOperandVal(1);
6912 if (FrameIdx != (1 << 31)) {
6913 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6914 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6922 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6923 /// which is split (or expanded) into two not necessarily identical pieces.
6924 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6925 // Currently all types are split in half.
6927 if (!VT.isVector()) {
6928 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6930 unsigned NumElements = VT.getVectorNumElements();
6931 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6932 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6935 return std::make_pair(LoVT, HiVT);
6938 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6940 std::pair<SDValue, SDValue>
6941 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6943 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6944 N.getValueType().getVectorNumElements() &&
6945 "More vector elements requested than available!");
6947 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6948 getConstant(0, DL, TLI->getVectorIdxTy()));
6949 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6950 getConstant(LoVT.getVectorNumElements(), DL,
6951 TLI->getVectorIdxTy()));
6952 return std::make_pair(Lo, Hi);
6955 void SelectionDAG::ExtractVectorElements(SDValue Op,
6956 SmallVectorImpl<SDValue> &Args,
6957 unsigned Start, unsigned Count) {
6958 EVT VT = Op.getValueType();
6960 Count = VT.getVectorNumElements();
6962 EVT EltVT = VT.getVectorElementType();
6963 EVT IdxTy = TLI->getVectorIdxTy();
6965 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6966 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6967 Op, getConstant(i, SL, IdxTy)));
6971 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6972 unsigned GlobalAddressSDNode::getAddressSpace() const {
6973 return getGlobal()->getType()->getAddressSpace();
6977 Type *ConstantPoolSDNode::getType() const {
6978 if (isMachineConstantPoolEntry())
6979 return Val.MachineCPVal->getType();
6980 return Val.ConstVal->getType();
6983 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6985 unsigned &SplatBitSize,
6987 unsigned MinSplatBits,
6988 bool isBigEndian) const {
6989 EVT VT = getValueType(0);
6990 assert(VT.isVector() && "Expected a vector type");
6991 unsigned sz = VT.getSizeInBits();
6992 if (MinSplatBits > sz)
6995 SplatValue = APInt(sz, 0);
6996 SplatUndef = APInt(sz, 0);
6998 // Get the bits. Bits with undefined values (when the corresponding element
6999 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7000 // in SplatValue. If any of the values are not constant, give up and return
7002 unsigned int nOps = getNumOperands();
7003 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7004 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7006 for (unsigned j = 0; j < nOps; ++j) {
7007 unsigned i = isBigEndian ? nOps-1-j : j;
7008 SDValue OpVal = getOperand(i);
7009 unsigned BitPos = j * EltBitSize;
7011 if (OpVal.getOpcode() == ISD::UNDEF)
7012 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7013 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7014 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7015 zextOrTrunc(sz) << BitPos;
7016 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7017 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7022 // The build_vector is all constants or undefs. Find the smallest element
7023 // size that splats the vector.
7025 HasAnyUndefs = (SplatUndef != 0);
7028 unsigned HalfSize = sz / 2;
7029 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7030 APInt LowValue = SplatValue.trunc(HalfSize);
7031 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7032 APInt LowUndef = SplatUndef.trunc(HalfSize);
7034 // If the two halves do not match (ignoring undef bits), stop here.
7035 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7036 MinSplatBits > HalfSize)
7039 SplatValue = HighValue | LowValue;
7040 SplatUndef = HighUndef & LowUndef;
7049 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7050 if (UndefElements) {
7051 UndefElements->clear();
7052 UndefElements->resize(getNumOperands());
7055 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7056 SDValue Op = getOperand(i);
7057 if (Op.getOpcode() == ISD::UNDEF) {
7059 (*UndefElements)[i] = true;
7060 } else if (!Splatted) {
7062 } else if (Splatted != Op) {
7068 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7069 "Can only have a splat without a constant for all undefs.");
7070 return getOperand(0);
7077 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7078 return dyn_cast_or_null<ConstantSDNode>(
7079 getSplatValue(UndefElements).getNode());
7083 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7084 return dyn_cast_or_null<ConstantFPSDNode>(
7085 getSplatValue(UndefElements).getNode());
7088 bool BuildVectorSDNode::isConstant() const {
7089 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7090 unsigned Opc = getOperand(i).getOpcode();
7091 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7097 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7098 // Find the first non-undef value in the shuffle mask.
7100 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7103 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7105 // Make sure all remaining elements are either undef or the same as the first
7107 for (int Idx = Mask[i]; i != e; ++i)
7108 if (Mask[i] >= 0 && Mask[i] != Idx)
7114 static void checkForCyclesHelper(const SDNode *N,
7115 SmallPtrSetImpl<const SDNode*> &Visited,
7116 SmallPtrSetImpl<const SDNode*> &Checked,
7117 const llvm::SelectionDAG *DAG) {
7118 // If this node has already been checked, don't check it again.
7119 if (Checked.count(N))
7122 // If a node has already been visited on this depth-first walk, reject it as
7124 if (!Visited.insert(N).second) {
7125 errs() << "Detected cycle in SelectionDAG\n";
7126 dbgs() << "Offending node:\n";
7127 N->dumprFull(DAG); dbgs() << "\n";
7131 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7132 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7139 void llvm::checkForCycles(const llvm::SDNode *N,
7140 const llvm::SelectionDAG *DAG,
7148 assert(N && "Checking nonexistent SDNode");
7149 SmallPtrSet<const SDNode*, 32> visited;
7150 SmallPtrSet<const SDNode*, 32> checked;
7151 checkForCyclesHelper(N, visited, checked, DAG);
7156 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7157 checkForCycles(DAG->getRoot().getNode(), DAG, force);