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.
2862 // Constant build vector truncation can be done with the original scalar
2863 // operands but with a new build vector with the truncated value type.
2864 return getNode(ISD::BUILD_VECTOR, DL, VT, BV->ops());
2870 case ISD::FP_EXTEND:
2871 case ISD::UINT_TO_FP:
2872 case ISD::SINT_TO_FP: {
2873 // Let the above scalar folding handle the folding of each element.
2874 SmallVector<SDValue, 8> Ops;
2875 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2876 SDValue OpN = BV->getOperand(i);
2877 OpN = getNode(Opcode, DL, VT.getVectorElementType(), OpN);
2878 if (OpN.getOpcode() != ISD::UNDEF &&
2879 OpN.getOpcode() != ISD::Constant &&
2880 OpN.getOpcode() != ISD::ConstantFP)
2884 if (Ops.size() == VT.getVectorNumElements())
2885 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2892 unsigned OpOpcode = Operand.getNode()->getOpcode();
2894 case ISD::TokenFactor:
2895 case ISD::MERGE_VALUES:
2896 case ISD::CONCAT_VECTORS:
2897 return Operand; // Factor, merge or concat of one node? No need.
2898 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2899 case ISD::FP_EXTEND:
2900 assert(VT.isFloatingPoint() &&
2901 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2902 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2903 assert((!VT.isVector() ||
2904 VT.getVectorNumElements() ==
2905 Operand.getValueType().getVectorNumElements()) &&
2906 "Vector element count mismatch!");
2907 if (Operand.getOpcode() == ISD::UNDEF)
2908 return getUNDEF(VT);
2910 case ISD::SIGN_EXTEND:
2911 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2912 "Invalid SIGN_EXTEND!");
2913 if (Operand.getValueType() == VT) return Operand; // noop extension
2914 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2915 "Invalid sext node, dst < src!");
2916 assert((!VT.isVector() ||
2917 VT.getVectorNumElements() ==
2918 Operand.getValueType().getVectorNumElements()) &&
2919 "Vector element count mismatch!");
2920 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2921 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2922 else if (OpOpcode == ISD::UNDEF)
2923 // sext(undef) = 0, because the top bits will all be the same.
2924 return getConstant(0, DL, VT);
2926 case ISD::ZERO_EXTEND:
2927 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2928 "Invalid ZERO_EXTEND!");
2929 if (Operand.getValueType() == VT) return Operand; // noop extension
2930 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2931 "Invalid zext node, dst < src!");
2932 assert((!VT.isVector() ||
2933 VT.getVectorNumElements() ==
2934 Operand.getValueType().getVectorNumElements()) &&
2935 "Vector element count mismatch!");
2936 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2937 return getNode(ISD::ZERO_EXTEND, DL, VT,
2938 Operand.getNode()->getOperand(0));
2939 else if (OpOpcode == ISD::UNDEF)
2940 // zext(undef) = 0, because the top bits will be zero.
2941 return getConstant(0, DL, VT);
2943 case ISD::ANY_EXTEND:
2944 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2945 "Invalid ANY_EXTEND!");
2946 if (Operand.getValueType() == VT) return Operand; // noop extension
2947 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2948 "Invalid anyext node, dst < src!");
2949 assert((!VT.isVector() ||
2950 VT.getVectorNumElements() ==
2951 Operand.getValueType().getVectorNumElements()) &&
2952 "Vector element count mismatch!");
2954 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2955 OpOpcode == ISD::ANY_EXTEND)
2956 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2957 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2958 else if (OpOpcode == ISD::UNDEF)
2959 return getUNDEF(VT);
2961 // (ext (trunx x)) -> x
2962 if (OpOpcode == ISD::TRUNCATE) {
2963 SDValue OpOp = Operand.getNode()->getOperand(0);
2964 if (OpOp.getValueType() == VT)
2969 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2970 "Invalid TRUNCATE!");
2971 if (Operand.getValueType() == VT) return Operand; // noop truncate
2972 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2973 "Invalid truncate node, src < dst!");
2974 assert((!VT.isVector() ||
2975 VT.getVectorNumElements() ==
2976 Operand.getValueType().getVectorNumElements()) &&
2977 "Vector element count mismatch!");
2978 if (OpOpcode == ISD::TRUNCATE)
2979 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2980 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2981 OpOpcode == ISD::ANY_EXTEND) {
2982 // If the source is smaller than the dest, we still need an extend.
2983 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2984 .bitsLT(VT.getScalarType()))
2985 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2986 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2987 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2988 return Operand.getNode()->getOperand(0);
2990 if (OpOpcode == ISD::UNDEF)
2991 return getUNDEF(VT);
2994 // Basic sanity checking.
2995 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2996 && "Cannot BITCAST between types of different sizes!");
2997 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2998 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2999 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3000 if (OpOpcode == ISD::UNDEF)
3001 return getUNDEF(VT);
3003 case ISD::SCALAR_TO_VECTOR:
3004 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3005 (VT.getVectorElementType() == Operand.getValueType() ||
3006 (VT.getVectorElementType().isInteger() &&
3007 Operand.getValueType().isInteger() &&
3008 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3009 "Illegal SCALAR_TO_VECTOR node!");
3010 if (OpOpcode == ISD::UNDEF)
3011 return getUNDEF(VT);
3012 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3013 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3014 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3015 Operand.getConstantOperandVal(1) == 0 &&
3016 Operand.getOperand(0).getValueType() == VT)
3017 return Operand.getOperand(0);
3020 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3021 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3022 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3023 Operand.getNode()->getOperand(0));
3024 if (OpOpcode == ISD::FNEG) // --X -> X
3025 return Operand.getNode()->getOperand(0);
3028 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3029 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3034 SDVTList VTs = getVTList(VT);
3035 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3036 FoldingSetNodeID ID;
3037 SDValue Ops[1] = { Operand };
3038 AddNodeIDNode(ID, Opcode, VTs, Ops);
3040 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3041 return SDValue(E, 0);
3043 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3044 DL.getDebugLoc(), VTs, Operand);
3045 CSEMap.InsertNode(N, IP);
3047 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3048 DL.getDebugLoc(), VTs, Operand);
3052 return SDValue(N, 0);
3055 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3056 SDNode *Cst1, SDNode *Cst2) {
3057 // If the opcode is a target-specific ISD node, there's nothing we can
3058 // do here and the operand rules may not line up with the below, so
3060 if (Opcode >= ISD::BUILTIN_OP_END)
3063 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3064 SmallVector<SDValue, 4> Outputs;
3065 EVT SVT = VT.getScalarType();
3067 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3068 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3069 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3072 if (Scalar1 && Scalar2)
3073 // Scalar instruction.
3074 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3076 // For vectors extract each constant element into Inputs so we can constant
3077 // fold them individually.
3078 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3079 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3083 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3085 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3086 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3087 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3088 if (!V1 || !V2) // Not a constant, bail.
3091 if (V1->isOpaque() || V2->isOpaque())
3094 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3095 // FIXME: This is valid and could be handled by truncating the APInts.
3096 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3099 Inputs.push_back(std::make_pair(V1, V2));
3103 // We have a number of constant values, constant fold them element by element.
3104 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3105 const APInt &C1 = Inputs[I].first->getAPIntValue();
3106 const APInt &C2 = Inputs[I].second->getAPIntValue();
3110 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3113 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3116 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3119 if (!C2.getBoolValue())
3121 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3124 if (!C2.getBoolValue())
3126 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3129 if (!C2.getBoolValue())
3131 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3134 if (!C2.getBoolValue())
3136 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3139 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3142 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3145 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3148 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3151 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3154 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3157 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3160 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3167 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3168 "Expected a scalar or vector!"));
3170 // Handle the scalar case first.
3172 return Outputs.back();
3174 // We may have a vector type but a scalar result. Create a splat.
3175 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3177 // Build a big vector out of the scalar elements we generated.
3178 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3181 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3182 SDValue N2, bool nuw, bool nsw, bool exact) {
3183 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3184 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3187 case ISD::TokenFactor:
3188 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3189 N2.getValueType() == MVT::Other && "Invalid token factor!");
3190 // Fold trivial token factors.
3191 if (N1.getOpcode() == ISD::EntryToken) return N2;
3192 if (N2.getOpcode() == ISD::EntryToken) return N1;
3193 if (N1 == N2) return N1;
3195 case ISD::CONCAT_VECTORS:
3196 // Concat of UNDEFs is UNDEF.
3197 if (N1.getOpcode() == ISD::UNDEF &&
3198 N2.getOpcode() == ISD::UNDEF)
3199 return getUNDEF(VT);
3201 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3202 // one big BUILD_VECTOR.
3203 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3204 N2.getOpcode() == ISD::BUILD_VECTOR) {
3205 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3206 N1.getNode()->op_end());
3207 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3209 // BUILD_VECTOR requires all inputs to be of the same type, find the
3210 // maximum type and extend them all.
3211 EVT SVT = VT.getScalarType();
3212 for (SDValue Op : Elts)
3213 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3214 if (SVT.bitsGT(VT.getScalarType()))
3215 for (SDValue &Op : Elts)
3216 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3217 ? getZExtOrTrunc(Op, DL, SVT)
3218 : getSExtOrTrunc(Op, DL, SVT);
3220 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3224 assert(VT.isInteger() && "This operator does not apply to FP types!");
3225 assert(N1.getValueType() == N2.getValueType() &&
3226 N1.getValueType() == VT && "Binary operator types must match!");
3227 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3228 // worth handling here.
3229 if (N2C && N2C->isNullValue())
3231 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3238 assert(VT.isInteger() && "This operator does not apply to FP types!");
3239 assert(N1.getValueType() == N2.getValueType() &&
3240 N1.getValueType() == VT && "Binary operator types must match!");
3241 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3242 // it's worth handling here.
3243 if (N2C && N2C->isNullValue())
3253 assert(VT.isInteger() && "This operator does not apply to FP types!");
3254 assert(N1.getValueType() == N2.getValueType() &&
3255 N1.getValueType() == VT && "Binary operator types must match!");
3262 if (getTarget().Options.UnsafeFPMath) {
3263 if (Opcode == ISD::FADD) {
3265 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3266 if (CFP->getValueAPF().isZero())
3269 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3270 if (CFP->getValueAPF().isZero())
3272 } else if (Opcode == ISD::FSUB) {
3274 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3275 if (CFP->getValueAPF().isZero())
3277 } else if (Opcode == ISD::FMUL) {
3278 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3281 // If the first operand isn't the constant, try the second
3283 CFP = dyn_cast<ConstantFPSDNode>(N2);
3290 return SDValue(CFP,0);
3292 if (CFP->isExactlyValue(1.0))
3297 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3298 assert(N1.getValueType() == N2.getValueType() &&
3299 N1.getValueType() == VT && "Binary operator types must match!");
3301 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3302 assert(N1.getValueType() == VT &&
3303 N1.getValueType().isFloatingPoint() &&
3304 N2.getValueType().isFloatingPoint() &&
3305 "Invalid FCOPYSIGN!");
3312 assert(VT == N1.getValueType() &&
3313 "Shift operators return type must be the same as their first arg");
3314 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3315 "Shifts only work on integers");
3316 assert((!VT.isVector() || VT == N2.getValueType()) &&
3317 "Vector shift amounts must be in the same as their first arg");
3318 // Verify that the shift amount VT is bit enough to hold valid shift
3319 // amounts. This catches things like trying to shift an i1024 value by an
3320 // i8, which is easy to fall into in generic code that uses
3321 // TLI.getShiftAmount().
3322 assert(N2.getValueType().getSizeInBits() >=
3323 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3324 "Invalid use of small shift amount with oversized value!");
3326 // Always fold shifts of i1 values so the code generator doesn't need to
3327 // handle them. Since we know the size of the shift has to be less than the
3328 // size of the value, the shift/rotate count is guaranteed to be zero.
3331 if (N2C && N2C->isNullValue())
3334 case ISD::FP_ROUND_INREG: {
3335 EVT EVT = cast<VTSDNode>(N2)->getVT();
3336 assert(VT == N1.getValueType() && "Not an inreg round!");
3337 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3338 "Cannot FP_ROUND_INREG integer types");
3339 assert(EVT.isVector() == VT.isVector() &&
3340 "FP_ROUND_INREG type should be vector iff the operand "
3342 assert((!EVT.isVector() ||
3343 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3344 "Vector element counts must match in FP_ROUND_INREG");
3345 assert(EVT.bitsLE(VT) && "Not rounding down!");
3347 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3351 assert(VT.isFloatingPoint() &&
3352 N1.getValueType().isFloatingPoint() &&
3353 VT.bitsLE(N1.getValueType()) &&
3354 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3355 if (N1.getValueType() == VT) return N1; // noop conversion.
3357 case ISD::AssertSext:
3358 case ISD::AssertZext: {
3359 EVT EVT = cast<VTSDNode>(N2)->getVT();
3360 assert(VT == N1.getValueType() && "Not an inreg extend!");
3361 assert(VT.isInteger() && EVT.isInteger() &&
3362 "Cannot *_EXTEND_INREG FP types");
3363 assert(!EVT.isVector() &&
3364 "AssertSExt/AssertZExt type should be the vector element type "
3365 "rather than the vector type!");
3366 assert(EVT.bitsLE(VT) && "Not extending!");
3367 if (VT == EVT) return N1; // noop assertion.
3370 case ISD::SIGN_EXTEND_INREG: {
3371 EVT EVT = cast<VTSDNode>(N2)->getVT();
3372 assert(VT == N1.getValueType() && "Not an inreg extend!");
3373 assert(VT.isInteger() && EVT.isInteger() &&
3374 "Cannot *_EXTEND_INREG FP types");
3375 assert(EVT.isVector() == VT.isVector() &&
3376 "SIGN_EXTEND_INREG type should be vector iff the operand "
3378 assert((!EVT.isVector() ||
3379 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3380 "Vector element counts must match in SIGN_EXTEND_INREG");
3381 assert(EVT.bitsLE(VT) && "Not extending!");
3382 if (EVT == VT) return N1; // Not actually extending
3385 APInt Val = N1C->getAPIntValue();
3386 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3387 Val <<= Val.getBitWidth()-FromBits;
3388 Val = Val.ashr(Val.getBitWidth()-FromBits);
3389 return getConstant(Val, DL, VT);
3393 case ISD::EXTRACT_VECTOR_ELT:
3394 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3395 if (N1.getOpcode() == ISD::UNDEF)
3396 return getUNDEF(VT);
3398 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3399 // expanding copies of large vectors from registers.
3401 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3402 N1.getNumOperands() > 0) {
3404 N1.getOperand(0).getValueType().getVectorNumElements();
3405 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3406 N1.getOperand(N2C->getZExtValue() / Factor),
3407 getConstant(N2C->getZExtValue() % Factor, DL,
3408 N2.getValueType()));
3411 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3412 // expanding large vector constants.
3413 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3414 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3416 if (VT != Elt.getValueType())
3417 // If the vector element type is not legal, the BUILD_VECTOR operands
3418 // are promoted and implicitly truncated, and the result implicitly
3419 // extended. Make that explicit here.
3420 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3425 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3426 // operations are lowered to scalars.
3427 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3428 // If the indices are the same, return the inserted element else
3429 // if the indices are known different, extract the element from
3430 // the original vector.
3431 SDValue N1Op2 = N1.getOperand(2);
3432 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3434 if (N1Op2C && N2C) {
3435 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3436 if (VT == N1.getOperand(1).getValueType())
3437 return N1.getOperand(1);
3439 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3442 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3446 case ISD::EXTRACT_ELEMENT:
3447 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3448 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3449 (N1.getValueType().isInteger() == VT.isInteger()) &&
3450 N1.getValueType() != VT &&
3451 "Wrong types for EXTRACT_ELEMENT!");
3453 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3454 // 64-bit integers into 32-bit parts. Instead of building the extract of
3455 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3456 if (N1.getOpcode() == ISD::BUILD_PAIR)
3457 return N1.getOperand(N2C->getZExtValue());
3459 // EXTRACT_ELEMENT of a constant int is also very common.
3460 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3461 unsigned ElementSize = VT.getSizeInBits();
3462 unsigned Shift = ElementSize * N2C->getZExtValue();
3463 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3464 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3467 case ISD::EXTRACT_SUBVECTOR: {
3469 if (VT.isSimple() && N1.getValueType().isSimple()) {
3470 assert(VT.isVector() && N1.getValueType().isVector() &&
3471 "Extract subvector VTs must be a vectors!");
3472 assert(VT.getVectorElementType() ==
3473 N1.getValueType().getVectorElementType() &&
3474 "Extract subvector VTs must have the same element type!");
3475 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3476 "Extract subvector must be from larger vector to smaller vector!");
3478 if (isa<ConstantSDNode>(Index.getNode())) {
3479 assert((VT.getVectorNumElements() +
3480 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3481 <= N1.getValueType().getVectorNumElements())
3482 && "Extract subvector overflow!");
3485 // Trivial extraction.
3486 if (VT.getSimpleVT() == N1.getSimpleValueType())
3493 // Perform trivial constant folding.
3495 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3498 // Canonicalize constant to RHS if commutative.
3499 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3500 std::swap(N1C, N2C);
3504 // Constant fold FP operations.
3505 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3506 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3507 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3509 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3510 // Canonicalize constant to RHS if commutative.
3511 std::swap(N1CFP, N2CFP);
3514 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3515 APFloat::opStatus s;
3518 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3519 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3520 return getConstantFP(V1, DL, VT);
3523 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3524 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3525 return getConstantFP(V1, DL, VT);
3528 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3529 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3530 return getConstantFP(V1, DL, VT);
3533 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3534 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3535 s!=APFloat::opDivByZero)) {
3536 return getConstantFP(V1, DL, VT);
3540 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3541 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3542 s!=APFloat::opDivByZero)) {
3543 return getConstantFP(V1, DL, VT);
3546 case ISD::FCOPYSIGN:
3548 return getConstantFP(V1, DL, VT);
3553 if (Opcode == ISD::FP_ROUND) {
3554 APFloat V = N1CFP->getValueAPF(); // make copy
3556 // This can return overflow, underflow, or inexact; we don't care.
3557 // FIXME need to be more flexible about rounding mode.
3558 (void)V.convert(EVTToAPFloatSemantics(VT),
3559 APFloat::rmNearestTiesToEven, &ignored);
3560 return getConstantFP(V, DL, VT);
3564 // Canonicalize an UNDEF to the RHS, even over a constant.
3565 if (N1.getOpcode() == ISD::UNDEF) {
3566 if (isCommutativeBinOp(Opcode)) {
3570 case ISD::FP_ROUND_INREG:
3571 case ISD::SIGN_EXTEND_INREG:
3577 return N1; // fold op(undef, arg2) -> undef
3585 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3586 // For vectors, we can't easily build an all zero vector, just return
3593 // Fold a bunch of operators when the RHS is undef.
3594 if (N2.getOpcode() == ISD::UNDEF) {
3597 if (N1.getOpcode() == ISD::UNDEF)
3598 // Handle undef ^ undef -> 0 special case. This is a common
3600 return getConstant(0, DL, VT);
3610 return N2; // fold op(arg1, undef) -> undef
3616 if (getTarget().Options.UnsafeFPMath)
3624 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3625 // For vectors, we can't easily build an all zero vector, just return
3630 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3631 // For vectors, we can't easily build an all one vector, just return
3639 // Memoize this node if possible.
3641 SDVTList VTs = getVTList(VT);
3642 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3643 if (VT != MVT::Glue) {
3644 SDValue Ops[] = {N1, N2};
3645 FoldingSetNodeID ID;
3646 AddNodeIDNode(ID, Opcode, VTs, Ops);
3648 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3650 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3651 return SDValue(E, 0);
3653 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3655 CSEMap.InsertNode(N, IP);
3657 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3661 return SDValue(N, 0);
3664 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3665 SDValue N1, SDValue N2, SDValue N3) {
3666 // Perform various simplifications.
3667 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3670 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3671 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3672 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3673 if (N1CFP && N2CFP && N3CFP) {
3674 APFloat V1 = N1CFP->getValueAPF();
3675 const APFloat &V2 = N2CFP->getValueAPF();
3676 const APFloat &V3 = N3CFP->getValueAPF();
3677 APFloat::opStatus s =
3678 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3679 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3680 return getConstantFP(V1, DL, VT);
3684 case ISD::CONCAT_VECTORS:
3685 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3686 // one big BUILD_VECTOR.
3687 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3688 N2.getOpcode() == ISD::BUILD_VECTOR &&
3689 N3.getOpcode() == ISD::BUILD_VECTOR) {
3690 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3691 N1.getNode()->op_end());
3692 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3693 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3694 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3698 // Use FoldSetCC to simplify SETCC's.
3699 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3700 if (Simp.getNode()) return Simp;
3705 if (N1C->getZExtValue())
3706 return N2; // select true, X, Y -> X
3707 return N3; // select false, X, Y -> Y
3710 if (N2 == N3) return N2; // select C, X, X -> X
3712 case ISD::VECTOR_SHUFFLE:
3713 llvm_unreachable("should use getVectorShuffle constructor!");
3714 case ISD::INSERT_SUBVECTOR: {
3716 if (VT.isSimple() && N1.getValueType().isSimple()
3717 && N2.getValueType().isSimple()) {
3718 assert(VT.isVector() && N1.getValueType().isVector() &&
3719 N2.getValueType().isVector() &&
3720 "Insert subvector VTs must be a vectors");
3721 assert(VT == N1.getValueType() &&
3722 "Dest and insert subvector source types must match!");
3723 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3724 "Insert subvector must be from smaller vector to larger vector!");
3725 if (isa<ConstantSDNode>(Index.getNode())) {
3726 assert((N2.getValueType().getVectorNumElements() +
3727 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3728 <= VT.getVectorNumElements())
3729 && "Insert subvector overflow!");
3732 // Trivial insertion.
3733 if (VT.getSimpleVT() == N2.getSimpleValueType())
3739 // Fold bit_convert nodes from a type to themselves.
3740 if (N1.getValueType() == VT)
3745 // Memoize node if it doesn't produce a flag.
3747 SDVTList VTs = getVTList(VT);
3748 if (VT != MVT::Glue) {
3749 SDValue Ops[] = { N1, N2, N3 };
3750 FoldingSetNodeID ID;
3751 AddNodeIDNode(ID, Opcode, VTs, Ops);
3753 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3754 return SDValue(E, 0);
3756 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3757 DL.getDebugLoc(), VTs, N1, N2, N3);
3758 CSEMap.InsertNode(N, IP);
3760 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3761 DL.getDebugLoc(), VTs, N1, N2, N3);
3765 return SDValue(N, 0);
3768 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3769 SDValue N1, SDValue N2, SDValue N3,
3771 SDValue Ops[] = { N1, N2, N3, N4 };
3772 return getNode(Opcode, DL, VT, Ops);
3775 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3776 SDValue N1, SDValue N2, SDValue N3,
3777 SDValue N4, SDValue N5) {
3778 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3779 return getNode(Opcode, DL, VT, Ops);
3782 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3783 /// the incoming stack arguments to be loaded from the stack.
3784 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3785 SmallVector<SDValue, 8> ArgChains;
3787 // Include the original chain at the beginning of the list. When this is
3788 // used by target LowerCall hooks, this helps legalize find the
3789 // CALLSEQ_BEGIN node.
3790 ArgChains.push_back(Chain);
3792 // Add a chain value for each stack argument.
3793 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3794 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3795 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3796 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3797 if (FI->getIndex() < 0)
3798 ArgChains.push_back(SDValue(L, 1));
3800 // Build a tokenfactor for all the chains.
3801 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3804 /// getMemsetValue - Vectorized representation of the memset value
3806 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3808 assert(Value.getOpcode() != ISD::UNDEF);
3810 unsigned NumBits = VT.getScalarType().getSizeInBits();
3811 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3812 assert(C->getAPIntValue().getBitWidth() == 8);
3813 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3815 return DAG.getConstant(Val, dl, VT);
3816 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3820 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3821 EVT IntVT = VT.getScalarType();
3822 if (!IntVT.isInteger())
3823 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3825 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3827 // Use a multiplication with 0x010101... to extend the input to the
3829 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3830 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3831 DAG.getConstant(Magic, dl, IntVT));
3834 if (VT != Value.getValueType() && !VT.isInteger())
3835 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3836 if (VT != Value.getValueType()) {
3837 assert(VT.getVectorElementType() == Value.getValueType() &&
3838 "value type should be one vector element here");
3839 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3840 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3846 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3847 /// used when a memcpy is turned into a memset when the source is a constant
3849 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3850 const TargetLowering &TLI, StringRef Str) {
3851 // Handle vector with all elements zero.
3854 return DAG.getConstant(0, dl, VT);
3855 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3856 return DAG.getConstantFP(0.0, dl, VT);
3857 else if (VT.isVector()) {
3858 unsigned NumElts = VT.getVectorNumElements();
3859 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3860 return DAG.getNode(ISD::BITCAST, dl, VT,
3861 DAG.getConstant(0, dl,
3862 EVT::getVectorVT(*DAG.getContext(),
3865 llvm_unreachable("Expected type!");
3868 assert(!VT.isVector() && "Can't handle vector type here!");
3869 unsigned NumVTBits = VT.getSizeInBits();
3870 unsigned NumVTBytes = NumVTBits / 8;
3871 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3873 APInt Val(NumVTBits, 0);
3874 if (TLI.isLittleEndian()) {
3875 for (unsigned i = 0; i != NumBytes; ++i)
3876 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3878 for (unsigned i = 0; i != NumBytes; ++i)
3879 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3882 // If the "cost" of materializing the integer immediate is less than the cost
3883 // of a load, then it is cost effective to turn the load into the immediate.
3884 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3885 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3886 return DAG.getConstant(Val, dl, VT);
3887 return SDValue(nullptr, 0);
3890 /// getMemBasePlusOffset - Returns base and offset node for the
3892 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3893 SelectionDAG &DAG) {
3894 EVT VT = Base.getValueType();
3895 return DAG.getNode(ISD::ADD, dl,
3896 VT, Base, DAG.getConstant(Offset, dl, VT));
3899 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3901 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3902 unsigned SrcDelta = 0;
3903 GlobalAddressSDNode *G = nullptr;
3904 if (Src.getOpcode() == ISD::GlobalAddress)
3905 G = cast<GlobalAddressSDNode>(Src);
3906 else if (Src.getOpcode() == ISD::ADD &&
3907 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3908 Src.getOperand(1).getOpcode() == ISD::Constant) {
3909 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3910 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3915 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3918 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3919 /// to replace the memset / memcpy. Return true if the number of memory ops
3920 /// is below the threshold. It returns the types of the sequence of
3921 /// memory ops to perform memset / memcpy by reference.
3922 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3923 unsigned Limit, uint64_t Size,
3924 unsigned DstAlign, unsigned SrcAlign,
3930 const TargetLowering &TLI) {
3931 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3932 "Expecting memcpy / memset source to meet alignment requirement!");
3933 // If 'SrcAlign' is zero, that means the memory operation does not need to
3934 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3935 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3936 // is the specified alignment of the memory operation. If it is zero, that
3937 // means it's possible to change the alignment of the destination.
3938 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3939 // not need to be loaded.
3940 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3941 IsMemset, ZeroMemset, MemcpyStrSrc,
3942 DAG.getMachineFunction());
3944 if (VT == MVT::Other) {
3946 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3947 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3948 VT = TLI.getPointerTy();
3950 switch (DstAlign & 7) {
3951 case 0: VT = MVT::i64; break;
3952 case 4: VT = MVT::i32; break;
3953 case 2: VT = MVT::i16; break;
3954 default: VT = MVT::i8; break;
3959 while (!TLI.isTypeLegal(LVT))
3960 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3961 assert(LVT.isInteger());
3967 unsigned NumMemOps = 0;
3969 unsigned VTSize = VT.getSizeInBits() / 8;
3970 while (VTSize > Size) {
3971 // For now, only use non-vector load / store's for the left-over pieces.
3976 if (VT.isVector() || VT.isFloatingPoint()) {
3977 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3978 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3979 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3981 else if (NewVT == MVT::i64 &&
3982 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3983 TLI.isSafeMemOpType(MVT::f64)) {
3984 // i64 is usually not legal on 32-bit targets, but f64 may be.
3992 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3993 if (NewVT == MVT::i8)
3995 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3997 NewVTSize = NewVT.getSizeInBits() / 8;
3999 // If the new VT cannot cover all of the remaining bits, then consider
4000 // issuing a (or a pair of) unaligned and overlapping load / store.
4001 // FIXME: Only does this for 64-bit or more since we don't have proper
4002 // cost model for unaligned load / store.
4005 if (NumMemOps && AllowOverlap &&
4006 VTSize >= 8 && NewVTSize < Size &&
4007 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4015 if (++NumMemOps > Limit)
4018 MemOps.push_back(VT);
4025 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4026 SDValue Chain, SDValue Dst,
4027 SDValue Src, uint64_t Size,
4028 unsigned Align, bool isVol,
4030 MachinePointerInfo DstPtrInfo,
4031 MachinePointerInfo SrcPtrInfo) {
4032 // Turn a memcpy of undef to nop.
4033 if (Src.getOpcode() == ISD::UNDEF)
4036 // Expand memcpy to a series of load and store ops if the size operand falls
4037 // below a certain threshold.
4038 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4039 // rather than maybe a humongous number of loads and stores.
4040 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4041 std::vector<EVT> MemOps;
4042 bool DstAlignCanChange = false;
4043 MachineFunction &MF = DAG.getMachineFunction();
4044 MachineFrameInfo *MFI = MF.getFrameInfo();
4045 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4046 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4047 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4048 DstAlignCanChange = true;
4049 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4050 if (Align > SrcAlign)
4053 bool CopyFromStr = isMemSrcFromString(Src, Str);
4054 bool isZeroStr = CopyFromStr && Str.empty();
4055 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4057 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4058 (DstAlignCanChange ? 0 : Align),
4059 (isZeroStr ? 0 : SrcAlign),
4060 false, false, CopyFromStr, true, DAG, TLI))
4063 if (DstAlignCanChange) {
4064 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4065 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4067 // Don't promote to an alignment that would require dynamic stack
4069 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4070 if (!TRI->needsStackRealignment(MF))
4071 while (NewAlign > Align &&
4072 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4075 if (NewAlign > Align) {
4076 // Give the stack frame object a larger alignment if needed.
4077 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4078 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4083 SmallVector<SDValue, 8> OutChains;
4084 unsigned NumMemOps = MemOps.size();
4085 uint64_t SrcOff = 0, DstOff = 0;
4086 for (unsigned i = 0; i != NumMemOps; ++i) {
4088 unsigned VTSize = VT.getSizeInBits() / 8;
4089 SDValue Value, Store;
4091 if (VTSize > Size) {
4092 // Issuing an unaligned load / store pair that overlaps with the previous
4093 // pair. Adjust the offset accordingly.
4094 assert(i == NumMemOps-1 && i != 0);
4095 SrcOff -= VTSize - Size;
4096 DstOff -= VTSize - Size;
4100 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4101 // It's unlikely a store of a vector immediate can be done in a single
4102 // instruction. It would require a load from a constantpool first.
4103 // We only handle zero vectors here.
4104 // FIXME: Handle other cases where store of vector immediate is done in
4105 // a single instruction.
4106 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4107 if (Value.getNode())
4108 Store = DAG.getStore(Chain, dl, Value,
4109 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4110 DstPtrInfo.getWithOffset(DstOff), isVol,
4114 if (!Store.getNode()) {
4115 // The type might not be legal for the target. This should only happen
4116 // if the type is smaller than a legal type, as on PPC, so the right
4117 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4118 // to Load/Store if NVT==VT.
4119 // FIXME does the case above also need this?
4120 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4121 assert(NVT.bitsGE(VT));
4122 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4123 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4124 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4125 false, MinAlign(SrcAlign, SrcOff));
4126 Store = DAG.getTruncStore(Chain, dl, Value,
4127 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4128 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4131 OutChains.push_back(Store);
4137 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4140 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4141 SDValue Chain, SDValue Dst,
4142 SDValue Src, uint64_t Size,
4143 unsigned Align, bool isVol,
4145 MachinePointerInfo DstPtrInfo,
4146 MachinePointerInfo SrcPtrInfo) {
4147 // Turn a memmove of undef to nop.
4148 if (Src.getOpcode() == ISD::UNDEF)
4151 // Expand memmove to a series of load and store ops if the size operand falls
4152 // below a certain threshold.
4153 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4154 std::vector<EVT> MemOps;
4155 bool DstAlignCanChange = false;
4156 MachineFunction &MF = DAG.getMachineFunction();
4157 MachineFrameInfo *MFI = MF.getFrameInfo();
4158 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4159 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4160 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4161 DstAlignCanChange = true;
4162 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4163 if (Align > SrcAlign)
4165 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4167 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4168 (DstAlignCanChange ? 0 : Align), SrcAlign,
4169 false, false, false, false, DAG, TLI))
4172 if (DstAlignCanChange) {
4173 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4174 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4175 if (NewAlign > Align) {
4176 // Give the stack frame object a larger alignment if needed.
4177 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4178 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4183 uint64_t SrcOff = 0, DstOff = 0;
4184 SmallVector<SDValue, 8> LoadValues;
4185 SmallVector<SDValue, 8> LoadChains;
4186 SmallVector<SDValue, 8> OutChains;
4187 unsigned NumMemOps = MemOps.size();
4188 for (unsigned i = 0; i < NumMemOps; i++) {
4190 unsigned VTSize = VT.getSizeInBits() / 8;
4193 Value = DAG.getLoad(VT, dl, Chain,
4194 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4195 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4196 false, false, SrcAlign);
4197 LoadValues.push_back(Value);
4198 LoadChains.push_back(Value.getValue(1));
4201 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4203 for (unsigned i = 0; i < NumMemOps; i++) {
4205 unsigned VTSize = VT.getSizeInBits() / 8;
4208 Store = DAG.getStore(Chain, dl, LoadValues[i],
4209 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4210 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4211 OutChains.push_back(Store);
4215 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4218 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4221 /// \param DAG Selection DAG where lowered code is placed.
4222 /// \param dl Link to corresponding IR location.
4223 /// \param Chain Control flow dependency.
4224 /// \param Dst Pointer to destination memory location.
4225 /// \param Src Value of byte to write into the memory.
4226 /// \param Size Number of bytes to write.
4227 /// \param Align Alignment of the destination in bytes.
4228 /// \param isVol True if destination is volatile.
4229 /// \param DstPtrInfo IR information on the memory pointer.
4230 /// \returns New head in the control flow, if lowering was successful, empty
4231 /// SDValue otherwise.
4233 /// The function tries to replace 'llvm.memset' intrinsic with several store
4234 /// operations and value calculation code. This is usually profitable for small
4236 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4237 SDValue Chain, SDValue Dst,
4238 SDValue Src, uint64_t Size,
4239 unsigned Align, bool isVol,
4240 MachinePointerInfo DstPtrInfo) {
4241 // Turn a memset of undef to nop.
4242 if (Src.getOpcode() == ISD::UNDEF)
4245 // Expand memset to a series of load/store ops if the size operand
4246 // falls below a certain threshold.
4247 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4248 std::vector<EVT> MemOps;
4249 bool DstAlignCanChange = false;
4250 MachineFunction &MF = DAG.getMachineFunction();
4251 MachineFrameInfo *MFI = MF.getFrameInfo();
4252 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4253 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4254 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4255 DstAlignCanChange = true;
4257 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4258 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4259 Size, (DstAlignCanChange ? 0 : Align), 0,
4260 true, IsZeroVal, false, true, DAG, TLI))
4263 if (DstAlignCanChange) {
4264 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4265 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4266 if (NewAlign > Align) {
4267 // Give the stack frame object a larger alignment if needed.
4268 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4269 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4274 SmallVector<SDValue, 8> OutChains;
4275 uint64_t DstOff = 0;
4276 unsigned NumMemOps = MemOps.size();
4278 // Find the largest store and generate the bit pattern for it.
4279 EVT LargestVT = MemOps[0];
4280 for (unsigned i = 1; i < NumMemOps; i++)
4281 if (MemOps[i].bitsGT(LargestVT))
4282 LargestVT = MemOps[i];
4283 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4285 for (unsigned i = 0; i < NumMemOps; i++) {
4287 unsigned VTSize = VT.getSizeInBits() / 8;
4288 if (VTSize > Size) {
4289 // Issuing an unaligned load / store pair that overlaps with the previous
4290 // pair. Adjust the offset accordingly.
4291 assert(i == NumMemOps-1 && i != 0);
4292 DstOff -= VTSize - Size;
4295 // If this store is smaller than the largest store see whether we can get
4296 // the smaller value for free with a truncate.
4297 SDValue Value = MemSetValue;
4298 if (VT.bitsLT(LargestVT)) {
4299 if (!LargestVT.isVector() && !VT.isVector() &&
4300 TLI.isTruncateFree(LargestVT, VT))
4301 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4303 Value = getMemsetValue(Src, VT, DAG, dl);
4305 assert(Value.getValueType() == VT && "Value with wrong type.");
4306 SDValue Store = DAG.getStore(Chain, dl, Value,
4307 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4308 DstPtrInfo.getWithOffset(DstOff),
4309 isVol, false, Align);
4310 OutChains.push_back(Store);
4311 DstOff += VT.getSizeInBits() / 8;
4315 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4318 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4319 SDValue Src, SDValue Size,
4320 unsigned Align, bool isVol, bool AlwaysInline,
4321 bool isTailCall, MachinePointerInfo DstPtrInfo,
4322 MachinePointerInfo SrcPtrInfo) {
4323 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4325 // Check to see if we should lower the memcpy to loads and stores first.
4326 // For cases within the target-specified limits, this is the best choice.
4327 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4329 // Memcpy with size zero? Just return the original chain.
4330 if (ConstantSize->isNullValue())
4333 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4334 ConstantSize->getZExtValue(),Align,
4335 isVol, false, DstPtrInfo, SrcPtrInfo);
4336 if (Result.getNode())
4340 // Then check to see if we should lower the memcpy with target-specific
4341 // code. If the target chooses to do this, this is the next best.
4343 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4344 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4345 DstPtrInfo, SrcPtrInfo);
4346 if (Result.getNode())
4350 // If we really need inline code and the target declined to provide it,
4351 // use a (potentially long) sequence of loads and stores.
4353 assert(ConstantSize && "AlwaysInline requires a constant size!");
4354 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4355 ConstantSize->getZExtValue(), Align, isVol,
4356 true, DstPtrInfo, SrcPtrInfo);
4359 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4360 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4361 // respect volatile, so they may do things like read or write memory
4362 // beyond the given memory regions. But fixing this isn't easy, and most
4363 // people don't care.
4365 // Emit a library call.
4366 TargetLowering::ArgListTy Args;
4367 TargetLowering::ArgListEntry Entry;
4368 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4369 Entry.Node = Dst; Args.push_back(Entry);
4370 Entry.Node = Src; Args.push_back(Entry);
4371 Entry.Node = Size; Args.push_back(Entry);
4372 // FIXME: pass in SDLoc
4373 TargetLowering::CallLoweringInfo CLI(*this);
4374 CLI.setDebugLoc(dl).setChain(Chain)
4375 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4376 Type::getVoidTy(*getContext()),
4377 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4378 TLI->getPointerTy()), std::move(Args), 0)
4380 .setTailCall(isTailCall);
4382 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4383 return CallResult.second;
4386 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4387 SDValue Src, SDValue Size,
4388 unsigned Align, bool isVol, bool isTailCall,
4389 MachinePointerInfo DstPtrInfo,
4390 MachinePointerInfo SrcPtrInfo) {
4391 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4393 // Check to see if we should lower the memmove to loads and stores first.
4394 // For cases within the target-specified limits, this is the best choice.
4395 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4397 // Memmove with size zero? Just return the original chain.
4398 if (ConstantSize->isNullValue())
4402 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4403 ConstantSize->getZExtValue(), Align, isVol,
4404 false, DstPtrInfo, SrcPtrInfo);
4405 if (Result.getNode())
4409 // Then check to see if we should lower the memmove with target-specific
4410 // code. If the target chooses to do this, this is the next best.
4412 SDValue Result = TSI->EmitTargetCodeForMemmove(
4413 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4414 if (Result.getNode())
4418 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4419 // not be safe. See memcpy above for more details.
4421 // Emit a library call.
4422 TargetLowering::ArgListTy Args;
4423 TargetLowering::ArgListEntry Entry;
4424 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4425 Entry.Node = Dst; Args.push_back(Entry);
4426 Entry.Node = Src; Args.push_back(Entry);
4427 Entry.Node = Size; Args.push_back(Entry);
4428 // FIXME: pass in SDLoc
4429 TargetLowering::CallLoweringInfo CLI(*this);
4430 CLI.setDebugLoc(dl).setChain(Chain)
4431 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4432 Type::getVoidTy(*getContext()),
4433 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4434 TLI->getPointerTy()), std::move(Args), 0)
4436 .setTailCall(isTailCall);
4438 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4439 return CallResult.second;
4442 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4443 SDValue Src, SDValue Size,
4444 unsigned Align, bool isVol, bool isTailCall,
4445 MachinePointerInfo DstPtrInfo) {
4446 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4448 // Check to see if we should lower the memset to stores first.
4449 // For cases within the target-specified limits, this is the best choice.
4450 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4452 // Memset with size zero? Just return the original chain.
4453 if (ConstantSize->isNullValue())
4457 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4458 Align, isVol, DstPtrInfo);
4460 if (Result.getNode())
4464 // Then check to see if we should lower the memset with target-specific
4465 // code. If the target chooses to do this, this is the next best.
4467 SDValue Result = TSI->EmitTargetCodeForMemset(
4468 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4469 if (Result.getNode())
4473 // Emit a library call.
4474 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4475 TargetLowering::ArgListTy Args;
4476 TargetLowering::ArgListEntry Entry;
4477 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4478 Args.push_back(Entry);
4480 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4481 Args.push_back(Entry);
4483 Entry.Ty = IntPtrTy;
4484 Args.push_back(Entry);
4486 // FIXME: pass in SDLoc
4487 TargetLowering::CallLoweringInfo CLI(*this);
4488 CLI.setDebugLoc(dl).setChain(Chain)
4489 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4490 Type::getVoidTy(*getContext()),
4491 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4492 TLI->getPointerTy()), std::move(Args), 0)
4494 .setTailCall(isTailCall);
4496 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4497 return CallResult.second;
4500 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4501 SDVTList VTList, ArrayRef<SDValue> Ops,
4502 MachineMemOperand *MMO,
4503 AtomicOrdering SuccessOrdering,
4504 AtomicOrdering FailureOrdering,
4505 SynchronizationScope SynchScope) {
4506 FoldingSetNodeID ID;
4507 ID.AddInteger(MemVT.getRawBits());
4508 AddNodeIDNode(ID, Opcode, VTList, Ops);
4509 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4511 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4512 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4513 return SDValue(E, 0);
4516 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4517 // SDNode doesn't have access to it. This memory will be "leaked" when
4518 // the node is deallocated, but recovered when the allocator is released.
4519 // If the number of operands is less than 5 we use AtomicSDNode's internal
4521 unsigned NumOps = Ops.size();
4522 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4525 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4526 dl.getDebugLoc(), VTList, MemVT,
4527 Ops.data(), DynOps, NumOps, MMO,
4528 SuccessOrdering, FailureOrdering,
4530 CSEMap.InsertNode(N, IP);
4532 return SDValue(N, 0);
4535 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4536 SDVTList VTList, ArrayRef<SDValue> Ops,
4537 MachineMemOperand *MMO,
4538 AtomicOrdering Ordering,
4539 SynchronizationScope SynchScope) {
4540 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4541 Ordering, SynchScope);
4544 SDValue SelectionDAG::getAtomicCmpSwap(
4545 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4546 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4547 unsigned Alignment, AtomicOrdering SuccessOrdering,
4548 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4549 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4550 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4551 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4553 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4554 Alignment = getEVTAlignment(MemVT);
4556 MachineFunction &MF = getMachineFunction();
4558 // FIXME: Volatile isn't really correct; we should keep track of atomic
4559 // orderings in the memoperand.
4560 unsigned Flags = MachineMemOperand::MOVolatile;
4561 Flags |= MachineMemOperand::MOLoad;
4562 Flags |= MachineMemOperand::MOStore;
4564 MachineMemOperand *MMO =
4565 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4567 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4568 SuccessOrdering, FailureOrdering, SynchScope);
4571 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4572 SDVTList VTs, SDValue Chain, SDValue Ptr,
4573 SDValue Cmp, SDValue Swp,
4574 MachineMemOperand *MMO,
4575 AtomicOrdering SuccessOrdering,
4576 AtomicOrdering FailureOrdering,
4577 SynchronizationScope SynchScope) {
4578 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4579 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4580 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4582 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4583 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4584 SuccessOrdering, FailureOrdering, SynchScope);
4587 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4589 SDValue Ptr, SDValue Val,
4590 const Value* PtrVal,
4592 AtomicOrdering Ordering,
4593 SynchronizationScope SynchScope) {
4594 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4595 Alignment = getEVTAlignment(MemVT);
4597 MachineFunction &MF = getMachineFunction();
4598 // An atomic store does not load. An atomic load does not store.
4599 // (An atomicrmw obviously both loads and stores.)
4600 // For now, atomics are considered to be volatile always, and they are
4602 // FIXME: Volatile isn't really correct; we should keep track of atomic
4603 // orderings in the memoperand.
4604 unsigned Flags = MachineMemOperand::MOVolatile;
4605 if (Opcode != ISD::ATOMIC_STORE)
4606 Flags |= MachineMemOperand::MOLoad;
4607 if (Opcode != ISD::ATOMIC_LOAD)
4608 Flags |= MachineMemOperand::MOStore;
4610 MachineMemOperand *MMO =
4611 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4612 MemVT.getStoreSize(), Alignment);
4614 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4615 Ordering, SynchScope);
4618 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4620 SDValue Ptr, SDValue Val,
4621 MachineMemOperand *MMO,
4622 AtomicOrdering Ordering,
4623 SynchronizationScope SynchScope) {
4624 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4625 Opcode == ISD::ATOMIC_LOAD_SUB ||
4626 Opcode == ISD::ATOMIC_LOAD_AND ||
4627 Opcode == ISD::ATOMIC_LOAD_OR ||
4628 Opcode == ISD::ATOMIC_LOAD_XOR ||
4629 Opcode == ISD::ATOMIC_LOAD_NAND ||
4630 Opcode == ISD::ATOMIC_LOAD_MIN ||
4631 Opcode == ISD::ATOMIC_LOAD_MAX ||
4632 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4633 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4634 Opcode == ISD::ATOMIC_SWAP ||
4635 Opcode == ISD::ATOMIC_STORE) &&
4636 "Invalid Atomic Op");
4638 EVT VT = Val.getValueType();
4640 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4641 getVTList(VT, MVT::Other);
4642 SDValue Ops[] = {Chain, Ptr, Val};
4643 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4646 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4647 EVT VT, SDValue Chain,
4649 MachineMemOperand *MMO,
4650 AtomicOrdering Ordering,
4651 SynchronizationScope SynchScope) {
4652 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4654 SDVTList VTs = getVTList(VT, MVT::Other);
4655 SDValue Ops[] = {Chain, Ptr};
4656 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4659 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4660 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4661 if (Ops.size() == 1)
4664 SmallVector<EVT, 4> VTs;
4665 VTs.reserve(Ops.size());
4666 for (unsigned i = 0; i < Ops.size(); ++i)
4667 VTs.push_back(Ops[i].getValueType());
4668 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4672 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4673 ArrayRef<SDValue> Ops,
4674 EVT MemVT, MachinePointerInfo PtrInfo,
4675 unsigned Align, bool Vol,
4676 bool ReadMem, bool WriteMem, unsigned Size) {
4677 if (Align == 0) // Ensure that codegen never sees alignment 0
4678 Align = getEVTAlignment(MemVT);
4680 MachineFunction &MF = getMachineFunction();
4683 Flags |= MachineMemOperand::MOStore;
4685 Flags |= MachineMemOperand::MOLoad;
4687 Flags |= MachineMemOperand::MOVolatile;
4689 Size = MemVT.getStoreSize();
4690 MachineMemOperand *MMO =
4691 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4693 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4697 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4698 ArrayRef<SDValue> Ops, EVT MemVT,
4699 MachineMemOperand *MMO) {
4700 assert((Opcode == ISD::INTRINSIC_VOID ||
4701 Opcode == ISD::INTRINSIC_W_CHAIN ||
4702 Opcode == ISD::PREFETCH ||
4703 Opcode == ISD::LIFETIME_START ||
4704 Opcode == ISD::LIFETIME_END ||
4705 (Opcode <= INT_MAX &&
4706 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4707 "Opcode is not a memory-accessing opcode!");
4709 // Memoize the node unless it returns a flag.
4710 MemIntrinsicSDNode *N;
4711 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4712 FoldingSetNodeID ID;
4713 AddNodeIDNode(ID, Opcode, VTList, Ops);
4714 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4716 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4717 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4718 return SDValue(E, 0);
4721 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4722 dl.getDebugLoc(), VTList, Ops,
4724 CSEMap.InsertNode(N, IP);
4726 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4727 dl.getDebugLoc(), VTList, Ops,
4731 return SDValue(N, 0);
4734 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4735 /// MachinePointerInfo record from it. This is particularly useful because the
4736 /// code generator has many cases where it doesn't bother passing in a
4737 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4738 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4739 // If this is FI+Offset, we can model it.
4740 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4741 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4743 // If this is (FI+Offset1)+Offset2, we can model it.
4744 if (Ptr.getOpcode() != ISD::ADD ||
4745 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4746 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4747 return MachinePointerInfo();
4749 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4750 return MachinePointerInfo::getFixedStack(FI, Offset+
4751 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
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, SDValue OffsetOp) {
4759 // If the 'Offset' value isn't a constant, we can't handle this.
4760 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4761 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4762 if (OffsetOp.getOpcode() == ISD::UNDEF)
4763 return InferPointerInfo(Ptr);
4764 return MachinePointerInfo();
4769 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4770 EVT VT, SDLoc dl, SDValue Chain,
4771 SDValue Ptr, SDValue Offset,
4772 MachinePointerInfo PtrInfo, EVT MemVT,
4773 bool isVolatile, bool isNonTemporal, bool isInvariant,
4774 unsigned Alignment, const AAMDNodes &AAInfo,
4775 const MDNode *Ranges) {
4776 assert(Chain.getValueType() == MVT::Other &&
4777 "Invalid chain type");
4778 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4779 Alignment = getEVTAlignment(VT);
4781 unsigned Flags = MachineMemOperand::MOLoad;
4783 Flags |= MachineMemOperand::MOVolatile;
4785 Flags |= MachineMemOperand::MONonTemporal;
4787 Flags |= MachineMemOperand::MOInvariant;
4789 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4791 if (PtrInfo.V.isNull())
4792 PtrInfo = InferPointerInfo(Ptr, Offset);
4794 MachineFunction &MF = getMachineFunction();
4795 MachineMemOperand *MMO =
4796 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4798 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4802 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4803 EVT VT, SDLoc dl, SDValue Chain,
4804 SDValue Ptr, SDValue Offset, EVT MemVT,
4805 MachineMemOperand *MMO) {
4807 ExtType = ISD::NON_EXTLOAD;
4808 } else if (ExtType == ISD::NON_EXTLOAD) {
4809 assert(VT == MemVT && "Non-extending load from different memory type!");
4812 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4813 "Should only be an extending load, not truncating!");
4814 assert(VT.isInteger() == MemVT.isInteger() &&
4815 "Cannot convert from FP to Int or Int -> FP!");
4816 assert(VT.isVector() == MemVT.isVector() &&
4817 "Cannot use an ext load to convert to or from a vector!");
4818 assert((!VT.isVector() ||
4819 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4820 "Cannot use an ext load to change the number of vector elements!");
4823 bool Indexed = AM != ISD::UNINDEXED;
4824 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4825 "Unindexed load with an offset!");
4827 SDVTList VTs = Indexed ?
4828 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4829 SDValue Ops[] = { Chain, Ptr, Offset };
4830 FoldingSetNodeID ID;
4831 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4832 ID.AddInteger(MemVT.getRawBits());
4833 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4834 MMO->isNonTemporal(),
4835 MMO->isInvariant()));
4836 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4838 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4839 cast<LoadSDNode>(E)->refineAlignment(MMO);
4840 return SDValue(E, 0);
4842 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4843 dl.getDebugLoc(), VTs, AM, ExtType,
4845 CSEMap.InsertNode(N, IP);
4847 return SDValue(N, 0);
4850 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4851 SDValue Chain, SDValue Ptr,
4852 MachinePointerInfo PtrInfo,
4853 bool isVolatile, bool isNonTemporal,
4854 bool isInvariant, unsigned Alignment,
4855 const AAMDNodes &AAInfo,
4856 const MDNode *Ranges) {
4857 SDValue Undef = getUNDEF(Ptr.getValueType());
4858 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4859 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4863 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4864 SDValue Chain, SDValue Ptr,
4865 MachineMemOperand *MMO) {
4866 SDValue Undef = getUNDEF(Ptr.getValueType());
4867 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4871 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4872 SDValue Chain, SDValue Ptr,
4873 MachinePointerInfo PtrInfo, EVT MemVT,
4874 bool isVolatile, bool isNonTemporal,
4875 bool isInvariant, unsigned Alignment,
4876 const AAMDNodes &AAInfo) {
4877 SDValue Undef = getUNDEF(Ptr.getValueType());
4878 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4879 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4884 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4885 SDValue Chain, SDValue Ptr, EVT MemVT,
4886 MachineMemOperand *MMO) {
4887 SDValue Undef = getUNDEF(Ptr.getValueType());
4888 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4893 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4894 SDValue Offset, ISD::MemIndexedMode AM) {
4895 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4896 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4897 "Load is already a indexed load!");
4898 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4899 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4900 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4901 false, LD->getAlignment());
4904 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4905 SDValue Ptr, MachinePointerInfo PtrInfo,
4906 bool isVolatile, bool isNonTemporal,
4907 unsigned Alignment, const AAMDNodes &AAInfo) {
4908 assert(Chain.getValueType() == MVT::Other &&
4909 "Invalid chain type");
4910 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4911 Alignment = getEVTAlignment(Val.getValueType());
4913 unsigned Flags = MachineMemOperand::MOStore;
4915 Flags |= MachineMemOperand::MOVolatile;
4917 Flags |= MachineMemOperand::MONonTemporal;
4919 if (PtrInfo.V.isNull())
4920 PtrInfo = InferPointerInfo(Ptr);
4922 MachineFunction &MF = getMachineFunction();
4923 MachineMemOperand *MMO =
4924 MF.getMachineMemOperand(PtrInfo, Flags,
4925 Val.getValueType().getStoreSize(), Alignment,
4928 return getStore(Chain, dl, Val, Ptr, MMO);
4931 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4932 SDValue Ptr, MachineMemOperand *MMO) {
4933 assert(Chain.getValueType() == MVT::Other &&
4934 "Invalid chain type");
4935 EVT VT = Val.getValueType();
4936 SDVTList VTs = getVTList(MVT::Other);
4937 SDValue Undef = getUNDEF(Ptr.getValueType());
4938 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4939 FoldingSetNodeID ID;
4940 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4941 ID.AddInteger(VT.getRawBits());
4942 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4943 MMO->isNonTemporal(), MMO->isInvariant()));
4944 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4946 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4947 cast<StoreSDNode>(E)->refineAlignment(MMO);
4948 return SDValue(E, 0);
4950 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4951 dl.getDebugLoc(), VTs,
4952 ISD::UNINDEXED, false, VT, MMO);
4953 CSEMap.InsertNode(N, IP);
4955 return SDValue(N, 0);
4958 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4959 SDValue Ptr, MachinePointerInfo PtrInfo,
4960 EVT SVT,bool isVolatile, bool isNonTemporal,
4962 const AAMDNodes &AAInfo) {
4963 assert(Chain.getValueType() == MVT::Other &&
4964 "Invalid chain type");
4965 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4966 Alignment = getEVTAlignment(SVT);
4968 unsigned Flags = MachineMemOperand::MOStore;
4970 Flags |= MachineMemOperand::MOVolatile;
4972 Flags |= MachineMemOperand::MONonTemporal;
4974 if (PtrInfo.V.isNull())
4975 PtrInfo = InferPointerInfo(Ptr);
4977 MachineFunction &MF = getMachineFunction();
4978 MachineMemOperand *MMO =
4979 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4982 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4985 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4986 SDValue Ptr, EVT SVT,
4987 MachineMemOperand *MMO) {
4988 EVT VT = Val.getValueType();
4990 assert(Chain.getValueType() == MVT::Other &&
4991 "Invalid chain type");
4993 return getStore(Chain, dl, Val, Ptr, MMO);
4995 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4996 "Should only be a truncating store, not extending!");
4997 assert(VT.isInteger() == SVT.isInteger() &&
4998 "Can't do FP-INT conversion!");
4999 assert(VT.isVector() == SVT.isVector() &&
5000 "Cannot use trunc store to convert to or from a vector!");
5001 assert((!VT.isVector() ||
5002 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5003 "Cannot use trunc store to change the number of vector elements!");
5005 SDVTList VTs = getVTList(MVT::Other);
5006 SDValue Undef = getUNDEF(Ptr.getValueType());
5007 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5008 FoldingSetNodeID ID;
5009 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5010 ID.AddInteger(SVT.getRawBits());
5011 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5012 MMO->isNonTemporal(), MMO->isInvariant()));
5013 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5015 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5016 cast<StoreSDNode>(E)->refineAlignment(MMO);
5017 return SDValue(E, 0);
5019 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5020 dl.getDebugLoc(), VTs,
5021 ISD::UNINDEXED, true, SVT, MMO);
5022 CSEMap.InsertNode(N, IP);
5024 return SDValue(N, 0);
5028 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5029 SDValue Offset, ISD::MemIndexedMode AM) {
5030 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5031 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5032 "Store is already a indexed store!");
5033 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5034 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5035 FoldingSetNodeID ID;
5036 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5037 ID.AddInteger(ST->getMemoryVT().getRawBits());
5038 ID.AddInteger(ST->getRawSubclassData());
5039 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5041 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5042 return SDValue(E, 0);
5044 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5045 dl.getDebugLoc(), VTs, AM,
5046 ST->isTruncatingStore(),
5048 ST->getMemOperand());
5049 CSEMap.InsertNode(N, IP);
5051 return SDValue(N, 0);
5055 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5056 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5057 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5059 SDVTList VTs = getVTList(VT, MVT::Other);
5060 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5061 FoldingSetNodeID ID;
5062 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5063 ID.AddInteger(VT.getRawBits());
5064 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5066 MMO->isNonTemporal(),
5067 MMO->isInvariant()));
5068 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5070 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5071 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5072 return SDValue(E, 0);
5074 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5075 dl.getDebugLoc(), Ops, 4, VTs,
5077 CSEMap.InsertNode(N, IP);
5079 return SDValue(N, 0);
5082 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5083 SDValue Ptr, SDValue Mask, EVT MemVT,
5084 MachineMemOperand *MMO, bool isTrunc) {
5085 assert(Chain.getValueType() == MVT::Other &&
5086 "Invalid chain type");
5087 EVT VT = Val.getValueType();
5088 SDVTList VTs = getVTList(MVT::Other);
5089 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5090 FoldingSetNodeID ID;
5091 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5092 ID.AddInteger(VT.getRawBits());
5093 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5094 MMO->isNonTemporal(), MMO->isInvariant()));
5095 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5097 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5098 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5099 return SDValue(E, 0);
5101 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5102 dl.getDebugLoc(), Ops, 4,
5103 VTs, isTrunc, MemVT, MMO);
5104 CSEMap.InsertNode(N, IP);
5106 return SDValue(N, 0);
5110 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5111 ArrayRef<SDValue> Ops,
5112 MachineMemOperand *MMO) {
5114 FoldingSetNodeID ID;
5115 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5116 ID.AddInteger(VT.getRawBits());
5117 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5119 MMO->isNonTemporal(),
5120 MMO->isInvariant()));
5121 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5123 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5124 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5125 return SDValue(E, 0);
5127 MaskedGatherSDNode *N =
5128 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5130 CSEMap.InsertNode(N, IP);
5132 return SDValue(N, 0);
5135 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5136 ArrayRef<SDValue> Ops,
5137 MachineMemOperand *MMO) {
5138 FoldingSetNodeID ID;
5139 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5140 ID.AddInteger(VT.getRawBits());
5141 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5142 MMO->isNonTemporal(),
5143 MMO->isInvariant()));
5144 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5146 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5147 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5148 return SDValue(E, 0);
5151 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5153 CSEMap.InsertNode(N, IP);
5155 return SDValue(N, 0);
5158 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5159 SDValue Chain, SDValue Ptr,
5162 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5163 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5166 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5167 ArrayRef<SDUse> Ops) {
5168 switch (Ops.size()) {
5169 case 0: return getNode(Opcode, DL, VT);
5170 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5171 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5172 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5176 // Copy from an SDUse array into an SDValue array for use with
5177 // the regular getNode logic.
5178 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5179 return getNode(Opcode, DL, VT, NewOps);
5182 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5183 ArrayRef<SDValue> Ops) {
5184 unsigned NumOps = Ops.size();
5186 case 0: return getNode(Opcode, DL, VT);
5187 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5188 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5189 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5195 case ISD::SELECT_CC: {
5196 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5197 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5198 "LHS and RHS of condition must have same type!");
5199 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5200 "True and False arms of SelectCC must have same type!");
5201 assert(Ops[2].getValueType() == VT &&
5202 "select_cc node must be of same type as true and false value!");
5206 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5207 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5208 "LHS/RHS of comparison should match types!");
5215 SDVTList VTs = getVTList(VT);
5217 if (VT != MVT::Glue) {
5218 FoldingSetNodeID ID;
5219 AddNodeIDNode(ID, Opcode, VTs, Ops);
5222 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5223 return SDValue(E, 0);
5225 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5227 CSEMap.InsertNode(N, IP);
5229 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5234 return SDValue(N, 0);
5237 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5238 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5239 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5242 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5243 ArrayRef<SDValue> Ops) {
5244 if (VTList.NumVTs == 1)
5245 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5249 // FIXME: figure out how to safely handle things like
5250 // int foo(int x) { return 1 << (x & 255); }
5251 // int bar() { return foo(256); }
5252 case ISD::SRA_PARTS:
5253 case ISD::SRL_PARTS:
5254 case ISD::SHL_PARTS:
5255 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5256 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5257 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5258 else if (N3.getOpcode() == ISD::AND)
5259 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5260 // If the and is only masking out bits that cannot effect the shift,
5261 // eliminate the and.
5262 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5263 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5264 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5270 // Memoize the node unless it returns a flag.
5272 unsigned NumOps = Ops.size();
5273 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5274 FoldingSetNodeID ID;
5275 AddNodeIDNode(ID, Opcode, VTList, Ops);
5277 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5278 return SDValue(E, 0);
5281 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5282 DL.getDebugLoc(), VTList, Ops[0]);
5283 } else if (NumOps == 2) {
5284 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5285 DL.getDebugLoc(), VTList, Ops[0],
5287 } else if (NumOps == 3) {
5288 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5289 DL.getDebugLoc(), VTList, Ops[0],
5292 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5295 CSEMap.InsertNode(N, IP);
5298 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5299 DL.getDebugLoc(), VTList, Ops[0]);
5300 } else if (NumOps == 2) {
5301 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5302 DL.getDebugLoc(), VTList, Ops[0],
5304 } else if (NumOps == 3) {
5305 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5306 DL.getDebugLoc(), VTList, Ops[0],
5309 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5314 return SDValue(N, 0);
5317 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5318 return getNode(Opcode, DL, VTList, None);
5321 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5323 SDValue Ops[] = { N1 };
5324 return getNode(Opcode, DL, VTList, Ops);
5327 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5328 SDValue N1, SDValue N2) {
5329 SDValue Ops[] = { N1, N2 };
5330 return getNode(Opcode, DL, VTList, Ops);
5333 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5334 SDValue N1, SDValue N2, SDValue N3) {
5335 SDValue Ops[] = { N1, N2, N3 };
5336 return getNode(Opcode, DL, VTList, Ops);
5339 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5340 SDValue N1, SDValue N2, SDValue N3,
5342 SDValue Ops[] = { N1, N2, N3, N4 };
5343 return getNode(Opcode, DL, VTList, Ops);
5346 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5347 SDValue N1, SDValue N2, SDValue N3,
5348 SDValue N4, SDValue N5) {
5349 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5350 return getNode(Opcode, DL, VTList, Ops);
5353 SDVTList SelectionDAG::getVTList(EVT VT) {
5354 return makeVTList(SDNode::getValueTypeList(VT), 1);
5357 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5358 FoldingSetNodeID ID;
5360 ID.AddInteger(VT1.getRawBits());
5361 ID.AddInteger(VT2.getRawBits());
5364 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5366 EVT *Array = Allocator.Allocate<EVT>(2);
5369 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5370 VTListMap.InsertNode(Result, IP);
5372 return Result->getSDVTList();
5375 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5376 FoldingSetNodeID ID;
5378 ID.AddInteger(VT1.getRawBits());
5379 ID.AddInteger(VT2.getRawBits());
5380 ID.AddInteger(VT3.getRawBits());
5383 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5385 EVT *Array = Allocator.Allocate<EVT>(3);
5389 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5390 VTListMap.InsertNode(Result, IP);
5392 return Result->getSDVTList();
5395 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5396 FoldingSetNodeID ID;
5398 ID.AddInteger(VT1.getRawBits());
5399 ID.AddInteger(VT2.getRawBits());
5400 ID.AddInteger(VT3.getRawBits());
5401 ID.AddInteger(VT4.getRawBits());
5404 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5406 EVT *Array = Allocator.Allocate<EVT>(4);
5411 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5412 VTListMap.InsertNode(Result, IP);
5414 return Result->getSDVTList();
5417 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5418 unsigned NumVTs = VTs.size();
5419 FoldingSetNodeID ID;
5420 ID.AddInteger(NumVTs);
5421 for (unsigned index = 0; index < NumVTs; index++) {
5422 ID.AddInteger(VTs[index].getRawBits());
5426 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5428 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5429 std::copy(VTs.begin(), VTs.end(), Array);
5430 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5431 VTListMap.InsertNode(Result, IP);
5433 return Result->getSDVTList();
5437 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5438 /// specified operands. If the resultant node already exists in the DAG,
5439 /// this does not modify the specified node, instead it returns the node that
5440 /// already exists. If the resultant node does not exist in the DAG, the
5441 /// input node is returned. As a degenerate case, if you specify the same
5442 /// input operands as the node already has, the input node is returned.
5443 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5444 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5446 // Check to see if there is no change.
5447 if (Op == N->getOperand(0)) return N;
5449 // See if the modified node already exists.
5450 void *InsertPos = nullptr;
5451 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5454 // Nope it doesn't. Remove the node from its current place in the maps.
5456 if (!RemoveNodeFromCSEMaps(N))
5457 InsertPos = nullptr;
5459 // Now we update the operands.
5460 N->OperandList[0].set(Op);
5462 // If this gets put into a CSE map, add it.
5463 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5467 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5468 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5470 // Check to see if there is no change.
5471 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5472 return N; // No operands changed, just return the input node.
5474 // See if the modified node already exists.
5475 void *InsertPos = nullptr;
5476 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5479 // Nope it doesn't. Remove the node from its current place in the maps.
5481 if (!RemoveNodeFromCSEMaps(N))
5482 InsertPos = nullptr;
5484 // Now we update the operands.
5485 if (N->OperandList[0] != Op1)
5486 N->OperandList[0].set(Op1);
5487 if (N->OperandList[1] != Op2)
5488 N->OperandList[1].set(Op2);
5490 // If this gets put into a CSE map, add it.
5491 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5495 SDNode *SelectionDAG::
5496 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5497 SDValue Ops[] = { Op1, Op2, Op3 };
5498 return UpdateNodeOperands(N, Ops);
5501 SDNode *SelectionDAG::
5502 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5503 SDValue Op3, SDValue Op4) {
5504 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5505 return UpdateNodeOperands(N, Ops);
5508 SDNode *SelectionDAG::
5509 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5510 SDValue Op3, SDValue Op4, SDValue Op5) {
5511 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5512 return UpdateNodeOperands(N, Ops);
5515 SDNode *SelectionDAG::
5516 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5517 unsigned NumOps = Ops.size();
5518 assert(N->getNumOperands() == NumOps &&
5519 "Update with wrong number of operands");
5521 // If no operands changed just return the input node.
5522 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5525 // See if the modified node already exists.
5526 void *InsertPos = nullptr;
5527 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5530 // Nope it doesn't. Remove the node from its current place in the maps.
5532 if (!RemoveNodeFromCSEMaps(N))
5533 InsertPos = nullptr;
5535 // Now we update the operands.
5536 for (unsigned i = 0; i != NumOps; ++i)
5537 if (N->OperandList[i] != Ops[i])
5538 N->OperandList[i].set(Ops[i]);
5540 // If this gets put into a CSE map, add it.
5541 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5545 /// DropOperands - Release the operands and set this node to have
5547 void SDNode::DropOperands() {
5548 // Unlike the code in MorphNodeTo that does this, we don't need to
5549 // watch for dead nodes here.
5550 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5556 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5559 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5561 SDVTList VTs = getVTList(VT);
5562 return SelectNodeTo(N, MachineOpc, VTs, None);
5565 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5566 EVT VT, SDValue Op1) {
5567 SDVTList VTs = getVTList(VT);
5568 SDValue Ops[] = { Op1 };
5569 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5572 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5573 EVT VT, SDValue Op1,
5575 SDVTList VTs = getVTList(VT);
5576 SDValue Ops[] = { Op1, Op2 };
5577 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5580 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5581 EVT VT, SDValue Op1,
5582 SDValue Op2, SDValue Op3) {
5583 SDVTList VTs = getVTList(VT);
5584 SDValue Ops[] = { Op1, Op2, Op3 };
5585 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5588 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5589 EVT VT, ArrayRef<SDValue> Ops) {
5590 SDVTList VTs = getVTList(VT);
5591 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5594 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5595 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5596 SDVTList VTs = getVTList(VT1, VT2);
5597 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5600 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5602 SDVTList VTs = getVTList(VT1, VT2);
5603 return SelectNodeTo(N, MachineOpc, VTs, None);
5606 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5607 EVT VT1, EVT VT2, EVT VT3,
5608 ArrayRef<SDValue> Ops) {
5609 SDVTList VTs = getVTList(VT1, VT2, VT3);
5610 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5613 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5614 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5615 ArrayRef<SDValue> Ops) {
5616 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5617 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5620 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5623 SDVTList VTs = getVTList(VT1, VT2);
5624 SDValue Ops[] = { Op1 };
5625 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5628 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5630 SDValue Op1, SDValue Op2) {
5631 SDVTList VTs = getVTList(VT1, VT2);
5632 SDValue Ops[] = { Op1, Op2 };
5633 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5636 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5638 SDValue Op1, SDValue Op2,
5640 SDVTList VTs = getVTList(VT1, VT2);
5641 SDValue Ops[] = { Op1, Op2, Op3 };
5642 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5645 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5646 EVT VT1, EVT VT2, EVT VT3,
5647 SDValue Op1, SDValue Op2,
5649 SDVTList VTs = getVTList(VT1, VT2, VT3);
5650 SDValue Ops[] = { Op1, Op2, Op3 };
5651 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5654 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5655 SDVTList VTs,ArrayRef<SDValue> Ops) {
5656 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5657 // Reset the NodeID to -1.
5662 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5663 /// the line number information on the merged node since it is not possible to
5664 /// preserve the information that operation is associated with multiple lines.
5665 /// This will make the debugger working better at -O0, were there is a higher
5666 /// probability having other instructions associated with that line.
5668 /// For IROrder, we keep the smaller of the two
5669 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5670 DebugLoc NLoc = N->getDebugLoc();
5671 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5672 N->setDebugLoc(DebugLoc());
5674 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5675 N->setIROrder(Order);
5679 /// MorphNodeTo - This *mutates* the specified node to have the specified
5680 /// return type, opcode, and operands.
5682 /// Note that MorphNodeTo returns the resultant node. If there is already a
5683 /// node of the specified opcode and operands, it returns that node instead of
5684 /// the current one. Note that the SDLoc need not be the same.
5686 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5687 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5688 /// node, and because it doesn't require CSE recalculation for any of
5689 /// the node's users.
5691 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5692 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5693 /// the legalizer which maintain worklists that would need to be updated when
5694 /// deleting things.
5695 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5696 SDVTList VTs, ArrayRef<SDValue> Ops) {
5697 unsigned NumOps = Ops.size();
5698 // If an identical node already exists, use it.
5700 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5701 FoldingSetNodeID ID;
5702 AddNodeIDNode(ID, Opc, VTs, Ops);
5703 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5704 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5707 if (!RemoveNodeFromCSEMaps(N))
5710 // Start the morphing.
5712 N->ValueList = VTs.VTs;
5713 N->NumValues = VTs.NumVTs;
5715 // Clear the operands list, updating used nodes to remove this from their
5716 // use list. Keep track of any operands that become dead as a result.
5717 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5718 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5720 SDNode *Used = Use.getNode();
5722 if (Used->use_empty())
5723 DeadNodeSet.insert(Used);
5726 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5727 // Initialize the memory references information.
5728 MN->setMemRefs(nullptr, nullptr);
5729 // If NumOps is larger than the # of operands we can have in a
5730 // MachineSDNode, reallocate the operand list.
5731 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5732 if (MN->OperandsNeedDelete)
5733 delete[] MN->OperandList;
5734 if (NumOps > array_lengthof(MN->LocalOperands))
5735 // We're creating a final node that will live unmorphed for the
5736 // remainder of the current SelectionDAG iteration, so we can allocate
5737 // the operands directly out of a pool with no recycling metadata.
5738 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5739 Ops.data(), NumOps);
5741 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5742 MN->OperandsNeedDelete = false;
5744 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5746 // If NumOps is larger than the # of operands we currently have, reallocate
5747 // the operand list.
5748 if (NumOps > N->NumOperands) {
5749 if (N->OperandsNeedDelete)
5750 delete[] N->OperandList;
5751 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5752 N->OperandsNeedDelete = true;
5754 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5757 // Delete any nodes that are still dead after adding the uses for the
5759 if (!DeadNodeSet.empty()) {
5760 SmallVector<SDNode *, 16> DeadNodes;
5761 for (SDNode *N : DeadNodeSet)
5763 DeadNodes.push_back(N);
5764 RemoveDeadNodes(DeadNodes);
5768 CSEMap.InsertNode(N, IP); // Memoize the new node.
5773 /// getMachineNode - These are used for target selectors to create a new node
5774 /// with specified return type(s), MachineInstr opcode, and operands.
5776 /// Note that getMachineNode returns the resultant node. If there is already a
5777 /// node of the specified opcode and operands, it returns that node instead of
5778 /// the current one.
5780 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5781 SDVTList VTs = getVTList(VT);
5782 return getMachineNode(Opcode, dl, VTs, None);
5786 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5787 SDVTList VTs = getVTList(VT);
5788 SDValue Ops[] = { Op1 };
5789 return getMachineNode(Opcode, dl, VTs, Ops);
5793 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5794 SDValue Op1, SDValue Op2) {
5795 SDVTList VTs = getVTList(VT);
5796 SDValue Ops[] = { Op1, Op2 };
5797 return getMachineNode(Opcode, dl, VTs, Ops);
5801 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5802 SDValue Op1, SDValue Op2, SDValue Op3) {
5803 SDVTList VTs = getVTList(VT);
5804 SDValue Ops[] = { Op1, Op2, Op3 };
5805 return getMachineNode(Opcode, dl, VTs, Ops);
5809 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5810 ArrayRef<SDValue> Ops) {
5811 SDVTList VTs = getVTList(VT);
5812 return getMachineNode(Opcode, dl, VTs, Ops);
5816 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5817 SDVTList VTs = getVTList(VT1, VT2);
5818 return getMachineNode(Opcode, dl, VTs, None);
5822 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5823 EVT VT1, EVT VT2, SDValue Op1) {
5824 SDVTList VTs = getVTList(VT1, VT2);
5825 SDValue Ops[] = { Op1 };
5826 return getMachineNode(Opcode, dl, VTs, Ops);
5830 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5831 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5832 SDVTList VTs = getVTList(VT1, VT2);
5833 SDValue Ops[] = { Op1, Op2 };
5834 return getMachineNode(Opcode, dl, VTs, Ops);
5838 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5839 EVT VT1, EVT VT2, SDValue Op1,
5840 SDValue Op2, SDValue Op3) {
5841 SDVTList VTs = getVTList(VT1, VT2);
5842 SDValue Ops[] = { Op1, Op2, Op3 };
5843 return getMachineNode(Opcode, dl, VTs, Ops);
5847 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5849 ArrayRef<SDValue> Ops) {
5850 SDVTList VTs = getVTList(VT1, VT2);
5851 return getMachineNode(Opcode, dl, VTs, Ops);
5855 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5856 EVT VT1, EVT VT2, EVT VT3,
5857 SDValue Op1, SDValue Op2) {
5858 SDVTList VTs = getVTList(VT1, VT2, VT3);
5859 SDValue Ops[] = { Op1, Op2 };
5860 return getMachineNode(Opcode, dl, VTs, Ops);
5864 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5865 EVT VT1, EVT VT2, EVT VT3,
5866 SDValue Op1, SDValue Op2, SDValue Op3) {
5867 SDVTList VTs = getVTList(VT1, VT2, VT3);
5868 SDValue Ops[] = { Op1, Op2, Op3 };
5869 return getMachineNode(Opcode, dl, VTs, Ops);
5873 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5874 EVT VT1, EVT VT2, EVT VT3,
5875 ArrayRef<SDValue> Ops) {
5876 SDVTList VTs = getVTList(VT1, VT2, VT3);
5877 return getMachineNode(Opcode, dl, VTs, Ops);
5881 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5882 EVT VT2, EVT VT3, EVT VT4,
5883 ArrayRef<SDValue> Ops) {
5884 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5885 return getMachineNode(Opcode, dl, VTs, Ops);
5889 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5890 ArrayRef<EVT> ResultTys,
5891 ArrayRef<SDValue> Ops) {
5892 SDVTList VTs = getVTList(ResultTys);
5893 return getMachineNode(Opcode, dl, VTs, Ops);
5897 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5898 ArrayRef<SDValue> OpsArray) {
5899 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5902 const SDValue *Ops = OpsArray.data();
5903 unsigned NumOps = OpsArray.size();
5906 FoldingSetNodeID ID;
5907 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5909 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5910 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5914 // Allocate a new MachineSDNode.
5915 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5916 DL.getDebugLoc(), VTs);
5918 // Initialize the operands list.
5919 if (NumOps > array_lengthof(N->LocalOperands))
5920 // We're creating a final node that will live unmorphed for the
5921 // remainder of the current SelectionDAG iteration, so we can allocate
5922 // the operands directly out of a pool with no recycling metadata.
5923 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5926 N->InitOperands(N->LocalOperands, Ops, NumOps);
5927 N->OperandsNeedDelete = false;
5930 CSEMap.InsertNode(N, IP);
5936 /// getTargetExtractSubreg - A convenience function for creating
5937 /// TargetOpcode::EXTRACT_SUBREG nodes.
5939 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5941 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5942 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5943 VT, Operand, SRIdxVal);
5944 return SDValue(Subreg, 0);
5947 /// getTargetInsertSubreg - A convenience function for creating
5948 /// TargetOpcode::INSERT_SUBREG nodes.
5950 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5951 SDValue Operand, SDValue Subreg) {
5952 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5953 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5954 VT, Operand, Subreg, SRIdxVal);
5955 return SDValue(Result, 0);
5958 /// getNodeIfExists - Get the specified node if it's already available, or
5959 /// else return NULL.
5960 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5961 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5963 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5964 FoldingSetNodeID ID;
5965 AddNodeIDNode(ID, Opcode, VTList, Ops);
5966 if (isBinOpWithFlags(Opcode))
5967 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5969 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5975 /// getDbgValue - Creates a SDDbgValue node.
5978 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5979 unsigned R, bool IsIndirect, uint64_t Off,
5980 DebugLoc DL, unsigned O) {
5981 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5982 "Expected inlined-at fields to agree");
5983 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5987 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5988 const Value *C, uint64_t Off,
5989 DebugLoc DL, unsigned O) {
5990 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5991 "Expected inlined-at fields to agree");
5992 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5996 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5997 unsigned FI, uint64_t Off,
5998 DebugLoc DL, unsigned O) {
5999 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6000 "Expected inlined-at fields to agree");
6001 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6006 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6007 /// pointed to by a use iterator is deleted, increment the use iterator
6008 /// so that it doesn't dangle.
6010 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6011 SDNode::use_iterator &UI;
6012 SDNode::use_iterator &UE;
6014 void NodeDeleted(SDNode *N, SDNode *E) override {
6015 // Increment the iterator as needed.
6016 while (UI != UE && N == *UI)
6021 RAUWUpdateListener(SelectionDAG &d,
6022 SDNode::use_iterator &ui,
6023 SDNode::use_iterator &ue)
6024 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6029 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6030 /// This can cause recursive merging of nodes in the DAG.
6032 /// This version assumes From has a single result value.
6034 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6035 SDNode *From = FromN.getNode();
6036 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6037 "Cannot replace with this method!");
6038 assert(From != To.getNode() && "Cannot replace uses of with self");
6040 // Iterate over all the existing uses of From. New uses will be added
6041 // to the beginning of the use list, which we avoid visiting.
6042 // This specifically avoids visiting uses of From that arise while the
6043 // replacement is happening, because any such uses would be the result
6044 // of CSE: If an existing node looks like From after one of its operands
6045 // is replaced by To, we don't want to replace of all its users with To
6046 // too. See PR3018 for more info.
6047 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6048 RAUWUpdateListener Listener(*this, UI, UE);
6052 // This node is about to morph, remove its old self from the CSE maps.
6053 RemoveNodeFromCSEMaps(User);
6055 // A user can appear in a use list multiple times, and when this
6056 // happens the uses are usually next to each other in the list.
6057 // To help reduce the number of CSE recomputations, process all
6058 // the uses of this user that we can find this way.
6060 SDUse &Use = UI.getUse();
6063 } while (UI != UE && *UI == User);
6065 // Now that we have modified User, add it back to the CSE maps. If it
6066 // already exists there, recursively merge the results together.
6067 AddModifiedNodeToCSEMaps(User);
6070 // If we just RAUW'd the root, take note.
6071 if (FromN == getRoot())
6075 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6076 /// This can cause recursive merging of nodes in the DAG.
6078 /// This version assumes that for each value of From, there is a
6079 /// corresponding value in To in the same position with the same type.
6081 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6083 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6084 assert((!From->hasAnyUseOfValue(i) ||
6085 From->getValueType(i) == To->getValueType(i)) &&
6086 "Cannot use this version of ReplaceAllUsesWith!");
6089 // Handle the trivial case.
6093 // Iterate over just the existing users of From. See the comments in
6094 // the ReplaceAllUsesWith above.
6095 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6096 RAUWUpdateListener Listener(*this, UI, UE);
6100 // This node is about to morph, remove its old self from the CSE maps.
6101 RemoveNodeFromCSEMaps(User);
6103 // A user can appear in a use list multiple times, and when this
6104 // happens the uses are usually next to each other in the list.
6105 // To help reduce the number of CSE recomputations, process all
6106 // the uses of this user that we can find this way.
6108 SDUse &Use = UI.getUse();
6111 } while (UI != UE && *UI == User);
6113 // Now that we have modified User, add it back to the CSE maps. If it
6114 // already exists there, recursively merge the results together.
6115 AddModifiedNodeToCSEMaps(User);
6118 // If we just RAUW'd the root, take note.
6119 if (From == getRoot().getNode())
6120 setRoot(SDValue(To, getRoot().getResNo()));
6123 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6124 /// This can cause recursive merging of nodes in the DAG.
6126 /// This version can replace From with any result values. To must match the
6127 /// number and types of values returned by From.
6128 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6129 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6130 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6132 // Iterate over just the existing users of From. See the comments in
6133 // the ReplaceAllUsesWith above.
6134 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6135 RAUWUpdateListener Listener(*this, UI, UE);
6139 // This node is about to morph, remove its old self from the CSE maps.
6140 RemoveNodeFromCSEMaps(User);
6142 // A user can appear in a use list multiple times, and when this
6143 // happens the uses are usually next to each other in the list.
6144 // To help reduce the number of CSE recomputations, process all
6145 // the uses of this user that we can find this way.
6147 SDUse &Use = UI.getUse();
6148 const SDValue &ToOp = To[Use.getResNo()];
6151 } while (UI != UE && *UI == User);
6153 // Now that we have modified User, add it back to the CSE maps. If it
6154 // already exists there, recursively merge the results together.
6155 AddModifiedNodeToCSEMaps(User);
6158 // If we just RAUW'd the root, take note.
6159 if (From == getRoot().getNode())
6160 setRoot(SDValue(To[getRoot().getResNo()]));
6163 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6164 /// uses of other values produced by From.getNode() alone. The Deleted
6165 /// vector is handled the same way as for ReplaceAllUsesWith.
6166 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6167 // Handle the really simple, really trivial case efficiently.
6168 if (From == To) return;
6170 // Handle the simple, trivial, case efficiently.
6171 if (From.getNode()->getNumValues() == 1) {
6172 ReplaceAllUsesWith(From, To);
6176 // Iterate over just the existing users of From. See the comments in
6177 // the ReplaceAllUsesWith above.
6178 SDNode::use_iterator UI = From.getNode()->use_begin(),
6179 UE = From.getNode()->use_end();
6180 RAUWUpdateListener Listener(*this, UI, UE);
6183 bool UserRemovedFromCSEMaps = false;
6185 // A user can appear in a use list multiple times, and when this
6186 // happens the uses are usually next to each other in the list.
6187 // To help reduce the number of CSE recomputations, process all
6188 // the uses of this user that we can find this way.
6190 SDUse &Use = UI.getUse();
6192 // Skip uses of different values from the same node.
6193 if (Use.getResNo() != From.getResNo()) {
6198 // If this node hasn't been modified yet, it's still in the CSE maps,
6199 // so remove its old self from the CSE maps.
6200 if (!UserRemovedFromCSEMaps) {
6201 RemoveNodeFromCSEMaps(User);
6202 UserRemovedFromCSEMaps = true;
6207 } while (UI != UE && *UI == User);
6209 // We are iterating over all uses of the From node, so if a use
6210 // doesn't use the specific value, no changes are made.
6211 if (!UserRemovedFromCSEMaps)
6214 // Now that we have modified User, add it back to the CSE maps. If it
6215 // already exists there, recursively merge the results together.
6216 AddModifiedNodeToCSEMaps(User);
6219 // If we just RAUW'd the root, take note.
6220 if (From == getRoot())
6225 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6226 /// to record information about a use.
6233 /// operator< - Sort Memos by User.
6234 bool operator<(const UseMemo &L, const UseMemo &R) {
6235 return (intptr_t)L.User < (intptr_t)R.User;
6239 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6240 /// uses of other values produced by From.getNode() alone. The same value
6241 /// may appear in both the From and To list. The Deleted vector is
6242 /// handled the same way as for ReplaceAllUsesWith.
6243 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6246 // Handle the simple, trivial case efficiently.
6248 return ReplaceAllUsesOfValueWith(*From, *To);
6250 // Read up all the uses and make records of them. This helps
6251 // processing new uses that are introduced during the
6252 // replacement process.
6253 SmallVector<UseMemo, 4> Uses;
6254 for (unsigned i = 0; i != Num; ++i) {
6255 unsigned FromResNo = From[i].getResNo();
6256 SDNode *FromNode = From[i].getNode();
6257 for (SDNode::use_iterator UI = FromNode->use_begin(),
6258 E = FromNode->use_end(); UI != E; ++UI) {
6259 SDUse &Use = UI.getUse();
6260 if (Use.getResNo() == FromResNo) {
6261 UseMemo Memo = { *UI, i, &Use };
6262 Uses.push_back(Memo);
6267 // Sort the uses, so that all the uses from a given User are together.
6268 std::sort(Uses.begin(), Uses.end());
6270 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6271 UseIndex != UseIndexEnd; ) {
6272 // We know that this user uses some value of From. If it is the right
6273 // value, update it.
6274 SDNode *User = Uses[UseIndex].User;
6276 // This node is about to morph, remove its old self from the CSE maps.
6277 RemoveNodeFromCSEMaps(User);
6279 // The Uses array is sorted, so all the uses for a given User
6280 // are next to each other in the list.
6281 // To help reduce the number of CSE recomputations, process all
6282 // the uses of this user that we can find this way.
6284 unsigned i = Uses[UseIndex].Index;
6285 SDUse &Use = *Uses[UseIndex].Use;
6289 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6291 // Now that we have modified User, add it back to the CSE maps. If it
6292 // already exists there, recursively merge the results together.
6293 AddModifiedNodeToCSEMaps(User);
6297 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6298 /// based on their topological order. It returns the maximum id and a vector
6299 /// of the SDNodes* in assigned order by reference.
6300 unsigned SelectionDAG::AssignTopologicalOrder() {
6302 unsigned DAGSize = 0;
6304 // SortedPos tracks the progress of the algorithm. Nodes before it are
6305 // sorted, nodes after it are unsorted. When the algorithm completes
6306 // it is at the end of the list.
6307 allnodes_iterator SortedPos = allnodes_begin();
6309 // Visit all the nodes. Move nodes with no operands to the front of
6310 // the list immediately. Annotate nodes that do have operands with their
6311 // operand count. Before we do this, the Node Id fields of the nodes
6312 // may contain arbitrary values. After, the Node Id fields for nodes
6313 // before SortedPos will contain the topological sort index, and the
6314 // Node Id fields for nodes At SortedPos and after will contain the
6315 // count of outstanding operands.
6316 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6318 checkForCycles(N, this);
6319 unsigned Degree = N->getNumOperands();
6321 // A node with no uses, add it to the result array immediately.
6322 N->setNodeId(DAGSize++);
6323 allnodes_iterator Q = N;
6325 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6326 assert(SortedPos != AllNodes.end() && "Overran node list");
6329 // Temporarily use the Node Id as scratch space for the degree count.
6330 N->setNodeId(Degree);
6334 // Visit all the nodes. As we iterate, move nodes into sorted order,
6335 // such that by the time the end is reached all nodes will be sorted.
6336 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6338 checkForCycles(N, this);
6339 // N is in sorted position, so all its uses have one less operand
6340 // that needs to be sorted.
6341 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6344 unsigned Degree = P->getNodeId();
6345 assert(Degree != 0 && "Invalid node degree");
6348 // All of P's operands are sorted, so P may sorted now.
6349 P->setNodeId(DAGSize++);
6351 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6352 assert(SortedPos != AllNodes.end() && "Overran node list");
6355 // Update P's outstanding operand count.
6356 P->setNodeId(Degree);
6359 if (I == SortedPos) {
6362 dbgs() << "Overran sorted position:\n";
6363 S->dumprFull(this); dbgs() << "\n";
6364 dbgs() << "Checking if this is due to cycles\n";
6365 checkForCycles(this, true);
6367 llvm_unreachable(nullptr);
6371 assert(SortedPos == AllNodes.end() &&
6372 "Topological sort incomplete!");
6373 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6374 "First node in topological sort is not the entry token!");
6375 assert(AllNodes.front().getNodeId() == 0 &&
6376 "First node in topological sort has non-zero id!");
6377 assert(AllNodes.front().getNumOperands() == 0 &&
6378 "First node in topological sort has operands!");
6379 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6380 "Last node in topologic sort has unexpected id!");
6381 assert(AllNodes.back().use_empty() &&
6382 "Last node in topologic sort has users!");
6383 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6387 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6388 /// value is produced by SD.
6389 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6391 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6392 SD->setHasDebugValue(true);
6394 DbgInfo->add(DB, SD, isParameter);
6397 /// TransferDbgValues - Transfer SDDbgValues.
6398 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6399 if (From == To || !From.getNode()->getHasDebugValue())
6401 SDNode *FromNode = From.getNode();
6402 SDNode *ToNode = To.getNode();
6403 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6404 SmallVector<SDDbgValue *, 2> ClonedDVs;
6405 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6407 SDDbgValue *Dbg = *I;
6408 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6410 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6411 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6412 Dbg->getDebugLoc(), Dbg->getOrder());
6413 ClonedDVs.push_back(Clone);
6416 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6417 E = ClonedDVs.end(); I != E; ++I)
6418 AddDbgValue(*I, ToNode, false);
6421 //===----------------------------------------------------------------------===//
6423 //===----------------------------------------------------------------------===//
6425 HandleSDNode::~HandleSDNode() {
6429 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6430 DebugLoc DL, const GlobalValue *GA,
6431 EVT VT, int64_t o, unsigned char TF)
6432 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6436 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6437 SDValue X, unsigned SrcAS,
6439 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6440 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6442 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6443 EVT memvt, MachineMemOperand *mmo)
6444 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6445 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6446 MMO->isNonTemporal(), MMO->isInvariant());
6447 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6448 assert(isNonTemporal() == MMO->isNonTemporal() &&
6449 "Non-temporal encoding error!");
6450 // We check here that the size of the memory operand fits within the size of
6451 // the MMO. This is because the MMO might indicate only a possible address
6452 // range instead of specifying the affected memory addresses precisely.
6453 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6456 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6457 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6458 : SDNode(Opc, Order, dl, VTs, Ops),
6459 MemoryVT(memvt), MMO(mmo) {
6460 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6461 MMO->isNonTemporal(), MMO->isInvariant());
6462 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6463 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6466 /// Profile - Gather unique data for the node.
6468 void SDNode::Profile(FoldingSetNodeID &ID) const {
6469 AddNodeIDNode(ID, this);
6474 std::vector<EVT> VTs;
6477 VTs.reserve(MVT::LAST_VALUETYPE);
6478 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6479 VTs.push_back(MVT((MVT::SimpleValueType)i));
6484 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6485 static ManagedStatic<EVTArray> SimpleVTArray;
6486 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6488 /// getValueTypeList - Return a pointer to the specified value type.
6490 const EVT *SDNode::getValueTypeList(EVT VT) {
6491 if (VT.isExtended()) {
6492 sys::SmartScopedLock<true> Lock(*VTMutex);
6493 return &(*EVTs->insert(VT).first);
6495 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6496 "Value type out of range!");
6497 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6501 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6502 /// indicated value. This method ignores uses of other values defined by this
6504 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6505 assert(Value < getNumValues() && "Bad value!");
6507 // TODO: Only iterate over uses of a given value of the node
6508 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6509 if (UI.getUse().getResNo() == Value) {
6516 // Found exactly the right number of uses?
6521 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6522 /// value. This method ignores uses of other values defined by this operation.
6523 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6524 assert(Value < getNumValues() && "Bad value!");
6526 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6527 if (UI.getUse().getResNo() == Value)
6534 /// isOnlyUserOf - Return true if this node is the only use of N.
6536 bool SDNode::isOnlyUserOf(SDNode *N) const {
6538 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6549 /// isOperand - Return true if this node is an operand of N.
6551 bool SDValue::isOperandOf(SDNode *N) const {
6552 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6553 if (*this == N->getOperand(i))
6558 bool SDNode::isOperandOf(SDNode *N) const {
6559 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6560 if (this == N->OperandList[i].getNode())
6565 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6566 /// be a chain) reaches the specified operand without crossing any
6567 /// side-effecting instructions on any chain path. In practice, this looks
6568 /// through token factors and non-volatile loads. In order to remain efficient,
6569 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6570 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6571 unsigned Depth) const {
6572 if (*this == Dest) return true;
6574 // Don't search too deeply, we just want to be able to see through
6575 // TokenFactor's etc.
6576 if (Depth == 0) return false;
6578 // If this is a token factor, all inputs to the TF happen in parallel. If any
6579 // of the operands of the TF does not reach dest, then we cannot do the xform.
6580 if (getOpcode() == ISD::TokenFactor) {
6581 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6582 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6587 // Loads don't have side effects, look through them.
6588 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6589 if (!Ld->isVolatile())
6590 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6595 /// hasPredecessor - Return true if N is a predecessor of this node.
6596 /// N is either an operand of this node, or can be reached by recursively
6597 /// traversing up the operands.
6598 /// NOTE: This is an expensive method. Use it carefully.
6599 bool SDNode::hasPredecessor(const SDNode *N) const {
6600 SmallPtrSet<const SDNode *, 32> Visited;
6601 SmallVector<const SDNode *, 16> Worklist;
6602 return hasPredecessorHelper(N, Visited, Worklist);
6606 SDNode::hasPredecessorHelper(const SDNode *N,
6607 SmallPtrSetImpl<const SDNode *> &Visited,
6608 SmallVectorImpl<const SDNode *> &Worklist) const {
6609 if (Visited.empty()) {
6610 Worklist.push_back(this);
6612 // Take a look in the visited set. If we've already encountered this node
6613 // we needn't search further.
6614 if (Visited.count(N))
6618 // Haven't visited N yet. Continue the search.
6619 while (!Worklist.empty()) {
6620 const SDNode *M = Worklist.pop_back_val();
6621 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6622 SDNode *Op = M->getOperand(i).getNode();
6623 if (Visited.insert(Op).second)
6624 Worklist.push_back(Op);
6633 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6634 assert(Num < NumOperands && "Invalid child # of SDNode!");
6635 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6638 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6639 assert(N->getNumValues() == 1 &&
6640 "Can't unroll a vector with multiple results!");
6642 EVT VT = N->getValueType(0);
6643 unsigned NE = VT.getVectorNumElements();
6644 EVT EltVT = VT.getVectorElementType();
6647 SmallVector<SDValue, 8> Scalars;
6648 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6650 // If ResNE is 0, fully unroll the vector op.
6653 else if (NE > ResNE)
6657 for (i= 0; i != NE; ++i) {
6658 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6659 SDValue Operand = N->getOperand(j);
6660 EVT OperandVT = Operand.getValueType();
6661 if (OperandVT.isVector()) {
6662 // A vector operand; extract a single element.
6663 EVT OperandEltVT = OperandVT.getVectorElementType();
6664 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6667 getConstant(i, dl, TLI->getVectorIdxTy()));
6669 // A scalar operand; just use it as is.
6670 Operands[j] = Operand;
6674 switch (N->getOpcode()) {
6676 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6679 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6686 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6687 getShiftAmountOperand(Operands[0].getValueType(),
6690 case ISD::SIGN_EXTEND_INREG:
6691 case ISD::FP_ROUND_INREG: {
6692 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6693 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6695 getValueType(ExtVT)));
6700 for (; i < ResNE; ++i)
6701 Scalars.push_back(getUNDEF(EltVT));
6703 return getNode(ISD::BUILD_VECTOR, dl,
6704 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6708 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6709 /// location that is 'Dist' units away from the location that the 'Base' load
6710 /// is loading from.
6711 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6712 unsigned Bytes, int Dist) const {
6713 if (LD->getChain() != Base->getChain())
6715 EVT VT = LD->getValueType(0);
6716 if (VT.getSizeInBits() / 8 != Bytes)
6719 SDValue Loc = LD->getOperand(1);
6720 SDValue BaseLoc = Base->getOperand(1);
6721 if (Loc.getOpcode() == ISD::FrameIndex) {
6722 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6724 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6725 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6726 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6727 int FS = MFI->getObjectSize(FI);
6728 int BFS = MFI->getObjectSize(BFI);
6729 if (FS != BFS || FS != (int)Bytes) return false;
6730 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6734 if (isBaseWithConstantOffset(Loc)) {
6735 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6736 if (Loc.getOperand(0) == BaseLoc) {
6737 // If the base location is a simple address with no offset itself, then
6738 // the second load's first add operand should be the base address.
6739 if (LocOffset == Dist * (int)Bytes)
6741 } else if (isBaseWithConstantOffset(BaseLoc)) {
6742 // The base location itself has an offset, so subtract that value from the
6743 // second load's offset before comparing to distance * size.
6745 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6746 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6747 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6752 const GlobalValue *GV1 = nullptr;
6753 const GlobalValue *GV2 = nullptr;
6754 int64_t Offset1 = 0;
6755 int64_t Offset2 = 0;
6756 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6757 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6758 if (isGA1 && isGA2 && GV1 == GV2)
6759 return Offset1 == (Offset2 + Dist*Bytes);
6764 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6765 /// it cannot be inferred.
6766 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6767 // If this is a GlobalAddress + cst, return the alignment.
6768 const GlobalValue *GV;
6769 int64_t GVOffset = 0;
6770 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6771 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6772 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6773 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6774 *TLI->getDataLayout());
6775 unsigned AlignBits = KnownZero.countTrailingOnes();
6776 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6778 return MinAlign(Align, GVOffset);
6781 // If this is a direct reference to a stack slot, use information about the
6782 // stack slot's alignment.
6783 int FrameIdx = 1 << 31;
6784 int64_t FrameOffset = 0;
6785 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6786 FrameIdx = FI->getIndex();
6787 } else if (isBaseWithConstantOffset(Ptr) &&
6788 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6790 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6791 FrameOffset = Ptr.getConstantOperandVal(1);
6794 if (FrameIdx != (1 << 31)) {
6795 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6796 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6804 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6805 /// which is split (or expanded) into two not necessarily identical pieces.
6806 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6807 // Currently all types are split in half.
6809 if (!VT.isVector()) {
6810 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6812 unsigned NumElements = VT.getVectorNumElements();
6813 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6814 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6817 return std::make_pair(LoVT, HiVT);
6820 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6822 std::pair<SDValue, SDValue>
6823 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6825 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6826 N.getValueType().getVectorNumElements() &&
6827 "More vector elements requested than available!");
6829 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6830 getConstant(0, DL, TLI->getVectorIdxTy()));
6831 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6832 getConstant(LoVT.getVectorNumElements(), DL,
6833 TLI->getVectorIdxTy()));
6834 return std::make_pair(Lo, Hi);
6837 void SelectionDAG::ExtractVectorElements(SDValue Op,
6838 SmallVectorImpl<SDValue> &Args,
6839 unsigned Start, unsigned Count) {
6840 EVT VT = Op.getValueType();
6842 Count = VT.getVectorNumElements();
6844 EVT EltVT = VT.getVectorElementType();
6845 EVT IdxTy = TLI->getVectorIdxTy();
6847 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6848 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6849 Op, getConstant(i, SL, IdxTy)));
6853 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6854 unsigned GlobalAddressSDNode::getAddressSpace() const {
6855 return getGlobal()->getType()->getAddressSpace();
6859 Type *ConstantPoolSDNode::getType() const {
6860 if (isMachineConstantPoolEntry())
6861 return Val.MachineCPVal->getType();
6862 return Val.ConstVal->getType();
6865 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6867 unsigned &SplatBitSize,
6869 unsigned MinSplatBits,
6870 bool isBigEndian) const {
6871 EVT VT = getValueType(0);
6872 assert(VT.isVector() && "Expected a vector type");
6873 unsigned sz = VT.getSizeInBits();
6874 if (MinSplatBits > sz)
6877 SplatValue = APInt(sz, 0);
6878 SplatUndef = APInt(sz, 0);
6880 // Get the bits. Bits with undefined values (when the corresponding element
6881 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6882 // in SplatValue. If any of the values are not constant, give up and return
6884 unsigned int nOps = getNumOperands();
6885 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6886 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6888 for (unsigned j = 0; j < nOps; ++j) {
6889 unsigned i = isBigEndian ? nOps-1-j : j;
6890 SDValue OpVal = getOperand(i);
6891 unsigned BitPos = j * EltBitSize;
6893 if (OpVal.getOpcode() == ISD::UNDEF)
6894 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6895 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6896 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6897 zextOrTrunc(sz) << BitPos;
6898 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6899 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6904 // The build_vector is all constants or undefs. Find the smallest element
6905 // size that splats the vector.
6907 HasAnyUndefs = (SplatUndef != 0);
6910 unsigned HalfSize = sz / 2;
6911 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6912 APInt LowValue = SplatValue.trunc(HalfSize);
6913 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6914 APInt LowUndef = SplatUndef.trunc(HalfSize);
6916 // If the two halves do not match (ignoring undef bits), stop here.
6917 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6918 MinSplatBits > HalfSize)
6921 SplatValue = HighValue | LowValue;
6922 SplatUndef = HighUndef & LowUndef;
6931 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6932 if (UndefElements) {
6933 UndefElements->clear();
6934 UndefElements->resize(getNumOperands());
6937 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6938 SDValue Op = getOperand(i);
6939 if (Op.getOpcode() == ISD::UNDEF) {
6941 (*UndefElements)[i] = true;
6942 } else if (!Splatted) {
6944 } else if (Splatted != Op) {
6950 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6951 "Can only have a splat without a constant for all undefs.");
6952 return getOperand(0);
6959 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6960 return dyn_cast_or_null<ConstantSDNode>(
6961 getSplatValue(UndefElements).getNode());
6965 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6966 return dyn_cast_or_null<ConstantFPSDNode>(
6967 getSplatValue(UndefElements).getNode());
6970 bool BuildVectorSDNode::isConstant() const {
6971 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6972 unsigned Opc = getOperand(i).getOpcode();
6973 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6979 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6980 // Find the first non-undef value in the shuffle mask.
6982 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6985 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6987 // Make sure all remaining elements are either undef or the same as the first
6989 for (int Idx = Mask[i]; i != e; ++i)
6990 if (Mask[i] >= 0 && Mask[i] != Idx)
6996 static void checkForCyclesHelper(const SDNode *N,
6997 SmallPtrSetImpl<const SDNode*> &Visited,
6998 SmallPtrSetImpl<const SDNode*> &Checked,
6999 const llvm::SelectionDAG *DAG) {
7000 // If this node has already been checked, don't check it again.
7001 if (Checked.count(N))
7004 // If a node has already been visited on this depth-first walk, reject it as
7006 if (!Visited.insert(N).second) {
7007 errs() << "Detected cycle in SelectionDAG\n";
7008 dbgs() << "Offending node:\n";
7009 N->dumprFull(DAG); dbgs() << "\n";
7013 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7014 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7021 void llvm::checkForCycles(const llvm::SDNode *N,
7022 const llvm::SelectionDAG *DAG,
7030 assert(N && "Checking nonexistent SDNode");
7031 SmallPtrSet<const SDNode*, 32> visited;
7032 SmallPtrSet<const SDNode*, 32> checked;
7033 checkForCyclesHelper(N, visited, checked, DAG);
7038 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7039 checkForCycles(DAG->getRoot().getNode(), DAG, force);