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());
401 /// Add logical or fast math flag values to FoldingSetNodeID value.
402 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
403 const SDNodeFlags *Flags) {
404 if (!isBinOpWithFlags(Opcode))
407 unsigned RawFlags = 0;
409 RawFlags = Flags->getRawFlags();
410 ID.AddInteger(RawFlags);
413 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
414 AddNodeIDFlags(ID, N->getOpcode(), N->getFlags());
417 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
418 SDVTList VTList, ArrayRef<SDValue> OpList) {
419 AddNodeIDOpcode(ID, OpC);
420 AddNodeIDValueTypes(ID, VTList);
421 AddNodeIDOperands(ID, OpList);
424 /// If this is an SDNode with special info, add this info to the NodeID data.
425 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
426 switch (N->getOpcode()) {
427 case ISD::TargetExternalSymbol:
428 case ISD::ExternalSymbol:
430 llvm_unreachable("Should only be used on nodes with operands");
431 default: break; // Normal nodes don't need extra info.
432 case ISD::TargetConstant:
433 case ISD::Constant: {
434 const ConstantSDNode *C = cast<ConstantSDNode>(N);
435 ID.AddPointer(C->getConstantIntValue());
436 ID.AddBoolean(C->isOpaque());
439 case ISD::TargetConstantFP:
440 case ISD::ConstantFP: {
441 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
444 case ISD::TargetGlobalAddress:
445 case ISD::GlobalAddress:
446 case ISD::TargetGlobalTLSAddress:
447 case ISD::GlobalTLSAddress: {
448 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
449 ID.AddPointer(GA->getGlobal());
450 ID.AddInteger(GA->getOffset());
451 ID.AddInteger(GA->getTargetFlags());
452 ID.AddInteger(GA->getAddressSpace());
455 case ISD::BasicBlock:
456 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
459 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
461 case ISD::RegisterMask:
462 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
465 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
467 case ISD::FrameIndex:
468 case ISD::TargetFrameIndex:
469 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
472 case ISD::TargetJumpTable:
473 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
476 case ISD::ConstantPool:
477 case ISD::TargetConstantPool: {
478 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
479 ID.AddInteger(CP->getAlignment());
480 ID.AddInteger(CP->getOffset());
481 if (CP->isMachineConstantPoolEntry())
482 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
484 ID.AddPointer(CP->getConstVal());
485 ID.AddInteger(CP->getTargetFlags());
488 case ISD::TargetIndex: {
489 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
490 ID.AddInteger(TI->getIndex());
491 ID.AddInteger(TI->getOffset());
492 ID.AddInteger(TI->getTargetFlags());
496 const LoadSDNode *LD = cast<LoadSDNode>(N);
497 ID.AddInteger(LD->getMemoryVT().getRawBits());
498 ID.AddInteger(LD->getRawSubclassData());
499 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
503 const StoreSDNode *ST = cast<StoreSDNode>(N);
504 ID.AddInteger(ST->getMemoryVT().getRawBits());
505 ID.AddInteger(ST->getRawSubclassData());
506 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
509 case ISD::ATOMIC_CMP_SWAP:
510 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
511 case ISD::ATOMIC_SWAP:
512 case ISD::ATOMIC_LOAD_ADD:
513 case ISD::ATOMIC_LOAD_SUB:
514 case ISD::ATOMIC_LOAD_AND:
515 case ISD::ATOMIC_LOAD_OR:
516 case ISD::ATOMIC_LOAD_XOR:
517 case ISD::ATOMIC_LOAD_NAND:
518 case ISD::ATOMIC_LOAD_MIN:
519 case ISD::ATOMIC_LOAD_MAX:
520 case ISD::ATOMIC_LOAD_UMIN:
521 case ISD::ATOMIC_LOAD_UMAX:
522 case ISD::ATOMIC_LOAD:
523 case ISD::ATOMIC_STORE: {
524 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
525 ID.AddInteger(AT->getMemoryVT().getRawBits());
526 ID.AddInteger(AT->getRawSubclassData());
527 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
530 case ISD::PREFETCH: {
531 const MemSDNode *PF = cast<MemSDNode>(N);
532 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
535 case ISD::VECTOR_SHUFFLE: {
536 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
537 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
539 ID.AddInteger(SVN->getMaskElt(i));
542 case ISD::TargetBlockAddress:
543 case ISD::BlockAddress: {
544 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
545 ID.AddPointer(BA->getBlockAddress());
546 ID.AddInteger(BA->getOffset());
547 ID.AddInteger(BA->getTargetFlags());
550 } // end switch (N->getOpcode())
552 AddNodeIDFlags(ID, N);
554 // Target specific memory nodes could also have address spaces to check.
555 if (N->isTargetMemoryOpcode())
556 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
559 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
561 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
562 AddNodeIDOpcode(ID, N->getOpcode());
563 // Add the return value info.
564 AddNodeIDValueTypes(ID, N->getVTList());
565 // Add the operand info.
566 AddNodeIDOperands(ID, N->ops());
568 // Handle SDNode leafs with special info.
569 AddNodeIDCustom(ID, N);
572 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
573 /// the CSE map that carries volatility, temporalness, indexing mode, and
574 /// extension/truncation information.
576 static inline unsigned
577 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
578 bool isNonTemporal, bool isInvariant) {
579 assert((ConvType & 3) == ConvType &&
580 "ConvType may not require more than 2 bits!");
581 assert((AM & 7) == AM &&
582 "AM may not require more than 3 bits!");
586 (isNonTemporal << 6) |
590 //===----------------------------------------------------------------------===//
591 // SelectionDAG Class
592 //===----------------------------------------------------------------------===//
594 /// doNotCSE - Return true if CSE should not be performed for this node.
595 static bool doNotCSE(SDNode *N) {
596 if (N->getValueType(0) == MVT::Glue)
597 return true; // Never CSE anything that produces a flag.
599 switch (N->getOpcode()) {
601 case ISD::HANDLENODE:
603 return true; // Never CSE these nodes.
606 // Check that remaining values produced are not flags.
607 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
608 if (N->getValueType(i) == MVT::Glue)
609 return true; // Never CSE anything that produces a flag.
614 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
616 void SelectionDAG::RemoveDeadNodes() {
617 // Create a dummy node (which is not added to allnodes), that adds a reference
618 // to the root node, preventing it from being deleted.
619 HandleSDNode Dummy(getRoot());
621 SmallVector<SDNode*, 128> DeadNodes;
623 // Add all obviously-dead nodes to the DeadNodes worklist.
624 for (SDNode &Node : allnodes())
625 if (Node.use_empty())
626 DeadNodes.push_back(&Node);
628 RemoveDeadNodes(DeadNodes);
630 // If the root changed (e.g. it was a dead load, update the root).
631 setRoot(Dummy.getValue());
634 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
635 /// given list, and any nodes that become unreachable as a result.
636 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
638 // Process the worklist, deleting the nodes and adding their uses to the
640 while (!DeadNodes.empty()) {
641 SDNode *N = DeadNodes.pop_back_val();
643 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
644 DUL->NodeDeleted(N, nullptr);
646 // Take the node out of the appropriate CSE map.
647 RemoveNodeFromCSEMaps(N);
649 // Next, brutally remove the operand list. This is safe to do, as there are
650 // no cycles in the graph.
651 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
653 SDNode *Operand = Use.getNode();
656 // Now that we removed this operand, see if there are no uses of it left.
657 if (Operand->use_empty())
658 DeadNodes.push_back(Operand);
665 void SelectionDAG::RemoveDeadNode(SDNode *N){
666 SmallVector<SDNode*, 16> DeadNodes(1, N);
668 // Create a dummy node that adds a reference to the root node, preventing
669 // it from being deleted. (This matters if the root is an operand of the
671 HandleSDNode Dummy(getRoot());
673 RemoveDeadNodes(DeadNodes);
676 void SelectionDAG::DeleteNode(SDNode *N) {
677 // First take this out of the appropriate CSE map.
678 RemoveNodeFromCSEMaps(N);
680 // Finally, remove uses due to operands of this node, remove from the
681 // AllNodes list, and delete the node.
682 DeleteNodeNotInCSEMaps(N);
685 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
686 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
687 assert(N->use_empty() && "Cannot delete a node that is not dead!");
689 // Drop all of the operands and decrement used node's use counts.
695 void SDDbgInfo::erase(const SDNode *Node) {
696 DbgValMapType::iterator I = DbgValMap.find(Node);
697 if (I == DbgValMap.end())
699 for (auto &Val: I->second)
700 Val->setIsInvalidated();
704 void SelectionDAG::DeallocateNode(SDNode *N) {
705 if (N->OperandsNeedDelete)
706 delete[] N->OperandList;
708 // Set the opcode to DELETED_NODE to help catch bugs when node
709 // memory is reallocated.
710 N->NodeType = ISD::DELETED_NODE;
712 NodeAllocator.Deallocate(AllNodes.remove(N));
714 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
715 // them and forget about that node.
720 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
721 static void VerifySDNode(SDNode *N) {
722 switch (N->getOpcode()) {
725 case ISD::BUILD_PAIR: {
726 EVT VT = N->getValueType(0);
727 assert(N->getNumValues() == 1 && "Too many results!");
728 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
729 "Wrong return type!");
730 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
731 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
732 "Mismatched operand types!");
733 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
734 "Wrong operand type!");
735 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
736 "Wrong return type size");
739 case ISD::BUILD_VECTOR: {
740 assert(N->getNumValues() == 1 && "Too many results!");
741 assert(N->getValueType(0).isVector() && "Wrong return type!");
742 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
743 "Wrong number of operands!");
744 EVT EltVT = N->getValueType(0).getVectorElementType();
745 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
746 assert((I->getValueType() == EltVT ||
747 (EltVT.isInteger() && I->getValueType().isInteger() &&
748 EltVT.bitsLE(I->getValueType()))) &&
749 "Wrong operand type!");
750 assert(I->getValueType() == N->getOperand(0).getValueType() &&
751 "Operands must all have the same type");
759 /// \brief Insert a newly allocated node into the DAG.
761 /// Handles insertion into the all nodes list and CSE map, as well as
762 /// verification and other common operations when a new node is allocated.
763 void SelectionDAG::InsertNode(SDNode *N) {
764 AllNodes.push_back(N);
766 N->PersistentId = NextPersistentId++;
771 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
772 /// correspond to it. This is useful when we're about to delete or repurpose
773 /// the node. We don't want future request for structurally identical nodes
774 /// to return N anymore.
775 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
777 switch (N->getOpcode()) {
778 case ISD::HANDLENODE: return false; // noop.
780 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
781 "Cond code doesn't exist!");
782 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
783 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
785 case ISD::ExternalSymbol:
786 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
788 case ISD::TargetExternalSymbol: {
789 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
790 Erased = TargetExternalSymbols.erase(
791 std::pair<std::string,unsigned char>(ESN->getSymbol(),
792 ESN->getTargetFlags()));
795 case ISD::MCSymbol: {
796 auto *MCSN = cast<MCSymbolSDNode>(N);
797 Erased = MCSymbols.erase(MCSN->getMCSymbol());
800 case ISD::VALUETYPE: {
801 EVT VT = cast<VTSDNode>(N)->getVT();
802 if (VT.isExtended()) {
803 Erased = ExtendedValueTypeNodes.erase(VT);
805 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
806 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
811 // Remove it from the CSE Map.
812 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
813 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
814 Erased = CSEMap.RemoveNode(N);
818 // Verify that the node was actually in one of the CSE maps, unless it has a
819 // flag result (which cannot be CSE'd) or is one of the special cases that are
820 // not subject to CSE.
821 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
822 !N->isMachineOpcode() && !doNotCSE(N)) {
825 llvm_unreachable("Node is not in map!");
831 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
832 /// maps and modified in place. Add it back to the CSE maps, unless an identical
833 /// node already exists, in which case transfer all its users to the existing
834 /// node. This transfer can potentially trigger recursive merging.
837 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
838 // For node types that aren't CSE'd, just act as if no identical node
841 SDNode *Existing = CSEMap.GetOrInsertNode(N);
843 // If there was already an existing matching node, use ReplaceAllUsesWith
844 // to replace the dead one with the existing one. This can cause
845 // recursive merging of other unrelated nodes down the line.
846 ReplaceAllUsesWith(N, Existing);
848 // N is now dead. Inform the listeners and delete it.
849 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
850 DUL->NodeDeleted(N, Existing);
851 DeleteNodeNotInCSEMaps(N);
856 // If the node doesn't already exist, we updated it. Inform listeners.
857 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
861 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
862 /// were replaced with those specified. If this node is never memoized,
863 /// return null, otherwise return a pointer to the slot it would take. If a
864 /// node already exists with these operands, the slot will be non-null.
865 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
870 SDValue Ops[] = { Op };
872 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
873 AddNodeIDCustom(ID, N);
874 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
878 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
879 /// were replaced with those specified. If this node is never memoized,
880 /// return null, otherwise return a pointer to the slot it would take. If a
881 /// node already exists with these operands, the slot will be non-null.
882 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
883 SDValue Op1, SDValue Op2,
888 SDValue Ops[] = { Op1, Op2 };
890 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
891 AddNodeIDCustom(ID, N);
892 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
897 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
898 /// were replaced with those specified. If this node is never memoized,
899 /// return null, otherwise return a pointer to the slot it would take. If a
900 /// node already exists with these operands, the slot will be non-null.
901 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
907 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
908 AddNodeIDCustom(ID, N);
909 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
913 /// getEVTAlignment - Compute the default alignment value for the
916 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
917 Type *Ty = VT == MVT::iPTR ?
918 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
919 VT.getTypeForEVT(*getContext());
921 return getDataLayout().getABITypeAlignment(Ty);
924 // EntryNode could meaningfully have debug info if we can find it...
925 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
926 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
927 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
928 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
929 UpdateListeners(nullptr) {
930 AllNodes.push_back(&EntryNode);
931 DbgInfo = new SDDbgInfo();
934 void SelectionDAG::init(MachineFunction &mf) {
936 TLI = getSubtarget().getTargetLowering();
937 TSI = getSubtarget().getSelectionDAGInfo();
938 Context = &mf.getFunction()->getContext();
941 SelectionDAG::~SelectionDAG() {
942 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
947 void SelectionDAG::allnodes_clear() {
948 assert(&*AllNodes.begin() == &EntryNode);
949 AllNodes.remove(AllNodes.begin());
950 while (!AllNodes.empty())
951 DeallocateNode(AllNodes.begin());
953 NextPersistentId = 0;
957 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
958 SDVTList VTs, SDValue N1,
960 const SDNodeFlags *Flags) {
961 if (isBinOpWithFlags(Opcode)) {
962 // If no flags were passed in, use a default flags object.
964 if (Flags == nullptr)
967 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
968 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
980 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
982 switch (N->getOpcode()) {
985 case ISD::ConstantFP:
986 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
987 "debug location. Use another overload.");
993 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
994 DebugLoc DL, void *&InsertPos) {
995 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
997 switch (N->getOpcode()) {
998 default: break; // Process only regular (non-target) constant nodes.
1000 case ISD::ConstantFP:
1001 // Erase debug location from the node if the node is used at several
1002 // different places to do not propagate one location to all uses as it
1003 // leads to incorrect debug info.
1004 if (N->getDebugLoc() != DL)
1005 N->setDebugLoc(DebugLoc());
1012 void SelectionDAG::clear() {
1014 OperandAllocator.Reset();
1017 ExtendedValueTypeNodes.clear();
1018 ExternalSymbols.clear();
1019 TargetExternalSymbols.clear();
1021 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1022 static_cast<CondCodeSDNode*>(nullptr));
1023 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1024 static_cast<SDNode*>(nullptr));
1026 EntryNode.UseList = nullptr;
1027 AllNodes.push_back(&EntryNode);
1028 Root = getEntryNode();
1032 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1033 return VT.bitsGT(Op.getValueType()) ?
1034 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1035 getNode(ISD::TRUNCATE, DL, VT, Op);
1038 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1039 return VT.bitsGT(Op.getValueType()) ?
1040 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1041 getNode(ISD::TRUNCATE, DL, VT, Op);
1044 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1045 return VT.bitsGT(Op.getValueType()) ?
1046 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1047 getNode(ISD::TRUNCATE, DL, VT, Op);
1050 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1052 if (VT.bitsLE(Op.getValueType()))
1053 return getNode(ISD::TRUNCATE, SL, VT, Op);
1055 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1056 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1059 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1060 assert(!VT.isVector() &&
1061 "getZeroExtendInReg should use the vector element type instead of "
1062 "the vector type!");
1063 if (Op.getValueType() == VT) return Op;
1064 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1065 APInt Imm = APInt::getLowBitsSet(BitWidth,
1066 VT.getSizeInBits());
1067 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1068 getConstant(Imm, DL, Op.getValueType()));
1071 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1072 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1073 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1074 "The sizes of the input and result must match in order to perform the "
1075 "extend in-register.");
1076 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1077 "The destination vector type must have fewer lanes than the input.");
1078 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1081 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1082 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1083 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1084 "The sizes of the input and result must match in order to perform the "
1085 "extend in-register.");
1086 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1087 "The destination vector type must have fewer lanes than the input.");
1088 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1091 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1092 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1093 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1094 "The sizes of the input and result must match in order to perform the "
1095 "extend in-register.");
1096 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1097 "The destination vector type must have fewer lanes than the input.");
1098 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1101 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1103 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1104 EVT EltVT = VT.getScalarType();
1106 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1107 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1110 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1111 EVT EltVT = VT.getScalarType();
1113 switch (TLI->getBooleanContents(VT)) {
1114 case TargetLowering::ZeroOrOneBooleanContent:
1115 case TargetLowering::UndefinedBooleanContent:
1116 TrueValue = getConstant(1, DL, VT);
1118 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1119 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1123 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1126 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1128 EVT EltVT = VT.getScalarType();
1129 assert((EltVT.getSizeInBits() >= 64 ||
1130 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1131 "getConstant with a uint64_t value that doesn't fit in the type!");
1132 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1135 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1138 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1141 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1142 bool isT, bool isO) {
1143 assert(VT.isInteger() && "Cannot create FP integer constant!");
1145 EVT EltVT = VT.getScalarType();
1146 const ConstantInt *Elt = &Val;
1148 // In some cases the vector type is legal but the element type is illegal and
1149 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1150 // inserted value (the type does not need to match the vector element type).
1151 // Any extra bits introduced will be truncated away.
1152 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1153 TargetLowering::TypePromoteInteger) {
1154 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1155 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1156 Elt = ConstantInt::get(*getContext(), NewVal);
1158 // In other cases the element type is illegal and needs to be expanded, for
1159 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1160 // the value into n parts and use a vector type with n-times the elements.
1161 // Then bitcast to the type requested.
1162 // Legalizing constants too early makes the DAGCombiner's job harder so we
1163 // only legalize if the DAG tells us we must produce legal types.
1164 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1165 TLI->getTypeAction(*getContext(), EltVT) ==
1166 TargetLowering::TypeExpandInteger) {
1167 APInt NewVal = Elt->getValue();
1168 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1169 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1170 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1171 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1173 // Check the temporary vector is the correct size. If this fails then
1174 // getTypeToTransformTo() probably returned a type whose size (in bits)
1175 // isn't a power-of-2 factor of the requested type size.
1176 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1178 SmallVector<SDValue, 2> EltParts;
1179 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1180 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1181 .trunc(ViaEltSizeInBits), DL,
1182 ViaEltVT, isT, isO));
1185 // EltParts is currently in little endian order. If we actually want
1186 // big-endian order then reverse it now.
1187 if (getDataLayout().isBigEndian())
1188 std::reverse(EltParts.begin(), EltParts.end());
1190 // The elements must be reversed when the element order is different
1191 // to the endianness of the elements (because the BITCAST is itself a
1192 // vector shuffle in this situation). However, we do not need any code to
1193 // perform this reversal because getConstant() is producing a vector
1195 // This situation occurs in MIPS MSA.
1197 SmallVector<SDValue, 8> Ops;
1198 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1199 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1201 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1202 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1207 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1208 "APInt size does not match type size!");
1209 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1210 FoldingSetNodeID ID;
1211 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1215 SDNode *N = nullptr;
1216 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1218 return SDValue(N, 0);
1221 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1223 CSEMap.InsertNode(N, IP);
1227 SDValue Result(N, 0);
1228 if (VT.isVector()) {
1229 SmallVector<SDValue, 8> Ops;
1230 Ops.assign(VT.getVectorNumElements(), Result);
1231 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1236 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1237 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1240 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1242 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1245 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1247 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1249 EVT EltVT = VT.getScalarType();
1251 // Do the map lookup using the actual bit pattern for the floating point
1252 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1253 // we don't have issues with SNANs.
1254 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1255 FoldingSetNodeID ID;
1256 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1259 SDNode *N = nullptr;
1260 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1262 return SDValue(N, 0);
1265 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1267 CSEMap.InsertNode(N, IP);
1271 SDValue Result(N, 0);
1272 if (VT.isVector()) {
1273 SmallVector<SDValue, 8> Ops;
1274 Ops.assign(VT.getVectorNumElements(), Result);
1275 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1280 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1282 EVT EltVT = VT.getScalarType();
1283 if (EltVT==MVT::f32)
1284 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1285 else if (EltVT==MVT::f64)
1286 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1287 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1290 APFloat apf = APFloat(Val);
1291 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1293 return getConstantFP(apf, DL, VT, isTarget);
1295 llvm_unreachable("Unsupported type in getConstantFP");
1298 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1299 EVT VT, int64_t Offset,
1301 unsigned char TargetFlags) {
1302 assert((TargetFlags == 0 || isTargetGA) &&
1303 "Cannot set target flags on target-independent globals");
1305 // Truncate (with sign-extension) the offset value to the pointer size.
1306 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1308 Offset = SignExtend64(Offset, BitWidth);
1311 if (GV->isThreadLocal())
1312 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1314 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1321 ID.AddInteger(GV->getType()->getAddressSpace());
1323 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1327 DL.getDebugLoc(), GV, VT,
1328 Offset, TargetFlags);
1329 CSEMap.InsertNode(N, IP);
1331 return SDValue(N, 0);
1334 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1335 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1336 FoldingSetNodeID ID;
1337 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1340 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1341 return SDValue(E, 0);
1343 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1344 CSEMap.InsertNode(N, IP);
1346 return SDValue(N, 0);
1349 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1350 unsigned char TargetFlags) {
1351 assert((TargetFlags == 0 || isTarget) &&
1352 "Cannot set target flags on target-independent jump tables");
1353 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1354 FoldingSetNodeID ID;
1355 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1357 ID.AddInteger(TargetFlags);
1359 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1360 return SDValue(E, 0);
1362 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1364 CSEMap.InsertNode(N, IP);
1366 return SDValue(N, 0);
1369 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1370 unsigned Alignment, int Offset,
1372 unsigned char TargetFlags) {
1373 assert((TargetFlags == 0 || isTarget) &&
1374 "Cannot set target flags on target-independent globals");
1376 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1377 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1378 FoldingSetNodeID ID;
1379 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1380 ID.AddInteger(Alignment);
1381 ID.AddInteger(Offset);
1383 ID.AddInteger(TargetFlags);
1385 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1386 return SDValue(E, 0);
1388 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1389 Alignment, TargetFlags);
1390 CSEMap.InsertNode(N, IP);
1392 return SDValue(N, 0);
1396 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1397 unsigned Alignment, int Offset,
1399 unsigned char TargetFlags) {
1400 assert((TargetFlags == 0 || isTarget) &&
1401 "Cannot set target flags on target-independent globals");
1403 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1404 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1407 ID.AddInteger(Alignment);
1408 ID.AddInteger(Offset);
1409 C->addSelectionDAGCSEId(ID);
1410 ID.AddInteger(TargetFlags);
1412 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1413 return SDValue(E, 0);
1415 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1416 Alignment, TargetFlags);
1417 CSEMap.InsertNode(N, IP);
1419 return SDValue(N, 0);
1422 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1423 unsigned char TargetFlags) {
1424 FoldingSetNodeID ID;
1425 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1426 ID.AddInteger(Index);
1427 ID.AddInteger(Offset);
1428 ID.AddInteger(TargetFlags);
1430 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1431 return SDValue(E, 0);
1433 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1435 CSEMap.InsertNode(N, IP);
1437 return SDValue(N, 0);
1440 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1441 FoldingSetNodeID ID;
1442 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1445 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1446 return SDValue(E, 0);
1448 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1449 CSEMap.InsertNode(N, IP);
1451 return SDValue(N, 0);
1454 SDValue SelectionDAG::getValueType(EVT VT) {
1455 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1456 ValueTypeNodes.size())
1457 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1459 SDNode *&N = VT.isExtended() ?
1460 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1462 if (N) return SDValue(N, 0);
1463 N = new (NodeAllocator) VTSDNode(VT);
1465 return SDValue(N, 0);
1468 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1469 SDNode *&N = ExternalSymbols[Sym];
1470 if (N) return SDValue(N, 0);
1471 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1473 return SDValue(N, 0);
1476 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1477 SDNode *&N = MCSymbols[Sym];
1479 return SDValue(N, 0);
1480 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1482 return SDValue(N, 0);
1485 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1486 unsigned char TargetFlags) {
1488 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1490 if (N) return SDValue(N, 0);
1491 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1497 if ((unsigned)Cond >= CondCodeNodes.size())
1498 CondCodeNodes.resize(Cond+1);
1500 if (!CondCodeNodes[Cond]) {
1501 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1502 CondCodeNodes[Cond] = N;
1506 return SDValue(CondCodeNodes[Cond], 0);
1509 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1510 // the shuffle mask M that point at N1 to point at N2, and indices that point
1511 // N2 to point at N1.
1512 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1514 ShuffleVectorSDNode::commuteMask(M);
1517 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1518 SDValue N2, const int *Mask) {
1519 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1520 "Invalid VECTOR_SHUFFLE");
1522 // Canonicalize shuffle undef, undef -> undef
1523 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1524 return getUNDEF(VT);
1526 // Validate that all indices in Mask are within the range of the elements
1527 // input to the shuffle.
1528 unsigned NElts = VT.getVectorNumElements();
1529 SmallVector<int, 8> MaskVec;
1530 for (unsigned i = 0; i != NElts; ++i) {
1531 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1532 MaskVec.push_back(Mask[i]);
1535 // Canonicalize shuffle v, v -> v, undef
1538 for (unsigned i = 0; i != NElts; ++i)
1539 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1542 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1543 if (N1.getOpcode() == ISD::UNDEF)
1544 commuteShuffle(N1, N2, MaskVec);
1546 // If shuffling a splat, try to blend the splat instead. We do this here so
1547 // that even when this arises during lowering we don't have to re-handle it.
1548 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1549 BitVector UndefElements;
1550 SDValue Splat = BV->getSplatValue(&UndefElements);
1554 for (int i = 0; i < (int)NElts; ++i) {
1555 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1558 // If this input comes from undef, mark it as such.
1559 if (UndefElements[MaskVec[i] - Offset]) {
1564 // If we can blend a non-undef lane, use that instead.
1565 if (!UndefElements[i])
1566 MaskVec[i] = i + Offset;
1569 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1570 BlendSplat(N1BV, 0);
1571 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1572 BlendSplat(N2BV, NElts);
1574 // Canonicalize all index into lhs, -> shuffle lhs, undef
1575 // Canonicalize all index into rhs, -> shuffle rhs, undef
1576 bool AllLHS = true, AllRHS = true;
1577 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1578 for (unsigned i = 0; i != NElts; ++i) {
1579 if (MaskVec[i] >= (int)NElts) {
1584 } else if (MaskVec[i] >= 0) {
1588 if (AllLHS && AllRHS)
1589 return getUNDEF(VT);
1590 if (AllLHS && !N2Undef)
1594 commuteShuffle(N1, N2, MaskVec);
1596 // Reset our undef status after accounting for the mask.
1597 N2Undef = N2.getOpcode() == ISD::UNDEF;
1598 // Re-check whether both sides ended up undef.
1599 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1600 return getUNDEF(VT);
1602 // If Identity shuffle return that node.
1603 bool Identity = true, AllSame = true;
1604 for (unsigned i = 0; i != NElts; ++i) {
1605 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1606 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1608 if (Identity && NElts)
1611 // Shuffling a constant splat doesn't change the result.
1615 // Look through any bitcasts. We check that these don't change the number
1616 // (and size) of elements and just changes their types.
1617 while (V.getOpcode() == ISD::BITCAST)
1618 V = V->getOperand(0);
1620 // A splat should always show up as a build vector node.
1621 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1622 BitVector UndefElements;
1623 SDValue Splat = BV->getSplatValue(&UndefElements);
1624 // If this is a splat of an undef, shuffling it is also undef.
1625 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1626 return getUNDEF(VT);
1629 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1631 // We only have a splat which can skip shuffles if there is a splatted
1632 // value and no undef lanes rearranged by the shuffle.
1633 if (Splat && UndefElements.none()) {
1634 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1635 // number of elements match or the value splatted is a zero constant.
1638 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1639 if (C->isNullValue())
1643 // If the shuffle itself creates a splat, build the vector directly.
1644 if (AllSame && SameNumElts) {
1645 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1646 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1648 EVT BuildVT = BV->getValueType(0);
1649 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1651 // We may have jumped through bitcasts, so the type of the
1652 // BUILD_VECTOR may not match the type of the shuffle.
1654 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1660 FoldingSetNodeID ID;
1661 SDValue Ops[2] = { N1, N2 };
1662 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1663 for (unsigned i = 0; i != NElts; ++i)
1664 ID.AddInteger(MaskVec[i]);
1667 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1668 return SDValue(E, 0);
1670 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1671 // SDNode doesn't have access to it. This memory will be "leaked" when
1672 // the node is deallocated, but recovered when the NodeAllocator is released.
1673 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1674 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1676 ShuffleVectorSDNode *N =
1677 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1678 dl.getDebugLoc(), N1, N2,
1680 CSEMap.InsertNode(N, IP);
1682 return SDValue(N, 0);
1685 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1686 MVT VT = SV.getSimpleValueType(0);
1687 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1688 ShuffleVectorSDNode::commuteMask(MaskVec);
1690 SDValue Op0 = SV.getOperand(0);
1691 SDValue Op1 = SV.getOperand(1);
1692 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1695 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1696 SDValue Val, SDValue DTy,
1697 SDValue STy, SDValue Rnd, SDValue Sat,
1698 ISD::CvtCode Code) {
1699 // If the src and dest types are the same and the conversion is between
1700 // integer types of the same sign or two floats, no conversion is necessary.
1702 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1705 FoldingSetNodeID ID;
1706 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1707 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1709 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1710 return SDValue(E, 0);
1712 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1715 CSEMap.InsertNode(N, IP);
1717 return SDValue(N, 0);
1720 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1721 FoldingSetNodeID ID;
1722 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1723 ID.AddInteger(RegNo);
1725 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1726 return SDValue(E, 0);
1728 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1729 CSEMap.InsertNode(N, IP);
1731 return SDValue(N, 0);
1734 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1735 FoldingSetNodeID ID;
1736 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1737 ID.AddPointer(RegMask);
1739 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1740 return SDValue(E, 0);
1742 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1743 CSEMap.InsertNode(N, IP);
1745 return SDValue(N, 0);
1748 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1749 FoldingSetNodeID ID;
1750 SDValue Ops[] = { Root };
1751 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1752 ID.AddPointer(Label);
1754 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1755 return SDValue(E, 0);
1757 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1758 dl.getDebugLoc(), Root, Label);
1759 CSEMap.InsertNode(N, IP);
1761 return SDValue(N, 0);
1765 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1768 unsigned char TargetFlags) {
1769 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1771 FoldingSetNodeID ID;
1772 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1774 ID.AddInteger(Offset);
1775 ID.AddInteger(TargetFlags);
1777 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1778 return SDValue(E, 0);
1780 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1782 CSEMap.InsertNode(N, IP);
1784 return SDValue(N, 0);
1787 SDValue SelectionDAG::getSrcValue(const Value *V) {
1788 assert((!V || V->getType()->isPointerTy()) &&
1789 "SrcValue is not a pointer?");
1791 FoldingSetNodeID ID;
1792 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1796 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1797 return SDValue(E, 0);
1799 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1800 CSEMap.InsertNode(N, IP);
1802 return SDValue(N, 0);
1805 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1806 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1807 FoldingSetNodeID ID;
1808 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1812 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1813 return SDValue(E, 0);
1815 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1816 CSEMap.InsertNode(N, IP);
1818 return SDValue(N, 0);
1821 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1822 if (VT == V.getValueType())
1825 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1828 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1829 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1830 unsigned SrcAS, unsigned DestAS) {
1831 SDValue Ops[] = {Ptr};
1832 FoldingSetNodeID ID;
1833 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1834 ID.AddInteger(SrcAS);
1835 ID.AddInteger(DestAS);
1838 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1839 return SDValue(E, 0);
1841 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1843 VT, Ptr, SrcAS, DestAS);
1844 CSEMap.InsertNode(N, IP);
1846 return SDValue(N, 0);
1849 /// getShiftAmountOperand - Return the specified value casted to
1850 /// the target's desired shift amount type.
1851 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1852 EVT OpTy = Op.getValueType();
1853 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1854 if (OpTy == ShTy || OpTy.isVector()) return Op;
1856 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1859 SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1861 const TargetLowering &TLI = getTargetLoweringInfo();
1862 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1863 EVT VT = Node->getValueType(0);
1864 SDValue Tmp1 = Node->getOperand(0);
1865 SDValue Tmp2 = Node->getOperand(1);
1866 unsigned Align = Node->getConstantOperandVal(3);
1868 SDValue VAListLoad =
1869 getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1, Tmp2,
1870 MachinePointerInfo(V), false, false, false, 0);
1871 SDValue VAList = VAListLoad;
1873 if (Align > TLI.getMinStackArgumentAlignment()) {
1874 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1876 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1877 getConstant(Align - 1, dl, VAList.getValueType()));
1879 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1880 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1883 // Increment the pointer, VAList, to the next vaarg
1884 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1885 getConstant(getDataLayout().getTypeAllocSize(
1886 VT.getTypeForEVT(*getContext())),
1887 dl, VAList.getValueType()));
1888 // Store the incremented VAList to the legalized pointer
1889 Tmp1 = getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2,
1890 MachinePointerInfo(V), false, false, 0);
1891 // Load the actual argument out of the pointer VAList
1892 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo(),
1893 false, false, false, 0);
1896 SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1898 const TargetLowering &TLI = getTargetLoweringInfo();
1899 // This defaults to loading a pointer from the input and storing it to the
1900 // output, returning the chain.
1901 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1902 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1903 SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
1904 Node->getOperand(0), Node->getOperand(2),
1905 MachinePointerInfo(VS), false, false, false, 0);
1906 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1907 MachinePointerInfo(VD), false, false, 0);
1910 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1911 /// specified value type.
1912 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1913 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1914 unsigned ByteSize = VT.getStoreSize();
1915 Type *Ty = VT.getTypeForEVT(*getContext());
1916 unsigned StackAlign =
1917 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1919 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1920 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1923 /// CreateStackTemporary - Create a stack temporary suitable for holding
1924 /// either of the specified value types.
1925 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1926 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1927 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1928 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1929 const DataLayout &DL = getDataLayout();
1931 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1933 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1934 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1935 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1938 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1939 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1940 // These setcc operations always fold.
1944 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1946 case ISD::SETTRUE2: {
1947 TargetLowering::BooleanContent Cnt =
1948 TLI->getBooleanContents(N1->getValueType(0));
1950 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1964 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1968 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1969 const APInt &C2 = N2C->getAPIntValue();
1970 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1971 const APInt &C1 = N1C->getAPIntValue();
1974 default: llvm_unreachable("Unknown integer setcc!");
1975 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1976 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1977 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1978 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1979 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1980 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1981 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1982 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1983 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1984 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1988 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1989 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1990 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1993 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1994 return getUNDEF(VT);
1996 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1997 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1998 return getUNDEF(VT);
2000 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
2001 R==APFloat::cmpLessThan, dl, VT);
2002 case ISD::SETLT: if (R==APFloat::cmpUnordered)
2003 return getUNDEF(VT);
2005 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
2006 case ISD::SETGT: if (R==APFloat::cmpUnordered)
2007 return getUNDEF(VT);
2009 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
2010 case ISD::SETLE: if (R==APFloat::cmpUnordered)
2011 return getUNDEF(VT);
2013 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
2014 R==APFloat::cmpEqual, dl, VT);
2015 case ISD::SETGE: if (R==APFloat::cmpUnordered)
2016 return getUNDEF(VT);
2018 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
2019 R==APFloat::cmpEqual, dl, VT);
2020 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
2021 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
2022 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
2023 R==APFloat::cmpEqual, dl, VT);
2024 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
2025 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
2026 R==APFloat::cmpLessThan, dl, VT);
2027 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
2028 R==APFloat::cmpUnordered, dl, VT);
2029 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
2030 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
2033 // Ensure that the constant occurs on the RHS.
2034 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
2035 MVT CompVT = N1.getValueType().getSimpleVT();
2036 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2039 return getSetCC(dl, VT, N2, N1, SwappedCond);
2043 // Could not fold it.
2047 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2048 /// use this predicate to simplify operations downstream.
2049 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2050 // This predicate is not safe for vector operations.
2051 if (Op.getValueType().isVector())
2054 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2055 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2058 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2059 /// this predicate to simplify operations downstream. Mask is known to be zero
2060 /// for bits that V cannot have.
2061 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2062 unsigned Depth) const {
2063 APInt KnownZero, KnownOne;
2064 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2065 return (KnownZero & Mask) == Mask;
2068 /// Determine which bits of Op are known to be either zero or one and return
2069 /// them in the KnownZero/KnownOne bitsets.
2070 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2071 APInt &KnownOne, unsigned Depth) const {
2072 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2074 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2076 return; // Limit search depth.
2078 APInt KnownZero2, KnownOne2;
2080 switch (Op.getOpcode()) {
2082 // We know all of the bits for a constant!
2083 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2084 KnownZero = ~KnownOne;
2087 // If either the LHS or the RHS are Zero, the result is zero.
2088 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2089 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2091 // Output known-1 bits are only known if set in both the LHS & RHS.
2092 KnownOne &= KnownOne2;
2093 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2094 KnownZero |= KnownZero2;
2097 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2098 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2100 // Output known-0 bits are only known if clear in both the LHS & RHS.
2101 KnownZero &= KnownZero2;
2102 // Output known-1 are known to be set if set in either the LHS | RHS.
2103 KnownOne |= KnownOne2;
2106 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2107 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2109 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2110 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2111 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2112 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2113 KnownZero = KnownZeroOut;
2117 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2118 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2120 // If low bits are zero in either operand, output low known-0 bits.
2121 // Also compute a conserative estimate for high known-0 bits.
2122 // More trickiness is possible, but this is sufficient for the
2123 // interesting case of alignment computation.
2124 KnownOne.clearAllBits();
2125 unsigned TrailZ = KnownZero.countTrailingOnes() +
2126 KnownZero2.countTrailingOnes();
2127 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2128 KnownZero2.countLeadingOnes(),
2129 BitWidth) - BitWidth;
2131 TrailZ = std::min(TrailZ, BitWidth);
2132 LeadZ = std::min(LeadZ, BitWidth);
2133 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2134 APInt::getHighBitsSet(BitWidth, LeadZ);
2138 // For the purposes of computing leading zeros we can conservatively
2139 // treat a udiv as a logical right shift by the power of 2 known to
2140 // be less than the denominator.
2141 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2142 unsigned LeadZ = KnownZero2.countLeadingOnes();
2144 KnownOne2.clearAllBits();
2145 KnownZero2.clearAllBits();
2146 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2147 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2148 if (RHSUnknownLeadingOnes != BitWidth)
2149 LeadZ = std::min(BitWidth,
2150 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2152 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2156 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2157 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2159 // Only known if known in both the LHS and RHS.
2160 KnownOne &= KnownOne2;
2161 KnownZero &= KnownZero2;
2163 case ISD::SELECT_CC:
2164 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2165 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2167 // Only known if known in both the LHS and RHS.
2168 KnownOne &= KnownOne2;
2169 KnownZero &= KnownZero2;
2177 if (Op.getResNo() != 1)
2179 // The boolean result conforms to getBooleanContents.
2180 // If we know the result of a setcc has the top bits zero, use this info.
2181 // We know that we have an integer-based boolean since these operations
2182 // are only available for integer.
2183 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2184 TargetLowering::ZeroOrOneBooleanContent &&
2186 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2189 // If we know the result of a setcc has the top bits zero, use this info.
2190 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2191 TargetLowering::ZeroOrOneBooleanContent &&
2193 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2196 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2197 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2198 unsigned ShAmt = SA->getZExtValue();
2200 // If the shift count is an invalid immediate, don't do anything.
2201 if (ShAmt >= BitWidth)
2204 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2205 KnownZero <<= ShAmt;
2207 // low bits known zero.
2208 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2212 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2213 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2214 unsigned ShAmt = SA->getZExtValue();
2216 // If the shift count is an invalid immediate, don't do anything.
2217 if (ShAmt >= BitWidth)
2220 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2221 KnownZero = KnownZero.lshr(ShAmt);
2222 KnownOne = KnownOne.lshr(ShAmt);
2224 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2225 KnownZero |= HighBits; // High bits known zero.
2229 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2230 unsigned ShAmt = SA->getZExtValue();
2232 // If the shift count is an invalid immediate, don't do anything.
2233 if (ShAmt >= BitWidth)
2236 // If any of the demanded bits are produced by the sign extension, we also
2237 // demand the input sign bit.
2238 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2240 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2241 KnownZero = KnownZero.lshr(ShAmt);
2242 KnownOne = KnownOne.lshr(ShAmt);
2244 // Handle the sign bits.
2245 APInt SignBit = APInt::getSignBit(BitWidth);
2246 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2248 if (KnownZero.intersects(SignBit)) {
2249 KnownZero |= HighBits; // New bits are known zero.
2250 } else if (KnownOne.intersects(SignBit)) {
2251 KnownOne |= HighBits; // New bits are known one.
2255 case ISD::SIGN_EXTEND_INREG: {
2256 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2257 unsigned EBits = EVT.getScalarType().getSizeInBits();
2259 // Sign extension. Compute the demanded bits in the result that are not
2260 // present in the input.
2261 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2263 APInt InSignBit = APInt::getSignBit(EBits);
2264 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2266 // If the sign extended bits are demanded, we know that the sign
2268 InSignBit = InSignBit.zext(BitWidth);
2269 if (NewBits.getBoolValue())
2270 InputDemandedBits |= InSignBit;
2272 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2273 KnownOne &= InputDemandedBits;
2274 KnownZero &= InputDemandedBits;
2276 // If the sign bit of the input is known set or clear, then we know the
2277 // top bits of the result.
2278 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2279 KnownZero |= NewBits;
2280 KnownOne &= ~NewBits;
2281 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2282 KnownOne |= NewBits;
2283 KnownZero &= ~NewBits;
2284 } else { // Input sign bit unknown
2285 KnownZero &= ~NewBits;
2286 KnownOne &= ~NewBits;
2291 case ISD::CTTZ_ZERO_UNDEF:
2293 case ISD::CTLZ_ZERO_UNDEF:
2295 unsigned LowBits = Log2_32(BitWidth)+1;
2296 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2297 KnownOne.clearAllBits();
2301 LoadSDNode *LD = cast<LoadSDNode>(Op);
2302 // If this is a ZEXTLoad and we are looking at the loaded value.
2303 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2304 EVT VT = LD->getMemoryVT();
2305 unsigned MemBits = VT.getScalarType().getSizeInBits();
2306 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2307 } else if (const MDNode *Ranges = LD->getRanges()) {
2308 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2312 case ISD::ZERO_EXTEND: {
2313 EVT InVT = Op.getOperand(0).getValueType();
2314 unsigned InBits = InVT.getScalarType().getSizeInBits();
2315 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2316 KnownZero = KnownZero.trunc(InBits);
2317 KnownOne = KnownOne.trunc(InBits);
2318 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2319 KnownZero = KnownZero.zext(BitWidth);
2320 KnownOne = KnownOne.zext(BitWidth);
2321 KnownZero |= NewBits;
2324 case ISD::SIGN_EXTEND: {
2325 EVT InVT = Op.getOperand(0).getValueType();
2326 unsigned InBits = InVT.getScalarType().getSizeInBits();
2327 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2329 KnownZero = KnownZero.trunc(InBits);
2330 KnownOne = KnownOne.trunc(InBits);
2331 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2333 // Note if the sign bit is known to be zero or one.
2334 bool SignBitKnownZero = KnownZero.isNegative();
2335 bool SignBitKnownOne = KnownOne.isNegative();
2337 KnownZero = KnownZero.zext(BitWidth);
2338 KnownOne = KnownOne.zext(BitWidth);
2340 // If the sign bit is known zero or one, the top bits match.
2341 if (SignBitKnownZero)
2342 KnownZero |= NewBits;
2343 else if (SignBitKnownOne)
2344 KnownOne |= NewBits;
2347 case ISD::ANY_EXTEND: {
2348 EVT InVT = Op.getOperand(0).getValueType();
2349 unsigned InBits = InVT.getScalarType().getSizeInBits();
2350 KnownZero = KnownZero.trunc(InBits);
2351 KnownOne = KnownOne.trunc(InBits);
2352 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2353 KnownZero = KnownZero.zext(BitWidth);
2354 KnownOne = KnownOne.zext(BitWidth);
2357 case ISD::TRUNCATE: {
2358 EVT InVT = Op.getOperand(0).getValueType();
2359 unsigned InBits = InVT.getScalarType().getSizeInBits();
2360 KnownZero = KnownZero.zext(InBits);
2361 KnownOne = KnownOne.zext(InBits);
2362 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2363 KnownZero = KnownZero.trunc(BitWidth);
2364 KnownOne = KnownOne.trunc(BitWidth);
2367 case ISD::AssertZext: {
2368 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2369 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2370 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2371 KnownZero |= (~InMask);
2372 KnownOne &= (~KnownZero);
2376 // All bits are zero except the low bit.
2377 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2381 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2382 // We know that the top bits of C-X are clear if X contains less bits
2383 // than C (i.e. no wrap-around can happen). For example, 20-X is
2384 // positive if we can prove that X is >= 0 and < 16.
2385 if (CLHS->getAPIntValue().isNonNegative()) {
2386 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2387 // NLZ can't be BitWidth with no sign bit
2388 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2389 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2391 // If all of the MaskV bits are known to be zero, then we know the
2392 // output top bits are zero, because we now know that the output is
2394 if ((KnownZero2 & MaskV) == MaskV) {
2395 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2396 // Top bits known zero.
2397 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2405 // Output known-0 bits are known if clear or set in both the low clear bits
2406 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2407 // low 3 bits clear.
2408 // Output known-0 bits are also known if the top bits of each input are
2409 // known to be clear. For example, if one input has the top 10 bits clear
2410 // and the other has the top 8 bits clear, we know the top 7 bits of the
2411 // output must be clear.
2412 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2413 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2414 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2416 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2417 KnownZeroHigh = std::min(KnownZeroHigh,
2418 KnownZero2.countLeadingOnes());
2419 KnownZeroLow = std::min(KnownZeroLow,
2420 KnownZero2.countTrailingOnes());
2422 if (Op.getOpcode() == ISD::ADD) {
2423 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2424 if (KnownZeroHigh > 1)
2425 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2429 // With ADDE, a carry bit may be added in, so we can only use this
2430 // information if we know (at least) that the low two bits are clear. We
2431 // then return to the caller that the low bit is unknown but that other bits
2433 if (KnownZeroLow >= 2) // ADDE
2434 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2438 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2439 const APInt &RA = Rem->getAPIntValue().abs();
2440 if (RA.isPowerOf2()) {
2441 APInt LowBits = RA - 1;
2442 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2444 // The low bits of the first operand are unchanged by the srem.
2445 KnownZero = KnownZero2 & LowBits;
2446 KnownOne = KnownOne2 & LowBits;
2448 // If the first operand is non-negative or has all low bits zero, then
2449 // the upper bits are all zero.
2450 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2451 KnownZero |= ~LowBits;
2453 // If the first operand is negative and not all low bits are zero, then
2454 // the upper bits are all one.
2455 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2456 KnownOne |= ~LowBits;
2457 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2462 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2463 const APInt &RA = Rem->getAPIntValue();
2464 if (RA.isPowerOf2()) {
2465 APInt LowBits = (RA - 1);
2466 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2468 // The upper bits are all zero, the lower ones are unchanged.
2469 KnownZero = KnownZero2 | ~LowBits;
2470 KnownOne = KnownOne2 & LowBits;
2475 // Since the result is less than or equal to either operand, any leading
2476 // zero bits in either operand must also exist in the result.
2477 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2478 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2480 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2481 KnownZero2.countLeadingOnes());
2482 KnownOne.clearAllBits();
2483 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2486 case ISD::EXTRACT_ELEMENT: {
2487 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2488 const unsigned Index =
2489 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2490 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2492 // Remove low part of known bits mask
2493 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2494 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2496 // Remove high part of known bit mask
2497 KnownZero = KnownZero.trunc(BitWidth);
2498 KnownOne = KnownOne.trunc(BitWidth);
2505 APInt Op0Zero, Op0One;
2506 APInt Op1Zero, Op1One;
2507 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2508 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2510 KnownZero = Op0Zero & Op1Zero;
2511 KnownOne = Op0One & Op1One;
2514 case ISD::FrameIndex:
2515 case ISD::TargetFrameIndex:
2516 if (unsigned Align = InferPtrAlignment(Op)) {
2517 // The low bits are known zero if the pointer is aligned.
2518 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2524 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2527 case ISD::INTRINSIC_WO_CHAIN:
2528 case ISD::INTRINSIC_W_CHAIN:
2529 case ISD::INTRINSIC_VOID:
2530 // Allow the target to implement this method for its nodes.
2531 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2535 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2538 /// ComputeNumSignBits - Return the number of times the sign bit of the
2539 /// register is replicated into the other bits. We know that at least 1 bit
2540 /// is always equal to the sign bit (itself), but other cases can give us
2541 /// information. For example, immediately after an "SRA X, 2", we know that
2542 /// the top 3 bits are all equal to each other, so we return 3.
2543 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2544 EVT VT = Op.getValueType();
2545 assert(VT.isInteger() && "Invalid VT!");
2546 unsigned VTBits = VT.getScalarType().getSizeInBits();
2548 unsigned FirstAnswer = 1;
2551 return 1; // Limit search depth.
2553 switch (Op.getOpcode()) {
2555 case ISD::AssertSext:
2556 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2557 return VTBits-Tmp+1;
2558 case ISD::AssertZext:
2559 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2562 case ISD::Constant: {
2563 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2564 return Val.getNumSignBits();
2567 case ISD::SIGN_EXTEND:
2569 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2570 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2572 case ISD::SIGN_EXTEND_INREG:
2573 // Max of the input and what this extends.
2575 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2578 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2579 return std::max(Tmp, Tmp2);
2582 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2583 // SRA X, C -> adds C sign bits.
2584 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2585 Tmp += C->getZExtValue();
2586 if (Tmp > VTBits) Tmp = VTBits;
2590 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2591 // shl destroys sign bits.
2592 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2593 if (C->getZExtValue() >= VTBits || // Bad shift.
2594 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2595 return Tmp - C->getZExtValue();
2600 case ISD::XOR: // NOT is handled here.
2601 // Logical binary ops preserve the number of sign bits at the worst.
2602 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2604 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2605 FirstAnswer = std::min(Tmp, Tmp2);
2606 // We computed what we know about the sign bits as our first
2607 // answer. Now proceed to the generic code that uses
2608 // computeKnownBits, and pick whichever answer is better.
2613 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2614 if (Tmp == 1) return 1; // Early out.
2615 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2616 return std::min(Tmp, Tmp2);
2617 case ISD::SELECT_CC:
2618 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2619 if (Tmp == 1) return 1; // Early out.
2620 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2621 return std::min(Tmp, Tmp2);
2626 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2628 return 1; // Early out.
2629 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2630 return std::min(Tmp, Tmp2);
2637 if (Op.getResNo() != 1)
2639 // The boolean result conforms to getBooleanContents. Fall through.
2640 // If setcc returns 0/-1, all bits are sign bits.
2641 // We know that we have an integer-based boolean since these operations
2642 // are only available for integer.
2643 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2644 TargetLowering::ZeroOrNegativeOneBooleanContent)
2648 // If setcc returns 0/-1, all bits are sign bits.
2649 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2650 TargetLowering::ZeroOrNegativeOneBooleanContent)
2655 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2656 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2658 // Handle rotate right by N like a rotate left by 32-N.
2659 if (Op.getOpcode() == ISD::ROTR)
2660 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2662 // If we aren't rotating out all of the known-in sign bits, return the
2663 // number that are left. This handles rotl(sext(x), 1) for example.
2664 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2665 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2669 // Add can have at most one carry bit. Thus we know that the output
2670 // is, at worst, one more bit than the inputs.
2671 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2672 if (Tmp == 1) return 1; // Early out.
2674 // Special case decrementing a value (ADD X, -1):
2675 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2676 if (CRHS->isAllOnesValue()) {
2677 APInt KnownZero, KnownOne;
2678 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2680 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2682 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2685 // If we are subtracting one from a positive number, there is no carry
2686 // out of the result.
2687 if (KnownZero.isNegative())
2691 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2692 if (Tmp2 == 1) return 1;
2693 return std::min(Tmp, Tmp2)-1;
2696 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2697 if (Tmp2 == 1) return 1;
2700 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2701 if (CLHS->isNullValue()) {
2702 APInt KnownZero, KnownOne;
2703 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2704 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2706 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2709 // If the input is known to be positive (the sign bit is known clear),
2710 // the output of the NEG has the same number of sign bits as the input.
2711 if (KnownZero.isNegative())
2714 // Otherwise, we treat this like a SUB.
2717 // Sub can have at most one carry bit. Thus we know that the output
2718 // is, at worst, one more bit than the inputs.
2719 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2720 if (Tmp == 1) return 1; // Early out.
2721 return std::min(Tmp, Tmp2)-1;
2723 // FIXME: it's tricky to do anything useful for this, but it is an important
2724 // case for targets like X86.
2726 case ISD::EXTRACT_ELEMENT: {
2727 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2728 const int BitWidth = Op.getValueType().getSizeInBits();
2730 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2732 // Get reverse index (starting from 1), Op1 value indexes elements from
2733 // little end. Sign starts at big end.
2734 const int rIndex = Items - 1 -
2735 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2737 // If the sign portion ends in our element the subtraction gives correct
2738 // result. Otherwise it gives either negative or > bitwidth result
2739 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2743 // If we are looking at the loaded value of the SDNode.
2744 if (Op.getResNo() == 0) {
2745 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2746 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2747 unsigned ExtType = LD->getExtensionType();
2750 case ISD::SEXTLOAD: // '17' bits known
2751 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2752 return VTBits-Tmp+1;
2753 case ISD::ZEXTLOAD: // '16' bits known
2754 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2760 // Allow the target to implement this method for its nodes.
2761 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2762 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2763 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2764 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2765 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2766 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2769 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2770 // use this information.
2771 APInt KnownZero, KnownOne;
2772 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2775 if (KnownZero.isNegative()) { // sign bit is 0
2777 } else if (KnownOne.isNegative()) { // sign bit is 1;
2784 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2785 // the number of identical bits in the top of the input value.
2787 Mask <<= Mask.getBitWidth()-VTBits;
2788 // Return # leading zeros. We use 'min' here in case Val was zero before
2789 // shifting. We don't want to return '64' as for an i32 "0".
2790 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2793 /// isBaseWithConstantOffset - Return true if the specified operand is an
2794 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2795 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2796 /// semantics as an ADD. This handles the equivalence:
2797 /// X|Cst == X+Cst iff X&Cst = 0.
2798 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2799 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2800 !isa<ConstantSDNode>(Op.getOperand(1)))
2803 if (Op.getOpcode() == ISD::OR &&
2804 !MaskedValueIsZero(Op.getOperand(0),
2805 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2812 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2813 // If we're told that NaNs won't happen, assume they won't.
2814 if (getTarget().Options.NoNaNsFPMath)
2817 // If the value is a constant, we can obviously see if it is a NaN or not.
2818 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2819 return !C->getValueAPF().isNaN();
2821 // TODO: Recognize more cases here.
2826 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2827 // If the value is a constant, we can obviously see if it is a zero or not.
2828 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2829 return !C->isZero();
2831 // TODO: Recognize more cases here.
2832 switch (Op.getOpcode()) {
2835 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2836 return !C->isNullValue();
2843 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2844 // Check the obvious case.
2845 if (A == B) return true;
2847 // For for negative and positive zero.
2848 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2849 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2850 if (CA->isZero() && CB->isZero()) return true;
2852 // Otherwise they may not be equal.
2856 /// getNode - Gets or creates the specified node.
2858 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2859 FoldingSetNodeID ID;
2860 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2862 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2863 return SDValue(E, 0);
2865 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2866 DL.getDebugLoc(), getVTList(VT));
2867 CSEMap.InsertNode(N, IP);
2870 return SDValue(N, 0);
2873 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2874 EVT VT, SDValue Operand) {
2875 // Constant fold unary operations with an integer constant operand. Even
2876 // opaque constant will be folded, because the folding of unary operations
2877 // doesn't create new constants with different values. Nevertheless, the
2878 // opaque flag is preserved during folding to prevent future folding with
2880 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2881 const APInt &Val = C->getAPIntValue();
2884 case ISD::SIGN_EXTEND:
2885 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2886 C->isTargetOpcode(), C->isOpaque());
2887 case ISD::ANY_EXTEND:
2888 case ISD::ZERO_EXTEND:
2890 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2891 C->isTargetOpcode(), C->isOpaque());
2892 case ISD::UINT_TO_FP:
2893 case ISD::SINT_TO_FP: {
2894 APFloat apf(EVTToAPFloatSemantics(VT),
2895 APInt::getNullValue(VT.getSizeInBits()));
2896 (void)apf.convertFromAPInt(Val,
2897 Opcode==ISD::SINT_TO_FP,
2898 APFloat::rmNearestTiesToEven);
2899 return getConstantFP(apf, DL, VT);
2902 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2903 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2904 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2905 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2906 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2907 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2910 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2913 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2916 case ISD::CTLZ_ZERO_UNDEF:
2917 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2920 case ISD::CTTZ_ZERO_UNDEF:
2921 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2926 // Constant fold unary operations with a floating point constant operand.
2927 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2928 APFloat V = C->getValueAPF(); // make copy
2932 return getConstantFP(V, DL, VT);
2935 return getConstantFP(V, DL, VT);
2937 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2938 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2939 return getConstantFP(V, DL, VT);
2943 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2944 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2945 return getConstantFP(V, DL, VT);
2949 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2950 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2951 return getConstantFP(V, DL, VT);
2954 case ISD::FP_EXTEND: {
2956 // This can return overflow, underflow, or inexact; we don't care.
2957 // FIXME need to be more flexible about rounding mode.
2958 (void)V.convert(EVTToAPFloatSemantics(VT),
2959 APFloat::rmNearestTiesToEven, &ignored);
2960 return getConstantFP(V, DL, VT);
2962 case ISD::FP_TO_SINT:
2963 case ISD::FP_TO_UINT: {
2966 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2967 // FIXME need to be more flexible about rounding mode.
2968 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2969 Opcode==ISD::FP_TO_SINT,
2970 APFloat::rmTowardZero, &ignored);
2971 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2973 APInt api(VT.getSizeInBits(), x);
2974 return getConstant(api, DL, VT);
2977 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2978 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2979 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2980 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2981 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2982 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2987 // Constant fold unary operations with a vector integer or float operand.
2988 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2989 if (BV->isConstant()) {
2992 // FIXME: Entirely reasonable to perform folding of other unary
2993 // operations here as the need arises.
3000 case ISD::FP_EXTEND:
3001 case ISD::FP_TO_SINT:
3002 case ISD::FP_TO_UINT:
3004 case ISD::UINT_TO_FP:
3005 case ISD::SINT_TO_FP:
3008 case ISD::CTLZ_ZERO_UNDEF:
3010 case ISD::CTTZ_ZERO_UNDEF:
3012 EVT SVT = VT.getScalarType();
3013 EVT InVT = BV->getValueType(0);
3014 EVT InSVT = InVT.getScalarType();
3016 // Find legal integer scalar type for constant promotion and
3017 // ensure that its scalar size is at least as large as source.
3019 if (SVT.isInteger()) {
3020 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3021 if (LegalSVT.bitsLT(SVT)) break;
3024 // Let the above scalar folding handle the folding of each element.
3025 SmallVector<SDValue, 8> Ops;
3026 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3027 SDValue OpN = BV->getOperand(i);
3028 EVT OpVT = OpN.getValueType();
3030 // Build vector (integer) scalar operands may need implicit
3031 // truncation - do this before constant folding.
3032 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
3033 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
3035 OpN = getNode(Opcode, DL, SVT, OpN);
3037 // Legalize the (integer) scalar constant if necessary.
3038 if (LegalSVT != SVT)
3039 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
3041 if (OpN.getOpcode() != ISD::UNDEF &&
3042 OpN.getOpcode() != ISD::Constant &&
3043 OpN.getOpcode() != ISD::ConstantFP)
3047 if (Ops.size() == VT.getVectorNumElements())
3048 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3055 unsigned OpOpcode = Operand.getNode()->getOpcode();
3057 case ISD::TokenFactor:
3058 case ISD::MERGE_VALUES:
3059 case ISD::CONCAT_VECTORS:
3060 return Operand; // Factor, merge or concat of one node? No need.
3061 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3062 case ISD::FP_EXTEND:
3063 assert(VT.isFloatingPoint() &&
3064 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3065 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3066 assert((!VT.isVector() ||
3067 VT.getVectorNumElements() ==
3068 Operand.getValueType().getVectorNumElements()) &&
3069 "Vector element count mismatch!");
3070 assert(Operand.getValueType().bitsLT(VT) &&
3071 "Invalid fpext node, dst < src!");
3072 if (Operand.getOpcode() == ISD::UNDEF)
3073 return getUNDEF(VT);
3075 case ISD::SIGN_EXTEND:
3076 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3077 "Invalid SIGN_EXTEND!");
3078 if (Operand.getValueType() == VT) return Operand; // noop extension
3079 assert((!VT.isVector() ||
3080 VT.getVectorNumElements() ==
3081 Operand.getValueType().getVectorNumElements()) &&
3082 "Vector element count mismatch!");
3083 assert(Operand.getValueType().bitsLT(VT) &&
3084 "Invalid sext node, dst < src!");
3085 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3086 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3087 else if (OpOpcode == ISD::UNDEF)
3088 // sext(undef) = 0, because the top bits will all be the same.
3089 return getConstant(0, DL, VT);
3091 case ISD::ZERO_EXTEND:
3092 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3093 "Invalid ZERO_EXTEND!");
3094 if (Operand.getValueType() == VT) return Operand; // noop extension
3095 assert((!VT.isVector() ||
3096 VT.getVectorNumElements() ==
3097 Operand.getValueType().getVectorNumElements()) &&
3098 "Vector element count mismatch!");
3099 assert(Operand.getValueType().bitsLT(VT) &&
3100 "Invalid zext node, dst < src!");
3101 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3102 return getNode(ISD::ZERO_EXTEND, DL, VT,
3103 Operand.getNode()->getOperand(0));
3104 else if (OpOpcode == ISD::UNDEF)
3105 // zext(undef) = 0, because the top bits will be zero.
3106 return getConstant(0, DL, VT);
3108 case ISD::ANY_EXTEND:
3109 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3110 "Invalid ANY_EXTEND!");
3111 if (Operand.getValueType() == VT) return Operand; // noop extension
3112 assert((!VT.isVector() ||
3113 VT.getVectorNumElements() ==
3114 Operand.getValueType().getVectorNumElements()) &&
3115 "Vector element count mismatch!");
3116 assert(Operand.getValueType().bitsLT(VT) &&
3117 "Invalid anyext node, dst < src!");
3119 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3120 OpOpcode == ISD::ANY_EXTEND)
3121 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3122 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3123 else if (OpOpcode == ISD::UNDEF)
3124 return getUNDEF(VT);
3126 // (ext (trunx x)) -> x
3127 if (OpOpcode == ISD::TRUNCATE) {
3128 SDValue OpOp = Operand.getNode()->getOperand(0);
3129 if (OpOp.getValueType() == VT)
3134 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3135 "Invalid TRUNCATE!");
3136 if (Operand.getValueType() == VT) return Operand; // noop truncate
3137 assert((!VT.isVector() ||
3138 VT.getVectorNumElements() ==
3139 Operand.getValueType().getVectorNumElements()) &&
3140 "Vector element count mismatch!");
3141 assert(Operand.getValueType().bitsGT(VT) &&
3142 "Invalid truncate node, src < dst!");
3143 if (OpOpcode == ISD::TRUNCATE)
3144 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3145 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3146 OpOpcode == ISD::ANY_EXTEND) {
3147 // If the source is smaller than the dest, we still need an extend.
3148 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3149 .bitsLT(VT.getScalarType()))
3150 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3151 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3152 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3153 return Operand.getNode()->getOperand(0);
3155 if (OpOpcode == ISD::UNDEF)
3156 return getUNDEF(VT);
3159 assert(VT.isInteger() && VT == Operand.getValueType() &&
3161 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3162 "BSWAP types must be a multiple of 16 bits!");
3163 if (OpOpcode == ISD::UNDEF)
3164 return getUNDEF(VT);
3167 // Basic sanity checking.
3168 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3169 && "Cannot BITCAST between types of different sizes!");
3170 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3171 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3172 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3173 if (OpOpcode == ISD::UNDEF)
3174 return getUNDEF(VT);
3176 case ISD::SCALAR_TO_VECTOR:
3177 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3178 (VT.getVectorElementType() == Operand.getValueType() ||
3179 (VT.getVectorElementType().isInteger() &&
3180 Operand.getValueType().isInteger() &&
3181 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3182 "Illegal SCALAR_TO_VECTOR node!");
3183 if (OpOpcode == ISD::UNDEF)
3184 return getUNDEF(VT);
3185 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3186 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3187 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3188 Operand.getConstantOperandVal(1) == 0 &&
3189 Operand.getOperand(0).getValueType() == VT)
3190 return Operand.getOperand(0);
3193 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3194 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3195 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3196 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3197 Operand.getNode()->getOperand(0),
3198 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3199 if (OpOpcode == ISD::FNEG) // --X -> X
3200 return Operand.getNode()->getOperand(0);
3203 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3204 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3209 SDVTList VTs = getVTList(VT);
3210 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3211 FoldingSetNodeID ID;
3212 SDValue Ops[1] = { Operand };
3213 AddNodeIDNode(ID, Opcode, VTs, Ops);
3215 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3216 return SDValue(E, 0);
3218 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3219 DL.getDebugLoc(), VTs, Operand);
3220 CSEMap.InsertNode(N, IP);
3222 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3223 DL.getDebugLoc(), VTs, Operand);
3227 return SDValue(N, 0);
3230 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3233 case ISD::ADD: return std::make_pair(C1 + C2, true);
3234 case ISD::SUB: return std::make_pair(C1 - C2, true);
3235 case ISD::MUL: return std::make_pair(C1 * C2, true);
3236 case ISD::AND: return std::make_pair(C1 & C2, true);
3237 case ISD::OR: return std::make_pair(C1 | C2, true);
3238 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3239 case ISD::SHL: return std::make_pair(C1 << C2, true);
3240 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3241 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3242 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3243 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3244 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3245 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3246 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3247 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3249 if (!C2.getBoolValue())
3251 return std::make_pair(C1.udiv(C2), true);
3253 if (!C2.getBoolValue())
3255 return std::make_pair(C1.urem(C2), true);
3257 if (!C2.getBoolValue())
3259 return std::make_pair(C1.sdiv(C2), true);
3261 if (!C2.getBoolValue())
3263 return std::make_pair(C1.srem(C2), true);
3265 return std::make_pair(APInt(1, 0), false);
3268 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3269 const ConstantSDNode *Cst1,
3270 const ConstantSDNode *Cst2) {
3271 if (Cst1->isOpaque() || Cst2->isOpaque())
3274 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3275 Cst2->getAPIntValue());
3278 return getConstant(Folded.first, DL, VT);
3281 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3282 SDNode *Cst1, SDNode *Cst2) {
3283 // If the opcode is a target-specific ISD node, there's nothing we can
3284 // do here and the operand rules may not line up with the below, so
3286 if (Opcode >= ISD::BUILTIN_OP_END)
3289 // Handle the case of two scalars.
3290 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3291 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3292 if (SDValue Folded =
3293 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3296 SmallVector<SDValue, 4> Outputs;
3297 // We may have a vector type but a scalar result. Create a splat.
3298 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3299 // Build a big vector out of the scalar elements we generated.
3300 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3307 // For vectors extract each constant element into Inputs so we can constant
3308 // fold them individually.
3309 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3310 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3314 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3316 EVT SVT = VT.getScalarType();
3317 SmallVector<SDValue, 4> Outputs;
3318 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3319 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3320 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3321 if (!V1 || !V2) // Not a constant, bail.
3324 if (V1->isOpaque() || V2->isOpaque())
3327 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3328 // FIXME: This is valid and could be handled by truncating the APInts.
3329 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3332 // Fold one vector element.
3333 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3334 V2->getAPIntValue());
3337 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3340 assert(VT.getVectorNumElements() == Outputs.size() &&
3341 "Vector size mismatch!");
3343 // We may have a vector type but a scalar result. Create a splat.
3344 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3346 // Build a big vector out of the scalar elements we generated.
3347 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3350 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3351 SDValue N2, const SDNodeFlags *Flags) {
3352 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3353 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3355 // Canonicalize constant to RHS if commutative.
3356 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3357 std::swap(N1C, N2C);
3363 case ISD::TokenFactor:
3364 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3365 N2.getValueType() == MVT::Other && "Invalid token factor!");
3366 // Fold trivial token factors.
3367 if (N1.getOpcode() == ISD::EntryToken) return N2;
3368 if (N2.getOpcode() == ISD::EntryToken) return N1;
3369 if (N1 == N2) return N1;
3371 case ISD::CONCAT_VECTORS:
3372 // Concat of UNDEFs is UNDEF.
3373 if (N1.getOpcode() == ISD::UNDEF &&
3374 N2.getOpcode() == ISD::UNDEF)
3375 return getUNDEF(VT);
3377 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3378 // one big BUILD_VECTOR.
3379 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3380 N2.getOpcode() == ISD::BUILD_VECTOR) {
3381 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3382 N1.getNode()->op_end());
3383 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3385 // BUILD_VECTOR requires all inputs to be of the same type, find the
3386 // maximum type and extend them all.
3387 EVT SVT = VT.getScalarType();
3388 for (SDValue Op : Elts)
3389 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3390 if (SVT.bitsGT(VT.getScalarType()))
3391 for (SDValue &Op : Elts)
3392 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3393 ? getZExtOrTrunc(Op, DL, SVT)
3394 : getSExtOrTrunc(Op, DL, SVT);
3396 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3400 assert(VT.isInteger() && "This operator does not apply to FP types!");
3401 assert(N1.getValueType() == N2.getValueType() &&
3402 N1.getValueType() == VT && "Binary operator types must match!");
3403 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3404 // worth handling here.
3405 if (N2C && N2C->isNullValue())
3407 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3414 assert(VT.isInteger() && "This operator does not apply to FP types!");
3415 assert(N1.getValueType() == N2.getValueType() &&
3416 N1.getValueType() == VT && "Binary operator types must match!");
3417 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3418 // it's worth handling here.
3419 if (N2C && N2C->isNullValue())
3433 assert(VT.isInteger() && "This operator does not apply to FP types!");
3434 assert(N1.getValueType() == N2.getValueType() &&
3435 N1.getValueType() == VT && "Binary operator types must match!");
3442 if (getTarget().Options.UnsafeFPMath) {
3443 if (Opcode == ISD::FADD) {
3445 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3446 if (CFP->getValueAPF().isZero())
3449 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3450 if (CFP->getValueAPF().isZero())
3452 } else if (Opcode == ISD::FSUB) {
3454 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3455 if (CFP->getValueAPF().isZero())
3457 } else if (Opcode == ISD::FMUL) {
3458 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3461 // If the first operand isn't the constant, try the second
3463 CFP = dyn_cast<ConstantFPSDNode>(N2);
3470 return SDValue(CFP,0);
3472 if (CFP->isExactlyValue(1.0))
3477 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3478 assert(N1.getValueType() == N2.getValueType() &&
3479 N1.getValueType() == VT && "Binary operator types must match!");
3481 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3482 assert(N1.getValueType() == VT &&
3483 N1.getValueType().isFloatingPoint() &&
3484 N2.getValueType().isFloatingPoint() &&
3485 "Invalid FCOPYSIGN!");
3492 assert(VT == N1.getValueType() &&
3493 "Shift operators return type must be the same as their first arg");
3494 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3495 "Shifts only work on integers");
3496 assert((!VT.isVector() || VT == N2.getValueType()) &&
3497 "Vector shift amounts must be in the same as their first arg");
3498 // Verify that the shift amount VT is bit enough to hold valid shift
3499 // amounts. This catches things like trying to shift an i1024 value by an
3500 // i8, which is easy to fall into in generic code that uses
3501 // TLI.getShiftAmount().
3502 assert(N2.getValueType().getSizeInBits() >=
3503 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3504 "Invalid use of small shift amount with oversized value!");
3506 // Always fold shifts of i1 values so the code generator doesn't need to
3507 // handle them. Since we know the size of the shift has to be less than the
3508 // size of the value, the shift/rotate count is guaranteed to be zero.
3511 if (N2C && N2C->isNullValue())
3514 case ISD::FP_ROUND_INREG: {
3515 EVT EVT = cast<VTSDNode>(N2)->getVT();
3516 assert(VT == N1.getValueType() && "Not an inreg round!");
3517 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3518 "Cannot FP_ROUND_INREG integer types");
3519 assert(EVT.isVector() == VT.isVector() &&
3520 "FP_ROUND_INREG type should be vector iff the operand "
3522 assert((!EVT.isVector() ||
3523 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3524 "Vector element counts must match in FP_ROUND_INREG");
3525 assert(EVT.bitsLE(VT) && "Not rounding down!");
3527 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3531 assert(VT.isFloatingPoint() &&
3532 N1.getValueType().isFloatingPoint() &&
3533 VT.bitsLE(N1.getValueType()) &&
3534 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3535 if (N1.getValueType() == VT) return N1; // noop conversion.
3537 case ISD::AssertSext:
3538 case ISD::AssertZext: {
3539 EVT EVT = cast<VTSDNode>(N2)->getVT();
3540 assert(VT == N1.getValueType() && "Not an inreg extend!");
3541 assert(VT.isInteger() && EVT.isInteger() &&
3542 "Cannot *_EXTEND_INREG FP types");
3543 assert(!EVT.isVector() &&
3544 "AssertSExt/AssertZExt type should be the vector element type "
3545 "rather than the vector type!");
3546 assert(EVT.bitsLE(VT) && "Not extending!");
3547 if (VT == EVT) return N1; // noop assertion.
3550 case ISD::SIGN_EXTEND_INREG: {
3551 EVT EVT = cast<VTSDNode>(N2)->getVT();
3552 assert(VT == N1.getValueType() && "Not an inreg extend!");
3553 assert(VT.isInteger() && EVT.isInteger() &&
3554 "Cannot *_EXTEND_INREG FP types");
3555 assert(EVT.isVector() == VT.isVector() &&
3556 "SIGN_EXTEND_INREG type should be vector iff the operand "
3558 assert((!EVT.isVector() ||
3559 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3560 "Vector element counts must match in SIGN_EXTEND_INREG");
3561 assert(EVT.bitsLE(VT) && "Not extending!");
3562 if (EVT == VT) return N1; // Not actually extending
3564 auto SignExtendInReg = [&](APInt Val) {
3565 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3566 Val <<= Val.getBitWidth() - FromBits;
3567 Val = Val.ashr(Val.getBitWidth() - FromBits);
3568 return getConstant(Val, DL, VT.getScalarType());
3572 APInt Val = N1C->getAPIntValue();
3573 return SignExtendInReg(Val);
3575 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3576 SmallVector<SDValue, 8> Ops;
3577 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3578 SDValue Op = N1.getOperand(i);
3579 if (Op.getValueType() != VT.getScalarType()) break;
3580 if (Op.getOpcode() == ISD::UNDEF) {
3584 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3585 APInt Val = C->getAPIntValue();
3586 Ops.push_back(SignExtendInReg(Val));
3591 if (Ops.size() == VT.getVectorNumElements())
3592 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3596 case ISD::EXTRACT_VECTOR_ELT:
3597 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3598 if (N1.getOpcode() == ISD::UNDEF)
3599 return getUNDEF(VT);
3601 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3602 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3603 return getUNDEF(VT);
3605 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3606 // expanding copies of large vectors from registers.
3608 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3609 N1.getNumOperands() > 0) {
3611 N1.getOperand(0).getValueType().getVectorNumElements();
3612 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3613 N1.getOperand(N2C->getZExtValue() / Factor),
3614 getConstant(N2C->getZExtValue() % Factor, DL,
3615 N2.getValueType()));
3618 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3619 // expanding large vector constants.
3620 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3621 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3623 if (VT != Elt.getValueType())
3624 // If the vector element type is not legal, the BUILD_VECTOR operands
3625 // are promoted and implicitly truncated, and the result implicitly
3626 // extended. Make that explicit here.
3627 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3632 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3633 // operations are lowered to scalars.
3634 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3635 // If the indices are the same, return the inserted element else
3636 // if the indices are known different, extract the element from
3637 // the original vector.
3638 SDValue N1Op2 = N1.getOperand(2);
3639 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3641 if (N1Op2C && N2C) {
3642 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3643 if (VT == N1.getOperand(1).getValueType())
3644 return N1.getOperand(1);
3646 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3649 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3653 case ISD::EXTRACT_ELEMENT:
3654 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3655 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3656 (N1.getValueType().isInteger() == VT.isInteger()) &&
3657 N1.getValueType() != VT &&
3658 "Wrong types for EXTRACT_ELEMENT!");
3660 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3661 // 64-bit integers into 32-bit parts. Instead of building the extract of
3662 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3663 if (N1.getOpcode() == ISD::BUILD_PAIR)
3664 return N1.getOperand(N2C->getZExtValue());
3666 // EXTRACT_ELEMENT of a constant int is also very common.
3667 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3668 unsigned ElementSize = VT.getSizeInBits();
3669 unsigned Shift = ElementSize * N2C->getZExtValue();
3670 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3671 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3674 case ISD::EXTRACT_SUBVECTOR: {
3676 if (VT.isSimple() && N1.getValueType().isSimple()) {
3677 assert(VT.isVector() && N1.getValueType().isVector() &&
3678 "Extract subvector VTs must be a vectors!");
3679 assert(VT.getVectorElementType() ==
3680 N1.getValueType().getVectorElementType() &&
3681 "Extract subvector VTs must have the same element type!");
3682 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3683 "Extract subvector must be from larger vector to smaller vector!");
3685 if (isa<ConstantSDNode>(Index)) {
3686 assert((VT.getVectorNumElements() +
3687 cast<ConstantSDNode>(Index)->getZExtValue()
3688 <= N1.getValueType().getVectorNumElements())
3689 && "Extract subvector overflow!");
3692 // Trivial extraction.
3693 if (VT.getSimpleVT() == N1.getSimpleValueType())
3700 // Perform trivial constant folding.
3702 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3705 // Constant fold FP operations.
3706 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3707 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3708 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3710 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3711 // Canonicalize constant to RHS if commutative.
3712 std::swap(N1CFP, N2CFP);
3715 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3716 APFloat::opStatus s;
3719 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3720 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3721 return getConstantFP(V1, DL, VT);
3724 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3725 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3726 return getConstantFP(V1, DL, VT);
3729 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3730 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3731 return getConstantFP(V1, DL, VT);
3734 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3735 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3736 s!=APFloat::opDivByZero)) {
3737 return getConstantFP(V1, DL, VT);
3741 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3742 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3743 s!=APFloat::opDivByZero)) {
3744 return getConstantFP(V1, DL, VT);
3747 case ISD::FCOPYSIGN:
3749 return getConstantFP(V1, DL, VT);
3754 if (Opcode == ISD::FP_ROUND) {
3755 APFloat V = N1CFP->getValueAPF(); // make copy
3757 // This can return overflow, underflow, or inexact; we don't care.
3758 // FIXME need to be more flexible about rounding mode.
3759 (void)V.convert(EVTToAPFloatSemantics(VT),
3760 APFloat::rmNearestTiesToEven, &ignored);
3761 return getConstantFP(V, DL, VT);
3765 // Canonicalize an UNDEF to the RHS, even over a constant.
3766 if (N1.getOpcode() == ISD::UNDEF) {
3767 if (isCommutativeBinOp(Opcode)) {
3771 case ISD::FP_ROUND_INREG:
3772 case ISD::SIGN_EXTEND_INREG:
3778 return N1; // fold op(undef, arg2) -> undef
3786 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3787 // For vectors, we can't easily build an all zero vector, just return
3794 // Fold a bunch of operators when the RHS is undef.
3795 if (N2.getOpcode() == ISD::UNDEF) {
3798 if (N1.getOpcode() == ISD::UNDEF)
3799 // Handle undef ^ undef -> 0 special case. This is a common
3801 return getConstant(0, DL, VT);
3811 return N2; // fold op(arg1, undef) -> undef
3817 if (getTarget().Options.UnsafeFPMath)
3825 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3826 // For vectors, we can't easily build an all zero vector, just return
3831 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3832 // For vectors, we can't easily build an all one vector, just return
3840 // Memoize this node if possible.
3842 SDVTList VTs = getVTList(VT);
3843 if (VT != MVT::Glue) {
3844 SDValue Ops[] = {N1, N2};
3845 FoldingSetNodeID ID;
3846 AddNodeIDNode(ID, Opcode, VTs, Ops);
3847 AddNodeIDFlags(ID, Opcode, Flags);
3849 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3850 return SDValue(E, 0);
3852 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3854 CSEMap.InsertNode(N, IP);
3856 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3860 return SDValue(N, 0);
3863 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3864 SDValue N1, SDValue N2, SDValue N3) {
3865 // Perform various simplifications.
3866 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3869 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3870 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3871 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3872 if (N1CFP && N2CFP && N3CFP) {
3873 APFloat V1 = N1CFP->getValueAPF();
3874 const APFloat &V2 = N2CFP->getValueAPF();
3875 const APFloat &V3 = N3CFP->getValueAPF();
3876 APFloat::opStatus s =
3877 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3878 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3879 return getConstantFP(V1, DL, VT);
3883 case ISD::CONCAT_VECTORS:
3884 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3885 // one big BUILD_VECTOR.
3886 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3887 N2.getOpcode() == ISD::BUILD_VECTOR &&
3888 N3.getOpcode() == ISD::BUILD_VECTOR) {
3889 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3890 N1.getNode()->op_end());
3891 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3892 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3893 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3897 // Use FoldSetCC to simplify SETCC's.
3898 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3899 if (Simp.getNode()) return Simp;
3904 if (N1C->getZExtValue())
3905 return N2; // select true, X, Y -> X
3906 return N3; // select false, X, Y -> Y
3909 if (N2 == N3) return N2; // select C, X, X -> X
3911 case ISD::VECTOR_SHUFFLE:
3912 llvm_unreachable("should use getVectorShuffle constructor!");
3913 case ISD::INSERT_SUBVECTOR: {
3915 if (VT.isSimple() && N1.getValueType().isSimple()
3916 && N2.getValueType().isSimple()) {
3917 assert(VT.isVector() && N1.getValueType().isVector() &&
3918 N2.getValueType().isVector() &&
3919 "Insert subvector VTs must be a vectors");
3920 assert(VT == N1.getValueType() &&
3921 "Dest and insert subvector source types must match!");
3922 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3923 "Insert subvector must be from smaller vector to larger vector!");
3924 if (isa<ConstantSDNode>(Index)) {
3925 assert((N2.getValueType().getVectorNumElements() +
3926 cast<ConstantSDNode>(Index)->getZExtValue()
3927 <= VT.getVectorNumElements())
3928 && "Insert subvector overflow!");
3931 // Trivial insertion.
3932 if (VT.getSimpleVT() == N2.getSimpleValueType())
3938 // Fold bit_convert nodes from a type to themselves.
3939 if (N1.getValueType() == VT)
3944 // Memoize node if it doesn't produce a flag.
3946 SDVTList VTs = getVTList(VT);
3947 if (VT != MVT::Glue) {
3948 SDValue Ops[] = { N1, N2, N3 };
3949 FoldingSetNodeID ID;
3950 AddNodeIDNode(ID, Opcode, VTs, Ops);
3952 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3953 return SDValue(E, 0);
3955 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3956 DL.getDebugLoc(), VTs, N1, N2, N3);
3957 CSEMap.InsertNode(N, IP);
3959 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3960 DL.getDebugLoc(), VTs, N1, N2, N3);
3964 return SDValue(N, 0);
3967 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3968 SDValue N1, SDValue N2, SDValue N3,
3970 SDValue Ops[] = { N1, N2, N3, N4 };
3971 return getNode(Opcode, DL, VT, Ops);
3974 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3975 SDValue N1, SDValue N2, SDValue N3,
3976 SDValue N4, SDValue N5) {
3977 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3978 return getNode(Opcode, DL, VT, Ops);
3981 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3982 /// the incoming stack arguments to be loaded from the stack.
3983 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3984 SmallVector<SDValue, 8> ArgChains;
3986 // Include the original chain at the beginning of the list. When this is
3987 // used by target LowerCall hooks, this helps legalize find the
3988 // CALLSEQ_BEGIN node.
3989 ArgChains.push_back(Chain);
3991 // Add a chain value for each stack argument.
3992 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3993 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3994 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3995 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3996 if (FI->getIndex() < 0)
3997 ArgChains.push_back(SDValue(L, 1));
3999 // Build a tokenfactor for all the chains.
4000 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4003 /// getMemsetValue - Vectorized representation of the memset value
4005 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4007 assert(Value.getOpcode() != ISD::UNDEF);
4009 unsigned NumBits = VT.getScalarType().getSizeInBits();
4010 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4011 assert(C->getAPIntValue().getBitWidth() == 8);
4012 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4014 return DAG.getConstant(Val, dl, VT);
4015 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4019 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4020 EVT IntVT = VT.getScalarType();
4021 if (!IntVT.isInteger())
4022 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4024 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4026 // Use a multiplication with 0x010101... to extend the input to the
4028 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4029 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4030 DAG.getConstant(Magic, dl, IntVT));
4033 if (VT != Value.getValueType() && !VT.isInteger())
4034 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4035 if (VT != Value.getValueType()) {
4036 assert(VT.getVectorElementType() == Value.getValueType() &&
4037 "value type should be one vector element here");
4038 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4039 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4045 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4046 /// used when a memcpy is turned into a memset when the source is a constant
4048 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4049 const TargetLowering &TLI, StringRef Str) {
4050 // Handle vector with all elements zero.
4053 return DAG.getConstant(0, dl, VT);
4054 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4055 return DAG.getConstantFP(0.0, dl, VT);
4056 else if (VT.isVector()) {
4057 unsigned NumElts = VT.getVectorNumElements();
4058 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4059 return DAG.getNode(ISD::BITCAST, dl, VT,
4060 DAG.getConstant(0, dl,
4061 EVT::getVectorVT(*DAG.getContext(),
4064 llvm_unreachable("Expected type!");
4067 assert(!VT.isVector() && "Can't handle vector type here!");
4068 unsigned NumVTBits = VT.getSizeInBits();
4069 unsigned NumVTBytes = NumVTBits / 8;
4070 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4072 APInt Val(NumVTBits, 0);
4073 if (DAG.getDataLayout().isLittleEndian()) {
4074 for (unsigned i = 0; i != NumBytes; ++i)
4075 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4077 for (unsigned i = 0; i != NumBytes; ++i)
4078 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4081 // If the "cost" of materializing the integer immediate is less than the cost
4082 // of a load, then it is cost effective to turn the load into the immediate.
4083 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4084 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4085 return DAG.getConstant(Val, dl, VT);
4086 return SDValue(nullptr, 0);
4089 /// getMemBasePlusOffset - Returns base and offset node for the
4091 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4092 SelectionDAG &DAG) {
4093 EVT VT = Base.getValueType();
4094 return DAG.getNode(ISD::ADD, dl,
4095 VT, Base, DAG.getConstant(Offset, dl, VT));
4098 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4100 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4101 unsigned SrcDelta = 0;
4102 GlobalAddressSDNode *G = nullptr;
4103 if (Src.getOpcode() == ISD::GlobalAddress)
4104 G = cast<GlobalAddressSDNode>(Src);
4105 else if (Src.getOpcode() == ISD::ADD &&
4106 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4107 Src.getOperand(1).getOpcode() == ISD::Constant) {
4108 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4109 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4114 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4117 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4118 /// Return true if the number of memory ops is below the threshold (Limit).
4119 /// It returns the types of the sequence of memory ops to perform
4120 /// memset / memcpy by reference.
4121 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4122 unsigned Limit, uint64_t Size,
4123 unsigned DstAlign, unsigned SrcAlign,
4129 const TargetLowering &TLI) {
4130 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4131 "Expecting memcpy / memset source to meet alignment requirement!");
4132 // If 'SrcAlign' is zero, that means the memory operation does not need to
4133 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4134 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4135 // is the specified alignment of the memory operation. If it is zero, that
4136 // means it's possible to change the alignment of the destination.
4137 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4138 // not need to be loaded.
4139 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4140 IsMemset, ZeroMemset, MemcpyStrSrc,
4141 DAG.getMachineFunction());
4143 if (VT == MVT::Other) {
4145 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4146 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4147 VT = TLI.getPointerTy(DAG.getDataLayout());
4149 switch (DstAlign & 7) {
4150 case 0: VT = MVT::i64; break;
4151 case 4: VT = MVT::i32; break;
4152 case 2: VT = MVT::i16; break;
4153 default: VT = MVT::i8; break;
4158 while (!TLI.isTypeLegal(LVT))
4159 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4160 assert(LVT.isInteger());
4166 unsigned NumMemOps = 0;
4168 unsigned VTSize = VT.getSizeInBits() / 8;
4169 while (VTSize > Size) {
4170 // For now, only use non-vector load / store's for the left-over pieces.
4175 if (VT.isVector() || VT.isFloatingPoint()) {
4176 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4177 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4178 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4180 else if (NewVT == MVT::i64 &&
4181 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4182 TLI.isSafeMemOpType(MVT::f64)) {
4183 // i64 is usually not legal on 32-bit targets, but f64 may be.
4191 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4192 if (NewVT == MVT::i8)
4194 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4196 NewVTSize = NewVT.getSizeInBits() / 8;
4198 // If the new VT cannot cover all of the remaining bits, then consider
4199 // issuing a (or a pair of) unaligned and overlapping load / store.
4200 // FIXME: Only does this for 64-bit or more since we don't have proper
4201 // cost model for unaligned load / store.
4204 if (NumMemOps && AllowOverlap &&
4205 VTSize >= 8 && NewVTSize < Size &&
4206 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4214 if (++NumMemOps > Limit)
4217 MemOps.push_back(VT);
4224 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4225 // On Darwin, -Os means optimize for size without hurting performance, so
4226 // only really optimize for size when -Oz (MinSize) is used.
4227 if (MF.getTarget().getTargetTriple().isOSDarwin())
4228 return MF.getFunction()->optForMinSize();
4229 return MF.getFunction()->optForSize();
4232 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4233 SDValue Chain, SDValue Dst,
4234 SDValue Src, uint64_t Size,
4235 unsigned Align, bool isVol,
4237 MachinePointerInfo DstPtrInfo,
4238 MachinePointerInfo SrcPtrInfo) {
4239 // Turn a memcpy of undef to nop.
4240 if (Src.getOpcode() == ISD::UNDEF)
4243 // Expand memcpy to a series of load and store ops if the size operand falls
4244 // below a certain threshold.
4245 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4246 // rather than maybe a humongous number of loads and stores.
4247 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4248 std::vector<EVT> MemOps;
4249 bool DstAlignCanChange = false;
4250 MachineFunction &MF = DAG.getMachineFunction();
4251 MachineFrameInfo *MFI = MF.getFrameInfo();
4252 bool OptSize = shouldLowerMemFuncForSize(MF);
4253 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4254 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4255 DstAlignCanChange = true;
4256 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4257 if (Align > SrcAlign)
4260 bool CopyFromStr = isMemSrcFromString(Src, Str);
4261 bool isZeroStr = CopyFromStr && Str.empty();
4262 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4264 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4265 (DstAlignCanChange ? 0 : Align),
4266 (isZeroStr ? 0 : SrcAlign),
4267 false, false, CopyFromStr, true, DAG, TLI))
4270 if (DstAlignCanChange) {
4271 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4272 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4274 // Don't promote to an alignment that would require dynamic stack
4276 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4277 if (!TRI->needsStackRealignment(MF))
4278 while (NewAlign > Align &&
4279 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4282 if (NewAlign > Align) {
4283 // Give the stack frame object a larger alignment if needed.
4284 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4285 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4290 SmallVector<SDValue, 8> OutChains;
4291 unsigned NumMemOps = MemOps.size();
4292 uint64_t SrcOff = 0, DstOff = 0;
4293 for (unsigned i = 0; i != NumMemOps; ++i) {
4295 unsigned VTSize = VT.getSizeInBits() / 8;
4296 SDValue Value, Store;
4298 if (VTSize > Size) {
4299 // Issuing an unaligned load / store pair that overlaps with the previous
4300 // pair. Adjust the offset accordingly.
4301 assert(i == NumMemOps-1 && i != 0);
4302 SrcOff -= VTSize - Size;
4303 DstOff -= VTSize - Size;
4307 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4308 // It's unlikely a store of a vector immediate can be done in a single
4309 // instruction. It would require a load from a constantpool first.
4310 // We only handle zero vectors here.
4311 // FIXME: Handle other cases where store of vector immediate is done in
4312 // a single instruction.
4313 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4314 if (Value.getNode())
4315 Store = DAG.getStore(Chain, dl, Value,
4316 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4317 DstPtrInfo.getWithOffset(DstOff), isVol,
4321 if (!Store.getNode()) {
4322 // The type might not be legal for the target. This should only happen
4323 // if the type is smaller than a legal type, as on PPC, so the right
4324 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4325 // to Load/Store if NVT==VT.
4326 // FIXME does the case above also need this?
4327 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4328 assert(NVT.bitsGE(VT));
4329 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4330 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4331 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4332 false, MinAlign(SrcAlign, SrcOff));
4333 Store = DAG.getTruncStore(Chain, dl, Value,
4334 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4335 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4338 OutChains.push_back(Store);
4344 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4347 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4348 SDValue Chain, SDValue Dst,
4349 SDValue Src, uint64_t Size,
4350 unsigned Align, bool isVol,
4352 MachinePointerInfo DstPtrInfo,
4353 MachinePointerInfo SrcPtrInfo) {
4354 // Turn a memmove of undef to nop.
4355 if (Src.getOpcode() == ISD::UNDEF)
4358 // Expand memmove to a series of load and store ops if the size operand falls
4359 // below a certain threshold.
4360 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4361 std::vector<EVT> MemOps;
4362 bool DstAlignCanChange = false;
4363 MachineFunction &MF = DAG.getMachineFunction();
4364 MachineFrameInfo *MFI = MF.getFrameInfo();
4365 bool OptSize = shouldLowerMemFuncForSize(MF);
4366 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4367 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4368 DstAlignCanChange = true;
4369 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4370 if (Align > SrcAlign)
4372 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4374 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4375 (DstAlignCanChange ? 0 : Align), SrcAlign,
4376 false, false, false, false, DAG, TLI))
4379 if (DstAlignCanChange) {
4380 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4381 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4382 if (NewAlign > Align) {
4383 // Give the stack frame object a larger alignment if needed.
4384 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4385 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4390 uint64_t SrcOff = 0, DstOff = 0;
4391 SmallVector<SDValue, 8> LoadValues;
4392 SmallVector<SDValue, 8> LoadChains;
4393 SmallVector<SDValue, 8> OutChains;
4394 unsigned NumMemOps = MemOps.size();
4395 for (unsigned i = 0; i < NumMemOps; i++) {
4397 unsigned VTSize = VT.getSizeInBits() / 8;
4400 Value = DAG.getLoad(VT, dl, Chain,
4401 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4402 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4403 false, false, SrcAlign);
4404 LoadValues.push_back(Value);
4405 LoadChains.push_back(Value.getValue(1));
4408 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4410 for (unsigned i = 0; i < NumMemOps; i++) {
4412 unsigned VTSize = VT.getSizeInBits() / 8;
4415 Store = DAG.getStore(Chain, dl, LoadValues[i],
4416 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4417 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4418 OutChains.push_back(Store);
4422 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4425 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4428 /// \param DAG Selection DAG where lowered code is placed.
4429 /// \param dl Link to corresponding IR location.
4430 /// \param Chain Control flow dependency.
4431 /// \param Dst Pointer to destination memory location.
4432 /// \param Src Value of byte to write into the memory.
4433 /// \param Size Number of bytes to write.
4434 /// \param Align Alignment of the destination in bytes.
4435 /// \param isVol True if destination is volatile.
4436 /// \param DstPtrInfo IR information on the memory pointer.
4437 /// \returns New head in the control flow, if lowering was successful, empty
4438 /// SDValue otherwise.
4440 /// The function tries to replace 'llvm.memset' intrinsic with several store
4441 /// operations and value calculation code. This is usually profitable for small
4443 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4444 SDValue Chain, SDValue Dst,
4445 SDValue Src, uint64_t Size,
4446 unsigned Align, bool isVol,
4447 MachinePointerInfo DstPtrInfo) {
4448 // Turn a memset of undef to nop.
4449 if (Src.getOpcode() == ISD::UNDEF)
4452 // Expand memset to a series of load/store ops if the size operand
4453 // falls below a certain threshold.
4454 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4455 std::vector<EVT> MemOps;
4456 bool DstAlignCanChange = false;
4457 MachineFunction &MF = DAG.getMachineFunction();
4458 MachineFrameInfo *MFI = MF.getFrameInfo();
4459 bool OptSize = shouldLowerMemFuncForSize(MF);
4460 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4461 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4462 DstAlignCanChange = true;
4464 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4465 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4466 Size, (DstAlignCanChange ? 0 : Align), 0,
4467 true, IsZeroVal, false, true, DAG, TLI))
4470 if (DstAlignCanChange) {
4471 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4472 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4473 if (NewAlign > Align) {
4474 // Give the stack frame object a larger alignment if needed.
4475 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4476 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4481 SmallVector<SDValue, 8> OutChains;
4482 uint64_t DstOff = 0;
4483 unsigned NumMemOps = MemOps.size();
4485 // Find the largest store and generate the bit pattern for it.
4486 EVT LargestVT = MemOps[0];
4487 for (unsigned i = 1; i < NumMemOps; i++)
4488 if (MemOps[i].bitsGT(LargestVT))
4489 LargestVT = MemOps[i];
4490 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4492 for (unsigned i = 0; i < NumMemOps; i++) {
4494 unsigned VTSize = VT.getSizeInBits() / 8;
4495 if (VTSize > Size) {
4496 // Issuing an unaligned load / store pair that overlaps with the previous
4497 // pair. Adjust the offset accordingly.
4498 assert(i == NumMemOps-1 && i != 0);
4499 DstOff -= VTSize - Size;
4502 // If this store is smaller than the largest store see whether we can get
4503 // the smaller value for free with a truncate.
4504 SDValue Value = MemSetValue;
4505 if (VT.bitsLT(LargestVT)) {
4506 if (!LargestVT.isVector() && !VT.isVector() &&
4507 TLI.isTruncateFree(LargestVT, VT))
4508 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4510 Value = getMemsetValue(Src, VT, DAG, dl);
4512 assert(Value.getValueType() == VT && "Value with wrong type.");
4513 SDValue Store = DAG.getStore(Chain, dl, Value,
4514 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4515 DstPtrInfo.getWithOffset(DstOff),
4516 isVol, false, Align);
4517 OutChains.push_back(Store);
4518 DstOff += VT.getSizeInBits() / 8;
4522 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4525 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4526 SDValue Src, SDValue Size,
4527 unsigned Align, bool isVol, bool AlwaysInline,
4528 bool isTailCall, MachinePointerInfo DstPtrInfo,
4529 MachinePointerInfo SrcPtrInfo) {
4530 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4532 // Check to see if we should lower the memcpy to loads and stores first.
4533 // For cases within the target-specified limits, this is the best choice.
4534 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4536 // Memcpy with size zero? Just return the original chain.
4537 if (ConstantSize->isNullValue())
4540 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4541 ConstantSize->getZExtValue(),Align,
4542 isVol, false, DstPtrInfo, SrcPtrInfo);
4543 if (Result.getNode())
4547 // Then check to see if we should lower the memcpy with target-specific
4548 // code. If the target chooses to do this, this is the next best.
4550 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4551 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4552 DstPtrInfo, SrcPtrInfo);
4553 if (Result.getNode())
4557 // If we really need inline code and the target declined to provide it,
4558 // use a (potentially long) sequence of loads and stores.
4560 assert(ConstantSize && "AlwaysInline requires a constant size!");
4561 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4562 ConstantSize->getZExtValue(), Align, isVol,
4563 true, DstPtrInfo, SrcPtrInfo);
4566 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4567 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4568 // respect volatile, so they may do things like read or write memory
4569 // beyond the given memory regions. But fixing this isn't easy, and most
4570 // people don't care.
4572 // Emit a library call.
4573 TargetLowering::ArgListTy Args;
4574 TargetLowering::ArgListEntry Entry;
4575 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4576 Entry.Node = Dst; Args.push_back(Entry);
4577 Entry.Node = Src; Args.push_back(Entry);
4578 Entry.Node = Size; Args.push_back(Entry);
4579 // FIXME: pass in SDLoc
4580 TargetLowering::CallLoweringInfo CLI(*this);
4583 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4584 Type::getVoidTy(*getContext()),
4585 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4586 TLI->getPointerTy(getDataLayout())),
4589 .setTailCall(isTailCall);
4591 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4592 return CallResult.second;
4595 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4596 SDValue Src, SDValue Size,
4597 unsigned Align, bool isVol, bool isTailCall,
4598 MachinePointerInfo DstPtrInfo,
4599 MachinePointerInfo SrcPtrInfo) {
4600 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4602 // Check to see if we should lower the memmove to loads and stores first.
4603 // For cases within the target-specified limits, this is the best choice.
4604 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4606 // Memmove with size zero? Just return the original chain.
4607 if (ConstantSize->isNullValue())
4611 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4612 ConstantSize->getZExtValue(), Align, isVol,
4613 false, DstPtrInfo, SrcPtrInfo);
4614 if (Result.getNode())
4618 // Then check to see if we should lower the memmove with target-specific
4619 // code. If the target chooses to do this, this is the next best.
4621 SDValue Result = TSI->EmitTargetCodeForMemmove(
4622 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4623 if (Result.getNode())
4627 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4628 // not be safe. See memcpy above for more details.
4630 // Emit a library call.
4631 TargetLowering::ArgListTy Args;
4632 TargetLowering::ArgListEntry Entry;
4633 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4634 Entry.Node = Dst; Args.push_back(Entry);
4635 Entry.Node = Src; Args.push_back(Entry);
4636 Entry.Node = Size; Args.push_back(Entry);
4637 // FIXME: pass in SDLoc
4638 TargetLowering::CallLoweringInfo CLI(*this);
4641 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4642 Type::getVoidTy(*getContext()),
4643 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4644 TLI->getPointerTy(getDataLayout())),
4647 .setTailCall(isTailCall);
4649 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4650 return CallResult.second;
4653 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4654 SDValue Src, SDValue Size,
4655 unsigned Align, bool isVol, bool isTailCall,
4656 MachinePointerInfo DstPtrInfo) {
4657 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4659 // Check to see if we should lower the memset to stores first.
4660 // For cases within the target-specified limits, this is the best choice.
4661 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4663 // Memset with size zero? Just return the original chain.
4664 if (ConstantSize->isNullValue())
4668 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4669 Align, isVol, DstPtrInfo);
4671 if (Result.getNode())
4675 // Then check to see if we should lower the memset with target-specific
4676 // code. If the target chooses to do this, this is the next best.
4678 SDValue Result = TSI->EmitTargetCodeForMemset(
4679 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4680 if (Result.getNode())
4684 // Emit a library call.
4685 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4686 TargetLowering::ArgListTy Args;
4687 TargetLowering::ArgListEntry Entry;
4688 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4689 Args.push_back(Entry);
4691 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4692 Args.push_back(Entry);
4694 Entry.Ty = IntPtrTy;
4695 Args.push_back(Entry);
4697 // FIXME: pass in SDLoc
4698 TargetLowering::CallLoweringInfo CLI(*this);
4701 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4702 Type::getVoidTy(*getContext()),
4703 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4704 TLI->getPointerTy(getDataLayout())),
4707 .setTailCall(isTailCall);
4709 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4710 return CallResult.second;
4713 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4714 SDVTList VTList, ArrayRef<SDValue> Ops,
4715 MachineMemOperand *MMO,
4716 AtomicOrdering SuccessOrdering,
4717 AtomicOrdering FailureOrdering,
4718 SynchronizationScope SynchScope) {
4719 FoldingSetNodeID ID;
4720 ID.AddInteger(MemVT.getRawBits());
4721 AddNodeIDNode(ID, Opcode, VTList, Ops);
4722 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4724 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4725 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4726 return SDValue(E, 0);
4729 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4730 // SDNode doesn't have access to it. This memory will be "leaked" when
4731 // the node is deallocated, but recovered when the allocator is released.
4732 // If the number of operands is less than 5 we use AtomicSDNode's internal
4734 unsigned NumOps = Ops.size();
4735 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4738 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4739 dl.getDebugLoc(), VTList, MemVT,
4740 Ops.data(), DynOps, NumOps, MMO,
4741 SuccessOrdering, FailureOrdering,
4743 CSEMap.InsertNode(N, IP);
4745 return SDValue(N, 0);
4748 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4749 SDVTList VTList, ArrayRef<SDValue> Ops,
4750 MachineMemOperand *MMO,
4751 AtomicOrdering Ordering,
4752 SynchronizationScope SynchScope) {
4753 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4754 Ordering, SynchScope);
4757 SDValue SelectionDAG::getAtomicCmpSwap(
4758 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4759 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4760 unsigned Alignment, AtomicOrdering SuccessOrdering,
4761 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4762 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4763 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4764 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4766 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4767 Alignment = getEVTAlignment(MemVT);
4769 MachineFunction &MF = getMachineFunction();
4771 // FIXME: Volatile isn't really correct; we should keep track of atomic
4772 // orderings in the memoperand.
4773 unsigned Flags = MachineMemOperand::MOVolatile;
4774 Flags |= MachineMemOperand::MOLoad;
4775 Flags |= MachineMemOperand::MOStore;
4777 MachineMemOperand *MMO =
4778 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4780 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4781 SuccessOrdering, FailureOrdering, SynchScope);
4784 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4785 SDVTList VTs, SDValue Chain, SDValue Ptr,
4786 SDValue Cmp, SDValue Swp,
4787 MachineMemOperand *MMO,
4788 AtomicOrdering SuccessOrdering,
4789 AtomicOrdering FailureOrdering,
4790 SynchronizationScope SynchScope) {
4791 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4792 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4793 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4795 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4796 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4797 SuccessOrdering, FailureOrdering, SynchScope);
4800 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4802 SDValue Ptr, SDValue Val,
4803 const Value* PtrVal,
4805 AtomicOrdering Ordering,
4806 SynchronizationScope SynchScope) {
4807 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4808 Alignment = getEVTAlignment(MemVT);
4810 MachineFunction &MF = getMachineFunction();
4811 // An atomic store does not load. An atomic load does not store.
4812 // (An atomicrmw obviously both loads and stores.)
4813 // For now, atomics are considered to be volatile always, and they are
4815 // FIXME: Volatile isn't really correct; we should keep track of atomic
4816 // orderings in the memoperand.
4817 unsigned Flags = MachineMemOperand::MOVolatile;
4818 if (Opcode != ISD::ATOMIC_STORE)
4819 Flags |= MachineMemOperand::MOLoad;
4820 if (Opcode != ISD::ATOMIC_LOAD)
4821 Flags |= MachineMemOperand::MOStore;
4823 MachineMemOperand *MMO =
4824 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4825 MemVT.getStoreSize(), Alignment);
4827 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4828 Ordering, SynchScope);
4831 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4833 SDValue Ptr, SDValue Val,
4834 MachineMemOperand *MMO,
4835 AtomicOrdering Ordering,
4836 SynchronizationScope SynchScope) {
4837 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4838 Opcode == ISD::ATOMIC_LOAD_SUB ||
4839 Opcode == ISD::ATOMIC_LOAD_AND ||
4840 Opcode == ISD::ATOMIC_LOAD_OR ||
4841 Opcode == ISD::ATOMIC_LOAD_XOR ||
4842 Opcode == ISD::ATOMIC_LOAD_NAND ||
4843 Opcode == ISD::ATOMIC_LOAD_MIN ||
4844 Opcode == ISD::ATOMIC_LOAD_MAX ||
4845 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4846 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4847 Opcode == ISD::ATOMIC_SWAP ||
4848 Opcode == ISD::ATOMIC_STORE) &&
4849 "Invalid Atomic Op");
4851 EVT VT = Val.getValueType();
4853 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4854 getVTList(VT, MVT::Other);
4855 SDValue Ops[] = {Chain, Ptr, Val};
4856 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4859 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4860 EVT VT, SDValue Chain,
4862 MachineMemOperand *MMO,
4863 AtomicOrdering Ordering,
4864 SynchronizationScope SynchScope) {
4865 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4867 SDVTList VTs = getVTList(VT, MVT::Other);
4868 SDValue Ops[] = {Chain, Ptr};
4869 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4872 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4873 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4874 if (Ops.size() == 1)
4877 SmallVector<EVT, 4> VTs;
4878 VTs.reserve(Ops.size());
4879 for (unsigned i = 0; i < Ops.size(); ++i)
4880 VTs.push_back(Ops[i].getValueType());
4881 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4885 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4886 ArrayRef<SDValue> Ops,
4887 EVT MemVT, MachinePointerInfo PtrInfo,
4888 unsigned Align, bool Vol,
4889 bool ReadMem, bool WriteMem, unsigned Size) {
4890 if (Align == 0) // Ensure that codegen never sees alignment 0
4891 Align = getEVTAlignment(MemVT);
4893 MachineFunction &MF = getMachineFunction();
4896 Flags |= MachineMemOperand::MOStore;
4898 Flags |= MachineMemOperand::MOLoad;
4900 Flags |= MachineMemOperand::MOVolatile;
4902 Size = MemVT.getStoreSize();
4903 MachineMemOperand *MMO =
4904 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4906 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4910 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4911 ArrayRef<SDValue> Ops, EVT MemVT,
4912 MachineMemOperand *MMO) {
4913 assert((Opcode == ISD::INTRINSIC_VOID ||
4914 Opcode == ISD::INTRINSIC_W_CHAIN ||
4915 Opcode == ISD::PREFETCH ||
4916 Opcode == ISD::LIFETIME_START ||
4917 Opcode == ISD::LIFETIME_END ||
4918 (Opcode <= INT_MAX &&
4919 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4920 "Opcode is not a memory-accessing opcode!");
4922 // Memoize the node unless it returns a flag.
4923 MemIntrinsicSDNode *N;
4924 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4925 FoldingSetNodeID ID;
4926 AddNodeIDNode(ID, Opcode, VTList, Ops);
4927 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4929 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4930 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4931 return SDValue(E, 0);
4934 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4935 dl.getDebugLoc(), VTList, Ops,
4937 CSEMap.InsertNode(N, IP);
4939 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4940 dl.getDebugLoc(), VTList, Ops,
4944 return SDValue(N, 0);
4947 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4948 /// MachinePointerInfo record from it. This is particularly useful because the
4949 /// code generator has many cases where it doesn't bother passing in a
4950 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4951 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4952 int64_t Offset = 0) {
4953 // If this is FI+Offset, we can model it.
4954 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4955 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4956 FI->getIndex(), Offset);
4958 // If this is (FI+Offset1)+Offset2, we can model it.
4959 if (Ptr.getOpcode() != ISD::ADD ||
4960 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4961 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4962 return MachinePointerInfo();
4964 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4965 return MachinePointerInfo::getFixedStack(
4966 DAG.getMachineFunction(), FI,
4967 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4970 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4971 /// MachinePointerInfo record from it. This is particularly useful because the
4972 /// code generator has many cases where it doesn't bother passing in a
4973 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4974 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4976 // If the 'Offset' value isn't a constant, we can't handle this.
4977 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4978 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4979 if (OffsetOp.getOpcode() == ISD::UNDEF)
4980 return InferPointerInfo(DAG, Ptr);
4981 return MachinePointerInfo();
4986 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4987 EVT VT, SDLoc dl, SDValue Chain,
4988 SDValue Ptr, SDValue Offset,
4989 MachinePointerInfo PtrInfo, EVT MemVT,
4990 bool isVolatile, bool isNonTemporal, bool isInvariant,
4991 unsigned Alignment, const AAMDNodes &AAInfo,
4992 const MDNode *Ranges) {
4993 assert(Chain.getValueType() == MVT::Other &&
4994 "Invalid chain type");
4995 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4996 Alignment = getEVTAlignment(VT);
4998 unsigned Flags = MachineMemOperand::MOLoad;
5000 Flags |= MachineMemOperand::MOVolatile;
5002 Flags |= MachineMemOperand::MONonTemporal;
5004 Flags |= MachineMemOperand::MOInvariant;
5006 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5008 if (PtrInfo.V.isNull())
5009 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5011 MachineFunction &MF = getMachineFunction();
5012 MachineMemOperand *MMO =
5013 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5015 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5019 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5020 EVT VT, SDLoc dl, SDValue Chain,
5021 SDValue Ptr, SDValue Offset, EVT MemVT,
5022 MachineMemOperand *MMO) {
5024 ExtType = ISD::NON_EXTLOAD;
5025 } else if (ExtType == ISD::NON_EXTLOAD) {
5026 assert(VT == MemVT && "Non-extending load from different memory type!");
5029 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5030 "Should only be an extending load, not truncating!");
5031 assert(VT.isInteger() == MemVT.isInteger() &&
5032 "Cannot convert from FP to Int or Int -> FP!");
5033 assert(VT.isVector() == MemVT.isVector() &&
5034 "Cannot use an ext load to convert to or from a vector!");
5035 assert((!VT.isVector() ||
5036 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5037 "Cannot use an ext load to change the number of vector elements!");
5040 bool Indexed = AM != ISD::UNINDEXED;
5041 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5042 "Unindexed load with an offset!");
5044 SDVTList VTs = Indexed ?
5045 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5046 SDValue Ops[] = { Chain, Ptr, Offset };
5047 FoldingSetNodeID ID;
5048 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5049 ID.AddInteger(MemVT.getRawBits());
5050 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5051 MMO->isNonTemporal(),
5052 MMO->isInvariant()));
5053 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5055 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5056 cast<LoadSDNode>(E)->refineAlignment(MMO);
5057 return SDValue(E, 0);
5059 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5060 dl.getDebugLoc(), VTs, AM, ExtType,
5062 CSEMap.InsertNode(N, IP);
5064 return SDValue(N, 0);
5067 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5068 SDValue Chain, SDValue Ptr,
5069 MachinePointerInfo PtrInfo,
5070 bool isVolatile, bool isNonTemporal,
5071 bool isInvariant, unsigned Alignment,
5072 const AAMDNodes &AAInfo,
5073 const MDNode *Ranges) {
5074 SDValue Undef = getUNDEF(Ptr.getValueType());
5075 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5076 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5080 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5081 SDValue Chain, SDValue Ptr,
5082 MachineMemOperand *MMO) {
5083 SDValue Undef = getUNDEF(Ptr.getValueType());
5084 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5088 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5089 SDValue Chain, SDValue Ptr,
5090 MachinePointerInfo PtrInfo, EVT MemVT,
5091 bool isVolatile, bool isNonTemporal,
5092 bool isInvariant, unsigned Alignment,
5093 const AAMDNodes &AAInfo) {
5094 SDValue Undef = getUNDEF(Ptr.getValueType());
5095 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5096 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5101 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5102 SDValue Chain, SDValue Ptr, EVT MemVT,
5103 MachineMemOperand *MMO) {
5104 SDValue Undef = getUNDEF(Ptr.getValueType());
5105 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5110 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5111 SDValue Offset, ISD::MemIndexedMode AM) {
5112 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5113 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5114 "Load is already a indexed load!");
5115 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5116 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5117 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5118 false, LD->getAlignment());
5121 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5122 SDValue Ptr, MachinePointerInfo PtrInfo,
5123 bool isVolatile, bool isNonTemporal,
5124 unsigned Alignment, const AAMDNodes &AAInfo) {
5125 assert(Chain.getValueType() == MVT::Other &&
5126 "Invalid chain type");
5127 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5128 Alignment = getEVTAlignment(Val.getValueType());
5130 unsigned Flags = MachineMemOperand::MOStore;
5132 Flags |= MachineMemOperand::MOVolatile;
5134 Flags |= MachineMemOperand::MONonTemporal;
5136 if (PtrInfo.V.isNull())
5137 PtrInfo = InferPointerInfo(*this, Ptr);
5139 MachineFunction &MF = getMachineFunction();
5140 MachineMemOperand *MMO =
5141 MF.getMachineMemOperand(PtrInfo, Flags,
5142 Val.getValueType().getStoreSize(), Alignment,
5145 return getStore(Chain, dl, Val, Ptr, MMO);
5148 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5149 SDValue Ptr, MachineMemOperand *MMO) {
5150 assert(Chain.getValueType() == MVT::Other &&
5151 "Invalid chain type");
5152 EVT VT = Val.getValueType();
5153 SDVTList VTs = getVTList(MVT::Other);
5154 SDValue Undef = getUNDEF(Ptr.getValueType());
5155 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5156 FoldingSetNodeID ID;
5157 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5158 ID.AddInteger(VT.getRawBits());
5159 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5160 MMO->isNonTemporal(), MMO->isInvariant()));
5161 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5163 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5164 cast<StoreSDNode>(E)->refineAlignment(MMO);
5165 return SDValue(E, 0);
5167 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5168 dl.getDebugLoc(), VTs,
5169 ISD::UNINDEXED, false, VT, MMO);
5170 CSEMap.InsertNode(N, IP);
5172 return SDValue(N, 0);
5175 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5176 SDValue Ptr, MachinePointerInfo PtrInfo,
5177 EVT SVT,bool isVolatile, bool isNonTemporal,
5179 const AAMDNodes &AAInfo) {
5180 assert(Chain.getValueType() == MVT::Other &&
5181 "Invalid chain type");
5182 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5183 Alignment = getEVTAlignment(SVT);
5185 unsigned Flags = MachineMemOperand::MOStore;
5187 Flags |= MachineMemOperand::MOVolatile;
5189 Flags |= MachineMemOperand::MONonTemporal;
5191 if (PtrInfo.V.isNull())
5192 PtrInfo = InferPointerInfo(*this, Ptr);
5194 MachineFunction &MF = getMachineFunction();
5195 MachineMemOperand *MMO =
5196 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5199 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5202 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5203 SDValue Ptr, EVT SVT,
5204 MachineMemOperand *MMO) {
5205 EVT VT = Val.getValueType();
5207 assert(Chain.getValueType() == MVT::Other &&
5208 "Invalid chain type");
5210 return getStore(Chain, dl, Val, Ptr, MMO);
5212 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5213 "Should only be a truncating store, not extending!");
5214 assert(VT.isInteger() == SVT.isInteger() &&
5215 "Can't do FP-INT conversion!");
5216 assert(VT.isVector() == SVT.isVector() &&
5217 "Cannot use trunc store to convert to or from a vector!");
5218 assert((!VT.isVector() ||
5219 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5220 "Cannot use trunc store to change the number of vector elements!");
5222 SDVTList VTs = getVTList(MVT::Other);
5223 SDValue Undef = getUNDEF(Ptr.getValueType());
5224 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5225 FoldingSetNodeID ID;
5226 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5227 ID.AddInteger(SVT.getRawBits());
5228 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5229 MMO->isNonTemporal(), MMO->isInvariant()));
5230 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5232 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5233 cast<StoreSDNode>(E)->refineAlignment(MMO);
5234 return SDValue(E, 0);
5236 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5237 dl.getDebugLoc(), VTs,
5238 ISD::UNINDEXED, true, SVT, MMO);
5239 CSEMap.InsertNode(N, IP);
5241 return SDValue(N, 0);
5245 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5246 SDValue Offset, ISD::MemIndexedMode AM) {
5247 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5248 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5249 "Store is already a indexed store!");
5250 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5251 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5252 FoldingSetNodeID ID;
5253 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5254 ID.AddInteger(ST->getMemoryVT().getRawBits());
5255 ID.AddInteger(ST->getRawSubclassData());
5256 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5258 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5259 return SDValue(E, 0);
5261 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5262 dl.getDebugLoc(), VTs, AM,
5263 ST->isTruncatingStore(),
5265 ST->getMemOperand());
5266 CSEMap.InsertNode(N, IP);
5268 return SDValue(N, 0);
5272 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5273 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5274 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5276 SDVTList VTs = getVTList(VT, MVT::Other);
5277 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5278 FoldingSetNodeID ID;
5279 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5280 ID.AddInteger(VT.getRawBits());
5281 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5283 MMO->isNonTemporal(),
5284 MMO->isInvariant()));
5285 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5287 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5288 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5289 return SDValue(E, 0);
5291 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5292 dl.getDebugLoc(), Ops, 4, VTs,
5294 CSEMap.InsertNode(N, IP);
5296 return SDValue(N, 0);
5299 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5300 SDValue Ptr, SDValue Mask, EVT MemVT,
5301 MachineMemOperand *MMO, bool isTrunc) {
5302 assert(Chain.getValueType() == MVT::Other &&
5303 "Invalid chain type");
5304 EVT VT = Val.getValueType();
5305 SDVTList VTs = getVTList(MVT::Other);
5306 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5307 FoldingSetNodeID ID;
5308 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5309 ID.AddInteger(VT.getRawBits());
5310 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5311 MMO->isNonTemporal(), MMO->isInvariant()));
5312 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5314 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5315 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5316 return SDValue(E, 0);
5318 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5319 dl.getDebugLoc(), Ops, 4,
5320 VTs, isTrunc, MemVT, MMO);
5321 CSEMap.InsertNode(N, IP);
5323 return SDValue(N, 0);
5327 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5328 ArrayRef<SDValue> Ops,
5329 MachineMemOperand *MMO) {
5331 FoldingSetNodeID ID;
5332 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5333 ID.AddInteger(VT.getRawBits());
5334 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5336 MMO->isNonTemporal(),
5337 MMO->isInvariant()));
5338 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5340 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5341 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5342 return SDValue(E, 0);
5344 MaskedGatherSDNode *N =
5345 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5347 CSEMap.InsertNode(N, IP);
5349 return SDValue(N, 0);
5352 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5353 ArrayRef<SDValue> Ops,
5354 MachineMemOperand *MMO) {
5355 FoldingSetNodeID ID;
5356 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5357 ID.AddInteger(VT.getRawBits());
5358 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5359 MMO->isNonTemporal(),
5360 MMO->isInvariant()));
5361 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5363 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5364 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5365 return SDValue(E, 0);
5368 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5370 CSEMap.InsertNode(N, IP);
5372 return SDValue(N, 0);
5375 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5376 SDValue Chain, SDValue Ptr,
5379 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5380 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5383 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5384 ArrayRef<SDUse> Ops) {
5385 switch (Ops.size()) {
5386 case 0: return getNode(Opcode, DL, VT);
5387 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5388 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5389 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5393 // Copy from an SDUse array into an SDValue array for use with
5394 // the regular getNode logic.
5395 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5396 return getNode(Opcode, DL, VT, NewOps);
5399 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5400 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5401 unsigned NumOps = Ops.size();
5403 case 0: return getNode(Opcode, DL, VT);
5404 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5405 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5406 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5412 case ISD::SELECT_CC: {
5413 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5414 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5415 "LHS and RHS of condition must have same type!");
5416 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5417 "True and False arms of SelectCC must have same type!");
5418 assert(Ops[2].getValueType() == VT &&
5419 "select_cc node must be of same type as true and false value!");
5423 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5424 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5425 "LHS/RHS of comparison should match types!");
5432 SDVTList VTs = getVTList(VT);
5434 if (VT != MVT::Glue) {
5435 FoldingSetNodeID ID;
5436 AddNodeIDNode(ID, Opcode, VTs, Ops);
5439 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5440 return SDValue(E, 0);
5442 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5444 CSEMap.InsertNode(N, IP);
5446 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5451 return SDValue(N, 0);
5454 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5455 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5456 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5459 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5460 ArrayRef<SDValue> Ops) {
5461 if (VTList.NumVTs == 1)
5462 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5466 // FIXME: figure out how to safely handle things like
5467 // int foo(int x) { return 1 << (x & 255); }
5468 // int bar() { return foo(256); }
5469 case ISD::SRA_PARTS:
5470 case ISD::SRL_PARTS:
5471 case ISD::SHL_PARTS:
5472 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5473 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5474 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5475 else if (N3.getOpcode() == ISD::AND)
5476 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5477 // If the and is only masking out bits that cannot effect the shift,
5478 // eliminate the and.
5479 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5480 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5481 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5487 // Memoize the node unless it returns a flag.
5489 unsigned NumOps = Ops.size();
5490 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5491 FoldingSetNodeID ID;
5492 AddNodeIDNode(ID, Opcode, VTList, Ops);
5494 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5495 return SDValue(E, 0);
5498 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5499 DL.getDebugLoc(), VTList, Ops[0]);
5500 } else if (NumOps == 2) {
5501 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5502 DL.getDebugLoc(), VTList, Ops[0],
5504 } else if (NumOps == 3) {
5505 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5506 DL.getDebugLoc(), VTList, Ops[0],
5509 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5512 CSEMap.InsertNode(N, IP);
5515 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5516 DL.getDebugLoc(), VTList, Ops[0]);
5517 } else if (NumOps == 2) {
5518 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5519 DL.getDebugLoc(), VTList, Ops[0],
5521 } else if (NumOps == 3) {
5522 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5523 DL.getDebugLoc(), VTList, Ops[0],
5526 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5531 return SDValue(N, 0);
5534 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5535 return getNode(Opcode, DL, VTList, None);
5538 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5540 SDValue Ops[] = { N1 };
5541 return getNode(Opcode, DL, VTList, Ops);
5544 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5545 SDValue N1, SDValue N2) {
5546 SDValue Ops[] = { N1, N2 };
5547 return getNode(Opcode, DL, VTList, Ops);
5550 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5551 SDValue N1, SDValue N2, SDValue N3) {
5552 SDValue Ops[] = { N1, N2, N3 };
5553 return getNode(Opcode, DL, VTList, Ops);
5556 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5557 SDValue N1, SDValue N2, SDValue N3,
5559 SDValue Ops[] = { N1, N2, N3, N4 };
5560 return getNode(Opcode, DL, VTList, Ops);
5563 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5564 SDValue N1, SDValue N2, SDValue N3,
5565 SDValue N4, SDValue N5) {
5566 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5567 return getNode(Opcode, DL, VTList, Ops);
5570 SDVTList SelectionDAG::getVTList(EVT VT) {
5571 return makeVTList(SDNode::getValueTypeList(VT), 1);
5574 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5575 FoldingSetNodeID ID;
5577 ID.AddInteger(VT1.getRawBits());
5578 ID.AddInteger(VT2.getRawBits());
5581 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5583 EVT *Array = Allocator.Allocate<EVT>(2);
5586 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5587 VTListMap.InsertNode(Result, IP);
5589 return Result->getSDVTList();
5592 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5593 FoldingSetNodeID ID;
5595 ID.AddInteger(VT1.getRawBits());
5596 ID.AddInteger(VT2.getRawBits());
5597 ID.AddInteger(VT3.getRawBits());
5600 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5602 EVT *Array = Allocator.Allocate<EVT>(3);
5606 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5607 VTListMap.InsertNode(Result, IP);
5609 return Result->getSDVTList();
5612 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5613 FoldingSetNodeID ID;
5615 ID.AddInteger(VT1.getRawBits());
5616 ID.AddInteger(VT2.getRawBits());
5617 ID.AddInteger(VT3.getRawBits());
5618 ID.AddInteger(VT4.getRawBits());
5621 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5623 EVT *Array = Allocator.Allocate<EVT>(4);
5628 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5629 VTListMap.InsertNode(Result, IP);
5631 return Result->getSDVTList();
5634 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5635 unsigned NumVTs = VTs.size();
5636 FoldingSetNodeID ID;
5637 ID.AddInteger(NumVTs);
5638 for (unsigned index = 0; index < NumVTs; index++) {
5639 ID.AddInteger(VTs[index].getRawBits());
5643 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5645 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5646 std::copy(VTs.begin(), VTs.end(), Array);
5647 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5648 VTListMap.InsertNode(Result, IP);
5650 return Result->getSDVTList();
5654 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5655 /// specified operands. If the resultant node already exists in the DAG,
5656 /// this does not modify the specified node, instead it returns the node that
5657 /// already exists. If the resultant node does not exist in the DAG, the
5658 /// input node is returned. As a degenerate case, if you specify the same
5659 /// input operands as the node already has, the input node is returned.
5660 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5661 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5663 // Check to see if there is no change.
5664 if (Op == N->getOperand(0)) return N;
5666 // See if the modified node already exists.
5667 void *InsertPos = nullptr;
5668 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5671 // Nope it doesn't. Remove the node from its current place in the maps.
5673 if (!RemoveNodeFromCSEMaps(N))
5674 InsertPos = nullptr;
5676 // Now we update the operands.
5677 N->OperandList[0].set(Op);
5679 // If this gets put into a CSE map, add it.
5680 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5684 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5685 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5687 // Check to see if there is no change.
5688 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5689 return N; // No operands changed, just return the input node.
5691 // See if the modified node already exists.
5692 void *InsertPos = nullptr;
5693 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5696 // Nope it doesn't. Remove the node from its current place in the maps.
5698 if (!RemoveNodeFromCSEMaps(N))
5699 InsertPos = nullptr;
5701 // Now we update the operands.
5702 if (N->OperandList[0] != Op1)
5703 N->OperandList[0].set(Op1);
5704 if (N->OperandList[1] != Op2)
5705 N->OperandList[1].set(Op2);
5707 // If this gets put into a CSE map, add it.
5708 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5712 SDNode *SelectionDAG::
5713 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5714 SDValue Ops[] = { Op1, Op2, Op3 };
5715 return UpdateNodeOperands(N, Ops);
5718 SDNode *SelectionDAG::
5719 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5720 SDValue Op3, SDValue Op4) {
5721 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5722 return UpdateNodeOperands(N, Ops);
5725 SDNode *SelectionDAG::
5726 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5727 SDValue Op3, SDValue Op4, SDValue Op5) {
5728 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5729 return UpdateNodeOperands(N, Ops);
5732 SDNode *SelectionDAG::
5733 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5734 unsigned NumOps = Ops.size();
5735 assert(N->getNumOperands() == NumOps &&
5736 "Update with wrong number of operands");
5738 // If no operands changed just return the input node.
5739 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5742 // See if the modified node already exists.
5743 void *InsertPos = nullptr;
5744 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5747 // Nope it doesn't. Remove the node from its current place in the maps.
5749 if (!RemoveNodeFromCSEMaps(N))
5750 InsertPos = nullptr;
5752 // Now we update the operands.
5753 for (unsigned i = 0; i != NumOps; ++i)
5754 if (N->OperandList[i] != Ops[i])
5755 N->OperandList[i].set(Ops[i]);
5757 // If this gets put into a CSE map, add it.
5758 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5762 /// DropOperands - Release the operands and set this node to have
5764 void SDNode::DropOperands() {
5765 // Unlike the code in MorphNodeTo that does this, we don't need to
5766 // watch for dead nodes here.
5767 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5773 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5776 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5778 SDVTList VTs = getVTList(VT);
5779 return SelectNodeTo(N, MachineOpc, VTs, None);
5782 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5783 EVT VT, SDValue Op1) {
5784 SDVTList VTs = getVTList(VT);
5785 SDValue Ops[] = { Op1 };
5786 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5789 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5790 EVT VT, SDValue Op1,
5792 SDVTList VTs = getVTList(VT);
5793 SDValue Ops[] = { Op1, Op2 };
5794 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5797 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5798 EVT VT, SDValue Op1,
5799 SDValue Op2, SDValue Op3) {
5800 SDVTList VTs = getVTList(VT);
5801 SDValue Ops[] = { Op1, Op2, Op3 };
5802 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5805 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5806 EVT VT, ArrayRef<SDValue> Ops) {
5807 SDVTList VTs = getVTList(VT);
5808 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5811 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5812 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5813 SDVTList VTs = getVTList(VT1, VT2);
5814 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5817 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5819 SDVTList VTs = getVTList(VT1, VT2);
5820 return SelectNodeTo(N, MachineOpc, VTs, None);
5823 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5824 EVT VT1, EVT VT2, EVT VT3,
5825 ArrayRef<SDValue> Ops) {
5826 SDVTList VTs = getVTList(VT1, VT2, VT3);
5827 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5830 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5831 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5832 ArrayRef<SDValue> Ops) {
5833 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5834 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5837 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5840 SDVTList VTs = getVTList(VT1, VT2);
5841 SDValue Ops[] = { Op1 };
5842 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5845 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5847 SDValue Op1, SDValue Op2) {
5848 SDVTList VTs = getVTList(VT1, VT2);
5849 SDValue Ops[] = { Op1, Op2 };
5850 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5853 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5855 SDValue Op1, SDValue Op2,
5857 SDVTList VTs = getVTList(VT1, VT2);
5858 SDValue Ops[] = { Op1, Op2, Op3 };
5859 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5862 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5863 EVT VT1, EVT VT2, EVT VT3,
5864 SDValue Op1, SDValue Op2,
5866 SDVTList VTs = getVTList(VT1, VT2, VT3);
5867 SDValue Ops[] = { Op1, Op2, Op3 };
5868 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5871 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5872 SDVTList VTs,ArrayRef<SDValue> Ops) {
5873 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5874 // Reset the NodeID to -1.
5879 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5880 /// the line number information on the merged node since it is not possible to
5881 /// preserve the information that operation is associated with multiple lines.
5882 /// This will make the debugger working better at -O0, were there is a higher
5883 /// probability having other instructions associated with that line.
5885 /// For IROrder, we keep the smaller of the two
5886 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5887 DebugLoc NLoc = N->getDebugLoc();
5888 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5889 N->setDebugLoc(DebugLoc());
5891 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5892 N->setIROrder(Order);
5896 /// MorphNodeTo - This *mutates* the specified node to have the specified
5897 /// return type, opcode, and operands.
5899 /// Note that MorphNodeTo returns the resultant node. If there is already a
5900 /// node of the specified opcode and operands, it returns that node instead of
5901 /// the current one. Note that the SDLoc need not be the same.
5903 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5904 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5905 /// node, and because it doesn't require CSE recalculation for any of
5906 /// the node's users.
5908 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5909 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5910 /// the legalizer which maintain worklists that would need to be updated when
5911 /// deleting things.
5912 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5913 SDVTList VTs, ArrayRef<SDValue> Ops) {
5914 unsigned NumOps = Ops.size();
5915 // If an identical node already exists, use it.
5917 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5918 FoldingSetNodeID ID;
5919 AddNodeIDNode(ID, Opc, VTs, Ops);
5920 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5921 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5924 if (!RemoveNodeFromCSEMaps(N))
5927 // Start the morphing.
5929 N->ValueList = VTs.VTs;
5930 N->NumValues = VTs.NumVTs;
5932 // Clear the operands list, updating used nodes to remove this from their
5933 // use list. Keep track of any operands that become dead as a result.
5934 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5935 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5937 SDNode *Used = Use.getNode();
5939 if (Used->use_empty())
5940 DeadNodeSet.insert(Used);
5943 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5944 // Initialize the memory references information.
5945 MN->setMemRefs(nullptr, nullptr);
5946 // If NumOps is larger than the # of operands we can have in a
5947 // MachineSDNode, reallocate the operand list.
5948 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5949 if (MN->OperandsNeedDelete)
5950 delete[] MN->OperandList;
5951 if (NumOps > array_lengthof(MN->LocalOperands))
5952 // We're creating a final node that will live unmorphed for the
5953 // remainder of the current SelectionDAG iteration, so we can allocate
5954 // the operands directly out of a pool with no recycling metadata.
5955 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5956 Ops.data(), NumOps);
5958 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5959 MN->OperandsNeedDelete = false;
5961 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5963 // If NumOps is larger than the # of operands we currently have, reallocate
5964 // the operand list.
5965 if (NumOps > N->NumOperands) {
5966 if (N->OperandsNeedDelete)
5967 delete[] N->OperandList;
5968 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5969 N->OperandsNeedDelete = true;
5971 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5974 // Delete any nodes that are still dead after adding the uses for the
5976 if (!DeadNodeSet.empty()) {
5977 SmallVector<SDNode *, 16> DeadNodes;
5978 for (SDNode *N : DeadNodeSet)
5980 DeadNodes.push_back(N);
5981 RemoveDeadNodes(DeadNodes);
5985 CSEMap.InsertNode(N, IP); // Memoize the new node.
5990 /// getMachineNode - These are used for target selectors to create a new node
5991 /// with specified return type(s), MachineInstr opcode, and operands.
5993 /// Note that getMachineNode returns the resultant node. If there is already a
5994 /// node of the specified opcode and operands, it returns that node instead of
5995 /// the current one.
5997 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5998 SDVTList VTs = getVTList(VT);
5999 return getMachineNode(Opcode, dl, VTs, None);
6003 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6004 SDVTList VTs = getVTList(VT);
6005 SDValue Ops[] = { Op1 };
6006 return getMachineNode(Opcode, dl, VTs, Ops);
6010 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6011 SDValue Op1, SDValue Op2) {
6012 SDVTList VTs = getVTList(VT);
6013 SDValue Ops[] = { Op1, Op2 };
6014 return getMachineNode(Opcode, dl, VTs, Ops);
6018 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6019 SDValue Op1, SDValue Op2, SDValue Op3) {
6020 SDVTList VTs = getVTList(VT);
6021 SDValue Ops[] = { Op1, Op2, Op3 };
6022 return getMachineNode(Opcode, dl, VTs, Ops);
6026 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6027 ArrayRef<SDValue> Ops) {
6028 SDVTList VTs = getVTList(VT);
6029 return getMachineNode(Opcode, dl, VTs, Ops);
6033 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6034 SDVTList VTs = getVTList(VT1, VT2);
6035 return getMachineNode(Opcode, dl, VTs, None);
6039 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6040 EVT VT1, EVT VT2, SDValue Op1) {
6041 SDVTList VTs = getVTList(VT1, VT2);
6042 SDValue Ops[] = { Op1 };
6043 return getMachineNode(Opcode, dl, VTs, Ops);
6047 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6048 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6049 SDVTList VTs = getVTList(VT1, VT2);
6050 SDValue Ops[] = { Op1, Op2 };
6051 return getMachineNode(Opcode, dl, VTs, Ops);
6055 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6056 EVT VT1, EVT VT2, SDValue Op1,
6057 SDValue Op2, SDValue Op3) {
6058 SDVTList VTs = getVTList(VT1, VT2);
6059 SDValue Ops[] = { Op1, Op2, Op3 };
6060 return getMachineNode(Opcode, dl, VTs, Ops);
6064 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6066 ArrayRef<SDValue> Ops) {
6067 SDVTList VTs = getVTList(VT1, VT2);
6068 return getMachineNode(Opcode, dl, VTs, Ops);
6072 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6073 EVT VT1, EVT VT2, EVT VT3,
6074 SDValue Op1, SDValue Op2) {
6075 SDVTList VTs = getVTList(VT1, VT2, VT3);
6076 SDValue Ops[] = { Op1, Op2 };
6077 return getMachineNode(Opcode, dl, VTs, Ops);
6081 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6082 EVT VT1, EVT VT2, EVT VT3,
6083 SDValue Op1, SDValue Op2, SDValue Op3) {
6084 SDVTList VTs = getVTList(VT1, VT2, VT3);
6085 SDValue Ops[] = { Op1, Op2, Op3 };
6086 return getMachineNode(Opcode, dl, VTs, Ops);
6090 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6091 EVT VT1, EVT VT2, EVT VT3,
6092 ArrayRef<SDValue> Ops) {
6093 SDVTList VTs = getVTList(VT1, VT2, VT3);
6094 return getMachineNode(Opcode, dl, VTs, Ops);
6098 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6099 EVT VT2, EVT VT3, EVT VT4,
6100 ArrayRef<SDValue> Ops) {
6101 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6102 return getMachineNode(Opcode, dl, VTs, Ops);
6106 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6107 ArrayRef<EVT> ResultTys,
6108 ArrayRef<SDValue> Ops) {
6109 SDVTList VTs = getVTList(ResultTys);
6110 return getMachineNode(Opcode, dl, VTs, Ops);
6114 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6115 ArrayRef<SDValue> OpsArray) {
6116 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6119 const SDValue *Ops = OpsArray.data();
6120 unsigned NumOps = OpsArray.size();
6123 FoldingSetNodeID ID;
6124 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6126 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6127 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6131 // Allocate a new MachineSDNode.
6132 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6133 DL.getDebugLoc(), VTs);
6135 // Initialize the operands list.
6136 if (NumOps > array_lengthof(N->LocalOperands))
6137 // We're creating a final node that will live unmorphed for the
6138 // remainder of the current SelectionDAG iteration, so we can allocate
6139 // the operands directly out of a pool with no recycling metadata.
6140 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6143 N->InitOperands(N->LocalOperands, Ops, NumOps);
6144 N->OperandsNeedDelete = false;
6147 CSEMap.InsertNode(N, IP);
6153 /// getTargetExtractSubreg - A convenience function for creating
6154 /// TargetOpcode::EXTRACT_SUBREG nodes.
6156 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6158 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6159 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6160 VT, Operand, SRIdxVal);
6161 return SDValue(Subreg, 0);
6164 /// getTargetInsertSubreg - A convenience function for creating
6165 /// TargetOpcode::INSERT_SUBREG nodes.
6167 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6168 SDValue Operand, SDValue Subreg) {
6169 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6170 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6171 VT, Operand, Subreg, SRIdxVal);
6172 return SDValue(Result, 0);
6175 /// getNodeIfExists - Get the specified node if it's already available, or
6176 /// else return NULL.
6177 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6178 ArrayRef<SDValue> Ops,
6179 const SDNodeFlags *Flags) {
6180 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6181 FoldingSetNodeID ID;
6182 AddNodeIDNode(ID, Opcode, VTList, Ops);
6183 AddNodeIDFlags(ID, Opcode, Flags);
6185 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6191 /// getDbgValue - Creates a SDDbgValue node.
6194 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6195 unsigned R, bool IsIndirect, uint64_t Off,
6196 DebugLoc DL, unsigned O) {
6197 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6198 "Expected inlined-at fields to agree");
6199 return new (DbgInfo->getAlloc())
6200 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6204 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6205 const Value *C, uint64_t Off,
6206 DebugLoc DL, unsigned O) {
6207 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6208 "Expected inlined-at fields to agree");
6209 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6213 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6214 unsigned FI, uint64_t Off,
6215 DebugLoc DL, unsigned O) {
6216 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6217 "Expected inlined-at fields to agree");
6218 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6223 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6224 /// pointed to by a use iterator is deleted, increment the use iterator
6225 /// so that it doesn't dangle.
6227 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6228 SDNode::use_iterator &UI;
6229 SDNode::use_iterator &UE;
6231 void NodeDeleted(SDNode *N, SDNode *E) override {
6232 // Increment the iterator as needed.
6233 while (UI != UE && N == *UI)
6238 RAUWUpdateListener(SelectionDAG &d,
6239 SDNode::use_iterator &ui,
6240 SDNode::use_iterator &ue)
6241 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6246 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6247 /// This can cause recursive merging of nodes in the DAG.
6249 /// This version assumes From has a single result value.
6251 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6252 SDNode *From = FromN.getNode();
6253 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6254 "Cannot replace with this method!");
6255 assert(From != To.getNode() && "Cannot replace uses of with self");
6257 // Iterate over all the existing uses of From. New uses will be added
6258 // to the beginning of the use list, which we avoid visiting.
6259 // This specifically avoids visiting uses of From that arise while the
6260 // replacement is happening, because any such uses would be the result
6261 // of CSE: If an existing node looks like From after one of its operands
6262 // is replaced by To, we don't want to replace of all its users with To
6263 // too. See PR3018 for more info.
6264 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6265 RAUWUpdateListener Listener(*this, UI, UE);
6269 // This node is about to morph, remove its old self from the CSE maps.
6270 RemoveNodeFromCSEMaps(User);
6272 // A user can appear in a use list multiple times, and when this
6273 // happens the uses are usually next to each other in the list.
6274 // To help reduce the number of CSE recomputations, process all
6275 // the uses of this user that we can find this way.
6277 SDUse &Use = UI.getUse();
6280 } while (UI != UE && *UI == User);
6282 // Now that we have modified User, add it back to the CSE maps. If it
6283 // already exists there, recursively merge the results together.
6284 AddModifiedNodeToCSEMaps(User);
6287 // If we just RAUW'd the root, take note.
6288 if (FromN == getRoot())
6292 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6293 /// This can cause recursive merging of nodes in the DAG.
6295 /// This version assumes that for each value of From, there is a
6296 /// corresponding value in To in the same position with the same type.
6298 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6300 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6301 assert((!From->hasAnyUseOfValue(i) ||
6302 From->getValueType(i) == To->getValueType(i)) &&
6303 "Cannot use this version of ReplaceAllUsesWith!");
6306 // Handle the trivial case.
6310 // Iterate over just the existing users of From. See the comments in
6311 // the ReplaceAllUsesWith above.
6312 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6313 RAUWUpdateListener Listener(*this, UI, UE);
6317 // This node is about to morph, remove its old self from the CSE maps.
6318 RemoveNodeFromCSEMaps(User);
6320 // A user can appear in a use list multiple times, and when this
6321 // happens the uses are usually next to each other in the list.
6322 // To help reduce the number of CSE recomputations, process all
6323 // the uses of this user that we can find this way.
6325 SDUse &Use = UI.getUse();
6328 } while (UI != UE && *UI == User);
6330 // Now that we have modified User, add it back to the CSE maps. If it
6331 // already exists there, recursively merge the results together.
6332 AddModifiedNodeToCSEMaps(User);
6335 // If we just RAUW'd the root, take note.
6336 if (From == getRoot().getNode())
6337 setRoot(SDValue(To, getRoot().getResNo()));
6340 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6341 /// This can cause recursive merging of nodes in the DAG.
6343 /// This version can replace From with any result values. To must match the
6344 /// number and types of values returned by From.
6345 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6346 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6347 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6349 // Iterate over just the existing users of From. See the comments in
6350 // the ReplaceAllUsesWith above.
6351 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6352 RAUWUpdateListener Listener(*this, UI, UE);
6356 // This node is about to morph, remove its old self from the CSE maps.
6357 RemoveNodeFromCSEMaps(User);
6359 // A user can appear in a use list multiple times, and when this
6360 // happens the uses are usually next to each other in the list.
6361 // To help reduce the number of CSE recomputations, process all
6362 // the uses of this user that we can find this way.
6364 SDUse &Use = UI.getUse();
6365 const SDValue &ToOp = To[Use.getResNo()];
6368 } while (UI != UE && *UI == User);
6370 // Now that we have modified User, add it back to the CSE maps. If it
6371 // already exists there, recursively merge the results together.
6372 AddModifiedNodeToCSEMaps(User);
6375 // If we just RAUW'd the root, take note.
6376 if (From == getRoot().getNode())
6377 setRoot(SDValue(To[getRoot().getResNo()]));
6380 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6381 /// uses of other values produced by From.getNode() alone. The Deleted
6382 /// vector is handled the same way as for ReplaceAllUsesWith.
6383 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6384 // Handle the really simple, really trivial case efficiently.
6385 if (From == To) return;
6387 // Handle the simple, trivial, case efficiently.
6388 if (From.getNode()->getNumValues() == 1) {
6389 ReplaceAllUsesWith(From, To);
6393 // Iterate over just the existing users of From. See the comments in
6394 // the ReplaceAllUsesWith above.
6395 SDNode::use_iterator UI = From.getNode()->use_begin(),
6396 UE = From.getNode()->use_end();
6397 RAUWUpdateListener Listener(*this, UI, UE);
6400 bool UserRemovedFromCSEMaps = false;
6402 // A user can appear in a use list multiple times, and when this
6403 // happens the uses are usually next to each other in the list.
6404 // To help reduce the number of CSE recomputations, process all
6405 // the uses of this user that we can find this way.
6407 SDUse &Use = UI.getUse();
6409 // Skip uses of different values from the same node.
6410 if (Use.getResNo() != From.getResNo()) {
6415 // If this node hasn't been modified yet, it's still in the CSE maps,
6416 // so remove its old self from the CSE maps.
6417 if (!UserRemovedFromCSEMaps) {
6418 RemoveNodeFromCSEMaps(User);
6419 UserRemovedFromCSEMaps = true;
6424 } while (UI != UE && *UI == User);
6426 // We are iterating over all uses of the From node, so if a use
6427 // doesn't use the specific value, no changes are made.
6428 if (!UserRemovedFromCSEMaps)
6431 // Now that we have modified User, add it back to the CSE maps. If it
6432 // already exists there, recursively merge the results together.
6433 AddModifiedNodeToCSEMaps(User);
6436 // If we just RAUW'd the root, take note.
6437 if (From == getRoot())
6442 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6443 /// to record information about a use.
6450 /// operator< - Sort Memos by User.
6451 bool operator<(const UseMemo &L, const UseMemo &R) {
6452 return (intptr_t)L.User < (intptr_t)R.User;
6456 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6457 /// uses of other values produced by From.getNode() alone. The same value
6458 /// may appear in both the From and To list. The Deleted vector is
6459 /// handled the same way as for ReplaceAllUsesWith.
6460 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6463 // Handle the simple, trivial case efficiently.
6465 return ReplaceAllUsesOfValueWith(*From, *To);
6467 // Read up all the uses and make records of them. This helps
6468 // processing new uses that are introduced during the
6469 // replacement process.
6470 SmallVector<UseMemo, 4> Uses;
6471 for (unsigned i = 0; i != Num; ++i) {
6472 unsigned FromResNo = From[i].getResNo();
6473 SDNode *FromNode = From[i].getNode();
6474 for (SDNode::use_iterator UI = FromNode->use_begin(),
6475 E = FromNode->use_end(); UI != E; ++UI) {
6476 SDUse &Use = UI.getUse();
6477 if (Use.getResNo() == FromResNo) {
6478 UseMemo Memo = { *UI, i, &Use };
6479 Uses.push_back(Memo);
6484 // Sort the uses, so that all the uses from a given User are together.
6485 std::sort(Uses.begin(), Uses.end());
6487 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6488 UseIndex != UseIndexEnd; ) {
6489 // We know that this user uses some value of From. If it is the right
6490 // value, update it.
6491 SDNode *User = Uses[UseIndex].User;
6493 // This node is about to morph, remove its old self from the CSE maps.
6494 RemoveNodeFromCSEMaps(User);
6496 // The Uses array is sorted, so all the uses for a given User
6497 // are next to each other in the list.
6498 // To help reduce the number of CSE recomputations, process all
6499 // the uses of this user that we can find this way.
6501 unsigned i = Uses[UseIndex].Index;
6502 SDUse &Use = *Uses[UseIndex].Use;
6506 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6508 // Now that we have modified User, add it back to the CSE maps. If it
6509 // already exists there, recursively merge the results together.
6510 AddModifiedNodeToCSEMaps(User);
6514 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6515 /// based on their topological order. It returns the maximum id and a vector
6516 /// of the SDNodes* in assigned order by reference.
6517 unsigned SelectionDAG::AssignTopologicalOrder() {
6519 unsigned DAGSize = 0;
6521 // SortedPos tracks the progress of the algorithm. Nodes before it are
6522 // sorted, nodes after it are unsorted. When the algorithm completes
6523 // it is at the end of the list.
6524 allnodes_iterator SortedPos = allnodes_begin();
6526 // Visit all the nodes. Move nodes with no operands to the front of
6527 // the list immediately. Annotate nodes that do have operands with their
6528 // operand count. Before we do this, the Node Id fields of the nodes
6529 // may contain arbitrary values. After, the Node Id fields for nodes
6530 // before SortedPos will contain the topological sort index, and the
6531 // Node Id fields for nodes At SortedPos and after will contain the
6532 // count of outstanding operands.
6533 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6535 checkForCycles(N, this);
6536 unsigned Degree = N->getNumOperands();
6538 // A node with no uses, add it to the result array immediately.
6539 N->setNodeId(DAGSize++);
6540 allnodes_iterator Q = N;
6542 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6543 assert(SortedPos != AllNodes.end() && "Overran node list");
6546 // Temporarily use the Node Id as scratch space for the degree count.
6547 N->setNodeId(Degree);
6551 // Visit all the nodes. As we iterate, move nodes into sorted order,
6552 // such that by the time the end is reached all nodes will be sorted.
6553 for (SDNode &Node : allnodes()) {
6555 checkForCycles(N, this);
6556 // N is in sorted position, so all its uses have one less operand
6557 // that needs to be sorted.
6558 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6561 unsigned Degree = P->getNodeId();
6562 assert(Degree != 0 && "Invalid node degree");
6565 // All of P's operands are sorted, so P may sorted now.
6566 P->setNodeId(DAGSize++);
6568 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6569 assert(SortedPos != AllNodes.end() && "Overran node list");
6572 // Update P's outstanding operand count.
6573 P->setNodeId(Degree);
6576 if (&Node == SortedPos) {
6578 allnodes_iterator I = N;
6580 dbgs() << "Overran sorted position:\n";
6581 S->dumprFull(this); dbgs() << "\n";
6582 dbgs() << "Checking if this is due to cycles\n";
6583 checkForCycles(this, true);
6585 llvm_unreachable(nullptr);
6589 assert(SortedPos == AllNodes.end() &&
6590 "Topological sort incomplete!");
6591 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6592 "First node in topological sort is not the entry token!");
6593 assert(AllNodes.front().getNodeId() == 0 &&
6594 "First node in topological sort has non-zero id!");
6595 assert(AllNodes.front().getNumOperands() == 0 &&
6596 "First node in topological sort has operands!");
6597 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6598 "Last node in topologic sort has unexpected id!");
6599 assert(AllNodes.back().use_empty() &&
6600 "Last node in topologic sort has users!");
6601 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6605 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6606 /// value is produced by SD.
6607 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6609 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6610 SD->setHasDebugValue(true);
6612 DbgInfo->add(DB, SD, isParameter);
6615 /// TransferDbgValues - Transfer SDDbgValues.
6616 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6617 if (From == To || !From.getNode()->getHasDebugValue())
6619 SDNode *FromNode = From.getNode();
6620 SDNode *ToNode = To.getNode();
6621 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6622 SmallVector<SDDbgValue *, 2> ClonedDVs;
6623 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6625 SDDbgValue *Dbg = *I;
6626 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6628 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6629 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6630 Dbg->getDebugLoc(), Dbg->getOrder());
6631 ClonedDVs.push_back(Clone);
6634 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6635 E = ClonedDVs.end(); I != E; ++I)
6636 AddDbgValue(*I, ToNode, false);
6639 //===----------------------------------------------------------------------===//
6641 //===----------------------------------------------------------------------===//
6643 HandleSDNode::~HandleSDNode() {
6647 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6648 DebugLoc DL, const GlobalValue *GA,
6649 EVT VT, int64_t o, unsigned char TF)
6650 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6654 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6655 SDValue X, unsigned SrcAS,
6657 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6658 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6660 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6661 EVT memvt, MachineMemOperand *mmo)
6662 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6663 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6664 MMO->isNonTemporal(), MMO->isInvariant());
6665 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6666 assert(isNonTemporal() == MMO->isNonTemporal() &&
6667 "Non-temporal encoding error!");
6668 // We check here that the size of the memory operand fits within the size of
6669 // the MMO. This is because the MMO might indicate only a possible address
6670 // range instead of specifying the affected memory addresses precisely.
6671 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6674 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6675 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6676 : SDNode(Opc, Order, dl, VTs, Ops),
6677 MemoryVT(memvt), MMO(mmo) {
6678 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6679 MMO->isNonTemporal(), MMO->isInvariant());
6680 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6681 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6684 /// Profile - Gather unique data for the node.
6686 void SDNode::Profile(FoldingSetNodeID &ID) const {
6687 AddNodeIDNode(ID, this);
6692 std::vector<EVT> VTs;
6695 VTs.reserve(MVT::LAST_VALUETYPE);
6696 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6697 VTs.push_back(MVT((MVT::SimpleValueType)i));
6702 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6703 static ManagedStatic<EVTArray> SimpleVTArray;
6704 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6706 /// getValueTypeList - Return a pointer to the specified value type.
6708 const EVT *SDNode::getValueTypeList(EVT VT) {
6709 if (VT.isExtended()) {
6710 sys::SmartScopedLock<true> Lock(*VTMutex);
6711 return &(*EVTs->insert(VT).first);
6713 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6714 "Value type out of range!");
6715 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6719 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6720 /// indicated value. This method ignores uses of other values defined by this
6722 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6723 assert(Value < getNumValues() && "Bad value!");
6725 // TODO: Only iterate over uses of a given value of the node
6726 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6727 if (UI.getUse().getResNo() == Value) {
6734 // Found exactly the right number of uses?
6739 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6740 /// value. This method ignores uses of other values defined by this operation.
6741 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6742 assert(Value < getNumValues() && "Bad value!");
6744 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6745 if (UI.getUse().getResNo() == Value)
6752 /// isOnlyUserOf - Return true if this node is the only use of N.
6754 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6756 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6767 /// isOperand - Return true if this node is an operand of N.
6769 bool SDValue::isOperandOf(const SDNode *N) const {
6770 for (const SDValue &Op : N->op_values())
6776 bool SDNode::isOperandOf(const SDNode *N) const {
6777 for (const SDValue &Op : N->op_values())
6778 if (this == Op.getNode())
6783 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6784 /// be a chain) reaches the specified operand without crossing any
6785 /// side-effecting instructions on any chain path. In practice, this looks
6786 /// through token factors and non-volatile loads. In order to remain efficient,
6787 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6788 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6789 unsigned Depth) const {
6790 if (*this == Dest) return true;
6792 // Don't search too deeply, we just want to be able to see through
6793 // TokenFactor's etc.
6794 if (Depth == 0) return false;
6796 // If this is a token factor, all inputs to the TF happen in parallel. If any
6797 // of the operands of the TF does not reach dest, then we cannot do the xform.
6798 if (getOpcode() == ISD::TokenFactor) {
6799 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6800 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6805 // Loads don't have side effects, look through them.
6806 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6807 if (!Ld->isVolatile())
6808 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6813 /// hasPredecessor - Return true if N is a predecessor of this node.
6814 /// N is either an operand of this node, or can be reached by recursively
6815 /// traversing up the operands.
6816 /// NOTE: This is an expensive method. Use it carefully.
6817 bool SDNode::hasPredecessor(const SDNode *N) const {
6818 SmallPtrSet<const SDNode *, 32> Visited;
6819 SmallVector<const SDNode *, 16> Worklist;
6820 return hasPredecessorHelper(N, Visited, Worklist);
6824 SDNode::hasPredecessorHelper(const SDNode *N,
6825 SmallPtrSetImpl<const SDNode *> &Visited,
6826 SmallVectorImpl<const SDNode *> &Worklist) const {
6827 if (Visited.empty()) {
6828 Worklist.push_back(this);
6830 // Take a look in the visited set. If we've already encountered this node
6831 // we needn't search further.
6832 if (Visited.count(N))
6836 // Haven't visited N yet. Continue the search.
6837 while (!Worklist.empty()) {
6838 const SDNode *M = Worklist.pop_back_val();
6839 for (const SDValue &OpV : M->op_values()) {
6840 SDNode *Op = OpV.getNode();
6841 if (Visited.insert(Op).second)
6842 Worklist.push_back(Op);
6851 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6852 assert(Num < NumOperands && "Invalid child # of SDNode!");
6853 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6856 const SDNodeFlags *SDNode::getFlags() const {
6857 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6858 return &FlagsNode->Flags;
6862 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6863 assert(N->getNumValues() == 1 &&
6864 "Can't unroll a vector with multiple results!");
6866 EVT VT = N->getValueType(0);
6867 unsigned NE = VT.getVectorNumElements();
6868 EVT EltVT = VT.getVectorElementType();
6871 SmallVector<SDValue, 8> Scalars;
6872 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6874 // If ResNE is 0, fully unroll the vector op.
6877 else if (NE > ResNE)
6881 for (i= 0; i != NE; ++i) {
6882 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6883 SDValue Operand = N->getOperand(j);
6884 EVT OperandVT = Operand.getValueType();
6885 if (OperandVT.isVector()) {
6886 // A vector operand; extract a single element.
6887 EVT OperandEltVT = OperandVT.getVectorElementType();
6889 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6890 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6892 // A scalar operand; just use it as is.
6893 Operands[j] = Operand;
6897 switch (N->getOpcode()) {
6899 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6904 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6911 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6912 getShiftAmountOperand(Operands[0].getValueType(),
6915 case ISD::SIGN_EXTEND_INREG:
6916 case ISD::FP_ROUND_INREG: {
6917 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6918 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6920 getValueType(ExtVT)));
6925 for (; i < ResNE; ++i)
6926 Scalars.push_back(getUNDEF(EltVT));
6928 return getNode(ISD::BUILD_VECTOR, dl,
6929 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6933 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6934 /// location that is 'Dist' units away from the location that the 'Base' load
6935 /// is loading from.
6936 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6937 unsigned Bytes, int Dist) const {
6938 if (LD->getChain() != Base->getChain())
6940 EVT VT = LD->getValueType(0);
6941 if (VT.getSizeInBits() / 8 != Bytes)
6944 SDValue Loc = LD->getOperand(1);
6945 SDValue BaseLoc = Base->getOperand(1);
6946 if (Loc.getOpcode() == ISD::FrameIndex) {
6947 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6949 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6950 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6951 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6952 int FS = MFI->getObjectSize(FI);
6953 int BFS = MFI->getObjectSize(BFI);
6954 if (FS != BFS || FS != (int)Bytes) return false;
6955 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6959 if (isBaseWithConstantOffset(Loc)) {
6960 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6961 if (Loc.getOperand(0) == BaseLoc) {
6962 // If the base location is a simple address with no offset itself, then
6963 // the second load's first add operand should be the base address.
6964 if (LocOffset == Dist * (int)Bytes)
6966 } else if (isBaseWithConstantOffset(BaseLoc)) {
6967 // The base location itself has an offset, so subtract that value from the
6968 // second load's offset before comparing to distance * size.
6970 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6971 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6972 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6977 const GlobalValue *GV1 = nullptr;
6978 const GlobalValue *GV2 = nullptr;
6979 int64_t Offset1 = 0;
6980 int64_t Offset2 = 0;
6981 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6982 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6983 if (isGA1 && isGA2 && GV1 == GV2)
6984 return Offset1 == (Offset2 + Dist*Bytes);
6989 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6990 /// it cannot be inferred.
6991 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6992 // If this is a GlobalAddress + cst, return the alignment.
6993 const GlobalValue *GV;
6994 int64_t GVOffset = 0;
6995 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6996 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6997 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6998 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7000 unsigned AlignBits = KnownZero.countTrailingOnes();
7001 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7003 return MinAlign(Align, GVOffset);
7006 // If this is a direct reference to a stack slot, use information about the
7007 // stack slot's alignment.
7008 int FrameIdx = 1 << 31;
7009 int64_t FrameOffset = 0;
7010 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7011 FrameIdx = FI->getIndex();
7012 } else if (isBaseWithConstantOffset(Ptr) &&
7013 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7015 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7016 FrameOffset = Ptr.getConstantOperandVal(1);
7019 if (FrameIdx != (1 << 31)) {
7020 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7021 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7029 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7030 /// which is split (or expanded) into two not necessarily identical pieces.
7031 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7032 // Currently all types are split in half.
7034 if (!VT.isVector()) {
7035 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7037 unsigned NumElements = VT.getVectorNumElements();
7038 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7039 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7042 return std::make_pair(LoVT, HiVT);
7045 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7047 std::pair<SDValue, SDValue>
7048 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7050 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7051 N.getValueType().getVectorNumElements() &&
7052 "More vector elements requested than available!");
7054 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7055 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7056 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7057 getConstant(LoVT.getVectorNumElements(), DL,
7058 TLI->getVectorIdxTy(getDataLayout())));
7059 return std::make_pair(Lo, Hi);
7062 void SelectionDAG::ExtractVectorElements(SDValue Op,
7063 SmallVectorImpl<SDValue> &Args,
7064 unsigned Start, unsigned Count) {
7065 EVT VT = Op.getValueType();
7067 Count = VT.getVectorNumElements();
7069 EVT EltVT = VT.getVectorElementType();
7070 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7072 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7073 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7074 Op, getConstant(i, SL, IdxTy)));
7078 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7079 unsigned GlobalAddressSDNode::getAddressSpace() const {
7080 return getGlobal()->getType()->getAddressSpace();
7084 Type *ConstantPoolSDNode::getType() const {
7085 if (isMachineConstantPoolEntry())
7086 return Val.MachineCPVal->getType();
7087 return Val.ConstVal->getType();
7090 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7092 unsigned &SplatBitSize,
7094 unsigned MinSplatBits,
7095 bool isBigEndian) const {
7096 EVT VT = getValueType(0);
7097 assert(VT.isVector() && "Expected a vector type");
7098 unsigned sz = VT.getSizeInBits();
7099 if (MinSplatBits > sz)
7102 SplatValue = APInt(sz, 0);
7103 SplatUndef = APInt(sz, 0);
7105 // Get the bits. Bits with undefined values (when the corresponding element
7106 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7107 // in SplatValue. If any of the values are not constant, give up and return
7109 unsigned int nOps = getNumOperands();
7110 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7111 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7113 for (unsigned j = 0; j < nOps; ++j) {
7114 unsigned i = isBigEndian ? nOps-1-j : j;
7115 SDValue OpVal = getOperand(i);
7116 unsigned BitPos = j * EltBitSize;
7118 if (OpVal.getOpcode() == ISD::UNDEF)
7119 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7120 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7121 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7122 zextOrTrunc(sz) << BitPos;
7123 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7124 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7129 // The build_vector is all constants or undefs. Find the smallest element
7130 // size that splats the vector.
7132 HasAnyUndefs = (SplatUndef != 0);
7135 unsigned HalfSize = sz / 2;
7136 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7137 APInt LowValue = SplatValue.trunc(HalfSize);
7138 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7139 APInt LowUndef = SplatUndef.trunc(HalfSize);
7141 // If the two halves do not match (ignoring undef bits), stop here.
7142 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7143 MinSplatBits > HalfSize)
7146 SplatValue = HighValue | LowValue;
7147 SplatUndef = HighUndef & LowUndef;
7156 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7157 if (UndefElements) {
7158 UndefElements->clear();
7159 UndefElements->resize(getNumOperands());
7162 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7163 SDValue Op = getOperand(i);
7164 if (Op.getOpcode() == ISD::UNDEF) {
7166 (*UndefElements)[i] = true;
7167 } else if (!Splatted) {
7169 } else if (Splatted != Op) {
7175 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7176 "Can only have a splat without a constant for all undefs.");
7177 return getOperand(0);
7184 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7185 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7189 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7190 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7193 bool BuildVectorSDNode::isConstant() const {
7194 for (const SDValue &Op : op_values()) {
7195 unsigned Opc = Op.getOpcode();
7196 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7202 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7203 // Find the first non-undef value in the shuffle mask.
7205 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7208 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7210 // Make sure all remaining elements are either undef or the same as the first
7212 for (int Idx = Mask[i]; i != e; ++i)
7213 if (Mask[i] >= 0 && Mask[i] != Idx)
7219 static void checkForCyclesHelper(const SDNode *N,
7220 SmallPtrSetImpl<const SDNode*> &Visited,
7221 SmallPtrSetImpl<const SDNode*> &Checked,
7222 const llvm::SelectionDAG *DAG) {
7223 // If this node has already been checked, don't check it again.
7224 if (Checked.count(N))
7227 // If a node has already been visited on this depth-first walk, reject it as
7229 if (!Visited.insert(N).second) {
7230 errs() << "Detected cycle in SelectionDAG\n";
7231 dbgs() << "Offending node:\n";
7232 N->dumprFull(DAG); dbgs() << "\n";
7236 for (const SDValue &Op : N->op_values())
7237 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7244 void llvm::checkForCycles(const llvm::SDNode *N,
7245 const llvm::SelectionDAG *DAG,
7253 assert(N && "Checking nonexistent SDNode");
7254 SmallPtrSet<const SDNode*, 32> visited;
7255 SmallPtrSet<const SDNode*, 32> checked;
7256 checkForCyclesHelper(N, visited, checked, DAG);
7261 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7262 checkForCycles(DAG->getRoot().getNode(), DAG, force);