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 (const SDValue &Op : N->op_values()) {
155 if (Op.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 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (const SDValue &Op : N->op_values()) {
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// \brief Return true if the specified node is a BUILD_VECTOR node of
199 /// all ConstantFPSDNode or undef.
200 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
201 if (N->getOpcode() != ISD::BUILD_VECTOR)
204 for (const SDValue &Op : N->op_values()) {
205 if (Op.getOpcode() == ISD::UNDEF)
207 if (!isa<ConstantFPSDNode>(Op))
213 /// isScalarToVector - Return true if the specified node is a
214 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
215 /// element is not an undef.
216 bool ISD::isScalarToVector(const SDNode *N) {
217 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
220 if (N->getOpcode() != ISD::BUILD_VECTOR)
222 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
224 unsigned NumElems = N->getNumOperands();
227 for (unsigned i = 1; i < NumElems; ++i) {
228 SDValue V = N->getOperand(i);
229 if (V.getOpcode() != ISD::UNDEF)
235 /// allOperandsUndef - Return true if the node has at least one operand
236 /// and all operands of the specified node are ISD::UNDEF.
237 bool ISD::allOperandsUndef(const SDNode *N) {
238 // Return false if the node has no operands.
239 // This is "logically inconsistent" with the definition of "all" but
240 // is probably the desired behavior.
241 if (N->getNumOperands() == 0)
244 for (const SDValue &Op : N->op_values())
245 if (Op.getOpcode() != ISD::UNDEF)
251 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
254 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
256 return ISD::SIGN_EXTEND;
258 return ISD::ZERO_EXTEND;
263 llvm_unreachable("Invalid LoadExtType");
266 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
267 /// when given the operation for (X op Y).
268 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
269 // To perform this operation, we just need to swap the L and G bits of the
271 unsigned OldL = (Operation >> 2) & 1;
272 unsigned OldG = (Operation >> 1) & 1;
273 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
274 (OldL << 1) | // New G bit
275 (OldG << 2)); // New L bit.
278 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
279 /// 'op' is a valid SetCC operation.
280 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
281 unsigned Operation = Op;
283 Operation ^= 7; // Flip L, G, E bits, but not U.
285 Operation ^= 15; // Flip all of the condition bits.
287 if (Operation > ISD::SETTRUE2)
288 Operation &= ~8; // Don't let N and U bits get set.
290 return ISD::CondCode(Operation);
294 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
295 /// signed operation and 2 if the result is an unsigned comparison. Return zero
296 /// if the operation does not depend on the sign of the input (setne and seteq).
297 static int isSignedOp(ISD::CondCode Opcode) {
299 default: llvm_unreachable("Illegal integer setcc operation!");
301 case ISD::SETNE: return 0;
305 case ISD::SETGE: return 1;
309 case ISD::SETUGE: return 2;
313 /// getSetCCOrOperation - Return the result of a logical OR between different
314 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
315 /// returns SETCC_INVALID if it is not possible to represent the resultant
317 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
319 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
320 // Cannot fold a signed integer setcc with an unsigned integer setcc.
321 return ISD::SETCC_INVALID;
323 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
325 // If the N and U bits get set then the resultant comparison DOES suddenly
326 // care about orderedness, and is true when ordered.
327 if (Op > ISD::SETTRUE2)
328 Op &= ~16; // Clear the U bit if the N bit is set.
330 // Canonicalize illegal integer setcc's.
331 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
334 return ISD::CondCode(Op);
337 /// getSetCCAndOperation - Return the result of a logical AND between different
338 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
339 /// function returns zero if it is not possible to represent the resultant
341 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
343 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
344 // Cannot fold a signed setcc with an unsigned setcc.
345 return ISD::SETCC_INVALID;
347 // Combine all of the condition bits.
348 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
350 // Canonicalize illegal integer setcc's.
354 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
355 case ISD::SETOEQ: // SETEQ & SETU[LG]E
356 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
357 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
358 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
365 //===----------------------------------------------------------------------===//
366 // SDNode Profile Support
367 //===----------------------------------------------------------------------===//
369 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
371 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
375 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
376 /// solely with their pointer.
377 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
378 ID.AddPointer(VTList.VTs);
381 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
383 static void AddNodeIDOperands(FoldingSetNodeID &ID,
384 ArrayRef<SDValue> Ops) {
385 for (auto& Op : Ops) {
386 ID.AddPointer(Op.getNode());
387 ID.AddInteger(Op.getResNo());
391 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
393 static void AddNodeIDOperands(FoldingSetNodeID &ID,
394 ArrayRef<SDUse> Ops) {
395 for (auto& Op : Ops) {
396 ID.AddPointer(Op.getNode());
397 ID.AddInteger(Op.getResNo());
400 /// Add logical or fast math flag values to FoldingSetNodeID value.
401 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
402 const SDNodeFlags *Flags) {
403 if (!Flags || !isBinOpWithFlags(Opcode))
406 unsigned RawFlags = Flags->getRawFlags();
407 // If no flags are set, do not alter the ID. We must match the ID of nodes
408 // that were created without explicitly specifying flags. This also saves time
409 // and allows a gradual increase in API usage of the optional optimization
412 ID.AddInteger(RawFlags);
415 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
416 if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
417 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
420 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
421 SDVTList VTList, ArrayRef<SDValue> OpList) {
422 AddNodeIDOpcode(ID, OpC);
423 AddNodeIDValueTypes(ID, VTList);
424 AddNodeIDOperands(ID, OpList);
427 /// If this is an SDNode with special info, add this info to the NodeID data.
428 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
429 switch (N->getOpcode()) {
430 case ISD::TargetExternalSymbol:
431 case ISD::ExternalSymbol:
433 llvm_unreachable("Should only be used on nodes with operands");
434 default: break; // Normal nodes don't need extra info.
435 case ISD::TargetConstant:
436 case ISD::Constant: {
437 const ConstantSDNode *C = cast<ConstantSDNode>(N);
438 ID.AddPointer(C->getConstantIntValue());
439 ID.AddBoolean(C->isOpaque());
442 case ISD::TargetConstantFP:
443 case ISD::ConstantFP: {
444 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
447 case ISD::TargetGlobalAddress:
448 case ISD::GlobalAddress:
449 case ISD::TargetGlobalTLSAddress:
450 case ISD::GlobalTLSAddress: {
451 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
452 ID.AddPointer(GA->getGlobal());
453 ID.AddInteger(GA->getOffset());
454 ID.AddInteger(GA->getTargetFlags());
455 ID.AddInteger(GA->getAddressSpace());
458 case ISD::BasicBlock:
459 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
462 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
464 case ISD::RegisterMask:
465 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
468 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
470 case ISD::FrameIndex:
471 case ISD::TargetFrameIndex:
472 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
475 case ISD::TargetJumpTable:
476 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
477 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
479 case ISD::ConstantPool:
480 case ISD::TargetConstantPool: {
481 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
482 ID.AddInteger(CP->getAlignment());
483 ID.AddInteger(CP->getOffset());
484 if (CP->isMachineConstantPoolEntry())
485 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
487 ID.AddPointer(CP->getConstVal());
488 ID.AddInteger(CP->getTargetFlags());
491 case ISD::TargetIndex: {
492 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
493 ID.AddInteger(TI->getIndex());
494 ID.AddInteger(TI->getOffset());
495 ID.AddInteger(TI->getTargetFlags());
499 const LoadSDNode *LD = cast<LoadSDNode>(N);
500 ID.AddInteger(LD->getMemoryVT().getRawBits());
501 ID.AddInteger(LD->getRawSubclassData());
502 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
506 const StoreSDNode *ST = cast<StoreSDNode>(N);
507 ID.AddInteger(ST->getMemoryVT().getRawBits());
508 ID.AddInteger(ST->getRawSubclassData());
509 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
512 case ISD::ATOMIC_CMP_SWAP:
513 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
514 case ISD::ATOMIC_SWAP:
515 case ISD::ATOMIC_LOAD_ADD:
516 case ISD::ATOMIC_LOAD_SUB:
517 case ISD::ATOMIC_LOAD_AND:
518 case ISD::ATOMIC_LOAD_OR:
519 case ISD::ATOMIC_LOAD_XOR:
520 case ISD::ATOMIC_LOAD_NAND:
521 case ISD::ATOMIC_LOAD_MIN:
522 case ISD::ATOMIC_LOAD_MAX:
523 case ISD::ATOMIC_LOAD_UMIN:
524 case ISD::ATOMIC_LOAD_UMAX:
525 case ISD::ATOMIC_LOAD:
526 case ISD::ATOMIC_STORE: {
527 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
528 ID.AddInteger(AT->getMemoryVT().getRawBits());
529 ID.AddInteger(AT->getRawSubclassData());
530 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
533 case ISD::PREFETCH: {
534 const MemSDNode *PF = cast<MemSDNode>(N);
535 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
538 case ISD::VECTOR_SHUFFLE: {
539 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
540 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
542 ID.AddInteger(SVN->getMaskElt(i));
545 case ISD::TargetBlockAddress:
546 case ISD::BlockAddress: {
547 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
548 ID.AddPointer(BA->getBlockAddress());
549 ID.AddInteger(BA->getOffset());
550 ID.AddInteger(BA->getTargetFlags());
553 } // end switch (N->getOpcode())
555 AddNodeIDFlags(ID, N);
557 // Target specific memory nodes could also have address spaces to check.
558 if (N->isTargetMemoryOpcode())
559 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
562 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
564 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
565 AddNodeIDOpcode(ID, N->getOpcode());
566 // Add the return value info.
567 AddNodeIDValueTypes(ID, N->getVTList());
568 // Add the operand info.
569 AddNodeIDOperands(ID, N->ops());
571 // Handle SDNode leafs with special info.
572 AddNodeIDCustom(ID, N);
575 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
576 /// the CSE map that carries volatility, temporalness, indexing mode, and
577 /// extension/truncation information.
579 static inline unsigned
580 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
581 bool isNonTemporal, bool isInvariant) {
582 assert((ConvType & 3) == ConvType &&
583 "ConvType may not require more than 2 bits!");
584 assert((AM & 7) == AM &&
585 "AM may not require more than 3 bits!");
589 (isNonTemporal << 6) |
593 //===----------------------------------------------------------------------===//
594 // SelectionDAG Class
595 //===----------------------------------------------------------------------===//
597 /// doNotCSE - Return true if CSE should not be performed for this node.
598 static bool doNotCSE(SDNode *N) {
599 if (N->getValueType(0) == MVT::Glue)
600 return true; // Never CSE anything that produces a flag.
602 switch (N->getOpcode()) {
604 case ISD::HANDLENODE:
606 return true; // Never CSE these nodes.
609 // Check that remaining values produced are not flags.
610 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
611 if (N->getValueType(i) == MVT::Glue)
612 return true; // Never CSE anything that produces a flag.
617 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
619 void SelectionDAG::RemoveDeadNodes() {
620 // Create a dummy node (which is not added to allnodes), that adds a reference
621 // to the root node, preventing it from being deleted.
622 HandleSDNode Dummy(getRoot());
624 SmallVector<SDNode*, 128> DeadNodes;
626 // Add all obviously-dead nodes to the DeadNodes worklist.
627 for (SDNode &Node : allnodes())
628 if (Node.use_empty())
629 DeadNodes.push_back(&Node);
631 RemoveDeadNodes(DeadNodes);
633 // If the root changed (e.g. it was a dead load, update the root).
634 setRoot(Dummy.getValue());
637 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
638 /// given list, and any nodes that become unreachable as a result.
639 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
641 // Process the worklist, deleting the nodes and adding their uses to the
643 while (!DeadNodes.empty()) {
644 SDNode *N = DeadNodes.pop_back_val();
646 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
647 DUL->NodeDeleted(N, nullptr);
649 // Take the node out of the appropriate CSE map.
650 RemoveNodeFromCSEMaps(N);
652 // Next, brutally remove the operand list. This is safe to do, as there are
653 // no cycles in the graph.
654 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
656 SDNode *Operand = Use.getNode();
659 // Now that we removed this operand, see if there are no uses of it left.
660 if (Operand->use_empty())
661 DeadNodes.push_back(Operand);
668 void SelectionDAG::RemoveDeadNode(SDNode *N){
669 SmallVector<SDNode*, 16> DeadNodes(1, N);
671 // Create a dummy node that adds a reference to the root node, preventing
672 // it from being deleted. (This matters if the root is an operand of the
674 HandleSDNode Dummy(getRoot());
676 RemoveDeadNodes(DeadNodes);
679 void SelectionDAG::DeleteNode(SDNode *N) {
680 // First take this out of the appropriate CSE map.
681 RemoveNodeFromCSEMaps(N);
683 // Finally, remove uses due to operands of this node, remove from the
684 // AllNodes list, and delete the node.
685 DeleteNodeNotInCSEMaps(N);
688 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
689 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
690 assert(N->use_empty() && "Cannot delete a node that is not dead!");
692 // Drop all of the operands and decrement used node's use counts.
698 void SDDbgInfo::erase(const SDNode *Node) {
699 DbgValMapType::iterator I = DbgValMap.find(Node);
700 if (I == DbgValMap.end())
702 for (auto &Val: I->second)
703 Val->setIsInvalidated();
707 void SelectionDAG::DeallocateNode(SDNode *N) {
708 if (N->OperandsNeedDelete)
709 delete[] N->OperandList;
711 // Set the opcode to DELETED_NODE to help catch bugs when node
712 // memory is reallocated.
713 N->NodeType = ISD::DELETED_NODE;
715 NodeAllocator.Deallocate(AllNodes.remove(N));
717 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
718 // them and forget about that node.
723 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
724 static void VerifySDNode(SDNode *N) {
725 switch (N->getOpcode()) {
728 case ISD::BUILD_PAIR: {
729 EVT VT = N->getValueType(0);
730 assert(N->getNumValues() == 1 && "Too many results!");
731 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
732 "Wrong return type!");
733 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
734 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
735 "Mismatched operand types!");
736 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
737 "Wrong operand type!");
738 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
739 "Wrong return type size");
742 case ISD::BUILD_VECTOR: {
743 assert(N->getNumValues() == 1 && "Too many results!");
744 assert(N->getValueType(0).isVector() && "Wrong return type!");
745 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
746 "Wrong number of operands!");
747 EVT EltVT = N->getValueType(0).getVectorElementType();
748 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
749 assert((I->getValueType() == EltVT ||
750 (EltVT.isInteger() && I->getValueType().isInteger() &&
751 EltVT.bitsLE(I->getValueType()))) &&
752 "Wrong operand type!");
753 assert(I->getValueType() == N->getOperand(0).getValueType() &&
754 "Operands must all have the same type");
762 /// \brief Insert a newly allocated node into the DAG.
764 /// Handles insertion into the all nodes list and CSE map, as well as
765 /// verification and other common operations when a new node is allocated.
766 void SelectionDAG::InsertNode(SDNode *N) {
767 AllNodes.push_back(N);
773 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
774 /// correspond to it. This is useful when we're about to delete or repurpose
775 /// the node. We don't want future request for structurally identical nodes
776 /// to return N anymore.
777 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
779 switch (N->getOpcode()) {
780 case ISD::HANDLENODE: return false; // noop.
782 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
783 "Cond code doesn't exist!");
784 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
785 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
787 case ISD::ExternalSymbol:
788 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
790 case ISD::TargetExternalSymbol: {
791 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
792 Erased = TargetExternalSymbols.erase(
793 std::pair<std::string,unsigned char>(ESN->getSymbol(),
794 ESN->getTargetFlags()));
797 case ISD::MCSymbol: {
798 auto *MCSN = cast<MCSymbolSDNode>(N);
799 Erased = MCSymbols.erase(MCSN->getMCSymbol());
802 case ISD::VALUETYPE: {
803 EVT VT = cast<VTSDNode>(N)->getVT();
804 if (VT.isExtended()) {
805 Erased = ExtendedValueTypeNodes.erase(VT);
807 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
808 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
813 // Remove it from the CSE Map.
814 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
815 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
816 Erased = CSEMap.RemoveNode(N);
820 // Verify that the node was actually in one of the CSE maps, unless it has a
821 // flag result (which cannot be CSE'd) or is one of the special cases that are
822 // not subject to CSE.
823 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
824 !N->isMachineOpcode() && !doNotCSE(N)) {
827 llvm_unreachable("Node is not in map!");
833 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
834 /// maps and modified in place. Add it back to the CSE maps, unless an identical
835 /// node already exists, in which case transfer all its users to the existing
836 /// node. This transfer can potentially trigger recursive merging.
839 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
840 // For node types that aren't CSE'd, just act as if no identical node
843 SDNode *Existing = CSEMap.GetOrInsertNode(N);
845 // If there was already an existing matching node, use ReplaceAllUsesWith
846 // to replace the dead one with the existing one. This can cause
847 // recursive merging of other unrelated nodes down the line.
848 ReplaceAllUsesWith(N, Existing);
850 // N is now dead. Inform the listeners and delete it.
851 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
852 DUL->NodeDeleted(N, Existing);
853 DeleteNodeNotInCSEMaps(N);
858 // If the node doesn't already exist, we updated it. Inform listeners.
859 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
863 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
864 /// were replaced with those specified. If this node is never memoized,
865 /// return null, otherwise return a pointer to the slot it would take. If a
866 /// node already exists with these operands, the slot will be non-null.
867 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
872 SDValue Ops[] = { Op };
874 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
875 AddNodeIDCustom(ID, N);
876 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
880 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
881 /// were replaced with those specified. If this node is never memoized,
882 /// return null, otherwise return a pointer to the slot it would take. If a
883 /// node already exists with these operands, the slot will be non-null.
884 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
885 SDValue Op1, SDValue Op2,
890 SDValue Ops[] = { Op1, Op2 };
892 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
893 AddNodeIDCustom(ID, N);
894 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
899 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
900 /// were replaced with those specified. If this node is never memoized,
901 /// return null, otherwise return a pointer to the slot it would take. If a
902 /// node already exists with these operands, the slot will be non-null.
903 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
909 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
910 AddNodeIDCustom(ID, N);
911 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
915 /// getEVTAlignment - Compute the default alignment value for the
918 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
919 Type *Ty = VT == MVT::iPTR ?
920 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
921 VT.getTypeForEVT(*getContext());
923 return getDataLayout().getABITypeAlignment(Ty);
926 // EntryNode could meaningfully have debug info if we can find it...
927 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
928 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
929 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
930 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
931 UpdateListeners(nullptr) {
932 AllNodes.push_back(&EntryNode);
933 DbgInfo = new SDDbgInfo();
936 void SelectionDAG::init(MachineFunction &mf) {
938 TLI = getSubtarget().getTargetLowering();
939 TSI = getSubtarget().getSelectionDAGInfo();
940 Context = &mf.getFunction()->getContext();
943 SelectionDAG::~SelectionDAG() {
944 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
949 void SelectionDAG::allnodes_clear() {
950 assert(&*AllNodes.begin() == &EntryNode);
951 AllNodes.remove(AllNodes.begin());
952 while (!AllNodes.empty())
953 DeallocateNode(AllNodes.begin());
956 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
957 SDVTList VTs, SDValue N1,
959 const SDNodeFlags *Flags) {
960 if (isBinOpWithFlags(Opcode)) {
961 // If no flags were passed in, use a default flags object.
963 if (Flags == nullptr)
966 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
967 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
972 BinarySDNode *N = new (NodeAllocator)
973 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
977 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
979 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
981 switch (N->getOpcode()) {
984 case ISD::ConstantFP:
985 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
986 "debug location. Use another overload.");
992 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
993 DebugLoc DL, void *&InsertPos) {
994 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
996 switch (N->getOpcode()) {
997 default: break; // Process only regular (non-target) constant nodes.
999 case ISD::ConstantFP:
1000 // Erase debug location from the node if the node is used at several
1001 // different places to do not propagate one location to all uses as it
1002 // leads to incorrect debug info.
1003 if (N->getDebugLoc() != DL)
1004 N->setDebugLoc(DebugLoc());
1011 void SelectionDAG::clear() {
1013 OperandAllocator.Reset();
1016 ExtendedValueTypeNodes.clear();
1017 ExternalSymbols.clear();
1018 TargetExternalSymbols.clear();
1020 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1021 static_cast<CondCodeSDNode*>(nullptr));
1022 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1023 static_cast<SDNode*>(nullptr));
1025 EntryNode.UseList = nullptr;
1026 AllNodes.push_back(&EntryNode);
1027 Root = getEntryNode();
1031 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1032 return VT.bitsGT(Op.getValueType()) ?
1033 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1034 getNode(ISD::TRUNCATE, DL, VT, Op);
1037 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1038 return VT.bitsGT(Op.getValueType()) ?
1039 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1040 getNode(ISD::TRUNCATE, DL, VT, Op);
1043 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1044 return VT.bitsGT(Op.getValueType()) ?
1045 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1046 getNode(ISD::TRUNCATE, DL, VT, Op);
1049 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1051 if (VT.bitsLE(Op.getValueType()))
1052 return getNode(ISD::TRUNCATE, SL, VT, Op);
1054 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1055 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1058 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1059 assert(!VT.isVector() &&
1060 "getZeroExtendInReg should use the vector element type instead of "
1061 "the vector type!");
1062 if (Op.getValueType() == VT) return Op;
1063 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1064 APInt Imm = APInt::getLowBitsSet(BitWidth,
1065 VT.getSizeInBits());
1066 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1067 getConstant(Imm, DL, Op.getValueType()));
1070 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1071 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1072 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1073 "The sizes of the input and result must match in order to perform the "
1074 "extend in-register.");
1075 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1076 "The destination vector type must have fewer lanes than the input.");
1077 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1080 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1081 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1082 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1083 "The sizes of the input and result must match in order to perform the "
1084 "extend in-register.");
1085 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1086 "The destination vector type must have fewer lanes than the input.");
1087 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1090 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1091 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1092 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1093 "The sizes of the input and result must match in order to perform the "
1094 "extend in-register.");
1095 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1096 "The destination vector type must have fewer lanes than the input.");
1097 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1100 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1102 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1103 EVT EltVT = VT.getScalarType();
1105 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1106 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1109 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1110 EVT EltVT = VT.getScalarType();
1112 switch (TLI->getBooleanContents(VT)) {
1113 case TargetLowering::ZeroOrOneBooleanContent:
1114 case TargetLowering::UndefinedBooleanContent:
1115 TrueValue = getConstant(1, DL, VT);
1117 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1118 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1122 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1125 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1127 EVT EltVT = VT.getScalarType();
1128 assert((EltVT.getSizeInBits() >= 64 ||
1129 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1130 "getConstant with a uint64_t value that doesn't fit in the type!");
1131 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1134 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1137 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1140 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1141 bool isT, bool isO) {
1142 assert(VT.isInteger() && "Cannot create FP integer constant!");
1144 EVT EltVT = VT.getScalarType();
1145 const ConstantInt *Elt = &Val;
1147 // In some cases the vector type is legal but the element type is illegal and
1148 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1149 // inserted value (the type does not need to match the vector element type).
1150 // Any extra bits introduced will be truncated away.
1151 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1152 TargetLowering::TypePromoteInteger) {
1153 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1154 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1155 Elt = ConstantInt::get(*getContext(), NewVal);
1157 // In other cases the element type is illegal and needs to be expanded, for
1158 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1159 // the value into n parts and use a vector type with n-times the elements.
1160 // Then bitcast to the type requested.
1161 // Legalizing constants too early makes the DAGCombiner's job harder so we
1162 // only legalize if the DAG tells us we must produce legal types.
1163 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1164 TLI->getTypeAction(*getContext(), EltVT) ==
1165 TargetLowering::TypeExpandInteger) {
1166 APInt NewVal = Elt->getValue();
1167 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1168 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1169 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1170 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1172 // Check the temporary vector is the correct size. If this fails then
1173 // getTypeToTransformTo() probably returned a type whose size (in bits)
1174 // isn't a power-of-2 factor of the requested type size.
1175 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1177 SmallVector<SDValue, 2> EltParts;
1178 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1179 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1180 .trunc(ViaEltSizeInBits), DL,
1181 ViaEltVT, isT, isO));
1184 // EltParts is currently in little endian order. If we actually want
1185 // big-endian order then reverse it now.
1186 if (getDataLayout().isBigEndian())
1187 std::reverse(EltParts.begin(), EltParts.end());
1189 // The elements must be reversed when the element order is different
1190 // to the endianness of the elements (because the BITCAST is itself a
1191 // vector shuffle in this situation). However, we do not need any code to
1192 // perform this reversal because getConstant() is producing a vector
1194 // This situation occurs in MIPS MSA.
1196 SmallVector<SDValue, 8> Ops;
1197 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1198 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1200 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1201 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1206 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1207 "APInt size does not match type size!");
1208 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1209 FoldingSetNodeID ID;
1210 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1214 SDNode *N = nullptr;
1215 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1217 return SDValue(N, 0);
1220 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1222 CSEMap.InsertNode(N, IP);
1226 SDValue Result(N, 0);
1227 if (VT.isVector()) {
1228 SmallVector<SDValue, 8> Ops;
1229 Ops.assign(VT.getVectorNumElements(), Result);
1230 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1235 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1236 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1239 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1241 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1244 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1246 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1248 EVT EltVT = VT.getScalarType();
1250 // Do the map lookup using the actual bit pattern for the floating point
1251 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1252 // we don't have issues with SNANs.
1253 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1254 FoldingSetNodeID ID;
1255 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1258 SDNode *N = nullptr;
1259 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1261 return SDValue(N, 0);
1264 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1266 CSEMap.InsertNode(N, IP);
1270 SDValue Result(N, 0);
1271 if (VT.isVector()) {
1272 SmallVector<SDValue, 8> Ops;
1273 Ops.assign(VT.getVectorNumElements(), Result);
1274 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1279 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1281 EVT EltVT = VT.getScalarType();
1282 if (EltVT==MVT::f32)
1283 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1284 else if (EltVT==MVT::f64)
1285 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1286 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1289 APFloat apf = APFloat(Val);
1290 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1292 return getConstantFP(apf, DL, VT, isTarget);
1294 llvm_unreachable("Unsupported type in getConstantFP");
1297 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1298 EVT VT, int64_t Offset,
1300 unsigned char TargetFlags) {
1301 assert((TargetFlags == 0 || isTargetGA) &&
1302 "Cannot set target flags on target-independent globals");
1304 // Truncate (with sign-extension) the offset value to the pointer size.
1305 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1307 Offset = SignExtend64(Offset, BitWidth);
1310 if (GV->isThreadLocal())
1311 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1313 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1315 FoldingSetNodeID ID;
1316 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1318 ID.AddInteger(Offset);
1319 ID.AddInteger(TargetFlags);
1320 ID.AddInteger(GV->getType()->getAddressSpace());
1322 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1326 DL.getDebugLoc(), GV, VT,
1327 Offset, TargetFlags);
1328 CSEMap.InsertNode(N, IP);
1330 return SDValue(N, 0);
1333 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1334 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1335 FoldingSetNodeID ID;
1336 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1339 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1340 return SDValue(E, 0);
1342 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1343 CSEMap.InsertNode(N, IP);
1345 return SDValue(N, 0);
1348 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1349 unsigned char TargetFlags) {
1350 assert((TargetFlags == 0 || isTarget) &&
1351 "Cannot set target flags on target-independent jump tables");
1352 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1353 FoldingSetNodeID ID;
1354 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1356 ID.AddInteger(TargetFlags);
1358 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1359 return SDValue(E, 0);
1361 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1363 CSEMap.InsertNode(N, IP);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1369 unsigned Alignment, int Offset,
1371 unsigned char TargetFlags) {
1372 assert((TargetFlags == 0 || isTarget) &&
1373 "Cannot set target flags on target-independent globals");
1375 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1376 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1377 FoldingSetNodeID ID;
1378 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1379 ID.AddInteger(Alignment);
1380 ID.AddInteger(Offset);
1382 ID.AddInteger(TargetFlags);
1384 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1385 return SDValue(E, 0);
1387 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1388 Alignment, TargetFlags);
1389 CSEMap.InsertNode(N, IP);
1391 return SDValue(N, 0);
1395 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1396 unsigned Alignment, int Offset,
1398 unsigned char TargetFlags) {
1399 assert((TargetFlags == 0 || isTarget) &&
1400 "Cannot set target flags on target-independent globals");
1402 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1403 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1404 FoldingSetNodeID ID;
1405 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1406 ID.AddInteger(Alignment);
1407 ID.AddInteger(Offset);
1408 C->addSelectionDAGCSEId(ID);
1409 ID.AddInteger(TargetFlags);
1411 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1412 return SDValue(E, 0);
1414 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1415 Alignment, TargetFlags);
1416 CSEMap.InsertNode(N, IP);
1418 return SDValue(N, 0);
1421 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1422 unsigned char TargetFlags) {
1423 FoldingSetNodeID ID;
1424 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1425 ID.AddInteger(Index);
1426 ID.AddInteger(Offset);
1427 ID.AddInteger(TargetFlags);
1429 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1430 return SDValue(E, 0);
1432 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1434 CSEMap.InsertNode(N, IP);
1436 return SDValue(N, 0);
1439 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1440 FoldingSetNodeID ID;
1441 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1444 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1445 return SDValue(E, 0);
1447 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1448 CSEMap.InsertNode(N, IP);
1450 return SDValue(N, 0);
1453 SDValue SelectionDAG::getValueType(EVT VT) {
1454 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1455 ValueTypeNodes.size())
1456 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1458 SDNode *&N = VT.isExtended() ?
1459 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1461 if (N) return SDValue(N, 0);
1462 N = new (NodeAllocator) VTSDNode(VT);
1464 return SDValue(N, 0);
1467 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1468 SDNode *&N = ExternalSymbols[Sym];
1469 if (N) return SDValue(N, 0);
1470 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1472 return SDValue(N, 0);
1475 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1476 SDNode *&N = MCSymbols[Sym];
1478 return SDValue(N, 0);
1479 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1481 return SDValue(N, 0);
1484 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1485 unsigned char TargetFlags) {
1487 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1489 if (N) return SDValue(N, 0);
1490 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1492 return SDValue(N, 0);
1495 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1496 if ((unsigned)Cond >= CondCodeNodes.size())
1497 CondCodeNodes.resize(Cond+1);
1499 if (!CondCodeNodes[Cond]) {
1500 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1501 CondCodeNodes[Cond] = N;
1505 return SDValue(CondCodeNodes[Cond], 0);
1508 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1509 // the shuffle mask M that point at N1 to point at N2, and indices that point
1510 // N2 to point at N1.
1511 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1513 ShuffleVectorSDNode::commuteMask(M);
1516 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1517 SDValue N2, const int *Mask) {
1518 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1519 "Invalid VECTOR_SHUFFLE");
1521 // Canonicalize shuffle undef, undef -> undef
1522 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1523 return getUNDEF(VT);
1525 // Validate that all indices in Mask are within the range of the elements
1526 // input to the shuffle.
1527 unsigned NElts = VT.getVectorNumElements();
1528 SmallVector<int, 8> MaskVec;
1529 for (unsigned i = 0; i != NElts; ++i) {
1530 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1531 MaskVec.push_back(Mask[i]);
1534 // Canonicalize shuffle v, v -> v, undef
1537 for (unsigned i = 0; i != NElts; ++i)
1538 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1541 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1542 if (N1.getOpcode() == ISD::UNDEF)
1543 commuteShuffle(N1, N2, MaskVec);
1545 // If shuffling a splat, try to blend the splat instead. We do this here so
1546 // that even when this arises during lowering we don't have to re-handle it.
1547 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1548 BitVector UndefElements;
1549 SDValue Splat = BV->getSplatValue(&UndefElements);
1553 for (int i = 0; i < (int)NElts; ++i) {
1554 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1557 // If this input comes from undef, mark it as such.
1558 if (UndefElements[MaskVec[i] - Offset]) {
1563 // If we can blend a non-undef lane, use that instead.
1564 if (!UndefElements[i])
1565 MaskVec[i] = i + Offset;
1568 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1569 BlendSplat(N1BV, 0);
1570 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1571 BlendSplat(N2BV, NElts);
1573 // Canonicalize all index into lhs, -> shuffle lhs, undef
1574 // Canonicalize all index into rhs, -> shuffle rhs, undef
1575 bool AllLHS = true, AllRHS = true;
1576 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1577 for (unsigned i = 0; i != NElts; ++i) {
1578 if (MaskVec[i] >= (int)NElts) {
1583 } else if (MaskVec[i] >= 0) {
1587 if (AllLHS && AllRHS)
1588 return getUNDEF(VT);
1589 if (AllLHS && !N2Undef)
1593 commuteShuffle(N1, N2, MaskVec);
1595 // Reset our undef status after accounting for the mask.
1596 N2Undef = N2.getOpcode() == ISD::UNDEF;
1597 // Re-check whether both sides ended up undef.
1598 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1599 return getUNDEF(VT);
1601 // If Identity shuffle return that node.
1602 bool Identity = true, AllSame = true;
1603 for (unsigned i = 0; i != NElts; ++i) {
1604 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1605 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1607 if (Identity && NElts)
1610 // Shuffling a constant splat doesn't change the result.
1614 // Look through any bitcasts. We check that these don't change the number
1615 // (and size) of elements and just changes their types.
1616 while (V.getOpcode() == ISD::BITCAST)
1617 V = V->getOperand(0);
1619 // A splat should always show up as a build vector node.
1620 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1621 BitVector UndefElements;
1622 SDValue Splat = BV->getSplatValue(&UndefElements);
1623 // If this is a splat of an undef, shuffling it is also undef.
1624 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1625 return getUNDEF(VT);
1628 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1630 // We only have a splat which can skip shuffles if there is a splatted
1631 // value and no undef lanes rearranged by the shuffle.
1632 if (Splat && UndefElements.none()) {
1633 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1634 // number of elements match or the value splatted is a zero constant.
1637 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1638 if (C->isNullValue())
1642 // If the shuffle itself creates a splat, build the vector directly.
1643 if (AllSame && SameNumElts) {
1644 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1645 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1647 EVT BuildVT = BV->getValueType(0);
1648 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1650 // We may have jumped through bitcasts, so the type of the
1651 // BUILD_VECTOR may not match the type of the shuffle.
1653 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1659 FoldingSetNodeID ID;
1660 SDValue Ops[2] = { N1, N2 };
1661 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1662 for (unsigned i = 0; i != NElts; ++i)
1663 ID.AddInteger(MaskVec[i]);
1666 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1667 return SDValue(E, 0);
1669 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1670 // SDNode doesn't have access to it. This memory will be "leaked" when
1671 // the node is deallocated, but recovered when the NodeAllocator is released.
1672 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1673 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1675 ShuffleVectorSDNode *N =
1676 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1677 dl.getDebugLoc(), N1, N2,
1679 CSEMap.InsertNode(N, IP);
1681 return SDValue(N, 0);
1684 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1685 MVT VT = SV.getSimpleValueType(0);
1686 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1687 ShuffleVectorSDNode::commuteMask(MaskVec);
1689 SDValue Op0 = SV.getOperand(0);
1690 SDValue Op1 = SV.getOperand(1);
1691 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1694 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1695 SDValue Val, SDValue DTy,
1696 SDValue STy, SDValue Rnd, SDValue Sat,
1697 ISD::CvtCode Code) {
1698 // If the src and dest types are the same and the conversion is between
1699 // integer types of the same sign or two floats, no conversion is necessary.
1701 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1704 FoldingSetNodeID ID;
1705 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1706 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1708 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1709 return SDValue(E, 0);
1711 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1714 CSEMap.InsertNode(N, IP);
1716 return SDValue(N, 0);
1719 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1720 FoldingSetNodeID ID;
1721 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1722 ID.AddInteger(RegNo);
1724 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1725 return SDValue(E, 0);
1727 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1728 CSEMap.InsertNode(N, IP);
1730 return SDValue(N, 0);
1733 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1734 FoldingSetNodeID ID;
1735 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1736 ID.AddPointer(RegMask);
1738 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1739 return SDValue(E, 0);
1741 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1742 CSEMap.InsertNode(N, IP);
1744 return SDValue(N, 0);
1747 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1748 FoldingSetNodeID ID;
1749 SDValue Ops[] = { Root };
1750 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1751 ID.AddPointer(Label);
1753 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1754 return SDValue(E, 0);
1756 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1757 dl.getDebugLoc(), Root, Label);
1758 CSEMap.InsertNode(N, IP);
1760 return SDValue(N, 0);
1764 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1767 unsigned char TargetFlags) {
1768 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1770 FoldingSetNodeID ID;
1771 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1773 ID.AddInteger(Offset);
1774 ID.AddInteger(TargetFlags);
1776 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1777 return SDValue(E, 0);
1779 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1781 CSEMap.InsertNode(N, IP);
1783 return SDValue(N, 0);
1786 SDValue SelectionDAG::getSrcValue(const Value *V) {
1787 assert((!V || V->getType()->isPointerTy()) &&
1788 "SrcValue is not a pointer?");
1790 FoldingSetNodeID ID;
1791 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1795 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1796 return SDValue(E, 0);
1798 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1799 CSEMap.InsertNode(N, IP);
1801 return SDValue(N, 0);
1804 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1805 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1806 FoldingSetNodeID ID;
1807 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1811 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1812 return SDValue(E, 0);
1814 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1815 CSEMap.InsertNode(N, IP);
1817 return SDValue(N, 0);
1820 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1821 if (VT == V.getValueType())
1824 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1827 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1828 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1829 unsigned SrcAS, unsigned DestAS) {
1830 SDValue Ops[] = {Ptr};
1831 FoldingSetNodeID ID;
1832 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1833 ID.AddInteger(SrcAS);
1834 ID.AddInteger(DestAS);
1837 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1838 return SDValue(E, 0);
1840 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1842 VT, Ptr, SrcAS, DestAS);
1843 CSEMap.InsertNode(N, IP);
1845 return SDValue(N, 0);
1848 /// getShiftAmountOperand - Return the specified value casted to
1849 /// the target's desired shift amount type.
1850 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1851 EVT OpTy = Op.getValueType();
1852 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1853 if (OpTy == ShTy || OpTy.isVector()) return Op;
1855 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1856 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1859 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1860 /// specified value type.
1861 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1862 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1863 unsigned ByteSize = VT.getStoreSize();
1864 Type *Ty = VT.getTypeForEVT(*getContext());
1865 unsigned StackAlign =
1866 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1868 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1869 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1872 /// CreateStackTemporary - Create a stack temporary suitable for holding
1873 /// either of the specified value types.
1874 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1875 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1876 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1877 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1878 const DataLayout &DL = getDataLayout();
1880 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1882 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1883 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1884 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1887 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1888 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1889 // These setcc operations always fold.
1893 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1895 case ISD::SETTRUE2: {
1896 TargetLowering::BooleanContent Cnt =
1897 TLI->getBooleanContents(N1->getValueType(0));
1899 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1913 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1917 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1918 const APInt &C2 = N2C->getAPIntValue();
1919 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1920 const APInt &C1 = N1C->getAPIntValue();
1923 default: llvm_unreachable("Unknown integer setcc!");
1924 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1925 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1926 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1927 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1928 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1929 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1930 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1931 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1932 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1933 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1937 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1938 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1939 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1942 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1943 return getUNDEF(VT);
1945 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1946 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1947 return getUNDEF(VT);
1949 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1950 R==APFloat::cmpLessThan, dl, VT);
1951 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1952 return getUNDEF(VT);
1954 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1955 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1956 return getUNDEF(VT);
1958 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1959 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1960 return getUNDEF(VT);
1962 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1963 R==APFloat::cmpEqual, dl, VT);
1964 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1965 return getUNDEF(VT);
1967 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1968 R==APFloat::cmpEqual, dl, VT);
1969 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1970 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1971 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1972 R==APFloat::cmpEqual, dl, VT);
1973 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1974 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1975 R==APFloat::cmpLessThan, dl, VT);
1976 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1977 R==APFloat::cmpUnordered, dl, VT);
1978 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1979 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1982 // Ensure that the constant occurs on the RHS.
1983 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1984 MVT CompVT = N1.getValueType().getSimpleVT();
1985 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1988 return getSetCC(dl, VT, N2, N1, SwappedCond);
1992 // Could not fold it.
1996 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1997 /// use this predicate to simplify operations downstream.
1998 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1999 // This predicate is not safe for vector operations.
2000 if (Op.getValueType().isVector())
2003 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2004 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2007 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2008 /// this predicate to simplify operations downstream. Mask is known to be zero
2009 /// for bits that V cannot have.
2010 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2011 unsigned Depth) const {
2012 APInt KnownZero, KnownOne;
2013 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2014 return (KnownZero & Mask) == Mask;
2017 /// Determine which bits of Op are known to be either zero or one and return
2018 /// them in the KnownZero/KnownOne bitsets.
2019 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2020 APInt &KnownOne, unsigned Depth) const {
2021 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2023 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2025 return; // Limit search depth.
2027 APInt KnownZero2, KnownOne2;
2029 switch (Op.getOpcode()) {
2031 // We know all of the bits for a constant!
2032 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2033 KnownZero = ~KnownOne;
2036 // If either the LHS or the RHS are Zero, the result is zero.
2037 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2038 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2040 // Output known-1 bits are only known if set in both the LHS & RHS.
2041 KnownOne &= KnownOne2;
2042 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2043 KnownZero |= KnownZero2;
2046 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2047 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2049 // Output known-0 bits are only known if clear in both the LHS & RHS.
2050 KnownZero &= KnownZero2;
2051 // Output known-1 are known to be set if set in either the LHS | RHS.
2052 KnownOne |= KnownOne2;
2055 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2056 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2058 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2059 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2060 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2061 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2062 KnownZero = KnownZeroOut;
2066 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2067 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2069 // If low bits are zero in either operand, output low known-0 bits.
2070 // Also compute a conserative estimate for high known-0 bits.
2071 // More trickiness is possible, but this is sufficient for the
2072 // interesting case of alignment computation.
2073 KnownOne.clearAllBits();
2074 unsigned TrailZ = KnownZero.countTrailingOnes() +
2075 KnownZero2.countTrailingOnes();
2076 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2077 KnownZero2.countLeadingOnes(),
2078 BitWidth) - BitWidth;
2080 TrailZ = std::min(TrailZ, BitWidth);
2081 LeadZ = std::min(LeadZ, BitWidth);
2082 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2083 APInt::getHighBitsSet(BitWidth, LeadZ);
2087 // For the purposes of computing leading zeros we can conservatively
2088 // treat a udiv as a logical right shift by the power of 2 known to
2089 // be less than the denominator.
2090 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2091 unsigned LeadZ = KnownZero2.countLeadingOnes();
2093 KnownOne2.clearAllBits();
2094 KnownZero2.clearAllBits();
2095 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2096 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2097 if (RHSUnknownLeadingOnes != BitWidth)
2098 LeadZ = std::min(BitWidth,
2099 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2101 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2105 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2106 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2108 // Only known if known in both the LHS and RHS.
2109 KnownOne &= KnownOne2;
2110 KnownZero &= KnownZero2;
2112 case ISD::SELECT_CC:
2113 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2114 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2116 // Only known if known in both the LHS and RHS.
2117 KnownOne &= KnownOne2;
2118 KnownZero &= KnownZero2;
2126 if (Op.getResNo() != 1)
2128 // The boolean result conforms to getBooleanContents.
2129 // If we know the result of a setcc has the top bits zero, use this info.
2130 // We know that we have an integer-based boolean since these operations
2131 // are only available for integer.
2132 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2133 TargetLowering::ZeroOrOneBooleanContent &&
2135 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2138 // If we know the result of a setcc has the top bits zero, use this info.
2139 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2140 TargetLowering::ZeroOrOneBooleanContent &&
2142 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2145 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2146 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2147 unsigned ShAmt = SA->getZExtValue();
2149 // If the shift count is an invalid immediate, don't do anything.
2150 if (ShAmt >= BitWidth)
2153 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2154 KnownZero <<= ShAmt;
2156 // low bits known zero.
2157 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2161 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2162 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2163 unsigned ShAmt = SA->getZExtValue();
2165 // If the shift count is an invalid immediate, don't do anything.
2166 if (ShAmt >= BitWidth)
2169 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2170 KnownZero = KnownZero.lshr(ShAmt);
2171 KnownOne = KnownOne.lshr(ShAmt);
2173 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2174 KnownZero |= HighBits; // High bits known zero.
2178 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2179 unsigned ShAmt = SA->getZExtValue();
2181 // If the shift count is an invalid immediate, don't do anything.
2182 if (ShAmt >= BitWidth)
2185 // If any of the demanded bits are produced by the sign extension, we also
2186 // demand the input sign bit.
2187 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2189 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2190 KnownZero = KnownZero.lshr(ShAmt);
2191 KnownOne = KnownOne.lshr(ShAmt);
2193 // Handle the sign bits.
2194 APInt SignBit = APInt::getSignBit(BitWidth);
2195 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2197 if (KnownZero.intersects(SignBit)) {
2198 KnownZero |= HighBits; // New bits are known zero.
2199 } else if (KnownOne.intersects(SignBit)) {
2200 KnownOne |= HighBits; // New bits are known one.
2204 case ISD::SIGN_EXTEND_INREG: {
2205 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2206 unsigned EBits = EVT.getScalarType().getSizeInBits();
2208 // Sign extension. Compute the demanded bits in the result that are not
2209 // present in the input.
2210 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2212 APInt InSignBit = APInt::getSignBit(EBits);
2213 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2215 // If the sign extended bits are demanded, we know that the sign
2217 InSignBit = InSignBit.zext(BitWidth);
2218 if (NewBits.getBoolValue())
2219 InputDemandedBits |= InSignBit;
2221 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2222 KnownOne &= InputDemandedBits;
2223 KnownZero &= InputDemandedBits;
2225 // If the sign bit of the input is known set or clear, then we know the
2226 // top bits of the result.
2227 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2228 KnownZero |= NewBits;
2229 KnownOne &= ~NewBits;
2230 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2231 KnownOne |= NewBits;
2232 KnownZero &= ~NewBits;
2233 } else { // Input sign bit unknown
2234 KnownZero &= ~NewBits;
2235 KnownOne &= ~NewBits;
2240 case ISD::CTTZ_ZERO_UNDEF:
2242 case ISD::CTLZ_ZERO_UNDEF:
2244 unsigned LowBits = Log2_32(BitWidth)+1;
2245 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2246 KnownOne.clearAllBits();
2250 LoadSDNode *LD = cast<LoadSDNode>(Op);
2251 // If this is a ZEXTLoad and we are looking at the loaded value.
2252 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2253 EVT VT = LD->getMemoryVT();
2254 unsigned MemBits = VT.getScalarType().getSizeInBits();
2255 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2256 } else if (const MDNode *Ranges = LD->getRanges()) {
2257 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2261 case ISD::ZERO_EXTEND: {
2262 EVT InVT = Op.getOperand(0).getValueType();
2263 unsigned InBits = InVT.getScalarType().getSizeInBits();
2264 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2265 KnownZero = KnownZero.trunc(InBits);
2266 KnownOne = KnownOne.trunc(InBits);
2267 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2268 KnownZero = KnownZero.zext(BitWidth);
2269 KnownOne = KnownOne.zext(BitWidth);
2270 KnownZero |= NewBits;
2273 case ISD::SIGN_EXTEND: {
2274 EVT InVT = Op.getOperand(0).getValueType();
2275 unsigned InBits = InVT.getScalarType().getSizeInBits();
2276 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2278 KnownZero = KnownZero.trunc(InBits);
2279 KnownOne = KnownOne.trunc(InBits);
2280 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2282 // Note if the sign bit is known to be zero or one.
2283 bool SignBitKnownZero = KnownZero.isNegative();
2284 bool SignBitKnownOne = KnownOne.isNegative();
2286 KnownZero = KnownZero.zext(BitWidth);
2287 KnownOne = KnownOne.zext(BitWidth);
2289 // If the sign bit is known zero or one, the top bits match.
2290 if (SignBitKnownZero)
2291 KnownZero |= NewBits;
2292 else if (SignBitKnownOne)
2293 KnownOne |= NewBits;
2296 case ISD::ANY_EXTEND: {
2297 EVT InVT = Op.getOperand(0).getValueType();
2298 unsigned InBits = InVT.getScalarType().getSizeInBits();
2299 KnownZero = KnownZero.trunc(InBits);
2300 KnownOne = KnownOne.trunc(InBits);
2301 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2302 KnownZero = KnownZero.zext(BitWidth);
2303 KnownOne = KnownOne.zext(BitWidth);
2306 case ISD::TRUNCATE: {
2307 EVT InVT = Op.getOperand(0).getValueType();
2308 unsigned InBits = InVT.getScalarType().getSizeInBits();
2309 KnownZero = KnownZero.zext(InBits);
2310 KnownOne = KnownOne.zext(InBits);
2311 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2312 KnownZero = KnownZero.trunc(BitWidth);
2313 KnownOne = KnownOne.trunc(BitWidth);
2316 case ISD::AssertZext: {
2317 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2318 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2319 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2320 KnownZero |= (~InMask);
2321 KnownOne &= (~KnownZero);
2325 // All bits are zero except the low bit.
2326 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2330 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2331 // We know that the top bits of C-X are clear if X contains less bits
2332 // than C (i.e. no wrap-around can happen). For example, 20-X is
2333 // positive if we can prove that X is >= 0 and < 16.
2334 if (CLHS->getAPIntValue().isNonNegative()) {
2335 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2336 // NLZ can't be BitWidth with no sign bit
2337 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2338 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2340 // If all of the MaskV bits are known to be zero, then we know the
2341 // output top bits are zero, because we now know that the output is
2343 if ((KnownZero2 & MaskV) == MaskV) {
2344 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2345 // Top bits known zero.
2346 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2354 // Output known-0 bits are known if clear or set in both the low clear bits
2355 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2356 // low 3 bits clear.
2357 // Output known-0 bits are also known if the top bits of each input are
2358 // known to be clear. For example, if one input has the top 10 bits clear
2359 // and the other has the top 8 bits clear, we know the top 7 bits of the
2360 // output must be clear.
2361 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2362 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2363 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2365 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2366 KnownZeroHigh = std::min(KnownZeroHigh,
2367 KnownZero2.countLeadingOnes());
2368 KnownZeroLow = std::min(KnownZeroLow,
2369 KnownZero2.countTrailingOnes());
2371 if (Op.getOpcode() == ISD::ADD) {
2372 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2373 if (KnownZeroHigh > 1)
2374 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2378 // With ADDE, a carry bit may be added in, so we can only use this
2379 // information if we know (at least) that the low two bits are clear. We
2380 // then return to the caller that the low bit is unknown but that other bits
2382 if (KnownZeroLow >= 2) // ADDE
2383 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2387 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2388 const APInt &RA = Rem->getAPIntValue().abs();
2389 if (RA.isPowerOf2()) {
2390 APInt LowBits = RA - 1;
2391 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2393 // The low bits of the first operand are unchanged by the srem.
2394 KnownZero = KnownZero2 & LowBits;
2395 KnownOne = KnownOne2 & LowBits;
2397 // If the first operand is non-negative or has all low bits zero, then
2398 // the upper bits are all zero.
2399 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2400 KnownZero |= ~LowBits;
2402 // If the first operand is negative and not all low bits are zero, then
2403 // the upper bits are all one.
2404 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2405 KnownOne |= ~LowBits;
2406 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2411 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2412 const APInt &RA = Rem->getAPIntValue();
2413 if (RA.isPowerOf2()) {
2414 APInt LowBits = (RA - 1);
2415 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2417 // The upper bits are all zero, the lower ones are unchanged.
2418 KnownZero = KnownZero2 | ~LowBits;
2419 KnownOne = KnownOne2 & LowBits;
2424 // Since the result is less than or equal to either operand, any leading
2425 // zero bits in either operand must also exist in the result.
2426 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2427 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2429 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2430 KnownZero2.countLeadingOnes());
2431 KnownOne.clearAllBits();
2432 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2435 case ISD::EXTRACT_ELEMENT: {
2436 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2437 const unsigned Index =
2438 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2439 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2441 // Remove low part of known bits mask
2442 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2443 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2445 // Remove high part of known bit mask
2446 KnownZero = KnownZero.trunc(BitWidth);
2447 KnownOne = KnownOne.trunc(BitWidth);
2454 APInt Op0Zero, Op0One;
2455 APInt Op1Zero, Op1One;
2456 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2457 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2459 KnownZero = Op0Zero & Op1Zero;
2460 KnownOne = Op0One & Op1One;
2463 case ISD::FrameIndex:
2464 case ISD::TargetFrameIndex:
2465 if (unsigned Align = InferPtrAlignment(Op)) {
2466 // The low bits are known zero if the pointer is aligned.
2467 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2473 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2476 case ISD::INTRINSIC_WO_CHAIN:
2477 case ISD::INTRINSIC_W_CHAIN:
2478 case ISD::INTRINSIC_VOID:
2479 // Allow the target to implement this method for its nodes.
2480 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2484 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2487 /// ComputeNumSignBits - Return the number of times the sign bit of the
2488 /// register is replicated into the other bits. We know that at least 1 bit
2489 /// is always equal to the sign bit (itself), but other cases can give us
2490 /// information. For example, immediately after an "SRA X, 2", we know that
2491 /// the top 3 bits are all equal to each other, so we return 3.
2492 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2493 EVT VT = Op.getValueType();
2494 assert(VT.isInteger() && "Invalid VT!");
2495 unsigned VTBits = VT.getScalarType().getSizeInBits();
2497 unsigned FirstAnswer = 1;
2500 return 1; // Limit search depth.
2502 switch (Op.getOpcode()) {
2504 case ISD::AssertSext:
2505 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2506 return VTBits-Tmp+1;
2507 case ISD::AssertZext:
2508 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2511 case ISD::Constant: {
2512 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2513 return Val.getNumSignBits();
2516 case ISD::SIGN_EXTEND:
2518 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2519 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2521 case ISD::SIGN_EXTEND_INREG:
2522 // Max of the input and what this extends.
2524 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2527 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2528 return std::max(Tmp, Tmp2);
2531 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2532 // SRA X, C -> adds C sign bits.
2533 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2534 Tmp += C->getZExtValue();
2535 if (Tmp > VTBits) Tmp = VTBits;
2539 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2540 // shl destroys sign bits.
2541 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2542 if (C->getZExtValue() >= VTBits || // Bad shift.
2543 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2544 return Tmp - C->getZExtValue();
2549 case ISD::XOR: // NOT is handled here.
2550 // Logical binary ops preserve the number of sign bits at the worst.
2551 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2553 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2554 FirstAnswer = std::min(Tmp, Tmp2);
2555 // We computed what we know about the sign bits as our first
2556 // answer. Now proceed to the generic code that uses
2557 // computeKnownBits, and pick whichever answer is better.
2562 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2563 if (Tmp == 1) return 1; // Early out.
2564 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2565 return std::min(Tmp, Tmp2);
2570 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2572 return 1; // Early out.
2573 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2574 return std::min(Tmp, Tmp2);
2581 if (Op.getResNo() != 1)
2583 // The boolean result conforms to getBooleanContents. Fall through.
2584 // If setcc returns 0/-1, all bits are sign bits.
2585 // We know that we have an integer-based boolean since these operations
2586 // are only available for integer.
2587 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2588 TargetLowering::ZeroOrNegativeOneBooleanContent)
2592 // If setcc returns 0/-1, all bits are sign bits.
2593 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2594 TargetLowering::ZeroOrNegativeOneBooleanContent)
2599 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2600 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2602 // Handle rotate right by N like a rotate left by 32-N.
2603 if (Op.getOpcode() == ISD::ROTR)
2604 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2606 // If we aren't rotating out all of the known-in sign bits, return the
2607 // number that are left. This handles rotl(sext(x), 1) for example.
2608 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2609 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2613 // Add can have at most one carry bit. Thus we know that the output
2614 // is, at worst, one more bit than the inputs.
2615 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2616 if (Tmp == 1) return 1; // Early out.
2618 // Special case decrementing a value (ADD X, -1):
2619 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2620 if (CRHS->isAllOnesValue()) {
2621 APInt KnownZero, KnownOne;
2622 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2624 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2626 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2629 // If we are subtracting one from a positive number, there is no carry
2630 // out of the result.
2631 if (KnownZero.isNegative())
2635 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2636 if (Tmp2 == 1) return 1;
2637 return std::min(Tmp, Tmp2)-1;
2640 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2641 if (Tmp2 == 1) return 1;
2644 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2645 if (CLHS->isNullValue()) {
2646 APInt KnownZero, KnownOne;
2647 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2648 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2650 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2653 // If the input is known to be positive (the sign bit is known clear),
2654 // the output of the NEG has the same number of sign bits as the input.
2655 if (KnownZero.isNegative())
2658 // Otherwise, we treat this like a SUB.
2661 // Sub can have at most one carry bit. Thus we know that the output
2662 // is, at worst, one more bit than the inputs.
2663 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2664 if (Tmp == 1) return 1; // Early out.
2665 return std::min(Tmp, Tmp2)-1;
2667 // FIXME: it's tricky to do anything useful for this, but it is an important
2668 // case for targets like X86.
2670 case ISD::EXTRACT_ELEMENT: {
2671 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2672 const int BitWidth = Op.getValueType().getSizeInBits();
2674 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2676 // Get reverse index (starting from 1), Op1 value indexes elements from
2677 // little end. Sign starts at big end.
2678 const int rIndex = Items - 1 -
2679 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2681 // If the sign portion ends in our element the substraction gives correct
2682 // result. Otherwise it gives either negative or > bitwidth result
2683 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2687 // If we are looking at the loaded value of the SDNode.
2688 if (Op.getResNo() == 0) {
2689 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2690 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2691 unsigned ExtType = LD->getExtensionType();
2694 case ISD::SEXTLOAD: // '17' bits known
2695 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2696 return VTBits-Tmp+1;
2697 case ISD::ZEXTLOAD: // '16' bits known
2698 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2704 // Allow the target to implement this method for its nodes.
2705 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2706 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2707 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2708 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2709 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2710 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2713 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2714 // use this information.
2715 APInt KnownZero, KnownOne;
2716 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2719 if (KnownZero.isNegative()) { // sign bit is 0
2721 } else if (KnownOne.isNegative()) { // sign bit is 1;
2728 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2729 // the number of identical bits in the top of the input value.
2731 Mask <<= Mask.getBitWidth()-VTBits;
2732 // Return # leading zeros. We use 'min' here in case Val was zero before
2733 // shifting. We don't want to return '64' as for an i32 "0".
2734 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2737 /// isBaseWithConstantOffset - Return true if the specified operand is an
2738 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2739 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2740 /// semantics as an ADD. This handles the equivalence:
2741 /// X|Cst == X+Cst iff X&Cst = 0.
2742 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2743 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2744 !isa<ConstantSDNode>(Op.getOperand(1)))
2747 if (Op.getOpcode() == ISD::OR &&
2748 !MaskedValueIsZero(Op.getOperand(0),
2749 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2756 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2757 // If we're told that NaNs won't happen, assume they won't.
2758 if (getTarget().Options.NoNaNsFPMath)
2761 // If the value is a constant, we can obviously see if it is a NaN or not.
2762 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2763 return !C->getValueAPF().isNaN();
2765 // TODO: Recognize more cases here.
2770 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2771 // If the value is a constant, we can obviously see if it is a zero or not.
2772 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2773 return !C->isZero();
2775 // TODO: Recognize more cases here.
2776 switch (Op.getOpcode()) {
2779 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2780 return !C->isNullValue();
2787 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2788 // Check the obvious case.
2789 if (A == B) return true;
2791 // For for negative and positive zero.
2792 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2793 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2794 if (CA->isZero() && CB->isZero()) return true;
2796 // Otherwise they may not be equal.
2800 /// getNode - Gets or creates the specified node.
2802 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2803 FoldingSetNodeID ID;
2804 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2806 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2807 return SDValue(E, 0);
2809 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2810 DL.getDebugLoc(), getVTList(VT));
2811 CSEMap.InsertNode(N, IP);
2814 return SDValue(N, 0);
2817 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2818 EVT VT, SDValue Operand) {
2819 // Constant fold unary operations with an integer constant operand. Even
2820 // opaque constant will be folded, because the folding of unary operations
2821 // doesn't create new constants with different values. Nevertheless, the
2822 // opaque flag is preserved during folding to prevent future folding with
2824 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2825 const APInt &Val = C->getAPIntValue();
2828 case ISD::SIGN_EXTEND:
2829 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2830 C->isTargetOpcode(), C->isOpaque());
2831 case ISD::ANY_EXTEND:
2832 case ISD::ZERO_EXTEND:
2834 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2835 C->isTargetOpcode(), C->isOpaque());
2836 case ISD::UINT_TO_FP:
2837 case ISD::SINT_TO_FP: {
2838 APFloat apf(EVTToAPFloatSemantics(VT),
2839 APInt::getNullValue(VT.getSizeInBits()));
2840 (void)apf.convertFromAPInt(Val,
2841 Opcode==ISD::SINT_TO_FP,
2842 APFloat::rmNearestTiesToEven);
2843 return getConstantFP(apf, DL, VT);
2846 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2847 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2848 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2849 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2850 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2851 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2854 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2857 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2860 case ISD::CTLZ_ZERO_UNDEF:
2861 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2864 case ISD::CTTZ_ZERO_UNDEF:
2865 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2870 // Constant fold unary operations with a floating point constant operand.
2871 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2872 APFloat V = C->getValueAPF(); // make copy
2876 return getConstantFP(V, DL, VT);
2879 return getConstantFP(V, DL, VT);
2881 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2882 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2883 return getConstantFP(V, DL, VT);
2887 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2888 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2889 return getConstantFP(V, DL, VT);
2893 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2894 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2895 return getConstantFP(V, DL, VT);
2898 case ISD::FP_EXTEND: {
2900 // This can return overflow, underflow, or inexact; we don't care.
2901 // FIXME need to be more flexible about rounding mode.
2902 (void)V.convert(EVTToAPFloatSemantics(VT),
2903 APFloat::rmNearestTiesToEven, &ignored);
2904 return getConstantFP(V, DL, VT);
2906 case ISD::FP_TO_SINT:
2907 case ISD::FP_TO_UINT: {
2910 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2911 // FIXME need to be more flexible about rounding mode.
2912 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2913 Opcode==ISD::FP_TO_SINT,
2914 APFloat::rmTowardZero, &ignored);
2915 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2917 APInt api(VT.getSizeInBits(), x);
2918 return getConstant(api, DL, VT);
2921 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2922 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2923 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2924 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2925 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2926 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2931 // Constant fold unary operations with a vector integer or float operand.
2932 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2933 if (BV->isConstant()) {
2936 // FIXME: Entirely reasonable to perform folding of other unary
2937 // operations here as the need arises.
2944 case ISD::FP_EXTEND:
2945 case ISD::FP_TO_SINT:
2946 case ISD::FP_TO_UINT:
2948 case ISD::UINT_TO_FP:
2949 case ISD::SINT_TO_FP:
2952 case ISD::CTLZ_ZERO_UNDEF:
2954 case ISD::CTTZ_ZERO_UNDEF:
2956 EVT SVT = VT.getScalarType();
2957 EVT InVT = BV->getValueType(0);
2958 EVT InSVT = InVT.getScalarType();
2960 // Find legal integer scalar type for constant promotion and
2961 // ensure that its scalar size is at least as large as source.
2963 if (SVT.isInteger()) {
2964 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2965 if (LegalSVT.bitsLT(SVT)) break;
2968 // Let the above scalar folding handle the folding of each element.
2969 SmallVector<SDValue, 8> Ops;
2970 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2971 SDValue OpN = BV->getOperand(i);
2972 EVT OpVT = OpN.getValueType();
2974 // Build vector (integer) scalar operands may need implicit
2975 // truncation - do this before constant folding.
2976 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2977 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2979 OpN = getNode(Opcode, DL, SVT, OpN);
2981 // Legalize the (integer) scalar constant if necessary.
2982 if (LegalSVT != SVT)
2983 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2985 if (OpN.getOpcode() != ISD::UNDEF &&
2986 OpN.getOpcode() != ISD::Constant &&
2987 OpN.getOpcode() != ISD::ConstantFP)
2991 if (Ops.size() == VT.getVectorNumElements())
2992 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2999 unsigned OpOpcode = Operand.getNode()->getOpcode();
3001 case ISD::TokenFactor:
3002 case ISD::MERGE_VALUES:
3003 case ISD::CONCAT_VECTORS:
3004 return Operand; // Factor, merge or concat of one node? No need.
3005 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3006 case ISD::FP_EXTEND:
3007 assert(VT.isFloatingPoint() &&
3008 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3009 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3010 assert((!VT.isVector() ||
3011 VT.getVectorNumElements() ==
3012 Operand.getValueType().getVectorNumElements()) &&
3013 "Vector element count mismatch!");
3014 if (Operand.getOpcode() == ISD::UNDEF)
3015 return getUNDEF(VT);
3017 case ISD::SIGN_EXTEND:
3018 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3019 "Invalid SIGN_EXTEND!");
3020 if (Operand.getValueType() == VT) return Operand; // noop extension
3021 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3022 "Invalid sext node, dst < src!");
3023 assert((!VT.isVector() ||
3024 VT.getVectorNumElements() ==
3025 Operand.getValueType().getVectorNumElements()) &&
3026 "Vector element count mismatch!");
3027 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3028 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3029 else if (OpOpcode == ISD::UNDEF)
3030 // sext(undef) = 0, because the top bits will all be the same.
3031 return getConstant(0, DL, VT);
3033 case ISD::ZERO_EXTEND:
3034 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3035 "Invalid ZERO_EXTEND!");
3036 if (Operand.getValueType() == VT) return Operand; // noop extension
3037 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3038 "Invalid zext node, dst < src!");
3039 assert((!VT.isVector() ||
3040 VT.getVectorNumElements() ==
3041 Operand.getValueType().getVectorNumElements()) &&
3042 "Vector element count mismatch!");
3043 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3044 return getNode(ISD::ZERO_EXTEND, DL, VT,
3045 Operand.getNode()->getOperand(0));
3046 else if (OpOpcode == ISD::UNDEF)
3047 // zext(undef) = 0, because the top bits will be zero.
3048 return getConstant(0, DL, VT);
3050 case ISD::ANY_EXTEND:
3051 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3052 "Invalid ANY_EXTEND!");
3053 if (Operand.getValueType() == VT) return Operand; // noop extension
3054 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3055 "Invalid anyext node, dst < src!");
3056 assert((!VT.isVector() ||
3057 VT.getVectorNumElements() ==
3058 Operand.getValueType().getVectorNumElements()) &&
3059 "Vector element count mismatch!");
3061 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3062 OpOpcode == ISD::ANY_EXTEND)
3063 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3064 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3065 else if (OpOpcode == ISD::UNDEF)
3066 return getUNDEF(VT);
3068 // (ext (trunx x)) -> x
3069 if (OpOpcode == ISD::TRUNCATE) {
3070 SDValue OpOp = Operand.getNode()->getOperand(0);
3071 if (OpOp.getValueType() == VT)
3076 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3077 "Invalid TRUNCATE!");
3078 if (Operand.getValueType() == VT) return Operand; // noop truncate
3079 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3080 "Invalid truncate node, src < dst!");
3081 assert((!VT.isVector() ||
3082 VT.getVectorNumElements() ==
3083 Operand.getValueType().getVectorNumElements()) &&
3084 "Vector element count mismatch!");
3085 if (OpOpcode == ISD::TRUNCATE)
3086 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3087 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3088 OpOpcode == ISD::ANY_EXTEND) {
3089 // If the source is smaller than the dest, we still need an extend.
3090 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3091 .bitsLT(VT.getScalarType()))
3092 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3093 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3094 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3095 return Operand.getNode()->getOperand(0);
3097 if (OpOpcode == ISD::UNDEF)
3098 return getUNDEF(VT);
3101 assert(VT.isInteger() && VT == Operand.getValueType() &&
3103 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3104 "BSWAP types must be a multiple of 16 bits!");
3105 if (OpOpcode == ISD::UNDEF)
3106 return getUNDEF(VT);
3109 // Basic sanity checking.
3110 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3111 && "Cannot BITCAST between types of different sizes!");
3112 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3113 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3114 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3115 if (OpOpcode == ISD::UNDEF)
3116 return getUNDEF(VT);
3118 case ISD::SCALAR_TO_VECTOR:
3119 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3120 (VT.getVectorElementType() == Operand.getValueType() ||
3121 (VT.getVectorElementType().isInteger() &&
3122 Operand.getValueType().isInteger() &&
3123 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3124 "Illegal SCALAR_TO_VECTOR node!");
3125 if (OpOpcode == ISD::UNDEF)
3126 return getUNDEF(VT);
3127 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3128 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3129 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3130 Operand.getConstantOperandVal(1) == 0 &&
3131 Operand.getOperand(0).getValueType() == VT)
3132 return Operand.getOperand(0);
3135 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3136 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3137 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3138 Operand.getNode()->getOperand(0));
3139 if (OpOpcode == ISD::FNEG) // --X -> X
3140 return Operand.getNode()->getOperand(0);
3143 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3144 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3149 SDVTList VTs = getVTList(VT);
3150 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3151 FoldingSetNodeID ID;
3152 SDValue Ops[1] = { Operand };
3153 AddNodeIDNode(ID, Opcode, VTs, Ops);
3155 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3156 return SDValue(E, 0);
3158 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3159 DL.getDebugLoc(), VTs, Operand);
3160 CSEMap.InsertNode(N, IP);
3162 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3163 DL.getDebugLoc(), VTs, Operand);
3167 return SDValue(N, 0);
3170 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3173 case ISD::ADD: return std::make_pair(C1 + C2, true);
3174 case ISD::SUB: return std::make_pair(C1 - C2, true);
3175 case ISD::MUL: return std::make_pair(C1 * C2, true);
3176 case ISD::AND: return std::make_pair(C1 & C2, true);
3177 case ISD::OR: return std::make_pair(C1 | C2, true);
3178 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3179 case ISD::SHL: return std::make_pair(C1 << C2, true);
3180 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3181 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3182 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3183 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3185 if (!C2.getBoolValue())
3187 return std::make_pair(C1.udiv(C2), true);
3189 if (!C2.getBoolValue())
3191 return std::make_pair(C1.urem(C2), true);
3193 if (!C2.getBoolValue())
3195 return std::make_pair(C1.sdiv(C2), true);
3197 if (!C2.getBoolValue())
3199 return std::make_pair(C1.srem(C2), true);
3201 return std::make_pair(APInt(1, 0), false);
3204 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3205 const ConstantSDNode *Cst1,
3206 const ConstantSDNode *Cst2) {
3207 if (Cst1->isOpaque() || Cst2->isOpaque())
3210 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3211 Cst2->getAPIntValue());
3214 return getConstant(Folded.first, DL, VT);
3217 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3218 SDNode *Cst1, SDNode *Cst2) {
3219 // If the opcode is a target-specific ISD node, there's nothing we can
3220 // do here and the operand rules may not line up with the below, so
3222 if (Opcode >= ISD::BUILTIN_OP_END)
3225 // Handle the case of two scalars.
3226 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3227 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3228 if (SDValue Folded =
3229 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3232 SmallVector<SDValue, 4> Outputs;
3233 // We may have a vector type but a scalar result. Create a splat.
3234 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3235 // Build a big vector out of the scalar elements we generated.
3236 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3243 // For vectors extract each constant element into Inputs so we can constant
3244 // fold them individually.
3245 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3246 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3250 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3252 EVT SVT = VT.getScalarType();
3253 SmallVector<SDValue, 4> Outputs;
3254 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3255 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3256 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3257 if (!V1 || !V2) // Not a constant, bail.
3260 if (V1->isOpaque() || V2->isOpaque())
3263 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3264 // FIXME: This is valid and could be handled by truncating the APInts.
3265 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3268 // Fold one vector element.
3269 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3270 V2->getAPIntValue());
3273 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3276 assert(VT.getVectorNumElements() == Outputs.size() &&
3277 "Vector size mismatch!");
3279 // We may have a vector type but a scalar result. Create a splat.
3280 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3282 // Build a big vector out of the scalar elements we generated.
3283 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3286 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3287 SDValue N2, const SDNodeFlags *Flags) {
3288 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3289 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3292 case ISD::TokenFactor:
3293 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3294 N2.getValueType() == MVT::Other && "Invalid token factor!");
3295 // Fold trivial token factors.
3296 if (N1.getOpcode() == ISD::EntryToken) return N2;
3297 if (N2.getOpcode() == ISD::EntryToken) return N1;
3298 if (N1 == N2) return N1;
3300 case ISD::CONCAT_VECTORS:
3301 // Concat of UNDEFs is UNDEF.
3302 if (N1.getOpcode() == ISD::UNDEF &&
3303 N2.getOpcode() == ISD::UNDEF)
3304 return getUNDEF(VT);
3306 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3307 // one big BUILD_VECTOR.
3308 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3309 N2.getOpcode() == ISD::BUILD_VECTOR) {
3310 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3311 N1.getNode()->op_end());
3312 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3314 // BUILD_VECTOR requires all inputs to be of the same type, find the
3315 // maximum type and extend them all.
3316 EVT SVT = VT.getScalarType();
3317 for (SDValue Op : Elts)
3318 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3319 if (SVT.bitsGT(VT.getScalarType()))
3320 for (SDValue &Op : Elts)
3321 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3322 ? getZExtOrTrunc(Op, DL, SVT)
3323 : getSExtOrTrunc(Op, DL, SVT);
3325 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3329 assert(VT.isInteger() && "This operator does not apply to FP types!");
3330 assert(N1.getValueType() == N2.getValueType() &&
3331 N1.getValueType() == VT && "Binary operator types must match!");
3332 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3333 // worth handling here.
3334 if (N2C && N2C->isNullValue())
3336 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3343 assert(VT.isInteger() && "This operator does not apply to FP types!");
3344 assert(N1.getValueType() == N2.getValueType() &&
3345 N1.getValueType() == VT && "Binary operator types must match!");
3346 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3347 // it's worth handling here.
3348 if (N2C && N2C->isNullValue())
3358 assert(VT.isInteger() && "This operator does not apply to FP types!");
3359 assert(N1.getValueType() == N2.getValueType() &&
3360 N1.getValueType() == VT && "Binary operator types must match!");
3367 if (getTarget().Options.UnsafeFPMath) {
3368 if (Opcode == ISD::FADD) {
3370 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3371 if (CFP->getValueAPF().isZero())
3374 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3375 if (CFP->getValueAPF().isZero())
3377 } else if (Opcode == ISD::FSUB) {
3379 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3380 if (CFP->getValueAPF().isZero())
3382 } else if (Opcode == ISD::FMUL) {
3383 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3386 // If the first operand isn't the constant, try the second
3388 CFP = dyn_cast<ConstantFPSDNode>(N2);
3395 return SDValue(CFP,0);
3397 if (CFP->isExactlyValue(1.0))
3402 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3403 assert(N1.getValueType() == N2.getValueType() &&
3404 N1.getValueType() == VT && "Binary operator types must match!");
3406 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3407 assert(N1.getValueType() == VT &&
3408 N1.getValueType().isFloatingPoint() &&
3409 N2.getValueType().isFloatingPoint() &&
3410 "Invalid FCOPYSIGN!");
3417 assert(VT == N1.getValueType() &&
3418 "Shift operators return type must be the same as their first arg");
3419 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3420 "Shifts only work on integers");
3421 assert((!VT.isVector() || VT == N2.getValueType()) &&
3422 "Vector shift amounts must be in the same as their first arg");
3423 // Verify that the shift amount VT is bit enough to hold valid shift
3424 // amounts. This catches things like trying to shift an i1024 value by an
3425 // i8, which is easy to fall into in generic code that uses
3426 // TLI.getShiftAmount().
3427 assert(N2.getValueType().getSizeInBits() >=
3428 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3429 "Invalid use of small shift amount with oversized value!");
3431 // Always fold shifts of i1 values so the code generator doesn't need to
3432 // handle them. Since we know the size of the shift has to be less than the
3433 // size of the value, the shift/rotate count is guaranteed to be zero.
3436 if (N2C && N2C->isNullValue())
3439 case ISD::FP_ROUND_INREG: {
3440 EVT EVT = cast<VTSDNode>(N2)->getVT();
3441 assert(VT == N1.getValueType() && "Not an inreg round!");
3442 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3443 "Cannot FP_ROUND_INREG integer types");
3444 assert(EVT.isVector() == VT.isVector() &&
3445 "FP_ROUND_INREG type should be vector iff the operand "
3447 assert((!EVT.isVector() ||
3448 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3449 "Vector element counts must match in FP_ROUND_INREG");
3450 assert(EVT.bitsLE(VT) && "Not rounding down!");
3452 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3456 assert(VT.isFloatingPoint() &&
3457 N1.getValueType().isFloatingPoint() &&
3458 VT.bitsLE(N1.getValueType()) &&
3459 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3460 if (N1.getValueType() == VT) return N1; // noop conversion.
3462 case ISD::AssertSext:
3463 case ISD::AssertZext: {
3464 EVT EVT = cast<VTSDNode>(N2)->getVT();
3465 assert(VT == N1.getValueType() && "Not an inreg extend!");
3466 assert(VT.isInteger() && EVT.isInteger() &&
3467 "Cannot *_EXTEND_INREG FP types");
3468 assert(!EVT.isVector() &&
3469 "AssertSExt/AssertZExt type should be the vector element type "
3470 "rather than the vector type!");
3471 assert(EVT.bitsLE(VT) && "Not extending!");
3472 if (VT == EVT) return N1; // noop assertion.
3475 case ISD::SIGN_EXTEND_INREG: {
3476 EVT EVT = cast<VTSDNode>(N2)->getVT();
3477 assert(VT == N1.getValueType() && "Not an inreg extend!");
3478 assert(VT.isInteger() && EVT.isInteger() &&
3479 "Cannot *_EXTEND_INREG FP types");
3480 assert(EVT.isVector() == VT.isVector() &&
3481 "SIGN_EXTEND_INREG type should be vector iff the operand "
3483 assert((!EVT.isVector() ||
3484 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3485 "Vector element counts must match in SIGN_EXTEND_INREG");
3486 assert(EVT.bitsLE(VT) && "Not extending!");
3487 if (EVT == VT) return N1; // Not actually extending
3489 auto SignExtendInReg = [&](APInt Val) {
3490 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3491 Val <<= Val.getBitWidth() - FromBits;
3492 Val = Val.ashr(Val.getBitWidth() - FromBits);
3493 return getConstant(Val, DL, VT.getScalarType());
3497 APInt Val = N1C->getAPIntValue();
3498 return SignExtendInReg(Val);
3500 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3501 SmallVector<SDValue, 8> Ops;
3502 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3503 SDValue Op = N1.getOperand(i);
3504 if (Op.getValueType() != VT.getScalarType()) break;
3505 if (Op.getOpcode() == ISD::UNDEF) {
3509 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3510 APInt Val = C->getAPIntValue();
3511 Ops.push_back(SignExtendInReg(Val));
3516 if (Ops.size() == VT.getVectorNumElements())
3517 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3521 case ISD::EXTRACT_VECTOR_ELT:
3522 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3523 if (N1.getOpcode() == ISD::UNDEF)
3524 return getUNDEF(VT);
3526 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3527 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3528 return getUNDEF(VT);
3530 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3531 // expanding copies of large vectors from registers.
3533 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3534 N1.getNumOperands() > 0) {
3536 N1.getOperand(0).getValueType().getVectorNumElements();
3537 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3538 N1.getOperand(N2C->getZExtValue() / Factor),
3539 getConstant(N2C->getZExtValue() % Factor, DL,
3540 N2.getValueType()));
3543 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3544 // expanding large vector constants.
3545 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3546 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3548 if (VT != Elt.getValueType())
3549 // If the vector element type is not legal, the BUILD_VECTOR operands
3550 // are promoted and implicitly truncated, and the result implicitly
3551 // extended. Make that explicit here.
3552 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3557 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3558 // operations are lowered to scalars.
3559 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3560 // If the indices are the same, return the inserted element else
3561 // if the indices are known different, extract the element from
3562 // the original vector.
3563 SDValue N1Op2 = N1.getOperand(2);
3564 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3566 if (N1Op2C && N2C) {
3567 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3568 if (VT == N1.getOperand(1).getValueType())
3569 return N1.getOperand(1);
3571 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3574 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3578 case ISD::EXTRACT_ELEMENT:
3579 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3580 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3581 (N1.getValueType().isInteger() == VT.isInteger()) &&
3582 N1.getValueType() != VT &&
3583 "Wrong types for EXTRACT_ELEMENT!");
3585 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3586 // 64-bit integers into 32-bit parts. Instead of building the extract of
3587 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3588 if (N1.getOpcode() == ISD::BUILD_PAIR)
3589 return N1.getOperand(N2C->getZExtValue());
3591 // EXTRACT_ELEMENT of a constant int is also very common.
3592 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3593 unsigned ElementSize = VT.getSizeInBits();
3594 unsigned Shift = ElementSize * N2C->getZExtValue();
3595 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3596 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3599 case ISD::EXTRACT_SUBVECTOR: {
3601 if (VT.isSimple() && N1.getValueType().isSimple()) {
3602 assert(VT.isVector() && N1.getValueType().isVector() &&
3603 "Extract subvector VTs must be a vectors!");
3604 assert(VT.getVectorElementType() ==
3605 N1.getValueType().getVectorElementType() &&
3606 "Extract subvector VTs must have the same element type!");
3607 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3608 "Extract subvector must be from larger vector to smaller vector!");
3610 if (isa<ConstantSDNode>(Index)) {
3611 assert((VT.getVectorNumElements() +
3612 cast<ConstantSDNode>(Index)->getZExtValue()
3613 <= N1.getValueType().getVectorNumElements())
3614 && "Extract subvector overflow!");
3617 // Trivial extraction.
3618 if (VT.getSimpleVT() == N1.getSimpleValueType())
3625 // Perform trivial constant folding.
3627 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3630 // Canonicalize constant to RHS if commutative.
3631 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3632 std::swap(N1C, N2C);
3636 // Constant fold FP operations.
3637 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3638 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3639 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3641 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3642 // Canonicalize constant to RHS if commutative.
3643 std::swap(N1CFP, N2CFP);
3646 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3647 APFloat::opStatus s;
3650 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3651 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3652 return getConstantFP(V1, DL, VT);
3655 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3656 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3657 return getConstantFP(V1, DL, VT);
3660 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3661 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3662 return getConstantFP(V1, DL, VT);
3665 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3666 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3667 s!=APFloat::opDivByZero)) {
3668 return getConstantFP(V1, DL, VT);
3672 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3673 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3674 s!=APFloat::opDivByZero)) {
3675 return getConstantFP(V1, DL, VT);
3678 case ISD::FCOPYSIGN:
3680 return getConstantFP(V1, DL, VT);
3685 if (Opcode == ISD::FP_ROUND) {
3686 APFloat V = N1CFP->getValueAPF(); // make copy
3688 // This can return overflow, underflow, or inexact; we don't care.
3689 // FIXME need to be more flexible about rounding mode.
3690 (void)V.convert(EVTToAPFloatSemantics(VT),
3691 APFloat::rmNearestTiesToEven, &ignored);
3692 return getConstantFP(V, DL, VT);
3696 // Canonicalize an UNDEF to the RHS, even over a constant.
3697 if (N1.getOpcode() == ISD::UNDEF) {
3698 if (isCommutativeBinOp(Opcode)) {
3702 case ISD::FP_ROUND_INREG:
3703 case ISD::SIGN_EXTEND_INREG:
3709 return N1; // fold op(undef, arg2) -> undef
3717 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3718 // For vectors, we can't easily build an all zero vector, just return
3725 // Fold a bunch of operators when the RHS is undef.
3726 if (N2.getOpcode() == ISD::UNDEF) {
3729 if (N1.getOpcode() == ISD::UNDEF)
3730 // Handle undef ^ undef -> 0 special case. This is a common
3732 return getConstant(0, DL, VT);
3742 return N2; // fold op(arg1, undef) -> undef
3748 if (getTarget().Options.UnsafeFPMath)
3756 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3757 // For vectors, we can't easily build an all zero vector, just return
3762 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3763 // For vectors, we can't easily build an all one vector, just return
3771 // Memoize this node if possible.
3773 SDVTList VTs = getVTList(VT);
3774 if (VT != MVT::Glue) {
3775 SDValue Ops[] = {N1, N2};
3776 FoldingSetNodeID ID;
3777 AddNodeIDNode(ID, Opcode, VTs, Ops);
3778 AddNodeIDFlags(ID, Opcode, Flags);
3780 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3781 return SDValue(E, 0);
3783 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3785 CSEMap.InsertNode(N, IP);
3787 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3791 return SDValue(N, 0);
3794 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3795 SDValue N1, SDValue N2, SDValue N3) {
3796 // Perform various simplifications.
3797 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3800 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3801 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3802 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3803 if (N1CFP && N2CFP && N3CFP) {
3804 APFloat V1 = N1CFP->getValueAPF();
3805 const APFloat &V2 = N2CFP->getValueAPF();
3806 const APFloat &V3 = N3CFP->getValueAPF();
3807 APFloat::opStatus s =
3808 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3809 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3810 return getConstantFP(V1, DL, VT);
3814 case ISD::CONCAT_VECTORS:
3815 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3816 // one big BUILD_VECTOR.
3817 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3818 N2.getOpcode() == ISD::BUILD_VECTOR &&
3819 N3.getOpcode() == ISD::BUILD_VECTOR) {
3820 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3821 N1.getNode()->op_end());
3822 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3823 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3824 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3828 // Use FoldSetCC to simplify SETCC's.
3829 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3830 if (Simp.getNode()) return Simp;
3835 if (N1C->getZExtValue())
3836 return N2; // select true, X, Y -> X
3837 return N3; // select false, X, Y -> Y
3840 if (N2 == N3) return N2; // select C, X, X -> X
3842 case ISD::VECTOR_SHUFFLE:
3843 llvm_unreachable("should use getVectorShuffle constructor!");
3844 case ISD::INSERT_SUBVECTOR: {
3846 if (VT.isSimple() && N1.getValueType().isSimple()
3847 && N2.getValueType().isSimple()) {
3848 assert(VT.isVector() && N1.getValueType().isVector() &&
3849 N2.getValueType().isVector() &&
3850 "Insert subvector VTs must be a vectors");
3851 assert(VT == N1.getValueType() &&
3852 "Dest and insert subvector source types must match!");
3853 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3854 "Insert subvector must be from smaller vector to larger vector!");
3855 if (isa<ConstantSDNode>(Index)) {
3856 assert((N2.getValueType().getVectorNumElements() +
3857 cast<ConstantSDNode>(Index)->getZExtValue()
3858 <= VT.getVectorNumElements())
3859 && "Insert subvector overflow!");
3862 // Trivial insertion.
3863 if (VT.getSimpleVT() == N2.getSimpleValueType())
3869 // Fold bit_convert nodes from a type to themselves.
3870 if (N1.getValueType() == VT)
3875 // Memoize node if it doesn't produce a flag.
3877 SDVTList VTs = getVTList(VT);
3878 if (VT != MVT::Glue) {
3879 SDValue Ops[] = { N1, N2, N3 };
3880 FoldingSetNodeID ID;
3881 AddNodeIDNode(ID, Opcode, VTs, Ops);
3883 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3884 return SDValue(E, 0);
3886 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3887 DL.getDebugLoc(), VTs, N1, N2, N3);
3888 CSEMap.InsertNode(N, IP);
3890 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3891 DL.getDebugLoc(), VTs, N1, N2, N3);
3895 return SDValue(N, 0);
3898 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3899 SDValue N1, SDValue N2, SDValue N3,
3901 SDValue Ops[] = { N1, N2, N3, N4 };
3902 return getNode(Opcode, DL, VT, Ops);
3905 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3906 SDValue N1, SDValue N2, SDValue N3,
3907 SDValue N4, SDValue N5) {
3908 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3909 return getNode(Opcode, DL, VT, Ops);
3912 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3913 /// the incoming stack arguments to be loaded from the stack.
3914 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3915 SmallVector<SDValue, 8> ArgChains;
3917 // Include the original chain at the beginning of the list. When this is
3918 // used by target LowerCall hooks, this helps legalize find the
3919 // CALLSEQ_BEGIN node.
3920 ArgChains.push_back(Chain);
3922 // Add a chain value for each stack argument.
3923 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3924 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3925 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3926 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3927 if (FI->getIndex() < 0)
3928 ArgChains.push_back(SDValue(L, 1));
3930 // Build a tokenfactor for all the chains.
3931 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3934 /// getMemsetValue - Vectorized representation of the memset value
3936 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3938 assert(Value.getOpcode() != ISD::UNDEF);
3940 unsigned NumBits = VT.getScalarType().getSizeInBits();
3941 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3942 assert(C->getAPIntValue().getBitWidth() == 8);
3943 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3945 return DAG.getConstant(Val, dl, VT);
3946 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3950 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3951 EVT IntVT = VT.getScalarType();
3952 if (!IntVT.isInteger())
3953 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3955 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3957 // Use a multiplication with 0x010101... to extend the input to the
3959 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3960 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3961 DAG.getConstant(Magic, dl, IntVT));
3964 if (VT != Value.getValueType() && !VT.isInteger())
3965 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3966 if (VT != Value.getValueType()) {
3967 assert(VT.getVectorElementType() == Value.getValueType() &&
3968 "value type should be one vector element here");
3969 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3970 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3976 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3977 /// used when a memcpy is turned into a memset when the source is a constant
3979 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3980 const TargetLowering &TLI, StringRef Str) {
3981 // Handle vector with all elements zero.
3984 return DAG.getConstant(0, dl, VT);
3985 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3986 return DAG.getConstantFP(0.0, dl, VT);
3987 else if (VT.isVector()) {
3988 unsigned NumElts = VT.getVectorNumElements();
3989 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3990 return DAG.getNode(ISD::BITCAST, dl, VT,
3991 DAG.getConstant(0, dl,
3992 EVT::getVectorVT(*DAG.getContext(),
3995 llvm_unreachable("Expected type!");
3998 assert(!VT.isVector() && "Can't handle vector type here!");
3999 unsigned NumVTBits = VT.getSizeInBits();
4000 unsigned NumVTBytes = NumVTBits / 8;
4001 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4003 APInt Val(NumVTBits, 0);
4004 if (DAG.getDataLayout().isLittleEndian()) {
4005 for (unsigned i = 0; i != NumBytes; ++i)
4006 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4008 for (unsigned i = 0; i != NumBytes; ++i)
4009 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4012 // If the "cost" of materializing the integer immediate is less than the cost
4013 // of a load, then it is cost effective to turn the load into the immediate.
4014 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4015 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4016 return DAG.getConstant(Val, dl, VT);
4017 return SDValue(nullptr, 0);
4020 /// getMemBasePlusOffset - Returns base and offset node for the
4022 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4023 SelectionDAG &DAG) {
4024 EVT VT = Base.getValueType();
4025 return DAG.getNode(ISD::ADD, dl,
4026 VT, Base, DAG.getConstant(Offset, dl, VT));
4029 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4031 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4032 unsigned SrcDelta = 0;
4033 GlobalAddressSDNode *G = nullptr;
4034 if (Src.getOpcode() == ISD::GlobalAddress)
4035 G = cast<GlobalAddressSDNode>(Src);
4036 else if (Src.getOpcode() == ISD::ADD &&
4037 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4038 Src.getOperand(1).getOpcode() == ISD::Constant) {
4039 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4040 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4045 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4048 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4049 /// Return true if the number of memory ops is below the threshold (Limit).
4050 /// It returns the types of the sequence of memory ops to perform
4051 /// memset / memcpy by reference.
4052 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4053 unsigned Limit, uint64_t Size,
4054 unsigned DstAlign, unsigned SrcAlign,
4060 const TargetLowering &TLI) {
4061 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4062 "Expecting memcpy / memset source to meet alignment requirement!");
4063 // If 'SrcAlign' is zero, that means the memory operation does not need to
4064 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4065 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4066 // is the specified alignment of the memory operation. If it is zero, that
4067 // means it's possible to change the alignment of the destination.
4068 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4069 // not need to be loaded.
4070 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4071 IsMemset, ZeroMemset, MemcpyStrSrc,
4072 DAG.getMachineFunction());
4074 if (VT == MVT::Other) {
4076 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4077 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4078 VT = TLI.getPointerTy(DAG.getDataLayout());
4080 switch (DstAlign & 7) {
4081 case 0: VT = MVT::i64; break;
4082 case 4: VT = MVT::i32; break;
4083 case 2: VT = MVT::i16; break;
4084 default: VT = MVT::i8; break;
4089 while (!TLI.isTypeLegal(LVT))
4090 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4091 assert(LVT.isInteger());
4097 unsigned NumMemOps = 0;
4099 unsigned VTSize = VT.getSizeInBits() / 8;
4100 while (VTSize > Size) {
4101 // For now, only use non-vector load / store's for the left-over pieces.
4106 if (VT.isVector() || VT.isFloatingPoint()) {
4107 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4108 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4109 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4111 else if (NewVT == MVT::i64 &&
4112 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4113 TLI.isSafeMemOpType(MVT::f64)) {
4114 // i64 is usually not legal on 32-bit targets, but f64 may be.
4122 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4123 if (NewVT == MVT::i8)
4125 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4127 NewVTSize = NewVT.getSizeInBits() / 8;
4129 // If the new VT cannot cover all of the remaining bits, then consider
4130 // issuing a (or a pair of) unaligned and overlapping load / store.
4131 // FIXME: Only does this for 64-bit or more since we don't have proper
4132 // cost model for unaligned load / store.
4135 if (NumMemOps && AllowOverlap &&
4136 VTSize >= 8 && NewVTSize < Size &&
4137 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4145 if (++NumMemOps > Limit)
4148 MemOps.push_back(VT);
4155 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4156 SDValue Chain, SDValue Dst,
4157 SDValue Src, uint64_t Size,
4158 unsigned Align, bool isVol,
4160 MachinePointerInfo DstPtrInfo,
4161 MachinePointerInfo SrcPtrInfo) {
4162 // Turn a memcpy of undef to nop.
4163 if (Src.getOpcode() == ISD::UNDEF)
4166 // Expand memcpy to a series of load and store ops if the size operand falls
4167 // below a certain threshold.
4168 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4169 // rather than maybe a humongous number of loads and stores.
4170 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4171 std::vector<EVT> MemOps;
4172 bool DstAlignCanChange = false;
4173 MachineFunction &MF = DAG.getMachineFunction();
4174 MachineFrameInfo *MFI = MF.getFrameInfo();
4175 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4176 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4177 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4178 DstAlignCanChange = true;
4179 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4180 if (Align > SrcAlign)
4183 bool CopyFromStr = isMemSrcFromString(Src, Str);
4184 bool isZeroStr = CopyFromStr && Str.empty();
4185 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4187 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4188 (DstAlignCanChange ? 0 : Align),
4189 (isZeroStr ? 0 : SrcAlign),
4190 false, false, CopyFromStr, true, DAG, TLI))
4193 if (DstAlignCanChange) {
4194 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4195 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4197 // Don't promote to an alignment that would require dynamic stack
4199 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4200 if (!TRI->needsStackRealignment(MF))
4201 while (NewAlign > Align &&
4202 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4205 if (NewAlign > Align) {
4206 // Give the stack frame object a larger alignment if needed.
4207 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4208 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4213 SmallVector<SDValue, 8> OutChains;
4214 unsigned NumMemOps = MemOps.size();
4215 uint64_t SrcOff = 0, DstOff = 0;
4216 for (unsigned i = 0; i != NumMemOps; ++i) {
4218 unsigned VTSize = VT.getSizeInBits() / 8;
4219 SDValue Value, Store;
4221 if (VTSize > Size) {
4222 // Issuing an unaligned load / store pair that overlaps with the previous
4223 // pair. Adjust the offset accordingly.
4224 assert(i == NumMemOps-1 && i != 0);
4225 SrcOff -= VTSize - Size;
4226 DstOff -= VTSize - Size;
4230 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4231 // It's unlikely a store of a vector immediate can be done in a single
4232 // instruction. It would require a load from a constantpool first.
4233 // We only handle zero vectors here.
4234 // FIXME: Handle other cases where store of vector immediate is done in
4235 // a single instruction.
4236 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4237 if (Value.getNode())
4238 Store = DAG.getStore(Chain, dl, Value,
4239 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4240 DstPtrInfo.getWithOffset(DstOff), isVol,
4244 if (!Store.getNode()) {
4245 // The type might not be legal for the target. This should only happen
4246 // if the type is smaller than a legal type, as on PPC, so the right
4247 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4248 // to Load/Store if NVT==VT.
4249 // FIXME does the case above also need this?
4250 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4251 assert(NVT.bitsGE(VT));
4252 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4253 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4254 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4255 false, MinAlign(SrcAlign, SrcOff));
4256 Store = DAG.getTruncStore(Chain, dl, Value,
4257 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4258 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4261 OutChains.push_back(Store);
4267 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4270 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4271 SDValue Chain, SDValue Dst,
4272 SDValue Src, uint64_t Size,
4273 unsigned Align, bool isVol,
4275 MachinePointerInfo DstPtrInfo,
4276 MachinePointerInfo SrcPtrInfo) {
4277 // Turn a memmove of undef to nop.
4278 if (Src.getOpcode() == ISD::UNDEF)
4281 // Expand memmove to a series of load and store ops if the size operand falls
4282 // below a certain threshold.
4283 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4284 std::vector<EVT> MemOps;
4285 bool DstAlignCanChange = false;
4286 MachineFunction &MF = DAG.getMachineFunction();
4287 MachineFrameInfo *MFI = MF.getFrameInfo();
4288 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4289 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4290 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4291 DstAlignCanChange = true;
4292 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4293 if (Align > SrcAlign)
4295 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4297 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4298 (DstAlignCanChange ? 0 : Align), SrcAlign,
4299 false, false, false, false, DAG, TLI))
4302 if (DstAlignCanChange) {
4303 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4304 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4305 if (NewAlign > Align) {
4306 // Give the stack frame object a larger alignment if needed.
4307 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4308 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4313 uint64_t SrcOff = 0, DstOff = 0;
4314 SmallVector<SDValue, 8> LoadValues;
4315 SmallVector<SDValue, 8> LoadChains;
4316 SmallVector<SDValue, 8> OutChains;
4317 unsigned NumMemOps = MemOps.size();
4318 for (unsigned i = 0; i < NumMemOps; i++) {
4320 unsigned VTSize = VT.getSizeInBits() / 8;
4323 Value = DAG.getLoad(VT, dl, Chain,
4324 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4325 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4326 false, false, SrcAlign);
4327 LoadValues.push_back(Value);
4328 LoadChains.push_back(Value.getValue(1));
4331 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4333 for (unsigned i = 0; i < NumMemOps; i++) {
4335 unsigned VTSize = VT.getSizeInBits() / 8;
4338 Store = DAG.getStore(Chain, dl, LoadValues[i],
4339 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4340 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4341 OutChains.push_back(Store);
4345 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4348 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4351 /// \param DAG Selection DAG where lowered code is placed.
4352 /// \param dl Link to corresponding IR location.
4353 /// \param Chain Control flow dependency.
4354 /// \param Dst Pointer to destination memory location.
4355 /// \param Src Value of byte to write into the memory.
4356 /// \param Size Number of bytes to write.
4357 /// \param Align Alignment of the destination in bytes.
4358 /// \param isVol True if destination is volatile.
4359 /// \param DstPtrInfo IR information on the memory pointer.
4360 /// \returns New head in the control flow, if lowering was successful, empty
4361 /// SDValue otherwise.
4363 /// The function tries to replace 'llvm.memset' intrinsic with several store
4364 /// operations and value calculation code. This is usually profitable for small
4366 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4367 SDValue Chain, SDValue Dst,
4368 SDValue Src, uint64_t Size,
4369 unsigned Align, bool isVol,
4370 MachinePointerInfo DstPtrInfo) {
4371 // Turn a memset of undef to nop.
4372 if (Src.getOpcode() == ISD::UNDEF)
4375 // Expand memset to a series of load/store ops if the size operand
4376 // falls below a certain threshold.
4377 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4378 std::vector<EVT> MemOps;
4379 bool DstAlignCanChange = false;
4380 MachineFunction &MF = DAG.getMachineFunction();
4381 MachineFrameInfo *MFI = MF.getFrameInfo();
4382 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4383 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4384 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4385 DstAlignCanChange = true;
4387 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4388 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4389 Size, (DstAlignCanChange ? 0 : Align), 0,
4390 true, IsZeroVal, false, true, DAG, TLI))
4393 if (DstAlignCanChange) {
4394 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4395 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4396 if (NewAlign > Align) {
4397 // Give the stack frame object a larger alignment if needed.
4398 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4399 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4404 SmallVector<SDValue, 8> OutChains;
4405 uint64_t DstOff = 0;
4406 unsigned NumMemOps = MemOps.size();
4408 // Find the largest store and generate the bit pattern for it.
4409 EVT LargestVT = MemOps[0];
4410 for (unsigned i = 1; i < NumMemOps; i++)
4411 if (MemOps[i].bitsGT(LargestVT))
4412 LargestVT = MemOps[i];
4413 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4415 for (unsigned i = 0; i < NumMemOps; i++) {
4417 unsigned VTSize = VT.getSizeInBits() / 8;
4418 if (VTSize > Size) {
4419 // Issuing an unaligned load / store pair that overlaps with the previous
4420 // pair. Adjust the offset accordingly.
4421 assert(i == NumMemOps-1 && i != 0);
4422 DstOff -= VTSize - Size;
4425 // If this store is smaller than the largest store see whether we can get
4426 // the smaller value for free with a truncate.
4427 SDValue Value = MemSetValue;
4428 if (VT.bitsLT(LargestVT)) {
4429 if (!LargestVT.isVector() && !VT.isVector() &&
4430 TLI.isTruncateFree(LargestVT, VT))
4431 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4433 Value = getMemsetValue(Src, VT, DAG, dl);
4435 assert(Value.getValueType() == VT && "Value with wrong type.");
4436 SDValue Store = DAG.getStore(Chain, dl, Value,
4437 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4438 DstPtrInfo.getWithOffset(DstOff),
4439 isVol, false, Align);
4440 OutChains.push_back(Store);
4441 DstOff += VT.getSizeInBits() / 8;
4445 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4448 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4449 SDValue Src, SDValue Size,
4450 unsigned Align, bool isVol, bool AlwaysInline,
4451 bool isTailCall, MachinePointerInfo DstPtrInfo,
4452 MachinePointerInfo SrcPtrInfo) {
4453 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4455 // Check to see if we should lower the memcpy to loads and stores first.
4456 // For cases within the target-specified limits, this is the best choice.
4457 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4459 // Memcpy with size zero? Just return the original chain.
4460 if (ConstantSize->isNullValue())
4463 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4464 ConstantSize->getZExtValue(),Align,
4465 isVol, false, DstPtrInfo, SrcPtrInfo);
4466 if (Result.getNode())
4470 // Then check to see if we should lower the memcpy with target-specific
4471 // code. If the target chooses to do this, this is the next best.
4473 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4474 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4475 DstPtrInfo, SrcPtrInfo);
4476 if (Result.getNode())
4480 // If we really need inline code and the target declined to provide it,
4481 // use a (potentially long) sequence of loads and stores.
4483 assert(ConstantSize && "AlwaysInline requires a constant size!");
4484 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4485 ConstantSize->getZExtValue(), Align, isVol,
4486 true, DstPtrInfo, SrcPtrInfo);
4489 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4490 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4491 // respect volatile, so they may do things like read or write memory
4492 // beyond the given memory regions. But fixing this isn't easy, and most
4493 // people don't care.
4495 // Emit a library call.
4496 TargetLowering::ArgListTy Args;
4497 TargetLowering::ArgListEntry Entry;
4498 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4499 Entry.Node = Dst; Args.push_back(Entry);
4500 Entry.Node = Src; Args.push_back(Entry);
4501 Entry.Node = Size; Args.push_back(Entry);
4502 // FIXME: pass in SDLoc
4503 TargetLowering::CallLoweringInfo CLI(*this);
4506 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4507 Type::getVoidTy(*getContext()),
4508 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4509 TLI->getPointerTy(getDataLayout())),
4512 .setTailCall(isTailCall);
4514 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4515 return CallResult.second;
4518 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4519 SDValue Src, SDValue Size,
4520 unsigned Align, bool isVol, bool isTailCall,
4521 MachinePointerInfo DstPtrInfo,
4522 MachinePointerInfo SrcPtrInfo) {
4523 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4525 // Check to see if we should lower the memmove to loads and stores first.
4526 // For cases within the target-specified limits, this is the best choice.
4527 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4529 // Memmove with size zero? Just return the original chain.
4530 if (ConstantSize->isNullValue())
4534 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4535 ConstantSize->getZExtValue(), Align, isVol,
4536 false, DstPtrInfo, SrcPtrInfo);
4537 if (Result.getNode())
4541 // Then check to see if we should lower the memmove with target-specific
4542 // code. If the target chooses to do this, this is the next best.
4544 SDValue Result = TSI->EmitTargetCodeForMemmove(
4545 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4546 if (Result.getNode())
4550 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4551 // not be safe. See memcpy above for more details.
4553 // Emit a library call.
4554 TargetLowering::ArgListTy Args;
4555 TargetLowering::ArgListEntry Entry;
4556 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4557 Entry.Node = Dst; Args.push_back(Entry);
4558 Entry.Node = Src; Args.push_back(Entry);
4559 Entry.Node = Size; Args.push_back(Entry);
4560 // FIXME: pass in SDLoc
4561 TargetLowering::CallLoweringInfo CLI(*this);
4564 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4565 Type::getVoidTy(*getContext()),
4566 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4567 TLI->getPointerTy(getDataLayout())),
4570 .setTailCall(isTailCall);
4572 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4573 return CallResult.second;
4576 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4577 SDValue Src, SDValue Size,
4578 unsigned Align, bool isVol, bool isTailCall,
4579 MachinePointerInfo DstPtrInfo) {
4580 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4582 // Check to see if we should lower the memset to stores first.
4583 // For cases within the target-specified limits, this is the best choice.
4584 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4586 // Memset with size zero? Just return the original chain.
4587 if (ConstantSize->isNullValue())
4591 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4592 Align, isVol, DstPtrInfo);
4594 if (Result.getNode())
4598 // Then check to see if we should lower the memset with target-specific
4599 // code. If the target chooses to do this, this is the next best.
4601 SDValue Result = TSI->EmitTargetCodeForMemset(
4602 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4603 if (Result.getNode())
4607 // Emit a library call.
4608 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4609 TargetLowering::ArgListTy Args;
4610 TargetLowering::ArgListEntry Entry;
4611 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4612 Args.push_back(Entry);
4614 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4615 Args.push_back(Entry);
4617 Entry.Ty = IntPtrTy;
4618 Args.push_back(Entry);
4620 // FIXME: pass in SDLoc
4621 TargetLowering::CallLoweringInfo CLI(*this);
4624 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4625 Type::getVoidTy(*getContext()),
4626 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4627 TLI->getPointerTy(getDataLayout())),
4630 .setTailCall(isTailCall);
4632 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4633 return CallResult.second;
4636 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4637 SDVTList VTList, ArrayRef<SDValue> Ops,
4638 MachineMemOperand *MMO,
4639 AtomicOrdering SuccessOrdering,
4640 AtomicOrdering FailureOrdering,
4641 SynchronizationScope SynchScope) {
4642 FoldingSetNodeID ID;
4643 ID.AddInteger(MemVT.getRawBits());
4644 AddNodeIDNode(ID, Opcode, VTList, Ops);
4645 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4647 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4648 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4649 return SDValue(E, 0);
4652 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4653 // SDNode doesn't have access to it. This memory will be "leaked" when
4654 // the node is deallocated, but recovered when the allocator is released.
4655 // If the number of operands is less than 5 we use AtomicSDNode's internal
4657 unsigned NumOps = Ops.size();
4658 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4661 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4662 dl.getDebugLoc(), VTList, MemVT,
4663 Ops.data(), DynOps, NumOps, MMO,
4664 SuccessOrdering, FailureOrdering,
4666 CSEMap.InsertNode(N, IP);
4668 return SDValue(N, 0);
4671 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4672 SDVTList VTList, ArrayRef<SDValue> Ops,
4673 MachineMemOperand *MMO,
4674 AtomicOrdering Ordering,
4675 SynchronizationScope SynchScope) {
4676 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4677 Ordering, SynchScope);
4680 SDValue SelectionDAG::getAtomicCmpSwap(
4681 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4682 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4683 unsigned Alignment, AtomicOrdering SuccessOrdering,
4684 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4685 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4686 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4687 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4689 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4690 Alignment = getEVTAlignment(MemVT);
4692 MachineFunction &MF = getMachineFunction();
4694 // FIXME: Volatile isn't really correct; we should keep track of atomic
4695 // orderings in the memoperand.
4696 unsigned Flags = MachineMemOperand::MOVolatile;
4697 Flags |= MachineMemOperand::MOLoad;
4698 Flags |= MachineMemOperand::MOStore;
4700 MachineMemOperand *MMO =
4701 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4703 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4704 SuccessOrdering, FailureOrdering, SynchScope);
4707 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4708 SDVTList VTs, SDValue Chain, SDValue Ptr,
4709 SDValue Cmp, SDValue Swp,
4710 MachineMemOperand *MMO,
4711 AtomicOrdering SuccessOrdering,
4712 AtomicOrdering FailureOrdering,
4713 SynchronizationScope SynchScope) {
4714 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4715 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4716 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4718 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4719 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4720 SuccessOrdering, FailureOrdering, SynchScope);
4723 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4725 SDValue Ptr, SDValue Val,
4726 const Value* PtrVal,
4728 AtomicOrdering Ordering,
4729 SynchronizationScope SynchScope) {
4730 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4731 Alignment = getEVTAlignment(MemVT);
4733 MachineFunction &MF = getMachineFunction();
4734 // An atomic store does not load. An atomic load does not store.
4735 // (An atomicrmw obviously both loads and stores.)
4736 // For now, atomics are considered to be volatile always, and they are
4738 // FIXME: Volatile isn't really correct; we should keep track of atomic
4739 // orderings in the memoperand.
4740 unsigned Flags = MachineMemOperand::MOVolatile;
4741 if (Opcode != ISD::ATOMIC_STORE)
4742 Flags |= MachineMemOperand::MOLoad;
4743 if (Opcode != ISD::ATOMIC_LOAD)
4744 Flags |= MachineMemOperand::MOStore;
4746 MachineMemOperand *MMO =
4747 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4748 MemVT.getStoreSize(), Alignment);
4750 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4751 Ordering, SynchScope);
4754 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4756 SDValue Ptr, SDValue Val,
4757 MachineMemOperand *MMO,
4758 AtomicOrdering Ordering,
4759 SynchronizationScope SynchScope) {
4760 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4761 Opcode == ISD::ATOMIC_LOAD_SUB ||
4762 Opcode == ISD::ATOMIC_LOAD_AND ||
4763 Opcode == ISD::ATOMIC_LOAD_OR ||
4764 Opcode == ISD::ATOMIC_LOAD_XOR ||
4765 Opcode == ISD::ATOMIC_LOAD_NAND ||
4766 Opcode == ISD::ATOMIC_LOAD_MIN ||
4767 Opcode == ISD::ATOMIC_LOAD_MAX ||
4768 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4769 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4770 Opcode == ISD::ATOMIC_SWAP ||
4771 Opcode == ISD::ATOMIC_STORE) &&
4772 "Invalid Atomic Op");
4774 EVT VT = Val.getValueType();
4776 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4777 getVTList(VT, MVT::Other);
4778 SDValue Ops[] = {Chain, Ptr, Val};
4779 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4782 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4783 EVT VT, SDValue Chain,
4785 MachineMemOperand *MMO,
4786 AtomicOrdering Ordering,
4787 SynchronizationScope SynchScope) {
4788 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4790 SDVTList VTs = getVTList(VT, MVT::Other);
4791 SDValue Ops[] = {Chain, Ptr};
4792 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4795 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4796 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4797 if (Ops.size() == 1)
4800 SmallVector<EVT, 4> VTs;
4801 VTs.reserve(Ops.size());
4802 for (unsigned i = 0; i < Ops.size(); ++i)
4803 VTs.push_back(Ops[i].getValueType());
4804 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4808 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4809 ArrayRef<SDValue> Ops,
4810 EVT MemVT, MachinePointerInfo PtrInfo,
4811 unsigned Align, bool Vol,
4812 bool ReadMem, bool WriteMem, unsigned Size) {
4813 if (Align == 0) // Ensure that codegen never sees alignment 0
4814 Align = getEVTAlignment(MemVT);
4816 MachineFunction &MF = getMachineFunction();
4819 Flags |= MachineMemOperand::MOStore;
4821 Flags |= MachineMemOperand::MOLoad;
4823 Flags |= MachineMemOperand::MOVolatile;
4825 Size = MemVT.getStoreSize();
4826 MachineMemOperand *MMO =
4827 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4829 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4833 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4834 ArrayRef<SDValue> Ops, EVT MemVT,
4835 MachineMemOperand *MMO) {
4836 assert((Opcode == ISD::INTRINSIC_VOID ||
4837 Opcode == ISD::INTRINSIC_W_CHAIN ||
4838 Opcode == ISD::PREFETCH ||
4839 Opcode == ISD::LIFETIME_START ||
4840 Opcode == ISD::LIFETIME_END ||
4841 (Opcode <= INT_MAX &&
4842 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4843 "Opcode is not a memory-accessing opcode!");
4845 // Memoize the node unless it returns a flag.
4846 MemIntrinsicSDNode *N;
4847 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4848 FoldingSetNodeID ID;
4849 AddNodeIDNode(ID, Opcode, VTList, Ops);
4850 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4852 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4853 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4854 return SDValue(E, 0);
4857 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4858 dl.getDebugLoc(), VTList, Ops,
4860 CSEMap.InsertNode(N, IP);
4862 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4863 dl.getDebugLoc(), VTList, Ops,
4867 return SDValue(N, 0);
4870 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4871 /// MachinePointerInfo record from it. This is particularly useful because the
4872 /// code generator has many cases where it doesn't bother passing in a
4873 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4874 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4875 // If this is FI+Offset, we can model it.
4876 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4877 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4879 // If this is (FI+Offset1)+Offset2, we can model it.
4880 if (Ptr.getOpcode() != ISD::ADD ||
4881 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4882 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4883 return MachinePointerInfo();
4885 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4886 return MachinePointerInfo::getFixedStack(FI, Offset+
4887 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4890 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4891 /// MachinePointerInfo record from it. This is particularly useful because the
4892 /// code generator has many cases where it doesn't bother passing in a
4893 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4894 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4895 // If the 'Offset' value isn't a constant, we can't handle this.
4896 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4897 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4898 if (OffsetOp.getOpcode() == ISD::UNDEF)
4899 return InferPointerInfo(Ptr);
4900 return MachinePointerInfo();
4905 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4906 EVT VT, SDLoc dl, SDValue Chain,
4907 SDValue Ptr, SDValue Offset,
4908 MachinePointerInfo PtrInfo, EVT MemVT,
4909 bool isVolatile, bool isNonTemporal, bool isInvariant,
4910 unsigned Alignment, const AAMDNodes &AAInfo,
4911 const MDNode *Ranges) {
4912 assert(Chain.getValueType() == MVT::Other &&
4913 "Invalid chain type");
4914 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4915 Alignment = getEVTAlignment(VT);
4917 unsigned Flags = MachineMemOperand::MOLoad;
4919 Flags |= MachineMemOperand::MOVolatile;
4921 Flags |= MachineMemOperand::MONonTemporal;
4923 Flags |= MachineMemOperand::MOInvariant;
4925 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4927 if (PtrInfo.V.isNull())
4928 PtrInfo = InferPointerInfo(Ptr, Offset);
4930 MachineFunction &MF = getMachineFunction();
4931 MachineMemOperand *MMO =
4932 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4934 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4938 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4939 EVT VT, SDLoc dl, SDValue Chain,
4940 SDValue Ptr, SDValue Offset, EVT MemVT,
4941 MachineMemOperand *MMO) {
4943 ExtType = ISD::NON_EXTLOAD;
4944 } else if (ExtType == ISD::NON_EXTLOAD) {
4945 assert(VT == MemVT && "Non-extending load from different memory type!");
4948 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4949 "Should only be an extending load, not truncating!");
4950 assert(VT.isInteger() == MemVT.isInteger() &&
4951 "Cannot convert from FP to Int or Int -> FP!");
4952 assert(VT.isVector() == MemVT.isVector() &&
4953 "Cannot use an ext load to convert to or from a vector!");
4954 assert((!VT.isVector() ||
4955 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4956 "Cannot use an ext load to change the number of vector elements!");
4959 bool Indexed = AM != ISD::UNINDEXED;
4960 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4961 "Unindexed load with an offset!");
4963 SDVTList VTs = Indexed ?
4964 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4965 SDValue Ops[] = { Chain, Ptr, Offset };
4966 FoldingSetNodeID ID;
4967 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4968 ID.AddInteger(MemVT.getRawBits());
4969 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4970 MMO->isNonTemporal(),
4971 MMO->isInvariant()));
4972 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4974 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4975 cast<LoadSDNode>(E)->refineAlignment(MMO);
4976 return SDValue(E, 0);
4978 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4979 dl.getDebugLoc(), VTs, AM, ExtType,
4981 CSEMap.InsertNode(N, IP);
4983 return SDValue(N, 0);
4986 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4987 SDValue Chain, SDValue Ptr,
4988 MachinePointerInfo PtrInfo,
4989 bool isVolatile, bool isNonTemporal,
4990 bool isInvariant, unsigned Alignment,
4991 const AAMDNodes &AAInfo,
4992 const MDNode *Ranges) {
4993 SDValue Undef = getUNDEF(Ptr.getValueType());
4994 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4995 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4999 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5000 SDValue Chain, SDValue Ptr,
5001 MachineMemOperand *MMO) {
5002 SDValue Undef = getUNDEF(Ptr.getValueType());
5003 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5007 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5008 SDValue Chain, SDValue Ptr,
5009 MachinePointerInfo PtrInfo, EVT MemVT,
5010 bool isVolatile, bool isNonTemporal,
5011 bool isInvariant, unsigned Alignment,
5012 const AAMDNodes &AAInfo) {
5013 SDValue Undef = getUNDEF(Ptr.getValueType());
5014 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5015 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5020 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5021 SDValue Chain, SDValue Ptr, EVT MemVT,
5022 MachineMemOperand *MMO) {
5023 SDValue Undef = getUNDEF(Ptr.getValueType());
5024 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5029 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5030 SDValue Offset, ISD::MemIndexedMode AM) {
5031 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5032 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5033 "Load is already a indexed load!");
5034 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5035 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5036 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5037 false, LD->getAlignment());
5040 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5041 SDValue Ptr, MachinePointerInfo PtrInfo,
5042 bool isVolatile, bool isNonTemporal,
5043 unsigned Alignment, const AAMDNodes &AAInfo) {
5044 assert(Chain.getValueType() == MVT::Other &&
5045 "Invalid chain type");
5046 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5047 Alignment = getEVTAlignment(Val.getValueType());
5049 unsigned Flags = MachineMemOperand::MOStore;
5051 Flags |= MachineMemOperand::MOVolatile;
5053 Flags |= MachineMemOperand::MONonTemporal;
5055 if (PtrInfo.V.isNull())
5056 PtrInfo = InferPointerInfo(Ptr);
5058 MachineFunction &MF = getMachineFunction();
5059 MachineMemOperand *MMO =
5060 MF.getMachineMemOperand(PtrInfo, Flags,
5061 Val.getValueType().getStoreSize(), Alignment,
5064 return getStore(Chain, dl, Val, Ptr, MMO);
5067 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5068 SDValue Ptr, MachineMemOperand *MMO) {
5069 assert(Chain.getValueType() == MVT::Other &&
5070 "Invalid chain type");
5071 EVT VT = Val.getValueType();
5072 SDVTList VTs = getVTList(MVT::Other);
5073 SDValue Undef = getUNDEF(Ptr.getValueType());
5074 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5075 FoldingSetNodeID ID;
5076 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5077 ID.AddInteger(VT.getRawBits());
5078 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5079 MMO->isNonTemporal(), MMO->isInvariant()));
5080 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5082 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5083 cast<StoreSDNode>(E)->refineAlignment(MMO);
5084 return SDValue(E, 0);
5086 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5087 dl.getDebugLoc(), VTs,
5088 ISD::UNINDEXED, false, VT, MMO);
5089 CSEMap.InsertNode(N, IP);
5091 return SDValue(N, 0);
5094 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5095 SDValue Ptr, MachinePointerInfo PtrInfo,
5096 EVT SVT,bool isVolatile, bool isNonTemporal,
5098 const AAMDNodes &AAInfo) {
5099 assert(Chain.getValueType() == MVT::Other &&
5100 "Invalid chain type");
5101 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5102 Alignment = getEVTAlignment(SVT);
5104 unsigned Flags = MachineMemOperand::MOStore;
5106 Flags |= MachineMemOperand::MOVolatile;
5108 Flags |= MachineMemOperand::MONonTemporal;
5110 if (PtrInfo.V.isNull())
5111 PtrInfo = InferPointerInfo(Ptr);
5113 MachineFunction &MF = getMachineFunction();
5114 MachineMemOperand *MMO =
5115 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5118 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5121 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5122 SDValue Ptr, EVT SVT,
5123 MachineMemOperand *MMO) {
5124 EVT VT = Val.getValueType();
5126 assert(Chain.getValueType() == MVT::Other &&
5127 "Invalid chain type");
5129 return getStore(Chain, dl, Val, Ptr, MMO);
5131 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5132 "Should only be a truncating store, not extending!");
5133 assert(VT.isInteger() == SVT.isInteger() &&
5134 "Can't do FP-INT conversion!");
5135 assert(VT.isVector() == SVT.isVector() &&
5136 "Cannot use trunc store to convert to or from a vector!");
5137 assert((!VT.isVector() ||
5138 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5139 "Cannot use trunc store to change the number of vector elements!");
5141 SDVTList VTs = getVTList(MVT::Other);
5142 SDValue Undef = getUNDEF(Ptr.getValueType());
5143 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5144 FoldingSetNodeID ID;
5145 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5146 ID.AddInteger(SVT.getRawBits());
5147 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5148 MMO->isNonTemporal(), MMO->isInvariant()));
5149 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5151 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5152 cast<StoreSDNode>(E)->refineAlignment(MMO);
5153 return SDValue(E, 0);
5155 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5156 dl.getDebugLoc(), VTs,
5157 ISD::UNINDEXED, true, SVT, MMO);
5158 CSEMap.InsertNode(N, IP);
5160 return SDValue(N, 0);
5164 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5165 SDValue Offset, ISD::MemIndexedMode AM) {
5166 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5167 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5168 "Store is already a indexed store!");
5169 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5170 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5171 FoldingSetNodeID ID;
5172 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5173 ID.AddInteger(ST->getMemoryVT().getRawBits());
5174 ID.AddInteger(ST->getRawSubclassData());
5175 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5177 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5178 return SDValue(E, 0);
5180 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5181 dl.getDebugLoc(), VTs, AM,
5182 ST->isTruncatingStore(),
5184 ST->getMemOperand());
5185 CSEMap.InsertNode(N, IP);
5187 return SDValue(N, 0);
5191 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5192 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5193 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5195 SDVTList VTs = getVTList(VT, MVT::Other);
5196 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5197 FoldingSetNodeID ID;
5198 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5199 ID.AddInteger(VT.getRawBits());
5200 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5202 MMO->isNonTemporal(),
5203 MMO->isInvariant()));
5204 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5206 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5207 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5208 return SDValue(E, 0);
5210 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5211 dl.getDebugLoc(), Ops, 4, VTs,
5213 CSEMap.InsertNode(N, IP);
5215 return SDValue(N, 0);
5218 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5219 SDValue Ptr, SDValue Mask, EVT MemVT,
5220 MachineMemOperand *MMO, bool isTrunc) {
5221 assert(Chain.getValueType() == MVT::Other &&
5222 "Invalid chain type");
5223 EVT VT = Val.getValueType();
5224 SDVTList VTs = getVTList(MVT::Other);
5225 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5226 FoldingSetNodeID ID;
5227 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5228 ID.AddInteger(VT.getRawBits());
5229 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5230 MMO->isNonTemporal(), MMO->isInvariant()));
5231 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5233 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5234 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5235 return SDValue(E, 0);
5237 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5238 dl.getDebugLoc(), Ops, 4,
5239 VTs, isTrunc, MemVT, MMO);
5240 CSEMap.InsertNode(N, IP);
5242 return SDValue(N, 0);
5246 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5247 ArrayRef<SDValue> Ops,
5248 MachineMemOperand *MMO) {
5250 FoldingSetNodeID ID;
5251 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5252 ID.AddInteger(VT.getRawBits());
5253 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5255 MMO->isNonTemporal(),
5256 MMO->isInvariant()));
5257 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5259 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5260 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5261 return SDValue(E, 0);
5263 MaskedGatherSDNode *N =
5264 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5266 CSEMap.InsertNode(N, IP);
5268 return SDValue(N, 0);
5271 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5272 ArrayRef<SDValue> Ops,
5273 MachineMemOperand *MMO) {
5274 FoldingSetNodeID ID;
5275 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5276 ID.AddInteger(VT.getRawBits());
5277 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5278 MMO->isNonTemporal(),
5279 MMO->isInvariant()));
5280 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5282 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5283 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5284 return SDValue(E, 0);
5287 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5289 CSEMap.InsertNode(N, IP);
5291 return SDValue(N, 0);
5294 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5295 SDValue Chain, SDValue Ptr,
5298 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5299 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5302 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5303 ArrayRef<SDUse> Ops) {
5304 switch (Ops.size()) {
5305 case 0: return getNode(Opcode, DL, VT);
5306 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5307 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5308 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5312 // Copy from an SDUse array into an SDValue array for use with
5313 // the regular getNode logic.
5314 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5315 return getNode(Opcode, DL, VT, NewOps);
5318 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5319 ArrayRef<SDValue> Ops) {
5320 unsigned NumOps = Ops.size();
5322 case 0: return getNode(Opcode, DL, VT);
5323 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5324 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5325 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5331 case ISD::SELECT_CC: {
5332 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5333 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5334 "LHS and RHS of condition must have same type!");
5335 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5336 "True and False arms of SelectCC must have same type!");
5337 assert(Ops[2].getValueType() == VT &&
5338 "select_cc node must be of same type as true and false value!");
5342 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5343 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5344 "LHS/RHS of comparison should match types!");
5351 SDVTList VTs = getVTList(VT);
5353 if (VT != MVT::Glue) {
5354 FoldingSetNodeID ID;
5355 AddNodeIDNode(ID, Opcode, VTs, Ops);
5358 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5359 return SDValue(E, 0);
5361 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5363 CSEMap.InsertNode(N, IP);
5365 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5370 return SDValue(N, 0);
5373 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5374 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5375 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5378 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5379 ArrayRef<SDValue> Ops) {
5380 if (VTList.NumVTs == 1)
5381 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5385 // FIXME: figure out how to safely handle things like
5386 // int foo(int x) { return 1 << (x & 255); }
5387 // int bar() { return foo(256); }
5388 case ISD::SRA_PARTS:
5389 case ISD::SRL_PARTS:
5390 case ISD::SHL_PARTS:
5391 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5392 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5393 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5394 else if (N3.getOpcode() == ISD::AND)
5395 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5396 // If the and is only masking out bits that cannot effect the shift,
5397 // eliminate the and.
5398 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5399 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5400 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5406 // Memoize the node unless it returns a flag.
5408 unsigned NumOps = Ops.size();
5409 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5410 FoldingSetNodeID ID;
5411 AddNodeIDNode(ID, Opcode, VTList, Ops);
5413 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5414 return SDValue(E, 0);
5417 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5418 DL.getDebugLoc(), VTList, Ops[0]);
5419 } else if (NumOps == 2) {
5420 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5421 DL.getDebugLoc(), VTList, Ops[0],
5423 } else if (NumOps == 3) {
5424 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5425 DL.getDebugLoc(), VTList, Ops[0],
5428 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5431 CSEMap.InsertNode(N, IP);
5434 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5435 DL.getDebugLoc(), VTList, Ops[0]);
5436 } else if (NumOps == 2) {
5437 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5438 DL.getDebugLoc(), VTList, Ops[0],
5440 } else if (NumOps == 3) {
5441 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5442 DL.getDebugLoc(), VTList, Ops[0],
5445 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5450 return SDValue(N, 0);
5453 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5454 return getNode(Opcode, DL, VTList, None);
5457 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5459 SDValue Ops[] = { N1 };
5460 return getNode(Opcode, DL, VTList, Ops);
5463 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5464 SDValue N1, SDValue N2) {
5465 SDValue Ops[] = { N1, N2 };
5466 return getNode(Opcode, DL, VTList, Ops);
5469 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5470 SDValue N1, SDValue N2, SDValue N3) {
5471 SDValue Ops[] = { N1, N2, N3 };
5472 return getNode(Opcode, DL, VTList, Ops);
5475 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5476 SDValue N1, SDValue N2, SDValue N3,
5478 SDValue Ops[] = { N1, N2, N3, N4 };
5479 return getNode(Opcode, DL, VTList, Ops);
5482 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5483 SDValue N1, SDValue N2, SDValue N3,
5484 SDValue N4, SDValue N5) {
5485 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5486 return getNode(Opcode, DL, VTList, Ops);
5489 SDVTList SelectionDAG::getVTList(EVT VT) {
5490 return makeVTList(SDNode::getValueTypeList(VT), 1);
5493 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5494 FoldingSetNodeID ID;
5496 ID.AddInteger(VT1.getRawBits());
5497 ID.AddInteger(VT2.getRawBits());
5500 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5502 EVT *Array = Allocator.Allocate<EVT>(2);
5505 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5506 VTListMap.InsertNode(Result, IP);
5508 return Result->getSDVTList();
5511 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5512 FoldingSetNodeID ID;
5514 ID.AddInteger(VT1.getRawBits());
5515 ID.AddInteger(VT2.getRawBits());
5516 ID.AddInteger(VT3.getRawBits());
5519 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5521 EVT *Array = Allocator.Allocate<EVT>(3);
5525 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5526 VTListMap.InsertNode(Result, IP);
5528 return Result->getSDVTList();
5531 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5532 FoldingSetNodeID ID;
5534 ID.AddInteger(VT1.getRawBits());
5535 ID.AddInteger(VT2.getRawBits());
5536 ID.AddInteger(VT3.getRawBits());
5537 ID.AddInteger(VT4.getRawBits());
5540 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5542 EVT *Array = Allocator.Allocate<EVT>(4);
5547 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5548 VTListMap.InsertNode(Result, IP);
5550 return Result->getSDVTList();
5553 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5554 unsigned NumVTs = VTs.size();
5555 FoldingSetNodeID ID;
5556 ID.AddInteger(NumVTs);
5557 for (unsigned index = 0; index < NumVTs; index++) {
5558 ID.AddInteger(VTs[index].getRawBits());
5562 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5564 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5565 std::copy(VTs.begin(), VTs.end(), Array);
5566 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5567 VTListMap.InsertNode(Result, IP);
5569 return Result->getSDVTList();
5573 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5574 /// specified operands. If the resultant node already exists in the DAG,
5575 /// this does not modify the specified node, instead it returns the node that
5576 /// already exists. If the resultant node does not exist in the DAG, the
5577 /// input node is returned. As a degenerate case, if you specify the same
5578 /// input operands as the node already has, the input node is returned.
5579 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5580 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5582 // Check to see if there is no change.
5583 if (Op == N->getOperand(0)) return N;
5585 // See if the modified node already exists.
5586 void *InsertPos = nullptr;
5587 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5590 // Nope it doesn't. Remove the node from its current place in the maps.
5592 if (!RemoveNodeFromCSEMaps(N))
5593 InsertPos = nullptr;
5595 // Now we update the operands.
5596 N->OperandList[0].set(Op);
5598 // If this gets put into a CSE map, add it.
5599 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5603 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5604 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5606 // Check to see if there is no change.
5607 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5608 return N; // No operands changed, just return the input node.
5610 // See if the modified node already exists.
5611 void *InsertPos = nullptr;
5612 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5615 // Nope it doesn't. Remove the node from its current place in the maps.
5617 if (!RemoveNodeFromCSEMaps(N))
5618 InsertPos = nullptr;
5620 // Now we update the operands.
5621 if (N->OperandList[0] != Op1)
5622 N->OperandList[0].set(Op1);
5623 if (N->OperandList[1] != Op2)
5624 N->OperandList[1].set(Op2);
5626 // If this gets put into a CSE map, add it.
5627 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5631 SDNode *SelectionDAG::
5632 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5633 SDValue Ops[] = { Op1, Op2, Op3 };
5634 return UpdateNodeOperands(N, Ops);
5637 SDNode *SelectionDAG::
5638 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5639 SDValue Op3, SDValue Op4) {
5640 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5641 return UpdateNodeOperands(N, Ops);
5644 SDNode *SelectionDAG::
5645 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5646 SDValue Op3, SDValue Op4, SDValue Op5) {
5647 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5648 return UpdateNodeOperands(N, Ops);
5651 SDNode *SelectionDAG::
5652 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5653 unsigned NumOps = Ops.size();
5654 assert(N->getNumOperands() == NumOps &&
5655 "Update with wrong number of operands");
5657 // If no operands changed just return the input node.
5658 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5661 // See if the modified node already exists.
5662 void *InsertPos = nullptr;
5663 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5666 // Nope it doesn't. Remove the node from its current place in the maps.
5668 if (!RemoveNodeFromCSEMaps(N))
5669 InsertPos = nullptr;
5671 // Now we update the operands.
5672 for (unsigned i = 0; i != NumOps; ++i)
5673 if (N->OperandList[i] != Ops[i])
5674 N->OperandList[i].set(Ops[i]);
5676 // If this gets put into a CSE map, add it.
5677 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5681 /// DropOperands - Release the operands and set this node to have
5683 void SDNode::DropOperands() {
5684 // Unlike the code in MorphNodeTo that does this, we don't need to
5685 // watch for dead nodes here.
5686 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5692 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5695 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5697 SDVTList VTs = getVTList(VT);
5698 return SelectNodeTo(N, MachineOpc, VTs, None);
5701 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5702 EVT VT, SDValue Op1) {
5703 SDVTList VTs = getVTList(VT);
5704 SDValue Ops[] = { Op1 };
5705 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5708 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5709 EVT VT, SDValue Op1,
5711 SDVTList VTs = getVTList(VT);
5712 SDValue Ops[] = { Op1, Op2 };
5713 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5716 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5717 EVT VT, SDValue Op1,
5718 SDValue Op2, SDValue Op3) {
5719 SDVTList VTs = getVTList(VT);
5720 SDValue Ops[] = { Op1, Op2, Op3 };
5721 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5724 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5725 EVT VT, ArrayRef<SDValue> Ops) {
5726 SDVTList VTs = getVTList(VT);
5727 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5730 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5731 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5732 SDVTList VTs = getVTList(VT1, VT2);
5733 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5736 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5738 SDVTList VTs = getVTList(VT1, VT2);
5739 return SelectNodeTo(N, MachineOpc, VTs, None);
5742 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5743 EVT VT1, EVT VT2, EVT VT3,
5744 ArrayRef<SDValue> Ops) {
5745 SDVTList VTs = getVTList(VT1, VT2, VT3);
5746 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5749 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5750 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5751 ArrayRef<SDValue> Ops) {
5752 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5753 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5756 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5759 SDVTList VTs = getVTList(VT1, VT2);
5760 SDValue Ops[] = { Op1 };
5761 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5764 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5766 SDValue Op1, SDValue Op2) {
5767 SDVTList VTs = getVTList(VT1, VT2);
5768 SDValue Ops[] = { Op1, Op2 };
5769 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5772 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5774 SDValue Op1, SDValue Op2,
5776 SDVTList VTs = getVTList(VT1, VT2);
5777 SDValue Ops[] = { Op1, Op2, Op3 };
5778 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5781 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5782 EVT VT1, EVT VT2, EVT VT3,
5783 SDValue Op1, SDValue Op2,
5785 SDVTList VTs = getVTList(VT1, VT2, VT3);
5786 SDValue Ops[] = { Op1, Op2, Op3 };
5787 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5790 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5791 SDVTList VTs,ArrayRef<SDValue> Ops) {
5792 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5793 // Reset the NodeID to -1.
5798 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5799 /// the line number information on the merged node since it is not possible to
5800 /// preserve the information that operation is associated with multiple lines.
5801 /// This will make the debugger working better at -O0, were there is a higher
5802 /// probability having other instructions associated with that line.
5804 /// For IROrder, we keep the smaller of the two
5805 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5806 DebugLoc NLoc = N->getDebugLoc();
5807 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5808 N->setDebugLoc(DebugLoc());
5810 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5811 N->setIROrder(Order);
5815 /// MorphNodeTo - This *mutates* the specified node to have the specified
5816 /// return type, opcode, and operands.
5818 /// Note that MorphNodeTo returns the resultant node. If there is already a
5819 /// node of the specified opcode and operands, it returns that node instead of
5820 /// the current one. Note that the SDLoc need not be the same.
5822 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5823 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5824 /// node, and because it doesn't require CSE recalculation for any of
5825 /// the node's users.
5827 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5828 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5829 /// the legalizer which maintain worklists that would need to be updated when
5830 /// deleting things.
5831 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5832 SDVTList VTs, ArrayRef<SDValue> Ops) {
5833 unsigned NumOps = Ops.size();
5834 // If an identical node already exists, use it.
5836 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5837 FoldingSetNodeID ID;
5838 AddNodeIDNode(ID, Opc, VTs, Ops);
5839 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5840 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5843 if (!RemoveNodeFromCSEMaps(N))
5846 // Start the morphing.
5848 N->ValueList = VTs.VTs;
5849 N->NumValues = VTs.NumVTs;
5851 // Clear the operands list, updating used nodes to remove this from their
5852 // use list. Keep track of any operands that become dead as a result.
5853 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5854 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5856 SDNode *Used = Use.getNode();
5858 if (Used->use_empty())
5859 DeadNodeSet.insert(Used);
5862 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5863 // Initialize the memory references information.
5864 MN->setMemRefs(nullptr, nullptr);
5865 // If NumOps is larger than the # of operands we can have in a
5866 // MachineSDNode, reallocate the operand list.
5867 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5868 if (MN->OperandsNeedDelete)
5869 delete[] MN->OperandList;
5870 if (NumOps > array_lengthof(MN->LocalOperands))
5871 // We're creating a final node that will live unmorphed for the
5872 // remainder of the current SelectionDAG iteration, so we can allocate
5873 // the operands directly out of a pool with no recycling metadata.
5874 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5875 Ops.data(), NumOps);
5877 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5878 MN->OperandsNeedDelete = false;
5880 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5882 // If NumOps is larger than the # of operands we currently have, reallocate
5883 // the operand list.
5884 if (NumOps > N->NumOperands) {
5885 if (N->OperandsNeedDelete)
5886 delete[] N->OperandList;
5887 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5888 N->OperandsNeedDelete = true;
5890 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5893 // Delete any nodes that are still dead after adding the uses for the
5895 if (!DeadNodeSet.empty()) {
5896 SmallVector<SDNode *, 16> DeadNodes;
5897 for (SDNode *N : DeadNodeSet)
5899 DeadNodes.push_back(N);
5900 RemoveDeadNodes(DeadNodes);
5904 CSEMap.InsertNode(N, IP); // Memoize the new node.
5909 /// getMachineNode - These are used for target selectors to create a new node
5910 /// with specified return type(s), MachineInstr opcode, and operands.
5912 /// Note that getMachineNode returns the resultant node. If there is already a
5913 /// node of the specified opcode and operands, it returns that node instead of
5914 /// the current one.
5916 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5917 SDVTList VTs = getVTList(VT);
5918 return getMachineNode(Opcode, dl, VTs, None);
5922 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5923 SDVTList VTs = getVTList(VT);
5924 SDValue Ops[] = { Op1 };
5925 return getMachineNode(Opcode, dl, VTs, Ops);
5929 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5930 SDValue Op1, SDValue Op2) {
5931 SDVTList VTs = getVTList(VT);
5932 SDValue Ops[] = { Op1, Op2 };
5933 return getMachineNode(Opcode, dl, VTs, Ops);
5937 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5938 SDValue Op1, SDValue Op2, SDValue Op3) {
5939 SDVTList VTs = getVTList(VT);
5940 SDValue Ops[] = { Op1, Op2, Op3 };
5941 return getMachineNode(Opcode, dl, VTs, Ops);
5945 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5946 ArrayRef<SDValue> Ops) {
5947 SDVTList VTs = getVTList(VT);
5948 return getMachineNode(Opcode, dl, VTs, Ops);
5952 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5953 SDVTList VTs = getVTList(VT1, VT2);
5954 return getMachineNode(Opcode, dl, VTs, None);
5958 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5959 EVT VT1, EVT VT2, SDValue Op1) {
5960 SDVTList VTs = getVTList(VT1, VT2);
5961 SDValue Ops[] = { Op1 };
5962 return getMachineNode(Opcode, dl, VTs, Ops);
5966 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5967 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5968 SDVTList VTs = getVTList(VT1, VT2);
5969 SDValue Ops[] = { Op1, Op2 };
5970 return getMachineNode(Opcode, dl, VTs, Ops);
5974 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5975 EVT VT1, EVT VT2, SDValue Op1,
5976 SDValue Op2, SDValue Op3) {
5977 SDVTList VTs = getVTList(VT1, VT2);
5978 SDValue Ops[] = { Op1, Op2, Op3 };
5979 return getMachineNode(Opcode, dl, VTs, Ops);
5983 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5985 ArrayRef<SDValue> Ops) {
5986 SDVTList VTs = getVTList(VT1, VT2);
5987 return getMachineNode(Opcode, dl, VTs, Ops);
5991 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5992 EVT VT1, EVT VT2, EVT VT3,
5993 SDValue Op1, SDValue Op2) {
5994 SDVTList VTs = getVTList(VT1, VT2, VT3);
5995 SDValue Ops[] = { Op1, Op2 };
5996 return getMachineNode(Opcode, dl, VTs, Ops);
6000 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6001 EVT VT1, EVT VT2, EVT VT3,
6002 SDValue Op1, SDValue Op2, SDValue Op3) {
6003 SDVTList VTs = getVTList(VT1, VT2, VT3);
6004 SDValue Ops[] = { Op1, Op2, Op3 };
6005 return getMachineNode(Opcode, dl, VTs, Ops);
6009 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6010 EVT VT1, EVT VT2, EVT VT3,
6011 ArrayRef<SDValue> Ops) {
6012 SDVTList VTs = getVTList(VT1, VT2, VT3);
6013 return getMachineNode(Opcode, dl, VTs, Ops);
6017 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6018 EVT VT2, EVT VT3, EVT VT4,
6019 ArrayRef<SDValue> Ops) {
6020 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6021 return getMachineNode(Opcode, dl, VTs, Ops);
6025 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6026 ArrayRef<EVT> ResultTys,
6027 ArrayRef<SDValue> Ops) {
6028 SDVTList VTs = getVTList(ResultTys);
6029 return getMachineNode(Opcode, dl, VTs, Ops);
6033 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6034 ArrayRef<SDValue> OpsArray) {
6035 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6038 const SDValue *Ops = OpsArray.data();
6039 unsigned NumOps = OpsArray.size();
6042 FoldingSetNodeID ID;
6043 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6045 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6046 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6050 // Allocate a new MachineSDNode.
6051 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6052 DL.getDebugLoc(), VTs);
6054 // Initialize the operands list.
6055 if (NumOps > array_lengthof(N->LocalOperands))
6056 // We're creating a final node that will live unmorphed for the
6057 // remainder of the current SelectionDAG iteration, so we can allocate
6058 // the operands directly out of a pool with no recycling metadata.
6059 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6062 N->InitOperands(N->LocalOperands, Ops, NumOps);
6063 N->OperandsNeedDelete = false;
6066 CSEMap.InsertNode(N, IP);
6072 /// getTargetExtractSubreg - A convenience function for creating
6073 /// TargetOpcode::EXTRACT_SUBREG nodes.
6075 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6077 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6078 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6079 VT, Operand, SRIdxVal);
6080 return SDValue(Subreg, 0);
6083 /// getTargetInsertSubreg - A convenience function for creating
6084 /// TargetOpcode::INSERT_SUBREG nodes.
6086 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6087 SDValue Operand, SDValue Subreg) {
6088 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6089 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6090 VT, Operand, Subreg, SRIdxVal);
6091 return SDValue(Result, 0);
6094 /// getNodeIfExists - Get the specified node if it's already available, or
6095 /// else return NULL.
6096 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6097 ArrayRef<SDValue> Ops,
6098 const SDNodeFlags *Flags) {
6099 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6100 FoldingSetNodeID ID;
6101 AddNodeIDNode(ID, Opcode, VTList, Ops);
6102 AddNodeIDFlags(ID, Opcode, Flags);
6104 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6110 /// getDbgValue - Creates a SDDbgValue node.
6113 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6114 unsigned R, bool IsIndirect, uint64_t Off,
6115 DebugLoc DL, unsigned O) {
6116 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6117 "Expected inlined-at fields to agree");
6118 return new (DbgInfo->getAlloc())
6119 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6123 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6124 const Value *C, uint64_t Off,
6125 DebugLoc DL, unsigned O) {
6126 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6127 "Expected inlined-at fields to agree");
6128 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6132 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6133 unsigned FI, uint64_t Off,
6134 DebugLoc DL, unsigned O) {
6135 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6136 "Expected inlined-at fields to agree");
6137 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6142 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6143 /// pointed to by a use iterator is deleted, increment the use iterator
6144 /// so that it doesn't dangle.
6146 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6147 SDNode::use_iterator &UI;
6148 SDNode::use_iterator &UE;
6150 void NodeDeleted(SDNode *N, SDNode *E) override {
6151 // Increment the iterator as needed.
6152 while (UI != UE && N == *UI)
6157 RAUWUpdateListener(SelectionDAG &d,
6158 SDNode::use_iterator &ui,
6159 SDNode::use_iterator &ue)
6160 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6165 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6166 /// This can cause recursive merging of nodes in the DAG.
6168 /// This version assumes From has a single result value.
6170 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6171 SDNode *From = FromN.getNode();
6172 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6173 "Cannot replace with this method!");
6174 assert(From != To.getNode() && "Cannot replace uses of with self");
6176 // Iterate over all the existing uses of From. New uses will be added
6177 // to the beginning of the use list, which we avoid visiting.
6178 // This specifically avoids visiting uses of From that arise while the
6179 // replacement is happening, because any such uses would be the result
6180 // of CSE: If an existing node looks like From after one of its operands
6181 // is replaced by To, we don't want to replace of all its users with To
6182 // too. See PR3018 for more info.
6183 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6184 RAUWUpdateListener Listener(*this, UI, UE);
6188 // This node is about to morph, remove its old self from the CSE maps.
6189 RemoveNodeFromCSEMaps(User);
6191 // A user can appear in a use list multiple times, and when this
6192 // happens the uses are usually next to each other in the list.
6193 // To help reduce the number of CSE recomputations, process all
6194 // the uses of this user that we can find this way.
6196 SDUse &Use = UI.getUse();
6199 } while (UI != UE && *UI == User);
6201 // Now that we have modified User, add it back to the CSE maps. If it
6202 // already exists there, recursively merge the results together.
6203 AddModifiedNodeToCSEMaps(User);
6206 // If we just RAUW'd the root, take note.
6207 if (FromN == getRoot())
6211 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6212 /// This can cause recursive merging of nodes in the DAG.
6214 /// This version assumes that for each value of From, there is a
6215 /// corresponding value in To in the same position with the same type.
6217 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6219 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6220 assert((!From->hasAnyUseOfValue(i) ||
6221 From->getValueType(i) == To->getValueType(i)) &&
6222 "Cannot use this version of ReplaceAllUsesWith!");
6225 // Handle the trivial case.
6229 // Iterate over just the existing users of From. See the comments in
6230 // the ReplaceAllUsesWith above.
6231 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6232 RAUWUpdateListener Listener(*this, UI, UE);
6236 // This node is about to morph, remove its old self from the CSE maps.
6237 RemoveNodeFromCSEMaps(User);
6239 // A user can appear in a use list multiple times, and when this
6240 // happens the uses are usually next to each other in the list.
6241 // To help reduce the number of CSE recomputations, process all
6242 // the uses of this user that we can find this way.
6244 SDUse &Use = UI.getUse();
6247 } while (UI != UE && *UI == User);
6249 // Now that we have modified User, add it back to the CSE maps. If it
6250 // already exists there, recursively merge the results together.
6251 AddModifiedNodeToCSEMaps(User);
6254 // If we just RAUW'd the root, take note.
6255 if (From == getRoot().getNode())
6256 setRoot(SDValue(To, getRoot().getResNo()));
6259 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6260 /// This can cause recursive merging of nodes in the DAG.
6262 /// This version can replace From with any result values. To must match the
6263 /// number and types of values returned by From.
6264 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6265 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6266 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6268 // Iterate over just the existing users of From. See the comments in
6269 // the ReplaceAllUsesWith above.
6270 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6271 RAUWUpdateListener Listener(*this, UI, UE);
6275 // This node is about to morph, remove its old self from the CSE maps.
6276 RemoveNodeFromCSEMaps(User);
6278 // A user can appear in a use list multiple times, and when this
6279 // happens the uses are usually next to each other in the list.
6280 // To help reduce the number of CSE recomputations, process all
6281 // the uses of this user that we can find this way.
6283 SDUse &Use = UI.getUse();
6284 const SDValue &ToOp = To[Use.getResNo()];
6287 } while (UI != UE && *UI == User);
6289 // Now that we have modified User, add it back to the CSE maps. If it
6290 // already exists there, recursively merge the results together.
6291 AddModifiedNodeToCSEMaps(User);
6294 // If we just RAUW'd the root, take note.
6295 if (From == getRoot().getNode())
6296 setRoot(SDValue(To[getRoot().getResNo()]));
6299 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6300 /// uses of other values produced by From.getNode() alone. The Deleted
6301 /// vector is handled the same way as for ReplaceAllUsesWith.
6302 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6303 // Handle the really simple, really trivial case efficiently.
6304 if (From == To) return;
6306 // Handle the simple, trivial, case efficiently.
6307 if (From.getNode()->getNumValues() == 1) {
6308 ReplaceAllUsesWith(From, To);
6312 // Iterate over just the existing users of From. See the comments in
6313 // the ReplaceAllUsesWith above.
6314 SDNode::use_iterator UI = From.getNode()->use_begin(),
6315 UE = From.getNode()->use_end();
6316 RAUWUpdateListener Listener(*this, UI, UE);
6319 bool UserRemovedFromCSEMaps = false;
6321 // A user can appear in a use list multiple times, and when this
6322 // happens the uses are usually next to each other in the list.
6323 // To help reduce the number of CSE recomputations, process all
6324 // the uses of this user that we can find this way.
6326 SDUse &Use = UI.getUse();
6328 // Skip uses of different values from the same node.
6329 if (Use.getResNo() != From.getResNo()) {
6334 // If this node hasn't been modified yet, it's still in the CSE maps,
6335 // so remove its old self from the CSE maps.
6336 if (!UserRemovedFromCSEMaps) {
6337 RemoveNodeFromCSEMaps(User);
6338 UserRemovedFromCSEMaps = true;
6343 } while (UI != UE && *UI == User);
6345 // We are iterating over all uses of the From node, so if a use
6346 // doesn't use the specific value, no changes are made.
6347 if (!UserRemovedFromCSEMaps)
6350 // Now that we have modified User, add it back to the CSE maps. If it
6351 // already exists there, recursively merge the results together.
6352 AddModifiedNodeToCSEMaps(User);
6355 // If we just RAUW'd the root, take note.
6356 if (From == getRoot())
6361 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6362 /// to record information about a use.
6369 /// operator< - Sort Memos by User.
6370 bool operator<(const UseMemo &L, const UseMemo &R) {
6371 return (intptr_t)L.User < (intptr_t)R.User;
6375 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6376 /// uses of other values produced by From.getNode() alone. The same value
6377 /// may appear in both the From and To list. The Deleted vector is
6378 /// handled the same way as for ReplaceAllUsesWith.
6379 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6382 // Handle the simple, trivial case efficiently.
6384 return ReplaceAllUsesOfValueWith(*From, *To);
6386 // Read up all the uses and make records of them. This helps
6387 // processing new uses that are introduced during the
6388 // replacement process.
6389 SmallVector<UseMemo, 4> Uses;
6390 for (unsigned i = 0; i != Num; ++i) {
6391 unsigned FromResNo = From[i].getResNo();
6392 SDNode *FromNode = From[i].getNode();
6393 for (SDNode::use_iterator UI = FromNode->use_begin(),
6394 E = FromNode->use_end(); UI != E; ++UI) {
6395 SDUse &Use = UI.getUse();
6396 if (Use.getResNo() == FromResNo) {
6397 UseMemo Memo = { *UI, i, &Use };
6398 Uses.push_back(Memo);
6403 // Sort the uses, so that all the uses from a given User are together.
6404 std::sort(Uses.begin(), Uses.end());
6406 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6407 UseIndex != UseIndexEnd; ) {
6408 // We know that this user uses some value of From. If it is the right
6409 // value, update it.
6410 SDNode *User = Uses[UseIndex].User;
6412 // This node is about to morph, remove its old self from the CSE maps.
6413 RemoveNodeFromCSEMaps(User);
6415 // The Uses array is sorted, so all the uses for a given User
6416 // are next to each other in the list.
6417 // To help reduce the number of CSE recomputations, process all
6418 // the uses of this user that we can find this way.
6420 unsigned i = Uses[UseIndex].Index;
6421 SDUse &Use = *Uses[UseIndex].Use;
6425 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6427 // Now that we have modified User, add it back to the CSE maps. If it
6428 // already exists there, recursively merge the results together.
6429 AddModifiedNodeToCSEMaps(User);
6433 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6434 /// based on their topological order. It returns the maximum id and a vector
6435 /// of the SDNodes* in assigned order by reference.
6436 unsigned SelectionDAG::AssignTopologicalOrder() {
6438 unsigned DAGSize = 0;
6440 // SortedPos tracks the progress of the algorithm. Nodes before it are
6441 // sorted, nodes after it are unsorted. When the algorithm completes
6442 // it is at the end of the list.
6443 allnodes_iterator SortedPos = allnodes_begin();
6445 // Visit all the nodes. Move nodes with no operands to the front of
6446 // the list immediately. Annotate nodes that do have operands with their
6447 // operand count. Before we do this, the Node Id fields of the nodes
6448 // may contain arbitrary values. After, the Node Id fields for nodes
6449 // before SortedPos will contain the topological sort index, and the
6450 // Node Id fields for nodes At SortedPos and after will contain the
6451 // count of outstanding operands.
6452 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6454 checkForCycles(N, this);
6455 unsigned Degree = N->getNumOperands();
6457 // A node with no uses, add it to the result array immediately.
6458 N->setNodeId(DAGSize++);
6459 allnodes_iterator Q = N;
6461 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6462 assert(SortedPos != AllNodes.end() && "Overran node list");
6465 // Temporarily use the Node Id as scratch space for the degree count.
6466 N->setNodeId(Degree);
6470 // Visit all the nodes. As we iterate, move nodes into sorted order,
6471 // such that by the time the end is reached all nodes will be sorted.
6472 for (SDNode &Node : allnodes()) {
6474 checkForCycles(N, this);
6475 // N is in sorted position, so all its uses have one less operand
6476 // that needs to be sorted.
6477 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6480 unsigned Degree = P->getNodeId();
6481 assert(Degree != 0 && "Invalid node degree");
6484 // All of P's operands are sorted, so P may sorted now.
6485 P->setNodeId(DAGSize++);
6487 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6488 assert(SortedPos != AllNodes.end() && "Overran node list");
6491 // Update P's outstanding operand count.
6492 P->setNodeId(Degree);
6495 if (&Node == SortedPos) {
6497 allnodes_iterator I = N;
6499 dbgs() << "Overran sorted position:\n";
6500 S->dumprFull(this); dbgs() << "\n";
6501 dbgs() << "Checking if this is due to cycles\n";
6502 checkForCycles(this, true);
6504 llvm_unreachable(nullptr);
6508 assert(SortedPos == AllNodes.end() &&
6509 "Topological sort incomplete!");
6510 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6511 "First node in topological sort is not the entry token!");
6512 assert(AllNodes.front().getNodeId() == 0 &&
6513 "First node in topological sort has non-zero id!");
6514 assert(AllNodes.front().getNumOperands() == 0 &&
6515 "First node in topological sort has operands!");
6516 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6517 "Last node in topologic sort has unexpected id!");
6518 assert(AllNodes.back().use_empty() &&
6519 "Last node in topologic sort has users!");
6520 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6524 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6525 /// value is produced by SD.
6526 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6528 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6529 SD->setHasDebugValue(true);
6531 DbgInfo->add(DB, SD, isParameter);
6534 /// TransferDbgValues - Transfer SDDbgValues.
6535 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6536 if (From == To || !From.getNode()->getHasDebugValue())
6538 SDNode *FromNode = From.getNode();
6539 SDNode *ToNode = To.getNode();
6540 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6541 SmallVector<SDDbgValue *, 2> ClonedDVs;
6542 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6544 SDDbgValue *Dbg = *I;
6545 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6547 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6548 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6549 Dbg->getDebugLoc(), Dbg->getOrder());
6550 ClonedDVs.push_back(Clone);
6553 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6554 E = ClonedDVs.end(); I != E; ++I)
6555 AddDbgValue(*I, ToNode, false);
6558 //===----------------------------------------------------------------------===//
6560 //===----------------------------------------------------------------------===//
6562 HandleSDNode::~HandleSDNode() {
6566 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6567 DebugLoc DL, const GlobalValue *GA,
6568 EVT VT, int64_t o, unsigned char TF)
6569 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6573 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6574 SDValue X, unsigned SrcAS,
6576 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6577 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6579 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6580 EVT memvt, MachineMemOperand *mmo)
6581 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6582 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6583 MMO->isNonTemporal(), MMO->isInvariant());
6584 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6585 assert(isNonTemporal() == MMO->isNonTemporal() &&
6586 "Non-temporal encoding error!");
6587 // We check here that the size of the memory operand fits within the size of
6588 // the MMO. This is because the MMO might indicate only a possible address
6589 // range instead of specifying the affected memory addresses precisely.
6590 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6593 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6594 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6595 : SDNode(Opc, Order, dl, VTs, Ops),
6596 MemoryVT(memvt), MMO(mmo) {
6597 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6598 MMO->isNonTemporal(), MMO->isInvariant());
6599 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6600 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6603 /// Profile - Gather unique data for the node.
6605 void SDNode::Profile(FoldingSetNodeID &ID) const {
6606 AddNodeIDNode(ID, this);
6611 std::vector<EVT> VTs;
6614 VTs.reserve(MVT::LAST_VALUETYPE);
6615 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6616 VTs.push_back(MVT((MVT::SimpleValueType)i));
6621 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6622 static ManagedStatic<EVTArray> SimpleVTArray;
6623 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6625 /// getValueTypeList - Return a pointer to the specified value type.
6627 const EVT *SDNode::getValueTypeList(EVT VT) {
6628 if (VT.isExtended()) {
6629 sys::SmartScopedLock<true> Lock(*VTMutex);
6630 return &(*EVTs->insert(VT).first);
6632 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6633 "Value type out of range!");
6634 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6638 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6639 /// indicated value. This method ignores uses of other values defined by this
6641 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6642 assert(Value < getNumValues() && "Bad value!");
6644 // TODO: Only iterate over uses of a given value of the node
6645 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6646 if (UI.getUse().getResNo() == Value) {
6653 // Found exactly the right number of uses?
6658 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6659 /// value. This method ignores uses of other values defined by this operation.
6660 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6661 assert(Value < getNumValues() && "Bad value!");
6663 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6664 if (UI.getUse().getResNo() == Value)
6671 /// isOnlyUserOf - Return true if this node is the only use of N.
6673 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6675 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6686 /// isOperand - Return true if this node is an operand of N.
6688 bool SDValue::isOperandOf(const SDNode *N) const {
6689 for (const SDValue &Op : N->op_values())
6695 bool SDNode::isOperandOf(const SDNode *N) const {
6696 for (const SDValue &Op : N->op_values())
6697 if (this == Op.getNode())
6702 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6703 /// be a chain) reaches the specified operand without crossing any
6704 /// side-effecting instructions on any chain path. In practice, this looks
6705 /// through token factors and non-volatile loads. In order to remain efficient,
6706 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6707 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6708 unsigned Depth) const {
6709 if (*this == Dest) return true;
6711 // Don't search too deeply, we just want to be able to see through
6712 // TokenFactor's etc.
6713 if (Depth == 0) return false;
6715 // If this is a token factor, all inputs to the TF happen in parallel. If any
6716 // of the operands of the TF does not reach dest, then we cannot do the xform.
6717 if (getOpcode() == ISD::TokenFactor) {
6718 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6719 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6724 // Loads don't have side effects, look through them.
6725 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6726 if (!Ld->isVolatile())
6727 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6732 /// hasPredecessor - Return true if N is a predecessor of this node.
6733 /// N is either an operand of this node, or can be reached by recursively
6734 /// traversing up the operands.
6735 /// NOTE: This is an expensive method. Use it carefully.
6736 bool SDNode::hasPredecessor(const SDNode *N) const {
6737 SmallPtrSet<const SDNode *, 32> Visited;
6738 SmallVector<const SDNode *, 16> Worklist;
6739 return hasPredecessorHelper(N, Visited, Worklist);
6743 SDNode::hasPredecessorHelper(const SDNode *N,
6744 SmallPtrSetImpl<const SDNode *> &Visited,
6745 SmallVectorImpl<const SDNode *> &Worklist) const {
6746 if (Visited.empty()) {
6747 Worklist.push_back(this);
6749 // Take a look in the visited set. If we've already encountered this node
6750 // we needn't search further.
6751 if (Visited.count(N))
6755 // Haven't visited N yet. Continue the search.
6756 while (!Worklist.empty()) {
6757 const SDNode *M = Worklist.pop_back_val();
6758 for (const SDValue &OpV : M->op_values()) {
6759 SDNode *Op = OpV.getNode();
6760 if (Visited.insert(Op).second)
6761 Worklist.push_back(Op);
6770 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6771 assert(Num < NumOperands && "Invalid child # of SDNode!");
6772 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6775 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6776 assert(N->getNumValues() == 1 &&
6777 "Can't unroll a vector with multiple results!");
6779 EVT VT = N->getValueType(0);
6780 unsigned NE = VT.getVectorNumElements();
6781 EVT EltVT = VT.getVectorElementType();
6784 SmallVector<SDValue, 8> Scalars;
6785 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6787 // If ResNE is 0, fully unroll the vector op.
6790 else if (NE > ResNE)
6794 for (i= 0; i != NE; ++i) {
6795 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6796 SDValue Operand = N->getOperand(j);
6797 EVT OperandVT = Operand.getValueType();
6798 if (OperandVT.isVector()) {
6799 // A vector operand; extract a single element.
6800 EVT OperandEltVT = OperandVT.getVectorElementType();
6802 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6803 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6805 // A scalar operand; just use it as is.
6806 Operands[j] = Operand;
6810 switch (N->getOpcode()) {
6812 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6815 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6822 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6823 getShiftAmountOperand(Operands[0].getValueType(),
6826 case ISD::SIGN_EXTEND_INREG:
6827 case ISD::FP_ROUND_INREG: {
6828 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6829 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6831 getValueType(ExtVT)));
6836 for (; i < ResNE; ++i)
6837 Scalars.push_back(getUNDEF(EltVT));
6839 return getNode(ISD::BUILD_VECTOR, dl,
6840 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6844 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6845 /// location that is 'Dist' units away from the location that the 'Base' load
6846 /// is loading from.
6847 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6848 unsigned Bytes, int Dist) const {
6849 if (LD->getChain() != Base->getChain())
6851 EVT VT = LD->getValueType(0);
6852 if (VT.getSizeInBits() / 8 != Bytes)
6855 SDValue Loc = LD->getOperand(1);
6856 SDValue BaseLoc = Base->getOperand(1);
6857 if (Loc.getOpcode() == ISD::FrameIndex) {
6858 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6860 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6861 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6862 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6863 int FS = MFI->getObjectSize(FI);
6864 int BFS = MFI->getObjectSize(BFI);
6865 if (FS != BFS || FS != (int)Bytes) return false;
6866 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6870 if (isBaseWithConstantOffset(Loc)) {
6871 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6872 if (Loc.getOperand(0) == BaseLoc) {
6873 // If the base location is a simple address with no offset itself, then
6874 // the second load's first add operand should be the base address.
6875 if (LocOffset == Dist * (int)Bytes)
6877 } else if (isBaseWithConstantOffset(BaseLoc)) {
6878 // The base location itself has an offset, so subtract that value from the
6879 // second load's offset before comparing to distance * size.
6881 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6882 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6883 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6888 const GlobalValue *GV1 = nullptr;
6889 const GlobalValue *GV2 = nullptr;
6890 int64_t Offset1 = 0;
6891 int64_t Offset2 = 0;
6892 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6893 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6894 if (isGA1 && isGA2 && GV1 == GV2)
6895 return Offset1 == (Offset2 + Dist*Bytes);
6900 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6901 /// it cannot be inferred.
6902 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6903 // If this is a GlobalAddress + cst, return the alignment.
6904 const GlobalValue *GV;
6905 int64_t GVOffset = 0;
6906 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6907 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
6908 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6909 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6911 unsigned AlignBits = KnownZero.countTrailingOnes();
6912 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6914 return MinAlign(Align, GVOffset);
6917 // If this is a direct reference to a stack slot, use information about the
6918 // stack slot's alignment.
6919 int FrameIdx = 1 << 31;
6920 int64_t FrameOffset = 0;
6921 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6922 FrameIdx = FI->getIndex();
6923 } else if (isBaseWithConstantOffset(Ptr) &&
6924 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6926 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6927 FrameOffset = Ptr.getConstantOperandVal(1);
6930 if (FrameIdx != (1 << 31)) {
6931 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6932 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6940 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6941 /// which is split (or expanded) into two not necessarily identical pieces.
6942 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6943 // Currently all types are split in half.
6945 if (!VT.isVector()) {
6946 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6948 unsigned NumElements = VT.getVectorNumElements();
6949 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6950 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6953 return std::make_pair(LoVT, HiVT);
6956 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6958 std::pair<SDValue, SDValue>
6959 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6961 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6962 N.getValueType().getVectorNumElements() &&
6963 "More vector elements requested than available!");
6965 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6966 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
6967 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6968 getConstant(LoVT.getVectorNumElements(), DL,
6969 TLI->getVectorIdxTy(getDataLayout())));
6970 return std::make_pair(Lo, Hi);
6973 void SelectionDAG::ExtractVectorElements(SDValue Op,
6974 SmallVectorImpl<SDValue> &Args,
6975 unsigned Start, unsigned Count) {
6976 EVT VT = Op.getValueType();
6978 Count = VT.getVectorNumElements();
6980 EVT EltVT = VT.getVectorElementType();
6981 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
6983 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6984 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6985 Op, getConstant(i, SL, IdxTy)));
6989 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6990 unsigned GlobalAddressSDNode::getAddressSpace() const {
6991 return getGlobal()->getType()->getAddressSpace();
6995 Type *ConstantPoolSDNode::getType() const {
6996 if (isMachineConstantPoolEntry())
6997 return Val.MachineCPVal->getType();
6998 return Val.ConstVal->getType();
7001 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7003 unsigned &SplatBitSize,
7005 unsigned MinSplatBits,
7006 bool isBigEndian) const {
7007 EVT VT = getValueType(0);
7008 assert(VT.isVector() && "Expected a vector type");
7009 unsigned sz = VT.getSizeInBits();
7010 if (MinSplatBits > sz)
7013 SplatValue = APInt(sz, 0);
7014 SplatUndef = APInt(sz, 0);
7016 // Get the bits. Bits with undefined values (when the corresponding element
7017 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7018 // in SplatValue. If any of the values are not constant, give up and return
7020 unsigned int nOps = getNumOperands();
7021 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7022 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7024 for (unsigned j = 0; j < nOps; ++j) {
7025 unsigned i = isBigEndian ? nOps-1-j : j;
7026 SDValue OpVal = getOperand(i);
7027 unsigned BitPos = j * EltBitSize;
7029 if (OpVal.getOpcode() == ISD::UNDEF)
7030 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7031 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7032 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7033 zextOrTrunc(sz) << BitPos;
7034 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7035 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7040 // The build_vector is all constants or undefs. Find the smallest element
7041 // size that splats the vector.
7043 HasAnyUndefs = (SplatUndef != 0);
7046 unsigned HalfSize = sz / 2;
7047 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7048 APInt LowValue = SplatValue.trunc(HalfSize);
7049 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7050 APInt LowUndef = SplatUndef.trunc(HalfSize);
7052 // If the two halves do not match (ignoring undef bits), stop here.
7053 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7054 MinSplatBits > HalfSize)
7057 SplatValue = HighValue | LowValue;
7058 SplatUndef = HighUndef & LowUndef;
7067 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7068 if (UndefElements) {
7069 UndefElements->clear();
7070 UndefElements->resize(getNumOperands());
7073 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7074 SDValue Op = getOperand(i);
7075 if (Op.getOpcode() == ISD::UNDEF) {
7077 (*UndefElements)[i] = true;
7078 } else if (!Splatted) {
7080 } else if (Splatted != Op) {
7086 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7087 "Can only have a splat without a constant for all undefs.");
7088 return getOperand(0);
7095 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7096 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7100 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7101 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7104 bool BuildVectorSDNode::isConstant() const {
7105 for (const SDValue &Op : op_values()) {
7106 unsigned Opc = Op.getOpcode();
7107 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7113 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7114 // Find the first non-undef value in the shuffle mask.
7116 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7119 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7121 // Make sure all remaining elements are either undef or the same as the first
7123 for (int Idx = Mask[i]; i != e; ++i)
7124 if (Mask[i] >= 0 && Mask[i] != Idx)
7130 static void checkForCyclesHelper(const SDNode *N,
7131 SmallPtrSetImpl<const SDNode*> &Visited,
7132 SmallPtrSetImpl<const SDNode*> &Checked,
7133 const llvm::SelectionDAG *DAG) {
7134 // If this node has already been checked, don't check it again.
7135 if (Checked.count(N))
7138 // If a node has already been visited on this depth-first walk, reject it as
7140 if (!Visited.insert(N).second) {
7141 errs() << "Detected cycle in SelectionDAG\n";
7142 dbgs() << "Offending node:\n";
7143 N->dumprFull(DAG); dbgs() << "\n";
7147 for (const SDValue &Op : N->op_values())
7148 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7155 void llvm::checkForCycles(const llvm::SDNode *N,
7156 const llvm::SelectionDAG *DAG,
7164 assert(N && "Checking nonexistent SDNode");
7165 SmallPtrSet<const SDNode*, 32> visited;
7166 SmallPtrSet<const SDNode*, 32> checked;
7167 checkForCyclesHelper(N, visited, checked, DAG);
7172 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7173 checkForCycles(DAG->getRoot().getNode(), DAG, force);