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/APSInt.h"
17 #include "llvm/ADT/SetVector.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringExtras.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/CodeGen/MachineBasicBlock.h"
24 #include "llvm/CodeGen/MachineConstantPool.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineModuleInfo.h"
27 #include "llvm/IR/CallingConv.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/DebugInfo.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/GlobalAlias.h"
34 #include "llvm/IR/GlobalVariable.h"
35 #include "llvm/IR/Intrinsics.h"
36 #include "llvm/Support/CommandLine.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/ManagedStatic.h"
40 #include "llvm/Support/MathExtras.h"
41 #include "llvm/Support/Mutex.h"
42 #include "llvm/Support/raw_ostream.h"
43 #include "llvm/Target/TargetInstrInfo.h"
44 #include "llvm/Target/TargetIntrinsicInfo.h"
45 #include "llvm/Target/TargetLowering.h"
46 #include "llvm/Target/TargetMachine.h"
47 #include "llvm/Target/TargetOptions.h"
48 #include "llvm/Target/TargetRegisterInfo.h"
49 #include "llvm/Target/TargetSelectionDAGInfo.h"
50 #include "llvm/Target/TargetSubtargetInfo.h"
57 /// makeVTList - Return an instance of the SDVTList struct initialized with the
58 /// specified members.
59 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
60 SDVTList Res = {VTs, NumVTs};
64 // Default null implementations of the callbacks.
65 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
66 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
68 //===----------------------------------------------------------------------===//
69 // ConstantFPSDNode Class
70 //===----------------------------------------------------------------------===//
72 /// isExactlyValue - We don't rely on operator== working on double values, as
73 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
74 /// As such, this method can be used to do an exact bit-for-bit comparison of
75 /// two floating point values.
76 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
77 return getValueAPF().bitwiseIsEqual(V);
80 bool ConstantFPSDNode::isValueValidForType(EVT VT,
82 assert(VT.isFloatingPoint() && "Can only convert between FP types");
84 // convert modifies in place, so make a copy.
85 APFloat Val2 = APFloat(Val);
87 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
88 APFloat::rmNearestTiesToEven,
93 //===----------------------------------------------------------------------===//
95 //===----------------------------------------------------------------------===//
97 /// isBuildVectorAllOnes - Return true if the specified node is a
98 /// BUILD_VECTOR where all of the elements are ~0 or undef.
99 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
100 // Look through a bit convert.
101 while (N->getOpcode() == ISD::BITCAST)
102 N = N->getOperand(0).getNode();
104 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
106 unsigned i = 0, e = N->getNumOperands();
108 // Skip over all of the undef values.
109 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
112 // Do not accept an all-undef vector.
113 if (i == e) return false;
115 // Do not accept build_vectors that aren't all constants or which have non-~0
116 // elements. We have to be a bit careful here, as the type of the constant
117 // may not be the same as the type of the vector elements due to type
118 // legalization (the elements are promoted to a legal type for the target and
119 // a vector of a type may be legal when the base element type is not).
120 // We only want to check enough bits to cover the vector elements, because
121 // we care if the resultant vector is all ones, not whether the individual
123 SDValue NotZero = N->getOperand(i);
124 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
125 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
126 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
128 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
129 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
134 // Okay, we have at least one ~0 value, check to see if the rest match or are
135 // undefs. Even with the above element type twiddling, this should be OK, as
136 // the same type legalization should have applied to all the elements.
137 for (++i; i != e; ++i)
138 if (N->getOperand(i) != NotZero &&
139 N->getOperand(i).getOpcode() != ISD::UNDEF)
145 /// isBuildVectorAllZeros - Return true if the specified node is a
146 /// BUILD_VECTOR where all of the elements are 0 or undef.
147 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
148 // Look through a bit convert.
149 while (N->getOpcode() == ISD::BITCAST)
150 N = N->getOperand(0).getNode();
152 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
154 bool IsAllUndef = true;
155 for (const SDValue &Op : N->op_values()) {
156 if (Op.getOpcode() == ISD::UNDEF)
159 // Do not accept build_vectors that aren't all constants or which have non-0
160 // elements. We have to be a bit careful here, as the type of the constant
161 // may not be the same as the type of the vector elements due to type
162 // legalization (the elements are promoted to a legal type for the target
163 // and a vector of a type may be legal when the base element type is not).
164 // We only want to check enough bits to cover the vector elements, because
165 // we care if the resultant vector is all zeros, not whether the individual
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Op)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Op)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (const SDValue &Op : N->op_values()) {
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (const SDValue &Op : N->op_values()) {
206 if (Op.getOpcode() == ISD::UNDEF)
208 if (!isa<ConstantFPSDNode>(Op))
214 /// allOperandsUndef - Return true if the node has at least one operand
215 /// and all operands of the specified node are ISD::UNDEF.
216 bool ISD::allOperandsUndef(const SDNode *N) {
217 // Return false if the node has no operands.
218 // This is "logically inconsistent" with the definition of "all" but
219 // is probably the desired behavior.
220 if (N->getNumOperands() == 0)
223 for (const SDValue &Op : N->op_values())
224 if (Op.getOpcode() != ISD::UNDEF)
230 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
233 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
235 return ISD::SIGN_EXTEND;
237 return ISD::ZERO_EXTEND;
242 llvm_unreachable("Invalid LoadExtType");
245 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
246 /// when given the operation for (X op Y).
247 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
248 // To perform this operation, we just need to swap the L and G bits of the
250 unsigned OldL = (Operation >> 2) & 1;
251 unsigned OldG = (Operation >> 1) & 1;
252 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
253 (OldL << 1) | // New G bit
254 (OldG << 2)); // New L bit.
257 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
258 /// 'op' is a valid SetCC operation.
259 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
260 unsigned Operation = Op;
262 Operation ^= 7; // Flip L, G, E bits, but not U.
264 Operation ^= 15; // Flip all of the condition bits.
266 if (Operation > ISD::SETTRUE2)
267 Operation &= ~8; // Don't let N and U bits get set.
269 return ISD::CondCode(Operation);
273 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
274 /// signed operation and 2 if the result is an unsigned comparison. Return zero
275 /// if the operation does not depend on the sign of the input (setne and seteq).
276 static int isSignedOp(ISD::CondCode Opcode) {
278 default: llvm_unreachable("Illegal integer setcc operation!");
280 case ISD::SETNE: return 0;
284 case ISD::SETGE: return 1;
288 case ISD::SETUGE: return 2;
292 /// getSetCCOrOperation - Return the result of a logical OR between different
293 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
294 /// returns SETCC_INVALID if it is not possible to represent the resultant
296 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
298 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
299 // Cannot fold a signed integer setcc with an unsigned integer setcc.
300 return ISD::SETCC_INVALID;
302 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
304 // If the N and U bits get set then the resultant comparison DOES suddenly
305 // care about orderedness, and is true when ordered.
306 if (Op > ISD::SETTRUE2)
307 Op &= ~16; // Clear the U bit if the N bit is set.
309 // Canonicalize illegal integer setcc's.
310 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
313 return ISD::CondCode(Op);
316 /// getSetCCAndOperation - Return the result of a logical AND between different
317 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
318 /// function returns zero if it is not possible to represent the resultant
320 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
322 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323 // Cannot fold a signed setcc with an unsigned setcc.
324 return ISD::SETCC_INVALID;
326 // Combine all of the condition bits.
327 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
329 // Canonicalize illegal integer setcc's.
333 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
334 case ISD::SETOEQ: // SETEQ & SETU[LG]E
335 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
336 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
337 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
344 //===----------------------------------------------------------------------===//
345 // SDNode Profile Support
346 //===----------------------------------------------------------------------===//
348 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
350 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
354 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
355 /// solely with their pointer.
356 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
357 ID.AddPointer(VTList.VTs);
360 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
362 static void AddNodeIDOperands(FoldingSetNodeID &ID,
363 ArrayRef<SDValue> Ops) {
364 for (auto& Op : Ops) {
365 ID.AddPointer(Op.getNode());
366 ID.AddInteger(Op.getResNo());
370 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
372 static void AddNodeIDOperands(FoldingSetNodeID &ID,
373 ArrayRef<SDUse> Ops) {
374 for (auto& Op : Ops) {
375 ID.AddPointer(Op.getNode());
376 ID.AddInteger(Op.getResNo());
380 /// Add logical or fast math flag values to FoldingSetNodeID value.
381 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
382 const SDNodeFlags *Flags) {
383 if (!isBinOpWithFlags(Opcode))
386 unsigned RawFlags = 0;
388 RawFlags = Flags->getRawFlags();
389 ID.AddInteger(RawFlags);
392 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
393 AddNodeIDFlags(ID, N->getOpcode(), N->getFlags());
396 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
397 SDVTList VTList, ArrayRef<SDValue> OpList) {
398 AddNodeIDOpcode(ID, OpC);
399 AddNodeIDValueTypes(ID, VTList);
400 AddNodeIDOperands(ID, OpList);
403 /// If this is an SDNode with special info, add this info to the NodeID data.
404 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
405 switch (N->getOpcode()) {
406 case ISD::TargetExternalSymbol:
407 case ISD::ExternalSymbol:
409 llvm_unreachable("Should only be used on nodes with operands");
410 default: break; // Normal nodes don't need extra info.
411 case ISD::TargetConstant:
412 case ISD::Constant: {
413 const ConstantSDNode *C = cast<ConstantSDNode>(N);
414 ID.AddPointer(C->getConstantIntValue());
415 ID.AddBoolean(C->isOpaque());
418 case ISD::TargetConstantFP:
419 case ISD::ConstantFP: {
420 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
423 case ISD::TargetGlobalAddress:
424 case ISD::GlobalAddress:
425 case ISD::TargetGlobalTLSAddress:
426 case ISD::GlobalTLSAddress: {
427 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
428 ID.AddPointer(GA->getGlobal());
429 ID.AddInteger(GA->getOffset());
430 ID.AddInteger(GA->getTargetFlags());
431 ID.AddInteger(GA->getAddressSpace());
434 case ISD::BasicBlock:
435 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
438 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
440 case ISD::RegisterMask:
441 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
444 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
446 case ISD::FrameIndex:
447 case ISD::TargetFrameIndex:
448 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
451 case ISD::TargetJumpTable:
452 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
453 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
455 case ISD::ConstantPool:
456 case ISD::TargetConstantPool: {
457 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
458 ID.AddInteger(CP->getAlignment());
459 ID.AddInteger(CP->getOffset());
460 if (CP->isMachineConstantPoolEntry())
461 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
463 ID.AddPointer(CP->getConstVal());
464 ID.AddInteger(CP->getTargetFlags());
467 case ISD::TargetIndex: {
468 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
469 ID.AddInteger(TI->getIndex());
470 ID.AddInteger(TI->getOffset());
471 ID.AddInteger(TI->getTargetFlags());
475 const LoadSDNode *LD = cast<LoadSDNode>(N);
476 ID.AddInteger(LD->getMemoryVT().getRawBits());
477 ID.AddInteger(LD->getRawSubclassData());
478 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
482 const StoreSDNode *ST = cast<StoreSDNode>(N);
483 ID.AddInteger(ST->getMemoryVT().getRawBits());
484 ID.AddInteger(ST->getRawSubclassData());
485 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
488 case ISD::ATOMIC_CMP_SWAP:
489 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
490 case ISD::ATOMIC_SWAP:
491 case ISD::ATOMIC_LOAD_ADD:
492 case ISD::ATOMIC_LOAD_SUB:
493 case ISD::ATOMIC_LOAD_AND:
494 case ISD::ATOMIC_LOAD_OR:
495 case ISD::ATOMIC_LOAD_XOR:
496 case ISD::ATOMIC_LOAD_NAND:
497 case ISD::ATOMIC_LOAD_MIN:
498 case ISD::ATOMIC_LOAD_MAX:
499 case ISD::ATOMIC_LOAD_UMIN:
500 case ISD::ATOMIC_LOAD_UMAX:
501 case ISD::ATOMIC_LOAD:
502 case ISD::ATOMIC_STORE: {
503 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
504 ID.AddInteger(AT->getMemoryVT().getRawBits());
505 ID.AddInteger(AT->getRawSubclassData());
506 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
509 case ISD::PREFETCH: {
510 const MemSDNode *PF = cast<MemSDNode>(N);
511 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
514 case ISD::VECTOR_SHUFFLE: {
515 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
516 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
518 ID.AddInteger(SVN->getMaskElt(i));
521 case ISD::TargetBlockAddress:
522 case ISD::BlockAddress: {
523 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
524 ID.AddPointer(BA->getBlockAddress());
525 ID.AddInteger(BA->getOffset());
526 ID.AddInteger(BA->getTargetFlags());
529 } // end switch (N->getOpcode())
531 AddNodeIDFlags(ID, N);
533 // Target specific memory nodes could also have address spaces to check.
534 if (N->isTargetMemoryOpcode())
535 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
538 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
540 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
541 AddNodeIDOpcode(ID, N->getOpcode());
542 // Add the return value info.
543 AddNodeIDValueTypes(ID, N->getVTList());
544 // Add the operand info.
545 AddNodeIDOperands(ID, N->ops());
547 // Handle SDNode leafs with special info.
548 AddNodeIDCustom(ID, N);
551 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
552 /// the CSE map that carries volatility, temporalness, indexing mode, and
553 /// extension/truncation information.
555 static inline unsigned
556 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
557 bool isNonTemporal, bool isInvariant) {
558 assert((ConvType & 3) == ConvType &&
559 "ConvType may not require more than 2 bits!");
560 assert((AM & 7) == AM &&
561 "AM may not require more than 3 bits!");
565 (isNonTemporal << 6) |
569 //===----------------------------------------------------------------------===//
570 // SelectionDAG Class
571 //===----------------------------------------------------------------------===//
573 /// doNotCSE - Return true if CSE should not be performed for this node.
574 static bool doNotCSE(SDNode *N) {
575 if (N->getValueType(0) == MVT::Glue)
576 return true; // Never CSE anything that produces a flag.
578 switch (N->getOpcode()) {
580 case ISD::HANDLENODE:
582 return true; // Never CSE these nodes.
585 // Check that remaining values produced are not flags.
586 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
587 if (N->getValueType(i) == MVT::Glue)
588 return true; // Never CSE anything that produces a flag.
593 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
595 void SelectionDAG::RemoveDeadNodes() {
596 // Create a dummy node (which is not added to allnodes), that adds a reference
597 // to the root node, preventing it from being deleted.
598 HandleSDNode Dummy(getRoot());
600 SmallVector<SDNode*, 128> DeadNodes;
602 // Add all obviously-dead nodes to the DeadNodes worklist.
603 for (SDNode &Node : allnodes())
604 if (Node.use_empty())
605 DeadNodes.push_back(&Node);
607 RemoveDeadNodes(DeadNodes);
609 // If the root changed (e.g. it was a dead load, update the root).
610 setRoot(Dummy.getValue());
613 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
614 /// given list, and any nodes that become unreachable as a result.
615 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
617 // Process the worklist, deleting the nodes and adding their uses to the
619 while (!DeadNodes.empty()) {
620 SDNode *N = DeadNodes.pop_back_val();
622 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
623 DUL->NodeDeleted(N, nullptr);
625 // Take the node out of the appropriate CSE map.
626 RemoveNodeFromCSEMaps(N);
628 // Next, brutally remove the operand list. This is safe to do, as there are
629 // no cycles in the graph.
630 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
632 SDNode *Operand = Use.getNode();
635 // Now that we removed this operand, see if there are no uses of it left.
636 if (Operand->use_empty())
637 DeadNodes.push_back(Operand);
644 void SelectionDAG::RemoveDeadNode(SDNode *N){
645 SmallVector<SDNode*, 16> DeadNodes(1, N);
647 // Create a dummy node that adds a reference to the root node, preventing
648 // it from being deleted. (This matters if the root is an operand of the
650 HandleSDNode Dummy(getRoot());
652 RemoveDeadNodes(DeadNodes);
655 void SelectionDAG::DeleteNode(SDNode *N) {
656 // First take this out of the appropriate CSE map.
657 RemoveNodeFromCSEMaps(N);
659 // Finally, remove uses due to operands of this node, remove from the
660 // AllNodes list, and delete the node.
661 DeleteNodeNotInCSEMaps(N);
664 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
665 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
666 assert(N->use_empty() && "Cannot delete a node that is not dead!");
668 // Drop all of the operands and decrement used node's use counts.
674 void SDDbgInfo::erase(const SDNode *Node) {
675 DbgValMapType::iterator I = DbgValMap.find(Node);
676 if (I == DbgValMap.end())
678 for (auto &Val: I->second)
679 Val->setIsInvalidated();
683 void SelectionDAG::DeallocateNode(SDNode *N) {
684 if (N->OperandsNeedDelete)
685 delete[] N->OperandList;
687 // Set the opcode to DELETED_NODE to help catch bugs when node
688 // memory is reallocated.
689 N->NodeType = ISD::DELETED_NODE;
691 NodeAllocator.Deallocate(AllNodes.remove(N));
693 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
694 // them and forget about that node.
699 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
700 static void VerifySDNode(SDNode *N) {
701 switch (N->getOpcode()) {
704 case ISD::BUILD_PAIR: {
705 EVT VT = N->getValueType(0);
706 assert(N->getNumValues() == 1 && "Too many results!");
707 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
708 "Wrong return type!");
709 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
710 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
711 "Mismatched operand types!");
712 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
713 "Wrong operand type!");
714 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
715 "Wrong return type size");
718 case ISD::BUILD_VECTOR: {
719 assert(N->getNumValues() == 1 && "Too many results!");
720 assert(N->getValueType(0).isVector() && "Wrong return type!");
721 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
722 "Wrong number of operands!");
723 EVT EltVT = N->getValueType(0).getVectorElementType();
724 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
725 assert((I->getValueType() == EltVT ||
726 (EltVT.isInteger() && I->getValueType().isInteger() &&
727 EltVT.bitsLE(I->getValueType()))) &&
728 "Wrong operand type!");
729 assert(I->getValueType() == N->getOperand(0).getValueType() &&
730 "Operands must all have the same type");
738 /// \brief Insert a newly allocated node into the DAG.
740 /// Handles insertion into the all nodes list and CSE map, as well as
741 /// verification and other common operations when a new node is allocated.
742 void SelectionDAG::InsertNode(SDNode *N) {
743 AllNodes.push_back(N);
745 N->PersistentId = NextPersistentId++;
750 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
751 /// correspond to it. This is useful when we're about to delete or repurpose
752 /// the node. We don't want future request for structurally identical nodes
753 /// to return N anymore.
754 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
756 switch (N->getOpcode()) {
757 case ISD::HANDLENODE: return false; // noop.
759 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
760 "Cond code doesn't exist!");
761 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
762 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
764 case ISD::ExternalSymbol:
765 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
767 case ISD::TargetExternalSymbol: {
768 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
769 Erased = TargetExternalSymbols.erase(
770 std::pair<std::string,unsigned char>(ESN->getSymbol(),
771 ESN->getTargetFlags()));
774 case ISD::MCSymbol: {
775 auto *MCSN = cast<MCSymbolSDNode>(N);
776 Erased = MCSymbols.erase(MCSN->getMCSymbol());
779 case ISD::VALUETYPE: {
780 EVT VT = cast<VTSDNode>(N)->getVT();
781 if (VT.isExtended()) {
782 Erased = ExtendedValueTypeNodes.erase(VT);
784 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
785 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
790 // Remove it from the CSE Map.
791 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
792 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
793 Erased = CSEMap.RemoveNode(N);
797 // Verify that the node was actually in one of the CSE maps, unless it has a
798 // flag result (which cannot be CSE'd) or is one of the special cases that are
799 // not subject to CSE.
800 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
801 !N->isMachineOpcode() && !doNotCSE(N)) {
804 llvm_unreachable("Node is not in map!");
810 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
811 /// maps and modified in place. Add it back to the CSE maps, unless an identical
812 /// node already exists, in which case transfer all its users to the existing
813 /// node. This transfer can potentially trigger recursive merging.
816 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
817 // For node types that aren't CSE'd, just act as if no identical node
820 SDNode *Existing = CSEMap.GetOrInsertNode(N);
822 // If there was already an existing matching node, use ReplaceAllUsesWith
823 // to replace the dead one with the existing one. This can cause
824 // recursive merging of other unrelated nodes down the line.
825 ReplaceAllUsesWith(N, Existing);
827 // N is now dead. Inform the listeners and delete it.
828 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
829 DUL->NodeDeleted(N, Existing);
830 DeleteNodeNotInCSEMaps(N);
835 // If the node doesn't already exist, we updated it. Inform listeners.
836 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
840 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
841 /// were replaced with those specified. If this node is never memoized,
842 /// return null, otherwise return a pointer to the slot it would take. If a
843 /// node already exists with these operands, the slot will be non-null.
844 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
849 SDValue Ops[] = { Op };
851 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
852 AddNodeIDCustom(ID, N);
853 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
857 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
858 /// were replaced with those specified. If this node is never memoized,
859 /// return null, otherwise return a pointer to the slot it would take. If a
860 /// node already exists with these operands, the slot will be non-null.
861 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
862 SDValue Op1, SDValue Op2,
867 SDValue Ops[] = { Op1, Op2 };
869 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
870 AddNodeIDCustom(ID, N);
871 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
876 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
877 /// were replaced with those specified. If this node is never memoized,
878 /// return null, otherwise return a pointer to the slot it would take. If a
879 /// node already exists with these operands, the slot will be non-null.
880 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
886 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
887 AddNodeIDCustom(ID, N);
888 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
892 /// getEVTAlignment - Compute the default alignment value for the
895 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
896 Type *Ty = VT == MVT::iPTR ?
897 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
898 VT.getTypeForEVT(*getContext());
900 return getDataLayout().getABITypeAlignment(Ty);
903 // EntryNode could meaningfully have debug info if we can find it...
904 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
905 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
906 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
907 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
908 UpdateListeners(nullptr) {
909 InsertNode(&EntryNode);
910 DbgInfo = new SDDbgInfo();
913 void SelectionDAG::init(MachineFunction &mf) {
915 TLI = getSubtarget().getTargetLowering();
916 TSI = getSubtarget().getSelectionDAGInfo();
917 Context = &mf.getFunction()->getContext();
920 SelectionDAG::~SelectionDAG() {
921 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
926 void SelectionDAG::allnodes_clear() {
927 assert(&*AllNodes.begin() == &EntryNode);
928 AllNodes.remove(AllNodes.begin());
929 while (!AllNodes.empty())
930 DeallocateNode(&AllNodes.front());
932 NextPersistentId = 0;
936 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
937 SDVTList VTs, SDValue N1,
939 const SDNodeFlags *Flags) {
940 if (isBinOpWithFlags(Opcode)) {
941 // If no flags were passed in, use a default flags object.
943 if (Flags == nullptr)
946 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
947 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
952 BinarySDNode *N = new (NodeAllocator)
953 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
957 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
959 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
961 switch (N->getOpcode()) {
964 case ISD::ConstantFP:
965 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
966 "debug location. Use another overload.");
972 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
973 DebugLoc DL, void *&InsertPos) {
974 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
976 switch (N->getOpcode()) {
977 default: break; // Process only regular (non-target) constant nodes.
979 case ISD::ConstantFP:
980 // Erase debug location from the node if the node is used at several
981 // different places to do not propagate one location to all uses as it
982 // leads to incorrect debug info.
983 if (N->getDebugLoc() != DL)
984 N->setDebugLoc(DebugLoc());
991 void SelectionDAG::clear() {
993 OperandAllocator.Reset();
996 ExtendedValueTypeNodes.clear();
997 ExternalSymbols.clear();
998 TargetExternalSymbols.clear();
1000 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1001 static_cast<CondCodeSDNode*>(nullptr));
1002 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1003 static_cast<SDNode*>(nullptr));
1005 EntryNode.UseList = nullptr;
1006 InsertNode(&EntryNode);
1007 Root = getEntryNode();
1011 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1012 return VT.bitsGT(Op.getValueType()) ?
1013 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1014 getNode(ISD::TRUNCATE, DL, VT, Op);
1017 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1018 return VT.bitsGT(Op.getValueType()) ?
1019 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1020 getNode(ISD::TRUNCATE, DL, VT, Op);
1023 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1024 return VT.bitsGT(Op.getValueType()) ?
1025 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1026 getNode(ISD::TRUNCATE, DL, VT, Op);
1029 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1031 if (VT.bitsLE(Op.getValueType()))
1032 return getNode(ISD::TRUNCATE, SL, VT, Op);
1034 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1035 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1038 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1039 assert(!VT.isVector() &&
1040 "getZeroExtendInReg should use the vector element type instead of "
1041 "the vector type!");
1042 if (Op.getValueType() == VT) return Op;
1043 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1044 APInt Imm = APInt::getLowBitsSet(BitWidth,
1045 VT.getSizeInBits());
1046 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1047 getConstant(Imm, DL, Op.getValueType()));
1050 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1051 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1052 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1053 "The sizes of the input and result must match in order to perform the "
1054 "extend in-register.");
1055 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1056 "The destination vector type must have fewer lanes than the input.");
1057 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1060 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1061 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1062 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1063 "The sizes of the input and result must match in order to perform the "
1064 "extend in-register.");
1065 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1066 "The destination vector type must have fewer lanes than the input.");
1067 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1070 SDValue SelectionDAG::getZeroExtendVectorInReg(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::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1080 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1082 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1083 EVT EltVT = VT.getScalarType();
1085 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1086 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1089 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1090 EVT EltVT = VT.getScalarType();
1092 switch (TLI->getBooleanContents(VT)) {
1093 case TargetLowering::ZeroOrOneBooleanContent:
1094 case TargetLowering::UndefinedBooleanContent:
1095 TrueValue = getConstant(1, DL, VT);
1097 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1098 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1102 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1105 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1107 EVT EltVT = VT.getScalarType();
1108 assert((EltVT.getSizeInBits() >= 64 ||
1109 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1110 "getConstant with a uint64_t value that doesn't fit in the type!");
1111 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1114 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1117 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1120 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1121 bool isT, bool isO) {
1122 assert(VT.isInteger() && "Cannot create FP integer constant!");
1124 EVT EltVT = VT.getScalarType();
1125 const ConstantInt *Elt = &Val;
1127 // In some cases the vector type is legal but the element type is illegal and
1128 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1129 // inserted value (the type does not need to match the vector element type).
1130 // Any extra bits introduced will be truncated away.
1131 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1132 TargetLowering::TypePromoteInteger) {
1133 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1134 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1135 Elt = ConstantInt::get(*getContext(), NewVal);
1137 // In other cases the element type is illegal and needs to be expanded, for
1138 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1139 // the value into n parts and use a vector type with n-times the elements.
1140 // Then bitcast to the type requested.
1141 // Legalizing constants too early makes the DAGCombiner's job harder so we
1142 // only legalize if the DAG tells us we must produce legal types.
1143 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1144 TLI->getTypeAction(*getContext(), EltVT) ==
1145 TargetLowering::TypeExpandInteger) {
1146 APInt NewVal = Elt->getValue();
1147 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1148 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1149 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1150 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1152 // Check the temporary vector is the correct size. If this fails then
1153 // getTypeToTransformTo() probably returned a type whose size (in bits)
1154 // isn't a power-of-2 factor of the requested type size.
1155 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1157 SmallVector<SDValue, 2> EltParts;
1158 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1159 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1160 .trunc(ViaEltSizeInBits), DL,
1161 ViaEltVT, isT, isO));
1164 // EltParts is currently in little endian order. If we actually want
1165 // big-endian order then reverse it now.
1166 if (getDataLayout().isBigEndian())
1167 std::reverse(EltParts.begin(), EltParts.end());
1169 // The elements must be reversed when the element order is different
1170 // to the endianness of the elements (because the BITCAST is itself a
1171 // vector shuffle in this situation). However, we do not need any code to
1172 // perform this reversal because getConstant() is producing a vector
1174 // This situation occurs in MIPS MSA.
1176 SmallVector<SDValue, 8> Ops;
1177 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1178 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1180 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1181 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1186 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1187 "APInt size does not match type size!");
1188 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1189 FoldingSetNodeID ID;
1190 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1194 SDNode *N = nullptr;
1195 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1197 return SDValue(N, 0);
1200 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1202 CSEMap.InsertNode(N, IP);
1206 SDValue Result(N, 0);
1207 if (VT.isVector()) {
1208 SmallVector<SDValue, 8> Ops;
1209 Ops.assign(VT.getVectorNumElements(), Result);
1210 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1215 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1216 return getConstant(Val, DL, TLI->getPointerTy(getDataLayout()), isTarget);
1219 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1221 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1224 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1226 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1228 EVT EltVT = VT.getScalarType();
1230 // Do the map lookup using the actual bit pattern for the floating point
1231 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1232 // we don't have issues with SNANs.
1233 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1234 FoldingSetNodeID ID;
1235 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1238 SDNode *N = nullptr;
1239 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1241 return SDValue(N, 0);
1244 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1246 CSEMap.InsertNode(N, IP);
1250 SDValue Result(N, 0);
1251 if (VT.isVector()) {
1252 SmallVector<SDValue, 8> Ops;
1253 Ops.assign(VT.getVectorNumElements(), Result);
1254 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1259 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1261 EVT EltVT = VT.getScalarType();
1262 if (EltVT==MVT::f32)
1263 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1264 else if (EltVT==MVT::f64)
1265 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1266 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1269 APFloat apf = APFloat(Val);
1270 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1272 return getConstantFP(apf, DL, VT, isTarget);
1274 llvm_unreachable("Unsupported type in getConstantFP");
1277 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1278 EVT VT, int64_t Offset,
1280 unsigned char TargetFlags) {
1281 assert((TargetFlags == 0 || isTargetGA) &&
1282 "Cannot set target flags on target-independent globals");
1284 // Truncate (with sign-extension) the offset value to the pointer size.
1285 unsigned BitWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
1287 Offset = SignExtend64(Offset, BitWidth);
1290 if (GV->isThreadLocal())
1291 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1293 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1295 FoldingSetNodeID ID;
1296 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1298 ID.AddInteger(Offset);
1299 ID.AddInteger(TargetFlags);
1300 ID.AddInteger(GV->getType()->getAddressSpace());
1302 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1303 return SDValue(E, 0);
1305 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1306 DL.getDebugLoc(), GV, VT,
1307 Offset, TargetFlags);
1308 CSEMap.InsertNode(N, IP);
1310 return SDValue(N, 0);
1313 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1314 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1315 FoldingSetNodeID ID;
1316 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1319 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1320 return SDValue(E, 0);
1322 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1323 CSEMap.InsertNode(N, IP);
1325 return SDValue(N, 0);
1328 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1329 unsigned char TargetFlags) {
1330 assert((TargetFlags == 0 || isTarget) &&
1331 "Cannot set target flags on target-independent jump tables");
1332 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1333 FoldingSetNodeID ID;
1334 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1336 ID.AddInteger(TargetFlags);
1338 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1339 return SDValue(E, 0);
1341 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1343 CSEMap.InsertNode(N, IP);
1345 return SDValue(N, 0);
1348 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1349 unsigned Alignment, int Offset,
1351 unsigned char TargetFlags) {
1352 assert((TargetFlags == 0 || isTarget) &&
1353 "Cannot set target flags on target-independent globals");
1355 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1356 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1357 FoldingSetNodeID ID;
1358 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1359 ID.AddInteger(Alignment);
1360 ID.AddInteger(Offset);
1362 ID.AddInteger(TargetFlags);
1364 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1365 return SDValue(E, 0);
1367 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1368 Alignment, TargetFlags);
1369 CSEMap.InsertNode(N, IP);
1371 return SDValue(N, 0);
1375 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1376 unsigned Alignment, int Offset,
1378 unsigned char TargetFlags) {
1379 assert((TargetFlags == 0 || isTarget) &&
1380 "Cannot set target flags on target-independent globals");
1382 Alignment = getDataLayout().getPrefTypeAlignment(C->getType());
1383 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1384 FoldingSetNodeID ID;
1385 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1386 ID.AddInteger(Alignment);
1387 ID.AddInteger(Offset);
1388 C->addSelectionDAGCSEId(ID);
1389 ID.AddInteger(TargetFlags);
1391 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1392 return SDValue(E, 0);
1394 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1395 Alignment, TargetFlags);
1396 CSEMap.InsertNode(N, IP);
1398 return SDValue(N, 0);
1401 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1402 unsigned char TargetFlags) {
1403 FoldingSetNodeID ID;
1404 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1405 ID.AddInteger(Index);
1406 ID.AddInteger(Offset);
1407 ID.AddInteger(TargetFlags);
1409 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1410 return SDValue(E, 0);
1413 new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset, -TargetFlags);
1414 CSEMap.InsertNode(N, IP);
1416 return SDValue(N, 0);
1419 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1420 FoldingSetNodeID ID;
1421 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1424 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1425 return SDValue(E, 0);
1427 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1428 CSEMap.InsertNode(N, IP);
1430 return SDValue(N, 0);
1433 SDValue SelectionDAG::getValueType(EVT VT) {
1434 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1435 ValueTypeNodes.size())
1436 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1438 SDNode *&N = VT.isExtended() ?
1439 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1441 if (N) return SDValue(N, 0);
1442 N = new (NodeAllocator) VTSDNode(VT);
1444 return SDValue(N, 0);
1447 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1448 SDNode *&N = ExternalSymbols[Sym];
1449 if (N) return SDValue(N, 0);
1450 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1452 return SDValue(N, 0);
1455 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1456 SDNode *&N = MCSymbols[Sym];
1458 return SDValue(N, 0);
1459 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1461 return SDValue(N, 0);
1464 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1465 unsigned char TargetFlags) {
1467 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1469 if (N) return SDValue(N, 0);
1470 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1472 return SDValue(N, 0);
1475 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1476 if ((unsigned)Cond >= CondCodeNodes.size())
1477 CondCodeNodes.resize(Cond+1);
1479 if (!CondCodeNodes[Cond]) {
1480 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1481 CondCodeNodes[Cond] = N;
1485 return SDValue(CondCodeNodes[Cond], 0);
1488 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1489 // the shuffle mask M that point at N1 to point at N2, and indices that point
1490 // N2 to point at N1.
1491 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1493 ShuffleVectorSDNode::commuteMask(M);
1496 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1497 SDValue N2, const int *Mask) {
1498 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1499 "Invalid VECTOR_SHUFFLE");
1501 // Canonicalize shuffle undef, undef -> undef
1502 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1503 return getUNDEF(VT);
1505 // Validate that all indices in Mask are within the range of the elements
1506 // input to the shuffle.
1507 unsigned NElts = VT.getVectorNumElements();
1508 SmallVector<int, 8> MaskVec;
1509 for (unsigned i = 0; i != NElts; ++i) {
1510 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1511 MaskVec.push_back(Mask[i]);
1514 // Canonicalize shuffle v, v -> v, undef
1517 for (unsigned i = 0; i != NElts; ++i)
1518 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1521 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1522 if (N1.getOpcode() == ISD::UNDEF)
1523 commuteShuffle(N1, N2, MaskVec);
1525 // If shuffling a splat, try to blend the splat instead. We do this here so
1526 // that even when this arises during lowering we don't have to re-handle it.
1527 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1528 BitVector UndefElements;
1529 SDValue Splat = BV->getSplatValue(&UndefElements);
1533 for (int i = 0; i < (int)NElts; ++i) {
1534 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1537 // If this input comes from undef, mark it as such.
1538 if (UndefElements[MaskVec[i] - Offset]) {
1543 // If we can blend a non-undef lane, use that instead.
1544 if (!UndefElements[i])
1545 MaskVec[i] = i + Offset;
1548 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1549 BlendSplat(N1BV, 0);
1550 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1551 BlendSplat(N2BV, NElts);
1553 // Canonicalize all index into lhs, -> shuffle lhs, undef
1554 // Canonicalize all index into rhs, -> shuffle rhs, undef
1555 bool AllLHS = true, AllRHS = true;
1556 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1557 for (unsigned i = 0; i != NElts; ++i) {
1558 if (MaskVec[i] >= (int)NElts) {
1563 } else if (MaskVec[i] >= 0) {
1567 if (AllLHS && AllRHS)
1568 return getUNDEF(VT);
1569 if (AllLHS && !N2Undef)
1573 commuteShuffle(N1, N2, MaskVec);
1575 // Reset our undef status after accounting for the mask.
1576 N2Undef = N2.getOpcode() == ISD::UNDEF;
1577 // Re-check whether both sides ended up undef.
1578 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1579 return getUNDEF(VT);
1581 // If Identity shuffle return that node.
1582 bool Identity = true, AllSame = true;
1583 for (unsigned i = 0; i != NElts; ++i) {
1584 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1585 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1587 if (Identity && NElts)
1590 // Shuffling a constant splat doesn't change the result.
1594 // Look through any bitcasts. We check that these don't change the number
1595 // (and size) of elements and just changes their types.
1596 while (V.getOpcode() == ISD::BITCAST)
1597 V = V->getOperand(0);
1599 // A splat should always show up as a build vector node.
1600 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1601 BitVector UndefElements;
1602 SDValue Splat = BV->getSplatValue(&UndefElements);
1603 // If this is a splat of an undef, shuffling it is also undef.
1604 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1605 return getUNDEF(VT);
1608 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1610 // We only have a splat which can skip shuffles if there is a splatted
1611 // value and no undef lanes rearranged by the shuffle.
1612 if (Splat && UndefElements.none()) {
1613 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1614 // number of elements match or the value splatted is a zero constant.
1617 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1618 if (C->isNullValue())
1622 // If the shuffle itself creates a splat, build the vector directly.
1623 if (AllSame && SameNumElts) {
1624 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1625 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1627 EVT BuildVT = BV->getValueType(0);
1628 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1630 // We may have jumped through bitcasts, so the type of the
1631 // BUILD_VECTOR may not match the type of the shuffle.
1633 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1639 FoldingSetNodeID ID;
1640 SDValue Ops[2] = { N1, N2 };
1641 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1642 for (unsigned i = 0; i != NElts; ++i)
1643 ID.AddInteger(MaskVec[i]);
1646 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1647 return SDValue(E, 0);
1649 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1650 // SDNode doesn't have access to it. This memory will be "leaked" when
1651 // the node is deallocated, but recovered when the NodeAllocator is released.
1652 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1653 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1655 ShuffleVectorSDNode *N =
1656 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1657 dl.getDebugLoc(), N1, N2,
1659 CSEMap.InsertNode(N, IP);
1661 return SDValue(N, 0);
1664 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1665 MVT VT = SV.getSimpleValueType(0);
1666 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1667 ShuffleVectorSDNode::commuteMask(MaskVec);
1669 SDValue Op0 = SV.getOperand(0);
1670 SDValue Op1 = SV.getOperand(1);
1671 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1674 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1675 SDValue Val, SDValue DTy,
1676 SDValue STy, SDValue Rnd, SDValue Sat,
1677 ISD::CvtCode Code) {
1678 // If the src and dest types are the same and the conversion is between
1679 // integer types of the same sign or two floats, no conversion is necessary.
1681 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1684 FoldingSetNodeID ID;
1685 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1686 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1688 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1689 return SDValue(E, 0);
1691 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1694 CSEMap.InsertNode(N, IP);
1696 return SDValue(N, 0);
1699 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1700 FoldingSetNodeID ID;
1701 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1702 ID.AddInteger(RegNo);
1704 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1705 return SDValue(E, 0);
1707 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1708 CSEMap.InsertNode(N, IP);
1710 return SDValue(N, 0);
1713 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1714 FoldingSetNodeID ID;
1715 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1716 ID.AddPointer(RegMask);
1718 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1719 return SDValue(E, 0);
1721 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1722 CSEMap.InsertNode(N, IP);
1724 return SDValue(N, 0);
1727 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1728 FoldingSetNodeID ID;
1729 SDValue Ops[] = { Root };
1730 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1731 ID.AddPointer(Label);
1733 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1734 return SDValue(E, 0);
1736 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1737 dl.getDebugLoc(), Root, Label);
1738 CSEMap.InsertNode(N, IP);
1740 return SDValue(N, 0);
1744 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1747 unsigned char TargetFlags) {
1748 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1750 FoldingSetNodeID ID;
1751 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1753 ID.AddInteger(Offset);
1754 ID.AddInteger(TargetFlags);
1756 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1757 return SDValue(E, 0);
1759 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1761 CSEMap.InsertNode(N, IP);
1763 return SDValue(N, 0);
1766 SDValue SelectionDAG::getSrcValue(const Value *V) {
1767 assert((!V || V->getType()->isPointerTy()) &&
1768 "SrcValue is not a pointer?");
1770 FoldingSetNodeID ID;
1771 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1775 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1776 return SDValue(E, 0);
1778 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1779 CSEMap.InsertNode(N, IP);
1781 return SDValue(N, 0);
1784 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1785 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1786 FoldingSetNodeID ID;
1787 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1791 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1792 return SDValue(E, 0);
1794 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1795 CSEMap.InsertNode(N, IP);
1797 return SDValue(N, 0);
1800 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1801 if (VT == V.getValueType())
1804 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1807 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1808 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1809 unsigned SrcAS, unsigned DestAS) {
1810 SDValue Ops[] = {Ptr};
1811 FoldingSetNodeID ID;
1812 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1813 ID.AddInteger(SrcAS);
1814 ID.AddInteger(DestAS);
1817 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1818 return SDValue(E, 0);
1820 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1822 VT, Ptr, SrcAS, DestAS);
1823 CSEMap.InsertNode(N, IP);
1825 return SDValue(N, 0);
1828 /// getShiftAmountOperand - Return the specified value casted to
1829 /// the target's desired shift amount type.
1830 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1831 EVT OpTy = Op.getValueType();
1832 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1833 if (OpTy == ShTy || OpTy.isVector()) return Op;
1835 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1838 SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1840 const TargetLowering &TLI = getTargetLoweringInfo();
1841 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1842 EVT VT = Node->getValueType(0);
1843 SDValue Tmp1 = Node->getOperand(0);
1844 SDValue Tmp2 = Node->getOperand(1);
1845 unsigned Align = Node->getConstantOperandVal(3);
1847 SDValue VAListLoad =
1848 getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1, Tmp2,
1849 MachinePointerInfo(V), false, false, false, 0);
1850 SDValue VAList = VAListLoad;
1852 if (Align > TLI.getMinStackArgumentAlignment()) {
1853 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1855 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1856 getConstant(Align - 1, dl, VAList.getValueType()));
1858 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1859 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1862 // Increment the pointer, VAList, to the next vaarg
1863 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1864 getConstant(getDataLayout().getTypeAllocSize(
1865 VT.getTypeForEVT(*getContext())),
1866 dl, VAList.getValueType()));
1867 // Store the incremented VAList to the legalized pointer
1868 Tmp1 = getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2,
1869 MachinePointerInfo(V), false, false, 0);
1870 // Load the actual argument out of the pointer VAList
1871 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo(),
1872 false, false, false, 0);
1875 SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1877 const TargetLowering &TLI = getTargetLoweringInfo();
1878 // This defaults to loading a pointer from the input and storing it to the
1879 // output, returning the chain.
1880 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1881 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1882 SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
1883 Node->getOperand(0), Node->getOperand(2),
1884 MachinePointerInfo(VS), false, false, false, 0);
1885 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1886 MachinePointerInfo(VD), false, false, 0);
1889 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1890 /// specified value type.
1891 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1892 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1893 unsigned ByteSize = VT.getStoreSize();
1894 Type *Ty = VT.getTypeForEVT(*getContext());
1895 unsigned StackAlign =
1896 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1898 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1899 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1902 /// CreateStackTemporary - Create a stack temporary suitable for holding
1903 /// either of the specified value types.
1904 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1905 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1906 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1907 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1908 const DataLayout &DL = getDataLayout();
1910 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1912 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1913 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1914 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1917 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1918 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1919 // These setcc operations always fold.
1923 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1925 case ISD::SETTRUE2: {
1926 TargetLowering::BooleanContent Cnt =
1927 TLI->getBooleanContents(N1->getValueType(0));
1929 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1943 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1947 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1948 const APInt &C2 = N2C->getAPIntValue();
1949 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1950 const APInt &C1 = N1C->getAPIntValue();
1953 default: llvm_unreachable("Unknown integer setcc!");
1954 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1955 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1956 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1957 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1958 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1959 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1960 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1961 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1962 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1963 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1967 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1968 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1969 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1972 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1973 return getUNDEF(VT);
1975 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1976 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1977 return getUNDEF(VT);
1979 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1980 R==APFloat::cmpLessThan, dl, VT);
1981 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1982 return getUNDEF(VT);
1984 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1985 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1986 return getUNDEF(VT);
1988 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1989 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1990 return getUNDEF(VT);
1992 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1993 R==APFloat::cmpEqual, dl, VT);
1994 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1995 return getUNDEF(VT);
1997 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1998 R==APFloat::cmpEqual, dl, VT);
1999 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
2000 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
2001 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
2002 R==APFloat::cmpEqual, dl, VT);
2003 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
2004 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
2005 R==APFloat::cmpLessThan, dl, VT);
2006 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
2007 R==APFloat::cmpUnordered, dl, VT);
2008 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
2009 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
2012 // Ensure that the constant occurs on the RHS.
2013 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
2014 MVT CompVT = N1.getValueType().getSimpleVT();
2015 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2018 return getSetCC(dl, VT, N2, N1, SwappedCond);
2022 // Could not fold it.
2026 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2027 /// use this predicate to simplify operations downstream.
2028 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2029 // This predicate is not safe for vector operations.
2030 if (Op.getValueType().isVector())
2033 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2034 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2037 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2038 /// this predicate to simplify operations downstream. Mask is known to be zero
2039 /// for bits that V cannot have.
2040 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2041 unsigned Depth) const {
2042 APInt KnownZero, KnownOne;
2043 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2044 return (KnownZero & Mask) == Mask;
2047 /// Determine which bits of Op are known to be either zero or one and return
2048 /// them in the KnownZero/KnownOne bitsets.
2049 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2050 APInt &KnownOne, unsigned Depth) const {
2051 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2053 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2055 return; // Limit search depth.
2057 APInt KnownZero2, KnownOne2;
2059 switch (Op.getOpcode()) {
2061 // We know all of the bits for a constant!
2062 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2063 KnownZero = ~KnownOne;
2066 // If either the LHS or the RHS are Zero, the result is zero.
2067 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2068 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2070 // Output known-1 bits are only known if set in both the LHS & RHS.
2071 KnownOne &= KnownOne2;
2072 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2073 KnownZero |= KnownZero2;
2076 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2077 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2079 // Output known-0 bits are only known if clear in both the LHS & RHS.
2080 KnownZero &= KnownZero2;
2081 // Output known-1 are known to be set if set in either the LHS | RHS.
2082 KnownOne |= KnownOne2;
2085 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2086 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2088 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2089 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2090 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2091 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2092 KnownZero = KnownZeroOut;
2096 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2097 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2099 // If low bits are zero in either operand, output low known-0 bits.
2100 // Also compute a conserative estimate for high known-0 bits.
2101 // More trickiness is possible, but this is sufficient for the
2102 // interesting case of alignment computation.
2103 KnownOne.clearAllBits();
2104 unsigned TrailZ = KnownZero.countTrailingOnes() +
2105 KnownZero2.countTrailingOnes();
2106 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2107 KnownZero2.countLeadingOnes(),
2108 BitWidth) - BitWidth;
2110 TrailZ = std::min(TrailZ, BitWidth);
2111 LeadZ = std::min(LeadZ, BitWidth);
2112 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2113 APInt::getHighBitsSet(BitWidth, LeadZ);
2117 // For the purposes of computing leading zeros we can conservatively
2118 // treat a udiv as a logical right shift by the power of 2 known to
2119 // be less than the denominator.
2120 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2121 unsigned LeadZ = KnownZero2.countLeadingOnes();
2123 KnownOne2.clearAllBits();
2124 KnownZero2.clearAllBits();
2125 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2126 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2127 if (RHSUnknownLeadingOnes != BitWidth)
2128 LeadZ = std::min(BitWidth,
2129 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2131 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2135 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2136 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2138 // Only known if known in both the LHS and RHS.
2139 KnownOne &= KnownOne2;
2140 KnownZero &= KnownZero2;
2142 case ISD::SELECT_CC:
2143 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2144 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2146 // Only known if known in both the LHS and RHS.
2147 KnownOne &= KnownOne2;
2148 KnownZero &= KnownZero2;
2156 if (Op.getResNo() != 1)
2158 // The boolean result conforms to getBooleanContents.
2159 // If we know the result of a setcc has the top bits zero, use this info.
2160 // We know that we have an integer-based boolean since these operations
2161 // are only available for integer.
2162 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2163 TargetLowering::ZeroOrOneBooleanContent &&
2165 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2168 // If we know the result of a setcc has the top bits zero, use this info.
2169 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2170 TargetLowering::ZeroOrOneBooleanContent &&
2172 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2175 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2176 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2177 unsigned ShAmt = SA->getZExtValue();
2179 // If the shift count is an invalid immediate, don't do anything.
2180 if (ShAmt >= BitWidth)
2183 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2184 KnownZero <<= ShAmt;
2186 // low bits known zero.
2187 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2191 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2192 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2193 unsigned ShAmt = SA->getZExtValue();
2195 // If the shift count is an invalid immediate, don't do anything.
2196 if (ShAmt >= BitWidth)
2199 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2200 KnownZero = KnownZero.lshr(ShAmt);
2201 KnownOne = KnownOne.lshr(ShAmt);
2203 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2204 KnownZero |= HighBits; // High bits known zero.
2208 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2209 unsigned ShAmt = SA->getZExtValue();
2211 // If the shift count is an invalid immediate, don't do anything.
2212 if (ShAmt >= BitWidth)
2215 // If any of the demanded bits are produced by the sign extension, we also
2216 // demand the input sign bit.
2217 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2219 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2220 KnownZero = KnownZero.lshr(ShAmt);
2221 KnownOne = KnownOne.lshr(ShAmt);
2223 // Handle the sign bits.
2224 APInt SignBit = APInt::getSignBit(BitWidth);
2225 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2227 if (KnownZero.intersects(SignBit)) {
2228 KnownZero |= HighBits; // New bits are known zero.
2229 } else if (KnownOne.intersects(SignBit)) {
2230 KnownOne |= HighBits; // New bits are known one.
2234 case ISD::SIGN_EXTEND_INREG: {
2235 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2236 unsigned EBits = EVT.getScalarType().getSizeInBits();
2238 // Sign extension. Compute the demanded bits in the result that are not
2239 // present in the input.
2240 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2242 APInt InSignBit = APInt::getSignBit(EBits);
2243 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2245 // If the sign extended bits are demanded, we know that the sign
2247 InSignBit = InSignBit.zext(BitWidth);
2248 if (NewBits.getBoolValue())
2249 InputDemandedBits |= InSignBit;
2251 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2252 KnownOne &= InputDemandedBits;
2253 KnownZero &= InputDemandedBits;
2255 // If the sign bit of the input is known set or clear, then we know the
2256 // top bits of the result.
2257 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2258 KnownZero |= NewBits;
2259 KnownOne &= ~NewBits;
2260 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2261 KnownOne |= NewBits;
2262 KnownZero &= ~NewBits;
2263 } else { // Input sign bit unknown
2264 KnownZero &= ~NewBits;
2265 KnownOne &= ~NewBits;
2270 case ISD::CTTZ_ZERO_UNDEF:
2272 case ISD::CTLZ_ZERO_UNDEF:
2274 unsigned LowBits = Log2_32(BitWidth)+1;
2275 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2276 KnownOne.clearAllBits();
2280 LoadSDNode *LD = cast<LoadSDNode>(Op);
2281 // If this is a ZEXTLoad and we are looking at the loaded value.
2282 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2283 EVT VT = LD->getMemoryVT();
2284 unsigned MemBits = VT.getScalarType().getSizeInBits();
2285 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2286 } else if (const MDNode *Ranges = LD->getRanges()) {
2287 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2291 case ISD::ZERO_EXTEND: {
2292 EVT InVT = Op.getOperand(0).getValueType();
2293 unsigned InBits = InVT.getScalarType().getSizeInBits();
2294 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2295 KnownZero = KnownZero.trunc(InBits);
2296 KnownOne = KnownOne.trunc(InBits);
2297 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2298 KnownZero = KnownZero.zext(BitWidth);
2299 KnownOne = KnownOne.zext(BitWidth);
2300 KnownZero |= NewBits;
2303 case ISD::SIGN_EXTEND: {
2304 EVT InVT = Op.getOperand(0).getValueType();
2305 unsigned InBits = InVT.getScalarType().getSizeInBits();
2306 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2308 KnownZero = KnownZero.trunc(InBits);
2309 KnownOne = KnownOne.trunc(InBits);
2310 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2312 // Note if the sign bit is known to be zero or one.
2313 bool SignBitKnownZero = KnownZero.isNegative();
2314 bool SignBitKnownOne = KnownOne.isNegative();
2316 KnownZero = KnownZero.zext(BitWidth);
2317 KnownOne = KnownOne.zext(BitWidth);
2319 // If the sign bit is known zero or one, the top bits match.
2320 if (SignBitKnownZero)
2321 KnownZero |= NewBits;
2322 else if (SignBitKnownOne)
2323 KnownOne |= NewBits;
2326 case ISD::ANY_EXTEND: {
2327 EVT InVT = Op.getOperand(0).getValueType();
2328 unsigned InBits = InVT.getScalarType().getSizeInBits();
2329 KnownZero = KnownZero.trunc(InBits);
2330 KnownOne = KnownOne.trunc(InBits);
2331 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2332 KnownZero = KnownZero.zext(BitWidth);
2333 KnownOne = KnownOne.zext(BitWidth);
2336 case ISD::TRUNCATE: {
2337 EVT InVT = Op.getOperand(0).getValueType();
2338 unsigned InBits = InVT.getScalarType().getSizeInBits();
2339 KnownZero = KnownZero.zext(InBits);
2340 KnownOne = KnownOne.zext(InBits);
2341 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2342 KnownZero = KnownZero.trunc(BitWidth);
2343 KnownOne = KnownOne.trunc(BitWidth);
2346 case ISD::AssertZext: {
2347 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2348 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2349 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2350 KnownZero |= (~InMask);
2351 KnownOne &= (~KnownZero);
2355 // All bits are zero except the low bit.
2356 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2360 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2361 // We know that the top bits of C-X are clear if X contains less bits
2362 // than C (i.e. no wrap-around can happen). For example, 20-X is
2363 // positive if we can prove that X is >= 0 and < 16.
2364 if (CLHS->getAPIntValue().isNonNegative()) {
2365 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2366 // NLZ can't be BitWidth with no sign bit
2367 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2368 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2370 // If all of the MaskV bits are known to be zero, then we know the
2371 // output top bits are zero, because we now know that the output is
2373 if ((KnownZero2 & MaskV) == MaskV) {
2374 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2375 // Top bits known zero.
2376 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2384 // Output known-0 bits are known if clear or set in both the low clear bits
2385 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2386 // low 3 bits clear.
2387 // Output known-0 bits are also known if the top bits of each input are
2388 // known to be clear. For example, if one input has the top 10 bits clear
2389 // and the other has the top 8 bits clear, we know the top 7 bits of the
2390 // output must be clear.
2391 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2392 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2393 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2395 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2396 KnownZeroHigh = std::min(KnownZeroHigh,
2397 KnownZero2.countLeadingOnes());
2398 KnownZeroLow = std::min(KnownZeroLow,
2399 KnownZero2.countTrailingOnes());
2401 if (Op.getOpcode() == ISD::ADD) {
2402 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2403 if (KnownZeroHigh > 1)
2404 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2408 // With ADDE, a carry bit may be added in, so we can only use this
2409 // information if we know (at least) that the low two bits are clear. We
2410 // then return to the caller that the low bit is unknown but that other bits
2412 if (KnownZeroLow >= 2) // ADDE
2413 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2417 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2418 const APInt &RA = Rem->getAPIntValue().abs();
2419 if (RA.isPowerOf2()) {
2420 APInt LowBits = RA - 1;
2421 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2423 // The low bits of the first operand are unchanged by the srem.
2424 KnownZero = KnownZero2 & LowBits;
2425 KnownOne = KnownOne2 & LowBits;
2427 // If the first operand is non-negative or has all low bits zero, then
2428 // the upper bits are all zero.
2429 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2430 KnownZero |= ~LowBits;
2432 // If the first operand is negative and not all low bits are zero, then
2433 // the upper bits are all one.
2434 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2435 KnownOne |= ~LowBits;
2436 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2441 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2442 const APInt &RA = Rem->getAPIntValue();
2443 if (RA.isPowerOf2()) {
2444 APInt LowBits = (RA - 1);
2445 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2447 // The upper bits are all zero, the lower ones are unchanged.
2448 KnownZero = KnownZero2 | ~LowBits;
2449 KnownOne = KnownOne2 & LowBits;
2454 // Since the result is less than or equal to either operand, any leading
2455 // zero bits in either operand must also exist in the result.
2456 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2457 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2459 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2460 KnownZero2.countLeadingOnes());
2461 KnownOne.clearAllBits();
2462 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2465 case ISD::EXTRACT_ELEMENT: {
2466 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2467 const unsigned Index =
2468 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2469 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2471 // Remove low part of known bits mask
2472 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2473 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2475 // Remove high part of known bit mask
2476 KnownZero = KnownZero.trunc(BitWidth);
2477 KnownOne = KnownOne.trunc(BitWidth);
2484 APInt Op0Zero, Op0One;
2485 APInt Op1Zero, Op1One;
2486 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2487 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2489 KnownZero = Op0Zero & Op1Zero;
2490 KnownOne = Op0One & Op1One;
2493 case ISD::FrameIndex:
2494 case ISD::TargetFrameIndex:
2495 if (unsigned Align = InferPtrAlignment(Op)) {
2496 // The low bits are known zero if the pointer is aligned.
2497 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2503 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2506 case ISD::INTRINSIC_WO_CHAIN:
2507 case ISD::INTRINSIC_W_CHAIN:
2508 case ISD::INTRINSIC_VOID:
2509 // Allow the target to implement this method for its nodes.
2510 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2514 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2517 /// ComputeNumSignBits - Return the number of times the sign bit of the
2518 /// register is replicated into the other bits. We know that at least 1 bit
2519 /// is always equal to the sign bit (itself), but other cases can give us
2520 /// information. For example, immediately after an "SRA X, 2", we know that
2521 /// the top 3 bits are all equal to each other, so we return 3.
2522 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2523 EVT VT = Op.getValueType();
2524 assert(VT.isInteger() && "Invalid VT!");
2525 unsigned VTBits = VT.getScalarType().getSizeInBits();
2527 unsigned FirstAnswer = 1;
2530 return 1; // Limit search depth.
2532 switch (Op.getOpcode()) {
2534 case ISD::AssertSext:
2535 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2536 return VTBits-Tmp+1;
2537 case ISD::AssertZext:
2538 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2541 case ISD::Constant: {
2542 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2543 return Val.getNumSignBits();
2546 case ISD::SIGN_EXTEND:
2548 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2549 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2551 case ISD::SIGN_EXTEND_INREG:
2552 // Max of the input and what this extends.
2554 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2557 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2558 return std::max(Tmp, Tmp2);
2561 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2562 // SRA X, C -> adds C sign bits.
2563 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2564 Tmp += C->getZExtValue();
2565 if (Tmp > VTBits) Tmp = VTBits;
2569 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2570 // shl destroys sign bits.
2571 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2572 if (C->getZExtValue() >= VTBits || // Bad shift.
2573 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2574 return Tmp - C->getZExtValue();
2579 case ISD::XOR: // NOT is handled here.
2580 // Logical binary ops preserve the number of sign bits at the worst.
2581 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2583 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2584 FirstAnswer = std::min(Tmp, Tmp2);
2585 // We computed what we know about the sign bits as our first
2586 // answer. Now proceed to the generic code that uses
2587 // computeKnownBits, and pick whichever answer is better.
2592 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2593 if (Tmp == 1) return 1; // Early out.
2594 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2595 return std::min(Tmp, Tmp2);
2596 case ISD::SELECT_CC:
2597 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2598 if (Tmp == 1) return 1; // Early out.
2599 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2600 return std::min(Tmp, Tmp2);
2605 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2607 return 1; // Early out.
2608 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2609 return std::min(Tmp, Tmp2);
2616 if (Op.getResNo() != 1)
2618 // The boolean result conforms to getBooleanContents. Fall through.
2619 // If setcc returns 0/-1, all bits are sign bits.
2620 // We know that we have an integer-based boolean since these operations
2621 // are only available for integer.
2622 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2623 TargetLowering::ZeroOrNegativeOneBooleanContent)
2627 // If setcc returns 0/-1, all bits are sign bits.
2628 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2629 TargetLowering::ZeroOrNegativeOneBooleanContent)
2634 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2635 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2637 // Handle rotate right by N like a rotate left by 32-N.
2638 if (Op.getOpcode() == ISD::ROTR)
2639 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2641 // If we aren't rotating out all of the known-in sign bits, return the
2642 // number that are left. This handles rotl(sext(x), 1) for example.
2643 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2644 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2648 // Add can have at most one carry bit. Thus we know that the output
2649 // is, at worst, one more bit than the inputs.
2650 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2651 if (Tmp == 1) return 1; // Early out.
2653 // Special case decrementing a value (ADD X, -1):
2654 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2655 if (CRHS->isAllOnesValue()) {
2656 APInt KnownZero, KnownOne;
2657 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2659 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2661 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2664 // If we are subtracting one from a positive number, there is no carry
2665 // out of the result.
2666 if (KnownZero.isNegative())
2670 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2671 if (Tmp2 == 1) return 1;
2672 return std::min(Tmp, Tmp2)-1;
2675 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2676 if (Tmp2 == 1) return 1;
2679 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2680 if (CLHS->isNullValue()) {
2681 APInt KnownZero, KnownOne;
2682 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2683 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2685 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2688 // If the input is known to be positive (the sign bit is known clear),
2689 // the output of the NEG has the same number of sign bits as the input.
2690 if (KnownZero.isNegative())
2693 // Otherwise, we treat this like a SUB.
2696 // Sub can have at most one carry bit. Thus we know that the output
2697 // is, at worst, one more bit than the inputs.
2698 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2699 if (Tmp == 1) return 1; // Early out.
2700 return std::min(Tmp, Tmp2)-1;
2702 // FIXME: it's tricky to do anything useful for this, but it is an important
2703 // case for targets like X86.
2705 case ISD::EXTRACT_ELEMENT: {
2706 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2707 const int BitWidth = Op.getValueType().getSizeInBits();
2709 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2711 // Get reverse index (starting from 1), Op1 value indexes elements from
2712 // little end. Sign starts at big end.
2713 const int rIndex = Items - 1 -
2714 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2716 // If the sign portion ends in our element the subtraction gives correct
2717 // result. Otherwise it gives either negative or > bitwidth result
2718 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2722 // If we are looking at the loaded value of the SDNode.
2723 if (Op.getResNo() == 0) {
2724 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2725 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2726 unsigned ExtType = LD->getExtensionType();
2729 case ISD::SEXTLOAD: // '17' bits known
2730 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2731 return VTBits-Tmp+1;
2732 case ISD::ZEXTLOAD: // '16' bits known
2733 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2739 // Allow the target to implement this method for its nodes.
2740 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2741 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2742 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2743 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2744 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2745 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2748 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2749 // use this information.
2750 APInt KnownZero, KnownOne;
2751 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2754 if (KnownZero.isNegative()) { // sign bit is 0
2756 } else if (KnownOne.isNegative()) { // sign bit is 1;
2763 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2764 // the number of identical bits in the top of the input value.
2766 Mask <<= Mask.getBitWidth()-VTBits;
2767 // Return # leading zeros. We use 'min' here in case Val was zero before
2768 // shifting. We don't want to return '64' as for an i32 "0".
2769 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2772 /// isBaseWithConstantOffset - Return true if the specified operand is an
2773 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2774 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2775 /// semantics as an ADD. This handles the equivalence:
2776 /// X|Cst == X+Cst iff X&Cst = 0.
2777 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2778 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2779 !isa<ConstantSDNode>(Op.getOperand(1)))
2782 if (Op.getOpcode() == ISD::OR &&
2783 !MaskedValueIsZero(Op.getOperand(0),
2784 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2791 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2792 // If we're told that NaNs won't happen, assume they won't.
2793 if (getTarget().Options.NoNaNsFPMath)
2796 // If the value is a constant, we can obviously see if it is a NaN or not.
2797 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2798 return !C->getValueAPF().isNaN();
2800 // TODO: Recognize more cases here.
2805 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2806 // If the value is a constant, we can obviously see if it is a zero or not.
2807 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2808 return !C->isZero();
2810 // TODO: Recognize more cases here.
2811 switch (Op.getOpcode()) {
2814 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2815 return !C->isNullValue();
2822 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2823 // Check the obvious case.
2824 if (A == B) return true;
2826 // For for negative and positive zero.
2827 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2828 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2829 if (CA->isZero() && CB->isZero()) return true;
2831 // Otherwise they may not be equal.
2835 /// getNode - Gets or creates the specified node.
2837 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2838 FoldingSetNodeID ID;
2839 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2841 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2842 return SDValue(E, 0);
2844 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2845 DL.getDebugLoc(), getVTList(VT));
2846 CSEMap.InsertNode(N, IP);
2849 return SDValue(N, 0);
2852 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2853 EVT VT, SDValue Operand) {
2854 // Constant fold unary operations with an integer constant operand. Even
2855 // opaque constant will be folded, because the folding of unary operations
2856 // doesn't create new constants with different values. Nevertheless, the
2857 // opaque flag is preserved during folding to prevent future folding with
2859 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2860 const APInt &Val = C->getAPIntValue();
2863 case ISD::SIGN_EXTEND:
2864 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2865 C->isTargetOpcode(), C->isOpaque());
2866 case ISD::ANY_EXTEND:
2867 case ISD::ZERO_EXTEND:
2869 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2870 C->isTargetOpcode(), C->isOpaque());
2871 case ISD::UINT_TO_FP:
2872 case ISD::SINT_TO_FP: {
2873 APFloat apf(EVTToAPFloatSemantics(VT),
2874 APInt::getNullValue(VT.getSizeInBits()));
2875 (void)apf.convertFromAPInt(Val,
2876 Opcode==ISD::SINT_TO_FP,
2877 APFloat::rmNearestTiesToEven);
2878 return getConstantFP(apf, DL, VT);
2881 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2882 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2883 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2884 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2885 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2886 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2889 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2892 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2895 case ISD::CTLZ_ZERO_UNDEF:
2896 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2899 case ISD::CTTZ_ZERO_UNDEF:
2900 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2905 // Constant fold unary operations with a floating point constant operand.
2906 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2907 APFloat V = C->getValueAPF(); // make copy
2911 return getConstantFP(V, DL, VT);
2914 return getConstantFP(V, DL, VT);
2916 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2917 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2918 return getConstantFP(V, DL, VT);
2922 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2923 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2924 return getConstantFP(V, DL, VT);
2928 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2929 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2930 return getConstantFP(V, DL, VT);
2933 case ISD::FP_EXTEND: {
2935 // This can return overflow, underflow, or inexact; we don't care.
2936 // FIXME need to be more flexible about rounding mode.
2937 (void)V.convert(EVTToAPFloatSemantics(VT),
2938 APFloat::rmNearestTiesToEven, &ignored);
2939 return getConstantFP(V, DL, VT);
2941 case ISD::FP_TO_SINT:
2942 case ISD::FP_TO_UINT: {
2945 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2946 // FIXME need to be more flexible about rounding mode.
2947 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2948 Opcode==ISD::FP_TO_SINT,
2949 APFloat::rmTowardZero, &ignored);
2950 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2952 APInt api(VT.getSizeInBits(), x);
2953 return getConstant(api, DL, VT);
2956 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2957 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2958 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2959 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2960 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2961 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2966 // Constant fold unary operations with a vector integer or float operand.
2967 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2968 if (BV->isConstant()) {
2971 // FIXME: Entirely reasonable to perform folding of other unary
2972 // operations here as the need arises.
2979 case ISD::FP_EXTEND:
2980 case ISD::FP_TO_SINT:
2981 case ISD::FP_TO_UINT:
2983 case ISD::UINT_TO_FP:
2984 case ISD::SINT_TO_FP:
2987 case ISD::CTLZ_ZERO_UNDEF:
2989 case ISD::CTTZ_ZERO_UNDEF:
2991 SDValue Ops = { Operand };
2992 if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, 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 assert(Operand.getValueType().bitsLT(VT) &&
3015 "Invalid fpext node, dst < src!");
3016 if (Operand.getOpcode() == ISD::UNDEF)
3017 return getUNDEF(VT);
3019 case ISD::SIGN_EXTEND:
3020 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3021 "Invalid SIGN_EXTEND!");
3022 if (Operand.getValueType() == VT) return Operand; // noop extension
3023 assert((!VT.isVector() ||
3024 VT.getVectorNumElements() ==
3025 Operand.getValueType().getVectorNumElements()) &&
3026 "Vector element count mismatch!");
3027 assert(Operand.getValueType().bitsLT(VT) &&
3028 "Invalid sext node, dst < src!");
3029 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3030 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3031 else if (OpOpcode == ISD::UNDEF)
3032 // sext(undef) = 0, because the top bits will all be the same.
3033 return getConstant(0, DL, VT);
3035 case ISD::ZERO_EXTEND:
3036 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3037 "Invalid ZERO_EXTEND!");
3038 if (Operand.getValueType() == VT) return Operand; // noop extension
3039 assert((!VT.isVector() ||
3040 VT.getVectorNumElements() ==
3041 Operand.getValueType().getVectorNumElements()) &&
3042 "Vector element count mismatch!");
3043 assert(Operand.getValueType().bitsLT(VT) &&
3044 "Invalid zext node, dst < src!");
3045 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3046 return getNode(ISD::ZERO_EXTEND, DL, VT,
3047 Operand.getNode()->getOperand(0));
3048 else if (OpOpcode == ISD::UNDEF)
3049 // zext(undef) = 0, because the top bits will be zero.
3050 return getConstant(0, DL, VT);
3052 case ISD::ANY_EXTEND:
3053 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3054 "Invalid ANY_EXTEND!");
3055 if (Operand.getValueType() == VT) return Operand; // noop extension
3056 assert((!VT.isVector() ||
3057 VT.getVectorNumElements() ==
3058 Operand.getValueType().getVectorNumElements()) &&
3059 "Vector element count mismatch!");
3060 assert(Operand.getValueType().bitsLT(VT) &&
3061 "Invalid anyext node, dst < src!");
3063 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3064 OpOpcode == ISD::ANY_EXTEND)
3065 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3066 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3067 else if (OpOpcode == ISD::UNDEF)
3068 return getUNDEF(VT);
3070 // (ext (trunx x)) -> x
3071 if (OpOpcode == ISD::TRUNCATE) {
3072 SDValue OpOp = Operand.getNode()->getOperand(0);
3073 if (OpOp.getValueType() == VT)
3078 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3079 "Invalid TRUNCATE!");
3080 if (Operand.getValueType() == VT) return Operand; // noop truncate
3081 assert((!VT.isVector() ||
3082 VT.getVectorNumElements() ==
3083 Operand.getValueType().getVectorNumElements()) &&
3084 "Vector element count mismatch!");
3085 assert(Operand.getValueType().bitsGT(VT) &&
3086 "Invalid truncate node, src < dst!");
3087 if (OpOpcode == ISD::TRUNCATE)
3088 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3089 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3090 OpOpcode == ISD::ANY_EXTEND) {
3091 // If the source is smaller than the dest, we still need an extend.
3092 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3093 .bitsLT(VT.getScalarType()))
3094 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3095 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3096 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3097 return Operand.getNode()->getOperand(0);
3099 if (OpOpcode == ISD::UNDEF)
3100 return getUNDEF(VT);
3103 assert(VT.isInteger() && VT == Operand.getValueType() &&
3105 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3106 "BSWAP types must be a multiple of 16 bits!");
3107 if (OpOpcode == ISD::UNDEF)
3108 return getUNDEF(VT);
3111 // Basic sanity checking.
3112 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3113 && "Cannot BITCAST between types of different sizes!");
3114 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3115 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3116 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3117 if (OpOpcode == ISD::UNDEF)
3118 return getUNDEF(VT);
3120 case ISD::SCALAR_TO_VECTOR:
3121 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3122 (VT.getVectorElementType() == Operand.getValueType() ||
3123 (VT.getVectorElementType().isInteger() &&
3124 Operand.getValueType().isInteger() &&
3125 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3126 "Illegal SCALAR_TO_VECTOR node!");
3127 if (OpOpcode == ISD::UNDEF)
3128 return getUNDEF(VT);
3129 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3130 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3131 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3132 Operand.getConstantOperandVal(1) == 0 &&
3133 Operand.getOperand(0).getValueType() == VT)
3134 return Operand.getOperand(0);
3137 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3138 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3139 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3140 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3141 Operand.getNode()->getOperand(0),
3142 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3143 if (OpOpcode == ISD::FNEG) // --X -> X
3144 return Operand.getNode()->getOperand(0);
3147 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3148 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3153 SDVTList VTs = getVTList(VT);
3154 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3155 FoldingSetNodeID ID;
3156 SDValue Ops[1] = { Operand };
3157 AddNodeIDNode(ID, Opcode, VTs, Ops);
3159 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3160 return SDValue(E, 0);
3162 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3163 DL.getDebugLoc(), VTs, Operand);
3164 CSEMap.InsertNode(N, IP);
3166 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3167 DL.getDebugLoc(), VTs, Operand);
3171 return SDValue(N, 0);
3174 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3177 case ISD::ADD: return std::make_pair(C1 + C2, true);
3178 case ISD::SUB: return std::make_pair(C1 - C2, true);
3179 case ISD::MUL: return std::make_pair(C1 * C2, true);
3180 case ISD::AND: return std::make_pair(C1 & C2, true);
3181 case ISD::OR: return std::make_pair(C1 | C2, true);
3182 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3183 case ISD::SHL: return std::make_pair(C1 << C2, true);
3184 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3185 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3186 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3187 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3188 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3189 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3190 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3191 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3193 if (!C2.getBoolValue())
3195 return std::make_pair(C1.udiv(C2), true);
3197 if (!C2.getBoolValue())
3199 return std::make_pair(C1.urem(C2), true);
3201 if (!C2.getBoolValue())
3203 return std::make_pair(C1.sdiv(C2), true);
3205 if (!C2.getBoolValue())
3207 return std::make_pair(C1.srem(C2), true);
3209 return std::make_pair(APInt(1, 0), false);
3212 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3213 const ConstantSDNode *Cst1,
3214 const ConstantSDNode *Cst2) {
3215 if (Cst1->isOpaque() || Cst2->isOpaque())
3218 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3219 Cst2->getAPIntValue());
3222 return getConstant(Folded.first, DL, VT);
3225 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3226 SDNode *Cst1, SDNode *Cst2) {
3227 // If the opcode is a target-specific ISD node, there's nothing we can
3228 // do here and the operand rules may not line up with the below, so
3230 if (Opcode >= ISD::BUILTIN_OP_END)
3233 // Handle the case of two scalars.
3234 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3235 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3236 if (SDValue Folded =
3237 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3240 SmallVector<SDValue, 4> Outputs;
3241 // We may have a vector type but a scalar result. Create a splat.
3242 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3243 // Build a big vector out of the scalar elements we generated.
3244 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3251 // For vectors extract each constant element into Inputs so we can constant
3252 // fold them individually.
3253 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3254 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3258 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3260 EVT SVT = VT.getScalarType();
3261 SmallVector<SDValue, 4> Outputs;
3262 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3263 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3264 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3265 if (!V1 || !V2) // Not a constant, bail.
3268 if (V1->isOpaque() || V2->isOpaque())
3271 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3272 // FIXME: This is valid and could be handled by truncating the APInts.
3273 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3276 // Fold one vector element.
3277 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3278 V2->getAPIntValue());
3281 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3284 assert(VT.getVectorNumElements() == Outputs.size() &&
3285 "Vector size mismatch!");
3287 // We may have a vector type but a scalar result. Create a splat.
3288 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3290 // Build a big vector out of the scalar elements we generated.
3291 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3294 SDValue SelectionDAG::FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
3296 ArrayRef<SDValue> Ops,
3297 const SDNodeFlags *Flags) {
3298 // If the opcode is a target-specific ISD node, there's nothing we can
3299 // do here and the operand rules may not line up with the below, so
3301 if (Opcode >= ISD::BUILTIN_OP_END)
3304 // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
3308 unsigned NumElts = VT.getVectorNumElements();
3310 auto IsSameVectorSize = [&](const SDValue &Op) {
3311 return Op.getValueType().isVector() &&
3312 Op.getValueType().getVectorNumElements() == NumElts;
3315 auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
3316 BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Op);
3317 return (Op.getOpcode() == ISD::UNDEF) || (BV && BV->isConstant());
3320 // All operands must be vector types with the same number of elements as
3321 // the result type and must be either UNDEF or a build vector of constant
3322 // or UNDEF scalars.
3323 if (!std::all_of(Ops.begin(), Ops.end(), IsConstantBuildVectorOrUndef) ||
3324 !std::all_of(Ops.begin(), Ops.end(), IsSameVectorSize))
3327 // Find legal integer scalar type for constant promotion and
3328 // ensure that its scalar size is at least as large as source.
3329 EVT SVT = VT.getScalarType();
3331 if (SVT.isInteger()) {
3332 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3333 if (LegalSVT.bitsLT(SVT))
3337 // Constant fold each scalar lane separately.
3338 SmallVector<SDValue, 4> ScalarResults;
3339 for (unsigned i = 0; i != NumElts; i++) {
3340 SmallVector<SDValue, 4> ScalarOps;
3341 for (SDValue Op : Ops) {
3342 EVT InSVT = Op.getValueType().getScalarType();
3343 BuildVectorSDNode *InBV = dyn_cast<BuildVectorSDNode>(Op);
3345 // We've checked that this is UNDEF above.
3346 ScalarOps.push_back(getUNDEF(InSVT));
3350 SDValue ScalarOp = InBV->getOperand(i);
3351 EVT ScalarVT = ScalarOp.getValueType();
3353 // Build vector (integer) scalar operands may need implicit
3354 // truncation - do this before constant folding.
3355 if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
3356 ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
3358 ScalarOps.push_back(ScalarOp);
3361 // Constant fold the scalar operands.
3362 SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
3364 // Legalize the (integer) scalar constant if necessary.
3365 if (LegalSVT != SVT)
3366 ScalarResult = getNode(ISD::ANY_EXTEND, DL, LegalSVT, ScalarResult);
3368 // Scalar folding only succeeded if the result is a constant or UNDEF.
3369 if (ScalarResult.getOpcode() != ISD::UNDEF &&
3370 ScalarResult.getOpcode() != ISD::Constant &&
3371 ScalarResult.getOpcode() != ISD::ConstantFP)
3373 ScalarResults.push_back(ScalarResult);
3376 assert(ScalarResults.size() == NumElts &&
3377 "Unexpected number of scalar results for BUILD_VECTOR");
3378 return getNode(ISD::BUILD_VECTOR, DL, VT, ScalarResults);
3381 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3382 SDValue N2, const SDNodeFlags *Flags) {
3383 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3384 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3386 // Canonicalize constant to RHS if commutative.
3387 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3388 std::swap(N1C, N2C);
3394 case ISD::TokenFactor:
3395 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3396 N2.getValueType() == MVT::Other && "Invalid token factor!");
3397 // Fold trivial token factors.
3398 if (N1.getOpcode() == ISD::EntryToken) return N2;
3399 if (N2.getOpcode() == ISD::EntryToken) return N1;
3400 if (N1 == N2) return N1;
3402 case ISD::CONCAT_VECTORS:
3403 // Concat of UNDEFs is UNDEF.
3404 if (N1.getOpcode() == ISD::UNDEF &&
3405 N2.getOpcode() == ISD::UNDEF)
3406 return getUNDEF(VT);
3408 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3409 // one big BUILD_VECTOR.
3410 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3411 N2.getOpcode() == ISD::BUILD_VECTOR) {
3412 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3413 N1.getNode()->op_end());
3414 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3416 // BUILD_VECTOR requires all inputs to be of the same type, find the
3417 // maximum type and extend them all.
3418 EVT SVT = VT.getScalarType();
3419 for (SDValue Op : Elts)
3420 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3421 if (SVT.bitsGT(VT.getScalarType()))
3422 for (SDValue &Op : Elts)
3423 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3424 ? getZExtOrTrunc(Op, DL, SVT)
3425 : getSExtOrTrunc(Op, DL, SVT);
3427 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3431 assert(VT.isInteger() && "This operator does not apply to FP types!");
3432 assert(N1.getValueType() == N2.getValueType() &&
3433 N1.getValueType() == VT && "Binary operator types must match!");
3434 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3435 // worth handling here.
3436 if (N2C && N2C->isNullValue())
3438 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3445 assert(VT.isInteger() && "This operator does not apply to FP types!");
3446 assert(N1.getValueType() == N2.getValueType() &&
3447 N1.getValueType() == VT && "Binary operator types must match!");
3448 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3449 // it's worth handling here.
3450 if (N2C && N2C->isNullValue())
3464 assert(VT.isInteger() && "This operator does not apply to FP types!");
3465 assert(N1.getValueType() == N2.getValueType() &&
3466 N1.getValueType() == VT && "Binary operator types must match!");
3473 if (getTarget().Options.UnsafeFPMath) {
3474 if (Opcode == ISD::FADD) {
3476 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3477 if (CFP->getValueAPF().isZero())
3480 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3481 if (CFP->getValueAPF().isZero())
3483 } else if (Opcode == ISD::FSUB) {
3485 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3486 if (CFP->getValueAPF().isZero())
3488 } else if (Opcode == ISD::FMUL) {
3489 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3492 // If the first operand isn't the constant, try the second
3494 CFP = dyn_cast<ConstantFPSDNode>(N2);
3501 return SDValue(CFP,0);
3503 if (CFP->isExactlyValue(1.0))
3508 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3509 assert(N1.getValueType() == N2.getValueType() &&
3510 N1.getValueType() == VT && "Binary operator types must match!");
3512 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3513 assert(N1.getValueType() == VT &&
3514 N1.getValueType().isFloatingPoint() &&
3515 N2.getValueType().isFloatingPoint() &&
3516 "Invalid FCOPYSIGN!");
3523 assert(VT == N1.getValueType() &&
3524 "Shift operators return type must be the same as their first arg");
3525 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3526 "Shifts only work on integers");
3527 assert((!VT.isVector() || VT == N2.getValueType()) &&
3528 "Vector shift amounts must be in the same as their first arg");
3529 // Verify that the shift amount VT is bit enough to hold valid shift
3530 // amounts. This catches things like trying to shift an i1024 value by an
3531 // i8, which is easy to fall into in generic code that uses
3532 // TLI.getShiftAmount().
3533 assert(N2.getValueType().getSizeInBits() >=
3534 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3535 "Invalid use of small shift amount with oversized value!");
3537 // Always fold shifts of i1 values so the code generator doesn't need to
3538 // handle them. Since we know the size of the shift has to be less than the
3539 // size of the value, the shift/rotate count is guaranteed to be zero.
3542 if (N2C && N2C->isNullValue())
3545 case ISD::FP_ROUND_INREG: {
3546 EVT EVT = cast<VTSDNode>(N2)->getVT();
3547 assert(VT == N1.getValueType() && "Not an inreg round!");
3548 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3549 "Cannot FP_ROUND_INREG integer types");
3550 assert(EVT.isVector() == VT.isVector() &&
3551 "FP_ROUND_INREG type should be vector iff the operand "
3553 assert((!EVT.isVector() ||
3554 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3555 "Vector element counts must match in FP_ROUND_INREG");
3556 assert(EVT.bitsLE(VT) && "Not rounding down!");
3558 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3562 assert(VT.isFloatingPoint() &&
3563 N1.getValueType().isFloatingPoint() &&
3564 VT.bitsLE(N1.getValueType()) &&
3565 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3566 if (N1.getValueType() == VT) return N1; // noop conversion.
3568 case ISD::AssertSext:
3569 case ISD::AssertZext: {
3570 EVT EVT = cast<VTSDNode>(N2)->getVT();
3571 assert(VT == N1.getValueType() && "Not an inreg extend!");
3572 assert(VT.isInteger() && EVT.isInteger() &&
3573 "Cannot *_EXTEND_INREG FP types");
3574 assert(!EVT.isVector() &&
3575 "AssertSExt/AssertZExt type should be the vector element type "
3576 "rather than the vector type!");
3577 assert(EVT.bitsLE(VT) && "Not extending!");
3578 if (VT == EVT) return N1; // noop assertion.
3581 case ISD::SIGN_EXTEND_INREG: {
3582 EVT EVT = cast<VTSDNode>(N2)->getVT();
3583 assert(VT == N1.getValueType() && "Not an inreg extend!");
3584 assert(VT.isInteger() && EVT.isInteger() &&
3585 "Cannot *_EXTEND_INREG FP types");
3586 assert(EVT.isVector() == VT.isVector() &&
3587 "SIGN_EXTEND_INREG type should be vector iff the operand "
3589 assert((!EVT.isVector() ||
3590 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3591 "Vector element counts must match in SIGN_EXTEND_INREG");
3592 assert(EVT.bitsLE(VT) && "Not extending!");
3593 if (EVT == VT) return N1; // Not actually extending
3595 auto SignExtendInReg = [&](APInt Val) {
3596 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3597 Val <<= Val.getBitWidth() - FromBits;
3598 Val = Val.ashr(Val.getBitWidth() - FromBits);
3599 return getConstant(Val, DL, VT.getScalarType());
3603 APInt Val = N1C->getAPIntValue();
3604 return SignExtendInReg(Val);
3606 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3607 SmallVector<SDValue, 8> Ops;
3608 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3609 SDValue Op = N1.getOperand(i);
3610 if (Op.getOpcode() == ISD::UNDEF) {
3611 Ops.push_back(getUNDEF(VT.getScalarType()));
3614 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3615 APInt Val = C->getAPIntValue();
3616 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3617 Ops.push_back(SignExtendInReg(Val));
3622 if (Ops.size() == VT.getVectorNumElements())
3623 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3627 case ISD::EXTRACT_VECTOR_ELT:
3628 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3629 if (N1.getOpcode() == ISD::UNDEF)
3630 return getUNDEF(VT);
3632 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3633 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3634 return getUNDEF(VT);
3636 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3637 // expanding copies of large vectors from registers.
3639 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3640 N1.getNumOperands() > 0) {
3642 N1.getOperand(0).getValueType().getVectorNumElements();
3643 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3644 N1.getOperand(N2C->getZExtValue() / Factor),
3645 getConstant(N2C->getZExtValue() % Factor, DL,
3646 N2.getValueType()));
3649 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3650 // expanding large vector constants.
3651 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3652 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3654 if (VT != Elt.getValueType())
3655 // If the vector element type is not legal, the BUILD_VECTOR operands
3656 // are promoted and implicitly truncated, and the result implicitly
3657 // extended. Make that explicit here.
3658 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3663 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3664 // operations are lowered to scalars.
3665 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3666 // If the indices are the same, return the inserted element else
3667 // if the indices are known different, extract the element from
3668 // the original vector.
3669 SDValue N1Op2 = N1.getOperand(2);
3670 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3672 if (N1Op2C && N2C) {
3673 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3674 if (VT == N1.getOperand(1).getValueType())
3675 return N1.getOperand(1);
3677 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3680 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3684 case ISD::EXTRACT_ELEMENT:
3685 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3686 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3687 (N1.getValueType().isInteger() == VT.isInteger()) &&
3688 N1.getValueType() != VT &&
3689 "Wrong types for EXTRACT_ELEMENT!");
3691 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3692 // 64-bit integers into 32-bit parts. Instead of building the extract of
3693 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3694 if (N1.getOpcode() == ISD::BUILD_PAIR)
3695 return N1.getOperand(N2C->getZExtValue());
3697 // EXTRACT_ELEMENT of a constant int is also very common.
3698 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3699 unsigned ElementSize = VT.getSizeInBits();
3700 unsigned Shift = ElementSize * N2C->getZExtValue();
3701 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3702 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3705 case ISD::EXTRACT_SUBVECTOR: {
3707 if (VT.isSimple() && N1.getValueType().isSimple()) {
3708 assert(VT.isVector() && N1.getValueType().isVector() &&
3709 "Extract subvector VTs must be a vectors!");
3710 assert(VT.getVectorElementType() ==
3711 N1.getValueType().getVectorElementType() &&
3712 "Extract subvector VTs must have the same element type!");
3713 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3714 "Extract subvector must be from larger vector to smaller vector!");
3716 if (isa<ConstantSDNode>(Index)) {
3717 assert((VT.getVectorNumElements() +
3718 cast<ConstantSDNode>(Index)->getZExtValue()
3719 <= N1.getValueType().getVectorNumElements())
3720 && "Extract subvector overflow!");
3723 // Trivial extraction.
3724 if (VT.getSimpleVT() == N1.getSimpleValueType())
3731 // Perform trivial constant folding.
3733 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3736 // Constant fold FP operations.
3737 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3738 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3739 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3741 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3742 // Canonicalize constant to RHS if commutative.
3743 std::swap(N1CFP, N2CFP);
3746 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3747 APFloat::opStatus s;
3750 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3751 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3752 return getConstantFP(V1, DL, VT);
3755 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3756 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3757 return getConstantFP(V1, DL, VT);
3760 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3761 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3762 return getConstantFP(V1, DL, VT);
3765 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3766 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3767 s!=APFloat::opDivByZero)) {
3768 return getConstantFP(V1, DL, VT);
3773 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3774 s!=APFloat::opDivByZero)) {
3775 return getConstantFP(V1, DL, VT);
3778 case ISD::FCOPYSIGN:
3780 return getConstantFP(V1, DL, VT);
3785 if (Opcode == ISD::FP_ROUND) {
3786 APFloat V = N1CFP->getValueAPF(); // make copy
3788 // This can return overflow, underflow, or inexact; we don't care.
3789 // FIXME need to be more flexible about rounding mode.
3790 (void)V.convert(EVTToAPFloatSemantics(VT),
3791 APFloat::rmNearestTiesToEven, &ignored);
3792 return getConstantFP(V, DL, VT);
3796 // Canonicalize an UNDEF to the RHS, even over a constant.
3797 if (N1.getOpcode() == ISD::UNDEF) {
3798 if (isCommutativeBinOp(Opcode)) {
3802 case ISD::FP_ROUND_INREG:
3803 case ISD::SIGN_EXTEND_INREG:
3809 return N1; // fold op(undef, arg2) -> undef
3817 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3818 // For vectors, we can't easily build an all zero vector, just return
3825 // Fold a bunch of operators when the RHS is undef.
3826 if (N2.getOpcode() == ISD::UNDEF) {
3829 if (N1.getOpcode() == ISD::UNDEF)
3830 // Handle undef ^ undef -> 0 special case. This is a common
3832 return getConstant(0, DL, VT);
3842 return N2; // fold op(arg1, undef) -> undef
3848 if (getTarget().Options.UnsafeFPMath)
3856 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3857 // For vectors, we can't easily build an all zero vector, just return
3862 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3863 // For vectors, we can't easily build an all one vector, just return
3871 // Memoize this node if possible.
3873 SDVTList VTs = getVTList(VT);
3874 if (VT != MVT::Glue) {
3875 SDValue Ops[] = {N1, N2};
3876 FoldingSetNodeID ID;
3877 AddNodeIDNode(ID, Opcode, VTs, Ops);
3878 AddNodeIDFlags(ID, Opcode, Flags);
3880 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3881 return SDValue(E, 0);
3883 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3885 CSEMap.InsertNode(N, IP);
3887 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3891 return SDValue(N, 0);
3894 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3895 SDValue N1, SDValue N2, SDValue N3) {
3896 // Perform various simplifications.
3899 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3900 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3901 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3902 if (N1CFP && N2CFP && N3CFP) {
3903 APFloat V1 = N1CFP->getValueAPF();
3904 const APFloat &V2 = N2CFP->getValueAPF();
3905 const APFloat &V3 = N3CFP->getValueAPF();
3906 APFloat::opStatus s =
3907 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3908 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3909 return getConstantFP(V1, DL, VT);
3913 case ISD::CONCAT_VECTORS:
3914 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3915 // one big BUILD_VECTOR.
3916 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3917 N2.getOpcode() == ISD::BUILD_VECTOR &&
3918 N3.getOpcode() == ISD::BUILD_VECTOR) {
3919 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3920 N1.getNode()->op_end());
3921 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3922 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3923 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3927 // Use FoldSetCC to simplify SETCC's.
3928 if (SDValue V = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL))
3933 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
3934 if (N1C->getZExtValue())
3935 return N2; // select true, X, Y -> X
3936 return N3; // select false, X, Y -> Y
3939 if (N2 == N3) return N2; // select C, X, X -> X
3941 case ISD::VECTOR_SHUFFLE:
3942 llvm_unreachable("should use getVectorShuffle constructor!");
3943 case ISD::INSERT_SUBVECTOR: {
3945 if (VT.isSimple() && N1.getValueType().isSimple()
3946 && N2.getValueType().isSimple()) {
3947 assert(VT.isVector() && N1.getValueType().isVector() &&
3948 N2.getValueType().isVector() &&
3949 "Insert subvector VTs must be a vectors");
3950 assert(VT == N1.getValueType() &&
3951 "Dest and insert subvector source types must match!");
3952 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3953 "Insert subvector must be from smaller vector to larger vector!");
3954 if (isa<ConstantSDNode>(Index)) {
3955 assert((N2.getValueType().getVectorNumElements() +
3956 cast<ConstantSDNode>(Index)->getZExtValue()
3957 <= VT.getVectorNumElements())
3958 && "Insert subvector overflow!");
3961 // Trivial insertion.
3962 if (VT.getSimpleVT() == N2.getSimpleValueType())
3968 // Fold bit_convert nodes from a type to themselves.
3969 if (N1.getValueType() == VT)
3974 // Memoize node if it doesn't produce a flag.
3976 SDVTList VTs = getVTList(VT);
3977 if (VT != MVT::Glue) {
3978 SDValue Ops[] = { N1, N2, N3 };
3979 FoldingSetNodeID ID;
3980 AddNodeIDNode(ID, Opcode, VTs, Ops);
3982 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3983 return SDValue(E, 0);
3985 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3986 DL.getDebugLoc(), VTs, N1, N2, N3);
3987 CSEMap.InsertNode(N, IP);
3989 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3990 DL.getDebugLoc(), VTs, N1, N2, N3);
3994 return SDValue(N, 0);
3997 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3998 SDValue N1, SDValue N2, SDValue N3,
4000 SDValue Ops[] = { N1, N2, N3, N4 };
4001 return getNode(Opcode, DL, VT, Ops);
4004 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4005 SDValue N1, SDValue N2, SDValue N3,
4006 SDValue N4, SDValue N5) {
4007 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4008 return getNode(Opcode, DL, VT, Ops);
4011 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
4012 /// the incoming stack arguments to be loaded from the stack.
4013 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
4014 SmallVector<SDValue, 8> ArgChains;
4016 // Include the original chain at the beginning of the list. When this is
4017 // used by target LowerCall hooks, this helps legalize find the
4018 // CALLSEQ_BEGIN node.
4019 ArgChains.push_back(Chain);
4021 // Add a chain value for each stack argument.
4022 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
4023 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
4024 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
4025 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
4026 if (FI->getIndex() < 0)
4027 ArgChains.push_back(SDValue(L, 1));
4029 // Build a tokenfactor for all the chains.
4030 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4033 /// getMemsetValue - Vectorized representation of the memset value
4035 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4037 assert(Value.getOpcode() != ISD::UNDEF);
4039 unsigned NumBits = VT.getScalarType().getSizeInBits();
4040 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4041 assert(C->getAPIntValue().getBitWidth() == 8);
4042 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4044 return DAG.getConstant(Val, dl, VT);
4045 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4049 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4050 EVT IntVT = VT.getScalarType();
4051 if (!IntVT.isInteger())
4052 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4054 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4056 // Use a multiplication with 0x010101... to extend the input to the
4058 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4059 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4060 DAG.getConstant(Magic, dl, IntVT));
4063 if (VT != Value.getValueType() && !VT.isInteger())
4064 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4065 if (VT != Value.getValueType()) {
4066 assert(VT.getVectorElementType() == Value.getValueType() &&
4067 "value type should be one vector element here");
4068 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4069 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4075 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4076 /// used when a memcpy is turned into a memset when the source is a constant
4078 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4079 const TargetLowering &TLI, StringRef Str) {
4080 // Handle vector with all elements zero.
4083 return DAG.getConstant(0, dl, VT);
4084 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4085 return DAG.getConstantFP(0.0, dl, VT);
4086 else if (VT.isVector()) {
4087 unsigned NumElts = VT.getVectorNumElements();
4088 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4089 return DAG.getNode(ISD::BITCAST, dl, VT,
4090 DAG.getConstant(0, dl,
4091 EVT::getVectorVT(*DAG.getContext(),
4094 llvm_unreachable("Expected type!");
4097 assert(!VT.isVector() && "Can't handle vector type here!");
4098 unsigned NumVTBits = VT.getSizeInBits();
4099 unsigned NumVTBytes = NumVTBits / 8;
4100 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4102 APInt Val(NumVTBits, 0);
4103 if (DAG.getDataLayout().isLittleEndian()) {
4104 for (unsigned i = 0; i != NumBytes; ++i)
4105 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4107 for (unsigned i = 0; i != NumBytes; ++i)
4108 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4111 // If the "cost" of materializing the integer immediate is less than the cost
4112 // of a load, then it is cost effective to turn the load into the immediate.
4113 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4114 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4115 return DAG.getConstant(Val, dl, VT);
4116 return SDValue(nullptr, 0);
4119 /// getMemBasePlusOffset - Returns base and offset node for the
4121 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4122 SelectionDAG &DAG) {
4123 EVT VT = Base.getValueType();
4124 return DAG.getNode(ISD::ADD, dl,
4125 VT, Base, DAG.getConstant(Offset, dl, VT));
4128 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4130 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4131 unsigned SrcDelta = 0;
4132 GlobalAddressSDNode *G = nullptr;
4133 if (Src.getOpcode() == ISD::GlobalAddress)
4134 G = cast<GlobalAddressSDNode>(Src);
4135 else if (Src.getOpcode() == ISD::ADD &&
4136 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4137 Src.getOperand(1).getOpcode() == ISD::Constant) {
4138 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4139 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4144 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4147 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4148 /// Return true if the number of memory ops is below the threshold (Limit).
4149 /// It returns the types of the sequence of memory ops to perform
4150 /// memset / memcpy by reference.
4151 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4152 unsigned Limit, uint64_t Size,
4153 unsigned DstAlign, unsigned SrcAlign,
4159 const TargetLowering &TLI) {
4160 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4161 "Expecting memcpy / memset source to meet alignment requirement!");
4162 // If 'SrcAlign' is zero, that means the memory operation does not need to
4163 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4164 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4165 // is the specified alignment of the memory operation. If it is zero, that
4166 // means it's possible to change the alignment of the destination.
4167 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4168 // not need to be loaded.
4169 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4170 IsMemset, ZeroMemset, MemcpyStrSrc,
4171 DAG.getMachineFunction());
4173 if (VT == MVT::Other) {
4175 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4176 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4177 VT = TLI.getPointerTy(DAG.getDataLayout());
4179 switch (DstAlign & 7) {
4180 case 0: VT = MVT::i64; break;
4181 case 4: VT = MVT::i32; break;
4182 case 2: VT = MVT::i16; break;
4183 default: VT = MVT::i8; break;
4188 while (!TLI.isTypeLegal(LVT))
4189 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4190 assert(LVT.isInteger());
4196 unsigned NumMemOps = 0;
4198 unsigned VTSize = VT.getSizeInBits() / 8;
4199 while (VTSize > Size) {
4200 // For now, only use non-vector load / store's for the left-over pieces.
4205 if (VT.isVector() || VT.isFloatingPoint()) {
4206 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4207 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4208 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4210 else if (NewVT == MVT::i64 &&
4211 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4212 TLI.isSafeMemOpType(MVT::f64)) {
4213 // i64 is usually not legal on 32-bit targets, but f64 may be.
4221 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4222 if (NewVT == MVT::i8)
4224 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4226 NewVTSize = NewVT.getSizeInBits() / 8;
4228 // If the new VT cannot cover all of the remaining bits, then consider
4229 // issuing a (or a pair of) unaligned and overlapping load / store.
4230 // FIXME: Only does this for 64-bit or more since we don't have proper
4231 // cost model for unaligned load / store.
4234 if (NumMemOps && AllowOverlap &&
4235 VTSize >= 8 && NewVTSize < Size &&
4236 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4244 if (++NumMemOps > Limit)
4247 MemOps.push_back(VT);
4254 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4255 // On Darwin, -Os means optimize for size without hurting performance, so
4256 // only really optimize for size when -Oz (MinSize) is used.
4257 if (MF.getTarget().getTargetTriple().isOSDarwin())
4258 return MF.getFunction()->optForMinSize();
4259 return MF.getFunction()->optForSize();
4262 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4263 SDValue Chain, SDValue Dst,
4264 SDValue Src, uint64_t Size,
4265 unsigned Align, bool isVol,
4267 MachinePointerInfo DstPtrInfo,
4268 MachinePointerInfo SrcPtrInfo) {
4269 // Turn a memcpy of undef to nop.
4270 if (Src.getOpcode() == ISD::UNDEF)
4273 // Expand memcpy to a series of load and store ops if the size operand falls
4274 // below a certain threshold.
4275 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4276 // rather than maybe a humongous number of loads and stores.
4277 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4278 std::vector<EVT> MemOps;
4279 bool DstAlignCanChange = false;
4280 MachineFunction &MF = DAG.getMachineFunction();
4281 MachineFrameInfo *MFI = MF.getFrameInfo();
4282 bool OptSize = shouldLowerMemFuncForSize(MF);
4283 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4284 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4285 DstAlignCanChange = true;
4286 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4287 if (Align > SrcAlign)
4290 bool CopyFromStr = isMemSrcFromString(Src, Str);
4291 bool isZeroStr = CopyFromStr && Str.empty();
4292 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4294 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4295 (DstAlignCanChange ? 0 : Align),
4296 (isZeroStr ? 0 : SrcAlign),
4297 false, false, CopyFromStr, true, DAG, TLI))
4300 if (DstAlignCanChange) {
4301 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4302 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4304 // Don't promote to an alignment that would require dynamic stack
4306 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4307 if (!TRI->needsStackRealignment(MF))
4308 while (NewAlign > Align &&
4309 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4312 if (NewAlign > Align) {
4313 // Give the stack frame object a larger alignment if needed.
4314 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4315 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4320 SmallVector<SDValue, 8> OutChains;
4321 unsigned NumMemOps = MemOps.size();
4322 uint64_t SrcOff = 0, DstOff = 0;
4323 for (unsigned i = 0; i != NumMemOps; ++i) {
4325 unsigned VTSize = VT.getSizeInBits() / 8;
4326 SDValue Value, Store;
4328 if (VTSize > Size) {
4329 // Issuing an unaligned load / store pair that overlaps with the previous
4330 // pair. Adjust the offset accordingly.
4331 assert(i == NumMemOps-1 && i != 0);
4332 SrcOff -= VTSize - Size;
4333 DstOff -= VTSize - Size;
4337 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4338 // It's unlikely a store of a vector immediate can be done in a single
4339 // instruction. It would require a load from a constantpool first.
4340 // We only handle zero vectors here.
4341 // FIXME: Handle other cases where store of vector immediate is done in
4342 // a single instruction.
4343 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4344 if (Value.getNode())
4345 Store = DAG.getStore(Chain, dl, Value,
4346 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4347 DstPtrInfo.getWithOffset(DstOff), isVol,
4351 if (!Store.getNode()) {
4352 // The type might not be legal for the target. This should only happen
4353 // if the type is smaller than a legal type, as on PPC, so the right
4354 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4355 // to Load/Store if NVT==VT.
4356 // FIXME does the case above also need this?
4357 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4358 assert(NVT.bitsGE(VT));
4359 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4360 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4361 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4362 false, MinAlign(SrcAlign, SrcOff));
4363 Store = DAG.getTruncStore(Chain, dl, Value,
4364 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4365 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4368 OutChains.push_back(Store);
4374 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4377 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4378 SDValue Chain, SDValue Dst,
4379 SDValue Src, uint64_t Size,
4380 unsigned Align, bool isVol,
4382 MachinePointerInfo DstPtrInfo,
4383 MachinePointerInfo SrcPtrInfo) {
4384 // Turn a memmove of undef to nop.
4385 if (Src.getOpcode() == ISD::UNDEF)
4388 // Expand memmove to a series of load and store ops if the size operand falls
4389 // below a certain threshold.
4390 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4391 std::vector<EVT> MemOps;
4392 bool DstAlignCanChange = false;
4393 MachineFunction &MF = DAG.getMachineFunction();
4394 MachineFrameInfo *MFI = MF.getFrameInfo();
4395 bool OptSize = shouldLowerMemFuncForSize(MF);
4396 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4397 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4398 DstAlignCanChange = true;
4399 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4400 if (Align > SrcAlign)
4402 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4404 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4405 (DstAlignCanChange ? 0 : Align), SrcAlign,
4406 false, false, false, false, DAG, TLI))
4409 if (DstAlignCanChange) {
4410 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4411 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4412 if (NewAlign > Align) {
4413 // Give the stack frame object a larger alignment if needed.
4414 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4415 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4420 uint64_t SrcOff = 0, DstOff = 0;
4421 SmallVector<SDValue, 8> LoadValues;
4422 SmallVector<SDValue, 8> LoadChains;
4423 SmallVector<SDValue, 8> OutChains;
4424 unsigned NumMemOps = MemOps.size();
4425 for (unsigned i = 0; i < NumMemOps; i++) {
4427 unsigned VTSize = VT.getSizeInBits() / 8;
4430 Value = DAG.getLoad(VT, dl, Chain,
4431 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4432 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4433 false, false, SrcAlign);
4434 LoadValues.push_back(Value);
4435 LoadChains.push_back(Value.getValue(1));
4438 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4440 for (unsigned i = 0; i < NumMemOps; i++) {
4442 unsigned VTSize = VT.getSizeInBits() / 8;
4445 Store = DAG.getStore(Chain, dl, LoadValues[i],
4446 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4447 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4448 OutChains.push_back(Store);
4452 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4455 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4458 /// \param DAG Selection DAG where lowered code is placed.
4459 /// \param dl Link to corresponding IR location.
4460 /// \param Chain Control flow dependency.
4461 /// \param Dst Pointer to destination memory location.
4462 /// \param Src Value of byte to write into the memory.
4463 /// \param Size Number of bytes to write.
4464 /// \param Align Alignment of the destination in bytes.
4465 /// \param isVol True if destination is volatile.
4466 /// \param DstPtrInfo IR information on the memory pointer.
4467 /// \returns New head in the control flow, if lowering was successful, empty
4468 /// SDValue otherwise.
4470 /// The function tries to replace 'llvm.memset' intrinsic with several store
4471 /// operations and value calculation code. This is usually profitable for small
4473 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4474 SDValue Chain, SDValue Dst,
4475 SDValue Src, uint64_t Size,
4476 unsigned Align, bool isVol,
4477 MachinePointerInfo DstPtrInfo) {
4478 // Turn a memset of undef to nop.
4479 if (Src.getOpcode() == ISD::UNDEF)
4482 // Expand memset to a series of load/store ops if the size operand
4483 // falls below a certain threshold.
4484 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4485 std::vector<EVT> MemOps;
4486 bool DstAlignCanChange = false;
4487 MachineFunction &MF = DAG.getMachineFunction();
4488 MachineFrameInfo *MFI = MF.getFrameInfo();
4489 bool OptSize = shouldLowerMemFuncForSize(MF);
4490 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4491 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4492 DstAlignCanChange = true;
4494 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4495 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4496 Size, (DstAlignCanChange ? 0 : Align), 0,
4497 true, IsZeroVal, false, true, DAG, TLI))
4500 if (DstAlignCanChange) {
4501 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4502 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4503 if (NewAlign > Align) {
4504 // Give the stack frame object a larger alignment if needed.
4505 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4506 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4511 SmallVector<SDValue, 8> OutChains;
4512 uint64_t DstOff = 0;
4513 unsigned NumMemOps = MemOps.size();
4515 // Find the largest store and generate the bit pattern for it.
4516 EVT LargestVT = MemOps[0];
4517 for (unsigned i = 1; i < NumMemOps; i++)
4518 if (MemOps[i].bitsGT(LargestVT))
4519 LargestVT = MemOps[i];
4520 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4522 for (unsigned i = 0; i < NumMemOps; i++) {
4524 unsigned VTSize = VT.getSizeInBits() / 8;
4525 if (VTSize > Size) {
4526 // Issuing an unaligned load / store pair that overlaps with the previous
4527 // pair. Adjust the offset accordingly.
4528 assert(i == NumMemOps-1 && i != 0);
4529 DstOff -= VTSize - Size;
4532 // If this store is smaller than the largest store see whether we can get
4533 // the smaller value for free with a truncate.
4534 SDValue Value = MemSetValue;
4535 if (VT.bitsLT(LargestVT)) {
4536 if (!LargestVT.isVector() && !VT.isVector() &&
4537 TLI.isTruncateFree(LargestVT, VT))
4538 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4540 Value = getMemsetValue(Src, VT, DAG, dl);
4542 assert(Value.getValueType() == VT && "Value with wrong type.");
4543 SDValue Store = DAG.getStore(Chain, dl, Value,
4544 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4545 DstPtrInfo.getWithOffset(DstOff),
4546 isVol, false, Align);
4547 OutChains.push_back(Store);
4548 DstOff += VT.getSizeInBits() / 8;
4552 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4555 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4556 SDValue Src, SDValue Size,
4557 unsigned Align, bool isVol, bool AlwaysInline,
4558 bool isTailCall, MachinePointerInfo DstPtrInfo,
4559 MachinePointerInfo SrcPtrInfo) {
4560 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4562 // Check to see if we should lower the memcpy to loads and stores first.
4563 // For cases within the target-specified limits, this is the best choice.
4564 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4566 // Memcpy with size zero? Just return the original chain.
4567 if (ConstantSize->isNullValue())
4570 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4571 ConstantSize->getZExtValue(),Align,
4572 isVol, false, DstPtrInfo, SrcPtrInfo);
4573 if (Result.getNode())
4577 // Then check to see if we should lower the memcpy with target-specific
4578 // code. If the target chooses to do this, this is the next best.
4580 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4581 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4582 DstPtrInfo, SrcPtrInfo);
4583 if (Result.getNode())
4587 // If we really need inline code and the target declined to provide it,
4588 // use a (potentially long) sequence of loads and stores.
4590 assert(ConstantSize && "AlwaysInline requires a constant size!");
4591 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4592 ConstantSize->getZExtValue(), Align, isVol,
4593 true, DstPtrInfo, SrcPtrInfo);
4596 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4597 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4598 // respect volatile, so they may do things like read or write memory
4599 // beyond the given memory regions. But fixing this isn't easy, and most
4600 // people don't care.
4602 // Emit a library call.
4603 TargetLowering::ArgListTy Args;
4604 TargetLowering::ArgListEntry Entry;
4605 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4606 Entry.Node = Dst; Args.push_back(Entry);
4607 Entry.Node = Src; Args.push_back(Entry);
4608 Entry.Node = Size; Args.push_back(Entry);
4609 // FIXME: pass in SDLoc
4610 TargetLowering::CallLoweringInfo CLI(*this);
4613 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4614 Type::getVoidTy(*getContext()),
4615 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4616 TLI->getPointerTy(getDataLayout())),
4619 .setTailCall(isTailCall);
4621 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4622 return CallResult.second;
4625 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4626 SDValue Src, SDValue Size,
4627 unsigned Align, bool isVol, bool isTailCall,
4628 MachinePointerInfo DstPtrInfo,
4629 MachinePointerInfo SrcPtrInfo) {
4630 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4632 // Check to see if we should lower the memmove to loads and stores first.
4633 // For cases within the target-specified limits, this is the best choice.
4634 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4636 // Memmove with size zero? Just return the original chain.
4637 if (ConstantSize->isNullValue())
4641 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4642 ConstantSize->getZExtValue(), Align, isVol,
4643 false, DstPtrInfo, SrcPtrInfo);
4644 if (Result.getNode())
4648 // Then check to see if we should lower the memmove with target-specific
4649 // code. If the target chooses to do this, this is the next best.
4651 SDValue Result = TSI->EmitTargetCodeForMemmove(
4652 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4653 if (Result.getNode())
4657 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4658 // not be safe. See memcpy above for more details.
4660 // Emit a library call.
4661 TargetLowering::ArgListTy Args;
4662 TargetLowering::ArgListEntry Entry;
4663 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4664 Entry.Node = Dst; Args.push_back(Entry);
4665 Entry.Node = Src; Args.push_back(Entry);
4666 Entry.Node = Size; Args.push_back(Entry);
4667 // FIXME: pass in SDLoc
4668 TargetLowering::CallLoweringInfo CLI(*this);
4671 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4672 Type::getVoidTy(*getContext()),
4673 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4674 TLI->getPointerTy(getDataLayout())),
4677 .setTailCall(isTailCall);
4679 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4680 return CallResult.second;
4683 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4684 SDValue Src, SDValue Size,
4685 unsigned Align, bool isVol, bool isTailCall,
4686 MachinePointerInfo DstPtrInfo) {
4687 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4689 // Check to see if we should lower the memset to stores first.
4690 // For cases within the target-specified limits, this is the best choice.
4691 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4693 // Memset with size zero? Just return the original chain.
4694 if (ConstantSize->isNullValue())
4698 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4699 Align, isVol, DstPtrInfo);
4701 if (Result.getNode())
4705 // Then check to see if we should lower the memset with target-specific
4706 // code. If the target chooses to do this, this is the next best.
4708 SDValue Result = TSI->EmitTargetCodeForMemset(
4709 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4710 if (Result.getNode())
4714 // Emit a library call.
4715 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4716 TargetLowering::ArgListTy Args;
4717 TargetLowering::ArgListEntry Entry;
4718 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4719 Args.push_back(Entry);
4721 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4722 Args.push_back(Entry);
4724 Entry.Ty = IntPtrTy;
4725 Args.push_back(Entry);
4727 // FIXME: pass in SDLoc
4728 TargetLowering::CallLoweringInfo CLI(*this);
4731 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4732 Type::getVoidTy(*getContext()),
4733 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4734 TLI->getPointerTy(getDataLayout())),
4737 .setTailCall(isTailCall);
4739 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4740 return CallResult.second;
4743 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4744 SDVTList VTList, ArrayRef<SDValue> Ops,
4745 MachineMemOperand *MMO,
4746 AtomicOrdering SuccessOrdering,
4747 AtomicOrdering FailureOrdering,
4748 SynchronizationScope SynchScope) {
4749 FoldingSetNodeID ID;
4750 ID.AddInteger(MemVT.getRawBits());
4751 AddNodeIDNode(ID, Opcode, VTList, Ops);
4752 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4754 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4755 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4756 return SDValue(E, 0);
4759 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4760 // SDNode doesn't have access to it. This memory will be "leaked" when
4761 // the node is deallocated, but recovered when the allocator is released.
4762 // If the number of operands is less than 5 we use AtomicSDNode's internal
4764 unsigned NumOps = Ops.size();
4765 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4768 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4769 dl.getDebugLoc(), VTList, MemVT,
4770 Ops.data(), DynOps, NumOps, MMO,
4771 SuccessOrdering, FailureOrdering,
4773 CSEMap.InsertNode(N, IP);
4775 return SDValue(N, 0);
4778 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4779 SDVTList VTList, ArrayRef<SDValue> Ops,
4780 MachineMemOperand *MMO,
4781 AtomicOrdering Ordering,
4782 SynchronizationScope SynchScope) {
4783 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4784 Ordering, SynchScope);
4787 SDValue SelectionDAG::getAtomicCmpSwap(
4788 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4789 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4790 unsigned Alignment, AtomicOrdering SuccessOrdering,
4791 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4792 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4793 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4794 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4796 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4797 Alignment = getEVTAlignment(MemVT);
4799 MachineFunction &MF = getMachineFunction();
4801 // FIXME: Volatile isn't really correct; we should keep track of atomic
4802 // orderings in the memoperand.
4803 unsigned Flags = MachineMemOperand::MOVolatile;
4804 Flags |= MachineMemOperand::MOLoad;
4805 Flags |= MachineMemOperand::MOStore;
4807 MachineMemOperand *MMO =
4808 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4810 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4811 SuccessOrdering, FailureOrdering, SynchScope);
4814 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4815 SDVTList VTs, SDValue Chain, SDValue Ptr,
4816 SDValue Cmp, SDValue Swp,
4817 MachineMemOperand *MMO,
4818 AtomicOrdering SuccessOrdering,
4819 AtomicOrdering FailureOrdering,
4820 SynchronizationScope SynchScope) {
4821 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4822 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4823 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4825 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4826 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4827 SuccessOrdering, FailureOrdering, SynchScope);
4830 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4832 SDValue Ptr, SDValue Val,
4833 const Value* PtrVal,
4835 AtomicOrdering Ordering,
4836 SynchronizationScope SynchScope) {
4837 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4838 Alignment = getEVTAlignment(MemVT);
4840 MachineFunction &MF = getMachineFunction();
4841 // An atomic store does not load. An atomic load does not store.
4842 // (An atomicrmw obviously both loads and stores.)
4843 // For now, atomics are considered to be volatile always, and they are
4845 // FIXME: Volatile isn't really correct; we should keep track of atomic
4846 // orderings in the memoperand.
4847 unsigned Flags = MachineMemOperand::MOVolatile;
4848 if (Opcode != ISD::ATOMIC_STORE)
4849 Flags |= MachineMemOperand::MOLoad;
4850 if (Opcode != ISD::ATOMIC_LOAD)
4851 Flags |= MachineMemOperand::MOStore;
4853 MachineMemOperand *MMO =
4854 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4855 MemVT.getStoreSize(), Alignment);
4857 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4858 Ordering, SynchScope);
4861 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4863 SDValue Ptr, SDValue Val,
4864 MachineMemOperand *MMO,
4865 AtomicOrdering Ordering,
4866 SynchronizationScope SynchScope) {
4867 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4868 Opcode == ISD::ATOMIC_LOAD_SUB ||
4869 Opcode == ISD::ATOMIC_LOAD_AND ||
4870 Opcode == ISD::ATOMIC_LOAD_OR ||
4871 Opcode == ISD::ATOMIC_LOAD_XOR ||
4872 Opcode == ISD::ATOMIC_LOAD_NAND ||
4873 Opcode == ISD::ATOMIC_LOAD_MIN ||
4874 Opcode == ISD::ATOMIC_LOAD_MAX ||
4875 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4876 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4877 Opcode == ISD::ATOMIC_SWAP ||
4878 Opcode == ISD::ATOMIC_STORE) &&
4879 "Invalid Atomic Op");
4881 EVT VT = Val.getValueType();
4883 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4884 getVTList(VT, MVT::Other);
4885 SDValue Ops[] = {Chain, Ptr, Val};
4886 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4889 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4890 EVT VT, SDValue Chain,
4892 MachineMemOperand *MMO,
4893 AtomicOrdering Ordering,
4894 SynchronizationScope SynchScope) {
4895 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4897 SDVTList VTs = getVTList(VT, MVT::Other);
4898 SDValue Ops[] = {Chain, Ptr};
4899 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4902 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4903 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4904 if (Ops.size() == 1)
4907 SmallVector<EVT, 4> VTs;
4908 VTs.reserve(Ops.size());
4909 for (unsigned i = 0; i < Ops.size(); ++i)
4910 VTs.push_back(Ops[i].getValueType());
4911 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4915 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4916 ArrayRef<SDValue> Ops,
4917 EVT MemVT, MachinePointerInfo PtrInfo,
4918 unsigned Align, bool Vol,
4919 bool ReadMem, bool WriteMem, unsigned Size) {
4920 if (Align == 0) // Ensure that codegen never sees alignment 0
4921 Align = getEVTAlignment(MemVT);
4923 MachineFunction &MF = getMachineFunction();
4926 Flags |= MachineMemOperand::MOStore;
4928 Flags |= MachineMemOperand::MOLoad;
4930 Flags |= MachineMemOperand::MOVolatile;
4932 Size = MemVT.getStoreSize();
4933 MachineMemOperand *MMO =
4934 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4936 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4940 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4941 ArrayRef<SDValue> Ops, EVT MemVT,
4942 MachineMemOperand *MMO) {
4943 assert((Opcode == ISD::INTRINSIC_VOID ||
4944 Opcode == ISD::INTRINSIC_W_CHAIN ||
4945 Opcode == ISD::PREFETCH ||
4946 Opcode == ISD::LIFETIME_START ||
4947 Opcode == ISD::LIFETIME_END ||
4948 (Opcode <= INT_MAX &&
4949 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4950 "Opcode is not a memory-accessing opcode!");
4952 // Memoize the node unless it returns a flag.
4953 MemIntrinsicSDNode *N;
4954 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4955 FoldingSetNodeID ID;
4956 AddNodeIDNode(ID, Opcode, VTList, Ops);
4957 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4959 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4960 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4961 return SDValue(E, 0);
4964 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4965 dl.getDebugLoc(), VTList, Ops,
4967 CSEMap.InsertNode(N, IP);
4969 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4970 dl.getDebugLoc(), VTList, Ops,
4974 return SDValue(N, 0);
4977 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4978 /// MachinePointerInfo record from it. This is particularly useful because the
4979 /// code generator has many cases where it doesn't bother passing in a
4980 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4981 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4982 int64_t Offset = 0) {
4983 // If this is FI+Offset, we can model it.
4984 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4985 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4986 FI->getIndex(), Offset);
4988 // If this is (FI+Offset1)+Offset2, we can model it.
4989 if (Ptr.getOpcode() != ISD::ADD ||
4990 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4991 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4992 return MachinePointerInfo();
4994 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4995 return MachinePointerInfo::getFixedStack(
4996 DAG.getMachineFunction(), FI,
4997 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
5000 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
5001 /// MachinePointerInfo record from it. This is particularly useful because the
5002 /// code generator has many cases where it doesn't bother passing in a
5003 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
5004 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
5006 // If the 'Offset' value isn't a constant, we can't handle this.
5007 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
5008 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
5009 if (OffsetOp.getOpcode() == ISD::UNDEF)
5010 return InferPointerInfo(DAG, Ptr);
5011 return MachinePointerInfo();
5016 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5017 EVT VT, SDLoc dl, SDValue Chain,
5018 SDValue Ptr, SDValue Offset,
5019 MachinePointerInfo PtrInfo, EVT MemVT,
5020 bool isVolatile, bool isNonTemporal, bool isInvariant,
5021 unsigned Alignment, const AAMDNodes &AAInfo,
5022 const MDNode *Ranges) {
5023 assert(Chain.getValueType() == MVT::Other &&
5024 "Invalid chain type");
5025 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5026 Alignment = getEVTAlignment(VT);
5028 unsigned Flags = MachineMemOperand::MOLoad;
5030 Flags |= MachineMemOperand::MOVolatile;
5032 Flags |= MachineMemOperand::MONonTemporal;
5034 Flags |= MachineMemOperand::MOInvariant;
5036 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5038 if (PtrInfo.V.isNull())
5039 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5041 MachineFunction &MF = getMachineFunction();
5042 MachineMemOperand *MMO =
5043 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5045 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5049 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5050 EVT VT, SDLoc dl, SDValue Chain,
5051 SDValue Ptr, SDValue Offset, EVT MemVT,
5052 MachineMemOperand *MMO) {
5054 ExtType = ISD::NON_EXTLOAD;
5055 } else if (ExtType == ISD::NON_EXTLOAD) {
5056 assert(VT == MemVT && "Non-extending load from different memory type!");
5059 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5060 "Should only be an extending load, not truncating!");
5061 assert(VT.isInteger() == MemVT.isInteger() &&
5062 "Cannot convert from FP to Int or Int -> FP!");
5063 assert(VT.isVector() == MemVT.isVector() &&
5064 "Cannot use an ext load to convert to or from a vector!");
5065 assert((!VT.isVector() ||
5066 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5067 "Cannot use an ext load to change the number of vector elements!");
5070 bool Indexed = AM != ISD::UNINDEXED;
5071 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5072 "Unindexed load with an offset!");
5074 SDVTList VTs = Indexed ?
5075 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5076 SDValue Ops[] = { Chain, Ptr, Offset };
5077 FoldingSetNodeID ID;
5078 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5079 ID.AddInteger(MemVT.getRawBits());
5080 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5081 MMO->isNonTemporal(),
5082 MMO->isInvariant()));
5083 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5085 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5086 cast<LoadSDNode>(E)->refineAlignment(MMO);
5087 return SDValue(E, 0);
5089 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5090 dl.getDebugLoc(), VTs, AM, ExtType,
5092 CSEMap.InsertNode(N, IP);
5094 return SDValue(N, 0);
5097 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5098 SDValue Chain, SDValue Ptr,
5099 MachinePointerInfo PtrInfo,
5100 bool isVolatile, bool isNonTemporal,
5101 bool isInvariant, unsigned Alignment,
5102 const AAMDNodes &AAInfo,
5103 const MDNode *Ranges) {
5104 SDValue Undef = getUNDEF(Ptr.getValueType());
5105 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5106 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5110 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5111 SDValue Chain, SDValue Ptr,
5112 MachineMemOperand *MMO) {
5113 SDValue Undef = getUNDEF(Ptr.getValueType());
5114 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5118 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5119 SDValue Chain, SDValue Ptr,
5120 MachinePointerInfo PtrInfo, EVT MemVT,
5121 bool isVolatile, bool isNonTemporal,
5122 bool isInvariant, unsigned Alignment,
5123 const AAMDNodes &AAInfo) {
5124 SDValue Undef = getUNDEF(Ptr.getValueType());
5125 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5126 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5131 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5132 SDValue Chain, SDValue Ptr, EVT MemVT,
5133 MachineMemOperand *MMO) {
5134 SDValue Undef = getUNDEF(Ptr.getValueType());
5135 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5140 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5141 SDValue Offset, ISD::MemIndexedMode AM) {
5142 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5143 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5144 "Load is already a indexed load!");
5145 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5146 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5147 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5148 false, LD->getAlignment());
5151 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5152 SDValue Ptr, MachinePointerInfo PtrInfo,
5153 bool isVolatile, bool isNonTemporal,
5154 unsigned Alignment, const AAMDNodes &AAInfo) {
5155 assert(Chain.getValueType() == MVT::Other &&
5156 "Invalid chain type");
5157 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5158 Alignment = getEVTAlignment(Val.getValueType());
5160 unsigned Flags = MachineMemOperand::MOStore;
5162 Flags |= MachineMemOperand::MOVolatile;
5164 Flags |= MachineMemOperand::MONonTemporal;
5166 if (PtrInfo.V.isNull())
5167 PtrInfo = InferPointerInfo(*this, Ptr);
5169 MachineFunction &MF = getMachineFunction();
5170 MachineMemOperand *MMO =
5171 MF.getMachineMemOperand(PtrInfo, Flags,
5172 Val.getValueType().getStoreSize(), Alignment,
5175 return getStore(Chain, dl, Val, Ptr, MMO);
5178 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5179 SDValue Ptr, MachineMemOperand *MMO) {
5180 assert(Chain.getValueType() == MVT::Other &&
5181 "Invalid chain type");
5182 EVT VT = Val.getValueType();
5183 SDVTList VTs = getVTList(MVT::Other);
5184 SDValue Undef = getUNDEF(Ptr.getValueType());
5185 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5186 FoldingSetNodeID ID;
5187 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5188 ID.AddInteger(VT.getRawBits());
5189 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5190 MMO->isNonTemporal(), MMO->isInvariant()));
5191 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5193 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5194 cast<StoreSDNode>(E)->refineAlignment(MMO);
5195 return SDValue(E, 0);
5197 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5198 dl.getDebugLoc(), VTs,
5199 ISD::UNINDEXED, false, VT, MMO);
5200 CSEMap.InsertNode(N, IP);
5202 return SDValue(N, 0);
5205 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5206 SDValue Ptr, MachinePointerInfo PtrInfo,
5207 EVT SVT,bool isVolatile, bool isNonTemporal,
5209 const AAMDNodes &AAInfo) {
5210 assert(Chain.getValueType() == MVT::Other &&
5211 "Invalid chain type");
5212 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5213 Alignment = getEVTAlignment(SVT);
5215 unsigned Flags = MachineMemOperand::MOStore;
5217 Flags |= MachineMemOperand::MOVolatile;
5219 Flags |= MachineMemOperand::MONonTemporal;
5221 if (PtrInfo.V.isNull())
5222 PtrInfo = InferPointerInfo(*this, Ptr);
5224 MachineFunction &MF = getMachineFunction();
5225 MachineMemOperand *MMO =
5226 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5229 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5232 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5233 SDValue Ptr, EVT SVT,
5234 MachineMemOperand *MMO) {
5235 EVT VT = Val.getValueType();
5237 assert(Chain.getValueType() == MVT::Other &&
5238 "Invalid chain type");
5240 return getStore(Chain, dl, Val, Ptr, MMO);
5242 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5243 "Should only be a truncating store, not extending!");
5244 assert(VT.isInteger() == SVT.isInteger() &&
5245 "Can't do FP-INT conversion!");
5246 assert(VT.isVector() == SVT.isVector() &&
5247 "Cannot use trunc store to convert to or from a vector!");
5248 assert((!VT.isVector() ||
5249 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5250 "Cannot use trunc store to change the number of vector elements!");
5252 SDVTList VTs = getVTList(MVT::Other);
5253 SDValue Undef = getUNDEF(Ptr.getValueType());
5254 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5255 FoldingSetNodeID ID;
5256 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5257 ID.AddInteger(SVT.getRawBits());
5258 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5259 MMO->isNonTemporal(), MMO->isInvariant()));
5260 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5262 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5263 cast<StoreSDNode>(E)->refineAlignment(MMO);
5264 return SDValue(E, 0);
5266 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5267 dl.getDebugLoc(), VTs,
5268 ISD::UNINDEXED, true, SVT, MMO);
5269 CSEMap.InsertNode(N, IP);
5271 return SDValue(N, 0);
5275 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5276 SDValue Offset, ISD::MemIndexedMode AM) {
5277 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5278 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5279 "Store is already a indexed store!");
5280 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5281 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5282 FoldingSetNodeID ID;
5283 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5284 ID.AddInteger(ST->getMemoryVT().getRawBits());
5285 ID.AddInteger(ST->getRawSubclassData());
5286 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5288 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5289 return SDValue(E, 0);
5291 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5292 dl.getDebugLoc(), VTs, AM,
5293 ST->isTruncatingStore(),
5295 ST->getMemOperand());
5296 CSEMap.InsertNode(N, IP);
5298 return SDValue(N, 0);
5302 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5303 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5304 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5306 SDVTList VTs = getVTList(VT, MVT::Other);
5307 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5308 FoldingSetNodeID ID;
5309 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5310 ID.AddInteger(VT.getRawBits());
5311 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5313 MMO->isNonTemporal(),
5314 MMO->isInvariant()));
5315 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5317 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5318 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5319 return SDValue(E, 0);
5321 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5322 dl.getDebugLoc(), Ops, 4, VTs,
5324 CSEMap.InsertNode(N, IP);
5326 return SDValue(N, 0);
5329 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5330 SDValue Ptr, SDValue Mask, EVT MemVT,
5331 MachineMemOperand *MMO, bool isTrunc) {
5332 assert(Chain.getValueType() == MVT::Other &&
5333 "Invalid chain type");
5334 EVT VT = Val.getValueType();
5335 SDVTList VTs = getVTList(MVT::Other);
5336 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5337 FoldingSetNodeID ID;
5338 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5339 ID.AddInteger(VT.getRawBits());
5340 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5341 MMO->isNonTemporal(), MMO->isInvariant()));
5342 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5344 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5345 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5346 return SDValue(E, 0);
5348 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5349 dl.getDebugLoc(), Ops, 4,
5350 VTs, isTrunc, MemVT, MMO);
5351 CSEMap.InsertNode(N, IP);
5353 return SDValue(N, 0);
5357 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5358 ArrayRef<SDValue> Ops,
5359 MachineMemOperand *MMO) {
5361 FoldingSetNodeID ID;
5362 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5363 ID.AddInteger(VT.getRawBits());
5364 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5366 MMO->isNonTemporal(),
5367 MMO->isInvariant()));
5368 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5370 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5371 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5372 return SDValue(E, 0);
5374 MaskedGatherSDNode *N =
5375 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5377 CSEMap.InsertNode(N, IP);
5379 return SDValue(N, 0);
5382 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5383 ArrayRef<SDValue> Ops,
5384 MachineMemOperand *MMO) {
5385 FoldingSetNodeID ID;
5386 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5387 ID.AddInteger(VT.getRawBits());
5388 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5389 MMO->isNonTemporal(),
5390 MMO->isInvariant()));
5391 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5393 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5394 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5395 return SDValue(E, 0);
5398 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5400 CSEMap.InsertNode(N, IP);
5402 return SDValue(N, 0);
5405 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5406 SDValue Chain, SDValue Ptr,
5409 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5410 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5413 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5414 ArrayRef<SDUse> Ops) {
5415 switch (Ops.size()) {
5416 case 0: return getNode(Opcode, DL, VT);
5417 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5418 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5419 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5423 // Copy from an SDUse array into an SDValue array for use with
5424 // the regular getNode logic.
5425 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5426 return getNode(Opcode, DL, VT, NewOps);
5429 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5430 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5431 unsigned NumOps = Ops.size();
5433 case 0: return getNode(Opcode, DL, VT);
5434 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5435 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5436 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5442 case ISD::SELECT_CC: {
5443 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5444 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5445 "LHS and RHS of condition must have same type!");
5446 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5447 "True and False arms of SelectCC must have same type!");
5448 assert(Ops[2].getValueType() == VT &&
5449 "select_cc node must be of same type as true and false value!");
5453 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5454 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5455 "LHS/RHS of comparison should match types!");
5462 SDVTList VTs = getVTList(VT);
5464 if (VT != MVT::Glue) {
5465 FoldingSetNodeID ID;
5466 AddNodeIDNode(ID, Opcode, VTs, Ops);
5469 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5470 return SDValue(E, 0);
5472 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5474 CSEMap.InsertNode(N, IP);
5476 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5481 return SDValue(N, 0);
5484 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5485 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5486 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5489 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5490 ArrayRef<SDValue> Ops) {
5491 if (VTList.NumVTs == 1)
5492 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5496 // FIXME: figure out how to safely handle things like
5497 // int foo(int x) { return 1 << (x & 255); }
5498 // int bar() { return foo(256); }
5499 case ISD::SRA_PARTS:
5500 case ISD::SRL_PARTS:
5501 case ISD::SHL_PARTS:
5502 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5503 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5504 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5505 else if (N3.getOpcode() == ISD::AND)
5506 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5507 // If the and is only masking out bits that cannot effect the shift,
5508 // eliminate the and.
5509 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5510 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5511 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5517 // Memoize the node unless it returns a flag.
5519 unsigned NumOps = Ops.size();
5520 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5521 FoldingSetNodeID ID;
5522 AddNodeIDNode(ID, Opcode, VTList, Ops);
5524 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5525 return SDValue(E, 0);
5528 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5529 DL.getDebugLoc(), VTList, Ops[0]);
5530 } else if (NumOps == 2) {
5531 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5532 DL.getDebugLoc(), VTList, Ops[0],
5534 } else if (NumOps == 3) {
5535 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5536 DL.getDebugLoc(), VTList, Ops[0],
5539 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5542 CSEMap.InsertNode(N, IP);
5545 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5546 DL.getDebugLoc(), VTList, Ops[0]);
5547 } else if (NumOps == 2) {
5548 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5549 DL.getDebugLoc(), VTList, Ops[0],
5551 } else if (NumOps == 3) {
5552 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5553 DL.getDebugLoc(), VTList, Ops[0],
5556 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5561 return SDValue(N, 0);
5564 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5565 return getNode(Opcode, DL, VTList, None);
5568 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5570 SDValue Ops[] = { N1 };
5571 return getNode(Opcode, DL, VTList, Ops);
5574 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5575 SDValue N1, SDValue N2) {
5576 SDValue Ops[] = { N1, N2 };
5577 return getNode(Opcode, DL, VTList, Ops);
5580 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5581 SDValue N1, SDValue N2, SDValue N3) {
5582 SDValue Ops[] = { N1, N2, N3 };
5583 return getNode(Opcode, DL, VTList, Ops);
5586 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5587 SDValue N1, SDValue N2, SDValue N3,
5589 SDValue Ops[] = { N1, N2, N3, N4 };
5590 return getNode(Opcode, DL, VTList, Ops);
5593 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5594 SDValue N1, SDValue N2, SDValue N3,
5595 SDValue N4, SDValue N5) {
5596 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5597 return getNode(Opcode, DL, VTList, Ops);
5600 SDVTList SelectionDAG::getVTList(EVT VT) {
5601 return makeVTList(SDNode::getValueTypeList(VT), 1);
5604 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5605 FoldingSetNodeID ID;
5607 ID.AddInteger(VT1.getRawBits());
5608 ID.AddInteger(VT2.getRawBits());
5611 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5613 EVT *Array = Allocator.Allocate<EVT>(2);
5616 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5617 VTListMap.InsertNode(Result, IP);
5619 return Result->getSDVTList();
5622 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5623 FoldingSetNodeID ID;
5625 ID.AddInteger(VT1.getRawBits());
5626 ID.AddInteger(VT2.getRawBits());
5627 ID.AddInteger(VT3.getRawBits());
5630 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5632 EVT *Array = Allocator.Allocate<EVT>(3);
5636 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5637 VTListMap.InsertNode(Result, IP);
5639 return Result->getSDVTList();
5642 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5643 FoldingSetNodeID ID;
5645 ID.AddInteger(VT1.getRawBits());
5646 ID.AddInteger(VT2.getRawBits());
5647 ID.AddInteger(VT3.getRawBits());
5648 ID.AddInteger(VT4.getRawBits());
5651 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5653 EVT *Array = Allocator.Allocate<EVT>(4);
5658 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5659 VTListMap.InsertNode(Result, IP);
5661 return Result->getSDVTList();
5664 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5665 unsigned NumVTs = VTs.size();
5666 FoldingSetNodeID ID;
5667 ID.AddInteger(NumVTs);
5668 for (unsigned index = 0; index < NumVTs; index++) {
5669 ID.AddInteger(VTs[index].getRawBits());
5673 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5675 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5676 std::copy(VTs.begin(), VTs.end(), Array);
5677 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5678 VTListMap.InsertNode(Result, IP);
5680 return Result->getSDVTList();
5684 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5685 /// specified operands. If the resultant node already exists in the DAG,
5686 /// this does not modify the specified node, instead it returns the node that
5687 /// already exists. If the resultant node does not exist in the DAG, the
5688 /// input node is returned. As a degenerate case, if you specify the same
5689 /// input operands as the node already has, the input node is returned.
5690 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5691 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5693 // Check to see if there is no change.
5694 if (Op == N->getOperand(0)) return N;
5696 // See if the modified node already exists.
5697 void *InsertPos = nullptr;
5698 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5701 // Nope it doesn't. Remove the node from its current place in the maps.
5703 if (!RemoveNodeFromCSEMaps(N))
5704 InsertPos = nullptr;
5706 // Now we update the operands.
5707 N->OperandList[0].set(Op);
5709 // If this gets put into a CSE map, add it.
5710 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5714 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5715 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5717 // Check to see if there is no change.
5718 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5719 return N; // No operands changed, just return the input node.
5721 // See if the modified node already exists.
5722 void *InsertPos = nullptr;
5723 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5726 // Nope it doesn't. Remove the node from its current place in the maps.
5728 if (!RemoveNodeFromCSEMaps(N))
5729 InsertPos = nullptr;
5731 // Now we update the operands.
5732 if (N->OperandList[0] != Op1)
5733 N->OperandList[0].set(Op1);
5734 if (N->OperandList[1] != Op2)
5735 N->OperandList[1].set(Op2);
5737 // If this gets put into a CSE map, add it.
5738 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5742 SDNode *SelectionDAG::
5743 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5744 SDValue Ops[] = { Op1, Op2, Op3 };
5745 return UpdateNodeOperands(N, Ops);
5748 SDNode *SelectionDAG::
5749 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5750 SDValue Op3, SDValue Op4) {
5751 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5752 return UpdateNodeOperands(N, Ops);
5755 SDNode *SelectionDAG::
5756 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5757 SDValue Op3, SDValue Op4, SDValue Op5) {
5758 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5759 return UpdateNodeOperands(N, Ops);
5762 SDNode *SelectionDAG::
5763 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5764 unsigned NumOps = Ops.size();
5765 assert(N->getNumOperands() == NumOps &&
5766 "Update with wrong number of operands");
5768 // If no operands changed just return the input node.
5769 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5772 // See if the modified node already exists.
5773 void *InsertPos = nullptr;
5774 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5777 // Nope it doesn't. Remove the node from its current place in the maps.
5779 if (!RemoveNodeFromCSEMaps(N))
5780 InsertPos = nullptr;
5782 // Now we update the operands.
5783 for (unsigned i = 0; i != NumOps; ++i)
5784 if (N->OperandList[i] != Ops[i])
5785 N->OperandList[i].set(Ops[i]);
5787 // If this gets put into a CSE map, add it.
5788 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5792 /// DropOperands - Release the operands and set this node to have
5794 void SDNode::DropOperands() {
5795 // Unlike the code in MorphNodeTo that does this, we don't need to
5796 // watch for dead nodes here.
5797 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5803 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5806 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5808 SDVTList VTs = getVTList(VT);
5809 return SelectNodeTo(N, MachineOpc, VTs, None);
5812 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5813 EVT VT, SDValue Op1) {
5814 SDVTList VTs = getVTList(VT);
5815 SDValue Ops[] = { Op1 };
5816 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5819 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5820 EVT VT, SDValue Op1,
5822 SDVTList VTs = getVTList(VT);
5823 SDValue Ops[] = { Op1, Op2 };
5824 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5827 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5828 EVT VT, SDValue Op1,
5829 SDValue Op2, SDValue Op3) {
5830 SDVTList VTs = getVTList(VT);
5831 SDValue Ops[] = { Op1, Op2, Op3 };
5832 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5835 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5836 EVT VT, ArrayRef<SDValue> Ops) {
5837 SDVTList VTs = getVTList(VT);
5838 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5841 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5842 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5843 SDVTList VTs = getVTList(VT1, VT2);
5844 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5847 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5849 SDVTList VTs = getVTList(VT1, VT2);
5850 return SelectNodeTo(N, MachineOpc, VTs, None);
5853 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5854 EVT VT1, EVT VT2, EVT VT3,
5855 ArrayRef<SDValue> Ops) {
5856 SDVTList VTs = getVTList(VT1, VT2, VT3);
5857 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5860 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5861 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5862 ArrayRef<SDValue> Ops) {
5863 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5864 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5867 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5870 SDVTList VTs = getVTList(VT1, VT2);
5871 SDValue Ops[] = { Op1 };
5872 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5875 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5877 SDValue Op1, SDValue Op2) {
5878 SDVTList VTs = getVTList(VT1, VT2);
5879 SDValue Ops[] = { Op1, Op2 };
5880 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5883 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5885 SDValue Op1, SDValue Op2,
5887 SDVTList VTs = getVTList(VT1, VT2);
5888 SDValue Ops[] = { Op1, Op2, Op3 };
5889 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5892 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5893 EVT VT1, EVT VT2, EVT VT3,
5894 SDValue Op1, SDValue Op2,
5896 SDVTList VTs = getVTList(VT1, VT2, VT3);
5897 SDValue Ops[] = { Op1, Op2, Op3 };
5898 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5901 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5902 SDVTList VTs,ArrayRef<SDValue> Ops) {
5903 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5904 // Reset the NodeID to -1.
5909 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5910 /// the line number information on the merged node since it is not possible to
5911 /// preserve the information that operation is associated with multiple lines.
5912 /// This will make the debugger working better at -O0, were there is a higher
5913 /// probability having other instructions associated with that line.
5915 /// For IROrder, we keep the smaller of the two
5916 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5917 DebugLoc NLoc = N->getDebugLoc();
5918 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5919 N->setDebugLoc(DebugLoc());
5921 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5922 N->setIROrder(Order);
5926 /// MorphNodeTo - This *mutates* the specified node to have the specified
5927 /// return type, opcode, and operands.
5929 /// Note that MorphNodeTo returns the resultant node. If there is already a
5930 /// node of the specified opcode and operands, it returns that node instead of
5931 /// the current one. Note that the SDLoc need not be the same.
5933 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5934 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5935 /// node, and because it doesn't require CSE recalculation for any of
5936 /// the node's users.
5938 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5939 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5940 /// the legalizer which maintain worklists that would need to be updated when
5941 /// deleting things.
5942 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5943 SDVTList VTs, ArrayRef<SDValue> Ops) {
5944 unsigned NumOps = Ops.size();
5945 // If an identical node already exists, use it.
5947 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5948 FoldingSetNodeID ID;
5949 AddNodeIDNode(ID, Opc, VTs, Ops);
5950 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5951 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5954 if (!RemoveNodeFromCSEMaps(N))
5957 // Start the morphing.
5959 N->ValueList = VTs.VTs;
5960 N->NumValues = VTs.NumVTs;
5962 // Clear the operands list, updating used nodes to remove this from their
5963 // use list. Keep track of any operands that become dead as a result.
5964 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5965 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5967 SDNode *Used = Use.getNode();
5969 if (Used->use_empty())
5970 DeadNodeSet.insert(Used);
5973 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5974 // Initialize the memory references information.
5975 MN->setMemRefs(nullptr, nullptr);
5976 // If NumOps is larger than the # of operands we can have in a
5977 // MachineSDNode, reallocate the operand list.
5978 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5979 if (MN->OperandsNeedDelete)
5980 delete[] MN->OperandList;
5981 if (NumOps > array_lengthof(MN->LocalOperands))
5982 // We're creating a final node that will live unmorphed for the
5983 // remainder of the current SelectionDAG iteration, so we can allocate
5984 // the operands directly out of a pool with no recycling metadata.
5985 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5986 Ops.data(), NumOps);
5988 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5989 MN->OperandsNeedDelete = false;
5991 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5993 // If NumOps is larger than the # of operands we currently have, reallocate
5994 // the operand list.
5995 if (NumOps > N->NumOperands) {
5996 if (N->OperandsNeedDelete)
5997 delete[] N->OperandList;
5998 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5999 N->OperandsNeedDelete = true;
6001 N->InitOperands(N->OperandList, Ops.data(), NumOps);
6004 // Delete any nodes that are still dead after adding the uses for the
6006 if (!DeadNodeSet.empty()) {
6007 SmallVector<SDNode *, 16> DeadNodes;
6008 for (SDNode *N : DeadNodeSet)
6010 DeadNodes.push_back(N);
6011 RemoveDeadNodes(DeadNodes);
6015 CSEMap.InsertNode(N, IP); // Memoize the new node.
6020 /// getMachineNode - These are used for target selectors to create a new node
6021 /// with specified return type(s), MachineInstr opcode, and operands.
6023 /// Note that getMachineNode returns the resultant node. If there is already a
6024 /// node of the specified opcode and operands, it returns that node instead of
6025 /// the current one.
6027 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
6028 SDVTList VTs = getVTList(VT);
6029 return getMachineNode(Opcode, dl, VTs, None);
6033 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6034 SDVTList VTs = getVTList(VT);
6035 SDValue Ops[] = { Op1 };
6036 return getMachineNode(Opcode, dl, VTs, Ops);
6040 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6041 SDValue Op1, SDValue Op2) {
6042 SDVTList VTs = getVTList(VT);
6043 SDValue Ops[] = { Op1, Op2 };
6044 return getMachineNode(Opcode, dl, VTs, Ops);
6048 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6049 SDValue Op1, SDValue Op2, SDValue Op3) {
6050 SDVTList VTs = getVTList(VT);
6051 SDValue Ops[] = { Op1, Op2, Op3 };
6052 return getMachineNode(Opcode, dl, VTs, Ops);
6056 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6057 ArrayRef<SDValue> Ops) {
6058 SDVTList VTs = getVTList(VT);
6059 return getMachineNode(Opcode, dl, VTs, Ops);
6063 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6064 SDVTList VTs = getVTList(VT1, VT2);
6065 return getMachineNode(Opcode, dl, VTs, None);
6069 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6070 EVT VT1, EVT VT2, SDValue Op1) {
6071 SDVTList VTs = getVTList(VT1, VT2);
6072 SDValue Ops[] = { Op1 };
6073 return getMachineNode(Opcode, dl, VTs, Ops);
6077 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6078 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6079 SDVTList VTs = getVTList(VT1, VT2);
6080 SDValue Ops[] = { Op1, Op2 };
6081 return getMachineNode(Opcode, dl, VTs, Ops);
6085 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6086 EVT VT1, EVT VT2, SDValue Op1,
6087 SDValue Op2, SDValue Op3) {
6088 SDVTList VTs = getVTList(VT1, VT2);
6089 SDValue Ops[] = { Op1, Op2, Op3 };
6090 return getMachineNode(Opcode, dl, VTs, Ops);
6094 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6096 ArrayRef<SDValue> Ops) {
6097 SDVTList VTs = getVTList(VT1, VT2);
6098 return getMachineNode(Opcode, dl, VTs, Ops);
6102 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6103 EVT VT1, EVT VT2, EVT VT3,
6104 SDValue Op1, SDValue Op2) {
6105 SDVTList VTs = getVTList(VT1, VT2, VT3);
6106 SDValue Ops[] = { Op1, Op2 };
6107 return getMachineNode(Opcode, dl, VTs, Ops);
6111 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6112 EVT VT1, EVT VT2, EVT VT3,
6113 SDValue Op1, SDValue Op2, SDValue Op3) {
6114 SDVTList VTs = getVTList(VT1, VT2, VT3);
6115 SDValue Ops[] = { Op1, Op2, Op3 };
6116 return getMachineNode(Opcode, dl, VTs, Ops);
6120 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6121 EVT VT1, EVT VT2, EVT VT3,
6122 ArrayRef<SDValue> Ops) {
6123 SDVTList VTs = getVTList(VT1, VT2, VT3);
6124 return getMachineNode(Opcode, dl, VTs, Ops);
6128 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6129 EVT VT2, EVT VT3, EVT VT4,
6130 ArrayRef<SDValue> Ops) {
6131 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6132 return getMachineNode(Opcode, dl, VTs, Ops);
6136 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6137 ArrayRef<EVT> ResultTys,
6138 ArrayRef<SDValue> Ops) {
6139 SDVTList VTs = getVTList(ResultTys);
6140 return getMachineNode(Opcode, dl, VTs, Ops);
6144 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6145 ArrayRef<SDValue> OpsArray) {
6146 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6149 const SDValue *Ops = OpsArray.data();
6150 unsigned NumOps = OpsArray.size();
6153 FoldingSetNodeID ID;
6154 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6156 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6157 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6161 // Allocate a new MachineSDNode.
6162 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6163 DL.getDebugLoc(), VTs);
6165 // Initialize the operands list.
6166 if (NumOps > array_lengthof(N->LocalOperands))
6167 // We're creating a final node that will live unmorphed for the
6168 // remainder of the current SelectionDAG iteration, so we can allocate
6169 // the operands directly out of a pool with no recycling metadata.
6170 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6173 N->InitOperands(N->LocalOperands, Ops, NumOps);
6174 N->OperandsNeedDelete = false;
6177 CSEMap.InsertNode(N, IP);
6183 /// getTargetExtractSubreg - A convenience function for creating
6184 /// TargetOpcode::EXTRACT_SUBREG nodes.
6186 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6188 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6189 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6190 VT, Operand, SRIdxVal);
6191 return SDValue(Subreg, 0);
6194 /// getTargetInsertSubreg - A convenience function for creating
6195 /// TargetOpcode::INSERT_SUBREG nodes.
6197 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6198 SDValue Operand, SDValue Subreg) {
6199 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6200 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6201 VT, Operand, Subreg, SRIdxVal);
6202 return SDValue(Result, 0);
6205 /// getNodeIfExists - Get the specified node if it's already available, or
6206 /// else return NULL.
6207 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6208 ArrayRef<SDValue> Ops,
6209 const SDNodeFlags *Flags) {
6210 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6211 FoldingSetNodeID ID;
6212 AddNodeIDNode(ID, Opcode, VTList, Ops);
6213 AddNodeIDFlags(ID, Opcode, Flags);
6215 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6221 /// getDbgValue - Creates a SDDbgValue node.
6224 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6225 unsigned R, bool IsIndirect, uint64_t Off,
6226 DebugLoc DL, unsigned O) {
6227 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6228 "Expected inlined-at fields to agree");
6229 return new (DbgInfo->getAlloc())
6230 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6234 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6235 const Value *C, uint64_t Off,
6236 DebugLoc DL, unsigned O) {
6237 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6238 "Expected inlined-at fields to agree");
6239 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6243 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6244 unsigned FI, uint64_t Off,
6245 DebugLoc DL, unsigned O) {
6246 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6247 "Expected inlined-at fields to agree");
6248 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6253 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6254 /// pointed to by a use iterator is deleted, increment the use iterator
6255 /// so that it doesn't dangle.
6257 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6258 SDNode::use_iterator &UI;
6259 SDNode::use_iterator &UE;
6261 void NodeDeleted(SDNode *N, SDNode *E) override {
6262 // Increment the iterator as needed.
6263 while (UI != UE && N == *UI)
6268 RAUWUpdateListener(SelectionDAG &d,
6269 SDNode::use_iterator &ui,
6270 SDNode::use_iterator &ue)
6271 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6276 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6277 /// This can cause recursive merging of nodes in the DAG.
6279 /// This version assumes From has a single result value.
6281 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6282 SDNode *From = FromN.getNode();
6283 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6284 "Cannot replace with this method!");
6285 assert(From != To.getNode() && "Cannot replace uses of with self");
6287 // Iterate over all the existing uses of From. New uses will be added
6288 // to the beginning of the use list, which we avoid visiting.
6289 // This specifically avoids visiting uses of From that arise while the
6290 // replacement is happening, because any such uses would be the result
6291 // of CSE: If an existing node looks like From after one of its operands
6292 // is replaced by To, we don't want to replace of all its users with To
6293 // too. See PR3018 for more info.
6294 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6295 RAUWUpdateListener Listener(*this, UI, UE);
6299 // This node is about to morph, remove its old self from the CSE maps.
6300 RemoveNodeFromCSEMaps(User);
6302 // A user can appear in a use list multiple times, and when this
6303 // happens the uses are usually next to each other in the list.
6304 // To help reduce the number of CSE recomputations, process all
6305 // the uses of this user that we can find this way.
6307 SDUse &Use = UI.getUse();
6310 } while (UI != UE && *UI == User);
6312 // Now that we have modified User, add it back to the CSE maps. If it
6313 // already exists there, recursively merge the results together.
6314 AddModifiedNodeToCSEMaps(User);
6317 // If we just RAUW'd the root, take note.
6318 if (FromN == getRoot())
6322 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6323 /// This can cause recursive merging of nodes in the DAG.
6325 /// This version assumes that for each value of From, there is a
6326 /// corresponding value in To in the same position with the same type.
6328 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6330 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6331 assert((!From->hasAnyUseOfValue(i) ||
6332 From->getValueType(i) == To->getValueType(i)) &&
6333 "Cannot use this version of ReplaceAllUsesWith!");
6336 // Handle the trivial case.
6340 // Iterate over just the existing users of From. See the comments in
6341 // the ReplaceAllUsesWith above.
6342 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6343 RAUWUpdateListener Listener(*this, UI, UE);
6347 // This node is about to morph, remove its old self from the CSE maps.
6348 RemoveNodeFromCSEMaps(User);
6350 // A user can appear in a use list multiple times, and when this
6351 // happens the uses are usually next to each other in the list.
6352 // To help reduce the number of CSE recomputations, process all
6353 // the uses of this user that we can find this way.
6355 SDUse &Use = UI.getUse();
6358 } while (UI != UE && *UI == User);
6360 // Now that we have modified User, add it back to the CSE maps. If it
6361 // already exists there, recursively merge the results together.
6362 AddModifiedNodeToCSEMaps(User);
6365 // If we just RAUW'd the root, take note.
6366 if (From == getRoot().getNode())
6367 setRoot(SDValue(To, getRoot().getResNo()));
6370 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6371 /// This can cause recursive merging of nodes in the DAG.
6373 /// This version can replace From with any result values. To must match the
6374 /// number and types of values returned by From.
6375 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6376 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6377 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6379 // Iterate over just the existing users of From. See the comments in
6380 // the ReplaceAllUsesWith above.
6381 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6382 RAUWUpdateListener Listener(*this, UI, UE);
6386 // This node is about to morph, remove its old self from the CSE maps.
6387 RemoveNodeFromCSEMaps(User);
6389 // A user can appear in a use list multiple times, and when this
6390 // happens the uses are usually next to each other in the list.
6391 // To help reduce the number of CSE recomputations, process all
6392 // the uses of this user that we can find this way.
6394 SDUse &Use = UI.getUse();
6395 const SDValue &ToOp = To[Use.getResNo()];
6398 } while (UI != UE && *UI == User);
6400 // Now that we have modified User, add it back to the CSE maps. If it
6401 // already exists there, recursively merge the results together.
6402 AddModifiedNodeToCSEMaps(User);
6405 // If we just RAUW'd the root, take note.
6406 if (From == getRoot().getNode())
6407 setRoot(SDValue(To[getRoot().getResNo()]));
6410 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6411 /// uses of other values produced by From.getNode() alone. The Deleted
6412 /// vector is handled the same way as for ReplaceAllUsesWith.
6413 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6414 // Handle the really simple, really trivial case efficiently.
6415 if (From == To) return;
6417 // Handle the simple, trivial, case efficiently.
6418 if (From.getNode()->getNumValues() == 1) {
6419 ReplaceAllUsesWith(From, To);
6423 // Iterate over just the existing users of From. See the comments in
6424 // the ReplaceAllUsesWith above.
6425 SDNode::use_iterator UI = From.getNode()->use_begin(),
6426 UE = From.getNode()->use_end();
6427 RAUWUpdateListener Listener(*this, UI, UE);
6430 bool UserRemovedFromCSEMaps = false;
6432 // A user can appear in a use list multiple times, and when this
6433 // happens the uses are usually next to each other in the list.
6434 // To help reduce the number of CSE recomputations, process all
6435 // the uses of this user that we can find this way.
6437 SDUse &Use = UI.getUse();
6439 // Skip uses of different values from the same node.
6440 if (Use.getResNo() != From.getResNo()) {
6445 // If this node hasn't been modified yet, it's still in the CSE maps,
6446 // so remove its old self from the CSE maps.
6447 if (!UserRemovedFromCSEMaps) {
6448 RemoveNodeFromCSEMaps(User);
6449 UserRemovedFromCSEMaps = true;
6454 } while (UI != UE && *UI == User);
6456 // We are iterating over all uses of the From node, so if a use
6457 // doesn't use the specific value, no changes are made.
6458 if (!UserRemovedFromCSEMaps)
6461 // Now that we have modified User, add it back to the CSE maps. If it
6462 // already exists there, recursively merge the results together.
6463 AddModifiedNodeToCSEMaps(User);
6466 // If we just RAUW'd the root, take note.
6467 if (From == getRoot())
6472 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6473 /// to record information about a use.
6480 /// operator< - Sort Memos by User.
6481 bool operator<(const UseMemo &L, const UseMemo &R) {
6482 return (intptr_t)L.User < (intptr_t)R.User;
6486 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6487 /// uses of other values produced by From.getNode() alone. The same value
6488 /// may appear in both the From and To list. The Deleted vector is
6489 /// handled the same way as for ReplaceAllUsesWith.
6490 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6493 // Handle the simple, trivial case efficiently.
6495 return ReplaceAllUsesOfValueWith(*From, *To);
6497 // Read up all the uses and make records of them. This helps
6498 // processing new uses that are introduced during the
6499 // replacement process.
6500 SmallVector<UseMemo, 4> Uses;
6501 for (unsigned i = 0; i != Num; ++i) {
6502 unsigned FromResNo = From[i].getResNo();
6503 SDNode *FromNode = From[i].getNode();
6504 for (SDNode::use_iterator UI = FromNode->use_begin(),
6505 E = FromNode->use_end(); UI != E; ++UI) {
6506 SDUse &Use = UI.getUse();
6507 if (Use.getResNo() == FromResNo) {
6508 UseMemo Memo = { *UI, i, &Use };
6509 Uses.push_back(Memo);
6514 // Sort the uses, so that all the uses from a given User are together.
6515 std::sort(Uses.begin(), Uses.end());
6517 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6518 UseIndex != UseIndexEnd; ) {
6519 // We know that this user uses some value of From. If it is the right
6520 // value, update it.
6521 SDNode *User = Uses[UseIndex].User;
6523 // This node is about to morph, remove its old self from the CSE maps.
6524 RemoveNodeFromCSEMaps(User);
6526 // The Uses array is sorted, so all the uses for a given User
6527 // are next to each other in the list.
6528 // To help reduce the number of CSE recomputations, process all
6529 // the uses of this user that we can find this way.
6531 unsigned i = Uses[UseIndex].Index;
6532 SDUse &Use = *Uses[UseIndex].Use;
6536 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6538 // Now that we have modified User, add it back to the CSE maps. If it
6539 // already exists there, recursively merge the results together.
6540 AddModifiedNodeToCSEMaps(User);
6544 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6545 /// based on their topological order. It returns the maximum id and a vector
6546 /// of the SDNodes* in assigned order by reference.
6547 unsigned SelectionDAG::AssignTopologicalOrder() {
6549 unsigned DAGSize = 0;
6551 // SortedPos tracks the progress of the algorithm. Nodes before it are
6552 // sorted, nodes after it are unsorted. When the algorithm completes
6553 // it is at the end of the list.
6554 allnodes_iterator SortedPos = allnodes_begin();
6556 // Visit all the nodes. Move nodes with no operands to the front of
6557 // the list immediately. Annotate nodes that do have operands with their
6558 // operand count. Before we do this, the Node Id fields of the nodes
6559 // may contain arbitrary values. After, the Node Id fields for nodes
6560 // before SortedPos will contain the topological sort index, and the
6561 // Node Id fields for nodes At SortedPos and after will contain the
6562 // count of outstanding operands.
6563 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6565 checkForCycles(N, this);
6566 unsigned Degree = N->getNumOperands();
6568 // A node with no uses, add it to the result array immediately.
6569 N->setNodeId(DAGSize++);
6570 allnodes_iterator Q(N);
6572 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6573 assert(SortedPos != AllNodes.end() && "Overran node list");
6576 // Temporarily use the Node Id as scratch space for the degree count.
6577 N->setNodeId(Degree);
6581 // Visit all the nodes. As we iterate, move nodes into sorted order,
6582 // such that by the time the end is reached all nodes will be sorted.
6583 for (SDNode &Node : allnodes()) {
6585 checkForCycles(N, this);
6586 // N is in sorted position, so all its uses have one less operand
6587 // that needs to be sorted.
6588 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6591 unsigned Degree = P->getNodeId();
6592 assert(Degree != 0 && "Invalid node degree");
6595 // All of P's operands are sorted, so P may sorted now.
6596 P->setNodeId(DAGSize++);
6598 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6599 assert(SortedPos != AllNodes.end() && "Overran node list");
6602 // Update P's outstanding operand count.
6603 P->setNodeId(Degree);
6606 if (&Node == SortedPos) {
6608 allnodes_iterator I(N);
6610 dbgs() << "Overran sorted position:\n";
6611 S->dumprFull(this); dbgs() << "\n";
6612 dbgs() << "Checking if this is due to cycles\n";
6613 checkForCycles(this, true);
6615 llvm_unreachable(nullptr);
6619 assert(SortedPos == AllNodes.end() &&
6620 "Topological sort incomplete!");
6621 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6622 "First node in topological sort is not the entry token!");
6623 assert(AllNodes.front().getNodeId() == 0 &&
6624 "First node in topological sort has non-zero id!");
6625 assert(AllNodes.front().getNumOperands() == 0 &&
6626 "First node in topological sort has operands!");
6627 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6628 "Last node in topologic sort has unexpected id!");
6629 assert(AllNodes.back().use_empty() &&
6630 "Last node in topologic sort has users!");
6631 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6635 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6636 /// value is produced by SD.
6637 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6639 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6640 SD->setHasDebugValue(true);
6642 DbgInfo->add(DB, SD, isParameter);
6645 /// TransferDbgValues - Transfer SDDbgValues.
6646 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6647 if (From == To || !From.getNode()->getHasDebugValue())
6649 SDNode *FromNode = From.getNode();
6650 SDNode *ToNode = To.getNode();
6651 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6652 SmallVector<SDDbgValue *, 2> ClonedDVs;
6653 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6655 SDDbgValue *Dbg = *I;
6656 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6658 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6659 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6660 Dbg->getDebugLoc(), Dbg->getOrder());
6661 ClonedDVs.push_back(Clone);
6664 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6665 E = ClonedDVs.end(); I != E; ++I)
6666 AddDbgValue(*I, ToNode, false);
6669 //===----------------------------------------------------------------------===//
6671 //===----------------------------------------------------------------------===//
6673 HandleSDNode::~HandleSDNode() {
6677 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6678 DebugLoc DL, const GlobalValue *GA,
6679 EVT VT, int64_t o, unsigned char TF)
6680 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6684 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6685 SDValue X, unsigned SrcAS,
6687 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6688 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6690 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6691 EVT memvt, MachineMemOperand *mmo)
6692 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6693 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6694 MMO->isNonTemporal(), MMO->isInvariant());
6695 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6696 assert(isNonTemporal() == MMO->isNonTemporal() &&
6697 "Non-temporal encoding error!");
6698 // We check here that the size of the memory operand fits within the size of
6699 // the MMO. This is because the MMO might indicate only a possible address
6700 // range instead of specifying the affected memory addresses precisely.
6701 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6704 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6705 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6706 : SDNode(Opc, Order, dl, VTs, Ops),
6707 MemoryVT(memvt), MMO(mmo) {
6708 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6709 MMO->isNonTemporal(), MMO->isInvariant());
6710 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6711 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6714 /// Profile - Gather unique data for the node.
6716 void SDNode::Profile(FoldingSetNodeID &ID) const {
6717 AddNodeIDNode(ID, this);
6722 std::vector<EVT> VTs;
6725 VTs.reserve(MVT::LAST_VALUETYPE);
6726 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6727 VTs.push_back(MVT((MVT::SimpleValueType)i));
6732 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6733 static ManagedStatic<EVTArray> SimpleVTArray;
6734 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6736 /// getValueTypeList - Return a pointer to the specified value type.
6738 const EVT *SDNode::getValueTypeList(EVT VT) {
6739 if (VT.isExtended()) {
6740 sys::SmartScopedLock<true> Lock(*VTMutex);
6741 return &(*EVTs->insert(VT).first);
6743 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6744 "Value type out of range!");
6745 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6749 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6750 /// indicated value. This method ignores uses of other values defined by this
6752 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6753 assert(Value < getNumValues() && "Bad value!");
6755 // TODO: Only iterate over uses of a given value of the node
6756 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6757 if (UI.getUse().getResNo() == Value) {
6764 // Found exactly the right number of uses?
6769 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6770 /// value. This method ignores uses of other values defined by this operation.
6771 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6772 assert(Value < getNumValues() && "Bad value!");
6774 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6775 if (UI.getUse().getResNo() == Value)
6782 /// isOnlyUserOf - Return true if this node is the only use of N.
6784 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6786 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6797 /// isOperand - Return true if this node is an operand of N.
6799 bool SDValue::isOperandOf(const SDNode *N) const {
6800 for (const SDValue &Op : N->op_values())
6806 bool SDNode::isOperandOf(const SDNode *N) const {
6807 for (const SDValue &Op : N->op_values())
6808 if (this == Op.getNode())
6813 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6814 /// be a chain) reaches the specified operand without crossing any
6815 /// side-effecting instructions on any chain path. In practice, this looks
6816 /// through token factors and non-volatile loads. In order to remain efficient,
6817 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6818 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6819 unsigned Depth) const {
6820 if (*this == Dest) return true;
6822 // Don't search too deeply, we just want to be able to see through
6823 // TokenFactor's etc.
6824 if (Depth == 0) return false;
6826 // If this is a token factor, all inputs to the TF happen in parallel. If any
6827 // of the operands of the TF does not reach dest, then we cannot do the xform.
6828 if (getOpcode() == ISD::TokenFactor) {
6829 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6830 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6835 // Loads don't have side effects, look through them.
6836 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6837 if (!Ld->isVolatile())
6838 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6843 /// hasPredecessor - Return true if N is a predecessor of this node.
6844 /// N is either an operand of this node, or can be reached by recursively
6845 /// traversing up the operands.
6846 /// NOTE: This is an expensive method. Use it carefully.
6847 bool SDNode::hasPredecessor(const SDNode *N) const {
6848 SmallPtrSet<const SDNode *, 32> Visited;
6849 SmallVector<const SDNode *, 16> Worklist;
6850 return hasPredecessorHelper(N, Visited, Worklist);
6854 SDNode::hasPredecessorHelper(const SDNode *N,
6855 SmallPtrSetImpl<const SDNode *> &Visited,
6856 SmallVectorImpl<const SDNode *> &Worklist) const {
6857 if (Visited.empty()) {
6858 Worklist.push_back(this);
6860 // Take a look in the visited set. If we've already encountered this node
6861 // we needn't search further.
6862 if (Visited.count(N))
6866 // Haven't visited N yet. Continue the search.
6867 while (!Worklist.empty()) {
6868 const SDNode *M = Worklist.pop_back_val();
6869 for (const SDValue &OpV : M->op_values()) {
6870 SDNode *Op = OpV.getNode();
6871 if (Visited.insert(Op).second)
6872 Worklist.push_back(Op);
6881 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6882 assert(Num < NumOperands && "Invalid child # of SDNode!");
6883 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6886 const SDNodeFlags *SDNode::getFlags() const {
6887 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6888 return &FlagsNode->Flags;
6892 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6893 assert(N->getNumValues() == 1 &&
6894 "Can't unroll a vector with multiple results!");
6896 EVT VT = N->getValueType(0);
6897 unsigned NE = VT.getVectorNumElements();
6898 EVT EltVT = VT.getVectorElementType();
6901 SmallVector<SDValue, 8> Scalars;
6902 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6904 // If ResNE is 0, fully unroll the vector op.
6907 else if (NE > ResNE)
6911 for (i= 0; i != NE; ++i) {
6912 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6913 SDValue Operand = N->getOperand(j);
6914 EVT OperandVT = Operand.getValueType();
6915 if (OperandVT.isVector()) {
6916 // A vector operand; extract a single element.
6917 EVT OperandEltVT = OperandVT.getVectorElementType();
6919 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6920 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6922 // A scalar operand; just use it as is.
6923 Operands[j] = Operand;
6927 switch (N->getOpcode()) {
6929 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6934 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6941 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6942 getShiftAmountOperand(Operands[0].getValueType(),
6945 case ISD::SIGN_EXTEND_INREG:
6946 case ISD::FP_ROUND_INREG: {
6947 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6948 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6950 getValueType(ExtVT)));
6955 for (; i < ResNE; ++i)
6956 Scalars.push_back(getUNDEF(EltVT));
6958 return getNode(ISD::BUILD_VECTOR, dl,
6959 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6963 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6964 /// location that is 'Dist' units away from the location that the 'Base' load
6965 /// is loading from.
6966 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6967 unsigned Bytes, int Dist) const {
6968 if (LD->getChain() != Base->getChain())
6970 EVT VT = LD->getValueType(0);
6971 if (VT.getSizeInBits() / 8 != Bytes)
6974 SDValue Loc = LD->getOperand(1);
6975 SDValue BaseLoc = Base->getOperand(1);
6976 if (Loc.getOpcode() == ISD::FrameIndex) {
6977 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6979 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6980 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6981 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6982 int FS = MFI->getObjectSize(FI);
6983 int BFS = MFI->getObjectSize(BFI);
6984 if (FS != BFS || FS != (int)Bytes) return false;
6985 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6989 if (isBaseWithConstantOffset(Loc)) {
6990 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6991 if (Loc.getOperand(0) == BaseLoc) {
6992 // If the base location is a simple address with no offset itself, then
6993 // the second load's first add operand should be the base address.
6994 if (LocOffset == Dist * (int)Bytes)
6996 } else if (isBaseWithConstantOffset(BaseLoc)) {
6997 // The base location itself has an offset, so subtract that value from the
6998 // second load's offset before comparing to distance * size.
7000 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
7001 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
7002 if ((LocOffset - BOffset) == Dist * (int)Bytes)
7007 const GlobalValue *GV1 = nullptr;
7008 const GlobalValue *GV2 = nullptr;
7009 int64_t Offset1 = 0;
7010 int64_t Offset2 = 0;
7011 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
7012 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
7013 if (isGA1 && isGA2 && GV1 == GV2)
7014 return Offset1 == (Offset2 + Dist*Bytes);
7019 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
7020 /// it cannot be inferred.
7021 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
7022 // If this is a GlobalAddress + cst, return the alignment.
7023 const GlobalValue *GV;
7024 int64_t GVOffset = 0;
7025 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
7026 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
7027 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
7028 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7030 unsigned AlignBits = KnownZero.countTrailingOnes();
7031 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7033 return MinAlign(Align, GVOffset);
7036 // If this is a direct reference to a stack slot, use information about the
7037 // stack slot's alignment.
7038 int FrameIdx = 1 << 31;
7039 int64_t FrameOffset = 0;
7040 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7041 FrameIdx = FI->getIndex();
7042 } else if (isBaseWithConstantOffset(Ptr) &&
7043 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7045 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7046 FrameOffset = Ptr.getConstantOperandVal(1);
7049 if (FrameIdx != (1 << 31)) {
7050 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7051 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7059 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7060 /// which is split (or expanded) into two not necessarily identical pieces.
7061 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7062 // Currently all types are split in half.
7064 if (!VT.isVector()) {
7065 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7067 unsigned NumElements = VT.getVectorNumElements();
7068 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7069 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7072 return std::make_pair(LoVT, HiVT);
7075 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7077 std::pair<SDValue, SDValue>
7078 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7080 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7081 N.getValueType().getVectorNumElements() &&
7082 "More vector elements requested than available!");
7084 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7085 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7086 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7087 getConstant(LoVT.getVectorNumElements(), DL,
7088 TLI->getVectorIdxTy(getDataLayout())));
7089 return std::make_pair(Lo, Hi);
7092 void SelectionDAG::ExtractVectorElements(SDValue Op,
7093 SmallVectorImpl<SDValue> &Args,
7094 unsigned Start, unsigned Count) {
7095 EVT VT = Op.getValueType();
7097 Count = VT.getVectorNumElements();
7099 EVT EltVT = VT.getVectorElementType();
7100 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7102 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7103 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7104 Op, getConstant(i, SL, IdxTy)));
7108 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7109 unsigned GlobalAddressSDNode::getAddressSpace() const {
7110 return getGlobal()->getType()->getAddressSpace();
7114 Type *ConstantPoolSDNode::getType() const {
7115 if (isMachineConstantPoolEntry())
7116 return Val.MachineCPVal->getType();
7117 return Val.ConstVal->getType();
7120 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7122 unsigned &SplatBitSize,
7124 unsigned MinSplatBits,
7125 bool isBigEndian) const {
7126 EVT VT = getValueType(0);
7127 assert(VT.isVector() && "Expected a vector type");
7128 unsigned sz = VT.getSizeInBits();
7129 if (MinSplatBits > sz)
7132 SplatValue = APInt(sz, 0);
7133 SplatUndef = APInt(sz, 0);
7135 // Get the bits. Bits with undefined values (when the corresponding element
7136 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7137 // in SplatValue. If any of the values are not constant, give up and return
7139 unsigned int nOps = getNumOperands();
7140 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7141 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7143 for (unsigned j = 0; j < nOps; ++j) {
7144 unsigned i = isBigEndian ? nOps-1-j : j;
7145 SDValue OpVal = getOperand(i);
7146 unsigned BitPos = j * EltBitSize;
7148 if (OpVal.getOpcode() == ISD::UNDEF)
7149 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7150 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7151 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7152 zextOrTrunc(sz) << BitPos;
7153 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7154 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7159 // The build_vector is all constants or undefs. Find the smallest element
7160 // size that splats the vector.
7162 HasAnyUndefs = (SplatUndef != 0);
7165 unsigned HalfSize = sz / 2;
7166 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7167 APInt LowValue = SplatValue.trunc(HalfSize);
7168 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7169 APInt LowUndef = SplatUndef.trunc(HalfSize);
7171 // If the two halves do not match (ignoring undef bits), stop here.
7172 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7173 MinSplatBits > HalfSize)
7176 SplatValue = HighValue | LowValue;
7177 SplatUndef = HighUndef & LowUndef;
7186 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7187 if (UndefElements) {
7188 UndefElements->clear();
7189 UndefElements->resize(getNumOperands());
7192 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7193 SDValue Op = getOperand(i);
7194 if (Op.getOpcode() == ISD::UNDEF) {
7196 (*UndefElements)[i] = true;
7197 } else if (!Splatted) {
7199 } else if (Splatted != Op) {
7205 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7206 "Can only have a splat without a constant for all undefs.");
7207 return getOperand(0);
7214 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7215 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7219 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7220 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7224 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7225 uint32_t BitWidth) const {
7226 if (ConstantFPSDNode *CN =
7227 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7229 APSInt IntVal(BitWidth);
7230 APFloat APF = CN->getValueAPF();
7231 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7236 return IntVal.exactLogBase2();
7241 bool BuildVectorSDNode::isConstant() const {
7242 for (const SDValue &Op : op_values()) {
7243 unsigned Opc = Op.getOpcode();
7244 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7250 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7251 // Find the first non-undef value in the shuffle mask.
7253 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7256 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7258 // Make sure all remaining elements are either undef or the same as the first
7260 for (int Idx = Mask[i]; i != e; ++i)
7261 if (Mask[i] >= 0 && Mask[i] != Idx)
7267 static void checkForCyclesHelper(const SDNode *N,
7268 SmallPtrSetImpl<const SDNode*> &Visited,
7269 SmallPtrSetImpl<const SDNode*> &Checked,
7270 const llvm::SelectionDAG *DAG) {
7271 // If this node has already been checked, don't check it again.
7272 if (Checked.count(N))
7275 // If a node has already been visited on this depth-first walk, reject it as
7277 if (!Visited.insert(N).second) {
7278 errs() << "Detected cycle in SelectionDAG\n";
7279 dbgs() << "Offending node:\n";
7280 N->dumprFull(DAG); dbgs() << "\n";
7284 for (const SDValue &Op : N->op_values())
7285 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7292 void llvm::checkForCycles(const llvm::SDNode *N,
7293 const llvm::SelectionDAG *DAG,
7301 assert(N && "Checking nonexistent SDNode");
7302 SmallPtrSet<const SDNode*, 32> visited;
7303 SmallPtrSet<const SDNode*, 32> checked;
7304 checkForCyclesHelper(N, visited, checked, DAG);
7309 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7310 checkForCycles(DAG->getRoot().getNode(), DAG, force);