1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
206 SDValue Op = N->getOperand(i);
207 if (Op.getOpcode() == ISD::UNDEF)
209 if (!isa<ConstantFPSDNode>(Op))
215 /// isScalarToVector - Return true if the specified node is a
216 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
217 /// element is not an undef.
218 bool ISD::isScalarToVector(const SDNode *N) {
219 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
222 if (N->getOpcode() != ISD::BUILD_VECTOR)
224 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226 unsigned NumElems = N->getNumOperands();
229 for (unsigned i = 1; i < NumElems; ++i) {
230 SDValue V = N->getOperand(i);
231 if (V.getOpcode() != ISD::UNDEF)
237 /// allOperandsUndef - Return true if the node has at least one operand
238 /// and all operands of the specified node are ISD::UNDEF.
239 bool ISD::allOperandsUndef(const SDNode *N) {
240 // Return false if the node has no operands.
241 // This is "logically inconsistent" with the definition of "all" but
242 // is probably the desired behavior.
243 if (N->getNumOperands() == 0)
246 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
247 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
253 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
256 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258 return ISD::SIGN_EXTEND;
260 return ISD::ZERO_EXTEND;
265 llvm_unreachable("Invalid LoadExtType");
268 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
269 /// when given the operation for (X op Y).
270 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
271 // To perform this operation, we just need to swap the L and G bits of the
273 unsigned OldL = (Operation >> 2) & 1;
274 unsigned OldG = (Operation >> 1) & 1;
275 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
276 (OldL << 1) | // New G bit
277 (OldG << 2)); // New L bit.
280 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
281 /// 'op' is a valid SetCC operation.
282 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
283 unsigned Operation = Op;
285 Operation ^= 7; // Flip L, G, E bits, but not U.
287 Operation ^= 15; // Flip all of the condition bits.
289 if (Operation > ISD::SETTRUE2)
290 Operation &= ~8; // Don't let N and U bits get set.
292 return ISD::CondCode(Operation);
296 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
297 /// signed operation and 2 if the result is an unsigned comparison. Return zero
298 /// if the operation does not depend on the sign of the input (setne and seteq).
299 static int isSignedOp(ISD::CondCode Opcode) {
301 default: llvm_unreachable("Illegal integer setcc operation!");
303 case ISD::SETNE: return 0;
307 case ISD::SETGE: return 1;
311 case ISD::SETUGE: return 2;
315 /// getSetCCOrOperation - Return the result of a logical OR between different
316 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
317 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
322 // Cannot fold a signed integer setcc with an unsigned integer setcc.
323 return ISD::SETCC_INVALID;
325 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
327 // If the N and U bits get set then the resultant comparison DOES suddenly
328 // care about orderedness, and is true when ordered.
329 if (Op > ISD::SETTRUE2)
330 Op &= ~16; // Clear the U bit if the N bit is set.
332 // Canonicalize illegal integer setcc's.
333 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
336 return ISD::CondCode(Op);
339 /// getSetCCAndOperation - Return the result of a logical AND between different
340 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
341 /// function returns zero if it is not possible to represent the resultant
343 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
346 // Cannot fold a signed setcc with an unsigned setcc.
347 return ISD::SETCC_INVALID;
349 // Combine all of the condition bits.
350 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352 // Canonicalize illegal integer setcc's.
356 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
357 case ISD::SETOEQ: // SETEQ & SETU[LG]E
358 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
359 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
360 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
367 //===----------------------------------------------------------------------===//
368 // SDNode Profile Support
369 //===----------------------------------------------------------------------===//
371 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
377 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
378 /// solely with their pointer.
379 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
380 ID.AddPointer(VTList.VTs);
383 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 static void AddNodeIDOperands(FoldingSetNodeID &ID,
386 ArrayRef<SDValue> Ops) {
387 for (auto& Op : Ops) {
388 ID.AddPointer(Op.getNode());
389 ID.AddInteger(Op.getResNo());
393 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 static void AddNodeIDOperands(FoldingSetNodeID &ID,
396 ArrayRef<SDUse> Ops) {
397 for (auto& Op : Ops) {
398 ID.AddPointer(Op.getNode());
399 ID.AddInteger(Op.getResNo());
403 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
407 ID.AddBoolean(exact);
410 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
411 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
412 bool nuw, bool nsw, bool exact) {
413 if (isBinOpWithFlags(Opcode))
414 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
417 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
418 SDVTList VTList, ArrayRef<SDValue> OpList) {
419 AddNodeIDOpcode(ID, OpC);
420 AddNodeIDValueTypes(ID, VTList);
421 AddNodeIDOperands(ID, OpList);
424 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
426 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
427 switch (N->getOpcode()) {
428 case ISD::TargetExternalSymbol:
429 case ISD::ExternalSymbol:
430 llvm_unreachable("Should only be used on nodes with operands");
431 default: break; // Normal nodes don't need extra info.
432 case ISD::TargetConstant:
433 case ISD::Constant: {
434 const ConstantSDNode *C = cast<ConstantSDNode>(N);
435 ID.AddPointer(C->getConstantIntValue());
436 ID.AddBoolean(C->isOpaque());
439 case ISD::TargetConstantFP:
440 case ISD::ConstantFP: {
441 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
444 case ISD::TargetGlobalAddress:
445 case ISD::GlobalAddress:
446 case ISD::TargetGlobalTLSAddress:
447 case ISD::GlobalTLSAddress: {
448 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
449 ID.AddPointer(GA->getGlobal());
450 ID.AddInteger(GA->getOffset());
451 ID.AddInteger(GA->getTargetFlags());
452 ID.AddInteger(GA->getAddressSpace());
455 case ISD::BasicBlock:
456 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
459 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
461 case ISD::RegisterMask:
462 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
465 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
467 case ISD::FrameIndex:
468 case ISD::TargetFrameIndex:
469 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
472 case ISD::TargetJumpTable:
473 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
476 case ISD::ConstantPool:
477 case ISD::TargetConstantPool: {
478 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
479 ID.AddInteger(CP->getAlignment());
480 ID.AddInteger(CP->getOffset());
481 if (CP->isMachineConstantPoolEntry())
482 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
484 ID.AddPointer(CP->getConstVal());
485 ID.AddInteger(CP->getTargetFlags());
488 case ISD::TargetIndex: {
489 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
490 ID.AddInteger(TI->getIndex());
491 ID.AddInteger(TI->getOffset());
492 ID.AddInteger(TI->getTargetFlags());
496 const LoadSDNode *LD = cast<LoadSDNode>(N);
497 ID.AddInteger(LD->getMemoryVT().getRawBits());
498 ID.AddInteger(LD->getRawSubclassData());
499 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
503 const StoreSDNode *ST = cast<StoreSDNode>(N);
504 ID.AddInteger(ST->getMemoryVT().getRawBits());
505 ID.AddInteger(ST->getRawSubclassData());
506 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
517 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
518 AddBinaryNodeIDCustom(
519 ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
520 BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
523 case ISD::ATOMIC_CMP_SWAP:
524 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
525 case ISD::ATOMIC_SWAP:
526 case ISD::ATOMIC_LOAD_ADD:
527 case ISD::ATOMIC_LOAD_SUB:
528 case ISD::ATOMIC_LOAD_AND:
529 case ISD::ATOMIC_LOAD_OR:
530 case ISD::ATOMIC_LOAD_XOR:
531 case ISD::ATOMIC_LOAD_NAND:
532 case ISD::ATOMIC_LOAD_MIN:
533 case ISD::ATOMIC_LOAD_MAX:
534 case ISD::ATOMIC_LOAD_UMIN:
535 case ISD::ATOMIC_LOAD_UMAX:
536 case ISD::ATOMIC_LOAD:
537 case ISD::ATOMIC_STORE: {
538 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
539 ID.AddInteger(AT->getMemoryVT().getRawBits());
540 ID.AddInteger(AT->getRawSubclassData());
541 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
544 case ISD::PREFETCH: {
545 const MemSDNode *PF = cast<MemSDNode>(N);
546 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
549 case ISD::VECTOR_SHUFFLE: {
550 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
551 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
553 ID.AddInteger(SVN->getMaskElt(i));
556 case ISD::TargetBlockAddress:
557 case ISD::BlockAddress: {
558 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
559 ID.AddPointer(BA->getBlockAddress());
560 ID.AddInteger(BA->getOffset());
561 ID.AddInteger(BA->getTargetFlags());
564 } // end switch (N->getOpcode())
566 // Target specific memory nodes could also have address spaces to check.
567 if (N->isTargetMemoryOpcode())
568 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
571 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
573 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
574 AddNodeIDOpcode(ID, N->getOpcode());
575 // Add the return value info.
576 AddNodeIDValueTypes(ID, N->getVTList());
577 // Add the operand info.
578 AddNodeIDOperands(ID, N->ops());
580 // Handle SDNode leafs with special info.
581 AddNodeIDCustom(ID, N);
584 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
585 /// the CSE map that carries volatility, temporalness, indexing mode, and
586 /// extension/truncation information.
588 static inline unsigned
589 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
590 bool isNonTemporal, bool isInvariant) {
591 assert((ConvType & 3) == ConvType &&
592 "ConvType may not require more than 2 bits!");
593 assert((AM & 7) == AM &&
594 "AM may not require more than 3 bits!");
598 (isNonTemporal << 6) |
602 //===----------------------------------------------------------------------===//
603 // SelectionDAG Class
604 //===----------------------------------------------------------------------===//
606 /// doNotCSE - Return true if CSE should not be performed for this node.
607 static bool doNotCSE(SDNode *N) {
608 if (N->getValueType(0) == MVT::Glue)
609 return true; // Never CSE anything that produces a flag.
611 switch (N->getOpcode()) {
613 case ISD::HANDLENODE:
615 return true; // Never CSE these nodes.
618 // Check that remaining values produced are not flags.
619 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
620 if (N->getValueType(i) == MVT::Glue)
621 return true; // Never CSE anything that produces a flag.
626 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
628 void SelectionDAG::RemoveDeadNodes() {
629 // Create a dummy node (which is not added to allnodes), that adds a reference
630 // to the root node, preventing it from being deleted.
631 HandleSDNode Dummy(getRoot());
633 SmallVector<SDNode*, 128> DeadNodes;
635 // Add all obviously-dead nodes to the DeadNodes worklist.
636 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
638 DeadNodes.push_back(I);
640 RemoveDeadNodes(DeadNodes);
642 // If the root changed (e.g. it was a dead load, update the root).
643 setRoot(Dummy.getValue());
646 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
647 /// given list, and any nodes that become unreachable as a result.
648 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
650 // Process the worklist, deleting the nodes and adding their uses to the
652 while (!DeadNodes.empty()) {
653 SDNode *N = DeadNodes.pop_back_val();
655 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
656 DUL->NodeDeleted(N, nullptr);
658 // Take the node out of the appropriate CSE map.
659 RemoveNodeFromCSEMaps(N);
661 // Next, brutally remove the operand list. This is safe to do, as there are
662 // no cycles in the graph.
663 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
665 SDNode *Operand = Use.getNode();
668 // Now that we removed this operand, see if there are no uses of it left.
669 if (Operand->use_empty())
670 DeadNodes.push_back(Operand);
677 void SelectionDAG::RemoveDeadNode(SDNode *N){
678 SmallVector<SDNode*, 16> DeadNodes(1, N);
680 // Create a dummy node that adds a reference to the root node, preventing
681 // it from being deleted. (This matters if the root is an operand of the
683 HandleSDNode Dummy(getRoot());
685 RemoveDeadNodes(DeadNodes);
688 void SelectionDAG::DeleteNode(SDNode *N) {
689 // First take this out of the appropriate CSE map.
690 RemoveNodeFromCSEMaps(N);
692 // Finally, remove uses due to operands of this node, remove from the
693 // AllNodes list, and delete the node.
694 DeleteNodeNotInCSEMaps(N);
697 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
698 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
699 assert(N->use_empty() && "Cannot delete a node that is not dead!");
701 // Drop all of the operands and decrement used node's use counts.
707 void SDDbgInfo::erase(const SDNode *Node) {
708 DbgValMapType::iterator I = DbgValMap.find(Node);
709 if (I == DbgValMap.end())
711 for (auto &Val: I->second)
712 Val->setIsInvalidated();
716 void SelectionDAG::DeallocateNode(SDNode *N) {
717 if (N->OperandsNeedDelete)
718 delete[] N->OperandList;
720 // Set the opcode to DELETED_NODE to help catch bugs when node
721 // memory is reallocated.
722 N->NodeType = ISD::DELETED_NODE;
724 NodeAllocator.Deallocate(AllNodes.remove(N));
726 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
727 // them and forget about that node.
732 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
733 static void VerifySDNode(SDNode *N) {
734 switch (N->getOpcode()) {
737 case ISD::BUILD_PAIR: {
738 EVT VT = N->getValueType(0);
739 assert(N->getNumValues() == 1 && "Too many results!");
740 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
741 "Wrong return type!");
742 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
743 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
744 "Mismatched operand types!");
745 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
746 "Wrong operand type!");
747 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
748 "Wrong return type size");
751 case ISD::BUILD_VECTOR: {
752 assert(N->getNumValues() == 1 && "Too many results!");
753 assert(N->getValueType(0).isVector() && "Wrong return type!");
754 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
755 "Wrong number of operands!");
756 EVT EltVT = N->getValueType(0).getVectorElementType();
757 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
758 assert((I->getValueType() == EltVT ||
759 (EltVT.isInteger() && I->getValueType().isInteger() &&
760 EltVT.bitsLE(I->getValueType()))) &&
761 "Wrong operand type!");
762 assert(I->getValueType() == N->getOperand(0).getValueType() &&
763 "Operands must all have the same type");
771 /// \brief Insert a newly allocated node into the DAG.
773 /// Handles insertion into the all nodes list and CSE map, as well as
774 /// verification and other common operations when a new node is allocated.
775 void SelectionDAG::InsertNode(SDNode *N) {
776 AllNodes.push_back(N);
782 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
783 /// correspond to it. This is useful when we're about to delete or repurpose
784 /// the node. We don't want future request for structurally identical nodes
785 /// to return N anymore.
786 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
788 switch (N->getOpcode()) {
789 case ISD::HANDLENODE: return false; // noop.
791 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
792 "Cond code doesn't exist!");
793 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
794 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
796 case ISD::ExternalSymbol:
797 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
799 case ISD::TargetExternalSymbol: {
800 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
801 Erased = TargetExternalSymbols.erase(
802 std::pair<std::string,unsigned char>(ESN->getSymbol(),
803 ESN->getTargetFlags()));
806 case ISD::VALUETYPE: {
807 EVT VT = cast<VTSDNode>(N)->getVT();
808 if (VT.isExtended()) {
809 Erased = ExtendedValueTypeNodes.erase(VT);
811 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
812 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
817 // Remove it from the CSE Map.
818 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
819 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
820 Erased = CSEMap.RemoveNode(N);
824 // Verify that the node was actually in one of the CSE maps, unless it has a
825 // flag result (which cannot be CSE'd) or is one of the special cases that are
826 // not subject to CSE.
827 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
828 !N->isMachineOpcode() && !doNotCSE(N)) {
831 llvm_unreachable("Node is not in map!");
837 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
838 /// maps and modified in place. Add it back to the CSE maps, unless an identical
839 /// node already exists, in which case transfer all its users to the existing
840 /// node. This transfer can potentially trigger recursive merging.
843 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
844 // For node types that aren't CSE'd, just act as if no identical node
847 SDNode *Existing = CSEMap.GetOrInsertNode(N);
849 // If there was already an existing matching node, use ReplaceAllUsesWith
850 // to replace the dead one with the existing one. This can cause
851 // recursive merging of other unrelated nodes down the line.
852 ReplaceAllUsesWith(N, Existing);
854 // N is now dead. Inform the listeners and delete it.
855 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
856 DUL->NodeDeleted(N, Existing);
857 DeleteNodeNotInCSEMaps(N);
862 // If the node doesn't already exist, we updated it. Inform listeners.
863 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified. If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take. If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
876 SDValue Ops[] = { Op };
878 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
879 AddNodeIDCustom(ID, N);
880 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
884 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
885 /// were replaced with those specified. If this node is never memoized,
886 /// return null, otherwise return a pointer to the slot it would take. If a
887 /// node already exists with these operands, the slot will be non-null.
888 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
889 SDValue Op1, SDValue Op2,
894 SDValue Ops[] = { Op1, Op2 };
896 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897 AddNodeIDCustom(ID, N);
898 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
903 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
904 /// were replaced with those specified. If this node is never memoized,
905 /// return null, otherwise return a pointer to the slot it would take. If a
906 /// node already exists with these operands, the slot will be non-null.
907 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
913 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
914 AddNodeIDCustom(ID, N);
915 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
919 /// getEVTAlignment - Compute the default alignment value for the
922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
923 Type *Ty = VT == MVT::iPTR ?
924 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
925 VT.getTypeForEVT(*getContext());
927 return TLI->getDataLayout()->getABITypeAlignment(Ty);
930 // EntryNode could meaningfully have debug info if we can find it...
931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
932 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
935 UpdateListeners(nullptr) {
936 AllNodes.push_back(&EntryNode);
937 DbgInfo = new SDDbgInfo();
940 void SelectionDAG::init(MachineFunction &mf) {
942 TLI = getSubtarget().getTargetLowering();
943 TSI = getSubtarget().getSelectionDAGInfo();
944 Context = &mf.getFunction()->getContext();
947 SelectionDAG::~SelectionDAG() {
948 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
953 void SelectionDAG::allnodes_clear() {
954 assert(&*AllNodes.begin() == &EntryNode);
955 AllNodes.remove(AllNodes.begin());
956 while (!AllNodes.empty())
957 DeallocateNode(AllNodes.begin());
960 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
961 SDVTList VTs, SDValue N1,
962 SDValue N2, bool nuw, bool nsw,
964 if (isBinOpWithFlags(Opcode)) {
965 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
966 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
967 FN->Flags.setNoUnsignedWrap(nuw);
968 FN->Flags.setNoSignedWrap(nsw);
969 FN->Flags.setExact(exact);
974 BinarySDNode *N = new (NodeAllocator)
975 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
979 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
981 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
983 switch (N->getOpcode()) {
986 case ISD::ConstantFP:
987 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
988 "debug location. Use another overload.");
994 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
995 DebugLoc DL, void *&InsertPos) {
996 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
998 switch (N->getOpcode()) {
999 default: break; // Process only regular (non-target) constant nodes.
1001 case ISD::ConstantFP:
1002 // Erase debug location from the node if the node is used at several
1003 // different places to do not propagate one location to all uses as it
1004 // leads to incorrect debug info.
1005 if (N->getDebugLoc() != DL)
1006 N->setDebugLoc(DebugLoc());
1013 void SelectionDAG::clear() {
1015 OperandAllocator.Reset();
1018 ExtendedValueTypeNodes.clear();
1019 ExternalSymbols.clear();
1020 TargetExternalSymbols.clear();
1021 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1022 static_cast<CondCodeSDNode*>(nullptr));
1023 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1024 static_cast<SDNode*>(nullptr));
1026 EntryNode.UseList = nullptr;
1027 AllNodes.push_back(&EntryNode);
1028 Root = getEntryNode();
1032 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1033 return VT.bitsGT(Op.getValueType()) ?
1034 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1035 getNode(ISD::TRUNCATE, DL, VT, Op);
1038 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1039 return VT.bitsGT(Op.getValueType()) ?
1040 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1041 getNode(ISD::TRUNCATE, DL, VT, Op);
1044 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1045 return VT.bitsGT(Op.getValueType()) ?
1046 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1047 getNode(ISD::TRUNCATE, DL, VT, Op);
1050 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1052 if (VT.bitsLE(Op.getValueType()))
1053 return getNode(ISD::TRUNCATE, SL, VT, Op);
1055 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1056 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1059 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1060 assert(!VT.isVector() &&
1061 "getZeroExtendInReg should use the vector element type instead of "
1062 "the vector type!");
1063 if (Op.getValueType() == VT) return Op;
1064 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1065 APInt Imm = APInt::getLowBitsSet(BitWidth,
1066 VT.getSizeInBits());
1067 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1068 getConstant(Imm, DL, Op.getValueType()));
1071 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1072 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1073 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1074 "The sizes of the input and result must match in order to perform the "
1075 "extend in-register.");
1076 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1077 "The destination vector type must have fewer lanes than the input.");
1078 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1081 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1082 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1083 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1084 "The sizes of the input and result must match in order to perform the "
1085 "extend in-register.");
1086 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1087 "The destination vector type must have fewer lanes than the input.");
1088 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1091 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1092 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1093 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1094 "The sizes of the input and result must match in order to perform the "
1095 "extend in-register.");
1096 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1097 "The destination vector type must have fewer lanes than the input.");
1098 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1101 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1103 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1104 EVT EltVT = VT.getScalarType();
1106 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1107 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1110 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1111 EVT EltVT = VT.getScalarType();
1113 switch (TLI->getBooleanContents(VT)) {
1114 case TargetLowering::ZeroOrOneBooleanContent:
1115 case TargetLowering::UndefinedBooleanContent:
1116 TrueValue = getConstant(1, DL, VT);
1118 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1119 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1123 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1126 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1128 EVT EltVT = VT.getScalarType();
1129 assert((EltVT.getSizeInBits() >= 64 ||
1130 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1131 "getConstant with a uint64_t value that doesn't fit in the type!");
1132 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1135 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1138 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1141 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1142 bool isT, bool isO) {
1143 assert(VT.isInteger() && "Cannot create FP integer constant!");
1145 EVT EltVT = VT.getScalarType();
1146 const ConstantInt *Elt = &Val;
1148 // In some cases the vector type is legal but the element type is illegal and
1149 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1150 // inserted value (the type does not need to match the vector element type).
1151 // Any extra bits introduced will be truncated away.
1152 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1153 TargetLowering::TypePromoteInteger) {
1154 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1155 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1156 Elt = ConstantInt::get(*getContext(), NewVal);
1158 // In other cases the element type is illegal and needs to be expanded, for
1159 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1160 // the value into n parts and use a vector type with n-times the elements.
1161 // Then bitcast to the type requested.
1162 // Legalizing constants too early makes the DAGCombiner's job harder so we
1163 // only legalize if the DAG tells us we must produce legal types.
1164 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1165 TLI->getTypeAction(*getContext(), EltVT) ==
1166 TargetLowering::TypeExpandInteger) {
1167 APInt NewVal = Elt->getValue();
1168 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1169 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1170 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1171 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1173 // Check the temporary vector is the correct size. If this fails then
1174 // getTypeToTransformTo() probably returned a type whose size (in bits)
1175 // isn't a power-of-2 factor of the requested type size.
1176 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1178 SmallVector<SDValue, 2> EltParts;
1179 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1180 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1181 .trunc(ViaEltSizeInBits), DL,
1182 ViaEltVT, isT, isO));
1185 // EltParts is currently in little endian order. If we actually want
1186 // big-endian order then reverse it now.
1187 if (TLI->isBigEndian())
1188 std::reverse(EltParts.begin(), EltParts.end());
1190 // The elements must be reversed when the element order is different
1191 // to the endianness of the elements (because the BITCAST is itself a
1192 // vector shuffle in this situation). However, we do not need any code to
1193 // perform this reversal because getConstant() is producing a vector
1195 // This situation occurs in MIPS MSA.
1197 SmallVector<SDValue, 8> Ops;
1198 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1199 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1201 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1202 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1207 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1208 "APInt size does not match type size!");
1209 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1210 FoldingSetNodeID ID;
1211 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1215 SDNode *N = nullptr;
1216 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1218 return SDValue(N, 0);
1221 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1223 CSEMap.InsertNode(N, IP);
1227 SDValue Result(N, 0);
1228 if (VT.isVector()) {
1229 SmallVector<SDValue, 8> Ops;
1230 Ops.assign(VT.getVectorNumElements(), Result);
1231 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1236 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1237 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1240 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1242 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1245 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1247 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1249 EVT EltVT = VT.getScalarType();
1251 // Do the map lookup using the actual bit pattern for the floating point
1252 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1253 // we don't have issues with SNANs.
1254 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1255 FoldingSetNodeID ID;
1256 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1259 SDNode *N = nullptr;
1260 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1262 return SDValue(N, 0);
1265 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1267 CSEMap.InsertNode(N, IP);
1271 SDValue Result(N, 0);
1272 if (VT.isVector()) {
1273 SmallVector<SDValue, 8> Ops;
1274 Ops.assign(VT.getVectorNumElements(), Result);
1275 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1280 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1282 EVT EltVT = VT.getScalarType();
1283 if (EltVT==MVT::f32)
1284 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1285 else if (EltVT==MVT::f64)
1286 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1287 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1290 APFloat apf = APFloat(Val);
1291 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1293 return getConstantFP(apf, DL, VT, isTarget);
1295 llvm_unreachable("Unsupported type in getConstantFP");
1298 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1299 EVT VT, int64_t Offset,
1301 unsigned char TargetFlags) {
1302 assert((TargetFlags == 0 || isTargetGA) &&
1303 "Cannot set target flags on target-independent globals");
1305 // Truncate (with sign-extension) the offset value to the pointer size.
1306 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1308 Offset = SignExtend64(Offset, BitWidth);
1311 if (GV->isThreadLocal())
1312 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1314 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1321 ID.AddInteger(GV->getType()->getAddressSpace());
1323 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1327 DL.getDebugLoc(), GV, VT,
1328 Offset, TargetFlags);
1329 CSEMap.InsertNode(N, IP);
1331 return SDValue(N, 0);
1334 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1335 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1336 FoldingSetNodeID ID;
1337 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1340 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1341 return SDValue(E, 0);
1343 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1344 CSEMap.InsertNode(N, IP);
1346 return SDValue(N, 0);
1349 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1350 unsigned char TargetFlags) {
1351 assert((TargetFlags == 0 || isTarget) &&
1352 "Cannot set target flags on target-independent jump tables");
1353 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1354 FoldingSetNodeID ID;
1355 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1357 ID.AddInteger(TargetFlags);
1359 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1360 return SDValue(E, 0);
1362 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1364 CSEMap.InsertNode(N, IP);
1366 return SDValue(N, 0);
1369 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1370 unsigned Alignment, int Offset,
1372 unsigned char TargetFlags) {
1373 assert((TargetFlags == 0 || isTarget) &&
1374 "Cannot set target flags on target-independent globals");
1376 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1377 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1378 FoldingSetNodeID ID;
1379 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1380 ID.AddInteger(Alignment);
1381 ID.AddInteger(Offset);
1383 ID.AddInteger(TargetFlags);
1385 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1386 return SDValue(E, 0);
1388 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1389 Alignment, TargetFlags);
1390 CSEMap.InsertNode(N, IP);
1392 return SDValue(N, 0);
1396 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1397 unsigned Alignment, int Offset,
1399 unsigned char TargetFlags) {
1400 assert((TargetFlags == 0 || isTarget) &&
1401 "Cannot set target flags on target-independent globals");
1403 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1404 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1407 ID.AddInteger(Alignment);
1408 ID.AddInteger(Offset);
1409 C->addSelectionDAGCSEId(ID);
1410 ID.AddInteger(TargetFlags);
1412 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1413 return SDValue(E, 0);
1415 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1416 Alignment, TargetFlags);
1417 CSEMap.InsertNode(N, IP);
1419 return SDValue(N, 0);
1422 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1423 unsigned char TargetFlags) {
1424 FoldingSetNodeID ID;
1425 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1426 ID.AddInteger(Index);
1427 ID.AddInteger(Offset);
1428 ID.AddInteger(TargetFlags);
1430 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1431 return SDValue(E, 0);
1433 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1435 CSEMap.InsertNode(N, IP);
1437 return SDValue(N, 0);
1440 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1441 FoldingSetNodeID ID;
1442 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1445 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1446 return SDValue(E, 0);
1448 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1449 CSEMap.InsertNode(N, IP);
1451 return SDValue(N, 0);
1454 SDValue SelectionDAG::getValueType(EVT VT) {
1455 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1456 ValueTypeNodes.size())
1457 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1459 SDNode *&N = VT.isExtended() ?
1460 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1462 if (N) return SDValue(N, 0);
1463 N = new (NodeAllocator) VTSDNode(VT);
1465 return SDValue(N, 0);
1468 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1469 SDNode *&N = ExternalSymbols[Sym];
1470 if (N) return SDValue(N, 0);
1471 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1473 return SDValue(N, 0);
1476 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1477 unsigned char TargetFlags) {
1479 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1481 if (N) return SDValue(N, 0);
1482 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1484 return SDValue(N, 0);
1487 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1488 if ((unsigned)Cond >= CondCodeNodes.size())
1489 CondCodeNodes.resize(Cond+1);
1491 if (!CondCodeNodes[Cond]) {
1492 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1493 CondCodeNodes[Cond] = N;
1497 return SDValue(CondCodeNodes[Cond], 0);
1500 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1501 // the shuffle mask M that point at N1 to point at N2, and indices that point
1502 // N2 to point at N1.
1503 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1505 ShuffleVectorSDNode::commuteMask(M);
1508 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1509 SDValue N2, const int *Mask) {
1510 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1511 "Invalid VECTOR_SHUFFLE");
1513 // Canonicalize shuffle undef, undef -> undef
1514 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1515 return getUNDEF(VT);
1517 // Validate that all indices in Mask are within the range of the elements
1518 // input to the shuffle.
1519 unsigned NElts = VT.getVectorNumElements();
1520 SmallVector<int, 8> MaskVec;
1521 for (unsigned i = 0; i != NElts; ++i) {
1522 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1523 MaskVec.push_back(Mask[i]);
1526 // Canonicalize shuffle v, v -> v, undef
1529 for (unsigned i = 0; i != NElts; ++i)
1530 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1533 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1534 if (N1.getOpcode() == ISD::UNDEF)
1535 commuteShuffle(N1, N2, MaskVec);
1537 // If shuffling a splat, try to blend the splat instead. We do this here so
1538 // that even when this arises during lowering we don't have to re-handle it.
1539 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1540 BitVector UndefElements;
1541 SDValue Splat = BV->getSplatValue(&UndefElements);
1545 for (int i = 0; i < (int)NElts; ++i) {
1546 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1549 // If this input comes from undef, mark it as such.
1550 if (UndefElements[MaskVec[i] - Offset]) {
1555 // If we can blend a non-undef lane, use that instead.
1556 if (!UndefElements[i])
1557 MaskVec[i] = i + Offset;
1560 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1561 BlendSplat(N1BV, 0);
1562 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1563 BlendSplat(N2BV, NElts);
1565 // Canonicalize all index into lhs, -> shuffle lhs, undef
1566 // Canonicalize all index into rhs, -> shuffle rhs, undef
1567 bool AllLHS = true, AllRHS = true;
1568 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1569 for (unsigned i = 0; i != NElts; ++i) {
1570 if (MaskVec[i] >= (int)NElts) {
1575 } else if (MaskVec[i] >= 0) {
1579 if (AllLHS && AllRHS)
1580 return getUNDEF(VT);
1581 if (AllLHS && !N2Undef)
1585 commuteShuffle(N1, N2, MaskVec);
1587 // Reset our undef status after accounting for the mask.
1588 N2Undef = N2.getOpcode() == ISD::UNDEF;
1589 // Re-check whether both sides ended up undef.
1590 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1591 return getUNDEF(VT);
1593 // If Identity shuffle return that node.
1594 bool Identity = true, AllSame = true;
1595 for (unsigned i = 0; i != NElts; ++i) {
1596 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1597 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1599 if (Identity && NElts)
1602 // Shuffling a constant splat doesn't change the result.
1606 // Look through any bitcasts. We check that these don't change the number
1607 // (and size) of elements and just changes their types.
1608 while (V.getOpcode() == ISD::BITCAST)
1609 V = V->getOperand(0);
1611 // A splat should always show up as a build vector node.
1612 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1613 BitVector UndefElements;
1614 SDValue Splat = BV->getSplatValue(&UndefElements);
1615 // If this is a splat of an undef, shuffling it is also undef.
1616 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1617 return getUNDEF(VT);
1620 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1622 // We only have a splat which can skip shuffles if there is a splatted
1623 // value and no undef lanes rearranged by the shuffle.
1624 if (Splat && UndefElements.none()) {
1625 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1626 // number of elements match or the value splatted is a zero constant.
1629 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1630 if (C->isNullValue())
1634 // If the shuffle itself creates a splat, build the vector directly.
1635 if (AllSame && SameNumElts) {
1636 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1637 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1639 EVT BuildVT = BV->getValueType(0);
1640 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1642 // We may have jumped through bitcasts, so the type of the
1643 // BUILD_VECTOR may not match the type of the shuffle.
1645 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1651 FoldingSetNodeID ID;
1652 SDValue Ops[2] = { N1, N2 };
1653 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1654 for (unsigned i = 0; i != NElts; ++i)
1655 ID.AddInteger(MaskVec[i]);
1658 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1659 return SDValue(E, 0);
1661 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1662 // SDNode doesn't have access to it. This memory will be "leaked" when
1663 // the node is deallocated, but recovered when the NodeAllocator is released.
1664 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1665 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1667 ShuffleVectorSDNode *N =
1668 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1669 dl.getDebugLoc(), N1, N2,
1671 CSEMap.InsertNode(N, IP);
1673 return SDValue(N, 0);
1676 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1677 MVT VT = SV.getSimpleValueType(0);
1678 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1679 ShuffleVectorSDNode::commuteMask(MaskVec);
1681 SDValue Op0 = SV.getOperand(0);
1682 SDValue Op1 = SV.getOperand(1);
1683 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1686 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1687 SDValue Val, SDValue DTy,
1688 SDValue STy, SDValue Rnd, SDValue Sat,
1689 ISD::CvtCode Code) {
1690 // If the src and dest types are the same and the conversion is between
1691 // integer types of the same sign or two floats, no conversion is necessary.
1693 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1696 FoldingSetNodeID ID;
1697 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1698 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1700 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1701 return SDValue(E, 0);
1703 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1706 CSEMap.InsertNode(N, IP);
1708 return SDValue(N, 0);
1711 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1712 FoldingSetNodeID ID;
1713 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1714 ID.AddInteger(RegNo);
1716 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1717 return SDValue(E, 0);
1719 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1720 CSEMap.InsertNode(N, IP);
1722 return SDValue(N, 0);
1725 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1728 ID.AddPointer(RegMask);
1730 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1731 return SDValue(E, 0);
1733 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1734 CSEMap.InsertNode(N, IP);
1736 return SDValue(N, 0);
1739 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1740 FoldingSetNodeID ID;
1741 SDValue Ops[] = { Root };
1742 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1743 ID.AddPointer(Label);
1745 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1746 return SDValue(E, 0);
1748 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1749 dl.getDebugLoc(), Root, Label);
1750 CSEMap.InsertNode(N, IP);
1752 return SDValue(N, 0);
1756 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1759 unsigned char TargetFlags) {
1760 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1762 FoldingSetNodeID ID;
1763 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1765 ID.AddInteger(Offset);
1766 ID.AddInteger(TargetFlags);
1768 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1769 return SDValue(E, 0);
1771 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1773 CSEMap.InsertNode(N, IP);
1775 return SDValue(N, 0);
1778 SDValue SelectionDAG::getSrcValue(const Value *V) {
1779 assert((!V || V->getType()->isPointerTy()) &&
1780 "SrcValue is not a pointer?");
1782 FoldingSetNodeID ID;
1783 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1787 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1788 return SDValue(E, 0);
1790 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1791 CSEMap.InsertNode(N, IP);
1793 return SDValue(N, 0);
1796 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1797 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1798 FoldingSetNodeID ID;
1799 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1803 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1804 return SDValue(E, 0);
1806 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1807 CSEMap.InsertNode(N, IP);
1809 return SDValue(N, 0);
1812 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1813 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1814 unsigned SrcAS, unsigned DestAS) {
1815 SDValue Ops[] = {Ptr};
1816 FoldingSetNodeID ID;
1817 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1818 ID.AddInteger(SrcAS);
1819 ID.AddInteger(DestAS);
1822 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1823 return SDValue(E, 0);
1825 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1827 VT, Ptr, SrcAS, DestAS);
1828 CSEMap.InsertNode(N, IP);
1830 return SDValue(N, 0);
1833 /// getShiftAmountOperand - Return the specified value casted to
1834 /// the target's desired shift amount type.
1835 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1836 EVT OpTy = Op.getValueType();
1837 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1838 if (OpTy == ShTy || OpTy.isVector()) return Op;
1840 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1841 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1844 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1845 /// specified value type.
1846 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1847 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1848 unsigned ByteSize = VT.getStoreSize();
1849 Type *Ty = VT.getTypeForEVT(*getContext());
1850 unsigned StackAlign =
1851 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1853 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1854 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1857 /// CreateStackTemporary - Create a stack temporary suitable for holding
1858 /// either of the specified value types.
1859 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1860 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1861 VT2.getStoreSizeInBits())/8;
1862 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1863 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1864 const DataLayout *TD = TLI->getDataLayout();
1865 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1866 TD->getPrefTypeAlignment(Ty2));
1868 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1869 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1870 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1873 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1874 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1875 // These setcc operations always fold.
1879 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1881 case ISD::SETTRUE2: {
1882 TargetLowering::BooleanContent Cnt =
1883 TLI->getBooleanContents(N1->getValueType(0));
1885 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1899 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1903 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1904 const APInt &C2 = N2C->getAPIntValue();
1905 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1906 const APInt &C1 = N1C->getAPIntValue();
1909 default: llvm_unreachable("Unknown integer setcc!");
1910 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1911 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1912 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1913 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1914 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1915 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1916 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1917 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1918 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1919 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1923 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1924 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1925 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1928 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1929 return getUNDEF(VT);
1931 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1932 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1933 return getUNDEF(VT);
1935 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1936 R==APFloat::cmpLessThan, dl, VT);
1937 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1938 return getUNDEF(VT);
1940 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1941 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1942 return getUNDEF(VT);
1944 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1945 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1946 return getUNDEF(VT);
1948 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1949 R==APFloat::cmpEqual, dl, VT);
1950 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1951 return getUNDEF(VT);
1953 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1954 R==APFloat::cmpEqual, dl, VT);
1955 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1956 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1957 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1958 R==APFloat::cmpEqual, dl, VT);
1959 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1960 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1961 R==APFloat::cmpLessThan, dl, VT);
1962 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1963 R==APFloat::cmpUnordered, dl, VT);
1964 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1965 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1968 // Ensure that the constant occurs on the RHS.
1969 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1970 MVT CompVT = N1.getValueType().getSimpleVT();
1971 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1974 return getSetCC(dl, VT, N2, N1, SwappedCond);
1978 // Could not fold it.
1982 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1983 /// use this predicate to simplify operations downstream.
1984 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1985 // This predicate is not safe for vector operations.
1986 if (Op.getValueType().isVector())
1989 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1990 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1993 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1994 /// this predicate to simplify operations downstream. Mask is known to be zero
1995 /// for bits that V cannot have.
1996 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1997 unsigned Depth) const {
1998 APInt KnownZero, KnownOne;
1999 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2000 return (KnownZero & Mask) == Mask;
2003 /// Determine which bits of Op are known to be either zero or one and return
2004 /// them in the KnownZero/KnownOne bitsets.
2005 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2006 APInt &KnownOne, unsigned Depth) const {
2007 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2009 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2011 return; // Limit search depth.
2013 APInt KnownZero2, KnownOne2;
2015 switch (Op.getOpcode()) {
2017 // We know all of the bits for a constant!
2018 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2019 KnownZero = ~KnownOne;
2022 // If either the LHS or the RHS are Zero, the result is zero.
2023 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2024 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2026 // Output known-1 bits are only known if set in both the LHS & RHS.
2027 KnownOne &= KnownOne2;
2028 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2029 KnownZero |= KnownZero2;
2032 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2033 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2035 // Output known-0 bits are only known if clear in both the LHS & RHS.
2036 KnownZero &= KnownZero2;
2037 // Output known-1 are known to be set if set in either the LHS | RHS.
2038 KnownOne |= KnownOne2;
2041 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2042 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2044 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2045 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2046 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2047 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2048 KnownZero = KnownZeroOut;
2052 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2053 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2055 // If low bits are zero in either operand, output low known-0 bits.
2056 // Also compute a conserative estimate for high known-0 bits.
2057 // More trickiness is possible, but this is sufficient for the
2058 // interesting case of alignment computation.
2059 KnownOne.clearAllBits();
2060 unsigned TrailZ = KnownZero.countTrailingOnes() +
2061 KnownZero2.countTrailingOnes();
2062 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2063 KnownZero2.countLeadingOnes(),
2064 BitWidth) - BitWidth;
2066 TrailZ = std::min(TrailZ, BitWidth);
2067 LeadZ = std::min(LeadZ, BitWidth);
2068 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2069 APInt::getHighBitsSet(BitWidth, LeadZ);
2073 // For the purposes of computing leading zeros we can conservatively
2074 // treat a udiv as a logical right shift by the power of 2 known to
2075 // be less than the denominator.
2076 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2077 unsigned LeadZ = KnownZero2.countLeadingOnes();
2079 KnownOne2.clearAllBits();
2080 KnownZero2.clearAllBits();
2081 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2082 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2083 if (RHSUnknownLeadingOnes != BitWidth)
2084 LeadZ = std::min(BitWidth,
2085 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2087 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2091 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2092 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2094 // Only known if known in both the LHS and RHS.
2095 KnownOne &= KnownOne2;
2096 KnownZero &= KnownZero2;
2098 case ISD::SELECT_CC:
2099 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2100 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2102 // Only known if known in both the LHS and RHS.
2103 KnownOne &= KnownOne2;
2104 KnownZero &= KnownZero2;
2112 if (Op.getResNo() != 1)
2114 // The boolean result conforms to getBooleanContents.
2115 // If we know the result of a setcc has the top bits zero, use this info.
2116 // We know that we have an integer-based boolean since these operations
2117 // are only available for integer.
2118 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2119 TargetLowering::ZeroOrOneBooleanContent &&
2121 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2124 // If we know the result of a setcc has the top bits zero, use this info.
2125 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2126 TargetLowering::ZeroOrOneBooleanContent &&
2128 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2131 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2132 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2133 unsigned ShAmt = SA->getZExtValue();
2135 // If the shift count is an invalid immediate, don't do anything.
2136 if (ShAmt >= BitWidth)
2139 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2140 KnownZero <<= ShAmt;
2142 // low bits known zero.
2143 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2147 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2148 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2149 unsigned ShAmt = SA->getZExtValue();
2151 // If the shift count is an invalid immediate, don't do anything.
2152 if (ShAmt >= BitWidth)
2155 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2156 KnownZero = KnownZero.lshr(ShAmt);
2157 KnownOne = KnownOne.lshr(ShAmt);
2159 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2160 KnownZero |= HighBits; // High bits known zero.
2164 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2165 unsigned ShAmt = SA->getZExtValue();
2167 // If the shift count is an invalid immediate, don't do anything.
2168 if (ShAmt >= BitWidth)
2171 // If any of the demanded bits are produced by the sign extension, we also
2172 // demand the input sign bit.
2173 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2175 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2176 KnownZero = KnownZero.lshr(ShAmt);
2177 KnownOne = KnownOne.lshr(ShAmt);
2179 // Handle the sign bits.
2180 APInt SignBit = APInt::getSignBit(BitWidth);
2181 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2183 if (KnownZero.intersects(SignBit)) {
2184 KnownZero |= HighBits; // New bits are known zero.
2185 } else if (KnownOne.intersects(SignBit)) {
2186 KnownOne |= HighBits; // New bits are known one.
2190 case ISD::SIGN_EXTEND_INREG: {
2191 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2192 unsigned EBits = EVT.getScalarType().getSizeInBits();
2194 // Sign extension. Compute the demanded bits in the result that are not
2195 // present in the input.
2196 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2198 APInt InSignBit = APInt::getSignBit(EBits);
2199 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2201 // If the sign extended bits are demanded, we know that the sign
2203 InSignBit = InSignBit.zext(BitWidth);
2204 if (NewBits.getBoolValue())
2205 InputDemandedBits |= InSignBit;
2207 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2208 KnownOne &= InputDemandedBits;
2209 KnownZero &= InputDemandedBits;
2211 // If the sign bit of the input is known set or clear, then we know the
2212 // top bits of the result.
2213 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2214 KnownZero |= NewBits;
2215 KnownOne &= ~NewBits;
2216 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2217 KnownOne |= NewBits;
2218 KnownZero &= ~NewBits;
2219 } else { // Input sign bit unknown
2220 KnownZero &= ~NewBits;
2221 KnownOne &= ~NewBits;
2226 case ISD::CTTZ_ZERO_UNDEF:
2228 case ISD::CTLZ_ZERO_UNDEF:
2230 unsigned LowBits = Log2_32(BitWidth)+1;
2231 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2232 KnownOne.clearAllBits();
2236 LoadSDNode *LD = cast<LoadSDNode>(Op);
2237 // If this is a ZEXTLoad and we are looking at the loaded value.
2238 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2239 EVT VT = LD->getMemoryVT();
2240 unsigned MemBits = VT.getScalarType().getSizeInBits();
2241 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2242 } else if (const MDNode *Ranges = LD->getRanges()) {
2243 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2247 case ISD::ZERO_EXTEND: {
2248 EVT InVT = Op.getOperand(0).getValueType();
2249 unsigned InBits = InVT.getScalarType().getSizeInBits();
2250 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2251 KnownZero = KnownZero.trunc(InBits);
2252 KnownOne = KnownOne.trunc(InBits);
2253 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2254 KnownZero = KnownZero.zext(BitWidth);
2255 KnownOne = KnownOne.zext(BitWidth);
2256 KnownZero |= NewBits;
2259 case ISD::SIGN_EXTEND: {
2260 EVT InVT = Op.getOperand(0).getValueType();
2261 unsigned InBits = InVT.getScalarType().getSizeInBits();
2262 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2264 KnownZero = KnownZero.trunc(InBits);
2265 KnownOne = KnownOne.trunc(InBits);
2266 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2268 // Note if the sign bit is known to be zero or one.
2269 bool SignBitKnownZero = KnownZero.isNegative();
2270 bool SignBitKnownOne = KnownOne.isNegative();
2272 KnownZero = KnownZero.zext(BitWidth);
2273 KnownOne = KnownOne.zext(BitWidth);
2275 // If the sign bit is known zero or one, the top bits match.
2276 if (SignBitKnownZero)
2277 KnownZero |= NewBits;
2278 else if (SignBitKnownOne)
2279 KnownOne |= NewBits;
2282 case ISD::ANY_EXTEND: {
2283 EVT InVT = Op.getOperand(0).getValueType();
2284 unsigned InBits = InVT.getScalarType().getSizeInBits();
2285 KnownZero = KnownZero.trunc(InBits);
2286 KnownOne = KnownOne.trunc(InBits);
2287 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2288 KnownZero = KnownZero.zext(BitWidth);
2289 KnownOne = KnownOne.zext(BitWidth);
2292 case ISD::TRUNCATE: {
2293 EVT InVT = Op.getOperand(0).getValueType();
2294 unsigned InBits = InVT.getScalarType().getSizeInBits();
2295 KnownZero = KnownZero.zext(InBits);
2296 KnownOne = KnownOne.zext(InBits);
2297 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2298 KnownZero = KnownZero.trunc(BitWidth);
2299 KnownOne = KnownOne.trunc(BitWidth);
2302 case ISD::AssertZext: {
2303 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2304 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2305 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2306 KnownZero |= (~InMask);
2307 KnownOne &= (~KnownZero);
2311 // All bits are zero except the low bit.
2312 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2316 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2317 // We know that the top bits of C-X are clear if X contains less bits
2318 // than C (i.e. no wrap-around can happen). For example, 20-X is
2319 // positive if we can prove that X is >= 0 and < 16.
2320 if (CLHS->getAPIntValue().isNonNegative()) {
2321 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2322 // NLZ can't be BitWidth with no sign bit
2323 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2324 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2326 // If all of the MaskV bits are known to be zero, then we know the
2327 // output top bits are zero, because we now know that the output is
2329 if ((KnownZero2 & MaskV) == MaskV) {
2330 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2331 // Top bits known zero.
2332 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2340 // Output known-0 bits are known if clear or set in both the low clear bits
2341 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2342 // low 3 bits clear.
2343 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2344 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2346 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2347 KnownZeroOut = std::min(KnownZeroOut,
2348 KnownZero2.countTrailingOnes());
2350 if (Op.getOpcode() == ISD::ADD) {
2351 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2355 // With ADDE, a carry bit may be added in, so we can only use this
2356 // information if we know (at least) that the low two bits are clear. We
2357 // then return to the caller that the low bit is unknown but that other bits
2359 if (KnownZeroOut >= 2) // ADDE
2360 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2364 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2365 const APInt &RA = Rem->getAPIntValue().abs();
2366 if (RA.isPowerOf2()) {
2367 APInt LowBits = RA - 1;
2368 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2370 // The low bits of the first operand are unchanged by the srem.
2371 KnownZero = KnownZero2 & LowBits;
2372 KnownOne = KnownOne2 & LowBits;
2374 // If the first operand is non-negative or has all low bits zero, then
2375 // the upper bits are all zero.
2376 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2377 KnownZero |= ~LowBits;
2379 // If the first operand is negative and not all low bits are zero, then
2380 // the upper bits are all one.
2381 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2382 KnownOne |= ~LowBits;
2383 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2388 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2389 const APInt &RA = Rem->getAPIntValue();
2390 if (RA.isPowerOf2()) {
2391 APInt LowBits = (RA - 1);
2392 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2394 // The upper bits are all zero, the lower ones are unchanged.
2395 KnownZero = KnownZero2 | ~LowBits;
2396 KnownOne = KnownOne2 & LowBits;
2401 // Since the result is less than or equal to either operand, any leading
2402 // zero bits in either operand must also exist in the result.
2403 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2404 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2406 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2407 KnownZero2.countLeadingOnes());
2408 KnownOne.clearAllBits();
2409 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2412 case ISD::EXTRACT_ELEMENT: {
2413 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2414 const unsigned Index =
2415 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2416 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2418 // Remove low part of known bits mask
2419 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2420 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2422 // Remove high part of known bit mask
2423 KnownZero = KnownZero.trunc(BitWidth);
2424 KnownOne = KnownOne.trunc(BitWidth);
2427 case ISD::FrameIndex:
2428 case ISD::TargetFrameIndex:
2429 if (unsigned Align = InferPtrAlignment(Op)) {
2430 // The low bits are known zero if the pointer is aligned.
2431 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2437 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2440 case ISD::INTRINSIC_WO_CHAIN:
2441 case ISD::INTRINSIC_W_CHAIN:
2442 case ISD::INTRINSIC_VOID:
2443 // Allow the target to implement this method for its nodes.
2444 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2448 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2451 /// ComputeNumSignBits - Return the number of times the sign bit of the
2452 /// register is replicated into the other bits. We know that at least 1 bit
2453 /// is always equal to the sign bit (itself), but other cases can give us
2454 /// information. For example, immediately after an "SRA X, 2", we know that
2455 /// the top 3 bits are all equal to each other, so we return 3.
2456 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2457 EVT VT = Op.getValueType();
2458 assert(VT.isInteger() && "Invalid VT!");
2459 unsigned VTBits = VT.getScalarType().getSizeInBits();
2461 unsigned FirstAnswer = 1;
2464 return 1; // Limit search depth.
2466 switch (Op.getOpcode()) {
2468 case ISD::AssertSext:
2469 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2470 return VTBits-Tmp+1;
2471 case ISD::AssertZext:
2472 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2475 case ISD::Constant: {
2476 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2477 return Val.getNumSignBits();
2480 case ISD::SIGN_EXTEND:
2482 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2483 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2485 case ISD::SIGN_EXTEND_INREG:
2486 // Max of the input and what this extends.
2488 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2491 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2492 return std::max(Tmp, Tmp2);
2495 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2496 // SRA X, C -> adds C sign bits.
2497 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2498 Tmp += C->getZExtValue();
2499 if (Tmp > VTBits) Tmp = VTBits;
2503 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2504 // shl destroys sign bits.
2505 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2506 if (C->getZExtValue() >= VTBits || // Bad shift.
2507 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2508 return Tmp - C->getZExtValue();
2513 case ISD::XOR: // NOT is handled here.
2514 // Logical binary ops preserve the number of sign bits at the worst.
2515 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2517 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2518 FirstAnswer = std::min(Tmp, Tmp2);
2519 // We computed what we know about the sign bits as our first
2520 // answer. Now proceed to the generic code that uses
2521 // computeKnownBits, and pick whichever answer is better.
2526 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2527 if (Tmp == 1) return 1; // Early out.
2528 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2529 return std::min(Tmp, Tmp2);
2537 if (Op.getResNo() != 1)
2539 // The boolean result conforms to getBooleanContents. Fall through.
2540 // If setcc returns 0/-1, all bits are sign bits.
2541 // We know that we have an integer-based boolean since these operations
2542 // are only available for integer.
2543 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2544 TargetLowering::ZeroOrNegativeOneBooleanContent)
2548 // If setcc returns 0/-1, all bits are sign bits.
2549 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2550 TargetLowering::ZeroOrNegativeOneBooleanContent)
2555 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2556 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2558 // Handle rotate right by N like a rotate left by 32-N.
2559 if (Op.getOpcode() == ISD::ROTR)
2560 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2562 // If we aren't rotating out all of the known-in sign bits, return the
2563 // number that are left. This handles rotl(sext(x), 1) for example.
2564 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2565 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2569 // Add can have at most one carry bit. Thus we know that the output
2570 // is, at worst, one more bit than the inputs.
2571 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2572 if (Tmp == 1) return 1; // Early out.
2574 // Special case decrementing a value (ADD X, -1):
2575 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2576 if (CRHS->isAllOnesValue()) {
2577 APInt KnownZero, KnownOne;
2578 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2580 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2582 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2585 // If we are subtracting one from a positive number, there is no carry
2586 // out of the result.
2587 if (KnownZero.isNegative())
2591 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2592 if (Tmp2 == 1) return 1;
2593 return std::min(Tmp, Tmp2)-1;
2596 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2597 if (Tmp2 == 1) return 1;
2600 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2601 if (CLHS->isNullValue()) {
2602 APInt KnownZero, KnownOne;
2603 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2604 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2606 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2609 // If the input is known to be positive (the sign bit is known clear),
2610 // the output of the NEG has the same number of sign bits as the input.
2611 if (KnownZero.isNegative())
2614 // Otherwise, we treat this like a SUB.
2617 // Sub can have at most one carry bit. Thus we know that the output
2618 // is, at worst, one more bit than the inputs.
2619 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2620 if (Tmp == 1) return 1; // Early out.
2621 return std::min(Tmp, Tmp2)-1;
2623 // FIXME: it's tricky to do anything useful for this, but it is an important
2624 // case for targets like X86.
2626 case ISD::EXTRACT_ELEMENT: {
2627 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2628 const int BitWidth = Op.getValueType().getSizeInBits();
2630 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2632 // Get reverse index (starting from 1), Op1 value indexes elements from
2633 // little end. Sign starts at big end.
2634 const int rIndex = Items - 1 -
2635 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2637 // If the sign portion ends in our element the substraction gives correct
2638 // result. Otherwise it gives either negative or > bitwidth result
2639 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2643 // If we are looking at the loaded value of the SDNode.
2644 if (Op.getResNo() == 0) {
2645 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2646 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2647 unsigned ExtType = LD->getExtensionType();
2650 case ISD::SEXTLOAD: // '17' bits known
2651 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2652 return VTBits-Tmp+1;
2653 case ISD::ZEXTLOAD: // '16' bits known
2654 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2660 // Allow the target to implement this method for its nodes.
2661 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2662 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2663 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2664 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2665 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2666 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2669 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2670 // use this information.
2671 APInt KnownZero, KnownOne;
2672 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2675 if (KnownZero.isNegative()) { // sign bit is 0
2677 } else if (KnownOne.isNegative()) { // sign bit is 1;
2684 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2685 // the number of identical bits in the top of the input value.
2687 Mask <<= Mask.getBitWidth()-VTBits;
2688 // Return # leading zeros. We use 'min' here in case Val was zero before
2689 // shifting. We don't want to return '64' as for an i32 "0".
2690 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2693 /// isBaseWithConstantOffset - Return true if the specified operand is an
2694 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2695 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2696 /// semantics as an ADD. This handles the equivalence:
2697 /// X|Cst == X+Cst iff X&Cst = 0.
2698 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2699 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2700 !isa<ConstantSDNode>(Op.getOperand(1)))
2703 if (Op.getOpcode() == ISD::OR &&
2704 !MaskedValueIsZero(Op.getOperand(0),
2705 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2712 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2713 // If we're told that NaNs won't happen, assume they won't.
2714 if (getTarget().Options.NoNaNsFPMath)
2717 // If the value is a constant, we can obviously see if it is a NaN or not.
2718 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2719 return !C->getValueAPF().isNaN();
2721 // TODO: Recognize more cases here.
2726 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2727 // If the value is a constant, we can obviously see if it is a zero or not.
2728 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2729 return !C->isZero();
2731 // TODO: Recognize more cases here.
2732 switch (Op.getOpcode()) {
2735 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2736 return !C->isNullValue();
2743 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2744 // Check the obvious case.
2745 if (A == B) return true;
2747 // For for negative and positive zero.
2748 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2749 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2750 if (CA->isZero() && CB->isZero()) return true;
2752 // Otherwise they may not be equal.
2756 /// getNode - Gets or creates the specified node.
2758 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2759 FoldingSetNodeID ID;
2760 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2762 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2763 return SDValue(E, 0);
2765 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2766 DL.getDebugLoc(), getVTList(VT));
2767 CSEMap.InsertNode(N, IP);
2770 return SDValue(N, 0);
2773 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2774 EVT VT, SDValue Operand) {
2775 // Constant fold unary operations with an integer constant operand. Even
2776 // opaque constant will be folded, because the folding of unary operations
2777 // doesn't create new constants with different values. Nevertheless, the
2778 // opaque flag is preserved during folding to prevent future folding with
2780 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2781 const APInt &Val = C->getAPIntValue();
2784 case ISD::SIGN_EXTEND:
2785 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2786 C->isTargetOpcode(), C->isOpaque());
2787 case ISD::ANY_EXTEND:
2788 case ISD::ZERO_EXTEND:
2790 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2791 C->isTargetOpcode(), C->isOpaque());
2792 case ISD::UINT_TO_FP:
2793 case ISD::SINT_TO_FP: {
2794 APFloat apf(EVTToAPFloatSemantics(VT),
2795 APInt::getNullValue(VT.getSizeInBits()));
2796 (void)apf.convertFromAPInt(Val,
2797 Opcode==ISD::SINT_TO_FP,
2798 APFloat::rmNearestTiesToEven);
2799 return getConstantFP(apf, DL, VT);
2802 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2803 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2804 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2805 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2806 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2807 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2810 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2813 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2816 case ISD::CTLZ_ZERO_UNDEF:
2817 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2820 case ISD::CTTZ_ZERO_UNDEF:
2821 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2826 // Constant fold unary operations with a floating point constant operand.
2827 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2828 APFloat V = C->getValueAPF(); // make copy
2832 return getConstantFP(V, DL, VT);
2835 return getConstantFP(V, DL, VT);
2837 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2838 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2839 return getConstantFP(V, DL, VT);
2843 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2844 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2845 return getConstantFP(V, DL, VT);
2849 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2850 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2851 return getConstantFP(V, DL, VT);
2854 case ISD::FP_EXTEND: {
2856 // This can return overflow, underflow, or inexact; we don't care.
2857 // FIXME need to be more flexible about rounding mode.
2858 (void)V.convert(EVTToAPFloatSemantics(VT),
2859 APFloat::rmNearestTiesToEven, &ignored);
2860 return getConstantFP(V, DL, VT);
2862 case ISD::FP_TO_SINT:
2863 case ISD::FP_TO_UINT: {
2866 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2867 // FIXME need to be more flexible about rounding mode.
2868 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2869 Opcode==ISD::FP_TO_SINT,
2870 APFloat::rmTowardZero, &ignored);
2871 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2873 APInt api(VT.getSizeInBits(), x);
2874 return getConstant(api, DL, VT);
2877 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2878 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2879 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2880 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2881 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2882 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2887 // Constant fold unary operations with a vector integer or float operand.
2888 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2889 if (BV->isConstant()) {
2892 // FIXME: Entirely reasonable to perform folding of other unary
2893 // operations here as the need arises.
2900 case ISD::FP_EXTEND:
2901 case ISD::FP_TO_SINT:
2902 case ISD::FP_TO_UINT:
2904 case ISD::UINT_TO_FP:
2905 case ISD::SINT_TO_FP: {
2906 EVT SVT = VT.getScalarType();
2907 EVT InVT = BV->getValueType(0);
2908 EVT InSVT = InVT.getScalarType();
2910 // Find legal integer scalar type for constant promotion and
2911 // ensure that its scalar size is at least as large as source.
2913 if (SVT.isInteger()) {
2914 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2915 if (LegalSVT.bitsLT(SVT)) break;
2918 // Let the above scalar folding handle the folding of each element.
2919 SmallVector<SDValue, 8> Ops;
2920 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2921 SDValue OpN = BV->getOperand(i);
2922 EVT OpVT = OpN.getValueType();
2924 // Build vector (integer) scalar operands may need implicit
2925 // truncation - do this before constant folding.
2926 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2927 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2929 OpN = getNode(Opcode, DL, SVT, OpN);
2931 // Legalize the (integer) scalar constant if necessary.
2932 if (LegalSVT != SVT)
2933 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2935 if (OpN.getOpcode() != ISD::UNDEF &&
2936 OpN.getOpcode() != ISD::Constant &&
2937 OpN.getOpcode() != ISD::ConstantFP)
2941 if (Ops.size() == VT.getVectorNumElements())
2942 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2949 unsigned OpOpcode = Operand.getNode()->getOpcode();
2951 case ISD::TokenFactor:
2952 case ISD::MERGE_VALUES:
2953 case ISD::CONCAT_VECTORS:
2954 return Operand; // Factor, merge or concat of one node? No need.
2955 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2956 case ISD::FP_EXTEND:
2957 assert(VT.isFloatingPoint() &&
2958 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2959 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2960 assert((!VT.isVector() ||
2961 VT.getVectorNumElements() ==
2962 Operand.getValueType().getVectorNumElements()) &&
2963 "Vector element count mismatch!");
2964 if (Operand.getOpcode() == ISD::UNDEF)
2965 return getUNDEF(VT);
2967 case ISD::SIGN_EXTEND:
2968 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2969 "Invalid SIGN_EXTEND!");
2970 if (Operand.getValueType() == VT) return Operand; // noop extension
2971 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2972 "Invalid sext node, dst < src!");
2973 assert((!VT.isVector() ||
2974 VT.getVectorNumElements() ==
2975 Operand.getValueType().getVectorNumElements()) &&
2976 "Vector element count mismatch!");
2977 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2978 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2979 else if (OpOpcode == ISD::UNDEF)
2980 // sext(undef) = 0, because the top bits will all be the same.
2981 return getConstant(0, DL, VT);
2983 case ISD::ZERO_EXTEND:
2984 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2985 "Invalid ZERO_EXTEND!");
2986 if (Operand.getValueType() == VT) return Operand; // noop extension
2987 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2988 "Invalid zext node, dst < src!");
2989 assert((!VT.isVector() ||
2990 VT.getVectorNumElements() ==
2991 Operand.getValueType().getVectorNumElements()) &&
2992 "Vector element count mismatch!");
2993 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2994 return getNode(ISD::ZERO_EXTEND, DL, VT,
2995 Operand.getNode()->getOperand(0));
2996 else if (OpOpcode == ISD::UNDEF)
2997 // zext(undef) = 0, because the top bits will be zero.
2998 return getConstant(0, DL, VT);
3000 case ISD::ANY_EXTEND:
3001 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3002 "Invalid ANY_EXTEND!");
3003 if (Operand.getValueType() == VT) return Operand; // noop extension
3004 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3005 "Invalid anyext node, dst < src!");
3006 assert((!VT.isVector() ||
3007 VT.getVectorNumElements() ==
3008 Operand.getValueType().getVectorNumElements()) &&
3009 "Vector element count mismatch!");
3011 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3012 OpOpcode == ISD::ANY_EXTEND)
3013 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3014 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3015 else if (OpOpcode == ISD::UNDEF)
3016 return getUNDEF(VT);
3018 // (ext (trunx x)) -> x
3019 if (OpOpcode == ISD::TRUNCATE) {
3020 SDValue OpOp = Operand.getNode()->getOperand(0);
3021 if (OpOp.getValueType() == VT)
3026 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3027 "Invalid TRUNCATE!");
3028 if (Operand.getValueType() == VT) return Operand; // noop truncate
3029 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3030 "Invalid truncate node, src < dst!");
3031 assert((!VT.isVector() ||
3032 VT.getVectorNumElements() ==
3033 Operand.getValueType().getVectorNumElements()) &&
3034 "Vector element count mismatch!");
3035 if (OpOpcode == ISD::TRUNCATE)
3036 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3037 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3038 OpOpcode == ISD::ANY_EXTEND) {
3039 // If the source is smaller than the dest, we still need an extend.
3040 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3041 .bitsLT(VT.getScalarType()))
3042 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3043 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3044 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3045 return Operand.getNode()->getOperand(0);
3047 if (OpOpcode == ISD::UNDEF)
3048 return getUNDEF(VT);
3051 // Basic sanity checking.
3052 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3053 && "Cannot BITCAST between types of different sizes!");
3054 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3055 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3056 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3057 if (OpOpcode == ISD::UNDEF)
3058 return getUNDEF(VT);
3060 case ISD::SCALAR_TO_VECTOR:
3061 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3062 (VT.getVectorElementType() == Operand.getValueType() ||
3063 (VT.getVectorElementType().isInteger() &&
3064 Operand.getValueType().isInteger() &&
3065 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3066 "Illegal SCALAR_TO_VECTOR node!");
3067 if (OpOpcode == ISD::UNDEF)
3068 return getUNDEF(VT);
3069 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3070 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3071 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3072 Operand.getConstantOperandVal(1) == 0 &&
3073 Operand.getOperand(0).getValueType() == VT)
3074 return Operand.getOperand(0);
3077 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3078 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3079 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3080 Operand.getNode()->getOperand(0));
3081 if (OpOpcode == ISD::FNEG) // --X -> X
3082 return Operand.getNode()->getOperand(0);
3085 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3086 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3091 SDVTList VTs = getVTList(VT);
3092 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3093 FoldingSetNodeID ID;
3094 SDValue Ops[1] = { Operand };
3095 AddNodeIDNode(ID, Opcode, VTs, Ops);
3097 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3098 return SDValue(E, 0);
3100 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3101 DL.getDebugLoc(), VTs, Operand);
3102 CSEMap.InsertNode(N, IP);
3104 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3105 DL.getDebugLoc(), VTs, Operand);
3109 return SDValue(N, 0);
3112 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3113 SDNode *Cst1, SDNode *Cst2) {
3114 // If the opcode is a target-specific ISD node, there's nothing we can
3115 // do here and the operand rules may not line up with the below, so
3117 if (Opcode >= ISD::BUILTIN_OP_END)
3120 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3121 SmallVector<SDValue, 4> Outputs;
3122 EVT SVT = VT.getScalarType();
3124 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3125 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3126 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3129 if (Scalar1 && Scalar2)
3130 // Scalar instruction.
3131 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3133 // For vectors extract each constant element into Inputs so we can constant
3134 // fold them individually.
3135 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3136 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3140 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3142 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3143 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3144 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3145 if (!V1 || !V2) // Not a constant, bail.
3148 if (V1->isOpaque() || V2->isOpaque())
3151 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3152 // FIXME: This is valid and could be handled by truncating the APInts.
3153 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3156 Inputs.push_back(std::make_pair(V1, V2));
3160 // We have a number of constant values, constant fold them element by element.
3161 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3162 const APInt &C1 = Inputs[I].first->getAPIntValue();
3163 const APInt &C2 = Inputs[I].second->getAPIntValue();
3167 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3170 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3173 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3176 if (!C2.getBoolValue())
3178 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3181 if (!C2.getBoolValue())
3183 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3186 if (!C2.getBoolValue())
3188 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3191 if (!C2.getBoolValue())
3193 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3196 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3199 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3202 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3205 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3208 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3211 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3214 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3217 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3224 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3225 "Expected a scalar or vector!"));
3227 // Handle the scalar case first.
3229 return Outputs.back();
3231 // We may have a vector type but a scalar result. Create a splat.
3232 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3234 // Build a big vector out of the scalar elements we generated.
3235 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3238 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3239 SDValue N2, bool nuw, bool nsw, bool exact) {
3240 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3241 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3244 case ISD::TokenFactor:
3245 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3246 N2.getValueType() == MVT::Other && "Invalid token factor!");
3247 // Fold trivial token factors.
3248 if (N1.getOpcode() == ISD::EntryToken) return N2;
3249 if (N2.getOpcode() == ISD::EntryToken) return N1;
3250 if (N1 == N2) return N1;
3252 case ISD::CONCAT_VECTORS:
3253 // Concat of UNDEFs is UNDEF.
3254 if (N1.getOpcode() == ISD::UNDEF &&
3255 N2.getOpcode() == ISD::UNDEF)
3256 return getUNDEF(VT);
3258 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3259 // one big BUILD_VECTOR.
3260 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3261 N2.getOpcode() == ISD::BUILD_VECTOR) {
3262 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3263 N1.getNode()->op_end());
3264 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3266 // BUILD_VECTOR requires all inputs to be of the same type, find the
3267 // maximum type and extend them all.
3268 EVT SVT = VT.getScalarType();
3269 for (SDValue Op : Elts)
3270 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3271 if (SVT.bitsGT(VT.getScalarType()))
3272 for (SDValue &Op : Elts)
3273 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3274 ? getZExtOrTrunc(Op, DL, SVT)
3275 : getSExtOrTrunc(Op, DL, SVT);
3277 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3281 assert(VT.isInteger() && "This operator does not apply to FP types!");
3282 assert(N1.getValueType() == N2.getValueType() &&
3283 N1.getValueType() == VT && "Binary operator types must match!");
3284 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3285 // worth handling here.
3286 if (N2C && N2C->isNullValue())
3288 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3295 assert(VT.isInteger() && "This operator does not apply to FP types!");
3296 assert(N1.getValueType() == N2.getValueType() &&
3297 N1.getValueType() == VT && "Binary operator types must match!");
3298 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3299 // it's worth handling here.
3300 if (N2C && N2C->isNullValue())
3310 assert(VT.isInteger() && "This operator does not apply to FP types!");
3311 assert(N1.getValueType() == N2.getValueType() &&
3312 N1.getValueType() == VT && "Binary operator types must match!");
3319 if (getTarget().Options.UnsafeFPMath) {
3320 if (Opcode == ISD::FADD) {
3322 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3323 if (CFP->getValueAPF().isZero())
3326 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3327 if (CFP->getValueAPF().isZero())
3329 } else if (Opcode == ISD::FSUB) {
3331 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3332 if (CFP->getValueAPF().isZero())
3334 } else if (Opcode == ISD::FMUL) {
3335 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3338 // If the first operand isn't the constant, try the second
3340 CFP = dyn_cast<ConstantFPSDNode>(N2);
3347 return SDValue(CFP,0);
3349 if (CFP->isExactlyValue(1.0))
3354 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3355 assert(N1.getValueType() == N2.getValueType() &&
3356 N1.getValueType() == VT && "Binary operator types must match!");
3358 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3359 assert(N1.getValueType() == VT &&
3360 N1.getValueType().isFloatingPoint() &&
3361 N2.getValueType().isFloatingPoint() &&
3362 "Invalid FCOPYSIGN!");
3369 assert(VT == N1.getValueType() &&
3370 "Shift operators return type must be the same as their first arg");
3371 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3372 "Shifts only work on integers");
3373 assert((!VT.isVector() || VT == N2.getValueType()) &&
3374 "Vector shift amounts must be in the same as their first arg");
3375 // Verify that the shift amount VT is bit enough to hold valid shift
3376 // amounts. This catches things like trying to shift an i1024 value by an
3377 // i8, which is easy to fall into in generic code that uses
3378 // TLI.getShiftAmount().
3379 assert(N2.getValueType().getSizeInBits() >=
3380 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3381 "Invalid use of small shift amount with oversized value!");
3383 // Always fold shifts of i1 values so the code generator doesn't need to
3384 // handle them. Since we know the size of the shift has to be less than the
3385 // size of the value, the shift/rotate count is guaranteed to be zero.
3388 if (N2C && N2C->isNullValue())
3391 case ISD::FP_ROUND_INREG: {
3392 EVT EVT = cast<VTSDNode>(N2)->getVT();
3393 assert(VT == N1.getValueType() && "Not an inreg round!");
3394 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3395 "Cannot FP_ROUND_INREG integer types");
3396 assert(EVT.isVector() == VT.isVector() &&
3397 "FP_ROUND_INREG type should be vector iff the operand "
3399 assert((!EVT.isVector() ||
3400 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3401 "Vector element counts must match in FP_ROUND_INREG");
3402 assert(EVT.bitsLE(VT) && "Not rounding down!");
3404 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3408 assert(VT.isFloatingPoint() &&
3409 N1.getValueType().isFloatingPoint() &&
3410 VT.bitsLE(N1.getValueType()) &&
3411 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3412 if (N1.getValueType() == VT) return N1; // noop conversion.
3414 case ISD::AssertSext:
3415 case ISD::AssertZext: {
3416 EVT EVT = cast<VTSDNode>(N2)->getVT();
3417 assert(VT == N1.getValueType() && "Not an inreg extend!");
3418 assert(VT.isInteger() && EVT.isInteger() &&
3419 "Cannot *_EXTEND_INREG FP types");
3420 assert(!EVT.isVector() &&
3421 "AssertSExt/AssertZExt type should be the vector element type "
3422 "rather than the vector type!");
3423 assert(EVT.bitsLE(VT) && "Not extending!");
3424 if (VT == EVT) return N1; // noop assertion.
3427 case ISD::SIGN_EXTEND_INREG: {
3428 EVT EVT = cast<VTSDNode>(N2)->getVT();
3429 assert(VT == N1.getValueType() && "Not an inreg extend!");
3430 assert(VT.isInteger() && EVT.isInteger() &&
3431 "Cannot *_EXTEND_INREG FP types");
3432 assert(EVT.isVector() == VT.isVector() &&
3433 "SIGN_EXTEND_INREG type should be vector iff the operand "
3435 assert((!EVT.isVector() ||
3436 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3437 "Vector element counts must match in SIGN_EXTEND_INREG");
3438 assert(EVT.bitsLE(VT) && "Not extending!");
3439 if (EVT == VT) return N1; // Not actually extending
3442 APInt Val = N1C->getAPIntValue();
3443 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3444 Val <<= Val.getBitWidth()-FromBits;
3445 Val = Val.ashr(Val.getBitWidth()-FromBits);
3446 return getConstant(Val, DL, VT);
3450 case ISD::EXTRACT_VECTOR_ELT:
3451 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3452 if (N1.getOpcode() == ISD::UNDEF)
3453 return getUNDEF(VT);
3455 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3456 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3457 return getUNDEF(VT);
3459 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3460 // expanding copies of large vectors from registers.
3462 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3463 N1.getNumOperands() > 0) {
3465 N1.getOperand(0).getValueType().getVectorNumElements();
3466 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3467 N1.getOperand(N2C->getZExtValue() / Factor),
3468 getConstant(N2C->getZExtValue() % Factor, DL,
3469 N2.getValueType()));
3472 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3473 // expanding large vector constants.
3474 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3475 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3477 if (VT != Elt.getValueType())
3478 // If the vector element type is not legal, the BUILD_VECTOR operands
3479 // are promoted and implicitly truncated, and the result implicitly
3480 // extended. Make that explicit here.
3481 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3486 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3487 // operations are lowered to scalars.
3488 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3489 // If the indices are the same, return the inserted element else
3490 // if the indices are known different, extract the element from
3491 // the original vector.
3492 SDValue N1Op2 = N1.getOperand(2);
3493 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3495 if (N1Op2C && N2C) {
3496 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3497 if (VT == N1.getOperand(1).getValueType())
3498 return N1.getOperand(1);
3500 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3503 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3507 case ISD::EXTRACT_ELEMENT:
3508 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3509 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3510 (N1.getValueType().isInteger() == VT.isInteger()) &&
3511 N1.getValueType() != VT &&
3512 "Wrong types for EXTRACT_ELEMENT!");
3514 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3515 // 64-bit integers into 32-bit parts. Instead of building the extract of
3516 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3517 if (N1.getOpcode() == ISD::BUILD_PAIR)
3518 return N1.getOperand(N2C->getZExtValue());
3520 // EXTRACT_ELEMENT of a constant int is also very common.
3521 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3522 unsigned ElementSize = VT.getSizeInBits();
3523 unsigned Shift = ElementSize * N2C->getZExtValue();
3524 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3525 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3528 case ISD::EXTRACT_SUBVECTOR: {
3530 if (VT.isSimple() && N1.getValueType().isSimple()) {
3531 assert(VT.isVector() && N1.getValueType().isVector() &&
3532 "Extract subvector VTs must be a vectors!");
3533 assert(VT.getVectorElementType() ==
3534 N1.getValueType().getVectorElementType() &&
3535 "Extract subvector VTs must have the same element type!");
3536 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3537 "Extract subvector must be from larger vector to smaller vector!");
3539 if (isa<ConstantSDNode>(Index.getNode())) {
3540 assert((VT.getVectorNumElements() +
3541 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3542 <= N1.getValueType().getVectorNumElements())
3543 && "Extract subvector overflow!");
3546 // Trivial extraction.
3547 if (VT.getSimpleVT() == N1.getSimpleValueType())
3554 // Perform trivial constant folding.
3556 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3559 // Canonicalize constant to RHS if commutative.
3560 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3561 std::swap(N1C, N2C);
3565 // Constant fold FP operations.
3566 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3567 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3568 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3570 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3571 // Canonicalize constant to RHS if commutative.
3572 std::swap(N1CFP, N2CFP);
3575 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3576 APFloat::opStatus s;
3579 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3580 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3581 return getConstantFP(V1, DL, VT);
3584 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3585 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3586 return getConstantFP(V1, DL, VT);
3589 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3590 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3591 return getConstantFP(V1, DL, VT);
3594 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3595 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3596 s!=APFloat::opDivByZero)) {
3597 return getConstantFP(V1, DL, VT);
3601 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3602 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3603 s!=APFloat::opDivByZero)) {
3604 return getConstantFP(V1, DL, VT);
3607 case ISD::FCOPYSIGN:
3609 return getConstantFP(V1, DL, VT);
3614 if (Opcode == ISD::FP_ROUND) {
3615 APFloat V = N1CFP->getValueAPF(); // make copy
3617 // This can return overflow, underflow, or inexact; we don't care.
3618 // FIXME need to be more flexible about rounding mode.
3619 (void)V.convert(EVTToAPFloatSemantics(VT),
3620 APFloat::rmNearestTiesToEven, &ignored);
3621 return getConstantFP(V, DL, VT);
3625 // Canonicalize an UNDEF to the RHS, even over a constant.
3626 if (N1.getOpcode() == ISD::UNDEF) {
3627 if (isCommutativeBinOp(Opcode)) {
3631 case ISD::FP_ROUND_INREG:
3632 case ISD::SIGN_EXTEND_INREG:
3638 return N1; // fold op(undef, arg2) -> undef
3646 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3647 // For vectors, we can't easily build an all zero vector, just return
3654 // Fold a bunch of operators when the RHS is undef.
3655 if (N2.getOpcode() == ISD::UNDEF) {
3658 if (N1.getOpcode() == ISD::UNDEF)
3659 // Handle undef ^ undef -> 0 special case. This is a common
3661 return getConstant(0, DL, VT);
3671 return N2; // fold op(arg1, undef) -> undef
3677 if (getTarget().Options.UnsafeFPMath)
3685 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3686 // For vectors, we can't easily build an all zero vector, just return
3691 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3692 // For vectors, we can't easily build an all one vector, just return
3700 // Memoize this node if possible.
3702 SDVTList VTs = getVTList(VT);
3703 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3704 if (VT != MVT::Glue) {
3705 SDValue Ops[] = {N1, N2};
3706 FoldingSetNodeID ID;
3707 AddNodeIDNode(ID, Opcode, VTs, Ops);
3709 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3711 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3712 return SDValue(E, 0);
3714 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3716 CSEMap.InsertNode(N, IP);
3718 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3722 return SDValue(N, 0);
3725 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3726 SDValue N1, SDValue N2, SDValue N3) {
3727 // Perform various simplifications.
3728 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3731 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3732 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3733 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3734 if (N1CFP && N2CFP && N3CFP) {
3735 APFloat V1 = N1CFP->getValueAPF();
3736 const APFloat &V2 = N2CFP->getValueAPF();
3737 const APFloat &V3 = N3CFP->getValueAPF();
3738 APFloat::opStatus s =
3739 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3740 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3741 return getConstantFP(V1, DL, VT);
3745 case ISD::CONCAT_VECTORS:
3746 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3747 // one big BUILD_VECTOR.
3748 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3749 N2.getOpcode() == ISD::BUILD_VECTOR &&
3750 N3.getOpcode() == ISD::BUILD_VECTOR) {
3751 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3752 N1.getNode()->op_end());
3753 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3754 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3755 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3759 // Use FoldSetCC to simplify SETCC's.
3760 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3761 if (Simp.getNode()) return Simp;
3766 if (N1C->getZExtValue())
3767 return N2; // select true, X, Y -> X
3768 return N3; // select false, X, Y -> Y
3771 if (N2 == N3) return N2; // select C, X, X -> X
3773 case ISD::VECTOR_SHUFFLE:
3774 llvm_unreachable("should use getVectorShuffle constructor!");
3775 case ISD::INSERT_SUBVECTOR: {
3777 if (VT.isSimple() && N1.getValueType().isSimple()
3778 && N2.getValueType().isSimple()) {
3779 assert(VT.isVector() && N1.getValueType().isVector() &&
3780 N2.getValueType().isVector() &&
3781 "Insert subvector VTs must be a vectors");
3782 assert(VT == N1.getValueType() &&
3783 "Dest and insert subvector source types must match!");
3784 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3785 "Insert subvector must be from smaller vector to larger vector!");
3786 if (isa<ConstantSDNode>(Index.getNode())) {
3787 assert((N2.getValueType().getVectorNumElements() +
3788 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3789 <= VT.getVectorNumElements())
3790 && "Insert subvector overflow!");
3793 // Trivial insertion.
3794 if (VT.getSimpleVT() == N2.getSimpleValueType())
3800 // Fold bit_convert nodes from a type to themselves.
3801 if (N1.getValueType() == VT)
3806 // Memoize node if it doesn't produce a flag.
3808 SDVTList VTs = getVTList(VT);
3809 if (VT != MVT::Glue) {
3810 SDValue Ops[] = { N1, N2, N3 };
3811 FoldingSetNodeID ID;
3812 AddNodeIDNode(ID, Opcode, VTs, Ops);
3814 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3815 return SDValue(E, 0);
3817 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3818 DL.getDebugLoc(), VTs, N1, N2, N3);
3819 CSEMap.InsertNode(N, IP);
3821 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3822 DL.getDebugLoc(), VTs, N1, N2, N3);
3826 return SDValue(N, 0);
3829 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3830 SDValue N1, SDValue N2, SDValue N3,
3832 SDValue Ops[] = { N1, N2, N3, N4 };
3833 return getNode(Opcode, DL, VT, Ops);
3836 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3837 SDValue N1, SDValue N2, SDValue N3,
3838 SDValue N4, SDValue N5) {
3839 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3840 return getNode(Opcode, DL, VT, Ops);
3843 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3844 /// the incoming stack arguments to be loaded from the stack.
3845 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3846 SmallVector<SDValue, 8> ArgChains;
3848 // Include the original chain at the beginning of the list. When this is
3849 // used by target LowerCall hooks, this helps legalize find the
3850 // CALLSEQ_BEGIN node.
3851 ArgChains.push_back(Chain);
3853 // Add a chain value for each stack argument.
3854 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3855 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3856 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3857 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3858 if (FI->getIndex() < 0)
3859 ArgChains.push_back(SDValue(L, 1));
3861 // Build a tokenfactor for all the chains.
3862 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3865 /// getMemsetValue - Vectorized representation of the memset value
3867 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3869 assert(Value.getOpcode() != ISD::UNDEF);
3871 unsigned NumBits = VT.getScalarType().getSizeInBits();
3872 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3873 assert(C->getAPIntValue().getBitWidth() == 8);
3874 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3876 return DAG.getConstant(Val, dl, VT);
3877 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3881 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3882 EVT IntVT = VT.getScalarType();
3883 if (!IntVT.isInteger())
3884 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3886 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3888 // Use a multiplication with 0x010101... to extend the input to the
3890 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3891 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3892 DAG.getConstant(Magic, dl, IntVT));
3895 if (VT != Value.getValueType() && !VT.isInteger())
3896 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3897 if (VT != Value.getValueType()) {
3898 assert(VT.getVectorElementType() == Value.getValueType() &&
3899 "value type should be one vector element here");
3900 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3901 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3907 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3908 /// used when a memcpy is turned into a memset when the source is a constant
3910 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3911 const TargetLowering &TLI, StringRef Str) {
3912 // Handle vector with all elements zero.
3915 return DAG.getConstant(0, dl, VT);
3916 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3917 return DAG.getConstantFP(0.0, dl, VT);
3918 else if (VT.isVector()) {
3919 unsigned NumElts = VT.getVectorNumElements();
3920 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3921 return DAG.getNode(ISD::BITCAST, dl, VT,
3922 DAG.getConstant(0, dl,
3923 EVT::getVectorVT(*DAG.getContext(),
3926 llvm_unreachable("Expected type!");
3929 assert(!VT.isVector() && "Can't handle vector type here!");
3930 unsigned NumVTBits = VT.getSizeInBits();
3931 unsigned NumVTBytes = NumVTBits / 8;
3932 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3934 APInt Val(NumVTBits, 0);
3935 if (TLI.isLittleEndian()) {
3936 for (unsigned i = 0; i != NumBytes; ++i)
3937 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3939 for (unsigned i = 0; i != NumBytes; ++i)
3940 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3943 // If the "cost" of materializing the integer immediate is less than the cost
3944 // of a load, then it is cost effective to turn the load into the immediate.
3945 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3946 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3947 return DAG.getConstant(Val, dl, VT);
3948 return SDValue(nullptr, 0);
3951 /// getMemBasePlusOffset - Returns base and offset node for the
3953 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3954 SelectionDAG &DAG) {
3955 EVT VT = Base.getValueType();
3956 return DAG.getNode(ISD::ADD, dl,
3957 VT, Base, DAG.getConstant(Offset, dl, VT));
3960 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3962 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3963 unsigned SrcDelta = 0;
3964 GlobalAddressSDNode *G = nullptr;
3965 if (Src.getOpcode() == ISD::GlobalAddress)
3966 G = cast<GlobalAddressSDNode>(Src);
3967 else if (Src.getOpcode() == ISD::ADD &&
3968 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3969 Src.getOperand(1).getOpcode() == ISD::Constant) {
3970 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3971 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3976 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3979 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3980 /// to replace the memset / memcpy. Return true if the number of memory ops
3981 /// is below the threshold. It returns the types of the sequence of
3982 /// memory ops to perform memset / memcpy by reference.
3983 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3984 unsigned Limit, uint64_t Size,
3985 unsigned DstAlign, unsigned SrcAlign,
3991 const TargetLowering &TLI) {
3992 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3993 "Expecting memcpy / memset source to meet alignment requirement!");
3994 // If 'SrcAlign' is zero, that means the memory operation does not need to
3995 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3996 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3997 // is the specified alignment of the memory operation. If it is zero, that
3998 // means it's possible to change the alignment of the destination.
3999 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4000 // not need to be loaded.
4001 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4002 IsMemset, ZeroMemset, MemcpyStrSrc,
4003 DAG.getMachineFunction());
4005 if (VT == MVT::Other) {
4007 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4008 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4009 VT = TLI.getPointerTy();
4011 switch (DstAlign & 7) {
4012 case 0: VT = MVT::i64; break;
4013 case 4: VT = MVT::i32; break;
4014 case 2: VT = MVT::i16; break;
4015 default: VT = MVT::i8; break;
4020 while (!TLI.isTypeLegal(LVT))
4021 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4022 assert(LVT.isInteger());
4028 unsigned NumMemOps = 0;
4030 unsigned VTSize = VT.getSizeInBits() / 8;
4031 while (VTSize > Size) {
4032 // For now, only use non-vector load / store's for the left-over pieces.
4037 if (VT.isVector() || VT.isFloatingPoint()) {
4038 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4039 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4040 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4042 else if (NewVT == MVT::i64 &&
4043 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4044 TLI.isSafeMemOpType(MVT::f64)) {
4045 // i64 is usually not legal on 32-bit targets, but f64 may be.
4053 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4054 if (NewVT == MVT::i8)
4056 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4058 NewVTSize = NewVT.getSizeInBits() / 8;
4060 // If the new VT cannot cover all of the remaining bits, then consider
4061 // issuing a (or a pair of) unaligned and overlapping load / store.
4062 // FIXME: Only does this for 64-bit or more since we don't have proper
4063 // cost model for unaligned load / store.
4066 if (NumMemOps && AllowOverlap &&
4067 VTSize >= 8 && NewVTSize < Size &&
4068 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4076 if (++NumMemOps > Limit)
4079 MemOps.push_back(VT);
4086 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4087 SDValue Chain, SDValue Dst,
4088 SDValue Src, uint64_t Size,
4089 unsigned Align, bool isVol,
4091 MachinePointerInfo DstPtrInfo,
4092 MachinePointerInfo SrcPtrInfo) {
4093 // Turn a memcpy of undef to nop.
4094 if (Src.getOpcode() == ISD::UNDEF)
4097 // Expand memcpy to a series of load and store ops if the size operand falls
4098 // below a certain threshold.
4099 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4100 // rather than maybe a humongous number of loads and stores.
4101 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4102 std::vector<EVT> MemOps;
4103 bool DstAlignCanChange = false;
4104 MachineFunction &MF = DAG.getMachineFunction();
4105 MachineFrameInfo *MFI = MF.getFrameInfo();
4106 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4107 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4108 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4109 DstAlignCanChange = true;
4110 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4111 if (Align > SrcAlign)
4114 bool CopyFromStr = isMemSrcFromString(Src, Str);
4115 bool isZeroStr = CopyFromStr && Str.empty();
4116 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4118 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4119 (DstAlignCanChange ? 0 : Align),
4120 (isZeroStr ? 0 : SrcAlign),
4121 false, false, CopyFromStr, true, DAG, TLI))
4124 if (DstAlignCanChange) {
4125 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4126 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4128 // Don't promote to an alignment that would require dynamic stack
4130 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4131 if (!TRI->needsStackRealignment(MF))
4132 while (NewAlign > Align &&
4133 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4136 if (NewAlign > Align) {
4137 // Give the stack frame object a larger alignment if needed.
4138 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4139 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4144 SmallVector<SDValue, 8> OutChains;
4145 unsigned NumMemOps = MemOps.size();
4146 uint64_t SrcOff = 0, DstOff = 0;
4147 for (unsigned i = 0; i != NumMemOps; ++i) {
4149 unsigned VTSize = VT.getSizeInBits() / 8;
4150 SDValue Value, Store;
4152 if (VTSize > Size) {
4153 // Issuing an unaligned load / store pair that overlaps with the previous
4154 // pair. Adjust the offset accordingly.
4155 assert(i == NumMemOps-1 && i != 0);
4156 SrcOff -= VTSize - Size;
4157 DstOff -= VTSize - Size;
4161 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4162 // It's unlikely a store of a vector immediate can be done in a single
4163 // instruction. It would require a load from a constantpool first.
4164 // We only handle zero vectors here.
4165 // FIXME: Handle other cases where store of vector immediate is done in
4166 // a single instruction.
4167 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4168 if (Value.getNode())
4169 Store = DAG.getStore(Chain, dl, Value,
4170 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4171 DstPtrInfo.getWithOffset(DstOff), isVol,
4175 if (!Store.getNode()) {
4176 // The type might not be legal for the target. This should only happen
4177 // if the type is smaller than a legal type, as on PPC, so the right
4178 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4179 // to Load/Store if NVT==VT.
4180 // FIXME does the case above also need this?
4181 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4182 assert(NVT.bitsGE(VT));
4183 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4184 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4185 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4186 false, MinAlign(SrcAlign, SrcOff));
4187 Store = DAG.getTruncStore(Chain, dl, Value,
4188 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4189 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4192 OutChains.push_back(Store);
4198 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4201 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4202 SDValue Chain, SDValue Dst,
4203 SDValue Src, uint64_t Size,
4204 unsigned Align, bool isVol,
4206 MachinePointerInfo DstPtrInfo,
4207 MachinePointerInfo SrcPtrInfo) {
4208 // Turn a memmove of undef to nop.
4209 if (Src.getOpcode() == ISD::UNDEF)
4212 // Expand memmove to a series of load and store ops if the size operand falls
4213 // below a certain threshold.
4214 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4215 std::vector<EVT> MemOps;
4216 bool DstAlignCanChange = false;
4217 MachineFunction &MF = DAG.getMachineFunction();
4218 MachineFrameInfo *MFI = MF.getFrameInfo();
4219 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4220 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4221 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4222 DstAlignCanChange = true;
4223 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4224 if (Align > SrcAlign)
4226 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4228 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4229 (DstAlignCanChange ? 0 : Align), SrcAlign,
4230 false, false, false, false, DAG, TLI))
4233 if (DstAlignCanChange) {
4234 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4235 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4236 if (NewAlign > Align) {
4237 // Give the stack frame object a larger alignment if needed.
4238 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4239 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4244 uint64_t SrcOff = 0, DstOff = 0;
4245 SmallVector<SDValue, 8> LoadValues;
4246 SmallVector<SDValue, 8> LoadChains;
4247 SmallVector<SDValue, 8> OutChains;
4248 unsigned NumMemOps = MemOps.size();
4249 for (unsigned i = 0; i < NumMemOps; i++) {
4251 unsigned VTSize = VT.getSizeInBits() / 8;
4254 Value = DAG.getLoad(VT, dl, Chain,
4255 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4256 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4257 false, false, SrcAlign);
4258 LoadValues.push_back(Value);
4259 LoadChains.push_back(Value.getValue(1));
4262 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4264 for (unsigned i = 0; i < NumMemOps; i++) {
4266 unsigned VTSize = VT.getSizeInBits() / 8;
4269 Store = DAG.getStore(Chain, dl, LoadValues[i],
4270 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4271 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4272 OutChains.push_back(Store);
4276 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4279 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4282 /// \param DAG Selection DAG where lowered code is placed.
4283 /// \param dl Link to corresponding IR location.
4284 /// \param Chain Control flow dependency.
4285 /// \param Dst Pointer to destination memory location.
4286 /// \param Src Value of byte to write into the memory.
4287 /// \param Size Number of bytes to write.
4288 /// \param Align Alignment of the destination in bytes.
4289 /// \param isVol True if destination is volatile.
4290 /// \param DstPtrInfo IR information on the memory pointer.
4291 /// \returns New head in the control flow, if lowering was successful, empty
4292 /// SDValue otherwise.
4294 /// The function tries to replace 'llvm.memset' intrinsic with several store
4295 /// operations and value calculation code. This is usually profitable for small
4297 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4298 SDValue Chain, SDValue Dst,
4299 SDValue Src, uint64_t Size,
4300 unsigned Align, bool isVol,
4301 MachinePointerInfo DstPtrInfo) {
4302 // Turn a memset of undef to nop.
4303 if (Src.getOpcode() == ISD::UNDEF)
4306 // Expand memset to a series of load/store ops if the size operand
4307 // falls below a certain threshold.
4308 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4309 std::vector<EVT> MemOps;
4310 bool DstAlignCanChange = false;
4311 MachineFunction &MF = DAG.getMachineFunction();
4312 MachineFrameInfo *MFI = MF.getFrameInfo();
4313 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4314 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4315 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4316 DstAlignCanChange = true;
4318 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4319 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4320 Size, (DstAlignCanChange ? 0 : Align), 0,
4321 true, IsZeroVal, false, true, DAG, TLI))
4324 if (DstAlignCanChange) {
4325 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4326 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4327 if (NewAlign > Align) {
4328 // Give the stack frame object a larger alignment if needed.
4329 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4330 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4335 SmallVector<SDValue, 8> OutChains;
4336 uint64_t DstOff = 0;
4337 unsigned NumMemOps = MemOps.size();
4339 // Find the largest store and generate the bit pattern for it.
4340 EVT LargestVT = MemOps[0];
4341 for (unsigned i = 1; i < NumMemOps; i++)
4342 if (MemOps[i].bitsGT(LargestVT))
4343 LargestVT = MemOps[i];
4344 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4346 for (unsigned i = 0; i < NumMemOps; i++) {
4348 unsigned VTSize = VT.getSizeInBits() / 8;
4349 if (VTSize > Size) {
4350 // Issuing an unaligned load / store pair that overlaps with the previous
4351 // pair. Adjust the offset accordingly.
4352 assert(i == NumMemOps-1 && i != 0);
4353 DstOff -= VTSize - Size;
4356 // If this store is smaller than the largest store see whether we can get
4357 // the smaller value for free with a truncate.
4358 SDValue Value = MemSetValue;
4359 if (VT.bitsLT(LargestVT)) {
4360 if (!LargestVT.isVector() && !VT.isVector() &&
4361 TLI.isTruncateFree(LargestVT, VT))
4362 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4364 Value = getMemsetValue(Src, VT, DAG, dl);
4366 assert(Value.getValueType() == VT && "Value with wrong type.");
4367 SDValue Store = DAG.getStore(Chain, dl, Value,
4368 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4369 DstPtrInfo.getWithOffset(DstOff),
4370 isVol, false, Align);
4371 OutChains.push_back(Store);
4372 DstOff += VT.getSizeInBits() / 8;
4376 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4379 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4380 SDValue Src, SDValue Size,
4381 unsigned Align, bool isVol, bool AlwaysInline,
4382 bool isTailCall, MachinePointerInfo DstPtrInfo,
4383 MachinePointerInfo SrcPtrInfo) {
4384 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4386 // Check to see if we should lower the memcpy to loads and stores first.
4387 // For cases within the target-specified limits, this is the best choice.
4388 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4390 // Memcpy with size zero? Just return the original chain.
4391 if (ConstantSize->isNullValue())
4394 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4395 ConstantSize->getZExtValue(),Align,
4396 isVol, false, DstPtrInfo, SrcPtrInfo);
4397 if (Result.getNode())
4401 // Then check to see if we should lower the memcpy with target-specific
4402 // code. If the target chooses to do this, this is the next best.
4404 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4405 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4406 DstPtrInfo, SrcPtrInfo);
4407 if (Result.getNode())
4411 // If we really need inline code and the target declined to provide it,
4412 // use a (potentially long) sequence of loads and stores.
4414 assert(ConstantSize && "AlwaysInline requires a constant size!");
4415 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4416 ConstantSize->getZExtValue(), Align, isVol,
4417 true, DstPtrInfo, SrcPtrInfo);
4420 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4421 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4422 // respect volatile, so they may do things like read or write memory
4423 // beyond the given memory regions. But fixing this isn't easy, and most
4424 // people don't care.
4426 // Emit a library call.
4427 TargetLowering::ArgListTy Args;
4428 TargetLowering::ArgListEntry Entry;
4429 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4430 Entry.Node = Dst; Args.push_back(Entry);
4431 Entry.Node = Src; Args.push_back(Entry);
4432 Entry.Node = Size; Args.push_back(Entry);
4433 // FIXME: pass in SDLoc
4434 TargetLowering::CallLoweringInfo CLI(*this);
4435 CLI.setDebugLoc(dl).setChain(Chain)
4436 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4437 Type::getVoidTy(*getContext()),
4438 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4439 TLI->getPointerTy()), std::move(Args), 0)
4441 .setTailCall(isTailCall);
4443 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4444 return CallResult.second;
4447 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4448 SDValue Src, SDValue Size,
4449 unsigned Align, bool isVol, bool isTailCall,
4450 MachinePointerInfo DstPtrInfo,
4451 MachinePointerInfo SrcPtrInfo) {
4452 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4454 // Check to see if we should lower the memmove to loads and stores first.
4455 // For cases within the target-specified limits, this is the best choice.
4456 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4458 // Memmove with size zero? Just return the original chain.
4459 if (ConstantSize->isNullValue())
4463 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4464 ConstantSize->getZExtValue(), Align, isVol,
4465 false, DstPtrInfo, SrcPtrInfo);
4466 if (Result.getNode())
4470 // Then check to see if we should lower the memmove with target-specific
4471 // code. If the target chooses to do this, this is the next best.
4473 SDValue Result = TSI->EmitTargetCodeForMemmove(
4474 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4475 if (Result.getNode())
4479 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4480 // not be safe. See memcpy above for more details.
4482 // Emit a library call.
4483 TargetLowering::ArgListTy Args;
4484 TargetLowering::ArgListEntry Entry;
4485 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4486 Entry.Node = Dst; Args.push_back(Entry);
4487 Entry.Node = Src; Args.push_back(Entry);
4488 Entry.Node = Size; Args.push_back(Entry);
4489 // FIXME: pass in SDLoc
4490 TargetLowering::CallLoweringInfo CLI(*this);
4491 CLI.setDebugLoc(dl).setChain(Chain)
4492 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4493 Type::getVoidTy(*getContext()),
4494 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4495 TLI->getPointerTy()), std::move(Args), 0)
4497 .setTailCall(isTailCall);
4499 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4500 return CallResult.second;
4503 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4504 SDValue Src, SDValue Size,
4505 unsigned Align, bool isVol, bool isTailCall,
4506 MachinePointerInfo DstPtrInfo) {
4507 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4509 // Check to see if we should lower the memset to stores first.
4510 // For cases within the target-specified limits, this is the best choice.
4511 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4513 // Memset with size zero? Just return the original chain.
4514 if (ConstantSize->isNullValue())
4518 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4519 Align, isVol, DstPtrInfo);
4521 if (Result.getNode())
4525 // Then check to see if we should lower the memset with target-specific
4526 // code. If the target chooses to do this, this is the next best.
4528 SDValue Result = TSI->EmitTargetCodeForMemset(
4529 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4530 if (Result.getNode())
4534 // Emit a library call.
4535 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4536 TargetLowering::ArgListTy Args;
4537 TargetLowering::ArgListEntry Entry;
4538 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4539 Args.push_back(Entry);
4541 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4542 Args.push_back(Entry);
4544 Entry.Ty = IntPtrTy;
4545 Args.push_back(Entry);
4547 // FIXME: pass in SDLoc
4548 TargetLowering::CallLoweringInfo CLI(*this);
4549 CLI.setDebugLoc(dl).setChain(Chain)
4550 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4551 Type::getVoidTy(*getContext()),
4552 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4553 TLI->getPointerTy()), std::move(Args), 0)
4555 .setTailCall(isTailCall);
4557 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4558 return CallResult.second;
4561 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4562 SDVTList VTList, ArrayRef<SDValue> Ops,
4563 MachineMemOperand *MMO,
4564 AtomicOrdering SuccessOrdering,
4565 AtomicOrdering FailureOrdering,
4566 SynchronizationScope SynchScope) {
4567 FoldingSetNodeID ID;
4568 ID.AddInteger(MemVT.getRawBits());
4569 AddNodeIDNode(ID, Opcode, VTList, Ops);
4570 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4572 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4573 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4574 return SDValue(E, 0);
4577 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4578 // SDNode doesn't have access to it. This memory will be "leaked" when
4579 // the node is deallocated, but recovered when the allocator is released.
4580 // If the number of operands is less than 5 we use AtomicSDNode's internal
4582 unsigned NumOps = Ops.size();
4583 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4586 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4587 dl.getDebugLoc(), VTList, MemVT,
4588 Ops.data(), DynOps, NumOps, MMO,
4589 SuccessOrdering, FailureOrdering,
4591 CSEMap.InsertNode(N, IP);
4593 return SDValue(N, 0);
4596 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4597 SDVTList VTList, ArrayRef<SDValue> Ops,
4598 MachineMemOperand *MMO,
4599 AtomicOrdering Ordering,
4600 SynchronizationScope SynchScope) {
4601 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4602 Ordering, SynchScope);
4605 SDValue SelectionDAG::getAtomicCmpSwap(
4606 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4607 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4608 unsigned Alignment, AtomicOrdering SuccessOrdering,
4609 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4610 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4611 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4612 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4614 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4615 Alignment = getEVTAlignment(MemVT);
4617 MachineFunction &MF = getMachineFunction();
4619 // FIXME: Volatile isn't really correct; we should keep track of atomic
4620 // orderings in the memoperand.
4621 unsigned Flags = MachineMemOperand::MOVolatile;
4622 Flags |= MachineMemOperand::MOLoad;
4623 Flags |= MachineMemOperand::MOStore;
4625 MachineMemOperand *MMO =
4626 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4628 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4629 SuccessOrdering, FailureOrdering, SynchScope);
4632 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4633 SDVTList VTs, SDValue Chain, SDValue Ptr,
4634 SDValue Cmp, SDValue Swp,
4635 MachineMemOperand *MMO,
4636 AtomicOrdering SuccessOrdering,
4637 AtomicOrdering FailureOrdering,
4638 SynchronizationScope SynchScope) {
4639 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4640 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4641 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4643 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4644 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4645 SuccessOrdering, FailureOrdering, SynchScope);
4648 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4650 SDValue Ptr, SDValue Val,
4651 const Value* PtrVal,
4653 AtomicOrdering Ordering,
4654 SynchronizationScope SynchScope) {
4655 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4656 Alignment = getEVTAlignment(MemVT);
4658 MachineFunction &MF = getMachineFunction();
4659 // An atomic store does not load. An atomic load does not store.
4660 // (An atomicrmw obviously both loads and stores.)
4661 // For now, atomics are considered to be volatile always, and they are
4663 // FIXME: Volatile isn't really correct; we should keep track of atomic
4664 // orderings in the memoperand.
4665 unsigned Flags = MachineMemOperand::MOVolatile;
4666 if (Opcode != ISD::ATOMIC_STORE)
4667 Flags |= MachineMemOperand::MOLoad;
4668 if (Opcode != ISD::ATOMIC_LOAD)
4669 Flags |= MachineMemOperand::MOStore;
4671 MachineMemOperand *MMO =
4672 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4673 MemVT.getStoreSize(), Alignment);
4675 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4676 Ordering, SynchScope);
4679 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4681 SDValue Ptr, SDValue Val,
4682 MachineMemOperand *MMO,
4683 AtomicOrdering Ordering,
4684 SynchronizationScope SynchScope) {
4685 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4686 Opcode == ISD::ATOMIC_LOAD_SUB ||
4687 Opcode == ISD::ATOMIC_LOAD_AND ||
4688 Opcode == ISD::ATOMIC_LOAD_OR ||
4689 Opcode == ISD::ATOMIC_LOAD_XOR ||
4690 Opcode == ISD::ATOMIC_LOAD_NAND ||
4691 Opcode == ISD::ATOMIC_LOAD_MIN ||
4692 Opcode == ISD::ATOMIC_LOAD_MAX ||
4693 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4694 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4695 Opcode == ISD::ATOMIC_SWAP ||
4696 Opcode == ISD::ATOMIC_STORE) &&
4697 "Invalid Atomic Op");
4699 EVT VT = Val.getValueType();
4701 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4702 getVTList(VT, MVT::Other);
4703 SDValue Ops[] = {Chain, Ptr, Val};
4704 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4707 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4708 EVT VT, SDValue Chain,
4710 MachineMemOperand *MMO,
4711 AtomicOrdering Ordering,
4712 SynchronizationScope SynchScope) {
4713 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4715 SDVTList VTs = getVTList(VT, MVT::Other);
4716 SDValue Ops[] = {Chain, Ptr};
4717 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4720 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4721 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4722 if (Ops.size() == 1)
4725 SmallVector<EVT, 4> VTs;
4726 VTs.reserve(Ops.size());
4727 for (unsigned i = 0; i < Ops.size(); ++i)
4728 VTs.push_back(Ops[i].getValueType());
4729 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4733 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4734 ArrayRef<SDValue> Ops,
4735 EVT MemVT, MachinePointerInfo PtrInfo,
4736 unsigned Align, bool Vol,
4737 bool ReadMem, bool WriteMem, unsigned Size) {
4738 if (Align == 0) // Ensure that codegen never sees alignment 0
4739 Align = getEVTAlignment(MemVT);
4741 MachineFunction &MF = getMachineFunction();
4744 Flags |= MachineMemOperand::MOStore;
4746 Flags |= MachineMemOperand::MOLoad;
4748 Flags |= MachineMemOperand::MOVolatile;
4750 Size = MemVT.getStoreSize();
4751 MachineMemOperand *MMO =
4752 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4754 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4758 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4759 ArrayRef<SDValue> Ops, EVT MemVT,
4760 MachineMemOperand *MMO) {
4761 assert((Opcode == ISD::INTRINSIC_VOID ||
4762 Opcode == ISD::INTRINSIC_W_CHAIN ||
4763 Opcode == ISD::PREFETCH ||
4764 Opcode == ISD::LIFETIME_START ||
4765 Opcode == ISD::LIFETIME_END ||
4766 (Opcode <= INT_MAX &&
4767 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4768 "Opcode is not a memory-accessing opcode!");
4770 // Memoize the node unless it returns a flag.
4771 MemIntrinsicSDNode *N;
4772 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4773 FoldingSetNodeID ID;
4774 AddNodeIDNode(ID, Opcode, VTList, Ops);
4775 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4777 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4778 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4779 return SDValue(E, 0);
4782 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4783 dl.getDebugLoc(), VTList, Ops,
4785 CSEMap.InsertNode(N, IP);
4787 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4788 dl.getDebugLoc(), VTList, Ops,
4792 return SDValue(N, 0);
4795 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4796 /// MachinePointerInfo record from it. This is particularly useful because the
4797 /// code generator has many cases where it doesn't bother passing in a
4798 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4799 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4800 // If this is FI+Offset, we can model it.
4801 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4802 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4804 // If this is (FI+Offset1)+Offset2, we can model it.
4805 if (Ptr.getOpcode() != ISD::ADD ||
4806 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4807 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4808 return MachinePointerInfo();
4810 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4811 return MachinePointerInfo::getFixedStack(FI, Offset+
4812 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4815 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4816 /// MachinePointerInfo record from it. This is particularly useful because the
4817 /// code generator has many cases where it doesn't bother passing in a
4818 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4819 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4820 // If the 'Offset' value isn't a constant, we can't handle this.
4821 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4822 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4823 if (OffsetOp.getOpcode() == ISD::UNDEF)
4824 return InferPointerInfo(Ptr);
4825 return MachinePointerInfo();
4830 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4831 EVT VT, SDLoc dl, SDValue Chain,
4832 SDValue Ptr, SDValue Offset,
4833 MachinePointerInfo PtrInfo, EVT MemVT,
4834 bool isVolatile, bool isNonTemporal, bool isInvariant,
4835 unsigned Alignment, const AAMDNodes &AAInfo,
4836 const MDNode *Ranges) {
4837 assert(Chain.getValueType() == MVT::Other &&
4838 "Invalid chain type");
4839 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4840 Alignment = getEVTAlignment(VT);
4842 unsigned Flags = MachineMemOperand::MOLoad;
4844 Flags |= MachineMemOperand::MOVolatile;
4846 Flags |= MachineMemOperand::MONonTemporal;
4848 Flags |= MachineMemOperand::MOInvariant;
4850 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4852 if (PtrInfo.V.isNull())
4853 PtrInfo = InferPointerInfo(Ptr, Offset);
4855 MachineFunction &MF = getMachineFunction();
4856 MachineMemOperand *MMO =
4857 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4859 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4863 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4864 EVT VT, SDLoc dl, SDValue Chain,
4865 SDValue Ptr, SDValue Offset, EVT MemVT,
4866 MachineMemOperand *MMO) {
4868 ExtType = ISD::NON_EXTLOAD;
4869 } else if (ExtType == ISD::NON_EXTLOAD) {
4870 assert(VT == MemVT && "Non-extending load from different memory type!");
4873 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4874 "Should only be an extending load, not truncating!");
4875 assert(VT.isInteger() == MemVT.isInteger() &&
4876 "Cannot convert from FP to Int or Int -> FP!");
4877 assert(VT.isVector() == MemVT.isVector() &&
4878 "Cannot use an ext load to convert to or from a vector!");
4879 assert((!VT.isVector() ||
4880 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4881 "Cannot use an ext load to change the number of vector elements!");
4884 bool Indexed = AM != ISD::UNINDEXED;
4885 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4886 "Unindexed load with an offset!");
4888 SDVTList VTs = Indexed ?
4889 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4890 SDValue Ops[] = { Chain, Ptr, Offset };
4891 FoldingSetNodeID ID;
4892 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4893 ID.AddInteger(MemVT.getRawBits());
4894 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4895 MMO->isNonTemporal(),
4896 MMO->isInvariant()));
4897 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4899 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4900 cast<LoadSDNode>(E)->refineAlignment(MMO);
4901 return SDValue(E, 0);
4903 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4904 dl.getDebugLoc(), VTs, AM, ExtType,
4906 CSEMap.InsertNode(N, IP);
4908 return SDValue(N, 0);
4911 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4912 SDValue Chain, SDValue Ptr,
4913 MachinePointerInfo PtrInfo,
4914 bool isVolatile, bool isNonTemporal,
4915 bool isInvariant, unsigned Alignment,
4916 const AAMDNodes &AAInfo,
4917 const MDNode *Ranges) {
4918 SDValue Undef = getUNDEF(Ptr.getValueType());
4919 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4920 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4924 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4925 SDValue Chain, SDValue Ptr,
4926 MachineMemOperand *MMO) {
4927 SDValue Undef = getUNDEF(Ptr.getValueType());
4928 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4932 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4933 SDValue Chain, SDValue Ptr,
4934 MachinePointerInfo PtrInfo, EVT MemVT,
4935 bool isVolatile, bool isNonTemporal,
4936 bool isInvariant, unsigned Alignment,
4937 const AAMDNodes &AAInfo) {
4938 SDValue Undef = getUNDEF(Ptr.getValueType());
4939 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4940 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4945 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4946 SDValue Chain, SDValue Ptr, EVT MemVT,
4947 MachineMemOperand *MMO) {
4948 SDValue Undef = getUNDEF(Ptr.getValueType());
4949 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4954 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4955 SDValue Offset, ISD::MemIndexedMode AM) {
4956 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4957 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4958 "Load is already a indexed load!");
4959 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4960 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4961 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4962 false, LD->getAlignment());
4965 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4966 SDValue Ptr, MachinePointerInfo PtrInfo,
4967 bool isVolatile, bool isNonTemporal,
4968 unsigned Alignment, const AAMDNodes &AAInfo) {
4969 assert(Chain.getValueType() == MVT::Other &&
4970 "Invalid chain type");
4971 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4972 Alignment = getEVTAlignment(Val.getValueType());
4974 unsigned Flags = MachineMemOperand::MOStore;
4976 Flags |= MachineMemOperand::MOVolatile;
4978 Flags |= MachineMemOperand::MONonTemporal;
4980 if (PtrInfo.V.isNull())
4981 PtrInfo = InferPointerInfo(Ptr);
4983 MachineFunction &MF = getMachineFunction();
4984 MachineMemOperand *MMO =
4985 MF.getMachineMemOperand(PtrInfo, Flags,
4986 Val.getValueType().getStoreSize(), Alignment,
4989 return getStore(Chain, dl, Val, Ptr, MMO);
4992 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4993 SDValue Ptr, MachineMemOperand *MMO) {
4994 assert(Chain.getValueType() == MVT::Other &&
4995 "Invalid chain type");
4996 EVT VT = Val.getValueType();
4997 SDVTList VTs = getVTList(MVT::Other);
4998 SDValue Undef = getUNDEF(Ptr.getValueType());
4999 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5000 FoldingSetNodeID ID;
5001 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5002 ID.AddInteger(VT.getRawBits());
5003 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5004 MMO->isNonTemporal(), MMO->isInvariant()));
5005 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5007 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5008 cast<StoreSDNode>(E)->refineAlignment(MMO);
5009 return SDValue(E, 0);
5011 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5012 dl.getDebugLoc(), VTs,
5013 ISD::UNINDEXED, false, VT, MMO);
5014 CSEMap.InsertNode(N, IP);
5016 return SDValue(N, 0);
5019 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5020 SDValue Ptr, MachinePointerInfo PtrInfo,
5021 EVT SVT,bool isVolatile, bool isNonTemporal,
5023 const AAMDNodes &AAInfo) {
5024 assert(Chain.getValueType() == MVT::Other &&
5025 "Invalid chain type");
5026 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5027 Alignment = getEVTAlignment(SVT);
5029 unsigned Flags = MachineMemOperand::MOStore;
5031 Flags |= MachineMemOperand::MOVolatile;
5033 Flags |= MachineMemOperand::MONonTemporal;
5035 if (PtrInfo.V.isNull())
5036 PtrInfo = InferPointerInfo(Ptr);
5038 MachineFunction &MF = getMachineFunction();
5039 MachineMemOperand *MMO =
5040 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5043 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5046 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5047 SDValue Ptr, EVT SVT,
5048 MachineMemOperand *MMO) {
5049 EVT VT = Val.getValueType();
5051 assert(Chain.getValueType() == MVT::Other &&
5052 "Invalid chain type");
5054 return getStore(Chain, dl, Val, Ptr, MMO);
5056 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5057 "Should only be a truncating store, not extending!");
5058 assert(VT.isInteger() == SVT.isInteger() &&
5059 "Can't do FP-INT conversion!");
5060 assert(VT.isVector() == SVT.isVector() &&
5061 "Cannot use trunc store to convert to or from a vector!");
5062 assert((!VT.isVector() ||
5063 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5064 "Cannot use trunc store to change the number of vector elements!");
5066 SDVTList VTs = getVTList(MVT::Other);
5067 SDValue Undef = getUNDEF(Ptr.getValueType());
5068 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5069 FoldingSetNodeID ID;
5070 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5071 ID.AddInteger(SVT.getRawBits());
5072 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5073 MMO->isNonTemporal(), MMO->isInvariant()));
5074 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5076 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5077 cast<StoreSDNode>(E)->refineAlignment(MMO);
5078 return SDValue(E, 0);
5080 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5081 dl.getDebugLoc(), VTs,
5082 ISD::UNINDEXED, true, SVT, MMO);
5083 CSEMap.InsertNode(N, IP);
5085 return SDValue(N, 0);
5089 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5090 SDValue Offset, ISD::MemIndexedMode AM) {
5091 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5092 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5093 "Store is already a indexed store!");
5094 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5095 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5096 FoldingSetNodeID ID;
5097 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5098 ID.AddInteger(ST->getMemoryVT().getRawBits());
5099 ID.AddInteger(ST->getRawSubclassData());
5100 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5102 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5103 return SDValue(E, 0);
5105 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5106 dl.getDebugLoc(), VTs, AM,
5107 ST->isTruncatingStore(),
5109 ST->getMemOperand());
5110 CSEMap.InsertNode(N, IP);
5112 return SDValue(N, 0);
5116 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5117 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5118 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5120 SDVTList VTs = getVTList(VT, MVT::Other);
5121 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5122 FoldingSetNodeID ID;
5123 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5124 ID.AddInteger(VT.getRawBits());
5125 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5127 MMO->isNonTemporal(),
5128 MMO->isInvariant()));
5129 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5131 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5132 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5133 return SDValue(E, 0);
5135 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5136 dl.getDebugLoc(), Ops, 4, VTs,
5138 CSEMap.InsertNode(N, IP);
5140 return SDValue(N, 0);
5143 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5144 SDValue Ptr, SDValue Mask, EVT MemVT,
5145 MachineMemOperand *MMO, bool isTrunc) {
5146 assert(Chain.getValueType() == MVT::Other &&
5147 "Invalid chain type");
5148 EVT VT = Val.getValueType();
5149 SDVTList VTs = getVTList(MVT::Other);
5150 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5151 FoldingSetNodeID ID;
5152 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5153 ID.AddInteger(VT.getRawBits());
5154 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5155 MMO->isNonTemporal(), MMO->isInvariant()));
5156 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5158 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5159 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5160 return SDValue(E, 0);
5162 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5163 dl.getDebugLoc(), Ops, 4,
5164 VTs, isTrunc, MemVT, MMO);
5165 CSEMap.InsertNode(N, IP);
5167 return SDValue(N, 0);
5171 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5172 ArrayRef<SDValue> Ops,
5173 MachineMemOperand *MMO) {
5175 FoldingSetNodeID ID;
5176 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5177 ID.AddInteger(VT.getRawBits());
5178 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5180 MMO->isNonTemporal(),
5181 MMO->isInvariant()));
5182 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5184 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5185 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5186 return SDValue(E, 0);
5188 MaskedGatherSDNode *N =
5189 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5191 CSEMap.InsertNode(N, IP);
5193 return SDValue(N, 0);
5196 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5197 ArrayRef<SDValue> Ops,
5198 MachineMemOperand *MMO) {
5199 FoldingSetNodeID ID;
5200 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5201 ID.AddInteger(VT.getRawBits());
5202 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5203 MMO->isNonTemporal(),
5204 MMO->isInvariant()));
5205 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5207 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5208 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5209 return SDValue(E, 0);
5212 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5214 CSEMap.InsertNode(N, IP);
5216 return SDValue(N, 0);
5219 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5220 SDValue Chain, SDValue Ptr,
5223 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5224 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5227 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5228 ArrayRef<SDUse> Ops) {
5229 switch (Ops.size()) {
5230 case 0: return getNode(Opcode, DL, VT);
5231 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5232 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5233 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5237 // Copy from an SDUse array into an SDValue array for use with
5238 // the regular getNode logic.
5239 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5240 return getNode(Opcode, DL, VT, NewOps);
5243 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5244 ArrayRef<SDValue> Ops) {
5245 unsigned NumOps = Ops.size();
5247 case 0: return getNode(Opcode, DL, VT);
5248 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5249 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5250 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5256 case ISD::SELECT_CC: {
5257 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5258 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5259 "LHS and RHS of condition must have same type!");
5260 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5261 "True and False arms of SelectCC must have same type!");
5262 assert(Ops[2].getValueType() == VT &&
5263 "select_cc node must be of same type as true and false value!");
5267 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5268 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5269 "LHS/RHS of comparison should match types!");
5276 SDVTList VTs = getVTList(VT);
5278 if (VT != MVT::Glue) {
5279 FoldingSetNodeID ID;
5280 AddNodeIDNode(ID, Opcode, VTs, Ops);
5283 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5284 return SDValue(E, 0);
5286 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5288 CSEMap.InsertNode(N, IP);
5290 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5295 return SDValue(N, 0);
5298 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5299 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5300 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5303 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5304 ArrayRef<SDValue> Ops) {
5305 if (VTList.NumVTs == 1)
5306 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5310 // FIXME: figure out how to safely handle things like
5311 // int foo(int x) { return 1 << (x & 255); }
5312 // int bar() { return foo(256); }
5313 case ISD::SRA_PARTS:
5314 case ISD::SRL_PARTS:
5315 case ISD::SHL_PARTS:
5316 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5317 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5318 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5319 else if (N3.getOpcode() == ISD::AND)
5320 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5321 // If the and is only masking out bits that cannot effect the shift,
5322 // eliminate the and.
5323 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5324 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5325 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5331 // Memoize the node unless it returns a flag.
5333 unsigned NumOps = Ops.size();
5334 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5335 FoldingSetNodeID ID;
5336 AddNodeIDNode(ID, Opcode, VTList, Ops);
5338 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5339 return SDValue(E, 0);
5342 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5343 DL.getDebugLoc(), VTList, Ops[0]);
5344 } else if (NumOps == 2) {
5345 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5346 DL.getDebugLoc(), VTList, Ops[0],
5348 } else if (NumOps == 3) {
5349 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5350 DL.getDebugLoc(), VTList, Ops[0],
5353 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5356 CSEMap.InsertNode(N, IP);
5359 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5360 DL.getDebugLoc(), VTList, Ops[0]);
5361 } else if (NumOps == 2) {
5362 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5363 DL.getDebugLoc(), VTList, Ops[0],
5365 } else if (NumOps == 3) {
5366 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5367 DL.getDebugLoc(), VTList, Ops[0],
5370 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5375 return SDValue(N, 0);
5378 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5379 return getNode(Opcode, DL, VTList, None);
5382 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5384 SDValue Ops[] = { N1 };
5385 return getNode(Opcode, DL, VTList, Ops);
5388 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5389 SDValue N1, SDValue N2) {
5390 SDValue Ops[] = { N1, N2 };
5391 return getNode(Opcode, DL, VTList, Ops);
5394 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5395 SDValue N1, SDValue N2, SDValue N3) {
5396 SDValue Ops[] = { N1, N2, N3 };
5397 return getNode(Opcode, DL, VTList, Ops);
5400 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5401 SDValue N1, SDValue N2, SDValue N3,
5403 SDValue Ops[] = { N1, N2, N3, N4 };
5404 return getNode(Opcode, DL, VTList, Ops);
5407 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5408 SDValue N1, SDValue N2, SDValue N3,
5409 SDValue N4, SDValue N5) {
5410 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5411 return getNode(Opcode, DL, VTList, Ops);
5414 SDVTList SelectionDAG::getVTList(EVT VT) {
5415 return makeVTList(SDNode::getValueTypeList(VT), 1);
5418 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5419 FoldingSetNodeID ID;
5421 ID.AddInteger(VT1.getRawBits());
5422 ID.AddInteger(VT2.getRawBits());
5425 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5427 EVT *Array = Allocator.Allocate<EVT>(2);
5430 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5431 VTListMap.InsertNode(Result, IP);
5433 return Result->getSDVTList();
5436 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5437 FoldingSetNodeID ID;
5439 ID.AddInteger(VT1.getRawBits());
5440 ID.AddInteger(VT2.getRawBits());
5441 ID.AddInteger(VT3.getRawBits());
5444 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5446 EVT *Array = Allocator.Allocate<EVT>(3);
5450 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5451 VTListMap.InsertNode(Result, IP);
5453 return Result->getSDVTList();
5456 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5457 FoldingSetNodeID ID;
5459 ID.AddInteger(VT1.getRawBits());
5460 ID.AddInteger(VT2.getRawBits());
5461 ID.AddInteger(VT3.getRawBits());
5462 ID.AddInteger(VT4.getRawBits());
5465 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5467 EVT *Array = Allocator.Allocate<EVT>(4);
5472 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5473 VTListMap.InsertNode(Result, IP);
5475 return Result->getSDVTList();
5478 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5479 unsigned NumVTs = VTs.size();
5480 FoldingSetNodeID ID;
5481 ID.AddInteger(NumVTs);
5482 for (unsigned index = 0; index < NumVTs; index++) {
5483 ID.AddInteger(VTs[index].getRawBits());
5487 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5489 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5490 std::copy(VTs.begin(), VTs.end(), Array);
5491 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5492 VTListMap.InsertNode(Result, IP);
5494 return Result->getSDVTList();
5498 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5499 /// specified operands. If the resultant node already exists in the DAG,
5500 /// this does not modify the specified node, instead it returns the node that
5501 /// already exists. If the resultant node does not exist in the DAG, the
5502 /// input node is returned. As a degenerate case, if you specify the same
5503 /// input operands as the node already has, the input node is returned.
5504 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5505 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5507 // Check to see if there is no change.
5508 if (Op == N->getOperand(0)) return N;
5510 // See if the modified node already exists.
5511 void *InsertPos = nullptr;
5512 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5515 // Nope it doesn't. Remove the node from its current place in the maps.
5517 if (!RemoveNodeFromCSEMaps(N))
5518 InsertPos = nullptr;
5520 // Now we update the operands.
5521 N->OperandList[0].set(Op);
5523 // If this gets put into a CSE map, add it.
5524 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5528 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5529 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5531 // Check to see if there is no change.
5532 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5533 return N; // No operands changed, just return the input node.
5535 // See if the modified node already exists.
5536 void *InsertPos = nullptr;
5537 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5540 // Nope it doesn't. Remove the node from its current place in the maps.
5542 if (!RemoveNodeFromCSEMaps(N))
5543 InsertPos = nullptr;
5545 // Now we update the operands.
5546 if (N->OperandList[0] != Op1)
5547 N->OperandList[0].set(Op1);
5548 if (N->OperandList[1] != Op2)
5549 N->OperandList[1].set(Op2);
5551 // If this gets put into a CSE map, add it.
5552 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5556 SDNode *SelectionDAG::
5557 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5558 SDValue Ops[] = { Op1, Op2, Op3 };
5559 return UpdateNodeOperands(N, Ops);
5562 SDNode *SelectionDAG::
5563 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5564 SDValue Op3, SDValue Op4) {
5565 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5566 return UpdateNodeOperands(N, Ops);
5569 SDNode *SelectionDAG::
5570 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5571 SDValue Op3, SDValue Op4, SDValue Op5) {
5572 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5573 return UpdateNodeOperands(N, Ops);
5576 SDNode *SelectionDAG::
5577 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5578 unsigned NumOps = Ops.size();
5579 assert(N->getNumOperands() == NumOps &&
5580 "Update with wrong number of operands");
5582 // If no operands changed just return the input node.
5583 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5586 // See if the modified node already exists.
5587 void *InsertPos = nullptr;
5588 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5591 // Nope it doesn't. Remove the node from its current place in the maps.
5593 if (!RemoveNodeFromCSEMaps(N))
5594 InsertPos = nullptr;
5596 // Now we update the operands.
5597 for (unsigned i = 0; i != NumOps; ++i)
5598 if (N->OperandList[i] != Ops[i])
5599 N->OperandList[i].set(Ops[i]);
5601 // If this gets put into a CSE map, add it.
5602 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5606 /// DropOperands - Release the operands and set this node to have
5608 void SDNode::DropOperands() {
5609 // Unlike the code in MorphNodeTo that does this, we don't need to
5610 // watch for dead nodes here.
5611 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5617 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5620 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5622 SDVTList VTs = getVTList(VT);
5623 return SelectNodeTo(N, MachineOpc, VTs, None);
5626 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5627 EVT VT, SDValue Op1) {
5628 SDVTList VTs = getVTList(VT);
5629 SDValue Ops[] = { Op1 };
5630 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5633 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5634 EVT VT, SDValue Op1,
5636 SDVTList VTs = getVTList(VT);
5637 SDValue Ops[] = { Op1, Op2 };
5638 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5641 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5642 EVT VT, SDValue Op1,
5643 SDValue Op2, SDValue Op3) {
5644 SDVTList VTs = getVTList(VT);
5645 SDValue Ops[] = { Op1, Op2, Op3 };
5646 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5649 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5650 EVT VT, ArrayRef<SDValue> Ops) {
5651 SDVTList VTs = getVTList(VT);
5652 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5655 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5656 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5657 SDVTList VTs = getVTList(VT1, VT2);
5658 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5661 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5663 SDVTList VTs = getVTList(VT1, VT2);
5664 return SelectNodeTo(N, MachineOpc, VTs, None);
5667 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5668 EVT VT1, EVT VT2, EVT VT3,
5669 ArrayRef<SDValue> Ops) {
5670 SDVTList VTs = getVTList(VT1, VT2, VT3);
5671 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5674 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5675 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5676 ArrayRef<SDValue> Ops) {
5677 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5678 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5681 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5684 SDVTList VTs = getVTList(VT1, VT2);
5685 SDValue Ops[] = { Op1 };
5686 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5689 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5691 SDValue Op1, SDValue Op2) {
5692 SDVTList VTs = getVTList(VT1, VT2);
5693 SDValue Ops[] = { Op1, Op2 };
5694 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5699 SDValue Op1, SDValue Op2,
5701 SDVTList VTs = getVTList(VT1, VT2);
5702 SDValue Ops[] = { Op1, Op2, Op3 };
5703 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5706 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5707 EVT VT1, EVT VT2, EVT VT3,
5708 SDValue Op1, SDValue Op2,
5710 SDVTList VTs = getVTList(VT1, VT2, VT3);
5711 SDValue Ops[] = { Op1, Op2, Op3 };
5712 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5715 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5716 SDVTList VTs,ArrayRef<SDValue> Ops) {
5717 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5718 // Reset the NodeID to -1.
5723 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5724 /// the line number information on the merged node since it is not possible to
5725 /// preserve the information that operation is associated with multiple lines.
5726 /// This will make the debugger working better at -O0, were there is a higher
5727 /// probability having other instructions associated with that line.
5729 /// For IROrder, we keep the smaller of the two
5730 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5731 DebugLoc NLoc = N->getDebugLoc();
5732 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5733 N->setDebugLoc(DebugLoc());
5735 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5736 N->setIROrder(Order);
5740 /// MorphNodeTo - This *mutates* the specified node to have the specified
5741 /// return type, opcode, and operands.
5743 /// Note that MorphNodeTo returns the resultant node. If there is already a
5744 /// node of the specified opcode and operands, it returns that node instead of
5745 /// the current one. Note that the SDLoc need not be the same.
5747 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5748 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5749 /// node, and because it doesn't require CSE recalculation for any of
5750 /// the node's users.
5752 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5753 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5754 /// the legalizer which maintain worklists that would need to be updated when
5755 /// deleting things.
5756 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5757 SDVTList VTs, ArrayRef<SDValue> Ops) {
5758 unsigned NumOps = Ops.size();
5759 // If an identical node already exists, use it.
5761 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5762 FoldingSetNodeID ID;
5763 AddNodeIDNode(ID, Opc, VTs, Ops);
5764 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5765 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5768 if (!RemoveNodeFromCSEMaps(N))
5771 // Start the morphing.
5773 N->ValueList = VTs.VTs;
5774 N->NumValues = VTs.NumVTs;
5776 // Clear the operands list, updating used nodes to remove this from their
5777 // use list. Keep track of any operands that become dead as a result.
5778 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5779 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5781 SDNode *Used = Use.getNode();
5783 if (Used->use_empty())
5784 DeadNodeSet.insert(Used);
5787 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5788 // Initialize the memory references information.
5789 MN->setMemRefs(nullptr, nullptr);
5790 // If NumOps is larger than the # of operands we can have in a
5791 // MachineSDNode, reallocate the operand list.
5792 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5793 if (MN->OperandsNeedDelete)
5794 delete[] MN->OperandList;
5795 if (NumOps > array_lengthof(MN->LocalOperands))
5796 // We're creating a final node that will live unmorphed for the
5797 // remainder of the current SelectionDAG iteration, so we can allocate
5798 // the operands directly out of a pool with no recycling metadata.
5799 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5800 Ops.data(), NumOps);
5802 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5803 MN->OperandsNeedDelete = false;
5805 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5807 // If NumOps is larger than the # of operands we currently have, reallocate
5808 // the operand list.
5809 if (NumOps > N->NumOperands) {
5810 if (N->OperandsNeedDelete)
5811 delete[] N->OperandList;
5812 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5813 N->OperandsNeedDelete = true;
5815 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5818 // Delete any nodes that are still dead after adding the uses for the
5820 if (!DeadNodeSet.empty()) {
5821 SmallVector<SDNode *, 16> DeadNodes;
5822 for (SDNode *N : DeadNodeSet)
5824 DeadNodes.push_back(N);
5825 RemoveDeadNodes(DeadNodes);
5829 CSEMap.InsertNode(N, IP); // Memoize the new node.
5834 /// getMachineNode - These are used for target selectors to create a new node
5835 /// with specified return type(s), MachineInstr opcode, and operands.
5837 /// Note that getMachineNode returns the resultant node. If there is already a
5838 /// node of the specified opcode and operands, it returns that node instead of
5839 /// the current one.
5841 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5842 SDVTList VTs = getVTList(VT);
5843 return getMachineNode(Opcode, dl, VTs, None);
5847 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5848 SDVTList VTs = getVTList(VT);
5849 SDValue Ops[] = { Op1 };
5850 return getMachineNode(Opcode, dl, VTs, Ops);
5854 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5855 SDValue Op1, SDValue Op2) {
5856 SDVTList VTs = getVTList(VT);
5857 SDValue Ops[] = { Op1, Op2 };
5858 return getMachineNode(Opcode, dl, VTs, Ops);
5862 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5863 SDValue Op1, SDValue Op2, SDValue Op3) {
5864 SDVTList VTs = getVTList(VT);
5865 SDValue Ops[] = { Op1, Op2, Op3 };
5866 return getMachineNode(Opcode, dl, VTs, Ops);
5870 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5871 ArrayRef<SDValue> Ops) {
5872 SDVTList VTs = getVTList(VT);
5873 return getMachineNode(Opcode, dl, VTs, Ops);
5877 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5878 SDVTList VTs = getVTList(VT1, VT2);
5879 return getMachineNode(Opcode, dl, VTs, None);
5883 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5884 EVT VT1, EVT VT2, SDValue Op1) {
5885 SDVTList VTs = getVTList(VT1, VT2);
5886 SDValue Ops[] = { Op1 };
5887 return getMachineNode(Opcode, dl, VTs, Ops);
5891 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5892 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5893 SDVTList VTs = getVTList(VT1, VT2);
5894 SDValue Ops[] = { Op1, Op2 };
5895 return getMachineNode(Opcode, dl, VTs, Ops);
5899 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5900 EVT VT1, EVT VT2, SDValue Op1,
5901 SDValue Op2, SDValue Op3) {
5902 SDVTList VTs = getVTList(VT1, VT2);
5903 SDValue Ops[] = { Op1, Op2, Op3 };
5904 return getMachineNode(Opcode, dl, VTs, Ops);
5908 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5910 ArrayRef<SDValue> Ops) {
5911 SDVTList VTs = getVTList(VT1, VT2);
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) {
5919 SDVTList VTs = getVTList(VT1, VT2, VT3);
5920 SDValue Ops[] = { Op1, Op2 };
5921 return getMachineNode(Opcode, dl, VTs, Ops);
5925 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5926 EVT VT1, EVT VT2, EVT VT3,
5927 SDValue Op1, SDValue Op2, SDValue Op3) {
5928 SDVTList VTs = getVTList(VT1, VT2, VT3);
5929 SDValue Ops[] = { Op1, Op2, Op3 };
5930 return getMachineNode(Opcode, dl, VTs, Ops);
5934 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5935 EVT VT1, EVT VT2, EVT VT3,
5936 ArrayRef<SDValue> Ops) {
5937 SDVTList VTs = getVTList(VT1, VT2, VT3);
5938 return getMachineNode(Opcode, dl, VTs, Ops);
5942 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5943 EVT VT2, EVT VT3, EVT VT4,
5944 ArrayRef<SDValue> Ops) {
5945 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5946 return getMachineNode(Opcode, dl, VTs, Ops);
5950 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5951 ArrayRef<EVT> ResultTys,
5952 ArrayRef<SDValue> Ops) {
5953 SDVTList VTs = getVTList(ResultTys);
5954 return getMachineNode(Opcode, dl, VTs, Ops);
5958 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5959 ArrayRef<SDValue> OpsArray) {
5960 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5963 const SDValue *Ops = OpsArray.data();
5964 unsigned NumOps = OpsArray.size();
5967 FoldingSetNodeID ID;
5968 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5970 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5971 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5975 // Allocate a new MachineSDNode.
5976 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5977 DL.getDebugLoc(), VTs);
5979 // Initialize the operands list.
5980 if (NumOps > array_lengthof(N->LocalOperands))
5981 // We're creating a final node that will live unmorphed for the
5982 // remainder of the current SelectionDAG iteration, so we can allocate
5983 // the operands directly out of a pool with no recycling metadata.
5984 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5987 N->InitOperands(N->LocalOperands, Ops, NumOps);
5988 N->OperandsNeedDelete = false;
5991 CSEMap.InsertNode(N, IP);
5997 /// getTargetExtractSubreg - A convenience function for creating
5998 /// TargetOpcode::EXTRACT_SUBREG nodes.
6000 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6002 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6003 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6004 VT, Operand, SRIdxVal);
6005 return SDValue(Subreg, 0);
6008 /// getTargetInsertSubreg - A convenience function for creating
6009 /// TargetOpcode::INSERT_SUBREG nodes.
6011 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6012 SDValue Operand, SDValue Subreg) {
6013 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6014 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6015 VT, Operand, Subreg, SRIdxVal);
6016 return SDValue(Result, 0);
6019 /// getNodeIfExists - Get the specified node if it's already available, or
6020 /// else return NULL.
6021 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6022 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
6024 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6025 FoldingSetNodeID ID;
6026 AddNodeIDNode(ID, Opcode, VTList, Ops);
6027 if (isBinOpWithFlags(Opcode))
6028 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
6030 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6036 /// getDbgValue - Creates a SDDbgValue node.
6039 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6040 unsigned R, bool IsIndirect, 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, N, R, IsIndirect, Off, DL, O);
6048 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6049 const Value *C, 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, C, Off, DL, O);
6057 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6058 unsigned FI, uint64_t Off,
6059 DebugLoc DL, unsigned O) {
6060 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6061 "Expected inlined-at fields to agree");
6062 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6067 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6068 /// pointed to by a use iterator is deleted, increment the use iterator
6069 /// so that it doesn't dangle.
6071 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6072 SDNode::use_iterator &UI;
6073 SDNode::use_iterator &UE;
6075 void NodeDeleted(SDNode *N, SDNode *E) override {
6076 // Increment the iterator as needed.
6077 while (UI != UE && N == *UI)
6082 RAUWUpdateListener(SelectionDAG &d,
6083 SDNode::use_iterator &ui,
6084 SDNode::use_iterator &ue)
6085 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6090 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6091 /// This can cause recursive merging of nodes in the DAG.
6093 /// This version assumes From has a single result value.
6095 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6096 SDNode *From = FromN.getNode();
6097 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6098 "Cannot replace with this method!");
6099 assert(From != To.getNode() && "Cannot replace uses of with self");
6101 // Iterate over all the existing uses of From. New uses will be added
6102 // to the beginning of the use list, which we avoid visiting.
6103 // This specifically avoids visiting uses of From that arise while the
6104 // replacement is happening, because any such uses would be the result
6105 // of CSE: If an existing node looks like From after one of its operands
6106 // is replaced by To, we don't want to replace of all its users with To
6107 // too. See PR3018 for more info.
6108 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6109 RAUWUpdateListener Listener(*this, UI, UE);
6113 // This node is about to morph, remove its old self from the CSE maps.
6114 RemoveNodeFromCSEMaps(User);
6116 // A user can appear in a use list multiple times, and when this
6117 // happens the uses are usually next to each other in the list.
6118 // To help reduce the number of CSE recomputations, process all
6119 // the uses of this user that we can find this way.
6121 SDUse &Use = UI.getUse();
6124 } while (UI != UE && *UI == User);
6126 // Now that we have modified User, add it back to the CSE maps. If it
6127 // already exists there, recursively merge the results together.
6128 AddModifiedNodeToCSEMaps(User);
6131 // If we just RAUW'd the root, take note.
6132 if (FromN == getRoot())
6136 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6137 /// This can cause recursive merging of nodes in the DAG.
6139 /// This version assumes that for each value of From, there is a
6140 /// corresponding value in To in the same position with the same type.
6142 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6144 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6145 assert((!From->hasAnyUseOfValue(i) ||
6146 From->getValueType(i) == To->getValueType(i)) &&
6147 "Cannot use this version of ReplaceAllUsesWith!");
6150 // Handle the trivial case.
6154 // Iterate over just the existing users of From. See the comments in
6155 // the ReplaceAllUsesWith above.
6156 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6157 RAUWUpdateListener Listener(*this, UI, UE);
6161 // This node is about to morph, remove its old self from the CSE maps.
6162 RemoveNodeFromCSEMaps(User);
6164 // A user can appear in a use list multiple times, and when this
6165 // happens the uses are usually next to each other in the list.
6166 // To help reduce the number of CSE recomputations, process all
6167 // the uses of this user that we can find this way.
6169 SDUse &Use = UI.getUse();
6172 } while (UI != UE && *UI == User);
6174 // Now that we have modified User, add it back to the CSE maps. If it
6175 // already exists there, recursively merge the results together.
6176 AddModifiedNodeToCSEMaps(User);
6179 // If we just RAUW'd the root, take note.
6180 if (From == getRoot().getNode())
6181 setRoot(SDValue(To, getRoot().getResNo()));
6184 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6185 /// This can cause recursive merging of nodes in the DAG.
6187 /// This version can replace From with any result values. To must match the
6188 /// number and types of values returned by From.
6189 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6190 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6191 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6193 // Iterate over just the existing users of From. See the comments in
6194 // the ReplaceAllUsesWith above.
6195 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6196 RAUWUpdateListener Listener(*this, UI, UE);
6200 // This node is about to morph, remove its old self from the CSE maps.
6201 RemoveNodeFromCSEMaps(User);
6203 // A user can appear in a use list multiple times, and when this
6204 // happens the uses are usually next to each other in the list.
6205 // To help reduce the number of CSE recomputations, process all
6206 // the uses of this user that we can find this way.
6208 SDUse &Use = UI.getUse();
6209 const SDValue &ToOp = To[Use.getResNo()];
6212 } while (UI != UE && *UI == User);
6214 // Now that we have modified User, add it back to the CSE maps. If it
6215 // already exists there, recursively merge the results together.
6216 AddModifiedNodeToCSEMaps(User);
6219 // If we just RAUW'd the root, take note.
6220 if (From == getRoot().getNode())
6221 setRoot(SDValue(To[getRoot().getResNo()]));
6224 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6225 /// uses of other values produced by From.getNode() alone. The Deleted
6226 /// vector is handled the same way as for ReplaceAllUsesWith.
6227 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6228 // Handle the really simple, really trivial case efficiently.
6229 if (From == To) return;
6231 // Handle the simple, trivial, case efficiently.
6232 if (From.getNode()->getNumValues() == 1) {
6233 ReplaceAllUsesWith(From, To);
6237 // Iterate over just the existing users of From. See the comments in
6238 // the ReplaceAllUsesWith above.
6239 SDNode::use_iterator UI = From.getNode()->use_begin(),
6240 UE = From.getNode()->use_end();
6241 RAUWUpdateListener Listener(*this, UI, UE);
6244 bool UserRemovedFromCSEMaps = false;
6246 // A user can appear in a use list multiple times, and when this
6247 // happens the uses are usually next to each other in the list.
6248 // To help reduce the number of CSE recomputations, process all
6249 // the uses of this user that we can find this way.
6251 SDUse &Use = UI.getUse();
6253 // Skip uses of different values from the same node.
6254 if (Use.getResNo() != From.getResNo()) {
6259 // If this node hasn't been modified yet, it's still in the CSE maps,
6260 // so remove its old self from the CSE maps.
6261 if (!UserRemovedFromCSEMaps) {
6262 RemoveNodeFromCSEMaps(User);
6263 UserRemovedFromCSEMaps = true;
6268 } while (UI != UE && *UI == User);
6270 // We are iterating over all uses of the From node, so if a use
6271 // doesn't use the specific value, no changes are made.
6272 if (!UserRemovedFromCSEMaps)
6275 // Now that we have modified User, add it back to the CSE maps. If it
6276 // already exists there, recursively merge the results together.
6277 AddModifiedNodeToCSEMaps(User);
6280 // If we just RAUW'd the root, take note.
6281 if (From == getRoot())
6286 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6287 /// to record information about a use.
6294 /// operator< - Sort Memos by User.
6295 bool operator<(const UseMemo &L, const UseMemo &R) {
6296 return (intptr_t)L.User < (intptr_t)R.User;
6300 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6301 /// uses of other values produced by From.getNode() alone. The same value
6302 /// may appear in both the From and To list. The Deleted vector is
6303 /// handled the same way as for ReplaceAllUsesWith.
6304 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6307 // Handle the simple, trivial case efficiently.
6309 return ReplaceAllUsesOfValueWith(*From, *To);
6311 // Read up all the uses and make records of them. This helps
6312 // processing new uses that are introduced during the
6313 // replacement process.
6314 SmallVector<UseMemo, 4> Uses;
6315 for (unsigned i = 0; i != Num; ++i) {
6316 unsigned FromResNo = From[i].getResNo();
6317 SDNode *FromNode = From[i].getNode();
6318 for (SDNode::use_iterator UI = FromNode->use_begin(),
6319 E = FromNode->use_end(); UI != E; ++UI) {
6320 SDUse &Use = UI.getUse();
6321 if (Use.getResNo() == FromResNo) {
6322 UseMemo Memo = { *UI, i, &Use };
6323 Uses.push_back(Memo);
6328 // Sort the uses, so that all the uses from a given User are together.
6329 std::sort(Uses.begin(), Uses.end());
6331 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6332 UseIndex != UseIndexEnd; ) {
6333 // We know that this user uses some value of From. If it is the right
6334 // value, update it.
6335 SDNode *User = Uses[UseIndex].User;
6337 // This node is about to morph, remove its old self from the CSE maps.
6338 RemoveNodeFromCSEMaps(User);
6340 // The Uses array is sorted, so all the uses for a given User
6341 // are next to each other in the list.
6342 // To help reduce the number of CSE recomputations, process all
6343 // the uses of this user that we can find this way.
6345 unsigned i = Uses[UseIndex].Index;
6346 SDUse &Use = *Uses[UseIndex].Use;
6350 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6352 // Now that we have modified User, add it back to the CSE maps. If it
6353 // already exists there, recursively merge the results together.
6354 AddModifiedNodeToCSEMaps(User);
6358 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6359 /// based on their topological order. It returns the maximum id and a vector
6360 /// of the SDNodes* in assigned order by reference.
6361 unsigned SelectionDAG::AssignTopologicalOrder() {
6363 unsigned DAGSize = 0;
6365 // SortedPos tracks the progress of the algorithm. Nodes before it are
6366 // sorted, nodes after it are unsorted. When the algorithm completes
6367 // it is at the end of the list.
6368 allnodes_iterator SortedPos = allnodes_begin();
6370 // Visit all the nodes. Move nodes with no operands to the front of
6371 // the list immediately. Annotate nodes that do have operands with their
6372 // operand count. Before we do this, the Node Id fields of the nodes
6373 // may contain arbitrary values. After, the Node Id fields for nodes
6374 // before SortedPos will contain the topological sort index, and the
6375 // Node Id fields for nodes At SortedPos and after will contain the
6376 // count of outstanding operands.
6377 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6379 checkForCycles(N, this);
6380 unsigned Degree = N->getNumOperands();
6382 // A node with no uses, add it to the result array immediately.
6383 N->setNodeId(DAGSize++);
6384 allnodes_iterator Q = N;
6386 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6387 assert(SortedPos != AllNodes.end() && "Overran node list");
6390 // Temporarily use the Node Id as scratch space for the degree count.
6391 N->setNodeId(Degree);
6395 // Visit all the nodes. As we iterate, move nodes into sorted order,
6396 // such that by the time the end is reached all nodes will be sorted.
6397 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6399 checkForCycles(N, this);
6400 // N is in sorted position, so all its uses have one less operand
6401 // that needs to be sorted.
6402 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6405 unsigned Degree = P->getNodeId();
6406 assert(Degree != 0 && "Invalid node degree");
6409 // All of P's operands are sorted, so P may sorted now.
6410 P->setNodeId(DAGSize++);
6412 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6413 assert(SortedPos != AllNodes.end() && "Overran node list");
6416 // Update P's outstanding operand count.
6417 P->setNodeId(Degree);
6420 if (I == SortedPos) {
6423 dbgs() << "Overran sorted position:\n";
6424 S->dumprFull(this); dbgs() << "\n";
6425 dbgs() << "Checking if this is due to cycles\n";
6426 checkForCycles(this, true);
6428 llvm_unreachable(nullptr);
6432 assert(SortedPos == AllNodes.end() &&
6433 "Topological sort incomplete!");
6434 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6435 "First node in topological sort is not the entry token!");
6436 assert(AllNodes.front().getNodeId() == 0 &&
6437 "First node in topological sort has non-zero id!");
6438 assert(AllNodes.front().getNumOperands() == 0 &&
6439 "First node in topological sort has operands!");
6440 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6441 "Last node in topologic sort has unexpected id!");
6442 assert(AllNodes.back().use_empty() &&
6443 "Last node in topologic sort has users!");
6444 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6448 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6449 /// value is produced by SD.
6450 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6452 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6453 SD->setHasDebugValue(true);
6455 DbgInfo->add(DB, SD, isParameter);
6458 /// TransferDbgValues - Transfer SDDbgValues.
6459 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6460 if (From == To || !From.getNode()->getHasDebugValue())
6462 SDNode *FromNode = From.getNode();
6463 SDNode *ToNode = To.getNode();
6464 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6465 SmallVector<SDDbgValue *, 2> ClonedDVs;
6466 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6468 SDDbgValue *Dbg = *I;
6469 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6471 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6472 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6473 Dbg->getDebugLoc(), Dbg->getOrder());
6474 ClonedDVs.push_back(Clone);
6477 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6478 E = ClonedDVs.end(); I != E; ++I)
6479 AddDbgValue(*I, ToNode, false);
6482 //===----------------------------------------------------------------------===//
6484 //===----------------------------------------------------------------------===//
6486 HandleSDNode::~HandleSDNode() {
6490 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6491 DebugLoc DL, const GlobalValue *GA,
6492 EVT VT, int64_t o, unsigned char TF)
6493 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6497 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6498 SDValue X, unsigned SrcAS,
6500 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6501 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6503 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6504 EVT memvt, MachineMemOperand *mmo)
6505 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6506 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6507 MMO->isNonTemporal(), MMO->isInvariant());
6508 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6509 assert(isNonTemporal() == MMO->isNonTemporal() &&
6510 "Non-temporal encoding error!");
6511 // We check here that the size of the memory operand fits within the size of
6512 // the MMO. This is because the MMO might indicate only a possible address
6513 // range instead of specifying the affected memory addresses precisely.
6514 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6517 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6518 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6519 : SDNode(Opc, Order, dl, VTs, Ops),
6520 MemoryVT(memvt), MMO(mmo) {
6521 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6522 MMO->isNonTemporal(), MMO->isInvariant());
6523 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6524 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6527 /// Profile - Gather unique data for the node.
6529 void SDNode::Profile(FoldingSetNodeID &ID) const {
6530 AddNodeIDNode(ID, this);
6535 std::vector<EVT> VTs;
6538 VTs.reserve(MVT::LAST_VALUETYPE);
6539 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6540 VTs.push_back(MVT((MVT::SimpleValueType)i));
6545 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6546 static ManagedStatic<EVTArray> SimpleVTArray;
6547 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6549 /// getValueTypeList - Return a pointer to the specified value type.
6551 const EVT *SDNode::getValueTypeList(EVT VT) {
6552 if (VT.isExtended()) {
6553 sys::SmartScopedLock<true> Lock(*VTMutex);
6554 return &(*EVTs->insert(VT).first);
6556 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6557 "Value type out of range!");
6558 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6562 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6563 /// indicated value. This method ignores uses of other values defined by this
6565 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6566 assert(Value < getNumValues() && "Bad value!");
6568 // TODO: Only iterate over uses of a given value of the node
6569 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6570 if (UI.getUse().getResNo() == Value) {
6577 // Found exactly the right number of uses?
6582 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6583 /// value. This method ignores uses of other values defined by this operation.
6584 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6585 assert(Value < getNumValues() && "Bad value!");
6587 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6588 if (UI.getUse().getResNo() == Value)
6595 /// isOnlyUserOf - Return true if this node is the only use of N.
6597 bool SDNode::isOnlyUserOf(SDNode *N) const {
6599 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6610 /// isOperand - Return true if this node is an operand of N.
6612 bool SDValue::isOperandOf(SDNode *N) const {
6613 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6614 if (*this == N->getOperand(i))
6619 bool SDNode::isOperandOf(SDNode *N) const {
6620 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6621 if (this == N->OperandList[i].getNode())
6626 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6627 /// be a chain) reaches the specified operand without crossing any
6628 /// side-effecting instructions on any chain path. In practice, this looks
6629 /// through token factors and non-volatile loads. In order to remain efficient,
6630 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6631 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6632 unsigned Depth) const {
6633 if (*this == Dest) return true;
6635 // Don't search too deeply, we just want to be able to see through
6636 // TokenFactor's etc.
6637 if (Depth == 0) return false;
6639 // If this is a token factor, all inputs to the TF happen in parallel. If any
6640 // of the operands of the TF does not reach dest, then we cannot do the xform.
6641 if (getOpcode() == ISD::TokenFactor) {
6642 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6643 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6648 // Loads don't have side effects, look through them.
6649 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6650 if (!Ld->isVolatile())
6651 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6656 /// hasPredecessor - Return true if N is a predecessor of this node.
6657 /// N is either an operand of this node, or can be reached by recursively
6658 /// traversing up the operands.
6659 /// NOTE: This is an expensive method. Use it carefully.
6660 bool SDNode::hasPredecessor(const SDNode *N) const {
6661 SmallPtrSet<const SDNode *, 32> Visited;
6662 SmallVector<const SDNode *, 16> Worklist;
6663 return hasPredecessorHelper(N, Visited, Worklist);
6667 SDNode::hasPredecessorHelper(const SDNode *N,
6668 SmallPtrSetImpl<const SDNode *> &Visited,
6669 SmallVectorImpl<const SDNode *> &Worklist) const {
6670 if (Visited.empty()) {
6671 Worklist.push_back(this);
6673 // Take a look in the visited set. If we've already encountered this node
6674 // we needn't search further.
6675 if (Visited.count(N))
6679 // Haven't visited N yet. Continue the search.
6680 while (!Worklist.empty()) {
6681 const SDNode *M = Worklist.pop_back_val();
6682 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6683 SDNode *Op = M->getOperand(i).getNode();
6684 if (Visited.insert(Op).second)
6685 Worklist.push_back(Op);
6694 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6695 assert(Num < NumOperands && "Invalid child # of SDNode!");
6696 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6699 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6700 assert(N->getNumValues() == 1 &&
6701 "Can't unroll a vector with multiple results!");
6703 EVT VT = N->getValueType(0);
6704 unsigned NE = VT.getVectorNumElements();
6705 EVT EltVT = VT.getVectorElementType();
6708 SmallVector<SDValue, 8> Scalars;
6709 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6711 // If ResNE is 0, fully unroll the vector op.
6714 else if (NE > ResNE)
6718 for (i= 0; i != NE; ++i) {
6719 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6720 SDValue Operand = N->getOperand(j);
6721 EVT OperandVT = Operand.getValueType();
6722 if (OperandVT.isVector()) {
6723 // A vector operand; extract a single element.
6724 EVT OperandEltVT = OperandVT.getVectorElementType();
6725 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6728 getConstant(i, dl, TLI->getVectorIdxTy()));
6730 // A scalar operand; just use it as is.
6731 Operands[j] = Operand;
6735 switch (N->getOpcode()) {
6737 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6740 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6747 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6748 getShiftAmountOperand(Operands[0].getValueType(),
6751 case ISD::SIGN_EXTEND_INREG:
6752 case ISD::FP_ROUND_INREG: {
6753 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6754 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6756 getValueType(ExtVT)));
6761 for (; i < ResNE; ++i)
6762 Scalars.push_back(getUNDEF(EltVT));
6764 return getNode(ISD::BUILD_VECTOR, dl,
6765 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6769 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6770 /// location that is 'Dist' units away from the location that the 'Base' load
6771 /// is loading from.
6772 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6773 unsigned Bytes, int Dist) const {
6774 if (LD->getChain() != Base->getChain())
6776 EVT VT = LD->getValueType(0);
6777 if (VT.getSizeInBits() / 8 != Bytes)
6780 SDValue Loc = LD->getOperand(1);
6781 SDValue BaseLoc = Base->getOperand(1);
6782 if (Loc.getOpcode() == ISD::FrameIndex) {
6783 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6785 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6786 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6787 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6788 int FS = MFI->getObjectSize(FI);
6789 int BFS = MFI->getObjectSize(BFI);
6790 if (FS != BFS || FS != (int)Bytes) return false;
6791 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6795 if (isBaseWithConstantOffset(Loc)) {
6796 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6797 if (Loc.getOperand(0) == BaseLoc) {
6798 // If the base location is a simple address with no offset itself, then
6799 // the second load's first add operand should be the base address.
6800 if (LocOffset == Dist * (int)Bytes)
6802 } else if (isBaseWithConstantOffset(BaseLoc)) {
6803 // The base location itself has an offset, so subtract that value from the
6804 // second load's offset before comparing to distance * size.
6806 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6807 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6808 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6813 const GlobalValue *GV1 = nullptr;
6814 const GlobalValue *GV2 = nullptr;
6815 int64_t Offset1 = 0;
6816 int64_t Offset2 = 0;
6817 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6818 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6819 if (isGA1 && isGA2 && GV1 == GV2)
6820 return Offset1 == (Offset2 + Dist*Bytes);
6825 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6826 /// it cannot be inferred.
6827 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6828 // If this is a GlobalAddress + cst, return the alignment.
6829 const GlobalValue *GV;
6830 int64_t GVOffset = 0;
6831 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6832 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6833 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6834 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6835 *TLI->getDataLayout());
6836 unsigned AlignBits = KnownZero.countTrailingOnes();
6837 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6839 return MinAlign(Align, GVOffset);
6842 // If this is a direct reference to a stack slot, use information about the
6843 // stack slot's alignment.
6844 int FrameIdx = 1 << 31;
6845 int64_t FrameOffset = 0;
6846 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6847 FrameIdx = FI->getIndex();
6848 } else if (isBaseWithConstantOffset(Ptr) &&
6849 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6851 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6852 FrameOffset = Ptr.getConstantOperandVal(1);
6855 if (FrameIdx != (1 << 31)) {
6856 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6857 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6865 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6866 /// which is split (or expanded) into two not necessarily identical pieces.
6867 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6868 // Currently all types are split in half.
6870 if (!VT.isVector()) {
6871 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6873 unsigned NumElements = VT.getVectorNumElements();
6874 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6875 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6878 return std::make_pair(LoVT, HiVT);
6881 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6883 std::pair<SDValue, SDValue>
6884 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6886 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6887 N.getValueType().getVectorNumElements() &&
6888 "More vector elements requested than available!");
6890 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6891 getConstant(0, DL, TLI->getVectorIdxTy()));
6892 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6893 getConstant(LoVT.getVectorNumElements(), DL,
6894 TLI->getVectorIdxTy()));
6895 return std::make_pair(Lo, Hi);
6898 void SelectionDAG::ExtractVectorElements(SDValue Op,
6899 SmallVectorImpl<SDValue> &Args,
6900 unsigned Start, unsigned Count) {
6901 EVT VT = Op.getValueType();
6903 Count = VT.getVectorNumElements();
6905 EVT EltVT = VT.getVectorElementType();
6906 EVT IdxTy = TLI->getVectorIdxTy();
6908 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6909 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6910 Op, getConstant(i, SL, IdxTy)));
6914 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6915 unsigned GlobalAddressSDNode::getAddressSpace() const {
6916 return getGlobal()->getType()->getAddressSpace();
6920 Type *ConstantPoolSDNode::getType() const {
6921 if (isMachineConstantPoolEntry())
6922 return Val.MachineCPVal->getType();
6923 return Val.ConstVal->getType();
6926 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6928 unsigned &SplatBitSize,
6930 unsigned MinSplatBits,
6931 bool isBigEndian) const {
6932 EVT VT = getValueType(0);
6933 assert(VT.isVector() && "Expected a vector type");
6934 unsigned sz = VT.getSizeInBits();
6935 if (MinSplatBits > sz)
6938 SplatValue = APInt(sz, 0);
6939 SplatUndef = APInt(sz, 0);
6941 // Get the bits. Bits with undefined values (when the corresponding element
6942 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6943 // in SplatValue. If any of the values are not constant, give up and return
6945 unsigned int nOps = getNumOperands();
6946 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6947 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6949 for (unsigned j = 0; j < nOps; ++j) {
6950 unsigned i = isBigEndian ? nOps-1-j : j;
6951 SDValue OpVal = getOperand(i);
6952 unsigned BitPos = j * EltBitSize;
6954 if (OpVal.getOpcode() == ISD::UNDEF)
6955 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6956 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6957 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6958 zextOrTrunc(sz) << BitPos;
6959 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6960 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6965 // The build_vector is all constants or undefs. Find the smallest element
6966 // size that splats the vector.
6968 HasAnyUndefs = (SplatUndef != 0);
6971 unsigned HalfSize = sz / 2;
6972 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6973 APInt LowValue = SplatValue.trunc(HalfSize);
6974 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6975 APInt LowUndef = SplatUndef.trunc(HalfSize);
6977 // If the two halves do not match (ignoring undef bits), stop here.
6978 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6979 MinSplatBits > HalfSize)
6982 SplatValue = HighValue | LowValue;
6983 SplatUndef = HighUndef & LowUndef;
6992 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6993 if (UndefElements) {
6994 UndefElements->clear();
6995 UndefElements->resize(getNumOperands());
6998 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6999 SDValue Op = getOperand(i);
7000 if (Op.getOpcode() == ISD::UNDEF) {
7002 (*UndefElements)[i] = true;
7003 } else if (!Splatted) {
7005 } else if (Splatted != Op) {
7011 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7012 "Can only have a splat without a constant for all undefs.");
7013 return getOperand(0);
7020 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7021 return dyn_cast_or_null<ConstantSDNode>(
7022 getSplatValue(UndefElements).getNode());
7026 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7027 return dyn_cast_or_null<ConstantFPSDNode>(
7028 getSplatValue(UndefElements).getNode());
7031 bool BuildVectorSDNode::isConstant() const {
7032 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7033 unsigned Opc = getOperand(i).getOpcode();
7034 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7040 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7041 // Find the first non-undef value in the shuffle mask.
7043 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7046 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7048 // Make sure all remaining elements are either undef or the same as the first
7050 for (int Idx = Mask[i]; i != e; ++i)
7051 if (Mask[i] >= 0 && Mask[i] != Idx)
7057 static void checkForCyclesHelper(const SDNode *N,
7058 SmallPtrSetImpl<const SDNode*> &Visited,
7059 SmallPtrSetImpl<const SDNode*> &Checked,
7060 const llvm::SelectionDAG *DAG) {
7061 // If this node has already been checked, don't check it again.
7062 if (Checked.count(N))
7065 // If a node has already been visited on this depth-first walk, reject it as
7067 if (!Visited.insert(N).second) {
7068 errs() << "Detected cycle in SelectionDAG\n";
7069 dbgs() << "Offending node:\n";
7070 N->dumprFull(DAG); dbgs() << "\n";
7074 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7075 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7082 void llvm::checkForCycles(const llvm::SDNode *N,
7083 const llvm::SelectionDAG *DAG,
7091 assert(N && "Checking nonexistent SDNode");
7092 SmallPtrSet<const SDNode*, 32> visited;
7093 SmallPtrSet<const SDNode*, 32> checked;
7094 checkForCyclesHelper(N, visited, checked, DAG);
7099 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7100 checkForCycles(DAG->getRoot().getNode(), DAG, force);