1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 if (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 if (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// isScalarToVector - Return true if the specified node is a
200 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
201 /// element is not an undef.
202 bool ISD::isScalarToVector(const SDNode *N) {
203 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
206 if (N->getOpcode() != ISD::BUILD_VECTOR)
208 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
210 unsigned NumElems = N->getNumOperands();
213 for (unsigned i = 1; i < NumElems; ++i) {
214 SDValue V = N->getOperand(i);
215 if (V.getOpcode() != ISD::UNDEF)
221 /// allOperandsUndef - Return true if the node has at least one operand
222 /// and all operands of the specified node are ISD::UNDEF.
223 bool ISD::allOperandsUndef(const SDNode *N) {
224 // Return false if the node has no operands.
225 // This is "logically inconsistent" with the definition of "all" but
226 // is probably the desired behavior.
227 if (N->getNumOperands() == 0)
230 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
231 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
237 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
240 return ISD::ANY_EXTEND;
242 return ISD::SIGN_EXTEND;
244 return ISD::ZERO_EXTEND;
249 llvm_unreachable("Invalid LoadExtType");
252 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
253 /// when given the operation for (X op Y).
254 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
255 // To perform this operation, we just need to swap the L and G bits of the
257 unsigned OldL = (Operation >> 2) & 1;
258 unsigned OldG = (Operation >> 1) & 1;
259 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
260 (OldL << 1) | // New G bit
261 (OldG << 2)); // New L bit.
264 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
265 /// 'op' is a valid SetCC operation.
266 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
267 unsigned Operation = Op;
269 Operation ^= 7; // Flip L, G, E bits, but not U.
271 Operation ^= 15; // Flip all of the condition bits.
273 if (Operation > ISD::SETTRUE2)
274 Operation &= ~8; // Don't let N and U bits get set.
276 return ISD::CondCode(Operation);
280 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
281 /// signed operation and 2 if the result is an unsigned comparison. Return zero
282 /// if the operation does not depend on the sign of the input (setne and seteq).
283 static int isSignedOp(ISD::CondCode Opcode) {
285 default: llvm_unreachable("Illegal integer setcc operation!");
287 case ISD::SETNE: return 0;
291 case ISD::SETGE: return 1;
295 case ISD::SETUGE: return 2;
299 /// getSetCCOrOperation - Return the result of a logical OR between different
300 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
301 /// returns SETCC_INVALID if it is not possible to represent the resultant
303 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
305 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
306 // Cannot fold a signed integer setcc with an unsigned integer setcc.
307 return ISD::SETCC_INVALID;
309 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
311 // If the N and U bits get set then the resultant comparison DOES suddenly
312 // care about orderedness, and is true when ordered.
313 if (Op > ISD::SETTRUE2)
314 Op &= ~16; // Clear the U bit if the N bit is set.
316 // Canonicalize illegal integer setcc's.
317 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
320 return ISD::CondCode(Op);
323 /// getSetCCAndOperation - Return the result of a logical AND between different
324 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
325 /// function returns zero if it is not possible to represent the resultant
327 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
329 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
330 // Cannot fold a signed setcc with an unsigned setcc.
331 return ISD::SETCC_INVALID;
333 // Combine all of the condition bits.
334 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
336 // Canonicalize illegal integer setcc's.
340 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
341 case ISD::SETOEQ: // SETEQ & SETU[LG]E
342 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
343 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
344 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
351 //===----------------------------------------------------------------------===//
352 // SDNode Profile Support
353 //===----------------------------------------------------------------------===//
355 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
357 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
361 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
362 /// solely with their pointer.
363 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
364 ID.AddPointer(VTList.VTs);
367 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
369 static void AddNodeIDOperands(FoldingSetNodeID &ID,
370 ArrayRef<SDValue> Ops) {
371 for (auto& Op : Ops) {
372 ID.AddPointer(Op.getNode());
373 ID.AddInteger(Op.getResNo());
377 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
379 static void AddNodeIDOperands(FoldingSetNodeID &ID,
380 ArrayRef<SDUse> Ops) {
381 for (auto& Op : Ops) {
382 ID.AddPointer(Op.getNode());
383 ID.AddInteger(Op.getResNo());
387 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
391 ID.AddBoolean(exact);
394 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
395 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
396 bool nuw, bool nsw, bool exact) {
397 if (isBinOpWithFlags(Opcode))
398 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
401 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
402 SDVTList VTList, ArrayRef<SDValue> OpList) {
403 AddNodeIDOpcode(ID, OpC);
404 AddNodeIDValueTypes(ID, VTList);
405 AddNodeIDOperands(ID, OpList);
408 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
410 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
411 switch (N->getOpcode()) {
412 case ISD::TargetExternalSymbol:
413 case ISD::ExternalSymbol:
414 llvm_unreachable("Should only be used on nodes with operands");
415 default: break; // Normal nodes don't need extra info.
416 case ISD::TargetConstant:
417 case ISD::Constant: {
418 const ConstantSDNode *C = cast<ConstantSDNode>(N);
419 ID.AddPointer(C->getConstantIntValue());
420 ID.AddBoolean(C->isOpaque());
423 case ISD::TargetConstantFP:
424 case ISD::ConstantFP: {
425 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
428 case ISD::TargetGlobalAddress:
429 case ISD::GlobalAddress:
430 case ISD::TargetGlobalTLSAddress:
431 case ISD::GlobalTLSAddress: {
432 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
433 ID.AddPointer(GA->getGlobal());
434 ID.AddInteger(GA->getOffset());
435 ID.AddInteger(GA->getTargetFlags());
436 ID.AddInteger(GA->getAddressSpace());
439 case ISD::BasicBlock:
440 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
443 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
445 case ISD::RegisterMask:
446 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
449 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
451 case ISD::FrameIndex:
452 case ISD::TargetFrameIndex:
453 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
456 case ISD::TargetJumpTable:
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
458 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
460 case ISD::ConstantPool:
461 case ISD::TargetConstantPool: {
462 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
463 ID.AddInteger(CP->getAlignment());
464 ID.AddInteger(CP->getOffset());
465 if (CP->isMachineConstantPoolEntry())
466 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
468 ID.AddPointer(CP->getConstVal());
469 ID.AddInteger(CP->getTargetFlags());
472 case ISD::TargetIndex: {
473 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
474 ID.AddInteger(TI->getIndex());
475 ID.AddInteger(TI->getOffset());
476 ID.AddInteger(TI->getTargetFlags());
480 const LoadSDNode *LD = cast<LoadSDNode>(N);
481 ID.AddInteger(LD->getMemoryVT().getRawBits());
482 ID.AddInteger(LD->getRawSubclassData());
483 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
487 const StoreSDNode *ST = cast<StoreSDNode>(N);
488 ID.AddInteger(ST->getMemoryVT().getRawBits());
489 ID.AddInteger(ST->getRawSubclassData());
490 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
501 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
502 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
503 BinNode->hasNoSignedWrap(), BinNode->isExact());
506 case ISD::ATOMIC_CMP_SWAP:
507 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
508 case ISD::ATOMIC_SWAP:
509 case ISD::ATOMIC_LOAD_ADD:
510 case ISD::ATOMIC_LOAD_SUB:
511 case ISD::ATOMIC_LOAD_AND:
512 case ISD::ATOMIC_LOAD_OR:
513 case ISD::ATOMIC_LOAD_XOR:
514 case ISD::ATOMIC_LOAD_NAND:
515 case ISD::ATOMIC_LOAD_MIN:
516 case ISD::ATOMIC_LOAD_MAX:
517 case ISD::ATOMIC_LOAD_UMIN:
518 case ISD::ATOMIC_LOAD_UMAX:
519 case ISD::ATOMIC_LOAD:
520 case ISD::ATOMIC_STORE: {
521 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
522 ID.AddInteger(AT->getMemoryVT().getRawBits());
523 ID.AddInteger(AT->getRawSubclassData());
524 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
527 case ISD::PREFETCH: {
528 const MemSDNode *PF = cast<MemSDNode>(N);
529 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
532 case ISD::VECTOR_SHUFFLE: {
533 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
534 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
536 ID.AddInteger(SVN->getMaskElt(i));
539 case ISD::TargetBlockAddress:
540 case ISD::BlockAddress: {
541 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
542 ID.AddPointer(BA->getBlockAddress());
543 ID.AddInteger(BA->getOffset());
544 ID.AddInteger(BA->getTargetFlags());
547 } // end switch (N->getOpcode())
549 // Target specific memory nodes could also have address spaces to check.
550 if (N->isTargetMemoryOpcode())
551 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
554 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
556 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
557 AddNodeIDOpcode(ID, N->getOpcode());
558 // Add the return value info.
559 AddNodeIDValueTypes(ID, N->getVTList());
560 // Add the operand info.
561 AddNodeIDOperands(ID, N->ops());
563 // Handle SDNode leafs with special info.
564 AddNodeIDCustom(ID, N);
567 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
568 /// the CSE map that carries volatility, temporalness, indexing mode, and
569 /// extension/truncation information.
571 static inline unsigned
572 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
573 bool isNonTemporal, bool isInvariant) {
574 assert((ConvType & 3) == ConvType &&
575 "ConvType may not require more than 2 bits!");
576 assert((AM & 7) == AM &&
577 "AM may not require more than 3 bits!");
581 (isNonTemporal << 6) |
585 //===----------------------------------------------------------------------===//
586 // SelectionDAG Class
587 //===----------------------------------------------------------------------===//
589 /// doNotCSE - Return true if CSE should not be performed for this node.
590 static bool doNotCSE(SDNode *N) {
591 if (N->getValueType(0) == MVT::Glue)
592 return true; // Never CSE anything that produces a flag.
594 switch (N->getOpcode()) {
596 case ISD::HANDLENODE:
598 return true; // Never CSE these nodes.
601 // Check that remaining values produced are not flags.
602 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
603 if (N->getValueType(i) == MVT::Glue)
604 return true; // Never CSE anything that produces a flag.
609 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
611 void SelectionDAG::RemoveDeadNodes() {
612 // Create a dummy node (which is not added to allnodes), that adds a reference
613 // to the root node, preventing it from being deleted.
614 HandleSDNode Dummy(getRoot());
616 SmallVector<SDNode*, 128> DeadNodes;
618 // Add all obviously-dead nodes to the DeadNodes worklist.
619 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
621 DeadNodes.push_back(I);
623 RemoveDeadNodes(DeadNodes);
625 // If the root changed (e.g. it was a dead load, update the root).
626 setRoot(Dummy.getValue());
629 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
630 /// given list, and any nodes that become unreachable as a result.
631 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
633 // Process the worklist, deleting the nodes and adding their uses to the
635 while (!DeadNodes.empty()) {
636 SDNode *N = DeadNodes.pop_back_val();
638 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
639 DUL->NodeDeleted(N, nullptr);
641 // Take the node out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Next, brutally remove the operand list. This is safe to do, as there are
645 // no cycles in the graph.
646 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
648 SDNode *Operand = Use.getNode();
651 // Now that we removed this operand, see if there are no uses of it left.
652 if (Operand->use_empty())
653 DeadNodes.push_back(Operand);
660 void SelectionDAG::RemoveDeadNode(SDNode *N){
661 SmallVector<SDNode*, 16> DeadNodes(1, N);
663 // Create a dummy node that adds a reference to the root node, preventing
664 // it from being deleted. (This matters if the root is an operand of the
666 HandleSDNode Dummy(getRoot());
668 RemoveDeadNodes(DeadNodes);
671 void SelectionDAG::DeleteNode(SDNode *N) {
672 // First take this out of the appropriate CSE map.
673 RemoveNodeFromCSEMaps(N);
675 // Finally, remove uses due to operands of this node, remove from the
676 // AllNodes list, and delete the node.
677 DeleteNodeNotInCSEMaps(N);
680 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
681 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
682 assert(N->use_empty() && "Cannot delete a node that is not dead!");
684 // Drop all of the operands and decrement used node's use counts.
690 void SelectionDAG::DeallocateNode(SDNode *N) {
691 if (N->OperandsNeedDelete)
692 delete[] N->OperandList;
694 // Set the opcode to DELETED_NODE to help catch bugs when node
695 // memory is reallocated.
696 N->NodeType = ISD::DELETED_NODE;
698 NodeAllocator.Deallocate(AllNodes.remove(N));
700 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
701 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
702 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
703 DbgVals[i]->setIsInvalidated();
707 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
708 static void VerifySDNode(SDNode *N) {
709 switch (N->getOpcode()) {
712 case ISD::BUILD_PAIR: {
713 EVT VT = N->getValueType(0);
714 assert(N->getNumValues() == 1 && "Too many results!");
715 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
716 "Wrong return type!");
717 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
718 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
719 "Mismatched operand types!");
720 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
721 "Wrong operand type!");
722 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
723 "Wrong return type size");
726 case ISD::BUILD_VECTOR: {
727 assert(N->getNumValues() == 1 && "Too many results!");
728 assert(N->getValueType(0).isVector() && "Wrong return type!");
729 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
730 "Wrong number of operands!");
731 EVT EltVT = N->getValueType(0).getVectorElementType();
732 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
733 assert((I->getValueType() == EltVT ||
734 (EltVT.isInteger() && I->getValueType().isInteger() &&
735 EltVT.bitsLE(I->getValueType()))) &&
736 "Wrong operand type!");
737 assert(I->getValueType() == N->getOperand(0).getValueType() &&
738 "Operands must all have the same type");
746 /// \brief Insert a newly allocated node into the DAG.
748 /// Handles insertion into the all nodes list and CSE map, as well as
749 /// verification and other common operations when a new node is allocated.
750 void SelectionDAG::InsertNode(SDNode *N) {
751 AllNodes.push_back(N);
757 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
758 /// correspond to it. This is useful when we're about to delete or repurpose
759 /// the node. We don't want future request for structurally identical nodes
760 /// to return N anymore.
761 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
763 switch (N->getOpcode()) {
764 case ISD::HANDLENODE: return false; // noop.
766 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
767 "Cond code doesn't exist!");
768 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
769 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
771 case ISD::ExternalSymbol:
772 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
774 case ISD::TargetExternalSymbol: {
775 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
776 Erased = TargetExternalSymbols.erase(
777 std::pair<std::string,unsigned char>(ESN->getSymbol(),
778 ESN->getTargetFlags()));
781 case ISD::VALUETYPE: {
782 EVT VT = cast<VTSDNode>(N)->getVT();
783 if (VT.isExtended()) {
784 Erased = ExtendedValueTypeNodes.erase(VT);
786 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
787 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
792 // Remove it from the CSE Map.
793 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
794 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
795 Erased = CSEMap.RemoveNode(N);
799 // Verify that the node was actually in one of the CSE maps, unless it has a
800 // flag result (which cannot be CSE'd) or is one of the special cases that are
801 // not subject to CSE.
802 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
803 !N->isMachineOpcode() && !doNotCSE(N)) {
806 llvm_unreachable("Node is not in map!");
812 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
813 /// maps and modified in place. Add it back to the CSE maps, unless an identical
814 /// node already exists, in which case transfer all its users to the existing
815 /// node. This transfer can potentially trigger recursive merging.
818 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
819 // For node types that aren't CSE'd, just act as if no identical node
822 SDNode *Existing = CSEMap.GetOrInsertNode(N);
824 // If there was already an existing matching node, use ReplaceAllUsesWith
825 // to replace the dead one with the existing one. This can cause
826 // recursive merging of other unrelated nodes down the line.
827 ReplaceAllUsesWith(N, Existing);
829 // N is now dead. Inform the listeners and delete it.
830 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
831 DUL->NodeDeleted(N, Existing);
832 DeleteNodeNotInCSEMaps(N);
837 // If the node doesn't already exist, we updated it. Inform listeners.
838 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
842 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
843 /// were replaced with those specified. If this node is never memoized,
844 /// return null, otherwise return a pointer to the slot it would take. If a
845 /// node already exists with these operands, the slot will be non-null.
846 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
851 SDValue Ops[] = { Op };
853 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
854 AddNodeIDCustom(ID, N);
855 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
859 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
860 /// were replaced with those specified. If this node is never memoized,
861 /// return null, otherwise return a pointer to the slot it would take. If a
862 /// node already exists with these operands, the slot will be non-null.
863 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
864 SDValue Op1, SDValue Op2,
869 SDValue Ops[] = { Op1, Op2 };
871 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
872 AddNodeIDCustom(ID, N);
873 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
878 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
879 /// were replaced with those specified. If this node is never memoized,
880 /// return null, otherwise return a pointer to the slot it would take. If a
881 /// node already exists with these operands, the slot will be non-null.
882 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
888 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
889 AddNodeIDCustom(ID, N);
890 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
894 /// getEVTAlignment - Compute the default alignment value for the
897 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
898 Type *Ty = VT == MVT::iPTR ?
899 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
900 VT.getTypeForEVT(*getContext());
902 return TLI->getDataLayout()->getABITypeAlignment(Ty);
905 // EntryNode could meaningfully have debug info if we can find it...
906 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
907 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
908 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
909 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
910 UpdateListeners(nullptr) {
911 AllNodes.push_back(&EntryNode);
912 DbgInfo = new SDDbgInfo();
915 void SelectionDAG::init(MachineFunction &mf) {
917 TLI = getSubtarget().getTargetLowering();
918 TSI = getSubtarget().getSelectionDAGInfo();
919 Context = &mf.getFunction()->getContext();
922 SelectionDAG::~SelectionDAG() {
923 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
928 void SelectionDAG::allnodes_clear() {
929 assert(&*AllNodes.begin() == &EntryNode);
930 AllNodes.remove(AllNodes.begin());
931 while (!AllNodes.empty())
932 DeallocateNode(AllNodes.begin());
935 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
936 SDVTList VTs, SDValue N1,
937 SDValue N2, bool nuw, bool nsw,
939 if (isBinOpWithFlags(Opcode)) {
940 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
941 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
942 FN->setHasNoUnsignedWrap(nuw);
943 FN->setHasNoSignedWrap(nsw);
944 FN->setIsExact(exact);
949 BinarySDNode *N = new (NodeAllocator)
950 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
954 void SelectionDAG::clear() {
956 OperandAllocator.Reset();
959 ExtendedValueTypeNodes.clear();
960 ExternalSymbols.clear();
961 TargetExternalSymbols.clear();
962 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
963 static_cast<CondCodeSDNode*>(nullptr));
964 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
965 static_cast<SDNode*>(nullptr));
967 EntryNode.UseList = nullptr;
968 AllNodes.push_back(&EntryNode);
969 Root = getEntryNode();
973 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
974 return VT.bitsGT(Op.getValueType()) ?
975 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
976 getNode(ISD::TRUNCATE, DL, VT, Op);
979 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
980 return VT.bitsGT(Op.getValueType()) ?
981 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
982 getNode(ISD::TRUNCATE, DL, VT, Op);
985 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
986 return VT.bitsGT(Op.getValueType()) ?
987 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
988 getNode(ISD::TRUNCATE, DL, VT, Op);
991 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
993 if (VT.bitsLE(Op.getValueType()))
994 return getNode(ISD::TRUNCATE, SL, VT, Op);
996 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
997 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1000 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1001 assert(!VT.isVector() &&
1002 "getZeroExtendInReg should use the vector element type instead of "
1003 "the vector type!");
1004 if (Op.getValueType() == VT) return Op;
1005 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1006 APInt Imm = APInt::getLowBitsSet(BitWidth,
1007 VT.getSizeInBits());
1008 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1009 getConstant(Imm, Op.getValueType()));
1012 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1013 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1014 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1015 "The sizes of the input and result must match in order to perform the "
1016 "extend in-register.");
1017 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1018 "The destination vector type must have fewer lanes than the input.");
1019 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1022 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1023 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1024 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1025 "The sizes of the input and result must match in order to perform the "
1026 "extend in-register.");
1027 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1028 "The destination vector type must have fewer lanes than the input.");
1029 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1032 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1033 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1034 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1035 "The sizes of the input and result must match in order to perform the "
1036 "extend in-register.");
1037 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1038 "The destination vector type must have fewer lanes than the input.");
1039 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1042 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1044 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1045 EVT EltVT = VT.getScalarType();
1047 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1048 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1051 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1052 EVT EltVT = VT.getScalarType();
1054 switch (TLI->getBooleanContents(VT)) {
1055 case TargetLowering::ZeroOrOneBooleanContent:
1056 case TargetLowering::UndefinedBooleanContent:
1057 TrueValue = getConstant(1, VT);
1059 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1060 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1064 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1067 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1068 EVT EltVT = VT.getScalarType();
1069 assert((EltVT.getSizeInBits() >= 64 ||
1070 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1071 "getConstant with a uint64_t value that doesn't fit in the type!");
1072 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1075 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1077 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1080 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1082 assert(VT.isInteger() && "Cannot create FP integer constant!");
1084 EVT EltVT = VT.getScalarType();
1085 const ConstantInt *Elt = &Val;
1087 // In some cases the vector type is legal but the element type is illegal and
1088 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1089 // inserted value (the type does not need to match the vector element type).
1090 // Any extra bits introduced will be truncated away.
1091 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1092 TargetLowering::TypePromoteInteger) {
1093 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1094 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1095 Elt = ConstantInt::get(*getContext(), NewVal);
1097 // In other cases the element type is illegal and needs to be expanded, for
1098 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1099 // the value into n parts and use a vector type with n-times the elements.
1100 // Then bitcast to the type requested.
1101 // Legalizing constants too early makes the DAGCombiner's job harder so we
1102 // only legalize if the DAG tells us we must produce legal types.
1103 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1104 TLI->getTypeAction(*getContext(), EltVT) ==
1105 TargetLowering::TypeExpandInteger) {
1106 APInt NewVal = Elt->getValue();
1107 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1108 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1109 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1110 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1112 // Check the temporary vector is the correct size. If this fails then
1113 // getTypeToTransformTo() probably returned a type whose size (in bits)
1114 // isn't a power-of-2 factor of the requested type size.
1115 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1117 SmallVector<SDValue, 2> EltParts;
1118 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1119 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1120 .trunc(ViaEltSizeInBits),
1121 ViaEltVT, isT, isO));
1124 // EltParts is currently in little endian order. If we actually want
1125 // big-endian order then reverse it now.
1126 if (TLI->isBigEndian())
1127 std::reverse(EltParts.begin(), EltParts.end());
1129 // The elements must be reversed when the element order is different
1130 // to the endianness of the elements (because the BITCAST is itself a
1131 // vector shuffle in this situation). However, we do not need any code to
1132 // perform this reversal because getConstant() is producing a vector
1134 // This situation occurs in MIPS MSA.
1136 SmallVector<SDValue, 8> Ops;
1137 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1138 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1140 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1141 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1146 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1147 "APInt size does not match type size!");
1148 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1149 FoldingSetNodeID ID;
1150 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1154 SDNode *N = nullptr;
1155 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1157 return SDValue(N, 0);
1160 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1161 CSEMap.InsertNode(N, IP);
1165 SDValue Result(N, 0);
1166 if (VT.isVector()) {
1167 SmallVector<SDValue, 8> Ops;
1168 Ops.assign(VT.getVectorNumElements(), Result);
1169 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1174 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1175 return getConstant(Val, TLI->getPointerTy(), isTarget);
1179 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1180 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1183 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1184 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1186 EVT EltVT = VT.getScalarType();
1188 // Do the map lookup using the actual bit pattern for the floating point
1189 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1190 // we don't have issues with SNANs.
1191 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1192 FoldingSetNodeID ID;
1193 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1196 SDNode *N = nullptr;
1197 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1199 return SDValue(N, 0);
1202 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1203 CSEMap.InsertNode(N, IP);
1207 SDValue Result(N, 0);
1208 if (VT.isVector()) {
1209 SmallVector<SDValue, 8> Ops;
1210 Ops.assign(VT.getVectorNumElements(), Result);
1211 // FIXME SDLoc info might be appropriate here
1212 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1217 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1218 EVT EltVT = VT.getScalarType();
1219 if (EltVT==MVT::f32)
1220 return getConstantFP(APFloat((float)Val), VT, isTarget);
1221 else if (EltVT==MVT::f64)
1222 return getConstantFP(APFloat(Val), VT, isTarget);
1223 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1226 APFloat apf = APFloat(Val);
1227 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1229 return getConstantFP(apf, VT, isTarget);
1231 llvm_unreachable("Unsupported type in getConstantFP");
1234 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1235 EVT VT, int64_t Offset,
1237 unsigned char TargetFlags) {
1238 assert((TargetFlags == 0 || isTargetGA) &&
1239 "Cannot set target flags on target-independent globals");
1241 // Truncate (with sign-extension) the offset value to the pointer size.
1242 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1244 Offset = SignExtend64(Offset, BitWidth);
1247 if (GV->isThreadLocal())
1248 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1250 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1252 FoldingSetNodeID ID;
1253 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1255 ID.AddInteger(Offset);
1256 ID.AddInteger(TargetFlags);
1257 ID.AddInteger(GV->getType()->getAddressSpace());
1259 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1260 return SDValue(E, 0);
1262 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1263 DL.getDebugLoc(), GV, VT,
1264 Offset, TargetFlags);
1265 CSEMap.InsertNode(N, IP);
1267 return SDValue(N, 0);
1270 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1271 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1272 FoldingSetNodeID ID;
1273 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1276 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1277 return SDValue(E, 0);
1279 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1280 CSEMap.InsertNode(N, IP);
1282 return SDValue(N, 0);
1285 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1286 unsigned char TargetFlags) {
1287 assert((TargetFlags == 0 || isTarget) &&
1288 "Cannot set target flags on target-independent jump tables");
1289 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1290 FoldingSetNodeID ID;
1291 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1293 ID.AddInteger(TargetFlags);
1295 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1296 return SDValue(E, 0);
1298 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1300 CSEMap.InsertNode(N, IP);
1302 return SDValue(N, 0);
1305 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1306 unsigned Alignment, int Offset,
1308 unsigned char TargetFlags) {
1309 assert((TargetFlags == 0 || isTarget) &&
1310 "Cannot set target flags on target-independent globals");
1312 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1313 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1314 FoldingSetNodeID ID;
1315 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1316 ID.AddInteger(Alignment);
1317 ID.AddInteger(Offset);
1319 ID.AddInteger(TargetFlags);
1321 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1322 return SDValue(E, 0);
1324 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1325 Alignment, TargetFlags);
1326 CSEMap.InsertNode(N, IP);
1328 return SDValue(N, 0);
1332 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1333 unsigned Alignment, int Offset,
1335 unsigned char TargetFlags) {
1336 assert((TargetFlags == 0 || isTarget) &&
1337 "Cannot set target flags on target-independent globals");
1339 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1340 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1341 FoldingSetNodeID ID;
1342 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1343 ID.AddInteger(Alignment);
1344 ID.AddInteger(Offset);
1345 C->addSelectionDAGCSEId(ID);
1346 ID.AddInteger(TargetFlags);
1348 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1349 return SDValue(E, 0);
1351 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1352 Alignment, TargetFlags);
1353 CSEMap.InsertNode(N, IP);
1355 return SDValue(N, 0);
1358 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1359 unsigned char TargetFlags) {
1360 FoldingSetNodeID ID;
1361 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1362 ID.AddInteger(Index);
1363 ID.AddInteger(Offset);
1364 ID.AddInteger(TargetFlags);
1366 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1367 return SDValue(E, 0);
1369 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1371 CSEMap.InsertNode(N, IP);
1373 return SDValue(N, 0);
1376 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1377 FoldingSetNodeID ID;
1378 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1381 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1382 return SDValue(E, 0);
1384 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1385 CSEMap.InsertNode(N, IP);
1387 return SDValue(N, 0);
1390 SDValue SelectionDAG::getValueType(EVT VT) {
1391 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1392 ValueTypeNodes.size())
1393 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1395 SDNode *&N = VT.isExtended() ?
1396 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1398 if (N) return SDValue(N, 0);
1399 N = new (NodeAllocator) VTSDNode(VT);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1405 SDNode *&N = ExternalSymbols[Sym];
1406 if (N) return SDValue(N, 0);
1407 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1409 return SDValue(N, 0);
1412 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1413 unsigned char TargetFlags) {
1415 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1417 if (N) return SDValue(N, 0);
1418 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1420 return SDValue(N, 0);
1423 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1424 if ((unsigned)Cond >= CondCodeNodes.size())
1425 CondCodeNodes.resize(Cond+1);
1427 if (!CondCodeNodes[Cond]) {
1428 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1429 CondCodeNodes[Cond] = N;
1433 return SDValue(CondCodeNodes[Cond], 0);
1436 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1437 // the shuffle mask M that point at N1 to point at N2, and indices that point
1438 // N2 to point at N1.
1439 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1441 int NElts = M.size();
1442 for (int i = 0; i != NElts; ++i) {
1450 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1451 SDValue N2, const int *Mask) {
1452 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1453 "Invalid VECTOR_SHUFFLE");
1455 // Canonicalize shuffle undef, undef -> undef
1456 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1457 return getUNDEF(VT);
1459 // Validate that all indices in Mask are within the range of the elements
1460 // input to the shuffle.
1461 unsigned NElts = VT.getVectorNumElements();
1462 SmallVector<int, 8> MaskVec;
1463 for (unsigned i = 0; i != NElts; ++i) {
1464 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1465 MaskVec.push_back(Mask[i]);
1468 // Canonicalize shuffle v, v -> v, undef
1471 for (unsigned i = 0; i != NElts; ++i)
1472 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1475 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1476 if (N1.getOpcode() == ISD::UNDEF)
1477 commuteShuffle(N1, N2, MaskVec);
1479 // Canonicalize all index into lhs, -> shuffle lhs, undef
1480 // Canonicalize all index into rhs, -> shuffle rhs, undef
1481 bool AllLHS = true, AllRHS = true;
1482 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1483 for (unsigned i = 0; i != NElts; ++i) {
1484 if (MaskVec[i] >= (int)NElts) {
1489 } else if (MaskVec[i] >= 0) {
1493 if (AllLHS && AllRHS)
1494 return getUNDEF(VT);
1495 if (AllLHS && !N2Undef)
1499 commuteShuffle(N1, N2, MaskVec);
1501 // Reset our undef status after accounting for the mask.
1502 N2Undef = N2.getOpcode() == ISD::UNDEF;
1503 // Re-check whether both sides ended up undef.
1504 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1505 return getUNDEF(VT);
1507 // If Identity shuffle return that node.
1508 bool Identity = true;
1509 for (unsigned i = 0; i != NElts; ++i) {
1510 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1512 if (Identity && NElts)
1515 // Shuffling a constant splat doesn't change the result.
1519 // Look through any bitcasts. We check that these don't change the number
1520 // (and size) of elements and just changes their types.
1521 while (V.getOpcode() == ISD::BITCAST)
1522 V = V->getOperand(0);
1524 // A splat should always show up as a build vector node.
1525 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1526 BitVector UndefElements;
1527 SDValue Splat = BV->getSplatValue(&UndefElements);
1528 // If this is a splat of an undef, shuffling it is also undef.
1529 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1530 return getUNDEF(VT);
1532 // We only have a splat which can skip shuffles if there is a splatted
1533 // value and no undef lanes rearranged by the shuffle.
1534 if (Splat && UndefElements.none()) {
1535 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1536 // number of elements match or the value splatted is a zero constant.
1537 if (V.getValueType().getVectorNumElements() ==
1538 VT.getVectorNumElements())
1540 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1541 if (C->isNullValue())
1547 FoldingSetNodeID ID;
1548 SDValue Ops[2] = { N1, N2 };
1549 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1550 for (unsigned i = 0; i != NElts; ++i)
1551 ID.AddInteger(MaskVec[i]);
1554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1555 return SDValue(E, 0);
1557 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1558 // SDNode doesn't have access to it. This memory will be "leaked" when
1559 // the node is deallocated, but recovered when the NodeAllocator is released.
1560 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1561 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1563 ShuffleVectorSDNode *N =
1564 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1565 dl.getDebugLoc(), N1, N2,
1567 CSEMap.InsertNode(N, IP);
1569 return SDValue(N, 0);
1572 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1573 MVT VT = SV.getSimpleValueType(0);
1574 unsigned NumElems = VT.getVectorNumElements();
1575 SmallVector<int, 8> MaskVec;
1577 for (unsigned i = 0; i != NumElems; ++i) {
1578 int Idx = SV.getMaskElt(i);
1580 if (Idx < (int)NumElems)
1585 MaskVec.push_back(Idx);
1588 SDValue Op0 = SV.getOperand(0);
1589 SDValue Op1 = SV.getOperand(1);
1590 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1593 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1594 SDValue Val, SDValue DTy,
1595 SDValue STy, SDValue Rnd, SDValue Sat,
1596 ISD::CvtCode Code) {
1597 // If the src and dest types are the same and the conversion is between
1598 // integer types of the same sign or two floats, no conversion is necessary.
1600 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1603 FoldingSetNodeID ID;
1604 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1605 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1607 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1608 return SDValue(E, 0);
1610 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1613 CSEMap.InsertNode(N, IP);
1615 return SDValue(N, 0);
1618 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1619 FoldingSetNodeID ID;
1620 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1621 ID.AddInteger(RegNo);
1623 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1624 return SDValue(E, 0);
1626 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1627 CSEMap.InsertNode(N, IP);
1629 return SDValue(N, 0);
1632 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1633 FoldingSetNodeID ID;
1634 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1635 ID.AddPointer(RegMask);
1637 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1638 return SDValue(E, 0);
1640 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1641 CSEMap.InsertNode(N, IP);
1643 return SDValue(N, 0);
1646 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1647 FoldingSetNodeID ID;
1648 SDValue Ops[] = { Root };
1649 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1650 ID.AddPointer(Label);
1652 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1653 return SDValue(E, 0);
1655 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1656 dl.getDebugLoc(), Root, Label);
1657 CSEMap.InsertNode(N, IP);
1659 return SDValue(N, 0);
1663 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1666 unsigned char TargetFlags) {
1667 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1669 FoldingSetNodeID ID;
1670 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1672 ID.AddInteger(Offset);
1673 ID.AddInteger(TargetFlags);
1675 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1676 return SDValue(E, 0);
1678 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1680 CSEMap.InsertNode(N, IP);
1682 return SDValue(N, 0);
1685 SDValue SelectionDAG::getSrcValue(const Value *V) {
1686 assert((!V || V->getType()->isPointerTy()) &&
1687 "SrcValue is not a pointer?");
1689 FoldingSetNodeID ID;
1690 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1694 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1695 return SDValue(E, 0);
1697 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1698 CSEMap.InsertNode(N, IP);
1700 return SDValue(N, 0);
1703 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1704 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1705 FoldingSetNodeID ID;
1706 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1710 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1711 return SDValue(E, 0);
1713 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1714 CSEMap.InsertNode(N, IP);
1716 return SDValue(N, 0);
1719 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1720 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1721 unsigned SrcAS, unsigned DestAS) {
1722 SDValue Ops[] = {Ptr};
1723 FoldingSetNodeID ID;
1724 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1725 ID.AddInteger(SrcAS);
1726 ID.AddInteger(DestAS);
1729 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1730 return SDValue(E, 0);
1732 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1734 VT, Ptr, SrcAS, DestAS);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 /// getShiftAmountOperand - Return the specified value casted to
1741 /// the target's desired shift amount type.
1742 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1743 EVT OpTy = Op.getValueType();
1744 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1745 if (OpTy == ShTy || OpTy.isVector()) return Op;
1747 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1748 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1751 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1752 /// specified value type.
1753 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1754 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1755 unsigned ByteSize = VT.getStoreSize();
1756 Type *Ty = VT.getTypeForEVT(*getContext());
1757 unsigned StackAlign =
1758 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1760 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1761 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1764 /// CreateStackTemporary - Create a stack temporary suitable for holding
1765 /// either of the specified value types.
1766 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1767 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1768 VT2.getStoreSizeInBits())/8;
1769 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1770 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1771 const DataLayout *TD = TLI->getDataLayout();
1772 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1773 TD->getPrefTypeAlignment(Ty2));
1775 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1776 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1777 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1780 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1781 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1782 // These setcc operations always fold.
1786 case ISD::SETFALSE2: return getConstant(0, VT);
1788 case ISD::SETTRUE2: {
1789 TargetLowering::BooleanContent Cnt =
1790 TLI->getBooleanContents(N1->getValueType(0));
1792 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1805 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1809 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1810 const APInt &C2 = N2C->getAPIntValue();
1811 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1812 const APInt &C1 = N1C->getAPIntValue();
1815 default: llvm_unreachable("Unknown integer setcc!");
1816 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1817 case ISD::SETNE: return getConstant(C1 != C2, VT);
1818 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1819 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1820 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1821 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1822 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1823 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1824 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1825 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1829 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1830 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1831 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1834 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1835 return getUNDEF(VT);
1837 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1838 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1839 return getUNDEF(VT);
1841 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1842 R==APFloat::cmpLessThan, VT);
1843 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1844 return getUNDEF(VT);
1846 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1847 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1848 return getUNDEF(VT);
1850 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1851 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1852 return getUNDEF(VT);
1854 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1855 R==APFloat::cmpEqual, VT);
1856 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1857 return getUNDEF(VT);
1859 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1860 R==APFloat::cmpEqual, VT);
1861 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1862 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1863 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1864 R==APFloat::cmpEqual, VT);
1865 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1866 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1867 R==APFloat::cmpLessThan, VT);
1868 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1869 R==APFloat::cmpUnordered, VT);
1870 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1871 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1874 // Ensure that the constant occurs on the RHS.
1875 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1876 MVT CompVT = N1.getValueType().getSimpleVT();
1877 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1880 return getSetCC(dl, VT, N2, N1, SwappedCond);
1884 // Could not fold it.
1888 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1889 /// use this predicate to simplify operations downstream.
1890 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1891 // This predicate is not safe for vector operations.
1892 if (Op.getValueType().isVector())
1895 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1896 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1899 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1900 /// this predicate to simplify operations downstream. Mask is known to be zero
1901 /// for bits that V cannot have.
1902 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1903 unsigned Depth) const {
1904 APInt KnownZero, KnownOne;
1905 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1906 return (KnownZero & Mask) == Mask;
1909 /// Determine which bits of Op are known to be either zero or one and return
1910 /// them in the KnownZero/KnownOne bitsets.
1911 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1912 APInt &KnownOne, unsigned Depth) const {
1913 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1915 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1917 return; // Limit search depth.
1919 APInt KnownZero2, KnownOne2;
1921 switch (Op.getOpcode()) {
1923 // We know all of the bits for a constant!
1924 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1925 KnownZero = ~KnownOne;
1928 // If either the LHS or the RHS are Zero, the result is zero.
1929 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1930 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1932 // Output known-1 bits are only known if set in both the LHS & RHS.
1933 KnownOne &= KnownOne2;
1934 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1935 KnownZero |= KnownZero2;
1938 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1939 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1941 // Output known-0 bits are only known if clear in both the LHS & RHS.
1942 KnownZero &= KnownZero2;
1943 // Output known-1 are known to be set if set in either the LHS | RHS.
1944 KnownOne |= KnownOne2;
1947 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1948 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1950 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1951 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1952 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1953 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1954 KnownZero = KnownZeroOut;
1958 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1959 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1961 // If low bits are zero in either operand, output low known-0 bits.
1962 // Also compute a conserative estimate for high known-0 bits.
1963 // More trickiness is possible, but this is sufficient for the
1964 // interesting case of alignment computation.
1965 KnownOne.clearAllBits();
1966 unsigned TrailZ = KnownZero.countTrailingOnes() +
1967 KnownZero2.countTrailingOnes();
1968 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1969 KnownZero2.countLeadingOnes(),
1970 BitWidth) - BitWidth;
1972 TrailZ = std::min(TrailZ, BitWidth);
1973 LeadZ = std::min(LeadZ, BitWidth);
1974 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1975 APInt::getHighBitsSet(BitWidth, LeadZ);
1979 // For the purposes of computing leading zeros we can conservatively
1980 // treat a udiv as a logical right shift by the power of 2 known to
1981 // be less than the denominator.
1982 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1983 unsigned LeadZ = KnownZero2.countLeadingOnes();
1985 KnownOne2.clearAllBits();
1986 KnownZero2.clearAllBits();
1987 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1988 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1989 if (RHSUnknownLeadingOnes != BitWidth)
1990 LeadZ = std::min(BitWidth,
1991 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1993 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1997 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1998 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2000 // Only known if known in both the LHS and RHS.
2001 KnownOne &= KnownOne2;
2002 KnownZero &= KnownZero2;
2004 case ISD::SELECT_CC:
2005 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2006 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2008 // Only known if known in both the LHS and RHS.
2009 KnownOne &= KnownOne2;
2010 KnownZero &= KnownZero2;
2018 if (Op.getResNo() != 1)
2020 // The boolean result conforms to getBooleanContents.
2021 // If we know the result of a setcc has the top bits zero, use this info.
2022 // We know that we have an integer-based boolean since these operations
2023 // are only available for integer.
2024 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2025 TargetLowering::ZeroOrOneBooleanContent &&
2027 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2030 // If we know the result of a setcc has the top bits zero, use this info.
2031 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2032 TargetLowering::ZeroOrOneBooleanContent &&
2034 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2037 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2038 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2039 unsigned ShAmt = SA->getZExtValue();
2041 // If the shift count is an invalid immediate, don't do anything.
2042 if (ShAmt >= BitWidth)
2045 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2046 KnownZero <<= ShAmt;
2048 // low bits known zero.
2049 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2053 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2054 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2055 unsigned ShAmt = SA->getZExtValue();
2057 // If the shift count is an invalid immediate, don't do anything.
2058 if (ShAmt >= BitWidth)
2061 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2062 KnownZero = KnownZero.lshr(ShAmt);
2063 KnownOne = KnownOne.lshr(ShAmt);
2065 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2066 KnownZero |= HighBits; // High bits known zero.
2070 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2071 unsigned ShAmt = SA->getZExtValue();
2073 // If the shift count is an invalid immediate, don't do anything.
2074 if (ShAmt >= BitWidth)
2077 // If any of the demanded bits are produced by the sign extension, we also
2078 // demand the input sign bit.
2079 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2081 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2082 KnownZero = KnownZero.lshr(ShAmt);
2083 KnownOne = KnownOne.lshr(ShAmt);
2085 // Handle the sign bits.
2086 APInt SignBit = APInt::getSignBit(BitWidth);
2087 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2089 if (KnownZero.intersects(SignBit)) {
2090 KnownZero |= HighBits; // New bits are known zero.
2091 } else if (KnownOne.intersects(SignBit)) {
2092 KnownOne |= HighBits; // New bits are known one.
2096 case ISD::SIGN_EXTEND_INREG: {
2097 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2098 unsigned EBits = EVT.getScalarType().getSizeInBits();
2100 // Sign extension. Compute the demanded bits in the result that are not
2101 // present in the input.
2102 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2104 APInt InSignBit = APInt::getSignBit(EBits);
2105 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2107 // If the sign extended bits are demanded, we know that the sign
2109 InSignBit = InSignBit.zext(BitWidth);
2110 if (NewBits.getBoolValue())
2111 InputDemandedBits |= InSignBit;
2113 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2114 KnownOne &= InputDemandedBits;
2115 KnownZero &= InputDemandedBits;
2117 // If the sign bit of the input is known set or clear, then we know the
2118 // top bits of the result.
2119 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2120 KnownZero |= NewBits;
2121 KnownOne &= ~NewBits;
2122 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2123 KnownOne |= NewBits;
2124 KnownZero &= ~NewBits;
2125 } else { // Input sign bit unknown
2126 KnownZero &= ~NewBits;
2127 KnownOne &= ~NewBits;
2132 case ISD::CTTZ_ZERO_UNDEF:
2134 case ISD::CTLZ_ZERO_UNDEF:
2136 unsigned LowBits = Log2_32(BitWidth)+1;
2137 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2138 KnownOne.clearAllBits();
2142 LoadSDNode *LD = cast<LoadSDNode>(Op);
2143 // If this is a ZEXTLoad and we are looking at the loaded value.
2144 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2145 EVT VT = LD->getMemoryVT();
2146 unsigned MemBits = VT.getScalarType().getSizeInBits();
2147 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2148 } else if (const MDNode *Ranges = LD->getRanges()) {
2149 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2153 case ISD::ZERO_EXTEND: {
2154 EVT InVT = Op.getOperand(0).getValueType();
2155 unsigned InBits = InVT.getScalarType().getSizeInBits();
2156 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2157 KnownZero = KnownZero.trunc(InBits);
2158 KnownOne = KnownOne.trunc(InBits);
2159 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2160 KnownZero = KnownZero.zext(BitWidth);
2161 KnownOne = KnownOne.zext(BitWidth);
2162 KnownZero |= NewBits;
2165 case ISD::SIGN_EXTEND: {
2166 EVT InVT = Op.getOperand(0).getValueType();
2167 unsigned InBits = InVT.getScalarType().getSizeInBits();
2168 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2170 KnownZero = KnownZero.trunc(InBits);
2171 KnownOne = KnownOne.trunc(InBits);
2172 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2174 // Note if the sign bit is known to be zero or one.
2175 bool SignBitKnownZero = KnownZero.isNegative();
2176 bool SignBitKnownOne = KnownOne.isNegative();
2178 KnownZero = KnownZero.zext(BitWidth);
2179 KnownOne = KnownOne.zext(BitWidth);
2181 // If the sign bit is known zero or one, the top bits match.
2182 if (SignBitKnownZero)
2183 KnownZero |= NewBits;
2184 else if (SignBitKnownOne)
2185 KnownOne |= NewBits;
2188 case ISD::ANY_EXTEND: {
2189 EVT InVT = Op.getOperand(0).getValueType();
2190 unsigned InBits = InVT.getScalarType().getSizeInBits();
2191 KnownZero = KnownZero.trunc(InBits);
2192 KnownOne = KnownOne.trunc(InBits);
2193 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2194 KnownZero = KnownZero.zext(BitWidth);
2195 KnownOne = KnownOne.zext(BitWidth);
2198 case ISD::TRUNCATE: {
2199 EVT InVT = Op.getOperand(0).getValueType();
2200 unsigned InBits = InVT.getScalarType().getSizeInBits();
2201 KnownZero = KnownZero.zext(InBits);
2202 KnownOne = KnownOne.zext(InBits);
2203 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2204 KnownZero = KnownZero.trunc(BitWidth);
2205 KnownOne = KnownOne.trunc(BitWidth);
2208 case ISD::AssertZext: {
2209 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2210 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2211 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2212 KnownZero |= (~InMask);
2213 KnownOne &= (~KnownZero);
2217 // All bits are zero except the low bit.
2218 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2222 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2223 // We know that the top bits of C-X are clear if X contains less bits
2224 // than C (i.e. no wrap-around can happen). For example, 20-X is
2225 // positive if we can prove that X is >= 0 and < 16.
2226 if (CLHS->getAPIntValue().isNonNegative()) {
2227 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2228 // NLZ can't be BitWidth with no sign bit
2229 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2230 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2232 // If all of the MaskV bits are known to be zero, then we know the
2233 // output top bits are zero, because we now know that the output is
2235 if ((KnownZero2 & MaskV) == MaskV) {
2236 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2237 // Top bits known zero.
2238 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2246 // Output known-0 bits are known if clear or set in both the low clear bits
2247 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2248 // low 3 bits clear.
2249 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2250 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2252 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2253 KnownZeroOut = std::min(KnownZeroOut,
2254 KnownZero2.countTrailingOnes());
2256 if (Op.getOpcode() == ISD::ADD) {
2257 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2261 // With ADDE, a carry bit may be added in, so we can only use this
2262 // information if we know (at least) that the low two bits are clear. We
2263 // then return to the caller that the low bit is unknown but that other bits
2265 if (KnownZeroOut >= 2) // ADDE
2266 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2270 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2271 const APInt &RA = Rem->getAPIntValue().abs();
2272 if (RA.isPowerOf2()) {
2273 APInt LowBits = RA - 1;
2274 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2276 // The low bits of the first operand are unchanged by the srem.
2277 KnownZero = KnownZero2 & LowBits;
2278 KnownOne = KnownOne2 & LowBits;
2280 // If the first operand is non-negative or has all low bits zero, then
2281 // the upper bits are all zero.
2282 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2283 KnownZero |= ~LowBits;
2285 // If the first operand is negative and not all low bits are zero, then
2286 // the upper bits are all one.
2287 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2288 KnownOne |= ~LowBits;
2289 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2294 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2295 const APInt &RA = Rem->getAPIntValue();
2296 if (RA.isPowerOf2()) {
2297 APInt LowBits = (RA - 1);
2298 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2300 // The upper bits are all zero, the lower ones are unchanged.
2301 KnownZero = KnownZero2 | ~LowBits;
2302 KnownOne = KnownOne2 & LowBits;
2307 // Since the result is less than or equal to either operand, any leading
2308 // zero bits in either operand must also exist in the result.
2309 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2310 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2312 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2313 KnownZero2.countLeadingOnes());
2314 KnownOne.clearAllBits();
2315 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2318 case ISD::FrameIndex:
2319 case ISD::TargetFrameIndex:
2320 if (unsigned Align = InferPtrAlignment(Op)) {
2321 // The low bits are known zero if the pointer is aligned.
2322 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2328 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2331 case ISD::INTRINSIC_WO_CHAIN:
2332 case ISD::INTRINSIC_W_CHAIN:
2333 case ISD::INTRINSIC_VOID:
2334 // Allow the target to implement this method for its nodes.
2335 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2339 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2342 /// ComputeNumSignBits - Return the number of times the sign bit of the
2343 /// register is replicated into the other bits. We know that at least 1 bit
2344 /// is always equal to the sign bit (itself), but other cases can give us
2345 /// information. For example, immediately after an "SRA X, 2", we know that
2346 /// the top 3 bits are all equal to each other, so we return 3.
2347 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2348 EVT VT = Op.getValueType();
2349 assert(VT.isInteger() && "Invalid VT!");
2350 unsigned VTBits = VT.getScalarType().getSizeInBits();
2352 unsigned FirstAnswer = 1;
2355 return 1; // Limit search depth.
2357 switch (Op.getOpcode()) {
2359 case ISD::AssertSext:
2360 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2361 return VTBits-Tmp+1;
2362 case ISD::AssertZext:
2363 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2366 case ISD::Constant: {
2367 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2368 return Val.getNumSignBits();
2371 case ISD::SIGN_EXTEND:
2373 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2374 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2376 case ISD::SIGN_EXTEND_INREG:
2377 // Max of the input and what this extends.
2379 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2382 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2383 return std::max(Tmp, Tmp2);
2386 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2387 // SRA X, C -> adds C sign bits.
2388 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2389 Tmp += C->getZExtValue();
2390 if (Tmp > VTBits) Tmp = VTBits;
2394 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2395 // shl destroys sign bits.
2396 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2397 if (C->getZExtValue() >= VTBits || // Bad shift.
2398 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2399 return Tmp - C->getZExtValue();
2404 case ISD::XOR: // NOT is handled here.
2405 // Logical binary ops preserve the number of sign bits at the worst.
2406 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2408 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2409 FirstAnswer = std::min(Tmp, Tmp2);
2410 // We computed what we know about the sign bits as our first
2411 // answer. Now proceed to the generic code that uses
2412 // computeKnownBits, and pick whichever answer is better.
2417 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2418 if (Tmp == 1) return 1; // Early out.
2419 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2420 return std::min(Tmp, Tmp2);
2428 if (Op.getResNo() != 1)
2430 // The boolean result conforms to getBooleanContents. Fall through.
2431 // If setcc returns 0/-1, all bits are sign bits.
2432 // We know that we have an integer-based boolean since these operations
2433 // are only available for integer.
2434 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2435 TargetLowering::ZeroOrNegativeOneBooleanContent)
2439 // If setcc returns 0/-1, all bits are sign bits.
2440 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2441 TargetLowering::ZeroOrNegativeOneBooleanContent)
2446 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2447 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2449 // Handle rotate right by N like a rotate left by 32-N.
2450 if (Op.getOpcode() == ISD::ROTR)
2451 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2453 // If we aren't rotating out all of the known-in sign bits, return the
2454 // number that are left. This handles rotl(sext(x), 1) for example.
2455 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2456 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2460 // Add can have at most one carry bit. Thus we know that the output
2461 // is, at worst, one more bit than the inputs.
2462 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2463 if (Tmp == 1) return 1; // Early out.
2465 // Special case decrementing a value (ADD X, -1):
2466 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2467 if (CRHS->isAllOnesValue()) {
2468 APInt KnownZero, KnownOne;
2469 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2471 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2473 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2476 // If we are subtracting one from a positive number, there is no carry
2477 // out of the result.
2478 if (KnownZero.isNegative())
2482 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2483 if (Tmp2 == 1) return 1;
2484 return std::min(Tmp, Tmp2)-1;
2487 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2488 if (Tmp2 == 1) return 1;
2491 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2492 if (CLHS->isNullValue()) {
2493 APInt KnownZero, KnownOne;
2494 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2495 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2497 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2500 // If the input is known to be positive (the sign bit is known clear),
2501 // the output of the NEG has the same number of sign bits as the input.
2502 if (KnownZero.isNegative())
2505 // Otherwise, we treat this like a SUB.
2508 // Sub can have at most one carry bit. Thus we know that the output
2509 // is, at worst, one more bit than the inputs.
2510 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2511 if (Tmp == 1) return 1; // Early out.
2512 return std::min(Tmp, Tmp2)-1;
2514 // FIXME: it's tricky to do anything useful for this, but it is an important
2515 // case for targets like X86.
2519 // If we are looking at the loaded value of the SDNode.
2520 if (Op.getResNo() == 0) {
2521 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2522 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2523 unsigned ExtType = LD->getExtensionType();
2526 case ISD::SEXTLOAD: // '17' bits known
2527 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2528 return VTBits-Tmp+1;
2529 case ISD::ZEXTLOAD: // '16' bits known
2530 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2536 // Allow the target to implement this method for its nodes.
2537 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2538 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2539 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2540 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2541 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2542 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2545 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2546 // use this information.
2547 APInt KnownZero, KnownOne;
2548 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2551 if (KnownZero.isNegative()) { // sign bit is 0
2553 } else if (KnownOne.isNegative()) { // sign bit is 1;
2560 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2561 // the number of identical bits in the top of the input value.
2563 Mask <<= Mask.getBitWidth()-VTBits;
2564 // Return # leading zeros. We use 'min' here in case Val was zero before
2565 // shifting. We don't want to return '64' as for an i32 "0".
2566 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2569 /// isBaseWithConstantOffset - Return true if the specified operand is an
2570 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2571 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2572 /// semantics as an ADD. This handles the equivalence:
2573 /// X|Cst == X+Cst iff X&Cst = 0.
2574 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2575 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2576 !isa<ConstantSDNode>(Op.getOperand(1)))
2579 if (Op.getOpcode() == ISD::OR &&
2580 !MaskedValueIsZero(Op.getOperand(0),
2581 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2588 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2589 // If we're told that NaNs won't happen, assume they won't.
2590 if (getTarget().Options.NoNaNsFPMath)
2593 // If the value is a constant, we can obviously see if it is a NaN or not.
2594 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2595 return !C->getValueAPF().isNaN();
2597 // TODO: Recognize more cases here.
2602 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2603 // If the value is a constant, we can obviously see if it is a zero or not.
2604 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2605 return !C->isZero();
2607 // TODO: Recognize more cases here.
2608 switch (Op.getOpcode()) {
2611 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2612 return !C->isNullValue();
2619 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2620 // Check the obvious case.
2621 if (A == B) return true;
2623 // For for negative and positive zero.
2624 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2625 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2626 if (CA->isZero() && CB->isZero()) return true;
2628 // Otherwise they may not be equal.
2632 /// getNode - Gets or creates the specified node.
2634 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2635 FoldingSetNodeID ID;
2636 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2638 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2639 return SDValue(E, 0);
2641 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2642 DL.getDebugLoc(), getVTList(VT));
2643 CSEMap.InsertNode(N, IP);
2646 return SDValue(N, 0);
2649 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2650 EVT VT, SDValue Operand) {
2651 // Constant fold unary operations with an integer constant operand. Even
2652 // opaque constant will be folded, because the folding of unary operations
2653 // doesn't create new constants with different values. Nevertheless, the
2654 // opaque flag is preserved during folding to prevent future folding with
2656 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2657 const APInt &Val = C->getAPIntValue();
2660 case ISD::SIGN_EXTEND:
2661 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2662 C->isTargetOpcode(), C->isOpaque());
2663 case ISD::ANY_EXTEND:
2664 case ISD::ZERO_EXTEND:
2666 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2667 C->isTargetOpcode(), C->isOpaque());
2668 case ISD::UINT_TO_FP:
2669 case ISD::SINT_TO_FP: {
2670 APFloat apf(EVTToAPFloatSemantics(VT),
2671 APInt::getNullValue(VT.getSizeInBits()));
2672 (void)apf.convertFromAPInt(Val,
2673 Opcode==ISD::SINT_TO_FP,
2674 APFloat::rmNearestTiesToEven);
2675 return getConstantFP(apf, VT);
2678 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2679 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2680 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2681 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2684 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2687 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2690 case ISD::CTLZ_ZERO_UNDEF:
2691 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2694 case ISD::CTTZ_ZERO_UNDEF:
2695 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2700 // Constant fold unary operations with a floating point constant operand.
2701 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2702 APFloat V = C->getValueAPF(); // make copy
2706 return getConstantFP(V, VT);
2709 return getConstantFP(V, VT);
2711 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2712 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2713 return getConstantFP(V, VT);
2717 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2718 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2719 return getConstantFP(V, VT);
2723 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2724 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2725 return getConstantFP(V, VT);
2728 case ISD::FP_EXTEND: {
2730 // This can return overflow, underflow, or inexact; we don't care.
2731 // FIXME need to be more flexible about rounding mode.
2732 (void)V.convert(EVTToAPFloatSemantics(VT),
2733 APFloat::rmNearestTiesToEven, &ignored);
2734 return getConstantFP(V, VT);
2736 case ISD::FP_TO_SINT:
2737 case ISD::FP_TO_UINT: {
2740 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2741 // FIXME need to be more flexible about rounding mode.
2742 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2743 Opcode==ISD::FP_TO_SINT,
2744 APFloat::rmTowardZero, &ignored);
2745 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2747 APInt api(VT.getSizeInBits(), x);
2748 return getConstant(api, VT);
2751 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2752 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2753 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2754 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2759 // Constant fold unary operations with a vector integer operand.
2760 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2761 if (BV->isConstant()) {
2764 // FIXME: Entirely reasonable to perform folding of other unary
2765 // operations here as the need arises.
2767 case ISD::UINT_TO_FP:
2768 case ISD::SINT_TO_FP: {
2769 SmallVector<SDValue, 8> Ops;
2770 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2771 SDValue OpN = BV->getOperand(i);
2772 // Let the above scalar folding handle the conversion of each
2774 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2778 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2784 unsigned OpOpcode = Operand.getNode()->getOpcode();
2786 case ISD::TokenFactor:
2787 case ISD::MERGE_VALUES:
2788 case ISD::CONCAT_VECTORS:
2789 return Operand; // Factor, merge or concat of one node? No need.
2790 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2791 case ISD::FP_EXTEND:
2792 assert(VT.isFloatingPoint() &&
2793 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2794 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2795 assert((!VT.isVector() ||
2796 VT.getVectorNumElements() ==
2797 Operand.getValueType().getVectorNumElements()) &&
2798 "Vector element count mismatch!");
2799 if (Operand.getOpcode() == ISD::UNDEF)
2800 return getUNDEF(VT);
2802 case ISD::SIGN_EXTEND:
2803 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2804 "Invalid SIGN_EXTEND!");
2805 if (Operand.getValueType() == VT) return Operand; // noop extension
2806 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2807 "Invalid sext node, dst < src!");
2808 assert((!VT.isVector() ||
2809 VT.getVectorNumElements() ==
2810 Operand.getValueType().getVectorNumElements()) &&
2811 "Vector element count mismatch!");
2812 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2813 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2814 else if (OpOpcode == ISD::UNDEF)
2815 // sext(undef) = 0, because the top bits will all be the same.
2816 return getConstant(0, VT);
2818 case ISD::ZERO_EXTEND:
2819 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2820 "Invalid ZERO_EXTEND!");
2821 if (Operand.getValueType() == VT) return Operand; // noop extension
2822 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2823 "Invalid zext node, dst < src!");
2824 assert((!VT.isVector() ||
2825 VT.getVectorNumElements() ==
2826 Operand.getValueType().getVectorNumElements()) &&
2827 "Vector element count mismatch!");
2828 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2829 return getNode(ISD::ZERO_EXTEND, DL, VT,
2830 Operand.getNode()->getOperand(0));
2831 else if (OpOpcode == ISD::UNDEF)
2832 // zext(undef) = 0, because the top bits will be zero.
2833 return getConstant(0, VT);
2835 case ISD::ANY_EXTEND:
2836 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2837 "Invalid ANY_EXTEND!");
2838 if (Operand.getValueType() == VT) return Operand; // noop extension
2839 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2840 "Invalid anyext node, dst < src!");
2841 assert((!VT.isVector() ||
2842 VT.getVectorNumElements() ==
2843 Operand.getValueType().getVectorNumElements()) &&
2844 "Vector element count mismatch!");
2846 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2847 OpOpcode == ISD::ANY_EXTEND)
2848 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2849 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2850 else if (OpOpcode == ISD::UNDEF)
2851 return getUNDEF(VT);
2853 // (ext (trunx x)) -> x
2854 if (OpOpcode == ISD::TRUNCATE) {
2855 SDValue OpOp = Operand.getNode()->getOperand(0);
2856 if (OpOp.getValueType() == VT)
2861 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2862 "Invalid TRUNCATE!");
2863 if (Operand.getValueType() == VT) return Operand; // noop truncate
2864 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2865 "Invalid truncate node, src < dst!");
2866 assert((!VT.isVector() ||
2867 VT.getVectorNumElements() ==
2868 Operand.getValueType().getVectorNumElements()) &&
2869 "Vector element count mismatch!");
2870 if (OpOpcode == ISD::TRUNCATE)
2871 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2872 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2873 OpOpcode == ISD::ANY_EXTEND) {
2874 // If the source is smaller than the dest, we still need an extend.
2875 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2876 .bitsLT(VT.getScalarType()))
2877 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2878 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2879 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2880 return Operand.getNode()->getOperand(0);
2882 if (OpOpcode == ISD::UNDEF)
2883 return getUNDEF(VT);
2886 // Basic sanity checking.
2887 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2888 && "Cannot BITCAST between types of different sizes!");
2889 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2890 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2891 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2892 if (OpOpcode == ISD::UNDEF)
2893 return getUNDEF(VT);
2895 case ISD::SCALAR_TO_VECTOR:
2896 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2897 (VT.getVectorElementType() == Operand.getValueType() ||
2898 (VT.getVectorElementType().isInteger() &&
2899 Operand.getValueType().isInteger() &&
2900 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2901 "Illegal SCALAR_TO_VECTOR node!");
2902 if (OpOpcode == ISD::UNDEF)
2903 return getUNDEF(VT);
2904 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2905 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2906 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2907 Operand.getConstantOperandVal(1) == 0 &&
2908 Operand.getOperand(0).getValueType() == VT)
2909 return Operand.getOperand(0);
2912 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2913 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2914 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2915 Operand.getNode()->getOperand(0));
2916 if (OpOpcode == ISD::FNEG) // --X -> X
2917 return Operand.getNode()->getOperand(0);
2920 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2921 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2926 SDVTList VTs = getVTList(VT);
2927 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2928 FoldingSetNodeID ID;
2929 SDValue Ops[1] = { Operand };
2930 AddNodeIDNode(ID, Opcode, VTs, Ops);
2932 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2933 return SDValue(E, 0);
2935 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2936 DL.getDebugLoc(), VTs, Operand);
2937 CSEMap.InsertNode(N, IP);
2939 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2940 DL.getDebugLoc(), VTs, Operand);
2944 return SDValue(N, 0);
2947 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2948 SDNode *Cst1, SDNode *Cst2) {
2949 // If the opcode is a target-specific ISD node, there's nothing we can
2950 // do here and the operand rules may not line up with the below, so
2952 if (Opcode >= ISD::BUILTIN_OP_END)
2955 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2956 SmallVector<SDValue, 4> Outputs;
2957 EVT SVT = VT.getScalarType();
2959 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2960 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2961 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2964 if (Scalar1 && Scalar2)
2965 // Scalar instruction.
2966 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2968 // For vectors extract each constant element into Inputs so we can constant
2969 // fold them individually.
2970 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2971 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2975 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2977 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2978 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2979 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2980 if (!V1 || !V2) // Not a constant, bail.
2983 if (V1->isOpaque() || V2->isOpaque())
2986 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2987 // FIXME: This is valid and could be handled by truncating the APInts.
2988 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2991 Inputs.push_back(std::make_pair(V1, V2));
2995 // We have a number of constant values, constant fold them element by element.
2996 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2997 const APInt &C1 = Inputs[I].first->getAPIntValue();
2998 const APInt &C2 = Inputs[I].second->getAPIntValue();
3002 Outputs.push_back(getConstant(C1 + C2, SVT));
3005 Outputs.push_back(getConstant(C1 - C2, SVT));
3008 Outputs.push_back(getConstant(C1 * C2, SVT));
3011 if (!C2.getBoolValue())
3013 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3016 if (!C2.getBoolValue())
3018 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3021 if (!C2.getBoolValue())
3023 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3026 if (!C2.getBoolValue())
3028 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3031 Outputs.push_back(getConstant(C1 & C2, SVT));
3034 Outputs.push_back(getConstant(C1 | C2, SVT));
3037 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3040 Outputs.push_back(getConstant(C1 << C2, SVT));
3043 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3046 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3049 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3052 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3059 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3060 "Expected a scalar or vector!"));
3062 // Handle the scalar case first.
3064 return Outputs.back();
3066 // We may have a vector type but a scalar result. Create a splat.
3067 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3069 // Build a big vector out of the scalar elements we generated.
3070 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3073 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3074 SDValue N2, bool nuw, bool nsw, bool exact) {
3075 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3076 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3079 case ISD::TokenFactor:
3080 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3081 N2.getValueType() == MVT::Other && "Invalid token factor!");
3082 // Fold trivial token factors.
3083 if (N1.getOpcode() == ISD::EntryToken) return N2;
3084 if (N2.getOpcode() == ISD::EntryToken) return N1;
3085 if (N1 == N2) return N1;
3087 case ISD::CONCAT_VECTORS:
3088 // Concat of UNDEFs is UNDEF.
3089 if (N1.getOpcode() == ISD::UNDEF &&
3090 N2.getOpcode() == ISD::UNDEF)
3091 return getUNDEF(VT);
3093 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3094 // one big BUILD_VECTOR.
3095 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3096 N2.getOpcode() == ISD::BUILD_VECTOR) {
3097 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3098 N1.getNode()->op_end());
3099 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3100 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3104 assert(VT.isInteger() && "This operator does not apply to FP types!");
3105 assert(N1.getValueType() == N2.getValueType() &&
3106 N1.getValueType() == VT && "Binary operator types must match!");
3107 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3108 // worth handling here.
3109 if (N2C && N2C->isNullValue())
3111 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3118 assert(VT.isInteger() && "This operator does not apply to FP types!");
3119 assert(N1.getValueType() == N2.getValueType() &&
3120 N1.getValueType() == VT && "Binary operator types must match!");
3121 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3122 // it's worth handling here.
3123 if (N2C && N2C->isNullValue())
3133 assert(VT.isInteger() && "This operator does not apply to FP types!");
3134 assert(N1.getValueType() == N2.getValueType() &&
3135 N1.getValueType() == VT && "Binary operator types must match!");
3142 if (getTarget().Options.UnsafeFPMath) {
3143 if (Opcode == ISD::FADD) {
3145 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3146 if (CFP->getValueAPF().isZero())
3149 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3150 if (CFP->getValueAPF().isZero())
3152 } else if (Opcode == ISD::FSUB) {
3154 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3155 if (CFP->getValueAPF().isZero())
3157 } else if (Opcode == ISD::FMUL) {
3158 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3161 // If the first operand isn't the constant, try the second
3163 CFP = dyn_cast<ConstantFPSDNode>(N2);
3170 return SDValue(CFP,0);
3172 if (CFP->isExactlyValue(1.0))
3177 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3178 assert(N1.getValueType() == N2.getValueType() &&
3179 N1.getValueType() == VT && "Binary operator types must match!");
3181 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3182 assert(N1.getValueType() == VT &&
3183 N1.getValueType().isFloatingPoint() &&
3184 N2.getValueType().isFloatingPoint() &&
3185 "Invalid FCOPYSIGN!");
3192 assert(VT == N1.getValueType() &&
3193 "Shift operators return type must be the same as their first arg");
3194 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3195 "Shifts only work on integers");
3196 assert((!VT.isVector() || VT == N2.getValueType()) &&
3197 "Vector shift amounts must be in the same as their first arg");
3198 // Verify that the shift amount VT is bit enough to hold valid shift
3199 // amounts. This catches things like trying to shift an i1024 value by an
3200 // i8, which is easy to fall into in generic code that uses
3201 // TLI.getShiftAmount().
3202 assert(N2.getValueType().getSizeInBits() >=
3203 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3204 "Invalid use of small shift amount with oversized value!");
3206 // Always fold shifts of i1 values so the code generator doesn't need to
3207 // handle them. Since we know the size of the shift has to be less than the
3208 // size of the value, the shift/rotate count is guaranteed to be zero.
3211 if (N2C && N2C->isNullValue())
3214 case ISD::FP_ROUND_INREG: {
3215 EVT EVT = cast<VTSDNode>(N2)->getVT();
3216 assert(VT == N1.getValueType() && "Not an inreg round!");
3217 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3218 "Cannot FP_ROUND_INREG integer types");
3219 assert(EVT.isVector() == VT.isVector() &&
3220 "FP_ROUND_INREG type should be vector iff the operand "
3222 assert((!EVT.isVector() ||
3223 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3224 "Vector element counts must match in FP_ROUND_INREG");
3225 assert(EVT.bitsLE(VT) && "Not rounding down!");
3227 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3231 assert(VT.isFloatingPoint() &&
3232 N1.getValueType().isFloatingPoint() &&
3233 VT.bitsLE(N1.getValueType()) &&
3234 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3235 if (N1.getValueType() == VT) return N1; // noop conversion.
3237 case ISD::AssertSext:
3238 case ISD::AssertZext: {
3239 EVT EVT = cast<VTSDNode>(N2)->getVT();
3240 assert(VT == N1.getValueType() && "Not an inreg extend!");
3241 assert(VT.isInteger() && EVT.isInteger() &&
3242 "Cannot *_EXTEND_INREG FP types");
3243 assert(!EVT.isVector() &&
3244 "AssertSExt/AssertZExt type should be the vector element type "
3245 "rather than the vector type!");
3246 assert(EVT.bitsLE(VT) && "Not extending!");
3247 if (VT == EVT) return N1; // noop assertion.
3250 case ISD::SIGN_EXTEND_INREG: {
3251 EVT EVT = cast<VTSDNode>(N2)->getVT();
3252 assert(VT == N1.getValueType() && "Not an inreg extend!");
3253 assert(VT.isInteger() && EVT.isInteger() &&
3254 "Cannot *_EXTEND_INREG FP types");
3255 assert(EVT.isVector() == VT.isVector() &&
3256 "SIGN_EXTEND_INREG type should be vector iff the operand "
3258 assert((!EVT.isVector() ||
3259 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3260 "Vector element counts must match in SIGN_EXTEND_INREG");
3261 assert(EVT.bitsLE(VT) && "Not extending!");
3262 if (EVT == VT) return N1; // Not actually extending
3265 APInt Val = N1C->getAPIntValue();
3266 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3267 Val <<= Val.getBitWidth()-FromBits;
3268 Val = Val.ashr(Val.getBitWidth()-FromBits);
3269 return getConstant(Val, VT);
3273 case ISD::EXTRACT_VECTOR_ELT:
3274 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3275 if (N1.getOpcode() == ISD::UNDEF)
3276 return getUNDEF(VT);
3278 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3279 // expanding copies of large vectors from registers.
3281 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3282 N1.getNumOperands() > 0) {
3284 N1.getOperand(0).getValueType().getVectorNumElements();
3285 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3286 N1.getOperand(N2C->getZExtValue() / Factor),
3287 getConstant(N2C->getZExtValue() % Factor,
3288 N2.getValueType()));
3291 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3292 // expanding large vector constants.
3293 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3294 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3296 if (VT != Elt.getValueType())
3297 // If the vector element type is not legal, the BUILD_VECTOR operands
3298 // are promoted and implicitly truncated, and the result implicitly
3299 // extended. Make that explicit here.
3300 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3305 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3306 // operations are lowered to scalars.
3307 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3308 // If the indices are the same, return the inserted element else
3309 // if the indices are known different, extract the element from
3310 // the original vector.
3311 SDValue N1Op2 = N1.getOperand(2);
3312 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3314 if (N1Op2C && N2C) {
3315 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3316 if (VT == N1.getOperand(1).getValueType())
3317 return N1.getOperand(1);
3319 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3322 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3326 case ISD::EXTRACT_ELEMENT:
3327 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3328 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3329 (N1.getValueType().isInteger() == VT.isInteger()) &&
3330 N1.getValueType() != VT &&
3331 "Wrong types for EXTRACT_ELEMENT!");
3333 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3334 // 64-bit integers into 32-bit parts. Instead of building the extract of
3335 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3336 if (N1.getOpcode() == ISD::BUILD_PAIR)
3337 return N1.getOperand(N2C->getZExtValue());
3339 // EXTRACT_ELEMENT of a constant int is also very common.
3340 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3341 unsigned ElementSize = VT.getSizeInBits();
3342 unsigned Shift = ElementSize * N2C->getZExtValue();
3343 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3344 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3347 case ISD::EXTRACT_SUBVECTOR: {
3349 if (VT.isSimple() && N1.getValueType().isSimple()) {
3350 assert(VT.isVector() && N1.getValueType().isVector() &&
3351 "Extract subvector VTs must be a vectors!");
3352 assert(VT.getVectorElementType() ==
3353 N1.getValueType().getVectorElementType() &&
3354 "Extract subvector VTs must have the same element type!");
3355 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3356 "Extract subvector must be from larger vector to smaller vector!");
3358 if (isa<ConstantSDNode>(Index.getNode())) {
3359 assert((VT.getVectorNumElements() +
3360 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3361 <= N1.getValueType().getVectorNumElements())
3362 && "Extract subvector overflow!");
3365 // Trivial extraction.
3366 if (VT.getSimpleVT() == N1.getSimpleValueType())
3373 // Perform trivial constant folding.
3374 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3375 if (SV.getNode()) return SV;
3377 // Canonicalize constant to RHS if commutative.
3378 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3379 std::swap(N1C, N2C);
3383 // Constant fold FP operations.
3384 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3385 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3386 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3388 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3389 // Canonicalize constant to RHS if commutative.
3390 std::swap(N1CFP, N2CFP);
3393 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3394 APFloat::opStatus s;
3397 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3398 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3399 return getConstantFP(V1, VT);
3402 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3403 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3404 return getConstantFP(V1, VT);
3407 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3408 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3409 return getConstantFP(V1, VT);
3412 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3413 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3414 s!=APFloat::opDivByZero)) {
3415 return getConstantFP(V1, VT);
3419 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3420 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3421 s!=APFloat::opDivByZero)) {
3422 return getConstantFP(V1, VT);
3425 case ISD::FCOPYSIGN:
3427 return getConstantFP(V1, VT);
3432 if (Opcode == ISD::FP_ROUND) {
3433 APFloat V = N1CFP->getValueAPF(); // make copy
3435 // This can return overflow, underflow, or inexact; we don't care.
3436 // FIXME need to be more flexible about rounding mode.
3437 (void)V.convert(EVTToAPFloatSemantics(VT),
3438 APFloat::rmNearestTiesToEven, &ignored);
3439 return getConstantFP(V, VT);
3443 // Canonicalize an UNDEF to the RHS, even over a constant.
3444 if (N1.getOpcode() == ISD::UNDEF) {
3445 if (isCommutativeBinOp(Opcode)) {
3449 case ISD::FP_ROUND_INREG:
3450 case ISD::SIGN_EXTEND_INREG:
3456 return N1; // fold op(undef, arg2) -> undef
3464 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3465 // For vectors, we can't easily build an all zero vector, just return
3472 // Fold a bunch of operators when the RHS is undef.
3473 if (N2.getOpcode() == ISD::UNDEF) {
3476 if (N1.getOpcode() == ISD::UNDEF)
3477 // Handle undef ^ undef -> 0 special case. This is a common
3479 return getConstant(0, VT);
3489 return N2; // fold op(arg1, undef) -> undef
3495 if (getTarget().Options.UnsafeFPMath)
3503 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3504 // For vectors, we can't easily build an all zero vector, just return
3509 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3510 // For vectors, we can't easily build an all one vector, just return
3518 // Memoize this node if possible.
3520 SDVTList VTs = getVTList(VT);
3521 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3522 if (VT != MVT::Glue) {
3523 SDValue Ops[] = {N1, N2};
3524 FoldingSetNodeID ID;
3525 AddNodeIDNode(ID, Opcode, VTs, Ops);
3527 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3529 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3530 return SDValue(E, 0);
3532 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3534 CSEMap.InsertNode(N, IP);
3537 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3541 return SDValue(N, 0);
3544 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3545 SDValue N1, SDValue N2, SDValue N3) {
3546 // Perform various simplifications.
3547 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3550 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3551 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3552 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3553 if (N1CFP && N2CFP && N3CFP) {
3554 APFloat V1 = N1CFP->getValueAPF();
3555 const APFloat &V2 = N2CFP->getValueAPF();
3556 const APFloat &V3 = N3CFP->getValueAPF();
3557 APFloat::opStatus s =
3558 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3559 if (s != APFloat::opInvalidOp)
3560 return getConstantFP(V1, VT);
3564 case ISD::CONCAT_VECTORS:
3565 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3566 // one big BUILD_VECTOR.
3567 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3568 N2.getOpcode() == ISD::BUILD_VECTOR &&
3569 N3.getOpcode() == ISD::BUILD_VECTOR) {
3570 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3571 N1.getNode()->op_end());
3572 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3573 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3574 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3578 // Use FoldSetCC to simplify SETCC's.
3579 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3580 if (Simp.getNode()) return Simp;
3585 if (N1C->getZExtValue())
3586 return N2; // select true, X, Y -> X
3587 return N3; // select false, X, Y -> Y
3590 if (N2 == N3) return N2; // select C, X, X -> X
3592 case ISD::VECTOR_SHUFFLE:
3593 llvm_unreachable("should use getVectorShuffle constructor!");
3594 case ISD::INSERT_SUBVECTOR: {
3596 if (VT.isSimple() && N1.getValueType().isSimple()
3597 && N2.getValueType().isSimple()) {
3598 assert(VT.isVector() && N1.getValueType().isVector() &&
3599 N2.getValueType().isVector() &&
3600 "Insert subvector VTs must be a vectors");
3601 assert(VT == N1.getValueType() &&
3602 "Dest and insert subvector source types must match!");
3603 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3604 "Insert subvector must be from smaller vector to larger vector!");
3605 if (isa<ConstantSDNode>(Index.getNode())) {
3606 assert((N2.getValueType().getVectorNumElements() +
3607 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3608 <= VT.getVectorNumElements())
3609 && "Insert subvector overflow!");
3612 // Trivial insertion.
3613 if (VT.getSimpleVT() == N2.getSimpleValueType())
3619 // Fold bit_convert nodes from a type to themselves.
3620 if (N1.getValueType() == VT)
3625 // Memoize node if it doesn't produce a flag.
3627 SDVTList VTs = getVTList(VT);
3628 if (VT != MVT::Glue) {
3629 SDValue Ops[] = { N1, N2, N3 };
3630 FoldingSetNodeID ID;
3631 AddNodeIDNode(ID, Opcode, VTs, Ops);
3633 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3634 return SDValue(E, 0);
3636 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3637 DL.getDebugLoc(), VTs, N1, N2, N3);
3638 CSEMap.InsertNode(N, IP);
3640 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3641 DL.getDebugLoc(), VTs, N1, N2, N3);
3645 return SDValue(N, 0);
3648 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3649 SDValue N1, SDValue N2, SDValue N3,
3651 SDValue Ops[] = { N1, N2, N3, N4 };
3652 return getNode(Opcode, DL, VT, Ops);
3655 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3656 SDValue N1, SDValue N2, SDValue N3,
3657 SDValue N4, SDValue N5) {
3658 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3659 return getNode(Opcode, DL, VT, Ops);
3662 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3663 /// the incoming stack arguments to be loaded from the stack.
3664 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3665 SmallVector<SDValue, 8> ArgChains;
3667 // Include the original chain at the beginning of the list. When this is
3668 // used by target LowerCall hooks, this helps legalize find the
3669 // CALLSEQ_BEGIN node.
3670 ArgChains.push_back(Chain);
3672 // Add a chain value for each stack argument.
3673 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3674 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3675 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3676 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3677 if (FI->getIndex() < 0)
3678 ArgChains.push_back(SDValue(L, 1));
3680 // Build a tokenfactor for all the chains.
3681 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3684 /// getMemsetValue - Vectorized representation of the memset value
3686 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3688 assert(Value.getOpcode() != ISD::UNDEF);
3690 unsigned NumBits = VT.getScalarType().getSizeInBits();
3691 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3692 assert(C->getAPIntValue().getBitWidth() == 8);
3693 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3695 return DAG.getConstant(Val, VT);
3696 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3699 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3701 // Use a multiplication with 0x010101... to extend the input to the
3703 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3704 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3710 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3711 /// used when a memcpy is turned into a memset when the source is a constant
3713 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3714 const TargetLowering &TLI, StringRef Str) {
3715 // Handle vector with all elements zero.
3718 return DAG.getConstant(0, VT);
3719 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3720 return DAG.getConstantFP(0.0, VT);
3721 else if (VT.isVector()) {
3722 unsigned NumElts = VT.getVectorNumElements();
3723 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3724 return DAG.getNode(ISD::BITCAST, dl, VT,
3725 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3728 llvm_unreachable("Expected type!");
3731 assert(!VT.isVector() && "Can't handle vector type here!");
3732 unsigned NumVTBits = VT.getSizeInBits();
3733 unsigned NumVTBytes = NumVTBits / 8;
3734 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3736 APInt Val(NumVTBits, 0);
3737 if (TLI.isLittleEndian()) {
3738 for (unsigned i = 0; i != NumBytes; ++i)
3739 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3741 for (unsigned i = 0; i != NumBytes; ++i)
3742 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3745 // If the "cost" of materializing the integer immediate is less than the cost
3746 // of a load, then it is cost effective to turn the load into the immediate.
3747 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3748 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3749 return DAG.getConstant(Val, VT);
3750 return SDValue(nullptr, 0);
3753 /// getMemBasePlusOffset - Returns base and offset node for the
3755 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3756 SelectionDAG &DAG) {
3757 EVT VT = Base.getValueType();
3758 return DAG.getNode(ISD::ADD, dl,
3759 VT, Base, DAG.getConstant(Offset, VT));
3762 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3764 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3765 unsigned SrcDelta = 0;
3766 GlobalAddressSDNode *G = nullptr;
3767 if (Src.getOpcode() == ISD::GlobalAddress)
3768 G = cast<GlobalAddressSDNode>(Src);
3769 else if (Src.getOpcode() == ISD::ADD &&
3770 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3771 Src.getOperand(1).getOpcode() == ISD::Constant) {
3772 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3773 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3778 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3781 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3782 /// to replace the memset / memcpy. Return true if the number of memory ops
3783 /// is below the threshold. It returns the types of the sequence of
3784 /// memory ops to perform memset / memcpy by reference.
3785 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3786 unsigned Limit, uint64_t Size,
3787 unsigned DstAlign, unsigned SrcAlign,
3793 const TargetLowering &TLI) {
3794 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3795 "Expecting memcpy / memset source to meet alignment requirement!");
3796 // If 'SrcAlign' is zero, that means the memory operation does not need to
3797 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3798 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3799 // is the specified alignment of the memory operation. If it is zero, that
3800 // means it's possible to change the alignment of the destination.
3801 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3802 // not need to be loaded.
3803 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3804 IsMemset, ZeroMemset, MemcpyStrSrc,
3805 DAG.getMachineFunction());
3807 if (VT == MVT::Other) {
3809 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3810 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3811 VT = TLI.getPointerTy();
3813 switch (DstAlign & 7) {
3814 case 0: VT = MVT::i64; break;
3815 case 4: VT = MVT::i32; break;
3816 case 2: VT = MVT::i16; break;
3817 default: VT = MVT::i8; break;
3822 while (!TLI.isTypeLegal(LVT))
3823 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3824 assert(LVT.isInteger());
3830 unsigned NumMemOps = 0;
3832 unsigned VTSize = VT.getSizeInBits() / 8;
3833 while (VTSize > Size) {
3834 // For now, only use non-vector load / store's for the left-over pieces.
3839 if (VT.isVector() || VT.isFloatingPoint()) {
3840 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3841 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3842 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3844 else if (NewVT == MVT::i64 &&
3845 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3846 TLI.isSafeMemOpType(MVT::f64)) {
3847 // i64 is usually not legal on 32-bit targets, but f64 may be.
3855 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3856 if (NewVT == MVT::i8)
3858 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3860 NewVTSize = NewVT.getSizeInBits() / 8;
3862 // If the new VT cannot cover all of the remaining bits, then consider
3863 // issuing a (or a pair of) unaligned and overlapping load / store.
3864 // FIXME: Only does this for 64-bit or more since we don't have proper
3865 // cost model for unaligned load / store.
3868 if (NumMemOps && AllowOverlap &&
3869 VTSize >= 8 && NewVTSize < Size &&
3870 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3878 if (++NumMemOps > Limit)
3881 MemOps.push_back(VT);
3888 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3889 SDValue Chain, SDValue Dst,
3890 SDValue Src, uint64_t Size,
3891 unsigned Align, bool isVol,
3893 MachinePointerInfo DstPtrInfo,
3894 MachinePointerInfo SrcPtrInfo) {
3895 // Turn a memcpy of undef to nop.
3896 if (Src.getOpcode() == ISD::UNDEF)
3899 // Expand memcpy to a series of load and store ops if the size operand falls
3900 // below a certain threshold.
3901 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3902 // rather than maybe a humongous number of loads and stores.
3903 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3904 std::vector<EVT> MemOps;
3905 bool DstAlignCanChange = false;
3906 MachineFunction &MF = DAG.getMachineFunction();
3907 MachineFrameInfo *MFI = MF.getFrameInfo();
3909 MF.getFunction()->getAttributes().
3910 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3911 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3912 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3913 DstAlignCanChange = true;
3914 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3915 if (Align > SrcAlign)
3918 bool CopyFromStr = isMemSrcFromString(Src, Str);
3919 bool isZeroStr = CopyFromStr && Str.empty();
3920 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3922 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3923 (DstAlignCanChange ? 0 : Align),
3924 (isZeroStr ? 0 : SrcAlign),
3925 false, false, CopyFromStr, true, DAG, TLI))
3928 if (DstAlignCanChange) {
3929 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3930 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3932 // Don't promote to an alignment that would require dynamic stack
3934 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3935 if (!TRI->needsStackRealignment(MF))
3936 while (NewAlign > Align &&
3937 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3940 if (NewAlign > Align) {
3941 // Give the stack frame object a larger alignment if needed.
3942 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3943 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3948 SmallVector<SDValue, 8> OutChains;
3949 unsigned NumMemOps = MemOps.size();
3950 uint64_t SrcOff = 0, DstOff = 0;
3951 for (unsigned i = 0; i != NumMemOps; ++i) {
3953 unsigned VTSize = VT.getSizeInBits() / 8;
3954 SDValue Value, Store;
3956 if (VTSize > Size) {
3957 // Issuing an unaligned load / store pair that overlaps with the previous
3958 // pair. Adjust the offset accordingly.
3959 assert(i == NumMemOps-1 && i != 0);
3960 SrcOff -= VTSize - Size;
3961 DstOff -= VTSize - Size;
3965 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3966 // It's unlikely a store of a vector immediate can be done in a single
3967 // instruction. It would require a load from a constantpool first.
3968 // We only handle zero vectors here.
3969 // FIXME: Handle other cases where store of vector immediate is done in
3970 // a single instruction.
3971 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3972 if (Value.getNode())
3973 Store = DAG.getStore(Chain, dl, Value,
3974 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3975 DstPtrInfo.getWithOffset(DstOff), isVol,
3979 if (!Store.getNode()) {
3980 // The type might not be legal for the target. This should only happen
3981 // if the type is smaller than a legal type, as on PPC, so the right
3982 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3983 // to Load/Store if NVT==VT.
3984 // FIXME does the case above also need this?
3985 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3986 assert(NVT.bitsGE(VT));
3987 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3988 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3989 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3990 false, MinAlign(SrcAlign, SrcOff));
3991 Store = DAG.getTruncStore(Chain, dl, Value,
3992 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3993 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3996 OutChains.push_back(Store);
4002 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4005 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4006 SDValue Chain, SDValue Dst,
4007 SDValue Src, uint64_t Size,
4008 unsigned Align, bool isVol,
4010 MachinePointerInfo DstPtrInfo,
4011 MachinePointerInfo SrcPtrInfo) {
4012 // Turn a memmove of undef to nop.
4013 if (Src.getOpcode() == ISD::UNDEF)
4016 // Expand memmove to a series of load and store ops if the size operand falls
4017 // below a certain threshold.
4018 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4019 std::vector<EVT> MemOps;
4020 bool DstAlignCanChange = false;
4021 MachineFunction &MF = DAG.getMachineFunction();
4022 MachineFrameInfo *MFI = MF.getFrameInfo();
4023 bool OptSize = MF.getFunction()->getAttributes().
4024 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4025 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4026 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4027 DstAlignCanChange = true;
4028 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4029 if (Align > SrcAlign)
4031 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4033 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4034 (DstAlignCanChange ? 0 : Align), SrcAlign,
4035 false, false, false, false, DAG, TLI))
4038 if (DstAlignCanChange) {
4039 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4040 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4041 if (NewAlign > Align) {
4042 // Give the stack frame object a larger alignment if needed.
4043 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4044 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4049 uint64_t SrcOff = 0, DstOff = 0;
4050 SmallVector<SDValue, 8> LoadValues;
4051 SmallVector<SDValue, 8> LoadChains;
4052 SmallVector<SDValue, 8> OutChains;
4053 unsigned NumMemOps = MemOps.size();
4054 for (unsigned i = 0; i < NumMemOps; i++) {
4056 unsigned VTSize = VT.getSizeInBits() / 8;
4059 Value = DAG.getLoad(VT, dl, Chain,
4060 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4061 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4062 false, false, SrcAlign);
4063 LoadValues.push_back(Value);
4064 LoadChains.push_back(Value.getValue(1));
4067 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4069 for (unsigned i = 0; i < NumMemOps; i++) {
4071 unsigned VTSize = VT.getSizeInBits() / 8;
4074 Store = DAG.getStore(Chain, dl, LoadValues[i],
4075 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4076 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4077 OutChains.push_back(Store);
4081 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4084 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4087 /// \param DAG Selection DAG where lowered code is placed.
4088 /// \param dl Link to corresponding IR location.
4089 /// \param Chain Control flow dependency.
4090 /// \param Dst Pointer to destination memory location.
4091 /// \param Src Value of byte to write into the memory.
4092 /// \param Size Number of bytes to write.
4093 /// \param Align Alignment of the destination in bytes.
4094 /// \param isVol True if destination is volatile.
4095 /// \param DstPtrInfo IR information on the memory pointer.
4096 /// \returns New head in the control flow, if lowering was successful, empty
4097 /// SDValue otherwise.
4099 /// The function tries to replace 'llvm.memset' intrinsic with several store
4100 /// operations and value calculation code. This is usually profitable for small
4102 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4103 SDValue Chain, SDValue Dst,
4104 SDValue Src, uint64_t Size,
4105 unsigned Align, bool isVol,
4106 MachinePointerInfo DstPtrInfo) {
4107 // Turn a memset of undef to nop.
4108 if (Src.getOpcode() == ISD::UNDEF)
4111 // Expand memset to a series of load/store ops if the size operand
4112 // falls below a certain threshold.
4113 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4114 std::vector<EVT> MemOps;
4115 bool DstAlignCanChange = false;
4116 MachineFunction &MF = DAG.getMachineFunction();
4117 MachineFrameInfo *MFI = MF.getFrameInfo();
4118 bool OptSize = MF.getFunction()->getAttributes().
4119 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4120 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4121 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4122 DstAlignCanChange = true;
4124 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4125 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4126 Size, (DstAlignCanChange ? 0 : Align), 0,
4127 true, IsZeroVal, false, true, DAG, TLI))
4130 if (DstAlignCanChange) {
4131 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4132 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4133 if (NewAlign > Align) {
4134 // Give the stack frame object a larger alignment if needed.
4135 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4136 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4141 SmallVector<SDValue, 8> OutChains;
4142 uint64_t DstOff = 0;
4143 unsigned NumMemOps = MemOps.size();
4145 // Find the largest store and generate the bit pattern for it.
4146 EVT LargestVT = MemOps[0];
4147 for (unsigned i = 1; i < NumMemOps; i++)
4148 if (MemOps[i].bitsGT(LargestVT))
4149 LargestVT = MemOps[i];
4150 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4152 for (unsigned i = 0; i < NumMemOps; i++) {
4154 unsigned VTSize = VT.getSizeInBits() / 8;
4155 if (VTSize > Size) {
4156 // Issuing an unaligned load / store pair that overlaps with the previous
4157 // pair. Adjust the offset accordingly.
4158 assert(i == NumMemOps-1 && i != 0);
4159 DstOff -= VTSize - Size;
4162 // If this store is smaller than the largest store see whether we can get
4163 // the smaller value for free with a truncate.
4164 SDValue Value = MemSetValue;
4165 if (VT.bitsLT(LargestVT)) {
4166 if (!LargestVT.isVector() && !VT.isVector() &&
4167 TLI.isTruncateFree(LargestVT, VT))
4168 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4170 Value = getMemsetValue(Src, VT, DAG, dl);
4172 assert(Value.getValueType() == VT && "Value with wrong type.");
4173 SDValue Store = DAG.getStore(Chain, dl, Value,
4174 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4175 DstPtrInfo.getWithOffset(DstOff),
4176 isVol, false, Align);
4177 OutChains.push_back(Store);
4178 DstOff += VT.getSizeInBits() / 8;
4182 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4185 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4186 SDValue Src, SDValue Size,
4187 unsigned Align, bool isVol, bool AlwaysInline,
4188 MachinePointerInfo DstPtrInfo,
4189 MachinePointerInfo SrcPtrInfo) {
4190 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4192 // Check to see if we should lower the memcpy to loads and stores first.
4193 // For cases within the target-specified limits, this is the best choice.
4194 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4196 // Memcpy with size zero? Just return the original chain.
4197 if (ConstantSize->isNullValue())
4200 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4201 ConstantSize->getZExtValue(),Align,
4202 isVol, false, DstPtrInfo, SrcPtrInfo);
4203 if (Result.getNode())
4207 // Then check to see if we should lower the memcpy with target-specific
4208 // code. If the target chooses to do this, this is the next best.
4210 TSI->EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4211 isVol, AlwaysInline, DstPtrInfo, SrcPtrInfo);
4212 if (Result.getNode())
4215 // If we really need inline code and the target declined to provide it,
4216 // use a (potentially long) sequence of loads and stores.
4218 assert(ConstantSize && "AlwaysInline requires a constant size!");
4219 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4220 ConstantSize->getZExtValue(), Align, isVol,
4221 true, DstPtrInfo, SrcPtrInfo);
4224 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4225 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4226 // respect volatile, so they may do things like read or write memory
4227 // beyond the given memory regions. But fixing this isn't easy, and most
4228 // people don't care.
4230 // Emit a library call.
4231 TargetLowering::ArgListTy Args;
4232 TargetLowering::ArgListEntry Entry;
4233 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4234 Entry.Node = Dst; Args.push_back(Entry);
4235 Entry.Node = Src; Args.push_back(Entry);
4236 Entry.Node = Size; Args.push_back(Entry);
4237 // FIXME: pass in SDLoc
4238 TargetLowering::CallLoweringInfo CLI(*this);
4239 CLI.setDebugLoc(dl).setChain(Chain)
4240 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4241 Type::getVoidTy(*getContext()),
4242 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4243 TLI->getPointerTy()), std::move(Args), 0)
4244 .setDiscardResult();
4245 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4247 return CallResult.second;
4250 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4251 SDValue Src, SDValue Size,
4252 unsigned Align, bool isVol,
4253 MachinePointerInfo DstPtrInfo,
4254 MachinePointerInfo SrcPtrInfo) {
4255 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4257 // Check to see if we should lower the memmove to loads and stores first.
4258 // For cases within the target-specified limits, this is the best choice.
4259 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4261 // Memmove with size zero? Just return the original chain.
4262 if (ConstantSize->isNullValue())
4266 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4267 ConstantSize->getZExtValue(), Align, isVol,
4268 false, DstPtrInfo, SrcPtrInfo);
4269 if (Result.getNode())
4273 // Then check to see if we should lower the memmove with target-specific
4274 // code. If the target chooses to do this, this is the next best.
4275 SDValue Result = TSI->EmitTargetCodeForMemmove(
4276 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4277 if (Result.getNode())
4280 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4281 // not be safe. See memcpy above for more details.
4283 // Emit a library call.
4284 TargetLowering::ArgListTy Args;
4285 TargetLowering::ArgListEntry Entry;
4286 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4287 Entry.Node = Dst; Args.push_back(Entry);
4288 Entry.Node = Src; Args.push_back(Entry);
4289 Entry.Node = Size; Args.push_back(Entry);
4290 // FIXME: pass in SDLoc
4291 TargetLowering::CallLoweringInfo CLI(*this);
4292 CLI.setDebugLoc(dl).setChain(Chain)
4293 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4294 Type::getVoidTy(*getContext()),
4295 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4296 TLI->getPointerTy()), std::move(Args), 0)
4297 .setDiscardResult();
4298 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4300 return CallResult.second;
4303 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4304 SDValue Src, SDValue Size,
4305 unsigned Align, bool isVol,
4306 MachinePointerInfo DstPtrInfo) {
4307 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4309 // Check to see if we should lower the memset to stores first.
4310 // For cases within the target-specified limits, this is the best choice.
4311 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4313 // Memset with size zero? Just return the original chain.
4314 if (ConstantSize->isNullValue())
4318 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4319 Align, isVol, DstPtrInfo);
4321 if (Result.getNode())
4325 // Then check to see if we should lower the memset with target-specific
4326 // code. If the target chooses to do this, this is the next best.
4327 SDValue Result = TSI->EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src,
4328 Size, Align, isVol, DstPtrInfo);
4329 if (Result.getNode())
4332 // Emit a library call.
4333 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4334 TargetLowering::ArgListTy Args;
4335 TargetLowering::ArgListEntry Entry;
4336 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4337 Args.push_back(Entry);
4339 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4340 Args.push_back(Entry);
4342 Entry.Ty = IntPtrTy;
4343 Args.push_back(Entry);
4345 // FIXME: pass in SDLoc
4346 TargetLowering::CallLoweringInfo CLI(*this);
4347 CLI.setDebugLoc(dl).setChain(Chain)
4348 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4349 Type::getVoidTy(*getContext()),
4350 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4351 TLI->getPointerTy()), std::move(Args), 0)
4352 .setDiscardResult();
4354 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4355 return CallResult.second;
4358 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4359 SDVTList VTList, ArrayRef<SDValue> Ops,
4360 MachineMemOperand *MMO,
4361 AtomicOrdering SuccessOrdering,
4362 AtomicOrdering FailureOrdering,
4363 SynchronizationScope SynchScope) {
4364 FoldingSetNodeID ID;
4365 ID.AddInteger(MemVT.getRawBits());
4366 AddNodeIDNode(ID, Opcode, VTList, Ops);
4367 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4369 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4370 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4371 return SDValue(E, 0);
4374 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4375 // SDNode doesn't have access to it. This memory will be "leaked" when
4376 // the node is deallocated, but recovered when the allocator is released.
4377 // If the number of operands is less than 5 we use AtomicSDNode's internal
4379 unsigned NumOps = Ops.size();
4380 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4383 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4384 dl.getDebugLoc(), VTList, MemVT,
4385 Ops.data(), DynOps, NumOps, MMO,
4386 SuccessOrdering, FailureOrdering,
4388 CSEMap.InsertNode(N, IP);
4390 return SDValue(N, 0);
4393 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4394 SDVTList VTList, ArrayRef<SDValue> Ops,
4395 MachineMemOperand *MMO,
4396 AtomicOrdering Ordering,
4397 SynchronizationScope SynchScope) {
4398 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4399 Ordering, SynchScope);
4402 SDValue SelectionDAG::getAtomicCmpSwap(
4403 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4404 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4405 unsigned Alignment, AtomicOrdering SuccessOrdering,
4406 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4407 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4408 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4409 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4411 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4412 Alignment = getEVTAlignment(MemVT);
4414 MachineFunction &MF = getMachineFunction();
4416 // FIXME: Volatile isn't really correct; we should keep track of atomic
4417 // orderings in the memoperand.
4418 unsigned Flags = MachineMemOperand::MOVolatile;
4419 Flags |= MachineMemOperand::MOLoad;
4420 Flags |= MachineMemOperand::MOStore;
4422 MachineMemOperand *MMO =
4423 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4425 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4426 SuccessOrdering, FailureOrdering, SynchScope);
4429 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4430 SDVTList VTs, SDValue Chain, SDValue Ptr,
4431 SDValue Cmp, SDValue Swp,
4432 MachineMemOperand *MMO,
4433 AtomicOrdering SuccessOrdering,
4434 AtomicOrdering FailureOrdering,
4435 SynchronizationScope SynchScope) {
4436 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4437 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4438 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4440 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4441 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4442 SuccessOrdering, FailureOrdering, SynchScope);
4445 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4447 SDValue Ptr, SDValue Val,
4448 const Value* PtrVal,
4450 AtomicOrdering Ordering,
4451 SynchronizationScope SynchScope) {
4452 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4453 Alignment = getEVTAlignment(MemVT);
4455 MachineFunction &MF = getMachineFunction();
4456 // An atomic store does not load. An atomic load does not store.
4457 // (An atomicrmw obviously both loads and stores.)
4458 // For now, atomics are considered to be volatile always, and they are
4460 // FIXME: Volatile isn't really correct; we should keep track of atomic
4461 // orderings in the memoperand.
4462 unsigned Flags = MachineMemOperand::MOVolatile;
4463 if (Opcode != ISD::ATOMIC_STORE)
4464 Flags |= MachineMemOperand::MOLoad;
4465 if (Opcode != ISD::ATOMIC_LOAD)
4466 Flags |= MachineMemOperand::MOStore;
4468 MachineMemOperand *MMO =
4469 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4470 MemVT.getStoreSize(), Alignment);
4472 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4473 Ordering, SynchScope);
4476 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4478 SDValue Ptr, SDValue Val,
4479 MachineMemOperand *MMO,
4480 AtomicOrdering Ordering,
4481 SynchronizationScope SynchScope) {
4482 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4483 Opcode == ISD::ATOMIC_LOAD_SUB ||
4484 Opcode == ISD::ATOMIC_LOAD_AND ||
4485 Opcode == ISD::ATOMIC_LOAD_OR ||
4486 Opcode == ISD::ATOMIC_LOAD_XOR ||
4487 Opcode == ISD::ATOMIC_LOAD_NAND ||
4488 Opcode == ISD::ATOMIC_LOAD_MIN ||
4489 Opcode == ISD::ATOMIC_LOAD_MAX ||
4490 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4491 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4492 Opcode == ISD::ATOMIC_SWAP ||
4493 Opcode == ISD::ATOMIC_STORE) &&
4494 "Invalid Atomic Op");
4496 EVT VT = Val.getValueType();
4498 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4499 getVTList(VT, MVT::Other);
4500 SDValue Ops[] = {Chain, Ptr, Val};
4501 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4504 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4505 EVT VT, SDValue Chain,
4507 MachineMemOperand *MMO,
4508 AtomicOrdering Ordering,
4509 SynchronizationScope SynchScope) {
4510 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4512 SDVTList VTs = getVTList(VT, MVT::Other);
4513 SDValue Ops[] = {Chain, Ptr};
4514 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4517 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4518 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4519 if (Ops.size() == 1)
4522 SmallVector<EVT, 4> VTs;
4523 VTs.reserve(Ops.size());
4524 for (unsigned i = 0; i < Ops.size(); ++i)
4525 VTs.push_back(Ops[i].getValueType());
4526 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4530 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4531 ArrayRef<SDValue> Ops,
4532 EVT MemVT, MachinePointerInfo PtrInfo,
4533 unsigned Align, bool Vol,
4534 bool ReadMem, bool WriteMem, unsigned Size) {
4535 if (Align == 0) // Ensure that codegen never sees alignment 0
4536 Align = getEVTAlignment(MemVT);
4538 MachineFunction &MF = getMachineFunction();
4541 Flags |= MachineMemOperand::MOStore;
4543 Flags |= MachineMemOperand::MOLoad;
4545 Flags |= MachineMemOperand::MOVolatile;
4547 Size = MemVT.getStoreSize();
4548 MachineMemOperand *MMO =
4549 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4551 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4555 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4556 ArrayRef<SDValue> Ops, EVT MemVT,
4557 MachineMemOperand *MMO) {
4558 assert((Opcode == ISD::INTRINSIC_VOID ||
4559 Opcode == ISD::INTRINSIC_W_CHAIN ||
4560 Opcode == ISD::PREFETCH ||
4561 Opcode == ISD::LIFETIME_START ||
4562 Opcode == ISD::LIFETIME_END ||
4563 (Opcode <= INT_MAX &&
4564 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4565 "Opcode is not a memory-accessing opcode!");
4567 // Memoize the node unless it returns a flag.
4568 MemIntrinsicSDNode *N;
4569 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4570 FoldingSetNodeID ID;
4571 AddNodeIDNode(ID, Opcode, VTList, Ops);
4572 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4574 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4575 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4576 return SDValue(E, 0);
4579 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4580 dl.getDebugLoc(), VTList, Ops,
4582 CSEMap.InsertNode(N, IP);
4584 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4585 dl.getDebugLoc(), VTList, Ops,
4589 return SDValue(N, 0);
4592 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4593 /// MachinePointerInfo record from it. This is particularly useful because the
4594 /// code generator has many cases where it doesn't bother passing in a
4595 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4596 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4597 // If this is FI+Offset, we can model it.
4598 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4599 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4601 // If this is (FI+Offset1)+Offset2, we can model it.
4602 if (Ptr.getOpcode() != ISD::ADD ||
4603 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4604 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4605 return MachinePointerInfo();
4607 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4608 return MachinePointerInfo::getFixedStack(FI, Offset+
4609 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4612 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4613 /// MachinePointerInfo record from it. This is particularly useful because the
4614 /// code generator has many cases where it doesn't bother passing in a
4615 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4616 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4617 // If the 'Offset' value isn't a constant, we can't handle this.
4618 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4619 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4620 if (OffsetOp.getOpcode() == ISD::UNDEF)
4621 return InferPointerInfo(Ptr);
4622 return MachinePointerInfo();
4627 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4628 EVT VT, SDLoc dl, SDValue Chain,
4629 SDValue Ptr, SDValue Offset,
4630 MachinePointerInfo PtrInfo, EVT MemVT,
4631 bool isVolatile, bool isNonTemporal, bool isInvariant,
4632 unsigned Alignment, const AAMDNodes &AAInfo,
4633 const MDNode *Ranges) {
4634 assert(Chain.getValueType() == MVT::Other &&
4635 "Invalid chain type");
4636 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4637 Alignment = getEVTAlignment(VT);
4639 unsigned Flags = MachineMemOperand::MOLoad;
4641 Flags |= MachineMemOperand::MOVolatile;
4643 Flags |= MachineMemOperand::MONonTemporal;
4645 Flags |= MachineMemOperand::MOInvariant;
4647 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4649 if (PtrInfo.V.isNull())
4650 PtrInfo = InferPointerInfo(Ptr, Offset);
4652 MachineFunction &MF = getMachineFunction();
4653 MachineMemOperand *MMO =
4654 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4656 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4660 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4661 EVT VT, SDLoc dl, SDValue Chain,
4662 SDValue Ptr, SDValue Offset, EVT MemVT,
4663 MachineMemOperand *MMO) {
4665 ExtType = ISD::NON_EXTLOAD;
4666 } else if (ExtType == ISD::NON_EXTLOAD) {
4667 assert(VT == MemVT && "Non-extending load from different memory type!");
4670 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4671 "Should only be an extending load, not truncating!");
4672 assert(VT.isInteger() == MemVT.isInteger() &&
4673 "Cannot convert from FP to Int or Int -> FP!");
4674 assert(VT.isVector() == MemVT.isVector() &&
4675 "Cannot use trunc store to convert to or from a vector!");
4676 assert((!VT.isVector() ||
4677 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4678 "Cannot use trunc store to change the number of vector elements!");
4681 bool Indexed = AM != ISD::UNINDEXED;
4682 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4683 "Unindexed load with an offset!");
4685 SDVTList VTs = Indexed ?
4686 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4687 SDValue Ops[] = { Chain, Ptr, Offset };
4688 FoldingSetNodeID ID;
4689 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4690 ID.AddInteger(MemVT.getRawBits());
4691 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4692 MMO->isNonTemporal(),
4693 MMO->isInvariant()));
4694 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4696 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4697 cast<LoadSDNode>(E)->refineAlignment(MMO);
4698 return SDValue(E, 0);
4700 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4701 dl.getDebugLoc(), VTs, AM, ExtType,
4703 CSEMap.InsertNode(N, IP);
4705 return SDValue(N, 0);
4708 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4709 SDValue Chain, SDValue Ptr,
4710 MachinePointerInfo PtrInfo,
4711 bool isVolatile, bool isNonTemporal,
4712 bool isInvariant, unsigned Alignment,
4713 const AAMDNodes &AAInfo,
4714 const MDNode *Ranges) {
4715 SDValue Undef = getUNDEF(Ptr.getValueType());
4716 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4717 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4721 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4722 SDValue Chain, SDValue Ptr,
4723 MachineMemOperand *MMO) {
4724 SDValue Undef = getUNDEF(Ptr.getValueType());
4725 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4729 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4730 SDValue Chain, SDValue Ptr,
4731 MachinePointerInfo PtrInfo, EVT MemVT,
4732 bool isVolatile, bool isNonTemporal,
4733 bool isInvariant, unsigned Alignment,
4734 const AAMDNodes &AAInfo) {
4735 SDValue Undef = getUNDEF(Ptr.getValueType());
4736 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4737 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4742 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4743 SDValue Chain, SDValue Ptr, EVT MemVT,
4744 MachineMemOperand *MMO) {
4745 SDValue Undef = getUNDEF(Ptr.getValueType());
4746 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4751 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4752 SDValue Offset, ISD::MemIndexedMode AM) {
4753 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4754 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4755 "Load is already a indexed load!");
4756 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4757 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4758 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4759 false, LD->getAlignment());
4762 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4763 SDValue Ptr, MachinePointerInfo PtrInfo,
4764 bool isVolatile, bool isNonTemporal,
4765 unsigned Alignment, const AAMDNodes &AAInfo) {
4766 assert(Chain.getValueType() == MVT::Other &&
4767 "Invalid chain type");
4768 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4769 Alignment = getEVTAlignment(Val.getValueType());
4771 unsigned Flags = MachineMemOperand::MOStore;
4773 Flags |= MachineMemOperand::MOVolatile;
4775 Flags |= MachineMemOperand::MONonTemporal;
4777 if (PtrInfo.V.isNull())
4778 PtrInfo = InferPointerInfo(Ptr);
4780 MachineFunction &MF = getMachineFunction();
4781 MachineMemOperand *MMO =
4782 MF.getMachineMemOperand(PtrInfo, Flags,
4783 Val.getValueType().getStoreSize(), Alignment,
4786 return getStore(Chain, dl, Val, Ptr, MMO);
4789 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4790 SDValue Ptr, MachineMemOperand *MMO) {
4791 assert(Chain.getValueType() == MVT::Other &&
4792 "Invalid chain type");
4793 EVT VT = Val.getValueType();
4794 SDVTList VTs = getVTList(MVT::Other);
4795 SDValue Undef = getUNDEF(Ptr.getValueType());
4796 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4797 FoldingSetNodeID ID;
4798 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4799 ID.AddInteger(VT.getRawBits());
4800 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4801 MMO->isNonTemporal(), MMO->isInvariant()));
4802 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4804 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4805 cast<StoreSDNode>(E)->refineAlignment(MMO);
4806 return SDValue(E, 0);
4808 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4809 dl.getDebugLoc(), VTs,
4810 ISD::UNINDEXED, false, VT, MMO);
4811 CSEMap.InsertNode(N, IP);
4813 return SDValue(N, 0);
4816 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4817 SDValue Ptr, MachinePointerInfo PtrInfo,
4818 EVT SVT,bool isVolatile, bool isNonTemporal,
4820 const AAMDNodes &AAInfo) {
4821 assert(Chain.getValueType() == MVT::Other &&
4822 "Invalid chain type");
4823 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4824 Alignment = getEVTAlignment(SVT);
4826 unsigned Flags = MachineMemOperand::MOStore;
4828 Flags |= MachineMemOperand::MOVolatile;
4830 Flags |= MachineMemOperand::MONonTemporal;
4832 if (PtrInfo.V.isNull())
4833 PtrInfo = InferPointerInfo(Ptr);
4835 MachineFunction &MF = getMachineFunction();
4836 MachineMemOperand *MMO =
4837 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4840 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4843 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4844 SDValue Ptr, EVT SVT,
4845 MachineMemOperand *MMO) {
4846 EVT VT = Val.getValueType();
4848 assert(Chain.getValueType() == MVT::Other &&
4849 "Invalid chain type");
4851 return getStore(Chain, dl, Val, Ptr, MMO);
4853 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4854 "Should only be a truncating store, not extending!");
4855 assert(VT.isInteger() == SVT.isInteger() &&
4856 "Can't do FP-INT conversion!");
4857 assert(VT.isVector() == SVT.isVector() &&
4858 "Cannot use trunc store to convert to or from a vector!");
4859 assert((!VT.isVector() ||
4860 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4861 "Cannot use trunc store to change the number of vector elements!");
4863 SDVTList VTs = getVTList(MVT::Other);
4864 SDValue Undef = getUNDEF(Ptr.getValueType());
4865 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4866 FoldingSetNodeID ID;
4867 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4868 ID.AddInteger(SVT.getRawBits());
4869 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4870 MMO->isNonTemporal(), MMO->isInvariant()));
4871 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4873 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4874 cast<StoreSDNode>(E)->refineAlignment(MMO);
4875 return SDValue(E, 0);
4877 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4878 dl.getDebugLoc(), VTs,
4879 ISD::UNINDEXED, true, SVT, MMO);
4880 CSEMap.InsertNode(N, IP);
4882 return SDValue(N, 0);
4886 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4887 SDValue Offset, ISD::MemIndexedMode AM) {
4888 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4889 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4890 "Store is already a indexed store!");
4891 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4892 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4893 FoldingSetNodeID ID;
4894 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4895 ID.AddInteger(ST->getMemoryVT().getRawBits());
4896 ID.AddInteger(ST->getRawSubclassData());
4897 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4899 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4900 return SDValue(E, 0);
4902 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4903 dl.getDebugLoc(), VTs, AM,
4904 ST->isTruncatingStore(),
4906 ST->getMemOperand());
4907 CSEMap.InsertNode(N, IP);
4909 return SDValue(N, 0);
4912 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4913 SDValue Chain, SDValue Ptr,
4916 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4917 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4920 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4921 ArrayRef<SDUse> Ops) {
4922 switch (Ops.size()) {
4923 case 0: return getNode(Opcode, DL, VT);
4924 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4925 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4926 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4930 // Copy from an SDUse array into an SDValue array for use with
4931 // the regular getNode logic.
4932 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4933 return getNode(Opcode, DL, VT, NewOps);
4936 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4937 ArrayRef<SDValue> Ops) {
4938 unsigned NumOps = Ops.size();
4940 case 0: return getNode(Opcode, DL, VT);
4941 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4942 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4943 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4949 case ISD::SELECT_CC: {
4950 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4951 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4952 "LHS and RHS of condition must have same type!");
4953 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4954 "True and False arms of SelectCC must have same type!");
4955 assert(Ops[2].getValueType() == VT &&
4956 "select_cc node must be of same type as true and false value!");
4960 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4961 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4962 "LHS/RHS of comparison should match types!");
4969 SDVTList VTs = getVTList(VT);
4971 if (VT != MVT::Glue) {
4972 FoldingSetNodeID ID;
4973 AddNodeIDNode(ID, Opcode, VTs, Ops);
4976 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4977 return SDValue(E, 0);
4979 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4981 CSEMap.InsertNode(N, IP);
4983 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4988 return SDValue(N, 0);
4991 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4992 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4993 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4996 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4997 ArrayRef<SDValue> Ops) {
4998 if (VTList.NumVTs == 1)
4999 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5003 // FIXME: figure out how to safely handle things like
5004 // int foo(int x) { return 1 << (x & 255); }
5005 // int bar() { return foo(256); }
5006 case ISD::SRA_PARTS:
5007 case ISD::SRL_PARTS:
5008 case ISD::SHL_PARTS:
5009 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5010 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5011 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5012 else if (N3.getOpcode() == ISD::AND)
5013 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5014 // If the and is only masking out bits that cannot effect the shift,
5015 // eliminate the and.
5016 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5017 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5018 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5024 // Memoize the node unless it returns a flag.
5026 unsigned NumOps = Ops.size();
5027 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5028 FoldingSetNodeID ID;
5029 AddNodeIDNode(ID, Opcode, VTList, Ops);
5031 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5032 return SDValue(E, 0);
5035 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5036 DL.getDebugLoc(), VTList, Ops[0]);
5037 } else if (NumOps == 2) {
5038 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5039 DL.getDebugLoc(), VTList, Ops[0],
5041 } else if (NumOps == 3) {
5042 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5043 DL.getDebugLoc(), VTList, Ops[0],
5046 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5049 CSEMap.InsertNode(N, IP);
5052 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5053 DL.getDebugLoc(), VTList, Ops[0]);
5054 } else if (NumOps == 2) {
5055 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5056 DL.getDebugLoc(), VTList, Ops[0],
5058 } else if (NumOps == 3) {
5059 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5060 DL.getDebugLoc(), VTList, Ops[0],
5063 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5068 return SDValue(N, 0);
5071 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5072 return getNode(Opcode, DL, VTList, None);
5075 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5077 SDValue Ops[] = { N1 };
5078 return getNode(Opcode, DL, VTList, Ops);
5081 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5082 SDValue N1, SDValue N2) {
5083 SDValue Ops[] = { N1, N2 };
5084 return getNode(Opcode, DL, VTList, Ops);
5087 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5088 SDValue N1, SDValue N2, SDValue N3) {
5089 SDValue Ops[] = { N1, N2, N3 };
5090 return getNode(Opcode, DL, VTList, Ops);
5093 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5094 SDValue N1, SDValue N2, SDValue N3,
5096 SDValue Ops[] = { N1, N2, N3, N4 };
5097 return getNode(Opcode, DL, VTList, Ops);
5100 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5101 SDValue N1, SDValue N2, SDValue N3,
5102 SDValue N4, SDValue N5) {
5103 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5104 return getNode(Opcode, DL, VTList, Ops);
5107 SDVTList SelectionDAG::getVTList(EVT VT) {
5108 return makeVTList(SDNode::getValueTypeList(VT), 1);
5111 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5112 FoldingSetNodeID ID;
5114 ID.AddInteger(VT1.getRawBits());
5115 ID.AddInteger(VT2.getRawBits());
5118 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5120 EVT *Array = Allocator.Allocate<EVT>(2);
5123 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5124 VTListMap.InsertNode(Result, IP);
5126 return Result->getSDVTList();
5129 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5130 FoldingSetNodeID ID;
5132 ID.AddInteger(VT1.getRawBits());
5133 ID.AddInteger(VT2.getRawBits());
5134 ID.AddInteger(VT3.getRawBits());
5137 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5139 EVT *Array = Allocator.Allocate<EVT>(3);
5143 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5144 VTListMap.InsertNode(Result, IP);
5146 return Result->getSDVTList();
5149 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5150 FoldingSetNodeID ID;
5152 ID.AddInteger(VT1.getRawBits());
5153 ID.AddInteger(VT2.getRawBits());
5154 ID.AddInteger(VT3.getRawBits());
5155 ID.AddInteger(VT4.getRawBits());
5158 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5160 EVT *Array = Allocator.Allocate<EVT>(4);
5165 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5166 VTListMap.InsertNode(Result, IP);
5168 return Result->getSDVTList();
5171 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5172 unsigned NumVTs = VTs.size();
5173 FoldingSetNodeID ID;
5174 ID.AddInteger(NumVTs);
5175 for (unsigned index = 0; index < NumVTs; index++) {
5176 ID.AddInteger(VTs[index].getRawBits());
5180 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5182 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5183 std::copy(VTs.begin(), VTs.end(), Array);
5184 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5185 VTListMap.InsertNode(Result, IP);
5187 return Result->getSDVTList();
5191 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5192 /// specified operands. If the resultant node already exists in the DAG,
5193 /// this does not modify the specified node, instead it returns the node that
5194 /// already exists. If the resultant node does not exist in the DAG, the
5195 /// input node is returned. As a degenerate case, if you specify the same
5196 /// input operands as the node already has, the input node is returned.
5197 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5198 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5200 // Check to see if there is no change.
5201 if (Op == N->getOperand(0)) return N;
5203 // See if the modified node already exists.
5204 void *InsertPos = nullptr;
5205 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5208 // Nope it doesn't. Remove the node from its current place in the maps.
5210 if (!RemoveNodeFromCSEMaps(N))
5211 InsertPos = nullptr;
5213 // Now we update the operands.
5214 N->OperandList[0].set(Op);
5216 // If this gets put into a CSE map, add it.
5217 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5221 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5222 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5224 // Check to see if there is no change.
5225 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5226 return N; // No operands changed, just return the input node.
5228 // See if the modified node already exists.
5229 void *InsertPos = nullptr;
5230 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5233 // Nope it doesn't. Remove the node from its current place in the maps.
5235 if (!RemoveNodeFromCSEMaps(N))
5236 InsertPos = nullptr;
5238 // Now we update the operands.
5239 if (N->OperandList[0] != Op1)
5240 N->OperandList[0].set(Op1);
5241 if (N->OperandList[1] != Op2)
5242 N->OperandList[1].set(Op2);
5244 // If this gets put into a CSE map, add it.
5245 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5249 SDNode *SelectionDAG::
5250 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5251 SDValue Ops[] = { Op1, Op2, Op3 };
5252 return UpdateNodeOperands(N, Ops);
5255 SDNode *SelectionDAG::
5256 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5257 SDValue Op3, SDValue Op4) {
5258 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5259 return UpdateNodeOperands(N, Ops);
5262 SDNode *SelectionDAG::
5263 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5264 SDValue Op3, SDValue Op4, SDValue Op5) {
5265 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5266 return UpdateNodeOperands(N, Ops);
5269 SDNode *SelectionDAG::
5270 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5271 unsigned NumOps = Ops.size();
5272 assert(N->getNumOperands() == NumOps &&
5273 "Update with wrong number of operands");
5275 // Check to see if there is no change.
5276 bool AnyChange = false;
5277 for (unsigned i = 0; i != NumOps; ++i) {
5278 if (Ops[i] != N->getOperand(i)) {
5284 // No operands changed, just return the input node.
5285 if (!AnyChange) return N;
5287 // See if the modified node already exists.
5288 void *InsertPos = nullptr;
5289 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5292 // Nope it doesn't. Remove the node from its current place in the maps.
5294 if (!RemoveNodeFromCSEMaps(N))
5295 InsertPos = nullptr;
5297 // Now we update the operands.
5298 for (unsigned i = 0; i != NumOps; ++i)
5299 if (N->OperandList[i] != Ops[i])
5300 N->OperandList[i].set(Ops[i]);
5302 // If this gets put into a CSE map, add it.
5303 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5307 /// DropOperands - Release the operands and set this node to have
5309 void SDNode::DropOperands() {
5310 // Unlike the code in MorphNodeTo that does this, we don't need to
5311 // watch for dead nodes here.
5312 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5318 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5321 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5323 SDVTList VTs = getVTList(VT);
5324 return SelectNodeTo(N, MachineOpc, VTs, None);
5327 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5328 EVT VT, SDValue Op1) {
5329 SDVTList VTs = getVTList(VT);
5330 SDValue Ops[] = { Op1 };
5331 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5334 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5335 EVT VT, SDValue Op1,
5337 SDVTList VTs = getVTList(VT);
5338 SDValue Ops[] = { Op1, Op2 };
5339 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5342 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5343 EVT VT, SDValue Op1,
5344 SDValue Op2, SDValue Op3) {
5345 SDVTList VTs = getVTList(VT);
5346 SDValue Ops[] = { Op1, Op2, Op3 };
5347 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5350 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5351 EVT VT, ArrayRef<SDValue> Ops) {
5352 SDVTList VTs = getVTList(VT);
5353 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5356 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5357 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5358 SDVTList VTs = getVTList(VT1, VT2);
5359 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5362 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5364 SDVTList VTs = getVTList(VT1, VT2);
5365 return SelectNodeTo(N, MachineOpc, VTs, None);
5368 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5369 EVT VT1, EVT VT2, EVT VT3,
5370 ArrayRef<SDValue> Ops) {
5371 SDVTList VTs = getVTList(VT1, VT2, VT3);
5372 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5375 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5376 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5377 ArrayRef<SDValue> Ops) {
5378 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5379 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5382 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5385 SDVTList VTs = getVTList(VT1, VT2);
5386 SDValue Ops[] = { Op1 };
5387 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5390 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5392 SDValue Op1, SDValue Op2) {
5393 SDVTList VTs = getVTList(VT1, VT2);
5394 SDValue Ops[] = { Op1, Op2 };
5395 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5398 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5400 SDValue Op1, SDValue Op2,
5402 SDVTList VTs = getVTList(VT1, VT2);
5403 SDValue Ops[] = { Op1, Op2, Op3 };
5404 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5407 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5408 EVT VT1, EVT VT2, EVT VT3,
5409 SDValue Op1, SDValue Op2,
5411 SDVTList VTs = getVTList(VT1, VT2, VT3);
5412 SDValue Ops[] = { Op1, Op2, Op3 };
5413 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5416 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5417 SDVTList VTs,ArrayRef<SDValue> Ops) {
5418 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5419 // Reset the NodeID to -1.
5424 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5425 /// the line number information on the merged node since it is not possible to
5426 /// preserve the information that operation is associated with multiple lines.
5427 /// This will make the debugger working better at -O0, were there is a higher
5428 /// probability having other instructions associated with that line.
5430 /// For IROrder, we keep the smaller of the two
5431 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5432 DebugLoc NLoc = N->getDebugLoc();
5433 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5434 (OLoc.getDebugLoc() != NLoc)) {
5435 N->setDebugLoc(DebugLoc());
5437 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5438 N->setIROrder(Order);
5442 /// MorphNodeTo - This *mutates* the specified node to have the specified
5443 /// return type, opcode, and operands.
5445 /// Note that MorphNodeTo returns the resultant node. If there is already a
5446 /// node of the specified opcode and operands, it returns that node instead of
5447 /// the current one. Note that the SDLoc need not be the same.
5449 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5450 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5451 /// node, and because it doesn't require CSE recalculation for any of
5452 /// the node's users.
5454 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5455 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5456 /// the legalizer which maintain worklists that would need to be updated when
5457 /// deleting things.
5458 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5459 SDVTList VTs, ArrayRef<SDValue> Ops) {
5460 unsigned NumOps = Ops.size();
5461 // If an identical node already exists, use it.
5463 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5464 FoldingSetNodeID ID;
5465 AddNodeIDNode(ID, Opc, VTs, Ops);
5466 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5467 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5470 if (!RemoveNodeFromCSEMaps(N))
5473 // Start the morphing.
5475 N->ValueList = VTs.VTs;
5476 N->NumValues = VTs.NumVTs;
5478 // Clear the operands list, updating used nodes to remove this from their
5479 // use list. Keep track of any operands that become dead as a result.
5480 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5481 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5483 SDNode *Used = Use.getNode();
5485 if (Used->use_empty())
5486 DeadNodeSet.insert(Used);
5489 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5490 // Initialize the memory references information.
5491 MN->setMemRefs(nullptr, nullptr);
5492 // If NumOps is larger than the # of operands we can have in a
5493 // MachineSDNode, reallocate the operand list.
5494 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5495 if (MN->OperandsNeedDelete)
5496 delete[] MN->OperandList;
5497 if (NumOps > array_lengthof(MN->LocalOperands))
5498 // We're creating a final node that will live unmorphed for the
5499 // remainder of the current SelectionDAG iteration, so we can allocate
5500 // the operands directly out of a pool with no recycling metadata.
5501 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5502 Ops.data(), NumOps);
5504 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5505 MN->OperandsNeedDelete = false;
5507 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5509 // If NumOps is larger than the # of operands we currently have, reallocate
5510 // the operand list.
5511 if (NumOps > N->NumOperands) {
5512 if (N->OperandsNeedDelete)
5513 delete[] N->OperandList;
5514 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5515 N->OperandsNeedDelete = true;
5517 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5520 // Delete any nodes that are still dead after adding the uses for the
5522 if (!DeadNodeSet.empty()) {
5523 SmallVector<SDNode *, 16> DeadNodes;
5524 for (SDNode *N : DeadNodeSet)
5526 DeadNodes.push_back(N);
5527 RemoveDeadNodes(DeadNodes);
5531 CSEMap.InsertNode(N, IP); // Memoize the new node.
5536 /// getMachineNode - These are used for target selectors to create a new node
5537 /// with specified return type(s), MachineInstr opcode, and operands.
5539 /// Note that getMachineNode returns the resultant node. If there is already a
5540 /// node of the specified opcode and operands, it returns that node instead of
5541 /// the current one.
5543 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5544 SDVTList VTs = getVTList(VT);
5545 return getMachineNode(Opcode, dl, VTs, None);
5549 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5550 SDVTList VTs = getVTList(VT);
5551 SDValue Ops[] = { Op1 };
5552 return getMachineNode(Opcode, dl, VTs, Ops);
5556 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5557 SDValue Op1, SDValue Op2) {
5558 SDVTList VTs = getVTList(VT);
5559 SDValue Ops[] = { Op1, Op2 };
5560 return getMachineNode(Opcode, dl, VTs, Ops);
5564 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5565 SDValue Op1, SDValue Op2, SDValue Op3) {
5566 SDVTList VTs = getVTList(VT);
5567 SDValue Ops[] = { Op1, Op2, Op3 };
5568 return getMachineNode(Opcode, dl, VTs, Ops);
5572 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5573 ArrayRef<SDValue> Ops) {
5574 SDVTList VTs = getVTList(VT);
5575 return getMachineNode(Opcode, dl, VTs, Ops);
5579 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5580 SDVTList VTs = getVTList(VT1, VT2);
5581 return getMachineNode(Opcode, dl, VTs, None);
5585 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5586 EVT VT1, EVT VT2, SDValue Op1) {
5587 SDVTList VTs = getVTList(VT1, VT2);
5588 SDValue Ops[] = { Op1 };
5589 return getMachineNode(Opcode, dl, VTs, Ops);
5593 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5594 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5595 SDVTList VTs = getVTList(VT1, VT2);
5596 SDValue Ops[] = { Op1, Op2 };
5597 return getMachineNode(Opcode, dl, VTs, Ops);
5601 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5602 EVT VT1, EVT VT2, SDValue Op1,
5603 SDValue Op2, SDValue Op3) {
5604 SDVTList VTs = getVTList(VT1, VT2);
5605 SDValue Ops[] = { Op1, Op2, Op3 };
5606 return getMachineNode(Opcode, dl, VTs, Ops);
5610 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5612 ArrayRef<SDValue> Ops) {
5613 SDVTList VTs = getVTList(VT1, VT2);
5614 return getMachineNode(Opcode, dl, VTs, Ops);
5618 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5619 EVT VT1, EVT VT2, EVT VT3,
5620 SDValue Op1, SDValue Op2) {
5621 SDVTList VTs = getVTList(VT1, VT2, VT3);
5622 SDValue Ops[] = { Op1, Op2 };
5623 return getMachineNode(Opcode, dl, VTs, Ops);
5627 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5628 EVT VT1, EVT VT2, EVT VT3,
5629 SDValue Op1, SDValue Op2, SDValue Op3) {
5630 SDVTList VTs = getVTList(VT1, VT2, VT3);
5631 SDValue Ops[] = { Op1, Op2, Op3 };
5632 return getMachineNode(Opcode, dl, VTs, Ops);
5636 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5637 EVT VT1, EVT VT2, EVT VT3,
5638 ArrayRef<SDValue> Ops) {
5639 SDVTList VTs = getVTList(VT1, VT2, VT3);
5640 return getMachineNode(Opcode, dl, VTs, Ops);
5644 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5645 EVT VT2, EVT VT3, EVT VT4,
5646 ArrayRef<SDValue> Ops) {
5647 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5648 return getMachineNode(Opcode, dl, VTs, Ops);
5652 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5653 ArrayRef<EVT> ResultTys,
5654 ArrayRef<SDValue> Ops) {
5655 SDVTList VTs = getVTList(ResultTys);
5656 return getMachineNode(Opcode, dl, VTs, Ops);
5660 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5661 ArrayRef<SDValue> OpsArray) {
5662 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5665 const SDValue *Ops = OpsArray.data();
5666 unsigned NumOps = OpsArray.size();
5669 FoldingSetNodeID ID;
5670 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5672 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5673 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5677 // Allocate a new MachineSDNode.
5678 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5679 DL.getDebugLoc(), VTs);
5681 // Initialize the operands list.
5682 if (NumOps > array_lengthof(N->LocalOperands))
5683 // We're creating a final node that will live unmorphed for the
5684 // remainder of the current SelectionDAG iteration, so we can allocate
5685 // the operands directly out of a pool with no recycling metadata.
5686 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5689 N->InitOperands(N->LocalOperands, Ops, NumOps);
5690 N->OperandsNeedDelete = false;
5693 CSEMap.InsertNode(N, IP);
5699 /// getTargetExtractSubreg - A convenience function for creating
5700 /// TargetOpcode::EXTRACT_SUBREG nodes.
5702 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5704 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5705 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5706 VT, Operand, SRIdxVal);
5707 return SDValue(Subreg, 0);
5710 /// getTargetInsertSubreg - A convenience function for creating
5711 /// TargetOpcode::INSERT_SUBREG nodes.
5713 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5714 SDValue Operand, SDValue Subreg) {
5715 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5716 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5717 VT, Operand, Subreg, SRIdxVal);
5718 return SDValue(Result, 0);
5721 /// getNodeIfExists - Get the specified node if it's already available, or
5722 /// else return NULL.
5723 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5724 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5726 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5727 FoldingSetNodeID ID;
5728 AddNodeIDNode(ID, Opcode, VTList, Ops);
5729 if (isBinOpWithFlags(Opcode))
5730 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5738 /// getDbgValue - Creates a SDDbgValue node.
5741 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5742 unsigned R, bool IsIndirect, uint64_t Off,
5743 DebugLoc DL, unsigned O) {
5744 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5748 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5749 const Value *C, uint64_t Off,
5750 DebugLoc DL, unsigned O) {
5751 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5755 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5756 unsigned FI, uint64_t Off,
5757 DebugLoc DL, unsigned O) {
5758 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5763 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5764 /// pointed to by a use iterator is deleted, increment the use iterator
5765 /// so that it doesn't dangle.
5767 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5768 SDNode::use_iterator &UI;
5769 SDNode::use_iterator &UE;
5771 void NodeDeleted(SDNode *N, SDNode *E) override {
5772 // Increment the iterator as needed.
5773 while (UI != UE && N == *UI)
5778 RAUWUpdateListener(SelectionDAG &d,
5779 SDNode::use_iterator &ui,
5780 SDNode::use_iterator &ue)
5781 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5786 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5787 /// This can cause recursive merging of nodes in the DAG.
5789 /// This version assumes From has a single result value.
5791 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5792 SDNode *From = FromN.getNode();
5793 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5794 "Cannot replace with this method!");
5795 assert(From != To.getNode() && "Cannot replace uses of with self");
5797 // Iterate over all the existing uses of From. New uses will be added
5798 // to the beginning of the use list, which we avoid visiting.
5799 // This specifically avoids visiting uses of From that arise while the
5800 // replacement is happening, because any such uses would be the result
5801 // of CSE: If an existing node looks like From after one of its operands
5802 // is replaced by To, we don't want to replace of all its users with To
5803 // too. See PR3018 for more info.
5804 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5805 RAUWUpdateListener Listener(*this, UI, UE);
5809 // This node is about to morph, remove its old self from the CSE maps.
5810 RemoveNodeFromCSEMaps(User);
5812 // A user can appear in a use list multiple times, and when this
5813 // happens the uses are usually next to each other in the list.
5814 // To help reduce the number of CSE recomputations, process all
5815 // the uses of this user that we can find this way.
5817 SDUse &Use = UI.getUse();
5820 } while (UI != UE && *UI == User);
5822 // Now that we have modified User, add it back to the CSE maps. If it
5823 // already exists there, recursively merge the results together.
5824 AddModifiedNodeToCSEMaps(User);
5827 // If we just RAUW'd the root, take note.
5828 if (FromN == getRoot())
5832 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5833 /// This can cause recursive merging of nodes in the DAG.
5835 /// This version assumes that for each value of From, there is a
5836 /// corresponding value in To in the same position with the same type.
5838 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5840 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5841 assert((!From->hasAnyUseOfValue(i) ||
5842 From->getValueType(i) == To->getValueType(i)) &&
5843 "Cannot use this version of ReplaceAllUsesWith!");
5846 // Handle the trivial case.
5850 // Iterate over just the existing users of From. See the comments in
5851 // the ReplaceAllUsesWith above.
5852 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5853 RAUWUpdateListener Listener(*this, UI, UE);
5857 // This node is about to morph, remove its old self from the CSE maps.
5858 RemoveNodeFromCSEMaps(User);
5860 // A user can appear in a use list multiple times, and when this
5861 // happens the uses are usually next to each other in the list.
5862 // To help reduce the number of CSE recomputations, process all
5863 // the uses of this user that we can find this way.
5865 SDUse &Use = UI.getUse();
5868 } while (UI != UE && *UI == User);
5870 // Now that we have modified User, add it back to the CSE maps. If it
5871 // already exists there, recursively merge the results together.
5872 AddModifiedNodeToCSEMaps(User);
5875 // If we just RAUW'd the root, take note.
5876 if (From == getRoot().getNode())
5877 setRoot(SDValue(To, getRoot().getResNo()));
5880 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5881 /// This can cause recursive merging of nodes in the DAG.
5883 /// This version can replace From with any result values. To must match the
5884 /// number and types of values returned by From.
5885 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5886 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5887 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5889 // Iterate over just the existing users of From. See the comments in
5890 // the ReplaceAllUsesWith above.
5891 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5892 RAUWUpdateListener Listener(*this, UI, UE);
5896 // This node is about to morph, remove its old self from the CSE maps.
5897 RemoveNodeFromCSEMaps(User);
5899 // A user can appear in a use list multiple times, and when this
5900 // happens the uses are usually next to each other in the list.
5901 // To help reduce the number of CSE recomputations, process all
5902 // the uses of this user that we can find this way.
5904 SDUse &Use = UI.getUse();
5905 const SDValue &ToOp = To[Use.getResNo()];
5908 } while (UI != UE && *UI == User);
5910 // Now that we have modified User, add it back to the CSE maps. If it
5911 // already exists there, recursively merge the results together.
5912 AddModifiedNodeToCSEMaps(User);
5915 // If we just RAUW'd the root, take note.
5916 if (From == getRoot().getNode())
5917 setRoot(SDValue(To[getRoot().getResNo()]));
5920 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5921 /// uses of other values produced by From.getNode() alone. The Deleted
5922 /// vector is handled the same way as for ReplaceAllUsesWith.
5923 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5924 // Handle the really simple, really trivial case efficiently.
5925 if (From == To) return;
5927 // Handle the simple, trivial, case efficiently.
5928 if (From.getNode()->getNumValues() == 1) {
5929 ReplaceAllUsesWith(From, To);
5933 // Iterate over just the existing users of From. See the comments in
5934 // the ReplaceAllUsesWith above.
5935 SDNode::use_iterator UI = From.getNode()->use_begin(),
5936 UE = From.getNode()->use_end();
5937 RAUWUpdateListener Listener(*this, UI, UE);
5940 bool UserRemovedFromCSEMaps = false;
5942 // A user can appear in a use list multiple times, and when this
5943 // happens the uses are usually next to each other in the list.
5944 // To help reduce the number of CSE recomputations, process all
5945 // the uses of this user that we can find this way.
5947 SDUse &Use = UI.getUse();
5949 // Skip uses of different values from the same node.
5950 if (Use.getResNo() != From.getResNo()) {
5955 // If this node hasn't been modified yet, it's still in the CSE maps,
5956 // so remove its old self from the CSE maps.
5957 if (!UserRemovedFromCSEMaps) {
5958 RemoveNodeFromCSEMaps(User);
5959 UserRemovedFromCSEMaps = true;
5964 } while (UI != UE && *UI == User);
5966 // We are iterating over all uses of the From node, so if a use
5967 // doesn't use the specific value, no changes are made.
5968 if (!UserRemovedFromCSEMaps)
5971 // Now that we have modified User, add it back to the CSE maps. If it
5972 // already exists there, recursively merge the results together.
5973 AddModifiedNodeToCSEMaps(User);
5976 // If we just RAUW'd the root, take note.
5977 if (From == getRoot())
5982 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5983 /// to record information about a use.
5990 /// operator< - Sort Memos by User.
5991 bool operator<(const UseMemo &L, const UseMemo &R) {
5992 return (intptr_t)L.User < (intptr_t)R.User;
5996 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5997 /// uses of other values produced by From.getNode() alone. The same value
5998 /// may appear in both the From and To list. The Deleted vector is
5999 /// handled the same way as for ReplaceAllUsesWith.
6000 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6003 // Handle the simple, trivial case efficiently.
6005 return ReplaceAllUsesOfValueWith(*From, *To);
6007 // Read up all the uses and make records of them. This helps
6008 // processing new uses that are introduced during the
6009 // replacement process.
6010 SmallVector<UseMemo, 4> Uses;
6011 for (unsigned i = 0; i != Num; ++i) {
6012 unsigned FromResNo = From[i].getResNo();
6013 SDNode *FromNode = From[i].getNode();
6014 for (SDNode::use_iterator UI = FromNode->use_begin(),
6015 E = FromNode->use_end(); UI != E; ++UI) {
6016 SDUse &Use = UI.getUse();
6017 if (Use.getResNo() == FromResNo) {
6018 UseMemo Memo = { *UI, i, &Use };
6019 Uses.push_back(Memo);
6024 // Sort the uses, so that all the uses from a given User are together.
6025 std::sort(Uses.begin(), Uses.end());
6027 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6028 UseIndex != UseIndexEnd; ) {
6029 // We know that this user uses some value of From. If it is the right
6030 // value, update it.
6031 SDNode *User = Uses[UseIndex].User;
6033 // This node is about to morph, remove its old self from the CSE maps.
6034 RemoveNodeFromCSEMaps(User);
6036 // The Uses array is sorted, so all the uses for a given User
6037 // are next to each other in the list.
6038 // To help reduce the number of CSE recomputations, process all
6039 // the uses of this user that we can find this way.
6041 unsigned i = Uses[UseIndex].Index;
6042 SDUse &Use = *Uses[UseIndex].Use;
6046 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6048 // Now that we have modified User, add it back to the CSE maps. If it
6049 // already exists there, recursively merge the results together.
6050 AddModifiedNodeToCSEMaps(User);
6054 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6055 /// based on their topological order. It returns the maximum id and a vector
6056 /// of the SDNodes* in assigned order by reference.
6057 unsigned SelectionDAG::AssignTopologicalOrder() {
6059 unsigned DAGSize = 0;
6061 // SortedPos tracks the progress of the algorithm. Nodes before it are
6062 // sorted, nodes after it are unsorted. When the algorithm completes
6063 // it is at the end of the list.
6064 allnodes_iterator SortedPos = allnodes_begin();
6066 // Visit all the nodes. Move nodes with no operands to the front of
6067 // the list immediately. Annotate nodes that do have operands with their
6068 // operand count. Before we do this, the Node Id fields of the nodes
6069 // may contain arbitrary values. After, the Node Id fields for nodes
6070 // before SortedPos will contain the topological sort index, and the
6071 // Node Id fields for nodes At SortedPos and after will contain the
6072 // count of outstanding operands.
6073 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6075 checkForCycles(N, this);
6076 unsigned Degree = N->getNumOperands();
6078 // A node with no uses, add it to the result array immediately.
6079 N->setNodeId(DAGSize++);
6080 allnodes_iterator Q = N;
6082 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6083 assert(SortedPos != AllNodes.end() && "Overran node list");
6086 // Temporarily use the Node Id as scratch space for the degree count.
6087 N->setNodeId(Degree);
6091 // Visit all the nodes. As we iterate, move nodes into sorted order,
6092 // such that by the time the end is reached all nodes will be sorted.
6093 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6095 checkForCycles(N, this);
6096 // N is in sorted position, so all its uses have one less operand
6097 // that needs to be sorted.
6098 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6101 unsigned Degree = P->getNodeId();
6102 assert(Degree != 0 && "Invalid node degree");
6105 // All of P's operands are sorted, so P may sorted now.
6106 P->setNodeId(DAGSize++);
6108 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6109 assert(SortedPos != AllNodes.end() && "Overran node list");
6112 // Update P's outstanding operand count.
6113 P->setNodeId(Degree);
6116 if (I == SortedPos) {
6119 dbgs() << "Overran sorted position:\n";
6120 S->dumprFull(this); dbgs() << "\n";
6121 dbgs() << "Checking if this is due to cycles\n";
6122 checkForCycles(this, true);
6124 llvm_unreachable(nullptr);
6128 assert(SortedPos == AllNodes.end() &&
6129 "Topological sort incomplete!");
6130 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6131 "First node in topological sort is not the entry token!");
6132 assert(AllNodes.front().getNodeId() == 0 &&
6133 "First node in topological sort has non-zero id!");
6134 assert(AllNodes.front().getNumOperands() == 0 &&
6135 "First node in topological sort has operands!");
6136 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6137 "Last node in topologic sort has unexpected id!");
6138 assert(AllNodes.back().use_empty() &&
6139 "Last node in topologic sort has users!");
6140 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6144 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6145 /// value is produced by SD.
6146 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6147 DbgInfo->add(DB, SD, isParameter);
6149 SD->setHasDebugValue(true);
6152 /// TransferDbgValues - Transfer SDDbgValues.
6153 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6154 if (From == To || !From.getNode()->getHasDebugValue())
6156 SDNode *FromNode = From.getNode();
6157 SDNode *ToNode = To.getNode();
6158 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6159 SmallVector<SDDbgValue *, 2> ClonedDVs;
6160 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6162 SDDbgValue *Dbg = *I;
6163 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6165 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6166 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6167 Dbg->getDebugLoc(), Dbg->getOrder());
6168 ClonedDVs.push_back(Clone);
6171 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6172 E = ClonedDVs.end(); I != E; ++I)
6173 AddDbgValue(*I, ToNode, false);
6176 //===----------------------------------------------------------------------===//
6178 //===----------------------------------------------------------------------===//
6180 HandleSDNode::~HandleSDNode() {
6184 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6185 DebugLoc DL, const GlobalValue *GA,
6186 EVT VT, int64_t o, unsigned char TF)
6187 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6191 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6192 SDValue X, unsigned SrcAS,
6194 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6195 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6197 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6198 EVT memvt, MachineMemOperand *mmo)
6199 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6200 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6201 MMO->isNonTemporal(), MMO->isInvariant());
6202 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6203 assert(isNonTemporal() == MMO->isNonTemporal() &&
6204 "Non-temporal encoding error!");
6205 // We check here that the size of the memory operand fits within the size of
6206 // the MMO. This is because the MMO might indicate only a possible address
6207 // range instead of specifying the affected memory addresses precisely.
6208 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6211 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6212 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6213 : SDNode(Opc, Order, dl, VTs, Ops),
6214 MemoryVT(memvt), MMO(mmo) {
6215 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6216 MMO->isNonTemporal(), MMO->isInvariant());
6217 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6218 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6221 /// Profile - Gather unique data for the node.
6223 void SDNode::Profile(FoldingSetNodeID &ID) const {
6224 AddNodeIDNode(ID, this);
6229 std::vector<EVT> VTs;
6232 VTs.reserve(MVT::LAST_VALUETYPE);
6233 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6234 VTs.push_back(MVT((MVT::SimpleValueType)i));
6239 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6240 static ManagedStatic<EVTArray> SimpleVTArray;
6241 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6243 /// getValueTypeList - Return a pointer to the specified value type.
6245 const EVT *SDNode::getValueTypeList(EVT VT) {
6246 if (VT.isExtended()) {
6247 sys::SmartScopedLock<true> Lock(*VTMutex);
6248 return &(*EVTs->insert(VT).first);
6250 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6251 "Value type out of range!");
6252 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6256 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6257 /// indicated value. This method ignores uses of other values defined by this
6259 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6260 assert(Value < getNumValues() && "Bad value!");
6262 // TODO: Only iterate over uses of a given value of the node
6263 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6264 if (UI.getUse().getResNo() == Value) {
6271 // Found exactly the right number of uses?
6276 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6277 /// value. This method ignores uses of other values defined by this operation.
6278 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6279 assert(Value < getNumValues() && "Bad value!");
6281 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6282 if (UI.getUse().getResNo() == Value)
6289 /// isOnlyUserOf - Return true if this node is the only use of N.
6291 bool SDNode::isOnlyUserOf(SDNode *N) const {
6293 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6304 /// isOperand - Return true if this node is an operand of N.
6306 bool SDValue::isOperandOf(SDNode *N) const {
6307 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6308 if (*this == N->getOperand(i))
6313 bool SDNode::isOperandOf(SDNode *N) const {
6314 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6315 if (this == N->OperandList[i].getNode())
6320 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6321 /// be a chain) reaches the specified operand without crossing any
6322 /// side-effecting instructions on any chain path. In practice, this looks
6323 /// through token factors and non-volatile loads. In order to remain efficient,
6324 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6325 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6326 unsigned Depth) const {
6327 if (*this == Dest) return true;
6329 // Don't search too deeply, we just want to be able to see through
6330 // TokenFactor's etc.
6331 if (Depth == 0) return false;
6333 // If this is a token factor, all inputs to the TF happen in parallel. If any
6334 // of the operands of the TF does not reach dest, then we cannot do the xform.
6335 if (getOpcode() == ISD::TokenFactor) {
6336 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6337 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6342 // Loads don't have side effects, look through them.
6343 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6344 if (!Ld->isVolatile())
6345 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6350 /// hasPredecessor - Return true if N is a predecessor of this node.
6351 /// N is either an operand of this node, or can be reached by recursively
6352 /// traversing up the operands.
6353 /// NOTE: This is an expensive method. Use it carefully.
6354 bool SDNode::hasPredecessor(const SDNode *N) const {
6355 SmallPtrSet<const SDNode *, 32> Visited;
6356 SmallVector<const SDNode *, 16> Worklist;
6357 return hasPredecessorHelper(N, Visited, Worklist);
6361 SDNode::hasPredecessorHelper(const SDNode *N,
6362 SmallPtrSetImpl<const SDNode *> &Visited,
6363 SmallVectorImpl<const SDNode *> &Worklist) const {
6364 if (Visited.empty()) {
6365 Worklist.push_back(this);
6367 // Take a look in the visited set. If we've already encountered this node
6368 // we needn't search further.
6369 if (Visited.count(N))
6373 // Haven't visited N yet. Continue the search.
6374 while (!Worklist.empty()) {
6375 const SDNode *M = Worklist.pop_back_val();
6376 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6377 SDNode *Op = M->getOperand(i).getNode();
6378 if (Visited.insert(Op))
6379 Worklist.push_back(Op);
6388 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6389 assert(Num < NumOperands && "Invalid child # of SDNode!");
6390 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6393 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6394 assert(N->getNumValues() == 1 &&
6395 "Can't unroll a vector with multiple results!");
6397 EVT VT = N->getValueType(0);
6398 unsigned NE = VT.getVectorNumElements();
6399 EVT EltVT = VT.getVectorElementType();
6402 SmallVector<SDValue, 8> Scalars;
6403 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6405 // If ResNE is 0, fully unroll the vector op.
6408 else if (NE > ResNE)
6412 for (i= 0; i != NE; ++i) {
6413 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6414 SDValue Operand = N->getOperand(j);
6415 EVT OperandVT = Operand.getValueType();
6416 if (OperandVT.isVector()) {
6417 // A vector operand; extract a single element.
6418 EVT OperandEltVT = OperandVT.getVectorElementType();
6419 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6422 getConstant(i, TLI->getVectorIdxTy()));
6424 // A scalar operand; just use it as is.
6425 Operands[j] = Operand;
6429 switch (N->getOpcode()) {
6431 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6434 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6441 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6442 getShiftAmountOperand(Operands[0].getValueType(),
6445 case ISD::SIGN_EXTEND_INREG:
6446 case ISD::FP_ROUND_INREG: {
6447 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6448 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6450 getValueType(ExtVT)));
6455 for (; i < ResNE; ++i)
6456 Scalars.push_back(getUNDEF(EltVT));
6458 return getNode(ISD::BUILD_VECTOR, dl,
6459 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6463 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6464 /// location that is 'Dist' units away from the location that the 'Base' load
6465 /// is loading from.
6466 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6467 unsigned Bytes, int Dist) const {
6468 if (LD->getChain() != Base->getChain())
6470 EVT VT = LD->getValueType(0);
6471 if (VT.getSizeInBits() / 8 != Bytes)
6474 SDValue Loc = LD->getOperand(1);
6475 SDValue BaseLoc = Base->getOperand(1);
6476 if (Loc.getOpcode() == ISD::FrameIndex) {
6477 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6479 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6480 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6481 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6482 int FS = MFI->getObjectSize(FI);
6483 int BFS = MFI->getObjectSize(BFI);
6484 if (FS != BFS || FS != (int)Bytes) return false;
6485 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6489 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6490 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6493 const GlobalValue *GV1 = nullptr;
6494 const GlobalValue *GV2 = nullptr;
6495 int64_t Offset1 = 0;
6496 int64_t Offset2 = 0;
6497 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6498 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6499 if (isGA1 && isGA2 && GV1 == GV2)
6500 return Offset1 == (Offset2 + Dist*Bytes);
6505 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6506 /// it cannot be inferred.
6507 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6508 // If this is a GlobalAddress + cst, return the alignment.
6509 const GlobalValue *GV;
6510 int64_t GVOffset = 0;
6511 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6512 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6513 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6514 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6515 TLI->getDataLayout());
6516 unsigned AlignBits = KnownZero.countTrailingOnes();
6517 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6519 return MinAlign(Align, GVOffset);
6522 // If this is a direct reference to a stack slot, use information about the
6523 // stack slot's alignment.
6524 int FrameIdx = 1 << 31;
6525 int64_t FrameOffset = 0;
6526 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6527 FrameIdx = FI->getIndex();
6528 } else if (isBaseWithConstantOffset(Ptr) &&
6529 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6531 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6532 FrameOffset = Ptr.getConstantOperandVal(1);
6535 if (FrameIdx != (1 << 31)) {
6536 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6537 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6545 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6546 /// which is split (or expanded) into two not necessarily identical pieces.
6547 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6548 // Currently all types are split in half.
6550 if (!VT.isVector()) {
6551 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6553 unsigned NumElements = VT.getVectorNumElements();
6554 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6555 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6558 return std::make_pair(LoVT, HiVT);
6561 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6563 std::pair<SDValue, SDValue>
6564 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6566 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6567 N.getValueType().getVectorNumElements() &&
6568 "More vector elements requested than available!");
6570 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6571 getConstant(0, TLI->getVectorIdxTy()));
6572 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6573 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6574 return std::make_pair(Lo, Hi);
6577 void SelectionDAG::ExtractVectorElements(SDValue Op,
6578 SmallVectorImpl<SDValue> &Args,
6579 unsigned Start, unsigned Count) {
6580 EVT VT = Op.getValueType();
6582 Count = VT.getVectorNumElements();
6584 EVT EltVT = VT.getVectorElementType();
6585 EVT IdxTy = TLI->getVectorIdxTy();
6587 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6588 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6589 Op, getConstant(i, IdxTy)));
6593 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6594 unsigned GlobalAddressSDNode::getAddressSpace() const {
6595 return getGlobal()->getType()->getAddressSpace();
6599 Type *ConstantPoolSDNode::getType() const {
6600 if (isMachineConstantPoolEntry())
6601 return Val.MachineCPVal->getType();
6602 return Val.ConstVal->getType();
6605 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6607 unsigned &SplatBitSize,
6609 unsigned MinSplatBits,
6610 bool isBigEndian) const {
6611 EVT VT = getValueType(0);
6612 assert(VT.isVector() && "Expected a vector type");
6613 unsigned sz = VT.getSizeInBits();
6614 if (MinSplatBits > sz)
6617 SplatValue = APInt(sz, 0);
6618 SplatUndef = APInt(sz, 0);
6620 // Get the bits. Bits with undefined values (when the corresponding element
6621 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6622 // in SplatValue. If any of the values are not constant, give up and return
6624 unsigned int nOps = getNumOperands();
6625 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6626 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6628 for (unsigned j = 0; j < nOps; ++j) {
6629 unsigned i = isBigEndian ? nOps-1-j : j;
6630 SDValue OpVal = getOperand(i);
6631 unsigned BitPos = j * EltBitSize;
6633 if (OpVal.getOpcode() == ISD::UNDEF)
6634 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6635 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6636 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6637 zextOrTrunc(sz) << BitPos;
6638 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6639 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6644 // The build_vector is all constants or undefs. Find the smallest element
6645 // size that splats the vector.
6647 HasAnyUndefs = (SplatUndef != 0);
6650 unsigned HalfSize = sz / 2;
6651 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6652 APInt LowValue = SplatValue.trunc(HalfSize);
6653 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6654 APInt LowUndef = SplatUndef.trunc(HalfSize);
6656 // If the two halves do not match (ignoring undef bits), stop here.
6657 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6658 MinSplatBits > HalfSize)
6661 SplatValue = HighValue | LowValue;
6662 SplatUndef = HighUndef & LowUndef;
6671 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6672 if (UndefElements) {
6673 UndefElements->clear();
6674 UndefElements->resize(getNumOperands());
6677 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6678 SDValue Op = getOperand(i);
6679 if (Op.getOpcode() == ISD::UNDEF) {
6681 (*UndefElements)[i] = true;
6682 } else if (!Splatted) {
6684 } else if (Splatted != Op) {
6690 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6691 "Can only have a splat without a constant for all undefs.");
6692 return getOperand(0);
6699 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6700 return dyn_cast_or_null<ConstantSDNode>(
6701 getSplatValue(UndefElements).getNode());
6705 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6706 return dyn_cast_or_null<ConstantFPSDNode>(
6707 getSplatValue(UndefElements).getNode());
6710 bool BuildVectorSDNode::isConstant() const {
6711 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6712 unsigned Opc = getOperand(i).getOpcode();
6713 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6719 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6720 // Find the first non-undef value in the shuffle mask.
6722 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6725 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6727 // Make sure all remaining elements are either undef or the same as the first
6729 for (int Idx = Mask[i]; i != e; ++i)
6730 if (Mask[i] >= 0 && Mask[i] != Idx)
6736 static void checkForCyclesHelper(const SDNode *N,
6737 SmallPtrSetImpl<const SDNode*> &Visited,
6738 SmallPtrSetImpl<const SDNode*> &Checked,
6739 const llvm::SelectionDAG *DAG) {
6740 // If this node has already been checked, don't check it again.
6741 if (Checked.count(N))
6744 // If a node has already been visited on this depth-first walk, reject it as
6746 if (!Visited.insert(N)) {
6747 errs() << "Detected cycle in SelectionDAG\n";
6748 dbgs() << "Offending node:\n";
6749 N->dumprFull(DAG); dbgs() << "\n";
6753 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6754 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6761 void llvm::checkForCycles(const llvm::SDNode *N,
6762 const llvm::SelectionDAG *DAG,
6770 assert(N && "Checking nonexistent SDNode");
6771 SmallPtrSet<const SDNode*, 32> visited;
6772 SmallPtrSet<const SDNode*, 32> checked;
6773 checkForCyclesHelper(N, visited, checked, DAG);
6778 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6779 checkForCycles(DAG->getRoot().getNode(), DAG, force);