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"
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59 SDVTList Res = {VTs, NumVTs};
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67 //===----------------------------------------------------------------------===//
68 // ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76 return getValueAPF().bitwiseIsEqual(V);
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
81 assert(VT.isFloatingPoint() && "Can only convert between FP types");
83 // convert modifies in place, so make a copy.
84 APFloat Val2 = APFloat(Val);
86 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87 APFloat::rmNearestTiesToEven,
92 //===----------------------------------------------------------------------===//
94 //===----------------------------------------------------------------------===//
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99 // Look through a bit convert.
100 while (N->getOpcode() == ISD::BITCAST)
101 N = N->getOperand(0).getNode();
103 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105 unsigned i = 0, e = N->getNumOperands();
107 // Skip over all of the undef values.
108 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111 // Do not accept an all-undef vector.
112 if (i == e) return false;
114 // Do not accept build_vectors that aren't all constants or which have non-~0
115 // elements. We have to be a bit careful here, as the type of the constant
116 // may not be the same as the type of the vector elements due to type
117 // legalization (the elements are promoted to a legal type for the target and
118 // a vector of a type may be legal when the base element type is not).
119 // We only want to check enough bits to cover the vector elements, because
120 // we care if the resultant vector is all ones, not whether the individual
122 SDValue NotZero = N->getOperand(i);
123 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133 // Okay, we have at least one ~0 value, check to see if the rest match or are
134 // undefs. Even with the above element type twiddling, this should be OK, as
135 // the same type legalization should have applied to all the elements.
136 for (++i; i != e; ++i)
137 if (N->getOperand(i) != NotZero &&
138 N->getOperand(i).getOpcode() != ISD::UNDEF)
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147 // Look through a bit convert.
148 while (N->getOpcode() == ISD::BITCAST)
149 N = N->getOperand(0).getNode();
151 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153 bool IsAllUndef = true;
154 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept build_vectors that aren't all constants or which have non-0
159 // elements. We have to be a bit careful here, as the type of the constant
160 // may not be the same as the type of the vector elements due to type
161 // legalization (the elements are promoted to a legal type for the target
162 // and a vector of a type may be legal when the base element type is not).
163 // We only want to check enough bits to cover the vector elements, because
164 // we care if the resultant vector is all zeros, not whether the individual
166 SDValue Zero = N->getOperand(i);
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (const SDValue &Op : N->op_values()) {
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 (const SDValue &Op : N->op_values()) {
206 if (Op.getOpcode() == ISD::UNDEF)
208 if (!isa<ConstantFPSDNode>(Op))
214 /// isScalarToVector - Return true if the specified node is a
215 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
216 /// element is not an undef.
217 bool ISD::isScalarToVector(const SDNode *N) {
218 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
221 if (N->getOpcode() != ISD::BUILD_VECTOR)
223 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
225 unsigned NumElems = N->getNumOperands();
228 for (unsigned i = 1; i < NumElems; ++i) {
229 SDValue V = N->getOperand(i);
230 if (V.getOpcode() != ISD::UNDEF)
236 /// allOperandsUndef - Return true if the node has at least one operand
237 /// and all operands of the specified node are ISD::UNDEF.
238 bool ISD::allOperandsUndef(const SDNode *N) {
239 // Return false if the node has no operands.
240 // This is "logically inconsistent" with the definition of "all" but
241 // is probably the desired behavior.
242 if (N->getNumOperands() == 0)
245 for (const SDValue &Op : N->op_values())
246 if (Op.getOpcode() != ISD::UNDEF)
252 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
255 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
257 return ISD::SIGN_EXTEND;
259 return ISD::ZERO_EXTEND;
264 llvm_unreachable("Invalid LoadExtType");
267 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
268 /// when given the operation for (X op Y).
269 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
270 // To perform this operation, we just need to swap the L and G bits of the
272 unsigned OldL = (Operation >> 2) & 1;
273 unsigned OldG = (Operation >> 1) & 1;
274 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
275 (OldL << 1) | // New G bit
276 (OldG << 2)); // New L bit.
279 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
280 /// 'op' is a valid SetCC operation.
281 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
282 unsigned Operation = Op;
284 Operation ^= 7; // Flip L, G, E bits, but not U.
286 Operation ^= 15; // Flip all of the condition bits.
288 if (Operation > ISD::SETTRUE2)
289 Operation &= ~8; // Don't let N and U bits get set.
291 return ISD::CondCode(Operation);
295 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
296 /// signed operation and 2 if the result is an unsigned comparison. Return zero
297 /// if the operation does not depend on the sign of the input (setne and seteq).
298 static int isSignedOp(ISD::CondCode Opcode) {
300 default: llvm_unreachable("Illegal integer setcc operation!");
302 case ISD::SETNE: return 0;
306 case ISD::SETGE: return 1;
310 case ISD::SETUGE: return 2;
314 /// getSetCCOrOperation - Return the result of a logical OR between different
315 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
316 /// returns SETCC_INVALID if it is not possible to represent the resultant
318 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
320 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
321 // Cannot fold a signed integer setcc with an unsigned integer setcc.
322 return ISD::SETCC_INVALID;
324 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
326 // If the N and U bits get set then the resultant comparison DOES suddenly
327 // care about orderedness, and is true when ordered.
328 if (Op > ISD::SETTRUE2)
329 Op &= ~16; // Clear the U bit if the N bit is set.
331 // Canonicalize illegal integer setcc's.
332 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
335 return ISD::CondCode(Op);
338 /// getSetCCAndOperation - Return the result of a logical AND between different
339 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
340 /// function returns zero if it is not possible to represent the resultant
342 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
344 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
345 // Cannot fold a signed setcc with an unsigned setcc.
346 return ISD::SETCC_INVALID;
348 // Combine all of the condition bits.
349 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
351 // Canonicalize illegal integer setcc's.
355 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
356 case ISD::SETOEQ: // SETEQ & SETU[LG]E
357 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
358 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
359 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
366 //===----------------------------------------------------------------------===//
367 // SDNode Profile Support
368 //===----------------------------------------------------------------------===//
370 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
372 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
376 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
377 /// solely with their pointer.
378 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
379 ID.AddPointer(VTList.VTs);
382 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
384 static void AddNodeIDOperands(FoldingSetNodeID &ID,
385 ArrayRef<SDValue> Ops) {
386 for (auto& Op : Ops) {
387 ID.AddPointer(Op.getNode());
388 ID.AddInteger(Op.getResNo());
392 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
394 static void AddNodeIDOperands(FoldingSetNodeID &ID,
395 ArrayRef<SDUse> Ops) {
396 for (auto& Op : Ops) {
397 ID.AddPointer(Op.getNode());
398 ID.AddInteger(Op.getResNo());
401 /// Add logical or fast math flag values to FoldingSetNodeID value.
402 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
403 const SDNodeFlags *Flags) {
404 if (!Flags || !isBinOpWithFlags(Opcode))
407 unsigned RawFlags = Flags->getRawFlags();
408 // If no flags are set, do not alter the ID. We must match the ID of nodes
409 // that were created without explicitly specifying flags. This also saves time
410 // and allows a gradual increase in API usage of the optional optimization
413 ID.AddInteger(RawFlags);
416 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
417 if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
418 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
421 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
422 SDVTList VTList, ArrayRef<SDValue> OpList) {
423 AddNodeIDOpcode(ID, OpC);
424 AddNodeIDValueTypes(ID, VTList);
425 AddNodeIDOperands(ID, OpList);
428 /// If this is an SDNode with special info, add this info to the NodeID data.
429 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
430 switch (N->getOpcode()) {
431 case ISD::TargetExternalSymbol:
432 case ISD::ExternalSymbol:
434 llvm_unreachable("Should only be used on nodes with operands");
435 default: break; // Normal nodes don't need extra info.
436 case ISD::TargetConstant:
437 case ISD::Constant: {
438 const ConstantSDNode *C = cast<ConstantSDNode>(N);
439 ID.AddPointer(C->getConstantIntValue());
440 ID.AddBoolean(C->isOpaque());
443 case ISD::TargetConstantFP:
444 case ISD::ConstantFP: {
445 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
448 case ISD::TargetGlobalAddress:
449 case ISD::GlobalAddress:
450 case ISD::TargetGlobalTLSAddress:
451 case ISD::GlobalTLSAddress: {
452 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
453 ID.AddPointer(GA->getGlobal());
454 ID.AddInteger(GA->getOffset());
455 ID.AddInteger(GA->getTargetFlags());
456 ID.AddInteger(GA->getAddressSpace());
459 case ISD::BasicBlock:
460 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
463 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
465 case ISD::RegisterMask:
466 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
469 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
471 case ISD::FrameIndex:
472 case ISD::TargetFrameIndex:
473 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
476 case ISD::TargetJumpTable:
477 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
478 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
480 case ISD::ConstantPool:
481 case ISD::TargetConstantPool: {
482 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
483 ID.AddInteger(CP->getAlignment());
484 ID.AddInteger(CP->getOffset());
485 if (CP->isMachineConstantPoolEntry())
486 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
488 ID.AddPointer(CP->getConstVal());
489 ID.AddInteger(CP->getTargetFlags());
492 case ISD::TargetIndex: {
493 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
494 ID.AddInteger(TI->getIndex());
495 ID.AddInteger(TI->getOffset());
496 ID.AddInteger(TI->getTargetFlags());
500 const LoadSDNode *LD = cast<LoadSDNode>(N);
501 ID.AddInteger(LD->getMemoryVT().getRawBits());
502 ID.AddInteger(LD->getRawSubclassData());
503 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
507 const StoreSDNode *ST = cast<StoreSDNode>(N);
508 ID.AddInteger(ST->getMemoryVT().getRawBits());
509 ID.AddInteger(ST->getRawSubclassData());
510 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
513 case ISD::ATOMIC_CMP_SWAP:
514 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
515 case ISD::ATOMIC_SWAP:
516 case ISD::ATOMIC_LOAD_ADD:
517 case ISD::ATOMIC_LOAD_SUB:
518 case ISD::ATOMIC_LOAD_AND:
519 case ISD::ATOMIC_LOAD_OR:
520 case ISD::ATOMIC_LOAD_XOR:
521 case ISD::ATOMIC_LOAD_NAND:
522 case ISD::ATOMIC_LOAD_MIN:
523 case ISD::ATOMIC_LOAD_MAX:
524 case ISD::ATOMIC_LOAD_UMIN:
525 case ISD::ATOMIC_LOAD_UMAX:
526 case ISD::ATOMIC_LOAD:
527 case ISD::ATOMIC_STORE: {
528 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
529 ID.AddInteger(AT->getMemoryVT().getRawBits());
530 ID.AddInteger(AT->getRawSubclassData());
531 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
534 case ISD::PREFETCH: {
535 const MemSDNode *PF = cast<MemSDNode>(N);
536 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
539 case ISD::VECTOR_SHUFFLE: {
540 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
541 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
543 ID.AddInteger(SVN->getMaskElt(i));
546 case ISD::TargetBlockAddress:
547 case ISD::BlockAddress: {
548 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
549 ID.AddPointer(BA->getBlockAddress());
550 ID.AddInteger(BA->getOffset());
551 ID.AddInteger(BA->getTargetFlags());
554 } // end switch (N->getOpcode())
556 AddNodeIDFlags(ID, N);
558 // Target specific memory nodes could also have address spaces to check.
559 if (N->isTargetMemoryOpcode())
560 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
563 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
565 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
566 AddNodeIDOpcode(ID, N->getOpcode());
567 // Add the return value info.
568 AddNodeIDValueTypes(ID, N->getVTList());
569 // Add the operand info.
570 AddNodeIDOperands(ID, N->ops());
572 // Handle SDNode leafs with special info.
573 AddNodeIDCustom(ID, N);
576 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
577 /// the CSE map that carries volatility, temporalness, indexing mode, and
578 /// extension/truncation information.
580 static inline unsigned
581 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
582 bool isNonTemporal, bool isInvariant) {
583 assert((ConvType & 3) == ConvType &&
584 "ConvType may not require more than 2 bits!");
585 assert((AM & 7) == AM &&
586 "AM may not require more than 3 bits!");
590 (isNonTemporal << 6) |
594 //===----------------------------------------------------------------------===//
595 // SelectionDAG Class
596 //===----------------------------------------------------------------------===//
598 /// doNotCSE - Return true if CSE should not be performed for this node.
599 static bool doNotCSE(SDNode *N) {
600 if (N->getValueType(0) == MVT::Glue)
601 return true; // Never CSE anything that produces a flag.
603 switch (N->getOpcode()) {
605 case ISD::HANDLENODE:
607 return true; // Never CSE these nodes.
610 // Check that remaining values produced are not flags.
611 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
612 if (N->getValueType(i) == MVT::Glue)
613 return true; // Never CSE anything that produces a flag.
618 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
620 void SelectionDAG::RemoveDeadNodes() {
621 // Create a dummy node (which is not added to allnodes), that adds a reference
622 // to the root node, preventing it from being deleted.
623 HandleSDNode Dummy(getRoot());
625 SmallVector<SDNode*, 128> DeadNodes;
627 // Add all obviously-dead nodes to the DeadNodes worklist.
628 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
630 DeadNodes.push_back(I);
632 RemoveDeadNodes(DeadNodes);
634 // If the root changed (e.g. it was a dead load, update the root).
635 setRoot(Dummy.getValue());
638 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
639 /// given list, and any nodes that become unreachable as a result.
640 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
642 // Process the worklist, deleting the nodes and adding their uses to the
644 while (!DeadNodes.empty()) {
645 SDNode *N = DeadNodes.pop_back_val();
647 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
648 DUL->NodeDeleted(N, nullptr);
650 // Take the node out of the appropriate CSE map.
651 RemoveNodeFromCSEMaps(N);
653 // Next, brutally remove the operand list. This is safe to do, as there are
654 // no cycles in the graph.
655 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
657 SDNode *Operand = Use.getNode();
660 // Now that we removed this operand, see if there are no uses of it left.
661 if (Operand->use_empty())
662 DeadNodes.push_back(Operand);
669 void SelectionDAG::RemoveDeadNode(SDNode *N){
670 SmallVector<SDNode*, 16> DeadNodes(1, N);
672 // Create a dummy node that adds a reference to the root node, preventing
673 // it from being deleted. (This matters if the root is an operand of the
675 HandleSDNode Dummy(getRoot());
677 RemoveDeadNodes(DeadNodes);
680 void SelectionDAG::DeleteNode(SDNode *N) {
681 // First take this out of the appropriate CSE map.
682 RemoveNodeFromCSEMaps(N);
684 // Finally, remove uses due to operands of this node, remove from the
685 // AllNodes list, and delete the node.
686 DeleteNodeNotInCSEMaps(N);
689 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
690 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
691 assert(N->use_empty() && "Cannot delete a node that is not dead!");
693 // Drop all of the operands and decrement used node's use counts.
699 void SDDbgInfo::erase(const SDNode *Node) {
700 DbgValMapType::iterator I = DbgValMap.find(Node);
701 if (I == DbgValMap.end())
703 for (auto &Val: I->second)
704 Val->setIsInvalidated();
708 void SelectionDAG::DeallocateNode(SDNode *N) {
709 if (N->OperandsNeedDelete)
710 delete[] N->OperandList;
712 // Set the opcode to DELETED_NODE to help catch bugs when node
713 // memory is reallocated.
714 N->NodeType = ISD::DELETED_NODE;
716 NodeAllocator.Deallocate(AllNodes.remove(N));
718 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
719 // them and forget about that node.
724 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
725 static void VerifySDNode(SDNode *N) {
726 switch (N->getOpcode()) {
729 case ISD::BUILD_PAIR: {
730 EVT VT = N->getValueType(0);
731 assert(N->getNumValues() == 1 && "Too many results!");
732 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
733 "Wrong return type!");
734 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
735 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
736 "Mismatched operand types!");
737 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
738 "Wrong operand type!");
739 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
740 "Wrong return type size");
743 case ISD::BUILD_VECTOR: {
744 assert(N->getNumValues() == 1 && "Too many results!");
745 assert(N->getValueType(0).isVector() && "Wrong return type!");
746 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
747 "Wrong number of operands!");
748 EVT EltVT = N->getValueType(0).getVectorElementType();
749 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
750 assert((I->getValueType() == EltVT ||
751 (EltVT.isInteger() && I->getValueType().isInteger() &&
752 EltVT.bitsLE(I->getValueType()))) &&
753 "Wrong operand type!");
754 assert(I->getValueType() == N->getOperand(0).getValueType() &&
755 "Operands must all have the same type");
763 /// \brief Insert a newly allocated node into the DAG.
765 /// Handles insertion into the all nodes list and CSE map, as well as
766 /// verification and other common operations when a new node is allocated.
767 void SelectionDAG::InsertNode(SDNode *N) {
768 AllNodes.push_back(N);
774 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
775 /// correspond to it. This is useful when we're about to delete or repurpose
776 /// the node. We don't want future request for structurally identical nodes
777 /// to return N anymore.
778 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
780 switch (N->getOpcode()) {
781 case ISD::HANDLENODE: return false; // noop.
783 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
784 "Cond code doesn't exist!");
785 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
786 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
788 case ISD::ExternalSymbol:
789 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
791 case ISD::TargetExternalSymbol: {
792 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
793 Erased = TargetExternalSymbols.erase(
794 std::pair<std::string,unsigned char>(ESN->getSymbol(),
795 ESN->getTargetFlags()));
798 case ISD::MCSymbol: {
799 auto *MCSN = cast<MCSymbolSDNode>(N);
800 Erased = MCSymbols.erase(MCSN->getMCSymbol());
803 case ISD::VALUETYPE: {
804 EVT VT = cast<VTSDNode>(N)->getVT();
805 if (VT.isExtended()) {
806 Erased = ExtendedValueTypeNodes.erase(VT);
808 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
809 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
814 // Remove it from the CSE Map.
815 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
816 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
817 Erased = CSEMap.RemoveNode(N);
821 // Verify that the node was actually in one of the CSE maps, unless it has a
822 // flag result (which cannot be CSE'd) or is one of the special cases that are
823 // not subject to CSE.
824 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
825 !N->isMachineOpcode() && !doNotCSE(N)) {
828 llvm_unreachable("Node is not in map!");
834 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
835 /// maps and modified in place. Add it back to the CSE maps, unless an identical
836 /// node already exists, in which case transfer all its users to the existing
837 /// node. This transfer can potentially trigger recursive merging.
840 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
841 // For node types that aren't CSE'd, just act as if no identical node
844 SDNode *Existing = CSEMap.GetOrInsertNode(N);
846 // If there was already an existing matching node, use ReplaceAllUsesWith
847 // to replace the dead one with the existing one. This can cause
848 // recursive merging of other unrelated nodes down the line.
849 ReplaceAllUsesWith(N, Existing);
851 // N is now dead. Inform the listeners and delete it.
852 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
853 DUL->NodeDeleted(N, Existing);
854 DeleteNodeNotInCSEMaps(N);
859 // If the node doesn't already exist, we updated it. Inform listeners.
860 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
864 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
865 /// were replaced with those specified. If this node is never memoized,
866 /// return null, otherwise return a pointer to the slot it would take. If a
867 /// node already exists with these operands, the slot will be non-null.
868 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
873 SDValue Ops[] = { Op };
875 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
876 AddNodeIDCustom(ID, N);
877 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
881 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
882 /// were replaced with those specified. If this node is never memoized,
883 /// return null, otherwise return a pointer to the slot it would take. If a
884 /// node already exists with these operands, the slot will be non-null.
885 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
886 SDValue Op1, SDValue Op2,
891 SDValue Ops[] = { Op1, Op2 };
893 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
894 AddNodeIDCustom(ID, N);
895 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
900 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
901 /// were replaced with those specified. If this node is never memoized,
902 /// return null, otherwise return a pointer to the slot it would take. If a
903 /// node already exists with these operands, the slot will be non-null.
904 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
910 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
911 AddNodeIDCustom(ID, N);
912 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
916 /// getEVTAlignment - Compute the default alignment value for the
919 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
920 Type *Ty = VT == MVT::iPTR ?
921 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
922 VT.getTypeForEVT(*getContext());
924 return getDataLayout().getABITypeAlignment(Ty);
927 // EntryNode could meaningfully have debug info if we can find it...
928 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
929 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
930 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
931 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
932 UpdateListeners(nullptr) {
933 AllNodes.push_back(&EntryNode);
934 DbgInfo = new SDDbgInfo();
937 void SelectionDAG::init(MachineFunction &mf) {
939 TLI = getSubtarget().getTargetLowering();
940 TSI = getSubtarget().getSelectionDAGInfo();
941 Context = &mf.getFunction()->getContext();
944 SelectionDAG::~SelectionDAG() {
945 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
950 void SelectionDAG::allnodes_clear() {
951 assert(&*AllNodes.begin() == &EntryNode);
952 AllNodes.remove(AllNodes.begin());
953 while (!AllNodes.empty())
954 DeallocateNode(AllNodes.begin());
957 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
958 SDVTList VTs, SDValue N1,
960 const SDNodeFlags *Flags) {
961 if (isBinOpWithFlags(Opcode)) {
962 // If no flags were passed in, use a default flags object.
964 if (Flags == nullptr)
967 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
968 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
980 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
982 switch (N->getOpcode()) {
985 case ISD::ConstantFP:
986 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
987 "debug location. Use another overload.");
993 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
994 DebugLoc DL, void *&InsertPos) {
995 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
997 switch (N->getOpcode()) {
998 default: break; // Process only regular (non-target) constant nodes.
1000 case ISD::ConstantFP:
1001 // Erase debug location from the node if the node is used at several
1002 // different places to do not propagate one location to all uses as it
1003 // leads to incorrect debug info.
1004 if (N->getDebugLoc() != DL)
1005 N->setDebugLoc(DebugLoc());
1012 void SelectionDAG::clear() {
1014 OperandAllocator.Reset();
1017 ExtendedValueTypeNodes.clear();
1018 ExternalSymbols.clear();
1019 TargetExternalSymbols.clear();
1021 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1022 static_cast<CondCodeSDNode*>(nullptr));
1023 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1024 static_cast<SDNode*>(nullptr));
1026 EntryNode.UseList = nullptr;
1027 AllNodes.push_back(&EntryNode);
1028 Root = getEntryNode();
1032 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1033 return VT.bitsGT(Op.getValueType()) ?
1034 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1035 getNode(ISD::TRUNCATE, DL, VT, Op);
1038 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1039 return VT.bitsGT(Op.getValueType()) ?
1040 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1041 getNode(ISD::TRUNCATE, DL, VT, Op);
1044 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1045 return VT.bitsGT(Op.getValueType()) ?
1046 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1047 getNode(ISD::TRUNCATE, DL, VT, Op);
1050 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1052 if (VT.bitsLE(Op.getValueType()))
1053 return getNode(ISD::TRUNCATE, SL, VT, Op);
1055 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1056 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1059 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1060 assert(!VT.isVector() &&
1061 "getZeroExtendInReg should use the vector element type instead of "
1062 "the vector type!");
1063 if (Op.getValueType() == VT) return Op;
1064 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1065 APInt Imm = APInt::getLowBitsSet(BitWidth,
1066 VT.getSizeInBits());
1067 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1068 getConstant(Imm, DL, Op.getValueType()));
1071 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1072 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1073 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1074 "The sizes of the input and result must match in order to perform the "
1075 "extend in-register.");
1076 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1077 "The destination vector type must have fewer lanes than the input.");
1078 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1081 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1082 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1083 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1084 "The sizes of the input and result must match in order to perform the "
1085 "extend in-register.");
1086 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1087 "The destination vector type must have fewer lanes than the input.");
1088 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1091 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1092 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1093 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1094 "The sizes of the input and result must match in order to perform the "
1095 "extend in-register.");
1096 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1097 "The destination vector type must have fewer lanes than the input.");
1098 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1101 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1103 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1104 EVT EltVT = VT.getScalarType();
1106 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1107 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1110 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1111 EVT EltVT = VT.getScalarType();
1113 switch (TLI->getBooleanContents(VT)) {
1114 case TargetLowering::ZeroOrOneBooleanContent:
1115 case TargetLowering::UndefinedBooleanContent:
1116 TrueValue = getConstant(1, DL, VT);
1118 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1119 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1123 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1126 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1128 EVT EltVT = VT.getScalarType();
1129 assert((EltVT.getSizeInBits() >= 64 ||
1130 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1131 "getConstant with a uint64_t value that doesn't fit in the type!");
1132 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1135 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1138 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1141 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1142 bool isT, bool isO) {
1143 assert(VT.isInteger() && "Cannot create FP integer constant!");
1145 EVT EltVT = VT.getScalarType();
1146 const ConstantInt *Elt = &Val;
1148 // In some cases the vector type is legal but the element type is illegal and
1149 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1150 // inserted value (the type does not need to match the vector element type).
1151 // Any extra bits introduced will be truncated away.
1152 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1153 TargetLowering::TypePromoteInteger) {
1154 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1155 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1156 Elt = ConstantInt::get(*getContext(), NewVal);
1158 // In other cases the element type is illegal and needs to be expanded, for
1159 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1160 // the value into n parts and use a vector type with n-times the elements.
1161 // Then bitcast to the type requested.
1162 // Legalizing constants too early makes the DAGCombiner's job harder so we
1163 // only legalize if the DAG tells us we must produce legal types.
1164 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1165 TLI->getTypeAction(*getContext(), EltVT) ==
1166 TargetLowering::TypeExpandInteger) {
1167 APInt NewVal = Elt->getValue();
1168 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1169 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1170 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1171 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1173 // Check the temporary vector is the correct size. If this fails then
1174 // getTypeToTransformTo() probably returned a type whose size (in bits)
1175 // isn't a power-of-2 factor of the requested type size.
1176 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1178 SmallVector<SDValue, 2> EltParts;
1179 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1180 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1181 .trunc(ViaEltSizeInBits), DL,
1182 ViaEltVT, isT, isO));
1185 // EltParts is currently in little endian order. If we actually want
1186 // big-endian order then reverse it now.
1187 if (getDataLayout().isBigEndian())
1188 std::reverse(EltParts.begin(), EltParts.end());
1190 // The elements must be reversed when the element order is different
1191 // to the endianness of the elements (because the BITCAST is itself a
1192 // vector shuffle in this situation). However, we do not need any code to
1193 // perform this reversal because getConstant() is producing a vector
1195 // This situation occurs in MIPS MSA.
1197 SmallVector<SDValue, 8> Ops;
1198 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1199 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1201 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1202 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1207 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1208 "APInt size does not match type size!");
1209 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1210 FoldingSetNodeID ID;
1211 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1215 SDNode *N = nullptr;
1216 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1218 return SDValue(N, 0);
1221 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1223 CSEMap.InsertNode(N, IP);
1227 SDValue Result(N, 0);
1228 if (VT.isVector()) {
1229 SmallVector<SDValue, 8> Ops;
1230 Ops.assign(VT.getVectorNumElements(), Result);
1231 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1236 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1237 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1240 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1242 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1245 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1247 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1249 EVT EltVT = VT.getScalarType();
1251 // Do the map lookup using the actual bit pattern for the floating point
1252 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1253 // we don't have issues with SNANs.
1254 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1255 FoldingSetNodeID ID;
1256 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1259 SDNode *N = nullptr;
1260 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1262 return SDValue(N, 0);
1265 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1267 CSEMap.InsertNode(N, IP);
1271 SDValue Result(N, 0);
1272 if (VT.isVector()) {
1273 SmallVector<SDValue, 8> Ops;
1274 Ops.assign(VT.getVectorNumElements(), Result);
1275 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1280 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1282 EVT EltVT = VT.getScalarType();
1283 if (EltVT==MVT::f32)
1284 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1285 else if (EltVT==MVT::f64)
1286 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1287 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1290 APFloat apf = APFloat(Val);
1291 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1293 return getConstantFP(apf, DL, VT, isTarget);
1295 llvm_unreachable("Unsupported type in getConstantFP");
1298 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1299 EVT VT, int64_t Offset,
1301 unsigned char TargetFlags) {
1302 assert((TargetFlags == 0 || isTargetGA) &&
1303 "Cannot set target flags on target-independent globals");
1305 // Truncate (with sign-extension) the offset value to the pointer size.
1306 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1308 Offset = SignExtend64(Offset, BitWidth);
1311 if (GV->isThreadLocal())
1312 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1314 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1321 ID.AddInteger(GV->getType()->getAddressSpace());
1323 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1324 return SDValue(E, 0);
1326 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1327 DL.getDebugLoc(), GV, VT,
1328 Offset, TargetFlags);
1329 CSEMap.InsertNode(N, IP);
1331 return SDValue(N, 0);
1334 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1335 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1336 FoldingSetNodeID ID;
1337 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1340 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1341 return SDValue(E, 0);
1343 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1344 CSEMap.InsertNode(N, IP);
1346 return SDValue(N, 0);
1349 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1350 unsigned char TargetFlags) {
1351 assert((TargetFlags == 0 || isTarget) &&
1352 "Cannot set target flags on target-independent jump tables");
1353 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1354 FoldingSetNodeID ID;
1355 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1357 ID.AddInteger(TargetFlags);
1359 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1360 return SDValue(E, 0);
1362 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1364 CSEMap.InsertNode(N, IP);
1366 return SDValue(N, 0);
1369 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1370 unsigned Alignment, int Offset,
1372 unsigned char TargetFlags) {
1373 assert((TargetFlags == 0 || isTarget) &&
1374 "Cannot set target flags on target-independent globals");
1376 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1377 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1378 FoldingSetNodeID ID;
1379 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1380 ID.AddInteger(Alignment);
1381 ID.AddInteger(Offset);
1383 ID.AddInteger(TargetFlags);
1385 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1386 return SDValue(E, 0);
1388 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1389 Alignment, TargetFlags);
1390 CSEMap.InsertNode(N, IP);
1392 return SDValue(N, 0);
1396 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1397 unsigned Alignment, int Offset,
1399 unsigned char TargetFlags) {
1400 assert((TargetFlags == 0 || isTarget) &&
1401 "Cannot set target flags on target-independent globals");
1403 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1404 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1405 FoldingSetNodeID ID;
1406 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1407 ID.AddInteger(Alignment);
1408 ID.AddInteger(Offset);
1409 C->addSelectionDAGCSEId(ID);
1410 ID.AddInteger(TargetFlags);
1412 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1413 return SDValue(E, 0);
1415 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1416 Alignment, TargetFlags);
1417 CSEMap.InsertNode(N, IP);
1419 return SDValue(N, 0);
1422 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1423 unsigned char TargetFlags) {
1424 FoldingSetNodeID ID;
1425 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1426 ID.AddInteger(Index);
1427 ID.AddInteger(Offset);
1428 ID.AddInteger(TargetFlags);
1430 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1431 return SDValue(E, 0);
1433 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1435 CSEMap.InsertNode(N, IP);
1437 return SDValue(N, 0);
1440 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1441 FoldingSetNodeID ID;
1442 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1445 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1446 return SDValue(E, 0);
1448 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1449 CSEMap.InsertNode(N, IP);
1451 return SDValue(N, 0);
1454 SDValue SelectionDAG::getValueType(EVT VT) {
1455 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1456 ValueTypeNodes.size())
1457 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1459 SDNode *&N = VT.isExtended() ?
1460 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1462 if (N) return SDValue(N, 0);
1463 N = new (NodeAllocator) VTSDNode(VT);
1465 return SDValue(N, 0);
1468 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1469 SDNode *&N = ExternalSymbols[Sym];
1470 if (N) return SDValue(N, 0);
1471 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1473 return SDValue(N, 0);
1476 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1477 SDNode *&N = MCSymbols[Sym];
1479 return SDValue(N, 0);
1480 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1482 return SDValue(N, 0);
1485 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1486 unsigned char TargetFlags) {
1488 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1490 if (N) return SDValue(N, 0);
1491 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1497 if ((unsigned)Cond >= CondCodeNodes.size())
1498 CondCodeNodes.resize(Cond+1);
1500 if (!CondCodeNodes[Cond]) {
1501 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1502 CondCodeNodes[Cond] = N;
1506 return SDValue(CondCodeNodes[Cond], 0);
1509 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1510 // the shuffle mask M that point at N1 to point at N2, and indices that point
1511 // N2 to point at N1.
1512 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1514 ShuffleVectorSDNode::commuteMask(M);
1517 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1518 SDValue N2, const int *Mask) {
1519 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1520 "Invalid VECTOR_SHUFFLE");
1522 // Canonicalize shuffle undef, undef -> undef
1523 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1524 return getUNDEF(VT);
1526 // Validate that all indices in Mask are within the range of the elements
1527 // input to the shuffle.
1528 unsigned NElts = VT.getVectorNumElements();
1529 SmallVector<int, 8> MaskVec;
1530 for (unsigned i = 0; i != NElts; ++i) {
1531 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1532 MaskVec.push_back(Mask[i]);
1535 // Canonicalize shuffle v, v -> v, undef
1538 for (unsigned i = 0; i != NElts; ++i)
1539 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1542 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1543 if (N1.getOpcode() == ISD::UNDEF)
1544 commuteShuffle(N1, N2, MaskVec);
1546 // If shuffling a splat, try to blend the splat instead. We do this here so
1547 // that even when this arises during lowering we don't have to re-handle it.
1548 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1549 BitVector UndefElements;
1550 SDValue Splat = BV->getSplatValue(&UndefElements);
1554 for (int i = 0; i < (int)NElts; ++i) {
1555 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1558 // If this input comes from undef, mark it as such.
1559 if (UndefElements[MaskVec[i] - Offset]) {
1564 // If we can blend a non-undef lane, use that instead.
1565 if (!UndefElements[i])
1566 MaskVec[i] = i + Offset;
1569 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1570 BlendSplat(N1BV, 0);
1571 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1572 BlendSplat(N2BV, NElts);
1574 // Canonicalize all index into lhs, -> shuffle lhs, undef
1575 // Canonicalize all index into rhs, -> shuffle rhs, undef
1576 bool AllLHS = true, AllRHS = true;
1577 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1578 for (unsigned i = 0; i != NElts; ++i) {
1579 if (MaskVec[i] >= (int)NElts) {
1584 } else if (MaskVec[i] >= 0) {
1588 if (AllLHS && AllRHS)
1589 return getUNDEF(VT);
1590 if (AllLHS && !N2Undef)
1594 commuteShuffle(N1, N2, MaskVec);
1596 // Reset our undef status after accounting for the mask.
1597 N2Undef = N2.getOpcode() == ISD::UNDEF;
1598 // Re-check whether both sides ended up undef.
1599 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1600 return getUNDEF(VT);
1602 // If Identity shuffle return that node.
1603 bool Identity = true, AllSame = true;
1604 for (unsigned i = 0; i != NElts; ++i) {
1605 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1606 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1608 if (Identity && NElts)
1611 // Shuffling a constant splat doesn't change the result.
1615 // Look through any bitcasts. We check that these don't change the number
1616 // (and size) of elements and just changes their types.
1617 while (V.getOpcode() == ISD::BITCAST)
1618 V = V->getOperand(0);
1620 // A splat should always show up as a build vector node.
1621 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1622 BitVector UndefElements;
1623 SDValue Splat = BV->getSplatValue(&UndefElements);
1624 // If this is a splat of an undef, shuffling it is also undef.
1625 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1626 return getUNDEF(VT);
1629 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1631 // We only have a splat which can skip shuffles if there is a splatted
1632 // value and no undef lanes rearranged by the shuffle.
1633 if (Splat && UndefElements.none()) {
1634 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1635 // number of elements match or the value splatted is a zero constant.
1638 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1639 if (C->isNullValue())
1643 // If the shuffle itself creates a splat, build the vector directly.
1644 if (AllSame && SameNumElts) {
1645 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1646 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1648 EVT BuildVT = BV->getValueType(0);
1649 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1651 // We may have jumped through bitcasts, so the type of the
1652 // BUILD_VECTOR may not match the type of the shuffle.
1654 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1660 FoldingSetNodeID ID;
1661 SDValue Ops[2] = { N1, N2 };
1662 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1663 for (unsigned i = 0; i != NElts; ++i)
1664 ID.AddInteger(MaskVec[i]);
1667 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1668 return SDValue(E, 0);
1670 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1671 // SDNode doesn't have access to it. This memory will be "leaked" when
1672 // the node is deallocated, but recovered when the NodeAllocator is released.
1673 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1674 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1676 ShuffleVectorSDNode *N =
1677 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1678 dl.getDebugLoc(), N1, N2,
1680 CSEMap.InsertNode(N, IP);
1682 return SDValue(N, 0);
1685 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1686 MVT VT = SV.getSimpleValueType(0);
1687 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1688 ShuffleVectorSDNode::commuteMask(MaskVec);
1690 SDValue Op0 = SV.getOperand(0);
1691 SDValue Op1 = SV.getOperand(1);
1692 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1695 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1696 SDValue Val, SDValue DTy,
1697 SDValue STy, SDValue Rnd, SDValue Sat,
1698 ISD::CvtCode Code) {
1699 // If the src and dest types are the same and the conversion is between
1700 // integer types of the same sign or two floats, no conversion is necessary.
1702 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1705 FoldingSetNodeID ID;
1706 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1707 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1709 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1710 return SDValue(E, 0);
1712 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1715 CSEMap.InsertNode(N, IP);
1717 return SDValue(N, 0);
1720 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1721 FoldingSetNodeID ID;
1722 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1723 ID.AddInteger(RegNo);
1725 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1726 return SDValue(E, 0);
1728 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1729 CSEMap.InsertNode(N, IP);
1731 return SDValue(N, 0);
1734 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1735 FoldingSetNodeID ID;
1736 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1737 ID.AddPointer(RegMask);
1739 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1740 return SDValue(E, 0);
1742 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1743 CSEMap.InsertNode(N, IP);
1745 return SDValue(N, 0);
1748 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1749 FoldingSetNodeID ID;
1750 SDValue Ops[] = { Root };
1751 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1752 ID.AddPointer(Label);
1754 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1755 return SDValue(E, 0);
1757 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1758 dl.getDebugLoc(), Root, Label);
1759 CSEMap.InsertNode(N, IP);
1761 return SDValue(N, 0);
1765 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1768 unsigned char TargetFlags) {
1769 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1771 FoldingSetNodeID ID;
1772 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1774 ID.AddInteger(Offset);
1775 ID.AddInteger(TargetFlags);
1777 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1778 return SDValue(E, 0);
1780 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1782 CSEMap.InsertNode(N, IP);
1784 return SDValue(N, 0);
1787 SDValue SelectionDAG::getSrcValue(const Value *V) {
1788 assert((!V || V->getType()->isPointerTy()) &&
1789 "SrcValue is not a pointer?");
1791 FoldingSetNodeID ID;
1792 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1796 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1797 return SDValue(E, 0);
1799 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1800 CSEMap.InsertNode(N, IP);
1802 return SDValue(N, 0);
1805 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1806 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1807 FoldingSetNodeID ID;
1808 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1812 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1813 return SDValue(E, 0);
1815 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1816 CSEMap.InsertNode(N, IP);
1818 return SDValue(N, 0);
1821 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1822 if (VT == V.getValueType())
1825 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1828 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1829 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1830 unsigned SrcAS, unsigned DestAS) {
1831 SDValue Ops[] = {Ptr};
1832 FoldingSetNodeID ID;
1833 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1834 ID.AddInteger(SrcAS);
1835 ID.AddInteger(DestAS);
1838 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1839 return SDValue(E, 0);
1841 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1843 VT, Ptr, SrcAS, DestAS);
1844 CSEMap.InsertNode(N, IP);
1846 return SDValue(N, 0);
1849 /// getShiftAmountOperand - Return the specified value casted to
1850 /// the target's desired shift amount type.
1851 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1852 EVT OpTy = Op.getValueType();
1853 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1854 if (OpTy == ShTy || OpTy.isVector()) return Op;
1856 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1857 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1860 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1861 /// specified value type.
1862 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1863 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1864 unsigned ByteSize = VT.getStoreSize();
1865 Type *Ty = VT.getTypeForEVT(*getContext());
1866 unsigned StackAlign =
1867 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1869 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1870 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1873 /// CreateStackTemporary - Create a stack temporary suitable for holding
1874 /// either of the specified value types.
1875 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1876 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1877 VT2.getStoreSizeInBits())/8;
1878 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1879 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1880 const DataLayout &DL = getDataLayout();
1882 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1884 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1885 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1886 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1889 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1890 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1891 // These setcc operations always fold.
1895 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1897 case ISD::SETTRUE2: {
1898 TargetLowering::BooleanContent Cnt =
1899 TLI->getBooleanContents(N1->getValueType(0));
1901 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1915 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1919 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1920 const APInt &C2 = N2C->getAPIntValue();
1921 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1922 const APInt &C1 = N1C->getAPIntValue();
1925 default: llvm_unreachable("Unknown integer setcc!");
1926 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1927 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1928 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1929 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1930 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1931 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1932 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1933 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1934 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1935 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1939 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1940 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1941 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1944 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1945 return getUNDEF(VT);
1947 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1948 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1949 return getUNDEF(VT);
1951 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1952 R==APFloat::cmpLessThan, dl, VT);
1953 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1954 return getUNDEF(VT);
1956 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1957 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1958 return getUNDEF(VT);
1960 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1961 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1962 return getUNDEF(VT);
1964 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1965 R==APFloat::cmpEqual, dl, VT);
1966 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1967 return getUNDEF(VT);
1969 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1970 R==APFloat::cmpEqual, dl, VT);
1971 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1972 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1973 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1974 R==APFloat::cmpEqual, dl, VT);
1975 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1976 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1977 R==APFloat::cmpLessThan, dl, VT);
1978 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1979 R==APFloat::cmpUnordered, dl, VT);
1980 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1981 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1984 // Ensure that the constant occurs on the RHS.
1985 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1986 MVT CompVT = N1.getValueType().getSimpleVT();
1987 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1990 return getSetCC(dl, VT, N2, N1, SwappedCond);
1994 // Could not fold it.
1998 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1999 /// use this predicate to simplify operations downstream.
2000 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2001 // This predicate is not safe for vector operations.
2002 if (Op.getValueType().isVector())
2005 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2006 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2009 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2010 /// this predicate to simplify operations downstream. Mask is known to be zero
2011 /// for bits that V cannot have.
2012 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2013 unsigned Depth) const {
2014 APInt KnownZero, KnownOne;
2015 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2016 return (KnownZero & Mask) == Mask;
2019 /// Determine which bits of Op are known to be either zero or one and return
2020 /// them in the KnownZero/KnownOne bitsets.
2021 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2022 APInt &KnownOne, unsigned Depth) const {
2023 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2025 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2027 return; // Limit search depth.
2029 APInt KnownZero2, KnownOne2;
2031 switch (Op.getOpcode()) {
2033 // We know all of the bits for a constant!
2034 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2035 KnownZero = ~KnownOne;
2038 // If either the LHS or the RHS are Zero, the result is zero.
2039 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2040 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2042 // Output known-1 bits are only known if set in both the LHS & RHS.
2043 KnownOne &= KnownOne2;
2044 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2045 KnownZero |= KnownZero2;
2048 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2049 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2051 // Output known-0 bits are only known if clear in both the LHS & RHS.
2052 KnownZero &= KnownZero2;
2053 // Output known-1 are known to be set if set in either the LHS | RHS.
2054 KnownOne |= KnownOne2;
2057 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2058 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2060 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2061 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2062 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2063 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2064 KnownZero = KnownZeroOut;
2068 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2069 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2071 // If low bits are zero in either operand, output low known-0 bits.
2072 // Also compute a conserative estimate for high known-0 bits.
2073 // More trickiness is possible, but this is sufficient for the
2074 // interesting case of alignment computation.
2075 KnownOne.clearAllBits();
2076 unsigned TrailZ = KnownZero.countTrailingOnes() +
2077 KnownZero2.countTrailingOnes();
2078 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2079 KnownZero2.countLeadingOnes(),
2080 BitWidth) - BitWidth;
2082 TrailZ = std::min(TrailZ, BitWidth);
2083 LeadZ = std::min(LeadZ, BitWidth);
2084 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2085 APInt::getHighBitsSet(BitWidth, LeadZ);
2089 // For the purposes of computing leading zeros we can conservatively
2090 // treat a udiv as a logical right shift by the power of 2 known to
2091 // be less than the denominator.
2092 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2093 unsigned LeadZ = KnownZero2.countLeadingOnes();
2095 KnownOne2.clearAllBits();
2096 KnownZero2.clearAllBits();
2097 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2098 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2099 if (RHSUnknownLeadingOnes != BitWidth)
2100 LeadZ = std::min(BitWidth,
2101 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2103 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2107 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2108 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2110 // Only known if known in both the LHS and RHS.
2111 KnownOne &= KnownOne2;
2112 KnownZero &= KnownZero2;
2114 case ISD::SELECT_CC:
2115 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2116 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2118 // Only known if known in both the LHS and RHS.
2119 KnownOne &= KnownOne2;
2120 KnownZero &= KnownZero2;
2128 if (Op.getResNo() != 1)
2130 // The boolean result conforms to getBooleanContents.
2131 // If we know the result of a setcc has the top bits zero, use this info.
2132 // We know that we have an integer-based boolean since these operations
2133 // are only available for integer.
2134 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2135 TargetLowering::ZeroOrOneBooleanContent &&
2137 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2140 // If we know the result of a setcc has the top bits zero, use this info.
2141 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2142 TargetLowering::ZeroOrOneBooleanContent &&
2144 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2147 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2148 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2149 unsigned ShAmt = SA->getZExtValue();
2151 // If the shift count is an invalid immediate, don't do anything.
2152 if (ShAmt >= BitWidth)
2155 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2156 KnownZero <<= ShAmt;
2158 // low bits known zero.
2159 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2163 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2164 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2165 unsigned ShAmt = SA->getZExtValue();
2167 // If the shift count is an invalid immediate, don't do anything.
2168 if (ShAmt >= BitWidth)
2171 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2172 KnownZero = KnownZero.lshr(ShAmt);
2173 KnownOne = KnownOne.lshr(ShAmt);
2175 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2176 KnownZero |= HighBits; // High bits known zero.
2180 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2181 unsigned ShAmt = SA->getZExtValue();
2183 // If the shift count is an invalid immediate, don't do anything.
2184 if (ShAmt >= BitWidth)
2187 // If any of the demanded bits are produced by the sign extension, we also
2188 // demand the input sign bit.
2189 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2191 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2192 KnownZero = KnownZero.lshr(ShAmt);
2193 KnownOne = KnownOne.lshr(ShAmt);
2195 // Handle the sign bits.
2196 APInt SignBit = APInt::getSignBit(BitWidth);
2197 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2199 if (KnownZero.intersects(SignBit)) {
2200 KnownZero |= HighBits; // New bits are known zero.
2201 } else if (KnownOne.intersects(SignBit)) {
2202 KnownOne |= HighBits; // New bits are known one.
2206 case ISD::SIGN_EXTEND_INREG: {
2207 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2208 unsigned EBits = EVT.getScalarType().getSizeInBits();
2210 // Sign extension. Compute the demanded bits in the result that are not
2211 // present in the input.
2212 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2214 APInt InSignBit = APInt::getSignBit(EBits);
2215 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2217 // If the sign extended bits are demanded, we know that the sign
2219 InSignBit = InSignBit.zext(BitWidth);
2220 if (NewBits.getBoolValue())
2221 InputDemandedBits |= InSignBit;
2223 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2224 KnownOne &= InputDemandedBits;
2225 KnownZero &= InputDemandedBits;
2227 // If the sign bit of the input is known set or clear, then we know the
2228 // top bits of the result.
2229 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2230 KnownZero |= NewBits;
2231 KnownOne &= ~NewBits;
2232 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2233 KnownOne |= NewBits;
2234 KnownZero &= ~NewBits;
2235 } else { // Input sign bit unknown
2236 KnownZero &= ~NewBits;
2237 KnownOne &= ~NewBits;
2242 case ISD::CTTZ_ZERO_UNDEF:
2244 case ISD::CTLZ_ZERO_UNDEF:
2246 unsigned LowBits = Log2_32(BitWidth)+1;
2247 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2248 KnownOne.clearAllBits();
2252 LoadSDNode *LD = cast<LoadSDNode>(Op);
2253 // If this is a ZEXTLoad and we are looking at the loaded value.
2254 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2255 EVT VT = LD->getMemoryVT();
2256 unsigned MemBits = VT.getScalarType().getSizeInBits();
2257 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2258 } else if (const MDNode *Ranges = LD->getRanges()) {
2259 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2263 case ISD::ZERO_EXTEND: {
2264 EVT InVT = Op.getOperand(0).getValueType();
2265 unsigned InBits = InVT.getScalarType().getSizeInBits();
2266 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2267 KnownZero = KnownZero.trunc(InBits);
2268 KnownOne = KnownOne.trunc(InBits);
2269 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2270 KnownZero = KnownZero.zext(BitWidth);
2271 KnownOne = KnownOne.zext(BitWidth);
2272 KnownZero |= NewBits;
2275 case ISD::SIGN_EXTEND: {
2276 EVT InVT = Op.getOperand(0).getValueType();
2277 unsigned InBits = InVT.getScalarType().getSizeInBits();
2278 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2280 KnownZero = KnownZero.trunc(InBits);
2281 KnownOne = KnownOne.trunc(InBits);
2282 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2284 // Note if the sign bit is known to be zero or one.
2285 bool SignBitKnownZero = KnownZero.isNegative();
2286 bool SignBitKnownOne = KnownOne.isNegative();
2288 KnownZero = KnownZero.zext(BitWidth);
2289 KnownOne = KnownOne.zext(BitWidth);
2291 // If the sign bit is known zero or one, the top bits match.
2292 if (SignBitKnownZero)
2293 KnownZero |= NewBits;
2294 else if (SignBitKnownOne)
2295 KnownOne |= NewBits;
2298 case ISD::ANY_EXTEND: {
2299 EVT InVT = Op.getOperand(0).getValueType();
2300 unsigned InBits = InVT.getScalarType().getSizeInBits();
2301 KnownZero = KnownZero.trunc(InBits);
2302 KnownOne = KnownOne.trunc(InBits);
2303 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2304 KnownZero = KnownZero.zext(BitWidth);
2305 KnownOne = KnownOne.zext(BitWidth);
2308 case ISD::TRUNCATE: {
2309 EVT InVT = Op.getOperand(0).getValueType();
2310 unsigned InBits = InVT.getScalarType().getSizeInBits();
2311 KnownZero = KnownZero.zext(InBits);
2312 KnownOne = KnownOne.zext(InBits);
2313 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2314 KnownZero = KnownZero.trunc(BitWidth);
2315 KnownOne = KnownOne.trunc(BitWidth);
2318 case ISD::AssertZext: {
2319 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2320 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2321 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2322 KnownZero |= (~InMask);
2323 KnownOne &= (~KnownZero);
2327 // All bits are zero except the low bit.
2328 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2332 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2333 // We know that the top bits of C-X are clear if X contains less bits
2334 // than C (i.e. no wrap-around can happen). For example, 20-X is
2335 // positive if we can prove that X is >= 0 and < 16.
2336 if (CLHS->getAPIntValue().isNonNegative()) {
2337 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2338 // NLZ can't be BitWidth with no sign bit
2339 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2340 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2342 // If all of the MaskV bits are known to be zero, then we know the
2343 // output top bits are zero, because we now know that the output is
2345 if ((KnownZero2 & MaskV) == MaskV) {
2346 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2347 // Top bits known zero.
2348 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2356 // Output known-0 bits are known if clear or set in both the low clear bits
2357 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2358 // low 3 bits clear.
2359 // Output known-0 bits are also known if the top bits of each input are
2360 // known to be clear. For example, if one input has the top 10 bits clear
2361 // and the other has the top 8 bits clear, we know the top 7 bits of the
2362 // output must be clear.
2363 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2364 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2365 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2367 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2368 KnownZeroHigh = std::min(KnownZeroHigh,
2369 KnownZero2.countLeadingOnes());
2370 KnownZeroLow = std::min(KnownZeroLow,
2371 KnownZero2.countTrailingOnes());
2373 if (Op.getOpcode() == ISD::ADD) {
2374 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2375 if (KnownZeroHigh > 1)
2376 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2380 // With ADDE, a carry bit may be added in, so we can only use this
2381 // information if we know (at least) that the low two bits are clear. We
2382 // then return to the caller that the low bit is unknown but that other bits
2384 if (KnownZeroLow >= 2) // ADDE
2385 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2389 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2390 const APInt &RA = Rem->getAPIntValue().abs();
2391 if (RA.isPowerOf2()) {
2392 APInt LowBits = RA - 1;
2393 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2395 // The low bits of the first operand are unchanged by the srem.
2396 KnownZero = KnownZero2 & LowBits;
2397 KnownOne = KnownOne2 & LowBits;
2399 // If the first operand is non-negative or has all low bits zero, then
2400 // the upper bits are all zero.
2401 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2402 KnownZero |= ~LowBits;
2404 // If the first operand is negative and not all low bits are zero, then
2405 // the upper bits are all one.
2406 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2407 KnownOne |= ~LowBits;
2408 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2413 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2414 const APInt &RA = Rem->getAPIntValue();
2415 if (RA.isPowerOf2()) {
2416 APInt LowBits = (RA - 1);
2417 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2419 // The upper bits are all zero, the lower ones are unchanged.
2420 KnownZero = KnownZero2 | ~LowBits;
2421 KnownOne = KnownOne2 & LowBits;
2426 // Since the result is less than or equal to either operand, any leading
2427 // zero bits in either operand must also exist in the result.
2428 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2429 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2431 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2432 KnownZero2.countLeadingOnes());
2433 KnownOne.clearAllBits();
2434 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2437 case ISD::EXTRACT_ELEMENT: {
2438 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2439 const unsigned Index =
2440 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2441 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2443 // Remove low part of known bits mask
2444 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2445 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2447 // Remove high part of known bit mask
2448 KnownZero = KnownZero.trunc(BitWidth);
2449 KnownOne = KnownOne.trunc(BitWidth);
2456 APInt Op0Zero, Op0One;
2457 APInt Op1Zero, Op1One;
2458 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2459 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2461 KnownZero = Op0Zero & Op1Zero;
2462 KnownOne = Op0One & Op1One;
2465 case ISD::FrameIndex:
2466 case ISD::TargetFrameIndex:
2467 if (unsigned Align = InferPtrAlignment(Op)) {
2468 // The low bits are known zero if the pointer is aligned.
2469 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2475 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2478 case ISD::INTRINSIC_WO_CHAIN:
2479 case ISD::INTRINSIC_W_CHAIN:
2480 case ISD::INTRINSIC_VOID:
2481 // Allow the target to implement this method for its nodes.
2482 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2486 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2489 /// ComputeNumSignBits - Return the number of times the sign bit of the
2490 /// register is replicated into the other bits. We know that at least 1 bit
2491 /// is always equal to the sign bit (itself), but other cases can give us
2492 /// information. For example, immediately after an "SRA X, 2", we know that
2493 /// the top 3 bits are all equal to each other, so we return 3.
2494 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2495 EVT VT = Op.getValueType();
2496 assert(VT.isInteger() && "Invalid VT!");
2497 unsigned VTBits = VT.getScalarType().getSizeInBits();
2499 unsigned FirstAnswer = 1;
2502 return 1; // Limit search depth.
2504 switch (Op.getOpcode()) {
2506 case ISD::AssertSext:
2507 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2508 return VTBits-Tmp+1;
2509 case ISD::AssertZext:
2510 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2513 case ISD::Constant: {
2514 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2515 return Val.getNumSignBits();
2518 case ISD::SIGN_EXTEND:
2520 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2521 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2523 case ISD::SIGN_EXTEND_INREG:
2524 // Max of the input and what this extends.
2526 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2529 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2530 return std::max(Tmp, Tmp2);
2533 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2534 // SRA X, C -> adds C sign bits.
2535 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2536 Tmp += C->getZExtValue();
2537 if (Tmp > VTBits) Tmp = VTBits;
2541 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2542 // shl destroys sign bits.
2543 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2544 if (C->getZExtValue() >= VTBits || // Bad shift.
2545 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2546 return Tmp - C->getZExtValue();
2551 case ISD::XOR: // NOT is handled here.
2552 // Logical binary ops preserve the number of sign bits at the worst.
2553 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2555 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2556 FirstAnswer = std::min(Tmp, Tmp2);
2557 // We computed what we know about the sign bits as our first
2558 // answer. Now proceed to the generic code that uses
2559 // computeKnownBits, and pick whichever answer is better.
2564 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2565 if (Tmp == 1) return 1; // Early out.
2566 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2567 return std::min(Tmp, Tmp2);
2572 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2574 return 1; // Early out.
2575 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2576 return std::min(Tmp, Tmp2);
2583 if (Op.getResNo() != 1)
2585 // The boolean result conforms to getBooleanContents. Fall through.
2586 // If setcc returns 0/-1, all bits are sign bits.
2587 // We know that we have an integer-based boolean since these operations
2588 // are only available for integer.
2589 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2590 TargetLowering::ZeroOrNegativeOneBooleanContent)
2594 // If setcc returns 0/-1, all bits are sign bits.
2595 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2596 TargetLowering::ZeroOrNegativeOneBooleanContent)
2601 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2602 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2604 // Handle rotate right by N like a rotate left by 32-N.
2605 if (Op.getOpcode() == ISD::ROTR)
2606 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2608 // If we aren't rotating out all of the known-in sign bits, return the
2609 // number that are left. This handles rotl(sext(x), 1) for example.
2610 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2611 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2615 // Add can have at most one carry bit. Thus we know that the output
2616 // is, at worst, one more bit than the inputs.
2617 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2618 if (Tmp == 1) return 1; // Early out.
2620 // Special case decrementing a value (ADD X, -1):
2621 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2622 if (CRHS->isAllOnesValue()) {
2623 APInt KnownZero, KnownOne;
2624 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2626 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2628 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2631 // If we are subtracting one from a positive number, there is no carry
2632 // out of the result.
2633 if (KnownZero.isNegative())
2637 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2638 if (Tmp2 == 1) return 1;
2639 return std::min(Tmp, Tmp2)-1;
2642 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2643 if (Tmp2 == 1) return 1;
2646 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2647 if (CLHS->isNullValue()) {
2648 APInt KnownZero, KnownOne;
2649 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2650 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2652 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2655 // If the input is known to be positive (the sign bit is known clear),
2656 // the output of the NEG has the same number of sign bits as the input.
2657 if (KnownZero.isNegative())
2660 // Otherwise, we treat this like a SUB.
2663 // Sub can have at most one carry bit. Thus we know that the output
2664 // is, at worst, one more bit than the inputs.
2665 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2666 if (Tmp == 1) return 1; // Early out.
2667 return std::min(Tmp, Tmp2)-1;
2669 // FIXME: it's tricky to do anything useful for this, but it is an important
2670 // case for targets like X86.
2672 case ISD::EXTRACT_ELEMENT: {
2673 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2674 const int BitWidth = Op.getValueType().getSizeInBits();
2676 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2678 // Get reverse index (starting from 1), Op1 value indexes elements from
2679 // little end. Sign starts at big end.
2680 const int rIndex = Items - 1 -
2681 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2683 // If the sign portion ends in our element the substraction gives correct
2684 // result. Otherwise it gives either negative or > bitwidth result
2685 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2689 // If we are looking at the loaded value of the SDNode.
2690 if (Op.getResNo() == 0) {
2691 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2692 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2693 unsigned ExtType = LD->getExtensionType();
2696 case ISD::SEXTLOAD: // '17' bits known
2697 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2698 return VTBits-Tmp+1;
2699 case ISD::ZEXTLOAD: // '16' bits known
2700 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2706 // Allow the target to implement this method for its nodes.
2707 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2708 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2709 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2710 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2711 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2712 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2715 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2716 // use this information.
2717 APInt KnownZero, KnownOne;
2718 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2721 if (KnownZero.isNegative()) { // sign bit is 0
2723 } else if (KnownOne.isNegative()) { // sign bit is 1;
2730 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2731 // the number of identical bits in the top of the input value.
2733 Mask <<= Mask.getBitWidth()-VTBits;
2734 // Return # leading zeros. We use 'min' here in case Val was zero before
2735 // shifting. We don't want to return '64' as for an i32 "0".
2736 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2739 /// isBaseWithConstantOffset - Return true if the specified operand is an
2740 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2741 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2742 /// semantics as an ADD. This handles the equivalence:
2743 /// X|Cst == X+Cst iff X&Cst = 0.
2744 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2745 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2746 !isa<ConstantSDNode>(Op.getOperand(1)))
2749 if (Op.getOpcode() == ISD::OR &&
2750 !MaskedValueIsZero(Op.getOperand(0),
2751 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2758 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2759 // If we're told that NaNs won't happen, assume they won't.
2760 if (getTarget().Options.NoNaNsFPMath)
2763 // If the value is a constant, we can obviously see if it is a NaN or not.
2764 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2765 return !C->getValueAPF().isNaN();
2767 // TODO: Recognize more cases here.
2772 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2773 // If the value is a constant, we can obviously see if it is a zero or not.
2774 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2775 return !C->isZero();
2777 // TODO: Recognize more cases here.
2778 switch (Op.getOpcode()) {
2781 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2782 return !C->isNullValue();
2789 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2790 // Check the obvious case.
2791 if (A == B) return true;
2793 // For for negative and positive zero.
2794 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2795 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2796 if (CA->isZero() && CB->isZero()) return true;
2798 // Otherwise they may not be equal.
2802 /// getNode - Gets or creates the specified node.
2804 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2805 FoldingSetNodeID ID;
2806 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2808 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2809 return SDValue(E, 0);
2811 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2812 DL.getDebugLoc(), getVTList(VT));
2813 CSEMap.InsertNode(N, IP);
2816 return SDValue(N, 0);
2819 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2820 EVT VT, SDValue Operand) {
2821 // Constant fold unary operations with an integer constant operand. Even
2822 // opaque constant will be folded, because the folding of unary operations
2823 // doesn't create new constants with different values. Nevertheless, the
2824 // opaque flag is preserved during folding to prevent future folding with
2826 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2827 const APInt &Val = C->getAPIntValue();
2830 case ISD::SIGN_EXTEND:
2831 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2832 C->isTargetOpcode(), C->isOpaque());
2833 case ISD::ANY_EXTEND:
2834 case ISD::ZERO_EXTEND:
2836 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2837 C->isTargetOpcode(), C->isOpaque());
2838 case ISD::UINT_TO_FP:
2839 case ISD::SINT_TO_FP: {
2840 APFloat apf(EVTToAPFloatSemantics(VT),
2841 APInt::getNullValue(VT.getSizeInBits()));
2842 (void)apf.convertFromAPInt(Val,
2843 Opcode==ISD::SINT_TO_FP,
2844 APFloat::rmNearestTiesToEven);
2845 return getConstantFP(apf, DL, VT);
2848 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2849 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2850 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2851 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2852 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2853 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2856 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2859 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2862 case ISD::CTLZ_ZERO_UNDEF:
2863 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2866 case ISD::CTTZ_ZERO_UNDEF:
2867 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2872 // Constant fold unary operations with a floating point constant operand.
2873 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2874 APFloat V = C->getValueAPF(); // make copy
2878 return getConstantFP(V, DL, VT);
2881 return getConstantFP(V, DL, VT);
2883 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2884 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2885 return getConstantFP(V, DL, VT);
2889 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2890 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2891 return getConstantFP(V, DL, VT);
2895 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2896 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2897 return getConstantFP(V, DL, VT);
2900 case ISD::FP_EXTEND: {
2902 // This can return overflow, underflow, or inexact; we don't care.
2903 // FIXME need to be more flexible about rounding mode.
2904 (void)V.convert(EVTToAPFloatSemantics(VT),
2905 APFloat::rmNearestTiesToEven, &ignored);
2906 return getConstantFP(V, DL, VT);
2908 case ISD::FP_TO_SINT:
2909 case ISD::FP_TO_UINT: {
2912 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2913 // FIXME need to be more flexible about rounding mode.
2914 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2915 Opcode==ISD::FP_TO_SINT,
2916 APFloat::rmTowardZero, &ignored);
2917 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2919 APInt api(VT.getSizeInBits(), x);
2920 return getConstant(api, DL, VT);
2923 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2924 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2925 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2926 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2927 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2928 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2933 // Constant fold unary operations with a vector integer or float operand.
2934 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2935 if (BV->isConstant()) {
2938 // FIXME: Entirely reasonable to perform folding of other unary
2939 // operations here as the need arises.
2946 case ISD::FP_EXTEND:
2947 case ISD::FP_TO_SINT:
2948 case ISD::FP_TO_UINT:
2950 case ISD::UINT_TO_FP:
2951 case ISD::SINT_TO_FP:
2954 case ISD::CTLZ_ZERO_UNDEF:
2956 case ISD::CTTZ_ZERO_UNDEF:
2958 EVT SVT = VT.getScalarType();
2959 EVT InVT = BV->getValueType(0);
2960 EVT InSVT = InVT.getScalarType();
2962 // Find legal integer scalar type for constant promotion and
2963 // ensure that its scalar size is at least as large as source.
2965 if (SVT.isInteger()) {
2966 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2967 if (LegalSVT.bitsLT(SVT)) break;
2970 // Let the above scalar folding handle the folding of each element.
2971 SmallVector<SDValue, 8> Ops;
2972 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2973 SDValue OpN = BV->getOperand(i);
2974 EVT OpVT = OpN.getValueType();
2976 // Build vector (integer) scalar operands may need implicit
2977 // truncation - do this before constant folding.
2978 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2979 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2981 OpN = getNode(Opcode, DL, SVT, OpN);
2983 // Legalize the (integer) scalar constant if necessary.
2984 if (LegalSVT != SVT)
2985 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2987 if (OpN.getOpcode() != ISD::UNDEF &&
2988 OpN.getOpcode() != ISD::Constant &&
2989 OpN.getOpcode() != ISD::ConstantFP)
2993 if (Ops.size() == VT.getVectorNumElements())
2994 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3001 unsigned OpOpcode = Operand.getNode()->getOpcode();
3003 case ISD::TokenFactor:
3004 case ISD::MERGE_VALUES:
3005 case ISD::CONCAT_VECTORS:
3006 return Operand; // Factor, merge or concat of one node? No need.
3007 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3008 case ISD::FP_EXTEND:
3009 assert(VT.isFloatingPoint() &&
3010 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3011 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3012 assert((!VT.isVector() ||
3013 VT.getVectorNumElements() ==
3014 Operand.getValueType().getVectorNumElements()) &&
3015 "Vector element count mismatch!");
3016 if (Operand.getOpcode() == ISD::UNDEF)
3017 return getUNDEF(VT);
3019 case ISD::SIGN_EXTEND:
3020 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3021 "Invalid SIGN_EXTEND!");
3022 if (Operand.getValueType() == VT) return Operand; // noop extension
3023 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3024 "Invalid sext node, dst < src!");
3025 assert((!VT.isVector() ||
3026 VT.getVectorNumElements() ==
3027 Operand.getValueType().getVectorNumElements()) &&
3028 "Vector element count mismatch!");
3029 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3030 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3031 else if (OpOpcode == ISD::UNDEF)
3032 // sext(undef) = 0, because the top bits will all be the same.
3033 return getConstant(0, DL, VT);
3035 case ISD::ZERO_EXTEND:
3036 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3037 "Invalid ZERO_EXTEND!");
3038 if (Operand.getValueType() == VT) return Operand; // noop extension
3039 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3040 "Invalid zext node, dst < src!");
3041 assert((!VT.isVector() ||
3042 VT.getVectorNumElements() ==
3043 Operand.getValueType().getVectorNumElements()) &&
3044 "Vector element count mismatch!");
3045 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3046 return getNode(ISD::ZERO_EXTEND, DL, VT,
3047 Operand.getNode()->getOperand(0));
3048 else if (OpOpcode == ISD::UNDEF)
3049 // zext(undef) = 0, because the top bits will be zero.
3050 return getConstant(0, DL, VT);
3052 case ISD::ANY_EXTEND:
3053 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3054 "Invalid ANY_EXTEND!");
3055 if (Operand.getValueType() == VT) return Operand; // noop extension
3056 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3057 "Invalid anyext node, dst < src!");
3058 assert((!VT.isVector() ||
3059 VT.getVectorNumElements() ==
3060 Operand.getValueType().getVectorNumElements()) &&
3061 "Vector element count mismatch!");
3063 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3064 OpOpcode == ISD::ANY_EXTEND)
3065 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3066 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3067 else if (OpOpcode == ISD::UNDEF)
3068 return getUNDEF(VT);
3070 // (ext (trunx x)) -> x
3071 if (OpOpcode == ISD::TRUNCATE) {
3072 SDValue OpOp = Operand.getNode()->getOperand(0);
3073 if (OpOp.getValueType() == VT)
3078 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3079 "Invalid TRUNCATE!");
3080 if (Operand.getValueType() == VT) return Operand; // noop truncate
3081 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3082 "Invalid truncate node, src < dst!");
3083 assert((!VT.isVector() ||
3084 VT.getVectorNumElements() ==
3085 Operand.getValueType().getVectorNumElements()) &&
3086 "Vector element count mismatch!");
3087 if (OpOpcode == ISD::TRUNCATE)
3088 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3089 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3090 OpOpcode == ISD::ANY_EXTEND) {
3091 // If the source is smaller than the dest, we still need an extend.
3092 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3093 .bitsLT(VT.getScalarType()))
3094 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3095 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3096 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3097 return Operand.getNode()->getOperand(0);
3099 if (OpOpcode == ISD::UNDEF)
3100 return getUNDEF(VT);
3103 assert(VT.isInteger() && VT == Operand.getValueType() &&
3105 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3106 "BSWAP types must be a multiple of 16 bits!");
3107 if (OpOpcode == ISD::UNDEF)
3108 return getUNDEF(VT);
3111 // Basic sanity checking.
3112 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3113 && "Cannot BITCAST between types of different sizes!");
3114 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3115 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3116 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3117 if (OpOpcode == ISD::UNDEF)
3118 return getUNDEF(VT);
3120 case ISD::SCALAR_TO_VECTOR:
3121 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3122 (VT.getVectorElementType() == Operand.getValueType() ||
3123 (VT.getVectorElementType().isInteger() &&
3124 Operand.getValueType().isInteger() &&
3125 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3126 "Illegal SCALAR_TO_VECTOR node!");
3127 if (OpOpcode == ISD::UNDEF)
3128 return getUNDEF(VT);
3129 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3130 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3131 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3132 Operand.getConstantOperandVal(1) == 0 &&
3133 Operand.getOperand(0).getValueType() == VT)
3134 return Operand.getOperand(0);
3137 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3138 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3139 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3140 Operand.getNode()->getOperand(0));
3141 if (OpOpcode == ISD::FNEG) // --X -> X
3142 return Operand.getNode()->getOperand(0);
3145 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3146 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3151 SDVTList VTs = getVTList(VT);
3152 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3153 FoldingSetNodeID ID;
3154 SDValue Ops[1] = { Operand };
3155 AddNodeIDNode(ID, Opcode, VTs, Ops);
3157 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3158 return SDValue(E, 0);
3160 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3161 DL.getDebugLoc(), VTs, Operand);
3162 CSEMap.InsertNode(N, IP);
3164 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3165 DL.getDebugLoc(), VTs, Operand);
3169 return SDValue(N, 0);
3172 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3175 case ISD::ADD: return std::make_pair(C1 + C2, true);
3176 case ISD::SUB: return std::make_pair(C1 - C2, true);
3177 case ISD::MUL: return std::make_pair(C1 * C2, true);
3178 case ISD::AND: return std::make_pair(C1 & C2, true);
3179 case ISD::OR: return std::make_pair(C1 | C2, true);
3180 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3181 case ISD::SHL: return std::make_pair(C1 << C2, true);
3182 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3183 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3184 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3185 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3187 if (!C2.getBoolValue())
3189 return std::make_pair(C1.udiv(C2), true);
3191 if (!C2.getBoolValue())
3193 return std::make_pair(C1.urem(C2), true);
3195 if (!C2.getBoolValue())
3197 return std::make_pair(C1.sdiv(C2), true);
3199 if (!C2.getBoolValue())
3201 return std::make_pair(C1.srem(C2), true);
3203 return std::make_pair(APInt(1, 0), false);
3206 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3207 const ConstantSDNode *Cst1,
3208 const ConstantSDNode *Cst2) {
3209 if (Cst1->isOpaque() || Cst2->isOpaque())
3212 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3213 Cst2->getAPIntValue());
3216 return getConstant(Folded.first, DL, VT);
3219 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3220 SDNode *Cst1, SDNode *Cst2) {
3221 // If the opcode is a target-specific ISD node, there's nothing we can
3222 // do here and the operand rules may not line up with the below, so
3224 if (Opcode >= ISD::BUILTIN_OP_END)
3227 // Handle the case of two scalars.
3228 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3229 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3230 if (SDValue Folded =
3231 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3234 SmallVector<SDValue, 4> Outputs;
3235 // We may have a vector type but a scalar result. Create a splat.
3236 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3237 // Build a big vector out of the scalar elements we generated.
3238 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3245 // For vectors extract each constant element into Inputs so we can constant
3246 // fold them individually.
3247 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3248 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3252 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3254 EVT SVT = VT.getScalarType();
3255 SmallVector<SDValue, 4> Outputs;
3256 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3257 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3258 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3259 if (!V1 || !V2) // Not a constant, bail.
3262 if (V1->isOpaque() || V2->isOpaque())
3265 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3266 // FIXME: This is valid and could be handled by truncating the APInts.
3267 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3270 // Fold one vector element.
3271 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3272 V2->getAPIntValue());
3275 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3278 assert(VT.getVectorNumElements() == Outputs.size() &&
3279 "Vector size mismatch!");
3281 // We may have a vector type but a scalar result. Create a splat.
3282 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3284 // Build a big vector out of the scalar elements we generated.
3285 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3288 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3289 SDValue N2, const SDNodeFlags *Flags) {
3290 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3291 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3294 case ISD::TokenFactor:
3295 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3296 N2.getValueType() == MVT::Other && "Invalid token factor!");
3297 // Fold trivial token factors.
3298 if (N1.getOpcode() == ISD::EntryToken) return N2;
3299 if (N2.getOpcode() == ISD::EntryToken) return N1;
3300 if (N1 == N2) return N1;
3302 case ISD::CONCAT_VECTORS:
3303 // Concat of UNDEFs is UNDEF.
3304 if (N1.getOpcode() == ISD::UNDEF &&
3305 N2.getOpcode() == ISD::UNDEF)
3306 return getUNDEF(VT);
3308 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3309 // one big BUILD_VECTOR.
3310 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3311 N2.getOpcode() == ISD::BUILD_VECTOR) {
3312 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3313 N1.getNode()->op_end());
3314 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3316 // BUILD_VECTOR requires all inputs to be of the same type, find the
3317 // maximum type and extend them all.
3318 EVT SVT = VT.getScalarType();
3319 for (SDValue Op : Elts)
3320 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3321 if (SVT.bitsGT(VT.getScalarType()))
3322 for (SDValue &Op : Elts)
3323 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3324 ? getZExtOrTrunc(Op, DL, SVT)
3325 : getSExtOrTrunc(Op, DL, SVT);
3327 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3331 assert(VT.isInteger() && "This operator does not apply to FP types!");
3332 assert(N1.getValueType() == N2.getValueType() &&
3333 N1.getValueType() == VT && "Binary operator types must match!");
3334 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3335 // worth handling here.
3336 if (N2C && N2C->isNullValue())
3338 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3345 assert(VT.isInteger() && "This operator does not apply to FP types!");
3346 assert(N1.getValueType() == N2.getValueType() &&
3347 N1.getValueType() == VT && "Binary operator types must match!");
3348 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3349 // it's worth handling here.
3350 if (N2C && N2C->isNullValue())
3360 assert(VT.isInteger() && "This operator does not apply to FP types!");
3361 assert(N1.getValueType() == N2.getValueType() &&
3362 N1.getValueType() == VT && "Binary operator types must match!");
3369 if (getTarget().Options.UnsafeFPMath) {
3370 if (Opcode == ISD::FADD) {
3372 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3373 if (CFP->getValueAPF().isZero())
3376 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3377 if (CFP->getValueAPF().isZero())
3379 } else if (Opcode == ISD::FSUB) {
3381 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3382 if (CFP->getValueAPF().isZero())
3384 } else if (Opcode == ISD::FMUL) {
3385 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3388 // If the first operand isn't the constant, try the second
3390 CFP = dyn_cast<ConstantFPSDNode>(N2);
3397 return SDValue(CFP,0);
3399 if (CFP->isExactlyValue(1.0))
3404 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3405 assert(N1.getValueType() == N2.getValueType() &&
3406 N1.getValueType() == VT && "Binary operator types must match!");
3408 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3409 assert(N1.getValueType() == VT &&
3410 N1.getValueType().isFloatingPoint() &&
3411 N2.getValueType().isFloatingPoint() &&
3412 "Invalid FCOPYSIGN!");
3419 assert(VT == N1.getValueType() &&
3420 "Shift operators return type must be the same as their first arg");
3421 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3422 "Shifts only work on integers");
3423 assert((!VT.isVector() || VT == N2.getValueType()) &&
3424 "Vector shift amounts must be in the same as their first arg");
3425 // Verify that the shift amount VT is bit enough to hold valid shift
3426 // amounts. This catches things like trying to shift an i1024 value by an
3427 // i8, which is easy to fall into in generic code that uses
3428 // TLI.getShiftAmount().
3429 assert(N2.getValueType().getSizeInBits() >=
3430 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3431 "Invalid use of small shift amount with oversized value!");
3433 // Always fold shifts of i1 values so the code generator doesn't need to
3434 // handle them. Since we know the size of the shift has to be less than the
3435 // size of the value, the shift/rotate count is guaranteed to be zero.
3438 if (N2C && N2C->isNullValue())
3441 case ISD::FP_ROUND_INREG: {
3442 EVT EVT = cast<VTSDNode>(N2)->getVT();
3443 assert(VT == N1.getValueType() && "Not an inreg round!");
3444 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3445 "Cannot FP_ROUND_INREG integer types");
3446 assert(EVT.isVector() == VT.isVector() &&
3447 "FP_ROUND_INREG type should be vector iff the operand "
3449 assert((!EVT.isVector() ||
3450 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3451 "Vector element counts must match in FP_ROUND_INREG");
3452 assert(EVT.bitsLE(VT) && "Not rounding down!");
3454 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3458 assert(VT.isFloatingPoint() &&
3459 N1.getValueType().isFloatingPoint() &&
3460 VT.bitsLE(N1.getValueType()) &&
3461 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3462 if (N1.getValueType() == VT) return N1; // noop conversion.
3464 case ISD::AssertSext:
3465 case ISD::AssertZext: {
3466 EVT EVT = cast<VTSDNode>(N2)->getVT();
3467 assert(VT == N1.getValueType() && "Not an inreg extend!");
3468 assert(VT.isInteger() && EVT.isInteger() &&
3469 "Cannot *_EXTEND_INREG FP types");
3470 assert(!EVT.isVector() &&
3471 "AssertSExt/AssertZExt type should be the vector element type "
3472 "rather than the vector type!");
3473 assert(EVT.bitsLE(VT) && "Not extending!");
3474 if (VT == EVT) return N1; // noop assertion.
3477 case ISD::SIGN_EXTEND_INREG: {
3478 EVT EVT = cast<VTSDNode>(N2)->getVT();
3479 assert(VT == N1.getValueType() && "Not an inreg extend!");
3480 assert(VT.isInteger() && EVT.isInteger() &&
3481 "Cannot *_EXTEND_INREG FP types");
3482 assert(EVT.isVector() == VT.isVector() &&
3483 "SIGN_EXTEND_INREG type should be vector iff the operand "
3485 assert((!EVT.isVector() ||
3486 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3487 "Vector element counts must match in SIGN_EXTEND_INREG");
3488 assert(EVT.bitsLE(VT) && "Not extending!");
3489 if (EVT == VT) return N1; // Not actually extending
3491 auto SignExtendInReg = [&](APInt Val) {
3492 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3493 Val <<= Val.getBitWidth() - FromBits;
3494 Val = Val.ashr(Val.getBitWidth() - FromBits);
3495 return getConstant(Val, DL, VT.getScalarType());
3499 APInt Val = N1C->getAPIntValue();
3500 return SignExtendInReg(Val);
3502 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3503 SmallVector<SDValue, 8> Ops;
3504 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3505 SDValue Op = N1.getOperand(i);
3506 if (Op.getValueType() != VT.getScalarType()) break;
3507 if (Op.getOpcode() == ISD::UNDEF) {
3511 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3512 APInt Val = C->getAPIntValue();
3513 Ops.push_back(SignExtendInReg(Val));
3518 if (Ops.size() == VT.getVectorNumElements())
3519 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3523 case ISD::EXTRACT_VECTOR_ELT:
3524 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3525 if (N1.getOpcode() == ISD::UNDEF)
3526 return getUNDEF(VT);
3528 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3529 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3530 return getUNDEF(VT);
3532 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3533 // expanding copies of large vectors from registers.
3535 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3536 N1.getNumOperands() > 0) {
3538 N1.getOperand(0).getValueType().getVectorNumElements();
3539 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3540 N1.getOperand(N2C->getZExtValue() / Factor),
3541 getConstant(N2C->getZExtValue() % Factor, DL,
3542 N2.getValueType()));
3545 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3546 // expanding large vector constants.
3547 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3548 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3550 if (VT != Elt.getValueType())
3551 // If the vector element type is not legal, the BUILD_VECTOR operands
3552 // are promoted and implicitly truncated, and the result implicitly
3553 // extended. Make that explicit here.
3554 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3559 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3560 // operations are lowered to scalars.
3561 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3562 // If the indices are the same, return the inserted element else
3563 // if the indices are known different, extract the element from
3564 // the original vector.
3565 SDValue N1Op2 = N1.getOperand(2);
3566 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3568 if (N1Op2C && N2C) {
3569 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3570 if (VT == N1.getOperand(1).getValueType())
3571 return N1.getOperand(1);
3573 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3576 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3580 case ISD::EXTRACT_ELEMENT:
3581 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3582 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3583 (N1.getValueType().isInteger() == VT.isInteger()) &&
3584 N1.getValueType() != VT &&
3585 "Wrong types for EXTRACT_ELEMENT!");
3587 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3588 // 64-bit integers into 32-bit parts. Instead of building the extract of
3589 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3590 if (N1.getOpcode() == ISD::BUILD_PAIR)
3591 return N1.getOperand(N2C->getZExtValue());
3593 // EXTRACT_ELEMENT of a constant int is also very common.
3594 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3595 unsigned ElementSize = VT.getSizeInBits();
3596 unsigned Shift = ElementSize * N2C->getZExtValue();
3597 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3598 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3601 case ISD::EXTRACT_SUBVECTOR: {
3603 if (VT.isSimple() && N1.getValueType().isSimple()) {
3604 assert(VT.isVector() && N1.getValueType().isVector() &&
3605 "Extract subvector VTs must be a vectors!");
3606 assert(VT.getVectorElementType() ==
3607 N1.getValueType().getVectorElementType() &&
3608 "Extract subvector VTs must have the same element type!");
3609 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3610 "Extract subvector must be from larger vector to smaller vector!");
3612 if (isa<ConstantSDNode>(Index.getNode())) {
3613 assert((VT.getVectorNumElements() +
3614 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3615 <= N1.getValueType().getVectorNumElements())
3616 && "Extract subvector overflow!");
3619 // Trivial extraction.
3620 if (VT.getSimpleVT() == N1.getSimpleValueType())
3627 // Perform trivial constant folding.
3629 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3632 // Canonicalize constant to RHS if commutative.
3633 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3634 std::swap(N1C, N2C);
3638 // Constant fold FP operations.
3639 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3640 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3641 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3643 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3644 // Canonicalize constant to RHS if commutative.
3645 std::swap(N1CFP, N2CFP);
3648 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3649 APFloat::opStatus s;
3652 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3653 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3654 return getConstantFP(V1, DL, VT);
3657 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3658 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3659 return getConstantFP(V1, DL, VT);
3662 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3663 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3664 return getConstantFP(V1, DL, VT);
3667 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3668 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3669 s!=APFloat::opDivByZero)) {
3670 return getConstantFP(V1, DL, VT);
3674 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3675 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3676 s!=APFloat::opDivByZero)) {
3677 return getConstantFP(V1, DL, VT);
3680 case ISD::FCOPYSIGN:
3682 return getConstantFP(V1, DL, VT);
3687 if (Opcode == ISD::FP_ROUND) {
3688 APFloat V = N1CFP->getValueAPF(); // make copy
3690 // This can return overflow, underflow, or inexact; we don't care.
3691 // FIXME need to be more flexible about rounding mode.
3692 (void)V.convert(EVTToAPFloatSemantics(VT),
3693 APFloat::rmNearestTiesToEven, &ignored);
3694 return getConstantFP(V, DL, VT);
3698 // Canonicalize an UNDEF to the RHS, even over a constant.
3699 if (N1.getOpcode() == ISD::UNDEF) {
3700 if (isCommutativeBinOp(Opcode)) {
3704 case ISD::FP_ROUND_INREG:
3705 case ISD::SIGN_EXTEND_INREG:
3711 return N1; // fold op(undef, arg2) -> undef
3719 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3720 // For vectors, we can't easily build an all zero vector, just return
3727 // Fold a bunch of operators when the RHS is undef.
3728 if (N2.getOpcode() == ISD::UNDEF) {
3731 if (N1.getOpcode() == ISD::UNDEF)
3732 // Handle undef ^ undef -> 0 special case. This is a common
3734 return getConstant(0, DL, VT);
3744 return N2; // fold op(arg1, undef) -> undef
3750 if (getTarget().Options.UnsafeFPMath)
3758 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3759 // For vectors, we can't easily build an all zero vector, just return
3764 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3765 // For vectors, we can't easily build an all one vector, just return
3773 // Memoize this node if possible.
3775 SDVTList VTs = getVTList(VT);
3776 if (VT != MVT::Glue) {
3777 SDValue Ops[] = {N1, N2};
3778 FoldingSetNodeID ID;
3779 AddNodeIDNode(ID, Opcode, VTs, Ops);
3780 AddNodeIDFlags(ID, Opcode, Flags);
3782 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3783 return SDValue(E, 0);
3785 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3787 CSEMap.InsertNode(N, IP);
3789 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3793 return SDValue(N, 0);
3796 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3797 SDValue N1, SDValue N2, SDValue N3) {
3798 // Perform various simplifications.
3799 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3802 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3803 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3804 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3805 if (N1CFP && N2CFP && N3CFP) {
3806 APFloat V1 = N1CFP->getValueAPF();
3807 const APFloat &V2 = N2CFP->getValueAPF();
3808 const APFloat &V3 = N3CFP->getValueAPF();
3809 APFloat::opStatus s =
3810 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3811 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3812 return getConstantFP(V1, DL, VT);
3816 case ISD::CONCAT_VECTORS:
3817 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3818 // one big BUILD_VECTOR.
3819 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3820 N2.getOpcode() == ISD::BUILD_VECTOR &&
3821 N3.getOpcode() == ISD::BUILD_VECTOR) {
3822 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3823 N1.getNode()->op_end());
3824 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3825 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3826 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3830 // Use FoldSetCC to simplify SETCC's.
3831 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3832 if (Simp.getNode()) return Simp;
3837 if (N1C->getZExtValue())
3838 return N2; // select true, X, Y -> X
3839 return N3; // select false, X, Y -> Y
3842 if (N2 == N3) return N2; // select C, X, X -> X
3844 case ISD::VECTOR_SHUFFLE:
3845 llvm_unreachable("should use getVectorShuffle constructor!");
3846 case ISD::INSERT_SUBVECTOR: {
3848 if (VT.isSimple() && N1.getValueType().isSimple()
3849 && N2.getValueType().isSimple()) {
3850 assert(VT.isVector() && N1.getValueType().isVector() &&
3851 N2.getValueType().isVector() &&
3852 "Insert subvector VTs must be a vectors");
3853 assert(VT == N1.getValueType() &&
3854 "Dest and insert subvector source types must match!");
3855 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3856 "Insert subvector must be from smaller vector to larger vector!");
3857 if (isa<ConstantSDNode>(Index.getNode())) {
3858 assert((N2.getValueType().getVectorNumElements() +
3859 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3860 <= VT.getVectorNumElements())
3861 && "Insert subvector overflow!");
3864 // Trivial insertion.
3865 if (VT.getSimpleVT() == N2.getSimpleValueType())
3871 // Fold bit_convert nodes from a type to themselves.
3872 if (N1.getValueType() == VT)
3877 // Memoize node if it doesn't produce a flag.
3879 SDVTList VTs = getVTList(VT);
3880 if (VT != MVT::Glue) {
3881 SDValue Ops[] = { N1, N2, N3 };
3882 FoldingSetNodeID ID;
3883 AddNodeIDNode(ID, Opcode, VTs, Ops);
3885 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3886 return SDValue(E, 0);
3888 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3889 DL.getDebugLoc(), VTs, N1, N2, N3);
3890 CSEMap.InsertNode(N, IP);
3892 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3893 DL.getDebugLoc(), VTs, N1, N2, N3);
3897 return SDValue(N, 0);
3900 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3901 SDValue N1, SDValue N2, SDValue N3,
3903 SDValue Ops[] = { N1, N2, N3, N4 };
3904 return getNode(Opcode, DL, VT, Ops);
3907 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3908 SDValue N1, SDValue N2, SDValue N3,
3909 SDValue N4, SDValue N5) {
3910 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3911 return getNode(Opcode, DL, VT, Ops);
3914 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3915 /// the incoming stack arguments to be loaded from the stack.
3916 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3917 SmallVector<SDValue, 8> ArgChains;
3919 // Include the original chain at the beginning of the list. When this is
3920 // used by target LowerCall hooks, this helps legalize find the
3921 // CALLSEQ_BEGIN node.
3922 ArgChains.push_back(Chain);
3924 // Add a chain value for each stack argument.
3925 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3926 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3927 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3928 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3929 if (FI->getIndex() < 0)
3930 ArgChains.push_back(SDValue(L, 1));
3932 // Build a tokenfactor for all the chains.
3933 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3936 /// getMemsetValue - Vectorized representation of the memset value
3938 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3940 assert(Value.getOpcode() != ISD::UNDEF);
3942 unsigned NumBits = VT.getScalarType().getSizeInBits();
3943 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3944 assert(C->getAPIntValue().getBitWidth() == 8);
3945 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3947 return DAG.getConstant(Val, dl, VT);
3948 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3952 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3953 EVT IntVT = VT.getScalarType();
3954 if (!IntVT.isInteger())
3955 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3957 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3959 // Use a multiplication with 0x010101... to extend the input to the
3961 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3962 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3963 DAG.getConstant(Magic, dl, IntVT));
3966 if (VT != Value.getValueType() && !VT.isInteger())
3967 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3968 if (VT != Value.getValueType()) {
3969 assert(VT.getVectorElementType() == Value.getValueType() &&
3970 "value type should be one vector element here");
3971 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3972 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3978 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3979 /// used when a memcpy is turned into a memset when the source is a constant
3981 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3982 const TargetLowering &TLI, StringRef Str) {
3983 // Handle vector with all elements zero.
3986 return DAG.getConstant(0, dl, VT);
3987 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3988 return DAG.getConstantFP(0.0, dl, VT);
3989 else if (VT.isVector()) {
3990 unsigned NumElts = VT.getVectorNumElements();
3991 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3992 return DAG.getNode(ISD::BITCAST, dl, VT,
3993 DAG.getConstant(0, dl,
3994 EVT::getVectorVT(*DAG.getContext(),
3997 llvm_unreachable("Expected type!");
4000 assert(!VT.isVector() && "Can't handle vector type here!");
4001 unsigned NumVTBits = VT.getSizeInBits();
4002 unsigned NumVTBytes = NumVTBits / 8;
4003 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4005 APInt Val(NumVTBits, 0);
4006 if (DAG.getDataLayout().isLittleEndian()) {
4007 for (unsigned i = 0; i != NumBytes; ++i)
4008 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4010 for (unsigned i = 0; i != NumBytes; ++i)
4011 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4014 // If the "cost" of materializing the integer immediate is less than the cost
4015 // of a load, then it is cost effective to turn the load into the immediate.
4016 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4017 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4018 return DAG.getConstant(Val, dl, VT);
4019 return SDValue(nullptr, 0);
4022 /// getMemBasePlusOffset - Returns base and offset node for the
4024 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4025 SelectionDAG &DAG) {
4026 EVT VT = Base.getValueType();
4027 return DAG.getNode(ISD::ADD, dl,
4028 VT, Base, DAG.getConstant(Offset, dl, VT));
4031 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4033 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4034 unsigned SrcDelta = 0;
4035 GlobalAddressSDNode *G = nullptr;
4036 if (Src.getOpcode() == ISD::GlobalAddress)
4037 G = cast<GlobalAddressSDNode>(Src);
4038 else if (Src.getOpcode() == ISD::ADD &&
4039 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4040 Src.getOperand(1).getOpcode() == ISD::Constant) {
4041 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4042 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4047 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4050 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4051 /// Return true if the number of memory ops is below the threshold (Limit).
4052 /// It returns the types of the sequence of memory ops to perform
4053 /// memset / memcpy by reference.
4054 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4055 unsigned Limit, uint64_t Size,
4056 unsigned DstAlign, unsigned SrcAlign,
4062 const TargetLowering &TLI) {
4063 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4064 "Expecting memcpy / memset source to meet alignment requirement!");
4065 // If 'SrcAlign' is zero, that means the memory operation does not need to
4066 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4067 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4068 // is the specified alignment of the memory operation. If it is zero, that
4069 // means it's possible to change the alignment of the destination.
4070 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4071 // not need to be loaded.
4072 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4073 IsMemset, ZeroMemset, MemcpyStrSrc,
4074 DAG.getMachineFunction());
4076 if (VT == MVT::Other) {
4078 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4079 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4080 VT = TLI.getPointerTy(DAG.getDataLayout());
4082 switch (DstAlign & 7) {
4083 case 0: VT = MVT::i64; break;
4084 case 4: VT = MVT::i32; break;
4085 case 2: VT = MVT::i16; break;
4086 default: VT = MVT::i8; break;
4091 while (!TLI.isTypeLegal(LVT))
4092 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4093 assert(LVT.isInteger());
4099 unsigned NumMemOps = 0;
4101 unsigned VTSize = VT.getSizeInBits() / 8;
4102 while (VTSize > Size) {
4103 // For now, only use non-vector load / store's for the left-over pieces.
4108 if (VT.isVector() || VT.isFloatingPoint()) {
4109 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4110 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4111 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4113 else if (NewVT == MVT::i64 &&
4114 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4115 TLI.isSafeMemOpType(MVT::f64)) {
4116 // i64 is usually not legal on 32-bit targets, but f64 may be.
4124 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4125 if (NewVT == MVT::i8)
4127 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4129 NewVTSize = NewVT.getSizeInBits() / 8;
4131 // If the new VT cannot cover all of the remaining bits, then consider
4132 // issuing a (or a pair of) unaligned and overlapping load / store.
4133 // FIXME: Only does this for 64-bit or more since we don't have proper
4134 // cost model for unaligned load / store.
4137 if (NumMemOps && AllowOverlap &&
4138 VTSize >= 8 && NewVTSize < Size &&
4139 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4147 if (++NumMemOps > Limit)
4150 MemOps.push_back(VT);
4157 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4158 SDValue Chain, SDValue Dst,
4159 SDValue Src, uint64_t Size,
4160 unsigned Align, bool isVol,
4162 MachinePointerInfo DstPtrInfo,
4163 MachinePointerInfo SrcPtrInfo) {
4164 // Turn a memcpy of undef to nop.
4165 if (Src.getOpcode() == ISD::UNDEF)
4168 // Expand memcpy to a series of load and store ops if the size operand falls
4169 // below a certain threshold.
4170 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4171 // rather than maybe a humongous number of loads and stores.
4172 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4173 std::vector<EVT> MemOps;
4174 bool DstAlignCanChange = false;
4175 MachineFunction &MF = DAG.getMachineFunction();
4176 MachineFrameInfo *MFI = MF.getFrameInfo();
4177 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4178 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4179 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4180 DstAlignCanChange = true;
4181 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4182 if (Align > SrcAlign)
4185 bool CopyFromStr = isMemSrcFromString(Src, Str);
4186 bool isZeroStr = CopyFromStr && Str.empty();
4187 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4189 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4190 (DstAlignCanChange ? 0 : Align),
4191 (isZeroStr ? 0 : SrcAlign),
4192 false, false, CopyFromStr, true, DAG, TLI))
4195 if (DstAlignCanChange) {
4196 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4197 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4199 // Don't promote to an alignment that would require dynamic stack
4201 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4202 if (!TRI->needsStackRealignment(MF))
4203 while (NewAlign > Align &&
4204 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4207 if (NewAlign > Align) {
4208 // Give the stack frame object a larger alignment if needed.
4209 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4210 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4215 SmallVector<SDValue, 8> OutChains;
4216 unsigned NumMemOps = MemOps.size();
4217 uint64_t SrcOff = 0, DstOff = 0;
4218 for (unsigned i = 0; i != NumMemOps; ++i) {
4220 unsigned VTSize = VT.getSizeInBits() / 8;
4221 SDValue Value, Store;
4223 if (VTSize > Size) {
4224 // Issuing an unaligned load / store pair that overlaps with the previous
4225 // pair. Adjust the offset accordingly.
4226 assert(i == NumMemOps-1 && i != 0);
4227 SrcOff -= VTSize - Size;
4228 DstOff -= VTSize - Size;
4232 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4233 // It's unlikely a store of a vector immediate can be done in a single
4234 // instruction. It would require a load from a constantpool first.
4235 // We only handle zero vectors here.
4236 // FIXME: Handle other cases where store of vector immediate is done in
4237 // a single instruction.
4238 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4239 if (Value.getNode())
4240 Store = DAG.getStore(Chain, dl, Value,
4241 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4242 DstPtrInfo.getWithOffset(DstOff), isVol,
4246 if (!Store.getNode()) {
4247 // The type might not be legal for the target. This should only happen
4248 // if the type is smaller than a legal type, as on PPC, so the right
4249 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4250 // to Load/Store if NVT==VT.
4251 // FIXME does the case above also need this?
4252 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4253 assert(NVT.bitsGE(VT));
4254 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4255 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4256 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4257 false, MinAlign(SrcAlign, SrcOff));
4258 Store = DAG.getTruncStore(Chain, dl, Value,
4259 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4260 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4263 OutChains.push_back(Store);
4269 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4272 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4273 SDValue Chain, SDValue Dst,
4274 SDValue Src, uint64_t Size,
4275 unsigned Align, bool isVol,
4277 MachinePointerInfo DstPtrInfo,
4278 MachinePointerInfo SrcPtrInfo) {
4279 // Turn a memmove of undef to nop.
4280 if (Src.getOpcode() == ISD::UNDEF)
4283 // Expand memmove to a series of load and store ops if the size operand falls
4284 // below a certain threshold.
4285 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4286 std::vector<EVT> MemOps;
4287 bool DstAlignCanChange = false;
4288 MachineFunction &MF = DAG.getMachineFunction();
4289 MachineFrameInfo *MFI = MF.getFrameInfo();
4290 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4291 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4292 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4293 DstAlignCanChange = true;
4294 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4295 if (Align > SrcAlign)
4297 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4299 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4300 (DstAlignCanChange ? 0 : Align), SrcAlign,
4301 false, false, false, false, DAG, TLI))
4304 if (DstAlignCanChange) {
4305 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4306 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4307 if (NewAlign > Align) {
4308 // Give the stack frame object a larger alignment if needed.
4309 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4310 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4315 uint64_t SrcOff = 0, DstOff = 0;
4316 SmallVector<SDValue, 8> LoadValues;
4317 SmallVector<SDValue, 8> LoadChains;
4318 SmallVector<SDValue, 8> OutChains;
4319 unsigned NumMemOps = MemOps.size();
4320 for (unsigned i = 0; i < NumMemOps; i++) {
4322 unsigned VTSize = VT.getSizeInBits() / 8;
4325 Value = DAG.getLoad(VT, dl, Chain,
4326 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4327 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4328 false, false, SrcAlign);
4329 LoadValues.push_back(Value);
4330 LoadChains.push_back(Value.getValue(1));
4333 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4335 for (unsigned i = 0; i < NumMemOps; i++) {
4337 unsigned VTSize = VT.getSizeInBits() / 8;
4340 Store = DAG.getStore(Chain, dl, LoadValues[i],
4341 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4342 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4343 OutChains.push_back(Store);
4347 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4350 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4353 /// \param DAG Selection DAG where lowered code is placed.
4354 /// \param dl Link to corresponding IR location.
4355 /// \param Chain Control flow dependency.
4356 /// \param Dst Pointer to destination memory location.
4357 /// \param Src Value of byte to write into the memory.
4358 /// \param Size Number of bytes to write.
4359 /// \param Align Alignment of the destination in bytes.
4360 /// \param isVol True if destination is volatile.
4361 /// \param DstPtrInfo IR information on the memory pointer.
4362 /// \returns New head in the control flow, if lowering was successful, empty
4363 /// SDValue otherwise.
4365 /// The function tries to replace 'llvm.memset' intrinsic with several store
4366 /// operations and value calculation code. This is usually profitable for small
4368 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4369 SDValue Chain, SDValue Dst,
4370 SDValue Src, uint64_t Size,
4371 unsigned Align, bool isVol,
4372 MachinePointerInfo DstPtrInfo) {
4373 // Turn a memset of undef to nop.
4374 if (Src.getOpcode() == ISD::UNDEF)
4377 // Expand memset to a series of load/store ops if the size operand
4378 // falls below a certain threshold.
4379 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4380 std::vector<EVT> MemOps;
4381 bool DstAlignCanChange = false;
4382 MachineFunction &MF = DAG.getMachineFunction();
4383 MachineFrameInfo *MFI = MF.getFrameInfo();
4384 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4385 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4386 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4387 DstAlignCanChange = true;
4389 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4390 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4391 Size, (DstAlignCanChange ? 0 : Align), 0,
4392 true, IsZeroVal, false, true, DAG, TLI))
4395 if (DstAlignCanChange) {
4396 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4397 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4398 if (NewAlign > Align) {
4399 // Give the stack frame object a larger alignment if needed.
4400 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4401 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4406 SmallVector<SDValue, 8> OutChains;
4407 uint64_t DstOff = 0;
4408 unsigned NumMemOps = MemOps.size();
4410 // Find the largest store and generate the bit pattern for it.
4411 EVT LargestVT = MemOps[0];
4412 for (unsigned i = 1; i < NumMemOps; i++)
4413 if (MemOps[i].bitsGT(LargestVT))
4414 LargestVT = MemOps[i];
4415 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4417 for (unsigned i = 0; i < NumMemOps; i++) {
4419 unsigned VTSize = VT.getSizeInBits() / 8;
4420 if (VTSize > Size) {
4421 // Issuing an unaligned load / store pair that overlaps with the previous
4422 // pair. Adjust the offset accordingly.
4423 assert(i == NumMemOps-1 && i != 0);
4424 DstOff -= VTSize - Size;
4427 // If this store is smaller than the largest store see whether we can get
4428 // the smaller value for free with a truncate.
4429 SDValue Value = MemSetValue;
4430 if (VT.bitsLT(LargestVT)) {
4431 if (!LargestVT.isVector() && !VT.isVector() &&
4432 TLI.isTruncateFree(LargestVT, VT))
4433 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4435 Value = getMemsetValue(Src, VT, DAG, dl);
4437 assert(Value.getValueType() == VT && "Value with wrong type.");
4438 SDValue Store = DAG.getStore(Chain, dl, Value,
4439 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4440 DstPtrInfo.getWithOffset(DstOff),
4441 isVol, false, Align);
4442 OutChains.push_back(Store);
4443 DstOff += VT.getSizeInBits() / 8;
4447 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4450 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4451 SDValue Src, SDValue Size,
4452 unsigned Align, bool isVol, bool AlwaysInline,
4453 bool isTailCall, MachinePointerInfo DstPtrInfo,
4454 MachinePointerInfo SrcPtrInfo) {
4455 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4457 // Check to see if we should lower the memcpy to loads and stores first.
4458 // For cases within the target-specified limits, this is the best choice.
4459 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4461 // Memcpy with size zero? Just return the original chain.
4462 if (ConstantSize->isNullValue())
4465 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4466 ConstantSize->getZExtValue(),Align,
4467 isVol, false, DstPtrInfo, SrcPtrInfo);
4468 if (Result.getNode())
4472 // Then check to see if we should lower the memcpy with target-specific
4473 // code. If the target chooses to do this, this is the next best.
4475 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4476 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4477 DstPtrInfo, SrcPtrInfo);
4478 if (Result.getNode())
4482 // If we really need inline code and the target declined to provide it,
4483 // use a (potentially long) sequence of loads and stores.
4485 assert(ConstantSize && "AlwaysInline requires a constant size!");
4486 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4487 ConstantSize->getZExtValue(), Align, isVol,
4488 true, DstPtrInfo, SrcPtrInfo);
4491 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4492 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4493 // respect volatile, so they may do things like read or write memory
4494 // beyond the given memory regions. But fixing this isn't easy, and most
4495 // people don't care.
4497 // Emit a library call.
4498 TargetLowering::ArgListTy Args;
4499 TargetLowering::ArgListEntry Entry;
4500 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4501 Entry.Node = Dst; Args.push_back(Entry);
4502 Entry.Node = Src; Args.push_back(Entry);
4503 Entry.Node = Size; Args.push_back(Entry);
4504 // FIXME: pass in SDLoc
4505 TargetLowering::CallLoweringInfo CLI(*this);
4508 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4509 Type::getVoidTy(*getContext()),
4510 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4511 TLI->getPointerTy(getDataLayout())),
4514 .setTailCall(isTailCall);
4516 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4517 return CallResult.second;
4520 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4521 SDValue Src, SDValue Size,
4522 unsigned Align, bool isVol, bool isTailCall,
4523 MachinePointerInfo DstPtrInfo,
4524 MachinePointerInfo SrcPtrInfo) {
4525 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4527 // Check to see if we should lower the memmove to loads and stores first.
4528 // For cases within the target-specified limits, this is the best choice.
4529 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4531 // Memmove with size zero? Just return the original chain.
4532 if (ConstantSize->isNullValue())
4536 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4537 ConstantSize->getZExtValue(), Align, isVol,
4538 false, DstPtrInfo, SrcPtrInfo);
4539 if (Result.getNode())
4543 // Then check to see if we should lower the memmove with target-specific
4544 // code. If the target chooses to do this, this is the next best.
4546 SDValue Result = TSI->EmitTargetCodeForMemmove(
4547 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4548 if (Result.getNode())
4552 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4553 // not be safe. See memcpy above for more details.
4555 // Emit a library call.
4556 TargetLowering::ArgListTy Args;
4557 TargetLowering::ArgListEntry Entry;
4558 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4559 Entry.Node = Dst; Args.push_back(Entry);
4560 Entry.Node = Src; Args.push_back(Entry);
4561 Entry.Node = Size; Args.push_back(Entry);
4562 // FIXME: pass in SDLoc
4563 TargetLowering::CallLoweringInfo CLI(*this);
4566 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4567 Type::getVoidTy(*getContext()),
4568 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4569 TLI->getPointerTy(getDataLayout())),
4572 .setTailCall(isTailCall);
4574 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4575 return CallResult.second;
4578 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4579 SDValue Src, SDValue Size,
4580 unsigned Align, bool isVol, bool isTailCall,
4581 MachinePointerInfo DstPtrInfo) {
4582 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4584 // Check to see if we should lower the memset to stores first.
4585 // For cases within the target-specified limits, this is the best choice.
4586 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4588 // Memset with size zero? Just return the original chain.
4589 if (ConstantSize->isNullValue())
4593 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4594 Align, isVol, DstPtrInfo);
4596 if (Result.getNode())
4600 // Then check to see if we should lower the memset with target-specific
4601 // code. If the target chooses to do this, this is the next best.
4603 SDValue Result = TSI->EmitTargetCodeForMemset(
4604 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4605 if (Result.getNode())
4609 // Emit a library call.
4610 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4611 TargetLowering::ArgListTy Args;
4612 TargetLowering::ArgListEntry Entry;
4613 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4614 Args.push_back(Entry);
4616 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4617 Args.push_back(Entry);
4619 Entry.Ty = IntPtrTy;
4620 Args.push_back(Entry);
4622 // FIXME: pass in SDLoc
4623 TargetLowering::CallLoweringInfo CLI(*this);
4626 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4627 Type::getVoidTy(*getContext()),
4628 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4629 TLI->getPointerTy(getDataLayout())),
4632 .setTailCall(isTailCall);
4634 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4635 return CallResult.second;
4638 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4639 SDVTList VTList, ArrayRef<SDValue> Ops,
4640 MachineMemOperand *MMO,
4641 AtomicOrdering SuccessOrdering,
4642 AtomicOrdering FailureOrdering,
4643 SynchronizationScope SynchScope) {
4644 FoldingSetNodeID ID;
4645 ID.AddInteger(MemVT.getRawBits());
4646 AddNodeIDNode(ID, Opcode, VTList, Ops);
4647 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4649 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4650 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4651 return SDValue(E, 0);
4654 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4655 // SDNode doesn't have access to it. This memory will be "leaked" when
4656 // the node is deallocated, but recovered when the allocator is released.
4657 // If the number of operands is less than 5 we use AtomicSDNode's internal
4659 unsigned NumOps = Ops.size();
4660 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4663 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4664 dl.getDebugLoc(), VTList, MemVT,
4665 Ops.data(), DynOps, NumOps, MMO,
4666 SuccessOrdering, FailureOrdering,
4668 CSEMap.InsertNode(N, IP);
4670 return SDValue(N, 0);
4673 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4674 SDVTList VTList, ArrayRef<SDValue> Ops,
4675 MachineMemOperand *MMO,
4676 AtomicOrdering Ordering,
4677 SynchronizationScope SynchScope) {
4678 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4679 Ordering, SynchScope);
4682 SDValue SelectionDAG::getAtomicCmpSwap(
4683 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4684 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4685 unsigned Alignment, AtomicOrdering SuccessOrdering,
4686 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4687 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4688 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4689 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4691 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4692 Alignment = getEVTAlignment(MemVT);
4694 MachineFunction &MF = getMachineFunction();
4696 // FIXME: Volatile isn't really correct; we should keep track of atomic
4697 // orderings in the memoperand.
4698 unsigned Flags = MachineMemOperand::MOVolatile;
4699 Flags |= MachineMemOperand::MOLoad;
4700 Flags |= MachineMemOperand::MOStore;
4702 MachineMemOperand *MMO =
4703 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4705 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4706 SuccessOrdering, FailureOrdering, SynchScope);
4709 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4710 SDVTList VTs, SDValue Chain, SDValue Ptr,
4711 SDValue Cmp, SDValue Swp,
4712 MachineMemOperand *MMO,
4713 AtomicOrdering SuccessOrdering,
4714 AtomicOrdering FailureOrdering,
4715 SynchronizationScope SynchScope) {
4716 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4717 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4718 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4720 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4721 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4722 SuccessOrdering, FailureOrdering, SynchScope);
4725 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4727 SDValue Ptr, SDValue Val,
4728 const Value* PtrVal,
4730 AtomicOrdering Ordering,
4731 SynchronizationScope SynchScope) {
4732 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4733 Alignment = getEVTAlignment(MemVT);
4735 MachineFunction &MF = getMachineFunction();
4736 // An atomic store does not load. An atomic load does not store.
4737 // (An atomicrmw obviously both loads and stores.)
4738 // For now, atomics are considered to be volatile always, and they are
4740 // FIXME: Volatile isn't really correct; we should keep track of atomic
4741 // orderings in the memoperand.
4742 unsigned Flags = MachineMemOperand::MOVolatile;
4743 if (Opcode != ISD::ATOMIC_STORE)
4744 Flags |= MachineMemOperand::MOLoad;
4745 if (Opcode != ISD::ATOMIC_LOAD)
4746 Flags |= MachineMemOperand::MOStore;
4748 MachineMemOperand *MMO =
4749 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4750 MemVT.getStoreSize(), Alignment);
4752 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4753 Ordering, SynchScope);
4756 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4758 SDValue Ptr, SDValue Val,
4759 MachineMemOperand *MMO,
4760 AtomicOrdering Ordering,
4761 SynchronizationScope SynchScope) {
4762 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4763 Opcode == ISD::ATOMIC_LOAD_SUB ||
4764 Opcode == ISD::ATOMIC_LOAD_AND ||
4765 Opcode == ISD::ATOMIC_LOAD_OR ||
4766 Opcode == ISD::ATOMIC_LOAD_XOR ||
4767 Opcode == ISD::ATOMIC_LOAD_NAND ||
4768 Opcode == ISD::ATOMIC_LOAD_MIN ||
4769 Opcode == ISD::ATOMIC_LOAD_MAX ||
4770 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4771 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4772 Opcode == ISD::ATOMIC_SWAP ||
4773 Opcode == ISD::ATOMIC_STORE) &&
4774 "Invalid Atomic Op");
4776 EVT VT = Val.getValueType();
4778 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4779 getVTList(VT, MVT::Other);
4780 SDValue Ops[] = {Chain, Ptr, Val};
4781 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4784 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4785 EVT VT, SDValue Chain,
4787 MachineMemOperand *MMO,
4788 AtomicOrdering Ordering,
4789 SynchronizationScope SynchScope) {
4790 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4792 SDVTList VTs = getVTList(VT, MVT::Other);
4793 SDValue Ops[] = {Chain, Ptr};
4794 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4797 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4798 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4799 if (Ops.size() == 1)
4802 SmallVector<EVT, 4> VTs;
4803 VTs.reserve(Ops.size());
4804 for (unsigned i = 0; i < Ops.size(); ++i)
4805 VTs.push_back(Ops[i].getValueType());
4806 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4810 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4811 ArrayRef<SDValue> Ops,
4812 EVT MemVT, MachinePointerInfo PtrInfo,
4813 unsigned Align, bool Vol,
4814 bool ReadMem, bool WriteMem, unsigned Size) {
4815 if (Align == 0) // Ensure that codegen never sees alignment 0
4816 Align = getEVTAlignment(MemVT);
4818 MachineFunction &MF = getMachineFunction();
4821 Flags |= MachineMemOperand::MOStore;
4823 Flags |= MachineMemOperand::MOLoad;
4825 Flags |= MachineMemOperand::MOVolatile;
4827 Size = MemVT.getStoreSize();
4828 MachineMemOperand *MMO =
4829 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4831 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4835 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4836 ArrayRef<SDValue> Ops, EVT MemVT,
4837 MachineMemOperand *MMO) {
4838 assert((Opcode == ISD::INTRINSIC_VOID ||
4839 Opcode == ISD::INTRINSIC_W_CHAIN ||
4840 Opcode == ISD::PREFETCH ||
4841 Opcode == ISD::LIFETIME_START ||
4842 Opcode == ISD::LIFETIME_END ||
4843 (Opcode <= INT_MAX &&
4844 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4845 "Opcode is not a memory-accessing opcode!");
4847 // Memoize the node unless it returns a flag.
4848 MemIntrinsicSDNode *N;
4849 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4850 FoldingSetNodeID ID;
4851 AddNodeIDNode(ID, Opcode, VTList, Ops);
4852 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4854 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4855 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4856 return SDValue(E, 0);
4859 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4860 dl.getDebugLoc(), VTList, Ops,
4862 CSEMap.InsertNode(N, IP);
4864 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4865 dl.getDebugLoc(), VTList, Ops,
4869 return SDValue(N, 0);
4872 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4873 /// MachinePointerInfo record from it. This is particularly useful because the
4874 /// code generator has many cases where it doesn't bother passing in a
4875 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4876 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4877 // If this is FI+Offset, we can model it.
4878 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4879 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4881 // If this is (FI+Offset1)+Offset2, we can model it.
4882 if (Ptr.getOpcode() != ISD::ADD ||
4883 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4884 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4885 return MachinePointerInfo();
4887 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4888 return MachinePointerInfo::getFixedStack(FI, Offset+
4889 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4892 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4893 /// MachinePointerInfo record from it. This is particularly useful because the
4894 /// code generator has many cases where it doesn't bother passing in a
4895 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4896 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4897 // If the 'Offset' value isn't a constant, we can't handle this.
4898 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4899 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4900 if (OffsetOp.getOpcode() == ISD::UNDEF)
4901 return InferPointerInfo(Ptr);
4902 return MachinePointerInfo();
4907 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4908 EVT VT, SDLoc dl, SDValue Chain,
4909 SDValue Ptr, SDValue Offset,
4910 MachinePointerInfo PtrInfo, EVT MemVT,
4911 bool isVolatile, bool isNonTemporal, bool isInvariant,
4912 unsigned Alignment, const AAMDNodes &AAInfo,
4913 const MDNode *Ranges) {
4914 assert(Chain.getValueType() == MVT::Other &&
4915 "Invalid chain type");
4916 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4917 Alignment = getEVTAlignment(VT);
4919 unsigned Flags = MachineMemOperand::MOLoad;
4921 Flags |= MachineMemOperand::MOVolatile;
4923 Flags |= MachineMemOperand::MONonTemporal;
4925 Flags |= MachineMemOperand::MOInvariant;
4927 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4929 if (PtrInfo.V.isNull())
4930 PtrInfo = InferPointerInfo(Ptr, Offset);
4932 MachineFunction &MF = getMachineFunction();
4933 MachineMemOperand *MMO =
4934 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4936 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4940 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4941 EVT VT, SDLoc dl, SDValue Chain,
4942 SDValue Ptr, SDValue Offset, EVT MemVT,
4943 MachineMemOperand *MMO) {
4945 ExtType = ISD::NON_EXTLOAD;
4946 } else if (ExtType == ISD::NON_EXTLOAD) {
4947 assert(VT == MemVT && "Non-extending load from different memory type!");
4950 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4951 "Should only be an extending load, not truncating!");
4952 assert(VT.isInteger() == MemVT.isInteger() &&
4953 "Cannot convert from FP to Int or Int -> FP!");
4954 assert(VT.isVector() == MemVT.isVector() &&
4955 "Cannot use an ext load to convert to or from a vector!");
4956 assert((!VT.isVector() ||
4957 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4958 "Cannot use an ext load to change the number of vector elements!");
4961 bool Indexed = AM != ISD::UNINDEXED;
4962 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4963 "Unindexed load with an offset!");
4965 SDVTList VTs = Indexed ?
4966 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4967 SDValue Ops[] = { Chain, Ptr, Offset };
4968 FoldingSetNodeID ID;
4969 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4970 ID.AddInteger(MemVT.getRawBits());
4971 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4972 MMO->isNonTemporal(),
4973 MMO->isInvariant()));
4974 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4976 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4977 cast<LoadSDNode>(E)->refineAlignment(MMO);
4978 return SDValue(E, 0);
4980 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4981 dl.getDebugLoc(), VTs, AM, ExtType,
4983 CSEMap.InsertNode(N, IP);
4985 return SDValue(N, 0);
4988 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4989 SDValue Chain, SDValue Ptr,
4990 MachinePointerInfo PtrInfo,
4991 bool isVolatile, bool isNonTemporal,
4992 bool isInvariant, unsigned Alignment,
4993 const AAMDNodes &AAInfo,
4994 const MDNode *Ranges) {
4995 SDValue Undef = getUNDEF(Ptr.getValueType());
4996 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4997 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5001 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5002 SDValue Chain, SDValue Ptr,
5003 MachineMemOperand *MMO) {
5004 SDValue Undef = getUNDEF(Ptr.getValueType());
5005 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5009 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5010 SDValue Chain, SDValue Ptr,
5011 MachinePointerInfo PtrInfo, EVT MemVT,
5012 bool isVolatile, bool isNonTemporal,
5013 bool isInvariant, unsigned Alignment,
5014 const AAMDNodes &AAInfo) {
5015 SDValue Undef = getUNDEF(Ptr.getValueType());
5016 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5017 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5022 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5023 SDValue Chain, SDValue Ptr, EVT MemVT,
5024 MachineMemOperand *MMO) {
5025 SDValue Undef = getUNDEF(Ptr.getValueType());
5026 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5031 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5032 SDValue Offset, ISD::MemIndexedMode AM) {
5033 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5034 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5035 "Load is already a indexed load!");
5036 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5037 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5038 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5039 false, LD->getAlignment());
5042 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5043 SDValue Ptr, MachinePointerInfo PtrInfo,
5044 bool isVolatile, bool isNonTemporal,
5045 unsigned Alignment, const AAMDNodes &AAInfo) {
5046 assert(Chain.getValueType() == MVT::Other &&
5047 "Invalid chain type");
5048 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5049 Alignment = getEVTAlignment(Val.getValueType());
5051 unsigned Flags = MachineMemOperand::MOStore;
5053 Flags |= MachineMemOperand::MOVolatile;
5055 Flags |= MachineMemOperand::MONonTemporal;
5057 if (PtrInfo.V.isNull())
5058 PtrInfo = InferPointerInfo(Ptr);
5060 MachineFunction &MF = getMachineFunction();
5061 MachineMemOperand *MMO =
5062 MF.getMachineMemOperand(PtrInfo, Flags,
5063 Val.getValueType().getStoreSize(), Alignment,
5066 return getStore(Chain, dl, Val, Ptr, MMO);
5069 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5070 SDValue Ptr, MachineMemOperand *MMO) {
5071 assert(Chain.getValueType() == MVT::Other &&
5072 "Invalid chain type");
5073 EVT VT = Val.getValueType();
5074 SDVTList VTs = getVTList(MVT::Other);
5075 SDValue Undef = getUNDEF(Ptr.getValueType());
5076 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5077 FoldingSetNodeID ID;
5078 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5079 ID.AddInteger(VT.getRawBits());
5080 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5081 MMO->isNonTemporal(), MMO->isInvariant()));
5082 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5084 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5085 cast<StoreSDNode>(E)->refineAlignment(MMO);
5086 return SDValue(E, 0);
5088 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5089 dl.getDebugLoc(), VTs,
5090 ISD::UNINDEXED, false, VT, MMO);
5091 CSEMap.InsertNode(N, IP);
5093 return SDValue(N, 0);
5096 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5097 SDValue Ptr, MachinePointerInfo PtrInfo,
5098 EVT SVT,bool isVolatile, bool isNonTemporal,
5100 const AAMDNodes &AAInfo) {
5101 assert(Chain.getValueType() == MVT::Other &&
5102 "Invalid chain type");
5103 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5104 Alignment = getEVTAlignment(SVT);
5106 unsigned Flags = MachineMemOperand::MOStore;
5108 Flags |= MachineMemOperand::MOVolatile;
5110 Flags |= MachineMemOperand::MONonTemporal;
5112 if (PtrInfo.V.isNull())
5113 PtrInfo = InferPointerInfo(Ptr);
5115 MachineFunction &MF = getMachineFunction();
5116 MachineMemOperand *MMO =
5117 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5120 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5123 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5124 SDValue Ptr, EVT SVT,
5125 MachineMemOperand *MMO) {
5126 EVT VT = Val.getValueType();
5128 assert(Chain.getValueType() == MVT::Other &&
5129 "Invalid chain type");
5131 return getStore(Chain, dl, Val, Ptr, MMO);
5133 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5134 "Should only be a truncating store, not extending!");
5135 assert(VT.isInteger() == SVT.isInteger() &&
5136 "Can't do FP-INT conversion!");
5137 assert(VT.isVector() == SVT.isVector() &&
5138 "Cannot use trunc store to convert to or from a vector!");
5139 assert((!VT.isVector() ||
5140 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5141 "Cannot use trunc store to change the number of vector elements!");
5143 SDVTList VTs = getVTList(MVT::Other);
5144 SDValue Undef = getUNDEF(Ptr.getValueType());
5145 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5146 FoldingSetNodeID ID;
5147 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5148 ID.AddInteger(SVT.getRawBits());
5149 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5150 MMO->isNonTemporal(), MMO->isInvariant()));
5151 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5153 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5154 cast<StoreSDNode>(E)->refineAlignment(MMO);
5155 return SDValue(E, 0);
5157 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5158 dl.getDebugLoc(), VTs,
5159 ISD::UNINDEXED, true, SVT, MMO);
5160 CSEMap.InsertNode(N, IP);
5162 return SDValue(N, 0);
5166 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5167 SDValue Offset, ISD::MemIndexedMode AM) {
5168 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5169 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5170 "Store is already a indexed store!");
5171 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5172 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5173 FoldingSetNodeID ID;
5174 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5175 ID.AddInteger(ST->getMemoryVT().getRawBits());
5176 ID.AddInteger(ST->getRawSubclassData());
5177 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5179 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5180 return SDValue(E, 0);
5182 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5183 dl.getDebugLoc(), VTs, AM,
5184 ST->isTruncatingStore(),
5186 ST->getMemOperand());
5187 CSEMap.InsertNode(N, IP);
5189 return SDValue(N, 0);
5193 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5194 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5195 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5197 SDVTList VTs = getVTList(VT, MVT::Other);
5198 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5199 FoldingSetNodeID ID;
5200 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5201 ID.AddInteger(VT.getRawBits());
5202 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5204 MMO->isNonTemporal(),
5205 MMO->isInvariant()));
5206 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5208 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5209 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5210 return SDValue(E, 0);
5212 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5213 dl.getDebugLoc(), Ops, 4, VTs,
5215 CSEMap.InsertNode(N, IP);
5217 return SDValue(N, 0);
5220 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5221 SDValue Ptr, SDValue Mask, EVT MemVT,
5222 MachineMemOperand *MMO, bool isTrunc) {
5223 assert(Chain.getValueType() == MVT::Other &&
5224 "Invalid chain type");
5225 EVT VT = Val.getValueType();
5226 SDVTList VTs = getVTList(MVT::Other);
5227 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5228 FoldingSetNodeID ID;
5229 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5230 ID.AddInteger(VT.getRawBits());
5231 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5232 MMO->isNonTemporal(), MMO->isInvariant()));
5233 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5235 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5236 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5237 return SDValue(E, 0);
5239 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5240 dl.getDebugLoc(), Ops, 4,
5241 VTs, isTrunc, MemVT, MMO);
5242 CSEMap.InsertNode(N, IP);
5244 return SDValue(N, 0);
5248 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5249 ArrayRef<SDValue> Ops,
5250 MachineMemOperand *MMO) {
5252 FoldingSetNodeID ID;
5253 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5254 ID.AddInteger(VT.getRawBits());
5255 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5257 MMO->isNonTemporal(),
5258 MMO->isInvariant()));
5259 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5261 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5262 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5263 return SDValue(E, 0);
5265 MaskedGatherSDNode *N =
5266 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5268 CSEMap.InsertNode(N, IP);
5270 return SDValue(N, 0);
5273 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5274 ArrayRef<SDValue> Ops,
5275 MachineMemOperand *MMO) {
5276 FoldingSetNodeID ID;
5277 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5278 ID.AddInteger(VT.getRawBits());
5279 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5280 MMO->isNonTemporal(),
5281 MMO->isInvariant()));
5282 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5284 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5285 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5286 return SDValue(E, 0);
5289 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5291 CSEMap.InsertNode(N, IP);
5293 return SDValue(N, 0);
5296 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5297 SDValue Chain, SDValue Ptr,
5300 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5301 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5304 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5305 ArrayRef<SDUse> Ops) {
5306 switch (Ops.size()) {
5307 case 0: return getNode(Opcode, DL, VT);
5308 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5309 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5310 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5314 // Copy from an SDUse array into an SDValue array for use with
5315 // the regular getNode logic.
5316 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5317 return getNode(Opcode, DL, VT, NewOps);
5320 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5321 ArrayRef<SDValue> Ops) {
5322 unsigned NumOps = Ops.size();
5324 case 0: return getNode(Opcode, DL, VT);
5325 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5326 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5327 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5333 case ISD::SELECT_CC: {
5334 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5335 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5336 "LHS and RHS of condition must have same type!");
5337 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5338 "True and False arms of SelectCC must have same type!");
5339 assert(Ops[2].getValueType() == VT &&
5340 "select_cc node must be of same type as true and false value!");
5344 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5345 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5346 "LHS/RHS of comparison should match types!");
5353 SDVTList VTs = getVTList(VT);
5355 if (VT != MVT::Glue) {
5356 FoldingSetNodeID ID;
5357 AddNodeIDNode(ID, Opcode, VTs, Ops);
5360 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5361 return SDValue(E, 0);
5363 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5365 CSEMap.InsertNode(N, IP);
5367 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5372 return SDValue(N, 0);
5375 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5376 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5377 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5380 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5381 ArrayRef<SDValue> Ops) {
5382 if (VTList.NumVTs == 1)
5383 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5387 // FIXME: figure out how to safely handle things like
5388 // int foo(int x) { return 1 << (x & 255); }
5389 // int bar() { return foo(256); }
5390 case ISD::SRA_PARTS:
5391 case ISD::SRL_PARTS:
5392 case ISD::SHL_PARTS:
5393 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5394 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5395 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5396 else if (N3.getOpcode() == ISD::AND)
5397 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5398 // If the and is only masking out bits that cannot effect the shift,
5399 // eliminate the and.
5400 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5401 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5402 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5408 // Memoize the node unless it returns a flag.
5410 unsigned NumOps = Ops.size();
5411 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5412 FoldingSetNodeID ID;
5413 AddNodeIDNode(ID, Opcode, VTList, Ops);
5415 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5416 return SDValue(E, 0);
5419 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5420 DL.getDebugLoc(), VTList, Ops[0]);
5421 } else if (NumOps == 2) {
5422 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5423 DL.getDebugLoc(), VTList, Ops[0],
5425 } else if (NumOps == 3) {
5426 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5427 DL.getDebugLoc(), VTList, Ops[0],
5430 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5433 CSEMap.InsertNode(N, IP);
5436 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5437 DL.getDebugLoc(), VTList, Ops[0]);
5438 } else if (NumOps == 2) {
5439 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5440 DL.getDebugLoc(), VTList, Ops[0],
5442 } else if (NumOps == 3) {
5443 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5444 DL.getDebugLoc(), VTList, Ops[0],
5447 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5452 return SDValue(N, 0);
5455 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5456 return getNode(Opcode, DL, VTList, None);
5459 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5461 SDValue Ops[] = { N1 };
5462 return getNode(Opcode, DL, VTList, Ops);
5465 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5466 SDValue N1, SDValue N2) {
5467 SDValue Ops[] = { N1, N2 };
5468 return getNode(Opcode, DL, VTList, Ops);
5471 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5472 SDValue N1, SDValue N2, SDValue N3) {
5473 SDValue Ops[] = { N1, N2, N3 };
5474 return getNode(Opcode, DL, VTList, Ops);
5477 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5478 SDValue N1, SDValue N2, SDValue N3,
5480 SDValue Ops[] = { N1, N2, N3, N4 };
5481 return getNode(Opcode, DL, VTList, Ops);
5484 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5485 SDValue N1, SDValue N2, SDValue N3,
5486 SDValue N4, SDValue N5) {
5487 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5488 return getNode(Opcode, DL, VTList, Ops);
5491 SDVTList SelectionDAG::getVTList(EVT VT) {
5492 return makeVTList(SDNode::getValueTypeList(VT), 1);
5495 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5496 FoldingSetNodeID ID;
5498 ID.AddInteger(VT1.getRawBits());
5499 ID.AddInteger(VT2.getRawBits());
5502 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5504 EVT *Array = Allocator.Allocate<EVT>(2);
5507 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5508 VTListMap.InsertNode(Result, IP);
5510 return Result->getSDVTList();
5513 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5514 FoldingSetNodeID ID;
5516 ID.AddInteger(VT1.getRawBits());
5517 ID.AddInteger(VT2.getRawBits());
5518 ID.AddInteger(VT3.getRawBits());
5521 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5523 EVT *Array = Allocator.Allocate<EVT>(3);
5527 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5528 VTListMap.InsertNode(Result, IP);
5530 return Result->getSDVTList();
5533 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5534 FoldingSetNodeID ID;
5536 ID.AddInteger(VT1.getRawBits());
5537 ID.AddInteger(VT2.getRawBits());
5538 ID.AddInteger(VT3.getRawBits());
5539 ID.AddInteger(VT4.getRawBits());
5542 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5544 EVT *Array = Allocator.Allocate<EVT>(4);
5549 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5550 VTListMap.InsertNode(Result, IP);
5552 return Result->getSDVTList();
5555 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5556 unsigned NumVTs = VTs.size();
5557 FoldingSetNodeID ID;
5558 ID.AddInteger(NumVTs);
5559 for (unsigned index = 0; index < NumVTs; index++) {
5560 ID.AddInteger(VTs[index].getRawBits());
5564 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5566 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5567 std::copy(VTs.begin(), VTs.end(), Array);
5568 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5569 VTListMap.InsertNode(Result, IP);
5571 return Result->getSDVTList();
5575 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5576 /// specified operands. If the resultant node already exists in the DAG,
5577 /// this does not modify the specified node, instead it returns the node that
5578 /// already exists. If the resultant node does not exist in the DAG, the
5579 /// input node is returned. As a degenerate case, if you specify the same
5580 /// input operands as the node already has, the input node is returned.
5581 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5582 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5584 // Check to see if there is no change.
5585 if (Op == N->getOperand(0)) return N;
5587 // See if the modified node already exists.
5588 void *InsertPos = nullptr;
5589 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5592 // Nope it doesn't. Remove the node from its current place in the maps.
5594 if (!RemoveNodeFromCSEMaps(N))
5595 InsertPos = nullptr;
5597 // Now we update the operands.
5598 N->OperandList[0].set(Op);
5600 // If this gets put into a CSE map, add it.
5601 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5605 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5606 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5608 // Check to see if there is no change.
5609 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5610 return N; // No operands changed, just return the input node.
5612 // See if the modified node already exists.
5613 void *InsertPos = nullptr;
5614 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5617 // Nope it doesn't. Remove the node from its current place in the maps.
5619 if (!RemoveNodeFromCSEMaps(N))
5620 InsertPos = nullptr;
5622 // Now we update the operands.
5623 if (N->OperandList[0] != Op1)
5624 N->OperandList[0].set(Op1);
5625 if (N->OperandList[1] != Op2)
5626 N->OperandList[1].set(Op2);
5628 // If this gets put into a CSE map, add it.
5629 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5633 SDNode *SelectionDAG::
5634 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5635 SDValue Ops[] = { Op1, Op2, Op3 };
5636 return UpdateNodeOperands(N, Ops);
5639 SDNode *SelectionDAG::
5640 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5641 SDValue Op3, SDValue Op4) {
5642 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5643 return UpdateNodeOperands(N, Ops);
5646 SDNode *SelectionDAG::
5647 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5648 SDValue Op3, SDValue Op4, SDValue Op5) {
5649 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5650 return UpdateNodeOperands(N, Ops);
5653 SDNode *SelectionDAG::
5654 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5655 unsigned NumOps = Ops.size();
5656 assert(N->getNumOperands() == NumOps &&
5657 "Update with wrong number of operands");
5659 // If no operands changed just return the input node.
5660 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5663 // See if the modified node already exists.
5664 void *InsertPos = nullptr;
5665 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5668 // Nope it doesn't. Remove the node from its current place in the maps.
5670 if (!RemoveNodeFromCSEMaps(N))
5671 InsertPos = nullptr;
5673 // Now we update the operands.
5674 for (unsigned i = 0; i != NumOps; ++i)
5675 if (N->OperandList[i] != Ops[i])
5676 N->OperandList[i].set(Ops[i]);
5678 // If this gets put into a CSE map, add it.
5679 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5683 /// DropOperands - Release the operands and set this node to have
5685 void SDNode::DropOperands() {
5686 // Unlike the code in MorphNodeTo that does this, we don't need to
5687 // watch for dead nodes here.
5688 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5694 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5699 SDVTList VTs = getVTList(VT);
5700 return SelectNodeTo(N, MachineOpc, VTs, None);
5703 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5704 EVT VT, SDValue Op1) {
5705 SDVTList VTs = getVTList(VT);
5706 SDValue Ops[] = { Op1 };
5707 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5710 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5711 EVT VT, SDValue Op1,
5713 SDVTList VTs = getVTList(VT);
5714 SDValue Ops[] = { Op1, Op2 };
5715 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5718 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5719 EVT VT, SDValue Op1,
5720 SDValue Op2, SDValue Op3) {
5721 SDVTList VTs = getVTList(VT);
5722 SDValue Ops[] = { Op1, Op2, Op3 };
5723 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5726 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5727 EVT VT, ArrayRef<SDValue> Ops) {
5728 SDVTList VTs = getVTList(VT);
5729 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5732 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5733 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5734 SDVTList VTs = getVTList(VT1, VT2);
5735 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5738 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5740 SDVTList VTs = getVTList(VT1, VT2);
5741 return SelectNodeTo(N, MachineOpc, VTs, None);
5744 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5745 EVT VT1, EVT VT2, EVT VT3,
5746 ArrayRef<SDValue> Ops) {
5747 SDVTList VTs = getVTList(VT1, VT2, VT3);
5748 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5751 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5752 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5753 ArrayRef<SDValue> Ops) {
5754 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5755 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5758 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5761 SDVTList VTs = getVTList(VT1, VT2);
5762 SDValue Ops[] = { Op1 };
5763 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5766 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5768 SDValue Op1, SDValue Op2) {
5769 SDVTList VTs = getVTList(VT1, VT2);
5770 SDValue Ops[] = { Op1, Op2 };
5771 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5774 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5776 SDValue Op1, SDValue Op2,
5778 SDVTList VTs = getVTList(VT1, VT2);
5779 SDValue Ops[] = { Op1, Op2, Op3 };
5780 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5783 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5784 EVT VT1, EVT VT2, EVT VT3,
5785 SDValue Op1, SDValue Op2,
5787 SDVTList VTs = getVTList(VT1, VT2, VT3);
5788 SDValue Ops[] = { Op1, Op2, Op3 };
5789 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5792 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5793 SDVTList VTs,ArrayRef<SDValue> Ops) {
5794 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5795 // Reset the NodeID to -1.
5800 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5801 /// the line number information on the merged node since it is not possible to
5802 /// preserve the information that operation is associated with multiple lines.
5803 /// This will make the debugger working better at -O0, were there is a higher
5804 /// probability having other instructions associated with that line.
5806 /// For IROrder, we keep the smaller of the two
5807 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5808 DebugLoc NLoc = N->getDebugLoc();
5809 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5810 N->setDebugLoc(DebugLoc());
5812 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5813 N->setIROrder(Order);
5817 /// MorphNodeTo - This *mutates* the specified node to have the specified
5818 /// return type, opcode, and operands.
5820 /// Note that MorphNodeTo returns the resultant node. If there is already a
5821 /// node of the specified opcode and operands, it returns that node instead of
5822 /// the current one. Note that the SDLoc need not be the same.
5824 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5825 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5826 /// node, and because it doesn't require CSE recalculation for any of
5827 /// the node's users.
5829 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5830 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5831 /// the legalizer which maintain worklists that would need to be updated when
5832 /// deleting things.
5833 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5834 SDVTList VTs, ArrayRef<SDValue> Ops) {
5835 unsigned NumOps = Ops.size();
5836 // If an identical node already exists, use it.
5838 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5839 FoldingSetNodeID ID;
5840 AddNodeIDNode(ID, Opc, VTs, Ops);
5841 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5842 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5845 if (!RemoveNodeFromCSEMaps(N))
5848 // Start the morphing.
5850 N->ValueList = VTs.VTs;
5851 N->NumValues = VTs.NumVTs;
5853 // Clear the operands list, updating used nodes to remove this from their
5854 // use list. Keep track of any operands that become dead as a result.
5855 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5856 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5858 SDNode *Used = Use.getNode();
5860 if (Used->use_empty())
5861 DeadNodeSet.insert(Used);
5864 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5865 // Initialize the memory references information.
5866 MN->setMemRefs(nullptr, nullptr);
5867 // If NumOps is larger than the # of operands we can have in a
5868 // MachineSDNode, reallocate the operand list.
5869 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5870 if (MN->OperandsNeedDelete)
5871 delete[] MN->OperandList;
5872 if (NumOps > array_lengthof(MN->LocalOperands))
5873 // We're creating a final node that will live unmorphed for the
5874 // remainder of the current SelectionDAG iteration, so we can allocate
5875 // the operands directly out of a pool with no recycling metadata.
5876 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5877 Ops.data(), NumOps);
5879 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5880 MN->OperandsNeedDelete = false;
5882 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5884 // If NumOps is larger than the # of operands we currently have, reallocate
5885 // the operand list.
5886 if (NumOps > N->NumOperands) {
5887 if (N->OperandsNeedDelete)
5888 delete[] N->OperandList;
5889 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5890 N->OperandsNeedDelete = true;
5892 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5895 // Delete any nodes that are still dead after adding the uses for the
5897 if (!DeadNodeSet.empty()) {
5898 SmallVector<SDNode *, 16> DeadNodes;
5899 for (SDNode *N : DeadNodeSet)
5901 DeadNodes.push_back(N);
5902 RemoveDeadNodes(DeadNodes);
5906 CSEMap.InsertNode(N, IP); // Memoize the new node.
5911 /// getMachineNode - These are used for target selectors to create a new node
5912 /// with specified return type(s), MachineInstr opcode, and operands.
5914 /// Note that getMachineNode returns the resultant node. If there is already a
5915 /// node of the specified opcode and operands, it returns that node instead of
5916 /// the current one.
5918 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5919 SDVTList VTs = getVTList(VT);
5920 return getMachineNode(Opcode, dl, VTs, None);
5924 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5925 SDVTList VTs = getVTList(VT);
5926 SDValue Ops[] = { Op1 };
5927 return getMachineNode(Opcode, dl, VTs, Ops);
5931 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5932 SDValue Op1, SDValue Op2) {
5933 SDVTList VTs = getVTList(VT);
5934 SDValue Ops[] = { Op1, Op2 };
5935 return getMachineNode(Opcode, dl, VTs, Ops);
5939 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5940 SDValue Op1, SDValue Op2, SDValue Op3) {
5941 SDVTList VTs = getVTList(VT);
5942 SDValue Ops[] = { Op1, Op2, Op3 };
5943 return getMachineNode(Opcode, dl, VTs, Ops);
5947 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5948 ArrayRef<SDValue> Ops) {
5949 SDVTList VTs = getVTList(VT);
5950 return getMachineNode(Opcode, dl, VTs, Ops);
5954 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5955 SDVTList VTs = getVTList(VT1, VT2);
5956 return getMachineNode(Opcode, dl, VTs, None);
5960 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5961 EVT VT1, EVT VT2, SDValue Op1) {
5962 SDVTList VTs = getVTList(VT1, VT2);
5963 SDValue Ops[] = { Op1 };
5964 return getMachineNode(Opcode, dl, VTs, Ops);
5968 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5969 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5970 SDVTList VTs = getVTList(VT1, VT2);
5971 SDValue Ops[] = { Op1, Op2 };
5972 return getMachineNode(Opcode, dl, VTs, Ops);
5976 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5977 EVT VT1, EVT VT2, SDValue Op1,
5978 SDValue Op2, SDValue Op3) {
5979 SDVTList VTs = getVTList(VT1, VT2);
5980 SDValue Ops[] = { Op1, Op2, Op3 };
5981 return getMachineNode(Opcode, dl, VTs, Ops);
5985 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5987 ArrayRef<SDValue> Ops) {
5988 SDVTList VTs = getVTList(VT1, VT2);
5989 return getMachineNode(Opcode, dl, VTs, Ops);
5993 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5994 EVT VT1, EVT VT2, EVT VT3,
5995 SDValue Op1, SDValue Op2) {
5996 SDVTList VTs = getVTList(VT1, VT2, VT3);
5997 SDValue Ops[] = { Op1, Op2 };
5998 return getMachineNode(Opcode, dl, VTs, Ops);
6002 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6003 EVT VT1, EVT VT2, EVT VT3,
6004 SDValue Op1, SDValue Op2, SDValue Op3) {
6005 SDVTList VTs = getVTList(VT1, VT2, VT3);
6006 SDValue Ops[] = { Op1, Op2, Op3 };
6007 return getMachineNode(Opcode, dl, VTs, Ops);
6011 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6012 EVT VT1, EVT VT2, EVT VT3,
6013 ArrayRef<SDValue> Ops) {
6014 SDVTList VTs = getVTList(VT1, VT2, VT3);
6015 return getMachineNode(Opcode, dl, VTs, Ops);
6019 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6020 EVT VT2, EVT VT3, EVT VT4,
6021 ArrayRef<SDValue> Ops) {
6022 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6023 return getMachineNode(Opcode, dl, VTs, Ops);
6027 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6028 ArrayRef<EVT> ResultTys,
6029 ArrayRef<SDValue> Ops) {
6030 SDVTList VTs = getVTList(ResultTys);
6031 return getMachineNode(Opcode, dl, VTs, Ops);
6035 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6036 ArrayRef<SDValue> OpsArray) {
6037 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6040 const SDValue *Ops = OpsArray.data();
6041 unsigned NumOps = OpsArray.size();
6044 FoldingSetNodeID ID;
6045 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6047 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6048 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6052 // Allocate a new MachineSDNode.
6053 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6054 DL.getDebugLoc(), VTs);
6056 // Initialize the operands list.
6057 if (NumOps > array_lengthof(N->LocalOperands))
6058 // We're creating a final node that will live unmorphed for the
6059 // remainder of the current SelectionDAG iteration, so we can allocate
6060 // the operands directly out of a pool with no recycling metadata.
6061 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6064 N->InitOperands(N->LocalOperands, Ops, NumOps);
6065 N->OperandsNeedDelete = false;
6068 CSEMap.InsertNode(N, IP);
6074 /// getTargetExtractSubreg - A convenience function for creating
6075 /// TargetOpcode::EXTRACT_SUBREG nodes.
6077 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6079 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6080 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6081 VT, Operand, SRIdxVal);
6082 return SDValue(Subreg, 0);
6085 /// getTargetInsertSubreg - A convenience function for creating
6086 /// TargetOpcode::INSERT_SUBREG nodes.
6088 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6089 SDValue Operand, SDValue Subreg) {
6090 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6091 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6092 VT, Operand, Subreg, SRIdxVal);
6093 return SDValue(Result, 0);
6096 /// getNodeIfExists - Get the specified node if it's already available, or
6097 /// else return NULL.
6098 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6099 ArrayRef<SDValue> Ops,
6100 const SDNodeFlags *Flags) {
6101 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6102 FoldingSetNodeID ID;
6103 AddNodeIDNode(ID, Opcode, VTList, Ops);
6104 AddNodeIDFlags(ID, Opcode, Flags);
6106 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6112 /// getDbgValue - Creates a SDDbgValue node.
6115 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6116 unsigned R, bool IsIndirect, uint64_t Off,
6117 DebugLoc DL, unsigned O) {
6118 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6119 "Expected inlined-at fields to agree");
6120 return new (DbgInfo->getAlloc())
6121 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6125 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6126 const Value *C, uint64_t Off,
6127 DebugLoc DL, unsigned O) {
6128 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6129 "Expected inlined-at fields to agree");
6130 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6134 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6135 unsigned FI, uint64_t Off,
6136 DebugLoc DL, unsigned O) {
6137 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6138 "Expected inlined-at fields to agree");
6139 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6144 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6145 /// pointed to by a use iterator is deleted, increment the use iterator
6146 /// so that it doesn't dangle.
6148 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6149 SDNode::use_iterator &UI;
6150 SDNode::use_iterator &UE;
6152 void NodeDeleted(SDNode *N, SDNode *E) override {
6153 // Increment the iterator as needed.
6154 while (UI != UE && N == *UI)
6159 RAUWUpdateListener(SelectionDAG &d,
6160 SDNode::use_iterator &ui,
6161 SDNode::use_iterator &ue)
6162 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6167 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6168 /// This can cause recursive merging of nodes in the DAG.
6170 /// This version assumes From has a single result value.
6172 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6173 SDNode *From = FromN.getNode();
6174 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6175 "Cannot replace with this method!");
6176 assert(From != To.getNode() && "Cannot replace uses of with self");
6178 // Iterate over all the existing uses of From. New uses will be added
6179 // to the beginning of the use list, which we avoid visiting.
6180 // This specifically avoids visiting uses of From that arise while the
6181 // replacement is happening, because any such uses would be the result
6182 // of CSE: If an existing node looks like From after one of its operands
6183 // is replaced by To, we don't want to replace of all its users with To
6184 // too. See PR3018 for more info.
6185 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6186 RAUWUpdateListener Listener(*this, UI, UE);
6190 // This node is about to morph, remove its old self from the CSE maps.
6191 RemoveNodeFromCSEMaps(User);
6193 // A user can appear in a use list multiple times, and when this
6194 // happens the uses are usually next to each other in the list.
6195 // To help reduce the number of CSE recomputations, process all
6196 // the uses of this user that we can find this way.
6198 SDUse &Use = UI.getUse();
6201 } while (UI != UE && *UI == User);
6203 // Now that we have modified User, add it back to the CSE maps. If it
6204 // already exists there, recursively merge the results together.
6205 AddModifiedNodeToCSEMaps(User);
6208 // If we just RAUW'd the root, take note.
6209 if (FromN == getRoot())
6213 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6214 /// This can cause recursive merging of nodes in the DAG.
6216 /// This version assumes that for each value of From, there is a
6217 /// corresponding value in To in the same position with the same type.
6219 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6221 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6222 assert((!From->hasAnyUseOfValue(i) ||
6223 From->getValueType(i) == To->getValueType(i)) &&
6224 "Cannot use this version of ReplaceAllUsesWith!");
6227 // Handle the trivial case.
6231 // Iterate over just the existing users of From. See the comments in
6232 // the ReplaceAllUsesWith above.
6233 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6234 RAUWUpdateListener Listener(*this, UI, UE);
6238 // This node is about to morph, remove its old self from the CSE maps.
6239 RemoveNodeFromCSEMaps(User);
6241 // A user can appear in a use list multiple times, and when this
6242 // happens the uses are usually next to each other in the list.
6243 // To help reduce the number of CSE recomputations, process all
6244 // the uses of this user that we can find this way.
6246 SDUse &Use = UI.getUse();
6249 } while (UI != UE && *UI == User);
6251 // Now that we have modified User, add it back to the CSE maps. If it
6252 // already exists there, recursively merge the results together.
6253 AddModifiedNodeToCSEMaps(User);
6256 // If we just RAUW'd the root, take note.
6257 if (From == getRoot().getNode())
6258 setRoot(SDValue(To, getRoot().getResNo()));
6261 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6262 /// This can cause recursive merging of nodes in the DAG.
6264 /// This version can replace From with any result values. To must match the
6265 /// number and types of values returned by From.
6266 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6267 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6268 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6270 // Iterate over just the existing users of From. See the comments in
6271 // the ReplaceAllUsesWith above.
6272 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6273 RAUWUpdateListener Listener(*this, UI, UE);
6277 // This node is about to morph, remove its old self from the CSE maps.
6278 RemoveNodeFromCSEMaps(User);
6280 // A user can appear in a use list multiple times, and when this
6281 // happens the uses are usually next to each other in the list.
6282 // To help reduce the number of CSE recomputations, process all
6283 // the uses of this user that we can find this way.
6285 SDUse &Use = UI.getUse();
6286 const SDValue &ToOp = To[Use.getResNo()];
6289 } while (UI != UE && *UI == User);
6291 // Now that we have modified User, add it back to the CSE maps. If it
6292 // already exists there, recursively merge the results together.
6293 AddModifiedNodeToCSEMaps(User);
6296 // If we just RAUW'd the root, take note.
6297 if (From == getRoot().getNode())
6298 setRoot(SDValue(To[getRoot().getResNo()]));
6301 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6302 /// uses of other values produced by From.getNode() alone. The Deleted
6303 /// vector is handled the same way as for ReplaceAllUsesWith.
6304 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6305 // Handle the really simple, really trivial case efficiently.
6306 if (From == To) return;
6308 // Handle the simple, trivial, case efficiently.
6309 if (From.getNode()->getNumValues() == 1) {
6310 ReplaceAllUsesWith(From, To);
6314 // Iterate over just the existing users of From. See the comments in
6315 // the ReplaceAllUsesWith above.
6316 SDNode::use_iterator UI = From.getNode()->use_begin(),
6317 UE = From.getNode()->use_end();
6318 RAUWUpdateListener Listener(*this, UI, UE);
6321 bool UserRemovedFromCSEMaps = false;
6323 // A user can appear in a use list multiple times, and when this
6324 // happens the uses are usually next to each other in the list.
6325 // To help reduce the number of CSE recomputations, process all
6326 // the uses of this user that we can find this way.
6328 SDUse &Use = UI.getUse();
6330 // Skip uses of different values from the same node.
6331 if (Use.getResNo() != From.getResNo()) {
6336 // If this node hasn't been modified yet, it's still in the CSE maps,
6337 // so remove its old self from the CSE maps.
6338 if (!UserRemovedFromCSEMaps) {
6339 RemoveNodeFromCSEMaps(User);
6340 UserRemovedFromCSEMaps = true;
6345 } while (UI != UE && *UI == User);
6347 // We are iterating over all uses of the From node, so if a use
6348 // doesn't use the specific value, no changes are made.
6349 if (!UserRemovedFromCSEMaps)
6352 // Now that we have modified User, add it back to the CSE maps. If it
6353 // already exists there, recursively merge the results together.
6354 AddModifiedNodeToCSEMaps(User);
6357 // If we just RAUW'd the root, take note.
6358 if (From == getRoot())
6363 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6364 /// to record information about a use.
6371 /// operator< - Sort Memos by User.
6372 bool operator<(const UseMemo &L, const UseMemo &R) {
6373 return (intptr_t)L.User < (intptr_t)R.User;
6377 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6378 /// uses of other values produced by From.getNode() alone. The same value
6379 /// may appear in both the From and To list. The Deleted vector is
6380 /// handled the same way as for ReplaceAllUsesWith.
6381 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6384 // Handle the simple, trivial case efficiently.
6386 return ReplaceAllUsesOfValueWith(*From, *To);
6388 // Read up all the uses and make records of them. This helps
6389 // processing new uses that are introduced during the
6390 // replacement process.
6391 SmallVector<UseMemo, 4> Uses;
6392 for (unsigned i = 0; i != Num; ++i) {
6393 unsigned FromResNo = From[i].getResNo();
6394 SDNode *FromNode = From[i].getNode();
6395 for (SDNode::use_iterator UI = FromNode->use_begin(),
6396 E = FromNode->use_end(); UI != E; ++UI) {
6397 SDUse &Use = UI.getUse();
6398 if (Use.getResNo() == FromResNo) {
6399 UseMemo Memo = { *UI, i, &Use };
6400 Uses.push_back(Memo);
6405 // Sort the uses, so that all the uses from a given User are together.
6406 std::sort(Uses.begin(), Uses.end());
6408 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6409 UseIndex != UseIndexEnd; ) {
6410 // We know that this user uses some value of From. If it is the right
6411 // value, update it.
6412 SDNode *User = Uses[UseIndex].User;
6414 // This node is about to morph, remove its old self from the CSE maps.
6415 RemoveNodeFromCSEMaps(User);
6417 // The Uses array is sorted, so all the uses for a given User
6418 // are next to each other in the list.
6419 // To help reduce the number of CSE recomputations, process all
6420 // the uses of this user that we can find this way.
6422 unsigned i = Uses[UseIndex].Index;
6423 SDUse &Use = *Uses[UseIndex].Use;
6427 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6429 // Now that we have modified User, add it back to the CSE maps. If it
6430 // already exists there, recursively merge the results together.
6431 AddModifiedNodeToCSEMaps(User);
6435 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6436 /// based on their topological order. It returns the maximum id and a vector
6437 /// of the SDNodes* in assigned order by reference.
6438 unsigned SelectionDAG::AssignTopologicalOrder() {
6440 unsigned DAGSize = 0;
6442 // SortedPos tracks the progress of the algorithm. Nodes before it are
6443 // sorted, nodes after it are unsorted. When the algorithm completes
6444 // it is at the end of the list.
6445 allnodes_iterator SortedPos = allnodes_begin();
6447 // Visit all the nodes. Move nodes with no operands to the front of
6448 // the list immediately. Annotate nodes that do have operands with their
6449 // operand count. Before we do this, the Node Id fields of the nodes
6450 // may contain arbitrary values. After, the Node Id fields for nodes
6451 // before SortedPos will contain the topological sort index, and the
6452 // Node Id fields for nodes At SortedPos and after will contain the
6453 // count of outstanding operands.
6454 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6456 checkForCycles(N, this);
6457 unsigned Degree = N->getNumOperands();
6459 // A node with no uses, add it to the result array immediately.
6460 N->setNodeId(DAGSize++);
6461 allnodes_iterator Q = N;
6463 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6464 assert(SortedPos != AllNodes.end() && "Overran node list");
6467 // Temporarily use the Node Id as scratch space for the degree count.
6468 N->setNodeId(Degree);
6472 // Visit all the nodes. As we iterate, move nodes into sorted order,
6473 // such that by the time the end is reached all nodes will be sorted.
6474 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6476 checkForCycles(N, this);
6477 // N is in sorted position, so all its uses have one less operand
6478 // that needs to be sorted.
6479 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6482 unsigned Degree = P->getNodeId();
6483 assert(Degree != 0 && "Invalid node degree");
6486 // All of P's operands are sorted, so P may sorted now.
6487 P->setNodeId(DAGSize++);
6489 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6490 assert(SortedPos != AllNodes.end() && "Overran node list");
6493 // Update P's outstanding operand count.
6494 P->setNodeId(Degree);
6497 if (I == SortedPos) {
6500 dbgs() << "Overran sorted position:\n";
6501 S->dumprFull(this); dbgs() << "\n";
6502 dbgs() << "Checking if this is due to cycles\n";
6503 checkForCycles(this, true);
6505 llvm_unreachable(nullptr);
6509 assert(SortedPos == AllNodes.end() &&
6510 "Topological sort incomplete!");
6511 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6512 "First node in topological sort is not the entry token!");
6513 assert(AllNodes.front().getNodeId() == 0 &&
6514 "First node in topological sort has non-zero id!");
6515 assert(AllNodes.front().getNumOperands() == 0 &&
6516 "First node in topological sort has operands!");
6517 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6518 "Last node in topologic sort has unexpected id!");
6519 assert(AllNodes.back().use_empty() &&
6520 "Last node in topologic sort has users!");
6521 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6525 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6526 /// value is produced by SD.
6527 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6529 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6530 SD->setHasDebugValue(true);
6532 DbgInfo->add(DB, SD, isParameter);
6535 /// TransferDbgValues - Transfer SDDbgValues.
6536 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6537 if (From == To || !From.getNode()->getHasDebugValue())
6539 SDNode *FromNode = From.getNode();
6540 SDNode *ToNode = To.getNode();
6541 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6542 SmallVector<SDDbgValue *, 2> ClonedDVs;
6543 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6545 SDDbgValue *Dbg = *I;
6546 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6548 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6549 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6550 Dbg->getDebugLoc(), Dbg->getOrder());
6551 ClonedDVs.push_back(Clone);
6554 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6555 E = ClonedDVs.end(); I != E; ++I)
6556 AddDbgValue(*I, ToNode, false);
6559 //===----------------------------------------------------------------------===//
6561 //===----------------------------------------------------------------------===//
6563 HandleSDNode::~HandleSDNode() {
6567 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6568 DebugLoc DL, const GlobalValue *GA,
6569 EVT VT, int64_t o, unsigned char TF)
6570 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6574 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6575 SDValue X, unsigned SrcAS,
6577 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6578 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6580 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6581 EVT memvt, MachineMemOperand *mmo)
6582 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6583 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6584 MMO->isNonTemporal(), MMO->isInvariant());
6585 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6586 assert(isNonTemporal() == MMO->isNonTemporal() &&
6587 "Non-temporal encoding error!");
6588 // We check here that the size of the memory operand fits within the size of
6589 // the MMO. This is because the MMO might indicate only a possible address
6590 // range instead of specifying the affected memory addresses precisely.
6591 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6594 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6595 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6596 : SDNode(Opc, Order, dl, VTs, Ops),
6597 MemoryVT(memvt), MMO(mmo) {
6598 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6599 MMO->isNonTemporal(), MMO->isInvariant());
6600 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6601 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6604 /// Profile - Gather unique data for the node.
6606 void SDNode::Profile(FoldingSetNodeID &ID) const {
6607 AddNodeIDNode(ID, this);
6612 std::vector<EVT> VTs;
6615 VTs.reserve(MVT::LAST_VALUETYPE);
6616 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6617 VTs.push_back(MVT((MVT::SimpleValueType)i));
6622 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6623 static ManagedStatic<EVTArray> SimpleVTArray;
6624 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6626 /// getValueTypeList - Return a pointer to the specified value type.
6628 const EVT *SDNode::getValueTypeList(EVT VT) {
6629 if (VT.isExtended()) {
6630 sys::SmartScopedLock<true> Lock(*VTMutex);
6631 return &(*EVTs->insert(VT).first);
6633 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6634 "Value type out of range!");
6635 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6639 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6640 /// indicated value. This method ignores uses of other values defined by this
6642 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6643 assert(Value < getNumValues() && "Bad value!");
6645 // TODO: Only iterate over uses of a given value of the node
6646 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6647 if (UI.getUse().getResNo() == Value) {
6654 // Found exactly the right number of uses?
6659 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6660 /// value. This method ignores uses of other values defined by this operation.
6661 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6662 assert(Value < getNumValues() && "Bad value!");
6664 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6665 if (UI.getUse().getResNo() == Value)
6672 /// isOnlyUserOf - Return true if this node is the only use of N.
6674 bool SDNode::isOnlyUserOf(SDNode *N) const {
6676 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6687 /// isOperand - Return true if this node is an operand of N.
6689 bool SDValue::isOperandOf(SDNode *N) const {
6690 for (const SDValue &Op : N->op_values())
6696 bool SDNode::isOperandOf(SDNode *N) const {
6697 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6698 if (this == N->OperandList[i].getNode())
6703 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6704 /// be a chain) reaches the specified operand without crossing any
6705 /// side-effecting instructions on any chain path. In practice, this looks
6706 /// through token factors and non-volatile loads. In order to remain efficient,
6707 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6708 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6709 unsigned Depth) const {
6710 if (*this == Dest) return true;
6712 // Don't search too deeply, we just want to be able to see through
6713 // TokenFactor's etc.
6714 if (Depth == 0) return false;
6716 // If this is a token factor, all inputs to the TF happen in parallel. If any
6717 // of the operands of the TF does not reach dest, then we cannot do the xform.
6718 if (getOpcode() == ISD::TokenFactor) {
6719 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6720 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6725 // Loads don't have side effects, look through them.
6726 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6727 if (!Ld->isVolatile())
6728 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6733 /// hasPredecessor - Return true if N is a predecessor of this node.
6734 /// N is either an operand of this node, or can be reached by recursively
6735 /// traversing up the operands.
6736 /// NOTE: This is an expensive method. Use it carefully.
6737 bool SDNode::hasPredecessor(const SDNode *N) const {
6738 SmallPtrSet<const SDNode *, 32> Visited;
6739 SmallVector<const SDNode *, 16> Worklist;
6740 return hasPredecessorHelper(N, Visited, Worklist);
6744 SDNode::hasPredecessorHelper(const SDNode *N,
6745 SmallPtrSetImpl<const SDNode *> &Visited,
6746 SmallVectorImpl<const SDNode *> &Worklist) const {
6747 if (Visited.empty()) {
6748 Worklist.push_back(this);
6750 // Take a look in the visited set. If we've already encountered this node
6751 // we needn't search further.
6752 if (Visited.count(N))
6756 // Haven't visited N yet. Continue the search.
6757 while (!Worklist.empty()) {
6758 const SDNode *M = Worklist.pop_back_val();
6759 for (const SDValue &OpV : M->op_values()) {
6760 SDNode *Op = OpV.getNode();
6761 if (Visited.insert(Op).second)
6762 Worklist.push_back(Op);
6771 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6772 assert(Num < NumOperands && "Invalid child # of SDNode!");
6773 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6776 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6777 assert(N->getNumValues() == 1 &&
6778 "Can't unroll a vector with multiple results!");
6780 EVT VT = N->getValueType(0);
6781 unsigned NE = VT.getVectorNumElements();
6782 EVT EltVT = VT.getVectorElementType();
6785 SmallVector<SDValue, 8> Scalars;
6786 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6788 // If ResNE is 0, fully unroll the vector op.
6791 else if (NE > ResNE)
6795 for (i= 0; i != NE; ++i) {
6796 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6797 SDValue Operand = N->getOperand(j);
6798 EVT OperandVT = Operand.getValueType();
6799 if (OperandVT.isVector()) {
6800 // A vector operand; extract a single element.
6801 EVT OperandEltVT = OperandVT.getVectorElementType();
6803 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6804 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6806 // A scalar operand; just use it as is.
6807 Operands[j] = Operand;
6811 switch (N->getOpcode()) {
6813 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6816 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6823 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6824 getShiftAmountOperand(Operands[0].getValueType(),
6827 case ISD::SIGN_EXTEND_INREG:
6828 case ISD::FP_ROUND_INREG: {
6829 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6830 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6832 getValueType(ExtVT)));
6837 for (; i < ResNE; ++i)
6838 Scalars.push_back(getUNDEF(EltVT));
6840 return getNode(ISD::BUILD_VECTOR, dl,
6841 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6845 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6846 /// location that is 'Dist' units away from the location that the 'Base' load
6847 /// is loading from.
6848 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6849 unsigned Bytes, int Dist) const {
6850 if (LD->getChain() != Base->getChain())
6852 EVT VT = LD->getValueType(0);
6853 if (VT.getSizeInBits() / 8 != Bytes)
6856 SDValue Loc = LD->getOperand(1);
6857 SDValue BaseLoc = Base->getOperand(1);
6858 if (Loc.getOpcode() == ISD::FrameIndex) {
6859 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6861 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6862 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6863 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6864 int FS = MFI->getObjectSize(FI);
6865 int BFS = MFI->getObjectSize(BFI);
6866 if (FS != BFS || FS != (int)Bytes) return false;
6867 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6871 if (isBaseWithConstantOffset(Loc)) {
6872 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6873 if (Loc.getOperand(0) == BaseLoc) {
6874 // If the base location is a simple address with no offset itself, then
6875 // the second load's first add operand should be the base address.
6876 if (LocOffset == Dist * (int)Bytes)
6878 } else if (isBaseWithConstantOffset(BaseLoc)) {
6879 // The base location itself has an offset, so subtract that value from the
6880 // second load's offset before comparing to distance * size.
6882 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6883 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6884 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6889 const GlobalValue *GV1 = nullptr;
6890 const GlobalValue *GV2 = nullptr;
6891 int64_t Offset1 = 0;
6892 int64_t Offset2 = 0;
6893 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6894 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6895 if (isGA1 && isGA2 && GV1 == GV2)
6896 return Offset1 == (Offset2 + Dist*Bytes);
6901 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6902 /// it cannot be inferred.
6903 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6904 // If this is a GlobalAddress + cst, return the alignment.
6905 const GlobalValue *GV;
6906 int64_t GVOffset = 0;
6907 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6908 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6909 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6910 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6912 unsigned AlignBits = KnownZero.countTrailingOnes();
6913 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6915 return MinAlign(Align, GVOffset);
6918 // If this is a direct reference to a stack slot, use information about the
6919 // stack slot's alignment.
6920 int FrameIdx = 1 << 31;
6921 int64_t FrameOffset = 0;
6922 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6923 FrameIdx = FI->getIndex();
6924 } else if (isBaseWithConstantOffset(Ptr) &&
6925 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6927 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6928 FrameOffset = Ptr.getConstantOperandVal(1);
6931 if (FrameIdx != (1 << 31)) {
6932 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6933 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6941 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6942 /// which is split (or expanded) into two not necessarily identical pieces.
6943 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6944 // Currently all types are split in half.
6946 if (!VT.isVector()) {
6947 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6949 unsigned NumElements = VT.getVectorNumElements();
6950 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6951 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6954 return std::make_pair(LoVT, HiVT);
6957 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6959 std::pair<SDValue, SDValue>
6960 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6962 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6963 N.getValueType().getVectorNumElements() &&
6964 "More vector elements requested than available!");
6966 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6967 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
6968 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6969 getConstant(LoVT.getVectorNumElements(), DL,
6970 TLI->getVectorIdxTy(getDataLayout())));
6971 return std::make_pair(Lo, Hi);
6974 void SelectionDAG::ExtractVectorElements(SDValue Op,
6975 SmallVectorImpl<SDValue> &Args,
6976 unsigned Start, unsigned Count) {
6977 EVT VT = Op.getValueType();
6979 Count = VT.getVectorNumElements();
6981 EVT EltVT = VT.getVectorElementType();
6982 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
6984 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6985 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6986 Op, getConstant(i, SL, IdxTy)));
6990 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6991 unsigned GlobalAddressSDNode::getAddressSpace() const {
6992 return getGlobal()->getType()->getAddressSpace();
6996 Type *ConstantPoolSDNode::getType() const {
6997 if (isMachineConstantPoolEntry())
6998 return Val.MachineCPVal->getType();
6999 return Val.ConstVal->getType();
7002 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7004 unsigned &SplatBitSize,
7006 unsigned MinSplatBits,
7007 bool isBigEndian) const {
7008 EVT VT = getValueType(0);
7009 assert(VT.isVector() && "Expected a vector type");
7010 unsigned sz = VT.getSizeInBits();
7011 if (MinSplatBits > sz)
7014 SplatValue = APInt(sz, 0);
7015 SplatUndef = APInt(sz, 0);
7017 // Get the bits. Bits with undefined values (when the corresponding element
7018 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7019 // in SplatValue. If any of the values are not constant, give up and return
7021 unsigned int nOps = getNumOperands();
7022 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7023 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7025 for (unsigned j = 0; j < nOps; ++j) {
7026 unsigned i = isBigEndian ? nOps-1-j : j;
7027 SDValue OpVal = getOperand(i);
7028 unsigned BitPos = j * EltBitSize;
7030 if (OpVal.getOpcode() == ISD::UNDEF)
7031 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7032 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7033 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7034 zextOrTrunc(sz) << BitPos;
7035 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7036 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7041 // The build_vector is all constants or undefs. Find the smallest element
7042 // size that splats the vector.
7044 HasAnyUndefs = (SplatUndef != 0);
7047 unsigned HalfSize = sz / 2;
7048 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7049 APInt LowValue = SplatValue.trunc(HalfSize);
7050 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7051 APInt LowUndef = SplatUndef.trunc(HalfSize);
7053 // If the two halves do not match (ignoring undef bits), stop here.
7054 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7055 MinSplatBits > HalfSize)
7058 SplatValue = HighValue | LowValue;
7059 SplatUndef = HighUndef & LowUndef;
7068 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7069 if (UndefElements) {
7070 UndefElements->clear();
7071 UndefElements->resize(getNumOperands());
7074 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7075 SDValue Op = getOperand(i);
7076 if (Op.getOpcode() == ISD::UNDEF) {
7078 (*UndefElements)[i] = true;
7079 } else if (!Splatted) {
7081 } else if (Splatted != Op) {
7087 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7088 "Can only have a splat without a constant for all undefs.");
7089 return getOperand(0);
7096 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7097 return dyn_cast_or_null<ConstantSDNode>(
7098 getSplatValue(UndefElements).getNode());
7102 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7103 return dyn_cast_or_null<ConstantFPSDNode>(
7104 getSplatValue(UndefElements).getNode());
7107 bool BuildVectorSDNode::isConstant() const {
7108 for (const SDValue &Op : op_values()) {
7109 unsigned Opc = Op.getOpcode();
7110 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7116 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7117 // Find the first non-undef value in the shuffle mask.
7119 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7122 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7124 // Make sure all remaining elements are either undef or the same as the first
7126 for (int Idx = Mask[i]; i != e; ++i)
7127 if (Mask[i] >= 0 && Mask[i] != Idx)
7133 static void checkForCyclesHelper(const SDNode *N,
7134 SmallPtrSetImpl<const SDNode*> &Visited,
7135 SmallPtrSetImpl<const SDNode*> &Checked,
7136 const llvm::SelectionDAG *DAG) {
7137 // If this node has already been checked, don't check it again.
7138 if (Checked.count(N))
7141 // If a node has already been visited on this depth-first walk, reject it as
7143 if (!Visited.insert(N).second) {
7144 errs() << "Detected cycle in SelectionDAG\n";
7145 dbgs() << "Offending node:\n";
7146 N->dumprFull(DAG); dbgs() << "\n";
7150 for (const SDValue &Op : N->op_values())
7151 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7158 void llvm::checkForCycles(const llvm::SDNode *N,
7159 const llvm::SelectionDAG *DAG,
7167 assert(N && "Checking nonexistent SDNode");
7168 SmallPtrSet<const SDNode*, 32> visited;
7169 SmallPtrSet<const SDNode*, 32> checked;
7170 checkForCyclesHelper(N, visited, checked, DAG);
7175 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7176 checkForCycles(DAG->getRoot().getNode(), DAG, force);