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, 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()), 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, VT);
1083 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1084 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1088 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1091 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1092 EVT EltVT = VT.getScalarType();
1093 assert((EltVT.getSizeInBits() >= 64 ||
1094 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1095 "getConstant with a uint64_t value that doesn't fit in the type!");
1096 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1099 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1101 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1104 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1106 assert(VT.isInteger() && "Cannot create FP integer constant!");
1108 EVT EltVT = VT.getScalarType();
1109 const ConstantInt *Elt = &Val;
1111 // In some cases the vector type is legal but the element type is illegal and
1112 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1113 // inserted value (the type does not need to match the vector element type).
1114 // Any extra bits introduced will be truncated away.
1115 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1116 TargetLowering::TypePromoteInteger) {
1117 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1118 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1119 Elt = ConstantInt::get(*getContext(), NewVal);
1121 // In other cases the element type is illegal and needs to be expanded, for
1122 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1123 // the value into n parts and use a vector type with n-times the elements.
1124 // Then bitcast to the type requested.
1125 // Legalizing constants too early makes the DAGCombiner's job harder so we
1126 // only legalize if the DAG tells us we must produce legal types.
1127 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1128 TLI->getTypeAction(*getContext(), EltVT) ==
1129 TargetLowering::TypeExpandInteger) {
1130 APInt NewVal = Elt->getValue();
1131 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1132 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1133 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1134 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1136 // Check the temporary vector is the correct size. If this fails then
1137 // getTypeToTransformTo() probably returned a type whose size (in bits)
1138 // isn't a power-of-2 factor of the requested type size.
1139 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1141 SmallVector<SDValue, 2> EltParts;
1142 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1143 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1144 .trunc(ViaEltSizeInBits),
1145 ViaEltVT, isT, isO));
1148 // EltParts is currently in little endian order. If we actually want
1149 // big-endian order then reverse it now.
1150 if (TLI->isBigEndian())
1151 std::reverse(EltParts.begin(), EltParts.end());
1153 // The elements must be reversed when the element order is different
1154 // to the endianness of the elements (because the BITCAST is itself a
1155 // vector shuffle in this situation). However, we do not need any code to
1156 // perform this reversal because getConstant() is producing a vector
1158 // This situation occurs in MIPS MSA.
1160 SmallVector<SDValue, 8> Ops;
1161 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1162 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1164 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1165 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1170 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1171 "APInt size does not match type size!");
1172 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1173 FoldingSetNodeID ID;
1174 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1178 SDNode *N = nullptr;
1179 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1181 return SDValue(N, 0);
1184 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1185 CSEMap.InsertNode(N, IP);
1189 SDValue Result(N, 0);
1190 if (VT.isVector()) {
1191 SmallVector<SDValue, 8> Ops;
1192 Ops.assign(VT.getVectorNumElements(), Result);
1193 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1198 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1199 return getConstant(Val, TLI->getPointerTy(), isTarget);
1203 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1204 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1207 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1208 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1210 EVT EltVT = VT.getScalarType();
1212 // Do the map lookup using the actual bit pattern for the floating point
1213 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1214 // we don't have issues with SNANs.
1215 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1216 FoldingSetNodeID ID;
1217 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1220 SDNode *N = nullptr;
1221 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1223 return SDValue(N, 0);
1226 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1227 CSEMap.InsertNode(N, IP);
1231 SDValue Result(N, 0);
1232 if (VT.isVector()) {
1233 SmallVector<SDValue, 8> Ops;
1234 Ops.assign(VT.getVectorNumElements(), Result);
1235 // FIXME SDLoc info might be appropriate here
1236 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1241 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1242 EVT EltVT = VT.getScalarType();
1243 if (EltVT==MVT::f32)
1244 return getConstantFP(APFloat((float)Val), VT, isTarget);
1245 else if (EltVT==MVT::f64)
1246 return getConstantFP(APFloat(Val), VT, isTarget);
1247 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1250 APFloat apf = APFloat(Val);
1251 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1253 return getConstantFP(apf, VT, isTarget);
1255 llvm_unreachable("Unsupported type in getConstantFP");
1258 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1259 EVT VT, int64_t Offset,
1261 unsigned char TargetFlags) {
1262 assert((TargetFlags == 0 || isTargetGA) &&
1263 "Cannot set target flags on target-independent globals");
1265 // Truncate (with sign-extension) the offset value to the pointer size.
1266 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1268 Offset = SignExtend64(Offset, BitWidth);
1271 if (GV->isThreadLocal())
1272 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1274 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1276 FoldingSetNodeID ID;
1277 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1279 ID.AddInteger(Offset);
1280 ID.AddInteger(TargetFlags);
1281 ID.AddInteger(GV->getType()->getAddressSpace());
1283 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1284 return SDValue(E, 0);
1286 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1287 DL.getDebugLoc(), GV, VT,
1288 Offset, TargetFlags);
1289 CSEMap.InsertNode(N, IP);
1291 return SDValue(N, 0);
1294 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1295 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1296 FoldingSetNodeID ID;
1297 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1300 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1301 return SDValue(E, 0);
1303 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1304 CSEMap.InsertNode(N, IP);
1306 return SDValue(N, 0);
1309 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1310 unsigned char TargetFlags) {
1311 assert((TargetFlags == 0 || isTarget) &&
1312 "Cannot set target flags on target-independent jump tables");
1313 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1314 FoldingSetNodeID ID;
1315 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1317 ID.AddInteger(TargetFlags);
1319 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1320 return SDValue(E, 0);
1322 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1324 CSEMap.InsertNode(N, IP);
1326 return SDValue(N, 0);
1329 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1330 unsigned Alignment, int Offset,
1332 unsigned char TargetFlags) {
1333 assert((TargetFlags == 0 || isTarget) &&
1334 "Cannot set target flags on target-independent globals");
1336 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1337 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1338 FoldingSetNodeID ID;
1339 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1340 ID.AddInteger(Alignment);
1341 ID.AddInteger(Offset);
1343 ID.AddInteger(TargetFlags);
1345 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1346 return SDValue(E, 0);
1348 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1349 Alignment, TargetFlags);
1350 CSEMap.InsertNode(N, IP);
1352 return SDValue(N, 0);
1356 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1357 unsigned Alignment, int Offset,
1359 unsigned char TargetFlags) {
1360 assert((TargetFlags == 0 || isTarget) &&
1361 "Cannot set target flags on target-independent globals");
1363 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1364 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1365 FoldingSetNodeID ID;
1366 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1367 ID.AddInteger(Alignment);
1368 ID.AddInteger(Offset);
1369 C->addSelectionDAGCSEId(ID);
1370 ID.AddInteger(TargetFlags);
1372 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1373 return SDValue(E, 0);
1375 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1376 Alignment, TargetFlags);
1377 CSEMap.InsertNode(N, IP);
1379 return SDValue(N, 0);
1382 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1383 unsigned char TargetFlags) {
1384 FoldingSetNodeID ID;
1385 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1386 ID.AddInteger(Index);
1387 ID.AddInteger(Offset);
1388 ID.AddInteger(TargetFlags);
1390 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1391 return SDValue(E, 0);
1393 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1395 CSEMap.InsertNode(N, IP);
1397 return SDValue(N, 0);
1400 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1401 FoldingSetNodeID ID;
1402 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1405 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1406 return SDValue(E, 0);
1408 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1409 CSEMap.InsertNode(N, IP);
1411 return SDValue(N, 0);
1414 SDValue SelectionDAG::getValueType(EVT VT) {
1415 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1416 ValueTypeNodes.size())
1417 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1419 SDNode *&N = VT.isExtended() ?
1420 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1422 if (N) return SDValue(N, 0);
1423 N = new (NodeAllocator) VTSDNode(VT);
1425 return SDValue(N, 0);
1428 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1429 SDNode *&N = ExternalSymbols[Sym];
1430 if (N) return SDValue(N, 0);
1431 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1433 return SDValue(N, 0);
1436 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1437 unsigned char TargetFlags) {
1439 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1441 if (N) return SDValue(N, 0);
1442 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1444 return SDValue(N, 0);
1447 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1448 if ((unsigned)Cond >= CondCodeNodes.size())
1449 CondCodeNodes.resize(Cond+1);
1451 if (!CondCodeNodes[Cond]) {
1452 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1453 CondCodeNodes[Cond] = N;
1457 return SDValue(CondCodeNodes[Cond], 0);
1460 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1461 // the shuffle mask M that point at N1 to point at N2, and indices that point
1462 // N2 to point at N1.
1463 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1465 ShuffleVectorSDNode::commuteMask(M);
1468 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1469 SDValue N2, const int *Mask) {
1470 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1471 "Invalid VECTOR_SHUFFLE");
1473 // Canonicalize shuffle undef, undef -> undef
1474 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1475 return getUNDEF(VT);
1477 // Validate that all indices in Mask are within the range of the elements
1478 // input to the shuffle.
1479 unsigned NElts = VT.getVectorNumElements();
1480 SmallVector<int, 8> MaskVec;
1481 for (unsigned i = 0; i != NElts; ++i) {
1482 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1483 MaskVec.push_back(Mask[i]);
1486 // Canonicalize shuffle v, v -> v, undef
1489 for (unsigned i = 0; i != NElts; ++i)
1490 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1493 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1494 if (N1.getOpcode() == ISD::UNDEF)
1495 commuteShuffle(N1, N2, MaskVec);
1497 // If shuffling a splat, try to blend the splat instead. We do this here so
1498 // that even when this arises during lowering we don't have to re-handle it.
1499 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1500 BitVector UndefElements;
1501 SDValue Splat = BV->getSplatValue(&UndefElements);
1505 for (int i = 0; i < (int)NElts; ++i) {
1506 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1509 // If this input comes from undef, mark it as such.
1510 if (UndefElements[MaskVec[i] - Offset]) {
1515 // If we can blend a non-undef lane, use that instead.
1516 if (!UndefElements[i])
1517 MaskVec[i] = i + Offset;
1520 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1521 BlendSplat(N1BV, 0);
1522 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1523 BlendSplat(N2BV, NElts);
1525 // Canonicalize all index into lhs, -> shuffle lhs, undef
1526 // Canonicalize all index into rhs, -> shuffle rhs, undef
1527 bool AllLHS = true, AllRHS = true;
1528 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1529 for (unsigned i = 0; i != NElts; ++i) {
1530 if (MaskVec[i] >= (int)NElts) {
1535 } else if (MaskVec[i] >= 0) {
1539 if (AllLHS && AllRHS)
1540 return getUNDEF(VT);
1541 if (AllLHS && !N2Undef)
1545 commuteShuffle(N1, N2, MaskVec);
1547 // Reset our undef status after accounting for the mask.
1548 N2Undef = N2.getOpcode() == ISD::UNDEF;
1549 // Re-check whether both sides ended up undef.
1550 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1551 return getUNDEF(VT);
1553 // If Identity shuffle return that node.
1554 bool Identity = true, AllSame = true;
1555 for (unsigned i = 0; i != NElts; ++i) {
1556 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1557 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1559 if (Identity && NElts)
1562 // Shuffling a constant splat doesn't change the result.
1566 // Look through any bitcasts. We check that these don't change the number
1567 // (and size) of elements and just changes their types.
1568 while (V.getOpcode() == ISD::BITCAST)
1569 V = V->getOperand(0);
1571 // A splat should always show up as a build vector node.
1572 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1573 BitVector UndefElements;
1574 SDValue Splat = BV->getSplatValue(&UndefElements);
1575 // If this is a splat of an undef, shuffling it is also undef.
1576 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1577 return getUNDEF(VT);
1580 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1582 // We only have a splat which can skip shuffles if there is a splatted
1583 // value and no undef lanes rearranged by the shuffle.
1584 if (Splat && UndefElements.none()) {
1585 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1586 // number of elements match or the value splatted is a zero constant.
1589 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1590 if (C->isNullValue())
1594 // If the shuffle itself creates a splat, build the vector directly.
1595 if (AllSame && SameNumElts) {
1596 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1597 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1599 EVT BuildVT = BV->getValueType(0);
1600 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1602 // We may have jumped through bitcasts, so the type of the
1603 // BUILD_VECTOR may not match the type of the shuffle.
1605 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1611 FoldingSetNodeID ID;
1612 SDValue Ops[2] = { N1, N2 };
1613 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1614 for (unsigned i = 0; i != NElts; ++i)
1615 ID.AddInteger(MaskVec[i]);
1618 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1619 return SDValue(E, 0);
1621 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1622 // SDNode doesn't have access to it. This memory will be "leaked" when
1623 // the node is deallocated, but recovered when the NodeAllocator is released.
1624 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1625 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1627 ShuffleVectorSDNode *N =
1628 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1629 dl.getDebugLoc(), N1, N2,
1631 CSEMap.InsertNode(N, IP);
1633 return SDValue(N, 0);
1636 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1637 MVT VT = SV.getSimpleValueType(0);
1638 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1639 ShuffleVectorSDNode::commuteMask(MaskVec);
1641 SDValue Op0 = SV.getOperand(0);
1642 SDValue Op1 = SV.getOperand(1);
1643 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1646 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1647 SDValue Val, SDValue DTy,
1648 SDValue STy, SDValue Rnd, SDValue Sat,
1649 ISD::CvtCode Code) {
1650 // If the src and dest types are the same and the conversion is between
1651 // integer types of the same sign or two floats, no conversion is necessary.
1653 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1656 FoldingSetNodeID ID;
1657 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1658 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661 return SDValue(E, 0);
1663 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1666 CSEMap.InsertNode(N, IP);
1668 return SDValue(N, 0);
1671 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1672 FoldingSetNodeID ID;
1673 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1674 ID.AddInteger(RegNo);
1676 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1677 return SDValue(E, 0);
1679 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1680 CSEMap.InsertNode(N, IP);
1682 return SDValue(N, 0);
1685 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1686 FoldingSetNodeID ID;
1687 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1688 ID.AddPointer(RegMask);
1690 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1691 return SDValue(E, 0);
1693 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1694 CSEMap.InsertNode(N, IP);
1696 return SDValue(N, 0);
1699 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1700 FoldingSetNodeID ID;
1701 SDValue Ops[] = { Root };
1702 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1703 ID.AddPointer(Label);
1705 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1706 return SDValue(E, 0);
1708 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1709 dl.getDebugLoc(), Root, Label);
1710 CSEMap.InsertNode(N, IP);
1712 return SDValue(N, 0);
1716 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1719 unsigned char TargetFlags) {
1720 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1722 FoldingSetNodeID ID;
1723 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1725 ID.AddInteger(Offset);
1726 ID.AddInteger(TargetFlags);
1728 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1729 return SDValue(E, 0);
1731 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1733 CSEMap.InsertNode(N, IP);
1735 return SDValue(N, 0);
1738 SDValue SelectionDAG::getSrcValue(const Value *V) {
1739 assert((!V || V->getType()->isPointerTy()) &&
1740 "SrcValue is not a pointer?");
1742 FoldingSetNodeID ID;
1743 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1747 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1748 return SDValue(E, 0);
1750 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1751 CSEMap.InsertNode(N, IP);
1753 return SDValue(N, 0);
1756 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1757 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1758 FoldingSetNodeID ID;
1759 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1763 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1764 return SDValue(E, 0);
1766 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1767 CSEMap.InsertNode(N, IP);
1769 return SDValue(N, 0);
1772 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1773 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1774 unsigned SrcAS, unsigned DestAS) {
1775 SDValue Ops[] = {Ptr};
1776 FoldingSetNodeID ID;
1777 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1778 ID.AddInteger(SrcAS);
1779 ID.AddInteger(DestAS);
1782 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1783 return SDValue(E, 0);
1785 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1787 VT, Ptr, SrcAS, DestAS);
1788 CSEMap.InsertNode(N, IP);
1790 return SDValue(N, 0);
1793 /// getShiftAmountOperand - Return the specified value casted to
1794 /// the target's desired shift amount type.
1795 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1796 EVT OpTy = Op.getValueType();
1797 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1798 if (OpTy == ShTy || OpTy.isVector()) return Op;
1800 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1801 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1804 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1805 /// specified value type.
1806 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1807 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1808 unsigned ByteSize = VT.getStoreSize();
1809 Type *Ty = VT.getTypeForEVT(*getContext());
1810 unsigned StackAlign =
1811 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1813 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1814 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1817 /// CreateStackTemporary - Create a stack temporary suitable for holding
1818 /// either of the specified value types.
1819 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1820 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1821 VT2.getStoreSizeInBits())/8;
1822 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1823 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1824 const DataLayout *TD = TLI->getDataLayout();
1825 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1826 TD->getPrefTypeAlignment(Ty2));
1828 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1829 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1830 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1833 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1834 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1835 // These setcc operations always fold.
1839 case ISD::SETFALSE2: return getConstant(0, VT);
1841 case ISD::SETTRUE2: {
1842 TargetLowering::BooleanContent Cnt =
1843 TLI->getBooleanContents(N1->getValueType(0));
1845 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1858 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1862 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1863 const APInt &C2 = N2C->getAPIntValue();
1864 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1865 const APInt &C1 = N1C->getAPIntValue();
1868 default: llvm_unreachable("Unknown integer setcc!");
1869 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1870 case ISD::SETNE: return getConstant(C1 != C2, VT);
1871 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1872 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1873 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1874 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1875 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1876 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1877 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1878 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1882 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1883 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1884 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1887 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1888 return getUNDEF(VT);
1890 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1891 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1892 return getUNDEF(VT);
1894 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1895 R==APFloat::cmpLessThan, VT);
1896 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1897 return getUNDEF(VT);
1899 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1900 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1901 return getUNDEF(VT);
1903 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1904 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1905 return getUNDEF(VT);
1907 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1908 R==APFloat::cmpEqual, VT);
1909 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1910 return getUNDEF(VT);
1912 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1913 R==APFloat::cmpEqual, VT);
1914 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1915 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1916 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1917 R==APFloat::cmpEqual, VT);
1918 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1919 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1920 R==APFloat::cmpLessThan, VT);
1921 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1922 R==APFloat::cmpUnordered, VT);
1923 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1924 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1927 // Ensure that the constant occurs on the RHS.
1928 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1929 MVT CompVT = N1.getValueType().getSimpleVT();
1930 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1933 return getSetCC(dl, VT, N2, N1, SwappedCond);
1937 // Could not fold it.
1941 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1942 /// use this predicate to simplify operations downstream.
1943 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1944 // This predicate is not safe for vector operations.
1945 if (Op.getValueType().isVector())
1948 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1949 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1952 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1953 /// this predicate to simplify operations downstream. Mask is known to be zero
1954 /// for bits that V cannot have.
1955 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1956 unsigned Depth) const {
1957 APInt KnownZero, KnownOne;
1958 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1959 return (KnownZero & Mask) == Mask;
1962 /// Determine which bits of Op are known to be either zero or one and return
1963 /// them in the KnownZero/KnownOne bitsets.
1964 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1965 APInt &KnownOne, unsigned Depth) const {
1966 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1968 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1970 return; // Limit search depth.
1972 APInt KnownZero2, KnownOne2;
1974 switch (Op.getOpcode()) {
1976 // We know all of the bits for a constant!
1977 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1978 KnownZero = ~KnownOne;
1981 // If either the LHS or the RHS are Zero, the result is zero.
1982 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1983 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1985 // Output known-1 bits are only known if set in both the LHS & RHS.
1986 KnownOne &= KnownOne2;
1987 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1988 KnownZero |= KnownZero2;
1991 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1992 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1994 // Output known-0 bits are only known if clear in both the LHS & RHS.
1995 KnownZero &= KnownZero2;
1996 // Output known-1 are known to be set if set in either the LHS | RHS.
1997 KnownOne |= KnownOne2;
2000 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2001 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2003 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2004 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2005 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2006 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2007 KnownZero = KnownZeroOut;
2011 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2012 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2014 // If low bits are zero in either operand, output low known-0 bits.
2015 // Also compute a conserative estimate for high known-0 bits.
2016 // More trickiness is possible, but this is sufficient for the
2017 // interesting case of alignment computation.
2018 KnownOne.clearAllBits();
2019 unsigned TrailZ = KnownZero.countTrailingOnes() +
2020 KnownZero2.countTrailingOnes();
2021 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2022 KnownZero2.countLeadingOnes(),
2023 BitWidth) - BitWidth;
2025 TrailZ = std::min(TrailZ, BitWidth);
2026 LeadZ = std::min(LeadZ, BitWidth);
2027 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2028 APInt::getHighBitsSet(BitWidth, LeadZ);
2032 // For the purposes of computing leading zeros we can conservatively
2033 // treat a udiv as a logical right shift by the power of 2 known to
2034 // be less than the denominator.
2035 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2036 unsigned LeadZ = KnownZero2.countLeadingOnes();
2038 KnownOne2.clearAllBits();
2039 KnownZero2.clearAllBits();
2040 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2041 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2042 if (RHSUnknownLeadingOnes != BitWidth)
2043 LeadZ = std::min(BitWidth,
2044 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2046 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2050 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2051 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2053 // Only known if known in both the LHS and RHS.
2054 KnownOne &= KnownOne2;
2055 KnownZero &= KnownZero2;
2057 case ISD::SELECT_CC:
2058 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2059 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2061 // Only known if known in both the LHS and RHS.
2062 KnownOne &= KnownOne2;
2063 KnownZero &= KnownZero2;
2071 if (Op.getResNo() != 1)
2073 // The boolean result conforms to getBooleanContents.
2074 // If we know the result of a setcc has the top bits zero, use this info.
2075 // We know that we have an integer-based boolean since these operations
2076 // are only available for integer.
2077 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2078 TargetLowering::ZeroOrOneBooleanContent &&
2080 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2083 // If we know the result of a setcc has the top bits zero, use this info.
2084 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2085 TargetLowering::ZeroOrOneBooleanContent &&
2087 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2090 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2091 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2092 unsigned ShAmt = SA->getZExtValue();
2094 // If the shift count is an invalid immediate, don't do anything.
2095 if (ShAmt >= BitWidth)
2098 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2099 KnownZero <<= ShAmt;
2101 // low bits known zero.
2102 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2106 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2107 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2108 unsigned ShAmt = SA->getZExtValue();
2110 // If the shift count is an invalid immediate, don't do anything.
2111 if (ShAmt >= BitWidth)
2114 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2115 KnownZero = KnownZero.lshr(ShAmt);
2116 KnownOne = KnownOne.lshr(ShAmt);
2118 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2119 KnownZero |= HighBits; // High bits known zero.
2123 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2124 unsigned ShAmt = SA->getZExtValue();
2126 // If the shift count is an invalid immediate, don't do anything.
2127 if (ShAmt >= BitWidth)
2130 // If any of the demanded bits are produced by the sign extension, we also
2131 // demand the input sign bit.
2132 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2134 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2135 KnownZero = KnownZero.lshr(ShAmt);
2136 KnownOne = KnownOne.lshr(ShAmt);
2138 // Handle the sign bits.
2139 APInt SignBit = APInt::getSignBit(BitWidth);
2140 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2142 if (KnownZero.intersects(SignBit)) {
2143 KnownZero |= HighBits; // New bits are known zero.
2144 } else if (KnownOne.intersects(SignBit)) {
2145 KnownOne |= HighBits; // New bits are known one.
2149 case ISD::SIGN_EXTEND_INREG: {
2150 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2151 unsigned EBits = EVT.getScalarType().getSizeInBits();
2153 // Sign extension. Compute the demanded bits in the result that are not
2154 // present in the input.
2155 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2157 APInt InSignBit = APInt::getSignBit(EBits);
2158 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2160 // If the sign extended bits are demanded, we know that the sign
2162 InSignBit = InSignBit.zext(BitWidth);
2163 if (NewBits.getBoolValue())
2164 InputDemandedBits |= InSignBit;
2166 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2167 KnownOne &= InputDemandedBits;
2168 KnownZero &= InputDemandedBits;
2170 // If the sign bit of the input is known set or clear, then we know the
2171 // top bits of the result.
2172 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2173 KnownZero |= NewBits;
2174 KnownOne &= ~NewBits;
2175 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2176 KnownOne |= NewBits;
2177 KnownZero &= ~NewBits;
2178 } else { // Input sign bit unknown
2179 KnownZero &= ~NewBits;
2180 KnownOne &= ~NewBits;
2185 case ISD::CTTZ_ZERO_UNDEF:
2187 case ISD::CTLZ_ZERO_UNDEF:
2189 unsigned LowBits = Log2_32(BitWidth)+1;
2190 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2191 KnownOne.clearAllBits();
2195 LoadSDNode *LD = cast<LoadSDNode>(Op);
2196 // If this is a ZEXTLoad and we are looking at the loaded value.
2197 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2198 EVT VT = LD->getMemoryVT();
2199 unsigned MemBits = VT.getScalarType().getSizeInBits();
2200 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2201 } else if (const MDNode *Ranges = LD->getRanges()) {
2202 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2206 case ISD::ZERO_EXTEND: {
2207 EVT InVT = Op.getOperand(0).getValueType();
2208 unsigned InBits = InVT.getScalarType().getSizeInBits();
2209 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2210 KnownZero = KnownZero.trunc(InBits);
2211 KnownOne = KnownOne.trunc(InBits);
2212 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2213 KnownZero = KnownZero.zext(BitWidth);
2214 KnownOne = KnownOne.zext(BitWidth);
2215 KnownZero |= NewBits;
2218 case ISD::SIGN_EXTEND: {
2219 EVT InVT = Op.getOperand(0).getValueType();
2220 unsigned InBits = InVT.getScalarType().getSizeInBits();
2221 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2223 KnownZero = KnownZero.trunc(InBits);
2224 KnownOne = KnownOne.trunc(InBits);
2225 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2227 // Note if the sign bit is known to be zero or one.
2228 bool SignBitKnownZero = KnownZero.isNegative();
2229 bool SignBitKnownOne = KnownOne.isNegative();
2231 KnownZero = KnownZero.zext(BitWidth);
2232 KnownOne = KnownOne.zext(BitWidth);
2234 // If the sign bit is known zero or one, the top bits match.
2235 if (SignBitKnownZero)
2236 KnownZero |= NewBits;
2237 else if (SignBitKnownOne)
2238 KnownOne |= NewBits;
2241 case ISD::ANY_EXTEND: {
2242 EVT InVT = Op.getOperand(0).getValueType();
2243 unsigned InBits = InVT.getScalarType().getSizeInBits();
2244 KnownZero = KnownZero.trunc(InBits);
2245 KnownOne = KnownOne.trunc(InBits);
2246 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2247 KnownZero = KnownZero.zext(BitWidth);
2248 KnownOne = KnownOne.zext(BitWidth);
2251 case ISD::TRUNCATE: {
2252 EVT InVT = Op.getOperand(0).getValueType();
2253 unsigned InBits = InVT.getScalarType().getSizeInBits();
2254 KnownZero = KnownZero.zext(InBits);
2255 KnownOne = KnownOne.zext(InBits);
2256 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2257 KnownZero = KnownZero.trunc(BitWidth);
2258 KnownOne = KnownOne.trunc(BitWidth);
2261 case ISD::AssertZext: {
2262 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2263 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2264 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2265 KnownZero |= (~InMask);
2266 KnownOne &= (~KnownZero);
2270 // All bits are zero except the low bit.
2271 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2275 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2276 // We know that the top bits of C-X are clear if X contains less bits
2277 // than C (i.e. no wrap-around can happen). For example, 20-X is
2278 // positive if we can prove that X is >= 0 and < 16.
2279 if (CLHS->getAPIntValue().isNonNegative()) {
2280 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2281 // NLZ can't be BitWidth with no sign bit
2282 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2283 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2285 // If all of the MaskV bits are known to be zero, then we know the
2286 // output top bits are zero, because we now know that the output is
2288 if ((KnownZero2 & MaskV) == MaskV) {
2289 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2290 // Top bits known zero.
2291 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2299 // Output known-0 bits are known if clear or set in both the low clear bits
2300 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2301 // low 3 bits clear.
2302 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2303 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2305 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2306 KnownZeroOut = std::min(KnownZeroOut,
2307 KnownZero2.countTrailingOnes());
2309 if (Op.getOpcode() == ISD::ADD) {
2310 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2314 // With ADDE, a carry bit may be added in, so we can only use this
2315 // information if we know (at least) that the low two bits are clear. We
2316 // then return to the caller that the low bit is unknown but that other bits
2318 if (KnownZeroOut >= 2) // ADDE
2319 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2323 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2324 const APInt &RA = Rem->getAPIntValue().abs();
2325 if (RA.isPowerOf2()) {
2326 APInt LowBits = RA - 1;
2327 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2329 // The low bits of the first operand are unchanged by the srem.
2330 KnownZero = KnownZero2 & LowBits;
2331 KnownOne = KnownOne2 & LowBits;
2333 // If the first operand is non-negative or has all low bits zero, then
2334 // the upper bits are all zero.
2335 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2336 KnownZero |= ~LowBits;
2338 // If the first operand is negative and not all low bits are zero, then
2339 // the upper bits are all one.
2340 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2341 KnownOne |= ~LowBits;
2342 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2347 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2348 const APInt &RA = Rem->getAPIntValue();
2349 if (RA.isPowerOf2()) {
2350 APInt LowBits = (RA - 1);
2351 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2353 // The upper bits are all zero, the lower ones are unchanged.
2354 KnownZero = KnownZero2 | ~LowBits;
2355 KnownOne = KnownOne2 & LowBits;
2360 // Since the result is less than or equal to either operand, any leading
2361 // zero bits in either operand must also exist in the result.
2362 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2363 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2365 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2366 KnownZero2.countLeadingOnes());
2367 KnownOne.clearAllBits();
2368 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2371 case ISD::EXTRACT_ELEMENT: {
2372 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2373 const unsigned Index =
2374 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2375 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2377 // Remove low part of known bits mask
2378 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2379 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2381 // Remove high part of known bit mask
2382 KnownZero = KnownZero.trunc(BitWidth);
2383 KnownOne = KnownOne.trunc(BitWidth);
2386 case ISD::FrameIndex:
2387 case ISD::TargetFrameIndex:
2388 if (unsigned Align = InferPtrAlignment(Op)) {
2389 // The low bits are known zero if the pointer is aligned.
2390 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2396 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2399 case ISD::INTRINSIC_WO_CHAIN:
2400 case ISD::INTRINSIC_W_CHAIN:
2401 case ISD::INTRINSIC_VOID:
2402 // Allow the target to implement this method for its nodes.
2403 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2407 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2410 /// ComputeNumSignBits - Return the number of times the sign bit of the
2411 /// register is replicated into the other bits. We know that at least 1 bit
2412 /// is always equal to the sign bit (itself), but other cases can give us
2413 /// information. For example, immediately after an "SRA X, 2", we know that
2414 /// the top 3 bits are all equal to each other, so we return 3.
2415 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2416 EVT VT = Op.getValueType();
2417 assert(VT.isInteger() && "Invalid VT!");
2418 unsigned VTBits = VT.getScalarType().getSizeInBits();
2420 unsigned FirstAnswer = 1;
2423 return 1; // Limit search depth.
2425 switch (Op.getOpcode()) {
2427 case ISD::AssertSext:
2428 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2429 return VTBits-Tmp+1;
2430 case ISD::AssertZext:
2431 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2434 case ISD::Constant: {
2435 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2436 return Val.getNumSignBits();
2439 case ISD::SIGN_EXTEND:
2441 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2442 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2444 case ISD::SIGN_EXTEND_INREG:
2445 // Max of the input and what this extends.
2447 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2450 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2451 return std::max(Tmp, Tmp2);
2454 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2455 // SRA X, C -> adds C sign bits.
2456 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2457 Tmp += C->getZExtValue();
2458 if (Tmp > VTBits) Tmp = VTBits;
2462 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2463 // shl destroys sign bits.
2464 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2465 if (C->getZExtValue() >= VTBits || // Bad shift.
2466 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2467 return Tmp - C->getZExtValue();
2472 case ISD::XOR: // NOT is handled here.
2473 // Logical binary ops preserve the number of sign bits at the worst.
2474 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2476 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2477 FirstAnswer = std::min(Tmp, Tmp2);
2478 // We computed what we know about the sign bits as our first
2479 // answer. Now proceed to the generic code that uses
2480 // computeKnownBits, and pick whichever answer is better.
2485 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2486 if (Tmp == 1) return 1; // Early out.
2487 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2488 return std::min(Tmp, Tmp2);
2496 if (Op.getResNo() != 1)
2498 // The boolean result conforms to getBooleanContents. Fall through.
2499 // If setcc returns 0/-1, all bits are sign bits.
2500 // We know that we have an integer-based boolean since these operations
2501 // are only available for integer.
2502 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2503 TargetLowering::ZeroOrNegativeOneBooleanContent)
2507 // If setcc returns 0/-1, all bits are sign bits.
2508 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2509 TargetLowering::ZeroOrNegativeOneBooleanContent)
2514 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2515 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2517 // Handle rotate right by N like a rotate left by 32-N.
2518 if (Op.getOpcode() == ISD::ROTR)
2519 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2521 // If we aren't rotating out all of the known-in sign bits, return the
2522 // number that are left. This handles rotl(sext(x), 1) for example.
2523 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2524 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2528 // Add can have at most one carry bit. Thus we know that the output
2529 // is, at worst, one more bit than the inputs.
2530 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2531 if (Tmp == 1) return 1; // Early out.
2533 // Special case decrementing a value (ADD X, -1):
2534 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2535 if (CRHS->isAllOnesValue()) {
2536 APInt KnownZero, KnownOne;
2537 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2539 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2541 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2544 // If we are subtracting one from a positive number, there is no carry
2545 // out of the result.
2546 if (KnownZero.isNegative())
2550 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2551 if (Tmp2 == 1) return 1;
2552 return std::min(Tmp, Tmp2)-1;
2555 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2556 if (Tmp2 == 1) return 1;
2559 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2560 if (CLHS->isNullValue()) {
2561 APInt KnownZero, KnownOne;
2562 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2563 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2565 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2568 // If the input is known to be positive (the sign bit is known clear),
2569 // the output of the NEG has the same number of sign bits as the input.
2570 if (KnownZero.isNegative())
2573 // Otherwise, we treat this like a SUB.
2576 // Sub can have at most one carry bit. Thus we know that the output
2577 // is, at worst, one more bit than the inputs.
2578 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2579 if (Tmp == 1) return 1; // Early out.
2580 return std::min(Tmp, Tmp2)-1;
2582 // FIXME: it's tricky to do anything useful for this, but it is an important
2583 // case for targets like X86.
2585 case ISD::EXTRACT_ELEMENT: {
2586 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2587 const int BitWidth = Op.getValueType().getSizeInBits();
2589 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2591 // Get reverse index (starting from 1), Op1 value indexes elements from
2592 // little end. Sign starts at big end.
2593 const int rIndex = Items - 1 -
2594 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2596 // If the sign portion ends in our element the substraction gives correct
2597 // result. Otherwise it gives either negative or > bitwidth result
2598 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2602 // If we are looking at the loaded value of the SDNode.
2603 if (Op.getResNo() == 0) {
2604 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2605 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2606 unsigned ExtType = LD->getExtensionType();
2609 case ISD::SEXTLOAD: // '17' bits known
2610 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2611 return VTBits-Tmp+1;
2612 case ISD::ZEXTLOAD: // '16' bits known
2613 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2619 // Allow the target to implement this method for its nodes.
2620 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2621 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2622 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2623 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2624 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2625 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2628 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2629 // use this information.
2630 APInt KnownZero, KnownOne;
2631 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2634 if (KnownZero.isNegative()) { // sign bit is 0
2636 } else if (KnownOne.isNegative()) { // sign bit is 1;
2643 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2644 // the number of identical bits in the top of the input value.
2646 Mask <<= Mask.getBitWidth()-VTBits;
2647 // Return # leading zeros. We use 'min' here in case Val was zero before
2648 // shifting. We don't want to return '64' as for an i32 "0".
2649 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2652 /// isBaseWithConstantOffset - Return true if the specified operand is an
2653 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2654 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2655 /// semantics as an ADD. This handles the equivalence:
2656 /// X|Cst == X+Cst iff X&Cst = 0.
2657 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2658 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2659 !isa<ConstantSDNode>(Op.getOperand(1)))
2662 if (Op.getOpcode() == ISD::OR &&
2663 !MaskedValueIsZero(Op.getOperand(0),
2664 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2671 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2672 // If we're told that NaNs won't happen, assume they won't.
2673 if (getTarget().Options.NoNaNsFPMath)
2676 // If the value is a constant, we can obviously see if it is a NaN or not.
2677 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2678 return !C->getValueAPF().isNaN();
2680 // TODO: Recognize more cases here.
2685 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2686 // If the value is a constant, we can obviously see if it is a zero or not.
2687 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2688 return !C->isZero();
2690 // TODO: Recognize more cases here.
2691 switch (Op.getOpcode()) {
2694 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2695 return !C->isNullValue();
2702 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2703 // Check the obvious case.
2704 if (A == B) return true;
2706 // For for negative and positive zero.
2707 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2708 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2709 if (CA->isZero() && CB->isZero()) return true;
2711 // Otherwise they may not be equal.
2715 /// getNode - Gets or creates the specified node.
2717 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2718 FoldingSetNodeID ID;
2719 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2721 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2722 return SDValue(E, 0);
2724 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2725 DL.getDebugLoc(), getVTList(VT));
2726 CSEMap.InsertNode(N, IP);
2729 return SDValue(N, 0);
2732 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2733 EVT VT, SDValue Operand) {
2734 // Constant fold unary operations with an integer constant operand. Even
2735 // opaque constant will be folded, because the folding of unary operations
2736 // doesn't create new constants with different values. Nevertheless, the
2737 // opaque flag is preserved during folding to prevent future folding with
2739 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2740 const APInt &Val = C->getAPIntValue();
2743 case ISD::SIGN_EXTEND:
2744 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2745 C->isTargetOpcode(), C->isOpaque());
2746 case ISD::ANY_EXTEND:
2747 case ISD::ZERO_EXTEND:
2749 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2750 C->isTargetOpcode(), C->isOpaque());
2751 case ISD::UINT_TO_FP:
2752 case ISD::SINT_TO_FP: {
2753 APFloat apf(EVTToAPFloatSemantics(VT),
2754 APInt::getNullValue(VT.getSizeInBits()));
2755 (void)apf.convertFromAPInt(Val,
2756 Opcode==ISD::SINT_TO_FP,
2757 APFloat::rmNearestTiesToEven);
2758 return getConstantFP(apf, VT);
2761 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2762 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), VT);
2763 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2764 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2765 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2766 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2769 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2772 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2775 case ISD::CTLZ_ZERO_UNDEF:
2776 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2779 case ISD::CTTZ_ZERO_UNDEF:
2780 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2785 // Constant fold unary operations with a floating point constant operand.
2786 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2787 APFloat V = C->getValueAPF(); // make copy
2791 return getConstantFP(V, VT);
2794 return getConstantFP(V, VT);
2796 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2797 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2798 return getConstantFP(V, VT);
2802 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2803 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2804 return getConstantFP(V, VT);
2808 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2809 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2810 return getConstantFP(V, VT);
2813 case ISD::FP_EXTEND: {
2815 // This can return overflow, underflow, or inexact; we don't care.
2816 // FIXME need to be more flexible about rounding mode.
2817 (void)V.convert(EVTToAPFloatSemantics(VT),
2818 APFloat::rmNearestTiesToEven, &ignored);
2819 return getConstantFP(V, VT);
2821 case ISD::FP_TO_SINT:
2822 case ISD::FP_TO_UINT: {
2825 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2826 // FIXME need to be more flexible about rounding mode.
2827 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2828 Opcode==ISD::FP_TO_SINT,
2829 APFloat::rmTowardZero, &ignored);
2830 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2832 APInt api(VT.getSizeInBits(), x);
2833 return getConstant(api, VT);
2836 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2837 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), VT);
2838 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2839 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2840 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2841 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2846 // Constant fold unary operations with a vector integer or float operand.
2847 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2848 if (BV->isConstant()) {
2851 // FIXME: Entirely reasonable to perform folding of other unary
2852 // operations here as the need arises.
2855 // Constant build vector truncation can be done with the original scalar
2856 // operands but with a new build vector with the truncated value type.
2857 return getNode(ISD::BUILD_VECTOR, DL, VT, BV->ops());
2863 case ISD::FP_EXTEND:
2864 case ISD::UINT_TO_FP:
2865 case ISD::SINT_TO_FP: {
2866 // Let the above scalar folding handle the folding of each element.
2867 SmallVector<SDValue, 8> Ops;
2868 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2869 SDValue OpN = BV->getOperand(i);
2870 OpN = getNode(Opcode, DL, VT.getVectorElementType(), OpN);
2871 if (OpN.getOpcode() != ISD::UNDEF &&
2872 OpN.getOpcode() != ISD::Constant &&
2873 OpN.getOpcode() != ISD::ConstantFP)
2877 if (Ops.size() == VT.getVectorNumElements())
2878 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2885 unsigned OpOpcode = Operand.getNode()->getOpcode();
2887 case ISD::TokenFactor:
2888 case ISD::MERGE_VALUES:
2889 case ISD::CONCAT_VECTORS:
2890 return Operand; // Factor, merge or concat of one node? No need.
2891 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2892 case ISD::FP_EXTEND:
2893 assert(VT.isFloatingPoint() &&
2894 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2895 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2896 assert((!VT.isVector() ||
2897 VT.getVectorNumElements() ==
2898 Operand.getValueType().getVectorNumElements()) &&
2899 "Vector element count mismatch!");
2900 if (Operand.getOpcode() == ISD::UNDEF)
2901 return getUNDEF(VT);
2903 case ISD::SIGN_EXTEND:
2904 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2905 "Invalid SIGN_EXTEND!");
2906 if (Operand.getValueType() == VT) return Operand; // noop extension
2907 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2908 "Invalid sext node, dst < src!");
2909 assert((!VT.isVector() ||
2910 VT.getVectorNumElements() ==
2911 Operand.getValueType().getVectorNumElements()) &&
2912 "Vector element count mismatch!");
2913 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2914 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2915 else if (OpOpcode == ISD::UNDEF)
2916 // sext(undef) = 0, because the top bits will all be the same.
2917 return getConstant(0, VT);
2919 case ISD::ZERO_EXTEND:
2920 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2921 "Invalid ZERO_EXTEND!");
2922 if (Operand.getValueType() == VT) return Operand; // noop extension
2923 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2924 "Invalid zext node, dst < src!");
2925 assert((!VT.isVector() ||
2926 VT.getVectorNumElements() ==
2927 Operand.getValueType().getVectorNumElements()) &&
2928 "Vector element count mismatch!");
2929 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2930 return getNode(ISD::ZERO_EXTEND, DL, VT,
2931 Operand.getNode()->getOperand(0));
2932 else if (OpOpcode == ISD::UNDEF)
2933 // zext(undef) = 0, because the top bits will be zero.
2934 return getConstant(0, VT);
2936 case ISD::ANY_EXTEND:
2937 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2938 "Invalid ANY_EXTEND!");
2939 if (Operand.getValueType() == VT) return Operand; // noop extension
2940 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2941 "Invalid anyext node, dst < src!");
2942 assert((!VT.isVector() ||
2943 VT.getVectorNumElements() ==
2944 Operand.getValueType().getVectorNumElements()) &&
2945 "Vector element count mismatch!");
2947 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2948 OpOpcode == ISD::ANY_EXTEND)
2949 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2950 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2951 else if (OpOpcode == ISD::UNDEF)
2952 return getUNDEF(VT);
2954 // (ext (trunx x)) -> x
2955 if (OpOpcode == ISD::TRUNCATE) {
2956 SDValue OpOp = Operand.getNode()->getOperand(0);
2957 if (OpOp.getValueType() == VT)
2962 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2963 "Invalid TRUNCATE!");
2964 if (Operand.getValueType() == VT) return Operand; // noop truncate
2965 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2966 "Invalid truncate node, src < dst!");
2967 assert((!VT.isVector() ||
2968 VT.getVectorNumElements() ==
2969 Operand.getValueType().getVectorNumElements()) &&
2970 "Vector element count mismatch!");
2971 if (OpOpcode == ISD::TRUNCATE)
2972 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2973 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2974 OpOpcode == ISD::ANY_EXTEND) {
2975 // If the source is smaller than the dest, we still need an extend.
2976 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2977 .bitsLT(VT.getScalarType()))
2978 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2979 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2980 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2981 return Operand.getNode()->getOperand(0);
2983 if (OpOpcode == ISD::UNDEF)
2984 return getUNDEF(VT);
2987 // Basic sanity checking.
2988 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2989 && "Cannot BITCAST between types of different sizes!");
2990 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2991 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2992 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2993 if (OpOpcode == ISD::UNDEF)
2994 return getUNDEF(VT);
2996 case ISD::SCALAR_TO_VECTOR:
2997 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2998 (VT.getVectorElementType() == Operand.getValueType() ||
2999 (VT.getVectorElementType().isInteger() &&
3000 Operand.getValueType().isInteger() &&
3001 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3002 "Illegal SCALAR_TO_VECTOR node!");
3003 if (OpOpcode == ISD::UNDEF)
3004 return getUNDEF(VT);
3005 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3006 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3007 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3008 Operand.getConstantOperandVal(1) == 0 &&
3009 Operand.getOperand(0).getValueType() == VT)
3010 return Operand.getOperand(0);
3013 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3014 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3015 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3016 Operand.getNode()->getOperand(0));
3017 if (OpOpcode == ISD::FNEG) // --X -> X
3018 return Operand.getNode()->getOperand(0);
3021 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3022 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3027 SDVTList VTs = getVTList(VT);
3028 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3029 FoldingSetNodeID ID;
3030 SDValue Ops[1] = { Operand };
3031 AddNodeIDNode(ID, Opcode, VTs, Ops);
3033 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3034 return SDValue(E, 0);
3036 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3037 DL.getDebugLoc(), VTs, Operand);
3038 CSEMap.InsertNode(N, IP);
3040 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3041 DL.getDebugLoc(), VTs, Operand);
3045 return SDValue(N, 0);
3048 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
3049 SDNode *Cst1, SDNode *Cst2) {
3050 // If the opcode is a target-specific ISD node, there's nothing we can
3051 // do here and the operand rules may not line up with the below, so
3053 if (Opcode >= ISD::BUILTIN_OP_END)
3056 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3057 SmallVector<SDValue, 4> Outputs;
3058 EVT SVT = VT.getScalarType();
3060 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3061 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3062 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3065 if (Scalar1 && Scalar2)
3066 // Scalar instruction.
3067 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3069 // For vectors extract each constant element into Inputs so we can constant
3070 // fold them individually.
3071 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3072 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3076 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3078 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3079 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3080 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3081 if (!V1 || !V2) // Not a constant, bail.
3084 if (V1->isOpaque() || V2->isOpaque())
3087 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3088 // FIXME: This is valid and could be handled by truncating the APInts.
3089 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3092 Inputs.push_back(std::make_pair(V1, V2));
3096 // We have a number of constant values, constant fold them element by element.
3097 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3098 const APInt &C1 = Inputs[I].first->getAPIntValue();
3099 const APInt &C2 = Inputs[I].second->getAPIntValue();
3103 Outputs.push_back(getConstant(C1 + C2, SVT));
3106 Outputs.push_back(getConstant(C1 - C2, SVT));
3109 Outputs.push_back(getConstant(C1 * C2, SVT));
3112 if (!C2.getBoolValue())
3114 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3117 if (!C2.getBoolValue())
3119 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3122 if (!C2.getBoolValue())
3124 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3127 if (!C2.getBoolValue())
3129 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3132 Outputs.push_back(getConstant(C1 & C2, SVT));
3135 Outputs.push_back(getConstant(C1 | C2, SVT));
3138 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3141 Outputs.push_back(getConstant(C1 << C2, SVT));
3144 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3147 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3150 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3153 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3160 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3161 "Expected a scalar or vector!"));
3163 // Handle the scalar case first.
3165 return Outputs.back();
3167 // We may have a vector type but a scalar result. Create a splat.
3168 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3170 // Build a big vector out of the scalar elements we generated.
3171 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3174 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3175 SDValue N2, bool nuw, bool nsw, bool exact) {
3176 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3177 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3180 case ISD::TokenFactor:
3181 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3182 N2.getValueType() == MVT::Other && "Invalid token factor!");
3183 // Fold trivial token factors.
3184 if (N1.getOpcode() == ISD::EntryToken) return N2;
3185 if (N2.getOpcode() == ISD::EntryToken) return N1;
3186 if (N1 == N2) return N1;
3188 case ISD::CONCAT_VECTORS:
3189 // Concat of UNDEFs is UNDEF.
3190 if (N1.getOpcode() == ISD::UNDEF &&
3191 N2.getOpcode() == ISD::UNDEF)
3192 return getUNDEF(VT);
3194 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3195 // one big BUILD_VECTOR.
3196 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3197 N2.getOpcode() == ISD::BUILD_VECTOR) {
3198 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3199 N1.getNode()->op_end());
3200 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3202 // BUILD_VECTOR requires all inputs to be of the same type, find the
3203 // maximum type and extend them all.
3204 EVT SVT = VT.getScalarType();
3205 for (SDValue Op : Elts)
3206 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3207 if (SVT.bitsGT(VT.getScalarType()))
3208 for (SDValue &Op : Elts)
3209 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3210 ? getZExtOrTrunc(Op, DL, SVT)
3211 : getSExtOrTrunc(Op, DL, SVT);
3213 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3217 assert(VT.isInteger() && "This operator does not apply to FP types!");
3218 assert(N1.getValueType() == N2.getValueType() &&
3219 N1.getValueType() == VT && "Binary operator types must match!");
3220 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3221 // worth handling here.
3222 if (N2C && N2C->isNullValue())
3224 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3231 assert(VT.isInteger() && "This operator does not apply to FP types!");
3232 assert(N1.getValueType() == N2.getValueType() &&
3233 N1.getValueType() == VT && "Binary operator types must match!");
3234 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3235 // it's worth handling here.
3236 if (N2C && N2C->isNullValue())
3246 assert(VT.isInteger() && "This operator does not apply to FP types!");
3247 assert(N1.getValueType() == N2.getValueType() &&
3248 N1.getValueType() == VT && "Binary operator types must match!");
3255 if (getTarget().Options.UnsafeFPMath) {
3256 if (Opcode == ISD::FADD) {
3258 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3259 if (CFP->getValueAPF().isZero())
3262 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3263 if (CFP->getValueAPF().isZero())
3265 } else if (Opcode == ISD::FSUB) {
3267 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3268 if (CFP->getValueAPF().isZero())
3270 } else if (Opcode == ISD::FMUL) {
3271 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3274 // If the first operand isn't the constant, try the second
3276 CFP = dyn_cast<ConstantFPSDNode>(N2);
3283 return SDValue(CFP,0);
3285 if (CFP->isExactlyValue(1.0))
3290 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3291 assert(N1.getValueType() == N2.getValueType() &&
3292 N1.getValueType() == VT && "Binary operator types must match!");
3294 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3295 assert(N1.getValueType() == VT &&
3296 N1.getValueType().isFloatingPoint() &&
3297 N2.getValueType().isFloatingPoint() &&
3298 "Invalid FCOPYSIGN!");
3305 assert(VT == N1.getValueType() &&
3306 "Shift operators return type must be the same as their first arg");
3307 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3308 "Shifts only work on integers");
3309 assert((!VT.isVector() || VT == N2.getValueType()) &&
3310 "Vector shift amounts must be in the same as their first arg");
3311 // Verify that the shift amount VT is bit enough to hold valid shift
3312 // amounts. This catches things like trying to shift an i1024 value by an
3313 // i8, which is easy to fall into in generic code that uses
3314 // TLI.getShiftAmount().
3315 assert(N2.getValueType().getSizeInBits() >=
3316 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3317 "Invalid use of small shift amount with oversized value!");
3319 // Always fold shifts of i1 values so the code generator doesn't need to
3320 // handle them. Since we know the size of the shift has to be less than the
3321 // size of the value, the shift/rotate count is guaranteed to be zero.
3324 if (N2C && N2C->isNullValue())
3327 case ISD::FP_ROUND_INREG: {
3328 EVT EVT = cast<VTSDNode>(N2)->getVT();
3329 assert(VT == N1.getValueType() && "Not an inreg round!");
3330 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3331 "Cannot FP_ROUND_INREG integer types");
3332 assert(EVT.isVector() == VT.isVector() &&
3333 "FP_ROUND_INREG type should be vector iff the operand "
3335 assert((!EVT.isVector() ||
3336 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3337 "Vector element counts must match in FP_ROUND_INREG");
3338 assert(EVT.bitsLE(VT) && "Not rounding down!");
3340 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3344 assert(VT.isFloatingPoint() &&
3345 N1.getValueType().isFloatingPoint() &&
3346 VT.bitsLE(N1.getValueType()) &&
3347 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3348 if (N1.getValueType() == VT) return N1; // noop conversion.
3350 case ISD::AssertSext:
3351 case ISD::AssertZext: {
3352 EVT EVT = cast<VTSDNode>(N2)->getVT();
3353 assert(VT == N1.getValueType() && "Not an inreg extend!");
3354 assert(VT.isInteger() && EVT.isInteger() &&
3355 "Cannot *_EXTEND_INREG FP types");
3356 assert(!EVT.isVector() &&
3357 "AssertSExt/AssertZExt type should be the vector element type "
3358 "rather than the vector type!");
3359 assert(EVT.bitsLE(VT) && "Not extending!");
3360 if (VT == EVT) return N1; // noop assertion.
3363 case ISD::SIGN_EXTEND_INREG: {
3364 EVT EVT = cast<VTSDNode>(N2)->getVT();
3365 assert(VT == N1.getValueType() && "Not an inreg extend!");
3366 assert(VT.isInteger() && EVT.isInteger() &&
3367 "Cannot *_EXTEND_INREG FP types");
3368 assert(EVT.isVector() == VT.isVector() &&
3369 "SIGN_EXTEND_INREG type should be vector iff the operand "
3371 assert((!EVT.isVector() ||
3372 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3373 "Vector element counts must match in SIGN_EXTEND_INREG");
3374 assert(EVT.bitsLE(VT) && "Not extending!");
3375 if (EVT == VT) return N1; // Not actually extending
3378 APInt Val = N1C->getAPIntValue();
3379 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3380 Val <<= Val.getBitWidth()-FromBits;
3381 Val = Val.ashr(Val.getBitWidth()-FromBits);
3382 return getConstant(Val, VT);
3386 case ISD::EXTRACT_VECTOR_ELT:
3387 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3388 if (N1.getOpcode() == ISD::UNDEF)
3389 return getUNDEF(VT);
3391 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3392 // expanding copies of large vectors from registers.
3394 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3395 N1.getNumOperands() > 0) {
3397 N1.getOperand(0).getValueType().getVectorNumElements();
3398 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3399 N1.getOperand(N2C->getZExtValue() / Factor),
3400 getConstant(N2C->getZExtValue() % Factor,
3401 N2.getValueType()));
3404 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3405 // expanding large vector constants.
3406 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3407 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3409 if (VT != Elt.getValueType())
3410 // If the vector element type is not legal, the BUILD_VECTOR operands
3411 // are promoted and implicitly truncated, and the result implicitly
3412 // extended. Make that explicit here.
3413 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3418 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3419 // operations are lowered to scalars.
3420 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3421 // If the indices are the same, return the inserted element else
3422 // if the indices are known different, extract the element from
3423 // the original vector.
3424 SDValue N1Op2 = N1.getOperand(2);
3425 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3427 if (N1Op2C && N2C) {
3428 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3429 if (VT == N1.getOperand(1).getValueType())
3430 return N1.getOperand(1);
3432 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3435 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3439 case ISD::EXTRACT_ELEMENT:
3440 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3441 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3442 (N1.getValueType().isInteger() == VT.isInteger()) &&
3443 N1.getValueType() != VT &&
3444 "Wrong types for EXTRACT_ELEMENT!");
3446 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3447 // 64-bit integers into 32-bit parts. Instead of building the extract of
3448 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3449 if (N1.getOpcode() == ISD::BUILD_PAIR)
3450 return N1.getOperand(N2C->getZExtValue());
3452 // EXTRACT_ELEMENT of a constant int is also very common.
3453 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3454 unsigned ElementSize = VT.getSizeInBits();
3455 unsigned Shift = ElementSize * N2C->getZExtValue();
3456 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3457 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3460 case ISD::EXTRACT_SUBVECTOR: {
3462 if (VT.isSimple() && N1.getValueType().isSimple()) {
3463 assert(VT.isVector() && N1.getValueType().isVector() &&
3464 "Extract subvector VTs must be a vectors!");
3465 assert(VT.getVectorElementType() ==
3466 N1.getValueType().getVectorElementType() &&
3467 "Extract subvector VTs must have the same element type!");
3468 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3469 "Extract subvector must be from larger vector to smaller vector!");
3471 if (isa<ConstantSDNode>(Index.getNode())) {
3472 assert((VT.getVectorNumElements() +
3473 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3474 <= N1.getValueType().getVectorNumElements())
3475 && "Extract subvector overflow!");
3478 // Trivial extraction.
3479 if (VT.getSimpleVT() == N1.getSimpleValueType())
3486 // Perform trivial constant folding.
3488 FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode()))
3491 // Canonicalize constant to RHS if commutative.
3492 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3493 std::swap(N1C, N2C);
3497 // Constant fold FP operations.
3498 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3499 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3500 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3502 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3503 // Canonicalize constant to RHS if commutative.
3504 std::swap(N1CFP, N2CFP);
3507 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3508 APFloat::opStatus s;
3511 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3512 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3513 return getConstantFP(V1, VT);
3516 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3517 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3518 return getConstantFP(V1, VT);
3521 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3522 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3523 return getConstantFP(V1, VT);
3526 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3527 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3528 s!=APFloat::opDivByZero)) {
3529 return getConstantFP(V1, VT);
3533 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3534 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3535 s!=APFloat::opDivByZero)) {
3536 return getConstantFP(V1, VT);
3539 case ISD::FCOPYSIGN:
3541 return getConstantFP(V1, VT);
3546 if (Opcode == ISD::FP_ROUND) {
3547 APFloat V = N1CFP->getValueAPF(); // make copy
3549 // This can return overflow, underflow, or inexact; we don't care.
3550 // FIXME need to be more flexible about rounding mode.
3551 (void)V.convert(EVTToAPFloatSemantics(VT),
3552 APFloat::rmNearestTiesToEven, &ignored);
3553 return getConstantFP(V, VT);
3557 // Canonicalize an UNDEF to the RHS, even over a constant.
3558 if (N1.getOpcode() == ISD::UNDEF) {
3559 if (isCommutativeBinOp(Opcode)) {
3563 case ISD::FP_ROUND_INREG:
3564 case ISD::SIGN_EXTEND_INREG:
3570 return N1; // fold op(undef, arg2) -> undef
3578 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3579 // For vectors, we can't easily build an all zero vector, just return
3586 // Fold a bunch of operators when the RHS is undef.
3587 if (N2.getOpcode() == ISD::UNDEF) {
3590 if (N1.getOpcode() == ISD::UNDEF)
3591 // Handle undef ^ undef -> 0 special case. This is a common
3593 return getConstant(0, VT);
3603 return N2; // fold op(arg1, undef) -> undef
3609 if (getTarget().Options.UnsafeFPMath)
3617 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3618 // For vectors, we can't easily build an all zero vector, just return
3623 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3624 // For vectors, we can't easily build an all one vector, just return
3632 // Memoize this node if possible.
3634 SDVTList VTs = getVTList(VT);
3635 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3636 if (VT != MVT::Glue) {
3637 SDValue Ops[] = {N1, N2};
3638 FoldingSetNodeID ID;
3639 AddNodeIDNode(ID, Opcode, VTs, Ops);
3641 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3643 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3644 return SDValue(E, 0);
3646 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3648 CSEMap.InsertNode(N, IP);
3650 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3654 return SDValue(N, 0);
3657 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3658 SDValue N1, SDValue N2, SDValue N3) {
3659 // Perform various simplifications.
3660 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3663 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3664 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3665 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3666 if (N1CFP && N2CFP && N3CFP) {
3667 APFloat V1 = N1CFP->getValueAPF();
3668 const APFloat &V2 = N2CFP->getValueAPF();
3669 const APFloat &V3 = N3CFP->getValueAPF();
3670 APFloat::opStatus s =
3671 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3672 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3673 return getConstantFP(V1, VT);
3677 case ISD::CONCAT_VECTORS:
3678 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3679 // one big BUILD_VECTOR.
3680 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3681 N2.getOpcode() == ISD::BUILD_VECTOR &&
3682 N3.getOpcode() == ISD::BUILD_VECTOR) {
3683 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3684 N1.getNode()->op_end());
3685 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3686 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3687 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3691 // Use FoldSetCC to simplify SETCC's.
3692 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3693 if (Simp.getNode()) return Simp;
3698 if (N1C->getZExtValue())
3699 return N2; // select true, X, Y -> X
3700 return N3; // select false, X, Y -> Y
3703 if (N2 == N3) return N2; // select C, X, X -> X
3705 case ISD::VECTOR_SHUFFLE:
3706 llvm_unreachable("should use getVectorShuffle constructor!");
3707 case ISD::INSERT_SUBVECTOR: {
3709 if (VT.isSimple() && N1.getValueType().isSimple()
3710 && N2.getValueType().isSimple()) {
3711 assert(VT.isVector() && N1.getValueType().isVector() &&
3712 N2.getValueType().isVector() &&
3713 "Insert subvector VTs must be a vectors");
3714 assert(VT == N1.getValueType() &&
3715 "Dest and insert subvector source types must match!");
3716 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3717 "Insert subvector must be from smaller vector to larger vector!");
3718 if (isa<ConstantSDNode>(Index.getNode())) {
3719 assert((N2.getValueType().getVectorNumElements() +
3720 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3721 <= VT.getVectorNumElements())
3722 && "Insert subvector overflow!");
3725 // Trivial insertion.
3726 if (VT.getSimpleVT() == N2.getSimpleValueType())
3732 // Fold bit_convert nodes from a type to themselves.
3733 if (N1.getValueType() == VT)
3738 // Memoize node if it doesn't produce a flag.
3740 SDVTList VTs = getVTList(VT);
3741 if (VT != MVT::Glue) {
3742 SDValue Ops[] = { N1, N2, N3 };
3743 FoldingSetNodeID ID;
3744 AddNodeIDNode(ID, Opcode, VTs, Ops);
3746 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3747 return SDValue(E, 0);
3749 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3750 DL.getDebugLoc(), VTs, N1, N2, N3);
3751 CSEMap.InsertNode(N, IP);
3753 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3754 DL.getDebugLoc(), VTs, N1, N2, N3);
3758 return SDValue(N, 0);
3761 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3762 SDValue N1, SDValue N2, SDValue N3,
3764 SDValue Ops[] = { N1, N2, N3, N4 };
3765 return getNode(Opcode, DL, VT, Ops);
3768 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3769 SDValue N1, SDValue N2, SDValue N3,
3770 SDValue N4, SDValue N5) {
3771 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3772 return getNode(Opcode, DL, VT, Ops);
3775 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3776 /// the incoming stack arguments to be loaded from the stack.
3777 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3778 SmallVector<SDValue, 8> ArgChains;
3780 // Include the original chain at the beginning of the list. When this is
3781 // used by target LowerCall hooks, this helps legalize find the
3782 // CALLSEQ_BEGIN node.
3783 ArgChains.push_back(Chain);
3785 // Add a chain value for each stack argument.
3786 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3787 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3788 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3789 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3790 if (FI->getIndex() < 0)
3791 ArgChains.push_back(SDValue(L, 1));
3793 // Build a tokenfactor for all the chains.
3794 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3797 /// getMemsetValue - Vectorized representation of the memset value
3799 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3801 assert(Value.getOpcode() != ISD::UNDEF);
3803 unsigned NumBits = VT.getScalarType().getSizeInBits();
3804 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3805 assert(C->getAPIntValue().getBitWidth() == 8);
3806 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3808 return DAG.getConstant(Val, VT);
3809 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3812 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3813 EVT IntVT = VT.getScalarType();
3814 if (!IntVT.isInteger())
3815 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3817 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3819 // Use a multiplication with 0x010101... to extend the input to the
3821 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3822 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3823 DAG.getConstant(Magic, IntVT));
3826 if (VT != Value.getValueType() && !VT.isInteger())
3827 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3828 if (VT != Value.getValueType()) {
3829 assert(VT.getVectorElementType() == Value.getValueType() &&
3830 "value type should be one vector element here");
3831 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3832 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3838 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3839 /// used when a memcpy is turned into a memset when the source is a constant
3841 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3842 const TargetLowering &TLI, StringRef Str) {
3843 // Handle vector with all elements zero.
3846 return DAG.getConstant(0, VT);
3847 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3848 return DAG.getConstantFP(0.0, VT);
3849 else if (VT.isVector()) {
3850 unsigned NumElts = VT.getVectorNumElements();
3851 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3852 return DAG.getNode(ISD::BITCAST, dl, VT,
3853 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3856 llvm_unreachable("Expected type!");
3859 assert(!VT.isVector() && "Can't handle vector type here!");
3860 unsigned NumVTBits = VT.getSizeInBits();
3861 unsigned NumVTBytes = NumVTBits / 8;
3862 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3864 APInt Val(NumVTBits, 0);
3865 if (TLI.isLittleEndian()) {
3866 for (unsigned i = 0; i != NumBytes; ++i)
3867 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3869 for (unsigned i = 0; i != NumBytes; ++i)
3870 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3873 // If the "cost" of materializing the integer immediate is less than the cost
3874 // of a load, then it is cost effective to turn the load into the immediate.
3875 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3876 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3877 return DAG.getConstant(Val, VT);
3878 return SDValue(nullptr, 0);
3881 /// getMemBasePlusOffset - Returns base and offset node for the
3883 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3884 SelectionDAG &DAG) {
3885 EVT VT = Base.getValueType();
3886 return DAG.getNode(ISD::ADD, dl,
3887 VT, Base, DAG.getConstant(Offset, VT));
3890 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3892 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3893 unsigned SrcDelta = 0;
3894 GlobalAddressSDNode *G = nullptr;
3895 if (Src.getOpcode() == ISD::GlobalAddress)
3896 G = cast<GlobalAddressSDNode>(Src);
3897 else if (Src.getOpcode() == ISD::ADD &&
3898 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3899 Src.getOperand(1).getOpcode() == ISD::Constant) {
3900 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3901 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3906 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3909 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3910 /// to replace the memset / memcpy. Return true if the number of memory ops
3911 /// is below the threshold. It returns the types of the sequence of
3912 /// memory ops to perform memset / memcpy by reference.
3913 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3914 unsigned Limit, uint64_t Size,
3915 unsigned DstAlign, unsigned SrcAlign,
3921 const TargetLowering &TLI) {
3922 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3923 "Expecting memcpy / memset source to meet alignment requirement!");
3924 // If 'SrcAlign' is zero, that means the memory operation does not need to
3925 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3926 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3927 // is the specified alignment of the memory operation. If it is zero, that
3928 // means it's possible to change the alignment of the destination.
3929 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3930 // not need to be loaded.
3931 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3932 IsMemset, ZeroMemset, MemcpyStrSrc,
3933 DAG.getMachineFunction());
3935 if (VT == MVT::Other) {
3937 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3938 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3939 VT = TLI.getPointerTy();
3941 switch (DstAlign & 7) {
3942 case 0: VT = MVT::i64; break;
3943 case 4: VT = MVT::i32; break;
3944 case 2: VT = MVT::i16; break;
3945 default: VT = MVT::i8; break;
3950 while (!TLI.isTypeLegal(LVT))
3951 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3952 assert(LVT.isInteger());
3958 unsigned NumMemOps = 0;
3960 unsigned VTSize = VT.getSizeInBits() / 8;
3961 while (VTSize > Size) {
3962 // For now, only use non-vector load / store's for the left-over pieces.
3967 if (VT.isVector() || VT.isFloatingPoint()) {
3968 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3969 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3970 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3972 else if (NewVT == MVT::i64 &&
3973 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3974 TLI.isSafeMemOpType(MVT::f64)) {
3975 // i64 is usually not legal on 32-bit targets, but f64 may be.
3983 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3984 if (NewVT == MVT::i8)
3986 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3988 NewVTSize = NewVT.getSizeInBits() / 8;
3990 // If the new VT cannot cover all of the remaining bits, then consider
3991 // issuing a (or a pair of) unaligned and overlapping load / store.
3992 // FIXME: Only does this for 64-bit or more since we don't have proper
3993 // cost model for unaligned load / store.
3996 if (NumMemOps && AllowOverlap &&
3997 VTSize >= 8 && NewVTSize < Size &&
3998 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4006 if (++NumMemOps > Limit)
4009 MemOps.push_back(VT);
4016 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4017 SDValue Chain, SDValue Dst,
4018 SDValue Src, uint64_t Size,
4019 unsigned Align, bool isVol,
4021 MachinePointerInfo DstPtrInfo,
4022 MachinePointerInfo SrcPtrInfo) {
4023 // Turn a memcpy of undef to nop.
4024 if (Src.getOpcode() == ISD::UNDEF)
4027 // Expand memcpy to a series of load and store ops if the size operand falls
4028 // below a certain threshold.
4029 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4030 // rather than maybe a humongous number of loads and stores.
4031 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4032 std::vector<EVT> MemOps;
4033 bool DstAlignCanChange = false;
4034 MachineFunction &MF = DAG.getMachineFunction();
4035 MachineFrameInfo *MFI = MF.getFrameInfo();
4036 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4037 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4038 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4039 DstAlignCanChange = true;
4040 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4041 if (Align > SrcAlign)
4044 bool CopyFromStr = isMemSrcFromString(Src, Str);
4045 bool isZeroStr = CopyFromStr && Str.empty();
4046 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4048 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4049 (DstAlignCanChange ? 0 : Align),
4050 (isZeroStr ? 0 : SrcAlign),
4051 false, false, CopyFromStr, true, DAG, TLI))
4054 if (DstAlignCanChange) {
4055 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4056 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4058 // Don't promote to an alignment that would require dynamic stack
4060 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4061 if (!TRI->needsStackRealignment(MF))
4062 while (NewAlign > Align &&
4063 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4066 if (NewAlign > Align) {
4067 // Give the stack frame object a larger alignment if needed.
4068 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4069 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4074 SmallVector<SDValue, 8> OutChains;
4075 unsigned NumMemOps = MemOps.size();
4076 uint64_t SrcOff = 0, DstOff = 0;
4077 for (unsigned i = 0; i != NumMemOps; ++i) {
4079 unsigned VTSize = VT.getSizeInBits() / 8;
4080 SDValue Value, Store;
4082 if (VTSize > Size) {
4083 // Issuing an unaligned load / store pair that overlaps with the previous
4084 // pair. Adjust the offset accordingly.
4085 assert(i == NumMemOps-1 && i != 0);
4086 SrcOff -= VTSize - Size;
4087 DstOff -= VTSize - Size;
4091 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4092 // It's unlikely a store of a vector immediate can be done in a single
4093 // instruction. It would require a load from a constantpool first.
4094 // We only handle zero vectors here.
4095 // FIXME: Handle other cases where store of vector immediate is done in
4096 // a single instruction.
4097 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4098 if (Value.getNode())
4099 Store = DAG.getStore(Chain, dl, Value,
4100 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4101 DstPtrInfo.getWithOffset(DstOff), isVol,
4105 if (!Store.getNode()) {
4106 // The type might not be legal for the target. This should only happen
4107 // if the type is smaller than a legal type, as on PPC, so the right
4108 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4109 // to Load/Store if NVT==VT.
4110 // FIXME does the case above also need this?
4111 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4112 assert(NVT.bitsGE(VT));
4113 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4114 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4115 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4116 false, MinAlign(SrcAlign, SrcOff));
4117 Store = DAG.getTruncStore(Chain, dl, Value,
4118 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4119 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4122 OutChains.push_back(Store);
4128 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4131 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4132 SDValue Chain, SDValue Dst,
4133 SDValue Src, uint64_t Size,
4134 unsigned Align, bool isVol,
4136 MachinePointerInfo DstPtrInfo,
4137 MachinePointerInfo SrcPtrInfo) {
4138 // Turn a memmove of undef to nop.
4139 if (Src.getOpcode() == ISD::UNDEF)
4142 // Expand memmove to a series of load and store ops if the size operand falls
4143 // below a certain threshold.
4144 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4145 std::vector<EVT> MemOps;
4146 bool DstAlignCanChange = false;
4147 MachineFunction &MF = DAG.getMachineFunction();
4148 MachineFrameInfo *MFI = MF.getFrameInfo();
4149 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4150 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4151 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4152 DstAlignCanChange = true;
4153 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4154 if (Align > SrcAlign)
4156 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4158 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4159 (DstAlignCanChange ? 0 : Align), SrcAlign,
4160 false, false, false, false, DAG, TLI))
4163 if (DstAlignCanChange) {
4164 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4165 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4166 if (NewAlign > Align) {
4167 // Give the stack frame object a larger alignment if needed.
4168 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4169 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4174 uint64_t SrcOff = 0, DstOff = 0;
4175 SmallVector<SDValue, 8> LoadValues;
4176 SmallVector<SDValue, 8> LoadChains;
4177 SmallVector<SDValue, 8> OutChains;
4178 unsigned NumMemOps = MemOps.size();
4179 for (unsigned i = 0; i < NumMemOps; i++) {
4181 unsigned VTSize = VT.getSizeInBits() / 8;
4184 Value = DAG.getLoad(VT, dl, Chain,
4185 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4186 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4187 false, false, SrcAlign);
4188 LoadValues.push_back(Value);
4189 LoadChains.push_back(Value.getValue(1));
4192 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4194 for (unsigned i = 0; i < NumMemOps; i++) {
4196 unsigned VTSize = VT.getSizeInBits() / 8;
4199 Store = DAG.getStore(Chain, dl, LoadValues[i],
4200 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4201 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4202 OutChains.push_back(Store);
4206 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4209 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4212 /// \param DAG Selection DAG where lowered code is placed.
4213 /// \param dl Link to corresponding IR location.
4214 /// \param Chain Control flow dependency.
4215 /// \param Dst Pointer to destination memory location.
4216 /// \param Src Value of byte to write into the memory.
4217 /// \param Size Number of bytes to write.
4218 /// \param Align Alignment of the destination in bytes.
4219 /// \param isVol True if destination is volatile.
4220 /// \param DstPtrInfo IR information on the memory pointer.
4221 /// \returns New head in the control flow, if lowering was successful, empty
4222 /// SDValue otherwise.
4224 /// The function tries to replace 'llvm.memset' intrinsic with several store
4225 /// operations and value calculation code. This is usually profitable for small
4227 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4228 SDValue Chain, SDValue Dst,
4229 SDValue Src, uint64_t Size,
4230 unsigned Align, bool isVol,
4231 MachinePointerInfo DstPtrInfo) {
4232 // Turn a memset of undef to nop.
4233 if (Src.getOpcode() == ISD::UNDEF)
4236 // Expand memset to a series of load/store ops if the size operand
4237 // falls below a certain threshold.
4238 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4239 std::vector<EVT> MemOps;
4240 bool DstAlignCanChange = false;
4241 MachineFunction &MF = DAG.getMachineFunction();
4242 MachineFrameInfo *MFI = MF.getFrameInfo();
4243 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4244 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4245 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4246 DstAlignCanChange = true;
4248 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4249 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4250 Size, (DstAlignCanChange ? 0 : Align), 0,
4251 true, IsZeroVal, false, true, DAG, TLI))
4254 if (DstAlignCanChange) {
4255 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4256 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4257 if (NewAlign > Align) {
4258 // Give the stack frame object a larger alignment if needed.
4259 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4260 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4265 SmallVector<SDValue, 8> OutChains;
4266 uint64_t DstOff = 0;
4267 unsigned NumMemOps = MemOps.size();
4269 // Find the largest store and generate the bit pattern for it.
4270 EVT LargestVT = MemOps[0];
4271 for (unsigned i = 1; i < NumMemOps; i++)
4272 if (MemOps[i].bitsGT(LargestVT))
4273 LargestVT = MemOps[i];
4274 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4276 for (unsigned i = 0; i < NumMemOps; i++) {
4278 unsigned VTSize = VT.getSizeInBits() / 8;
4279 if (VTSize > Size) {
4280 // Issuing an unaligned load / store pair that overlaps with the previous
4281 // pair. Adjust the offset accordingly.
4282 assert(i == NumMemOps-1 && i != 0);
4283 DstOff -= VTSize - Size;
4286 // If this store is smaller than the largest store see whether we can get
4287 // the smaller value for free with a truncate.
4288 SDValue Value = MemSetValue;
4289 if (VT.bitsLT(LargestVT)) {
4290 if (!LargestVT.isVector() && !VT.isVector() &&
4291 TLI.isTruncateFree(LargestVT, VT))
4292 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4294 Value = getMemsetValue(Src, VT, DAG, dl);
4296 assert(Value.getValueType() == VT && "Value with wrong type.");
4297 SDValue Store = DAG.getStore(Chain, dl, Value,
4298 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4299 DstPtrInfo.getWithOffset(DstOff),
4300 isVol, false, Align);
4301 OutChains.push_back(Store);
4302 DstOff += VT.getSizeInBits() / 8;
4306 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4309 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4310 SDValue Src, SDValue Size,
4311 unsigned Align, bool isVol, bool AlwaysInline,
4312 bool isTailCall, MachinePointerInfo DstPtrInfo,
4313 MachinePointerInfo SrcPtrInfo) {
4314 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4316 // Check to see if we should lower the memcpy to loads and stores first.
4317 // For cases within the target-specified limits, this is the best choice.
4318 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4320 // Memcpy with size zero? Just return the original chain.
4321 if (ConstantSize->isNullValue())
4324 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4325 ConstantSize->getZExtValue(),Align,
4326 isVol, false, DstPtrInfo, SrcPtrInfo);
4327 if (Result.getNode())
4331 // Then check to see if we should lower the memcpy with target-specific
4332 // code. If the target chooses to do this, this is the next best.
4334 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4335 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4336 DstPtrInfo, SrcPtrInfo);
4337 if (Result.getNode())
4341 // If we really need inline code and the target declined to provide it,
4342 // use a (potentially long) sequence of loads and stores.
4344 assert(ConstantSize && "AlwaysInline requires a constant size!");
4345 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4346 ConstantSize->getZExtValue(), Align, isVol,
4347 true, DstPtrInfo, SrcPtrInfo);
4350 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4351 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4352 // respect volatile, so they may do things like read or write memory
4353 // beyond the given memory regions. But fixing this isn't easy, and most
4354 // people don't care.
4356 // Emit a library call.
4357 TargetLowering::ArgListTy Args;
4358 TargetLowering::ArgListEntry Entry;
4359 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4360 Entry.Node = Dst; Args.push_back(Entry);
4361 Entry.Node = Src; Args.push_back(Entry);
4362 Entry.Node = Size; Args.push_back(Entry);
4363 // FIXME: pass in SDLoc
4364 TargetLowering::CallLoweringInfo CLI(*this);
4365 CLI.setDebugLoc(dl).setChain(Chain)
4366 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4367 Type::getVoidTy(*getContext()),
4368 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4369 TLI->getPointerTy()), std::move(Args), 0)
4371 .setTailCall(isTailCall);
4373 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4374 return CallResult.second;
4377 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4378 SDValue Src, SDValue Size,
4379 unsigned Align, bool isVol, bool isTailCall,
4380 MachinePointerInfo DstPtrInfo,
4381 MachinePointerInfo SrcPtrInfo) {
4382 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4384 // Check to see if we should lower the memmove to loads and stores first.
4385 // For cases within the target-specified limits, this is the best choice.
4386 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4388 // Memmove with size zero? Just return the original chain.
4389 if (ConstantSize->isNullValue())
4393 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4394 ConstantSize->getZExtValue(), Align, isVol,
4395 false, DstPtrInfo, SrcPtrInfo);
4396 if (Result.getNode())
4400 // Then check to see if we should lower the memmove with target-specific
4401 // code. If the target chooses to do this, this is the next best.
4403 SDValue Result = TSI->EmitTargetCodeForMemmove(
4404 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4405 if (Result.getNode())
4409 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4410 // not be safe. See memcpy above for more details.
4412 // Emit a library call.
4413 TargetLowering::ArgListTy Args;
4414 TargetLowering::ArgListEntry Entry;
4415 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4416 Entry.Node = Dst; Args.push_back(Entry);
4417 Entry.Node = Src; Args.push_back(Entry);
4418 Entry.Node = Size; Args.push_back(Entry);
4419 // FIXME: pass in SDLoc
4420 TargetLowering::CallLoweringInfo CLI(*this);
4421 CLI.setDebugLoc(dl).setChain(Chain)
4422 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4423 Type::getVoidTy(*getContext()),
4424 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4425 TLI->getPointerTy()), std::move(Args), 0)
4427 .setTailCall(isTailCall);
4429 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4430 return CallResult.second;
4433 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4434 SDValue Src, SDValue Size,
4435 unsigned Align, bool isVol, bool isTailCall,
4436 MachinePointerInfo DstPtrInfo) {
4437 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4439 // Check to see if we should lower the memset to stores first.
4440 // For cases within the target-specified limits, this is the best choice.
4441 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4443 // Memset with size zero? Just return the original chain.
4444 if (ConstantSize->isNullValue())
4448 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4449 Align, isVol, DstPtrInfo);
4451 if (Result.getNode())
4455 // Then check to see if we should lower the memset with target-specific
4456 // code. If the target chooses to do this, this is the next best.
4458 SDValue Result = TSI->EmitTargetCodeForMemset(
4459 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4460 if (Result.getNode())
4464 // Emit a library call.
4465 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4466 TargetLowering::ArgListTy Args;
4467 TargetLowering::ArgListEntry Entry;
4468 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4469 Args.push_back(Entry);
4471 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4472 Args.push_back(Entry);
4474 Entry.Ty = IntPtrTy;
4475 Args.push_back(Entry);
4477 // FIXME: pass in SDLoc
4478 TargetLowering::CallLoweringInfo CLI(*this);
4479 CLI.setDebugLoc(dl).setChain(Chain)
4480 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4481 Type::getVoidTy(*getContext()),
4482 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4483 TLI->getPointerTy()), std::move(Args), 0)
4485 .setTailCall(isTailCall);
4487 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4488 return CallResult.second;
4491 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4492 SDVTList VTList, ArrayRef<SDValue> Ops,
4493 MachineMemOperand *MMO,
4494 AtomicOrdering SuccessOrdering,
4495 AtomicOrdering FailureOrdering,
4496 SynchronizationScope SynchScope) {
4497 FoldingSetNodeID ID;
4498 ID.AddInteger(MemVT.getRawBits());
4499 AddNodeIDNode(ID, Opcode, VTList, Ops);
4500 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4502 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4503 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4504 return SDValue(E, 0);
4507 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4508 // SDNode doesn't have access to it. This memory will be "leaked" when
4509 // the node is deallocated, but recovered when the allocator is released.
4510 // If the number of operands is less than 5 we use AtomicSDNode's internal
4512 unsigned NumOps = Ops.size();
4513 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4516 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4517 dl.getDebugLoc(), VTList, MemVT,
4518 Ops.data(), DynOps, NumOps, MMO,
4519 SuccessOrdering, FailureOrdering,
4521 CSEMap.InsertNode(N, IP);
4523 return SDValue(N, 0);
4526 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4527 SDVTList VTList, ArrayRef<SDValue> Ops,
4528 MachineMemOperand *MMO,
4529 AtomicOrdering Ordering,
4530 SynchronizationScope SynchScope) {
4531 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4532 Ordering, SynchScope);
4535 SDValue SelectionDAG::getAtomicCmpSwap(
4536 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4537 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4538 unsigned Alignment, AtomicOrdering SuccessOrdering,
4539 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4540 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4541 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4542 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4544 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4545 Alignment = getEVTAlignment(MemVT);
4547 MachineFunction &MF = getMachineFunction();
4549 // FIXME: Volatile isn't really correct; we should keep track of atomic
4550 // orderings in the memoperand.
4551 unsigned Flags = MachineMemOperand::MOVolatile;
4552 Flags |= MachineMemOperand::MOLoad;
4553 Flags |= MachineMemOperand::MOStore;
4555 MachineMemOperand *MMO =
4556 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4558 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4559 SuccessOrdering, FailureOrdering, SynchScope);
4562 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4563 SDVTList VTs, SDValue Chain, SDValue Ptr,
4564 SDValue Cmp, SDValue Swp,
4565 MachineMemOperand *MMO,
4566 AtomicOrdering SuccessOrdering,
4567 AtomicOrdering FailureOrdering,
4568 SynchronizationScope SynchScope) {
4569 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4570 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4571 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4573 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4574 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4575 SuccessOrdering, FailureOrdering, SynchScope);
4578 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4580 SDValue Ptr, SDValue Val,
4581 const Value* PtrVal,
4583 AtomicOrdering Ordering,
4584 SynchronizationScope SynchScope) {
4585 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4586 Alignment = getEVTAlignment(MemVT);
4588 MachineFunction &MF = getMachineFunction();
4589 // An atomic store does not load. An atomic load does not store.
4590 // (An atomicrmw obviously both loads and stores.)
4591 // For now, atomics are considered to be volatile always, and they are
4593 // FIXME: Volatile isn't really correct; we should keep track of atomic
4594 // orderings in the memoperand.
4595 unsigned Flags = MachineMemOperand::MOVolatile;
4596 if (Opcode != ISD::ATOMIC_STORE)
4597 Flags |= MachineMemOperand::MOLoad;
4598 if (Opcode != ISD::ATOMIC_LOAD)
4599 Flags |= MachineMemOperand::MOStore;
4601 MachineMemOperand *MMO =
4602 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4603 MemVT.getStoreSize(), Alignment);
4605 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4606 Ordering, SynchScope);
4609 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4611 SDValue Ptr, SDValue Val,
4612 MachineMemOperand *MMO,
4613 AtomicOrdering Ordering,
4614 SynchronizationScope SynchScope) {
4615 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4616 Opcode == ISD::ATOMIC_LOAD_SUB ||
4617 Opcode == ISD::ATOMIC_LOAD_AND ||
4618 Opcode == ISD::ATOMIC_LOAD_OR ||
4619 Opcode == ISD::ATOMIC_LOAD_XOR ||
4620 Opcode == ISD::ATOMIC_LOAD_NAND ||
4621 Opcode == ISD::ATOMIC_LOAD_MIN ||
4622 Opcode == ISD::ATOMIC_LOAD_MAX ||
4623 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4624 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4625 Opcode == ISD::ATOMIC_SWAP ||
4626 Opcode == ISD::ATOMIC_STORE) &&
4627 "Invalid Atomic Op");
4629 EVT VT = Val.getValueType();
4631 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4632 getVTList(VT, MVT::Other);
4633 SDValue Ops[] = {Chain, Ptr, Val};
4634 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4637 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4638 EVT VT, SDValue Chain,
4640 MachineMemOperand *MMO,
4641 AtomicOrdering Ordering,
4642 SynchronizationScope SynchScope) {
4643 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4645 SDVTList VTs = getVTList(VT, MVT::Other);
4646 SDValue Ops[] = {Chain, Ptr};
4647 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4650 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4651 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4652 if (Ops.size() == 1)
4655 SmallVector<EVT, 4> VTs;
4656 VTs.reserve(Ops.size());
4657 for (unsigned i = 0; i < Ops.size(); ++i)
4658 VTs.push_back(Ops[i].getValueType());
4659 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4663 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4664 ArrayRef<SDValue> Ops,
4665 EVT MemVT, MachinePointerInfo PtrInfo,
4666 unsigned Align, bool Vol,
4667 bool ReadMem, bool WriteMem, unsigned Size) {
4668 if (Align == 0) // Ensure that codegen never sees alignment 0
4669 Align = getEVTAlignment(MemVT);
4671 MachineFunction &MF = getMachineFunction();
4674 Flags |= MachineMemOperand::MOStore;
4676 Flags |= MachineMemOperand::MOLoad;
4678 Flags |= MachineMemOperand::MOVolatile;
4680 Size = MemVT.getStoreSize();
4681 MachineMemOperand *MMO =
4682 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4684 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4688 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4689 ArrayRef<SDValue> Ops, EVT MemVT,
4690 MachineMemOperand *MMO) {
4691 assert((Opcode == ISD::INTRINSIC_VOID ||
4692 Opcode == ISD::INTRINSIC_W_CHAIN ||
4693 Opcode == ISD::PREFETCH ||
4694 Opcode == ISD::LIFETIME_START ||
4695 Opcode == ISD::LIFETIME_END ||
4696 (Opcode <= INT_MAX &&
4697 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4698 "Opcode is not a memory-accessing opcode!");
4700 // Memoize the node unless it returns a flag.
4701 MemIntrinsicSDNode *N;
4702 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4703 FoldingSetNodeID ID;
4704 AddNodeIDNode(ID, Opcode, VTList, Ops);
4705 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4707 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4708 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4709 return SDValue(E, 0);
4712 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4713 dl.getDebugLoc(), VTList, Ops,
4715 CSEMap.InsertNode(N, IP);
4717 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4718 dl.getDebugLoc(), VTList, Ops,
4722 return SDValue(N, 0);
4725 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4726 /// MachinePointerInfo record from it. This is particularly useful because the
4727 /// code generator has many cases where it doesn't bother passing in a
4728 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4729 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4730 // If this is FI+Offset, we can model it.
4731 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4732 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4734 // If this is (FI+Offset1)+Offset2, we can model it.
4735 if (Ptr.getOpcode() != ISD::ADD ||
4736 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4737 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4738 return MachinePointerInfo();
4740 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4741 return MachinePointerInfo::getFixedStack(FI, Offset+
4742 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4745 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4746 /// MachinePointerInfo record from it. This is particularly useful because the
4747 /// code generator has many cases where it doesn't bother passing in a
4748 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4749 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4750 // If the 'Offset' value isn't a constant, we can't handle this.
4751 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4752 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4753 if (OffsetOp.getOpcode() == ISD::UNDEF)
4754 return InferPointerInfo(Ptr);
4755 return MachinePointerInfo();
4760 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4761 EVT VT, SDLoc dl, SDValue Chain,
4762 SDValue Ptr, SDValue Offset,
4763 MachinePointerInfo PtrInfo, EVT MemVT,
4764 bool isVolatile, bool isNonTemporal, bool isInvariant,
4765 unsigned Alignment, const AAMDNodes &AAInfo,
4766 const MDNode *Ranges) {
4767 assert(Chain.getValueType() == MVT::Other &&
4768 "Invalid chain type");
4769 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4770 Alignment = getEVTAlignment(VT);
4772 unsigned Flags = MachineMemOperand::MOLoad;
4774 Flags |= MachineMemOperand::MOVolatile;
4776 Flags |= MachineMemOperand::MONonTemporal;
4778 Flags |= MachineMemOperand::MOInvariant;
4780 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4782 if (PtrInfo.V.isNull())
4783 PtrInfo = InferPointerInfo(Ptr, Offset);
4785 MachineFunction &MF = getMachineFunction();
4786 MachineMemOperand *MMO =
4787 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4789 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4793 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4794 EVT VT, SDLoc dl, SDValue Chain,
4795 SDValue Ptr, SDValue Offset, EVT MemVT,
4796 MachineMemOperand *MMO) {
4798 ExtType = ISD::NON_EXTLOAD;
4799 } else if (ExtType == ISD::NON_EXTLOAD) {
4800 assert(VT == MemVT && "Non-extending load from different memory type!");
4803 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4804 "Should only be an extending load, not truncating!");
4805 assert(VT.isInteger() == MemVT.isInteger() &&
4806 "Cannot convert from FP to Int or Int -> FP!");
4807 assert(VT.isVector() == MemVT.isVector() &&
4808 "Cannot use an ext load to convert to or from a vector!");
4809 assert((!VT.isVector() ||
4810 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4811 "Cannot use an ext load to change the number of vector elements!");
4814 bool Indexed = AM != ISD::UNINDEXED;
4815 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4816 "Unindexed load with an offset!");
4818 SDVTList VTs = Indexed ?
4819 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4820 SDValue Ops[] = { Chain, Ptr, Offset };
4821 FoldingSetNodeID ID;
4822 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4823 ID.AddInteger(MemVT.getRawBits());
4824 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4825 MMO->isNonTemporal(),
4826 MMO->isInvariant()));
4827 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4829 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4830 cast<LoadSDNode>(E)->refineAlignment(MMO);
4831 return SDValue(E, 0);
4833 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4834 dl.getDebugLoc(), VTs, AM, ExtType,
4836 CSEMap.InsertNode(N, IP);
4838 return SDValue(N, 0);
4841 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4842 SDValue Chain, SDValue Ptr,
4843 MachinePointerInfo PtrInfo,
4844 bool isVolatile, bool isNonTemporal,
4845 bool isInvariant, unsigned Alignment,
4846 const AAMDNodes &AAInfo,
4847 const MDNode *Ranges) {
4848 SDValue Undef = getUNDEF(Ptr.getValueType());
4849 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4850 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4854 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4855 SDValue Chain, SDValue Ptr,
4856 MachineMemOperand *MMO) {
4857 SDValue Undef = getUNDEF(Ptr.getValueType());
4858 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4862 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4863 SDValue Chain, SDValue Ptr,
4864 MachinePointerInfo PtrInfo, EVT MemVT,
4865 bool isVolatile, bool isNonTemporal,
4866 bool isInvariant, unsigned Alignment,
4867 const AAMDNodes &AAInfo) {
4868 SDValue Undef = getUNDEF(Ptr.getValueType());
4869 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4870 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4875 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4876 SDValue Chain, SDValue Ptr, EVT MemVT,
4877 MachineMemOperand *MMO) {
4878 SDValue Undef = getUNDEF(Ptr.getValueType());
4879 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4884 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4885 SDValue Offset, ISD::MemIndexedMode AM) {
4886 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4887 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4888 "Load is already a indexed load!");
4889 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4890 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4891 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4892 false, LD->getAlignment());
4895 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4896 SDValue Ptr, MachinePointerInfo PtrInfo,
4897 bool isVolatile, bool isNonTemporal,
4898 unsigned Alignment, const AAMDNodes &AAInfo) {
4899 assert(Chain.getValueType() == MVT::Other &&
4900 "Invalid chain type");
4901 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4902 Alignment = getEVTAlignment(Val.getValueType());
4904 unsigned Flags = MachineMemOperand::MOStore;
4906 Flags |= MachineMemOperand::MOVolatile;
4908 Flags |= MachineMemOperand::MONonTemporal;
4910 if (PtrInfo.V.isNull())
4911 PtrInfo = InferPointerInfo(Ptr);
4913 MachineFunction &MF = getMachineFunction();
4914 MachineMemOperand *MMO =
4915 MF.getMachineMemOperand(PtrInfo, Flags,
4916 Val.getValueType().getStoreSize(), Alignment,
4919 return getStore(Chain, dl, Val, Ptr, MMO);
4922 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4923 SDValue Ptr, MachineMemOperand *MMO) {
4924 assert(Chain.getValueType() == MVT::Other &&
4925 "Invalid chain type");
4926 EVT VT = Val.getValueType();
4927 SDVTList VTs = getVTList(MVT::Other);
4928 SDValue Undef = getUNDEF(Ptr.getValueType());
4929 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4930 FoldingSetNodeID ID;
4931 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4932 ID.AddInteger(VT.getRawBits());
4933 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4934 MMO->isNonTemporal(), MMO->isInvariant()));
4935 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4937 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4938 cast<StoreSDNode>(E)->refineAlignment(MMO);
4939 return SDValue(E, 0);
4941 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4942 dl.getDebugLoc(), VTs,
4943 ISD::UNINDEXED, false, VT, MMO);
4944 CSEMap.InsertNode(N, IP);
4946 return SDValue(N, 0);
4949 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4950 SDValue Ptr, MachinePointerInfo PtrInfo,
4951 EVT SVT,bool isVolatile, bool isNonTemporal,
4953 const AAMDNodes &AAInfo) {
4954 assert(Chain.getValueType() == MVT::Other &&
4955 "Invalid chain type");
4956 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4957 Alignment = getEVTAlignment(SVT);
4959 unsigned Flags = MachineMemOperand::MOStore;
4961 Flags |= MachineMemOperand::MOVolatile;
4963 Flags |= MachineMemOperand::MONonTemporal;
4965 if (PtrInfo.V.isNull())
4966 PtrInfo = InferPointerInfo(Ptr);
4968 MachineFunction &MF = getMachineFunction();
4969 MachineMemOperand *MMO =
4970 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4973 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4976 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4977 SDValue Ptr, EVT SVT,
4978 MachineMemOperand *MMO) {
4979 EVT VT = Val.getValueType();
4981 assert(Chain.getValueType() == MVT::Other &&
4982 "Invalid chain type");
4984 return getStore(Chain, dl, Val, Ptr, MMO);
4986 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4987 "Should only be a truncating store, not extending!");
4988 assert(VT.isInteger() == SVT.isInteger() &&
4989 "Can't do FP-INT conversion!");
4990 assert(VT.isVector() == SVT.isVector() &&
4991 "Cannot use trunc store to convert to or from a vector!");
4992 assert((!VT.isVector() ||
4993 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4994 "Cannot use trunc store to change the number of vector elements!");
4996 SDVTList VTs = getVTList(MVT::Other);
4997 SDValue Undef = getUNDEF(Ptr.getValueType());
4998 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4999 FoldingSetNodeID ID;
5000 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5001 ID.AddInteger(SVT.getRawBits());
5002 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5003 MMO->isNonTemporal(), MMO->isInvariant()));
5004 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5006 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5007 cast<StoreSDNode>(E)->refineAlignment(MMO);
5008 return SDValue(E, 0);
5010 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5011 dl.getDebugLoc(), VTs,
5012 ISD::UNINDEXED, true, SVT, MMO);
5013 CSEMap.InsertNode(N, IP);
5015 return SDValue(N, 0);
5019 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5020 SDValue Offset, ISD::MemIndexedMode AM) {
5021 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5022 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5023 "Store is already a indexed store!");
5024 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5025 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5026 FoldingSetNodeID ID;
5027 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5028 ID.AddInteger(ST->getMemoryVT().getRawBits());
5029 ID.AddInteger(ST->getRawSubclassData());
5030 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5032 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5033 return SDValue(E, 0);
5035 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5036 dl.getDebugLoc(), VTs, AM,
5037 ST->isTruncatingStore(),
5039 ST->getMemOperand());
5040 CSEMap.InsertNode(N, IP);
5042 return SDValue(N, 0);
5046 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5047 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5048 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5050 SDVTList VTs = getVTList(VT, MVT::Other);
5051 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5052 FoldingSetNodeID ID;
5053 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5054 ID.AddInteger(VT.getRawBits());
5055 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5057 MMO->isNonTemporal(),
5058 MMO->isInvariant()));
5059 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5061 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5062 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5063 return SDValue(E, 0);
5065 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5066 dl.getDebugLoc(), Ops, 4, VTs,
5068 CSEMap.InsertNode(N, IP);
5070 return SDValue(N, 0);
5073 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5074 SDValue Ptr, SDValue Mask, EVT MemVT,
5075 MachineMemOperand *MMO, bool isTrunc) {
5076 assert(Chain.getValueType() == MVT::Other &&
5077 "Invalid chain type");
5078 EVT VT = Val.getValueType();
5079 SDVTList VTs = getVTList(MVT::Other);
5080 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5081 FoldingSetNodeID ID;
5082 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5083 ID.AddInteger(VT.getRawBits());
5084 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5085 MMO->isNonTemporal(), MMO->isInvariant()));
5086 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5088 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5089 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5090 return SDValue(E, 0);
5092 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5093 dl.getDebugLoc(), Ops, 4,
5094 VTs, isTrunc, MemVT, MMO);
5095 CSEMap.InsertNode(N, IP);
5097 return SDValue(N, 0);
5100 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5101 SDValue Chain, SDValue Ptr,
5104 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
5105 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5108 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5109 ArrayRef<SDUse> Ops) {
5110 switch (Ops.size()) {
5111 case 0: return getNode(Opcode, DL, VT);
5112 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5113 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5114 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5118 // Copy from an SDUse array into an SDValue array for use with
5119 // the regular getNode logic.
5120 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5121 return getNode(Opcode, DL, VT, NewOps);
5124 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5125 ArrayRef<SDValue> Ops) {
5126 unsigned NumOps = Ops.size();
5128 case 0: return getNode(Opcode, DL, VT);
5129 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5130 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5131 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5137 case ISD::SELECT_CC: {
5138 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5139 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5140 "LHS and RHS of condition must have same type!");
5141 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5142 "True and False arms of SelectCC must have same type!");
5143 assert(Ops[2].getValueType() == VT &&
5144 "select_cc node must be of same type as true and false value!");
5148 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5149 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5150 "LHS/RHS of comparison should match types!");
5157 SDVTList VTs = getVTList(VT);
5159 if (VT != MVT::Glue) {
5160 FoldingSetNodeID ID;
5161 AddNodeIDNode(ID, Opcode, VTs, Ops);
5164 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5165 return SDValue(E, 0);
5167 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5169 CSEMap.InsertNode(N, IP);
5171 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5176 return SDValue(N, 0);
5179 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5180 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5181 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5184 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5185 ArrayRef<SDValue> Ops) {
5186 if (VTList.NumVTs == 1)
5187 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5191 // FIXME: figure out how to safely handle things like
5192 // int foo(int x) { return 1 << (x & 255); }
5193 // int bar() { return foo(256); }
5194 case ISD::SRA_PARTS:
5195 case ISD::SRL_PARTS:
5196 case ISD::SHL_PARTS:
5197 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5198 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5199 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5200 else if (N3.getOpcode() == ISD::AND)
5201 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5202 // If the and is only masking out bits that cannot effect the shift,
5203 // eliminate the and.
5204 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5205 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5206 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5212 // Memoize the node unless it returns a flag.
5214 unsigned NumOps = Ops.size();
5215 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5216 FoldingSetNodeID ID;
5217 AddNodeIDNode(ID, Opcode, VTList, Ops);
5219 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5220 return SDValue(E, 0);
5223 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5224 DL.getDebugLoc(), VTList, Ops[0]);
5225 } else if (NumOps == 2) {
5226 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5227 DL.getDebugLoc(), VTList, Ops[0],
5229 } else if (NumOps == 3) {
5230 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5231 DL.getDebugLoc(), VTList, Ops[0],
5234 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5237 CSEMap.InsertNode(N, IP);
5240 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5241 DL.getDebugLoc(), VTList, Ops[0]);
5242 } else if (NumOps == 2) {
5243 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5244 DL.getDebugLoc(), VTList, Ops[0],
5246 } else if (NumOps == 3) {
5247 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5248 DL.getDebugLoc(), VTList, Ops[0],
5251 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5256 return SDValue(N, 0);
5259 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5260 return getNode(Opcode, DL, VTList, None);
5263 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5265 SDValue Ops[] = { N1 };
5266 return getNode(Opcode, DL, VTList, Ops);
5269 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5270 SDValue N1, SDValue N2) {
5271 SDValue Ops[] = { N1, N2 };
5272 return getNode(Opcode, DL, VTList, Ops);
5275 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5276 SDValue N1, SDValue N2, SDValue N3) {
5277 SDValue Ops[] = { N1, N2, N3 };
5278 return getNode(Opcode, DL, VTList, Ops);
5281 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5282 SDValue N1, SDValue N2, SDValue N3,
5284 SDValue Ops[] = { N1, N2, N3, N4 };
5285 return getNode(Opcode, DL, VTList, Ops);
5288 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5289 SDValue N1, SDValue N2, SDValue N3,
5290 SDValue N4, SDValue N5) {
5291 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5292 return getNode(Opcode, DL, VTList, Ops);
5295 SDVTList SelectionDAG::getVTList(EVT VT) {
5296 return makeVTList(SDNode::getValueTypeList(VT), 1);
5299 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5300 FoldingSetNodeID ID;
5302 ID.AddInteger(VT1.getRawBits());
5303 ID.AddInteger(VT2.getRawBits());
5306 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5308 EVT *Array = Allocator.Allocate<EVT>(2);
5311 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5312 VTListMap.InsertNode(Result, IP);
5314 return Result->getSDVTList();
5317 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5318 FoldingSetNodeID ID;
5320 ID.AddInteger(VT1.getRawBits());
5321 ID.AddInteger(VT2.getRawBits());
5322 ID.AddInteger(VT3.getRawBits());
5325 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5327 EVT *Array = Allocator.Allocate<EVT>(3);
5331 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5332 VTListMap.InsertNode(Result, IP);
5334 return Result->getSDVTList();
5337 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5338 FoldingSetNodeID ID;
5340 ID.AddInteger(VT1.getRawBits());
5341 ID.AddInteger(VT2.getRawBits());
5342 ID.AddInteger(VT3.getRawBits());
5343 ID.AddInteger(VT4.getRawBits());
5346 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5348 EVT *Array = Allocator.Allocate<EVT>(4);
5353 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5354 VTListMap.InsertNode(Result, IP);
5356 return Result->getSDVTList();
5359 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5360 unsigned NumVTs = VTs.size();
5361 FoldingSetNodeID ID;
5362 ID.AddInteger(NumVTs);
5363 for (unsigned index = 0; index < NumVTs; index++) {
5364 ID.AddInteger(VTs[index].getRawBits());
5368 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5370 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5371 std::copy(VTs.begin(), VTs.end(), Array);
5372 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5373 VTListMap.InsertNode(Result, IP);
5375 return Result->getSDVTList();
5379 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5380 /// specified operands. If the resultant node already exists in the DAG,
5381 /// this does not modify the specified node, instead it returns the node that
5382 /// already exists. If the resultant node does not exist in the DAG, the
5383 /// input node is returned. As a degenerate case, if you specify the same
5384 /// input operands as the node already has, the input node is returned.
5385 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5386 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5388 // Check to see if there is no change.
5389 if (Op == N->getOperand(0)) return N;
5391 // See if the modified node already exists.
5392 void *InsertPos = nullptr;
5393 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5396 // Nope it doesn't. Remove the node from its current place in the maps.
5398 if (!RemoveNodeFromCSEMaps(N))
5399 InsertPos = nullptr;
5401 // Now we update the operands.
5402 N->OperandList[0].set(Op);
5404 // If this gets put into a CSE map, add it.
5405 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5409 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5410 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5412 // Check to see if there is no change.
5413 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5414 return N; // No operands changed, just return the input node.
5416 // See if the modified node already exists.
5417 void *InsertPos = nullptr;
5418 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5421 // Nope it doesn't. Remove the node from its current place in the maps.
5423 if (!RemoveNodeFromCSEMaps(N))
5424 InsertPos = nullptr;
5426 // Now we update the operands.
5427 if (N->OperandList[0] != Op1)
5428 N->OperandList[0].set(Op1);
5429 if (N->OperandList[1] != Op2)
5430 N->OperandList[1].set(Op2);
5432 // If this gets put into a CSE map, add it.
5433 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5437 SDNode *SelectionDAG::
5438 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5439 SDValue Ops[] = { Op1, Op2, Op3 };
5440 return UpdateNodeOperands(N, Ops);
5443 SDNode *SelectionDAG::
5444 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5445 SDValue Op3, SDValue Op4) {
5446 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5447 return UpdateNodeOperands(N, Ops);
5450 SDNode *SelectionDAG::
5451 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5452 SDValue Op3, SDValue Op4, SDValue Op5) {
5453 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5454 return UpdateNodeOperands(N, Ops);
5457 SDNode *SelectionDAG::
5458 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5459 unsigned NumOps = Ops.size();
5460 assert(N->getNumOperands() == NumOps &&
5461 "Update with wrong number of operands");
5463 // If no operands changed just return the input node.
5464 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5467 // See if the modified node already exists.
5468 void *InsertPos = nullptr;
5469 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5472 // Nope it doesn't. Remove the node from its current place in the maps.
5474 if (!RemoveNodeFromCSEMaps(N))
5475 InsertPos = nullptr;
5477 // Now we update the operands.
5478 for (unsigned i = 0; i != NumOps; ++i)
5479 if (N->OperandList[i] != Ops[i])
5480 N->OperandList[i].set(Ops[i]);
5482 // If this gets put into a CSE map, add it.
5483 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5487 /// DropOperands - Release the operands and set this node to have
5489 void SDNode::DropOperands() {
5490 // Unlike the code in MorphNodeTo that does this, we don't need to
5491 // watch for dead nodes here.
5492 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5498 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5501 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5503 SDVTList VTs = getVTList(VT);
5504 return SelectNodeTo(N, MachineOpc, VTs, None);
5507 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5508 EVT VT, SDValue Op1) {
5509 SDVTList VTs = getVTList(VT);
5510 SDValue Ops[] = { Op1 };
5511 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5514 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5515 EVT VT, SDValue Op1,
5517 SDVTList VTs = getVTList(VT);
5518 SDValue Ops[] = { Op1, Op2 };
5519 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5522 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5523 EVT VT, SDValue Op1,
5524 SDValue Op2, SDValue Op3) {
5525 SDVTList VTs = getVTList(VT);
5526 SDValue Ops[] = { Op1, Op2, Op3 };
5527 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5530 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5531 EVT VT, ArrayRef<SDValue> Ops) {
5532 SDVTList VTs = getVTList(VT);
5533 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5536 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5537 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5538 SDVTList VTs = getVTList(VT1, VT2);
5539 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5542 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5544 SDVTList VTs = getVTList(VT1, VT2);
5545 return SelectNodeTo(N, MachineOpc, VTs, None);
5548 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5549 EVT VT1, EVT VT2, EVT VT3,
5550 ArrayRef<SDValue> Ops) {
5551 SDVTList VTs = getVTList(VT1, VT2, VT3);
5552 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5555 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5556 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5557 ArrayRef<SDValue> Ops) {
5558 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5559 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5562 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5565 SDVTList VTs = getVTList(VT1, VT2);
5566 SDValue Ops[] = { Op1 };
5567 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5570 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5572 SDValue Op1, SDValue Op2) {
5573 SDVTList VTs = getVTList(VT1, VT2);
5574 SDValue Ops[] = { Op1, Op2 };
5575 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5578 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5580 SDValue Op1, SDValue Op2,
5582 SDVTList VTs = getVTList(VT1, VT2);
5583 SDValue Ops[] = { Op1, Op2, Op3 };
5584 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5587 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5588 EVT VT1, EVT VT2, EVT VT3,
5589 SDValue Op1, SDValue Op2,
5591 SDVTList VTs = getVTList(VT1, VT2, VT3);
5592 SDValue Ops[] = { Op1, Op2, Op3 };
5593 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5596 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5597 SDVTList VTs,ArrayRef<SDValue> Ops) {
5598 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5599 // Reset the NodeID to -1.
5604 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5605 /// the line number information on the merged node since it is not possible to
5606 /// preserve the information that operation is associated with multiple lines.
5607 /// This will make the debugger working better at -O0, were there is a higher
5608 /// probability having other instructions associated with that line.
5610 /// For IROrder, we keep the smaller of the two
5611 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5612 DebugLoc NLoc = N->getDebugLoc();
5613 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5614 N->setDebugLoc(DebugLoc());
5616 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5617 N->setIROrder(Order);
5621 /// MorphNodeTo - This *mutates* the specified node to have the specified
5622 /// return type, opcode, and operands.
5624 /// Note that MorphNodeTo returns the resultant node. If there is already a
5625 /// node of the specified opcode and operands, it returns that node instead of
5626 /// the current one. Note that the SDLoc need not be the same.
5628 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5629 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5630 /// node, and because it doesn't require CSE recalculation for any of
5631 /// the node's users.
5633 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5634 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5635 /// the legalizer which maintain worklists that would need to be updated when
5636 /// deleting things.
5637 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5638 SDVTList VTs, ArrayRef<SDValue> Ops) {
5639 unsigned NumOps = Ops.size();
5640 // If an identical node already exists, use it.
5642 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5643 FoldingSetNodeID ID;
5644 AddNodeIDNode(ID, Opc, VTs, Ops);
5645 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5646 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5649 if (!RemoveNodeFromCSEMaps(N))
5652 // Start the morphing.
5654 N->ValueList = VTs.VTs;
5655 N->NumValues = VTs.NumVTs;
5657 // Clear the operands list, updating used nodes to remove this from their
5658 // use list. Keep track of any operands that become dead as a result.
5659 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5660 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5662 SDNode *Used = Use.getNode();
5664 if (Used->use_empty())
5665 DeadNodeSet.insert(Used);
5668 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5669 // Initialize the memory references information.
5670 MN->setMemRefs(nullptr, nullptr);
5671 // If NumOps is larger than the # of operands we can have in a
5672 // MachineSDNode, reallocate the operand list.
5673 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5674 if (MN->OperandsNeedDelete)
5675 delete[] MN->OperandList;
5676 if (NumOps > array_lengthof(MN->LocalOperands))
5677 // We're creating a final node that will live unmorphed for the
5678 // remainder of the current SelectionDAG iteration, so we can allocate
5679 // the operands directly out of a pool with no recycling metadata.
5680 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5681 Ops.data(), NumOps);
5683 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5684 MN->OperandsNeedDelete = false;
5686 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5688 // If NumOps is larger than the # of operands we currently have, reallocate
5689 // the operand list.
5690 if (NumOps > N->NumOperands) {
5691 if (N->OperandsNeedDelete)
5692 delete[] N->OperandList;
5693 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5694 N->OperandsNeedDelete = true;
5696 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5699 // Delete any nodes that are still dead after adding the uses for the
5701 if (!DeadNodeSet.empty()) {
5702 SmallVector<SDNode *, 16> DeadNodes;
5703 for (SDNode *N : DeadNodeSet)
5705 DeadNodes.push_back(N);
5706 RemoveDeadNodes(DeadNodes);
5710 CSEMap.InsertNode(N, IP); // Memoize the new node.
5715 /// getMachineNode - These are used for target selectors to create a new node
5716 /// with specified return type(s), MachineInstr opcode, and operands.
5718 /// Note that getMachineNode returns the resultant node. If there is already a
5719 /// node of the specified opcode and operands, it returns that node instead of
5720 /// the current one.
5722 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5723 SDVTList VTs = getVTList(VT);
5724 return getMachineNode(Opcode, dl, VTs, None);
5728 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5729 SDVTList VTs = getVTList(VT);
5730 SDValue Ops[] = { Op1 };
5731 return getMachineNode(Opcode, dl, VTs, Ops);
5735 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5736 SDValue Op1, SDValue Op2) {
5737 SDVTList VTs = getVTList(VT);
5738 SDValue Ops[] = { Op1, Op2 };
5739 return getMachineNode(Opcode, dl, VTs, Ops);
5743 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5744 SDValue Op1, SDValue Op2, SDValue Op3) {
5745 SDVTList VTs = getVTList(VT);
5746 SDValue Ops[] = { Op1, Op2, Op3 };
5747 return getMachineNode(Opcode, dl, VTs, Ops);
5751 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5752 ArrayRef<SDValue> Ops) {
5753 SDVTList VTs = getVTList(VT);
5754 return getMachineNode(Opcode, dl, VTs, Ops);
5758 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5759 SDVTList VTs = getVTList(VT1, VT2);
5760 return getMachineNode(Opcode, dl, VTs, None);
5764 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5765 EVT VT1, EVT VT2, SDValue Op1) {
5766 SDVTList VTs = getVTList(VT1, VT2);
5767 SDValue Ops[] = { Op1 };
5768 return getMachineNode(Opcode, dl, VTs, Ops);
5772 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5773 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5774 SDVTList VTs = getVTList(VT1, VT2);
5775 SDValue Ops[] = { Op1, Op2 };
5776 return getMachineNode(Opcode, dl, VTs, Ops);
5780 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5781 EVT VT1, EVT VT2, SDValue Op1,
5782 SDValue Op2, SDValue Op3) {
5783 SDVTList VTs = getVTList(VT1, VT2);
5784 SDValue Ops[] = { Op1, Op2, Op3 };
5785 return getMachineNode(Opcode, dl, VTs, Ops);
5789 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5791 ArrayRef<SDValue> Ops) {
5792 SDVTList VTs = getVTList(VT1, VT2);
5793 return getMachineNode(Opcode, dl, VTs, Ops);
5797 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5798 EVT VT1, EVT VT2, EVT VT3,
5799 SDValue Op1, SDValue Op2) {
5800 SDVTList VTs = getVTList(VT1, VT2, VT3);
5801 SDValue Ops[] = { Op1, Op2 };
5802 return getMachineNode(Opcode, dl, VTs, Ops);
5806 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5807 EVT VT1, EVT VT2, EVT VT3,
5808 SDValue Op1, SDValue Op2, SDValue Op3) {
5809 SDVTList VTs = getVTList(VT1, VT2, VT3);
5810 SDValue Ops[] = { Op1, Op2, Op3 };
5811 return getMachineNode(Opcode, dl, VTs, Ops);
5815 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5816 EVT VT1, EVT VT2, EVT VT3,
5817 ArrayRef<SDValue> Ops) {
5818 SDVTList VTs = getVTList(VT1, VT2, VT3);
5819 return getMachineNode(Opcode, dl, VTs, Ops);
5823 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5824 EVT VT2, EVT VT3, EVT VT4,
5825 ArrayRef<SDValue> Ops) {
5826 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5827 return getMachineNode(Opcode, dl, VTs, Ops);
5831 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5832 ArrayRef<EVT> ResultTys,
5833 ArrayRef<SDValue> Ops) {
5834 SDVTList VTs = getVTList(ResultTys);
5835 return getMachineNode(Opcode, dl, VTs, Ops);
5839 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5840 ArrayRef<SDValue> OpsArray) {
5841 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5844 const SDValue *Ops = OpsArray.data();
5845 unsigned NumOps = OpsArray.size();
5848 FoldingSetNodeID ID;
5849 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5851 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5852 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5856 // Allocate a new MachineSDNode.
5857 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5858 DL.getDebugLoc(), VTs);
5860 // Initialize the operands list.
5861 if (NumOps > array_lengthof(N->LocalOperands))
5862 // We're creating a final node that will live unmorphed for the
5863 // remainder of the current SelectionDAG iteration, so we can allocate
5864 // the operands directly out of a pool with no recycling metadata.
5865 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5868 N->InitOperands(N->LocalOperands, Ops, NumOps);
5869 N->OperandsNeedDelete = false;
5872 CSEMap.InsertNode(N, IP);
5878 /// getTargetExtractSubreg - A convenience function for creating
5879 /// TargetOpcode::EXTRACT_SUBREG nodes.
5881 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5883 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5884 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5885 VT, Operand, SRIdxVal);
5886 return SDValue(Subreg, 0);
5889 /// getTargetInsertSubreg - A convenience function for creating
5890 /// TargetOpcode::INSERT_SUBREG nodes.
5892 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5893 SDValue Operand, SDValue Subreg) {
5894 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5895 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5896 VT, Operand, Subreg, SRIdxVal);
5897 return SDValue(Result, 0);
5900 /// getNodeIfExists - Get the specified node if it's already available, or
5901 /// else return NULL.
5902 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5903 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5905 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5906 FoldingSetNodeID ID;
5907 AddNodeIDNode(ID, Opcode, VTList, Ops);
5908 if (isBinOpWithFlags(Opcode))
5909 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5911 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5917 /// getDbgValue - Creates a SDDbgValue node.
5920 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5921 unsigned R, bool IsIndirect, uint64_t Off,
5922 DebugLoc DL, unsigned O) {
5923 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5924 "Expected inlined-at fields to agree");
5925 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5929 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5930 const Value *C, uint64_t Off,
5931 DebugLoc DL, unsigned O) {
5932 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5933 "Expected inlined-at fields to agree");
5934 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
5938 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
5939 unsigned FI, uint64_t Off,
5940 DebugLoc DL, unsigned O) {
5941 assert(cast<MDLocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5942 "Expected inlined-at fields to agree");
5943 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
5948 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5949 /// pointed to by a use iterator is deleted, increment the use iterator
5950 /// so that it doesn't dangle.
5952 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5953 SDNode::use_iterator &UI;
5954 SDNode::use_iterator &UE;
5956 void NodeDeleted(SDNode *N, SDNode *E) override {
5957 // Increment the iterator as needed.
5958 while (UI != UE && N == *UI)
5963 RAUWUpdateListener(SelectionDAG &d,
5964 SDNode::use_iterator &ui,
5965 SDNode::use_iterator &ue)
5966 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5971 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5972 /// This can cause recursive merging of nodes in the DAG.
5974 /// This version assumes From has a single result value.
5976 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5977 SDNode *From = FromN.getNode();
5978 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5979 "Cannot replace with this method!");
5980 assert(From != To.getNode() && "Cannot replace uses of with self");
5982 // Iterate over all the existing uses of From. New uses will be added
5983 // to the beginning of the use list, which we avoid visiting.
5984 // This specifically avoids visiting uses of From that arise while the
5985 // replacement is happening, because any such uses would be the result
5986 // of CSE: If an existing node looks like From after one of its operands
5987 // is replaced by To, we don't want to replace of all its users with To
5988 // too. See PR3018 for more info.
5989 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5990 RAUWUpdateListener Listener(*this, UI, UE);
5994 // This node is about to morph, remove its old self from the CSE maps.
5995 RemoveNodeFromCSEMaps(User);
5997 // A user can appear in a use list multiple times, and when this
5998 // happens the uses are usually next to each other in the list.
5999 // To help reduce the number of CSE recomputations, process all
6000 // the uses of this user that we can find this way.
6002 SDUse &Use = UI.getUse();
6005 } while (UI != UE && *UI == User);
6007 // Now that we have modified User, add it back to the CSE maps. If it
6008 // already exists there, recursively merge the results together.
6009 AddModifiedNodeToCSEMaps(User);
6012 // If we just RAUW'd the root, take note.
6013 if (FromN == getRoot())
6017 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6018 /// This can cause recursive merging of nodes in the DAG.
6020 /// This version assumes that for each value of From, there is a
6021 /// corresponding value in To in the same position with the same type.
6023 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6025 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6026 assert((!From->hasAnyUseOfValue(i) ||
6027 From->getValueType(i) == To->getValueType(i)) &&
6028 "Cannot use this version of ReplaceAllUsesWith!");
6031 // Handle the trivial case.
6035 // Iterate over just the existing users of From. See the comments in
6036 // the ReplaceAllUsesWith above.
6037 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6038 RAUWUpdateListener Listener(*this, UI, UE);
6042 // This node is about to morph, remove its old self from the CSE maps.
6043 RemoveNodeFromCSEMaps(User);
6045 // A user can appear in a use list multiple times, and when this
6046 // happens the uses are usually next to each other in the list.
6047 // To help reduce the number of CSE recomputations, process all
6048 // the uses of this user that we can find this way.
6050 SDUse &Use = UI.getUse();
6053 } while (UI != UE && *UI == User);
6055 // Now that we have modified User, add it back to the CSE maps. If it
6056 // already exists there, recursively merge the results together.
6057 AddModifiedNodeToCSEMaps(User);
6060 // If we just RAUW'd the root, take note.
6061 if (From == getRoot().getNode())
6062 setRoot(SDValue(To, getRoot().getResNo()));
6065 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6066 /// This can cause recursive merging of nodes in the DAG.
6068 /// This version can replace From with any result values. To must match the
6069 /// number and types of values returned by From.
6070 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6071 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6072 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6074 // Iterate over just the existing users of From. See the comments in
6075 // the ReplaceAllUsesWith above.
6076 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6077 RAUWUpdateListener Listener(*this, UI, UE);
6081 // This node is about to morph, remove its old self from the CSE maps.
6082 RemoveNodeFromCSEMaps(User);
6084 // A user can appear in a use list multiple times, and when this
6085 // happens the uses are usually next to each other in the list.
6086 // To help reduce the number of CSE recomputations, process all
6087 // the uses of this user that we can find this way.
6089 SDUse &Use = UI.getUse();
6090 const SDValue &ToOp = To[Use.getResNo()];
6093 } while (UI != UE && *UI == User);
6095 // Now that we have modified User, add it back to the CSE maps. If it
6096 // already exists there, recursively merge the results together.
6097 AddModifiedNodeToCSEMaps(User);
6100 // If we just RAUW'd the root, take note.
6101 if (From == getRoot().getNode())
6102 setRoot(SDValue(To[getRoot().getResNo()]));
6105 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6106 /// uses of other values produced by From.getNode() alone. The Deleted
6107 /// vector is handled the same way as for ReplaceAllUsesWith.
6108 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6109 // Handle the really simple, really trivial case efficiently.
6110 if (From == To) return;
6112 // Handle the simple, trivial, case efficiently.
6113 if (From.getNode()->getNumValues() == 1) {
6114 ReplaceAllUsesWith(From, To);
6118 // Iterate over just the existing users of From. See the comments in
6119 // the ReplaceAllUsesWith above.
6120 SDNode::use_iterator UI = From.getNode()->use_begin(),
6121 UE = From.getNode()->use_end();
6122 RAUWUpdateListener Listener(*this, UI, UE);
6125 bool UserRemovedFromCSEMaps = false;
6127 // A user can appear in a use list multiple times, and when this
6128 // happens the uses are usually next to each other in the list.
6129 // To help reduce the number of CSE recomputations, process all
6130 // the uses of this user that we can find this way.
6132 SDUse &Use = UI.getUse();
6134 // Skip uses of different values from the same node.
6135 if (Use.getResNo() != From.getResNo()) {
6140 // If this node hasn't been modified yet, it's still in the CSE maps,
6141 // so remove its old self from the CSE maps.
6142 if (!UserRemovedFromCSEMaps) {
6143 RemoveNodeFromCSEMaps(User);
6144 UserRemovedFromCSEMaps = true;
6149 } while (UI != UE && *UI == User);
6151 // We are iterating over all uses of the From node, so if a use
6152 // doesn't use the specific value, no changes are made.
6153 if (!UserRemovedFromCSEMaps)
6156 // Now that we have modified User, add it back to the CSE maps. If it
6157 // already exists there, recursively merge the results together.
6158 AddModifiedNodeToCSEMaps(User);
6161 // If we just RAUW'd the root, take note.
6162 if (From == getRoot())
6167 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6168 /// to record information about a use.
6175 /// operator< - Sort Memos by User.
6176 bool operator<(const UseMemo &L, const UseMemo &R) {
6177 return (intptr_t)L.User < (intptr_t)R.User;
6181 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6182 /// uses of other values produced by From.getNode() alone. The same value
6183 /// may appear in both the From and To list. The Deleted vector is
6184 /// handled the same way as for ReplaceAllUsesWith.
6185 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6188 // Handle the simple, trivial case efficiently.
6190 return ReplaceAllUsesOfValueWith(*From, *To);
6192 // Read up all the uses and make records of them. This helps
6193 // processing new uses that are introduced during the
6194 // replacement process.
6195 SmallVector<UseMemo, 4> Uses;
6196 for (unsigned i = 0; i != Num; ++i) {
6197 unsigned FromResNo = From[i].getResNo();
6198 SDNode *FromNode = From[i].getNode();
6199 for (SDNode::use_iterator UI = FromNode->use_begin(),
6200 E = FromNode->use_end(); UI != E; ++UI) {
6201 SDUse &Use = UI.getUse();
6202 if (Use.getResNo() == FromResNo) {
6203 UseMemo Memo = { *UI, i, &Use };
6204 Uses.push_back(Memo);
6209 // Sort the uses, so that all the uses from a given User are together.
6210 std::sort(Uses.begin(), Uses.end());
6212 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6213 UseIndex != UseIndexEnd; ) {
6214 // We know that this user uses some value of From. If it is the right
6215 // value, update it.
6216 SDNode *User = Uses[UseIndex].User;
6218 // This node is about to morph, remove its old self from the CSE maps.
6219 RemoveNodeFromCSEMaps(User);
6221 // The Uses array is sorted, so all the uses for a given User
6222 // are next to each other in the list.
6223 // To help reduce the number of CSE recomputations, process all
6224 // the uses of this user that we can find this way.
6226 unsigned i = Uses[UseIndex].Index;
6227 SDUse &Use = *Uses[UseIndex].Use;
6231 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6233 // Now that we have modified User, add it back to the CSE maps. If it
6234 // already exists there, recursively merge the results together.
6235 AddModifiedNodeToCSEMaps(User);
6239 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6240 /// based on their topological order. It returns the maximum id and a vector
6241 /// of the SDNodes* in assigned order by reference.
6242 unsigned SelectionDAG::AssignTopologicalOrder() {
6244 unsigned DAGSize = 0;
6246 // SortedPos tracks the progress of the algorithm. Nodes before it are
6247 // sorted, nodes after it are unsorted. When the algorithm completes
6248 // it is at the end of the list.
6249 allnodes_iterator SortedPos = allnodes_begin();
6251 // Visit all the nodes. Move nodes with no operands to the front of
6252 // the list immediately. Annotate nodes that do have operands with their
6253 // operand count. Before we do this, the Node Id fields of the nodes
6254 // may contain arbitrary values. After, the Node Id fields for nodes
6255 // before SortedPos will contain the topological sort index, and the
6256 // Node Id fields for nodes At SortedPos and after will contain the
6257 // count of outstanding operands.
6258 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6260 checkForCycles(N, this);
6261 unsigned Degree = N->getNumOperands();
6263 // A node with no uses, add it to the result array immediately.
6264 N->setNodeId(DAGSize++);
6265 allnodes_iterator Q = N;
6267 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6268 assert(SortedPos != AllNodes.end() && "Overran node list");
6271 // Temporarily use the Node Id as scratch space for the degree count.
6272 N->setNodeId(Degree);
6276 // Visit all the nodes. As we iterate, move nodes into sorted order,
6277 // such that by the time the end is reached all nodes will be sorted.
6278 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6280 checkForCycles(N, this);
6281 // N is in sorted position, so all its uses have one less operand
6282 // that needs to be sorted.
6283 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6286 unsigned Degree = P->getNodeId();
6287 assert(Degree != 0 && "Invalid node degree");
6290 // All of P's operands are sorted, so P may sorted now.
6291 P->setNodeId(DAGSize++);
6293 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6294 assert(SortedPos != AllNodes.end() && "Overran node list");
6297 // Update P's outstanding operand count.
6298 P->setNodeId(Degree);
6301 if (I == SortedPos) {
6304 dbgs() << "Overran sorted position:\n";
6305 S->dumprFull(this); dbgs() << "\n";
6306 dbgs() << "Checking if this is due to cycles\n";
6307 checkForCycles(this, true);
6309 llvm_unreachable(nullptr);
6313 assert(SortedPos == AllNodes.end() &&
6314 "Topological sort incomplete!");
6315 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6316 "First node in topological sort is not the entry token!");
6317 assert(AllNodes.front().getNodeId() == 0 &&
6318 "First node in topological sort has non-zero id!");
6319 assert(AllNodes.front().getNumOperands() == 0 &&
6320 "First node in topological sort has operands!");
6321 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6322 "Last node in topologic sort has unexpected id!");
6323 assert(AllNodes.back().use_empty() &&
6324 "Last node in topologic sort has users!");
6325 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6329 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6330 /// value is produced by SD.
6331 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6333 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6334 SD->setHasDebugValue(true);
6336 DbgInfo->add(DB, SD, isParameter);
6339 /// TransferDbgValues - Transfer SDDbgValues.
6340 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6341 if (From == To || !From.getNode()->getHasDebugValue())
6343 SDNode *FromNode = From.getNode();
6344 SDNode *ToNode = To.getNode();
6345 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6346 SmallVector<SDDbgValue *, 2> ClonedDVs;
6347 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6349 SDDbgValue *Dbg = *I;
6350 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6352 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6353 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6354 Dbg->getDebugLoc(), Dbg->getOrder());
6355 ClonedDVs.push_back(Clone);
6358 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6359 E = ClonedDVs.end(); I != E; ++I)
6360 AddDbgValue(*I, ToNode, false);
6363 //===----------------------------------------------------------------------===//
6365 //===----------------------------------------------------------------------===//
6367 HandleSDNode::~HandleSDNode() {
6371 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6372 DebugLoc DL, const GlobalValue *GA,
6373 EVT VT, int64_t o, unsigned char TF)
6374 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6378 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6379 SDValue X, unsigned SrcAS,
6381 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6382 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6384 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6385 EVT memvt, MachineMemOperand *mmo)
6386 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6387 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6388 MMO->isNonTemporal(), MMO->isInvariant());
6389 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6390 assert(isNonTemporal() == MMO->isNonTemporal() &&
6391 "Non-temporal encoding error!");
6392 // We check here that the size of the memory operand fits within the size of
6393 // the MMO. This is because the MMO might indicate only a possible address
6394 // range instead of specifying the affected memory addresses precisely.
6395 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6398 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6399 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6400 : SDNode(Opc, Order, dl, VTs, Ops),
6401 MemoryVT(memvt), MMO(mmo) {
6402 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6403 MMO->isNonTemporal(), MMO->isInvariant());
6404 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6405 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6408 /// Profile - Gather unique data for the node.
6410 void SDNode::Profile(FoldingSetNodeID &ID) const {
6411 AddNodeIDNode(ID, this);
6416 std::vector<EVT> VTs;
6419 VTs.reserve(MVT::LAST_VALUETYPE);
6420 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6421 VTs.push_back(MVT((MVT::SimpleValueType)i));
6426 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6427 static ManagedStatic<EVTArray> SimpleVTArray;
6428 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6430 /// getValueTypeList - Return a pointer to the specified value type.
6432 const EVT *SDNode::getValueTypeList(EVT VT) {
6433 if (VT.isExtended()) {
6434 sys::SmartScopedLock<true> Lock(*VTMutex);
6435 return &(*EVTs->insert(VT).first);
6437 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6438 "Value type out of range!");
6439 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6443 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6444 /// indicated value. This method ignores uses of other values defined by this
6446 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6447 assert(Value < getNumValues() && "Bad value!");
6449 // TODO: Only iterate over uses of a given value of the node
6450 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6451 if (UI.getUse().getResNo() == Value) {
6458 // Found exactly the right number of uses?
6463 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6464 /// value. This method ignores uses of other values defined by this operation.
6465 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6466 assert(Value < getNumValues() && "Bad value!");
6468 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6469 if (UI.getUse().getResNo() == Value)
6476 /// isOnlyUserOf - Return true if this node is the only use of N.
6478 bool SDNode::isOnlyUserOf(SDNode *N) const {
6480 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6491 /// isOperand - Return true if this node is an operand of N.
6493 bool SDValue::isOperandOf(SDNode *N) const {
6494 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6495 if (*this == N->getOperand(i))
6500 bool SDNode::isOperandOf(SDNode *N) const {
6501 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6502 if (this == N->OperandList[i].getNode())
6507 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6508 /// be a chain) reaches the specified operand without crossing any
6509 /// side-effecting instructions on any chain path. In practice, this looks
6510 /// through token factors and non-volatile loads. In order to remain efficient,
6511 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6512 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6513 unsigned Depth) const {
6514 if (*this == Dest) return true;
6516 // Don't search too deeply, we just want to be able to see through
6517 // TokenFactor's etc.
6518 if (Depth == 0) return false;
6520 // If this is a token factor, all inputs to the TF happen in parallel. If any
6521 // of the operands of the TF does not reach dest, then we cannot do the xform.
6522 if (getOpcode() == ISD::TokenFactor) {
6523 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6524 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6529 // Loads don't have side effects, look through them.
6530 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6531 if (!Ld->isVolatile())
6532 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6537 /// hasPredecessor - Return true if N is a predecessor of this node.
6538 /// N is either an operand of this node, or can be reached by recursively
6539 /// traversing up the operands.
6540 /// NOTE: This is an expensive method. Use it carefully.
6541 bool SDNode::hasPredecessor(const SDNode *N) const {
6542 SmallPtrSet<const SDNode *, 32> Visited;
6543 SmallVector<const SDNode *, 16> Worklist;
6544 return hasPredecessorHelper(N, Visited, Worklist);
6548 SDNode::hasPredecessorHelper(const SDNode *N,
6549 SmallPtrSetImpl<const SDNode *> &Visited,
6550 SmallVectorImpl<const SDNode *> &Worklist) const {
6551 if (Visited.empty()) {
6552 Worklist.push_back(this);
6554 // Take a look in the visited set. If we've already encountered this node
6555 // we needn't search further.
6556 if (Visited.count(N))
6560 // Haven't visited N yet. Continue the search.
6561 while (!Worklist.empty()) {
6562 const SDNode *M = Worklist.pop_back_val();
6563 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6564 SDNode *Op = M->getOperand(i).getNode();
6565 if (Visited.insert(Op).second)
6566 Worklist.push_back(Op);
6575 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6576 assert(Num < NumOperands && "Invalid child # of SDNode!");
6577 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6580 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6581 assert(N->getNumValues() == 1 &&
6582 "Can't unroll a vector with multiple results!");
6584 EVT VT = N->getValueType(0);
6585 unsigned NE = VT.getVectorNumElements();
6586 EVT EltVT = VT.getVectorElementType();
6589 SmallVector<SDValue, 8> Scalars;
6590 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6592 // If ResNE is 0, fully unroll the vector op.
6595 else if (NE > ResNE)
6599 for (i= 0; i != NE; ++i) {
6600 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6601 SDValue Operand = N->getOperand(j);
6602 EVT OperandVT = Operand.getValueType();
6603 if (OperandVT.isVector()) {
6604 // A vector operand; extract a single element.
6605 EVT OperandEltVT = OperandVT.getVectorElementType();
6606 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6609 getConstant(i, TLI->getVectorIdxTy()));
6611 // A scalar operand; just use it as is.
6612 Operands[j] = Operand;
6616 switch (N->getOpcode()) {
6618 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6621 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6628 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6629 getShiftAmountOperand(Operands[0].getValueType(),
6632 case ISD::SIGN_EXTEND_INREG:
6633 case ISD::FP_ROUND_INREG: {
6634 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6635 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6637 getValueType(ExtVT)));
6642 for (; i < ResNE; ++i)
6643 Scalars.push_back(getUNDEF(EltVT));
6645 return getNode(ISD::BUILD_VECTOR, dl,
6646 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6650 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6651 /// location that is 'Dist' units away from the location that the 'Base' load
6652 /// is loading from.
6653 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6654 unsigned Bytes, int Dist) const {
6655 if (LD->getChain() != Base->getChain())
6657 EVT VT = LD->getValueType(0);
6658 if (VT.getSizeInBits() / 8 != Bytes)
6661 SDValue Loc = LD->getOperand(1);
6662 SDValue BaseLoc = Base->getOperand(1);
6663 if (Loc.getOpcode() == ISD::FrameIndex) {
6664 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6666 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6667 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6668 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6669 int FS = MFI->getObjectSize(FI);
6670 int BFS = MFI->getObjectSize(BFI);
6671 if (FS != BFS || FS != (int)Bytes) return false;
6672 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6676 if (isBaseWithConstantOffset(Loc)) {
6677 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6678 if (Loc.getOperand(0) == BaseLoc) {
6679 // If the base location is a simple address with no offset itself, then
6680 // the second load's first add operand should be the base address.
6681 if (LocOffset == Dist * (int)Bytes)
6683 } else if (isBaseWithConstantOffset(BaseLoc)) {
6684 // The base location itself has an offset, so subtract that value from the
6685 // second load's offset before comparing to distance * size.
6687 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6688 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6689 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6694 const GlobalValue *GV1 = nullptr;
6695 const GlobalValue *GV2 = nullptr;
6696 int64_t Offset1 = 0;
6697 int64_t Offset2 = 0;
6698 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6699 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6700 if (isGA1 && isGA2 && GV1 == GV2)
6701 return Offset1 == (Offset2 + Dist*Bytes);
6706 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6707 /// it cannot be inferred.
6708 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6709 // If this is a GlobalAddress + cst, return the alignment.
6710 const GlobalValue *GV;
6711 int64_t GVOffset = 0;
6712 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6713 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6714 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6715 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6716 *TLI->getDataLayout());
6717 unsigned AlignBits = KnownZero.countTrailingOnes();
6718 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6720 return MinAlign(Align, GVOffset);
6723 // If this is a direct reference to a stack slot, use information about the
6724 // stack slot's alignment.
6725 int FrameIdx = 1 << 31;
6726 int64_t FrameOffset = 0;
6727 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6728 FrameIdx = FI->getIndex();
6729 } else if (isBaseWithConstantOffset(Ptr) &&
6730 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6732 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6733 FrameOffset = Ptr.getConstantOperandVal(1);
6736 if (FrameIdx != (1 << 31)) {
6737 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6738 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6746 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6747 /// which is split (or expanded) into two not necessarily identical pieces.
6748 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6749 // Currently all types are split in half.
6751 if (!VT.isVector()) {
6752 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6754 unsigned NumElements = VT.getVectorNumElements();
6755 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6756 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6759 return std::make_pair(LoVT, HiVT);
6762 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6764 std::pair<SDValue, SDValue>
6765 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6767 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6768 N.getValueType().getVectorNumElements() &&
6769 "More vector elements requested than available!");
6771 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6772 getConstant(0, TLI->getVectorIdxTy()));
6773 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6774 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6775 return std::make_pair(Lo, Hi);
6778 void SelectionDAG::ExtractVectorElements(SDValue Op,
6779 SmallVectorImpl<SDValue> &Args,
6780 unsigned Start, unsigned Count) {
6781 EVT VT = Op.getValueType();
6783 Count = VT.getVectorNumElements();
6785 EVT EltVT = VT.getVectorElementType();
6786 EVT IdxTy = TLI->getVectorIdxTy();
6788 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6789 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6790 Op, getConstant(i, IdxTy)));
6794 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6795 unsigned GlobalAddressSDNode::getAddressSpace() const {
6796 return getGlobal()->getType()->getAddressSpace();
6800 Type *ConstantPoolSDNode::getType() const {
6801 if (isMachineConstantPoolEntry())
6802 return Val.MachineCPVal->getType();
6803 return Val.ConstVal->getType();
6806 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6808 unsigned &SplatBitSize,
6810 unsigned MinSplatBits,
6811 bool isBigEndian) const {
6812 EVT VT = getValueType(0);
6813 assert(VT.isVector() && "Expected a vector type");
6814 unsigned sz = VT.getSizeInBits();
6815 if (MinSplatBits > sz)
6818 SplatValue = APInt(sz, 0);
6819 SplatUndef = APInt(sz, 0);
6821 // Get the bits. Bits with undefined values (when the corresponding element
6822 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6823 // in SplatValue. If any of the values are not constant, give up and return
6825 unsigned int nOps = getNumOperands();
6826 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6827 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6829 for (unsigned j = 0; j < nOps; ++j) {
6830 unsigned i = isBigEndian ? nOps-1-j : j;
6831 SDValue OpVal = getOperand(i);
6832 unsigned BitPos = j * EltBitSize;
6834 if (OpVal.getOpcode() == ISD::UNDEF)
6835 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6836 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6837 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6838 zextOrTrunc(sz) << BitPos;
6839 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6840 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6845 // The build_vector is all constants or undefs. Find the smallest element
6846 // size that splats the vector.
6848 HasAnyUndefs = (SplatUndef != 0);
6851 unsigned HalfSize = sz / 2;
6852 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6853 APInt LowValue = SplatValue.trunc(HalfSize);
6854 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6855 APInt LowUndef = SplatUndef.trunc(HalfSize);
6857 // If the two halves do not match (ignoring undef bits), stop here.
6858 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6859 MinSplatBits > HalfSize)
6862 SplatValue = HighValue | LowValue;
6863 SplatUndef = HighUndef & LowUndef;
6872 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6873 if (UndefElements) {
6874 UndefElements->clear();
6875 UndefElements->resize(getNumOperands());
6878 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6879 SDValue Op = getOperand(i);
6880 if (Op.getOpcode() == ISD::UNDEF) {
6882 (*UndefElements)[i] = true;
6883 } else if (!Splatted) {
6885 } else if (Splatted != Op) {
6891 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6892 "Can only have a splat without a constant for all undefs.");
6893 return getOperand(0);
6900 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6901 return dyn_cast_or_null<ConstantSDNode>(
6902 getSplatValue(UndefElements).getNode());
6906 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6907 return dyn_cast_or_null<ConstantFPSDNode>(
6908 getSplatValue(UndefElements).getNode());
6911 bool BuildVectorSDNode::isConstant() const {
6912 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6913 unsigned Opc = getOperand(i).getOpcode();
6914 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6920 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6921 // Find the first non-undef value in the shuffle mask.
6923 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6926 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6928 // Make sure all remaining elements are either undef or the same as the first
6930 for (int Idx = Mask[i]; i != e; ++i)
6931 if (Mask[i] >= 0 && Mask[i] != Idx)
6937 static void checkForCyclesHelper(const SDNode *N,
6938 SmallPtrSetImpl<const SDNode*> &Visited,
6939 SmallPtrSetImpl<const SDNode*> &Checked,
6940 const llvm::SelectionDAG *DAG) {
6941 // If this node has already been checked, don't check it again.
6942 if (Checked.count(N))
6945 // If a node has already been visited on this depth-first walk, reject it as
6947 if (!Visited.insert(N).second) {
6948 errs() << "Detected cycle in SelectionDAG\n";
6949 dbgs() << "Offending node:\n";
6950 N->dumprFull(DAG); dbgs() << "\n";
6954 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6955 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6962 void llvm::checkForCycles(const llvm::SDNode *N,
6963 const llvm::SelectionDAG *DAG,
6971 assert(N && "Checking nonexistent SDNode");
6972 SmallPtrSet<const SDNode*, 32> visited;
6973 SmallPtrSet<const SDNode*, 32> checked;
6974 checkForCyclesHelper(N, visited, checked, DAG);
6979 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6980 checkForCycles(DAG->getRoot().getNode(), DAG, force);