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 TM.getSubtargetImpl()
903 ->getTargetLowering()
905 ->getABITypeAlignment(Ty);
908 // EntryNode could meaningfully have debug info if we can find it...
909 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
910 : TM(tm), TSI(*tm.getSubtargetImpl()->getSelectionDAGInfo()), TLI(nullptr),
912 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
913 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
914 UpdateListeners(nullptr) {
915 AllNodes.push_back(&EntryNode);
916 DbgInfo = new SDDbgInfo();
919 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
922 Context = &mf.getFunction()->getContext();
925 SelectionDAG::~SelectionDAG() {
926 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
931 void SelectionDAG::allnodes_clear() {
932 assert(&*AllNodes.begin() == &EntryNode);
933 AllNodes.remove(AllNodes.begin());
934 while (!AllNodes.empty())
935 DeallocateNode(AllNodes.begin());
938 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
939 SDVTList VTs, SDValue N1,
940 SDValue N2, bool nuw, bool nsw,
942 if (isBinOpWithFlags(Opcode)) {
943 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
944 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
945 FN->setHasNoUnsignedWrap(nuw);
946 FN->setHasNoSignedWrap(nsw);
947 FN->setIsExact(exact);
952 BinarySDNode *N = new (NodeAllocator)
953 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
957 void SelectionDAG::clear() {
959 OperandAllocator.Reset();
962 ExtendedValueTypeNodes.clear();
963 ExternalSymbols.clear();
964 TargetExternalSymbols.clear();
965 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
966 static_cast<CondCodeSDNode*>(nullptr));
967 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
968 static_cast<SDNode*>(nullptr));
970 EntryNode.UseList = nullptr;
971 AllNodes.push_back(&EntryNode);
972 Root = getEntryNode();
976 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
977 return VT.bitsGT(Op.getValueType()) ?
978 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
979 getNode(ISD::TRUNCATE, DL, VT, Op);
982 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
983 return VT.bitsGT(Op.getValueType()) ?
984 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
985 getNode(ISD::TRUNCATE, DL, VT, Op);
988 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
989 return VT.bitsGT(Op.getValueType()) ?
990 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
991 getNode(ISD::TRUNCATE, DL, VT, Op);
994 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
996 if (VT.bitsLE(Op.getValueType()))
997 return getNode(ISD::TRUNCATE, SL, VT, Op);
999 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1000 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1003 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1004 assert(!VT.isVector() &&
1005 "getZeroExtendInReg should use the vector element type instead of "
1006 "the vector type!");
1007 if (Op.getValueType() == VT) return Op;
1008 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1009 APInt Imm = APInt::getLowBitsSet(BitWidth,
1010 VT.getSizeInBits());
1011 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1012 getConstant(Imm, Op.getValueType()));
1015 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1016 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1017 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1018 "The sizes of the input and result must match in order to perform the "
1019 "extend in-register.");
1020 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1021 "The destination vector type must have fewer lanes than the input.");
1022 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1025 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1026 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1027 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1028 "The sizes of the input and result must match in order to perform the "
1029 "extend in-register.");
1030 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1031 "The destination vector type must have fewer lanes than the input.");
1032 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1035 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1036 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1037 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1038 "The sizes of the input and result must match in order to perform the "
1039 "extend in-register.");
1040 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1041 "The destination vector type must have fewer lanes than the input.");
1042 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1045 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1047 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1048 EVT EltVT = VT.getScalarType();
1050 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1051 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1054 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1055 EVT EltVT = VT.getScalarType();
1057 switch (TLI->getBooleanContents(VT)) {
1058 case TargetLowering::ZeroOrOneBooleanContent:
1059 case TargetLowering::UndefinedBooleanContent:
1060 TrueValue = getConstant(1, VT);
1062 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1063 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1067 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1070 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1071 EVT EltVT = VT.getScalarType();
1072 assert((EltVT.getSizeInBits() >= 64 ||
1073 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1074 "getConstant with a uint64_t value that doesn't fit in the type!");
1075 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1078 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1080 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1083 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1085 assert(VT.isInteger() && "Cannot create FP integer constant!");
1087 EVT EltVT = VT.getScalarType();
1088 const ConstantInt *Elt = &Val;
1090 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1092 // In some cases the vector type is legal but the element type is illegal and
1093 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1094 // inserted value (the type does not need to match the vector element type).
1095 // Any extra bits introduced will be truncated away.
1096 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1097 TargetLowering::TypePromoteInteger) {
1098 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1099 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1100 Elt = ConstantInt::get(*getContext(), NewVal);
1102 // In other cases the element type is illegal and needs to be expanded, for
1103 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1104 // the value into n parts and use a vector type with n-times the elements.
1105 // Then bitcast to the type requested.
1106 // Legalizing constants too early makes the DAGCombiner's job harder so we
1107 // only legalize if the DAG tells us we must produce legal types.
1108 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1109 TLI->getTypeAction(*getContext(), EltVT) ==
1110 TargetLowering::TypeExpandInteger) {
1111 APInt NewVal = Elt->getValue();
1112 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1113 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1114 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1115 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1117 // Check the temporary vector is the correct size. If this fails then
1118 // getTypeToTransformTo() probably returned a type whose size (in bits)
1119 // isn't a power-of-2 factor of the requested type size.
1120 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1122 SmallVector<SDValue, 2> EltParts;
1123 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1124 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1125 .trunc(ViaEltSizeInBits),
1126 ViaEltVT, isT, isO));
1129 // EltParts is currently in little endian order. If we actually want
1130 // big-endian order then reverse it now.
1131 if (TLI->isBigEndian())
1132 std::reverse(EltParts.begin(), EltParts.end());
1134 // The elements must be reversed when the element order is different
1135 // to the endianness of the elements (because the BITCAST is itself a
1136 // vector shuffle in this situation). However, we do not need any code to
1137 // perform this reversal because getConstant() is producing a vector
1139 // This situation occurs in MIPS MSA.
1141 SmallVector<SDValue, 8> Ops;
1142 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1143 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1145 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1146 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1151 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1152 "APInt size does not match type size!");
1153 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1154 FoldingSetNodeID ID;
1155 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1159 SDNode *N = nullptr;
1160 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1162 return SDValue(N, 0);
1165 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1166 CSEMap.InsertNode(N, IP);
1170 SDValue Result(N, 0);
1171 if (VT.isVector()) {
1172 SmallVector<SDValue, 8> Ops;
1173 Ops.assign(VT.getVectorNumElements(), Result);
1174 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1179 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1180 return getConstant(Val,
1181 TM.getSubtargetImpl()->getTargetLowering()->getPointerTy(),
1186 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1187 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1190 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1191 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1193 EVT EltVT = VT.getScalarType();
1195 // Do the map lookup using the actual bit pattern for the floating point
1196 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1197 // we don't have issues with SNANs.
1198 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1199 FoldingSetNodeID ID;
1200 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1203 SDNode *N = nullptr;
1204 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1206 return SDValue(N, 0);
1209 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1210 CSEMap.InsertNode(N, IP);
1214 SDValue Result(N, 0);
1215 if (VT.isVector()) {
1216 SmallVector<SDValue, 8> Ops;
1217 Ops.assign(VT.getVectorNumElements(), Result);
1218 // FIXME SDLoc info might be appropriate here
1219 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1224 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1225 EVT EltVT = VT.getScalarType();
1226 if (EltVT==MVT::f32)
1227 return getConstantFP(APFloat((float)Val), VT, isTarget);
1228 else if (EltVT==MVT::f64)
1229 return getConstantFP(APFloat(Val), VT, isTarget);
1230 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1233 APFloat apf = APFloat(Val);
1234 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1236 return getConstantFP(apf, VT, isTarget);
1238 llvm_unreachable("Unsupported type in getConstantFP");
1241 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1242 EVT VT, int64_t Offset,
1244 unsigned char TargetFlags) {
1245 assert((TargetFlags == 0 || isTargetGA) &&
1246 "Cannot set target flags on target-independent globals");
1247 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1249 // Truncate (with sign-extension) the offset value to the pointer size.
1250 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1252 Offset = SignExtend64(Offset, BitWidth);
1255 if (GV->isThreadLocal())
1256 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1258 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1260 FoldingSetNodeID ID;
1261 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1263 ID.AddInteger(Offset);
1264 ID.AddInteger(TargetFlags);
1265 ID.AddInteger(GV->getType()->getAddressSpace());
1267 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1268 return SDValue(E, 0);
1270 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1271 DL.getDebugLoc(), GV, VT,
1272 Offset, TargetFlags);
1273 CSEMap.InsertNode(N, IP);
1275 return SDValue(N, 0);
1278 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1279 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1284 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1285 return SDValue(E, 0);
1287 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1288 CSEMap.InsertNode(N, IP);
1290 return SDValue(N, 0);
1293 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1294 unsigned char TargetFlags) {
1295 assert((TargetFlags == 0 || isTarget) &&
1296 "Cannot set target flags on target-independent jump tables");
1297 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1298 FoldingSetNodeID ID;
1299 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1301 ID.AddInteger(TargetFlags);
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1308 CSEMap.InsertNode(N, IP);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1314 unsigned Alignment, int Offset,
1316 unsigned char TargetFlags) {
1317 assert((TargetFlags == 0 || isTarget) &&
1318 "Cannot set target flags on target-independent globals");
1320 Alignment = TM.getSubtargetImpl()
1321 ->getTargetLowering()
1323 ->getPrefTypeAlignment(C->getType());
1324 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1325 FoldingSetNodeID ID;
1326 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1327 ID.AddInteger(Alignment);
1328 ID.AddInteger(Offset);
1330 ID.AddInteger(TargetFlags);
1332 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1333 return SDValue(E, 0);
1335 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1336 Alignment, TargetFlags);
1337 CSEMap.InsertNode(N, IP);
1339 return SDValue(N, 0);
1343 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1344 unsigned Alignment, int Offset,
1346 unsigned char TargetFlags) {
1347 assert((TargetFlags == 0 || isTarget) &&
1348 "Cannot set target flags on target-independent globals");
1350 Alignment = TM.getSubtargetImpl()
1351 ->getTargetLowering()
1353 ->getPrefTypeAlignment(C->getType());
1354 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1355 FoldingSetNodeID ID;
1356 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1357 ID.AddInteger(Alignment);
1358 ID.AddInteger(Offset);
1359 C->addSelectionDAGCSEId(ID);
1360 ID.AddInteger(TargetFlags);
1362 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1363 return SDValue(E, 0);
1365 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1366 Alignment, TargetFlags);
1367 CSEMap.InsertNode(N, IP);
1369 return SDValue(N, 0);
1372 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1373 unsigned char TargetFlags) {
1374 FoldingSetNodeID ID;
1375 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1376 ID.AddInteger(Index);
1377 ID.AddInteger(Offset);
1378 ID.AddInteger(TargetFlags);
1380 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1381 return SDValue(E, 0);
1383 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1385 CSEMap.InsertNode(N, IP);
1387 return SDValue(N, 0);
1390 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1391 FoldingSetNodeID ID;
1392 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1396 return SDValue(E, 0);
1398 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1399 CSEMap.InsertNode(N, IP);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getValueType(EVT VT) {
1405 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1406 ValueTypeNodes.size())
1407 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1409 SDNode *&N = VT.isExtended() ?
1410 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1412 if (N) return SDValue(N, 0);
1413 N = new (NodeAllocator) VTSDNode(VT);
1415 return SDValue(N, 0);
1418 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1419 SDNode *&N = ExternalSymbols[Sym];
1420 if (N) return SDValue(N, 0);
1421 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1423 return SDValue(N, 0);
1426 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1427 unsigned char TargetFlags) {
1429 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1431 if (N) return SDValue(N, 0);
1432 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1434 return SDValue(N, 0);
1437 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1438 if ((unsigned)Cond >= CondCodeNodes.size())
1439 CondCodeNodes.resize(Cond+1);
1441 if (!CondCodeNodes[Cond]) {
1442 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1443 CondCodeNodes[Cond] = N;
1447 return SDValue(CondCodeNodes[Cond], 0);
1450 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1451 // the shuffle mask M that point at N1 to point at N2, and indices that point
1452 // N2 to point at N1.
1453 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1455 int NElts = M.size();
1456 for (int i = 0; i != NElts; ++i) {
1464 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1465 SDValue N2, const int *Mask) {
1466 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1467 "Invalid VECTOR_SHUFFLE");
1469 // Canonicalize shuffle undef, undef -> undef
1470 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1471 return getUNDEF(VT);
1473 // Validate that all indices in Mask are within the range of the elements
1474 // input to the shuffle.
1475 unsigned NElts = VT.getVectorNumElements();
1476 SmallVector<int, 8> MaskVec;
1477 for (unsigned i = 0; i != NElts; ++i) {
1478 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1479 MaskVec.push_back(Mask[i]);
1482 // Canonicalize shuffle v, v -> v, undef
1485 for (unsigned i = 0; i != NElts; ++i)
1486 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1489 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1490 if (N1.getOpcode() == ISD::UNDEF)
1491 commuteShuffle(N1, N2, MaskVec);
1493 // Canonicalize all index into lhs, -> shuffle lhs, undef
1494 // Canonicalize all index into rhs, -> shuffle rhs, undef
1495 bool AllLHS = true, AllRHS = true;
1496 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1497 for (unsigned i = 0; i != NElts; ++i) {
1498 if (MaskVec[i] >= (int)NElts) {
1503 } else if (MaskVec[i] >= 0) {
1507 if (AllLHS && AllRHS)
1508 return getUNDEF(VT);
1509 if (AllLHS && !N2Undef)
1513 commuteShuffle(N1, N2, MaskVec);
1515 // Reset our undef status after accounting for the mask.
1516 N2Undef = N2.getOpcode() == ISD::UNDEF;
1517 // Re-check whether both sides ended up undef.
1518 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1519 return getUNDEF(VT);
1521 // If Identity shuffle return that node.
1522 bool Identity = true;
1523 for (unsigned i = 0; i != NElts; ++i) {
1524 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1526 if (Identity && NElts)
1529 // Shuffling a constant splat doesn't change the result.
1533 // Look through any bitcasts. We check that these don't change the number
1534 // (and size) of elements and just changes their types.
1535 while (V.getOpcode() == ISD::BITCAST)
1536 V = V->getOperand(0);
1538 // A splat should always show up as a build vector node.
1539 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1540 BitVector UndefElements;
1541 SDValue Splat = BV->getSplatValue(&UndefElements);
1542 // If this is a splat of an undef, shuffling it is also undef.
1543 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1544 return getUNDEF(VT);
1546 // We only have a splat which can skip shuffles if there is a splatted
1547 // value and no undef lanes rearranged by the shuffle.
1548 if (Splat && UndefElements.none()) {
1549 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1550 // number of elements match or the value splatted is a zero constant.
1551 if (V.getValueType().getVectorNumElements() ==
1552 VT.getVectorNumElements())
1554 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1555 if (C->isNullValue())
1561 FoldingSetNodeID ID;
1562 SDValue Ops[2] = { N1, N2 };
1563 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1564 for (unsigned i = 0; i != NElts; ++i)
1565 ID.AddInteger(MaskVec[i]);
1568 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1569 return SDValue(E, 0);
1571 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1572 // SDNode doesn't have access to it. This memory will be "leaked" when
1573 // the node is deallocated, but recovered when the NodeAllocator is released.
1574 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1575 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1577 ShuffleVectorSDNode *N =
1578 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1579 dl.getDebugLoc(), N1, N2,
1581 CSEMap.InsertNode(N, IP);
1583 return SDValue(N, 0);
1586 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1587 MVT VT = SV.getSimpleValueType(0);
1588 unsigned NumElems = VT.getVectorNumElements();
1589 SmallVector<int, 8> MaskVec;
1591 for (unsigned i = 0; i != NumElems; ++i) {
1592 int Idx = SV.getMaskElt(i);
1594 if (Idx < (int)NumElems)
1599 MaskVec.push_back(Idx);
1602 SDValue Op0 = SV.getOperand(0);
1603 SDValue Op1 = SV.getOperand(1);
1604 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1607 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1608 SDValue Val, SDValue DTy,
1609 SDValue STy, SDValue Rnd, SDValue Sat,
1610 ISD::CvtCode Code) {
1611 // If the src and dest types are the same and the conversion is between
1612 // integer types of the same sign or two floats, no conversion is necessary.
1614 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1617 FoldingSetNodeID ID;
1618 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1619 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1621 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1622 return SDValue(E, 0);
1624 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1627 CSEMap.InsertNode(N, IP);
1629 return SDValue(N, 0);
1632 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1633 FoldingSetNodeID ID;
1634 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1635 ID.AddInteger(RegNo);
1637 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1638 return SDValue(E, 0);
1640 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1641 CSEMap.InsertNode(N, IP);
1643 return SDValue(N, 0);
1646 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1647 FoldingSetNodeID ID;
1648 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1649 ID.AddPointer(RegMask);
1651 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1652 return SDValue(E, 0);
1654 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1655 CSEMap.InsertNode(N, IP);
1657 return SDValue(N, 0);
1660 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1661 FoldingSetNodeID ID;
1662 SDValue Ops[] = { Root };
1663 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1664 ID.AddPointer(Label);
1666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1667 return SDValue(E, 0);
1669 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1670 dl.getDebugLoc(), Root, Label);
1671 CSEMap.InsertNode(N, IP);
1673 return SDValue(N, 0);
1677 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1680 unsigned char TargetFlags) {
1681 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1683 FoldingSetNodeID ID;
1684 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1686 ID.AddInteger(Offset);
1687 ID.AddInteger(TargetFlags);
1689 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1690 return SDValue(E, 0);
1692 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1694 CSEMap.InsertNode(N, IP);
1696 return SDValue(N, 0);
1699 SDValue SelectionDAG::getSrcValue(const Value *V) {
1700 assert((!V || V->getType()->isPointerTy()) &&
1701 "SrcValue is not a pointer?");
1703 FoldingSetNodeID ID;
1704 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1708 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1709 return SDValue(E, 0);
1711 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1712 CSEMap.InsertNode(N, IP);
1714 return SDValue(N, 0);
1717 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1718 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1719 FoldingSetNodeID ID;
1720 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1724 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1725 return SDValue(E, 0);
1727 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1728 CSEMap.InsertNode(N, IP);
1730 return SDValue(N, 0);
1733 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1734 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1735 unsigned SrcAS, unsigned DestAS) {
1736 SDValue Ops[] = {Ptr};
1737 FoldingSetNodeID ID;
1738 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1739 ID.AddInteger(SrcAS);
1740 ID.AddInteger(DestAS);
1743 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1744 return SDValue(E, 0);
1746 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1748 VT, Ptr, SrcAS, DestAS);
1749 CSEMap.InsertNode(N, IP);
1751 return SDValue(N, 0);
1754 /// getShiftAmountOperand - Return the specified value casted to
1755 /// the target's desired shift amount type.
1756 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1757 EVT OpTy = Op.getValueType();
1759 TM.getSubtargetImpl()->getTargetLowering()->getShiftAmountTy(LHSTy);
1760 if (OpTy == ShTy || OpTy.isVector()) return Op;
1762 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1763 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1766 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1767 /// specified value type.
1768 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1769 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1770 unsigned ByteSize = VT.getStoreSize();
1771 Type *Ty = VT.getTypeForEVT(*getContext());
1772 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1773 unsigned StackAlign =
1774 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1776 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1777 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1780 /// CreateStackTemporary - Create a stack temporary suitable for holding
1781 /// either of the specified value types.
1782 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1783 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1784 VT2.getStoreSizeInBits())/8;
1785 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1786 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1787 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1788 const DataLayout *TD = TLI->getDataLayout();
1789 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1790 TD->getPrefTypeAlignment(Ty2));
1792 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1793 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1794 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1797 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1798 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1799 // These setcc operations always fold.
1803 case ISD::SETFALSE2: return getConstant(0, VT);
1805 case ISD::SETTRUE2: {
1806 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1807 TargetLowering::BooleanContent Cnt =
1808 TLI->getBooleanContents(N1->getValueType(0));
1810 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1823 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1827 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1828 const APInt &C2 = N2C->getAPIntValue();
1829 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1830 const APInt &C1 = N1C->getAPIntValue();
1833 default: llvm_unreachable("Unknown integer setcc!");
1834 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1835 case ISD::SETNE: return getConstant(C1 != C2, VT);
1836 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1837 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1838 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1839 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1840 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1841 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1842 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1843 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1847 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1848 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1849 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1852 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1853 return getUNDEF(VT);
1855 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1856 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1857 return getUNDEF(VT);
1859 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1860 R==APFloat::cmpLessThan, VT);
1861 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1862 return getUNDEF(VT);
1864 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1865 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1866 return getUNDEF(VT);
1868 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1869 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1870 return getUNDEF(VT);
1872 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1873 R==APFloat::cmpEqual, VT);
1874 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1875 return getUNDEF(VT);
1877 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1878 R==APFloat::cmpEqual, VT);
1879 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1880 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1881 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1882 R==APFloat::cmpEqual, VT);
1883 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1884 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1885 R==APFloat::cmpLessThan, VT);
1886 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1887 R==APFloat::cmpUnordered, VT);
1888 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1889 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1892 // Ensure that the constant occurs on the RHS.
1893 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1894 MVT CompVT = N1.getValueType().getSimpleVT();
1895 if (!TM.getSubtargetImpl()->getTargetLowering()->isCondCodeLegal(
1896 SwappedCond, CompVT))
1899 return getSetCC(dl, VT, N2, N1, SwappedCond);
1903 // Could not fold it.
1907 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1908 /// use this predicate to simplify operations downstream.
1909 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1910 // This predicate is not safe for vector operations.
1911 if (Op.getValueType().isVector())
1914 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1915 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1918 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1919 /// this predicate to simplify operations downstream. Mask is known to be zero
1920 /// for bits that V cannot have.
1921 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1922 unsigned Depth) const {
1923 APInt KnownZero, KnownOne;
1924 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1925 return (KnownZero & Mask) == Mask;
1928 /// Determine which bits of Op are known to be either zero or one and return
1929 /// them in the KnownZero/KnownOne bitsets.
1930 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1931 APInt &KnownOne, unsigned Depth) const {
1932 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
1933 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1935 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1937 return; // Limit search depth.
1939 APInt KnownZero2, KnownOne2;
1941 switch (Op.getOpcode()) {
1943 // We know all of the bits for a constant!
1944 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1945 KnownZero = ~KnownOne;
1948 // If either the LHS or the RHS are Zero, the result is zero.
1949 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1950 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1952 // Output known-1 bits are only known if set in both the LHS & RHS.
1953 KnownOne &= KnownOne2;
1954 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1955 KnownZero |= KnownZero2;
1958 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1959 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1961 // Output known-0 bits are only known if clear in both the LHS & RHS.
1962 KnownZero &= KnownZero2;
1963 // Output known-1 are known to be set if set in either the LHS | RHS.
1964 KnownOne |= KnownOne2;
1967 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1968 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1970 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1971 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1972 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1973 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1974 KnownZero = KnownZeroOut;
1978 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1979 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1981 // If low bits are zero in either operand, output low known-0 bits.
1982 // Also compute a conserative estimate for high known-0 bits.
1983 // More trickiness is possible, but this is sufficient for the
1984 // interesting case of alignment computation.
1985 KnownOne.clearAllBits();
1986 unsigned TrailZ = KnownZero.countTrailingOnes() +
1987 KnownZero2.countTrailingOnes();
1988 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1989 KnownZero2.countLeadingOnes(),
1990 BitWidth) - BitWidth;
1992 TrailZ = std::min(TrailZ, BitWidth);
1993 LeadZ = std::min(LeadZ, BitWidth);
1994 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1995 APInt::getHighBitsSet(BitWidth, LeadZ);
1999 // For the purposes of computing leading zeros we can conservatively
2000 // treat a udiv as a logical right shift by the power of 2 known to
2001 // be less than the denominator.
2002 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2003 unsigned LeadZ = KnownZero2.countLeadingOnes();
2005 KnownOne2.clearAllBits();
2006 KnownZero2.clearAllBits();
2007 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2008 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2009 if (RHSUnknownLeadingOnes != BitWidth)
2010 LeadZ = std::min(BitWidth,
2011 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2013 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2017 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2018 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2020 // Only known if known in both the LHS and RHS.
2021 KnownOne &= KnownOne2;
2022 KnownZero &= KnownZero2;
2024 case ISD::SELECT_CC:
2025 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2026 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2028 // Only known if known in both the LHS and RHS.
2029 KnownOne &= KnownOne2;
2030 KnownZero &= KnownZero2;
2038 if (Op.getResNo() != 1)
2040 // The boolean result conforms to getBooleanContents.
2041 // If we know the result of a setcc has the top bits zero, use this info.
2042 // We know that we have an integer-based boolean since these operations
2043 // are only available for integer.
2044 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2045 TargetLowering::ZeroOrOneBooleanContent &&
2047 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2050 // If we know the result of a setcc has the top bits zero, use this info.
2051 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2052 TargetLowering::ZeroOrOneBooleanContent &&
2054 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2057 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2058 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2059 unsigned ShAmt = SA->getZExtValue();
2061 // If the shift count is an invalid immediate, don't do anything.
2062 if (ShAmt >= BitWidth)
2065 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2066 KnownZero <<= ShAmt;
2068 // low bits known zero.
2069 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2073 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2074 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2075 unsigned ShAmt = SA->getZExtValue();
2077 // If the shift count is an invalid immediate, don't do anything.
2078 if (ShAmt >= BitWidth)
2081 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2082 KnownZero = KnownZero.lshr(ShAmt);
2083 KnownOne = KnownOne.lshr(ShAmt);
2085 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2086 KnownZero |= HighBits; // High bits known zero.
2090 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2091 unsigned ShAmt = SA->getZExtValue();
2093 // If the shift count is an invalid immediate, don't do anything.
2094 if (ShAmt >= BitWidth)
2097 // If any of the demanded bits are produced by the sign extension, we also
2098 // demand the input sign bit.
2099 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2101 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2102 KnownZero = KnownZero.lshr(ShAmt);
2103 KnownOne = KnownOne.lshr(ShAmt);
2105 // Handle the sign bits.
2106 APInt SignBit = APInt::getSignBit(BitWidth);
2107 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2109 if (KnownZero.intersects(SignBit)) {
2110 KnownZero |= HighBits; // New bits are known zero.
2111 } else if (KnownOne.intersects(SignBit)) {
2112 KnownOne |= HighBits; // New bits are known one.
2116 case ISD::SIGN_EXTEND_INREG: {
2117 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2118 unsigned EBits = EVT.getScalarType().getSizeInBits();
2120 // Sign extension. Compute the demanded bits in the result that are not
2121 // present in the input.
2122 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2124 APInt InSignBit = APInt::getSignBit(EBits);
2125 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2127 // If the sign extended bits are demanded, we know that the sign
2129 InSignBit = InSignBit.zext(BitWidth);
2130 if (NewBits.getBoolValue())
2131 InputDemandedBits |= InSignBit;
2133 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2134 KnownOne &= InputDemandedBits;
2135 KnownZero &= InputDemandedBits;
2137 // If the sign bit of the input is known set or clear, then we know the
2138 // top bits of the result.
2139 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2140 KnownZero |= NewBits;
2141 KnownOne &= ~NewBits;
2142 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2143 KnownOne |= NewBits;
2144 KnownZero &= ~NewBits;
2145 } else { // Input sign bit unknown
2146 KnownZero &= ~NewBits;
2147 KnownOne &= ~NewBits;
2152 case ISD::CTTZ_ZERO_UNDEF:
2154 case ISD::CTLZ_ZERO_UNDEF:
2156 unsigned LowBits = Log2_32(BitWidth)+1;
2157 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2158 KnownOne.clearAllBits();
2162 LoadSDNode *LD = cast<LoadSDNode>(Op);
2163 // If this is a ZEXTLoad and we are looking at the loaded value.
2164 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2165 EVT VT = LD->getMemoryVT();
2166 unsigned MemBits = VT.getScalarType().getSizeInBits();
2167 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2168 } else if (const MDNode *Ranges = LD->getRanges()) {
2169 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2173 case ISD::ZERO_EXTEND: {
2174 EVT InVT = Op.getOperand(0).getValueType();
2175 unsigned InBits = InVT.getScalarType().getSizeInBits();
2176 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2177 KnownZero = KnownZero.trunc(InBits);
2178 KnownOne = KnownOne.trunc(InBits);
2179 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2180 KnownZero = KnownZero.zext(BitWidth);
2181 KnownOne = KnownOne.zext(BitWidth);
2182 KnownZero |= NewBits;
2185 case ISD::SIGN_EXTEND: {
2186 EVT InVT = Op.getOperand(0).getValueType();
2187 unsigned InBits = InVT.getScalarType().getSizeInBits();
2188 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2190 KnownZero = KnownZero.trunc(InBits);
2191 KnownOne = KnownOne.trunc(InBits);
2192 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2194 // Note if the sign bit is known to be zero or one.
2195 bool SignBitKnownZero = KnownZero.isNegative();
2196 bool SignBitKnownOne = KnownOne.isNegative();
2198 KnownZero = KnownZero.zext(BitWidth);
2199 KnownOne = KnownOne.zext(BitWidth);
2201 // If the sign bit is known zero or one, the top bits match.
2202 if (SignBitKnownZero)
2203 KnownZero |= NewBits;
2204 else if (SignBitKnownOne)
2205 KnownOne |= NewBits;
2208 case ISD::ANY_EXTEND: {
2209 EVT InVT = Op.getOperand(0).getValueType();
2210 unsigned InBits = InVT.getScalarType().getSizeInBits();
2211 KnownZero = KnownZero.trunc(InBits);
2212 KnownOne = KnownOne.trunc(InBits);
2213 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2214 KnownZero = KnownZero.zext(BitWidth);
2215 KnownOne = KnownOne.zext(BitWidth);
2218 case ISD::TRUNCATE: {
2219 EVT InVT = Op.getOperand(0).getValueType();
2220 unsigned InBits = InVT.getScalarType().getSizeInBits();
2221 KnownZero = KnownZero.zext(InBits);
2222 KnownOne = KnownOne.zext(InBits);
2223 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2224 KnownZero = KnownZero.trunc(BitWidth);
2225 KnownOne = KnownOne.trunc(BitWidth);
2228 case ISD::AssertZext: {
2229 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2230 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2231 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2232 KnownZero |= (~InMask);
2233 KnownOne &= (~KnownZero);
2237 // All bits are zero except the low bit.
2238 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2242 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2243 // We know that the top bits of C-X are clear if X contains less bits
2244 // than C (i.e. no wrap-around can happen). For example, 20-X is
2245 // positive if we can prove that X is >= 0 and < 16.
2246 if (CLHS->getAPIntValue().isNonNegative()) {
2247 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2248 // NLZ can't be BitWidth with no sign bit
2249 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2250 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2252 // If all of the MaskV bits are known to be zero, then we know the
2253 // output top bits are zero, because we now know that the output is
2255 if ((KnownZero2 & MaskV) == MaskV) {
2256 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2257 // Top bits known zero.
2258 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2266 // Output known-0 bits are known if clear or set in both the low clear bits
2267 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2268 // low 3 bits clear.
2269 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2270 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2272 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2273 KnownZeroOut = std::min(KnownZeroOut,
2274 KnownZero2.countTrailingOnes());
2276 if (Op.getOpcode() == ISD::ADD) {
2277 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2281 // With ADDE, a carry bit may be added in, so we can only use this
2282 // information if we know (at least) that the low two bits are clear. We
2283 // then return to the caller that the low bit is unknown but that other bits
2285 if (KnownZeroOut >= 2) // ADDE
2286 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2290 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2291 const APInt &RA = Rem->getAPIntValue().abs();
2292 if (RA.isPowerOf2()) {
2293 APInt LowBits = RA - 1;
2294 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2296 // The low bits of the first operand are unchanged by the srem.
2297 KnownZero = KnownZero2 & LowBits;
2298 KnownOne = KnownOne2 & LowBits;
2300 // If the first operand is non-negative or has all low bits zero, then
2301 // the upper bits are all zero.
2302 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2303 KnownZero |= ~LowBits;
2305 // If the first operand is negative and not all low bits are zero, then
2306 // the upper bits are all one.
2307 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2308 KnownOne |= ~LowBits;
2309 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2314 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2315 const APInt &RA = Rem->getAPIntValue();
2316 if (RA.isPowerOf2()) {
2317 APInt LowBits = (RA - 1);
2318 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2320 // The upper bits are all zero, the lower ones are unchanged.
2321 KnownZero = KnownZero2 | ~LowBits;
2322 KnownOne = KnownOne2 & LowBits;
2327 // Since the result is less than or equal to either operand, any leading
2328 // zero bits in either operand must also exist in the result.
2329 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2330 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2332 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2333 KnownZero2.countLeadingOnes());
2334 KnownOne.clearAllBits();
2335 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2338 case ISD::FrameIndex:
2339 case ISD::TargetFrameIndex:
2340 if (unsigned Align = InferPtrAlignment(Op)) {
2341 // The low bits are known zero if the pointer is aligned.
2342 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2348 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2351 case ISD::INTRINSIC_WO_CHAIN:
2352 case ISD::INTRINSIC_W_CHAIN:
2353 case ISD::INTRINSIC_VOID:
2354 // Allow the target to implement this method for its nodes.
2355 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2359 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2362 /// ComputeNumSignBits - Return the number of times the sign bit of the
2363 /// register is replicated into the other bits. We know that at least 1 bit
2364 /// is always equal to the sign bit (itself), but other cases can give us
2365 /// information. For example, immediately after an "SRA X, 2", we know that
2366 /// the top 3 bits are all equal to each other, so we return 3.
2367 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2368 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
2369 EVT VT = Op.getValueType();
2370 assert(VT.isInteger() && "Invalid VT!");
2371 unsigned VTBits = VT.getScalarType().getSizeInBits();
2373 unsigned FirstAnswer = 1;
2376 return 1; // Limit search depth.
2378 switch (Op.getOpcode()) {
2380 case ISD::AssertSext:
2381 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2382 return VTBits-Tmp+1;
2383 case ISD::AssertZext:
2384 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2387 case ISD::Constant: {
2388 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2389 return Val.getNumSignBits();
2392 case ISD::SIGN_EXTEND:
2394 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2395 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2397 case ISD::SIGN_EXTEND_INREG:
2398 // Max of the input and what this extends.
2400 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2403 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2404 return std::max(Tmp, Tmp2);
2407 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2408 // SRA X, C -> adds C sign bits.
2409 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2410 Tmp += C->getZExtValue();
2411 if (Tmp > VTBits) Tmp = VTBits;
2415 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2416 // shl destroys sign bits.
2417 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2418 if (C->getZExtValue() >= VTBits || // Bad shift.
2419 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2420 return Tmp - C->getZExtValue();
2425 case ISD::XOR: // NOT is handled here.
2426 // Logical binary ops preserve the number of sign bits at the worst.
2427 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2429 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2430 FirstAnswer = std::min(Tmp, Tmp2);
2431 // We computed what we know about the sign bits as our first
2432 // answer. Now proceed to the generic code that uses
2433 // computeKnownBits, and pick whichever answer is better.
2438 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2439 if (Tmp == 1) return 1; // Early out.
2440 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2441 return std::min(Tmp, Tmp2);
2449 if (Op.getResNo() != 1)
2451 // The boolean result conforms to getBooleanContents. Fall through.
2452 // If setcc returns 0/-1, all bits are sign bits.
2453 // We know that we have an integer-based boolean since these operations
2454 // are only available for integer.
2455 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2456 TargetLowering::ZeroOrNegativeOneBooleanContent)
2460 // If setcc returns 0/-1, all bits are sign bits.
2461 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2462 TargetLowering::ZeroOrNegativeOneBooleanContent)
2467 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2468 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2470 // Handle rotate right by N like a rotate left by 32-N.
2471 if (Op.getOpcode() == ISD::ROTR)
2472 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2474 // If we aren't rotating out all of the known-in sign bits, return the
2475 // number that are left. This handles rotl(sext(x), 1) for example.
2476 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2477 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2481 // Add can have at most one carry bit. Thus we know that the output
2482 // is, at worst, one more bit than the inputs.
2483 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2484 if (Tmp == 1) return 1; // Early out.
2486 // Special case decrementing a value (ADD X, -1):
2487 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2488 if (CRHS->isAllOnesValue()) {
2489 APInt KnownZero, KnownOne;
2490 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2492 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2494 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2497 // If we are subtracting one from a positive number, there is no carry
2498 // out of the result.
2499 if (KnownZero.isNegative())
2503 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2504 if (Tmp2 == 1) return 1;
2505 return std::min(Tmp, Tmp2)-1;
2508 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2509 if (Tmp2 == 1) return 1;
2512 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2513 if (CLHS->isNullValue()) {
2514 APInt KnownZero, KnownOne;
2515 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2516 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2518 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2521 // If the input is known to be positive (the sign bit is known clear),
2522 // the output of the NEG has the same number of sign bits as the input.
2523 if (KnownZero.isNegative())
2526 // Otherwise, we treat this like a SUB.
2529 // Sub can have at most one carry bit. Thus we know that the output
2530 // is, at worst, one more bit than the inputs.
2531 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2532 if (Tmp == 1) return 1; // Early out.
2533 return std::min(Tmp, Tmp2)-1;
2535 // FIXME: it's tricky to do anything useful for this, but it is an important
2536 // case for targets like X86.
2540 // If we are looking at the loaded value of the SDNode.
2541 if (Op.getResNo() == 0) {
2542 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2543 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2544 unsigned ExtType = LD->getExtensionType();
2547 case ISD::SEXTLOAD: // '17' bits known
2548 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2549 return VTBits-Tmp+1;
2550 case ISD::ZEXTLOAD: // '16' bits known
2551 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2557 // Allow the target to implement this method for its nodes.
2558 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2559 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2560 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2561 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2562 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2563 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2566 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2567 // use this information.
2568 APInt KnownZero, KnownOne;
2569 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2572 if (KnownZero.isNegative()) { // sign bit is 0
2574 } else if (KnownOne.isNegative()) { // sign bit is 1;
2581 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2582 // the number of identical bits in the top of the input value.
2584 Mask <<= Mask.getBitWidth()-VTBits;
2585 // Return # leading zeros. We use 'min' here in case Val was zero before
2586 // shifting. We don't want to return '64' as for an i32 "0".
2587 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2590 /// isBaseWithConstantOffset - Return true if the specified operand is an
2591 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2592 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2593 /// semantics as an ADD. This handles the equivalence:
2594 /// X|Cst == X+Cst iff X&Cst = 0.
2595 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2596 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2597 !isa<ConstantSDNode>(Op.getOperand(1)))
2600 if (Op.getOpcode() == ISD::OR &&
2601 !MaskedValueIsZero(Op.getOperand(0),
2602 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2609 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2610 // If we're told that NaNs won't happen, assume they won't.
2611 if (getTarget().Options.NoNaNsFPMath)
2614 // If the value is a constant, we can obviously see if it is a NaN or not.
2615 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2616 return !C->getValueAPF().isNaN();
2618 // TODO: Recognize more cases here.
2623 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2624 // If the value is a constant, we can obviously see if it is a zero or not.
2625 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2626 return !C->isZero();
2628 // TODO: Recognize more cases here.
2629 switch (Op.getOpcode()) {
2632 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2633 return !C->isNullValue();
2640 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2641 // Check the obvious case.
2642 if (A == B) return true;
2644 // For for negative and positive zero.
2645 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2646 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2647 if (CA->isZero() && CB->isZero()) return true;
2649 // Otherwise they may not be equal.
2653 /// getNode - Gets or creates the specified node.
2655 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2656 FoldingSetNodeID ID;
2657 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2659 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2660 return SDValue(E, 0);
2662 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2663 DL.getDebugLoc(), getVTList(VT));
2664 CSEMap.InsertNode(N, IP);
2667 return SDValue(N, 0);
2670 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2671 EVT VT, SDValue Operand) {
2672 // Constant fold unary operations with an integer constant operand. Even
2673 // opaque constant will be folded, because the folding of unary operations
2674 // doesn't create new constants with different values. Nevertheless, the
2675 // opaque flag is preserved during folding to prevent future folding with
2677 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2678 const APInt &Val = C->getAPIntValue();
2681 case ISD::SIGN_EXTEND:
2682 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2683 C->isTargetOpcode(), C->isOpaque());
2684 case ISD::ANY_EXTEND:
2685 case ISD::ZERO_EXTEND:
2687 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2688 C->isTargetOpcode(), C->isOpaque());
2689 case ISD::UINT_TO_FP:
2690 case ISD::SINT_TO_FP: {
2691 APFloat apf(EVTToAPFloatSemantics(VT),
2692 APInt::getNullValue(VT.getSizeInBits()));
2693 (void)apf.convertFromAPInt(Val,
2694 Opcode==ISD::SINT_TO_FP,
2695 APFloat::rmNearestTiesToEven);
2696 return getConstantFP(apf, VT);
2699 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2700 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2701 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2702 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2705 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2708 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2711 case ISD::CTLZ_ZERO_UNDEF:
2712 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2715 case ISD::CTTZ_ZERO_UNDEF:
2716 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2721 // Constant fold unary operations with a floating point constant operand.
2722 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2723 APFloat V = C->getValueAPF(); // make copy
2727 return getConstantFP(V, VT);
2730 return getConstantFP(V, VT);
2732 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2733 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2734 return getConstantFP(V, VT);
2738 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2739 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2740 return getConstantFP(V, VT);
2744 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2745 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2746 return getConstantFP(V, VT);
2749 case ISD::FP_EXTEND: {
2751 // This can return overflow, underflow, or inexact; we don't care.
2752 // FIXME need to be more flexible about rounding mode.
2753 (void)V.convert(EVTToAPFloatSemantics(VT),
2754 APFloat::rmNearestTiesToEven, &ignored);
2755 return getConstantFP(V, VT);
2757 case ISD::FP_TO_SINT:
2758 case ISD::FP_TO_UINT: {
2761 assert(integerPartWidth >= 64);
2762 // FIXME need to be more flexible about rounding mode.
2763 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2764 Opcode==ISD::FP_TO_SINT,
2765 APFloat::rmTowardZero, &ignored);
2766 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2768 APInt api(VT.getSizeInBits(), x);
2769 return getConstant(api, VT);
2772 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2773 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2774 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2775 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2780 // Constant fold unary operations with a vector integer operand.
2781 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2782 if (BV->isConstant()) {
2785 // FIXME: Entirely reasonable to perform folding of other unary
2786 // operations here as the need arises.
2788 case ISD::UINT_TO_FP:
2789 case ISD::SINT_TO_FP: {
2790 SmallVector<SDValue, 8> Ops;
2791 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2792 SDValue OpN = BV->getOperand(i);
2793 // Let the above scalar folding handle the conversion of each
2795 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2799 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2805 unsigned OpOpcode = Operand.getNode()->getOpcode();
2807 case ISD::TokenFactor:
2808 case ISD::MERGE_VALUES:
2809 case ISD::CONCAT_VECTORS:
2810 return Operand; // Factor, merge or concat of one node? No need.
2811 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2812 case ISD::FP_EXTEND:
2813 assert(VT.isFloatingPoint() &&
2814 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2815 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2816 assert((!VT.isVector() ||
2817 VT.getVectorNumElements() ==
2818 Operand.getValueType().getVectorNumElements()) &&
2819 "Vector element count mismatch!");
2820 if (Operand.getOpcode() == ISD::UNDEF)
2821 return getUNDEF(VT);
2823 case ISD::SIGN_EXTEND:
2824 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2825 "Invalid SIGN_EXTEND!");
2826 if (Operand.getValueType() == VT) return Operand; // noop extension
2827 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2828 "Invalid sext node, dst < src!");
2829 assert((!VT.isVector() ||
2830 VT.getVectorNumElements() ==
2831 Operand.getValueType().getVectorNumElements()) &&
2832 "Vector element count mismatch!");
2833 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2834 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2835 else if (OpOpcode == ISD::UNDEF)
2836 // sext(undef) = 0, because the top bits will all be the same.
2837 return getConstant(0, VT);
2839 case ISD::ZERO_EXTEND:
2840 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2841 "Invalid ZERO_EXTEND!");
2842 if (Operand.getValueType() == VT) return Operand; // noop extension
2843 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2844 "Invalid zext node, dst < src!");
2845 assert((!VT.isVector() ||
2846 VT.getVectorNumElements() ==
2847 Operand.getValueType().getVectorNumElements()) &&
2848 "Vector element count mismatch!");
2849 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2850 return getNode(ISD::ZERO_EXTEND, DL, VT,
2851 Operand.getNode()->getOperand(0));
2852 else if (OpOpcode == ISD::UNDEF)
2853 // zext(undef) = 0, because the top bits will be zero.
2854 return getConstant(0, VT);
2856 case ISD::ANY_EXTEND:
2857 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2858 "Invalid ANY_EXTEND!");
2859 if (Operand.getValueType() == VT) return Operand; // noop extension
2860 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2861 "Invalid anyext node, dst < src!");
2862 assert((!VT.isVector() ||
2863 VT.getVectorNumElements() ==
2864 Operand.getValueType().getVectorNumElements()) &&
2865 "Vector element count mismatch!");
2867 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2868 OpOpcode == ISD::ANY_EXTEND)
2869 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2870 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2871 else if (OpOpcode == ISD::UNDEF)
2872 return getUNDEF(VT);
2874 // (ext (trunx x)) -> x
2875 if (OpOpcode == ISD::TRUNCATE) {
2876 SDValue OpOp = Operand.getNode()->getOperand(0);
2877 if (OpOp.getValueType() == VT)
2882 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2883 "Invalid TRUNCATE!");
2884 if (Operand.getValueType() == VT) return Operand; // noop truncate
2885 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2886 "Invalid truncate node, src < dst!");
2887 assert((!VT.isVector() ||
2888 VT.getVectorNumElements() ==
2889 Operand.getValueType().getVectorNumElements()) &&
2890 "Vector element count mismatch!");
2891 if (OpOpcode == ISD::TRUNCATE)
2892 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2893 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2894 OpOpcode == ISD::ANY_EXTEND) {
2895 // If the source is smaller than the dest, we still need an extend.
2896 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2897 .bitsLT(VT.getScalarType()))
2898 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2899 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2900 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2901 return Operand.getNode()->getOperand(0);
2903 if (OpOpcode == ISD::UNDEF)
2904 return getUNDEF(VT);
2907 // Basic sanity checking.
2908 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2909 && "Cannot BITCAST between types of different sizes!");
2910 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2911 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2912 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2913 if (OpOpcode == ISD::UNDEF)
2914 return getUNDEF(VT);
2916 case ISD::SCALAR_TO_VECTOR:
2917 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2918 (VT.getVectorElementType() == Operand.getValueType() ||
2919 (VT.getVectorElementType().isInteger() &&
2920 Operand.getValueType().isInteger() &&
2921 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2922 "Illegal SCALAR_TO_VECTOR node!");
2923 if (OpOpcode == ISD::UNDEF)
2924 return getUNDEF(VT);
2925 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2926 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2927 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2928 Operand.getConstantOperandVal(1) == 0 &&
2929 Operand.getOperand(0).getValueType() == VT)
2930 return Operand.getOperand(0);
2933 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2934 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2935 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2936 Operand.getNode()->getOperand(0));
2937 if (OpOpcode == ISD::FNEG) // --X -> X
2938 return Operand.getNode()->getOperand(0);
2941 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2942 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2947 SDVTList VTs = getVTList(VT);
2948 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2949 FoldingSetNodeID ID;
2950 SDValue Ops[1] = { Operand };
2951 AddNodeIDNode(ID, Opcode, VTs, Ops);
2953 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2954 return SDValue(E, 0);
2956 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2957 DL.getDebugLoc(), VTs, Operand);
2958 CSEMap.InsertNode(N, IP);
2960 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2961 DL.getDebugLoc(), VTs, Operand);
2965 return SDValue(N, 0);
2968 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2969 SDNode *Cst1, SDNode *Cst2) {
2970 // If the opcode is a target-specific ISD node, there's nothing we can
2971 // do here and the operand rules may not line up with the below, so
2973 if (Opcode >= ISD::BUILTIN_OP_END)
2976 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2977 SmallVector<SDValue, 4> Outputs;
2978 EVT SVT = VT.getScalarType();
2980 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2981 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2982 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2985 if (Scalar1 && Scalar2)
2986 // Scalar instruction.
2987 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2989 // For vectors extract each constant element into Inputs so we can constant
2990 // fold them individually.
2991 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2992 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2996 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2998 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2999 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3000 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3001 if (!V1 || !V2) // Not a constant, bail.
3004 if (V1->isOpaque() || V2->isOpaque())
3007 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3008 // FIXME: This is valid and could be handled by truncating the APInts.
3009 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3012 Inputs.push_back(std::make_pair(V1, V2));
3016 // We have a number of constant values, constant fold them element by element.
3017 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3018 const APInt &C1 = Inputs[I].first->getAPIntValue();
3019 const APInt &C2 = Inputs[I].second->getAPIntValue();
3023 Outputs.push_back(getConstant(C1 + C2, SVT));
3026 Outputs.push_back(getConstant(C1 - C2, SVT));
3029 Outputs.push_back(getConstant(C1 * C2, SVT));
3032 if (!C2.getBoolValue())
3034 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3037 if (!C2.getBoolValue())
3039 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3042 if (!C2.getBoolValue())
3044 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3047 if (!C2.getBoolValue())
3049 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3052 Outputs.push_back(getConstant(C1 & C2, SVT));
3055 Outputs.push_back(getConstant(C1 | C2, SVT));
3058 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3061 Outputs.push_back(getConstant(C1 << C2, SVT));
3064 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3067 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3070 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3073 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3080 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3081 "Expected a scalar or vector!"));
3083 // Handle the scalar case first.
3085 return Outputs.back();
3087 // We may have a vector type but a scalar result. Create a splat.
3088 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3090 // Build a big vector out of the scalar elements we generated.
3091 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3094 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3095 SDValue N2, bool nuw, bool nsw, bool exact) {
3096 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3097 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3100 case ISD::TokenFactor:
3101 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3102 N2.getValueType() == MVT::Other && "Invalid token factor!");
3103 // Fold trivial token factors.
3104 if (N1.getOpcode() == ISD::EntryToken) return N2;
3105 if (N2.getOpcode() == ISD::EntryToken) return N1;
3106 if (N1 == N2) return N1;
3108 case ISD::CONCAT_VECTORS:
3109 // Concat of UNDEFs is UNDEF.
3110 if (N1.getOpcode() == ISD::UNDEF &&
3111 N2.getOpcode() == ISD::UNDEF)
3112 return getUNDEF(VT);
3114 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3115 // one big BUILD_VECTOR.
3116 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3117 N2.getOpcode() == ISD::BUILD_VECTOR) {
3118 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3119 N1.getNode()->op_end());
3120 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3121 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3125 assert(VT.isInteger() && "This operator does not apply to FP types!");
3126 assert(N1.getValueType() == N2.getValueType() &&
3127 N1.getValueType() == VT && "Binary operator types must match!");
3128 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3129 // worth handling here.
3130 if (N2C && N2C->isNullValue())
3132 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3139 assert(VT.isInteger() && "This operator does not apply to FP types!");
3140 assert(N1.getValueType() == N2.getValueType() &&
3141 N1.getValueType() == VT && "Binary operator types must match!");
3142 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3143 // it's worth handling here.
3144 if (N2C && N2C->isNullValue())
3154 assert(VT.isInteger() && "This operator does not apply to FP types!");
3155 assert(N1.getValueType() == N2.getValueType() &&
3156 N1.getValueType() == VT && "Binary operator types must match!");
3163 if (getTarget().Options.UnsafeFPMath) {
3164 if (Opcode == ISD::FADD) {
3166 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3167 if (CFP->getValueAPF().isZero())
3170 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3171 if (CFP->getValueAPF().isZero())
3173 } else if (Opcode == ISD::FSUB) {
3175 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3176 if (CFP->getValueAPF().isZero())
3178 } else if (Opcode == ISD::FMUL) {
3179 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3182 // If the first operand isn't the constant, try the second
3184 CFP = dyn_cast<ConstantFPSDNode>(N2);
3191 return SDValue(CFP,0);
3193 if (CFP->isExactlyValue(1.0))
3198 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3199 assert(N1.getValueType() == N2.getValueType() &&
3200 N1.getValueType() == VT && "Binary operator types must match!");
3202 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3203 assert(N1.getValueType() == VT &&
3204 N1.getValueType().isFloatingPoint() &&
3205 N2.getValueType().isFloatingPoint() &&
3206 "Invalid FCOPYSIGN!");
3213 assert(VT == N1.getValueType() &&
3214 "Shift operators return type must be the same as their first arg");
3215 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3216 "Shifts only work on integers");
3217 assert((!VT.isVector() || VT == N2.getValueType()) &&
3218 "Vector shift amounts must be in the same as their first arg");
3219 // Verify that the shift amount VT is bit enough to hold valid shift
3220 // amounts. This catches things like trying to shift an i1024 value by an
3221 // i8, which is easy to fall into in generic code that uses
3222 // TLI.getShiftAmount().
3223 assert(N2.getValueType().getSizeInBits() >=
3224 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3225 "Invalid use of small shift amount with oversized value!");
3227 // Always fold shifts of i1 values so the code generator doesn't need to
3228 // handle them. Since we know the size of the shift has to be less than the
3229 // size of the value, the shift/rotate count is guaranteed to be zero.
3232 if (N2C && N2C->isNullValue())
3235 case ISD::FP_ROUND_INREG: {
3236 EVT EVT = cast<VTSDNode>(N2)->getVT();
3237 assert(VT == N1.getValueType() && "Not an inreg round!");
3238 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3239 "Cannot FP_ROUND_INREG integer types");
3240 assert(EVT.isVector() == VT.isVector() &&
3241 "FP_ROUND_INREG type should be vector iff the operand "
3243 assert((!EVT.isVector() ||
3244 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3245 "Vector element counts must match in FP_ROUND_INREG");
3246 assert(EVT.bitsLE(VT) && "Not rounding down!");
3248 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3252 assert(VT.isFloatingPoint() &&
3253 N1.getValueType().isFloatingPoint() &&
3254 VT.bitsLE(N1.getValueType()) &&
3255 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3256 if (N1.getValueType() == VT) return N1; // noop conversion.
3258 case ISD::AssertSext:
3259 case ISD::AssertZext: {
3260 EVT EVT = cast<VTSDNode>(N2)->getVT();
3261 assert(VT == N1.getValueType() && "Not an inreg extend!");
3262 assert(VT.isInteger() && EVT.isInteger() &&
3263 "Cannot *_EXTEND_INREG FP types");
3264 assert(!EVT.isVector() &&
3265 "AssertSExt/AssertZExt type should be the vector element type "
3266 "rather than the vector type!");
3267 assert(EVT.bitsLE(VT) && "Not extending!");
3268 if (VT == EVT) return N1; // noop assertion.
3271 case ISD::SIGN_EXTEND_INREG: {
3272 EVT EVT = cast<VTSDNode>(N2)->getVT();
3273 assert(VT == N1.getValueType() && "Not an inreg extend!");
3274 assert(VT.isInteger() && EVT.isInteger() &&
3275 "Cannot *_EXTEND_INREG FP types");
3276 assert(EVT.isVector() == VT.isVector() &&
3277 "SIGN_EXTEND_INREG type should be vector iff the operand "
3279 assert((!EVT.isVector() ||
3280 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3281 "Vector element counts must match in SIGN_EXTEND_INREG");
3282 assert(EVT.bitsLE(VT) && "Not extending!");
3283 if (EVT == VT) return N1; // Not actually extending
3286 APInt Val = N1C->getAPIntValue();
3287 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3288 Val <<= Val.getBitWidth()-FromBits;
3289 Val = Val.ashr(Val.getBitWidth()-FromBits);
3290 return getConstant(Val, VT);
3294 case ISD::EXTRACT_VECTOR_ELT:
3295 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3296 if (N1.getOpcode() == ISD::UNDEF)
3297 return getUNDEF(VT);
3299 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3300 // expanding copies of large vectors from registers.
3302 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3303 N1.getNumOperands() > 0) {
3305 N1.getOperand(0).getValueType().getVectorNumElements();
3306 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3307 N1.getOperand(N2C->getZExtValue() / Factor),
3308 getConstant(N2C->getZExtValue() % Factor,
3309 N2.getValueType()));
3312 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3313 // expanding large vector constants.
3314 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3315 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3317 if (VT != Elt.getValueType())
3318 // If the vector element type is not legal, the BUILD_VECTOR operands
3319 // are promoted and implicitly truncated, and the result implicitly
3320 // extended. Make that explicit here.
3321 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3326 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3327 // operations are lowered to scalars.
3328 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3329 // If the indices are the same, return the inserted element else
3330 // if the indices are known different, extract the element from
3331 // the original vector.
3332 SDValue N1Op2 = N1.getOperand(2);
3333 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3335 if (N1Op2C && N2C) {
3336 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3337 if (VT == N1.getOperand(1).getValueType())
3338 return N1.getOperand(1);
3340 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3343 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3347 case ISD::EXTRACT_ELEMENT:
3348 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3349 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3350 (N1.getValueType().isInteger() == VT.isInteger()) &&
3351 N1.getValueType() != VT &&
3352 "Wrong types for EXTRACT_ELEMENT!");
3354 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3355 // 64-bit integers into 32-bit parts. Instead of building the extract of
3356 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3357 if (N1.getOpcode() == ISD::BUILD_PAIR)
3358 return N1.getOperand(N2C->getZExtValue());
3360 // EXTRACT_ELEMENT of a constant int is also very common.
3361 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3362 unsigned ElementSize = VT.getSizeInBits();
3363 unsigned Shift = ElementSize * N2C->getZExtValue();
3364 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3365 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3368 case ISD::EXTRACT_SUBVECTOR: {
3370 if (VT.isSimple() && N1.getValueType().isSimple()) {
3371 assert(VT.isVector() && N1.getValueType().isVector() &&
3372 "Extract subvector VTs must be a vectors!");
3373 assert(VT.getVectorElementType() ==
3374 N1.getValueType().getVectorElementType() &&
3375 "Extract subvector VTs must have the same element type!");
3376 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3377 "Extract subvector must be from larger vector to smaller vector!");
3379 if (isa<ConstantSDNode>(Index.getNode())) {
3380 assert((VT.getVectorNumElements() +
3381 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3382 <= N1.getValueType().getVectorNumElements())
3383 && "Extract subvector overflow!");
3386 // Trivial extraction.
3387 if (VT.getSimpleVT() == N1.getSimpleValueType())
3394 // Perform trivial constant folding.
3395 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3396 if (SV.getNode()) return SV;
3398 // Canonicalize constant to RHS if commutative.
3399 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3400 std::swap(N1C, N2C);
3404 // Constant fold FP operations.
3405 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3406 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3407 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3409 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3410 // Canonicalize constant to RHS if commutative.
3411 std::swap(N1CFP, N2CFP);
3414 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3415 APFloat::opStatus s;
3418 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3419 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3420 return getConstantFP(V1, VT);
3423 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3424 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3425 return getConstantFP(V1, VT);
3428 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3429 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3430 return getConstantFP(V1, VT);
3433 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3434 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3435 s!=APFloat::opDivByZero)) {
3436 return getConstantFP(V1, VT);
3440 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3441 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3442 s!=APFloat::opDivByZero)) {
3443 return getConstantFP(V1, VT);
3446 case ISD::FCOPYSIGN:
3448 return getConstantFP(V1, VT);
3453 if (Opcode == ISD::FP_ROUND) {
3454 APFloat V = N1CFP->getValueAPF(); // make copy
3456 // This can return overflow, underflow, or inexact; we don't care.
3457 // FIXME need to be more flexible about rounding mode.
3458 (void)V.convert(EVTToAPFloatSemantics(VT),
3459 APFloat::rmNearestTiesToEven, &ignored);
3460 return getConstantFP(V, VT);
3464 // Canonicalize an UNDEF to the RHS, even over a constant.
3465 if (N1.getOpcode() == ISD::UNDEF) {
3466 if (isCommutativeBinOp(Opcode)) {
3470 case ISD::FP_ROUND_INREG:
3471 case ISD::SIGN_EXTEND_INREG:
3477 return N1; // fold op(undef, arg2) -> undef
3485 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3486 // For vectors, we can't easily build an all zero vector, just return
3493 // Fold a bunch of operators when the RHS is undef.
3494 if (N2.getOpcode() == ISD::UNDEF) {
3497 if (N1.getOpcode() == ISD::UNDEF)
3498 // Handle undef ^ undef -> 0 special case. This is a common
3500 return getConstant(0, VT);
3510 return N2; // fold op(arg1, undef) -> undef
3516 if (getTarget().Options.UnsafeFPMath)
3524 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3525 // For vectors, we can't easily build an all zero vector, just return
3530 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3531 // For vectors, we can't easily build an all one vector, just return
3539 // Memoize this node if possible.
3541 SDVTList VTs = getVTList(VT);
3542 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3543 if (VT != MVT::Glue) {
3544 SDValue Ops[] = {N1, N2};
3545 FoldingSetNodeID ID;
3546 AddNodeIDNode(ID, Opcode, VTs, Ops);
3548 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3550 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3551 return SDValue(E, 0);
3553 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3555 CSEMap.InsertNode(N, IP);
3558 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3562 return SDValue(N, 0);
3565 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3566 SDValue N1, SDValue N2, SDValue N3) {
3567 // Perform various simplifications.
3568 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3571 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3572 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3573 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3574 if (N1CFP && N2CFP && N3CFP) {
3575 APFloat V1 = N1CFP->getValueAPF();
3576 const APFloat &V2 = N2CFP->getValueAPF();
3577 const APFloat &V3 = N3CFP->getValueAPF();
3578 APFloat::opStatus s =
3579 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3580 if (s != APFloat::opInvalidOp)
3581 return getConstantFP(V1, VT);
3585 case ISD::CONCAT_VECTORS:
3586 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3587 // one big BUILD_VECTOR.
3588 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3589 N2.getOpcode() == ISD::BUILD_VECTOR &&
3590 N3.getOpcode() == ISD::BUILD_VECTOR) {
3591 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3592 N1.getNode()->op_end());
3593 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3594 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3595 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3599 // Use FoldSetCC to simplify SETCC's.
3600 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3601 if (Simp.getNode()) return Simp;
3606 if (N1C->getZExtValue())
3607 return N2; // select true, X, Y -> X
3608 return N3; // select false, X, Y -> Y
3611 if (N2 == N3) return N2; // select C, X, X -> X
3613 case ISD::VECTOR_SHUFFLE:
3614 llvm_unreachable("should use getVectorShuffle constructor!");
3615 case ISD::INSERT_SUBVECTOR: {
3617 if (VT.isSimple() && N1.getValueType().isSimple()
3618 && N2.getValueType().isSimple()) {
3619 assert(VT.isVector() && N1.getValueType().isVector() &&
3620 N2.getValueType().isVector() &&
3621 "Insert subvector VTs must be a vectors");
3622 assert(VT == N1.getValueType() &&
3623 "Dest and insert subvector source types must match!");
3624 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3625 "Insert subvector must be from smaller vector to larger vector!");
3626 if (isa<ConstantSDNode>(Index.getNode())) {
3627 assert((N2.getValueType().getVectorNumElements() +
3628 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3629 <= VT.getVectorNumElements())
3630 && "Insert subvector overflow!");
3633 // Trivial insertion.
3634 if (VT.getSimpleVT() == N2.getSimpleValueType())
3640 // Fold bit_convert nodes from a type to themselves.
3641 if (N1.getValueType() == VT)
3646 // Memoize node if it doesn't produce a flag.
3648 SDVTList VTs = getVTList(VT);
3649 if (VT != MVT::Glue) {
3650 SDValue Ops[] = { N1, N2, N3 };
3651 FoldingSetNodeID ID;
3652 AddNodeIDNode(ID, Opcode, VTs, Ops);
3654 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3655 return SDValue(E, 0);
3657 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3658 DL.getDebugLoc(), VTs, N1, N2, N3);
3659 CSEMap.InsertNode(N, IP);
3661 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3662 DL.getDebugLoc(), VTs, N1, N2, N3);
3666 return SDValue(N, 0);
3669 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3670 SDValue N1, SDValue N2, SDValue N3,
3672 SDValue Ops[] = { N1, N2, N3, N4 };
3673 return getNode(Opcode, DL, VT, Ops);
3676 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3677 SDValue N1, SDValue N2, SDValue N3,
3678 SDValue N4, SDValue N5) {
3679 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3680 return getNode(Opcode, DL, VT, Ops);
3683 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3684 /// the incoming stack arguments to be loaded from the stack.
3685 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3686 SmallVector<SDValue, 8> ArgChains;
3688 // Include the original chain at the beginning of the list. When this is
3689 // used by target LowerCall hooks, this helps legalize find the
3690 // CALLSEQ_BEGIN node.
3691 ArgChains.push_back(Chain);
3693 // Add a chain value for each stack argument.
3694 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3695 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3696 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3697 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3698 if (FI->getIndex() < 0)
3699 ArgChains.push_back(SDValue(L, 1));
3701 // Build a tokenfactor for all the chains.
3702 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3705 /// getMemsetValue - Vectorized representation of the memset value
3707 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3709 assert(Value.getOpcode() != ISD::UNDEF);
3711 unsigned NumBits = VT.getScalarType().getSizeInBits();
3712 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3713 assert(C->getAPIntValue().getBitWidth() == 8);
3714 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3716 return DAG.getConstant(Val, VT);
3717 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3720 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3722 // Use a multiplication with 0x010101... to extend the input to the
3724 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3725 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3731 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3732 /// used when a memcpy is turned into a memset when the source is a constant
3734 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3735 const TargetLowering &TLI, StringRef Str) {
3736 // Handle vector with all elements zero.
3739 return DAG.getConstant(0, VT);
3740 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3741 return DAG.getConstantFP(0.0, VT);
3742 else if (VT.isVector()) {
3743 unsigned NumElts = VT.getVectorNumElements();
3744 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3745 return DAG.getNode(ISD::BITCAST, dl, VT,
3746 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3749 llvm_unreachable("Expected type!");
3752 assert(!VT.isVector() && "Can't handle vector type here!");
3753 unsigned NumVTBits = VT.getSizeInBits();
3754 unsigned NumVTBytes = NumVTBits / 8;
3755 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3757 APInt Val(NumVTBits, 0);
3758 if (TLI.isLittleEndian()) {
3759 for (unsigned i = 0; i != NumBytes; ++i)
3760 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3762 for (unsigned i = 0; i != NumBytes; ++i)
3763 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3766 // If the "cost" of materializing the integer immediate is less than the cost
3767 // of a load, then it is cost effective to turn the load into the immediate.
3768 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3769 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3770 return DAG.getConstant(Val, VT);
3771 return SDValue(nullptr, 0);
3774 /// getMemBasePlusOffset - Returns base and offset node for the
3776 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3777 SelectionDAG &DAG) {
3778 EVT VT = Base.getValueType();
3779 return DAG.getNode(ISD::ADD, dl,
3780 VT, Base, DAG.getConstant(Offset, VT));
3783 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3785 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3786 unsigned SrcDelta = 0;
3787 GlobalAddressSDNode *G = nullptr;
3788 if (Src.getOpcode() == ISD::GlobalAddress)
3789 G = cast<GlobalAddressSDNode>(Src);
3790 else if (Src.getOpcode() == ISD::ADD &&
3791 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3792 Src.getOperand(1).getOpcode() == ISD::Constant) {
3793 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3794 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3799 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3802 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3803 /// to replace the memset / memcpy. Return true if the number of memory ops
3804 /// is below the threshold. It returns the types of the sequence of
3805 /// memory ops to perform memset / memcpy by reference.
3806 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3807 unsigned Limit, uint64_t Size,
3808 unsigned DstAlign, unsigned SrcAlign,
3814 const TargetLowering &TLI) {
3815 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3816 "Expecting memcpy / memset source to meet alignment requirement!");
3817 // If 'SrcAlign' is zero, that means the memory operation does not need to
3818 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3819 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3820 // is the specified alignment of the memory operation. If it is zero, that
3821 // means it's possible to change the alignment of the destination.
3822 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3823 // not need to be loaded.
3824 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3825 IsMemset, ZeroMemset, MemcpyStrSrc,
3826 DAG.getMachineFunction());
3828 if (VT == MVT::Other) {
3830 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3831 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3832 VT = TLI.getPointerTy();
3834 switch (DstAlign & 7) {
3835 case 0: VT = MVT::i64; break;
3836 case 4: VT = MVT::i32; break;
3837 case 2: VT = MVT::i16; break;
3838 default: VT = MVT::i8; break;
3843 while (!TLI.isTypeLegal(LVT))
3844 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3845 assert(LVT.isInteger());
3851 unsigned NumMemOps = 0;
3853 unsigned VTSize = VT.getSizeInBits() / 8;
3854 while (VTSize > Size) {
3855 // For now, only use non-vector load / store's for the left-over pieces.
3860 if (VT.isVector() || VT.isFloatingPoint()) {
3861 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3862 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3863 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3865 else if (NewVT == MVT::i64 &&
3866 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3867 TLI.isSafeMemOpType(MVT::f64)) {
3868 // i64 is usually not legal on 32-bit targets, but f64 may be.
3876 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3877 if (NewVT == MVT::i8)
3879 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3881 NewVTSize = NewVT.getSizeInBits() / 8;
3883 // If the new VT cannot cover all of the remaining bits, then consider
3884 // issuing a (or a pair of) unaligned and overlapping load / store.
3885 // FIXME: Only does this for 64-bit or more since we don't have proper
3886 // cost model for unaligned load / store.
3889 if (NumMemOps && AllowOverlap &&
3890 VTSize >= 8 && NewVTSize < Size &&
3891 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3899 if (++NumMemOps > Limit)
3902 MemOps.push_back(VT);
3909 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3910 SDValue Chain, SDValue Dst,
3911 SDValue Src, uint64_t Size,
3912 unsigned Align, bool isVol,
3914 MachinePointerInfo DstPtrInfo,
3915 MachinePointerInfo SrcPtrInfo) {
3916 // Turn a memcpy of undef to nop.
3917 if (Src.getOpcode() == ISD::UNDEF)
3920 // Expand memcpy to a series of load and store ops if the size operand falls
3921 // below a certain threshold.
3922 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3923 // rather than maybe a humongous number of loads and stores.
3924 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3925 std::vector<EVT> MemOps;
3926 bool DstAlignCanChange = false;
3927 MachineFunction &MF = DAG.getMachineFunction();
3928 MachineFrameInfo *MFI = MF.getFrameInfo();
3930 MF.getFunction()->getAttributes().
3931 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3932 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3933 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3934 DstAlignCanChange = true;
3935 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3936 if (Align > SrcAlign)
3939 bool CopyFromStr = isMemSrcFromString(Src, Str);
3940 bool isZeroStr = CopyFromStr && Str.empty();
3941 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3943 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3944 (DstAlignCanChange ? 0 : Align),
3945 (isZeroStr ? 0 : SrcAlign),
3946 false, false, CopyFromStr, true, DAG, TLI))
3949 if (DstAlignCanChange) {
3950 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3951 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3953 // Don't promote to an alignment that would require dynamic stack
3955 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3956 if (!TRI->needsStackRealignment(MF))
3957 while (NewAlign > Align &&
3958 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3961 if (NewAlign > Align) {
3962 // Give the stack frame object a larger alignment if needed.
3963 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3964 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3969 SmallVector<SDValue, 8> OutChains;
3970 unsigned NumMemOps = MemOps.size();
3971 uint64_t SrcOff = 0, DstOff = 0;
3972 for (unsigned i = 0; i != NumMemOps; ++i) {
3974 unsigned VTSize = VT.getSizeInBits() / 8;
3975 SDValue Value, Store;
3977 if (VTSize > Size) {
3978 // Issuing an unaligned load / store pair that overlaps with the previous
3979 // pair. Adjust the offset accordingly.
3980 assert(i == NumMemOps-1 && i != 0);
3981 SrcOff -= VTSize - Size;
3982 DstOff -= VTSize - Size;
3986 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3987 // It's unlikely a store of a vector immediate can be done in a single
3988 // instruction. It would require a load from a constantpool first.
3989 // We only handle zero vectors here.
3990 // FIXME: Handle other cases where store of vector immediate is done in
3991 // a single instruction.
3992 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3993 if (Value.getNode())
3994 Store = DAG.getStore(Chain, dl, Value,
3995 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3996 DstPtrInfo.getWithOffset(DstOff), isVol,
4000 if (!Store.getNode()) {
4001 // The type might not be legal for the target. This should only happen
4002 // if the type is smaller than a legal type, as on PPC, so the right
4003 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4004 // to Load/Store if NVT==VT.
4005 // FIXME does the case above also need this?
4006 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4007 assert(NVT.bitsGE(VT));
4008 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4009 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4010 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4011 false, MinAlign(SrcAlign, SrcOff));
4012 Store = DAG.getTruncStore(Chain, dl, Value,
4013 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4014 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4017 OutChains.push_back(Store);
4023 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4026 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4027 SDValue Chain, SDValue Dst,
4028 SDValue Src, uint64_t Size,
4029 unsigned Align, bool isVol,
4031 MachinePointerInfo DstPtrInfo,
4032 MachinePointerInfo SrcPtrInfo) {
4033 // Turn a memmove of undef to nop.
4034 if (Src.getOpcode() == ISD::UNDEF)
4037 // Expand memmove to a series of load and store ops if the size operand falls
4038 // below a certain threshold.
4039 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4040 std::vector<EVT> MemOps;
4041 bool DstAlignCanChange = false;
4042 MachineFunction &MF = DAG.getMachineFunction();
4043 MachineFrameInfo *MFI = MF.getFrameInfo();
4044 bool OptSize = MF.getFunction()->getAttributes().
4045 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4046 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4047 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4048 DstAlignCanChange = true;
4049 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4050 if (Align > SrcAlign)
4052 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4054 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4055 (DstAlignCanChange ? 0 : Align), SrcAlign,
4056 false, false, false, false, DAG, TLI))
4059 if (DstAlignCanChange) {
4060 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4061 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4062 if (NewAlign > Align) {
4063 // Give the stack frame object a larger alignment if needed.
4064 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4065 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4070 uint64_t SrcOff = 0, DstOff = 0;
4071 SmallVector<SDValue, 8> LoadValues;
4072 SmallVector<SDValue, 8> LoadChains;
4073 SmallVector<SDValue, 8> OutChains;
4074 unsigned NumMemOps = MemOps.size();
4075 for (unsigned i = 0; i < NumMemOps; i++) {
4077 unsigned VTSize = VT.getSizeInBits() / 8;
4080 Value = DAG.getLoad(VT, dl, Chain,
4081 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4082 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4083 false, false, SrcAlign);
4084 LoadValues.push_back(Value);
4085 LoadChains.push_back(Value.getValue(1));
4088 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4090 for (unsigned i = 0; i < NumMemOps; i++) {
4092 unsigned VTSize = VT.getSizeInBits() / 8;
4095 Store = DAG.getStore(Chain, dl, LoadValues[i],
4096 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4097 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4098 OutChains.push_back(Store);
4102 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4105 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4108 /// \param DAG Selection DAG where lowered code is placed.
4109 /// \param dl Link to corresponding IR location.
4110 /// \param Chain Control flow dependency.
4111 /// \param Dst Pointer to destination memory location.
4112 /// \param Src Value of byte to write into the memory.
4113 /// \param Size Number of bytes to write.
4114 /// \param Align Alignment of the destination in bytes.
4115 /// \param isVol True if destination is volatile.
4116 /// \param DstPtrInfo IR information on the memory pointer.
4117 /// \returns New head in the control flow, if lowering was successful, empty
4118 /// SDValue otherwise.
4120 /// The function tries to replace 'llvm.memset' intrinsic with several store
4121 /// operations and value calculation code. This is usually profitable for small
4123 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4124 SDValue Chain, SDValue Dst,
4125 SDValue Src, uint64_t Size,
4126 unsigned Align, bool isVol,
4127 MachinePointerInfo DstPtrInfo) {
4128 // Turn a memset of undef to nop.
4129 if (Src.getOpcode() == ISD::UNDEF)
4132 // Expand memset to a series of load/store ops if the size operand
4133 // falls below a certain threshold.
4134 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4135 std::vector<EVT> MemOps;
4136 bool DstAlignCanChange = false;
4137 MachineFunction &MF = DAG.getMachineFunction();
4138 MachineFrameInfo *MFI = MF.getFrameInfo();
4139 bool OptSize = MF.getFunction()->getAttributes().
4140 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4141 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4142 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4143 DstAlignCanChange = true;
4145 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4146 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4147 Size, (DstAlignCanChange ? 0 : Align), 0,
4148 true, IsZeroVal, false, true, DAG, TLI))
4151 if (DstAlignCanChange) {
4152 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4153 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4154 if (NewAlign > Align) {
4155 // Give the stack frame object a larger alignment if needed.
4156 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4157 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4162 SmallVector<SDValue, 8> OutChains;
4163 uint64_t DstOff = 0;
4164 unsigned NumMemOps = MemOps.size();
4166 // Find the largest store and generate the bit pattern for it.
4167 EVT LargestVT = MemOps[0];
4168 for (unsigned i = 1; i < NumMemOps; i++)
4169 if (MemOps[i].bitsGT(LargestVT))
4170 LargestVT = MemOps[i];
4171 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4173 for (unsigned i = 0; i < NumMemOps; i++) {
4175 unsigned VTSize = VT.getSizeInBits() / 8;
4176 if (VTSize > Size) {
4177 // Issuing an unaligned load / store pair that overlaps with the previous
4178 // pair. Adjust the offset accordingly.
4179 assert(i == NumMemOps-1 && i != 0);
4180 DstOff -= VTSize - Size;
4183 // If this store is smaller than the largest store see whether we can get
4184 // the smaller value for free with a truncate.
4185 SDValue Value = MemSetValue;
4186 if (VT.bitsLT(LargestVT)) {
4187 if (!LargestVT.isVector() && !VT.isVector() &&
4188 TLI.isTruncateFree(LargestVT, VT))
4189 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4191 Value = getMemsetValue(Src, VT, DAG, dl);
4193 assert(Value.getValueType() == VT && "Value with wrong type.");
4194 SDValue Store = DAG.getStore(Chain, dl, Value,
4195 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4196 DstPtrInfo.getWithOffset(DstOff),
4197 isVol, false, Align);
4198 OutChains.push_back(Store);
4199 DstOff += VT.getSizeInBits() / 8;
4203 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4206 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4207 SDValue Src, SDValue Size,
4208 unsigned Align, bool isVol, bool AlwaysInline,
4209 MachinePointerInfo DstPtrInfo,
4210 MachinePointerInfo SrcPtrInfo) {
4211 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4213 // Check to see if we should lower the memcpy to loads and stores first.
4214 // For cases within the target-specified limits, this is the best choice.
4215 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4217 // Memcpy with size zero? Just return the original chain.
4218 if (ConstantSize->isNullValue())
4221 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4222 ConstantSize->getZExtValue(),Align,
4223 isVol, false, DstPtrInfo, SrcPtrInfo);
4224 if (Result.getNode())
4228 // Then check to see if we should lower the memcpy with target-specific
4229 // code. If the target chooses to do this, this is the next best.
4231 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4232 isVol, AlwaysInline,
4233 DstPtrInfo, SrcPtrInfo);
4234 if (Result.getNode())
4237 // If we really need inline code and the target declined to provide it,
4238 // use a (potentially long) sequence of loads and stores.
4240 assert(ConstantSize && "AlwaysInline requires a constant size!");
4241 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4242 ConstantSize->getZExtValue(), Align, isVol,
4243 true, DstPtrInfo, SrcPtrInfo);
4246 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4247 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4248 // respect volatile, so they may do things like read or write memory
4249 // beyond the given memory regions. But fixing this isn't easy, and most
4250 // people don't care.
4252 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
4254 // Emit a library call.
4255 TargetLowering::ArgListTy Args;
4256 TargetLowering::ArgListEntry Entry;
4257 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4258 Entry.Node = Dst; Args.push_back(Entry);
4259 Entry.Node = Src; Args.push_back(Entry);
4260 Entry.Node = Size; Args.push_back(Entry);
4261 // FIXME: pass in SDLoc
4262 TargetLowering::CallLoweringInfo CLI(*this);
4263 CLI.setDebugLoc(dl).setChain(Chain)
4264 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4265 Type::getVoidTy(*getContext()),
4266 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4267 TLI->getPointerTy()), std::move(Args), 0)
4268 .setDiscardResult();
4269 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4271 return CallResult.second;
4274 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4275 SDValue Src, SDValue Size,
4276 unsigned Align, bool isVol,
4277 MachinePointerInfo DstPtrInfo,
4278 MachinePointerInfo SrcPtrInfo) {
4279 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4281 // Check to see if we should lower the memmove to loads and stores first.
4282 // For cases within the target-specified limits, this is the best choice.
4283 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4285 // Memmove with size zero? Just return the original chain.
4286 if (ConstantSize->isNullValue())
4290 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4291 ConstantSize->getZExtValue(), Align, isVol,
4292 false, DstPtrInfo, SrcPtrInfo);
4293 if (Result.getNode())
4297 // Then check to see if we should lower the memmove with target-specific
4298 // code. If the target chooses to do this, this is the next best.
4300 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4301 DstPtrInfo, SrcPtrInfo);
4302 if (Result.getNode())
4305 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4306 // not be safe. See memcpy above for more details.
4308 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
4310 // Emit a library call.
4311 TargetLowering::ArgListTy Args;
4312 TargetLowering::ArgListEntry Entry;
4313 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4314 Entry.Node = Dst; Args.push_back(Entry);
4315 Entry.Node = Src; Args.push_back(Entry);
4316 Entry.Node = Size; Args.push_back(Entry);
4317 // FIXME: pass in SDLoc
4318 TargetLowering::CallLoweringInfo CLI(*this);
4319 CLI.setDebugLoc(dl).setChain(Chain)
4320 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4321 Type::getVoidTy(*getContext()),
4322 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4323 TLI->getPointerTy()), std::move(Args), 0)
4324 .setDiscardResult();
4325 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4327 return CallResult.second;
4330 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4331 SDValue Src, SDValue Size,
4332 unsigned Align, bool isVol,
4333 MachinePointerInfo DstPtrInfo) {
4334 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4336 // Check to see if we should lower the memset to stores first.
4337 // For cases within the target-specified limits, this is the best choice.
4338 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4340 // Memset with size zero? Just return the original chain.
4341 if (ConstantSize->isNullValue())
4345 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4346 Align, isVol, DstPtrInfo);
4348 if (Result.getNode())
4352 // Then check to see if we should lower the memset with target-specific
4353 // code. If the target chooses to do this, this is the next best.
4355 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4357 if (Result.getNode())
4360 // Emit a library call.
4361 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
4362 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4363 TargetLowering::ArgListTy Args;
4364 TargetLowering::ArgListEntry Entry;
4365 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4366 Args.push_back(Entry);
4367 // Extend or truncate the argument to be an i32 value for the call.
4368 if (Src.getValueType().bitsGT(MVT::i32))
4369 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4371 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4373 Entry.Ty = Type::getInt32Ty(*getContext());
4374 Entry.isSExt = true;
4375 Args.push_back(Entry);
4377 Entry.Ty = IntPtrTy;
4378 Entry.isSExt = false;
4379 Args.push_back(Entry);
4381 // FIXME: pass in SDLoc
4382 TargetLowering::CallLoweringInfo CLI(*this);
4383 CLI.setDebugLoc(dl).setChain(Chain)
4384 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4385 Type::getVoidTy(*getContext()),
4386 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4387 TLI->getPointerTy()), std::move(Args), 0)
4388 .setDiscardResult();
4390 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4391 return CallResult.second;
4394 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4395 SDVTList VTList, ArrayRef<SDValue> Ops,
4396 MachineMemOperand *MMO,
4397 AtomicOrdering SuccessOrdering,
4398 AtomicOrdering FailureOrdering,
4399 SynchronizationScope SynchScope) {
4400 FoldingSetNodeID ID;
4401 ID.AddInteger(MemVT.getRawBits());
4402 AddNodeIDNode(ID, Opcode, VTList, Ops);
4403 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4405 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4406 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4407 return SDValue(E, 0);
4410 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4411 // SDNode doesn't have access to it. This memory will be "leaked" when
4412 // the node is deallocated, but recovered when the allocator is released.
4413 // If the number of operands is less than 5 we use AtomicSDNode's internal
4415 unsigned NumOps = Ops.size();
4416 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4419 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4420 dl.getDebugLoc(), VTList, MemVT,
4421 Ops.data(), DynOps, NumOps, MMO,
4422 SuccessOrdering, FailureOrdering,
4424 CSEMap.InsertNode(N, IP);
4426 return SDValue(N, 0);
4429 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4430 SDVTList VTList, ArrayRef<SDValue> Ops,
4431 MachineMemOperand *MMO,
4432 AtomicOrdering Ordering,
4433 SynchronizationScope SynchScope) {
4434 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4435 Ordering, SynchScope);
4438 SDValue SelectionDAG::getAtomicCmpSwap(
4439 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4440 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4441 unsigned Alignment, AtomicOrdering SuccessOrdering,
4442 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4443 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4444 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4445 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4447 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4448 Alignment = getEVTAlignment(MemVT);
4450 MachineFunction &MF = getMachineFunction();
4452 // FIXME: Volatile isn't really correct; we should keep track of atomic
4453 // orderings in the memoperand.
4454 unsigned Flags = MachineMemOperand::MOVolatile;
4455 Flags |= MachineMemOperand::MOLoad;
4456 Flags |= MachineMemOperand::MOStore;
4458 MachineMemOperand *MMO =
4459 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4461 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4462 SuccessOrdering, FailureOrdering, SynchScope);
4465 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4466 SDVTList VTs, SDValue Chain, SDValue Ptr,
4467 SDValue Cmp, SDValue Swp,
4468 MachineMemOperand *MMO,
4469 AtomicOrdering SuccessOrdering,
4470 AtomicOrdering FailureOrdering,
4471 SynchronizationScope SynchScope) {
4472 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4473 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4474 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4476 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4477 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4478 SuccessOrdering, FailureOrdering, SynchScope);
4481 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4483 SDValue Ptr, SDValue Val,
4484 const Value* PtrVal,
4486 AtomicOrdering Ordering,
4487 SynchronizationScope SynchScope) {
4488 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4489 Alignment = getEVTAlignment(MemVT);
4491 MachineFunction &MF = getMachineFunction();
4492 // An atomic store does not load. An atomic load does not store.
4493 // (An atomicrmw obviously both loads and stores.)
4494 // For now, atomics are considered to be volatile always, and they are
4496 // FIXME: Volatile isn't really correct; we should keep track of atomic
4497 // orderings in the memoperand.
4498 unsigned Flags = MachineMemOperand::MOVolatile;
4499 if (Opcode != ISD::ATOMIC_STORE)
4500 Flags |= MachineMemOperand::MOLoad;
4501 if (Opcode != ISD::ATOMIC_LOAD)
4502 Flags |= MachineMemOperand::MOStore;
4504 MachineMemOperand *MMO =
4505 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4506 MemVT.getStoreSize(), Alignment);
4508 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4509 Ordering, SynchScope);
4512 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4514 SDValue Ptr, SDValue Val,
4515 MachineMemOperand *MMO,
4516 AtomicOrdering Ordering,
4517 SynchronizationScope SynchScope) {
4518 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4519 Opcode == ISD::ATOMIC_LOAD_SUB ||
4520 Opcode == ISD::ATOMIC_LOAD_AND ||
4521 Opcode == ISD::ATOMIC_LOAD_OR ||
4522 Opcode == ISD::ATOMIC_LOAD_XOR ||
4523 Opcode == ISD::ATOMIC_LOAD_NAND ||
4524 Opcode == ISD::ATOMIC_LOAD_MIN ||
4525 Opcode == ISD::ATOMIC_LOAD_MAX ||
4526 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4527 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4528 Opcode == ISD::ATOMIC_SWAP ||
4529 Opcode == ISD::ATOMIC_STORE) &&
4530 "Invalid Atomic Op");
4532 EVT VT = Val.getValueType();
4534 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4535 getVTList(VT, MVT::Other);
4536 SDValue Ops[] = {Chain, Ptr, Val};
4537 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4540 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4541 EVT VT, SDValue Chain,
4543 MachineMemOperand *MMO,
4544 AtomicOrdering Ordering,
4545 SynchronizationScope SynchScope) {
4546 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4548 SDVTList VTs = getVTList(VT, MVT::Other);
4549 SDValue Ops[] = {Chain, Ptr};
4550 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4553 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4554 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4555 if (Ops.size() == 1)
4558 SmallVector<EVT, 4> VTs;
4559 VTs.reserve(Ops.size());
4560 for (unsigned i = 0; i < Ops.size(); ++i)
4561 VTs.push_back(Ops[i].getValueType());
4562 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4566 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4567 ArrayRef<SDValue> Ops,
4568 EVT MemVT, MachinePointerInfo PtrInfo,
4569 unsigned Align, bool Vol,
4570 bool ReadMem, bool WriteMem, unsigned Size) {
4571 if (Align == 0) // Ensure that codegen never sees alignment 0
4572 Align = getEVTAlignment(MemVT);
4574 MachineFunction &MF = getMachineFunction();
4577 Flags |= MachineMemOperand::MOStore;
4579 Flags |= MachineMemOperand::MOLoad;
4581 Flags |= MachineMemOperand::MOVolatile;
4583 Size = MemVT.getStoreSize();
4584 MachineMemOperand *MMO =
4585 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4587 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4591 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4592 ArrayRef<SDValue> Ops, EVT MemVT,
4593 MachineMemOperand *MMO) {
4594 assert((Opcode == ISD::INTRINSIC_VOID ||
4595 Opcode == ISD::INTRINSIC_W_CHAIN ||
4596 Opcode == ISD::PREFETCH ||
4597 Opcode == ISD::LIFETIME_START ||
4598 Opcode == ISD::LIFETIME_END ||
4599 (Opcode <= INT_MAX &&
4600 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4601 "Opcode is not a memory-accessing opcode!");
4603 // Memoize the node unless it returns a flag.
4604 MemIntrinsicSDNode *N;
4605 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4606 FoldingSetNodeID ID;
4607 AddNodeIDNode(ID, Opcode, VTList, Ops);
4608 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4610 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4611 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4612 return SDValue(E, 0);
4615 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4616 dl.getDebugLoc(), VTList, Ops,
4618 CSEMap.InsertNode(N, IP);
4620 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4621 dl.getDebugLoc(), VTList, Ops,
4625 return SDValue(N, 0);
4628 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4629 /// MachinePointerInfo record from it. This is particularly useful because the
4630 /// code generator has many cases where it doesn't bother passing in a
4631 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4632 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4633 // If this is FI+Offset, we can model it.
4634 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4635 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4637 // If this is (FI+Offset1)+Offset2, we can model it.
4638 if (Ptr.getOpcode() != ISD::ADD ||
4639 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4640 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4641 return MachinePointerInfo();
4643 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4644 return MachinePointerInfo::getFixedStack(FI, Offset+
4645 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4648 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4649 /// MachinePointerInfo record from it. This is particularly useful because the
4650 /// code generator has many cases where it doesn't bother passing in a
4651 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4652 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4653 // If the 'Offset' value isn't a constant, we can't handle this.
4654 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4655 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4656 if (OffsetOp.getOpcode() == ISD::UNDEF)
4657 return InferPointerInfo(Ptr);
4658 return MachinePointerInfo();
4663 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4664 EVT VT, SDLoc dl, SDValue Chain,
4665 SDValue Ptr, SDValue Offset,
4666 MachinePointerInfo PtrInfo, EVT MemVT,
4667 bool isVolatile, bool isNonTemporal, bool isInvariant,
4668 unsigned Alignment, const AAMDNodes &AAInfo,
4669 const MDNode *Ranges) {
4670 assert(Chain.getValueType() == MVT::Other &&
4671 "Invalid chain type");
4672 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4673 Alignment = getEVTAlignment(VT);
4675 unsigned Flags = MachineMemOperand::MOLoad;
4677 Flags |= MachineMemOperand::MOVolatile;
4679 Flags |= MachineMemOperand::MONonTemporal;
4681 Flags |= MachineMemOperand::MOInvariant;
4683 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4685 if (PtrInfo.V.isNull())
4686 PtrInfo = InferPointerInfo(Ptr, Offset);
4688 MachineFunction &MF = getMachineFunction();
4689 MachineMemOperand *MMO =
4690 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4692 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4696 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4697 EVT VT, SDLoc dl, SDValue Chain,
4698 SDValue Ptr, SDValue Offset, EVT MemVT,
4699 MachineMemOperand *MMO) {
4701 ExtType = ISD::NON_EXTLOAD;
4702 } else if (ExtType == ISD::NON_EXTLOAD) {
4703 assert(VT == MemVT && "Non-extending load from different memory type!");
4706 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4707 "Should only be an extending load, not truncating!");
4708 assert(VT.isInteger() == MemVT.isInteger() &&
4709 "Cannot convert from FP to Int or Int -> FP!");
4710 assert(VT.isVector() == MemVT.isVector() &&
4711 "Cannot use trunc store to convert to or from a vector!");
4712 assert((!VT.isVector() ||
4713 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4714 "Cannot use trunc store to change the number of vector elements!");
4717 bool Indexed = AM != ISD::UNINDEXED;
4718 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4719 "Unindexed load with an offset!");
4721 SDVTList VTs = Indexed ?
4722 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4723 SDValue Ops[] = { Chain, Ptr, Offset };
4724 FoldingSetNodeID ID;
4725 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4726 ID.AddInteger(MemVT.getRawBits());
4727 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4728 MMO->isNonTemporal(),
4729 MMO->isInvariant()));
4730 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4733 cast<LoadSDNode>(E)->refineAlignment(MMO);
4734 return SDValue(E, 0);
4736 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4737 dl.getDebugLoc(), VTs, AM, ExtType,
4739 CSEMap.InsertNode(N, IP);
4741 return SDValue(N, 0);
4744 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4745 SDValue Chain, SDValue Ptr,
4746 MachinePointerInfo PtrInfo,
4747 bool isVolatile, bool isNonTemporal,
4748 bool isInvariant, unsigned Alignment,
4749 const AAMDNodes &AAInfo,
4750 const MDNode *Ranges) {
4751 SDValue Undef = getUNDEF(Ptr.getValueType());
4752 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4753 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4757 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4758 SDValue Chain, SDValue Ptr,
4759 MachineMemOperand *MMO) {
4760 SDValue Undef = getUNDEF(Ptr.getValueType());
4761 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4765 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4766 SDValue Chain, SDValue Ptr,
4767 MachinePointerInfo PtrInfo, EVT MemVT,
4768 bool isVolatile, bool isNonTemporal,
4769 bool isInvariant, unsigned Alignment,
4770 const AAMDNodes &AAInfo) {
4771 SDValue Undef = getUNDEF(Ptr.getValueType());
4772 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4773 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4778 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4779 SDValue Chain, SDValue Ptr, EVT MemVT,
4780 MachineMemOperand *MMO) {
4781 SDValue Undef = getUNDEF(Ptr.getValueType());
4782 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4787 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4788 SDValue Offset, ISD::MemIndexedMode AM) {
4789 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4790 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4791 "Load is already a indexed load!");
4792 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4793 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4794 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4795 false, LD->getAlignment());
4798 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4799 SDValue Ptr, MachinePointerInfo PtrInfo,
4800 bool isVolatile, bool isNonTemporal,
4801 unsigned Alignment, const AAMDNodes &AAInfo) {
4802 assert(Chain.getValueType() == MVT::Other &&
4803 "Invalid chain type");
4804 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4805 Alignment = getEVTAlignment(Val.getValueType());
4807 unsigned Flags = MachineMemOperand::MOStore;
4809 Flags |= MachineMemOperand::MOVolatile;
4811 Flags |= MachineMemOperand::MONonTemporal;
4813 if (PtrInfo.V.isNull())
4814 PtrInfo = InferPointerInfo(Ptr);
4816 MachineFunction &MF = getMachineFunction();
4817 MachineMemOperand *MMO =
4818 MF.getMachineMemOperand(PtrInfo, Flags,
4819 Val.getValueType().getStoreSize(), Alignment,
4822 return getStore(Chain, dl, Val, Ptr, MMO);
4825 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4826 SDValue Ptr, MachineMemOperand *MMO) {
4827 assert(Chain.getValueType() == MVT::Other &&
4828 "Invalid chain type");
4829 EVT VT = Val.getValueType();
4830 SDVTList VTs = getVTList(MVT::Other);
4831 SDValue Undef = getUNDEF(Ptr.getValueType());
4832 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4833 FoldingSetNodeID ID;
4834 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4835 ID.AddInteger(VT.getRawBits());
4836 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4837 MMO->isNonTemporal(), MMO->isInvariant()));
4838 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4840 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4841 cast<StoreSDNode>(E)->refineAlignment(MMO);
4842 return SDValue(E, 0);
4844 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4845 dl.getDebugLoc(), VTs,
4846 ISD::UNINDEXED, false, VT, MMO);
4847 CSEMap.InsertNode(N, IP);
4849 return SDValue(N, 0);
4852 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4853 SDValue Ptr, MachinePointerInfo PtrInfo,
4854 EVT SVT,bool isVolatile, bool isNonTemporal,
4856 const AAMDNodes &AAInfo) {
4857 assert(Chain.getValueType() == MVT::Other &&
4858 "Invalid chain type");
4859 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4860 Alignment = getEVTAlignment(SVT);
4862 unsigned Flags = MachineMemOperand::MOStore;
4864 Flags |= MachineMemOperand::MOVolatile;
4866 Flags |= MachineMemOperand::MONonTemporal;
4868 if (PtrInfo.V.isNull())
4869 PtrInfo = InferPointerInfo(Ptr);
4871 MachineFunction &MF = getMachineFunction();
4872 MachineMemOperand *MMO =
4873 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4876 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4879 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4880 SDValue Ptr, EVT SVT,
4881 MachineMemOperand *MMO) {
4882 EVT VT = Val.getValueType();
4884 assert(Chain.getValueType() == MVT::Other &&
4885 "Invalid chain type");
4887 return getStore(Chain, dl, Val, Ptr, MMO);
4889 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4890 "Should only be a truncating store, not extending!");
4891 assert(VT.isInteger() == SVT.isInteger() &&
4892 "Can't do FP-INT conversion!");
4893 assert(VT.isVector() == SVT.isVector() &&
4894 "Cannot use trunc store to convert to or from a vector!");
4895 assert((!VT.isVector() ||
4896 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4897 "Cannot use trunc store to change the number of vector elements!");
4899 SDVTList VTs = getVTList(MVT::Other);
4900 SDValue Undef = getUNDEF(Ptr.getValueType());
4901 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4902 FoldingSetNodeID ID;
4903 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4904 ID.AddInteger(SVT.getRawBits());
4905 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4906 MMO->isNonTemporal(), MMO->isInvariant()));
4907 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4909 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4910 cast<StoreSDNode>(E)->refineAlignment(MMO);
4911 return SDValue(E, 0);
4913 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4914 dl.getDebugLoc(), VTs,
4915 ISD::UNINDEXED, true, SVT, MMO);
4916 CSEMap.InsertNode(N, IP);
4918 return SDValue(N, 0);
4922 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4923 SDValue Offset, ISD::MemIndexedMode AM) {
4924 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4925 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4926 "Store is already a indexed store!");
4927 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4928 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4929 FoldingSetNodeID ID;
4930 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4931 ID.AddInteger(ST->getMemoryVT().getRawBits());
4932 ID.AddInteger(ST->getRawSubclassData());
4933 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4935 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4936 return SDValue(E, 0);
4938 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4939 dl.getDebugLoc(), VTs, AM,
4940 ST->isTruncatingStore(),
4942 ST->getMemOperand());
4943 CSEMap.InsertNode(N, IP);
4945 return SDValue(N, 0);
4948 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4949 SDValue Chain, SDValue Ptr,
4952 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4953 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4956 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4957 ArrayRef<SDUse> Ops) {
4958 switch (Ops.size()) {
4959 case 0: return getNode(Opcode, DL, VT);
4960 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4961 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4962 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4966 // Copy from an SDUse array into an SDValue array for use with
4967 // the regular getNode logic.
4968 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4969 return getNode(Opcode, DL, VT, NewOps);
4972 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4973 ArrayRef<SDValue> Ops) {
4974 unsigned NumOps = Ops.size();
4976 case 0: return getNode(Opcode, DL, VT);
4977 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4978 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4979 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4985 case ISD::SELECT_CC: {
4986 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4987 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4988 "LHS and RHS of condition must have same type!");
4989 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4990 "True and False arms of SelectCC must have same type!");
4991 assert(Ops[2].getValueType() == VT &&
4992 "select_cc node must be of same type as true and false value!");
4996 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4997 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4998 "LHS/RHS of comparison should match types!");
5005 SDVTList VTs = getVTList(VT);
5007 if (VT != MVT::Glue) {
5008 FoldingSetNodeID ID;
5009 AddNodeIDNode(ID, Opcode, VTs, Ops);
5012 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5013 return SDValue(E, 0);
5015 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5017 CSEMap.InsertNode(N, IP);
5019 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5024 return SDValue(N, 0);
5027 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5028 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5029 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5032 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5033 ArrayRef<SDValue> Ops) {
5034 if (VTList.NumVTs == 1)
5035 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5039 // FIXME: figure out how to safely handle things like
5040 // int foo(int x) { return 1 << (x & 255); }
5041 // int bar() { return foo(256); }
5042 case ISD::SRA_PARTS:
5043 case ISD::SRL_PARTS:
5044 case ISD::SHL_PARTS:
5045 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5046 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5047 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5048 else if (N3.getOpcode() == ISD::AND)
5049 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5050 // If the and is only masking out bits that cannot effect the shift,
5051 // eliminate the and.
5052 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5053 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5054 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5060 // Memoize the node unless it returns a flag.
5062 unsigned NumOps = Ops.size();
5063 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5064 FoldingSetNodeID ID;
5065 AddNodeIDNode(ID, Opcode, VTList, Ops);
5067 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5068 return SDValue(E, 0);
5071 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5072 DL.getDebugLoc(), VTList, Ops[0]);
5073 } else if (NumOps == 2) {
5074 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5075 DL.getDebugLoc(), VTList, Ops[0],
5077 } else if (NumOps == 3) {
5078 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5079 DL.getDebugLoc(), VTList, Ops[0],
5082 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5085 CSEMap.InsertNode(N, IP);
5088 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5089 DL.getDebugLoc(), VTList, Ops[0]);
5090 } else if (NumOps == 2) {
5091 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5092 DL.getDebugLoc(), VTList, Ops[0],
5094 } else if (NumOps == 3) {
5095 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5096 DL.getDebugLoc(), VTList, Ops[0],
5099 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5104 return SDValue(N, 0);
5107 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5108 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5111 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5113 SDValue Ops[] = { N1 };
5114 return getNode(Opcode, DL, VTList, Ops);
5117 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5118 SDValue N1, SDValue N2) {
5119 SDValue Ops[] = { N1, N2 };
5120 return getNode(Opcode, DL, VTList, Ops);
5123 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5124 SDValue N1, SDValue N2, SDValue N3) {
5125 SDValue Ops[] = { N1, N2, N3 };
5126 return getNode(Opcode, DL, VTList, Ops);
5129 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5130 SDValue N1, SDValue N2, SDValue N3,
5132 SDValue Ops[] = { N1, N2, N3, N4 };
5133 return getNode(Opcode, DL, VTList, Ops);
5136 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5137 SDValue N1, SDValue N2, SDValue N3,
5138 SDValue N4, SDValue N5) {
5139 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5140 return getNode(Opcode, DL, VTList, Ops);
5143 SDVTList SelectionDAG::getVTList(EVT VT) {
5144 return makeVTList(SDNode::getValueTypeList(VT), 1);
5147 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5148 FoldingSetNodeID ID;
5150 ID.AddInteger(VT1.getRawBits());
5151 ID.AddInteger(VT2.getRawBits());
5154 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5156 EVT *Array = Allocator.Allocate<EVT>(2);
5159 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5160 VTListMap.InsertNode(Result, IP);
5162 return Result->getSDVTList();
5165 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5166 FoldingSetNodeID ID;
5168 ID.AddInteger(VT1.getRawBits());
5169 ID.AddInteger(VT2.getRawBits());
5170 ID.AddInteger(VT3.getRawBits());
5173 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5175 EVT *Array = Allocator.Allocate<EVT>(3);
5179 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5180 VTListMap.InsertNode(Result, IP);
5182 return Result->getSDVTList();
5185 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5186 FoldingSetNodeID ID;
5188 ID.AddInteger(VT1.getRawBits());
5189 ID.AddInteger(VT2.getRawBits());
5190 ID.AddInteger(VT3.getRawBits());
5191 ID.AddInteger(VT4.getRawBits());
5194 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5196 EVT *Array = Allocator.Allocate<EVT>(4);
5201 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5202 VTListMap.InsertNode(Result, IP);
5204 return Result->getSDVTList();
5207 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5208 unsigned NumVTs = VTs.size();
5209 FoldingSetNodeID ID;
5210 ID.AddInteger(NumVTs);
5211 for (unsigned index = 0; index < NumVTs; index++) {
5212 ID.AddInteger(VTs[index].getRawBits());
5216 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5218 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5219 std::copy(VTs.begin(), VTs.end(), Array);
5220 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5221 VTListMap.InsertNode(Result, IP);
5223 return Result->getSDVTList();
5227 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5228 /// specified operands. If the resultant node already exists in the DAG,
5229 /// this does not modify the specified node, instead it returns the node that
5230 /// already exists. If the resultant node does not exist in the DAG, the
5231 /// input node is returned. As a degenerate case, if you specify the same
5232 /// input operands as the node already has, the input node is returned.
5233 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5234 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5236 // Check to see if there is no change.
5237 if (Op == N->getOperand(0)) return N;
5239 // See if the modified node already exists.
5240 void *InsertPos = nullptr;
5241 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5244 // Nope it doesn't. Remove the node from its current place in the maps.
5246 if (!RemoveNodeFromCSEMaps(N))
5247 InsertPos = nullptr;
5249 // Now we update the operands.
5250 N->OperandList[0].set(Op);
5252 // If this gets put into a CSE map, add it.
5253 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5257 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5258 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5260 // Check to see if there is no change.
5261 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5262 return N; // No operands changed, just return the input node.
5264 // See if the modified node already exists.
5265 void *InsertPos = nullptr;
5266 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5269 // Nope it doesn't. Remove the node from its current place in the maps.
5271 if (!RemoveNodeFromCSEMaps(N))
5272 InsertPos = nullptr;
5274 // Now we update the operands.
5275 if (N->OperandList[0] != Op1)
5276 N->OperandList[0].set(Op1);
5277 if (N->OperandList[1] != Op2)
5278 N->OperandList[1].set(Op2);
5280 // If this gets put into a CSE map, add it.
5281 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5285 SDNode *SelectionDAG::
5286 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5287 SDValue Ops[] = { Op1, Op2, Op3 };
5288 return UpdateNodeOperands(N, Ops);
5291 SDNode *SelectionDAG::
5292 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5293 SDValue Op3, SDValue Op4) {
5294 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5295 return UpdateNodeOperands(N, Ops);
5298 SDNode *SelectionDAG::
5299 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5300 SDValue Op3, SDValue Op4, SDValue Op5) {
5301 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5302 return UpdateNodeOperands(N, Ops);
5305 SDNode *SelectionDAG::
5306 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5307 unsigned NumOps = Ops.size();
5308 assert(N->getNumOperands() == NumOps &&
5309 "Update with wrong number of operands");
5311 // Check to see if there is no change.
5312 bool AnyChange = false;
5313 for (unsigned i = 0; i != NumOps; ++i) {
5314 if (Ops[i] != N->getOperand(i)) {
5320 // No operands changed, just return the input node.
5321 if (!AnyChange) return N;
5323 // See if the modified node already exists.
5324 void *InsertPos = nullptr;
5325 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5328 // Nope it doesn't. Remove the node from its current place in the maps.
5330 if (!RemoveNodeFromCSEMaps(N))
5331 InsertPos = nullptr;
5333 // Now we update the operands.
5334 for (unsigned i = 0; i != NumOps; ++i)
5335 if (N->OperandList[i] != Ops[i])
5336 N->OperandList[i].set(Ops[i]);
5338 // If this gets put into a CSE map, add it.
5339 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5343 /// DropOperands - Release the operands and set this node to have
5345 void SDNode::DropOperands() {
5346 // Unlike the code in MorphNodeTo that does this, we don't need to
5347 // watch for dead nodes here.
5348 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5354 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5357 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5359 SDVTList VTs = getVTList(VT);
5360 return SelectNodeTo(N, MachineOpc, VTs, None);
5363 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5364 EVT VT, SDValue Op1) {
5365 SDVTList VTs = getVTList(VT);
5366 SDValue Ops[] = { Op1 };
5367 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5370 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5371 EVT VT, SDValue Op1,
5373 SDVTList VTs = getVTList(VT);
5374 SDValue Ops[] = { Op1, Op2 };
5375 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5378 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5379 EVT VT, SDValue Op1,
5380 SDValue Op2, SDValue Op3) {
5381 SDVTList VTs = getVTList(VT);
5382 SDValue Ops[] = { Op1, Op2, Op3 };
5383 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5386 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5387 EVT VT, ArrayRef<SDValue> Ops) {
5388 SDVTList VTs = getVTList(VT);
5389 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5392 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5393 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5394 SDVTList VTs = getVTList(VT1, VT2);
5395 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5398 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5400 SDVTList VTs = getVTList(VT1, VT2);
5401 return SelectNodeTo(N, MachineOpc, VTs, None);
5404 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5405 EVT VT1, EVT VT2, EVT VT3,
5406 ArrayRef<SDValue> Ops) {
5407 SDVTList VTs = getVTList(VT1, VT2, VT3);
5408 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5411 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5412 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5413 ArrayRef<SDValue> Ops) {
5414 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5415 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5418 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5421 SDVTList VTs = getVTList(VT1, VT2);
5422 SDValue Ops[] = { Op1 };
5423 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5426 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5428 SDValue Op1, SDValue Op2) {
5429 SDVTList VTs = getVTList(VT1, VT2);
5430 SDValue Ops[] = { Op1, Op2 };
5431 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5434 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5436 SDValue Op1, SDValue Op2,
5438 SDVTList VTs = getVTList(VT1, VT2);
5439 SDValue Ops[] = { Op1, Op2, Op3 };
5440 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5443 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5444 EVT VT1, EVT VT2, EVT VT3,
5445 SDValue Op1, SDValue Op2,
5447 SDVTList VTs = getVTList(VT1, VT2, VT3);
5448 SDValue Ops[] = { Op1, Op2, Op3 };
5449 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5452 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5453 SDVTList VTs,ArrayRef<SDValue> Ops) {
5454 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5455 // Reset the NodeID to -1.
5460 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5461 /// the line number information on the merged node since it is not possible to
5462 /// preserve the information that operation is associated with multiple lines.
5463 /// This will make the debugger working better at -O0, were there is a higher
5464 /// probability having other instructions associated with that line.
5466 /// For IROrder, we keep the smaller of the two
5467 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5468 DebugLoc NLoc = N->getDebugLoc();
5469 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5470 (OLoc.getDebugLoc() != NLoc)) {
5471 N->setDebugLoc(DebugLoc());
5473 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5474 N->setIROrder(Order);
5478 /// MorphNodeTo - This *mutates* the specified node to have the specified
5479 /// return type, opcode, and operands.
5481 /// Note that MorphNodeTo returns the resultant node. If there is already a
5482 /// node of the specified opcode and operands, it returns that node instead of
5483 /// the current one. Note that the SDLoc need not be the same.
5485 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5486 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5487 /// node, and because it doesn't require CSE recalculation for any of
5488 /// the node's users.
5490 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5491 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5492 /// the legalizer which maintain worklists that would need to be updated when
5493 /// deleting things.
5494 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5495 SDVTList VTs, ArrayRef<SDValue> Ops) {
5496 unsigned NumOps = Ops.size();
5497 // If an identical node already exists, use it.
5499 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5500 FoldingSetNodeID ID;
5501 AddNodeIDNode(ID, Opc, VTs, Ops);
5502 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5503 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5506 if (!RemoveNodeFromCSEMaps(N))
5509 // Start the morphing.
5511 N->ValueList = VTs.VTs;
5512 N->NumValues = VTs.NumVTs;
5514 // Clear the operands list, updating used nodes to remove this from their
5515 // use list. Keep track of any operands that become dead as a result.
5516 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5517 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5519 SDNode *Used = Use.getNode();
5521 if (Used->use_empty())
5522 DeadNodeSet.insert(Used);
5525 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5526 // Initialize the memory references information.
5527 MN->setMemRefs(nullptr, nullptr);
5528 // If NumOps is larger than the # of operands we can have in a
5529 // MachineSDNode, reallocate the operand list.
5530 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5531 if (MN->OperandsNeedDelete)
5532 delete[] MN->OperandList;
5533 if (NumOps > array_lengthof(MN->LocalOperands))
5534 // We're creating a final node that will live unmorphed for the
5535 // remainder of the current SelectionDAG iteration, so we can allocate
5536 // the operands directly out of a pool with no recycling metadata.
5537 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5538 Ops.data(), NumOps);
5540 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5541 MN->OperandsNeedDelete = false;
5543 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5545 // If NumOps is larger than the # of operands we currently have, reallocate
5546 // the operand list.
5547 if (NumOps > N->NumOperands) {
5548 if (N->OperandsNeedDelete)
5549 delete[] N->OperandList;
5550 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5551 N->OperandsNeedDelete = true;
5553 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5556 // Delete any nodes that are still dead after adding the uses for the
5558 if (!DeadNodeSet.empty()) {
5559 SmallVector<SDNode *, 16> DeadNodes;
5560 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5561 E = DeadNodeSet.end(); I != E; ++I)
5562 if ((*I)->use_empty())
5563 DeadNodes.push_back(*I);
5564 RemoveDeadNodes(DeadNodes);
5568 CSEMap.InsertNode(N, IP); // Memoize the new node.
5573 /// getMachineNode - These are used for target selectors to create a new node
5574 /// with specified return type(s), MachineInstr opcode, and operands.
5576 /// Note that getMachineNode returns the resultant node. If there is already a
5577 /// node of the specified opcode and operands, it returns that node instead of
5578 /// the current one.
5580 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5581 SDVTList VTs = getVTList(VT);
5582 return getMachineNode(Opcode, dl, VTs, None);
5586 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5587 SDVTList VTs = getVTList(VT);
5588 SDValue Ops[] = { Op1 };
5589 return getMachineNode(Opcode, dl, VTs, Ops);
5593 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5594 SDValue Op1, SDValue Op2) {
5595 SDVTList VTs = getVTList(VT);
5596 SDValue Ops[] = { Op1, Op2 };
5597 return getMachineNode(Opcode, dl, VTs, Ops);
5601 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5602 SDValue Op1, SDValue Op2, SDValue Op3) {
5603 SDVTList VTs = getVTList(VT);
5604 SDValue Ops[] = { Op1, Op2, Op3 };
5605 return getMachineNode(Opcode, dl, VTs, Ops);
5609 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5610 ArrayRef<SDValue> Ops) {
5611 SDVTList VTs = getVTList(VT);
5612 return getMachineNode(Opcode, dl, VTs, Ops);
5616 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5617 SDVTList VTs = getVTList(VT1, VT2);
5618 return getMachineNode(Opcode, dl, VTs, None);
5622 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5623 EVT VT1, EVT VT2, SDValue Op1) {
5624 SDVTList VTs = getVTList(VT1, VT2);
5625 SDValue Ops[] = { Op1 };
5626 return getMachineNode(Opcode, dl, VTs, Ops);
5630 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5631 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5632 SDVTList VTs = getVTList(VT1, VT2);
5633 SDValue Ops[] = { Op1, Op2 };
5634 return getMachineNode(Opcode, dl, VTs, Ops);
5638 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5639 EVT VT1, EVT VT2, SDValue Op1,
5640 SDValue Op2, SDValue Op3) {
5641 SDVTList VTs = getVTList(VT1, VT2);
5642 SDValue Ops[] = { Op1, Op2, Op3 };
5643 return getMachineNode(Opcode, dl, VTs, Ops);
5647 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5649 ArrayRef<SDValue> Ops) {
5650 SDVTList VTs = getVTList(VT1, VT2);
5651 return getMachineNode(Opcode, dl, VTs, Ops);
5655 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5656 EVT VT1, EVT VT2, EVT VT3,
5657 SDValue Op1, SDValue Op2) {
5658 SDVTList VTs = getVTList(VT1, VT2, VT3);
5659 SDValue Ops[] = { Op1, Op2 };
5660 return getMachineNode(Opcode, dl, VTs, Ops);
5664 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5665 EVT VT1, EVT VT2, EVT VT3,
5666 SDValue Op1, SDValue Op2, SDValue Op3) {
5667 SDVTList VTs = getVTList(VT1, VT2, VT3);
5668 SDValue Ops[] = { Op1, Op2, Op3 };
5669 return getMachineNode(Opcode, dl, VTs, Ops);
5673 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5674 EVT VT1, EVT VT2, EVT VT3,
5675 ArrayRef<SDValue> Ops) {
5676 SDVTList VTs = getVTList(VT1, VT2, VT3);
5677 return getMachineNode(Opcode, dl, VTs, Ops);
5681 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5682 EVT VT2, EVT VT3, EVT VT4,
5683 ArrayRef<SDValue> Ops) {
5684 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5685 return getMachineNode(Opcode, dl, VTs, Ops);
5689 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5690 ArrayRef<EVT> ResultTys,
5691 ArrayRef<SDValue> Ops) {
5692 SDVTList VTs = getVTList(ResultTys);
5693 return getMachineNode(Opcode, dl, VTs, Ops);
5697 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5698 ArrayRef<SDValue> OpsArray) {
5699 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5702 const SDValue *Ops = OpsArray.data();
5703 unsigned NumOps = OpsArray.size();
5706 FoldingSetNodeID ID;
5707 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5709 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5710 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5714 // Allocate a new MachineSDNode.
5715 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5716 DL.getDebugLoc(), VTs);
5718 // Initialize the operands list.
5719 if (NumOps > array_lengthof(N->LocalOperands))
5720 // We're creating a final node that will live unmorphed for the
5721 // remainder of the current SelectionDAG iteration, so we can allocate
5722 // the operands directly out of a pool with no recycling metadata.
5723 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5726 N->InitOperands(N->LocalOperands, Ops, NumOps);
5727 N->OperandsNeedDelete = false;
5730 CSEMap.InsertNode(N, IP);
5736 /// getTargetExtractSubreg - A convenience function for creating
5737 /// TargetOpcode::EXTRACT_SUBREG nodes.
5739 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5741 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5742 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5743 VT, Operand, SRIdxVal);
5744 return SDValue(Subreg, 0);
5747 /// getTargetInsertSubreg - A convenience function for creating
5748 /// TargetOpcode::INSERT_SUBREG nodes.
5750 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5751 SDValue Operand, SDValue Subreg) {
5752 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5753 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5754 VT, Operand, Subreg, SRIdxVal);
5755 return SDValue(Result, 0);
5758 /// getNodeIfExists - Get the specified node if it's already available, or
5759 /// else return NULL.
5760 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5761 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5763 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5764 FoldingSetNodeID ID;
5765 AddNodeIDNode(ID, Opcode, VTList, Ops);
5766 if (isBinOpWithFlags(Opcode))
5767 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5769 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5775 /// getDbgValue - Creates a SDDbgValue node.
5779 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5780 bool IsIndirect, uint64_t Off,
5781 DebugLoc DL, unsigned O) {
5782 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5787 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5789 DebugLoc DL, unsigned O) {
5790 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5795 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5796 DebugLoc DL, unsigned O) {
5797 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5802 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5803 /// pointed to by a use iterator is deleted, increment the use iterator
5804 /// so that it doesn't dangle.
5806 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5807 SDNode::use_iterator &UI;
5808 SDNode::use_iterator &UE;
5810 void NodeDeleted(SDNode *N, SDNode *E) override {
5811 // Increment the iterator as needed.
5812 while (UI != UE && N == *UI)
5817 RAUWUpdateListener(SelectionDAG &d,
5818 SDNode::use_iterator &ui,
5819 SDNode::use_iterator &ue)
5820 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5825 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5826 /// This can cause recursive merging of nodes in the DAG.
5828 /// This version assumes From has a single result value.
5830 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5831 SDNode *From = FromN.getNode();
5832 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5833 "Cannot replace with this method!");
5834 assert(From != To.getNode() && "Cannot replace uses of with self");
5836 // Iterate over all the existing uses of From. New uses will be added
5837 // to the beginning of the use list, which we avoid visiting.
5838 // This specifically avoids visiting uses of From that arise while the
5839 // replacement is happening, because any such uses would be the result
5840 // of CSE: If an existing node looks like From after one of its operands
5841 // is replaced by To, we don't want to replace of all its users with To
5842 // too. See PR3018 for more info.
5843 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5844 RAUWUpdateListener Listener(*this, UI, UE);
5848 // This node is about to morph, remove its old self from the CSE maps.
5849 RemoveNodeFromCSEMaps(User);
5851 // A user can appear in a use list multiple times, and when this
5852 // happens the uses are usually next to each other in the list.
5853 // To help reduce the number of CSE recomputations, process all
5854 // the uses of this user that we can find this way.
5856 SDUse &Use = UI.getUse();
5859 } while (UI != UE && *UI == User);
5861 // Now that we have modified User, add it back to the CSE maps. If it
5862 // already exists there, recursively merge the results together.
5863 AddModifiedNodeToCSEMaps(User);
5866 // If we just RAUW'd the root, take note.
5867 if (FromN == getRoot())
5871 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5872 /// This can cause recursive merging of nodes in the DAG.
5874 /// This version assumes that for each value of From, there is a
5875 /// corresponding value in To in the same position with the same type.
5877 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5879 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5880 assert((!From->hasAnyUseOfValue(i) ||
5881 From->getValueType(i) == To->getValueType(i)) &&
5882 "Cannot use this version of ReplaceAllUsesWith!");
5885 // Handle the trivial case.
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();
5907 } while (UI != UE && *UI == User);
5909 // Now that we have modified User, add it back to the CSE maps. If it
5910 // already exists there, recursively merge the results together.
5911 AddModifiedNodeToCSEMaps(User);
5914 // If we just RAUW'd the root, take note.
5915 if (From == getRoot().getNode())
5916 setRoot(SDValue(To, getRoot().getResNo()));
5919 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5920 /// This can cause recursive merging of nodes in the DAG.
5922 /// This version can replace From with any result values. To must match the
5923 /// number and types of values returned by From.
5924 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5925 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5926 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5928 // Iterate over just the existing users of From. See the comments in
5929 // the ReplaceAllUsesWith above.
5930 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5931 RAUWUpdateListener Listener(*this, UI, UE);
5935 // This node is about to morph, remove its old self from the CSE maps.
5936 RemoveNodeFromCSEMaps(User);
5938 // A user can appear in a use list multiple times, and when this
5939 // happens the uses are usually next to each other in the list.
5940 // To help reduce the number of CSE recomputations, process all
5941 // the uses of this user that we can find this way.
5943 SDUse &Use = UI.getUse();
5944 const SDValue &ToOp = To[Use.getResNo()];
5947 } while (UI != UE && *UI == User);
5949 // Now that we have modified User, add it back to the CSE maps. If it
5950 // already exists there, recursively merge the results together.
5951 AddModifiedNodeToCSEMaps(User);
5954 // If we just RAUW'd the root, take note.
5955 if (From == getRoot().getNode())
5956 setRoot(SDValue(To[getRoot().getResNo()]));
5959 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5960 /// uses of other values produced by From.getNode() alone. The Deleted
5961 /// vector is handled the same way as for ReplaceAllUsesWith.
5962 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5963 // Handle the really simple, really trivial case efficiently.
5964 if (From == To) return;
5966 // Handle the simple, trivial, case efficiently.
5967 if (From.getNode()->getNumValues() == 1) {
5968 ReplaceAllUsesWith(From, To);
5972 // Iterate over just the existing users of From. See the comments in
5973 // the ReplaceAllUsesWith above.
5974 SDNode::use_iterator UI = From.getNode()->use_begin(),
5975 UE = From.getNode()->use_end();
5976 RAUWUpdateListener Listener(*this, UI, UE);
5979 bool UserRemovedFromCSEMaps = false;
5981 // A user can appear in a use list multiple times, and when this
5982 // happens the uses are usually next to each other in the list.
5983 // To help reduce the number of CSE recomputations, process all
5984 // the uses of this user that we can find this way.
5986 SDUse &Use = UI.getUse();
5988 // Skip uses of different values from the same node.
5989 if (Use.getResNo() != From.getResNo()) {
5994 // If this node hasn't been modified yet, it's still in the CSE maps,
5995 // so remove its old self from the CSE maps.
5996 if (!UserRemovedFromCSEMaps) {
5997 RemoveNodeFromCSEMaps(User);
5998 UserRemovedFromCSEMaps = true;
6003 } while (UI != UE && *UI == User);
6005 // We are iterating over all uses of the From node, so if a use
6006 // doesn't use the specific value, no changes are made.
6007 if (!UserRemovedFromCSEMaps)
6010 // Now that we have modified User, add it back to the CSE maps. If it
6011 // already exists there, recursively merge the results together.
6012 AddModifiedNodeToCSEMaps(User);
6015 // If we just RAUW'd the root, take note.
6016 if (From == getRoot())
6021 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6022 /// to record information about a use.
6029 /// operator< - Sort Memos by User.
6030 bool operator<(const UseMemo &L, const UseMemo &R) {
6031 return (intptr_t)L.User < (intptr_t)R.User;
6035 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6036 /// uses of other values produced by From.getNode() alone. The same value
6037 /// may appear in both the From and To list. The Deleted vector is
6038 /// handled the same way as for ReplaceAllUsesWith.
6039 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6042 // Handle the simple, trivial case efficiently.
6044 return ReplaceAllUsesOfValueWith(*From, *To);
6046 // Read up all the uses and make records of them. This helps
6047 // processing new uses that are introduced during the
6048 // replacement process.
6049 SmallVector<UseMemo, 4> Uses;
6050 for (unsigned i = 0; i != Num; ++i) {
6051 unsigned FromResNo = From[i].getResNo();
6052 SDNode *FromNode = From[i].getNode();
6053 for (SDNode::use_iterator UI = FromNode->use_begin(),
6054 E = FromNode->use_end(); UI != E; ++UI) {
6055 SDUse &Use = UI.getUse();
6056 if (Use.getResNo() == FromResNo) {
6057 UseMemo Memo = { *UI, i, &Use };
6058 Uses.push_back(Memo);
6063 // Sort the uses, so that all the uses from a given User are together.
6064 std::sort(Uses.begin(), Uses.end());
6066 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6067 UseIndex != UseIndexEnd; ) {
6068 // We know that this user uses some value of From. If it is the right
6069 // value, update it.
6070 SDNode *User = Uses[UseIndex].User;
6072 // This node is about to morph, remove its old self from the CSE maps.
6073 RemoveNodeFromCSEMaps(User);
6075 // The Uses array is sorted, so all the uses for a given User
6076 // are next to each other in the list.
6077 // To help reduce the number of CSE recomputations, process all
6078 // the uses of this user that we can find this way.
6080 unsigned i = Uses[UseIndex].Index;
6081 SDUse &Use = *Uses[UseIndex].Use;
6085 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6087 // Now that we have modified User, add it back to the CSE maps. If it
6088 // already exists there, recursively merge the results together.
6089 AddModifiedNodeToCSEMaps(User);
6093 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6094 /// based on their topological order. It returns the maximum id and a vector
6095 /// of the SDNodes* in assigned order by reference.
6096 unsigned SelectionDAG::AssignTopologicalOrder() {
6098 unsigned DAGSize = 0;
6100 // SortedPos tracks the progress of the algorithm. Nodes before it are
6101 // sorted, nodes after it are unsorted. When the algorithm completes
6102 // it is at the end of the list.
6103 allnodes_iterator SortedPos = allnodes_begin();
6105 // Visit all the nodes. Move nodes with no operands to the front of
6106 // the list immediately. Annotate nodes that do have operands with their
6107 // operand count. Before we do this, the Node Id fields of the nodes
6108 // may contain arbitrary values. After, the Node Id fields for nodes
6109 // before SortedPos will contain the topological sort index, and the
6110 // Node Id fields for nodes At SortedPos and after will contain the
6111 // count of outstanding operands.
6112 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6114 checkForCycles(N, this);
6115 unsigned Degree = N->getNumOperands();
6117 // A node with no uses, add it to the result array immediately.
6118 N->setNodeId(DAGSize++);
6119 allnodes_iterator Q = N;
6121 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6122 assert(SortedPos != AllNodes.end() && "Overran node list");
6125 // Temporarily use the Node Id as scratch space for the degree count.
6126 N->setNodeId(Degree);
6130 // Visit all the nodes. As we iterate, move nodes into sorted order,
6131 // such that by the time the end is reached all nodes will be sorted.
6132 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6134 checkForCycles(N, this);
6135 // N is in sorted position, so all its uses have one less operand
6136 // that needs to be sorted.
6137 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6140 unsigned Degree = P->getNodeId();
6141 assert(Degree != 0 && "Invalid node degree");
6144 // All of P's operands are sorted, so P may sorted now.
6145 P->setNodeId(DAGSize++);
6147 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6148 assert(SortedPos != AllNodes.end() && "Overran node list");
6151 // Update P's outstanding operand count.
6152 P->setNodeId(Degree);
6155 if (I == SortedPos) {
6158 dbgs() << "Overran sorted position:\n";
6159 S->dumprFull(this); dbgs() << "\n";
6160 dbgs() << "Checking if this is due to cycles\n";
6161 checkForCycles(this, true);
6163 llvm_unreachable(nullptr);
6167 assert(SortedPos == AllNodes.end() &&
6168 "Topological sort incomplete!");
6169 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6170 "First node in topological sort is not the entry token!");
6171 assert(AllNodes.front().getNodeId() == 0 &&
6172 "First node in topological sort has non-zero id!");
6173 assert(AllNodes.front().getNumOperands() == 0 &&
6174 "First node in topological sort has operands!");
6175 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6176 "Last node in topologic sort has unexpected id!");
6177 assert(AllNodes.back().use_empty() &&
6178 "Last node in topologic sort has users!");
6179 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6183 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6184 /// value is produced by SD.
6185 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6186 DbgInfo->add(DB, SD, isParameter);
6188 SD->setHasDebugValue(true);
6191 /// TransferDbgValues - Transfer SDDbgValues.
6192 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6193 if (From == To || !From.getNode()->getHasDebugValue())
6195 SDNode *FromNode = From.getNode();
6196 SDNode *ToNode = To.getNode();
6197 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6198 SmallVector<SDDbgValue *, 2> ClonedDVs;
6199 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6201 SDDbgValue *Dbg = *I;
6202 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6203 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6205 Dbg->getOffset(), Dbg->getDebugLoc(),
6207 ClonedDVs.push_back(Clone);
6210 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6211 E = ClonedDVs.end(); I != E; ++I)
6212 AddDbgValue(*I, ToNode, false);
6215 //===----------------------------------------------------------------------===//
6217 //===----------------------------------------------------------------------===//
6219 HandleSDNode::~HandleSDNode() {
6223 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6224 DebugLoc DL, const GlobalValue *GA,
6225 EVT VT, int64_t o, unsigned char TF)
6226 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6230 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6231 SDValue X, unsigned SrcAS,
6233 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6234 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6236 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6237 EVT memvt, MachineMemOperand *mmo)
6238 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6239 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6240 MMO->isNonTemporal(), MMO->isInvariant());
6241 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6242 assert(isNonTemporal() == MMO->isNonTemporal() &&
6243 "Non-temporal encoding error!");
6244 // We check here that the size of the memory operand fits within the size of
6245 // the MMO. This is because the MMO might indicate only a possible address
6246 // range instead of specifying the affected memory addresses precisely.
6247 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6250 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6251 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6252 : SDNode(Opc, Order, dl, VTs, Ops),
6253 MemoryVT(memvt), MMO(mmo) {
6254 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6255 MMO->isNonTemporal(), MMO->isInvariant());
6256 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6257 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6260 /// Profile - Gather unique data for the node.
6262 void SDNode::Profile(FoldingSetNodeID &ID) const {
6263 AddNodeIDNode(ID, this);
6268 std::vector<EVT> VTs;
6271 VTs.reserve(MVT::LAST_VALUETYPE);
6272 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6273 VTs.push_back(MVT((MVT::SimpleValueType)i));
6278 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6279 static ManagedStatic<EVTArray> SimpleVTArray;
6280 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6282 /// getValueTypeList - Return a pointer to the specified value type.
6284 const EVT *SDNode::getValueTypeList(EVT VT) {
6285 if (VT.isExtended()) {
6286 sys::SmartScopedLock<true> Lock(*VTMutex);
6287 return &(*EVTs->insert(VT).first);
6289 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6290 "Value type out of range!");
6291 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6295 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6296 /// indicated value. This method ignores uses of other values defined by this
6298 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6299 assert(Value < getNumValues() && "Bad value!");
6301 // TODO: Only iterate over uses of a given value of the node
6302 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6303 if (UI.getUse().getResNo() == Value) {
6310 // Found exactly the right number of uses?
6315 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6316 /// value. This method ignores uses of other values defined by this operation.
6317 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6318 assert(Value < getNumValues() && "Bad value!");
6320 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6321 if (UI.getUse().getResNo() == Value)
6328 /// isOnlyUserOf - Return true if this node is the only use of N.
6330 bool SDNode::isOnlyUserOf(SDNode *N) const {
6332 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6343 /// isOperand - Return true if this node is an operand of N.
6345 bool SDValue::isOperandOf(SDNode *N) const {
6346 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6347 if (*this == N->getOperand(i))
6352 bool SDNode::isOperandOf(SDNode *N) const {
6353 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6354 if (this == N->OperandList[i].getNode())
6359 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6360 /// be a chain) reaches the specified operand without crossing any
6361 /// side-effecting instructions on any chain path. In practice, this looks
6362 /// through token factors and non-volatile loads. In order to remain efficient,
6363 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6364 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6365 unsigned Depth) const {
6366 if (*this == Dest) return true;
6368 // Don't search too deeply, we just want to be able to see through
6369 // TokenFactor's etc.
6370 if (Depth == 0) return false;
6372 // If this is a token factor, all inputs to the TF happen in parallel. If any
6373 // of the operands of the TF does not reach dest, then we cannot do the xform.
6374 if (getOpcode() == ISD::TokenFactor) {
6375 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6376 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6381 // Loads don't have side effects, look through them.
6382 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6383 if (!Ld->isVolatile())
6384 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6389 /// hasPredecessor - Return true if N is a predecessor of this node.
6390 /// N is either an operand of this node, or can be reached by recursively
6391 /// traversing up the operands.
6392 /// NOTE: This is an expensive method. Use it carefully.
6393 bool SDNode::hasPredecessor(const SDNode *N) const {
6394 SmallPtrSet<const SDNode *, 32> Visited;
6395 SmallVector<const SDNode *, 16> Worklist;
6396 return hasPredecessorHelper(N, Visited, Worklist);
6400 SDNode::hasPredecessorHelper(const SDNode *N,
6401 SmallPtrSet<const SDNode *, 32> &Visited,
6402 SmallVectorImpl<const SDNode *> &Worklist) const {
6403 if (Visited.empty()) {
6404 Worklist.push_back(this);
6406 // Take a look in the visited set. If we've already encountered this node
6407 // we needn't search further.
6408 if (Visited.count(N))
6412 // Haven't visited N yet. Continue the search.
6413 while (!Worklist.empty()) {
6414 const SDNode *M = Worklist.pop_back_val();
6415 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6416 SDNode *Op = M->getOperand(i).getNode();
6417 if (Visited.insert(Op))
6418 Worklist.push_back(Op);
6427 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6428 assert(Num < NumOperands && "Invalid child # of SDNode!");
6429 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6432 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6433 assert(N->getNumValues() == 1 &&
6434 "Can't unroll a vector with multiple results!");
6436 EVT VT = N->getValueType(0);
6437 unsigned NE = VT.getVectorNumElements();
6438 EVT EltVT = VT.getVectorElementType();
6441 SmallVector<SDValue, 8> Scalars;
6442 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6444 // If ResNE is 0, fully unroll the vector op.
6447 else if (NE > ResNE)
6451 for (i= 0; i != NE; ++i) {
6452 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6453 SDValue Operand = N->getOperand(j);
6454 EVT OperandVT = Operand.getValueType();
6455 if (OperandVT.isVector()) {
6456 // A vector operand; extract a single element.
6457 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
6458 EVT OperandEltVT = OperandVT.getVectorElementType();
6459 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6462 getConstant(i, TLI->getVectorIdxTy()));
6464 // A scalar operand; just use it as is.
6465 Operands[j] = Operand;
6469 switch (N->getOpcode()) {
6471 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6474 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6481 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6482 getShiftAmountOperand(Operands[0].getValueType(),
6485 case ISD::SIGN_EXTEND_INREG:
6486 case ISD::FP_ROUND_INREG: {
6487 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6488 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6490 getValueType(ExtVT)));
6495 for (; i < ResNE; ++i)
6496 Scalars.push_back(getUNDEF(EltVT));
6498 return getNode(ISD::BUILD_VECTOR, dl,
6499 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6503 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6504 /// location that is 'Dist' units away from the location that the 'Base' load
6505 /// is loading from.
6506 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6507 unsigned Bytes, int Dist) const {
6508 if (LD->getChain() != Base->getChain())
6510 EVT VT = LD->getValueType(0);
6511 if (VT.getSizeInBits() / 8 != Bytes)
6514 SDValue Loc = LD->getOperand(1);
6515 SDValue BaseLoc = Base->getOperand(1);
6516 if (Loc.getOpcode() == ISD::FrameIndex) {
6517 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6519 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6520 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6521 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6522 int FS = MFI->getObjectSize(FI);
6523 int BFS = MFI->getObjectSize(BFI);
6524 if (FS != BFS || FS != (int)Bytes) return false;
6525 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6529 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6530 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6533 const GlobalValue *GV1 = nullptr;
6534 const GlobalValue *GV2 = nullptr;
6535 int64_t Offset1 = 0;
6536 int64_t Offset2 = 0;
6537 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
6538 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6539 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6540 if (isGA1 && isGA2 && GV1 == GV2)
6541 return Offset1 == (Offset2 + Dist*Bytes);
6546 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6547 /// it cannot be inferred.
6548 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6549 // If this is a GlobalAddress + cst, return the alignment.
6550 const GlobalValue *GV;
6551 int64_t GVOffset = 0;
6552 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
6553 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6554 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6555 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6556 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6557 TLI->getDataLayout());
6558 unsigned AlignBits = KnownZero.countTrailingOnes();
6559 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6561 return MinAlign(Align, GVOffset);
6564 // If this is a direct reference to a stack slot, use information about the
6565 // stack slot's alignment.
6566 int FrameIdx = 1 << 31;
6567 int64_t FrameOffset = 0;
6568 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6569 FrameIdx = FI->getIndex();
6570 } else if (isBaseWithConstantOffset(Ptr) &&
6571 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6573 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6574 FrameOffset = Ptr.getConstantOperandVal(1);
6577 if (FrameIdx != (1 << 31)) {
6578 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6579 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6587 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6588 /// which is split (or expanded) into two not necessarily identical pieces.
6589 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6590 // Currently all types are split in half.
6592 if (!VT.isVector()) {
6593 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6595 unsigned NumElements = VT.getVectorNumElements();
6596 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6597 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6600 return std::make_pair(LoVT, HiVT);
6603 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6605 std::pair<SDValue, SDValue>
6606 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6608 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6609 N.getValueType().getVectorNumElements() &&
6610 "More vector elements requested than available!");
6612 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6613 getConstant(0, TLI->getVectorIdxTy()));
6614 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6615 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6616 return std::make_pair(Lo, Hi);
6619 void SelectionDAG::ExtractVectorElements(SDValue Op,
6620 SmallVectorImpl<SDValue> &Args,
6621 unsigned Start, unsigned Count) {
6622 EVT VT = Op.getValueType();
6624 Count = VT.getVectorNumElements();
6626 EVT EltVT = VT.getVectorElementType();
6627 EVT IdxTy = TLI->getVectorIdxTy();
6629 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6630 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6631 Op, getConstant(i, IdxTy)));
6635 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6636 unsigned GlobalAddressSDNode::getAddressSpace() const {
6637 return getGlobal()->getType()->getAddressSpace();
6641 Type *ConstantPoolSDNode::getType() const {
6642 if (isMachineConstantPoolEntry())
6643 return Val.MachineCPVal->getType();
6644 return Val.ConstVal->getType();
6647 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6649 unsigned &SplatBitSize,
6651 unsigned MinSplatBits,
6652 bool isBigEndian) const {
6653 EVT VT = getValueType(0);
6654 assert(VT.isVector() && "Expected a vector type");
6655 unsigned sz = VT.getSizeInBits();
6656 if (MinSplatBits > sz)
6659 SplatValue = APInt(sz, 0);
6660 SplatUndef = APInt(sz, 0);
6662 // Get the bits. Bits with undefined values (when the corresponding element
6663 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6664 // in SplatValue. If any of the values are not constant, give up and return
6666 unsigned int nOps = getNumOperands();
6667 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6668 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6670 for (unsigned j = 0; j < nOps; ++j) {
6671 unsigned i = isBigEndian ? nOps-1-j : j;
6672 SDValue OpVal = getOperand(i);
6673 unsigned BitPos = j * EltBitSize;
6675 if (OpVal.getOpcode() == ISD::UNDEF)
6676 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6677 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6678 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6679 zextOrTrunc(sz) << BitPos;
6680 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6681 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6686 // The build_vector is all constants or undefs. Find the smallest element
6687 // size that splats the vector.
6689 HasAnyUndefs = (SplatUndef != 0);
6692 unsigned HalfSize = sz / 2;
6693 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6694 APInt LowValue = SplatValue.trunc(HalfSize);
6695 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6696 APInt LowUndef = SplatUndef.trunc(HalfSize);
6698 // If the two halves do not match (ignoring undef bits), stop here.
6699 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6700 MinSplatBits > HalfSize)
6703 SplatValue = HighValue | LowValue;
6704 SplatUndef = HighUndef & LowUndef;
6713 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6714 if (UndefElements) {
6715 UndefElements->clear();
6716 UndefElements->resize(getNumOperands());
6719 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6720 SDValue Op = getOperand(i);
6721 if (Op.getOpcode() == ISD::UNDEF) {
6723 (*UndefElements)[i] = true;
6724 } else if (!Splatted) {
6726 } else if (Splatted != Op) {
6732 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6733 "Can only have a splat without a constant for all undefs.");
6734 return getOperand(0);
6741 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6742 return dyn_cast_or_null<ConstantSDNode>(
6743 getSplatValue(UndefElements).getNode());
6747 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6748 return dyn_cast_or_null<ConstantFPSDNode>(
6749 getSplatValue(UndefElements).getNode());
6752 bool BuildVectorSDNode::isConstant() const {
6753 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6754 unsigned Opc = getOperand(i).getOpcode();
6755 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6761 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6762 // Find the first non-undef value in the shuffle mask.
6764 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6767 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6769 // Make sure all remaining elements are either undef or the same as the first
6771 for (int Idx = Mask[i]; i != e; ++i)
6772 if (Mask[i] >= 0 && Mask[i] != Idx)
6778 static void checkForCyclesHelper(const SDNode *N,
6779 SmallPtrSet<const SDNode*, 32> &Visited,
6780 SmallPtrSet<const SDNode*, 32> &Checked,
6781 const llvm::SelectionDAG *DAG) {
6782 // If this node has already been checked, don't check it again.
6783 if (Checked.count(N))
6786 // If a node has already been visited on this depth-first walk, reject it as
6788 if (!Visited.insert(N)) {
6789 errs() << "Detected cycle in SelectionDAG\n";
6790 dbgs() << "Offending node:\n";
6791 N->dumprFull(DAG); dbgs() << "\n";
6795 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6796 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6803 void llvm::checkForCycles(const llvm::SDNode *N,
6804 const llvm::SelectionDAG *DAG,
6812 assert(N && "Checking nonexistent SDNode");
6813 SmallPtrSet<const SDNode*, 32> visited;
6814 SmallPtrSet<const SDNode*, 32> checked;
6815 checkForCyclesHelper(N, visited, checked, DAG);
6820 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6821 checkForCycles(DAG->getRoot().getNode(), DAG, force);