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"
54 /// makeVTList - Return an instance of the SDVTList struct initialized with the
55 /// specified members.
56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
57 SDVTList Res = {VTs, NumVTs};
61 // Default null implementations of the callbacks.
62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
65 //===----------------------------------------------------------------------===//
66 // ConstantFPSDNode Class
67 //===----------------------------------------------------------------------===//
69 /// isExactlyValue - We don't rely on operator== working on double values, as
70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
71 /// As such, this method can be used to do an exact bit-for-bit comparison of
72 /// two floating point values.
73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
74 return getValueAPF().bitwiseIsEqual(V);
77 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 assert(VT.isFloatingPoint() && "Can only convert between FP types");
81 // convert modifies in place, so make a copy.
82 APFloat Val2 = APFloat(Val);
84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
85 APFloat::rmNearestTiesToEven,
90 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
94 /// isBuildVectorAllOnes - Return true if the specified node is a
95 /// BUILD_VECTOR where all of the elements are ~0 or undef.
96 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
97 // Look through a bit convert.
98 if (N->getOpcode() == ISD::BITCAST)
99 N = N->getOperand(0).getNode();
101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
103 unsigned i = 0, e = N->getNumOperands();
105 // Skip over all of the undef values.
106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109 // Do not accept an all-undef vector.
110 if (i == e) return false;
112 // Do not accept build_vectors that aren't all constants or which have non-~0
113 // elements. We have to be a bit careful here, as the type of the constant
114 // may not be the same as the type of the vector elements due to type
115 // legalization (the elements are promoted to a legal type for the target and
116 // a vector of a type may be legal when the base element type is not).
117 // We only want to check enough bits to cover the vector elements, because
118 // we care if the resultant vector is all ones, not whether the individual
120 SDValue NotZero = N->getOperand(i);
121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
123 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
131 // Okay, we have at least one ~0 value, check to see if the rest match or are
132 // undefs. Even with the above element type twiddling, this should be OK, as
133 // the same type legalization should have applied to all the elements.
134 for (++i; i != e; ++i)
135 if (N->getOperand(i) != NotZero &&
136 N->getOperand(i).getOpcode() != ISD::UNDEF)
142 /// isBuildVectorAllZeros - Return true if the specified node is a
143 /// BUILD_VECTOR where all of the elements are 0 or undef.
144 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
145 // Look through a bit convert.
146 if (N->getOpcode() == ISD::BITCAST)
147 N = N->getOperand(0).getNode();
149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
151 bool IsAllUndef = true;
152 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
153 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept build_vectors that aren't all constants or which have non-0
157 // elements. We have to be a bit careful here, as the type of the constant
158 // may not be the same as the type of the vector elements due to type
159 // legalization (the elements are promoted to a legal type for the target
160 // and a vector of a type may be legal when the base element type is not).
161 // We only want to check enough bits to cover the vector elements, because
162 // we care if the resultant vector is all zeros, not whether the individual
164 SDValue Zero = N->getOperand(i);
165 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
166 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
167 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
170 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
176 // Do not accept an all-undef vector.
182 /// \brief Return true if the specified node is a BUILD_VECTOR node of
183 /// all ConstantSDNode or undef.
184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
185 if (N->getOpcode() != ISD::BUILD_VECTOR)
188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
189 SDValue Op = N->getOperand(i);
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// isScalarToVector - Return true if the specified node is a
199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
200 /// element is not an undef.
201 bool ISD::isScalarToVector(const SDNode *N) {
202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
205 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 unsigned NumElems = N->getNumOperands();
212 for (unsigned i = 1; i < NumElems; ++i) {
213 SDValue V = N->getOperand(i);
214 if (V.getOpcode() != ISD::UNDEF)
220 /// allOperandsUndef - Return true if the node has at least one operand
221 /// and all operands of the specified node are ISD::UNDEF.
222 bool ISD::allOperandsUndef(const SDNode *N) {
223 // Return false if the node has no operands.
224 // This is "logically inconsistent" with the definition of "all" but
225 // is probably the desired behavior.
226 if (N->getNumOperands() == 0)
229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
230 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
236 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
239 return ISD::ANY_EXTEND;
241 return ISD::SIGN_EXTEND;
243 return ISD::ZERO_EXTEND;
248 llvm_unreachable("Invalid LoadExtType");
251 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
252 /// when given the operation for (X op Y).
253 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
254 // To perform this operation, we just need to swap the L and G bits of the
256 unsigned OldL = (Operation >> 2) & 1;
257 unsigned OldG = (Operation >> 1) & 1;
258 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
259 (OldL << 1) | // New G bit
260 (OldG << 2)); // New L bit.
263 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
264 /// 'op' is a valid SetCC operation.
265 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
266 unsigned Operation = Op;
268 Operation ^= 7; // Flip L, G, E bits, but not U.
270 Operation ^= 15; // Flip all of the condition bits.
272 if (Operation > ISD::SETTRUE2)
273 Operation &= ~8; // Don't let N and U bits get set.
275 return ISD::CondCode(Operation);
279 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
280 /// signed operation and 2 if the result is an unsigned comparison. Return zero
281 /// if the operation does not depend on the sign of the input (setne and seteq).
282 static int isSignedOp(ISD::CondCode Opcode) {
284 default: llvm_unreachable("Illegal integer setcc operation!");
286 case ISD::SETNE: return 0;
290 case ISD::SETGE: return 1;
294 case ISD::SETUGE: return 2;
298 /// getSetCCOrOperation - Return the result of a logical OR between different
299 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
300 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
305 // Cannot fold a signed integer setcc with an unsigned integer setcc.
306 return ISD::SETCC_INVALID;
308 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
310 // If the N and U bits get set then the resultant comparison DOES suddenly
311 // care about orderedness, and is true when ordered.
312 if (Op > ISD::SETTRUE2)
313 Op &= ~16; // Clear the U bit if the N bit is set.
315 // Canonicalize illegal integer setcc's.
316 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
319 return ISD::CondCode(Op);
322 /// getSetCCAndOperation - Return the result of a logical AND between different
323 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
324 /// function returns zero if it is not possible to represent the resultant
326 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
329 // Cannot fold a signed setcc with an unsigned setcc.
330 return ISD::SETCC_INVALID;
332 // Combine all of the condition bits.
333 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
335 // Canonicalize illegal integer setcc's.
339 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
340 case ISD::SETOEQ: // SETEQ & SETU[LG]E
341 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
342 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
343 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
350 //===----------------------------------------------------------------------===//
351 // SDNode Profile Support
352 //===----------------------------------------------------------------------===//
354 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
360 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
361 /// solely with their pointer.
362 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
363 ID.AddPointer(VTList.VTs);
366 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 static void AddNodeIDOperands(FoldingSetNodeID &ID,
369 ArrayRef<SDValue> Ops) {
370 for (auto& Op : Ops) {
371 ID.AddPointer(Op.getNode());
372 ID.AddInteger(Op.getResNo());
376 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 static void AddNodeIDOperands(FoldingSetNodeID &ID,
379 ArrayRef<SDUse> Ops) {
380 for (auto& Op : Ops) {
381 ID.AddPointer(Op.getNode());
382 ID.AddInteger(Op.getResNo());
386 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
390 ID.AddBoolean(exact);
393 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
394 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
395 bool nuw, bool nsw, bool exact) {
396 if (isBinOpWithFlags(Opcode))
397 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
400 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
401 SDVTList VTList, ArrayRef<SDValue> OpList) {
402 AddNodeIDOpcode(ID, OpC);
403 AddNodeIDValueTypes(ID, VTList);
404 AddNodeIDOperands(ID, OpList);
407 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
410 switch (N->getOpcode()) {
411 case ISD::TargetExternalSymbol:
412 case ISD::ExternalSymbol:
413 llvm_unreachable("Should only be used on nodes with operands");
414 default: break; // Normal nodes don't need extra info.
415 case ISD::TargetConstant:
416 case ISD::Constant: {
417 const ConstantSDNode *C = cast<ConstantSDNode>(N);
418 ID.AddPointer(C->getConstantIntValue());
419 ID.AddBoolean(C->isOpaque());
422 case ISD::TargetConstantFP:
423 case ISD::ConstantFP: {
424 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
427 case ISD::TargetGlobalAddress:
428 case ISD::GlobalAddress:
429 case ISD::TargetGlobalTLSAddress:
430 case ISD::GlobalTLSAddress: {
431 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
432 ID.AddPointer(GA->getGlobal());
433 ID.AddInteger(GA->getOffset());
434 ID.AddInteger(GA->getTargetFlags());
435 ID.AddInteger(GA->getAddressSpace());
438 case ISD::BasicBlock:
439 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
442 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444 case ISD::RegisterMask:
445 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
448 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450 case ISD::FrameIndex:
451 case ISD::TargetFrameIndex:
452 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
455 case ISD::TargetJumpTable:
456 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459 case ISD::ConstantPool:
460 case ISD::TargetConstantPool: {
461 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
462 ID.AddInteger(CP->getAlignment());
463 ID.AddInteger(CP->getOffset());
464 if (CP->isMachineConstantPoolEntry())
465 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467 ID.AddPointer(CP->getConstVal());
468 ID.AddInteger(CP->getTargetFlags());
471 case ISD::TargetIndex: {
472 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
473 ID.AddInteger(TI->getIndex());
474 ID.AddInteger(TI->getOffset());
475 ID.AddInteger(TI->getTargetFlags());
479 const LoadSDNode *LD = cast<LoadSDNode>(N);
480 ID.AddInteger(LD->getMemoryVT().getRawBits());
481 ID.AddInteger(LD->getRawSubclassData());
482 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
486 const StoreSDNode *ST = cast<StoreSDNode>(N);
487 ID.AddInteger(ST->getMemoryVT().getRawBits());
488 ID.AddInteger(ST->getRawSubclassData());
489 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
500 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
501 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
502 BinNode->hasNoSignedWrap(), BinNode->isExact());
505 case ISD::ATOMIC_CMP_SWAP:
506 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
507 case ISD::ATOMIC_SWAP:
508 case ISD::ATOMIC_LOAD_ADD:
509 case ISD::ATOMIC_LOAD_SUB:
510 case ISD::ATOMIC_LOAD_AND:
511 case ISD::ATOMIC_LOAD_OR:
512 case ISD::ATOMIC_LOAD_XOR:
513 case ISD::ATOMIC_LOAD_NAND:
514 case ISD::ATOMIC_LOAD_MIN:
515 case ISD::ATOMIC_LOAD_MAX:
516 case ISD::ATOMIC_LOAD_UMIN:
517 case ISD::ATOMIC_LOAD_UMAX:
518 case ISD::ATOMIC_LOAD:
519 case ISD::ATOMIC_STORE: {
520 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
521 ID.AddInteger(AT->getMemoryVT().getRawBits());
522 ID.AddInteger(AT->getRawSubclassData());
523 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
526 case ISD::PREFETCH: {
527 const MemSDNode *PF = cast<MemSDNode>(N);
528 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
531 case ISD::VECTOR_SHUFFLE: {
532 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
533 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535 ID.AddInteger(SVN->getMaskElt(i));
538 case ISD::TargetBlockAddress:
539 case ISD::BlockAddress: {
540 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
541 ID.AddPointer(BA->getBlockAddress());
542 ID.AddInteger(BA->getOffset());
543 ID.AddInteger(BA->getTargetFlags());
546 } // end switch (N->getOpcode())
548 // Target specific memory nodes could also have address spaces to check.
549 if (N->isTargetMemoryOpcode())
550 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
553 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
556 AddNodeIDOpcode(ID, N->getOpcode());
557 // Add the return value info.
558 AddNodeIDValueTypes(ID, N->getVTList());
559 // Add the operand info.
560 AddNodeIDOperands(ID, N->ops());
562 // Handle SDNode leafs with special info.
563 AddNodeIDCustom(ID, N);
566 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
567 /// the CSE map that carries volatility, temporalness, indexing mode, and
568 /// extension/truncation information.
570 static inline unsigned
571 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
572 bool isNonTemporal, bool isInvariant) {
573 assert((ConvType & 3) == ConvType &&
574 "ConvType may not require more than 2 bits!");
575 assert((AM & 7) == AM &&
576 "AM may not require more than 3 bits!");
580 (isNonTemporal << 6) |
584 //===----------------------------------------------------------------------===//
585 // SelectionDAG Class
586 //===----------------------------------------------------------------------===//
588 /// doNotCSE - Return true if CSE should not be performed for this node.
589 static bool doNotCSE(SDNode *N) {
590 if (N->getValueType(0) == MVT::Glue)
591 return true; // Never CSE anything that produces a flag.
593 switch (N->getOpcode()) {
595 case ISD::HANDLENODE:
597 return true; // Never CSE these nodes.
600 // Check that remaining values produced are not flags.
601 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
602 if (N->getValueType(i) == MVT::Glue)
603 return true; // Never CSE anything that produces a flag.
608 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 void SelectionDAG::RemoveDeadNodes() {
611 // Create a dummy node (which is not added to allnodes), that adds a reference
612 // to the root node, preventing it from being deleted.
613 HandleSDNode Dummy(getRoot());
615 SmallVector<SDNode*, 128> DeadNodes;
617 // Add all obviously-dead nodes to the DeadNodes worklist.
618 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620 DeadNodes.push_back(I);
622 RemoveDeadNodes(DeadNodes);
624 // If the root changed (e.g. it was a dead load, update the root).
625 setRoot(Dummy.getValue());
628 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
629 /// given list, and any nodes that become unreachable as a result.
630 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
632 // Process the worklist, deleting the nodes and adding their uses to the
634 while (!DeadNodes.empty()) {
635 SDNode *N = DeadNodes.pop_back_val();
637 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
638 DUL->NodeDeleted(N, nullptr);
640 // Take the node out of the appropriate CSE map.
641 RemoveNodeFromCSEMaps(N);
643 // Next, brutally remove the operand list. This is safe to do, as there are
644 // no cycles in the graph.
645 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647 SDNode *Operand = Use.getNode();
650 // Now that we removed this operand, see if there are no uses of it left.
651 if (Operand->use_empty())
652 DeadNodes.push_back(Operand);
659 void SelectionDAG::RemoveDeadNode(SDNode *N){
660 SmallVector<SDNode*, 16> DeadNodes(1, N);
662 // Create a dummy node that adds a reference to the root node, preventing
663 // it from being deleted. (This matters if the root is an operand of the
665 HandleSDNode Dummy(getRoot());
667 RemoveDeadNodes(DeadNodes);
670 void SelectionDAG::DeleteNode(SDNode *N) {
671 // First take this out of the appropriate CSE map.
672 RemoveNodeFromCSEMaps(N);
674 // Finally, remove uses due to operands of this node, remove from the
675 // AllNodes list, and delete the node.
676 DeleteNodeNotInCSEMaps(N);
679 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
680 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
681 assert(N->use_empty() && "Cannot delete a node that is not dead!");
683 // Drop all of the operands and decrement used node's use counts.
689 void SelectionDAG::DeallocateNode(SDNode *N) {
690 if (N->OperandsNeedDelete)
691 delete[] N->OperandList;
693 // Set the opcode to DELETED_NODE to help catch bugs when node
694 // memory is reallocated.
695 N->NodeType = ISD::DELETED_NODE;
697 NodeAllocator.Deallocate(AllNodes.remove(N));
699 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
700 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
701 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
702 DbgVals[i]->setIsInvalidated();
706 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
707 static void VerifySDNode(SDNode *N) {
708 switch (N->getOpcode()) {
711 case ISD::BUILD_PAIR: {
712 EVT VT = N->getValueType(0);
713 assert(N->getNumValues() == 1 && "Too many results!");
714 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
715 "Wrong return type!");
716 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
717 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
718 "Mismatched operand types!");
719 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
720 "Wrong operand type!");
721 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
722 "Wrong return type size");
725 case ISD::BUILD_VECTOR: {
726 assert(N->getNumValues() == 1 && "Too many results!");
727 assert(N->getValueType(0).isVector() && "Wrong return type!");
728 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
729 "Wrong number of operands!");
730 EVT EltVT = N->getValueType(0).getVectorElementType();
731 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
732 assert((I->getValueType() == EltVT ||
733 (EltVT.isInteger() && I->getValueType().isInteger() &&
734 EltVT.bitsLE(I->getValueType()))) &&
735 "Wrong operand type!");
736 assert(I->getValueType() == N->getOperand(0).getValueType() &&
737 "Operands must all have the same type");
745 /// \brief Insert a newly allocated node into the DAG.
747 /// Handles insertion into the all nodes list and CSE map, as well as
748 /// verification and other common operations when a new node is allocated.
749 void SelectionDAG::InsertNode(SDNode *N) {
750 AllNodes.push_back(N);
756 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
757 /// correspond to it. This is useful when we're about to delete or repurpose
758 /// the node. We don't want future request for structurally identical nodes
759 /// to return N anymore.
760 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
762 switch (N->getOpcode()) {
763 case ISD::HANDLENODE: return false; // noop.
765 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
766 "Cond code doesn't exist!");
767 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
768 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
770 case ISD::ExternalSymbol:
771 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
773 case ISD::TargetExternalSymbol: {
774 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
775 Erased = TargetExternalSymbols.erase(
776 std::pair<std::string,unsigned char>(ESN->getSymbol(),
777 ESN->getTargetFlags()));
780 case ISD::VALUETYPE: {
781 EVT VT = cast<VTSDNode>(N)->getVT();
782 if (VT.isExtended()) {
783 Erased = ExtendedValueTypeNodes.erase(VT);
785 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
786 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
791 // Remove it from the CSE Map.
792 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
793 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
794 Erased = CSEMap.RemoveNode(N);
798 // Verify that the node was actually in one of the CSE maps, unless it has a
799 // flag result (which cannot be CSE'd) or is one of the special cases that are
800 // not subject to CSE.
801 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
802 !N->isMachineOpcode() && !doNotCSE(N)) {
805 llvm_unreachable("Node is not in map!");
811 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
812 /// maps and modified in place. Add it back to the CSE maps, unless an identical
813 /// node already exists, in which case transfer all its users to the existing
814 /// node. This transfer can potentially trigger recursive merging.
817 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
818 // For node types that aren't CSE'd, just act as if no identical node
821 SDNode *Existing = CSEMap.GetOrInsertNode(N);
823 // If there was already an existing matching node, use ReplaceAllUsesWith
824 // to replace the dead one with the existing one. This can cause
825 // recursive merging of other unrelated nodes down the line.
826 ReplaceAllUsesWith(N, Existing);
828 // N is now dead. Inform the listeners and delete it.
829 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
830 DUL->NodeDeleted(N, Existing);
831 DeleteNodeNotInCSEMaps(N);
836 // If the node doesn't already exist, we updated it. Inform listeners.
837 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
841 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
842 /// were replaced with those specified. If this node is never memoized,
843 /// return null, otherwise return a pointer to the slot it would take. If a
844 /// node already exists with these operands, the slot will be non-null.
845 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
850 SDValue Ops[] = { Op };
852 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
853 AddNodeIDCustom(ID, N);
854 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
858 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
859 /// were replaced with those specified. If this node is never memoized,
860 /// return null, otherwise return a pointer to the slot it would take. If a
861 /// node already exists with these operands, the slot will be non-null.
862 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
863 SDValue Op1, SDValue Op2,
868 SDValue Ops[] = { Op1, Op2 };
870 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
871 AddNodeIDCustom(ID, N);
872 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
877 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
878 /// were replaced with those specified. If this node is never memoized,
879 /// return null, otherwise return a pointer to the slot it would take. If a
880 /// node already exists with these operands, the slot will be non-null.
881 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
887 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
888 AddNodeIDCustom(ID, N);
889 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
893 /// getEVTAlignment - Compute the default alignment value for the
896 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
897 Type *Ty = VT == MVT::iPTR ?
898 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
899 VT.getTypeForEVT(*getContext());
901 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
904 // EntryNode could meaningfully have debug info if we can find it...
905 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
906 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
907 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
908 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
909 UpdateListeners(nullptr) {
910 AllNodes.push_back(&EntryNode);
911 DbgInfo = new SDDbgInfo();
914 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
917 Context = &mf.getFunction()->getContext();
920 SelectionDAG::~SelectionDAG() {
921 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
926 void SelectionDAG::allnodes_clear() {
927 assert(&*AllNodes.begin() == &EntryNode);
928 AllNodes.remove(AllNodes.begin());
929 while (!AllNodes.empty())
930 DeallocateNode(AllNodes.begin());
933 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
934 SDVTList VTs, SDValue N1,
935 SDValue N2, bool nuw, bool nsw,
937 if (isBinOpWithFlags(Opcode)) {
938 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
939 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
940 FN->setHasNoUnsignedWrap(nuw);
941 FN->setHasNoSignedWrap(nsw);
942 FN->setIsExact(exact);
947 BinarySDNode *N = new (NodeAllocator)
948 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
952 void SelectionDAG::clear() {
954 OperandAllocator.Reset();
957 ExtendedValueTypeNodes.clear();
958 ExternalSymbols.clear();
959 TargetExternalSymbols.clear();
960 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
961 static_cast<CondCodeSDNode*>(nullptr));
962 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
963 static_cast<SDNode*>(nullptr));
965 EntryNode.UseList = nullptr;
966 AllNodes.push_back(&EntryNode);
967 Root = getEntryNode();
971 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
972 return VT.bitsGT(Op.getValueType()) ?
973 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
974 getNode(ISD::TRUNCATE, DL, VT, Op);
977 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
978 return VT.bitsGT(Op.getValueType()) ?
979 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
980 getNode(ISD::TRUNCATE, DL, VT, Op);
983 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
984 return VT.bitsGT(Op.getValueType()) ?
985 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
986 getNode(ISD::TRUNCATE, DL, VT, Op);
989 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
991 if (VT.bitsLE(Op.getValueType()))
992 return getNode(ISD::TRUNCATE, SL, VT, Op);
994 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
995 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
998 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
999 assert(!VT.isVector() &&
1000 "getZeroExtendInReg should use the vector element type instead of "
1001 "the vector type!");
1002 if (Op.getValueType() == VT) return Op;
1003 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1004 APInt Imm = APInt::getLowBitsSet(BitWidth,
1005 VT.getSizeInBits());
1006 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1007 getConstant(Imm, Op.getValueType()));
1010 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1011 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1012 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1013 "The sizes of the input and result must match in order to perform the "
1014 "extend in-register.");
1015 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1016 "The destination vector type must have fewer lanes than the input.");
1017 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1020 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1021 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1022 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1023 "The sizes of the input and result must match in order to perform the "
1024 "extend in-register.");
1025 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1026 "The destination vector type must have fewer lanes than the input.");
1027 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1030 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1031 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1032 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1033 "The sizes of the input and result must match in order to perform the "
1034 "extend in-register.");
1035 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1036 "The destination vector type must have fewer lanes than the input.");
1037 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1040 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1042 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1043 EVT EltVT = VT.getScalarType();
1045 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1046 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1049 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1050 EVT EltVT = VT.getScalarType();
1052 switch (TLI->getBooleanContents(VT)) {
1053 case TargetLowering::ZeroOrOneBooleanContent:
1054 case TargetLowering::UndefinedBooleanContent:
1055 TrueValue = getConstant(1, VT);
1057 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1058 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1062 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1065 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1066 EVT EltVT = VT.getScalarType();
1067 assert((EltVT.getSizeInBits() >= 64 ||
1068 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1069 "getConstant with a uint64_t value that doesn't fit in the type!");
1070 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1073 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1075 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1078 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1080 assert(VT.isInteger() && "Cannot create FP integer constant!");
1082 EVT EltVT = VT.getScalarType();
1083 const ConstantInt *Elt = &Val;
1085 const TargetLowering *TLI = TM.getTargetLowering();
1087 // In some cases the vector type is legal but the element type is illegal and
1088 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1089 // inserted value (the type does not need to match the vector element type).
1090 // Any extra bits introduced will be truncated away.
1091 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1092 TargetLowering::TypePromoteInteger) {
1093 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1094 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1095 Elt = ConstantInt::get(*getContext(), NewVal);
1097 // In other cases the element type is illegal and needs to be expanded, for
1098 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1099 // the value into n parts and use a vector type with n-times the elements.
1100 // Then bitcast to the type requested.
1101 // Legalizing constants too early makes the DAGCombiner's job harder so we
1102 // only legalize if the DAG tells us we must produce legal types.
1103 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1104 TLI->getTypeAction(*getContext(), EltVT) ==
1105 TargetLowering::TypeExpandInteger) {
1106 APInt NewVal = Elt->getValue();
1107 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1108 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1109 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1110 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1112 // Check the temporary vector is the correct size. If this fails then
1113 // getTypeToTransformTo() probably returned a type whose size (in bits)
1114 // isn't a power-of-2 factor of the requested type size.
1115 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1117 SmallVector<SDValue, 2> EltParts;
1118 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1119 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1120 .trunc(ViaEltSizeInBits),
1121 ViaEltVT, isT, isO));
1124 // EltParts is currently in little endian order. If we actually want
1125 // big-endian order then reverse it now.
1126 if (TLI->isBigEndian())
1127 std::reverse(EltParts.begin(), EltParts.end());
1129 // The elements must be reversed when the element order is different
1130 // to the endianness of the elements (because the BITCAST is itself a
1131 // vector shuffle in this situation). However, we do not need any code to
1132 // perform this reversal because getConstant() is producing a vector
1134 // This situation occurs in MIPS MSA.
1136 SmallVector<SDValue, 8> Ops;
1137 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1138 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1140 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1141 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1146 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1147 "APInt size does not match type size!");
1148 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1149 FoldingSetNodeID ID;
1150 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1154 SDNode *N = nullptr;
1155 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1157 return SDValue(N, 0);
1160 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1161 CSEMap.InsertNode(N, IP);
1165 SDValue Result(N, 0);
1166 if (VT.isVector()) {
1167 SmallVector<SDValue, 8> Ops;
1168 Ops.assign(VT.getVectorNumElements(), Result);
1169 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1174 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1175 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1179 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1180 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1183 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1184 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1186 EVT EltVT = VT.getScalarType();
1188 // Do the map lookup using the actual bit pattern for the floating point
1189 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1190 // we don't have issues with SNANs.
1191 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1192 FoldingSetNodeID ID;
1193 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1196 SDNode *N = nullptr;
1197 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1199 return SDValue(N, 0);
1202 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1203 CSEMap.InsertNode(N, IP);
1207 SDValue Result(N, 0);
1208 if (VT.isVector()) {
1209 SmallVector<SDValue, 8> Ops;
1210 Ops.assign(VT.getVectorNumElements(), Result);
1211 // FIXME SDLoc info might be appropriate here
1212 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1217 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1218 EVT EltVT = VT.getScalarType();
1219 if (EltVT==MVT::f32)
1220 return getConstantFP(APFloat((float)Val), VT, isTarget);
1221 else if (EltVT==MVT::f64)
1222 return getConstantFP(APFloat(Val), VT, isTarget);
1223 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1226 APFloat apf = APFloat(Val);
1227 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1229 return getConstantFP(apf, VT, isTarget);
1231 llvm_unreachable("Unsupported type in getConstantFP");
1234 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1235 EVT VT, int64_t Offset,
1237 unsigned char TargetFlags) {
1238 assert((TargetFlags == 0 || isTargetGA) &&
1239 "Cannot set target flags on target-independent globals");
1240 const TargetLowering *TLI = TM.getTargetLowering();
1242 // Truncate (with sign-extension) the offset value to the pointer size.
1243 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1245 Offset = SignExtend64(Offset, BitWidth);
1248 if (GV->isThreadLocal())
1249 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1251 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1253 FoldingSetNodeID ID;
1254 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1256 ID.AddInteger(Offset);
1257 ID.AddInteger(TargetFlags);
1258 ID.AddInteger(GV->getType()->getAddressSpace());
1260 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1261 return SDValue(E, 0);
1263 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1264 DL.getDebugLoc(), GV, VT,
1265 Offset, TargetFlags);
1266 CSEMap.InsertNode(N, IP);
1268 return SDValue(N, 0);
1271 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1272 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1273 FoldingSetNodeID ID;
1274 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1277 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1278 return SDValue(E, 0);
1280 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1281 CSEMap.InsertNode(N, IP);
1283 return SDValue(N, 0);
1286 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1287 unsigned char TargetFlags) {
1288 assert((TargetFlags == 0 || isTarget) &&
1289 "Cannot set target flags on target-independent jump tables");
1290 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1291 FoldingSetNodeID ID;
1292 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1294 ID.AddInteger(TargetFlags);
1296 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1297 return SDValue(E, 0);
1299 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1301 CSEMap.InsertNode(N, IP);
1303 return SDValue(N, 0);
1306 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1307 unsigned Alignment, int Offset,
1309 unsigned char TargetFlags) {
1310 assert((TargetFlags == 0 || isTarget) &&
1311 "Cannot set target flags on target-independent globals");
1314 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1315 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1318 ID.AddInteger(Alignment);
1319 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1323 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1327 Alignment, TargetFlags);
1328 CSEMap.InsertNode(N, IP);
1330 return SDValue(N, 0);
1334 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1335 unsigned Alignment, int Offset,
1337 unsigned char TargetFlags) {
1338 assert((TargetFlags == 0 || isTarget) &&
1339 "Cannot set target flags on target-independent globals");
1342 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1343 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1344 FoldingSetNodeID ID;
1345 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1346 ID.AddInteger(Alignment);
1347 ID.AddInteger(Offset);
1348 C->addSelectionDAGCSEId(ID);
1349 ID.AddInteger(TargetFlags);
1351 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1352 return SDValue(E, 0);
1354 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1355 Alignment, TargetFlags);
1356 CSEMap.InsertNode(N, IP);
1358 return SDValue(N, 0);
1361 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1362 unsigned char TargetFlags) {
1363 FoldingSetNodeID ID;
1364 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1365 ID.AddInteger(Index);
1366 ID.AddInteger(Offset);
1367 ID.AddInteger(TargetFlags);
1369 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1370 return SDValue(E, 0);
1372 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1374 CSEMap.InsertNode(N, IP);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1380 FoldingSetNodeID ID;
1381 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1384 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1385 return SDValue(E, 0);
1387 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1388 CSEMap.InsertNode(N, IP);
1390 return SDValue(N, 0);
1393 SDValue SelectionDAG::getValueType(EVT VT) {
1394 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1395 ValueTypeNodes.size())
1396 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1398 SDNode *&N = VT.isExtended() ?
1399 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1401 if (N) return SDValue(N, 0);
1402 N = new (NodeAllocator) VTSDNode(VT);
1404 return SDValue(N, 0);
1407 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1408 SDNode *&N = ExternalSymbols[Sym];
1409 if (N) return SDValue(N, 0);
1410 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1412 return SDValue(N, 0);
1415 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1416 unsigned char TargetFlags) {
1418 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1420 if (N) return SDValue(N, 0);
1421 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1423 return SDValue(N, 0);
1426 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1427 if ((unsigned)Cond >= CondCodeNodes.size())
1428 CondCodeNodes.resize(Cond+1);
1430 if (!CondCodeNodes[Cond]) {
1431 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1432 CondCodeNodes[Cond] = N;
1436 return SDValue(CondCodeNodes[Cond], 0);
1439 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1440 // the shuffle mask M that point at N1 to point at N2, and indices that point
1441 // N2 to point at N1.
1442 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1444 int NElts = M.size();
1445 for (int i = 0; i != NElts; ++i) {
1453 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1454 SDValue N2, const int *Mask) {
1455 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1456 "Invalid VECTOR_SHUFFLE");
1458 // Canonicalize shuffle undef, undef -> undef
1459 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1460 return getUNDEF(VT);
1462 // Validate that all indices in Mask are within the range of the elements
1463 // input to the shuffle.
1464 unsigned NElts = VT.getVectorNumElements();
1465 SmallVector<int, 8> MaskVec;
1466 for (unsigned i = 0; i != NElts; ++i) {
1467 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1468 MaskVec.push_back(Mask[i]);
1471 // Canonicalize shuffle v, v -> v, undef
1474 for (unsigned i = 0; i != NElts; ++i)
1475 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1478 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1479 if (N1.getOpcode() == ISD::UNDEF)
1480 commuteShuffle(N1, N2, MaskVec);
1482 // Canonicalize all index into lhs, -> shuffle lhs, undef
1483 // Canonicalize all index into rhs, -> shuffle rhs, undef
1484 bool AllLHS = true, AllRHS = true;
1485 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1486 for (unsigned i = 0; i != NElts; ++i) {
1487 if (MaskVec[i] >= (int)NElts) {
1492 } else if (MaskVec[i] >= 0) {
1496 if (AllLHS && AllRHS)
1497 return getUNDEF(VT);
1498 if (AllLHS && !N2Undef)
1502 commuteShuffle(N1, N2, MaskVec);
1504 // Reset our undef status after accounting for the mask.
1505 N2Undef = N2.getOpcode() == ISD::UNDEF;
1506 // Re-check whether both sides ended up undef.
1507 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1508 return getUNDEF(VT);
1510 // If Identity shuffle return that node.
1511 bool Identity = true;
1512 for (unsigned i = 0; i != NElts; ++i) {
1513 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1515 if (Identity && NElts)
1518 // Shuffling a constant splat doesn't change the result.
1522 // Look through any bitcasts. We check that these don't change the number
1523 // (and size) of elements and just changes their types.
1524 while (V.getOpcode() == ISD::BITCAST)
1525 V = V->getOperand(0);
1527 // A splat should always show up as a build vector node.
1528 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1529 BitVector UndefElements;
1530 SDValue Splat = BV->getSplatValue(&UndefElements);
1531 // If this is a splat of an undef, shuffling it is also undef.
1532 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1533 return getUNDEF(VT);
1535 // We only have a splat which can skip shuffles if there is a splatted
1536 // value and no undef lanes rearranged by the shuffle.
1537 if (Splat && UndefElements.none()) {
1538 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1539 // number of elements match or the value splatted is a zero constant.
1540 if (V.getValueType().getVectorNumElements() ==
1541 VT.getVectorNumElements())
1543 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1544 if (C->isNullValue())
1550 FoldingSetNodeID ID;
1551 SDValue Ops[2] = { N1, N2 };
1552 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1553 for (unsigned i = 0; i != NElts; ++i)
1554 ID.AddInteger(MaskVec[i]);
1557 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1558 return SDValue(E, 0);
1560 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1561 // SDNode doesn't have access to it. This memory will be "leaked" when
1562 // the node is deallocated, but recovered when the NodeAllocator is released.
1563 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1564 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1566 ShuffleVectorSDNode *N =
1567 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1568 dl.getDebugLoc(), N1, N2,
1570 CSEMap.InsertNode(N, IP);
1572 return SDValue(N, 0);
1575 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1576 MVT VT = SV.getSimpleValueType(0);
1577 unsigned NumElems = VT.getVectorNumElements();
1578 SmallVector<int, 8> MaskVec;
1580 for (unsigned i = 0; i != NumElems; ++i) {
1581 int Idx = SV.getMaskElt(i);
1583 if (Idx < (int)NumElems)
1588 MaskVec.push_back(Idx);
1591 SDValue Op0 = SV.getOperand(0);
1592 SDValue Op1 = SV.getOperand(1);
1593 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1596 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1597 SDValue Val, SDValue DTy,
1598 SDValue STy, SDValue Rnd, SDValue Sat,
1599 ISD::CvtCode Code) {
1600 // If the src and dest types are the same and the conversion is between
1601 // integer types of the same sign or two floats, no conversion is necessary.
1603 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1606 FoldingSetNodeID ID;
1607 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1608 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1610 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1611 return SDValue(E, 0);
1613 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1616 CSEMap.InsertNode(N, IP);
1618 return SDValue(N, 0);
1621 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1622 FoldingSetNodeID ID;
1623 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1624 ID.AddInteger(RegNo);
1626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1627 return SDValue(E, 0);
1629 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1630 CSEMap.InsertNode(N, IP);
1632 return SDValue(N, 0);
1635 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1636 FoldingSetNodeID ID;
1637 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1638 ID.AddPointer(RegMask);
1640 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1641 return SDValue(E, 0);
1643 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1644 CSEMap.InsertNode(N, IP);
1646 return SDValue(N, 0);
1649 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1650 FoldingSetNodeID ID;
1651 SDValue Ops[] = { Root };
1652 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1653 ID.AddPointer(Label);
1655 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1656 return SDValue(E, 0);
1658 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1659 dl.getDebugLoc(), Root, Label);
1660 CSEMap.InsertNode(N, IP);
1662 return SDValue(N, 0);
1666 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1669 unsigned char TargetFlags) {
1670 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1672 FoldingSetNodeID ID;
1673 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1675 ID.AddInteger(Offset);
1676 ID.AddInteger(TargetFlags);
1678 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1679 return SDValue(E, 0);
1681 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1683 CSEMap.InsertNode(N, IP);
1685 return SDValue(N, 0);
1688 SDValue SelectionDAG::getSrcValue(const Value *V) {
1689 assert((!V || V->getType()->isPointerTy()) &&
1690 "SrcValue is not a pointer?");
1692 FoldingSetNodeID ID;
1693 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1697 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1698 return SDValue(E, 0);
1700 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1701 CSEMap.InsertNode(N, IP);
1703 return SDValue(N, 0);
1706 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1707 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1708 FoldingSetNodeID ID;
1709 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1713 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1714 return SDValue(E, 0);
1716 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1717 CSEMap.InsertNode(N, IP);
1719 return SDValue(N, 0);
1722 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1723 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1724 unsigned SrcAS, unsigned DestAS) {
1725 SDValue Ops[] = {Ptr};
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1728 ID.AddInteger(SrcAS);
1729 ID.AddInteger(DestAS);
1732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1733 return SDValue(E, 0);
1735 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1737 VT, Ptr, SrcAS, DestAS);
1738 CSEMap.InsertNode(N, IP);
1740 return SDValue(N, 0);
1743 /// getShiftAmountOperand - Return the specified value casted to
1744 /// the target's desired shift amount type.
1745 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1746 EVT OpTy = Op.getValueType();
1747 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1748 if (OpTy == ShTy || OpTy.isVector()) return Op;
1750 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1751 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1754 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1755 /// specified value type.
1756 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1757 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1758 unsigned ByteSize = VT.getStoreSize();
1759 Type *Ty = VT.getTypeForEVT(*getContext());
1760 const TargetLowering *TLI = TM.getTargetLowering();
1761 unsigned StackAlign =
1762 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1764 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1765 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1768 /// CreateStackTemporary - Create a stack temporary suitable for holding
1769 /// either of the specified value types.
1770 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1771 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1772 VT2.getStoreSizeInBits())/8;
1773 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1774 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1775 const TargetLowering *TLI = TM.getTargetLowering();
1776 const DataLayout *TD = TLI->getDataLayout();
1777 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1778 TD->getPrefTypeAlignment(Ty2));
1780 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1781 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1782 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1785 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1786 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1787 // These setcc operations always fold.
1791 case ISD::SETFALSE2: return getConstant(0, VT);
1793 case ISD::SETTRUE2: {
1794 const TargetLowering *TLI = TM.getTargetLowering();
1795 TargetLowering::BooleanContent Cnt =
1796 TLI->getBooleanContents(N1->getValueType(0));
1798 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1811 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1815 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1816 const APInt &C2 = N2C->getAPIntValue();
1817 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1818 const APInt &C1 = N1C->getAPIntValue();
1821 default: llvm_unreachable("Unknown integer setcc!");
1822 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1823 case ISD::SETNE: return getConstant(C1 != C2, VT);
1824 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1825 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1826 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1827 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1828 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1829 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1830 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1831 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1835 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1836 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1837 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1840 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1841 return getUNDEF(VT);
1843 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1844 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1845 return getUNDEF(VT);
1847 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1848 R==APFloat::cmpLessThan, VT);
1849 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1850 return getUNDEF(VT);
1852 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1853 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1854 return getUNDEF(VT);
1856 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1857 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1858 return getUNDEF(VT);
1860 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1861 R==APFloat::cmpEqual, VT);
1862 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1863 return getUNDEF(VT);
1865 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1866 R==APFloat::cmpEqual, VT);
1867 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1868 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1869 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1870 R==APFloat::cmpEqual, VT);
1871 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1872 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1873 R==APFloat::cmpLessThan, VT);
1874 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1875 R==APFloat::cmpUnordered, VT);
1876 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1877 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1880 // Ensure that the constant occurs on the RHS.
1881 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1882 MVT CompVT = N1.getValueType().getSimpleVT();
1883 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1886 return getSetCC(dl, VT, N2, N1, SwappedCond);
1890 // Could not fold it.
1894 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1895 /// use this predicate to simplify operations downstream.
1896 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1897 // This predicate is not safe for vector operations.
1898 if (Op.getValueType().isVector())
1901 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1902 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1905 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1906 /// this predicate to simplify operations downstream. Mask is known to be zero
1907 /// for bits that V cannot have.
1908 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1909 unsigned Depth) const {
1910 APInt KnownZero, KnownOne;
1911 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1912 return (KnownZero & Mask) == Mask;
1915 /// Determine which bits of Op are known to be either zero or one and return
1916 /// them in the KnownZero/KnownOne bitsets.
1917 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1918 APInt &KnownOne, unsigned Depth) const {
1919 const TargetLowering *TLI = TM.getTargetLowering();
1920 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1922 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1924 return; // Limit search depth.
1926 APInt KnownZero2, KnownOne2;
1928 switch (Op.getOpcode()) {
1930 // We know all of the bits for a constant!
1931 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1932 KnownZero = ~KnownOne;
1935 // If either the LHS or the RHS are Zero, the result is zero.
1936 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1937 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1939 // Output known-1 bits are only known if set in both the LHS & RHS.
1940 KnownOne &= KnownOne2;
1941 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1942 KnownZero |= KnownZero2;
1945 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1946 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1948 // Output known-0 bits are only known if clear in both the LHS & RHS.
1949 KnownZero &= KnownZero2;
1950 // Output known-1 are known to be set if set in either the LHS | RHS.
1951 KnownOne |= KnownOne2;
1954 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1955 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1957 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1958 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1959 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1960 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1961 KnownZero = KnownZeroOut;
1965 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1966 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1968 // If low bits are zero in either operand, output low known-0 bits.
1969 // Also compute a conserative estimate for high known-0 bits.
1970 // More trickiness is possible, but this is sufficient for the
1971 // interesting case of alignment computation.
1972 KnownOne.clearAllBits();
1973 unsigned TrailZ = KnownZero.countTrailingOnes() +
1974 KnownZero2.countTrailingOnes();
1975 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1976 KnownZero2.countLeadingOnes(),
1977 BitWidth) - BitWidth;
1979 TrailZ = std::min(TrailZ, BitWidth);
1980 LeadZ = std::min(LeadZ, BitWidth);
1981 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1982 APInt::getHighBitsSet(BitWidth, LeadZ);
1986 // For the purposes of computing leading zeros we can conservatively
1987 // treat a udiv as a logical right shift by the power of 2 known to
1988 // be less than the denominator.
1989 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1990 unsigned LeadZ = KnownZero2.countLeadingOnes();
1992 KnownOne2.clearAllBits();
1993 KnownZero2.clearAllBits();
1994 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1995 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1996 if (RHSUnknownLeadingOnes != BitWidth)
1997 LeadZ = std::min(BitWidth,
1998 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2000 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2004 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2005 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2007 // Only known if known in both the LHS and RHS.
2008 KnownOne &= KnownOne2;
2009 KnownZero &= KnownZero2;
2011 case ISD::SELECT_CC:
2012 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2013 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2015 // Only known if known in both the LHS and RHS.
2016 KnownOne &= KnownOne2;
2017 KnownZero &= KnownZero2;
2025 if (Op.getResNo() != 1)
2027 // The boolean result conforms to getBooleanContents.
2028 // If we know the result of a setcc has the top bits zero, use this info.
2029 // We know that we have an integer-based boolean since these operations
2030 // are only available for integer.
2031 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2032 TargetLowering::ZeroOrOneBooleanContent &&
2034 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2037 // If we know the result of a setcc has the top bits zero, use this info.
2038 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2039 TargetLowering::ZeroOrOneBooleanContent &&
2041 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2044 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2045 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2046 unsigned ShAmt = SA->getZExtValue();
2048 // If the shift count is an invalid immediate, don't do anything.
2049 if (ShAmt >= BitWidth)
2052 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2053 KnownZero <<= ShAmt;
2055 // low bits known zero.
2056 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2060 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2061 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2062 unsigned ShAmt = SA->getZExtValue();
2064 // If the shift count is an invalid immediate, don't do anything.
2065 if (ShAmt >= BitWidth)
2068 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2069 KnownZero = KnownZero.lshr(ShAmt);
2070 KnownOne = KnownOne.lshr(ShAmt);
2072 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2073 KnownZero |= HighBits; // High bits known zero.
2077 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2078 unsigned ShAmt = SA->getZExtValue();
2080 // If the shift count is an invalid immediate, don't do anything.
2081 if (ShAmt >= BitWidth)
2084 // If any of the demanded bits are produced by the sign extension, we also
2085 // demand the input sign bit.
2086 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2088 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2089 KnownZero = KnownZero.lshr(ShAmt);
2090 KnownOne = KnownOne.lshr(ShAmt);
2092 // Handle the sign bits.
2093 APInt SignBit = APInt::getSignBit(BitWidth);
2094 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2096 if (KnownZero.intersects(SignBit)) {
2097 KnownZero |= HighBits; // New bits are known zero.
2098 } else if (KnownOne.intersects(SignBit)) {
2099 KnownOne |= HighBits; // New bits are known one.
2103 case ISD::SIGN_EXTEND_INREG: {
2104 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2105 unsigned EBits = EVT.getScalarType().getSizeInBits();
2107 // Sign extension. Compute the demanded bits in the result that are not
2108 // present in the input.
2109 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2111 APInt InSignBit = APInt::getSignBit(EBits);
2112 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2114 // If the sign extended bits are demanded, we know that the sign
2116 InSignBit = InSignBit.zext(BitWidth);
2117 if (NewBits.getBoolValue())
2118 InputDemandedBits |= InSignBit;
2120 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2121 KnownOne &= InputDemandedBits;
2122 KnownZero &= InputDemandedBits;
2124 // If the sign bit of the input is known set or clear, then we know the
2125 // top bits of the result.
2126 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2127 KnownZero |= NewBits;
2128 KnownOne &= ~NewBits;
2129 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2130 KnownOne |= NewBits;
2131 KnownZero &= ~NewBits;
2132 } else { // Input sign bit unknown
2133 KnownZero &= ~NewBits;
2134 KnownOne &= ~NewBits;
2139 case ISD::CTTZ_ZERO_UNDEF:
2141 case ISD::CTLZ_ZERO_UNDEF:
2143 unsigned LowBits = Log2_32(BitWidth)+1;
2144 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2145 KnownOne.clearAllBits();
2149 LoadSDNode *LD = cast<LoadSDNode>(Op);
2150 // If this is a ZEXTLoad and we are looking at the loaded value.
2151 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2152 EVT VT = LD->getMemoryVT();
2153 unsigned MemBits = VT.getScalarType().getSizeInBits();
2154 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2155 } else if (const MDNode *Ranges = LD->getRanges()) {
2156 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2160 case ISD::ZERO_EXTEND: {
2161 EVT InVT = Op.getOperand(0).getValueType();
2162 unsigned InBits = InVT.getScalarType().getSizeInBits();
2163 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2164 KnownZero = KnownZero.trunc(InBits);
2165 KnownOne = KnownOne.trunc(InBits);
2166 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2167 KnownZero = KnownZero.zext(BitWidth);
2168 KnownOne = KnownOne.zext(BitWidth);
2169 KnownZero |= NewBits;
2172 case ISD::SIGN_EXTEND: {
2173 EVT InVT = Op.getOperand(0).getValueType();
2174 unsigned InBits = InVT.getScalarType().getSizeInBits();
2175 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);
2181 // Note if the sign bit is known to be zero or one.
2182 bool SignBitKnownZero = KnownZero.isNegative();
2183 bool SignBitKnownOne = KnownOne.isNegative();
2185 KnownZero = KnownZero.zext(BitWidth);
2186 KnownOne = KnownOne.zext(BitWidth);
2188 // If the sign bit is known zero or one, the top bits match.
2189 if (SignBitKnownZero)
2190 KnownZero |= NewBits;
2191 else if (SignBitKnownOne)
2192 KnownOne |= NewBits;
2195 case ISD::ANY_EXTEND: {
2196 EVT InVT = Op.getOperand(0).getValueType();
2197 unsigned InBits = InVT.getScalarType().getSizeInBits();
2198 KnownZero = KnownZero.trunc(InBits);
2199 KnownOne = KnownOne.trunc(InBits);
2200 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2201 KnownZero = KnownZero.zext(BitWidth);
2202 KnownOne = KnownOne.zext(BitWidth);
2205 case ISD::TRUNCATE: {
2206 EVT InVT = Op.getOperand(0).getValueType();
2207 unsigned InBits = InVT.getScalarType().getSizeInBits();
2208 KnownZero = KnownZero.zext(InBits);
2209 KnownOne = KnownOne.zext(InBits);
2210 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 KnownZero = KnownZero.trunc(BitWidth);
2212 KnownOne = KnownOne.trunc(BitWidth);
2215 case ISD::AssertZext: {
2216 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2217 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2218 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2219 KnownZero |= (~InMask);
2220 KnownOne &= (~KnownZero);
2224 // All bits are zero except the low bit.
2225 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2229 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2230 // We know that the top bits of C-X are clear if X contains less bits
2231 // than C (i.e. no wrap-around can happen). For example, 20-X is
2232 // positive if we can prove that X is >= 0 and < 16.
2233 if (CLHS->getAPIntValue().isNonNegative()) {
2234 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2235 // NLZ can't be BitWidth with no sign bit
2236 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2237 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2239 // If all of the MaskV bits are known to be zero, then we know the
2240 // output top bits are zero, because we now know that the output is
2242 if ((KnownZero2 & MaskV) == MaskV) {
2243 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2244 // Top bits known zero.
2245 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2253 // Output known-0 bits are known if clear or set in both the low clear bits
2254 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2255 // low 3 bits clear.
2256 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2257 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2259 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2260 KnownZeroOut = std::min(KnownZeroOut,
2261 KnownZero2.countTrailingOnes());
2263 if (Op.getOpcode() == ISD::ADD) {
2264 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2268 // With ADDE, a carry bit may be added in, so we can only use this
2269 // information if we know (at least) that the low two bits are clear. We
2270 // then return to the caller that the low bit is unknown but that other bits
2272 if (KnownZeroOut >= 2) // ADDE
2273 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2277 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2278 const APInt &RA = Rem->getAPIntValue().abs();
2279 if (RA.isPowerOf2()) {
2280 APInt LowBits = RA - 1;
2281 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2283 // The low bits of the first operand are unchanged by the srem.
2284 KnownZero = KnownZero2 & LowBits;
2285 KnownOne = KnownOne2 & LowBits;
2287 // If the first operand is non-negative or has all low bits zero, then
2288 // the upper bits are all zero.
2289 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2290 KnownZero |= ~LowBits;
2292 // If the first operand is negative and not all low bits are zero, then
2293 // the upper bits are all one.
2294 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2295 KnownOne |= ~LowBits;
2296 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2301 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2302 const APInt &RA = Rem->getAPIntValue();
2303 if (RA.isPowerOf2()) {
2304 APInt LowBits = (RA - 1);
2305 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2307 // The upper bits are all zero, the lower ones are unchanged.
2308 KnownZero = KnownZero2 | ~LowBits;
2309 KnownOne = KnownOne2 & LowBits;
2314 // Since the result is less than or equal to either operand, any leading
2315 // zero bits in either operand must also exist in the result.
2316 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2317 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2319 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2320 KnownZero2.countLeadingOnes());
2321 KnownOne.clearAllBits();
2322 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2325 case ISD::FrameIndex:
2326 case ISD::TargetFrameIndex:
2327 if (unsigned Align = InferPtrAlignment(Op)) {
2328 // The low bits are known zero if the pointer is aligned.
2329 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2335 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2338 case ISD::INTRINSIC_WO_CHAIN:
2339 case ISD::INTRINSIC_W_CHAIN:
2340 case ISD::INTRINSIC_VOID:
2341 // Allow the target to implement this method for its nodes.
2342 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2346 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2349 /// ComputeNumSignBits - Return the number of times the sign bit of the
2350 /// register is replicated into the other bits. We know that at least 1 bit
2351 /// is always equal to the sign bit (itself), but other cases can give us
2352 /// information. For example, immediately after an "SRA X, 2", we know that
2353 /// the top 3 bits are all equal to each other, so we return 3.
2354 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2355 const TargetLowering *TLI = TM.getTargetLowering();
2356 EVT VT = Op.getValueType();
2357 assert(VT.isInteger() && "Invalid VT!");
2358 unsigned VTBits = VT.getScalarType().getSizeInBits();
2360 unsigned FirstAnswer = 1;
2363 return 1; // Limit search depth.
2365 switch (Op.getOpcode()) {
2367 case ISD::AssertSext:
2368 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2369 return VTBits-Tmp+1;
2370 case ISD::AssertZext:
2371 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2374 case ISD::Constant: {
2375 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2376 return Val.getNumSignBits();
2379 case ISD::SIGN_EXTEND:
2381 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2382 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2384 case ISD::SIGN_EXTEND_INREG:
2385 // Max of the input and what this extends.
2387 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2390 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2391 return std::max(Tmp, Tmp2);
2394 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395 // SRA X, C -> adds C sign bits.
2396 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2397 Tmp += C->getZExtValue();
2398 if (Tmp > VTBits) Tmp = VTBits;
2402 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2403 // shl destroys sign bits.
2404 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2405 if (C->getZExtValue() >= VTBits || // Bad shift.
2406 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2407 return Tmp - C->getZExtValue();
2412 case ISD::XOR: // NOT is handled here.
2413 // Logical binary ops preserve the number of sign bits at the worst.
2414 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2416 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2417 FirstAnswer = std::min(Tmp, Tmp2);
2418 // We computed what we know about the sign bits as our first
2419 // answer. Now proceed to the generic code that uses
2420 // computeKnownBits, and pick whichever answer is better.
2425 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2426 if (Tmp == 1) return 1; // Early out.
2427 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2428 return std::min(Tmp, Tmp2);
2436 if (Op.getResNo() != 1)
2438 // The boolean result conforms to getBooleanContents. Fall through.
2439 // If setcc returns 0/-1, all bits are sign bits.
2440 // We know that we have an integer-based boolean since these operations
2441 // are only available for integer.
2442 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2443 TargetLowering::ZeroOrNegativeOneBooleanContent)
2447 // If setcc returns 0/-1, all bits are sign bits.
2448 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2449 TargetLowering::ZeroOrNegativeOneBooleanContent)
2454 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2455 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2457 // Handle rotate right by N like a rotate left by 32-N.
2458 if (Op.getOpcode() == ISD::ROTR)
2459 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2461 // If we aren't rotating out all of the known-in sign bits, return the
2462 // number that are left. This handles rotl(sext(x), 1) for example.
2463 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2464 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2468 // Add can have at most one carry bit. Thus we know that the output
2469 // is, at worst, one more bit than the inputs.
2470 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471 if (Tmp == 1) return 1; // Early out.
2473 // Special case decrementing a value (ADD X, -1):
2474 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2475 if (CRHS->isAllOnesValue()) {
2476 APInt KnownZero, KnownOne;
2477 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2479 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2481 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2484 // If we are subtracting one from a positive number, there is no carry
2485 // out of the result.
2486 if (KnownZero.isNegative())
2490 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2491 if (Tmp2 == 1) return 1;
2492 return std::min(Tmp, Tmp2)-1;
2495 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2496 if (Tmp2 == 1) return 1;
2499 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2500 if (CLHS->isNullValue()) {
2501 APInt KnownZero, KnownOne;
2502 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2503 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2505 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2508 // If the input is known to be positive (the sign bit is known clear),
2509 // the output of the NEG has the same number of sign bits as the input.
2510 if (KnownZero.isNegative())
2513 // Otherwise, we treat this like a SUB.
2516 // Sub can have at most one carry bit. Thus we know that the output
2517 // is, at worst, one more bit than the inputs.
2518 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2519 if (Tmp == 1) return 1; // Early out.
2520 return std::min(Tmp, Tmp2)-1;
2522 // FIXME: it's tricky to do anything useful for this, but it is an important
2523 // case for targets like X86.
2527 // If we are looking at the loaded value of the SDNode.
2528 if (Op.getResNo() == 0) {
2529 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2530 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2531 unsigned ExtType = LD->getExtensionType();
2534 case ISD::SEXTLOAD: // '17' bits known
2535 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2536 return VTBits-Tmp+1;
2537 case ISD::ZEXTLOAD: // '16' bits known
2538 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2544 // Allow the target to implement this method for its nodes.
2545 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2546 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2547 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2548 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2549 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2550 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2553 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2554 // use this information.
2555 APInt KnownZero, KnownOne;
2556 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2559 if (KnownZero.isNegative()) { // sign bit is 0
2561 } else if (KnownOne.isNegative()) { // sign bit is 1;
2568 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2569 // the number of identical bits in the top of the input value.
2571 Mask <<= Mask.getBitWidth()-VTBits;
2572 // Return # leading zeros. We use 'min' here in case Val was zero before
2573 // shifting. We don't want to return '64' as for an i32 "0".
2574 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2577 /// isBaseWithConstantOffset - Return true if the specified operand is an
2578 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2579 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2580 /// semantics as an ADD. This handles the equivalence:
2581 /// X|Cst == X+Cst iff X&Cst = 0.
2582 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2583 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2584 !isa<ConstantSDNode>(Op.getOperand(1)))
2587 if (Op.getOpcode() == ISD::OR &&
2588 !MaskedValueIsZero(Op.getOperand(0),
2589 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2596 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2597 // If we're told that NaNs won't happen, assume they won't.
2598 if (getTarget().Options.NoNaNsFPMath)
2601 // If the value is a constant, we can obviously see if it is a NaN or not.
2602 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2603 return !C->getValueAPF().isNaN();
2605 // TODO: Recognize more cases here.
2610 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2611 // If the value is a constant, we can obviously see if it is a zero or not.
2612 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2613 return !C->isZero();
2615 // TODO: Recognize more cases here.
2616 switch (Op.getOpcode()) {
2619 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2620 return !C->isNullValue();
2627 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2628 // Check the obvious case.
2629 if (A == B) return true;
2631 // For for negative and positive zero.
2632 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2633 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2634 if (CA->isZero() && CB->isZero()) return true;
2636 // Otherwise they may not be equal.
2640 /// getNode - Gets or creates the specified node.
2642 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2643 FoldingSetNodeID ID;
2644 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2646 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2647 return SDValue(E, 0);
2649 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2650 DL.getDebugLoc(), getVTList(VT));
2651 CSEMap.InsertNode(N, IP);
2654 return SDValue(N, 0);
2657 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2658 EVT VT, SDValue Operand) {
2659 // Constant fold unary operations with an integer constant operand. Even
2660 // opaque constant will be folded, because the folding of unary operations
2661 // doesn't create new constants with different values. Nevertheless, the
2662 // opaque flag is preserved during folding to prevent future folding with
2664 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2665 const APInt &Val = C->getAPIntValue();
2668 case ISD::SIGN_EXTEND:
2669 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2670 C->isTargetOpcode(), C->isOpaque());
2671 case ISD::ANY_EXTEND:
2672 case ISD::ZERO_EXTEND:
2674 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2675 C->isTargetOpcode(), C->isOpaque());
2676 case ISD::UINT_TO_FP:
2677 case ISD::SINT_TO_FP: {
2678 APFloat apf(EVTToAPFloatSemantics(VT),
2679 APInt::getNullValue(VT.getSizeInBits()));
2680 (void)apf.convertFromAPInt(Val,
2681 Opcode==ISD::SINT_TO_FP,
2682 APFloat::rmNearestTiesToEven);
2683 return getConstantFP(apf, VT);
2686 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2687 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2688 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2689 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2692 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2695 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2698 case ISD::CTLZ_ZERO_UNDEF:
2699 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2702 case ISD::CTTZ_ZERO_UNDEF:
2703 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2708 // Constant fold unary operations with a floating point constant operand.
2709 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2710 APFloat V = C->getValueAPF(); // make copy
2714 return getConstantFP(V, VT);
2717 return getConstantFP(V, VT);
2719 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2720 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2721 return getConstantFP(V, VT);
2725 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2726 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2727 return getConstantFP(V, VT);
2731 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2732 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2733 return getConstantFP(V, VT);
2736 case ISD::FP_EXTEND: {
2738 // This can return overflow, underflow, or inexact; we don't care.
2739 // FIXME need to be more flexible about rounding mode.
2740 (void)V.convert(EVTToAPFloatSemantics(VT),
2741 APFloat::rmNearestTiesToEven, &ignored);
2742 return getConstantFP(V, VT);
2744 case ISD::FP_TO_SINT:
2745 case ISD::FP_TO_UINT: {
2748 assert(integerPartWidth >= 64);
2749 // FIXME need to be more flexible about rounding mode.
2750 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2751 Opcode==ISD::FP_TO_SINT,
2752 APFloat::rmTowardZero, &ignored);
2753 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2755 APInt api(VT.getSizeInBits(), x);
2756 return getConstant(api, VT);
2759 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2760 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2761 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2762 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2767 // Constant fold unary operations with a vector integer operand.
2768 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2769 if (BV->isConstant()) {
2772 // FIXME: Entirely reasonable to perform folding of other unary
2773 // operations here as the need arises.
2775 case ISD::UINT_TO_FP:
2776 case ISD::SINT_TO_FP: {
2777 SmallVector<SDValue, 8> Ops;
2778 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2779 SDValue OpN = BV->getOperand(i);
2780 // Let the above scalar folding handle the conversion of each
2782 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2786 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2792 unsigned OpOpcode = Operand.getNode()->getOpcode();
2794 case ISD::TokenFactor:
2795 case ISD::MERGE_VALUES:
2796 case ISD::CONCAT_VECTORS:
2797 return Operand; // Factor, merge or concat of one node? No need.
2798 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2799 case ISD::FP_EXTEND:
2800 assert(VT.isFloatingPoint() &&
2801 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2802 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2803 assert((!VT.isVector() ||
2804 VT.getVectorNumElements() ==
2805 Operand.getValueType().getVectorNumElements()) &&
2806 "Vector element count mismatch!");
2807 if (Operand.getOpcode() == ISD::UNDEF)
2808 return getUNDEF(VT);
2810 case ISD::SIGN_EXTEND:
2811 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2812 "Invalid SIGN_EXTEND!");
2813 if (Operand.getValueType() == VT) return Operand; // noop extension
2814 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2815 "Invalid sext node, dst < src!");
2816 assert((!VT.isVector() ||
2817 VT.getVectorNumElements() ==
2818 Operand.getValueType().getVectorNumElements()) &&
2819 "Vector element count mismatch!");
2820 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2821 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2822 else if (OpOpcode == ISD::UNDEF)
2823 // sext(undef) = 0, because the top bits will all be the same.
2824 return getConstant(0, VT);
2826 case ISD::ZERO_EXTEND:
2827 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2828 "Invalid ZERO_EXTEND!");
2829 if (Operand.getValueType() == VT) return Operand; // noop extension
2830 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2831 "Invalid zext node, dst < src!");
2832 assert((!VT.isVector() ||
2833 VT.getVectorNumElements() ==
2834 Operand.getValueType().getVectorNumElements()) &&
2835 "Vector element count mismatch!");
2836 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2837 return getNode(ISD::ZERO_EXTEND, DL, VT,
2838 Operand.getNode()->getOperand(0));
2839 else if (OpOpcode == ISD::UNDEF)
2840 // zext(undef) = 0, because the top bits will be zero.
2841 return getConstant(0, VT);
2843 case ISD::ANY_EXTEND:
2844 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2845 "Invalid ANY_EXTEND!");
2846 if (Operand.getValueType() == VT) return Operand; // noop extension
2847 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2848 "Invalid anyext node, dst < src!");
2849 assert((!VT.isVector() ||
2850 VT.getVectorNumElements() ==
2851 Operand.getValueType().getVectorNumElements()) &&
2852 "Vector element count mismatch!");
2854 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2855 OpOpcode == ISD::ANY_EXTEND)
2856 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2857 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2858 else if (OpOpcode == ISD::UNDEF)
2859 return getUNDEF(VT);
2861 // (ext (trunx x)) -> x
2862 if (OpOpcode == ISD::TRUNCATE) {
2863 SDValue OpOp = Operand.getNode()->getOperand(0);
2864 if (OpOp.getValueType() == VT)
2869 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2870 "Invalid TRUNCATE!");
2871 if (Operand.getValueType() == VT) return Operand; // noop truncate
2872 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2873 "Invalid truncate node, src < dst!");
2874 assert((!VT.isVector() ||
2875 VT.getVectorNumElements() ==
2876 Operand.getValueType().getVectorNumElements()) &&
2877 "Vector element count mismatch!");
2878 if (OpOpcode == ISD::TRUNCATE)
2879 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2880 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2881 OpOpcode == ISD::ANY_EXTEND) {
2882 // If the source is smaller than the dest, we still need an extend.
2883 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2884 .bitsLT(VT.getScalarType()))
2885 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2886 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2887 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2888 return Operand.getNode()->getOperand(0);
2890 if (OpOpcode == ISD::UNDEF)
2891 return getUNDEF(VT);
2894 // Basic sanity checking.
2895 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2896 && "Cannot BITCAST between types of different sizes!");
2897 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2898 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2899 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2900 if (OpOpcode == ISD::UNDEF)
2901 return getUNDEF(VT);
2903 case ISD::SCALAR_TO_VECTOR:
2904 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2905 (VT.getVectorElementType() == Operand.getValueType() ||
2906 (VT.getVectorElementType().isInteger() &&
2907 Operand.getValueType().isInteger() &&
2908 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2909 "Illegal SCALAR_TO_VECTOR node!");
2910 if (OpOpcode == ISD::UNDEF)
2911 return getUNDEF(VT);
2912 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2913 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2914 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2915 Operand.getConstantOperandVal(1) == 0 &&
2916 Operand.getOperand(0).getValueType() == VT)
2917 return Operand.getOperand(0);
2920 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2921 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2922 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2923 Operand.getNode()->getOperand(0));
2924 if (OpOpcode == ISD::FNEG) // --X -> X
2925 return Operand.getNode()->getOperand(0);
2928 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2929 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2934 SDVTList VTs = getVTList(VT);
2935 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2936 FoldingSetNodeID ID;
2937 SDValue Ops[1] = { Operand };
2938 AddNodeIDNode(ID, Opcode, VTs, Ops);
2940 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2941 return SDValue(E, 0);
2943 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2944 DL.getDebugLoc(), VTs, Operand);
2945 CSEMap.InsertNode(N, IP);
2947 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2948 DL.getDebugLoc(), VTs, Operand);
2952 return SDValue(N, 0);
2955 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2956 SDNode *Cst1, SDNode *Cst2) {
2957 // If the opcode is a target-specific ISD node, there's nothing we can
2958 // do here and the operand rules may not line up with the below, so
2960 if (Opcode >= ISD::BUILTIN_OP_END)
2963 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2964 SmallVector<SDValue, 4> Outputs;
2965 EVT SVT = VT.getScalarType();
2967 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2968 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2969 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2972 if (Scalar1 && Scalar2)
2973 // Scalar instruction.
2974 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2976 // For vectors extract each constant element into Inputs so we can constant
2977 // fold them individually.
2978 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2979 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2983 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2985 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2986 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2987 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2988 if (!V1 || !V2) // Not a constant, bail.
2991 if (V1->isOpaque() || V2->isOpaque())
2994 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2995 // FIXME: This is valid and could be handled by truncating the APInts.
2996 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2999 Inputs.push_back(std::make_pair(V1, V2));
3003 // We have a number of constant values, constant fold them element by element.
3004 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3005 const APInt &C1 = Inputs[I].first->getAPIntValue();
3006 const APInt &C2 = Inputs[I].second->getAPIntValue();
3010 Outputs.push_back(getConstant(C1 + C2, SVT));
3013 Outputs.push_back(getConstant(C1 - C2, SVT));
3016 Outputs.push_back(getConstant(C1 * C2, SVT));
3019 if (!C2.getBoolValue())
3021 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3024 if (!C2.getBoolValue())
3026 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3029 if (!C2.getBoolValue())
3031 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3034 if (!C2.getBoolValue())
3036 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3039 Outputs.push_back(getConstant(C1 & C2, SVT));
3042 Outputs.push_back(getConstant(C1 | C2, SVT));
3045 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3048 Outputs.push_back(getConstant(C1 << C2, SVT));
3051 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3054 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3057 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3060 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3067 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3068 "Expected a scalar or vector!"));
3070 // Handle the scalar case first.
3072 return Outputs.back();
3074 // We may have a vector type but a scalar result. Create a splat.
3075 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3077 // Build a big vector out of the scalar elements we generated.
3078 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3081 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3082 SDValue N2, bool nuw, bool nsw, bool exact) {
3083 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3084 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3087 case ISD::TokenFactor:
3088 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3089 N2.getValueType() == MVT::Other && "Invalid token factor!");
3090 // Fold trivial token factors.
3091 if (N1.getOpcode() == ISD::EntryToken) return N2;
3092 if (N2.getOpcode() == ISD::EntryToken) return N1;
3093 if (N1 == N2) return N1;
3095 case ISD::CONCAT_VECTORS:
3096 // Concat of UNDEFs is UNDEF.
3097 if (N1.getOpcode() == ISD::UNDEF &&
3098 N2.getOpcode() == ISD::UNDEF)
3099 return getUNDEF(VT);
3101 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3102 // one big BUILD_VECTOR.
3103 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3104 N2.getOpcode() == ISD::BUILD_VECTOR) {
3105 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3106 N1.getNode()->op_end());
3107 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3108 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3112 assert(VT.isInteger() && "This operator does not apply to FP types!");
3113 assert(N1.getValueType() == N2.getValueType() &&
3114 N1.getValueType() == VT && "Binary operator types must match!");
3115 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3116 // worth handling here.
3117 if (N2C && N2C->isNullValue())
3119 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3126 assert(VT.isInteger() && "This operator does not apply to FP types!");
3127 assert(N1.getValueType() == N2.getValueType() &&
3128 N1.getValueType() == VT && "Binary operator types must match!");
3129 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3130 // it's worth handling here.
3131 if (N2C && N2C->isNullValue())
3141 assert(VT.isInteger() && "This operator does not apply to FP types!");
3142 assert(N1.getValueType() == N2.getValueType() &&
3143 N1.getValueType() == VT && "Binary operator types must match!");
3150 if (getTarget().Options.UnsafeFPMath) {
3151 if (Opcode == ISD::FADD) {
3153 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3154 if (CFP->getValueAPF().isZero())
3157 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3158 if (CFP->getValueAPF().isZero())
3160 } else if (Opcode == ISD::FSUB) {
3162 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3163 if (CFP->getValueAPF().isZero())
3165 } else if (Opcode == ISD::FMUL) {
3166 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3169 // If the first operand isn't the constant, try the second
3171 CFP = dyn_cast<ConstantFPSDNode>(N2);
3178 return SDValue(CFP,0);
3180 if (CFP->isExactlyValue(1.0))
3185 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3186 assert(N1.getValueType() == N2.getValueType() &&
3187 N1.getValueType() == VT && "Binary operator types must match!");
3189 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3190 assert(N1.getValueType() == VT &&
3191 N1.getValueType().isFloatingPoint() &&
3192 N2.getValueType().isFloatingPoint() &&
3193 "Invalid FCOPYSIGN!");
3200 assert(VT == N1.getValueType() &&
3201 "Shift operators return type must be the same as their first arg");
3202 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3203 "Shifts only work on integers");
3204 assert((!VT.isVector() || VT == N2.getValueType()) &&
3205 "Vector shift amounts must be in the same as their first arg");
3206 // Verify that the shift amount VT is bit enough to hold valid shift
3207 // amounts. This catches things like trying to shift an i1024 value by an
3208 // i8, which is easy to fall into in generic code that uses
3209 // TLI.getShiftAmount().
3210 assert(N2.getValueType().getSizeInBits() >=
3211 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3212 "Invalid use of small shift amount with oversized value!");
3214 // Always fold shifts of i1 values so the code generator doesn't need to
3215 // handle them. Since we know the size of the shift has to be less than the
3216 // size of the value, the shift/rotate count is guaranteed to be zero.
3219 if (N2C && N2C->isNullValue())
3222 case ISD::FP_ROUND_INREG: {
3223 EVT EVT = cast<VTSDNode>(N2)->getVT();
3224 assert(VT == N1.getValueType() && "Not an inreg round!");
3225 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3226 "Cannot FP_ROUND_INREG integer types");
3227 assert(EVT.isVector() == VT.isVector() &&
3228 "FP_ROUND_INREG type should be vector iff the operand "
3230 assert((!EVT.isVector() ||
3231 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3232 "Vector element counts must match in FP_ROUND_INREG");
3233 assert(EVT.bitsLE(VT) && "Not rounding down!");
3235 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3239 assert(VT.isFloatingPoint() &&
3240 N1.getValueType().isFloatingPoint() &&
3241 VT.bitsLE(N1.getValueType()) &&
3242 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3243 if (N1.getValueType() == VT) return N1; // noop conversion.
3245 case ISD::AssertSext:
3246 case ISD::AssertZext: {
3247 EVT EVT = cast<VTSDNode>(N2)->getVT();
3248 assert(VT == N1.getValueType() && "Not an inreg extend!");
3249 assert(VT.isInteger() && EVT.isInteger() &&
3250 "Cannot *_EXTEND_INREG FP types");
3251 assert(!EVT.isVector() &&
3252 "AssertSExt/AssertZExt type should be the vector element type "
3253 "rather than the vector type!");
3254 assert(EVT.bitsLE(VT) && "Not extending!");
3255 if (VT == EVT) return N1; // noop assertion.
3258 case ISD::SIGN_EXTEND_INREG: {
3259 EVT EVT = cast<VTSDNode>(N2)->getVT();
3260 assert(VT == N1.getValueType() && "Not an inreg extend!");
3261 assert(VT.isInteger() && EVT.isInteger() &&
3262 "Cannot *_EXTEND_INREG FP types");
3263 assert(EVT.isVector() == VT.isVector() &&
3264 "SIGN_EXTEND_INREG type should be vector iff the operand "
3266 assert((!EVT.isVector() ||
3267 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3268 "Vector element counts must match in SIGN_EXTEND_INREG");
3269 assert(EVT.bitsLE(VT) && "Not extending!");
3270 if (EVT == VT) return N1; // Not actually extending
3273 APInt Val = N1C->getAPIntValue();
3274 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3275 Val <<= Val.getBitWidth()-FromBits;
3276 Val = Val.ashr(Val.getBitWidth()-FromBits);
3277 return getConstant(Val, VT);
3281 case ISD::EXTRACT_VECTOR_ELT:
3282 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3283 if (N1.getOpcode() == ISD::UNDEF)
3284 return getUNDEF(VT);
3286 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3287 // expanding copies of large vectors from registers.
3289 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3290 N1.getNumOperands() > 0) {
3292 N1.getOperand(0).getValueType().getVectorNumElements();
3293 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3294 N1.getOperand(N2C->getZExtValue() / Factor),
3295 getConstant(N2C->getZExtValue() % Factor,
3296 N2.getValueType()));
3299 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3300 // expanding large vector constants.
3301 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3302 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3304 if (VT != Elt.getValueType())
3305 // If the vector element type is not legal, the BUILD_VECTOR operands
3306 // are promoted and implicitly truncated, and the result implicitly
3307 // extended. Make that explicit here.
3308 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3313 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3314 // operations are lowered to scalars.
3315 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3316 // If the indices are the same, return the inserted element else
3317 // if the indices are known different, extract the element from
3318 // the original vector.
3319 SDValue N1Op2 = N1.getOperand(2);
3320 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3322 if (N1Op2C && N2C) {
3323 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3324 if (VT == N1.getOperand(1).getValueType())
3325 return N1.getOperand(1);
3327 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3330 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3334 case ISD::EXTRACT_ELEMENT:
3335 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3336 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3337 (N1.getValueType().isInteger() == VT.isInteger()) &&
3338 N1.getValueType() != VT &&
3339 "Wrong types for EXTRACT_ELEMENT!");
3341 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3342 // 64-bit integers into 32-bit parts. Instead of building the extract of
3343 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3344 if (N1.getOpcode() == ISD::BUILD_PAIR)
3345 return N1.getOperand(N2C->getZExtValue());
3347 // EXTRACT_ELEMENT of a constant int is also very common.
3348 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3349 unsigned ElementSize = VT.getSizeInBits();
3350 unsigned Shift = ElementSize * N2C->getZExtValue();
3351 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3352 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3355 case ISD::EXTRACT_SUBVECTOR: {
3357 if (VT.isSimple() && N1.getValueType().isSimple()) {
3358 assert(VT.isVector() && N1.getValueType().isVector() &&
3359 "Extract subvector VTs must be a vectors!");
3360 assert(VT.getVectorElementType() ==
3361 N1.getValueType().getVectorElementType() &&
3362 "Extract subvector VTs must have the same element type!");
3363 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3364 "Extract subvector must be from larger vector to smaller vector!");
3366 if (isa<ConstantSDNode>(Index.getNode())) {
3367 assert((VT.getVectorNumElements() +
3368 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3369 <= N1.getValueType().getVectorNumElements())
3370 && "Extract subvector overflow!");
3373 // Trivial extraction.
3374 if (VT.getSimpleVT() == N1.getSimpleValueType())
3381 // Perform trivial constant folding.
3382 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3383 if (SV.getNode()) return SV;
3385 // Canonicalize constant to RHS if commutative.
3386 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3387 std::swap(N1C, N2C);
3391 // Constant fold FP operations.
3392 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3393 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3395 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3396 // Canonicalize constant to RHS if commutative.
3397 std::swap(N1CFP, N2CFP);
3400 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3401 APFloat::opStatus s;
3404 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3405 if (s != APFloat::opInvalidOp)
3406 return getConstantFP(V1, VT);
3409 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3410 if (s!=APFloat::opInvalidOp)
3411 return getConstantFP(V1, VT);
3414 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3415 if (s!=APFloat::opInvalidOp)
3416 return getConstantFP(V1, VT);
3419 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3420 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3421 return getConstantFP(V1, VT);
3424 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3425 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3426 return getConstantFP(V1, VT);
3428 case ISD::FCOPYSIGN:
3430 return getConstantFP(V1, VT);
3435 if (Opcode == ISD::FP_ROUND) {
3436 APFloat V = N1CFP->getValueAPF(); // make copy
3438 // This can return overflow, underflow, or inexact; we don't care.
3439 // FIXME need to be more flexible about rounding mode.
3440 (void)V.convert(EVTToAPFloatSemantics(VT),
3441 APFloat::rmNearestTiesToEven, &ignored);
3442 return getConstantFP(V, VT);
3446 // Canonicalize an UNDEF to the RHS, even over a constant.
3447 if (N1.getOpcode() == ISD::UNDEF) {
3448 if (isCommutativeBinOp(Opcode)) {
3452 case ISD::FP_ROUND_INREG:
3453 case ISD::SIGN_EXTEND_INREG:
3459 return N1; // fold op(undef, arg2) -> undef
3467 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3468 // For vectors, we can't easily build an all zero vector, just return
3475 // Fold a bunch of operators when the RHS is undef.
3476 if (N2.getOpcode() == ISD::UNDEF) {
3479 if (N1.getOpcode() == ISD::UNDEF)
3480 // Handle undef ^ undef -> 0 special case. This is a common
3482 return getConstant(0, VT);
3492 return N2; // fold op(arg1, undef) -> undef
3498 if (getTarget().Options.UnsafeFPMath)
3506 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3507 // For vectors, we can't easily build an all zero vector, just return
3512 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3513 // For vectors, we can't easily build an all one vector, just return
3521 // Memoize this node if possible.
3523 SDVTList VTs = getVTList(VT);
3524 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3525 if (VT != MVT::Glue) {
3526 SDValue Ops[] = {N1, N2};
3527 FoldingSetNodeID ID;
3528 AddNodeIDNode(ID, Opcode, VTs, Ops);
3530 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3532 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3533 return SDValue(E, 0);
3535 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3537 CSEMap.InsertNode(N, IP);
3540 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3544 return SDValue(N, 0);
3547 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3548 SDValue N1, SDValue N2, SDValue N3) {
3549 // Perform various simplifications.
3550 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3553 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3554 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3555 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3556 if (N1CFP && N2CFP && N3CFP) {
3557 APFloat V1 = N1CFP->getValueAPF();
3558 const APFloat &V2 = N2CFP->getValueAPF();
3559 const APFloat &V3 = N3CFP->getValueAPF();
3560 APFloat::opStatus s =
3561 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3562 if (s != APFloat::opInvalidOp)
3563 return getConstantFP(V1, VT);
3567 case ISD::CONCAT_VECTORS:
3568 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3569 // one big BUILD_VECTOR.
3570 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3571 N2.getOpcode() == ISD::BUILD_VECTOR &&
3572 N3.getOpcode() == ISD::BUILD_VECTOR) {
3573 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3574 N1.getNode()->op_end());
3575 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3576 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3577 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3581 // Use FoldSetCC to simplify SETCC's.
3582 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3583 if (Simp.getNode()) return Simp;
3588 if (N1C->getZExtValue())
3589 return N2; // select true, X, Y -> X
3590 return N3; // select false, X, Y -> Y
3593 if (N2 == N3) return N2; // select C, X, X -> X
3595 case ISD::VECTOR_SHUFFLE:
3596 llvm_unreachable("should use getVectorShuffle constructor!");
3597 case ISD::INSERT_SUBVECTOR: {
3599 if (VT.isSimple() && N1.getValueType().isSimple()
3600 && N2.getValueType().isSimple()) {
3601 assert(VT.isVector() && N1.getValueType().isVector() &&
3602 N2.getValueType().isVector() &&
3603 "Insert subvector VTs must be a vectors");
3604 assert(VT == N1.getValueType() &&
3605 "Dest and insert subvector source types must match!");
3606 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3607 "Insert subvector must be from smaller vector to larger vector!");
3608 if (isa<ConstantSDNode>(Index.getNode())) {
3609 assert((N2.getValueType().getVectorNumElements() +
3610 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3611 <= VT.getVectorNumElements())
3612 && "Insert subvector overflow!");
3615 // Trivial insertion.
3616 if (VT.getSimpleVT() == N2.getSimpleValueType())
3622 // Fold bit_convert nodes from a type to themselves.
3623 if (N1.getValueType() == VT)
3628 // Memoize node if it doesn't produce a flag.
3630 SDVTList VTs = getVTList(VT);
3631 if (VT != MVT::Glue) {
3632 SDValue Ops[] = { N1, N2, N3 };
3633 FoldingSetNodeID ID;
3634 AddNodeIDNode(ID, Opcode, VTs, Ops);
3636 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3637 return SDValue(E, 0);
3639 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3640 DL.getDebugLoc(), VTs, N1, N2, N3);
3641 CSEMap.InsertNode(N, IP);
3643 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3644 DL.getDebugLoc(), VTs, N1, N2, N3);
3648 return SDValue(N, 0);
3651 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3652 SDValue N1, SDValue N2, SDValue N3,
3654 SDValue Ops[] = { N1, N2, N3, N4 };
3655 return getNode(Opcode, DL, VT, Ops);
3658 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3659 SDValue N1, SDValue N2, SDValue N3,
3660 SDValue N4, SDValue N5) {
3661 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3662 return getNode(Opcode, DL, VT, Ops);
3665 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3666 /// the incoming stack arguments to be loaded from the stack.
3667 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3668 SmallVector<SDValue, 8> ArgChains;
3670 // Include the original chain at the beginning of the list. When this is
3671 // used by target LowerCall hooks, this helps legalize find the
3672 // CALLSEQ_BEGIN node.
3673 ArgChains.push_back(Chain);
3675 // Add a chain value for each stack argument.
3676 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3677 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3678 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3679 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3680 if (FI->getIndex() < 0)
3681 ArgChains.push_back(SDValue(L, 1));
3683 // Build a tokenfactor for all the chains.
3684 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3687 /// getMemsetValue - Vectorized representation of the memset value
3689 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3691 assert(Value.getOpcode() != ISD::UNDEF);
3693 unsigned NumBits = VT.getScalarType().getSizeInBits();
3694 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3695 assert(C->getAPIntValue().getBitWidth() == 8);
3696 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3698 return DAG.getConstant(Val, VT);
3699 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3702 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3704 // Use a multiplication with 0x010101... to extend the input to the
3706 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3707 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3713 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3714 /// used when a memcpy is turned into a memset when the source is a constant
3716 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3717 const TargetLowering &TLI, StringRef Str) {
3718 // Handle vector with all elements zero.
3721 return DAG.getConstant(0, VT);
3722 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3723 return DAG.getConstantFP(0.0, VT);
3724 else if (VT.isVector()) {
3725 unsigned NumElts = VT.getVectorNumElements();
3726 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3727 return DAG.getNode(ISD::BITCAST, dl, VT,
3728 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3731 llvm_unreachable("Expected type!");
3734 assert(!VT.isVector() && "Can't handle vector type here!");
3735 unsigned NumVTBits = VT.getSizeInBits();
3736 unsigned NumVTBytes = NumVTBits / 8;
3737 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3739 APInt Val(NumVTBits, 0);
3740 if (TLI.isLittleEndian()) {
3741 for (unsigned i = 0; i != NumBytes; ++i)
3742 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3744 for (unsigned i = 0; i != NumBytes; ++i)
3745 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3748 // If the "cost" of materializing the integer immediate is less than the cost
3749 // of a load, then it is cost effective to turn the load into the immediate.
3750 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3751 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3752 return DAG.getConstant(Val, VT);
3753 return SDValue(nullptr, 0);
3756 /// getMemBasePlusOffset - Returns base and offset node for the
3758 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3759 SelectionDAG &DAG) {
3760 EVT VT = Base.getValueType();
3761 return DAG.getNode(ISD::ADD, dl,
3762 VT, Base, DAG.getConstant(Offset, VT));
3765 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3767 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3768 unsigned SrcDelta = 0;
3769 GlobalAddressSDNode *G = nullptr;
3770 if (Src.getOpcode() == ISD::GlobalAddress)
3771 G = cast<GlobalAddressSDNode>(Src);
3772 else if (Src.getOpcode() == ISD::ADD &&
3773 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3774 Src.getOperand(1).getOpcode() == ISD::Constant) {
3775 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3776 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3781 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3784 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3785 /// to replace the memset / memcpy. Return true if the number of memory ops
3786 /// is below the threshold. It returns the types of the sequence of
3787 /// memory ops to perform memset / memcpy by reference.
3788 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3789 unsigned Limit, uint64_t Size,
3790 unsigned DstAlign, unsigned SrcAlign,
3796 const TargetLowering &TLI) {
3797 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3798 "Expecting memcpy / memset source to meet alignment requirement!");
3799 // If 'SrcAlign' is zero, that means the memory operation does not need to
3800 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3801 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3802 // is the specified alignment of the memory operation. If it is zero, that
3803 // means it's possible to change the alignment of the destination.
3804 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3805 // not need to be loaded.
3806 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3807 IsMemset, ZeroMemset, MemcpyStrSrc,
3808 DAG.getMachineFunction());
3810 if (VT == MVT::Other) {
3812 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3813 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3814 VT = TLI.getPointerTy();
3816 switch (DstAlign & 7) {
3817 case 0: VT = MVT::i64; break;
3818 case 4: VT = MVT::i32; break;
3819 case 2: VT = MVT::i16; break;
3820 default: VT = MVT::i8; break;
3825 while (!TLI.isTypeLegal(LVT))
3826 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3827 assert(LVT.isInteger());
3833 unsigned NumMemOps = 0;
3835 unsigned VTSize = VT.getSizeInBits() / 8;
3836 while (VTSize > Size) {
3837 // For now, only use non-vector load / store's for the left-over pieces.
3842 if (VT.isVector() || VT.isFloatingPoint()) {
3843 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3844 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3845 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3847 else if (NewVT == MVT::i64 &&
3848 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3849 TLI.isSafeMemOpType(MVT::f64)) {
3850 // i64 is usually not legal on 32-bit targets, but f64 may be.
3858 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3859 if (NewVT == MVT::i8)
3861 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3863 NewVTSize = NewVT.getSizeInBits() / 8;
3865 // If the new VT cannot cover all of the remaining bits, then consider
3866 // issuing a (or a pair of) unaligned and overlapping load / store.
3867 // FIXME: Only does this for 64-bit or more since we don't have proper
3868 // cost model for unaligned load / store.
3871 if (NumMemOps && AllowOverlap &&
3872 VTSize >= 8 && NewVTSize < Size &&
3873 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
3881 if (++NumMemOps > Limit)
3884 MemOps.push_back(VT);
3891 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3892 SDValue Chain, SDValue Dst,
3893 SDValue Src, uint64_t Size,
3894 unsigned Align, bool isVol,
3896 MachinePointerInfo DstPtrInfo,
3897 MachinePointerInfo SrcPtrInfo) {
3898 // Turn a memcpy of undef to nop.
3899 if (Src.getOpcode() == ISD::UNDEF)
3902 // Expand memcpy to a series of load and store ops if the size operand falls
3903 // below a certain threshold.
3904 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3905 // rather than maybe a humongous number of loads and stores.
3906 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3907 std::vector<EVT> MemOps;
3908 bool DstAlignCanChange = false;
3909 MachineFunction &MF = DAG.getMachineFunction();
3910 MachineFrameInfo *MFI = MF.getFrameInfo();
3912 MF.getFunction()->getAttributes().
3913 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3914 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3915 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3916 DstAlignCanChange = true;
3917 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3918 if (Align > SrcAlign)
3921 bool CopyFromStr = isMemSrcFromString(Src, Str);
3922 bool isZeroStr = CopyFromStr && Str.empty();
3923 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3925 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3926 (DstAlignCanChange ? 0 : Align),
3927 (isZeroStr ? 0 : SrcAlign),
3928 false, false, CopyFromStr, true, DAG, TLI))
3931 if (DstAlignCanChange) {
3932 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3933 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3935 // Don't promote to an alignment that would require dynamic stack
3937 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3938 if (!TRI->needsStackRealignment(MF))
3939 while (NewAlign > Align &&
3940 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3943 if (NewAlign > Align) {
3944 // Give the stack frame object a larger alignment if needed.
3945 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3946 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3951 SmallVector<SDValue, 8> OutChains;
3952 unsigned NumMemOps = MemOps.size();
3953 uint64_t SrcOff = 0, DstOff = 0;
3954 for (unsigned i = 0; i != NumMemOps; ++i) {
3956 unsigned VTSize = VT.getSizeInBits() / 8;
3957 SDValue Value, Store;
3959 if (VTSize > Size) {
3960 // Issuing an unaligned load / store pair that overlaps with the previous
3961 // pair. Adjust the offset accordingly.
3962 assert(i == NumMemOps-1 && i != 0);
3963 SrcOff -= VTSize - Size;
3964 DstOff -= VTSize - Size;
3968 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3969 // It's unlikely a store of a vector immediate can be done in a single
3970 // instruction. It would require a load from a constantpool first.
3971 // We only handle zero vectors here.
3972 // FIXME: Handle other cases where store of vector immediate is done in
3973 // a single instruction.
3974 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3975 if (Value.getNode())
3976 Store = DAG.getStore(Chain, dl, Value,
3977 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3978 DstPtrInfo.getWithOffset(DstOff), isVol,
3982 if (!Store.getNode()) {
3983 // The type might not be legal for the target. This should only happen
3984 // if the type is smaller than a legal type, as on PPC, so the right
3985 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3986 // to Load/Store if NVT==VT.
3987 // FIXME does the case above also need this?
3988 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3989 assert(NVT.bitsGE(VT));
3990 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3991 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3992 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3993 MinAlign(SrcAlign, SrcOff));
3994 Store = DAG.getTruncStore(Chain, dl, Value,
3995 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3996 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3999 OutChains.push_back(Store);
4005 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4008 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4009 SDValue Chain, SDValue Dst,
4010 SDValue Src, uint64_t Size,
4011 unsigned Align, bool isVol,
4013 MachinePointerInfo DstPtrInfo,
4014 MachinePointerInfo SrcPtrInfo) {
4015 // Turn a memmove of undef to nop.
4016 if (Src.getOpcode() == ISD::UNDEF)
4019 // Expand memmove to a series of load and store ops if the size operand falls
4020 // below a certain threshold.
4021 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4022 std::vector<EVT> MemOps;
4023 bool DstAlignCanChange = false;
4024 MachineFunction &MF = DAG.getMachineFunction();
4025 MachineFrameInfo *MFI = MF.getFrameInfo();
4026 bool OptSize = MF.getFunction()->getAttributes().
4027 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4028 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4029 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4030 DstAlignCanChange = true;
4031 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4032 if (Align > SrcAlign)
4034 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4036 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4037 (DstAlignCanChange ? 0 : Align), SrcAlign,
4038 false, false, false, false, DAG, TLI))
4041 if (DstAlignCanChange) {
4042 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4043 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4044 if (NewAlign > Align) {
4045 // Give the stack frame object a larger alignment if needed.
4046 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4047 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4052 uint64_t SrcOff = 0, DstOff = 0;
4053 SmallVector<SDValue, 8> LoadValues;
4054 SmallVector<SDValue, 8> LoadChains;
4055 SmallVector<SDValue, 8> OutChains;
4056 unsigned NumMemOps = MemOps.size();
4057 for (unsigned i = 0; i < NumMemOps; i++) {
4059 unsigned VTSize = VT.getSizeInBits() / 8;
4062 Value = DAG.getLoad(VT, dl, Chain,
4063 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4064 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4065 false, false, SrcAlign);
4066 LoadValues.push_back(Value);
4067 LoadChains.push_back(Value.getValue(1));
4070 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4072 for (unsigned i = 0; i < NumMemOps; i++) {
4074 unsigned VTSize = VT.getSizeInBits() / 8;
4077 Store = DAG.getStore(Chain, dl, LoadValues[i],
4078 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4079 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4080 OutChains.push_back(Store);
4084 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4087 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4090 /// \param DAG Selection DAG where lowered code is placed.
4091 /// \param dl Link to corresponding IR location.
4092 /// \param Chain Control flow dependency.
4093 /// \param Dst Pointer to destination memory location.
4094 /// \param Src Value of byte to write into the memory.
4095 /// \param Size Number of bytes to write.
4096 /// \param Align Alignment of the destination in bytes.
4097 /// \param isVol True if destination is volatile.
4098 /// \param DstPtrInfo IR information on the memory pointer.
4099 /// \returns New head in the control flow, if lowering was successful, empty
4100 /// SDValue otherwise.
4102 /// The function tries to replace 'llvm.memset' intrinsic with several store
4103 /// operations and value calculation code. This is usually profitable for small
4105 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4106 SDValue Chain, SDValue Dst,
4107 SDValue Src, uint64_t Size,
4108 unsigned Align, bool isVol,
4109 MachinePointerInfo DstPtrInfo) {
4110 // Turn a memset of undef to nop.
4111 if (Src.getOpcode() == ISD::UNDEF)
4114 // Expand memset to a series of load/store ops if the size operand
4115 // falls below a certain threshold.
4116 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4117 std::vector<EVT> MemOps;
4118 bool DstAlignCanChange = false;
4119 MachineFunction &MF = DAG.getMachineFunction();
4120 MachineFrameInfo *MFI = MF.getFrameInfo();
4121 bool OptSize = MF.getFunction()->getAttributes().
4122 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4123 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4124 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4125 DstAlignCanChange = true;
4127 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4128 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4129 Size, (DstAlignCanChange ? 0 : Align), 0,
4130 true, IsZeroVal, false, true, DAG, TLI))
4133 if (DstAlignCanChange) {
4134 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4135 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4136 if (NewAlign > Align) {
4137 // Give the stack frame object a larger alignment if needed.
4138 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4139 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4144 SmallVector<SDValue, 8> OutChains;
4145 uint64_t DstOff = 0;
4146 unsigned NumMemOps = MemOps.size();
4148 // Find the largest store and generate the bit pattern for it.
4149 EVT LargestVT = MemOps[0];
4150 for (unsigned i = 1; i < NumMemOps; i++)
4151 if (MemOps[i].bitsGT(LargestVT))
4152 LargestVT = MemOps[i];
4153 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4155 for (unsigned i = 0; i < NumMemOps; i++) {
4157 unsigned VTSize = VT.getSizeInBits() / 8;
4158 if (VTSize > Size) {
4159 // Issuing an unaligned load / store pair that overlaps with the previous
4160 // pair. Adjust the offset accordingly.
4161 assert(i == NumMemOps-1 && i != 0);
4162 DstOff -= VTSize - Size;
4165 // If this store is smaller than the largest store see whether we can get
4166 // the smaller value for free with a truncate.
4167 SDValue Value = MemSetValue;
4168 if (VT.bitsLT(LargestVT)) {
4169 if (!LargestVT.isVector() && !VT.isVector() &&
4170 TLI.isTruncateFree(LargestVT, VT))
4171 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4173 Value = getMemsetValue(Src, VT, DAG, dl);
4175 assert(Value.getValueType() == VT && "Value with wrong type.");
4176 SDValue Store = DAG.getStore(Chain, dl, Value,
4177 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4178 DstPtrInfo.getWithOffset(DstOff),
4179 isVol, false, Align);
4180 OutChains.push_back(Store);
4181 DstOff += VT.getSizeInBits() / 8;
4185 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4188 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4189 SDValue Src, SDValue Size,
4190 unsigned Align, bool isVol, bool AlwaysInline,
4191 MachinePointerInfo DstPtrInfo,
4192 MachinePointerInfo SrcPtrInfo) {
4193 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4195 // Check to see if we should lower the memcpy to loads and stores first.
4196 // For cases within the target-specified limits, this is the best choice.
4197 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4199 // Memcpy with size zero? Just return the original chain.
4200 if (ConstantSize->isNullValue())
4203 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4204 ConstantSize->getZExtValue(),Align,
4205 isVol, false, DstPtrInfo, SrcPtrInfo);
4206 if (Result.getNode())
4210 // Then check to see if we should lower the memcpy with target-specific
4211 // code. If the target chooses to do this, this is the next best.
4213 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4214 isVol, AlwaysInline,
4215 DstPtrInfo, SrcPtrInfo);
4216 if (Result.getNode())
4219 // If we really need inline code and the target declined to provide it,
4220 // use a (potentially long) sequence of loads and stores.
4222 assert(ConstantSize && "AlwaysInline requires a constant size!");
4223 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4224 ConstantSize->getZExtValue(), Align, isVol,
4225 true, DstPtrInfo, SrcPtrInfo);
4228 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4229 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4230 // respect volatile, so they may do things like read or write memory
4231 // beyond the given memory regions. But fixing this isn't easy, and most
4232 // people don't care.
4234 const TargetLowering *TLI = TM.getTargetLowering();
4236 // Emit a library call.
4237 TargetLowering::ArgListTy Args;
4238 TargetLowering::ArgListEntry Entry;
4239 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4240 Entry.Node = Dst; Args.push_back(Entry);
4241 Entry.Node = Src; Args.push_back(Entry);
4242 Entry.Node = Size; Args.push_back(Entry);
4243 // FIXME: pass in SDLoc
4244 TargetLowering::CallLoweringInfo CLI(*this);
4245 CLI.setDebugLoc(dl).setChain(Chain)
4246 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4247 Type::getVoidTy(*getContext()),
4248 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4249 TLI->getPointerTy()), std::move(Args), 0)
4250 .setDiscardResult();
4251 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4253 return CallResult.second;
4256 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4257 SDValue Src, SDValue Size,
4258 unsigned Align, bool isVol,
4259 MachinePointerInfo DstPtrInfo,
4260 MachinePointerInfo SrcPtrInfo) {
4261 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4263 // Check to see if we should lower the memmove to loads and stores first.
4264 // For cases within the target-specified limits, this is the best choice.
4265 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4267 // Memmove with size zero? Just return the original chain.
4268 if (ConstantSize->isNullValue())
4272 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4273 ConstantSize->getZExtValue(), Align, isVol,
4274 false, DstPtrInfo, SrcPtrInfo);
4275 if (Result.getNode())
4279 // Then check to see if we should lower the memmove with target-specific
4280 // code. If the target chooses to do this, this is the next best.
4282 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4283 DstPtrInfo, SrcPtrInfo);
4284 if (Result.getNode())
4287 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4288 // not be safe. See memcpy above for more details.
4290 const TargetLowering *TLI = TM.getTargetLowering();
4292 // Emit a library call.
4293 TargetLowering::ArgListTy Args;
4294 TargetLowering::ArgListEntry Entry;
4295 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4296 Entry.Node = Dst; Args.push_back(Entry);
4297 Entry.Node = Src; Args.push_back(Entry);
4298 Entry.Node = Size; Args.push_back(Entry);
4299 // FIXME: pass in SDLoc
4300 TargetLowering::CallLoweringInfo CLI(*this);
4301 CLI.setDebugLoc(dl).setChain(Chain)
4302 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4303 Type::getVoidTy(*getContext()),
4304 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4305 TLI->getPointerTy()), std::move(Args), 0)
4306 .setDiscardResult();
4307 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4309 return CallResult.second;
4312 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4313 SDValue Src, SDValue Size,
4314 unsigned Align, bool isVol,
4315 MachinePointerInfo DstPtrInfo) {
4316 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4318 // Check to see if we should lower the memset to stores first.
4319 // For cases within the target-specified limits, this is the best choice.
4320 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4322 // Memset with size zero? Just return the original chain.
4323 if (ConstantSize->isNullValue())
4327 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4328 Align, isVol, DstPtrInfo);
4330 if (Result.getNode())
4334 // Then check to see if we should lower the memset with target-specific
4335 // code. If the target chooses to do this, this is the next best.
4337 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4339 if (Result.getNode())
4342 // Emit a library call.
4343 const TargetLowering *TLI = TM.getTargetLowering();
4344 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4345 TargetLowering::ArgListTy Args;
4346 TargetLowering::ArgListEntry Entry;
4347 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4348 Args.push_back(Entry);
4349 // Extend or truncate the argument to be an i32 value for the call.
4350 if (Src.getValueType().bitsGT(MVT::i32))
4351 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4353 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4355 Entry.Ty = Type::getInt32Ty(*getContext());
4356 Entry.isSExt = true;
4357 Args.push_back(Entry);
4359 Entry.Ty = IntPtrTy;
4360 Entry.isSExt = false;
4361 Args.push_back(Entry);
4363 // FIXME: pass in SDLoc
4364 TargetLowering::CallLoweringInfo CLI(*this);
4365 CLI.setDebugLoc(dl).setChain(Chain)
4366 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4367 Type::getVoidTy(*getContext()),
4368 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4369 TLI->getPointerTy()), std::move(Args), 0)
4370 .setDiscardResult();
4372 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4373 return CallResult.second;
4376 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4377 SDVTList VTList, ArrayRef<SDValue> Ops,
4378 MachineMemOperand *MMO,
4379 AtomicOrdering SuccessOrdering,
4380 AtomicOrdering FailureOrdering,
4381 SynchronizationScope SynchScope) {
4382 FoldingSetNodeID ID;
4383 ID.AddInteger(MemVT.getRawBits());
4384 AddNodeIDNode(ID, Opcode, VTList, Ops);
4385 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4387 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4388 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4389 return SDValue(E, 0);
4392 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4393 // SDNode doesn't have access to it. This memory will be "leaked" when
4394 // the node is deallocated, but recovered when the allocator is released.
4395 // If the number of operands is less than 5 we use AtomicSDNode's internal
4397 unsigned NumOps = Ops.size();
4398 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4401 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4402 dl.getDebugLoc(), VTList, MemVT,
4403 Ops.data(), DynOps, NumOps, MMO,
4404 SuccessOrdering, FailureOrdering,
4406 CSEMap.InsertNode(N, IP);
4408 return SDValue(N, 0);
4411 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4412 SDVTList VTList, ArrayRef<SDValue> Ops,
4413 MachineMemOperand *MMO,
4414 AtomicOrdering Ordering,
4415 SynchronizationScope SynchScope) {
4416 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4417 Ordering, SynchScope);
4420 SDValue SelectionDAG::getAtomicCmpSwap(
4421 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4422 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4423 unsigned Alignment, AtomicOrdering SuccessOrdering,
4424 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4425 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4426 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4427 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4429 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4430 Alignment = getEVTAlignment(MemVT);
4432 MachineFunction &MF = getMachineFunction();
4434 // FIXME: Volatile isn't really correct; we should keep track of atomic
4435 // orderings in the memoperand.
4436 unsigned Flags = MachineMemOperand::MOVolatile;
4437 Flags |= MachineMemOperand::MOLoad;
4438 Flags |= MachineMemOperand::MOStore;
4440 MachineMemOperand *MMO =
4441 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4443 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4444 SuccessOrdering, FailureOrdering, SynchScope);
4447 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4448 SDVTList VTs, SDValue Chain, SDValue Ptr,
4449 SDValue Cmp, SDValue Swp,
4450 MachineMemOperand *MMO,
4451 AtomicOrdering SuccessOrdering,
4452 AtomicOrdering FailureOrdering,
4453 SynchronizationScope SynchScope) {
4454 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4455 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4456 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4458 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4459 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4460 SuccessOrdering, FailureOrdering, SynchScope);
4463 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4465 SDValue Ptr, SDValue Val,
4466 const Value* PtrVal,
4468 AtomicOrdering Ordering,
4469 SynchronizationScope SynchScope) {
4470 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4471 Alignment = getEVTAlignment(MemVT);
4473 MachineFunction &MF = getMachineFunction();
4474 // An atomic store does not load. An atomic load does not store.
4475 // (An atomicrmw obviously both loads and stores.)
4476 // For now, atomics are considered to be volatile always, and they are
4478 // FIXME: Volatile isn't really correct; we should keep track of atomic
4479 // orderings in the memoperand.
4480 unsigned Flags = MachineMemOperand::MOVolatile;
4481 if (Opcode != ISD::ATOMIC_STORE)
4482 Flags |= MachineMemOperand::MOLoad;
4483 if (Opcode != ISD::ATOMIC_LOAD)
4484 Flags |= MachineMemOperand::MOStore;
4486 MachineMemOperand *MMO =
4487 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4488 MemVT.getStoreSize(), Alignment);
4490 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4491 Ordering, SynchScope);
4494 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4496 SDValue Ptr, SDValue Val,
4497 MachineMemOperand *MMO,
4498 AtomicOrdering Ordering,
4499 SynchronizationScope SynchScope) {
4500 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4501 Opcode == ISD::ATOMIC_LOAD_SUB ||
4502 Opcode == ISD::ATOMIC_LOAD_AND ||
4503 Opcode == ISD::ATOMIC_LOAD_OR ||
4504 Opcode == ISD::ATOMIC_LOAD_XOR ||
4505 Opcode == ISD::ATOMIC_LOAD_NAND ||
4506 Opcode == ISD::ATOMIC_LOAD_MIN ||
4507 Opcode == ISD::ATOMIC_LOAD_MAX ||
4508 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4509 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4510 Opcode == ISD::ATOMIC_SWAP ||
4511 Opcode == ISD::ATOMIC_STORE) &&
4512 "Invalid Atomic Op");
4514 EVT VT = Val.getValueType();
4516 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4517 getVTList(VT, MVT::Other);
4518 SDValue Ops[] = {Chain, Ptr, Val};
4519 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4522 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4523 EVT VT, SDValue Chain,
4525 MachineMemOperand *MMO,
4526 AtomicOrdering Ordering,
4527 SynchronizationScope SynchScope) {
4528 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4530 SDVTList VTs = getVTList(VT, MVT::Other);
4531 SDValue Ops[] = {Chain, Ptr};
4532 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4535 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4536 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4537 if (Ops.size() == 1)
4540 SmallVector<EVT, 4> VTs;
4541 VTs.reserve(Ops.size());
4542 for (unsigned i = 0; i < Ops.size(); ++i)
4543 VTs.push_back(Ops[i].getValueType());
4544 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4548 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4549 ArrayRef<SDValue> Ops,
4550 EVT MemVT, MachinePointerInfo PtrInfo,
4551 unsigned Align, bool Vol,
4552 bool ReadMem, bool WriteMem) {
4553 if (Align == 0) // Ensure that codegen never sees alignment 0
4554 Align = getEVTAlignment(MemVT);
4556 MachineFunction &MF = getMachineFunction();
4559 Flags |= MachineMemOperand::MOStore;
4561 Flags |= MachineMemOperand::MOLoad;
4563 Flags |= MachineMemOperand::MOVolatile;
4564 MachineMemOperand *MMO =
4565 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4567 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4571 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4572 ArrayRef<SDValue> Ops, EVT MemVT,
4573 MachineMemOperand *MMO) {
4574 assert((Opcode == ISD::INTRINSIC_VOID ||
4575 Opcode == ISD::INTRINSIC_W_CHAIN ||
4576 Opcode == ISD::PREFETCH ||
4577 Opcode == ISD::LIFETIME_START ||
4578 Opcode == ISD::LIFETIME_END ||
4579 (Opcode <= INT_MAX &&
4580 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4581 "Opcode is not a memory-accessing opcode!");
4583 // Memoize the node unless it returns a flag.
4584 MemIntrinsicSDNode *N;
4585 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4586 FoldingSetNodeID ID;
4587 AddNodeIDNode(ID, Opcode, VTList, Ops);
4588 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4590 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4591 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4592 return SDValue(E, 0);
4595 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4596 dl.getDebugLoc(), VTList, Ops,
4598 CSEMap.InsertNode(N, IP);
4600 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4601 dl.getDebugLoc(), VTList, Ops,
4605 return SDValue(N, 0);
4608 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4609 /// MachinePointerInfo record from it. This is particularly useful because the
4610 /// code generator has many cases where it doesn't bother passing in a
4611 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4612 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4613 // If this is FI+Offset, we can model it.
4614 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4615 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4617 // If this is (FI+Offset1)+Offset2, we can model it.
4618 if (Ptr.getOpcode() != ISD::ADD ||
4619 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4620 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4621 return MachinePointerInfo();
4623 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4624 return MachinePointerInfo::getFixedStack(FI, Offset+
4625 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
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, SDValue OffsetOp) {
4633 // If the 'Offset' value isn't a constant, we can't handle this.
4634 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4635 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4636 if (OffsetOp.getOpcode() == ISD::UNDEF)
4637 return InferPointerInfo(Ptr);
4638 return MachinePointerInfo();
4643 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4644 EVT VT, SDLoc dl, SDValue Chain,
4645 SDValue Ptr, SDValue Offset,
4646 MachinePointerInfo PtrInfo, EVT MemVT,
4647 bool isVolatile, bool isNonTemporal, bool isInvariant,
4648 unsigned Alignment, const AAMDNodes &AAInfo,
4649 const MDNode *Ranges) {
4650 assert(Chain.getValueType() == MVT::Other &&
4651 "Invalid chain type");
4652 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4653 Alignment = getEVTAlignment(VT);
4655 unsigned Flags = MachineMemOperand::MOLoad;
4657 Flags |= MachineMemOperand::MOVolatile;
4659 Flags |= MachineMemOperand::MONonTemporal;
4661 Flags |= MachineMemOperand::MOInvariant;
4663 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4665 if (PtrInfo.V.isNull())
4666 PtrInfo = InferPointerInfo(Ptr, Offset);
4668 MachineFunction &MF = getMachineFunction();
4669 MachineMemOperand *MMO =
4670 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4672 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4676 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4677 EVT VT, SDLoc dl, SDValue Chain,
4678 SDValue Ptr, SDValue Offset, EVT MemVT,
4679 MachineMemOperand *MMO) {
4681 ExtType = ISD::NON_EXTLOAD;
4682 } else if (ExtType == ISD::NON_EXTLOAD) {
4683 assert(VT == MemVT && "Non-extending load from different memory type!");
4686 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4687 "Should only be an extending load, not truncating!");
4688 assert(VT.isInteger() == MemVT.isInteger() &&
4689 "Cannot convert from FP to Int or Int -> FP!");
4690 assert(VT.isVector() == MemVT.isVector() &&
4691 "Cannot use trunc store to convert to or from a vector!");
4692 assert((!VT.isVector() ||
4693 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4694 "Cannot use trunc store to change the number of vector elements!");
4697 bool Indexed = AM != ISD::UNINDEXED;
4698 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4699 "Unindexed load with an offset!");
4701 SDVTList VTs = Indexed ?
4702 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4703 SDValue Ops[] = { Chain, Ptr, Offset };
4704 FoldingSetNodeID ID;
4705 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4706 ID.AddInteger(MemVT.getRawBits());
4707 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4708 MMO->isNonTemporal(),
4709 MMO->isInvariant()));
4710 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4712 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4713 cast<LoadSDNode>(E)->refineAlignment(MMO);
4714 return SDValue(E, 0);
4716 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4717 dl.getDebugLoc(), VTs, AM, ExtType,
4719 CSEMap.InsertNode(N, IP);
4721 return SDValue(N, 0);
4724 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4725 SDValue Chain, SDValue Ptr,
4726 MachinePointerInfo PtrInfo,
4727 bool isVolatile, bool isNonTemporal,
4728 bool isInvariant, unsigned Alignment,
4729 const AAMDNodes &AAInfo,
4730 const MDNode *Ranges) {
4731 SDValue Undef = getUNDEF(Ptr.getValueType());
4732 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4733 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4737 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4738 SDValue Chain, SDValue Ptr,
4739 MachineMemOperand *MMO) {
4740 SDValue Undef = getUNDEF(Ptr.getValueType());
4741 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4745 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4746 SDValue Chain, SDValue Ptr,
4747 MachinePointerInfo PtrInfo, EVT MemVT,
4748 bool isVolatile, bool isNonTemporal,
4749 unsigned Alignment, const AAMDNodes &AAInfo) {
4750 SDValue Undef = getUNDEF(Ptr.getValueType());
4751 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4752 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4757 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4758 SDValue Chain, SDValue Ptr, EVT MemVT,
4759 MachineMemOperand *MMO) {
4760 SDValue Undef = getUNDEF(Ptr.getValueType());
4761 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4766 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4767 SDValue Offset, ISD::MemIndexedMode AM) {
4768 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4769 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4770 "Load is already a indexed load!");
4771 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4772 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4773 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4774 false, LD->getAlignment());
4777 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4778 SDValue Ptr, MachinePointerInfo PtrInfo,
4779 bool isVolatile, bool isNonTemporal,
4780 unsigned Alignment, const AAMDNodes &AAInfo) {
4781 assert(Chain.getValueType() == MVT::Other &&
4782 "Invalid chain type");
4783 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4784 Alignment = getEVTAlignment(Val.getValueType());
4786 unsigned Flags = MachineMemOperand::MOStore;
4788 Flags |= MachineMemOperand::MOVolatile;
4790 Flags |= MachineMemOperand::MONonTemporal;
4792 if (PtrInfo.V.isNull())
4793 PtrInfo = InferPointerInfo(Ptr);
4795 MachineFunction &MF = getMachineFunction();
4796 MachineMemOperand *MMO =
4797 MF.getMachineMemOperand(PtrInfo, Flags,
4798 Val.getValueType().getStoreSize(), Alignment,
4801 return getStore(Chain, dl, Val, Ptr, MMO);
4804 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4805 SDValue Ptr, MachineMemOperand *MMO) {
4806 assert(Chain.getValueType() == MVT::Other &&
4807 "Invalid chain type");
4808 EVT VT = Val.getValueType();
4809 SDVTList VTs = getVTList(MVT::Other);
4810 SDValue Undef = getUNDEF(Ptr.getValueType());
4811 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4812 FoldingSetNodeID ID;
4813 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4814 ID.AddInteger(VT.getRawBits());
4815 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4816 MMO->isNonTemporal(), MMO->isInvariant()));
4817 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4819 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4820 cast<StoreSDNode>(E)->refineAlignment(MMO);
4821 return SDValue(E, 0);
4823 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4824 dl.getDebugLoc(), VTs,
4825 ISD::UNINDEXED, false, VT, MMO);
4826 CSEMap.InsertNode(N, IP);
4828 return SDValue(N, 0);
4831 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4832 SDValue Ptr, MachinePointerInfo PtrInfo,
4833 EVT SVT,bool isVolatile, bool isNonTemporal,
4835 const AAMDNodes &AAInfo) {
4836 assert(Chain.getValueType() == MVT::Other &&
4837 "Invalid chain type");
4838 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4839 Alignment = getEVTAlignment(SVT);
4841 unsigned Flags = MachineMemOperand::MOStore;
4843 Flags |= MachineMemOperand::MOVolatile;
4845 Flags |= MachineMemOperand::MONonTemporal;
4847 if (PtrInfo.V.isNull())
4848 PtrInfo = InferPointerInfo(Ptr);
4850 MachineFunction &MF = getMachineFunction();
4851 MachineMemOperand *MMO =
4852 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4855 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4858 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4859 SDValue Ptr, EVT SVT,
4860 MachineMemOperand *MMO) {
4861 EVT VT = Val.getValueType();
4863 assert(Chain.getValueType() == MVT::Other &&
4864 "Invalid chain type");
4866 return getStore(Chain, dl, Val, Ptr, MMO);
4868 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4869 "Should only be a truncating store, not extending!");
4870 assert(VT.isInteger() == SVT.isInteger() &&
4871 "Can't do FP-INT conversion!");
4872 assert(VT.isVector() == SVT.isVector() &&
4873 "Cannot use trunc store to convert to or from a vector!");
4874 assert((!VT.isVector() ||
4875 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4876 "Cannot use trunc store to change the number of vector elements!");
4878 SDVTList VTs = getVTList(MVT::Other);
4879 SDValue Undef = getUNDEF(Ptr.getValueType());
4880 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4881 FoldingSetNodeID ID;
4882 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4883 ID.AddInteger(SVT.getRawBits());
4884 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4885 MMO->isNonTemporal(), MMO->isInvariant()));
4886 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4888 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4889 cast<StoreSDNode>(E)->refineAlignment(MMO);
4890 return SDValue(E, 0);
4892 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4893 dl.getDebugLoc(), VTs,
4894 ISD::UNINDEXED, true, SVT, MMO);
4895 CSEMap.InsertNode(N, IP);
4897 return SDValue(N, 0);
4901 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4902 SDValue Offset, ISD::MemIndexedMode AM) {
4903 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4904 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4905 "Store is already a indexed store!");
4906 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4907 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4908 FoldingSetNodeID ID;
4909 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4910 ID.AddInteger(ST->getMemoryVT().getRawBits());
4911 ID.AddInteger(ST->getRawSubclassData());
4912 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4914 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4915 return SDValue(E, 0);
4917 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4918 dl.getDebugLoc(), VTs, AM,
4919 ST->isTruncatingStore(),
4921 ST->getMemOperand());
4922 CSEMap.InsertNode(N, IP);
4924 return SDValue(N, 0);
4927 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4928 SDValue Chain, SDValue Ptr,
4931 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4932 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4935 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4936 ArrayRef<SDUse> Ops) {
4937 switch (Ops.size()) {
4938 case 0: return getNode(Opcode, DL, VT);
4939 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4940 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4941 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4945 // Copy from an SDUse array into an SDValue array for use with
4946 // the regular getNode logic.
4947 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4948 return getNode(Opcode, DL, VT, NewOps);
4951 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4952 ArrayRef<SDValue> Ops) {
4953 unsigned NumOps = Ops.size();
4955 case 0: return getNode(Opcode, DL, VT);
4956 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4957 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4958 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4964 case ISD::SELECT_CC: {
4965 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4966 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4967 "LHS and RHS of condition must have same type!");
4968 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4969 "True and False arms of SelectCC must have same type!");
4970 assert(Ops[2].getValueType() == VT &&
4971 "select_cc node must be of same type as true and false value!");
4975 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4976 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4977 "LHS/RHS of comparison should match types!");
4984 SDVTList VTs = getVTList(VT);
4986 if (VT != MVT::Glue) {
4987 FoldingSetNodeID ID;
4988 AddNodeIDNode(ID, Opcode, VTs, Ops);
4991 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4992 return SDValue(E, 0);
4994 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4996 CSEMap.InsertNode(N, IP);
4998 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5003 return SDValue(N, 0);
5006 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5007 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5008 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5011 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5012 ArrayRef<SDValue> Ops) {
5013 if (VTList.NumVTs == 1)
5014 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5018 // FIXME: figure out how to safely handle things like
5019 // int foo(int x) { return 1 << (x & 255); }
5020 // int bar() { return foo(256); }
5021 case ISD::SRA_PARTS:
5022 case ISD::SRL_PARTS:
5023 case ISD::SHL_PARTS:
5024 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5025 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5026 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5027 else if (N3.getOpcode() == ISD::AND)
5028 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5029 // If the and is only masking out bits that cannot effect the shift,
5030 // eliminate the and.
5031 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5032 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5033 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5039 // Memoize the node unless it returns a flag.
5041 unsigned NumOps = Ops.size();
5042 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5043 FoldingSetNodeID ID;
5044 AddNodeIDNode(ID, Opcode, VTList, Ops);
5046 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5047 return SDValue(E, 0);
5050 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5051 DL.getDebugLoc(), VTList, Ops[0]);
5052 } else if (NumOps == 2) {
5053 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5054 DL.getDebugLoc(), VTList, Ops[0],
5056 } else if (NumOps == 3) {
5057 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5058 DL.getDebugLoc(), VTList, Ops[0],
5061 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5064 CSEMap.InsertNode(N, IP);
5067 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5068 DL.getDebugLoc(), VTList, Ops[0]);
5069 } else if (NumOps == 2) {
5070 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5071 DL.getDebugLoc(), VTList, Ops[0],
5073 } else if (NumOps == 3) {
5074 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5075 DL.getDebugLoc(), VTList, Ops[0],
5078 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5083 return SDValue(N, 0);
5086 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5087 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5090 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5092 SDValue Ops[] = { N1 };
5093 return getNode(Opcode, DL, VTList, Ops);
5096 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5097 SDValue N1, SDValue N2) {
5098 SDValue Ops[] = { N1, N2 };
5099 return getNode(Opcode, DL, VTList, Ops);
5102 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5103 SDValue N1, SDValue N2, SDValue N3) {
5104 SDValue Ops[] = { N1, N2, N3 };
5105 return getNode(Opcode, DL, VTList, Ops);
5108 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5109 SDValue N1, SDValue N2, SDValue N3,
5111 SDValue Ops[] = { N1, N2, N3, N4 };
5112 return getNode(Opcode, DL, VTList, Ops);
5115 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5116 SDValue N1, SDValue N2, SDValue N3,
5117 SDValue N4, SDValue N5) {
5118 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5119 return getNode(Opcode, DL, VTList, Ops);
5122 SDVTList SelectionDAG::getVTList(EVT VT) {
5123 return makeVTList(SDNode::getValueTypeList(VT), 1);
5126 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5127 FoldingSetNodeID ID;
5129 ID.AddInteger(VT1.getRawBits());
5130 ID.AddInteger(VT2.getRawBits());
5133 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5135 EVT *Array = Allocator.Allocate<EVT>(2);
5138 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5139 VTListMap.InsertNode(Result, IP);
5141 return Result->getSDVTList();
5144 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5145 FoldingSetNodeID ID;
5147 ID.AddInteger(VT1.getRawBits());
5148 ID.AddInteger(VT2.getRawBits());
5149 ID.AddInteger(VT3.getRawBits());
5152 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5154 EVT *Array = Allocator.Allocate<EVT>(3);
5158 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5159 VTListMap.InsertNode(Result, IP);
5161 return Result->getSDVTList();
5164 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5165 FoldingSetNodeID ID;
5167 ID.AddInteger(VT1.getRawBits());
5168 ID.AddInteger(VT2.getRawBits());
5169 ID.AddInteger(VT3.getRawBits());
5170 ID.AddInteger(VT4.getRawBits());
5173 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5175 EVT *Array = Allocator.Allocate<EVT>(4);
5180 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5181 VTListMap.InsertNode(Result, IP);
5183 return Result->getSDVTList();
5186 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5187 unsigned NumVTs = VTs.size();
5188 FoldingSetNodeID ID;
5189 ID.AddInteger(NumVTs);
5190 for (unsigned index = 0; index < NumVTs; index++) {
5191 ID.AddInteger(VTs[index].getRawBits());
5195 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5197 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5198 std::copy(VTs.begin(), VTs.end(), Array);
5199 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5200 VTListMap.InsertNode(Result, IP);
5202 return Result->getSDVTList();
5206 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5207 /// specified operands. If the resultant node already exists in the DAG,
5208 /// this does not modify the specified node, instead it returns the node that
5209 /// already exists. If the resultant node does not exist in the DAG, the
5210 /// input node is returned. As a degenerate case, if you specify the same
5211 /// input operands as the node already has, the input node is returned.
5212 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5213 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5215 // Check to see if there is no change.
5216 if (Op == N->getOperand(0)) return N;
5218 // See if the modified node already exists.
5219 void *InsertPos = nullptr;
5220 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5223 // Nope it doesn't. Remove the node from its current place in the maps.
5225 if (!RemoveNodeFromCSEMaps(N))
5226 InsertPos = nullptr;
5228 // Now we update the operands.
5229 N->OperandList[0].set(Op);
5231 // If this gets put into a CSE map, add it.
5232 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5236 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5237 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5239 // Check to see if there is no change.
5240 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5241 return N; // No operands changed, just return the input node.
5243 // See if the modified node already exists.
5244 void *InsertPos = nullptr;
5245 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5248 // Nope it doesn't. Remove the node from its current place in the maps.
5250 if (!RemoveNodeFromCSEMaps(N))
5251 InsertPos = nullptr;
5253 // Now we update the operands.
5254 if (N->OperandList[0] != Op1)
5255 N->OperandList[0].set(Op1);
5256 if (N->OperandList[1] != Op2)
5257 N->OperandList[1].set(Op2);
5259 // If this gets put into a CSE map, add it.
5260 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5264 SDNode *SelectionDAG::
5265 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5266 SDValue Ops[] = { Op1, Op2, Op3 };
5267 return UpdateNodeOperands(N, Ops);
5270 SDNode *SelectionDAG::
5271 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5272 SDValue Op3, SDValue Op4) {
5273 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5274 return UpdateNodeOperands(N, Ops);
5277 SDNode *SelectionDAG::
5278 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5279 SDValue Op3, SDValue Op4, SDValue Op5) {
5280 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5281 return UpdateNodeOperands(N, Ops);
5284 SDNode *SelectionDAG::
5285 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5286 unsigned NumOps = Ops.size();
5287 assert(N->getNumOperands() == NumOps &&
5288 "Update with wrong number of operands");
5290 // Check to see if there is no change.
5291 bool AnyChange = false;
5292 for (unsigned i = 0; i != NumOps; ++i) {
5293 if (Ops[i] != N->getOperand(i)) {
5299 // No operands changed, just return the input node.
5300 if (!AnyChange) return N;
5302 // See if the modified node already exists.
5303 void *InsertPos = nullptr;
5304 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5307 // Nope it doesn't. Remove the node from its current place in the maps.
5309 if (!RemoveNodeFromCSEMaps(N))
5310 InsertPos = nullptr;
5312 // Now we update the operands.
5313 for (unsigned i = 0; i != NumOps; ++i)
5314 if (N->OperandList[i] != Ops[i])
5315 N->OperandList[i].set(Ops[i]);
5317 // If this gets put into a CSE map, add it.
5318 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5322 /// DropOperands - Release the operands and set this node to have
5324 void SDNode::DropOperands() {
5325 // Unlike the code in MorphNodeTo that does this, we don't need to
5326 // watch for dead nodes here.
5327 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5333 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5336 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5338 SDVTList VTs = getVTList(VT);
5339 return SelectNodeTo(N, MachineOpc, VTs, None);
5342 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5343 EVT VT, SDValue Op1) {
5344 SDVTList VTs = getVTList(VT);
5345 SDValue Ops[] = { Op1 };
5346 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5349 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5350 EVT VT, SDValue Op1,
5352 SDVTList VTs = getVTList(VT);
5353 SDValue Ops[] = { Op1, Op2 };
5354 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5357 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5358 EVT VT, SDValue Op1,
5359 SDValue Op2, SDValue Op3) {
5360 SDVTList VTs = getVTList(VT);
5361 SDValue Ops[] = { Op1, Op2, Op3 };
5362 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5365 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5366 EVT VT, ArrayRef<SDValue> Ops) {
5367 SDVTList VTs = getVTList(VT);
5368 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5371 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5372 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5373 SDVTList VTs = getVTList(VT1, VT2);
5374 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5377 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5379 SDVTList VTs = getVTList(VT1, VT2);
5380 return SelectNodeTo(N, MachineOpc, VTs, None);
5383 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5384 EVT VT1, EVT VT2, EVT VT3,
5385 ArrayRef<SDValue> Ops) {
5386 SDVTList VTs = getVTList(VT1, VT2, VT3);
5387 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5390 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5391 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5392 ArrayRef<SDValue> Ops) {
5393 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5394 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5397 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5400 SDVTList VTs = getVTList(VT1, VT2);
5401 SDValue Ops[] = { Op1 };
5402 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5405 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5407 SDValue Op1, SDValue Op2) {
5408 SDVTList VTs = getVTList(VT1, VT2);
5409 SDValue Ops[] = { Op1, Op2 };
5410 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5413 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5415 SDValue Op1, SDValue Op2,
5417 SDVTList VTs = getVTList(VT1, VT2);
5418 SDValue Ops[] = { Op1, Op2, Op3 };
5419 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5422 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5423 EVT VT1, EVT VT2, EVT VT3,
5424 SDValue Op1, SDValue Op2,
5426 SDVTList VTs = getVTList(VT1, VT2, VT3);
5427 SDValue Ops[] = { Op1, Op2, Op3 };
5428 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5431 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5432 SDVTList VTs,ArrayRef<SDValue> Ops) {
5433 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5434 // Reset the NodeID to -1.
5439 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5440 /// the line number information on the merged node since it is not possible to
5441 /// preserve the information that operation is associated with multiple lines.
5442 /// This will make the debugger working better at -O0, were there is a higher
5443 /// probability having other instructions associated with that line.
5445 /// For IROrder, we keep the smaller of the two
5446 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5447 DebugLoc NLoc = N->getDebugLoc();
5448 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5449 (OLoc.getDebugLoc() != NLoc)) {
5450 N->setDebugLoc(DebugLoc());
5452 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5453 N->setIROrder(Order);
5457 /// MorphNodeTo - This *mutates* the specified node to have the specified
5458 /// return type, opcode, and operands.
5460 /// Note that MorphNodeTo returns the resultant node. If there is already a
5461 /// node of the specified opcode and operands, it returns that node instead of
5462 /// the current one. Note that the SDLoc need not be the same.
5464 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5465 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5466 /// node, and because it doesn't require CSE recalculation for any of
5467 /// the node's users.
5469 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5470 SDVTList VTs, ArrayRef<SDValue> Ops) {
5471 unsigned NumOps = Ops.size();
5472 // If an identical node already exists, use it.
5474 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5475 FoldingSetNodeID ID;
5476 AddNodeIDNode(ID, Opc, VTs, Ops);
5477 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5478 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5481 if (!RemoveNodeFromCSEMaps(N))
5484 // Start the morphing.
5486 N->ValueList = VTs.VTs;
5487 N->NumValues = VTs.NumVTs;
5489 // Clear the operands list, updating used nodes to remove this from their
5490 // use list. Keep track of any operands that become dead as a result.
5491 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5492 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5494 SDNode *Used = Use.getNode();
5496 if (Used->use_empty())
5497 DeadNodeSet.insert(Used);
5500 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5501 // Initialize the memory references information.
5502 MN->setMemRefs(nullptr, nullptr);
5503 // If NumOps is larger than the # of operands we can have in a
5504 // MachineSDNode, reallocate the operand list.
5505 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5506 if (MN->OperandsNeedDelete)
5507 delete[] MN->OperandList;
5508 if (NumOps > array_lengthof(MN->LocalOperands))
5509 // We're creating a final node that will live unmorphed for the
5510 // remainder of the current SelectionDAG iteration, so we can allocate
5511 // the operands directly out of a pool with no recycling metadata.
5512 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5513 Ops.data(), NumOps);
5515 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5516 MN->OperandsNeedDelete = false;
5518 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5520 // If NumOps is larger than the # of operands we currently have, reallocate
5521 // the operand list.
5522 if (NumOps > N->NumOperands) {
5523 if (N->OperandsNeedDelete)
5524 delete[] N->OperandList;
5525 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5526 N->OperandsNeedDelete = true;
5528 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5531 // Delete any nodes that are still dead after adding the uses for the
5533 if (!DeadNodeSet.empty()) {
5534 SmallVector<SDNode *, 16> DeadNodes;
5535 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5536 E = DeadNodeSet.end(); I != E; ++I)
5537 if ((*I)->use_empty())
5538 DeadNodes.push_back(*I);
5539 RemoveDeadNodes(DeadNodes);
5543 CSEMap.InsertNode(N, IP); // Memoize the new node.
5548 /// getMachineNode - These are used for target selectors to create a new node
5549 /// with specified return type(s), MachineInstr opcode, and operands.
5551 /// Note that getMachineNode returns the resultant node. If there is already a
5552 /// node of the specified opcode and operands, it returns that node instead of
5553 /// the current one.
5555 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5556 SDVTList VTs = getVTList(VT);
5557 return getMachineNode(Opcode, dl, VTs, None);
5561 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5562 SDVTList VTs = getVTList(VT);
5563 SDValue Ops[] = { Op1 };
5564 return getMachineNode(Opcode, dl, VTs, Ops);
5568 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5569 SDValue Op1, SDValue Op2) {
5570 SDVTList VTs = getVTList(VT);
5571 SDValue Ops[] = { Op1, Op2 };
5572 return getMachineNode(Opcode, dl, VTs, Ops);
5576 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5577 SDValue Op1, SDValue Op2, SDValue Op3) {
5578 SDVTList VTs = getVTList(VT);
5579 SDValue Ops[] = { Op1, Op2, Op3 };
5580 return getMachineNode(Opcode, dl, VTs, Ops);
5584 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5585 ArrayRef<SDValue> Ops) {
5586 SDVTList VTs = getVTList(VT);
5587 return getMachineNode(Opcode, dl, VTs, Ops);
5591 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5592 SDVTList VTs = getVTList(VT1, VT2);
5593 return getMachineNode(Opcode, dl, VTs, None);
5597 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5598 EVT VT1, EVT VT2, SDValue Op1) {
5599 SDVTList VTs = getVTList(VT1, VT2);
5600 SDValue Ops[] = { Op1 };
5601 return getMachineNode(Opcode, dl, VTs, Ops);
5605 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5606 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5607 SDVTList VTs = getVTList(VT1, VT2);
5608 SDValue Ops[] = { Op1, Op2 };
5609 return getMachineNode(Opcode, dl, VTs, Ops);
5613 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5614 EVT VT1, EVT VT2, SDValue Op1,
5615 SDValue Op2, SDValue Op3) {
5616 SDVTList VTs = getVTList(VT1, VT2);
5617 SDValue Ops[] = { Op1, Op2, Op3 };
5618 return getMachineNode(Opcode, dl, VTs, Ops);
5622 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5624 ArrayRef<SDValue> Ops) {
5625 SDVTList VTs = getVTList(VT1, VT2);
5626 return getMachineNode(Opcode, dl, VTs, Ops);
5630 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5631 EVT VT1, EVT VT2, EVT VT3,
5632 SDValue Op1, SDValue Op2) {
5633 SDVTList VTs = getVTList(VT1, VT2, VT3);
5634 SDValue Ops[] = { Op1, Op2 };
5635 return getMachineNode(Opcode, dl, VTs, Ops);
5639 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5640 EVT VT1, EVT VT2, EVT VT3,
5641 SDValue Op1, SDValue Op2, SDValue Op3) {
5642 SDVTList VTs = getVTList(VT1, VT2, VT3);
5643 SDValue Ops[] = { Op1, Op2, Op3 };
5644 return getMachineNode(Opcode, dl, VTs, Ops);
5648 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5649 EVT VT1, EVT VT2, EVT VT3,
5650 ArrayRef<SDValue> Ops) {
5651 SDVTList VTs = getVTList(VT1, VT2, VT3);
5652 return getMachineNode(Opcode, dl, VTs, Ops);
5656 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5657 EVT VT2, EVT VT3, EVT VT4,
5658 ArrayRef<SDValue> Ops) {
5659 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5660 return getMachineNode(Opcode, dl, VTs, Ops);
5664 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5665 ArrayRef<EVT> ResultTys,
5666 ArrayRef<SDValue> Ops) {
5667 SDVTList VTs = getVTList(ResultTys);
5668 return getMachineNode(Opcode, dl, VTs, Ops);
5672 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5673 ArrayRef<SDValue> OpsArray) {
5674 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5677 const SDValue *Ops = OpsArray.data();
5678 unsigned NumOps = OpsArray.size();
5681 FoldingSetNodeID ID;
5682 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5684 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5685 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5689 // Allocate a new MachineSDNode.
5690 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5691 DL.getDebugLoc(), VTs);
5693 // Initialize the operands list.
5694 if (NumOps > array_lengthof(N->LocalOperands))
5695 // We're creating a final node that will live unmorphed for the
5696 // remainder of the current SelectionDAG iteration, so we can allocate
5697 // the operands directly out of a pool with no recycling metadata.
5698 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5701 N->InitOperands(N->LocalOperands, Ops, NumOps);
5702 N->OperandsNeedDelete = false;
5705 CSEMap.InsertNode(N, IP);
5711 /// getTargetExtractSubreg - A convenience function for creating
5712 /// TargetOpcode::EXTRACT_SUBREG nodes.
5714 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5716 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5717 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5718 VT, Operand, SRIdxVal);
5719 return SDValue(Subreg, 0);
5722 /// getTargetInsertSubreg - A convenience function for creating
5723 /// TargetOpcode::INSERT_SUBREG nodes.
5725 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5726 SDValue Operand, SDValue Subreg) {
5727 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5728 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5729 VT, Operand, Subreg, SRIdxVal);
5730 return SDValue(Result, 0);
5733 /// getNodeIfExists - Get the specified node if it's already available, or
5734 /// else return NULL.
5735 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5736 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5738 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5739 FoldingSetNodeID ID;
5740 AddNodeIDNode(ID, Opcode, VTList, Ops);
5741 if (isBinOpWithFlags(Opcode))
5742 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5744 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5750 /// getDbgValue - Creates a SDDbgValue node.
5754 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5755 bool IsIndirect, uint64_t Off,
5756 DebugLoc DL, unsigned O) {
5757 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5762 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5764 DebugLoc DL, unsigned O) {
5765 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5770 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5771 DebugLoc DL, unsigned O) {
5772 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5777 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5778 /// pointed to by a use iterator is deleted, increment the use iterator
5779 /// so that it doesn't dangle.
5781 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5782 SDNode::use_iterator &UI;
5783 SDNode::use_iterator &UE;
5785 void NodeDeleted(SDNode *N, SDNode *E) override {
5786 // Increment the iterator as needed.
5787 while (UI != UE && N == *UI)
5792 RAUWUpdateListener(SelectionDAG &d,
5793 SDNode::use_iterator &ui,
5794 SDNode::use_iterator &ue)
5795 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5800 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5801 /// This can cause recursive merging of nodes in the DAG.
5803 /// This version assumes From has a single result value.
5805 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5806 SDNode *From = FromN.getNode();
5807 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5808 "Cannot replace with this method!");
5809 assert(From != To.getNode() && "Cannot replace uses of with self");
5811 // Iterate over all the existing uses of From. New uses will be added
5812 // to the beginning of the use list, which we avoid visiting.
5813 // This specifically avoids visiting uses of From that arise while the
5814 // replacement is happening, because any such uses would be the result
5815 // of CSE: If an existing node looks like From after one of its operands
5816 // is replaced by To, we don't want to replace of all its users with To
5817 // too. See PR3018 for more info.
5818 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5819 RAUWUpdateListener Listener(*this, UI, UE);
5823 // This node is about to morph, remove its old self from the CSE maps.
5824 RemoveNodeFromCSEMaps(User);
5826 // A user can appear in a use list multiple times, and when this
5827 // happens the uses are usually next to each other in the list.
5828 // To help reduce the number of CSE recomputations, process all
5829 // the uses of this user that we can find this way.
5831 SDUse &Use = UI.getUse();
5834 } while (UI != UE && *UI == User);
5836 // Now that we have modified User, add it back to the CSE maps. If it
5837 // already exists there, recursively merge the results together.
5838 AddModifiedNodeToCSEMaps(User);
5841 // If we just RAUW'd the root, take note.
5842 if (FromN == getRoot())
5846 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5847 /// This can cause recursive merging of nodes in the DAG.
5849 /// This version assumes that for each value of From, there is a
5850 /// corresponding value in To in the same position with the same type.
5852 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5854 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5855 assert((!From->hasAnyUseOfValue(i) ||
5856 From->getValueType(i) == To->getValueType(i)) &&
5857 "Cannot use this version of ReplaceAllUsesWith!");
5860 // Handle the trivial case.
5864 // Iterate over just the existing users of From. See the comments in
5865 // the ReplaceAllUsesWith above.
5866 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5867 RAUWUpdateListener Listener(*this, UI, UE);
5871 // This node is about to morph, remove its old self from the CSE maps.
5872 RemoveNodeFromCSEMaps(User);
5874 // A user can appear in a use list multiple times, and when this
5875 // happens the uses are usually next to each other in the list.
5876 // To help reduce the number of CSE recomputations, process all
5877 // the uses of this user that we can find this way.
5879 SDUse &Use = UI.getUse();
5882 } while (UI != UE && *UI == User);
5884 // Now that we have modified User, add it back to the CSE maps. If it
5885 // already exists there, recursively merge the results together.
5886 AddModifiedNodeToCSEMaps(User);
5889 // If we just RAUW'd the root, take note.
5890 if (From == getRoot().getNode())
5891 setRoot(SDValue(To, getRoot().getResNo()));
5894 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5895 /// This can cause recursive merging of nodes in the DAG.
5897 /// This version can replace From with any result values. To must match the
5898 /// number and types of values returned by From.
5899 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5900 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5901 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5903 // Iterate over just the existing users of From. See the comments in
5904 // the ReplaceAllUsesWith above.
5905 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5906 RAUWUpdateListener Listener(*this, UI, UE);
5910 // This node is about to morph, remove its old self from the CSE maps.
5911 RemoveNodeFromCSEMaps(User);
5913 // A user can appear in a use list multiple times, and when this
5914 // happens the uses are usually next to each other in the list.
5915 // To help reduce the number of CSE recomputations, process all
5916 // the uses of this user that we can find this way.
5918 SDUse &Use = UI.getUse();
5919 const SDValue &ToOp = To[Use.getResNo()];
5922 } while (UI != UE && *UI == User);
5924 // Now that we have modified User, add it back to the CSE maps. If it
5925 // already exists there, recursively merge the results together.
5926 AddModifiedNodeToCSEMaps(User);
5929 // If we just RAUW'd the root, take note.
5930 if (From == getRoot().getNode())
5931 setRoot(SDValue(To[getRoot().getResNo()]));
5934 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5935 /// uses of other values produced by From.getNode() alone. The Deleted
5936 /// vector is handled the same way as for ReplaceAllUsesWith.
5937 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5938 // Handle the really simple, really trivial case efficiently.
5939 if (From == To) return;
5941 // Handle the simple, trivial, case efficiently.
5942 if (From.getNode()->getNumValues() == 1) {
5943 ReplaceAllUsesWith(From, To);
5947 // Iterate over just the existing users of From. See the comments in
5948 // the ReplaceAllUsesWith above.
5949 SDNode::use_iterator UI = From.getNode()->use_begin(),
5950 UE = From.getNode()->use_end();
5951 RAUWUpdateListener Listener(*this, UI, UE);
5954 bool UserRemovedFromCSEMaps = false;
5956 // A user can appear in a use list multiple times, and when this
5957 // happens the uses are usually next to each other in the list.
5958 // To help reduce the number of CSE recomputations, process all
5959 // the uses of this user that we can find this way.
5961 SDUse &Use = UI.getUse();
5963 // Skip uses of different values from the same node.
5964 if (Use.getResNo() != From.getResNo()) {
5969 // If this node hasn't been modified yet, it's still in the CSE maps,
5970 // so remove its old self from the CSE maps.
5971 if (!UserRemovedFromCSEMaps) {
5972 RemoveNodeFromCSEMaps(User);
5973 UserRemovedFromCSEMaps = true;
5978 } while (UI != UE && *UI == User);
5980 // We are iterating over all uses of the From node, so if a use
5981 // doesn't use the specific value, no changes are made.
5982 if (!UserRemovedFromCSEMaps)
5985 // Now that we have modified User, add it back to the CSE maps. If it
5986 // already exists there, recursively merge the results together.
5987 AddModifiedNodeToCSEMaps(User);
5990 // If we just RAUW'd the root, take note.
5991 if (From == getRoot())
5996 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5997 /// to record information about a use.
6004 /// operator< - Sort Memos by User.
6005 bool operator<(const UseMemo &L, const UseMemo &R) {
6006 return (intptr_t)L.User < (intptr_t)R.User;
6010 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6011 /// uses of other values produced by From.getNode() alone. The same value
6012 /// may appear in both the From and To list. The Deleted vector is
6013 /// handled the same way as for ReplaceAllUsesWith.
6014 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6017 // Handle the simple, trivial case efficiently.
6019 return ReplaceAllUsesOfValueWith(*From, *To);
6021 // Read up all the uses and make records of them. This helps
6022 // processing new uses that are introduced during the
6023 // replacement process.
6024 SmallVector<UseMemo, 4> Uses;
6025 for (unsigned i = 0; i != Num; ++i) {
6026 unsigned FromResNo = From[i].getResNo();
6027 SDNode *FromNode = From[i].getNode();
6028 for (SDNode::use_iterator UI = FromNode->use_begin(),
6029 E = FromNode->use_end(); UI != E; ++UI) {
6030 SDUse &Use = UI.getUse();
6031 if (Use.getResNo() == FromResNo) {
6032 UseMemo Memo = { *UI, i, &Use };
6033 Uses.push_back(Memo);
6038 // Sort the uses, so that all the uses from a given User are together.
6039 std::sort(Uses.begin(), Uses.end());
6041 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6042 UseIndex != UseIndexEnd; ) {
6043 // We know that this user uses some value of From. If it is the right
6044 // value, update it.
6045 SDNode *User = Uses[UseIndex].User;
6047 // This node is about to morph, remove its old self from the CSE maps.
6048 RemoveNodeFromCSEMaps(User);
6050 // The Uses array is sorted, so all the uses for a given User
6051 // are next to each other in the list.
6052 // To help reduce the number of CSE recomputations, process all
6053 // the uses of this user that we can find this way.
6055 unsigned i = Uses[UseIndex].Index;
6056 SDUse &Use = *Uses[UseIndex].Use;
6060 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6062 // Now that we have modified User, add it back to the CSE maps. If it
6063 // already exists there, recursively merge the results together.
6064 AddModifiedNodeToCSEMaps(User);
6068 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6069 /// based on their topological order. It returns the maximum id and a vector
6070 /// of the SDNodes* in assigned order by reference.
6071 unsigned SelectionDAG::AssignTopologicalOrder() {
6073 unsigned DAGSize = 0;
6075 // SortedPos tracks the progress of the algorithm. Nodes before it are
6076 // sorted, nodes after it are unsorted. When the algorithm completes
6077 // it is at the end of the list.
6078 allnodes_iterator SortedPos = allnodes_begin();
6080 // Visit all the nodes. Move nodes with no operands to the front of
6081 // the list immediately. Annotate nodes that do have operands with their
6082 // operand count. Before we do this, the Node Id fields of the nodes
6083 // may contain arbitrary values. After, the Node Id fields for nodes
6084 // before SortedPos will contain the topological sort index, and the
6085 // Node Id fields for nodes At SortedPos and after will contain the
6086 // count of outstanding operands.
6087 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6089 checkForCycles(N, this);
6090 unsigned Degree = N->getNumOperands();
6092 // A node with no uses, add it to the result array immediately.
6093 N->setNodeId(DAGSize++);
6094 allnodes_iterator Q = N;
6096 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6097 assert(SortedPos != AllNodes.end() && "Overran node list");
6100 // Temporarily use the Node Id as scratch space for the degree count.
6101 N->setNodeId(Degree);
6105 // Visit all the nodes. As we iterate, move nodes into sorted order,
6106 // such that by the time the end is reached all nodes will be sorted.
6107 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6109 checkForCycles(N, this);
6110 // N is in sorted position, so all its uses have one less operand
6111 // that needs to be sorted.
6112 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6115 unsigned Degree = P->getNodeId();
6116 assert(Degree != 0 && "Invalid node degree");
6119 // All of P's operands are sorted, so P may sorted now.
6120 P->setNodeId(DAGSize++);
6122 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6123 assert(SortedPos != AllNodes.end() && "Overran node list");
6126 // Update P's outstanding operand count.
6127 P->setNodeId(Degree);
6130 if (I == SortedPos) {
6133 dbgs() << "Overran sorted position:\n";
6134 S->dumprFull(this); dbgs() << "\n";
6135 dbgs() << "Checking if this is due to cycles\n";
6136 checkForCycles(this, true);
6138 llvm_unreachable(nullptr);
6142 assert(SortedPos == AllNodes.end() &&
6143 "Topological sort incomplete!");
6144 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6145 "First node in topological sort is not the entry token!");
6146 assert(AllNodes.front().getNodeId() == 0 &&
6147 "First node in topological sort has non-zero id!");
6148 assert(AllNodes.front().getNumOperands() == 0 &&
6149 "First node in topological sort has operands!");
6150 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6151 "Last node in topologic sort has unexpected id!");
6152 assert(AllNodes.back().use_empty() &&
6153 "Last node in topologic sort has users!");
6154 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6158 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6159 /// value is produced by SD.
6160 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6161 DbgInfo->add(DB, SD, isParameter);
6163 SD->setHasDebugValue(true);
6166 /// TransferDbgValues - Transfer SDDbgValues.
6167 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6168 if (From == To || !From.getNode()->getHasDebugValue())
6170 SDNode *FromNode = From.getNode();
6171 SDNode *ToNode = To.getNode();
6172 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6173 SmallVector<SDDbgValue *, 2> ClonedDVs;
6174 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6176 SDDbgValue *Dbg = *I;
6177 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6178 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6180 Dbg->getOffset(), Dbg->getDebugLoc(),
6182 ClonedDVs.push_back(Clone);
6185 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6186 E = ClonedDVs.end(); I != E; ++I)
6187 AddDbgValue(*I, ToNode, false);
6190 //===----------------------------------------------------------------------===//
6192 //===----------------------------------------------------------------------===//
6194 HandleSDNode::~HandleSDNode() {
6198 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6199 DebugLoc DL, const GlobalValue *GA,
6200 EVT VT, int64_t o, unsigned char TF)
6201 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6205 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6206 SDValue X, unsigned SrcAS,
6208 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6209 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6211 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6212 EVT memvt, MachineMemOperand *mmo)
6213 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6214 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6215 MMO->isNonTemporal(), MMO->isInvariant());
6216 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6217 assert(isNonTemporal() == MMO->isNonTemporal() &&
6218 "Non-temporal encoding error!");
6219 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6222 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6223 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6224 : SDNode(Opc, Order, dl, VTs, Ops),
6225 MemoryVT(memvt), MMO(mmo) {
6226 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6227 MMO->isNonTemporal(), MMO->isInvariant());
6228 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6229 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6232 /// Profile - Gather unique data for the node.
6234 void SDNode::Profile(FoldingSetNodeID &ID) const {
6235 AddNodeIDNode(ID, this);
6240 std::vector<EVT> VTs;
6243 VTs.reserve(MVT::LAST_VALUETYPE);
6244 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6245 VTs.push_back(MVT((MVT::SimpleValueType)i));
6250 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6251 static ManagedStatic<EVTArray> SimpleVTArray;
6252 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6254 /// getValueTypeList - Return a pointer to the specified value type.
6256 const EVT *SDNode::getValueTypeList(EVT VT) {
6257 if (VT.isExtended()) {
6258 sys::SmartScopedLock<true> Lock(*VTMutex);
6259 return &(*EVTs->insert(VT).first);
6261 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6262 "Value type out of range!");
6263 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6267 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6268 /// indicated value. This method ignores uses of other values defined by this
6270 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6271 assert(Value < getNumValues() && "Bad value!");
6273 // TODO: Only iterate over uses of a given value of the node
6274 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6275 if (UI.getUse().getResNo() == Value) {
6282 // Found exactly the right number of uses?
6287 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6288 /// value. This method ignores uses of other values defined by this operation.
6289 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6290 assert(Value < getNumValues() && "Bad value!");
6292 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6293 if (UI.getUse().getResNo() == Value)
6300 /// isOnlyUserOf - Return true if this node is the only use of N.
6302 bool SDNode::isOnlyUserOf(SDNode *N) const {
6304 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6315 /// isOperand - Return true if this node is an operand of N.
6317 bool SDValue::isOperandOf(SDNode *N) const {
6318 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6319 if (*this == N->getOperand(i))
6324 bool SDNode::isOperandOf(SDNode *N) const {
6325 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6326 if (this == N->OperandList[i].getNode())
6331 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6332 /// be a chain) reaches the specified operand without crossing any
6333 /// side-effecting instructions on any chain path. In practice, this looks
6334 /// through token factors and non-volatile loads. In order to remain efficient,
6335 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6336 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6337 unsigned Depth) const {
6338 if (*this == Dest) return true;
6340 // Don't search too deeply, we just want to be able to see through
6341 // TokenFactor's etc.
6342 if (Depth == 0) return false;
6344 // If this is a token factor, all inputs to the TF happen in parallel. If any
6345 // of the operands of the TF does not reach dest, then we cannot do the xform.
6346 if (getOpcode() == ISD::TokenFactor) {
6347 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6348 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6353 // Loads don't have side effects, look through them.
6354 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6355 if (!Ld->isVolatile())
6356 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6361 /// hasPredecessor - Return true if N is a predecessor of this node.
6362 /// N is either an operand of this node, or can be reached by recursively
6363 /// traversing up the operands.
6364 /// NOTE: This is an expensive method. Use it carefully.
6365 bool SDNode::hasPredecessor(const SDNode *N) const {
6366 SmallPtrSet<const SDNode *, 32> Visited;
6367 SmallVector<const SDNode *, 16> Worklist;
6368 return hasPredecessorHelper(N, Visited, Worklist);
6372 SDNode::hasPredecessorHelper(const SDNode *N,
6373 SmallPtrSet<const SDNode *, 32> &Visited,
6374 SmallVectorImpl<const SDNode *> &Worklist) const {
6375 if (Visited.empty()) {
6376 Worklist.push_back(this);
6378 // Take a look in the visited set. If we've already encountered this node
6379 // we needn't search further.
6380 if (Visited.count(N))
6384 // Haven't visited N yet. Continue the search.
6385 while (!Worklist.empty()) {
6386 const SDNode *M = Worklist.pop_back_val();
6387 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6388 SDNode *Op = M->getOperand(i).getNode();
6389 if (Visited.insert(Op))
6390 Worklist.push_back(Op);
6399 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6400 assert(Num < NumOperands && "Invalid child # of SDNode!");
6401 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6404 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6405 assert(N->getNumValues() == 1 &&
6406 "Can't unroll a vector with multiple results!");
6408 EVT VT = N->getValueType(0);
6409 unsigned NE = VT.getVectorNumElements();
6410 EVT EltVT = VT.getVectorElementType();
6413 SmallVector<SDValue, 8> Scalars;
6414 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6416 // If ResNE is 0, fully unroll the vector op.
6419 else if (NE > ResNE)
6423 for (i= 0; i != NE; ++i) {
6424 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6425 SDValue Operand = N->getOperand(j);
6426 EVT OperandVT = Operand.getValueType();
6427 if (OperandVT.isVector()) {
6428 // A vector operand; extract a single element.
6429 const TargetLowering *TLI = TM.getTargetLowering();
6430 EVT OperandEltVT = OperandVT.getVectorElementType();
6431 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6434 getConstant(i, TLI->getVectorIdxTy()));
6436 // A scalar operand; just use it as is.
6437 Operands[j] = Operand;
6441 switch (N->getOpcode()) {
6443 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6446 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6453 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6454 getShiftAmountOperand(Operands[0].getValueType(),
6457 case ISD::SIGN_EXTEND_INREG:
6458 case ISD::FP_ROUND_INREG: {
6459 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6460 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6462 getValueType(ExtVT)));
6467 for (; i < ResNE; ++i)
6468 Scalars.push_back(getUNDEF(EltVT));
6470 return getNode(ISD::BUILD_VECTOR, dl,
6471 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6475 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6476 /// location that is 'Dist' units away from the location that the 'Base' load
6477 /// is loading from.
6478 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6479 unsigned Bytes, int Dist) const {
6480 if (LD->getChain() != Base->getChain())
6482 EVT VT = LD->getValueType(0);
6483 if (VT.getSizeInBits() / 8 != Bytes)
6486 SDValue Loc = LD->getOperand(1);
6487 SDValue BaseLoc = Base->getOperand(1);
6488 if (Loc.getOpcode() == ISD::FrameIndex) {
6489 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6491 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6492 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6493 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6494 int FS = MFI->getObjectSize(FI);
6495 int BFS = MFI->getObjectSize(BFI);
6496 if (FS != BFS || FS != (int)Bytes) return false;
6497 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6501 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6502 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6505 const GlobalValue *GV1 = nullptr;
6506 const GlobalValue *GV2 = nullptr;
6507 int64_t Offset1 = 0;
6508 int64_t Offset2 = 0;
6509 const TargetLowering *TLI = TM.getTargetLowering();
6510 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6511 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6512 if (isGA1 && isGA2 && GV1 == GV2)
6513 return Offset1 == (Offset2 + Dist*Bytes);
6518 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6519 /// it cannot be inferred.
6520 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6521 // If this is a GlobalAddress + cst, return the alignment.
6522 const GlobalValue *GV;
6523 int64_t GVOffset = 0;
6524 const TargetLowering *TLI = TM.getTargetLowering();
6525 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6526 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6527 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6528 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6529 TLI->getDataLayout());
6530 unsigned AlignBits = KnownZero.countTrailingOnes();
6531 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6533 return MinAlign(Align, GVOffset);
6536 // If this is a direct reference to a stack slot, use information about the
6537 // stack slot's alignment.
6538 int FrameIdx = 1 << 31;
6539 int64_t FrameOffset = 0;
6540 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6541 FrameIdx = FI->getIndex();
6542 } else if (isBaseWithConstantOffset(Ptr) &&
6543 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6545 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6546 FrameOffset = Ptr.getConstantOperandVal(1);
6549 if (FrameIdx != (1 << 31)) {
6550 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6551 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6559 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6560 /// which is split (or expanded) into two not necessarily identical pieces.
6561 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6562 // Currently all types are split in half.
6564 if (!VT.isVector()) {
6565 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6567 unsigned NumElements = VT.getVectorNumElements();
6568 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6569 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6572 return std::make_pair(LoVT, HiVT);
6575 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6577 std::pair<SDValue, SDValue>
6578 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6580 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6581 N.getValueType().getVectorNumElements() &&
6582 "More vector elements requested than available!");
6584 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6585 getConstant(0, TLI->getVectorIdxTy()));
6586 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6587 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6588 return std::make_pair(Lo, Hi);
6591 void SelectionDAG::ExtractVectorElements(SDValue Op,
6592 SmallVectorImpl<SDValue> &Args,
6593 unsigned Start, unsigned Count) {
6594 EVT VT = Op.getValueType();
6596 Count = VT.getVectorNumElements();
6598 EVT EltVT = VT.getVectorElementType();
6599 EVT IdxTy = TLI->getVectorIdxTy();
6601 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6602 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6603 Op, getConstant(i, IdxTy)));
6607 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6608 unsigned GlobalAddressSDNode::getAddressSpace() const {
6609 return getGlobal()->getType()->getAddressSpace();
6613 Type *ConstantPoolSDNode::getType() const {
6614 if (isMachineConstantPoolEntry())
6615 return Val.MachineCPVal->getType();
6616 return Val.ConstVal->getType();
6619 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6621 unsigned &SplatBitSize,
6623 unsigned MinSplatBits,
6624 bool isBigEndian) const {
6625 EVT VT = getValueType(0);
6626 assert(VT.isVector() && "Expected a vector type");
6627 unsigned sz = VT.getSizeInBits();
6628 if (MinSplatBits > sz)
6631 SplatValue = APInt(sz, 0);
6632 SplatUndef = APInt(sz, 0);
6634 // Get the bits. Bits with undefined values (when the corresponding element
6635 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6636 // in SplatValue. If any of the values are not constant, give up and return
6638 unsigned int nOps = getNumOperands();
6639 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6640 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6642 for (unsigned j = 0; j < nOps; ++j) {
6643 unsigned i = isBigEndian ? nOps-1-j : j;
6644 SDValue OpVal = getOperand(i);
6645 unsigned BitPos = j * EltBitSize;
6647 if (OpVal.getOpcode() == ISD::UNDEF)
6648 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6649 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6650 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6651 zextOrTrunc(sz) << BitPos;
6652 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6653 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6658 // The build_vector is all constants or undefs. Find the smallest element
6659 // size that splats the vector.
6661 HasAnyUndefs = (SplatUndef != 0);
6664 unsigned HalfSize = sz / 2;
6665 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6666 APInt LowValue = SplatValue.trunc(HalfSize);
6667 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6668 APInt LowUndef = SplatUndef.trunc(HalfSize);
6670 // If the two halves do not match (ignoring undef bits), stop here.
6671 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6672 MinSplatBits > HalfSize)
6675 SplatValue = HighValue | LowValue;
6676 SplatUndef = HighUndef & LowUndef;
6685 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6686 if (UndefElements) {
6687 UndefElements->clear();
6688 UndefElements->resize(getNumOperands());
6691 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6692 SDValue Op = getOperand(i);
6693 if (Op.getOpcode() == ISD::UNDEF) {
6695 (*UndefElements)[i] = true;
6696 } else if (!Splatted) {
6698 } else if (Splatted != Op) {
6704 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6705 "Can only have a splat without a constant for all undefs.");
6706 return getOperand(0);
6713 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6714 return dyn_cast_or_null<ConstantSDNode>(
6715 getSplatValue(UndefElements).getNode());
6719 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6720 return dyn_cast_or_null<ConstantFPSDNode>(
6721 getSplatValue(UndefElements).getNode());
6724 bool BuildVectorSDNode::isConstant() const {
6725 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6726 unsigned Opc = getOperand(i).getOpcode();
6727 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6733 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6734 // Find the first non-undef value in the shuffle mask.
6736 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6739 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6741 // Make sure all remaining elements are either undef or the same as the first
6743 for (int Idx = Mask[i]; i != e; ++i)
6744 if (Mask[i] >= 0 && Mask[i] != Idx)
6750 static void checkForCyclesHelper(const SDNode *N,
6751 SmallPtrSet<const SDNode*, 32> &Visited,
6752 SmallPtrSet<const SDNode*, 32> &Checked,
6753 const llvm::SelectionDAG *DAG) {
6754 // If this node has already been checked, don't check it again.
6755 if (Checked.count(N))
6758 // If a node has already been visited on this depth-first walk, reject it as
6760 if (!Visited.insert(N)) {
6761 errs() << "Detected cycle in SelectionDAG\n";
6762 dbgs() << "Offending node:\n";
6763 N->dumprFull(DAG); dbgs() << "\n";
6767 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6768 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6775 void llvm::checkForCycles(const llvm::SDNode *N,
6776 const llvm::SelectionDAG *DAG,
6784 assert(N && "Checking nonexistent SDNode");
6785 SmallPtrSet<const SDNode*, 32> visited;
6786 SmallPtrSet<const SDNode*, 32> checked;
6787 checkForCyclesHelper(N, visited, checked, DAG);
6792 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6793 checkForCycles(DAG->getRoot().getNode(), DAG, force);