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 false, 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 bool isInvariant, unsigned Alignment,
4750 const AAMDNodes &AAInfo) {
4751 SDValue Undef = getUNDEF(Ptr.getValueType());
4752 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4753 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4758 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4759 SDValue Chain, SDValue Ptr, EVT MemVT,
4760 MachineMemOperand *MMO) {
4761 SDValue Undef = getUNDEF(Ptr.getValueType());
4762 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4767 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4768 SDValue Offset, ISD::MemIndexedMode AM) {
4769 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4770 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4771 "Load is already a indexed load!");
4772 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4773 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4774 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4775 false, LD->getAlignment());
4778 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4779 SDValue Ptr, MachinePointerInfo PtrInfo,
4780 bool isVolatile, bool isNonTemporal,
4781 unsigned Alignment, const AAMDNodes &AAInfo) {
4782 assert(Chain.getValueType() == MVT::Other &&
4783 "Invalid chain type");
4784 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4785 Alignment = getEVTAlignment(Val.getValueType());
4787 unsigned Flags = MachineMemOperand::MOStore;
4789 Flags |= MachineMemOperand::MOVolatile;
4791 Flags |= MachineMemOperand::MONonTemporal;
4793 if (PtrInfo.V.isNull())
4794 PtrInfo = InferPointerInfo(Ptr);
4796 MachineFunction &MF = getMachineFunction();
4797 MachineMemOperand *MMO =
4798 MF.getMachineMemOperand(PtrInfo, Flags,
4799 Val.getValueType().getStoreSize(), Alignment,
4802 return getStore(Chain, dl, Val, Ptr, MMO);
4805 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4806 SDValue Ptr, MachineMemOperand *MMO) {
4807 assert(Chain.getValueType() == MVT::Other &&
4808 "Invalid chain type");
4809 EVT VT = Val.getValueType();
4810 SDVTList VTs = getVTList(MVT::Other);
4811 SDValue Undef = getUNDEF(Ptr.getValueType());
4812 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4813 FoldingSetNodeID ID;
4814 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4815 ID.AddInteger(VT.getRawBits());
4816 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4817 MMO->isNonTemporal(), MMO->isInvariant()));
4818 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4820 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4821 cast<StoreSDNode>(E)->refineAlignment(MMO);
4822 return SDValue(E, 0);
4824 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4825 dl.getDebugLoc(), VTs,
4826 ISD::UNINDEXED, false, VT, MMO);
4827 CSEMap.InsertNode(N, IP);
4829 return SDValue(N, 0);
4832 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4833 SDValue Ptr, MachinePointerInfo PtrInfo,
4834 EVT SVT,bool isVolatile, bool isNonTemporal,
4836 const AAMDNodes &AAInfo) {
4837 assert(Chain.getValueType() == MVT::Other &&
4838 "Invalid chain type");
4839 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4840 Alignment = getEVTAlignment(SVT);
4842 unsigned Flags = MachineMemOperand::MOStore;
4844 Flags |= MachineMemOperand::MOVolatile;
4846 Flags |= MachineMemOperand::MONonTemporal;
4848 if (PtrInfo.V.isNull())
4849 PtrInfo = InferPointerInfo(Ptr);
4851 MachineFunction &MF = getMachineFunction();
4852 MachineMemOperand *MMO =
4853 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4856 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4859 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4860 SDValue Ptr, EVT SVT,
4861 MachineMemOperand *MMO) {
4862 EVT VT = Val.getValueType();
4864 assert(Chain.getValueType() == MVT::Other &&
4865 "Invalid chain type");
4867 return getStore(Chain, dl, Val, Ptr, MMO);
4869 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4870 "Should only be a truncating store, not extending!");
4871 assert(VT.isInteger() == SVT.isInteger() &&
4872 "Can't do FP-INT conversion!");
4873 assert(VT.isVector() == SVT.isVector() &&
4874 "Cannot use trunc store to convert to or from a vector!");
4875 assert((!VT.isVector() ||
4876 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4877 "Cannot use trunc store to change the number of vector elements!");
4879 SDVTList VTs = getVTList(MVT::Other);
4880 SDValue Undef = getUNDEF(Ptr.getValueType());
4881 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4882 FoldingSetNodeID ID;
4883 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4884 ID.AddInteger(SVT.getRawBits());
4885 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4886 MMO->isNonTemporal(), MMO->isInvariant()));
4887 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4889 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4890 cast<StoreSDNode>(E)->refineAlignment(MMO);
4891 return SDValue(E, 0);
4893 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4894 dl.getDebugLoc(), VTs,
4895 ISD::UNINDEXED, true, SVT, MMO);
4896 CSEMap.InsertNode(N, IP);
4898 return SDValue(N, 0);
4902 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4903 SDValue Offset, ISD::MemIndexedMode AM) {
4904 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4905 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4906 "Store is already a indexed store!");
4907 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4908 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4909 FoldingSetNodeID ID;
4910 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4911 ID.AddInteger(ST->getMemoryVT().getRawBits());
4912 ID.AddInteger(ST->getRawSubclassData());
4913 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4915 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4916 return SDValue(E, 0);
4918 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4919 dl.getDebugLoc(), VTs, AM,
4920 ST->isTruncatingStore(),
4922 ST->getMemOperand());
4923 CSEMap.InsertNode(N, IP);
4925 return SDValue(N, 0);
4928 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4929 SDValue Chain, SDValue Ptr,
4932 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4933 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4936 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4937 ArrayRef<SDUse> Ops) {
4938 switch (Ops.size()) {
4939 case 0: return getNode(Opcode, DL, VT);
4940 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4941 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4942 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4946 // Copy from an SDUse array into an SDValue array for use with
4947 // the regular getNode logic.
4948 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4949 return getNode(Opcode, DL, VT, NewOps);
4952 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4953 ArrayRef<SDValue> Ops) {
4954 unsigned NumOps = Ops.size();
4956 case 0: return getNode(Opcode, DL, VT);
4957 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4958 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4959 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4965 case ISD::SELECT_CC: {
4966 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4967 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4968 "LHS and RHS of condition must have same type!");
4969 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4970 "True and False arms of SelectCC must have same type!");
4971 assert(Ops[2].getValueType() == VT &&
4972 "select_cc node must be of same type as true and false value!");
4976 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4977 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4978 "LHS/RHS of comparison should match types!");
4985 SDVTList VTs = getVTList(VT);
4987 if (VT != MVT::Glue) {
4988 FoldingSetNodeID ID;
4989 AddNodeIDNode(ID, Opcode, VTs, Ops);
4992 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4993 return SDValue(E, 0);
4995 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4997 CSEMap.InsertNode(N, IP);
4999 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5004 return SDValue(N, 0);
5007 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5008 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5009 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5012 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5013 ArrayRef<SDValue> Ops) {
5014 if (VTList.NumVTs == 1)
5015 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5019 // FIXME: figure out how to safely handle things like
5020 // int foo(int x) { return 1 << (x & 255); }
5021 // int bar() { return foo(256); }
5022 case ISD::SRA_PARTS:
5023 case ISD::SRL_PARTS:
5024 case ISD::SHL_PARTS:
5025 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5026 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5027 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5028 else if (N3.getOpcode() == ISD::AND)
5029 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5030 // If the and is only masking out bits that cannot effect the shift,
5031 // eliminate the and.
5032 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5033 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5034 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5040 // Memoize the node unless it returns a flag.
5042 unsigned NumOps = Ops.size();
5043 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5044 FoldingSetNodeID ID;
5045 AddNodeIDNode(ID, Opcode, VTList, Ops);
5047 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5048 return SDValue(E, 0);
5051 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5052 DL.getDebugLoc(), VTList, Ops[0]);
5053 } else if (NumOps == 2) {
5054 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5055 DL.getDebugLoc(), VTList, Ops[0],
5057 } else if (NumOps == 3) {
5058 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5059 DL.getDebugLoc(), VTList, Ops[0],
5062 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5065 CSEMap.InsertNode(N, IP);
5068 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5069 DL.getDebugLoc(), VTList, Ops[0]);
5070 } else if (NumOps == 2) {
5071 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5072 DL.getDebugLoc(), VTList, Ops[0],
5074 } else if (NumOps == 3) {
5075 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5076 DL.getDebugLoc(), VTList, Ops[0],
5079 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5084 return SDValue(N, 0);
5087 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5088 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5091 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5093 SDValue Ops[] = { N1 };
5094 return getNode(Opcode, DL, VTList, Ops);
5097 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5098 SDValue N1, SDValue N2) {
5099 SDValue Ops[] = { N1, N2 };
5100 return getNode(Opcode, DL, VTList, Ops);
5103 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5104 SDValue N1, SDValue N2, SDValue N3) {
5105 SDValue Ops[] = { N1, N2, N3 };
5106 return getNode(Opcode, DL, VTList, Ops);
5109 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5110 SDValue N1, SDValue N2, SDValue N3,
5112 SDValue Ops[] = { N1, N2, N3, N4 };
5113 return getNode(Opcode, DL, VTList, Ops);
5116 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5117 SDValue N1, SDValue N2, SDValue N3,
5118 SDValue N4, SDValue N5) {
5119 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5120 return getNode(Opcode, DL, VTList, Ops);
5123 SDVTList SelectionDAG::getVTList(EVT VT) {
5124 return makeVTList(SDNode::getValueTypeList(VT), 1);
5127 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5128 FoldingSetNodeID ID;
5130 ID.AddInteger(VT1.getRawBits());
5131 ID.AddInteger(VT2.getRawBits());
5134 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5136 EVT *Array = Allocator.Allocate<EVT>(2);
5139 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5140 VTListMap.InsertNode(Result, IP);
5142 return Result->getSDVTList();
5145 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5146 FoldingSetNodeID ID;
5148 ID.AddInteger(VT1.getRawBits());
5149 ID.AddInteger(VT2.getRawBits());
5150 ID.AddInteger(VT3.getRawBits());
5153 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5155 EVT *Array = Allocator.Allocate<EVT>(3);
5159 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5160 VTListMap.InsertNode(Result, IP);
5162 return Result->getSDVTList();
5165 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5166 FoldingSetNodeID ID;
5168 ID.AddInteger(VT1.getRawBits());
5169 ID.AddInteger(VT2.getRawBits());
5170 ID.AddInteger(VT3.getRawBits());
5171 ID.AddInteger(VT4.getRawBits());
5174 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5176 EVT *Array = Allocator.Allocate<EVT>(4);
5181 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5182 VTListMap.InsertNode(Result, IP);
5184 return Result->getSDVTList();
5187 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5188 unsigned NumVTs = VTs.size();
5189 FoldingSetNodeID ID;
5190 ID.AddInteger(NumVTs);
5191 for (unsigned index = 0; index < NumVTs; index++) {
5192 ID.AddInteger(VTs[index].getRawBits());
5196 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5198 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5199 std::copy(VTs.begin(), VTs.end(), Array);
5200 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5201 VTListMap.InsertNode(Result, IP);
5203 return Result->getSDVTList();
5207 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5208 /// specified operands. If the resultant node already exists in the DAG,
5209 /// this does not modify the specified node, instead it returns the node that
5210 /// already exists. If the resultant node does not exist in the DAG, the
5211 /// input node is returned. As a degenerate case, if you specify the same
5212 /// input operands as the node already has, the input node is returned.
5213 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5214 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5216 // Check to see if there is no change.
5217 if (Op == N->getOperand(0)) return N;
5219 // See if the modified node already exists.
5220 void *InsertPos = nullptr;
5221 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5224 // Nope it doesn't. Remove the node from its current place in the maps.
5226 if (!RemoveNodeFromCSEMaps(N))
5227 InsertPos = nullptr;
5229 // Now we update the operands.
5230 N->OperandList[0].set(Op);
5232 // If this gets put into a CSE map, add it.
5233 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5237 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5238 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5240 // Check to see if there is no change.
5241 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5242 return N; // No operands changed, just return the input node.
5244 // See if the modified node already exists.
5245 void *InsertPos = nullptr;
5246 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5249 // Nope it doesn't. Remove the node from its current place in the maps.
5251 if (!RemoveNodeFromCSEMaps(N))
5252 InsertPos = nullptr;
5254 // Now we update the operands.
5255 if (N->OperandList[0] != Op1)
5256 N->OperandList[0].set(Op1);
5257 if (N->OperandList[1] != Op2)
5258 N->OperandList[1].set(Op2);
5260 // If this gets put into a CSE map, add it.
5261 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5265 SDNode *SelectionDAG::
5266 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5267 SDValue Ops[] = { Op1, Op2, Op3 };
5268 return UpdateNodeOperands(N, Ops);
5271 SDNode *SelectionDAG::
5272 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5273 SDValue Op3, SDValue Op4) {
5274 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5275 return UpdateNodeOperands(N, Ops);
5278 SDNode *SelectionDAG::
5279 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5280 SDValue Op3, SDValue Op4, SDValue Op5) {
5281 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5282 return UpdateNodeOperands(N, Ops);
5285 SDNode *SelectionDAG::
5286 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5287 unsigned NumOps = Ops.size();
5288 assert(N->getNumOperands() == NumOps &&
5289 "Update with wrong number of operands");
5291 // Check to see if there is no change.
5292 bool AnyChange = false;
5293 for (unsigned i = 0; i != NumOps; ++i) {
5294 if (Ops[i] != N->getOperand(i)) {
5300 // No operands changed, just return the input node.
5301 if (!AnyChange) return N;
5303 // See if the modified node already exists.
5304 void *InsertPos = nullptr;
5305 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5308 // Nope it doesn't. Remove the node from its current place in the maps.
5310 if (!RemoveNodeFromCSEMaps(N))
5311 InsertPos = nullptr;
5313 // Now we update the operands.
5314 for (unsigned i = 0; i != NumOps; ++i)
5315 if (N->OperandList[i] != Ops[i])
5316 N->OperandList[i].set(Ops[i]);
5318 // If this gets put into a CSE map, add it.
5319 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5323 /// DropOperands - Release the operands and set this node to have
5325 void SDNode::DropOperands() {
5326 // Unlike the code in MorphNodeTo that does this, we don't need to
5327 // watch for dead nodes here.
5328 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5334 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5337 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5339 SDVTList VTs = getVTList(VT);
5340 return SelectNodeTo(N, MachineOpc, VTs, None);
5343 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5344 EVT VT, SDValue Op1) {
5345 SDVTList VTs = getVTList(VT);
5346 SDValue Ops[] = { Op1 };
5347 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5350 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5351 EVT VT, SDValue Op1,
5353 SDVTList VTs = getVTList(VT);
5354 SDValue Ops[] = { Op1, Op2 };
5355 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5358 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5359 EVT VT, SDValue Op1,
5360 SDValue Op2, SDValue Op3) {
5361 SDVTList VTs = getVTList(VT);
5362 SDValue Ops[] = { Op1, Op2, Op3 };
5363 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5366 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5367 EVT VT, ArrayRef<SDValue> Ops) {
5368 SDVTList VTs = getVTList(VT);
5369 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5372 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5373 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5374 SDVTList VTs = getVTList(VT1, VT2);
5375 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5378 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5380 SDVTList VTs = getVTList(VT1, VT2);
5381 return SelectNodeTo(N, MachineOpc, VTs, None);
5384 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5385 EVT VT1, EVT VT2, EVT VT3,
5386 ArrayRef<SDValue> Ops) {
5387 SDVTList VTs = getVTList(VT1, VT2, VT3);
5388 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5391 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5392 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5393 ArrayRef<SDValue> Ops) {
5394 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5395 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5398 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5401 SDVTList VTs = getVTList(VT1, VT2);
5402 SDValue Ops[] = { Op1 };
5403 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5406 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5408 SDValue Op1, SDValue Op2) {
5409 SDVTList VTs = getVTList(VT1, VT2);
5410 SDValue Ops[] = { Op1, Op2 };
5411 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5414 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5416 SDValue Op1, SDValue Op2,
5418 SDVTList VTs = getVTList(VT1, VT2);
5419 SDValue Ops[] = { Op1, Op2, Op3 };
5420 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5423 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5424 EVT VT1, EVT VT2, EVT VT3,
5425 SDValue Op1, SDValue Op2,
5427 SDVTList VTs = getVTList(VT1, VT2, VT3);
5428 SDValue Ops[] = { Op1, Op2, Op3 };
5429 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5432 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5433 SDVTList VTs,ArrayRef<SDValue> Ops) {
5434 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5435 // Reset the NodeID to -1.
5440 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5441 /// the line number information on the merged node since it is not possible to
5442 /// preserve the information that operation is associated with multiple lines.
5443 /// This will make the debugger working better at -O0, were there is a higher
5444 /// probability having other instructions associated with that line.
5446 /// For IROrder, we keep the smaller of the two
5447 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5448 DebugLoc NLoc = N->getDebugLoc();
5449 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5450 (OLoc.getDebugLoc() != NLoc)) {
5451 N->setDebugLoc(DebugLoc());
5453 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5454 N->setIROrder(Order);
5458 /// MorphNodeTo - This *mutates* the specified node to have the specified
5459 /// return type, opcode, and operands.
5461 /// Note that MorphNodeTo returns the resultant node. If there is already a
5462 /// node of the specified opcode and operands, it returns that node instead of
5463 /// the current one. Note that the SDLoc need not be the same.
5465 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5466 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5467 /// node, and because it doesn't require CSE recalculation for any of
5468 /// the node's users.
5470 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5471 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5472 /// the legalizer which maintain worklists that would need to be updated when
5473 /// deleting things.
5474 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5475 SDVTList VTs, ArrayRef<SDValue> Ops) {
5476 unsigned NumOps = Ops.size();
5477 // If an identical node already exists, use it.
5479 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5480 FoldingSetNodeID ID;
5481 AddNodeIDNode(ID, Opc, VTs, Ops);
5482 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5483 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5486 if (!RemoveNodeFromCSEMaps(N))
5489 // Start the morphing.
5491 N->ValueList = VTs.VTs;
5492 N->NumValues = VTs.NumVTs;
5494 // Clear the operands list, updating used nodes to remove this from their
5495 // use list. Keep track of any operands that become dead as a result.
5496 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5497 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5499 SDNode *Used = Use.getNode();
5501 if (Used->use_empty())
5502 DeadNodeSet.insert(Used);
5505 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5506 // Initialize the memory references information.
5507 MN->setMemRefs(nullptr, nullptr);
5508 // If NumOps is larger than the # of operands we can have in a
5509 // MachineSDNode, reallocate the operand list.
5510 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5511 if (MN->OperandsNeedDelete)
5512 delete[] MN->OperandList;
5513 if (NumOps > array_lengthof(MN->LocalOperands))
5514 // We're creating a final node that will live unmorphed for the
5515 // remainder of the current SelectionDAG iteration, so we can allocate
5516 // the operands directly out of a pool with no recycling metadata.
5517 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5518 Ops.data(), NumOps);
5520 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5521 MN->OperandsNeedDelete = false;
5523 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5525 // If NumOps is larger than the # of operands we currently have, reallocate
5526 // the operand list.
5527 if (NumOps > N->NumOperands) {
5528 if (N->OperandsNeedDelete)
5529 delete[] N->OperandList;
5530 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5531 N->OperandsNeedDelete = true;
5533 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5536 // Delete any nodes that are still dead after adding the uses for the
5538 if (!DeadNodeSet.empty()) {
5539 SmallVector<SDNode *, 16> DeadNodes;
5540 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5541 E = DeadNodeSet.end(); I != E; ++I)
5542 if ((*I)->use_empty())
5543 DeadNodes.push_back(*I);
5544 RemoveDeadNodes(DeadNodes);
5548 CSEMap.InsertNode(N, IP); // Memoize the new node.
5553 /// getMachineNode - These are used for target selectors to create a new node
5554 /// with specified return type(s), MachineInstr opcode, and operands.
5556 /// Note that getMachineNode returns the resultant node. If there is already a
5557 /// node of the specified opcode and operands, it returns that node instead of
5558 /// the current one.
5560 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5561 SDVTList VTs = getVTList(VT);
5562 return getMachineNode(Opcode, dl, VTs, None);
5566 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5567 SDVTList VTs = getVTList(VT);
5568 SDValue Ops[] = { Op1 };
5569 return getMachineNode(Opcode, dl, VTs, Ops);
5573 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5574 SDValue Op1, SDValue Op2) {
5575 SDVTList VTs = getVTList(VT);
5576 SDValue Ops[] = { Op1, Op2 };
5577 return getMachineNode(Opcode, dl, VTs, Ops);
5581 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5582 SDValue Op1, SDValue Op2, SDValue Op3) {
5583 SDVTList VTs = getVTList(VT);
5584 SDValue Ops[] = { Op1, Op2, Op3 };
5585 return getMachineNode(Opcode, dl, VTs, Ops);
5589 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5590 ArrayRef<SDValue> Ops) {
5591 SDVTList VTs = getVTList(VT);
5592 return getMachineNode(Opcode, dl, VTs, Ops);
5596 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5597 SDVTList VTs = getVTList(VT1, VT2);
5598 return getMachineNode(Opcode, dl, VTs, None);
5602 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5603 EVT VT1, EVT VT2, SDValue Op1) {
5604 SDVTList VTs = getVTList(VT1, VT2);
5605 SDValue Ops[] = { Op1 };
5606 return getMachineNode(Opcode, dl, VTs, Ops);
5610 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5611 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5612 SDVTList VTs = getVTList(VT1, VT2);
5613 SDValue Ops[] = { Op1, Op2 };
5614 return getMachineNode(Opcode, dl, VTs, Ops);
5618 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5619 EVT VT1, EVT VT2, SDValue Op1,
5620 SDValue Op2, SDValue Op3) {
5621 SDVTList VTs = getVTList(VT1, VT2);
5622 SDValue Ops[] = { Op1, Op2, Op3 };
5623 return getMachineNode(Opcode, dl, VTs, Ops);
5627 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5629 ArrayRef<SDValue> Ops) {
5630 SDVTList VTs = getVTList(VT1, VT2);
5631 return getMachineNode(Opcode, dl, VTs, Ops);
5635 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5636 EVT VT1, EVT VT2, EVT VT3,
5637 SDValue Op1, SDValue Op2) {
5638 SDVTList VTs = getVTList(VT1, VT2, VT3);
5639 SDValue Ops[] = { Op1, Op2 };
5640 return getMachineNode(Opcode, dl, VTs, Ops);
5644 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5645 EVT VT1, EVT VT2, EVT VT3,
5646 SDValue Op1, SDValue Op2, SDValue Op3) {
5647 SDVTList VTs = getVTList(VT1, VT2, VT3);
5648 SDValue Ops[] = { Op1, Op2, Op3 };
5649 return getMachineNode(Opcode, dl, VTs, Ops);
5653 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5654 EVT VT1, EVT VT2, EVT VT3,
5655 ArrayRef<SDValue> Ops) {
5656 SDVTList VTs = getVTList(VT1, VT2, VT3);
5657 return getMachineNode(Opcode, dl, VTs, Ops);
5661 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5662 EVT VT2, EVT VT3, EVT VT4,
5663 ArrayRef<SDValue> Ops) {
5664 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5665 return getMachineNode(Opcode, dl, VTs, Ops);
5669 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5670 ArrayRef<EVT> ResultTys,
5671 ArrayRef<SDValue> Ops) {
5672 SDVTList VTs = getVTList(ResultTys);
5673 return getMachineNode(Opcode, dl, VTs, Ops);
5677 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5678 ArrayRef<SDValue> OpsArray) {
5679 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5682 const SDValue *Ops = OpsArray.data();
5683 unsigned NumOps = OpsArray.size();
5686 FoldingSetNodeID ID;
5687 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5689 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5690 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5694 // Allocate a new MachineSDNode.
5695 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5696 DL.getDebugLoc(), VTs);
5698 // Initialize the operands list.
5699 if (NumOps > array_lengthof(N->LocalOperands))
5700 // We're creating a final node that will live unmorphed for the
5701 // remainder of the current SelectionDAG iteration, so we can allocate
5702 // the operands directly out of a pool with no recycling metadata.
5703 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5706 N->InitOperands(N->LocalOperands, Ops, NumOps);
5707 N->OperandsNeedDelete = false;
5710 CSEMap.InsertNode(N, IP);
5716 /// getTargetExtractSubreg - A convenience function for creating
5717 /// TargetOpcode::EXTRACT_SUBREG nodes.
5719 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5721 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5722 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5723 VT, Operand, SRIdxVal);
5724 return SDValue(Subreg, 0);
5727 /// getTargetInsertSubreg - A convenience function for creating
5728 /// TargetOpcode::INSERT_SUBREG nodes.
5730 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5731 SDValue Operand, SDValue Subreg) {
5732 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5733 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5734 VT, Operand, Subreg, SRIdxVal);
5735 return SDValue(Result, 0);
5738 /// getNodeIfExists - Get the specified node if it's already available, or
5739 /// else return NULL.
5740 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5741 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5743 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5744 FoldingSetNodeID ID;
5745 AddNodeIDNode(ID, Opcode, VTList, Ops);
5746 if (isBinOpWithFlags(Opcode))
5747 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5749 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5755 /// getDbgValue - Creates a SDDbgValue node.
5759 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5760 bool IsIndirect, uint64_t Off,
5761 DebugLoc DL, unsigned O) {
5762 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5767 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5769 DebugLoc DL, unsigned O) {
5770 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5775 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5776 DebugLoc DL, unsigned O) {
5777 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5782 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5783 /// pointed to by a use iterator is deleted, increment the use iterator
5784 /// so that it doesn't dangle.
5786 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5787 SDNode::use_iterator &UI;
5788 SDNode::use_iterator &UE;
5790 void NodeDeleted(SDNode *N, SDNode *E) override {
5791 // Increment the iterator as needed.
5792 while (UI != UE && N == *UI)
5797 RAUWUpdateListener(SelectionDAG &d,
5798 SDNode::use_iterator &ui,
5799 SDNode::use_iterator &ue)
5800 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5805 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5806 /// This can cause recursive merging of nodes in the DAG.
5808 /// This version assumes From has a single result value.
5810 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5811 SDNode *From = FromN.getNode();
5812 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5813 "Cannot replace with this method!");
5814 assert(From != To.getNode() && "Cannot replace uses of with self");
5816 // Iterate over all the existing uses of From. New uses will be added
5817 // to the beginning of the use list, which we avoid visiting.
5818 // This specifically avoids visiting uses of From that arise while the
5819 // replacement is happening, because any such uses would be the result
5820 // of CSE: If an existing node looks like From after one of its operands
5821 // is replaced by To, we don't want to replace of all its users with To
5822 // too. See PR3018 for more info.
5823 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5824 RAUWUpdateListener Listener(*this, UI, UE);
5828 // This node is about to morph, remove its old self from the CSE maps.
5829 RemoveNodeFromCSEMaps(User);
5831 // A user can appear in a use list multiple times, and when this
5832 // happens the uses are usually next to each other in the list.
5833 // To help reduce the number of CSE recomputations, process all
5834 // the uses of this user that we can find this way.
5836 SDUse &Use = UI.getUse();
5839 } while (UI != UE && *UI == User);
5841 // Now that we have modified User, add it back to the CSE maps. If it
5842 // already exists there, recursively merge the results together.
5843 AddModifiedNodeToCSEMaps(User);
5846 // If we just RAUW'd the root, take note.
5847 if (FromN == getRoot())
5851 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5852 /// This can cause recursive merging of nodes in the DAG.
5854 /// This version assumes that for each value of From, there is a
5855 /// corresponding value in To in the same position with the same type.
5857 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5859 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5860 assert((!From->hasAnyUseOfValue(i) ||
5861 From->getValueType(i) == To->getValueType(i)) &&
5862 "Cannot use this version of ReplaceAllUsesWith!");
5865 // Handle the trivial case.
5869 // Iterate over just the existing users of From. See the comments in
5870 // the ReplaceAllUsesWith above.
5871 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5872 RAUWUpdateListener Listener(*this, UI, UE);
5876 // This node is about to morph, remove its old self from the CSE maps.
5877 RemoveNodeFromCSEMaps(User);
5879 // A user can appear in a use list multiple times, and when this
5880 // happens the uses are usually next to each other in the list.
5881 // To help reduce the number of CSE recomputations, process all
5882 // the uses of this user that we can find this way.
5884 SDUse &Use = UI.getUse();
5887 } while (UI != UE && *UI == User);
5889 // Now that we have modified User, add it back to the CSE maps. If it
5890 // already exists there, recursively merge the results together.
5891 AddModifiedNodeToCSEMaps(User);
5894 // If we just RAUW'd the root, take note.
5895 if (From == getRoot().getNode())
5896 setRoot(SDValue(To, getRoot().getResNo()));
5899 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5900 /// This can cause recursive merging of nodes in the DAG.
5902 /// This version can replace From with any result values. To must match the
5903 /// number and types of values returned by From.
5904 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5905 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5906 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5908 // Iterate over just the existing users of From. See the comments in
5909 // the ReplaceAllUsesWith above.
5910 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5911 RAUWUpdateListener Listener(*this, UI, UE);
5915 // This node is about to morph, remove its old self from the CSE maps.
5916 RemoveNodeFromCSEMaps(User);
5918 // A user can appear in a use list multiple times, and when this
5919 // happens the uses are usually next to each other in the list.
5920 // To help reduce the number of CSE recomputations, process all
5921 // the uses of this user that we can find this way.
5923 SDUse &Use = UI.getUse();
5924 const SDValue &ToOp = To[Use.getResNo()];
5927 } while (UI != UE && *UI == User);
5929 // Now that we have modified User, add it back to the CSE maps. If it
5930 // already exists there, recursively merge the results together.
5931 AddModifiedNodeToCSEMaps(User);
5934 // If we just RAUW'd the root, take note.
5935 if (From == getRoot().getNode())
5936 setRoot(SDValue(To[getRoot().getResNo()]));
5939 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5940 /// uses of other values produced by From.getNode() alone. The Deleted
5941 /// vector is handled the same way as for ReplaceAllUsesWith.
5942 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5943 // Handle the really simple, really trivial case efficiently.
5944 if (From == To) return;
5946 // Handle the simple, trivial, case efficiently.
5947 if (From.getNode()->getNumValues() == 1) {
5948 ReplaceAllUsesWith(From, To);
5952 // Iterate over just the existing users of From. See the comments in
5953 // the ReplaceAllUsesWith above.
5954 SDNode::use_iterator UI = From.getNode()->use_begin(),
5955 UE = From.getNode()->use_end();
5956 RAUWUpdateListener Listener(*this, UI, UE);
5959 bool UserRemovedFromCSEMaps = false;
5961 // A user can appear in a use list multiple times, and when this
5962 // happens the uses are usually next to each other in the list.
5963 // To help reduce the number of CSE recomputations, process all
5964 // the uses of this user that we can find this way.
5966 SDUse &Use = UI.getUse();
5968 // Skip uses of different values from the same node.
5969 if (Use.getResNo() != From.getResNo()) {
5974 // If this node hasn't been modified yet, it's still in the CSE maps,
5975 // so remove its old self from the CSE maps.
5976 if (!UserRemovedFromCSEMaps) {
5977 RemoveNodeFromCSEMaps(User);
5978 UserRemovedFromCSEMaps = true;
5983 } while (UI != UE && *UI == User);
5985 // We are iterating over all uses of the From node, so if a use
5986 // doesn't use the specific value, no changes are made.
5987 if (!UserRemovedFromCSEMaps)
5990 // Now that we have modified User, add it back to the CSE maps. If it
5991 // already exists there, recursively merge the results together.
5992 AddModifiedNodeToCSEMaps(User);
5995 // If we just RAUW'd the root, take note.
5996 if (From == getRoot())
6001 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6002 /// to record information about a use.
6009 /// operator< - Sort Memos by User.
6010 bool operator<(const UseMemo &L, const UseMemo &R) {
6011 return (intptr_t)L.User < (intptr_t)R.User;
6015 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6016 /// uses of other values produced by From.getNode() alone. The same value
6017 /// may appear in both the From and To list. The Deleted vector is
6018 /// handled the same way as for ReplaceAllUsesWith.
6019 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6022 // Handle the simple, trivial case efficiently.
6024 return ReplaceAllUsesOfValueWith(*From, *To);
6026 // Read up all the uses and make records of them. This helps
6027 // processing new uses that are introduced during the
6028 // replacement process.
6029 SmallVector<UseMemo, 4> Uses;
6030 for (unsigned i = 0; i != Num; ++i) {
6031 unsigned FromResNo = From[i].getResNo();
6032 SDNode *FromNode = From[i].getNode();
6033 for (SDNode::use_iterator UI = FromNode->use_begin(),
6034 E = FromNode->use_end(); UI != E; ++UI) {
6035 SDUse &Use = UI.getUse();
6036 if (Use.getResNo() == FromResNo) {
6037 UseMemo Memo = { *UI, i, &Use };
6038 Uses.push_back(Memo);
6043 // Sort the uses, so that all the uses from a given User are together.
6044 std::sort(Uses.begin(), Uses.end());
6046 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6047 UseIndex != UseIndexEnd; ) {
6048 // We know that this user uses some value of From. If it is the right
6049 // value, update it.
6050 SDNode *User = Uses[UseIndex].User;
6052 // This node is about to morph, remove its old self from the CSE maps.
6053 RemoveNodeFromCSEMaps(User);
6055 // The Uses array is sorted, so all the uses for a given User
6056 // are next to each other in the list.
6057 // To help reduce the number of CSE recomputations, process all
6058 // the uses of this user that we can find this way.
6060 unsigned i = Uses[UseIndex].Index;
6061 SDUse &Use = *Uses[UseIndex].Use;
6065 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6067 // Now that we have modified User, add it back to the CSE maps. If it
6068 // already exists there, recursively merge the results together.
6069 AddModifiedNodeToCSEMaps(User);
6073 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6074 /// based on their topological order. It returns the maximum id and a vector
6075 /// of the SDNodes* in assigned order by reference.
6076 unsigned SelectionDAG::AssignTopologicalOrder() {
6078 unsigned DAGSize = 0;
6080 // SortedPos tracks the progress of the algorithm. Nodes before it are
6081 // sorted, nodes after it are unsorted. When the algorithm completes
6082 // it is at the end of the list.
6083 allnodes_iterator SortedPos = allnodes_begin();
6085 // Visit all the nodes. Move nodes with no operands to the front of
6086 // the list immediately. Annotate nodes that do have operands with their
6087 // operand count. Before we do this, the Node Id fields of the nodes
6088 // may contain arbitrary values. After, the Node Id fields for nodes
6089 // before SortedPos will contain the topological sort index, and the
6090 // Node Id fields for nodes At SortedPos and after will contain the
6091 // count of outstanding operands.
6092 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6094 checkForCycles(N, this);
6095 unsigned Degree = N->getNumOperands();
6097 // A node with no uses, add it to the result array immediately.
6098 N->setNodeId(DAGSize++);
6099 allnodes_iterator Q = N;
6101 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6102 assert(SortedPos != AllNodes.end() && "Overran node list");
6105 // Temporarily use the Node Id as scratch space for the degree count.
6106 N->setNodeId(Degree);
6110 // Visit all the nodes. As we iterate, move nodes into sorted order,
6111 // such that by the time the end is reached all nodes will be sorted.
6112 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6114 checkForCycles(N, this);
6115 // N is in sorted position, so all its uses have one less operand
6116 // that needs to be sorted.
6117 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6120 unsigned Degree = P->getNodeId();
6121 assert(Degree != 0 && "Invalid node degree");
6124 // All of P's operands are sorted, so P may sorted now.
6125 P->setNodeId(DAGSize++);
6127 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6128 assert(SortedPos != AllNodes.end() && "Overran node list");
6131 // Update P's outstanding operand count.
6132 P->setNodeId(Degree);
6135 if (I == SortedPos) {
6138 dbgs() << "Overran sorted position:\n";
6139 S->dumprFull(this); dbgs() << "\n";
6140 dbgs() << "Checking if this is due to cycles\n";
6141 checkForCycles(this, true);
6143 llvm_unreachable(nullptr);
6147 assert(SortedPos == AllNodes.end() &&
6148 "Topological sort incomplete!");
6149 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6150 "First node in topological sort is not the entry token!");
6151 assert(AllNodes.front().getNodeId() == 0 &&
6152 "First node in topological sort has non-zero id!");
6153 assert(AllNodes.front().getNumOperands() == 0 &&
6154 "First node in topological sort has operands!");
6155 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6156 "Last node in topologic sort has unexpected id!");
6157 assert(AllNodes.back().use_empty() &&
6158 "Last node in topologic sort has users!");
6159 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6163 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6164 /// value is produced by SD.
6165 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6166 DbgInfo->add(DB, SD, isParameter);
6168 SD->setHasDebugValue(true);
6171 /// TransferDbgValues - Transfer SDDbgValues.
6172 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6173 if (From == To || !From.getNode()->getHasDebugValue())
6175 SDNode *FromNode = From.getNode();
6176 SDNode *ToNode = To.getNode();
6177 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6178 SmallVector<SDDbgValue *, 2> ClonedDVs;
6179 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6181 SDDbgValue *Dbg = *I;
6182 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6183 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6185 Dbg->getOffset(), Dbg->getDebugLoc(),
6187 ClonedDVs.push_back(Clone);
6190 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6191 E = ClonedDVs.end(); I != E; ++I)
6192 AddDbgValue(*I, ToNode, false);
6195 //===----------------------------------------------------------------------===//
6197 //===----------------------------------------------------------------------===//
6199 HandleSDNode::~HandleSDNode() {
6203 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6204 DebugLoc DL, const GlobalValue *GA,
6205 EVT VT, int64_t o, unsigned char TF)
6206 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6210 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6211 SDValue X, unsigned SrcAS,
6213 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6214 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6216 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6217 EVT memvt, MachineMemOperand *mmo)
6218 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6219 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6220 MMO->isNonTemporal(), MMO->isInvariant());
6221 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6222 assert(isNonTemporal() == MMO->isNonTemporal() &&
6223 "Non-temporal encoding error!");
6224 // We check here that the size of the memory operand fits within the size of
6225 // the MMO. This is because the MMO might indicate only a possible address
6226 // range instead of specifying the affected memory addresses precisely.
6227 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6230 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6231 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6232 : SDNode(Opc, Order, dl, VTs, Ops),
6233 MemoryVT(memvt), MMO(mmo) {
6234 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6235 MMO->isNonTemporal(), MMO->isInvariant());
6236 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6237 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6240 /// Profile - Gather unique data for the node.
6242 void SDNode::Profile(FoldingSetNodeID &ID) const {
6243 AddNodeIDNode(ID, this);
6248 std::vector<EVT> VTs;
6251 VTs.reserve(MVT::LAST_VALUETYPE);
6252 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6253 VTs.push_back(MVT((MVT::SimpleValueType)i));
6258 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6259 static ManagedStatic<EVTArray> SimpleVTArray;
6260 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6262 /// getValueTypeList - Return a pointer to the specified value type.
6264 const EVT *SDNode::getValueTypeList(EVT VT) {
6265 if (VT.isExtended()) {
6266 sys::SmartScopedLock<true> Lock(*VTMutex);
6267 return &(*EVTs->insert(VT).first);
6269 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6270 "Value type out of range!");
6271 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6275 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6276 /// indicated value. This method ignores uses of other values defined by this
6278 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6279 assert(Value < getNumValues() && "Bad value!");
6281 // TODO: Only iterate over uses of a given value of the node
6282 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6283 if (UI.getUse().getResNo() == Value) {
6290 // Found exactly the right number of uses?
6295 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6296 /// value. This method ignores uses of other values defined by this operation.
6297 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6298 assert(Value < getNumValues() && "Bad value!");
6300 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6301 if (UI.getUse().getResNo() == Value)
6308 /// isOnlyUserOf - Return true if this node is the only use of N.
6310 bool SDNode::isOnlyUserOf(SDNode *N) const {
6312 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6323 /// isOperand - Return true if this node is an operand of N.
6325 bool SDValue::isOperandOf(SDNode *N) const {
6326 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6327 if (*this == N->getOperand(i))
6332 bool SDNode::isOperandOf(SDNode *N) const {
6333 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6334 if (this == N->OperandList[i].getNode())
6339 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6340 /// be a chain) reaches the specified operand without crossing any
6341 /// side-effecting instructions on any chain path. In practice, this looks
6342 /// through token factors and non-volatile loads. In order to remain efficient,
6343 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6344 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6345 unsigned Depth) const {
6346 if (*this == Dest) return true;
6348 // Don't search too deeply, we just want to be able to see through
6349 // TokenFactor's etc.
6350 if (Depth == 0) return false;
6352 // If this is a token factor, all inputs to the TF happen in parallel. If any
6353 // of the operands of the TF does not reach dest, then we cannot do the xform.
6354 if (getOpcode() == ISD::TokenFactor) {
6355 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6356 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6361 // Loads don't have side effects, look through them.
6362 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6363 if (!Ld->isVolatile())
6364 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6369 /// hasPredecessor - Return true if N is a predecessor of this node.
6370 /// N is either an operand of this node, or can be reached by recursively
6371 /// traversing up the operands.
6372 /// NOTE: This is an expensive method. Use it carefully.
6373 bool SDNode::hasPredecessor(const SDNode *N) const {
6374 SmallPtrSet<const SDNode *, 32> Visited;
6375 SmallVector<const SDNode *, 16> Worklist;
6376 return hasPredecessorHelper(N, Visited, Worklist);
6380 SDNode::hasPredecessorHelper(const SDNode *N,
6381 SmallPtrSet<const SDNode *, 32> &Visited,
6382 SmallVectorImpl<const SDNode *> &Worklist) const {
6383 if (Visited.empty()) {
6384 Worklist.push_back(this);
6386 // Take a look in the visited set. If we've already encountered this node
6387 // we needn't search further.
6388 if (Visited.count(N))
6392 // Haven't visited N yet. Continue the search.
6393 while (!Worklist.empty()) {
6394 const SDNode *M = Worklist.pop_back_val();
6395 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6396 SDNode *Op = M->getOperand(i).getNode();
6397 if (Visited.insert(Op))
6398 Worklist.push_back(Op);
6407 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6408 assert(Num < NumOperands && "Invalid child # of SDNode!");
6409 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6412 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6413 assert(N->getNumValues() == 1 &&
6414 "Can't unroll a vector with multiple results!");
6416 EVT VT = N->getValueType(0);
6417 unsigned NE = VT.getVectorNumElements();
6418 EVT EltVT = VT.getVectorElementType();
6421 SmallVector<SDValue, 8> Scalars;
6422 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6424 // If ResNE is 0, fully unroll the vector op.
6427 else if (NE > ResNE)
6431 for (i= 0; i != NE; ++i) {
6432 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6433 SDValue Operand = N->getOperand(j);
6434 EVT OperandVT = Operand.getValueType();
6435 if (OperandVT.isVector()) {
6436 // A vector operand; extract a single element.
6437 const TargetLowering *TLI = TM.getTargetLowering();
6438 EVT OperandEltVT = OperandVT.getVectorElementType();
6439 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6442 getConstant(i, TLI->getVectorIdxTy()));
6444 // A scalar operand; just use it as is.
6445 Operands[j] = Operand;
6449 switch (N->getOpcode()) {
6451 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6454 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6461 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6462 getShiftAmountOperand(Operands[0].getValueType(),
6465 case ISD::SIGN_EXTEND_INREG:
6466 case ISD::FP_ROUND_INREG: {
6467 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6468 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6470 getValueType(ExtVT)));
6475 for (; i < ResNE; ++i)
6476 Scalars.push_back(getUNDEF(EltVT));
6478 return getNode(ISD::BUILD_VECTOR, dl,
6479 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6483 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6484 /// location that is 'Dist' units away from the location that the 'Base' load
6485 /// is loading from.
6486 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6487 unsigned Bytes, int Dist) const {
6488 if (LD->getChain() != Base->getChain())
6490 EVT VT = LD->getValueType(0);
6491 if (VT.getSizeInBits() / 8 != Bytes)
6494 SDValue Loc = LD->getOperand(1);
6495 SDValue BaseLoc = Base->getOperand(1);
6496 if (Loc.getOpcode() == ISD::FrameIndex) {
6497 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6499 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6500 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6501 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6502 int FS = MFI->getObjectSize(FI);
6503 int BFS = MFI->getObjectSize(BFI);
6504 if (FS != BFS || FS != (int)Bytes) return false;
6505 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6509 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6510 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6513 const GlobalValue *GV1 = nullptr;
6514 const GlobalValue *GV2 = nullptr;
6515 int64_t Offset1 = 0;
6516 int64_t Offset2 = 0;
6517 const TargetLowering *TLI = TM.getTargetLowering();
6518 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6519 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6520 if (isGA1 && isGA2 && GV1 == GV2)
6521 return Offset1 == (Offset2 + Dist*Bytes);
6526 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6527 /// it cannot be inferred.
6528 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6529 // If this is a GlobalAddress + cst, return the alignment.
6530 const GlobalValue *GV;
6531 int64_t GVOffset = 0;
6532 const TargetLowering *TLI = TM.getTargetLowering();
6533 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6534 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6535 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6536 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6537 TLI->getDataLayout());
6538 unsigned AlignBits = KnownZero.countTrailingOnes();
6539 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6541 return MinAlign(Align, GVOffset);
6544 // If this is a direct reference to a stack slot, use information about the
6545 // stack slot's alignment.
6546 int FrameIdx = 1 << 31;
6547 int64_t FrameOffset = 0;
6548 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6549 FrameIdx = FI->getIndex();
6550 } else if (isBaseWithConstantOffset(Ptr) &&
6551 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6553 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6554 FrameOffset = Ptr.getConstantOperandVal(1);
6557 if (FrameIdx != (1 << 31)) {
6558 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6559 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6567 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6568 /// which is split (or expanded) into two not necessarily identical pieces.
6569 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6570 // Currently all types are split in half.
6572 if (!VT.isVector()) {
6573 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6575 unsigned NumElements = VT.getVectorNumElements();
6576 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6577 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6580 return std::make_pair(LoVT, HiVT);
6583 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6585 std::pair<SDValue, SDValue>
6586 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6588 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6589 N.getValueType().getVectorNumElements() &&
6590 "More vector elements requested than available!");
6592 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6593 getConstant(0, TLI->getVectorIdxTy()));
6594 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6595 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6596 return std::make_pair(Lo, Hi);
6599 void SelectionDAG::ExtractVectorElements(SDValue Op,
6600 SmallVectorImpl<SDValue> &Args,
6601 unsigned Start, unsigned Count) {
6602 EVT VT = Op.getValueType();
6604 Count = VT.getVectorNumElements();
6606 EVT EltVT = VT.getVectorElementType();
6607 EVT IdxTy = TLI->getVectorIdxTy();
6609 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6610 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6611 Op, getConstant(i, IdxTy)));
6615 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6616 unsigned GlobalAddressSDNode::getAddressSpace() const {
6617 return getGlobal()->getType()->getAddressSpace();
6621 Type *ConstantPoolSDNode::getType() const {
6622 if (isMachineConstantPoolEntry())
6623 return Val.MachineCPVal->getType();
6624 return Val.ConstVal->getType();
6627 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6629 unsigned &SplatBitSize,
6631 unsigned MinSplatBits,
6632 bool isBigEndian) const {
6633 EVT VT = getValueType(0);
6634 assert(VT.isVector() && "Expected a vector type");
6635 unsigned sz = VT.getSizeInBits();
6636 if (MinSplatBits > sz)
6639 SplatValue = APInt(sz, 0);
6640 SplatUndef = APInt(sz, 0);
6642 // Get the bits. Bits with undefined values (when the corresponding element
6643 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6644 // in SplatValue. If any of the values are not constant, give up and return
6646 unsigned int nOps = getNumOperands();
6647 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6648 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6650 for (unsigned j = 0; j < nOps; ++j) {
6651 unsigned i = isBigEndian ? nOps-1-j : j;
6652 SDValue OpVal = getOperand(i);
6653 unsigned BitPos = j * EltBitSize;
6655 if (OpVal.getOpcode() == ISD::UNDEF)
6656 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6657 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6658 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6659 zextOrTrunc(sz) << BitPos;
6660 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6661 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6666 // The build_vector is all constants or undefs. Find the smallest element
6667 // size that splats the vector.
6669 HasAnyUndefs = (SplatUndef != 0);
6672 unsigned HalfSize = sz / 2;
6673 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6674 APInt LowValue = SplatValue.trunc(HalfSize);
6675 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6676 APInt LowUndef = SplatUndef.trunc(HalfSize);
6678 // If the two halves do not match (ignoring undef bits), stop here.
6679 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6680 MinSplatBits > HalfSize)
6683 SplatValue = HighValue | LowValue;
6684 SplatUndef = HighUndef & LowUndef;
6693 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6694 if (UndefElements) {
6695 UndefElements->clear();
6696 UndefElements->resize(getNumOperands());
6699 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6700 SDValue Op = getOperand(i);
6701 if (Op.getOpcode() == ISD::UNDEF) {
6703 (*UndefElements)[i] = true;
6704 } else if (!Splatted) {
6706 } else if (Splatted != Op) {
6712 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6713 "Can only have a splat without a constant for all undefs.");
6714 return getOperand(0);
6721 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6722 return dyn_cast_or_null<ConstantSDNode>(
6723 getSplatValue(UndefElements).getNode());
6727 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6728 return dyn_cast_or_null<ConstantFPSDNode>(
6729 getSplatValue(UndefElements).getNode());
6732 bool BuildVectorSDNode::isConstant() const {
6733 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6734 unsigned Opc = getOperand(i).getOpcode();
6735 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6741 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6742 // Find the first non-undef value in the shuffle mask.
6744 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6747 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6749 // Make sure all remaining elements are either undef or the same as the first
6751 for (int Idx = Mask[i]; i != e; ++i)
6752 if (Mask[i] >= 0 && Mask[i] != Idx)
6758 static void checkForCyclesHelper(const SDNode *N,
6759 SmallPtrSet<const SDNode*, 32> &Visited,
6760 SmallPtrSet<const SDNode*, 32> &Checked,
6761 const llvm::SelectionDAG *DAG) {
6762 // If this node has already been checked, don't check it again.
6763 if (Checked.count(N))
6766 // If a node has already been visited on this depth-first walk, reject it as
6768 if (!Visited.insert(N)) {
6769 errs() << "Detected cycle in SelectionDAG\n";
6770 dbgs() << "Offending node:\n";
6771 N->dumprFull(DAG); dbgs() << "\n";
6775 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6776 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6783 void llvm::checkForCycles(const llvm::SDNode *N,
6784 const llvm::SelectionDAG *DAG,
6792 assert(N && "Checking nonexistent SDNode");
6793 SmallPtrSet<const SDNode*, 32> visited;
6794 SmallPtrSet<const SDNode*, 32> checked;
6795 checkForCyclesHelper(N, visited, checked, DAG);
6800 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6801 checkForCycles(DAG->getRoot().getNode(), DAG, force);