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 (const SDValue &Op : N->op_values()) {
155 if (Op.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 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (const SDValue &Op : N->op_values()) {
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// \brief Return true if the specified node is a BUILD_VECTOR node of
199 /// all ConstantFPSDNode or undef.
200 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
201 if (N->getOpcode() != ISD::BUILD_VECTOR)
204 for (const SDValue &Op : N->op_values()) {
205 if (Op.getOpcode() == ISD::UNDEF)
207 if (!isa<ConstantFPSDNode>(Op))
213 /// isScalarToVector - Return true if the specified node is a
214 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
215 /// element is not an undef.
216 bool ISD::isScalarToVector(const SDNode *N) {
217 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
220 if (N->getOpcode() != ISD::BUILD_VECTOR)
222 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
224 unsigned NumElems = N->getNumOperands();
227 for (unsigned i = 1; i < NumElems; ++i) {
228 SDValue V = N->getOperand(i);
229 if (V.getOpcode() != ISD::UNDEF)
235 /// allOperandsUndef - Return true if the node has at least one operand
236 /// and all operands of the specified node are ISD::UNDEF.
237 bool ISD::allOperandsUndef(const SDNode *N) {
238 // Return false if the node has no operands.
239 // This is "logically inconsistent" with the definition of "all" but
240 // is probably the desired behavior.
241 if (N->getNumOperands() == 0)
244 for (const SDValue &Op : N->op_values())
245 if (Op.getOpcode() != ISD::UNDEF)
251 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
254 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
256 return ISD::SIGN_EXTEND;
258 return ISD::ZERO_EXTEND;
263 llvm_unreachable("Invalid LoadExtType");
266 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
267 /// when given the operation for (X op Y).
268 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
269 // To perform this operation, we just need to swap the L and G bits of the
271 unsigned OldL = (Operation >> 2) & 1;
272 unsigned OldG = (Operation >> 1) & 1;
273 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
274 (OldL << 1) | // New G bit
275 (OldG << 2)); // New L bit.
278 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
279 /// 'op' is a valid SetCC operation.
280 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
281 unsigned Operation = Op;
283 Operation ^= 7; // Flip L, G, E bits, but not U.
285 Operation ^= 15; // Flip all of the condition bits.
287 if (Operation > ISD::SETTRUE2)
288 Operation &= ~8; // Don't let N and U bits get set.
290 return ISD::CondCode(Operation);
294 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
295 /// signed operation and 2 if the result is an unsigned comparison. Return zero
296 /// if the operation does not depend on the sign of the input (setne and seteq).
297 static int isSignedOp(ISD::CondCode Opcode) {
299 default: llvm_unreachable("Illegal integer setcc operation!");
301 case ISD::SETNE: return 0;
305 case ISD::SETGE: return 1;
309 case ISD::SETUGE: return 2;
313 /// getSetCCOrOperation - Return the result of a logical OR between different
314 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
315 /// returns SETCC_INVALID if it is not possible to represent the resultant
317 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
319 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
320 // Cannot fold a signed integer setcc with an unsigned integer setcc.
321 return ISD::SETCC_INVALID;
323 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
325 // If the N and U bits get set then the resultant comparison DOES suddenly
326 // care about orderedness, and is true when ordered.
327 if (Op > ISD::SETTRUE2)
328 Op &= ~16; // Clear the U bit if the N bit is set.
330 // Canonicalize illegal integer setcc's.
331 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
334 return ISD::CondCode(Op);
337 /// getSetCCAndOperation - Return the result of a logical AND between different
338 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
339 /// function returns zero if it is not possible to represent the resultant
341 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
343 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
344 // Cannot fold a signed setcc with an unsigned setcc.
345 return ISD::SETCC_INVALID;
347 // Combine all of the condition bits.
348 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
350 // Canonicalize illegal integer setcc's.
354 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
355 case ISD::SETOEQ: // SETEQ & SETU[LG]E
356 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
357 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
358 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
365 //===----------------------------------------------------------------------===//
366 // SDNode Profile Support
367 //===----------------------------------------------------------------------===//
369 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
371 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
375 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
376 /// solely with their pointer.
377 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
378 ID.AddPointer(VTList.VTs);
381 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
383 static void AddNodeIDOperands(FoldingSetNodeID &ID,
384 ArrayRef<SDValue> Ops) {
385 for (auto& Op : Ops) {
386 ID.AddPointer(Op.getNode());
387 ID.AddInteger(Op.getResNo());
391 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
393 static void AddNodeIDOperands(FoldingSetNodeID &ID,
394 ArrayRef<SDUse> Ops) {
395 for (auto& Op : Ops) {
396 ID.AddPointer(Op.getNode());
397 ID.AddInteger(Op.getResNo());
400 /// Add logical or fast math flag values to FoldingSetNodeID value.
401 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
402 const SDNodeFlags *Flags) {
403 if (!Flags || !isBinOpWithFlags(Opcode))
406 unsigned RawFlags = Flags->getRawFlags();
407 // If no flags are set, do not alter the ID. We must match the ID of nodes
408 // that were created without explicitly specifying flags. This also saves time
409 // and allows a gradual increase in API usage of the optional optimization
412 ID.AddInteger(RawFlags);
415 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
416 if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
417 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
420 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
421 SDVTList VTList, ArrayRef<SDValue> OpList) {
422 AddNodeIDOpcode(ID, OpC);
423 AddNodeIDValueTypes(ID, VTList);
424 AddNodeIDOperands(ID, OpList);
427 /// If this is an SDNode with special info, add this info to the NodeID data.
428 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
429 switch (N->getOpcode()) {
430 case ISD::TargetExternalSymbol:
431 case ISD::ExternalSymbol:
433 llvm_unreachable("Should only be used on nodes with operands");
434 default: break; // Normal nodes don't need extra info.
435 case ISD::TargetConstant:
436 case ISD::Constant: {
437 const ConstantSDNode *C = cast<ConstantSDNode>(N);
438 ID.AddPointer(C->getConstantIntValue());
439 ID.AddBoolean(C->isOpaque());
442 case ISD::TargetConstantFP:
443 case ISD::ConstantFP: {
444 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
447 case ISD::TargetGlobalAddress:
448 case ISD::GlobalAddress:
449 case ISD::TargetGlobalTLSAddress:
450 case ISD::GlobalTLSAddress: {
451 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
452 ID.AddPointer(GA->getGlobal());
453 ID.AddInteger(GA->getOffset());
454 ID.AddInteger(GA->getTargetFlags());
455 ID.AddInteger(GA->getAddressSpace());
458 case ISD::BasicBlock:
459 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
462 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
464 case ISD::RegisterMask:
465 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
468 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
470 case ISD::FrameIndex:
471 case ISD::TargetFrameIndex:
472 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
475 case ISD::TargetJumpTable:
476 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
477 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
479 case ISD::ConstantPool:
480 case ISD::TargetConstantPool: {
481 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
482 ID.AddInteger(CP->getAlignment());
483 ID.AddInteger(CP->getOffset());
484 if (CP->isMachineConstantPoolEntry())
485 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
487 ID.AddPointer(CP->getConstVal());
488 ID.AddInteger(CP->getTargetFlags());
491 case ISD::TargetIndex: {
492 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
493 ID.AddInteger(TI->getIndex());
494 ID.AddInteger(TI->getOffset());
495 ID.AddInteger(TI->getTargetFlags());
499 const LoadSDNode *LD = cast<LoadSDNode>(N);
500 ID.AddInteger(LD->getMemoryVT().getRawBits());
501 ID.AddInteger(LD->getRawSubclassData());
502 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
506 const StoreSDNode *ST = cast<StoreSDNode>(N);
507 ID.AddInteger(ST->getMemoryVT().getRawBits());
508 ID.AddInteger(ST->getRawSubclassData());
509 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
512 case ISD::ATOMIC_CMP_SWAP:
513 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
514 case ISD::ATOMIC_SWAP:
515 case ISD::ATOMIC_LOAD_ADD:
516 case ISD::ATOMIC_LOAD_SUB:
517 case ISD::ATOMIC_LOAD_AND:
518 case ISD::ATOMIC_LOAD_OR:
519 case ISD::ATOMIC_LOAD_XOR:
520 case ISD::ATOMIC_LOAD_NAND:
521 case ISD::ATOMIC_LOAD_MIN:
522 case ISD::ATOMIC_LOAD_MAX:
523 case ISD::ATOMIC_LOAD_UMIN:
524 case ISD::ATOMIC_LOAD_UMAX:
525 case ISD::ATOMIC_LOAD:
526 case ISD::ATOMIC_STORE: {
527 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
528 ID.AddInteger(AT->getMemoryVT().getRawBits());
529 ID.AddInteger(AT->getRawSubclassData());
530 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
533 case ISD::PREFETCH: {
534 const MemSDNode *PF = cast<MemSDNode>(N);
535 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
538 case ISD::VECTOR_SHUFFLE: {
539 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
540 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
542 ID.AddInteger(SVN->getMaskElt(i));
545 case ISD::TargetBlockAddress:
546 case ISD::BlockAddress: {
547 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
548 ID.AddPointer(BA->getBlockAddress());
549 ID.AddInteger(BA->getOffset());
550 ID.AddInteger(BA->getTargetFlags());
553 } // end switch (N->getOpcode())
555 AddNodeIDFlags(ID, N);
557 // Target specific memory nodes could also have address spaces to check.
558 if (N->isTargetMemoryOpcode())
559 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
562 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
564 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
565 AddNodeIDOpcode(ID, N->getOpcode());
566 // Add the return value info.
567 AddNodeIDValueTypes(ID, N->getVTList());
568 // Add the operand info.
569 AddNodeIDOperands(ID, N->ops());
571 // Handle SDNode leafs with special info.
572 AddNodeIDCustom(ID, N);
575 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
576 /// the CSE map that carries volatility, temporalness, indexing mode, and
577 /// extension/truncation information.
579 static inline unsigned
580 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
581 bool isNonTemporal, bool isInvariant) {
582 assert((ConvType & 3) == ConvType &&
583 "ConvType may not require more than 2 bits!");
584 assert((AM & 7) == AM &&
585 "AM may not require more than 3 bits!");
589 (isNonTemporal << 6) |
593 //===----------------------------------------------------------------------===//
594 // SelectionDAG Class
595 //===----------------------------------------------------------------------===//
597 /// doNotCSE - Return true if CSE should not be performed for this node.
598 static bool doNotCSE(SDNode *N) {
599 if (N->getValueType(0) == MVT::Glue)
600 return true; // Never CSE anything that produces a flag.
602 switch (N->getOpcode()) {
604 case ISD::HANDLENODE:
606 return true; // Never CSE these nodes.
609 // Check that remaining values produced are not flags.
610 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
611 if (N->getValueType(i) == MVT::Glue)
612 return true; // Never CSE anything that produces a flag.
617 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
619 void SelectionDAG::RemoveDeadNodes() {
620 // Create a dummy node (which is not added to allnodes), that adds a reference
621 // to the root node, preventing it from being deleted.
622 HandleSDNode Dummy(getRoot());
624 SmallVector<SDNode*, 128> DeadNodes;
626 // Add all obviously-dead nodes to the DeadNodes worklist.
627 for (SDNode &Node : allnodes())
628 if (Node.use_empty())
629 DeadNodes.push_back(&Node);
631 RemoveDeadNodes(DeadNodes);
633 // If the root changed (e.g. it was a dead load, update the root).
634 setRoot(Dummy.getValue());
637 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
638 /// given list, and any nodes that become unreachable as a result.
639 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
641 // Process the worklist, deleting the nodes and adding their uses to the
643 while (!DeadNodes.empty()) {
644 SDNode *N = DeadNodes.pop_back_val();
646 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
647 DUL->NodeDeleted(N, nullptr);
649 // Take the node out of the appropriate CSE map.
650 RemoveNodeFromCSEMaps(N);
652 // Next, brutally remove the operand list. This is safe to do, as there are
653 // no cycles in the graph.
654 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
656 SDNode *Operand = Use.getNode();
659 // Now that we removed this operand, see if there are no uses of it left.
660 if (Operand->use_empty())
661 DeadNodes.push_back(Operand);
668 void SelectionDAG::RemoveDeadNode(SDNode *N){
669 SmallVector<SDNode*, 16> DeadNodes(1, N);
671 // Create a dummy node that adds a reference to the root node, preventing
672 // it from being deleted. (This matters if the root is an operand of the
674 HandleSDNode Dummy(getRoot());
676 RemoveDeadNodes(DeadNodes);
679 void SelectionDAG::DeleteNode(SDNode *N) {
680 // First take this out of the appropriate CSE map.
681 RemoveNodeFromCSEMaps(N);
683 // Finally, remove uses due to operands of this node, remove from the
684 // AllNodes list, and delete the node.
685 DeleteNodeNotInCSEMaps(N);
688 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
689 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
690 assert(N->use_empty() && "Cannot delete a node that is not dead!");
692 // Drop all of the operands and decrement used node's use counts.
698 void SDDbgInfo::erase(const SDNode *Node) {
699 DbgValMapType::iterator I = DbgValMap.find(Node);
700 if (I == DbgValMap.end())
702 for (auto &Val: I->second)
703 Val->setIsInvalidated();
707 void SelectionDAG::DeallocateNode(SDNode *N) {
708 if (N->OperandsNeedDelete)
709 delete[] N->OperandList;
711 // Set the opcode to DELETED_NODE to help catch bugs when node
712 // memory is reallocated.
713 N->NodeType = ISD::DELETED_NODE;
715 NodeAllocator.Deallocate(AllNodes.remove(N));
717 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
718 // them and forget about that node.
723 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
724 static void VerifySDNode(SDNode *N) {
725 switch (N->getOpcode()) {
728 case ISD::BUILD_PAIR: {
729 EVT VT = N->getValueType(0);
730 assert(N->getNumValues() == 1 && "Too many results!");
731 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
732 "Wrong return type!");
733 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
734 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
735 "Mismatched operand types!");
736 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
737 "Wrong operand type!");
738 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
739 "Wrong return type size");
742 case ISD::BUILD_VECTOR: {
743 assert(N->getNumValues() == 1 && "Too many results!");
744 assert(N->getValueType(0).isVector() && "Wrong return type!");
745 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
746 "Wrong number of operands!");
747 EVT EltVT = N->getValueType(0).getVectorElementType();
748 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
749 assert((I->getValueType() == EltVT ||
750 (EltVT.isInteger() && I->getValueType().isInteger() &&
751 EltVT.bitsLE(I->getValueType()))) &&
752 "Wrong operand type!");
753 assert(I->getValueType() == N->getOperand(0).getValueType() &&
754 "Operands must all have the same type");
762 /// \brief Insert a newly allocated node into the DAG.
764 /// Handles insertion into the all nodes list and CSE map, as well as
765 /// verification and other common operations when a new node is allocated.
766 void SelectionDAG::InsertNode(SDNode *N) {
767 AllNodes.push_back(N);
773 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
774 /// correspond to it. This is useful when we're about to delete or repurpose
775 /// the node. We don't want future request for structurally identical nodes
776 /// to return N anymore.
777 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
779 switch (N->getOpcode()) {
780 case ISD::HANDLENODE: return false; // noop.
782 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
783 "Cond code doesn't exist!");
784 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
785 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
787 case ISD::ExternalSymbol:
788 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
790 case ISD::TargetExternalSymbol: {
791 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
792 Erased = TargetExternalSymbols.erase(
793 std::pair<std::string,unsigned char>(ESN->getSymbol(),
794 ESN->getTargetFlags()));
797 case ISD::MCSymbol: {
798 auto *MCSN = cast<MCSymbolSDNode>(N);
799 Erased = MCSymbols.erase(MCSN->getMCSymbol());
802 case ISD::VALUETYPE: {
803 EVT VT = cast<VTSDNode>(N)->getVT();
804 if (VT.isExtended()) {
805 Erased = ExtendedValueTypeNodes.erase(VT);
807 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
808 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
813 // Remove it from the CSE Map.
814 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
815 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
816 Erased = CSEMap.RemoveNode(N);
820 // Verify that the node was actually in one of the CSE maps, unless it has a
821 // flag result (which cannot be CSE'd) or is one of the special cases that are
822 // not subject to CSE.
823 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
824 !N->isMachineOpcode() && !doNotCSE(N)) {
827 llvm_unreachable("Node is not in map!");
833 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
834 /// maps and modified in place. Add it back to the CSE maps, unless an identical
835 /// node already exists, in which case transfer all its users to the existing
836 /// node. This transfer can potentially trigger recursive merging.
839 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
840 // For node types that aren't CSE'd, just act as if no identical node
843 SDNode *Existing = CSEMap.GetOrInsertNode(N);
845 // If there was already an existing matching node, use ReplaceAllUsesWith
846 // to replace the dead one with the existing one. This can cause
847 // recursive merging of other unrelated nodes down the line.
848 ReplaceAllUsesWith(N, Existing);
850 // N is now dead. Inform the listeners and delete it.
851 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
852 DUL->NodeDeleted(N, Existing);
853 DeleteNodeNotInCSEMaps(N);
858 // If the node doesn't already exist, we updated it. Inform listeners.
859 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
863 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
864 /// were replaced with those specified. If this node is never memoized,
865 /// return null, otherwise return a pointer to the slot it would take. If a
866 /// node already exists with these operands, the slot will be non-null.
867 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
872 SDValue Ops[] = { Op };
874 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
875 AddNodeIDCustom(ID, N);
876 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
880 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
881 /// were replaced with those specified. If this node is never memoized,
882 /// return null, otherwise return a pointer to the slot it would take. If a
883 /// node already exists with these operands, the slot will be non-null.
884 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
885 SDValue Op1, SDValue Op2,
890 SDValue Ops[] = { Op1, Op2 };
892 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
893 AddNodeIDCustom(ID, N);
894 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
899 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
900 /// were replaced with those specified. If this node is never memoized,
901 /// return null, otherwise return a pointer to the slot it would take. If a
902 /// node already exists with these operands, the slot will be non-null.
903 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
909 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
910 AddNodeIDCustom(ID, N);
911 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
915 /// getEVTAlignment - Compute the default alignment value for the
918 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
919 Type *Ty = VT == MVT::iPTR ?
920 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
921 VT.getTypeForEVT(*getContext());
923 return getDataLayout().getABITypeAlignment(Ty);
926 // EntryNode could meaningfully have debug info if we can find it...
927 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
928 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
929 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
930 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
931 UpdateListeners(nullptr) {
932 AllNodes.push_back(&EntryNode);
933 DbgInfo = new SDDbgInfo();
936 void SelectionDAG::init(MachineFunction &mf) {
938 TLI = getSubtarget().getTargetLowering();
939 TSI = getSubtarget().getSelectionDAGInfo();
940 Context = &mf.getFunction()->getContext();
943 SelectionDAG::~SelectionDAG() {
944 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
949 void SelectionDAG::allnodes_clear() {
950 assert(&*AllNodes.begin() == &EntryNode);
951 AllNodes.remove(AllNodes.begin());
952 while (!AllNodes.empty())
953 DeallocateNode(AllNodes.begin());
956 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
957 SDVTList VTs, SDValue N1,
959 const SDNodeFlags *Flags) {
960 if (isBinOpWithFlags(Opcode)) {
961 // If no flags were passed in, use a default flags object.
963 if (Flags == nullptr)
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
972 BinarySDNode *N = new (NodeAllocator)
973 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
977 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
979 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
981 switch (N->getOpcode()) {
984 case ISD::ConstantFP:
985 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
986 "debug location. Use another overload.");
992 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
993 DebugLoc DL, void *&InsertPos) {
994 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
996 switch (N->getOpcode()) {
997 default: break; // Process only regular (non-target) constant nodes.
999 case ISD::ConstantFP:
1000 // Erase debug location from the node if the node is used at several
1001 // different places to do not propagate one location to all uses as it
1002 // leads to incorrect debug info.
1003 if (N->getDebugLoc() != DL)
1004 N->setDebugLoc(DebugLoc());
1011 void SelectionDAG::clear() {
1013 OperandAllocator.Reset();
1016 ExtendedValueTypeNodes.clear();
1017 ExternalSymbols.clear();
1018 TargetExternalSymbols.clear();
1020 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1021 static_cast<CondCodeSDNode*>(nullptr));
1022 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1023 static_cast<SDNode*>(nullptr));
1025 EntryNode.UseList = nullptr;
1026 AllNodes.push_back(&EntryNode);
1027 Root = getEntryNode();
1031 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1032 return VT.bitsGT(Op.getValueType()) ?
1033 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1034 getNode(ISD::TRUNCATE, DL, VT, Op);
1037 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1038 return VT.bitsGT(Op.getValueType()) ?
1039 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1040 getNode(ISD::TRUNCATE, DL, VT, Op);
1043 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1044 return VT.bitsGT(Op.getValueType()) ?
1045 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1046 getNode(ISD::TRUNCATE, DL, VT, Op);
1049 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1051 if (VT.bitsLE(Op.getValueType()))
1052 return getNode(ISD::TRUNCATE, SL, VT, Op);
1054 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1055 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1058 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1059 assert(!VT.isVector() &&
1060 "getZeroExtendInReg should use the vector element type instead of "
1061 "the vector type!");
1062 if (Op.getValueType() == VT) return Op;
1063 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1064 APInt Imm = APInt::getLowBitsSet(BitWidth,
1065 VT.getSizeInBits());
1066 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1067 getConstant(Imm, DL, Op.getValueType()));
1070 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1071 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1072 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1073 "The sizes of the input and result must match in order to perform the "
1074 "extend in-register.");
1075 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1076 "The destination vector type must have fewer lanes than the input.");
1077 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1080 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1081 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1082 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1083 "The sizes of the input and result must match in order to perform the "
1084 "extend in-register.");
1085 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1086 "The destination vector type must have fewer lanes than the input.");
1087 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1090 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1091 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1092 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1093 "The sizes of the input and result must match in order to perform the "
1094 "extend in-register.");
1095 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1096 "The destination vector type must have fewer lanes than the input.");
1097 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1100 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1102 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1103 EVT EltVT = VT.getScalarType();
1105 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1106 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1109 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1110 EVT EltVT = VT.getScalarType();
1112 switch (TLI->getBooleanContents(VT)) {
1113 case TargetLowering::ZeroOrOneBooleanContent:
1114 case TargetLowering::UndefinedBooleanContent:
1115 TrueValue = getConstant(1, DL, VT);
1117 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1118 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1122 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1125 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1127 EVT EltVT = VT.getScalarType();
1128 assert((EltVT.getSizeInBits() >= 64 ||
1129 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1130 "getConstant with a uint64_t value that doesn't fit in the type!");
1131 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1134 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1137 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1140 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1141 bool isT, bool isO) {
1142 assert(VT.isInteger() && "Cannot create FP integer constant!");
1144 EVT EltVT = VT.getScalarType();
1145 const ConstantInt *Elt = &Val;
1147 // In some cases the vector type is legal but the element type is illegal and
1148 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1149 // inserted value (the type does not need to match the vector element type).
1150 // Any extra bits introduced will be truncated away.
1151 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1152 TargetLowering::TypePromoteInteger) {
1153 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1154 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1155 Elt = ConstantInt::get(*getContext(), NewVal);
1157 // In other cases the element type is illegal and needs to be expanded, for
1158 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1159 // the value into n parts and use a vector type with n-times the elements.
1160 // Then bitcast to the type requested.
1161 // Legalizing constants too early makes the DAGCombiner's job harder so we
1162 // only legalize if the DAG tells us we must produce legal types.
1163 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1164 TLI->getTypeAction(*getContext(), EltVT) ==
1165 TargetLowering::TypeExpandInteger) {
1166 APInt NewVal = Elt->getValue();
1167 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1168 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1169 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1170 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1172 // Check the temporary vector is the correct size. If this fails then
1173 // getTypeToTransformTo() probably returned a type whose size (in bits)
1174 // isn't a power-of-2 factor of the requested type size.
1175 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1177 SmallVector<SDValue, 2> EltParts;
1178 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1179 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1180 .trunc(ViaEltSizeInBits), DL,
1181 ViaEltVT, isT, isO));
1184 // EltParts is currently in little endian order. If we actually want
1185 // big-endian order then reverse it now.
1186 if (getDataLayout().isBigEndian())
1187 std::reverse(EltParts.begin(), EltParts.end());
1189 // The elements must be reversed when the element order is different
1190 // to the endianness of the elements (because the BITCAST is itself a
1191 // vector shuffle in this situation). However, we do not need any code to
1192 // perform this reversal because getConstant() is producing a vector
1194 // This situation occurs in MIPS MSA.
1196 SmallVector<SDValue, 8> Ops;
1197 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1198 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1200 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1201 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1206 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1207 "APInt size does not match type size!");
1208 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1209 FoldingSetNodeID ID;
1210 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1214 SDNode *N = nullptr;
1215 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1217 return SDValue(N, 0);
1220 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1222 CSEMap.InsertNode(N, IP);
1226 SDValue Result(N, 0);
1227 if (VT.isVector()) {
1228 SmallVector<SDValue, 8> Ops;
1229 Ops.assign(VT.getVectorNumElements(), Result);
1230 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1235 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1236 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1239 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1241 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1244 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1246 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1248 EVT EltVT = VT.getScalarType();
1250 // Do the map lookup using the actual bit pattern for the floating point
1251 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1252 // we don't have issues with SNANs.
1253 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1254 FoldingSetNodeID ID;
1255 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1258 SDNode *N = nullptr;
1259 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1261 return SDValue(N, 0);
1264 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1266 CSEMap.InsertNode(N, IP);
1270 SDValue Result(N, 0);
1271 if (VT.isVector()) {
1272 SmallVector<SDValue, 8> Ops;
1273 Ops.assign(VT.getVectorNumElements(), Result);
1274 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1279 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1281 EVT EltVT = VT.getScalarType();
1282 if (EltVT==MVT::f32)
1283 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1284 else if (EltVT==MVT::f64)
1285 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1289 APFloat apf = APFloat(Val);
1290 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1292 return getConstantFP(apf, DL, VT, isTarget);
1294 llvm_unreachable("Unsupported type in getConstantFP");
1297 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1298 EVT VT, int64_t Offset,
1300 unsigned char TargetFlags) {
1301 assert((TargetFlags == 0 || isTargetGA) &&
1302 "Cannot set target flags on target-independent globals");
1304 // Truncate (with sign-extension) the offset value to the pointer size.
1305 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1307 Offset = SignExtend64(Offset, BitWidth);
1310 if (GV->isThreadLocal())
1311 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1313 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1315 FoldingSetNodeID ID;
1316 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1318 ID.AddInteger(Offset);
1319 ID.AddInteger(TargetFlags);
1320 ID.AddInteger(GV->getType()->getAddressSpace());
1322 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1326 DL.getDebugLoc(), GV, VT,
1327 Offset, TargetFlags);
1328 CSEMap.InsertNode(N, IP);
1330 return SDValue(N, 0);
1333 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1334 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1335 FoldingSetNodeID ID;
1336 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1339 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1340 return SDValue(E, 0);
1342 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1343 CSEMap.InsertNode(N, IP);
1345 return SDValue(N, 0);
1348 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1349 unsigned char TargetFlags) {
1350 assert((TargetFlags == 0 || isTarget) &&
1351 "Cannot set target flags on target-independent jump tables");
1352 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1353 FoldingSetNodeID ID;
1354 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1356 ID.AddInteger(TargetFlags);
1358 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1359 return SDValue(E, 0);
1361 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1363 CSEMap.InsertNode(N, IP);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1369 unsigned Alignment, int Offset,
1371 unsigned char TargetFlags) {
1372 assert((TargetFlags == 0 || isTarget) &&
1373 "Cannot set target flags on target-independent globals");
1375 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1376 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1377 FoldingSetNodeID ID;
1378 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1379 ID.AddInteger(Alignment);
1380 ID.AddInteger(Offset);
1382 ID.AddInteger(TargetFlags);
1384 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1385 return SDValue(E, 0);
1387 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1388 Alignment, TargetFlags);
1389 CSEMap.InsertNode(N, IP);
1391 return SDValue(N, 0);
1395 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1396 unsigned Alignment, int Offset,
1398 unsigned char TargetFlags) {
1399 assert((TargetFlags == 0 || isTarget) &&
1400 "Cannot set target flags on target-independent globals");
1402 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1403 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1404 FoldingSetNodeID ID;
1405 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1406 ID.AddInteger(Alignment);
1407 ID.AddInteger(Offset);
1408 C->addSelectionDAGCSEId(ID);
1409 ID.AddInteger(TargetFlags);
1411 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1412 return SDValue(E, 0);
1414 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1415 Alignment, TargetFlags);
1416 CSEMap.InsertNode(N, IP);
1418 return SDValue(N, 0);
1421 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1422 unsigned char TargetFlags) {
1423 FoldingSetNodeID ID;
1424 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1425 ID.AddInteger(Index);
1426 ID.AddInteger(Offset);
1427 ID.AddInteger(TargetFlags);
1429 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1430 return SDValue(E, 0);
1432 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1434 CSEMap.InsertNode(N, IP);
1436 return SDValue(N, 0);
1439 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1440 FoldingSetNodeID ID;
1441 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1444 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1445 return SDValue(E, 0);
1447 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1448 CSEMap.InsertNode(N, IP);
1450 return SDValue(N, 0);
1453 SDValue SelectionDAG::getValueType(EVT VT) {
1454 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1455 ValueTypeNodes.size())
1456 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1458 SDNode *&N = VT.isExtended() ?
1459 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1461 if (N) return SDValue(N, 0);
1462 N = new (NodeAllocator) VTSDNode(VT);
1464 return SDValue(N, 0);
1467 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1468 SDNode *&N = ExternalSymbols[Sym];
1469 if (N) return SDValue(N, 0);
1470 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1472 return SDValue(N, 0);
1475 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1476 SDNode *&N = MCSymbols[Sym];
1478 return SDValue(N, 0);
1479 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1481 return SDValue(N, 0);
1484 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1485 unsigned char TargetFlags) {
1487 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1489 if (N) return SDValue(N, 0);
1490 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1492 return SDValue(N, 0);
1495 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1496 if ((unsigned)Cond >= CondCodeNodes.size())
1497 CondCodeNodes.resize(Cond+1);
1499 if (!CondCodeNodes[Cond]) {
1500 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1501 CondCodeNodes[Cond] = N;
1505 return SDValue(CondCodeNodes[Cond], 0);
1508 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1509 // the shuffle mask M that point at N1 to point at N2, and indices that point
1510 // N2 to point at N1.
1511 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1513 ShuffleVectorSDNode::commuteMask(M);
1516 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1517 SDValue N2, const int *Mask) {
1518 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1519 "Invalid VECTOR_SHUFFLE");
1521 // Canonicalize shuffle undef, undef -> undef
1522 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1523 return getUNDEF(VT);
1525 // Validate that all indices in Mask are within the range of the elements
1526 // input to the shuffle.
1527 unsigned NElts = VT.getVectorNumElements();
1528 SmallVector<int, 8> MaskVec;
1529 for (unsigned i = 0; i != NElts; ++i) {
1530 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1531 MaskVec.push_back(Mask[i]);
1534 // Canonicalize shuffle v, v -> v, undef
1537 for (unsigned i = 0; i != NElts; ++i)
1538 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1541 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1542 if (N1.getOpcode() == ISD::UNDEF)
1543 commuteShuffle(N1, N2, MaskVec);
1545 // If shuffling a splat, try to blend the splat instead. We do this here so
1546 // that even when this arises during lowering we don't have to re-handle it.
1547 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1548 BitVector UndefElements;
1549 SDValue Splat = BV->getSplatValue(&UndefElements);
1553 for (int i = 0; i < (int)NElts; ++i) {
1554 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1557 // If this input comes from undef, mark it as such.
1558 if (UndefElements[MaskVec[i] - Offset]) {
1563 // If we can blend a non-undef lane, use that instead.
1564 if (!UndefElements[i])
1565 MaskVec[i] = i + Offset;
1568 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1569 BlendSplat(N1BV, 0);
1570 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1571 BlendSplat(N2BV, NElts);
1573 // Canonicalize all index into lhs, -> shuffle lhs, undef
1574 // Canonicalize all index into rhs, -> shuffle rhs, undef
1575 bool AllLHS = true, AllRHS = true;
1576 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1577 for (unsigned i = 0; i != NElts; ++i) {
1578 if (MaskVec[i] >= (int)NElts) {
1583 } else if (MaskVec[i] >= 0) {
1587 if (AllLHS && AllRHS)
1588 return getUNDEF(VT);
1589 if (AllLHS && !N2Undef)
1593 commuteShuffle(N1, N2, MaskVec);
1595 // Reset our undef status after accounting for the mask.
1596 N2Undef = N2.getOpcode() == ISD::UNDEF;
1597 // Re-check whether both sides ended up undef.
1598 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1599 return getUNDEF(VT);
1601 // If Identity shuffle return that node.
1602 bool Identity = true, AllSame = true;
1603 for (unsigned i = 0; i != NElts; ++i) {
1604 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1605 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1607 if (Identity && NElts)
1610 // Shuffling a constant splat doesn't change the result.
1614 // Look through any bitcasts. We check that these don't change the number
1615 // (and size) of elements and just changes their types.
1616 while (V.getOpcode() == ISD::BITCAST)
1617 V = V->getOperand(0);
1619 // A splat should always show up as a build vector node.
1620 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1621 BitVector UndefElements;
1622 SDValue Splat = BV->getSplatValue(&UndefElements);
1623 // If this is a splat of an undef, shuffling it is also undef.
1624 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1625 return getUNDEF(VT);
1628 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1630 // We only have a splat which can skip shuffles if there is a splatted
1631 // value and no undef lanes rearranged by the shuffle.
1632 if (Splat && UndefElements.none()) {
1633 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1634 // number of elements match or the value splatted is a zero constant.
1637 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1638 if (C->isNullValue())
1642 // If the shuffle itself creates a splat, build the vector directly.
1643 if (AllSame && SameNumElts) {
1644 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1645 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1647 EVT BuildVT = BV->getValueType(0);
1648 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1650 // We may have jumped through bitcasts, so the type of the
1651 // BUILD_VECTOR may not match the type of the shuffle.
1653 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1659 FoldingSetNodeID ID;
1660 SDValue Ops[2] = { N1, N2 };
1661 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1662 for (unsigned i = 0; i != NElts; ++i)
1663 ID.AddInteger(MaskVec[i]);
1666 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1667 return SDValue(E, 0);
1669 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1670 // SDNode doesn't have access to it. This memory will be "leaked" when
1671 // the node is deallocated, but recovered when the NodeAllocator is released.
1672 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1673 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1675 ShuffleVectorSDNode *N =
1676 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1677 dl.getDebugLoc(), N1, N2,
1679 CSEMap.InsertNode(N, IP);
1681 return SDValue(N, 0);
1684 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1685 MVT VT = SV.getSimpleValueType(0);
1686 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1687 ShuffleVectorSDNode::commuteMask(MaskVec);
1689 SDValue Op0 = SV.getOperand(0);
1690 SDValue Op1 = SV.getOperand(1);
1691 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1694 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1695 SDValue Val, SDValue DTy,
1696 SDValue STy, SDValue Rnd, SDValue Sat,
1697 ISD::CvtCode Code) {
1698 // If the src and dest types are the same and the conversion is between
1699 // integer types of the same sign or two floats, no conversion is necessary.
1701 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1704 FoldingSetNodeID ID;
1705 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1706 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1708 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1709 return SDValue(E, 0);
1711 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1714 CSEMap.InsertNode(N, IP);
1716 return SDValue(N, 0);
1719 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1720 FoldingSetNodeID ID;
1721 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1722 ID.AddInteger(RegNo);
1724 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1725 return SDValue(E, 0);
1727 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1728 CSEMap.InsertNode(N, IP);
1730 return SDValue(N, 0);
1733 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1734 FoldingSetNodeID ID;
1735 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1736 ID.AddPointer(RegMask);
1738 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1739 return SDValue(E, 0);
1741 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1742 CSEMap.InsertNode(N, IP);
1744 return SDValue(N, 0);
1747 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1748 FoldingSetNodeID ID;
1749 SDValue Ops[] = { Root };
1750 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1751 ID.AddPointer(Label);
1753 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1754 return SDValue(E, 0);
1756 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1757 dl.getDebugLoc(), Root, Label);
1758 CSEMap.InsertNode(N, IP);
1760 return SDValue(N, 0);
1764 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1767 unsigned char TargetFlags) {
1768 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1770 FoldingSetNodeID ID;
1771 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1773 ID.AddInteger(Offset);
1774 ID.AddInteger(TargetFlags);
1776 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1777 return SDValue(E, 0);
1779 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1781 CSEMap.InsertNode(N, IP);
1783 return SDValue(N, 0);
1786 SDValue SelectionDAG::getSrcValue(const Value *V) {
1787 assert((!V || V->getType()->isPointerTy()) &&
1788 "SrcValue is not a pointer?");
1790 FoldingSetNodeID ID;
1791 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1795 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1796 return SDValue(E, 0);
1798 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1799 CSEMap.InsertNode(N, IP);
1801 return SDValue(N, 0);
1804 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1805 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1806 FoldingSetNodeID ID;
1807 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1811 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1812 return SDValue(E, 0);
1814 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1815 CSEMap.InsertNode(N, IP);
1817 return SDValue(N, 0);
1820 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1821 if (VT == V.getValueType())
1824 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1827 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1828 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1829 unsigned SrcAS, unsigned DestAS) {
1830 SDValue Ops[] = {Ptr};
1831 FoldingSetNodeID ID;
1832 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1833 ID.AddInteger(SrcAS);
1834 ID.AddInteger(DestAS);
1837 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1838 return SDValue(E, 0);
1840 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1842 VT, Ptr, SrcAS, DestAS);
1843 CSEMap.InsertNode(N, IP);
1845 return SDValue(N, 0);
1848 /// getShiftAmountOperand - Return the specified value casted to
1849 /// the target's desired shift amount type.
1850 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1851 EVT OpTy = Op.getValueType();
1852 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1853 if (OpTy == ShTy || OpTy.isVector()) return Op;
1855 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1858 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1859 /// specified value type.
1860 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1861 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1862 unsigned ByteSize = VT.getStoreSize();
1863 Type *Ty = VT.getTypeForEVT(*getContext());
1864 unsigned StackAlign =
1865 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1867 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1868 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1871 /// CreateStackTemporary - Create a stack temporary suitable for holding
1872 /// either of the specified value types.
1873 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1874 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1875 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1876 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1877 const DataLayout &DL = getDataLayout();
1879 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1881 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1882 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1883 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1886 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1887 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1888 // These setcc operations always fold.
1892 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1894 case ISD::SETTRUE2: {
1895 TargetLowering::BooleanContent Cnt =
1896 TLI->getBooleanContents(N1->getValueType(0));
1898 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1912 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1916 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1917 const APInt &C2 = N2C->getAPIntValue();
1918 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1919 const APInt &C1 = N1C->getAPIntValue();
1922 default: llvm_unreachable("Unknown integer setcc!");
1923 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1924 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1925 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1926 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1927 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1928 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1929 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1930 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1931 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1932 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1936 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1937 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1938 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1941 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1942 return getUNDEF(VT);
1944 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1945 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1946 return getUNDEF(VT);
1948 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1949 R==APFloat::cmpLessThan, dl, VT);
1950 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1951 return getUNDEF(VT);
1953 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1954 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1955 return getUNDEF(VT);
1957 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1958 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1959 return getUNDEF(VT);
1961 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1962 R==APFloat::cmpEqual, dl, VT);
1963 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1964 return getUNDEF(VT);
1966 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1967 R==APFloat::cmpEqual, dl, VT);
1968 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1969 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1970 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1971 R==APFloat::cmpEqual, dl, VT);
1972 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1973 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1974 R==APFloat::cmpLessThan, dl, VT);
1975 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1976 R==APFloat::cmpUnordered, dl, VT);
1977 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1978 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1981 // Ensure that the constant occurs on the RHS.
1982 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1983 MVT CompVT = N1.getValueType().getSimpleVT();
1984 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1987 return getSetCC(dl, VT, N2, N1, SwappedCond);
1991 // Could not fold it.
1995 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1996 /// use this predicate to simplify operations downstream.
1997 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1998 // This predicate is not safe for vector operations.
1999 if (Op.getValueType().isVector())
2002 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2003 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2006 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2007 /// this predicate to simplify operations downstream. Mask is known to be zero
2008 /// for bits that V cannot have.
2009 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2010 unsigned Depth) const {
2011 APInt KnownZero, KnownOne;
2012 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2013 return (KnownZero & Mask) == Mask;
2016 /// Determine which bits of Op are known to be either zero or one and return
2017 /// them in the KnownZero/KnownOne bitsets.
2018 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2019 APInt &KnownOne, unsigned Depth) const {
2020 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2022 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2024 return; // Limit search depth.
2026 APInt KnownZero2, KnownOne2;
2028 switch (Op.getOpcode()) {
2030 // We know all of the bits for a constant!
2031 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2032 KnownZero = ~KnownOne;
2035 // If either the LHS or the RHS are Zero, the result is zero.
2036 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2037 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2039 // Output known-1 bits are only known if set in both the LHS & RHS.
2040 KnownOne &= KnownOne2;
2041 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2042 KnownZero |= KnownZero2;
2045 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2046 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2048 // Output known-0 bits are only known if clear in both the LHS & RHS.
2049 KnownZero &= KnownZero2;
2050 // Output known-1 are known to be set if set in either the LHS | RHS.
2051 KnownOne |= KnownOne2;
2054 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2055 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2057 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2058 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2059 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2060 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2061 KnownZero = KnownZeroOut;
2065 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2066 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2068 // If low bits are zero in either operand, output low known-0 bits.
2069 // Also compute a conserative estimate for high known-0 bits.
2070 // More trickiness is possible, but this is sufficient for the
2071 // interesting case of alignment computation.
2072 KnownOne.clearAllBits();
2073 unsigned TrailZ = KnownZero.countTrailingOnes() +
2074 KnownZero2.countTrailingOnes();
2075 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2076 KnownZero2.countLeadingOnes(),
2077 BitWidth) - BitWidth;
2079 TrailZ = std::min(TrailZ, BitWidth);
2080 LeadZ = std::min(LeadZ, BitWidth);
2081 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2082 APInt::getHighBitsSet(BitWidth, LeadZ);
2086 // For the purposes of computing leading zeros we can conservatively
2087 // treat a udiv as a logical right shift by the power of 2 known to
2088 // be less than the denominator.
2089 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2090 unsigned LeadZ = KnownZero2.countLeadingOnes();
2092 KnownOne2.clearAllBits();
2093 KnownZero2.clearAllBits();
2094 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2095 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2096 if (RHSUnknownLeadingOnes != BitWidth)
2097 LeadZ = std::min(BitWidth,
2098 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2100 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2104 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2105 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2107 // Only known if known in both the LHS and RHS.
2108 KnownOne &= KnownOne2;
2109 KnownZero &= KnownZero2;
2111 case ISD::SELECT_CC:
2112 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2113 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2115 // Only known if known in both the LHS and RHS.
2116 KnownOne &= KnownOne2;
2117 KnownZero &= KnownZero2;
2125 if (Op.getResNo() != 1)
2127 // The boolean result conforms to getBooleanContents.
2128 // If we know the result of a setcc has the top bits zero, use this info.
2129 // We know that we have an integer-based boolean since these operations
2130 // are only available for integer.
2131 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2132 TargetLowering::ZeroOrOneBooleanContent &&
2134 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2137 // If we know the result of a setcc has the top bits zero, use this info.
2138 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2139 TargetLowering::ZeroOrOneBooleanContent &&
2141 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2144 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2145 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2146 unsigned ShAmt = SA->getZExtValue();
2148 // If the shift count is an invalid immediate, don't do anything.
2149 if (ShAmt >= BitWidth)
2152 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2153 KnownZero <<= ShAmt;
2155 // low bits known zero.
2156 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2160 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2161 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2162 unsigned ShAmt = SA->getZExtValue();
2164 // If the shift count is an invalid immediate, don't do anything.
2165 if (ShAmt >= BitWidth)
2168 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2169 KnownZero = KnownZero.lshr(ShAmt);
2170 KnownOne = KnownOne.lshr(ShAmt);
2172 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2173 KnownZero |= HighBits; // High bits known zero.
2177 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2178 unsigned ShAmt = SA->getZExtValue();
2180 // If the shift count is an invalid immediate, don't do anything.
2181 if (ShAmt >= BitWidth)
2184 // If any of the demanded bits are produced by the sign extension, we also
2185 // demand the input sign bit.
2186 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2188 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2189 KnownZero = KnownZero.lshr(ShAmt);
2190 KnownOne = KnownOne.lshr(ShAmt);
2192 // Handle the sign bits.
2193 APInt SignBit = APInt::getSignBit(BitWidth);
2194 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2196 if (KnownZero.intersects(SignBit)) {
2197 KnownZero |= HighBits; // New bits are known zero.
2198 } else if (KnownOne.intersects(SignBit)) {
2199 KnownOne |= HighBits; // New bits are known one.
2203 case ISD::SIGN_EXTEND_INREG: {
2204 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2205 unsigned EBits = EVT.getScalarType().getSizeInBits();
2207 // Sign extension. Compute the demanded bits in the result that are not
2208 // present in the input.
2209 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2211 APInt InSignBit = APInt::getSignBit(EBits);
2212 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2214 // If the sign extended bits are demanded, we know that the sign
2216 InSignBit = InSignBit.zext(BitWidth);
2217 if (NewBits.getBoolValue())
2218 InputDemandedBits |= InSignBit;
2220 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2221 KnownOne &= InputDemandedBits;
2222 KnownZero &= InputDemandedBits;
2224 // If the sign bit of the input is known set or clear, then we know the
2225 // top bits of the result.
2226 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2227 KnownZero |= NewBits;
2228 KnownOne &= ~NewBits;
2229 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2230 KnownOne |= NewBits;
2231 KnownZero &= ~NewBits;
2232 } else { // Input sign bit unknown
2233 KnownZero &= ~NewBits;
2234 KnownOne &= ~NewBits;
2239 case ISD::CTTZ_ZERO_UNDEF:
2241 case ISD::CTLZ_ZERO_UNDEF:
2243 unsigned LowBits = Log2_32(BitWidth)+1;
2244 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2245 KnownOne.clearAllBits();
2249 LoadSDNode *LD = cast<LoadSDNode>(Op);
2250 // If this is a ZEXTLoad and we are looking at the loaded value.
2251 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2252 EVT VT = LD->getMemoryVT();
2253 unsigned MemBits = VT.getScalarType().getSizeInBits();
2254 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2255 } else if (const MDNode *Ranges = LD->getRanges()) {
2256 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2260 case ISD::ZERO_EXTEND: {
2261 EVT InVT = Op.getOperand(0).getValueType();
2262 unsigned InBits = InVT.getScalarType().getSizeInBits();
2263 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2264 KnownZero = KnownZero.trunc(InBits);
2265 KnownOne = KnownOne.trunc(InBits);
2266 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2267 KnownZero = KnownZero.zext(BitWidth);
2268 KnownOne = KnownOne.zext(BitWidth);
2269 KnownZero |= NewBits;
2272 case ISD::SIGN_EXTEND: {
2273 EVT InVT = Op.getOperand(0).getValueType();
2274 unsigned InBits = InVT.getScalarType().getSizeInBits();
2275 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2277 KnownZero = KnownZero.trunc(InBits);
2278 KnownOne = KnownOne.trunc(InBits);
2279 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2281 // Note if the sign bit is known to be zero or one.
2282 bool SignBitKnownZero = KnownZero.isNegative();
2283 bool SignBitKnownOne = KnownOne.isNegative();
2285 KnownZero = KnownZero.zext(BitWidth);
2286 KnownOne = KnownOne.zext(BitWidth);
2288 // If the sign bit is known zero or one, the top bits match.
2289 if (SignBitKnownZero)
2290 KnownZero |= NewBits;
2291 else if (SignBitKnownOne)
2292 KnownOne |= NewBits;
2295 case ISD::ANY_EXTEND: {
2296 EVT InVT = Op.getOperand(0).getValueType();
2297 unsigned InBits = InVT.getScalarType().getSizeInBits();
2298 KnownZero = KnownZero.trunc(InBits);
2299 KnownOne = KnownOne.trunc(InBits);
2300 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2301 KnownZero = KnownZero.zext(BitWidth);
2302 KnownOne = KnownOne.zext(BitWidth);
2305 case ISD::TRUNCATE: {
2306 EVT InVT = Op.getOperand(0).getValueType();
2307 unsigned InBits = InVT.getScalarType().getSizeInBits();
2308 KnownZero = KnownZero.zext(InBits);
2309 KnownOne = KnownOne.zext(InBits);
2310 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2311 KnownZero = KnownZero.trunc(BitWidth);
2312 KnownOne = KnownOne.trunc(BitWidth);
2315 case ISD::AssertZext: {
2316 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2317 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2318 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2319 KnownZero |= (~InMask);
2320 KnownOne &= (~KnownZero);
2324 // All bits are zero except the low bit.
2325 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2329 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2330 // We know that the top bits of C-X are clear if X contains less bits
2331 // than C (i.e. no wrap-around can happen). For example, 20-X is
2332 // positive if we can prove that X is >= 0 and < 16.
2333 if (CLHS->getAPIntValue().isNonNegative()) {
2334 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2335 // NLZ can't be BitWidth with no sign bit
2336 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2337 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2339 // If all of the MaskV bits are known to be zero, then we know the
2340 // output top bits are zero, because we now know that the output is
2342 if ((KnownZero2 & MaskV) == MaskV) {
2343 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2344 // Top bits known zero.
2345 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2353 // Output known-0 bits are known if clear or set in both the low clear bits
2354 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2355 // low 3 bits clear.
2356 // Output known-0 bits are also known if the top bits of each input are
2357 // known to be clear. For example, if one input has the top 10 bits clear
2358 // and the other has the top 8 bits clear, we know the top 7 bits of the
2359 // output must be clear.
2360 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2361 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2362 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2364 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2365 KnownZeroHigh = std::min(KnownZeroHigh,
2366 KnownZero2.countLeadingOnes());
2367 KnownZeroLow = std::min(KnownZeroLow,
2368 KnownZero2.countTrailingOnes());
2370 if (Op.getOpcode() == ISD::ADD) {
2371 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2372 if (KnownZeroHigh > 1)
2373 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2377 // With ADDE, a carry bit may be added in, so we can only use this
2378 // information if we know (at least) that the low two bits are clear. We
2379 // then return to the caller that the low bit is unknown but that other bits
2381 if (KnownZeroLow >= 2) // ADDE
2382 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2386 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2387 const APInt &RA = Rem->getAPIntValue().abs();
2388 if (RA.isPowerOf2()) {
2389 APInt LowBits = RA - 1;
2390 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2392 // The low bits of the first operand are unchanged by the srem.
2393 KnownZero = KnownZero2 & LowBits;
2394 KnownOne = KnownOne2 & LowBits;
2396 // If the first operand is non-negative or has all low bits zero, then
2397 // the upper bits are all zero.
2398 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2399 KnownZero |= ~LowBits;
2401 // If the first operand is negative and not all low bits are zero, then
2402 // the upper bits are all one.
2403 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2404 KnownOne |= ~LowBits;
2405 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2410 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2411 const APInt &RA = Rem->getAPIntValue();
2412 if (RA.isPowerOf2()) {
2413 APInt LowBits = (RA - 1);
2414 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2416 // The upper bits are all zero, the lower ones are unchanged.
2417 KnownZero = KnownZero2 | ~LowBits;
2418 KnownOne = KnownOne2 & LowBits;
2423 // Since the result is less than or equal to either operand, any leading
2424 // zero bits in either operand must also exist in the result.
2425 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2426 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2428 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2429 KnownZero2.countLeadingOnes());
2430 KnownOne.clearAllBits();
2431 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2434 case ISD::EXTRACT_ELEMENT: {
2435 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2436 const unsigned Index =
2437 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2438 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2440 // Remove low part of known bits mask
2441 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2442 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2444 // Remove high part of known bit mask
2445 KnownZero = KnownZero.trunc(BitWidth);
2446 KnownOne = KnownOne.trunc(BitWidth);
2453 APInt Op0Zero, Op0One;
2454 APInt Op1Zero, Op1One;
2455 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2456 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2458 KnownZero = Op0Zero & Op1Zero;
2459 KnownOne = Op0One & Op1One;
2462 case ISD::FrameIndex:
2463 case ISD::TargetFrameIndex:
2464 if (unsigned Align = InferPtrAlignment(Op)) {
2465 // The low bits are known zero if the pointer is aligned.
2466 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2472 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2475 case ISD::INTRINSIC_WO_CHAIN:
2476 case ISD::INTRINSIC_W_CHAIN:
2477 case ISD::INTRINSIC_VOID:
2478 // Allow the target to implement this method for its nodes.
2479 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2483 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2486 /// ComputeNumSignBits - Return the number of times the sign bit of the
2487 /// register is replicated into the other bits. We know that at least 1 bit
2488 /// is always equal to the sign bit (itself), but other cases can give us
2489 /// information. For example, immediately after an "SRA X, 2", we know that
2490 /// the top 3 bits are all equal to each other, so we return 3.
2491 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2492 EVT VT = Op.getValueType();
2493 assert(VT.isInteger() && "Invalid VT!");
2494 unsigned VTBits = VT.getScalarType().getSizeInBits();
2496 unsigned FirstAnswer = 1;
2499 return 1; // Limit search depth.
2501 switch (Op.getOpcode()) {
2503 case ISD::AssertSext:
2504 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2505 return VTBits-Tmp+1;
2506 case ISD::AssertZext:
2507 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2510 case ISD::Constant: {
2511 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2512 return Val.getNumSignBits();
2515 case ISD::SIGN_EXTEND:
2517 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2518 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2520 case ISD::SIGN_EXTEND_INREG:
2521 // Max of the input and what this extends.
2523 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2526 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2527 return std::max(Tmp, Tmp2);
2530 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2531 // SRA X, C -> adds C sign bits.
2532 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2533 Tmp += C->getZExtValue();
2534 if (Tmp > VTBits) Tmp = VTBits;
2538 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2539 // shl destroys sign bits.
2540 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2541 if (C->getZExtValue() >= VTBits || // Bad shift.
2542 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2543 return Tmp - C->getZExtValue();
2548 case ISD::XOR: // NOT is handled here.
2549 // Logical binary ops preserve the number of sign bits at the worst.
2550 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2552 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2553 FirstAnswer = std::min(Tmp, Tmp2);
2554 // We computed what we know about the sign bits as our first
2555 // answer. Now proceed to the generic code that uses
2556 // computeKnownBits, and pick whichever answer is better.
2561 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2562 if (Tmp == 1) return 1; // Early out.
2563 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2564 return std::min(Tmp, Tmp2);
2569 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2571 return 1; // Early out.
2572 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2573 return std::min(Tmp, Tmp2);
2580 if (Op.getResNo() != 1)
2582 // The boolean result conforms to getBooleanContents. Fall through.
2583 // If setcc returns 0/-1, all bits are sign bits.
2584 // We know that we have an integer-based boolean since these operations
2585 // are only available for integer.
2586 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2587 TargetLowering::ZeroOrNegativeOneBooleanContent)
2591 // If setcc returns 0/-1, all bits are sign bits.
2592 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2593 TargetLowering::ZeroOrNegativeOneBooleanContent)
2598 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2599 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2601 // Handle rotate right by N like a rotate left by 32-N.
2602 if (Op.getOpcode() == ISD::ROTR)
2603 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2605 // If we aren't rotating out all of the known-in sign bits, return the
2606 // number that are left. This handles rotl(sext(x), 1) for example.
2607 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2608 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2612 // Add can have at most one carry bit. Thus we know that the output
2613 // is, at worst, one more bit than the inputs.
2614 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2615 if (Tmp == 1) return 1; // Early out.
2617 // Special case decrementing a value (ADD X, -1):
2618 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2619 if (CRHS->isAllOnesValue()) {
2620 APInt KnownZero, KnownOne;
2621 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2623 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2625 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2628 // If we are subtracting one from a positive number, there is no carry
2629 // out of the result.
2630 if (KnownZero.isNegative())
2634 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2635 if (Tmp2 == 1) return 1;
2636 return std::min(Tmp, Tmp2)-1;
2639 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2640 if (Tmp2 == 1) return 1;
2643 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2644 if (CLHS->isNullValue()) {
2645 APInt KnownZero, KnownOne;
2646 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2647 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2649 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2652 // If the input is known to be positive (the sign bit is known clear),
2653 // the output of the NEG has the same number of sign bits as the input.
2654 if (KnownZero.isNegative())
2657 // Otherwise, we treat this like a SUB.
2660 // Sub can have at most one carry bit. Thus we know that the output
2661 // is, at worst, one more bit than the inputs.
2662 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2663 if (Tmp == 1) return 1; // Early out.
2664 return std::min(Tmp, Tmp2)-1;
2666 // FIXME: it's tricky to do anything useful for this, but it is an important
2667 // case for targets like X86.
2669 case ISD::EXTRACT_ELEMENT: {
2670 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2671 const int BitWidth = Op.getValueType().getSizeInBits();
2673 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2675 // Get reverse index (starting from 1), Op1 value indexes elements from
2676 // little end. Sign starts at big end.
2677 const int rIndex = Items - 1 -
2678 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2680 // If the sign portion ends in our element the subtraction gives correct
2681 // result. Otherwise it gives either negative or > bitwidth result
2682 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2686 // If we are looking at the loaded value of the SDNode.
2687 if (Op.getResNo() == 0) {
2688 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2689 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2690 unsigned ExtType = LD->getExtensionType();
2693 case ISD::SEXTLOAD: // '17' bits known
2694 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2695 return VTBits-Tmp+1;
2696 case ISD::ZEXTLOAD: // '16' bits known
2697 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2703 // Allow the target to implement this method for its nodes.
2704 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2705 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2706 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2707 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2708 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2709 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2712 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2713 // use this information.
2714 APInt KnownZero, KnownOne;
2715 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2718 if (KnownZero.isNegative()) { // sign bit is 0
2720 } else if (KnownOne.isNegative()) { // sign bit is 1;
2727 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2728 // the number of identical bits in the top of the input value.
2730 Mask <<= Mask.getBitWidth()-VTBits;
2731 // Return # leading zeros. We use 'min' here in case Val was zero before
2732 // shifting. We don't want to return '64' as for an i32 "0".
2733 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2736 /// isBaseWithConstantOffset - Return true if the specified operand is an
2737 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2738 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2739 /// semantics as an ADD. This handles the equivalence:
2740 /// X|Cst == X+Cst iff X&Cst = 0.
2741 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2742 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2743 !isa<ConstantSDNode>(Op.getOperand(1)))
2746 if (Op.getOpcode() == ISD::OR &&
2747 !MaskedValueIsZero(Op.getOperand(0),
2748 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2755 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2756 // If we're told that NaNs won't happen, assume they won't.
2757 if (getTarget().Options.NoNaNsFPMath)
2760 // If the value is a constant, we can obviously see if it is a NaN or not.
2761 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2762 return !C->getValueAPF().isNaN();
2764 // TODO: Recognize more cases here.
2769 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2770 // If the value is a constant, we can obviously see if it is a zero or not.
2771 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2772 return !C->isZero();
2774 // TODO: Recognize more cases here.
2775 switch (Op.getOpcode()) {
2778 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2779 return !C->isNullValue();
2786 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2787 // Check the obvious case.
2788 if (A == B) return true;
2790 // For for negative and positive zero.
2791 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2792 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2793 if (CA->isZero() && CB->isZero()) return true;
2795 // Otherwise they may not be equal.
2799 /// getNode - Gets or creates the specified node.
2801 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2802 FoldingSetNodeID ID;
2803 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2805 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2806 return SDValue(E, 0);
2808 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2809 DL.getDebugLoc(), getVTList(VT));
2810 CSEMap.InsertNode(N, IP);
2813 return SDValue(N, 0);
2816 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2817 EVT VT, SDValue Operand) {
2818 // Constant fold unary operations with an integer constant operand. Even
2819 // opaque constant will be folded, because the folding of unary operations
2820 // doesn't create new constants with different values. Nevertheless, the
2821 // opaque flag is preserved during folding to prevent future folding with
2823 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2824 const APInt &Val = C->getAPIntValue();
2827 case ISD::SIGN_EXTEND:
2828 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2829 C->isTargetOpcode(), C->isOpaque());
2830 case ISD::ANY_EXTEND:
2831 case ISD::ZERO_EXTEND:
2833 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2834 C->isTargetOpcode(), C->isOpaque());
2835 case ISD::UINT_TO_FP:
2836 case ISD::SINT_TO_FP: {
2837 APFloat apf(EVTToAPFloatSemantics(VT),
2838 APInt::getNullValue(VT.getSizeInBits()));
2839 (void)apf.convertFromAPInt(Val,
2840 Opcode==ISD::SINT_TO_FP,
2841 APFloat::rmNearestTiesToEven);
2842 return getConstantFP(apf, DL, VT);
2845 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2846 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2847 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2848 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2849 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2850 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2853 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2856 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2859 case ISD::CTLZ_ZERO_UNDEF:
2860 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2863 case ISD::CTTZ_ZERO_UNDEF:
2864 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2869 // Constant fold unary operations with a floating point constant operand.
2870 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2871 APFloat V = C->getValueAPF(); // make copy
2875 return getConstantFP(V, DL, VT);
2878 return getConstantFP(V, DL, VT);
2880 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2881 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2882 return getConstantFP(V, DL, VT);
2886 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2887 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2888 return getConstantFP(V, DL, VT);
2892 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2893 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2894 return getConstantFP(V, DL, VT);
2897 case ISD::FP_EXTEND: {
2899 // This can return overflow, underflow, or inexact; we don't care.
2900 // FIXME need to be more flexible about rounding mode.
2901 (void)V.convert(EVTToAPFloatSemantics(VT),
2902 APFloat::rmNearestTiesToEven, &ignored);
2903 return getConstantFP(V, DL, VT);
2905 case ISD::FP_TO_SINT:
2906 case ISD::FP_TO_UINT: {
2909 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2910 // FIXME need to be more flexible about rounding mode.
2911 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2912 Opcode==ISD::FP_TO_SINT,
2913 APFloat::rmTowardZero, &ignored);
2914 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2916 APInt api(VT.getSizeInBits(), x);
2917 return getConstant(api, DL, VT);
2920 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2921 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2922 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2923 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2924 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2925 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2930 // Constant fold unary operations with a vector integer or float operand.
2931 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2932 if (BV->isConstant()) {
2935 // FIXME: Entirely reasonable to perform folding of other unary
2936 // operations here as the need arises.
2943 case ISD::FP_EXTEND:
2944 case ISD::FP_TO_SINT:
2945 case ISD::FP_TO_UINT:
2947 case ISD::UINT_TO_FP:
2948 case ISD::SINT_TO_FP:
2951 case ISD::CTLZ_ZERO_UNDEF:
2953 case ISD::CTTZ_ZERO_UNDEF:
2955 EVT SVT = VT.getScalarType();
2956 EVT InVT = BV->getValueType(0);
2957 EVT InSVT = InVT.getScalarType();
2959 // Find legal integer scalar type for constant promotion and
2960 // ensure that its scalar size is at least as large as source.
2962 if (SVT.isInteger()) {
2963 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2964 if (LegalSVT.bitsLT(SVT)) break;
2967 // Let the above scalar folding handle the folding of each element.
2968 SmallVector<SDValue, 8> Ops;
2969 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2970 SDValue OpN = BV->getOperand(i);
2971 EVT OpVT = OpN.getValueType();
2973 // Build vector (integer) scalar operands may need implicit
2974 // truncation - do this before constant folding.
2975 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2976 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2978 OpN = getNode(Opcode, DL, SVT, OpN);
2980 // Legalize the (integer) scalar constant if necessary.
2981 if (LegalSVT != SVT)
2982 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2984 if (OpN.getOpcode() != ISD::UNDEF &&
2985 OpN.getOpcode() != ISD::Constant &&
2986 OpN.getOpcode() != ISD::ConstantFP)
2990 if (Ops.size() == VT.getVectorNumElements())
2991 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2998 unsigned OpOpcode = Operand.getNode()->getOpcode();
3000 case ISD::TokenFactor:
3001 case ISD::MERGE_VALUES:
3002 case ISD::CONCAT_VECTORS:
3003 return Operand; // Factor, merge or concat of one node? No need.
3004 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3005 case ISD::FP_EXTEND:
3006 assert(VT.isFloatingPoint() &&
3007 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3008 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3009 assert((!VT.isVector() ||
3010 VT.getVectorNumElements() ==
3011 Operand.getValueType().getVectorNumElements()) &&
3012 "Vector element count mismatch!");
3013 assert(Operand.getValueType().bitsLT(VT) &&
3014 "Invalid fpext node, dst < src!");
3015 if (Operand.getOpcode() == ISD::UNDEF)
3016 return getUNDEF(VT);
3018 case ISD::SIGN_EXTEND:
3019 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3020 "Invalid SIGN_EXTEND!");
3021 if (Operand.getValueType() == VT) return Operand; // noop extension
3022 assert((!VT.isVector() ||
3023 VT.getVectorNumElements() ==
3024 Operand.getValueType().getVectorNumElements()) &&
3025 "Vector element count mismatch!");
3026 assert(Operand.getValueType().bitsLT(VT) &&
3027 "Invalid sext node, dst < src!");
3028 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3029 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3030 else if (OpOpcode == ISD::UNDEF)
3031 // sext(undef) = 0, because the top bits will all be the same.
3032 return getConstant(0, DL, VT);
3034 case ISD::ZERO_EXTEND:
3035 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3036 "Invalid ZERO_EXTEND!");
3037 if (Operand.getValueType() == VT) return Operand; // noop extension
3038 assert((!VT.isVector() ||
3039 VT.getVectorNumElements() ==
3040 Operand.getValueType().getVectorNumElements()) &&
3041 "Vector element count mismatch!");
3042 assert(Operand.getValueType().bitsLT(VT) &&
3043 "Invalid zext node, dst < src!");
3044 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3045 return getNode(ISD::ZERO_EXTEND, DL, VT,
3046 Operand.getNode()->getOperand(0));
3047 else if (OpOpcode == ISD::UNDEF)
3048 // zext(undef) = 0, because the top bits will be zero.
3049 return getConstant(0, DL, VT);
3051 case ISD::ANY_EXTEND:
3052 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3053 "Invalid ANY_EXTEND!");
3054 if (Operand.getValueType() == VT) return Operand; // noop extension
3055 assert((!VT.isVector() ||
3056 VT.getVectorNumElements() ==
3057 Operand.getValueType().getVectorNumElements()) &&
3058 "Vector element count mismatch!");
3059 assert(Operand.getValueType().bitsLT(VT) &&
3060 "Invalid anyext node, dst < src!");
3062 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3063 OpOpcode == ISD::ANY_EXTEND)
3064 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3065 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3066 else if (OpOpcode == ISD::UNDEF)
3067 return getUNDEF(VT);
3069 // (ext (trunx x)) -> x
3070 if (OpOpcode == ISD::TRUNCATE) {
3071 SDValue OpOp = Operand.getNode()->getOperand(0);
3072 if (OpOp.getValueType() == VT)
3077 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3078 "Invalid TRUNCATE!");
3079 if (Operand.getValueType() == VT) return Operand; // noop truncate
3080 assert((!VT.isVector() ||
3081 VT.getVectorNumElements() ==
3082 Operand.getValueType().getVectorNumElements()) &&
3083 "Vector element count mismatch!");
3084 assert(Operand.getValueType().bitsGT(VT) &&
3085 "Invalid truncate node, src < dst!");
3086 if (OpOpcode == ISD::TRUNCATE)
3087 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3088 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3089 OpOpcode == ISD::ANY_EXTEND) {
3090 // If the source is smaller than the dest, we still need an extend.
3091 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3092 .bitsLT(VT.getScalarType()))
3093 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3094 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3095 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3096 return Operand.getNode()->getOperand(0);
3098 if (OpOpcode == ISD::UNDEF)
3099 return getUNDEF(VT);
3102 assert(VT.isInteger() && VT == Operand.getValueType() &&
3104 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3105 "BSWAP types must be a multiple of 16 bits!");
3106 if (OpOpcode == ISD::UNDEF)
3107 return getUNDEF(VT);
3110 // Basic sanity checking.
3111 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3112 && "Cannot BITCAST between types of different sizes!");
3113 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3114 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3115 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3116 if (OpOpcode == ISD::UNDEF)
3117 return getUNDEF(VT);
3119 case ISD::SCALAR_TO_VECTOR:
3120 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3121 (VT.getVectorElementType() == Operand.getValueType() ||
3122 (VT.getVectorElementType().isInteger() &&
3123 Operand.getValueType().isInteger() &&
3124 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3125 "Illegal SCALAR_TO_VECTOR node!");
3126 if (OpOpcode == ISD::UNDEF)
3127 return getUNDEF(VT);
3128 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3129 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3130 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3131 Operand.getConstantOperandVal(1) == 0 &&
3132 Operand.getOperand(0).getValueType() == VT)
3133 return Operand.getOperand(0);
3136 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3137 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3138 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3139 Operand.getNode()->getOperand(0));
3140 if (OpOpcode == ISD::FNEG) // --X -> X
3141 return Operand.getNode()->getOperand(0);
3144 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3145 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3150 SDVTList VTs = getVTList(VT);
3151 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3152 FoldingSetNodeID ID;
3153 SDValue Ops[1] = { Operand };
3154 AddNodeIDNode(ID, Opcode, VTs, Ops);
3156 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3157 return SDValue(E, 0);
3159 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3160 DL.getDebugLoc(), VTs, Operand);
3161 CSEMap.InsertNode(N, IP);
3163 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3164 DL.getDebugLoc(), VTs, Operand);
3168 return SDValue(N, 0);
3171 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3174 case ISD::ADD: return std::make_pair(C1 + C2, true);
3175 case ISD::SUB: return std::make_pair(C1 - C2, true);
3176 case ISD::MUL: return std::make_pair(C1 * C2, true);
3177 case ISD::AND: return std::make_pair(C1 & C2, true);
3178 case ISD::OR: return std::make_pair(C1 | C2, true);
3179 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3180 case ISD::SHL: return std::make_pair(C1 << C2, true);
3181 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3182 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3183 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3184 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3185 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3186 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3187 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3188 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3190 if (!C2.getBoolValue())
3192 return std::make_pair(C1.udiv(C2), true);
3194 if (!C2.getBoolValue())
3196 return std::make_pair(C1.urem(C2), true);
3198 if (!C2.getBoolValue())
3200 return std::make_pair(C1.sdiv(C2), true);
3202 if (!C2.getBoolValue())
3204 return std::make_pair(C1.srem(C2), true);
3206 return std::make_pair(APInt(1, 0), false);
3209 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3210 const ConstantSDNode *Cst1,
3211 const ConstantSDNode *Cst2) {
3212 if (Cst1->isOpaque() || Cst2->isOpaque())
3215 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3216 Cst2->getAPIntValue());
3219 return getConstant(Folded.first, DL, VT);
3222 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3223 SDNode *Cst1, SDNode *Cst2) {
3224 // If the opcode is a target-specific ISD node, there's nothing we can
3225 // do here and the operand rules may not line up with the below, so
3227 if (Opcode >= ISD::BUILTIN_OP_END)
3230 // Handle the case of two scalars.
3231 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3232 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3233 if (SDValue Folded =
3234 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3237 SmallVector<SDValue, 4> Outputs;
3238 // We may have a vector type but a scalar result. Create a splat.
3239 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3240 // Build a big vector out of the scalar elements we generated.
3241 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3248 // For vectors extract each constant element into Inputs so we can constant
3249 // fold them individually.
3250 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3251 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3255 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3257 EVT SVT = VT.getScalarType();
3258 SmallVector<SDValue, 4> Outputs;
3259 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3260 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3261 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3262 if (!V1 || !V2) // Not a constant, bail.
3265 if (V1->isOpaque() || V2->isOpaque())
3268 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3269 // FIXME: This is valid and could be handled by truncating the APInts.
3270 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3273 // Fold one vector element.
3274 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3275 V2->getAPIntValue());
3278 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3281 assert(VT.getVectorNumElements() == Outputs.size() &&
3282 "Vector size mismatch!");
3284 // We may have a vector type but a scalar result. Create a splat.
3285 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3287 // Build a big vector out of the scalar elements we generated.
3288 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3291 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3292 SDValue N2, const SDNodeFlags *Flags) {
3293 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3294 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3297 case ISD::TokenFactor:
3298 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3299 N2.getValueType() == MVT::Other && "Invalid token factor!");
3300 // Fold trivial token factors.
3301 if (N1.getOpcode() == ISD::EntryToken) return N2;
3302 if (N2.getOpcode() == ISD::EntryToken) return N1;
3303 if (N1 == N2) return N1;
3305 case ISD::CONCAT_VECTORS:
3306 // Concat of UNDEFs is UNDEF.
3307 if (N1.getOpcode() == ISD::UNDEF &&
3308 N2.getOpcode() == ISD::UNDEF)
3309 return getUNDEF(VT);
3311 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3312 // one big BUILD_VECTOR.
3313 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3314 N2.getOpcode() == ISD::BUILD_VECTOR) {
3315 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3316 N1.getNode()->op_end());
3317 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3319 // BUILD_VECTOR requires all inputs to be of the same type, find the
3320 // maximum type and extend them all.
3321 EVT SVT = VT.getScalarType();
3322 for (SDValue Op : Elts)
3323 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3324 if (SVT.bitsGT(VT.getScalarType()))
3325 for (SDValue &Op : Elts)
3326 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3327 ? getZExtOrTrunc(Op, DL, SVT)
3328 : getSExtOrTrunc(Op, DL, SVT);
3330 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3334 assert(VT.isInteger() && "This operator does not apply to FP types!");
3335 assert(N1.getValueType() == N2.getValueType() &&
3336 N1.getValueType() == VT && "Binary operator types must match!");
3337 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3338 // worth handling here.
3339 if (N2C && N2C->isNullValue())
3341 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3348 assert(VT.isInteger() && "This operator does not apply to FP types!");
3349 assert(N1.getValueType() == N2.getValueType() &&
3350 N1.getValueType() == VT && "Binary operator types must match!");
3351 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3352 // it's worth handling here.
3353 if (N2C && N2C->isNullValue())
3367 assert(VT.isInteger() && "This operator does not apply to FP types!");
3368 assert(N1.getValueType() == N2.getValueType() &&
3369 N1.getValueType() == VT && "Binary operator types must match!");
3376 if (getTarget().Options.UnsafeFPMath) {
3377 if (Opcode == ISD::FADD) {
3379 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3380 if (CFP->getValueAPF().isZero())
3383 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3384 if (CFP->getValueAPF().isZero())
3386 } else if (Opcode == ISD::FSUB) {
3388 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3389 if (CFP->getValueAPF().isZero())
3391 } else if (Opcode == ISD::FMUL) {
3392 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3395 // If the first operand isn't the constant, try the second
3397 CFP = dyn_cast<ConstantFPSDNode>(N2);
3404 return SDValue(CFP,0);
3406 if (CFP->isExactlyValue(1.0))
3411 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3412 assert(N1.getValueType() == N2.getValueType() &&
3413 N1.getValueType() == VT && "Binary operator types must match!");
3415 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3416 assert(N1.getValueType() == VT &&
3417 N1.getValueType().isFloatingPoint() &&
3418 N2.getValueType().isFloatingPoint() &&
3419 "Invalid FCOPYSIGN!");
3426 assert(VT == N1.getValueType() &&
3427 "Shift operators return type must be the same as their first arg");
3428 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3429 "Shifts only work on integers");
3430 assert((!VT.isVector() || VT == N2.getValueType()) &&
3431 "Vector shift amounts must be in the same as their first arg");
3432 // Verify that the shift amount VT is bit enough to hold valid shift
3433 // amounts. This catches things like trying to shift an i1024 value by an
3434 // i8, which is easy to fall into in generic code that uses
3435 // TLI.getShiftAmount().
3436 assert(N2.getValueType().getSizeInBits() >=
3437 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3438 "Invalid use of small shift amount with oversized value!");
3440 // Always fold shifts of i1 values so the code generator doesn't need to
3441 // handle them. Since we know the size of the shift has to be less than the
3442 // size of the value, the shift/rotate count is guaranteed to be zero.
3445 if (N2C && N2C->isNullValue())
3448 case ISD::FP_ROUND_INREG: {
3449 EVT EVT = cast<VTSDNode>(N2)->getVT();
3450 assert(VT == N1.getValueType() && "Not an inreg round!");
3451 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3452 "Cannot FP_ROUND_INREG integer types");
3453 assert(EVT.isVector() == VT.isVector() &&
3454 "FP_ROUND_INREG type should be vector iff the operand "
3456 assert((!EVT.isVector() ||
3457 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3458 "Vector element counts must match in FP_ROUND_INREG");
3459 assert(EVT.bitsLE(VT) && "Not rounding down!");
3461 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3465 assert(VT.isFloatingPoint() &&
3466 N1.getValueType().isFloatingPoint() &&
3467 VT.bitsLE(N1.getValueType()) &&
3468 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3469 if (N1.getValueType() == VT) return N1; // noop conversion.
3471 case ISD::AssertSext:
3472 case ISD::AssertZext: {
3473 EVT EVT = cast<VTSDNode>(N2)->getVT();
3474 assert(VT == N1.getValueType() && "Not an inreg extend!");
3475 assert(VT.isInteger() && EVT.isInteger() &&
3476 "Cannot *_EXTEND_INREG FP types");
3477 assert(!EVT.isVector() &&
3478 "AssertSExt/AssertZExt type should be the vector element type "
3479 "rather than the vector type!");
3480 assert(EVT.bitsLE(VT) && "Not extending!");
3481 if (VT == EVT) return N1; // noop assertion.
3484 case ISD::SIGN_EXTEND_INREG: {
3485 EVT EVT = cast<VTSDNode>(N2)->getVT();
3486 assert(VT == N1.getValueType() && "Not an inreg extend!");
3487 assert(VT.isInteger() && EVT.isInteger() &&
3488 "Cannot *_EXTEND_INREG FP types");
3489 assert(EVT.isVector() == VT.isVector() &&
3490 "SIGN_EXTEND_INREG type should be vector iff the operand "
3492 assert((!EVT.isVector() ||
3493 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3494 "Vector element counts must match in SIGN_EXTEND_INREG");
3495 assert(EVT.bitsLE(VT) && "Not extending!");
3496 if (EVT == VT) return N1; // Not actually extending
3498 auto SignExtendInReg = [&](APInt Val) {
3499 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3500 Val <<= Val.getBitWidth() - FromBits;
3501 Val = Val.ashr(Val.getBitWidth() - FromBits);
3502 return getConstant(Val, DL, VT.getScalarType());
3506 APInt Val = N1C->getAPIntValue();
3507 return SignExtendInReg(Val);
3509 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3510 SmallVector<SDValue, 8> Ops;
3511 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3512 SDValue Op = N1.getOperand(i);
3513 if (Op.getValueType() != VT.getScalarType()) break;
3514 if (Op.getOpcode() == ISD::UNDEF) {
3518 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3519 APInt Val = C->getAPIntValue();
3520 Ops.push_back(SignExtendInReg(Val));
3525 if (Ops.size() == VT.getVectorNumElements())
3526 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3530 case ISD::EXTRACT_VECTOR_ELT:
3531 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3532 if (N1.getOpcode() == ISD::UNDEF)
3533 return getUNDEF(VT);
3535 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3536 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3537 return getUNDEF(VT);
3539 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3540 // expanding copies of large vectors from registers.
3542 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3543 N1.getNumOperands() > 0) {
3545 N1.getOperand(0).getValueType().getVectorNumElements();
3546 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3547 N1.getOperand(N2C->getZExtValue() / Factor),
3548 getConstant(N2C->getZExtValue() % Factor, DL,
3549 N2.getValueType()));
3552 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3553 // expanding large vector constants.
3554 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3555 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3557 if (VT != Elt.getValueType())
3558 // If the vector element type is not legal, the BUILD_VECTOR operands
3559 // are promoted and implicitly truncated, and the result implicitly
3560 // extended. Make that explicit here.
3561 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3566 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3567 // operations are lowered to scalars.
3568 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3569 // If the indices are the same, return the inserted element else
3570 // if the indices are known different, extract the element from
3571 // the original vector.
3572 SDValue N1Op2 = N1.getOperand(2);
3573 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3575 if (N1Op2C && N2C) {
3576 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3577 if (VT == N1.getOperand(1).getValueType())
3578 return N1.getOperand(1);
3580 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3583 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3587 case ISD::EXTRACT_ELEMENT:
3588 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3589 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3590 (N1.getValueType().isInteger() == VT.isInteger()) &&
3591 N1.getValueType() != VT &&
3592 "Wrong types for EXTRACT_ELEMENT!");
3594 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3595 // 64-bit integers into 32-bit parts. Instead of building the extract of
3596 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3597 if (N1.getOpcode() == ISD::BUILD_PAIR)
3598 return N1.getOperand(N2C->getZExtValue());
3600 // EXTRACT_ELEMENT of a constant int is also very common.
3601 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3602 unsigned ElementSize = VT.getSizeInBits();
3603 unsigned Shift = ElementSize * N2C->getZExtValue();
3604 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3605 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3608 case ISD::EXTRACT_SUBVECTOR: {
3610 if (VT.isSimple() && N1.getValueType().isSimple()) {
3611 assert(VT.isVector() && N1.getValueType().isVector() &&
3612 "Extract subvector VTs must be a vectors!");
3613 assert(VT.getVectorElementType() ==
3614 N1.getValueType().getVectorElementType() &&
3615 "Extract subvector VTs must have the same element type!");
3616 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3617 "Extract subvector must be from larger vector to smaller vector!");
3619 if (isa<ConstantSDNode>(Index)) {
3620 assert((VT.getVectorNumElements() +
3621 cast<ConstantSDNode>(Index)->getZExtValue()
3622 <= N1.getValueType().getVectorNumElements())
3623 && "Extract subvector overflow!");
3626 // Trivial extraction.
3627 if (VT.getSimpleVT() == N1.getSimpleValueType())
3634 // Perform trivial constant folding.
3636 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3639 // Canonicalize constant to RHS if commutative.
3640 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3641 std::swap(N1C, N2C);
3645 // Constant fold FP operations.
3646 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3647 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3648 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3650 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3651 // Canonicalize constant to RHS if commutative.
3652 std::swap(N1CFP, N2CFP);
3655 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3656 APFloat::opStatus s;
3659 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3660 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3661 return getConstantFP(V1, DL, VT);
3664 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3665 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3666 return getConstantFP(V1, DL, VT);
3669 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3670 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3671 return getConstantFP(V1, DL, VT);
3674 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3675 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3676 s!=APFloat::opDivByZero)) {
3677 return getConstantFP(V1, DL, VT);
3681 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3682 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3683 s!=APFloat::opDivByZero)) {
3684 return getConstantFP(V1, DL, VT);
3687 case ISD::FCOPYSIGN:
3689 return getConstantFP(V1, DL, VT);
3694 if (Opcode == ISD::FP_ROUND) {
3695 APFloat V = N1CFP->getValueAPF(); // make copy
3697 // This can return overflow, underflow, or inexact; we don't care.
3698 // FIXME need to be more flexible about rounding mode.
3699 (void)V.convert(EVTToAPFloatSemantics(VT),
3700 APFloat::rmNearestTiesToEven, &ignored);
3701 return getConstantFP(V, DL, VT);
3705 // Canonicalize an UNDEF to the RHS, even over a constant.
3706 if (N1.getOpcode() == ISD::UNDEF) {
3707 if (isCommutativeBinOp(Opcode)) {
3711 case ISD::FP_ROUND_INREG:
3712 case ISD::SIGN_EXTEND_INREG:
3718 return N1; // fold op(undef, arg2) -> undef
3726 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3727 // For vectors, we can't easily build an all zero vector, just return
3734 // Fold a bunch of operators when the RHS is undef.
3735 if (N2.getOpcode() == ISD::UNDEF) {
3738 if (N1.getOpcode() == ISD::UNDEF)
3739 // Handle undef ^ undef -> 0 special case. This is a common
3741 return getConstant(0, DL, VT);
3751 return N2; // fold op(arg1, undef) -> undef
3757 if (getTarget().Options.UnsafeFPMath)
3765 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3766 // For vectors, we can't easily build an all zero vector, just return
3771 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3772 // For vectors, we can't easily build an all one vector, just return
3780 // Memoize this node if possible.
3782 SDVTList VTs = getVTList(VT);
3783 if (VT != MVT::Glue) {
3784 SDValue Ops[] = {N1, N2};
3785 FoldingSetNodeID ID;
3786 AddNodeIDNode(ID, Opcode, VTs, Ops);
3787 AddNodeIDFlags(ID, Opcode, Flags);
3789 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3790 return SDValue(E, 0);
3792 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3794 CSEMap.InsertNode(N, IP);
3796 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3800 return SDValue(N, 0);
3803 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3804 SDValue N1, SDValue N2, SDValue N3) {
3805 // Perform various simplifications.
3806 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3809 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3810 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3811 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3812 if (N1CFP && N2CFP && N3CFP) {
3813 APFloat V1 = N1CFP->getValueAPF();
3814 const APFloat &V2 = N2CFP->getValueAPF();
3815 const APFloat &V3 = N3CFP->getValueAPF();
3816 APFloat::opStatus s =
3817 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3818 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3819 return getConstantFP(V1, DL, VT);
3823 case ISD::CONCAT_VECTORS:
3824 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3825 // one big BUILD_VECTOR.
3826 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3827 N2.getOpcode() == ISD::BUILD_VECTOR &&
3828 N3.getOpcode() == ISD::BUILD_VECTOR) {
3829 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3830 N1.getNode()->op_end());
3831 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3832 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3833 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3837 // Use FoldSetCC to simplify SETCC's.
3838 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3839 if (Simp.getNode()) return Simp;
3844 if (N1C->getZExtValue())
3845 return N2; // select true, X, Y -> X
3846 return N3; // select false, X, Y -> Y
3849 if (N2 == N3) return N2; // select C, X, X -> X
3851 case ISD::VECTOR_SHUFFLE:
3852 llvm_unreachable("should use getVectorShuffle constructor!");
3853 case ISD::INSERT_SUBVECTOR: {
3855 if (VT.isSimple() && N1.getValueType().isSimple()
3856 && N2.getValueType().isSimple()) {
3857 assert(VT.isVector() && N1.getValueType().isVector() &&
3858 N2.getValueType().isVector() &&
3859 "Insert subvector VTs must be a vectors");
3860 assert(VT == N1.getValueType() &&
3861 "Dest and insert subvector source types must match!");
3862 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3863 "Insert subvector must be from smaller vector to larger vector!");
3864 if (isa<ConstantSDNode>(Index)) {
3865 assert((N2.getValueType().getVectorNumElements() +
3866 cast<ConstantSDNode>(Index)->getZExtValue()
3867 <= VT.getVectorNumElements())
3868 && "Insert subvector overflow!");
3871 // Trivial insertion.
3872 if (VT.getSimpleVT() == N2.getSimpleValueType())
3878 // Fold bit_convert nodes from a type to themselves.
3879 if (N1.getValueType() == VT)
3884 // Memoize node if it doesn't produce a flag.
3886 SDVTList VTs = getVTList(VT);
3887 if (VT != MVT::Glue) {
3888 SDValue Ops[] = { N1, N2, N3 };
3889 FoldingSetNodeID ID;
3890 AddNodeIDNode(ID, Opcode, VTs, Ops);
3892 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3893 return SDValue(E, 0);
3895 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3896 DL.getDebugLoc(), VTs, N1, N2, N3);
3897 CSEMap.InsertNode(N, IP);
3899 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3900 DL.getDebugLoc(), VTs, N1, N2, N3);
3904 return SDValue(N, 0);
3907 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3908 SDValue N1, SDValue N2, SDValue N3,
3910 SDValue Ops[] = { N1, N2, N3, N4 };
3911 return getNode(Opcode, DL, VT, Ops);
3914 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3915 SDValue N1, SDValue N2, SDValue N3,
3916 SDValue N4, SDValue N5) {
3917 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3918 return getNode(Opcode, DL, VT, Ops);
3921 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3922 /// the incoming stack arguments to be loaded from the stack.
3923 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3924 SmallVector<SDValue, 8> ArgChains;
3926 // Include the original chain at the beginning of the list. When this is
3927 // used by target LowerCall hooks, this helps legalize find the
3928 // CALLSEQ_BEGIN node.
3929 ArgChains.push_back(Chain);
3931 // Add a chain value for each stack argument.
3932 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3933 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3934 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3935 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3936 if (FI->getIndex() < 0)
3937 ArgChains.push_back(SDValue(L, 1));
3939 // Build a tokenfactor for all the chains.
3940 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3943 /// getMemsetValue - Vectorized representation of the memset value
3945 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3947 assert(Value.getOpcode() != ISD::UNDEF);
3949 unsigned NumBits = VT.getScalarType().getSizeInBits();
3950 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3951 assert(C->getAPIntValue().getBitWidth() == 8);
3952 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3954 return DAG.getConstant(Val, dl, VT);
3955 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3959 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3960 EVT IntVT = VT.getScalarType();
3961 if (!IntVT.isInteger())
3962 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3964 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3966 // Use a multiplication with 0x010101... to extend the input to the
3968 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3969 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3970 DAG.getConstant(Magic, dl, IntVT));
3973 if (VT != Value.getValueType() && !VT.isInteger())
3974 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3975 if (VT != Value.getValueType()) {
3976 assert(VT.getVectorElementType() == Value.getValueType() &&
3977 "value type should be one vector element here");
3978 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3979 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3985 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3986 /// used when a memcpy is turned into a memset when the source is a constant
3988 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3989 const TargetLowering &TLI, StringRef Str) {
3990 // Handle vector with all elements zero.
3993 return DAG.getConstant(0, dl, VT);
3994 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3995 return DAG.getConstantFP(0.0, dl, VT);
3996 else if (VT.isVector()) {
3997 unsigned NumElts = VT.getVectorNumElements();
3998 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3999 return DAG.getNode(ISD::BITCAST, dl, VT,
4000 DAG.getConstant(0, dl,
4001 EVT::getVectorVT(*DAG.getContext(),
4004 llvm_unreachable("Expected type!");
4007 assert(!VT.isVector() && "Can't handle vector type here!");
4008 unsigned NumVTBits = VT.getSizeInBits();
4009 unsigned NumVTBytes = NumVTBits / 8;
4010 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4012 APInt Val(NumVTBits, 0);
4013 if (DAG.getDataLayout().isLittleEndian()) {
4014 for (unsigned i = 0; i != NumBytes; ++i)
4015 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4017 for (unsigned i = 0; i != NumBytes; ++i)
4018 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4021 // If the "cost" of materializing the integer immediate is less than the cost
4022 // of a load, then it is cost effective to turn the load into the immediate.
4023 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4024 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4025 return DAG.getConstant(Val, dl, VT);
4026 return SDValue(nullptr, 0);
4029 /// getMemBasePlusOffset - Returns base and offset node for the
4031 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4032 SelectionDAG &DAG) {
4033 EVT VT = Base.getValueType();
4034 return DAG.getNode(ISD::ADD, dl,
4035 VT, Base, DAG.getConstant(Offset, dl, VT));
4038 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4040 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4041 unsigned SrcDelta = 0;
4042 GlobalAddressSDNode *G = nullptr;
4043 if (Src.getOpcode() == ISD::GlobalAddress)
4044 G = cast<GlobalAddressSDNode>(Src);
4045 else if (Src.getOpcode() == ISD::ADD &&
4046 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4047 Src.getOperand(1).getOpcode() == ISD::Constant) {
4048 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4049 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4054 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4057 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4058 /// Return true if the number of memory ops is below the threshold (Limit).
4059 /// It returns the types of the sequence of memory ops to perform
4060 /// memset / memcpy by reference.
4061 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4062 unsigned Limit, uint64_t Size,
4063 unsigned DstAlign, unsigned SrcAlign,
4069 const TargetLowering &TLI) {
4070 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4071 "Expecting memcpy / memset source to meet alignment requirement!");
4072 // If 'SrcAlign' is zero, that means the memory operation does not need to
4073 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4074 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4075 // is the specified alignment of the memory operation. If it is zero, that
4076 // means it's possible to change the alignment of the destination.
4077 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4078 // not need to be loaded.
4079 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4080 IsMemset, ZeroMemset, MemcpyStrSrc,
4081 DAG.getMachineFunction());
4083 if (VT == MVT::Other) {
4085 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4086 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4087 VT = TLI.getPointerTy(DAG.getDataLayout());
4089 switch (DstAlign & 7) {
4090 case 0: VT = MVT::i64; break;
4091 case 4: VT = MVT::i32; break;
4092 case 2: VT = MVT::i16; break;
4093 default: VT = MVT::i8; break;
4098 while (!TLI.isTypeLegal(LVT))
4099 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4100 assert(LVT.isInteger());
4106 unsigned NumMemOps = 0;
4108 unsigned VTSize = VT.getSizeInBits() / 8;
4109 while (VTSize > Size) {
4110 // For now, only use non-vector load / store's for the left-over pieces.
4115 if (VT.isVector() || VT.isFloatingPoint()) {
4116 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4117 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4118 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4120 else if (NewVT == MVT::i64 &&
4121 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4122 TLI.isSafeMemOpType(MVT::f64)) {
4123 // i64 is usually not legal on 32-bit targets, but f64 may be.
4131 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4132 if (NewVT == MVT::i8)
4134 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4136 NewVTSize = NewVT.getSizeInBits() / 8;
4138 // If the new VT cannot cover all of the remaining bits, then consider
4139 // issuing a (or a pair of) unaligned and overlapping load / store.
4140 // FIXME: Only does this for 64-bit or more since we don't have proper
4141 // cost model for unaligned load / store.
4144 if (NumMemOps && AllowOverlap &&
4145 VTSize >= 8 && NewVTSize < Size &&
4146 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4154 if (++NumMemOps > Limit)
4157 MemOps.push_back(VT);
4164 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4165 // On Darwin, -Os means optimize for size without hurting performance, so
4166 // only really optimize for size when -Oz (MinSize) is used.
4167 if (MF.getTarget().getTargetTriple().isOSDarwin())
4168 return MF.getFunction()->optForMinSize();
4169 return MF.getFunction()->optForSize();
4172 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4173 SDValue Chain, SDValue Dst,
4174 SDValue Src, uint64_t Size,
4175 unsigned Align, bool isVol,
4177 MachinePointerInfo DstPtrInfo,
4178 MachinePointerInfo SrcPtrInfo) {
4179 // Turn a memcpy of undef to nop.
4180 if (Src.getOpcode() == ISD::UNDEF)
4183 // Expand memcpy to a series of load and store ops if the size operand falls
4184 // below a certain threshold.
4185 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4186 // rather than maybe a humongous number of loads and stores.
4187 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4188 std::vector<EVT> MemOps;
4189 bool DstAlignCanChange = false;
4190 MachineFunction &MF = DAG.getMachineFunction();
4191 MachineFrameInfo *MFI = MF.getFrameInfo();
4192 bool OptSize = shouldLowerMemFuncForSize(MF);
4193 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4194 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4195 DstAlignCanChange = true;
4196 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4197 if (Align > SrcAlign)
4200 bool CopyFromStr = isMemSrcFromString(Src, Str);
4201 bool isZeroStr = CopyFromStr && Str.empty();
4202 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4204 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4205 (DstAlignCanChange ? 0 : Align),
4206 (isZeroStr ? 0 : SrcAlign),
4207 false, false, CopyFromStr, true, DAG, TLI))
4210 if (DstAlignCanChange) {
4211 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4212 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4214 // Don't promote to an alignment that would require dynamic stack
4216 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4217 if (!TRI->needsStackRealignment(MF))
4218 while (NewAlign > Align &&
4219 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4222 if (NewAlign > Align) {
4223 // Give the stack frame object a larger alignment if needed.
4224 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4225 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4230 SmallVector<SDValue, 8> OutChains;
4231 unsigned NumMemOps = MemOps.size();
4232 uint64_t SrcOff = 0, DstOff = 0;
4233 for (unsigned i = 0; i != NumMemOps; ++i) {
4235 unsigned VTSize = VT.getSizeInBits() / 8;
4236 SDValue Value, Store;
4238 if (VTSize > Size) {
4239 // Issuing an unaligned load / store pair that overlaps with the previous
4240 // pair. Adjust the offset accordingly.
4241 assert(i == NumMemOps-1 && i != 0);
4242 SrcOff -= VTSize - Size;
4243 DstOff -= VTSize - Size;
4247 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4248 // It's unlikely a store of a vector immediate can be done in a single
4249 // instruction. It would require a load from a constantpool first.
4250 // We only handle zero vectors here.
4251 // FIXME: Handle other cases where store of vector immediate is done in
4252 // a single instruction.
4253 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4254 if (Value.getNode())
4255 Store = DAG.getStore(Chain, dl, Value,
4256 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4257 DstPtrInfo.getWithOffset(DstOff), isVol,
4261 if (!Store.getNode()) {
4262 // The type might not be legal for the target. This should only happen
4263 // if the type is smaller than a legal type, as on PPC, so the right
4264 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4265 // to Load/Store if NVT==VT.
4266 // FIXME does the case above also need this?
4267 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4268 assert(NVT.bitsGE(VT));
4269 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4270 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4271 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4272 false, MinAlign(SrcAlign, SrcOff));
4273 Store = DAG.getTruncStore(Chain, dl, Value,
4274 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4275 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4278 OutChains.push_back(Store);
4284 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4287 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4288 SDValue Chain, SDValue Dst,
4289 SDValue Src, uint64_t Size,
4290 unsigned Align, bool isVol,
4292 MachinePointerInfo DstPtrInfo,
4293 MachinePointerInfo SrcPtrInfo) {
4294 // Turn a memmove of undef to nop.
4295 if (Src.getOpcode() == ISD::UNDEF)
4298 // Expand memmove to a series of load and store ops if the size operand falls
4299 // below a certain threshold.
4300 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4301 std::vector<EVT> MemOps;
4302 bool DstAlignCanChange = false;
4303 MachineFunction &MF = DAG.getMachineFunction();
4304 MachineFrameInfo *MFI = MF.getFrameInfo();
4305 bool OptSize = shouldLowerMemFuncForSize(MF);
4306 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4307 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4308 DstAlignCanChange = true;
4309 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4310 if (Align > SrcAlign)
4312 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4314 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4315 (DstAlignCanChange ? 0 : Align), SrcAlign,
4316 false, false, false, false, DAG, TLI))
4319 if (DstAlignCanChange) {
4320 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4321 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4322 if (NewAlign > Align) {
4323 // Give the stack frame object a larger alignment if needed.
4324 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4325 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4330 uint64_t SrcOff = 0, DstOff = 0;
4331 SmallVector<SDValue, 8> LoadValues;
4332 SmallVector<SDValue, 8> LoadChains;
4333 SmallVector<SDValue, 8> OutChains;
4334 unsigned NumMemOps = MemOps.size();
4335 for (unsigned i = 0; i < NumMemOps; i++) {
4337 unsigned VTSize = VT.getSizeInBits() / 8;
4340 Value = DAG.getLoad(VT, dl, Chain,
4341 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4342 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4343 false, false, SrcAlign);
4344 LoadValues.push_back(Value);
4345 LoadChains.push_back(Value.getValue(1));
4348 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4350 for (unsigned i = 0; i < NumMemOps; i++) {
4352 unsigned VTSize = VT.getSizeInBits() / 8;
4355 Store = DAG.getStore(Chain, dl, LoadValues[i],
4356 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4357 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4358 OutChains.push_back(Store);
4362 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4365 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4368 /// \param DAG Selection DAG where lowered code is placed.
4369 /// \param dl Link to corresponding IR location.
4370 /// \param Chain Control flow dependency.
4371 /// \param Dst Pointer to destination memory location.
4372 /// \param Src Value of byte to write into the memory.
4373 /// \param Size Number of bytes to write.
4374 /// \param Align Alignment of the destination in bytes.
4375 /// \param isVol True if destination is volatile.
4376 /// \param DstPtrInfo IR information on the memory pointer.
4377 /// \returns New head in the control flow, if lowering was successful, empty
4378 /// SDValue otherwise.
4380 /// The function tries to replace 'llvm.memset' intrinsic with several store
4381 /// operations and value calculation code. This is usually profitable for small
4383 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4384 SDValue Chain, SDValue Dst,
4385 SDValue Src, uint64_t Size,
4386 unsigned Align, bool isVol,
4387 MachinePointerInfo DstPtrInfo) {
4388 // Turn a memset of undef to nop.
4389 if (Src.getOpcode() == ISD::UNDEF)
4392 // Expand memset to a series of load/store ops if the size operand
4393 // falls below a certain threshold.
4394 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4395 std::vector<EVT> MemOps;
4396 bool DstAlignCanChange = false;
4397 MachineFunction &MF = DAG.getMachineFunction();
4398 MachineFrameInfo *MFI = MF.getFrameInfo();
4399 bool OptSize = shouldLowerMemFuncForSize(MF);
4400 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4401 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4402 DstAlignCanChange = true;
4404 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4405 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4406 Size, (DstAlignCanChange ? 0 : Align), 0,
4407 true, IsZeroVal, false, true, DAG, TLI))
4410 if (DstAlignCanChange) {
4411 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4412 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4413 if (NewAlign > Align) {
4414 // Give the stack frame object a larger alignment if needed.
4415 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4416 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4421 SmallVector<SDValue, 8> OutChains;
4422 uint64_t DstOff = 0;
4423 unsigned NumMemOps = MemOps.size();
4425 // Find the largest store and generate the bit pattern for it.
4426 EVT LargestVT = MemOps[0];
4427 for (unsigned i = 1; i < NumMemOps; i++)
4428 if (MemOps[i].bitsGT(LargestVT))
4429 LargestVT = MemOps[i];
4430 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4432 for (unsigned i = 0; i < NumMemOps; i++) {
4434 unsigned VTSize = VT.getSizeInBits() / 8;
4435 if (VTSize > Size) {
4436 // Issuing an unaligned load / store pair that overlaps with the previous
4437 // pair. Adjust the offset accordingly.
4438 assert(i == NumMemOps-1 && i != 0);
4439 DstOff -= VTSize - Size;
4442 // If this store is smaller than the largest store see whether we can get
4443 // the smaller value for free with a truncate.
4444 SDValue Value = MemSetValue;
4445 if (VT.bitsLT(LargestVT)) {
4446 if (!LargestVT.isVector() && !VT.isVector() &&
4447 TLI.isTruncateFree(LargestVT, VT))
4448 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4450 Value = getMemsetValue(Src, VT, DAG, dl);
4452 assert(Value.getValueType() == VT && "Value with wrong type.");
4453 SDValue Store = DAG.getStore(Chain, dl, Value,
4454 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4455 DstPtrInfo.getWithOffset(DstOff),
4456 isVol, false, Align);
4457 OutChains.push_back(Store);
4458 DstOff += VT.getSizeInBits() / 8;
4462 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4465 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4466 SDValue Src, SDValue Size,
4467 unsigned Align, bool isVol, bool AlwaysInline,
4468 bool isTailCall, MachinePointerInfo DstPtrInfo,
4469 MachinePointerInfo SrcPtrInfo) {
4470 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4472 // Check to see if we should lower the memcpy to loads and stores first.
4473 // For cases within the target-specified limits, this is the best choice.
4474 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4476 // Memcpy with size zero? Just return the original chain.
4477 if (ConstantSize->isNullValue())
4480 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4481 ConstantSize->getZExtValue(),Align,
4482 isVol, false, DstPtrInfo, SrcPtrInfo);
4483 if (Result.getNode())
4487 // Then check to see if we should lower the memcpy with target-specific
4488 // code. If the target chooses to do this, this is the next best.
4490 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4491 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4492 DstPtrInfo, SrcPtrInfo);
4493 if (Result.getNode())
4497 // If we really need inline code and the target declined to provide it,
4498 // use a (potentially long) sequence of loads and stores.
4500 assert(ConstantSize && "AlwaysInline requires a constant size!");
4501 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4502 ConstantSize->getZExtValue(), Align, isVol,
4503 true, DstPtrInfo, SrcPtrInfo);
4506 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4507 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4508 // respect volatile, so they may do things like read or write memory
4509 // beyond the given memory regions. But fixing this isn't easy, and most
4510 // people don't care.
4512 // Emit a library call.
4513 TargetLowering::ArgListTy Args;
4514 TargetLowering::ArgListEntry Entry;
4515 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4516 Entry.Node = Dst; Args.push_back(Entry);
4517 Entry.Node = Src; Args.push_back(Entry);
4518 Entry.Node = Size; Args.push_back(Entry);
4519 // FIXME: pass in SDLoc
4520 TargetLowering::CallLoweringInfo CLI(*this);
4523 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4524 Type::getVoidTy(*getContext()),
4525 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4526 TLI->getPointerTy(getDataLayout())),
4529 .setTailCall(isTailCall);
4531 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4532 return CallResult.second;
4535 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4536 SDValue Src, SDValue Size,
4537 unsigned Align, bool isVol, bool isTailCall,
4538 MachinePointerInfo DstPtrInfo,
4539 MachinePointerInfo SrcPtrInfo) {
4540 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4542 // Check to see if we should lower the memmove to loads and stores first.
4543 // For cases within the target-specified limits, this is the best choice.
4544 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4546 // Memmove with size zero? Just return the original chain.
4547 if (ConstantSize->isNullValue())
4551 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4552 ConstantSize->getZExtValue(), Align, isVol,
4553 false, DstPtrInfo, SrcPtrInfo);
4554 if (Result.getNode())
4558 // Then check to see if we should lower the memmove with target-specific
4559 // code. If the target chooses to do this, this is the next best.
4561 SDValue Result = TSI->EmitTargetCodeForMemmove(
4562 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4563 if (Result.getNode())
4567 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4568 // not be safe. See memcpy above for more details.
4570 // Emit a library call.
4571 TargetLowering::ArgListTy Args;
4572 TargetLowering::ArgListEntry Entry;
4573 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4574 Entry.Node = Dst; Args.push_back(Entry);
4575 Entry.Node = Src; Args.push_back(Entry);
4576 Entry.Node = Size; Args.push_back(Entry);
4577 // FIXME: pass in SDLoc
4578 TargetLowering::CallLoweringInfo CLI(*this);
4581 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4582 Type::getVoidTy(*getContext()),
4583 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4584 TLI->getPointerTy(getDataLayout())),
4587 .setTailCall(isTailCall);
4589 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4590 return CallResult.second;
4593 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4594 SDValue Src, SDValue Size,
4595 unsigned Align, bool isVol, bool isTailCall,
4596 MachinePointerInfo DstPtrInfo) {
4597 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4599 // Check to see if we should lower the memset to stores first.
4600 // For cases within the target-specified limits, this is the best choice.
4601 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4603 // Memset with size zero? Just return the original chain.
4604 if (ConstantSize->isNullValue())
4608 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4609 Align, isVol, DstPtrInfo);
4611 if (Result.getNode())
4615 // Then check to see if we should lower the memset with target-specific
4616 // code. If the target chooses to do this, this is the next best.
4618 SDValue Result = TSI->EmitTargetCodeForMemset(
4619 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4620 if (Result.getNode())
4624 // Emit a library call.
4625 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4626 TargetLowering::ArgListTy Args;
4627 TargetLowering::ArgListEntry Entry;
4628 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4629 Args.push_back(Entry);
4631 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4632 Args.push_back(Entry);
4634 Entry.Ty = IntPtrTy;
4635 Args.push_back(Entry);
4637 // FIXME: pass in SDLoc
4638 TargetLowering::CallLoweringInfo CLI(*this);
4641 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4642 Type::getVoidTy(*getContext()),
4643 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4644 TLI->getPointerTy(getDataLayout())),
4647 .setTailCall(isTailCall);
4649 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4650 return CallResult.second;
4653 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4654 SDVTList VTList, ArrayRef<SDValue> Ops,
4655 MachineMemOperand *MMO,
4656 AtomicOrdering SuccessOrdering,
4657 AtomicOrdering FailureOrdering,
4658 SynchronizationScope SynchScope) {
4659 FoldingSetNodeID ID;
4660 ID.AddInteger(MemVT.getRawBits());
4661 AddNodeIDNode(ID, Opcode, VTList, Ops);
4662 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4664 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4665 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4666 return SDValue(E, 0);
4669 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4670 // SDNode doesn't have access to it. This memory will be "leaked" when
4671 // the node is deallocated, but recovered when the allocator is released.
4672 // If the number of operands is less than 5 we use AtomicSDNode's internal
4674 unsigned NumOps = Ops.size();
4675 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4678 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4679 dl.getDebugLoc(), VTList, MemVT,
4680 Ops.data(), DynOps, NumOps, MMO,
4681 SuccessOrdering, FailureOrdering,
4683 CSEMap.InsertNode(N, IP);
4685 return SDValue(N, 0);
4688 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4689 SDVTList VTList, ArrayRef<SDValue> Ops,
4690 MachineMemOperand *MMO,
4691 AtomicOrdering Ordering,
4692 SynchronizationScope SynchScope) {
4693 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4694 Ordering, SynchScope);
4697 SDValue SelectionDAG::getAtomicCmpSwap(
4698 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4699 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4700 unsigned Alignment, AtomicOrdering SuccessOrdering,
4701 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4702 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4703 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4704 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4706 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4707 Alignment = getEVTAlignment(MemVT);
4709 MachineFunction &MF = getMachineFunction();
4711 // FIXME: Volatile isn't really correct; we should keep track of atomic
4712 // orderings in the memoperand.
4713 unsigned Flags = MachineMemOperand::MOVolatile;
4714 Flags |= MachineMemOperand::MOLoad;
4715 Flags |= MachineMemOperand::MOStore;
4717 MachineMemOperand *MMO =
4718 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4720 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4721 SuccessOrdering, FailureOrdering, SynchScope);
4724 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4725 SDVTList VTs, SDValue Chain, SDValue Ptr,
4726 SDValue Cmp, SDValue Swp,
4727 MachineMemOperand *MMO,
4728 AtomicOrdering SuccessOrdering,
4729 AtomicOrdering FailureOrdering,
4730 SynchronizationScope SynchScope) {
4731 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4732 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4733 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4735 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4736 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4737 SuccessOrdering, FailureOrdering, SynchScope);
4740 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4742 SDValue Ptr, SDValue Val,
4743 const Value* PtrVal,
4745 AtomicOrdering Ordering,
4746 SynchronizationScope SynchScope) {
4747 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4748 Alignment = getEVTAlignment(MemVT);
4750 MachineFunction &MF = getMachineFunction();
4751 // An atomic store does not load. An atomic load does not store.
4752 // (An atomicrmw obviously both loads and stores.)
4753 // For now, atomics are considered to be volatile always, and they are
4755 // FIXME: Volatile isn't really correct; we should keep track of atomic
4756 // orderings in the memoperand.
4757 unsigned Flags = MachineMemOperand::MOVolatile;
4758 if (Opcode != ISD::ATOMIC_STORE)
4759 Flags |= MachineMemOperand::MOLoad;
4760 if (Opcode != ISD::ATOMIC_LOAD)
4761 Flags |= MachineMemOperand::MOStore;
4763 MachineMemOperand *MMO =
4764 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4765 MemVT.getStoreSize(), Alignment);
4767 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4768 Ordering, SynchScope);
4771 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4773 SDValue Ptr, SDValue Val,
4774 MachineMemOperand *MMO,
4775 AtomicOrdering Ordering,
4776 SynchronizationScope SynchScope) {
4777 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4778 Opcode == ISD::ATOMIC_LOAD_SUB ||
4779 Opcode == ISD::ATOMIC_LOAD_AND ||
4780 Opcode == ISD::ATOMIC_LOAD_OR ||
4781 Opcode == ISD::ATOMIC_LOAD_XOR ||
4782 Opcode == ISD::ATOMIC_LOAD_NAND ||
4783 Opcode == ISD::ATOMIC_LOAD_MIN ||
4784 Opcode == ISD::ATOMIC_LOAD_MAX ||
4785 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4786 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4787 Opcode == ISD::ATOMIC_SWAP ||
4788 Opcode == ISD::ATOMIC_STORE) &&
4789 "Invalid Atomic Op");
4791 EVT VT = Val.getValueType();
4793 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4794 getVTList(VT, MVT::Other);
4795 SDValue Ops[] = {Chain, Ptr, Val};
4796 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4799 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4800 EVT VT, SDValue Chain,
4802 MachineMemOperand *MMO,
4803 AtomicOrdering Ordering,
4804 SynchronizationScope SynchScope) {
4805 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4807 SDVTList VTs = getVTList(VT, MVT::Other);
4808 SDValue Ops[] = {Chain, Ptr};
4809 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4812 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4813 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4814 if (Ops.size() == 1)
4817 SmallVector<EVT, 4> VTs;
4818 VTs.reserve(Ops.size());
4819 for (unsigned i = 0; i < Ops.size(); ++i)
4820 VTs.push_back(Ops[i].getValueType());
4821 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4825 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4826 ArrayRef<SDValue> Ops,
4827 EVT MemVT, MachinePointerInfo PtrInfo,
4828 unsigned Align, bool Vol,
4829 bool ReadMem, bool WriteMem, unsigned Size) {
4830 if (Align == 0) // Ensure that codegen never sees alignment 0
4831 Align = getEVTAlignment(MemVT);
4833 MachineFunction &MF = getMachineFunction();
4836 Flags |= MachineMemOperand::MOStore;
4838 Flags |= MachineMemOperand::MOLoad;
4840 Flags |= MachineMemOperand::MOVolatile;
4842 Size = MemVT.getStoreSize();
4843 MachineMemOperand *MMO =
4844 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4846 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4850 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4851 ArrayRef<SDValue> Ops, EVT MemVT,
4852 MachineMemOperand *MMO) {
4853 assert((Opcode == ISD::INTRINSIC_VOID ||
4854 Opcode == ISD::INTRINSIC_W_CHAIN ||
4855 Opcode == ISD::PREFETCH ||
4856 Opcode == ISD::LIFETIME_START ||
4857 Opcode == ISD::LIFETIME_END ||
4858 (Opcode <= INT_MAX &&
4859 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4860 "Opcode is not a memory-accessing opcode!");
4862 // Memoize the node unless it returns a flag.
4863 MemIntrinsicSDNode *N;
4864 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4865 FoldingSetNodeID ID;
4866 AddNodeIDNode(ID, Opcode, VTList, Ops);
4867 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4869 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4870 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4871 return SDValue(E, 0);
4874 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4875 dl.getDebugLoc(), VTList, Ops,
4877 CSEMap.InsertNode(N, IP);
4879 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4880 dl.getDebugLoc(), VTList, Ops,
4884 return SDValue(N, 0);
4887 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4888 /// MachinePointerInfo record from it. This is particularly useful because the
4889 /// code generator has many cases where it doesn't bother passing in a
4890 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4891 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4892 int64_t Offset = 0) {
4893 // If this is FI+Offset, we can model it.
4894 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4895 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4896 FI->getIndex(), Offset);
4898 // If this is (FI+Offset1)+Offset2, we can model it.
4899 if (Ptr.getOpcode() != ISD::ADD ||
4900 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4901 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4902 return MachinePointerInfo();
4904 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4905 return MachinePointerInfo::getFixedStack(
4906 DAG.getMachineFunction(), FI,
4907 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4910 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4911 /// MachinePointerInfo record from it. This is particularly useful because the
4912 /// code generator has many cases where it doesn't bother passing in a
4913 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4914 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4916 // If the 'Offset' value isn't a constant, we can't handle this.
4917 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4918 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4919 if (OffsetOp.getOpcode() == ISD::UNDEF)
4920 return InferPointerInfo(DAG, Ptr);
4921 return MachinePointerInfo();
4926 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4927 EVT VT, SDLoc dl, SDValue Chain,
4928 SDValue Ptr, SDValue Offset,
4929 MachinePointerInfo PtrInfo, EVT MemVT,
4930 bool isVolatile, bool isNonTemporal, bool isInvariant,
4931 unsigned Alignment, const AAMDNodes &AAInfo,
4932 const MDNode *Ranges) {
4933 assert(Chain.getValueType() == MVT::Other &&
4934 "Invalid chain type");
4935 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4936 Alignment = getEVTAlignment(VT);
4938 unsigned Flags = MachineMemOperand::MOLoad;
4940 Flags |= MachineMemOperand::MOVolatile;
4942 Flags |= MachineMemOperand::MONonTemporal;
4944 Flags |= MachineMemOperand::MOInvariant;
4946 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4948 if (PtrInfo.V.isNull())
4949 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
4951 MachineFunction &MF = getMachineFunction();
4952 MachineMemOperand *MMO =
4953 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4955 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4959 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4960 EVT VT, SDLoc dl, SDValue Chain,
4961 SDValue Ptr, SDValue Offset, EVT MemVT,
4962 MachineMemOperand *MMO) {
4964 ExtType = ISD::NON_EXTLOAD;
4965 } else if (ExtType == ISD::NON_EXTLOAD) {
4966 assert(VT == MemVT && "Non-extending load from different memory type!");
4969 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4970 "Should only be an extending load, not truncating!");
4971 assert(VT.isInteger() == MemVT.isInteger() &&
4972 "Cannot convert from FP to Int or Int -> FP!");
4973 assert(VT.isVector() == MemVT.isVector() &&
4974 "Cannot use an ext load to convert to or from a vector!");
4975 assert((!VT.isVector() ||
4976 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4977 "Cannot use an ext load to change the number of vector elements!");
4980 bool Indexed = AM != ISD::UNINDEXED;
4981 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4982 "Unindexed load with an offset!");
4984 SDVTList VTs = Indexed ?
4985 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4986 SDValue Ops[] = { Chain, Ptr, Offset };
4987 FoldingSetNodeID ID;
4988 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4989 ID.AddInteger(MemVT.getRawBits());
4990 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4991 MMO->isNonTemporal(),
4992 MMO->isInvariant()));
4993 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4995 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4996 cast<LoadSDNode>(E)->refineAlignment(MMO);
4997 return SDValue(E, 0);
4999 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5000 dl.getDebugLoc(), VTs, AM, ExtType,
5002 CSEMap.InsertNode(N, IP);
5004 return SDValue(N, 0);
5007 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5008 SDValue Chain, SDValue Ptr,
5009 MachinePointerInfo PtrInfo,
5010 bool isVolatile, bool isNonTemporal,
5011 bool isInvariant, unsigned Alignment,
5012 const AAMDNodes &AAInfo,
5013 const MDNode *Ranges) {
5014 SDValue Undef = getUNDEF(Ptr.getValueType());
5015 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5016 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5020 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5021 SDValue Chain, SDValue Ptr,
5022 MachineMemOperand *MMO) {
5023 SDValue Undef = getUNDEF(Ptr.getValueType());
5024 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5028 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5029 SDValue Chain, SDValue Ptr,
5030 MachinePointerInfo PtrInfo, EVT MemVT,
5031 bool isVolatile, bool isNonTemporal,
5032 bool isInvariant, unsigned Alignment,
5033 const AAMDNodes &AAInfo) {
5034 SDValue Undef = getUNDEF(Ptr.getValueType());
5035 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5036 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5041 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5042 SDValue Chain, SDValue Ptr, EVT MemVT,
5043 MachineMemOperand *MMO) {
5044 SDValue Undef = getUNDEF(Ptr.getValueType());
5045 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5050 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5051 SDValue Offset, ISD::MemIndexedMode AM) {
5052 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5053 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5054 "Load is already a indexed load!");
5055 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5056 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5057 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5058 false, LD->getAlignment());
5061 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5062 SDValue Ptr, MachinePointerInfo PtrInfo,
5063 bool isVolatile, bool isNonTemporal,
5064 unsigned Alignment, const AAMDNodes &AAInfo) {
5065 assert(Chain.getValueType() == MVT::Other &&
5066 "Invalid chain type");
5067 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5068 Alignment = getEVTAlignment(Val.getValueType());
5070 unsigned Flags = MachineMemOperand::MOStore;
5072 Flags |= MachineMemOperand::MOVolatile;
5074 Flags |= MachineMemOperand::MONonTemporal;
5076 if (PtrInfo.V.isNull())
5077 PtrInfo = InferPointerInfo(*this, Ptr);
5079 MachineFunction &MF = getMachineFunction();
5080 MachineMemOperand *MMO =
5081 MF.getMachineMemOperand(PtrInfo, Flags,
5082 Val.getValueType().getStoreSize(), Alignment,
5085 return getStore(Chain, dl, Val, Ptr, MMO);
5088 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5089 SDValue Ptr, MachineMemOperand *MMO) {
5090 assert(Chain.getValueType() == MVT::Other &&
5091 "Invalid chain type");
5092 EVT VT = Val.getValueType();
5093 SDVTList VTs = getVTList(MVT::Other);
5094 SDValue Undef = getUNDEF(Ptr.getValueType());
5095 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5096 FoldingSetNodeID ID;
5097 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5098 ID.AddInteger(VT.getRawBits());
5099 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5100 MMO->isNonTemporal(), MMO->isInvariant()));
5101 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5103 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5104 cast<StoreSDNode>(E)->refineAlignment(MMO);
5105 return SDValue(E, 0);
5107 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5108 dl.getDebugLoc(), VTs,
5109 ISD::UNINDEXED, false, VT, MMO);
5110 CSEMap.InsertNode(N, IP);
5112 return SDValue(N, 0);
5115 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5116 SDValue Ptr, MachinePointerInfo PtrInfo,
5117 EVT SVT,bool isVolatile, bool isNonTemporal,
5119 const AAMDNodes &AAInfo) {
5120 assert(Chain.getValueType() == MVT::Other &&
5121 "Invalid chain type");
5122 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5123 Alignment = getEVTAlignment(SVT);
5125 unsigned Flags = MachineMemOperand::MOStore;
5127 Flags |= MachineMemOperand::MOVolatile;
5129 Flags |= MachineMemOperand::MONonTemporal;
5131 if (PtrInfo.V.isNull())
5132 PtrInfo = InferPointerInfo(*this, Ptr);
5134 MachineFunction &MF = getMachineFunction();
5135 MachineMemOperand *MMO =
5136 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5139 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5142 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5143 SDValue Ptr, EVT SVT,
5144 MachineMemOperand *MMO) {
5145 EVT VT = Val.getValueType();
5147 assert(Chain.getValueType() == MVT::Other &&
5148 "Invalid chain type");
5150 return getStore(Chain, dl, Val, Ptr, MMO);
5152 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5153 "Should only be a truncating store, not extending!");
5154 assert(VT.isInteger() == SVT.isInteger() &&
5155 "Can't do FP-INT conversion!");
5156 assert(VT.isVector() == SVT.isVector() &&
5157 "Cannot use trunc store to convert to or from a vector!");
5158 assert((!VT.isVector() ||
5159 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5160 "Cannot use trunc store to change the number of vector elements!");
5162 SDVTList VTs = getVTList(MVT::Other);
5163 SDValue Undef = getUNDEF(Ptr.getValueType());
5164 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5165 FoldingSetNodeID ID;
5166 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5167 ID.AddInteger(SVT.getRawBits());
5168 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5169 MMO->isNonTemporal(), MMO->isInvariant()));
5170 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5172 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5173 cast<StoreSDNode>(E)->refineAlignment(MMO);
5174 return SDValue(E, 0);
5176 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5177 dl.getDebugLoc(), VTs,
5178 ISD::UNINDEXED, true, SVT, MMO);
5179 CSEMap.InsertNode(N, IP);
5181 return SDValue(N, 0);
5185 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5186 SDValue Offset, ISD::MemIndexedMode AM) {
5187 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5188 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5189 "Store is already a indexed store!");
5190 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5191 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5192 FoldingSetNodeID ID;
5193 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5194 ID.AddInteger(ST->getMemoryVT().getRawBits());
5195 ID.AddInteger(ST->getRawSubclassData());
5196 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5198 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5199 return SDValue(E, 0);
5201 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5202 dl.getDebugLoc(), VTs, AM,
5203 ST->isTruncatingStore(),
5205 ST->getMemOperand());
5206 CSEMap.InsertNode(N, IP);
5208 return SDValue(N, 0);
5212 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5213 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5214 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5216 SDVTList VTs = getVTList(VT, MVT::Other);
5217 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5218 FoldingSetNodeID ID;
5219 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5220 ID.AddInteger(VT.getRawBits());
5221 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5223 MMO->isNonTemporal(),
5224 MMO->isInvariant()));
5225 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5227 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5228 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5229 return SDValue(E, 0);
5231 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5232 dl.getDebugLoc(), Ops, 4, VTs,
5234 CSEMap.InsertNode(N, IP);
5236 return SDValue(N, 0);
5239 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5240 SDValue Ptr, SDValue Mask, EVT MemVT,
5241 MachineMemOperand *MMO, bool isTrunc) {
5242 assert(Chain.getValueType() == MVT::Other &&
5243 "Invalid chain type");
5244 EVT VT = Val.getValueType();
5245 SDVTList VTs = getVTList(MVT::Other);
5246 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5247 FoldingSetNodeID ID;
5248 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5249 ID.AddInteger(VT.getRawBits());
5250 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5251 MMO->isNonTemporal(), MMO->isInvariant()));
5252 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5254 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5255 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5256 return SDValue(E, 0);
5258 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5259 dl.getDebugLoc(), Ops, 4,
5260 VTs, isTrunc, MemVT, MMO);
5261 CSEMap.InsertNode(N, IP);
5263 return SDValue(N, 0);
5267 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5268 ArrayRef<SDValue> Ops,
5269 MachineMemOperand *MMO) {
5271 FoldingSetNodeID ID;
5272 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5273 ID.AddInteger(VT.getRawBits());
5274 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5276 MMO->isNonTemporal(),
5277 MMO->isInvariant()));
5278 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5280 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5281 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5282 return SDValue(E, 0);
5284 MaskedGatherSDNode *N =
5285 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5287 CSEMap.InsertNode(N, IP);
5289 return SDValue(N, 0);
5292 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5293 ArrayRef<SDValue> Ops,
5294 MachineMemOperand *MMO) {
5295 FoldingSetNodeID ID;
5296 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5297 ID.AddInteger(VT.getRawBits());
5298 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5299 MMO->isNonTemporal(),
5300 MMO->isInvariant()));
5301 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5303 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5304 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5305 return SDValue(E, 0);
5308 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5310 CSEMap.InsertNode(N, IP);
5312 return SDValue(N, 0);
5315 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5316 SDValue Chain, SDValue Ptr,
5319 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5320 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5323 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5324 ArrayRef<SDUse> Ops) {
5325 switch (Ops.size()) {
5326 case 0: return getNode(Opcode, DL, VT);
5327 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5328 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5329 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5333 // Copy from an SDUse array into an SDValue array for use with
5334 // the regular getNode logic.
5335 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5336 return getNode(Opcode, DL, VT, NewOps);
5339 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5340 ArrayRef<SDValue> Ops) {
5341 unsigned NumOps = Ops.size();
5343 case 0: return getNode(Opcode, DL, VT);
5344 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5345 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5346 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5352 case ISD::SELECT_CC: {
5353 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5354 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5355 "LHS and RHS of condition must have same type!");
5356 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5357 "True and False arms of SelectCC must have same type!");
5358 assert(Ops[2].getValueType() == VT &&
5359 "select_cc node must be of same type as true and false value!");
5363 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5364 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5365 "LHS/RHS of comparison should match types!");
5372 SDVTList VTs = getVTList(VT);
5374 if (VT != MVT::Glue) {
5375 FoldingSetNodeID ID;
5376 AddNodeIDNode(ID, Opcode, VTs, Ops);
5379 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5380 return SDValue(E, 0);
5382 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5384 CSEMap.InsertNode(N, IP);
5386 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5391 return SDValue(N, 0);
5394 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5395 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5396 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5399 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5400 ArrayRef<SDValue> Ops) {
5401 if (VTList.NumVTs == 1)
5402 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5406 // FIXME: figure out how to safely handle things like
5407 // int foo(int x) { return 1 << (x & 255); }
5408 // int bar() { return foo(256); }
5409 case ISD::SRA_PARTS:
5410 case ISD::SRL_PARTS:
5411 case ISD::SHL_PARTS:
5412 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5413 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5414 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5415 else if (N3.getOpcode() == ISD::AND)
5416 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5417 // If the and is only masking out bits that cannot effect the shift,
5418 // eliminate the and.
5419 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5420 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5421 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5427 // Memoize the node unless it returns a flag.
5429 unsigned NumOps = Ops.size();
5430 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5431 FoldingSetNodeID ID;
5432 AddNodeIDNode(ID, Opcode, VTList, Ops);
5434 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5435 return SDValue(E, 0);
5438 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5439 DL.getDebugLoc(), VTList, Ops[0]);
5440 } else if (NumOps == 2) {
5441 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5442 DL.getDebugLoc(), VTList, Ops[0],
5444 } else if (NumOps == 3) {
5445 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5446 DL.getDebugLoc(), VTList, Ops[0],
5449 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5452 CSEMap.InsertNode(N, IP);
5455 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5456 DL.getDebugLoc(), VTList, Ops[0]);
5457 } else if (NumOps == 2) {
5458 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5459 DL.getDebugLoc(), VTList, Ops[0],
5461 } else if (NumOps == 3) {
5462 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5463 DL.getDebugLoc(), VTList, Ops[0],
5466 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5471 return SDValue(N, 0);
5474 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5475 return getNode(Opcode, DL, VTList, None);
5478 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5480 SDValue Ops[] = { N1 };
5481 return getNode(Opcode, DL, VTList, Ops);
5484 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5485 SDValue N1, SDValue N2) {
5486 SDValue Ops[] = { N1, N2 };
5487 return getNode(Opcode, DL, VTList, Ops);
5490 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5491 SDValue N1, SDValue N2, SDValue N3) {
5492 SDValue Ops[] = { N1, N2, N3 };
5493 return getNode(Opcode, DL, VTList, Ops);
5496 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5497 SDValue N1, SDValue N2, SDValue N3,
5499 SDValue Ops[] = { N1, N2, N3, N4 };
5500 return getNode(Opcode, DL, VTList, Ops);
5503 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5504 SDValue N1, SDValue N2, SDValue N3,
5505 SDValue N4, SDValue N5) {
5506 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5507 return getNode(Opcode, DL, VTList, Ops);
5510 SDVTList SelectionDAG::getVTList(EVT VT) {
5511 return makeVTList(SDNode::getValueTypeList(VT), 1);
5514 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5515 FoldingSetNodeID ID;
5517 ID.AddInteger(VT1.getRawBits());
5518 ID.AddInteger(VT2.getRawBits());
5521 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5523 EVT *Array = Allocator.Allocate<EVT>(2);
5526 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5527 VTListMap.InsertNode(Result, IP);
5529 return Result->getSDVTList();
5532 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5533 FoldingSetNodeID ID;
5535 ID.AddInteger(VT1.getRawBits());
5536 ID.AddInteger(VT2.getRawBits());
5537 ID.AddInteger(VT3.getRawBits());
5540 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5542 EVT *Array = Allocator.Allocate<EVT>(3);
5546 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5547 VTListMap.InsertNode(Result, IP);
5549 return Result->getSDVTList();
5552 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5553 FoldingSetNodeID ID;
5555 ID.AddInteger(VT1.getRawBits());
5556 ID.AddInteger(VT2.getRawBits());
5557 ID.AddInteger(VT3.getRawBits());
5558 ID.AddInteger(VT4.getRawBits());
5561 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5563 EVT *Array = Allocator.Allocate<EVT>(4);
5568 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5569 VTListMap.InsertNode(Result, IP);
5571 return Result->getSDVTList();
5574 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5575 unsigned NumVTs = VTs.size();
5576 FoldingSetNodeID ID;
5577 ID.AddInteger(NumVTs);
5578 for (unsigned index = 0; index < NumVTs; index++) {
5579 ID.AddInteger(VTs[index].getRawBits());
5583 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5585 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5586 std::copy(VTs.begin(), VTs.end(), Array);
5587 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5588 VTListMap.InsertNode(Result, IP);
5590 return Result->getSDVTList();
5594 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5595 /// specified operands. If the resultant node already exists in the DAG,
5596 /// this does not modify the specified node, instead it returns the node that
5597 /// already exists. If the resultant node does not exist in the DAG, the
5598 /// input node is returned. As a degenerate case, if you specify the same
5599 /// input operands as the node already has, the input node is returned.
5600 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5601 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5603 // Check to see if there is no change.
5604 if (Op == N->getOperand(0)) return N;
5606 // See if the modified node already exists.
5607 void *InsertPos = nullptr;
5608 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5611 // Nope it doesn't. Remove the node from its current place in the maps.
5613 if (!RemoveNodeFromCSEMaps(N))
5614 InsertPos = nullptr;
5616 // Now we update the operands.
5617 N->OperandList[0].set(Op);
5619 // If this gets put into a CSE map, add it.
5620 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5624 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5625 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5627 // Check to see if there is no change.
5628 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5629 return N; // No operands changed, just return the input node.
5631 // See if the modified node already exists.
5632 void *InsertPos = nullptr;
5633 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5636 // Nope it doesn't. Remove the node from its current place in the maps.
5638 if (!RemoveNodeFromCSEMaps(N))
5639 InsertPos = nullptr;
5641 // Now we update the operands.
5642 if (N->OperandList[0] != Op1)
5643 N->OperandList[0].set(Op1);
5644 if (N->OperandList[1] != Op2)
5645 N->OperandList[1].set(Op2);
5647 // If this gets put into a CSE map, add it.
5648 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5652 SDNode *SelectionDAG::
5653 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5654 SDValue Ops[] = { Op1, Op2, Op3 };
5655 return UpdateNodeOperands(N, Ops);
5658 SDNode *SelectionDAG::
5659 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5660 SDValue Op3, SDValue Op4) {
5661 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5662 return UpdateNodeOperands(N, Ops);
5665 SDNode *SelectionDAG::
5666 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5667 SDValue Op3, SDValue Op4, SDValue Op5) {
5668 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5669 return UpdateNodeOperands(N, Ops);
5672 SDNode *SelectionDAG::
5673 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5674 unsigned NumOps = Ops.size();
5675 assert(N->getNumOperands() == NumOps &&
5676 "Update with wrong number of operands");
5678 // If no operands changed just return the input node.
5679 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5682 // See if the modified node already exists.
5683 void *InsertPos = nullptr;
5684 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5687 // Nope it doesn't. Remove the node from its current place in the maps.
5689 if (!RemoveNodeFromCSEMaps(N))
5690 InsertPos = nullptr;
5692 // Now we update the operands.
5693 for (unsigned i = 0; i != NumOps; ++i)
5694 if (N->OperandList[i] != Ops[i])
5695 N->OperandList[i].set(Ops[i]);
5697 // If this gets put into a CSE map, add it.
5698 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5702 /// DropOperands - Release the operands and set this node to have
5704 void SDNode::DropOperands() {
5705 // Unlike the code in MorphNodeTo that does this, we don't need to
5706 // watch for dead nodes here.
5707 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5713 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5716 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5718 SDVTList VTs = getVTList(VT);
5719 return SelectNodeTo(N, MachineOpc, VTs, None);
5722 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5723 EVT VT, SDValue Op1) {
5724 SDVTList VTs = getVTList(VT);
5725 SDValue Ops[] = { Op1 };
5726 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5729 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5730 EVT VT, SDValue Op1,
5732 SDVTList VTs = getVTList(VT);
5733 SDValue Ops[] = { Op1, Op2 };
5734 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5737 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5738 EVT VT, SDValue Op1,
5739 SDValue Op2, SDValue Op3) {
5740 SDVTList VTs = getVTList(VT);
5741 SDValue Ops[] = { Op1, Op2, Op3 };
5742 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5745 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5746 EVT VT, ArrayRef<SDValue> Ops) {
5747 SDVTList VTs = getVTList(VT);
5748 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5751 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5752 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5753 SDVTList VTs = getVTList(VT1, VT2);
5754 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5757 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5759 SDVTList VTs = getVTList(VT1, VT2);
5760 return SelectNodeTo(N, MachineOpc, VTs, None);
5763 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5764 EVT VT1, EVT VT2, EVT VT3,
5765 ArrayRef<SDValue> Ops) {
5766 SDVTList VTs = getVTList(VT1, VT2, VT3);
5767 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5770 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5771 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5772 ArrayRef<SDValue> Ops) {
5773 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5774 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5777 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5780 SDVTList VTs = getVTList(VT1, VT2);
5781 SDValue Ops[] = { Op1 };
5782 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5785 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5787 SDValue Op1, SDValue Op2) {
5788 SDVTList VTs = getVTList(VT1, VT2);
5789 SDValue Ops[] = { Op1, Op2 };
5790 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5793 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5795 SDValue Op1, SDValue Op2,
5797 SDVTList VTs = getVTList(VT1, VT2);
5798 SDValue Ops[] = { Op1, Op2, Op3 };
5799 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5802 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5803 EVT VT1, EVT VT2, EVT VT3,
5804 SDValue Op1, SDValue Op2,
5806 SDVTList VTs = getVTList(VT1, VT2, VT3);
5807 SDValue Ops[] = { Op1, Op2, Op3 };
5808 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5811 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5812 SDVTList VTs,ArrayRef<SDValue> Ops) {
5813 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5814 // Reset the NodeID to -1.
5819 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5820 /// the line number information on the merged node since it is not possible to
5821 /// preserve the information that operation is associated with multiple lines.
5822 /// This will make the debugger working better at -O0, were there is a higher
5823 /// probability having other instructions associated with that line.
5825 /// For IROrder, we keep the smaller of the two
5826 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5827 DebugLoc NLoc = N->getDebugLoc();
5828 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5829 N->setDebugLoc(DebugLoc());
5831 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5832 N->setIROrder(Order);
5836 /// MorphNodeTo - This *mutates* the specified node to have the specified
5837 /// return type, opcode, and operands.
5839 /// Note that MorphNodeTo returns the resultant node. If there is already a
5840 /// node of the specified opcode and operands, it returns that node instead of
5841 /// the current one. Note that the SDLoc need not be the same.
5843 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5844 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5845 /// node, and because it doesn't require CSE recalculation for any of
5846 /// the node's users.
5848 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5849 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5850 /// the legalizer which maintain worklists that would need to be updated when
5851 /// deleting things.
5852 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5853 SDVTList VTs, ArrayRef<SDValue> Ops) {
5854 unsigned NumOps = Ops.size();
5855 // If an identical node already exists, use it.
5857 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5858 FoldingSetNodeID ID;
5859 AddNodeIDNode(ID, Opc, VTs, Ops);
5860 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5861 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5864 if (!RemoveNodeFromCSEMaps(N))
5867 // Start the morphing.
5869 N->ValueList = VTs.VTs;
5870 N->NumValues = VTs.NumVTs;
5872 // Clear the operands list, updating used nodes to remove this from their
5873 // use list. Keep track of any operands that become dead as a result.
5874 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5875 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5877 SDNode *Used = Use.getNode();
5879 if (Used->use_empty())
5880 DeadNodeSet.insert(Used);
5883 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5884 // Initialize the memory references information.
5885 MN->setMemRefs(nullptr, nullptr);
5886 // If NumOps is larger than the # of operands we can have in a
5887 // MachineSDNode, reallocate the operand list.
5888 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5889 if (MN->OperandsNeedDelete)
5890 delete[] MN->OperandList;
5891 if (NumOps > array_lengthof(MN->LocalOperands))
5892 // We're creating a final node that will live unmorphed for the
5893 // remainder of the current SelectionDAG iteration, so we can allocate
5894 // the operands directly out of a pool with no recycling metadata.
5895 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5896 Ops.data(), NumOps);
5898 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5899 MN->OperandsNeedDelete = false;
5901 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5903 // If NumOps is larger than the # of operands we currently have, reallocate
5904 // the operand list.
5905 if (NumOps > N->NumOperands) {
5906 if (N->OperandsNeedDelete)
5907 delete[] N->OperandList;
5908 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5909 N->OperandsNeedDelete = true;
5911 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5914 // Delete any nodes that are still dead after adding the uses for the
5916 if (!DeadNodeSet.empty()) {
5917 SmallVector<SDNode *, 16> DeadNodes;
5918 for (SDNode *N : DeadNodeSet)
5920 DeadNodes.push_back(N);
5921 RemoveDeadNodes(DeadNodes);
5925 CSEMap.InsertNode(N, IP); // Memoize the new node.
5930 /// getMachineNode - These are used for target selectors to create a new node
5931 /// with specified return type(s), MachineInstr opcode, and operands.
5933 /// Note that getMachineNode returns the resultant node. If there is already a
5934 /// node of the specified opcode and operands, it returns that node instead of
5935 /// the current one.
5937 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5938 SDVTList VTs = getVTList(VT);
5939 return getMachineNode(Opcode, dl, VTs, None);
5943 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5944 SDVTList VTs = getVTList(VT);
5945 SDValue Ops[] = { Op1 };
5946 return getMachineNode(Opcode, dl, VTs, Ops);
5950 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5951 SDValue Op1, SDValue Op2) {
5952 SDVTList VTs = getVTList(VT);
5953 SDValue Ops[] = { Op1, Op2 };
5954 return getMachineNode(Opcode, dl, VTs, Ops);
5958 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5959 SDValue Op1, SDValue Op2, SDValue Op3) {
5960 SDVTList VTs = getVTList(VT);
5961 SDValue Ops[] = { Op1, Op2, Op3 };
5962 return getMachineNode(Opcode, dl, VTs, Ops);
5966 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5967 ArrayRef<SDValue> Ops) {
5968 SDVTList VTs = getVTList(VT);
5969 return getMachineNode(Opcode, dl, VTs, Ops);
5973 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5974 SDVTList VTs = getVTList(VT1, VT2);
5975 return getMachineNode(Opcode, dl, VTs, None);
5979 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5980 EVT VT1, EVT VT2, SDValue Op1) {
5981 SDVTList VTs = getVTList(VT1, VT2);
5982 SDValue Ops[] = { Op1 };
5983 return getMachineNode(Opcode, dl, VTs, Ops);
5987 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5988 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5989 SDVTList VTs = getVTList(VT1, VT2);
5990 SDValue Ops[] = { Op1, Op2 };
5991 return getMachineNode(Opcode, dl, VTs, Ops);
5995 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5996 EVT VT1, EVT VT2, SDValue Op1,
5997 SDValue Op2, SDValue Op3) {
5998 SDVTList VTs = getVTList(VT1, VT2);
5999 SDValue Ops[] = { Op1, Op2, Op3 };
6000 return getMachineNode(Opcode, dl, VTs, Ops);
6004 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6006 ArrayRef<SDValue> Ops) {
6007 SDVTList VTs = getVTList(VT1, VT2);
6008 return getMachineNode(Opcode, dl, VTs, Ops);
6012 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6013 EVT VT1, EVT VT2, EVT VT3,
6014 SDValue Op1, SDValue Op2) {
6015 SDVTList VTs = getVTList(VT1, VT2, VT3);
6016 SDValue Ops[] = { Op1, Op2 };
6017 return getMachineNode(Opcode, dl, VTs, Ops);
6021 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6022 EVT VT1, EVT VT2, EVT VT3,
6023 SDValue Op1, SDValue Op2, SDValue Op3) {
6024 SDVTList VTs = getVTList(VT1, VT2, VT3);
6025 SDValue Ops[] = { Op1, Op2, Op3 };
6026 return getMachineNode(Opcode, dl, VTs, Ops);
6030 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6031 EVT VT1, EVT VT2, EVT VT3,
6032 ArrayRef<SDValue> Ops) {
6033 SDVTList VTs = getVTList(VT1, VT2, VT3);
6034 return getMachineNode(Opcode, dl, VTs, Ops);
6038 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6039 EVT VT2, EVT VT3, EVT VT4,
6040 ArrayRef<SDValue> Ops) {
6041 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6042 return getMachineNode(Opcode, dl, VTs, Ops);
6046 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6047 ArrayRef<EVT> ResultTys,
6048 ArrayRef<SDValue> Ops) {
6049 SDVTList VTs = getVTList(ResultTys);
6050 return getMachineNode(Opcode, dl, VTs, Ops);
6054 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6055 ArrayRef<SDValue> OpsArray) {
6056 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6059 const SDValue *Ops = OpsArray.data();
6060 unsigned NumOps = OpsArray.size();
6063 FoldingSetNodeID ID;
6064 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6066 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6067 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6071 // Allocate a new MachineSDNode.
6072 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6073 DL.getDebugLoc(), VTs);
6075 // Initialize the operands list.
6076 if (NumOps > array_lengthof(N->LocalOperands))
6077 // We're creating a final node that will live unmorphed for the
6078 // remainder of the current SelectionDAG iteration, so we can allocate
6079 // the operands directly out of a pool with no recycling metadata.
6080 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6083 N->InitOperands(N->LocalOperands, Ops, NumOps);
6084 N->OperandsNeedDelete = false;
6087 CSEMap.InsertNode(N, IP);
6093 /// getTargetExtractSubreg - A convenience function for creating
6094 /// TargetOpcode::EXTRACT_SUBREG nodes.
6096 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6098 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6099 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6100 VT, Operand, SRIdxVal);
6101 return SDValue(Subreg, 0);
6104 /// getTargetInsertSubreg - A convenience function for creating
6105 /// TargetOpcode::INSERT_SUBREG nodes.
6107 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6108 SDValue Operand, SDValue Subreg) {
6109 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6110 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6111 VT, Operand, Subreg, SRIdxVal);
6112 return SDValue(Result, 0);
6115 /// getNodeIfExists - Get the specified node if it's already available, or
6116 /// else return NULL.
6117 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6118 ArrayRef<SDValue> Ops,
6119 const SDNodeFlags *Flags) {
6120 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6121 FoldingSetNodeID ID;
6122 AddNodeIDNode(ID, Opcode, VTList, Ops);
6123 AddNodeIDFlags(ID, Opcode, Flags);
6125 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6131 /// getDbgValue - Creates a SDDbgValue node.
6134 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6135 unsigned R, bool IsIndirect, uint64_t Off,
6136 DebugLoc DL, unsigned O) {
6137 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6138 "Expected inlined-at fields to agree");
6139 return new (DbgInfo->getAlloc())
6140 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6144 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6145 const Value *C, uint64_t Off,
6146 DebugLoc DL, unsigned O) {
6147 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6148 "Expected inlined-at fields to agree");
6149 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6153 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6154 unsigned FI, uint64_t Off,
6155 DebugLoc DL, unsigned O) {
6156 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6157 "Expected inlined-at fields to agree");
6158 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6163 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6164 /// pointed to by a use iterator is deleted, increment the use iterator
6165 /// so that it doesn't dangle.
6167 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6168 SDNode::use_iterator &UI;
6169 SDNode::use_iterator &UE;
6171 void NodeDeleted(SDNode *N, SDNode *E) override {
6172 // Increment the iterator as needed.
6173 while (UI != UE && N == *UI)
6178 RAUWUpdateListener(SelectionDAG &d,
6179 SDNode::use_iterator &ui,
6180 SDNode::use_iterator &ue)
6181 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6186 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6187 /// This can cause recursive merging of nodes in the DAG.
6189 /// This version assumes From has a single result value.
6191 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6192 SDNode *From = FromN.getNode();
6193 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6194 "Cannot replace with this method!");
6195 assert(From != To.getNode() && "Cannot replace uses of with self");
6197 // Iterate over all the existing uses of From. New uses will be added
6198 // to the beginning of the use list, which we avoid visiting.
6199 // This specifically avoids visiting uses of From that arise while the
6200 // replacement is happening, because any such uses would be the result
6201 // of CSE: If an existing node looks like From after one of its operands
6202 // is replaced by To, we don't want to replace of all its users with To
6203 // too. See PR3018 for more info.
6204 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6205 RAUWUpdateListener Listener(*this, UI, UE);
6209 // This node is about to morph, remove its old self from the CSE maps.
6210 RemoveNodeFromCSEMaps(User);
6212 // A user can appear in a use list multiple times, and when this
6213 // happens the uses are usually next to each other in the list.
6214 // To help reduce the number of CSE recomputations, process all
6215 // the uses of this user that we can find this way.
6217 SDUse &Use = UI.getUse();
6220 } while (UI != UE && *UI == User);
6222 // Now that we have modified User, add it back to the CSE maps. If it
6223 // already exists there, recursively merge the results together.
6224 AddModifiedNodeToCSEMaps(User);
6227 // If we just RAUW'd the root, take note.
6228 if (FromN == getRoot())
6232 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6233 /// This can cause recursive merging of nodes in the DAG.
6235 /// This version assumes that for each value of From, there is a
6236 /// corresponding value in To in the same position with the same type.
6238 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6240 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6241 assert((!From->hasAnyUseOfValue(i) ||
6242 From->getValueType(i) == To->getValueType(i)) &&
6243 "Cannot use this version of ReplaceAllUsesWith!");
6246 // Handle the trivial case.
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();
6268 } while (UI != UE && *UI == User);
6270 // Now that we have modified User, add it back to the CSE maps. If it
6271 // already exists there, recursively merge the results together.
6272 AddModifiedNodeToCSEMaps(User);
6275 // If we just RAUW'd the root, take note.
6276 if (From == getRoot().getNode())
6277 setRoot(SDValue(To, getRoot().getResNo()));
6280 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6281 /// This can cause recursive merging of nodes in the DAG.
6283 /// This version can replace From with any result values. To must match the
6284 /// number and types of values returned by From.
6285 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6286 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6287 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6289 // Iterate over just the existing users of From. See the comments in
6290 // the ReplaceAllUsesWith above.
6291 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6292 RAUWUpdateListener Listener(*this, UI, UE);
6296 // This node is about to morph, remove its old self from the CSE maps.
6297 RemoveNodeFromCSEMaps(User);
6299 // A user can appear in a use list multiple times, and when this
6300 // happens the uses are usually next to each other in the list.
6301 // To help reduce the number of CSE recomputations, process all
6302 // the uses of this user that we can find this way.
6304 SDUse &Use = UI.getUse();
6305 const SDValue &ToOp = To[Use.getResNo()];
6308 } while (UI != UE && *UI == User);
6310 // Now that we have modified User, add it back to the CSE maps. If it
6311 // already exists there, recursively merge the results together.
6312 AddModifiedNodeToCSEMaps(User);
6315 // If we just RAUW'd the root, take note.
6316 if (From == getRoot().getNode())
6317 setRoot(SDValue(To[getRoot().getResNo()]));
6320 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6321 /// uses of other values produced by From.getNode() alone. The Deleted
6322 /// vector is handled the same way as for ReplaceAllUsesWith.
6323 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6324 // Handle the really simple, really trivial case efficiently.
6325 if (From == To) return;
6327 // Handle the simple, trivial, case efficiently.
6328 if (From.getNode()->getNumValues() == 1) {
6329 ReplaceAllUsesWith(From, To);
6333 // Iterate over just the existing users of From. See the comments in
6334 // the ReplaceAllUsesWith above.
6335 SDNode::use_iterator UI = From.getNode()->use_begin(),
6336 UE = From.getNode()->use_end();
6337 RAUWUpdateListener Listener(*this, UI, UE);
6340 bool UserRemovedFromCSEMaps = false;
6342 // A user can appear in a use list multiple times, and when this
6343 // happens the uses are usually next to each other in the list.
6344 // To help reduce the number of CSE recomputations, process all
6345 // the uses of this user that we can find this way.
6347 SDUse &Use = UI.getUse();
6349 // Skip uses of different values from the same node.
6350 if (Use.getResNo() != From.getResNo()) {
6355 // If this node hasn't been modified yet, it's still in the CSE maps,
6356 // so remove its old self from the CSE maps.
6357 if (!UserRemovedFromCSEMaps) {
6358 RemoveNodeFromCSEMaps(User);
6359 UserRemovedFromCSEMaps = true;
6364 } while (UI != UE && *UI == User);
6366 // We are iterating over all uses of the From node, so if a use
6367 // doesn't use the specific value, no changes are made.
6368 if (!UserRemovedFromCSEMaps)
6371 // Now that we have modified User, add it back to the CSE maps. If it
6372 // already exists there, recursively merge the results together.
6373 AddModifiedNodeToCSEMaps(User);
6376 // If we just RAUW'd the root, take note.
6377 if (From == getRoot())
6382 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6383 /// to record information about a use.
6390 /// operator< - Sort Memos by User.
6391 bool operator<(const UseMemo &L, const UseMemo &R) {
6392 return (intptr_t)L.User < (intptr_t)R.User;
6396 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6397 /// uses of other values produced by From.getNode() alone. The same value
6398 /// may appear in both the From and To list. The Deleted vector is
6399 /// handled the same way as for ReplaceAllUsesWith.
6400 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6403 // Handle the simple, trivial case efficiently.
6405 return ReplaceAllUsesOfValueWith(*From, *To);
6407 // Read up all the uses and make records of them. This helps
6408 // processing new uses that are introduced during the
6409 // replacement process.
6410 SmallVector<UseMemo, 4> Uses;
6411 for (unsigned i = 0; i != Num; ++i) {
6412 unsigned FromResNo = From[i].getResNo();
6413 SDNode *FromNode = From[i].getNode();
6414 for (SDNode::use_iterator UI = FromNode->use_begin(),
6415 E = FromNode->use_end(); UI != E; ++UI) {
6416 SDUse &Use = UI.getUse();
6417 if (Use.getResNo() == FromResNo) {
6418 UseMemo Memo = { *UI, i, &Use };
6419 Uses.push_back(Memo);
6424 // Sort the uses, so that all the uses from a given User are together.
6425 std::sort(Uses.begin(), Uses.end());
6427 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6428 UseIndex != UseIndexEnd; ) {
6429 // We know that this user uses some value of From. If it is the right
6430 // value, update it.
6431 SDNode *User = Uses[UseIndex].User;
6433 // This node is about to morph, remove its old self from the CSE maps.
6434 RemoveNodeFromCSEMaps(User);
6436 // The Uses array is sorted, so all the uses for a given User
6437 // are next to each other in the list.
6438 // To help reduce the number of CSE recomputations, process all
6439 // the uses of this user that we can find this way.
6441 unsigned i = Uses[UseIndex].Index;
6442 SDUse &Use = *Uses[UseIndex].Use;
6446 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6448 // Now that we have modified User, add it back to the CSE maps. If it
6449 // already exists there, recursively merge the results together.
6450 AddModifiedNodeToCSEMaps(User);
6454 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6455 /// based on their topological order. It returns the maximum id and a vector
6456 /// of the SDNodes* in assigned order by reference.
6457 unsigned SelectionDAG::AssignTopologicalOrder() {
6459 unsigned DAGSize = 0;
6461 // SortedPos tracks the progress of the algorithm. Nodes before it are
6462 // sorted, nodes after it are unsorted. When the algorithm completes
6463 // it is at the end of the list.
6464 allnodes_iterator SortedPos = allnodes_begin();
6466 // Visit all the nodes. Move nodes with no operands to the front of
6467 // the list immediately. Annotate nodes that do have operands with their
6468 // operand count. Before we do this, the Node Id fields of the nodes
6469 // may contain arbitrary values. After, the Node Id fields for nodes
6470 // before SortedPos will contain the topological sort index, and the
6471 // Node Id fields for nodes At SortedPos and after will contain the
6472 // count of outstanding operands.
6473 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6475 checkForCycles(N, this);
6476 unsigned Degree = N->getNumOperands();
6478 // A node with no uses, add it to the result array immediately.
6479 N->setNodeId(DAGSize++);
6480 allnodes_iterator Q = N;
6482 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6483 assert(SortedPos != AllNodes.end() && "Overran node list");
6486 // Temporarily use the Node Id as scratch space for the degree count.
6487 N->setNodeId(Degree);
6491 // Visit all the nodes. As we iterate, move nodes into sorted order,
6492 // such that by the time the end is reached all nodes will be sorted.
6493 for (SDNode &Node : allnodes()) {
6495 checkForCycles(N, this);
6496 // N is in sorted position, so all its uses have one less operand
6497 // that needs to be sorted.
6498 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6501 unsigned Degree = P->getNodeId();
6502 assert(Degree != 0 && "Invalid node degree");
6505 // All of P's operands are sorted, so P may sorted now.
6506 P->setNodeId(DAGSize++);
6508 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6509 assert(SortedPos != AllNodes.end() && "Overran node list");
6512 // Update P's outstanding operand count.
6513 P->setNodeId(Degree);
6516 if (&Node == SortedPos) {
6518 allnodes_iterator I = N;
6520 dbgs() << "Overran sorted position:\n";
6521 S->dumprFull(this); dbgs() << "\n";
6522 dbgs() << "Checking if this is due to cycles\n";
6523 checkForCycles(this, true);
6525 llvm_unreachable(nullptr);
6529 assert(SortedPos == AllNodes.end() &&
6530 "Topological sort incomplete!");
6531 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6532 "First node in topological sort is not the entry token!");
6533 assert(AllNodes.front().getNodeId() == 0 &&
6534 "First node in topological sort has non-zero id!");
6535 assert(AllNodes.front().getNumOperands() == 0 &&
6536 "First node in topological sort has operands!");
6537 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6538 "Last node in topologic sort has unexpected id!");
6539 assert(AllNodes.back().use_empty() &&
6540 "Last node in topologic sort has users!");
6541 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6545 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6546 /// value is produced by SD.
6547 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6549 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6550 SD->setHasDebugValue(true);
6552 DbgInfo->add(DB, SD, isParameter);
6555 /// TransferDbgValues - Transfer SDDbgValues.
6556 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6557 if (From == To || !From.getNode()->getHasDebugValue())
6559 SDNode *FromNode = From.getNode();
6560 SDNode *ToNode = To.getNode();
6561 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6562 SmallVector<SDDbgValue *, 2> ClonedDVs;
6563 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6565 SDDbgValue *Dbg = *I;
6566 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6568 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6569 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6570 Dbg->getDebugLoc(), Dbg->getOrder());
6571 ClonedDVs.push_back(Clone);
6574 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6575 E = ClonedDVs.end(); I != E; ++I)
6576 AddDbgValue(*I, ToNode, false);
6579 //===----------------------------------------------------------------------===//
6581 //===----------------------------------------------------------------------===//
6583 HandleSDNode::~HandleSDNode() {
6587 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6588 DebugLoc DL, const GlobalValue *GA,
6589 EVT VT, int64_t o, unsigned char TF)
6590 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6594 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6595 SDValue X, unsigned SrcAS,
6597 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6598 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6600 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6601 EVT memvt, MachineMemOperand *mmo)
6602 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6603 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6604 MMO->isNonTemporal(), MMO->isInvariant());
6605 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6606 assert(isNonTemporal() == MMO->isNonTemporal() &&
6607 "Non-temporal encoding error!");
6608 // We check here that the size of the memory operand fits within the size of
6609 // the MMO. This is because the MMO might indicate only a possible address
6610 // range instead of specifying the affected memory addresses precisely.
6611 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6614 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6615 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6616 : SDNode(Opc, Order, dl, VTs, Ops),
6617 MemoryVT(memvt), MMO(mmo) {
6618 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6619 MMO->isNonTemporal(), MMO->isInvariant());
6620 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6621 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6624 /// Profile - Gather unique data for the node.
6626 void SDNode::Profile(FoldingSetNodeID &ID) const {
6627 AddNodeIDNode(ID, this);
6632 std::vector<EVT> VTs;
6635 VTs.reserve(MVT::LAST_VALUETYPE);
6636 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6637 VTs.push_back(MVT((MVT::SimpleValueType)i));
6642 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6643 static ManagedStatic<EVTArray> SimpleVTArray;
6644 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6646 /// getValueTypeList - Return a pointer to the specified value type.
6648 const EVT *SDNode::getValueTypeList(EVT VT) {
6649 if (VT.isExtended()) {
6650 sys::SmartScopedLock<true> Lock(*VTMutex);
6651 return &(*EVTs->insert(VT).first);
6653 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6654 "Value type out of range!");
6655 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6659 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6660 /// indicated value. This method ignores uses of other values defined by this
6662 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6663 assert(Value < getNumValues() && "Bad value!");
6665 // TODO: Only iterate over uses of a given value of the node
6666 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6667 if (UI.getUse().getResNo() == Value) {
6674 // Found exactly the right number of uses?
6679 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6680 /// value. This method ignores uses of other values defined by this operation.
6681 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6682 assert(Value < getNumValues() && "Bad value!");
6684 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6685 if (UI.getUse().getResNo() == Value)
6692 /// isOnlyUserOf - Return true if this node is the only use of N.
6694 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6696 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6707 /// isOperand - Return true if this node is an operand of N.
6709 bool SDValue::isOperandOf(const SDNode *N) const {
6710 for (const SDValue &Op : N->op_values())
6716 bool SDNode::isOperandOf(const SDNode *N) const {
6717 for (const SDValue &Op : N->op_values())
6718 if (this == Op.getNode())
6723 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6724 /// be a chain) reaches the specified operand without crossing any
6725 /// side-effecting instructions on any chain path. In practice, this looks
6726 /// through token factors and non-volatile loads. In order to remain efficient,
6727 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6728 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6729 unsigned Depth) const {
6730 if (*this == Dest) return true;
6732 // Don't search too deeply, we just want to be able to see through
6733 // TokenFactor's etc.
6734 if (Depth == 0) return false;
6736 // If this is a token factor, all inputs to the TF happen in parallel. If any
6737 // of the operands of the TF does not reach dest, then we cannot do the xform.
6738 if (getOpcode() == ISD::TokenFactor) {
6739 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6740 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6745 // Loads don't have side effects, look through them.
6746 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6747 if (!Ld->isVolatile())
6748 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6753 /// hasPredecessor - Return true if N is a predecessor of this node.
6754 /// N is either an operand of this node, or can be reached by recursively
6755 /// traversing up the operands.
6756 /// NOTE: This is an expensive method. Use it carefully.
6757 bool SDNode::hasPredecessor(const SDNode *N) const {
6758 SmallPtrSet<const SDNode *, 32> Visited;
6759 SmallVector<const SDNode *, 16> Worklist;
6760 return hasPredecessorHelper(N, Visited, Worklist);
6764 SDNode::hasPredecessorHelper(const SDNode *N,
6765 SmallPtrSetImpl<const SDNode *> &Visited,
6766 SmallVectorImpl<const SDNode *> &Worklist) const {
6767 if (Visited.empty()) {
6768 Worklist.push_back(this);
6770 // Take a look in the visited set. If we've already encountered this node
6771 // we needn't search further.
6772 if (Visited.count(N))
6776 // Haven't visited N yet. Continue the search.
6777 while (!Worklist.empty()) {
6778 const SDNode *M = Worklist.pop_back_val();
6779 for (const SDValue &OpV : M->op_values()) {
6780 SDNode *Op = OpV.getNode();
6781 if (Visited.insert(Op).second)
6782 Worklist.push_back(Op);
6791 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6792 assert(Num < NumOperands && "Invalid child # of SDNode!");
6793 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6796 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6797 assert(N->getNumValues() == 1 &&
6798 "Can't unroll a vector with multiple results!");
6800 EVT VT = N->getValueType(0);
6801 unsigned NE = VT.getVectorNumElements();
6802 EVT EltVT = VT.getVectorElementType();
6805 SmallVector<SDValue, 8> Scalars;
6806 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6808 // If ResNE is 0, fully unroll the vector op.
6811 else if (NE > ResNE)
6815 for (i= 0; i != NE; ++i) {
6816 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6817 SDValue Operand = N->getOperand(j);
6818 EVT OperandVT = Operand.getValueType();
6819 if (OperandVT.isVector()) {
6820 // A vector operand; extract a single element.
6821 EVT OperandEltVT = OperandVT.getVectorElementType();
6823 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6824 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6826 // A scalar operand; just use it as is.
6827 Operands[j] = Operand;
6831 switch (N->getOpcode()) {
6833 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6836 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6843 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6844 getShiftAmountOperand(Operands[0].getValueType(),
6847 case ISD::SIGN_EXTEND_INREG:
6848 case ISD::FP_ROUND_INREG: {
6849 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6850 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6852 getValueType(ExtVT)));
6857 for (; i < ResNE; ++i)
6858 Scalars.push_back(getUNDEF(EltVT));
6860 return getNode(ISD::BUILD_VECTOR, dl,
6861 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6865 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6866 /// location that is 'Dist' units away from the location that the 'Base' load
6867 /// is loading from.
6868 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6869 unsigned Bytes, int Dist) const {
6870 if (LD->getChain() != Base->getChain())
6872 EVT VT = LD->getValueType(0);
6873 if (VT.getSizeInBits() / 8 != Bytes)
6876 SDValue Loc = LD->getOperand(1);
6877 SDValue BaseLoc = Base->getOperand(1);
6878 if (Loc.getOpcode() == ISD::FrameIndex) {
6879 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6881 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6882 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6883 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6884 int FS = MFI->getObjectSize(FI);
6885 int BFS = MFI->getObjectSize(BFI);
6886 if (FS != BFS || FS != (int)Bytes) return false;
6887 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6891 if (isBaseWithConstantOffset(Loc)) {
6892 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6893 if (Loc.getOperand(0) == BaseLoc) {
6894 // If the base location is a simple address with no offset itself, then
6895 // the second load's first add operand should be the base address.
6896 if (LocOffset == Dist * (int)Bytes)
6898 } else if (isBaseWithConstantOffset(BaseLoc)) {
6899 // The base location itself has an offset, so subtract that value from the
6900 // second load's offset before comparing to distance * size.
6902 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6903 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6904 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6909 const GlobalValue *GV1 = nullptr;
6910 const GlobalValue *GV2 = nullptr;
6911 int64_t Offset1 = 0;
6912 int64_t Offset2 = 0;
6913 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6914 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6915 if (isGA1 && isGA2 && GV1 == GV2)
6916 return Offset1 == (Offset2 + Dist*Bytes);
6921 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6922 /// it cannot be inferred.
6923 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6924 // If this is a GlobalAddress + cst, return the alignment.
6925 const GlobalValue *GV;
6926 int64_t GVOffset = 0;
6927 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6928 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6929 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6930 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6932 unsigned AlignBits = KnownZero.countTrailingOnes();
6933 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6935 return MinAlign(Align, GVOffset);
6938 // If this is a direct reference to a stack slot, use information about the
6939 // stack slot's alignment.
6940 int FrameIdx = 1 << 31;
6941 int64_t FrameOffset = 0;
6942 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6943 FrameIdx = FI->getIndex();
6944 } else if (isBaseWithConstantOffset(Ptr) &&
6945 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6947 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6948 FrameOffset = Ptr.getConstantOperandVal(1);
6951 if (FrameIdx != (1 << 31)) {
6952 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6953 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6961 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6962 /// which is split (or expanded) into two not necessarily identical pieces.
6963 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6964 // Currently all types are split in half.
6966 if (!VT.isVector()) {
6967 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6969 unsigned NumElements = VT.getVectorNumElements();
6970 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6971 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6974 return std::make_pair(LoVT, HiVT);
6977 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6979 std::pair<SDValue, SDValue>
6980 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6982 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6983 N.getValueType().getVectorNumElements() &&
6984 "More vector elements requested than available!");
6986 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6987 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
6988 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6989 getConstant(LoVT.getVectorNumElements(), DL,
6990 TLI->getVectorIdxTy(getDataLayout())));
6991 return std::make_pair(Lo, Hi);
6994 void SelectionDAG::ExtractVectorElements(SDValue Op,
6995 SmallVectorImpl<SDValue> &Args,
6996 unsigned Start, unsigned Count) {
6997 EVT VT = Op.getValueType();
6999 Count = VT.getVectorNumElements();
7001 EVT EltVT = VT.getVectorElementType();
7002 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7004 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7005 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7006 Op, getConstant(i, SL, IdxTy)));
7010 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7011 unsigned GlobalAddressSDNode::getAddressSpace() const {
7012 return getGlobal()->getType()->getAddressSpace();
7016 Type *ConstantPoolSDNode::getType() const {
7017 if (isMachineConstantPoolEntry())
7018 return Val.MachineCPVal->getType();
7019 return Val.ConstVal->getType();
7022 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7024 unsigned &SplatBitSize,
7026 unsigned MinSplatBits,
7027 bool isBigEndian) const {
7028 EVT VT = getValueType(0);
7029 assert(VT.isVector() && "Expected a vector type");
7030 unsigned sz = VT.getSizeInBits();
7031 if (MinSplatBits > sz)
7034 SplatValue = APInt(sz, 0);
7035 SplatUndef = APInt(sz, 0);
7037 // Get the bits. Bits with undefined values (when the corresponding element
7038 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7039 // in SplatValue. If any of the values are not constant, give up and return
7041 unsigned int nOps = getNumOperands();
7042 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7043 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7045 for (unsigned j = 0; j < nOps; ++j) {
7046 unsigned i = isBigEndian ? nOps-1-j : j;
7047 SDValue OpVal = getOperand(i);
7048 unsigned BitPos = j * EltBitSize;
7050 if (OpVal.getOpcode() == ISD::UNDEF)
7051 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7052 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7053 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7054 zextOrTrunc(sz) << BitPos;
7055 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7056 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7061 // The build_vector is all constants or undefs. Find the smallest element
7062 // size that splats the vector.
7064 HasAnyUndefs = (SplatUndef != 0);
7067 unsigned HalfSize = sz / 2;
7068 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7069 APInt LowValue = SplatValue.trunc(HalfSize);
7070 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7071 APInt LowUndef = SplatUndef.trunc(HalfSize);
7073 // If the two halves do not match (ignoring undef bits), stop here.
7074 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7075 MinSplatBits > HalfSize)
7078 SplatValue = HighValue | LowValue;
7079 SplatUndef = HighUndef & LowUndef;
7088 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7089 if (UndefElements) {
7090 UndefElements->clear();
7091 UndefElements->resize(getNumOperands());
7094 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7095 SDValue Op = getOperand(i);
7096 if (Op.getOpcode() == ISD::UNDEF) {
7098 (*UndefElements)[i] = true;
7099 } else if (!Splatted) {
7101 } else if (Splatted != Op) {
7107 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7108 "Can only have a splat without a constant for all undefs.");
7109 return getOperand(0);
7116 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7117 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7121 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7122 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7125 bool BuildVectorSDNode::isConstant() const {
7126 for (const SDValue &Op : op_values()) {
7127 unsigned Opc = Op.getOpcode();
7128 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7134 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7135 // Find the first non-undef value in the shuffle mask.
7137 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7140 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7142 // Make sure all remaining elements are either undef or the same as the first
7144 for (int Idx = Mask[i]; i != e; ++i)
7145 if (Mask[i] >= 0 && Mask[i] != Idx)
7151 static void checkForCyclesHelper(const SDNode *N,
7152 SmallPtrSetImpl<const SDNode*> &Visited,
7153 SmallPtrSetImpl<const SDNode*> &Checked,
7154 const llvm::SelectionDAG *DAG) {
7155 // If this node has already been checked, don't check it again.
7156 if (Checked.count(N))
7159 // If a node has already been visited on this depth-first walk, reject it as
7161 if (!Visited.insert(N).second) {
7162 errs() << "Detected cycle in SelectionDAG\n";
7163 dbgs() << "Offending node:\n";
7164 N->dumprFull(DAG); dbgs() << "\n";
7168 for (const SDValue &Op : N->op_values())
7169 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7176 void llvm::checkForCycles(const llvm::SDNode *N,
7177 const llvm::SelectionDAG *DAG,
7185 assert(N && "Checking nonexistent SDNode");
7186 SmallPtrSet<const SDNode*, 32> visited;
7187 SmallPtrSet<const SDNode*, 32> checked;
7188 checkForCyclesHelper(N, visited, checked, DAG);
7193 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7194 checkForCycles(DAG->getRoot().getNode(), DAG, force);