1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
206 SDValue Op = N->getOperand(i);
207 if (Op.getOpcode() == ISD::UNDEF)
209 if (!isa<ConstantFPSDNode>(Op))
215 /// isScalarToVector - Return true if the specified node is a
216 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
217 /// element is not an undef.
218 bool ISD::isScalarToVector(const SDNode *N) {
219 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
222 if (N->getOpcode() != ISD::BUILD_VECTOR)
224 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226 unsigned NumElems = N->getNumOperands();
229 for (unsigned i = 1; i < NumElems; ++i) {
230 SDValue V = N->getOperand(i);
231 if (V.getOpcode() != ISD::UNDEF)
237 /// allOperandsUndef - Return true if the node has at least one operand
238 /// and all operands of the specified node are ISD::UNDEF.
239 bool ISD::allOperandsUndef(const SDNode *N) {
240 // Return false if the node has no operands.
241 // This is "logically inconsistent" with the definition of "all" but
242 // is probably the desired behavior.
243 if (N->getNumOperands() == 0)
246 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
247 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
253 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
256 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258 return ISD::SIGN_EXTEND;
260 return ISD::ZERO_EXTEND;
265 llvm_unreachable("Invalid LoadExtType");
268 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
269 /// when given the operation for (X op Y).
270 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
271 // To perform this operation, we just need to swap the L and G bits of the
273 unsigned OldL = (Operation >> 2) & 1;
274 unsigned OldG = (Operation >> 1) & 1;
275 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
276 (OldL << 1) | // New G bit
277 (OldG << 2)); // New L bit.
280 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
281 /// 'op' is a valid SetCC operation.
282 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
283 unsigned Operation = Op;
285 Operation ^= 7; // Flip L, G, E bits, but not U.
287 Operation ^= 15; // Flip all of the condition bits.
289 if (Operation > ISD::SETTRUE2)
290 Operation &= ~8; // Don't let N and U bits get set.
292 return ISD::CondCode(Operation);
296 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
297 /// signed operation and 2 if the result is an unsigned comparison. Return zero
298 /// if the operation does not depend on the sign of the input (setne and seteq).
299 static int isSignedOp(ISD::CondCode Opcode) {
301 default: llvm_unreachable("Illegal integer setcc operation!");
303 case ISD::SETNE: return 0;
307 case ISD::SETGE: return 1;
311 case ISD::SETUGE: return 2;
315 /// getSetCCOrOperation - Return the result of a logical OR between different
316 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
317 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
322 // Cannot fold a signed integer setcc with an unsigned integer setcc.
323 return ISD::SETCC_INVALID;
325 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
327 // If the N and U bits get set then the resultant comparison DOES suddenly
328 // care about orderedness, and is true when ordered.
329 if (Op > ISD::SETTRUE2)
330 Op &= ~16; // Clear the U bit if the N bit is set.
332 // Canonicalize illegal integer setcc's.
333 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
336 return ISD::CondCode(Op);
339 /// getSetCCAndOperation - Return the result of a logical AND between different
340 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
341 /// function returns zero if it is not possible to represent the resultant
343 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
346 // Cannot fold a signed setcc with an unsigned setcc.
347 return ISD::SETCC_INVALID;
349 // Combine all of the condition bits.
350 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352 // Canonicalize illegal integer setcc's.
356 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
357 case ISD::SETOEQ: // SETEQ & SETU[LG]E
358 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
359 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
360 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
367 //===----------------------------------------------------------------------===//
368 // SDNode Profile Support
369 //===----------------------------------------------------------------------===//
371 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
377 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
378 /// solely with their pointer.
379 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
380 ID.AddPointer(VTList.VTs);
383 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 static void AddNodeIDOperands(FoldingSetNodeID &ID,
386 ArrayRef<SDValue> Ops) {
387 for (auto& Op : Ops) {
388 ID.AddPointer(Op.getNode());
389 ID.AddInteger(Op.getResNo());
393 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 static void AddNodeIDOperands(FoldingSetNodeID &ID,
396 ArrayRef<SDUse> Ops) {
397 for (auto& Op : Ops) {
398 ID.AddPointer(Op.getNode());
399 ID.AddInteger(Op.getResNo());
403 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
407 ID.AddBoolean(exact);
410 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
411 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
412 bool nuw, bool nsw, bool exact) {
413 if (isBinOpWithFlags(Opcode))
414 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
417 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
418 SDVTList VTList, ArrayRef<SDValue> OpList) {
419 AddNodeIDOpcode(ID, OpC);
420 AddNodeIDValueTypes(ID, VTList);
421 AddNodeIDOperands(ID, OpList);
424 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
426 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
427 switch (N->getOpcode()) {
428 case ISD::TargetExternalSymbol:
429 case ISD::ExternalSymbol:
430 llvm_unreachable("Should only be used on nodes with operands");
431 default: break; // Normal nodes don't need extra info.
432 case ISD::TargetConstant:
433 case ISD::Constant: {
434 const ConstantSDNode *C = cast<ConstantSDNode>(N);
435 ID.AddPointer(C->getConstantIntValue());
436 ID.AddBoolean(C->isOpaque());
439 case ISD::TargetConstantFP:
440 case ISD::ConstantFP: {
441 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
444 case ISD::TargetGlobalAddress:
445 case ISD::GlobalAddress:
446 case ISD::TargetGlobalTLSAddress:
447 case ISD::GlobalTLSAddress: {
448 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
449 ID.AddPointer(GA->getGlobal());
450 ID.AddInteger(GA->getOffset());
451 ID.AddInteger(GA->getTargetFlags());
452 ID.AddInteger(GA->getAddressSpace());
455 case ISD::BasicBlock:
456 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
459 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
461 case ISD::RegisterMask:
462 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
465 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
467 case ISD::FrameIndex:
468 case ISD::TargetFrameIndex:
469 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
472 case ISD::TargetJumpTable:
473 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
476 case ISD::ConstantPool:
477 case ISD::TargetConstantPool: {
478 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
479 ID.AddInteger(CP->getAlignment());
480 ID.AddInteger(CP->getOffset());
481 if (CP->isMachineConstantPoolEntry())
482 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
484 ID.AddPointer(CP->getConstVal());
485 ID.AddInteger(CP->getTargetFlags());
488 case ISD::TargetIndex: {
489 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
490 ID.AddInteger(TI->getIndex());
491 ID.AddInteger(TI->getOffset());
492 ID.AddInteger(TI->getTargetFlags());
496 const LoadSDNode *LD = cast<LoadSDNode>(N);
497 ID.AddInteger(LD->getMemoryVT().getRawBits());
498 ID.AddInteger(LD->getRawSubclassData());
499 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
503 const StoreSDNode *ST = cast<StoreSDNode>(N);
504 ID.AddInteger(ST->getMemoryVT().getRawBits());
505 ID.AddInteger(ST->getRawSubclassData());
506 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
517 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
518 AddBinaryNodeIDCustom(
519 ID, N->getOpcode(), BinNode->Flags.hasNoUnsignedWrap(),
520 BinNode->Flags.hasNoSignedWrap(), BinNode->Flags.hasExact());
523 case ISD::ATOMIC_CMP_SWAP:
524 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
525 case ISD::ATOMIC_SWAP:
526 case ISD::ATOMIC_LOAD_ADD:
527 case ISD::ATOMIC_LOAD_SUB:
528 case ISD::ATOMIC_LOAD_AND:
529 case ISD::ATOMIC_LOAD_OR:
530 case ISD::ATOMIC_LOAD_XOR:
531 case ISD::ATOMIC_LOAD_NAND:
532 case ISD::ATOMIC_LOAD_MIN:
533 case ISD::ATOMIC_LOAD_MAX:
534 case ISD::ATOMIC_LOAD_UMIN:
535 case ISD::ATOMIC_LOAD_UMAX:
536 case ISD::ATOMIC_LOAD:
537 case ISD::ATOMIC_STORE: {
538 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
539 ID.AddInteger(AT->getMemoryVT().getRawBits());
540 ID.AddInteger(AT->getRawSubclassData());
541 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
544 case ISD::PREFETCH: {
545 const MemSDNode *PF = cast<MemSDNode>(N);
546 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
549 case ISD::VECTOR_SHUFFLE: {
550 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
551 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
553 ID.AddInteger(SVN->getMaskElt(i));
556 case ISD::TargetBlockAddress:
557 case ISD::BlockAddress: {
558 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
559 ID.AddPointer(BA->getBlockAddress());
560 ID.AddInteger(BA->getOffset());
561 ID.AddInteger(BA->getTargetFlags());
564 } // end switch (N->getOpcode())
566 // Target specific memory nodes could also have address spaces to check.
567 if (N->isTargetMemoryOpcode())
568 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
571 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
573 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
574 AddNodeIDOpcode(ID, N->getOpcode());
575 // Add the return value info.
576 AddNodeIDValueTypes(ID, N->getVTList());
577 // Add the operand info.
578 AddNodeIDOperands(ID, N->ops());
580 // Handle SDNode leafs with special info.
581 AddNodeIDCustom(ID, N);
584 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
585 /// the CSE map that carries volatility, temporalness, indexing mode, and
586 /// extension/truncation information.
588 static inline unsigned
589 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
590 bool isNonTemporal, bool isInvariant) {
591 assert((ConvType & 3) == ConvType &&
592 "ConvType may not require more than 2 bits!");
593 assert((AM & 7) == AM &&
594 "AM may not require more than 3 bits!");
598 (isNonTemporal << 6) |
602 //===----------------------------------------------------------------------===//
603 // SelectionDAG Class
604 //===----------------------------------------------------------------------===//
606 /// doNotCSE - Return true if CSE should not be performed for this node.
607 static bool doNotCSE(SDNode *N) {
608 if (N->getValueType(0) == MVT::Glue)
609 return true; // Never CSE anything that produces a flag.
611 switch (N->getOpcode()) {
613 case ISD::HANDLENODE:
615 return true; // Never CSE these nodes.
618 // Check that remaining values produced are not flags.
619 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
620 if (N->getValueType(i) == MVT::Glue)
621 return true; // Never CSE anything that produces a flag.
626 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
628 void SelectionDAG::RemoveDeadNodes() {
629 // Create a dummy node (which is not added to allnodes), that adds a reference
630 // to the root node, preventing it from being deleted.
631 HandleSDNode Dummy(getRoot());
633 SmallVector<SDNode*, 128> DeadNodes;
635 // Add all obviously-dead nodes to the DeadNodes worklist.
636 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
638 DeadNodes.push_back(I);
640 RemoveDeadNodes(DeadNodes);
642 // If the root changed (e.g. it was a dead load, update the root).
643 setRoot(Dummy.getValue());
646 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
647 /// given list, and any nodes that become unreachable as a result.
648 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
650 // Process the worklist, deleting the nodes and adding their uses to the
652 while (!DeadNodes.empty()) {
653 SDNode *N = DeadNodes.pop_back_val();
655 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
656 DUL->NodeDeleted(N, nullptr);
658 // Take the node out of the appropriate CSE map.
659 RemoveNodeFromCSEMaps(N);
661 // Next, brutally remove the operand list. This is safe to do, as there are
662 // no cycles in the graph.
663 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
665 SDNode *Operand = Use.getNode();
668 // Now that we removed this operand, see if there are no uses of it left.
669 if (Operand->use_empty())
670 DeadNodes.push_back(Operand);
677 void SelectionDAG::RemoveDeadNode(SDNode *N){
678 SmallVector<SDNode*, 16> DeadNodes(1, N);
680 // Create a dummy node that adds a reference to the root node, preventing
681 // it from being deleted. (This matters if the root is an operand of the
683 HandleSDNode Dummy(getRoot());
685 RemoveDeadNodes(DeadNodes);
688 void SelectionDAG::DeleteNode(SDNode *N) {
689 // First take this out of the appropriate CSE map.
690 RemoveNodeFromCSEMaps(N);
692 // Finally, remove uses due to operands of this node, remove from the
693 // AllNodes list, and delete the node.
694 DeleteNodeNotInCSEMaps(N);
697 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
698 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
699 assert(N->use_empty() && "Cannot delete a node that is not dead!");
701 // Drop all of the operands and decrement used node's use counts.
707 void SDDbgInfo::erase(const SDNode *Node) {
708 DbgValMapType::iterator I = DbgValMap.find(Node);
709 if (I == DbgValMap.end())
711 for (auto &Val: I->second)
712 Val->setIsInvalidated();
716 void SelectionDAG::DeallocateNode(SDNode *N) {
717 if (N->OperandsNeedDelete)
718 delete[] N->OperandList;
720 // Set the opcode to DELETED_NODE to help catch bugs when node
721 // memory is reallocated.
722 N->NodeType = ISD::DELETED_NODE;
724 NodeAllocator.Deallocate(AllNodes.remove(N));
726 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
727 // them and forget about that node.
732 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
733 static void VerifySDNode(SDNode *N) {
734 switch (N->getOpcode()) {
737 case ISD::BUILD_PAIR: {
738 EVT VT = N->getValueType(0);
739 assert(N->getNumValues() == 1 && "Too many results!");
740 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
741 "Wrong return type!");
742 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
743 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
744 "Mismatched operand types!");
745 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
746 "Wrong operand type!");
747 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
748 "Wrong return type size");
751 case ISD::BUILD_VECTOR: {
752 assert(N->getNumValues() == 1 && "Too many results!");
753 assert(N->getValueType(0).isVector() && "Wrong return type!");
754 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
755 "Wrong number of operands!");
756 EVT EltVT = N->getValueType(0).getVectorElementType();
757 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
758 assert((I->getValueType() == EltVT ||
759 (EltVT.isInteger() && I->getValueType().isInteger() &&
760 EltVT.bitsLE(I->getValueType()))) &&
761 "Wrong operand type!");
762 assert(I->getValueType() == N->getOperand(0).getValueType() &&
763 "Operands must all have the same type");
771 /// \brief Insert a newly allocated node into the DAG.
773 /// Handles insertion into the all nodes list and CSE map, as well as
774 /// verification and other common operations when a new node is allocated.
775 void SelectionDAG::InsertNode(SDNode *N) {
776 AllNodes.push_back(N);
782 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
783 /// correspond to it. This is useful when we're about to delete or repurpose
784 /// the node. We don't want future request for structurally identical nodes
785 /// to return N anymore.
786 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
788 switch (N->getOpcode()) {
789 case ISD::HANDLENODE: return false; // noop.
791 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
792 "Cond code doesn't exist!");
793 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
794 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
796 case ISD::ExternalSymbol:
797 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
799 case ISD::TargetExternalSymbol: {
800 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
801 Erased = TargetExternalSymbols.erase(
802 std::pair<std::string,unsigned char>(ESN->getSymbol(),
803 ESN->getTargetFlags()));
806 case ISD::VALUETYPE: {
807 EVT VT = cast<VTSDNode>(N)->getVT();
808 if (VT.isExtended()) {
809 Erased = ExtendedValueTypeNodes.erase(VT);
811 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
812 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
817 // Remove it from the CSE Map.
818 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
819 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
820 Erased = CSEMap.RemoveNode(N);
824 // Verify that the node was actually in one of the CSE maps, unless it has a
825 // flag result (which cannot be CSE'd) or is one of the special cases that are
826 // not subject to CSE.
827 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
828 !N->isMachineOpcode() && !doNotCSE(N)) {
831 llvm_unreachable("Node is not in map!");
837 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
838 /// maps and modified in place. Add it back to the CSE maps, unless an identical
839 /// node already exists, in which case transfer all its users to the existing
840 /// node. This transfer can potentially trigger recursive merging.
843 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
844 // For node types that aren't CSE'd, just act as if no identical node
847 SDNode *Existing = CSEMap.GetOrInsertNode(N);
849 // If there was already an existing matching node, use ReplaceAllUsesWith
850 // to replace the dead one with the existing one. This can cause
851 // recursive merging of other unrelated nodes down the line.
852 ReplaceAllUsesWith(N, Existing);
854 // N is now dead. Inform the listeners and delete it.
855 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
856 DUL->NodeDeleted(N, Existing);
857 DeleteNodeNotInCSEMaps(N);
862 // If the node doesn't already exist, we updated it. Inform listeners.
863 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
867 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
868 /// were replaced with those specified. If this node is never memoized,
869 /// return null, otherwise return a pointer to the slot it would take. If a
870 /// node already exists with these operands, the slot will be non-null.
871 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
876 SDValue Ops[] = { Op };
878 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
879 AddNodeIDCustom(ID, N);
880 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
884 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
885 /// were replaced with those specified. If this node is never memoized,
886 /// return null, otherwise return a pointer to the slot it would take. If a
887 /// node already exists with these operands, the slot will be non-null.
888 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
889 SDValue Op1, SDValue Op2,
894 SDValue Ops[] = { Op1, Op2 };
896 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
897 AddNodeIDCustom(ID, N);
898 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
903 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
904 /// were replaced with those specified. If this node is never memoized,
905 /// return null, otherwise return a pointer to the slot it would take. If a
906 /// node already exists with these operands, the slot will be non-null.
907 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
913 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
914 AddNodeIDCustom(ID, N);
915 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
919 /// getEVTAlignment - Compute the default alignment value for the
922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
923 Type *Ty = VT == MVT::iPTR ?
924 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
925 VT.getTypeForEVT(*getContext());
927 return TLI->getDataLayout()->getABITypeAlignment(Ty);
930 // EntryNode could meaningfully have debug info if we can find it...
931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
932 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
935 UpdateListeners(nullptr) {
936 AllNodes.push_back(&EntryNode);
937 DbgInfo = new SDDbgInfo();
940 void SelectionDAG::init(MachineFunction &mf) {
942 TLI = getSubtarget().getTargetLowering();
943 TSI = getSubtarget().getSelectionDAGInfo();
944 Context = &mf.getFunction()->getContext();
947 SelectionDAG::~SelectionDAG() {
948 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
953 void SelectionDAG::allnodes_clear() {
954 assert(&*AllNodes.begin() == &EntryNode);
955 AllNodes.remove(AllNodes.begin());
956 while (!AllNodes.empty())
957 DeallocateNode(AllNodes.begin());
960 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
961 SDVTList VTs, SDValue N1,
962 SDValue N2, bool nuw, bool nsw,
964 if (isBinOpWithFlags(Opcode)) {
965 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
966 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
967 FN->Flags.setNoUnsignedWrap(nuw);
968 FN->Flags.setNoSignedWrap(nsw);
969 FN->Flags.setExact(exact);
974 BinarySDNode *N = new (NodeAllocator)
975 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
979 void SelectionDAG::clear() {
981 OperandAllocator.Reset();
984 ExtendedValueTypeNodes.clear();
985 ExternalSymbols.clear();
986 TargetExternalSymbols.clear();
987 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
988 static_cast<CondCodeSDNode*>(nullptr));
989 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
990 static_cast<SDNode*>(nullptr));
992 EntryNode.UseList = nullptr;
993 AllNodes.push_back(&EntryNode);
994 Root = getEntryNode();
998 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
999 return VT.bitsGT(Op.getValueType()) ?
1000 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1001 getNode(ISD::TRUNCATE, DL, VT, Op);
1004 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1005 return VT.bitsGT(Op.getValueType()) ?
1006 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1007 getNode(ISD::TRUNCATE, DL, VT, Op);
1010 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1011 return VT.bitsGT(Op.getValueType()) ?
1012 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1013 getNode(ISD::TRUNCATE, DL, VT, Op);
1016 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1018 if (VT.bitsLE(Op.getValueType()))
1019 return getNode(ISD::TRUNCATE, SL, VT, Op);
1021 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1022 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1025 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1026 assert(!VT.isVector() &&
1027 "getZeroExtendInReg should use the vector element type instead of "
1028 "the vector type!");
1029 if (Op.getValueType() == VT) return Op;
1030 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1031 APInt Imm = APInt::getLowBitsSet(BitWidth,
1032 VT.getSizeInBits());
1033 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1034 getConstant(Imm, DL, Op.getValueType()));
1037 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1038 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1039 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1040 "The sizes of the input and result must match in order to perform the "
1041 "extend in-register.");
1042 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1043 "The destination vector type must have fewer lanes than the input.");
1044 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1047 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1048 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1049 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1050 "The sizes of the input and result must match in order to perform the "
1051 "extend in-register.");
1052 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1053 "The destination vector type must have fewer lanes than the input.");
1054 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1057 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1058 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1059 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1060 "The sizes of the input and result must match in order to perform the "
1061 "extend in-register.");
1062 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1063 "The destination vector type must have fewer lanes than the input.");
1064 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1067 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1069 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1070 EVT EltVT = VT.getScalarType();
1072 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1073 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1076 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1077 EVT EltVT = VT.getScalarType();
1079 switch (TLI->getBooleanContents(VT)) {
1080 case TargetLowering::ZeroOrOneBooleanContent:
1081 case TargetLowering::UndefinedBooleanContent:
1082 TrueValue = getConstant(1, DL, VT);
1084 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1085 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1089 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1092 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1094 EVT EltVT = VT.getScalarType();
1095 assert((EltVT.getSizeInBits() >= 64 ||
1096 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1097 "getConstant with a uint64_t value that doesn't fit in the type!");
1098 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1101 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1104 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1107 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1108 bool isT, bool isO) {
1109 assert(VT.isInteger() && "Cannot create FP integer constant!");
1111 EVT EltVT = VT.getScalarType();
1112 const ConstantInt *Elt = &Val;
1114 // In some cases the vector type is legal but the element type is illegal and
1115 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1116 // inserted value (the type does not need to match the vector element type).
1117 // Any extra bits introduced will be truncated away.
1118 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1119 TargetLowering::TypePromoteInteger) {
1120 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1121 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1122 Elt = ConstantInt::get(*getContext(), NewVal);
1124 // In other cases the element type is illegal and needs to be expanded, for
1125 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1126 // the value into n parts and use a vector type with n-times the elements.
1127 // Then bitcast to the type requested.
1128 // Legalizing constants too early makes the DAGCombiner's job harder so we
1129 // only legalize if the DAG tells us we must produce legal types.
1130 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1131 TLI->getTypeAction(*getContext(), EltVT) ==
1132 TargetLowering::TypeExpandInteger) {
1133 APInt NewVal = Elt->getValue();
1134 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1135 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1136 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1137 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1139 // Check the temporary vector is the correct size. If this fails then
1140 // getTypeToTransformTo() probably returned a type whose size (in bits)
1141 // isn't a power-of-2 factor of the requested type size.
1142 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1144 SmallVector<SDValue, 2> EltParts;
1145 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1146 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1147 .trunc(ViaEltSizeInBits), DL,
1148 ViaEltVT, isT, isO));
1151 // EltParts is currently in little endian order. If we actually want
1152 // big-endian order then reverse it now.
1153 if (TLI->isBigEndian())
1154 std::reverse(EltParts.begin(), EltParts.end());
1156 // The elements must be reversed when the element order is different
1157 // to the endianness of the elements (because the BITCAST is itself a
1158 // vector shuffle in this situation). However, we do not need any code to
1159 // perform this reversal because getConstant() is producing a vector
1161 // This situation occurs in MIPS MSA.
1163 SmallVector<SDValue, 8> Ops;
1164 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1165 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1167 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1168 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1173 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1174 "APInt size does not match type size!");
1175 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1176 FoldingSetNodeID ID;
1177 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1181 SDNode *N = nullptr;
1182 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1184 return SDValue(N, 0);
1187 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1189 CSEMap.InsertNode(N, IP);
1193 SDValue Result(N, 0);
1194 if (VT.isVector()) {
1195 SmallVector<SDValue, 8> Ops;
1196 Ops.assign(VT.getVectorNumElements(), Result);
1197 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1202 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1203 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1206 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1208 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1211 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1213 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1215 EVT EltVT = VT.getScalarType();
1217 // Do the map lookup using the actual bit pattern for the floating point
1218 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1219 // we don't have issues with SNANs.
1220 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1221 FoldingSetNodeID ID;
1222 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1225 SDNode *N = nullptr;
1226 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1228 return SDValue(N, 0);
1231 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1232 CSEMap.InsertNode(N, IP);
1236 SDValue Result(N, 0);
1237 if (VT.isVector()) {
1238 SmallVector<SDValue, 8> Ops;
1239 Ops.assign(VT.getVectorNumElements(), Result);
1240 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1245 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1247 EVT EltVT = VT.getScalarType();
1248 if (EltVT==MVT::f32)
1249 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1250 else if (EltVT==MVT::f64)
1251 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1252 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1255 APFloat apf = APFloat(Val);
1256 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1258 return getConstantFP(apf, DL, VT, isTarget);
1260 llvm_unreachable("Unsupported type in getConstantFP");
1263 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1264 EVT VT, int64_t Offset,
1266 unsigned char TargetFlags) {
1267 assert((TargetFlags == 0 || isTargetGA) &&
1268 "Cannot set target flags on target-independent globals");
1270 // Truncate (with sign-extension) the offset value to the pointer size.
1271 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1273 Offset = SignExtend64(Offset, BitWidth);
1276 if (GV->isThreadLocal())
1277 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1279 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1281 FoldingSetNodeID ID;
1282 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1284 ID.AddInteger(Offset);
1285 ID.AddInteger(TargetFlags);
1286 ID.AddInteger(GV->getType()->getAddressSpace());
1288 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1289 return SDValue(E, 0);
1291 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1292 DL.getDebugLoc(), GV, VT,
1293 Offset, TargetFlags);
1294 CSEMap.InsertNode(N, IP);
1296 return SDValue(N, 0);
1299 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1300 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1301 FoldingSetNodeID ID;
1302 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1305 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1306 return SDValue(E, 0);
1308 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1309 CSEMap.InsertNode(N, IP);
1311 return SDValue(N, 0);
1314 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1315 unsigned char TargetFlags) {
1316 assert((TargetFlags == 0 || isTarget) &&
1317 "Cannot set target flags on target-independent jump tables");
1318 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1319 FoldingSetNodeID ID;
1320 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1322 ID.AddInteger(TargetFlags);
1324 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1325 return SDValue(E, 0);
1327 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1329 CSEMap.InsertNode(N, IP);
1331 return SDValue(N, 0);
1334 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1335 unsigned Alignment, int Offset,
1337 unsigned char TargetFlags) {
1338 assert((TargetFlags == 0 || isTarget) &&
1339 "Cannot set target flags on target-independent globals");
1341 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1342 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1343 FoldingSetNodeID ID;
1344 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1345 ID.AddInteger(Alignment);
1346 ID.AddInteger(Offset);
1348 ID.AddInteger(TargetFlags);
1350 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1351 return SDValue(E, 0);
1353 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1354 Alignment, TargetFlags);
1355 CSEMap.InsertNode(N, IP);
1357 return SDValue(N, 0);
1361 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1362 unsigned Alignment, int Offset,
1364 unsigned char TargetFlags) {
1365 assert((TargetFlags == 0 || isTarget) &&
1366 "Cannot set target flags on target-independent globals");
1368 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1369 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1370 FoldingSetNodeID ID;
1371 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1372 ID.AddInteger(Alignment);
1373 ID.AddInteger(Offset);
1374 C->addSelectionDAGCSEId(ID);
1375 ID.AddInteger(TargetFlags);
1377 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1378 return SDValue(E, 0);
1380 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1381 Alignment, TargetFlags);
1382 CSEMap.InsertNode(N, IP);
1384 return SDValue(N, 0);
1387 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1388 unsigned char TargetFlags) {
1389 FoldingSetNodeID ID;
1390 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1391 ID.AddInteger(Index);
1392 ID.AddInteger(Offset);
1393 ID.AddInteger(TargetFlags);
1395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1396 return SDValue(E, 0);
1398 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1400 CSEMap.InsertNode(N, IP);
1402 return SDValue(N, 0);
1405 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1410 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1411 return SDValue(E, 0);
1413 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1414 CSEMap.InsertNode(N, IP);
1416 return SDValue(N, 0);
1419 SDValue SelectionDAG::getValueType(EVT VT) {
1420 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1421 ValueTypeNodes.size())
1422 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1424 SDNode *&N = VT.isExtended() ?
1425 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1427 if (N) return SDValue(N, 0);
1428 N = new (NodeAllocator) VTSDNode(VT);
1430 return SDValue(N, 0);
1433 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1434 SDNode *&N = ExternalSymbols[Sym];
1435 if (N) return SDValue(N, 0);
1436 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1442 unsigned char TargetFlags) {
1444 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1446 if (N) return SDValue(N, 0);
1447 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1449 return SDValue(N, 0);
1452 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1453 if ((unsigned)Cond >= CondCodeNodes.size())
1454 CondCodeNodes.resize(Cond+1);
1456 if (!CondCodeNodes[Cond]) {
1457 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1458 CondCodeNodes[Cond] = N;
1462 return SDValue(CondCodeNodes[Cond], 0);
1465 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1466 // the shuffle mask M that point at N1 to point at N2, and indices that point
1467 // N2 to point at N1.
1468 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1470 ShuffleVectorSDNode::commuteMask(M);
1473 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1474 SDValue N2, const int *Mask) {
1475 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1476 "Invalid VECTOR_SHUFFLE");
1478 // Canonicalize shuffle undef, undef -> undef
1479 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1480 return getUNDEF(VT);
1482 // Validate that all indices in Mask are within the range of the elements
1483 // input to the shuffle.
1484 unsigned NElts = VT.getVectorNumElements();
1485 SmallVector<int, 8> MaskVec;
1486 for (unsigned i = 0; i != NElts; ++i) {
1487 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1488 MaskVec.push_back(Mask[i]);
1491 // Canonicalize shuffle v, v -> v, undef
1494 for (unsigned i = 0; i != NElts; ++i)
1495 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1498 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1499 if (N1.getOpcode() == ISD::UNDEF)
1500 commuteShuffle(N1, N2, MaskVec);
1502 // If shuffling a splat, try to blend the splat instead. We do this here so
1503 // that even when this arises during lowering we don't have to re-handle it.
1504 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1505 BitVector UndefElements;
1506 SDValue Splat = BV->getSplatValue(&UndefElements);
1510 for (int i = 0; i < (int)NElts; ++i) {
1511 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1514 // If this input comes from undef, mark it as such.
1515 if (UndefElements[MaskVec[i] - Offset]) {
1520 // If we can blend a non-undef lane, use that instead.
1521 if (!UndefElements[i])
1522 MaskVec[i] = i + Offset;
1525 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1526 BlendSplat(N1BV, 0);
1527 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1528 BlendSplat(N2BV, NElts);
1530 // Canonicalize all index into lhs, -> shuffle lhs, undef
1531 // Canonicalize all index into rhs, -> shuffle rhs, undef
1532 bool AllLHS = true, AllRHS = true;
1533 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1534 for (unsigned i = 0; i != NElts; ++i) {
1535 if (MaskVec[i] >= (int)NElts) {
1540 } else if (MaskVec[i] >= 0) {
1544 if (AllLHS && AllRHS)
1545 return getUNDEF(VT);
1546 if (AllLHS && !N2Undef)
1550 commuteShuffle(N1, N2, MaskVec);
1552 // Reset our undef status after accounting for the mask.
1553 N2Undef = N2.getOpcode() == ISD::UNDEF;
1554 // Re-check whether both sides ended up undef.
1555 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1556 return getUNDEF(VT);
1558 // If Identity shuffle return that node.
1559 bool Identity = true, AllSame = true;
1560 for (unsigned i = 0; i != NElts; ++i) {
1561 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1562 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1564 if (Identity && NElts)
1567 // Shuffling a constant splat doesn't change the result.
1571 // Look through any bitcasts. We check that these don't change the number
1572 // (and size) of elements and just changes their types.
1573 while (V.getOpcode() == ISD::BITCAST)
1574 V = V->getOperand(0);
1576 // A splat should always show up as a build vector node.
1577 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1578 BitVector UndefElements;
1579 SDValue Splat = BV->getSplatValue(&UndefElements);
1580 // If this is a splat of an undef, shuffling it is also undef.
1581 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1582 return getUNDEF(VT);
1585 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1587 // We only have a splat which can skip shuffles if there is a splatted
1588 // value and no undef lanes rearranged by the shuffle.
1589 if (Splat && UndefElements.none()) {
1590 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1591 // number of elements match or the value splatted is a zero constant.
1594 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1595 if (C->isNullValue())
1599 // If the shuffle itself creates a splat, build the vector directly.
1600 if (AllSame && SameNumElts) {
1601 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1602 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1604 EVT BuildVT = BV->getValueType(0);
1605 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1607 // We may have jumped through bitcasts, so the type of the
1608 // BUILD_VECTOR may not match the type of the shuffle.
1610 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1616 FoldingSetNodeID ID;
1617 SDValue Ops[2] = { N1, N2 };
1618 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1619 for (unsigned i = 0; i != NElts; ++i)
1620 ID.AddInteger(MaskVec[i]);
1623 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1624 return SDValue(E, 0);
1626 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1627 // SDNode doesn't have access to it. This memory will be "leaked" when
1628 // the node is deallocated, but recovered when the NodeAllocator is released.
1629 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1630 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1632 ShuffleVectorSDNode *N =
1633 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1634 dl.getDebugLoc(), N1, N2,
1636 CSEMap.InsertNode(N, IP);
1638 return SDValue(N, 0);
1641 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1642 MVT VT = SV.getSimpleValueType(0);
1643 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1644 ShuffleVectorSDNode::commuteMask(MaskVec);
1646 SDValue Op0 = SV.getOperand(0);
1647 SDValue Op1 = SV.getOperand(1);
1648 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1651 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1652 SDValue Val, SDValue DTy,
1653 SDValue STy, SDValue Rnd, SDValue Sat,
1654 ISD::CvtCode Code) {
1655 // If the src and dest types are the same and the conversion is between
1656 // integer types of the same sign or two floats, no conversion is necessary.
1658 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1661 FoldingSetNodeID ID;
1662 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1663 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1665 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1666 return SDValue(E, 0);
1668 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1671 CSEMap.InsertNode(N, IP);
1673 return SDValue(N, 0);
1676 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1677 FoldingSetNodeID ID;
1678 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1679 ID.AddInteger(RegNo);
1681 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1682 return SDValue(E, 0);
1684 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1685 CSEMap.InsertNode(N, IP);
1687 return SDValue(N, 0);
1690 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1691 FoldingSetNodeID ID;
1692 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1693 ID.AddPointer(RegMask);
1695 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1696 return SDValue(E, 0);
1698 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1699 CSEMap.InsertNode(N, IP);
1701 return SDValue(N, 0);
1704 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1705 FoldingSetNodeID ID;
1706 SDValue Ops[] = { Root };
1707 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1708 ID.AddPointer(Label);
1710 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1711 return SDValue(E, 0);
1713 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1714 dl.getDebugLoc(), Root, Label);
1715 CSEMap.InsertNode(N, IP);
1717 return SDValue(N, 0);
1721 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1724 unsigned char TargetFlags) {
1725 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1727 FoldingSetNodeID ID;
1728 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1730 ID.AddInteger(Offset);
1731 ID.AddInteger(TargetFlags);
1733 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1734 return SDValue(E, 0);
1736 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1738 CSEMap.InsertNode(N, IP);
1740 return SDValue(N, 0);
1743 SDValue SelectionDAG::getSrcValue(const Value *V) {
1744 assert((!V || V->getType()->isPointerTy()) &&
1745 "SrcValue is not a pointer?");
1747 FoldingSetNodeID ID;
1748 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1752 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1753 return SDValue(E, 0);
1755 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1756 CSEMap.InsertNode(N, IP);
1758 return SDValue(N, 0);
1761 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1762 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1763 FoldingSetNodeID ID;
1764 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1768 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1769 return SDValue(E, 0);
1771 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1772 CSEMap.InsertNode(N, IP);
1774 return SDValue(N, 0);
1777 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1778 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1779 unsigned SrcAS, unsigned DestAS) {
1780 SDValue Ops[] = {Ptr};
1781 FoldingSetNodeID ID;
1782 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1783 ID.AddInteger(SrcAS);
1784 ID.AddInteger(DestAS);
1787 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1788 return SDValue(E, 0);
1790 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1792 VT, Ptr, SrcAS, DestAS);
1793 CSEMap.InsertNode(N, IP);
1795 return SDValue(N, 0);
1798 /// getShiftAmountOperand - Return the specified value casted to
1799 /// the target's desired shift amount type.
1800 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1801 EVT OpTy = Op.getValueType();
1802 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1803 if (OpTy == ShTy || OpTy.isVector()) return Op;
1805 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1806 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1809 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1810 /// specified value type.
1811 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1812 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1813 unsigned ByteSize = VT.getStoreSize();
1814 Type *Ty = VT.getTypeForEVT(*getContext());
1815 unsigned StackAlign =
1816 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1818 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1819 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1822 /// CreateStackTemporary - Create a stack temporary suitable for holding
1823 /// either of the specified value types.
1824 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1825 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1826 VT2.getStoreSizeInBits())/8;
1827 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1828 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1829 const DataLayout *TD = TLI->getDataLayout();
1830 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1831 TD->getPrefTypeAlignment(Ty2));
1833 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1834 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1835 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1838 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1839 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1840 // These setcc operations always fold.
1844 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1846 case ISD::SETTRUE2: {
1847 TargetLowering::BooleanContent Cnt =
1848 TLI->getBooleanContents(N1->getValueType(0));
1850 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1864 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1868 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1869 const APInt &C2 = N2C->getAPIntValue();
1870 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1871 const APInt &C1 = N1C->getAPIntValue();
1874 default: llvm_unreachable("Unknown integer setcc!");
1875 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1876 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1877 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1878 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1879 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1880 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1881 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1882 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1883 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1884 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1888 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1889 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1890 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1893 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1894 return getUNDEF(VT);
1896 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1897 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1898 return getUNDEF(VT);
1900 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1901 R==APFloat::cmpLessThan, dl, VT);
1902 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1903 return getUNDEF(VT);
1905 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1906 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1907 return getUNDEF(VT);
1909 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1910 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1911 return getUNDEF(VT);
1913 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1914 R==APFloat::cmpEqual, dl, VT);
1915 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1916 return getUNDEF(VT);
1918 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1919 R==APFloat::cmpEqual, dl, VT);
1920 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1921 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1922 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1923 R==APFloat::cmpEqual, dl, VT);
1924 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1925 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1926 R==APFloat::cmpLessThan, dl, VT);
1927 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1928 R==APFloat::cmpUnordered, dl, VT);
1929 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1930 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1933 // Ensure that the constant occurs on the RHS.
1934 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1935 MVT CompVT = N1.getValueType().getSimpleVT();
1936 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1939 return getSetCC(dl, VT, N2, N1, SwappedCond);
1943 // Could not fold it.
1947 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1948 /// use this predicate to simplify operations downstream.
1949 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1950 // This predicate is not safe for vector operations.
1951 if (Op.getValueType().isVector())
1954 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1955 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1958 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1959 /// this predicate to simplify operations downstream. Mask is known to be zero
1960 /// for bits that V cannot have.
1961 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1962 unsigned Depth) const {
1963 APInt KnownZero, KnownOne;
1964 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1965 return (KnownZero & Mask) == Mask;
1968 /// Determine which bits of Op are known to be either zero or one and return
1969 /// them in the KnownZero/KnownOne bitsets.
1970 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1971 APInt &KnownOne, unsigned Depth) const {
1972 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1974 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1976 return; // Limit search depth.
1978 APInt KnownZero2, KnownOne2;
1980 switch (Op.getOpcode()) {
1982 // We know all of the bits for a constant!
1983 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1984 KnownZero = ~KnownOne;
1987 // If either the LHS or the RHS are Zero, the result is zero.
1988 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1989 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1991 // Output known-1 bits are only known if set in both the LHS & RHS.
1992 KnownOne &= KnownOne2;
1993 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1994 KnownZero |= KnownZero2;
1997 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1998 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2000 // Output known-0 bits are only known if clear in both the LHS & RHS.
2001 KnownZero &= KnownZero2;
2002 // Output known-1 are known to be set if set in either the LHS | RHS.
2003 KnownOne |= KnownOne2;
2006 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2007 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2009 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2010 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2011 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2012 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2013 KnownZero = KnownZeroOut;
2017 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2018 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2020 // If low bits are zero in either operand, output low known-0 bits.
2021 // Also compute a conserative estimate for high known-0 bits.
2022 // More trickiness is possible, but this is sufficient for the
2023 // interesting case of alignment computation.
2024 KnownOne.clearAllBits();
2025 unsigned TrailZ = KnownZero.countTrailingOnes() +
2026 KnownZero2.countTrailingOnes();
2027 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2028 KnownZero2.countLeadingOnes(),
2029 BitWidth) - BitWidth;
2031 TrailZ = std::min(TrailZ, BitWidth);
2032 LeadZ = std::min(LeadZ, BitWidth);
2033 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2034 APInt::getHighBitsSet(BitWidth, LeadZ);
2038 // For the purposes of computing leading zeros we can conservatively
2039 // treat a udiv as a logical right shift by the power of 2 known to
2040 // be less than the denominator.
2041 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2042 unsigned LeadZ = KnownZero2.countLeadingOnes();
2044 KnownOne2.clearAllBits();
2045 KnownZero2.clearAllBits();
2046 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2047 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2048 if (RHSUnknownLeadingOnes != BitWidth)
2049 LeadZ = std::min(BitWidth,
2050 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2052 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2056 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2057 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2059 // Only known if known in both the LHS and RHS.
2060 KnownOne &= KnownOne2;
2061 KnownZero &= KnownZero2;
2063 case ISD::SELECT_CC:
2064 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2065 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2067 // Only known if known in both the LHS and RHS.
2068 KnownOne &= KnownOne2;
2069 KnownZero &= KnownZero2;
2077 if (Op.getResNo() != 1)
2079 // The boolean result conforms to getBooleanContents.
2080 // If we know the result of a setcc has the top bits zero, use this info.
2081 // We know that we have an integer-based boolean since these operations
2082 // are only available for integer.
2083 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2084 TargetLowering::ZeroOrOneBooleanContent &&
2086 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2089 // If we know the result of a setcc has the top bits zero, use this info.
2090 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2091 TargetLowering::ZeroOrOneBooleanContent &&
2093 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2096 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2097 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2098 unsigned ShAmt = SA->getZExtValue();
2100 // If the shift count is an invalid immediate, don't do anything.
2101 if (ShAmt >= BitWidth)
2104 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2105 KnownZero <<= ShAmt;
2107 // low bits known zero.
2108 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2112 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2113 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2114 unsigned ShAmt = SA->getZExtValue();
2116 // If the shift count is an invalid immediate, don't do anything.
2117 if (ShAmt >= BitWidth)
2120 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2121 KnownZero = KnownZero.lshr(ShAmt);
2122 KnownOne = KnownOne.lshr(ShAmt);
2124 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2125 KnownZero |= HighBits; // High bits known zero.
2129 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2130 unsigned ShAmt = SA->getZExtValue();
2132 // If the shift count is an invalid immediate, don't do anything.
2133 if (ShAmt >= BitWidth)
2136 // If any of the demanded bits are produced by the sign extension, we also
2137 // demand the input sign bit.
2138 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2140 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2141 KnownZero = KnownZero.lshr(ShAmt);
2142 KnownOne = KnownOne.lshr(ShAmt);
2144 // Handle the sign bits.
2145 APInt SignBit = APInt::getSignBit(BitWidth);
2146 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2148 if (KnownZero.intersects(SignBit)) {
2149 KnownZero |= HighBits; // New bits are known zero.
2150 } else if (KnownOne.intersects(SignBit)) {
2151 KnownOne |= HighBits; // New bits are known one.
2155 case ISD::SIGN_EXTEND_INREG: {
2156 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2157 unsigned EBits = EVT.getScalarType().getSizeInBits();
2159 // Sign extension. Compute the demanded bits in the result that are not
2160 // present in the input.
2161 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2163 APInt InSignBit = APInt::getSignBit(EBits);
2164 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2166 // If the sign extended bits are demanded, we know that the sign
2168 InSignBit = InSignBit.zext(BitWidth);
2169 if (NewBits.getBoolValue())
2170 InputDemandedBits |= InSignBit;
2172 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2173 KnownOne &= InputDemandedBits;
2174 KnownZero &= InputDemandedBits;
2176 // If the sign bit of the input is known set or clear, then we know the
2177 // top bits of the result.
2178 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2179 KnownZero |= NewBits;
2180 KnownOne &= ~NewBits;
2181 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2182 KnownOne |= NewBits;
2183 KnownZero &= ~NewBits;
2184 } else { // Input sign bit unknown
2185 KnownZero &= ~NewBits;
2186 KnownOne &= ~NewBits;
2191 case ISD::CTTZ_ZERO_UNDEF:
2193 case ISD::CTLZ_ZERO_UNDEF:
2195 unsigned LowBits = Log2_32(BitWidth)+1;
2196 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2197 KnownOne.clearAllBits();
2201 LoadSDNode *LD = cast<LoadSDNode>(Op);
2202 // If this is a ZEXTLoad and we are looking at the loaded value.
2203 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2204 EVT VT = LD->getMemoryVT();
2205 unsigned MemBits = VT.getScalarType().getSizeInBits();
2206 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2207 } else if (const MDNode *Ranges = LD->getRanges()) {
2208 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2212 case ISD::ZERO_EXTEND: {
2213 EVT InVT = Op.getOperand(0).getValueType();
2214 unsigned InBits = InVT.getScalarType().getSizeInBits();
2215 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2216 KnownZero = KnownZero.trunc(InBits);
2217 KnownOne = KnownOne.trunc(InBits);
2218 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2219 KnownZero = KnownZero.zext(BitWidth);
2220 KnownOne = KnownOne.zext(BitWidth);
2221 KnownZero |= NewBits;
2224 case ISD::SIGN_EXTEND: {
2225 EVT InVT = Op.getOperand(0).getValueType();
2226 unsigned InBits = InVT.getScalarType().getSizeInBits();
2227 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2229 KnownZero = KnownZero.trunc(InBits);
2230 KnownOne = KnownOne.trunc(InBits);
2231 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2233 // Note if the sign bit is known to be zero or one.
2234 bool SignBitKnownZero = KnownZero.isNegative();
2235 bool SignBitKnownOne = KnownOne.isNegative();
2237 KnownZero = KnownZero.zext(BitWidth);
2238 KnownOne = KnownOne.zext(BitWidth);
2240 // If the sign bit is known zero or one, the top bits match.
2241 if (SignBitKnownZero)
2242 KnownZero |= NewBits;
2243 else if (SignBitKnownOne)
2244 KnownOne |= NewBits;
2247 case ISD::ANY_EXTEND: {
2248 EVT InVT = Op.getOperand(0).getValueType();
2249 unsigned InBits = InVT.getScalarType().getSizeInBits();
2250 KnownZero = KnownZero.trunc(InBits);
2251 KnownOne = KnownOne.trunc(InBits);
2252 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2253 KnownZero = KnownZero.zext(BitWidth);
2254 KnownOne = KnownOne.zext(BitWidth);
2257 case ISD::TRUNCATE: {
2258 EVT InVT = Op.getOperand(0).getValueType();
2259 unsigned InBits = InVT.getScalarType().getSizeInBits();
2260 KnownZero = KnownZero.zext(InBits);
2261 KnownOne = KnownOne.zext(InBits);
2262 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2263 KnownZero = KnownZero.trunc(BitWidth);
2264 KnownOne = KnownOne.trunc(BitWidth);
2267 case ISD::AssertZext: {
2268 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2269 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2270 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2271 KnownZero |= (~InMask);
2272 KnownOne &= (~KnownZero);
2276 // All bits are zero except the low bit.
2277 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2281 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2282 // We know that the top bits of C-X are clear if X contains less bits
2283 // than C (i.e. no wrap-around can happen). For example, 20-X is
2284 // positive if we can prove that X is >= 0 and < 16.
2285 if (CLHS->getAPIntValue().isNonNegative()) {
2286 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2287 // NLZ can't be BitWidth with no sign bit
2288 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2289 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2291 // If all of the MaskV bits are known to be zero, then we know the
2292 // output top bits are zero, because we now know that the output is
2294 if ((KnownZero2 & MaskV) == MaskV) {
2295 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2296 // Top bits known zero.
2297 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2305 // Output known-0 bits are known if clear or set in both the low clear bits
2306 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2307 // low 3 bits clear.
2308 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2309 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2311 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2312 KnownZeroOut = std::min(KnownZeroOut,
2313 KnownZero2.countTrailingOnes());
2315 if (Op.getOpcode() == ISD::ADD) {
2316 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2320 // With ADDE, a carry bit may be added in, so we can only use this
2321 // information if we know (at least) that the low two bits are clear. We
2322 // then return to the caller that the low bit is unknown but that other bits
2324 if (KnownZeroOut >= 2) // ADDE
2325 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2329 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2330 const APInt &RA = Rem->getAPIntValue().abs();
2331 if (RA.isPowerOf2()) {
2332 APInt LowBits = RA - 1;
2333 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2335 // The low bits of the first operand are unchanged by the srem.
2336 KnownZero = KnownZero2 & LowBits;
2337 KnownOne = KnownOne2 & LowBits;
2339 // If the first operand is non-negative or has all low bits zero, then
2340 // the upper bits are all zero.
2341 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2342 KnownZero |= ~LowBits;
2344 // If the first operand is negative and not all low bits are zero, then
2345 // the upper bits are all one.
2346 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2347 KnownOne |= ~LowBits;
2348 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2353 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2354 const APInt &RA = Rem->getAPIntValue();
2355 if (RA.isPowerOf2()) {
2356 APInt LowBits = (RA - 1);
2357 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2359 // The upper bits are all zero, the lower ones are unchanged.
2360 KnownZero = KnownZero2 | ~LowBits;
2361 KnownOne = KnownOne2 & LowBits;
2366 // Since the result is less than or equal to either operand, any leading
2367 // zero bits in either operand must also exist in the result.
2368 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2369 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2371 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2372 KnownZero2.countLeadingOnes());
2373 KnownOne.clearAllBits();
2374 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2377 case ISD::EXTRACT_ELEMENT: {
2378 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2379 const unsigned Index =
2380 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2381 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2383 // Remove low part of known bits mask
2384 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2385 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2387 // Remove high part of known bit mask
2388 KnownZero = KnownZero.trunc(BitWidth);
2389 KnownOne = KnownOne.trunc(BitWidth);
2392 case ISD::FrameIndex:
2393 case ISD::TargetFrameIndex:
2394 if (unsigned Align = InferPtrAlignment(Op)) {
2395 // The low bits are known zero if the pointer is aligned.
2396 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2402 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2405 case ISD::INTRINSIC_WO_CHAIN:
2406 case ISD::INTRINSIC_W_CHAIN:
2407 case ISD::INTRINSIC_VOID:
2408 // Allow the target to implement this method for its nodes.
2409 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2413 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2416 /// ComputeNumSignBits - Return the number of times the sign bit of the
2417 /// register is replicated into the other bits. We know that at least 1 bit
2418 /// is always equal to the sign bit (itself), but other cases can give us
2419 /// information. For example, immediately after an "SRA X, 2", we know that
2420 /// the top 3 bits are all equal to each other, so we return 3.
2421 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2422 EVT VT = Op.getValueType();
2423 assert(VT.isInteger() && "Invalid VT!");
2424 unsigned VTBits = VT.getScalarType().getSizeInBits();
2426 unsigned FirstAnswer = 1;
2429 return 1; // Limit search depth.
2431 switch (Op.getOpcode()) {
2433 case ISD::AssertSext:
2434 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2435 return VTBits-Tmp+1;
2436 case ISD::AssertZext:
2437 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2440 case ISD::Constant: {
2441 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2442 return Val.getNumSignBits();
2445 case ISD::SIGN_EXTEND:
2447 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2448 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2450 case ISD::SIGN_EXTEND_INREG:
2451 // Max of the input and what this extends.
2453 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2456 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2457 return std::max(Tmp, Tmp2);
2460 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2461 // SRA X, C -> adds C sign bits.
2462 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2463 Tmp += C->getZExtValue();
2464 if (Tmp > VTBits) Tmp = VTBits;
2468 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2469 // shl destroys sign bits.
2470 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2471 if (C->getZExtValue() >= VTBits || // Bad shift.
2472 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2473 return Tmp - C->getZExtValue();
2478 case ISD::XOR: // NOT is handled here.
2479 // Logical binary ops preserve the number of sign bits at the worst.
2480 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2482 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2483 FirstAnswer = std::min(Tmp, Tmp2);
2484 // We computed what we know about the sign bits as our first
2485 // answer. Now proceed to the generic code that uses
2486 // computeKnownBits, and pick whichever answer is better.
2491 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2492 if (Tmp == 1) return 1; // Early out.
2493 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2494 return std::min(Tmp, Tmp2);
2502 if (Op.getResNo() != 1)
2504 // The boolean result conforms to getBooleanContents. Fall through.
2505 // If setcc returns 0/-1, all bits are sign bits.
2506 // We know that we have an integer-based boolean since these operations
2507 // are only available for integer.
2508 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2509 TargetLowering::ZeroOrNegativeOneBooleanContent)
2513 // If setcc returns 0/-1, all bits are sign bits.
2514 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2515 TargetLowering::ZeroOrNegativeOneBooleanContent)
2520 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2521 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2523 // Handle rotate right by N like a rotate left by 32-N.
2524 if (Op.getOpcode() == ISD::ROTR)
2525 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2527 // If we aren't rotating out all of the known-in sign bits, return the
2528 // number that are left. This handles rotl(sext(x), 1) for example.
2529 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2530 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2534 // Add can have at most one carry bit. Thus we know that the output
2535 // is, at worst, one more bit than the inputs.
2536 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2537 if (Tmp == 1) return 1; // Early out.
2539 // Special case decrementing a value (ADD X, -1):
2540 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2541 if (CRHS->isAllOnesValue()) {
2542 APInt KnownZero, KnownOne;
2543 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2545 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2547 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2550 // If we are subtracting one from a positive number, there is no carry
2551 // out of the result.
2552 if (KnownZero.isNegative())
2556 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2557 if (Tmp2 == 1) return 1;
2558 return std::min(Tmp, Tmp2)-1;
2561 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2562 if (Tmp2 == 1) return 1;
2565 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2566 if (CLHS->isNullValue()) {
2567 APInt KnownZero, KnownOne;
2568 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2569 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2571 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2574 // If the input is known to be positive (the sign bit is known clear),
2575 // the output of the NEG has the same number of sign bits as the input.
2576 if (KnownZero.isNegative())
2579 // Otherwise, we treat this like a SUB.
2582 // Sub can have at most one carry bit. Thus we know that the output
2583 // is, at worst, one more bit than the inputs.
2584 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2585 if (Tmp == 1) return 1; // Early out.
2586 return std::min(Tmp, Tmp2)-1;
2588 // FIXME: it's tricky to do anything useful for this, but it is an important
2589 // case for targets like X86.
2591 case ISD::EXTRACT_ELEMENT: {
2592 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2593 const int BitWidth = Op.getValueType().getSizeInBits();
2595 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2597 // Get reverse index (starting from 1), Op1 value indexes elements from
2598 // little end. Sign starts at big end.
2599 const int rIndex = Items - 1 -
2600 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2602 // If the sign portion ends in our element the substraction gives correct
2603 // result. Otherwise it gives either negative or > bitwidth result
2604 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2608 // If we are looking at the loaded value of the SDNode.
2609 if (Op.getResNo() == 0) {
2610 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2611 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2612 unsigned ExtType = LD->getExtensionType();
2615 case ISD::SEXTLOAD: // '17' bits known
2616 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2617 return VTBits-Tmp+1;
2618 case ISD::ZEXTLOAD: // '16' bits known
2619 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2625 // Allow the target to implement this method for its nodes.
2626 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2627 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2628 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2629 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2630 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2631 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2634 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2635 // use this information.
2636 APInt KnownZero, KnownOne;
2637 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2640 if (KnownZero.isNegative()) { // sign bit is 0
2642 } else if (KnownOne.isNegative()) { // sign bit is 1;
2649 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2650 // the number of identical bits in the top of the input value.
2652 Mask <<= Mask.getBitWidth()-VTBits;
2653 // Return # leading zeros. We use 'min' here in case Val was zero before
2654 // shifting. We don't want to return '64' as for an i32 "0".
2655 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2658 /// isBaseWithConstantOffset - Return true if the specified operand is an
2659 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2660 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2661 /// semantics as an ADD. This handles the equivalence:
2662 /// X|Cst == X+Cst iff X&Cst = 0.
2663 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2664 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2665 !isa<ConstantSDNode>(Op.getOperand(1)))
2668 if (Op.getOpcode() == ISD::OR &&
2669 !MaskedValueIsZero(Op.getOperand(0),
2670 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2677 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2678 // If we're told that NaNs won't happen, assume they won't.
2679 if (getTarget().Options.NoNaNsFPMath)
2682 // If the value is a constant, we can obviously see if it is a NaN or not.
2683 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2684 return !C->getValueAPF().isNaN();
2686 // TODO: Recognize more cases here.
2691 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2692 // If the value is a constant, we can obviously see if it is a zero or not.
2693 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2694 return !C->isZero();
2696 // TODO: Recognize more cases here.
2697 switch (Op.getOpcode()) {
2700 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2701 return !C->isNullValue();
2708 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2709 // Check the obvious case.
2710 if (A == B) return true;
2712 // For for negative and positive zero.
2713 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2714 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2715 if (CA->isZero() && CB->isZero()) return true;
2717 // Otherwise they may not be equal.
2721 /// getNode - Gets or creates the specified node.
2723 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2724 FoldingSetNodeID ID;
2725 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2727 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2728 return SDValue(E, 0);
2730 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2731 DL.getDebugLoc(), getVTList(VT));
2732 CSEMap.InsertNode(N, IP);
2735 return SDValue(N, 0);
2738 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2739 EVT VT, SDValue Operand) {
2740 // Constant fold unary operations with an integer constant operand. Even
2741 // opaque constant will be folded, because the folding of unary operations
2742 // doesn't create new constants with different values. Nevertheless, the
2743 // opaque flag is preserved during folding to prevent future folding with
2745 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2746 const APInt &Val = C->getAPIntValue();
2749 case ISD::SIGN_EXTEND:
2750 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2751 C->isTargetOpcode(), C->isOpaque());
2752 case ISD::ANY_EXTEND:
2753 case ISD::ZERO_EXTEND:
2755 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2756 C->isTargetOpcode(), C->isOpaque());
2757 case ISD::UINT_TO_FP:
2758 case ISD::SINT_TO_FP: {
2759 APFloat apf(EVTToAPFloatSemantics(VT),
2760 APInt::getNullValue(VT.getSizeInBits()));
2761 (void)apf.convertFromAPInt(Val,
2762 Opcode==ISD::SINT_TO_FP,
2763 APFloat::rmNearestTiesToEven);
2764 return getConstantFP(apf, DL, VT);
2767 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2768 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2769 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2770 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2771 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2772 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2775 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2778 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2781 case ISD::CTLZ_ZERO_UNDEF:
2782 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2785 case ISD::CTTZ_ZERO_UNDEF:
2786 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2791 // Constant fold unary operations with a floating point constant operand.
2792 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2793 APFloat V = C->getValueAPF(); // make copy
2797 return getConstantFP(V, DL, VT);
2800 return getConstantFP(V, DL, VT);
2802 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2803 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2804 return getConstantFP(V, DL, VT);
2808 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2809 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2810 return getConstantFP(V, DL, VT);
2814 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2815 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2816 return getConstantFP(V, DL, VT);
2819 case ISD::FP_EXTEND: {
2821 // This can return overflow, underflow, or inexact; we don't care.
2822 // FIXME need to be more flexible about rounding mode.
2823 (void)V.convert(EVTToAPFloatSemantics(VT),
2824 APFloat::rmNearestTiesToEven, &ignored);
2825 return getConstantFP(V, DL, VT);
2827 case ISD::FP_TO_SINT:
2828 case ISD::FP_TO_UINT: {
2831 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2832 // FIXME need to be more flexible about rounding mode.
2833 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2834 Opcode==ISD::FP_TO_SINT,
2835 APFloat::rmTowardZero, &ignored);
2836 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2838 APInt api(VT.getSizeInBits(), x);
2839 return getConstant(api, DL, VT);
2842 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2843 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2844 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2845 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2846 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2847 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2852 // Constant fold unary operations with a vector integer or float operand.
2853 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2854 if (BV->isConstant()) {
2857 // FIXME: Entirely reasonable to perform folding of other unary
2858 // operations here as the need arises.
2865 case ISD::FP_EXTEND:
2866 case ISD::FP_TO_SINT:
2867 case ISD::FP_TO_UINT:
2869 case ISD::UINT_TO_FP:
2870 case ISD::SINT_TO_FP: {
2871 EVT SVT = VT.getScalarType();
2872 EVT InVT = BV->getValueType(0);
2873 EVT InSVT = InVT.getScalarType();
2875 // Find legal integer scalar type for constant promotion.
2877 if (SVT.isInteger()) {
2878 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2879 assert(LegalSVT.bitsGE(SVT) && "Unexpected legal scalar type size");
2882 // Let the above scalar folding handle the folding of each element.
2883 SmallVector<SDValue, 8> Ops;
2884 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2885 SDValue OpN = BV->getOperand(i);
2886 EVT OpVT = OpN.getValueType();
2888 // Build vector (integer) scalar operands may need implicit
2889 // truncation - do this before constant folding.
2890 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2891 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2893 OpN = getNode(Opcode, DL, SVT, OpN);
2895 // Legalize the (integer) scalar constant if necessary.
2896 if (LegalSVT != SVT)
2897 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2899 if (OpN.getOpcode() != ISD::UNDEF &&
2900 OpN.getOpcode() != ISD::Constant &&
2901 OpN.getOpcode() != ISD::ConstantFP)
2905 if (Ops.size() == VT.getVectorNumElements())
2906 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2913 unsigned OpOpcode = Operand.getNode()->getOpcode();
2915 case ISD::TokenFactor:
2916 case ISD::MERGE_VALUES:
2917 case ISD::CONCAT_VECTORS:
2918 return Operand; // Factor, merge or concat of one node? No need.
2919 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2920 case ISD::FP_EXTEND:
2921 assert(VT.isFloatingPoint() &&
2922 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2923 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2924 assert((!VT.isVector() ||
2925 VT.getVectorNumElements() ==
2926 Operand.getValueType().getVectorNumElements()) &&
2927 "Vector element count mismatch!");
2928 if (Operand.getOpcode() == ISD::UNDEF)
2929 return getUNDEF(VT);
2931 case ISD::SIGN_EXTEND:
2932 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2933 "Invalid SIGN_EXTEND!");
2934 if (Operand.getValueType() == VT) return Operand; // noop extension
2935 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2936 "Invalid sext node, dst < src!");
2937 assert((!VT.isVector() ||
2938 VT.getVectorNumElements() ==
2939 Operand.getValueType().getVectorNumElements()) &&
2940 "Vector element count mismatch!");
2941 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2942 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2943 else if (OpOpcode == ISD::UNDEF)
2944 // sext(undef) = 0, because the top bits will all be the same.
2945 return getConstant(0, DL, VT);
2947 case ISD::ZERO_EXTEND:
2948 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2949 "Invalid ZERO_EXTEND!");
2950 if (Operand.getValueType() == VT) return Operand; // noop extension
2951 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2952 "Invalid zext node, dst < src!");
2953 assert((!VT.isVector() ||
2954 VT.getVectorNumElements() ==
2955 Operand.getValueType().getVectorNumElements()) &&
2956 "Vector element count mismatch!");
2957 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2958 return getNode(ISD::ZERO_EXTEND, DL, VT,
2959 Operand.getNode()->getOperand(0));
2960 else if (OpOpcode == ISD::UNDEF)
2961 // zext(undef) = 0, because the top bits will be zero.
2962 return getConstant(0, DL, VT);
2964 case ISD::ANY_EXTEND:
2965 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2966 "Invalid ANY_EXTEND!");
2967 if (Operand.getValueType() == VT) return Operand; // noop extension
2968 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2969 "Invalid anyext node, dst < src!");
2970 assert((!VT.isVector() ||
2971 VT.getVectorNumElements() ==
2972 Operand.getValueType().getVectorNumElements()) &&
2973 "Vector element count mismatch!");
2975 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2976 OpOpcode == ISD::ANY_EXTEND)
2977 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2978 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2979 else if (OpOpcode == ISD::UNDEF)
2980 return getUNDEF(VT);
2982 // (ext (trunx x)) -> x
2983 if (OpOpcode == ISD::TRUNCATE) {
2984 SDValue OpOp = Operand.getNode()->getOperand(0);
2985 if (OpOp.getValueType() == VT)
2990 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2991 "Invalid TRUNCATE!");
2992 if (Operand.getValueType() == VT) return Operand; // noop truncate
2993 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2994 "Invalid truncate node, src < dst!");
2995 assert((!VT.isVector() ||
2996 VT.getVectorNumElements() ==
2997 Operand.getValueType().getVectorNumElements()) &&
2998 "Vector element count mismatch!");
2999 if (OpOpcode == ISD::TRUNCATE)
3000 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3001 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3002 OpOpcode == ISD::ANY_EXTEND) {
3003 // If the source is smaller than the dest, we still need an extend.
3004 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3005 .bitsLT(VT.getScalarType()))
3006 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3007 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3008 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3009 return Operand.getNode()->getOperand(0);
3011 if (OpOpcode == ISD::UNDEF)
3012 return getUNDEF(VT);
3015 // Basic sanity checking.
3016 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3017 && "Cannot BITCAST between types of different sizes!");
3018 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3019 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3020 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3021 if (OpOpcode == ISD::UNDEF)
3022 return getUNDEF(VT);
3024 case ISD::SCALAR_TO_VECTOR:
3025 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3026 (VT.getVectorElementType() == Operand.getValueType() ||
3027 (VT.getVectorElementType().isInteger() &&
3028 Operand.getValueType().isInteger() &&
3029 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3030 "Illegal SCALAR_TO_VECTOR node!");
3031 if (OpOpcode == ISD::UNDEF)
3032 return getUNDEF(VT);
3033 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3034 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3035 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3036 Operand.getConstantOperandVal(1) == 0 &&
3037 Operand.getOperand(0).getValueType() == VT)
3038 return Operand.getOperand(0);
3041 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3042 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3043 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3044 Operand.getNode()->getOperand(0));
3045 if (OpOpcode == ISD::FNEG) // --X -> X
3046 return Operand.getNode()->getOperand(0);
3049 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3050 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3055 SDVTList VTs = getVTList(VT);
3056 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3057 FoldingSetNodeID ID;
3058 SDValue Ops[1] = { Operand };
3059 AddNodeIDNode(ID, Opcode, VTs, Ops);
3061 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3062 return SDValue(E, 0);
3064 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3065 DL.getDebugLoc(), VTs, Operand);
3066 CSEMap.InsertNode(N, IP);
3068 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3069 DL.getDebugLoc(), VTs, Operand);
3073 return SDValue(N, 0);
3076 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3077 SDNode *Cst1, SDNode *Cst2) {
3078 // If the opcode is a target-specific ISD node, there's nothing we can
3079 // do here and the operand rules may not line up with the below, so
3081 if (Opcode >= ISD::BUILTIN_OP_END)
3084 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3085 SmallVector<SDValue, 4> Outputs;
3086 EVT SVT = VT.getScalarType();
3088 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3089 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3090 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3093 if (Scalar1 && Scalar2)
3094 // Scalar instruction.
3095 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3097 // For vectors extract each constant element into Inputs so we can constant
3098 // fold them individually.
3099 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3100 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3104 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3106 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3107 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3108 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3109 if (!V1 || !V2) // Not a constant, bail.
3112 if (V1->isOpaque() || V2->isOpaque())
3115 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3116 // FIXME: This is valid and could be handled by truncating the APInts.
3117 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3120 Inputs.push_back(std::make_pair(V1, V2));
3124 // We have a number of constant values, constant fold them element by element.
3125 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3126 const APInt &C1 = Inputs[I].first->getAPIntValue();
3127 const APInt &C2 = Inputs[I].second->getAPIntValue();
3131 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3134 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3137 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3140 if (!C2.getBoolValue())
3142 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3145 if (!C2.getBoolValue())
3147 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3150 if (!C2.getBoolValue())
3152 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3155 if (!C2.getBoolValue())
3157 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3160 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3163 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3166 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3169 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3172 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3175 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3178 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3181 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3188 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3189 "Expected a scalar or vector!"));
3191 // Handle the scalar case first.
3193 return Outputs.back();
3195 // We may have a vector type but a scalar result. Create a splat.
3196 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3198 // Build a big vector out of the scalar elements we generated.
3199 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3202 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3203 SDValue N2, bool nuw, bool nsw, bool exact) {
3204 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3205 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3208 case ISD::TokenFactor:
3209 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3210 N2.getValueType() == MVT::Other && "Invalid token factor!");
3211 // Fold trivial token factors.
3212 if (N1.getOpcode() == ISD::EntryToken) return N2;
3213 if (N2.getOpcode() == ISD::EntryToken) return N1;
3214 if (N1 == N2) return N1;
3216 case ISD::CONCAT_VECTORS:
3217 // Concat of UNDEFs is UNDEF.
3218 if (N1.getOpcode() == ISD::UNDEF &&
3219 N2.getOpcode() == ISD::UNDEF)
3220 return getUNDEF(VT);
3222 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3223 // one big BUILD_VECTOR.
3224 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3225 N2.getOpcode() == ISD::BUILD_VECTOR) {
3226 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3227 N1.getNode()->op_end());
3228 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3230 // BUILD_VECTOR requires all inputs to be of the same type, find the
3231 // maximum type and extend them all.
3232 EVT SVT = VT.getScalarType();
3233 for (SDValue Op : Elts)
3234 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3235 if (SVT.bitsGT(VT.getScalarType()))
3236 for (SDValue &Op : Elts)
3237 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3238 ? getZExtOrTrunc(Op, DL, SVT)
3239 : getSExtOrTrunc(Op, DL, SVT);
3241 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3245 assert(VT.isInteger() && "This operator does not apply to FP types!");
3246 assert(N1.getValueType() == N2.getValueType() &&
3247 N1.getValueType() == VT && "Binary operator types must match!");
3248 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3249 // worth handling here.
3250 if (N2C && N2C->isNullValue())
3252 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3259 assert(VT.isInteger() && "This operator does not apply to FP types!");
3260 assert(N1.getValueType() == N2.getValueType() &&
3261 N1.getValueType() == VT && "Binary operator types must match!");
3262 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3263 // it's worth handling here.
3264 if (N2C && N2C->isNullValue())
3274 assert(VT.isInteger() && "This operator does not apply to FP types!");
3275 assert(N1.getValueType() == N2.getValueType() &&
3276 N1.getValueType() == VT && "Binary operator types must match!");
3283 if (getTarget().Options.UnsafeFPMath) {
3284 if (Opcode == ISD::FADD) {
3286 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3287 if (CFP->getValueAPF().isZero())
3290 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3291 if (CFP->getValueAPF().isZero())
3293 } else if (Opcode == ISD::FSUB) {
3295 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3296 if (CFP->getValueAPF().isZero())
3298 } else if (Opcode == ISD::FMUL) {
3299 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3302 // If the first operand isn't the constant, try the second
3304 CFP = dyn_cast<ConstantFPSDNode>(N2);
3311 return SDValue(CFP,0);
3313 if (CFP->isExactlyValue(1.0))
3318 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3319 assert(N1.getValueType() == N2.getValueType() &&
3320 N1.getValueType() == VT && "Binary operator types must match!");
3322 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3323 assert(N1.getValueType() == VT &&
3324 N1.getValueType().isFloatingPoint() &&
3325 N2.getValueType().isFloatingPoint() &&
3326 "Invalid FCOPYSIGN!");
3333 assert(VT == N1.getValueType() &&
3334 "Shift operators return type must be the same as their first arg");
3335 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3336 "Shifts only work on integers");
3337 assert((!VT.isVector() || VT == N2.getValueType()) &&
3338 "Vector shift amounts must be in the same as their first arg");
3339 // Verify that the shift amount VT is bit enough to hold valid shift
3340 // amounts. This catches things like trying to shift an i1024 value by an
3341 // i8, which is easy to fall into in generic code that uses
3342 // TLI.getShiftAmount().
3343 assert(N2.getValueType().getSizeInBits() >=
3344 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3345 "Invalid use of small shift amount with oversized value!");
3347 // Always fold shifts of i1 values so the code generator doesn't need to
3348 // handle them. Since we know the size of the shift has to be less than the
3349 // size of the value, the shift/rotate count is guaranteed to be zero.
3352 if (N2C && N2C->isNullValue())
3355 case ISD::FP_ROUND_INREG: {
3356 EVT EVT = cast<VTSDNode>(N2)->getVT();
3357 assert(VT == N1.getValueType() && "Not an inreg round!");
3358 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3359 "Cannot FP_ROUND_INREG integer types");
3360 assert(EVT.isVector() == VT.isVector() &&
3361 "FP_ROUND_INREG type should be vector iff the operand "
3363 assert((!EVT.isVector() ||
3364 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3365 "Vector element counts must match in FP_ROUND_INREG");
3366 assert(EVT.bitsLE(VT) && "Not rounding down!");
3368 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3372 assert(VT.isFloatingPoint() &&
3373 N1.getValueType().isFloatingPoint() &&
3374 VT.bitsLE(N1.getValueType()) &&
3375 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3376 if (N1.getValueType() == VT) return N1; // noop conversion.
3378 case ISD::AssertSext:
3379 case ISD::AssertZext: {
3380 EVT EVT = cast<VTSDNode>(N2)->getVT();
3381 assert(VT == N1.getValueType() && "Not an inreg extend!");
3382 assert(VT.isInteger() && EVT.isInteger() &&
3383 "Cannot *_EXTEND_INREG FP types");
3384 assert(!EVT.isVector() &&
3385 "AssertSExt/AssertZExt type should be the vector element type "
3386 "rather than the vector type!");
3387 assert(EVT.bitsLE(VT) && "Not extending!");
3388 if (VT == EVT) return N1; // noop assertion.
3391 case ISD::SIGN_EXTEND_INREG: {
3392 EVT EVT = cast<VTSDNode>(N2)->getVT();
3393 assert(VT == N1.getValueType() && "Not an inreg extend!");
3394 assert(VT.isInteger() && EVT.isInteger() &&
3395 "Cannot *_EXTEND_INREG FP types");
3396 assert(EVT.isVector() == VT.isVector() &&
3397 "SIGN_EXTEND_INREG type should be vector iff the operand "
3399 assert((!EVT.isVector() ||
3400 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3401 "Vector element counts must match in SIGN_EXTEND_INREG");
3402 assert(EVT.bitsLE(VT) && "Not extending!");
3403 if (EVT == VT) return N1; // Not actually extending
3406 APInt Val = N1C->getAPIntValue();
3407 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3408 Val <<= Val.getBitWidth()-FromBits;
3409 Val = Val.ashr(Val.getBitWidth()-FromBits);
3410 return getConstant(Val, DL, VT);
3414 case ISD::EXTRACT_VECTOR_ELT:
3415 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3416 if (N1.getOpcode() == ISD::UNDEF)
3417 return getUNDEF(VT);
3419 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3420 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3421 return getUNDEF(VT);
3423 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3424 // expanding copies of large vectors from registers.
3426 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3427 N1.getNumOperands() > 0) {
3429 N1.getOperand(0).getValueType().getVectorNumElements();
3430 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3431 N1.getOperand(N2C->getZExtValue() / Factor),
3432 getConstant(N2C->getZExtValue() % Factor, DL,
3433 N2.getValueType()));
3436 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3437 // expanding large vector constants.
3438 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3439 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3441 if (VT != Elt.getValueType())
3442 // If the vector element type is not legal, the BUILD_VECTOR operands
3443 // are promoted and implicitly truncated, and the result implicitly
3444 // extended. Make that explicit here.
3445 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3450 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3451 // operations are lowered to scalars.
3452 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3453 // If the indices are the same, return the inserted element else
3454 // if the indices are known different, extract the element from
3455 // the original vector.
3456 SDValue N1Op2 = N1.getOperand(2);
3457 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3459 if (N1Op2C && N2C) {
3460 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3461 if (VT == N1.getOperand(1).getValueType())
3462 return N1.getOperand(1);
3464 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3467 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3471 case ISD::EXTRACT_ELEMENT:
3472 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3473 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3474 (N1.getValueType().isInteger() == VT.isInteger()) &&
3475 N1.getValueType() != VT &&
3476 "Wrong types for EXTRACT_ELEMENT!");
3478 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3479 // 64-bit integers into 32-bit parts. Instead of building the extract of
3480 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3481 if (N1.getOpcode() == ISD::BUILD_PAIR)
3482 return N1.getOperand(N2C->getZExtValue());
3484 // EXTRACT_ELEMENT of a constant int is also very common.
3485 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3486 unsigned ElementSize = VT.getSizeInBits();
3487 unsigned Shift = ElementSize * N2C->getZExtValue();
3488 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3489 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3492 case ISD::EXTRACT_SUBVECTOR: {
3494 if (VT.isSimple() && N1.getValueType().isSimple()) {
3495 assert(VT.isVector() && N1.getValueType().isVector() &&
3496 "Extract subvector VTs must be a vectors!");
3497 assert(VT.getVectorElementType() ==
3498 N1.getValueType().getVectorElementType() &&
3499 "Extract subvector VTs must have the same element type!");
3500 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3501 "Extract subvector must be from larger vector to smaller vector!");
3503 if (isa<ConstantSDNode>(Index.getNode())) {
3504 assert((VT.getVectorNumElements() +
3505 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3506 <= N1.getValueType().getVectorNumElements())
3507 && "Extract subvector overflow!");
3510 // Trivial extraction.
3511 if (VT.getSimpleVT() == N1.getSimpleValueType())
3518 // Perform trivial constant folding.
3520 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3523 // Canonicalize constant to RHS if commutative.
3524 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3525 std::swap(N1C, N2C);
3529 // Constant fold FP operations.
3530 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3531 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3532 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3534 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3535 // Canonicalize constant to RHS if commutative.
3536 std::swap(N1CFP, N2CFP);
3539 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3540 APFloat::opStatus s;
3543 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3544 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3545 return getConstantFP(V1, DL, VT);
3548 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3549 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3550 return getConstantFP(V1, DL, VT);
3553 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3554 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3555 return getConstantFP(V1, DL, VT);
3558 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3559 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3560 s!=APFloat::opDivByZero)) {
3561 return getConstantFP(V1, DL, VT);
3565 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3566 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3567 s!=APFloat::opDivByZero)) {
3568 return getConstantFP(V1, DL, VT);
3571 case ISD::FCOPYSIGN:
3573 return getConstantFP(V1, DL, VT);
3578 if (Opcode == ISD::FP_ROUND) {
3579 APFloat V = N1CFP->getValueAPF(); // make copy
3581 // This can return overflow, underflow, or inexact; we don't care.
3582 // FIXME need to be more flexible about rounding mode.
3583 (void)V.convert(EVTToAPFloatSemantics(VT),
3584 APFloat::rmNearestTiesToEven, &ignored);
3585 return getConstantFP(V, DL, VT);
3589 // Canonicalize an UNDEF to the RHS, even over a constant.
3590 if (N1.getOpcode() == ISD::UNDEF) {
3591 if (isCommutativeBinOp(Opcode)) {
3595 case ISD::FP_ROUND_INREG:
3596 case ISD::SIGN_EXTEND_INREG:
3602 return N1; // fold op(undef, arg2) -> undef
3610 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3611 // For vectors, we can't easily build an all zero vector, just return
3618 // Fold a bunch of operators when the RHS is undef.
3619 if (N2.getOpcode() == ISD::UNDEF) {
3622 if (N1.getOpcode() == ISD::UNDEF)
3623 // Handle undef ^ undef -> 0 special case. This is a common
3625 return getConstant(0, DL, VT);
3635 return N2; // fold op(arg1, undef) -> undef
3641 if (getTarget().Options.UnsafeFPMath)
3649 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3650 // For vectors, we can't easily build an all zero vector, just return
3655 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3656 // For vectors, we can't easily build an all one vector, just return
3664 // Memoize this node if possible.
3666 SDVTList VTs = getVTList(VT);
3667 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3668 if (VT != MVT::Glue) {
3669 SDValue Ops[] = {N1, N2};
3670 FoldingSetNodeID ID;
3671 AddNodeIDNode(ID, Opcode, VTs, Ops);
3673 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3675 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3676 return SDValue(E, 0);
3678 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3680 CSEMap.InsertNode(N, IP);
3682 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3686 return SDValue(N, 0);
3689 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3690 SDValue N1, SDValue N2, SDValue N3) {
3691 // Perform various simplifications.
3692 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3695 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3696 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3697 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3698 if (N1CFP && N2CFP && N3CFP) {
3699 APFloat V1 = N1CFP->getValueAPF();
3700 const APFloat &V2 = N2CFP->getValueAPF();
3701 const APFloat &V3 = N3CFP->getValueAPF();
3702 APFloat::opStatus s =
3703 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3704 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3705 return getConstantFP(V1, DL, VT);
3709 case ISD::CONCAT_VECTORS:
3710 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3711 // one big BUILD_VECTOR.
3712 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3713 N2.getOpcode() == ISD::BUILD_VECTOR &&
3714 N3.getOpcode() == ISD::BUILD_VECTOR) {
3715 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3716 N1.getNode()->op_end());
3717 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3718 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3719 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3723 // Use FoldSetCC to simplify SETCC's.
3724 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3725 if (Simp.getNode()) return Simp;
3730 if (N1C->getZExtValue())
3731 return N2; // select true, X, Y -> X
3732 return N3; // select false, X, Y -> Y
3735 if (N2 == N3) return N2; // select C, X, X -> X
3737 case ISD::VECTOR_SHUFFLE:
3738 llvm_unreachable("should use getVectorShuffle constructor!");
3739 case ISD::INSERT_SUBVECTOR: {
3741 if (VT.isSimple() && N1.getValueType().isSimple()
3742 && N2.getValueType().isSimple()) {
3743 assert(VT.isVector() && N1.getValueType().isVector() &&
3744 N2.getValueType().isVector() &&
3745 "Insert subvector VTs must be a vectors");
3746 assert(VT == N1.getValueType() &&
3747 "Dest and insert subvector source types must match!");
3748 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3749 "Insert subvector must be from smaller vector to larger vector!");
3750 if (isa<ConstantSDNode>(Index.getNode())) {
3751 assert((N2.getValueType().getVectorNumElements() +
3752 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3753 <= VT.getVectorNumElements())
3754 && "Insert subvector overflow!");
3757 // Trivial insertion.
3758 if (VT.getSimpleVT() == N2.getSimpleValueType())
3764 // Fold bit_convert nodes from a type to themselves.
3765 if (N1.getValueType() == VT)
3770 // Memoize node if it doesn't produce a flag.
3772 SDVTList VTs = getVTList(VT);
3773 if (VT != MVT::Glue) {
3774 SDValue Ops[] = { N1, N2, N3 };
3775 FoldingSetNodeID ID;
3776 AddNodeIDNode(ID, Opcode, VTs, Ops);
3778 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3779 return SDValue(E, 0);
3781 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3782 DL.getDebugLoc(), VTs, N1, N2, N3);
3783 CSEMap.InsertNode(N, IP);
3785 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3786 DL.getDebugLoc(), VTs, N1, N2, N3);
3790 return SDValue(N, 0);
3793 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3794 SDValue N1, SDValue N2, SDValue N3,
3796 SDValue Ops[] = { N1, N2, N3, N4 };
3797 return getNode(Opcode, DL, VT, Ops);
3800 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3801 SDValue N1, SDValue N2, SDValue N3,
3802 SDValue N4, SDValue N5) {
3803 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3804 return getNode(Opcode, DL, VT, Ops);
3807 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3808 /// the incoming stack arguments to be loaded from the stack.
3809 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3810 SmallVector<SDValue, 8> ArgChains;
3812 // Include the original chain at the beginning of the list. When this is
3813 // used by target LowerCall hooks, this helps legalize find the
3814 // CALLSEQ_BEGIN node.
3815 ArgChains.push_back(Chain);
3817 // Add a chain value for each stack argument.
3818 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3819 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3820 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3821 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3822 if (FI->getIndex() < 0)
3823 ArgChains.push_back(SDValue(L, 1));
3825 // Build a tokenfactor for all the chains.
3826 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3829 /// getMemsetValue - Vectorized representation of the memset value
3831 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3833 assert(Value.getOpcode() != ISD::UNDEF);
3835 unsigned NumBits = VT.getScalarType().getSizeInBits();
3836 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3837 assert(C->getAPIntValue().getBitWidth() == 8);
3838 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3840 return DAG.getConstant(Val, dl, VT);
3841 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3845 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3846 EVT IntVT = VT.getScalarType();
3847 if (!IntVT.isInteger())
3848 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3850 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3852 // Use a multiplication with 0x010101... to extend the input to the
3854 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3855 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3856 DAG.getConstant(Magic, dl, IntVT));
3859 if (VT != Value.getValueType() && !VT.isInteger())
3860 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3861 if (VT != Value.getValueType()) {
3862 assert(VT.getVectorElementType() == Value.getValueType() &&
3863 "value type should be one vector element here");
3864 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3865 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3871 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3872 /// used when a memcpy is turned into a memset when the source is a constant
3874 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3875 const TargetLowering &TLI, StringRef Str) {
3876 // Handle vector with all elements zero.
3879 return DAG.getConstant(0, dl, VT);
3880 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3881 return DAG.getConstantFP(0.0, dl, VT);
3882 else if (VT.isVector()) {
3883 unsigned NumElts = VT.getVectorNumElements();
3884 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3885 return DAG.getNode(ISD::BITCAST, dl, VT,
3886 DAG.getConstant(0, dl,
3887 EVT::getVectorVT(*DAG.getContext(),
3890 llvm_unreachable("Expected type!");
3893 assert(!VT.isVector() && "Can't handle vector type here!");
3894 unsigned NumVTBits = VT.getSizeInBits();
3895 unsigned NumVTBytes = NumVTBits / 8;
3896 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3898 APInt Val(NumVTBits, 0);
3899 if (TLI.isLittleEndian()) {
3900 for (unsigned i = 0; i != NumBytes; ++i)
3901 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3903 for (unsigned i = 0; i != NumBytes; ++i)
3904 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3907 // If the "cost" of materializing the integer immediate is less than the cost
3908 // of a load, then it is cost effective to turn the load into the immediate.
3909 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3910 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3911 return DAG.getConstant(Val, dl, VT);
3912 return SDValue(nullptr, 0);
3915 /// getMemBasePlusOffset - Returns base and offset node for the
3917 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3918 SelectionDAG &DAG) {
3919 EVT VT = Base.getValueType();
3920 return DAG.getNode(ISD::ADD, dl,
3921 VT, Base, DAG.getConstant(Offset, dl, VT));
3924 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3926 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3927 unsigned SrcDelta = 0;
3928 GlobalAddressSDNode *G = nullptr;
3929 if (Src.getOpcode() == ISD::GlobalAddress)
3930 G = cast<GlobalAddressSDNode>(Src);
3931 else if (Src.getOpcode() == ISD::ADD &&
3932 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3933 Src.getOperand(1).getOpcode() == ISD::Constant) {
3934 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3935 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3940 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3943 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3944 /// to replace the memset / memcpy. Return true if the number of memory ops
3945 /// is below the threshold. It returns the types of the sequence of
3946 /// memory ops to perform memset / memcpy by reference.
3947 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3948 unsigned Limit, uint64_t Size,
3949 unsigned DstAlign, unsigned SrcAlign,
3955 const TargetLowering &TLI) {
3956 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3957 "Expecting memcpy / memset source to meet alignment requirement!");
3958 // If 'SrcAlign' is zero, that means the memory operation does not need to
3959 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3960 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3961 // is the specified alignment of the memory operation. If it is zero, that
3962 // means it's possible to change the alignment of the destination.
3963 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3964 // not need to be loaded.
3965 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3966 IsMemset, ZeroMemset, MemcpyStrSrc,
3967 DAG.getMachineFunction());
3969 if (VT == MVT::Other) {
3971 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3972 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3973 VT = TLI.getPointerTy();
3975 switch (DstAlign & 7) {
3976 case 0: VT = MVT::i64; break;
3977 case 4: VT = MVT::i32; break;
3978 case 2: VT = MVT::i16; break;
3979 default: VT = MVT::i8; break;
3984 while (!TLI.isTypeLegal(LVT))
3985 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3986 assert(LVT.isInteger());
3992 unsigned NumMemOps = 0;
3994 unsigned VTSize = VT.getSizeInBits() / 8;
3995 while (VTSize > Size) {
3996 // For now, only use non-vector load / store's for the left-over pieces.
4001 if (VT.isVector() || VT.isFloatingPoint()) {
4002 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4003 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4004 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4006 else if (NewVT == MVT::i64 &&
4007 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4008 TLI.isSafeMemOpType(MVT::f64)) {
4009 // i64 is usually not legal on 32-bit targets, but f64 may be.
4017 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4018 if (NewVT == MVT::i8)
4020 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4022 NewVTSize = NewVT.getSizeInBits() / 8;
4024 // If the new VT cannot cover all of the remaining bits, then consider
4025 // issuing a (or a pair of) unaligned and overlapping load / store.
4026 // FIXME: Only does this for 64-bit or more since we don't have proper
4027 // cost model for unaligned load / store.
4030 if (NumMemOps && AllowOverlap &&
4031 VTSize >= 8 && NewVTSize < Size &&
4032 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4040 if (++NumMemOps > Limit)
4043 MemOps.push_back(VT);
4050 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4051 SDValue Chain, SDValue Dst,
4052 SDValue Src, uint64_t Size,
4053 unsigned Align, bool isVol,
4055 MachinePointerInfo DstPtrInfo,
4056 MachinePointerInfo SrcPtrInfo) {
4057 // Turn a memcpy of undef to nop.
4058 if (Src.getOpcode() == ISD::UNDEF)
4061 // Expand memcpy to a series of load and store ops if the size operand falls
4062 // below a certain threshold.
4063 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4064 // rather than maybe a humongous number of loads and stores.
4065 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4066 std::vector<EVT> MemOps;
4067 bool DstAlignCanChange = false;
4068 MachineFunction &MF = DAG.getMachineFunction();
4069 MachineFrameInfo *MFI = MF.getFrameInfo();
4070 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4071 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4072 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4073 DstAlignCanChange = true;
4074 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4075 if (Align > SrcAlign)
4078 bool CopyFromStr = isMemSrcFromString(Src, Str);
4079 bool isZeroStr = CopyFromStr && Str.empty();
4080 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4082 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4083 (DstAlignCanChange ? 0 : Align),
4084 (isZeroStr ? 0 : SrcAlign),
4085 false, false, CopyFromStr, true, DAG, TLI))
4088 if (DstAlignCanChange) {
4089 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4090 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4092 // Don't promote to an alignment that would require dynamic stack
4094 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4095 if (!TRI->needsStackRealignment(MF))
4096 while (NewAlign > Align &&
4097 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4100 if (NewAlign > Align) {
4101 // Give the stack frame object a larger alignment if needed.
4102 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4103 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4108 SmallVector<SDValue, 8> OutChains;
4109 unsigned NumMemOps = MemOps.size();
4110 uint64_t SrcOff = 0, DstOff = 0;
4111 for (unsigned i = 0; i != NumMemOps; ++i) {
4113 unsigned VTSize = VT.getSizeInBits() / 8;
4114 SDValue Value, Store;
4116 if (VTSize > Size) {
4117 // Issuing an unaligned load / store pair that overlaps with the previous
4118 // pair. Adjust the offset accordingly.
4119 assert(i == NumMemOps-1 && i != 0);
4120 SrcOff -= VTSize - Size;
4121 DstOff -= VTSize - Size;
4125 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4126 // It's unlikely a store of a vector immediate can be done in a single
4127 // instruction. It would require a load from a constantpool first.
4128 // We only handle zero vectors here.
4129 // FIXME: Handle other cases where store of vector immediate is done in
4130 // a single instruction.
4131 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4132 if (Value.getNode())
4133 Store = DAG.getStore(Chain, dl, Value,
4134 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4135 DstPtrInfo.getWithOffset(DstOff), isVol,
4139 if (!Store.getNode()) {
4140 // The type might not be legal for the target. This should only happen
4141 // if the type is smaller than a legal type, as on PPC, so the right
4142 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4143 // to Load/Store if NVT==VT.
4144 // FIXME does the case above also need this?
4145 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4146 assert(NVT.bitsGE(VT));
4147 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4148 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4149 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4150 false, MinAlign(SrcAlign, SrcOff));
4151 Store = DAG.getTruncStore(Chain, dl, Value,
4152 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4153 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4156 OutChains.push_back(Store);
4162 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4165 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4166 SDValue Chain, SDValue Dst,
4167 SDValue Src, uint64_t Size,
4168 unsigned Align, bool isVol,
4170 MachinePointerInfo DstPtrInfo,
4171 MachinePointerInfo SrcPtrInfo) {
4172 // Turn a memmove of undef to nop.
4173 if (Src.getOpcode() == ISD::UNDEF)
4176 // Expand memmove to a series of load and store ops if the size operand falls
4177 // below a certain threshold.
4178 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4179 std::vector<EVT> MemOps;
4180 bool DstAlignCanChange = false;
4181 MachineFunction &MF = DAG.getMachineFunction();
4182 MachineFrameInfo *MFI = MF.getFrameInfo();
4183 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4184 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4185 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4186 DstAlignCanChange = true;
4187 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4188 if (Align > SrcAlign)
4190 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4192 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4193 (DstAlignCanChange ? 0 : Align), SrcAlign,
4194 false, false, false, false, DAG, TLI))
4197 if (DstAlignCanChange) {
4198 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4199 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4200 if (NewAlign > Align) {
4201 // Give the stack frame object a larger alignment if needed.
4202 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4203 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4208 uint64_t SrcOff = 0, DstOff = 0;
4209 SmallVector<SDValue, 8> LoadValues;
4210 SmallVector<SDValue, 8> LoadChains;
4211 SmallVector<SDValue, 8> OutChains;
4212 unsigned NumMemOps = MemOps.size();
4213 for (unsigned i = 0; i < NumMemOps; i++) {
4215 unsigned VTSize = VT.getSizeInBits() / 8;
4218 Value = DAG.getLoad(VT, dl, Chain,
4219 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4220 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4221 false, false, SrcAlign);
4222 LoadValues.push_back(Value);
4223 LoadChains.push_back(Value.getValue(1));
4226 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4228 for (unsigned i = 0; i < NumMemOps; i++) {
4230 unsigned VTSize = VT.getSizeInBits() / 8;
4233 Store = DAG.getStore(Chain, dl, LoadValues[i],
4234 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4235 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4236 OutChains.push_back(Store);
4240 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4243 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4246 /// \param DAG Selection DAG where lowered code is placed.
4247 /// \param dl Link to corresponding IR location.
4248 /// \param Chain Control flow dependency.
4249 /// \param Dst Pointer to destination memory location.
4250 /// \param Src Value of byte to write into the memory.
4251 /// \param Size Number of bytes to write.
4252 /// \param Align Alignment of the destination in bytes.
4253 /// \param isVol True if destination is volatile.
4254 /// \param DstPtrInfo IR information on the memory pointer.
4255 /// \returns New head in the control flow, if lowering was successful, empty
4256 /// SDValue otherwise.
4258 /// The function tries to replace 'llvm.memset' intrinsic with several store
4259 /// operations and value calculation code. This is usually profitable for small
4261 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4262 SDValue Chain, SDValue Dst,
4263 SDValue Src, uint64_t Size,
4264 unsigned Align, bool isVol,
4265 MachinePointerInfo DstPtrInfo) {
4266 // Turn a memset of undef to nop.
4267 if (Src.getOpcode() == ISD::UNDEF)
4270 // Expand memset to a series of load/store ops if the size operand
4271 // falls below a certain threshold.
4272 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4273 std::vector<EVT> MemOps;
4274 bool DstAlignCanChange = false;
4275 MachineFunction &MF = DAG.getMachineFunction();
4276 MachineFrameInfo *MFI = MF.getFrameInfo();
4277 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4278 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4279 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4280 DstAlignCanChange = true;
4282 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4283 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4284 Size, (DstAlignCanChange ? 0 : Align), 0,
4285 true, IsZeroVal, false, true, DAG, TLI))
4288 if (DstAlignCanChange) {
4289 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4290 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4291 if (NewAlign > Align) {
4292 // Give the stack frame object a larger alignment if needed.
4293 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4294 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4299 SmallVector<SDValue, 8> OutChains;
4300 uint64_t DstOff = 0;
4301 unsigned NumMemOps = MemOps.size();
4303 // Find the largest store and generate the bit pattern for it.
4304 EVT LargestVT = MemOps[0];
4305 for (unsigned i = 1; i < NumMemOps; i++)
4306 if (MemOps[i].bitsGT(LargestVT))
4307 LargestVT = MemOps[i];
4308 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4310 for (unsigned i = 0; i < NumMemOps; i++) {
4312 unsigned VTSize = VT.getSizeInBits() / 8;
4313 if (VTSize > Size) {
4314 // Issuing an unaligned load / store pair that overlaps with the previous
4315 // pair. Adjust the offset accordingly.
4316 assert(i == NumMemOps-1 && i != 0);
4317 DstOff -= VTSize - Size;
4320 // If this store is smaller than the largest store see whether we can get
4321 // the smaller value for free with a truncate.
4322 SDValue Value = MemSetValue;
4323 if (VT.bitsLT(LargestVT)) {
4324 if (!LargestVT.isVector() && !VT.isVector() &&
4325 TLI.isTruncateFree(LargestVT, VT))
4326 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4328 Value = getMemsetValue(Src, VT, DAG, dl);
4330 assert(Value.getValueType() == VT && "Value with wrong type.");
4331 SDValue Store = DAG.getStore(Chain, dl, Value,
4332 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4333 DstPtrInfo.getWithOffset(DstOff),
4334 isVol, false, Align);
4335 OutChains.push_back(Store);
4336 DstOff += VT.getSizeInBits() / 8;
4340 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4343 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4344 SDValue Src, SDValue Size,
4345 unsigned Align, bool isVol, bool AlwaysInline,
4346 bool isTailCall, MachinePointerInfo DstPtrInfo,
4347 MachinePointerInfo SrcPtrInfo) {
4348 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4350 // Check to see if we should lower the memcpy to loads and stores first.
4351 // For cases within the target-specified limits, this is the best choice.
4352 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4354 // Memcpy with size zero? Just return the original chain.
4355 if (ConstantSize->isNullValue())
4358 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4359 ConstantSize->getZExtValue(),Align,
4360 isVol, false, DstPtrInfo, SrcPtrInfo);
4361 if (Result.getNode())
4365 // Then check to see if we should lower the memcpy with target-specific
4366 // code. If the target chooses to do this, this is the next best.
4368 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4369 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4370 DstPtrInfo, SrcPtrInfo);
4371 if (Result.getNode())
4375 // If we really need inline code and the target declined to provide it,
4376 // use a (potentially long) sequence of loads and stores.
4378 assert(ConstantSize && "AlwaysInline requires a constant size!");
4379 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4380 ConstantSize->getZExtValue(), Align, isVol,
4381 true, DstPtrInfo, SrcPtrInfo);
4384 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4385 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4386 // respect volatile, so they may do things like read or write memory
4387 // beyond the given memory regions. But fixing this isn't easy, and most
4388 // people don't care.
4390 // Emit a library call.
4391 TargetLowering::ArgListTy Args;
4392 TargetLowering::ArgListEntry Entry;
4393 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4394 Entry.Node = Dst; Args.push_back(Entry);
4395 Entry.Node = Src; Args.push_back(Entry);
4396 Entry.Node = Size; Args.push_back(Entry);
4397 // FIXME: pass in SDLoc
4398 TargetLowering::CallLoweringInfo CLI(*this);
4399 CLI.setDebugLoc(dl).setChain(Chain)
4400 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4401 Type::getVoidTy(*getContext()),
4402 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4403 TLI->getPointerTy()), std::move(Args), 0)
4405 .setTailCall(isTailCall);
4407 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4408 return CallResult.second;
4411 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4412 SDValue Src, SDValue Size,
4413 unsigned Align, bool isVol, bool isTailCall,
4414 MachinePointerInfo DstPtrInfo,
4415 MachinePointerInfo SrcPtrInfo) {
4416 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4418 // Check to see if we should lower the memmove to loads and stores first.
4419 // For cases within the target-specified limits, this is the best choice.
4420 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4422 // Memmove with size zero? Just return the original chain.
4423 if (ConstantSize->isNullValue())
4427 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4428 ConstantSize->getZExtValue(), Align, isVol,
4429 false, DstPtrInfo, SrcPtrInfo);
4430 if (Result.getNode())
4434 // Then check to see if we should lower the memmove with target-specific
4435 // code. If the target chooses to do this, this is the next best.
4437 SDValue Result = TSI->EmitTargetCodeForMemmove(
4438 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4439 if (Result.getNode())
4443 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4444 // not be safe. See memcpy above for more details.
4446 // Emit a library call.
4447 TargetLowering::ArgListTy Args;
4448 TargetLowering::ArgListEntry Entry;
4449 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4450 Entry.Node = Dst; Args.push_back(Entry);
4451 Entry.Node = Src; Args.push_back(Entry);
4452 Entry.Node = Size; Args.push_back(Entry);
4453 // FIXME: pass in SDLoc
4454 TargetLowering::CallLoweringInfo CLI(*this);
4455 CLI.setDebugLoc(dl).setChain(Chain)
4456 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4457 Type::getVoidTy(*getContext()),
4458 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4459 TLI->getPointerTy()), std::move(Args), 0)
4461 .setTailCall(isTailCall);
4463 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4464 return CallResult.second;
4467 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4468 SDValue Src, SDValue Size,
4469 unsigned Align, bool isVol, bool isTailCall,
4470 MachinePointerInfo DstPtrInfo) {
4471 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4473 // Check to see if we should lower the memset to stores first.
4474 // For cases within the target-specified limits, this is the best choice.
4475 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4477 // Memset with size zero? Just return the original chain.
4478 if (ConstantSize->isNullValue())
4482 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4483 Align, isVol, DstPtrInfo);
4485 if (Result.getNode())
4489 // Then check to see if we should lower the memset with target-specific
4490 // code. If the target chooses to do this, this is the next best.
4492 SDValue Result = TSI->EmitTargetCodeForMemset(
4493 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4494 if (Result.getNode())
4498 // Emit a library call.
4499 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4500 TargetLowering::ArgListTy Args;
4501 TargetLowering::ArgListEntry Entry;
4502 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4503 Args.push_back(Entry);
4505 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4506 Args.push_back(Entry);
4508 Entry.Ty = IntPtrTy;
4509 Args.push_back(Entry);
4511 // FIXME: pass in SDLoc
4512 TargetLowering::CallLoweringInfo CLI(*this);
4513 CLI.setDebugLoc(dl).setChain(Chain)
4514 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4515 Type::getVoidTy(*getContext()),
4516 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4517 TLI->getPointerTy()), std::move(Args), 0)
4519 .setTailCall(isTailCall);
4521 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4522 return CallResult.second;
4525 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4526 SDVTList VTList, ArrayRef<SDValue> Ops,
4527 MachineMemOperand *MMO,
4528 AtomicOrdering SuccessOrdering,
4529 AtomicOrdering FailureOrdering,
4530 SynchronizationScope SynchScope) {
4531 FoldingSetNodeID ID;
4532 ID.AddInteger(MemVT.getRawBits());
4533 AddNodeIDNode(ID, Opcode, VTList, Ops);
4534 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4536 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4537 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4538 return SDValue(E, 0);
4541 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4542 // SDNode doesn't have access to it. This memory will be "leaked" when
4543 // the node is deallocated, but recovered when the allocator is released.
4544 // If the number of operands is less than 5 we use AtomicSDNode's internal
4546 unsigned NumOps = Ops.size();
4547 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4550 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4551 dl.getDebugLoc(), VTList, MemVT,
4552 Ops.data(), DynOps, NumOps, MMO,
4553 SuccessOrdering, FailureOrdering,
4555 CSEMap.InsertNode(N, IP);
4557 return SDValue(N, 0);
4560 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4561 SDVTList VTList, ArrayRef<SDValue> Ops,
4562 MachineMemOperand *MMO,
4563 AtomicOrdering Ordering,
4564 SynchronizationScope SynchScope) {
4565 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4566 Ordering, SynchScope);
4569 SDValue SelectionDAG::getAtomicCmpSwap(
4570 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4571 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4572 unsigned Alignment, AtomicOrdering SuccessOrdering,
4573 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4574 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4575 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4576 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4578 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4579 Alignment = getEVTAlignment(MemVT);
4581 MachineFunction &MF = getMachineFunction();
4583 // FIXME: Volatile isn't really correct; we should keep track of atomic
4584 // orderings in the memoperand.
4585 unsigned Flags = MachineMemOperand::MOVolatile;
4586 Flags |= MachineMemOperand::MOLoad;
4587 Flags |= MachineMemOperand::MOStore;
4589 MachineMemOperand *MMO =
4590 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4592 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4593 SuccessOrdering, FailureOrdering, SynchScope);
4596 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4597 SDVTList VTs, SDValue Chain, SDValue Ptr,
4598 SDValue Cmp, SDValue Swp,
4599 MachineMemOperand *MMO,
4600 AtomicOrdering SuccessOrdering,
4601 AtomicOrdering FailureOrdering,
4602 SynchronizationScope SynchScope) {
4603 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4604 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4605 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4607 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4608 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4609 SuccessOrdering, FailureOrdering, SynchScope);
4612 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4614 SDValue Ptr, SDValue Val,
4615 const Value* PtrVal,
4617 AtomicOrdering Ordering,
4618 SynchronizationScope SynchScope) {
4619 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4620 Alignment = getEVTAlignment(MemVT);
4622 MachineFunction &MF = getMachineFunction();
4623 // An atomic store does not load. An atomic load does not store.
4624 // (An atomicrmw obviously both loads and stores.)
4625 // For now, atomics are considered to be volatile always, and they are
4627 // FIXME: Volatile isn't really correct; we should keep track of atomic
4628 // orderings in the memoperand.
4629 unsigned Flags = MachineMemOperand::MOVolatile;
4630 if (Opcode != ISD::ATOMIC_STORE)
4631 Flags |= MachineMemOperand::MOLoad;
4632 if (Opcode != ISD::ATOMIC_LOAD)
4633 Flags |= MachineMemOperand::MOStore;
4635 MachineMemOperand *MMO =
4636 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4637 MemVT.getStoreSize(), Alignment);
4639 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4640 Ordering, SynchScope);
4643 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4645 SDValue Ptr, SDValue Val,
4646 MachineMemOperand *MMO,
4647 AtomicOrdering Ordering,
4648 SynchronizationScope SynchScope) {
4649 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4650 Opcode == ISD::ATOMIC_LOAD_SUB ||
4651 Opcode == ISD::ATOMIC_LOAD_AND ||
4652 Opcode == ISD::ATOMIC_LOAD_OR ||
4653 Opcode == ISD::ATOMIC_LOAD_XOR ||
4654 Opcode == ISD::ATOMIC_LOAD_NAND ||
4655 Opcode == ISD::ATOMIC_LOAD_MIN ||
4656 Opcode == ISD::ATOMIC_LOAD_MAX ||
4657 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4658 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4659 Opcode == ISD::ATOMIC_SWAP ||
4660 Opcode == ISD::ATOMIC_STORE) &&
4661 "Invalid Atomic Op");
4663 EVT VT = Val.getValueType();
4665 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4666 getVTList(VT, MVT::Other);
4667 SDValue Ops[] = {Chain, Ptr, Val};
4668 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4671 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4672 EVT VT, SDValue Chain,
4674 MachineMemOperand *MMO,
4675 AtomicOrdering Ordering,
4676 SynchronizationScope SynchScope) {
4677 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4679 SDVTList VTs = getVTList(VT, MVT::Other);
4680 SDValue Ops[] = {Chain, Ptr};
4681 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4684 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4685 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4686 if (Ops.size() == 1)
4689 SmallVector<EVT, 4> VTs;
4690 VTs.reserve(Ops.size());
4691 for (unsigned i = 0; i < Ops.size(); ++i)
4692 VTs.push_back(Ops[i].getValueType());
4693 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4697 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4698 ArrayRef<SDValue> Ops,
4699 EVT MemVT, MachinePointerInfo PtrInfo,
4700 unsigned Align, bool Vol,
4701 bool ReadMem, bool WriteMem, unsigned Size) {
4702 if (Align == 0) // Ensure that codegen never sees alignment 0
4703 Align = getEVTAlignment(MemVT);
4705 MachineFunction &MF = getMachineFunction();
4708 Flags |= MachineMemOperand::MOStore;
4710 Flags |= MachineMemOperand::MOLoad;
4712 Flags |= MachineMemOperand::MOVolatile;
4714 Size = MemVT.getStoreSize();
4715 MachineMemOperand *MMO =
4716 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4718 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4722 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4723 ArrayRef<SDValue> Ops, EVT MemVT,
4724 MachineMemOperand *MMO) {
4725 assert((Opcode == ISD::INTRINSIC_VOID ||
4726 Opcode == ISD::INTRINSIC_W_CHAIN ||
4727 Opcode == ISD::PREFETCH ||
4728 Opcode == ISD::LIFETIME_START ||
4729 Opcode == ISD::LIFETIME_END ||
4730 (Opcode <= INT_MAX &&
4731 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4732 "Opcode is not a memory-accessing opcode!");
4734 // Memoize the node unless it returns a flag.
4735 MemIntrinsicSDNode *N;
4736 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4737 FoldingSetNodeID ID;
4738 AddNodeIDNode(ID, Opcode, VTList, Ops);
4739 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4741 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4742 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4743 return SDValue(E, 0);
4746 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4747 dl.getDebugLoc(), VTList, Ops,
4749 CSEMap.InsertNode(N, IP);
4751 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4752 dl.getDebugLoc(), VTList, Ops,
4756 return SDValue(N, 0);
4759 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4760 /// MachinePointerInfo record from it. This is particularly useful because the
4761 /// code generator has many cases where it doesn't bother passing in a
4762 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4763 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4764 // If this is FI+Offset, we can model it.
4765 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4766 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4768 // If this is (FI+Offset1)+Offset2, we can model it.
4769 if (Ptr.getOpcode() != ISD::ADD ||
4770 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4771 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4772 return MachinePointerInfo();
4774 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4775 return MachinePointerInfo::getFixedStack(FI, Offset+
4776 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4779 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4780 /// MachinePointerInfo record from it. This is particularly useful because the
4781 /// code generator has many cases where it doesn't bother passing in a
4782 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4783 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4784 // If the 'Offset' value isn't a constant, we can't handle this.
4785 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4786 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4787 if (OffsetOp.getOpcode() == ISD::UNDEF)
4788 return InferPointerInfo(Ptr);
4789 return MachinePointerInfo();
4794 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4795 EVT VT, SDLoc dl, SDValue Chain,
4796 SDValue Ptr, SDValue Offset,
4797 MachinePointerInfo PtrInfo, EVT MemVT,
4798 bool isVolatile, bool isNonTemporal, bool isInvariant,
4799 unsigned Alignment, const AAMDNodes &AAInfo,
4800 const MDNode *Ranges) {
4801 assert(Chain.getValueType() == MVT::Other &&
4802 "Invalid chain type");
4803 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4804 Alignment = getEVTAlignment(VT);
4806 unsigned Flags = MachineMemOperand::MOLoad;
4808 Flags |= MachineMemOperand::MOVolatile;
4810 Flags |= MachineMemOperand::MONonTemporal;
4812 Flags |= MachineMemOperand::MOInvariant;
4814 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4816 if (PtrInfo.V.isNull())
4817 PtrInfo = InferPointerInfo(Ptr, Offset);
4819 MachineFunction &MF = getMachineFunction();
4820 MachineMemOperand *MMO =
4821 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4823 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4827 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4828 EVT VT, SDLoc dl, SDValue Chain,
4829 SDValue Ptr, SDValue Offset, EVT MemVT,
4830 MachineMemOperand *MMO) {
4832 ExtType = ISD::NON_EXTLOAD;
4833 } else if (ExtType == ISD::NON_EXTLOAD) {
4834 assert(VT == MemVT && "Non-extending load from different memory type!");
4837 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4838 "Should only be an extending load, not truncating!");
4839 assert(VT.isInteger() == MemVT.isInteger() &&
4840 "Cannot convert from FP to Int or Int -> FP!");
4841 assert(VT.isVector() == MemVT.isVector() &&
4842 "Cannot use an ext load to convert to or from a vector!");
4843 assert((!VT.isVector() ||
4844 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4845 "Cannot use an ext load to change the number of vector elements!");
4848 bool Indexed = AM != ISD::UNINDEXED;
4849 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4850 "Unindexed load with an offset!");
4852 SDVTList VTs = Indexed ?
4853 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4854 SDValue Ops[] = { Chain, Ptr, Offset };
4855 FoldingSetNodeID ID;
4856 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4857 ID.AddInteger(MemVT.getRawBits());
4858 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4859 MMO->isNonTemporal(),
4860 MMO->isInvariant()));
4861 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4863 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4864 cast<LoadSDNode>(E)->refineAlignment(MMO);
4865 return SDValue(E, 0);
4867 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4868 dl.getDebugLoc(), VTs, AM, ExtType,
4870 CSEMap.InsertNode(N, IP);
4872 return SDValue(N, 0);
4875 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4876 SDValue Chain, SDValue Ptr,
4877 MachinePointerInfo PtrInfo,
4878 bool isVolatile, bool isNonTemporal,
4879 bool isInvariant, unsigned Alignment,
4880 const AAMDNodes &AAInfo,
4881 const MDNode *Ranges) {
4882 SDValue Undef = getUNDEF(Ptr.getValueType());
4883 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4884 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4888 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4889 SDValue Chain, SDValue Ptr,
4890 MachineMemOperand *MMO) {
4891 SDValue Undef = getUNDEF(Ptr.getValueType());
4892 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4896 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4897 SDValue Chain, SDValue Ptr,
4898 MachinePointerInfo PtrInfo, EVT MemVT,
4899 bool isVolatile, bool isNonTemporal,
4900 bool isInvariant, unsigned Alignment,
4901 const AAMDNodes &AAInfo) {
4902 SDValue Undef = getUNDEF(Ptr.getValueType());
4903 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4904 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4909 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4910 SDValue Chain, SDValue Ptr, EVT MemVT,
4911 MachineMemOperand *MMO) {
4912 SDValue Undef = getUNDEF(Ptr.getValueType());
4913 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4918 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4919 SDValue Offset, ISD::MemIndexedMode AM) {
4920 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4921 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4922 "Load is already a indexed load!");
4923 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4924 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4925 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4926 false, LD->getAlignment());
4929 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4930 SDValue Ptr, MachinePointerInfo PtrInfo,
4931 bool isVolatile, bool isNonTemporal,
4932 unsigned Alignment, const AAMDNodes &AAInfo) {
4933 assert(Chain.getValueType() == MVT::Other &&
4934 "Invalid chain type");
4935 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4936 Alignment = getEVTAlignment(Val.getValueType());
4938 unsigned Flags = MachineMemOperand::MOStore;
4940 Flags |= MachineMemOperand::MOVolatile;
4942 Flags |= MachineMemOperand::MONonTemporal;
4944 if (PtrInfo.V.isNull())
4945 PtrInfo = InferPointerInfo(Ptr);
4947 MachineFunction &MF = getMachineFunction();
4948 MachineMemOperand *MMO =
4949 MF.getMachineMemOperand(PtrInfo, Flags,
4950 Val.getValueType().getStoreSize(), Alignment,
4953 return getStore(Chain, dl, Val, Ptr, MMO);
4956 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4957 SDValue Ptr, MachineMemOperand *MMO) {
4958 assert(Chain.getValueType() == MVT::Other &&
4959 "Invalid chain type");
4960 EVT VT = Val.getValueType();
4961 SDVTList VTs = getVTList(MVT::Other);
4962 SDValue Undef = getUNDEF(Ptr.getValueType());
4963 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4964 FoldingSetNodeID ID;
4965 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4966 ID.AddInteger(VT.getRawBits());
4967 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4968 MMO->isNonTemporal(), MMO->isInvariant()));
4969 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4971 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4972 cast<StoreSDNode>(E)->refineAlignment(MMO);
4973 return SDValue(E, 0);
4975 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4976 dl.getDebugLoc(), VTs,
4977 ISD::UNINDEXED, false, VT, MMO);
4978 CSEMap.InsertNode(N, IP);
4980 return SDValue(N, 0);
4983 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4984 SDValue Ptr, MachinePointerInfo PtrInfo,
4985 EVT SVT,bool isVolatile, bool isNonTemporal,
4987 const AAMDNodes &AAInfo) {
4988 assert(Chain.getValueType() == MVT::Other &&
4989 "Invalid chain type");
4990 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4991 Alignment = getEVTAlignment(SVT);
4993 unsigned Flags = MachineMemOperand::MOStore;
4995 Flags |= MachineMemOperand::MOVolatile;
4997 Flags |= MachineMemOperand::MONonTemporal;
4999 if (PtrInfo.V.isNull())
5000 PtrInfo = InferPointerInfo(Ptr);
5002 MachineFunction &MF = getMachineFunction();
5003 MachineMemOperand *MMO =
5004 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5007 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5010 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5011 SDValue Ptr, EVT SVT,
5012 MachineMemOperand *MMO) {
5013 EVT VT = Val.getValueType();
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5018 return getStore(Chain, dl, Val, Ptr, MMO);
5020 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5021 "Should only be a truncating store, not extending!");
5022 assert(VT.isInteger() == SVT.isInteger() &&
5023 "Can't do FP-INT conversion!");
5024 assert(VT.isVector() == SVT.isVector() &&
5025 "Cannot use trunc store to convert to or from a vector!");
5026 assert((!VT.isVector() ||
5027 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5028 "Cannot use trunc store to change the number of vector elements!");
5030 SDVTList VTs = getVTList(MVT::Other);
5031 SDValue Undef = getUNDEF(Ptr.getValueType());
5032 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5033 FoldingSetNodeID ID;
5034 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5035 ID.AddInteger(SVT.getRawBits());
5036 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5037 MMO->isNonTemporal(), MMO->isInvariant()));
5038 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5040 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5041 cast<StoreSDNode>(E)->refineAlignment(MMO);
5042 return SDValue(E, 0);
5044 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5045 dl.getDebugLoc(), VTs,
5046 ISD::UNINDEXED, true, SVT, MMO);
5047 CSEMap.InsertNode(N, IP);
5049 return SDValue(N, 0);
5053 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5054 SDValue Offset, ISD::MemIndexedMode AM) {
5055 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5056 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5057 "Store is already a indexed store!");
5058 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5059 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5060 FoldingSetNodeID ID;
5061 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5062 ID.AddInteger(ST->getMemoryVT().getRawBits());
5063 ID.AddInteger(ST->getRawSubclassData());
5064 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5066 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5067 return SDValue(E, 0);
5069 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5070 dl.getDebugLoc(), VTs, AM,
5071 ST->isTruncatingStore(),
5073 ST->getMemOperand());
5074 CSEMap.InsertNode(N, IP);
5076 return SDValue(N, 0);
5080 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5081 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5082 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5084 SDVTList VTs = getVTList(VT, MVT::Other);
5085 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5086 FoldingSetNodeID ID;
5087 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5088 ID.AddInteger(VT.getRawBits());
5089 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5091 MMO->isNonTemporal(),
5092 MMO->isInvariant()));
5093 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5095 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5096 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5097 return SDValue(E, 0);
5099 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5100 dl.getDebugLoc(), Ops, 4, VTs,
5102 CSEMap.InsertNode(N, IP);
5104 return SDValue(N, 0);
5107 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5108 SDValue Ptr, SDValue Mask, EVT MemVT,
5109 MachineMemOperand *MMO, bool isTrunc) {
5110 assert(Chain.getValueType() == MVT::Other &&
5111 "Invalid chain type");
5112 EVT VT = Val.getValueType();
5113 SDVTList VTs = getVTList(MVT::Other);
5114 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5115 FoldingSetNodeID ID;
5116 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5117 ID.AddInteger(VT.getRawBits());
5118 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5119 MMO->isNonTemporal(), MMO->isInvariant()));
5120 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5122 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5123 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5124 return SDValue(E, 0);
5126 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5127 dl.getDebugLoc(), Ops, 4,
5128 VTs, isTrunc, MemVT, MMO);
5129 CSEMap.InsertNode(N, IP);
5131 return SDValue(N, 0);
5135 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5136 ArrayRef<SDValue> Ops,
5137 MachineMemOperand *MMO) {
5139 FoldingSetNodeID ID;
5140 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5141 ID.AddInteger(VT.getRawBits());
5142 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5144 MMO->isNonTemporal(),
5145 MMO->isInvariant()));
5146 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5148 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5149 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5150 return SDValue(E, 0);
5152 MaskedGatherSDNode *N =
5153 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5155 CSEMap.InsertNode(N, IP);
5157 return SDValue(N, 0);
5160 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5161 ArrayRef<SDValue> Ops,
5162 MachineMemOperand *MMO) {
5163 FoldingSetNodeID ID;
5164 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5165 ID.AddInteger(VT.getRawBits());
5166 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5167 MMO->isNonTemporal(),
5168 MMO->isInvariant()));
5169 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5171 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5172 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5173 return SDValue(E, 0);
5176 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5178 CSEMap.InsertNode(N, IP);
5180 return SDValue(N, 0);
5183 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5184 SDValue Chain, SDValue Ptr,
5187 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5188 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5191 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5192 ArrayRef<SDUse> Ops) {
5193 switch (Ops.size()) {
5194 case 0: return getNode(Opcode, DL, VT);
5195 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5196 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5197 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5201 // Copy from an SDUse array into an SDValue array for use with
5202 // the regular getNode logic.
5203 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5204 return getNode(Opcode, DL, VT, NewOps);
5207 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5208 ArrayRef<SDValue> Ops) {
5209 unsigned NumOps = Ops.size();
5211 case 0: return getNode(Opcode, DL, VT);
5212 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5213 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5214 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5220 case ISD::SELECT_CC: {
5221 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5222 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5223 "LHS and RHS of condition must have same type!");
5224 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5225 "True and False arms of SelectCC must have same type!");
5226 assert(Ops[2].getValueType() == VT &&
5227 "select_cc node must be of same type as true and false value!");
5231 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5232 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5233 "LHS/RHS of comparison should match types!");
5240 SDVTList VTs = getVTList(VT);
5242 if (VT != MVT::Glue) {
5243 FoldingSetNodeID ID;
5244 AddNodeIDNode(ID, Opcode, VTs, Ops);
5247 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5248 return SDValue(E, 0);
5250 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5252 CSEMap.InsertNode(N, IP);
5254 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5259 return SDValue(N, 0);
5262 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5263 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5264 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5267 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5268 ArrayRef<SDValue> Ops) {
5269 if (VTList.NumVTs == 1)
5270 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5274 // FIXME: figure out how to safely handle things like
5275 // int foo(int x) { return 1 << (x & 255); }
5276 // int bar() { return foo(256); }
5277 case ISD::SRA_PARTS:
5278 case ISD::SRL_PARTS:
5279 case ISD::SHL_PARTS:
5280 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5281 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5282 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5283 else if (N3.getOpcode() == ISD::AND)
5284 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5285 // If the and is only masking out bits that cannot effect the shift,
5286 // eliminate the and.
5287 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5288 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5289 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5295 // Memoize the node unless it returns a flag.
5297 unsigned NumOps = Ops.size();
5298 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5299 FoldingSetNodeID ID;
5300 AddNodeIDNode(ID, Opcode, VTList, Ops);
5302 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5303 return SDValue(E, 0);
5306 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5307 DL.getDebugLoc(), VTList, Ops[0]);
5308 } else if (NumOps == 2) {
5309 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5310 DL.getDebugLoc(), VTList, Ops[0],
5312 } else if (NumOps == 3) {
5313 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5314 DL.getDebugLoc(), VTList, Ops[0],
5317 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5320 CSEMap.InsertNode(N, IP);
5323 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5324 DL.getDebugLoc(), VTList, Ops[0]);
5325 } else if (NumOps == 2) {
5326 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5327 DL.getDebugLoc(), VTList, Ops[0],
5329 } else if (NumOps == 3) {
5330 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5331 DL.getDebugLoc(), VTList, Ops[0],
5334 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5339 return SDValue(N, 0);
5342 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5343 return getNode(Opcode, DL, VTList, None);
5346 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5348 SDValue Ops[] = { N1 };
5349 return getNode(Opcode, DL, VTList, Ops);
5352 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5353 SDValue N1, SDValue N2) {
5354 SDValue Ops[] = { N1, N2 };
5355 return getNode(Opcode, DL, VTList, Ops);
5358 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5359 SDValue N1, SDValue N2, SDValue N3) {
5360 SDValue Ops[] = { N1, N2, N3 };
5361 return getNode(Opcode, DL, VTList, Ops);
5364 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5365 SDValue N1, SDValue N2, SDValue N3,
5367 SDValue Ops[] = { N1, N2, N3, N4 };
5368 return getNode(Opcode, DL, VTList, Ops);
5371 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5372 SDValue N1, SDValue N2, SDValue N3,
5373 SDValue N4, SDValue N5) {
5374 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5375 return getNode(Opcode, DL, VTList, Ops);
5378 SDVTList SelectionDAG::getVTList(EVT VT) {
5379 return makeVTList(SDNode::getValueTypeList(VT), 1);
5382 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5383 FoldingSetNodeID ID;
5385 ID.AddInteger(VT1.getRawBits());
5386 ID.AddInteger(VT2.getRawBits());
5389 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5391 EVT *Array = Allocator.Allocate<EVT>(2);
5394 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5395 VTListMap.InsertNode(Result, IP);
5397 return Result->getSDVTList();
5400 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5401 FoldingSetNodeID ID;
5403 ID.AddInteger(VT1.getRawBits());
5404 ID.AddInteger(VT2.getRawBits());
5405 ID.AddInteger(VT3.getRawBits());
5408 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5410 EVT *Array = Allocator.Allocate<EVT>(3);
5414 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5415 VTListMap.InsertNode(Result, IP);
5417 return Result->getSDVTList();
5420 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5421 FoldingSetNodeID ID;
5423 ID.AddInteger(VT1.getRawBits());
5424 ID.AddInteger(VT2.getRawBits());
5425 ID.AddInteger(VT3.getRawBits());
5426 ID.AddInteger(VT4.getRawBits());
5429 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5431 EVT *Array = Allocator.Allocate<EVT>(4);
5436 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5437 VTListMap.InsertNode(Result, IP);
5439 return Result->getSDVTList();
5442 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5443 unsigned NumVTs = VTs.size();
5444 FoldingSetNodeID ID;
5445 ID.AddInteger(NumVTs);
5446 for (unsigned index = 0; index < NumVTs; index++) {
5447 ID.AddInteger(VTs[index].getRawBits());
5451 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5453 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5454 std::copy(VTs.begin(), VTs.end(), Array);
5455 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5456 VTListMap.InsertNode(Result, IP);
5458 return Result->getSDVTList();
5462 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5463 /// specified operands. If the resultant node already exists in the DAG,
5464 /// this does not modify the specified node, instead it returns the node that
5465 /// already exists. If the resultant node does not exist in the DAG, the
5466 /// input node is returned. As a degenerate case, if you specify the same
5467 /// input operands as the node already has, the input node is returned.
5468 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5469 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5471 // Check to see if there is no change.
5472 if (Op == N->getOperand(0)) return N;
5474 // See if the modified node already exists.
5475 void *InsertPos = nullptr;
5476 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, 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 N->OperandList[0].set(Op);
5487 // If this gets put into a CSE map, add it.
5488 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5492 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5493 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5495 // Check to see if there is no change.
5496 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5497 return N; // No operands changed, just return the input node.
5499 // See if the modified node already exists.
5500 void *InsertPos = nullptr;
5501 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5504 // Nope it doesn't. Remove the node from its current place in the maps.
5506 if (!RemoveNodeFromCSEMaps(N))
5507 InsertPos = nullptr;
5509 // Now we update the operands.
5510 if (N->OperandList[0] != Op1)
5511 N->OperandList[0].set(Op1);
5512 if (N->OperandList[1] != Op2)
5513 N->OperandList[1].set(Op2);
5515 // If this gets put into a CSE map, add it.
5516 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5520 SDNode *SelectionDAG::
5521 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5522 SDValue Ops[] = { Op1, Op2, Op3 };
5523 return UpdateNodeOperands(N, Ops);
5526 SDNode *SelectionDAG::
5527 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5528 SDValue Op3, SDValue Op4) {
5529 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5530 return UpdateNodeOperands(N, Ops);
5533 SDNode *SelectionDAG::
5534 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5535 SDValue Op3, SDValue Op4, SDValue Op5) {
5536 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5537 return UpdateNodeOperands(N, Ops);
5540 SDNode *SelectionDAG::
5541 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5542 unsigned NumOps = Ops.size();
5543 assert(N->getNumOperands() == NumOps &&
5544 "Update with wrong number of operands");
5546 // If no operands changed just return the input node.
5547 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5550 // See if the modified node already exists.
5551 void *InsertPos = nullptr;
5552 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5555 // Nope it doesn't. Remove the node from its current place in the maps.
5557 if (!RemoveNodeFromCSEMaps(N))
5558 InsertPos = nullptr;
5560 // Now we update the operands.
5561 for (unsigned i = 0; i != NumOps; ++i)
5562 if (N->OperandList[i] != Ops[i])
5563 N->OperandList[i].set(Ops[i]);
5565 // If this gets put into a CSE map, add it.
5566 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5570 /// DropOperands - Release the operands and set this node to have
5572 void SDNode::DropOperands() {
5573 // Unlike the code in MorphNodeTo that does this, we don't need to
5574 // watch for dead nodes here.
5575 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5581 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5584 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5586 SDVTList VTs = getVTList(VT);
5587 return SelectNodeTo(N, MachineOpc, VTs, None);
5590 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5591 EVT VT, SDValue Op1) {
5592 SDVTList VTs = getVTList(VT);
5593 SDValue Ops[] = { Op1 };
5594 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5597 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5598 EVT VT, SDValue Op1,
5600 SDVTList VTs = getVTList(VT);
5601 SDValue Ops[] = { Op1, Op2 };
5602 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5605 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5606 EVT VT, SDValue Op1,
5607 SDValue Op2, SDValue Op3) {
5608 SDVTList VTs = getVTList(VT);
5609 SDValue Ops[] = { Op1, Op2, Op3 };
5610 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5613 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5614 EVT VT, ArrayRef<SDValue> Ops) {
5615 SDVTList VTs = getVTList(VT);
5616 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5619 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5620 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5621 SDVTList VTs = getVTList(VT1, VT2);
5622 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5625 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5627 SDVTList VTs = getVTList(VT1, VT2);
5628 return SelectNodeTo(N, MachineOpc, VTs, None);
5631 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5632 EVT VT1, EVT VT2, EVT VT3,
5633 ArrayRef<SDValue> Ops) {
5634 SDVTList VTs = getVTList(VT1, VT2, VT3);
5635 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5638 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5639 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5640 ArrayRef<SDValue> Ops) {
5641 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5642 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5645 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5648 SDVTList VTs = getVTList(VT1, VT2);
5649 SDValue Ops[] = { Op1 };
5650 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5653 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5655 SDValue Op1, SDValue Op2) {
5656 SDVTList VTs = getVTList(VT1, VT2);
5657 SDValue Ops[] = { Op1, Op2 };
5658 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5661 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5663 SDValue Op1, SDValue Op2,
5665 SDVTList VTs = getVTList(VT1, VT2);
5666 SDValue Ops[] = { Op1, Op2, Op3 };
5667 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5670 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5671 EVT VT1, EVT VT2, EVT VT3,
5672 SDValue Op1, SDValue Op2,
5674 SDVTList VTs = getVTList(VT1, VT2, VT3);
5675 SDValue Ops[] = { Op1, Op2, Op3 };
5676 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5679 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5680 SDVTList VTs,ArrayRef<SDValue> Ops) {
5681 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5682 // Reset the NodeID to -1.
5687 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5688 /// the line number information on the merged node since it is not possible to
5689 /// preserve the information that operation is associated with multiple lines.
5690 /// This will make the debugger working better at -O0, were there is a higher
5691 /// probability having other instructions associated with that line.
5693 /// For IROrder, we keep the smaller of the two
5694 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5695 DebugLoc NLoc = N->getDebugLoc();
5696 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5697 N->setDebugLoc(DebugLoc());
5699 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5700 N->setIROrder(Order);
5704 /// MorphNodeTo - This *mutates* the specified node to have the specified
5705 /// return type, opcode, and operands.
5707 /// Note that MorphNodeTo returns the resultant node. If there is already a
5708 /// node of the specified opcode and operands, it returns that node instead of
5709 /// the current one. Note that the SDLoc need not be the same.
5711 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5712 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5713 /// node, and because it doesn't require CSE recalculation for any of
5714 /// the node's users.
5716 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5717 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5718 /// the legalizer which maintain worklists that would need to be updated when
5719 /// deleting things.
5720 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5721 SDVTList VTs, ArrayRef<SDValue> Ops) {
5722 unsigned NumOps = Ops.size();
5723 // If an identical node already exists, use it.
5725 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5726 FoldingSetNodeID ID;
5727 AddNodeIDNode(ID, Opc, VTs, Ops);
5728 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5729 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5732 if (!RemoveNodeFromCSEMaps(N))
5735 // Start the morphing.
5737 N->ValueList = VTs.VTs;
5738 N->NumValues = VTs.NumVTs;
5740 // Clear the operands list, updating used nodes to remove this from their
5741 // use list. Keep track of any operands that become dead as a result.
5742 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5743 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5745 SDNode *Used = Use.getNode();
5747 if (Used->use_empty())
5748 DeadNodeSet.insert(Used);
5751 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5752 // Initialize the memory references information.
5753 MN->setMemRefs(nullptr, nullptr);
5754 // If NumOps is larger than the # of operands we can have in a
5755 // MachineSDNode, reallocate the operand list.
5756 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5757 if (MN->OperandsNeedDelete)
5758 delete[] MN->OperandList;
5759 if (NumOps > array_lengthof(MN->LocalOperands))
5760 // We're creating a final node that will live unmorphed for the
5761 // remainder of the current SelectionDAG iteration, so we can allocate
5762 // the operands directly out of a pool with no recycling metadata.
5763 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5764 Ops.data(), NumOps);
5766 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5767 MN->OperandsNeedDelete = false;
5769 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5771 // If NumOps is larger than the # of operands we currently have, reallocate
5772 // the operand list.
5773 if (NumOps > N->NumOperands) {
5774 if (N->OperandsNeedDelete)
5775 delete[] N->OperandList;
5776 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5777 N->OperandsNeedDelete = true;
5779 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5782 // Delete any nodes that are still dead after adding the uses for the
5784 if (!DeadNodeSet.empty()) {
5785 SmallVector<SDNode *, 16> DeadNodes;
5786 for (SDNode *N : DeadNodeSet)
5788 DeadNodes.push_back(N);
5789 RemoveDeadNodes(DeadNodes);
5793 CSEMap.InsertNode(N, IP); // Memoize the new node.
5798 /// getMachineNode - These are used for target selectors to create a new node
5799 /// with specified return type(s), MachineInstr opcode, and operands.
5801 /// Note that getMachineNode returns the resultant node. If there is already a
5802 /// node of the specified opcode and operands, it returns that node instead of
5803 /// the current one.
5805 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5806 SDVTList VTs = getVTList(VT);
5807 return getMachineNode(Opcode, dl, VTs, None);
5811 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5812 SDVTList VTs = getVTList(VT);
5813 SDValue Ops[] = { Op1 };
5814 return getMachineNode(Opcode, dl, VTs, Ops);
5818 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5819 SDValue Op1, SDValue Op2) {
5820 SDVTList VTs = getVTList(VT);
5821 SDValue Ops[] = { Op1, Op2 };
5822 return getMachineNode(Opcode, dl, VTs, Ops);
5826 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5827 SDValue Op1, SDValue Op2, SDValue Op3) {
5828 SDVTList VTs = getVTList(VT);
5829 SDValue Ops[] = { Op1, Op2, Op3 };
5830 return getMachineNode(Opcode, dl, VTs, Ops);
5834 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5835 ArrayRef<SDValue> Ops) {
5836 SDVTList VTs = getVTList(VT);
5837 return getMachineNode(Opcode, dl, VTs, Ops);
5841 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5842 SDVTList VTs = getVTList(VT1, VT2);
5843 return getMachineNode(Opcode, dl, VTs, None);
5847 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5848 EVT VT1, EVT VT2, SDValue Op1) {
5849 SDVTList VTs = getVTList(VT1, VT2);
5850 SDValue Ops[] = { Op1 };
5851 return getMachineNode(Opcode, dl, VTs, Ops);
5855 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5856 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5857 SDVTList VTs = getVTList(VT1, VT2);
5858 SDValue Ops[] = { Op1, Op2 };
5859 return getMachineNode(Opcode, dl, VTs, Ops);
5863 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5864 EVT VT1, EVT VT2, SDValue Op1,
5865 SDValue Op2, SDValue Op3) {
5866 SDVTList VTs = getVTList(VT1, VT2);
5867 SDValue Ops[] = { Op1, Op2, Op3 };
5868 return getMachineNode(Opcode, dl, VTs, Ops);
5872 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5874 ArrayRef<SDValue> Ops) {
5875 SDVTList VTs = getVTList(VT1, VT2);
5876 return getMachineNode(Opcode, dl, VTs, Ops);
5880 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5881 EVT VT1, EVT VT2, EVT VT3,
5882 SDValue Op1, SDValue Op2) {
5883 SDVTList VTs = getVTList(VT1, VT2, VT3);
5884 SDValue Ops[] = { Op1, Op2 };
5885 return getMachineNode(Opcode, dl, VTs, Ops);
5889 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5890 EVT VT1, EVT VT2, EVT VT3,
5891 SDValue Op1, SDValue Op2, SDValue Op3) {
5892 SDVTList VTs = getVTList(VT1, VT2, VT3);
5893 SDValue Ops[] = { Op1, Op2, Op3 };
5894 return getMachineNode(Opcode, dl, VTs, Ops);
5898 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5899 EVT VT1, EVT VT2, EVT VT3,
5900 ArrayRef<SDValue> Ops) {
5901 SDVTList VTs = getVTList(VT1, VT2, VT3);
5902 return getMachineNode(Opcode, dl, VTs, Ops);
5906 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5907 EVT VT2, EVT VT3, EVT VT4,
5908 ArrayRef<SDValue> Ops) {
5909 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5910 return getMachineNode(Opcode, dl, VTs, Ops);
5914 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5915 ArrayRef<EVT> ResultTys,
5916 ArrayRef<SDValue> Ops) {
5917 SDVTList VTs = getVTList(ResultTys);
5918 return getMachineNode(Opcode, dl, VTs, Ops);
5922 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5923 ArrayRef<SDValue> OpsArray) {
5924 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5927 const SDValue *Ops = OpsArray.data();
5928 unsigned NumOps = OpsArray.size();
5931 FoldingSetNodeID ID;
5932 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5934 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5935 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5939 // Allocate a new MachineSDNode.
5940 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5941 DL.getDebugLoc(), VTs);
5943 // Initialize the operands list.
5944 if (NumOps > array_lengthof(N->LocalOperands))
5945 // We're creating a final node that will live unmorphed for the
5946 // remainder of the current SelectionDAG iteration, so we can allocate
5947 // the operands directly out of a pool with no recycling metadata.
5948 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5951 N->InitOperands(N->LocalOperands, Ops, NumOps);
5952 N->OperandsNeedDelete = false;
5955 CSEMap.InsertNode(N, IP);
5961 /// getTargetExtractSubreg - A convenience function for creating
5962 /// TargetOpcode::EXTRACT_SUBREG nodes.
5964 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5966 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5967 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5968 VT, Operand, SRIdxVal);
5969 return SDValue(Subreg, 0);
5972 /// getTargetInsertSubreg - A convenience function for creating
5973 /// TargetOpcode::INSERT_SUBREG nodes.
5975 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5976 SDValue Operand, SDValue Subreg) {
5977 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5978 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5979 VT, Operand, Subreg, SRIdxVal);
5980 return SDValue(Result, 0);
5983 /// getNodeIfExists - Get the specified node if it's already available, or
5984 /// else return NULL.
5985 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5986 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5988 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5989 FoldingSetNodeID ID;
5990 AddNodeIDNode(ID, Opcode, VTList, Ops);
5991 if (isBinOpWithFlags(Opcode))
5992 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5994 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
6000 /// getDbgValue - Creates a SDDbgValue node.
6003 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6004 unsigned R, bool IsIndirect, uint64_t Off,
6005 DebugLoc DL, unsigned O) {
6006 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6007 "Expected inlined-at fields to agree");
6008 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6012 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6013 const Value *C, uint64_t Off,
6014 DebugLoc DL, unsigned O) {
6015 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6016 "Expected inlined-at fields to agree");
6017 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6021 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6022 unsigned FI, uint64_t Off,
6023 DebugLoc DL, unsigned O) {
6024 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6025 "Expected inlined-at fields to agree");
6026 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6031 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6032 /// pointed to by a use iterator is deleted, increment the use iterator
6033 /// so that it doesn't dangle.
6035 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6036 SDNode::use_iterator &UI;
6037 SDNode::use_iterator &UE;
6039 void NodeDeleted(SDNode *N, SDNode *E) override {
6040 // Increment the iterator as needed.
6041 while (UI != UE && N == *UI)
6046 RAUWUpdateListener(SelectionDAG &d,
6047 SDNode::use_iterator &ui,
6048 SDNode::use_iterator &ue)
6049 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6054 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6055 /// This can cause recursive merging of nodes in the DAG.
6057 /// This version assumes From has a single result value.
6059 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6060 SDNode *From = FromN.getNode();
6061 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6062 "Cannot replace with this method!");
6063 assert(From != To.getNode() && "Cannot replace uses of with self");
6065 // Iterate over all the existing uses of From. New uses will be added
6066 // to the beginning of the use list, which we avoid visiting.
6067 // This specifically avoids visiting uses of From that arise while the
6068 // replacement is happening, because any such uses would be the result
6069 // of CSE: If an existing node looks like From after one of its operands
6070 // is replaced by To, we don't want to replace of all its users with To
6071 // too. See PR3018 for more info.
6072 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6073 RAUWUpdateListener Listener(*this, UI, UE);
6077 // This node is about to morph, remove its old self from the CSE maps.
6078 RemoveNodeFromCSEMaps(User);
6080 // A user can appear in a use list multiple times, and when this
6081 // happens the uses are usually next to each other in the list.
6082 // To help reduce the number of CSE recomputations, process all
6083 // the uses of this user that we can find this way.
6085 SDUse &Use = UI.getUse();
6088 } while (UI != UE && *UI == User);
6090 // Now that we have modified User, add it back to the CSE maps. If it
6091 // already exists there, recursively merge the results together.
6092 AddModifiedNodeToCSEMaps(User);
6095 // If we just RAUW'd the root, take note.
6096 if (FromN == getRoot())
6100 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6101 /// This can cause recursive merging of nodes in the DAG.
6103 /// This version assumes that for each value of From, there is a
6104 /// corresponding value in To in the same position with the same type.
6106 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6108 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6109 assert((!From->hasAnyUseOfValue(i) ||
6110 From->getValueType(i) == To->getValueType(i)) &&
6111 "Cannot use this version of ReplaceAllUsesWith!");
6114 // Handle the trivial case.
6118 // Iterate over just the existing users of From. See the comments in
6119 // the ReplaceAllUsesWith above.
6120 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6121 RAUWUpdateListener Listener(*this, UI, UE);
6125 // This node is about to morph, remove its old self from the CSE maps.
6126 RemoveNodeFromCSEMaps(User);
6128 // A user can appear in a use list multiple times, and when this
6129 // happens the uses are usually next to each other in the list.
6130 // To help reduce the number of CSE recomputations, process all
6131 // the uses of this user that we can find this way.
6133 SDUse &Use = UI.getUse();
6136 } while (UI != UE && *UI == User);
6138 // Now that we have modified User, add it back to the CSE maps. If it
6139 // already exists there, recursively merge the results together.
6140 AddModifiedNodeToCSEMaps(User);
6143 // If we just RAUW'd the root, take note.
6144 if (From == getRoot().getNode())
6145 setRoot(SDValue(To, getRoot().getResNo()));
6148 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6149 /// This can cause recursive merging of nodes in the DAG.
6151 /// This version can replace From with any result values. To must match the
6152 /// number and types of values returned by From.
6153 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6154 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6155 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6157 // Iterate over just the existing users of From. See the comments in
6158 // the ReplaceAllUsesWith above.
6159 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6160 RAUWUpdateListener Listener(*this, UI, UE);
6164 // This node is about to morph, remove its old self from the CSE maps.
6165 RemoveNodeFromCSEMaps(User);
6167 // A user can appear in a use list multiple times, and when this
6168 // happens the uses are usually next to each other in the list.
6169 // To help reduce the number of CSE recomputations, process all
6170 // the uses of this user that we can find this way.
6172 SDUse &Use = UI.getUse();
6173 const SDValue &ToOp = To[Use.getResNo()];
6176 } while (UI != UE && *UI == User);
6178 // Now that we have modified User, add it back to the CSE maps. If it
6179 // already exists there, recursively merge the results together.
6180 AddModifiedNodeToCSEMaps(User);
6183 // If we just RAUW'd the root, take note.
6184 if (From == getRoot().getNode())
6185 setRoot(SDValue(To[getRoot().getResNo()]));
6188 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6189 /// uses of other values produced by From.getNode() alone. The Deleted
6190 /// vector is handled the same way as for ReplaceAllUsesWith.
6191 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6192 // Handle the really simple, really trivial case efficiently.
6193 if (From == To) return;
6195 // Handle the simple, trivial, case efficiently.
6196 if (From.getNode()->getNumValues() == 1) {
6197 ReplaceAllUsesWith(From, To);
6201 // Iterate over just the existing users of From. See the comments in
6202 // the ReplaceAllUsesWith above.
6203 SDNode::use_iterator UI = From.getNode()->use_begin(),
6204 UE = From.getNode()->use_end();
6205 RAUWUpdateListener Listener(*this, UI, UE);
6208 bool UserRemovedFromCSEMaps = false;
6210 // A user can appear in a use list multiple times, and when this
6211 // happens the uses are usually next to each other in the list.
6212 // To help reduce the number of CSE recomputations, process all
6213 // the uses of this user that we can find this way.
6215 SDUse &Use = UI.getUse();
6217 // Skip uses of different values from the same node.
6218 if (Use.getResNo() != From.getResNo()) {
6223 // If this node hasn't been modified yet, it's still in the CSE maps,
6224 // so remove its old self from the CSE maps.
6225 if (!UserRemovedFromCSEMaps) {
6226 RemoveNodeFromCSEMaps(User);
6227 UserRemovedFromCSEMaps = true;
6232 } while (UI != UE && *UI == User);
6234 // We are iterating over all uses of the From node, so if a use
6235 // doesn't use the specific value, no changes are made.
6236 if (!UserRemovedFromCSEMaps)
6239 // Now that we have modified User, add it back to the CSE maps. If it
6240 // already exists there, recursively merge the results together.
6241 AddModifiedNodeToCSEMaps(User);
6244 // If we just RAUW'd the root, take note.
6245 if (From == getRoot())
6250 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6251 /// to record information about a use.
6258 /// operator< - Sort Memos by User.
6259 bool operator<(const UseMemo &L, const UseMemo &R) {
6260 return (intptr_t)L.User < (intptr_t)R.User;
6264 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6265 /// uses of other values produced by From.getNode() alone. The same value
6266 /// may appear in both the From and To list. The Deleted vector is
6267 /// handled the same way as for ReplaceAllUsesWith.
6268 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6271 // Handle the simple, trivial case efficiently.
6273 return ReplaceAllUsesOfValueWith(*From, *To);
6275 // Read up all the uses and make records of them. This helps
6276 // processing new uses that are introduced during the
6277 // replacement process.
6278 SmallVector<UseMemo, 4> Uses;
6279 for (unsigned i = 0; i != Num; ++i) {
6280 unsigned FromResNo = From[i].getResNo();
6281 SDNode *FromNode = From[i].getNode();
6282 for (SDNode::use_iterator UI = FromNode->use_begin(),
6283 E = FromNode->use_end(); UI != E; ++UI) {
6284 SDUse &Use = UI.getUse();
6285 if (Use.getResNo() == FromResNo) {
6286 UseMemo Memo = { *UI, i, &Use };
6287 Uses.push_back(Memo);
6292 // Sort the uses, so that all the uses from a given User are together.
6293 std::sort(Uses.begin(), Uses.end());
6295 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6296 UseIndex != UseIndexEnd; ) {
6297 // We know that this user uses some value of From. If it is the right
6298 // value, update it.
6299 SDNode *User = Uses[UseIndex].User;
6301 // This node is about to morph, remove its old self from the CSE maps.
6302 RemoveNodeFromCSEMaps(User);
6304 // The Uses array is sorted, so all the uses for a given User
6305 // are next to each other in the list.
6306 // To help reduce the number of CSE recomputations, process all
6307 // the uses of this user that we can find this way.
6309 unsigned i = Uses[UseIndex].Index;
6310 SDUse &Use = *Uses[UseIndex].Use;
6314 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6316 // Now that we have modified User, add it back to the CSE maps. If it
6317 // already exists there, recursively merge the results together.
6318 AddModifiedNodeToCSEMaps(User);
6322 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6323 /// based on their topological order. It returns the maximum id and a vector
6324 /// of the SDNodes* in assigned order by reference.
6325 unsigned SelectionDAG::AssignTopologicalOrder() {
6327 unsigned DAGSize = 0;
6329 // SortedPos tracks the progress of the algorithm. Nodes before it are
6330 // sorted, nodes after it are unsorted. When the algorithm completes
6331 // it is at the end of the list.
6332 allnodes_iterator SortedPos = allnodes_begin();
6334 // Visit all the nodes. Move nodes with no operands to the front of
6335 // the list immediately. Annotate nodes that do have operands with their
6336 // operand count. Before we do this, the Node Id fields of the nodes
6337 // may contain arbitrary values. After, the Node Id fields for nodes
6338 // before SortedPos will contain the topological sort index, and the
6339 // Node Id fields for nodes At SortedPos and after will contain the
6340 // count of outstanding operands.
6341 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6343 checkForCycles(N, this);
6344 unsigned Degree = N->getNumOperands();
6346 // A node with no uses, add it to the result array immediately.
6347 N->setNodeId(DAGSize++);
6348 allnodes_iterator Q = N;
6350 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6351 assert(SortedPos != AllNodes.end() && "Overran node list");
6354 // Temporarily use the Node Id as scratch space for the degree count.
6355 N->setNodeId(Degree);
6359 // Visit all the nodes. As we iterate, move nodes into sorted order,
6360 // such that by the time the end is reached all nodes will be sorted.
6361 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6363 checkForCycles(N, this);
6364 // N is in sorted position, so all its uses have one less operand
6365 // that needs to be sorted.
6366 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6369 unsigned Degree = P->getNodeId();
6370 assert(Degree != 0 && "Invalid node degree");
6373 // All of P's operands are sorted, so P may sorted now.
6374 P->setNodeId(DAGSize++);
6376 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6377 assert(SortedPos != AllNodes.end() && "Overran node list");
6380 // Update P's outstanding operand count.
6381 P->setNodeId(Degree);
6384 if (I == SortedPos) {
6387 dbgs() << "Overran sorted position:\n";
6388 S->dumprFull(this); dbgs() << "\n";
6389 dbgs() << "Checking if this is due to cycles\n";
6390 checkForCycles(this, true);
6392 llvm_unreachable(nullptr);
6396 assert(SortedPos == AllNodes.end() &&
6397 "Topological sort incomplete!");
6398 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6399 "First node in topological sort is not the entry token!");
6400 assert(AllNodes.front().getNodeId() == 0 &&
6401 "First node in topological sort has non-zero id!");
6402 assert(AllNodes.front().getNumOperands() == 0 &&
6403 "First node in topological sort has operands!");
6404 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6405 "Last node in topologic sort has unexpected id!");
6406 assert(AllNodes.back().use_empty() &&
6407 "Last node in topologic sort has users!");
6408 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6412 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6413 /// value is produced by SD.
6414 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6416 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6417 SD->setHasDebugValue(true);
6419 DbgInfo->add(DB, SD, isParameter);
6422 /// TransferDbgValues - Transfer SDDbgValues.
6423 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6424 if (From == To || !From.getNode()->getHasDebugValue())
6426 SDNode *FromNode = From.getNode();
6427 SDNode *ToNode = To.getNode();
6428 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6429 SmallVector<SDDbgValue *, 2> ClonedDVs;
6430 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6432 SDDbgValue *Dbg = *I;
6433 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6435 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6436 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6437 Dbg->getDebugLoc(), Dbg->getOrder());
6438 ClonedDVs.push_back(Clone);
6441 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6442 E = ClonedDVs.end(); I != E; ++I)
6443 AddDbgValue(*I, ToNode, false);
6446 //===----------------------------------------------------------------------===//
6448 //===----------------------------------------------------------------------===//
6450 HandleSDNode::~HandleSDNode() {
6454 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6455 DebugLoc DL, const GlobalValue *GA,
6456 EVT VT, int64_t o, unsigned char TF)
6457 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6461 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6462 SDValue X, unsigned SrcAS,
6464 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6465 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6467 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6468 EVT memvt, MachineMemOperand *mmo)
6469 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6470 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6471 MMO->isNonTemporal(), MMO->isInvariant());
6472 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6473 assert(isNonTemporal() == MMO->isNonTemporal() &&
6474 "Non-temporal encoding error!");
6475 // We check here that the size of the memory operand fits within the size of
6476 // the MMO. This is because the MMO might indicate only a possible address
6477 // range instead of specifying the affected memory addresses precisely.
6478 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6481 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6482 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6483 : SDNode(Opc, Order, dl, VTs, Ops),
6484 MemoryVT(memvt), MMO(mmo) {
6485 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6486 MMO->isNonTemporal(), MMO->isInvariant());
6487 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6488 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6491 /// Profile - Gather unique data for the node.
6493 void SDNode::Profile(FoldingSetNodeID &ID) const {
6494 AddNodeIDNode(ID, this);
6499 std::vector<EVT> VTs;
6502 VTs.reserve(MVT::LAST_VALUETYPE);
6503 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6504 VTs.push_back(MVT((MVT::SimpleValueType)i));
6509 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6510 static ManagedStatic<EVTArray> SimpleVTArray;
6511 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6513 /// getValueTypeList - Return a pointer to the specified value type.
6515 const EVT *SDNode::getValueTypeList(EVT VT) {
6516 if (VT.isExtended()) {
6517 sys::SmartScopedLock<true> Lock(*VTMutex);
6518 return &(*EVTs->insert(VT).first);
6520 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6521 "Value type out of range!");
6522 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6526 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6527 /// indicated value. This method ignores uses of other values defined by this
6529 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6530 assert(Value < getNumValues() && "Bad value!");
6532 // TODO: Only iterate over uses of a given value of the node
6533 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6534 if (UI.getUse().getResNo() == Value) {
6541 // Found exactly the right number of uses?
6546 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6547 /// value. This method ignores uses of other values defined by this operation.
6548 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6549 assert(Value < getNumValues() && "Bad value!");
6551 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6552 if (UI.getUse().getResNo() == Value)
6559 /// isOnlyUserOf - Return true if this node is the only use of N.
6561 bool SDNode::isOnlyUserOf(SDNode *N) const {
6563 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6574 /// isOperand - Return true if this node is an operand of N.
6576 bool SDValue::isOperandOf(SDNode *N) const {
6577 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6578 if (*this == N->getOperand(i))
6583 bool SDNode::isOperandOf(SDNode *N) const {
6584 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6585 if (this == N->OperandList[i].getNode())
6590 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6591 /// be a chain) reaches the specified operand without crossing any
6592 /// side-effecting instructions on any chain path. In practice, this looks
6593 /// through token factors and non-volatile loads. In order to remain efficient,
6594 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6595 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6596 unsigned Depth) const {
6597 if (*this == Dest) return true;
6599 // Don't search too deeply, we just want to be able to see through
6600 // TokenFactor's etc.
6601 if (Depth == 0) return false;
6603 // If this is a token factor, all inputs to the TF happen in parallel. If any
6604 // of the operands of the TF does not reach dest, then we cannot do the xform.
6605 if (getOpcode() == ISD::TokenFactor) {
6606 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6607 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6612 // Loads don't have side effects, look through them.
6613 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6614 if (!Ld->isVolatile())
6615 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6620 /// hasPredecessor - Return true if N is a predecessor of this node.
6621 /// N is either an operand of this node, or can be reached by recursively
6622 /// traversing up the operands.
6623 /// NOTE: This is an expensive method. Use it carefully.
6624 bool SDNode::hasPredecessor(const SDNode *N) const {
6625 SmallPtrSet<const SDNode *, 32> Visited;
6626 SmallVector<const SDNode *, 16> Worklist;
6627 return hasPredecessorHelper(N, Visited, Worklist);
6631 SDNode::hasPredecessorHelper(const SDNode *N,
6632 SmallPtrSetImpl<const SDNode *> &Visited,
6633 SmallVectorImpl<const SDNode *> &Worklist) const {
6634 if (Visited.empty()) {
6635 Worklist.push_back(this);
6637 // Take a look in the visited set. If we've already encountered this node
6638 // we needn't search further.
6639 if (Visited.count(N))
6643 // Haven't visited N yet. Continue the search.
6644 while (!Worklist.empty()) {
6645 const SDNode *M = Worklist.pop_back_val();
6646 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6647 SDNode *Op = M->getOperand(i).getNode();
6648 if (Visited.insert(Op).second)
6649 Worklist.push_back(Op);
6658 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6659 assert(Num < NumOperands && "Invalid child # of SDNode!");
6660 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6663 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6664 assert(N->getNumValues() == 1 &&
6665 "Can't unroll a vector with multiple results!");
6667 EVT VT = N->getValueType(0);
6668 unsigned NE = VT.getVectorNumElements();
6669 EVT EltVT = VT.getVectorElementType();
6672 SmallVector<SDValue, 8> Scalars;
6673 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6675 // If ResNE is 0, fully unroll the vector op.
6678 else if (NE > ResNE)
6682 for (i= 0; i != NE; ++i) {
6683 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6684 SDValue Operand = N->getOperand(j);
6685 EVT OperandVT = Operand.getValueType();
6686 if (OperandVT.isVector()) {
6687 // A vector operand; extract a single element.
6688 EVT OperandEltVT = OperandVT.getVectorElementType();
6689 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6692 getConstant(i, dl, TLI->getVectorIdxTy()));
6694 // A scalar operand; just use it as is.
6695 Operands[j] = Operand;
6699 switch (N->getOpcode()) {
6701 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6704 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6711 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6712 getShiftAmountOperand(Operands[0].getValueType(),
6715 case ISD::SIGN_EXTEND_INREG:
6716 case ISD::FP_ROUND_INREG: {
6717 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6718 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6720 getValueType(ExtVT)));
6725 for (; i < ResNE; ++i)
6726 Scalars.push_back(getUNDEF(EltVT));
6728 return getNode(ISD::BUILD_VECTOR, dl,
6729 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6733 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6734 /// location that is 'Dist' units away from the location that the 'Base' load
6735 /// is loading from.
6736 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6737 unsigned Bytes, int Dist) const {
6738 if (LD->getChain() != Base->getChain())
6740 EVT VT = LD->getValueType(0);
6741 if (VT.getSizeInBits() / 8 != Bytes)
6744 SDValue Loc = LD->getOperand(1);
6745 SDValue BaseLoc = Base->getOperand(1);
6746 if (Loc.getOpcode() == ISD::FrameIndex) {
6747 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6749 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6750 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6751 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6752 int FS = MFI->getObjectSize(FI);
6753 int BFS = MFI->getObjectSize(BFI);
6754 if (FS != BFS || FS != (int)Bytes) return false;
6755 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6759 if (isBaseWithConstantOffset(Loc)) {
6760 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6761 if (Loc.getOperand(0) == BaseLoc) {
6762 // If the base location is a simple address with no offset itself, then
6763 // the second load's first add operand should be the base address.
6764 if (LocOffset == Dist * (int)Bytes)
6766 } else if (isBaseWithConstantOffset(BaseLoc)) {
6767 // The base location itself has an offset, so subtract that value from the
6768 // second load's offset before comparing to distance * size.
6770 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6771 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6772 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6777 const GlobalValue *GV1 = nullptr;
6778 const GlobalValue *GV2 = nullptr;
6779 int64_t Offset1 = 0;
6780 int64_t Offset2 = 0;
6781 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6782 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6783 if (isGA1 && isGA2 && GV1 == GV2)
6784 return Offset1 == (Offset2 + Dist*Bytes);
6789 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6790 /// it cannot be inferred.
6791 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6792 // If this is a GlobalAddress + cst, return the alignment.
6793 const GlobalValue *GV;
6794 int64_t GVOffset = 0;
6795 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6796 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6797 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6798 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6799 *TLI->getDataLayout());
6800 unsigned AlignBits = KnownZero.countTrailingOnes();
6801 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6803 return MinAlign(Align, GVOffset);
6806 // If this is a direct reference to a stack slot, use information about the
6807 // stack slot's alignment.
6808 int FrameIdx = 1 << 31;
6809 int64_t FrameOffset = 0;
6810 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6811 FrameIdx = FI->getIndex();
6812 } else if (isBaseWithConstantOffset(Ptr) &&
6813 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6815 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6816 FrameOffset = Ptr.getConstantOperandVal(1);
6819 if (FrameIdx != (1 << 31)) {
6820 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6821 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6829 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6830 /// which is split (or expanded) into two not necessarily identical pieces.
6831 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6832 // Currently all types are split in half.
6834 if (!VT.isVector()) {
6835 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6837 unsigned NumElements = VT.getVectorNumElements();
6838 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6839 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6842 return std::make_pair(LoVT, HiVT);
6845 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6847 std::pair<SDValue, SDValue>
6848 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6850 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6851 N.getValueType().getVectorNumElements() &&
6852 "More vector elements requested than available!");
6854 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6855 getConstant(0, DL, TLI->getVectorIdxTy()));
6856 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6857 getConstant(LoVT.getVectorNumElements(), DL,
6858 TLI->getVectorIdxTy()));
6859 return std::make_pair(Lo, Hi);
6862 void SelectionDAG::ExtractVectorElements(SDValue Op,
6863 SmallVectorImpl<SDValue> &Args,
6864 unsigned Start, unsigned Count) {
6865 EVT VT = Op.getValueType();
6867 Count = VT.getVectorNumElements();
6869 EVT EltVT = VT.getVectorElementType();
6870 EVT IdxTy = TLI->getVectorIdxTy();
6872 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6873 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6874 Op, getConstant(i, SL, IdxTy)));
6878 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6879 unsigned GlobalAddressSDNode::getAddressSpace() const {
6880 return getGlobal()->getType()->getAddressSpace();
6884 Type *ConstantPoolSDNode::getType() const {
6885 if (isMachineConstantPoolEntry())
6886 return Val.MachineCPVal->getType();
6887 return Val.ConstVal->getType();
6890 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6892 unsigned &SplatBitSize,
6894 unsigned MinSplatBits,
6895 bool isBigEndian) const {
6896 EVT VT = getValueType(0);
6897 assert(VT.isVector() && "Expected a vector type");
6898 unsigned sz = VT.getSizeInBits();
6899 if (MinSplatBits > sz)
6902 SplatValue = APInt(sz, 0);
6903 SplatUndef = APInt(sz, 0);
6905 // Get the bits. Bits with undefined values (when the corresponding element
6906 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6907 // in SplatValue. If any of the values are not constant, give up and return
6909 unsigned int nOps = getNumOperands();
6910 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6911 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6913 for (unsigned j = 0; j < nOps; ++j) {
6914 unsigned i = isBigEndian ? nOps-1-j : j;
6915 SDValue OpVal = getOperand(i);
6916 unsigned BitPos = j * EltBitSize;
6918 if (OpVal.getOpcode() == ISD::UNDEF)
6919 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6920 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6921 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6922 zextOrTrunc(sz) << BitPos;
6923 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6924 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6929 // The build_vector is all constants or undefs. Find the smallest element
6930 // size that splats the vector.
6932 HasAnyUndefs = (SplatUndef != 0);
6935 unsigned HalfSize = sz / 2;
6936 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6937 APInt LowValue = SplatValue.trunc(HalfSize);
6938 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6939 APInt LowUndef = SplatUndef.trunc(HalfSize);
6941 // If the two halves do not match (ignoring undef bits), stop here.
6942 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6943 MinSplatBits > HalfSize)
6946 SplatValue = HighValue | LowValue;
6947 SplatUndef = HighUndef & LowUndef;
6956 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6957 if (UndefElements) {
6958 UndefElements->clear();
6959 UndefElements->resize(getNumOperands());
6962 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6963 SDValue Op = getOperand(i);
6964 if (Op.getOpcode() == ISD::UNDEF) {
6966 (*UndefElements)[i] = true;
6967 } else if (!Splatted) {
6969 } else if (Splatted != Op) {
6975 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6976 "Can only have a splat without a constant for all undefs.");
6977 return getOperand(0);
6984 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6985 return dyn_cast_or_null<ConstantSDNode>(
6986 getSplatValue(UndefElements).getNode());
6990 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6991 return dyn_cast_or_null<ConstantFPSDNode>(
6992 getSplatValue(UndefElements).getNode());
6995 bool BuildVectorSDNode::isConstant() const {
6996 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6997 unsigned Opc = getOperand(i).getOpcode();
6998 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7004 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7005 // Find the first non-undef value in the shuffle mask.
7007 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7010 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7012 // Make sure all remaining elements are either undef or the same as the first
7014 for (int Idx = Mask[i]; i != e; ++i)
7015 if (Mask[i] >= 0 && Mask[i] != Idx)
7021 static void checkForCyclesHelper(const SDNode *N,
7022 SmallPtrSetImpl<const SDNode*> &Visited,
7023 SmallPtrSetImpl<const SDNode*> &Checked,
7024 const llvm::SelectionDAG *DAG) {
7025 // If this node has already been checked, don't check it again.
7026 if (Checked.count(N))
7029 // If a node has already been visited on this depth-first walk, reject it as
7031 if (!Visited.insert(N).second) {
7032 errs() << "Detected cycle in SelectionDAG\n";
7033 dbgs() << "Offending node:\n";
7034 N->dumprFull(DAG); dbgs() << "\n";
7038 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7039 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7046 void llvm::checkForCycles(const llvm::SDNode *N,
7047 const llvm::SelectionDAG *DAG,
7055 assert(N && "Checking nonexistent SDNode");
7056 SmallPtrSet<const SDNode*, 32> visited;
7057 SmallPtrSet<const SDNode*, 32> checked;
7058 checkForCyclesHelper(N, visited, checked, DAG);
7063 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7064 checkForCycles(DAG->getRoot().getNode(), DAG, force);