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/APSInt.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringExtras.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineConstantPool.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineModuleInfo.h"
27 #include "llvm/IR/CallingConv.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/DebugInfo.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/GlobalAlias.h"
34 #include "llvm/IR/GlobalVariable.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/ManagedStatic.h"
40 #include "llvm/Support/MathExtras.h"
41 #include "llvm/Support/Mutex.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Target/TargetInstrInfo.h"
44 #include "llvm/Target/TargetIntrinsicInfo.h"
45 #include "llvm/Target/TargetLowering.h"
46 #include "llvm/Target/TargetMachine.h"
47 #include "llvm/Target/TargetOptions.h"
48 #include "llvm/Target/TargetRegisterInfo.h"
49 #include "llvm/Target/TargetSelectionDAGInfo.h"
50 #include "llvm/Target/TargetSubtargetInfo.h"
57 /// makeVTList - Return an instance of the SDVTList struct initialized with the
58 /// specified members.
59 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
60 SDVTList Res = {VTs, NumVTs};
64 // Default null implementations of the callbacks.
65 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
66 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
68 //===----------------------------------------------------------------------===//
69 // ConstantFPSDNode Class
70 //===----------------------------------------------------------------------===//
72 /// isExactlyValue - We don't rely on operator== working on double values, as
73 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
74 /// As such, this method can be used to do an exact bit-for-bit comparison of
75 /// two floating point values.
76 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
77 return getValueAPF().bitwiseIsEqual(V);
80 bool ConstantFPSDNode::isValueValidForType(EVT VT,
82 assert(VT.isFloatingPoint() && "Can only convert between FP types");
84 // convert modifies in place, so make a copy.
85 APFloat Val2 = APFloat(Val);
87 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
88 APFloat::rmNearestTiesToEven,
93 //===----------------------------------------------------------------------===//
95 //===----------------------------------------------------------------------===//
97 /// isBuildVectorAllOnes - Return true if the specified node is a
98 /// BUILD_VECTOR where all of the elements are ~0 or undef.
99 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
100 // Look through a bit convert.
101 while (N->getOpcode() == ISD::BITCAST)
102 N = N->getOperand(0).getNode();
104 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
106 unsigned i = 0, e = N->getNumOperands();
108 // Skip over all of the undef values.
109 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
112 // Do not accept an all-undef vector.
113 if (i == e) return false;
115 // Do not accept build_vectors that aren't all constants or which have non-~0
116 // elements. We have to be a bit careful here, as the type of the constant
117 // may not be the same as the type of the vector elements due to type
118 // legalization (the elements are promoted to a legal type for the target and
119 // a vector of a type may be legal when the base element type is not).
120 // We only want to check enough bits to cover the vector elements, because
121 // we care if the resultant vector is all ones, not whether the individual
123 SDValue NotZero = N->getOperand(i);
124 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
125 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
126 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
128 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
129 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
134 // Okay, we have at least one ~0 value, check to see if the rest match or are
135 // undefs. Even with the above element type twiddling, this should be OK, as
136 // the same type legalization should have applied to all the elements.
137 for (++i; i != e; ++i)
138 if (N->getOperand(i) != NotZero &&
139 N->getOperand(i).getOpcode() != ISD::UNDEF)
145 /// isBuildVectorAllZeros - Return true if the specified node is a
146 /// BUILD_VECTOR where all of the elements are 0 or undef.
147 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
148 // Look through a bit convert.
149 while (N->getOpcode() == ISD::BITCAST)
150 N = N->getOperand(0).getNode();
152 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
154 bool IsAllUndef = true;
155 for (const SDValue &Op : N->op_values()) {
156 if (Op.getOpcode() == ISD::UNDEF)
159 // Do not accept build_vectors that aren't all constants or which have non-0
160 // elements. We have to be a bit careful here, as the type of the constant
161 // may not be the same as the type of the vector elements due to type
162 // legalization (the elements are promoted to a legal type for the target
163 // and a vector of a type may be legal when the base element type is not).
164 // We only want to check enough bits to cover the vector elements, because
165 // we care if the resultant vector is all zeros, not whether the individual
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (const SDValue &Op : N->op_values()) {
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (const SDValue &Op : N->op_values()) {
206 if (Op.getOpcode() == ISD::UNDEF)
208 if (!isa<ConstantFPSDNode>(Op))
214 /// isScalarToVector - Return true if the specified node is a
215 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
216 /// element is not an undef.
217 bool ISD::isScalarToVector(const SDNode *N) {
218 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
221 if (N->getOpcode() != ISD::BUILD_VECTOR)
223 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
225 unsigned NumElems = N->getNumOperands();
228 for (unsigned i = 1; i < NumElems; ++i) {
229 SDValue V = N->getOperand(i);
230 if (V.getOpcode() != ISD::UNDEF)
236 /// allOperandsUndef - Return true if the node has at least one operand
237 /// and all operands of the specified node are ISD::UNDEF.
238 bool ISD::allOperandsUndef(const SDNode *N) {
239 // Return false if the node has no operands.
240 // This is "logically inconsistent" with the definition of "all" but
241 // is probably the desired behavior.
242 if (N->getNumOperands() == 0)
245 for (const SDValue &Op : N->op_values())
246 if (Op.getOpcode() != ISD::UNDEF)
252 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
255 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
257 return ISD::SIGN_EXTEND;
259 return ISD::ZERO_EXTEND;
264 llvm_unreachable("Invalid LoadExtType");
267 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
268 /// when given the operation for (X op Y).
269 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
270 // To perform this operation, we just need to swap the L and G bits of the
272 unsigned OldL = (Operation >> 2) & 1;
273 unsigned OldG = (Operation >> 1) & 1;
274 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
275 (OldL << 1) | // New G bit
276 (OldG << 2)); // New L bit.
279 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
280 /// 'op' is a valid SetCC operation.
281 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
282 unsigned Operation = Op;
284 Operation ^= 7; // Flip L, G, E bits, but not U.
286 Operation ^= 15; // Flip all of the condition bits.
288 if (Operation > ISD::SETTRUE2)
289 Operation &= ~8; // Don't let N and U bits get set.
291 return ISD::CondCode(Operation);
295 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
296 /// signed operation and 2 if the result is an unsigned comparison. Return zero
297 /// if the operation does not depend on the sign of the input (setne and seteq).
298 static int isSignedOp(ISD::CondCode Opcode) {
300 default: llvm_unreachable("Illegal integer setcc operation!");
302 case ISD::SETNE: return 0;
306 case ISD::SETGE: return 1;
310 case ISD::SETUGE: return 2;
314 /// getSetCCOrOperation - Return the result of a logical OR between different
315 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
316 /// returns SETCC_INVALID if it is not possible to represent the resultant
318 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
320 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
321 // Cannot fold a signed integer setcc with an unsigned integer setcc.
322 return ISD::SETCC_INVALID;
324 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
326 // If the N and U bits get set then the resultant comparison DOES suddenly
327 // care about orderedness, and is true when ordered.
328 if (Op > ISD::SETTRUE2)
329 Op &= ~16; // Clear the U bit if the N bit is set.
331 // Canonicalize illegal integer setcc's.
332 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
335 return ISD::CondCode(Op);
338 /// getSetCCAndOperation - Return the result of a logical AND between different
339 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
340 /// function returns zero if it is not possible to represent the resultant
342 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
344 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
345 // Cannot fold a signed setcc with an unsigned setcc.
346 return ISD::SETCC_INVALID;
348 // Combine all of the condition bits.
349 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
351 // Canonicalize illegal integer setcc's.
355 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
356 case ISD::SETOEQ: // SETEQ & SETU[LG]E
357 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
358 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
359 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
366 //===----------------------------------------------------------------------===//
367 // SDNode Profile Support
368 //===----------------------------------------------------------------------===//
370 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
372 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
376 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
377 /// solely with their pointer.
378 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
379 ID.AddPointer(VTList.VTs);
382 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
384 static void AddNodeIDOperands(FoldingSetNodeID &ID,
385 ArrayRef<SDValue> Ops) {
386 for (auto& Op : Ops) {
387 ID.AddPointer(Op.getNode());
388 ID.AddInteger(Op.getResNo());
392 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
394 static void AddNodeIDOperands(FoldingSetNodeID &ID,
395 ArrayRef<SDUse> Ops) {
396 for (auto& Op : Ops) {
397 ID.AddPointer(Op.getNode());
398 ID.AddInteger(Op.getResNo());
402 /// Add logical or fast math flag values to FoldingSetNodeID value.
403 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
404 const SDNodeFlags *Flags) {
405 if (!isBinOpWithFlags(Opcode))
408 unsigned RawFlags = 0;
410 RawFlags = Flags->getRawFlags();
411 ID.AddInteger(RawFlags);
414 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
415 AddNodeIDFlags(ID, N->getOpcode(), N->getFlags());
418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
419 SDVTList VTList, ArrayRef<SDValue> OpList) {
420 AddNodeIDOpcode(ID, OpC);
421 AddNodeIDValueTypes(ID, VTList);
422 AddNodeIDOperands(ID, OpList);
425 /// If this is an SDNode with special info, add this info to the NodeID data.
426 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
427 switch (N->getOpcode()) {
428 case ISD::TargetExternalSymbol:
429 case ISD::ExternalSymbol:
431 llvm_unreachable("Should only be used on nodes with operands");
432 default: break; // Normal nodes don't need extra info.
433 case ISD::TargetConstant:
434 case ISD::Constant: {
435 const ConstantSDNode *C = cast<ConstantSDNode>(N);
436 ID.AddPointer(C->getConstantIntValue());
437 ID.AddBoolean(C->isOpaque());
440 case ISD::TargetConstantFP:
441 case ISD::ConstantFP: {
442 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
445 case ISD::TargetGlobalAddress:
446 case ISD::GlobalAddress:
447 case ISD::TargetGlobalTLSAddress:
448 case ISD::GlobalTLSAddress: {
449 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
450 ID.AddPointer(GA->getGlobal());
451 ID.AddInteger(GA->getOffset());
452 ID.AddInteger(GA->getTargetFlags());
453 ID.AddInteger(GA->getAddressSpace());
456 case ISD::BasicBlock:
457 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
460 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
462 case ISD::RegisterMask:
463 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
466 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
468 case ISD::FrameIndex:
469 case ISD::TargetFrameIndex:
470 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
473 case ISD::TargetJumpTable:
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
475 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
477 case ISD::ConstantPool:
478 case ISD::TargetConstantPool: {
479 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
480 ID.AddInteger(CP->getAlignment());
481 ID.AddInteger(CP->getOffset());
482 if (CP->isMachineConstantPoolEntry())
483 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
485 ID.AddPointer(CP->getConstVal());
486 ID.AddInteger(CP->getTargetFlags());
489 case ISD::TargetIndex: {
490 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
491 ID.AddInteger(TI->getIndex());
492 ID.AddInteger(TI->getOffset());
493 ID.AddInteger(TI->getTargetFlags());
497 const LoadSDNode *LD = cast<LoadSDNode>(N);
498 ID.AddInteger(LD->getMemoryVT().getRawBits());
499 ID.AddInteger(LD->getRawSubclassData());
500 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
504 const StoreSDNode *ST = cast<StoreSDNode>(N);
505 ID.AddInteger(ST->getMemoryVT().getRawBits());
506 ID.AddInteger(ST->getRawSubclassData());
507 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
510 case ISD::ATOMIC_CMP_SWAP:
511 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
512 case ISD::ATOMIC_SWAP:
513 case ISD::ATOMIC_LOAD_ADD:
514 case ISD::ATOMIC_LOAD_SUB:
515 case ISD::ATOMIC_LOAD_AND:
516 case ISD::ATOMIC_LOAD_OR:
517 case ISD::ATOMIC_LOAD_XOR:
518 case ISD::ATOMIC_LOAD_NAND:
519 case ISD::ATOMIC_LOAD_MIN:
520 case ISD::ATOMIC_LOAD_MAX:
521 case ISD::ATOMIC_LOAD_UMIN:
522 case ISD::ATOMIC_LOAD_UMAX:
523 case ISD::ATOMIC_LOAD:
524 case ISD::ATOMIC_STORE: {
525 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
526 ID.AddInteger(AT->getMemoryVT().getRawBits());
527 ID.AddInteger(AT->getRawSubclassData());
528 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
531 case ISD::PREFETCH: {
532 const MemSDNode *PF = cast<MemSDNode>(N);
533 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
536 case ISD::VECTOR_SHUFFLE: {
537 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
538 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
540 ID.AddInteger(SVN->getMaskElt(i));
543 case ISD::TargetBlockAddress:
544 case ISD::BlockAddress: {
545 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
546 ID.AddPointer(BA->getBlockAddress());
547 ID.AddInteger(BA->getOffset());
548 ID.AddInteger(BA->getTargetFlags());
551 } // end switch (N->getOpcode())
553 AddNodeIDFlags(ID, N);
555 // Target specific memory nodes could also have address spaces to check.
556 if (N->isTargetMemoryOpcode())
557 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
560 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
562 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
563 AddNodeIDOpcode(ID, N->getOpcode());
564 // Add the return value info.
565 AddNodeIDValueTypes(ID, N->getVTList());
566 // Add the operand info.
567 AddNodeIDOperands(ID, N->ops());
569 // Handle SDNode leafs with special info.
570 AddNodeIDCustom(ID, N);
573 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
574 /// the CSE map that carries volatility, temporalness, indexing mode, and
575 /// extension/truncation information.
577 static inline unsigned
578 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
579 bool isNonTemporal, bool isInvariant) {
580 assert((ConvType & 3) == ConvType &&
581 "ConvType may not require more than 2 bits!");
582 assert((AM & 7) == AM &&
583 "AM may not require more than 3 bits!");
587 (isNonTemporal << 6) |
591 //===----------------------------------------------------------------------===//
592 // SelectionDAG Class
593 //===----------------------------------------------------------------------===//
595 /// doNotCSE - Return true if CSE should not be performed for this node.
596 static bool doNotCSE(SDNode *N) {
597 if (N->getValueType(0) == MVT::Glue)
598 return true; // Never CSE anything that produces a flag.
600 switch (N->getOpcode()) {
602 case ISD::HANDLENODE:
604 return true; // Never CSE these nodes.
607 // Check that remaining values produced are not flags.
608 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
609 if (N->getValueType(i) == MVT::Glue)
610 return true; // Never CSE anything that produces a flag.
615 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
617 void SelectionDAG::RemoveDeadNodes() {
618 // Create a dummy node (which is not added to allnodes), that adds a reference
619 // to the root node, preventing it from being deleted.
620 HandleSDNode Dummy(getRoot());
622 SmallVector<SDNode*, 128> DeadNodes;
624 // Add all obviously-dead nodes to the DeadNodes worklist.
625 for (SDNode &Node : allnodes())
626 if (Node.use_empty())
627 DeadNodes.push_back(&Node);
629 RemoveDeadNodes(DeadNodes);
631 // If the root changed (e.g. it was a dead load, update the root).
632 setRoot(Dummy.getValue());
635 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
636 /// given list, and any nodes that become unreachable as a result.
637 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
639 // Process the worklist, deleting the nodes and adding their uses to the
641 while (!DeadNodes.empty()) {
642 SDNode *N = DeadNodes.pop_back_val();
644 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
645 DUL->NodeDeleted(N, nullptr);
647 // Take the node out of the appropriate CSE map.
648 RemoveNodeFromCSEMaps(N);
650 // Next, brutally remove the operand list. This is safe to do, as there are
651 // no cycles in the graph.
652 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
654 SDNode *Operand = Use.getNode();
657 // Now that we removed this operand, see if there are no uses of it left.
658 if (Operand->use_empty())
659 DeadNodes.push_back(Operand);
666 void SelectionDAG::RemoveDeadNode(SDNode *N){
667 SmallVector<SDNode*, 16> DeadNodes(1, N);
669 // Create a dummy node that adds a reference to the root node, preventing
670 // it from being deleted. (This matters if the root is an operand of the
672 HandleSDNode Dummy(getRoot());
674 RemoveDeadNodes(DeadNodes);
677 void SelectionDAG::DeleteNode(SDNode *N) {
678 // First take this out of the appropriate CSE map.
679 RemoveNodeFromCSEMaps(N);
681 // Finally, remove uses due to operands of this node, remove from the
682 // AllNodes list, and delete the node.
683 DeleteNodeNotInCSEMaps(N);
686 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
687 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
688 assert(N->use_empty() && "Cannot delete a node that is not dead!");
690 // Drop all of the operands and decrement used node's use counts.
696 void SDDbgInfo::erase(const SDNode *Node) {
697 DbgValMapType::iterator I = DbgValMap.find(Node);
698 if (I == DbgValMap.end())
700 for (auto &Val: I->second)
701 Val->setIsInvalidated();
705 void SelectionDAG::DeallocateNode(SDNode *N) {
706 if (N->OperandsNeedDelete)
707 delete[] N->OperandList;
709 // Set the opcode to DELETED_NODE to help catch bugs when node
710 // memory is reallocated.
711 N->NodeType = ISD::DELETED_NODE;
713 NodeAllocator.Deallocate(AllNodes.remove(N));
715 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
716 // them and forget about that node.
721 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
722 static void VerifySDNode(SDNode *N) {
723 switch (N->getOpcode()) {
726 case ISD::BUILD_PAIR: {
727 EVT VT = N->getValueType(0);
728 assert(N->getNumValues() == 1 && "Too many results!");
729 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
730 "Wrong return type!");
731 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
732 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
733 "Mismatched operand types!");
734 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
735 "Wrong operand type!");
736 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
737 "Wrong return type size");
740 case ISD::BUILD_VECTOR: {
741 assert(N->getNumValues() == 1 && "Too many results!");
742 assert(N->getValueType(0).isVector() && "Wrong return type!");
743 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
744 "Wrong number of operands!");
745 EVT EltVT = N->getValueType(0).getVectorElementType();
746 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
747 assert((I->getValueType() == EltVT ||
748 (EltVT.isInteger() && I->getValueType().isInteger() &&
749 EltVT.bitsLE(I->getValueType()))) &&
750 "Wrong operand type!");
751 assert(I->getValueType() == N->getOperand(0).getValueType() &&
752 "Operands must all have the same type");
760 /// \brief Insert a newly allocated node into the DAG.
762 /// Handles insertion into the all nodes list and CSE map, as well as
763 /// verification and other common operations when a new node is allocated.
764 void SelectionDAG::InsertNode(SDNode *N) {
765 AllNodes.push_back(N);
767 N->PersistentId = NextPersistentId++;
772 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
773 /// correspond to it. This is useful when we're about to delete or repurpose
774 /// the node. We don't want future request for structurally identical nodes
775 /// to return N anymore.
776 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
778 switch (N->getOpcode()) {
779 case ISD::HANDLENODE: return false; // noop.
781 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
782 "Cond code doesn't exist!");
783 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
784 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
786 case ISD::ExternalSymbol:
787 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
789 case ISD::TargetExternalSymbol: {
790 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
791 Erased = TargetExternalSymbols.erase(
792 std::pair<std::string,unsigned char>(ESN->getSymbol(),
793 ESN->getTargetFlags()));
796 case ISD::MCSymbol: {
797 auto *MCSN = cast<MCSymbolSDNode>(N);
798 Erased = MCSymbols.erase(MCSN->getMCSymbol());
801 case ISD::VALUETYPE: {
802 EVT VT = cast<VTSDNode>(N)->getVT();
803 if (VT.isExtended()) {
804 Erased = ExtendedValueTypeNodes.erase(VT);
806 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
807 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
812 // Remove it from the CSE Map.
813 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
814 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
815 Erased = CSEMap.RemoveNode(N);
819 // Verify that the node was actually in one of the CSE maps, unless it has a
820 // flag result (which cannot be CSE'd) or is one of the special cases that are
821 // not subject to CSE.
822 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
823 !N->isMachineOpcode() && !doNotCSE(N)) {
826 llvm_unreachable("Node is not in map!");
832 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
833 /// maps and modified in place. Add it back to the CSE maps, unless an identical
834 /// node already exists, in which case transfer all its users to the existing
835 /// node. This transfer can potentially trigger recursive merging.
838 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
839 // For node types that aren't CSE'd, just act as if no identical node
842 SDNode *Existing = CSEMap.GetOrInsertNode(N);
844 // If there was already an existing matching node, use ReplaceAllUsesWith
845 // to replace the dead one with the existing one. This can cause
846 // recursive merging of other unrelated nodes down the line.
847 ReplaceAllUsesWith(N, Existing);
849 // N is now dead. Inform the listeners and delete it.
850 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
851 DUL->NodeDeleted(N, Existing);
852 DeleteNodeNotInCSEMaps(N);
857 // If the node doesn't already exist, we updated it. Inform listeners.
858 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
862 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
863 /// were replaced with those specified. If this node is never memoized,
864 /// return null, otherwise return a pointer to the slot it would take. If a
865 /// node already exists with these operands, the slot will be non-null.
866 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
871 SDValue Ops[] = { Op };
873 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
874 AddNodeIDCustom(ID, N);
875 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
879 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
880 /// were replaced with those specified. If this node is never memoized,
881 /// return null, otherwise return a pointer to the slot it would take. If a
882 /// node already exists with these operands, the slot will be non-null.
883 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
884 SDValue Op1, SDValue Op2,
889 SDValue Ops[] = { Op1, Op2 };
891 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
892 AddNodeIDCustom(ID, N);
893 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
898 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
899 /// were replaced with those specified. If this node is never memoized,
900 /// return null, otherwise return a pointer to the slot it would take. If a
901 /// node already exists with these operands, the slot will be non-null.
902 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
908 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
909 AddNodeIDCustom(ID, N);
910 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
914 /// getEVTAlignment - Compute the default alignment value for the
917 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
918 Type *Ty = VT == MVT::iPTR ?
919 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
920 VT.getTypeForEVT(*getContext());
922 return getDataLayout().getABITypeAlignment(Ty);
925 // EntryNode could meaningfully have debug info if we can find it...
926 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
927 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
928 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
929 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
930 UpdateListeners(nullptr) {
931 InsertNode(&EntryNode);
932 DbgInfo = new SDDbgInfo();
935 void SelectionDAG::init(MachineFunction &mf) {
937 TLI = getSubtarget().getTargetLowering();
938 TSI = getSubtarget().getSelectionDAGInfo();
939 Context = &mf.getFunction()->getContext();
942 SelectionDAG::~SelectionDAG() {
943 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
948 void SelectionDAG::allnodes_clear() {
949 assert(&*AllNodes.begin() == &EntryNode);
950 AllNodes.remove(AllNodes.begin());
951 while (!AllNodes.empty())
952 DeallocateNode(&AllNodes.front());
954 NextPersistentId = 0;
958 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
959 SDVTList VTs, SDValue N1,
961 const SDNodeFlags *Flags) {
962 if (isBinOpWithFlags(Opcode)) {
963 // If no flags were passed in, use a default flags object.
965 if (Flags == nullptr)
968 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
969 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
974 BinarySDNode *N = new (NodeAllocator)
975 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
979 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
981 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
983 switch (N->getOpcode()) {
986 case ISD::ConstantFP:
987 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
988 "debug location. Use another overload.");
994 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
995 DebugLoc DL, void *&InsertPos) {
996 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
998 switch (N->getOpcode()) {
999 default: break; // Process only regular (non-target) constant nodes.
1001 case ISD::ConstantFP:
1002 // Erase debug location from the node if the node is used at several
1003 // different places to do not propagate one location to all uses as it
1004 // leads to incorrect debug info.
1005 if (N->getDebugLoc() != DL)
1006 N->setDebugLoc(DebugLoc());
1013 void SelectionDAG::clear() {
1015 OperandAllocator.Reset();
1018 ExtendedValueTypeNodes.clear();
1019 ExternalSymbols.clear();
1020 TargetExternalSymbols.clear();
1022 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1023 static_cast<CondCodeSDNode*>(nullptr));
1024 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1025 static_cast<SDNode*>(nullptr));
1027 EntryNode.UseList = nullptr;
1028 InsertNode(&EntryNode);
1029 Root = getEntryNode();
1033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1034 return VT.bitsGT(Op.getValueType()) ?
1035 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1036 getNode(ISD::TRUNCATE, DL, VT, Op);
1039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1040 return VT.bitsGT(Op.getValueType()) ?
1041 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1042 getNode(ISD::TRUNCATE, DL, VT, Op);
1045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1046 return VT.bitsGT(Op.getValueType()) ?
1047 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1048 getNode(ISD::TRUNCATE, DL, VT, Op);
1051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1053 if (VT.bitsLE(Op.getValueType()))
1054 return getNode(ISD::TRUNCATE, SL, VT, Op);
1056 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1057 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1061 assert(!VT.isVector() &&
1062 "getZeroExtendInReg should use the vector element type instead of "
1063 "the vector type!");
1064 if (Op.getValueType() == VT) return Op;
1065 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1066 APInt Imm = APInt::getLowBitsSet(BitWidth,
1067 VT.getSizeInBits());
1068 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1069 getConstant(Imm, DL, Op.getValueType()));
1072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1073 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1074 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1075 "The sizes of the input and result must match in order to perform the "
1076 "extend in-register.");
1077 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1078 "The destination vector type must have fewer lanes than the input.");
1079 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1083 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1084 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1085 "The sizes of the input and result must match in order to perform the "
1086 "extend in-register.");
1087 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1088 "The destination vector type must have fewer lanes than the input.");
1089 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1093 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1094 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1095 "The sizes of the input and result must match in order to perform the "
1096 "extend in-register.");
1097 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1098 "The destination vector type must have fewer lanes than the input.");
1099 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1105 EVT EltVT = VT.getScalarType();
1107 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1108 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1112 EVT EltVT = VT.getScalarType();
1114 switch (TLI->getBooleanContents(VT)) {
1115 case TargetLowering::ZeroOrOneBooleanContent:
1116 case TargetLowering::UndefinedBooleanContent:
1117 TrueValue = getConstant(1, DL, VT);
1119 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1120 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1124 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1129 EVT EltVT = VT.getScalarType();
1130 assert((EltVT.getSizeInBits() >= 64 ||
1131 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1132 "getConstant with a uint64_t value that doesn't fit in the type!");
1133 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1139 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1143 bool isT, bool isO) {
1144 assert(VT.isInteger() && "Cannot create FP integer constant!");
1146 EVT EltVT = VT.getScalarType();
1147 const ConstantInt *Elt = &Val;
1149 // In some cases the vector type is legal but the element type is illegal and
1150 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1151 // inserted value (the type does not need to match the vector element type).
1152 // Any extra bits introduced will be truncated away.
1153 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1154 TargetLowering::TypePromoteInteger) {
1155 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1156 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1157 Elt = ConstantInt::get(*getContext(), NewVal);
1159 // In other cases the element type is illegal and needs to be expanded, for
1160 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1161 // the value into n parts and use a vector type with n-times the elements.
1162 // Then bitcast to the type requested.
1163 // Legalizing constants too early makes the DAGCombiner's job harder so we
1164 // only legalize if the DAG tells us we must produce legal types.
1165 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1166 TLI->getTypeAction(*getContext(), EltVT) ==
1167 TargetLowering::TypeExpandInteger) {
1168 APInt NewVal = Elt->getValue();
1169 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1170 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1171 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1172 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1174 // Check the temporary vector is the correct size. If this fails then
1175 // getTypeToTransformTo() probably returned a type whose size (in bits)
1176 // isn't a power-of-2 factor of the requested type size.
1177 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1179 SmallVector<SDValue, 2> EltParts;
1180 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1181 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1182 .trunc(ViaEltSizeInBits), DL,
1183 ViaEltVT, isT, isO));
1186 // EltParts is currently in little endian order. If we actually want
1187 // big-endian order then reverse it now.
1188 if (getDataLayout().isBigEndian())
1189 std::reverse(EltParts.begin(), EltParts.end());
1191 // The elements must be reversed when the element order is different
1192 // to the endianness of the elements (because the BITCAST is itself a
1193 // vector shuffle in this situation). However, we do not need any code to
1194 // perform this reversal because getConstant() is producing a vector
1196 // This situation occurs in MIPS MSA.
1198 SmallVector<SDValue, 8> Ops;
1199 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1200 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1202 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1203 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1208 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1209 "APInt size does not match type size!");
1210 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1211 FoldingSetNodeID ID;
1212 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1216 SDNode *N = nullptr;
1217 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1219 return SDValue(N, 0);
1222 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1224 CSEMap.InsertNode(N, IP);
1228 SDValue Result(N, 0);
1229 if (VT.isVector()) {
1230 SmallVector<SDValue, 8> Ops;
1231 Ops.assign(VT.getVectorNumElements(), Result);
1232 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1238 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1243 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1248 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1250 EVT EltVT = VT.getScalarType();
1252 // Do the map lookup using the actual bit pattern for the floating point
1253 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1254 // we don't have issues with SNANs.
1255 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1256 FoldingSetNodeID ID;
1257 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1260 SDNode *N = nullptr;
1261 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1263 return SDValue(N, 0);
1266 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1268 CSEMap.InsertNode(N, IP);
1272 SDValue Result(N, 0);
1273 if (VT.isVector()) {
1274 SmallVector<SDValue, 8> Ops;
1275 Ops.assign(VT.getVectorNumElements(), Result);
1276 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1283 EVT EltVT = VT.getScalarType();
1284 if (EltVT==MVT::f32)
1285 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f64)
1287 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1288 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1291 APFloat apf = APFloat(Val);
1292 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1294 return getConstantFP(apf, DL, VT, isTarget);
1296 llvm_unreachable("Unsupported type in getConstantFP");
1299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1300 EVT VT, int64_t Offset,
1302 unsigned char TargetFlags) {
1303 assert((TargetFlags == 0 || isTargetGA) &&
1304 "Cannot set target flags on target-independent globals");
1306 // Truncate (with sign-extension) the offset value to the pointer size.
1307 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1309 Offset = SignExtend64(Offset, BitWidth);
1312 if (GV->isThreadLocal())
1313 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1315 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1320 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1322 ID.AddInteger(GV->getType()->getAddressSpace());
1324 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1325 return SDValue(E, 0);
1327 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1328 DL.getDebugLoc(), GV, VT,
1329 Offset, TargetFlags);
1330 CSEMap.InsertNode(N, IP);
1332 return SDValue(N, 0);
1335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1336 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1337 FoldingSetNodeID ID;
1338 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1342 return SDValue(E, 0);
1344 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1345 CSEMap.InsertNode(N, IP);
1347 return SDValue(N, 0);
1350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1351 unsigned char TargetFlags) {
1352 assert((TargetFlags == 0 || isTarget) &&
1353 "Cannot set target flags on target-independent jump tables");
1354 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1355 FoldingSetNodeID ID;
1356 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1358 ID.AddInteger(TargetFlags);
1360 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1361 return SDValue(E, 0);
1363 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1365 CSEMap.InsertNode(N, IP);
1367 return SDValue(N, 0);
1370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1371 unsigned Alignment, int Offset,
1373 unsigned char TargetFlags) {
1374 assert((TargetFlags == 0 || isTarget) &&
1375 "Cannot set target flags on target-independent globals");
1377 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1378 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1379 FoldingSetNodeID ID;
1380 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1381 ID.AddInteger(Alignment);
1382 ID.AddInteger(Offset);
1384 ID.AddInteger(TargetFlags);
1386 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1387 return SDValue(E, 0);
1389 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1390 Alignment, TargetFlags);
1391 CSEMap.InsertNode(N, IP);
1393 return SDValue(N, 0);
1397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1398 unsigned Alignment, int Offset,
1400 unsigned char TargetFlags) {
1401 assert((TargetFlags == 0 || isTarget) &&
1402 "Cannot set target flags on target-independent globals");
1404 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1405 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1408 ID.AddInteger(Alignment);
1409 ID.AddInteger(Offset);
1410 C->addSelectionDAGCSEId(ID);
1411 ID.AddInteger(TargetFlags);
1413 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1414 return SDValue(E, 0);
1416 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1417 Alignment, TargetFlags);
1418 CSEMap.InsertNode(N, IP);
1420 return SDValue(N, 0);
1423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1424 unsigned char TargetFlags) {
1425 FoldingSetNodeID ID;
1426 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1427 ID.AddInteger(Index);
1428 ID.AddInteger(Offset);
1429 ID.AddInteger(TargetFlags);
1431 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1432 return SDValue(E, 0);
1434 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1436 CSEMap.InsertNode(N, IP);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1442 FoldingSetNodeID ID;
1443 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1446 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1447 return SDValue(E, 0);
1449 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1450 CSEMap.InsertNode(N, IP);
1452 return SDValue(N, 0);
1455 SDValue SelectionDAG::getValueType(EVT VT) {
1456 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1457 ValueTypeNodes.size())
1458 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1460 SDNode *&N = VT.isExtended() ?
1461 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1463 if (N) return SDValue(N, 0);
1464 N = new (NodeAllocator) VTSDNode(VT);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1470 SDNode *&N = ExternalSymbols[Sym];
1471 if (N) return SDValue(N, 0);
1472 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1474 return SDValue(N, 0);
1477 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1478 SDNode *&N = MCSymbols[Sym];
1480 return SDValue(N, 0);
1481 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1483 return SDValue(N, 0);
1486 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1487 unsigned char TargetFlags) {
1489 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1491 if (N) return SDValue(N, 0);
1492 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1494 return SDValue(N, 0);
1497 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1498 if ((unsigned)Cond >= CondCodeNodes.size())
1499 CondCodeNodes.resize(Cond+1);
1501 if (!CondCodeNodes[Cond]) {
1502 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1503 CondCodeNodes[Cond] = N;
1507 return SDValue(CondCodeNodes[Cond], 0);
1510 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1511 // the shuffle mask M that point at N1 to point at N2, and indices that point
1512 // N2 to point at N1.
1513 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1515 ShuffleVectorSDNode::commuteMask(M);
1518 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1519 SDValue N2, const int *Mask) {
1520 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1521 "Invalid VECTOR_SHUFFLE");
1523 // Canonicalize shuffle undef, undef -> undef
1524 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1525 return getUNDEF(VT);
1527 // Validate that all indices in Mask are within the range of the elements
1528 // input to the shuffle.
1529 unsigned NElts = VT.getVectorNumElements();
1530 SmallVector<int, 8> MaskVec;
1531 for (unsigned i = 0; i != NElts; ++i) {
1532 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1533 MaskVec.push_back(Mask[i]);
1536 // Canonicalize shuffle v, v -> v, undef
1539 for (unsigned i = 0; i != NElts; ++i)
1540 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1543 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1544 if (N1.getOpcode() == ISD::UNDEF)
1545 commuteShuffle(N1, N2, MaskVec);
1547 // If shuffling a splat, try to blend the splat instead. We do this here so
1548 // that even when this arises during lowering we don't have to re-handle it.
1549 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1550 BitVector UndefElements;
1551 SDValue Splat = BV->getSplatValue(&UndefElements);
1555 for (int i = 0; i < (int)NElts; ++i) {
1556 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1559 // If this input comes from undef, mark it as such.
1560 if (UndefElements[MaskVec[i] - Offset]) {
1565 // If we can blend a non-undef lane, use that instead.
1566 if (!UndefElements[i])
1567 MaskVec[i] = i + Offset;
1570 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1571 BlendSplat(N1BV, 0);
1572 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1573 BlendSplat(N2BV, NElts);
1575 // Canonicalize all index into lhs, -> shuffle lhs, undef
1576 // Canonicalize all index into rhs, -> shuffle rhs, undef
1577 bool AllLHS = true, AllRHS = true;
1578 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1579 for (unsigned i = 0; i != NElts; ++i) {
1580 if (MaskVec[i] >= (int)NElts) {
1585 } else if (MaskVec[i] >= 0) {
1589 if (AllLHS && AllRHS)
1590 return getUNDEF(VT);
1591 if (AllLHS && !N2Undef)
1595 commuteShuffle(N1, N2, MaskVec);
1597 // Reset our undef status after accounting for the mask.
1598 N2Undef = N2.getOpcode() == ISD::UNDEF;
1599 // Re-check whether both sides ended up undef.
1600 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1601 return getUNDEF(VT);
1603 // If Identity shuffle return that node.
1604 bool Identity = true, AllSame = true;
1605 for (unsigned i = 0; i != NElts; ++i) {
1606 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1607 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1609 if (Identity && NElts)
1612 // Shuffling a constant splat doesn't change the result.
1616 // Look through any bitcasts. We check that these don't change the number
1617 // (and size) of elements and just changes their types.
1618 while (V.getOpcode() == ISD::BITCAST)
1619 V = V->getOperand(0);
1621 // A splat should always show up as a build vector node.
1622 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1623 BitVector UndefElements;
1624 SDValue Splat = BV->getSplatValue(&UndefElements);
1625 // If this is a splat of an undef, shuffling it is also undef.
1626 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1627 return getUNDEF(VT);
1630 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1632 // We only have a splat which can skip shuffles if there is a splatted
1633 // value and no undef lanes rearranged by the shuffle.
1634 if (Splat && UndefElements.none()) {
1635 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1636 // number of elements match or the value splatted is a zero constant.
1639 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1640 if (C->isNullValue())
1644 // If the shuffle itself creates a splat, build the vector directly.
1645 if (AllSame && SameNumElts) {
1646 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1647 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1649 EVT BuildVT = BV->getValueType(0);
1650 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1652 // We may have jumped through bitcasts, so the type of the
1653 // BUILD_VECTOR may not match the type of the shuffle.
1655 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1661 FoldingSetNodeID ID;
1662 SDValue Ops[2] = { N1, N2 };
1663 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1664 for (unsigned i = 0; i != NElts; ++i)
1665 ID.AddInteger(MaskVec[i]);
1668 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1669 return SDValue(E, 0);
1671 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1672 // SDNode doesn't have access to it. This memory will be "leaked" when
1673 // the node is deallocated, but recovered when the NodeAllocator is released.
1674 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1675 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1677 ShuffleVectorSDNode *N =
1678 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1679 dl.getDebugLoc(), N1, N2,
1681 CSEMap.InsertNode(N, IP);
1683 return SDValue(N, 0);
1686 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1687 MVT VT = SV.getSimpleValueType(0);
1688 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1689 ShuffleVectorSDNode::commuteMask(MaskVec);
1691 SDValue Op0 = SV.getOperand(0);
1692 SDValue Op1 = SV.getOperand(1);
1693 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1696 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1697 SDValue Val, SDValue DTy,
1698 SDValue STy, SDValue Rnd, SDValue Sat,
1699 ISD::CvtCode Code) {
1700 // If the src and dest types are the same and the conversion is between
1701 // integer types of the same sign or two floats, no conversion is necessary.
1703 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1706 FoldingSetNodeID ID;
1707 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1708 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1710 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1711 return SDValue(E, 0);
1713 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1716 CSEMap.InsertNode(N, IP);
1718 return SDValue(N, 0);
1721 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1722 FoldingSetNodeID ID;
1723 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1724 ID.AddInteger(RegNo);
1726 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1727 return SDValue(E, 0);
1729 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1730 CSEMap.InsertNode(N, IP);
1732 return SDValue(N, 0);
1735 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1736 FoldingSetNodeID ID;
1737 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1738 ID.AddPointer(RegMask);
1740 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1741 return SDValue(E, 0);
1743 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1744 CSEMap.InsertNode(N, IP);
1746 return SDValue(N, 0);
1749 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1750 FoldingSetNodeID ID;
1751 SDValue Ops[] = { Root };
1752 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1753 ID.AddPointer(Label);
1755 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1756 return SDValue(E, 0);
1758 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1759 dl.getDebugLoc(), Root, Label);
1760 CSEMap.InsertNode(N, IP);
1762 return SDValue(N, 0);
1766 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1769 unsigned char TargetFlags) {
1770 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1772 FoldingSetNodeID ID;
1773 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1775 ID.AddInteger(Offset);
1776 ID.AddInteger(TargetFlags);
1778 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1779 return SDValue(E, 0);
1781 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1783 CSEMap.InsertNode(N, IP);
1785 return SDValue(N, 0);
1788 SDValue SelectionDAG::getSrcValue(const Value *V) {
1789 assert((!V || V->getType()->isPointerTy()) &&
1790 "SrcValue is not a pointer?");
1792 FoldingSetNodeID ID;
1793 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1797 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1798 return SDValue(E, 0);
1800 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1801 CSEMap.InsertNode(N, IP);
1803 return SDValue(N, 0);
1806 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1807 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1808 FoldingSetNodeID ID;
1809 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1813 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1814 return SDValue(E, 0);
1816 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1817 CSEMap.InsertNode(N, IP);
1819 return SDValue(N, 0);
1822 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1823 if (VT == V.getValueType())
1826 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1829 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1830 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1831 unsigned SrcAS, unsigned DestAS) {
1832 SDValue Ops[] = {Ptr};
1833 FoldingSetNodeID ID;
1834 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1835 ID.AddInteger(SrcAS);
1836 ID.AddInteger(DestAS);
1839 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1840 return SDValue(E, 0);
1842 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1844 VT, Ptr, SrcAS, DestAS);
1845 CSEMap.InsertNode(N, IP);
1847 return SDValue(N, 0);
1850 /// getShiftAmountOperand - Return the specified value casted to
1851 /// the target's desired shift amount type.
1852 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1853 EVT OpTy = Op.getValueType();
1854 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1855 if (OpTy == ShTy || OpTy.isVector()) return Op;
1857 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1860 SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1862 const TargetLowering &TLI = getTargetLoweringInfo();
1863 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1864 EVT VT = Node->getValueType(0);
1865 SDValue Tmp1 = Node->getOperand(0);
1866 SDValue Tmp2 = Node->getOperand(1);
1867 unsigned Align = Node->getConstantOperandVal(3);
1869 SDValue VAListLoad =
1870 getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1, Tmp2,
1871 MachinePointerInfo(V), false, false, false, 0);
1872 SDValue VAList = VAListLoad;
1874 if (Align > TLI.getMinStackArgumentAlignment()) {
1875 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1877 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1878 getConstant(Align - 1, dl, VAList.getValueType()));
1880 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1881 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1884 // Increment the pointer, VAList, to the next vaarg
1885 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1886 getConstant(getDataLayout().getTypeAllocSize(
1887 VT.getTypeForEVT(*getContext())),
1888 dl, VAList.getValueType()));
1889 // Store the incremented VAList to the legalized pointer
1890 Tmp1 = getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2,
1891 MachinePointerInfo(V), false, false, 0);
1892 // Load the actual argument out of the pointer VAList
1893 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo(),
1894 false, false, false, 0);
1897 SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1899 const TargetLowering &TLI = getTargetLoweringInfo();
1900 // This defaults to loading a pointer from the input and storing it to the
1901 // output, returning the chain.
1902 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1903 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1904 SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
1905 Node->getOperand(0), Node->getOperand(2),
1906 MachinePointerInfo(VS), false, false, false, 0);
1907 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1908 MachinePointerInfo(VD), false, false, 0);
1911 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1912 /// specified value type.
1913 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1914 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1915 unsigned ByteSize = VT.getStoreSize();
1916 Type *Ty = VT.getTypeForEVT(*getContext());
1917 unsigned StackAlign =
1918 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1920 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1921 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1924 /// CreateStackTemporary - Create a stack temporary suitable for holding
1925 /// either of the specified value types.
1926 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1927 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1928 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1929 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1930 const DataLayout &DL = getDataLayout();
1932 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1934 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1935 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1936 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1939 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1940 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1941 // These setcc operations always fold.
1945 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1947 case ISD::SETTRUE2: {
1948 TargetLowering::BooleanContent Cnt =
1949 TLI->getBooleanContents(N1->getValueType(0));
1951 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1965 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1969 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1970 const APInt &C2 = N2C->getAPIntValue();
1971 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1972 const APInt &C1 = N1C->getAPIntValue();
1975 default: llvm_unreachable("Unknown integer setcc!");
1976 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1977 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1978 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1979 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1980 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1981 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1982 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1983 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1984 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1985 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1989 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1990 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1991 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1994 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1995 return getUNDEF(VT);
1997 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1998 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1999 return getUNDEF(VT);
2001 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
2002 R==APFloat::cmpLessThan, dl, VT);
2003 case ISD::SETLT: if (R==APFloat::cmpUnordered)
2004 return getUNDEF(VT);
2006 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
2007 case ISD::SETGT: if (R==APFloat::cmpUnordered)
2008 return getUNDEF(VT);
2010 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
2011 case ISD::SETLE: if (R==APFloat::cmpUnordered)
2012 return getUNDEF(VT);
2014 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
2015 R==APFloat::cmpEqual, dl, VT);
2016 case ISD::SETGE: if (R==APFloat::cmpUnordered)
2017 return getUNDEF(VT);
2019 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
2020 R==APFloat::cmpEqual, dl, VT);
2021 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
2022 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
2023 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
2024 R==APFloat::cmpEqual, dl, VT);
2025 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
2026 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
2027 R==APFloat::cmpLessThan, dl, VT);
2028 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
2029 R==APFloat::cmpUnordered, dl, VT);
2030 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
2031 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
2034 // Ensure that the constant occurs on the RHS.
2035 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
2036 MVT CompVT = N1.getValueType().getSimpleVT();
2037 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2040 return getSetCC(dl, VT, N2, N1, SwappedCond);
2044 // Could not fold it.
2048 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2049 /// use this predicate to simplify operations downstream.
2050 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2051 // This predicate is not safe for vector operations.
2052 if (Op.getValueType().isVector())
2055 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2056 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2059 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2060 /// this predicate to simplify operations downstream. Mask is known to be zero
2061 /// for bits that V cannot have.
2062 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2063 unsigned Depth) const {
2064 APInt KnownZero, KnownOne;
2065 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2066 return (KnownZero & Mask) == Mask;
2069 /// Determine which bits of Op are known to be either zero or one and return
2070 /// them in the KnownZero/KnownOne bitsets.
2071 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2072 APInt &KnownOne, unsigned Depth) const {
2073 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2075 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2077 return; // Limit search depth.
2079 APInt KnownZero2, KnownOne2;
2081 switch (Op.getOpcode()) {
2083 // We know all of the bits for a constant!
2084 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2085 KnownZero = ~KnownOne;
2088 // If either the LHS or the RHS are Zero, the result is zero.
2089 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2090 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2092 // Output known-1 bits are only known if set in both the LHS & RHS.
2093 KnownOne &= KnownOne2;
2094 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2095 KnownZero |= KnownZero2;
2098 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2099 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2101 // Output known-0 bits are only known if clear in both the LHS & RHS.
2102 KnownZero &= KnownZero2;
2103 // Output known-1 are known to be set if set in either the LHS | RHS.
2104 KnownOne |= KnownOne2;
2107 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2108 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2110 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2111 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2112 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2113 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2114 KnownZero = KnownZeroOut;
2118 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2119 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2121 // If low bits are zero in either operand, output low known-0 bits.
2122 // Also compute a conserative estimate for high known-0 bits.
2123 // More trickiness is possible, but this is sufficient for the
2124 // interesting case of alignment computation.
2125 KnownOne.clearAllBits();
2126 unsigned TrailZ = KnownZero.countTrailingOnes() +
2127 KnownZero2.countTrailingOnes();
2128 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2129 KnownZero2.countLeadingOnes(),
2130 BitWidth) - BitWidth;
2132 TrailZ = std::min(TrailZ, BitWidth);
2133 LeadZ = std::min(LeadZ, BitWidth);
2134 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2135 APInt::getHighBitsSet(BitWidth, LeadZ);
2139 // For the purposes of computing leading zeros we can conservatively
2140 // treat a udiv as a logical right shift by the power of 2 known to
2141 // be less than the denominator.
2142 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2143 unsigned LeadZ = KnownZero2.countLeadingOnes();
2145 KnownOne2.clearAllBits();
2146 KnownZero2.clearAllBits();
2147 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2148 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2149 if (RHSUnknownLeadingOnes != BitWidth)
2150 LeadZ = std::min(BitWidth,
2151 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2153 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2157 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2158 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2160 // Only known if known in both the LHS and RHS.
2161 KnownOne &= KnownOne2;
2162 KnownZero &= KnownZero2;
2164 case ISD::SELECT_CC:
2165 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2166 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2168 // Only known if known in both the LHS and RHS.
2169 KnownOne &= KnownOne2;
2170 KnownZero &= KnownZero2;
2178 if (Op.getResNo() != 1)
2180 // The boolean result conforms to getBooleanContents.
2181 // If we know the result of a setcc has the top bits zero, use this info.
2182 // We know that we have an integer-based boolean since these operations
2183 // are only available for integer.
2184 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2185 TargetLowering::ZeroOrOneBooleanContent &&
2187 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2190 // If we know the result of a setcc has the top bits zero, use this info.
2191 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2192 TargetLowering::ZeroOrOneBooleanContent &&
2194 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2197 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2198 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2199 unsigned ShAmt = SA->getZExtValue();
2201 // If the shift count is an invalid immediate, don't do anything.
2202 if (ShAmt >= BitWidth)
2205 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2206 KnownZero <<= ShAmt;
2208 // low bits known zero.
2209 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2213 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2214 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2215 unsigned ShAmt = SA->getZExtValue();
2217 // If the shift count is an invalid immediate, don't do anything.
2218 if (ShAmt >= BitWidth)
2221 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2222 KnownZero = KnownZero.lshr(ShAmt);
2223 KnownOne = KnownOne.lshr(ShAmt);
2225 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2226 KnownZero |= HighBits; // High bits known zero.
2230 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2231 unsigned ShAmt = SA->getZExtValue();
2233 // If the shift count is an invalid immediate, don't do anything.
2234 if (ShAmt >= BitWidth)
2237 // If any of the demanded bits are produced by the sign extension, we also
2238 // demand the input sign bit.
2239 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2241 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2242 KnownZero = KnownZero.lshr(ShAmt);
2243 KnownOne = KnownOne.lshr(ShAmt);
2245 // Handle the sign bits.
2246 APInt SignBit = APInt::getSignBit(BitWidth);
2247 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2249 if (KnownZero.intersects(SignBit)) {
2250 KnownZero |= HighBits; // New bits are known zero.
2251 } else if (KnownOne.intersects(SignBit)) {
2252 KnownOne |= HighBits; // New bits are known one.
2256 case ISD::SIGN_EXTEND_INREG: {
2257 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2258 unsigned EBits = EVT.getScalarType().getSizeInBits();
2260 // Sign extension. Compute the demanded bits in the result that are not
2261 // present in the input.
2262 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2264 APInt InSignBit = APInt::getSignBit(EBits);
2265 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2267 // If the sign extended bits are demanded, we know that the sign
2269 InSignBit = InSignBit.zext(BitWidth);
2270 if (NewBits.getBoolValue())
2271 InputDemandedBits |= InSignBit;
2273 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2274 KnownOne &= InputDemandedBits;
2275 KnownZero &= InputDemandedBits;
2277 // If the sign bit of the input is known set or clear, then we know the
2278 // top bits of the result.
2279 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2280 KnownZero |= NewBits;
2281 KnownOne &= ~NewBits;
2282 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2283 KnownOne |= NewBits;
2284 KnownZero &= ~NewBits;
2285 } else { // Input sign bit unknown
2286 KnownZero &= ~NewBits;
2287 KnownOne &= ~NewBits;
2292 case ISD::CTTZ_ZERO_UNDEF:
2294 case ISD::CTLZ_ZERO_UNDEF:
2296 unsigned LowBits = Log2_32(BitWidth)+1;
2297 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2298 KnownOne.clearAllBits();
2302 LoadSDNode *LD = cast<LoadSDNode>(Op);
2303 // If this is a ZEXTLoad and we are looking at the loaded value.
2304 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2305 EVT VT = LD->getMemoryVT();
2306 unsigned MemBits = VT.getScalarType().getSizeInBits();
2307 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2308 } else if (const MDNode *Ranges = LD->getRanges()) {
2309 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2313 case ISD::ZERO_EXTEND: {
2314 EVT InVT = Op.getOperand(0).getValueType();
2315 unsigned InBits = InVT.getScalarType().getSizeInBits();
2316 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2317 KnownZero = KnownZero.trunc(InBits);
2318 KnownOne = KnownOne.trunc(InBits);
2319 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2320 KnownZero = KnownZero.zext(BitWidth);
2321 KnownOne = KnownOne.zext(BitWidth);
2322 KnownZero |= NewBits;
2325 case ISD::SIGN_EXTEND: {
2326 EVT InVT = Op.getOperand(0).getValueType();
2327 unsigned InBits = InVT.getScalarType().getSizeInBits();
2328 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2330 KnownZero = KnownZero.trunc(InBits);
2331 KnownOne = KnownOne.trunc(InBits);
2332 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2334 // Note if the sign bit is known to be zero or one.
2335 bool SignBitKnownZero = KnownZero.isNegative();
2336 bool SignBitKnownOne = KnownOne.isNegative();
2338 KnownZero = KnownZero.zext(BitWidth);
2339 KnownOne = KnownOne.zext(BitWidth);
2341 // If the sign bit is known zero or one, the top bits match.
2342 if (SignBitKnownZero)
2343 KnownZero |= NewBits;
2344 else if (SignBitKnownOne)
2345 KnownOne |= NewBits;
2348 case ISD::ANY_EXTEND: {
2349 EVT InVT = Op.getOperand(0).getValueType();
2350 unsigned InBits = InVT.getScalarType().getSizeInBits();
2351 KnownZero = KnownZero.trunc(InBits);
2352 KnownOne = KnownOne.trunc(InBits);
2353 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2354 KnownZero = KnownZero.zext(BitWidth);
2355 KnownOne = KnownOne.zext(BitWidth);
2358 case ISD::TRUNCATE: {
2359 EVT InVT = Op.getOperand(0).getValueType();
2360 unsigned InBits = InVT.getScalarType().getSizeInBits();
2361 KnownZero = KnownZero.zext(InBits);
2362 KnownOne = KnownOne.zext(InBits);
2363 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2364 KnownZero = KnownZero.trunc(BitWidth);
2365 KnownOne = KnownOne.trunc(BitWidth);
2368 case ISD::AssertZext: {
2369 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2370 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2371 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2372 KnownZero |= (~InMask);
2373 KnownOne &= (~KnownZero);
2377 // All bits are zero except the low bit.
2378 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2382 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2383 // We know that the top bits of C-X are clear if X contains less bits
2384 // than C (i.e. no wrap-around can happen). For example, 20-X is
2385 // positive if we can prove that X is >= 0 and < 16.
2386 if (CLHS->getAPIntValue().isNonNegative()) {
2387 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2388 // NLZ can't be BitWidth with no sign bit
2389 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2390 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2392 // If all of the MaskV bits are known to be zero, then we know the
2393 // output top bits are zero, because we now know that the output is
2395 if ((KnownZero2 & MaskV) == MaskV) {
2396 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2397 // Top bits known zero.
2398 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2406 // Output known-0 bits are known if clear or set in both the low clear bits
2407 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2408 // low 3 bits clear.
2409 // Output known-0 bits are also known if the top bits of each input are
2410 // known to be clear. For example, if one input has the top 10 bits clear
2411 // and the other has the top 8 bits clear, we know the top 7 bits of the
2412 // output must be clear.
2413 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2414 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2415 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2417 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2418 KnownZeroHigh = std::min(KnownZeroHigh,
2419 KnownZero2.countLeadingOnes());
2420 KnownZeroLow = std::min(KnownZeroLow,
2421 KnownZero2.countTrailingOnes());
2423 if (Op.getOpcode() == ISD::ADD) {
2424 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2425 if (KnownZeroHigh > 1)
2426 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2430 // With ADDE, a carry bit may be added in, so we can only use this
2431 // information if we know (at least) that the low two bits are clear. We
2432 // then return to the caller that the low bit is unknown but that other bits
2434 if (KnownZeroLow >= 2) // ADDE
2435 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2439 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2440 const APInt &RA = Rem->getAPIntValue().abs();
2441 if (RA.isPowerOf2()) {
2442 APInt LowBits = RA - 1;
2443 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2445 // The low bits of the first operand are unchanged by the srem.
2446 KnownZero = KnownZero2 & LowBits;
2447 KnownOne = KnownOne2 & LowBits;
2449 // If the first operand is non-negative or has all low bits zero, then
2450 // the upper bits are all zero.
2451 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2452 KnownZero |= ~LowBits;
2454 // If the first operand is negative and not all low bits are zero, then
2455 // the upper bits are all one.
2456 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2457 KnownOne |= ~LowBits;
2458 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2463 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2464 const APInt &RA = Rem->getAPIntValue();
2465 if (RA.isPowerOf2()) {
2466 APInt LowBits = (RA - 1);
2467 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2469 // The upper bits are all zero, the lower ones are unchanged.
2470 KnownZero = KnownZero2 | ~LowBits;
2471 KnownOne = KnownOne2 & LowBits;
2476 // Since the result is less than or equal to either operand, any leading
2477 // zero bits in either operand must also exist in the result.
2478 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2479 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2481 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2482 KnownZero2.countLeadingOnes());
2483 KnownOne.clearAllBits();
2484 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2487 case ISD::EXTRACT_ELEMENT: {
2488 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2489 const unsigned Index =
2490 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2491 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2493 // Remove low part of known bits mask
2494 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2495 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2497 // Remove high part of known bit mask
2498 KnownZero = KnownZero.trunc(BitWidth);
2499 KnownOne = KnownOne.trunc(BitWidth);
2506 APInt Op0Zero, Op0One;
2507 APInt Op1Zero, Op1One;
2508 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2509 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2511 KnownZero = Op0Zero & Op1Zero;
2512 KnownOne = Op0One & Op1One;
2515 case ISD::FrameIndex:
2516 case ISD::TargetFrameIndex:
2517 if (unsigned Align = InferPtrAlignment(Op)) {
2518 // The low bits are known zero if the pointer is aligned.
2519 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2525 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2528 case ISD::INTRINSIC_WO_CHAIN:
2529 case ISD::INTRINSIC_W_CHAIN:
2530 case ISD::INTRINSIC_VOID:
2531 // Allow the target to implement this method for its nodes.
2532 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2536 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2539 /// ComputeNumSignBits - Return the number of times the sign bit of the
2540 /// register is replicated into the other bits. We know that at least 1 bit
2541 /// is always equal to the sign bit (itself), but other cases can give us
2542 /// information. For example, immediately after an "SRA X, 2", we know that
2543 /// the top 3 bits are all equal to each other, so we return 3.
2544 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2545 EVT VT = Op.getValueType();
2546 assert(VT.isInteger() && "Invalid VT!");
2547 unsigned VTBits = VT.getScalarType().getSizeInBits();
2549 unsigned FirstAnswer = 1;
2552 return 1; // Limit search depth.
2554 switch (Op.getOpcode()) {
2556 case ISD::AssertSext:
2557 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2558 return VTBits-Tmp+1;
2559 case ISD::AssertZext:
2560 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2563 case ISD::Constant: {
2564 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2565 return Val.getNumSignBits();
2568 case ISD::SIGN_EXTEND:
2570 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2571 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2573 case ISD::SIGN_EXTEND_INREG:
2574 // Max of the input and what this extends.
2576 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2579 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2580 return std::max(Tmp, Tmp2);
2583 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2584 // SRA X, C -> adds C sign bits.
2585 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2586 Tmp += C->getZExtValue();
2587 if (Tmp > VTBits) Tmp = VTBits;
2591 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2592 // shl destroys sign bits.
2593 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2594 if (C->getZExtValue() >= VTBits || // Bad shift.
2595 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2596 return Tmp - C->getZExtValue();
2601 case ISD::XOR: // NOT is handled here.
2602 // Logical binary ops preserve the number of sign bits at the worst.
2603 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2605 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2606 FirstAnswer = std::min(Tmp, Tmp2);
2607 // We computed what we know about the sign bits as our first
2608 // answer. Now proceed to the generic code that uses
2609 // computeKnownBits, and pick whichever answer is better.
2614 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2615 if (Tmp == 1) return 1; // Early out.
2616 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2617 return std::min(Tmp, Tmp2);
2618 case ISD::SELECT_CC:
2619 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2620 if (Tmp == 1) return 1; // Early out.
2621 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2622 return std::min(Tmp, Tmp2);
2627 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2629 return 1; // Early out.
2630 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2631 return std::min(Tmp, Tmp2);
2638 if (Op.getResNo() != 1)
2640 // The boolean result conforms to getBooleanContents. Fall through.
2641 // If setcc returns 0/-1, all bits are sign bits.
2642 // We know that we have an integer-based boolean since these operations
2643 // are only available for integer.
2644 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2645 TargetLowering::ZeroOrNegativeOneBooleanContent)
2649 // If setcc returns 0/-1, all bits are sign bits.
2650 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2651 TargetLowering::ZeroOrNegativeOneBooleanContent)
2656 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2657 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2659 // Handle rotate right by N like a rotate left by 32-N.
2660 if (Op.getOpcode() == ISD::ROTR)
2661 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2663 // If we aren't rotating out all of the known-in sign bits, return the
2664 // number that are left. This handles rotl(sext(x), 1) for example.
2665 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2666 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2670 // Add can have at most one carry bit. Thus we know that the output
2671 // is, at worst, one more bit than the inputs.
2672 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2673 if (Tmp == 1) return 1; // Early out.
2675 // Special case decrementing a value (ADD X, -1):
2676 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2677 if (CRHS->isAllOnesValue()) {
2678 APInt KnownZero, KnownOne;
2679 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2681 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2683 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2686 // If we are subtracting one from a positive number, there is no carry
2687 // out of the result.
2688 if (KnownZero.isNegative())
2692 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2693 if (Tmp2 == 1) return 1;
2694 return std::min(Tmp, Tmp2)-1;
2697 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2698 if (Tmp2 == 1) return 1;
2701 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2702 if (CLHS->isNullValue()) {
2703 APInt KnownZero, KnownOne;
2704 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2705 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2707 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2710 // If the input is known to be positive (the sign bit is known clear),
2711 // the output of the NEG has the same number of sign bits as the input.
2712 if (KnownZero.isNegative())
2715 // Otherwise, we treat this like a SUB.
2718 // Sub can have at most one carry bit. Thus we know that the output
2719 // is, at worst, one more bit than the inputs.
2720 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2721 if (Tmp == 1) return 1; // Early out.
2722 return std::min(Tmp, Tmp2)-1;
2724 // FIXME: it's tricky to do anything useful for this, but it is an important
2725 // case for targets like X86.
2727 case ISD::EXTRACT_ELEMENT: {
2728 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2729 const int BitWidth = Op.getValueType().getSizeInBits();
2731 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2733 // Get reverse index (starting from 1), Op1 value indexes elements from
2734 // little end. Sign starts at big end.
2735 const int rIndex = Items - 1 -
2736 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2738 // If the sign portion ends in our element the subtraction gives correct
2739 // result. Otherwise it gives either negative or > bitwidth result
2740 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2744 // If we are looking at the loaded value of the SDNode.
2745 if (Op.getResNo() == 0) {
2746 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2747 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2748 unsigned ExtType = LD->getExtensionType();
2751 case ISD::SEXTLOAD: // '17' bits known
2752 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2753 return VTBits-Tmp+1;
2754 case ISD::ZEXTLOAD: // '16' bits known
2755 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2761 // Allow the target to implement this method for its nodes.
2762 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2763 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2764 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2765 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2766 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2767 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2770 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2771 // use this information.
2772 APInt KnownZero, KnownOne;
2773 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2776 if (KnownZero.isNegative()) { // sign bit is 0
2778 } else if (KnownOne.isNegative()) { // sign bit is 1;
2785 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2786 // the number of identical bits in the top of the input value.
2788 Mask <<= Mask.getBitWidth()-VTBits;
2789 // Return # leading zeros. We use 'min' here in case Val was zero before
2790 // shifting. We don't want to return '64' as for an i32 "0".
2791 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2794 /// isBaseWithConstantOffset - Return true if the specified operand is an
2795 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2796 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2797 /// semantics as an ADD. This handles the equivalence:
2798 /// X|Cst == X+Cst iff X&Cst = 0.
2799 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2800 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2801 !isa<ConstantSDNode>(Op.getOperand(1)))
2804 if (Op.getOpcode() == ISD::OR &&
2805 !MaskedValueIsZero(Op.getOperand(0),
2806 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2813 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2814 // If we're told that NaNs won't happen, assume they won't.
2815 if (getTarget().Options.NoNaNsFPMath)
2818 // If the value is a constant, we can obviously see if it is a NaN or not.
2819 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2820 return !C->getValueAPF().isNaN();
2822 // TODO: Recognize more cases here.
2827 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2828 // If the value is a constant, we can obviously see if it is a zero or not.
2829 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2830 return !C->isZero();
2832 // TODO: Recognize more cases here.
2833 switch (Op.getOpcode()) {
2836 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2837 return !C->isNullValue();
2844 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2845 // Check the obvious case.
2846 if (A == B) return true;
2848 // For for negative and positive zero.
2849 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2850 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2851 if (CA->isZero() && CB->isZero()) return true;
2853 // Otherwise they may not be equal.
2857 /// getNode - Gets or creates the specified node.
2859 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2860 FoldingSetNodeID ID;
2861 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2863 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2864 return SDValue(E, 0);
2866 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2867 DL.getDebugLoc(), getVTList(VT));
2868 CSEMap.InsertNode(N, IP);
2871 return SDValue(N, 0);
2874 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2875 EVT VT, SDValue Operand) {
2876 // Constant fold unary operations with an integer constant operand. Even
2877 // opaque constant will be folded, because the folding of unary operations
2878 // doesn't create new constants with different values. Nevertheless, the
2879 // opaque flag is preserved during folding to prevent future folding with
2881 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2882 const APInt &Val = C->getAPIntValue();
2885 case ISD::SIGN_EXTEND:
2886 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2887 C->isTargetOpcode(), C->isOpaque());
2888 case ISD::ANY_EXTEND:
2889 case ISD::ZERO_EXTEND:
2891 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2892 C->isTargetOpcode(), C->isOpaque());
2893 case ISD::UINT_TO_FP:
2894 case ISD::SINT_TO_FP: {
2895 APFloat apf(EVTToAPFloatSemantics(VT),
2896 APInt::getNullValue(VT.getSizeInBits()));
2897 (void)apf.convertFromAPInt(Val,
2898 Opcode==ISD::SINT_TO_FP,
2899 APFloat::rmNearestTiesToEven);
2900 return getConstantFP(apf, DL, VT);
2903 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2904 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2905 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2906 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2907 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2908 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2911 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2914 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2917 case ISD::CTLZ_ZERO_UNDEF:
2918 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2921 case ISD::CTTZ_ZERO_UNDEF:
2922 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2927 // Constant fold unary operations with a floating point constant operand.
2928 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2929 APFloat V = C->getValueAPF(); // make copy
2933 return getConstantFP(V, DL, VT);
2936 return getConstantFP(V, DL, VT);
2938 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2939 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2940 return getConstantFP(V, DL, VT);
2944 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2945 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2946 return getConstantFP(V, DL, VT);
2950 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2951 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2952 return getConstantFP(V, DL, VT);
2955 case ISD::FP_EXTEND: {
2957 // This can return overflow, underflow, or inexact; we don't care.
2958 // FIXME need to be more flexible about rounding mode.
2959 (void)V.convert(EVTToAPFloatSemantics(VT),
2960 APFloat::rmNearestTiesToEven, &ignored);
2961 return getConstantFP(V, DL, VT);
2963 case ISD::FP_TO_SINT:
2964 case ISD::FP_TO_UINT: {
2967 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2968 // FIXME need to be more flexible about rounding mode.
2969 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2970 Opcode==ISD::FP_TO_SINT,
2971 APFloat::rmTowardZero, &ignored);
2972 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2974 APInt api(VT.getSizeInBits(), x);
2975 return getConstant(api, DL, VT);
2978 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2979 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2980 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2981 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2982 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2983 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2988 // Constant fold unary operations with a vector integer or float operand.
2989 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2990 if (BV->isConstant()) {
2993 // FIXME: Entirely reasonable to perform folding of other unary
2994 // operations here as the need arises.
3001 case ISD::FP_EXTEND:
3002 case ISD::FP_TO_SINT:
3003 case ISD::FP_TO_UINT:
3005 case ISD::UINT_TO_FP:
3006 case ISD::SINT_TO_FP:
3009 case ISD::CTLZ_ZERO_UNDEF:
3011 case ISD::CTTZ_ZERO_UNDEF:
3013 SDValue Ops = { Operand };
3014 if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
3021 unsigned OpOpcode = Operand.getNode()->getOpcode();
3023 case ISD::TokenFactor:
3024 case ISD::MERGE_VALUES:
3025 case ISD::CONCAT_VECTORS:
3026 return Operand; // Factor, merge or concat of one node? No need.
3027 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3028 case ISD::FP_EXTEND:
3029 assert(VT.isFloatingPoint() &&
3030 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3031 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3032 assert((!VT.isVector() ||
3033 VT.getVectorNumElements() ==
3034 Operand.getValueType().getVectorNumElements()) &&
3035 "Vector element count mismatch!");
3036 assert(Operand.getValueType().bitsLT(VT) &&
3037 "Invalid fpext node, dst < src!");
3038 if (Operand.getOpcode() == ISD::UNDEF)
3039 return getUNDEF(VT);
3041 case ISD::SIGN_EXTEND:
3042 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3043 "Invalid SIGN_EXTEND!");
3044 if (Operand.getValueType() == VT) return Operand; // noop extension
3045 assert((!VT.isVector() ||
3046 VT.getVectorNumElements() ==
3047 Operand.getValueType().getVectorNumElements()) &&
3048 "Vector element count mismatch!");
3049 assert(Operand.getValueType().bitsLT(VT) &&
3050 "Invalid sext node, dst < src!");
3051 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3052 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3053 else if (OpOpcode == ISD::UNDEF)
3054 // sext(undef) = 0, because the top bits will all be the same.
3055 return getConstant(0, DL, VT);
3057 case ISD::ZERO_EXTEND:
3058 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3059 "Invalid ZERO_EXTEND!");
3060 if (Operand.getValueType() == VT) return Operand; // noop extension
3061 assert((!VT.isVector() ||
3062 VT.getVectorNumElements() ==
3063 Operand.getValueType().getVectorNumElements()) &&
3064 "Vector element count mismatch!");
3065 assert(Operand.getValueType().bitsLT(VT) &&
3066 "Invalid zext node, dst < src!");
3067 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3068 return getNode(ISD::ZERO_EXTEND, DL, VT,
3069 Operand.getNode()->getOperand(0));
3070 else if (OpOpcode == ISD::UNDEF)
3071 // zext(undef) = 0, because the top bits will be zero.
3072 return getConstant(0, DL, VT);
3074 case ISD::ANY_EXTEND:
3075 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3076 "Invalid ANY_EXTEND!");
3077 if (Operand.getValueType() == VT) return Operand; // noop extension
3078 assert((!VT.isVector() ||
3079 VT.getVectorNumElements() ==
3080 Operand.getValueType().getVectorNumElements()) &&
3081 "Vector element count mismatch!");
3082 assert(Operand.getValueType().bitsLT(VT) &&
3083 "Invalid anyext node, dst < src!");
3085 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3086 OpOpcode == ISD::ANY_EXTEND)
3087 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3088 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3089 else if (OpOpcode == ISD::UNDEF)
3090 return getUNDEF(VT);
3092 // (ext (trunx x)) -> x
3093 if (OpOpcode == ISD::TRUNCATE) {
3094 SDValue OpOp = Operand.getNode()->getOperand(0);
3095 if (OpOp.getValueType() == VT)
3100 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3101 "Invalid TRUNCATE!");
3102 if (Operand.getValueType() == VT) return Operand; // noop truncate
3103 assert((!VT.isVector() ||
3104 VT.getVectorNumElements() ==
3105 Operand.getValueType().getVectorNumElements()) &&
3106 "Vector element count mismatch!");
3107 assert(Operand.getValueType().bitsGT(VT) &&
3108 "Invalid truncate node, src < dst!");
3109 if (OpOpcode == ISD::TRUNCATE)
3110 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3111 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3112 OpOpcode == ISD::ANY_EXTEND) {
3113 // If the source is smaller than the dest, we still need an extend.
3114 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3115 .bitsLT(VT.getScalarType()))
3116 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3117 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3118 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3119 return Operand.getNode()->getOperand(0);
3121 if (OpOpcode == ISD::UNDEF)
3122 return getUNDEF(VT);
3125 assert(VT.isInteger() && VT == Operand.getValueType() &&
3127 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3128 "BSWAP types must be a multiple of 16 bits!");
3129 if (OpOpcode == ISD::UNDEF)
3130 return getUNDEF(VT);
3133 // Basic sanity checking.
3134 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3135 && "Cannot BITCAST between types of different sizes!");
3136 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3137 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3138 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3139 if (OpOpcode == ISD::UNDEF)
3140 return getUNDEF(VT);
3142 case ISD::SCALAR_TO_VECTOR:
3143 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3144 (VT.getVectorElementType() == Operand.getValueType() ||
3145 (VT.getVectorElementType().isInteger() &&
3146 Operand.getValueType().isInteger() &&
3147 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3148 "Illegal SCALAR_TO_VECTOR node!");
3149 if (OpOpcode == ISD::UNDEF)
3150 return getUNDEF(VT);
3151 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3152 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3153 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3154 Operand.getConstantOperandVal(1) == 0 &&
3155 Operand.getOperand(0).getValueType() == VT)
3156 return Operand.getOperand(0);
3159 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3160 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3161 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3162 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3163 Operand.getNode()->getOperand(0),
3164 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3165 if (OpOpcode == ISD::FNEG) // --X -> X
3166 return Operand.getNode()->getOperand(0);
3169 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3170 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3175 SDVTList VTs = getVTList(VT);
3176 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3177 FoldingSetNodeID ID;
3178 SDValue Ops[1] = { Operand };
3179 AddNodeIDNode(ID, Opcode, VTs, Ops);
3181 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3182 return SDValue(E, 0);
3184 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3185 DL.getDebugLoc(), VTs, Operand);
3186 CSEMap.InsertNode(N, IP);
3188 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3189 DL.getDebugLoc(), VTs, Operand);
3193 return SDValue(N, 0);
3196 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3199 case ISD::ADD: return std::make_pair(C1 + C2, true);
3200 case ISD::SUB: return std::make_pair(C1 - C2, true);
3201 case ISD::MUL: return std::make_pair(C1 * C2, true);
3202 case ISD::AND: return std::make_pair(C1 & C2, true);
3203 case ISD::OR: return std::make_pair(C1 | C2, true);
3204 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3205 case ISD::SHL: return std::make_pair(C1 << C2, true);
3206 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3207 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3208 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3209 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3210 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3211 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3212 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3213 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3215 if (!C2.getBoolValue())
3217 return std::make_pair(C1.udiv(C2), true);
3219 if (!C2.getBoolValue())
3221 return std::make_pair(C1.urem(C2), true);
3223 if (!C2.getBoolValue())
3225 return std::make_pair(C1.sdiv(C2), true);
3227 if (!C2.getBoolValue())
3229 return std::make_pair(C1.srem(C2), true);
3231 return std::make_pair(APInt(1, 0), false);
3234 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3235 const ConstantSDNode *Cst1,
3236 const ConstantSDNode *Cst2) {
3237 if (Cst1->isOpaque() || Cst2->isOpaque())
3240 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3241 Cst2->getAPIntValue());
3244 return getConstant(Folded.first, DL, VT);
3247 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3248 SDNode *Cst1, SDNode *Cst2) {
3249 // If the opcode is a target-specific ISD node, there's nothing we can
3250 // do here and the operand rules may not line up with the below, so
3252 if (Opcode >= ISD::BUILTIN_OP_END)
3255 // Handle the case of two scalars.
3256 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3257 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3258 if (SDValue Folded =
3259 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3262 SmallVector<SDValue, 4> Outputs;
3263 // We may have a vector type but a scalar result. Create a splat.
3264 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3265 // Build a big vector out of the scalar elements we generated.
3266 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3273 // For vectors extract each constant element into Inputs so we can constant
3274 // fold them individually.
3275 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3276 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3280 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3282 EVT SVT = VT.getScalarType();
3283 SmallVector<SDValue, 4> Outputs;
3284 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3285 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3286 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3287 if (!V1 || !V2) // Not a constant, bail.
3290 if (V1->isOpaque() || V2->isOpaque())
3293 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3294 // FIXME: This is valid and could be handled by truncating the APInts.
3295 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3298 // Fold one vector element.
3299 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3300 V2->getAPIntValue());
3303 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3306 assert(VT.getVectorNumElements() == Outputs.size() &&
3307 "Vector size mismatch!");
3309 // We may have a vector type but a scalar result. Create a splat.
3310 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3312 // Build a big vector out of the scalar elements we generated.
3313 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3316 SDValue SelectionDAG::FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
3318 ArrayRef<SDValue> Ops,
3319 const SDNodeFlags *Flags) {
3320 // If the opcode is a target-specific ISD node, there's nothing we can
3321 // do here and the operand rules may not line up with the below, so
3323 if (Opcode >= ISD::BUILTIN_OP_END)
3326 // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
3330 unsigned NumElts = VT.getVectorNumElements();
3332 auto IsSameVectorSize = [&](const SDValue &Op) {
3333 return Op.getValueType().isVector() &&
3334 Op.getValueType().getVectorNumElements() == NumElts;
3337 auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
3338 BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Op);
3339 return (Op.getOpcode() == ISD::UNDEF) || (BV && BV->isConstant());
3342 // All operands must be vector types with the same number of elements as
3343 // the result type and must be either UNDEF or a build vector of constant
3344 // or UNDEF scalars.
3345 if (!std::all_of(Ops.begin(), Ops.end(), IsConstantBuildVectorOrUndef) ||
3346 !std::all_of(Ops.begin(), Ops.end(), IsSameVectorSize))
3349 // Find legal integer scalar type for constant promotion and
3350 // ensure that its scalar size is at least as large as source.
3351 EVT SVT = VT.getScalarType();
3353 if (SVT.isInteger()) {
3354 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3355 if (LegalSVT.bitsLT(SVT))
3359 // Constant fold each scalar lane separately.
3360 SmallVector<SDValue, 4> ScalarResults;
3361 for (unsigned i = 0; i != NumElts; i++) {
3362 SmallVector<SDValue, 4> ScalarOps;
3363 for (SDValue Op : Ops) {
3364 EVT InSVT = Op->getValueType(0).getScalarType();
3365 BuildVectorSDNode *InBV = dyn_cast<BuildVectorSDNode>(Op);
3367 // We've checked that this is UNDEF above.
3368 ScalarOps.push_back(getUNDEF(LegalSVT));
3372 SDValue ScalarOp = InBV->getOperand(i);
3373 EVT ScalarVT = ScalarOp.getValueType();
3375 // Build vector (integer) scalar operands may need implicit
3376 // truncation - do this before constant folding.
3377 if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
3378 ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
3380 ScalarOps.push_back(ScalarOp);
3383 // Constant fold the scalar operands.
3384 SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
3386 // Legalize the (integer) scalar constant if necessary.
3387 if (LegalSVT != SVT)
3388 ScalarResult = getNode(ISD::ANY_EXTEND, DL, LegalSVT, ScalarResult);
3390 // Scalar folding only succeeded if the result is a constant or UNDEF.
3391 if (ScalarResult.getOpcode() != ISD::UNDEF &&
3392 ScalarResult.getOpcode() != ISD::Constant &&
3393 ScalarResult.getOpcode() != ISD::ConstantFP)
3395 ScalarResults.push_back(ScalarResult);
3398 assert(ScalarResults.size() == NumElts &&
3399 "Unexpected number of scalar results for BUILD_VECTOR");
3400 return getNode(ISD::BUILD_VECTOR, DL, VT, ScalarResults);
3403 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3404 SDValue N2, const SDNodeFlags *Flags) {
3405 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3406 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3408 // Canonicalize constant to RHS if commutative.
3409 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3410 std::swap(N1C, N2C);
3416 case ISD::TokenFactor:
3417 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3418 N2.getValueType() == MVT::Other && "Invalid token factor!");
3419 // Fold trivial token factors.
3420 if (N1.getOpcode() == ISD::EntryToken) return N2;
3421 if (N2.getOpcode() == ISD::EntryToken) return N1;
3422 if (N1 == N2) return N1;
3424 case ISD::CONCAT_VECTORS:
3425 // Concat of UNDEFs is UNDEF.
3426 if (N1.getOpcode() == ISD::UNDEF &&
3427 N2.getOpcode() == ISD::UNDEF)
3428 return getUNDEF(VT);
3430 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3431 // one big BUILD_VECTOR.
3432 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3433 N2.getOpcode() == ISD::BUILD_VECTOR) {
3434 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3435 N1.getNode()->op_end());
3436 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3438 // BUILD_VECTOR requires all inputs to be of the same type, find the
3439 // maximum type and extend them all.
3440 EVT SVT = VT.getScalarType();
3441 for (SDValue Op : Elts)
3442 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3443 if (SVT.bitsGT(VT.getScalarType()))
3444 for (SDValue &Op : Elts)
3445 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3446 ? getZExtOrTrunc(Op, DL, SVT)
3447 : getSExtOrTrunc(Op, DL, SVT);
3449 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3453 assert(VT.isInteger() && "This operator does not apply to FP types!");
3454 assert(N1.getValueType() == N2.getValueType() &&
3455 N1.getValueType() == VT && "Binary operator types must match!");
3456 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3457 // worth handling here.
3458 if (N2C && N2C->isNullValue())
3460 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3467 assert(VT.isInteger() && "This operator does not apply to FP types!");
3468 assert(N1.getValueType() == N2.getValueType() &&
3469 N1.getValueType() == VT && "Binary operator types must match!");
3470 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3471 // it's worth handling here.
3472 if (N2C && N2C->isNullValue())
3486 assert(VT.isInteger() && "This operator does not apply to FP types!");
3487 assert(N1.getValueType() == N2.getValueType() &&
3488 N1.getValueType() == VT && "Binary operator types must match!");
3495 if (getTarget().Options.UnsafeFPMath) {
3496 if (Opcode == ISD::FADD) {
3498 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3499 if (CFP->getValueAPF().isZero())
3502 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3503 if (CFP->getValueAPF().isZero())
3505 } else if (Opcode == ISD::FSUB) {
3507 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3508 if (CFP->getValueAPF().isZero())
3510 } else if (Opcode == ISD::FMUL) {
3511 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3514 // If the first operand isn't the constant, try the second
3516 CFP = dyn_cast<ConstantFPSDNode>(N2);
3523 return SDValue(CFP,0);
3525 if (CFP->isExactlyValue(1.0))
3530 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3531 assert(N1.getValueType() == N2.getValueType() &&
3532 N1.getValueType() == VT && "Binary operator types must match!");
3534 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3535 assert(N1.getValueType() == VT &&
3536 N1.getValueType().isFloatingPoint() &&
3537 N2.getValueType().isFloatingPoint() &&
3538 "Invalid FCOPYSIGN!");
3545 assert(VT == N1.getValueType() &&
3546 "Shift operators return type must be the same as their first arg");
3547 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3548 "Shifts only work on integers");
3549 assert((!VT.isVector() || VT == N2.getValueType()) &&
3550 "Vector shift amounts must be in the same as their first arg");
3551 // Verify that the shift amount VT is bit enough to hold valid shift
3552 // amounts. This catches things like trying to shift an i1024 value by an
3553 // i8, which is easy to fall into in generic code that uses
3554 // TLI.getShiftAmount().
3555 assert(N2.getValueType().getSizeInBits() >=
3556 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3557 "Invalid use of small shift amount with oversized value!");
3559 // Always fold shifts of i1 values so the code generator doesn't need to
3560 // handle them. Since we know the size of the shift has to be less than the
3561 // size of the value, the shift/rotate count is guaranteed to be zero.
3564 if (N2C && N2C->isNullValue())
3567 case ISD::FP_ROUND_INREG: {
3568 EVT EVT = cast<VTSDNode>(N2)->getVT();
3569 assert(VT == N1.getValueType() && "Not an inreg round!");
3570 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3571 "Cannot FP_ROUND_INREG integer types");
3572 assert(EVT.isVector() == VT.isVector() &&
3573 "FP_ROUND_INREG type should be vector iff the operand "
3575 assert((!EVT.isVector() ||
3576 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3577 "Vector element counts must match in FP_ROUND_INREG");
3578 assert(EVT.bitsLE(VT) && "Not rounding down!");
3580 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3584 assert(VT.isFloatingPoint() &&
3585 N1.getValueType().isFloatingPoint() &&
3586 VT.bitsLE(N1.getValueType()) &&
3587 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3588 if (N1.getValueType() == VT) return N1; // noop conversion.
3590 case ISD::AssertSext:
3591 case ISD::AssertZext: {
3592 EVT EVT = cast<VTSDNode>(N2)->getVT();
3593 assert(VT == N1.getValueType() && "Not an inreg extend!");
3594 assert(VT.isInteger() && EVT.isInteger() &&
3595 "Cannot *_EXTEND_INREG FP types");
3596 assert(!EVT.isVector() &&
3597 "AssertSExt/AssertZExt type should be the vector element type "
3598 "rather than the vector type!");
3599 assert(EVT.bitsLE(VT) && "Not extending!");
3600 if (VT == EVT) return N1; // noop assertion.
3603 case ISD::SIGN_EXTEND_INREG: {
3604 EVT EVT = cast<VTSDNode>(N2)->getVT();
3605 assert(VT == N1.getValueType() && "Not an inreg extend!");
3606 assert(VT.isInteger() && EVT.isInteger() &&
3607 "Cannot *_EXTEND_INREG FP types");
3608 assert(EVT.isVector() == VT.isVector() &&
3609 "SIGN_EXTEND_INREG type should be vector iff the operand "
3611 assert((!EVT.isVector() ||
3612 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3613 "Vector element counts must match in SIGN_EXTEND_INREG");
3614 assert(EVT.bitsLE(VT) && "Not extending!");
3615 if (EVT == VT) return N1; // Not actually extending
3617 auto SignExtendInReg = [&](APInt Val) {
3618 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3619 Val <<= Val.getBitWidth() - FromBits;
3620 Val = Val.ashr(Val.getBitWidth() - FromBits);
3621 return getConstant(Val, DL, VT.getScalarType());
3625 APInt Val = N1C->getAPIntValue();
3626 return SignExtendInReg(Val);
3628 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3629 SmallVector<SDValue, 8> Ops;
3630 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3631 SDValue Op = N1.getOperand(i);
3632 if (Op.getOpcode() == ISD::UNDEF) {
3633 Ops.push_back(getUNDEF(VT.getScalarType()));
3636 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3637 APInt Val = C->getAPIntValue();
3638 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3639 Ops.push_back(SignExtendInReg(Val));
3644 if (Ops.size() == VT.getVectorNumElements())
3645 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3649 case ISD::EXTRACT_VECTOR_ELT:
3650 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3651 if (N1.getOpcode() == ISD::UNDEF)
3652 return getUNDEF(VT);
3654 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3655 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3656 return getUNDEF(VT);
3658 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3659 // expanding copies of large vectors from registers.
3661 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3662 N1.getNumOperands() > 0) {
3664 N1.getOperand(0).getValueType().getVectorNumElements();
3665 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3666 N1.getOperand(N2C->getZExtValue() / Factor),
3667 getConstant(N2C->getZExtValue() % Factor, DL,
3668 N2.getValueType()));
3671 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3672 // expanding large vector constants.
3673 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3674 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3676 if (VT != Elt.getValueType())
3677 // If the vector element type is not legal, the BUILD_VECTOR operands
3678 // are promoted and implicitly truncated, and the result implicitly
3679 // extended. Make that explicit here.
3680 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3685 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3686 // operations are lowered to scalars.
3687 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3688 // If the indices are the same, return the inserted element else
3689 // if the indices are known different, extract the element from
3690 // the original vector.
3691 SDValue N1Op2 = N1.getOperand(2);
3692 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3694 if (N1Op2C && N2C) {
3695 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3696 if (VT == N1.getOperand(1).getValueType())
3697 return N1.getOperand(1);
3699 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3702 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3706 case ISD::EXTRACT_ELEMENT:
3707 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3708 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3709 (N1.getValueType().isInteger() == VT.isInteger()) &&
3710 N1.getValueType() != VT &&
3711 "Wrong types for EXTRACT_ELEMENT!");
3713 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3714 // 64-bit integers into 32-bit parts. Instead of building the extract of
3715 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3716 if (N1.getOpcode() == ISD::BUILD_PAIR)
3717 return N1.getOperand(N2C->getZExtValue());
3719 // EXTRACT_ELEMENT of a constant int is also very common.
3720 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3721 unsigned ElementSize = VT.getSizeInBits();
3722 unsigned Shift = ElementSize * N2C->getZExtValue();
3723 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3724 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3727 case ISD::EXTRACT_SUBVECTOR: {
3729 if (VT.isSimple() && N1.getValueType().isSimple()) {
3730 assert(VT.isVector() && N1.getValueType().isVector() &&
3731 "Extract subvector VTs must be a vectors!");
3732 assert(VT.getVectorElementType() ==
3733 N1.getValueType().getVectorElementType() &&
3734 "Extract subvector VTs must have the same element type!");
3735 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3736 "Extract subvector must be from larger vector to smaller vector!");
3738 if (isa<ConstantSDNode>(Index)) {
3739 assert((VT.getVectorNumElements() +
3740 cast<ConstantSDNode>(Index)->getZExtValue()
3741 <= N1.getValueType().getVectorNumElements())
3742 && "Extract subvector overflow!");
3745 // Trivial extraction.
3746 if (VT.getSimpleVT() == N1.getSimpleValueType())
3753 // Perform trivial constant folding.
3755 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3758 // Constant fold FP operations.
3759 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3760 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3761 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3763 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3764 // Canonicalize constant to RHS if commutative.
3765 std::swap(N1CFP, N2CFP);
3768 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3769 APFloat::opStatus s;
3772 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3773 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3774 return getConstantFP(V1, DL, VT);
3777 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3778 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3779 return getConstantFP(V1, DL, VT);
3782 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3783 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3784 return getConstantFP(V1, DL, VT);
3787 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3788 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3789 s!=APFloat::opDivByZero)) {
3790 return getConstantFP(V1, DL, VT);
3795 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3796 s!=APFloat::opDivByZero)) {
3797 return getConstantFP(V1, DL, VT);
3800 case ISD::FCOPYSIGN:
3802 return getConstantFP(V1, DL, VT);
3807 if (Opcode == ISD::FP_ROUND) {
3808 APFloat V = N1CFP->getValueAPF(); // make copy
3810 // This can return overflow, underflow, or inexact; we don't care.
3811 // FIXME need to be more flexible about rounding mode.
3812 (void)V.convert(EVTToAPFloatSemantics(VT),
3813 APFloat::rmNearestTiesToEven, &ignored);
3814 return getConstantFP(V, DL, VT);
3818 // Canonicalize an UNDEF to the RHS, even over a constant.
3819 if (N1.getOpcode() == ISD::UNDEF) {
3820 if (isCommutativeBinOp(Opcode)) {
3824 case ISD::FP_ROUND_INREG:
3825 case ISD::SIGN_EXTEND_INREG:
3831 return N1; // fold op(undef, arg2) -> undef
3839 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3840 // For vectors, we can't easily build an all zero vector, just return
3847 // Fold a bunch of operators when the RHS is undef.
3848 if (N2.getOpcode() == ISD::UNDEF) {
3851 if (N1.getOpcode() == ISD::UNDEF)
3852 // Handle undef ^ undef -> 0 special case. This is a common
3854 return getConstant(0, DL, VT);
3864 return N2; // fold op(arg1, undef) -> undef
3870 if (getTarget().Options.UnsafeFPMath)
3878 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3879 // For vectors, we can't easily build an all zero vector, just return
3884 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3885 // For vectors, we can't easily build an all one vector, just return
3893 // Memoize this node if possible.
3895 SDVTList VTs = getVTList(VT);
3896 if (VT != MVT::Glue) {
3897 SDValue Ops[] = {N1, N2};
3898 FoldingSetNodeID ID;
3899 AddNodeIDNode(ID, Opcode, VTs, Ops);
3900 AddNodeIDFlags(ID, Opcode, Flags);
3902 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3903 return SDValue(E, 0);
3905 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3907 CSEMap.InsertNode(N, IP);
3909 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3913 return SDValue(N, 0);
3916 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3917 SDValue N1, SDValue N2, SDValue N3) {
3918 // Perform various simplifications.
3919 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3922 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3923 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3924 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3925 if (N1CFP && N2CFP && N3CFP) {
3926 APFloat V1 = N1CFP->getValueAPF();
3927 const APFloat &V2 = N2CFP->getValueAPF();
3928 const APFloat &V3 = N3CFP->getValueAPF();
3929 APFloat::opStatus s =
3930 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3931 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3932 return getConstantFP(V1, DL, VT);
3936 case ISD::CONCAT_VECTORS:
3937 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3938 // one big BUILD_VECTOR.
3939 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3940 N2.getOpcode() == ISD::BUILD_VECTOR &&
3941 N3.getOpcode() == ISD::BUILD_VECTOR) {
3942 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3943 N1.getNode()->op_end());
3944 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3945 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3946 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3950 // Use FoldSetCC to simplify SETCC's.
3951 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3952 if (Simp.getNode()) return Simp;
3957 if (N1C->getZExtValue())
3958 return N2; // select true, X, Y -> X
3959 return N3; // select false, X, Y -> Y
3962 if (N2 == N3) return N2; // select C, X, X -> X
3964 case ISD::VECTOR_SHUFFLE:
3965 llvm_unreachable("should use getVectorShuffle constructor!");
3966 case ISD::INSERT_SUBVECTOR: {
3968 if (VT.isSimple() && N1.getValueType().isSimple()
3969 && N2.getValueType().isSimple()) {
3970 assert(VT.isVector() && N1.getValueType().isVector() &&
3971 N2.getValueType().isVector() &&
3972 "Insert subvector VTs must be a vectors");
3973 assert(VT == N1.getValueType() &&
3974 "Dest and insert subvector source types must match!");
3975 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3976 "Insert subvector must be from smaller vector to larger vector!");
3977 if (isa<ConstantSDNode>(Index)) {
3978 assert((N2.getValueType().getVectorNumElements() +
3979 cast<ConstantSDNode>(Index)->getZExtValue()
3980 <= VT.getVectorNumElements())
3981 && "Insert subvector overflow!");
3984 // Trivial insertion.
3985 if (VT.getSimpleVT() == N2.getSimpleValueType())
3991 // Fold bit_convert nodes from a type to themselves.
3992 if (N1.getValueType() == VT)
3997 // Memoize node if it doesn't produce a flag.
3999 SDVTList VTs = getVTList(VT);
4000 if (VT != MVT::Glue) {
4001 SDValue Ops[] = { N1, N2, N3 };
4002 FoldingSetNodeID ID;
4003 AddNodeIDNode(ID, Opcode, VTs, Ops);
4005 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
4006 return SDValue(E, 0);
4008 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4009 DL.getDebugLoc(), VTs, N1, N2, N3);
4010 CSEMap.InsertNode(N, IP);
4012 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4013 DL.getDebugLoc(), VTs, N1, N2, N3);
4017 return SDValue(N, 0);
4020 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4021 SDValue N1, SDValue N2, SDValue N3,
4023 SDValue Ops[] = { N1, N2, N3, N4 };
4024 return getNode(Opcode, DL, VT, Ops);
4027 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4028 SDValue N1, SDValue N2, SDValue N3,
4029 SDValue N4, SDValue N5) {
4030 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4031 return getNode(Opcode, DL, VT, Ops);
4034 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
4035 /// the incoming stack arguments to be loaded from the stack.
4036 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
4037 SmallVector<SDValue, 8> ArgChains;
4039 // Include the original chain at the beginning of the list. When this is
4040 // used by target LowerCall hooks, this helps legalize find the
4041 // CALLSEQ_BEGIN node.
4042 ArgChains.push_back(Chain);
4044 // Add a chain value for each stack argument.
4045 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
4046 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
4047 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
4048 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
4049 if (FI->getIndex() < 0)
4050 ArgChains.push_back(SDValue(L, 1));
4052 // Build a tokenfactor for all the chains.
4053 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4056 /// getMemsetValue - Vectorized representation of the memset value
4058 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4060 assert(Value.getOpcode() != ISD::UNDEF);
4062 unsigned NumBits = VT.getScalarType().getSizeInBits();
4063 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4064 assert(C->getAPIntValue().getBitWidth() == 8);
4065 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4067 return DAG.getConstant(Val, dl, VT);
4068 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4072 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4073 EVT IntVT = VT.getScalarType();
4074 if (!IntVT.isInteger())
4075 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4077 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4079 // Use a multiplication with 0x010101... to extend the input to the
4081 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4082 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4083 DAG.getConstant(Magic, dl, IntVT));
4086 if (VT != Value.getValueType() && !VT.isInteger())
4087 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4088 if (VT != Value.getValueType()) {
4089 assert(VT.getVectorElementType() == Value.getValueType() &&
4090 "value type should be one vector element here");
4091 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4092 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4098 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4099 /// used when a memcpy is turned into a memset when the source is a constant
4101 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4102 const TargetLowering &TLI, StringRef Str) {
4103 // Handle vector with all elements zero.
4106 return DAG.getConstant(0, dl, VT);
4107 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4108 return DAG.getConstantFP(0.0, dl, VT);
4109 else if (VT.isVector()) {
4110 unsigned NumElts = VT.getVectorNumElements();
4111 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4112 return DAG.getNode(ISD::BITCAST, dl, VT,
4113 DAG.getConstant(0, dl,
4114 EVT::getVectorVT(*DAG.getContext(),
4117 llvm_unreachable("Expected type!");
4120 assert(!VT.isVector() && "Can't handle vector type here!");
4121 unsigned NumVTBits = VT.getSizeInBits();
4122 unsigned NumVTBytes = NumVTBits / 8;
4123 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4125 APInt Val(NumVTBits, 0);
4126 if (DAG.getDataLayout().isLittleEndian()) {
4127 for (unsigned i = 0; i != NumBytes; ++i)
4128 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4130 for (unsigned i = 0; i != NumBytes; ++i)
4131 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4134 // If the "cost" of materializing the integer immediate is less than the cost
4135 // of a load, then it is cost effective to turn the load into the immediate.
4136 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4137 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4138 return DAG.getConstant(Val, dl, VT);
4139 return SDValue(nullptr, 0);
4142 /// getMemBasePlusOffset - Returns base and offset node for the
4144 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4145 SelectionDAG &DAG) {
4146 EVT VT = Base.getValueType();
4147 return DAG.getNode(ISD::ADD, dl,
4148 VT, Base, DAG.getConstant(Offset, dl, VT));
4151 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4153 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4154 unsigned SrcDelta = 0;
4155 GlobalAddressSDNode *G = nullptr;
4156 if (Src.getOpcode() == ISD::GlobalAddress)
4157 G = cast<GlobalAddressSDNode>(Src);
4158 else if (Src.getOpcode() == ISD::ADD &&
4159 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4160 Src.getOperand(1).getOpcode() == ISD::Constant) {
4161 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4162 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4167 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4170 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4171 /// Return true if the number of memory ops is below the threshold (Limit).
4172 /// It returns the types of the sequence of memory ops to perform
4173 /// memset / memcpy by reference.
4174 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4175 unsigned Limit, uint64_t Size,
4176 unsigned DstAlign, unsigned SrcAlign,
4182 const TargetLowering &TLI) {
4183 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4184 "Expecting memcpy / memset source to meet alignment requirement!");
4185 // If 'SrcAlign' is zero, that means the memory operation does not need to
4186 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4187 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4188 // is the specified alignment of the memory operation. If it is zero, that
4189 // means it's possible to change the alignment of the destination.
4190 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4191 // not need to be loaded.
4192 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4193 IsMemset, ZeroMemset, MemcpyStrSrc,
4194 DAG.getMachineFunction());
4196 if (VT == MVT::Other) {
4198 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4199 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4200 VT = TLI.getPointerTy(DAG.getDataLayout());
4202 switch (DstAlign & 7) {
4203 case 0: VT = MVT::i64; break;
4204 case 4: VT = MVT::i32; break;
4205 case 2: VT = MVT::i16; break;
4206 default: VT = MVT::i8; break;
4211 while (!TLI.isTypeLegal(LVT))
4212 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4213 assert(LVT.isInteger());
4219 unsigned NumMemOps = 0;
4221 unsigned VTSize = VT.getSizeInBits() / 8;
4222 while (VTSize > Size) {
4223 // For now, only use non-vector load / store's for the left-over pieces.
4228 if (VT.isVector() || VT.isFloatingPoint()) {
4229 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4230 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4231 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4233 else if (NewVT == MVT::i64 &&
4234 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4235 TLI.isSafeMemOpType(MVT::f64)) {
4236 // i64 is usually not legal on 32-bit targets, but f64 may be.
4244 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4245 if (NewVT == MVT::i8)
4247 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4249 NewVTSize = NewVT.getSizeInBits() / 8;
4251 // If the new VT cannot cover all of the remaining bits, then consider
4252 // issuing a (or a pair of) unaligned and overlapping load / store.
4253 // FIXME: Only does this for 64-bit or more since we don't have proper
4254 // cost model for unaligned load / store.
4257 if (NumMemOps && AllowOverlap &&
4258 VTSize >= 8 && NewVTSize < Size &&
4259 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4267 if (++NumMemOps > Limit)
4270 MemOps.push_back(VT);
4277 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4278 // On Darwin, -Os means optimize for size without hurting performance, so
4279 // only really optimize for size when -Oz (MinSize) is used.
4280 if (MF.getTarget().getTargetTriple().isOSDarwin())
4281 return MF.getFunction()->optForMinSize();
4282 return MF.getFunction()->optForSize();
4285 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4286 SDValue Chain, SDValue Dst,
4287 SDValue Src, uint64_t Size,
4288 unsigned Align, bool isVol,
4290 MachinePointerInfo DstPtrInfo,
4291 MachinePointerInfo SrcPtrInfo) {
4292 // Turn a memcpy of undef to nop.
4293 if (Src.getOpcode() == ISD::UNDEF)
4296 // Expand memcpy to a series of load and store ops if the size operand falls
4297 // below a certain threshold.
4298 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4299 // rather than maybe a humongous number of loads and stores.
4300 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4301 std::vector<EVT> MemOps;
4302 bool DstAlignCanChange = false;
4303 MachineFunction &MF = DAG.getMachineFunction();
4304 MachineFrameInfo *MFI = MF.getFrameInfo();
4305 bool OptSize = shouldLowerMemFuncForSize(MF);
4306 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4307 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4308 DstAlignCanChange = true;
4309 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4310 if (Align > SrcAlign)
4313 bool CopyFromStr = isMemSrcFromString(Src, Str);
4314 bool isZeroStr = CopyFromStr && Str.empty();
4315 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4317 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4318 (DstAlignCanChange ? 0 : Align),
4319 (isZeroStr ? 0 : SrcAlign),
4320 false, false, CopyFromStr, true, DAG, TLI))
4323 if (DstAlignCanChange) {
4324 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4325 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4327 // Don't promote to an alignment that would require dynamic stack
4329 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4330 if (!TRI->needsStackRealignment(MF))
4331 while (NewAlign > Align &&
4332 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4335 if (NewAlign > Align) {
4336 // Give the stack frame object a larger alignment if needed.
4337 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4338 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4343 SmallVector<SDValue, 8> OutChains;
4344 unsigned NumMemOps = MemOps.size();
4345 uint64_t SrcOff = 0, DstOff = 0;
4346 for (unsigned i = 0; i != NumMemOps; ++i) {
4348 unsigned VTSize = VT.getSizeInBits() / 8;
4349 SDValue Value, Store;
4351 if (VTSize > Size) {
4352 // Issuing an unaligned load / store pair that overlaps with the previous
4353 // pair. Adjust the offset accordingly.
4354 assert(i == NumMemOps-1 && i != 0);
4355 SrcOff -= VTSize - Size;
4356 DstOff -= VTSize - Size;
4360 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4361 // It's unlikely a store of a vector immediate can be done in a single
4362 // instruction. It would require a load from a constantpool first.
4363 // We only handle zero vectors here.
4364 // FIXME: Handle other cases where store of vector immediate is done in
4365 // a single instruction.
4366 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4367 if (Value.getNode())
4368 Store = DAG.getStore(Chain, dl, Value,
4369 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4370 DstPtrInfo.getWithOffset(DstOff), isVol,
4374 if (!Store.getNode()) {
4375 // The type might not be legal for the target. This should only happen
4376 // if the type is smaller than a legal type, as on PPC, so the right
4377 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4378 // to Load/Store if NVT==VT.
4379 // FIXME does the case above also need this?
4380 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4381 assert(NVT.bitsGE(VT));
4382 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4383 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4384 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4385 false, MinAlign(SrcAlign, SrcOff));
4386 Store = DAG.getTruncStore(Chain, dl, Value,
4387 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4388 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4391 OutChains.push_back(Store);
4397 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4400 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4401 SDValue Chain, SDValue Dst,
4402 SDValue Src, uint64_t Size,
4403 unsigned Align, bool isVol,
4405 MachinePointerInfo DstPtrInfo,
4406 MachinePointerInfo SrcPtrInfo) {
4407 // Turn a memmove of undef to nop.
4408 if (Src.getOpcode() == ISD::UNDEF)
4411 // Expand memmove to a series of load and store ops if the size operand falls
4412 // below a certain threshold.
4413 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4414 std::vector<EVT> MemOps;
4415 bool DstAlignCanChange = false;
4416 MachineFunction &MF = DAG.getMachineFunction();
4417 MachineFrameInfo *MFI = MF.getFrameInfo();
4418 bool OptSize = shouldLowerMemFuncForSize(MF);
4419 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4420 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4421 DstAlignCanChange = true;
4422 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4423 if (Align > SrcAlign)
4425 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4427 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4428 (DstAlignCanChange ? 0 : Align), SrcAlign,
4429 false, false, false, false, DAG, TLI))
4432 if (DstAlignCanChange) {
4433 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4434 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4435 if (NewAlign > Align) {
4436 // Give the stack frame object a larger alignment if needed.
4437 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4438 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4443 uint64_t SrcOff = 0, DstOff = 0;
4444 SmallVector<SDValue, 8> LoadValues;
4445 SmallVector<SDValue, 8> LoadChains;
4446 SmallVector<SDValue, 8> OutChains;
4447 unsigned NumMemOps = MemOps.size();
4448 for (unsigned i = 0; i < NumMemOps; i++) {
4450 unsigned VTSize = VT.getSizeInBits() / 8;
4453 Value = DAG.getLoad(VT, dl, Chain,
4454 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4455 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4456 false, false, SrcAlign);
4457 LoadValues.push_back(Value);
4458 LoadChains.push_back(Value.getValue(1));
4461 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4463 for (unsigned i = 0; i < NumMemOps; i++) {
4465 unsigned VTSize = VT.getSizeInBits() / 8;
4468 Store = DAG.getStore(Chain, dl, LoadValues[i],
4469 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4470 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4471 OutChains.push_back(Store);
4475 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4478 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4481 /// \param DAG Selection DAG where lowered code is placed.
4482 /// \param dl Link to corresponding IR location.
4483 /// \param Chain Control flow dependency.
4484 /// \param Dst Pointer to destination memory location.
4485 /// \param Src Value of byte to write into the memory.
4486 /// \param Size Number of bytes to write.
4487 /// \param Align Alignment of the destination in bytes.
4488 /// \param isVol True if destination is volatile.
4489 /// \param DstPtrInfo IR information on the memory pointer.
4490 /// \returns New head in the control flow, if lowering was successful, empty
4491 /// SDValue otherwise.
4493 /// The function tries to replace 'llvm.memset' intrinsic with several store
4494 /// operations and value calculation code. This is usually profitable for small
4496 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4497 SDValue Chain, SDValue Dst,
4498 SDValue Src, uint64_t Size,
4499 unsigned Align, bool isVol,
4500 MachinePointerInfo DstPtrInfo) {
4501 // Turn a memset of undef to nop.
4502 if (Src.getOpcode() == ISD::UNDEF)
4505 // Expand memset to a series of load/store ops if the size operand
4506 // falls below a certain threshold.
4507 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4508 std::vector<EVT> MemOps;
4509 bool DstAlignCanChange = false;
4510 MachineFunction &MF = DAG.getMachineFunction();
4511 MachineFrameInfo *MFI = MF.getFrameInfo();
4512 bool OptSize = shouldLowerMemFuncForSize(MF);
4513 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4514 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4515 DstAlignCanChange = true;
4517 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4518 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4519 Size, (DstAlignCanChange ? 0 : Align), 0,
4520 true, IsZeroVal, false, true, DAG, TLI))
4523 if (DstAlignCanChange) {
4524 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4525 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4526 if (NewAlign > Align) {
4527 // Give the stack frame object a larger alignment if needed.
4528 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4529 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4534 SmallVector<SDValue, 8> OutChains;
4535 uint64_t DstOff = 0;
4536 unsigned NumMemOps = MemOps.size();
4538 // Find the largest store and generate the bit pattern for it.
4539 EVT LargestVT = MemOps[0];
4540 for (unsigned i = 1; i < NumMemOps; i++)
4541 if (MemOps[i].bitsGT(LargestVT))
4542 LargestVT = MemOps[i];
4543 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4545 for (unsigned i = 0; i < NumMemOps; i++) {
4547 unsigned VTSize = VT.getSizeInBits() / 8;
4548 if (VTSize > Size) {
4549 // Issuing an unaligned load / store pair that overlaps with the previous
4550 // pair. Adjust the offset accordingly.
4551 assert(i == NumMemOps-1 && i != 0);
4552 DstOff -= VTSize - Size;
4555 // If this store is smaller than the largest store see whether we can get
4556 // the smaller value for free with a truncate.
4557 SDValue Value = MemSetValue;
4558 if (VT.bitsLT(LargestVT)) {
4559 if (!LargestVT.isVector() && !VT.isVector() &&
4560 TLI.isTruncateFree(LargestVT, VT))
4561 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4563 Value = getMemsetValue(Src, VT, DAG, dl);
4565 assert(Value.getValueType() == VT && "Value with wrong type.");
4566 SDValue Store = DAG.getStore(Chain, dl, Value,
4567 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4568 DstPtrInfo.getWithOffset(DstOff),
4569 isVol, false, Align);
4570 OutChains.push_back(Store);
4571 DstOff += VT.getSizeInBits() / 8;
4575 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4578 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4579 SDValue Src, SDValue Size,
4580 unsigned Align, bool isVol, bool AlwaysInline,
4581 bool isTailCall, MachinePointerInfo DstPtrInfo,
4582 MachinePointerInfo SrcPtrInfo) {
4583 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4585 // Check to see if we should lower the memcpy to loads and stores first.
4586 // For cases within the target-specified limits, this is the best choice.
4587 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4589 // Memcpy with size zero? Just return the original chain.
4590 if (ConstantSize->isNullValue())
4593 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4594 ConstantSize->getZExtValue(),Align,
4595 isVol, false, DstPtrInfo, SrcPtrInfo);
4596 if (Result.getNode())
4600 // Then check to see if we should lower the memcpy with target-specific
4601 // code. If the target chooses to do this, this is the next best.
4603 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4604 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4605 DstPtrInfo, SrcPtrInfo);
4606 if (Result.getNode())
4610 // If we really need inline code and the target declined to provide it,
4611 // use a (potentially long) sequence of loads and stores.
4613 assert(ConstantSize && "AlwaysInline requires a constant size!");
4614 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4615 ConstantSize->getZExtValue(), Align, isVol,
4616 true, DstPtrInfo, SrcPtrInfo);
4619 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4620 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4621 // respect volatile, so they may do things like read or write memory
4622 // beyond the given memory regions. But fixing this isn't easy, and most
4623 // people don't care.
4625 // Emit a library call.
4626 TargetLowering::ArgListTy Args;
4627 TargetLowering::ArgListEntry Entry;
4628 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4629 Entry.Node = Dst; Args.push_back(Entry);
4630 Entry.Node = Src; Args.push_back(Entry);
4631 Entry.Node = Size; Args.push_back(Entry);
4632 // FIXME: pass in SDLoc
4633 TargetLowering::CallLoweringInfo CLI(*this);
4636 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4637 Type::getVoidTy(*getContext()),
4638 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4639 TLI->getPointerTy(getDataLayout())),
4642 .setTailCall(isTailCall);
4644 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4645 return CallResult.second;
4648 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4649 SDValue Src, SDValue Size,
4650 unsigned Align, bool isVol, bool isTailCall,
4651 MachinePointerInfo DstPtrInfo,
4652 MachinePointerInfo SrcPtrInfo) {
4653 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4655 // Check to see if we should lower the memmove to loads and stores first.
4656 // For cases within the target-specified limits, this is the best choice.
4657 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4659 // Memmove with size zero? Just return the original chain.
4660 if (ConstantSize->isNullValue())
4664 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4665 ConstantSize->getZExtValue(), Align, isVol,
4666 false, DstPtrInfo, SrcPtrInfo);
4667 if (Result.getNode())
4671 // Then check to see if we should lower the memmove with target-specific
4672 // code. If the target chooses to do this, this is the next best.
4674 SDValue Result = TSI->EmitTargetCodeForMemmove(
4675 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4676 if (Result.getNode())
4680 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4681 // not be safe. See memcpy above for more details.
4683 // Emit a library call.
4684 TargetLowering::ArgListTy Args;
4685 TargetLowering::ArgListEntry Entry;
4686 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4687 Entry.Node = Dst; Args.push_back(Entry);
4688 Entry.Node = Src; Args.push_back(Entry);
4689 Entry.Node = Size; Args.push_back(Entry);
4690 // FIXME: pass in SDLoc
4691 TargetLowering::CallLoweringInfo CLI(*this);
4694 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4695 Type::getVoidTy(*getContext()),
4696 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4697 TLI->getPointerTy(getDataLayout())),
4700 .setTailCall(isTailCall);
4702 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4703 return CallResult.second;
4706 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4707 SDValue Src, SDValue Size,
4708 unsigned Align, bool isVol, bool isTailCall,
4709 MachinePointerInfo DstPtrInfo) {
4710 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4712 // Check to see if we should lower the memset to stores first.
4713 // For cases within the target-specified limits, this is the best choice.
4714 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4716 // Memset with size zero? Just return the original chain.
4717 if (ConstantSize->isNullValue())
4721 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4722 Align, isVol, DstPtrInfo);
4724 if (Result.getNode())
4728 // Then check to see if we should lower the memset with target-specific
4729 // code. If the target chooses to do this, this is the next best.
4731 SDValue Result = TSI->EmitTargetCodeForMemset(
4732 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4733 if (Result.getNode())
4737 // Emit a library call.
4738 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4739 TargetLowering::ArgListTy Args;
4740 TargetLowering::ArgListEntry Entry;
4741 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4742 Args.push_back(Entry);
4744 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4745 Args.push_back(Entry);
4747 Entry.Ty = IntPtrTy;
4748 Args.push_back(Entry);
4750 // FIXME: pass in SDLoc
4751 TargetLowering::CallLoweringInfo CLI(*this);
4754 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4755 Type::getVoidTy(*getContext()),
4756 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4757 TLI->getPointerTy(getDataLayout())),
4760 .setTailCall(isTailCall);
4762 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4763 return CallResult.second;
4766 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4767 SDVTList VTList, ArrayRef<SDValue> Ops,
4768 MachineMemOperand *MMO,
4769 AtomicOrdering SuccessOrdering,
4770 AtomicOrdering FailureOrdering,
4771 SynchronizationScope SynchScope) {
4772 FoldingSetNodeID ID;
4773 ID.AddInteger(MemVT.getRawBits());
4774 AddNodeIDNode(ID, Opcode, VTList, Ops);
4775 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4777 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4778 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4779 return SDValue(E, 0);
4782 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4783 // SDNode doesn't have access to it. This memory will be "leaked" when
4784 // the node is deallocated, but recovered when the allocator is released.
4785 // If the number of operands is less than 5 we use AtomicSDNode's internal
4787 unsigned NumOps = Ops.size();
4788 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4791 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4792 dl.getDebugLoc(), VTList, MemVT,
4793 Ops.data(), DynOps, NumOps, MMO,
4794 SuccessOrdering, FailureOrdering,
4796 CSEMap.InsertNode(N, IP);
4798 return SDValue(N, 0);
4801 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4802 SDVTList VTList, ArrayRef<SDValue> Ops,
4803 MachineMemOperand *MMO,
4804 AtomicOrdering Ordering,
4805 SynchronizationScope SynchScope) {
4806 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4807 Ordering, SynchScope);
4810 SDValue SelectionDAG::getAtomicCmpSwap(
4811 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4812 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4813 unsigned Alignment, AtomicOrdering SuccessOrdering,
4814 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4815 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4816 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4817 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4819 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4820 Alignment = getEVTAlignment(MemVT);
4822 MachineFunction &MF = getMachineFunction();
4824 // FIXME: Volatile isn't really correct; we should keep track of atomic
4825 // orderings in the memoperand.
4826 unsigned Flags = MachineMemOperand::MOVolatile;
4827 Flags |= MachineMemOperand::MOLoad;
4828 Flags |= MachineMemOperand::MOStore;
4830 MachineMemOperand *MMO =
4831 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4833 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4834 SuccessOrdering, FailureOrdering, SynchScope);
4837 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4838 SDVTList VTs, SDValue Chain, SDValue Ptr,
4839 SDValue Cmp, SDValue Swp,
4840 MachineMemOperand *MMO,
4841 AtomicOrdering SuccessOrdering,
4842 AtomicOrdering FailureOrdering,
4843 SynchronizationScope SynchScope) {
4844 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4845 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4846 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4848 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4849 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4850 SuccessOrdering, FailureOrdering, SynchScope);
4853 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4855 SDValue Ptr, SDValue Val,
4856 const Value* PtrVal,
4858 AtomicOrdering Ordering,
4859 SynchronizationScope SynchScope) {
4860 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4861 Alignment = getEVTAlignment(MemVT);
4863 MachineFunction &MF = getMachineFunction();
4864 // An atomic store does not load. An atomic load does not store.
4865 // (An atomicrmw obviously both loads and stores.)
4866 // For now, atomics are considered to be volatile always, and they are
4868 // FIXME: Volatile isn't really correct; we should keep track of atomic
4869 // orderings in the memoperand.
4870 unsigned Flags = MachineMemOperand::MOVolatile;
4871 if (Opcode != ISD::ATOMIC_STORE)
4872 Flags |= MachineMemOperand::MOLoad;
4873 if (Opcode != ISD::ATOMIC_LOAD)
4874 Flags |= MachineMemOperand::MOStore;
4876 MachineMemOperand *MMO =
4877 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4878 MemVT.getStoreSize(), Alignment);
4880 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4881 Ordering, SynchScope);
4884 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4886 SDValue Ptr, SDValue Val,
4887 MachineMemOperand *MMO,
4888 AtomicOrdering Ordering,
4889 SynchronizationScope SynchScope) {
4890 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4891 Opcode == ISD::ATOMIC_LOAD_SUB ||
4892 Opcode == ISD::ATOMIC_LOAD_AND ||
4893 Opcode == ISD::ATOMIC_LOAD_OR ||
4894 Opcode == ISD::ATOMIC_LOAD_XOR ||
4895 Opcode == ISD::ATOMIC_LOAD_NAND ||
4896 Opcode == ISD::ATOMIC_LOAD_MIN ||
4897 Opcode == ISD::ATOMIC_LOAD_MAX ||
4898 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4899 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4900 Opcode == ISD::ATOMIC_SWAP ||
4901 Opcode == ISD::ATOMIC_STORE) &&
4902 "Invalid Atomic Op");
4904 EVT VT = Val.getValueType();
4906 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4907 getVTList(VT, MVT::Other);
4908 SDValue Ops[] = {Chain, Ptr, Val};
4909 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4912 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4913 EVT VT, SDValue Chain,
4915 MachineMemOperand *MMO,
4916 AtomicOrdering Ordering,
4917 SynchronizationScope SynchScope) {
4918 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4920 SDVTList VTs = getVTList(VT, MVT::Other);
4921 SDValue Ops[] = {Chain, Ptr};
4922 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4925 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4926 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4927 if (Ops.size() == 1)
4930 SmallVector<EVT, 4> VTs;
4931 VTs.reserve(Ops.size());
4932 for (unsigned i = 0; i < Ops.size(); ++i)
4933 VTs.push_back(Ops[i].getValueType());
4934 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4938 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4939 ArrayRef<SDValue> Ops,
4940 EVT MemVT, MachinePointerInfo PtrInfo,
4941 unsigned Align, bool Vol,
4942 bool ReadMem, bool WriteMem, unsigned Size) {
4943 if (Align == 0) // Ensure that codegen never sees alignment 0
4944 Align = getEVTAlignment(MemVT);
4946 MachineFunction &MF = getMachineFunction();
4949 Flags |= MachineMemOperand::MOStore;
4951 Flags |= MachineMemOperand::MOLoad;
4953 Flags |= MachineMemOperand::MOVolatile;
4955 Size = MemVT.getStoreSize();
4956 MachineMemOperand *MMO =
4957 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4959 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4963 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4964 ArrayRef<SDValue> Ops, EVT MemVT,
4965 MachineMemOperand *MMO) {
4966 assert((Opcode == ISD::INTRINSIC_VOID ||
4967 Opcode == ISD::INTRINSIC_W_CHAIN ||
4968 Opcode == ISD::PREFETCH ||
4969 Opcode == ISD::LIFETIME_START ||
4970 Opcode == ISD::LIFETIME_END ||
4971 (Opcode <= INT_MAX &&
4972 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4973 "Opcode is not a memory-accessing opcode!");
4975 // Memoize the node unless it returns a flag.
4976 MemIntrinsicSDNode *N;
4977 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4978 FoldingSetNodeID ID;
4979 AddNodeIDNode(ID, Opcode, VTList, Ops);
4980 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4982 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4983 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4984 return SDValue(E, 0);
4987 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4988 dl.getDebugLoc(), VTList, Ops,
4990 CSEMap.InsertNode(N, IP);
4992 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4993 dl.getDebugLoc(), VTList, Ops,
4997 return SDValue(N, 0);
5000 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
5001 /// MachinePointerInfo record from it. This is particularly useful because the
5002 /// code generator has many cases where it doesn't bother passing in a
5003 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
5004 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
5005 int64_t Offset = 0) {
5006 // If this is FI+Offset, we can model it.
5007 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
5008 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
5009 FI->getIndex(), Offset);
5011 // If this is (FI+Offset1)+Offset2, we can model it.
5012 if (Ptr.getOpcode() != ISD::ADD ||
5013 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
5014 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
5015 return MachinePointerInfo();
5017 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
5018 return MachinePointerInfo::getFixedStack(
5019 DAG.getMachineFunction(), FI,
5020 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
5023 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
5024 /// MachinePointerInfo record from it. This is particularly useful because the
5025 /// code generator has many cases where it doesn't bother passing in a
5026 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
5027 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
5029 // If the 'Offset' value isn't a constant, we can't handle this.
5030 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
5031 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
5032 if (OffsetOp.getOpcode() == ISD::UNDEF)
5033 return InferPointerInfo(DAG, Ptr);
5034 return MachinePointerInfo();
5039 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5040 EVT VT, SDLoc dl, SDValue Chain,
5041 SDValue Ptr, SDValue Offset,
5042 MachinePointerInfo PtrInfo, EVT MemVT,
5043 bool isVolatile, bool isNonTemporal, bool isInvariant,
5044 unsigned Alignment, const AAMDNodes &AAInfo,
5045 const MDNode *Ranges) {
5046 assert(Chain.getValueType() == MVT::Other &&
5047 "Invalid chain type");
5048 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5049 Alignment = getEVTAlignment(VT);
5051 unsigned Flags = MachineMemOperand::MOLoad;
5053 Flags |= MachineMemOperand::MOVolatile;
5055 Flags |= MachineMemOperand::MONonTemporal;
5057 Flags |= MachineMemOperand::MOInvariant;
5059 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5061 if (PtrInfo.V.isNull())
5062 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5064 MachineFunction &MF = getMachineFunction();
5065 MachineMemOperand *MMO =
5066 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5068 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5072 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5073 EVT VT, SDLoc dl, SDValue Chain,
5074 SDValue Ptr, SDValue Offset, EVT MemVT,
5075 MachineMemOperand *MMO) {
5077 ExtType = ISD::NON_EXTLOAD;
5078 } else if (ExtType == ISD::NON_EXTLOAD) {
5079 assert(VT == MemVT && "Non-extending load from different memory type!");
5082 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5083 "Should only be an extending load, not truncating!");
5084 assert(VT.isInteger() == MemVT.isInteger() &&
5085 "Cannot convert from FP to Int or Int -> FP!");
5086 assert(VT.isVector() == MemVT.isVector() &&
5087 "Cannot use an ext load to convert to or from a vector!");
5088 assert((!VT.isVector() ||
5089 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5090 "Cannot use an ext load to change the number of vector elements!");
5093 bool Indexed = AM != ISD::UNINDEXED;
5094 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5095 "Unindexed load with an offset!");
5097 SDVTList VTs = Indexed ?
5098 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5099 SDValue Ops[] = { Chain, Ptr, Offset };
5100 FoldingSetNodeID ID;
5101 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5102 ID.AddInteger(MemVT.getRawBits());
5103 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5104 MMO->isNonTemporal(),
5105 MMO->isInvariant()));
5106 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5108 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5109 cast<LoadSDNode>(E)->refineAlignment(MMO);
5110 return SDValue(E, 0);
5112 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5113 dl.getDebugLoc(), VTs, AM, ExtType,
5115 CSEMap.InsertNode(N, IP);
5117 return SDValue(N, 0);
5120 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5121 SDValue Chain, SDValue Ptr,
5122 MachinePointerInfo PtrInfo,
5123 bool isVolatile, bool isNonTemporal,
5124 bool isInvariant, unsigned Alignment,
5125 const AAMDNodes &AAInfo,
5126 const MDNode *Ranges) {
5127 SDValue Undef = getUNDEF(Ptr.getValueType());
5128 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5129 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5133 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5134 SDValue Chain, SDValue Ptr,
5135 MachineMemOperand *MMO) {
5136 SDValue Undef = getUNDEF(Ptr.getValueType());
5137 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5141 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5142 SDValue Chain, SDValue Ptr,
5143 MachinePointerInfo PtrInfo, EVT MemVT,
5144 bool isVolatile, bool isNonTemporal,
5145 bool isInvariant, unsigned Alignment,
5146 const AAMDNodes &AAInfo) {
5147 SDValue Undef = getUNDEF(Ptr.getValueType());
5148 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5149 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5154 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5155 SDValue Chain, SDValue Ptr, EVT MemVT,
5156 MachineMemOperand *MMO) {
5157 SDValue Undef = getUNDEF(Ptr.getValueType());
5158 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5163 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5164 SDValue Offset, ISD::MemIndexedMode AM) {
5165 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5166 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5167 "Load is already a indexed load!");
5168 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5169 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5170 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5171 false, LD->getAlignment());
5174 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5175 SDValue Ptr, MachinePointerInfo PtrInfo,
5176 bool isVolatile, bool isNonTemporal,
5177 unsigned Alignment, const AAMDNodes &AAInfo) {
5178 assert(Chain.getValueType() == MVT::Other &&
5179 "Invalid chain type");
5180 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5181 Alignment = getEVTAlignment(Val.getValueType());
5183 unsigned Flags = MachineMemOperand::MOStore;
5185 Flags |= MachineMemOperand::MOVolatile;
5187 Flags |= MachineMemOperand::MONonTemporal;
5189 if (PtrInfo.V.isNull())
5190 PtrInfo = InferPointerInfo(*this, Ptr);
5192 MachineFunction &MF = getMachineFunction();
5193 MachineMemOperand *MMO =
5194 MF.getMachineMemOperand(PtrInfo, Flags,
5195 Val.getValueType().getStoreSize(), Alignment,
5198 return getStore(Chain, dl, Val, Ptr, MMO);
5201 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5202 SDValue Ptr, MachineMemOperand *MMO) {
5203 assert(Chain.getValueType() == MVT::Other &&
5204 "Invalid chain type");
5205 EVT VT = Val.getValueType();
5206 SDVTList VTs = getVTList(MVT::Other);
5207 SDValue Undef = getUNDEF(Ptr.getValueType());
5208 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5209 FoldingSetNodeID ID;
5210 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5211 ID.AddInteger(VT.getRawBits());
5212 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5213 MMO->isNonTemporal(), MMO->isInvariant()));
5214 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5216 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5217 cast<StoreSDNode>(E)->refineAlignment(MMO);
5218 return SDValue(E, 0);
5220 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5221 dl.getDebugLoc(), VTs,
5222 ISD::UNINDEXED, false, VT, MMO);
5223 CSEMap.InsertNode(N, IP);
5225 return SDValue(N, 0);
5228 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5229 SDValue Ptr, MachinePointerInfo PtrInfo,
5230 EVT SVT,bool isVolatile, bool isNonTemporal,
5232 const AAMDNodes &AAInfo) {
5233 assert(Chain.getValueType() == MVT::Other &&
5234 "Invalid chain type");
5235 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5236 Alignment = getEVTAlignment(SVT);
5238 unsigned Flags = MachineMemOperand::MOStore;
5240 Flags |= MachineMemOperand::MOVolatile;
5242 Flags |= MachineMemOperand::MONonTemporal;
5244 if (PtrInfo.V.isNull())
5245 PtrInfo = InferPointerInfo(*this, Ptr);
5247 MachineFunction &MF = getMachineFunction();
5248 MachineMemOperand *MMO =
5249 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5252 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5255 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5256 SDValue Ptr, EVT SVT,
5257 MachineMemOperand *MMO) {
5258 EVT VT = Val.getValueType();
5260 assert(Chain.getValueType() == MVT::Other &&
5261 "Invalid chain type");
5263 return getStore(Chain, dl, Val, Ptr, MMO);
5265 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5266 "Should only be a truncating store, not extending!");
5267 assert(VT.isInteger() == SVT.isInteger() &&
5268 "Can't do FP-INT conversion!");
5269 assert(VT.isVector() == SVT.isVector() &&
5270 "Cannot use trunc store to convert to or from a vector!");
5271 assert((!VT.isVector() ||
5272 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5273 "Cannot use trunc store to change the number of vector elements!");
5275 SDVTList VTs = getVTList(MVT::Other);
5276 SDValue Undef = getUNDEF(Ptr.getValueType());
5277 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5278 FoldingSetNodeID ID;
5279 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5280 ID.AddInteger(SVT.getRawBits());
5281 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5282 MMO->isNonTemporal(), MMO->isInvariant()));
5283 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5285 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5286 cast<StoreSDNode>(E)->refineAlignment(MMO);
5287 return SDValue(E, 0);
5289 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5290 dl.getDebugLoc(), VTs,
5291 ISD::UNINDEXED, true, SVT, MMO);
5292 CSEMap.InsertNode(N, IP);
5294 return SDValue(N, 0);
5298 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5299 SDValue Offset, ISD::MemIndexedMode AM) {
5300 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5301 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5302 "Store is already a indexed store!");
5303 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5304 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5305 FoldingSetNodeID ID;
5306 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5307 ID.AddInteger(ST->getMemoryVT().getRawBits());
5308 ID.AddInteger(ST->getRawSubclassData());
5309 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5311 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5312 return SDValue(E, 0);
5314 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5315 dl.getDebugLoc(), VTs, AM,
5316 ST->isTruncatingStore(),
5318 ST->getMemOperand());
5319 CSEMap.InsertNode(N, IP);
5321 return SDValue(N, 0);
5325 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5326 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5327 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5329 SDVTList VTs = getVTList(VT, MVT::Other);
5330 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5331 FoldingSetNodeID ID;
5332 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5333 ID.AddInteger(VT.getRawBits());
5334 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, 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<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5342 return SDValue(E, 0);
5344 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5345 dl.getDebugLoc(), Ops, 4, VTs,
5347 CSEMap.InsertNode(N, IP);
5349 return SDValue(N, 0);
5352 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5353 SDValue Ptr, SDValue Mask, EVT MemVT,
5354 MachineMemOperand *MMO, bool isTrunc) {
5355 assert(Chain.getValueType() == MVT::Other &&
5356 "Invalid chain type");
5357 EVT VT = Val.getValueType();
5358 SDVTList VTs = getVTList(MVT::Other);
5359 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5360 FoldingSetNodeID ID;
5361 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5362 ID.AddInteger(VT.getRawBits());
5363 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5364 MMO->isNonTemporal(), MMO->isInvariant()));
5365 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5367 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5368 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5369 return SDValue(E, 0);
5371 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5372 dl.getDebugLoc(), Ops, 4,
5373 VTs, isTrunc, MemVT, MMO);
5374 CSEMap.InsertNode(N, IP);
5376 return SDValue(N, 0);
5380 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5381 ArrayRef<SDValue> Ops,
5382 MachineMemOperand *MMO) {
5384 FoldingSetNodeID ID;
5385 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5386 ID.AddInteger(VT.getRawBits());
5387 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5389 MMO->isNonTemporal(),
5390 MMO->isInvariant()));
5391 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5393 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5394 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5395 return SDValue(E, 0);
5397 MaskedGatherSDNode *N =
5398 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5400 CSEMap.InsertNode(N, IP);
5402 return SDValue(N, 0);
5405 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5406 ArrayRef<SDValue> Ops,
5407 MachineMemOperand *MMO) {
5408 FoldingSetNodeID ID;
5409 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5410 ID.AddInteger(VT.getRawBits());
5411 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5412 MMO->isNonTemporal(),
5413 MMO->isInvariant()));
5414 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5416 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5417 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5418 return SDValue(E, 0);
5421 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5423 CSEMap.InsertNode(N, IP);
5425 return SDValue(N, 0);
5428 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5429 SDValue Chain, SDValue Ptr,
5432 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5433 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5436 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5437 ArrayRef<SDUse> Ops) {
5438 switch (Ops.size()) {
5439 case 0: return getNode(Opcode, DL, VT);
5440 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5441 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5442 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5446 // Copy from an SDUse array into an SDValue array for use with
5447 // the regular getNode logic.
5448 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5449 return getNode(Opcode, DL, VT, NewOps);
5452 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5453 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5454 unsigned NumOps = Ops.size();
5456 case 0: return getNode(Opcode, DL, VT);
5457 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5458 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5459 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5465 case ISD::SELECT_CC: {
5466 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5467 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5468 "LHS and RHS of condition must have same type!");
5469 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5470 "True and False arms of SelectCC must have same type!");
5471 assert(Ops[2].getValueType() == VT &&
5472 "select_cc node must be of same type as true and false value!");
5476 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5477 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5478 "LHS/RHS of comparison should match types!");
5485 SDVTList VTs = getVTList(VT);
5487 if (VT != MVT::Glue) {
5488 FoldingSetNodeID ID;
5489 AddNodeIDNode(ID, Opcode, VTs, Ops);
5492 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5493 return SDValue(E, 0);
5495 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5497 CSEMap.InsertNode(N, IP);
5499 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5504 return SDValue(N, 0);
5507 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5508 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5509 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5512 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5513 ArrayRef<SDValue> Ops) {
5514 if (VTList.NumVTs == 1)
5515 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5519 // FIXME: figure out how to safely handle things like
5520 // int foo(int x) { return 1 << (x & 255); }
5521 // int bar() { return foo(256); }
5522 case ISD::SRA_PARTS:
5523 case ISD::SRL_PARTS:
5524 case ISD::SHL_PARTS:
5525 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5526 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5527 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5528 else if (N3.getOpcode() == ISD::AND)
5529 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5530 // If the and is only masking out bits that cannot effect the shift,
5531 // eliminate the and.
5532 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5533 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5534 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5540 // Memoize the node unless it returns a flag.
5542 unsigned NumOps = Ops.size();
5543 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5544 FoldingSetNodeID ID;
5545 AddNodeIDNode(ID, Opcode, VTList, Ops);
5547 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5548 return SDValue(E, 0);
5551 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5552 DL.getDebugLoc(), VTList, Ops[0]);
5553 } else if (NumOps == 2) {
5554 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5555 DL.getDebugLoc(), VTList, Ops[0],
5557 } else if (NumOps == 3) {
5558 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5559 DL.getDebugLoc(), VTList, Ops[0],
5562 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5565 CSEMap.InsertNode(N, IP);
5568 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5569 DL.getDebugLoc(), VTList, Ops[0]);
5570 } else if (NumOps == 2) {
5571 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5572 DL.getDebugLoc(), VTList, Ops[0],
5574 } else if (NumOps == 3) {
5575 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5576 DL.getDebugLoc(), VTList, Ops[0],
5579 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5584 return SDValue(N, 0);
5587 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5588 return getNode(Opcode, DL, VTList, None);
5591 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5593 SDValue Ops[] = { N1 };
5594 return getNode(Opcode, DL, VTList, Ops);
5597 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5598 SDValue N1, SDValue N2) {
5599 SDValue Ops[] = { N1, N2 };
5600 return getNode(Opcode, DL, VTList, Ops);
5603 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5604 SDValue N1, SDValue N2, SDValue N3) {
5605 SDValue Ops[] = { N1, N2, N3 };
5606 return getNode(Opcode, DL, VTList, Ops);
5609 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5610 SDValue N1, SDValue N2, SDValue N3,
5612 SDValue Ops[] = { N1, N2, N3, N4 };
5613 return getNode(Opcode, DL, VTList, Ops);
5616 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5617 SDValue N1, SDValue N2, SDValue N3,
5618 SDValue N4, SDValue N5) {
5619 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5620 return getNode(Opcode, DL, VTList, Ops);
5623 SDVTList SelectionDAG::getVTList(EVT VT) {
5624 return makeVTList(SDNode::getValueTypeList(VT), 1);
5627 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5628 FoldingSetNodeID ID;
5630 ID.AddInteger(VT1.getRawBits());
5631 ID.AddInteger(VT2.getRawBits());
5634 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5636 EVT *Array = Allocator.Allocate<EVT>(2);
5639 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5640 VTListMap.InsertNode(Result, IP);
5642 return Result->getSDVTList();
5645 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5646 FoldingSetNodeID ID;
5648 ID.AddInteger(VT1.getRawBits());
5649 ID.AddInteger(VT2.getRawBits());
5650 ID.AddInteger(VT3.getRawBits());
5653 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5655 EVT *Array = Allocator.Allocate<EVT>(3);
5659 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5660 VTListMap.InsertNode(Result, IP);
5662 return Result->getSDVTList();
5665 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5666 FoldingSetNodeID ID;
5668 ID.AddInteger(VT1.getRawBits());
5669 ID.AddInteger(VT2.getRawBits());
5670 ID.AddInteger(VT3.getRawBits());
5671 ID.AddInteger(VT4.getRawBits());
5674 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5676 EVT *Array = Allocator.Allocate<EVT>(4);
5681 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5682 VTListMap.InsertNode(Result, IP);
5684 return Result->getSDVTList();
5687 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5688 unsigned NumVTs = VTs.size();
5689 FoldingSetNodeID ID;
5690 ID.AddInteger(NumVTs);
5691 for (unsigned index = 0; index < NumVTs; index++) {
5692 ID.AddInteger(VTs[index].getRawBits());
5696 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5698 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5699 std::copy(VTs.begin(), VTs.end(), Array);
5700 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5701 VTListMap.InsertNode(Result, IP);
5703 return Result->getSDVTList();
5707 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5708 /// specified operands. If the resultant node already exists in the DAG,
5709 /// this does not modify the specified node, instead it returns the node that
5710 /// already exists. If the resultant node does not exist in the DAG, the
5711 /// input node is returned. As a degenerate case, if you specify the same
5712 /// input operands as the node already has, the input node is returned.
5713 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5714 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5716 // Check to see if there is no change.
5717 if (Op == N->getOperand(0)) return N;
5719 // See if the modified node already exists.
5720 void *InsertPos = nullptr;
5721 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5724 // Nope it doesn't. Remove the node from its current place in the maps.
5726 if (!RemoveNodeFromCSEMaps(N))
5727 InsertPos = nullptr;
5729 // Now we update the operands.
5730 N->OperandList[0].set(Op);
5732 // If this gets put into a CSE map, add it.
5733 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5737 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5738 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5740 // Check to see if there is no change.
5741 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5742 return N; // No operands changed, just return the input node.
5744 // See if the modified node already exists.
5745 void *InsertPos = nullptr;
5746 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5749 // Nope it doesn't. Remove the node from its current place in the maps.
5751 if (!RemoveNodeFromCSEMaps(N))
5752 InsertPos = nullptr;
5754 // Now we update the operands.
5755 if (N->OperandList[0] != Op1)
5756 N->OperandList[0].set(Op1);
5757 if (N->OperandList[1] != Op2)
5758 N->OperandList[1].set(Op2);
5760 // If this gets put into a CSE map, add it.
5761 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5765 SDNode *SelectionDAG::
5766 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5767 SDValue Ops[] = { Op1, Op2, Op3 };
5768 return UpdateNodeOperands(N, Ops);
5771 SDNode *SelectionDAG::
5772 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5773 SDValue Op3, SDValue Op4) {
5774 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5775 return UpdateNodeOperands(N, Ops);
5778 SDNode *SelectionDAG::
5779 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5780 SDValue Op3, SDValue Op4, SDValue Op5) {
5781 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5782 return UpdateNodeOperands(N, Ops);
5785 SDNode *SelectionDAG::
5786 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5787 unsigned NumOps = Ops.size();
5788 assert(N->getNumOperands() == NumOps &&
5789 "Update with wrong number of operands");
5791 // If no operands changed just return the input node.
5792 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5795 // See if the modified node already exists.
5796 void *InsertPos = nullptr;
5797 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5800 // Nope it doesn't. Remove the node from its current place in the maps.
5802 if (!RemoveNodeFromCSEMaps(N))
5803 InsertPos = nullptr;
5805 // Now we update the operands.
5806 for (unsigned i = 0; i != NumOps; ++i)
5807 if (N->OperandList[i] != Ops[i])
5808 N->OperandList[i].set(Ops[i]);
5810 // If this gets put into a CSE map, add it.
5811 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5815 /// DropOperands - Release the operands and set this node to have
5817 void SDNode::DropOperands() {
5818 // Unlike the code in MorphNodeTo that does this, we don't need to
5819 // watch for dead nodes here.
5820 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5826 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5829 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5831 SDVTList VTs = getVTList(VT);
5832 return SelectNodeTo(N, MachineOpc, VTs, None);
5835 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5836 EVT VT, SDValue Op1) {
5837 SDVTList VTs = getVTList(VT);
5838 SDValue Ops[] = { Op1 };
5839 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5842 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5843 EVT VT, SDValue Op1,
5845 SDVTList VTs = getVTList(VT);
5846 SDValue Ops[] = { Op1, Op2 };
5847 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5850 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5851 EVT VT, SDValue Op1,
5852 SDValue Op2, SDValue Op3) {
5853 SDVTList VTs = getVTList(VT);
5854 SDValue Ops[] = { Op1, Op2, Op3 };
5855 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5858 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5859 EVT VT, ArrayRef<SDValue> Ops) {
5860 SDVTList VTs = getVTList(VT);
5861 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5864 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5865 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5866 SDVTList VTs = getVTList(VT1, VT2);
5867 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5870 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5872 SDVTList VTs = getVTList(VT1, VT2);
5873 return SelectNodeTo(N, MachineOpc, VTs, None);
5876 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5877 EVT VT1, EVT VT2, EVT VT3,
5878 ArrayRef<SDValue> Ops) {
5879 SDVTList VTs = getVTList(VT1, VT2, VT3);
5880 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5883 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5884 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5885 ArrayRef<SDValue> Ops) {
5886 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5887 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5890 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5893 SDVTList VTs = getVTList(VT1, VT2);
5894 SDValue Ops[] = { Op1 };
5895 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5898 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5900 SDValue Op1, SDValue Op2) {
5901 SDVTList VTs = getVTList(VT1, VT2);
5902 SDValue Ops[] = { Op1, Op2 };
5903 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5906 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5908 SDValue Op1, SDValue Op2,
5910 SDVTList VTs = getVTList(VT1, VT2);
5911 SDValue Ops[] = { Op1, Op2, Op3 };
5912 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5915 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5916 EVT VT1, EVT VT2, EVT VT3,
5917 SDValue Op1, SDValue Op2,
5919 SDVTList VTs = getVTList(VT1, VT2, VT3);
5920 SDValue Ops[] = { Op1, Op2, Op3 };
5921 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5924 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5925 SDVTList VTs,ArrayRef<SDValue> Ops) {
5926 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5927 // Reset the NodeID to -1.
5932 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5933 /// the line number information on the merged node since it is not possible to
5934 /// preserve the information that operation is associated with multiple lines.
5935 /// This will make the debugger working better at -O0, were there is a higher
5936 /// probability having other instructions associated with that line.
5938 /// For IROrder, we keep the smaller of the two
5939 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5940 DebugLoc NLoc = N->getDebugLoc();
5941 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5942 N->setDebugLoc(DebugLoc());
5944 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5945 N->setIROrder(Order);
5949 /// MorphNodeTo - This *mutates* the specified node to have the specified
5950 /// return type, opcode, and operands.
5952 /// Note that MorphNodeTo returns the resultant node. If there is already a
5953 /// node of the specified opcode and operands, it returns that node instead of
5954 /// the current one. Note that the SDLoc need not be the same.
5956 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5957 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5958 /// node, and because it doesn't require CSE recalculation for any of
5959 /// the node's users.
5961 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5962 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5963 /// the legalizer which maintain worklists that would need to be updated when
5964 /// deleting things.
5965 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5966 SDVTList VTs, ArrayRef<SDValue> Ops) {
5967 unsigned NumOps = Ops.size();
5968 // If an identical node already exists, use it.
5970 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5971 FoldingSetNodeID ID;
5972 AddNodeIDNode(ID, Opc, VTs, Ops);
5973 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5974 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5977 if (!RemoveNodeFromCSEMaps(N))
5980 // Start the morphing.
5982 N->ValueList = VTs.VTs;
5983 N->NumValues = VTs.NumVTs;
5985 // Clear the operands list, updating used nodes to remove this from their
5986 // use list. Keep track of any operands that become dead as a result.
5987 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5988 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5990 SDNode *Used = Use.getNode();
5992 if (Used->use_empty())
5993 DeadNodeSet.insert(Used);
5996 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5997 // Initialize the memory references information.
5998 MN->setMemRefs(nullptr, nullptr);
5999 // If NumOps is larger than the # of operands we can have in a
6000 // MachineSDNode, reallocate the operand list.
6001 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
6002 if (MN->OperandsNeedDelete)
6003 delete[] MN->OperandList;
6004 if (NumOps > array_lengthof(MN->LocalOperands))
6005 // We're creating a final node that will live unmorphed for the
6006 // remainder of the current SelectionDAG iteration, so we can allocate
6007 // the operands directly out of a pool with no recycling metadata.
6008 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6009 Ops.data(), NumOps);
6011 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
6012 MN->OperandsNeedDelete = false;
6014 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
6016 // If NumOps is larger than the # of operands we currently have, reallocate
6017 // the operand list.
6018 if (NumOps > N->NumOperands) {
6019 if (N->OperandsNeedDelete)
6020 delete[] N->OperandList;
6021 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
6022 N->OperandsNeedDelete = true;
6024 N->InitOperands(N->OperandList, Ops.data(), NumOps);
6027 // Delete any nodes that are still dead after adding the uses for the
6029 if (!DeadNodeSet.empty()) {
6030 SmallVector<SDNode *, 16> DeadNodes;
6031 for (SDNode *N : DeadNodeSet)
6033 DeadNodes.push_back(N);
6034 RemoveDeadNodes(DeadNodes);
6038 CSEMap.InsertNode(N, IP); // Memoize the new node.
6043 /// getMachineNode - These are used for target selectors to create a new node
6044 /// with specified return type(s), MachineInstr opcode, and operands.
6046 /// Note that getMachineNode returns the resultant node. If there is already a
6047 /// node of the specified opcode and operands, it returns that node instead of
6048 /// the current one.
6050 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
6051 SDVTList VTs = getVTList(VT);
6052 return getMachineNode(Opcode, dl, VTs, None);
6056 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6057 SDVTList VTs = getVTList(VT);
6058 SDValue Ops[] = { Op1 };
6059 return getMachineNode(Opcode, dl, VTs, Ops);
6063 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6064 SDValue Op1, SDValue Op2) {
6065 SDVTList VTs = getVTList(VT);
6066 SDValue Ops[] = { Op1, Op2 };
6067 return getMachineNode(Opcode, dl, VTs, Ops);
6071 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6072 SDValue Op1, SDValue Op2, SDValue Op3) {
6073 SDVTList VTs = getVTList(VT);
6074 SDValue Ops[] = { Op1, Op2, Op3 };
6075 return getMachineNode(Opcode, dl, VTs, Ops);
6079 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6080 ArrayRef<SDValue> Ops) {
6081 SDVTList VTs = getVTList(VT);
6082 return getMachineNode(Opcode, dl, VTs, Ops);
6086 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6087 SDVTList VTs = getVTList(VT1, VT2);
6088 return getMachineNode(Opcode, dl, VTs, None);
6092 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6093 EVT VT1, EVT VT2, SDValue Op1) {
6094 SDVTList VTs = getVTList(VT1, VT2);
6095 SDValue Ops[] = { Op1 };
6096 return getMachineNode(Opcode, dl, VTs, Ops);
6100 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6101 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6102 SDVTList VTs = getVTList(VT1, VT2);
6103 SDValue Ops[] = { Op1, Op2 };
6104 return getMachineNode(Opcode, dl, VTs, Ops);
6108 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6109 EVT VT1, EVT VT2, SDValue Op1,
6110 SDValue Op2, SDValue Op3) {
6111 SDVTList VTs = getVTList(VT1, VT2);
6112 SDValue Ops[] = { Op1, Op2, Op3 };
6113 return getMachineNode(Opcode, dl, VTs, Ops);
6117 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6119 ArrayRef<SDValue> Ops) {
6120 SDVTList VTs = getVTList(VT1, VT2);
6121 return getMachineNode(Opcode, dl, VTs, Ops);
6125 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6126 EVT VT1, EVT VT2, EVT VT3,
6127 SDValue Op1, SDValue Op2) {
6128 SDVTList VTs = getVTList(VT1, VT2, VT3);
6129 SDValue Ops[] = { Op1, Op2 };
6130 return getMachineNode(Opcode, dl, VTs, Ops);
6134 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6135 EVT VT1, EVT VT2, EVT VT3,
6136 SDValue Op1, SDValue Op2, SDValue Op3) {
6137 SDVTList VTs = getVTList(VT1, VT2, VT3);
6138 SDValue Ops[] = { Op1, Op2, Op3 };
6139 return getMachineNode(Opcode, dl, VTs, Ops);
6143 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6144 EVT VT1, EVT VT2, EVT VT3,
6145 ArrayRef<SDValue> Ops) {
6146 SDVTList VTs = getVTList(VT1, VT2, VT3);
6147 return getMachineNode(Opcode, dl, VTs, Ops);
6151 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6152 EVT VT2, EVT VT3, EVT VT4,
6153 ArrayRef<SDValue> Ops) {
6154 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6155 return getMachineNode(Opcode, dl, VTs, Ops);
6159 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6160 ArrayRef<EVT> ResultTys,
6161 ArrayRef<SDValue> Ops) {
6162 SDVTList VTs = getVTList(ResultTys);
6163 return getMachineNode(Opcode, dl, VTs, Ops);
6167 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6168 ArrayRef<SDValue> OpsArray) {
6169 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6172 const SDValue *Ops = OpsArray.data();
6173 unsigned NumOps = OpsArray.size();
6176 FoldingSetNodeID ID;
6177 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6179 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6180 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6184 // Allocate a new MachineSDNode.
6185 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6186 DL.getDebugLoc(), VTs);
6188 // Initialize the operands list.
6189 if (NumOps > array_lengthof(N->LocalOperands))
6190 // We're creating a final node that will live unmorphed for the
6191 // remainder of the current SelectionDAG iteration, so we can allocate
6192 // the operands directly out of a pool with no recycling metadata.
6193 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6196 N->InitOperands(N->LocalOperands, Ops, NumOps);
6197 N->OperandsNeedDelete = false;
6200 CSEMap.InsertNode(N, IP);
6206 /// getTargetExtractSubreg - A convenience function for creating
6207 /// TargetOpcode::EXTRACT_SUBREG nodes.
6209 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6211 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6212 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6213 VT, Operand, SRIdxVal);
6214 return SDValue(Subreg, 0);
6217 /// getTargetInsertSubreg - A convenience function for creating
6218 /// TargetOpcode::INSERT_SUBREG nodes.
6220 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6221 SDValue Operand, SDValue Subreg) {
6222 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6223 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6224 VT, Operand, Subreg, SRIdxVal);
6225 return SDValue(Result, 0);
6228 /// getNodeIfExists - Get the specified node if it's already available, or
6229 /// else return NULL.
6230 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6231 ArrayRef<SDValue> Ops,
6232 const SDNodeFlags *Flags) {
6233 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6234 FoldingSetNodeID ID;
6235 AddNodeIDNode(ID, Opcode, VTList, Ops);
6236 AddNodeIDFlags(ID, Opcode, Flags);
6238 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6244 /// getDbgValue - Creates a SDDbgValue node.
6247 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6248 unsigned R, bool IsIndirect, uint64_t Off,
6249 DebugLoc DL, unsigned O) {
6250 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6251 "Expected inlined-at fields to agree");
6252 return new (DbgInfo->getAlloc())
6253 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6257 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6258 const Value *C, uint64_t Off,
6259 DebugLoc DL, unsigned O) {
6260 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6261 "Expected inlined-at fields to agree");
6262 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6266 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6267 unsigned FI, uint64_t Off,
6268 DebugLoc DL, unsigned O) {
6269 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6270 "Expected inlined-at fields to agree");
6271 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6276 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6277 /// pointed to by a use iterator is deleted, increment the use iterator
6278 /// so that it doesn't dangle.
6280 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6281 SDNode::use_iterator &UI;
6282 SDNode::use_iterator &UE;
6284 void NodeDeleted(SDNode *N, SDNode *E) override {
6285 // Increment the iterator as needed.
6286 while (UI != UE && N == *UI)
6291 RAUWUpdateListener(SelectionDAG &d,
6292 SDNode::use_iterator &ui,
6293 SDNode::use_iterator &ue)
6294 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6299 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6300 /// This can cause recursive merging of nodes in the DAG.
6302 /// This version assumes From has a single result value.
6304 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6305 SDNode *From = FromN.getNode();
6306 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6307 "Cannot replace with this method!");
6308 assert(From != To.getNode() && "Cannot replace uses of with self");
6310 // Iterate over all the existing uses of From. New uses will be added
6311 // to the beginning of the use list, which we avoid visiting.
6312 // This specifically avoids visiting uses of From that arise while the
6313 // replacement is happening, because any such uses would be the result
6314 // of CSE: If an existing node looks like From after one of its operands
6315 // is replaced by To, we don't want to replace of all its users with To
6316 // too. See PR3018 for more info.
6317 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6318 RAUWUpdateListener Listener(*this, UI, UE);
6322 // This node is about to morph, remove its old self from the CSE maps.
6323 RemoveNodeFromCSEMaps(User);
6325 // A user can appear in a use list multiple times, and when this
6326 // happens the uses are usually next to each other in the list.
6327 // To help reduce the number of CSE recomputations, process all
6328 // the uses of this user that we can find this way.
6330 SDUse &Use = UI.getUse();
6333 } while (UI != UE && *UI == User);
6335 // Now that we have modified User, add it back to the CSE maps. If it
6336 // already exists there, recursively merge the results together.
6337 AddModifiedNodeToCSEMaps(User);
6340 // If we just RAUW'd the root, take note.
6341 if (FromN == getRoot())
6345 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6346 /// This can cause recursive merging of nodes in the DAG.
6348 /// This version assumes that for each value of From, there is a
6349 /// corresponding value in To in the same position with the same type.
6351 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6353 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6354 assert((!From->hasAnyUseOfValue(i) ||
6355 From->getValueType(i) == To->getValueType(i)) &&
6356 "Cannot use this version of ReplaceAllUsesWith!");
6359 // Handle the trivial case.
6363 // Iterate over just the existing users of From. See the comments in
6364 // the ReplaceAllUsesWith above.
6365 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6366 RAUWUpdateListener Listener(*this, UI, UE);
6370 // This node is about to morph, remove its old self from the CSE maps.
6371 RemoveNodeFromCSEMaps(User);
6373 // A user can appear in a use list multiple times, and when this
6374 // happens the uses are usually next to each other in the list.
6375 // To help reduce the number of CSE recomputations, process all
6376 // the uses of this user that we can find this way.
6378 SDUse &Use = UI.getUse();
6381 } while (UI != UE && *UI == User);
6383 // Now that we have modified User, add it back to the CSE maps. If it
6384 // already exists there, recursively merge the results together.
6385 AddModifiedNodeToCSEMaps(User);
6388 // If we just RAUW'd the root, take note.
6389 if (From == getRoot().getNode())
6390 setRoot(SDValue(To, getRoot().getResNo()));
6393 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6394 /// This can cause recursive merging of nodes in the DAG.
6396 /// This version can replace From with any result values. To must match the
6397 /// number and types of values returned by From.
6398 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6399 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6400 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6402 // Iterate over just the existing users of From. See the comments in
6403 // the ReplaceAllUsesWith above.
6404 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6405 RAUWUpdateListener Listener(*this, UI, UE);
6409 // This node is about to morph, remove its old self from the CSE maps.
6410 RemoveNodeFromCSEMaps(User);
6412 // A user can appear in a use list multiple times, and when this
6413 // happens the uses are usually next to each other in the list.
6414 // To help reduce the number of CSE recomputations, process all
6415 // the uses of this user that we can find this way.
6417 SDUse &Use = UI.getUse();
6418 const SDValue &ToOp = To[Use.getResNo()];
6421 } while (UI != UE && *UI == User);
6423 // Now that we have modified User, add it back to the CSE maps. If it
6424 // already exists there, recursively merge the results together.
6425 AddModifiedNodeToCSEMaps(User);
6428 // If we just RAUW'd the root, take note.
6429 if (From == getRoot().getNode())
6430 setRoot(SDValue(To[getRoot().getResNo()]));
6433 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6434 /// uses of other values produced by From.getNode() alone. The Deleted
6435 /// vector is handled the same way as for ReplaceAllUsesWith.
6436 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6437 // Handle the really simple, really trivial case efficiently.
6438 if (From == To) return;
6440 // Handle the simple, trivial, case efficiently.
6441 if (From.getNode()->getNumValues() == 1) {
6442 ReplaceAllUsesWith(From, To);
6446 // Iterate over just the existing users of From. See the comments in
6447 // the ReplaceAllUsesWith above.
6448 SDNode::use_iterator UI = From.getNode()->use_begin(),
6449 UE = From.getNode()->use_end();
6450 RAUWUpdateListener Listener(*this, UI, UE);
6453 bool UserRemovedFromCSEMaps = false;
6455 // A user can appear in a use list multiple times, and when this
6456 // happens the uses are usually next to each other in the list.
6457 // To help reduce the number of CSE recomputations, process all
6458 // the uses of this user that we can find this way.
6460 SDUse &Use = UI.getUse();
6462 // Skip uses of different values from the same node.
6463 if (Use.getResNo() != From.getResNo()) {
6468 // If this node hasn't been modified yet, it's still in the CSE maps,
6469 // so remove its old self from the CSE maps.
6470 if (!UserRemovedFromCSEMaps) {
6471 RemoveNodeFromCSEMaps(User);
6472 UserRemovedFromCSEMaps = true;
6477 } while (UI != UE && *UI == User);
6479 // We are iterating over all uses of the From node, so if a use
6480 // doesn't use the specific value, no changes are made.
6481 if (!UserRemovedFromCSEMaps)
6484 // Now that we have modified User, add it back to the CSE maps. If it
6485 // already exists there, recursively merge the results together.
6486 AddModifiedNodeToCSEMaps(User);
6489 // If we just RAUW'd the root, take note.
6490 if (From == getRoot())
6495 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6496 /// to record information about a use.
6503 /// operator< - Sort Memos by User.
6504 bool operator<(const UseMemo &L, const UseMemo &R) {
6505 return (intptr_t)L.User < (intptr_t)R.User;
6509 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6510 /// uses of other values produced by From.getNode() alone. The same value
6511 /// may appear in both the From and To list. The Deleted vector is
6512 /// handled the same way as for ReplaceAllUsesWith.
6513 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6516 // Handle the simple, trivial case efficiently.
6518 return ReplaceAllUsesOfValueWith(*From, *To);
6520 // Read up all the uses and make records of them. This helps
6521 // processing new uses that are introduced during the
6522 // replacement process.
6523 SmallVector<UseMemo, 4> Uses;
6524 for (unsigned i = 0; i != Num; ++i) {
6525 unsigned FromResNo = From[i].getResNo();
6526 SDNode *FromNode = From[i].getNode();
6527 for (SDNode::use_iterator UI = FromNode->use_begin(),
6528 E = FromNode->use_end(); UI != E; ++UI) {
6529 SDUse &Use = UI.getUse();
6530 if (Use.getResNo() == FromResNo) {
6531 UseMemo Memo = { *UI, i, &Use };
6532 Uses.push_back(Memo);
6537 // Sort the uses, so that all the uses from a given User are together.
6538 std::sort(Uses.begin(), Uses.end());
6540 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6541 UseIndex != UseIndexEnd; ) {
6542 // We know that this user uses some value of From. If it is the right
6543 // value, update it.
6544 SDNode *User = Uses[UseIndex].User;
6546 // This node is about to morph, remove its old self from the CSE maps.
6547 RemoveNodeFromCSEMaps(User);
6549 // The Uses array is sorted, so all the uses for a given User
6550 // are next to each other in the list.
6551 // To help reduce the number of CSE recomputations, process all
6552 // the uses of this user that we can find this way.
6554 unsigned i = Uses[UseIndex].Index;
6555 SDUse &Use = *Uses[UseIndex].Use;
6559 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6561 // Now that we have modified User, add it back to the CSE maps. If it
6562 // already exists there, recursively merge the results together.
6563 AddModifiedNodeToCSEMaps(User);
6567 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6568 /// based on their topological order. It returns the maximum id and a vector
6569 /// of the SDNodes* in assigned order by reference.
6570 unsigned SelectionDAG::AssignTopologicalOrder() {
6572 unsigned DAGSize = 0;
6574 // SortedPos tracks the progress of the algorithm. Nodes before it are
6575 // sorted, nodes after it are unsorted. When the algorithm completes
6576 // it is at the end of the list.
6577 allnodes_iterator SortedPos = allnodes_begin();
6579 // Visit all the nodes. Move nodes with no operands to the front of
6580 // the list immediately. Annotate nodes that do have operands with their
6581 // operand count. Before we do this, the Node Id fields of the nodes
6582 // may contain arbitrary values. After, the Node Id fields for nodes
6583 // before SortedPos will contain the topological sort index, and the
6584 // Node Id fields for nodes At SortedPos and after will contain the
6585 // count of outstanding operands.
6586 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6588 checkForCycles(N, this);
6589 unsigned Degree = N->getNumOperands();
6591 // A node with no uses, add it to the result array immediately.
6592 N->setNodeId(DAGSize++);
6593 allnodes_iterator Q(N);
6595 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6596 assert(SortedPos != AllNodes.end() && "Overran node list");
6599 // Temporarily use the Node Id as scratch space for the degree count.
6600 N->setNodeId(Degree);
6604 // Visit all the nodes. As we iterate, move nodes into sorted order,
6605 // such that by the time the end is reached all nodes will be sorted.
6606 for (SDNode &Node : allnodes()) {
6608 checkForCycles(N, this);
6609 // N is in sorted position, so all its uses have one less operand
6610 // that needs to be sorted.
6611 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6614 unsigned Degree = P->getNodeId();
6615 assert(Degree != 0 && "Invalid node degree");
6618 // All of P's operands are sorted, so P may sorted now.
6619 P->setNodeId(DAGSize++);
6621 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6622 assert(SortedPos != AllNodes.end() && "Overran node list");
6625 // Update P's outstanding operand count.
6626 P->setNodeId(Degree);
6629 if (&Node == SortedPos) {
6631 allnodes_iterator I(N);
6633 dbgs() << "Overran sorted position:\n";
6634 S->dumprFull(this); dbgs() << "\n";
6635 dbgs() << "Checking if this is due to cycles\n";
6636 checkForCycles(this, true);
6638 llvm_unreachable(nullptr);
6642 assert(SortedPos == AllNodes.end() &&
6643 "Topological sort incomplete!");
6644 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6645 "First node in topological sort is not the entry token!");
6646 assert(AllNodes.front().getNodeId() == 0 &&
6647 "First node in topological sort has non-zero id!");
6648 assert(AllNodes.front().getNumOperands() == 0 &&
6649 "First node in topological sort has operands!");
6650 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6651 "Last node in topologic sort has unexpected id!");
6652 assert(AllNodes.back().use_empty() &&
6653 "Last node in topologic sort has users!");
6654 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6658 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6659 /// value is produced by SD.
6660 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6662 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6663 SD->setHasDebugValue(true);
6665 DbgInfo->add(DB, SD, isParameter);
6668 /// TransferDbgValues - Transfer SDDbgValues.
6669 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6670 if (From == To || !From.getNode()->getHasDebugValue())
6672 SDNode *FromNode = From.getNode();
6673 SDNode *ToNode = To.getNode();
6674 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6675 SmallVector<SDDbgValue *, 2> ClonedDVs;
6676 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6678 SDDbgValue *Dbg = *I;
6679 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6681 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6682 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6683 Dbg->getDebugLoc(), Dbg->getOrder());
6684 ClonedDVs.push_back(Clone);
6687 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6688 E = ClonedDVs.end(); I != E; ++I)
6689 AddDbgValue(*I, ToNode, false);
6692 //===----------------------------------------------------------------------===//
6694 //===----------------------------------------------------------------------===//
6696 HandleSDNode::~HandleSDNode() {
6700 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6701 DebugLoc DL, const GlobalValue *GA,
6702 EVT VT, int64_t o, unsigned char TF)
6703 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6707 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6708 SDValue X, unsigned SrcAS,
6710 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6711 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6713 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6714 EVT memvt, MachineMemOperand *mmo)
6715 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6716 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6717 MMO->isNonTemporal(), MMO->isInvariant());
6718 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6719 assert(isNonTemporal() == MMO->isNonTemporal() &&
6720 "Non-temporal encoding error!");
6721 // We check here that the size of the memory operand fits within the size of
6722 // the MMO. This is because the MMO might indicate only a possible address
6723 // range instead of specifying the affected memory addresses precisely.
6724 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6727 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6728 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6729 : SDNode(Opc, Order, dl, VTs, Ops),
6730 MemoryVT(memvt), MMO(mmo) {
6731 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6732 MMO->isNonTemporal(), MMO->isInvariant());
6733 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6734 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6737 /// Profile - Gather unique data for the node.
6739 void SDNode::Profile(FoldingSetNodeID &ID) const {
6740 AddNodeIDNode(ID, this);
6745 std::vector<EVT> VTs;
6748 VTs.reserve(MVT::LAST_VALUETYPE);
6749 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6750 VTs.push_back(MVT((MVT::SimpleValueType)i));
6755 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6756 static ManagedStatic<EVTArray> SimpleVTArray;
6757 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6759 /// getValueTypeList - Return a pointer to the specified value type.
6761 const EVT *SDNode::getValueTypeList(EVT VT) {
6762 if (VT.isExtended()) {
6763 sys::SmartScopedLock<true> Lock(*VTMutex);
6764 return &(*EVTs->insert(VT).first);
6766 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6767 "Value type out of range!");
6768 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6772 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6773 /// indicated value. This method ignores uses of other values defined by this
6775 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6776 assert(Value < getNumValues() && "Bad value!");
6778 // TODO: Only iterate over uses of a given value of the node
6779 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6780 if (UI.getUse().getResNo() == Value) {
6787 // Found exactly the right number of uses?
6792 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6793 /// value. This method ignores uses of other values defined by this operation.
6794 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6795 assert(Value < getNumValues() && "Bad value!");
6797 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6798 if (UI.getUse().getResNo() == Value)
6805 /// isOnlyUserOf - Return true if this node is the only use of N.
6807 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6809 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6820 /// isOperand - Return true if this node is an operand of N.
6822 bool SDValue::isOperandOf(const SDNode *N) const {
6823 for (const SDValue &Op : N->op_values())
6829 bool SDNode::isOperandOf(const SDNode *N) const {
6830 for (const SDValue &Op : N->op_values())
6831 if (this == Op.getNode())
6836 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6837 /// be a chain) reaches the specified operand without crossing any
6838 /// side-effecting instructions on any chain path. In practice, this looks
6839 /// through token factors and non-volatile loads. In order to remain efficient,
6840 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6841 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6842 unsigned Depth) const {
6843 if (*this == Dest) return true;
6845 // Don't search too deeply, we just want to be able to see through
6846 // TokenFactor's etc.
6847 if (Depth == 0) return false;
6849 // If this is a token factor, all inputs to the TF happen in parallel. If any
6850 // of the operands of the TF does not reach dest, then we cannot do the xform.
6851 if (getOpcode() == ISD::TokenFactor) {
6852 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6853 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6858 // Loads don't have side effects, look through them.
6859 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6860 if (!Ld->isVolatile())
6861 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6866 /// hasPredecessor - Return true if N is a predecessor of this node.
6867 /// N is either an operand of this node, or can be reached by recursively
6868 /// traversing up the operands.
6869 /// NOTE: This is an expensive method. Use it carefully.
6870 bool SDNode::hasPredecessor(const SDNode *N) const {
6871 SmallPtrSet<const SDNode *, 32> Visited;
6872 SmallVector<const SDNode *, 16> Worklist;
6873 return hasPredecessorHelper(N, Visited, Worklist);
6877 SDNode::hasPredecessorHelper(const SDNode *N,
6878 SmallPtrSetImpl<const SDNode *> &Visited,
6879 SmallVectorImpl<const SDNode *> &Worklist) const {
6880 if (Visited.empty()) {
6881 Worklist.push_back(this);
6883 // Take a look in the visited set. If we've already encountered this node
6884 // we needn't search further.
6885 if (Visited.count(N))
6889 // Haven't visited N yet. Continue the search.
6890 while (!Worklist.empty()) {
6891 const SDNode *M = Worklist.pop_back_val();
6892 for (const SDValue &OpV : M->op_values()) {
6893 SDNode *Op = OpV.getNode();
6894 if (Visited.insert(Op).second)
6895 Worklist.push_back(Op);
6904 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6905 assert(Num < NumOperands && "Invalid child # of SDNode!");
6906 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6909 const SDNodeFlags *SDNode::getFlags() const {
6910 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6911 return &FlagsNode->Flags;
6915 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6916 assert(N->getNumValues() == 1 &&
6917 "Can't unroll a vector with multiple results!");
6919 EVT VT = N->getValueType(0);
6920 unsigned NE = VT.getVectorNumElements();
6921 EVT EltVT = VT.getVectorElementType();
6924 SmallVector<SDValue, 8> Scalars;
6925 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6927 // If ResNE is 0, fully unroll the vector op.
6930 else if (NE > ResNE)
6934 for (i= 0; i != NE; ++i) {
6935 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6936 SDValue Operand = N->getOperand(j);
6937 EVT OperandVT = Operand.getValueType();
6938 if (OperandVT.isVector()) {
6939 // A vector operand; extract a single element.
6940 EVT OperandEltVT = OperandVT.getVectorElementType();
6942 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6943 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6945 // A scalar operand; just use it as is.
6946 Operands[j] = Operand;
6950 switch (N->getOpcode()) {
6952 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6957 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6964 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6965 getShiftAmountOperand(Operands[0].getValueType(),
6968 case ISD::SIGN_EXTEND_INREG:
6969 case ISD::FP_ROUND_INREG: {
6970 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6971 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6973 getValueType(ExtVT)));
6978 for (; i < ResNE; ++i)
6979 Scalars.push_back(getUNDEF(EltVT));
6981 return getNode(ISD::BUILD_VECTOR, dl,
6982 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6986 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6987 /// location that is 'Dist' units away from the location that the 'Base' load
6988 /// is loading from.
6989 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6990 unsigned Bytes, int Dist) const {
6991 if (LD->getChain() != Base->getChain())
6993 EVT VT = LD->getValueType(0);
6994 if (VT.getSizeInBits() / 8 != Bytes)
6997 SDValue Loc = LD->getOperand(1);
6998 SDValue BaseLoc = Base->getOperand(1);
6999 if (Loc.getOpcode() == ISD::FrameIndex) {
7000 if (BaseLoc.getOpcode() != ISD::FrameIndex)
7002 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
7003 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
7004 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
7005 int FS = MFI->getObjectSize(FI);
7006 int BFS = MFI->getObjectSize(BFI);
7007 if (FS != BFS || FS != (int)Bytes) return false;
7008 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
7012 if (isBaseWithConstantOffset(Loc)) {
7013 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
7014 if (Loc.getOperand(0) == BaseLoc) {
7015 // If the base location is a simple address with no offset itself, then
7016 // the second load's first add operand should be the base address.
7017 if (LocOffset == Dist * (int)Bytes)
7019 } else if (isBaseWithConstantOffset(BaseLoc)) {
7020 // The base location itself has an offset, so subtract that value from the
7021 // second load's offset before comparing to distance * size.
7023 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
7024 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
7025 if ((LocOffset - BOffset) == Dist * (int)Bytes)
7030 const GlobalValue *GV1 = nullptr;
7031 const GlobalValue *GV2 = nullptr;
7032 int64_t Offset1 = 0;
7033 int64_t Offset2 = 0;
7034 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
7035 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
7036 if (isGA1 && isGA2 && GV1 == GV2)
7037 return Offset1 == (Offset2 + Dist*Bytes);
7042 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
7043 /// it cannot be inferred.
7044 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
7045 // If this is a GlobalAddress + cst, return the alignment.
7046 const GlobalValue *GV;
7047 int64_t GVOffset = 0;
7048 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
7049 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
7050 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
7051 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7053 unsigned AlignBits = KnownZero.countTrailingOnes();
7054 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7056 return MinAlign(Align, GVOffset);
7059 // If this is a direct reference to a stack slot, use information about the
7060 // stack slot's alignment.
7061 int FrameIdx = 1 << 31;
7062 int64_t FrameOffset = 0;
7063 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7064 FrameIdx = FI->getIndex();
7065 } else if (isBaseWithConstantOffset(Ptr) &&
7066 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7068 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7069 FrameOffset = Ptr.getConstantOperandVal(1);
7072 if (FrameIdx != (1 << 31)) {
7073 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7074 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7082 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7083 /// which is split (or expanded) into two not necessarily identical pieces.
7084 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7085 // Currently all types are split in half.
7087 if (!VT.isVector()) {
7088 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7090 unsigned NumElements = VT.getVectorNumElements();
7091 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7092 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7095 return std::make_pair(LoVT, HiVT);
7098 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7100 std::pair<SDValue, SDValue>
7101 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7103 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7104 N.getValueType().getVectorNumElements() &&
7105 "More vector elements requested than available!");
7107 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7108 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7109 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7110 getConstant(LoVT.getVectorNumElements(), DL,
7111 TLI->getVectorIdxTy(getDataLayout())));
7112 return std::make_pair(Lo, Hi);
7115 void SelectionDAG::ExtractVectorElements(SDValue Op,
7116 SmallVectorImpl<SDValue> &Args,
7117 unsigned Start, unsigned Count) {
7118 EVT VT = Op.getValueType();
7120 Count = VT.getVectorNumElements();
7122 EVT EltVT = VT.getVectorElementType();
7123 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7125 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7126 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7127 Op, getConstant(i, SL, IdxTy)));
7131 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7132 unsigned GlobalAddressSDNode::getAddressSpace() const {
7133 return getGlobal()->getType()->getAddressSpace();
7137 Type *ConstantPoolSDNode::getType() const {
7138 if (isMachineConstantPoolEntry())
7139 return Val.MachineCPVal->getType();
7140 return Val.ConstVal->getType();
7143 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7145 unsigned &SplatBitSize,
7147 unsigned MinSplatBits,
7148 bool isBigEndian) const {
7149 EVT VT = getValueType(0);
7150 assert(VT.isVector() && "Expected a vector type");
7151 unsigned sz = VT.getSizeInBits();
7152 if (MinSplatBits > sz)
7155 SplatValue = APInt(sz, 0);
7156 SplatUndef = APInt(sz, 0);
7158 // Get the bits. Bits with undefined values (when the corresponding element
7159 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7160 // in SplatValue. If any of the values are not constant, give up and return
7162 unsigned int nOps = getNumOperands();
7163 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7164 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7166 for (unsigned j = 0; j < nOps; ++j) {
7167 unsigned i = isBigEndian ? nOps-1-j : j;
7168 SDValue OpVal = getOperand(i);
7169 unsigned BitPos = j * EltBitSize;
7171 if (OpVal.getOpcode() == ISD::UNDEF)
7172 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7173 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7174 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7175 zextOrTrunc(sz) << BitPos;
7176 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7177 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7182 // The build_vector is all constants or undefs. Find the smallest element
7183 // size that splats the vector.
7185 HasAnyUndefs = (SplatUndef != 0);
7188 unsigned HalfSize = sz / 2;
7189 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7190 APInt LowValue = SplatValue.trunc(HalfSize);
7191 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7192 APInt LowUndef = SplatUndef.trunc(HalfSize);
7194 // If the two halves do not match (ignoring undef bits), stop here.
7195 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7196 MinSplatBits > HalfSize)
7199 SplatValue = HighValue | LowValue;
7200 SplatUndef = HighUndef & LowUndef;
7209 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7210 if (UndefElements) {
7211 UndefElements->clear();
7212 UndefElements->resize(getNumOperands());
7215 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7216 SDValue Op = getOperand(i);
7217 if (Op.getOpcode() == ISD::UNDEF) {
7219 (*UndefElements)[i] = true;
7220 } else if (!Splatted) {
7222 } else if (Splatted != Op) {
7228 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7229 "Can only have a splat without a constant for all undefs.");
7230 return getOperand(0);
7237 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7238 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7242 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7243 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7247 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7248 uint32_t BitWidth) const {
7249 if (ConstantFPSDNode *CN =
7250 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7252 APSInt IntVal(BitWidth);
7253 APFloat APF = CN->getValueAPF();
7254 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7259 return IntVal.exactLogBase2();
7264 bool BuildVectorSDNode::isConstant() const {
7265 for (const SDValue &Op : op_values()) {
7266 unsigned Opc = Op.getOpcode();
7267 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7273 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7274 // Find the first non-undef value in the shuffle mask.
7276 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7279 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7281 // Make sure all remaining elements are either undef or the same as the first
7283 for (int Idx = Mask[i]; i != e; ++i)
7284 if (Mask[i] >= 0 && Mask[i] != Idx)
7290 static void checkForCyclesHelper(const SDNode *N,
7291 SmallPtrSetImpl<const SDNode*> &Visited,
7292 SmallPtrSetImpl<const SDNode*> &Checked,
7293 const llvm::SelectionDAG *DAG) {
7294 // If this node has already been checked, don't check it again.
7295 if (Checked.count(N))
7298 // If a node has already been visited on this depth-first walk, reject it as
7300 if (!Visited.insert(N).second) {
7301 errs() << "Detected cycle in SelectionDAG\n";
7302 dbgs() << "Offending node:\n";
7303 N->dumprFull(DAG); dbgs() << "\n";
7307 for (const SDValue &Op : N->op_values())
7308 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7315 void llvm::checkForCycles(const llvm::SDNode *N,
7316 const llvm::SelectionDAG *DAG,
7324 assert(N && "Checking nonexistent SDNode");
7325 SmallPtrSet<const SDNode*, 32> visited;
7326 SmallPtrSet<const SDNode*, 32> checked;
7327 checkForCyclesHelper(N, visited, checked, DAG);
7332 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7333 checkForCycles(DAG->getRoot().getNode(), DAG, force);