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();
705 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
706 /// correspond to it. This is useful when we're about to delete or repurpose
707 /// the node. We don't want future request for structurally identical nodes
708 /// to return N anymore.
709 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
711 switch (N->getOpcode()) {
712 case ISD::HANDLENODE: return false; // noop.
714 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
715 "Cond code doesn't exist!");
716 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
717 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
719 case ISD::ExternalSymbol:
720 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
722 case ISD::TargetExternalSymbol: {
723 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
724 Erased = TargetExternalSymbols.erase(
725 std::pair<std::string,unsigned char>(ESN->getSymbol(),
726 ESN->getTargetFlags()));
729 case ISD::VALUETYPE: {
730 EVT VT = cast<VTSDNode>(N)->getVT();
731 if (VT.isExtended()) {
732 Erased = ExtendedValueTypeNodes.erase(VT);
734 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
735 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
740 // Remove it from the CSE Map.
741 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
742 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
743 Erased = CSEMap.RemoveNode(N);
747 // Verify that the node was actually in one of the CSE maps, unless it has a
748 // flag result (which cannot be CSE'd) or is one of the special cases that are
749 // not subject to CSE.
750 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
751 !N->isMachineOpcode() && !doNotCSE(N)) {
754 llvm_unreachable("Node is not in map!");
760 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
761 /// maps and modified in place. Add it back to the CSE maps, unless an identical
762 /// node already exists, in which case transfer all its users to the existing
763 /// node. This transfer can potentially trigger recursive merging.
766 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
767 // For node types that aren't CSE'd, just act as if no identical node
770 SDNode *Existing = CSEMap.GetOrInsertNode(N);
772 // If there was already an existing matching node, use ReplaceAllUsesWith
773 // to replace the dead one with the existing one. This can cause
774 // recursive merging of other unrelated nodes down the line.
775 ReplaceAllUsesWith(N, Existing);
777 // N is now dead. Inform the listeners and delete it.
778 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
779 DUL->NodeDeleted(N, Existing);
780 DeleteNodeNotInCSEMaps(N);
785 // If the node doesn't already exist, we updated it. Inform listeners.
786 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
790 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
791 /// were replaced with those specified. If this node is never memoized,
792 /// return null, otherwise return a pointer to the slot it would take. If a
793 /// node already exists with these operands, the slot will be non-null.
794 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
799 SDValue Ops[] = { Op };
801 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
802 AddNodeIDCustom(ID, N);
803 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
807 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
808 /// were replaced with those specified. If this node is never memoized,
809 /// return null, otherwise return a pointer to the slot it would take. If a
810 /// node already exists with these operands, the slot will be non-null.
811 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
812 SDValue Op1, SDValue Op2,
817 SDValue Ops[] = { Op1, Op2 };
819 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
820 AddNodeIDCustom(ID, N);
821 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
826 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
827 /// were replaced with those specified. If this node is never memoized,
828 /// return null, otherwise return a pointer to the slot it would take. If a
829 /// node already exists with these operands, the slot will be non-null.
830 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
836 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
837 AddNodeIDCustom(ID, N);
838 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
843 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
844 static void VerifyNodeCommon(SDNode *N) {
845 switch (N->getOpcode()) {
848 case ISD::BUILD_PAIR: {
849 EVT VT = N->getValueType(0);
850 assert(N->getNumValues() == 1 && "Too many results!");
851 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
852 "Wrong return type!");
853 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
854 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
855 "Mismatched operand types!");
856 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
857 "Wrong operand type!");
858 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
859 "Wrong return type size");
862 case ISD::BUILD_VECTOR: {
863 assert(N->getNumValues() == 1 && "Too many results!");
864 assert(N->getValueType(0).isVector() && "Wrong return type!");
865 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
866 "Wrong number of operands!");
867 EVT EltVT = N->getValueType(0).getVectorElementType();
868 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
869 assert((I->getValueType() == EltVT ||
870 (EltVT.isInteger() && I->getValueType().isInteger() &&
871 EltVT.bitsLE(I->getValueType()))) &&
872 "Wrong operand type!");
873 assert(I->getValueType() == N->getOperand(0).getValueType() &&
874 "Operands must all have the same type");
881 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
882 static void VerifySDNode(SDNode *N) {
883 // The SDNode allocators cannot be used to allocate nodes with fields that are
884 // not present in an SDNode!
885 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
886 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
887 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
888 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
889 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
890 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
891 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
892 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
893 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
894 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
895 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
896 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
897 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
898 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
899 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
900 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
901 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
902 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
903 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
908 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
910 static void VerifyMachineNode(SDNode *N) {
911 // The MachineNode allocators cannot be used to allocate nodes with fields
912 // that are not present in a MachineNode!
913 // Currently there are no such nodes.
919 /// getEVTAlignment - Compute the default alignment value for the
922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
923 Type *Ty = VT == MVT::iPTR ?
924 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
925 VT.getTypeForEVT(*getContext());
927 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
930 // EntryNode could meaningfully have debug info if we can find it...
931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
932 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
935 UpdateListeners(nullptr) {
936 AllNodes.push_back(&EntryNode);
937 DbgInfo = new SDDbgInfo();
940 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
943 Context = &mf.getFunction()->getContext();
946 SelectionDAG::~SelectionDAG() {
947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
952 void SelectionDAG::allnodes_clear() {
953 assert(&*AllNodes.begin() == &EntryNode);
954 AllNodes.remove(AllNodes.begin());
955 while (!AllNodes.empty())
956 DeallocateNode(AllNodes.begin());
959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
960 SDVTList VTs, SDValue N1,
961 SDValue N2, bool nuw, bool nsw,
963 if (isBinOpWithFlags(Opcode)) {
964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
966 FN->setHasNoUnsignedWrap(nuw);
967 FN->setHasNoSignedWrap(nsw);
968 FN->setIsExact(exact);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 void SelectionDAG::clear() {
980 OperandAllocator.Reset();
983 ExtendedValueTypeNodes.clear();
984 ExternalSymbols.clear();
985 TargetExternalSymbols.clear();
986 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
987 static_cast<CondCodeSDNode*>(nullptr));
988 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
989 static_cast<SDNode*>(nullptr));
991 EntryNode.UseList = nullptr;
992 AllNodes.push_back(&EntryNode);
993 Root = getEntryNode();
997 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
998 return VT.bitsGT(Op.getValueType()) ?
999 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1000 getNode(ISD::TRUNCATE, DL, VT, Op);
1003 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1004 return VT.bitsGT(Op.getValueType()) ?
1005 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1006 getNode(ISD::TRUNCATE, DL, VT, Op);
1009 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1010 return VT.bitsGT(Op.getValueType()) ?
1011 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1012 getNode(ISD::TRUNCATE, DL, VT, Op);
1015 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1017 if (VT.bitsLE(Op.getValueType()))
1018 return getNode(ISD::TRUNCATE, SL, VT, Op);
1020 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1021 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1024 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1025 assert(!VT.isVector() &&
1026 "getZeroExtendInReg should use the vector element type instead of "
1027 "the vector type!");
1028 if (Op.getValueType() == VT) return Op;
1029 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1030 APInt Imm = APInt::getLowBitsSet(BitWidth,
1031 VT.getSizeInBits());
1032 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1033 getConstant(Imm, Op.getValueType()));
1036 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1037 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1038 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1039 "The sizes of the input and result must match in order to perform the "
1040 "extend in-register.");
1041 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1042 "The destination vector type must have fewer lanes than the input.");
1043 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1046 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1048 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1049 EVT EltVT = VT.getScalarType();
1051 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1052 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1055 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1056 EVT EltVT = VT.getScalarType();
1058 switch (TLI->getBooleanContents(VT)) {
1059 case TargetLowering::ZeroOrOneBooleanContent:
1060 case TargetLowering::UndefinedBooleanContent:
1061 TrueValue = getConstant(1, VT);
1063 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1064 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1068 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1071 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1072 EVT EltVT = VT.getScalarType();
1073 assert((EltVT.getSizeInBits() >= 64 ||
1074 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1075 "getConstant with a uint64_t value that doesn't fit in the type!");
1076 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1079 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1081 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1084 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1086 assert(VT.isInteger() && "Cannot create FP integer constant!");
1088 EVT EltVT = VT.getScalarType();
1089 const ConstantInt *Elt = &Val;
1091 const TargetLowering *TLI = TM.getTargetLowering();
1093 // In some cases the vector type is legal but the element type is illegal and
1094 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1095 // inserted value (the type does not need to match the vector element type).
1096 // Any extra bits introduced will be truncated away.
1097 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1098 TargetLowering::TypePromoteInteger) {
1099 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1100 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1101 Elt = ConstantInt::get(*getContext(), NewVal);
1103 // In other cases the element type is illegal and needs to be expanded, for
1104 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1105 // the value into n parts and use a vector type with n-times the elements.
1106 // Then bitcast to the type requested.
1107 // Legalizing constants too early makes the DAGCombiner's job harder so we
1108 // only legalize if the DAG tells us we must produce legal types.
1109 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1110 TLI->getTypeAction(*getContext(), EltVT) ==
1111 TargetLowering::TypeExpandInteger) {
1112 APInt NewVal = Elt->getValue();
1113 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1114 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1115 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1116 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1118 // Check the temporary vector is the correct size. If this fails then
1119 // getTypeToTransformTo() probably returned a type whose size (in bits)
1120 // isn't a power-of-2 factor of the requested type size.
1121 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1123 SmallVector<SDValue, 2> EltParts;
1124 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1125 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1126 .trunc(ViaEltSizeInBits),
1127 ViaEltVT, isT, isO));
1130 // EltParts is currently in little endian order. If we actually want
1131 // big-endian order then reverse it now.
1132 if (TLI->isBigEndian())
1133 std::reverse(EltParts.begin(), EltParts.end());
1135 // The elements must be reversed when the element order is different
1136 // to the endianness of the elements (because the BITCAST is itself a
1137 // vector shuffle in this situation). However, we do not need any code to
1138 // perform this reversal because getConstant() is producing a vector
1140 // This situation occurs in MIPS MSA.
1142 SmallVector<SDValue, 8> Ops;
1143 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1144 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1146 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1147 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1152 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1153 "APInt size does not match type size!");
1154 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1155 FoldingSetNodeID ID;
1156 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1160 SDNode *N = nullptr;
1161 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1163 return SDValue(N, 0);
1166 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1167 CSEMap.InsertNode(N, IP);
1168 AllNodes.push_back(N);
1171 SDValue Result(N, 0);
1172 if (VT.isVector()) {
1173 SmallVector<SDValue, 8> Ops;
1174 Ops.assign(VT.getVectorNumElements(), Result);
1175 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1180 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1181 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1185 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1186 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1189 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1190 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1192 EVT EltVT = VT.getScalarType();
1194 // Do the map lookup using the actual bit pattern for the floating point
1195 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1196 // we don't have issues with SNANs.
1197 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1198 FoldingSetNodeID ID;
1199 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1202 SDNode *N = nullptr;
1203 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1205 return SDValue(N, 0);
1208 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1209 CSEMap.InsertNode(N, IP);
1210 AllNodes.push_back(N);
1213 SDValue Result(N, 0);
1214 if (VT.isVector()) {
1215 SmallVector<SDValue, 8> Ops;
1216 Ops.assign(VT.getVectorNumElements(), Result);
1217 // FIXME SDLoc info might be appropriate here
1218 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1223 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1224 EVT EltVT = VT.getScalarType();
1225 if (EltVT==MVT::f32)
1226 return getConstantFP(APFloat((float)Val), VT, isTarget);
1227 else if (EltVT==MVT::f64)
1228 return getConstantFP(APFloat(Val), VT, isTarget);
1229 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1232 APFloat apf = APFloat(Val);
1233 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1235 return getConstantFP(apf, VT, isTarget);
1237 llvm_unreachable("Unsupported type in getConstantFP");
1240 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1241 EVT VT, int64_t Offset,
1243 unsigned char TargetFlags) {
1244 assert((TargetFlags == 0 || isTargetGA) &&
1245 "Cannot set target flags on target-independent globals");
1246 const TargetLowering *TLI = TM.getTargetLowering();
1248 // Truncate (with sign-extension) the offset value to the pointer size.
1249 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1251 Offset = SignExtend64(Offset, BitWidth);
1254 if (GV->isThreadLocal())
1255 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1257 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1259 FoldingSetNodeID ID;
1260 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1262 ID.AddInteger(Offset);
1263 ID.AddInteger(TargetFlags);
1264 ID.AddInteger(GV->getType()->getAddressSpace());
1266 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1267 return SDValue(E, 0);
1269 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1270 DL.getDebugLoc(), GV, VT,
1271 Offset, TargetFlags);
1272 CSEMap.InsertNode(N, IP);
1273 AllNodes.push_back(N);
1274 return SDValue(N, 0);
1277 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1278 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1279 FoldingSetNodeID ID;
1280 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1283 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1284 return SDValue(E, 0);
1286 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1287 CSEMap.InsertNode(N, IP);
1288 AllNodes.push_back(N);
1289 return SDValue(N, 0);
1292 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1293 unsigned char TargetFlags) {
1294 assert((TargetFlags == 0 || isTarget) &&
1295 "Cannot set target flags on target-independent jump tables");
1296 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1297 FoldingSetNodeID ID;
1298 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1300 ID.AddInteger(TargetFlags);
1302 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1303 return SDValue(E, 0);
1305 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1307 CSEMap.InsertNode(N, IP);
1308 AllNodes.push_back(N);
1309 return SDValue(N, 0);
1312 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1313 unsigned Alignment, int Offset,
1315 unsigned char TargetFlags) {
1316 assert((TargetFlags == 0 || isTarget) &&
1317 "Cannot set target flags on target-independent globals");
1320 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1321 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1322 FoldingSetNodeID ID;
1323 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1324 ID.AddInteger(Alignment);
1325 ID.AddInteger(Offset);
1327 ID.AddInteger(TargetFlags);
1329 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1330 return SDValue(E, 0);
1332 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1333 Alignment, TargetFlags);
1334 CSEMap.InsertNode(N, IP);
1335 AllNodes.push_back(N);
1336 return SDValue(N, 0);
1340 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1341 unsigned Alignment, int Offset,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent globals");
1348 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1349 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1350 FoldingSetNodeID ID;
1351 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1352 ID.AddInteger(Alignment);
1353 ID.AddInteger(Offset);
1354 C->addSelectionDAGCSEId(ID);
1355 ID.AddInteger(TargetFlags);
1357 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1358 return SDValue(E, 0);
1360 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1361 Alignment, TargetFlags);
1362 CSEMap.InsertNode(N, IP);
1363 AllNodes.push_back(N);
1364 return SDValue(N, 0);
1367 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1368 unsigned char TargetFlags) {
1369 FoldingSetNodeID ID;
1370 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1371 ID.AddInteger(Index);
1372 ID.AddInteger(Offset);
1373 ID.AddInteger(TargetFlags);
1375 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1376 return SDValue(E, 0);
1378 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1380 CSEMap.InsertNode(N, IP);
1381 AllNodes.push_back(N);
1382 return SDValue(N, 0);
1385 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1386 FoldingSetNodeID ID;
1387 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1390 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1391 return SDValue(E, 0);
1393 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1394 CSEMap.InsertNode(N, IP);
1395 AllNodes.push_back(N);
1396 return SDValue(N, 0);
1399 SDValue SelectionDAG::getValueType(EVT VT) {
1400 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1401 ValueTypeNodes.size())
1402 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1404 SDNode *&N = VT.isExtended() ?
1405 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1407 if (N) return SDValue(N, 0);
1408 N = new (NodeAllocator) VTSDNode(VT);
1409 AllNodes.push_back(N);
1410 return SDValue(N, 0);
1413 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1414 SDNode *&N = ExternalSymbols[Sym];
1415 if (N) return SDValue(N, 0);
1416 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1417 AllNodes.push_back(N);
1418 return SDValue(N, 0);
1421 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1422 unsigned char TargetFlags) {
1424 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1426 if (N) return SDValue(N, 0);
1427 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1428 AllNodes.push_back(N);
1429 return SDValue(N, 0);
1432 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1433 if ((unsigned)Cond >= CondCodeNodes.size())
1434 CondCodeNodes.resize(Cond+1);
1436 if (!CondCodeNodes[Cond]) {
1437 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1438 CondCodeNodes[Cond] = N;
1439 AllNodes.push_back(N);
1442 return SDValue(CondCodeNodes[Cond], 0);
1445 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1446 // the shuffle mask M that point at N1 to point at N2, and indices that point
1447 // N2 to point at N1.
1448 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1450 int NElts = M.size();
1451 for (int i = 0; i != NElts; ++i) {
1459 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1460 SDValue N2, const int *Mask) {
1461 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1462 "Invalid VECTOR_SHUFFLE");
1464 // Canonicalize shuffle undef, undef -> undef
1465 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1466 return getUNDEF(VT);
1468 // Validate that all indices in Mask are within the range of the elements
1469 // input to the shuffle.
1470 unsigned NElts = VT.getVectorNumElements();
1471 SmallVector<int, 8> MaskVec;
1472 for (unsigned i = 0; i != NElts; ++i) {
1473 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1474 MaskVec.push_back(Mask[i]);
1477 // Canonicalize shuffle v, v -> v, undef
1480 for (unsigned i = 0; i != NElts; ++i)
1481 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1484 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1485 if (N1.getOpcode() == ISD::UNDEF)
1486 commuteShuffle(N1, N2, MaskVec);
1488 // Canonicalize all index into lhs, -> shuffle lhs, undef
1489 // Canonicalize all index into rhs, -> shuffle rhs, undef
1490 bool AllLHS = true, AllRHS = true;
1491 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1492 for (unsigned i = 0; i != NElts; ++i) {
1493 if (MaskVec[i] >= (int)NElts) {
1498 } else if (MaskVec[i] >= 0) {
1502 if (AllLHS && AllRHS)
1503 return getUNDEF(VT);
1504 if (AllLHS && !N2Undef)
1508 commuteShuffle(N1, N2, MaskVec);
1510 // Reset our undef status after accounting for the mask.
1511 N2Undef = N2.getOpcode() == ISD::UNDEF;
1512 // Re-check whether both sides ended up undef.
1513 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1514 return getUNDEF(VT);
1516 // If Identity shuffle return that node.
1517 bool Identity = true;
1518 for (unsigned i = 0; i != NElts; ++i) {
1519 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1521 if (Identity && NElts)
1524 // Shuffling a constant splat doesn't change the result.
1528 // Look through any bitcasts. We check that these don't change the number
1529 // (and size) of elements and just changes their types.
1530 while (V.getOpcode() == ISD::BITCAST)
1531 V = V->getOperand(0);
1533 // A splat should always show up as a build vector node.
1534 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1535 BitVector UndefElements;
1536 SDValue Splat = BV->getSplatValue(&UndefElements);
1537 // If this is a splat of an undef, shuffling it is also undef.
1538 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1539 return getUNDEF(VT);
1541 // We only have a splat which can skip shuffles if there is a splatted
1542 // value and no undef lanes rearranged by the shuffle.
1543 if (Splat && UndefElements.none()) {
1544 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1545 // number of elements match or the value splatted is a zero constant.
1546 if (V.getValueType().getVectorNumElements() ==
1547 VT.getVectorNumElements())
1549 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1550 if (C->isNullValue())
1556 FoldingSetNodeID ID;
1557 SDValue Ops[2] = { N1, N2 };
1558 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1559 for (unsigned i = 0; i != NElts; ++i)
1560 ID.AddInteger(MaskVec[i]);
1563 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1564 return SDValue(E, 0);
1566 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1567 // SDNode doesn't have access to it. This memory will be "leaked" when
1568 // the node is deallocated, but recovered when the NodeAllocator is released.
1569 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1570 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1572 ShuffleVectorSDNode *N =
1573 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1574 dl.getDebugLoc(), N1, N2,
1576 CSEMap.InsertNode(N, IP);
1577 AllNodes.push_back(N);
1578 return SDValue(N, 0);
1581 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1582 SDValue Val, SDValue DTy,
1583 SDValue STy, SDValue Rnd, SDValue Sat,
1584 ISD::CvtCode Code) {
1585 // If the src and dest types are the same and the conversion is between
1586 // integer types of the same sign or two floats, no conversion is necessary.
1588 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1591 FoldingSetNodeID ID;
1592 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1593 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1595 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1596 return SDValue(E, 0);
1598 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1601 CSEMap.InsertNode(N, IP);
1602 AllNodes.push_back(N);
1603 return SDValue(N, 0);
1606 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1607 FoldingSetNodeID ID;
1608 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1609 ID.AddInteger(RegNo);
1611 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1612 return SDValue(E, 0);
1614 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1615 CSEMap.InsertNode(N, IP);
1616 AllNodes.push_back(N);
1617 return SDValue(N, 0);
1620 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1621 FoldingSetNodeID ID;
1622 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1623 ID.AddPointer(RegMask);
1625 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1626 return SDValue(E, 0);
1628 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1629 CSEMap.InsertNode(N, IP);
1630 AllNodes.push_back(N);
1631 return SDValue(N, 0);
1634 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1635 FoldingSetNodeID ID;
1636 SDValue Ops[] = { Root };
1637 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1638 ID.AddPointer(Label);
1640 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1641 return SDValue(E, 0);
1643 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1644 dl.getDebugLoc(), Root, Label);
1645 CSEMap.InsertNode(N, IP);
1646 AllNodes.push_back(N);
1647 return SDValue(N, 0);
1651 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1654 unsigned char TargetFlags) {
1655 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1657 FoldingSetNodeID ID;
1658 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1660 ID.AddInteger(Offset);
1661 ID.AddInteger(TargetFlags);
1663 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1664 return SDValue(E, 0);
1666 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1668 CSEMap.InsertNode(N, IP);
1669 AllNodes.push_back(N);
1670 return SDValue(N, 0);
1673 SDValue SelectionDAG::getSrcValue(const Value *V) {
1674 assert((!V || V->getType()->isPointerTy()) &&
1675 "SrcValue is not a pointer?");
1677 FoldingSetNodeID ID;
1678 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1682 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1683 return SDValue(E, 0);
1685 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1686 CSEMap.InsertNode(N, IP);
1687 AllNodes.push_back(N);
1688 return SDValue(N, 0);
1691 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1692 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1693 FoldingSetNodeID ID;
1694 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1698 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1699 return SDValue(E, 0);
1701 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1702 CSEMap.InsertNode(N, IP);
1703 AllNodes.push_back(N);
1704 return SDValue(N, 0);
1707 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1708 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1709 unsigned SrcAS, unsigned DestAS) {
1710 SDValue Ops[] = {Ptr};
1711 FoldingSetNodeID ID;
1712 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1713 ID.AddInteger(SrcAS);
1714 ID.AddInteger(DestAS);
1717 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1718 return SDValue(E, 0);
1720 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1722 VT, Ptr, SrcAS, DestAS);
1723 CSEMap.InsertNode(N, IP);
1724 AllNodes.push_back(N);
1725 return SDValue(N, 0);
1728 /// getShiftAmountOperand - Return the specified value casted to
1729 /// the target's desired shift amount type.
1730 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1731 EVT OpTy = Op.getValueType();
1732 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1733 if (OpTy == ShTy || OpTy.isVector()) return Op;
1735 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1736 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1739 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1740 /// specified value type.
1741 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1742 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1743 unsigned ByteSize = VT.getStoreSize();
1744 Type *Ty = VT.getTypeForEVT(*getContext());
1745 const TargetLowering *TLI = TM.getTargetLowering();
1746 unsigned StackAlign =
1747 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1749 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1750 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1753 /// CreateStackTemporary - Create a stack temporary suitable for holding
1754 /// either of the specified value types.
1755 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1756 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1757 VT2.getStoreSizeInBits())/8;
1758 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1759 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1760 const TargetLowering *TLI = TM.getTargetLowering();
1761 const DataLayout *TD = TLI->getDataLayout();
1762 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1763 TD->getPrefTypeAlignment(Ty2));
1765 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1766 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1767 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1770 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1771 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1772 // These setcc operations always fold.
1776 case ISD::SETFALSE2: return getConstant(0, VT);
1778 case ISD::SETTRUE2: {
1779 const TargetLowering *TLI = TM.getTargetLowering();
1780 TargetLowering::BooleanContent Cnt =
1781 TLI->getBooleanContents(N1->getValueType(0));
1783 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1796 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1800 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1801 const APInt &C2 = N2C->getAPIntValue();
1802 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1803 const APInt &C1 = N1C->getAPIntValue();
1806 default: llvm_unreachable("Unknown integer setcc!");
1807 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1808 case ISD::SETNE: return getConstant(C1 != C2, VT);
1809 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1810 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1811 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1812 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1813 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1814 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1815 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1816 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1820 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1821 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1822 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1825 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1826 return getUNDEF(VT);
1828 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1829 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1830 return getUNDEF(VT);
1832 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1833 R==APFloat::cmpLessThan, VT);
1834 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1835 return getUNDEF(VT);
1837 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1838 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1839 return getUNDEF(VT);
1841 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1842 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1843 return getUNDEF(VT);
1845 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1846 R==APFloat::cmpEqual, VT);
1847 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1848 return getUNDEF(VT);
1850 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1851 R==APFloat::cmpEqual, VT);
1852 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1853 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1854 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1855 R==APFloat::cmpEqual, VT);
1856 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1857 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1858 R==APFloat::cmpLessThan, VT);
1859 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1860 R==APFloat::cmpUnordered, VT);
1861 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1862 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1865 // Ensure that the constant occurs on the RHS.
1866 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1867 MVT CompVT = N1.getValueType().getSimpleVT();
1868 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1871 return getSetCC(dl, VT, N2, N1, SwappedCond);
1875 // Could not fold it.
1879 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1880 /// use this predicate to simplify operations downstream.
1881 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1882 // This predicate is not safe for vector operations.
1883 if (Op.getValueType().isVector())
1886 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1887 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1890 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1891 /// this predicate to simplify operations downstream. Mask is known to be zero
1892 /// for bits that V cannot have.
1893 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1894 unsigned Depth) const {
1895 APInt KnownZero, KnownOne;
1896 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1897 return (KnownZero & Mask) == Mask;
1900 /// Determine which bits of Op are known to be either zero or one and return
1901 /// them in the KnownZero/KnownOne bitsets.
1902 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1903 APInt &KnownOne, unsigned Depth) const {
1904 const TargetLowering *TLI = TM.getTargetLowering();
1905 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1907 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1909 return; // Limit search depth.
1911 APInt KnownZero2, KnownOne2;
1913 switch (Op.getOpcode()) {
1915 // We know all of the bits for a constant!
1916 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1917 KnownZero = ~KnownOne;
1920 // If either the LHS or the RHS are Zero, the result is zero.
1921 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1922 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1924 // Output known-1 bits are only known if set in both the LHS & RHS.
1925 KnownOne &= KnownOne2;
1926 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1927 KnownZero |= KnownZero2;
1930 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1931 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1933 // Output known-0 bits are only known if clear in both the LHS & RHS.
1934 KnownZero &= KnownZero2;
1935 // Output known-1 are known to be set if set in either the LHS | RHS.
1936 KnownOne |= KnownOne2;
1939 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1940 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1942 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1943 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1944 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1945 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1946 KnownZero = KnownZeroOut;
1950 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1951 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1953 // If low bits are zero in either operand, output low known-0 bits.
1954 // Also compute a conserative estimate for high known-0 bits.
1955 // More trickiness is possible, but this is sufficient for the
1956 // interesting case of alignment computation.
1957 KnownOne.clearAllBits();
1958 unsigned TrailZ = KnownZero.countTrailingOnes() +
1959 KnownZero2.countTrailingOnes();
1960 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1961 KnownZero2.countLeadingOnes(),
1962 BitWidth) - BitWidth;
1964 TrailZ = std::min(TrailZ, BitWidth);
1965 LeadZ = std::min(LeadZ, BitWidth);
1966 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1967 APInt::getHighBitsSet(BitWidth, LeadZ);
1971 // For the purposes of computing leading zeros we can conservatively
1972 // treat a udiv as a logical right shift by the power of 2 known to
1973 // be less than the denominator.
1974 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1975 unsigned LeadZ = KnownZero2.countLeadingOnes();
1977 KnownOne2.clearAllBits();
1978 KnownZero2.clearAllBits();
1979 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1980 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1981 if (RHSUnknownLeadingOnes != BitWidth)
1982 LeadZ = std::min(BitWidth,
1983 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1985 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1989 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1990 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1992 // Only known if known in both the LHS and RHS.
1993 KnownOne &= KnownOne2;
1994 KnownZero &= KnownZero2;
1996 case ISD::SELECT_CC:
1997 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1998 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2000 // Only known if known in both the LHS and RHS.
2001 KnownOne &= KnownOne2;
2002 KnownZero &= KnownZero2;
2010 if (Op.getResNo() != 1)
2012 // The boolean result conforms to getBooleanContents.
2013 // If we know the result of a setcc has the top bits zero, use this info.
2014 // We know that we have an integer-based boolean since these operations
2015 // are only available for integer.
2016 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2017 TargetLowering::ZeroOrOneBooleanContent &&
2019 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2022 // If we know the result of a setcc has the top bits zero, use this info.
2023 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2024 TargetLowering::ZeroOrOneBooleanContent &&
2026 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2029 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2030 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2031 unsigned ShAmt = SA->getZExtValue();
2033 // If the shift count is an invalid immediate, don't do anything.
2034 if (ShAmt >= BitWidth)
2037 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2038 KnownZero <<= ShAmt;
2040 // low bits known zero.
2041 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2045 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2046 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2047 unsigned ShAmt = SA->getZExtValue();
2049 // If the shift count is an invalid immediate, don't do anything.
2050 if (ShAmt >= BitWidth)
2053 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2054 KnownZero = KnownZero.lshr(ShAmt);
2055 KnownOne = KnownOne.lshr(ShAmt);
2057 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2058 KnownZero |= HighBits; // High bits known zero.
2062 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2063 unsigned ShAmt = SA->getZExtValue();
2065 // If the shift count is an invalid immediate, don't do anything.
2066 if (ShAmt >= BitWidth)
2069 // If any of the demanded bits are produced by the sign extension, we also
2070 // demand the input sign bit.
2071 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2073 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2074 KnownZero = KnownZero.lshr(ShAmt);
2075 KnownOne = KnownOne.lshr(ShAmt);
2077 // Handle the sign bits.
2078 APInt SignBit = APInt::getSignBit(BitWidth);
2079 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2081 if (KnownZero.intersects(SignBit)) {
2082 KnownZero |= HighBits; // New bits are known zero.
2083 } else if (KnownOne.intersects(SignBit)) {
2084 KnownOne |= HighBits; // New bits are known one.
2088 case ISD::SIGN_EXTEND_INREG: {
2089 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2090 unsigned EBits = EVT.getScalarType().getSizeInBits();
2092 // Sign extension. Compute the demanded bits in the result that are not
2093 // present in the input.
2094 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2096 APInt InSignBit = APInt::getSignBit(EBits);
2097 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2099 // If the sign extended bits are demanded, we know that the sign
2101 InSignBit = InSignBit.zext(BitWidth);
2102 if (NewBits.getBoolValue())
2103 InputDemandedBits |= InSignBit;
2105 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2106 KnownOne &= InputDemandedBits;
2107 KnownZero &= InputDemandedBits;
2109 // If the sign bit of the input is known set or clear, then we know the
2110 // top bits of the result.
2111 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2112 KnownZero |= NewBits;
2113 KnownOne &= ~NewBits;
2114 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2115 KnownOne |= NewBits;
2116 KnownZero &= ~NewBits;
2117 } else { // Input sign bit unknown
2118 KnownZero &= ~NewBits;
2119 KnownOne &= ~NewBits;
2124 case ISD::CTTZ_ZERO_UNDEF:
2126 case ISD::CTLZ_ZERO_UNDEF:
2128 unsigned LowBits = Log2_32(BitWidth)+1;
2129 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2130 KnownOne.clearAllBits();
2134 LoadSDNode *LD = cast<LoadSDNode>(Op);
2135 // If this is a ZEXTLoad and we are looking at the loaded value.
2136 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2137 EVT VT = LD->getMemoryVT();
2138 unsigned MemBits = VT.getScalarType().getSizeInBits();
2139 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2140 } else if (const MDNode *Ranges = LD->getRanges()) {
2141 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2145 case ISD::ZERO_EXTEND: {
2146 EVT InVT = Op.getOperand(0).getValueType();
2147 unsigned InBits = InVT.getScalarType().getSizeInBits();
2148 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2149 KnownZero = KnownZero.trunc(InBits);
2150 KnownOne = KnownOne.trunc(InBits);
2151 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2152 KnownZero = KnownZero.zext(BitWidth);
2153 KnownOne = KnownOne.zext(BitWidth);
2154 KnownZero |= NewBits;
2157 case ISD::SIGN_EXTEND: {
2158 EVT InVT = Op.getOperand(0).getValueType();
2159 unsigned InBits = InVT.getScalarType().getSizeInBits();
2160 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2162 KnownZero = KnownZero.trunc(InBits);
2163 KnownOne = KnownOne.trunc(InBits);
2164 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2166 // Note if the sign bit is known to be zero or one.
2167 bool SignBitKnownZero = KnownZero.isNegative();
2168 bool SignBitKnownOne = KnownOne.isNegative();
2170 KnownZero = KnownZero.zext(BitWidth);
2171 KnownOne = KnownOne.zext(BitWidth);
2173 // If the sign bit is known zero or one, the top bits match.
2174 if (SignBitKnownZero)
2175 KnownZero |= NewBits;
2176 else if (SignBitKnownOne)
2177 KnownOne |= NewBits;
2180 case ISD::ANY_EXTEND: {
2181 EVT InVT = Op.getOperand(0).getValueType();
2182 unsigned InBits = InVT.getScalarType().getSizeInBits();
2183 KnownZero = KnownZero.trunc(InBits);
2184 KnownOne = KnownOne.trunc(InBits);
2185 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2186 KnownZero = KnownZero.zext(BitWidth);
2187 KnownOne = KnownOne.zext(BitWidth);
2190 case ISD::TRUNCATE: {
2191 EVT InVT = Op.getOperand(0).getValueType();
2192 unsigned InBits = InVT.getScalarType().getSizeInBits();
2193 KnownZero = KnownZero.zext(InBits);
2194 KnownOne = KnownOne.zext(InBits);
2195 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2196 KnownZero = KnownZero.trunc(BitWidth);
2197 KnownOne = KnownOne.trunc(BitWidth);
2200 case ISD::AssertZext: {
2201 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2202 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2203 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2204 KnownZero |= (~InMask);
2205 KnownOne &= (~KnownZero);
2209 // All bits are zero except the low bit.
2210 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2214 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2215 // We know that the top bits of C-X are clear if X contains less bits
2216 // than C (i.e. no wrap-around can happen). For example, 20-X is
2217 // positive if we can prove that X is >= 0 and < 16.
2218 if (CLHS->getAPIntValue().isNonNegative()) {
2219 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2220 // NLZ can't be BitWidth with no sign bit
2221 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2222 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2224 // If all of the MaskV bits are known to be zero, then we know the
2225 // output top bits are zero, because we now know that the output is
2227 if ((KnownZero2 & MaskV) == MaskV) {
2228 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2229 // Top bits known zero.
2230 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2238 // Output known-0 bits are known if clear or set in both the low clear bits
2239 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2240 // low 3 bits clear.
2241 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2242 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2244 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2245 KnownZeroOut = std::min(KnownZeroOut,
2246 KnownZero2.countTrailingOnes());
2248 if (Op.getOpcode() == ISD::ADD) {
2249 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2253 // With ADDE, a carry bit may be added in, so we can only use this
2254 // information if we know (at least) that the low two bits are clear. We
2255 // then return to the caller that the low bit is unknown but that other bits
2257 if (KnownZeroOut >= 2) // ADDE
2258 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2262 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2263 const APInt &RA = Rem->getAPIntValue().abs();
2264 if (RA.isPowerOf2()) {
2265 APInt LowBits = RA - 1;
2266 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2268 // The low bits of the first operand are unchanged by the srem.
2269 KnownZero = KnownZero2 & LowBits;
2270 KnownOne = KnownOne2 & LowBits;
2272 // If the first operand is non-negative or has all low bits zero, then
2273 // the upper bits are all zero.
2274 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2275 KnownZero |= ~LowBits;
2277 // If the first operand is negative and not all low bits are zero, then
2278 // the upper bits are all one.
2279 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2280 KnownOne |= ~LowBits;
2281 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2286 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2287 const APInt &RA = Rem->getAPIntValue();
2288 if (RA.isPowerOf2()) {
2289 APInt LowBits = (RA - 1);
2290 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2292 // The upper bits are all zero, the lower ones are unchanged.
2293 KnownZero = KnownZero2 | ~LowBits;
2294 KnownOne = KnownOne2 & LowBits;
2299 // Since the result is less than or equal to either operand, any leading
2300 // zero bits in either operand must also exist in the result.
2301 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2302 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2304 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2305 KnownZero2.countLeadingOnes());
2306 KnownOne.clearAllBits();
2307 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2310 case ISD::FrameIndex:
2311 case ISD::TargetFrameIndex:
2312 if (unsigned Align = InferPtrAlignment(Op)) {
2313 // The low bits are known zero if the pointer is aligned.
2314 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2320 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2323 case ISD::INTRINSIC_WO_CHAIN:
2324 case ISD::INTRINSIC_W_CHAIN:
2325 case ISD::INTRINSIC_VOID:
2326 // Allow the target to implement this method for its nodes.
2327 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2331 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2334 /// ComputeNumSignBits - Return the number of times the sign bit of the
2335 /// register is replicated into the other bits. We know that at least 1 bit
2336 /// is always equal to the sign bit (itself), but other cases can give us
2337 /// information. For example, immediately after an "SRA X, 2", we know that
2338 /// the top 3 bits are all equal to each other, so we return 3.
2339 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2340 const TargetLowering *TLI = TM.getTargetLowering();
2341 EVT VT = Op.getValueType();
2342 assert(VT.isInteger() && "Invalid VT!");
2343 unsigned VTBits = VT.getScalarType().getSizeInBits();
2345 unsigned FirstAnswer = 1;
2348 return 1; // Limit search depth.
2350 switch (Op.getOpcode()) {
2352 case ISD::AssertSext:
2353 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2354 return VTBits-Tmp+1;
2355 case ISD::AssertZext:
2356 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2359 case ISD::Constant: {
2360 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2361 return Val.getNumSignBits();
2364 case ISD::SIGN_EXTEND:
2366 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2367 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2369 case ISD::SIGN_EXTEND_INREG:
2370 // Max of the input and what this extends.
2372 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2375 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2376 return std::max(Tmp, Tmp2);
2379 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2380 // SRA X, C -> adds C sign bits.
2381 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2382 Tmp += C->getZExtValue();
2383 if (Tmp > VTBits) Tmp = VTBits;
2387 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2388 // shl destroys sign bits.
2389 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2390 if (C->getZExtValue() >= VTBits || // Bad shift.
2391 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2392 return Tmp - C->getZExtValue();
2397 case ISD::XOR: // NOT is handled here.
2398 // Logical binary ops preserve the number of sign bits at the worst.
2399 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2401 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2402 FirstAnswer = std::min(Tmp, Tmp2);
2403 // We computed what we know about the sign bits as our first
2404 // answer. Now proceed to the generic code that uses
2405 // computeKnownBits, and pick whichever answer is better.
2410 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2411 if (Tmp == 1) return 1; // Early out.
2412 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2413 return std::min(Tmp, Tmp2);
2421 if (Op.getResNo() != 1)
2423 // The boolean result conforms to getBooleanContents. Fall through.
2424 // If setcc returns 0/-1, all bits are sign bits.
2425 // We know that we have an integer-based boolean since these operations
2426 // are only available for integer.
2427 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2428 TargetLowering::ZeroOrNegativeOneBooleanContent)
2432 // If setcc returns 0/-1, all bits are sign bits.
2433 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2434 TargetLowering::ZeroOrNegativeOneBooleanContent)
2439 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2440 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2442 // Handle rotate right by N like a rotate left by 32-N.
2443 if (Op.getOpcode() == ISD::ROTR)
2444 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2446 // If we aren't rotating out all of the known-in sign bits, return the
2447 // number that are left. This handles rotl(sext(x), 1) for example.
2448 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2449 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2453 // Add can have at most one carry bit. Thus we know that the output
2454 // is, at worst, one more bit than the inputs.
2455 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2456 if (Tmp == 1) return 1; // Early out.
2458 // Special case decrementing a value (ADD X, -1):
2459 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2460 if (CRHS->isAllOnesValue()) {
2461 APInt KnownZero, KnownOne;
2462 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2464 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2466 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2469 // If we are subtracting one from a positive number, there is no carry
2470 // out of the result.
2471 if (KnownZero.isNegative())
2475 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2476 if (Tmp2 == 1) return 1;
2477 return std::min(Tmp, Tmp2)-1;
2480 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2481 if (Tmp2 == 1) return 1;
2484 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2485 if (CLHS->isNullValue()) {
2486 APInt KnownZero, KnownOne;
2487 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2488 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2490 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2493 // If the input is known to be positive (the sign bit is known clear),
2494 // the output of the NEG has the same number of sign bits as the input.
2495 if (KnownZero.isNegative())
2498 // Otherwise, we treat this like a SUB.
2501 // Sub can have at most one carry bit. Thus we know that the output
2502 // is, at worst, one more bit than the inputs.
2503 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2504 if (Tmp == 1) return 1; // Early out.
2505 return std::min(Tmp, Tmp2)-1;
2507 // FIXME: it's tricky to do anything useful for this, but it is an important
2508 // case for targets like X86.
2512 // If we are looking at the loaded value of the SDNode.
2513 if (Op.getResNo() == 0) {
2514 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2515 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2516 unsigned ExtType = LD->getExtensionType();
2519 case ISD::SEXTLOAD: // '17' bits known
2520 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2521 return VTBits-Tmp+1;
2522 case ISD::ZEXTLOAD: // '16' bits known
2523 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2529 // Allow the target to implement this method for its nodes.
2530 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2531 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2532 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2533 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2534 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2535 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2538 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2539 // use this information.
2540 APInt KnownZero, KnownOne;
2541 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2544 if (KnownZero.isNegative()) { // sign bit is 0
2546 } else if (KnownOne.isNegative()) { // sign bit is 1;
2553 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2554 // the number of identical bits in the top of the input value.
2556 Mask <<= Mask.getBitWidth()-VTBits;
2557 // Return # leading zeros. We use 'min' here in case Val was zero before
2558 // shifting. We don't want to return '64' as for an i32 "0".
2559 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2562 /// isBaseWithConstantOffset - Return true if the specified operand is an
2563 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2564 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2565 /// semantics as an ADD. This handles the equivalence:
2566 /// X|Cst == X+Cst iff X&Cst = 0.
2567 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2568 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2569 !isa<ConstantSDNode>(Op.getOperand(1)))
2572 if (Op.getOpcode() == ISD::OR &&
2573 !MaskedValueIsZero(Op.getOperand(0),
2574 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2581 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2582 // If we're told that NaNs won't happen, assume they won't.
2583 if (getTarget().Options.NoNaNsFPMath)
2586 // If the value is a constant, we can obviously see if it is a NaN or not.
2587 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2588 return !C->getValueAPF().isNaN();
2590 // TODO: Recognize more cases here.
2595 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2596 // If the value is a constant, we can obviously see if it is a zero or not.
2597 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2598 return !C->isZero();
2600 // TODO: Recognize more cases here.
2601 switch (Op.getOpcode()) {
2604 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2605 return !C->isNullValue();
2612 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2613 // Check the obvious case.
2614 if (A == B) return true;
2616 // For for negative and positive zero.
2617 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2618 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2619 if (CA->isZero() && CB->isZero()) return true;
2621 // Otherwise they may not be equal.
2625 /// getNode - Gets or creates the specified node.
2627 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2628 FoldingSetNodeID ID;
2629 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2631 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2632 return SDValue(E, 0);
2634 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2635 DL.getDebugLoc(), getVTList(VT));
2636 CSEMap.InsertNode(N, IP);
2638 AllNodes.push_back(N);
2642 return SDValue(N, 0);
2645 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2646 EVT VT, SDValue Operand) {
2647 // Constant fold unary operations with an integer constant operand. Even
2648 // opaque constant will be folded, because the folding of unary operations
2649 // doesn't create new constants with different values. Nevertheless, the
2650 // opaque flag is preserved during folding to prevent future folding with
2652 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2653 const APInt &Val = C->getAPIntValue();
2656 case ISD::SIGN_EXTEND:
2657 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2658 C->isTargetOpcode(), C->isOpaque());
2659 case ISD::ANY_EXTEND:
2660 case ISD::ZERO_EXTEND:
2662 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2663 C->isTargetOpcode(), C->isOpaque());
2664 case ISD::UINT_TO_FP:
2665 case ISD::SINT_TO_FP: {
2666 APFloat apf(EVTToAPFloatSemantics(VT),
2667 APInt::getNullValue(VT.getSizeInBits()));
2668 (void)apf.convertFromAPInt(Val,
2669 Opcode==ISD::SINT_TO_FP,
2670 APFloat::rmNearestTiesToEven);
2671 return getConstantFP(apf, VT);
2674 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2675 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2676 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2677 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2680 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2683 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2686 case ISD::CTLZ_ZERO_UNDEF:
2687 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2690 case ISD::CTTZ_ZERO_UNDEF:
2691 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2696 // Constant fold unary operations with a floating point constant operand.
2697 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2698 APFloat V = C->getValueAPF(); // make copy
2702 return getConstantFP(V, VT);
2705 return getConstantFP(V, VT);
2707 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2708 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2709 return getConstantFP(V, VT);
2713 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2714 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2715 return getConstantFP(V, VT);
2719 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2720 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2721 return getConstantFP(V, VT);
2724 case ISD::FP_EXTEND: {
2726 // This can return overflow, underflow, or inexact; we don't care.
2727 // FIXME need to be more flexible about rounding mode.
2728 (void)V.convert(EVTToAPFloatSemantics(VT),
2729 APFloat::rmNearestTiesToEven, &ignored);
2730 return getConstantFP(V, VT);
2732 case ISD::FP_TO_SINT:
2733 case ISD::FP_TO_UINT: {
2736 assert(integerPartWidth >= 64);
2737 // FIXME need to be more flexible about rounding mode.
2738 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2739 Opcode==ISD::FP_TO_SINT,
2740 APFloat::rmTowardZero, &ignored);
2741 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2743 APInt api(VT.getSizeInBits(), x);
2744 return getConstant(api, VT);
2747 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2748 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2749 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2750 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2755 unsigned OpOpcode = Operand.getNode()->getOpcode();
2757 case ISD::TokenFactor:
2758 case ISD::MERGE_VALUES:
2759 case ISD::CONCAT_VECTORS:
2760 return Operand; // Factor, merge or concat of one node? No need.
2761 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2762 case ISD::FP_EXTEND:
2763 assert(VT.isFloatingPoint() &&
2764 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2765 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2766 assert((!VT.isVector() ||
2767 VT.getVectorNumElements() ==
2768 Operand.getValueType().getVectorNumElements()) &&
2769 "Vector element count mismatch!");
2770 if (Operand.getOpcode() == ISD::UNDEF)
2771 return getUNDEF(VT);
2773 case ISD::SIGN_EXTEND:
2774 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2775 "Invalid SIGN_EXTEND!");
2776 if (Operand.getValueType() == VT) return Operand; // noop extension
2777 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2778 "Invalid sext node, dst < src!");
2779 assert((!VT.isVector() ||
2780 VT.getVectorNumElements() ==
2781 Operand.getValueType().getVectorNumElements()) &&
2782 "Vector element count mismatch!");
2783 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2784 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2785 else if (OpOpcode == ISD::UNDEF)
2786 // sext(undef) = 0, because the top bits will all be the same.
2787 return getConstant(0, VT);
2789 case ISD::ZERO_EXTEND:
2790 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2791 "Invalid ZERO_EXTEND!");
2792 if (Operand.getValueType() == VT) return Operand; // noop extension
2793 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2794 "Invalid zext node, dst < src!");
2795 assert((!VT.isVector() ||
2796 VT.getVectorNumElements() ==
2797 Operand.getValueType().getVectorNumElements()) &&
2798 "Vector element count mismatch!");
2799 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2800 return getNode(ISD::ZERO_EXTEND, DL, VT,
2801 Operand.getNode()->getOperand(0));
2802 else if (OpOpcode == ISD::UNDEF)
2803 // zext(undef) = 0, because the top bits will be zero.
2804 return getConstant(0, VT);
2806 case ISD::ANY_EXTEND:
2807 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2808 "Invalid ANY_EXTEND!");
2809 if (Operand.getValueType() == VT) return Operand; // noop extension
2810 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2811 "Invalid anyext node, dst < src!");
2812 assert((!VT.isVector() ||
2813 VT.getVectorNumElements() ==
2814 Operand.getValueType().getVectorNumElements()) &&
2815 "Vector element count mismatch!");
2817 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2818 OpOpcode == ISD::ANY_EXTEND)
2819 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2820 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2821 else if (OpOpcode == ISD::UNDEF)
2822 return getUNDEF(VT);
2824 // (ext (trunx x)) -> x
2825 if (OpOpcode == ISD::TRUNCATE) {
2826 SDValue OpOp = Operand.getNode()->getOperand(0);
2827 if (OpOp.getValueType() == VT)
2832 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2833 "Invalid TRUNCATE!");
2834 if (Operand.getValueType() == VT) return Operand; // noop truncate
2835 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2836 "Invalid truncate node, src < dst!");
2837 assert((!VT.isVector() ||
2838 VT.getVectorNumElements() ==
2839 Operand.getValueType().getVectorNumElements()) &&
2840 "Vector element count mismatch!");
2841 if (OpOpcode == ISD::TRUNCATE)
2842 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2843 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2844 OpOpcode == ISD::ANY_EXTEND) {
2845 // If the source is smaller than the dest, we still need an extend.
2846 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2847 .bitsLT(VT.getScalarType()))
2848 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2849 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2850 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2851 return Operand.getNode()->getOperand(0);
2853 if (OpOpcode == ISD::UNDEF)
2854 return getUNDEF(VT);
2857 // Basic sanity checking.
2858 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2859 && "Cannot BITCAST between types of different sizes!");
2860 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2861 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2862 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2863 if (OpOpcode == ISD::UNDEF)
2864 return getUNDEF(VT);
2866 case ISD::SCALAR_TO_VECTOR:
2867 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2868 (VT.getVectorElementType() == Operand.getValueType() ||
2869 (VT.getVectorElementType().isInteger() &&
2870 Operand.getValueType().isInteger() &&
2871 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2872 "Illegal SCALAR_TO_VECTOR node!");
2873 if (OpOpcode == ISD::UNDEF)
2874 return getUNDEF(VT);
2875 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2876 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2877 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2878 Operand.getConstantOperandVal(1) == 0 &&
2879 Operand.getOperand(0).getValueType() == VT)
2880 return Operand.getOperand(0);
2883 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2884 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2885 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2886 Operand.getNode()->getOperand(0));
2887 if (OpOpcode == ISD::FNEG) // --X -> X
2888 return Operand.getNode()->getOperand(0);
2891 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2892 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2897 SDVTList VTs = getVTList(VT);
2898 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2899 FoldingSetNodeID ID;
2900 SDValue Ops[1] = { Operand };
2901 AddNodeIDNode(ID, Opcode, VTs, Ops);
2903 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2904 return SDValue(E, 0);
2906 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2907 DL.getDebugLoc(), VTs, Operand);
2908 CSEMap.InsertNode(N, IP);
2910 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2911 DL.getDebugLoc(), VTs, Operand);
2914 AllNodes.push_back(N);
2918 return SDValue(N, 0);
2921 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2922 SDNode *Cst1, SDNode *Cst2) {
2923 // If the opcode is a target-specific ISD node, there's nothing we can
2924 // do here and the operand rules may not line up with the below, so
2926 if (Opcode >= ISD::BUILTIN_OP_END)
2929 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2930 SmallVector<SDValue, 4> Outputs;
2931 EVT SVT = VT.getScalarType();
2933 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2934 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2935 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2938 if (Scalar1 && Scalar2)
2939 // Scalar instruction.
2940 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2942 // For vectors extract each constant element into Inputs so we can constant
2943 // fold them individually.
2944 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2945 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2949 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2951 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2952 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2953 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2954 if (!V1 || !V2) // Not a constant, bail.
2957 if (V1->isOpaque() || V2->isOpaque())
2960 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2961 // FIXME: This is valid and could be handled by truncating the APInts.
2962 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2965 Inputs.push_back(std::make_pair(V1, V2));
2969 // We have a number of constant values, constant fold them element by element.
2970 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2971 const APInt &C1 = Inputs[I].first->getAPIntValue();
2972 const APInt &C2 = Inputs[I].second->getAPIntValue();
2976 Outputs.push_back(getConstant(C1 + C2, SVT));
2979 Outputs.push_back(getConstant(C1 - C2, SVT));
2982 Outputs.push_back(getConstant(C1 * C2, SVT));
2985 if (!C2.getBoolValue())
2987 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2990 if (!C2.getBoolValue())
2992 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2995 if (!C2.getBoolValue())
2997 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3000 if (!C2.getBoolValue())
3002 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3005 Outputs.push_back(getConstant(C1 & C2, SVT));
3008 Outputs.push_back(getConstant(C1 | C2, SVT));
3011 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3014 Outputs.push_back(getConstant(C1 << C2, SVT));
3017 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3020 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3023 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3026 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3033 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3034 "Expected a scalar or vector!"));
3036 // Handle the scalar case first.
3038 return Outputs.back();
3040 // We may have a vector type but a scalar result. Create a splat.
3041 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3043 // Build a big vector out of the scalar elements we generated.
3044 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3047 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3048 SDValue N2, bool nuw, bool nsw, bool exact) {
3049 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3050 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3053 case ISD::TokenFactor:
3054 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3055 N2.getValueType() == MVT::Other && "Invalid token factor!");
3056 // Fold trivial token factors.
3057 if (N1.getOpcode() == ISD::EntryToken) return N2;
3058 if (N2.getOpcode() == ISD::EntryToken) return N1;
3059 if (N1 == N2) return N1;
3061 case ISD::CONCAT_VECTORS:
3062 // Concat of UNDEFs is UNDEF.
3063 if (N1.getOpcode() == ISD::UNDEF &&
3064 N2.getOpcode() == ISD::UNDEF)
3065 return getUNDEF(VT);
3067 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3068 // one big BUILD_VECTOR.
3069 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3070 N2.getOpcode() == ISD::BUILD_VECTOR) {
3071 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3072 N1.getNode()->op_end());
3073 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3074 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3078 assert(VT.isInteger() && "This operator does not apply to FP types!");
3079 assert(N1.getValueType() == N2.getValueType() &&
3080 N1.getValueType() == VT && "Binary operator types must match!");
3081 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3082 // worth handling here.
3083 if (N2C && N2C->isNullValue())
3085 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3092 assert(VT.isInteger() && "This operator does not apply to FP types!");
3093 assert(N1.getValueType() == N2.getValueType() &&
3094 N1.getValueType() == VT && "Binary operator types must match!");
3095 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3096 // it's worth handling here.
3097 if (N2C && N2C->isNullValue())
3107 assert(VT.isInteger() && "This operator does not apply to FP types!");
3108 assert(N1.getValueType() == N2.getValueType() &&
3109 N1.getValueType() == VT && "Binary operator types must match!");
3116 if (getTarget().Options.UnsafeFPMath) {
3117 if (Opcode == ISD::FADD) {
3119 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3120 if (CFP->getValueAPF().isZero())
3123 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3124 if (CFP->getValueAPF().isZero())
3126 } else if (Opcode == ISD::FSUB) {
3128 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3129 if (CFP->getValueAPF().isZero())
3131 } else if (Opcode == ISD::FMUL) {
3132 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3135 // If the first operand isn't the constant, try the second
3137 CFP = dyn_cast<ConstantFPSDNode>(N2);
3144 return SDValue(CFP,0);
3146 if (CFP->isExactlyValue(1.0))
3151 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3152 assert(N1.getValueType() == N2.getValueType() &&
3153 N1.getValueType() == VT && "Binary operator types must match!");
3155 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3156 assert(N1.getValueType() == VT &&
3157 N1.getValueType().isFloatingPoint() &&
3158 N2.getValueType().isFloatingPoint() &&
3159 "Invalid FCOPYSIGN!");
3166 assert(VT == N1.getValueType() &&
3167 "Shift operators return type must be the same as their first arg");
3168 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3169 "Shifts only work on integers");
3170 assert((!VT.isVector() || VT == N2.getValueType()) &&
3171 "Vector shift amounts must be in the same as their first arg");
3172 // Verify that the shift amount VT is bit enough to hold valid shift
3173 // amounts. This catches things like trying to shift an i1024 value by an
3174 // i8, which is easy to fall into in generic code that uses
3175 // TLI.getShiftAmount().
3176 assert(N2.getValueType().getSizeInBits() >=
3177 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3178 "Invalid use of small shift amount with oversized value!");
3180 // Always fold shifts of i1 values so the code generator doesn't need to
3181 // handle them. Since we know the size of the shift has to be less than the
3182 // size of the value, the shift/rotate count is guaranteed to be zero.
3185 if (N2C && N2C->isNullValue())
3188 case ISD::FP_ROUND_INREG: {
3189 EVT EVT = cast<VTSDNode>(N2)->getVT();
3190 assert(VT == N1.getValueType() && "Not an inreg round!");
3191 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3192 "Cannot FP_ROUND_INREG integer types");
3193 assert(EVT.isVector() == VT.isVector() &&
3194 "FP_ROUND_INREG type should be vector iff the operand "
3196 assert((!EVT.isVector() ||
3197 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3198 "Vector element counts must match in FP_ROUND_INREG");
3199 assert(EVT.bitsLE(VT) && "Not rounding down!");
3201 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3205 assert(VT.isFloatingPoint() &&
3206 N1.getValueType().isFloatingPoint() &&
3207 VT.bitsLE(N1.getValueType()) &&
3208 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3209 if (N1.getValueType() == VT) return N1; // noop conversion.
3211 case ISD::AssertSext:
3212 case ISD::AssertZext: {
3213 EVT EVT = cast<VTSDNode>(N2)->getVT();
3214 assert(VT == N1.getValueType() && "Not an inreg extend!");
3215 assert(VT.isInteger() && EVT.isInteger() &&
3216 "Cannot *_EXTEND_INREG FP types");
3217 assert(!EVT.isVector() &&
3218 "AssertSExt/AssertZExt type should be the vector element type "
3219 "rather than the vector type!");
3220 assert(EVT.bitsLE(VT) && "Not extending!");
3221 if (VT == EVT) return N1; // noop assertion.
3224 case ISD::SIGN_EXTEND_INREG: {
3225 EVT EVT = cast<VTSDNode>(N2)->getVT();
3226 assert(VT == N1.getValueType() && "Not an inreg extend!");
3227 assert(VT.isInteger() && EVT.isInteger() &&
3228 "Cannot *_EXTEND_INREG FP types");
3229 assert(EVT.isVector() == VT.isVector() &&
3230 "SIGN_EXTEND_INREG type should be vector iff the operand "
3232 assert((!EVT.isVector() ||
3233 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3234 "Vector element counts must match in SIGN_EXTEND_INREG");
3235 assert(EVT.bitsLE(VT) && "Not extending!");
3236 if (EVT == VT) return N1; // Not actually extending
3239 APInt Val = N1C->getAPIntValue();
3240 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3241 Val <<= Val.getBitWidth()-FromBits;
3242 Val = Val.ashr(Val.getBitWidth()-FromBits);
3243 return getConstant(Val, VT);
3247 case ISD::EXTRACT_VECTOR_ELT:
3248 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3249 if (N1.getOpcode() == ISD::UNDEF)
3250 return getUNDEF(VT);
3252 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3253 // expanding copies of large vectors from registers.
3255 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3256 N1.getNumOperands() > 0) {
3258 N1.getOperand(0).getValueType().getVectorNumElements();
3259 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3260 N1.getOperand(N2C->getZExtValue() / Factor),
3261 getConstant(N2C->getZExtValue() % Factor,
3262 N2.getValueType()));
3265 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3266 // expanding large vector constants.
3267 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3268 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3270 if (VT != Elt.getValueType())
3271 // If the vector element type is not legal, the BUILD_VECTOR operands
3272 // are promoted and implicitly truncated, and the result implicitly
3273 // extended. Make that explicit here.
3274 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3279 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3280 // operations are lowered to scalars.
3281 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3282 // If the indices are the same, return the inserted element else
3283 // if the indices are known different, extract the element from
3284 // the original vector.
3285 SDValue N1Op2 = N1.getOperand(2);
3286 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3288 if (N1Op2C && N2C) {
3289 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3290 if (VT == N1.getOperand(1).getValueType())
3291 return N1.getOperand(1);
3293 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3296 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3300 case ISD::EXTRACT_ELEMENT:
3301 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3302 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3303 (N1.getValueType().isInteger() == VT.isInteger()) &&
3304 N1.getValueType() != VT &&
3305 "Wrong types for EXTRACT_ELEMENT!");
3307 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3308 // 64-bit integers into 32-bit parts. Instead of building the extract of
3309 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3310 if (N1.getOpcode() == ISD::BUILD_PAIR)
3311 return N1.getOperand(N2C->getZExtValue());
3313 // EXTRACT_ELEMENT of a constant int is also very common.
3314 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3315 unsigned ElementSize = VT.getSizeInBits();
3316 unsigned Shift = ElementSize * N2C->getZExtValue();
3317 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3318 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3321 case ISD::EXTRACT_SUBVECTOR: {
3323 if (VT.isSimple() && N1.getValueType().isSimple()) {
3324 assert(VT.isVector() && N1.getValueType().isVector() &&
3325 "Extract subvector VTs must be a vectors!");
3326 assert(VT.getVectorElementType() ==
3327 N1.getValueType().getVectorElementType() &&
3328 "Extract subvector VTs must have the same element type!");
3329 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3330 "Extract subvector must be from larger vector to smaller vector!");
3332 if (isa<ConstantSDNode>(Index.getNode())) {
3333 assert((VT.getVectorNumElements() +
3334 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3335 <= N1.getValueType().getVectorNumElements())
3336 && "Extract subvector overflow!");
3339 // Trivial extraction.
3340 if (VT.getSimpleVT() == N1.getSimpleValueType())
3347 // Perform trivial constant folding.
3348 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3349 if (SV.getNode()) return SV;
3351 // Canonicalize constant to RHS if commutative.
3352 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3353 std::swap(N1C, N2C);
3357 // Constant fold FP operations.
3358 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3359 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3361 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3362 // Canonicalize constant to RHS if commutative.
3363 std::swap(N1CFP, N2CFP);
3366 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3367 APFloat::opStatus s;
3370 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3371 if (s != APFloat::opInvalidOp)
3372 return getConstantFP(V1, VT);
3375 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3376 if (s!=APFloat::opInvalidOp)
3377 return getConstantFP(V1, VT);
3380 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3381 if (s!=APFloat::opInvalidOp)
3382 return getConstantFP(V1, VT);
3385 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3386 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3387 return getConstantFP(V1, VT);
3390 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3391 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3392 return getConstantFP(V1, VT);
3394 case ISD::FCOPYSIGN:
3396 return getConstantFP(V1, VT);
3401 if (Opcode == ISD::FP_ROUND) {
3402 APFloat V = N1CFP->getValueAPF(); // make copy
3404 // This can return overflow, underflow, or inexact; we don't care.
3405 // FIXME need to be more flexible about rounding mode.
3406 (void)V.convert(EVTToAPFloatSemantics(VT),
3407 APFloat::rmNearestTiesToEven, &ignored);
3408 return getConstantFP(V, VT);
3412 // Canonicalize an UNDEF to the RHS, even over a constant.
3413 if (N1.getOpcode() == ISD::UNDEF) {
3414 if (isCommutativeBinOp(Opcode)) {
3418 case ISD::FP_ROUND_INREG:
3419 case ISD::SIGN_EXTEND_INREG:
3425 return N1; // fold op(undef, arg2) -> undef
3433 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3434 // For vectors, we can't easily build an all zero vector, just return
3441 // Fold a bunch of operators when the RHS is undef.
3442 if (N2.getOpcode() == ISD::UNDEF) {
3445 if (N1.getOpcode() == ISD::UNDEF)
3446 // Handle undef ^ undef -> 0 special case. This is a common
3448 return getConstant(0, VT);
3458 return N2; // fold op(arg1, undef) -> undef
3464 if (getTarget().Options.UnsafeFPMath)
3472 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3473 // For vectors, we can't easily build an all zero vector, just return
3478 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3479 // For vectors, we can't easily build an all one vector, just return
3487 // Memoize this node if possible.
3489 SDVTList VTs = getVTList(VT);
3490 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3491 if (VT != MVT::Glue) {
3492 SDValue Ops[] = {N1, N2};
3493 FoldingSetNodeID ID;
3494 AddNodeIDNode(ID, Opcode, VTs, Ops);
3496 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3498 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3499 return SDValue(E, 0);
3501 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3503 CSEMap.InsertNode(N, IP);
3506 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3509 AllNodes.push_back(N);
3513 return SDValue(N, 0);
3516 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3517 SDValue N1, SDValue N2, SDValue N3) {
3518 // Perform various simplifications.
3519 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3522 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3523 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3524 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3525 if (N1CFP && N2CFP && N3CFP) {
3526 APFloat V1 = N1CFP->getValueAPF();
3527 const APFloat &V2 = N2CFP->getValueAPF();
3528 const APFloat &V3 = N3CFP->getValueAPF();
3529 APFloat::opStatus s =
3530 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3531 if (s != APFloat::opInvalidOp)
3532 return getConstantFP(V1, VT);
3536 case ISD::CONCAT_VECTORS:
3537 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3538 // one big BUILD_VECTOR.
3539 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3540 N2.getOpcode() == ISD::BUILD_VECTOR &&
3541 N3.getOpcode() == ISD::BUILD_VECTOR) {
3542 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3543 N1.getNode()->op_end());
3544 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3545 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3546 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3550 // Use FoldSetCC to simplify SETCC's.
3551 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3552 if (Simp.getNode()) return Simp;
3557 if (N1C->getZExtValue())
3558 return N2; // select true, X, Y -> X
3559 return N3; // select false, X, Y -> Y
3562 if (N2 == N3) return N2; // select C, X, X -> X
3564 case ISD::VECTOR_SHUFFLE:
3565 llvm_unreachable("should use getVectorShuffle constructor!");
3566 case ISD::INSERT_SUBVECTOR: {
3568 if (VT.isSimple() && N1.getValueType().isSimple()
3569 && N2.getValueType().isSimple()) {
3570 assert(VT.isVector() && N1.getValueType().isVector() &&
3571 N2.getValueType().isVector() &&
3572 "Insert subvector VTs must be a vectors");
3573 assert(VT == N1.getValueType() &&
3574 "Dest and insert subvector source types must match!");
3575 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3576 "Insert subvector must be from smaller vector to larger vector!");
3577 if (isa<ConstantSDNode>(Index.getNode())) {
3578 assert((N2.getValueType().getVectorNumElements() +
3579 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3580 <= VT.getVectorNumElements())
3581 && "Insert subvector overflow!");
3584 // Trivial insertion.
3585 if (VT.getSimpleVT() == N2.getSimpleValueType())
3591 // Fold bit_convert nodes from a type to themselves.
3592 if (N1.getValueType() == VT)
3597 // Memoize node if it doesn't produce a flag.
3599 SDVTList VTs = getVTList(VT);
3600 if (VT != MVT::Glue) {
3601 SDValue Ops[] = { N1, N2, N3 };
3602 FoldingSetNodeID ID;
3603 AddNodeIDNode(ID, Opcode, VTs, Ops);
3605 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3606 return SDValue(E, 0);
3608 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3609 DL.getDebugLoc(), VTs, N1, N2, N3);
3610 CSEMap.InsertNode(N, IP);
3612 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3613 DL.getDebugLoc(), VTs, N1, N2, N3);
3616 AllNodes.push_back(N);
3620 return SDValue(N, 0);
3623 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3624 SDValue N1, SDValue N2, SDValue N3,
3626 SDValue Ops[] = { N1, N2, N3, N4 };
3627 return getNode(Opcode, DL, VT, Ops);
3630 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3631 SDValue N1, SDValue N2, SDValue N3,
3632 SDValue N4, SDValue N5) {
3633 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3634 return getNode(Opcode, DL, VT, Ops);
3637 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3638 /// the incoming stack arguments to be loaded from the stack.
3639 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3640 SmallVector<SDValue, 8> ArgChains;
3642 // Include the original chain at the beginning of the list. When this is
3643 // used by target LowerCall hooks, this helps legalize find the
3644 // CALLSEQ_BEGIN node.
3645 ArgChains.push_back(Chain);
3647 // Add a chain value for each stack argument.
3648 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3649 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3650 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3651 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3652 if (FI->getIndex() < 0)
3653 ArgChains.push_back(SDValue(L, 1));
3655 // Build a tokenfactor for all the chains.
3656 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3659 /// getMemsetValue - Vectorized representation of the memset value
3661 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3663 assert(Value.getOpcode() != ISD::UNDEF);
3665 unsigned NumBits = VT.getScalarType().getSizeInBits();
3666 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3667 assert(C->getAPIntValue().getBitWidth() == 8);
3668 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3670 return DAG.getConstant(Val, VT);
3671 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3674 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3676 // Use a multiplication with 0x010101... to extend the input to the
3678 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3679 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3685 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3686 /// used when a memcpy is turned into a memset when the source is a constant
3688 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3689 const TargetLowering &TLI, StringRef Str) {
3690 // Handle vector with all elements zero.
3693 return DAG.getConstant(0, VT);
3694 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3695 return DAG.getConstantFP(0.0, VT);
3696 else if (VT.isVector()) {
3697 unsigned NumElts = VT.getVectorNumElements();
3698 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3699 return DAG.getNode(ISD::BITCAST, dl, VT,
3700 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3703 llvm_unreachable("Expected type!");
3706 assert(!VT.isVector() && "Can't handle vector type here!");
3707 unsigned NumVTBits = VT.getSizeInBits();
3708 unsigned NumVTBytes = NumVTBits / 8;
3709 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3711 APInt Val(NumVTBits, 0);
3712 if (TLI.isLittleEndian()) {
3713 for (unsigned i = 0; i != NumBytes; ++i)
3714 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3716 for (unsigned i = 0; i != NumBytes; ++i)
3717 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3720 // If the "cost" of materializing the integer immediate is less than the cost
3721 // of a load, then it is cost effective to turn the load into the immediate.
3722 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3723 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3724 return DAG.getConstant(Val, VT);
3725 return SDValue(nullptr, 0);
3728 /// getMemBasePlusOffset - Returns base and offset node for the
3730 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3731 SelectionDAG &DAG) {
3732 EVT VT = Base.getValueType();
3733 return DAG.getNode(ISD::ADD, dl,
3734 VT, Base, DAG.getConstant(Offset, VT));
3737 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3739 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3740 unsigned SrcDelta = 0;
3741 GlobalAddressSDNode *G = nullptr;
3742 if (Src.getOpcode() == ISD::GlobalAddress)
3743 G = cast<GlobalAddressSDNode>(Src);
3744 else if (Src.getOpcode() == ISD::ADD &&
3745 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3746 Src.getOperand(1).getOpcode() == ISD::Constant) {
3747 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3748 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3753 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3756 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3757 /// to replace the memset / memcpy. Return true if the number of memory ops
3758 /// is below the threshold. It returns the types of the sequence of
3759 /// memory ops to perform memset / memcpy by reference.
3760 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3761 unsigned Limit, uint64_t Size,
3762 unsigned DstAlign, unsigned SrcAlign,
3768 const TargetLowering &TLI) {
3769 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3770 "Expecting memcpy / memset source to meet alignment requirement!");
3771 // If 'SrcAlign' is zero, that means the memory operation does not need to
3772 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3773 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3774 // is the specified alignment of the memory operation. If it is zero, that
3775 // means it's possible to change the alignment of the destination.
3776 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3777 // not need to be loaded.
3778 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3779 IsMemset, ZeroMemset, MemcpyStrSrc,
3780 DAG.getMachineFunction());
3782 if (VT == MVT::Other) {
3784 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3785 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3786 VT = TLI.getPointerTy();
3788 switch (DstAlign & 7) {
3789 case 0: VT = MVT::i64; break;
3790 case 4: VT = MVT::i32; break;
3791 case 2: VT = MVT::i16; break;
3792 default: VT = MVT::i8; break;
3797 while (!TLI.isTypeLegal(LVT))
3798 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3799 assert(LVT.isInteger());
3805 unsigned NumMemOps = 0;
3807 unsigned VTSize = VT.getSizeInBits() / 8;
3808 while (VTSize > Size) {
3809 // For now, only use non-vector load / store's for the left-over pieces.
3814 if (VT.isVector() || VT.isFloatingPoint()) {
3815 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3816 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3817 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3819 else if (NewVT == MVT::i64 &&
3820 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3821 TLI.isSafeMemOpType(MVT::f64)) {
3822 // i64 is usually not legal on 32-bit targets, but f64 may be.
3830 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3831 if (NewVT == MVT::i8)
3833 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3835 NewVTSize = NewVT.getSizeInBits() / 8;
3837 // If the new VT cannot cover all of the remaining bits, then consider
3838 // issuing a (or a pair of) unaligned and overlapping load / store.
3839 // FIXME: Only does this for 64-bit or more since we don't have proper
3840 // cost model for unaligned load / store.
3843 if (NumMemOps && AllowOverlap &&
3844 VTSize >= 8 && NewVTSize < Size &&
3845 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3853 if (++NumMemOps > Limit)
3856 MemOps.push_back(VT);
3863 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3864 SDValue Chain, SDValue Dst,
3865 SDValue Src, uint64_t Size,
3866 unsigned Align, bool isVol,
3868 MachinePointerInfo DstPtrInfo,
3869 MachinePointerInfo SrcPtrInfo) {
3870 // Turn a memcpy of undef to nop.
3871 if (Src.getOpcode() == ISD::UNDEF)
3874 // Expand memcpy to a series of load and store ops if the size operand falls
3875 // below a certain threshold.
3876 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3877 // rather than maybe a humongous number of loads and stores.
3878 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3879 std::vector<EVT> MemOps;
3880 bool DstAlignCanChange = false;
3881 MachineFunction &MF = DAG.getMachineFunction();
3882 MachineFrameInfo *MFI = MF.getFrameInfo();
3884 MF.getFunction()->getAttributes().
3885 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3886 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3887 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3888 DstAlignCanChange = true;
3889 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3890 if (Align > SrcAlign)
3893 bool CopyFromStr = isMemSrcFromString(Src, Str);
3894 bool isZeroStr = CopyFromStr && Str.empty();
3895 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3897 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3898 (DstAlignCanChange ? 0 : Align),
3899 (isZeroStr ? 0 : SrcAlign),
3900 false, false, CopyFromStr, true, DAG, TLI))
3903 if (DstAlignCanChange) {
3904 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3905 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3907 // Don't promote to an alignment that would require dynamic stack
3909 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3910 if (!TRI->needsStackRealignment(MF))
3911 while (NewAlign > Align &&
3912 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3915 if (NewAlign > Align) {
3916 // Give the stack frame object a larger alignment if needed.
3917 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3918 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3923 SmallVector<SDValue, 8> OutChains;
3924 unsigned NumMemOps = MemOps.size();
3925 uint64_t SrcOff = 0, DstOff = 0;
3926 for (unsigned i = 0; i != NumMemOps; ++i) {
3928 unsigned VTSize = VT.getSizeInBits() / 8;
3929 SDValue Value, Store;
3931 if (VTSize > Size) {
3932 // Issuing an unaligned load / store pair that overlaps with the previous
3933 // pair. Adjust the offset accordingly.
3934 assert(i == NumMemOps-1 && i != 0);
3935 SrcOff -= VTSize - Size;
3936 DstOff -= VTSize - Size;
3940 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3941 // It's unlikely a store of a vector immediate can be done in a single
3942 // instruction. It would require a load from a constantpool first.
3943 // We only handle zero vectors here.
3944 // FIXME: Handle other cases where store of vector immediate is done in
3945 // a single instruction.
3946 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3947 if (Value.getNode())
3948 Store = DAG.getStore(Chain, dl, Value,
3949 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3950 DstPtrInfo.getWithOffset(DstOff), isVol,
3954 if (!Store.getNode()) {
3955 // The type might not be legal for the target. This should only happen
3956 // if the type is smaller than a legal type, as on PPC, so the right
3957 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3958 // to Load/Store if NVT==VT.
3959 // FIXME does the case above also need this?
3960 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3961 assert(NVT.bitsGE(VT));
3962 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3963 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3964 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3965 MinAlign(SrcAlign, SrcOff));
3966 Store = DAG.getTruncStore(Chain, dl, Value,
3967 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3968 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3971 OutChains.push_back(Store);
3977 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3980 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3981 SDValue Chain, SDValue Dst,
3982 SDValue Src, uint64_t Size,
3983 unsigned Align, bool isVol,
3985 MachinePointerInfo DstPtrInfo,
3986 MachinePointerInfo SrcPtrInfo) {
3987 // Turn a memmove of undef to nop.
3988 if (Src.getOpcode() == ISD::UNDEF)
3991 // Expand memmove to a series of load and store ops if the size operand falls
3992 // below a certain threshold.
3993 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3994 std::vector<EVT> MemOps;
3995 bool DstAlignCanChange = false;
3996 MachineFunction &MF = DAG.getMachineFunction();
3997 MachineFrameInfo *MFI = MF.getFrameInfo();
3998 bool OptSize = MF.getFunction()->getAttributes().
3999 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4000 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4001 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4002 DstAlignCanChange = true;
4003 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4004 if (Align > SrcAlign)
4006 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4008 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4009 (DstAlignCanChange ? 0 : Align), SrcAlign,
4010 false, false, false, false, DAG, TLI))
4013 if (DstAlignCanChange) {
4014 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4015 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4016 if (NewAlign > Align) {
4017 // Give the stack frame object a larger alignment if needed.
4018 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4019 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4024 uint64_t SrcOff = 0, DstOff = 0;
4025 SmallVector<SDValue, 8> LoadValues;
4026 SmallVector<SDValue, 8> LoadChains;
4027 SmallVector<SDValue, 8> OutChains;
4028 unsigned NumMemOps = MemOps.size();
4029 for (unsigned i = 0; i < NumMemOps; i++) {
4031 unsigned VTSize = VT.getSizeInBits() / 8;
4034 Value = DAG.getLoad(VT, dl, Chain,
4035 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4036 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4037 false, false, SrcAlign);
4038 LoadValues.push_back(Value);
4039 LoadChains.push_back(Value.getValue(1));
4042 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4044 for (unsigned i = 0; i < NumMemOps; i++) {
4046 unsigned VTSize = VT.getSizeInBits() / 8;
4049 Store = DAG.getStore(Chain, dl, LoadValues[i],
4050 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4051 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4052 OutChains.push_back(Store);
4056 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4059 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4062 /// \param DAG Selection DAG where lowered code is placed.
4063 /// \param dl Link to corresponding IR location.
4064 /// \param Chain Control flow dependency.
4065 /// \param Dst Pointer to destination memory location.
4066 /// \param Src Value of byte to write into the memory.
4067 /// \param Size Number of bytes to write.
4068 /// \param Align Alignment of the destination in bytes.
4069 /// \param isVol True if destination is volatile.
4070 /// \param DstPtrInfo IR information on the memory pointer.
4071 /// \returns New head in the control flow, if lowering was successful, empty
4072 /// SDValue otherwise.
4074 /// The function tries to replace 'llvm.memset' intrinsic with several store
4075 /// operations and value calculation code. This is usually profitable for small
4077 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4078 SDValue Chain, SDValue Dst,
4079 SDValue Src, uint64_t Size,
4080 unsigned Align, bool isVol,
4081 MachinePointerInfo DstPtrInfo) {
4082 // Turn a memset of undef to nop.
4083 if (Src.getOpcode() == ISD::UNDEF)
4086 // Expand memset to a series of load/store ops if the size operand
4087 // falls below a certain threshold.
4088 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4089 std::vector<EVT> MemOps;
4090 bool DstAlignCanChange = false;
4091 MachineFunction &MF = DAG.getMachineFunction();
4092 MachineFrameInfo *MFI = MF.getFrameInfo();
4093 bool OptSize = MF.getFunction()->getAttributes().
4094 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4095 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4096 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4097 DstAlignCanChange = true;
4099 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4100 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4101 Size, (DstAlignCanChange ? 0 : Align), 0,
4102 true, IsZeroVal, false, true, DAG, TLI))
4105 if (DstAlignCanChange) {
4106 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4107 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4108 if (NewAlign > Align) {
4109 // Give the stack frame object a larger alignment if needed.
4110 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4111 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4116 SmallVector<SDValue, 8> OutChains;
4117 uint64_t DstOff = 0;
4118 unsigned NumMemOps = MemOps.size();
4120 // Find the largest store and generate the bit pattern for it.
4121 EVT LargestVT = MemOps[0];
4122 for (unsigned i = 1; i < NumMemOps; i++)
4123 if (MemOps[i].bitsGT(LargestVT))
4124 LargestVT = MemOps[i];
4125 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4127 for (unsigned i = 0; i < NumMemOps; i++) {
4129 unsigned VTSize = VT.getSizeInBits() / 8;
4130 if (VTSize > Size) {
4131 // Issuing an unaligned load / store pair that overlaps with the previous
4132 // pair. Adjust the offset accordingly.
4133 assert(i == NumMemOps-1 && i != 0);
4134 DstOff -= VTSize - Size;
4137 // If this store is smaller than the largest store see whether we can get
4138 // the smaller value for free with a truncate.
4139 SDValue Value = MemSetValue;
4140 if (VT.bitsLT(LargestVT)) {
4141 if (!LargestVT.isVector() && !VT.isVector() &&
4142 TLI.isTruncateFree(LargestVT, VT))
4143 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4145 Value = getMemsetValue(Src, VT, DAG, dl);
4147 assert(Value.getValueType() == VT && "Value with wrong type.");
4148 SDValue Store = DAG.getStore(Chain, dl, Value,
4149 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4150 DstPtrInfo.getWithOffset(DstOff),
4151 isVol, false, Align);
4152 OutChains.push_back(Store);
4153 DstOff += VT.getSizeInBits() / 8;
4157 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4160 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4161 SDValue Src, SDValue Size,
4162 unsigned Align, bool isVol, bool AlwaysInline,
4163 MachinePointerInfo DstPtrInfo,
4164 MachinePointerInfo SrcPtrInfo) {
4165 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4167 // Check to see if we should lower the memcpy to loads and stores first.
4168 // For cases within the target-specified limits, this is the best choice.
4169 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4171 // Memcpy with size zero? Just return the original chain.
4172 if (ConstantSize->isNullValue())
4175 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4176 ConstantSize->getZExtValue(),Align,
4177 isVol, false, DstPtrInfo, SrcPtrInfo);
4178 if (Result.getNode())
4182 // Then check to see if we should lower the memcpy with target-specific
4183 // code. If the target chooses to do this, this is the next best.
4185 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4186 isVol, AlwaysInline,
4187 DstPtrInfo, SrcPtrInfo);
4188 if (Result.getNode())
4191 // If we really need inline code and the target declined to provide it,
4192 // use a (potentially long) sequence of loads and stores.
4194 assert(ConstantSize && "AlwaysInline requires a constant size!");
4195 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4196 ConstantSize->getZExtValue(), Align, isVol,
4197 true, DstPtrInfo, SrcPtrInfo);
4200 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4201 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4202 // respect volatile, so they may do things like read or write memory
4203 // beyond the given memory regions. But fixing this isn't easy, and most
4204 // people don't care.
4206 const TargetLowering *TLI = TM.getTargetLowering();
4208 // Emit a library call.
4209 TargetLowering::ArgListTy Args;
4210 TargetLowering::ArgListEntry Entry;
4211 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4212 Entry.Node = Dst; Args.push_back(Entry);
4213 Entry.Node = Src; Args.push_back(Entry);
4214 Entry.Node = Size; Args.push_back(Entry);
4215 // FIXME: pass in SDLoc
4216 TargetLowering::CallLoweringInfo CLI(*this);
4217 CLI.setDebugLoc(dl).setChain(Chain)
4218 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4219 Type::getVoidTy(*getContext()),
4220 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4221 TLI->getPointerTy()), std::move(Args), 0)
4222 .setDiscardResult();
4223 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4225 return CallResult.second;
4228 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4229 SDValue Src, SDValue Size,
4230 unsigned Align, bool isVol,
4231 MachinePointerInfo DstPtrInfo,
4232 MachinePointerInfo SrcPtrInfo) {
4233 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4235 // Check to see if we should lower the memmove to loads and stores first.
4236 // For cases within the target-specified limits, this is the best choice.
4237 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4239 // Memmove with size zero? Just return the original chain.
4240 if (ConstantSize->isNullValue())
4244 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4245 ConstantSize->getZExtValue(), Align, isVol,
4246 false, DstPtrInfo, SrcPtrInfo);
4247 if (Result.getNode())
4251 // Then check to see if we should lower the memmove with target-specific
4252 // code. If the target chooses to do this, this is the next best.
4254 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4255 DstPtrInfo, SrcPtrInfo);
4256 if (Result.getNode())
4259 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4260 // not be safe. See memcpy above for more details.
4262 const TargetLowering *TLI = TM.getTargetLowering();
4264 // Emit a library call.
4265 TargetLowering::ArgListTy Args;
4266 TargetLowering::ArgListEntry Entry;
4267 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4268 Entry.Node = Dst; Args.push_back(Entry);
4269 Entry.Node = Src; Args.push_back(Entry);
4270 Entry.Node = Size; Args.push_back(Entry);
4271 // FIXME: pass in SDLoc
4272 TargetLowering::CallLoweringInfo CLI(*this);
4273 CLI.setDebugLoc(dl).setChain(Chain)
4274 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4275 Type::getVoidTy(*getContext()),
4276 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4277 TLI->getPointerTy()), std::move(Args), 0)
4278 .setDiscardResult();
4279 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4281 return CallResult.second;
4284 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4285 SDValue Src, SDValue Size,
4286 unsigned Align, bool isVol,
4287 MachinePointerInfo DstPtrInfo) {
4288 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4290 // Check to see if we should lower the memset to stores first.
4291 // For cases within the target-specified limits, this is the best choice.
4292 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4294 // Memset with size zero? Just return the original chain.
4295 if (ConstantSize->isNullValue())
4299 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4300 Align, isVol, DstPtrInfo);
4302 if (Result.getNode())
4306 // Then check to see if we should lower the memset with target-specific
4307 // code. If the target chooses to do this, this is the next best.
4309 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4311 if (Result.getNode())
4314 // Emit a library call.
4315 const TargetLowering *TLI = TM.getTargetLowering();
4316 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4317 TargetLowering::ArgListTy Args;
4318 TargetLowering::ArgListEntry Entry;
4319 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4320 Args.push_back(Entry);
4321 // Extend or truncate the argument to be an i32 value for the call.
4322 if (Src.getValueType().bitsGT(MVT::i32))
4323 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4325 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4327 Entry.Ty = Type::getInt32Ty(*getContext());
4328 Entry.isSExt = true;
4329 Args.push_back(Entry);
4331 Entry.Ty = IntPtrTy;
4332 Entry.isSExt = false;
4333 Args.push_back(Entry);
4335 // FIXME: pass in SDLoc
4336 TargetLowering::CallLoweringInfo CLI(*this);
4337 CLI.setDebugLoc(dl).setChain(Chain)
4338 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4339 Type::getVoidTy(*getContext()),
4340 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4341 TLI->getPointerTy()), std::move(Args), 0)
4342 .setDiscardResult();
4344 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4345 return CallResult.second;
4348 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4349 SDVTList VTList, ArrayRef<SDValue> Ops,
4350 MachineMemOperand *MMO,
4351 AtomicOrdering SuccessOrdering,
4352 AtomicOrdering FailureOrdering,
4353 SynchronizationScope SynchScope) {
4354 FoldingSetNodeID ID;
4355 ID.AddInteger(MemVT.getRawBits());
4356 AddNodeIDNode(ID, Opcode, VTList, Ops);
4357 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4359 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4360 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4361 return SDValue(E, 0);
4364 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4365 // SDNode doesn't have access to it. This memory will be "leaked" when
4366 // the node is deallocated, but recovered when the allocator is released.
4367 // If the number of operands is less than 5 we use AtomicSDNode's internal
4369 unsigned NumOps = Ops.size();
4370 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4373 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4374 dl.getDebugLoc(), VTList, MemVT,
4375 Ops.data(), DynOps, NumOps, MMO,
4376 SuccessOrdering, FailureOrdering,
4378 CSEMap.InsertNode(N, IP);
4379 AllNodes.push_back(N);
4380 return SDValue(N, 0);
4383 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4384 SDVTList VTList, ArrayRef<SDValue> Ops,
4385 MachineMemOperand *MMO,
4386 AtomicOrdering Ordering,
4387 SynchronizationScope SynchScope) {
4388 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4389 Ordering, SynchScope);
4392 SDValue SelectionDAG::getAtomicCmpSwap(
4393 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4394 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4395 unsigned Alignment, AtomicOrdering SuccessOrdering,
4396 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4397 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4398 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4399 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4401 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4402 Alignment = getEVTAlignment(MemVT);
4404 MachineFunction &MF = getMachineFunction();
4406 // FIXME: Volatile isn't really correct; we should keep track of atomic
4407 // orderings in the memoperand.
4408 unsigned Flags = MachineMemOperand::MOVolatile;
4409 Flags |= MachineMemOperand::MOLoad;
4410 Flags |= MachineMemOperand::MOStore;
4412 MachineMemOperand *MMO =
4413 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4415 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4416 SuccessOrdering, FailureOrdering, SynchScope);
4419 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4420 SDVTList VTs, SDValue Chain, SDValue Ptr,
4421 SDValue Cmp, SDValue Swp,
4422 MachineMemOperand *MMO,
4423 AtomicOrdering SuccessOrdering,
4424 AtomicOrdering FailureOrdering,
4425 SynchronizationScope SynchScope) {
4426 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4427 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4428 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4430 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4431 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4432 SuccessOrdering, FailureOrdering, SynchScope);
4435 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4437 SDValue Ptr, SDValue Val,
4438 const Value* PtrVal,
4440 AtomicOrdering Ordering,
4441 SynchronizationScope SynchScope) {
4442 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4443 Alignment = getEVTAlignment(MemVT);
4445 MachineFunction &MF = getMachineFunction();
4446 // An atomic store does not load. An atomic load does not store.
4447 // (An atomicrmw obviously both loads and stores.)
4448 // For now, atomics are considered to be volatile always, and they are
4450 // FIXME: Volatile isn't really correct; we should keep track of atomic
4451 // orderings in the memoperand.
4452 unsigned Flags = MachineMemOperand::MOVolatile;
4453 if (Opcode != ISD::ATOMIC_STORE)
4454 Flags |= MachineMemOperand::MOLoad;
4455 if (Opcode != ISD::ATOMIC_LOAD)
4456 Flags |= MachineMemOperand::MOStore;
4458 MachineMemOperand *MMO =
4459 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4460 MemVT.getStoreSize(), Alignment);
4462 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4463 Ordering, SynchScope);
4466 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4468 SDValue Ptr, SDValue Val,
4469 MachineMemOperand *MMO,
4470 AtomicOrdering Ordering,
4471 SynchronizationScope SynchScope) {
4472 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4473 Opcode == ISD::ATOMIC_LOAD_SUB ||
4474 Opcode == ISD::ATOMIC_LOAD_AND ||
4475 Opcode == ISD::ATOMIC_LOAD_OR ||
4476 Opcode == ISD::ATOMIC_LOAD_XOR ||
4477 Opcode == ISD::ATOMIC_LOAD_NAND ||
4478 Opcode == ISD::ATOMIC_LOAD_MIN ||
4479 Opcode == ISD::ATOMIC_LOAD_MAX ||
4480 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4481 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4482 Opcode == ISD::ATOMIC_SWAP ||
4483 Opcode == ISD::ATOMIC_STORE) &&
4484 "Invalid Atomic Op");
4486 EVT VT = Val.getValueType();
4488 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4489 getVTList(VT, MVT::Other);
4490 SDValue Ops[] = {Chain, Ptr, Val};
4491 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4494 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4495 EVT VT, SDValue Chain,
4497 MachineMemOperand *MMO,
4498 AtomicOrdering Ordering,
4499 SynchronizationScope SynchScope) {
4500 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4502 SDVTList VTs = getVTList(VT, MVT::Other);
4503 SDValue Ops[] = {Chain, Ptr};
4504 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4507 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4508 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4509 if (Ops.size() == 1)
4512 SmallVector<EVT, 4> VTs;
4513 VTs.reserve(Ops.size());
4514 for (unsigned i = 0; i < Ops.size(); ++i)
4515 VTs.push_back(Ops[i].getValueType());
4516 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4520 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4521 ArrayRef<SDValue> Ops,
4522 EVT MemVT, MachinePointerInfo PtrInfo,
4523 unsigned Align, bool Vol,
4524 bool ReadMem, bool WriteMem) {
4525 if (Align == 0) // Ensure that codegen never sees alignment 0
4526 Align = getEVTAlignment(MemVT);
4528 MachineFunction &MF = getMachineFunction();
4531 Flags |= MachineMemOperand::MOStore;
4533 Flags |= MachineMemOperand::MOLoad;
4535 Flags |= MachineMemOperand::MOVolatile;
4536 MachineMemOperand *MMO =
4537 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4539 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4543 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4544 ArrayRef<SDValue> Ops, EVT MemVT,
4545 MachineMemOperand *MMO) {
4546 assert((Opcode == ISD::INTRINSIC_VOID ||
4547 Opcode == ISD::INTRINSIC_W_CHAIN ||
4548 Opcode == ISD::PREFETCH ||
4549 Opcode == ISD::LIFETIME_START ||
4550 Opcode == ISD::LIFETIME_END ||
4551 (Opcode <= INT_MAX &&
4552 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4553 "Opcode is not a memory-accessing opcode!");
4555 // Memoize the node unless it returns a flag.
4556 MemIntrinsicSDNode *N;
4557 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4558 FoldingSetNodeID ID;
4559 AddNodeIDNode(ID, Opcode, VTList, Ops);
4560 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4562 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4563 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4564 return SDValue(E, 0);
4567 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4568 dl.getDebugLoc(), VTList, Ops,
4570 CSEMap.InsertNode(N, IP);
4572 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4573 dl.getDebugLoc(), VTList, Ops,
4576 AllNodes.push_back(N);
4577 return SDValue(N, 0);
4580 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4581 /// MachinePointerInfo record from it. This is particularly useful because the
4582 /// code generator has many cases where it doesn't bother passing in a
4583 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4584 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4585 // If this is FI+Offset, we can model it.
4586 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4587 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4589 // If this is (FI+Offset1)+Offset2, we can model it.
4590 if (Ptr.getOpcode() != ISD::ADD ||
4591 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4592 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4593 return MachinePointerInfo();
4595 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4596 return MachinePointerInfo::getFixedStack(FI, Offset+
4597 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4600 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4601 /// MachinePointerInfo record from it. This is particularly useful because the
4602 /// code generator has many cases where it doesn't bother passing in a
4603 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4604 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4605 // If the 'Offset' value isn't a constant, we can't handle this.
4606 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4607 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4608 if (OffsetOp.getOpcode() == ISD::UNDEF)
4609 return InferPointerInfo(Ptr);
4610 return MachinePointerInfo();
4615 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4616 EVT VT, SDLoc dl, SDValue Chain,
4617 SDValue Ptr, SDValue Offset,
4618 MachinePointerInfo PtrInfo, EVT MemVT,
4619 bool isVolatile, bool isNonTemporal, bool isInvariant,
4620 unsigned Alignment, const MDNode *TBAAInfo,
4621 const MDNode *Ranges) {
4622 assert(Chain.getValueType() == MVT::Other &&
4623 "Invalid chain type");
4624 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4625 Alignment = getEVTAlignment(VT);
4627 unsigned Flags = MachineMemOperand::MOLoad;
4629 Flags |= MachineMemOperand::MOVolatile;
4631 Flags |= MachineMemOperand::MONonTemporal;
4633 Flags |= MachineMemOperand::MOInvariant;
4635 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4637 if (PtrInfo.V.isNull())
4638 PtrInfo = InferPointerInfo(Ptr, Offset);
4640 MachineFunction &MF = getMachineFunction();
4641 MachineMemOperand *MMO =
4642 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4644 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4648 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4649 EVT VT, SDLoc dl, SDValue Chain,
4650 SDValue Ptr, SDValue Offset, EVT MemVT,
4651 MachineMemOperand *MMO) {
4653 ExtType = ISD::NON_EXTLOAD;
4654 } else if (ExtType == ISD::NON_EXTLOAD) {
4655 assert(VT == MemVT && "Non-extending load from different memory type!");
4658 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4659 "Should only be an extending load, not truncating!");
4660 assert(VT.isInteger() == MemVT.isInteger() &&
4661 "Cannot convert from FP to Int or Int -> FP!");
4662 assert(VT.isVector() == MemVT.isVector() &&
4663 "Cannot use trunc store to convert to or from a vector!");
4664 assert((!VT.isVector() ||
4665 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4666 "Cannot use trunc store to change the number of vector elements!");
4669 bool Indexed = AM != ISD::UNINDEXED;
4670 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4671 "Unindexed load with an offset!");
4673 SDVTList VTs = Indexed ?
4674 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4675 SDValue Ops[] = { Chain, Ptr, Offset };
4676 FoldingSetNodeID ID;
4677 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4678 ID.AddInteger(MemVT.getRawBits());
4679 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4680 MMO->isNonTemporal(),
4681 MMO->isInvariant()));
4682 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4684 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4685 cast<LoadSDNode>(E)->refineAlignment(MMO);
4686 return SDValue(E, 0);
4688 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4689 dl.getDebugLoc(), VTs, AM, ExtType,
4691 CSEMap.InsertNode(N, IP);
4692 AllNodes.push_back(N);
4693 return SDValue(N, 0);
4696 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4697 SDValue Chain, SDValue Ptr,
4698 MachinePointerInfo PtrInfo,
4699 bool isVolatile, bool isNonTemporal,
4700 bool isInvariant, unsigned Alignment,
4701 const MDNode *TBAAInfo,
4702 const MDNode *Ranges) {
4703 SDValue Undef = getUNDEF(Ptr.getValueType());
4704 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4705 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4709 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4710 SDValue Chain, SDValue Ptr,
4711 MachineMemOperand *MMO) {
4712 SDValue Undef = getUNDEF(Ptr.getValueType());
4713 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4717 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4718 SDValue Chain, SDValue Ptr,
4719 MachinePointerInfo PtrInfo, EVT MemVT,
4720 bool isVolatile, bool isNonTemporal,
4721 unsigned Alignment, const MDNode *TBAAInfo) {
4722 SDValue Undef = getUNDEF(Ptr.getValueType());
4723 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4724 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4729 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4730 SDValue Chain, SDValue Ptr, EVT MemVT,
4731 MachineMemOperand *MMO) {
4732 SDValue Undef = getUNDEF(Ptr.getValueType());
4733 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4738 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4739 SDValue Offset, ISD::MemIndexedMode AM) {
4740 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4741 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4742 "Load is already a indexed load!");
4743 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4744 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4745 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4746 false, LD->getAlignment());
4749 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4750 SDValue Ptr, MachinePointerInfo PtrInfo,
4751 bool isVolatile, bool isNonTemporal,
4752 unsigned Alignment, const MDNode *TBAAInfo) {
4753 assert(Chain.getValueType() == MVT::Other &&
4754 "Invalid chain type");
4755 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4756 Alignment = getEVTAlignment(Val.getValueType());
4758 unsigned Flags = MachineMemOperand::MOStore;
4760 Flags |= MachineMemOperand::MOVolatile;
4762 Flags |= MachineMemOperand::MONonTemporal;
4764 if (PtrInfo.V.isNull())
4765 PtrInfo = InferPointerInfo(Ptr);
4767 MachineFunction &MF = getMachineFunction();
4768 MachineMemOperand *MMO =
4769 MF.getMachineMemOperand(PtrInfo, Flags,
4770 Val.getValueType().getStoreSize(), Alignment,
4773 return getStore(Chain, dl, Val, Ptr, MMO);
4776 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4777 SDValue Ptr, MachineMemOperand *MMO) {
4778 assert(Chain.getValueType() == MVT::Other &&
4779 "Invalid chain type");
4780 EVT VT = Val.getValueType();
4781 SDVTList VTs = getVTList(MVT::Other);
4782 SDValue Undef = getUNDEF(Ptr.getValueType());
4783 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4784 FoldingSetNodeID ID;
4785 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4786 ID.AddInteger(VT.getRawBits());
4787 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4788 MMO->isNonTemporal(), MMO->isInvariant()));
4789 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4791 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4792 cast<StoreSDNode>(E)->refineAlignment(MMO);
4793 return SDValue(E, 0);
4795 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4796 dl.getDebugLoc(), VTs,
4797 ISD::UNINDEXED, false, VT, MMO);
4798 CSEMap.InsertNode(N, IP);
4799 AllNodes.push_back(N);
4800 return SDValue(N, 0);
4803 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4804 SDValue Ptr, MachinePointerInfo PtrInfo,
4805 EVT SVT,bool isVolatile, bool isNonTemporal,
4807 const MDNode *TBAAInfo) {
4808 assert(Chain.getValueType() == MVT::Other &&
4809 "Invalid chain type");
4810 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4811 Alignment = getEVTAlignment(SVT);
4813 unsigned Flags = MachineMemOperand::MOStore;
4815 Flags |= MachineMemOperand::MOVolatile;
4817 Flags |= MachineMemOperand::MONonTemporal;
4819 if (PtrInfo.V.isNull())
4820 PtrInfo = InferPointerInfo(Ptr);
4822 MachineFunction &MF = getMachineFunction();
4823 MachineMemOperand *MMO =
4824 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4827 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4830 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4831 SDValue Ptr, EVT SVT,
4832 MachineMemOperand *MMO) {
4833 EVT VT = Val.getValueType();
4835 assert(Chain.getValueType() == MVT::Other &&
4836 "Invalid chain type");
4838 return getStore(Chain, dl, Val, Ptr, MMO);
4840 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4841 "Should only be a truncating store, not extending!");
4842 assert(VT.isInteger() == SVT.isInteger() &&
4843 "Can't do FP-INT conversion!");
4844 assert(VT.isVector() == SVT.isVector() &&
4845 "Cannot use trunc store to convert to or from a vector!");
4846 assert((!VT.isVector() ||
4847 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4848 "Cannot use trunc store to change the number of vector elements!");
4850 SDVTList VTs = getVTList(MVT::Other);
4851 SDValue Undef = getUNDEF(Ptr.getValueType());
4852 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4853 FoldingSetNodeID ID;
4854 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4855 ID.AddInteger(SVT.getRawBits());
4856 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4857 MMO->isNonTemporal(), MMO->isInvariant()));
4858 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4860 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4861 cast<StoreSDNode>(E)->refineAlignment(MMO);
4862 return SDValue(E, 0);
4864 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4865 dl.getDebugLoc(), VTs,
4866 ISD::UNINDEXED, true, SVT, MMO);
4867 CSEMap.InsertNode(N, IP);
4868 AllNodes.push_back(N);
4869 return SDValue(N, 0);
4873 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4874 SDValue Offset, ISD::MemIndexedMode AM) {
4875 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4876 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4877 "Store is already a indexed store!");
4878 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4879 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4880 FoldingSetNodeID ID;
4881 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4882 ID.AddInteger(ST->getMemoryVT().getRawBits());
4883 ID.AddInteger(ST->getRawSubclassData());
4884 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4886 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4887 return SDValue(E, 0);
4889 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4890 dl.getDebugLoc(), VTs, AM,
4891 ST->isTruncatingStore(),
4893 ST->getMemOperand());
4894 CSEMap.InsertNode(N, IP);
4895 AllNodes.push_back(N);
4896 return SDValue(N, 0);
4899 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4900 SDValue Chain, SDValue Ptr,
4903 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4904 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4907 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4908 ArrayRef<SDUse> Ops) {
4909 switch (Ops.size()) {
4910 case 0: return getNode(Opcode, DL, VT);
4911 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4912 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4913 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4917 // Copy from an SDUse array into an SDValue array for use with
4918 // the regular getNode logic.
4919 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4920 return getNode(Opcode, DL, VT, NewOps);
4923 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4924 ArrayRef<SDValue> Ops) {
4925 unsigned NumOps = Ops.size();
4927 case 0: return getNode(Opcode, DL, VT);
4928 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4929 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4930 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4936 case ISD::SELECT_CC: {
4937 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4938 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4939 "LHS and RHS of condition must have same type!");
4940 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4941 "True and False arms of SelectCC must have same type!");
4942 assert(Ops[2].getValueType() == VT &&
4943 "select_cc node must be of same type as true and false value!");
4947 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4948 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4949 "LHS/RHS of comparison should match types!");
4956 SDVTList VTs = getVTList(VT);
4958 if (VT != MVT::Glue) {
4959 FoldingSetNodeID ID;
4960 AddNodeIDNode(ID, Opcode, VTs, Ops);
4963 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4964 return SDValue(E, 0);
4966 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4968 CSEMap.InsertNode(N, IP);
4970 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4974 AllNodes.push_back(N);
4978 return SDValue(N, 0);
4981 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4982 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4983 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4986 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4987 ArrayRef<SDValue> Ops) {
4988 if (VTList.NumVTs == 1)
4989 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4993 // FIXME: figure out how to safely handle things like
4994 // int foo(int x) { return 1 << (x & 255); }
4995 // int bar() { return foo(256); }
4996 case ISD::SRA_PARTS:
4997 case ISD::SRL_PARTS:
4998 case ISD::SHL_PARTS:
4999 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5000 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5001 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5002 else if (N3.getOpcode() == ISD::AND)
5003 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5004 // If the and is only masking out bits that cannot effect the shift,
5005 // eliminate the and.
5006 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5007 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5008 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5014 // Memoize the node unless it returns a flag.
5016 unsigned NumOps = Ops.size();
5017 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5018 FoldingSetNodeID ID;
5019 AddNodeIDNode(ID, Opcode, VTList, Ops);
5021 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5022 return SDValue(E, 0);
5025 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5026 DL.getDebugLoc(), VTList, Ops[0]);
5027 } else if (NumOps == 2) {
5028 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5029 DL.getDebugLoc(), VTList, Ops[0],
5031 } else if (NumOps == 3) {
5032 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5033 DL.getDebugLoc(), VTList, Ops[0],
5036 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5039 CSEMap.InsertNode(N, IP);
5042 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5043 DL.getDebugLoc(), VTList, Ops[0]);
5044 } else if (NumOps == 2) {
5045 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5046 DL.getDebugLoc(), VTList, Ops[0],
5048 } else if (NumOps == 3) {
5049 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5050 DL.getDebugLoc(), VTList, Ops[0],
5053 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5057 AllNodes.push_back(N);
5061 return SDValue(N, 0);
5064 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5065 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5068 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5070 SDValue Ops[] = { N1 };
5071 return getNode(Opcode, DL, VTList, Ops);
5074 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5075 SDValue N1, SDValue N2) {
5076 SDValue Ops[] = { N1, N2 };
5077 return getNode(Opcode, DL, VTList, Ops);
5080 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5081 SDValue N1, SDValue N2, SDValue N3) {
5082 SDValue Ops[] = { N1, N2, N3 };
5083 return getNode(Opcode, DL, VTList, Ops);
5086 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5087 SDValue N1, SDValue N2, SDValue N3,
5089 SDValue Ops[] = { N1, N2, N3, N4 };
5090 return getNode(Opcode, DL, VTList, Ops);
5093 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5094 SDValue N1, SDValue N2, SDValue N3,
5095 SDValue N4, SDValue N5) {
5096 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5097 return getNode(Opcode, DL, VTList, Ops);
5100 SDVTList SelectionDAG::getVTList(EVT VT) {
5101 return makeVTList(SDNode::getValueTypeList(VT), 1);
5104 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5105 FoldingSetNodeID ID;
5107 ID.AddInteger(VT1.getRawBits());
5108 ID.AddInteger(VT2.getRawBits());
5111 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5113 EVT *Array = Allocator.Allocate<EVT>(2);
5116 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5117 VTListMap.InsertNode(Result, IP);
5119 return Result->getSDVTList();
5122 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5123 FoldingSetNodeID ID;
5125 ID.AddInteger(VT1.getRawBits());
5126 ID.AddInteger(VT2.getRawBits());
5127 ID.AddInteger(VT3.getRawBits());
5130 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5132 EVT *Array = Allocator.Allocate<EVT>(3);
5136 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5137 VTListMap.InsertNode(Result, IP);
5139 return Result->getSDVTList();
5142 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5143 FoldingSetNodeID ID;
5145 ID.AddInteger(VT1.getRawBits());
5146 ID.AddInteger(VT2.getRawBits());
5147 ID.AddInteger(VT3.getRawBits());
5148 ID.AddInteger(VT4.getRawBits());
5151 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5153 EVT *Array = Allocator.Allocate<EVT>(4);
5158 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5159 VTListMap.InsertNode(Result, IP);
5161 return Result->getSDVTList();
5164 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5165 unsigned NumVTs = VTs.size();
5166 FoldingSetNodeID ID;
5167 ID.AddInteger(NumVTs);
5168 for (unsigned index = 0; index < NumVTs; index++) {
5169 ID.AddInteger(VTs[index].getRawBits());
5173 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5175 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5176 std::copy(VTs.begin(), VTs.end(), Array);
5177 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5178 VTListMap.InsertNode(Result, IP);
5180 return Result->getSDVTList();
5184 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5185 /// specified operands. If the resultant node already exists in the DAG,
5186 /// this does not modify the specified node, instead it returns the node that
5187 /// already exists. If the resultant node does not exist in the DAG, the
5188 /// input node is returned. As a degenerate case, if you specify the same
5189 /// input operands as the node already has, the input node is returned.
5190 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5191 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5193 // Check to see if there is no change.
5194 if (Op == N->getOperand(0)) return N;
5196 // See if the modified node already exists.
5197 void *InsertPos = nullptr;
5198 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5201 // Nope it doesn't. Remove the node from its current place in the maps.
5203 if (!RemoveNodeFromCSEMaps(N))
5204 InsertPos = nullptr;
5206 // Now we update the operands.
5207 N->OperandList[0].set(Op);
5209 // If this gets put into a CSE map, add it.
5210 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5214 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5215 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5217 // Check to see if there is no change.
5218 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5219 return N; // No operands changed, just return the input node.
5221 // See if the modified node already exists.
5222 void *InsertPos = nullptr;
5223 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5226 // Nope it doesn't. Remove the node from its current place in the maps.
5228 if (!RemoveNodeFromCSEMaps(N))
5229 InsertPos = nullptr;
5231 // Now we update the operands.
5232 if (N->OperandList[0] != Op1)
5233 N->OperandList[0].set(Op1);
5234 if (N->OperandList[1] != Op2)
5235 N->OperandList[1].set(Op2);
5237 // If this gets put into a CSE map, add it.
5238 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5242 SDNode *SelectionDAG::
5243 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5244 SDValue Ops[] = { Op1, Op2, Op3 };
5245 return UpdateNodeOperands(N, Ops);
5248 SDNode *SelectionDAG::
5249 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5250 SDValue Op3, SDValue Op4) {
5251 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5252 return UpdateNodeOperands(N, Ops);
5255 SDNode *SelectionDAG::
5256 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5257 SDValue Op3, SDValue Op4, SDValue Op5) {
5258 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5259 return UpdateNodeOperands(N, Ops);
5262 SDNode *SelectionDAG::
5263 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5264 unsigned NumOps = Ops.size();
5265 assert(N->getNumOperands() == NumOps &&
5266 "Update with wrong number of operands");
5268 // Check to see if there is no change.
5269 bool AnyChange = false;
5270 for (unsigned i = 0; i != NumOps; ++i) {
5271 if (Ops[i] != N->getOperand(i)) {
5277 // No operands changed, just return the input node.
5278 if (!AnyChange) return N;
5280 // See if the modified node already exists.
5281 void *InsertPos = nullptr;
5282 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5285 // Nope it doesn't. Remove the node from its current place in the maps.
5287 if (!RemoveNodeFromCSEMaps(N))
5288 InsertPos = nullptr;
5290 // Now we update the operands.
5291 for (unsigned i = 0; i != NumOps; ++i)
5292 if (N->OperandList[i] != Ops[i])
5293 N->OperandList[i].set(Ops[i]);
5295 // If this gets put into a CSE map, add it.
5296 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5300 /// DropOperands - Release the operands and set this node to have
5302 void SDNode::DropOperands() {
5303 // Unlike the code in MorphNodeTo that does this, we don't need to
5304 // watch for dead nodes here.
5305 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5311 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5314 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5316 SDVTList VTs = getVTList(VT);
5317 return SelectNodeTo(N, MachineOpc, VTs, None);
5320 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5321 EVT VT, SDValue Op1) {
5322 SDVTList VTs = getVTList(VT);
5323 SDValue Ops[] = { Op1 };
5324 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5327 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5328 EVT VT, SDValue Op1,
5330 SDVTList VTs = getVTList(VT);
5331 SDValue Ops[] = { Op1, Op2 };
5332 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5335 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5336 EVT VT, SDValue Op1,
5337 SDValue Op2, SDValue Op3) {
5338 SDVTList VTs = getVTList(VT);
5339 SDValue Ops[] = { Op1, Op2, Op3 };
5340 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5343 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5344 EVT VT, ArrayRef<SDValue> Ops) {
5345 SDVTList VTs = getVTList(VT);
5346 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5349 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5350 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5351 SDVTList VTs = getVTList(VT1, VT2);
5352 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5355 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5357 SDVTList VTs = getVTList(VT1, VT2);
5358 return SelectNodeTo(N, MachineOpc, VTs, None);
5361 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5362 EVT VT1, EVT VT2, EVT VT3,
5363 ArrayRef<SDValue> Ops) {
5364 SDVTList VTs = getVTList(VT1, VT2, VT3);
5365 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5368 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5369 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5370 ArrayRef<SDValue> Ops) {
5371 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5372 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5375 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5378 SDVTList VTs = getVTList(VT1, VT2);
5379 SDValue Ops[] = { Op1 };
5380 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5383 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5385 SDValue Op1, SDValue Op2) {
5386 SDVTList VTs = getVTList(VT1, VT2);
5387 SDValue Ops[] = { Op1, Op2 };
5388 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5391 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5393 SDValue Op1, SDValue Op2,
5395 SDVTList VTs = getVTList(VT1, VT2);
5396 SDValue Ops[] = { Op1, Op2, Op3 };
5397 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5400 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5401 EVT VT1, EVT VT2, EVT VT3,
5402 SDValue Op1, SDValue Op2,
5404 SDVTList VTs = getVTList(VT1, VT2, VT3);
5405 SDValue Ops[] = { Op1, Op2, Op3 };
5406 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5409 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5410 SDVTList VTs,ArrayRef<SDValue> Ops) {
5411 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5412 // Reset the NodeID to -1.
5417 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5418 /// the line number information on the merged node since it is not possible to
5419 /// preserve the information that operation is associated with multiple lines.
5420 /// This will make the debugger working better at -O0, were there is a higher
5421 /// probability having other instructions associated with that line.
5423 /// For IROrder, we keep the smaller of the two
5424 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5425 DebugLoc NLoc = N->getDebugLoc();
5426 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5427 (OLoc.getDebugLoc() != NLoc)) {
5428 N->setDebugLoc(DebugLoc());
5430 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5431 N->setIROrder(Order);
5435 /// MorphNodeTo - This *mutates* the specified node to have the specified
5436 /// return type, opcode, and operands.
5438 /// Note that MorphNodeTo returns the resultant node. If there is already a
5439 /// node of the specified opcode and operands, it returns that node instead of
5440 /// the current one. Note that the SDLoc need not be the same.
5442 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5443 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5444 /// node, and because it doesn't require CSE recalculation for any of
5445 /// the node's users.
5447 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5448 SDVTList VTs, ArrayRef<SDValue> Ops) {
5449 unsigned NumOps = Ops.size();
5450 // If an identical node already exists, use it.
5452 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5453 FoldingSetNodeID ID;
5454 AddNodeIDNode(ID, Opc, VTs, Ops);
5455 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5456 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5459 if (!RemoveNodeFromCSEMaps(N))
5462 // Start the morphing.
5464 N->ValueList = VTs.VTs;
5465 N->NumValues = VTs.NumVTs;
5467 // Clear the operands list, updating used nodes to remove this from their
5468 // use list. Keep track of any operands that become dead as a result.
5469 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5470 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5472 SDNode *Used = Use.getNode();
5474 if (Used->use_empty())
5475 DeadNodeSet.insert(Used);
5478 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5479 // Initialize the memory references information.
5480 MN->setMemRefs(nullptr, nullptr);
5481 // If NumOps is larger than the # of operands we can have in a
5482 // MachineSDNode, reallocate the operand list.
5483 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5484 if (MN->OperandsNeedDelete)
5485 delete[] MN->OperandList;
5486 if (NumOps > array_lengthof(MN->LocalOperands))
5487 // We're creating a final node that will live unmorphed for the
5488 // remainder of the current SelectionDAG iteration, so we can allocate
5489 // the operands directly out of a pool with no recycling metadata.
5490 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5491 Ops.data(), NumOps);
5493 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5494 MN->OperandsNeedDelete = false;
5496 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5498 // If NumOps is larger than the # of operands we currently have, reallocate
5499 // the operand list.
5500 if (NumOps > N->NumOperands) {
5501 if (N->OperandsNeedDelete)
5502 delete[] N->OperandList;
5503 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5504 N->OperandsNeedDelete = true;
5506 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5509 // Delete any nodes that are still dead after adding the uses for the
5511 if (!DeadNodeSet.empty()) {
5512 SmallVector<SDNode *, 16> DeadNodes;
5513 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5514 E = DeadNodeSet.end(); I != E; ++I)
5515 if ((*I)->use_empty())
5516 DeadNodes.push_back(*I);
5517 RemoveDeadNodes(DeadNodes);
5521 CSEMap.InsertNode(N, IP); // Memoize the new node.
5526 /// getMachineNode - These are used for target selectors to create a new node
5527 /// with specified return type(s), MachineInstr opcode, and operands.
5529 /// Note that getMachineNode returns the resultant node. If there is already a
5530 /// node of the specified opcode and operands, it returns that node instead of
5531 /// the current one.
5533 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5534 SDVTList VTs = getVTList(VT);
5535 return getMachineNode(Opcode, dl, VTs, None);
5539 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5540 SDVTList VTs = getVTList(VT);
5541 SDValue Ops[] = { Op1 };
5542 return getMachineNode(Opcode, dl, VTs, Ops);
5546 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5547 SDValue Op1, SDValue Op2) {
5548 SDVTList VTs = getVTList(VT);
5549 SDValue Ops[] = { Op1, Op2 };
5550 return getMachineNode(Opcode, dl, VTs, Ops);
5554 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5555 SDValue Op1, SDValue Op2, SDValue Op3) {
5556 SDVTList VTs = getVTList(VT);
5557 SDValue Ops[] = { Op1, Op2, Op3 };
5558 return getMachineNode(Opcode, dl, VTs, Ops);
5562 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5563 ArrayRef<SDValue> Ops) {
5564 SDVTList VTs = getVTList(VT);
5565 return getMachineNode(Opcode, dl, VTs, Ops);
5569 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5570 SDVTList VTs = getVTList(VT1, VT2);
5571 return getMachineNode(Opcode, dl, VTs, None);
5575 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5576 EVT VT1, EVT VT2, SDValue Op1) {
5577 SDVTList VTs = getVTList(VT1, VT2);
5578 SDValue Ops[] = { Op1 };
5579 return getMachineNode(Opcode, dl, VTs, Ops);
5583 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5584 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5585 SDVTList VTs = getVTList(VT1, VT2);
5586 SDValue Ops[] = { Op1, Op2 };
5587 return getMachineNode(Opcode, dl, VTs, Ops);
5591 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5592 EVT VT1, EVT VT2, SDValue Op1,
5593 SDValue Op2, SDValue Op3) {
5594 SDVTList VTs = getVTList(VT1, VT2);
5595 SDValue Ops[] = { Op1, Op2, Op3 };
5596 return getMachineNode(Opcode, dl, VTs, Ops);
5600 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5602 ArrayRef<SDValue> Ops) {
5603 SDVTList VTs = getVTList(VT1, VT2);
5604 return getMachineNode(Opcode, dl, VTs, Ops);
5608 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5609 EVT VT1, EVT VT2, EVT VT3,
5610 SDValue Op1, SDValue Op2) {
5611 SDVTList VTs = getVTList(VT1, VT2, VT3);
5612 SDValue Ops[] = { Op1, Op2 };
5613 return getMachineNode(Opcode, dl, VTs, Ops);
5617 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5618 EVT VT1, EVT VT2, EVT VT3,
5619 SDValue Op1, SDValue Op2, SDValue Op3) {
5620 SDVTList VTs = getVTList(VT1, VT2, VT3);
5621 SDValue Ops[] = { Op1, Op2, Op3 };
5622 return getMachineNode(Opcode, dl, VTs, Ops);
5626 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5627 EVT VT1, EVT VT2, EVT VT3,
5628 ArrayRef<SDValue> Ops) {
5629 SDVTList VTs = getVTList(VT1, VT2, VT3);
5630 return getMachineNode(Opcode, dl, VTs, Ops);
5634 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5635 EVT VT2, EVT VT3, EVT VT4,
5636 ArrayRef<SDValue> Ops) {
5637 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5638 return getMachineNode(Opcode, dl, VTs, Ops);
5642 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5643 ArrayRef<EVT> ResultTys,
5644 ArrayRef<SDValue> Ops) {
5645 SDVTList VTs = getVTList(ResultTys);
5646 return getMachineNode(Opcode, dl, VTs, Ops);
5650 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5651 ArrayRef<SDValue> OpsArray) {
5652 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5655 const SDValue *Ops = OpsArray.data();
5656 unsigned NumOps = OpsArray.size();
5659 FoldingSetNodeID ID;
5660 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5662 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5663 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5667 // Allocate a new MachineSDNode.
5668 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5669 DL.getDebugLoc(), VTs);
5671 // Initialize the operands list.
5672 if (NumOps > array_lengthof(N->LocalOperands))
5673 // We're creating a final node that will live unmorphed for the
5674 // remainder of the current SelectionDAG iteration, so we can allocate
5675 // the operands directly out of a pool with no recycling metadata.
5676 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5679 N->InitOperands(N->LocalOperands, Ops, NumOps);
5680 N->OperandsNeedDelete = false;
5683 CSEMap.InsertNode(N, IP);
5685 AllNodes.push_back(N);
5687 VerifyMachineNode(N);
5692 /// getTargetExtractSubreg - A convenience function for creating
5693 /// TargetOpcode::EXTRACT_SUBREG nodes.
5695 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5697 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5698 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5699 VT, Operand, SRIdxVal);
5700 return SDValue(Subreg, 0);
5703 /// getTargetInsertSubreg - A convenience function for creating
5704 /// TargetOpcode::INSERT_SUBREG nodes.
5706 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5707 SDValue Operand, SDValue Subreg) {
5708 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5709 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5710 VT, Operand, Subreg, SRIdxVal);
5711 return SDValue(Result, 0);
5714 /// getNodeIfExists - Get the specified node if it's already available, or
5715 /// else return NULL.
5716 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5717 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5719 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5720 FoldingSetNodeID ID;
5721 AddNodeIDNode(ID, Opcode, VTList, Ops);
5722 if (isBinOpWithFlags(Opcode))
5723 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5725 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5731 /// getDbgValue - Creates a SDDbgValue node.
5735 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5736 bool IsIndirect, uint64_t Off,
5737 DebugLoc DL, unsigned O) {
5738 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5743 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5745 DebugLoc DL, unsigned O) {
5746 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5751 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5752 DebugLoc DL, unsigned O) {
5753 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5758 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5759 /// pointed to by a use iterator is deleted, increment the use iterator
5760 /// so that it doesn't dangle.
5762 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5763 SDNode::use_iterator &UI;
5764 SDNode::use_iterator &UE;
5766 void NodeDeleted(SDNode *N, SDNode *E) override {
5767 // Increment the iterator as needed.
5768 while (UI != UE && N == *UI)
5773 RAUWUpdateListener(SelectionDAG &d,
5774 SDNode::use_iterator &ui,
5775 SDNode::use_iterator &ue)
5776 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5781 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5782 /// This can cause recursive merging of nodes in the DAG.
5784 /// This version assumes From has a single result value.
5786 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5787 SDNode *From = FromN.getNode();
5788 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5789 "Cannot replace with this method!");
5790 assert(From != To.getNode() && "Cannot replace uses of with self");
5792 // Iterate over all the existing uses of From. New uses will be added
5793 // to the beginning of the use list, which we avoid visiting.
5794 // This specifically avoids visiting uses of From that arise while the
5795 // replacement is happening, because any such uses would be the result
5796 // of CSE: If an existing node looks like From after one of its operands
5797 // is replaced by To, we don't want to replace of all its users with To
5798 // too. See PR3018 for more info.
5799 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5800 RAUWUpdateListener Listener(*this, UI, UE);
5804 // This node is about to morph, remove its old self from the CSE maps.
5805 RemoveNodeFromCSEMaps(User);
5807 // A user can appear in a use list multiple times, and when this
5808 // happens the uses are usually next to each other in the list.
5809 // To help reduce the number of CSE recomputations, process all
5810 // the uses of this user that we can find this way.
5812 SDUse &Use = UI.getUse();
5815 } while (UI != UE && *UI == User);
5817 // Now that we have modified User, add it back to the CSE maps. If it
5818 // already exists there, recursively merge the results together.
5819 AddModifiedNodeToCSEMaps(User);
5822 // If we just RAUW'd the root, take note.
5823 if (FromN == getRoot())
5827 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5828 /// This can cause recursive merging of nodes in the DAG.
5830 /// This version assumes that for each value of From, there is a
5831 /// corresponding value in To in the same position with the same type.
5833 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5835 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5836 assert((!From->hasAnyUseOfValue(i) ||
5837 From->getValueType(i) == To->getValueType(i)) &&
5838 "Cannot use this version of ReplaceAllUsesWith!");
5841 // Handle the trivial case.
5845 // Iterate over just the existing users of From. See the comments in
5846 // the ReplaceAllUsesWith above.
5847 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5848 RAUWUpdateListener Listener(*this, UI, UE);
5852 // This node is about to morph, remove its old self from the CSE maps.
5853 RemoveNodeFromCSEMaps(User);
5855 // A user can appear in a use list multiple times, and when this
5856 // happens the uses are usually next to each other in the list.
5857 // To help reduce the number of CSE recomputations, process all
5858 // the uses of this user that we can find this way.
5860 SDUse &Use = UI.getUse();
5863 } while (UI != UE && *UI == User);
5865 // Now that we have modified User, add it back to the CSE maps. If it
5866 // already exists there, recursively merge the results together.
5867 AddModifiedNodeToCSEMaps(User);
5870 // If we just RAUW'd the root, take note.
5871 if (From == getRoot().getNode())
5872 setRoot(SDValue(To, getRoot().getResNo()));
5875 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5876 /// This can cause recursive merging of nodes in the DAG.
5878 /// This version can replace From with any result values. To must match the
5879 /// number and types of values returned by From.
5880 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5881 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5882 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5884 // Iterate over just the existing users of From. See the comments in
5885 // the ReplaceAllUsesWith above.
5886 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5887 RAUWUpdateListener Listener(*this, UI, UE);
5891 // This node is about to morph, remove its old self from the CSE maps.
5892 RemoveNodeFromCSEMaps(User);
5894 // A user can appear in a use list multiple times, and when this
5895 // happens the uses are usually next to each other in the list.
5896 // To help reduce the number of CSE recomputations, process all
5897 // the uses of this user that we can find this way.
5899 SDUse &Use = UI.getUse();
5900 const SDValue &ToOp = To[Use.getResNo()];
5903 } while (UI != UE && *UI == User);
5905 // Now that we have modified User, add it back to the CSE maps. If it
5906 // already exists there, recursively merge the results together.
5907 AddModifiedNodeToCSEMaps(User);
5910 // If we just RAUW'd the root, take note.
5911 if (From == getRoot().getNode())
5912 setRoot(SDValue(To[getRoot().getResNo()]));
5915 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5916 /// uses of other values produced by From.getNode() alone. The Deleted
5917 /// vector is handled the same way as for ReplaceAllUsesWith.
5918 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5919 // Handle the really simple, really trivial case efficiently.
5920 if (From == To) return;
5922 // Handle the simple, trivial, case efficiently.
5923 if (From.getNode()->getNumValues() == 1) {
5924 ReplaceAllUsesWith(From, To);
5928 // Iterate over just the existing users of From. See the comments in
5929 // the ReplaceAllUsesWith above.
5930 SDNode::use_iterator UI = From.getNode()->use_begin(),
5931 UE = From.getNode()->use_end();
5932 RAUWUpdateListener Listener(*this, UI, UE);
5935 bool UserRemovedFromCSEMaps = false;
5937 // A user can appear in a use list multiple times, and when this
5938 // happens the uses are usually next to each other in the list.
5939 // To help reduce the number of CSE recomputations, process all
5940 // the uses of this user that we can find this way.
5942 SDUse &Use = UI.getUse();
5944 // Skip uses of different values from the same node.
5945 if (Use.getResNo() != From.getResNo()) {
5950 // If this node hasn't been modified yet, it's still in the CSE maps,
5951 // so remove its old self from the CSE maps.
5952 if (!UserRemovedFromCSEMaps) {
5953 RemoveNodeFromCSEMaps(User);
5954 UserRemovedFromCSEMaps = true;
5959 } while (UI != UE && *UI == User);
5961 // We are iterating over all uses of the From node, so if a use
5962 // doesn't use the specific value, no changes are made.
5963 if (!UserRemovedFromCSEMaps)
5966 // Now that we have modified User, add it back to the CSE maps. If it
5967 // already exists there, recursively merge the results together.
5968 AddModifiedNodeToCSEMaps(User);
5971 // If we just RAUW'd the root, take note.
5972 if (From == getRoot())
5977 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5978 /// to record information about a use.
5985 /// operator< - Sort Memos by User.
5986 bool operator<(const UseMemo &L, const UseMemo &R) {
5987 return (intptr_t)L.User < (intptr_t)R.User;
5991 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5992 /// uses of other values produced by From.getNode() alone. The same value
5993 /// may appear in both the From and To list. The Deleted vector is
5994 /// handled the same way as for ReplaceAllUsesWith.
5995 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5998 // Handle the simple, trivial case efficiently.
6000 return ReplaceAllUsesOfValueWith(*From, *To);
6002 // Read up all the uses and make records of them. This helps
6003 // processing new uses that are introduced during the
6004 // replacement process.
6005 SmallVector<UseMemo, 4> Uses;
6006 for (unsigned i = 0; i != Num; ++i) {
6007 unsigned FromResNo = From[i].getResNo();
6008 SDNode *FromNode = From[i].getNode();
6009 for (SDNode::use_iterator UI = FromNode->use_begin(),
6010 E = FromNode->use_end(); UI != E; ++UI) {
6011 SDUse &Use = UI.getUse();
6012 if (Use.getResNo() == FromResNo) {
6013 UseMemo Memo = { *UI, i, &Use };
6014 Uses.push_back(Memo);
6019 // Sort the uses, so that all the uses from a given User are together.
6020 std::sort(Uses.begin(), Uses.end());
6022 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6023 UseIndex != UseIndexEnd; ) {
6024 // We know that this user uses some value of From. If it is the right
6025 // value, update it.
6026 SDNode *User = Uses[UseIndex].User;
6028 // This node is about to morph, remove its old self from the CSE maps.
6029 RemoveNodeFromCSEMaps(User);
6031 // The Uses array is sorted, so all the uses for a given User
6032 // are next to each other in the list.
6033 // To help reduce the number of CSE recomputations, process all
6034 // the uses of this user that we can find this way.
6036 unsigned i = Uses[UseIndex].Index;
6037 SDUse &Use = *Uses[UseIndex].Use;
6041 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6043 // Now that we have modified User, add it back to the CSE maps. If it
6044 // already exists there, recursively merge the results together.
6045 AddModifiedNodeToCSEMaps(User);
6049 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6050 /// based on their topological order. It returns the maximum id and a vector
6051 /// of the SDNodes* in assigned order by reference.
6052 unsigned SelectionDAG::AssignTopologicalOrder() {
6054 unsigned DAGSize = 0;
6056 // SortedPos tracks the progress of the algorithm. Nodes before it are
6057 // sorted, nodes after it are unsorted. When the algorithm completes
6058 // it is at the end of the list.
6059 allnodes_iterator SortedPos = allnodes_begin();
6061 // Visit all the nodes. Move nodes with no operands to the front of
6062 // the list immediately. Annotate nodes that do have operands with their
6063 // operand count. Before we do this, the Node Id fields of the nodes
6064 // may contain arbitrary values. After, the Node Id fields for nodes
6065 // before SortedPos will contain the topological sort index, and the
6066 // Node Id fields for nodes At SortedPos and after will contain the
6067 // count of outstanding operands.
6068 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6070 checkForCycles(N, this);
6071 unsigned Degree = N->getNumOperands();
6073 // A node with no uses, add it to the result array immediately.
6074 N->setNodeId(DAGSize++);
6075 allnodes_iterator Q = N;
6077 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6078 assert(SortedPos != AllNodes.end() && "Overran node list");
6081 // Temporarily use the Node Id as scratch space for the degree count.
6082 N->setNodeId(Degree);
6086 // Visit all the nodes. As we iterate, move nodes into sorted order,
6087 // such that by the time the end is reached all nodes will be sorted.
6088 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6090 checkForCycles(N, this);
6091 // N is in sorted position, so all its uses have one less operand
6092 // that needs to be sorted.
6093 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6096 unsigned Degree = P->getNodeId();
6097 assert(Degree != 0 && "Invalid node degree");
6100 // All of P's operands are sorted, so P may sorted now.
6101 P->setNodeId(DAGSize++);
6103 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6104 assert(SortedPos != AllNodes.end() && "Overran node list");
6107 // Update P's outstanding operand count.
6108 P->setNodeId(Degree);
6111 if (I == SortedPos) {
6114 dbgs() << "Overran sorted position:\n";
6115 S->dumprFull(this); dbgs() << "\n";
6116 dbgs() << "Checking if this is due to cycles\n";
6117 checkForCycles(this, true);
6119 llvm_unreachable(nullptr);
6123 assert(SortedPos == AllNodes.end() &&
6124 "Topological sort incomplete!");
6125 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6126 "First node in topological sort is not the entry token!");
6127 assert(AllNodes.front().getNodeId() == 0 &&
6128 "First node in topological sort has non-zero id!");
6129 assert(AllNodes.front().getNumOperands() == 0 &&
6130 "First node in topological sort has operands!");
6131 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6132 "Last node in topologic sort has unexpected id!");
6133 assert(AllNodes.back().use_empty() &&
6134 "Last node in topologic sort has users!");
6135 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6139 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6140 /// value is produced by SD.
6141 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6142 DbgInfo->add(DB, SD, isParameter);
6144 SD->setHasDebugValue(true);
6147 /// TransferDbgValues - Transfer SDDbgValues.
6148 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6149 if (From == To || !From.getNode()->getHasDebugValue())
6151 SDNode *FromNode = From.getNode();
6152 SDNode *ToNode = To.getNode();
6153 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6154 SmallVector<SDDbgValue *, 2> ClonedDVs;
6155 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6157 SDDbgValue *Dbg = *I;
6158 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6159 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6161 Dbg->getOffset(), Dbg->getDebugLoc(),
6163 ClonedDVs.push_back(Clone);
6166 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6167 E = ClonedDVs.end(); I != E; ++I)
6168 AddDbgValue(*I, ToNode, false);
6171 //===----------------------------------------------------------------------===//
6173 //===----------------------------------------------------------------------===//
6175 HandleSDNode::~HandleSDNode() {
6179 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6180 DebugLoc DL, const GlobalValue *GA,
6181 EVT VT, int64_t o, unsigned char TF)
6182 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6186 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6187 SDValue X, unsigned SrcAS,
6189 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6190 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6192 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6193 EVT memvt, MachineMemOperand *mmo)
6194 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6195 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6196 MMO->isNonTemporal(), MMO->isInvariant());
6197 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6198 assert(isNonTemporal() == MMO->isNonTemporal() &&
6199 "Non-temporal encoding error!");
6200 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6203 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6204 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6205 : SDNode(Opc, Order, dl, VTs, Ops),
6206 MemoryVT(memvt), MMO(mmo) {
6207 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6208 MMO->isNonTemporal(), MMO->isInvariant());
6209 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6210 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6213 /// Profile - Gather unique data for the node.
6215 void SDNode::Profile(FoldingSetNodeID &ID) const {
6216 AddNodeIDNode(ID, this);
6221 std::vector<EVT> VTs;
6224 VTs.reserve(MVT::LAST_VALUETYPE);
6225 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6226 VTs.push_back(MVT((MVT::SimpleValueType)i));
6231 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6232 static ManagedStatic<EVTArray> SimpleVTArray;
6233 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6235 /// getValueTypeList - Return a pointer to the specified value type.
6237 const EVT *SDNode::getValueTypeList(EVT VT) {
6238 if (VT.isExtended()) {
6239 sys::SmartScopedLock<true> Lock(*VTMutex);
6240 return &(*EVTs->insert(VT).first);
6242 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6243 "Value type out of range!");
6244 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6248 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6249 /// indicated value. This method ignores uses of other values defined by this
6251 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6252 assert(Value < getNumValues() && "Bad value!");
6254 // TODO: Only iterate over uses of a given value of the node
6255 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6256 if (UI.getUse().getResNo() == Value) {
6263 // Found exactly the right number of uses?
6268 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6269 /// value. This method ignores uses of other values defined by this operation.
6270 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6271 assert(Value < getNumValues() && "Bad value!");
6273 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6274 if (UI.getUse().getResNo() == Value)
6281 /// isOnlyUserOf - Return true if this node is the only use of N.
6283 bool SDNode::isOnlyUserOf(SDNode *N) const {
6285 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6296 /// isOperand - Return true if this node is an operand of N.
6298 bool SDValue::isOperandOf(SDNode *N) const {
6299 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6300 if (*this == N->getOperand(i))
6305 bool SDNode::isOperandOf(SDNode *N) const {
6306 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6307 if (this == N->OperandList[i].getNode())
6312 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6313 /// be a chain) reaches the specified operand without crossing any
6314 /// side-effecting instructions on any chain path. In practice, this looks
6315 /// through token factors and non-volatile loads. In order to remain efficient,
6316 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6317 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6318 unsigned Depth) const {
6319 if (*this == Dest) return true;
6321 // Don't search too deeply, we just want to be able to see through
6322 // TokenFactor's etc.
6323 if (Depth == 0) return false;
6325 // If this is a token factor, all inputs to the TF happen in parallel. If any
6326 // of the operands of the TF does not reach dest, then we cannot do the xform.
6327 if (getOpcode() == ISD::TokenFactor) {
6328 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6329 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6334 // Loads don't have side effects, look through them.
6335 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6336 if (!Ld->isVolatile())
6337 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6342 /// hasPredecessor - Return true if N is a predecessor of this node.
6343 /// N is either an operand of this node, or can be reached by recursively
6344 /// traversing up the operands.
6345 /// NOTE: This is an expensive method. Use it carefully.
6346 bool SDNode::hasPredecessor(const SDNode *N) const {
6347 SmallPtrSet<const SDNode *, 32> Visited;
6348 SmallVector<const SDNode *, 16> Worklist;
6349 return hasPredecessorHelper(N, Visited, Worklist);
6353 SDNode::hasPredecessorHelper(const SDNode *N,
6354 SmallPtrSet<const SDNode *, 32> &Visited,
6355 SmallVectorImpl<const SDNode *> &Worklist) const {
6356 if (Visited.empty()) {
6357 Worklist.push_back(this);
6359 // Take a look in the visited set. If we've already encountered this node
6360 // we needn't search further.
6361 if (Visited.count(N))
6365 // Haven't visited N yet. Continue the search.
6366 while (!Worklist.empty()) {
6367 const SDNode *M = Worklist.pop_back_val();
6368 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6369 SDNode *Op = M->getOperand(i).getNode();
6370 if (Visited.insert(Op))
6371 Worklist.push_back(Op);
6380 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6381 assert(Num < NumOperands && "Invalid child # of SDNode!");
6382 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6385 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6386 assert(N->getNumValues() == 1 &&
6387 "Can't unroll a vector with multiple results!");
6389 EVT VT = N->getValueType(0);
6390 unsigned NE = VT.getVectorNumElements();
6391 EVT EltVT = VT.getVectorElementType();
6394 SmallVector<SDValue, 8> Scalars;
6395 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6397 // If ResNE is 0, fully unroll the vector op.
6400 else if (NE > ResNE)
6404 for (i= 0; i != NE; ++i) {
6405 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6406 SDValue Operand = N->getOperand(j);
6407 EVT OperandVT = Operand.getValueType();
6408 if (OperandVT.isVector()) {
6409 // A vector operand; extract a single element.
6410 const TargetLowering *TLI = TM.getTargetLowering();
6411 EVT OperandEltVT = OperandVT.getVectorElementType();
6412 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6415 getConstant(i, TLI->getVectorIdxTy()));
6417 // A scalar operand; just use it as is.
6418 Operands[j] = Operand;
6422 switch (N->getOpcode()) {
6424 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6427 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6434 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6435 getShiftAmountOperand(Operands[0].getValueType(),
6438 case ISD::SIGN_EXTEND_INREG:
6439 case ISD::FP_ROUND_INREG: {
6440 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6441 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6443 getValueType(ExtVT)));
6448 for (; i < ResNE; ++i)
6449 Scalars.push_back(getUNDEF(EltVT));
6451 return getNode(ISD::BUILD_VECTOR, dl,
6452 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6456 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6457 /// location that is 'Dist' units away from the location that the 'Base' load
6458 /// is loading from.
6459 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6460 unsigned Bytes, int Dist) const {
6461 if (LD->getChain() != Base->getChain())
6463 EVT VT = LD->getValueType(0);
6464 if (VT.getSizeInBits() / 8 != Bytes)
6467 SDValue Loc = LD->getOperand(1);
6468 SDValue BaseLoc = Base->getOperand(1);
6469 if (Loc.getOpcode() == ISD::FrameIndex) {
6470 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6472 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6473 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6474 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6475 int FS = MFI->getObjectSize(FI);
6476 int BFS = MFI->getObjectSize(BFI);
6477 if (FS != BFS || FS != (int)Bytes) return false;
6478 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6482 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6483 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6486 const GlobalValue *GV1 = nullptr;
6487 const GlobalValue *GV2 = nullptr;
6488 int64_t Offset1 = 0;
6489 int64_t Offset2 = 0;
6490 const TargetLowering *TLI = TM.getTargetLowering();
6491 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6492 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6493 if (isGA1 && isGA2 && GV1 == GV2)
6494 return Offset1 == (Offset2 + Dist*Bytes);
6499 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6500 /// it cannot be inferred.
6501 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6502 // If this is a GlobalAddress + cst, return the alignment.
6503 const GlobalValue *GV;
6504 int64_t GVOffset = 0;
6505 const TargetLowering *TLI = TM.getTargetLowering();
6506 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6507 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6508 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6509 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6510 TLI->getDataLayout());
6511 unsigned AlignBits = KnownZero.countTrailingOnes();
6512 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6514 return MinAlign(Align, GVOffset);
6517 // If this is a direct reference to a stack slot, use information about the
6518 // stack slot's alignment.
6519 int FrameIdx = 1 << 31;
6520 int64_t FrameOffset = 0;
6521 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6522 FrameIdx = FI->getIndex();
6523 } else if (isBaseWithConstantOffset(Ptr) &&
6524 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6526 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6527 FrameOffset = Ptr.getConstantOperandVal(1);
6530 if (FrameIdx != (1 << 31)) {
6531 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6532 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6540 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6541 /// which is split (or expanded) into two not necessarily identical pieces.
6542 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6543 // Currently all types are split in half.
6545 if (!VT.isVector()) {
6546 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6548 unsigned NumElements = VT.getVectorNumElements();
6549 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6550 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6553 return std::make_pair(LoVT, HiVT);
6556 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6558 std::pair<SDValue, SDValue>
6559 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6561 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6562 N.getValueType().getVectorNumElements() &&
6563 "More vector elements requested than available!");
6565 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6566 getConstant(0, TLI->getVectorIdxTy()));
6567 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6568 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6569 return std::make_pair(Lo, Hi);
6572 void SelectionDAG::ExtractVectorElements(SDValue Op,
6573 SmallVectorImpl<SDValue> &Args,
6574 unsigned Start, unsigned Count) {
6575 EVT VT = Op.getValueType();
6577 Count = VT.getVectorNumElements();
6579 EVT EltVT = VT.getVectorElementType();
6580 EVT IdxTy = TLI->getVectorIdxTy();
6582 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6583 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6584 Op, getConstant(i, IdxTy)));
6588 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6589 unsigned GlobalAddressSDNode::getAddressSpace() const {
6590 return getGlobal()->getType()->getAddressSpace();
6594 Type *ConstantPoolSDNode::getType() const {
6595 if (isMachineConstantPoolEntry())
6596 return Val.MachineCPVal->getType();
6597 return Val.ConstVal->getType();
6600 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6602 unsigned &SplatBitSize,
6604 unsigned MinSplatBits,
6605 bool isBigEndian) const {
6606 EVT VT = getValueType(0);
6607 assert(VT.isVector() && "Expected a vector type");
6608 unsigned sz = VT.getSizeInBits();
6609 if (MinSplatBits > sz)
6612 SplatValue = APInt(sz, 0);
6613 SplatUndef = APInt(sz, 0);
6615 // Get the bits. Bits with undefined values (when the corresponding element
6616 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6617 // in SplatValue. If any of the values are not constant, give up and return
6619 unsigned int nOps = getNumOperands();
6620 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6621 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6623 for (unsigned j = 0; j < nOps; ++j) {
6624 unsigned i = isBigEndian ? nOps-1-j : j;
6625 SDValue OpVal = getOperand(i);
6626 unsigned BitPos = j * EltBitSize;
6628 if (OpVal.getOpcode() == ISD::UNDEF)
6629 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6630 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6631 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6632 zextOrTrunc(sz) << BitPos;
6633 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6634 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6639 // The build_vector is all constants or undefs. Find the smallest element
6640 // size that splats the vector.
6642 HasAnyUndefs = (SplatUndef != 0);
6645 unsigned HalfSize = sz / 2;
6646 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6647 APInt LowValue = SplatValue.trunc(HalfSize);
6648 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6649 APInt LowUndef = SplatUndef.trunc(HalfSize);
6651 // If the two halves do not match (ignoring undef bits), stop here.
6652 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6653 MinSplatBits > HalfSize)
6656 SplatValue = HighValue | LowValue;
6657 SplatUndef = HighUndef & LowUndef;
6666 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6667 if (UndefElements) {
6668 UndefElements->clear();
6669 UndefElements->resize(getNumOperands());
6672 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6673 SDValue Op = getOperand(i);
6674 if (Op.getOpcode() == ISD::UNDEF) {
6676 (*UndefElements)[i] = true;
6677 } else if (!Splatted) {
6679 } else if (Splatted != Op) {
6685 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6686 "Can only have a splat without a constant for all undefs.");
6687 return getOperand(0);
6694 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6695 return dyn_cast_or_null<ConstantSDNode>(
6696 getSplatValue(UndefElements).getNode());
6700 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6701 return dyn_cast_or_null<ConstantFPSDNode>(
6702 getSplatValue(UndefElements).getNode());
6705 bool BuildVectorSDNode::isConstant() const {
6706 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6707 unsigned Opc = getOperand(i).getOpcode();
6708 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6714 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6715 // Find the first non-undef value in the shuffle mask.
6717 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6720 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6722 // Make sure all remaining elements are either undef or the same as the first
6724 for (int Idx = Mask[i]; i != e; ++i)
6725 if (Mask[i] >= 0 && Mask[i] != Idx)
6731 static void checkForCyclesHelper(const SDNode *N,
6732 SmallPtrSet<const SDNode*, 32> &Visited,
6733 SmallPtrSet<const SDNode*, 32> &Checked,
6734 const llvm::SelectionDAG *DAG) {
6735 // If this node has already been checked, don't check it again.
6736 if (Checked.count(N))
6739 // If a node has already been visited on this depth-first walk, reject it as
6741 if (!Visited.insert(N)) {
6742 errs() << "Detected cycle in SelectionDAG\n";
6743 dbgs() << "Offending node:\n";
6744 N->dumprFull(DAG); dbgs() << "\n";
6748 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6749 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6756 void llvm::checkForCycles(const llvm::SDNode *N,
6757 const llvm::SelectionDAG *DAG,
6765 assert(N && "Checking nonexistent SDNode");
6766 SmallPtrSet<const SDNode*, 32> visited;
6767 SmallPtrSet<const SDNode*, 32> checked;
6768 checkForCyclesHelper(N, visited, checked, DAG);
6773 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6774 checkForCycles(DAG->getRoot().getNode(), DAG, force);