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.begin());
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 EVT SVT = VT.getScalarType();
3014 EVT InVT = BV->getValueType(0);
3015 EVT InSVT = InVT.getScalarType();
3017 // Find legal integer scalar type for constant promotion and
3018 // ensure that its scalar size is at least as large as source.
3020 if (SVT.isInteger()) {
3021 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3022 if (LegalSVT.bitsLT(SVT)) break;
3025 // Let the above scalar folding handle the folding of each element.
3026 SmallVector<SDValue, 8> Ops;
3027 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3028 SDValue OpN = BV->getOperand(i);
3029 EVT OpVT = OpN.getValueType();
3031 // Build vector (integer) scalar operands may need implicit
3032 // truncation - do this before constant folding.
3033 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
3034 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
3036 OpN = getNode(Opcode, DL, SVT, OpN);
3038 // Legalize the (integer) scalar constant if necessary.
3039 if (LegalSVT != SVT)
3040 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
3042 if (OpN.getOpcode() != ISD::UNDEF &&
3043 OpN.getOpcode() != ISD::Constant &&
3044 OpN.getOpcode() != ISD::ConstantFP)
3048 if (Ops.size() == VT.getVectorNumElements())
3049 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3056 unsigned OpOpcode = Operand.getNode()->getOpcode();
3058 case ISD::TokenFactor:
3059 case ISD::MERGE_VALUES:
3060 case ISD::CONCAT_VECTORS:
3061 return Operand; // Factor, merge or concat of one node? No need.
3062 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3063 case ISD::FP_EXTEND:
3064 assert(VT.isFloatingPoint() &&
3065 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3066 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3067 assert((!VT.isVector() ||
3068 VT.getVectorNumElements() ==
3069 Operand.getValueType().getVectorNumElements()) &&
3070 "Vector element count mismatch!");
3071 assert(Operand.getValueType().bitsLT(VT) &&
3072 "Invalid fpext node, dst < src!");
3073 if (Operand.getOpcode() == ISD::UNDEF)
3074 return getUNDEF(VT);
3076 case ISD::SIGN_EXTEND:
3077 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3078 "Invalid SIGN_EXTEND!");
3079 if (Operand.getValueType() == VT) return Operand; // noop extension
3080 assert((!VT.isVector() ||
3081 VT.getVectorNumElements() ==
3082 Operand.getValueType().getVectorNumElements()) &&
3083 "Vector element count mismatch!");
3084 assert(Operand.getValueType().bitsLT(VT) &&
3085 "Invalid sext node, dst < src!");
3086 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3087 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3088 else if (OpOpcode == ISD::UNDEF)
3089 // sext(undef) = 0, because the top bits will all be the same.
3090 return getConstant(0, DL, VT);
3092 case ISD::ZERO_EXTEND:
3093 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3094 "Invalid ZERO_EXTEND!");
3095 if (Operand.getValueType() == VT) return Operand; // noop extension
3096 assert((!VT.isVector() ||
3097 VT.getVectorNumElements() ==
3098 Operand.getValueType().getVectorNumElements()) &&
3099 "Vector element count mismatch!");
3100 assert(Operand.getValueType().bitsLT(VT) &&
3101 "Invalid zext node, dst < src!");
3102 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3103 return getNode(ISD::ZERO_EXTEND, DL, VT,
3104 Operand.getNode()->getOperand(0));
3105 else if (OpOpcode == ISD::UNDEF)
3106 // zext(undef) = 0, because the top bits will be zero.
3107 return getConstant(0, DL, VT);
3109 case ISD::ANY_EXTEND:
3110 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3111 "Invalid ANY_EXTEND!");
3112 if (Operand.getValueType() == VT) return Operand; // noop extension
3113 assert((!VT.isVector() ||
3114 VT.getVectorNumElements() ==
3115 Operand.getValueType().getVectorNumElements()) &&
3116 "Vector element count mismatch!");
3117 assert(Operand.getValueType().bitsLT(VT) &&
3118 "Invalid anyext node, dst < src!");
3120 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3121 OpOpcode == ISD::ANY_EXTEND)
3122 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3123 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3124 else if (OpOpcode == ISD::UNDEF)
3125 return getUNDEF(VT);
3127 // (ext (trunx x)) -> x
3128 if (OpOpcode == ISD::TRUNCATE) {
3129 SDValue OpOp = Operand.getNode()->getOperand(0);
3130 if (OpOp.getValueType() == VT)
3135 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3136 "Invalid TRUNCATE!");
3137 if (Operand.getValueType() == VT) return Operand; // noop truncate
3138 assert((!VT.isVector() ||
3139 VT.getVectorNumElements() ==
3140 Operand.getValueType().getVectorNumElements()) &&
3141 "Vector element count mismatch!");
3142 assert(Operand.getValueType().bitsGT(VT) &&
3143 "Invalid truncate node, src < dst!");
3144 if (OpOpcode == ISD::TRUNCATE)
3145 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3146 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3147 OpOpcode == ISD::ANY_EXTEND) {
3148 // If the source is smaller than the dest, we still need an extend.
3149 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3150 .bitsLT(VT.getScalarType()))
3151 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3152 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3153 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3154 return Operand.getNode()->getOperand(0);
3156 if (OpOpcode == ISD::UNDEF)
3157 return getUNDEF(VT);
3160 assert(VT.isInteger() && VT == Operand.getValueType() &&
3162 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3163 "BSWAP types must be a multiple of 16 bits!");
3164 if (OpOpcode == ISD::UNDEF)
3165 return getUNDEF(VT);
3168 // Basic sanity checking.
3169 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3170 && "Cannot BITCAST between types of different sizes!");
3171 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3172 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3173 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3174 if (OpOpcode == ISD::UNDEF)
3175 return getUNDEF(VT);
3177 case ISD::SCALAR_TO_VECTOR:
3178 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3179 (VT.getVectorElementType() == Operand.getValueType() ||
3180 (VT.getVectorElementType().isInteger() &&
3181 Operand.getValueType().isInteger() &&
3182 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3183 "Illegal SCALAR_TO_VECTOR node!");
3184 if (OpOpcode == ISD::UNDEF)
3185 return getUNDEF(VT);
3186 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3187 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3188 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3189 Operand.getConstantOperandVal(1) == 0 &&
3190 Operand.getOperand(0).getValueType() == VT)
3191 return Operand.getOperand(0);
3194 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3195 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3196 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3197 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3198 Operand.getNode()->getOperand(0),
3199 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3200 if (OpOpcode == ISD::FNEG) // --X -> X
3201 return Operand.getNode()->getOperand(0);
3204 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3205 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3210 SDVTList VTs = getVTList(VT);
3211 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3212 FoldingSetNodeID ID;
3213 SDValue Ops[1] = { Operand };
3214 AddNodeIDNode(ID, Opcode, VTs, Ops);
3216 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3217 return SDValue(E, 0);
3219 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3220 DL.getDebugLoc(), VTs, Operand);
3221 CSEMap.InsertNode(N, IP);
3223 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3224 DL.getDebugLoc(), VTs, Operand);
3228 return SDValue(N, 0);
3231 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3234 case ISD::ADD: return std::make_pair(C1 + C2, true);
3235 case ISD::SUB: return std::make_pair(C1 - C2, true);
3236 case ISD::MUL: return std::make_pair(C1 * C2, true);
3237 case ISD::AND: return std::make_pair(C1 & C2, true);
3238 case ISD::OR: return std::make_pair(C1 | C2, true);
3239 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3240 case ISD::SHL: return std::make_pair(C1 << C2, true);
3241 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3242 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3243 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3244 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3245 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3246 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3247 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3248 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3250 if (!C2.getBoolValue())
3252 return std::make_pair(C1.udiv(C2), true);
3254 if (!C2.getBoolValue())
3256 return std::make_pair(C1.urem(C2), true);
3258 if (!C2.getBoolValue())
3260 return std::make_pair(C1.sdiv(C2), true);
3262 if (!C2.getBoolValue())
3264 return std::make_pair(C1.srem(C2), true);
3266 return std::make_pair(APInt(1, 0), false);
3269 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3270 const ConstantSDNode *Cst1,
3271 const ConstantSDNode *Cst2) {
3272 if (Cst1->isOpaque() || Cst2->isOpaque())
3275 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3276 Cst2->getAPIntValue());
3279 return getConstant(Folded.first, DL, VT);
3282 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3283 SDNode *Cst1, SDNode *Cst2) {
3284 // If the opcode is a target-specific ISD node, there's nothing we can
3285 // do here and the operand rules may not line up with the below, so
3287 if (Opcode >= ISD::BUILTIN_OP_END)
3290 // Handle the case of two scalars.
3291 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3292 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3293 if (SDValue Folded =
3294 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3297 SmallVector<SDValue, 4> Outputs;
3298 // We may have a vector type but a scalar result. Create a splat.
3299 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3300 // Build a big vector out of the scalar elements we generated.
3301 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3308 // For vectors extract each constant element into Inputs so we can constant
3309 // fold them individually.
3310 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3311 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3315 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3317 EVT SVT = VT.getScalarType();
3318 SmallVector<SDValue, 4> Outputs;
3319 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3320 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3321 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3322 if (!V1 || !V2) // Not a constant, bail.
3325 if (V1->isOpaque() || V2->isOpaque())
3328 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3329 // FIXME: This is valid and could be handled by truncating the APInts.
3330 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3333 // Fold one vector element.
3334 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3335 V2->getAPIntValue());
3338 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3341 assert(VT.getVectorNumElements() == Outputs.size() &&
3342 "Vector size mismatch!");
3344 // We may have a vector type but a scalar result. Create a splat.
3345 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3347 // Build a big vector out of the scalar elements we generated.
3348 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3351 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3352 SDValue N2, const SDNodeFlags *Flags) {
3353 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3354 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3356 // Canonicalize constant to RHS if commutative.
3357 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3358 std::swap(N1C, N2C);
3364 case ISD::TokenFactor:
3365 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3366 N2.getValueType() == MVT::Other && "Invalid token factor!");
3367 // Fold trivial token factors.
3368 if (N1.getOpcode() == ISD::EntryToken) return N2;
3369 if (N2.getOpcode() == ISD::EntryToken) return N1;
3370 if (N1 == N2) return N1;
3372 case ISD::CONCAT_VECTORS:
3373 // Concat of UNDEFs is UNDEF.
3374 if (N1.getOpcode() == ISD::UNDEF &&
3375 N2.getOpcode() == ISD::UNDEF)
3376 return getUNDEF(VT);
3378 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3379 // one big BUILD_VECTOR.
3380 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3381 N2.getOpcode() == ISD::BUILD_VECTOR) {
3382 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3383 N1.getNode()->op_end());
3384 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3386 // BUILD_VECTOR requires all inputs to be of the same type, find the
3387 // maximum type and extend them all.
3388 EVT SVT = VT.getScalarType();
3389 for (SDValue Op : Elts)
3390 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3391 if (SVT.bitsGT(VT.getScalarType()))
3392 for (SDValue &Op : Elts)
3393 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3394 ? getZExtOrTrunc(Op, DL, SVT)
3395 : getSExtOrTrunc(Op, DL, SVT);
3397 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3401 assert(VT.isInteger() && "This operator does not apply to FP types!");
3402 assert(N1.getValueType() == N2.getValueType() &&
3403 N1.getValueType() == VT && "Binary operator types must match!");
3404 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3405 // worth handling here.
3406 if (N2C && N2C->isNullValue())
3408 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3415 assert(VT.isInteger() && "This operator does not apply to FP types!");
3416 assert(N1.getValueType() == N2.getValueType() &&
3417 N1.getValueType() == VT && "Binary operator types must match!");
3418 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3419 // it's worth handling here.
3420 if (N2C && N2C->isNullValue())
3434 assert(VT.isInteger() && "This operator does not apply to FP types!");
3435 assert(N1.getValueType() == N2.getValueType() &&
3436 N1.getValueType() == VT && "Binary operator types must match!");
3443 if (getTarget().Options.UnsafeFPMath) {
3444 if (Opcode == ISD::FADD) {
3446 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3447 if (CFP->getValueAPF().isZero())
3450 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3451 if (CFP->getValueAPF().isZero())
3453 } else if (Opcode == ISD::FSUB) {
3455 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3456 if (CFP->getValueAPF().isZero())
3458 } else if (Opcode == ISD::FMUL) {
3459 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3462 // If the first operand isn't the constant, try the second
3464 CFP = dyn_cast<ConstantFPSDNode>(N2);
3471 return SDValue(CFP,0);
3473 if (CFP->isExactlyValue(1.0))
3478 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3479 assert(N1.getValueType() == N2.getValueType() &&
3480 N1.getValueType() == VT && "Binary operator types must match!");
3482 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3483 assert(N1.getValueType() == VT &&
3484 N1.getValueType().isFloatingPoint() &&
3485 N2.getValueType().isFloatingPoint() &&
3486 "Invalid FCOPYSIGN!");
3493 assert(VT == N1.getValueType() &&
3494 "Shift operators return type must be the same as their first arg");
3495 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3496 "Shifts only work on integers");
3497 assert((!VT.isVector() || VT == N2.getValueType()) &&
3498 "Vector shift amounts must be in the same as their first arg");
3499 // Verify that the shift amount VT is bit enough to hold valid shift
3500 // amounts. This catches things like trying to shift an i1024 value by an
3501 // i8, which is easy to fall into in generic code that uses
3502 // TLI.getShiftAmount().
3503 assert(N2.getValueType().getSizeInBits() >=
3504 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3505 "Invalid use of small shift amount with oversized value!");
3507 // Always fold shifts of i1 values so the code generator doesn't need to
3508 // handle them. Since we know the size of the shift has to be less than the
3509 // size of the value, the shift/rotate count is guaranteed to be zero.
3512 if (N2C && N2C->isNullValue())
3515 case ISD::FP_ROUND_INREG: {
3516 EVT EVT = cast<VTSDNode>(N2)->getVT();
3517 assert(VT == N1.getValueType() && "Not an inreg round!");
3518 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3519 "Cannot FP_ROUND_INREG integer types");
3520 assert(EVT.isVector() == VT.isVector() &&
3521 "FP_ROUND_INREG type should be vector iff the operand "
3523 assert((!EVT.isVector() ||
3524 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3525 "Vector element counts must match in FP_ROUND_INREG");
3526 assert(EVT.bitsLE(VT) && "Not rounding down!");
3528 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3532 assert(VT.isFloatingPoint() &&
3533 N1.getValueType().isFloatingPoint() &&
3534 VT.bitsLE(N1.getValueType()) &&
3535 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3536 if (N1.getValueType() == VT) return N1; // noop conversion.
3538 case ISD::AssertSext:
3539 case ISD::AssertZext: {
3540 EVT EVT = cast<VTSDNode>(N2)->getVT();
3541 assert(VT == N1.getValueType() && "Not an inreg extend!");
3542 assert(VT.isInteger() && EVT.isInteger() &&
3543 "Cannot *_EXTEND_INREG FP types");
3544 assert(!EVT.isVector() &&
3545 "AssertSExt/AssertZExt type should be the vector element type "
3546 "rather than the vector type!");
3547 assert(EVT.bitsLE(VT) && "Not extending!");
3548 if (VT == EVT) return N1; // noop assertion.
3551 case ISD::SIGN_EXTEND_INREG: {
3552 EVT EVT = cast<VTSDNode>(N2)->getVT();
3553 assert(VT == N1.getValueType() && "Not an inreg extend!");
3554 assert(VT.isInteger() && EVT.isInteger() &&
3555 "Cannot *_EXTEND_INREG FP types");
3556 assert(EVT.isVector() == VT.isVector() &&
3557 "SIGN_EXTEND_INREG type should be vector iff the operand "
3559 assert((!EVT.isVector() ||
3560 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3561 "Vector element counts must match in SIGN_EXTEND_INREG");
3562 assert(EVT.bitsLE(VT) && "Not extending!");
3563 if (EVT == VT) return N1; // Not actually extending
3565 auto SignExtendInReg = [&](APInt Val) {
3566 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3567 Val <<= Val.getBitWidth() - FromBits;
3568 Val = Val.ashr(Val.getBitWidth() - FromBits);
3569 return getConstant(Val, DL, VT.getScalarType());
3573 APInt Val = N1C->getAPIntValue();
3574 return SignExtendInReg(Val);
3576 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3577 SmallVector<SDValue, 8> Ops;
3578 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3579 SDValue Op = N1.getOperand(i);
3580 if (Op.getOpcode() == ISD::UNDEF) {
3581 Ops.push_back(getUNDEF(VT.getScalarType()));
3584 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3585 APInt Val = C->getAPIntValue();
3586 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3587 Ops.push_back(SignExtendInReg(Val));
3592 if (Ops.size() == VT.getVectorNumElements())
3593 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3597 case ISD::EXTRACT_VECTOR_ELT:
3598 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3599 if (N1.getOpcode() == ISD::UNDEF)
3600 return getUNDEF(VT);
3602 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3603 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3604 return getUNDEF(VT);
3606 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3607 // expanding copies of large vectors from registers.
3609 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3610 N1.getNumOperands() > 0) {
3612 N1.getOperand(0).getValueType().getVectorNumElements();
3613 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3614 N1.getOperand(N2C->getZExtValue() / Factor),
3615 getConstant(N2C->getZExtValue() % Factor, DL,
3616 N2.getValueType()));
3619 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3620 // expanding large vector constants.
3621 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3622 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3624 if (VT != Elt.getValueType())
3625 // If the vector element type is not legal, the BUILD_VECTOR operands
3626 // are promoted and implicitly truncated, and the result implicitly
3627 // extended. Make that explicit here.
3628 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3633 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3634 // operations are lowered to scalars.
3635 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3636 // If the indices are the same, return the inserted element else
3637 // if the indices are known different, extract the element from
3638 // the original vector.
3639 SDValue N1Op2 = N1.getOperand(2);
3640 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3642 if (N1Op2C && N2C) {
3643 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3644 if (VT == N1.getOperand(1).getValueType())
3645 return N1.getOperand(1);
3647 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3650 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3654 case ISD::EXTRACT_ELEMENT:
3655 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3656 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3657 (N1.getValueType().isInteger() == VT.isInteger()) &&
3658 N1.getValueType() != VT &&
3659 "Wrong types for EXTRACT_ELEMENT!");
3661 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3662 // 64-bit integers into 32-bit parts. Instead of building the extract of
3663 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3664 if (N1.getOpcode() == ISD::BUILD_PAIR)
3665 return N1.getOperand(N2C->getZExtValue());
3667 // EXTRACT_ELEMENT of a constant int is also very common.
3668 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3669 unsigned ElementSize = VT.getSizeInBits();
3670 unsigned Shift = ElementSize * N2C->getZExtValue();
3671 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3672 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3675 case ISD::EXTRACT_SUBVECTOR: {
3677 if (VT.isSimple() && N1.getValueType().isSimple()) {
3678 assert(VT.isVector() && N1.getValueType().isVector() &&
3679 "Extract subvector VTs must be a vectors!");
3680 assert(VT.getVectorElementType() ==
3681 N1.getValueType().getVectorElementType() &&
3682 "Extract subvector VTs must have the same element type!");
3683 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3684 "Extract subvector must be from larger vector to smaller vector!");
3686 if (isa<ConstantSDNode>(Index)) {
3687 assert((VT.getVectorNumElements() +
3688 cast<ConstantSDNode>(Index)->getZExtValue()
3689 <= N1.getValueType().getVectorNumElements())
3690 && "Extract subvector overflow!");
3693 // Trivial extraction.
3694 if (VT.getSimpleVT() == N1.getSimpleValueType())
3701 // Perform trivial constant folding.
3703 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3706 // Constant fold FP operations.
3707 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3708 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3709 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3711 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3712 // Canonicalize constant to RHS if commutative.
3713 std::swap(N1CFP, N2CFP);
3716 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3717 APFloat::opStatus s;
3720 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3721 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3722 return getConstantFP(V1, DL, VT);
3725 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3726 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3727 return getConstantFP(V1, DL, VT);
3730 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3731 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3732 return getConstantFP(V1, DL, VT);
3735 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3736 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3737 s!=APFloat::opDivByZero)) {
3738 return getConstantFP(V1, DL, VT);
3743 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3744 s!=APFloat::opDivByZero)) {
3745 return getConstantFP(V1, DL, VT);
3748 case ISD::FCOPYSIGN:
3750 return getConstantFP(V1, DL, VT);
3755 if (Opcode == ISD::FP_ROUND) {
3756 APFloat V = N1CFP->getValueAPF(); // make copy
3758 // This can return overflow, underflow, or inexact; we don't care.
3759 // FIXME need to be more flexible about rounding mode.
3760 (void)V.convert(EVTToAPFloatSemantics(VT),
3761 APFloat::rmNearestTiesToEven, &ignored);
3762 return getConstantFP(V, DL, VT);
3766 // Canonicalize an UNDEF to the RHS, even over a constant.
3767 if (N1.getOpcode() == ISD::UNDEF) {
3768 if (isCommutativeBinOp(Opcode)) {
3772 case ISD::FP_ROUND_INREG:
3773 case ISD::SIGN_EXTEND_INREG:
3779 return N1; // fold op(undef, arg2) -> undef
3787 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3788 // For vectors, we can't easily build an all zero vector, just return
3795 // Fold a bunch of operators when the RHS is undef.
3796 if (N2.getOpcode() == ISD::UNDEF) {
3799 if (N1.getOpcode() == ISD::UNDEF)
3800 // Handle undef ^ undef -> 0 special case. This is a common
3802 return getConstant(0, DL, VT);
3812 return N2; // fold op(arg1, undef) -> undef
3818 if (getTarget().Options.UnsafeFPMath)
3826 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3827 // For vectors, we can't easily build an all zero vector, just return
3832 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3833 // For vectors, we can't easily build an all one vector, just return
3841 // Memoize this node if possible.
3843 SDVTList VTs = getVTList(VT);
3844 if (VT != MVT::Glue) {
3845 SDValue Ops[] = {N1, N2};
3846 FoldingSetNodeID ID;
3847 AddNodeIDNode(ID, Opcode, VTs, Ops);
3848 AddNodeIDFlags(ID, Opcode, Flags);
3850 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3851 return SDValue(E, 0);
3853 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3855 CSEMap.InsertNode(N, IP);
3857 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3861 return SDValue(N, 0);
3864 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3865 SDValue N1, SDValue N2, SDValue N3) {
3866 // Perform various simplifications.
3867 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3870 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3871 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3872 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3873 if (N1CFP && N2CFP && N3CFP) {
3874 APFloat V1 = N1CFP->getValueAPF();
3875 const APFloat &V2 = N2CFP->getValueAPF();
3876 const APFloat &V3 = N3CFP->getValueAPF();
3877 APFloat::opStatus s =
3878 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3879 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3880 return getConstantFP(V1, DL, VT);
3884 case ISD::CONCAT_VECTORS:
3885 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3886 // one big BUILD_VECTOR.
3887 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3888 N2.getOpcode() == ISD::BUILD_VECTOR &&
3889 N3.getOpcode() == ISD::BUILD_VECTOR) {
3890 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3891 N1.getNode()->op_end());
3892 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3893 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3894 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3898 // Use FoldSetCC to simplify SETCC's.
3899 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3900 if (Simp.getNode()) return Simp;
3905 if (N1C->getZExtValue())
3906 return N2; // select true, X, Y -> X
3907 return N3; // select false, X, Y -> Y
3910 if (N2 == N3) return N2; // select C, X, X -> X
3912 case ISD::VECTOR_SHUFFLE:
3913 llvm_unreachable("should use getVectorShuffle constructor!");
3914 case ISD::INSERT_SUBVECTOR: {
3916 if (VT.isSimple() && N1.getValueType().isSimple()
3917 && N2.getValueType().isSimple()) {
3918 assert(VT.isVector() && N1.getValueType().isVector() &&
3919 N2.getValueType().isVector() &&
3920 "Insert subvector VTs must be a vectors");
3921 assert(VT == N1.getValueType() &&
3922 "Dest and insert subvector source types must match!");
3923 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3924 "Insert subvector must be from smaller vector to larger vector!");
3925 if (isa<ConstantSDNode>(Index)) {
3926 assert((N2.getValueType().getVectorNumElements() +
3927 cast<ConstantSDNode>(Index)->getZExtValue()
3928 <= VT.getVectorNumElements())
3929 && "Insert subvector overflow!");
3932 // Trivial insertion.
3933 if (VT.getSimpleVT() == N2.getSimpleValueType())
3939 // Fold bit_convert nodes from a type to themselves.
3940 if (N1.getValueType() == VT)
3945 // Memoize node if it doesn't produce a flag.
3947 SDVTList VTs = getVTList(VT);
3948 if (VT != MVT::Glue) {
3949 SDValue Ops[] = { N1, N2, N3 };
3950 FoldingSetNodeID ID;
3951 AddNodeIDNode(ID, Opcode, VTs, Ops);
3953 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3954 return SDValue(E, 0);
3956 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3957 DL.getDebugLoc(), VTs, N1, N2, N3);
3958 CSEMap.InsertNode(N, IP);
3960 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3961 DL.getDebugLoc(), VTs, N1, N2, N3);
3965 return SDValue(N, 0);
3968 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3969 SDValue N1, SDValue N2, SDValue N3,
3971 SDValue Ops[] = { N1, N2, N3, N4 };
3972 return getNode(Opcode, DL, VT, Ops);
3975 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3976 SDValue N1, SDValue N2, SDValue N3,
3977 SDValue N4, SDValue N5) {
3978 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3979 return getNode(Opcode, DL, VT, Ops);
3982 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3983 /// the incoming stack arguments to be loaded from the stack.
3984 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3985 SmallVector<SDValue, 8> ArgChains;
3987 // Include the original chain at the beginning of the list. When this is
3988 // used by target LowerCall hooks, this helps legalize find the
3989 // CALLSEQ_BEGIN node.
3990 ArgChains.push_back(Chain);
3992 // Add a chain value for each stack argument.
3993 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3994 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3995 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3996 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3997 if (FI->getIndex() < 0)
3998 ArgChains.push_back(SDValue(L, 1));
4000 // Build a tokenfactor for all the chains.
4001 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4004 /// getMemsetValue - Vectorized representation of the memset value
4006 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4008 assert(Value.getOpcode() != ISD::UNDEF);
4010 unsigned NumBits = VT.getScalarType().getSizeInBits();
4011 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4012 assert(C->getAPIntValue().getBitWidth() == 8);
4013 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4015 return DAG.getConstant(Val, dl, VT);
4016 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4020 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4021 EVT IntVT = VT.getScalarType();
4022 if (!IntVT.isInteger())
4023 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4025 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4027 // Use a multiplication with 0x010101... to extend the input to the
4029 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4030 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4031 DAG.getConstant(Magic, dl, IntVT));
4034 if (VT != Value.getValueType() && !VT.isInteger())
4035 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4036 if (VT != Value.getValueType()) {
4037 assert(VT.getVectorElementType() == Value.getValueType() &&
4038 "value type should be one vector element here");
4039 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4040 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4046 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4047 /// used when a memcpy is turned into a memset when the source is a constant
4049 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4050 const TargetLowering &TLI, StringRef Str) {
4051 // Handle vector with all elements zero.
4054 return DAG.getConstant(0, dl, VT);
4055 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4056 return DAG.getConstantFP(0.0, dl, VT);
4057 else if (VT.isVector()) {
4058 unsigned NumElts = VT.getVectorNumElements();
4059 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4060 return DAG.getNode(ISD::BITCAST, dl, VT,
4061 DAG.getConstant(0, dl,
4062 EVT::getVectorVT(*DAG.getContext(),
4065 llvm_unreachable("Expected type!");
4068 assert(!VT.isVector() && "Can't handle vector type here!");
4069 unsigned NumVTBits = VT.getSizeInBits();
4070 unsigned NumVTBytes = NumVTBits / 8;
4071 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4073 APInt Val(NumVTBits, 0);
4074 if (DAG.getDataLayout().isLittleEndian()) {
4075 for (unsigned i = 0; i != NumBytes; ++i)
4076 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4078 for (unsigned i = 0; i != NumBytes; ++i)
4079 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4082 // If the "cost" of materializing the integer immediate is less than the cost
4083 // of a load, then it is cost effective to turn the load into the immediate.
4084 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4085 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4086 return DAG.getConstant(Val, dl, VT);
4087 return SDValue(nullptr, 0);
4090 /// getMemBasePlusOffset - Returns base and offset node for the
4092 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4093 SelectionDAG &DAG) {
4094 EVT VT = Base.getValueType();
4095 return DAG.getNode(ISD::ADD, dl,
4096 VT, Base, DAG.getConstant(Offset, dl, VT));
4099 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4101 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4102 unsigned SrcDelta = 0;
4103 GlobalAddressSDNode *G = nullptr;
4104 if (Src.getOpcode() == ISD::GlobalAddress)
4105 G = cast<GlobalAddressSDNode>(Src);
4106 else if (Src.getOpcode() == ISD::ADD &&
4107 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4108 Src.getOperand(1).getOpcode() == ISD::Constant) {
4109 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4110 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4115 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4118 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4119 /// Return true if the number of memory ops is below the threshold (Limit).
4120 /// It returns the types of the sequence of memory ops to perform
4121 /// memset / memcpy by reference.
4122 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4123 unsigned Limit, uint64_t Size,
4124 unsigned DstAlign, unsigned SrcAlign,
4130 const TargetLowering &TLI) {
4131 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4132 "Expecting memcpy / memset source to meet alignment requirement!");
4133 // If 'SrcAlign' is zero, that means the memory operation does not need to
4134 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4135 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4136 // is the specified alignment of the memory operation. If it is zero, that
4137 // means it's possible to change the alignment of the destination.
4138 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4139 // not need to be loaded.
4140 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4141 IsMemset, ZeroMemset, MemcpyStrSrc,
4142 DAG.getMachineFunction());
4144 if (VT == MVT::Other) {
4146 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4147 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4148 VT = TLI.getPointerTy(DAG.getDataLayout());
4150 switch (DstAlign & 7) {
4151 case 0: VT = MVT::i64; break;
4152 case 4: VT = MVT::i32; break;
4153 case 2: VT = MVT::i16; break;
4154 default: VT = MVT::i8; break;
4159 while (!TLI.isTypeLegal(LVT))
4160 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4161 assert(LVT.isInteger());
4167 unsigned NumMemOps = 0;
4169 unsigned VTSize = VT.getSizeInBits() / 8;
4170 while (VTSize > Size) {
4171 // For now, only use non-vector load / store's for the left-over pieces.
4176 if (VT.isVector() || VT.isFloatingPoint()) {
4177 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4178 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4179 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4181 else if (NewVT == MVT::i64 &&
4182 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4183 TLI.isSafeMemOpType(MVT::f64)) {
4184 // i64 is usually not legal on 32-bit targets, but f64 may be.
4192 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4193 if (NewVT == MVT::i8)
4195 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4197 NewVTSize = NewVT.getSizeInBits() / 8;
4199 // If the new VT cannot cover all of the remaining bits, then consider
4200 // issuing a (or a pair of) unaligned and overlapping load / store.
4201 // FIXME: Only does this for 64-bit or more since we don't have proper
4202 // cost model for unaligned load / store.
4205 if (NumMemOps && AllowOverlap &&
4206 VTSize >= 8 && NewVTSize < Size &&
4207 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4215 if (++NumMemOps > Limit)
4218 MemOps.push_back(VT);
4225 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4226 // On Darwin, -Os means optimize for size without hurting performance, so
4227 // only really optimize for size when -Oz (MinSize) is used.
4228 if (MF.getTarget().getTargetTriple().isOSDarwin())
4229 return MF.getFunction()->optForMinSize();
4230 return MF.getFunction()->optForSize();
4233 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4234 SDValue Chain, SDValue Dst,
4235 SDValue Src, uint64_t Size,
4236 unsigned Align, bool isVol,
4238 MachinePointerInfo DstPtrInfo,
4239 MachinePointerInfo SrcPtrInfo) {
4240 // Turn a memcpy of undef to nop.
4241 if (Src.getOpcode() == ISD::UNDEF)
4244 // Expand memcpy to a series of load and store ops if the size operand falls
4245 // below a certain threshold.
4246 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4247 // rather than maybe a humongous number of loads and stores.
4248 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4249 std::vector<EVT> MemOps;
4250 bool DstAlignCanChange = false;
4251 MachineFunction &MF = DAG.getMachineFunction();
4252 MachineFrameInfo *MFI = MF.getFrameInfo();
4253 bool OptSize = shouldLowerMemFuncForSize(MF);
4254 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4255 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4256 DstAlignCanChange = true;
4257 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4258 if (Align > SrcAlign)
4261 bool CopyFromStr = isMemSrcFromString(Src, Str);
4262 bool isZeroStr = CopyFromStr && Str.empty();
4263 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4265 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4266 (DstAlignCanChange ? 0 : Align),
4267 (isZeroStr ? 0 : SrcAlign),
4268 false, false, CopyFromStr, true, DAG, TLI))
4271 if (DstAlignCanChange) {
4272 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4273 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4275 // Don't promote to an alignment that would require dynamic stack
4277 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4278 if (!TRI->needsStackRealignment(MF))
4279 while (NewAlign > Align &&
4280 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4283 if (NewAlign > Align) {
4284 // Give the stack frame object a larger alignment if needed.
4285 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4286 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4291 SmallVector<SDValue, 8> OutChains;
4292 unsigned NumMemOps = MemOps.size();
4293 uint64_t SrcOff = 0, DstOff = 0;
4294 for (unsigned i = 0; i != NumMemOps; ++i) {
4296 unsigned VTSize = VT.getSizeInBits() / 8;
4297 SDValue Value, Store;
4299 if (VTSize > Size) {
4300 // Issuing an unaligned load / store pair that overlaps with the previous
4301 // pair. Adjust the offset accordingly.
4302 assert(i == NumMemOps-1 && i != 0);
4303 SrcOff -= VTSize - Size;
4304 DstOff -= VTSize - Size;
4308 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4309 // It's unlikely a store of a vector immediate can be done in a single
4310 // instruction. It would require a load from a constantpool first.
4311 // We only handle zero vectors here.
4312 // FIXME: Handle other cases where store of vector immediate is done in
4313 // a single instruction.
4314 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4315 if (Value.getNode())
4316 Store = DAG.getStore(Chain, dl, Value,
4317 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4318 DstPtrInfo.getWithOffset(DstOff), isVol,
4322 if (!Store.getNode()) {
4323 // The type might not be legal for the target. This should only happen
4324 // if the type is smaller than a legal type, as on PPC, so the right
4325 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4326 // to Load/Store if NVT==VT.
4327 // FIXME does the case above also need this?
4328 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4329 assert(NVT.bitsGE(VT));
4330 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4331 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4332 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4333 false, MinAlign(SrcAlign, SrcOff));
4334 Store = DAG.getTruncStore(Chain, dl, Value,
4335 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4336 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4339 OutChains.push_back(Store);
4345 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4348 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4349 SDValue Chain, SDValue Dst,
4350 SDValue Src, uint64_t Size,
4351 unsigned Align, bool isVol,
4353 MachinePointerInfo DstPtrInfo,
4354 MachinePointerInfo SrcPtrInfo) {
4355 // Turn a memmove of undef to nop.
4356 if (Src.getOpcode() == ISD::UNDEF)
4359 // Expand memmove to a series of load and store ops if the size operand falls
4360 // below a certain threshold.
4361 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4362 std::vector<EVT> MemOps;
4363 bool DstAlignCanChange = false;
4364 MachineFunction &MF = DAG.getMachineFunction();
4365 MachineFrameInfo *MFI = MF.getFrameInfo();
4366 bool OptSize = shouldLowerMemFuncForSize(MF);
4367 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4368 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4369 DstAlignCanChange = true;
4370 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4371 if (Align > SrcAlign)
4373 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4375 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4376 (DstAlignCanChange ? 0 : Align), SrcAlign,
4377 false, false, false, false, DAG, TLI))
4380 if (DstAlignCanChange) {
4381 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4382 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4383 if (NewAlign > Align) {
4384 // Give the stack frame object a larger alignment if needed.
4385 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4386 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4391 uint64_t SrcOff = 0, DstOff = 0;
4392 SmallVector<SDValue, 8> LoadValues;
4393 SmallVector<SDValue, 8> LoadChains;
4394 SmallVector<SDValue, 8> OutChains;
4395 unsigned NumMemOps = MemOps.size();
4396 for (unsigned i = 0; i < NumMemOps; i++) {
4398 unsigned VTSize = VT.getSizeInBits() / 8;
4401 Value = DAG.getLoad(VT, dl, Chain,
4402 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4403 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4404 false, false, SrcAlign);
4405 LoadValues.push_back(Value);
4406 LoadChains.push_back(Value.getValue(1));
4409 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4411 for (unsigned i = 0; i < NumMemOps; i++) {
4413 unsigned VTSize = VT.getSizeInBits() / 8;
4416 Store = DAG.getStore(Chain, dl, LoadValues[i],
4417 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4418 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4419 OutChains.push_back(Store);
4423 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4426 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4429 /// \param DAG Selection DAG where lowered code is placed.
4430 /// \param dl Link to corresponding IR location.
4431 /// \param Chain Control flow dependency.
4432 /// \param Dst Pointer to destination memory location.
4433 /// \param Src Value of byte to write into the memory.
4434 /// \param Size Number of bytes to write.
4435 /// \param Align Alignment of the destination in bytes.
4436 /// \param isVol True if destination is volatile.
4437 /// \param DstPtrInfo IR information on the memory pointer.
4438 /// \returns New head in the control flow, if lowering was successful, empty
4439 /// SDValue otherwise.
4441 /// The function tries to replace 'llvm.memset' intrinsic with several store
4442 /// operations and value calculation code. This is usually profitable for small
4444 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4445 SDValue Chain, SDValue Dst,
4446 SDValue Src, uint64_t Size,
4447 unsigned Align, bool isVol,
4448 MachinePointerInfo DstPtrInfo) {
4449 // Turn a memset of undef to nop.
4450 if (Src.getOpcode() == ISD::UNDEF)
4453 // Expand memset to a series of load/store ops if the size operand
4454 // falls below a certain threshold.
4455 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4456 std::vector<EVT> MemOps;
4457 bool DstAlignCanChange = false;
4458 MachineFunction &MF = DAG.getMachineFunction();
4459 MachineFrameInfo *MFI = MF.getFrameInfo();
4460 bool OptSize = shouldLowerMemFuncForSize(MF);
4461 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4462 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4463 DstAlignCanChange = true;
4465 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4466 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4467 Size, (DstAlignCanChange ? 0 : Align), 0,
4468 true, IsZeroVal, false, true, DAG, TLI))
4471 if (DstAlignCanChange) {
4472 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4473 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4474 if (NewAlign > Align) {
4475 // Give the stack frame object a larger alignment if needed.
4476 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4477 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4482 SmallVector<SDValue, 8> OutChains;
4483 uint64_t DstOff = 0;
4484 unsigned NumMemOps = MemOps.size();
4486 // Find the largest store and generate the bit pattern for it.
4487 EVT LargestVT = MemOps[0];
4488 for (unsigned i = 1; i < NumMemOps; i++)
4489 if (MemOps[i].bitsGT(LargestVT))
4490 LargestVT = MemOps[i];
4491 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4493 for (unsigned i = 0; i < NumMemOps; i++) {
4495 unsigned VTSize = VT.getSizeInBits() / 8;
4496 if (VTSize > Size) {
4497 // Issuing an unaligned load / store pair that overlaps with the previous
4498 // pair. Adjust the offset accordingly.
4499 assert(i == NumMemOps-1 && i != 0);
4500 DstOff -= VTSize - Size;
4503 // If this store is smaller than the largest store see whether we can get
4504 // the smaller value for free with a truncate.
4505 SDValue Value = MemSetValue;
4506 if (VT.bitsLT(LargestVT)) {
4507 if (!LargestVT.isVector() && !VT.isVector() &&
4508 TLI.isTruncateFree(LargestVT, VT))
4509 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4511 Value = getMemsetValue(Src, VT, DAG, dl);
4513 assert(Value.getValueType() == VT && "Value with wrong type.");
4514 SDValue Store = DAG.getStore(Chain, dl, Value,
4515 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4516 DstPtrInfo.getWithOffset(DstOff),
4517 isVol, false, Align);
4518 OutChains.push_back(Store);
4519 DstOff += VT.getSizeInBits() / 8;
4523 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4526 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4527 SDValue Src, SDValue Size,
4528 unsigned Align, bool isVol, bool AlwaysInline,
4529 bool isTailCall, MachinePointerInfo DstPtrInfo,
4530 MachinePointerInfo SrcPtrInfo) {
4531 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4533 // Check to see if we should lower the memcpy to loads and stores first.
4534 // For cases within the target-specified limits, this is the best choice.
4535 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4537 // Memcpy with size zero? Just return the original chain.
4538 if (ConstantSize->isNullValue())
4541 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4542 ConstantSize->getZExtValue(),Align,
4543 isVol, false, DstPtrInfo, SrcPtrInfo);
4544 if (Result.getNode())
4548 // Then check to see if we should lower the memcpy with target-specific
4549 // code. If the target chooses to do this, this is the next best.
4551 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4552 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4553 DstPtrInfo, SrcPtrInfo);
4554 if (Result.getNode())
4558 // If we really need inline code and the target declined to provide it,
4559 // use a (potentially long) sequence of loads and stores.
4561 assert(ConstantSize && "AlwaysInline requires a constant size!");
4562 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4563 ConstantSize->getZExtValue(), Align, isVol,
4564 true, DstPtrInfo, SrcPtrInfo);
4567 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4568 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4569 // respect volatile, so they may do things like read or write memory
4570 // beyond the given memory regions. But fixing this isn't easy, and most
4571 // people don't care.
4573 // Emit a library call.
4574 TargetLowering::ArgListTy Args;
4575 TargetLowering::ArgListEntry Entry;
4576 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4577 Entry.Node = Dst; Args.push_back(Entry);
4578 Entry.Node = Src; Args.push_back(Entry);
4579 Entry.Node = Size; Args.push_back(Entry);
4580 // FIXME: pass in SDLoc
4581 TargetLowering::CallLoweringInfo CLI(*this);
4584 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4585 Type::getVoidTy(*getContext()),
4586 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4587 TLI->getPointerTy(getDataLayout())),
4590 .setTailCall(isTailCall);
4592 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4593 return CallResult.second;
4596 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4597 SDValue Src, SDValue Size,
4598 unsigned Align, bool isVol, bool isTailCall,
4599 MachinePointerInfo DstPtrInfo,
4600 MachinePointerInfo SrcPtrInfo) {
4601 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4603 // Check to see if we should lower the memmove to loads and stores first.
4604 // For cases within the target-specified limits, this is the best choice.
4605 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4607 // Memmove with size zero? Just return the original chain.
4608 if (ConstantSize->isNullValue())
4612 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4613 ConstantSize->getZExtValue(), Align, isVol,
4614 false, DstPtrInfo, SrcPtrInfo);
4615 if (Result.getNode())
4619 // Then check to see if we should lower the memmove with target-specific
4620 // code. If the target chooses to do this, this is the next best.
4622 SDValue Result = TSI->EmitTargetCodeForMemmove(
4623 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4624 if (Result.getNode())
4628 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4629 // not be safe. See memcpy above for more details.
4631 // Emit a library call.
4632 TargetLowering::ArgListTy Args;
4633 TargetLowering::ArgListEntry Entry;
4634 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4635 Entry.Node = Dst; Args.push_back(Entry);
4636 Entry.Node = Src; Args.push_back(Entry);
4637 Entry.Node = Size; Args.push_back(Entry);
4638 // FIXME: pass in SDLoc
4639 TargetLowering::CallLoweringInfo CLI(*this);
4642 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4643 Type::getVoidTy(*getContext()),
4644 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4645 TLI->getPointerTy(getDataLayout())),
4648 .setTailCall(isTailCall);
4650 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4651 return CallResult.second;
4654 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4655 SDValue Src, SDValue Size,
4656 unsigned Align, bool isVol, bool isTailCall,
4657 MachinePointerInfo DstPtrInfo) {
4658 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4660 // Check to see if we should lower the memset to stores first.
4661 // For cases within the target-specified limits, this is the best choice.
4662 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4664 // Memset with size zero? Just return the original chain.
4665 if (ConstantSize->isNullValue())
4669 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4670 Align, isVol, DstPtrInfo);
4672 if (Result.getNode())
4676 // Then check to see if we should lower the memset with target-specific
4677 // code. If the target chooses to do this, this is the next best.
4679 SDValue Result = TSI->EmitTargetCodeForMemset(
4680 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4681 if (Result.getNode())
4685 // Emit a library call.
4686 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4687 TargetLowering::ArgListTy Args;
4688 TargetLowering::ArgListEntry Entry;
4689 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4690 Args.push_back(Entry);
4692 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4693 Args.push_back(Entry);
4695 Entry.Ty = IntPtrTy;
4696 Args.push_back(Entry);
4698 // FIXME: pass in SDLoc
4699 TargetLowering::CallLoweringInfo CLI(*this);
4702 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4703 Type::getVoidTy(*getContext()),
4704 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4705 TLI->getPointerTy(getDataLayout())),
4708 .setTailCall(isTailCall);
4710 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4711 return CallResult.second;
4714 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4715 SDVTList VTList, ArrayRef<SDValue> Ops,
4716 MachineMemOperand *MMO,
4717 AtomicOrdering SuccessOrdering,
4718 AtomicOrdering FailureOrdering,
4719 SynchronizationScope SynchScope) {
4720 FoldingSetNodeID ID;
4721 ID.AddInteger(MemVT.getRawBits());
4722 AddNodeIDNode(ID, Opcode, VTList, Ops);
4723 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4725 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4726 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4727 return SDValue(E, 0);
4730 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4731 // SDNode doesn't have access to it. This memory will be "leaked" when
4732 // the node is deallocated, but recovered when the allocator is released.
4733 // If the number of operands is less than 5 we use AtomicSDNode's internal
4735 unsigned NumOps = Ops.size();
4736 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4739 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4740 dl.getDebugLoc(), VTList, MemVT,
4741 Ops.data(), DynOps, NumOps, MMO,
4742 SuccessOrdering, FailureOrdering,
4744 CSEMap.InsertNode(N, IP);
4746 return SDValue(N, 0);
4749 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4750 SDVTList VTList, ArrayRef<SDValue> Ops,
4751 MachineMemOperand *MMO,
4752 AtomicOrdering Ordering,
4753 SynchronizationScope SynchScope) {
4754 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4755 Ordering, SynchScope);
4758 SDValue SelectionDAG::getAtomicCmpSwap(
4759 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4760 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4761 unsigned Alignment, AtomicOrdering SuccessOrdering,
4762 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4763 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4764 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4765 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4767 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4768 Alignment = getEVTAlignment(MemVT);
4770 MachineFunction &MF = getMachineFunction();
4772 // FIXME: Volatile isn't really correct; we should keep track of atomic
4773 // orderings in the memoperand.
4774 unsigned Flags = MachineMemOperand::MOVolatile;
4775 Flags |= MachineMemOperand::MOLoad;
4776 Flags |= MachineMemOperand::MOStore;
4778 MachineMemOperand *MMO =
4779 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4781 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4782 SuccessOrdering, FailureOrdering, SynchScope);
4785 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4786 SDVTList VTs, SDValue Chain, SDValue Ptr,
4787 SDValue Cmp, SDValue Swp,
4788 MachineMemOperand *MMO,
4789 AtomicOrdering SuccessOrdering,
4790 AtomicOrdering FailureOrdering,
4791 SynchronizationScope SynchScope) {
4792 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4793 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4794 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4796 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4797 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4798 SuccessOrdering, FailureOrdering, SynchScope);
4801 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4803 SDValue Ptr, SDValue Val,
4804 const Value* PtrVal,
4806 AtomicOrdering Ordering,
4807 SynchronizationScope SynchScope) {
4808 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4809 Alignment = getEVTAlignment(MemVT);
4811 MachineFunction &MF = getMachineFunction();
4812 // An atomic store does not load. An atomic load does not store.
4813 // (An atomicrmw obviously both loads and stores.)
4814 // For now, atomics are considered to be volatile always, and they are
4816 // FIXME: Volatile isn't really correct; we should keep track of atomic
4817 // orderings in the memoperand.
4818 unsigned Flags = MachineMemOperand::MOVolatile;
4819 if (Opcode != ISD::ATOMIC_STORE)
4820 Flags |= MachineMemOperand::MOLoad;
4821 if (Opcode != ISD::ATOMIC_LOAD)
4822 Flags |= MachineMemOperand::MOStore;
4824 MachineMemOperand *MMO =
4825 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4826 MemVT.getStoreSize(), Alignment);
4828 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4829 Ordering, SynchScope);
4832 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4834 SDValue Ptr, SDValue Val,
4835 MachineMemOperand *MMO,
4836 AtomicOrdering Ordering,
4837 SynchronizationScope SynchScope) {
4838 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4839 Opcode == ISD::ATOMIC_LOAD_SUB ||
4840 Opcode == ISD::ATOMIC_LOAD_AND ||
4841 Opcode == ISD::ATOMIC_LOAD_OR ||
4842 Opcode == ISD::ATOMIC_LOAD_XOR ||
4843 Opcode == ISD::ATOMIC_LOAD_NAND ||
4844 Opcode == ISD::ATOMIC_LOAD_MIN ||
4845 Opcode == ISD::ATOMIC_LOAD_MAX ||
4846 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4847 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4848 Opcode == ISD::ATOMIC_SWAP ||
4849 Opcode == ISD::ATOMIC_STORE) &&
4850 "Invalid Atomic Op");
4852 EVT VT = Val.getValueType();
4854 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4855 getVTList(VT, MVT::Other);
4856 SDValue Ops[] = {Chain, Ptr, Val};
4857 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4860 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4861 EVT VT, SDValue Chain,
4863 MachineMemOperand *MMO,
4864 AtomicOrdering Ordering,
4865 SynchronizationScope SynchScope) {
4866 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4868 SDVTList VTs = getVTList(VT, MVT::Other);
4869 SDValue Ops[] = {Chain, Ptr};
4870 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4873 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4874 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4875 if (Ops.size() == 1)
4878 SmallVector<EVT, 4> VTs;
4879 VTs.reserve(Ops.size());
4880 for (unsigned i = 0; i < Ops.size(); ++i)
4881 VTs.push_back(Ops[i].getValueType());
4882 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4886 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4887 ArrayRef<SDValue> Ops,
4888 EVT MemVT, MachinePointerInfo PtrInfo,
4889 unsigned Align, bool Vol,
4890 bool ReadMem, bool WriteMem, unsigned Size) {
4891 if (Align == 0) // Ensure that codegen never sees alignment 0
4892 Align = getEVTAlignment(MemVT);
4894 MachineFunction &MF = getMachineFunction();
4897 Flags |= MachineMemOperand::MOStore;
4899 Flags |= MachineMemOperand::MOLoad;
4901 Flags |= MachineMemOperand::MOVolatile;
4903 Size = MemVT.getStoreSize();
4904 MachineMemOperand *MMO =
4905 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4907 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4911 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4912 ArrayRef<SDValue> Ops, EVT MemVT,
4913 MachineMemOperand *MMO) {
4914 assert((Opcode == ISD::INTRINSIC_VOID ||
4915 Opcode == ISD::INTRINSIC_W_CHAIN ||
4916 Opcode == ISD::PREFETCH ||
4917 Opcode == ISD::LIFETIME_START ||
4918 Opcode == ISD::LIFETIME_END ||
4919 (Opcode <= INT_MAX &&
4920 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4921 "Opcode is not a memory-accessing opcode!");
4923 // Memoize the node unless it returns a flag.
4924 MemIntrinsicSDNode *N;
4925 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4926 FoldingSetNodeID ID;
4927 AddNodeIDNode(ID, Opcode, VTList, Ops);
4928 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4930 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4931 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4932 return SDValue(E, 0);
4935 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4936 dl.getDebugLoc(), VTList, Ops,
4938 CSEMap.InsertNode(N, IP);
4940 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4941 dl.getDebugLoc(), VTList, Ops,
4945 return SDValue(N, 0);
4948 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4949 /// MachinePointerInfo record from it. This is particularly useful because the
4950 /// code generator has many cases where it doesn't bother passing in a
4951 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4952 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4953 int64_t Offset = 0) {
4954 // If this is FI+Offset, we can model it.
4955 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4956 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4957 FI->getIndex(), Offset);
4959 // If this is (FI+Offset1)+Offset2, we can model it.
4960 if (Ptr.getOpcode() != ISD::ADD ||
4961 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4962 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4963 return MachinePointerInfo();
4965 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4966 return MachinePointerInfo::getFixedStack(
4967 DAG.getMachineFunction(), FI,
4968 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4971 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4972 /// MachinePointerInfo record from it. This is particularly useful because the
4973 /// code generator has many cases where it doesn't bother passing in a
4974 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4975 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4977 // If the 'Offset' value isn't a constant, we can't handle this.
4978 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4979 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4980 if (OffsetOp.getOpcode() == ISD::UNDEF)
4981 return InferPointerInfo(DAG, Ptr);
4982 return MachinePointerInfo();
4987 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4988 EVT VT, SDLoc dl, SDValue Chain,
4989 SDValue Ptr, SDValue Offset,
4990 MachinePointerInfo PtrInfo, EVT MemVT,
4991 bool isVolatile, bool isNonTemporal, bool isInvariant,
4992 unsigned Alignment, const AAMDNodes &AAInfo,
4993 const MDNode *Ranges) {
4994 assert(Chain.getValueType() == MVT::Other &&
4995 "Invalid chain type");
4996 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4997 Alignment = getEVTAlignment(VT);
4999 unsigned Flags = MachineMemOperand::MOLoad;
5001 Flags |= MachineMemOperand::MOVolatile;
5003 Flags |= MachineMemOperand::MONonTemporal;
5005 Flags |= MachineMemOperand::MOInvariant;
5007 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5009 if (PtrInfo.V.isNull())
5010 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5012 MachineFunction &MF = getMachineFunction();
5013 MachineMemOperand *MMO =
5014 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5016 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5020 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5021 EVT VT, SDLoc dl, SDValue Chain,
5022 SDValue Ptr, SDValue Offset, EVT MemVT,
5023 MachineMemOperand *MMO) {
5025 ExtType = ISD::NON_EXTLOAD;
5026 } else if (ExtType == ISD::NON_EXTLOAD) {
5027 assert(VT == MemVT && "Non-extending load from different memory type!");
5030 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5031 "Should only be an extending load, not truncating!");
5032 assert(VT.isInteger() == MemVT.isInteger() &&
5033 "Cannot convert from FP to Int or Int -> FP!");
5034 assert(VT.isVector() == MemVT.isVector() &&
5035 "Cannot use an ext load to convert to or from a vector!");
5036 assert((!VT.isVector() ||
5037 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5038 "Cannot use an ext load to change the number of vector elements!");
5041 bool Indexed = AM != ISD::UNINDEXED;
5042 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5043 "Unindexed load with an offset!");
5045 SDVTList VTs = Indexed ?
5046 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5047 SDValue Ops[] = { Chain, Ptr, Offset };
5048 FoldingSetNodeID ID;
5049 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5050 ID.AddInteger(MemVT.getRawBits());
5051 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5052 MMO->isNonTemporal(),
5053 MMO->isInvariant()));
5054 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5056 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5057 cast<LoadSDNode>(E)->refineAlignment(MMO);
5058 return SDValue(E, 0);
5060 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5061 dl.getDebugLoc(), VTs, AM, ExtType,
5063 CSEMap.InsertNode(N, IP);
5065 return SDValue(N, 0);
5068 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5069 SDValue Chain, SDValue Ptr,
5070 MachinePointerInfo PtrInfo,
5071 bool isVolatile, bool isNonTemporal,
5072 bool isInvariant, unsigned Alignment,
5073 const AAMDNodes &AAInfo,
5074 const MDNode *Ranges) {
5075 SDValue Undef = getUNDEF(Ptr.getValueType());
5076 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5077 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5081 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5082 SDValue Chain, SDValue Ptr,
5083 MachineMemOperand *MMO) {
5084 SDValue Undef = getUNDEF(Ptr.getValueType());
5085 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5089 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5090 SDValue Chain, SDValue Ptr,
5091 MachinePointerInfo PtrInfo, EVT MemVT,
5092 bool isVolatile, bool isNonTemporal,
5093 bool isInvariant, unsigned Alignment,
5094 const AAMDNodes &AAInfo) {
5095 SDValue Undef = getUNDEF(Ptr.getValueType());
5096 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5097 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5102 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5103 SDValue Chain, SDValue Ptr, EVT MemVT,
5104 MachineMemOperand *MMO) {
5105 SDValue Undef = getUNDEF(Ptr.getValueType());
5106 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5111 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5112 SDValue Offset, ISD::MemIndexedMode AM) {
5113 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5114 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5115 "Load is already a indexed load!");
5116 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5117 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5118 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5119 false, LD->getAlignment());
5122 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5123 SDValue Ptr, MachinePointerInfo PtrInfo,
5124 bool isVolatile, bool isNonTemporal,
5125 unsigned Alignment, const AAMDNodes &AAInfo) {
5126 assert(Chain.getValueType() == MVT::Other &&
5127 "Invalid chain type");
5128 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5129 Alignment = getEVTAlignment(Val.getValueType());
5131 unsigned Flags = MachineMemOperand::MOStore;
5133 Flags |= MachineMemOperand::MOVolatile;
5135 Flags |= MachineMemOperand::MONonTemporal;
5137 if (PtrInfo.V.isNull())
5138 PtrInfo = InferPointerInfo(*this, Ptr);
5140 MachineFunction &MF = getMachineFunction();
5141 MachineMemOperand *MMO =
5142 MF.getMachineMemOperand(PtrInfo, Flags,
5143 Val.getValueType().getStoreSize(), Alignment,
5146 return getStore(Chain, dl, Val, Ptr, MMO);
5149 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5150 SDValue Ptr, MachineMemOperand *MMO) {
5151 assert(Chain.getValueType() == MVT::Other &&
5152 "Invalid chain type");
5153 EVT VT = Val.getValueType();
5154 SDVTList VTs = getVTList(MVT::Other);
5155 SDValue Undef = getUNDEF(Ptr.getValueType());
5156 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5157 FoldingSetNodeID ID;
5158 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5159 ID.AddInteger(VT.getRawBits());
5160 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5161 MMO->isNonTemporal(), MMO->isInvariant()));
5162 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5164 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5165 cast<StoreSDNode>(E)->refineAlignment(MMO);
5166 return SDValue(E, 0);
5168 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5169 dl.getDebugLoc(), VTs,
5170 ISD::UNINDEXED, false, VT, MMO);
5171 CSEMap.InsertNode(N, IP);
5173 return SDValue(N, 0);
5176 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5177 SDValue Ptr, MachinePointerInfo PtrInfo,
5178 EVT SVT,bool isVolatile, bool isNonTemporal,
5180 const AAMDNodes &AAInfo) {
5181 assert(Chain.getValueType() == MVT::Other &&
5182 "Invalid chain type");
5183 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5184 Alignment = getEVTAlignment(SVT);
5186 unsigned Flags = MachineMemOperand::MOStore;
5188 Flags |= MachineMemOperand::MOVolatile;
5190 Flags |= MachineMemOperand::MONonTemporal;
5192 if (PtrInfo.V.isNull())
5193 PtrInfo = InferPointerInfo(*this, Ptr);
5195 MachineFunction &MF = getMachineFunction();
5196 MachineMemOperand *MMO =
5197 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5200 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5203 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5204 SDValue Ptr, EVT SVT,
5205 MachineMemOperand *MMO) {
5206 EVT VT = Val.getValueType();
5208 assert(Chain.getValueType() == MVT::Other &&
5209 "Invalid chain type");
5211 return getStore(Chain, dl, Val, Ptr, MMO);
5213 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5214 "Should only be a truncating store, not extending!");
5215 assert(VT.isInteger() == SVT.isInteger() &&
5216 "Can't do FP-INT conversion!");
5217 assert(VT.isVector() == SVT.isVector() &&
5218 "Cannot use trunc store to convert to or from a vector!");
5219 assert((!VT.isVector() ||
5220 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5221 "Cannot use trunc store to change the number of vector elements!");
5223 SDVTList VTs = getVTList(MVT::Other);
5224 SDValue Undef = getUNDEF(Ptr.getValueType());
5225 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5226 FoldingSetNodeID ID;
5227 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5228 ID.AddInteger(SVT.getRawBits());
5229 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5230 MMO->isNonTemporal(), MMO->isInvariant()));
5231 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5233 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5234 cast<StoreSDNode>(E)->refineAlignment(MMO);
5235 return SDValue(E, 0);
5237 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5238 dl.getDebugLoc(), VTs,
5239 ISD::UNINDEXED, true, SVT, MMO);
5240 CSEMap.InsertNode(N, IP);
5242 return SDValue(N, 0);
5246 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5247 SDValue Offset, ISD::MemIndexedMode AM) {
5248 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5249 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5250 "Store is already a indexed store!");
5251 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5252 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5253 FoldingSetNodeID ID;
5254 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5255 ID.AddInteger(ST->getMemoryVT().getRawBits());
5256 ID.AddInteger(ST->getRawSubclassData());
5257 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5259 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5260 return SDValue(E, 0);
5262 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5263 dl.getDebugLoc(), VTs, AM,
5264 ST->isTruncatingStore(),
5266 ST->getMemOperand());
5267 CSEMap.InsertNode(N, IP);
5269 return SDValue(N, 0);
5273 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5274 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5275 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5277 SDVTList VTs = getVTList(VT, MVT::Other);
5278 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5279 FoldingSetNodeID ID;
5280 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5281 ID.AddInteger(VT.getRawBits());
5282 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5284 MMO->isNonTemporal(),
5285 MMO->isInvariant()));
5286 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5288 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5289 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5290 return SDValue(E, 0);
5292 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5293 dl.getDebugLoc(), Ops, 4, VTs,
5295 CSEMap.InsertNode(N, IP);
5297 return SDValue(N, 0);
5300 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5301 SDValue Ptr, SDValue Mask, EVT MemVT,
5302 MachineMemOperand *MMO, bool isTrunc) {
5303 assert(Chain.getValueType() == MVT::Other &&
5304 "Invalid chain type");
5305 EVT VT = Val.getValueType();
5306 SDVTList VTs = getVTList(MVT::Other);
5307 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5308 FoldingSetNodeID ID;
5309 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5310 ID.AddInteger(VT.getRawBits());
5311 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5312 MMO->isNonTemporal(), MMO->isInvariant()));
5313 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5315 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5316 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5317 return SDValue(E, 0);
5319 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5320 dl.getDebugLoc(), Ops, 4,
5321 VTs, isTrunc, MemVT, MMO);
5322 CSEMap.InsertNode(N, IP);
5324 return SDValue(N, 0);
5328 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5329 ArrayRef<SDValue> Ops,
5330 MachineMemOperand *MMO) {
5332 FoldingSetNodeID ID;
5333 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5334 ID.AddInteger(VT.getRawBits());
5335 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5337 MMO->isNonTemporal(),
5338 MMO->isInvariant()));
5339 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5341 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5342 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5343 return SDValue(E, 0);
5345 MaskedGatherSDNode *N =
5346 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5348 CSEMap.InsertNode(N, IP);
5350 return SDValue(N, 0);
5353 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5354 ArrayRef<SDValue> Ops,
5355 MachineMemOperand *MMO) {
5356 FoldingSetNodeID ID;
5357 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5358 ID.AddInteger(VT.getRawBits());
5359 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5360 MMO->isNonTemporal(),
5361 MMO->isInvariant()));
5362 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5364 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5365 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5366 return SDValue(E, 0);
5369 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5371 CSEMap.InsertNode(N, IP);
5373 return SDValue(N, 0);
5376 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5377 SDValue Chain, SDValue Ptr,
5380 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5381 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5384 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5385 ArrayRef<SDUse> Ops) {
5386 switch (Ops.size()) {
5387 case 0: return getNode(Opcode, DL, VT);
5388 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5389 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5390 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5394 // Copy from an SDUse array into an SDValue array for use with
5395 // the regular getNode logic.
5396 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5397 return getNode(Opcode, DL, VT, NewOps);
5400 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5401 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5402 unsigned NumOps = Ops.size();
5404 case 0: return getNode(Opcode, DL, VT);
5405 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5406 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5407 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5413 case ISD::SELECT_CC: {
5414 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5415 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5416 "LHS and RHS of condition must have same type!");
5417 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5418 "True and False arms of SelectCC must have same type!");
5419 assert(Ops[2].getValueType() == VT &&
5420 "select_cc node must be of same type as true and false value!");
5424 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5425 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5426 "LHS/RHS of comparison should match types!");
5433 SDVTList VTs = getVTList(VT);
5435 if (VT != MVT::Glue) {
5436 FoldingSetNodeID ID;
5437 AddNodeIDNode(ID, Opcode, VTs, Ops);
5440 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5441 return SDValue(E, 0);
5443 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5445 CSEMap.InsertNode(N, IP);
5447 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5452 return SDValue(N, 0);
5455 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5456 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5457 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5460 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5461 ArrayRef<SDValue> Ops) {
5462 if (VTList.NumVTs == 1)
5463 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5467 // FIXME: figure out how to safely handle things like
5468 // int foo(int x) { return 1 << (x & 255); }
5469 // int bar() { return foo(256); }
5470 case ISD::SRA_PARTS:
5471 case ISD::SRL_PARTS:
5472 case ISD::SHL_PARTS:
5473 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5474 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5475 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5476 else if (N3.getOpcode() == ISD::AND)
5477 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5478 // If the and is only masking out bits that cannot effect the shift,
5479 // eliminate the and.
5480 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5481 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5482 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5488 // Memoize the node unless it returns a flag.
5490 unsigned NumOps = Ops.size();
5491 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5492 FoldingSetNodeID ID;
5493 AddNodeIDNode(ID, Opcode, VTList, Ops);
5495 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5496 return SDValue(E, 0);
5499 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5500 DL.getDebugLoc(), VTList, Ops[0]);
5501 } else if (NumOps == 2) {
5502 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5503 DL.getDebugLoc(), VTList, Ops[0],
5505 } else if (NumOps == 3) {
5506 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5507 DL.getDebugLoc(), VTList, Ops[0],
5510 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5513 CSEMap.InsertNode(N, IP);
5516 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5517 DL.getDebugLoc(), VTList, Ops[0]);
5518 } else if (NumOps == 2) {
5519 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5520 DL.getDebugLoc(), VTList, Ops[0],
5522 } else if (NumOps == 3) {
5523 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5524 DL.getDebugLoc(), VTList, Ops[0],
5527 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5532 return SDValue(N, 0);
5535 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5536 return getNode(Opcode, DL, VTList, None);
5539 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5541 SDValue Ops[] = { N1 };
5542 return getNode(Opcode, DL, VTList, Ops);
5545 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5546 SDValue N1, SDValue N2) {
5547 SDValue Ops[] = { N1, N2 };
5548 return getNode(Opcode, DL, VTList, Ops);
5551 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5552 SDValue N1, SDValue N2, SDValue N3) {
5553 SDValue Ops[] = { N1, N2, N3 };
5554 return getNode(Opcode, DL, VTList, Ops);
5557 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5558 SDValue N1, SDValue N2, SDValue N3,
5560 SDValue Ops[] = { N1, N2, N3, N4 };
5561 return getNode(Opcode, DL, VTList, Ops);
5564 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5565 SDValue N1, SDValue N2, SDValue N3,
5566 SDValue N4, SDValue N5) {
5567 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5568 return getNode(Opcode, DL, VTList, Ops);
5571 SDVTList SelectionDAG::getVTList(EVT VT) {
5572 return makeVTList(SDNode::getValueTypeList(VT), 1);
5575 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5576 FoldingSetNodeID ID;
5578 ID.AddInteger(VT1.getRawBits());
5579 ID.AddInteger(VT2.getRawBits());
5582 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5584 EVT *Array = Allocator.Allocate<EVT>(2);
5587 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5588 VTListMap.InsertNode(Result, IP);
5590 return Result->getSDVTList();
5593 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5594 FoldingSetNodeID ID;
5596 ID.AddInteger(VT1.getRawBits());
5597 ID.AddInteger(VT2.getRawBits());
5598 ID.AddInteger(VT3.getRawBits());
5601 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5603 EVT *Array = Allocator.Allocate<EVT>(3);
5607 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5608 VTListMap.InsertNode(Result, IP);
5610 return Result->getSDVTList();
5613 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5614 FoldingSetNodeID ID;
5616 ID.AddInteger(VT1.getRawBits());
5617 ID.AddInteger(VT2.getRawBits());
5618 ID.AddInteger(VT3.getRawBits());
5619 ID.AddInteger(VT4.getRawBits());
5622 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5624 EVT *Array = Allocator.Allocate<EVT>(4);
5629 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5630 VTListMap.InsertNode(Result, IP);
5632 return Result->getSDVTList();
5635 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5636 unsigned NumVTs = VTs.size();
5637 FoldingSetNodeID ID;
5638 ID.AddInteger(NumVTs);
5639 for (unsigned index = 0; index < NumVTs; index++) {
5640 ID.AddInteger(VTs[index].getRawBits());
5644 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5646 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5647 std::copy(VTs.begin(), VTs.end(), Array);
5648 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5649 VTListMap.InsertNode(Result, IP);
5651 return Result->getSDVTList();
5655 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5656 /// specified operands. If the resultant node already exists in the DAG,
5657 /// this does not modify the specified node, instead it returns the node that
5658 /// already exists. If the resultant node does not exist in the DAG, the
5659 /// input node is returned. As a degenerate case, if you specify the same
5660 /// input operands as the node already has, the input node is returned.
5661 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5662 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5664 // Check to see if there is no change.
5665 if (Op == N->getOperand(0)) return N;
5667 // See if the modified node already exists.
5668 void *InsertPos = nullptr;
5669 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5672 // Nope it doesn't. Remove the node from its current place in the maps.
5674 if (!RemoveNodeFromCSEMaps(N))
5675 InsertPos = nullptr;
5677 // Now we update the operands.
5678 N->OperandList[0].set(Op);
5680 // If this gets put into a CSE map, add it.
5681 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5685 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5686 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5688 // Check to see if there is no change.
5689 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5690 return N; // No operands changed, just return the input node.
5692 // See if the modified node already exists.
5693 void *InsertPos = nullptr;
5694 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5697 // Nope it doesn't. Remove the node from its current place in the maps.
5699 if (!RemoveNodeFromCSEMaps(N))
5700 InsertPos = nullptr;
5702 // Now we update the operands.
5703 if (N->OperandList[0] != Op1)
5704 N->OperandList[0].set(Op1);
5705 if (N->OperandList[1] != Op2)
5706 N->OperandList[1].set(Op2);
5708 // If this gets put into a CSE map, add it.
5709 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5713 SDNode *SelectionDAG::
5714 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5715 SDValue Ops[] = { Op1, Op2, Op3 };
5716 return UpdateNodeOperands(N, Ops);
5719 SDNode *SelectionDAG::
5720 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5721 SDValue Op3, SDValue Op4) {
5722 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5723 return UpdateNodeOperands(N, Ops);
5726 SDNode *SelectionDAG::
5727 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5728 SDValue Op3, SDValue Op4, SDValue Op5) {
5729 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5730 return UpdateNodeOperands(N, Ops);
5733 SDNode *SelectionDAG::
5734 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5735 unsigned NumOps = Ops.size();
5736 assert(N->getNumOperands() == NumOps &&
5737 "Update with wrong number of operands");
5739 // If no operands changed just return the input node.
5740 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5743 // See if the modified node already exists.
5744 void *InsertPos = nullptr;
5745 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5748 // Nope it doesn't. Remove the node from its current place in the maps.
5750 if (!RemoveNodeFromCSEMaps(N))
5751 InsertPos = nullptr;
5753 // Now we update the operands.
5754 for (unsigned i = 0; i != NumOps; ++i)
5755 if (N->OperandList[i] != Ops[i])
5756 N->OperandList[i].set(Ops[i]);
5758 // If this gets put into a CSE map, add it.
5759 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5763 /// DropOperands - Release the operands and set this node to have
5765 void SDNode::DropOperands() {
5766 // Unlike the code in MorphNodeTo that does this, we don't need to
5767 // watch for dead nodes here.
5768 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5774 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5777 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5779 SDVTList VTs = getVTList(VT);
5780 return SelectNodeTo(N, MachineOpc, VTs, None);
5783 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5784 EVT VT, SDValue Op1) {
5785 SDVTList VTs = getVTList(VT);
5786 SDValue Ops[] = { Op1 };
5787 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5790 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5791 EVT VT, SDValue Op1,
5793 SDVTList VTs = getVTList(VT);
5794 SDValue Ops[] = { Op1, Op2 };
5795 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5798 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5799 EVT VT, SDValue Op1,
5800 SDValue Op2, SDValue Op3) {
5801 SDVTList VTs = getVTList(VT);
5802 SDValue Ops[] = { Op1, Op2, Op3 };
5803 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5806 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5807 EVT VT, ArrayRef<SDValue> Ops) {
5808 SDVTList VTs = getVTList(VT);
5809 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5812 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5813 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5814 SDVTList VTs = getVTList(VT1, VT2);
5815 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5818 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5820 SDVTList VTs = getVTList(VT1, VT2);
5821 return SelectNodeTo(N, MachineOpc, VTs, None);
5824 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5825 EVT VT1, EVT VT2, EVT VT3,
5826 ArrayRef<SDValue> Ops) {
5827 SDVTList VTs = getVTList(VT1, VT2, VT3);
5828 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5831 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5832 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5833 ArrayRef<SDValue> Ops) {
5834 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5835 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5838 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5841 SDVTList VTs = getVTList(VT1, VT2);
5842 SDValue Ops[] = { Op1 };
5843 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5846 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5848 SDValue Op1, SDValue Op2) {
5849 SDVTList VTs = getVTList(VT1, VT2);
5850 SDValue Ops[] = { Op1, Op2 };
5851 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5854 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5856 SDValue Op1, SDValue Op2,
5858 SDVTList VTs = getVTList(VT1, VT2);
5859 SDValue Ops[] = { Op1, Op2, Op3 };
5860 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5863 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5864 EVT VT1, EVT VT2, EVT VT3,
5865 SDValue Op1, SDValue Op2,
5867 SDVTList VTs = getVTList(VT1, VT2, VT3);
5868 SDValue Ops[] = { Op1, Op2, Op3 };
5869 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5872 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5873 SDVTList VTs,ArrayRef<SDValue> Ops) {
5874 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5875 // Reset the NodeID to -1.
5880 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5881 /// the line number information on the merged node since it is not possible to
5882 /// preserve the information that operation is associated with multiple lines.
5883 /// This will make the debugger working better at -O0, were there is a higher
5884 /// probability having other instructions associated with that line.
5886 /// For IROrder, we keep the smaller of the two
5887 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5888 DebugLoc NLoc = N->getDebugLoc();
5889 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5890 N->setDebugLoc(DebugLoc());
5892 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5893 N->setIROrder(Order);
5897 /// MorphNodeTo - This *mutates* the specified node to have the specified
5898 /// return type, opcode, and operands.
5900 /// Note that MorphNodeTo returns the resultant node. If there is already a
5901 /// node of the specified opcode and operands, it returns that node instead of
5902 /// the current one. Note that the SDLoc need not be the same.
5904 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5905 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5906 /// node, and because it doesn't require CSE recalculation for any of
5907 /// the node's users.
5909 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5910 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5911 /// the legalizer which maintain worklists that would need to be updated when
5912 /// deleting things.
5913 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5914 SDVTList VTs, ArrayRef<SDValue> Ops) {
5915 unsigned NumOps = Ops.size();
5916 // If an identical node already exists, use it.
5918 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5919 FoldingSetNodeID ID;
5920 AddNodeIDNode(ID, Opc, VTs, Ops);
5921 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5922 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5925 if (!RemoveNodeFromCSEMaps(N))
5928 // Start the morphing.
5930 N->ValueList = VTs.VTs;
5931 N->NumValues = VTs.NumVTs;
5933 // Clear the operands list, updating used nodes to remove this from their
5934 // use list. Keep track of any operands that become dead as a result.
5935 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5936 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5938 SDNode *Used = Use.getNode();
5940 if (Used->use_empty())
5941 DeadNodeSet.insert(Used);
5944 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5945 // Initialize the memory references information.
5946 MN->setMemRefs(nullptr, nullptr);
5947 // If NumOps is larger than the # of operands we can have in a
5948 // MachineSDNode, reallocate the operand list.
5949 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5950 if (MN->OperandsNeedDelete)
5951 delete[] MN->OperandList;
5952 if (NumOps > array_lengthof(MN->LocalOperands))
5953 // We're creating a final node that will live unmorphed for the
5954 // remainder of the current SelectionDAG iteration, so we can allocate
5955 // the operands directly out of a pool with no recycling metadata.
5956 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5957 Ops.data(), NumOps);
5959 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5960 MN->OperandsNeedDelete = false;
5962 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5964 // If NumOps is larger than the # of operands we currently have, reallocate
5965 // the operand list.
5966 if (NumOps > N->NumOperands) {
5967 if (N->OperandsNeedDelete)
5968 delete[] N->OperandList;
5969 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5970 N->OperandsNeedDelete = true;
5972 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5975 // Delete any nodes that are still dead after adding the uses for the
5977 if (!DeadNodeSet.empty()) {
5978 SmallVector<SDNode *, 16> DeadNodes;
5979 for (SDNode *N : DeadNodeSet)
5981 DeadNodes.push_back(N);
5982 RemoveDeadNodes(DeadNodes);
5986 CSEMap.InsertNode(N, IP); // Memoize the new node.
5991 /// getMachineNode - These are used for target selectors to create a new node
5992 /// with specified return type(s), MachineInstr opcode, and operands.
5994 /// Note that getMachineNode returns the resultant node. If there is already a
5995 /// node of the specified opcode and operands, it returns that node instead of
5996 /// the current one.
5998 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5999 SDVTList VTs = getVTList(VT);
6000 return getMachineNode(Opcode, dl, VTs, None);
6004 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6005 SDVTList VTs = getVTList(VT);
6006 SDValue Ops[] = { Op1 };
6007 return getMachineNode(Opcode, dl, VTs, Ops);
6011 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6012 SDValue Op1, SDValue Op2) {
6013 SDVTList VTs = getVTList(VT);
6014 SDValue Ops[] = { Op1, Op2 };
6015 return getMachineNode(Opcode, dl, VTs, Ops);
6019 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6020 SDValue Op1, SDValue Op2, SDValue Op3) {
6021 SDVTList VTs = getVTList(VT);
6022 SDValue Ops[] = { Op1, Op2, Op3 };
6023 return getMachineNode(Opcode, dl, VTs, Ops);
6027 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6028 ArrayRef<SDValue> Ops) {
6029 SDVTList VTs = getVTList(VT);
6030 return getMachineNode(Opcode, dl, VTs, Ops);
6034 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6035 SDVTList VTs = getVTList(VT1, VT2);
6036 return getMachineNode(Opcode, dl, VTs, None);
6040 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6041 EVT VT1, EVT VT2, SDValue Op1) {
6042 SDVTList VTs = getVTList(VT1, VT2);
6043 SDValue Ops[] = { Op1 };
6044 return getMachineNode(Opcode, dl, VTs, Ops);
6048 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6049 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6050 SDVTList VTs = getVTList(VT1, VT2);
6051 SDValue Ops[] = { Op1, Op2 };
6052 return getMachineNode(Opcode, dl, VTs, Ops);
6056 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6057 EVT VT1, EVT VT2, SDValue Op1,
6058 SDValue Op2, SDValue Op3) {
6059 SDVTList VTs = getVTList(VT1, VT2);
6060 SDValue Ops[] = { Op1, Op2, Op3 };
6061 return getMachineNode(Opcode, dl, VTs, Ops);
6065 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6067 ArrayRef<SDValue> Ops) {
6068 SDVTList VTs = getVTList(VT1, VT2);
6069 return getMachineNode(Opcode, dl, VTs, Ops);
6073 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6074 EVT VT1, EVT VT2, EVT VT3,
6075 SDValue Op1, SDValue Op2) {
6076 SDVTList VTs = getVTList(VT1, VT2, VT3);
6077 SDValue Ops[] = { Op1, Op2 };
6078 return getMachineNode(Opcode, dl, VTs, Ops);
6082 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6083 EVT VT1, EVT VT2, EVT VT3,
6084 SDValue Op1, SDValue Op2, SDValue Op3) {
6085 SDVTList VTs = getVTList(VT1, VT2, VT3);
6086 SDValue Ops[] = { Op1, Op2, Op3 };
6087 return getMachineNode(Opcode, dl, VTs, Ops);
6091 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6092 EVT VT1, EVT VT2, EVT VT3,
6093 ArrayRef<SDValue> Ops) {
6094 SDVTList VTs = getVTList(VT1, VT2, VT3);
6095 return getMachineNode(Opcode, dl, VTs, Ops);
6099 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6100 EVT VT2, EVT VT3, EVT VT4,
6101 ArrayRef<SDValue> Ops) {
6102 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6103 return getMachineNode(Opcode, dl, VTs, Ops);
6107 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6108 ArrayRef<EVT> ResultTys,
6109 ArrayRef<SDValue> Ops) {
6110 SDVTList VTs = getVTList(ResultTys);
6111 return getMachineNode(Opcode, dl, VTs, Ops);
6115 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6116 ArrayRef<SDValue> OpsArray) {
6117 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6120 const SDValue *Ops = OpsArray.data();
6121 unsigned NumOps = OpsArray.size();
6124 FoldingSetNodeID ID;
6125 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6127 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6128 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6132 // Allocate a new MachineSDNode.
6133 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6134 DL.getDebugLoc(), VTs);
6136 // Initialize the operands list.
6137 if (NumOps > array_lengthof(N->LocalOperands))
6138 // We're creating a final node that will live unmorphed for the
6139 // remainder of the current SelectionDAG iteration, so we can allocate
6140 // the operands directly out of a pool with no recycling metadata.
6141 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6144 N->InitOperands(N->LocalOperands, Ops, NumOps);
6145 N->OperandsNeedDelete = false;
6148 CSEMap.InsertNode(N, IP);
6154 /// getTargetExtractSubreg - A convenience function for creating
6155 /// TargetOpcode::EXTRACT_SUBREG nodes.
6157 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6159 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6160 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6161 VT, Operand, SRIdxVal);
6162 return SDValue(Subreg, 0);
6165 /// getTargetInsertSubreg - A convenience function for creating
6166 /// TargetOpcode::INSERT_SUBREG nodes.
6168 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6169 SDValue Operand, SDValue Subreg) {
6170 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6171 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6172 VT, Operand, Subreg, SRIdxVal);
6173 return SDValue(Result, 0);
6176 /// getNodeIfExists - Get the specified node if it's already available, or
6177 /// else return NULL.
6178 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6179 ArrayRef<SDValue> Ops,
6180 const SDNodeFlags *Flags) {
6181 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6182 FoldingSetNodeID ID;
6183 AddNodeIDNode(ID, Opcode, VTList, Ops);
6184 AddNodeIDFlags(ID, Opcode, Flags);
6186 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6192 /// getDbgValue - Creates a SDDbgValue node.
6195 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6196 unsigned R, bool IsIndirect, uint64_t Off,
6197 DebugLoc DL, unsigned O) {
6198 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6199 "Expected inlined-at fields to agree");
6200 return new (DbgInfo->getAlloc())
6201 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6205 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6206 const Value *C, uint64_t Off,
6207 DebugLoc DL, unsigned O) {
6208 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6209 "Expected inlined-at fields to agree");
6210 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6214 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6215 unsigned FI, uint64_t Off,
6216 DebugLoc DL, unsigned O) {
6217 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6218 "Expected inlined-at fields to agree");
6219 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6224 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6225 /// pointed to by a use iterator is deleted, increment the use iterator
6226 /// so that it doesn't dangle.
6228 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6229 SDNode::use_iterator &UI;
6230 SDNode::use_iterator &UE;
6232 void NodeDeleted(SDNode *N, SDNode *E) override {
6233 // Increment the iterator as needed.
6234 while (UI != UE && N == *UI)
6239 RAUWUpdateListener(SelectionDAG &d,
6240 SDNode::use_iterator &ui,
6241 SDNode::use_iterator &ue)
6242 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6247 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6248 /// This can cause recursive merging of nodes in the DAG.
6250 /// This version assumes From has a single result value.
6252 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6253 SDNode *From = FromN.getNode();
6254 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6255 "Cannot replace with this method!");
6256 assert(From != To.getNode() && "Cannot replace uses of with self");
6258 // Iterate over all the existing uses of From. New uses will be added
6259 // to the beginning of the use list, which we avoid visiting.
6260 // This specifically avoids visiting uses of From that arise while the
6261 // replacement is happening, because any such uses would be the result
6262 // of CSE: If an existing node looks like From after one of its operands
6263 // is replaced by To, we don't want to replace of all its users with To
6264 // too. See PR3018 for more info.
6265 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6266 RAUWUpdateListener Listener(*this, UI, UE);
6270 // This node is about to morph, remove its old self from the CSE maps.
6271 RemoveNodeFromCSEMaps(User);
6273 // A user can appear in a use list multiple times, and when this
6274 // happens the uses are usually next to each other in the list.
6275 // To help reduce the number of CSE recomputations, process all
6276 // the uses of this user that we can find this way.
6278 SDUse &Use = UI.getUse();
6281 } while (UI != UE && *UI == User);
6283 // Now that we have modified User, add it back to the CSE maps. If it
6284 // already exists there, recursively merge the results together.
6285 AddModifiedNodeToCSEMaps(User);
6288 // If we just RAUW'd the root, take note.
6289 if (FromN == getRoot())
6293 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6294 /// This can cause recursive merging of nodes in the DAG.
6296 /// This version assumes that for each value of From, there is a
6297 /// corresponding value in To in the same position with the same type.
6299 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6301 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6302 assert((!From->hasAnyUseOfValue(i) ||
6303 From->getValueType(i) == To->getValueType(i)) &&
6304 "Cannot use this version of ReplaceAllUsesWith!");
6307 // Handle the trivial case.
6311 // Iterate over just the existing users of From. See the comments in
6312 // the ReplaceAllUsesWith above.
6313 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6314 RAUWUpdateListener Listener(*this, UI, UE);
6318 // This node is about to morph, remove its old self from the CSE maps.
6319 RemoveNodeFromCSEMaps(User);
6321 // A user can appear in a use list multiple times, and when this
6322 // happens the uses are usually next to each other in the list.
6323 // To help reduce the number of CSE recomputations, process all
6324 // the uses of this user that we can find this way.
6326 SDUse &Use = UI.getUse();
6329 } while (UI != UE && *UI == User);
6331 // Now that we have modified User, add it back to the CSE maps. If it
6332 // already exists there, recursively merge the results together.
6333 AddModifiedNodeToCSEMaps(User);
6336 // If we just RAUW'd the root, take note.
6337 if (From == getRoot().getNode())
6338 setRoot(SDValue(To, getRoot().getResNo()));
6341 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6342 /// This can cause recursive merging of nodes in the DAG.
6344 /// This version can replace From with any result values. To must match the
6345 /// number and types of values returned by From.
6346 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6347 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6348 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6350 // Iterate over just the existing users of From. See the comments in
6351 // the ReplaceAllUsesWith above.
6352 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6353 RAUWUpdateListener Listener(*this, UI, UE);
6357 // This node is about to morph, remove its old self from the CSE maps.
6358 RemoveNodeFromCSEMaps(User);
6360 // A user can appear in a use list multiple times, and when this
6361 // happens the uses are usually next to each other in the list.
6362 // To help reduce the number of CSE recomputations, process all
6363 // the uses of this user that we can find this way.
6365 SDUse &Use = UI.getUse();
6366 const SDValue &ToOp = To[Use.getResNo()];
6369 } while (UI != UE && *UI == User);
6371 // Now that we have modified User, add it back to the CSE maps. If it
6372 // already exists there, recursively merge the results together.
6373 AddModifiedNodeToCSEMaps(User);
6376 // If we just RAUW'd the root, take note.
6377 if (From == getRoot().getNode())
6378 setRoot(SDValue(To[getRoot().getResNo()]));
6381 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6382 /// uses of other values produced by From.getNode() alone. The Deleted
6383 /// vector is handled the same way as for ReplaceAllUsesWith.
6384 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6385 // Handle the really simple, really trivial case efficiently.
6386 if (From == To) return;
6388 // Handle the simple, trivial, case efficiently.
6389 if (From.getNode()->getNumValues() == 1) {
6390 ReplaceAllUsesWith(From, To);
6394 // Iterate over just the existing users of From. See the comments in
6395 // the ReplaceAllUsesWith above.
6396 SDNode::use_iterator UI = From.getNode()->use_begin(),
6397 UE = From.getNode()->use_end();
6398 RAUWUpdateListener Listener(*this, UI, UE);
6401 bool UserRemovedFromCSEMaps = false;
6403 // A user can appear in a use list multiple times, and when this
6404 // happens the uses are usually next to each other in the list.
6405 // To help reduce the number of CSE recomputations, process all
6406 // the uses of this user that we can find this way.
6408 SDUse &Use = UI.getUse();
6410 // Skip uses of different values from the same node.
6411 if (Use.getResNo() != From.getResNo()) {
6416 // If this node hasn't been modified yet, it's still in the CSE maps,
6417 // so remove its old self from the CSE maps.
6418 if (!UserRemovedFromCSEMaps) {
6419 RemoveNodeFromCSEMaps(User);
6420 UserRemovedFromCSEMaps = true;
6425 } while (UI != UE && *UI == User);
6427 // We are iterating over all uses of the From node, so if a use
6428 // doesn't use the specific value, no changes are made.
6429 if (!UserRemovedFromCSEMaps)
6432 // Now that we have modified User, add it back to the CSE maps. If it
6433 // already exists there, recursively merge the results together.
6434 AddModifiedNodeToCSEMaps(User);
6437 // If we just RAUW'd the root, take note.
6438 if (From == getRoot())
6443 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6444 /// to record information about a use.
6451 /// operator< - Sort Memos by User.
6452 bool operator<(const UseMemo &L, const UseMemo &R) {
6453 return (intptr_t)L.User < (intptr_t)R.User;
6457 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6458 /// uses of other values produced by From.getNode() alone. The same value
6459 /// may appear in both the From and To list. The Deleted vector is
6460 /// handled the same way as for ReplaceAllUsesWith.
6461 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6464 // Handle the simple, trivial case efficiently.
6466 return ReplaceAllUsesOfValueWith(*From, *To);
6468 // Read up all the uses and make records of them. This helps
6469 // processing new uses that are introduced during the
6470 // replacement process.
6471 SmallVector<UseMemo, 4> Uses;
6472 for (unsigned i = 0; i != Num; ++i) {
6473 unsigned FromResNo = From[i].getResNo();
6474 SDNode *FromNode = From[i].getNode();
6475 for (SDNode::use_iterator UI = FromNode->use_begin(),
6476 E = FromNode->use_end(); UI != E; ++UI) {
6477 SDUse &Use = UI.getUse();
6478 if (Use.getResNo() == FromResNo) {
6479 UseMemo Memo = { *UI, i, &Use };
6480 Uses.push_back(Memo);
6485 // Sort the uses, so that all the uses from a given User are together.
6486 std::sort(Uses.begin(), Uses.end());
6488 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6489 UseIndex != UseIndexEnd; ) {
6490 // We know that this user uses some value of From. If it is the right
6491 // value, update it.
6492 SDNode *User = Uses[UseIndex].User;
6494 // This node is about to morph, remove its old self from the CSE maps.
6495 RemoveNodeFromCSEMaps(User);
6497 // The Uses array is sorted, so all the uses for a given User
6498 // are next to each other in the list.
6499 // To help reduce the number of CSE recomputations, process all
6500 // the uses of this user that we can find this way.
6502 unsigned i = Uses[UseIndex].Index;
6503 SDUse &Use = *Uses[UseIndex].Use;
6507 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6509 // Now that we have modified User, add it back to the CSE maps. If it
6510 // already exists there, recursively merge the results together.
6511 AddModifiedNodeToCSEMaps(User);
6515 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6516 /// based on their topological order. It returns the maximum id and a vector
6517 /// of the SDNodes* in assigned order by reference.
6518 unsigned SelectionDAG::AssignTopologicalOrder() {
6520 unsigned DAGSize = 0;
6522 // SortedPos tracks the progress of the algorithm. Nodes before it are
6523 // sorted, nodes after it are unsorted. When the algorithm completes
6524 // it is at the end of the list.
6525 allnodes_iterator SortedPos = allnodes_begin();
6527 // Visit all the nodes. Move nodes with no operands to the front of
6528 // the list immediately. Annotate nodes that do have operands with their
6529 // operand count. Before we do this, the Node Id fields of the nodes
6530 // may contain arbitrary values. After, the Node Id fields for nodes
6531 // before SortedPos will contain the topological sort index, and the
6532 // Node Id fields for nodes At SortedPos and after will contain the
6533 // count of outstanding operands.
6534 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6536 checkForCycles(N, this);
6537 unsigned Degree = N->getNumOperands();
6539 // A node with no uses, add it to the result array immediately.
6540 N->setNodeId(DAGSize++);
6541 allnodes_iterator Q = N;
6543 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6544 assert(SortedPos != AllNodes.end() && "Overran node list");
6547 // Temporarily use the Node Id as scratch space for the degree count.
6548 N->setNodeId(Degree);
6552 // Visit all the nodes. As we iterate, move nodes into sorted order,
6553 // such that by the time the end is reached all nodes will be sorted.
6554 for (SDNode &Node : allnodes()) {
6556 checkForCycles(N, this);
6557 // N is in sorted position, so all its uses have one less operand
6558 // that needs to be sorted.
6559 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6562 unsigned Degree = P->getNodeId();
6563 assert(Degree != 0 && "Invalid node degree");
6566 // All of P's operands are sorted, so P may sorted now.
6567 P->setNodeId(DAGSize++);
6569 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6570 assert(SortedPos != AllNodes.end() && "Overran node list");
6573 // Update P's outstanding operand count.
6574 P->setNodeId(Degree);
6577 if (&Node == SortedPos) {
6579 allnodes_iterator I = N;
6581 dbgs() << "Overran sorted position:\n";
6582 S->dumprFull(this); dbgs() << "\n";
6583 dbgs() << "Checking if this is due to cycles\n";
6584 checkForCycles(this, true);
6586 llvm_unreachable(nullptr);
6590 assert(SortedPos == AllNodes.end() &&
6591 "Topological sort incomplete!");
6592 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6593 "First node in topological sort is not the entry token!");
6594 assert(AllNodes.front().getNodeId() == 0 &&
6595 "First node in topological sort has non-zero id!");
6596 assert(AllNodes.front().getNumOperands() == 0 &&
6597 "First node in topological sort has operands!");
6598 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6599 "Last node in topologic sort has unexpected id!");
6600 assert(AllNodes.back().use_empty() &&
6601 "Last node in topologic sort has users!");
6602 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6606 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6607 /// value is produced by SD.
6608 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6610 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6611 SD->setHasDebugValue(true);
6613 DbgInfo->add(DB, SD, isParameter);
6616 /// TransferDbgValues - Transfer SDDbgValues.
6617 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6618 if (From == To || !From.getNode()->getHasDebugValue())
6620 SDNode *FromNode = From.getNode();
6621 SDNode *ToNode = To.getNode();
6622 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6623 SmallVector<SDDbgValue *, 2> ClonedDVs;
6624 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6626 SDDbgValue *Dbg = *I;
6627 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6629 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6630 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6631 Dbg->getDebugLoc(), Dbg->getOrder());
6632 ClonedDVs.push_back(Clone);
6635 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6636 E = ClonedDVs.end(); I != E; ++I)
6637 AddDbgValue(*I, ToNode, false);
6640 //===----------------------------------------------------------------------===//
6642 //===----------------------------------------------------------------------===//
6644 HandleSDNode::~HandleSDNode() {
6648 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6649 DebugLoc DL, const GlobalValue *GA,
6650 EVT VT, int64_t o, unsigned char TF)
6651 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6655 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6656 SDValue X, unsigned SrcAS,
6658 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6659 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6661 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6662 EVT memvt, MachineMemOperand *mmo)
6663 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6664 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6665 MMO->isNonTemporal(), MMO->isInvariant());
6666 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6667 assert(isNonTemporal() == MMO->isNonTemporal() &&
6668 "Non-temporal encoding error!");
6669 // We check here that the size of the memory operand fits within the size of
6670 // the MMO. This is because the MMO might indicate only a possible address
6671 // range instead of specifying the affected memory addresses precisely.
6672 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6675 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6676 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6677 : SDNode(Opc, Order, dl, VTs, Ops),
6678 MemoryVT(memvt), MMO(mmo) {
6679 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6680 MMO->isNonTemporal(), MMO->isInvariant());
6681 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6682 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6685 /// Profile - Gather unique data for the node.
6687 void SDNode::Profile(FoldingSetNodeID &ID) const {
6688 AddNodeIDNode(ID, this);
6693 std::vector<EVT> VTs;
6696 VTs.reserve(MVT::LAST_VALUETYPE);
6697 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6698 VTs.push_back(MVT((MVT::SimpleValueType)i));
6703 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6704 static ManagedStatic<EVTArray> SimpleVTArray;
6705 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6707 /// getValueTypeList - Return a pointer to the specified value type.
6709 const EVT *SDNode::getValueTypeList(EVT VT) {
6710 if (VT.isExtended()) {
6711 sys::SmartScopedLock<true> Lock(*VTMutex);
6712 return &(*EVTs->insert(VT).first);
6714 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6715 "Value type out of range!");
6716 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6720 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6721 /// indicated value. This method ignores uses of other values defined by this
6723 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6724 assert(Value < getNumValues() && "Bad value!");
6726 // TODO: Only iterate over uses of a given value of the node
6727 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6728 if (UI.getUse().getResNo() == Value) {
6735 // Found exactly the right number of uses?
6740 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6741 /// value. This method ignores uses of other values defined by this operation.
6742 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6743 assert(Value < getNumValues() && "Bad value!");
6745 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6746 if (UI.getUse().getResNo() == Value)
6753 /// isOnlyUserOf - Return true if this node is the only use of N.
6755 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6757 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6768 /// isOperand - Return true if this node is an operand of N.
6770 bool SDValue::isOperandOf(const SDNode *N) const {
6771 for (const SDValue &Op : N->op_values())
6777 bool SDNode::isOperandOf(const SDNode *N) const {
6778 for (const SDValue &Op : N->op_values())
6779 if (this == Op.getNode())
6784 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6785 /// be a chain) reaches the specified operand without crossing any
6786 /// side-effecting instructions on any chain path. In practice, this looks
6787 /// through token factors and non-volatile loads. In order to remain efficient,
6788 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6789 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6790 unsigned Depth) const {
6791 if (*this == Dest) return true;
6793 // Don't search too deeply, we just want to be able to see through
6794 // TokenFactor's etc.
6795 if (Depth == 0) return false;
6797 // If this is a token factor, all inputs to the TF happen in parallel. If any
6798 // of the operands of the TF does not reach dest, then we cannot do the xform.
6799 if (getOpcode() == ISD::TokenFactor) {
6800 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6801 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6806 // Loads don't have side effects, look through them.
6807 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6808 if (!Ld->isVolatile())
6809 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6814 /// hasPredecessor - Return true if N is a predecessor of this node.
6815 /// N is either an operand of this node, or can be reached by recursively
6816 /// traversing up the operands.
6817 /// NOTE: This is an expensive method. Use it carefully.
6818 bool SDNode::hasPredecessor(const SDNode *N) const {
6819 SmallPtrSet<const SDNode *, 32> Visited;
6820 SmallVector<const SDNode *, 16> Worklist;
6821 return hasPredecessorHelper(N, Visited, Worklist);
6825 SDNode::hasPredecessorHelper(const SDNode *N,
6826 SmallPtrSetImpl<const SDNode *> &Visited,
6827 SmallVectorImpl<const SDNode *> &Worklist) const {
6828 if (Visited.empty()) {
6829 Worklist.push_back(this);
6831 // Take a look in the visited set. If we've already encountered this node
6832 // we needn't search further.
6833 if (Visited.count(N))
6837 // Haven't visited N yet. Continue the search.
6838 while (!Worklist.empty()) {
6839 const SDNode *M = Worklist.pop_back_val();
6840 for (const SDValue &OpV : M->op_values()) {
6841 SDNode *Op = OpV.getNode();
6842 if (Visited.insert(Op).second)
6843 Worklist.push_back(Op);
6852 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6853 assert(Num < NumOperands && "Invalid child # of SDNode!");
6854 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6857 const SDNodeFlags *SDNode::getFlags() const {
6858 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6859 return &FlagsNode->Flags;
6863 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6864 assert(N->getNumValues() == 1 &&
6865 "Can't unroll a vector with multiple results!");
6867 EVT VT = N->getValueType(0);
6868 unsigned NE = VT.getVectorNumElements();
6869 EVT EltVT = VT.getVectorElementType();
6872 SmallVector<SDValue, 8> Scalars;
6873 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6875 // If ResNE is 0, fully unroll the vector op.
6878 else if (NE > ResNE)
6882 for (i= 0; i != NE; ++i) {
6883 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6884 SDValue Operand = N->getOperand(j);
6885 EVT OperandVT = Operand.getValueType();
6886 if (OperandVT.isVector()) {
6887 // A vector operand; extract a single element.
6888 EVT OperandEltVT = OperandVT.getVectorElementType();
6890 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6891 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6893 // A scalar operand; just use it as is.
6894 Operands[j] = Operand;
6898 switch (N->getOpcode()) {
6900 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6905 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6912 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6913 getShiftAmountOperand(Operands[0].getValueType(),
6916 case ISD::SIGN_EXTEND_INREG:
6917 case ISD::FP_ROUND_INREG: {
6918 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6919 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6921 getValueType(ExtVT)));
6926 for (; i < ResNE; ++i)
6927 Scalars.push_back(getUNDEF(EltVT));
6929 return getNode(ISD::BUILD_VECTOR, dl,
6930 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6934 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6935 /// location that is 'Dist' units away from the location that the 'Base' load
6936 /// is loading from.
6937 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6938 unsigned Bytes, int Dist) const {
6939 if (LD->getChain() != Base->getChain())
6941 EVT VT = LD->getValueType(0);
6942 if (VT.getSizeInBits() / 8 != Bytes)
6945 SDValue Loc = LD->getOperand(1);
6946 SDValue BaseLoc = Base->getOperand(1);
6947 if (Loc.getOpcode() == ISD::FrameIndex) {
6948 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6950 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6951 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6952 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6953 int FS = MFI->getObjectSize(FI);
6954 int BFS = MFI->getObjectSize(BFI);
6955 if (FS != BFS || FS != (int)Bytes) return false;
6956 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6960 if (isBaseWithConstantOffset(Loc)) {
6961 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6962 if (Loc.getOperand(0) == BaseLoc) {
6963 // If the base location is a simple address with no offset itself, then
6964 // the second load's first add operand should be the base address.
6965 if (LocOffset == Dist * (int)Bytes)
6967 } else if (isBaseWithConstantOffset(BaseLoc)) {
6968 // The base location itself has an offset, so subtract that value from the
6969 // second load's offset before comparing to distance * size.
6971 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6972 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6973 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6978 const GlobalValue *GV1 = nullptr;
6979 const GlobalValue *GV2 = nullptr;
6980 int64_t Offset1 = 0;
6981 int64_t Offset2 = 0;
6982 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6983 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6984 if (isGA1 && isGA2 && GV1 == GV2)
6985 return Offset1 == (Offset2 + Dist*Bytes);
6990 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6991 /// it cannot be inferred.
6992 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6993 // If this is a GlobalAddress + cst, return the alignment.
6994 const GlobalValue *GV;
6995 int64_t GVOffset = 0;
6996 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6997 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6998 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6999 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7001 unsigned AlignBits = KnownZero.countTrailingOnes();
7002 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7004 return MinAlign(Align, GVOffset);
7007 // If this is a direct reference to a stack slot, use information about the
7008 // stack slot's alignment.
7009 int FrameIdx = 1 << 31;
7010 int64_t FrameOffset = 0;
7011 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7012 FrameIdx = FI->getIndex();
7013 } else if (isBaseWithConstantOffset(Ptr) &&
7014 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7016 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7017 FrameOffset = Ptr.getConstantOperandVal(1);
7020 if (FrameIdx != (1 << 31)) {
7021 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7022 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7030 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7031 /// which is split (or expanded) into two not necessarily identical pieces.
7032 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7033 // Currently all types are split in half.
7035 if (!VT.isVector()) {
7036 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7038 unsigned NumElements = VT.getVectorNumElements();
7039 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7040 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7043 return std::make_pair(LoVT, HiVT);
7046 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7048 std::pair<SDValue, SDValue>
7049 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7051 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7052 N.getValueType().getVectorNumElements() &&
7053 "More vector elements requested than available!");
7055 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7056 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7057 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7058 getConstant(LoVT.getVectorNumElements(), DL,
7059 TLI->getVectorIdxTy(getDataLayout())));
7060 return std::make_pair(Lo, Hi);
7063 void SelectionDAG::ExtractVectorElements(SDValue Op,
7064 SmallVectorImpl<SDValue> &Args,
7065 unsigned Start, unsigned Count) {
7066 EVT VT = Op.getValueType();
7068 Count = VT.getVectorNumElements();
7070 EVT EltVT = VT.getVectorElementType();
7071 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7073 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7074 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7075 Op, getConstant(i, SL, IdxTy)));
7079 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7080 unsigned GlobalAddressSDNode::getAddressSpace() const {
7081 return getGlobal()->getType()->getAddressSpace();
7085 Type *ConstantPoolSDNode::getType() const {
7086 if (isMachineConstantPoolEntry())
7087 return Val.MachineCPVal->getType();
7088 return Val.ConstVal->getType();
7091 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7093 unsigned &SplatBitSize,
7095 unsigned MinSplatBits,
7096 bool isBigEndian) const {
7097 EVT VT = getValueType(0);
7098 assert(VT.isVector() && "Expected a vector type");
7099 unsigned sz = VT.getSizeInBits();
7100 if (MinSplatBits > sz)
7103 SplatValue = APInt(sz, 0);
7104 SplatUndef = APInt(sz, 0);
7106 // Get the bits. Bits with undefined values (when the corresponding element
7107 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7108 // in SplatValue. If any of the values are not constant, give up and return
7110 unsigned int nOps = getNumOperands();
7111 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7112 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7114 for (unsigned j = 0; j < nOps; ++j) {
7115 unsigned i = isBigEndian ? nOps-1-j : j;
7116 SDValue OpVal = getOperand(i);
7117 unsigned BitPos = j * EltBitSize;
7119 if (OpVal.getOpcode() == ISD::UNDEF)
7120 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7121 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7122 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7123 zextOrTrunc(sz) << BitPos;
7124 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7125 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7130 // The build_vector is all constants or undefs. Find the smallest element
7131 // size that splats the vector.
7133 HasAnyUndefs = (SplatUndef != 0);
7136 unsigned HalfSize = sz / 2;
7137 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7138 APInt LowValue = SplatValue.trunc(HalfSize);
7139 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7140 APInt LowUndef = SplatUndef.trunc(HalfSize);
7142 // If the two halves do not match (ignoring undef bits), stop here.
7143 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7144 MinSplatBits > HalfSize)
7147 SplatValue = HighValue | LowValue;
7148 SplatUndef = HighUndef & LowUndef;
7157 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7158 if (UndefElements) {
7159 UndefElements->clear();
7160 UndefElements->resize(getNumOperands());
7163 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7164 SDValue Op = getOperand(i);
7165 if (Op.getOpcode() == ISD::UNDEF) {
7167 (*UndefElements)[i] = true;
7168 } else if (!Splatted) {
7170 } else if (Splatted != Op) {
7176 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7177 "Can only have a splat without a constant for all undefs.");
7178 return getOperand(0);
7185 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7186 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7190 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7191 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7195 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7196 uint32_t BitWidth) const {
7197 if (ConstantFPSDNode *CN =
7198 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7200 APSInt IntVal(BitWidth);
7201 APFloat APF = CN->getValueAPF();
7202 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7207 return IntVal.exactLogBase2();
7212 bool BuildVectorSDNode::isConstant() const {
7213 for (const SDValue &Op : op_values()) {
7214 unsigned Opc = Op.getOpcode();
7215 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7221 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7222 // Find the first non-undef value in the shuffle mask.
7224 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7227 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7229 // Make sure all remaining elements are either undef or the same as the first
7231 for (int Idx = Mask[i]; i != e; ++i)
7232 if (Mask[i] >= 0 && Mask[i] != Idx)
7238 static void checkForCyclesHelper(const SDNode *N,
7239 SmallPtrSetImpl<const SDNode*> &Visited,
7240 SmallPtrSetImpl<const SDNode*> &Checked,
7241 const llvm::SelectionDAG *DAG) {
7242 // If this node has already been checked, don't check it again.
7243 if (Checked.count(N))
7246 // If a node has already been visited on this depth-first walk, reject it as
7248 if (!Visited.insert(N).second) {
7249 errs() << "Detected cycle in SelectionDAG\n";
7250 dbgs() << "Offending node:\n";
7251 N->dumprFull(DAG); dbgs() << "\n";
7255 for (const SDValue &Op : N->op_values())
7256 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7263 void llvm::checkForCycles(const llvm::SDNode *N,
7264 const llvm::SelectionDAG *DAG,
7272 assert(N && "Checking nonexistent SDNode");
7273 SmallPtrSet<const SDNode*, 32> visited;
7274 SmallPtrSet<const SDNode*, 32> checked;
7275 checkForCyclesHelper(N, visited, checked, DAG);
7280 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7281 checkForCycles(DAG->getRoot().getNode(), DAG, force);