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 SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1860 const TargetLowering &TLI = getTargetLoweringInfo();
1861 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1862 EVT VT = Node->getValueType(0);
1863 SDValue Tmp1 = Node->getOperand(0);
1864 SDValue Tmp2 = Node->getOperand(1);
1865 unsigned Align = Node->getConstantOperandVal(3);
1867 SDValue VAListLoad =
1868 getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1, Tmp2,
1869 MachinePointerInfo(V), false, false, false, 0);
1870 SDValue VAList = VAListLoad;
1872 if (Align > TLI.getMinStackArgumentAlignment()) {
1873 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1875 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1876 getConstant(Align - 1, dl, VAList.getValueType()));
1878 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1879 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1882 // Increment the pointer, VAList, to the next vaarg
1883 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1884 getConstant(getDataLayout().getTypeAllocSize(
1885 VT.getTypeForEVT(*getContext())),
1886 dl, VAList.getValueType()));
1887 // Store the incremented VAList to the legalized pointer
1888 Tmp1 = getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2,
1889 MachinePointerInfo(V), false, false, 0);
1890 // Load the actual argument out of the pointer VAList
1891 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo(),
1892 false, false, false, 0);
1895 SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1897 const TargetLowering &TLI = getTargetLoweringInfo();
1898 // This defaults to loading a pointer from the input and storing it to the
1899 // output, returning the chain.
1900 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1901 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1902 SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
1903 Node->getOperand(0), Node->getOperand(2),
1904 MachinePointerInfo(VS), false, false, false, 0);
1905 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1906 MachinePointerInfo(VD), false, false, 0);
1909 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1910 /// specified value type.
1911 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1912 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1913 unsigned ByteSize = VT.getStoreSize();
1914 Type *Ty = VT.getTypeForEVT(*getContext());
1915 unsigned StackAlign =
1916 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1918 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1919 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1922 /// CreateStackTemporary - Create a stack temporary suitable for holding
1923 /// either of the specified value types.
1924 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1925 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1926 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1927 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1928 const DataLayout &DL = getDataLayout();
1930 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1932 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1933 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1934 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1937 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1938 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1939 // These setcc operations always fold.
1943 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1945 case ISD::SETTRUE2: {
1946 TargetLowering::BooleanContent Cnt =
1947 TLI->getBooleanContents(N1->getValueType(0));
1949 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1963 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1967 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1968 const APInt &C2 = N2C->getAPIntValue();
1969 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1970 const APInt &C1 = N1C->getAPIntValue();
1973 default: llvm_unreachable("Unknown integer setcc!");
1974 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1975 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1976 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1977 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1978 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1979 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1980 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1981 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1982 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1983 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1987 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1988 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1989 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1992 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1993 return getUNDEF(VT);
1995 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1996 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1997 return getUNDEF(VT);
1999 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
2000 R==APFloat::cmpLessThan, dl, VT);
2001 case ISD::SETLT: if (R==APFloat::cmpUnordered)
2002 return getUNDEF(VT);
2004 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
2005 case ISD::SETGT: if (R==APFloat::cmpUnordered)
2006 return getUNDEF(VT);
2008 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
2009 case ISD::SETLE: if (R==APFloat::cmpUnordered)
2010 return getUNDEF(VT);
2012 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
2013 R==APFloat::cmpEqual, dl, VT);
2014 case ISD::SETGE: if (R==APFloat::cmpUnordered)
2015 return getUNDEF(VT);
2017 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
2018 R==APFloat::cmpEqual, dl, VT);
2019 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
2020 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
2021 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
2022 R==APFloat::cmpEqual, dl, VT);
2023 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
2024 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
2025 R==APFloat::cmpLessThan, dl, VT);
2026 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
2027 R==APFloat::cmpUnordered, dl, VT);
2028 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
2029 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
2032 // Ensure that the constant occurs on the RHS.
2033 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
2034 MVT CompVT = N1.getValueType().getSimpleVT();
2035 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2038 return getSetCC(dl, VT, N2, N1, SwappedCond);
2042 // Could not fold it.
2046 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2047 /// use this predicate to simplify operations downstream.
2048 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2049 // This predicate is not safe for vector operations.
2050 if (Op.getValueType().isVector())
2053 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2054 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2057 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2058 /// this predicate to simplify operations downstream. Mask is known to be zero
2059 /// for bits that V cannot have.
2060 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2061 unsigned Depth) const {
2062 APInt KnownZero, KnownOne;
2063 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2064 return (KnownZero & Mask) == Mask;
2067 /// Determine which bits of Op are known to be either zero or one and return
2068 /// them in the KnownZero/KnownOne bitsets.
2069 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2070 APInt &KnownOne, unsigned Depth) const {
2071 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2073 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2075 return; // Limit search depth.
2077 APInt KnownZero2, KnownOne2;
2079 switch (Op.getOpcode()) {
2081 // We know all of the bits for a constant!
2082 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2083 KnownZero = ~KnownOne;
2086 // If either the LHS or the RHS are Zero, the result is zero.
2087 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2088 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2090 // Output known-1 bits are only known if set in both the LHS & RHS.
2091 KnownOne &= KnownOne2;
2092 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2093 KnownZero |= KnownZero2;
2096 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2097 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2099 // Output known-0 bits are only known if clear in both the LHS & RHS.
2100 KnownZero &= KnownZero2;
2101 // Output known-1 are known to be set if set in either the LHS | RHS.
2102 KnownOne |= KnownOne2;
2105 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2106 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2108 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2109 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2110 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2111 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2112 KnownZero = KnownZeroOut;
2116 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2117 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2119 // If low bits are zero in either operand, output low known-0 bits.
2120 // Also compute a conserative estimate for high known-0 bits.
2121 // More trickiness is possible, but this is sufficient for the
2122 // interesting case of alignment computation.
2123 KnownOne.clearAllBits();
2124 unsigned TrailZ = KnownZero.countTrailingOnes() +
2125 KnownZero2.countTrailingOnes();
2126 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2127 KnownZero2.countLeadingOnes(),
2128 BitWidth) - BitWidth;
2130 TrailZ = std::min(TrailZ, BitWidth);
2131 LeadZ = std::min(LeadZ, BitWidth);
2132 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2133 APInt::getHighBitsSet(BitWidth, LeadZ);
2137 // For the purposes of computing leading zeros we can conservatively
2138 // treat a udiv as a logical right shift by the power of 2 known to
2139 // be less than the denominator.
2140 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2141 unsigned LeadZ = KnownZero2.countLeadingOnes();
2143 KnownOne2.clearAllBits();
2144 KnownZero2.clearAllBits();
2145 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2146 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2147 if (RHSUnknownLeadingOnes != BitWidth)
2148 LeadZ = std::min(BitWidth,
2149 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2151 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2155 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2156 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2158 // Only known if known in both the LHS and RHS.
2159 KnownOne &= KnownOne2;
2160 KnownZero &= KnownZero2;
2162 case ISD::SELECT_CC:
2163 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2164 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2166 // Only known if known in both the LHS and RHS.
2167 KnownOne &= KnownOne2;
2168 KnownZero &= KnownZero2;
2176 if (Op.getResNo() != 1)
2178 // The boolean result conforms to getBooleanContents.
2179 // If we know the result of a setcc has the top bits zero, use this info.
2180 // We know that we have an integer-based boolean since these operations
2181 // are only available for integer.
2182 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2183 TargetLowering::ZeroOrOneBooleanContent &&
2185 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2188 // If we know the result of a setcc has the top bits zero, use this info.
2189 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2190 TargetLowering::ZeroOrOneBooleanContent &&
2192 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2195 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2196 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2197 unsigned ShAmt = SA->getZExtValue();
2199 // If the shift count is an invalid immediate, don't do anything.
2200 if (ShAmt >= BitWidth)
2203 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2204 KnownZero <<= ShAmt;
2206 // low bits known zero.
2207 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2211 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2212 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2213 unsigned ShAmt = SA->getZExtValue();
2215 // If the shift count is an invalid immediate, don't do anything.
2216 if (ShAmt >= BitWidth)
2219 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2220 KnownZero = KnownZero.lshr(ShAmt);
2221 KnownOne = KnownOne.lshr(ShAmt);
2223 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2224 KnownZero |= HighBits; // High bits known zero.
2228 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2229 unsigned ShAmt = SA->getZExtValue();
2231 // If the shift count is an invalid immediate, don't do anything.
2232 if (ShAmt >= BitWidth)
2235 // If any of the demanded bits are produced by the sign extension, we also
2236 // demand the input sign bit.
2237 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2239 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2240 KnownZero = KnownZero.lshr(ShAmt);
2241 KnownOne = KnownOne.lshr(ShAmt);
2243 // Handle the sign bits.
2244 APInt SignBit = APInt::getSignBit(BitWidth);
2245 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2247 if (KnownZero.intersects(SignBit)) {
2248 KnownZero |= HighBits; // New bits are known zero.
2249 } else if (KnownOne.intersects(SignBit)) {
2250 KnownOne |= HighBits; // New bits are known one.
2254 case ISD::SIGN_EXTEND_INREG: {
2255 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2256 unsigned EBits = EVT.getScalarType().getSizeInBits();
2258 // Sign extension. Compute the demanded bits in the result that are not
2259 // present in the input.
2260 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2262 APInt InSignBit = APInt::getSignBit(EBits);
2263 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2265 // If the sign extended bits are demanded, we know that the sign
2267 InSignBit = InSignBit.zext(BitWidth);
2268 if (NewBits.getBoolValue())
2269 InputDemandedBits |= InSignBit;
2271 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2272 KnownOne &= InputDemandedBits;
2273 KnownZero &= InputDemandedBits;
2275 // If the sign bit of the input is known set or clear, then we know the
2276 // top bits of the result.
2277 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2278 KnownZero |= NewBits;
2279 KnownOne &= ~NewBits;
2280 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2281 KnownOne |= NewBits;
2282 KnownZero &= ~NewBits;
2283 } else { // Input sign bit unknown
2284 KnownZero &= ~NewBits;
2285 KnownOne &= ~NewBits;
2290 case ISD::CTTZ_ZERO_UNDEF:
2292 case ISD::CTLZ_ZERO_UNDEF:
2294 unsigned LowBits = Log2_32(BitWidth)+1;
2295 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2296 KnownOne.clearAllBits();
2300 LoadSDNode *LD = cast<LoadSDNode>(Op);
2301 // If this is a ZEXTLoad and we are looking at the loaded value.
2302 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2303 EVT VT = LD->getMemoryVT();
2304 unsigned MemBits = VT.getScalarType().getSizeInBits();
2305 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2306 } else if (const MDNode *Ranges = LD->getRanges()) {
2307 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2311 case ISD::ZERO_EXTEND: {
2312 EVT InVT = Op.getOperand(0).getValueType();
2313 unsigned InBits = InVT.getScalarType().getSizeInBits();
2314 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2315 KnownZero = KnownZero.trunc(InBits);
2316 KnownOne = KnownOne.trunc(InBits);
2317 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2318 KnownZero = KnownZero.zext(BitWidth);
2319 KnownOne = KnownOne.zext(BitWidth);
2320 KnownZero |= NewBits;
2323 case ISD::SIGN_EXTEND: {
2324 EVT InVT = Op.getOperand(0).getValueType();
2325 unsigned InBits = InVT.getScalarType().getSizeInBits();
2326 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2328 KnownZero = KnownZero.trunc(InBits);
2329 KnownOne = KnownOne.trunc(InBits);
2330 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2332 // Note if the sign bit is known to be zero or one.
2333 bool SignBitKnownZero = KnownZero.isNegative();
2334 bool SignBitKnownOne = KnownOne.isNegative();
2336 KnownZero = KnownZero.zext(BitWidth);
2337 KnownOne = KnownOne.zext(BitWidth);
2339 // If the sign bit is known zero or one, the top bits match.
2340 if (SignBitKnownZero)
2341 KnownZero |= NewBits;
2342 else if (SignBitKnownOne)
2343 KnownOne |= NewBits;
2346 case ISD::ANY_EXTEND: {
2347 EVT InVT = Op.getOperand(0).getValueType();
2348 unsigned InBits = InVT.getScalarType().getSizeInBits();
2349 KnownZero = KnownZero.trunc(InBits);
2350 KnownOne = KnownOne.trunc(InBits);
2351 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2352 KnownZero = KnownZero.zext(BitWidth);
2353 KnownOne = KnownOne.zext(BitWidth);
2356 case ISD::TRUNCATE: {
2357 EVT InVT = Op.getOperand(0).getValueType();
2358 unsigned InBits = InVT.getScalarType().getSizeInBits();
2359 KnownZero = KnownZero.zext(InBits);
2360 KnownOne = KnownOne.zext(InBits);
2361 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2362 KnownZero = KnownZero.trunc(BitWidth);
2363 KnownOne = KnownOne.trunc(BitWidth);
2366 case ISD::AssertZext: {
2367 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2368 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2369 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2370 KnownZero |= (~InMask);
2371 KnownOne &= (~KnownZero);
2375 // All bits are zero except the low bit.
2376 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2380 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2381 // We know that the top bits of C-X are clear if X contains less bits
2382 // than C (i.e. no wrap-around can happen). For example, 20-X is
2383 // positive if we can prove that X is >= 0 and < 16.
2384 if (CLHS->getAPIntValue().isNonNegative()) {
2385 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2386 // NLZ can't be BitWidth with no sign bit
2387 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2388 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2390 // If all of the MaskV bits are known to be zero, then we know the
2391 // output top bits are zero, because we now know that the output is
2393 if ((KnownZero2 & MaskV) == MaskV) {
2394 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2395 // Top bits known zero.
2396 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2404 // Output known-0 bits are known if clear or set in both the low clear bits
2405 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2406 // low 3 bits clear.
2407 // Output known-0 bits are also known if the top bits of each input are
2408 // known to be clear. For example, if one input has the top 10 bits clear
2409 // and the other has the top 8 bits clear, we know the top 7 bits of the
2410 // output must be clear.
2411 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2412 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2413 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2415 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2416 KnownZeroHigh = std::min(KnownZeroHigh,
2417 KnownZero2.countLeadingOnes());
2418 KnownZeroLow = std::min(KnownZeroLow,
2419 KnownZero2.countTrailingOnes());
2421 if (Op.getOpcode() == ISD::ADD) {
2422 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2423 if (KnownZeroHigh > 1)
2424 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2428 // With ADDE, a carry bit may be added in, so we can only use this
2429 // information if we know (at least) that the low two bits are clear. We
2430 // then return to the caller that the low bit is unknown but that other bits
2432 if (KnownZeroLow >= 2) // ADDE
2433 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2437 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2438 const APInt &RA = Rem->getAPIntValue().abs();
2439 if (RA.isPowerOf2()) {
2440 APInt LowBits = RA - 1;
2441 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2443 // The low bits of the first operand are unchanged by the srem.
2444 KnownZero = KnownZero2 & LowBits;
2445 KnownOne = KnownOne2 & LowBits;
2447 // If the first operand is non-negative or has all low bits zero, then
2448 // the upper bits are all zero.
2449 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2450 KnownZero |= ~LowBits;
2452 // If the first operand is negative and not all low bits are zero, then
2453 // the upper bits are all one.
2454 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2455 KnownOne |= ~LowBits;
2456 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2461 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2462 const APInt &RA = Rem->getAPIntValue();
2463 if (RA.isPowerOf2()) {
2464 APInt LowBits = (RA - 1);
2465 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2467 // The upper bits are all zero, the lower ones are unchanged.
2468 KnownZero = KnownZero2 | ~LowBits;
2469 KnownOne = KnownOne2 & LowBits;
2474 // Since the result is less than or equal to either operand, any leading
2475 // zero bits in either operand must also exist in the result.
2476 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2477 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2479 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2480 KnownZero2.countLeadingOnes());
2481 KnownOne.clearAllBits();
2482 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2485 case ISD::EXTRACT_ELEMENT: {
2486 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2487 const unsigned Index =
2488 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2489 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2491 // Remove low part of known bits mask
2492 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2493 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2495 // Remove high part of known bit mask
2496 KnownZero = KnownZero.trunc(BitWidth);
2497 KnownOne = KnownOne.trunc(BitWidth);
2504 APInt Op0Zero, Op0One;
2505 APInt Op1Zero, Op1One;
2506 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2507 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2509 KnownZero = Op0Zero & Op1Zero;
2510 KnownOne = Op0One & Op1One;
2513 case ISD::FrameIndex:
2514 case ISD::TargetFrameIndex:
2515 if (unsigned Align = InferPtrAlignment(Op)) {
2516 // The low bits are known zero if the pointer is aligned.
2517 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2523 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2526 case ISD::INTRINSIC_WO_CHAIN:
2527 case ISD::INTRINSIC_W_CHAIN:
2528 case ISD::INTRINSIC_VOID:
2529 // Allow the target to implement this method for its nodes.
2530 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2534 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2537 /// ComputeNumSignBits - Return the number of times the sign bit of the
2538 /// register is replicated into the other bits. We know that at least 1 bit
2539 /// is always equal to the sign bit (itself), but other cases can give us
2540 /// information. For example, immediately after an "SRA X, 2", we know that
2541 /// the top 3 bits are all equal to each other, so we return 3.
2542 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2543 EVT VT = Op.getValueType();
2544 assert(VT.isInteger() && "Invalid VT!");
2545 unsigned VTBits = VT.getScalarType().getSizeInBits();
2547 unsigned FirstAnswer = 1;
2550 return 1; // Limit search depth.
2552 switch (Op.getOpcode()) {
2554 case ISD::AssertSext:
2555 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2556 return VTBits-Tmp+1;
2557 case ISD::AssertZext:
2558 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2561 case ISD::Constant: {
2562 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2563 return Val.getNumSignBits();
2566 case ISD::SIGN_EXTEND:
2568 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2569 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2571 case ISD::SIGN_EXTEND_INREG:
2572 // Max of the input and what this extends.
2574 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2577 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2578 return std::max(Tmp, Tmp2);
2581 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2582 // SRA X, C -> adds C sign bits.
2583 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2584 Tmp += C->getZExtValue();
2585 if (Tmp > VTBits) Tmp = VTBits;
2589 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2590 // shl destroys sign bits.
2591 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2592 if (C->getZExtValue() >= VTBits || // Bad shift.
2593 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2594 return Tmp - C->getZExtValue();
2599 case ISD::XOR: // NOT is handled here.
2600 // Logical binary ops preserve the number of sign bits at the worst.
2601 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2603 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2604 FirstAnswer = std::min(Tmp, Tmp2);
2605 // We computed what we know about the sign bits as our first
2606 // answer. Now proceed to the generic code that uses
2607 // computeKnownBits, and pick whichever answer is better.
2612 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2613 if (Tmp == 1) return 1; // Early out.
2614 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2615 return std::min(Tmp, Tmp2);
2616 case ISD::SELECT_CC:
2617 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2618 if (Tmp == 1) return 1; // Early out.
2619 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2620 return std::min(Tmp, Tmp2);
2625 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2627 return 1; // Early out.
2628 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2629 return std::min(Tmp, Tmp2);
2636 if (Op.getResNo() != 1)
2638 // The boolean result conforms to getBooleanContents. Fall through.
2639 // If setcc returns 0/-1, all bits are sign bits.
2640 // We know that we have an integer-based boolean since these operations
2641 // are only available for integer.
2642 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2643 TargetLowering::ZeroOrNegativeOneBooleanContent)
2647 // If setcc returns 0/-1, all bits are sign bits.
2648 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2649 TargetLowering::ZeroOrNegativeOneBooleanContent)
2654 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2655 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2657 // Handle rotate right by N like a rotate left by 32-N.
2658 if (Op.getOpcode() == ISD::ROTR)
2659 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2661 // If we aren't rotating out all of the known-in sign bits, return the
2662 // number that are left. This handles rotl(sext(x), 1) for example.
2663 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2664 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2668 // Add can have at most one carry bit. Thus we know that the output
2669 // is, at worst, one more bit than the inputs.
2670 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2671 if (Tmp == 1) return 1; // Early out.
2673 // Special case decrementing a value (ADD X, -1):
2674 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2675 if (CRHS->isAllOnesValue()) {
2676 APInt KnownZero, KnownOne;
2677 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2679 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2681 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2684 // If we are subtracting one from a positive number, there is no carry
2685 // out of the result.
2686 if (KnownZero.isNegative())
2690 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2691 if (Tmp2 == 1) return 1;
2692 return std::min(Tmp, Tmp2)-1;
2695 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2696 if (Tmp2 == 1) return 1;
2699 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2700 if (CLHS->isNullValue()) {
2701 APInt KnownZero, KnownOne;
2702 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2703 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2705 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2708 // If the input is known to be positive (the sign bit is known clear),
2709 // the output of the NEG has the same number of sign bits as the input.
2710 if (KnownZero.isNegative())
2713 // Otherwise, we treat this like a SUB.
2716 // Sub can have at most one carry bit. Thus we know that the output
2717 // is, at worst, one more bit than the inputs.
2718 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2719 if (Tmp == 1) return 1; // Early out.
2720 return std::min(Tmp, Tmp2)-1;
2722 // FIXME: it's tricky to do anything useful for this, but it is an important
2723 // case for targets like X86.
2725 case ISD::EXTRACT_ELEMENT: {
2726 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2727 const int BitWidth = Op.getValueType().getSizeInBits();
2729 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2731 // Get reverse index (starting from 1), Op1 value indexes elements from
2732 // little end. Sign starts at big end.
2733 const int rIndex = Items - 1 -
2734 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2736 // If the sign portion ends in our element the subtraction gives correct
2737 // result. Otherwise it gives either negative or > bitwidth result
2738 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2742 // If we are looking at the loaded value of the SDNode.
2743 if (Op.getResNo() == 0) {
2744 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2745 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2746 unsigned ExtType = LD->getExtensionType();
2749 case ISD::SEXTLOAD: // '17' bits known
2750 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2751 return VTBits-Tmp+1;
2752 case ISD::ZEXTLOAD: // '16' bits known
2753 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2759 // Allow the target to implement this method for its nodes.
2760 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2761 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2762 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2763 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2764 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2765 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2768 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2769 // use this information.
2770 APInt KnownZero, KnownOne;
2771 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2774 if (KnownZero.isNegative()) { // sign bit is 0
2776 } else if (KnownOne.isNegative()) { // sign bit is 1;
2783 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2784 // the number of identical bits in the top of the input value.
2786 Mask <<= Mask.getBitWidth()-VTBits;
2787 // Return # leading zeros. We use 'min' here in case Val was zero before
2788 // shifting. We don't want to return '64' as for an i32 "0".
2789 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2792 /// isBaseWithConstantOffset - Return true if the specified operand is an
2793 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2794 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2795 /// semantics as an ADD. This handles the equivalence:
2796 /// X|Cst == X+Cst iff X&Cst = 0.
2797 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2798 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2799 !isa<ConstantSDNode>(Op.getOperand(1)))
2802 if (Op.getOpcode() == ISD::OR &&
2803 !MaskedValueIsZero(Op.getOperand(0),
2804 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2811 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2812 // If we're told that NaNs won't happen, assume they won't.
2813 if (getTarget().Options.NoNaNsFPMath)
2816 // If the value is a constant, we can obviously see if it is a NaN or not.
2817 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2818 return !C->getValueAPF().isNaN();
2820 // TODO: Recognize more cases here.
2825 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2826 // If the value is a constant, we can obviously see if it is a zero or not.
2827 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2828 return !C->isZero();
2830 // TODO: Recognize more cases here.
2831 switch (Op.getOpcode()) {
2834 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2835 return !C->isNullValue();
2842 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2843 // Check the obvious case.
2844 if (A == B) return true;
2846 // For for negative and positive zero.
2847 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2848 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2849 if (CA->isZero() && CB->isZero()) return true;
2851 // Otherwise they may not be equal.
2855 /// getNode - Gets or creates the specified node.
2857 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2858 FoldingSetNodeID ID;
2859 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2861 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2862 return SDValue(E, 0);
2864 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2865 DL.getDebugLoc(), getVTList(VT));
2866 CSEMap.InsertNode(N, IP);
2869 return SDValue(N, 0);
2872 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2873 EVT VT, SDValue Operand) {
2874 // Constant fold unary operations with an integer constant operand. Even
2875 // opaque constant will be folded, because the folding of unary operations
2876 // doesn't create new constants with different values. Nevertheless, the
2877 // opaque flag is preserved during folding to prevent future folding with
2879 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2880 const APInt &Val = C->getAPIntValue();
2883 case ISD::SIGN_EXTEND:
2884 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2885 C->isTargetOpcode(), C->isOpaque());
2886 case ISD::ANY_EXTEND:
2887 case ISD::ZERO_EXTEND:
2889 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2890 C->isTargetOpcode(), C->isOpaque());
2891 case ISD::UINT_TO_FP:
2892 case ISD::SINT_TO_FP: {
2893 APFloat apf(EVTToAPFloatSemantics(VT),
2894 APInt::getNullValue(VT.getSizeInBits()));
2895 (void)apf.convertFromAPInt(Val,
2896 Opcode==ISD::SINT_TO_FP,
2897 APFloat::rmNearestTiesToEven);
2898 return getConstantFP(apf, DL, VT);
2901 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2902 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2903 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2904 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2905 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2906 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2909 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2912 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2915 case ISD::CTLZ_ZERO_UNDEF:
2916 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2919 case ISD::CTTZ_ZERO_UNDEF:
2920 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2925 // Constant fold unary operations with a floating point constant operand.
2926 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2927 APFloat V = C->getValueAPF(); // make copy
2931 return getConstantFP(V, DL, VT);
2934 return getConstantFP(V, DL, VT);
2936 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2937 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2938 return getConstantFP(V, DL, VT);
2942 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2943 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2944 return getConstantFP(V, DL, VT);
2948 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2949 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2950 return getConstantFP(V, DL, VT);
2953 case ISD::FP_EXTEND: {
2955 // This can return overflow, underflow, or inexact; we don't care.
2956 // FIXME need to be more flexible about rounding mode.
2957 (void)V.convert(EVTToAPFloatSemantics(VT),
2958 APFloat::rmNearestTiesToEven, &ignored);
2959 return getConstantFP(V, DL, VT);
2961 case ISD::FP_TO_SINT:
2962 case ISD::FP_TO_UINT: {
2965 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2966 // FIXME need to be more flexible about rounding mode.
2967 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2968 Opcode==ISD::FP_TO_SINT,
2969 APFloat::rmTowardZero, &ignored);
2970 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2972 APInt api(VT.getSizeInBits(), x);
2973 return getConstant(api, DL, VT);
2976 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2977 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2978 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2979 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2980 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2981 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2986 // Constant fold unary operations with a vector integer or float operand.
2987 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2988 if (BV->isConstant()) {
2991 // FIXME: Entirely reasonable to perform folding of other unary
2992 // operations here as the need arises.
2999 case ISD::FP_EXTEND:
3000 case ISD::FP_TO_SINT:
3001 case ISD::FP_TO_UINT:
3003 case ISD::UINT_TO_FP:
3004 case ISD::SINT_TO_FP:
3007 case ISD::CTLZ_ZERO_UNDEF:
3009 case ISD::CTTZ_ZERO_UNDEF:
3011 EVT SVT = VT.getScalarType();
3012 EVT InVT = BV->getValueType(0);
3013 EVT InSVT = InVT.getScalarType();
3015 // Find legal integer scalar type for constant promotion and
3016 // ensure that its scalar size is at least as large as source.
3018 if (SVT.isInteger()) {
3019 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3020 if (LegalSVT.bitsLT(SVT)) break;
3023 // Let the above scalar folding handle the folding of each element.
3024 SmallVector<SDValue, 8> Ops;
3025 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3026 SDValue OpN = BV->getOperand(i);
3027 EVT OpVT = OpN.getValueType();
3029 // Build vector (integer) scalar operands may need implicit
3030 // truncation - do this before constant folding.
3031 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
3032 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
3034 OpN = getNode(Opcode, DL, SVT, OpN);
3036 // Legalize the (integer) scalar constant if necessary.
3037 if (LegalSVT != SVT)
3038 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
3040 if (OpN.getOpcode() != ISD::UNDEF &&
3041 OpN.getOpcode() != ISD::Constant &&
3042 OpN.getOpcode() != ISD::ConstantFP)
3046 if (Ops.size() == VT.getVectorNumElements())
3047 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3054 unsigned OpOpcode = Operand.getNode()->getOpcode();
3056 case ISD::TokenFactor:
3057 case ISD::MERGE_VALUES:
3058 case ISD::CONCAT_VECTORS:
3059 return Operand; // Factor, merge or concat of one node? No need.
3060 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3061 case ISD::FP_EXTEND:
3062 assert(VT.isFloatingPoint() &&
3063 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3064 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3065 assert((!VT.isVector() ||
3066 VT.getVectorNumElements() ==
3067 Operand.getValueType().getVectorNumElements()) &&
3068 "Vector element count mismatch!");
3069 assert(Operand.getValueType().bitsLT(VT) &&
3070 "Invalid fpext node, dst < src!");
3071 if (Operand.getOpcode() == ISD::UNDEF)
3072 return getUNDEF(VT);
3074 case ISD::SIGN_EXTEND:
3075 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3076 "Invalid SIGN_EXTEND!");
3077 if (Operand.getValueType() == VT) return Operand; // noop extension
3078 assert((!VT.isVector() ||
3079 VT.getVectorNumElements() ==
3080 Operand.getValueType().getVectorNumElements()) &&
3081 "Vector element count mismatch!");
3082 assert(Operand.getValueType().bitsLT(VT) &&
3083 "Invalid sext node, dst < src!");
3084 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3085 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3086 else if (OpOpcode == ISD::UNDEF)
3087 // sext(undef) = 0, because the top bits will all be the same.
3088 return getConstant(0, DL, VT);
3090 case ISD::ZERO_EXTEND:
3091 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3092 "Invalid ZERO_EXTEND!");
3093 if (Operand.getValueType() == VT) return Operand; // noop extension
3094 assert((!VT.isVector() ||
3095 VT.getVectorNumElements() ==
3096 Operand.getValueType().getVectorNumElements()) &&
3097 "Vector element count mismatch!");
3098 assert(Operand.getValueType().bitsLT(VT) &&
3099 "Invalid zext node, dst < src!");
3100 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3101 return getNode(ISD::ZERO_EXTEND, DL, VT,
3102 Operand.getNode()->getOperand(0));
3103 else if (OpOpcode == ISD::UNDEF)
3104 // zext(undef) = 0, because the top bits will be zero.
3105 return getConstant(0, DL, VT);
3107 case ISD::ANY_EXTEND:
3108 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3109 "Invalid ANY_EXTEND!");
3110 if (Operand.getValueType() == VT) return Operand; // noop extension
3111 assert((!VT.isVector() ||
3112 VT.getVectorNumElements() ==
3113 Operand.getValueType().getVectorNumElements()) &&
3114 "Vector element count mismatch!");
3115 assert(Operand.getValueType().bitsLT(VT) &&
3116 "Invalid anyext node, dst < src!");
3118 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3119 OpOpcode == ISD::ANY_EXTEND)
3120 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3121 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3122 else if (OpOpcode == ISD::UNDEF)
3123 return getUNDEF(VT);
3125 // (ext (trunx x)) -> x
3126 if (OpOpcode == ISD::TRUNCATE) {
3127 SDValue OpOp = Operand.getNode()->getOperand(0);
3128 if (OpOp.getValueType() == VT)
3133 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3134 "Invalid TRUNCATE!");
3135 if (Operand.getValueType() == VT) return Operand; // noop truncate
3136 assert((!VT.isVector() ||
3137 VT.getVectorNumElements() ==
3138 Operand.getValueType().getVectorNumElements()) &&
3139 "Vector element count mismatch!");
3140 assert(Operand.getValueType().bitsGT(VT) &&
3141 "Invalid truncate node, src < dst!");
3142 if (OpOpcode == ISD::TRUNCATE)
3143 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3144 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3145 OpOpcode == ISD::ANY_EXTEND) {
3146 // If the source is smaller than the dest, we still need an extend.
3147 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3148 .bitsLT(VT.getScalarType()))
3149 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3150 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3151 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3152 return Operand.getNode()->getOperand(0);
3154 if (OpOpcode == ISD::UNDEF)
3155 return getUNDEF(VT);
3158 assert(VT.isInteger() && VT == Operand.getValueType() &&
3160 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3161 "BSWAP types must be a multiple of 16 bits!");
3162 if (OpOpcode == ISD::UNDEF)
3163 return getUNDEF(VT);
3166 // Basic sanity checking.
3167 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3168 && "Cannot BITCAST between types of different sizes!");
3169 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3170 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3171 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3172 if (OpOpcode == ISD::UNDEF)
3173 return getUNDEF(VT);
3175 case ISD::SCALAR_TO_VECTOR:
3176 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3177 (VT.getVectorElementType() == Operand.getValueType() ||
3178 (VT.getVectorElementType().isInteger() &&
3179 Operand.getValueType().isInteger() &&
3180 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3181 "Illegal SCALAR_TO_VECTOR node!");
3182 if (OpOpcode == ISD::UNDEF)
3183 return getUNDEF(VT);
3184 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3185 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3186 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3187 Operand.getConstantOperandVal(1) == 0 &&
3188 Operand.getOperand(0).getValueType() == VT)
3189 return Operand.getOperand(0);
3192 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3193 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3194 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3195 Operand.getNode()->getOperand(0));
3196 if (OpOpcode == ISD::FNEG) // --X -> X
3197 return Operand.getNode()->getOperand(0);
3200 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3201 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3206 SDVTList VTs = getVTList(VT);
3207 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3208 FoldingSetNodeID ID;
3209 SDValue Ops[1] = { Operand };
3210 AddNodeIDNode(ID, Opcode, VTs, Ops);
3212 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3213 return SDValue(E, 0);
3215 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3216 DL.getDebugLoc(), VTs, Operand);
3217 CSEMap.InsertNode(N, IP);
3219 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3220 DL.getDebugLoc(), VTs, Operand);
3224 return SDValue(N, 0);
3227 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3230 case ISD::ADD: return std::make_pair(C1 + C2, true);
3231 case ISD::SUB: return std::make_pair(C1 - C2, true);
3232 case ISD::MUL: return std::make_pair(C1 * C2, true);
3233 case ISD::AND: return std::make_pair(C1 & C2, true);
3234 case ISD::OR: return std::make_pair(C1 | C2, true);
3235 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3236 case ISD::SHL: return std::make_pair(C1 << C2, true);
3237 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3238 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3239 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3240 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3241 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3242 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3243 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3244 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3246 if (!C2.getBoolValue())
3248 return std::make_pair(C1.udiv(C2), true);
3250 if (!C2.getBoolValue())
3252 return std::make_pair(C1.urem(C2), true);
3254 if (!C2.getBoolValue())
3256 return std::make_pair(C1.sdiv(C2), true);
3258 if (!C2.getBoolValue())
3260 return std::make_pair(C1.srem(C2), true);
3262 return std::make_pair(APInt(1, 0), false);
3265 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3266 const ConstantSDNode *Cst1,
3267 const ConstantSDNode *Cst2) {
3268 if (Cst1->isOpaque() || Cst2->isOpaque())
3271 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3272 Cst2->getAPIntValue());
3275 return getConstant(Folded.first, DL, VT);
3278 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3279 SDNode *Cst1, SDNode *Cst2) {
3280 // If the opcode is a target-specific ISD node, there's nothing we can
3281 // do here and the operand rules may not line up with the below, so
3283 if (Opcode >= ISD::BUILTIN_OP_END)
3286 // Handle the case of two scalars.
3287 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3288 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3289 if (SDValue Folded =
3290 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3293 SmallVector<SDValue, 4> Outputs;
3294 // We may have a vector type but a scalar result. Create a splat.
3295 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3296 // Build a big vector out of the scalar elements we generated.
3297 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3304 // For vectors extract each constant element into Inputs so we can constant
3305 // fold them individually.
3306 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3307 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3311 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3313 EVT SVT = VT.getScalarType();
3314 SmallVector<SDValue, 4> Outputs;
3315 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3316 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3317 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3318 if (!V1 || !V2) // Not a constant, bail.
3321 if (V1->isOpaque() || V2->isOpaque())
3324 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3325 // FIXME: This is valid and could be handled by truncating the APInts.
3326 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3329 // Fold one vector element.
3330 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3331 V2->getAPIntValue());
3334 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3337 assert(VT.getVectorNumElements() == Outputs.size() &&
3338 "Vector size mismatch!");
3340 // We may have a vector type but a scalar result. Create a splat.
3341 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3343 // Build a big vector out of the scalar elements we generated.
3344 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3347 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3348 SDValue N2, const SDNodeFlags *Flags) {
3349 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3350 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3352 // Canonicalize constant to RHS if commutative.
3353 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3354 std::swap(N1C, N2C);
3360 case ISD::TokenFactor:
3361 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3362 N2.getValueType() == MVT::Other && "Invalid token factor!");
3363 // Fold trivial token factors.
3364 if (N1.getOpcode() == ISD::EntryToken) return N2;
3365 if (N2.getOpcode() == ISD::EntryToken) return N1;
3366 if (N1 == N2) return N1;
3368 case ISD::CONCAT_VECTORS:
3369 // Concat of UNDEFs is UNDEF.
3370 if (N1.getOpcode() == ISD::UNDEF &&
3371 N2.getOpcode() == ISD::UNDEF)
3372 return getUNDEF(VT);
3374 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3375 // one big BUILD_VECTOR.
3376 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3377 N2.getOpcode() == ISD::BUILD_VECTOR) {
3378 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3379 N1.getNode()->op_end());
3380 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3382 // BUILD_VECTOR requires all inputs to be of the same type, find the
3383 // maximum type and extend them all.
3384 EVT SVT = VT.getScalarType();
3385 for (SDValue Op : Elts)
3386 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3387 if (SVT.bitsGT(VT.getScalarType()))
3388 for (SDValue &Op : Elts)
3389 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3390 ? getZExtOrTrunc(Op, DL, SVT)
3391 : getSExtOrTrunc(Op, DL, SVT);
3393 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3397 assert(VT.isInteger() && "This operator does not apply to FP types!");
3398 assert(N1.getValueType() == N2.getValueType() &&
3399 N1.getValueType() == VT && "Binary operator types must match!");
3400 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3401 // worth handling here.
3402 if (N2C && N2C->isNullValue())
3404 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3411 assert(VT.isInteger() && "This operator does not apply to FP types!");
3412 assert(N1.getValueType() == N2.getValueType() &&
3413 N1.getValueType() == VT && "Binary operator types must match!");
3414 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3415 // it's worth handling here.
3416 if (N2C && N2C->isNullValue())
3430 assert(VT.isInteger() && "This operator does not apply to FP types!");
3431 assert(N1.getValueType() == N2.getValueType() &&
3432 N1.getValueType() == VT && "Binary operator types must match!");
3439 if (getTarget().Options.UnsafeFPMath) {
3440 if (Opcode == ISD::FADD) {
3442 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3443 if (CFP->getValueAPF().isZero())
3446 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3447 if (CFP->getValueAPF().isZero())
3449 } else if (Opcode == ISD::FSUB) {
3451 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3452 if (CFP->getValueAPF().isZero())
3454 } else if (Opcode == ISD::FMUL) {
3455 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3458 // If the first operand isn't the constant, try the second
3460 CFP = dyn_cast<ConstantFPSDNode>(N2);
3467 return SDValue(CFP,0);
3469 if (CFP->isExactlyValue(1.0))
3474 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3475 assert(N1.getValueType() == N2.getValueType() &&
3476 N1.getValueType() == VT && "Binary operator types must match!");
3478 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3479 assert(N1.getValueType() == VT &&
3480 N1.getValueType().isFloatingPoint() &&
3481 N2.getValueType().isFloatingPoint() &&
3482 "Invalid FCOPYSIGN!");
3489 assert(VT == N1.getValueType() &&
3490 "Shift operators return type must be the same as their first arg");
3491 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3492 "Shifts only work on integers");
3493 assert((!VT.isVector() || VT == N2.getValueType()) &&
3494 "Vector shift amounts must be in the same as their first arg");
3495 // Verify that the shift amount VT is bit enough to hold valid shift
3496 // amounts. This catches things like trying to shift an i1024 value by an
3497 // i8, which is easy to fall into in generic code that uses
3498 // TLI.getShiftAmount().
3499 assert(N2.getValueType().getSizeInBits() >=
3500 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3501 "Invalid use of small shift amount with oversized value!");
3503 // Always fold shifts of i1 values so the code generator doesn't need to
3504 // handle them. Since we know the size of the shift has to be less than the
3505 // size of the value, the shift/rotate count is guaranteed to be zero.
3508 if (N2C && N2C->isNullValue())
3511 case ISD::FP_ROUND_INREG: {
3512 EVT EVT = cast<VTSDNode>(N2)->getVT();
3513 assert(VT == N1.getValueType() && "Not an inreg round!");
3514 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3515 "Cannot FP_ROUND_INREG integer types");
3516 assert(EVT.isVector() == VT.isVector() &&
3517 "FP_ROUND_INREG type should be vector iff the operand "
3519 assert((!EVT.isVector() ||
3520 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3521 "Vector element counts must match in FP_ROUND_INREG");
3522 assert(EVT.bitsLE(VT) && "Not rounding down!");
3524 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3528 assert(VT.isFloatingPoint() &&
3529 N1.getValueType().isFloatingPoint() &&
3530 VT.bitsLE(N1.getValueType()) &&
3531 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3532 if (N1.getValueType() == VT) return N1; // noop conversion.
3534 case ISD::AssertSext:
3535 case ISD::AssertZext: {
3536 EVT EVT = cast<VTSDNode>(N2)->getVT();
3537 assert(VT == N1.getValueType() && "Not an inreg extend!");
3538 assert(VT.isInteger() && EVT.isInteger() &&
3539 "Cannot *_EXTEND_INREG FP types");
3540 assert(!EVT.isVector() &&
3541 "AssertSExt/AssertZExt type should be the vector element type "
3542 "rather than the vector type!");
3543 assert(EVT.bitsLE(VT) && "Not extending!");
3544 if (VT == EVT) return N1; // noop assertion.
3547 case ISD::SIGN_EXTEND_INREG: {
3548 EVT EVT = cast<VTSDNode>(N2)->getVT();
3549 assert(VT == N1.getValueType() && "Not an inreg extend!");
3550 assert(VT.isInteger() && EVT.isInteger() &&
3551 "Cannot *_EXTEND_INREG FP types");
3552 assert(EVT.isVector() == VT.isVector() &&
3553 "SIGN_EXTEND_INREG type should be vector iff the operand "
3555 assert((!EVT.isVector() ||
3556 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3557 "Vector element counts must match in SIGN_EXTEND_INREG");
3558 assert(EVT.bitsLE(VT) && "Not extending!");
3559 if (EVT == VT) return N1; // Not actually extending
3561 auto SignExtendInReg = [&](APInt Val) {
3562 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3563 Val <<= Val.getBitWidth() - FromBits;
3564 Val = Val.ashr(Val.getBitWidth() - FromBits);
3565 return getConstant(Val, DL, VT.getScalarType());
3569 APInt Val = N1C->getAPIntValue();
3570 return SignExtendInReg(Val);
3572 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3573 SmallVector<SDValue, 8> Ops;
3574 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3575 SDValue Op = N1.getOperand(i);
3576 if (Op.getValueType() != VT.getScalarType()) break;
3577 if (Op.getOpcode() == ISD::UNDEF) {
3581 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3582 APInt Val = C->getAPIntValue();
3583 Ops.push_back(SignExtendInReg(Val));
3588 if (Ops.size() == VT.getVectorNumElements())
3589 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3593 case ISD::EXTRACT_VECTOR_ELT:
3594 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3595 if (N1.getOpcode() == ISD::UNDEF)
3596 return getUNDEF(VT);
3598 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3599 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3600 return getUNDEF(VT);
3602 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3603 // expanding copies of large vectors from registers.
3605 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3606 N1.getNumOperands() > 0) {
3608 N1.getOperand(0).getValueType().getVectorNumElements();
3609 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3610 N1.getOperand(N2C->getZExtValue() / Factor),
3611 getConstant(N2C->getZExtValue() % Factor, DL,
3612 N2.getValueType()));
3615 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3616 // expanding large vector constants.
3617 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3618 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3620 if (VT != Elt.getValueType())
3621 // If the vector element type is not legal, the BUILD_VECTOR operands
3622 // are promoted and implicitly truncated, and the result implicitly
3623 // extended. Make that explicit here.
3624 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3629 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3630 // operations are lowered to scalars.
3631 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3632 // If the indices are the same, return the inserted element else
3633 // if the indices are known different, extract the element from
3634 // the original vector.
3635 SDValue N1Op2 = N1.getOperand(2);
3636 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3638 if (N1Op2C && N2C) {
3639 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3640 if (VT == N1.getOperand(1).getValueType())
3641 return N1.getOperand(1);
3643 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3646 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3650 case ISD::EXTRACT_ELEMENT:
3651 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3652 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3653 (N1.getValueType().isInteger() == VT.isInteger()) &&
3654 N1.getValueType() != VT &&
3655 "Wrong types for EXTRACT_ELEMENT!");
3657 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3658 // 64-bit integers into 32-bit parts. Instead of building the extract of
3659 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3660 if (N1.getOpcode() == ISD::BUILD_PAIR)
3661 return N1.getOperand(N2C->getZExtValue());
3663 // EXTRACT_ELEMENT of a constant int is also very common.
3664 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3665 unsigned ElementSize = VT.getSizeInBits();
3666 unsigned Shift = ElementSize * N2C->getZExtValue();
3667 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3668 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3671 case ISD::EXTRACT_SUBVECTOR: {
3673 if (VT.isSimple() && N1.getValueType().isSimple()) {
3674 assert(VT.isVector() && N1.getValueType().isVector() &&
3675 "Extract subvector VTs must be a vectors!");
3676 assert(VT.getVectorElementType() ==
3677 N1.getValueType().getVectorElementType() &&
3678 "Extract subvector VTs must have the same element type!");
3679 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3680 "Extract subvector must be from larger vector to smaller vector!");
3682 if (isa<ConstantSDNode>(Index)) {
3683 assert((VT.getVectorNumElements() +
3684 cast<ConstantSDNode>(Index)->getZExtValue()
3685 <= N1.getValueType().getVectorNumElements())
3686 && "Extract subvector overflow!");
3689 // Trivial extraction.
3690 if (VT.getSimpleVT() == N1.getSimpleValueType())
3697 // Perform trivial constant folding.
3699 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3702 // Constant fold FP operations.
3703 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3704 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3705 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3707 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3708 // Canonicalize constant to RHS if commutative.
3709 std::swap(N1CFP, N2CFP);
3712 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3713 APFloat::opStatus s;
3716 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3717 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3718 return getConstantFP(V1, DL, VT);
3721 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3722 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3723 return getConstantFP(V1, DL, VT);
3726 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3727 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3728 return getConstantFP(V1, DL, VT);
3731 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3732 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3733 s!=APFloat::opDivByZero)) {
3734 return getConstantFP(V1, DL, VT);
3738 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3739 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3740 s!=APFloat::opDivByZero)) {
3741 return getConstantFP(V1, DL, VT);
3744 case ISD::FCOPYSIGN:
3746 return getConstantFP(V1, DL, VT);
3751 if (Opcode == ISD::FP_ROUND) {
3752 APFloat V = N1CFP->getValueAPF(); // make copy
3754 // This can return overflow, underflow, or inexact; we don't care.
3755 // FIXME need to be more flexible about rounding mode.
3756 (void)V.convert(EVTToAPFloatSemantics(VT),
3757 APFloat::rmNearestTiesToEven, &ignored);
3758 return getConstantFP(V, DL, VT);
3762 // Canonicalize an UNDEF to the RHS, even over a constant.
3763 if (N1.getOpcode() == ISD::UNDEF) {
3764 if (isCommutativeBinOp(Opcode)) {
3768 case ISD::FP_ROUND_INREG:
3769 case ISD::SIGN_EXTEND_INREG:
3775 return N1; // fold op(undef, arg2) -> undef
3783 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3784 // For vectors, we can't easily build an all zero vector, just return
3791 // Fold a bunch of operators when the RHS is undef.
3792 if (N2.getOpcode() == ISD::UNDEF) {
3795 if (N1.getOpcode() == ISD::UNDEF)
3796 // Handle undef ^ undef -> 0 special case. This is a common
3798 return getConstant(0, DL, VT);
3808 return N2; // fold op(arg1, undef) -> undef
3814 if (getTarget().Options.UnsafeFPMath)
3822 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3823 // For vectors, we can't easily build an all zero vector, just return
3828 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3829 // For vectors, we can't easily build an all one vector, just return
3837 // Memoize this node if possible.
3839 SDVTList VTs = getVTList(VT);
3840 if (VT != MVT::Glue) {
3841 SDValue Ops[] = {N1, N2};
3842 FoldingSetNodeID ID;
3843 AddNodeIDNode(ID, Opcode, VTs, Ops);
3844 AddNodeIDFlags(ID, Opcode, Flags);
3846 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3847 return SDValue(E, 0);
3849 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3851 CSEMap.InsertNode(N, IP);
3853 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3857 return SDValue(N, 0);
3860 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3861 SDValue N1, SDValue N2, SDValue N3) {
3862 // Perform various simplifications.
3863 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3866 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3867 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3868 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3869 if (N1CFP && N2CFP && N3CFP) {
3870 APFloat V1 = N1CFP->getValueAPF();
3871 const APFloat &V2 = N2CFP->getValueAPF();
3872 const APFloat &V3 = N3CFP->getValueAPF();
3873 APFloat::opStatus s =
3874 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3875 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3876 return getConstantFP(V1, DL, VT);
3880 case ISD::CONCAT_VECTORS:
3881 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3882 // one big BUILD_VECTOR.
3883 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3884 N2.getOpcode() == ISD::BUILD_VECTOR &&
3885 N3.getOpcode() == ISD::BUILD_VECTOR) {
3886 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3887 N1.getNode()->op_end());
3888 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3889 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3890 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3894 // Use FoldSetCC to simplify SETCC's.
3895 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3896 if (Simp.getNode()) return Simp;
3901 if (N1C->getZExtValue())
3902 return N2; // select true, X, Y -> X
3903 return N3; // select false, X, Y -> Y
3906 if (N2 == N3) return N2; // select C, X, X -> X
3908 case ISD::VECTOR_SHUFFLE:
3909 llvm_unreachable("should use getVectorShuffle constructor!");
3910 case ISD::INSERT_SUBVECTOR: {
3912 if (VT.isSimple() && N1.getValueType().isSimple()
3913 && N2.getValueType().isSimple()) {
3914 assert(VT.isVector() && N1.getValueType().isVector() &&
3915 N2.getValueType().isVector() &&
3916 "Insert subvector VTs must be a vectors");
3917 assert(VT == N1.getValueType() &&
3918 "Dest and insert subvector source types must match!");
3919 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3920 "Insert subvector must be from smaller vector to larger vector!");
3921 if (isa<ConstantSDNode>(Index)) {
3922 assert((N2.getValueType().getVectorNumElements() +
3923 cast<ConstantSDNode>(Index)->getZExtValue()
3924 <= VT.getVectorNumElements())
3925 && "Insert subvector overflow!");
3928 // Trivial insertion.
3929 if (VT.getSimpleVT() == N2.getSimpleValueType())
3935 // Fold bit_convert nodes from a type to themselves.
3936 if (N1.getValueType() == VT)
3941 // Memoize node if it doesn't produce a flag.
3943 SDVTList VTs = getVTList(VT);
3944 if (VT != MVT::Glue) {
3945 SDValue Ops[] = { N1, N2, N3 };
3946 FoldingSetNodeID ID;
3947 AddNodeIDNode(ID, Opcode, VTs, Ops);
3949 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3950 return SDValue(E, 0);
3952 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3953 DL.getDebugLoc(), VTs, N1, N2, N3);
3954 CSEMap.InsertNode(N, IP);
3956 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3957 DL.getDebugLoc(), VTs, N1, N2, N3);
3961 return SDValue(N, 0);
3964 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3965 SDValue N1, SDValue N2, SDValue N3,
3967 SDValue Ops[] = { N1, N2, N3, N4 };
3968 return getNode(Opcode, DL, VT, Ops);
3971 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3972 SDValue N1, SDValue N2, SDValue N3,
3973 SDValue N4, SDValue N5) {
3974 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3975 return getNode(Opcode, DL, VT, Ops);
3978 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3979 /// the incoming stack arguments to be loaded from the stack.
3980 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3981 SmallVector<SDValue, 8> ArgChains;
3983 // Include the original chain at the beginning of the list. When this is
3984 // used by target LowerCall hooks, this helps legalize find the
3985 // CALLSEQ_BEGIN node.
3986 ArgChains.push_back(Chain);
3988 // Add a chain value for each stack argument.
3989 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3990 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3991 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3992 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3993 if (FI->getIndex() < 0)
3994 ArgChains.push_back(SDValue(L, 1));
3996 // Build a tokenfactor for all the chains.
3997 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4000 /// getMemsetValue - Vectorized representation of the memset value
4002 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4004 assert(Value.getOpcode() != ISD::UNDEF);
4006 unsigned NumBits = VT.getScalarType().getSizeInBits();
4007 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4008 assert(C->getAPIntValue().getBitWidth() == 8);
4009 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4011 return DAG.getConstant(Val, dl, VT);
4012 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4016 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4017 EVT IntVT = VT.getScalarType();
4018 if (!IntVT.isInteger())
4019 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4021 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4023 // Use a multiplication with 0x010101... to extend the input to the
4025 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4026 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4027 DAG.getConstant(Magic, dl, IntVT));
4030 if (VT != Value.getValueType() && !VT.isInteger())
4031 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4032 if (VT != Value.getValueType()) {
4033 assert(VT.getVectorElementType() == Value.getValueType() &&
4034 "value type should be one vector element here");
4035 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4036 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4042 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4043 /// used when a memcpy is turned into a memset when the source is a constant
4045 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4046 const TargetLowering &TLI, StringRef Str) {
4047 // Handle vector with all elements zero.
4050 return DAG.getConstant(0, dl, VT);
4051 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4052 return DAG.getConstantFP(0.0, dl, VT);
4053 else if (VT.isVector()) {
4054 unsigned NumElts = VT.getVectorNumElements();
4055 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4056 return DAG.getNode(ISD::BITCAST, dl, VT,
4057 DAG.getConstant(0, dl,
4058 EVT::getVectorVT(*DAG.getContext(),
4061 llvm_unreachable("Expected type!");
4064 assert(!VT.isVector() && "Can't handle vector type here!");
4065 unsigned NumVTBits = VT.getSizeInBits();
4066 unsigned NumVTBytes = NumVTBits / 8;
4067 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4069 APInt Val(NumVTBits, 0);
4070 if (DAG.getDataLayout().isLittleEndian()) {
4071 for (unsigned i = 0; i != NumBytes; ++i)
4072 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4074 for (unsigned i = 0; i != NumBytes; ++i)
4075 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4078 // If the "cost" of materializing the integer immediate is less than the cost
4079 // of a load, then it is cost effective to turn the load into the immediate.
4080 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4081 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4082 return DAG.getConstant(Val, dl, VT);
4083 return SDValue(nullptr, 0);
4086 /// getMemBasePlusOffset - Returns base and offset node for the
4088 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4089 SelectionDAG &DAG) {
4090 EVT VT = Base.getValueType();
4091 return DAG.getNode(ISD::ADD, dl,
4092 VT, Base, DAG.getConstant(Offset, dl, VT));
4095 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4097 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4098 unsigned SrcDelta = 0;
4099 GlobalAddressSDNode *G = nullptr;
4100 if (Src.getOpcode() == ISD::GlobalAddress)
4101 G = cast<GlobalAddressSDNode>(Src);
4102 else if (Src.getOpcode() == ISD::ADD &&
4103 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4104 Src.getOperand(1).getOpcode() == ISD::Constant) {
4105 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4106 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4111 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4114 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4115 /// Return true if the number of memory ops is below the threshold (Limit).
4116 /// It returns the types of the sequence of memory ops to perform
4117 /// memset / memcpy by reference.
4118 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4119 unsigned Limit, uint64_t Size,
4120 unsigned DstAlign, unsigned SrcAlign,
4126 const TargetLowering &TLI) {
4127 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4128 "Expecting memcpy / memset source to meet alignment requirement!");
4129 // If 'SrcAlign' is zero, that means the memory operation does not need to
4130 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4131 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4132 // is the specified alignment of the memory operation. If it is zero, that
4133 // means it's possible to change the alignment of the destination.
4134 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4135 // not need to be loaded.
4136 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4137 IsMemset, ZeroMemset, MemcpyStrSrc,
4138 DAG.getMachineFunction());
4140 if (VT == MVT::Other) {
4142 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4143 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4144 VT = TLI.getPointerTy(DAG.getDataLayout());
4146 switch (DstAlign & 7) {
4147 case 0: VT = MVT::i64; break;
4148 case 4: VT = MVT::i32; break;
4149 case 2: VT = MVT::i16; break;
4150 default: VT = MVT::i8; break;
4155 while (!TLI.isTypeLegal(LVT))
4156 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4157 assert(LVT.isInteger());
4163 unsigned NumMemOps = 0;
4165 unsigned VTSize = VT.getSizeInBits() / 8;
4166 while (VTSize > Size) {
4167 // For now, only use non-vector load / store's for the left-over pieces.
4172 if (VT.isVector() || VT.isFloatingPoint()) {
4173 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4174 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4175 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4177 else if (NewVT == MVT::i64 &&
4178 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4179 TLI.isSafeMemOpType(MVT::f64)) {
4180 // i64 is usually not legal on 32-bit targets, but f64 may be.
4188 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4189 if (NewVT == MVT::i8)
4191 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4193 NewVTSize = NewVT.getSizeInBits() / 8;
4195 // If the new VT cannot cover all of the remaining bits, then consider
4196 // issuing a (or a pair of) unaligned and overlapping load / store.
4197 // FIXME: Only does this for 64-bit or more since we don't have proper
4198 // cost model for unaligned load / store.
4201 if (NumMemOps && AllowOverlap &&
4202 VTSize >= 8 && NewVTSize < Size &&
4203 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4211 if (++NumMemOps > Limit)
4214 MemOps.push_back(VT);
4221 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4222 // On Darwin, -Os means optimize for size without hurting performance, so
4223 // only really optimize for size when -Oz (MinSize) is used.
4224 if (MF.getTarget().getTargetTriple().isOSDarwin())
4225 return MF.getFunction()->optForMinSize();
4226 return MF.getFunction()->optForSize();
4229 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4230 SDValue Chain, SDValue Dst,
4231 SDValue Src, uint64_t Size,
4232 unsigned Align, bool isVol,
4234 MachinePointerInfo DstPtrInfo,
4235 MachinePointerInfo SrcPtrInfo) {
4236 // Turn a memcpy of undef to nop.
4237 if (Src.getOpcode() == ISD::UNDEF)
4240 // Expand memcpy to a series of load and store ops if the size operand falls
4241 // below a certain threshold.
4242 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4243 // rather than maybe a humongous number of loads and stores.
4244 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4245 std::vector<EVT> MemOps;
4246 bool DstAlignCanChange = false;
4247 MachineFunction &MF = DAG.getMachineFunction();
4248 MachineFrameInfo *MFI = MF.getFrameInfo();
4249 bool OptSize = shouldLowerMemFuncForSize(MF);
4250 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4251 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4252 DstAlignCanChange = true;
4253 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4254 if (Align > SrcAlign)
4257 bool CopyFromStr = isMemSrcFromString(Src, Str);
4258 bool isZeroStr = CopyFromStr && Str.empty();
4259 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4261 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4262 (DstAlignCanChange ? 0 : Align),
4263 (isZeroStr ? 0 : SrcAlign),
4264 false, false, CopyFromStr, true, DAG, TLI))
4267 if (DstAlignCanChange) {
4268 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4269 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4271 // Don't promote to an alignment that would require dynamic stack
4273 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4274 if (!TRI->needsStackRealignment(MF))
4275 while (NewAlign > Align &&
4276 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4279 if (NewAlign > Align) {
4280 // Give the stack frame object a larger alignment if needed.
4281 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4282 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4287 SmallVector<SDValue, 8> OutChains;
4288 unsigned NumMemOps = MemOps.size();
4289 uint64_t SrcOff = 0, DstOff = 0;
4290 for (unsigned i = 0; i != NumMemOps; ++i) {
4292 unsigned VTSize = VT.getSizeInBits() / 8;
4293 SDValue Value, Store;
4295 if (VTSize > Size) {
4296 // Issuing an unaligned load / store pair that overlaps with the previous
4297 // pair. Adjust the offset accordingly.
4298 assert(i == NumMemOps-1 && i != 0);
4299 SrcOff -= VTSize - Size;
4300 DstOff -= VTSize - Size;
4304 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4305 // It's unlikely a store of a vector immediate can be done in a single
4306 // instruction. It would require a load from a constantpool first.
4307 // We only handle zero vectors here.
4308 // FIXME: Handle other cases where store of vector immediate is done in
4309 // a single instruction.
4310 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4311 if (Value.getNode())
4312 Store = DAG.getStore(Chain, dl, Value,
4313 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4314 DstPtrInfo.getWithOffset(DstOff), isVol,
4318 if (!Store.getNode()) {
4319 // The type might not be legal for the target. This should only happen
4320 // if the type is smaller than a legal type, as on PPC, so the right
4321 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4322 // to Load/Store if NVT==VT.
4323 // FIXME does the case above also need this?
4324 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4325 assert(NVT.bitsGE(VT));
4326 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4327 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4328 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4329 false, MinAlign(SrcAlign, SrcOff));
4330 Store = DAG.getTruncStore(Chain, dl, Value,
4331 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4332 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4335 OutChains.push_back(Store);
4341 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4344 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4345 SDValue Chain, SDValue Dst,
4346 SDValue Src, uint64_t Size,
4347 unsigned Align, bool isVol,
4349 MachinePointerInfo DstPtrInfo,
4350 MachinePointerInfo SrcPtrInfo) {
4351 // Turn a memmove of undef to nop.
4352 if (Src.getOpcode() == ISD::UNDEF)
4355 // Expand memmove to a series of load and store ops if the size operand falls
4356 // below a certain threshold.
4357 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4358 std::vector<EVT> MemOps;
4359 bool DstAlignCanChange = false;
4360 MachineFunction &MF = DAG.getMachineFunction();
4361 MachineFrameInfo *MFI = MF.getFrameInfo();
4362 bool OptSize = shouldLowerMemFuncForSize(MF);
4363 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4364 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4365 DstAlignCanChange = true;
4366 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4367 if (Align > SrcAlign)
4369 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4371 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4372 (DstAlignCanChange ? 0 : Align), SrcAlign,
4373 false, false, false, false, DAG, TLI))
4376 if (DstAlignCanChange) {
4377 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4378 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4379 if (NewAlign > Align) {
4380 // Give the stack frame object a larger alignment if needed.
4381 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4382 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4387 uint64_t SrcOff = 0, DstOff = 0;
4388 SmallVector<SDValue, 8> LoadValues;
4389 SmallVector<SDValue, 8> LoadChains;
4390 SmallVector<SDValue, 8> OutChains;
4391 unsigned NumMemOps = MemOps.size();
4392 for (unsigned i = 0; i < NumMemOps; i++) {
4394 unsigned VTSize = VT.getSizeInBits() / 8;
4397 Value = DAG.getLoad(VT, dl, Chain,
4398 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4399 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4400 false, false, SrcAlign);
4401 LoadValues.push_back(Value);
4402 LoadChains.push_back(Value.getValue(1));
4405 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4407 for (unsigned i = 0; i < NumMemOps; i++) {
4409 unsigned VTSize = VT.getSizeInBits() / 8;
4412 Store = DAG.getStore(Chain, dl, LoadValues[i],
4413 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4414 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4415 OutChains.push_back(Store);
4419 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4422 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4425 /// \param DAG Selection DAG where lowered code is placed.
4426 /// \param dl Link to corresponding IR location.
4427 /// \param Chain Control flow dependency.
4428 /// \param Dst Pointer to destination memory location.
4429 /// \param Src Value of byte to write into the memory.
4430 /// \param Size Number of bytes to write.
4431 /// \param Align Alignment of the destination in bytes.
4432 /// \param isVol True if destination is volatile.
4433 /// \param DstPtrInfo IR information on the memory pointer.
4434 /// \returns New head in the control flow, if lowering was successful, empty
4435 /// SDValue otherwise.
4437 /// The function tries to replace 'llvm.memset' intrinsic with several store
4438 /// operations and value calculation code. This is usually profitable for small
4440 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4441 SDValue Chain, SDValue Dst,
4442 SDValue Src, uint64_t Size,
4443 unsigned Align, bool isVol,
4444 MachinePointerInfo DstPtrInfo) {
4445 // Turn a memset of undef to nop.
4446 if (Src.getOpcode() == ISD::UNDEF)
4449 // Expand memset to a series of load/store ops if the size operand
4450 // falls below a certain threshold.
4451 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4452 std::vector<EVT> MemOps;
4453 bool DstAlignCanChange = false;
4454 MachineFunction &MF = DAG.getMachineFunction();
4455 MachineFrameInfo *MFI = MF.getFrameInfo();
4456 bool OptSize = shouldLowerMemFuncForSize(MF);
4457 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4458 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4459 DstAlignCanChange = true;
4461 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4462 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4463 Size, (DstAlignCanChange ? 0 : Align), 0,
4464 true, IsZeroVal, false, true, DAG, TLI))
4467 if (DstAlignCanChange) {
4468 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4469 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4470 if (NewAlign > Align) {
4471 // Give the stack frame object a larger alignment if needed.
4472 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4473 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4478 SmallVector<SDValue, 8> OutChains;
4479 uint64_t DstOff = 0;
4480 unsigned NumMemOps = MemOps.size();
4482 // Find the largest store and generate the bit pattern for it.
4483 EVT LargestVT = MemOps[0];
4484 for (unsigned i = 1; i < NumMemOps; i++)
4485 if (MemOps[i].bitsGT(LargestVT))
4486 LargestVT = MemOps[i];
4487 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4489 for (unsigned i = 0; i < NumMemOps; i++) {
4491 unsigned VTSize = VT.getSizeInBits() / 8;
4492 if (VTSize > Size) {
4493 // Issuing an unaligned load / store pair that overlaps with the previous
4494 // pair. Adjust the offset accordingly.
4495 assert(i == NumMemOps-1 && i != 0);
4496 DstOff -= VTSize - Size;
4499 // If this store is smaller than the largest store see whether we can get
4500 // the smaller value for free with a truncate.
4501 SDValue Value = MemSetValue;
4502 if (VT.bitsLT(LargestVT)) {
4503 if (!LargestVT.isVector() && !VT.isVector() &&
4504 TLI.isTruncateFree(LargestVT, VT))
4505 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4507 Value = getMemsetValue(Src, VT, DAG, dl);
4509 assert(Value.getValueType() == VT && "Value with wrong type.");
4510 SDValue Store = DAG.getStore(Chain, dl, Value,
4511 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4512 DstPtrInfo.getWithOffset(DstOff),
4513 isVol, false, Align);
4514 OutChains.push_back(Store);
4515 DstOff += VT.getSizeInBits() / 8;
4519 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4522 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4523 SDValue Src, SDValue Size,
4524 unsigned Align, bool isVol, bool AlwaysInline,
4525 bool isTailCall, MachinePointerInfo DstPtrInfo,
4526 MachinePointerInfo SrcPtrInfo) {
4527 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4529 // Check to see if we should lower the memcpy to loads and stores first.
4530 // For cases within the target-specified limits, this is the best choice.
4531 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4533 // Memcpy with size zero? Just return the original chain.
4534 if (ConstantSize->isNullValue())
4537 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4538 ConstantSize->getZExtValue(),Align,
4539 isVol, false, DstPtrInfo, SrcPtrInfo);
4540 if (Result.getNode())
4544 // Then check to see if we should lower the memcpy with target-specific
4545 // code. If the target chooses to do this, this is the next best.
4547 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4548 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4549 DstPtrInfo, SrcPtrInfo);
4550 if (Result.getNode())
4554 // If we really need inline code and the target declined to provide it,
4555 // use a (potentially long) sequence of loads and stores.
4557 assert(ConstantSize && "AlwaysInline requires a constant size!");
4558 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4559 ConstantSize->getZExtValue(), Align, isVol,
4560 true, DstPtrInfo, SrcPtrInfo);
4563 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4564 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4565 // respect volatile, so they may do things like read or write memory
4566 // beyond the given memory regions. But fixing this isn't easy, and most
4567 // people don't care.
4569 // Emit a library call.
4570 TargetLowering::ArgListTy Args;
4571 TargetLowering::ArgListEntry Entry;
4572 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4573 Entry.Node = Dst; Args.push_back(Entry);
4574 Entry.Node = Src; Args.push_back(Entry);
4575 Entry.Node = Size; Args.push_back(Entry);
4576 // FIXME: pass in SDLoc
4577 TargetLowering::CallLoweringInfo CLI(*this);
4580 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4581 Type::getVoidTy(*getContext()),
4582 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4583 TLI->getPointerTy(getDataLayout())),
4586 .setTailCall(isTailCall);
4588 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4589 return CallResult.second;
4592 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4593 SDValue Src, SDValue Size,
4594 unsigned Align, bool isVol, bool isTailCall,
4595 MachinePointerInfo DstPtrInfo,
4596 MachinePointerInfo SrcPtrInfo) {
4597 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4599 // Check to see if we should lower the memmove to loads and stores first.
4600 // For cases within the target-specified limits, this is the best choice.
4601 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4603 // Memmove with size zero? Just return the original chain.
4604 if (ConstantSize->isNullValue())
4608 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4609 ConstantSize->getZExtValue(), Align, isVol,
4610 false, DstPtrInfo, SrcPtrInfo);
4611 if (Result.getNode())
4615 // Then check to see if we should lower the memmove with target-specific
4616 // code. If the target chooses to do this, this is the next best.
4618 SDValue Result = TSI->EmitTargetCodeForMemmove(
4619 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4620 if (Result.getNode())
4624 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4625 // not be safe. See memcpy above for more details.
4627 // Emit a library call.
4628 TargetLowering::ArgListTy Args;
4629 TargetLowering::ArgListEntry Entry;
4630 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4631 Entry.Node = Dst; Args.push_back(Entry);
4632 Entry.Node = Src; Args.push_back(Entry);
4633 Entry.Node = Size; Args.push_back(Entry);
4634 // FIXME: pass in SDLoc
4635 TargetLowering::CallLoweringInfo CLI(*this);
4638 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4639 Type::getVoidTy(*getContext()),
4640 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4641 TLI->getPointerTy(getDataLayout())),
4644 .setTailCall(isTailCall);
4646 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4647 return CallResult.second;
4650 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4651 SDValue Src, SDValue Size,
4652 unsigned Align, bool isVol, bool isTailCall,
4653 MachinePointerInfo DstPtrInfo) {
4654 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4656 // Check to see if we should lower the memset to stores first.
4657 // For cases within the target-specified limits, this is the best choice.
4658 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4660 // Memset with size zero? Just return the original chain.
4661 if (ConstantSize->isNullValue())
4665 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4666 Align, isVol, DstPtrInfo);
4668 if (Result.getNode())
4672 // Then check to see if we should lower the memset with target-specific
4673 // code. If the target chooses to do this, this is the next best.
4675 SDValue Result = TSI->EmitTargetCodeForMemset(
4676 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4677 if (Result.getNode())
4681 // Emit a library call.
4682 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4683 TargetLowering::ArgListTy Args;
4684 TargetLowering::ArgListEntry Entry;
4685 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4686 Args.push_back(Entry);
4688 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4689 Args.push_back(Entry);
4691 Entry.Ty = IntPtrTy;
4692 Args.push_back(Entry);
4694 // FIXME: pass in SDLoc
4695 TargetLowering::CallLoweringInfo CLI(*this);
4698 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4699 Type::getVoidTy(*getContext()),
4700 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4701 TLI->getPointerTy(getDataLayout())),
4704 .setTailCall(isTailCall);
4706 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4707 return CallResult.second;
4710 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4711 SDVTList VTList, ArrayRef<SDValue> Ops,
4712 MachineMemOperand *MMO,
4713 AtomicOrdering SuccessOrdering,
4714 AtomicOrdering FailureOrdering,
4715 SynchronizationScope SynchScope) {
4716 FoldingSetNodeID ID;
4717 ID.AddInteger(MemVT.getRawBits());
4718 AddNodeIDNode(ID, Opcode, VTList, Ops);
4719 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4721 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4722 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4723 return SDValue(E, 0);
4726 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4727 // SDNode doesn't have access to it. This memory will be "leaked" when
4728 // the node is deallocated, but recovered when the allocator is released.
4729 // If the number of operands is less than 5 we use AtomicSDNode's internal
4731 unsigned NumOps = Ops.size();
4732 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4735 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4736 dl.getDebugLoc(), VTList, MemVT,
4737 Ops.data(), DynOps, NumOps, MMO,
4738 SuccessOrdering, FailureOrdering,
4740 CSEMap.InsertNode(N, IP);
4742 return SDValue(N, 0);
4745 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4746 SDVTList VTList, ArrayRef<SDValue> Ops,
4747 MachineMemOperand *MMO,
4748 AtomicOrdering Ordering,
4749 SynchronizationScope SynchScope) {
4750 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4751 Ordering, SynchScope);
4754 SDValue SelectionDAG::getAtomicCmpSwap(
4755 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4756 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4757 unsigned Alignment, AtomicOrdering SuccessOrdering,
4758 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4759 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4760 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4761 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4763 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4764 Alignment = getEVTAlignment(MemVT);
4766 MachineFunction &MF = getMachineFunction();
4768 // FIXME: Volatile isn't really correct; we should keep track of atomic
4769 // orderings in the memoperand.
4770 unsigned Flags = MachineMemOperand::MOVolatile;
4771 Flags |= MachineMemOperand::MOLoad;
4772 Flags |= MachineMemOperand::MOStore;
4774 MachineMemOperand *MMO =
4775 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4777 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4778 SuccessOrdering, FailureOrdering, SynchScope);
4781 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4782 SDVTList VTs, SDValue Chain, SDValue Ptr,
4783 SDValue Cmp, SDValue Swp,
4784 MachineMemOperand *MMO,
4785 AtomicOrdering SuccessOrdering,
4786 AtomicOrdering FailureOrdering,
4787 SynchronizationScope SynchScope) {
4788 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4789 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4790 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4792 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4793 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4794 SuccessOrdering, FailureOrdering, SynchScope);
4797 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4799 SDValue Ptr, SDValue Val,
4800 const Value* PtrVal,
4802 AtomicOrdering Ordering,
4803 SynchronizationScope SynchScope) {
4804 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4805 Alignment = getEVTAlignment(MemVT);
4807 MachineFunction &MF = getMachineFunction();
4808 // An atomic store does not load. An atomic load does not store.
4809 // (An atomicrmw obviously both loads and stores.)
4810 // For now, atomics are considered to be volatile always, and they are
4812 // FIXME: Volatile isn't really correct; we should keep track of atomic
4813 // orderings in the memoperand.
4814 unsigned Flags = MachineMemOperand::MOVolatile;
4815 if (Opcode != ISD::ATOMIC_STORE)
4816 Flags |= MachineMemOperand::MOLoad;
4817 if (Opcode != ISD::ATOMIC_LOAD)
4818 Flags |= MachineMemOperand::MOStore;
4820 MachineMemOperand *MMO =
4821 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4822 MemVT.getStoreSize(), Alignment);
4824 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4825 Ordering, SynchScope);
4828 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4830 SDValue Ptr, SDValue Val,
4831 MachineMemOperand *MMO,
4832 AtomicOrdering Ordering,
4833 SynchronizationScope SynchScope) {
4834 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4835 Opcode == ISD::ATOMIC_LOAD_SUB ||
4836 Opcode == ISD::ATOMIC_LOAD_AND ||
4837 Opcode == ISD::ATOMIC_LOAD_OR ||
4838 Opcode == ISD::ATOMIC_LOAD_XOR ||
4839 Opcode == ISD::ATOMIC_LOAD_NAND ||
4840 Opcode == ISD::ATOMIC_LOAD_MIN ||
4841 Opcode == ISD::ATOMIC_LOAD_MAX ||
4842 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4843 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4844 Opcode == ISD::ATOMIC_SWAP ||
4845 Opcode == ISD::ATOMIC_STORE) &&
4846 "Invalid Atomic Op");
4848 EVT VT = Val.getValueType();
4850 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4851 getVTList(VT, MVT::Other);
4852 SDValue Ops[] = {Chain, Ptr, Val};
4853 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4856 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4857 EVT VT, SDValue Chain,
4859 MachineMemOperand *MMO,
4860 AtomicOrdering Ordering,
4861 SynchronizationScope SynchScope) {
4862 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4864 SDVTList VTs = getVTList(VT, MVT::Other);
4865 SDValue Ops[] = {Chain, Ptr};
4866 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4869 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4870 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4871 if (Ops.size() == 1)
4874 SmallVector<EVT, 4> VTs;
4875 VTs.reserve(Ops.size());
4876 for (unsigned i = 0; i < Ops.size(); ++i)
4877 VTs.push_back(Ops[i].getValueType());
4878 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4882 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4883 ArrayRef<SDValue> Ops,
4884 EVT MemVT, MachinePointerInfo PtrInfo,
4885 unsigned Align, bool Vol,
4886 bool ReadMem, bool WriteMem, unsigned Size) {
4887 if (Align == 0) // Ensure that codegen never sees alignment 0
4888 Align = getEVTAlignment(MemVT);
4890 MachineFunction &MF = getMachineFunction();
4893 Flags |= MachineMemOperand::MOStore;
4895 Flags |= MachineMemOperand::MOLoad;
4897 Flags |= MachineMemOperand::MOVolatile;
4899 Size = MemVT.getStoreSize();
4900 MachineMemOperand *MMO =
4901 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4903 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4907 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4908 ArrayRef<SDValue> Ops, EVT MemVT,
4909 MachineMemOperand *MMO) {
4910 assert((Opcode == ISD::INTRINSIC_VOID ||
4911 Opcode == ISD::INTRINSIC_W_CHAIN ||
4912 Opcode == ISD::PREFETCH ||
4913 Opcode == ISD::LIFETIME_START ||
4914 Opcode == ISD::LIFETIME_END ||
4915 (Opcode <= INT_MAX &&
4916 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4917 "Opcode is not a memory-accessing opcode!");
4919 // Memoize the node unless it returns a flag.
4920 MemIntrinsicSDNode *N;
4921 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4922 FoldingSetNodeID ID;
4923 AddNodeIDNode(ID, Opcode, VTList, Ops);
4924 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4926 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4927 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4928 return SDValue(E, 0);
4931 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4932 dl.getDebugLoc(), VTList, Ops,
4934 CSEMap.InsertNode(N, IP);
4936 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4937 dl.getDebugLoc(), VTList, Ops,
4941 return SDValue(N, 0);
4944 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4945 /// MachinePointerInfo record from it. This is particularly useful because the
4946 /// code generator has many cases where it doesn't bother passing in a
4947 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4948 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4949 int64_t Offset = 0) {
4950 // If this is FI+Offset, we can model it.
4951 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4952 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4953 FI->getIndex(), Offset);
4955 // If this is (FI+Offset1)+Offset2, we can model it.
4956 if (Ptr.getOpcode() != ISD::ADD ||
4957 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4958 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4959 return MachinePointerInfo();
4961 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4962 return MachinePointerInfo::getFixedStack(
4963 DAG.getMachineFunction(), FI,
4964 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4967 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4968 /// MachinePointerInfo record from it. This is particularly useful because the
4969 /// code generator has many cases where it doesn't bother passing in a
4970 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4971 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4973 // If the 'Offset' value isn't a constant, we can't handle this.
4974 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4975 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4976 if (OffsetOp.getOpcode() == ISD::UNDEF)
4977 return InferPointerInfo(DAG, Ptr);
4978 return MachinePointerInfo();
4983 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4984 EVT VT, SDLoc dl, SDValue Chain,
4985 SDValue Ptr, SDValue Offset,
4986 MachinePointerInfo PtrInfo, EVT MemVT,
4987 bool isVolatile, bool isNonTemporal, bool isInvariant,
4988 unsigned Alignment, const AAMDNodes &AAInfo,
4989 const MDNode *Ranges) {
4990 assert(Chain.getValueType() == MVT::Other &&
4991 "Invalid chain type");
4992 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4993 Alignment = getEVTAlignment(VT);
4995 unsigned Flags = MachineMemOperand::MOLoad;
4997 Flags |= MachineMemOperand::MOVolatile;
4999 Flags |= MachineMemOperand::MONonTemporal;
5001 Flags |= MachineMemOperand::MOInvariant;
5003 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5005 if (PtrInfo.V.isNull())
5006 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5008 MachineFunction &MF = getMachineFunction();
5009 MachineMemOperand *MMO =
5010 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5012 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5016 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5017 EVT VT, SDLoc dl, SDValue Chain,
5018 SDValue Ptr, SDValue Offset, EVT MemVT,
5019 MachineMemOperand *MMO) {
5021 ExtType = ISD::NON_EXTLOAD;
5022 } else if (ExtType == ISD::NON_EXTLOAD) {
5023 assert(VT == MemVT && "Non-extending load from different memory type!");
5026 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5027 "Should only be an extending load, not truncating!");
5028 assert(VT.isInteger() == MemVT.isInteger() &&
5029 "Cannot convert from FP to Int or Int -> FP!");
5030 assert(VT.isVector() == MemVT.isVector() &&
5031 "Cannot use an ext load to convert to or from a vector!");
5032 assert((!VT.isVector() ||
5033 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5034 "Cannot use an ext load to change the number of vector elements!");
5037 bool Indexed = AM != ISD::UNINDEXED;
5038 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5039 "Unindexed load with an offset!");
5041 SDVTList VTs = Indexed ?
5042 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5043 SDValue Ops[] = { Chain, Ptr, Offset };
5044 FoldingSetNodeID ID;
5045 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5046 ID.AddInteger(MemVT.getRawBits());
5047 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5048 MMO->isNonTemporal(),
5049 MMO->isInvariant()));
5050 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5052 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5053 cast<LoadSDNode>(E)->refineAlignment(MMO);
5054 return SDValue(E, 0);
5056 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5057 dl.getDebugLoc(), VTs, AM, ExtType,
5059 CSEMap.InsertNode(N, IP);
5061 return SDValue(N, 0);
5064 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5065 SDValue Chain, SDValue Ptr,
5066 MachinePointerInfo PtrInfo,
5067 bool isVolatile, bool isNonTemporal,
5068 bool isInvariant, unsigned Alignment,
5069 const AAMDNodes &AAInfo,
5070 const MDNode *Ranges) {
5071 SDValue Undef = getUNDEF(Ptr.getValueType());
5072 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5073 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5077 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5078 SDValue Chain, SDValue Ptr,
5079 MachineMemOperand *MMO) {
5080 SDValue Undef = getUNDEF(Ptr.getValueType());
5081 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5085 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5086 SDValue Chain, SDValue Ptr,
5087 MachinePointerInfo PtrInfo, EVT MemVT,
5088 bool isVolatile, bool isNonTemporal,
5089 bool isInvariant, unsigned Alignment,
5090 const AAMDNodes &AAInfo) {
5091 SDValue Undef = getUNDEF(Ptr.getValueType());
5092 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5093 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5098 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5099 SDValue Chain, SDValue Ptr, EVT MemVT,
5100 MachineMemOperand *MMO) {
5101 SDValue Undef = getUNDEF(Ptr.getValueType());
5102 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5107 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5108 SDValue Offset, ISD::MemIndexedMode AM) {
5109 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5110 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5111 "Load is already a indexed load!");
5112 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5113 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5114 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5115 false, LD->getAlignment());
5118 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5119 SDValue Ptr, MachinePointerInfo PtrInfo,
5120 bool isVolatile, bool isNonTemporal,
5121 unsigned Alignment, const AAMDNodes &AAInfo) {
5122 assert(Chain.getValueType() == MVT::Other &&
5123 "Invalid chain type");
5124 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5125 Alignment = getEVTAlignment(Val.getValueType());
5127 unsigned Flags = MachineMemOperand::MOStore;
5129 Flags |= MachineMemOperand::MOVolatile;
5131 Flags |= MachineMemOperand::MONonTemporal;
5133 if (PtrInfo.V.isNull())
5134 PtrInfo = InferPointerInfo(*this, Ptr);
5136 MachineFunction &MF = getMachineFunction();
5137 MachineMemOperand *MMO =
5138 MF.getMachineMemOperand(PtrInfo, Flags,
5139 Val.getValueType().getStoreSize(), Alignment,
5142 return getStore(Chain, dl, Val, Ptr, MMO);
5145 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5146 SDValue Ptr, MachineMemOperand *MMO) {
5147 assert(Chain.getValueType() == MVT::Other &&
5148 "Invalid chain type");
5149 EVT VT = Val.getValueType();
5150 SDVTList VTs = getVTList(MVT::Other);
5151 SDValue Undef = getUNDEF(Ptr.getValueType());
5152 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5153 FoldingSetNodeID ID;
5154 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5155 ID.AddInteger(VT.getRawBits());
5156 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5157 MMO->isNonTemporal(), MMO->isInvariant()));
5158 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5160 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5161 cast<StoreSDNode>(E)->refineAlignment(MMO);
5162 return SDValue(E, 0);
5164 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5165 dl.getDebugLoc(), VTs,
5166 ISD::UNINDEXED, false, VT, MMO);
5167 CSEMap.InsertNode(N, IP);
5169 return SDValue(N, 0);
5172 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5173 SDValue Ptr, MachinePointerInfo PtrInfo,
5174 EVT SVT,bool isVolatile, bool isNonTemporal,
5176 const AAMDNodes &AAInfo) {
5177 assert(Chain.getValueType() == MVT::Other &&
5178 "Invalid chain type");
5179 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5180 Alignment = getEVTAlignment(SVT);
5182 unsigned Flags = MachineMemOperand::MOStore;
5184 Flags |= MachineMemOperand::MOVolatile;
5186 Flags |= MachineMemOperand::MONonTemporal;
5188 if (PtrInfo.V.isNull())
5189 PtrInfo = InferPointerInfo(*this, Ptr);
5191 MachineFunction &MF = getMachineFunction();
5192 MachineMemOperand *MMO =
5193 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5196 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5199 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5200 SDValue Ptr, EVT SVT,
5201 MachineMemOperand *MMO) {
5202 EVT VT = Val.getValueType();
5204 assert(Chain.getValueType() == MVT::Other &&
5205 "Invalid chain type");
5207 return getStore(Chain, dl, Val, Ptr, MMO);
5209 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5210 "Should only be a truncating store, not extending!");
5211 assert(VT.isInteger() == SVT.isInteger() &&
5212 "Can't do FP-INT conversion!");
5213 assert(VT.isVector() == SVT.isVector() &&
5214 "Cannot use trunc store to convert to or from a vector!");
5215 assert((!VT.isVector() ||
5216 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5217 "Cannot use trunc store to change the number of vector elements!");
5219 SDVTList VTs = getVTList(MVT::Other);
5220 SDValue Undef = getUNDEF(Ptr.getValueType());
5221 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5222 FoldingSetNodeID ID;
5223 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5224 ID.AddInteger(SVT.getRawBits());
5225 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5226 MMO->isNonTemporal(), MMO->isInvariant()));
5227 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5229 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5230 cast<StoreSDNode>(E)->refineAlignment(MMO);
5231 return SDValue(E, 0);
5233 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5234 dl.getDebugLoc(), VTs,
5235 ISD::UNINDEXED, true, SVT, MMO);
5236 CSEMap.InsertNode(N, IP);
5238 return SDValue(N, 0);
5242 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5243 SDValue Offset, ISD::MemIndexedMode AM) {
5244 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5245 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5246 "Store is already a indexed store!");
5247 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5248 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5249 FoldingSetNodeID ID;
5250 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5251 ID.AddInteger(ST->getMemoryVT().getRawBits());
5252 ID.AddInteger(ST->getRawSubclassData());
5253 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5255 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5256 return SDValue(E, 0);
5258 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5259 dl.getDebugLoc(), VTs, AM,
5260 ST->isTruncatingStore(),
5262 ST->getMemOperand());
5263 CSEMap.InsertNode(N, IP);
5265 return SDValue(N, 0);
5269 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5270 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5271 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5273 SDVTList VTs = getVTList(VT, MVT::Other);
5274 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5275 FoldingSetNodeID ID;
5276 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5277 ID.AddInteger(VT.getRawBits());
5278 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5280 MMO->isNonTemporal(),
5281 MMO->isInvariant()));
5282 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5284 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5285 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5286 return SDValue(E, 0);
5288 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5289 dl.getDebugLoc(), Ops, 4, VTs,
5291 CSEMap.InsertNode(N, IP);
5293 return SDValue(N, 0);
5296 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5297 SDValue Ptr, SDValue Mask, EVT MemVT,
5298 MachineMemOperand *MMO, bool isTrunc) {
5299 assert(Chain.getValueType() == MVT::Other &&
5300 "Invalid chain type");
5301 EVT VT = Val.getValueType();
5302 SDVTList VTs = getVTList(MVT::Other);
5303 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5304 FoldingSetNodeID ID;
5305 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5306 ID.AddInteger(VT.getRawBits());
5307 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5308 MMO->isNonTemporal(), MMO->isInvariant()));
5309 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5311 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5312 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5313 return SDValue(E, 0);
5315 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5316 dl.getDebugLoc(), Ops, 4,
5317 VTs, isTrunc, MemVT, MMO);
5318 CSEMap.InsertNode(N, IP);
5320 return SDValue(N, 0);
5324 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5325 ArrayRef<SDValue> Ops,
5326 MachineMemOperand *MMO) {
5328 FoldingSetNodeID ID;
5329 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5330 ID.AddInteger(VT.getRawBits());
5331 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5333 MMO->isNonTemporal(),
5334 MMO->isInvariant()));
5335 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5337 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5338 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5339 return SDValue(E, 0);
5341 MaskedGatherSDNode *N =
5342 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5344 CSEMap.InsertNode(N, IP);
5346 return SDValue(N, 0);
5349 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5350 ArrayRef<SDValue> Ops,
5351 MachineMemOperand *MMO) {
5352 FoldingSetNodeID ID;
5353 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5354 ID.AddInteger(VT.getRawBits());
5355 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5356 MMO->isNonTemporal(),
5357 MMO->isInvariant()));
5358 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5360 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5361 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5362 return SDValue(E, 0);
5365 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5367 CSEMap.InsertNode(N, IP);
5369 return SDValue(N, 0);
5372 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5373 SDValue Chain, SDValue Ptr,
5376 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5377 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5380 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5381 ArrayRef<SDUse> Ops) {
5382 switch (Ops.size()) {
5383 case 0: return getNode(Opcode, DL, VT);
5384 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5385 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5386 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5390 // Copy from an SDUse array into an SDValue array for use with
5391 // the regular getNode logic.
5392 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5393 return getNode(Opcode, DL, VT, NewOps);
5396 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5397 ArrayRef<SDValue> Ops) {
5398 unsigned NumOps = Ops.size();
5400 case 0: return getNode(Opcode, DL, VT);
5401 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5402 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5403 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5409 case ISD::SELECT_CC: {
5410 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5411 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5412 "LHS and RHS of condition must have same type!");
5413 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5414 "True and False arms of SelectCC must have same type!");
5415 assert(Ops[2].getValueType() == VT &&
5416 "select_cc node must be of same type as true and false value!");
5420 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5421 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5422 "LHS/RHS of comparison should match types!");
5429 SDVTList VTs = getVTList(VT);
5431 if (VT != MVT::Glue) {
5432 FoldingSetNodeID ID;
5433 AddNodeIDNode(ID, Opcode, VTs, Ops);
5436 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5437 return SDValue(E, 0);
5439 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5441 CSEMap.InsertNode(N, IP);
5443 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5448 return SDValue(N, 0);
5451 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5452 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5453 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5456 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5457 ArrayRef<SDValue> Ops) {
5458 if (VTList.NumVTs == 1)
5459 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5463 // FIXME: figure out how to safely handle things like
5464 // int foo(int x) { return 1 << (x & 255); }
5465 // int bar() { return foo(256); }
5466 case ISD::SRA_PARTS:
5467 case ISD::SRL_PARTS:
5468 case ISD::SHL_PARTS:
5469 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5470 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5471 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5472 else if (N3.getOpcode() == ISD::AND)
5473 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5474 // If the and is only masking out bits that cannot effect the shift,
5475 // eliminate the and.
5476 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5477 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5478 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5484 // Memoize the node unless it returns a flag.
5486 unsigned NumOps = Ops.size();
5487 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5488 FoldingSetNodeID ID;
5489 AddNodeIDNode(ID, Opcode, VTList, Ops);
5491 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5492 return SDValue(E, 0);
5495 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5496 DL.getDebugLoc(), VTList, Ops[0]);
5497 } else if (NumOps == 2) {
5498 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5499 DL.getDebugLoc(), VTList, Ops[0],
5501 } else if (NumOps == 3) {
5502 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5503 DL.getDebugLoc(), VTList, Ops[0],
5506 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5509 CSEMap.InsertNode(N, IP);
5512 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5513 DL.getDebugLoc(), VTList, Ops[0]);
5514 } else if (NumOps == 2) {
5515 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5516 DL.getDebugLoc(), VTList, Ops[0],
5518 } else if (NumOps == 3) {
5519 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5520 DL.getDebugLoc(), VTList, Ops[0],
5523 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5528 return SDValue(N, 0);
5531 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5532 return getNode(Opcode, DL, VTList, None);
5535 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5537 SDValue Ops[] = { N1 };
5538 return getNode(Opcode, DL, VTList, Ops);
5541 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5542 SDValue N1, SDValue N2) {
5543 SDValue Ops[] = { N1, N2 };
5544 return getNode(Opcode, DL, VTList, Ops);
5547 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5548 SDValue N1, SDValue N2, SDValue N3) {
5549 SDValue Ops[] = { N1, N2, N3 };
5550 return getNode(Opcode, DL, VTList, Ops);
5553 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5554 SDValue N1, SDValue N2, SDValue N3,
5556 SDValue Ops[] = { N1, N2, N3, N4 };
5557 return getNode(Opcode, DL, VTList, Ops);
5560 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5561 SDValue N1, SDValue N2, SDValue N3,
5562 SDValue N4, SDValue N5) {
5563 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5564 return getNode(Opcode, DL, VTList, Ops);
5567 SDVTList SelectionDAG::getVTList(EVT VT) {
5568 return makeVTList(SDNode::getValueTypeList(VT), 1);
5571 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5572 FoldingSetNodeID ID;
5574 ID.AddInteger(VT1.getRawBits());
5575 ID.AddInteger(VT2.getRawBits());
5578 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5580 EVT *Array = Allocator.Allocate<EVT>(2);
5583 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5584 VTListMap.InsertNode(Result, IP);
5586 return Result->getSDVTList();
5589 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5590 FoldingSetNodeID ID;
5592 ID.AddInteger(VT1.getRawBits());
5593 ID.AddInteger(VT2.getRawBits());
5594 ID.AddInteger(VT3.getRawBits());
5597 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5599 EVT *Array = Allocator.Allocate<EVT>(3);
5603 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5604 VTListMap.InsertNode(Result, IP);
5606 return Result->getSDVTList();
5609 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5610 FoldingSetNodeID ID;
5612 ID.AddInteger(VT1.getRawBits());
5613 ID.AddInteger(VT2.getRawBits());
5614 ID.AddInteger(VT3.getRawBits());
5615 ID.AddInteger(VT4.getRawBits());
5618 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5620 EVT *Array = Allocator.Allocate<EVT>(4);
5625 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5626 VTListMap.InsertNode(Result, IP);
5628 return Result->getSDVTList();
5631 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5632 unsigned NumVTs = VTs.size();
5633 FoldingSetNodeID ID;
5634 ID.AddInteger(NumVTs);
5635 for (unsigned index = 0; index < NumVTs; index++) {
5636 ID.AddInteger(VTs[index].getRawBits());
5640 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5642 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5643 std::copy(VTs.begin(), VTs.end(), Array);
5644 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5645 VTListMap.InsertNode(Result, IP);
5647 return Result->getSDVTList();
5651 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5652 /// specified operands. If the resultant node already exists in the DAG,
5653 /// this does not modify the specified node, instead it returns the node that
5654 /// already exists. If the resultant node does not exist in the DAG, the
5655 /// input node is returned. As a degenerate case, if you specify the same
5656 /// input operands as the node already has, the input node is returned.
5657 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5658 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5660 // Check to see if there is no change.
5661 if (Op == N->getOperand(0)) return N;
5663 // See if the modified node already exists.
5664 void *InsertPos = nullptr;
5665 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5668 // Nope it doesn't. Remove the node from its current place in the maps.
5670 if (!RemoveNodeFromCSEMaps(N))
5671 InsertPos = nullptr;
5673 // Now we update the operands.
5674 N->OperandList[0].set(Op);
5676 // If this gets put into a CSE map, add it.
5677 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5681 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5682 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5684 // Check to see if there is no change.
5685 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5686 return N; // No operands changed, just return the input node.
5688 // See if the modified node already exists.
5689 void *InsertPos = nullptr;
5690 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5693 // Nope it doesn't. Remove the node from its current place in the maps.
5695 if (!RemoveNodeFromCSEMaps(N))
5696 InsertPos = nullptr;
5698 // Now we update the operands.
5699 if (N->OperandList[0] != Op1)
5700 N->OperandList[0].set(Op1);
5701 if (N->OperandList[1] != Op2)
5702 N->OperandList[1].set(Op2);
5704 // If this gets put into a CSE map, add it.
5705 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5709 SDNode *SelectionDAG::
5710 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5711 SDValue Ops[] = { Op1, Op2, Op3 };
5712 return UpdateNodeOperands(N, Ops);
5715 SDNode *SelectionDAG::
5716 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5717 SDValue Op3, SDValue Op4) {
5718 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5719 return UpdateNodeOperands(N, Ops);
5722 SDNode *SelectionDAG::
5723 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5724 SDValue Op3, SDValue Op4, SDValue Op5) {
5725 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5726 return UpdateNodeOperands(N, Ops);
5729 SDNode *SelectionDAG::
5730 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5731 unsigned NumOps = Ops.size();
5732 assert(N->getNumOperands() == NumOps &&
5733 "Update with wrong number of operands");
5735 // If no operands changed just return the input node.
5736 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5739 // See if the modified node already exists.
5740 void *InsertPos = nullptr;
5741 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5744 // Nope it doesn't. Remove the node from its current place in the maps.
5746 if (!RemoveNodeFromCSEMaps(N))
5747 InsertPos = nullptr;
5749 // Now we update the operands.
5750 for (unsigned i = 0; i != NumOps; ++i)
5751 if (N->OperandList[i] != Ops[i])
5752 N->OperandList[i].set(Ops[i]);
5754 // If this gets put into a CSE map, add it.
5755 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5759 /// DropOperands - Release the operands and set this node to have
5761 void SDNode::DropOperands() {
5762 // Unlike the code in MorphNodeTo that does this, we don't need to
5763 // watch for dead nodes here.
5764 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5770 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5773 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5775 SDVTList VTs = getVTList(VT);
5776 return SelectNodeTo(N, MachineOpc, VTs, None);
5779 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5780 EVT VT, SDValue Op1) {
5781 SDVTList VTs = getVTList(VT);
5782 SDValue Ops[] = { Op1 };
5783 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5786 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5787 EVT VT, SDValue Op1,
5789 SDVTList VTs = getVTList(VT);
5790 SDValue Ops[] = { Op1, Op2 };
5791 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5794 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5795 EVT VT, SDValue Op1,
5796 SDValue Op2, SDValue Op3) {
5797 SDVTList VTs = getVTList(VT);
5798 SDValue Ops[] = { Op1, Op2, Op3 };
5799 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5802 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5803 EVT VT, ArrayRef<SDValue> Ops) {
5804 SDVTList VTs = getVTList(VT);
5805 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5808 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5809 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5810 SDVTList VTs = getVTList(VT1, VT2);
5811 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5814 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5816 SDVTList VTs = getVTList(VT1, VT2);
5817 return SelectNodeTo(N, MachineOpc, VTs, None);
5820 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5821 EVT VT1, EVT VT2, EVT VT3,
5822 ArrayRef<SDValue> Ops) {
5823 SDVTList VTs = getVTList(VT1, VT2, VT3);
5824 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5827 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5828 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5829 ArrayRef<SDValue> Ops) {
5830 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5831 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5834 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5837 SDVTList VTs = getVTList(VT1, VT2);
5838 SDValue Ops[] = { Op1 };
5839 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5842 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5844 SDValue Op1, SDValue Op2) {
5845 SDVTList VTs = getVTList(VT1, VT2);
5846 SDValue Ops[] = { Op1, Op2 };
5847 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5850 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5852 SDValue Op1, SDValue Op2,
5854 SDVTList VTs = getVTList(VT1, VT2);
5855 SDValue Ops[] = { Op1, Op2, Op3 };
5856 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5859 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5860 EVT VT1, EVT VT2, EVT VT3,
5861 SDValue Op1, SDValue Op2,
5863 SDVTList VTs = getVTList(VT1, VT2, VT3);
5864 SDValue Ops[] = { Op1, Op2, Op3 };
5865 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5868 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5869 SDVTList VTs,ArrayRef<SDValue> Ops) {
5870 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5871 // Reset the NodeID to -1.
5876 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5877 /// the line number information on the merged node since it is not possible to
5878 /// preserve the information that operation is associated with multiple lines.
5879 /// This will make the debugger working better at -O0, were there is a higher
5880 /// probability having other instructions associated with that line.
5882 /// For IROrder, we keep the smaller of the two
5883 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5884 DebugLoc NLoc = N->getDebugLoc();
5885 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5886 N->setDebugLoc(DebugLoc());
5888 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5889 N->setIROrder(Order);
5893 /// MorphNodeTo - This *mutates* the specified node to have the specified
5894 /// return type, opcode, and operands.
5896 /// Note that MorphNodeTo returns the resultant node. If there is already a
5897 /// node of the specified opcode and operands, it returns that node instead of
5898 /// the current one. Note that the SDLoc need not be the same.
5900 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5901 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5902 /// node, and because it doesn't require CSE recalculation for any of
5903 /// the node's users.
5905 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5906 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5907 /// the legalizer which maintain worklists that would need to be updated when
5908 /// deleting things.
5909 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5910 SDVTList VTs, ArrayRef<SDValue> Ops) {
5911 unsigned NumOps = Ops.size();
5912 // If an identical node already exists, use it.
5914 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5915 FoldingSetNodeID ID;
5916 AddNodeIDNode(ID, Opc, VTs, Ops);
5917 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5918 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5921 if (!RemoveNodeFromCSEMaps(N))
5924 // Start the morphing.
5926 N->ValueList = VTs.VTs;
5927 N->NumValues = VTs.NumVTs;
5929 // Clear the operands list, updating used nodes to remove this from their
5930 // use list. Keep track of any operands that become dead as a result.
5931 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5932 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5934 SDNode *Used = Use.getNode();
5936 if (Used->use_empty())
5937 DeadNodeSet.insert(Used);
5940 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5941 // Initialize the memory references information.
5942 MN->setMemRefs(nullptr, nullptr);
5943 // If NumOps is larger than the # of operands we can have in a
5944 // MachineSDNode, reallocate the operand list.
5945 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5946 if (MN->OperandsNeedDelete)
5947 delete[] MN->OperandList;
5948 if (NumOps > array_lengthof(MN->LocalOperands))
5949 // We're creating a final node that will live unmorphed for the
5950 // remainder of the current SelectionDAG iteration, so we can allocate
5951 // the operands directly out of a pool with no recycling metadata.
5952 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5953 Ops.data(), NumOps);
5955 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5956 MN->OperandsNeedDelete = false;
5958 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5960 // If NumOps is larger than the # of operands we currently have, reallocate
5961 // the operand list.
5962 if (NumOps > N->NumOperands) {
5963 if (N->OperandsNeedDelete)
5964 delete[] N->OperandList;
5965 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5966 N->OperandsNeedDelete = true;
5968 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5971 // Delete any nodes that are still dead after adding the uses for the
5973 if (!DeadNodeSet.empty()) {
5974 SmallVector<SDNode *, 16> DeadNodes;
5975 for (SDNode *N : DeadNodeSet)
5977 DeadNodes.push_back(N);
5978 RemoveDeadNodes(DeadNodes);
5982 CSEMap.InsertNode(N, IP); // Memoize the new node.
5987 /// getMachineNode - These are used for target selectors to create a new node
5988 /// with specified return type(s), MachineInstr opcode, and operands.
5990 /// Note that getMachineNode returns the resultant node. If there is already a
5991 /// node of the specified opcode and operands, it returns that node instead of
5992 /// the current one.
5994 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5995 SDVTList VTs = getVTList(VT);
5996 return getMachineNode(Opcode, dl, VTs, None);
6000 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6001 SDVTList VTs = getVTList(VT);
6002 SDValue Ops[] = { Op1 };
6003 return getMachineNode(Opcode, dl, VTs, Ops);
6007 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6008 SDValue Op1, SDValue Op2) {
6009 SDVTList VTs = getVTList(VT);
6010 SDValue Ops[] = { Op1, Op2 };
6011 return getMachineNode(Opcode, dl, VTs, Ops);
6015 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6016 SDValue Op1, SDValue Op2, SDValue Op3) {
6017 SDVTList VTs = getVTList(VT);
6018 SDValue Ops[] = { Op1, Op2, Op3 };
6019 return getMachineNode(Opcode, dl, VTs, Ops);
6023 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6024 ArrayRef<SDValue> Ops) {
6025 SDVTList VTs = getVTList(VT);
6026 return getMachineNode(Opcode, dl, VTs, Ops);
6030 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6031 SDVTList VTs = getVTList(VT1, VT2);
6032 return getMachineNode(Opcode, dl, VTs, None);
6036 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6037 EVT VT1, EVT VT2, SDValue Op1) {
6038 SDVTList VTs = getVTList(VT1, VT2);
6039 SDValue Ops[] = { Op1 };
6040 return getMachineNode(Opcode, dl, VTs, Ops);
6044 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6045 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6046 SDVTList VTs = getVTList(VT1, VT2);
6047 SDValue Ops[] = { Op1, Op2 };
6048 return getMachineNode(Opcode, dl, VTs, Ops);
6052 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6053 EVT VT1, EVT VT2, SDValue Op1,
6054 SDValue Op2, SDValue Op3) {
6055 SDVTList VTs = getVTList(VT1, VT2);
6056 SDValue Ops[] = { Op1, Op2, Op3 };
6057 return getMachineNode(Opcode, dl, VTs, Ops);
6061 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6063 ArrayRef<SDValue> Ops) {
6064 SDVTList VTs = getVTList(VT1, VT2);
6065 return getMachineNode(Opcode, dl, VTs, Ops);
6069 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6070 EVT VT1, EVT VT2, EVT VT3,
6071 SDValue Op1, SDValue Op2) {
6072 SDVTList VTs = getVTList(VT1, VT2, VT3);
6073 SDValue Ops[] = { Op1, Op2 };
6074 return getMachineNode(Opcode, dl, VTs, Ops);
6078 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6079 EVT VT1, EVT VT2, EVT VT3,
6080 SDValue Op1, SDValue Op2, SDValue Op3) {
6081 SDVTList VTs = getVTList(VT1, VT2, VT3);
6082 SDValue Ops[] = { Op1, Op2, Op3 };
6083 return getMachineNode(Opcode, dl, VTs, Ops);
6087 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6088 EVT VT1, EVT VT2, EVT VT3,
6089 ArrayRef<SDValue> Ops) {
6090 SDVTList VTs = getVTList(VT1, VT2, VT3);
6091 return getMachineNode(Opcode, dl, VTs, Ops);
6095 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6096 EVT VT2, EVT VT3, EVT VT4,
6097 ArrayRef<SDValue> Ops) {
6098 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6099 return getMachineNode(Opcode, dl, VTs, Ops);
6103 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6104 ArrayRef<EVT> ResultTys,
6105 ArrayRef<SDValue> Ops) {
6106 SDVTList VTs = getVTList(ResultTys);
6107 return getMachineNode(Opcode, dl, VTs, Ops);
6111 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6112 ArrayRef<SDValue> OpsArray) {
6113 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6116 const SDValue *Ops = OpsArray.data();
6117 unsigned NumOps = OpsArray.size();
6120 FoldingSetNodeID ID;
6121 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6123 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6124 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6128 // Allocate a new MachineSDNode.
6129 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6130 DL.getDebugLoc(), VTs);
6132 // Initialize the operands list.
6133 if (NumOps > array_lengthof(N->LocalOperands))
6134 // We're creating a final node that will live unmorphed for the
6135 // remainder of the current SelectionDAG iteration, so we can allocate
6136 // the operands directly out of a pool with no recycling metadata.
6137 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6140 N->InitOperands(N->LocalOperands, Ops, NumOps);
6141 N->OperandsNeedDelete = false;
6144 CSEMap.InsertNode(N, IP);
6150 /// getTargetExtractSubreg - A convenience function for creating
6151 /// TargetOpcode::EXTRACT_SUBREG nodes.
6153 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6155 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6156 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6157 VT, Operand, SRIdxVal);
6158 return SDValue(Subreg, 0);
6161 /// getTargetInsertSubreg - A convenience function for creating
6162 /// TargetOpcode::INSERT_SUBREG nodes.
6164 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6165 SDValue Operand, SDValue Subreg) {
6166 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6167 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6168 VT, Operand, Subreg, SRIdxVal);
6169 return SDValue(Result, 0);
6172 /// getNodeIfExists - Get the specified node if it's already available, or
6173 /// else return NULL.
6174 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6175 ArrayRef<SDValue> Ops,
6176 const SDNodeFlags *Flags) {
6177 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6178 FoldingSetNodeID ID;
6179 AddNodeIDNode(ID, Opcode, VTList, Ops);
6180 AddNodeIDFlags(ID, Opcode, Flags);
6182 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6188 /// getDbgValue - Creates a SDDbgValue node.
6191 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6192 unsigned R, bool IsIndirect, uint64_t Off,
6193 DebugLoc DL, unsigned O) {
6194 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6195 "Expected inlined-at fields to agree");
6196 return new (DbgInfo->getAlloc())
6197 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6201 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6202 const Value *C, uint64_t Off,
6203 DebugLoc DL, unsigned O) {
6204 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6205 "Expected inlined-at fields to agree");
6206 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6210 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6211 unsigned FI, uint64_t Off,
6212 DebugLoc DL, unsigned O) {
6213 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6214 "Expected inlined-at fields to agree");
6215 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6220 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6221 /// pointed to by a use iterator is deleted, increment the use iterator
6222 /// so that it doesn't dangle.
6224 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6225 SDNode::use_iterator &UI;
6226 SDNode::use_iterator &UE;
6228 void NodeDeleted(SDNode *N, SDNode *E) override {
6229 // Increment the iterator as needed.
6230 while (UI != UE && N == *UI)
6235 RAUWUpdateListener(SelectionDAG &d,
6236 SDNode::use_iterator &ui,
6237 SDNode::use_iterator &ue)
6238 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6243 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6244 /// This can cause recursive merging of nodes in the DAG.
6246 /// This version assumes From has a single result value.
6248 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6249 SDNode *From = FromN.getNode();
6250 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6251 "Cannot replace with this method!");
6252 assert(From != To.getNode() && "Cannot replace uses of with self");
6254 // Iterate over all the existing uses of From. New uses will be added
6255 // to the beginning of the use list, which we avoid visiting.
6256 // This specifically avoids visiting uses of From that arise while the
6257 // replacement is happening, because any such uses would be the result
6258 // of CSE: If an existing node looks like From after one of its operands
6259 // is replaced by To, we don't want to replace of all its users with To
6260 // too. See PR3018 for more info.
6261 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6262 RAUWUpdateListener Listener(*this, UI, UE);
6266 // This node is about to morph, remove its old self from the CSE maps.
6267 RemoveNodeFromCSEMaps(User);
6269 // A user can appear in a use list multiple times, and when this
6270 // happens the uses are usually next to each other in the list.
6271 // To help reduce the number of CSE recomputations, process all
6272 // the uses of this user that we can find this way.
6274 SDUse &Use = UI.getUse();
6277 } while (UI != UE && *UI == User);
6279 // Now that we have modified User, add it back to the CSE maps. If it
6280 // already exists there, recursively merge the results together.
6281 AddModifiedNodeToCSEMaps(User);
6284 // If we just RAUW'd the root, take note.
6285 if (FromN == getRoot())
6289 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6290 /// This can cause recursive merging of nodes in the DAG.
6292 /// This version assumes that for each value of From, there is a
6293 /// corresponding value in To in the same position with the same type.
6295 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6297 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6298 assert((!From->hasAnyUseOfValue(i) ||
6299 From->getValueType(i) == To->getValueType(i)) &&
6300 "Cannot use this version of ReplaceAllUsesWith!");
6303 // Handle the trivial case.
6307 // Iterate over just the existing users of From. See the comments in
6308 // the ReplaceAllUsesWith above.
6309 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6310 RAUWUpdateListener Listener(*this, UI, UE);
6314 // This node is about to morph, remove its old self from the CSE maps.
6315 RemoveNodeFromCSEMaps(User);
6317 // A user can appear in a use list multiple times, and when this
6318 // happens the uses are usually next to each other in the list.
6319 // To help reduce the number of CSE recomputations, process all
6320 // the uses of this user that we can find this way.
6322 SDUse &Use = UI.getUse();
6325 } while (UI != UE && *UI == User);
6327 // Now that we have modified User, add it back to the CSE maps. If it
6328 // already exists there, recursively merge the results together.
6329 AddModifiedNodeToCSEMaps(User);
6332 // If we just RAUW'd the root, take note.
6333 if (From == getRoot().getNode())
6334 setRoot(SDValue(To, getRoot().getResNo()));
6337 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6338 /// This can cause recursive merging of nodes in the DAG.
6340 /// This version can replace From with any result values. To must match the
6341 /// number and types of values returned by From.
6342 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6343 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6344 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6346 // Iterate over just the existing users of From. See the comments in
6347 // the ReplaceAllUsesWith above.
6348 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6349 RAUWUpdateListener Listener(*this, UI, UE);
6353 // This node is about to morph, remove its old self from the CSE maps.
6354 RemoveNodeFromCSEMaps(User);
6356 // A user can appear in a use list multiple times, and when this
6357 // happens the uses are usually next to each other in the list.
6358 // To help reduce the number of CSE recomputations, process all
6359 // the uses of this user that we can find this way.
6361 SDUse &Use = UI.getUse();
6362 const SDValue &ToOp = To[Use.getResNo()];
6365 } while (UI != UE && *UI == User);
6367 // Now that we have modified User, add it back to the CSE maps. If it
6368 // already exists there, recursively merge the results together.
6369 AddModifiedNodeToCSEMaps(User);
6372 // If we just RAUW'd the root, take note.
6373 if (From == getRoot().getNode())
6374 setRoot(SDValue(To[getRoot().getResNo()]));
6377 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6378 /// uses of other values produced by From.getNode() alone. The Deleted
6379 /// vector is handled the same way as for ReplaceAllUsesWith.
6380 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6381 // Handle the really simple, really trivial case efficiently.
6382 if (From == To) return;
6384 // Handle the simple, trivial, case efficiently.
6385 if (From.getNode()->getNumValues() == 1) {
6386 ReplaceAllUsesWith(From, To);
6390 // Iterate over just the existing users of From. See the comments in
6391 // the ReplaceAllUsesWith above.
6392 SDNode::use_iterator UI = From.getNode()->use_begin(),
6393 UE = From.getNode()->use_end();
6394 RAUWUpdateListener Listener(*this, UI, UE);
6397 bool UserRemovedFromCSEMaps = false;
6399 // A user can appear in a use list multiple times, and when this
6400 // happens the uses are usually next to each other in the list.
6401 // To help reduce the number of CSE recomputations, process all
6402 // the uses of this user that we can find this way.
6404 SDUse &Use = UI.getUse();
6406 // Skip uses of different values from the same node.
6407 if (Use.getResNo() != From.getResNo()) {
6412 // If this node hasn't been modified yet, it's still in the CSE maps,
6413 // so remove its old self from the CSE maps.
6414 if (!UserRemovedFromCSEMaps) {
6415 RemoveNodeFromCSEMaps(User);
6416 UserRemovedFromCSEMaps = true;
6421 } while (UI != UE && *UI == User);
6423 // We are iterating over all uses of the From node, so if a use
6424 // doesn't use the specific value, no changes are made.
6425 if (!UserRemovedFromCSEMaps)
6428 // Now that we have modified User, add it back to the CSE maps. If it
6429 // already exists there, recursively merge the results together.
6430 AddModifiedNodeToCSEMaps(User);
6433 // If we just RAUW'd the root, take note.
6434 if (From == getRoot())
6439 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6440 /// to record information about a use.
6447 /// operator< - Sort Memos by User.
6448 bool operator<(const UseMemo &L, const UseMemo &R) {
6449 return (intptr_t)L.User < (intptr_t)R.User;
6453 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6454 /// uses of other values produced by From.getNode() alone. The same value
6455 /// may appear in both the From and To list. The Deleted vector is
6456 /// handled the same way as for ReplaceAllUsesWith.
6457 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6460 // Handle the simple, trivial case efficiently.
6462 return ReplaceAllUsesOfValueWith(*From, *To);
6464 // Read up all the uses and make records of them. This helps
6465 // processing new uses that are introduced during the
6466 // replacement process.
6467 SmallVector<UseMemo, 4> Uses;
6468 for (unsigned i = 0; i != Num; ++i) {
6469 unsigned FromResNo = From[i].getResNo();
6470 SDNode *FromNode = From[i].getNode();
6471 for (SDNode::use_iterator UI = FromNode->use_begin(),
6472 E = FromNode->use_end(); UI != E; ++UI) {
6473 SDUse &Use = UI.getUse();
6474 if (Use.getResNo() == FromResNo) {
6475 UseMemo Memo = { *UI, i, &Use };
6476 Uses.push_back(Memo);
6481 // Sort the uses, so that all the uses from a given User are together.
6482 std::sort(Uses.begin(), Uses.end());
6484 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6485 UseIndex != UseIndexEnd; ) {
6486 // We know that this user uses some value of From. If it is the right
6487 // value, update it.
6488 SDNode *User = Uses[UseIndex].User;
6490 // This node is about to morph, remove its old self from the CSE maps.
6491 RemoveNodeFromCSEMaps(User);
6493 // The Uses array is sorted, so all the uses for a given User
6494 // are next to each other in the list.
6495 // To help reduce the number of CSE recomputations, process all
6496 // the uses of this user that we can find this way.
6498 unsigned i = Uses[UseIndex].Index;
6499 SDUse &Use = *Uses[UseIndex].Use;
6503 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6505 // Now that we have modified User, add it back to the CSE maps. If it
6506 // already exists there, recursively merge the results together.
6507 AddModifiedNodeToCSEMaps(User);
6511 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6512 /// based on their topological order. It returns the maximum id and a vector
6513 /// of the SDNodes* in assigned order by reference.
6514 unsigned SelectionDAG::AssignTopologicalOrder() {
6516 unsigned DAGSize = 0;
6518 // SortedPos tracks the progress of the algorithm. Nodes before it are
6519 // sorted, nodes after it are unsorted. When the algorithm completes
6520 // it is at the end of the list.
6521 allnodes_iterator SortedPos = allnodes_begin();
6523 // Visit all the nodes. Move nodes with no operands to the front of
6524 // the list immediately. Annotate nodes that do have operands with their
6525 // operand count. Before we do this, the Node Id fields of the nodes
6526 // may contain arbitrary values. After, the Node Id fields for nodes
6527 // before SortedPos will contain the topological sort index, and the
6528 // Node Id fields for nodes At SortedPos and after will contain the
6529 // count of outstanding operands.
6530 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6532 checkForCycles(N, this);
6533 unsigned Degree = N->getNumOperands();
6535 // A node with no uses, add it to the result array immediately.
6536 N->setNodeId(DAGSize++);
6537 allnodes_iterator Q = N;
6539 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6540 assert(SortedPos != AllNodes.end() && "Overran node list");
6543 // Temporarily use the Node Id as scratch space for the degree count.
6544 N->setNodeId(Degree);
6548 // Visit all the nodes. As we iterate, move nodes into sorted order,
6549 // such that by the time the end is reached all nodes will be sorted.
6550 for (SDNode &Node : allnodes()) {
6552 checkForCycles(N, this);
6553 // N is in sorted position, so all its uses have one less operand
6554 // that needs to be sorted.
6555 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6558 unsigned Degree = P->getNodeId();
6559 assert(Degree != 0 && "Invalid node degree");
6562 // All of P's operands are sorted, so P may sorted now.
6563 P->setNodeId(DAGSize++);
6565 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6566 assert(SortedPos != AllNodes.end() && "Overran node list");
6569 // Update P's outstanding operand count.
6570 P->setNodeId(Degree);
6573 if (&Node == SortedPos) {
6575 allnodes_iterator I = N;
6577 dbgs() << "Overran sorted position:\n";
6578 S->dumprFull(this); dbgs() << "\n";
6579 dbgs() << "Checking if this is due to cycles\n";
6580 checkForCycles(this, true);
6582 llvm_unreachable(nullptr);
6586 assert(SortedPos == AllNodes.end() &&
6587 "Topological sort incomplete!");
6588 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6589 "First node in topological sort is not the entry token!");
6590 assert(AllNodes.front().getNodeId() == 0 &&
6591 "First node in topological sort has non-zero id!");
6592 assert(AllNodes.front().getNumOperands() == 0 &&
6593 "First node in topological sort has operands!");
6594 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6595 "Last node in topologic sort has unexpected id!");
6596 assert(AllNodes.back().use_empty() &&
6597 "Last node in topologic sort has users!");
6598 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6602 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6603 /// value is produced by SD.
6604 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6606 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6607 SD->setHasDebugValue(true);
6609 DbgInfo->add(DB, SD, isParameter);
6612 /// TransferDbgValues - Transfer SDDbgValues.
6613 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6614 if (From == To || !From.getNode()->getHasDebugValue())
6616 SDNode *FromNode = From.getNode();
6617 SDNode *ToNode = To.getNode();
6618 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6619 SmallVector<SDDbgValue *, 2> ClonedDVs;
6620 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6622 SDDbgValue *Dbg = *I;
6623 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6625 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6626 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6627 Dbg->getDebugLoc(), Dbg->getOrder());
6628 ClonedDVs.push_back(Clone);
6631 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6632 E = ClonedDVs.end(); I != E; ++I)
6633 AddDbgValue(*I, ToNode, false);
6636 //===----------------------------------------------------------------------===//
6638 //===----------------------------------------------------------------------===//
6640 HandleSDNode::~HandleSDNode() {
6644 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6645 DebugLoc DL, const GlobalValue *GA,
6646 EVT VT, int64_t o, unsigned char TF)
6647 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6651 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6652 SDValue X, unsigned SrcAS,
6654 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6655 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6657 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6658 EVT memvt, MachineMemOperand *mmo)
6659 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6660 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6661 MMO->isNonTemporal(), MMO->isInvariant());
6662 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6663 assert(isNonTemporal() == MMO->isNonTemporal() &&
6664 "Non-temporal encoding error!");
6665 // We check here that the size of the memory operand fits within the size of
6666 // the MMO. This is because the MMO might indicate only a possible address
6667 // range instead of specifying the affected memory addresses precisely.
6668 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6671 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6672 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6673 : SDNode(Opc, Order, dl, VTs, Ops),
6674 MemoryVT(memvt), MMO(mmo) {
6675 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6676 MMO->isNonTemporal(), MMO->isInvariant());
6677 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6678 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6681 /// Profile - Gather unique data for the node.
6683 void SDNode::Profile(FoldingSetNodeID &ID) const {
6684 AddNodeIDNode(ID, this);
6689 std::vector<EVT> VTs;
6692 VTs.reserve(MVT::LAST_VALUETYPE);
6693 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6694 VTs.push_back(MVT((MVT::SimpleValueType)i));
6699 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6700 static ManagedStatic<EVTArray> SimpleVTArray;
6701 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6703 /// getValueTypeList - Return a pointer to the specified value type.
6705 const EVT *SDNode::getValueTypeList(EVT VT) {
6706 if (VT.isExtended()) {
6707 sys::SmartScopedLock<true> Lock(*VTMutex);
6708 return &(*EVTs->insert(VT).first);
6710 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6711 "Value type out of range!");
6712 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6716 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6717 /// indicated value. This method ignores uses of other values defined by this
6719 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6720 assert(Value < getNumValues() && "Bad value!");
6722 // TODO: Only iterate over uses of a given value of the node
6723 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6724 if (UI.getUse().getResNo() == Value) {
6731 // Found exactly the right number of uses?
6736 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6737 /// value. This method ignores uses of other values defined by this operation.
6738 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6739 assert(Value < getNumValues() && "Bad value!");
6741 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6742 if (UI.getUse().getResNo() == Value)
6749 /// isOnlyUserOf - Return true if this node is the only use of N.
6751 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6753 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6764 /// isOperand - Return true if this node is an operand of N.
6766 bool SDValue::isOperandOf(const SDNode *N) const {
6767 for (const SDValue &Op : N->op_values())
6773 bool SDNode::isOperandOf(const SDNode *N) const {
6774 for (const SDValue &Op : N->op_values())
6775 if (this == Op.getNode())
6780 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6781 /// be a chain) reaches the specified operand without crossing any
6782 /// side-effecting instructions on any chain path. In practice, this looks
6783 /// through token factors and non-volatile loads. In order to remain efficient,
6784 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6785 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6786 unsigned Depth) const {
6787 if (*this == Dest) return true;
6789 // Don't search too deeply, we just want to be able to see through
6790 // TokenFactor's etc.
6791 if (Depth == 0) return false;
6793 // If this is a token factor, all inputs to the TF happen in parallel. If any
6794 // of the operands of the TF does not reach dest, then we cannot do the xform.
6795 if (getOpcode() == ISD::TokenFactor) {
6796 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6797 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6802 // Loads don't have side effects, look through them.
6803 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6804 if (!Ld->isVolatile())
6805 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6810 /// hasPredecessor - Return true if N is a predecessor of this node.
6811 /// N is either an operand of this node, or can be reached by recursively
6812 /// traversing up the operands.
6813 /// NOTE: This is an expensive method. Use it carefully.
6814 bool SDNode::hasPredecessor(const SDNode *N) const {
6815 SmallPtrSet<const SDNode *, 32> Visited;
6816 SmallVector<const SDNode *, 16> Worklist;
6817 return hasPredecessorHelper(N, Visited, Worklist);
6821 SDNode::hasPredecessorHelper(const SDNode *N,
6822 SmallPtrSetImpl<const SDNode *> &Visited,
6823 SmallVectorImpl<const SDNode *> &Worklist) const {
6824 if (Visited.empty()) {
6825 Worklist.push_back(this);
6827 // Take a look in the visited set. If we've already encountered this node
6828 // we needn't search further.
6829 if (Visited.count(N))
6833 // Haven't visited N yet. Continue the search.
6834 while (!Worklist.empty()) {
6835 const SDNode *M = Worklist.pop_back_val();
6836 for (const SDValue &OpV : M->op_values()) {
6837 SDNode *Op = OpV.getNode();
6838 if (Visited.insert(Op).second)
6839 Worklist.push_back(Op);
6848 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6849 assert(Num < NumOperands && "Invalid child # of SDNode!");
6850 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6853 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6854 assert(N->getNumValues() == 1 &&
6855 "Can't unroll a vector with multiple results!");
6857 EVT VT = N->getValueType(0);
6858 unsigned NE = VT.getVectorNumElements();
6859 EVT EltVT = VT.getVectorElementType();
6862 SmallVector<SDValue, 8> Scalars;
6863 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6865 // If ResNE is 0, fully unroll the vector op.
6868 else if (NE > ResNE)
6872 for (i= 0; i != NE; ++i) {
6873 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6874 SDValue Operand = N->getOperand(j);
6875 EVT OperandVT = Operand.getValueType();
6876 if (OperandVT.isVector()) {
6877 // A vector operand; extract a single element.
6878 EVT OperandEltVT = OperandVT.getVectorElementType();
6880 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6881 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6883 // A scalar operand; just use it as is.
6884 Operands[j] = Operand;
6888 switch (N->getOpcode()) {
6890 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6893 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6900 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6901 getShiftAmountOperand(Operands[0].getValueType(),
6904 case ISD::SIGN_EXTEND_INREG:
6905 case ISD::FP_ROUND_INREG: {
6906 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6907 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6909 getValueType(ExtVT)));
6914 for (; i < ResNE; ++i)
6915 Scalars.push_back(getUNDEF(EltVT));
6917 return getNode(ISD::BUILD_VECTOR, dl,
6918 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6922 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6923 /// location that is 'Dist' units away from the location that the 'Base' load
6924 /// is loading from.
6925 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6926 unsigned Bytes, int Dist) const {
6927 if (LD->getChain() != Base->getChain())
6929 EVT VT = LD->getValueType(0);
6930 if (VT.getSizeInBits() / 8 != Bytes)
6933 SDValue Loc = LD->getOperand(1);
6934 SDValue BaseLoc = Base->getOperand(1);
6935 if (Loc.getOpcode() == ISD::FrameIndex) {
6936 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6938 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6939 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6940 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6941 int FS = MFI->getObjectSize(FI);
6942 int BFS = MFI->getObjectSize(BFI);
6943 if (FS != BFS || FS != (int)Bytes) return false;
6944 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6948 if (isBaseWithConstantOffset(Loc)) {
6949 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6950 if (Loc.getOperand(0) == BaseLoc) {
6951 // If the base location is a simple address with no offset itself, then
6952 // the second load's first add operand should be the base address.
6953 if (LocOffset == Dist * (int)Bytes)
6955 } else if (isBaseWithConstantOffset(BaseLoc)) {
6956 // The base location itself has an offset, so subtract that value from the
6957 // second load's offset before comparing to distance * size.
6959 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6960 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6961 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6966 const GlobalValue *GV1 = nullptr;
6967 const GlobalValue *GV2 = nullptr;
6968 int64_t Offset1 = 0;
6969 int64_t Offset2 = 0;
6970 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6971 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6972 if (isGA1 && isGA2 && GV1 == GV2)
6973 return Offset1 == (Offset2 + Dist*Bytes);
6978 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6979 /// it cannot be inferred.
6980 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6981 // If this is a GlobalAddress + cst, return the alignment.
6982 const GlobalValue *GV;
6983 int64_t GVOffset = 0;
6984 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6985 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6986 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6987 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6989 unsigned AlignBits = KnownZero.countTrailingOnes();
6990 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6992 return MinAlign(Align, GVOffset);
6995 // If this is a direct reference to a stack slot, use information about the
6996 // stack slot's alignment.
6997 int FrameIdx = 1 << 31;
6998 int64_t FrameOffset = 0;
6999 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7000 FrameIdx = FI->getIndex();
7001 } else if (isBaseWithConstantOffset(Ptr) &&
7002 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7004 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7005 FrameOffset = Ptr.getConstantOperandVal(1);
7008 if (FrameIdx != (1 << 31)) {
7009 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7010 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7018 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7019 /// which is split (or expanded) into two not necessarily identical pieces.
7020 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7021 // Currently all types are split in half.
7023 if (!VT.isVector()) {
7024 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7026 unsigned NumElements = VT.getVectorNumElements();
7027 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7028 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7031 return std::make_pair(LoVT, HiVT);
7034 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7036 std::pair<SDValue, SDValue>
7037 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7039 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7040 N.getValueType().getVectorNumElements() &&
7041 "More vector elements requested than available!");
7043 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7044 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7045 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7046 getConstant(LoVT.getVectorNumElements(), DL,
7047 TLI->getVectorIdxTy(getDataLayout())));
7048 return std::make_pair(Lo, Hi);
7051 void SelectionDAG::ExtractVectorElements(SDValue Op,
7052 SmallVectorImpl<SDValue> &Args,
7053 unsigned Start, unsigned Count) {
7054 EVT VT = Op.getValueType();
7056 Count = VT.getVectorNumElements();
7058 EVT EltVT = VT.getVectorElementType();
7059 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7061 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7062 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7063 Op, getConstant(i, SL, IdxTy)));
7067 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7068 unsigned GlobalAddressSDNode::getAddressSpace() const {
7069 return getGlobal()->getType()->getAddressSpace();
7073 Type *ConstantPoolSDNode::getType() const {
7074 if (isMachineConstantPoolEntry())
7075 return Val.MachineCPVal->getType();
7076 return Val.ConstVal->getType();
7079 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7081 unsigned &SplatBitSize,
7083 unsigned MinSplatBits,
7084 bool isBigEndian) const {
7085 EVT VT = getValueType(0);
7086 assert(VT.isVector() && "Expected a vector type");
7087 unsigned sz = VT.getSizeInBits();
7088 if (MinSplatBits > sz)
7091 SplatValue = APInt(sz, 0);
7092 SplatUndef = APInt(sz, 0);
7094 // Get the bits. Bits with undefined values (when the corresponding element
7095 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7096 // in SplatValue. If any of the values are not constant, give up and return
7098 unsigned int nOps = getNumOperands();
7099 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7100 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7102 for (unsigned j = 0; j < nOps; ++j) {
7103 unsigned i = isBigEndian ? nOps-1-j : j;
7104 SDValue OpVal = getOperand(i);
7105 unsigned BitPos = j * EltBitSize;
7107 if (OpVal.getOpcode() == ISD::UNDEF)
7108 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7109 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7110 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7111 zextOrTrunc(sz) << BitPos;
7112 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7113 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7118 // The build_vector is all constants or undefs. Find the smallest element
7119 // size that splats the vector.
7121 HasAnyUndefs = (SplatUndef != 0);
7124 unsigned HalfSize = sz / 2;
7125 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7126 APInt LowValue = SplatValue.trunc(HalfSize);
7127 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7128 APInt LowUndef = SplatUndef.trunc(HalfSize);
7130 // If the two halves do not match (ignoring undef bits), stop here.
7131 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7132 MinSplatBits > HalfSize)
7135 SplatValue = HighValue | LowValue;
7136 SplatUndef = HighUndef & LowUndef;
7145 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7146 if (UndefElements) {
7147 UndefElements->clear();
7148 UndefElements->resize(getNumOperands());
7151 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7152 SDValue Op = getOperand(i);
7153 if (Op.getOpcode() == ISD::UNDEF) {
7155 (*UndefElements)[i] = true;
7156 } else if (!Splatted) {
7158 } else if (Splatted != Op) {
7164 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7165 "Can only have a splat without a constant for all undefs.");
7166 return getOperand(0);
7173 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7174 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7178 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7179 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7182 bool BuildVectorSDNode::isConstant() const {
7183 for (const SDValue &Op : op_values()) {
7184 unsigned Opc = Op.getOpcode();
7185 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7191 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7192 // Find the first non-undef value in the shuffle mask.
7194 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7197 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7199 // Make sure all remaining elements are either undef or the same as the first
7201 for (int Idx = Mask[i]; i != e; ++i)
7202 if (Mask[i] >= 0 && Mask[i] != Idx)
7208 static void checkForCyclesHelper(const SDNode *N,
7209 SmallPtrSetImpl<const SDNode*> &Visited,
7210 SmallPtrSetImpl<const SDNode*> &Checked,
7211 const llvm::SelectionDAG *DAG) {
7212 // If this node has already been checked, don't check it again.
7213 if (Checked.count(N))
7216 // If a node has already been visited on this depth-first walk, reject it as
7218 if (!Visited.insert(N).second) {
7219 errs() << "Detected cycle in SelectionDAG\n";
7220 dbgs() << "Offending node:\n";
7221 N->dumprFull(DAG); dbgs() << "\n";
7225 for (const SDValue &Op : N->op_values())
7226 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7233 void llvm::checkForCycles(const llvm::SDNode *N,
7234 const llvm::SelectionDAG *DAG,
7242 assert(N && "Checking nonexistent SDNode");
7243 SmallPtrSet<const SDNode*, 32> visited;
7244 SmallPtrSet<const SDNode*, 32> checked;
7245 checkForCyclesHelper(N, visited, checked, DAG);
7250 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7251 checkForCycles(DAG->getRoot().getNode(), DAG, force);