1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
206 SDValue Op = N->getOperand(i);
207 if (Op.getOpcode() == ISD::UNDEF)
209 if (!isa<ConstantFPSDNode>(Op))
215 /// isScalarToVector - Return true if the specified node is a
216 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
217 /// element is not an undef.
218 bool ISD::isScalarToVector(const SDNode *N) {
219 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
222 if (N->getOpcode() != ISD::BUILD_VECTOR)
224 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226 unsigned NumElems = N->getNumOperands();
229 for (unsigned i = 1; i < NumElems; ++i) {
230 SDValue V = N->getOperand(i);
231 if (V.getOpcode() != ISD::UNDEF)
237 /// allOperandsUndef - Return true if the node has at least one operand
238 /// and all operands of the specified node are ISD::UNDEF.
239 bool ISD::allOperandsUndef(const SDNode *N) {
240 // Return false if the node has no operands.
241 // This is "logically inconsistent" with the definition of "all" but
242 // is probably the desired behavior.
243 if (N->getNumOperands() == 0)
246 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
247 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
253 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
256 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258 return ISD::SIGN_EXTEND;
260 return ISD::ZERO_EXTEND;
265 llvm_unreachable("Invalid LoadExtType");
268 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
269 /// when given the operation for (X op Y).
270 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
271 // To perform this operation, we just need to swap the L and G bits of the
273 unsigned OldL = (Operation >> 2) & 1;
274 unsigned OldG = (Operation >> 1) & 1;
275 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
276 (OldL << 1) | // New G bit
277 (OldG << 2)); // New L bit.
280 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
281 /// 'op' is a valid SetCC operation.
282 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
283 unsigned Operation = Op;
285 Operation ^= 7; // Flip L, G, E bits, but not U.
287 Operation ^= 15; // Flip all of the condition bits.
289 if (Operation > ISD::SETTRUE2)
290 Operation &= ~8; // Don't let N and U bits get set.
292 return ISD::CondCode(Operation);
296 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
297 /// signed operation and 2 if the result is an unsigned comparison. Return zero
298 /// if the operation does not depend on the sign of the input (setne and seteq).
299 static int isSignedOp(ISD::CondCode Opcode) {
301 default: llvm_unreachable("Illegal integer setcc operation!");
303 case ISD::SETNE: return 0;
307 case ISD::SETGE: return 1;
311 case ISD::SETUGE: return 2;
315 /// getSetCCOrOperation - Return the result of a logical OR between different
316 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
317 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
322 // Cannot fold a signed integer setcc with an unsigned integer setcc.
323 return ISD::SETCC_INVALID;
325 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
327 // If the N and U bits get set then the resultant comparison DOES suddenly
328 // care about orderedness, and is true when ordered.
329 if (Op > ISD::SETTRUE2)
330 Op &= ~16; // Clear the U bit if the N bit is set.
332 // Canonicalize illegal integer setcc's.
333 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
336 return ISD::CondCode(Op);
339 /// getSetCCAndOperation - Return the result of a logical AND between different
340 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
341 /// function returns zero if it is not possible to represent the resultant
343 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
346 // Cannot fold a signed setcc with an unsigned setcc.
347 return ISD::SETCC_INVALID;
349 // Combine all of the condition bits.
350 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352 // Canonicalize illegal integer setcc's.
356 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
357 case ISD::SETOEQ: // SETEQ & SETU[LG]E
358 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
359 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
360 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
367 //===----------------------------------------------------------------------===//
368 // SDNode Profile Support
369 //===----------------------------------------------------------------------===//
371 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
377 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
378 /// solely with their pointer.
379 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
380 ID.AddPointer(VTList.VTs);
383 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 static void AddNodeIDOperands(FoldingSetNodeID &ID,
386 ArrayRef<SDValue> Ops) {
387 for (auto& Op : Ops) {
388 ID.AddPointer(Op.getNode());
389 ID.AddInteger(Op.getResNo());
393 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 static void AddNodeIDOperands(FoldingSetNodeID &ID,
396 ArrayRef<SDUse> Ops) {
397 for (auto& Op : Ops) {
398 ID.AddPointer(Op.getNode());
399 ID.AddInteger(Op.getResNo());
403 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
407 ID.AddBoolean(exact);
410 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
411 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
412 bool nuw, bool nsw, bool exact) {
413 if (isBinOpWithFlags(Opcode))
414 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
417 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
418 SDVTList VTList, ArrayRef<SDValue> OpList) {
419 AddNodeIDOpcode(ID, OpC);
420 AddNodeIDValueTypes(ID, VTList);
421 AddNodeIDOperands(ID, OpList);
424 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
426 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
427 switch (N->getOpcode()) {
428 case ISD::TargetExternalSymbol:
429 case ISD::ExternalSymbol:
430 llvm_unreachable("Should only be used on nodes with operands");
431 default: break; // Normal nodes don't need extra info.
432 case ISD::TargetConstant:
433 case ISD::Constant: {
434 const ConstantSDNode *C = cast<ConstantSDNode>(N);
435 ID.AddPointer(C->getConstantIntValue());
436 ID.AddBoolean(C->isOpaque());
439 case ISD::TargetConstantFP:
440 case ISD::ConstantFP: {
441 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
444 case ISD::TargetGlobalAddress:
445 case ISD::GlobalAddress:
446 case ISD::TargetGlobalTLSAddress:
447 case ISD::GlobalTLSAddress: {
448 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
449 ID.AddPointer(GA->getGlobal());
450 ID.AddInteger(GA->getOffset());
451 ID.AddInteger(GA->getTargetFlags());
452 ID.AddInteger(GA->getAddressSpace());
455 case ISD::BasicBlock:
456 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
459 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
461 case ISD::RegisterMask:
462 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
465 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
467 case ISD::FrameIndex:
468 case ISD::TargetFrameIndex:
469 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
472 case ISD::TargetJumpTable:
473 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
474 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
476 case ISD::ConstantPool:
477 case ISD::TargetConstantPool: {
478 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
479 ID.AddInteger(CP->getAlignment());
480 ID.AddInteger(CP->getOffset());
481 if (CP->isMachineConstantPoolEntry())
482 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
484 ID.AddPointer(CP->getConstVal());
485 ID.AddInteger(CP->getTargetFlags());
488 case ISD::TargetIndex: {
489 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
490 ID.AddInteger(TI->getIndex());
491 ID.AddInteger(TI->getOffset());
492 ID.AddInteger(TI->getTargetFlags());
496 const LoadSDNode *LD = cast<LoadSDNode>(N);
497 ID.AddInteger(LD->getMemoryVT().getRawBits());
498 ID.AddInteger(LD->getRawSubclassData());
499 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
503 const StoreSDNode *ST = cast<StoreSDNode>(N);
504 ID.AddInteger(ST->getMemoryVT().getRawBits());
505 ID.AddInteger(ST->getRawSubclassData());
506 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
517 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
518 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
519 BinNode->hasNoSignedWrap(), BinNode->isExact());
522 case ISD::ATOMIC_CMP_SWAP:
523 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
524 case ISD::ATOMIC_SWAP:
525 case ISD::ATOMIC_LOAD_ADD:
526 case ISD::ATOMIC_LOAD_SUB:
527 case ISD::ATOMIC_LOAD_AND:
528 case ISD::ATOMIC_LOAD_OR:
529 case ISD::ATOMIC_LOAD_XOR:
530 case ISD::ATOMIC_LOAD_NAND:
531 case ISD::ATOMIC_LOAD_MIN:
532 case ISD::ATOMIC_LOAD_MAX:
533 case ISD::ATOMIC_LOAD_UMIN:
534 case ISD::ATOMIC_LOAD_UMAX:
535 case ISD::ATOMIC_LOAD:
536 case ISD::ATOMIC_STORE: {
537 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
538 ID.AddInteger(AT->getMemoryVT().getRawBits());
539 ID.AddInteger(AT->getRawSubclassData());
540 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
543 case ISD::PREFETCH: {
544 const MemSDNode *PF = cast<MemSDNode>(N);
545 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
548 case ISD::VECTOR_SHUFFLE: {
549 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
550 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
552 ID.AddInteger(SVN->getMaskElt(i));
555 case ISD::TargetBlockAddress:
556 case ISD::BlockAddress: {
557 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
558 ID.AddPointer(BA->getBlockAddress());
559 ID.AddInteger(BA->getOffset());
560 ID.AddInteger(BA->getTargetFlags());
563 } // end switch (N->getOpcode())
565 // Target specific memory nodes could also have address spaces to check.
566 if (N->isTargetMemoryOpcode())
567 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
570 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
572 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
573 AddNodeIDOpcode(ID, N->getOpcode());
574 // Add the return value info.
575 AddNodeIDValueTypes(ID, N->getVTList());
576 // Add the operand info.
577 AddNodeIDOperands(ID, N->ops());
579 // Handle SDNode leafs with special info.
580 AddNodeIDCustom(ID, N);
583 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
584 /// the CSE map that carries volatility, temporalness, indexing mode, and
585 /// extension/truncation information.
587 static inline unsigned
588 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
589 bool isNonTemporal, bool isInvariant) {
590 assert((ConvType & 3) == ConvType &&
591 "ConvType may not require more than 2 bits!");
592 assert((AM & 7) == AM &&
593 "AM may not require more than 3 bits!");
597 (isNonTemporal << 6) |
601 //===----------------------------------------------------------------------===//
602 // SelectionDAG Class
603 //===----------------------------------------------------------------------===//
605 /// doNotCSE - Return true if CSE should not be performed for this node.
606 static bool doNotCSE(SDNode *N) {
607 if (N->getValueType(0) == MVT::Glue)
608 return true; // Never CSE anything that produces a flag.
610 switch (N->getOpcode()) {
612 case ISD::HANDLENODE:
614 return true; // Never CSE these nodes.
617 // Check that remaining values produced are not flags.
618 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
619 if (N->getValueType(i) == MVT::Glue)
620 return true; // Never CSE anything that produces a flag.
625 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
627 void SelectionDAG::RemoveDeadNodes() {
628 // Create a dummy node (which is not added to allnodes), that adds a reference
629 // to the root node, preventing it from being deleted.
630 HandleSDNode Dummy(getRoot());
632 SmallVector<SDNode*, 128> DeadNodes;
634 // Add all obviously-dead nodes to the DeadNodes worklist.
635 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
637 DeadNodes.push_back(I);
639 RemoveDeadNodes(DeadNodes);
641 // If the root changed (e.g. it was a dead load, update the root).
642 setRoot(Dummy.getValue());
645 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
646 /// given list, and any nodes that become unreachable as a result.
647 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
649 // Process the worklist, deleting the nodes and adding their uses to the
651 while (!DeadNodes.empty()) {
652 SDNode *N = DeadNodes.pop_back_val();
654 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
655 DUL->NodeDeleted(N, nullptr);
657 // Take the node out of the appropriate CSE map.
658 RemoveNodeFromCSEMaps(N);
660 // Next, brutally remove the operand list. This is safe to do, as there are
661 // no cycles in the graph.
662 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
664 SDNode *Operand = Use.getNode();
667 // Now that we removed this operand, see if there are no uses of it left.
668 if (Operand->use_empty())
669 DeadNodes.push_back(Operand);
676 void SelectionDAG::RemoveDeadNode(SDNode *N){
677 SmallVector<SDNode*, 16> DeadNodes(1, N);
679 // Create a dummy node that adds a reference to the root node, preventing
680 // it from being deleted. (This matters if the root is an operand of the
682 HandleSDNode Dummy(getRoot());
684 RemoveDeadNodes(DeadNodes);
687 void SelectionDAG::DeleteNode(SDNode *N) {
688 // First take this out of the appropriate CSE map.
689 RemoveNodeFromCSEMaps(N);
691 // Finally, remove uses due to operands of this node, remove from the
692 // AllNodes list, and delete the node.
693 DeleteNodeNotInCSEMaps(N);
696 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
697 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
698 assert(N->use_empty() && "Cannot delete a node that is not dead!");
700 // Drop all of the operands and decrement used node's use counts.
706 void SDDbgInfo::erase(const SDNode *Node) {
707 DbgValMapType::iterator I = DbgValMap.find(Node);
708 if (I == DbgValMap.end())
710 for (auto &Val: I->second)
711 Val->setIsInvalidated();
715 void SelectionDAG::DeallocateNode(SDNode *N) {
716 if (N->OperandsNeedDelete)
717 delete[] N->OperandList;
719 // Set the opcode to DELETED_NODE to help catch bugs when node
720 // memory is reallocated.
721 N->NodeType = ISD::DELETED_NODE;
723 NodeAllocator.Deallocate(AllNodes.remove(N));
725 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
726 // them and forget about that node.
731 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
732 static void VerifySDNode(SDNode *N) {
733 switch (N->getOpcode()) {
736 case ISD::BUILD_PAIR: {
737 EVT VT = N->getValueType(0);
738 assert(N->getNumValues() == 1 && "Too many results!");
739 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
740 "Wrong return type!");
741 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
742 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
743 "Mismatched operand types!");
744 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
745 "Wrong operand type!");
746 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
747 "Wrong return type size");
750 case ISD::BUILD_VECTOR: {
751 assert(N->getNumValues() == 1 && "Too many results!");
752 assert(N->getValueType(0).isVector() && "Wrong return type!");
753 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
754 "Wrong number of operands!");
755 EVT EltVT = N->getValueType(0).getVectorElementType();
756 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
757 assert((I->getValueType() == EltVT ||
758 (EltVT.isInteger() && I->getValueType().isInteger() &&
759 EltVT.bitsLE(I->getValueType()))) &&
760 "Wrong operand type!");
761 assert(I->getValueType() == N->getOperand(0).getValueType() &&
762 "Operands must all have the same type");
770 /// \brief Insert a newly allocated node into the DAG.
772 /// Handles insertion into the all nodes list and CSE map, as well as
773 /// verification and other common operations when a new node is allocated.
774 void SelectionDAG::InsertNode(SDNode *N) {
775 AllNodes.push_back(N);
781 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
782 /// correspond to it. This is useful when we're about to delete or repurpose
783 /// the node. We don't want future request for structurally identical nodes
784 /// to return N anymore.
785 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
787 switch (N->getOpcode()) {
788 case ISD::HANDLENODE: return false; // noop.
790 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
791 "Cond code doesn't exist!");
792 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
793 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
795 case ISD::ExternalSymbol:
796 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
798 case ISD::TargetExternalSymbol: {
799 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
800 Erased = TargetExternalSymbols.erase(
801 std::pair<std::string,unsigned char>(ESN->getSymbol(),
802 ESN->getTargetFlags()));
805 case ISD::VALUETYPE: {
806 EVT VT = cast<VTSDNode>(N)->getVT();
807 if (VT.isExtended()) {
808 Erased = ExtendedValueTypeNodes.erase(VT);
810 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
811 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
816 // Remove it from the CSE Map.
817 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
818 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
819 Erased = CSEMap.RemoveNode(N);
823 // Verify that the node was actually in one of the CSE maps, unless it has a
824 // flag result (which cannot be CSE'd) or is one of the special cases that are
825 // not subject to CSE.
826 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
827 !N->isMachineOpcode() && !doNotCSE(N)) {
830 llvm_unreachable("Node is not in map!");
836 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
837 /// maps and modified in place. Add it back to the CSE maps, unless an identical
838 /// node already exists, in which case transfer all its users to the existing
839 /// node. This transfer can potentially trigger recursive merging.
842 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
843 // For node types that aren't CSE'd, just act as if no identical node
846 SDNode *Existing = CSEMap.GetOrInsertNode(N);
848 // If there was already an existing matching node, use ReplaceAllUsesWith
849 // to replace the dead one with the existing one. This can cause
850 // recursive merging of other unrelated nodes down the line.
851 ReplaceAllUsesWith(N, Existing);
853 // N is now dead. Inform the listeners and delete it.
854 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
855 DUL->NodeDeleted(N, Existing);
856 DeleteNodeNotInCSEMaps(N);
861 // If the node doesn't already exist, we updated it. Inform listeners.
862 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
866 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
867 /// were replaced with those specified. If this node is never memoized,
868 /// return null, otherwise return a pointer to the slot it would take. If a
869 /// node already exists with these operands, the slot will be non-null.
870 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
875 SDValue Ops[] = { Op };
877 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
878 AddNodeIDCustom(ID, N);
879 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
883 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
884 /// were replaced with those specified. If this node is never memoized,
885 /// return null, otherwise return a pointer to the slot it would take. If a
886 /// node already exists with these operands, the slot will be non-null.
887 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
888 SDValue Op1, SDValue Op2,
893 SDValue Ops[] = { Op1, Op2 };
895 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
896 AddNodeIDCustom(ID, N);
897 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
902 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
903 /// were replaced with those specified. If this node is never memoized,
904 /// return null, otherwise return a pointer to the slot it would take. If a
905 /// node already exists with these operands, the slot will be non-null.
906 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
912 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
913 AddNodeIDCustom(ID, N);
914 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
918 /// getEVTAlignment - Compute the default alignment value for the
921 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
922 Type *Ty = VT == MVT::iPTR ?
923 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
924 VT.getTypeForEVT(*getContext());
926 return TLI->getDataLayout()->getABITypeAlignment(Ty);
929 // EntryNode could meaningfully have debug info if we can find it...
930 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
931 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
932 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
933 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
934 UpdateListeners(nullptr) {
935 AllNodes.push_back(&EntryNode);
936 DbgInfo = new SDDbgInfo();
939 void SelectionDAG::init(MachineFunction &mf) {
941 TLI = getSubtarget().getTargetLowering();
942 TSI = getSubtarget().getSelectionDAGInfo();
943 Context = &mf.getFunction()->getContext();
946 SelectionDAG::~SelectionDAG() {
947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
952 void SelectionDAG::allnodes_clear() {
953 assert(&*AllNodes.begin() == &EntryNode);
954 AllNodes.remove(AllNodes.begin());
955 while (!AllNodes.empty())
956 DeallocateNode(AllNodes.begin());
959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
960 SDVTList VTs, SDValue N1,
961 SDValue N2, bool nuw, bool nsw,
963 if (isBinOpWithFlags(Opcode)) {
964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
966 FN->setHasNoUnsignedWrap(nuw);
967 FN->setHasNoSignedWrap(nsw);
968 FN->setIsExact(exact);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 void SelectionDAG::clear() {
980 OperandAllocator.Reset();
983 ExtendedValueTypeNodes.clear();
984 ExternalSymbols.clear();
985 TargetExternalSymbols.clear();
986 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
987 static_cast<CondCodeSDNode*>(nullptr));
988 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
989 static_cast<SDNode*>(nullptr));
991 EntryNode.UseList = nullptr;
992 AllNodes.push_back(&EntryNode);
993 Root = getEntryNode();
997 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
998 return VT.bitsGT(Op.getValueType()) ?
999 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1000 getNode(ISD::TRUNCATE, DL, VT, Op);
1003 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1004 return VT.bitsGT(Op.getValueType()) ?
1005 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1006 getNode(ISD::TRUNCATE, DL, VT, Op);
1009 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1010 return VT.bitsGT(Op.getValueType()) ?
1011 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1012 getNode(ISD::TRUNCATE, DL, VT, Op);
1015 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1017 if (VT.bitsLE(Op.getValueType()))
1018 return getNode(ISD::TRUNCATE, SL, VT, Op);
1020 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1021 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1024 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1025 assert(!VT.isVector() &&
1026 "getZeroExtendInReg should use the vector element type instead of "
1027 "the vector type!");
1028 if (Op.getValueType() == VT) return Op;
1029 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1030 APInt Imm = APInt::getLowBitsSet(BitWidth,
1031 VT.getSizeInBits());
1032 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1033 getConstant(Imm, DL, Op.getValueType()));
1036 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1037 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1038 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1039 "The sizes of the input and result must match in order to perform the "
1040 "extend in-register.");
1041 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1042 "The destination vector type must have fewer lanes than the input.");
1043 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1046 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1047 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1048 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1049 "The sizes of the input and result must match in order to perform the "
1050 "extend in-register.");
1051 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1052 "The destination vector type must have fewer lanes than the input.");
1053 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1056 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1057 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1058 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1059 "The sizes of the input and result must match in order to perform the "
1060 "extend in-register.");
1061 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1062 "The destination vector type must have fewer lanes than the input.");
1063 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1066 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1068 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1069 EVT EltVT = VT.getScalarType();
1071 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1072 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1075 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1076 EVT EltVT = VT.getScalarType();
1078 switch (TLI->getBooleanContents(VT)) {
1079 case TargetLowering::ZeroOrOneBooleanContent:
1080 case TargetLowering::UndefinedBooleanContent:
1081 TrueValue = getConstant(1, DL, VT);
1083 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1084 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1088 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1091 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1093 EVT EltVT = VT.getScalarType();
1094 assert((EltVT.getSizeInBits() >= 64 ||
1095 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1096 "getConstant with a uint64_t value that doesn't fit in the type!");
1097 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1100 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1103 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1106 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1107 bool isT, bool isO) {
1108 assert(VT.isInteger() && "Cannot create FP integer constant!");
1110 EVT EltVT = VT.getScalarType();
1111 const ConstantInt *Elt = &Val;
1113 // In some cases the vector type is legal but the element type is illegal and
1114 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1115 // inserted value (the type does not need to match the vector element type).
1116 // Any extra bits introduced will be truncated away.
1117 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1118 TargetLowering::TypePromoteInteger) {
1119 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1120 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1121 Elt = ConstantInt::get(*getContext(), NewVal);
1123 // In other cases the element type is illegal and needs to be expanded, for
1124 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1125 // the value into n parts and use a vector type with n-times the elements.
1126 // Then bitcast to the type requested.
1127 // Legalizing constants too early makes the DAGCombiner's job harder so we
1128 // only legalize if the DAG tells us we must produce legal types.
1129 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1130 TLI->getTypeAction(*getContext(), EltVT) ==
1131 TargetLowering::TypeExpandInteger) {
1132 APInt NewVal = Elt->getValue();
1133 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1134 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1135 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1136 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1138 // Check the temporary vector is the correct size. If this fails then
1139 // getTypeToTransformTo() probably returned a type whose size (in bits)
1140 // isn't a power-of-2 factor of the requested type size.
1141 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1143 SmallVector<SDValue, 2> EltParts;
1144 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1145 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1146 .trunc(ViaEltSizeInBits), DL,
1147 ViaEltVT, isT, isO));
1150 // EltParts is currently in little endian order. If we actually want
1151 // big-endian order then reverse it now.
1152 if (TLI->isBigEndian())
1153 std::reverse(EltParts.begin(), EltParts.end());
1155 // The elements must be reversed when the element order is different
1156 // to the endianness of the elements (because the BITCAST is itself a
1157 // vector shuffle in this situation). However, we do not need any code to
1158 // perform this reversal because getConstant() is producing a vector
1160 // This situation occurs in MIPS MSA.
1162 SmallVector<SDValue, 8> Ops;
1163 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1164 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1166 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1167 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1172 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1173 "APInt size does not match type size!");
1174 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1175 FoldingSetNodeID ID;
1176 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1180 SDNode *N = nullptr;
1181 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1183 return SDValue(N, 0);
1186 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1188 CSEMap.InsertNode(N, IP);
1192 SDValue Result(N, 0);
1193 if (VT.isVector()) {
1194 SmallVector<SDValue, 8> Ops;
1195 Ops.assign(VT.getVectorNumElements(), Result);
1196 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1201 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1202 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1205 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1207 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1210 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1212 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1214 EVT EltVT = VT.getScalarType();
1216 // Do the map lookup using the actual bit pattern for the floating point
1217 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1218 // we don't have issues with SNANs.
1219 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1220 FoldingSetNodeID ID;
1221 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1224 SDNode *N = nullptr;
1225 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1227 return SDValue(N, 0);
1230 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1231 CSEMap.InsertNode(N, IP);
1235 SDValue Result(N, 0);
1236 if (VT.isVector()) {
1237 SmallVector<SDValue, 8> Ops;
1238 Ops.assign(VT.getVectorNumElements(), Result);
1239 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1244 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1246 EVT EltVT = VT.getScalarType();
1247 if (EltVT==MVT::f32)
1248 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1249 else if (EltVT==MVT::f64)
1250 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1251 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1254 APFloat apf = APFloat(Val);
1255 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1257 return getConstantFP(apf, DL, VT, isTarget);
1259 llvm_unreachable("Unsupported type in getConstantFP");
1262 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1263 EVT VT, int64_t Offset,
1265 unsigned char TargetFlags) {
1266 assert((TargetFlags == 0 || isTargetGA) &&
1267 "Cannot set target flags on target-independent globals");
1269 // Truncate (with sign-extension) the offset value to the pointer size.
1270 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1272 Offset = SignExtend64(Offset, BitWidth);
1275 if (GV->isThreadLocal())
1276 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1278 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1283 ID.AddInteger(Offset);
1284 ID.AddInteger(TargetFlags);
1285 ID.AddInteger(GV->getType()->getAddressSpace());
1287 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1288 return SDValue(E, 0);
1290 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1291 DL.getDebugLoc(), GV, VT,
1292 Offset, TargetFlags);
1293 CSEMap.InsertNode(N, IP);
1295 return SDValue(N, 0);
1298 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1299 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1300 FoldingSetNodeID ID;
1301 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1304 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1305 return SDValue(E, 0);
1307 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1308 CSEMap.InsertNode(N, IP);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1314 unsigned char TargetFlags) {
1315 assert((TargetFlags == 0 || isTarget) &&
1316 "Cannot set target flags on target-independent jump tables");
1317 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1318 FoldingSetNodeID ID;
1319 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1321 ID.AddInteger(TargetFlags);
1323 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1328 CSEMap.InsertNode(N, IP);
1330 return SDValue(N, 0);
1333 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1334 unsigned Alignment, int Offset,
1336 unsigned char TargetFlags) {
1337 assert((TargetFlags == 0 || isTarget) &&
1338 "Cannot set target flags on target-independent globals");
1340 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1341 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1342 FoldingSetNodeID ID;
1343 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1344 ID.AddInteger(Alignment);
1345 ID.AddInteger(Offset);
1347 ID.AddInteger(TargetFlags);
1349 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1350 return SDValue(E, 0);
1352 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1353 Alignment, TargetFlags);
1354 CSEMap.InsertNode(N, IP);
1356 return SDValue(N, 0);
1360 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1361 unsigned Alignment, int Offset,
1363 unsigned char TargetFlags) {
1364 assert((TargetFlags == 0 || isTarget) &&
1365 "Cannot set target flags on target-independent globals");
1367 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1368 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1369 FoldingSetNodeID ID;
1370 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1371 ID.AddInteger(Alignment);
1372 ID.AddInteger(Offset);
1373 C->addSelectionDAGCSEId(ID);
1374 ID.AddInteger(TargetFlags);
1376 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1377 return SDValue(E, 0);
1379 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1380 Alignment, TargetFlags);
1381 CSEMap.InsertNode(N, IP);
1383 return SDValue(N, 0);
1386 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1387 unsigned char TargetFlags) {
1388 FoldingSetNodeID ID;
1389 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1390 ID.AddInteger(Index);
1391 ID.AddInteger(Offset);
1392 ID.AddInteger(TargetFlags);
1394 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1395 return SDValue(E, 0);
1397 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1399 CSEMap.InsertNode(N, IP);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1409 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1410 return SDValue(E, 0);
1412 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1413 CSEMap.InsertNode(N, IP);
1415 return SDValue(N, 0);
1418 SDValue SelectionDAG::getValueType(EVT VT) {
1419 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1420 ValueTypeNodes.size())
1421 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1423 SDNode *&N = VT.isExtended() ?
1424 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1426 if (N) return SDValue(N, 0);
1427 N = new (NodeAllocator) VTSDNode(VT);
1429 return SDValue(N, 0);
1432 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1433 SDNode *&N = ExternalSymbols[Sym];
1434 if (N) return SDValue(N, 0);
1435 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1437 return SDValue(N, 0);
1440 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1441 unsigned char TargetFlags) {
1443 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1445 if (N) return SDValue(N, 0);
1446 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1448 return SDValue(N, 0);
1451 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1452 if ((unsigned)Cond >= CondCodeNodes.size())
1453 CondCodeNodes.resize(Cond+1);
1455 if (!CondCodeNodes[Cond]) {
1456 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1457 CondCodeNodes[Cond] = N;
1461 return SDValue(CondCodeNodes[Cond], 0);
1464 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1465 // the shuffle mask M that point at N1 to point at N2, and indices that point
1466 // N2 to point at N1.
1467 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1469 ShuffleVectorSDNode::commuteMask(M);
1472 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1473 SDValue N2, const int *Mask) {
1474 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1475 "Invalid VECTOR_SHUFFLE");
1477 // Canonicalize shuffle undef, undef -> undef
1478 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1479 return getUNDEF(VT);
1481 // Validate that all indices in Mask are within the range of the elements
1482 // input to the shuffle.
1483 unsigned NElts = VT.getVectorNumElements();
1484 SmallVector<int, 8> MaskVec;
1485 for (unsigned i = 0; i != NElts; ++i) {
1486 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1487 MaskVec.push_back(Mask[i]);
1490 // Canonicalize shuffle v, v -> v, undef
1493 for (unsigned i = 0; i != NElts; ++i)
1494 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1497 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1498 if (N1.getOpcode() == ISD::UNDEF)
1499 commuteShuffle(N1, N2, MaskVec);
1501 // If shuffling a splat, try to blend the splat instead. We do this here so
1502 // that even when this arises during lowering we don't have to re-handle it.
1503 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1504 BitVector UndefElements;
1505 SDValue Splat = BV->getSplatValue(&UndefElements);
1509 for (int i = 0; i < (int)NElts; ++i) {
1510 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1513 // If this input comes from undef, mark it as such.
1514 if (UndefElements[MaskVec[i] - Offset]) {
1519 // If we can blend a non-undef lane, use that instead.
1520 if (!UndefElements[i])
1521 MaskVec[i] = i + Offset;
1524 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1525 BlendSplat(N1BV, 0);
1526 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1527 BlendSplat(N2BV, NElts);
1529 // Canonicalize all index into lhs, -> shuffle lhs, undef
1530 // Canonicalize all index into rhs, -> shuffle rhs, undef
1531 bool AllLHS = true, AllRHS = true;
1532 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1533 for (unsigned i = 0; i != NElts; ++i) {
1534 if (MaskVec[i] >= (int)NElts) {
1539 } else if (MaskVec[i] >= 0) {
1543 if (AllLHS && AllRHS)
1544 return getUNDEF(VT);
1545 if (AllLHS && !N2Undef)
1549 commuteShuffle(N1, N2, MaskVec);
1551 // Reset our undef status after accounting for the mask.
1552 N2Undef = N2.getOpcode() == ISD::UNDEF;
1553 // Re-check whether both sides ended up undef.
1554 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1555 return getUNDEF(VT);
1557 // If Identity shuffle return that node.
1558 bool Identity = true, AllSame = true;
1559 for (unsigned i = 0; i != NElts; ++i) {
1560 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1561 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1563 if (Identity && NElts)
1566 // Shuffling a constant splat doesn't change the result.
1570 // Look through any bitcasts. We check that these don't change the number
1571 // (and size) of elements and just changes their types.
1572 while (V.getOpcode() == ISD::BITCAST)
1573 V = V->getOperand(0);
1575 // A splat should always show up as a build vector node.
1576 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1577 BitVector UndefElements;
1578 SDValue Splat = BV->getSplatValue(&UndefElements);
1579 // If this is a splat of an undef, shuffling it is also undef.
1580 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1581 return getUNDEF(VT);
1584 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1586 // We only have a splat which can skip shuffles if there is a splatted
1587 // value and no undef lanes rearranged by the shuffle.
1588 if (Splat && UndefElements.none()) {
1589 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1590 // number of elements match or the value splatted is a zero constant.
1593 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1594 if (C->isNullValue())
1598 // If the shuffle itself creates a splat, build the vector directly.
1599 if (AllSame && SameNumElts) {
1600 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1601 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1603 EVT BuildVT = BV->getValueType(0);
1604 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1606 // We may have jumped through bitcasts, so the type of the
1607 // BUILD_VECTOR may not match the type of the shuffle.
1609 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1615 FoldingSetNodeID ID;
1616 SDValue Ops[2] = { N1, N2 };
1617 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1618 for (unsigned i = 0; i != NElts; ++i)
1619 ID.AddInteger(MaskVec[i]);
1622 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1623 return SDValue(E, 0);
1625 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1626 // SDNode doesn't have access to it. This memory will be "leaked" when
1627 // the node is deallocated, but recovered when the NodeAllocator is released.
1628 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1629 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1631 ShuffleVectorSDNode *N =
1632 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1633 dl.getDebugLoc(), N1, N2,
1635 CSEMap.InsertNode(N, IP);
1637 return SDValue(N, 0);
1640 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1641 MVT VT = SV.getSimpleValueType(0);
1642 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1643 ShuffleVectorSDNode::commuteMask(MaskVec);
1645 SDValue Op0 = SV.getOperand(0);
1646 SDValue Op1 = SV.getOperand(1);
1647 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1650 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1651 SDValue Val, SDValue DTy,
1652 SDValue STy, SDValue Rnd, SDValue Sat,
1653 ISD::CvtCode Code) {
1654 // If the src and dest types are the same and the conversion is between
1655 // integer types of the same sign or two floats, no conversion is necessary.
1657 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1660 FoldingSetNodeID ID;
1661 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1662 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1664 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1665 return SDValue(E, 0);
1667 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1670 CSEMap.InsertNode(N, IP);
1672 return SDValue(N, 0);
1675 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1676 FoldingSetNodeID ID;
1677 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1678 ID.AddInteger(RegNo);
1680 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1681 return SDValue(E, 0);
1683 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1684 CSEMap.InsertNode(N, IP);
1686 return SDValue(N, 0);
1689 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1690 FoldingSetNodeID ID;
1691 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1692 ID.AddPointer(RegMask);
1694 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1695 return SDValue(E, 0);
1697 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1698 CSEMap.InsertNode(N, IP);
1700 return SDValue(N, 0);
1703 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1704 FoldingSetNodeID ID;
1705 SDValue Ops[] = { Root };
1706 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1707 ID.AddPointer(Label);
1709 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1710 return SDValue(E, 0);
1712 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1713 dl.getDebugLoc(), Root, Label);
1714 CSEMap.InsertNode(N, IP);
1716 return SDValue(N, 0);
1720 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1723 unsigned char TargetFlags) {
1724 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1729 ID.AddInteger(Offset);
1730 ID.AddInteger(TargetFlags);
1732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1733 return SDValue(E, 0);
1735 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1737 CSEMap.InsertNode(N, IP);
1739 return SDValue(N, 0);
1742 SDValue SelectionDAG::getSrcValue(const Value *V) {
1743 assert((!V || V->getType()->isPointerTy()) &&
1744 "SrcValue is not a pointer?");
1746 FoldingSetNodeID ID;
1747 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1751 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1752 return SDValue(E, 0);
1754 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1755 CSEMap.InsertNode(N, IP);
1757 return SDValue(N, 0);
1760 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1761 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1762 FoldingSetNodeID ID;
1763 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1767 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1768 return SDValue(E, 0);
1770 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1771 CSEMap.InsertNode(N, IP);
1773 return SDValue(N, 0);
1776 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1777 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1778 unsigned SrcAS, unsigned DestAS) {
1779 SDValue Ops[] = {Ptr};
1780 FoldingSetNodeID ID;
1781 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1782 ID.AddInteger(SrcAS);
1783 ID.AddInteger(DestAS);
1786 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1787 return SDValue(E, 0);
1789 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1791 VT, Ptr, SrcAS, DestAS);
1792 CSEMap.InsertNode(N, IP);
1794 return SDValue(N, 0);
1797 /// getShiftAmountOperand - Return the specified value casted to
1798 /// the target's desired shift amount type.
1799 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1800 EVT OpTy = Op.getValueType();
1801 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1802 if (OpTy == ShTy || OpTy.isVector()) return Op;
1804 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1805 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1808 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1809 /// specified value type.
1810 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1811 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1812 unsigned ByteSize = VT.getStoreSize();
1813 Type *Ty = VT.getTypeForEVT(*getContext());
1814 unsigned StackAlign =
1815 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1817 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1818 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1821 /// CreateStackTemporary - Create a stack temporary suitable for holding
1822 /// either of the specified value types.
1823 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1824 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1825 VT2.getStoreSizeInBits())/8;
1826 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1827 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1828 const DataLayout *TD = TLI->getDataLayout();
1829 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1830 TD->getPrefTypeAlignment(Ty2));
1832 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1833 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1834 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1837 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1838 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1839 // These setcc operations always fold.
1843 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1845 case ISD::SETTRUE2: {
1846 TargetLowering::BooleanContent Cnt =
1847 TLI->getBooleanContents(N1->getValueType(0));
1849 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1863 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1867 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1868 const APInt &C2 = N2C->getAPIntValue();
1869 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1870 const APInt &C1 = N1C->getAPIntValue();
1873 default: llvm_unreachable("Unknown integer setcc!");
1874 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1875 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1876 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1877 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1878 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1879 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1880 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1881 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1882 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1883 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1887 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1888 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1889 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1892 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1893 return getUNDEF(VT);
1895 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1896 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1897 return getUNDEF(VT);
1899 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1900 R==APFloat::cmpLessThan, dl, VT);
1901 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1902 return getUNDEF(VT);
1904 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1905 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1906 return getUNDEF(VT);
1908 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1909 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1910 return getUNDEF(VT);
1912 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1913 R==APFloat::cmpEqual, dl, VT);
1914 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1915 return getUNDEF(VT);
1917 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1918 R==APFloat::cmpEqual, dl, VT);
1919 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1920 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1921 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1922 R==APFloat::cmpEqual, dl, VT);
1923 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1924 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1925 R==APFloat::cmpLessThan, dl, VT);
1926 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1927 R==APFloat::cmpUnordered, dl, VT);
1928 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1929 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1932 // Ensure that the constant occurs on the RHS.
1933 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1934 MVT CompVT = N1.getValueType().getSimpleVT();
1935 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1938 return getSetCC(dl, VT, N2, N1, SwappedCond);
1942 // Could not fold it.
1946 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1947 /// use this predicate to simplify operations downstream.
1948 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1949 // This predicate is not safe for vector operations.
1950 if (Op.getValueType().isVector())
1953 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1954 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1957 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1958 /// this predicate to simplify operations downstream. Mask is known to be zero
1959 /// for bits that V cannot have.
1960 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1961 unsigned Depth) const {
1962 APInt KnownZero, KnownOne;
1963 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1964 return (KnownZero & Mask) == Mask;
1967 /// Determine which bits of Op are known to be either zero or one and return
1968 /// them in the KnownZero/KnownOne bitsets.
1969 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1970 APInt &KnownOne, unsigned Depth) const {
1971 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1973 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1975 return; // Limit search depth.
1977 APInt KnownZero2, KnownOne2;
1979 switch (Op.getOpcode()) {
1981 // We know all of the bits for a constant!
1982 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1983 KnownZero = ~KnownOne;
1986 // If either the LHS or the RHS are Zero, the result is zero.
1987 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1988 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1990 // Output known-1 bits are only known if set in both the LHS & RHS.
1991 KnownOne &= KnownOne2;
1992 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1993 KnownZero |= KnownZero2;
1996 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1997 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1999 // Output known-0 bits are only known if clear in both the LHS & RHS.
2000 KnownZero &= KnownZero2;
2001 // Output known-1 are known to be set if set in either the LHS | RHS.
2002 KnownOne |= KnownOne2;
2005 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2006 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2008 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2009 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2010 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2011 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2012 KnownZero = KnownZeroOut;
2016 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2017 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2019 // If low bits are zero in either operand, output low known-0 bits.
2020 // Also compute a conserative estimate for high known-0 bits.
2021 // More trickiness is possible, but this is sufficient for the
2022 // interesting case of alignment computation.
2023 KnownOne.clearAllBits();
2024 unsigned TrailZ = KnownZero.countTrailingOnes() +
2025 KnownZero2.countTrailingOnes();
2026 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2027 KnownZero2.countLeadingOnes(),
2028 BitWidth) - BitWidth;
2030 TrailZ = std::min(TrailZ, BitWidth);
2031 LeadZ = std::min(LeadZ, BitWidth);
2032 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2033 APInt::getHighBitsSet(BitWidth, LeadZ);
2037 // For the purposes of computing leading zeros we can conservatively
2038 // treat a udiv as a logical right shift by the power of 2 known to
2039 // be less than the denominator.
2040 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2041 unsigned LeadZ = KnownZero2.countLeadingOnes();
2043 KnownOne2.clearAllBits();
2044 KnownZero2.clearAllBits();
2045 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2046 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2047 if (RHSUnknownLeadingOnes != BitWidth)
2048 LeadZ = std::min(BitWidth,
2049 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2051 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2055 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2056 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2058 // Only known if known in both the LHS and RHS.
2059 KnownOne &= KnownOne2;
2060 KnownZero &= KnownZero2;
2062 case ISD::SELECT_CC:
2063 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2064 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2066 // Only known if known in both the LHS and RHS.
2067 KnownOne &= KnownOne2;
2068 KnownZero &= KnownZero2;
2076 if (Op.getResNo() != 1)
2078 // The boolean result conforms to getBooleanContents.
2079 // If we know the result of a setcc has the top bits zero, use this info.
2080 // We know that we have an integer-based boolean since these operations
2081 // are only available for integer.
2082 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2083 TargetLowering::ZeroOrOneBooleanContent &&
2085 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2088 // If we know the result of a setcc has the top bits zero, use this info.
2089 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2090 TargetLowering::ZeroOrOneBooleanContent &&
2092 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2095 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2096 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2097 unsigned ShAmt = SA->getZExtValue();
2099 // If the shift count is an invalid immediate, don't do anything.
2100 if (ShAmt >= BitWidth)
2103 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2104 KnownZero <<= ShAmt;
2106 // low bits known zero.
2107 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2111 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2112 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2113 unsigned ShAmt = SA->getZExtValue();
2115 // If the shift count is an invalid immediate, don't do anything.
2116 if (ShAmt >= BitWidth)
2119 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2120 KnownZero = KnownZero.lshr(ShAmt);
2121 KnownOne = KnownOne.lshr(ShAmt);
2123 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2124 KnownZero |= HighBits; // High bits known zero.
2128 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2129 unsigned ShAmt = SA->getZExtValue();
2131 // If the shift count is an invalid immediate, don't do anything.
2132 if (ShAmt >= BitWidth)
2135 // If any of the demanded bits are produced by the sign extension, we also
2136 // demand the input sign bit.
2137 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2139 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2140 KnownZero = KnownZero.lshr(ShAmt);
2141 KnownOne = KnownOne.lshr(ShAmt);
2143 // Handle the sign bits.
2144 APInt SignBit = APInt::getSignBit(BitWidth);
2145 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2147 if (KnownZero.intersects(SignBit)) {
2148 KnownZero |= HighBits; // New bits are known zero.
2149 } else if (KnownOne.intersects(SignBit)) {
2150 KnownOne |= HighBits; // New bits are known one.
2154 case ISD::SIGN_EXTEND_INREG: {
2155 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2156 unsigned EBits = EVT.getScalarType().getSizeInBits();
2158 // Sign extension. Compute the demanded bits in the result that are not
2159 // present in the input.
2160 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2162 APInt InSignBit = APInt::getSignBit(EBits);
2163 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2165 // If the sign extended bits are demanded, we know that the sign
2167 InSignBit = InSignBit.zext(BitWidth);
2168 if (NewBits.getBoolValue())
2169 InputDemandedBits |= InSignBit;
2171 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2172 KnownOne &= InputDemandedBits;
2173 KnownZero &= InputDemandedBits;
2175 // If the sign bit of the input is known set or clear, then we know the
2176 // top bits of the result.
2177 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2178 KnownZero |= NewBits;
2179 KnownOne &= ~NewBits;
2180 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2181 KnownOne |= NewBits;
2182 KnownZero &= ~NewBits;
2183 } else { // Input sign bit unknown
2184 KnownZero &= ~NewBits;
2185 KnownOne &= ~NewBits;
2190 case ISD::CTTZ_ZERO_UNDEF:
2192 case ISD::CTLZ_ZERO_UNDEF:
2194 unsigned LowBits = Log2_32(BitWidth)+1;
2195 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2196 KnownOne.clearAllBits();
2200 LoadSDNode *LD = cast<LoadSDNode>(Op);
2201 // If this is a ZEXTLoad and we are looking at the loaded value.
2202 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2203 EVT VT = LD->getMemoryVT();
2204 unsigned MemBits = VT.getScalarType().getSizeInBits();
2205 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2206 } else if (const MDNode *Ranges = LD->getRanges()) {
2207 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2211 case ISD::ZERO_EXTEND: {
2212 EVT InVT = Op.getOperand(0).getValueType();
2213 unsigned InBits = InVT.getScalarType().getSizeInBits();
2214 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2215 KnownZero = KnownZero.trunc(InBits);
2216 KnownOne = KnownOne.trunc(InBits);
2217 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2218 KnownZero = KnownZero.zext(BitWidth);
2219 KnownOne = KnownOne.zext(BitWidth);
2220 KnownZero |= NewBits;
2223 case ISD::SIGN_EXTEND: {
2224 EVT InVT = Op.getOperand(0).getValueType();
2225 unsigned InBits = InVT.getScalarType().getSizeInBits();
2226 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2228 KnownZero = KnownZero.trunc(InBits);
2229 KnownOne = KnownOne.trunc(InBits);
2230 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2232 // Note if the sign bit is known to be zero or one.
2233 bool SignBitKnownZero = KnownZero.isNegative();
2234 bool SignBitKnownOne = KnownOne.isNegative();
2236 KnownZero = KnownZero.zext(BitWidth);
2237 KnownOne = KnownOne.zext(BitWidth);
2239 // If the sign bit is known zero or one, the top bits match.
2240 if (SignBitKnownZero)
2241 KnownZero |= NewBits;
2242 else if (SignBitKnownOne)
2243 KnownOne |= NewBits;
2246 case ISD::ANY_EXTEND: {
2247 EVT InVT = Op.getOperand(0).getValueType();
2248 unsigned InBits = InVT.getScalarType().getSizeInBits();
2249 KnownZero = KnownZero.trunc(InBits);
2250 KnownOne = KnownOne.trunc(InBits);
2251 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2252 KnownZero = KnownZero.zext(BitWidth);
2253 KnownOne = KnownOne.zext(BitWidth);
2256 case ISD::TRUNCATE: {
2257 EVT InVT = Op.getOperand(0).getValueType();
2258 unsigned InBits = InVT.getScalarType().getSizeInBits();
2259 KnownZero = KnownZero.zext(InBits);
2260 KnownOne = KnownOne.zext(InBits);
2261 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2262 KnownZero = KnownZero.trunc(BitWidth);
2263 KnownOne = KnownOne.trunc(BitWidth);
2266 case ISD::AssertZext: {
2267 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2268 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2269 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2270 KnownZero |= (~InMask);
2271 KnownOne &= (~KnownZero);
2275 // All bits are zero except the low bit.
2276 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2280 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2281 // We know that the top bits of C-X are clear if X contains less bits
2282 // than C (i.e. no wrap-around can happen). For example, 20-X is
2283 // positive if we can prove that X is >= 0 and < 16.
2284 if (CLHS->getAPIntValue().isNonNegative()) {
2285 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2286 // NLZ can't be BitWidth with no sign bit
2287 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2288 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2290 // If all of the MaskV bits are known to be zero, then we know the
2291 // output top bits are zero, because we now know that the output is
2293 if ((KnownZero2 & MaskV) == MaskV) {
2294 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2295 // Top bits known zero.
2296 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2304 // Output known-0 bits are known if clear or set in both the low clear bits
2305 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2306 // low 3 bits clear.
2307 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2308 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2310 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2311 KnownZeroOut = std::min(KnownZeroOut,
2312 KnownZero2.countTrailingOnes());
2314 if (Op.getOpcode() == ISD::ADD) {
2315 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2319 // With ADDE, a carry bit may be added in, so we can only use this
2320 // information if we know (at least) that the low two bits are clear. We
2321 // then return to the caller that the low bit is unknown but that other bits
2323 if (KnownZeroOut >= 2) // ADDE
2324 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2328 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2329 const APInt &RA = Rem->getAPIntValue().abs();
2330 if (RA.isPowerOf2()) {
2331 APInt LowBits = RA - 1;
2332 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2334 // The low bits of the first operand are unchanged by the srem.
2335 KnownZero = KnownZero2 & LowBits;
2336 KnownOne = KnownOne2 & LowBits;
2338 // If the first operand is non-negative or has all low bits zero, then
2339 // the upper bits are all zero.
2340 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2341 KnownZero |= ~LowBits;
2343 // If the first operand is negative and not all low bits are zero, then
2344 // the upper bits are all one.
2345 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2346 KnownOne |= ~LowBits;
2347 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2352 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2353 const APInt &RA = Rem->getAPIntValue();
2354 if (RA.isPowerOf2()) {
2355 APInt LowBits = (RA - 1);
2356 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2358 // The upper bits are all zero, the lower ones are unchanged.
2359 KnownZero = KnownZero2 | ~LowBits;
2360 KnownOne = KnownOne2 & LowBits;
2365 // Since the result is less than or equal to either operand, any leading
2366 // zero bits in either operand must also exist in the result.
2367 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2368 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2370 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2371 KnownZero2.countLeadingOnes());
2372 KnownOne.clearAllBits();
2373 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2376 case ISD::EXTRACT_ELEMENT: {
2377 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2378 const unsigned Index =
2379 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2380 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2382 // Remove low part of known bits mask
2383 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2384 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2386 // Remove high part of known bit mask
2387 KnownZero = KnownZero.trunc(BitWidth);
2388 KnownOne = KnownOne.trunc(BitWidth);
2391 case ISD::FrameIndex:
2392 case ISD::TargetFrameIndex:
2393 if (unsigned Align = InferPtrAlignment(Op)) {
2394 // The low bits are known zero if the pointer is aligned.
2395 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2401 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2404 case ISD::INTRINSIC_WO_CHAIN:
2405 case ISD::INTRINSIC_W_CHAIN:
2406 case ISD::INTRINSIC_VOID:
2407 // Allow the target to implement this method for its nodes.
2408 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2412 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2415 /// ComputeNumSignBits - Return the number of times the sign bit of the
2416 /// register is replicated into the other bits. We know that at least 1 bit
2417 /// is always equal to the sign bit (itself), but other cases can give us
2418 /// information. For example, immediately after an "SRA X, 2", we know that
2419 /// the top 3 bits are all equal to each other, so we return 3.
2420 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2421 EVT VT = Op.getValueType();
2422 assert(VT.isInteger() && "Invalid VT!");
2423 unsigned VTBits = VT.getScalarType().getSizeInBits();
2425 unsigned FirstAnswer = 1;
2428 return 1; // Limit search depth.
2430 switch (Op.getOpcode()) {
2432 case ISD::AssertSext:
2433 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2434 return VTBits-Tmp+1;
2435 case ISD::AssertZext:
2436 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2439 case ISD::Constant: {
2440 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2441 return Val.getNumSignBits();
2444 case ISD::SIGN_EXTEND:
2446 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2447 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2449 case ISD::SIGN_EXTEND_INREG:
2450 // Max of the input and what this extends.
2452 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2455 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2456 return std::max(Tmp, Tmp2);
2459 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2460 // SRA X, C -> adds C sign bits.
2461 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2462 Tmp += C->getZExtValue();
2463 if (Tmp > VTBits) Tmp = VTBits;
2467 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2468 // shl destroys sign bits.
2469 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2470 if (C->getZExtValue() >= VTBits || // Bad shift.
2471 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2472 return Tmp - C->getZExtValue();
2477 case ISD::XOR: // NOT is handled here.
2478 // Logical binary ops preserve the number of sign bits at the worst.
2479 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2481 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2482 FirstAnswer = std::min(Tmp, Tmp2);
2483 // We computed what we know about the sign bits as our first
2484 // answer. Now proceed to the generic code that uses
2485 // computeKnownBits, and pick whichever answer is better.
2490 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2491 if (Tmp == 1) return 1; // Early out.
2492 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2493 return std::min(Tmp, Tmp2);
2501 if (Op.getResNo() != 1)
2503 // The boolean result conforms to getBooleanContents. Fall through.
2504 // If setcc returns 0/-1, all bits are sign bits.
2505 // We know that we have an integer-based boolean since these operations
2506 // are only available for integer.
2507 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2508 TargetLowering::ZeroOrNegativeOneBooleanContent)
2512 // If setcc returns 0/-1, all bits are sign bits.
2513 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2514 TargetLowering::ZeroOrNegativeOneBooleanContent)
2519 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2520 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2522 // Handle rotate right by N like a rotate left by 32-N.
2523 if (Op.getOpcode() == ISD::ROTR)
2524 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2526 // If we aren't rotating out all of the known-in sign bits, return the
2527 // number that are left. This handles rotl(sext(x), 1) for example.
2528 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2529 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2533 // Add can have at most one carry bit. Thus we know that the output
2534 // is, at worst, one more bit than the inputs.
2535 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2536 if (Tmp == 1) return 1; // Early out.
2538 // Special case decrementing a value (ADD X, -1):
2539 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2540 if (CRHS->isAllOnesValue()) {
2541 APInt KnownZero, KnownOne;
2542 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2544 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2546 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2549 // If we are subtracting one from a positive number, there is no carry
2550 // out of the result.
2551 if (KnownZero.isNegative())
2555 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2556 if (Tmp2 == 1) return 1;
2557 return std::min(Tmp, Tmp2)-1;
2560 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2561 if (Tmp2 == 1) return 1;
2564 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2565 if (CLHS->isNullValue()) {
2566 APInt KnownZero, KnownOne;
2567 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2568 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2570 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2573 // If the input is known to be positive (the sign bit is known clear),
2574 // the output of the NEG has the same number of sign bits as the input.
2575 if (KnownZero.isNegative())
2578 // Otherwise, we treat this like a SUB.
2581 // Sub can have at most one carry bit. Thus we know that the output
2582 // is, at worst, one more bit than the inputs.
2583 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2584 if (Tmp == 1) return 1; // Early out.
2585 return std::min(Tmp, Tmp2)-1;
2587 // FIXME: it's tricky to do anything useful for this, but it is an important
2588 // case for targets like X86.
2590 case ISD::EXTRACT_ELEMENT: {
2591 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2592 const int BitWidth = Op.getValueType().getSizeInBits();
2594 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2596 // Get reverse index (starting from 1), Op1 value indexes elements from
2597 // little end. Sign starts at big end.
2598 const int rIndex = Items - 1 -
2599 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2601 // If the sign portion ends in our element the substraction gives correct
2602 // result. Otherwise it gives either negative or > bitwidth result
2603 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2607 // If we are looking at the loaded value of the SDNode.
2608 if (Op.getResNo() == 0) {
2609 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2610 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2611 unsigned ExtType = LD->getExtensionType();
2614 case ISD::SEXTLOAD: // '17' bits known
2615 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2616 return VTBits-Tmp+1;
2617 case ISD::ZEXTLOAD: // '16' bits known
2618 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2624 // Allow the target to implement this method for its nodes.
2625 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2626 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2627 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2628 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2629 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2630 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2633 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2634 // use this information.
2635 APInt KnownZero, KnownOne;
2636 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2639 if (KnownZero.isNegative()) { // sign bit is 0
2641 } else if (KnownOne.isNegative()) { // sign bit is 1;
2648 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2649 // the number of identical bits in the top of the input value.
2651 Mask <<= Mask.getBitWidth()-VTBits;
2652 // Return # leading zeros. We use 'min' here in case Val was zero before
2653 // shifting. We don't want to return '64' as for an i32 "0".
2654 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2657 /// isBaseWithConstantOffset - Return true if the specified operand is an
2658 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2659 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2660 /// semantics as an ADD. This handles the equivalence:
2661 /// X|Cst == X+Cst iff X&Cst = 0.
2662 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2663 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2664 !isa<ConstantSDNode>(Op.getOperand(1)))
2667 if (Op.getOpcode() == ISD::OR &&
2668 !MaskedValueIsZero(Op.getOperand(0),
2669 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2676 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2677 // If we're told that NaNs won't happen, assume they won't.
2678 if (getTarget().Options.NoNaNsFPMath)
2681 // If the value is a constant, we can obviously see if it is a NaN or not.
2682 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2683 return !C->getValueAPF().isNaN();
2685 // TODO: Recognize more cases here.
2690 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2691 // If the value is a constant, we can obviously see if it is a zero or not.
2692 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2693 return !C->isZero();
2695 // TODO: Recognize more cases here.
2696 switch (Op.getOpcode()) {
2699 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2700 return !C->isNullValue();
2707 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2708 // Check the obvious case.
2709 if (A == B) return true;
2711 // For for negative and positive zero.
2712 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2713 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2714 if (CA->isZero() && CB->isZero()) return true;
2716 // Otherwise they may not be equal.
2720 /// getNode - Gets or creates the specified node.
2722 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2723 FoldingSetNodeID ID;
2724 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2726 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2727 return SDValue(E, 0);
2729 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2730 DL.getDebugLoc(), getVTList(VT));
2731 CSEMap.InsertNode(N, IP);
2734 return SDValue(N, 0);
2737 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2738 EVT VT, SDValue Operand) {
2739 // Constant fold unary operations with an integer constant operand. Even
2740 // opaque constant will be folded, because the folding of unary operations
2741 // doesn't create new constants with different values. Nevertheless, the
2742 // opaque flag is preserved during folding to prevent future folding with
2744 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2745 const APInt &Val = C->getAPIntValue();
2748 case ISD::SIGN_EXTEND:
2749 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2750 C->isTargetOpcode(), C->isOpaque());
2751 case ISD::ANY_EXTEND:
2752 case ISD::ZERO_EXTEND:
2754 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2755 C->isTargetOpcode(), C->isOpaque());
2756 case ISD::UINT_TO_FP:
2757 case ISD::SINT_TO_FP: {
2758 APFloat apf(EVTToAPFloatSemantics(VT),
2759 APInt::getNullValue(VT.getSizeInBits()));
2760 (void)apf.convertFromAPInt(Val,
2761 Opcode==ISD::SINT_TO_FP,
2762 APFloat::rmNearestTiesToEven);
2763 return getConstantFP(apf, DL, VT);
2766 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2767 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2768 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2769 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2770 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2771 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2774 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2777 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2780 case ISD::CTLZ_ZERO_UNDEF:
2781 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2784 case ISD::CTTZ_ZERO_UNDEF:
2785 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2790 // Constant fold unary operations with a floating point constant operand.
2791 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2792 APFloat V = C->getValueAPF(); // make copy
2796 return getConstantFP(V, DL, VT);
2799 return getConstantFP(V, DL, VT);
2801 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2802 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2803 return getConstantFP(V, DL, VT);
2807 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2808 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2809 return getConstantFP(V, DL, VT);
2813 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2814 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2815 return getConstantFP(V, DL, VT);
2818 case ISD::FP_EXTEND: {
2820 // This can return overflow, underflow, or inexact; we don't care.
2821 // FIXME need to be more flexible about rounding mode.
2822 (void)V.convert(EVTToAPFloatSemantics(VT),
2823 APFloat::rmNearestTiesToEven, &ignored);
2824 return getConstantFP(V, DL, VT);
2826 case ISD::FP_TO_SINT:
2827 case ISD::FP_TO_UINT: {
2830 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2831 // FIXME need to be more flexible about rounding mode.
2832 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2833 Opcode==ISD::FP_TO_SINT,
2834 APFloat::rmTowardZero, &ignored);
2835 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2837 APInt api(VT.getSizeInBits(), x);
2838 return getConstant(api, DL, VT);
2841 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2842 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2843 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2844 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2845 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2846 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2851 // Constant fold unary operations with a vector integer or float operand.
2852 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2853 if (BV->isConstant()) {
2856 // FIXME: Entirely reasonable to perform folding of other unary
2857 // operations here as the need arises.
2860 // Constant build vector truncation can be done with the original scalar
2861 // operands but with a new build vector with the truncated value type.
2862 return getNode(ISD::BUILD_VECTOR, DL, VT, BV->ops());
2868 case ISD::FP_EXTEND:
2869 case ISD::UINT_TO_FP:
2870 case ISD::SINT_TO_FP: {
2871 // Let the above scalar folding handle the folding of each element.
2872 SmallVector<SDValue, 8> Ops;
2873 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2874 SDValue OpN = BV->getOperand(i);
2875 OpN = getNode(Opcode, DL, VT.getVectorElementType(), OpN);
2876 if (OpN.getOpcode() != ISD::UNDEF &&
2877 OpN.getOpcode() != ISD::Constant &&
2878 OpN.getOpcode() != ISD::ConstantFP)
2882 if (Ops.size() == VT.getVectorNumElements())
2883 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2890 unsigned OpOpcode = Operand.getNode()->getOpcode();
2892 case ISD::TokenFactor:
2893 case ISD::MERGE_VALUES:
2894 case ISD::CONCAT_VECTORS:
2895 return Operand; // Factor, merge or concat of one node? No need.
2896 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2897 case ISD::FP_EXTEND:
2898 assert(VT.isFloatingPoint() &&
2899 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2900 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2901 assert((!VT.isVector() ||
2902 VT.getVectorNumElements() ==
2903 Operand.getValueType().getVectorNumElements()) &&
2904 "Vector element count mismatch!");
2905 if (Operand.getOpcode() == ISD::UNDEF)
2906 return getUNDEF(VT);
2908 case ISD::SIGN_EXTEND:
2909 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2910 "Invalid SIGN_EXTEND!");
2911 if (Operand.getValueType() == VT) return Operand; // noop extension
2912 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2913 "Invalid sext node, dst < src!");
2914 assert((!VT.isVector() ||
2915 VT.getVectorNumElements() ==
2916 Operand.getValueType().getVectorNumElements()) &&
2917 "Vector element count mismatch!");
2918 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2919 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2920 else if (OpOpcode == ISD::UNDEF)
2921 // sext(undef) = 0, because the top bits will all be the same.
2922 return getConstant(0, DL, VT);
2924 case ISD::ZERO_EXTEND:
2925 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2926 "Invalid ZERO_EXTEND!");
2927 if (Operand.getValueType() == VT) return Operand; // noop extension
2928 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2929 "Invalid zext node, dst < src!");
2930 assert((!VT.isVector() ||
2931 VT.getVectorNumElements() ==
2932 Operand.getValueType().getVectorNumElements()) &&
2933 "Vector element count mismatch!");
2934 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2935 return getNode(ISD::ZERO_EXTEND, DL, VT,
2936 Operand.getNode()->getOperand(0));
2937 else if (OpOpcode == ISD::UNDEF)
2938 // zext(undef) = 0, because the top bits will be zero.
2939 return getConstant(0, DL, VT);
2941 case ISD::ANY_EXTEND:
2942 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2943 "Invalid ANY_EXTEND!");
2944 if (Operand.getValueType() == VT) return Operand; // noop extension
2945 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2946 "Invalid anyext node, dst < src!");
2947 assert((!VT.isVector() ||
2948 VT.getVectorNumElements() ==
2949 Operand.getValueType().getVectorNumElements()) &&
2950 "Vector element count mismatch!");
2952 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2953 OpOpcode == ISD::ANY_EXTEND)
2954 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2955 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2956 else if (OpOpcode == ISD::UNDEF)
2957 return getUNDEF(VT);
2959 // (ext (trunx x)) -> x
2960 if (OpOpcode == ISD::TRUNCATE) {
2961 SDValue OpOp = Operand.getNode()->getOperand(0);
2962 if (OpOp.getValueType() == VT)
2967 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2968 "Invalid TRUNCATE!");
2969 if (Operand.getValueType() == VT) return Operand; // noop truncate
2970 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2971 "Invalid truncate node, src < dst!");
2972 assert((!VT.isVector() ||
2973 VT.getVectorNumElements() ==
2974 Operand.getValueType().getVectorNumElements()) &&
2975 "Vector element count mismatch!");
2976 if (OpOpcode == ISD::TRUNCATE)
2977 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2978 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2979 OpOpcode == ISD::ANY_EXTEND) {
2980 // If the source is smaller than the dest, we still need an extend.
2981 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2982 .bitsLT(VT.getScalarType()))
2983 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2984 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2985 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2986 return Operand.getNode()->getOperand(0);
2988 if (OpOpcode == ISD::UNDEF)
2989 return getUNDEF(VT);
2992 // Basic sanity checking.
2993 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2994 && "Cannot BITCAST between types of different sizes!");
2995 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2996 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2997 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2998 if (OpOpcode == ISD::UNDEF)
2999 return getUNDEF(VT);
3001 case ISD::SCALAR_TO_VECTOR:
3002 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3003 (VT.getVectorElementType() == Operand.getValueType() ||
3004 (VT.getVectorElementType().isInteger() &&
3005 Operand.getValueType().isInteger() &&
3006 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3007 "Illegal SCALAR_TO_VECTOR node!");
3008 if (OpOpcode == ISD::UNDEF)
3009 return getUNDEF(VT);
3010 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3011 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3012 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3013 Operand.getConstantOperandVal(1) == 0 &&
3014 Operand.getOperand(0).getValueType() == VT)
3015 return Operand.getOperand(0);
3018 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3019 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3020 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3021 Operand.getNode()->getOperand(0));
3022 if (OpOpcode == ISD::FNEG) // --X -> X
3023 return Operand.getNode()->getOperand(0);
3026 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3027 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3032 SDVTList VTs = getVTList(VT);
3033 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3034 FoldingSetNodeID ID;
3035 SDValue Ops[1] = { Operand };
3036 AddNodeIDNode(ID, Opcode, VTs, Ops);
3038 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3039 return SDValue(E, 0);
3041 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3042 DL.getDebugLoc(), VTs, Operand);
3043 CSEMap.InsertNode(N, IP);
3045 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3046 DL.getDebugLoc(), VTs, Operand);
3050 return SDValue(N, 0);
3053 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3054 SDNode *Cst1, SDNode *Cst2) {
3055 // If the opcode is a target-specific ISD node, there's nothing we can
3056 // do here and the operand rules may not line up with the below, so
3058 if (Opcode >= ISD::BUILTIN_OP_END)
3061 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3062 SmallVector<SDValue, 4> Outputs;
3063 EVT SVT = VT.getScalarType();
3065 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3066 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3067 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3070 if (Scalar1 && Scalar2)
3071 // Scalar instruction.
3072 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3074 // For vectors extract each constant element into Inputs so we can constant
3075 // fold them individually.
3076 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3077 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3081 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3083 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3084 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3085 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3086 if (!V1 || !V2) // Not a constant, bail.
3089 if (V1->isOpaque() || V2->isOpaque())
3092 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3093 // FIXME: This is valid and could be handled by truncating the APInts.
3094 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3097 Inputs.push_back(std::make_pair(V1, V2));
3101 // We have a number of constant values, constant fold them element by element.
3102 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3103 const APInt &C1 = Inputs[I].first->getAPIntValue();
3104 const APInt &C2 = Inputs[I].second->getAPIntValue();
3108 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3111 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3114 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3117 if (!C2.getBoolValue())
3119 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3122 if (!C2.getBoolValue())
3124 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3127 if (!C2.getBoolValue())
3129 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3132 if (!C2.getBoolValue())
3134 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3137 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3140 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3143 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3146 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3149 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3152 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3155 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3158 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3165 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3166 "Expected a scalar or vector!"));
3168 // Handle the scalar case first.
3170 return Outputs.back();
3172 // We may have a vector type but a scalar result. Create a splat.
3173 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3175 // Build a big vector out of the scalar elements we generated.
3176 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3179 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3180 SDValue N2, bool nuw, bool nsw, bool exact) {
3181 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3182 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3185 case ISD::TokenFactor:
3186 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3187 N2.getValueType() == MVT::Other && "Invalid token factor!");
3188 // Fold trivial token factors.
3189 if (N1.getOpcode() == ISD::EntryToken) return N2;
3190 if (N2.getOpcode() == ISD::EntryToken) return N1;
3191 if (N1 == N2) return N1;
3193 case ISD::CONCAT_VECTORS:
3194 // Concat of UNDEFs is UNDEF.
3195 if (N1.getOpcode() == ISD::UNDEF &&
3196 N2.getOpcode() == ISD::UNDEF)
3197 return getUNDEF(VT);
3199 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3200 // one big BUILD_VECTOR.
3201 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3202 N2.getOpcode() == ISD::BUILD_VECTOR) {
3203 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3204 N1.getNode()->op_end());
3205 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3207 // BUILD_VECTOR requires all inputs to be of the same type, find the
3208 // maximum type and extend them all.
3209 EVT SVT = VT.getScalarType();
3210 for (SDValue Op : Elts)
3211 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3212 if (SVT.bitsGT(VT.getScalarType()))
3213 for (SDValue &Op : Elts)
3214 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3215 ? getZExtOrTrunc(Op, DL, SVT)
3216 : getSExtOrTrunc(Op, DL, SVT);
3218 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3222 assert(VT.isInteger() && "This operator does not apply to FP types!");
3223 assert(N1.getValueType() == N2.getValueType() &&
3224 N1.getValueType() == VT && "Binary operator types must match!");
3225 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3226 // worth handling here.
3227 if (N2C && N2C->isNullValue())
3229 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3236 assert(VT.isInteger() && "This operator does not apply to FP types!");
3237 assert(N1.getValueType() == N2.getValueType() &&
3238 N1.getValueType() == VT && "Binary operator types must match!");
3239 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3240 // it's worth handling here.
3241 if (N2C && N2C->isNullValue())
3251 assert(VT.isInteger() && "This operator does not apply to FP types!");
3252 assert(N1.getValueType() == N2.getValueType() &&
3253 N1.getValueType() == VT && "Binary operator types must match!");
3260 if (getTarget().Options.UnsafeFPMath) {
3261 if (Opcode == ISD::FADD) {
3263 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3264 if (CFP->getValueAPF().isZero())
3267 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3268 if (CFP->getValueAPF().isZero())
3270 } else if (Opcode == ISD::FSUB) {
3272 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3273 if (CFP->getValueAPF().isZero())
3275 } else if (Opcode == ISD::FMUL) {
3276 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3279 // If the first operand isn't the constant, try the second
3281 CFP = dyn_cast<ConstantFPSDNode>(N2);
3288 return SDValue(CFP,0);
3290 if (CFP->isExactlyValue(1.0))
3295 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3296 assert(N1.getValueType() == N2.getValueType() &&
3297 N1.getValueType() == VT && "Binary operator types must match!");
3299 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3300 assert(N1.getValueType() == VT &&
3301 N1.getValueType().isFloatingPoint() &&
3302 N2.getValueType().isFloatingPoint() &&
3303 "Invalid FCOPYSIGN!");
3310 assert(VT == N1.getValueType() &&
3311 "Shift operators return type must be the same as their first arg");
3312 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3313 "Shifts only work on integers");
3314 assert((!VT.isVector() || VT == N2.getValueType()) &&
3315 "Vector shift amounts must be in the same as their first arg");
3316 // Verify that the shift amount VT is bit enough to hold valid shift
3317 // amounts. This catches things like trying to shift an i1024 value by an
3318 // i8, which is easy to fall into in generic code that uses
3319 // TLI.getShiftAmount().
3320 assert(N2.getValueType().getSizeInBits() >=
3321 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3322 "Invalid use of small shift amount with oversized value!");
3324 // Always fold shifts of i1 values so the code generator doesn't need to
3325 // handle them. Since we know the size of the shift has to be less than the
3326 // size of the value, the shift/rotate count is guaranteed to be zero.
3329 if (N2C && N2C->isNullValue())
3332 case ISD::FP_ROUND_INREG: {
3333 EVT EVT = cast<VTSDNode>(N2)->getVT();
3334 assert(VT == N1.getValueType() && "Not an inreg round!");
3335 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3336 "Cannot FP_ROUND_INREG integer types");
3337 assert(EVT.isVector() == VT.isVector() &&
3338 "FP_ROUND_INREG type should be vector iff the operand "
3340 assert((!EVT.isVector() ||
3341 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3342 "Vector element counts must match in FP_ROUND_INREG");
3343 assert(EVT.bitsLE(VT) && "Not rounding down!");
3345 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3349 assert(VT.isFloatingPoint() &&
3350 N1.getValueType().isFloatingPoint() &&
3351 VT.bitsLE(N1.getValueType()) &&
3352 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3353 if (N1.getValueType() == VT) return N1; // noop conversion.
3355 case ISD::AssertSext:
3356 case ISD::AssertZext: {
3357 EVT EVT = cast<VTSDNode>(N2)->getVT();
3358 assert(VT == N1.getValueType() && "Not an inreg extend!");
3359 assert(VT.isInteger() && EVT.isInteger() &&
3360 "Cannot *_EXTEND_INREG FP types");
3361 assert(!EVT.isVector() &&
3362 "AssertSExt/AssertZExt type should be the vector element type "
3363 "rather than the vector type!");
3364 assert(EVT.bitsLE(VT) && "Not extending!");
3365 if (VT == EVT) return N1; // noop assertion.
3368 case ISD::SIGN_EXTEND_INREG: {
3369 EVT EVT = cast<VTSDNode>(N2)->getVT();
3370 assert(VT == N1.getValueType() && "Not an inreg extend!");
3371 assert(VT.isInteger() && EVT.isInteger() &&
3372 "Cannot *_EXTEND_INREG FP types");
3373 assert(EVT.isVector() == VT.isVector() &&
3374 "SIGN_EXTEND_INREG type should be vector iff the operand "
3376 assert((!EVT.isVector() ||
3377 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3378 "Vector element counts must match in SIGN_EXTEND_INREG");
3379 assert(EVT.bitsLE(VT) && "Not extending!");
3380 if (EVT == VT) return N1; // Not actually extending
3383 APInt Val = N1C->getAPIntValue();
3384 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3385 Val <<= Val.getBitWidth()-FromBits;
3386 Val = Val.ashr(Val.getBitWidth()-FromBits);
3387 return getConstant(Val, DL, VT);
3391 case ISD::EXTRACT_VECTOR_ELT:
3392 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3393 if (N1.getOpcode() == ISD::UNDEF)
3394 return getUNDEF(VT);
3396 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3397 // expanding copies of large vectors from registers.
3399 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3400 N1.getNumOperands() > 0) {
3402 N1.getOperand(0).getValueType().getVectorNumElements();
3403 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3404 N1.getOperand(N2C->getZExtValue() / Factor),
3405 getConstant(N2C->getZExtValue() % Factor, DL,
3406 N2.getValueType()));
3409 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3410 // expanding large vector constants.
3411 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3412 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3414 if (VT != Elt.getValueType())
3415 // If the vector element type is not legal, the BUILD_VECTOR operands
3416 // are promoted and implicitly truncated, and the result implicitly
3417 // extended. Make that explicit here.
3418 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3423 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3424 // operations are lowered to scalars.
3425 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3426 // If the indices are the same, return the inserted element else
3427 // if the indices are known different, extract the element from
3428 // the original vector.
3429 SDValue N1Op2 = N1.getOperand(2);
3430 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3432 if (N1Op2C && N2C) {
3433 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3434 if (VT == N1.getOperand(1).getValueType())
3435 return N1.getOperand(1);
3437 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3440 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3444 case ISD::EXTRACT_ELEMENT:
3445 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3446 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3447 (N1.getValueType().isInteger() == VT.isInteger()) &&
3448 N1.getValueType() != VT &&
3449 "Wrong types for EXTRACT_ELEMENT!");
3451 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3452 // 64-bit integers into 32-bit parts. Instead of building the extract of
3453 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3454 if (N1.getOpcode() == ISD::BUILD_PAIR)
3455 return N1.getOperand(N2C->getZExtValue());
3457 // EXTRACT_ELEMENT of a constant int is also very common.
3458 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3459 unsigned ElementSize = VT.getSizeInBits();
3460 unsigned Shift = ElementSize * N2C->getZExtValue();
3461 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3462 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3465 case ISD::EXTRACT_SUBVECTOR: {
3467 if (VT.isSimple() && N1.getValueType().isSimple()) {
3468 assert(VT.isVector() && N1.getValueType().isVector() &&
3469 "Extract subvector VTs must be a vectors!");
3470 assert(VT.getVectorElementType() ==
3471 N1.getValueType().getVectorElementType() &&
3472 "Extract subvector VTs must have the same element type!");
3473 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3474 "Extract subvector must be from larger vector to smaller vector!");
3476 if (isa<ConstantSDNode>(Index.getNode())) {
3477 assert((VT.getVectorNumElements() +
3478 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3479 <= N1.getValueType().getVectorNumElements())
3480 && "Extract subvector overflow!");
3483 // Trivial extraction.
3484 if (VT.getSimpleVT() == N1.getSimpleValueType())
3491 // Perform trivial constant folding.
3493 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3496 // Canonicalize constant to RHS if commutative.
3497 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3498 std::swap(N1C, N2C);
3502 // Constant fold FP operations.
3503 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3504 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3505 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3507 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3508 // Canonicalize constant to RHS if commutative.
3509 std::swap(N1CFP, N2CFP);
3512 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3513 APFloat::opStatus s;
3516 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3517 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3518 return getConstantFP(V1, DL, VT);
3521 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3522 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3523 return getConstantFP(V1, DL, VT);
3526 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3527 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3528 return getConstantFP(V1, DL, VT);
3531 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3532 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3533 s!=APFloat::opDivByZero)) {
3534 return getConstantFP(V1, DL, VT);
3538 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3539 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3540 s!=APFloat::opDivByZero)) {
3541 return getConstantFP(V1, DL, VT);
3544 case ISD::FCOPYSIGN:
3546 return getConstantFP(V1, DL, VT);
3551 if (Opcode == ISD::FP_ROUND) {
3552 APFloat V = N1CFP->getValueAPF(); // make copy
3554 // This can return overflow, underflow, or inexact; we don't care.
3555 // FIXME need to be more flexible about rounding mode.
3556 (void)V.convert(EVTToAPFloatSemantics(VT),
3557 APFloat::rmNearestTiesToEven, &ignored);
3558 return getConstantFP(V, DL, VT);
3562 // Canonicalize an UNDEF to the RHS, even over a constant.
3563 if (N1.getOpcode() == ISD::UNDEF) {
3564 if (isCommutativeBinOp(Opcode)) {
3568 case ISD::FP_ROUND_INREG:
3569 case ISD::SIGN_EXTEND_INREG:
3575 return N1; // fold op(undef, arg2) -> undef
3583 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3584 // For vectors, we can't easily build an all zero vector, just return
3591 // Fold a bunch of operators when the RHS is undef.
3592 if (N2.getOpcode() == ISD::UNDEF) {
3595 if (N1.getOpcode() == ISD::UNDEF)
3596 // Handle undef ^ undef -> 0 special case. This is a common
3598 return getConstant(0, DL, VT);
3608 return N2; // fold op(arg1, undef) -> undef
3614 if (getTarget().Options.UnsafeFPMath)
3622 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3623 // For vectors, we can't easily build an all zero vector, just return
3628 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3629 // For vectors, we can't easily build an all one vector, just return
3637 // Memoize this node if possible.
3639 SDVTList VTs = getVTList(VT);
3640 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3641 if (VT != MVT::Glue) {
3642 SDValue Ops[] = {N1, N2};
3643 FoldingSetNodeID ID;
3644 AddNodeIDNode(ID, Opcode, VTs, Ops);
3646 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3648 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3649 return SDValue(E, 0);
3651 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3653 CSEMap.InsertNode(N, IP);
3655 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3659 return SDValue(N, 0);
3662 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3663 SDValue N1, SDValue N2, SDValue N3) {
3664 // Perform various simplifications.
3665 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3668 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3669 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3670 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3671 if (N1CFP && N2CFP && N3CFP) {
3672 APFloat V1 = N1CFP->getValueAPF();
3673 const APFloat &V2 = N2CFP->getValueAPF();
3674 const APFloat &V3 = N3CFP->getValueAPF();
3675 APFloat::opStatus s =
3676 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3677 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3678 return getConstantFP(V1, DL, VT);
3682 case ISD::CONCAT_VECTORS:
3683 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3684 // one big BUILD_VECTOR.
3685 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3686 N2.getOpcode() == ISD::BUILD_VECTOR &&
3687 N3.getOpcode() == ISD::BUILD_VECTOR) {
3688 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3689 N1.getNode()->op_end());
3690 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3691 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3692 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3696 // Use FoldSetCC to simplify SETCC's.
3697 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3698 if (Simp.getNode()) return Simp;
3703 if (N1C->getZExtValue())
3704 return N2; // select true, X, Y -> X
3705 return N3; // select false, X, Y -> Y
3708 if (N2 == N3) return N2; // select C, X, X -> X
3710 case ISD::VECTOR_SHUFFLE:
3711 llvm_unreachable("should use getVectorShuffle constructor!");
3712 case ISD::INSERT_SUBVECTOR: {
3714 if (VT.isSimple() && N1.getValueType().isSimple()
3715 && N2.getValueType().isSimple()) {
3716 assert(VT.isVector() && N1.getValueType().isVector() &&
3717 N2.getValueType().isVector() &&
3718 "Insert subvector VTs must be a vectors");
3719 assert(VT == N1.getValueType() &&
3720 "Dest and insert subvector source types must match!");
3721 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3722 "Insert subvector must be from smaller vector to larger vector!");
3723 if (isa<ConstantSDNode>(Index.getNode())) {
3724 assert((N2.getValueType().getVectorNumElements() +
3725 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3726 <= VT.getVectorNumElements())
3727 && "Insert subvector overflow!");
3730 // Trivial insertion.
3731 if (VT.getSimpleVT() == N2.getSimpleValueType())
3737 // Fold bit_convert nodes from a type to themselves.
3738 if (N1.getValueType() == VT)
3743 // Memoize node if it doesn't produce a flag.
3745 SDVTList VTs = getVTList(VT);
3746 if (VT != MVT::Glue) {
3747 SDValue Ops[] = { N1, N2, N3 };
3748 FoldingSetNodeID ID;
3749 AddNodeIDNode(ID, Opcode, VTs, Ops);
3751 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3752 return SDValue(E, 0);
3754 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3755 DL.getDebugLoc(), VTs, N1, N2, N3);
3756 CSEMap.InsertNode(N, IP);
3758 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3759 DL.getDebugLoc(), VTs, N1, N2, N3);
3763 return SDValue(N, 0);
3766 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3767 SDValue N1, SDValue N2, SDValue N3,
3769 SDValue Ops[] = { N1, N2, N3, N4 };
3770 return getNode(Opcode, DL, VT, Ops);
3773 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3774 SDValue N1, SDValue N2, SDValue N3,
3775 SDValue N4, SDValue N5) {
3776 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3777 return getNode(Opcode, DL, VT, Ops);
3780 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3781 /// the incoming stack arguments to be loaded from the stack.
3782 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3783 SmallVector<SDValue, 8> ArgChains;
3785 // Include the original chain at the beginning of the list. When this is
3786 // used by target LowerCall hooks, this helps legalize find the
3787 // CALLSEQ_BEGIN node.
3788 ArgChains.push_back(Chain);
3790 // Add a chain value for each stack argument.
3791 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3792 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3793 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3794 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3795 if (FI->getIndex() < 0)
3796 ArgChains.push_back(SDValue(L, 1));
3798 // Build a tokenfactor for all the chains.
3799 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3802 /// getMemsetValue - Vectorized representation of the memset value
3804 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3806 assert(Value.getOpcode() != ISD::UNDEF);
3808 unsigned NumBits = VT.getScalarType().getSizeInBits();
3809 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3810 assert(C->getAPIntValue().getBitWidth() == 8);
3811 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3813 return DAG.getConstant(Val, dl, VT);
3814 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3818 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3819 EVT IntVT = VT.getScalarType();
3820 if (!IntVT.isInteger())
3821 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3823 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3825 // Use a multiplication with 0x010101... to extend the input to the
3827 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3828 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3829 DAG.getConstant(Magic, dl, IntVT));
3832 if (VT != Value.getValueType() && !VT.isInteger())
3833 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3834 if (VT != Value.getValueType()) {
3835 assert(VT.getVectorElementType() == Value.getValueType() &&
3836 "value type should be one vector element here");
3837 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3838 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3844 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3845 /// used when a memcpy is turned into a memset when the source is a constant
3847 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3848 const TargetLowering &TLI, StringRef Str) {
3849 // Handle vector with all elements zero.
3852 return DAG.getConstant(0, dl, VT);
3853 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3854 return DAG.getConstantFP(0.0, dl, VT);
3855 else if (VT.isVector()) {
3856 unsigned NumElts = VT.getVectorNumElements();
3857 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3858 return DAG.getNode(ISD::BITCAST, dl, VT,
3859 DAG.getConstant(0, dl,
3860 EVT::getVectorVT(*DAG.getContext(),
3863 llvm_unreachable("Expected type!");
3866 assert(!VT.isVector() && "Can't handle vector type here!");
3867 unsigned NumVTBits = VT.getSizeInBits();
3868 unsigned NumVTBytes = NumVTBits / 8;
3869 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3871 APInt Val(NumVTBits, 0);
3872 if (TLI.isLittleEndian()) {
3873 for (unsigned i = 0; i != NumBytes; ++i)
3874 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3876 for (unsigned i = 0; i != NumBytes; ++i)
3877 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3880 // If the "cost" of materializing the integer immediate is less than the cost
3881 // of a load, then it is cost effective to turn the load into the immediate.
3882 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3883 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3884 return DAG.getConstant(Val, dl, VT);
3885 return SDValue(nullptr, 0);
3888 /// getMemBasePlusOffset - Returns base and offset node for the
3890 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3891 SelectionDAG &DAG) {
3892 EVT VT = Base.getValueType();
3893 return DAG.getNode(ISD::ADD, dl,
3894 VT, Base, DAG.getConstant(Offset, dl, VT));
3897 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3899 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3900 unsigned SrcDelta = 0;
3901 GlobalAddressSDNode *G = nullptr;
3902 if (Src.getOpcode() == ISD::GlobalAddress)
3903 G = cast<GlobalAddressSDNode>(Src);
3904 else if (Src.getOpcode() == ISD::ADD &&
3905 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3906 Src.getOperand(1).getOpcode() == ISD::Constant) {
3907 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3908 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3913 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3916 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3917 /// to replace the memset / memcpy. Return true if the number of memory ops
3918 /// is below the threshold. It returns the types of the sequence of
3919 /// memory ops to perform memset / memcpy by reference.
3920 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3921 unsigned Limit, uint64_t Size,
3922 unsigned DstAlign, unsigned SrcAlign,
3928 const TargetLowering &TLI) {
3929 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3930 "Expecting memcpy / memset source to meet alignment requirement!");
3931 // If 'SrcAlign' is zero, that means the memory operation does not need to
3932 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3933 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3934 // is the specified alignment of the memory operation. If it is zero, that
3935 // means it's possible to change the alignment of the destination.
3936 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3937 // not need to be loaded.
3938 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3939 IsMemset, ZeroMemset, MemcpyStrSrc,
3940 DAG.getMachineFunction());
3942 if (VT == MVT::Other) {
3944 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3945 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3946 VT = TLI.getPointerTy();
3948 switch (DstAlign & 7) {
3949 case 0: VT = MVT::i64; break;
3950 case 4: VT = MVT::i32; break;
3951 case 2: VT = MVT::i16; break;
3952 default: VT = MVT::i8; break;
3957 while (!TLI.isTypeLegal(LVT))
3958 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3959 assert(LVT.isInteger());
3965 unsigned NumMemOps = 0;
3967 unsigned VTSize = VT.getSizeInBits() / 8;
3968 while (VTSize > Size) {
3969 // For now, only use non-vector load / store's for the left-over pieces.
3974 if (VT.isVector() || VT.isFloatingPoint()) {
3975 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3976 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3977 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3979 else if (NewVT == MVT::i64 &&
3980 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3981 TLI.isSafeMemOpType(MVT::f64)) {
3982 // i64 is usually not legal on 32-bit targets, but f64 may be.
3990 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3991 if (NewVT == MVT::i8)
3993 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3995 NewVTSize = NewVT.getSizeInBits() / 8;
3997 // If the new VT cannot cover all of the remaining bits, then consider
3998 // issuing a (or a pair of) unaligned and overlapping load / store.
3999 // FIXME: Only does this for 64-bit or more since we don't have proper
4000 // cost model for unaligned load / store.
4003 if (NumMemOps && AllowOverlap &&
4004 VTSize >= 8 && NewVTSize < Size &&
4005 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4013 if (++NumMemOps > Limit)
4016 MemOps.push_back(VT);
4023 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4024 SDValue Chain, SDValue Dst,
4025 SDValue Src, uint64_t Size,
4026 unsigned Align, bool isVol,
4028 MachinePointerInfo DstPtrInfo,
4029 MachinePointerInfo SrcPtrInfo) {
4030 // Turn a memcpy of undef to nop.
4031 if (Src.getOpcode() == ISD::UNDEF)
4034 // Expand memcpy to a series of load and store ops if the size operand falls
4035 // below a certain threshold.
4036 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4037 // rather than maybe a humongous number of loads and stores.
4038 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4039 std::vector<EVT> MemOps;
4040 bool DstAlignCanChange = false;
4041 MachineFunction &MF = DAG.getMachineFunction();
4042 MachineFrameInfo *MFI = MF.getFrameInfo();
4043 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4044 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4045 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4046 DstAlignCanChange = true;
4047 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4048 if (Align > SrcAlign)
4051 bool CopyFromStr = isMemSrcFromString(Src, Str);
4052 bool isZeroStr = CopyFromStr && Str.empty();
4053 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4055 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4056 (DstAlignCanChange ? 0 : Align),
4057 (isZeroStr ? 0 : SrcAlign),
4058 false, false, CopyFromStr, true, DAG, TLI))
4061 if (DstAlignCanChange) {
4062 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4063 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4065 // Don't promote to an alignment that would require dynamic stack
4067 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4068 if (!TRI->needsStackRealignment(MF))
4069 while (NewAlign > Align &&
4070 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4073 if (NewAlign > Align) {
4074 // Give the stack frame object a larger alignment if needed.
4075 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4076 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4081 SmallVector<SDValue, 8> OutChains;
4082 unsigned NumMemOps = MemOps.size();
4083 uint64_t SrcOff = 0, DstOff = 0;
4084 for (unsigned i = 0; i != NumMemOps; ++i) {
4086 unsigned VTSize = VT.getSizeInBits() / 8;
4087 SDValue Value, Store;
4089 if (VTSize > Size) {
4090 // Issuing an unaligned load / store pair that overlaps with the previous
4091 // pair. Adjust the offset accordingly.
4092 assert(i == NumMemOps-1 && i != 0);
4093 SrcOff -= VTSize - Size;
4094 DstOff -= VTSize - Size;
4098 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4099 // It's unlikely a store of a vector immediate can be done in a single
4100 // instruction. It would require a load from a constantpool first.
4101 // We only handle zero vectors here.
4102 // FIXME: Handle other cases where store of vector immediate is done in
4103 // a single instruction.
4104 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4105 if (Value.getNode())
4106 Store = DAG.getStore(Chain, dl, Value,
4107 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4108 DstPtrInfo.getWithOffset(DstOff), isVol,
4112 if (!Store.getNode()) {
4113 // The type might not be legal for the target. This should only happen
4114 // if the type is smaller than a legal type, as on PPC, so the right
4115 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4116 // to Load/Store if NVT==VT.
4117 // FIXME does the case above also need this?
4118 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4119 assert(NVT.bitsGE(VT));
4120 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4121 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4122 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4123 false, MinAlign(SrcAlign, SrcOff));
4124 Store = DAG.getTruncStore(Chain, dl, Value,
4125 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4126 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4129 OutChains.push_back(Store);
4135 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4138 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4139 SDValue Chain, SDValue Dst,
4140 SDValue Src, uint64_t Size,
4141 unsigned Align, bool isVol,
4143 MachinePointerInfo DstPtrInfo,
4144 MachinePointerInfo SrcPtrInfo) {
4145 // Turn a memmove of undef to nop.
4146 if (Src.getOpcode() == ISD::UNDEF)
4149 // Expand memmove to a series of load and store ops if the size operand falls
4150 // below a certain threshold.
4151 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4152 std::vector<EVT> MemOps;
4153 bool DstAlignCanChange = false;
4154 MachineFunction &MF = DAG.getMachineFunction();
4155 MachineFrameInfo *MFI = MF.getFrameInfo();
4156 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4157 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4158 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4159 DstAlignCanChange = true;
4160 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4161 if (Align > SrcAlign)
4163 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4165 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4166 (DstAlignCanChange ? 0 : Align), SrcAlign,
4167 false, false, false, false, DAG, TLI))
4170 if (DstAlignCanChange) {
4171 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4172 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4173 if (NewAlign > Align) {
4174 // Give the stack frame object a larger alignment if needed.
4175 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4176 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4181 uint64_t SrcOff = 0, DstOff = 0;
4182 SmallVector<SDValue, 8> LoadValues;
4183 SmallVector<SDValue, 8> LoadChains;
4184 SmallVector<SDValue, 8> OutChains;
4185 unsigned NumMemOps = MemOps.size();
4186 for (unsigned i = 0; i < NumMemOps; i++) {
4188 unsigned VTSize = VT.getSizeInBits() / 8;
4191 Value = DAG.getLoad(VT, dl, Chain,
4192 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4193 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4194 false, false, SrcAlign);
4195 LoadValues.push_back(Value);
4196 LoadChains.push_back(Value.getValue(1));
4199 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4201 for (unsigned i = 0; i < NumMemOps; i++) {
4203 unsigned VTSize = VT.getSizeInBits() / 8;
4206 Store = DAG.getStore(Chain, dl, LoadValues[i],
4207 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4208 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4209 OutChains.push_back(Store);
4213 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4216 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4219 /// \param DAG Selection DAG where lowered code is placed.
4220 /// \param dl Link to corresponding IR location.
4221 /// \param Chain Control flow dependency.
4222 /// \param Dst Pointer to destination memory location.
4223 /// \param Src Value of byte to write into the memory.
4224 /// \param Size Number of bytes to write.
4225 /// \param Align Alignment of the destination in bytes.
4226 /// \param isVol True if destination is volatile.
4227 /// \param DstPtrInfo IR information on the memory pointer.
4228 /// \returns New head in the control flow, if lowering was successful, empty
4229 /// SDValue otherwise.
4231 /// The function tries to replace 'llvm.memset' intrinsic with several store
4232 /// operations and value calculation code. This is usually profitable for small
4234 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4235 SDValue Chain, SDValue Dst,
4236 SDValue Src, uint64_t Size,
4237 unsigned Align, bool isVol,
4238 MachinePointerInfo DstPtrInfo) {
4239 // Turn a memset of undef to nop.
4240 if (Src.getOpcode() == ISD::UNDEF)
4243 // Expand memset to a series of load/store ops if the size operand
4244 // falls below a certain threshold.
4245 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4246 std::vector<EVT> MemOps;
4247 bool DstAlignCanChange = false;
4248 MachineFunction &MF = DAG.getMachineFunction();
4249 MachineFrameInfo *MFI = MF.getFrameInfo();
4250 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4251 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4252 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4253 DstAlignCanChange = true;
4255 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4256 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4257 Size, (DstAlignCanChange ? 0 : Align), 0,
4258 true, IsZeroVal, false, true, DAG, TLI))
4261 if (DstAlignCanChange) {
4262 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4263 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4264 if (NewAlign > Align) {
4265 // Give the stack frame object a larger alignment if needed.
4266 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4267 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4272 SmallVector<SDValue, 8> OutChains;
4273 uint64_t DstOff = 0;
4274 unsigned NumMemOps = MemOps.size();
4276 // Find the largest store and generate the bit pattern for it.
4277 EVT LargestVT = MemOps[0];
4278 for (unsigned i = 1; i < NumMemOps; i++)
4279 if (MemOps[i].bitsGT(LargestVT))
4280 LargestVT = MemOps[i];
4281 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4283 for (unsigned i = 0; i < NumMemOps; i++) {
4285 unsigned VTSize = VT.getSizeInBits() / 8;
4286 if (VTSize > Size) {
4287 // Issuing an unaligned load / store pair that overlaps with the previous
4288 // pair. Adjust the offset accordingly.
4289 assert(i == NumMemOps-1 && i != 0);
4290 DstOff -= VTSize - Size;
4293 // If this store is smaller than the largest store see whether we can get
4294 // the smaller value for free with a truncate.
4295 SDValue Value = MemSetValue;
4296 if (VT.bitsLT(LargestVT)) {
4297 if (!LargestVT.isVector() && !VT.isVector() &&
4298 TLI.isTruncateFree(LargestVT, VT))
4299 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4301 Value = getMemsetValue(Src, VT, DAG, dl);
4303 assert(Value.getValueType() == VT && "Value with wrong type.");
4304 SDValue Store = DAG.getStore(Chain, dl, Value,
4305 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4306 DstPtrInfo.getWithOffset(DstOff),
4307 isVol, false, Align);
4308 OutChains.push_back(Store);
4309 DstOff += VT.getSizeInBits() / 8;
4313 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4316 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4317 SDValue Src, SDValue Size,
4318 unsigned Align, bool isVol, bool AlwaysInline,
4319 bool isTailCall, MachinePointerInfo DstPtrInfo,
4320 MachinePointerInfo SrcPtrInfo) {
4321 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4323 // Check to see if we should lower the memcpy to loads and stores first.
4324 // For cases within the target-specified limits, this is the best choice.
4325 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4327 // Memcpy with size zero? Just return the original chain.
4328 if (ConstantSize->isNullValue())
4331 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4332 ConstantSize->getZExtValue(),Align,
4333 isVol, false, DstPtrInfo, SrcPtrInfo);
4334 if (Result.getNode())
4338 // Then check to see if we should lower the memcpy with target-specific
4339 // code. If the target chooses to do this, this is the next best.
4341 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4342 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4343 DstPtrInfo, SrcPtrInfo);
4344 if (Result.getNode())
4348 // If we really need inline code and the target declined to provide it,
4349 // use a (potentially long) sequence of loads and stores.
4351 assert(ConstantSize && "AlwaysInline requires a constant size!");
4352 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4353 ConstantSize->getZExtValue(), Align, isVol,
4354 true, DstPtrInfo, SrcPtrInfo);
4357 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4358 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4359 // respect volatile, so they may do things like read or write memory
4360 // beyond the given memory regions. But fixing this isn't easy, and most
4361 // people don't care.
4363 // Emit a library call.
4364 TargetLowering::ArgListTy Args;
4365 TargetLowering::ArgListEntry Entry;
4366 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4367 Entry.Node = Dst; Args.push_back(Entry);
4368 Entry.Node = Src; Args.push_back(Entry);
4369 Entry.Node = Size; Args.push_back(Entry);
4370 // FIXME: pass in SDLoc
4371 TargetLowering::CallLoweringInfo CLI(*this);
4372 CLI.setDebugLoc(dl).setChain(Chain)
4373 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4374 Type::getVoidTy(*getContext()),
4375 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4376 TLI->getPointerTy()), std::move(Args), 0)
4378 .setTailCall(isTailCall);
4380 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4381 return CallResult.second;
4384 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4385 SDValue Src, SDValue Size,
4386 unsigned Align, bool isVol, bool isTailCall,
4387 MachinePointerInfo DstPtrInfo,
4388 MachinePointerInfo SrcPtrInfo) {
4389 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4391 // Check to see if we should lower the memmove to loads and stores first.
4392 // For cases within the target-specified limits, this is the best choice.
4393 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4395 // Memmove with size zero? Just return the original chain.
4396 if (ConstantSize->isNullValue())
4400 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4401 ConstantSize->getZExtValue(), Align, isVol,
4402 false, DstPtrInfo, SrcPtrInfo);
4403 if (Result.getNode())
4407 // Then check to see if we should lower the memmove with target-specific
4408 // code. If the target chooses to do this, this is the next best.
4410 SDValue Result = TSI->EmitTargetCodeForMemmove(
4411 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4412 if (Result.getNode())
4416 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4417 // not be safe. See memcpy above for more details.
4419 // Emit a library call.
4420 TargetLowering::ArgListTy Args;
4421 TargetLowering::ArgListEntry Entry;
4422 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4423 Entry.Node = Dst; Args.push_back(Entry);
4424 Entry.Node = Src; Args.push_back(Entry);
4425 Entry.Node = Size; Args.push_back(Entry);
4426 // FIXME: pass in SDLoc
4427 TargetLowering::CallLoweringInfo CLI(*this);
4428 CLI.setDebugLoc(dl).setChain(Chain)
4429 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4430 Type::getVoidTy(*getContext()),
4431 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4432 TLI->getPointerTy()), std::move(Args), 0)
4434 .setTailCall(isTailCall);
4436 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4437 return CallResult.second;
4440 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4441 SDValue Src, SDValue Size,
4442 unsigned Align, bool isVol, bool isTailCall,
4443 MachinePointerInfo DstPtrInfo) {
4444 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4446 // Check to see if we should lower the memset to stores first.
4447 // For cases within the target-specified limits, this is the best choice.
4448 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4450 // Memset with size zero? Just return the original chain.
4451 if (ConstantSize->isNullValue())
4455 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4456 Align, isVol, DstPtrInfo);
4458 if (Result.getNode())
4462 // Then check to see if we should lower the memset with target-specific
4463 // code. If the target chooses to do this, this is the next best.
4465 SDValue Result = TSI->EmitTargetCodeForMemset(
4466 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4467 if (Result.getNode())
4471 // Emit a library call.
4472 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4473 TargetLowering::ArgListTy Args;
4474 TargetLowering::ArgListEntry Entry;
4475 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4476 Args.push_back(Entry);
4478 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4479 Args.push_back(Entry);
4481 Entry.Ty = IntPtrTy;
4482 Args.push_back(Entry);
4484 // FIXME: pass in SDLoc
4485 TargetLowering::CallLoweringInfo CLI(*this);
4486 CLI.setDebugLoc(dl).setChain(Chain)
4487 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4488 Type::getVoidTy(*getContext()),
4489 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4490 TLI->getPointerTy()), std::move(Args), 0)
4492 .setTailCall(isTailCall);
4494 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4495 return CallResult.second;
4498 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4499 SDVTList VTList, ArrayRef<SDValue> Ops,
4500 MachineMemOperand *MMO,
4501 AtomicOrdering SuccessOrdering,
4502 AtomicOrdering FailureOrdering,
4503 SynchronizationScope SynchScope) {
4504 FoldingSetNodeID ID;
4505 ID.AddInteger(MemVT.getRawBits());
4506 AddNodeIDNode(ID, Opcode, VTList, Ops);
4507 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4509 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4510 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4511 return SDValue(E, 0);
4514 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4515 // SDNode doesn't have access to it. This memory will be "leaked" when
4516 // the node is deallocated, but recovered when the allocator is released.
4517 // If the number of operands is less than 5 we use AtomicSDNode's internal
4519 unsigned NumOps = Ops.size();
4520 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4523 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4524 dl.getDebugLoc(), VTList, MemVT,
4525 Ops.data(), DynOps, NumOps, MMO,
4526 SuccessOrdering, FailureOrdering,
4528 CSEMap.InsertNode(N, IP);
4530 return SDValue(N, 0);
4533 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4534 SDVTList VTList, ArrayRef<SDValue> Ops,
4535 MachineMemOperand *MMO,
4536 AtomicOrdering Ordering,
4537 SynchronizationScope SynchScope) {
4538 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4539 Ordering, SynchScope);
4542 SDValue SelectionDAG::getAtomicCmpSwap(
4543 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4544 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4545 unsigned Alignment, AtomicOrdering SuccessOrdering,
4546 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4547 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4548 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4549 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4551 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4552 Alignment = getEVTAlignment(MemVT);
4554 MachineFunction &MF = getMachineFunction();
4556 // FIXME: Volatile isn't really correct; we should keep track of atomic
4557 // orderings in the memoperand.
4558 unsigned Flags = MachineMemOperand::MOVolatile;
4559 Flags |= MachineMemOperand::MOLoad;
4560 Flags |= MachineMemOperand::MOStore;
4562 MachineMemOperand *MMO =
4563 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4565 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4566 SuccessOrdering, FailureOrdering, SynchScope);
4569 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4570 SDVTList VTs, SDValue Chain, SDValue Ptr,
4571 SDValue Cmp, SDValue Swp,
4572 MachineMemOperand *MMO,
4573 AtomicOrdering SuccessOrdering,
4574 AtomicOrdering FailureOrdering,
4575 SynchronizationScope SynchScope) {
4576 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4577 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4578 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4580 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4581 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4582 SuccessOrdering, FailureOrdering, SynchScope);
4585 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4587 SDValue Ptr, SDValue Val,
4588 const Value* PtrVal,
4590 AtomicOrdering Ordering,
4591 SynchronizationScope SynchScope) {
4592 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4593 Alignment = getEVTAlignment(MemVT);
4595 MachineFunction &MF = getMachineFunction();
4596 // An atomic store does not load. An atomic load does not store.
4597 // (An atomicrmw obviously both loads and stores.)
4598 // For now, atomics are considered to be volatile always, and they are
4600 // FIXME: Volatile isn't really correct; we should keep track of atomic
4601 // orderings in the memoperand.
4602 unsigned Flags = MachineMemOperand::MOVolatile;
4603 if (Opcode != ISD::ATOMIC_STORE)
4604 Flags |= MachineMemOperand::MOLoad;
4605 if (Opcode != ISD::ATOMIC_LOAD)
4606 Flags |= MachineMemOperand::MOStore;
4608 MachineMemOperand *MMO =
4609 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4610 MemVT.getStoreSize(), Alignment);
4612 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4613 Ordering, SynchScope);
4616 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4618 SDValue Ptr, SDValue Val,
4619 MachineMemOperand *MMO,
4620 AtomicOrdering Ordering,
4621 SynchronizationScope SynchScope) {
4622 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4623 Opcode == ISD::ATOMIC_LOAD_SUB ||
4624 Opcode == ISD::ATOMIC_LOAD_AND ||
4625 Opcode == ISD::ATOMIC_LOAD_OR ||
4626 Opcode == ISD::ATOMIC_LOAD_XOR ||
4627 Opcode == ISD::ATOMIC_LOAD_NAND ||
4628 Opcode == ISD::ATOMIC_LOAD_MIN ||
4629 Opcode == ISD::ATOMIC_LOAD_MAX ||
4630 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4631 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4632 Opcode == ISD::ATOMIC_SWAP ||
4633 Opcode == ISD::ATOMIC_STORE) &&
4634 "Invalid Atomic Op");
4636 EVT VT = Val.getValueType();
4638 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4639 getVTList(VT, MVT::Other);
4640 SDValue Ops[] = {Chain, Ptr, Val};
4641 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4644 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4645 EVT VT, SDValue Chain,
4647 MachineMemOperand *MMO,
4648 AtomicOrdering Ordering,
4649 SynchronizationScope SynchScope) {
4650 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4652 SDVTList VTs = getVTList(VT, MVT::Other);
4653 SDValue Ops[] = {Chain, Ptr};
4654 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4657 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4658 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4659 if (Ops.size() == 1)
4662 SmallVector<EVT, 4> VTs;
4663 VTs.reserve(Ops.size());
4664 for (unsigned i = 0; i < Ops.size(); ++i)
4665 VTs.push_back(Ops[i].getValueType());
4666 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4670 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4671 ArrayRef<SDValue> Ops,
4672 EVT MemVT, MachinePointerInfo PtrInfo,
4673 unsigned Align, bool Vol,
4674 bool ReadMem, bool WriteMem, unsigned Size) {
4675 if (Align == 0) // Ensure that codegen never sees alignment 0
4676 Align = getEVTAlignment(MemVT);
4678 MachineFunction &MF = getMachineFunction();
4681 Flags |= MachineMemOperand::MOStore;
4683 Flags |= MachineMemOperand::MOLoad;
4685 Flags |= MachineMemOperand::MOVolatile;
4687 Size = MemVT.getStoreSize();
4688 MachineMemOperand *MMO =
4689 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4691 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4695 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4696 ArrayRef<SDValue> Ops, EVT MemVT,
4697 MachineMemOperand *MMO) {
4698 assert((Opcode == ISD::INTRINSIC_VOID ||
4699 Opcode == ISD::INTRINSIC_W_CHAIN ||
4700 Opcode == ISD::PREFETCH ||
4701 Opcode == ISD::LIFETIME_START ||
4702 Opcode == ISD::LIFETIME_END ||
4703 (Opcode <= INT_MAX &&
4704 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4705 "Opcode is not a memory-accessing opcode!");
4707 // Memoize the node unless it returns a flag.
4708 MemIntrinsicSDNode *N;
4709 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4710 FoldingSetNodeID ID;
4711 AddNodeIDNode(ID, Opcode, VTList, Ops);
4712 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4714 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4715 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4716 return SDValue(E, 0);
4719 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4720 dl.getDebugLoc(), VTList, Ops,
4722 CSEMap.InsertNode(N, IP);
4724 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4725 dl.getDebugLoc(), VTList, Ops,
4729 return SDValue(N, 0);
4732 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4733 /// MachinePointerInfo record from it. This is particularly useful because the
4734 /// code generator has many cases where it doesn't bother passing in a
4735 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4736 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4737 // If this is FI+Offset, we can model it.
4738 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4739 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4741 // If this is (FI+Offset1)+Offset2, we can model it.
4742 if (Ptr.getOpcode() != ISD::ADD ||
4743 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4744 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4745 return MachinePointerInfo();
4747 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4748 return MachinePointerInfo::getFixedStack(FI, Offset+
4749 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4752 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4753 /// MachinePointerInfo record from it. This is particularly useful because the
4754 /// code generator has many cases where it doesn't bother passing in a
4755 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4756 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4757 // If the 'Offset' value isn't a constant, we can't handle this.
4758 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4759 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4760 if (OffsetOp.getOpcode() == ISD::UNDEF)
4761 return InferPointerInfo(Ptr);
4762 return MachinePointerInfo();
4767 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4768 EVT VT, SDLoc dl, SDValue Chain,
4769 SDValue Ptr, SDValue Offset,
4770 MachinePointerInfo PtrInfo, EVT MemVT,
4771 bool isVolatile, bool isNonTemporal, bool isInvariant,
4772 unsigned Alignment, const AAMDNodes &AAInfo,
4773 const MDNode *Ranges) {
4774 assert(Chain.getValueType() == MVT::Other &&
4775 "Invalid chain type");
4776 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4777 Alignment = getEVTAlignment(VT);
4779 unsigned Flags = MachineMemOperand::MOLoad;
4781 Flags |= MachineMemOperand::MOVolatile;
4783 Flags |= MachineMemOperand::MONonTemporal;
4785 Flags |= MachineMemOperand::MOInvariant;
4787 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4789 if (PtrInfo.V.isNull())
4790 PtrInfo = InferPointerInfo(Ptr, Offset);
4792 MachineFunction &MF = getMachineFunction();
4793 MachineMemOperand *MMO =
4794 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4796 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4800 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4801 EVT VT, SDLoc dl, SDValue Chain,
4802 SDValue Ptr, SDValue Offset, EVT MemVT,
4803 MachineMemOperand *MMO) {
4805 ExtType = ISD::NON_EXTLOAD;
4806 } else if (ExtType == ISD::NON_EXTLOAD) {
4807 assert(VT == MemVT && "Non-extending load from different memory type!");
4810 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4811 "Should only be an extending load, not truncating!");
4812 assert(VT.isInteger() == MemVT.isInteger() &&
4813 "Cannot convert from FP to Int or Int -> FP!");
4814 assert(VT.isVector() == MemVT.isVector() &&
4815 "Cannot use an ext load to convert to or from a vector!");
4816 assert((!VT.isVector() ||
4817 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4818 "Cannot use an ext load to change the number of vector elements!");
4821 bool Indexed = AM != ISD::UNINDEXED;
4822 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4823 "Unindexed load with an offset!");
4825 SDVTList VTs = Indexed ?
4826 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4827 SDValue Ops[] = { Chain, Ptr, Offset };
4828 FoldingSetNodeID ID;
4829 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4830 ID.AddInteger(MemVT.getRawBits());
4831 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4832 MMO->isNonTemporal(),
4833 MMO->isInvariant()));
4834 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4836 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4837 cast<LoadSDNode>(E)->refineAlignment(MMO);
4838 return SDValue(E, 0);
4840 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4841 dl.getDebugLoc(), VTs, AM, ExtType,
4843 CSEMap.InsertNode(N, IP);
4845 return SDValue(N, 0);
4848 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4849 SDValue Chain, SDValue Ptr,
4850 MachinePointerInfo PtrInfo,
4851 bool isVolatile, bool isNonTemporal,
4852 bool isInvariant, unsigned Alignment,
4853 const AAMDNodes &AAInfo,
4854 const MDNode *Ranges) {
4855 SDValue Undef = getUNDEF(Ptr.getValueType());
4856 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4857 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4861 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4862 SDValue Chain, SDValue Ptr,
4863 MachineMemOperand *MMO) {
4864 SDValue Undef = getUNDEF(Ptr.getValueType());
4865 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4869 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4870 SDValue Chain, SDValue Ptr,
4871 MachinePointerInfo PtrInfo, EVT MemVT,
4872 bool isVolatile, bool isNonTemporal,
4873 bool isInvariant, unsigned Alignment,
4874 const AAMDNodes &AAInfo) {
4875 SDValue Undef = getUNDEF(Ptr.getValueType());
4876 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4877 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4882 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4883 SDValue Chain, SDValue Ptr, EVT MemVT,
4884 MachineMemOperand *MMO) {
4885 SDValue Undef = getUNDEF(Ptr.getValueType());
4886 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4891 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4892 SDValue Offset, ISD::MemIndexedMode AM) {
4893 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4894 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4895 "Load is already a indexed load!");
4896 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4897 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4898 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4899 false, LD->getAlignment());
4902 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4903 SDValue Ptr, MachinePointerInfo PtrInfo,
4904 bool isVolatile, bool isNonTemporal,
4905 unsigned Alignment, const AAMDNodes &AAInfo) {
4906 assert(Chain.getValueType() == MVT::Other &&
4907 "Invalid chain type");
4908 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4909 Alignment = getEVTAlignment(Val.getValueType());
4911 unsigned Flags = MachineMemOperand::MOStore;
4913 Flags |= MachineMemOperand::MOVolatile;
4915 Flags |= MachineMemOperand::MONonTemporal;
4917 if (PtrInfo.V.isNull())
4918 PtrInfo = InferPointerInfo(Ptr);
4920 MachineFunction &MF = getMachineFunction();
4921 MachineMemOperand *MMO =
4922 MF.getMachineMemOperand(PtrInfo, Flags,
4923 Val.getValueType().getStoreSize(), Alignment,
4926 return getStore(Chain, dl, Val, Ptr, MMO);
4929 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4930 SDValue Ptr, MachineMemOperand *MMO) {
4931 assert(Chain.getValueType() == MVT::Other &&
4932 "Invalid chain type");
4933 EVT VT = Val.getValueType();
4934 SDVTList VTs = getVTList(MVT::Other);
4935 SDValue Undef = getUNDEF(Ptr.getValueType());
4936 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4937 FoldingSetNodeID ID;
4938 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4939 ID.AddInteger(VT.getRawBits());
4940 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4941 MMO->isNonTemporal(), MMO->isInvariant()));
4942 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4944 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4945 cast<StoreSDNode>(E)->refineAlignment(MMO);
4946 return SDValue(E, 0);
4948 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4949 dl.getDebugLoc(), VTs,
4950 ISD::UNINDEXED, false, VT, MMO);
4951 CSEMap.InsertNode(N, IP);
4953 return SDValue(N, 0);
4956 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4957 SDValue Ptr, MachinePointerInfo PtrInfo,
4958 EVT SVT,bool isVolatile, bool isNonTemporal,
4960 const AAMDNodes &AAInfo) {
4961 assert(Chain.getValueType() == MVT::Other &&
4962 "Invalid chain type");
4963 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4964 Alignment = getEVTAlignment(SVT);
4966 unsigned Flags = MachineMemOperand::MOStore;
4968 Flags |= MachineMemOperand::MOVolatile;
4970 Flags |= MachineMemOperand::MONonTemporal;
4972 if (PtrInfo.V.isNull())
4973 PtrInfo = InferPointerInfo(Ptr);
4975 MachineFunction &MF = getMachineFunction();
4976 MachineMemOperand *MMO =
4977 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4980 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4983 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4984 SDValue Ptr, EVT SVT,
4985 MachineMemOperand *MMO) {
4986 EVT VT = Val.getValueType();
4988 assert(Chain.getValueType() == MVT::Other &&
4989 "Invalid chain type");
4991 return getStore(Chain, dl, Val, Ptr, MMO);
4993 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4994 "Should only be a truncating store, not extending!");
4995 assert(VT.isInteger() == SVT.isInteger() &&
4996 "Can't do FP-INT conversion!");
4997 assert(VT.isVector() == SVT.isVector() &&
4998 "Cannot use trunc store to convert to or from a vector!");
4999 assert((!VT.isVector() ||
5000 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5001 "Cannot use trunc store to change the number of vector elements!");
5003 SDVTList VTs = getVTList(MVT::Other);
5004 SDValue Undef = getUNDEF(Ptr.getValueType());
5005 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5006 FoldingSetNodeID ID;
5007 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5008 ID.AddInteger(SVT.getRawBits());
5009 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5010 MMO->isNonTemporal(), MMO->isInvariant()));
5011 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5013 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5014 cast<StoreSDNode>(E)->refineAlignment(MMO);
5015 return SDValue(E, 0);
5017 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5018 dl.getDebugLoc(), VTs,
5019 ISD::UNINDEXED, true, SVT, MMO);
5020 CSEMap.InsertNode(N, IP);
5022 return SDValue(N, 0);
5026 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5027 SDValue Offset, ISD::MemIndexedMode AM) {
5028 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5029 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5030 "Store is already a indexed store!");
5031 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5032 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5033 FoldingSetNodeID ID;
5034 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5035 ID.AddInteger(ST->getMemoryVT().getRawBits());
5036 ID.AddInteger(ST->getRawSubclassData());
5037 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5039 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5040 return SDValue(E, 0);
5042 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5043 dl.getDebugLoc(), VTs, AM,
5044 ST->isTruncatingStore(),
5046 ST->getMemOperand());
5047 CSEMap.InsertNode(N, IP);
5049 return SDValue(N, 0);
5053 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5054 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5055 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5057 SDVTList VTs = getVTList(VT, MVT::Other);
5058 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5059 FoldingSetNodeID ID;
5060 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5061 ID.AddInteger(VT.getRawBits());
5062 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5064 MMO->isNonTemporal(),
5065 MMO->isInvariant()));
5066 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5068 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5069 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5070 return SDValue(E, 0);
5072 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5073 dl.getDebugLoc(), Ops, 4, VTs,
5075 CSEMap.InsertNode(N, IP);
5077 return SDValue(N, 0);
5080 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5081 SDValue Ptr, SDValue Mask, EVT MemVT,
5082 MachineMemOperand *MMO, bool isTrunc) {
5083 assert(Chain.getValueType() == MVT::Other &&
5084 "Invalid chain type");
5085 EVT VT = Val.getValueType();
5086 SDVTList VTs = getVTList(MVT::Other);
5087 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5088 FoldingSetNodeID ID;
5089 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5090 ID.AddInteger(VT.getRawBits());
5091 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5092 MMO->isNonTemporal(), MMO->isInvariant()));
5093 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5095 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5096 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5097 return SDValue(E, 0);
5099 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5100 dl.getDebugLoc(), Ops, 4,
5101 VTs, isTrunc, MemVT, MMO);
5102 CSEMap.InsertNode(N, IP);
5104 return SDValue(N, 0);
5108 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5109 ArrayRef<SDValue> Ops,
5110 MachineMemOperand *MMO) {
5112 FoldingSetNodeID ID;
5113 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5114 ID.AddInteger(VT.getRawBits());
5115 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5117 MMO->isNonTemporal(),
5118 MMO->isInvariant()));
5119 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5121 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5122 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5123 return SDValue(E, 0);
5125 MaskedGatherSDNode *N =
5126 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5128 CSEMap.InsertNode(N, IP);
5130 return SDValue(N, 0);
5133 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5134 ArrayRef<SDValue> Ops,
5135 MachineMemOperand *MMO) {
5136 FoldingSetNodeID ID;
5137 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5138 ID.AddInteger(VT.getRawBits());
5139 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5140 MMO->isNonTemporal(),
5141 MMO->isInvariant()));
5142 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5144 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5145 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5146 return SDValue(E, 0);
5149 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5151 CSEMap.InsertNode(N, IP);
5153 return SDValue(N, 0);
5156 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5157 SDValue Chain, SDValue Ptr,
5160 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5161 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5164 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5165 ArrayRef<SDUse> Ops) {
5166 switch (Ops.size()) {
5167 case 0: return getNode(Opcode, DL, VT);
5168 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5169 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5170 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5174 // Copy from an SDUse array into an SDValue array for use with
5175 // the regular getNode logic.
5176 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5177 return getNode(Opcode, DL, VT, NewOps);
5180 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5181 ArrayRef<SDValue> Ops) {
5182 unsigned NumOps = Ops.size();
5184 case 0: return getNode(Opcode, DL, VT);
5185 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5186 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5187 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5193 case ISD::SELECT_CC: {
5194 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5195 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5196 "LHS and RHS of condition must have same type!");
5197 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5198 "True and False arms of SelectCC must have same type!");
5199 assert(Ops[2].getValueType() == VT &&
5200 "select_cc node must be of same type as true and false value!");
5204 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5205 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5206 "LHS/RHS of comparison should match types!");
5213 SDVTList VTs = getVTList(VT);
5215 if (VT != MVT::Glue) {
5216 FoldingSetNodeID ID;
5217 AddNodeIDNode(ID, Opcode, VTs, Ops);
5220 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5221 return SDValue(E, 0);
5223 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5225 CSEMap.InsertNode(N, IP);
5227 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5232 return SDValue(N, 0);
5235 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5236 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5237 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5240 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5241 ArrayRef<SDValue> Ops) {
5242 if (VTList.NumVTs == 1)
5243 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5247 // FIXME: figure out how to safely handle things like
5248 // int foo(int x) { return 1 << (x & 255); }
5249 // int bar() { return foo(256); }
5250 case ISD::SRA_PARTS:
5251 case ISD::SRL_PARTS:
5252 case ISD::SHL_PARTS:
5253 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5254 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5255 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5256 else if (N3.getOpcode() == ISD::AND)
5257 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5258 // If the and is only masking out bits that cannot effect the shift,
5259 // eliminate the and.
5260 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5261 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5262 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5268 // Memoize the node unless it returns a flag.
5270 unsigned NumOps = Ops.size();
5271 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5272 FoldingSetNodeID ID;
5273 AddNodeIDNode(ID, Opcode, VTList, Ops);
5275 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5276 return SDValue(E, 0);
5279 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5280 DL.getDebugLoc(), VTList, Ops[0]);
5281 } else if (NumOps == 2) {
5282 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5283 DL.getDebugLoc(), VTList, Ops[0],
5285 } else if (NumOps == 3) {
5286 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5287 DL.getDebugLoc(), VTList, Ops[0],
5290 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5293 CSEMap.InsertNode(N, IP);
5296 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5297 DL.getDebugLoc(), VTList, Ops[0]);
5298 } else if (NumOps == 2) {
5299 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5300 DL.getDebugLoc(), VTList, Ops[0],
5302 } else if (NumOps == 3) {
5303 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5304 DL.getDebugLoc(), VTList, Ops[0],
5307 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5312 return SDValue(N, 0);
5315 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5316 return getNode(Opcode, DL, VTList, None);
5319 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5321 SDValue Ops[] = { N1 };
5322 return getNode(Opcode, DL, VTList, Ops);
5325 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5326 SDValue N1, SDValue N2) {
5327 SDValue Ops[] = { N1, N2 };
5328 return getNode(Opcode, DL, VTList, Ops);
5331 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5332 SDValue N1, SDValue N2, SDValue N3) {
5333 SDValue Ops[] = { N1, N2, N3 };
5334 return getNode(Opcode, DL, VTList, Ops);
5337 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5338 SDValue N1, SDValue N2, SDValue N3,
5340 SDValue Ops[] = { N1, N2, N3, N4 };
5341 return getNode(Opcode, DL, VTList, Ops);
5344 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5345 SDValue N1, SDValue N2, SDValue N3,
5346 SDValue N4, SDValue N5) {
5347 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5348 return getNode(Opcode, DL, VTList, Ops);
5351 SDVTList SelectionDAG::getVTList(EVT VT) {
5352 return makeVTList(SDNode::getValueTypeList(VT), 1);
5355 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5356 FoldingSetNodeID ID;
5358 ID.AddInteger(VT1.getRawBits());
5359 ID.AddInteger(VT2.getRawBits());
5362 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5364 EVT *Array = Allocator.Allocate<EVT>(2);
5367 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5368 VTListMap.InsertNode(Result, IP);
5370 return Result->getSDVTList();
5373 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5374 FoldingSetNodeID ID;
5376 ID.AddInteger(VT1.getRawBits());
5377 ID.AddInteger(VT2.getRawBits());
5378 ID.AddInteger(VT3.getRawBits());
5381 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5383 EVT *Array = Allocator.Allocate<EVT>(3);
5387 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5388 VTListMap.InsertNode(Result, IP);
5390 return Result->getSDVTList();
5393 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5394 FoldingSetNodeID ID;
5396 ID.AddInteger(VT1.getRawBits());
5397 ID.AddInteger(VT2.getRawBits());
5398 ID.AddInteger(VT3.getRawBits());
5399 ID.AddInteger(VT4.getRawBits());
5402 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5404 EVT *Array = Allocator.Allocate<EVT>(4);
5409 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5410 VTListMap.InsertNode(Result, IP);
5412 return Result->getSDVTList();
5415 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5416 unsigned NumVTs = VTs.size();
5417 FoldingSetNodeID ID;
5418 ID.AddInteger(NumVTs);
5419 for (unsigned index = 0; index < NumVTs; index++) {
5420 ID.AddInteger(VTs[index].getRawBits());
5424 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5426 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5427 std::copy(VTs.begin(), VTs.end(), Array);
5428 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5429 VTListMap.InsertNode(Result, IP);
5431 return Result->getSDVTList();
5435 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5436 /// specified operands. If the resultant node already exists in the DAG,
5437 /// this does not modify the specified node, instead it returns the node that
5438 /// already exists. If the resultant node does not exist in the DAG, the
5439 /// input node is returned. As a degenerate case, if you specify the same
5440 /// input operands as the node already has, the input node is returned.
5441 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5442 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5444 // Check to see if there is no change.
5445 if (Op == N->getOperand(0)) return N;
5447 // See if the modified node already exists.
5448 void *InsertPos = nullptr;
5449 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5452 // Nope it doesn't. Remove the node from its current place in the maps.
5454 if (!RemoveNodeFromCSEMaps(N))
5455 InsertPos = nullptr;
5457 // Now we update the operands.
5458 N->OperandList[0].set(Op);
5460 // If this gets put into a CSE map, add it.
5461 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5465 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5466 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5468 // Check to see if there is no change.
5469 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5470 return N; // No operands changed, just return the input node.
5472 // See if the modified node already exists.
5473 void *InsertPos = nullptr;
5474 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5477 // Nope it doesn't. Remove the node from its current place in the maps.
5479 if (!RemoveNodeFromCSEMaps(N))
5480 InsertPos = nullptr;
5482 // Now we update the operands.
5483 if (N->OperandList[0] != Op1)
5484 N->OperandList[0].set(Op1);
5485 if (N->OperandList[1] != Op2)
5486 N->OperandList[1].set(Op2);
5488 // If this gets put into a CSE map, add it.
5489 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5493 SDNode *SelectionDAG::
5494 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5495 SDValue Ops[] = { Op1, Op2, Op3 };
5496 return UpdateNodeOperands(N, Ops);
5499 SDNode *SelectionDAG::
5500 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5501 SDValue Op3, SDValue Op4) {
5502 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5503 return UpdateNodeOperands(N, Ops);
5506 SDNode *SelectionDAG::
5507 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5508 SDValue Op3, SDValue Op4, SDValue Op5) {
5509 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5510 return UpdateNodeOperands(N, Ops);
5513 SDNode *SelectionDAG::
5514 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5515 unsigned NumOps = Ops.size();
5516 assert(N->getNumOperands() == NumOps &&
5517 "Update with wrong number of operands");
5519 // If no operands changed just return the input node.
5520 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5523 // See if the modified node already exists.
5524 void *InsertPos = nullptr;
5525 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5528 // Nope it doesn't. Remove the node from its current place in the maps.
5530 if (!RemoveNodeFromCSEMaps(N))
5531 InsertPos = nullptr;
5533 // Now we update the operands.
5534 for (unsigned i = 0; i != NumOps; ++i)
5535 if (N->OperandList[i] != Ops[i])
5536 N->OperandList[i].set(Ops[i]);
5538 // If this gets put into a CSE map, add it.
5539 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5543 /// DropOperands - Release the operands and set this node to have
5545 void SDNode::DropOperands() {
5546 // Unlike the code in MorphNodeTo that does this, we don't need to
5547 // watch for dead nodes here.
5548 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5554 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5557 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5559 SDVTList VTs = getVTList(VT);
5560 return SelectNodeTo(N, MachineOpc, VTs, None);
5563 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5564 EVT VT, SDValue Op1) {
5565 SDVTList VTs = getVTList(VT);
5566 SDValue Ops[] = { Op1 };
5567 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5570 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5571 EVT VT, SDValue Op1,
5573 SDVTList VTs = getVTList(VT);
5574 SDValue Ops[] = { Op1, Op2 };
5575 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5578 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5579 EVT VT, SDValue Op1,
5580 SDValue Op2, SDValue Op3) {
5581 SDVTList VTs = getVTList(VT);
5582 SDValue Ops[] = { Op1, Op2, Op3 };
5583 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5586 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5587 EVT VT, ArrayRef<SDValue> Ops) {
5588 SDVTList VTs = getVTList(VT);
5589 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5592 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5593 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5594 SDVTList VTs = getVTList(VT1, VT2);
5595 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5598 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5600 SDVTList VTs = getVTList(VT1, VT2);
5601 return SelectNodeTo(N, MachineOpc, VTs, None);
5604 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5605 EVT VT1, EVT VT2, EVT VT3,
5606 ArrayRef<SDValue> Ops) {
5607 SDVTList VTs = getVTList(VT1, VT2, VT3);
5608 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5611 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5612 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5613 ArrayRef<SDValue> Ops) {
5614 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5615 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5618 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5621 SDVTList VTs = getVTList(VT1, VT2);
5622 SDValue Ops[] = { Op1 };
5623 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5626 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5628 SDValue Op1, SDValue Op2) {
5629 SDVTList VTs = getVTList(VT1, VT2);
5630 SDValue Ops[] = { Op1, Op2 };
5631 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5634 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5636 SDValue Op1, SDValue Op2,
5638 SDVTList VTs = getVTList(VT1, VT2);
5639 SDValue Ops[] = { Op1, Op2, Op3 };
5640 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5643 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5644 EVT VT1, EVT VT2, EVT VT3,
5645 SDValue Op1, SDValue Op2,
5647 SDVTList VTs = getVTList(VT1, VT2, VT3);
5648 SDValue Ops[] = { Op1, Op2, Op3 };
5649 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5652 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5653 SDVTList VTs,ArrayRef<SDValue> Ops) {
5654 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5655 // Reset the NodeID to -1.
5660 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5661 /// the line number information on the merged node since it is not possible to
5662 /// preserve the information that operation is associated with multiple lines.
5663 /// This will make the debugger working better at -O0, were there is a higher
5664 /// probability having other instructions associated with that line.
5666 /// For IROrder, we keep the smaller of the two
5667 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5668 DebugLoc NLoc = N->getDebugLoc();
5669 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5670 N->setDebugLoc(DebugLoc());
5672 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5673 N->setIROrder(Order);
5677 /// MorphNodeTo - This *mutates* the specified node to have the specified
5678 /// return type, opcode, and operands.
5680 /// Note that MorphNodeTo returns the resultant node. If there is already a
5681 /// node of the specified opcode and operands, it returns that node instead of
5682 /// the current one. Note that the SDLoc need not be the same.
5684 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5685 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5686 /// node, and because it doesn't require CSE recalculation for any of
5687 /// the node's users.
5689 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5690 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5691 /// the legalizer which maintain worklists that would need to be updated when
5692 /// deleting things.
5693 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5694 SDVTList VTs, ArrayRef<SDValue> Ops) {
5695 unsigned NumOps = Ops.size();
5696 // If an identical node already exists, use it.
5698 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5699 FoldingSetNodeID ID;
5700 AddNodeIDNode(ID, Opc, VTs, Ops);
5701 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5702 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5705 if (!RemoveNodeFromCSEMaps(N))
5708 // Start the morphing.
5710 N->ValueList = VTs.VTs;
5711 N->NumValues = VTs.NumVTs;
5713 // Clear the operands list, updating used nodes to remove this from their
5714 // use list. Keep track of any operands that become dead as a result.
5715 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5716 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5718 SDNode *Used = Use.getNode();
5720 if (Used->use_empty())
5721 DeadNodeSet.insert(Used);
5724 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5725 // Initialize the memory references information.
5726 MN->setMemRefs(nullptr, nullptr);
5727 // If NumOps is larger than the # of operands we can have in a
5728 // MachineSDNode, reallocate the operand list.
5729 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5730 if (MN->OperandsNeedDelete)
5731 delete[] MN->OperandList;
5732 if (NumOps > array_lengthof(MN->LocalOperands))
5733 // We're creating a final node that will live unmorphed for the
5734 // remainder of the current SelectionDAG iteration, so we can allocate
5735 // the operands directly out of a pool with no recycling metadata.
5736 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5737 Ops.data(), NumOps);
5739 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5740 MN->OperandsNeedDelete = false;
5742 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5744 // If NumOps is larger than the # of operands we currently have, reallocate
5745 // the operand list.
5746 if (NumOps > N->NumOperands) {
5747 if (N->OperandsNeedDelete)
5748 delete[] N->OperandList;
5749 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5750 N->OperandsNeedDelete = true;
5752 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5755 // Delete any nodes that are still dead after adding the uses for the
5757 if (!DeadNodeSet.empty()) {
5758 SmallVector<SDNode *, 16> DeadNodes;
5759 for (SDNode *N : DeadNodeSet)
5761 DeadNodes.push_back(N);
5762 RemoveDeadNodes(DeadNodes);
5766 CSEMap.InsertNode(N, IP); // Memoize the new node.
5771 /// getMachineNode - These are used for target selectors to create a new node
5772 /// with specified return type(s), MachineInstr opcode, and operands.
5774 /// Note that getMachineNode returns the resultant node. If there is already a
5775 /// node of the specified opcode and operands, it returns that node instead of
5776 /// the current one.
5778 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5779 SDVTList VTs = getVTList(VT);
5780 return getMachineNode(Opcode, dl, VTs, None);
5784 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5785 SDVTList VTs = getVTList(VT);
5786 SDValue Ops[] = { Op1 };
5787 return getMachineNode(Opcode, dl, VTs, Ops);
5791 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5792 SDValue Op1, SDValue Op2) {
5793 SDVTList VTs = getVTList(VT);
5794 SDValue Ops[] = { Op1, Op2 };
5795 return getMachineNode(Opcode, dl, VTs, Ops);
5799 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5800 SDValue Op1, SDValue Op2, SDValue Op3) {
5801 SDVTList VTs = getVTList(VT);
5802 SDValue Ops[] = { Op1, Op2, Op3 };
5803 return getMachineNode(Opcode, dl, VTs, Ops);
5807 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5808 ArrayRef<SDValue> Ops) {
5809 SDVTList VTs = getVTList(VT);
5810 return getMachineNode(Opcode, dl, VTs, Ops);
5814 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5815 SDVTList VTs = getVTList(VT1, VT2);
5816 return getMachineNode(Opcode, dl, VTs, None);
5820 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5821 EVT VT1, EVT VT2, SDValue Op1) {
5822 SDVTList VTs = getVTList(VT1, VT2);
5823 SDValue Ops[] = { Op1 };
5824 return getMachineNode(Opcode, dl, VTs, Ops);
5828 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5829 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5830 SDVTList VTs = getVTList(VT1, VT2);
5831 SDValue Ops[] = { Op1, Op2 };
5832 return getMachineNode(Opcode, dl, VTs, Ops);
5836 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5837 EVT VT1, EVT VT2, SDValue Op1,
5838 SDValue Op2, SDValue Op3) {
5839 SDVTList VTs = getVTList(VT1, VT2);
5840 SDValue Ops[] = { Op1, Op2, Op3 };
5841 return getMachineNode(Opcode, dl, VTs, Ops);
5845 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5847 ArrayRef<SDValue> Ops) {
5848 SDVTList VTs = getVTList(VT1, VT2);
5849 return getMachineNode(Opcode, dl, VTs, Ops);
5853 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5854 EVT VT1, EVT VT2, EVT VT3,
5855 SDValue Op1, SDValue Op2) {
5856 SDVTList VTs = getVTList(VT1, VT2, VT3);
5857 SDValue Ops[] = { Op1, Op2 };
5858 return getMachineNode(Opcode, dl, VTs, Ops);
5862 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5863 EVT VT1, EVT VT2, EVT VT3,
5864 SDValue Op1, SDValue Op2, SDValue Op3) {
5865 SDVTList VTs = getVTList(VT1, VT2, VT3);
5866 SDValue Ops[] = { Op1, Op2, Op3 };
5867 return getMachineNode(Opcode, dl, VTs, Ops);
5871 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5872 EVT VT1, EVT VT2, EVT VT3,
5873 ArrayRef<SDValue> Ops) {
5874 SDVTList VTs = getVTList(VT1, VT2, VT3);
5875 return getMachineNode(Opcode, dl, VTs, Ops);
5879 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5880 EVT VT2, EVT VT3, EVT VT4,
5881 ArrayRef<SDValue> Ops) {
5882 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5883 return getMachineNode(Opcode, dl, VTs, Ops);
5887 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5888 ArrayRef<EVT> ResultTys,
5889 ArrayRef<SDValue> Ops) {
5890 SDVTList VTs = getVTList(ResultTys);
5891 return getMachineNode(Opcode, dl, VTs, Ops);
5895 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5896 ArrayRef<SDValue> OpsArray) {
5897 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5900 const SDValue *Ops = OpsArray.data();
5901 unsigned NumOps = OpsArray.size();
5904 FoldingSetNodeID ID;
5905 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5907 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5908 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5912 // Allocate a new MachineSDNode.
5913 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5914 DL.getDebugLoc(), VTs);
5916 // Initialize the operands list.
5917 if (NumOps > array_lengthof(N->LocalOperands))
5918 // We're creating a final node that will live unmorphed for the
5919 // remainder of the current SelectionDAG iteration, so we can allocate
5920 // the operands directly out of a pool with no recycling metadata.
5921 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5924 N->InitOperands(N->LocalOperands, Ops, NumOps);
5925 N->OperandsNeedDelete = false;
5928 CSEMap.InsertNode(N, IP);
5934 /// getTargetExtractSubreg - A convenience function for creating
5935 /// TargetOpcode::EXTRACT_SUBREG nodes.
5937 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5939 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5940 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5941 VT, Operand, SRIdxVal);
5942 return SDValue(Subreg, 0);
5945 /// getTargetInsertSubreg - A convenience function for creating
5946 /// TargetOpcode::INSERT_SUBREG nodes.
5948 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5949 SDValue Operand, SDValue Subreg) {
5950 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5951 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5952 VT, Operand, Subreg, SRIdxVal);
5953 return SDValue(Result, 0);
5956 /// getNodeIfExists - Get the specified node if it's already available, or
5957 /// else return NULL.
5958 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5959 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5961 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5962 FoldingSetNodeID ID;
5963 AddNodeIDNode(ID, Opcode, VTList, Ops);
5964 if (isBinOpWithFlags(Opcode))
5965 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5967 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5973 /// getDbgValue - Creates a SDDbgValue node.
5976 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5977 unsigned R, bool IsIndirect, uint64_t Off,
5978 DebugLoc DL, unsigned O) {
5979 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5980 "Expected inlined-at fields to agree");
5981 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5985 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5986 const Value *C, uint64_t Off,
5987 DebugLoc DL, unsigned O) {
5988 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5989 "Expected inlined-at fields to agree");
5990 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5994 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5995 unsigned FI, uint64_t Off,
5996 DebugLoc DL, unsigned O) {
5997 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5998 "Expected inlined-at fields to agree");
5999 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6004 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6005 /// pointed to by a use iterator is deleted, increment the use iterator
6006 /// so that it doesn't dangle.
6008 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6009 SDNode::use_iterator &UI;
6010 SDNode::use_iterator &UE;
6012 void NodeDeleted(SDNode *N, SDNode *E) override {
6013 // Increment the iterator as needed.
6014 while (UI != UE && N == *UI)
6019 RAUWUpdateListener(SelectionDAG &d,
6020 SDNode::use_iterator &ui,
6021 SDNode::use_iterator &ue)
6022 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6027 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6028 /// This can cause recursive merging of nodes in the DAG.
6030 /// This version assumes From has a single result value.
6032 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6033 SDNode *From = FromN.getNode();
6034 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6035 "Cannot replace with this method!");
6036 assert(From != To.getNode() && "Cannot replace uses of with self");
6038 // Iterate over all the existing uses of From. New uses will be added
6039 // to the beginning of the use list, which we avoid visiting.
6040 // This specifically avoids visiting uses of From that arise while the
6041 // replacement is happening, because any such uses would be the result
6042 // of CSE: If an existing node looks like From after one of its operands
6043 // is replaced by To, we don't want to replace of all its users with To
6044 // too. See PR3018 for more info.
6045 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6046 RAUWUpdateListener Listener(*this, UI, UE);
6050 // This node is about to morph, remove its old self from the CSE maps.
6051 RemoveNodeFromCSEMaps(User);
6053 // A user can appear in a use list multiple times, and when this
6054 // happens the uses are usually next to each other in the list.
6055 // To help reduce the number of CSE recomputations, process all
6056 // the uses of this user that we can find this way.
6058 SDUse &Use = UI.getUse();
6061 } while (UI != UE && *UI == User);
6063 // Now that we have modified User, add it back to the CSE maps. If it
6064 // already exists there, recursively merge the results together.
6065 AddModifiedNodeToCSEMaps(User);
6068 // If we just RAUW'd the root, take note.
6069 if (FromN == getRoot())
6073 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6074 /// This can cause recursive merging of nodes in the DAG.
6076 /// This version assumes that for each value of From, there is a
6077 /// corresponding value in To in the same position with the same type.
6079 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6081 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6082 assert((!From->hasAnyUseOfValue(i) ||
6083 From->getValueType(i) == To->getValueType(i)) &&
6084 "Cannot use this version of ReplaceAllUsesWith!");
6087 // Handle the trivial case.
6091 // Iterate over just the existing users of From. See the comments in
6092 // the ReplaceAllUsesWith above.
6093 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6094 RAUWUpdateListener Listener(*this, UI, UE);
6098 // This node is about to morph, remove its old self from the CSE maps.
6099 RemoveNodeFromCSEMaps(User);
6101 // A user can appear in a use list multiple times, and when this
6102 // happens the uses are usually next to each other in the list.
6103 // To help reduce the number of CSE recomputations, process all
6104 // the uses of this user that we can find this way.
6106 SDUse &Use = UI.getUse();
6109 } while (UI != UE && *UI == User);
6111 // Now that we have modified User, add it back to the CSE maps. If it
6112 // already exists there, recursively merge the results together.
6113 AddModifiedNodeToCSEMaps(User);
6116 // If we just RAUW'd the root, take note.
6117 if (From == getRoot().getNode())
6118 setRoot(SDValue(To, getRoot().getResNo()));
6121 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6122 /// This can cause recursive merging of nodes in the DAG.
6124 /// This version can replace From with any result values. To must match the
6125 /// number and types of values returned by From.
6126 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6127 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6128 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6130 // Iterate over just the existing users of From. See the comments in
6131 // the ReplaceAllUsesWith above.
6132 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6133 RAUWUpdateListener Listener(*this, UI, UE);
6137 // This node is about to morph, remove its old self from the CSE maps.
6138 RemoveNodeFromCSEMaps(User);
6140 // A user can appear in a use list multiple times, and when this
6141 // happens the uses are usually next to each other in the list.
6142 // To help reduce the number of CSE recomputations, process all
6143 // the uses of this user that we can find this way.
6145 SDUse &Use = UI.getUse();
6146 const SDValue &ToOp = To[Use.getResNo()];
6149 } while (UI != UE && *UI == User);
6151 // Now that we have modified User, add it back to the CSE maps. If it
6152 // already exists there, recursively merge the results together.
6153 AddModifiedNodeToCSEMaps(User);
6156 // If we just RAUW'd the root, take note.
6157 if (From == getRoot().getNode())
6158 setRoot(SDValue(To[getRoot().getResNo()]));
6161 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6162 /// uses of other values produced by From.getNode() alone. The Deleted
6163 /// vector is handled the same way as for ReplaceAllUsesWith.
6164 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6165 // Handle the really simple, really trivial case efficiently.
6166 if (From == To) return;
6168 // Handle the simple, trivial, case efficiently.
6169 if (From.getNode()->getNumValues() == 1) {
6170 ReplaceAllUsesWith(From, To);
6174 // Iterate over just the existing users of From. See the comments in
6175 // the ReplaceAllUsesWith above.
6176 SDNode::use_iterator UI = From.getNode()->use_begin(),
6177 UE = From.getNode()->use_end();
6178 RAUWUpdateListener Listener(*this, UI, UE);
6181 bool UserRemovedFromCSEMaps = false;
6183 // A user can appear in a use list multiple times, and when this
6184 // happens the uses are usually next to each other in the list.
6185 // To help reduce the number of CSE recomputations, process all
6186 // the uses of this user that we can find this way.
6188 SDUse &Use = UI.getUse();
6190 // Skip uses of different values from the same node.
6191 if (Use.getResNo() != From.getResNo()) {
6196 // If this node hasn't been modified yet, it's still in the CSE maps,
6197 // so remove its old self from the CSE maps.
6198 if (!UserRemovedFromCSEMaps) {
6199 RemoveNodeFromCSEMaps(User);
6200 UserRemovedFromCSEMaps = true;
6205 } while (UI != UE && *UI == User);
6207 // We are iterating over all uses of the From node, so if a use
6208 // doesn't use the specific value, no changes are made.
6209 if (!UserRemovedFromCSEMaps)
6212 // Now that we have modified User, add it back to the CSE maps. If it
6213 // already exists there, recursively merge the results together.
6214 AddModifiedNodeToCSEMaps(User);
6217 // If we just RAUW'd the root, take note.
6218 if (From == getRoot())
6223 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6224 /// to record information about a use.
6231 /// operator< - Sort Memos by User.
6232 bool operator<(const UseMemo &L, const UseMemo &R) {
6233 return (intptr_t)L.User < (intptr_t)R.User;
6237 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6238 /// uses of other values produced by From.getNode() alone. The same value
6239 /// may appear in both the From and To list. The Deleted vector is
6240 /// handled the same way as for ReplaceAllUsesWith.
6241 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6244 // Handle the simple, trivial case efficiently.
6246 return ReplaceAllUsesOfValueWith(*From, *To);
6248 // Read up all the uses and make records of them. This helps
6249 // processing new uses that are introduced during the
6250 // replacement process.
6251 SmallVector<UseMemo, 4> Uses;
6252 for (unsigned i = 0; i != Num; ++i) {
6253 unsigned FromResNo = From[i].getResNo();
6254 SDNode *FromNode = From[i].getNode();
6255 for (SDNode::use_iterator UI = FromNode->use_begin(),
6256 E = FromNode->use_end(); UI != E; ++UI) {
6257 SDUse &Use = UI.getUse();
6258 if (Use.getResNo() == FromResNo) {
6259 UseMemo Memo = { *UI, i, &Use };
6260 Uses.push_back(Memo);
6265 // Sort the uses, so that all the uses from a given User are together.
6266 std::sort(Uses.begin(), Uses.end());
6268 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6269 UseIndex != UseIndexEnd; ) {
6270 // We know that this user uses some value of From. If it is the right
6271 // value, update it.
6272 SDNode *User = Uses[UseIndex].User;
6274 // This node is about to morph, remove its old self from the CSE maps.
6275 RemoveNodeFromCSEMaps(User);
6277 // The Uses array is sorted, so all the uses for a given User
6278 // are next to each other in the list.
6279 // To help reduce the number of CSE recomputations, process all
6280 // the uses of this user that we can find this way.
6282 unsigned i = Uses[UseIndex].Index;
6283 SDUse &Use = *Uses[UseIndex].Use;
6287 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6289 // Now that we have modified User, add it back to the CSE maps. If it
6290 // already exists there, recursively merge the results together.
6291 AddModifiedNodeToCSEMaps(User);
6295 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6296 /// based on their topological order. It returns the maximum id and a vector
6297 /// of the SDNodes* in assigned order by reference.
6298 unsigned SelectionDAG::AssignTopologicalOrder() {
6300 unsigned DAGSize = 0;
6302 // SortedPos tracks the progress of the algorithm. Nodes before it are
6303 // sorted, nodes after it are unsorted. When the algorithm completes
6304 // it is at the end of the list.
6305 allnodes_iterator SortedPos = allnodes_begin();
6307 // Visit all the nodes. Move nodes with no operands to the front of
6308 // the list immediately. Annotate nodes that do have operands with their
6309 // operand count. Before we do this, the Node Id fields of the nodes
6310 // may contain arbitrary values. After, the Node Id fields for nodes
6311 // before SortedPos will contain the topological sort index, and the
6312 // Node Id fields for nodes At SortedPos and after will contain the
6313 // count of outstanding operands.
6314 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6316 checkForCycles(N, this);
6317 unsigned Degree = N->getNumOperands();
6319 // A node with no uses, add it to the result array immediately.
6320 N->setNodeId(DAGSize++);
6321 allnodes_iterator Q = N;
6323 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6324 assert(SortedPos != AllNodes.end() && "Overran node list");
6327 // Temporarily use the Node Id as scratch space for the degree count.
6328 N->setNodeId(Degree);
6332 // Visit all the nodes. As we iterate, move nodes into sorted order,
6333 // such that by the time the end is reached all nodes will be sorted.
6334 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6336 checkForCycles(N, this);
6337 // N is in sorted position, so all its uses have one less operand
6338 // that needs to be sorted.
6339 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6342 unsigned Degree = P->getNodeId();
6343 assert(Degree != 0 && "Invalid node degree");
6346 // All of P's operands are sorted, so P may sorted now.
6347 P->setNodeId(DAGSize++);
6349 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6350 assert(SortedPos != AllNodes.end() && "Overran node list");
6353 // Update P's outstanding operand count.
6354 P->setNodeId(Degree);
6357 if (I == SortedPos) {
6360 dbgs() << "Overran sorted position:\n";
6361 S->dumprFull(this); dbgs() << "\n";
6362 dbgs() << "Checking if this is due to cycles\n";
6363 checkForCycles(this, true);
6365 llvm_unreachable(nullptr);
6369 assert(SortedPos == AllNodes.end() &&
6370 "Topological sort incomplete!");
6371 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6372 "First node in topological sort is not the entry token!");
6373 assert(AllNodes.front().getNodeId() == 0 &&
6374 "First node in topological sort has non-zero id!");
6375 assert(AllNodes.front().getNumOperands() == 0 &&
6376 "First node in topological sort has operands!");
6377 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6378 "Last node in topologic sort has unexpected id!");
6379 assert(AllNodes.back().use_empty() &&
6380 "Last node in topologic sort has users!");
6381 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6385 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6386 /// value is produced by SD.
6387 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6389 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6390 SD->setHasDebugValue(true);
6392 DbgInfo->add(DB, SD, isParameter);
6395 /// TransferDbgValues - Transfer SDDbgValues.
6396 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6397 if (From == To || !From.getNode()->getHasDebugValue())
6399 SDNode *FromNode = From.getNode();
6400 SDNode *ToNode = To.getNode();
6401 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6402 SmallVector<SDDbgValue *, 2> ClonedDVs;
6403 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6405 SDDbgValue *Dbg = *I;
6406 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6408 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6409 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6410 Dbg->getDebugLoc(), Dbg->getOrder());
6411 ClonedDVs.push_back(Clone);
6414 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6415 E = ClonedDVs.end(); I != E; ++I)
6416 AddDbgValue(*I, ToNode, false);
6419 //===----------------------------------------------------------------------===//
6421 //===----------------------------------------------------------------------===//
6423 HandleSDNode::~HandleSDNode() {
6427 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6428 DebugLoc DL, const GlobalValue *GA,
6429 EVT VT, int64_t o, unsigned char TF)
6430 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6434 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6435 SDValue X, unsigned SrcAS,
6437 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6438 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6440 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6441 EVT memvt, MachineMemOperand *mmo)
6442 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6443 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6444 MMO->isNonTemporal(), MMO->isInvariant());
6445 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6446 assert(isNonTemporal() == MMO->isNonTemporal() &&
6447 "Non-temporal encoding error!");
6448 // We check here that the size of the memory operand fits within the size of
6449 // the MMO. This is because the MMO might indicate only a possible address
6450 // range instead of specifying the affected memory addresses precisely.
6451 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6454 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6455 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6456 : SDNode(Opc, Order, dl, VTs, Ops),
6457 MemoryVT(memvt), MMO(mmo) {
6458 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6459 MMO->isNonTemporal(), MMO->isInvariant());
6460 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6461 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6464 /// Profile - Gather unique data for the node.
6466 void SDNode::Profile(FoldingSetNodeID &ID) const {
6467 AddNodeIDNode(ID, this);
6472 std::vector<EVT> VTs;
6475 VTs.reserve(MVT::LAST_VALUETYPE);
6476 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6477 VTs.push_back(MVT((MVT::SimpleValueType)i));
6482 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6483 static ManagedStatic<EVTArray> SimpleVTArray;
6484 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6486 /// getValueTypeList - Return a pointer to the specified value type.
6488 const EVT *SDNode::getValueTypeList(EVT VT) {
6489 if (VT.isExtended()) {
6490 sys::SmartScopedLock<true> Lock(*VTMutex);
6491 return &(*EVTs->insert(VT).first);
6493 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6494 "Value type out of range!");
6495 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6499 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6500 /// indicated value. This method ignores uses of other values defined by this
6502 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6503 assert(Value < getNumValues() && "Bad value!");
6505 // TODO: Only iterate over uses of a given value of the node
6506 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6507 if (UI.getUse().getResNo() == Value) {
6514 // Found exactly the right number of uses?
6519 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6520 /// value. This method ignores uses of other values defined by this operation.
6521 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6522 assert(Value < getNumValues() && "Bad value!");
6524 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6525 if (UI.getUse().getResNo() == Value)
6532 /// isOnlyUserOf - Return true if this node is the only use of N.
6534 bool SDNode::isOnlyUserOf(SDNode *N) const {
6536 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6547 /// isOperand - Return true if this node is an operand of N.
6549 bool SDValue::isOperandOf(SDNode *N) const {
6550 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6551 if (*this == N->getOperand(i))
6556 bool SDNode::isOperandOf(SDNode *N) const {
6557 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6558 if (this == N->OperandList[i].getNode())
6563 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6564 /// be a chain) reaches the specified operand without crossing any
6565 /// side-effecting instructions on any chain path. In practice, this looks
6566 /// through token factors and non-volatile loads. In order to remain efficient,
6567 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6568 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6569 unsigned Depth) const {
6570 if (*this == Dest) return true;
6572 // Don't search too deeply, we just want to be able to see through
6573 // TokenFactor's etc.
6574 if (Depth == 0) return false;
6576 // If this is a token factor, all inputs to the TF happen in parallel. If any
6577 // of the operands of the TF does not reach dest, then we cannot do the xform.
6578 if (getOpcode() == ISD::TokenFactor) {
6579 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6580 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6585 // Loads don't have side effects, look through them.
6586 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6587 if (!Ld->isVolatile())
6588 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6593 /// hasPredecessor - Return true if N is a predecessor of this node.
6594 /// N is either an operand of this node, or can be reached by recursively
6595 /// traversing up the operands.
6596 /// NOTE: This is an expensive method. Use it carefully.
6597 bool SDNode::hasPredecessor(const SDNode *N) const {
6598 SmallPtrSet<const SDNode *, 32> Visited;
6599 SmallVector<const SDNode *, 16> Worklist;
6600 return hasPredecessorHelper(N, Visited, Worklist);
6604 SDNode::hasPredecessorHelper(const SDNode *N,
6605 SmallPtrSetImpl<const SDNode *> &Visited,
6606 SmallVectorImpl<const SDNode *> &Worklist) const {
6607 if (Visited.empty()) {
6608 Worklist.push_back(this);
6610 // Take a look in the visited set. If we've already encountered this node
6611 // we needn't search further.
6612 if (Visited.count(N))
6616 // Haven't visited N yet. Continue the search.
6617 while (!Worklist.empty()) {
6618 const SDNode *M = Worklist.pop_back_val();
6619 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6620 SDNode *Op = M->getOperand(i).getNode();
6621 if (Visited.insert(Op).second)
6622 Worklist.push_back(Op);
6631 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6632 assert(Num < NumOperands && "Invalid child # of SDNode!");
6633 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6636 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6637 assert(N->getNumValues() == 1 &&
6638 "Can't unroll a vector with multiple results!");
6640 EVT VT = N->getValueType(0);
6641 unsigned NE = VT.getVectorNumElements();
6642 EVT EltVT = VT.getVectorElementType();
6645 SmallVector<SDValue, 8> Scalars;
6646 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6648 // If ResNE is 0, fully unroll the vector op.
6651 else if (NE > ResNE)
6655 for (i= 0; i != NE; ++i) {
6656 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6657 SDValue Operand = N->getOperand(j);
6658 EVT OperandVT = Operand.getValueType();
6659 if (OperandVT.isVector()) {
6660 // A vector operand; extract a single element.
6661 EVT OperandEltVT = OperandVT.getVectorElementType();
6662 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6665 getConstant(i, dl, TLI->getVectorIdxTy()));
6667 // A scalar operand; just use it as is.
6668 Operands[j] = Operand;
6672 switch (N->getOpcode()) {
6674 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6677 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6684 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6685 getShiftAmountOperand(Operands[0].getValueType(),
6688 case ISD::SIGN_EXTEND_INREG:
6689 case ISD::FP_ROUND_INREG: {
6690 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6691 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6693 getValueType(ExtVT)));
6698 for (; i < ResNE; ++i)
6699 Scalars.push_back(getUNDEF(EltVT));
6701 return getNode(ISD::BUILD_VECTOR, dl,
6702 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6706 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6707 /// location that is 'Dist' units away from the location that the 'Base' load
6708 /// is loading from.
6709 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6710 unsigned Bytes, int Dist) const {
6711 if (LD->getChain() != Base->getChain())
6713 EVT VT = LD->getValueType(0);
6714 if (VT.getSizeInBits() / 8 != Bytes)
6717 SDValue Loc = LD->getOperand(1);
6718 SDValue BaseLoc = Base->getOperand(1);
6719 if (Loc.getOpcode() == ISD::FrameIndex) {
6720 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6722 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6723 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6724 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6725 int FS = MFI->getObjectSize(FI);
6726 int BFS = MFI->getObjectSize(BFI);
6727 if (FS != BFS || FS != (int)Bytes) return false;
6728 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6732 if (isBaseWithConstantOffset(Loc)) {
6733 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6734 if (Loc.getOperand(0) == BaseLoc) {
6735 // If the base location is a simple address with no offset itself, then
6736 // the second load's first add operand should be the base address.
6737 if (LocOffset == Dist * (int)Bytes)
6739 } else if (isBaseWithConstantOffset(BaseLoc)) {
6740 // The base location itself has an offset, so subtract that value from the
6741 // second load's offset before comparing to distance * size.
6743 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6744 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6745 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6750 const GlobalValue *GV1 = nullptr;
6751 const GlobalValue *GV2 = nullptr;
6752 int64_t Offset1 = 0;
6753 int64_t Offset2 = 0;
6754 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6755 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6756 if (isGA1 && isGA2 && GV1 == GV2)
6757 return Offset1 == (Offset2 + Dist*Bytes);
6762 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6763 /// it cannot be inferred.
6764 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6765 // If this is a GlobalAddress + cst, return the alignment.
6766 const GlobalValue *GV;
6767 int64_t GVOffset = 0;
6768 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6769 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6770 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6771 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6772 *TLI->getDataLayout());
6773 unsigned AlignBits = KnownZero.countTrailingOnes();
6774 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6776 return MinAlign(Align, GVOffset);
6779 // If this is a direct reference to a stack slot, use information about the
6780 // stack slot's alignment.
6781 int FrameIdx = 1 << 31;
6782 int64_t FrameOffset = 0;
6783 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6784 FrameIdx = FI->getIndex();
6785 } else if (isBaseWithConstantOffset(Ptr) &&
6786 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6788 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6789 FrameOffset = Ptr.getConstantOperandVal(1);
6792 if (FrameIdx != (1 << 31)) {
6793 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6794 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6802 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6803 /// which is split (or expanded) into two not necessarily identical pieces.
6804 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6805 // Currently all types are split in half.
6807 if (!VT.isVector()) {
6808 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6810 unsigned NumElements = VT.getVectorNumElements();
6811 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6812 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6815 return std::make_pair(LoVT, HiVT);
6818 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6820 std::pair<SDValue, SDValue>
6821 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6823 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6824 N.getValueType().getVectorNumElements() &&
6825 "More vector elements requested than available!");
6827 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6828 getConstant(0, DL, TLI->getVectorIdxTy()));
6829 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6830 getConstant(LoVT.getVectorNumElements(), DL,
6831 TLI->getVectorIdxTy()));
6832 return std::make_pair(Lo, Hi);
6835 void SelectionDAG::ExtractVectorElements(SDValue Op,
6836 SmallVectorImpl<SDValue> &Args,
6837 unsigned Start, unsigned Count) {
6838 EVT VT = Op.getValueType();
6840 Count = VT.getVectorNumElements();
6842 EVT EltVT = VT.getVectorElementType();
6843 EVT IdxTy = TLI->getVectorIdxTy();
6845 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6846 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6847 Op, getConstant(i, SL, IdxTy)));
6851 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6852 unsigned GlobalAddressSDNode::getAddressSpace() const {
6853 return getGlobal()->getType()->getAddressSpace();
6857 Type *ConstantPoolSDNode::getType() const {
6858 if (isMachineConstantPoolEntry())
6859 return Val.MachineCPVal->getType();
6860 return Val.ConstVal->getType();
6863 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6865 unsigned &SplatBitSize,
6867 unsigned MinSplatBits,
6868 bool isBigEndian) const {
6869 EVT VT = getValueType(0);
6870 assert(VT.isVector() && "Expected a vector type");
6871 unsigned sz = VT.getSizeInBits();
6872 if (MinSplatBits > sz)
6875 SplatValue = APInt(sz, 0);
6876 SplatUndef = APInt(sz, 0);
6878 // Get the bits. Bits with undefined values (when the corresponding element
6879 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6880 // in SplatValue. If any of the values are not constant, give up and return
6882 unsigned int nOps = getNumOperands();
6883 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6884 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6886 for (unsigned j = 0; j < nOps; ++j) {
6887 unsigned i = isBigEndian ? nOps-1-j : j;
6888 SDValue OpVal = getOperand(i);
6889 unsigned BitPos = j * EltBitSize;
6891 if (OpVal.getOpcode() == ISD::UNDEF)
6892 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6893 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6894 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6895 zextOrTrunc(sz) << BitPos;
6896 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6897 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6902 // The build_vector is all constants or undefs. Find the smallest element
6903 // size that splats the vector.
6905 HasAnyUndefs = (SplatUndef != 0);
6908 unsigned HalfSize = sz / 2;
6909 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6910 APInt LowValue = SplatValue.trunc(HalfSize);
6911 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6912 APInt LowUndef = SplatUndef.trunc(HalfSize);
6914 // If the two halves do not match (ignoring undef bits), stop here.
6915 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6916 MinSplatBits > HalfSize)
6919 SplatValue = HighValue | LowValue;
6920 SplatUndef = HighUndef & LowUndef;
6929 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6930 if (UndefElements) {
6931 UndefElements->clear();
6932 UndefElements->resize(getNumOperands());
6935 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6936 SDValue Op = getOperand(i);
6937 if (Op.getOpcode() == ISD::UNDEF) {
6939 (*UndefElements)[i] = true;
6940 } else if (!Splatted) {
6942 } else if (Splatted != Op) {
6948 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6949 "Can only have a splat without a constant for all undefs.");
6950 return getOperand(0);
6957 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6958 return dyn_cast_or_null<ConstantSDNode>(
6959 getSplatValue(UndefElements).getNode());
6963 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6964 return dyn_cast_or_null<ConstantFPSDNode>(
6965 getSplatValue(UndefElements).getNode());
6968 bool BuildVectorSDNode::isConstant() const {
6969 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6970 unsigned Opc = getOperand(i).getOpcode();
6971 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6977 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6978 // Find the first non-undef value in the shuffle mask.
6980 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6983 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6985 // Make sure all remaining elements are either undef or the same as the first
6987 for (int Idx = Mask[i]; i != e; ++i)
6988 if (Mask[i] >= 0 && Mask[i] != Idx)
6994 static void checkForCyclesHelper(const SDNode *N,
6995 SmallPtrSetImpl<const SDNode*> &Visited,
6996 SmallPtrSetImpl<const SDNode*> &Checked,
6997 const llvm::SelectionDAG *DAG) {
6998 // If this node has already been checked, don't check it again.
6999 if (Checked.count(N))
7002 // If a node has already been visited on this depth-first walk, reject it as
7004 if (!Visited.insert(N).second) {
7005 errs() << "Detected cycle in SelectionDAG\n";
7006 dbgs() << "Offending node:\n";
7007 N->dumprFull(DAG); dbgs() << "\n";
7011 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7012 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7019 void llvm::checkForCycles(const llvm::SDNode *N,
7020 const llvm::SelectionDAG *DAG,
7028 assert(N && "Checking nonexistent SDNode");
7029 SmallPtrSet<const SDNode*, 32> visited;
7030 SmallPtrSet<const SDNode*, 32> checked;
7031 checkForCyclesHelper(N, visited, checked, DAG);
7036 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7037 checkForCycles(DAG->getRoot().getNode(), DAG, force);