1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59 SDVTList Res = {VTs, NumVTs};
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67 //===----------------------------------------------------------------------===//
68 // ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76 return getValueAPF().bitwiseIsEqual(V);
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
81 assert(VT.isFloatingPoint() && "Can only convert between FP types");
83 // convert modifies in place, so make a copy.
84 APFloat Val2 = APFloat(Val);
86 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87 APFloat::rmNearestTiesToEven,
92 //===----------------------------------------------------------------------===//
94 //===----------------------------------------------------------------------===//
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99 // Look through a bit convert.
100 while (N->getOpcode() == ISD::BITCAST)
101 N = N->getOperand(0).getNode();
103 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105 unsigned i = 0, e = N->getNumOperands();
107 // Skip over all of the undef values.
108 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111 // Do not accept an all-undef vector.
112 if (i == e) return false;
114 // Do not accept build_vectors that aren't all constants or which have non-~0
115 // elements. We have to be a bit careful here, as the type of the constant
116 // may not be the same as the type of the vector elements due to type
117 // legalization (the elements are promoted to a legal type for the target and
118 // a vector of a type may be legal when the base element type is not).
119 // We only want to check enough bits to cover the vector elements, because
120 // we care if the resultant vector is all ones, not whether the individual
122 SDValue NotZero = N->getOperand(i);
123 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133 // Okay, we have at least one ~0 value, check to see if the rest match or are
134 // undefs. Even with the above element type twiddling, this should be OK, as
135 // the same type legalization should have applied to all the elements.
136 for (++i; i != e; ++i)
137 if (N->getOperand(i) != NotZero &&
138 N->getOperand(i).getOpcode() != ISD::UNDEF)
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147 // Look through a bit convert.
148 while (N->getOpcode() == ISD::BITCAST)
149 N = N->getOperand(0).getNode();
151 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153 bool IsAllUndef = true;
154 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept build_vectors that aren't all constants or which have non-0
159 // elements. We have to be a bit careful here, as the type of the constant
160 // may not be the same as the type of the vector elements due to type
161 // legalization (the elements are promoted to a legal type for the target
162 // and a vector of a type may be legal when the base element type is not).
163 // We only want to check enough bits to cover the vector elements, because
164 // we care if the resultant vector is all zeros, not whether the individual
166 SDValue Zero = N->getOperand(i);
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
191 SDValue Op = N->getOperand(i);
192 if (Op.getOpcode() == ISD::UNDEF)
194 if (!isa<ConstantSDNode>(Op))
200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
201 /// all ConstantFPSDNode or undef.
202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
207 SDValue Op = N->getOperand(i);
208 if (Op.getOpcode() == ISD::UNDEF)
210 if (!isa<ConstantFPSDNode>(Op))
216 /// isScalarToVector - Return true if the specified node is a
217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
218 /// element is not an undef.
219 bool ISD::isScalarToVector(const SDNode *N) {
220 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
223 if (N->getOpcode() != ISD::BUILD_VECTOR)
225 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
227 unsigned NumElems = N->getNumOperands();
230 for (unsigned i = 1; i < NumElems; ++i) {
231 SDValue V = N->getOperand(i);
232 if (V.getOpcode() != ISD::UNDEF)
238 /// allOperandsUndef - Return true if the node has at least one operand
239 /// and all operands of the specified node are ISD::UNDEF.
240 bool ISD::allOperandsUndef(const SDNode *N) {
241 // Return false if the node has no operands.
242 // This is "logically inconsistent" with the definition of "all" but
243 // is probably the desired behavior.
244 if (N->getNumOperands() == 0)
247 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
248 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
257 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
259 return ISD::SIGN_EXTEND;
261 return ISD::ZERO_EXTEND;
266 llvm_unreachable("Invalid LoadExtType");
269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
270 /// when given the operation for (X op Y).
271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
272 // To perform this operation, we just need to swap the L and G bits of the
274 unsigned OldL = (Operation >> 2) & 1;
275 unsigned OldG = (Operation >> 1) & 1;
276 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
277 (OldL << 1) | // New G bit
278 (OldG << 2)); // New L bit.
281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
282 /// 'op' is a valid SetCC operation.
283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
284 unsigned Operation = Op;
286 Operation ^= 7; // Flip L, G, E bits, but not U.
288 Operation ^= 15; // Flip all of the condition bits.
290 if (Operation > ISD::SETTRUE2)
291 Operation &= ~8; // Don't let N and U bits get set.
293 return ISD::CondCode(Operation);
297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
298 /// signed operation and 2 if the result is an unsigned comparison. Return zero
299 /// if the operation does not depend on the sign of the input (setne and seteq).
300 static int isSignedOp(ISD::CondCode Opcode) {
302 default: llvm_unreachable("Illegal integer setcc operation!");
304 case ISD::SETNE: return 0;
308 case ISD::SETGE: return 1;
312 case ISD::SETUGE: return 2;
316 /// getSetCCOrOperation - Return the result of a logical OR between different
317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
318 /// returns SETCC_INVALID if it is not possible to represent the resultant
320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
322 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323 // Cannot fold a signed integer setcc with an unsigned integer setcc.
324 return ISD::SETCC_INVALID;
326 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
328 // If the N and U bits get set then the resultant comparison DOES suddenly
329 // care about orderedness, and is true when ordered.
330 if (Op > ISD::SETTRUE2)
331 Op &= ~16; // Clear the U bit if the N bit is set.
333 // Canonicalize illegal integer setcc's.
334 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
337 return ISD::CondCode(Op);
340 /// getSetCCAndOperation - Return the result of a logical AND between different
341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
342 /// function returns zero if it is not possible to represent the resultant
344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
346 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
347 // Cannot fold a signed setcc with an unsigned setcc.
348 return ISD::SETCC_INVALID;
350 // Combine all of the condition bits.
351 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
353 // Canonicalize illegal integer setcc's.
357 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
358 case ISD::SETOEQ: // SETEQ & SETU[LG]E
359 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
360 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
361 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
368 //===----------------------------------------------------------------------===//
369 // SDNode Profile Support
370 //===----------------------------------------------------------------------===//
372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
379 /// solely with their pointer.
380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
381 ID.AddPointer(VTList.VTs);
384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
387 ArrayRef<SDValue> Ops) {
388 for (auto& Op : Ops) {
389 ID.AddPointer(Op.getNode());
390 ID.AddInteger(Op.getResNo());
394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
397 ArrayRef<SDUse> Ops) {
398 for (auto& Op : Ops) {
399 ID.AddPointer(Op.getNode());
400 ID.AddInteger(Op.getResNo());
404 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
408 ID.AddBoolean(exact);
411 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
412 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
413 bool nuw, bool nsw, bool exact) {
414 if (isBinOpWithFlags(Opcode))
415 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
418 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
419 SDVTList VTList, ArrayRef<SDValue> OpList) {
420 AddNodeIDOpcode(ID, OpC);
421 AddNodeIDValueTypes(ID, VTList);
422 AddNodeIDOperands(ID, OpList);
425 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
427 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
428 switch (N->getOpcode()) {
429 case ISD::TargetExternalSymbol:
430 case ISD::ExternalSymbol:
431 llvm_unreachable("Should only be used on nodes with operands");
432 default: break; // Normal nodes don't need extra info.
433 case ISD::TargetConstant:
434 case ISD::Constant: {
435 const ConstantSDNode *C = cast<ConstantSDNode>(N);
436 ID.AddPointer(C->getConstantIntValue());
437 ID.AddBoolean(C->isOpaque());
440 case ISD::TargetConstantFP:
441 case ISD::ConstantFP: {
442 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
445 case ISD::TargetGlobalAddress:
446 case ISD::GlobalAddress:
447 case ISD::TargetGlobalTLSAddress:
448 case ISD::GlobalTLSAddress: {
449 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
450 ID.AddPointer(GA->getGlobal());
451 ID.AddInteger(GA->getOffset());
452 ID.AddInteger(GA->getTargetFlags());
453 ID.AddInteger(GA->getAddressSpace());
456 case ISD::BasicBlock:
457 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
460 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
462 case ISD::RegisterMask:
463 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
466 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
468 case ISD::FrameIndex:
469 case ISD::TargetFrameIndex:
470 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
473 case ISD::TargetJumpTable:
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
475 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
477 case ISD::ConstantPool:
478 case ISD::TargetConstantPool: {
479 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
480 ID.AddInteger(CP->getAlignment());
481 ID.AddInteger(CP->getOffset());
482 if (CP->isMachineConstantPoolEntry())
483 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
485 ID.AddPointer(CP->getConstVal());
486 ID.AddInteger(CP->getTargetFlags());
489 case ISD::TargetIndex: {
490 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
491 ID.AddInteger(TI->getIndex());
492 ID.AddInteger(TI->getOffset());
493 ID.AddInteger(TI->getTargetFlags());
497 const LoadSDNode *LD = cast<LoadSDNode>(N);
498 ID.AddInteger(LD->getMemoryVT().getRawBits());
499 ID.AddInteger(LD->getRawSubclassData());
500 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
504 const StoreSDNode *ST = cast<StoreSDNode>(N);
505 ID.AddInteger(ST->getMemoryVT().getRawBits());
506 ID.AddInteger(ST->getRawSubclassData());
507 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
518 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
519 AddBinaryNodeIDCustom(
520 ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
521 BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
524 case ISD::ATOMIC_CMP_SWAP:
525 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
526 case ISD::ATOMIC_SWAP:
527 case ISD::ATOMIC_LOAD_ADD:
528 case ISD::ATOMIC_LOAD_SUB:
529 case ISD::ATOMIC_LOAD_AND:
530 case ISD::ATOMIC_LOAD_OR:
531 case ISD::ATOMIC_LOAD_XOR:
532 case ISD::ATOMIC_LOAD_NAND:
533 case ISD::ATOMIC_LOAD_MIN:
534 case ISD::ATOMIC_LOAD_MAX:
535 case ISD::ATOMIC_LOAD_UMIN:
536 case ISD::ATOMIC_LOAD_UMAX:
537 case ISD::ATOMIC_LOAD:
538 case ISD::ATOMIC_STORE: {
539 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
540 ID.AddInteger(AT->getMemoryVT().getRawBits());
541 ID.AddInteger(AT->getRawSubclassData());
542 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
545 case ISD::PREFETCH: {
546 const MemSDNode *PF = cast<MemSDNode>(N);
547 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
550 case ISD::VECTOR_SHUFFLE: {
551 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
552 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
554 ID.AddInteger(SVN->getMaskElt(i));
557 case ISD::TargetBlockAddress:
558 case ISD::BlockAddress: {
559 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
560 ID.AddPointer(BA->getBlockAddress());
561 ID.AddInteger(BA->getOffset());
562 ID.AddInteger(BA->getTargetFlags());
565 } // end switch (N->getOpcode())
567 // Target specific memory nodes could also have address spaces to check.
568 if (N->isTargetMemoryOpcode())
569 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
575 AddNodeIDOpcode(ID, N->getOpcode());
576 // Add the return value info.
577 AddNodeIDValueTypes(ID, N->getVTList());
578 // Add the operand info.
579 AddNodeIDOperands(ID, N->ops());
581 // Handle SDNode leafs with special info.
582 AddNodeIDCustom(ID, N);
585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
586 /// the CSE map that carries volatility, temporalness, indexing mode, and
587 /// extension/truncation information.
589 static inline unsigned
590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
591 bool isNonTemporal, bool isInvariant) {
592 assert((ConvType & 3) == ConvType &&
593 "ConvType may not require more than 2 bits!");
594 assert((AM & 7) == AM &&
595 "AM may not require more than 3 bits!");
599 (isNonTemporal << 6) |
603 //===----------------------------------------------------------------------===//
604 // SelectionDAG Class
605 //===----------------------------------------------------------------------===//
607 /// doNotCSE - Return true if CSE should not be performed for this node.
608 static bool doNotCSE(SDNode *N) {
609 if (N->getValueType(0) == MVT::Glue)
610 return true; // Never CSE anything that produces a flag.
612 switch (N->getOpcode()) {
614 case ISD::HANDLENODE:
616 return true; // Never CSE these nodes.
619 // Check that remaining values produced are not flags.
620 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
621 if (N->getValueType(i) == MVT::Glue)
622 return true; // Never CSE anything that produces a flag.
627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
629 void SelectionDAG::RemoveDeadNodes() {
630 // Create a dummy node (which is not added to allnodes), that adds a reference
631 // to the root node, preventing it from being deleted.
632 HandleSDNode Dummy(getRoot());
634 SmallVector<SDNode*, 128> DeadNodes;
636 // Add all obviously-dead nodes to the DeadNodes worklist.
637 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
639 DeadNodes.push_back(I);
641 RemoveDeadNodes(DeadNodes);
643 // If the root changed (e.g. it was a dead load, update the root).
644 setRoot(Dummy.getValue());
647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
648 /// given list, and any nodes that become unreachable as a result.
649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
651 // Process the worklist, deleting the nodes and adding their uses to the
653 while (!DeadNodes.empty()) {
654 SDNode *N = DeadNodes.pop_back_val();
656 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
657 DUL->NodeDeleted(N, nullptr);
659 // Take the node out of the appropriate CSE map.
660 RemoveNodeFromCSEMaps(N);
662 // Next, brutally remove the operand list. This is safe to do, as there are
663 // no cycles in the graph.
664 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
666 SDNode *Operand = Use.getNode();
669 // Now that we removed this operand, see if there are no uses of it left.
670 if (Operand->use_empty())
671 DeadNodes.push_back(Operand);
678 void SelectionDAG::RemoveDeadNode(SDNode *N){
679 SmallVector<SDNode*, 16> DeadNodes(1, N);
681 // Create a dummy node that adds a reference to the root node, preventing
682 // it from being deleted. (This matters if the root is an operand of the
684 HandleSDNode Dummy(getRoot());
686 RemoveDeadNodes(DeadNodes);
689 void SelectionDAG::DeleteNode(SDNode *N) {
690 // First take this out of the appropriate CSE map.
691 RemoveNodeFromCSEMaps(N);
693 // Finally, remove uses due to operands of this node, remove from the
694 // AllNodes list, and delete the node.
695 DeleteNodeNotInCSEMaps(N);
698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
699 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
700 assert(N->use_empty() && "Cannot delete a node that is not dead!");
702 // Drop all of the operands and decrement used node's use counts.
708 void SDDbgInfo::erase(const SDNode *Node) {
709 DbgValMapType::iterator I = DbgValMap.find(Node);
710 if (I == DbgValMap.end())
712 for (auto &Val: I->second)
713 Val->setIsInvalidated();
717 void SelectionDAG::DeallocateNode(SDNode *N) {
718 if (N->OperandsNeedDelete)
719 delete[] N->OperandList;
721 // Set the opcode to DELETED_NODE to help catch bugs when node
722 // memory is reallocated.
723 N->NodeType = ISD::DELETED_NODE;
725 NodeAllocator.Deallocate(AllNodes.remove(N));
727 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
728 // them and forget about that node.
733 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
734 static void VerifySDNode(SDNode *N) {
735 switch (N->getOpcode()) {
738 case ISD::BUILD_PAIR: {
739 EVT VT = N->getValueType(0);
740 assert(N->getNumValues() == 1 && "Too many results!");
741 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
742 "Wrong return type!");
743 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
744 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
745 "Mismatched operand types!");
746 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
747 "Wrong operand type!");
748 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
749 "Wrong return type size");
752 case ISD::BUILD_VECTOR: {
753 assert(N->getNumValues() == 1 && "Too many results!");
754 assert(N->getValueType(0).isVector() && "Wrong return type!");
755 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
756 "Wrong number of operands!");
757 EVT EltVT = N->getValueType(0).getVectorElementType();
758 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
759 assert((I->getValueType() == EltVT ||
760 (EltVT.isInteger() && I->getValueType().isInteger() &&
761 EltVT.bitsLE(I->getValueType()))) &&
762 "Wrong operand type!");
763 assert(I->getValueType() == N->getOperand(0).getValueType() &&
764 "Operands must all have the same type");
772 /// \brief Insert a newly allocated node into the DAG.
774 /// Handles insertion into the all nodes list and CSE map, as well as
775 /// verification and other common operations when a new node is allocated.
776 void SelectionDAG::InsertNode(SDNode *N) {
777 AllNodes.push_back(N);
783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
784 /// correspond to it. This is useful when we're about to delete or repurpose
785 /// the node. We don't want future request for structurally identical nodes
786 /// to return N anymore.
787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
789 switch (N->getOpcode()) {
790 case ISD::HANDLENODE: return false; // noop.
792 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
793 "Cond code doesn't exist!");
794 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
795 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
797 case ISD::ExternalSymbol:
798 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
800 case ISD::TargetExternalSymbol: {
801 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
802 Erased = TargetExternalSymbols.erase(
803 std::pair<std::string,unsigned char>(ESN->getSymbol(),
804 ESN->getTargetFlags()));
807 case ISD::VALUETYPE: {
808 EVT VT = cast<VTSDNode>(N)->getVT();
809 if (VT.isExtended()) {
810 Erased = ExtendedValueTypeNodes.erase(VT);
812 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
813 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
818 // Remove it from the CSE Map.
819 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
820 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
821 Erased = CSEMap.RemoveNode(N);
825 // Verify that the node was actually in one of the CSE maps, unless it has a
826 // flag result (which cannot be CSE'd) or is one of the special cases that are
827 // not subject to CSE.
828 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
829 !N->isMachineOpcode() && !doNotCSE(N)) {
832 llvm_unreachable("Node is not in map!");
838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
840 /// node already exists, in which case transfer all its users to the existing
841 /// node. This transfer can potentially trigger recursive merging.
844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
845 // For node types that aren't CSE'd, just act as if no identical node
848 SDNode *Existing = CSEMap.GetOrInsertNode(N);
850 // If there was already an existing matching node, use ReplaceAllUsesWith
851 // to replace the dead one with the existing one. This can cause
852 // recursive merging of other unrelated nodes down the line.
853 ReplaceAllUsesWith(N, Existing);
855 // N is now dead. Inform the listeners and delete it.
856 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
857 DUL->NodeDeleted(N, Existing);
858 DeleteNodeNotInCSEMaps(N);
863 // If the node doesn't already exist, we updated it. Inform listeners.
864 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
869 /// were replaced with those specified. If this node is never memoized,
870 /// return null, otherwise return a pointer to the slot it would take. If a
871 /// node already exists with these operands, the slot will be non-null.
872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
877 SDValue Ops[] = { Op };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
886 /// were replaced with those specified. If this node is never memoized,
887 /// return null, otherwise return a pointer to the slot it would take. If a
888 /// node already exists with these operands, the slot will be non-null.
889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
890 SDValue Op1, SDValue Op2,
895 SDValue Ops[] = { Op1, Op2 };
897 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
898 AddNodeIDCustom(ID, N);
899 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
905 /// were replaced with those specified. If this node is never memoized,
906 /// return null, otherwise return a pointer to the slot it would take. If a
907 /// node already exists with these operands, the slot will be non-null.
908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
914 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
915 AddNodeIDCustom(ID, N);
916 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
920 /// getEVTAlignment - Compute the default alignment value for the
923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
924 Type *Ty = VT == MVT::iPTR ?
925 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
926 VT.getTypeForEVT(*getContext());
928 return TLI->getDataLayout()->getABITypeAlignment(Ty);
931 // EntryNode could meaningfully have debug info if we can find it...
932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
933 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
934 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
935 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
936 UpdateListeners(nullptr) {
937 AllNodes.push_back(&EntryNode);
938 DbgInfo = new SDDbgInfo();
941 void SelectionDAG::init(MachineFunction &mf) {
943 TLI = getSubtarget().getTargetLowering();
944 TSI = getSubtarget().getSelectionDAGInfo();
945 Context = &mf.getFunction()->getContext();
948 SelectionDAG::~SelectionDAG() {
949 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
954 void SelectionDAG::allnodes_clear() {
955 assert(&*AllNodes.begin() == &EntryNode);
956 AllNodes.remove(AllNodes.begin());
957 while (!AllNodes.empty())
958 DeallocateNode(AllNodes.begin());
961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
962 SDVTList VTs, SDValue N1,
963 SDValue N2, bool nuw, bool nsw,
965 if (isBinOpWithFlags(Opcode)) {
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
968 FN->Flags.setNoUnsignedWrap(nuw);
969 FN->Flags.setNoSignedWrap(nsw);
970 FN->Flags.setExact(exact);
975 BinarySDNode *N = new (NodeAllocator)
976 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
982 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
984 switch (N->getOpcode()) {
987 case ISD::ConstantFP:
988 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
989 "debug location. Use another overload.");
995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
996 DebugLoc DL, void *&InsertPos) {
997 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
999 switch (N->getOpcode()) {
1000 default: break; // Process only regular (non-target) constant nodes.
1002 case ISD::ConstantFP:
1003 // Erase debug location from the node if the node is used at several
1004 // different places to do not propagate one location to all uses as it
1005 // leads to incorrect debug info.
1006 if (N->getDebugLoc() != DL)
1007 N->setDebugLoc(DebugLoc());
1014 void SelectionDAG::clear() {
1016 OperandAllocator.Reset();
1019 ExtendedValueTypeNodes.clear();
1020 ExternalSymbols.clear();
1021 TargetExternalSymbols.clear();
1022 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1023 static_cast<CondCodeSDNode*>(nullptr));
1024 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1025 static_cast<SDNode*>(nullptr));
1027 EntryNode.UseList = nullptr;
1028 AllNodes.push_back(&EntryNode);
1029 Root = getEntryNode();
1033 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1034 return VT.bitsGT(Op.getValueType()) ?
1035 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1036 getNode(ISD::TRUNCATE, DL, VT, Op);
1039 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1040 return VT.bitsGT(Op.getValueType()) ?
1041 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1042 getNode(ISD::TRUNCATE, DL, VT, Op);
1045 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1046 return VT.bitsGT(Op.getValueType()) ?
1047 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1048 getNode(ISD::TRUNCATE, DL, VT, Op);
1051 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1053 if (VT.bitsLE(Op.getValueType()))
1054 return getNode(ISD::TRUNCATE, SL, VT, Op);
1056 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1057 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1060 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1061 assert(!VT.isVector() &&
1062 "getZeroExtendInReg should use the vector element type instead of "
1063 "the vector type!");
1064 if (Op.getValueType() == VT) return Op;
1065 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1066 APInt Imm = APInt::getLowBitsSet(BitWidth,
1067 VT.getSizeInBits());
1068 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1069 getConstant(Imm, DL, Op.getValueType()));
1072 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1073 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1074 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1075 "The sizes of the input and result must match in order to perform the "
1076 "extend in-register.");
1077 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1078 "The destination vector type must have fewer lanes than the input.");
1079 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1082 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1083 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1084 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1085 "The sizes of the input and result must match in order to perform the "
1086 "extend in-register.");
1087 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1088 "The destination vector type must have fewer lanes than the input.");
1089 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1092 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1093 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1094 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1095 "The sizes of the input and result must match in order to perform the "
1096 "extend in-register.");
1097 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1098 "The destination vector type must have fewer lanes than the input.");
1099 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1102 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1104 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1105 EVT EltVT = VT.getScalarType();
1107 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1108 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1111 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1112 EVT EltVT = VT.getScalarType();
1114 switch (TLI->getBooleanContents(VT)) {
1115 case TargetLowering::ZeroOrOneBooleanContent:
1116 case TargetLowering::UndefinedBooleanContent:
1117 TrueValue = getConstant(1, DL, VT);
1119 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1120 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1124 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1127 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1129 EVT EltVT = VT.getScalarType();
1130 assert((EltVT.getSizeInBits() >= 64 ||
1131 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1132 "getConstant with a uint64_t value that doesn't fit in the type!");
1133 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1136 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1139 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1142 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1143 bool isT, bool isO) {
1144 assert(VT.isInteger() && "Cannot create FP integer constant!");
1146 EVT EltVT = VT.getScalarType();
1147 const ConstantInt *Elt = &Val;
1149 // In some cases the vector type is legal but the element type is illegal and
1150 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1151 // inserted value (the type does not need to match the vector element type).
1152 // Any extra bits introduced will be truncated away.
1153 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1154 TargetLowering::TypePromoteInteger) {
1155 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1156 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1157 Elt = ConstantInt::get(*getContext(), NewVal);
1159 // In other cases the element type is illegal and needs to be expanded, for
1160 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1161 // the value into n parts and use a vector type with n-times the elements.
1162 // Then bitcast to the type requested.
1163 // Legalizing constants too early makes the DAGCombiner's job harder so we
1164 // only legalize if the DAG tells us we must produce legal types.
1165 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1166 TLI->getTypeAction(*getContext(), EltVT) ==
1167 TargetLowering::TypeExpandInteger) {
1168 APInt NewVal = Elt->getValue();
1169 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1170 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1171 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1172 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1174 // Check the temporary vector is the correct size. If this fails then
1175 // getTypeToTransformTo() probably returned a type whose size (in bits)
1176 // isn't a power-of-2 factor of the requested type size.
1177 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1179 SmallVector<SDValue, 2> EltParts;
1180 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1181 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1182 .trunc(ViaEltSizeInBits), DL,
1183 ViaEltVT, isT, isO));
1186 // EltParts is currently in little endian order. If we actually want
1187 // big-endian order then reverse it now.
1188 if (TLI->isBigEndian())
1189 std::reverse(EltParts.begin(), EltParts.end());
1191 // The elements must be reversed when the element order is different
1192 // to the endianness of the elements (because the BITCAST is itself a
1193 // vector shuffle in this situation). However, we do not need any code to
1194 // perform this reversal because getConstant() is producing a vector
1196 // This situation occurs in MIPS MSA.
1198 SmallVector<SDValue, 8> Ops;
1199 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1200 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1202 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1203 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1208 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1209 "APInt size does not match type size!");
1210 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1211 FoldingSetNodeID ID;
1212 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1216 SDNode *N = nullptr;
1217 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1219 return SDValue(N, 0);
1222 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1224 CSEMap.InsertNode(N, IP);
1228 SDValue Result(N, 0);
1229 if (VT.isVector()) {
1230 SmallVector<SDValue, 8> Ops;
1231 Ops.assign(VT.getVectorNumElements(), Result);
1232 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1237 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1238 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1241 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1243 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1246 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1248 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1250 EVT EltVT = VT.getScalarType();
1252 // Do the map lookup using the actual bit pattern for the floating point
1253 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1254 // we don't have issues with SNANs.
1255 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1256 FoldingSetNodeID ID;
1257 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1260 SDNode *N = nullptr;
1261 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1263 return SDValue(N, 0);
1266 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1268 CSEMap.InsertNode(N, IP);
1272 SDValue Result(N, 0);
1273 if (VT.isVector()) {
1274 SmallVector<SDValue, 8> Ops;
1275 Ops.assign(VT.getVectorNumElements(), Result);
1276 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1281 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1283 EVT EltVT = VT.getScalarType();
1284 if (EltVT==MVT::f32)
1285 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f64)
1287 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1288 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1291 APFloat apf = APFloat(Val);
1292 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1294 return getConstantFP(apf, DL, VT, isTarget);
1296 llvm_unreachable("Unsupported type in getConstantFP");
1299 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1300 EVT VT, int64_t Offset,
1302 unsigned char TargetFlags) {
1303 assert((TargetFlags == 0 || isTargetGA) &&
1304 "Cannot set target flags on target-independent globals");
1306 // Truncate (with sign-extension) the offset value to the pointer size.
1307 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1309 Offset = SignExtend64(Offset, BitWidth);
1312 if (GV->isThreadLocal())
1313 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1315 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1320 ID.AddInteger(Offset);
1321 ID.AddInteger(TargetFlags);
1322 ID.AddInteger(GV->getType()->getAddressSpace());
1324 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1325 return SDValue(E, 0);
1327 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1328 DL.getDebugLoc(), GV, VT,
1329 Offset, TargetFlags);
1330 CSEMap.InsertNode(N, IP);
1332 return SDValue(N, 0);
1335 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1336 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1337 FoldingSetNodeID ID;
1338 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1342 return SDValue(E, 0);
1344 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1345 CSEMap.InsertNode(N, IP);
1347 return SDValue(N, 0);
1350 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1351 unsigned char TargetFlags) {
1352 assert((TargetFlags == 0 || isTarget) &&
1353 "Cannot set target flags on target-independent jump tables");
1354 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1355 FoldingSetNodeID ID;
1356 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1358 ID.AddInteger(TargetFlags);
1360 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1361 return SDValue(E, 0);
1363 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1365 CSEMap.InsertNode(N, IP);
1367 return SDValue(N, 0);
1370 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1371 unsigned Alignment, int Offset,
1373 unsigned char TargetFlags) {
1374 assert((TargetFlags == 0 || isTarget) &&
1375 "Cannot set target flags on target-independent globals");
1377 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1378 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1379 FoldingSetNodeID ID;
1380 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1381 ID.AddInteger(Alignment);
1382 ID.AddInteger(Offset);
1384 ID.AddInteger(TargetFlags);
1386 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1387 return SDValue(E, 0);
1389 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1390 Alignment, TargetFlags);
1391 CSEMap.InsertNode(N, IP);
1393 return SDValue(N, 0);
1397 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1398 unsigned Alignment, int Offset,
1400 unsigned char TargetFlags) {
1401 assert((TargetFlags == 0 || isTarget) &&
1402 "Cannot set target flags on target-independent globals");
1404 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1405 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1408 ID.AddInteger(Alignment);
1409 ID.AddInteger(Offset);
1410 C->addSelectionDAGCSEId(ID);
1411 ID.AddInteger(TargetFlags);
1413 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1414 return SDValue(E, 0);
1416 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1417 Alignment, TargetFlags);
1418 CSEMap.InsertNode(N, IP);
1420 return SDValue(N, 0);
1423 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1424 unsigned char TargetFlags) {
1425 FoldingSetNodeID ID;
1426 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1427 ID.AddInteger(Index);
1428 ID.AddInteger(Offset);
1429 ID.AddInteger(TargetFlags);
1431 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1432 return SDValue(E, 0);
1434 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1436 CSEMap.InsertNode(N, IP);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1442 FoldingSetNodeID ID;
1443 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1446 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1447 return SDValue(E, 0);
1449 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1450 CSEMap.InsertNode(N, IP);
1452 return SDValue(N, 0);
1455 SDValue SelectionDAG::getValueType(EVT VT) {
1456 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1457 ValueTypeNodes.size())
1458 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1460 SDNode *&N = VT.isExtended() ?
1461 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1463 if (N) return SDValue(N, 0);
1464 N = new (NodeAllocator) VTSDNode(VT);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1470 SDNode *&N = ExternalSymbols[Sym];
1471 if (N) return SDValue(N, 0);
1472 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1474 return SDValue(N, 0);
1477 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1478 unsigned char TargetFlags) {
1480 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1482 if (N) return SDValue(N, 0);
1483 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1485 return SDValue(N, 0);
1488 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1489 if ((unsigned)Cond >= CondCodeNodes.size())
1490 CondCodeNodes.resize(Cond+1);
1492 if (!CondCodeNodes[Cond]) {
1493 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1494 CondCodeNodes[Cond] = N;
1498 return SDValue(CondCodeNodes[Cond], 0);
1501 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1502 // the shuffle mask M that point at N1 to point at N2, and indices that point
1503 // N2 to point at N1.
1504 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1506 ShuffleVectorSDNode::commuteMask(M);
1509 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1510 SDValue N2, const int *Mask) {
1511 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1512 "Invalid VECTOR_SHUFFLE");
1514 // Canonicalize shuffle undef, undef -> undef
1515 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1516 return getUNDEF(VT);
1518 // Validate that all indices in Mask are within the range of the elements
1519 // input to the shuffle.
1520 unsigned NElts = VT.getVectorNumElements();
1521 SmallVector<int, 8> MaskVec;
1522 for (unsigned i = 0; i != NElts; ++i) {
1523 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1524 MaskVec.push_back(Mask[i]);
1527 // Canonicalize shuffle v, v -> v, undef
1530 for (unsigned i = 0; i != NElts; ++i)
1531 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1534 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1535 if (N1.getOpcode() == ISD::UNDEF)
1536 commuteShuffle(N1, N2, MaskVec);
1538 // If shuffling a splat, try to blend the splat instead. We do this here so
1539 // that even when this arises during lowering we don't have to re-handle it.
1540 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1541 BitVector UndefElements;
1542 SDValue Splat = BV->getSplatValue(&UndefElements);
1546 for (int i = 0; i < (int)NElts; ++i) {
1547 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1550 // If this input comes from undef, mark it as such.
1551 if (UndefElements[MaskVec[i] - Offset]) {
1556 // If we can blend a non-undef lane, use that instead.
1557 if (!UndefElements[i])
1558 MaskVec[i] = i + Offset;
1561 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1562 BlendSplat(N1BV, 0);
1563 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1564 BlendSplat(N2BV, NElts);
1566 // Canonicalize all index into lhs, -> shuffle lhs, undef
1567 // Canonicalize all index into rhs, -> shuffle rhs, undef
1568 bool AllLHS = true, AllRHS = true;
1569 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1570 for (unsigned i = 0; i != NElts; ++i) {
1571 if (MaskVec[i] >= (int)NElts) {
1576 } else if (MaskVec[i] >= 0) {
1580 if (AllLHS && AllRHS)
1581 return getUNDEF(VT);
1582 if (AllLHS && !N2Undef)
1586 commuteShuffle(N1, N2, MaskVec);
1588 // Reset our undef status after accounting for the mask.
1589 N2Undef = N2.getOpcode() == ISD::UNDEF;
1590 // Re-check whether both sides ended up undef.
1591 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1592 return getUNDEF(VT);
1594 // If Identity shuffle return that node.
1595 bool Identity = true, AllSame = true;
1596 for (unsigned i = 0; i != NElts; ++i) {
1597 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1598 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1600 if (Identity && NElts)
1603 // Shuffling a constant splat doesn't change the result.
1607 // Look through any bitcasts. We check that these don't change the number
1608 // (and size) of elements and just changes their types.
1609 while (V.getOpcode() == ISD::BITCAST)
1610 V = V->getOperand(0);
1612 // A splat should always show up as a build vector node.
1613 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1614 BitVector UndefElements;
1615 SDValue Splat = BV->getSplatValue(&UndefElements);
1616 // If this is a splat of an undef, shuffling it is also undef.
1617 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1618 return getUNDEF(VT);
1621 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1623 // We only have a splat which can skip shuffles if there is a splatted
1624 // value and no undef lanes rearranged by the shuffle.
1625 if (Splat && UndefElements.none()) {
1626 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1627 // number of elements match or the value splatted is a zero constant.
1630 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1631 if (C->isNullValue())
1635 // If the shuffle itself creates a splat, build the vector directly.
1636 if (AllSame && SameNumElts) {
1637 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1638 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1640 EVT BuildVT = BV->getValueType(0);
1641 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1643 // We may have jumped through bitcasts, so the type of the
1644 // BUILD_VECTOR may not match the type of the shuffle.
1646 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1652 FoldingSetNodeID ID;
1653 SDValue Ops[2] = { N1, N2 };
1654 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1655 for (unsigned i = 0; i != NElts; ++i)
1656 ID.AddInteger(MaskVec[i]);
1659 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1660 return SDValue(E, 0);
1662 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1663 // SDNode doesn't have access to it. This memory will be "leaked" when
1664 // the node is deallocated, but recovered when the NodeAllocator is released.
1665 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1666 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1668 ShuffleVectorSDNode *N =
1669 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1670 dl.getDebugLoc(), N1, N2,
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1678 MVT VT = SV.getSimpleValueType(0);
1679 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1680 ShuffleVectorSDNode::commuteMask(MaskVec);
1682 SDValue Op0 = SV.getOperand(0);
1683 SDValue Op1 = SV.getOperand(1);
1684 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1687 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1688 SDValue Val, SDValue DTy,
1689 SDValue STy, SDValue Rnd, SDValue Sat,
1690 ISD::CvtCode Code) {
1691 // If the src and dest types are the same and the conversion is between
1692 // integer types of the same sign or two floats, no conversion is necessary.
1694 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1697 FoldingSetNodeID ID;
1698 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1699 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1701 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1702 return SDValue(E, 0);
1704 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1707 CSEMap.InsertNode(N, IP);
1709 return SDValue(N, 0);
1712 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1713 FoldingSetNodeID ID;
1714 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1715 ID.AddInteger(RegNo);
1717 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1718 return SDValue(E, 0);
1720 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1721 CSEMap.InsertNode(N, IP);
1723 return SDValue(N, 0);
1726 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1727 FoldingSetNodeID ID;
1728 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1729 ID.AddPointer(RegMask);
1731 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1735 CSEMap.InsertNode(N, IP);
1737 return SDValue(N, 0);
1740 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1741 FoldingSetNodeID ID;
1742 SDValue Ops[] = { Root };
1743 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1744 ID.AddPointer(Label);
1746 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1747 return SDValue(E, 0);
1749 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1750 dl.getDebugLoc(), Root, Label);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1757 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1760 unsigned char TargetFlags) {
1761 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1763 FoldingSetNodeID ID;
1764 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1766 ID.AddInteger(Offset);
1767 ID.AddInteger(TargetFlags);
1769 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1772 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1774 CSEMap.InsertNode(N, IP);
1776 return SDValue(N, 0);
1779 SDValue SelectionDAG::getSrcValue(const Value *V) {
1780 assert((!V || V->getType()->isPointerTy()) &&
1781 "SrcValue is not a pointer?");
1783 FoldingSetNodeID ID;
1784 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1788 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1789 return SDValue(E, 0);
1791 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1792 CSEMap.InsertNode(N, IP);
1794 return SDValue(N, 0);
1797 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1798 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1799 FoldingSetNodeID ID;
1800 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1804 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1805 return SDValue(E, 0);
1807 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1808 CSEMap.InsertNode(N, IP);
1810 return SDValue(N, 0);
1813 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1814 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1815 unsigned SrcAS, unsigned DestAS) {
1816 SDValue Ops[] = {Ptr};
1817 FoldingSetNodeID ID;
1818 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1819 ID.AddInteger(SrcAS);
1820 ID.AddInteger(DestAS);
1823 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1824 return SDValue(E, 0);
1826 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1828 VT, Ptr, SrcAS, DestAS);
1829 CSEMap.InsertNode(N, IP);
1831 return SDValue(N, 0);
1834 /// getShiftAmountOperand - Return the specified value casted to
1835 /// the target's desired shift amount type.
1836 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1837 EVT OpTy = Op.getValueType();
1838 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1839 if (OpTy == ShTy || OpTy.isVector()) return Op;
1841 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1842 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1845 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1846 /// specified value type.
1847 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1848 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1849 unsigned ByteSize = VT.getStoreSize();
1850 Type *Ty = VT.getTypeForEVT(*getContext());
1851 unsigned StackAlign =
1852 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1854 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1855 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1858 /// CreateStackTemporary - Create a stack temporary suitable for holding
1859 /// either of the specified value types.
1860 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1861 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1862 VT2.getStoreSizeInBits())/8;
1863 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1864 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1865 const DataLayout *TD = TLI->getDataLayout();
1866 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1867 TD->getPrefTypeAlignment(Ty2));
1869 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1870 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1871 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1874 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1875 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1876 // These setcc operations always fold.
1880 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1882 case ISD::SETTRUE2: {
1883 TargetLowering::BooleanContent Cnt =
1884 TLI->getBooleanContents(N1->getValueType(0));
1886 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1900 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1904 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1905 const APInt &C2 = N2C->getAPIntValue();
1906 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1907 const APInt &C1 = N1C->getAPIntValue();
1910 default: llvm_unreachable("Unknown integer setcc!");
1911 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1912 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1913 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1914 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1915 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1916 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1917 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1918 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1919 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1920 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1924 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1925 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1926 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1929 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1930 return getUNDEF(VT);
1932 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1933 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1934 return getUNDEF(VT);
1936 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1937 R==APFloat::cmpLessThan, dl, VT);
1938 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1939 return getUNDEF(VT);
1941 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1942 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1943 return getUNDEF(VT);
1945 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1946 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1947 return getUNDEF(VT);
1949 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1950 R==APFloat::cmpEqual, dl, VT);
1951 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1952 return getUNDEF(VT);
1954 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1955 R==APFloat::cmpEqual, dl, VT);
1956 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1957 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1958 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1959 R==APFloat::cmpEqual, dl, VT);
1960 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1961 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1962 R==APFloat::cmpLessThan, dl, VT);
1963 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1964 R==APFloat::cmpUnordered, dl, VT);
1965 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1966 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1969 // Ensure that the constant occurs on the RHS.
1970 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1971 MVT CompVT = N1.getValueType().getSimpleVT();
1972 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1975 return getSetCC(dl, VT, N2, N1, SwappedCond);
1979 // Could not fold it.
1983 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1984 /// use this predicate to simplify operations downstream.
1985 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1986 // This predicate is not safe for vector operations.
1987 if (Op.getValueType().isVector())
1990 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1991 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1994 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1995 /// this predicate to simplify operations downstream. Mask is known to be zero
1996 /// for bits that V cannot have.
1997 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1998 unsigned Depth) const {
1999 APInt KnownZero, KnownOne;
2000 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2001 return (KnownZero & Mask) == Mask;
2004 /// Determine which bits of Op are known to be either zero or one and return
2005 /// them in the KnownZero/KnownOne bitsets.
2006 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2007 APInt &KnownOne, unsigned Depth) const {
2008 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2010 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2012 return; // Limit search depth.
2014 APInt KnownZero2, KnownOne2;
2016 switch (Op.getOpcode()) {
2018 // We know all of the bits for a constant!
2019 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2020 KnownZero = ~KnownOne;
2023 // If either the LHS or the RHS are Zero, the result is zero.
2024 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2025 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2027 // Output known-1 bits are only known if set in both the LHS & RHS.
2028 KnownOne &= KnownOne2;
2029 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2030 KnownZero |= KnownZero2;
2033 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2034 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2036 // Output known-0 bits are only known if clear in both the LHS & RHS.
2037 KnownZero &= KnownZero2;
2038 // Output known-1 are known to be set if set in either the LHS | RHS.
2039 KnownOne |= KnownOne2;
2042 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2043 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2045 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2046 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2047 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2048 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2049 KnownZero = KnownZeroOut;
2053 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2054 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2056 // If low bits are zero in either operand, output low known-0 bits.
2057 // Also compute a conserative estimate for high known-0 bits.
2058 // More trickiness is possible, but this is sufficient for the
2059 // interesting case of alignment computation.
2060 KnownOne.clearAllBits();
2061 unsigned TrailZ = KnownZero.countTrailingOnes() +
2062 KnownZero2.countTrailingOnes();
2063 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2064 KnownZero2.countLeadingOnes(),
2065 BitWidth) - BitWidth;
2067 TrailZ = std::min(TrailZ, BitWidth);
2068 LeadZ = std::min(LeadZ, BitWidth);
2069 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2070 APInt::getHighBitsSet(BitWidth, LeadZ);
2074 // For the purposes of computing leading zeros we can conservatively
2075 // treat a udiv as a logical right shift by the power of 2 known to
2076 // be less than the denominator.
2077 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2078 unsigned LeadZ = KnownZero2.countLeadingOnes();
2080 KnownOne2.clearAllBits();
2081 KnownZero2.clearAllBits();
2082 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2083 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2084 if (RHSUnknownLeadingOnes != BitWidth)
2085 LeadZ = std::min(BitWidth,
2086 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2088 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2092 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2093 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2095 // Only known if known in both the LHS and RHS.
2096 KnownOne &= KnownOne2;
2097 KnownZero &= KnownZero2;
2099 case ISD::SELECT_CC:
2100 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2101 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2103 // Only known if known in both the LHS and RHS.
2104 KnownOne &= KnownOne2;
2105 KnownZero &= KnownZero2;
2113 if (Op.getResNo() != 1)
2115 // The boolean result conforms to getBooleanContents.
2116 // If we know the result of a setcc has the top bits zero, use this info.
2117 // We know that we have an integer-based boolean since these operations
2118 // are only available for integer.
2119 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2120 TargetLowering::ZeroOrOneBooleanContent &&
2122 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2125 // If we know the result of a setcc has the top bits zero, use this info.
2126 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2127 TargetLowering::ZeroOrOneBooleanContent &&
2129 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2132 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2133 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2134 unsigned ShAmt = SA->getZExtValue();
2136 // If the shift count is an invalid immediate, don't do anything.
2137 if (ShAmt >= BitWidth)
2140 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141 KnownZero <<= ShAmt;
2143 // low bits known zero.
2144 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2148 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2149 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2150 unsigned ShAmt = SA->getZExtValue();
2152 // If the shift count is an invalid immediate, don't do anything.
2153 if (ShAmt >= BitWidth)
2156 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2157 KnownZero = KnownZero.lshr(ShAmt);
2158 KnownOne = KnownOne.lshr(ShAmt);
2160 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2161 KnownZero |= HighBits; // High bits known zero.
2165 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2166 unsigned ShAmt = SA->getZExtValue();
2168 // If the shift count is an invalid immediate, don't do anything.
2169 if (ShAmt >= BitWidth)
2172 // If any of the demanded bits are produced by the sign extension, we also
2173 // demand the input sign bit.
2174 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2176 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2177 KnownZero = KnownZero.lshr(ShAmt);
2178 KnownOne = KnownOne.lshr(ShAmt);
2180 // Handle the sign bits.
2181 APInt SignBit = APInt::getSignBit(BitWidth);
2182 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2184 if (KnownZero.intersects(SignBit)) {
2185 KnownZero |= HighBits; // New bits are known zero.
2186 } else if (KnownOne.intersects(SignBit)) {
2187 KnownOne |= HighBits; // New bits are known one.
2191 case ISD::SIGN_EXTEND_INREG: {
2192 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2193 unsigned EBits = EVT.getScalarType().getSizeInBits();
2195 // Sign extension. Compute the demanded bits in the result that are not
2196 // present in the input.
2197 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2199 APInt InSignBit = APInt::getSignBit(EBits);
2200 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2202 // If the sign extended bits are demanded, we know that the sign
2204 InSignBit = InSignBit.zext(BitWidth);
2205 if (NewBits.getBoolValue())
2206 InputDemandedBits |= InSignBit;
2208 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2209 KnownOne &= InputDemandedBits;
2210 KnownZero &= InputDemandedBits;
2212 // If the sign bit of the input is known set or clear, then we know the
2213 // top bits of the result.
2214 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2215 KnownZero |= NewBits;
2216 KnownOne &= ~NewBits;
2217 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2218 KnownOne |= NewBits;
2219 KnownZero &= ~NewBits;
2220 } else { // Input sign bit unknown
2221 KnownZero &= ~NewBits;
2222 KnownOne &= ~NewBits;
2227 case ISD::CTTZ_ZERO_UNDEF:
2229 case ISD::CTLZ_ZERO_UNDEF:
2231 unsigned LowBits = Log2_32(BitWidth)+1;
2232 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2233 KnownOne.clearAllBits();
2237 LoadSDNode *LD = cast<LoadSDNode>(Op);
2238 // If this is a ZEXTLoad and we are looking at the loaded value.
2239 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2240 EVT VT = LD->getMemoryVT();
2241 unsigned MemBits = VT.getScalarType().getSizeInBits();
2242 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2243 } else if (const MDNode *Ranges = LD->getRanges()) {
2244 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2248 case ISD::ZERO_EXTEND: {
2249 EVT InVT = Op.getOperand(0).getValueType();
2250 unsigned InBits = InVT.getScalarType().getSizeInBits();
2251 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2252 KnownZero = KnownZero.trunc(InBits);
2253 KnownOne = KnownOne.trunc(InBits);
2254 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2255 KnownZero = KnownZero.zext(BitWidth);
2256 KnownOne = KnownOne.zext(BitWidth);
2257 KnownZero |= NewBits;
2260 case ISD::SIGN_EXTEND: {
2261 EVT InVT = Op.getOperand(0).getValueType();
2262 unsigned InBits = InVT.getScalarType().getSizeInBits();
2263 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2265 KnownZero = KnownZero.trunc(InBits);
2266 KnownOne = KnownOne.trunc(InBits);
2267 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2269 // Note if the sign bit is known to be zero or one.
2270 bool SignBitKnownZero = KnownZero.isNegative();
2271 bool SignBitKnownOne = KnownOne.isNegative();
2273 KnownZero = KnownZero.zext(BitWidth);
2274 KnownOne = KnownOne.zext(BitWidth);
2276 // If the sign bit is known zero or one, the top bits match.
2277 if (SignBitKnownZero)
2278 KnownZero |= NewBits;
2279 else if (SignBitKnownOne)
2280 KnownOne |= NewBits;
2283 case ISD::ANY_EXTEND: {
2284 EVT InVT = Op.getOperand(0).getValueType();
2285 unsigned InBits = InVT.getScalarType().getSizeInBits();
2286 KnownZero = KnownZero.trunc(InBits);
2287 KnownOne = KnownOne.trunc(InBits);
2288 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2289 KnownZero = KnownZero.zext(BitWidth);
2290 KnownOne = KnownOne.zext(BitWidth);
2293 case ISD::TRUNCATE: {
2294 EVT InVT = Op.getOperand(0).getValueType();
2295 unsigned InBits = InVT.getScalarType().getSizeInBits();
2296 KnownZero = KnownZero.zext(InBits);
2297 KnownOne = KnownOne.zext(InBits);
2298 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2299 KnownZero = KnownZero.trunc(BitWidth);
2300 KnownOne = KnownOne.trunc(BitWidth);
2303 case ISD::AssertZext: {
2304 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2305 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2306 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2307 KnownZero |= (~InMask);
2308 KnownOne &= (~KnownZero);
2312 // All bits are zero except the low bit.
2313 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2317 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2318 // We know that the top bits of C-X are clear if X contains less bits
2319 // than C (i.e. no wrap-around can happen). For example, 20-X is
2320 // positive if we can prove that X is >= 0 and < 16.
2321 if (CLHS->getAPIntValue().isNonNegative()) {
2322 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2323 // NLZ can't be BitWidth with no sign bit
2324 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2325 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2327 // If all of the MaskV bits are known to be zero, then we know the
2328 // output top bits are zero, because we now know that the output is
2330 if ((KnownZero2 & MaskV) == MaskV) {
2331 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2332 // Top bits known zero.
2333 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2341 // Output known-0 bits are known if clear or set in both the low clear bits
2342 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2343 // low 3 bits clear.
2344 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2345 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2347 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2348 KnownZeroOut = std::min(KnownZeroOut,
2349 KnownZero2.countTrailingOnes());
2351 if (Op.getOpcode() == ISD::ADD) {
2352 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2356 // With ADDE, a carry bit may be added in, so we can only use this
2357 // information if we know (at least) that the low two bits are clear. We
2358 // then return to the caller that the low bit is unknown but that other bits
2360 if (KnownZeroOut >= 2) // ADDE
2361 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2365 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2366 const APInt &RA = Rem->getAPIntValue().abs();
2367 if (RA.isPowerOf2()) {
2368 APInt LowBits = RA - 1;
2369 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2371 // The low bits of the first operand are unchanged by the srem.
2372 KnownZero = KnownZero2 & LowBits;
2373 KnownOne = KnownOne2 & LowBits;
2375 // If the first operand is non-negative or has all low bits zero, then
2376 // the upper bits are all zero.
2377 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2378 KnownZero |= ~LowBits;
2380 // If the first operand is negative and not all low bits are zero, then
2381 // the upper bits are all one.
2382 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2383 KnownOne |= ~LowBits;
2384 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2389 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2390 const APInt &RA = Rem->getAPIntValue();
2391 if (RA.isPowerOf2()) {
2392 APInt LowBits = (RA - 1);
2393 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2395 // The upper bits are all zero, the lower ones are unchanged.
2396 KnownZero = KnownZero2 | ~LowBits;
2397 KnownOne = KnownOne2 & LowBits;
2402 // Since the result is less than or equal to either operand, any leading
2403 // zero bits in either operand must also exist in the result.
2404 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2405 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2407 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2408 KnownZero2.countLeadingOnes());
2409 KnownOne.clearAllBits();
2410 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2413 case ISD::EXTRACT_ELEMENT: {
2414 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2415 const unsigned Index =
2416 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2417 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2419 // Remove low part of known bits mask
2420 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2421 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2423 // Remove high part of known bit mask
2424 KnownZero = KnownZero.trunc(BitWidth);
2425 KnownOne = KnownOne.trunc(BitWidth);
2428 case ISD::FrameIndex:
2429 case ISD::TargetFrameIndex:
2430 if (unsigned Align = InferPtrAlignment(Op)) {
2431 // The low bits are known zero if the pointer is aligned.
2432 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2438 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2441 case ISD::INTRINSIC_WO_CHAIN:
2442 case ISD::INTRINSIC_W_CHAIN:
2443 case ISD::INTRINSIC_VOID:
2444 // Allow the target to implement this method for its nodes.
2445 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2449 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2452 /// ComputeNumSignBits - Return the number of times the sign bit of the
2453 /// register is replicated into the other bits. We know that at least 1 bit
2454 /// is always equal to the sign bit (itself), but other cases can give us
2455 /// information. For example, immediately after an "SRA X, 2", we know that
2456 /// the top 3 bits are all equal to each other, so we return 3.
2457 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2458 EVT VT = Op.getValueType();
2459 assert(VT.isInteger() && "Invalid VT!");
2460 unsigned VTBits = VT.getScalarType().getSizeInBits();
2462 unsigned FirstAnswer = 1;
2465 return 1; // Limit search depth.
2467 switch (Op.getOpcode()) {
2469 case ISD::AssertSext:
2470 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2471 return VTBits-Tmp+1;
2472 case ISD::AssertZext:
2473 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2476 case ISD::Constant: {
2477 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2478 return Val.getNumSignBits();
2481 case ISD::SIGN_EXTEND:
2483 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2484 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2486 case ISD::SIGN_EXTEND_INREG:
2487 // Max of the input and what this extends.
2489 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2492 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2493 return std::max(Tmp, Tmp2);
2496 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2497 // SRA X, C -> adds C sign bits.
2498 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2499 Tmp += C->getZExtValue();
2500 if (Tmp > VTBits) Tmp = VTBits;
2504 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2505 // shl destroys sign bits.
2506 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2507 if (C->getZExtValue() >= VTBits || // Bad shift.
2508 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2509 return Tmp - C->getZExtValue();
2514 case ISD::XOR: // NOT is handled here.
2515 // Logical binary ops preserve the number of sign bits at the worst.
2516 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2518 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2519 FirstAnswer = std::min(Tmp, Tmp2);
2520 // We computed what we know about the sign bits as our first
2521 // answer. Now proceed to the generic code that uses
2522 // computeKnownBits, and pick whichever answer is better.
2527 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2528 if (Tmp == 1) return 1; // Early out.
2529 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2530 return std::min(Tmp, Tmp2);
2538 if (Op.getResNo() != 1)
2540 // The boolean result conforms to getBooleanContents. Fall through.
2541 // If setcc returns 0/-1, all bits are sign bits.
2542 // We know that we have an integer-based boolean since these operations
2543 // are only available for integer.
2544 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2545 TargetLowering::ZeroOrNegativeOneBooleanContent)
2549 // If setcc returns 0/-1, all bits are sign bits.
2550 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2551 TargetLowering::ZeroOrNegativeOneBooleanContent)
2556 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2557 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2559 // Handle rotate right by N like a rotate left by 32-N.
2560 if (Op.getOpcode() == ISD::ROTR)
2561 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2563 // If we aren't rotating out all of the known-in sign bits, return the
2564 // number that are left. This handles rotl(sext(x), 1) for example.
2565 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2566 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2570 // Add can have at most one carry bit. Thus we know that the output
2571 // is, at worst, one more bit than the inputs.
2572 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2573 if (Tmp == 1) return 1; // Early out.
2575 // Special case decrementing a value (ADD X, -1):
2576 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2577 if (CRHS->isAllOnesValue()) {
2578 APInt KnownZero, KnownOne;
2579 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2581 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2583 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2586 // If we are subtracting one from a positive number, there is no carry
2587 // out of the result.
2588 if (KnownZero.isNegative())
2592 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2593 if (Tmp2 == 1) return 1;
2594 return std::min(Tmp, Tmp2)-1;
2597 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2598 if (Tmp2 == 1) return 1;
2601 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2602 if (CLHS->isNullValue()) {
2603 APInt KnownZero, KnownOne;
2604 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2605 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2607 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2610 // If the input is known to be positive (the sign bit is known clear),
2611 // the output of the NEG has the same number of sign bits as the input.
2612 if (KnownZero.isNegative())
2615 // Otherwise, we treat this like a SUB.
2618 // Sub can have at most one carry bit. Thus we know that the output
2619 // is, at worst, one more bit than the inputs.
2620 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2621 if (Tmp == 1) return 1; // Early out.
2622 return std::min(Tmp, Tmp2)-1;
2624 // FIXME: it's tricky to do anything useful for this, but it is an important
2625 // case for targets like X86.
2627 case ISD::EXTRACT_ELEMENT: {
2628 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2629 const int BitWidth = Op.getValueType().getSizeInBits();
2631 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2633 // Get reverse index (starting from 1), Op1 value indexes elements from
2634 // little end. Sign starts at big end.
2635 const int rIndex = Items - 1 -
2636 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2638 // If the sign portion ends in our element the substraction gives correct
2639 // result. Otherwise it gives either negative or > bitwidth result
2640 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2644 // If we are looking at the loaded value of the SDNode.
2645 if (Op.getResNo() == 0) {
2646 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2647 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2648 unsigned ExtType = LD->getExtensionType();
2651 case ISD::SEXTLOAD: // '17' bits known
2652 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2653 return VTBits-Tmp+1;
2654 case ISD::ZEXTLOAD: // '16' bits known
2655 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2661 // Allow the target to implement this method for its nodes.
2662 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2663 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2664 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2665 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2666 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2667 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2670 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2671 // use this information.
2672 APInt KnownZero, KnownOne;
2673 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2676 if (KnownZero.isNegative()) { // sign bit is 0
2678 } else if (KnownOne.isNegative()) { // sign bit is 1;
2685 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2686 // the number of identical bits in the top of the input value.
2688 Mask <<= Mask.getBitWidth()-VTBits;
2689 // Return # leading zeros. We use 'min' here in case Val was zero before
2690 // shifting. We don't want to return '64' as for an i32 "0".
2691 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2694 /// isBaseWithConstantOffset - Return true if the specified operand is an
2695 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2696 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2697 /// semantics as an ADD. This handles the equivalence:
2698 /// X|Cst == X+Cst iff X&Cst = 0.
2699 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2700 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2701 !isa<ConstantSDNode>(Op.getOperand(1)))
2704 if (Op.getOpcode() == ISD::OR &&
2705 !MaskedValueIsZero(Op.getOperand(0),
2706 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2713 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2714 // If we're told that NaNs won't happen, assume they won't.
2715 if (getTarget().Options.NoNaNsFPMath)
2718 // If the value is a constant, we can obviously see if it is a NaN or not.
2719 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2720 return !C->getValueAPF().isNaN();
2722 // TODO: Recognize more cases here.
2727 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2728 // If the value is a constant, we can obviously see if it is a zero or not.
2729 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2730 return !C->isZero();
2732 // TODO: Recognize more cases here.
2733 switch (Op.getOpcode()) {
2736 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2737 return !C->isNullValue();
2744 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2745 // Check the obvious case.
2746 if (A == B) return true;
2748 // For for negative and positive zero.
2749 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2750 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2751 if (CA->isZero() && CB->isZero()) return true;
2753 // Otherwise they may not be equal.
2757 /// getNode - Gets or creates the specified node.
2759 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2760 FoldingSetNodeID ID;
2761 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2763 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2764 return SDValue(E, 0);
2766 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2767 DL.getDebugLoc(), getVTList(VT));
2768 CSEMap.InsertNode(N, IP);
2771 return SDValue(N, 0);
2774 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2775 EVT VT, SDValue Operand) {
2776 // Constant fold unary operations with an integer constant operand. Even
2777 // opaque constant will be folded, because the folding of unary operations
2778 // doesn't create new constants with different values. Nevertheless, the
2779 // opaque flag is preserved during folding to prevent future folding with
2781 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2782 const APInt &Val = C->getAPIntValue();
2785 case ISD::SIGN_EXTEND:
2786 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2787 C->isTargetOpcode(), C->isOpaque());
2788 case ISD::ANY_EXTEND:
2789 case ISD::ZERO_EXTEND:
2791 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2792 C->isTargetOpcode(), C->isOpaque());
2793 case ISD::UINT_TO_FP:
2794 case ISD::SINT_TO_FP: {
2795 APFloat apf(EVTToAPFloatSemantics(VT),
2796 APInt::getNullValue(VT.getSizeInBits()));
2797 (void)apf.convertFromAPInt(Val,
2798 Opcode==ISD::SINT_TO_FP,
2799 APFloat::rmNearestTiesToEven);
2800 return getConstantFP(apf, DL, VT);
2803 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2804 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2805 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2806 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2807 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2808 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2811 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2814 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2817 case ISD::CTLZ_ZERO_UNDEF:
2818 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2821 case ISD::CTTZ_ZERO_UNDEF:
2822 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2827 // Constant fold unary operations with a floating point constant operand.
2828 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2829 APFloat V = C->getValueAPF(); // make copy
2833 return getConstantFP(V, DL, VT);
2836 return getConstantFP(V, DL, VT);
2838 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2839 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2840 return getConstantFP(V, DL, VT);
2844 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2845 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2846 return getConstantFP(V, DL, VT);
2850 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2851 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2852 return getConstantFP(V, DL, VT);
2855 case ISD::FP_EXTEND: {
2857 // This can return overflow, underflow, or inexact; we don't care.
2858 // FIXME need to be more flexible about rounding mode.
2859 (void)V.convert(EVTToAPFloatSemantics(VT),
2860 APFloat::rmNearestTiesToEven, &ignored);
2861 return getConstantFP(V, DL, VT);
2863 case ISD::FP_TO_SINT:
2864 case ISD::FP_TO_UINT: {
2867 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2868 // FIXME need to be more flexible about rounding mode.
2869 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2870 Opcode==ISD::FP_TO_SINT,
2871 APFloat::rmTowardZero, &ignored);
2872 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2874 APInt api(VT.getSizeInBits(), x);
2875 return getConstant(api, DL, VT);
2878 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2879 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2880 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2881 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2882 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2883 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2888 // Constant fold unary operations with a vector integer or float operand.
2889 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2890 if (BV->isConstant()) {
2893 // FIXME: Entirely reasonable to perform folding of other unary
2894 // operations here as the need arises.
2901 case ISD::FP_EXTEND:
2902 case ISD::FP_TO_SINT:
2903 case ISD::FP_TO_UINT:
2905 case ISD::UINT_TO_FP:
2906 case ISD::SINT_TO_FP: {
2907 EVT SVT = VT.getScalarType();
2908 EVT InVT = BV->getValueType(0);
2909 EVT InSVT = InVT.getScalarType();
2911 // Find legal integer scalar type for constant promotion and
2912 // ensure that its scalar size is at least as large as source.
2914 if (SVT.isInteger()) {
2915 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2916 if (LegalSVT.bitsLT(SVT)) break;
2919 // Let the above scalar folding handle the folding of each element.
2920 SmallVector<SDValue, 8> Ops;
2921 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2922 SDValue OpN = BV->getOperand(i);
2923 EVT OpVT = OpN.getValueType();
2925 // Build vector (integer) scalar operands may need implicit
2926 // truncation - do this before constant folding.
2927 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2928 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2930 OpN = getNode(Opcode, DL, SVT, OpN);
2932 // Legalize the (integer) scalar constant if necessary.
2933 if (LegalSVT != SVT)
2934 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2936 if (OpN.getOpcode() != ISD::UNDEF &&
2937 OpN.getOpcode() != ISD::Constant &&
2938 OpN.getOpcode() != ISD::ConstantFP)
2942 if (Ops.size() == VT.getVectorNumElements())
2943 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2950 unsigned OpOpcode = Operand.getNode()->getOpcode();
2952 case ISD::TokenFactor:
2953 case ISD::MERGE_VALUES:
2954 case ISD::CONCAT_VECTORS:
2955 return Operand; // Factor, merge or concat of one node? No need.
2956 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2957 case ISD::FP_EXTEND:
2958 assert(VT.isFloatingPoint() &&
2959 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2960 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2961 assert((!VT.isVector() ||
2962 VT.getVectorNumElements() ==
2963 Operand.getValueType().getVectorNumElements()) &&
2964 "Vector element count mismatch!");
2965 if (Operand.getOpcode() == ISD::UNDEF)
2966 return getUNDEF(VT);
2968 case ISD::SIGN_EXTEND:
2969 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2970 "Invalid SIGN_EXTEND!");
2971 if (Operand.getValueType() == VT) return Operand; // noop extension
2972 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2973 "Invalid sext node, dst < src!");
2974 assert((!VT.isVector() ||
2975 VT.getVectorNumElements() ==
2976 Operand.getValueType().getVectorNumElements()) &&
2977 "Vector element count mismatch!");
2978 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2979 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2980 else if (OpOpcode == ISD::UNDEF)
2981 // sext(undef) = 0, because the top bits will all be the same.
2982 return getConstant(0, DL, VT);
2984 case ISD::ZERO_EXTEND:
2985 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2986 "Invalid ZERO_EXTEND!");
2987 if (Operand.getValueType() == VT) return Operand; // noop extension
2988 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2989 "Invalid zext node, dst < src!");
2990 assert((!VT.isVector() ||
2991 VT.getVectorNumElements() ==
2992 Operand.getValueType().getVectorNumElements()) &&
2993 "Vector element count mismatch!");
2994 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2995 return getNode(ISD::ZERO_EXTEND, DL, VT,
2996 Operand.getNode()->getOperand(0));
2997 else if (OpOpcode == ISD::UNDEF)
2998 // zext(undef) = 0, because the top bits will be zero.
2999 return getConstant(0, DL, VT);
3001 case ISD::ANY_EXTEND:
3002 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3003 "Invalid ANY_EXTEND!");
3004 if (Operand.getValueType() == VT) return Operand; // noop extension
3005 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3006 "Invalid anyext node, dst < src!");
3007 assert((!VT.isVector() ||
3008 VT.getVectorNumElements() ==
3009 Operand.getValueType().getVectorNumElements()) &&
3010 "Vector element count mismatch!");
3012 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3013 OpOpcode == ISD::ANY_EXTEND)
3014 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3015 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3016 else if (OpOpcode == ISD::UNDEF)
3017 return getUNDEF(VT);
3019 // (ext (trunx x)) -> x
3020 if (OpOpcode == ISD::TRUNCATE) {
3021 SDValue OpOp = Operand.getNode()->getOperand(0);
3022 if (OpOp.getValueType() == VT)
3027 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3028 "Invalid TRUNCATE!");
3029 if (Operand.getValueType() == VT) return Operand; // noop truncate
3030 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3031 "Invalid truncate node, src < dst!");
3032 assert((!VT.isVector() ||
3033 VT.getVectorNumElements() ==
3034 Operand.getValueType().getVectorNumElements()) &&
3035 "Vector element count mismatch!");
3036 if (OpOpcode == ISD::TRUNCATE)
3037 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3038 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3039 OpOpcode == ISD::ANY_EXTEND) {
3040 // If the source is smaller than the dest, we still need an extend.
3041 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3042 .bitsLT(VT.getScalarType()))
3043 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3044 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3045 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3046 return Operand.getNode()->getOperand(0);
3048 if (OpOpcode == ISD::UNDEF)
3049 return getUNDEF(VT);
3052 // Basic sanity checking.
3053 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3054 && "Cannot BITCAST between types of different sizes!");
3055 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3056 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3057 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3058 if (OpOpcode == ISD::UNDEF)
3059 return getUNDEF(VT);
3061 case ISD::SCALAR_TO_VECTOR:
3062 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3063 (VT.getVectorElementType() == Operand.getValueType() ||
3064 (VT.getVectorElementType().isInteger() &&
3065 Operand.getValueType().isInteger() &&
3066 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3067 "Illegal SCALAR_TO_VECTOR node!");
3068 if (OpOpcode == ISD::UNDEF)
3069 return getUNDEF(VT);
3070 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3071 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3072 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3073 Operand.getConstantOperandVal(1) == 0 &&
3074 Operand.getOperand(0).getValueType() == VT)
3075 return Operand.getOperand(0);
3078 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3079 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3080 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3081 Operand.getNode()->getOperand(0));
3082 if (OpOpcode == ISD::FNEG) // --X -> X
3083 return Operand.getNode()->getOperand(0);
3086 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3087 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3092 SDVTList VTs = getVTList(VT);
3093 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3094 FoldingSetNodeID ID;
3095 SDValue Ops[1] = { Operand };
3096 AddNodeIDNode(ID, Opcode, VTs, Ops);
3098 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3099 return SDValue(E, 0);
3101 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3102 DL.getDebugLoc(), VTs, Operand);
3103 CSEMap.InsertNode(N, IP);
3105 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3106 DL.getDebugLoc(), VTs, Operand);
3110 return SDValue(N, 0);
3113 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3116 case ISD::ADD: return std::make_pair(C1 + C2, true);
3117 case ISD::SUB: return std::make_pair(C1 - C2, true);
3118 case ISD::MUL: return std::make_pair(C1 * C2, true);
3119 case ISD::AND: return std::make_pair(C1 & C2, true);
3120 case ISD::OR: return std::make_pair(C1 | C2, true);
3121 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3122 case ISD::SHL: return std::make_pair(C1 << C2, true);
3123 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3124 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3125 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3126 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3128 if (!C2.getBoolValue())
3130 return std::make_pair(C1.udiv(C2), true);
3132 if (!C2.getBoolValue())
3134 return std::make_pair(C1.urem(C2), true);
3136 if (!C2.getBoolValue())
3138 return std::make_pair(C1.sdiv(C2), true);
3140 if (!C2.getBoolValue())
3142 return std::make_pair(C1.srem(C2), true);
3144 return std::make_pair(APInt(1, 0), false);
3147 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3148 const ConstantSDNode *Cst1,
3149 const ConstantSDNode *Cst2) {
3150 if (Cst1->isOpaque() || Cst2->isOpaque())
3153 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3154 Cst2->getAPIntValue());
3157 return getConstant(Folded.first, DL, VT);
3160 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3161 SDNode *Cst1, SDNode *Cst2) {
3162 // If the opcode is a target-specific ISD node, there's nothing we can
3163 // do here and the operand rules may not line up with the below, so
3165 if (Opcode >= ISD::BUILTIN_OP_END)
3168 // Handle the case of two scalars.
3169 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3170 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3171 if (SDValue Folded =
3172 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3175 SmallVector<SDValue, 4> Outputs;
3176 // We may have a vector type but a scalar result. Create a splat.
3177 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3178 // Build a big vector out of the scalar elements we generated.
3179 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3186 // For vectors extract each constant element into Inputs so we can constant
3187 // fold them individually.
3188 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3189 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3193 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3195 EVT SVT = VT.getScalarType();
3196 SmallVector<SDValue, 4> Outputs;
3197 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3198 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3199 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3200 if (!V1 || !V2) // Not a constant, bail.
3203 if (V1->isOpaque() || V2->isOpaque())
3206 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3207 // FIXME: This is valid and could be handled by truncating the APInts.
3208 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3211 // Fold one vector element.
3212 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3213 V2->getAPIntValue());
3216 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3219 assert(VT.getVectorNumElements() == Outputs.size() &&
3220 "Vector size mismatch!");
3222 // We may have a vector type but a scalar result. Create a splat.
3223 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3225 // Build a big vector out of the scalar elements we generated.
3226 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3229 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3230 SDValue N2, bool nuw, bool nsw, bool exact) {
3231 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3232 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3235 case ISD::TokenFactor:
3236 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3237 N2.getValueType() == MVT::Other && "Invalid token factor!");
3238 // Fold trivial token factors.
3239 if (N1.getOpcode() == ISD::EntryToken) return N2;
3240 if (N2.getOpcode() == ISD::EntryToken) return N1;
3241 if (N1 == N2) return N1;
3243 case ISD::CONCAT_VECTORS:
3244 // Concat of UNDEFs is UNDEF.
3245 if (N1.getOpcode() == ISD::UNDEF &&
3246 N2.getOpcode() == ISD::UNDEF)
3247 return getUNDEF(VT);
3249 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3250 // one big BUILD_VECTOR.
3251 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3252 N2.getOpcode() == ISD::BUILD_VECTOR) {
3253 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3254 N1.getNode()->op_end());
3255 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3257 // BUILD_VECTOR requires all inputs to be of the same type, find the
3258 // maximum type and extend them all.
3259 EVT SVT = VT.getScalarType();
3260 for (SDValue Op : Elts)
3261 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3262 if (SVT.bitsGT(VT.getScalarType()))
3263 for (SDValue &Op : Elts)
3264 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3265 ? getZExtOrTrunc(Op, DL, SVT)
3266 : getSExtOrTrunc(Op, DL, SVT);
3268 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3272 assert(VT.isInteger() && "This operator does not apply to FP types!");
3273 assert(N1.getValueType() == N2.getValueType() &&
3274 N1.getValueType() == VT && "Binary operator types must match!");
3275 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3276 // worth handling here.
3277 if (N2C && N2C->isNullValue())
3279 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3286 assert(VT.isInteger() && "This operator does not apply to FP types!");
3287 assert(N1.getValueType() == N2.getValueType() &&
3288 N1.getValueType() == VT && "Binary operator types must match!");
3289 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3290 // it's worth handling here.
3291 if (N2C && N2C->isNullValue())
3301 assert(VT.isInteger() && "This operator does not apply to FP types!");
3302 assert(N1.getValueType() == N2.getValueType() &&
3303 N1.getValueType() == VT && "Binary operator types must match!");
3310 if (getTarget().Options.UnsafeFPMath) {
3311 if (Opcode == ISD::FADD) {
3313 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3314 if (CFP->getValueAPF().isZero())
3317 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3318 if (CFP->getValueAPF().isZero())
3320 } else if (Opcode == ISD::FSUB) {
3322 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3323 if (CFP->getValueAPF().isZero())
3325 } else if (Opcode == ISD::FMUL) {
3326 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3329 // If the first operand isn't the constant, try the second
3331 CFP = dyn_cast<ConstantFPSDNode>(N2);
3338 return SDValue(CFP,0);
3340 if (CFP->isExactlyValue(1.0))
3345 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3346 assert(N1.getValueType() == N2.getValueType() &&
3347 N1.getValueType() == VT && "Binary operator types must match!");
3349 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3350 assert(N1.getValueType() == VT &&
3351 N1.getValueType().isFloatingPoint() &&
3352 N2.getValueType().isFloatingPoint() &&
3353 "Invalid FCOPYSIGN!");
3360 assert(VT == N1.getValueType() &&
3361 "Shift operators return type must be the same as their first arg");
3362 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3363 "Shifts only work on integers");
3364 assert((!VT.isVector() || VT == N2.getValueType()) &&
3365 "Vector shift amounts must be in the same as their first arg");
3366 // Verify that the shift amount VT is bit enough to hold valid shift
3367 // amounts. This catches things like trying to shift an i1024 value by an
3368 // i8, which is easy to fall into in generic code that uses
3369 // TLI.getShiftAmount().
3370 assert(N2.getValueType().getSizeInBits() >=
3371 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3372 "Invalid use of small shift amount with oversized value!");
3374 // Always fold shifts of i1 values so the code generator doesn't need to
3375 // handle them. Since we know the size of the shift has to be less than the
3376 // size of the value, the shift/rotate count is guaranteed to be zero.
3379 if (N2C && N2C->isNullValue())
3382 case ISD::FP_ROUND_INREG: {
3383 EVT EVT = cast<VTSDNode>(N2)->getVT();
3384 assert(VT == N1.getValueType() && "Not an inreg round!");
3385 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3386 "Cannot FP_ROUND_INREG integer types");
3387 assert(EVT.isVector() == VT.isVector() &&
3388 "FP_ROUND_INREG type should be vector iff the operand "
3390 assert((!EVT.isVector() ||
3391 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3392 "Vector element counts must match in FP_ROUND_INREG");
3393 assert(EVT.bitsLE(VT) && "Not rounding down!");
3395 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3399 assert(VT.isFloatingPoint() &&
3400 N1.getValueType().isFloatingPoint() &&
3401 VT.bitsLE(N1.getValueType()) &&
3402 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3403 if (N1.getValueType() == VT) return N1; // noop conversion.
3405 case ISD::AssertSext:
3406 case ISD::AssertZext: {
3407 EVT EVT = cast<VTSDNode>(N2)->getVT();
3408 assert(VT == N1.getValueType() && "Not an inreg extend!");
3409 assert(VT.isInteger() && EVT.isInteger() &&
3410 "Cannot *_EXTEND_INREG FP types");
3411 assert(!EVT.isVector() &&
3412 "AssertSExt/AssertZExt type should be the vector element type "
3413 "rather than the vector type!");
3414 assert(EVT.bitsLE(VT) && "Not extending!");
3415 if (VT == EVT) return N1; // noop assertion.
3418 case ISD::SIGN_EXTEND_INREG: {
3419 EVT EVT = cast<VTSDNode>(N2)->getVT();
3420 assert(VT == N1.getValueType() && "Not an inreg extend!");
3421 assert(VT.isInteger() && EVT.isInteger() &&
3422 "Cannot *_EXTEND_INREG FP types");
3423 assert(EVT.isVector() == VT.isVector() &&
3424 "SIGN_EXTEND_INREG type should be vector iff the operand "
3426 assert((!EVT.isVector() ||
3427 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3428 "Vector element counts must match in SIGN_EXTEND_INREG");
3429 assert(EVT.bitsLE(VT) && "Not extending!");
3430 if (EVT == VT) return N1; // Not actually extending
3433 APInt Val = N1C->getAPIntValue();
3434 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3435 Val <<= Val.getBitWidth()-FromBits;
3436 Val = Val.ashr(Val.getBitWidth()-FromBits);
3437 return getConstant(Val, DL, VT);
3441 case ISD::EXTRACT_VECTOR_ELT:
3442 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3443 if (N1.getOpcode() == ISD::UNDEF)
3444 return getUNDEF(VT);
3446 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3447 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3448 return getUNDEF(VT);
3450 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3451 // expanding copies of large vectors from registers.
3453 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3454 N1.getNumOperands() > 0) {
3456 N1.getOperand(0).getValueType().getVectorNumElements();
3457 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3458 N1.getOperand(N2C->getZExtValue() / Factor),
3459 getConstant(N2C->getZExtValue() % Factor, DL,
3460 N2.getValueType()));
3463 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3464 // expanding large vector constants.
3465 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3466 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3468 if (VT != Elt.getValueType())
3469 // If the vector element type is not legal, the BUILD_VECTOR operands
3470 // are promoted and implicitly truncated, and the result implicitly
3471 // extended. Make that explicit here.
3472 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3477 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3478 // operations are lowered to scalars.
3479 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3480 // If the indices are the same, return the inserted element else
3481 // if the indices are known different, extract the element from
3482 // the original vector.
3483 SDValue N1Op2 = N1.getOperand(2);
3484 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3486 if (N1Op2C && N2C) {
3487 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3488 if (VT == N1.getOperand(1).getValueType())
3489 return N1.getOperand(1);
3491 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3494 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3498 case ISD::EXTRACT_ELEMENT:
3499 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3500 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3501 (N1.getValueType().isInteger() == VT.isInteger()) &&
3502 N1.getValueType() != VT &&
3503 "Wrong types for EXTRACT_ELEMENT!");
3505 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3506 // 64-bit integers into 32-bit parts. Instead of building the extract of
3507 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3508 if (N1.getOpcode() == ISD::BUILD_PAIR)
3509 return N1.getOperand(N2C->getZExtValue());
3511 // EXTRACT_ELEMENT of a constant int is also very common.
3512 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3513 unsigned ElementSize = VT.getSizeInBits();
3514 unsigned Shift = ElementSize * N2C->getZExtValue();
3515 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3516 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3519 case ISD::EXTRACT_SUBVECTOR: {
3521 if (VT.isSimple() && N1.getValueType().isSimple()) {
3522 assert(VT.isVector() && N1.getValueType().isVector() &&
3523 "Extract subvector VTs must be a vectors!");
3524 assert(VT.getVectorElementType() ==
3525 N1.getValueType().getVectorElementType() &&
3526 "Extract subvector VTs must have the same element type!");
3527 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3528 "Extract subvector must be from larger vector to smaller vector!");
3530 if (isa<ConstantSDNode>(Index.getNode())) {
3531 assert((VT.getVectorNumElements() +
3532 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3533 <= N1.getValueType().getVectorNumElements())
3534 && "Extract subvector overflow!");
3537 // Trivial extraction.
3538 if (VT.getSimpleVT() == N1.getSimpleValueType())
3545 // Perform trivial constant folding.
3547 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3550 // Canonicalize constant to RHS if commutative.
3551 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3552 std::swap(N1C, N2C);
3556 // Constant fold FP operations.
3557 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3558 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3559 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3561 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3562 // Canonicalize constant to RHS if commutative.
3563 std::swap(N1CFP, N2CFP);
3566 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3567 APFloat::opStatus s;
3570 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3571 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3572 return getConstantFP(V1, DL, VT);
3575 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3576 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3577 return getConstantFP(V1, DL, VT);
3580 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3581 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3582 return getConstantFP(V1, DL, VT);
3585 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3586 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3587 s!=APFloat::opDivByZero)) {
3588 return getConstantFP(V1, DL, VT);
3592 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3593 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3594 s!=APFloat::opDivByZero)) {
3595 return getConstantFP(V1, DL, VT);
3598 case ISD::FCOPYSIGN:
3600 return getConstantFP(V1, DL, VT);
3605 if (Opcode == ISD::FP_ROUND) {
3606 APFloat V = N1CFP->getValueAPF(); // make copy
3608 // This can return overflow, underflow, or inexact; we don't care.
3609 // FIXME need to be more flexible about rounding mode.
3610 (void)V.convert(EVTToAPFloatSemantics(VT),
3611 APFloat::rmNearestTiesToEven, &ignored);
3612 return getConstantFP(V, DL, VT);
3616 // Canonicalize an UNDEF to the RHS, even over a constant.
3617 if (N1.getOpcode() == ISD::UNDEF) {
3618 if (isCommutativeBinOp(Opcode)) {
3622 case ISD::FP_ROUND_INREG:
3623 case ISD::SIGN_EXTEND_INREG:
3629 return N1; // fold op(undef, arg2) -> undef
3637 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3638 // For vectors, we can't easily build an all zero vector, just return
3645 // Fold a bunch of operators when the RHS is undef.
3646 if (N2.getOpcode() == ISD::UNDEF) {
3649 if (N1.getOpcode() == ISD::UNDEF)
3650 // Handle undef ^ undef -> 0 special case. This is a common
3652 return getConstant(0, DL, VT);
3662 return N2; // fold op(arg1, undef) -> undef
3668 if (getTarget().Options.UnsafeFPMath)
3676 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3677 // For vectors, we can't easily build an all zero vector, just return
3682 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3683 // For vectors, we can't easily build an all one vector, just return
3691 // Memoize this node if possible.
3693 SDVTList VTs = getVTList(VT);
3694 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3695 if (VT != MVT::Glue) {
3696 SDValue Ops[] = {N1, N2};
3697 FoldingSetNodeID ID;
3698 AddNodeIDNode(ID, Opcode, VTs, Ops);
3700 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3702 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3703 return SDValue(E, 0);
3705 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3707 CSEMap.InsertNode(N, IP);
3709 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3713 return SDValue(N, 0);
3716 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3717 SDValue N1, SDValue N2, SDValue N3) {
3718 // Perform various simplifications.
3719 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3722 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3723 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3724 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3725 if (N1CFP && N2CFP && N3CFP) {
3726 APFloat V1 = N1CFP->getValueAPF();
3727 const APFloat &V2 = N2CFP->getValueAPF();
3728 const APFloat &V3 = N3CFP->getValueAPF();
3729 APFloat::opStatus s =
3730 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3731 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3732 return getConstantFP(V1, DL, VT);
3736 case ISD::CONCAT_VECTORS:
3737 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3738 // one big BUILD_VECTOR.
3739 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3740 N2.getOpcode() == ISD::BUILD_VECTOR &&
3741 N3.getOpcode() == ISD::BUILD_VECTOR) {
3742 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3743 N1.getNode()->op_end());
3744 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3745 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3746 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3750 // Use FoldSetCC to simplify SETCC's.
3751 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3752 if (Simp.getNode()) return Simp;
3757 if (N1C->getZExtValue())
3758 return N2; // select true, X, Y -> X
3759 return N3; // select false, X, Y -> Y
3762 if (N2 == N3) return N2; // select C, X, X -> X
3764 case ISD::VECTOR_SHUFFLE:
3765 llvm_unreachable("should use getVectorShuffle constructor!");
3766 case ISD::INSERT_SUBVECTOR: {
3768 if (VT.isSimple() && N1.getValueType().isSimple()
3769 && N2.getValueType().isSimple()) {
3770 assert(VT.isVector() && N1.getValueType().isVector() &&
3771 N2.getValueType().isVector() &&
3772 "Insert subvector VTs must be a vectors");
3773 assert(VT == N1.getValueType() &&
3774 "Dest and insert subvector source types must match!");
3775 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3776 "Insert subvector must be from smaller vector to larger vector!");
3777 if (isa<ConstantSDNode>(Index.getNode())) {
3778 assert((N2.getValueType().getVectorNumElements() +
3779 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3780 <= VT.getVectorNumElements())
3781 && "Insert subvector overflow!");
3784 // Trivial insertion.
3785 if (VT.getSimpleVT() == N2.getSimpleValueType())
3791 // Fold bit_convert nodes from a type to themselves.
3792 if (N1.getValueType() == VT)
3797 // Memoize node if it doesn't produce a flag.
3799 SDVTList VTs = getVTList(VT);
3800 if (VT != MVT::Glue) {
3801 SDValue Ops[] = { N1, N2, N3 };
3802 FoldingSetNodeID ID;
3803 AddNodeIDNode(ID, Opcode, VTs, Ops);
3805 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3806 return SDValue(E, 0);
3808 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3809 DL.getDebugLoc(), VTs, N1, N2, N3);
3810 CSEMap.InsertNode(N, IP);
3812 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3813 DL.getDebugLoc(), VTs, N1, N2, N3);
3817 return SDValue(N, 0);
3820 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3821 SDValue N1, SDValue N2, SDValue N3,
3823 SDValue Ops[] = { N1, N2, N3, N4 };
3824 return getNode(Opcode, DL, VT, Ops);
3827 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3828 SDValue N1, SDValue N2, SDValue N3,
3829 SDValue N4, SDValue N5) {
3830 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3831 return getNode(Opcode, DL, VT, Ops);
3834 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3835 /// the incoming stack arguments to be loaded from the stack.
3836 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3837 SmallVector<SDValue, 8> ArgChains;
3839 // Include the original chain at the beginning of the list. When this is
3840 // used by target LowerCall hooks, this helps legalize find the
3841 // CALLSEQ_BEGIN node.
3842 ArgChains.push_back(Chain);
3844 // Add a chain value for each stack argument.
3845 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3846 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3847 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3848 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3849 if (FI->getIndex() < 0)
3850 ArgChains.push_back(SDValue(L, 1));
3852 // Build a tokenfactor for all the chains.
3853 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3856 /// getMemsetValue - Vectorized representation of the memset value
3858 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3860 assert(Value.getOpcode() != ISD::UNDEF);
3862 unsigned NumBits = VT.getScalarType().getSizeInBits();
3863 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3864 assert(C->getAPIntValue().getBitWidth() == 8);
3865 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3867 return DAG.getConstant(Val, dl, VT);
3868 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3872 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3873 EVT IntVT = VT.getScalarType();
3874 if (!IntVT.isInteger())
3875 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3877 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3879 // Use a multiplication with 0x010101... to extend the input to the
3881 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3882 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3883 DAG.getConstant(Magic, dl, IntVT));
3886 if (VT != Value.getValueType() && !VT.isInteger())
3887 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3888 if (VT != Value.getValueType()) {
3889 assert(VT.getVectorElementType() == Value.getValueType() &&
3890 "value type should be one vector element here");
3891 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3892 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3898 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3899 /// used when a memcpy is turned into a memset when the source is a constant
3901 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3902 const TargetLowering &TLI, StringRef Str) {
3903 // Handle vector with all elements zero.
3906 return DAG.getConstant(0, dl, VT);
3907 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3908 return DAG.getConstantFP(0.0, dl, VT);
3909 else if (VT.isVector()) {
3910 unsigned NumElts = VT.getVectorNumElements();
3911 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3912 return DAG.getNode(ISD::BITCAST, dl, VT,
3913 DAG.getConstant(0, dl,
3914 EVT::getVectorVT(*DAG.getContext(),
3917 llvm_unreachable("Expected type!");
3920 assert(!VT.isVector() && "Can't handle vector type here!");
3921 unsigned NumVTBits = VT.getSizeInBits();
3922 unsigned NumVTBytes = NumVTBits / 8;
3923 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3925 APInt Val(NumVTBits, 0);
3926 if (TLI.isLittleEndian()) {
3927 for (unsigned i = 0; i != NumBytes; ++i)
3928 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3930 for (unsigned i = 0; i != NumBytes; ++i)
3931 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3934 // If the "cost" of materializing the integer immediate is less than the cost
3935 // of a load, then it is cost effective to turn the load into the immediate.
3936 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3937 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3938 return DAG.getConstant(Val, dl, VT);
3939 return SDValue(nullptr, 0);
3942 /// getMemBasePlusOffset - Returns base and offset node for the
3944 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3945 SelectionDAG &DAG) {
3946 EVT VT = Base.getValueType();
3947 return DAG.getNode(ISD::ADD, dl,
3948 VT, Base, DAG.getConstant(Offset, dl, VT));
3951 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3953 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3954 unsigned SrcDelta = 0;
3955 GlobalAddressSDNode *G = nullptr;
3956 if (Src.getOpcode() == ISD::GlobalAddress)
3957 G = cast<GlobalAddressSDNode>(Src);
3958 else if (Src.getOpcode() == ISD::ADD &&
3959 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3960 Src.getOperand(1).getOpcode() == ISD::Constant) {
3961 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3962 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3967 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3970 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3971 /// to replace the memset / memcpy. Return true if the number of memory ops
3972 /// is below the threshold. It returns the types of the sequence of
3973 /// memory ops to perform memset / memcpy by reference.
3974 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3975 unsigned Limit, uint64_t Size,
3976 unsigned DstAlign, unsigned SrcAlign,
3982 const TargetLowering &TLI) {
3983 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3984 "Expecting memcpy / memset source to meet alignment requirement!");
3985 // If 'SrcAlign' is zero, that means the memory operation does not need to
3986 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3987 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3988 // is the specified alignment of the memory operation. If it is zero, that
3989 // means it's possible to change the alignment of the destination.
3990 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3991 // not need to be loaded.
3992 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3993 IsMemset, ZeroMemset, MemcpyStrSrc,
3994 DAG.getMachineFunction());
3996 if (VT == MVT::Other) {
3998 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3999 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4000 VT = TLI.getPointerTy();
4002 switch (DstAlign & 7) {
4003 case 0: VT = MVT::i64; break;
4004 case 4: VT = MVT::i32; break;
4005 case 2: VT = MVT::i16; break;
4006 default: VT = MVT::i8; break;
4011 while (!TLI.isTypeLegal(LVT))
4012 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4013 assert(LVT.isInteger());
4019 unsigned NumMemOps = 0;
4021 unsigned VTSize = VT.getSizeInBits() / 8;
4022 while (VTSize > Size) {
4023 // For now, only use non-vector load / store's for the left-over pieces.
4028 if (VT.isVector() || VT.isFloatingPoint()) {
4029 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4030 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4031 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4033 else if (NewVT == MVT::i64 &&
4034 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4035 TLI.isSafeMemOpType(MVT::f64)) {
4036 // i64 is usually not legal on 32-bit targets, but f64 may be.
4044 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4045 if (NewVT == MVT::i8)
4047 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4049 NewVTSize = NewVT.getSizeInBits() / 8;
4051 // If the new VT cannot cover all of the remaining bits, then consider
4052 // issuing a (or a pair of) unaligned and overlapping load / store.
4053 // FIXME: Only does this for 64-bit or more since we don't have proper
4054 // cost model for unaligned load / store.
4057 if (NumMemOps && AllowOverlap &&
4058 VTSize >= 8 && NewVTSize < Size &&
4059 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4067 if (++NumMemOps > Limit)
4070 MemOps.push_back(VT);
4077 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4078 SDValue Chain, SDValue Dst,
4079 SDValue Src, uint64_t Size,
4080 unsigned Align, bool isVol,
4082 MachinePointerInfo DstPtrInfo,
4083 MachinePointerInfo SrcPtrInfo) {
4084 // Turn a memcpy of undef to nop.
4085 if (Src.getOpcode() == ISD::UNDEF)
4088 // Expand memcpy to a series of load and store ops if the size operand falls
4089 // below a certain threshold.
4090 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4091 // rather than maybe a humongous number of loads and stores.
4092 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4093 std::vector<EVT> MemOps;
4094 bool DstAlignCanChange = false;
4095 MachineFunction &MF = DAG.getMachineFunction();
4096 MachineFrameInfo *MFI = MF.getFrameInfo();
4097 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4098 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4099 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4100 DstAlignCanChange = true;
4101 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4102 if (Align > SrcAlign)
4105 bool CopyFromStr = isMemSrcFromString(Src, Str);
4106 bool isZeroStr = CopyFromStr && Str.empty();
4107 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4109 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4110 (DstAlignCanChange ? 0 : Align),
4111 (isZeroStr ? 0 : SrcAlign),
4112 false, false, CopyFromStr, true, DAG, TLI))
4115 if (DstAlignCanChange) {
4116 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4117 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4119 // Don't promote to an alignment that would require dynamic stack
4121 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4122 if (!TRI->needsStackRealignment(MF))
4123 while (NewAlign > Align &&
4124 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4127 if (NewAlign > Align) {
4128 // Give the stack frame object a larger alignment if needed.
4129 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4130 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4135 SmallVector<SDValue, 8> OutChains;
4136 unsigned NumMemOps = MemOps.size();
4137 uint64_t SrcOff = 0, DstOff = 0;
4138 for (unsigned i = 0; i != NumMemOps; ++i) {
4140 unsigned VTSize = VT.getSizeInBits() / 8;
4141 SDValue Value, Store;
4143 if (VTSize > Size) {
4144 // Issuing an unaligned load / store pair that overlaps with the previous
4145 // pair. Adjust the offset accordingly.
4146 assert(i == NumMemOps-1 && i != 0);
4147 SrcOff -= VTSize - Size;
4148 DstOff -= VTSize - Size;
4152 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4153 // It's unlikely a store of a vector immediate can be done in a single
4154 // instruction. It would require a load from a constantpool first.
4155 // We only handle zero vectors here.
4156 // FIXME: Handle other cases where store of vector immediate is done in
4157 // a single instruction.
4158 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4159 if (Value.getNode())
4160 Store = DAG.getStore(Chain, dl, Value,
4161 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4162 DstPtrInfo.getWithOffset(DstOff), isVol,
4166 if (!Store.getNode()) {
4167 // The type might not be legal for the target. This should only happen
4168 // if the type is smaller than a legal type, as on PPC, so the right
4169 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4170 // to Load/Store if NVT==VT.
4171 // FIXME does the case above also need this?
4172 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4173 assert(NVT.bitsGE(VT));
4174 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4175 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4176 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4177 false, MinAlign(SrcAlign, SrcOff));
4178 Store = DAG.getTruncStore(Chain, dl, Value,
4179 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4180 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4183 OutChains.push_back(Store);
4189 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4192 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4193 SDValue Chain, SDValue Dst,
4194 SDValue Src, uint64_t Size,
4195 unsigned Align, bool isVol,
4197 MachinePointerInfo DstPtrInfo,
4198 MachinePointerInfo SrcPtrInfo) {
4199 // Turn a memmove of undef to nop.
4200 if (Src.getOpcode() == ISD::UNDEF)
4203 // Expand memmove to a series of load and store ops if the size operand falls
4204 // below a certain threshold.
4205 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4206 std::vector<EVT> MemOps;
4207 bool DstAlignCanChange = false;
4208 MachineFunction &MF = DAG.getMachineFunction();
4209 MachineFrameInfo *MFI = MF.getFrameInfo();
4210 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4211 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4212 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4213 DstAlignCanChange = true;
4214 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4215 if (Align > SrcAlign)
4217 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4219 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4220 (DstAlignCanChange ? 0 : Align), SrcAlign,
4221 false, false, false, false, DAG, TLI))
4224 if (DstAlignCanChange) {
4225 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4226 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4227 if (NewAlign > Align) {
4228 // Give the stack frame object a larger alignment if needed.
4229 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4230 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4235 uint64_t SrcOff = 0, DstOff = 0;
4236 SmallVector<SDValue, 8> LoadValues;
4237 SmallVector<SDValue, 8> LoadChains;
4238 SmallVector<SDValue, 8> OutChains;
4239 unsigned NumMemOps = MemOps.size();
4240 for (unsigned i = 0; i < NumMemOps; i++) {
4242 unsigned VTSize = VT.getSizeInBits() / 8;
4245 Value = DAG.getLoad(VT, dl, Chain,
4246 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4247 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4248 false, false, SrcAlign);
4249 LoadValues.push_back(Value);
4250 LoadChains.push_back(Value.getValue(1));
4253 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4255 for (unsigned i = 0; i < NumMemOps; i++) {
4257 unsigned VTSize = VT.getSizeInBits() / 8;
4260 Store = DAG.getStore(Chain, dl, LoadValues[i],
4261 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4262 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4263 OutChains.push_back(Store);
4267 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4270 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4273 /// \param DAG Selection DAG where lowered code is placed.
4274 /// \param dl Link to corresponding IR location.
4275 /// \param Chain Control flow dependency.
4276 /// \param Dst Pointer to destination memory location.
4277 /// \param Src Value of byte to write into the memory.
4278 /// \param Size Number of bytes to write.
4279 /// \param Align Alignment of the destination in bytes.
4280 /// \param isVol True if destination is volatile.
4281 /// \param DstPtrInfo IR information on the memory pointer.
4282 /// \returns New head in the control flow, if lowering was successful, empty
4283 /// SDValue otherwise.
4285 /// The function tries to replace 'llvm.memset' intrinsic with several store
4286 /// operations and value calculation code. This is usually profitable for small
4288 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4289 SDValue Chain, SDValue Dst,
4290 SDValue Src, uint64_t Size,
4291 unsigned Align, bool isVol,
4292 MachinePointerInfo DstPtrInfo) {
4293 // Turn a memset of undef to nop.
4294 if (Src.getOpcode() == ISD::UNDEF)
4297 // Expand memset to a series of load/store ops if the size operand
4298 // falls below a certain threshold.
4299 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4300 std::vector<EVT> MemOps;
4301 bool DstAlignCanChange = false;
4302 MachineFunction &MF = DAG.getMachineFunction();
4303 MachineFrameInfo *MFI = MF.getFrameInfo();
4304 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4305 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4306 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4307 DstAlignCanChange = true;
4309 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4310 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4311 Size, (DstAlignCanChange ? 0 : Align), 0,
4312 true, IsZeroVal, false, true, DAG, TLI))
4315 if (DstAlignCanChange) {
4316 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4317 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4318 if (NewAlign > Align) {
4319 // Give the stack frame object a larger alignment if needed.
4320 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4321 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4326 SmallVector<SDValue, 8> OutChains;
4327 uint64_t DstOff = 0;
4328 unsigned NumMemOps = MemOps.size();
4330 // Find the largest store and generate the bit pattern for it.
4331 EVT LargestVT = MemOps[0];
4332 for (unsigned i = 1; i < NumMemOps; i++)
4333 if (MemOps[i].bitsGT(LargestVT))
4334 LargestVT = MemOps[i];
4335 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4337 for (unsigned i = 0; i < NumMemOps; i++) {
4339 unsigned VTSize = VT.getSizeInBits() / 8;
4340 if (VTSize > Size) {
4341 // Issuing an unaligned load / store pair that overlaps with the previous
4342 // pair. Adjust the offset accordingly.
4343 assert(i == NumMemOps-1 && i != 0);
4344 DstOff -= VTSize - Size;
4347 // If this store is smaller than the largest store see whether we can get
4348 // the smaller value for free with a truncate.
4349 SDValue Value = MemSetValue;
4350 if (VT.bitsLT(LargestVT)) {
4351 if (!LargestVT.isVector() && !VT.isVector() &&
4352 TLI.isTruncateFree(LargestVT, VT))
4353 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4355 Value = getMemsetValue(Src, VT, DAG, dl);
4357 assert(Value.getValueType() == VT && "Value with wrong type.");
4358 SDValue Store = DAG.getStore(Chain, dl, Value,
4359 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4360 DstPtrInfo.getWithOffset(DstOff),
4361 isVol, false, Align);
4362 OutChains.push_back(Store);
4363 DstOff += VT.getSizeInBits() / 8;
4367 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4370 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4371 SDValue Src, SDValue Size,
4372 unsigned Align, bool isVol, bool AlwaysInline,
4373 bool isTailCall, MachinePointerInfo DstPtrInfo,
4374 MachinePointerInfo SrcPtrInfo) {
4375 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4377 // Check to see if we should lower the memcpy to loads and stores first.
4378 // For cases within the target-specified limits, this is the best choice.
4379 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4381 // Memcpy with size zero? Just return the original chain.
4382 if (ConstantSize->isNullValue())
4385 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4386 ConstantSize->getZExtValue(),Align,
4387 isVol, false, DstPtrInfo, SrcPtrInfo);
4388 if (Result.getNode())
4392 // Then check to see if we should lower the memcpy with target-specific
4393 // code. If the target chooses to do this, this is the next best.
4395 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4396 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4397 DstPtrInfo, SrcPtrInfo);
4398 if (Result.getNode())
4402 // If we really need inline code and the target declined to provide it,
4403 // use a (potentially long) sequence of loads and stores.
4405 assert(ConstantSize && "AlwaysInline requires a constant size!");
4406 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4407 ConstantSize->getZExtValue(), Align, isVol,
4408 true, DstPtrInfo, SrcPtrInfo);
4411 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4412 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4413 // respect volatile, so they may do things like read or write memory
4414 // beyond the given memory regions. But fixing this isn't easy, and most
4415 // people don't care.
4417 // Emit a library call.
4418 TargetLowering::ArgListTy Args;
4419 TargetLowering::ArgListEntry Entry;
4420 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4421 Entry.Node = Dst; Args.push_back(Entry);
4422 Entry.Node = Src; Args.push_back(Entry);
4423 Entry.Node = Size; Args.push_back(Entry);
4424 // FIXME: pass in SDLoc
4425 TargetLowering::CallLoweringInfo CLI(*this);
4426 CLI.setDebugLoc(dl).setChain(Chain)
4427 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4428 Type::getVoidTy(*getContext()),
4429 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4430 TLI->getPointerTy()), std::move(Args), 0)
4432 .setTailCall(isTailCall);
4434 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4435 return CallResult.second;
4438 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4439 SDValue Src, SDValue Size,
4440 unsigned Align, bool isVol, bool isTailCall,
4441 MachinePointerInfo DstPtrInfo,
4442 MachinePointerInfo SrcPtrInfo) {
4443 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4445 // Check to see if we should lower the memmove to loads and stores first.
4446 // For cases within the target-specified limits, this is the best choice.
4447 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4449 // Memmove with size zero? Just return the original chain.
4450 if (ConstantSize->isNullValue())
4454 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4455 ConstantSize->getZExtValue(), Align, isVol,
4456 false, DstPtrInfo, SrcPtrInfo);
4457 if (Result.getNode())
4461 // Then check to see if we should lower the memmove with target-specific
4462 // code. If the target chooses to do this, this is the next best.
4464 SDValue Result = TSI->EmitTargetCodeForMemmove(
4465 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4466 if (Result.getNode())
4470 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4471 // not be safe. See memcpy above for more details.
4473 // Emit a library call.
4474 TargetLowering::ArgListTy Args;
4475 TargetLowering::ArgListEntry Entry;
4476 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4477 Entry.Node = Dst; Args.push_back(Entry);
4478 Entry.Node = Src; Args.push_back(Entry);
4479 Entry.Node = Size; Args.push_back(Entry);
4480 // FIXME: pass in SDLoc
4481 TargetLowering::CallLoweringInfo CLI(*this);
4482 CLI.setDebugLoc(dl).setChain(Chain)
4483 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4484 Type::getVoidTy(*getContext()),
4485 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4486 TLI->getPointerTy()), std::move(Args), 0)
4488 .setTailCall(isTailCall);
4490 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4491 return CallResult.second;
4494 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4495 SDValue Src, SDValue Size,
4496 unsigned Align, bool isVol, bool isTailCall,
4497 MachinePointerInfo DstPtrInfo) {
4498 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4500 // Check to see if we should lower the memset to stores first.
4501 // For cases within the target-specified limits, this is the best choice.
4502 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4504 // Memset with size zero? Just return the original chain.
4505 if (ConstantSize->isNullValue())
4509 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4510 Align, isVol, DstPtrInfo);
4512 if (Result.getNode())
4516 // Then check to see if we should lower the memset with target-specific
4517 // code. If the target chooses to do this, this is the next best.
4519 SDValue Result = TSI->EmitTargetCodeForMemset(
4520 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4521 if (Result.getNode())
4525 // Emit a library call.
4526 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4527 TargetLowering::ArgListTy Args;
4528 TargetLowering::ArgListEntry Entry;
4529 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4530 Args.push_back(Entry);
4532 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4533 Args.push_back(Entry);
4535 Entry.Ty = IntPtrTy;
4536 Args.push_back(Entry);
4538 // FIXME: pass in SDLoc
4539 TargetLowering::CallLoweringInfo CLI(*this);
4540 CLI.setDebugLoc(dl).setChain(Chain)
4541 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4542 Type::getVoidTy(*getContext()),
4543 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4544 TLI->getPointerTy()), std::move(Args), 0)
4546 .setTailCall(isTailCall);
4548 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4549 return CallResult.second;
4552 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4553 SDVTList VTList, ArrayRef<SDValue> Ops,
4554 MachineMemOperand *MMO,
4555 AtomicOrdering SuccessOrdering,
4556 AtomicOrdering FailureOrdering,
4557 SynchronizationScope SynchScope) {
4558 FoldingSetNodeID ID;
4559 ID.AddInteger(MemVT.getRawBits());
4560 AddNodeIDNode(ID, Opcode, VTList, Ops);
4561 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4563 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4564 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4565 return SDValue(E, 0);
4568 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4569 // SDNode doesn't have access to it. This memory will be "leaked" when
4570 // the node is deallocated, but recovered when the allocator is released.
4571 // If the number of operands is less than 5 we use AtomicSDNode's internal
4573 unsigned NumOps = Ops.size();
4574 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4577 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4578 dl.getDebugLoc(), VTList, MemVT,
4579 Ops.data(), DynOps, NumOps, MMO,
4580 SuccessOrdering, FailureOrdering,
4582 CSEMap.InsertNode(N, IP);
4584 return SDValue(N, 0);
4587 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4588 SDVTList VTList, ArrayRef<SDValue> Ops,
4589 MachineMemOperand *MMO,
4590 AtomicOrdering Ordering,
4591 SynchronizationScope SynchScope) {
4592 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4593 Ordering, SynchScope);
4596 SDValue SelectionDAG::getAtomicCmpSwap(
4597 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4598 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4599 unsigned Alignment, AtomicOrdering SuccessOrdering,
4600 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4601 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4602 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4603 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4605 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4606 Alignment = getEVTAlignment(MemVT);
4608 MachineFunction &MF = getMachineFunction();
4610 // FIXME: Volatile isn't really correct; we should keep track of atomic
4611 // orderings in the memoperand.
4612 unsigned Flags = MachineMemOperand::MOVolatile;
4613 Flags |= MachineMemOperand::MOLoad;
4614 Flags |= MachineMemOperand::MOStore;
4616 MachineMemOperand *MMO =
4617 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4619 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4620 SuccessOrdering, FailureOrdering, SynchScope);
4623 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4624 SDVTList VTs, SDValue Chain, SDValue Ptr,
4625 SDValue Cmp, SDValue Swp,
4626 MachineMemOperand *MMO,
4627 AtomicOrdering SuccessOrdering,
4628 AtomicOrdering FailureOrdering,
4629 SynchronizationScope SynchScope) {
4630 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4631 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4632 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4634 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4635 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4636 SuccessOrdering, FailureOrdering, SynchScope);
4639 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4641 SDValue Ptr, SDValue Val,
4642 const Value* PtrVal,
4644 AtomicOrdering Ordering,
4645 SynchronizationScope SynchScope) {
4646 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4647 Alignment = getEVTAlignment(MemVT);
4649 MachineFunction &MF = getMachineFunction();
4650 // An atomic store does not load. An atomic load does not store.
4651 // (An atomicrmw obviously both loads and stores.)
4652 // For now, atomics are considered to be volatile always, and they are
4654 // FIXME: Volatile isn't really correct; we should keep track of atomic
4655 // orderings in the memoperand.
4656 unsigned Flags = MachineMemOperand::MOVolatile;
4657 if (Opcode != ISD::ATOMIC_STORE)
4658 Flags |= MachineMemOperand::MOLoad;
4659 if (Opcode != ISD::ATOMIC_LOAD)
4660 Flags |= MachineMemOperand::MOStore;
4662 MachineMemOperand *MMO =
4663 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4664 MemVT.getStoreSize(), Alignment);
4666 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4667 Ordering, SynchScope);
4670 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4672 SDValue Ptr, SDValue Val,
4673 MachineMemOperand *MMO,
4674 AtomicOrdering Ordering,
4675 SynchronizationScope SynchScope) {
4676 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4677 Opcode == ISD::ATOMIC_LOAD_SUB ||
4678 Opcode == ISD::ATOMIC_LOAD_AND ||
4679 Opcode == ISD::ATOMIC_LOAD_OR ||
4680 Opcode == ISD::ATOMIC_LOAD_XOR ||
4681 Opcode == ISD::ATOMIC_LOAD_NAND ||
4682 Opcode == ISD::ATOMIC_LOAD_MIN ||
4683 Opcode == ISD::ATOMIC_LOAD_MAX ||
4684 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4685 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4686 Opcode == ISD::ATOMIC_SWAP ||
4687 Opcode == ISD::ATOMIC_STORE) &&
4688 "Invalid Atomic Op");
4690 EVT VT = Val.getValueType();
4692 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4693 getVTList(VT, MVT::Other);
4694 SDValue Ops[] = {Chain, Ptr, Val};
4695 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4698 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4699 EVT VT, SDValue Chain,
4701 MachineMemOperand *MMO,
4702 AtomicOrdering Ordering,
4703 SynchronizationScope SynchScope) {
4704 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4706 SDVTList VTs = getVTList(VT, MVT::Other);
4707 SDValue Ops[] = {Chain, Ptr};
4708 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4711 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4712 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4713 if (Ops.size() == 1)
4716 SmallVector<EVT, 4> VTs;
4717 VTs.reserve(Ops.size());
4718 for (unsigned i = 0; i < Ops.size(); ++i)
4719 VTs.push_back(Ops[i].getValueType());
4720 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4724 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4725 ArrayRef<SDValue> Ops,
4726 EVT MemVT, MachinePointerInfo PtrInfo,
4727 unsigned Align, bool Vol,
4728 bool ReadMem, bool WriteMem, unsigned Size) {
4729 if (Align == 0) // Ensure that codegen never sees alignment 0
4730 Align = getEVTAlignment(MemVT);
4732 MachineFunction &MF = getMachineFunction();
4735 Flags |= MachineMemOperand::MOStore;
4737 Flags |= MachineMemOperand::MOLoad;
4739 Flags |= MachineMemOperand::MOVolatile;
4741 Size = MemVT.getStoreSize();
4742 MachineMemOperand *MMO =
4743 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4745 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4749 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4750 ArrayRef<SDValue> Ops, EVT MemVT,
4751 MachineMemOperand *MMO) {
4752 assert((Opcode == ISD::INTRINSIC_VOID ||
4753 Opcode == ISD::INTRINSIC_W_CHAIN ||
4754 Opcode == ISD::PREFETCH ||
4755 Opcode == ISD::LIFETIME_START ||
4756 Opcode == ISD::LIFETIME_END ||
4757 (Opcode <= INT_MAX &&
4758 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4759 "Opcode is not a memory-accessing opcode!");
4761 // Memoize the node unless it returns a flag.
4762 MemIntrinsicSDNode *N;
4763 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4764 FoldingSetNodeID ID;
4765 AddNodeIDNode(ID, Opcode, VTList, Ops);
4766 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4768 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4769 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4770 return SDValue(E, 0);
4773 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4774 dl.getDebugLoc(), VTList, Ops,
4776 CSEMap.InsertNode(N, IP);
4778 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4779 dl.getDebugLoc(), VTList, Ops,
4783 return SDValue(N, 0);
4786 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4787 /// MachinePointerInfo record from it. This is particularly useful because the
4788 /// code generator has many cases where it doesn't bother passing in a
4789 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4790 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4791 // If this is FI+Offset, we can model it.
4792 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4793 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4795 // If this is (FI+Offset1)+Offset2, we can model it.
4796 if (Ptr.getOpcode() != ISD::ADD ||
4797 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4798 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4799 return MachinePointerInfo();
4801 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4802 return MachinePointerInfo::getFixedStack(FI, Offset+
4803 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4806 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4807 /// MachinePointerInfo record from it. This is particularly useful because the
4808 /// code generator has many cases where it doesn't bother passing in a
4809 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4810 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4811 // If the 'Offset' value isn't a constant, we can't handle this.
4812 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4813 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4814 if (OffsetOp.getOpcode() == ISD::UNDEF)
4815 return InferPointerInfo(Ptr);
4816 return MachinePointerInfo();
4821 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4822 EVT VT, SDLoc dl, SDValue Chain,
4823 SDValue Ptr, SDValue Offset,
4824 MachinePointerInfo PtrInfo, EVT MemVT,
4825 bool isVolatile, bool isNonTemporal, bool isInvariant,
4826 unsigned Alignment, const AAMDNodes &AAInfo,
4827 const MDNode *Ranges) {
4828 assert(Chain.getValueType() == MVT::Other &&
4829 "Invalid chain type");
4830 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4831 Alignment = getEVTAlignment(VT);
4833 unsigned Flags = MachineMemOperand::MOLoad;
4835 Flags |= MachineMemOperand::MOVolatile;
4837 Flags |= MachineMemOperand::MONonTemporal;
4839 Flags |= MachineMemOperand::MOInvariant;
4841 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4843 if (PtrInfo.V.isNull())
4844 PtrInfo = InferPointerInfo(Ptr, Offset);
4846 MachineFunction &MF = getMachineFunction();
4847 MachineMemOperand *MMO =
4848 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4850 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4854 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4855 EVT VT, SDLoc dl, SDValue Chain,
4856 SDValue Ptr, SDValue Offset, EVT MemVT,
4857 MachineMemOperand *MMO) {
4859 ExtType = ISD::NON_EXTLOAD;
4860 } else if (ExtType == ISD::NON_EXTLOAD) {
4861 assert(VT == MemVT && "Non-extending load from different memory type!");
4864 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4865 "Should only be an extending load, not truncating!");
4866 assert(VT.isInteger() == MemVT.isInteger() &&
4867 "Cannot convert from FP to Int or Int -> FP!");
4868 assert(VT.isVector() == MemVT.isVector() &&
4869 "Cannot use an ext load to convert to or from a vector!");
4870 assert((!VT.isVector() ||
4871 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4872 "Cannot use an ext load to change the number of vector elements!");
4875 bool Indexed = AM != ISD::UNINDEXED;
4876 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4877 "Unindexed load with an offset!");
4879 SDVTList VTs = Indexed ?
4880 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4881 SDValue Ops[] = { Chain, Ptr, Offset };
4882 FoldingSetNodeID ID;
4883 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4884 ID.AddInteger(MemVT.getRawBits());
4885 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4886 MMO->isNonTemporal(),
4887 MMO->isInvariant()));
4888 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4890 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4891 cast<LoadSDNode>(E)->refineAlignment(MMO);
4892 return SDValue(E, 0);
4894 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4895 dl.getDebugLoc(), VTs, AM, ExtType,
4897 CSEMap.InsertNode(N, IP);
4899 return SDValue(N, 0);
4902 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4903 SDValue Chain, SDValue Ptr,
4904 MachinePointerInfo PtrInfo,
4905 bool isVolatile, bool isNonTemporal,
4906 bool isInvariant, unsigned Alignment,
4907 const AAMDNodes &AAInfo,
4908 const MDNode *Ranges) {
4909 SDValue Undef = getUNDEF(Ptr.getValueType());
4910 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4911 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4915 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4916 SDValue Chain, SDValue Ptr,
4917 MachineMemOperand *MMO) {
4918 SDValue Undef = getUNDEF(Ptr.getValueType());
4919 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4923 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4924 SDValue Chain, SDValue Ptr,
4925 MachinePointerInfo PtrInfo, EVT MemVT,
4926 bool isVolatile, bool isNonTemporal,
4927 bool isInvariant, unsigned Alignment,
4928 const AAMDNodes &AAInfo) {
4929 SDValue Undef = getUNDEF(Ptr.getValueType());
4930 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4931 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4936 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4937 SDValue Chain, SDValue Ptr, EVT MemVT,
4938 MachineMemOperand *MMO) {
4939 SDValue Undef = getUNDEF(Ptr.getValueType());
4940 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4945 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4946 SDValue Offset, ISD::MemIndexedMode AM) {
4947 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4948 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4949 "Load is already a indexed load!");
4950 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4951 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4952 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4953 false, LD->getAlignment());
4956 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4957 SDValue Ptr, MachinePointerInfo PtrInfo,
4958 bool isVolatile, bool isNonTemporal,
4959 unsigned Alignment, const AAMDNodes &AAInfo) {
4960 assert(Chain.getValueType() == MVT::Other &&
4961 "Invalid chain type");
4962 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4963 Alignment = getEVTAlignment(Val.getValueType());
4965 unsigned Flags = MachineMemOperand::MOStore;
4967 Flags |= MachineMemOperand::MOVolatile;
4969 Flags |= MachineMemOperand::MONonTemporal;
4971 if (PtrInfo.V.isNull())
4972 PtrInfo = InferPointerInfo(Ptr);
4974 MachineFunction &MF = getMachineFunction();
4975 MachineMemOperand *MMO =
4976 MF.getMachineMemOperand(PtrInfo, Flags,
4977 Val.getValueType().getStoreSize(), Alignment,
4980 return getStore(Chain, dl, Val, Ptr, MMO);
4983 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4984 SDValue Ptr, MachineMemOperand *MMO) {
4985 assert(Chain.getValueType() == MVT::Other &&
4986 "Invalid chain type");
4987 EVT VT = Val.getValueType();
4988 SDVTList VTs = getVTList(MVT::Other);
4989 SDValue Undef = getUNDEF(Ptr.getValueType());
4990 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4991 FoldingSetNodeID ID;
4992 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4993 ID.AddInteger(VT.getRawBits());
4994 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4995 MMO->isNonTemporal(), MMO->isInvariant()));
4996 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4998 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4999 cast<StoreSDNode>(E)->refineAlignment(MMO);
5000 return SDValue(E, 0);
5002 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5003 dl.getDebugLoc(), VTs,
5004 ISD::UNINDEXED, false, VT, MMO);
5005 CSEMap.InsertNode(N, IP);
5007 return SDValue(N, 0);
5010 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5011 SDValue Ptr, MachinePointerInfo PtrInfo,
5012 EVT SVT,bool isVolatile, bool isNonTemporal,
5014 const AAMDNodes &AAInfo) {
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5017 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5018 Alignment = getEVTAlignment(SVT);
5020 unsigned Flags = MachineMemOperand::MOStore;
5022 Flags |= MachineMemOperand::MOVolatile;
5024 Flags |= MachineMemOperand::MONonTemporal;
5026 if (PtrInfo.V.isNull())
5027 PtrInfo = InferPointerInfo(Ptr);
5029 MachineFunction &MF = getMachineFunction();
5030 MachineMemOperand *MMO =
5031 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5034 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5037 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5038 SDValue Ptr, EVT SVT,
5039 MachineMemOperand *MMO) {
5040 EVT VT = Val.getValueType();
5042 assert(Chain.getValueType() == MVT::Other &&
5043 "Invalid chain type");
5045 return getStore(Chain, dl, Val, Ptr, MMO);
5047 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5048 "Should only be a truncating store, not extending!");
5049 assert(VT.isInteger() == SVT.isInteger() &&
5050 "Can't do FP-INT conversion!");
5051 assert(VT.isVector() == SVT.isVector() &&
5052 "Cannot use trunc store to convert to or from a vector!");
5053 assert((!VT.isVector() ||
5054 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5055 "Cannot use trunc store to change the number of vector elements!");
5057 SDVTList VTs = getVTList(MVT::Other);
5058 SDValue Undef = getUNDEF(Ptr.getValueType());
5059 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5060 FoldingSetNodeID ID;
5061 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5062 ID.AddInteger(SVT.getRawBits());
5063 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5064 MMO->isNonTemporal(), MMO->isInvariant()));
5065 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5067 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5068 cast<StoreSDNode>(E)->refineAlignment(MMO);
5069 return SDValue(E, 0);
5071 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5072 dl.getDebugLoc(), VTs,
5073 ISD::UNINDEXED, true, SVT, MMO);
5074 CSEMap.InsertNode(N, IP);
5076 return SDValue(N, 0);
5080 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5081 SDValue Offset, ISD::MemIndexedMode AM) {
5082 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5083 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5084 "Store is already a indexed store!");
5085 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5086 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5087 FoldingSetNodeID ID;
5088 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5089 ID.AddInteger(ST->getMemoryVT().getRawBits());
5090 ID.AddInteger(ST->getRawSubclassData());
5091 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5093 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5094 return SDValue(E, 0);
5096 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5097 dl.getDebugLoc(), VTs, AM,
5098 ST->isTruncatingStore(),
5100 ST->getMemOperand());
5101 CSEMap.InsertNode(N, IP);
5103 return SDValue(N, 0);
5107 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5108 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5109 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5111 SDVTList VTs = getVTList(VT, MVT::Other);
5112 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5113 FoldingSetNodeID ID;
5114 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5115 ID.AddInteger(VT.getRawBits());
5116 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5118 MMO->isNonTemporal(),
5119 MMO->isInvariant()));
5120 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5122 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5123 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5124 return SDValue(E, 0);
5126 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5127 dl.getDebugLoc(), Ops, 4, VTs,
5129 CSEMap.InsertNode(N, IP);
5131 return SDValue(N, 0);
5134 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5135 SDValue Ptr, SDValue Mask, EVT MemVT,
5136 MachineMemOperand *MMO, bool isTrunc) {
5137 assert(Chain.getValueType() == MVT::Other &&
5138 "Invalid chain type");
5139 EVT VT = Val.getValueType();
5140 SDVTList VTs = getVTList(MVT::Other);
5141 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5142 FoldingSetNodeID ID;
5143 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5144 ID.AddInteger(VT.getRawBits());
5145 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5146 MMO->isNonTemporal(), MMO->isInvariant()));
5147 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5149 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5150 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5151 return SDValue(E, 0);
5153 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5154 dl.getDebugLoc(), Ops, 4,
5155 VTs, isTrunc, MemVT, MMO);
5156 CSEMap.InsertNode(N, IP);
5158 return SDValue(N, 0);
5162 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5163 ArrayRef<SDValue> Ops,
5164 MachineMemOperand *MMO) {
5166 FoldingSetNodeID ID;
5167 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5168 ID.AddInteger(VT.getRawBits());
5169 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5171 MMO->isNonTemporal(),
5172 MMO->isInvariant()));
5173 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5175 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5176 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5177 return SDValue(E, 0);
5179 MaskedGatherSDNode *N =
5180 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5182 CSEMap.InsertNode(N, IP);
5184 return SDValue(N, 0);
5187 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5188 ArrayRef<SDValue> Ops,
5189 MachineMemOperand *MMO) {
5190 FoldingSetNodeID ID;
5191 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5192 ID.AddInteger(VT.getRawBits());
5193 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5194 MMO->isNonTemporal(),
5195 MMO->isInvariant()));
5196 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5198 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5199 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5200 return SDValue(E, 0);
5203 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5205 CSEMap.InsertNode(N, IP);
5207 return SDValue(N, 0);
5210 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5211 SDValue Chain, SDValue Ptr,
5214 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5215 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5218 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5219 ArrayRef<SDUse> Ops) {
5220 switch (Ops.size()) {
5221 case 0: return getNode(Opcode, DL, VT);
5222 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5223 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5224 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5228 // Copy from an SDUse array into an SDValue array for use with
5229 // the regular getNode logic.
5230 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5231 return getNode(Opcode, DL, VT, NewOps);
5234 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5235 ArrayRef<SDValue> Ops) {
5236 unsigned NumOps = Ops.size();
5238 case 0: return getNode(Opcode, DL, VT);
5239 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5240 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5241 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5247 case ISD::SELECT_CC: {
5248 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5249 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5250 "LHS and RHS of condition must have same type!");
5251 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5252 "True and False arms of SelectCC must have same type!");
5253 assert(Ops[2].getValueType() == VT &&
5254 "select_cc node must be of same type as true and false value!");
5258 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5259 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5260 "LHS/RHS of comparison should match types!");
5267 SDVTList VTs = getVTList(VT);
5269 if (VT != MVT::Glue) {
5270 FoldingSetNodeID ID;
5271 AddNodeIDNode(ID, Opcode, VTs, Ops);
5274 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5275 return SDValue(E, 0);
5277 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5279 CSEMap.InsertNode(N, IP);
5281 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5286 return SDValue(N, 0);
5289 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5290 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5291 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5294 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5295 ArrayRef<SDValue> Ops) {
5296 if (VTList.NumVTs == 1)
5297 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5301 // FIXME: figure out how to safely handle things like
5302 // int foo(int x) { return 1 << (x & 255); }
5303 // int bar() { return foo(256); }
5304 case ISD::SRA_PARTS:
5305 case ISD::SRL_PARTS:
5306 case ISD::SHL_PARTS:
5307 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5308 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5309 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5310 else if (N3.getOpcode() == ISD::AND)
5311 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5312 // If the and is only masking out bits that cannot effect the shift,
5313 // eliminate the and.
5314 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5315 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5316 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5322 // Memoize the node unless it returns a flag.
5324 unsigned NumOps = Ops.size();
5325 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5326 FoldingSetNodeID ID;
5327 AddNodeIDNode(ID, Opcode, VTList, Ops);
5329 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5330 return SDValue(E, 0);
5333 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5334 DL.getDebugLoc(), VTList, Ops[0]);
5335 } else if (NumOps == 2) {
5336 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5337 DL.getDebugLoc(), VTList, Ops[0],
5339 } else if (NumOps == 3) {
5340 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5341 DL.getDebugLoc(), VTList, Ops[0],
5344 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5347 CSEMap.InsertNode(N, IP);
5350 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5351 DL.getDebugLoc(), VTList, Ops[0]);
5352 } else if (NumOps == 2) {
5353 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5354 DL.getDebugLoc(), VTList, Ops[0],
5356 } else if (NumOps == 3) {
5357 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5358 DL.getDebugLoc(), VTList, Ops[0],
5361 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5366 return SDValue(N, 0);
5369 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5370 return getNode(Opcode, DL, VTList, None);
5373 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5375 SDValue Ops[] = { N1 };
5376 return getNode(Opcode, DL, VTList, Ops);
5379 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5380 SDValue N1, SDValue N2) {
5381 SDValue Ops[] = { N1, N2 };
5382 return getNode(Opcode, DL, VTList, Ops);
5385 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5386 SDValue N1, SDValue N2, SDValue N3) {
5387 SDValue Ops[] = { N1, N2, N3 };
5388 return getNode(Opcode, DL, VTList, Ops);
5391 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5392 SDValue N1, SDValue N2, SDValue N3,
5394 SDValue Ops[] = { N1, N2, N3, N4 };
5395 return getNode(Opcode, DL, VTList, Ops);
5398 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5399 SDValue N1, SDValue N2, SDValue N3,
5400 SDValue N4, SDValue N5) {
5401 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5402 return getNode(Opcode, DL, VTList, Ops);
5405 SDVTList SelectionDAG::getVTList(EVT VT) {
5406 return makeVTList(SDNode::getValueTypeList(VT), 1);
5409 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5410 FoldingSetNodeID ID;
5412 ID.AddInteger(VT1.getRawBits());
5413 ID.AddInteger(VT2.getRawBits());
5416 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5418 EVT *Array = Allocator.Allocate<EVT>(2);
5421 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5422 VTListMap.InsertNode(Result, IP);
5424 return Result->getSDVTList();
5427 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5428 FoldingSetNodeID ID;
5430 ID.AddInteger(VT1.getRawBits());
5431 ID.AddInteger(VT2.getRawBits());
5432 ID.AddInteger(VT3.getRawBits());
5435 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5437 EVT *Array = Allocator.Allocate<EVT>(3);
5441 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5442 VTListMap.InsertNode(Result, IP);
5444 return Result->getSDVTList();
5447 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5448 FoldingSetNodeID ID;
5450 ID.AddInteger(VT1.getRawBits());
5451 ID.AddInteger(VT2.getRawBits());
5452 ID.AddInteger(VT3.getRawBits());
5453 ID.AddInteger(VT4.getRawBits());
5456 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5458 EVT *Array = Allocator.Allocate<EVT>(4);
5463 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5464 VTListMap.InsertNode(Result, IP);
5466 return Result->getSDVTList();
5469 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5470 unsigned NumVTs = VTs.size();
5471 FoldingSetNodeID ID;
5472 ID.AddInteger(NumVTs);
5473 for (unsigned index = 0; index < NumVTs; index++) {
5474 ID.AddInteger(VTs[index].getRawBits());
5478 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5480 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5481 std::copy(VTs.begin(), VTs.end(), Array);
5482 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5483 VTListMap.InsertNode(Result, IP);
5485 return Result->getSDVTList();
5489 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5490 /// specified operands. If the resultant node already exists in the DAG,
5491 /// this does not modify the specified node, instead it returns the node that
5492 /// already exists. If the resultant node does not exist in the DAG, the
5493 /// input node is returned. As a degenerate case, if you specify the same
5494 /// input operands as the node already has, the input node is returned.
5495 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5496 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5498 // Check to see if there is no change.
5499 if (Op == N->getOperand(0)) return N;
5501 // See if the modified node already exists.
5502 void *InsertPos = nullptr;
5503 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5506 // Nope it doesn't. Remove the node from its current place in the maps.
5508 if (!RemoveNodeFromCSEMaps(N))
5509 InsertPos = nullptr;
5511 // Now we update the operands.
5512 N->OperandList[0].set(Op);
5514 // If this gets put into a CSE map, add it.
5515 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5519 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5520 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5522 // Check to see if there is no change.
5523 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5524 return N; // No operands changed, just return the input node.
5526 // See if the modified node already exists.
5527 void *InsertPos = nullptr;
5528 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5531 // Nope it doesn't. Remove the node from its current place in the maps.
5533 if (!RemoveNodeFromCSEMaps(N))
5534 InsertPos = nullptr;
5536 // Now we update the operands.
5537 if (N->OperandList[0] != Op1)
5538 N->OperandList[0].set(Op1);
5539 if (N->OperandList[1] != Op2)
5540 N->OperandList[1].set(Op2);
5542 // If this gets put into a CSE map, add it.
5543 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5547 SDNode *SelectionDAG::
5548 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5549 SDValue Ops[] = { Op1, Op2, Op3 };
5550 return UpdateNodeOperands(N, Ops);
5553 SDNode *SelectionDAG::
5554 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5555 SDValue Op3, SDValue Op4) {
5556 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5557 return UpdateNodeOperands(N, Ops);
5560 SDNode *SelectionDAG::
5561 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5562 SDValue Op3, SDValue Op4, SDValue Op5) {
5563 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5564 return UpdateNodeOperands(N, Ops);
5567 SDNode *SelectionDAG::
5568 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5569 unsigned NumOps = Ops.size();
5570 assert(N->getNumOperands() == NumOps &&
5571 "Update with wrong number of operands");
5573 // If no operands changed just return the input node.
5574 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5577 // See if the modified node already exists.
5578 void *InsertPos = nullptr;
5579 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5582 // Nope it doesn't. Remove the node from its current place in the maps.
5584 if (!RemoveNodeFromCSEMaps(N))
5585 InsertPos = nullptr;
5587 // Now we update the operands.
5588 for (unsigned i = 0; i != NumOps; ++i)
5589 if (N->OperandList[i] != Ops[i])
5590 N->OperandList[i].set(Ops[i]);
5592 // If this gets put into a CSE map, add it.
5593 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5597 /// DropOperands - Release the operands and set this node to have
5599 void SDNode::DropOperands() {
5600 // Unlike the code in MorphNodeTo that does this, we don't need to
5601 // watch for dead nodes here.
5602 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5608 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5611 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5613 SDVTList VTs = getVTList(VT);
5614 return SelectNodeTo(N, MachineOpc, VTs, None);
5617 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5618 EVT VT, SDValue Op1) {
5619 SDVTList VTs = getVTList(VT);
5620 SDValue Ops[] = { Op1 };
5621 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5624 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5625 EVT VT, SDValue Op1,
5627 SDVTList VTs = getVTList(VT);
5628 SDValue Ops[] = { Op1, Op2 };
5629 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5632 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5633 EVT VT, SDValue Op1,
5634 SDValue Op2, SDValue Op3) {
5635 SDVTList VTs = getVTList(VT);
5636 SDValue Ops[] = { Op1, Op2, Op3 };
5637 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5640 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5641 EVT VT, ArrayRef<SDValue> Ops) {
5642 SDVTList VTs = getVTList(VT);
5643 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5646 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5647 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5648 SDVTList VTs = getVTList(VT1, VT2);
5649 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5652 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5654 SDVTList VTs = getVTList(VT1, VT2);
5655 return SelectNodeTo(N, MachineOpc, VTs, None);
5658 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5659 EVT VT1, EVT VT2, EVT VT3,
5660 ArrayRef<SDValue> Ops) {
5661 SDVTList VTs = getVTList(VT1, VT2, VT3);
5662 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5665 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5666 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5667 ArrayRef<SDValue> Ops) {
5668 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5669 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5672 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5675 SDVTList VTs = getVTList(VT1, VT2);
5676 SDValue Ops[] = { Op1 };
5677 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5680 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5682 SDValue Op1, SDValue Op2) {
5683 SDVTList VTs = getVTList(VT1, VT2);
5684 SDValue Ops[] = { Op1, Op2 };
5685 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5688 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5690 SDValue Op1, SDValue Op2,
5692 SDVTList VTs = getVTList(VT1, VT2);
5693 SDValue Ops[] = { Op1, Op2, Op3 };
5694 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698 EVT VT1, EVT VT2, EVT VT3,
5699 SDValue Op1, SDValue Op2,
5701 SDVTList VTs = getVTList(VT1, VT2, VT3);
5702 SDValue Ops[] = { Op1, Op2, Op3 };
5703 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5706 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5707 SDVTList VTs,ArrayRef<SDValue> Ops) {
5708 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5709 // Reset the NodeID to -1.
5714 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5715 /// the line number information on the merged node since it is not possible to
5716 /// preserve the information that operation is associated with multiple lines.
5717 /// This will make the debugger working better at -O0, were there is a higher
5718 /// probability having other instructions associated with that line.
5720 /// For IROrder, we keep the smaller of the two
5721 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5722 DebugLoc NLoc = N->getDebugLoc();
5723 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5724 N->setDebugLoc(DebugLoc());
5726 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5727 N->setIROrder(Order);
5731 /// MorphNodeTo - This *mutates* the specified node to have the specified
5732 /// return type, opcode, and operands.
5734 /// Note that MorphNodeTo returns the resultant node. If there is already a
5735 /// node of the specified opcode and operands, it returns that node instead of
5736 /// the current one. Note that the SDLoc need not be the same.
5738 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5739 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5740 /// node, and because it doesn't require CSE recalculation for any of
5741 /// the node's users.
5743 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5744 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5745 /// the legalizer which maintain worklists that would need to be updated when
5746 /// deleting things.
5747 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5748 SDVTList VTs, ArrayRef<SDValue> Ops) {
5749 unsigned NumOps = Ops.size();
5750 // If an identical node already exists, use it.
5752 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5753 FoldingSetNodeID ID;
5754 AddNodeIDNode(ID, Opc, VTs, Ops);
5755 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5756 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5759 if (!RemoveNodeFromCSEMaps(N))
5762 // Start the morphing.
5764 N->ValueList = VTs.VTs;
5765 N->NumValues = VTs.NumVTs;
5767 // Clear the operands list, updating used nodes to remove this from their
5768 // use list. Keep track of any operands that become dead as a result.
5769 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5770 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5772 SDNode *Used = Use.getNode();
5774 if (Used->use_empty())
5775 DeadNodeSet.insert(Used);
5778 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5779 // Initialize the memory references information.
5780 MN->setMemRefs(nullptr, nullptr);
5781 // If NumOps is larger than the # of operands we can have in a
5782 // MachineSDNode, reallocate the operand list.
5783 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5784 if (MN->OperandsNeedDelete)
5785 delete[] MN->OperandList;
5786 if (NumOps > array_lengthof(MN->LocalOperands))
5787 // We're creating a final node that will live unmorphed for the
5788 // remainder of the current SelectionDAG iteration, so we can allocate
5789 // the operands directly out of a pool with no recycling metadata.
5790 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5791 Ops.data(), NumOps);
5793 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5794 MN->OperandsNeedDelete = false;
5796 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5798 // If NumOps is larger than the # of operands we currently have, reallocate
5799 // the operand list.
5800 if (NumOps > N->NumOperands) {
5801 if (N->OperandsNeedDelete)
5802 delete[] N->OperandList;
5803 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5804 N->OperandsNeedDelete = true;
5806 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5809 // Delete any nodes that are still dead after adding the uses for the
5811 if (!DeadNodeSet.empty()) {
5812 SmallVector<SDNode *, 16> DeadNodes;
5813 for (SDNode *N : DeadNodeSet)
5815 DeadNodes.push_back(N);
5816 RemoveDeadNodes(DeadNodes);
5820 CSEMap.InsertNode(N, IP); // Memoize the new node.
5825 /// getMachineNode - These are used for target selectors to create a new node
5826 /// with specified return type(s), MachineInstr opcode, and operands.
5828 /// Note that getMachineNode returns the resultant node. If there is already a
5829 /// node of the specified opcode and operands, it returns that node instead of
5830 /// the current one.
5832 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5833 SDVTList VTs = getVTList(VT);
5834 return getMachineNode(Opcode, dl, VTs, None);
5838 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5839 SDVTList VTs = getVTList(VT);
5840 SDValue Ops[] = { Op1 };
5841 return getMachineNode(Opcode, dl, VTs, Ops);
5845 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5846 SDValue Op1, SDValue Op2) {
5847 SDVTList VTs = getVTList(VT);
5848 SDValue Ops[] = { Op1, Op2 };
5849 return getMachineNode(Opcode, dl, VTs, Ops);
5853 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5854 SDValue Op1, SDValue Op2, SDValue Op3) {
5855 SDVTList VTs = getVTList(VT);
5856 SDValue Ops[] = { Op1, Op2, Op3 };
5857 return getMachineNode(Opcode, dl, VTs, Ops);
5861 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5862 ArrayRef<SDValue> Ops) {
5863 SDVTList VTs = getVTList(VT);
5864 return getMachineNode(Opcode, dl, VTs, Ops);
5868 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5869 SDVTList VTs = getVTList(VT1, VT2);
5870 return getMachineNode(Opcode, dl, VTs, None);
5874 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5875 EVT VT1, EVT VT2, SDValue Op1) {
5876 SDVTList VTs = getVTList(VT1, VT2);
5877 SDValue Ops[] = { Op1 };
5878 return getMachineNode(Opcode, dl, VTs, Ops);
5882 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5883 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5884 SDVTList VTs = getVTList(VT1, VT2);
5885 SDValue Ops[] = { Op1, Op2 };
5886 return getMachineNode(Opcode, dl, VTs, Ops);
5890 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5891 EVT VT1, EVT VT2, SDValue Op1,
5892 SDValue Op2, SDValue Op3) {
5893 SDVTList VTs = getVTList(VT1, VT2);
5894 SDValue Ops[] = { Op1, Op2, Op3 };
5895 return getMachineNode(Opcode, dl, VTs, Ops);
5899 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5901 ArrayRef<SDValue> Ops) {
5902 SDVTList VTs = getVTList(VT1, VT2);
5903 return getMachineNode(Opcode, dl, VTs, Ops);
5907 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5908 EVT VT1, EVT VT2, EVT VT3,
5909 SDValue Op1, SDValue Op2) {
5910 SDVTList VTs = getVTList(VT1, VT2, VT3);
5911 SDValue Ops[] = { Op1, Op2 };
5912 return getMachineNode(Opcode, dl, VTs, Ops);
5916 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5917 EVT VT1, EVT VT2, EVT VT3,
5918 SDValue Op1, SDValue Op2, SDValue Op3) {
5919 SDVTList VTs = getVTList(VT1, VT2, VT3);
5920 SDValue Ops[] = { Op1, Op2, Op3 };
5921 return getMachineNode(Opcode, dl, VTs, Ops);
5925 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5926 EVT VT1, EVT VT2, EVT VT3,
5927 ArrayRef<SDValue> Ops) {
5928 SDVTList VTs = getVTList(VT1, VT2, VT3);
5929 return getMachineNode(Opcode, dl, VTs, Ops);
5933 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5934 EVT VT2, EVT VT3, EVT VT4,
5935 ArrayRef<SDValue> Ops) {
5936 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5937 return getMachineNode(Opcode, dl, VTs, Ops);
5941 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5942 ArrayRef<EVT> ResultTys,
5943 ArrayRef<SDValue> Ops) {
5944 SDVTList VTs = getVTList(ResultTys);
5945 return getMachineNode(Opcode, dl, VTs, Ops);
5949 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5950 ArrayRef<SDValue> OpsArray) {
5951 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5954 const SDValue *Ops = OpsArray.data();
5955 unsigned NumOps = OpsArray.size();
5958 FoldingSetNodeID ID;
5959 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5961 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5962 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5966 // Allocate a new MachineSDNode.
5967 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5968 DL.getDebugLoc(), VTs);
5970 // Initialize the operands list.
5971 if (NumOps > array_lengthof(N->LocalOperands))
5972 // We're creating a final node that will live unmorphed for the
5973 // remainder of the current SelectionDAG iteration, so we can allocate
5974 // the operands directly out of a pool with no recycling metadata.
5975 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5978 N->InitOperands(N->LocalOperands, Ops, NumOps);
5979 N->OperandsNeedDelete = false;
5982 CSEMap.InsertNode(N, IP);
5988 /// getTargetExtractSubreg - A convenience function for creating
5989 /// TargetOpcode::EXTRACT_SUBREG nodes.
5991 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5993 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5994 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5995 VT, Operand, SRIdxVal);
5996 return SDValue(Subreg, 0);
5999 /// getTargetInsertSubreg - A convenience function for creating
6000 /// TargetOpcode::INSERT_SUBREG nodes.
6002 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6003 SDValue Operand, SDValue Subreg) {
6004 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6005 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6006 VT, Operand, Subreg, SRIdxVal);
6007 return SDValue(Result, 0);
6010 /// getNodeIfExists - Get the specified node if it's already available, or
6011 /// else return NULL.
6012 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6013 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6015 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6016 FoldingSetNodeID ID;
6017 AddNodeIDNode(ID, Opcode, VTList, Ops);
6018 if (isBinOpWithFlags(Opcode))
6019 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6021 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6027 /// getDbgValue - Creates a SDDbgValue node.
6030 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6031 unsigned R, bool IsIndirect, uint64_t Off,
6032 DebugLoc DL, unsigned O) {
6033 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6034 "Expected inlined-at fields to agree");
6035 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6039 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6040 const Value *C, uint64_t Off,
6041 DebugLoc DL, unsigned O) {
6042 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6043 "Expected inlined-at fields to agree");
6044 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6048 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6049 unsigned FI, uint64_t Off,
6050 DebugLoc DL, unsigned O) {
6051 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6052 "Expected inlined-at fields to agree");
6053 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6058 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6059 /// pointed to by a use iterator is deleted, increment the use iterator
6060 /// so that it doesn't dangle.
6062 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6063 SDNode::use_iterator &UI;
6064 SDNode::use_iterator &UE;
6066 void NodeDeleted(SDNode *N, SDNode *E) override {
6067 // Increment the iterator as needed.
6068 while (UI != UE && N == *UI)
6073 RAUWUpdateListener(SelectionDAG &d,
6074 SDNode::use_iterator &ui,
6075 SDNode::use_iterator &ue)
6076 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6081 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6082 /// This can cause recursive merging of nodes in the DAG.
6084 /// This version assumes From has a single result value.
6086 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6087 SDNode *From = FromN.getNode();
6088 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6089 "Cannot replace with this method!");
6090 assert(From != To.getNode() && "Cannot replace uses of with self");
6092 // Iterate over all the existing uses of From. New uses will be added
6093 // to the beginning of the use list, which we avoid visiting.
6094 // This specifically avoids visiting uses of From that arise while the
6095 // replacement is happening, because any such uses would be the result
6096 // of CSE: If an existing node looks like From after one of its operands
6097 // is replaced by To, we don't want to replace of all its users with To
6098 // too. See PR3018 for more info.
6099 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6100 RAUWUpdateListener Listener(*this, UI, UE);
6104 // This node is about to morph, remove its old self from the CSE maps.
6105 RemoveNodeFromCSEMaps(User);
6107 // A user can appear in a use list multiple times, and when this
6108 // happens the uses are usually next to each other in the list.
6109 // To help reduce the number of CSE recomputations, process all
6110 // the uses of this user that we can find this way.
6112 SDUse &Use = UI.getUse();
6115 } while (UI != UE && *UI == User);
6117 // Now that we have modified User, add it back to the CSE maps. If it
6118 // already exists there, recursively merge the results together.
6119 AddModifiedNodeToCSEMaps(User);
6122 // If we just RAUW'd the root, take note.
6123 if (FromN == getRoot())
6127 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6128 /// This can cause recursive merging of nodes in the DAG.
6130 /// This version assumes that for each value of From, there is a
6131 /// corresponding value in To in the same position with the same type.
6133 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6135 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6136 assert((!From->hasAnyUseOfValue(i) ||
6137 From->getValueType(i) == To->getValueType(i)) &&
6138 "Cannot use this version of ReplaceAllUsesWith!");
6141 // Handle the trivial case.
6145 // Iterate over just the existing users of From. See the comments in
6146 // the ReplaceAllUsesWith above.
6147 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6148 RAUWUpdateListener Listener(*this, UI, UE);
6152 // This node is about to morph, remove its old self from the CSE maps.
6153 RemoveNodeFromCSEMaps(User);
6155 // A user can appear in a use list multiple times, and when this
6156 // happens the uses are usually next to each other in the list.
6157 // To help reduce the number of CSE recomputations, process all
6158 // the uses of this user that we can find this way.
6160 SDUse &Use = UI.getUse();
6163 } while (UI != UE && *UI == User);
6165 // Now that we have modified User, add it back to the CSE maps. If it
6166 // already exists there, recursively merge the results together.
6167 AddModifiedNodeToCSEMaps(User);
6170 // If we just RAUW'd the root, take note.
6171 if (From == getRoot().getNode())
6172 setRoot(SDValue(To, getRoot().getResNo()));
6175 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6176 /// This can cause recursive merging of nodes in the DAG.
6178 /// This version can replace From with any result values. To must match the
6179 /// number and types of values returned by From.
6180 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6181 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6182 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6184 // Iterate over just the existing users of From. See the comments in
6185 // the ReplaceAllUsesWith above.
6186 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6187 RAUWUpdateListener Listener(*this, UI, UE);
6191 // This node is about to morph, remove its old self from the CSE maps.
6192 RemoveNodeFromCSEMaps(User);
6194 // A user can appear in a use list multiple times, and when this
6195 // happens the uses are usually next to each other in the list.
6196 // To help reduce the number of CSE recomputations, process all
6197 // the uses of this user that we can find this way.
6199 SDUse &Use = UI.getUse();
6200 const SDValue &ToOp = To[Use.getResNo()];
6203 } while (UI != UE && *UI == User);
6205 // Now that we have modified User, add it back to the CSE maps. If it
6206 // already exists there, recursively merge the results together.
6207 AddModifiedNodeToCSEMaps(User);
6210 // If we just RAUW'd the root, take note.
6211 if (From == getRoot().getNode())
6212 setRoot(SDValue(To[getRoot().getResNo()]));
6215 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6216 /// uses of other values produced by From.getNode() alone. The Deleted
6217 /// vector is handled the same way as for ReplaceAllUsesWith.
6218 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6219 // Handle the really simple, really trivial case efficiently.
6220 if (From == To) return;
6222 // Handle the simple, trivial, case efficiently.
6223 if (From.getNode()->getNumValues() == 1) {
6224 ReplaceAllUsesWith(From, To);
6228 // Iterate over just the existing users of From. See the comments in
6229 // the ReplaceAllUsesWith above.
6230 SDNode::use_iterator UI = From.getNode()->use_begin(),
6231 UE = From.getNode()->use_end();
6232 RAUWUpdateListener Listener(*this, UI, UE);
6235 bool UserRemovedFromCSEMaps = false;
6237 // A user can appear in a use list multiple times, and when this
6238 // happens the uses are usually next to each other in the list.
6239 // To help reduce the number of CSE recomputations, process all
6240 // the uses of this user that we can find this way.
6242 SDUse &Use = UI.getUse();
6244 // Skip uses of different values from the same node.
6245 if (Use.getResNo() != From.getResNo()) {
6250 // If this node hasn't been modified yet, it's still in the CSE maps,
6251 // so remove its old self from the CSE maps.
6252 if (!UserRemovedFromCSEMaps) {
6253 RemoveNodeFromCSEMaps(User);
6254 UserRemovedFromCSEMaps = true;
6259 } while (UI != UE && *UI == User);
6261 // We are iterating over all uses of the From node, so if a use
6262 // doesn't use the specific value, no changes are made.
6263 if (!UserRemovedFromCSEMaps)
6266 // Now that we have modified User, add it back to the CSE maps. If it
6267 // already exists there, recursively merge the results together.
6268 AddModifiedNodeToCSEMaps(User);
6271 // If we just RAUW'd the root, take note.
6272 if (From == getRoot())
6277 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6278 /// to record information about a use.
6285 /// operator< - Sort Memos by User.
6286 bool operator<(const UseMemo &L, const UseMemo &R) {
6287 return (intptr_t)L.User < (intptr_t)R.User;
6291 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6292 /// uses of other values produced by From.getNode() alone. The same value
6293 /// may appear in both the From and To list. The Deleted vector is
6294 /// handled the same way as for ReplaceAllUsesWith.
6295 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6298 // Handle the simple, trivial case efficiently.
6300 return ReplaceAllUsesOfValueWith(*From, *To);
6302 // Read up all the uses and make records of them. This helps
6303 // processing new uses that are introduced during the
6304 // replacement process.
6305 SmallVector<UseMemo, 4> Uses;
6306 for (unsigned i = 0; i != Num; ++i) {
6307 unsigned FromResNo = From[i].getResNo();
6308 SDNode *FromNode = From[i].getNode();
6309 for (SDNode::use_iterator UI = FromNode->use_begin(),
6310 E = FromNode->use_end(); UI != E; ++UI) {
6311 SDUse &Use = UI.getUse();
6312 if (Use.getResNo() == FromResNo) {
6313 UseMemo Memo = { *UI, i, &Use };
6314 Uses.push_back(Memo);
6319 // Sort the uses, so that all the uses from a given User are together.
6320 std::sort(Uses.begin(), Uses.end());
6322 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6323 UseIndex != UseIndexEnd; ) {
6324 // We know that this user uses some value of From. If it is the right
6325 // value, update it.
6326 SDNode *User = Uses[UseIndex].User;
6328 // This node is about to morph, remove its old self from the CSE maps.
6329 RemoveNodeFromCSEMaps(User);
6331 // The Uses array is sorted, so all the uses for a given User
6332 // are next to each other in the list.
6333 // To help reduce the number of CSE recomputations, process all
6334 // the uses of this user that we can find this way.
6336 unsigned i = Uses[UseIndex].Index;
6337 SDUse &Use = *Uses[UseIndex].Use;
6341 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6343 // Now that we have modified User, add it back to the CSE maps. If it
6344 // already exists there, recursively merge the results together.
6345 AddModifiedNodeToCSEMaps(User);
6349 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6350 /// based on their topological order. It returns the maximum id and a vector
6351 /// of the SDNodes* in assigned order by reference.
6352 unsigned SelectionDAG::AssignTopologicalOrder() {
6354 unsigned DAGSize = 0;
6356 // SortedPos tracks the progress of the algorithm. Nodes before it are
6357 // sorted, nodes after it are unsorted. When the algorithm completes
6358 // it is at the end of the list.
6359 allnodes_iterator SortedPos = allnodes_begin();
6361 // Visit all the nodes. Move nodes with no operands to the front of
6362 // the list immediately. Annotate nodes that do have operands with their
6363 // operand count. Before we do this, the Node Id fields of the nodes
6364 // may contain arbitrary values. After, the Node Id fields for nodes
6365 // before SortedPos will contain the topological sort index, and the
6366 // Node Id fields for nodes At SortedPos and after will contain the
6367 // count of outstanding operands.
6368 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6370 checkForCycles(N, this);
6371 unsigned Degree = N->getNumOperands();
6373 // A node with no uses, add it to the result array immediately.
6374 N->setNodeId(DAGSize++);
6375 allnodes_iterator Q = N;
6377 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6378 assert(SortedPos != AllNodes.end() && "Overran node list");
6381 // Temporarily use the Node Id as scratch space for the degree count.
6382 N->setNodeId(Degree);
6386 // Visit all the nodes. As we iterate, move nodes into sorted order,
6387 // such that by the time the end is reached all nodes will be sorted.
6388 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6390 checkForCycles(N, this);
6391 // N is in sorted position, so all its uses have one less operand
6392 // that needs to be sorted.
6393 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6396 unsigned Degree = P->getNodeId();
6397 assert(Degree != 0 && "Invalid node degree");
6400 // All of P's operands are sorted, so P may sorted now.
6401 P->setNodeId(DAGSize++);
6403 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6404 assert(SortedPos != AllNodes.end() && "Overran node list");
6407 // Update P's outstanding operand count.
6408 P->setNodeId(Degree);
6411 if (I == SortedPos) {
6414 dbgs() << "Overran sorted position:\n";
6415 S->dumprFull(this); dbgs() << "\n";
6416 dbgs() << "Checking if this is due to cycles\n";
6417 checkForCycles(this, true);
6419 llvm_unreachable(nullptr);
6423 assert(SortedPos == AllNodes.end() &&
6424 "Topological sort incomplete!");
6425 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6426 "First node in topological sort is not the entry token!");
6427 assert(AllNodes.front().getNodeId() == 0 &&
6428 "First node in topological sort has non-zero id!");
6429 assert(AllNodes.front().getNumOperands() == 0 &&
6430 "First node in topological sort has operands!");
6431 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6432 "Last node in topologic sort has unexpected id!");
6433 assert(AllNodes.back().use_empty() &&
6434 "Last node in topologic sort has users!");
6435 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6439 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6440 /// value is produced by SD.
6441 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6443 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6444 SD->setHasDebugValue(true);
6446 DbgInfo->add(DB, SD, isParameter);
6449 /// TransferDbgValues - Transfer SDDbgValues.
6450 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6451 if (From == To || !From.getNode()->getHasDebugValue())
6453 SDNode *FromNode = From.getNode();
6454 SDNode *ToNode = To.getNode();
6455 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6456 SmallVector<SDDbgValue *, 2> ClonedDVs;
6457 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6459 SDDbgValue *Dbg = *I;
6460 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6462 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6463 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6464 Dbg->getDebugLoc(), Dbg->getOrder());
6465 ClonedDVs.push_back(Clone);
6468 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6469 E = ClonedDVs.end(); I != E; ++I)
6470 AddDbgValue(*I, ToNode, false);
6473 //===----------------------------------------------------------------------===//
6475 //===----------------------------------------------------------------------===//
6477 HandleSDNode::~HandleSDNode() {
6481 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6482 DebugLoc DL, const GlobalValue *GA,
6483 EVT VT, int64_t o, unsigned char TF)
6484 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6488 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6489 SDValue X, unsigned SrcAS,
6491 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6492 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6494 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6495 EVT memvt, MachineMemOperand *mmo)
6496 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6497 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6498 MMO->isNonTemporal(), MMO->isInvariant());
6499 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6500 assert(isNonTemporal() == MMO->isNonTemporal() &&
6501 "Non-temporal encoding error!");
6502 // We check here that the size of the memory operand fits within the size of
6503 // the MMO. This is because the MMO might indicate only a possible address
6504 // range instead of specifying the affected memory addresses precisely.
6505 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6508 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6509 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6510 : SDNode(Opc, Order, dl, VTs, Ops),
6511 MemoryVT(memvt), MMO(mmo) {
6512 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6513 MMO->isNonTemporal(), MMO->isInvariant());
6514 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6515 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6518 /// Profile - Gather unique data for the node.
6520 void SDNode::Profile(FoldingSetNodeID &ID) const {
6521 AddNodeIDNode(ID, this);
6526 std::vector<EVT> VTs;
6529 VTs.reserve(MVT::LAST_VALUETYPE);
6530 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6531 VTs.push_back(MVT((MVT::SimpleValueType)i));
6536 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6537 static ManagedStatic<EVTArray> SimpleVTArray;
6538 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6540 /// getValueTypeList - Return a pointer to the specified value type.
6542 const EVT *SDNode::getValueTypeList(EVT VT) {
6543 if (VT.isExtended()) {
6544 sys::SmartScopedLock<true> Lock(*VTMutex);
6545 return &(*EVTs->insert(VT).first);
6547 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6548 "Value type out of range!");
6549 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6553 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6554 /// indicated value. This method ignores uses of other values defined by this
6556 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6557 assert(Value < getNumValues() && "Bad value!");
6559 // TODO: Only iterate over uses of a given value of the node
6560 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6561 if (UI.getUse().getResNo() == Value) {
6568 // Found exactly the right number of uses?
6573 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6574 /// value. This method ignores uses of other values defined by this operation.
6575 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6576 assert(Value < getNumValues() && "Bad value!");
6578 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6579 if (UI.getUse().getResNo() == Value)
6586 /// isOnlyUserOf - Return true if this node is the only use of N.
6588 bool SDNode::isOnlyUserOf(SDNode *N) const {
6590 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6601 /// isOperand - Return true if this node is an operand of N.
6603 bool SDValue::isOperandOf(SDNode *N) const {
6604 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6605 if (*this == N->getOperand(i))
6610 bool SDNode::isOperandOf(SDNode *N) const {
6611 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6612 if (this == N->OperandList[i].getNode())
6617 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6618 /// be a chain) reaches the specified operand without crossing any
6619 /// side-effecting instructions on any chain path. In practice, this looks
6620 /// through token factors and non-volatile loads. In order to remain efficient,
6621 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6622 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6623 unsigned Depth) const {
6624 if (*this == Dest) return true;
6626 // Don't search too deeply, we just want to be able to see through
6627 // TokenFactor's etc.
6628 if (Depth == 0) return false;
6630 // If this is a token factor, all inputs to the TF happen in parallel. If any
6631 // of the operands of the TF does not reach dest, then we cannot do the xform.
6632 if (getOpcode() == ISD::TokenFactor) {
6633 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6634 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6639 // Loads don't have side effects, look through them.
6640 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6641 if (!Ld->isVolatile())
6642 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6647 /// hasPredecessor - Return true if N is a predecessor of this node.
6648 /// N is either an operand of this node, or can be reached by recursively
6649 /// traversing up the operands.
6650 /// NOTE: This is an expensive method. Use it carefully.
6651 bool SDNode::hasPredecessor(const SDNode *N) const {
6652 SmallPtrSet<const SDNode *, 32> Visited;
6653 SmallVector<const SDNode *, 16> Worklist;
6654 return hasPredecessorHelper(N, Visited, Worklist);
6658 SDNode::hasPredecessorHelper(const SDNode *N,
6659 SmallPtrSetImpl<const SDNode *> &Visited,
6660 SmallVectorImpl<const SDNode *> &Worklist) const {
6661 if (Visited.empty()) {
6662 Worklist.push_back(this);
6664 // Take a look in the visited set. If we've already encountered this node
6665 // we needn't search further.
6666 if (Visited.count(N))
6670 // Haven't visited N yet. Continue the search.
6671 while (!Worklist.empty()) {
6672 const SDNode *M = Worklist.pop_back_val();
6673 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6674 SDNode *Op = M->getOperand(i).getNode();
6675 if (Visited.insert(Op).second)
6676 Worklist.push_back(Op);
6685 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6686 assert(Num < NumOperands && "Invalid child # of SDNode!");
6687 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6690 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6691 assert(N->getNumValues() == 1 &&
6692 "Can't unroll a vector with multiple results!");
6694 EVT VT = N->getValueType(0);
6695 unsigned NE = VT.getVectorNumElements();
6696 EVT EltVT = VT.getVectorElementType();
6699 SmallVector<SDValue, 8> Scalars;
6700 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6702 // If ResNE is 0, fully unroll the vector op.
6705 else if (NE > ResNE)
6709 for (i= 0; i != NE; ++i) {
6710 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6711 SDValue Operand = N->getOperand(j);
6712 EVT OperandVT = Operand.getValueType();
6713 if (OperandVT.isVector()) {
6714 // A vector operand; extract a single element.
6715 EVT OperandEltVT = OperandVT.getVectorElementType();
6716 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6719 getConstant(i, dl, TLI->getVectorIdxTy()));
6721 // A scalar operand; just use it as is.
6722 Operands[j] = Operand;
6726 switch (N->getOpcode()) {
6728 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6731 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6738 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6739 getShiftAmountOperand(Operands[0].getValueType(),
6742 case ISD::SIGN_EXTEND_INREG:
6743 case ISD::FP_ROUND_INREG: {
6744 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6745 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6747 getValueType(ExtVT)));
6752 for (; i < ResNE; ++i)
6753 Scalars.push_back(getUNDEF(EltVT));
6755 return getNode(ISD::BUILD_VECTOR, dl,
6756 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6760 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6761 /// location that is 'Dist' units away from the location that the 'Base' load
6762 /// is loading from.
6763 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6764 unsigned Bytes, int Dist) const {
6765 if (LD->getChain() != Base->getChain())
6767 EVT VT = LD->getValueType(0);
6768 if (VT.getSizeInBits() / 8 != Bytes)
6771 SDValue Loc = LD->getOperand(1);
6772 SDValue BaseLoc = Base->getOperand(1);
6773 if (Loc.getOpcode() == ISD::FrameIndex) {
6774 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6776 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6777 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6778 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6779 int FS = MFI->getObjectSize(FI);
6780 int BFS = MFI->getObjectSize(BFI);
6781 if (FS != BFS || FS != (int)Bytes) return false;
6782 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6786 if (isBaseWithConstantOffset(Loc)) {
6787 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6788 if (Loc.getOperand(0) == BaseLoc) {
6789 // If the base location is a simple address with no offset itself, then
6790 // the second load's first add operand should be the base address.
6791 if (LocOffset == Dist * (int)Bytes)
6793 } else if (isBaseWithConstantOffset(BaseLoc)) {
6794 // The base location itself has an offset, so subtract that value from the
6795 // second load's offset before comparing to distance * size.
6797 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6798 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6799 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6804 const GlobalValue *GV1 = nullptr;
6805 const GlobalValue *GV2 = nullptr;
6806 int64_t Offset1 = 0;
6807 int64_t Offset2 = 0;
6808 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6809 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6810 if (isGA1 && isGA2 && GV1 == GV2)
6811 return Offset1 == (Offset2 + Dist*Bytes);
6816 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6817 /// it cannot be inferred.
6818 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6819 // If this is a GlobalAddress + cst, return the alignment.
6820 const GlobalValue *GV;
6821 int64_t GVOffset = 0;
6822 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6823 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6824 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6825 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6826 *TLI->getDataLayout());
6827 unsigned AlignBits = KnownZero.countTrailingOnes();
6828 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6830 return MinAlign(Align, GVOffset);
6833 // If this is a direct reference to a stack slot, use information about the
6834 // stack slot's alignment.
6835 int FrameIdx = 1 << 31;
6836 int64_t FrameOffset = 0;
6837 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6838 FrameIdx = FI->getIndex();
6839 } else if (isBaseWithConstantOffset(Ptr) &&
6840 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6842 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6843 FrameOffset = Ptr.getConstantOperandVal(1);
6846 if (FrameIdx != (1 << 31)) {
6847 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6848 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6856 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6857 /// which is split (or expanded) into two not necessarily identical pieces.
6858 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6859 // Currently all types are split in half.
6861 if (!VT.isVector()) {
6862 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6864 unsigned NumElements = VT.getVectorNumElements();
6865 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6866 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6869 return std::make_pair(LoVT, HiVT);
6872 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6874 std::pair<SDValue, SDValue>
6875 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6877 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6878 N.getValueType().getVectorNumElements() &&
6879 "More vector elements requested than available!");
6881 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6882 getConstant(0, DL, TLI->getVectorIdxTy()));
6883 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6884 getConstant(LoVT.getVectorNumElements(), DL,
6885 TLI->getVectorIdxTy()));
6886 return std::make_pair(Lo, Hi);
6889 void SelectionDAG::ExtractVectorElements(SDValue Op,
6890 SmallVectorImpl<SDValue> &Args,
6891 unsigned Start, unsigned Count) {
6892 EVT VT = Op.getValueType();
6894 Count = VT.getVectorNumElements();
6896 EVT EltVT = VT.getVectorElementType();
6897 EVT IdxTy = TLI->getVectorIdxTy();
6899 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6900 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6901 Op, getConstant(i, SL, IdxTy)));
6905 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6906 unsigned GlobalAddressSDNode::getAddressSpace() const {
6907 return getGlobal()->getType()->getAddressSpace();
6911 Type *ConstantPoolSDNode::getType() const {
6912 if (isMachineConstantPoolEntry())
6913 return Val.MachineCPVal->getType();
6914 return Val.ConstVal->getType();
6917 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6919 unsigned &SplatBitSize,
6921 unsigned MinSplatBits,
6922 bool isBigEndian) const {
6923 EVT VT = getValueType(0);
6924 assert(VT.isVector() && "Expected a vector type");
6925 unsigned sz = VT.getSizeInBits();
6926 if (MinSplatBits > sz)
6929 SplatValue = APInt(sz, 0);
6930 SplatUndef = APInt(sz, 0);
6932 // Get the bits. Bits with undefined values (when the corresponding element
6933 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6934 // in SplatValue. If any of the values are not constant, give up and return
6936 unsigned int nOps = getNumOperands();
6937 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6938 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6940 for (unsigned j = 0; j < nOps; ++j) {
6941 unsigned i = isBigEndian ? nOps-1-j : j;
6942 SDValue OpVal = getOperand(i);
6943 unsigned BitPos = j * EltBitSize;
6945 if (OpVal.getOpcode() == ISD::UNDEF)
6946 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6947 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6948 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6949 zextOrTrunc(sz) << BitPos;
6950 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6951 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6956 // The build_vector is all constants or undefs. Find the smallest element
6957 // size that splats the vector.
6959 HasAnyUndefs = (SplatUndef != 0);
6962 unsigned HalfSize = sz / 2;
6963 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6964 APInt LowValue = SplatValue.trunc(HalfSize);
6965 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6966 APInt LowUndef = SplatUndef.trunc(HalfSize);
6968 // If the two halves do not match (ignoring undef bits), stop here.
6969 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6970 MinSplatBits > HalfSize)
6973 SplatValue = HighValue | LowValue;
6974 SplatUndef = HighUndef & LowUndef;
6983 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6984 if (UndefElements) {
6985 UndefElements->clear();
6986 UndefElements->resize(getNumOperands());
6989 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6990 SDValue Op = getOperand(i);
6991 if (Op.getOpcode() == ISD::UNDEF) {
6993 (*UndefElements)[i] = true;
6994 } else if (!Splatted) {
6996 } else if (Splatted != Op) {
7002 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7003 "Can only have a splat without a constant for all undefs.");
7004 return getOperand(0);
7011 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7012 return dyn_cast_or_null<ConstantSDNode>(
7013 getSplatValue(UndefElements).getNode());
7017 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7018 return dyn_cast_or_null<ConstantFPSDNode>(
7019 getSplatValue(UndefElements).getNode());
7022 bool BuildVectorSDNode::isConstant() const {
7023 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7024 unsigned Opc = getOperand(i).getOpcode();
7025 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7031 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7032 // Find the first non-undef value in the shuffle mask.
7034 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7037 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7039 // Make sure all remaining elements are either undef or the same as the first
7041 for (int Idx = Mask[i]; i != e; ++i)
7042 if (Mask[i] >= 0 && Mask[i] != Idx)
7048 static void checkForCyclesHelper(const SDNode *N,
7049 SmallPtrSetImpl<const SDNode*> &Visited,
7050 SmallPtrSetImpl<const SDNode*> &Checked,
7051 const llvm::SelectionDAG *DAG) {
7052 // If this node has already been checked, don't check it again.
7053 if (Checked.count(N))
7056 // If a node has already been visited on this depth-first walk, reject it as
7058 if (!Visited.insert(N).second) {
7059 errs() << "Detected cycle in SelectionDAG\n";
7060 dbgs() << "Offending node:\n";
7061 N->dumprFull(DAG); dbgs() << "\n";
7065 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7066 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7073 void llvm::checkForCycles(const llvm::SDNode *N,
7074 const llvm::SelectionDAG *DAG,
7082 assert(N && "Checking nonexistent SDNode");
7083 SmallPtrSet<const SDNode*, 32> visited;
7084 SmallPtrSet<const SDNode*, 32> checked;
7085 checkForCyclesHelper(N, visited, checked, DAG);
7090 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7091 checkForCycles(DAG->getRoot().getNode(), DAG, force);