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(ID, N->getOpcode(),
519 BinNode->Flags.hasNoUnsignedWrap(),
520 BinNode->Flags.hasNoSignedWrap(),
521 BinNode->Flags.hasExact());
524 case ISD::ATOMIC_CMP_SWAP:
525 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
526 case ISD::ATOMIC_SWAP:
527 case ISD::ATOMIC_LOAD_ADD:
528 case ISD::ATOMIC_LOAD_SUB:
529 case ISD::ATOMIC_LOAD_AND:
530 case ISD::ATOMIC_LOAD_OR:
531 case ISD::ATOMIC_LOAD_XOR:
532 case ISD::ATOMIC_LOAD_NAND:
533 case ISD::ATOMIC_LOAD_MIN:
534 case ISD::ATOMIC_LOAD_MAX:
535 case ISD::ATOMIC_LOAD_UMIN:
536 case ISD::ATOMIC_LOAD_UMAX:
537 case ISD::ATOMIC_LOAD:
538 case ISD::ATOMIC_STORE: {
539 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
540 ID.AddInteger(AT->getMemoryVT().getRawBits());
541 ID.AddInteger(AT->getRawSubclassData());
542 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
545 case ISD::PREFETCH: {
546 const MemSDNode *PF = cast<MemSDNode>(N);
547 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
550 case ISD::VECTOR_SHUFFLE: {
551 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
552 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
554 ID.AddInteger(SVN->getMaskElt(i));
557 case ISD::TargetBlockAddress:
558 case ISD::BlockAddress: {
559 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
560 ID.AddPointer(BA->getBlockAddress());
561 ID.AddInteger(BA->getOffset());
562 ID.AddInteger(BA->getTargetFlags());
565 } // end switch (N->getOpcode())
567 // Target specific memory nodes could also have address spaces to check.
568 if (N->isTargetMemoryOpcode())
569 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
572 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
574 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
575 AddNodeIDOpcode(ID, N->getOpcode());
576 // Add the return value info.
577 AddNodeIDValueTypes(ID, N->getVTList());
578 // Add the operand info.
579 AddNodeIDOperands(ID, N->ops());
581 // Handle SDNode leafs with special info.
582 AddNodeIDCustom(ID, N);
585 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
586 /// the CSE map that carries volatility, temporalness, indexing mode, and
587 /// extension/truncation information.
589 static inline unsigned
590 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
591 bool isNonTemporal, bool isInvariant) {
592 assert((ConvType & 3) == ConvType &&
593 "ConvType may not require more than 2 bits!");
594 assert((AM & 7) == AM &&
595 "AM may not require more than 3 bits!");
599 (isNonTemporal << 6) |
603 //===----------------------------------------------------------------------===//
604 // SelectionDAG Class
605 //===----------------------------------------------------------------------===//
607 /// doNotCSE - Return true if CSE should not be performed for this node.
608 static bool doNotCSE(SDNode *N) {
609 if (N->getValueType(0) == MVT::Glue)
610 return true; // Never CSE anything that produces a flag.
612 switch (N->getOpcode()) {
614 case ISD::HANDLENODE:
616 return true; // Never CSE these nodes.
619 // Check that remaining values produced are not flags.
620 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
621 if (N->getValueType(i) == MVT::Glue)
622 return true; // Never CSE anything that produces a flag.
627 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
629 void SelectionDAG::RemoveDeadNodes() {
630 // Create a dummy node (which is not added to allnodes), that adds a reference
631 // to the root node, preventing it from being deleted.
632 HandleSDNode Dummy(getRoot());
634 SmallVector<SDNode*, 128> DeadNodes;
636 // Add all obviously-dead nodes to the DeadNodes worklist.
637 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
639 DeadNodes.push_back(I);
641 RemoveDeadNodes(DeadNodes);
643 // If the root changed (e.g. it was a dead load, update the root).
644 setRoot(Dummy.getValue());
647 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
648 /// given list, and any nodes that become unreachable as a result.
649 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
651 // Process the worklist, deleting the nodes and adding their uses to the
653 while (!DeadNodes.empty()) {
654 SDNode *N = DeadNodes.pop_back_val();
656 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
657 DUL->NodeDeleted(N, nullptr);
659 // Take the node out of the appropriate CSE map.
660 RemoveNodeFromCSEMaps(N);
662 // Next, brutally remove the operand list. This is safe to do, as there are
663 // no cycles in the graph.
664 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
666 SDNode *Operand = Use.getNode();
669 // Now that we removed this operand, see if there are no uses of it left.
670 if (Operand->use_empty())
671 DeadNodes.push_back(Operand);
678 void SelectionDAG::RemoveDeadNode(SDNode *N){
679 SmallVector<SDNode*, 16> DeadNodes(1, N);
681 // Create a dummy node that adds a reference to the root node, preventing
682 // it from being deleted. (This matters if the root is an operand of the
684 HandleSDNode Dummy(getRoot());
686 RemoveDeadNodes(DeadNodes);
689 void SelectionDAG::DeleteNode(SDNode *N) {
690 // First take this out of the appropriate CSE map.
691 RemoveNodeFromCSEMaps(N);
693 // Finally, remove uses due to operands of this node, remove from the
694 // AllNodes list, and delete the node.
695 DeleteNodeNotInCSEMaps(N);
698 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
699 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
700 assert(N->use_empty() && "Cannot delete a node that is not dead!");
702 // Drop all of the operands and decrement used node's use counts.
708 void SDDbgInfo::erase(const SDNode *Node) {
709 DbgValMapType::iterator I = DbgValMap.find(Node);
710 if (I == DbgValMap.end())
712 for (auto &Val: I->second)
713 Val->setIsInvalidated();
717 void SelectionDAG::DeallocateNode(SDNode *N) {
718 if (N->OperandsNeedDelete)
719 delete[] N->OperandList;
721 // Set the opcode to DELETED_NODE to help catch bugs when node
722 // memory is reallocated.
723 N->NodeType = ISD::DELETED_NODE;
725 NodeAllocator.Deallocate(AllNodes.remove(N));
727 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
728 // them and forget about that node.
733 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
734 static void VerifySDNode(SDNode *N) {
735 switch (N->getOpcode()) {
738 case ISD::BUILD_PAIR: {
739 EVT VT = N->getValueType(0);
740 assert(N->getNumValues() == 1 && "Too many results!");
741 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
742 "Wrong return type!");
743 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
744 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
745 "Mismatched operand types!");
746 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
747 "Wrong operand type!");
748 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
749 "Wrong return type size");
752 case ISD::BUILD_VECTOR: {
753 assert(N->getNumValues() == 1 && "Too many results!");
754 assert(N->getValueType(0).isVector() && "Wrong return type!");
755 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
756 "Wrong number of operands!");
757 EVT EltVT = N->getValueType(0).getVectorElementType();
758 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
759 assert((I->getValueType() == EltVT ||
760 (EltVT.isInteger() && I->getValueType().isInteger() &&
761 EltVT.bitsLE(I->getValueType()))) &&
762 "Wrong operand type!");
763 assert(I->getValueType() == N->getOperand(0).getValueType() &&
764 "Operands must all have the same type");
772 /// \brief Insert a newly allocated node into the DAG.
774 /// Handles insertion into the all nodes list and CSE map, as well as
775 /// verification and other common operations when a new node is allocated.
776 void SelectionDAG::InsertNode(SDNode *N) {
777 AllNodes.push_back(N);
783 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
784 /// correspond to it. This is useful when we're about to delete or repurpose
785 /// the node. We don't want future request for structurally identical nodes
786 /// to return N anymore.
787 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
789 switch (N->getOpcode()) {
790 case ISD::HANDLENODE: return false; // noop.
792 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
793 "Cond code doesn't exist!");
794 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
795 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
797 case ISD::ExternalSymbol:
798 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
800 case ISD::TargetExternalSymbol: {
801 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
802 Erased = TargetExternalSymbols.erase(
803 std::pair<std::string,unsigned char>(ESN->getSymbol(),
804 ESN->getTargetFlags()));
807 case ISD::VALUETYPE: {
808 EVT VT = cast<VTSDNode>(N)->getVT();
809 if (VT.isExtended()) {
810 Erased = ExtendedValueTypeNodes.erase(VT);
812 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
813 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
818 // Remove it from the CSE Map.
819 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
820 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
821 Erased = CSEMap.RemoveNode(N);
825 // Verify that the node was actually in one of the CSE maps, unless it has a
826 // flag result (which cannot be CSE'd) or is one of the special cases that are
827 // not subject to CSE.
828 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
829 !N->isMachineOpcode() && !doNotCSE(N)) {
832 llvm_unreachable("Node is not in map!");
838 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
839 /// maps and modified in place. Add it back to the CSE maps, unless an identical
840 /// node already exists, in which case transfer all its users to the existing
841 /// node. This transfer can potentially trigger recursive merging.
844 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
845 // For node types that aren't CSE'd, just act as if no identical node
848 SDNode *Existing = CSEMap.GetOrInsertNode(N);
850 // If there was already an existing matching node, use ReplaceAllUsesWith
851 // to replace the dead one with the existing one. This can cause
852 // recursive merging of other unrelated nodes down the line.
853 ReplaceAllUsesWith(N, Existing);
855 // N is now dead. Inform the listeners and delete it.
856 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
857 DUL->NodeDeleted(N, Existing);
858 DeleteNodeNotInCSEMaps(N);
863 // If the node doesn't already exist, we updated it. Inform listeners.
864 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
868 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
869 /// were replaced with those specified. If this node is never memoized,
870 /// return null, otherwise return a pointer to the slot it would take. If a
871 /// node already exists with these operands, the slot will be non-null.
872 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
877 SDValue Ops[] = { Op };
879 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
880 AddNodeIDCustom(ID, N);
881 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
885 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
886 /// were replaced with those specified. If this node is never memoized,
887 /// return null, otherwise return a pointer to the slot it would take. If a
888 /// node already exists with these operands, the slot will be non-null.
889 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
890 SDValue Op1, SDValue Op2,
895 SDValue Ops[] = { Op1, Op2 };
897 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
898 AddNodeIDCustom(ID, N);
899 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
904 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
905 /// were replaced with those specified. If this node is never memoized,
906 /// return null, otherwise return a pointer to the slot it would take. If a
907 /// node already exists with these operands, the slot will be non-null.
908 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
914 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
915 AddNodeIDCustom(ID, N);
916 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
920 /// getEVTAlignment - Compute the default alignment value for the
923 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
924 Type *Ty = VT == MVT::iPTR ?
925 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
926 VT.getTypeForEVT(*getContext());
928 return TLI->getDataLayout()->getABITypeAlignment(Ty);
931 // EntryNode could meaningfully have debug info if we can find it...
932 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
933 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
934 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
935 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
936 UpdateListeners(nullptr) {
937 AllNodes.push_back(&EntryNode);
938 DbgInfo = new SDDbgInfo();
941 void SelectionDAG::init(MachineFunction &mf) {
943 TLI = getSubtarget().getTargetLowering();
944 TSI = getSubtarget().getSelectionDAGInfo();
945 Context = &mf.getFunction()->getContext();
948 SelectionDAG::~SelectionDAG() {
949 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
954 void SelectionDAG::allnodes_clear() {
955 assert(&*AllNodes.begin() == &EntryNode);
956 AllNodes.remove(AllNodes.begin());
957 while (!AllNodes.empty())
958 DeallocateNode(AllNodes.begin());
961 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
962 SDVTList VTs, SDValue N1,
963 SDValue N2, bool nuw, bool nsw,
965 if (isBinOpWithFlags(Opcode)) {
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
968 FN->Flags.setNoUnsignedWrap(nuw);
969 FN->Flags.setNoSignedWrap(nsw);
970 FN->Flags.setExact(exact);
975 BinarySDNode *N = new (NodeAllocator)
976 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
980 void SelectionDAG::clear() {
982 OperandAllocator.Reset();
985 ExtendedValueTypeNodes.clear();
986 ExternalSymbols.clear();
987 TargetExternalSymbols.clear();
988 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
989 static_cast<CondCodeSDNode*>(nullptr));
990 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
991 static_cast<SDNode*>(nullptr));
993 EntryNode.UseList = nullptr;
994 AllNodes.push_back(&EntryNode);
995 Root = getEntryNode();
999 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1000 return VT.bitsGT(Op.getValueType()) ?
1001 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1002 getNode(ISD::TRUNCATE, DL, VT, Op);
1005 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1006 return VT.bitsGT(Op.getValueType()) ?
1007 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1008 getNode(ISD::TRUNCATE, DL, VT, Op);
1011 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1012 return VT.bitsGT(Op.getValueType()) ?
1013 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1014 getNode(ISD::TRUNCATE, DL, VT, Op);
1017 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1019 if (VT.bitsLE(Op.getValueType()))
1020 return getNode(ISD::TRUNCATE, SL, VT, Op);
1022 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1023 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1026 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1027 assert(!VT.isVector() &&
1028 "getZeroExtendInReg should use the vector element type instead of "
1029 "the vector type!");
1030 if (Op.getValueType() == VT) return Op;
1031 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1032 APInt Imm = APInt::getLowBitsSet(BitWidth,
1033 VT.getSizeInBits());
1034 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1035 getConstant(Imm, DL, Op.getValueType()));
1038 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1039 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1040 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1041 "The sizes of the input and result must match in order to perform the "
1042 "extend in-register.");
1043 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1044 "The destination vector type must have fewer lanes than the input.");
1045 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1048 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1049 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1050 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1051 "The sizes of the input and result must match in order to perform the "
1052 "extend in-register.");
1053 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1054 "The destination vector type must have fewer lanes than the input.");
1055 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1058 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1059 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1060 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1061 "The sizes of the input and result must match in order to perform the "
1062 "extend in-register.");
1063 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1064 "The destination vector type must have fewer lanes than the input.");
1065 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1068 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1070 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1071 EVT EltVT = VT.getScalarType();
1073 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1074 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1077 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1078 EVT EltVT = VT.getScalarType();
1080 switch (TLI->getBooleanContents(VT)) {
1081 case TargetLowering::ZeroOrOneBooleanContent:
1082 case TargetLowering::UndefinedBooleanContent:
1083 TrueValue = getConstant(1, DL, VT);
1085 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1086 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1090 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1093 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1095 EVT EltVT = VT.getScalarType();
1096 assert((EltVT.getSizeInBits() >= 64 ||
1097 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1098 "getConstant with a uint64_t value that doesn't fit in the type!");
1099 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1102 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1105 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1108 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1109 bool isT, bool isO) {
1110 assert(VT.isInteger() && "Cannot create FP integer constant!");
1112 EVT EltVT = VT.getScalarType();
1113 const ConstantInt *Elt = &Val;
1115 // In some cases the vector type is legal but the element type is illegal and
1116 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1117 // inserted value (the type does not need to match the vector element type).
1118 // Any extra bits introduced will be truncated away.
1119 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1120 TargetLowering::TypePromoteInteger) {
1121 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1122 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1123 Elt = ConstantInt::get(*getContext(), NewVal);
1125 // In other cases the element type is illegal and needs to be expanded, for
1126 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1127 // the value into n parts and use a vector type with n-times the elements.
1128 // Then bitcast to the type requested.
1129 // Legalizing constants too early makes the DAGCombiner's job harder so we
1130 // only legalize if the DAG tells us we must produce legal types.
1131 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1132 TLI->getTypeAction(*getContext(), EltVT) ==
1133 TargetLowering::TypeExpandInteger) {
1134 APInt NewVal = Elt->getValue();
1135 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1136 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1137 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1138 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1140 // Check the temporary vector is the correct size. If this fails then
1141 // getTypeToTransformTo() probably returned a type whose size (in bits)
1142 // isn't a power-of-2 factor of the requested type size.
1143 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1145 SmallVector<SDValue, 2> EltParts;
1146 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1147 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1148 .trunc(ViaEltSizeInBits), DL,
1149 ViaEltVT, isT, isO));
1152 // EltParts is currently in little endian order. If we actually want
1153 // big-endian order then reverse it now.
1154 if (TLI->isBigEndian())
1155 std::reverse(EltParts.begin(), EltParts.end());
1157 // The elements must be reversed when the element order is different
1158 // to the endianness of the elements (because the BITCAST is itself a
1159 // vector shuffle in this situation). However, we do not need any code to
1160 // perform this reversal because getConstant() is producing a vector
1162 // This situation occurs in MIPS MSA.
1164 SmallVector<SDValue, 8> Ops;
1165 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1166 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1168 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1169 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1174 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1175 "APInt size does not match type size!");
1176 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1177 FoldingSetNodeID ID;
1178 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1182 SDNode *N = nullptr;
1183 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1185 return SDValue(N, 0);
1188 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1190 CSEMap.InsertNode(N, IP);
1194 SDValue Result(N, 0);
1195 if (VT.isVector()) {
1196 SmallVector<SDValue, 8> Ops;
1197 Ops.assign(VT.getVectorNumElements(), Result);
1198 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1203 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1204 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1207 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1209 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1212 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1214 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1216 EVT EltVT = VT.getScalarType();
1218 // Do the map lookup using the actual bit pattern for the floating point
1219 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1220 // we don't have issues with SNANs.
1221 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1222 FoldingSetNodeID ID;
1223 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1226 SDNode *N = nullptr;
1227 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1229 return SDValue(N, 0);
1232 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1233 CSEMap.InsertNode(N, IP);
1237 SDValue Result(N, 0);
1238 if (VT.isVector()) {
1239 SmallVector<SDValue, 8> Ops;
1240 Ops.assign(VT.getVectorNumElements(), Result);
1241 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1246 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1248 EVT EltVT = VT.getScalarType();
1249 if (EltVT==MVT::f32)
1250 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1251 else if (EltVT==MVT::f64)
1252 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1253 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1256 APFloat apf = APFloat(Val);
1257 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1259 return getConstantFP(apf, DL, VT, isTarget);
1261 llvm_unreachable("Unsupported type in getConstantFP");
1264 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1265 EVT VT, int64_t Offset,
1267 unsigned char TargetFlags) {
1268 assert((TargetFlags == 0 || isTargetGA) &&
1269 "Cannot set target flags on target-independent globals");
1271 // Truncate (with sign-extension) the offset value to the pointer size.
1272 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1274 Offset = SignExtend64(Offset, BitWidth);
1277 if (GV->isThreadLocal())
1278 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1280 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1282 FoldingSetNodeID ID;
1283 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1285 ID.AddInteger(Offset);
1286 ID.AddInteger(TargetFlags);
1287 ID.AddInteger(GV->getType()->getAddressSpace());
1289 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1290 return SDValue(E, 0);
1292 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1293 DL.getDebugLoc(), GV, VT,
1294 Offset, TargetFlags);
1295 CSEMap.InsertNode(N, IP);
1297 return SDValue(N, 0);
1300 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1301 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1302 FoldingSetNodeID ID;
1303 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1306 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1307 return SDValue(E, 0);
1309 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1310 CSEMap.InsertNode(N, IP);
1312 return SDValue(N, 0);
1315 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1316 unsigned char TargetFlags) {
1317 assert((TargetFlags == 0 || isTarget) &&
1318 "Cannot set target flags on target-independent jump tables");
1319 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1320 FoldingSetNodeID ID;
1321 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1323 ID.AddInteger(TargetFlags);
1325 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1326 return SDValue(E, 0);
1328 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1330 CSEMap.InsertNode(N, IP);
1332 return SDValue(N, 0);
1335 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1336 unsigned Alignment, int Offset,
1338 unsigned char TargetFlags) {
1339 assert((TargetFlags == 0 || isTarget) &&
1340 "Cannot set target flags on target-independent globals");
1342 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1343 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1344 FoldingSetNodeID ID;
1345 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1346 ID.AddInteger(Alignment);
1347 ID.AddInteger(Offset);
1349 ID.AddInteger(TargetFlags);
1351 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1352 return SDValue(E, 0);
1354 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1355 Alignment, TargetFlags);
1356 CSEMap.InsertNode(N, IP);
1358 return SDValue(N, 0);
1362 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1363 unsigned Alignment, int Offset,
1365 unsigned char TargetFlags) {
1366 assert((TargetFlags == 0 || isTarget) &&
1367 "Cannot set target flags on target-independent globals");
1369 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1370 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1371 FoldingSetNodeID ID;
1372 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1373 ID.AddInteger(Alignment);
1374 ID.AddInteger(Offset);
1375 C->addSelectionDAGCSEId(ID);
1376 ID.AddInteger(TargetFlags);
1378 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1379 return SDValue(E, 0);
1381 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1382 Alignment, TargetFlags);
1383 CSEMap.InsertNode(N, IP);
1385 return SDValue(N, 0);
1388 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1389 unsigned char TargetFlags) {
1390 FoldingSetNodeID ID;
1391 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1392 ID.AddInteger(Index);
1393 ID.AddInteger(Offset);
1394 ID.AddInteger(TargetFlags);
1396 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1397 return SDValue(E, 0);
1399 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1401 CSEMap.InsertNode(N, IP);
1403 return SDValue(N, 0);
1406 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1407 FoldingSetNodeID ID;
1408 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1411 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1412 return SDValue(E, 0);
1414 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1415 CSEMap.InsertNode(N, IP);
1417 return SDValue(N, 0);
1420 SDValue SelectionDAG::getValueType(EVT VT) {
1421 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1422 ValueTypeNodes.size())
1423 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1425 SDNode *&N = VT.isExtended() ?
1426 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1428 if (N) return SDValue(N, 0);
1429 N = new (NodeAllocator) VTSDNode(VT);
1431 return SDValue(N, 0);
1434 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1435 SDNode *&N = ExternalSymbols[Sym];
1436 if (N) return SDValue(N, 0);
1437 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1439 return SDValue(N, 0);
1442 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1443 unsigned char TargetFlags) {
1445 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1447 if (N) return SDValue(N, 0);
1448 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1450 return SDValue(N, 0);
1453 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1454 if ((unsigned)Cond >= CondCodeNodes.size())
1455 CondCodeNodes.resize(Cond+1);
1457 if (!CondCodeNodes[Cond]) {
1458 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1459 CondCodeNodes[Cond] = N;
1463 return SDValue(CondCodeNodes[Cond], 0);
1466 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1467 // the shuffle mask M that point at N1 to point at N2, and indices that point
1468 // N2 to point at N1.
1469 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1471 ShuffleVectorSDNode::commuteMask(M);
1474 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1475 SDValue N2, const int *Mask) {
1476 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1477 "Invalid VECTOR_SHUFFLE");
1479 // Canonicalize shuffle undef, undef -> undef
1480 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1481 return getUNDEF(VT);
1483 // Validate that all indices in Mask are within the range of the elements
1484 // input to the shuffle.
1485 unsigned NElts = VT.getVectorNumElements();
1486 SmallVector<int, 8> MaskVec;
1487 for (unsigned i = 0; i != NElts; ++i) {
1488 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1489 MaskVec.push_back(Mask[i]);
1492 // Canonicalize shuffle v, v -> v, undef
1495 for (unsigned i = 0; i != NElts; ++i)
1496 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1499 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1500 if (N1.getOpcode() == ISD::UNDEF)
1501 commuteShuffle(N1, N2, MaskVec);
1503 // If shuffling a splat, try to blend the splat instead. We do this here so
1504 // that even when this arises during lowering we don't have to re-handle it.
1505 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1506 BitVector UndefElements;
1507 SDValue Splat = BV->getSplatValue(&UndefElements);
1511 for (int i = 0; i < (int)NElts; ++i) {
1512 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1515 // If this input comes from undef, mark it as such.
1516 if (UndefElements[MaskVec[i] - Offset]) {
1521 // If we can blend a non-undef lane, use that instead.
1522 if (!UndefElements[i])
1523 MaskVec[i] = i + Offset;
1526 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1527 BlendSplat(N1BV, 0);
1528 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1529 BlendSplat(N2BV, NElts);
1531 // Canonicalize all index into lhs, -> shuffle lhs, undef
1532 // Canonicalize all index into rhs, -> shuffle rhs, undef
1533 bool AllLHS = true, AllRHS = true;
1534 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1535 for (unsigned i = 0; i != NElts; ++i) {
1536 if (MaskVec[i] >= (int)NElts) {
1541 } else if (MaskVec[i] >= 0) {
1545 if (AllLHS && AllRHS)
1546 return getUNDEF(VT);
1547 if (AllLHS && !N2Undef)
1551 commuteShuffle(N1, N2, MaskVec);
1553 // Reset our undef status after accounting for the mask.
1554 N2Undef = N2.getOpcode() == ISD::UNDEF;
1555 // Re-check whether both sides ended up undef.
1556 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1557 return getUNDEF(VT);
1559 // If Identity shuffle return that node.
1560 bool Identity = true, AllSame = true;
1561 for (unsigned i = 0; i != NElts; ++i) {
1562 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1563 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1565 if (Identity && NElts)
1568 // Shuffling a constant splat doesn't change the result.
1572 // Look through any bitcasts. We check that these don't change the number
1573 // (and size) of elements and just changes their types.
1574 while (V.getOpcode() == ISD::BITCAST)
1575 V = V->getOperand(0);
1577 // A splat should always show up as a build vector node.
1578 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1579 BitVector UndefElements;
1580 SDValue Splat = BV->getSplatValue(&UndefElements);
1581 // If this is a splat of an undef, shuffling it is also undef.
1582 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1583 return getUNDEF(VT);
1586 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1588 // We only have a splat which can skip shuffles if there is a splatted
1589 // value and no undef lanes rearranged by the shuffle.
1590 if (Splat && UndefElements.none()) {
1591 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1592 // number of elements match or the value splatted is a zero constant.
1595 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1596 if (C->isNullValue())
1600 // If the shuffle itself creates a splat, build the vector directly.
1601 if (AllSame && SameNumElts) {
1602 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1603 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1605 EVT BuildVT = BV->getValueType(0);
1606 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1608 // We may have jumped through bitcasts, so the type of the
1609 // BUILD_VECTOR may not match the type of the shuffle.
1611 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1617 FoldingSetNodeID ID;
1618 SDValue Ops[2] = { N1, N2 };
1619 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1620 for (unsigned i = 0; i != NElts; ++i)
1621 ID.AddInteger(MaskVec[i]);
1624 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1625 return SDValue(E, 0);
1627 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1628 // SDNode doesn't have access to it. This memory will be "leaked" when
1629 // the node is deallocated, but recovered when the NodeAllocator is released.
1630 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1631 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1633 ShuffleVectorSDNode *N =
1634 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1635 dl.getDebugLoc(), N1, N2,
1637 CSEMap.InsertNode(N, IP);
1639 return SDValue(N, 0);
1642 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1643 MVT VT = SV.getSimpleValueType(0);
1644 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1645 ShuffleVectorSDNode::commuteMask(MaskVec);
1647 SDValue Op0 = SV.getOperand(0);
1648 SDValue Op1 = SV.getOperand(1);
1649 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1652 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1653 SDValue Val, SDValue DTy,
1654 SDValue STy, SDValue Rnd, SDValue Sat,
1655 ISD::CvtCode Code) {
1656 // If the src and dest types are the same and the conversion is between
1657 // integer types of the same sign or two floats, no conversion is necessary.
1659 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1662 FoldingSetNodeID ID;
1663 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1664 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1667 return SDValue(E, 0);
1669 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1672 CSEMap.InsertNode(N, IP);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1678 FoldingSetNodeID ID;
1679 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1680 ID.AddInteger(RegNo);
1682 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1683 return SDValue(E, 0);
1685 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1686 CSEMap.InsertNode(N, IP);
1688 return SDValue(N, 0);
1691 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1692 FoldingSetNodeID ID;
1693 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1694 ID.AddPointer(RegMask);
1696 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1697 return SDValue(E, 0);
1699 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1700 CSEMap.InsertNode(N, IP);
1702 return SDValue(N, 0);
1705 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1706 FoldingSetNodeID ID;
1707 SDValue Ops[] = { Root };
1708 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1709 ID.AddPointer(Label);
1711 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1712 return SDValue(E, 0);
1714 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1715 dl.getDebugLoc(), Root, Label);
1716 CSEMap.InsertNode(N, IP);
1718 return SDValue(N, 0);
1722 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1725 unsigned char TargetFlags) {
1726 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1728 FoldingSetNodeID ID;
1729 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1731 ID.AddInteger(Offset);
1732 ID.AddInteger(TargetFlags);
1734 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1735 return SDValue(E, 0);
1737 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1739 CSEMap.InsertNode(N, IP);
1741 return SDValue(N, 0);
1744 SDValue SelectionDAG::getSrcValue(const Value *V) {
1745 assert((!V || V->getType()->isPointerTy()) &&
1746 "SrcValue is not a pointer?");
1748 FoldingSetNodeID ID;
1749 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1753 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1754 return SDValue(E, 0);
1756 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1757 CSEMap.InsertNode(N, IP);
1759 return SDValue(N, 0);
1762 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1763 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1764 FoldingSetNodeID ID;
1765 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1769 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1770 return SDValue(E, 0);
1772 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1773 CSEMap.InsertNode(N, IP);
1775 return SDValue(N, 0);
1778 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1779 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1780 unsigned SrcAS, unsigned DestAS) {
1781 SDValue Ops[] = {Ptr};
1782 FoldingSetNodeID ID;
1783 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1784 ID.AddInteger(SrcAS);
1785 ID.AddInteger(DestAS);
1788 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1789 return SDValue(E, 0);
1791 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1793 VT, Ptr, SrcAS, DestAS);
1794 CSEMap.InsertNode(N, IP);
1796 return SDValue(N, 0);
1799 /// getShiftAmountOperand - Return the specified value casted to
1800 /// the target's desired shift amount type.
1801 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1802 EVT OpTy = Op.getValueType();
1803 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1804 if (OpTy == ShTy || OpTy.isVector()) return Op;
1806 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1807 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1810 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1811 /// specified value type.
1812 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1813 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1814 unsigned ByteSize = VT.getStoreSize();
1815 Type *Ty = VT.getTypeForEVT(*getContext());
1816 unsigned StackAlign =
1817 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1819 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1820 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1823 /// CreateStackTemporary - Create a stack temporary suitable for holding
1824 /// either of the specified value types.
1825 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1826 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1827 VT2.getStoreSizeInBits())/8;
1828 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1829 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1830 const DataLayout *TD = TLI->getDataLayout();
1831 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1832 TD->getPrefTypeAlignment(Ty2));
1834 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1835 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1836 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1839 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1840 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1841 // These setcc operations always fold.
1845 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1847 case ISD::SETTRUE2: {
1848 TargetLowering::BooleanContent Cnt =
1849 TLI->getBooleanContents(N1->getValueType(0));
1851 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1865 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1869 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1870 const APInt &C2 = N2C->getAPIntValue();
1871 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1872 const APInt &C1 = N1C->getAPIntValue();
1875 default: llvm_unreachable("Unknown integer setcc!");
1876 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1877 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1878 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1879 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1880 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1881 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1882 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1883 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1884 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1885 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1889 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1890 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1891 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1894 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1895 return getUNDEF(VT);
1897 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1898 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1899 return getUNDEF(VT);
1901 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1902 R==APFloat::cmpLessThan, dl, VT);
1903 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1904 return getUNDEF(VT);
1906 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1907 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1908 return getUNDEF(VT);
1910 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1911 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1912 return getUNDEF(VT);
1914 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1915 R==APFloat::cmpEqual, dl, VT);
1916 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1917 return getUNDEF(VT);
1919 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1920 R==APFloat::cmpEqual, dl, VT);
1921 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1922 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1923 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1924 R==APFloat::cmpEqual, dl, VT);
1925 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1926 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1927 R==APFloat::cmpLessThan, dl, VT);
1928 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1929 R==APFloat::cmpUnordered, dl, VT);
1930 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1931 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1934 // Ensure that the constant occurs on the RHS.
1935 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1936 MVT CompVT = N1.getValueType().getSimpleVT();
1937 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1940 return getSetCC(dl, VT, N2, N1, SwappedCond);
1944 // Could not fold it.
1948 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1949 /// use this predicate to simplify operations downstream.
1950 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1951 // This predicate is not safe for vector operations.
1952 if (Op.getValueType().isVector())
1955 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1956 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1959 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1960 /// this predicate to simplify operations downstream. Mask is known to be zero
1961 /// for bits that V cannot have.
1962 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1963 unsigned Depth) const {
1964 APInt KnownZero, KnownOne;
1965 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1966 return (KnownZero & Mask) == Mask;
1969 /// Determine which bits of Op are known to be either zero or one and return
1970 /// them in the KnownZero/KnownOne bitsets.
1971 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1972 APInt &KnownOne, unsigned Depth) const {
1973 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1975 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1977 return; // Limit search depth.
1979 APInt KnownZero2, KnownOne2;
1981 switch (Op.getOpcode()) {
1983 // We know all of the bits for a constant!
1984 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1985 KnownZero = ~KnownOne;
1988 // If either the LHS or the RHS are Zero, the result is zero.
1989 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1990 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1992 // Output known-1 bits are only known if set in both the LHS & RHS.
1993 KnownOne &= KnownOne2;
1994 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1995 KnownZero |= KnownZero2;
1998 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1999 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2001 // Output known-0 bits are only known if clear in both the LHS & RHS.
2002 KnownZero &= KnownZero2;
2003 // Output known-1 are known to be set if set in either the LHS | RHS.
2004 KnownOne |= KnownOne2;
2007 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2008 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2010 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2011 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2012 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2013 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2014 KnownZero = KnownZeroOut;
2018 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2019 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2021 // If low bits are zero in either operand, output low known-0 bits.
2022 // Also compute a conserative estimate for high known-0 bits.
2023 // More trickiness is possible, but this is sufficient for the
2024 // interesting case of alignment computation.
2025 KnownOne.clearAllBits();
2026 unsigned TrailZ = KnownZero.countTrailingOnes() +
2027 KnownZero2.countTrailingOnes();
2028 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2029 KnownZero2.countLeadingOnes(),
2030 BitWidth) - BitWidth;
2032 TrailZ = std::min(TrailZ, BitWidth);
2033 LeadZ = std::min(LeadZ, BitWidth);
2034 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2035 APInt::getHighBitsSet(BitWidth, LeadZ);
2039 // For the purposes of computing leading zeros we can conservatively
2040 // treat a udiv as a logical right shift by the power of 2 known to
2041 // be less than the denominator.
2042 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2043 unsigned LeadZ = KnownZero2.countLeadingOnes();
2045 KnownOne2.clearAllBits();
2046 KnownZero2.clearAllBits();
2047 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2048 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2049 if (RHSUnknownLeadingOnes != BitWidth)
2050 LeadZ = std::min(BitWidth,
2051 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2053 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2057 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2058 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2060 // Only known if known in both the LHS and RHS.
2061 KnownOne &= KnownOne2;
2062 KnownZero &= KnownZero2;
2064 case ISD::SELECT_CC:
2065 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2066 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2068 // Only known if known in both the LHS and RHS.
2069 KnownOne &= KnownOne2;
2070 KnownZero &= KnownZero2;
2078 if (Op.getResNo() != 1)
2080 // The boolean result conforms to getBooleanContents.
2081 // If we know the result of a setcc has the top bits zero, use this info.
2082 // We know that we have an integer-based boolean since these operations
2083 // are only available for integer.
2084 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2085 TargetLowering::ZeroOrOneBooleanContent &&
2087 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2090 // If we know the result of a setcc has the top bits zero, use this info.
2091 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2092 TargetLowering::ZeroOrOneBooleanContent &&
2094 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2097 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2098 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2099 unsigned ShAmt = SA->getZExtValue();
2101 // If the shift count is an invalid immediate, don't do anything.
2102 if (ShAmt >= BitWidth)
2105 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2106 KnownZero <<= ShAmt;
2108 // low bits known zero.
2109 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2113 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2114 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2115 unsigned ShAmt = SA->getZExtValue();
2117 // If the shift count is an invalid immediate, don't do anything.
2118 if (ShAmt >= BitWidth)
2121 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2122 KnownZero = KnownZero.lshr(ShAmt);
2123 KnownOne = KnownOne.lshr(ShAmt);
2125 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2126 KnownZero |= HighBits; // High bits known zero.
2130 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2131 unsigned ShAmt = SA->getZExtValue();
2133 // If the shift count is an invalid immediate, don't do anything.
2134 if (ShAmt >= BitWidth)
2137 // If any of the demanded bits are produced by the sign extension, we also
2138 // demand the input sign bit.
2139 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2141 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2142 KnownZero = KnownZero.lshr(ShAmt);
2143 KnownOne = KnownOne.lshr(ShAmt);
2145 // Handle the sign bits.
2146 APInt SignBit = APInt::getSignBit(BitWidth);
2147 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2149 if (KnownZero.intersects(SignBit)) {
2150 KnownZero |= HighBits; // New bits are known zero.
2151 } else if (KnownOne.intersects(SignBit)) {
2152 KnownOne |= HighBits; // New bits are known one.
2156 case ISD::SIGN_EXTEND_INREG: {
2157 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2158 unsigned EBits = EVT.getScalarType().getSizeInBits();
2160 // Sign extension. Compute the demanded bits in the result that are not
2161 // present in the input.
2162 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2164 APInt InSignBit = APInt::getSignBit(EBits);
2165 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2167 // If the sign extended bits are demanded, we know that the sign
2169 InSignBit = InSignBit.zext(BitWidth);
2170 if (NewBits.getBoolValue())
2171 InputDemandedBits |= InSignBit;
2173 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2174 KnownOne &= InputDemandedBits;
2175 KnownZero &= InputDemandedBits;
2177 // If the sign bit of the input is known set or clear, then we know the
2178 // top bits of the result.
2179 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2180 KnownZero |= NewBits;
2181 KnownOne &= ~NewBits;
2182 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2183 KnownOne |= NewBits;
2184 KnownZero &= ~NewBits;
2185 } else { // Input sign bit unknown
2186 KnownZero &= ~NewBits;
2187 KnownOne &= ~NewBits;
2192 case ISD::CTTZ_ZERO_UNDEF:
2194 case ISD::CTLZ_ZERO_UNDEF:
2196 unsigned LowBits = Log2_32(BitWidth)+1;
2197 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2198 KnownOne.clearAllBits();
2202 LoadSDNode *LD = cast<LoadSDNode>(Op);
2203 // If this is a ZEXTLoad and we are looking at the loaded value.
2204 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2205 EVT VT = LD->getMemoryVT();
2206 unsigned MemBits = VT.getScalarType().getSizeInBits();
2207 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2208 } else if (const MDNode *Ranges = LD->getRanges()) {
2209 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2213 case ISD::ZERO_EXTEND: {
2214 EVT InVT = Op.getOperand(0).getValueType();
2215 unsigned InBits = InVT.getScalarType().getSizeInBits();
2216 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2217 KnownZero = KnownZero.trunc(InBits);
2218 KnownOne = KnownOne.trunc(InBits);
2219 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2220 KnownZero = KnownZero.zext(BitWidth);
2221 KnownOne = KnownOne.zext(BitWidth);
2222 KnownZero |= NewBits;
2225 case ISD::SIGN_EXTEND: {
2226 EVT InVT = Op.getOperand(0).getValueType();
2227 unsigned InBits = InVT.getScalarType().getSizeInBits();
2228 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2230 KnownZero = KnownZero.trunc(InBits);
2231 KnownOne = KnownOne.trunc(InBits);
2232 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2234 // Note if the sign bit is known to be zero or one.
2235 bool SignBitKnownZero = KnownZero.isNegative();
2236 bool SignBitKnownOne = KnownOne.isNegative();
2238 KnownZero = KnownZero.zext(BitWidth);
2239 KnownOne = KnownOne.zext(BitWidth);
2241 // If the sign bit is known zero or one, the top bits match.
2242 if (SignBitKnownZero)
2243 KnownZero |= NewBits;
2244 else if (SignBitKnownOne)
2245 KnownOne |= NewBits;
2248 case ISD::ANY_EXTEND: {
2249 EVT InVT = Op.getOperand(0).getValueType();
2250 unsigned InBits = InVT.getScalarType().getSizeInBits();
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);
2258 case ISD::TRUNCATE: {
2259 EVT InVT = Op.getOperand(0).getValueType();
2260 unsigned InBits = InVT.getScalarType().getSizeInBits();
2261 KnownZero = KnownZero.zext(InBits);
2262 KnownOne = KnownOne.zext(InBits);
2263 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2264 KnownZero = KnownZero.trunc(BitWidth);
2265 KnownOne = KnownOne.trunc(BitWidth);
2268 case ISD::AssertZext: {
2269 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2270 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2271 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2272 KnownZero |= (~InMask);
2273 KnownOne &= (~KnownZero);
2277 // All bits are zero except the low bit.
2278 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2282 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2283 // We know that the top bits of C-X are clear if X contains less bits
2284 // than C (i.e. no wrap-around can happen). For example, 20-X is
2285 // positive if we can prove that X is >= 0 and < 16.
2286 if (CLHS->getAPIntValue().isNonNegative()) {
2287 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2288 // NLZ can't be BitWidth with no sign bit
2289 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2290 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2292 // If all of the MaskV bits are known to be zero, then we know the
2293 // output top bits are zero, because we now know that the output is
2295 if ((KnownZero2 & MaskV) == MaskV) {
2296 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2297 // Top bits known zero.
2298 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2306 // Output known-0 bits are known if clear or set in both the low clear bits
2307 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2308 // low 3 bits clear.
2309 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2310 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2312 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2313 KnownZeroOut = std::min(KnownZeroOut,
2314 KnownZero2.countTrailingOnes());
2316 if (Op.getOpcode() == ISD::ADD) {
2317 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2321 // With ADDE, a carry bit may be added in, so we can only use this
2322 // information if we know (at least) that the low two bits are clear. We
2323 // then return to the caller that the low bit is unknown but that other bits
2325 if (KnownZeroOut >= 2) // ADDE
2326 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2330 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2331 const APInt &RA = Rem->getAPIntValue().abs();
2332 if (RA.isPowerOf2()) {
2333 APInt LowBits = RA - 1;
2334 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2336 // The low bits of the first operand are unchanged by the srem.
2337 KnownZero = KnownZero2 & LowBits;
2338 KnownOne = KnownOne2 & LowBits;
2340 // If the first operand is non-negative or has all low bits zero, then
2341 // the upper bits are all zero.
2342 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2343 KnownZero |= ~LowBits;
2345 // If the first operand is negative and not all low bits are zero, then
2346 // the upper bits are all one.
2347 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2348 KnownOne |= ~LowBits;
2349 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2354 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2355 const APInt &RA = Rem->getAPIntValue();
2356 if (RA.isPowerOf2()) {
2357 APInt LowBits = (RA - 1);
2358 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2360 // The upper bits are all zero, the lower ones are unchanged.
2361 KnownZero = KnownZero2 | ~LowBits;
2362 KnownOne = KnownOne2 & LowBits;
2367 // Since the result is less than or equal to either operand, any leading
2368 // zero bits in either operand must also exist in the result.
2369 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2370 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2372 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2373 KnownZero2.countLeadingOnes());
2374 KnownOne.clearAllBits();
2375 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2378 case ISD::EXTRACT_ELEMENT: {
2379 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2380 const unsigned Index =
2381 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2382 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2384 // Remove low part of known bits mask
2385 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2386 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2388 // Remove high part of known bit mask
2389 KnownZero = KnownZero.trunc(BitWidth);
2390 KnownOne = KnownOne.trunc(BitWidth);
2393 case ISD::FrameIndex:
2394 case ISD::TargetFrameIndex:
2395 if (unsigned Align = InferPtrAlignment(Op)) {
2396 // The low bits are known zero if the pointer is aligned.
2397 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2403 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2406 case ISD::INTRINSIC_WO_CHAIN:
2407 case ISD::INTRINSIC_W_CHAIN:
2408 case ISD::INTRINSIC_VOID:
2409 // Allow the target to implement this method for its nodes.
2410 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2414 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2417 /// ComputeNumSignBits - Return the number of times the sign bit of the
2418 /// register is replicated into the other bits. We know that at least 1 bit
2419 /// is always equal to the sign bit (itself), but other cases can give us
2420 /// information. For example, immediately after an "SRA X, 2", we know that
2421 /// the top 3 bits are all equal to each other, so we return 3.
2422 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2423 EVT VT = Op.getValueType();
2424 assert(VT.isInteger() && "Invalid VT!");
2425 unsigned VTBits = VT.getScalarType().getSizeInBits();
2427 unsigned FirstAnswer = 1;
2430 return 1; // Limit search depth.
2432 switch (Op.getOpcode()) {
2434 case ISD::AssertSext:
2435 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2436 return VTBits-Tmp+1;
2437 case ISD::AssertZext:
2438 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2441 case ISD::Constant: {
2442 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2443 return Val.getNumSignBits();
2446 case ISD::SIGN_EXTEND:
2448 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2449 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2451 case ISD::SIGN_EXTEND_INREG:
2452 // Max of the input and what this extends.
2454 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2457 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2458 return std::max(Tmp, Tmp2);
2461 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2462 // SRA X, C -> adds C sign bits.
2463 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2464 Tmp += C->getZExtValue();
2465 if (Tmp > VTBits) Tmp = VTBits;
2469 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2470 // shl destroys sign bits.
2471 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2472 if (C->getZExtValue() >= VTBits || // Bad shift.
2473 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2474 return Tmp - C->getZExtValue();
2479 case ISD::XOR: // NOT is handled here.
2480 // Logical binary ops preserve the number of sign bits at the worst.
2481 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2483 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2484 FirstAnswer = std::min(Tmp, Tmp2);
2485 // We computed what we know about the sign bits as our first
2486 // answer. Now proceed to the generic code that uses
2487 // computeKnownBits, and pick whichever answer is better.
2492 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2493 if (Tmp == 1) return 1; // Early out.
2494 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2495 return std::min(Tmp, Tmp2);
2503 if (Op.getResNo() != 1)
2505 // The boolean result conforms to getBooleanContents. Fall through.
2506 // If setcc returns 0/-1, all bits are sign bits.
2507 // We know that we have an integer-based boolean since these operations
2508 // are only available for integer.
2509 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2510 TargetLowering::ZeroOrNegativeOneBooleanContent)
2514 // If setcc returns 0/-1, all bits are sign bits.
2515 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2516 TargetLowering::ZeroOrNegativeOneBooleanContent)
2521 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2522 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2524 // Handle rotate right by N like a rotate left by 32-N.
2525 if (Op.getOpcode() == ISD::ROTR)
2526 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2528 // If we aren't rotating out all of the known-in sign bits, return the
2529 // number that are left. This handles rotl(sext(x), 1) for example.
2530 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2531 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2535 // Add can have at most one carry bit. Thus we know that the output
2536 // is, at worst, one more bit than the inputs.
2537 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2538 if (Tmp == 1) return 1; // Early out.
2540 // Special case decrementing a value (ADD X, -1):
2541 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2542 if (CRHS->isAllOnesValue()) {
2543 APInt KnownZero, KnownOne;
2544 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2546 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2548 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2551 // If we are subtracting one from a positive number, there is no carry
2552 // out of the result.
2553 if (KnownZero.isNegative())
2557 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2558 if (Tmp2 == 1) return 1;
2559 return std::min(Tmp, Tmp2)-1;
2562 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2563 if (Tmp2 == 1) return 1;
2566 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2567 if (CLHS->isNullValue()) {
2568 APInt KnownZero, KnownOne;
2569 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2570 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2572 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2575 // If the input is known to be positive (the sign bit is known clear),
2576 // the output of the NEG has the same number of sign bits as the input.
2577 if (KnownZero.isNegative())
2580 // Otherwise, we treat this like a SUB.
2583 // Sub can have at most one carry bit. Thus we know that the output
2584 // is, at worst, one more bit than the inputs.
2585 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2586 if (Tmp == 1) return 1; // Early out.
2587 return std::min(Tmp, Tmp2)-1;
2589 // FIXME: it's tricky to do anything useful for this, but it is an important
2590 // case for targets like X86.
2592 case ISD::EXTRACT_ELEMENT: {
2593 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2594 const int BitWidth = Op.getValueType().getSizeInBits();
2596 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2598 // Get reverse index (starting from 1), Op1 value indexes elements from
2599 // little end. Sign starts at big end.
2600 const int rIndex = Items - 1 -
2601 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2603 // If the sign portion ends in our element the substraction gives correct
2604 // result. Otherwise it gives either negative or > bitwidth result
2605 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2609 // If we are looking at the loaded value of the SDNode.
2610 if (Op.getResNo() == 0) {
2611 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2612 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2613 unsigned ExtType = LD->getExtensionType();
2616 case ISD::SEXTLOAD: // '17' bits known
2617 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2618 return VTBits-Tmp+1;
2619 case ISD::ZEXTLOAD: // '16' bits known
2620 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2626 // Allow the target to implement this method for its nodes.
2627 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2628 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2629 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2630 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2631 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2632 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2635 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2636 // use this information.
2637 APInt KnownZero, KnownOne;
2638 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2641 if (KnownZero.isNegative()) { // sign bit is 0
2643 } else if (KnownOne.isNegative()) { // sign bit is 1;
2650 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2651 // the number of identical bits in the top of the input value.
2653 Mask <<= Mask.getBitWidth()-VTBits;
2654 // Return # leading zeros. We use 'min' here in case Val was zero before
2655 // shifting. We don't want to return '64' as for an i32 "0".
2656 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2659 /// isBaseWithConstantOffset - Return true if the specified operand is an
2660 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2661 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2662 /// semantics as an ADD. This handles the equivalence:
2663 /// X|Cst == X+Cst iff X&Cst = 0.
2664 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2665 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2666 !isa<ConstantSDNode>(Op.getOperand(1)))
2669 if (Op.getOpcode() == ISD::OR &&
2670 !MaskedValueIsZero(Op.getOperand(0),
2671 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2678 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2679 // If we're told that NaNs won't happen, assume they won't.
2680 if (getTarget().Options.NoNaNsFPMath)
2683 // If the value is a constant, we can obviously see if it is a NaN or not.
2684 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2685 return !C->getValueAPF().isNaN();
2687 // TODO: Recognize more cases here.
2692 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2693 // If the value is a constant, we can obviously see if it is a zero or not.
2694 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2695 return !C->isZero();
2697 // TODO: Recognize more cases here.
2698 switch (Op.getOpcode()) {
2701 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2702 return !C->isNullValue();
2709 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2710 // Check the obvious case.
2711 if (A == B) return true;
2713 // For for negative and positive zero.
2714 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2715 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2716 if (CA->isZero() && CB->isZero()) return true;
2718 // Otherwise they may not be equal.
2722 /// getNode - Gets or creates the specified node.
2724 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2725 FoldingSetNodeID ID;
2726 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2728 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2729 return SDValue(E, 0);
2731 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2732 DL.getDebugLoc(), getVTList(VT));
2733 CSEMap.InsertNode(N, IP);
2736 return SDValue(N, 0);
2739 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2740 EVT VT, SDValue Operand) {
2741 // Constant fold unary operations with an integer constant operand. Even
2742 // opaque constant will be folded, because the folding of unary operations
2743 // doesn't create new constants with different values. Nevertheless, the
2744 // opaque flag is preserved during folding to prevent future folding with
2746 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2747 const APInt &Val = C->getAPIntValue();
2750 case ISD::SIGN_EXTEND:
2751 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2752 C->isTargetOpcode(), C->isOpaque());
2753 case ISD::ANY_EXTEND:
2754 case ISD::ZERO_EXTEND:
2756 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2757 C->isTargetOpcode(), C->isOpaque());
2758 case ISD::UINT_TO_FP:
2759 case ISD::SINT_TO_FP: {
2760 APFloat apf(EVTToAPFloatSemantics(VT),
2761 APInt::getNullValue(VT.getSizeInBits()));
2762 (void)apf.convertFromAPInt(Val,
2763 Opcode==ISD::SINT_TO_FP,
2764 APFloat::rmNearestTiesToEven);
2765 return getConstantFP(apf, DL, VT);
2768 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2769 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2770 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2771 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2772 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2773 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2776 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2779 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2782 case ISD::CTLZ_ZERO_UNDEF:
2783 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2786 case ISD::CTTZ_ZERO_UNDEF:
2787 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2792 // Constant fold unary operations with a floating point constant operand.
2793 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2794 APFloat V = C->getValueAPF(); // make copy
2798 return getConstantFP(V, DL, VT);
2801 return getConstantFP(V, DL, VT);
2803 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2804 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2805 return getConstantFP(V, DL, VT);
2809 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2810 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2811 return getConstantFP(V, DL, VT);
2815 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2816 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2817 return getConstantFP(V, DL, VT);
2820 case ISD::FP_EXTEND: {
2822 // This can return overflow, underflow, or inexact; we don't care.
2823 // FIXME need to be more flexible about rounding mode.
2824 (void)V.convert(EVTToAPFloatSemantics(VT),
2825 APFloat::rmNearestTiesToEven, &ignored);
2826 return getConstantFP(V, DL, VT);
2828 case ISD::FP_TO_SINT:
2829 case ISD::FP_TO_UINT: {
2832 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2833 // FIXME need to be more flexible about rounding mode.
2834 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2835 Opcode==ISD::FP_TO_SINT,
2836 APFloat::rmTowardZero, &ignored);
2837 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2839 APInt api(VT.getSizeInBits(), x);
2840 return getConstant(api, DL, VT);
2843 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2844 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2845 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2846 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2847 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2848 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2853 // Constant fold unary operations with a vector integer or float operand.
2854 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2855 if (BV->isConstant()) {
2858 // FIXME: Entirely reasonable to perform folding of other unary
2859 // operations here as the need arises.
2866 case ISD::FP_EXTEND:
2868 case ISD::UINT_TO_FP:
2869 case ISD::SINT_TO_FP: {
2870 EVT SVT = VT.getScalarType();
2871 EVT InVT = BV->getValueType(0);
2872 EVT InSVT = InVT.getScalarType();
2874 // Find legal integer scalar type for constant promotion.
2876 if (SVT.isInteger()) {
2877 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2878 assert(LegalSVT.bitsGE(SVT) && "Unexpected legal scalar type size");
2881 // Let the above scalar folding handle the folding of each element.
2882 SmallVector<SDValue, 8> Ops;
2883 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2884 SDValue OpN = BV->getOperand(i);
2885 EVT OpVT = OpN.getValueType();
2887 // Build vector (integer) scalar operands may need implicit
2888 // truncation - do this before constant folding.
2889 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2890 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2892 OpN = getNode(Opcode, DL, SVT, OpN);
2894 // Legalize the (integer) scalar constant if necessary.
2895 if (LegalSVT != SVT)
2896 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2898 if (OpN.getOpcode() != ISD::UNDEF &&
2899 OpN.getOpcode() != ISD::Constant &&
2900 OpN.getOpcode() != ISD::ConstantFP)
2904 if (Ops.size() == VT.getVectorNumElements())
2905 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2912 unsigned OpOpcode = Operand.getNode()->getOpcode();
2914 case ISD::TokenFactor:
2915 case ISD::MERGE_VALUES:
2916 case ISD::CONCAT_VECTORS:
2917 return Operand; // Factor, merge or concat of one node? No need.
2918 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2919 case ISD::FP_EXTEND:
2920 assert(VT.isFloatingPoint() &&
2921 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2922 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2923 assert((!VT.isVector() ||
2924 VT.getVectorNumElements() ==
2925 Operand.getValueType().getVectorNumElements()) &&
2926 "Vector element count mismatch!");
2927 if (Operand.getOpcode() == ISD::UNDEF)
2928 return getUNDEF(VT);
2930 case ISD::SIGN_EXTEND:
2931 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2932 "Invalid SIGN_EXTEND!");
2933 if (Operand.getValueType() == VT) return Operand; // noop extension
2934 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2935 "Invalid sext node, dst < src!");
2936 assert((!VT.isVector() ||
2937 VT.getVectorNumElements() ==
2938 Operand.getValueType().getVectorNumElements()) &&
2939 "Vector element count mismatch!");
2940 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2941 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2942 else if (OpOpcode == ISD::UNDEF)
2943 // sext(undef) = 0, because the top bits will all be the same.
2944 return getConstant(0, DL, VT);
2946 case ISD::ZERO_EXTEND:
2947 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2948 "Invalid ZERO_EXTEND!");
2949 if (Operand.getValueType() == VT) return Operand; // noop extension
2950 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2951 "Invalid zext node, dst < src!");
2952 assert((!VT.isVector() ||
2953 VT.getVectorNumElements() ==
2954 Operand.getValueType().getVectorNumElements()) &&
2955 "Vector element count mismatch!");
2956 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2957 return getNode(ISD::ZERO_EXTEND, DL, VT,
2958 Operand.getNode()->getOperand(0));
2959 else if (OpOpcode == ISD::UNDEF)
2960 // zext(undef) = 0, because the top bits will be zero.
2961 return getConstant(0, DL, VT);
2963 case ISD::ANY_EXTEND:
2964 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2965 "Invalid ANY_EXTEND!");
2966 if (Operand.getValueType() == VT) return Operand; // noop extension
2967 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2968 "Invalid anyext node, dst < src!");
2969 assert((!VT.isVector() ||
2970 VT.getVectorNumElements() ==
2971 Operand.getValueType().getVectorNumElements()) &&
2972 "Vector element count mismatch!");
2974 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2975 OpOpcode == ISD::ANY_EXTEND)
2976 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2977 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2978 else if (OpOpcode == ISD::UNDEF)
2979 return getUNDEF(VT);
2981 // (ext (trunx x)) -> x
2982 if (OpOpcode == ISD::TRUNCATE) {
2983 SDValue OpOp = Operand.getNode()->getOperand(0);
2984 if (OpOp.getValueType() == VT)
2989 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2990 "Invalid TRUNCATE!");
2991 if (Operand.getValueType() == VT) return Operand; // noop truncate
2992 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2993 "Invalid truncate node, src < dst!");
2994 assert((!VT.isVector() ||
2995 VT.getVectorNumElements() ==
2996 Operand.getValueType().getVectorNumElements()) &&
2997 "Vector element count mismatch!");
2998 if (OpOpcode == ISD::TRUNCATE)
2999 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3000 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3001 OpOpcode == ISD::ANY_EXTEND) {
3002 // If the source is smaller than the dest, we still need an extend.
3003 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3004 .bitsLT(VT.getScalarType()))
3005 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3006 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3007 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3008 return Operand.getNode()->getOperand(0);
3010 if (OpOpcode == ISD::UNDEF)
3011 return getUNDEF(VT);
3014 // Basic sanity checking.
3015 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3016 && "Cannot BITCAST between types of different sizes!");
3017 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3018 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3019 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3020 if (OpOpcode == ISD::UNDEF)
3021 return getUNDEF(VT);
3023 case ISD::SCALAR_TO_VECTOR:
3024 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3025 (VT.getVectorElementType() == Operand.getValueType() ||
3026 (VT.getVectorElementType().isInteger() &&
3027 Operand.getValueType().isInteger() &&
3028 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3029 "Illegal SCALAR_TO_VECTOR node!");
3030 if (OpOpcode == ISD::UNDEF)
3031 return getUNDEF(VT);
3032 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3033 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3034 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3035 Operand.getConstantOperandVal(1) == 0 &&
3036 Operand.getOperand(0).getValueType() == VT)
3037 return Operand.getOperand(0);
3040 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3041 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3042 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3043 Operand.getNode()->getOperand(0));
3044 if (OpOpcode == ISD::FNEG) // --X -> X
3045 return Operand.getNode()->getOperand(0);
3048 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3049 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3054 SDVTList VTs = getVTList(VT);
3055 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3056 FoldingSetNodeID ID;
3057 SDValue Ops[1] = { Operand };
3058 AddNodeIDNode(ID, Opcode, VTs, Ops);
3060 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3061 return SDValue(E, 0);
3063 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3064 DL.getDebugLoc(), VTs, Operand);
3065 CSEMap.InsertNode(N, IP);
3067 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3068 DL.getDebugLoc(), VTs, Operand);
3072 return SDValue(N, 0);
3075 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3076 SDNode *Cst1, SDNode *Cst2) {
3077 // If the opcode is a target-specific ISD node, there's nothing we can
3078 // do here and the operand rules may not line up with the below, so
3080 if (Opcode >= ISD::BUILTIN_OP_END)
3083 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3084 SmallVector<SDValue, 4> Outputs;
3085 EVT SVT = VT.getScalarType();
3087 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3088 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3089 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3092 if (Scalar1 && Scalar2)
3093 // Scalar instruction.
3094 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3096 // For vectors extract each constant element into Inputs so we can constant
3097 // fold them individually.
3098 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3099 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3103 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3105 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3106 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3107 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3108 if (!V1 || !V2) // Not a constant, bail.
3111 if (V1->isOpaque() || V2->isOpaque())
3114 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3115 // FIXME: This is valid and could be handled by truncating the APInts.
3116 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3119 Inputs.push_back(std::make_pair(V1, V2));
3123 // We have a number of constant values, constant fold them element by element.
3124 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3125 const APInt &C1 = Inputs[I].first->getAPIntValue();
3126 const APInt &C2 = Inputs[I].second->getAPIntValue();
3130 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3133 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3136 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3139 if (!C2.getBoolValue())
3141 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3144 if (!C2.getBoolValue())
3146 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3149 if (!C2.getBoolValue())
3151 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3154 if (!C2.getBoolValue())
3156 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3159 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3162 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3165 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3168 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3171 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3174 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3177 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3180 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3187 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3188 "Expected a scalar or vector!"));
3190 // Handle the scalar case first.
3192 return Outputs.back();
3194 // We may have a vector type but a scalar result. Create a splat.
3195 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3197 // Build a big vector out of the scalar elements we generated.
3198 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3201 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3202 SDValue N2, bool nuw, bool nsw, bool exact) {
3203 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3204 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3207 case ISD::TokenFactor:
3208 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3209 N2.getValueType() == MVT::Other && "Invalid token factor!");
3210 // Fold trivial token factors.
3211 if (N1.getOpcode() == ISD::EntryToken) return N2;
3212 if (N2.getOpcode() == ISD::EntryToken) return N1;
3213 if (N1 == N2) return N1;
3215 case ISD::CONCAT_VECTORS:
3216 // Concat of UNDEFs is UNDEF.
3217 if (N1.getOpcode() == ISD::UNDEF &&
3218 N2.getOpcode() == ISD::UNDEF)
3219 return getUNDEF(VT);
3221 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3222 // one big BUILD_VECTOR.
3223 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3224 N2.getOpcode() == ISD::BUILD_VECTOR) {
3225 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3226 N1.getNode()->op_end());
3227 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3229 // BUILD_VECTOR requires all inputs to be of the same type, find the
3230 // maximum type and extend them all.
3231 EVT SVT = VT.getScalarType();
3232 for (SDValue Op : Elts)
3233 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3234 if (SVT.bitsGT(VT.getScalarType()))
3235 for (SDValue &Op : Elts)
3236 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3237 ? getZExtOrTrunc(Op, DL, SVT)
3238 : getSExtOrTrunc(Op, DL, SVT);
3240 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3244 assert(VT.isInteger() && "This operator does not apply to FP types!");
3245 assert(N1.getValueType() == N2.getValueType() &&
3246 N1.getValueType() == VT && "Binary operator types must match!");
3247 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3248 // worth handling here.
3249 if (N2C && N2C->isNullValue())
3251 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3258 assert(VT.isInteger() && "This operator does not apply to FP types!");
3259 assert(N1.getValueType() == N2.getValueType() &&
3260 N1.getValueType() == VT && "Binary operator types must match!");
3261 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3262 // it's worth handling here.
3263 if (N2C && N2C->isNullValue())
3273 assert(VT.isInteger() && "This operator does not apply to FP types!");
3274 assert(N1.getValueType() == N2.getValueType() &&
3275 N1.getValueType() == VT && "Binary operator types must match!");
3282 if (getTarget().Options.UnsafeFPMath) {
3283 if (Opcode == ISD::FADD) {
3285 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3286 if (CFP->getValueAPF().isZero())
3289 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3290 if (CFP->getValueAPF().isZero())
3292 } else if (Opcode == ISD::FSUB) {
3294 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3295 if (CFP->getValueAPF().isZero())
3297 } else if (Opcode == ISD::FMUL) {
3298 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3301 // If the first operand isn't the constant, try the second
3303 CFP = dyn_cast<ConstantFPSDNode>(N2);
3310 return SDValue(CFP,0);
3312 if (CFP->isExactlyValue(1.0))
3317 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3318 assert(N1.getValueType() == N2.getValueType() &&
3319 N1.getValueType() == VT && "Binary operator types must match!");
3321 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3322 assert(N1.getValueType() == VT &&
3323 N1.getValueType().isFloatingPoint() &&
3324 N2.getValueType().isFloatingPoint() &&
3325 "Invalid FCOPYSIGN!");
3332 assert(VT == N1.getValueType() &&
3333 "Shift operators return type must be the same as their first arg");
3334 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3335 "Shifts only work on integers");
3336 assert((!VT.isVector() || VT == N2.getValueType()) &&
3337 "Vector shift amounts must be in the same as their first arg");
3338 // Verify that the shift amount VT is bit enough to hold valid shift
3339 // amounts. This catches things like trying to shift an i1024 value by an
3340 // i8, which is easy to fall into in generic code that uses
3341 // TLI.getShiftAmount().
3342 assert(N2.getValueType().getSizeInBits() >=
3343 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3344 "Invalid use of small shift amount with oversized value!");
3346 // Always fold shifts of i1 values so the code generator doesn't need to
3347 // handle them. Since we know the size of the shift has to be less than the
3348 // size of the value, the shift/rotate count is guaranteed to be zero.
3351 if (N2C && N2C->isNullValue())
3354 case ISD::FP_ROUND_INREG: {
3355 EVT EVT = cast<VTSDNode>(N2)->getVT();
3356 assert(VT == N1.getValueType() && "Not an inreg round!");
3357 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3358 "Cannot FP_ROUND_INREG integer types");
3359 assert(EVT.isVector() == VT.isVector() &&
3360 "FP_ROUND_INREG type should be vector iff the operand "
3362 assert((!EVT.isVector() ||
3363 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3364 "Vector element counts must match in FP_ROUND_INREG");
3365 assert(EVT.bitsLE(VT) && "Not rounding down!");
3367 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3371 assert(VT.isFloatingPoint() &&
3372 N1.getValueType().isFloatingPoint() &&
3373 VT.bitsLE(N1.getValueType()) &&
3374 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3375 if (N1.getValueType() == VT) return N1; // noop conversion.
3377 case ISD::AssertSext:
3378 case ISD::AssertZext: {
3379 EVT EVT = cast<VTSDNode>(N2)->getVT();
3380 assert(VT == N1.getValueType() && "Not an inreg extend!");
3381 assert(VT.isInteger() && EVT.isInteger() &&
3382 "Cannot *_EXTEND_INREG FP types");
3383 assert(!EVT.isVector() &&
3384 "AssertSExt/AssertZExt type should be the vector element type "
3385 "rather than the vector type!");
3386 assert(EVT.bitsLE(VT) && "Not extending!");
3387 if (VT == EVT) return N1; // noop assertion.
3390 case ISD::SIGN_EXTEND_INREG: {
3391 EVT EVT = cast<VTSDNode>(N2)->getVT();
3392 assert(VT == N1.getValueType() && "Not an inreg extend!");
3393 assert(VT.isInteger() && EVT.isInteger() &&
3394 "Cannot *_EXTEND_INREG FP types");
3395 assert(EVT.isVector() == VT.isVector() &&
3396 "SIGN_EXTEND_INREG type should be vector iff the operand "
3398 assert((!EVT.isVector() ||
3399 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3400 "Vector element counts must match in SIGN_EXTEND_INREG");
3401 assert(EVT.bitsLE(VT) && "Not extending!");
3402 if (EVT == VT) return N1; // Not actually extending
3405 APInt Val = N1C->getAPIntValue();
3406 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3407 Val <<= Val.getBitWidth()-FromBits;
3408 Val = Val.ashr(Val.getBitWidth()-FromBits);
3409 return getConstant(Val, DL, VT);
3413 case ISD::EXTRACT_VECTOR_ELT:
3414 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3415 if (N1.getOpcode() == ISD::UNDEF)
3416 return getUNDEF(VT);
3418 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3419 // expanding copies of large vectors from registers.
3421 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3422 N1.getNumOperands() > 0) {
3424 N1.getOperand(0).getValueType().getVectorNumElements();
3425 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3426 N1.getOperand(N2C->getZExtValue() / Factor),
3427 getConstant(N2C->getZExtValue() % Factor, DL,
3428 N2.getValueType()));
3431 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3432 // expanding large vector constants.
3433 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3434 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3436 if (VT != Elt.getValueType())
3437 // If the vector element type is not legal, the BUILD_VECTOR operands
3438 // are promoted and implicitly truncated, and the result implicitly
3439 // extended. Make that explicit here.
3440 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3445 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3446 // operations are lowered to scalars.
3447 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3448 // If the indices are the same, return the inserted element else
3449 // if the indices are known different, extract the element from
3450 // the original vector.
3451 SDValue N1Op2 = N1.getOperand(2);
3452 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3454 if (N1Op2C && N2C) {
3455 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3456 if (VT == N1.getOperand(1).getValueType())
3457 return N1.getOperand(1);
3459 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3462 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3466 case ISD::EXTRACT_ELEMENT:
3467 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3468 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3469 (N1.getValueType().isInteger() == VT.isInteger()) &&
3470 N1.getValueType() != VT &&
3471 "Wrong types for EXTRACT_ELEMENT!");
3473 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3474 // 64-bit integers into 32-bit parts. Instead of building the extract of
3475 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3476 if (N1.getOpcode() == ISD::BUILD_PAIR)
3477 return N1.getOperand(N2C->getZExtValue());
3479 // EXTRACT_ELEMENT of a constant int is also very common.
3480 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3481 unsigned ElementSize = VT.getSizeInBits();
3482 unsigned Shift = ElementSize * N2C->getZExtValue();
3483 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3484 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3487 case ISD::EXTRACT_SUBVECTOR: {
3489 if (VT.isSimple() && N1.getValueType().isSimple()) {
3490 assert(VT.isVector() && N1.getValueType().isVector() &&
3491 "Extract subvector VTs must be a vectors!");
3492 assert(VT.getVectorElementType() ==
3493 N1.getValueType().getVectorElementType() &&
3494 "Extract subvector VTs must have the same element type!");
3495 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3496 "Extract subvector must be from larger vector to smaller vector!");
3498 if (isa<ConstantSDNode>(Index.getNode())) {
3499 assert((VT.getVectorNumElements() +
3500 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3501 <= N1.getValueType().getVectorNumElements())
3502 && "Extract subvector overflow!");
3505 // Trivial extraction.
3506 if (VT.getSimpleVT() == N1.getSimpleValueType())
3513 // Perform trivial constant folding.
3515 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3518 // Canonicalize constant to RHS if commutative.
3519 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3520 std::swap(N1C, N2C);
3524 // Constant fold FP operations.
3525 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3526 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3527 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3529 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3530 // Canonicalize constant to RHS if commutative.
3531 std::swap(N1CFP, N2CFP);
3534 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3535 APFloat::opStatus s;
3538 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3539 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3540 return getConstantFP(V1, DL, VT);
3543 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3544 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3545 return getConstantFP(V1, DL, VT);
3548 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3549 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3550 return getConstantFP(V1, DL, VT);
3553 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3554 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3555 s!=APFloat::opDivByZero)) {
3556 return getConstantFP(V1, DL, VT);
3560 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3561 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3562 s!=APFloat::opDivByZero)) {
3563 return getConstantFP(V1, DL, VT);
3566 case ISD::FCOPYSIGN:
3568 return getConstantFP(V1, DL, VT);
3573 if (Opcode == ISD::FP_ROUND) {
3574 APFloat V = N1CFP->getValueAPF(); // make copy
3576 // This can return overflow, underflow, or inexact; we don't care.
3577 // FIXME need to be more flexible about rounding mode.
3578 (void)V.convert(EVTToAPFloatSemantics(VT),
3579 APFloat::rmNearestTiesToEven, &ignored);
3580 return getConstantFP(V, DL, VT);
3584 // Canonicalize an UNDEF to the RHS, even over a constant.
3585 if (N1.getOpcode() == ISD::UNDEF) {
3586 if (isCommutativeBinOp(Opcode)) {
3590 case ISD::FP_ROUND_INREG:
3591 case ISD::SIGN_EXTEND_INREG:
3597 return N1; // fold op(undef, arg2) -> undef
3605 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3606 // For vectors, we can't easily build an all zero vector, just return
3613 // Fold a bunch of operators when the RHS is undef.
3614 if (N2.getOpcode() == ISD::UNDEF) {
3617 if (N1.getOpcode() == ISD::UNDEF)
3618 // Handle undef ^ undef -> 0 special case. This is a common
3620 return getConstant(0, DL, VT);
3630 return N2; // fold op(arg1, undef) -> undef
3636 if (getTarget().Options.UnsafeFPMath)
3644 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3645 // For vectors, we can't easily build an all zero vector, just return
3650 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3651 // For vectors, we can't easily build an all one vector, just return
3659 // Memoize this node if possible.
3661 SDVTList VTs = getVTList(VT);
3662 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3663 if (VT != MVT::Glue) {
3664 SDValue Ops[] = {N1, N2};
3665 FoldingSetNodeID ID;
3666 AddNodeIDNode(ID, Opcode, VTs, Ops);
3668 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3670 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3671 return SDValue(E, 0);
3673 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3675 CSEMap.InsertNode(N, IP);
3677 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3681 return SDValue(N, 0);
3684 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3685 SDValue N1, SDValue N2, SDValue N3) {
3686 // Perform various simplifications.
3687 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3690 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3691 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3692 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3693 if (N1CFP && N2CFP && N3CFP) {
3694 APFloat V1 = N1CFP->getValueAPF();
3695 const APFloat &V2 = N2CFP->getValueAPF();
3696 const APFloat &V3 = N3CFP->getValueAPF();
3697 APFloat::opStatus s =
3698 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3699 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3700 return getConstantFP(V1, DL, VT);
3704 case ISD::CONCAT_VECTORS:
3705 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3706 // one big BUILD_VECTOR.
3707 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3708 N2.getOpcode() == ISD::BUILD_VECTOR &&
3709 N3.getOpcode() == ISD::BUILD_VECTOR) {
3710 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3711 N1.getNode()->op_end());
3712 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3713 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3714 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3718 // Use FoldSetCC to simplify SETCC's.
3719 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3720 if (Simp.getNode()) return Simp;
3725 if (N1C->getZExtValue())
3726 return N2; // select true, X, Y -> X
3727 return N3; // select false, X, Y -> Y
3730 if (N2 == N3) return N2; // select C, X, X -> X
3732 case ISD::VECTOR_SHUFFLE:
3733 llvm_unreachable("should use getVectorShuffle constructor!");
3734 case ISD::INSERT_SUBVECTOR: {
3736 if (VT.isSimple() && N1.getValueType().isSimple()
3737 && N2.getValueType().isSimple()) {
3738 assert(VT.isVector() && N1.getValueType().isVector() &&
3739 N2.getValueType().isVector() &&
3740 "Insert subvector VTs must be a vectors");
3741 assert(VT == N1.getValueType() &&
3742 "Dest and insert subvector source types must match!");
3743 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3744 "Insert subvector must be from smaller vector to larger vector!");
3745 if (isa<ConstantSDNode>(Index.getNode())) {
3746 assert((N2.getValueType().getVectorNumElements() +
3747 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3748 <= VT.getVectorNumElements())
3749 && "Insert subvector overflow!");
3752 // Trivial insertion.
3753 if (VT.getSimpleVT() == N2.getSimpleValueType())
3759 // Fold bit_convert nodes from a type to themselves.
3760 if (N1.getValueType() == VT)
3765 // Memoize node if it doesn't produce a flag.
3767 SDVTList VTs = getVTList(VT);
3768 if (VT != MVT::Glue) {
3769 SDValue Ops[] = { N1, N2, N3 };
3770 FoldingSetNodeID ID;
3771 AddNodeIDNode(ID, Opcode, VTs, Ops);
3773 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3774 return SDValue(E, 0);
3776 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3777 DL.getDebugLoc(), VTs, N1, N2, N3);
3778 CSEMap.InsertNode(N, IP);
3780 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3781 DL.getDebugLoc(), VTs, N1, N2, N3);
3785 return SDValue(N, 0);
3788 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3789 SDValue N1, SDValue N2, SDValue N3,
3791 SDValue Ops[] = { N1, N2, N3, N4 };
3792 return getNode(Opcode, DL, VT, Ops);
3795 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3796 SDValue N1, SDValue N2, SDValue N3,
3797 SDValue N4, SDValue N5) {
3798 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3799 return getNode(Opcode, DL, VT, Ops);
3802 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3803 /// the incoming stack arguments to be loaded from the stack.
3804 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3805 SmallVector<SDValue, 8> ArgChains;
3807 // Include the original chain at the beginning of the list. When this is
3808 // used by target LowerCall hooks, this helps legalize find the
3809 // CALLSEQ_BEGIN node.
3810 ArgChains.push_back(Chain);
3812 // Add a chain value for each stack argument.
3813 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3814 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3815 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3816 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3817 if (FI->getIndex() < 0)
3818 ArgChains.push_back(SDValue(L, 1));
3820 // Build a tokenfactor for all the chains.
3821 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3824 /// getMemsetValue - Vectorized representation of the memset value
3826 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3828 assert(Value.getOpcode() != ISD::UNDEF);
3830 unsigned NumBits = VT.getScalarType().getSizeInBits();
3831 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3832 assert(C->getAPIntValue().getBitWidth() == 8);
3833 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3835 return DAG.getConstant(Val, dl, VT);
3836 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3840 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3841 EVT IntVT = VT.getScalarType();
3842 if (!IntVT.isInteger())
3843 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3845 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3847 // Use a multiplication with 0x010101... to extend the input to the
3849 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3850 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3851 DAG.getConstant(Magic, dl, IntVT));
3854 if (VT != Value.getValueType() && !VT.isInteger())
3855 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3856 if (VT != Value.getValueType()) {
3857 assert(VT.getVectorElementType() == Value.getValueType() &&
3858 "value type should be one vector element here");
3859 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3860 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3866 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3867 /// used when a memcpy is turned into a memset when the source is a constant
3869 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3870 const TargetLowering &TLI, StringRef Str) {
3871 // Handle vector with all elements zero.
3874 return DAG.getConstant(0, dl, VT);
3875 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3876 return DAG.getConstantFP(0.0, dl, VT);
3877 else if (VT.isVector()) {
3878 unsigned NumElts = VT.getVectorNumElements();
3879 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3880 return DAG.getNode(ISD::BITCAST, dl, VT,
3881 DAG.getConstant(0, dl,
3882 EVT::getVectorVT(*DAG.getContext(),
3885 llvm_unreachable("Expected type!");
3888 assert(!VT.isVector() && "Can't handle vector type here!");
3889 unsigned NumVTBits = VT.getSizeInBits();
3890 unsigned NumVTBytes = NumVTBits / 8;
3891 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3893 APInt Val(NumVTBits, 0);
3894 if (TLI.isLittleEndian()) {
3895 for (unsigned i = 0; i != NumBytes; ++i)
3896 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3898 for (unsigned i = 0; i != NumBytes; ++i)
3899 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3902 // If the "cost" of materializing the integer immediate is less than the cost
3903 // of a load, then it is cost effective to turn the load into the immediate.
3904 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3905 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3906 return DAG.getConstant(Val, dl, VT);
3907 return SDValue(nullptr, 0);
3910 /// getMemBasePlusOffset - Returns base and offset node for the
3912 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3913 SelectionDAG &DAG) {
3914 EVT VT = Base.getValueType();
3915 return DAG.getNode(ISD::ADD, dl,
3916 VT, Base, DAG.getConstant(Offset, dl, VT));
3919 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3921 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3922 unsigned SrcDelta = 0;
3923 GlobalAddressSDNode *G = nullptr;
3924 if (Src.getOpcode() == ISD::GlobalAddress)
3925 G = cast<GlobalAddressSDNode>(Src);
3926 else if (Src.getOpcode() == ISD::ADD &&
3927 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3928 Src.getOperand(1).getOpcode() == ISD::Constant) {
3929 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3930 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3935 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3938 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3939 /// to replace the memset / memcpy. Return true if the number of memory ops
3940 /// is below the threshold. It returns the types of the sequence of
3941 /// memory ops to perform memset / memcpy by reference.
3942 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3943 unsigned Limit, uint64_t Size,
3944 unsigned DstAlign, unsigned SrcAlign,
3950 const TargetLowering &TLI) {
3951 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3952 "Expecting memcpy / memset source to meet alignment requirement!");
3953 // If 'SrcAlign' is zero, that means the memory operation does not need to
3954 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3955 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3956 // is the specified alignment of the memory operation. If it is zero, that
3957 // means it's possible to change the alignment of the destination.
3958 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3959 // not need to be loaded.
3960 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3961 IsMemset, ZeroMemset, MemcpyStrSrc,
3962 DAG.getMachineFunction());
3964 if (VT == MVT::Other) {
3966 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3967 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3968 VT = TLI.getPointerTy();
3970 switch (DstAlign & 7) {
3971 case 0: VT = MVT::i64; break;
3972 case 4: VT = MVT::i32; break;
3973 case 2: VT = MVT::i16; break;
3974 default: VT = MVT::i8; break;
3979 while (!TLI.isTypeLegal(LVT))
3980 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3981 assert(LVT.isInteger());
3987 unsigned NumMemOps = 0;
3989 unsigned VTSize = VT.getSizeInBits() / 8;
3990 while (VTSize > Size) {
3991 // For now, only use non-vector load / store's for the left-over pieces.
3996 if (VT.isVector() || VT.isFloatingPoint()) {
3997 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3998 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3999 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4001 else if (NewVT == MVT::i64 &&
4002 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4003 TLI.isSafeMemOpType(MVT::f64)) {
4004 // i64 is usually not legal on 32-bit targets, but f64 may be.
4012 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4013 if (NewVT == MVT::i8)
4015 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4017 NewVTSize = NewVT.getSizeInBits() / 8;
4019 // If the new VT cannot cover all of the remaining bits, then consider
4020 // issuing a (or a pair of) unaligned and overlapping load / store.
4021 // FIXME: Only does this for 64-bit or more since we don't have proper
4022 // cost model for unaligned load / store.
4025 if (NumMemOps && AllowOverlap &&
4026 VTSize >= 8 && NewVTSize < Size &&
4027 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4035 if (++NumMemOps > Limit)
4038 MemOps.push_back(VT);
4045 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4046 SDValue Chain, SDValue Dst,
4047 SDValue Src, uint64_t Size,
4048 unsigned Align, bool isVol,
4050 MachinePointerInfo DstPtrInfo,
4051 MachinePointerInfo SrcPtrInfo) {
4052 // Turn a memcpy of undef to nop.
4053 if (Src.getOpcode() == ISD::UNDEF)
4056 // Expand memcpy to a series of load and store ops if the size operand falls
4057 // below a certain threshold.
4058 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4059 // rather than maybe a humongous number of loads and stores.
4060 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4061 std::vector<EVT> MemOps;
4062 bool DstAlignCanChange = false;
4063 MachineFunction &MF = DAG.getMachineFunction();
4064 MachineFrameInfo *MFI = MF.getFrameInfo();
4065 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4066 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4067 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4068 DstAlignCanChange = true;
4069 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4070 if (Align > SrcAlign)
4073 bool CopyFromStr = isMemSrcFromString(Src, Str);
4074 bool isZeroStr = CopyFromStr && Str.empty();
4075 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4077 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4078 (DstAlignCanChange ? 0 : Align),
4079 (isZeroStr ? 0 : SrcAlign),
4080 false, false, CopyFromStr, true, DAG, TLI))
4083 if (DstAlignCanChange) {
4084 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4085 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4087 // Don't promote to an alignment that would require dynamic stack
4089 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4090 if (!TRI->needsStackRealignment(MF))
4091 while (NewAlign > Align &&
4092 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4095 if (NewAlign > Align) {
4096 // Give the stack frame object a larger alignment if needed.
4097 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4098 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4103 SmallVector<SDValue, 8> OutChains;
4104 unsigned NumMemOps = MemOps.size();
4105 uint64_t SrcOff = 0, DstOff = 0;
4106 for (unsigned i = 0; i != NumMemOps; ++i) {
4108 unsigned VTSize = VT.getSizeInBits() / 8;
4109 SDValue Value, Store;
4111 if (VTSize > Size) {
4112 // Issuing an unaligned load / store pair that overlaps with the previous
4113 // pair. Adjust the offset accordingly.
4114 assert(i == NumMemOps-1 && i != 0);
4115 SrcOff -= VTSize - Size;
4116 DstOff -= VTSize - Size;
4120 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4121 // It's unlikely a store of a vector immediate can be done in a single
4122 // instruction. It would require a load from a constantpool first.
4123 // We only handle zero vectors here.
4124 // FIXME: Handle other cases where store of vector immediate is done in
4125 // a single instruction.
4126 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4127 if (Value.getNode())
4128 Store = DAG.getStore(Chain, dl, Value,
4129 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4130 DstPtrInfo.getWithOffset(DstOff), isVol,
4134 if (!Store.getNode()) {
4135 // The type might not be legal for the target. This should only happen
4136 // if the type is smaller than a legal type, as on PPC, so the right
4137 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4138 // to Load/Store if NVT==VT.
4139 // FIXME does the case above also need this?
4140 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4141 assert(NVT.bitsGE(VT));
4142 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4143 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4144 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4145 false, MinAlign(SrcAlign, SrcOff));
4146 Store = DAG.getTruncStore(Chain, dl, Value,
4147 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4148 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4151 OutChains.push_back(Store);
4157 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4160 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4161 SDValue Chain, SDValue Dst,
4162 SDValue Src, uint64_t Size,
4163 unsigned Align, bool isVol,
4165 MachinePointerInfo DstPtrInfo,
4166 MachinePointerInfo SrcPtrInfo) {
4167 // Turn a memmove of undef to nop.
4168 if (Src.getOpcode() == ISD::UNDEF)
4171 // Expand memmove to a series of load and store ops if the size operand falls
4172 // below a certain threshold.
4173 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4174 std::vector<EVT> MemOps;
4175 bool DstAlignCanChange = false;
4176 MachineFunction &MF = DAG.getMachineFunction();
4177 MachineFrameInfo *MFI = MF.getFrameInfo();
4178 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4179 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4180 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4181 DstAlignCanChange = true;
4182 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4183 if (Align > SrcAlign)
4185 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4187 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4188 (DstAlignCanChange ? 0 : Align), SrcAlign,
4189 false, false, false, false, DAG, TLI))
4192 if (DstAlignCanChange) {
4193 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4194 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4195 if (NewAlign > Align) {
4196 // Give the stack frame object a larger alignment if needed.
4197 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4198 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4203 uint64_t SrcOff = 0, DstOff = 0;
4204 SmallVector<SDValue, 8> LoadValues;
4205 SmallVector<SDValue, 8> LoadChains;
4206 SmallVector<SDValue, 8> OutChains;
4207 unsigned NumMemOps = MemOps.size();
4208 for (unsigned i = 0; i < NumMemOps; i++) {
4210 unsigned VTSize = VT.getSizeInBits() / 8;
4213 Value = DAG.getLoad(VT, dl, Chain,
4214 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4215 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4216 false, false, SrcAlign);
4217 LoadValues.push_back(Value);
4218 LoadChains.push_back(Value.getValue(1));
4221 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4223 for (unsigned i = 0; i < NumMemOps; i++) {
4225 unsigned VTSize = VT.getSizeInBits() / 8;
4228 Store = DAG.getStore(Chain, dl, LoadValues[i],
4229 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4230 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4231 OutChains.push_back(Store);
4235 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4238 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4241 /// \param DAG Selection DAG where lowered code is placed.
4242 /// \param dl Link to corresponding IR location.
4243 /// \param Chain Control flow dependency.
4244 /// \param Dst Pointer to destination memory location.
4245 /// \param Src Value of byte to write into the memory.
4246 /// \param Size Number of bytes to write.
4247 /// \param Align Alignment of the destination in bytes.
4248 /// \param isVol True if destination is volatile.
4249 /// \param DstPtrInfo IR information on the memory pointer.
4250 /// \returns New head in the control flow, if lowering was successful, empty
4251 /// SDValue otherwise.
4253 /// The function tries to replace 'llvm.memset' intrinsic with several store
4254 /// operations and value calculation code. This is usually profitable for small
4256 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4257 SDValue Chain, SDValue Dst,
4258 SDValue Src, uint64_t Size,
4259 unsigned Align, bool isVol,
4260 MachinePointerInfo DstPtrInfo) {
4261 // Turn a memset of undef to nop.
4262 if (Src.getOpcode() == ISD::UNDEF)
4265 // Expand memset to a series of load/store ops if the size operand
4266 // falls below a certain threshold.
4267 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4268 std::vector<EVT> MemOps;
4269 bool DstAlignCanChange = false;
4270 MachineFunction &MF = DAG.getMachineFunction();
4271 MachineFrameInfo *MFI = MF.getFrameInfo();
4272 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4273 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4274 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4275 DstAlignCanChange = true;
4277 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4278 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4279 Size, (DstAlignCanChange ? 0 : Align), 0,
4280 true, IsZeroVal, false, true, DAG, TLI))
4283 if (DstAlignCanChange) {
4284 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4285 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4286 if (NewAlign > Align) {
4287 // Give the stack frame object a larger alignment if needed.
4288 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4289 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4294 SmallVector<SDValue, 8> OutChains;
4295 uint64_t DstOff = 0;
4296 unsigned NumMemOps = MemOps.size();
4298 // Find the largest store and generate the bit pattern for it.
4299 EVT LargestVT = MemOps[0];
4300 for (unsigned i = 1; i < NumMemOps; i++)
4301 if (MemOps[i].bitsGT(LargestVT))
4302 LargestVT = MemOps[i];
4303 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4305 for (unsigned i = 0; i < NumMemOps; i++) {
4307 unsigned VTSize = VT.getSizeInBits() / 8;
4308 if (VTSize > Size) {
4309 // Issuing an unaligned load / store pair that overlaps with the previous
4310 // pair. Adjust the offset accordingly.
4311 assert(i == NumMemOps-1 && i != 0);
4312 DstOff -= VTSize - Size;
4315 // If this store is smaller than the largest store see whether we can get
4316 // the smaller value for free with a truncate.
4317 SDValue Value = MemSetValue;
4318 if (VT.bitsLT(LargestVT)) {
4319 if (!LargestVT.isVector() && !VT.isVector() &&
4320 TLI.isTruncateFree(LargestVT, VT))
4321 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4323 Value = getMemsetValue(Src, VT, DAG, dl);
4325 assert(Value.getValueType() == VT && "Value with wrong type.");
4326 SDValue Store = DAG.getStore(Chain, dl, Value,
4327 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4328 DstPtrInfo.getWithOffset(DstOff),
4329 isVol, false, Align);
4330 OutChains.push_back(Store);
4331 DstOff += VT.getSizeInBits() / 8;
4335 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4338 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4339 SDValue Src, SDValue Size,
4340 unsigned Align, bool isVol, bool AlwaysInline,
4341 bool isTailCall, MachinePointerInfo DstPtrInfo,
4342 MachinePointerInfo SrcPtrInfo) {
4343 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4345 // Check to see if we should lower the memcpy to loads and stores first.
4346 // For cases within the target-specified limits, this is the best choice.
4347 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4349 // Memcpy with size zero? Just return the original chain.
4350 if (ConstantSize->isNullValue())
4353 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4354 ConstantSize->getZExtValue(),Align,
4355 isVol, false, DstPtrInfo, SrcPtrInfo);
4356 if (Result.getNode())
4360 // Then check to see if we should lower the memcpy with target-specific
4361 // code. If the target chooses to do this, this is the next best.
4363 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4364 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4365 DstPtrInfo, SrcPtrInfo);
4366 if (Result.getNode())
4370 // If we really need inline code and the target declined to provide it,
4371 // use a (potentially long) sequence of loads and stores.
4373 assert(ConstantSize && "AlwaysInline requires a constant size!");
4374 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4375 ConstantSize->getZExtValue(), Align, isVol,
4376 true, DstPtrInfo, SrcPtrInfo);
4379 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4380 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4381 // respect volatile, so they may do things like read or write memory
4382 // beyond the given memory regions. But fixing this isn't easy, and most
4383 // people don't care.
4385 // Emit a library call.
4386 TargetLowering::ArgListTy Args;
4387 TargetLowering::ArgListEntry Entry;
4388 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4389 Entry.Node = Dst; Args.push_back(Entry);
4390 Entry.Node = Src; Args.push_back(Entry);
4391 Entry.Node = Size; Args.push_back(Entry);
4392 // FIXME: pass in SDLoc
4393 TargetLowering::CallLoweringInfo CLI(*this);
4394 CLI.setDebugLoc(dl).setChain(Chain)
4395 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4396 Type::getVoidTy(*getContext()),
4397 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4398 TLI->getPointerTy()), std::move(Args), 0)
4400 .setTailCall(isTailCall);
4402 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4403 return CallResult.second;
4406 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4407 SDValue Src, SDValue Size,
4408 unsigned Align, bool isVol, bool isTailCall,
4409 MachinePointerInfo DstPtrInfo,
4410 MachinePointerInfo SrcPtrInfo) {
4411 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4413 // Check to see if we should lower the memmove to loads and stores first.
4414 // For cases within the target-specified limits, this is the best choice.
4415 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4417 // Memmove with size zero? Just return the original chain.
4418 if (ConstantSize->isNullValue())
4422 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4423 ConstantSize->getZExtValue(), Align, isVol,
4424 false, DstPtrInfo, SrcPtrInfo);
4425 if (Result.getNode())
4429 // Then check to see if we should lower the memmove with target-specific
4430 // code. If the target chooses to do this, this is the next best.
4432 SDValue Result = TSI->EmitTargetCodeForMemmove(
4433 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4434 if (Result.getNode())
4438 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4439 // not be safe. See memcpy above for more details.
4441 // Emit a library call.
4442 TargetLowering::ArgListTy Args;
4443 TargetLowering::ArgListEntry Entry;
4444 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4445 Entry.Node = Dst; Args.push_back(Entry);
4446 Entry.Node = Src; Args.push_back(Entry);
4447 Entry.Node = Size; Args.push_back(Entry);
4448 // FIXME: pass in SDLoc
4449 TargetLowering::CallLoweringInfo CLI(*this);
4450 CLI.setDebugLoc(dl).setChain(Chain)
4451 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4452 Type::getVoidTy(*getContext()),
4453 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4454 TLI->getPointerTy()), std::move(Args), 0)
4456 .setTailCall(isTailCall);
4458 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4459 return CallResult.second;
4462 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4463 SDValue Src, SDValue Size,
4464 unsigned Align, bool isVol, bool isTailCall,
4465 MachinePointerInfo DstPtrInfo) {
4466 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4468 // Check to see if we should lower the memset to stores first.
4469 // For cases within the target-specified limits, this is the best choice.
4470 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4472 // Memset with size zero? Just return the original chain.
4473 if (ConstantSize->isNullValue())
4477 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4478 Align, isVol, DstPtrInfo);
4480 if (Result.getNode())
4484 // Then check to see if we should lower the memset with target-specific
4485 // code. If the target chooses to do this, this is the next best.
4487 SDValue Result = TSI->EmitTargetCodeForMemset(
4488 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4489 if (Result.getNode())
4493 // Emit a library call.
4494 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4495 TargetLowering::ArgListTy Args;
4496 TargetLowering::ArgListEntry Entry;
4497 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4498 Args.push_back(Entry);
4500 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4501 Args.push_back(Entry);
4503 Entry.Ty = IntPtrTy;
4504 Args.push_back(Entry);
4506 // FIXME: pass in SDLoc
4507 TargetLowering::CallLoweringInfo CLI(*this);
4508 CLI.setDebugLoc(dl).setChain(Chain)
4509 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4510 Type::getVoidTy(*getContext()),
4511 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4512 TLI->getPointerTy()), std::move(Args), 0)
4514 .setTailCall(isTailCall);
4516 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4517 return CallResult.second;
4520 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4521 SDVTList VTList, ArrayRef<SDValue> Ops,
4522 MachineMemOperand *MMO,
4523 AtomicOrdering SuccessOrdering,
4524 AtomicOrdering FailureOrdering,
4525 SynchronizationScope SynchScope) {
4526 FoldingSetNodeID ID;
4527 ID.AddInteger(MemVT.getRawBits());
4528 AddNodeIDNode(ID, Opcode, VTList, Ops);
4529 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4531 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4532 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4533 return SDValue(E, 0);
4536 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4537 // SDNode doesn't have access to it. This memory will be "leaked" when
4538 // the node is deallocated, but recovered when the allocator is released.
4539 // If the number of operands is less than 5 we use AtomicSDNode's internal
4541 unsigned NumOps = Ops.size();
4542 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4545 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4546 dl.getDebugLoc(), VTList, MemVT,
4547 Ops.data(), DynOps, NumOps, MMO,
4548 SuccessOrdering, FailureOrdering,
4550 CSEMap.InsertNode(N, IP);
4552 return SDValue(N, 0);
4555 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4556 SDVTList VTList, ArrayRef<SDValue> Ops,
4557 MachineMemOperand *MMO,
4558 AtomicOrdering Ordering,
4559 SynchronizationScope SynchScope) {
4560 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4561 Ordering, SynchScope);
4564 SDValue SelectionDAG::getAtomicCmpSwap(
4565 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4566 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4567 unsigned Alignment, AtomicOrdering SuccessOrdering,
4568 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4569 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4570 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4571 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4573 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4574 Alignment = getEVTAlignment(MemVT);
4576 MachineFunction &MF = getMachineFunction();
4578 // FIXME: Volatile isn't really correct; we should keep track of atomic
4579 // orderings in the memoperand.
4580 unsigned Flags = MachineMemOperand::MOVolatile;
4581 Flags |= MachineMemOperand::MOLoad;
4582 Flags |= MachineMemOperand::MOStore;
4584 MachineMemOperand *MMO =
4585 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4587 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4588 SuccessOrdering, FailureOrdering, SynchScope);
4591 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4592 SDVTList VTs, SDValue Chain, SDValue Ptr,
4593 SDValue Cmp, SDValue Swp,
4594 MachineMemOperand *MMO,
4595 AtomicOrdering SuccessOrdering,
4596 AtomicOrdering FailureOrdering,
4597 SynchronizationScope SynchScope) {
4598 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4599 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4600 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4602 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4603 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4604 SuccessOrdering, FailureOrdering, SynchScope);
4607 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4609 SDValue Ptr, SDValue Val,
4610 const Value* PtrVal,
4612 AtomicOrdering Ordering,
4613 SynchronizationScope SynchScope) {
4614 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4615 Alignment = getEVTAlignment(MemVT);
4617 MachineFunction &MF = getMachineFunction();
4618 // An atomic store does not load. An atomic load does not store.
4619 // (An atomicrmw obviously both loads and stores.)
4620 // For now, atomics are considered to be volatile always, and they are
4622 // FIXME: Volatile isn't really correct; we should keep track of atomic
4623 // orderings in the memoperand.
4624 unsigned Flags = MachineMemOperand::MOVolatile;
4625 if (Opcode != ISD::ATOMIC_STORE)
4626 Flags |= MachineMemOperand::MOLoad;
4627 if (Opcode != ISD::ATOMIC_LOAD)
4628 Flags |= MachineMemOperand::MOStore;
4630 MachineMemOperand *MMO =
4631 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4632 MemVT.getStoreSize(), Alignment);
4634 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4635 Ordering, SynchScope);
4638 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4640 SDValue Ptr, SDValue Val,
4641 MachineMemOperand *MMO,
4642 AtomicOrdering Ordering,
4643 SynchronizationScope SynchScope) {
4644 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4645 Opcode == ISD::ATOMIC_LOAD_SUB ||
4646 Opcode == ISD::ATOMIC_LOAD_AND ||
4647 Opcode == ISD::ATOMIC_LOAD_OR ||
4648 Opcode == ISD::ATOMIC_LOAD_XOR ||
4649 Opcode == ISD::ATOMIC_LOAD_NAND ||
4650 Opcode == ISD::ATOMIC_LOAD_MIN ||
4651 Opcode == ISD::ATOMIC_LOAD_MAX ||
4652 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4653 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4654 Opcode == ISD::ATOMIC_SWAP ||
4655 Opcode == ISD::ATOMIC_STORE) &&
4656 "Invalid Atomic Op");
4658 EVT VT = Val.getValueType();
4660 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4661 getVTList(VT, MVT::Other);
4662 SDValue Ops[] = {Chain, Ptr, Val};
4663 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4666 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4667 EVT VT, SDValue Chain,
4669 MachineMemOperand *MMO,
4670 AtomicOrdering Ordering,
4671 SynchronizationScope SynchScope) {
4672 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4674 SDVTList VTs = getVTList(VT, MVT::Other);
4675 SDValue Ops[] = {Chain, Ptr};
4676 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4679 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4680 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4681 if (Ops.size() == 1)
4684 SmallVector<EVT, 4> VTs;
4685 VTs.reserve(Ops.size());
4686 for (unsigned i = 0; i < Ops.size(); ++i)
4687 VTs.push_back(Ops[i].getValueType());
4688 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4692 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4693 ArrayRef<SDValue> Ops,
4694 EVT MemVT, MachinePointerInfo PtrInfo,
4695 unsigned Align, bool Vol,
4696 bool ReadMem, bool WriteMem, unsigned Size) {
4697 if (Align == 0) // Ensure that codegen never sees alignment 0
4698 Align = getEVTAlignment(MemVT);
4700 MachineFunction &MF = getMachineFunction();
4703 Flags |= MachineMemOperand::MOStore;
4705 Flags |= MachineMemOperand::MOLoad;
4707 Flags |= MachineMemOperand::MOVolatile;
4709 Size = MemVT.getStoreSize();
4710 MachineMemOperand *MMO =
4711 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4713 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4717 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4718 ArrayRef<SDValue> Ops, EVT MemVT,
4719 MachineMemOperand *MMO) {
4720 assert((Opcode == ISD::INTRINSIC_VOID ||
4721 Opcode == ISD::INTRINSIC_W_CHAIN ||
4722 Opcode == ISD::PREFETCH ||
4723 Opcode == ISD::LIFETIME_START ||
4724 Opcode == ISD::LIFETIME_END ||
4725 (Opcode <= INT_MAX &&
4726 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4727 "Opcode is not a memory-accessing opcode!");
4729 // Memoize the node unless it returns a flag.
4730 MemIntrinsicSDNode *N;
4731 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4732 FoldingSetNodeID ID;
4733 AddNodeIDNode(ID, Opcode, VTList, Ops);
4734 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4736 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4737 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4738 return SDValue(E, 0);
4741 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4742 dl.getDebugLoc(), VTList, Ops,
4744 CSEMap.InsertNode(N, IP);
4746 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4747 dl.getDebugLoc(), VTList, Ops,
4751 return SDValue(N, 0);
4754 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4755 /// MachinePointerInfo record from it. This is particularly useful because the
4756 /// code generator has many cases where it doesn't bother passing in a
4757 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4758 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4759 // If this is FI+Offset, we can model it.
4760 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4761 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4763 // If this is (FI+Offset1)+Offset2, we can model it.
4764 if (Ptr.getOpcode() != ISD::ADD ||
4765 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4766 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4767 return MachinePointerInfo();
4769 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4770 return MachinePointerInfo::getFixedStack(FI, Offset+
4771 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4774 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4775 /// MachinePointerInfo record from it. This is particularly useful because the
4776 /// code generator has many cases where it doesn't bother passing in a
4777 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4778 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4779 // If the 'Offset' value isn't a constant, we can't handle this.
4780 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4781 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4782 if (OffsetOp.getOpcode() == ISD::UNDEF)
4783 return InferPointerInfo(Ptr);
4784 return MachinePointerInfo();
4789 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4790 EVT VT, SDLoc dl, SDValue Chain,
4791 SDValue Ptr, SDValue Offset,
4792 MachinePointerInfo PtrInfo, EVT MemVT,
4793 bool isVolatile, bool isNonTemporal, bool isInvariant,
4794 unsigned Alignment, const AAMDNodes &AAInfo,
4795 const MDNode *Ranges) {
4796 assert(Chain.getValueType() == MVT::Other &&
4797 "Invalid chain type");
4798 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4799 Alignment = getEVTAlignment(VT);
4801 unsigned Flags = MachineMemOperand::MOLoad;
4803 Flags |= MachineMemOperand::MOVolatile;
4805 Flags |= MachineMemOperand::MONonTemporal;
4807 Flags |= MachineMemOperand::MOInvariant;
4809 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4811 if (PtrInfo.V.isNull())
4812 PtrInfo = InferPointerInfo(Ptr, Offset);
4814 MachineFunction &MF = getMachineFunction();
4815 MachineMemOperand *MMO =
4816 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4818 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4822 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4823 EVT VT, SDLoc dl, SDValue Chain,
4824 SDValue Ptr, SDValue Offset, EVT MemVT,
4825 MachineMemOperand *MMO) {
4827 ExtType = ISD::NON_EXTLOAD;
4828 } else if (ExtType == ISD::NON_EXTLOAD) {
4829 assert(VT == MemVT && "Non-extending load from different memory type!");
4832 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4833 "Should only be an extending load, not truncating!");
4834 assert(VT.isInteger() == MemVT.isInteger() &&
4835 "Cannot convert from FP to Int or Int -> FP!");
4836 assert(VT.isVector() == MemVT.isVector() &&
4837 "Cannot use an ext load to convert to or from a vector!");
4838 assert((!VT.isVector() ||
4839 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4840 "Cannot use an ext load to change the number of vector elements!");
4843 bool Indexed = AM != ISD::UNINDEXED;
4844 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4845 "Unindexed load with an offset!");
4847 SDVTList VTs = Indexed ?
4848 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4849 SDValue Ops[] = { Chain, Ptr, Offset };
4850 FoldingSetNodeID ID;
4851 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4852 ID.AddInteger(MemVT.getRawBits());
4853 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4854 MMO->isNonTemporal(),
4855 MMO->isInvariant()));
4856 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4858 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4859 cast<LoadSDNode>(E)->refineAlignment(MMO);
4860 return SDValue(E, 0);
4862 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4863 dl.getDebugLoc(), VTs, AM, ExtType,
4865 CSEMap.InsertNode(N, IP);
4867 return SDValue(N, 0);
4870 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4871 SDValue Chain, SDValue Ptr,
4872 MachinePointerInfo PtrInfo,
4873 bool isVolatile, bool isNonTemporal,
4874 bool isInvariant, unsigned Alignment,
4875 const AAMDNodes &AAInfo,
4876 const MDNode *Ranges) {
4877 SDValue Undef = getUNDEF(Ptr.getValueType());
4878 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4879 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4883 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4884 SDValue Chain, SDValue Ptr,
4885 MachineMemOperand *MMO) {
4886 SDValue Undef = getUNDEF(Ptr.getValueType());
4887 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4891 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4892 SDValue Chain, SDValue Ptr,
4893 MachinePointerInfo PtrInfo, EVT MemVT,
4894 bool isVolatile, bool isNonTemporal,
4895 bool isInvariant, unsigned Alignment,
4896 const AAMDNodes &AAInfo) {
4897 SDValue Undef = getUNDEF(Ptr.getValueType());
4898 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4899 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4904 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4905 SDValue Chain, SDValue Ptr, EVT MemVT,
4906 MachineMemOperand *MMO) {
4907 SDValue Undef = getUNDEF(Ptr.getValueType());
4908 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4913 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4914 SDValue Offset, ISD::MemIndexedMode AM) {
4915 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4916 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4917 "Load is already a indexed load!");
4918 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4919 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4920 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4921 false, LD->getAlignment());
4924 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4925 SDValue Ptr, MachinePointerInfo PtrInfo,
4926 bool isVolatile, bool isNonTemporal,
4927 unsigned Alignment, const AAMDNodes &AAInfo) {
4928 assert(Chain.getValueType() == MVT::Other &&
4929 "Invalid chain type");
4930 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4931 Alignment = getEVTAlignment(Val.getValueType());
4933 unsigned Flags = MachineMemOperand::MOStore;
4935 Flags |= MachineMemOperand::MOVolatile;
4937 Flags |= MachineMemOperand::MONonTemporal;
4939 if (PtrInfo.V.isNull())
4940 PtrInfo = InferPointerInfo(Ptr);
4942 MachineFunction &MF = getMachineFunction();
4943 MachineMemOperand *MMO =
4944 MF.getMachineMemOperand(PtrInfo, Flags,
4945 Val.getValueType().getStoreSize(), Alignment,
4948 return getStore(Chain, dl, Val, Ptr, MMO);
4951 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4952 SDValue Ptr, MachineMemOperand *MMO) {
4953 assert(Chain.getValueType() == MVT::Other &&
4954 "Invalid chain type");
4955 EVT VT = Val.getValueType();
4956 SDVTList VTs = getVTList(MVT::Other);
4957 SDValue Undef = getUNDEF(Ptr.getValueType());
4958 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4959 FoldingSetNodeID ID;
4960 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4961 ID.AddInteger(VT.getRawBits());
4962 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4963 MMO->isNonTemporal(), MMO->isInvariant()));
4964 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4966 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4967 cast<StoreSDNode>(E)->refineAlignment(MMO);
4968 return SDValue(E, 0);
4970 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4971 dl.getDebugLoc(), VTs,
4972 ISD::UNINDEXED, false, VT, MMO);
4973 CSEMap.InsertNode(N, IP);
4975 return SDValue(N, 0);
4978 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4979 SDValue Ptr, MachinePointerInfo PtrInfo,
4980 EVT SVT,bool isVolatile, bool isNonTemporal,
4982 const AAMDNodes &AAInfo) {
4983 assert(Chain.getValueType() == MVT::Other &&
4984 "Invalid chain type");
4985 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4986 Alignment = getEVTAlignment(SVT);
4988 unsigned Flags = MachineMemOperand::MOStore;
4990 Flags |= MachineMemOperand::MOVolatile;
4992 Flags |= MachineMemOperand::MONonTemporal;
4994 if (PtrInfo.V.isNull())
4995 PtrInfo = InferPointerInfo(Ptr);
4997 MachineFunction &MF = getMachineFunction();
4998 MachineMemOperand *MMO =
4999 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5002 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5005 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5006 SDValue Ptr, EVT SVT,
5007 MachineMemOperand *MMO) {
5008 EVT VT = Val.getValueType();
5010 assert(Chain.getValueType() == MVT::Other &&
5011 "Invalid chain type");
5013 return getStore(Chain, dl, Val, Ptr, MMO);
5015 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5016 "Should only be a truncating store, not extending!");
5017 assert(VT.isInteger() == SVT.isInteger() &&
5018 "Can't do FP-INT conversion!");
5019 assert(VT.isVector() == SVT.isVector() &&
5020 "Cannot use trunc store to convert to or from a vector!");
5021 assert((!VT.isVector() ||
5022 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5023 "Cannot use trunc store to change the number of vector elements!");
5025 SDVTList VTs = getVTList(MVT::Other);
5026 SDValue Undef = getUNDEF(Ptr.getValueType());
5027 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5028 FoldingSetNodeID ID;
5029 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5030 ID.AddInteger(SVT.getRawBits());
5031 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5032 MMO->isNonTemporal(), MMO->isInvariant()));
5033 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5035 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5036 cast<StoreSDNode>(E)->refineAlignment(MMO);
5037 return SDValue(E, 0);
5039 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5040 dl.getDebugLoc(), VTs,
5041 ISD::UNINDEXED, true, SVT, MMO);
5042 CSEMap.InsertNode(N, IP);
5044 return SDValue(N, 0);
5048 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5049 SDValue Offset, ISD::MemIndexedMode AM) {
5050 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5051 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5052 "Store is already a indexed store!");
5053 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5054 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5055 FoldingSetNodeID ID;
5056 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5057 ID.AddInteger(ST->getMemoryVT().getRawBits());
5058 ID.AddInteger(ST->getRawSubclassData());
5059 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5061 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5062 return SDValue(E, 0);
5064 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5065 dl.getDebugLoc(), VTs, AM,
5066 ST->isTruncatingStore(),
5068 ST->getMemOperand());
5069 CSEMap.InsertNode(N, IP);
5071 return SDValue(N, 0);
5075 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5076 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5077 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5079 SDVTList VTs = getVTList(VT, MVT::Other);
5080 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5081 FoldingSetNodeID ID;
5082 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5083 ID.AddInteger(VT.getRawBits());
5084 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5086 MMO->isNonTemporal(),
5087 MMO->isInvariant()));
5088 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5090 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5091 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5092 return SDValue(E, 0);
5094 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5095 dl.getDebugLoc(), Ops, 4, VTs,
5097 CSEMap.InsertNode(N, IP);
5099 return SDValue(N, 0);
5102 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5103 SDValue Ptr, SDValue Mask, EVT MemVT,
5104 MachineMemOperand *MMO, bool isTrunc) {
5105 assert(Chain.getValueType() == MVT::Other &&
5106 "Invalid chain type");
5107 EVT VT = Val.getValueType();
5108 SDVTList VTs = getVTList(MVT::Other);
5109 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5110 FoldingSetNodeID ID;
5111 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5112 ID.AddInteger(VT.getRawBits());
5113 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5114 MMO->isNonTemporal(), MMO->isInvariant()));
5115 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5117 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5118 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5119 return SDValue(E, 0);
5121 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5122 dl.getDebugLoc(), Ops, 4,
5123 VTs, isTrunc, MemVT, MMO);
5124 CSEMap.InsertNode(N, IP);
5126 return SDValue(N, 0);
5130 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5131 ArrayRef<SDValue> Ops,
5132 MachineMemOperand *MMO) {
5134 FoldingSetNodeID ID;
5135 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5136 ID.AddInteger(VT.getRawBits());
5137 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5139 MMO->isNonTemporal(),
5140 MMO->isInvariant()));
5141 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5143 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5144 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5145 return SDValue(E, 0);
5147 MaskedGatherSDNode *N =
5148 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5150 CSEMap.InsertNode(N, IP);
5152 return SDValue(N, 0);
5155 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5156 ArrayRef<SDValue> Ops,
5157 MachineMemOperand *MMO) {
5158 FoldingSetNodeID ID;
5159 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5160 ID.AddInteger(VT.getRawBits());
5161 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5162 MMO->isNonTemporal(),
5163 MMO->isInvariant()));
5164 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5166 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5167 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5168 return SDValue(E, 0);
5171 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5173 CSEMap.InsertNode(N, IP);
5175 return SDValue(N, 0);
5178 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5179 SDValue Chain, SDValue Ptr,
5182 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5183 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5186 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5187 ArrayRef<SDUse> Ops) {
5188 switch (Ops.size()) {
5189 case 0: return getNode(Opcode, DL, VT);
5190 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5191 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5192 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5196 // Copy from an SDUse array into an SDValue array for use with
5197 // the regular getNode logic.
5198 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5199 return getNode(Opcode, DL, VT, NewOps);
5202 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5203 ArrayRef<SDValue> Ops) {
5204 unsigned NumOps = Ops.size();
5206 case 0: return getNode(Opcode, DL, VT);
5207 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5208 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5209 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5215 case ISD::SELECT_CC: {
5216 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5217 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5218 "LHS and RHS of condition must have same type!");
5219 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5220 "True and False arms of SelectCC must have same type!");
5221 assert(Ops[2].getValueType() == VT &&
5222 "select_cc node must be of same type as true and false value!");
5226 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5227 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5228 "LHS/RHS of comparison should match types!");
5235 SDVTList VTs = getVTList(VT);
5237 if (VT != MVT::Glue) {
5238 FoldingSetNodeID ID;
5239 AddNodeIDNode(ID, Opcode, VTs, Ops);
5242 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5243 return SDValue(E, 0);
5245 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5247 CSEMap.InsertNode(N, IP);
5249 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5254 return SDValue(N, 0);
5257 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5258 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5259 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5262 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5263 ArrayRef<SDValue> Ops) {
5264 if (VTList.NumVTs == 1)
5265 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5269 // FIXME: figure out how to safely handle things like
5270 // int foo(int x) { return 1 << (x & 255); }
5271 // int bar() { return foo(256); }
5272 case ISD::SRA_PARTS:
5273 case ISD::SRL_PARTS:
5274 case ISD::SHL_PARTS:
5275 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5276 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5277 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5278 else if (N3.getOpcode() == ISD::AND)
5279 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5280 // If the and is only masking out bits that cannot effect the shift,
5281 // eliminate the and.
5282 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5283 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5284 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5290 // Memoize the node unless it returns a flag.
5292 unsigned NumOps = Ops.size();
5293 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5294 FoldingSetNodeID ID;
5295 AddNodeIDNode(ID, Opcode, VTList, Ops);
5297 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5298 return SDValue(E, 0);
5301 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5302 DL.getDebugLoc(), VTList, Ops[0]);
5303 } else if (NumOps == 2) {
5304 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5305 DL.getDebugLoc(), VTList, Ops[0],
5307 } else if (NumOps == 3) {
5308 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5309 DL.getDebugLoc(), VTList, Ops[0],
5312 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5315 CSEMap.InsertNode(N, IP);
5318 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5319 DL.getDebugLoc(), VTList, Ops[0]);
5320 } else if (NumOps == 2) {
5321 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5322 DL.getDebugLoc(), VTList, Ops[0],
5324 } else if (NumOps == 3) {
5325 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5326 DL.getDebugLoc(), VTList, Ops[0],
5329 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5334 return SDValue(N, 0);
5337 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5338 return getNode(Opcode, DL, VTList, None);
5341 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5343 SDValue Ops[] = { N1 };
5344 return getNode(Opcode, DL, VTList, Ops);
5347 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5348 SDValue N1, SDValue N2) {
5349 SDValue Ops[] = { N1, N2 };
5350 return getNode(Opcode, DL, VTList, Ops);
5353 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5354 SDValue N1, SDValue N2, SDValue N3) {
5355 SDValue Ops[] = { N1, N2, N3 };
5356 return getNode(Opcode, DL, VTList, Ops);
5359 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5360 SDValue N1, SDValue N2, SDValue N3,
5362 SDValue Ops[] = { N1, N2, N3, N4 };
5363 return getNode(Opcode, DL, VTList, Ops);
5366 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5367 SDValue N1, SDValue N2, SDValue N3,
5368 SDValue N4, SDValue N5) {
5369 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5370 return getNode(Opcode, DL, VTList, Ops);
5373 SDVTList SelectionDAG::getVTList(EVT VT) {
5374 return makeVTList(SDNode::getValueTypeList(VT), 1);
5377 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5378 FoldingSetNodeID ID;
5380 ID.AddInteger(VT1.getRawBits());
5381 ID.AddInteger(VT2.getRawBits());
5384 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5386 EVT *Array = Allocator.Allocate<EVT>(2);
5389 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5390 VTListMap.InsertNode(Result, IP);
5392 return Result->getSDVTList();
5395 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5396 FoldingSetNodeID ID;
5398 ID.AddInteger(VT1.getRawBits());
5399 ID.AddInteger(VT2.getRawBits());
5400 ID.AddInteger(VT3.getRawBits());
5403 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5405 EVT *Array = Allocator.Allocate<EVT>(3);
5409 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5410 VTListMap.InsertNode(Result, IP);
5412 return Result->getSDVTList();
5415 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5416 FoldingSetNodeID ID;
5418 ID.AddInteger(VT1.getRawBits());
5419 ID.AddInteger(VT2.getRawBits());
5420 ID.AddInteger(VT3.getRawBits());
5421 ID.AddInteger(VT4.getRawBits());
5424 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5426 EVT *Array = Allocator.Allocate<EVT>(4);
5431 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5432 VTListMap.InsertNode(Result, IP);
5434 return Result->getSDVTList();
5437 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5438 unsigned NumVTs = VTs.size();
5439 FoldingSetNodeID ID;
5440 ID.AddInteger(NumVTs);
5441 for (unsigned index = 0; index < NumVTs; index++) {
5442 ID.AddInteger(VTs[index].getRawBits());
5446 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5448 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5449 std::copy(VTs.begin(), VTs.end(), Array);
5450 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5451 VTListMap.InsertNode(Result, IP);
5453 return Result->getSDVTList();
5457 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5458 /// specified operands. If the resultant node already exists in the DAG,
5459 /// this does not modify the specified node, instead it returns the node that
5460 /// already exists. If the resultant node does not exist in the DAG, the
5461 /// input node is returned. As a degenerate case, if you specify the same
5462 /// input operands as the node already has, the input node is returned.
5463 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5464 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5466 // Check to see if there is no change.
5467 if (Op == N->getOperand(0)) return N;
5469 // See if the modified node already exists.
5470 void *InsertPos = nullptr;
5471 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5474 // Nope it doesn't. Remove the node from its current place in the maps.
5476 if (!RemoveNodeFromCSEMaps(N))
5477 InsertPos = nullptr;
5479 // Now we update the operands.
5480 N->OperandList[0].set(Op);
5482 // If this gets put into a CSE map, add it.
5483 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5487 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5488 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5490 // Check to see if there is no change.
5491 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5492 return N; // No operands changed, just return the input node.
5494 // See if the modified node already exists.
5495 void *InsertPos = nullptr;
5496 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5499 // Nope it doesn't. Remove the node from its current place in the maps.
5501 if (!RemoveNodeFromCSEMaps(N))
5502 InsertPos = nullptr;
5504 // Now we update the operands.
5505 if (N->OperandList[0] != Op1)
5506 N->OperandList[0].set(Op1);
5507 if (N->OperandList[1] != Op2)
5508 N->OperandList[1].set(Op2);
5510 // If this gets put into a CSE map, add it.
5511 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5515 SDNode *SelectionDAG::
5516 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5517 SDValue Ops[] = { Op1, Op2, Op3 };
5518 return UpdateNodeOperands(N, Ops);
5521 SDNode *SelectionDAG::
5522 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5523 SDValue Op3, SDValue Op4) {
5524 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5525 return UpdateNodeOperands(N, Ops);
5528 SDNode *SelectionDAG::
5529 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5530 SDValue Op3, SDValue Op4, SDValue Op5) {
5531 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5532 return UpdateNodeOperands(N, Ops);
5535 SDNode *SelectionDAG::
5536 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5537 unsigned NumOps = Ops.size();
5538 assert(N->getNumOperands() == NumOps &&
5539 "Update with wrong number of operands");
5541 // If no operands changed just return the input node.
5542 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5545 // See if the modified node already exists.
5546 void *InsertPos = nullptr;
5547 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5550 // Nope it doesn't. Remove the node from its current place in the maps.
5552 if (!RemoveNodeFromCSEMaps(N))
5553 InsertPos = nullptr;
5555 // Now we update the operands.
5556 for (unsigned i = 0; i != NumOps; ++i)
5557 if (N->OperandList[i] != Ops[i])
5558 N->OperandList[i].set(Ops[i]);
5560 // If this gets put into a CSE map, add it.
5561 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5565 /// DropOperands - Release the operands and set this node to have
5567 void SDNode::DropOperands() {
5568 // Unlike the code in MorphNodeTo that does this, we don't need to
5569 // watch for dead nodes here.
5570 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5576 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5579 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5581 SDVTList VTs = getVTList(VT);
5582 return SelectNodeTo(N, MachineOpc, VTs, None);
5585 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5586 EVT VT, SDValue Op1) {
5587 SDVTList VTs = getVTList(VT);
5588 SDValue Ops[] = { Op1 };
5589 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5592 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5593 EVT VT, SDValue Op1,
5595 SDVTList VTs = getVTList(VT);
5596 SDValue Ops[] = { Op1, Op2 };
5597 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5600 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5601 EVT VT, SDValue Op1,
5602 SDValue Op2, SDValue Op3) {
5603 SDVTList VTs = getVTList(VT);
5604 SDValue Ops[] = { Op1, Op2, Op3 };
5605 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5608 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5609 EVT VT, ArrayRef<SDValue> Ops) {
5610 SDVTList VTs = getVTList(VT);
5611 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5614 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5615 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5616 SDVTList VTs = getVTList(VT1, VT2);
5617 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5620 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5622 SDVTList VTs = getVTList(VT1, VT2);
5623 return SelectNodeTo(N, MachineOpc, VTs, None);
5626 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5627 EVT VT1, EVT VT2, EVT VT3,
5628 ArrayRef<SDValue> Ops) {
5629 SDVTList VTs = getVTList(VT1, VT2, VT3);
5630 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5633 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5634 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5635 ArrayRef<SDValue> Ops) {
5636 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5637 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5640 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5643 SDVTList VTs = getVTList(VT1, VT2);
5644 SDValue Ops[] = { Op1 };
5645 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5648 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5650 SDValue Op1, SDValue Op2) {
5651 SDVTList VTs = getVTList(VT1, VT2);
5652 SDValue Ops[] = { Op1, Op2 };
5653 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5656 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5658 SDValue Op1, SDValue Op2,
5660 SDVTList VTs = getVTList(VT1, VT2);
5661 SDValue Ops[] = { Op1, Op2, Op3 };
5662 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5665 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5666 EVT VT1, EVT VT2, EVT VT3,
5667 SDValue Op1, SDValue Op2,
5669 SDVTList VTs = getVTList(VT1, VT2, VT3);
5670 SDValue Ops[] = { Op1, Op2, Op3 };
5671 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5674 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5675 SDVTList VTs,ArrayRef<SDValue> Ops) {
5676 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5677 // Reset the NodeID to -1.
5682 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5683 /// the line number information on the merged node since it is not possible to
5684 /// preserve the information that operation is associated with multiple lines.
5685 /// This will make the debugger working better at -O0, were there is a higher
5686 /// probability having other instructions associated with that line.
5688 /// For IROrder, we keep the smaller of the two
5689 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5690 DebugLoc NLoc = N->getDebugLoc();
5691 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5692 N->setDebugLoc(DebugLoc());
5694 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5695 N->setIROrder(Order);
5699 /// MorphNodeTo - This *mutates* the specified node to have the specified
5700 /// return type, opcode, and operands.
5702 /// Note that MorphNodeTo returns the resultant node. If there is already a
5703 /// node of the specified opcode and operands, it returns that node instead of
5704 /// the current one. Note that the SDLoc need not be the same.
5706 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5707 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5708 /// node, and because it doesn't require CSE recalculation for any of
5709 /// the node's users.
5711 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5712 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5713 /// the legalizer which maintain worklists that would need to be updated when
5714 /// deleting things.
5715 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5716 SDVTList VTs, ArrayRef<SDValue> Ops) {
5717 unsigned NumOps = Ops.size();
5718 // If an identical node already exists, use it.
5720 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5721 FoldingSetNodeID ID;
5722 AddNodeIDNode(ID, Opc, VTs, Ops);
5723 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5724 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5727 if (!RemoveNodeFromCSEMaps(N))
5730 // Start the morphing.
5732 N->ValueList = VTs.VTs;
5733 N->NumValues = VTs.NumVTs;
5735 // Clear the operands list, updating used nodes to remove this from their
5736 // use list. Keep track of any operands that become dead as a result.
5737 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5738 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5740 SDNode *Used = Use.getNode();
5742 if (Used->use_empty())
5743 DeadNodeSet.insert(Used);
5746 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5747 // Initialize the memory references information.
5748 MN->setMemRefs(nullptr, nullptr);
5749 // If NumOps is larger than the # of operands we can have in a
5750 // MachineSDNode, reallocate the operand list.
5751 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5752 if (MN->OperandsNeedDelete)
5753 delete[] MN->OperandList;
5754 if (NumOps > array_lengthof(MN->LocalOperands))
5755 // We're creating a final node that will live unmorphed for the
5756 // remainder of the current SelectionDAG iteration, so we can allocate
5757 // the operands directly out of a pool with no recycling metadata.
5758 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5759 Ops.data(), NumOps);
5761 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5762 MN->OperandsNeedDelete = false;
5764 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5766 // If NumOps is larger than the # of operands we currently have, reallocate
5767 // the operand list.
5768 if (NumOps > N->NumOperands) {
5769 if (N->OperandsNeedDelete)
5770 delete[] N->OperandList;
5771 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5772 N->OperandsNeedDelete = true;
5774 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5777 // Delete any nodes that are still dead after adding the uses for the
5779 if (!DeadNodeSet.empty()) {
5780 SmallVector<SDNode *, 16> DeadNodes;
5781 for (SDNode *N : DeadNodeSet)
5783 DeadNodes.push_back(N);
5784 RemoveDeadNodes(DeadNodes);
5788 CSEMap.InsertNode(N, IP); // Memoize the new node.
5793 /// getMachineNode - These are used for target selectors to create a new node
5794 /// with specified return type(s), MachineInstr opcode, and operands.
5796 /// Note that getMachineNode returns the resultant node. If there is already a
5797 /// node of the specified opcode and operands, it returns that node instead of
5798 /// the current one.
5800 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5801 SDVTList VTs = getVTList(VT);
5802 return getMachineNode(Opcode, dl, VTs, None);
5806 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5807 SDVTList VTs = getVTList(VT);
5808 SDValue Ops[] = { Op1 };
5809 return getMachineNode(Opcode, dl, VTs, Ops);
5813 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5814 SDValue Op1, SDValue Op2) {
5815 SDVTList VTs = getVTList(VT);
5816 SDValue Ops[] = { Op1, Op2 };
5817 return getMachineNode(Opcode, dl, VTs, Ops);
5821 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5822 SDValue Op1, SDValue Op2, SDValue Op3) {
5823 SDVTList VTs = getVTList(VT);
5824 SDValue Ops[] = { Op1, Op2, Op3 };
5825 return getMachineNode(Opcode, dl, VTs, Ops);
5829 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5830 ArrayRef<SDValue> Ops) {
5831 SDVTList VTs = getVTList(VT);
5832 return getMachineNode(Opcode, dl, VTs, Ops);
5836 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5837 SDVTList VTs = getVTList(VT1, VT2);
5838 return getMachineNode(Opcode, dl, VTs, None);
5842 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5843 EVT VT1, EVT VT2, SDValue Op1) {
5844 SDVTList VTs = getVTList(VT1, VT2);
5845 SDValue Ops[] = { Op1 };
5846 return getMachineNode(Opcode, dl, VTs, Ops);
5850 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5851 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5852 SDVTList VTs = getVTList(VT1, VT2);
5853 SDValue Ops[] = { Op1, Op2 };
5854 return getMachineNode(Opcode, dl, VTs, Ops);
5858 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5859 EVT VT1, EVT VT2, SDValue Op1,
5860 SDValue Op2, SDValue Op3) {
5861 SDVTList VTs = getVTList(VT1, VT2);
5862 SDValue Ops[] = { Op1, Op2, Op3 };
5863 return getMachineNode(Opcode, dl, VTs, Ops);
5867 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5869 ArrayRef<SDValue> Ops) {
5870 SDVTList VTs = getVTList(VT1, VT2);
5871 return getMachineNode(Opcode, dl, VTs, Ops);
5875 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5876 EVT VT1, EVT VT2, EVT VT3,
5877 SDValue Op1, SDValue Op2) {
5878 SDVTList VTs = getVTList(VT1, VT2, VT3);
5879 SDValue Ops[] = { Op1, Op2 };
5880 return getMachineNode(Opcode, dl, VTs, Ops);
5884 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5885 EVT VT1, EVT VT2, EVT VT3,
5886 SDValue Op1, SDValue Op2, SDValue Op3) {
5887 SDVTList VTs = getVTList(VT1, VT2, VT3);
5888 SDValue Ops[] = { Op1, Op2, Op3 };
5889 return getMachineNode(Opcode, dl, VTs, Ops);
5893 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5894 EVT VT1, EVT VT2, EVT VT3,
5895 ArrayRef<SDValue> Ops) {
5896 SDVTList VTs = getVTList(VT1, VT2, VT3);
5897 return getMachineNode(Opcode, dl, VTs, Ops);
5901 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5902 EVT VT2, EVT VT3, EVT VT4,
5903 ArrayRef<SDValue> Ops) {
5904 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5905 return getMachineNode(Opcode, dl, VTs, Ops);
5909 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5910 ArrayRef<EVT> ResultTys,
5911 ArrayRef<SDValue> Ops) {
5912 SDVTList VTs = getVTList(ResultTys);
5913 return getMachineNode(Opcode, dl, VTs, Ops);
5917 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5918 ArrayRef<SDValue> OpsArray) {
5919 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5922 const SDValue *Ops = OpsArray.data();
5923 unsigned NumOps = OpsArray.size();
5926 FoldingSetNodeID ID;
5927 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5929 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5930 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5934 // Allocate a new MachineSDNode.
5935 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5936 DL.getDebugLoc(), VTs);
5938 // Initialize the operands list.
5939 if (NumOps > array_lengthof(N->LocalOperands))
5940 // We're creating a final node that will live unmorphed for the
5941 // remainder of the current SelectionDAG iteration, so we can allocate
5942 // the operands directly out of a pool with no recycling metadata.
5943 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5946 N->InitOperands(N->LocalOperands, Ops, NumOps);
5947 N->OperandsNeedDelete = false;
5950 CSEMap.InsertNode(N, IP);
5956 /// getTargetExtractSubreg - A convenience function for creating
5957 /// TargetOpcode::EXTRACT_SUBREG nodes.
5959 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5961 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5962 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5963 VT, Operand, SRIdxVal);
5964 return SDValue(Subreg, 0);
5967 /// getTargetInsertSubreg - A convenience function for creating
5968 /// TargetOpcode::INSERT_SUBREG nodes.
5970 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5971 SDValue Operand, SDValue Subreg) {
5972 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5973 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5974 VT, Operand, Subreg, SRIdxVal);
5975 return SDValue(Result, 0);
5978 /// getNodeIfExists - Get the specified node if it's already available, or
5979 /// else return NULL.
5980 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5981 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5983 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5984 FoldingSetNodeID ID;
5985 AddNodeIDNode(ID, Opcode, VTList, Ops);
5986 if (isBinOpWithFlags(Opcode))
5987 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5989 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5995 /// getDbgValue - Creates a SDDbgValue node.
5998 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5999 unsigned R, bool IsIndirect, uint64_t Off,
6000 DebugLoc DL, unsigned O) {
6001 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6002 "Expected inlined-at fields to agree");
6003 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6007 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6008 const Value *C, uint64_t Off,
6009 DebugLoc DL, unsigned O) {
6010 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6011 "Expected inlined-at fields to agree");
6012 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6016 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6017 unsigned FI, uint64_t Off,
6018 DebugLoc DL, unsigned O) {
6019 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6020 "Expected inlined-at fields to agree");
6021 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6026 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6027 /// pointed to by a use iterator is deleted, increment the use iterator
6028 /// so that it doesn't dangle.
6030 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6031 SDNode::use_iterator &UI;
6032 SDNode::use_iterator &UE;
6034 void NodeDeleted(SDNode *N, SDNode *E) override {
6035 // Increment the iterator as needed.
6036 while (UI != UE && N == *UI)
6041 RAUWUpdateListener(SelectionDAG &d,
6042 SDNode::use_iterator &ui,
6043 SDNode::use_iterator &ue)
6044 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6049 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6050 /// This can cause recursive merging of nodes in the DAG.
6052 /// This version assumes From has a single result value.
6054 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6055 SDNode *From = FromN.getNode();
6056 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6057 "Cannot replace with this method!");
6058 assert(From != To.getNode() && "Cannot replace uses of with self");
6060 // Iterate over all the existing uses of From. New uses will be added
6061 // to the beginning of the use list, which we avoid visiting.
6062 // This specifically avoids visiting uses of From that arise while the
6063 // replacement is happening, because any such uses would be the result
6064 // of CSE: If an existing node looks like From after one of its operands
6065 // is replaced by To, we don't want to replace of all its users with To
6066 // too. See PR3018 for more info.
6067 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6068 RAUWUpdateListener Listener(*this, UI, UE);
6072 // This node is about to morph, remove its old self from the CSE maps.
6073 RemoveNodeFromCSEMaps(User);
6075 // A user can appear in a use list multiple times, and when this
6076 // happens the uses are usually next to each other in the list.
6077 // To help reduce the number of CSE recomputations, process all
6078 // the uses of this user that we can find this way.
6080 SDUse &Use = UI.getUse();
6083 } while (UI != UE && *UI == User);
6085 // Now that we have modified User, add it back to the CSE maps. If it
6086 // already exists there, recursively merge the results together.
6087 AddModifiedNodeToCSEMaps(User);
6090 // If we just RAUW'd the root, take note.
6091 if (FromN == getRoot())
6095 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6096 /// This can cause recursive merging of nodes in the DAG.
6098 /// This version assumes that for each value of From, there is a
6099 /// corresponding value in To in the same position with the same type.
6101 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6103 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6104 assert((!From->hasAnyUseOfValue(i) ||
6105 From->getValueType(i) == To->getValueType(i)) &&
6106 "Cannot use this version of ReplaceAllUsesWith!");
6109 // Handle the trivial case.
6113 // Iterate over just the existing users of From. See the comments in
6114 // the ReplaceAllUsesWith above.
6115 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6116 RAUWUpdateListener Listener(*this, UI, UE);
6120 // This node is about to morph, remove its old self from the CSE maps.
6121 RemoveNodeFromCSEMaps(User);
6123 // A user can appear in a use list multiple times, and when this
6124 // happens the uses are usually next to each other in the list.
6125 // To help reduce the number of CSE recomputations, process all
6126 // the uses of this user that we can find this way.
6128 SDUse &Use = UI.getUse();
6131 } while (UI != UE && *UI == User);
6133 // Now that we have modified User, add it back to the CSE maps. If it
6134 // already exists there, recursively merge the results together.
6135 AddModifiedNodeToCSEMaps(User);
6138 // If we just RAUW'd the root, take note.
6139 if (From == getRoot().getNode())
6140 setRoot(SDValue(To, getRoot().getResNo()));
6143 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6144 /// This can cause recursive merging of nodes in the DAG.
6146 /// This version can replace From with any result values. To must match the
6147 /// number and types of values returned by From.
6148 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6149 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6150 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6152 // Iterate over just the existing users of From. See the comments in
6153 // the ReplaceAllUsesWith above.
6154 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6155 RAUWUpdateListener Listener(*this, UI, UE);
6159 // This node is about to morph, remove its old self from the CSE maps.
6160 RemoveNodeFromCSEMaps(User);
6162 // A user can appear in a use list multiple times, and when this
6163 // happens the uses are usually next to each other in the list.
6164 // To help reduce the number of CSE recomputations, process all
6165 // the uses of this user that we can find this way.
6167 SDUse &Use = UI.getUse();
6168 const SDValue &ToOp = To[Use.getResNo()];
6171 } while (UI != UE && *UI == User);
6173 // Now that we have modified User, add it back to the CSE maps. If it
6174 // already exists there, recursively merge the results together.
6175 AddModifiedNodeToCSEMaps(User);
6178 // If we just RAUW'd the root, take note.
6179 if (From == getRoot().getNode())
6180 setRoot(SDValue(To[getRoot().getResNo()]));
6183 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6184 /// uses of other values produced by From.getNode() alone. The Deleted
6185 /// vector is handled the same way as for ReplaceAllUsesWith.
6186 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6187 // Handle the really simple, really trivial case efficiently.
6188 if (From == To) return;
6190 // Handle the simple, trivial, case efficiently.
6191 if (From.getNode()->getNumValues() == 1) {
6192 ReplaceAllUsesWith(From, To);
6196 // Iterate over just the existing users of From. See the comments in
6197 // the ReplaceAllUsesWith above.
6198 SDNode::use_iterator UI = From.getNode()->use_begin(),
6199 UE = From.getNode()->use_end();
6200 RAUWUpdateListener Listener(*this, UI, UE);
6203 bool UserRemovedFromCSEMaps = false;
6205 // A user can appear in a use list multiple times, and when this
6206 // happens the uses are usually next to each other in the list.
6207 // To help reduce the number of CSE recomputations, process all
6208 // the uses of this user that we can find this way.
6210 SDUse &Use = UI.getUse();
6212 // Skip uses of different values from the same node.
6213 if (Use.getResNo() != From.getResNo()) {
6218 // If this node hasn't been modified yet, it's still in the CSE maps,
6219 // so remove its old self from the CSE maps.
6220 if (!UserRemovedFromCSEMaps) {
6221 RemoveNodeFromCSEMaps(User);
6222 UserRemovedFromCSEMaps = true;
6227 } while (UI != UE && *UI == User);
6229 // We are iterating over all uses of the From node, so if a use
6230 // doesn't use the specific value, no changes are made.
6231 if (!UserRemovedFromCSEMaps)
6234 // Now that we have modified User, add it back to the CSE maps. If it
6235 // already exists there, recursively merge the results together.
6236 AddModifiedNodeToCSEMaps(User);
6239 // If we just RAUW'd the root, take note.
6240 if (From == getRoot())
6245 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6246 /// to record information about a use.
6253 /// operator< - Sort Memos by User.
6254 bool operator<(const UseMemo &L, const UseMemo &R) {
6255 return (intptr_t)L.User < (intptr_t)R.User;
6259 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6260 /// uses of other values produced by From.getNode() alone. The same value
6261 /// may appear in both the From and To list. The Deleted vector is
6262 /// handled the same way as for ReplaceAllUsesWith.
6263 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6266 // Handle the simple, trivial case efficiently.
6268 return ReplaceAllUsesOfValueWith(*From, *To);
6270 // Read up all the uses and make records of them. This helps
6271 // processing new uses that are introduced during the
6272 // replacement process.
6273 SmallVector<UseMemo, 4> Uses;
6274 for (unsigned i = 0; i != Num; ++i) {
6275 unsigned FromResNo = From[i].getResNo();
6276 SDNode *FromNode = From[i].getNode();
6277 for (SDNode::use_iterator UI = FromNode->use_begin(),
6278 E = FromNode->use_end(); UI != E; ++UI) {
6279 SDUse &Use = UI.getUse();
6280 if (Use.getResNo() == FromResNo) {
6281 UseMemo Memo = { *UI, i, &Use };
6282 Uses.push_back(Memo);
6287 // Sort the uses, so that all the uses from a given User are together.
6288 std::sort(Uses.begin(), Uses.end());
6290 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6291 UseIndex != UseIndexEnd; ) {
6292 // We know that this user uses some value of From. If it is the right
6293 // value, update it.
6294 SDNode *User = Uses[UseIndex].User;
6296 // This node is about to morph, remove its old self from the CSE maps.
6297 RemoveNodeFromCSEMaps(User);
6299 // The Uses array is sorted, so all the uses for a given User
6300 // are next to each other in the list.
6301 // To help reduce the number of CSE recomputations, process all
6302 // the uses of this user that we can find this way.
6304 unsigned i = Uses[UseIndex].Index;
6305 SDUse &Use = *Uses[UseIndex].Use;
6309 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6311 // Now that we have modified User, add it back to the CSE maps. If it
6312 // already exists there, recursively merge the results together.
6313 AddModifiedNodeToCSEMaps(User);
6317 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6318 /// based on their topological order. It returns the maximum id and a vector
6319 /// of the SDNodes* in assigned order by reference.
6320 unsigned SelectionDAG::AssignTopologicalOrder() {
6322 unsigned DAGSize = 0;
6324 // SortedPos tracks the progress of the algorithm. Nodes before it are
6325 // sorted, nodes after it are unsorted. When the algorithm completes
6326 // it is at the end of the list.
6327 allnodes_iterator SortedPos = allnodes_begin();
6329 // Visit all the nodes. Move nodes with no operands to the front of
6330 // the list immediately. Annotate nodes that do have operands with their
6331 // operand count. Before we do this, the Node Id fields of the nodes
6332 // may contain arbitrary values. After, the Node Id fields for nodes
6333 // before SortedPos will contain the topological sort index, and the
6334 // Node Id fields for nodes At SortedPos and after will contain the
6335 // count of outstanding operands.
6336 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6338 checkForCycles(N, this);
6339 unsigned Degree = N->getNumOperands();
6341 // A node with no uses, add it to the result array immediately.
6342 N->setNodeId(DAGSize++);
6343 allnodes_iterator Q = N;
6345 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6346 assert(SortedPos != AllNodes.end() && "Overran node list");
6349 // Temporarily use the Node Id as scratch space for the degree count.
6350 N->setNodeId(Degree);
6354 // Visit all the nodes. As we iterate, move nodes into sorted order,
6355 // such that by the time the end is reached all nodes will be sorted.
6356 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6358 checkForCycles(N, this);
6359 // N is in sorted position, so all its uses have one less operand
6360 // that needs to be sorted.
6361 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6364 unsigned Degree = P->getNodeId();
6365 assert(Degree != 0 && "Invalid node degree");
6368 // All of P's operands are sorted, so P may sorted now.
6369 P->setNodeId(DAGSize++);
6371 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6372 assert(SortedPos != AllNodes.end() && "Overran node list");
6375 // Update P's outstanding operand count.
6376 P->setNodeId(Degree);
6379 if (I == SortedPos) {
6382 dbgs() << "Overran sorted position:\n";
6383 S->dumprFull(this); dbgs() << "\n";
6384 dbgs() << "Checking if this is due to cycles\n";
6385 checkForCycles(this, true);
6387 llvm_unreachable(nullptr);
6391 assert(SortedPos == AllNodes.end() &&
6392 "Topological sort incomplete!");
6393 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6394 "First node in topological sort is not the entry token!");
6395 assert(AllNodes.front().getNodeId() == 0 &&
6396 "First node in topological sort has non-zero id!");
6397 assert(AllNodes.front().getNumOperands() == 0 &&
6398 "First node in topological sort has operands!");
6399 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6400 "Last node in topologic sort has unexpected id!");
6401 assert(AllNodes.back().use_empty() &&
6402 "Last node in topologic sort has users!");
6403 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6407 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6408 /// value is produced by SD.
6409 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6411 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6412 SD->setHasDebugValue(true);
6414 DbgInfo->add(DB, SD, isParameter);
6417 /// TransferDbgValues - Transfer SDDbgValues.
6418 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6419 if (From == To || !From.getNode()->getHasDebugValue())
6421 SDNode *FromNode = From.getNode();
6422 SDNode *ToNode = To.getNode();
6423 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6424 SmallVector<SDDbgValue *, 2> ClonedDVs;
6425 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6427 SDDbgValue *Dbg = *I;
6428 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6430 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6431 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6432 Dbg->getDebugLoc(), Dbg->getOrder());
6433 ClonedDVs.push_back(Clone);
6436 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6437 E = ClonedDVs.end(); I != E; ++I)
6438 AddDbgValue(*I, ToNode, false);
6441 //===----------------------------------------------------------------------===//
6443 //===----------------------------------------------------------------------===//
6445 HandleSDNode::~HandleSDNode() {
6449 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6450 DebugLoc DL, const GlobalValue *GA,
6451 EVT VT, int64_t o, unsigned char TF)
6452 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6456 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6457 SDValue X, unsigned SrcAS,
6459 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6460 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6462 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6463 EVT memvt, MachineMemOperand *mmo)
6464 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6465 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6466 MMO->isNonTemporal(), MMO->isInvariant());
6467 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6468 assert(isNonTemporal() == MMO->isNonTemporal() &&
6469 "Non-temporal encoding error!");
6470 // We check here that the size of the memory operand fits within the size of
6471 // the MMO. This is because the MMO might indicate only a possible address
6472 // range instead of specifying the affected memory addresses precisely.
6473 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6476 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6477 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6478 : SDNode(Opc, Order, dl, VTs, Ops),
6479 MemoryVT(memvt), MMO(mmo) {
6480 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6481 MMO->isNonTemporal(), MMO->isInvariant());
6482 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6483 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6486 /// Profile - Gather unique data for the node.
6488 void SDNode::Profile(FoldingSetNodeID &ID) const {
6489 AddNodeIDNode(ID, this);
6494 std::vector<EVT> VTs;
6497 VTs.reserve(MVT::LAST_VALUETYPE);
6498 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6499 VTs.push_back(MVT((MVT::SimpleValueType)i));
6504 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6505 static ManagedStatic<EVTArray> SimpleVTArray;
6506 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6508 /// getValueTypeList - Return a pointer to the specified value type.
6510 const EVT *SDNode::getValueTypeList(EVT VT) {
6511 if (VT.isExtended()) {
6512 sys::SmartScopedLock<true> Lock(*VTMutex);
6513 return &(*EVTs->insert(VT).first);
6515 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6516 "Value type out of range!");
6517 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6521 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6522 /// indicated value. This method ignores uses of other values defined by this
6524 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6525 assert(Value < getNumValues() && "Bad value!");
6527 // TODO: Only iterate over uses of a given value of the node
6528 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6529 if (UI.getUse().getResNo() == Value) {
6536 // Found exactly the right number of uses?
6541 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6542 /// value. This method ignores uses of other values defined by this operation.
6543 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6544 assert(Value < getNumValues() && "Bad value!");
6546 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6547 if (UI.getUse().getResNo() == Value)
6554 /// isOnlyUserOf - Return true if this node is the only use of N.
6556 bool SDNode::isOnlyUserOf(SDNode *N) const {
6558 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6569 /// isOperand - Return true if this node is an operand of N.
6571 bool SDValue::isOperandOf(SDNode *N) const {
6572 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6573 if (*this == N->getOperand(i))
6578 bool SDNode::isOperandOf(SDNode *N) const {
6579 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6580 if (this == N->OperandList[i].getNode())
6585 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6586 /// be a chain) reaches the specified operand without crossing any
6587 /// side-effecting instructions on any chain path. In practice, this looks
6588 /// through token factors and non-volatile loads. In order to remain efficient,
6589 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6590 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6591 unsigned Depth) const {
6592 if (*this == Dest) return true;
6594 // Don't search too deeply, we just want to be able to see through
6595 // TokenFactor's etc.
6596 if (Depth == 0) return false;
6598 // If this is a token factor, all inputs to the TF happen in parallel. If any
6599 // of the operands of the TF does not reach dest, then we cannot do the xform.
6600 if (getOpcode() == ISD::TokenFactor) {
6601 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6602 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6607 // Loads don't have side effects, look through them.
6608 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6609 if (!Ld->isVolatile())
6610 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6615 /// hasPredecessor - Return true if N is a predecessor of this node.
6616 /// N is either an operand of this node, or can be reached by recursively
6617 /// traversing up the operands.
6618 /// NOTE: This is an expensive method. Use it carefully.
6619 bool SDNode::hasPredecessor(const SDNode *N) const {
6620 SmallPtrSet<const SDNode *, 32> Visited;
6621 SmallVector<const SDNode *, 16> Worklist;
6622 return hasPredecessorHelper(N, Visited, Worklist);
6626 SDNode::hasPredecessorHelper(const SDNode *N,
6627 SmallPtrSetImpl<const SDNode *> &Visited,
6628 SmallVectorImpl<const SDNode *> &Worklist) const {
6629 if (Visited.empty()) {
6630 Worklist.push_back(this);
6632 // Take a look in the visited set. If we've already encountered this node
6633 // we needn't search further.
6634 if (Visited.count(N))
6638 // Haven't visited N yet. Continue the search.
6639 while (!Worklist.empty()) {
6640 const SDNode *M = Worklist.pop_back_val();
6641 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6642 SDNode *Op = M->getOperand(i).getNode();
6643 if (Visited.insert(Op).second)
6644 Worklist.push_back(Op);
6653 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6654 assert(Num < NumOperands && "Invalid child # of SDNode!");
6655 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6658 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6659 assert(N->getNumValues() == 1 &&
6660 "Can't unroll a vector with multiple results!");
6662 EVT VT = N->getValueType(0);
6663 unsigned NE = VT.getVectorNumElements();
6664 EVT EltVT = VT.getVectorElementType();
6667 SmallVector<SDValue, 8> Scalars;
6668 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6670 // If ResNE is 0, fully unroll the vector op.
6673 else if (NE > ResNE)
6677 for (i= 0; i != NE; ++i) {
6678 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6679 SDValue Operand = N->getOperand(j);
6680 EVT OperandVT = Operand.getValueType();
6681 if (OperandVT.isVector()) {
6682 // A vector operand; extract a single element.
6683 EVT OperandEltVT = OperandVT.getVectorElementType();
6684 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6687 getConstant(i, dl, TLI->getVectorIdxTy()));
6689 // A scalar operand; just use it as is.
6690 Operands[j] = Operand;
6694 switch (N->getOpcode()) {
6696 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6699 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6706 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6707 getShiftAmountOperand(Operands[0].getValueType(),
6710 case ISD::SIGN_EXTEND_INREG:
6711 case ISD::FP_ROUND_INREG: {
6712 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6713 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6715 getValueType(ExtVT)));
6720 for (; i < ResNE; ++i)
6721 Scalars.push_back(getUNDEF(EltVT));
6723 return getNode(ISD::BUILD_VECTOR, dl,
6724 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6728 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6729 /// location that is 'Dist' units away from the location that the 'Base' load
6730 /// is loading from.
6731 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6732 unsigned Bytes, int Dist) const {
6733 if (LD->getChain() != Base->getChain())
6735 EVT VT = LD->getValueType(0);
6736 if (VT.getSizeInBits() / 8 != Bytes)
6739 SDValue Loc = LD->getOperand(1);
6740 SDValue BaseLoc = Base->getOperand(1);
6741 if (Loc.getOpcode() == ISD::FrameIndex) {
6742 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6744 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6745 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6746 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6747 int FS = MFI->getObjectSize(FI);
6748 int BFS = MFI->getObjectSize(BFI);
6749 if (FS != BFS || FS != (int)Bytes) return false;
6750 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6754 if (isBaseWithConstantOffset(Loc)) {
6755 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6756 if (Loc.getOperand(0) == BaseLoc) {
6757 // If the base location is a simple address with no offset itself, then
6758 // the second load's first add operand should be the base address.
6759 if (LocOffset == Dist * (int)Bytes)
6761 } else if (isBaseWithConstantOffset(BaseLoc)) {
6762 // The base location itself has an offset, so subtract that value from the
6763 // second load's offset before comparing to distance * size.
6765 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6766 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6767 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6772 const GlobalValue *GV1 = nullptr;
6773 const GlobalValue *GV2 = nullptr;
6774 int64_t Offset1 = 0;
6775 int64_t Offset2 = 0;
6776 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6777 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6778 if (isGA1 && isGA2 && GV1 == GV2)
6779 return Offset1 == (Offset2 + Dist*Bytes);
6784 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6785 /// it cannot be inferred.
6786 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6787 // If this is a GlobalAddress + cst, return the alignment.
6788 const GlobalValue *GV;
6789 int64_t GVOffset = 0;
6790 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6791 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6792 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6793 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6794 *TLI->getDataLayout());
6795 unsigned AlignBits = KnownZero.countTrailingOnes();
6796 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6798 return MinAlign(Align, GVOffset);
6801 // If this is a direct reference to a stack slot, use information about the
6802 // stack slot's alignment.
6803 int FrameIdx = 1 << 31;
6804 int64_t FrameOffset = 0;
6805 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6806 FrameIdx = FI->getIndex();
6807 } else if (isBaseWithConstantOffset(Ptr) &&
6808 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6810 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6811 FrameOffset = Ptr.getConstantOperandVal(1);
6814 if (FrameIdx != (1 << 31)) {
6815 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6816 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6824 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6825 /// which is split (or expanded) into two not necessarily identical pieces.
6826 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6827 // Currently all types are split in half.
6829 if (!VT.isVector()) {
6830 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6832 unsigned NumElements = VT.getVectorNumElements();
6833 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6834 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6837 return std::make_pair(LoVT, HiVT);
6840 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6842 std::pair<SDValue, SDValue>
6843 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6845 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6846 N.getValueType().getVectorNumElements() &&
6847 "More vector elements requested than available!");
6849 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6850 getConstant(0, DL, TLI->getVectorIdxTy()));
6851 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6852 getConstant(LoVT.getVectorNumElements(), DL,
6853 TLI->getVectorIdxTy()));
6854 return std::make_pair(Lo, Hi);
6857 void SelectionDAG::ExtractVectorElements(SDValue Op,
6858 SmallVectorImpl<SDValue> &Args,
6859 unsigned Start, unsigned Count) {
6860 EVT VT = Op.getValueType();
6862 Count = VT.getVectorNumElements();
6864 EVT EltVT = VT.getVectorElementType();
6865 EVT IdxTy = TLI->getVectorIdxTy();
6867 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6868 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6869 Op, getConstant(i, SL, IdxTy)));
6873 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6874 unsigned GlobalAddressSDNode::getAddressSpace() const {
6875 return getGlobal()->getType()->getAddressSpace();
6879 Type *ConstantPoolSDNode::getType() const {
6880 if (isMachineConstantPoolEntry())
6881 return Val.MachineCPVal->getType();
6882 return Val.ConstVal->getType();
6885 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6887 unsigned &SplatBitSize,
6889 unsigned MinSplatBits,
6890 bool isBigEndian) const {
6891 EVT VT = getValueType(0);
6892 assert(VT.isVector() && "Expected a vector type");
6893 unsigned sz = VT.getSizeInBits();
6894 if (MinSplatBits > sz)
6897 SplatValue = APInt(sz, 0);
6898 SplatUndef = APInt(sz, 0);
6900 // Get the bits. Bits with undefined values (when the corresponding element
6901 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6902 // in SplatValue. If any of the values are not constant, give up and return
6904 unsigned int nOps = getNumOperands();
6905 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6906 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6908 for (unsigned j = 0; j < nOps; ++j) {
6909 unsigned i = isBigEndian ? nOps-1-j : j;
6910 SDValue OpVal = getOperand(i);
6911 unsigned BitPos = j * EltBitSize;
6913 if (OpVal.getOpcode() == ISD::UNDEF)
6914 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6915 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6916 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6917 zextOrTrunc(sz) << BitPos;
6918 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6919 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6924 // The build_vector is all constants or undefs. Find the smallest element
6925 // size that splats the vector.
6927 HasAnyUndefs = (SplatUndef != 0);
6930 unsigned HalfSize = sz / 2;
6931 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6932 APInt LowValue = SplatValue.trunc(HalfSize);
6933 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6934 APInt LowUndef = SplatUndef.trunc(HalfSize);
6936 // If the two halves do not match (ignoring undef bits), stop here.
6937 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6938 MinSplatBits > HalfSize)
6941 SplatValue = HighValue | LowValue;
6942 SplatUndef = HighUndef & LowUndef;
6951 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6952 if (UndefElements) {
6953 UndefElements->clear();
6954 UndefElements->resize(getNumOperands());
6957 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6958 SDValue Op = getOperand(i);
6959 if (Op.getOpcode() == ISD::UNDEF) {
6961 (*UndefElements)[i] = true;
6962 } else if (!Splatted) {
6964 } else if (Splatted != Op) {
6970 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6971 "Can only have a splat without a constant for all undefs.");
6972 return getOperand(0);
6979 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6980 return dyn_cast_or_null<ConstantSDNode>(
6981 getSplatValue(UndefElements).getNode());
6985 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6986 return dyn_cast_or_null<ConstantFPSDNode>(
6987 getSplatValue(UndefElements).getNode());
6990 bool BuildVectorSDNode::isConstant() const {
6991 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6992 unsigned Opc = getOperand(i).getOpcode();
6993 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6999 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7000 // Find the first non-undef value in the shuffle mask.
7002 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7005 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7007 // Make sure all remaining elements are either undef or the same as the first
7009 for (int Idx = Mask[i]; i != e; ++i)
7010 if (Mask[i] >= 0 && Mask[i] != Idx)
7016 static void checkForCyclesHelper(const SDNode *N,
7017 SmallPtrSetImpl<const SDNode*> &Visited,
7018 SmallPtrSetImpl<const SDNode*> &Checked,
7019 const llvm::SelectionDAG *DAG) {
7020 // If this node has already been checked, don't check it again.
7021 if (Checked.count(N))
7024 // If a node has already been visited on this depth-first walk, reject it as
7026 if (!Visited.insert(N).second) {
7027 errs() << "Detected cycle in SelectionDAG\n";
7028 dbgs() << "Offending node:\n";
7029 N->dumprFull(DAG); dbgs() << "\n";
7033 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7034 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7041 void llvm::checkForCycles(const llvm::SDNode *N,
7042 const llvm::SelectionDAG *DAG,
7050 assert(N && "Checking nonexistent SDNode");
7051 SmallPtrSet<const SDNode*, 32> visited;
7052 SmallPtrSet<const SDNode*, 32> checked;
7053 checkForCyclesHelper(N, visited, checked, DAG);
7058 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7059 checkForCycles(DAG->getRoot().getNode(), DAG, force);