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 if (LD->getExtensionType() == ISD::NON_EXTLOAD)
2288 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero, KnownOne);
2292 case ISD::ZERO_EXTEND: {
2293 EVT InVT = Op.getOperand(0).getValueType();
2294 unsigned InBits = InVT.getScalarType().getSizeInBits();
2295 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2296 KnownZero = KnownZero.trunc(InBits);
2297 KnownOne = KnownOne.trunc(InBits);
2298 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2299 KnownZero = KnownZero.zext(BitWidth);
2300 KnownOne = KnownOne.zext(BitWidth);
2301 KnownZero |= NewBits;
2304 case ISD::SIGN_EXTEND: {
2305 EVT InVT = Op.getOperand(0).getValueType();
2306 unsigned InBits = InVT.getScalarType().getSizeInBits();
2307 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2309 KnownZero = KnownZero.trunc(InBits);
2310 KnownOne = KnownOne.trunc(InBits);
2311 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2313 // Note if the sign bit is known to be zero or one.
2314 bool SignBitKnownZero = KnownZero.isNegative();
2315 bool SignBitKnownOne = KnownOne.isNegative();
2317 KnownZero = KnownZero.zext(BitWidth);
2318 KnownOne = KnownOne.zext(BitWidth);
2320 // If the sign bit is known zero or one, the top bits match.
2321 if (SignBitKnownZero)
2322 KnownZero |= NewBits;
2323 else if (SignBitKnownOne)
2324 KnownOne |= NewBits;
2327 case ISD::ANY_EXTEND: {
2328 EVT InVT = Op.getOperand(0).getValueType();
2329 unsigned InBits = InVT.getScalarType().getSizeInBits();
2330 KnownZero = KnownZero.trunc(InBits);
2331 KnownOne = KnownOne.trunc(InBits);
2332 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2333 KnownZero = KnownZero.zext(BitWidth);
2334 KnownOne = KnownOne.zext(BitWidth);
2337 case ISD::TRUNCATE: {
2338 EVT InVT = Op.getOperand(0).getValueType();
2339 unsigned InBits = InVT.getScalarType().getSizeInBits();
2340 KnownZero = KnownZero.zext(InBits);
2341 KnownOne = KnownOne.zext(InBits);
2342 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2343 KnownZero = KnownZero.trunc(BitWidth);
2344 KnownOne = KnownOne.trunc(BitWidth);
2347 case ISD::AssertZext: {
2348 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2349 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2350 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2351 KnownZero |= (~InMask);
2352 KnownOne &= (~KnownZero);
2356 // All bits are zero except the low bit.
2357 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2361 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2362 // We know that the top bits of C-X are clear if X contains less bits
2363 // than C (i.e. no wrap-around can happen). For example, 20-X is
2364 // positive if we can prove that X is >= 0 and < 16.
2365 if (CLHS->getAPIntValue().isNonNegative()) {
2366 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2367 // NLZ can't be BitWidth with no sign bit
2368 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2369 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2371 // If all of the MaskV bits are known to be zero, then we know the
2372 // output top bits are zero, because we now know that the output is
2374 if ((KnownZero2 & MaskV) == MaskV) {
2375 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2376 // Top bits known zero.
2377 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2385 // Output known-0 bits are known if clear or set in both the low clear bits
2386 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2387 // low 3 bits clear.
2388 // Output known-0 bits are also known if the top bits of each input are
2389 // known to be clear. For example, if one input has the top 10 bits clear
2390 // and the other has the top 8 bits clear, we know the top 7 bits of the
2391 // output must be clear.
2392 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2393 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2394 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2396 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2397 KnownZeroHigh = std::min(KnownZeroHigh,
2398 KnownZero2.countLeadingOnes());
2399 KnownZeroLow = std::min(KnownZeroLow,
2400 KnownZero2.countTrailingOnes());
2402 if (Op.getOpcode() == ISD::ADD) {
2403 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2404 if (KnownZeroHigh > 1)
2405 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2409 // With ADDE, a carry bit may be added in, so we can only use this
2410 // information if we know (at least) that the low two bits are clear. We
2411 // then return to the caller that the low bit is unknown but that other bits
2413 if (KnownZeroLow >= 2) // ADDE
2414 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2418 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2419 const APInt &RA = Rem->getAPIntValue().abs();
2420 if (RA.isPowerOf2()) {
2421 APInt LowBits = RA - 1;
2422 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2424 // The low bits of the first operand are unchanged by the srem.
2425 KnownZero = KnownZero2 & LowBits;
2426 KnownOne = KnownOne2 & LowBits;
2428 // If the first operand is non-negative or has all low bits zero, then
2429 // the upper bits are all zero.
2430 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2431 KnownZero |= ~LowBits;
2433 // If the first operand is negative and not all low bits are zero, then
2434 // the upper bits are all one.
2435 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2436 KnownOne |= ~LowBits;
2437 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2442 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2443 const APInt &RA = Rem->getAPIntValue();
2444 if (RA.isPowerOf2()) {
2445 APInt LowBits = (RA - 1);
2446 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2448 // The upper bits are all zero, the lower ones are unchanged.
2449 KnownZero = KnownZero2 | ~LowBits;
2450 KnownOne = KnownOne2 & LowBits;
2455 // Since the result is less than or equal to either operand, any leading
2456 // zero bits in either operand must also exist in the result.
2457 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2458 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2460 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2461 KnownZero2.countLeadingOnes());
2462 KnownOne.clearAllBits();
2463 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2466 case ISD::EXTRACT_ELEMENT: {
2467 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2468 const unsigned Index =
2469 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2470 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2472 // Remove low part of known bits mask
2473 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2474 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2476 // Remove high part of known bit mask
2477 KnownZero = KnownZero.trunc(BitWidth);
2478 KnownOne = KnownOne.trunc(BitWidth);
2485 APInt Op0Zero, Op0One;
2486 APInt Op1Zero, Op1One;
2487 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2488 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2490 KnownZero = Op0Zero & Op1Zero;
2491 KnownOne = Op0One & Op1One;
2494 case ISD::FrameIndex:
2495 case ISD::TargetFrameIndex:
2496 if (unsigned Align = InferPtrAlignment(Op)) {
2497 // The low bits are known zero if the pointer is aligned.
2498 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2504 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2507 case ISD::INTRINSIC_WO_CHAIN:
2508 case ISD::INTRINSIC_W_CHAIN:
2509 case ISD::INTRINSIC_VOID:
2510 // Allow the target to implement this method for its nodes.
2511 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2515 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2518 /// ComputeNumSignBits - Return the number of times the sign bit of the
2519 /// register is replicated into the other bits. We know that at least 1 bit
2520 /// is always equal to the sign bit (itself), but other cases can give us
2521 /// information. For example, immediately after an "SRA X, 2", we know that
2522 /// the top 3 bits are all equal to each other, so we return 3.
2523 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2524 EVT VT = Op.getValueType();
2525 assert(VT.isInteger() && "Invalid VT!");
2526 unsigned VTBits = VT.getScalarType().getSizeInBits();
2528 unsigned FirstAnswer = 1;
2531 return 1; // Limit search depth.
2533 switch (Op.getOpcode()) {
2535 case ISD::AssertSext:
2536 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2537 return VTBits-Tmp+1;
2538 case ISD::AssertZext:
2539 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2542 case ISD::Constant: {
2543 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2544 return Val.getNumSignBits();
2547 case ISD::SIGN_EXTEND:
2549 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2550 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2552 case ISD::SIGN_EXTEND_INREG:
2553 // Max of the input and what this extends.
2555 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2558 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2559 return std::max(Tmp, Tmp2);
2562 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2563 // SRA X, C -> adds C sign bits.
2564 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2565 Tmp += C->getZExtValue();
2566 if (Tmp > VTBits) Tmp = VTBits;
2570 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2571 // shl destroys sign bits.
2572 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2573 if (C->getZExtValue() >= VTBits || // Bad shift.
2574 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2575 return Tmp - C->getZExtValue();
2580 case ISD::XOR: // NOT is handled here.
2581 // Logical binary ops preserve the number of sign bits at the worst.
2582 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2584 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2585 FirstAnswer = std::min(Tmp, Tmp2);
2586 // We computed what we know about the sign bits as our first
2587 // answer. Now proceed to the generic code that uses
2588 // computeKnownBits, and pick whichever answer is better.
2593 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2594 if (Tmp == 1) return 1; // Early out.
2595 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2596 return std::min(Tmp, Tmp2);
2597 case ISD::SELECT_CC:
2598 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2599 if (Tmp == 1) return 1; // Early out.
2600 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2601 return std::min(Tmp, Tmp2);
2606 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2608 return 1; // Early out.
2609 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2610 return std::min(Tmp, Tmp2);
2617 if (Op.getResNo() != 1)
2619 // The boolean result conforms to getBooleanContents. Fall through.
2620 // If setcc returns 0/-1, all bits are sign bits.
2621 // We know that we have an integer-based boolean since these operations
2622 // are only available for integer.
2623 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2624 TargetLowering::ZeroOrNegativeOneBooleanContent)
2628 // If setcc returns 0/-1, all bits are sign bits.
2629 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2630 TargetLowering::ZeroOrNegativeOneBooleanContent)
2635 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2636 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2638 // Handle rotate right by N like a rotate left by 32-N.
2639 if (Op.getOpcode() == ISD::ROTR)
2640 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2642 // If we aren't rotating out all of the known-in sign bits, return the
2643 // number that are left. This handles rotl(sext(x), 1) for example.
2644 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2645 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2649 // Add can have at most one carry bit. Thus we know that the output
2650 // is, at worst, one more bit than the inputs.
2651 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2652 if (Tmp == 1) return 1; // Early out.
2654 // Special case decrementing a value (ADD X, -1):
2655 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2656 if (CRHS->isAllOnesValue()) {
2657 APInt KnownZero, KnownOne;
2658 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2660 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2662 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2665 // If we are subtracting one from a positive number, there is no carry
2666 // out of the result.
2667 if (KnownZero.isNegative())
2671 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2672 if (Tmp2 == 1) return 1;
2673 return std::min(Tmp, Tmp2)-1;
2676 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2677 if (Tmp2 == 1) return 1;
2680 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2681 if (CLHS->isNullValue()) {
2682 APInt KnownZero, KnownOne;
2683 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2684 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2686 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2689 // If the input is known to be positive (the sign bit is known clear),
2690 // the output of the NEG has the same number of sign bits as the input.
2691 if (KnownZero.isNegative())
2694 // Otherwise, we treat this like a SUB.
2697 // Sub can have at most one carry bit. Thus we know that the output
2698 // is, at worst, one more bit than the inputs.
2699 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2700 if (Tmp == 1) return 1; // Early out.
2701 return std::min(Tmp, Tmp2)-1;
2703 // FIXME: it's tricky to do anything useful for this, but it is an important
2704 // case for targets like X86.
2706 case ISD::EXTRACT_ELEMENT: {
2707 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2708 const int BitWidth = Op.getValueType().getSizeInBits();
2710 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2712 // Get reverse index (starting from 1), Op1 value indexes elements from
2713 // little end. Sign starts at big end.
2714 const int rIndex = Items - 1 -
2715 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2717 // If the sign portion ends in our element the subtraction gives correct
2718 // result. Otherwise it gives either negative or > bitwidth result
2719 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2723 // If we are looking at the loaded value of the SDNode.
2724 if (Op.getResNo() == 0) {
2725 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2726 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2727 unsigned ExtType = LD->getExtensionType();
2730 case ISD::SEXTLOAD: // '17' bits known
2731 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2732 return VTBits-Tmp+1;
2733 case ISD::ZEXTLOAD: // '16' bits known
2734 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2740 // Allow the target to implement this method for its nodes.
2741 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2742 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2743 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2744 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2745 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2746 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2749 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2750 // use this information.
2751 APInt KnownZero, KnownOne;
2752 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2755 if (KnownZero.isNegative()) { // sign bit is 0
2757 } else if (KnownOne.isNegative()) { // sign bit is 1;
2764 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2765 // the number of identical bits in the top of the input value.
2767 Mask <<= Mask.getBitWidth()-VTBits;
2768 // Return # leading zeros. We use 'min' here in case Val was zero before
2769 // shifting. We don't want to return '64' as for an i32 "0".
2770 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2773 /// isBaseWithConstantOffset - Return true if the specified operand is an
2774 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2775 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2776 /// semantics as an ADD. This handles the equivalence:
2777 /// X|Cst == X+Cst iff X&Cst = 0.
2778 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2779 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2780 !isa<ConstantSDNode>(Op.getOperand(1)))
2783 if (Op.getOpcode() == ISD::OR &&
2784 !MaskedValueIsZero(Op.getOperand(0),
2785 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2792 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2793 // If we're told that NaNs won't happen, assume they won't.
2794 if (getTarget().Options.NoNaNsFPMath)
2797 // If the value is a constant, we can obviously see if it is a NaN or not.
2798 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2799 return !C->getValueAPF().isNaN();
2801 // TODO: Recognize more cases here.
2806 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2807 // If the value is a constant, we can obviously see if it is a zero or not.
2808 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2809 return !C->isZero();
2811 // TODO: Recognize more cases here.
2812 switch (Op.getOpcode()) {
2815 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2816 return !C->isNullValue();
2823 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2824 // Check the obvious case.
2825 if (A == B) return true;
2827 // For for negative and positive zero.
2828 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2829 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2830 if (CA->isZero() && CB->isZero()) return true;
2832 // Otherwise they may not be equal.
2836 /// getNode - Gets or creates the specified node.
2838 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2839 FoldingSetNodeID ID;
2840 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2842 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2843 return SDValue(E, 0);
2845 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2846 DL.getDebugLoc(), getVTList(VT));
2847 CSEMap.InsertNode(N, IP);
2850 return SDValue(N, 0);
2853 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2854 EVT VT, SDValue Operand) {
2855 // Constant fold unary operations with an integer constant operand. Even
2856 // opaque constant will be folded, because the folding of unary operations
2857 // doesn't create new constants with different values. Nevertheless, the
2858 // opaque flag is preserved during folding to prevent future folding with
2860 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2861 const APInt &Val = C->getAPIntValue();
2864 case ISD::SIGN_EXTEND:
2865 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2866 C->isTargetOpcode(), C->isOpaque());
2867 case ISD::ANY_EXTEND:
2868 case ISD::ZERO_EXTEND:
2870 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2871 C->isTargetOpcode(), C->isOpaque());
2872 case ISD::UINT_TO_FP:
2873 case ISD::SINT_TO_FP: {
2874 APFloat apf(EVTToAPFloatSemantics(VT),
2875 APInt::getNullValue(VT.getSizeInBits()));
2876 (void)apf.convertFromAPInt(Val,
2877 Opcode==ISD::SINT_TO_FP,
2878 APFloat::rmNearestTiesToEven);
2879 return getConstantFP(apf, DL, VT);
2882 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2883 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2884 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2885 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2886 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2887 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2890 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2893 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2896 case ISD::CTLZ_ZERO_UNDEF:
2897 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2900 case ISD::CTTZ_ZERO_UNDEF:
2901 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2906 // Constant fold unary operations with a floating point constant operand.
2907 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2908 APFloat V = C->getValueAPF(); // make copy
2912 return getConstantFP(V, DL, VT);
2915 return getConstantFP(V, DL, VT);
2917 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2918 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2919 return getConstantFP(V, DL, VT);
2923 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2924 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2925 return getConstantFP(V, DL, VT);
2929 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2930 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2931 return getConstantFP(V, DL, VT);
2934 case ISD::FP_EXTEND: {
2936 // This can return overflow, underflow, or inexact; we don't care.
2937 // FIXME need to be more flexible about rounding mode.
2938 (void)V.convert(EVTToAPFloatSemantics(VT),
2939 APFloat::rmNearestTiesToEven, &ignored);
2940 return getConstantFP(V, DL, VT);
2942 case ISD::FP_TO_SINT:
2943 case ISD::FP_TO_UINT: {
2946 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2947 // FIXME need to be more flexible about rounding mode.
2948 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2949 Opcode==ISD::FP_TO_SINT,
2950 APFloat::rmTowardZero, &ignored);
2951 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2953 APInt api(VT.getSizeInBits(), x);
2954 return getConstant(api, DL, VT);
2957 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2958 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2959 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2960 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2961 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2962 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2967 // Constant fold unary operations with a vector integer or float operand.
2968 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2969 if (BV->isConstant()) {
2972 // FIXME: Entirely reasonable to perform folding of other unary
2973 // operations here as the need arises.
2980 case ISD::FP_EXTEND:
2981 case ISD::FP_TO_SINT:
2982 case ISD::FP_TO_UINT:
2984 case ISD::UINT_TO_FP:
2985 case ISD::SINT_TO_FP:
2988 case ISD::CTLZ_ZERO_UNDEF:
2990 case ISD::CTTZ_ZERO_UNDEF:
2992 SDValue Ops = { Operand };
2993 if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
3000 unsigned OpOpcode = Operand.getNode()->getOpcode();
3002 case ISD::TokenFactor:
3003 case ISD::MERGE_VALUES:
3004 case ISD::CONCAT_VECTORS:
3005 return Operand; // Factor, merge or concat of one node? No need.
3006 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3007 case ISD::FP_EXTEND:
3008 assert(VT.isFloatingPoint() &&
3009 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3010 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3011 assert((!VT.isVector() ||
3012 VT.getVectorNumElements() ==
3013 Operand.getValueType().getVectorNumElements()) &&
3014 "Vector element count mismatch!");
3015 assert(Operand.getValueType().bitsLT(VT) &&
3016 "Invalid fpext node, dst < src!");
3017 if (Operand.getOpcode() == ISD::UNDEF)
3018 return getUNDEF(VT);
3020 case ISD::SIGN_EXTEND:
3021 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3022 "Invalid SIGN_EXTEND!");
3023 if (Operand.getValueType() == VT) return Operand; // noop extension
3024 assert((!VT.isVector() ||
3025 VT.getVectorNumElements() ==
3026 Operand.getValueType().getVectorNumElements()) &&
3027 "Vector element count mismatch!");
3028 assert(Operand.getValueType().bitsLT(VT) &&
3029 "Invalid sext node, dst < src!");
3030 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3031 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3032 else if (OpOpcode == ISD::UNDEF)
3033 // sext(undef) = 0, because the top bits will all be the same.
3034 return getConstant(0, DL, VT);
3036 case ISD::ZERO_EXTEND:
3037 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3038 "Invalid ZERO_EXTEND!");
3039 if (Operand.getValueType() == VT) return Operand; // noop extension
3040 assert((!VT.isVector() ||
3041 VT.getVectorNumElements() ==
3042 Operand.getValueType().getVectorNumElements()) &&
3043 "Vector element count mismatch!");
3044 assert(Operand.getValueType().bitsLT(VT) &&
3045 "Invalid zext node, dst < src!");
3046 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3047 return getNode(ISD::ZERO_EXTEND, DL, VT,
3048 Operand.getNode()->getOperand(0));
3049 else if (OpOpcode == ISD::UNDEF)
3050 // zext(undef) = 0, because the top bits will be zero.
3051 return getConstant(0, DL, VT);
3053 case ISD::ANY_EXTEND:
3054 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3055 "Invalid ANY_EXTEND!");
3056 if (Operand.getValueType() == VT) return Operand; // noop extension
3057 assert((!VT.isVector() ||
3058 VT.getVectorNumElements() ==
3059 Operand.getValueType().getVectorNumElements()) &&
3060 "Vector element count mismatch!");
3061 assert(Operand.getValueType().bitsLT(VT) &&
3062 "Invalid anyext node, dst < src!");
3064 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3065 OpOpcode == ISD::ANY_EXTEND)
3066 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3067 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3068 else if (OpOpcode == ISD::UNDEF)
3069 return getUNDEF(VT);
3071 // (ext (trunx x)) -> x
3072 if (OpOpcode == ISD::TRUNCATE) {
3073 SDValue OpOp = Operand.getNode()->getOperand(0);
3074 if (OpOp.getValueType() == VT)
3079 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3080 "Invalid TRUNCATE!");
3081 if (Operand.getValueType() == VT) return Operand; // noop truncate
3082 assert((!VT.isVector() ||
3083 VT.getVectorNumElements() ==
3084 Operand.getValueType().getVectorNumElements()) &&
3085 "Vector element count mismatch!");
3086 assert(Operand.getValueType().bitsGT(VT) &&
3087 "Invalid truncate node, src < dst!");
3088 if (OpOpcode == ISD::TRUNCATE)
3089 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3090 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3091 OpOpcode == ISD::ANY_EXTEND) {
3092 // If the source is smaller than the dest, we still need an extend.
3093 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3094 .bitsLT(VT.getScalarType()))
3095 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3096 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3097 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3098 return Operand.getNode()->getOperand(0);
3100 if (OpOpcode == ISD::UNDEF)
3101 return getUNDEF(VT);
3104 assert(VT.isInteger() && VT == Operand.getValueType() &&
3106 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3107 "BSWAP types must be a multiple of 16 bits!");
3108 if (OpOpcode == ISD::UNDEF)
3109 return getUNDEF(VT);
3112 // Basic sanity checking.
3113 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3114 && "Cannot BITCAST between types of different sizes!");
3115 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3116 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3117 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3118 if (OpOpcode == ISD::UNDEF)
3119 return getUNDEF(VT);
3121 case ISD::SCALAR_TO_VECTOR:
3122 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3123 (VT.getVectorElementType() == Operand.getValueType() ||
3124 (VT.getVectorElementType().isInteger() &&
3125 Operand.getValueType().isInteger() &&
3126 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3127 "Illegal SCALAR_TO_VECTOR node!");
3128 if (OpOpcode == ISD::UNDEF)
3129 return getUNDEF(VT);
3130 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3131 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3132 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3133 Operand.getConstantOperandVal(1) == 0 &&
3134 Operand.getOperand(0).getValueType() == VT)
3135 return Operand.getOperand(0);
3138 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3139 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3140 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3141 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3142 Operand.getNode()->getOperand(0),
3143 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3144 if (OpOpcode == ISD::FNEG) // --X -> X
3145 return Operand.getNode()->getOperand(0);
3148 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3149 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3154 SDVTList VTs = getVTList(VT);
3155 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3156 FoldingSetNodeID ID;
3157 SDValue Ops[1] = { Operand };
3158 AddNodeIDNode(ID, Opcode, VTs, Ops);
3160 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3161 return SDValue(E, 0);
3163 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3164 DL.getDebugLoc(), VTs, Operand);
3165 CSEMap.InsertNode(N, IP);
3167 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3168 DL.getDebugLoc(), VTs, Operand);
3172 return SDValue(N, 0);
3175 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3178 case ISD::ADD: return std::make_pair(C1 + C2, true);
3179 case ISD::SUB: return std::make_pair(C1 - C2, true);
3180 case ISD::MUL: return std::make_pair(C1 * C2, true);
3181 case ISD::AND: return std::make_pair(C1 & C2, true);
3182 case ISD::OR: return std::make_pair(C1 | C2, true);
3183 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3184 case ISD::SHL: return std::make_pair(C1 << C2, true);
3185 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3186 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3187 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3188 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3189 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3190 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3191 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3192 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3194 if (!C2.getBoolValue())
3196 return std::make_pair(C1.udiv(C2), true);
3198 if (!C2.getBoolValue())
3200 return std::make_pair(C1.urem(C2), true);
3202 if (!C2.getBoolValue())
3204 return std::make_pair(C1.sdiv(C2), true);
3206 if (!C2.getBoolValue())
3208 return std::make_pair(C1.srem(C2), true);
3210 return std::make_pair(APInt(1, 0), false);
3213 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3214 const ConstantSDNode *Cst1,
3215 const ConstantSDNode *Cst2) {
3216 if (Cst1->isOpaque() || Cst2->isOpaque())
3219 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3220 Cst2->getAPIntValue());
3223 return getConstant(Folded.first, DL, VT);
3226 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3227 SDNode *Cst1, SDNode *Cst2) {
3228 // If the opcode is a target-specific ISD node, there's nothing we can
3229 // do here and the operand rules may not line up with the below, so
3231 if (Opcode >= ISD::BUILTIN_OP_END)
3234 // Handle the case of two scalars.
3235 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3236 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3237 if (SDValue Folded =
3238 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3241 SmallVector<SDValue, 4> Outputs;
3242 // We may have a vector type but a scalar result. Create a splat.
3243 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3244 // Build a big vector out of the scalar elements we generated.
3245 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3252 // For vectors extract each constant element into Inputs so we can constant
3253 // fold them individually.
3254 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3255 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3259 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3261 EVT SVT = VT.getScalarType();
3262 SmallVector<SDValue, 4> Outputs;
3263 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3264 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3265 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3266 if (!V1 || !V2) // Not a constant, bail.
3269 if (V1->isOpaque() || V2->isOpaque())
3272 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3273 // FIXME: This is valid and could be handled by truncating the APInts.
3274 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3277 // Fold one vector element.
3278 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3279 V2->getAPIntValue());
3282 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3285 assert(VT.getVectorNumElements() == Outputs.size() &&
3286 "Vector size mismatch!");
3288 // We may have a vector type but a scalar result. Create a splat.
3289 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3291 // Build a big vector out of the scalar elements we generated.
3292 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3295 SDValue SelectionDAG::FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
3297 ArrayRef<SDValue> Ops,
3298 const SDNodeFlags *Flags) {
3299 // If the opcode is a target-specific ISD node, there's nothing we can
3300 // do here and the operand rules may not line up with the below, so
3302 if (Opcode >= ISD::BUILTIN_OP_END)
3305 // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
3309 unsigned NumElts = VT.getVectorNumElements();
3311 auto IsSameVectorSize = [&](const SDValue &Op) {
3312 return Op.getValueType().isVector() &&
3313 Op.getValueType().getVectorNumElements() == NumElts;
3316 auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
3317 BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Op);
3318 return (Op.getOpcode() == ISD::UNDEF) || (BV && BV->isConstant());
3321 // All operands must be vector types with the same number of elements as
3322 // the result type and must be either UNDEF or a build vector of constant
3323 // or UNDEF scalars.
3324 if (!std::all_of(Ops.begin(), Ops.end(), IsConstantBuildVectorOrUndef) ||
3325 !std::all_of(Ops.begin(), Ops.end(), IsSameVectorSize))
3328 // Find legal integer scalar type for constant promotion and
3329 // ensure that its scalar size is at least as large as source.
3330 EVT SVT = VT.getScalarType();
3332 if (SVT.isInteger()) {
3333 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3334 if (LegalSVT.bitsLT(SVT))
3338 // Constant fold each scalar lane separately.
3339 SmallVector<SDValue, 4> ScalarResults;
3340 for (unsigned i = 0; i != NumElts; i++) {
3341 SmallVector<SDValue, 4> ScalarOps;
3342 for (SDValue Op : Ops) {
3343 EVT InSVT = Op.getValueType().getScalarType();
3344 BuildVectorSDNode *InBV = dyn_cast<BuildVectorSDNode>(Op);
3346 // We've checked that this is UNDEF above.
3347 ScalarOps.push_back(getUNDEF(InSVT));
3351 SDValue ScalarOp = InBV->getOperand(i);
3352 EVT ScalarVT = ScalarOp.getValueType();
3354 // Build vector (integer) scalar operands may need implicit
3355 // truncation - do this before constant folding.
3356 if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
3357 ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
3359 ScalarOps.push_back(ScalarOp);
3362 // Constant fold the scalar operands.
3363 SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
3365 // Legalize the (integer) scalar constant if necessary.
3366 if (LegalSVT != SVT)
3367 ScalarResult = getNode(ISD::ANY_EXTEND, DL, LegalSVT, ScalarResult);
3369 // Scalar folding only succeeded if the result is a constant or UNDEF.
3370 if (ScalarResult.getOpcode() != ISD::UNDEF &&
3371 ScalarResult.getOpcode() != ISD::Constant &&
3372 ScalarResult.getOpcode() != ISD::ConstantFP)
3374 ScalarResults.push_back(ScalarResult);
3377 assert(ScalarResults.size() == NumElts &&
3378 "Unexpected number of scalar results for BUILD_VECTOR");
3379 return getNode(ISD::BUILD_VECTOR, DL, VT, ScalarResults);
3382 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3383 SDValue N2, const SDNodeFlags *Flags) {
3384 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3385 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3386 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3387 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3389 // Canonicalize constant to RHS if commutative.
3390 if (isCommutativeBinOp(Opcode)) {
3392 std::swap(N1C, N2C);
3394 } else if (N1CFP && !N2CFP) {
3395 std::swap(N1CFP, N2CFP);
3402 case ISD::TokenFactor:
3403 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3404 N2.getValueType() == MVT::Other && "Invalid token factor!");
3405 // Fold trivial token factors.
3406 if (N1.getOpcode() == ISD::EntryToken) return N2;
3407 if (N2.getOpcode() == ISD::EntryToken) return N1;
3408 if (N1 == N2) return N1;
3410 case ISD::CONCAT_VECTORS:
3411 // Concat of UNDEFs is UNDEF.
3412 if (N1.getOpcode() == ISD::UNDEF &&
3413 N2.getOpcode() == ISD::UNDEF)
3414 return getUNDEF(VT);
3416 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3417 // one big BUILD_VECTOR.
3418 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3419 N2.getOpcode() == ISD::BUILD_VECTOR) {
3420 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3421 N1.getNode()->op_end());
3422 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3424 // BUILD_VECTOR requires all inputs to be of the same type, find the
3425 // maximum type and extend them all.
3426 EVT SVT = VT.getScalarType();
3427 for (SDValue Op : Elts)
3428 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3429 if (SVT.bitsGT(VT.getScalarType()))
3430 for (SDValue &Op : Elts)
3431 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3432 ? getZExtOrTrunc(Op, DL, SVT)
3433 : getSExtOrTrunc(Op, DL, SVT);
3435 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3439 assert(VT.isInteger() && "This operator does not apply to FP types!");
3440 assert(N1.getValueType() == N2.getValueType() &&
3441 N1.getValueType() == VT && "Binary operator types must match!");
3442 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3443 // worth handling here.
3444 if (N2C && N2C->isNullValue())
3446 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3453 assert(VT.isInteger() && "This operator does not apply to FP types!");
3454 assert(N1.getValueType() == N2.getValueType() &&
3455 N1.getValueType() == VT && "Binary operator types must match!");
3456 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3457 // it's worth handling here.
3458 if (N2C && N2C->isNullValue())
3472 assert(VT.isInteger() && "This operator does not apply to FP types!");
3473 assert(N1.getValueType() == N2.getValueType() &&
3474 N1.getValueType() == VT && "Binary operator types must match!");
3481 if (getTarget().Options.UnsafeFPMath) {
3482 if (Opcode == ISD::FADD) {
3484 if (N2CFP && N2CFP->getValueAPF().isZero())
3486 } else if (Opcode == ISD::FSUB) {
3488 if (N2CFP && N2CFP->getValueAPF().isZero())
3490 } else if (Opcode == ISD::FMUL) {
3492 if (N2CFP && N2CFP->isZero())
3495 if (N2CFP && N2CFP->isExactlyValue(1.0))
3499 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3500 assert(N1.getValueType() == N2.getValueType() &&
3501 N1.getValueType() == VT && "Binary operator types must match!");
3503 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3504 assert(N1.getValueType() == VT &&
3505 N1.getValueType().isFloatingPoint() &&
3506 N2.getValueType().isFloatingPoint() &&
3507 "Invalid FCOPYSIGN!");
3514 assert(VT == N1.getValueType() &&
3515 "Shift operators return type must be the same as their first arg");
3516 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3517 "Shifts only work on integers");
3518 assert((!VT.isVector() || VT == N2.getValueType()) &&
3519 "Vector shift amounts must be in the same as their first arg");
3520 // Verify that the shift amount VT is bit enough to hold valid shift
3521 // amounts. This catches things like trying to shift an i1024 value by an
3522 // i8, which is easy to fall into in generic code that uses
3523 // TLI.getShiftAmount().
3524 assert(N2.getValueType().getSizeInBits() >=
3525 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3526 "Invalid use of small shift amount with oversized value!");
3528 // Always fold shifts of i1 values so the code generator doesn't need to
3529 // handle them. Since we know the size of the shift has to be less than the
3530 // size of the value, the shift/rotate count is guaranteed to be zero.
3533 if (N2C && N2C->isNullValue())
3536 case ISD::FP_ROUND_INREG: {
3537 EVT EVT = cast<VTSDNode>(N2)->getVT();
3538 assert(VT == N1.getValueType() && "Not an inreg round!");
3539 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3540 "Cannot FP_ROUND_INREG integer types");
3541 assert(EVT.isVector() == VT.isVector() &&
3542 "FP_ROUND_INREG type should be vector iff the operand "
3544 assert((!EVT.isVector() ||
3545 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3546 "Vector element counts must match in FP_ROUND_INREG");
3547 assert(EVT.bitsLE(VT) && "Not rounding down!");
3549 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3553 assert(VT.isFloatingPoint() &&
3554 N1.getValueType().isFloatingPoint() &&
3555 VT.bitsLE(N1.getValueType()) &&
3556 N2C && "Invalid FP_ROUND!");
3557 if (N1.getValueType() == VT) return N1; // noop conversion.
3559 case ISD::AssertSext:
3560 case ISD::AssertZext: {
3561 EVT EVT = cast<VTSDNode>(N2)->getVT();
3562 assert(VT == N1.getValueType() && "Not an inreg extend!");
3563 assert(VT.isInteger() && EVT.isInteger() &&
3564 "Cannot *_EXTEND_INREG FP types");
3565 assert(!EVT.isVector() &&
3566 "AssertSExt/AssertZExt type should be the vector element type "
3567 "rather than the vector type!");
3568 assert(EVT.bitsLE(VT) && "Not extending!");
3569 if (VT == EVT) return N1; // noop assertion.
3572 case ISD::SIGN_EXTEND_INREG: {
3573 EVT EVT = cast<VTSDNode>(N2)->getVT();
3574 assert(VT == N1.getValueType() && "Not an inreg extend!");
3575 assert(VT.isInteger() && EVT.isInteger() &&
3576 "Cannot *_EXTEND_INREG FP types");
3577 assert(EVT.isVector() == VT.isVector() &&
3578 "SIGN_EXTEND_INREG type should be vector iff the operand "
3580 assert((!EVT.isVector() ||
3581 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3582 "Vector element counts must match in SIGN_EXTEND_INREG");
3583 assert(EVT.bitsLE(VT) && "Not extending!");
3584 if (EVT == VT) return N1; // Not actually extending
3586 auto SignExtendInReg = [&](APInt Val) {
3587 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3588 Val <<= Val.getBitWidth() - FromBits;
3589 Val = Val.ashr(Val.getBitWidth() - FromBits);
3590 return getConstant(Val, DL, VT.getScalarType());
3594 APInt Val = N1C->getAPIntValue();
3595 return SignExtendInReg(Val);
3597 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3598 SmallVector<SDValue, 8> Ops;
3599 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3600 SDValue Op = N1.getOperand(i);
3601 if (Op.getOpcode() == ISD::UNDEF) {
3602 Ops.push_back(getUNDEF(VT.getScalarType()));
3605 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3606 APInt Val = C->getAPIntValue();
3607 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3608 Ops.push_back(SignExtendInReg(Val));
3613 if (Ops.size() == VT.getVectorNumElements())
3614 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3618 case ISD::EXTRACT_VECTOR_ELT:
3619 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3620 if (N1.getOpcode() == ISD::UNDEF)
3621 return getUNDEF(VT);
3623 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3624 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3625 return getUNDEF(VT);
3627 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3628 // expanding copies of large vectors from registers.
3630 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3631 N1.getNumOperands() > 0) {
3633 N1.getOperand(0).getValueType().getVectorNumElements();
3634 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3635 N1.getOperand(N2C->getZExtValue() / Factor),
3636 getConstant(N2C->getZExtValue() % Factor, DL,
3637 N2.getValueType()));
3640 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3641 // expanding large vector constants.
3642 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3643 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3645 if (VT != Elt.getValueType())
3646 // If the vector element type is not legal, the BUILD_VECTOR operands
3647 // are promoted and implicitly truncated, and the result implicitly
3648 // extended. Make that explicit here.
3649 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3654 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3655 // operations are lowered to scalars.
3656 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3657 // If the indices are the same, return the inserted element else
3658 // if the indices are known different, extract the element from
3659 // the original vector.
3660 SDValue N1Op2 = N1.getOperand(2);
3661 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3663 if (N1Op2C && N2C) {
3664 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3665 if (VT == N1.getOperand(1).getValueType())
3666 return N1.getOperand(1);
3668 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3671 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3675 case ISD::EXTRACT_ELEMENT:
3676 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3677 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3678 (N1.getValueType().isInteger() == VT.isInteger()) &&
3679 N1.getValueType() != VT &&
3680 "Wrong types for EXTRACT_ELEMENT!");
3682 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3683 // 64-bit integers into 32-bit parts. Instead of building the extract of
3684 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3685 if (N1.getOpcode() == ISD::BUILD_PAIR)
3686 return N1.getOperand(N2C->getZExtValue());
3688 // EXTRACT_ELEMENT of a constant int is also very common.
3690 unsigned ElementSize = VT.getSizeInBits();
3691 unsigned Shift = ElementSize * N2C->getZExtValue();
3692 APInt ShiftedVal = N1C->getAPIntValue().lshr(Shift);
3693 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3696 case ISD::EXTRACT_SUBVECTOR:
3697 if (VT.isSimple() && N1.getValueType().isSimple()) {
3698 assert(VT.isVector() && N1.getValueType().isVector() &&
3699 "Extract subvector VTs must be a vectors!");
3700 assert(VT.getVectorElementType() ==
3701 N1.getValueType().getVectorElementType() &&
3702 "Extract subvector VTs must have the same element type!");
3703 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3704 "Extract subvector must be from larger vector to smaller vector!");
3707 assert((VT.getVectorNumElements() + N2C->getZExtValue()
3708 <= N1.getValueType().getVectorNumElements())
3709 && "Extract subvector overflow!");
3712 // Trivial extraction.
3713 if (VT.getSimpleVT() == N1.getSimpleValueType())
3719 // Perform trivial constant folding.
3721 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3724 // Constant fold FP operations.
3725 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3728 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3729 APFloat::opStatus s;
3732 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3733 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3734 return getConstantFP(V1, DL, VT);
3737 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3738 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3739 return getConstantFP(V1, DL, VT);
3742 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3743 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3744 return getConstantFP(V1, DL, VT);
3747 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3748 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3749 s!=APFloat::opDivByZero)) {
3750 return getConstantFP(V1, DL, VT);
3755 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3756 s!=APFloat::opDivByZero)) {
3757 return getConstantFP(V1, DL, VT);
3760 case ISD::FCOPYSIGN:
3762 return getConstantFP(V1, DL, VT);
3767 if (Opcode == ISD::FP_ROUND) {
3768 APFloat V = N1CFP->getValueAPF(); // make copy
3770 // This can return overflow, underflow, or inexact; we don't care.
3771 // FIXME need to be more flexible about rounding mode.
3772 (void)V.convert(EVTToAPFloatSemantics(VT),
3773 APFloat::rmNearestTiesToEven, &ignored);
3774 return getConstantFP(V, DL, VT);
3778 // Canonicalize an UNDEF to the RHS, even over a constant.
3779 if (N1.getOpcode() == ISD::UNDEF) {
3780 if (isCommutativeBinOp(Opcode)) {
3784 case ISD::FP_ROUND_INREG:
3785 case ISD::SIGN_EXTEND_INREG:
3791 return N1; // fold op(undef, arg2) -> undef
3799 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3800 // For vectors, we can't easily build an all zero vector, just return
3807 // Fold a bunch of operators when the RHS is undef.
3808 if (N2.getOpcode() == ISD::UNDEF) {
3811 if (N1.getOpcode() == ISD::UNDEF)
3812 // Handle undef ^ undef -> 0 special case. This is a common
3814 return getConstant(0, DL, VT);
3824 return N2; // fold op(arg1, undef) -> undef
3830 if (getTarget().Options.UnsafeFPMath)
3838 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3839 // For vectors, we can't easily build an all zero vector, just return
3844 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3845 // For vectors, we can't easily build an all one vector, just return
3853 // Memoize this node if possible.
3855 SDVTList VTs = getVTList(VT);
3856 if (VT != MVT::Glue) {
3857 SDValue Ops[] = {N1, N2};
3858 FoldingSetNodeID ID;
3859 AddNodeIDNode(ID, Opcode, VTs, Ops);
3860 AddNodeIDFlags(ID, Opcode, Flags);
3862 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3863 return SDValue(E, 0);
3865 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3867 CSEMap.InsertNode(N, IP);
3869 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3873 return SDValue(N, 0);
3876 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3877 SDValue N1, SDValue N2, SDValue N3) {
3878 // Perform various simplifications.
3881 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3882 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3883 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3884 if (N1CFP && N2CFP && N3CFP) {
3885 APFloat V1 = N1CFP->getValueAPF();
3886 const APFloat &V2 = N2CFP->getValueAPF();
3887 const APFloat &V3 = N3CFP->getValueAPF();
3888 APFloat::opStatus s =
3889 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3890 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3891 return getConstantFP(V1, DL, VT);
3895 case ISD::CONCAT_VECTORS:
3896 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3897 // one big BUILD_VECTOR.
3898 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3899 N2.getOpcode() == ISD::BUILD_VECTOR &&
3900 N3.getOpcode() == ISD::BUILD_VECTOR) {
3901 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3902 N1.getNode()->op_end());
3903 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3904 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3905 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3909 // Use FoldSetCC to simplify SETCC's.
3910 if (SDValue V = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL))
3915 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
3916 if (N1C->getZExtValue())
3917 return N2; // select true, X, Y -> X
3918 return N3; // select false, X, Y -> Y
3921 if (N2 == N3) return N2; // select C, X, X -> X
3923 case ISD::VECTOR_SHUFFLE:
3924 llvm_unreachable("should use getVectorShuffle constructor!");
3925 case ISD::INSERT_SUBVECTOR: {
3927 if (VT.isSimple() && N1.getValueType().isSimple()
3928 && N2.getValueType().isSimple()) {
3929 assert(VT.isVector() && N1.getValueType().isVector() &&
3930 N2.getValueType().isVector() &&
3931 "Insert subvector VTs must be a vectors");
3932 assert(VT == N1.getValueType() &&
3933 "Dest and insert subvector source types must match!");
3934 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3935 "Insert subvector must be from smaller vector to larger vector!");
3936 if (isa<ConstantSDNode>(Index)) {
3937 assert((N2.getValueType().getVectorNumElements() +
3938 cast<ConstantSDNode>(Index)->getZExtValue()
3939 <= VT.getVectorNumElements())
3940 && "Insert subvector overflow!");
3943 // Trivial insertion.
3944 if (VT.getSimpleVT() == N2.getSimpleValueType())
3950 // Fold bit_convert nodes from a type to themselves.
3951 if (N1.getValueType() == VT)
3956 // Memoize node if it doesn't produce a flag.
3958 SDVTList VTs = getVTList(VT);
3959 if (VT != MVT::Glue) {
3960 SDValue Ops[] = { N1, N2, N3 };
3961 FoldingSetNodeID ID;
3962 AddNodeIDNode(ID, Opcode, VTs, Ops);
3964 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3965 return SDValue(E, 0);
3967 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3968 DL.getDebugLoc(), VTs, N1, N2, N3);
3969 CSEMap.InsertNode(N, IP);
3971 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3972 DL.getDebugLoc(), VTs, N1, N2, N3);
3976 return SDValue(N, 0);
3979 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3980 SDValue N1, SDValue N2, SDValue N3,
3982 SDValue Ops[] = { N1, N2, N3, N4 };
3983 return getNode(Opcode, DL, VT, Ops);
3986 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3987 SDValue N1, SDValue N2, SDValue N3,
3988 SDValue N4, SDValue N5) {
3989 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3990 return getNode(Opcode, DL, VT, Ops);
3993 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3994 /// the incoming stack arguments to be loaded from the stack.
3995 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3996 SmallVector<SDValue, 8> ArgChains;
3998 // Include the original chain at the beginning of the list. When this is
3999 // used by target LowerCall hooks, this helps legalize find the
4000 // CALLSEQ_BEGIN node.
4001 ArgChains.push_back(Chain);
4003 // Add a chain value for each stack argument.
4004 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
4005 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
4006 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
4007 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
4008 if (FI->getIndex() < 0)
4009 ArgChains.push_back(SDValue(L, 1));
4011 // Build a tokenfactor for all the chains.
4012 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4015 /// getMemsetValue - Vectorized representation of the memset value
4017 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4019 assert(Value.getOpcode() != ISD::UNDEF);
4021 unsigned NumBits = VT.getScalarType().getSizeInBits();
4022 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4023 assert(C->getAPIntValue().getBitWidth() == 8);
4024 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4026 return DAG.getConstant(Val, dl, VT);
4027 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4031 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4032 EVT IntVT = VT.getScalarType();
4033 if (!IntVT.isInteger())
4034 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4036 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4038 // Use a multiplication with 0x010101... to extend the input to the
4040 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4041 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4042 DAG.getConstant(Magic, dl, IntVT));
4045 if (VT != Value.getValueType() && !VT.isInteger())
4046 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4047 if (VT != Value.getValueType()) {
4048 assert(VT.getVectorElementType() == Value.getValueType() &&
4049 "value type should be one vector element here");
4050 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4051 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4057 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4058 /// used when a memcpy is turned into a memset when the source is a constant
4060 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4061 const TargetLowering &TLI, StringRef Str) {
4062 // Handle vector with all elements zero.
4065 return DAG.getConstant(0, dl, VT);
4066 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4067 return DAG.getConstantFP(0.0, dl, VT);
4068 else if (VT.isVector()) {
4069 unsigned NumElts = VT.getVectorNumElements();
4070 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4071 return DAG.getNode(ISD::BITCAST, dl, VT,
4072 DAG.getConstant(0, dl,
4073 EVT::getVectorVT(*DAG.getContext(),
4076 llvm_unreachable("Expected type!");
4079 assert(!VT.isVector() && "Can't handle vector type here!");
4080 unsigned NumVTBits = VT.getSizeInBits();
4081 unsigned NumVTBytes = NumVTBits / 8;
4082 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4084 APInt Val(NumVTBits, 0);
4085 if (DAG.getDataLayout().isLittleEndian()) {
4086 for (unsigned i = 0; i != NumBytes; ++i)
4087 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4089 for (unsigned i = 0; i != NumBytes; ++i)
4090 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4093 // If the "cost" of materializing the integer immediate is less than the cost
4094 // of a load, then it is cost effective to turn the load into the immediate.
4095 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4096 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4097 return DAG.getConstant(Val, dl, VT);
4098 return SDValue(nullptr, 0);
4101 /// getMemBasePlusOffset - Returns base and offset node for the
4103 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4104 SelectionDAG &DAG) {
4105 EVT VT = Base.getValueType();
4106 return DAG.getNode(ISD::ADD, dl,
4107 VT, Base, DAG.getConstant(Offset, dl, VT));
4110 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4112 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4113 unsigned SrcDelta = 0;
4114 GlobalAddressSDNode *G = nullptr;
4115 if (Src.getOpcode() == ISD::GlobalAddress)
4116 G = cast<GlobalAddressSDNode>(Src);
4117 else if (Src.getOpcode() == ISD::ADD &&
4118 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4119 Src.getOperand(1).getOpcode() == ISD::Constant) {
4120 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4121 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4126 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4129 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4130 /// Return true if the number of memory ops is below the threshold (Limit).
4131 /// It returns the types of the sequence of memory ops to perform
4132 /// memset / memcpy by reference.
4133 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4134 unsigned Limit, uint64_t Size,
4135 unsigned DstAlign, unsigned SrcAlign,
4141 const TargetLowering &TLI) {
4142 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4143 "Expecting memcpy / memset source to meet alignment requirement!");
4144 // If 'SrcAlign' is zero, that means the memory operation does not need to
4145 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4146 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4147 // is the specified alignment of the memory operation. If it is zero, that
4148 // means it's possible to change the alignment of the destination.
4149 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4150 // not need to be loaded.
4151 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4152 IsMemset, ZeroMemset, MemcpyStrSrc,
4153 DAG.getMachineFunction());
4155 if (VT == MVT::Other) {
4157 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4158 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4159 VT = TLI.getPointerTy(DAG.getDataLayout());
4161 switch (DstAlign & 7) {
4162 case 0: VT = MVT::i64; break;
4163 case 4: VT = MVT::i32; break;
4164 case 2: VT = MVT::i16; break;
4165 default: VT = MVT::i8; break;
4170 while (!TLI.isTypeLegal(LVT))
4171 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4172 assert(LVT.isInteger());
4178 unsigned NumMemOps = 0;
4180 unsigned VTSize = VT.getSizeInBits() / 8;
4181 while (VTSize > Size) {
4182 // For now, only use non-vector load / store's for the left-over pieces.
4187 if (VT.isVector() || VT.isFloatingPoint()) {
4188 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4189 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4190 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4192 else if (NewVT == MVT::i64 &&
4193 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4194 TLI.isSafeMemOpType(MVT::f64)) {
4195 // i64 is usually not legal on 32-bit targets, but f64 may be.
4203 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4204 if (NewVT == MVT::i8)
4206 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4208 NewVTSize = NewVT.getSizeInBits() / 8;
4210 // If the new VT cannot cover all of the remaining bits, then consider
4211 // issuing a (or a pair of) unaligned and overlapping load / store.
4212 // FIXME: Only does this for 64-bit or more since we don't have proper
4213 // cost model for unaligned load / store.
4216 if (NumMemOps && AllowOverlap &&
4217 VTSize >= 8 && NewVTSize < Size &&
4218 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4226 if (++NumMemOps > Limit)
4229 MemOps.push_back(VT);
4236 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4237 // On Darwin, -Os means optimize for size without hurting performance, so
4238 // only really optimize for size when -Oz (MinSize) is used.
4239 if (MF.getTarget().getTargetTriple().isOSDarwin())
4240 return MF.getFunction()->optForMinSize();
4241 return MF.getFunction()->optForSize();
4244 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4245 SDValue Chain, SDValue Dst,
4246 SDValue Src, uint64_t Size,
4247 unsigned Align, bool isVol,
4249 MachinePointerInfo DstPtrInfo,
4250 MachinePointerInfo SrcPtrInfo) {
4251 // Turn a memcpy of undef to nop.
4252 if (Src.getOpcode() == ISD::UNDEF)
4255 // Expand memcpy to a series of load and store ops if the size operand falls
4256 // below a certain threshold.
4257 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4258 // rather than maybe a humongous number of loads and stores.
4259 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4260 std::vector<EVT> MemOps;
4261 bool DstAlignCanChange = false;
4262 MachineFunction &MF = DAG.getMachineFunction();
4263 MachineFrameInfo *MFI = MF.getFrameInfo();
4264 bool OptSize = shouldLowerMemFuncForSize(MF);
4265 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4266 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4267 DstAlignCanChange = true;
4268 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4269 if (Align > SrcAlign)
4272 bool CopyFromStr = isMemSrcFromString(Src, Str);
4273 bool isZeroStr = CopyFromStr && Str.empty();
4274 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4276 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4277 (DstAlignCanChange ? 0 : Align),
4278 (isZeroStr ? 0 : SrcAlign),
4279 false, false, CopyFromStr, true, DAG, TLI))
4282 if (DstAlignCanChange) {
4283 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4284 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4286 // Don't promote to an alignment that would require dynamic stack
4288 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4289 if (!TRI->needsStackRealignment(MF))
4290 while (NewAlign > Align &&
4291 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4294 if (NewAlign > Align) {
4295 // Give the stack frame object a larger alignment if needed.
4296 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4297 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4302 SmallVector<SDValue, 8> OutChains;
4303 unsigned NumMemOps = MemOps.size();
4304 uint64_t SrcOff = 0, DstOff = 0;
4305 for (unsigned i = 0; i != NumMemOps; ++i) {
4307 unsigned VTSize = VT.getSizeInBits() / 8;
4308 SDValue Value, Store;
4310 if (VTSize > Size) {
4311 // Issuing an unaligned load / store pair that overlaps with the previous
4312 // pair. Adjust the offset accordingly.
4313 assert(i == NumMemOps-1 && i != 0);
4314 SrcOff -= VTSize - Size;
4315 DstOff -= VTSize - Size;
4319 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4320 // It's unlikely a store of a vector immediate can be done in a single
4321 // instruction. It would require a load from a constantpool first.
4322 // We only handle zero vectors here.
4323 // FIXME: Handle other cases where store of vector immediate is done in
4324 // a single instruction.
4325 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4326 if (Value.getNode())
4327 Store = DAG.getStore(Chain, dl, Value,
4328 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4329 DstPtrInfo.getWithOffset(DstOff), isVol,
4333 if (!Store.getNode()) {
4334 // The type might not be legal for the target. This should only happen
4335 // if the type is smaller than a legal type, as on PPC, so the right
4336 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4337 // to Load/Store if NVT==VT.
4338 // FIXME does the case above also need this?
4339 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4340 assert(NVT.bitsGE(VT));
4341 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4342 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4343 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4344 false, MinAlign(SrcAlign, SrcOff));
4345 Store = DAG.getTruncStore(Chain, dl, Value,
4346 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4347 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4350 OutChains.push_back(Store);
4356 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4359 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4360 SDValue Chain, SDValue Dst,
4361 SDValue Src, uint64_t Size,
4362 unsigned Align, bool isVol,
4364 MachinePointerInfo DstPtrInfo,
4365 MachinePointerInfo SrcPtrInfo) {
4366 // Turn a memmove of undef to nop.
4367 if (Src.getOpcode() == ISD::UNDEF)
4370 // Expand memmove to a series of load and store ops if the size operand falls
4371 // below a certain threshold.
4372 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4373 std::vector<EVT> MemOps;
4374 bool DstAlignCanChange = false;
4375 MachineFunction &MF = DAG.getMachineFunction();
4376 MachineFrameInfo *MFI = MF.getFrameInfo();
4377 bool OptSize = shouldLowerMemFuncForSize(MF);
4378 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4379 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4380 DstAlignCanChange = true;
4381 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4382 if (Align > SrcAlign)
4384 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4386 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4387 (DstAlignCanChange ? 0 : Align), SrcAlign,
4388 false, false, false, false, DAG, TLI))
4391 if (DstAlignCanChange) {
4392 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4393 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4394 if (NewAlign > Align) {
4395 // Give the stack frame object a larger alignment if needed.
4396 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4397 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4402 uint64_t SrcOff = 0, DstOff = 0;
4403 SmallVector<SDValue, 8> LoadValues;
4404 SmallVector<SDValue, 8> LoadChains;
4405 SmallVector<SDValue, 8> OutChains;
4406 unsigned NumMemOps = MemOps.size();
4407 for (unsigned i = 0; i < NumMemOps; i++) {
4409 unsigned VTSize = VT.getSizeInBits() / 8;
4412 Value = DAG.getLoad(VT, dl, Chain,
4413 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4414 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4415 false, false, SrcAlign);
4416 LoadValues.push_back(Value);
4417 LoadChains.push_back(Value.getValue(1));
4420 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4422 for (unsigned i = 0; i < NumMemOps; i++) {
4424 unsigned VTSize = VT.getSizeInBits() / 8;
4427 Store = DAG.getStore(Chain, dl, LoadValues[i],
4428 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4429 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4430 OutChains.push_back(Store);
4434 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4437 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4440 /// \param DAG Selection DAG where lowered code is placed.
4441 /// \param dl Link to corresponding IR location.
4442 /// \param Chain Control flow dependency.
4443 /// \param Dst Pointer to destination memory location.
4444 /// \param Src Value of byte to write into the memory.
4445 /// \param Size Number of bytes to write.
4446 /// \param Align Alignment of the destination in bytes.
4447 /// \param isVol True if destination is volatile.
4448 /// \param DstPtrInfo IR information on the memory pointer.
4449 /// \returns New head in the control flow, if lowering was successful, empty
4450 /// SDValue otherwise.
4452 /// The function tries to replace 'llvm.memset' intrinsic with several store
4453 /// operations and value calculation code. This is usually profitable for small
4455 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4456 SDValue Chain, SDValue Dst,
4457 SDValue Src, uint64_t Size,
4458 unsigned Align, bool isVol,
4459 MachinePointerInfo DstPtrInfo) {
4460 // Turn a memset of undef to nop.
4461 if (Src.getOpcode() == ISD::UNDEF)
4464 // Expand memset to a series of load/store ops if the size operand
4465 // falls below a certain threshold.
4466 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4467 std::vector<EVT> MemOps;
4468 bool DstAlignCanChange = false;
4469 MachineFunction &MF = DAG.getMachineFunction();
4470 MachineFrameInfo *MFI = MF.getFrameInfo();
4471 bool OptSize = shouldLowerMemFuncForSize(MF);
4472 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4473 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4474 DstAlignCanChange = true;
4476 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4477 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4478 Size, (DstAlignCanChange ? 0 : Align), 0,
4479 true, IsZeroVal, false, true, DAG, TLI))
4482 if (DstAlignCanChange) {
4483 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4484 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4485 if (NewAlign > Align) {
4486 // Give the stack frame object a larger alignment if needed.
4487 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4488 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4493 SmallVector<SDValue, 8> OutChains;
4494 uint64_t DstOff = 0;
4495 unsigned NumMemOps = MemOps.size();
4497 // Find the largest store and generate the bit pattern for it.
4498 EVT LargestVT = MemOps[0];
4499 for (unsigned i = 1; i < NumMemOps; i++)
4500 if (MemOps[i].bitsGT(LargestVT))
4501 LargestVT = MemOps[i];
4502 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4504 for (unsigned i = 0; i < NumMemOps; i++) {
4506 unsigned VTSize = VT.getSizeInBits() / 8;
4507 if (VTSize > Size) {
4508 // Issuing an unaligned load / store pair that overlaps with the previous
4509 // pair. Adjust the offset accordingly.
4510 assert(i == NumMemOps-1 && i != 0);
4511 DstOff -= VTSize - Size;
4514 // If this store is smaller than the largest store see whether we can get
4515 // the smaller value for free with a truncate.
4516 SDValue Value = MemSetValue;
4517 if (VT.bitsLT(LargestVT)) {
4518 if (!LargestVT.isVector() && !VT.isVector() &&
4519 TLI.isTruncateFree(LargestVT, VT))
4520 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4522 Value = getMemsetValue(Src, VT, DAG, dl);
4524 assert(Value.getValueType() == VT && "Value with wrong type.");
4525 SDValue Store = DAG.getStore(Chain, dl, Value,
4526 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4527 DstPtrInfo.getWithOffset(DstOff),
4528 isVol, false, Align);
4529 OutChains.push_back(Store);
4530 DstOff += VT.getSizeInBits() / 8;
4534 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4537 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4538 SDValue Src, SDValue Size,
4539 unsigned Align, bool isVol, bool AlwaysInline,
4540 bool isTailCall, MachinePointerInfo DstPtrInfo,
4541 MachinePointerInfo SrcPtrInfo) {
4542 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4544 // Check to see if we should lower the memcpy to loads and stores first.
4545 // For cases within the target-specified limits, this is the best choice.
4546 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4548 // Memcpy with size zero? Just return the original chain.
4549 if (ConstantSize->isNullValue())
4552 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4553 ConstantSize->getZExtValue(),Align,
4554 isVol, false, DstPtrInfo, SrcPtrInfo);
4555 if (Result.getNode())
4559 // Then check to see if we should lower the memcpy with target-specific
4560 // code. If the target chooses to do this, this is the next best.
4562 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4563 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4564 DstPtrInfo, SrcPtrInfo);
4565 if (Result.getNode())
4569 // If we really need inline code and the target declined to provide it,
4570 // use a (potentially long) sequence of loads and stores.
4572 assert(ConstantSize && "AlwaysInline requires a constant size!");
4573 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4574 ConstantSize->getZExtValue(), Align, isVol,
4575 true, DstPtrInfo, SrcPtrInfo);
4578 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4579 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4580 // respect volatile, so they may do things like read or write memory
4581 // beyond the given memory regions. But fixing this isn't easy, and most
4582 // people don't care.
4584 // Emit a library call.
4585 TargetLowering::ArgListTy Args;
4586 TargetLowering::ArgListEntry Entry;
4587 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4588 Entry.Node = Dst; Args.push_back(Entry);
4589 Entry.Node = Src; Args.push_back(Entry);
4590 Entry.Node = Size; Args.push_back(Entry);
4591 // FIXME: pass in SDLoc
4592 TargetLowering::CallLoweringInfo CLI(*this);
4595 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4596 Type::getVoidTy(*getContext()),
4597 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4598 TLI->getPointerTy(getDataLayout())),
4601 .setTailCall(isTailCall);
4603 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4604 return CallResult.second;
4607 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4608 SDValue Src, SDValue Size,
4609 unsigned Align, bool isVol, bool isTailCall,
4610 MachinePointerInfo DstPtrInfo,
4611 MachinePointerInfo SrcPtrInfo) {
4612 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4614 // Check to see if we should lower the memmove to loads and stores first.
4615 // For cases within the target-specified limits, this is the best choice.
4616 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4618 // Memmove with size zero? Just return the original chain.
4619 if (ConstantSize->isNullValue())
4623 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4624 ConstantSize->getZExtValue(), Align, isVol,
4625 false, DstPtrInfo, SrcPtrInfo);
4626 if (Result.getNode())
4630 // Then check to see if we should lower the memmove with target-specific
4631 // code. If the target chooses to do this, this is the next best.
4633 SDValue Result = TSI->EmitTargetCodeForMemmove(
4634 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4635 if (Result.getNode())
4639 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4640 // not be safe. See memcpy above for more details.
4642 // Emit a library call.
4643 TargetLowering::ArgListTy Args;
4644 TargetLowering::ArgListEntry Entry;
4645 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4646 Entry.Node = Dst; Args.push_back(Entry);
4647 Entry.Node = Src; Args.push_back(Entry);
4648 Entry.Node = Size; Args.push_back(Entry);
4649 // FIXME: pass in SDLoc
4650 TargetLowering::CallLoweringInfo CLI(*this);
4653 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4654 Type::getVoidTy(*getContext()),
4655 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4656 TLI->getPointerTy(getDataLayout())),
4659 .setTailCall(isTailCall);
4661 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4662 return CallResult.second;
4665 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4666 SDValue Src, SDValue Size,
4667 unsigned Align, bool isVol, bool isTailCall,
4668 MachinePointerInfo DstPtrInfo) {
4669 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4671 // Check to see if we should lower the memset to stores first.
4672 // For cases within the target-specified limits, this is the best choice.
4673 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4675 // Memset with size zero? Just return the original chain.
4676 if (ConstantSize->isNullValue())
4680 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4681 Align, isVol, DstPtrInfo);
4683 if (Result.getNode())
4687 // Then check to see if we should lower the memset with target-specific
4688 // code. If the target chooses to do this, this is the next best.
4690 SDValue Result = TSI->EmitTargetCodeForMemset(
4691 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4692 if (Result.getNode())
4696 // Emit a library call.
4697 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4698 TargetLowering::ArgListTy Args;
4699 TargetLowering::ArgListEntry Entry;
4700 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4701 Args.push_back(Entry);
4703 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4704 Args.push_back(Entry);
4706 Entry.Ty = IntPtrTy;
4707 Args.push_back(Entry);
4709 // FIXME: pass in SDLoc
4710 TargetLowering::CallLoweringInfo CLI(*this);
4713 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4714 Type::getVoidTy(*getContext()),
4715 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4716 TLI->getPointerTy(getDataLayout())),
4719 .setTailCall(isTailCall);
4721 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4722 return CallResult.second;
4725 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4726 SDVTList VTList, ArrayRef<SDValue> Ops,
4727 MachineMemOperand *MMO,
4728 AtomicOrdering SuccessOrdering,
4729 AtomicOrdering FailureOrdering,
4730 SynchronizationScope SynchScope) {
4731 FoldingSetNodeID ID;
4732 ID.AddInteger(MemVT.getRawBits());
4733 AddNodeIDNode(ID, Opcode, VTList, Ops);
4734 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4736 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4737 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4738 return SDValue(E, 0);
4741 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4742 // SDNode doesn't have access to it. This memory will be "leaked" when
4743 // the node is deallocated, but recovered when the allocator is released.
4744 // If the number of operands is less than 5 we use AtomicSDNode's internal
4746 unsigned NumOps = Ops.size();
4747 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4750 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4751 dl.getDebugLoc(), VTList, MemVT,
4752 Ops.data(), DynOps, NumOps, MMO,
4753 SuccessOrdering, FailureOrdering,
4755 CSEMap.InsertNode(N, IP);
4757 return SDValue(N, 0);
4760 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4761 SDVTList VTList, ArrayRef<SDValue> Ops,
4762 MachineMemOperand *MMO,
4763 AtomicOrdering Ordering,
4764 SynchronizationScope SynchScope) {
4765 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4766 Ordering, SynchScope);
4769 SDValue SelectionDAG::getAtomicCmpSwap(
4770 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4771 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4772 unsigned Alignment, AtomicOrdering SuccessOrdering,
4773 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4774 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4775 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4776 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4778 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4779 Alignment = getEVTAlignment(MemVT);
4781 MachineFunction &MF = getMachineFunction();
4783 // FIXME: Volatile isn't really correct; we should keep track of atomic
4784 // orderings in the memoperand.
4785 unsigned Flags = MachineMemOperand::MOVolatile;
4786 Flags |= MachineMemOperand::MOLoad;
4787 Flags |= MachineMemOperand::MOStore;
4789 MachineMemOperand *MMO =
4790 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4792 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4793 SuccessOrdering, FailureOrdering, SynchScope);
4796 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4797 SDVTList VTs, SDValue Chain, SDValue Ptr,
4798 SDValue Cmp, SDValue Swp,
4799 MachineMemOperand *MMO,
4800 AtomicOrdering SuccessOrdering,
4801 AtomicOrdering FailureOrdering,
4802 SynchronizationScope SynchScope) {
4803 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4804 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4805 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4807 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4808 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4809 SuccessOrdering, FailureOrdering, SynchScope);
4812 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4814 SDValue Ptr, SDValue Val,
4815 const Value* PtrVal,
4817 AtomicOrdering Ordering,
4818 SynchronizationScope SynchScope) {
4819 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4820 Alignment = getEVTAlignment(MemVT);
4822 MachineFunction &MF = getMachineFunction();
4823 // An atomic store does not load. An atomic load does not store.
4824 // (An atomicrmw obviously both loads and stores.)
4825 // For now, atomics are considered to be volatile always, and they are
4827 // FIXME: Volatile isn't really correct; we should keep track of atomic
4828 // orderings in the memoperand.
4829 unsigned Flags = MachineMemOperand::MOVolatile;
4830 if (Opcode != ISD::ATOMIC_STORE)
4831 Flags |= MachineMemOperand::MOLoad;
4832 if (Opcode != ISD::ATOMIC_LOAD)
4833 Flags |= MachineMemOperand::MOStore;
4835 MachineMemOperand *MMO =
4836 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4837 MemVT.getStoreSize(), Alignment);
4839 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4840 Ordering, SynchScope);
4843 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4845 SDValue Ptr, SDValue Val,
4846 MachineMemOperand *MMO,
4847 AtomicOrdering Ordering,
4848 SynchronizationScope SynchScope) {
4849 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4850 Opcode == ISD::ATOMIC_LOAD_SUB ||
4851 Opcode == ISD::ATOMIC_LOAD_AND ||
4852 Opcode == ISD::ATOMIC_LOAD_OR ||
4853 Opcode == ISD::ATOMIC_LOAD_XOR ||
4854 Opcode == ISD::ATOMIC_LOAD_NAND ||
4855 Opcode == ISD::ATOMIC_LOAD_MIN ||
4856 Opcode == ISD::ATOMIC_LOAD_MAX ||
4857 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4858 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4859 Opcode == ISD::ATOMIC_SWAP ||
4860 Opcode == ISD::ATOMIC_STORE) &&
4861 "Invalid Atomic Op");
4863 EVT VT = Val.getValueType();
4865 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4866 getVTList(VT, MVT::Other);
4867 SDValue Ops[] = {Chain, Ptr, Val};
4868 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4871 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4872 EVT VT, SDValue Chain,
4874 MachineMemOperand *MMO,
4875 AtomicOrdering Ordering,
4876 SynchronizationScope SynchScope) {
4877 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4879 SDVTList VTs = getVTList(VT, MVT::Other);
4880 SDValue Ops[] = {Chain, Ptr};
4881 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4884 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4885 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4886 if (Ops.size() == 1)
4889 SmallVector<EVT, 4> VTs;
4890 VTs.reserve(Ops.size());
4891 for (unsigned i = 0; i < Ops.size(); ++i)
4892 VTs.push_back(Ops[i].getValueType());
4893 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4897 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4898 ArrayRef<SDValue> Ops,
4899 EVT MemVT, MachinePointerInfo PtrInfo,
4900 unsigned Align, bool Vol,
4901 bool ReadMem, bool WriteMem, unsigned Size) {
4902 if (Align == 0) // Ensure that codegen never sees alignment 0
4903 Align = getEVTAlignment(MemVT);
4905 MachineFunction &MF = getMachineFunction();
4908 Flags |= MachineMemOperand::MOStore;
4910 Flags |= MachineMemOperand::MOLoad;
4912 Flags |= MachineMemOperand::MOVolatile;
4914 Size = MemVT.getStoreSize();
4915 MachineMemOperand *MMO =
4916 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4918 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4922 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4923 ArrayRef<SDValue> Ops, EVT MemVT,
4924 MachineMemOperand *MMO) {
4925 assert((Opcode == ISD::INTRINSIC_VOID ||
4926 Opcode == ISD::INTRINSIC_W_CHAIN ||
4927 Opcode == ISD::PREFETCH ||
4928 Opcode == ISD::LIFETIME_START ||
4929 Opcode == ISD::LIFETIME_END ||
4930 (Opcode <= INT_MAX &&
4931 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4932 "Opcode is not a memory-accessing opcode!");
4934 // Memoize the node unless it returns a flag.
4935 MemIntrinsicSDNode *N;
4936 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4937 FoldingSetNodeID ID;
4938 AddNodeIDNode(ID, Opcode, VTList, Ops);
4939 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4941 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4942 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4943 return SDValue(E, 0);
4946 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4947 dl.getDebugLoc(), VTList, Ops,
4949 CSEMap.InsertNode(N, IP);
4951 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4952 dl.getDebugLoc(), VTList, Ops,
4956 return SDValue(N, 0);
4959 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4960 /// MachinePointerInfo record from it. This is particularly useful because the
4961 /// code generator has many cases where it doesn't bother passing in a
4962 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4963 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4964 int64_t Offset = 0) {
4965 // If this is FI+Offset, we can model it.
4966 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4967 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4968 FI->getIndex(), Offset);
4970 // If this is (FI+Offset1)+Offset2, we can model it.
4971 if (Ptr.getOpcode() != ISD::ADD ||
4972 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4973 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4974 return MachinePointerInfo();
4976 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4977 return MachinePointerInfo::getFixedStack(
4978 DAG.getMachineFunction(), FI,
4979 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4982 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4983 /// MachinePointerInfo record from it. This is particularly useful because the
4984 /// code generator has many cases where it doesn't bother passing in a
4985 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4986 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4988 // If the 'Offset' value isn't a constant, we can't handle this.
4989 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4990 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4991 if (OffsetOp.getOpcode() == ISD::UNDEF)
4992 return InferPointerInfo(DAG, Ptr);
4993 return MachinePointerInfo();
4998 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4999 EVT VT, SDLoc dl, SDValue Chain,
5000 SDValue Ptr, SDValue Offset,
5001 MachinePointerInfo PtrInfo, EVT MemVT,
5002 bool isVolatile, bool isNonTemporal, bool isInvariant,
5003 unsigned Alignment, const AAMDNodes &AAInfo,
5004 const MDNode *Ranges) {
5005 assert(Chain.getValueType() == MVT::Other &&
5006 "Invalid chain type");
5007 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5008 Alignment = getEVTAlignment(VT);
5010 unsigned Flags = MachineMemOperand::MOLoad;
5012 Flags |= MachineMemOperand::MOVolatile;
5014 Flags |= MachineMemOperand::MONonTemporal;
5016 Flags |= MachineMemOperand::MOInvariant;
5018 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5020 if (PtrInfo.V.isNull())
5021 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5023 MachineFunction &MF = getMachineFunction();
5024 MachineMemOperand *MMO =
5025 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5027 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5031 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5032 EVT VT, SDLoc dl, SDValue Chain,
5033 SDValue Ptr, SDValue Offset, EVT MemVT,
5034 MachineMemOperand *MMO) {
5036 ExtType = ISD::NON_EXTLOAD;
5037 } else if (ExtType == ISD::NON_EXTLOAD) {
5038 assert(VT == MemVT && "Non-extending load from different memory type!");
5041 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5042 "Should only be an extending load, not truncating!");
5043 assert(VT.isInteger() == MemVT.isInteger() &&
5044 "Cannot convert from FP to Int or Int -> FP!");
5045 assert(VT.isVector() == MemVT.isVector() &&
5046 "Cannot use an ext load to convert to or from a vector!");
5047 assert((!VT.isVector() ||
5048 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5049 "Cannot use an ext load to change the number of vector elements!");
5052 bool Indexed = AM != ISD::UNINDEXED;
5053 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5054 "Unindexed load with an offset!");
5056 SDVTList VTs = Indexed ?
5057 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5058 SDValue Ops[] = { Chain, Ptr, Offset };
5059 FoldingSetNodeID ID;
5060 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5061 ID.AddInteger(MemVT.getRawBits());
5062 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5063 MMO->isNonTemporal(),
5064 MMO->isInvariant()));
5065 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5067 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5068 cast<LoadSDNode>(E)->refineAlignment(MMO);
5069 return SDValue(E, 0);
5071 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5072 dl.getDebugLoc(), VTs, AM, ExtType,
5074 CSEMap.InsertNode(N, IP);
5076 return SDValue(N, 0);
5079 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5080 SDValue Chain, SDValue Ptr,
5081 MachinePointerInfo PtrInfo,
5082 bool isVolatile, bool isNonTemporal,
5083 bool isInvariant, unsigned Alignment,
5084 const AAMDNodes &AAInfo,
5085 const MDNode *Ranges) {
5086 SDValue Undef = getUNDEF(Ptr.getValueType());
5087 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5088 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5092 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5093 SDValue Chain, SDValue Ptr,
5094 MachineMemOperand *MMO) {
5095 SDValue Undef = getUNDEF(Ptr.getValueType());
5096 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5100 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5101 SDValue Chain, SDValue Ptr,
5102 MachinePointerInfo PtrInfo, EVT MemVT,
5103 bool isVolatile, bool isNonTemporal,
5104 bool isInvariant, unsigned Alignment,
5105 const AAMDNodes &AAInfo) {
5106 SDValue Undef = getUNDEF(Ptr.getValueType());
5107 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5108 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5113 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5114 SDValue Chain, SDValue Ptr, EVT MemVT,
5115 MachineMemOperand *MMO) {
5116 SDValue Undef = getUNDEF(Ptr.getValueType());
5117 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5122 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5123 SDValue Offset, ISD::MemIndexedMode AM) {
5124 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5125 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5126 "Load is already a indexed load!");
5127 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5128 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5129 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5130 false, LD->getAlignment());
5133 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5134 SDValue Ptr, MachinePointerInfo PtrInfo,
5135 bool isVolatile, bool isNonTemporal,
5136 unsigned Alignment, const AAMDNodes &AAInfo) {
5137 assert(Chain.getValueType() == MVT::Other &&
5138 "Invalid chain type");
5139 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5140 Alignment = getEVTAlignment(Val.getValueType());
5142 unsigned Flags = MachineMemOperand::MOStore;
5144 Flags |= MachineMemOperand::MOVolatile;
5146 Flags |= MachineMemOperand::MONonTemporal;
5148 if (PtrInfo.V.isNull())
5149 PtrInfo = InferPointerInfo(*this, Ptr);
5151 MachineFunction &MF = getMachineFunction();
5152 MachineMemOperand *MMO =
5153 MF.getMachineMemOperand(PtrInfo, Flags,
5154 Val.getValueType().getStoreSize(), Alignment,
5157 return getStore(Chain, dl, Val, Ptr, MMO);
5160 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5161 SDValue Ptr, MachineMemOperand *MMO) {
5162 assert(Chain.getValueType() == MVT::Other &&
5163 "Invalid chain type");
5164 EVT VT = Val.getValueType();
5165 SDVTList VTs = getVTList(MVT::Other);
5166 SDValue Undef = getUNDEF(Ptr.getValueType());
5167 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5168 FoldingSetNodeID ID;
5169 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5170 ID.AddInteger(VT.getRawBits());
5171 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5172 MMO->isNonTemporal(), MMO->isInvariant()));
5173 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5175 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5176 cast<StoreSDNode>(E)->refineAlignment(MMO);
5177 return SDValue(E, 0);
5179 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5180 dl.getDebugLoc(), VTs,
5181 ISD::UNINDEXED, false, VT, MMO);
5182 CSEMap.InsertNode(N, IP);
5184 return SDValue(N, 0);
5187 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5188 SDValue Ptr, MachinePointerInfo PtrInfo,
5189 EVT SVT,bool isVolatile, bool isNonTemporal,
5191 const AAMDNodes &AAInfo) {
5192 assert(Chain.getValueType() == MVT::Other &&
5193 "Invalid chain type");
5194 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5195 Alignment = getEVTAlignment(SVT);
5197 unsigned Flags = MachineMemOperand::MOStore;
5199 Flags |= MachineMemOperand::MOVolatile;
5201 Flags |= MachineMemOperand::MONonTemporal;
5203 if (PtrInfo.V.isNull())
5204 PtrInfo = InferPointerInfo(*this, Ptr);
5206 MachineFunction &MF = getMachineFunction();
5207 MachineMemOperand *MMO =
5208 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5211 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5214 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5215 SDValue Ptr, EVT SVT,
5216 MachineMemOperand *MMO) {
5217 EVT VT = Val.getValueType();
5219 assert(Chain.getValueType() == MVT::Other &&
5220 "Invalid chain type");
5222 return getStore(Chain, dl, Val, Ptr, MMO);
5224 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5225 "Should only be a truncating store, not extending!");
5226 assert(VT.isInteger() == SVT.isInteger() &&
5227 "Can't do FP-INT conversion!");
5228 assert(VT.isVector() == SVT.isVector() &&
5229 "Cannot use trunc store to convert to or from a vector!");
5230 assert((!VT.isVector() ||
5231 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5232 "Cannot use trunc store to change the number of vector elements!");
5234 SDVTList VTs = getVTList(MVT::Other);
5235 SDValue Undef = getUNDEF(Ptr.getValueType());
5236 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5237 FoldingSetNodeID ID;
5238 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5239 ID.AddInteger(SVT.getRawBits());
5240 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5241 MMO->isNonTemporal(), MMO->isInvariant()));
5242 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5244 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5245 cast<StoreSDNode>(E)->refineAlignment(MMO);
5246 return SDValue(E, 0);
5248 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5249 dl.getDebugLoc(), VTs,
5250 ISD::UNINDEXED, true, SVT, MMO);
5251 CSEMap.InsertNode(N, IP);
5253 return SDValue(N, 0);
5257 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5258 SDValue Offset, ISD::MemIndexedMode AM) {
5259 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5260 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5261 "Store is already a indexed store!");
5262 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5263 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5264 FoldingSetNodeID ID;
5265 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5266 ID.AddInteger(ST->getMemoryVT().getRawBits());
5267 ID.AddInteger(ST->getRawSubclassData());
5268 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5270 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5271 return SDValue(E, 0);
5273 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5274 dl.getDebugLoc(), VTs, AM,
5275 ST->isTruncatingStore(),
5277 ST->getMemOperand());
5278 CSEMap.InsertNode(N, IP);
5280 return SDValue(N, 0);
5284 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5285 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5286 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5288 SDVTList VTs = getVTList(VT, MVT::Other);
5289 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5290 FoldingSetNodeID ID;
5291 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5292 ID.AddInteger(VT.getRawBits());
5293 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5295 MMO->isNonTemporal(),
5296 MMO->isInvariant()));
5297 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5299 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5300 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5301 return SDValue(E, 0);
5303 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5304 dl.getDebugLoc(), Ops, 4, VTs,
5306 CSEMap.InsertNode(N, IP);
5308 return SDValue(N, 0);
5311 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5312 SDValue Ptr, SDValue Mask, EVT MemVT,
5313 MachineMemOperand *MMO, bool isTrunc) {
5314 assert(Chain.getValueType() == MVT::Other &&
5315 "Invalid chain type");
5316 EVT VT = Val.getValueType();
5317 SDVTList VTs = getVTList(MVT::Other);
5318 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5319 FoldingSetNodeID ID;
5320 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5321 ID.AddInteger(VT.getRawBits());
5322 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5323 MMO->isNonTemporal(), MMO->isInvariant()));
5324 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5326 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5327 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5328 return SDValue(E, 0);
5330 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5331 dl.getDebugLoc(), Ops, 4,
5332 VTs, isTrunc, MemVT, MMO);
5333 CSEMap.InsertNode(N, IP);
5335 return SDValue(N, 0);
5339 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5340 ArrayRef<SDValue> Ops,
5341 MachineMemOperand *MMO) {
5343 FoldingSetNodeID ID;
5344 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5345 ID.AddInteger(VT.getRawBits());
5346 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5348 MMO->isNonTemporal(),
5349 MMO->isInvariant()));
5350 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5352 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5353 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5354 return SDValue(E, 0);
5356 MaskedGatherSDNode *N =
5357 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5359 CSEMap.InsertNode(N, IP);
5361 return SDValue(N, 0);
5364 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5365 ArrayRef<SDValue> Ops,
5366 MachineMemOperand *MMO) {
5367 FoldingSetNodeID ID;
5368 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5369 ID.AddInteger(VT.getRawBits());
5370 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5371 MMO->isNonTemporal(),
5372 MMO->isInvariant()));
5373 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5375 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5376 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5377 return SDValue(E, 0);
5380 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5382 CSEMap.InsertNode(N, IP);
5384 return SDValue(N, 0);
5387 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5388 SDValue Chain, SDValue Ptr,
5391 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5392 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5395 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5396 ArrayRef<SDUse> Ops) {
5397 switch (Ops.size()) {
5398 case 0: return getNode(Opcode, DL, VT);
5399 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5400 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5401 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5405 // Copy from an SDUse array into an SDValue array for use with
5406 // the regular getNode logic.
5407 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5408 return getNode(Opcode, DL, VT, NewOps);
5411 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5412 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5413 unsigned NumOps = Ops.size();
5415 case 0: return getNode(Opcode, DL, VT);
5416 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5417 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5418 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5424 case ISD::SELECT_CC: {
5425 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5426 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5427 "LHS and RHS of condition must have same type!");
5428 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5429 "True and False arms of SelectCC must have same type!");
5430 assert(Ops[2].getValueType() == VT &&
5431 "select_cc node must be of same type as true and false value!");
5435 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5436 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5437 "LHS/RHS of comparison should match types!");
5444 SDVTList VTs = getVTList(VT);
5446 if (VT != MVT::Glue) {
5447 FoldingSetNodeID ID;
5448 AddNodeIDNode(ID, Opcode, VTs, Ops);
5451 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5452 return SDValue(E, 0);
5454 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5456 CSEMap.InsertNode(N, IP);
5458 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5463 return SDValue(N, 0);
5466 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5467 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5468 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5471 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5472 ArrayRef<SDValue> Ops) {
5473 if (VTList.NumVTs == 1)
5474 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5478 // FIXME: figure out how to safely handle things like
5479 // int foo(int x) { return 1 << (x & 255); }
5480 // int bar() { return foo(256); }
5481 case ISD::SRA_PARTS:
5482 case ISD::SRL_PARTS:
5483 case ISD::SHL_PARTS:
5484 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5485 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5486 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5487 else if (N3.getOpcode() == ISD::AND)
5488 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5489 // If the and is only masking out bits that cannot effect the shift,
5490 // eliminate the and.
5491 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5492 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5493 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5499 // Memoize the node unless it returns a flag.
5501 unsigned NumOps = Ops.size();
5502 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5503 FoldingSetNodeID ID;
5504 AddNodeIDNode(ID, Opcode, VTList, Ops);
5506 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5507 return SDValue(E, 0);
5510 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5511 DL.getDebugLoc(), VTList, Ops[0]);
5512 } else if (NumOps == 2) {
5513 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5514 DL.getDebugLoc(), VTList, Ops[0],
5516 } else if (NumOps == 3) {
5517 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5518 DL.getDebugLoc(), VTList, Ops[0],
5521 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5524 CSEMap.InsertNode(N, IP);
5527 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5528 DL.getDebugLoc(), VTList, Ops[0]);
5529 } else if (NumOps == 2) {
5530 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5531 DL.getDebugLoc(), VTList, Ops[0],
5533 } else if (NumOps == 3) {
5534 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5535 DL.getDebugLoc(), VTList, Ops[0],
5538 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5543 return SDValue(N, 0);
5546 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5547 return getNode(Opcode, DL, VTList, None);
5550 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5552 SDValue Ops[] = { N1 };
5553 return getNode(Opcode, DL, VTList, Ops);
5556 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5557 SDValue N1, SDValue N2) {
5558 SDValue Ops[] = { N1, N2 };
5559 return getNode(Opcode, DL, VTList, Ops);
5562 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5563 SDValue N1, SDValue N2, SDValue N3) {
5564 SDValue Ops[] = { N1, N2, N3 };
5565 return getNode(Opcode, DL, VTList, Ops);
5568 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5569 SDValue N1, SDValue N2, SDValue N3,
5571 SDValue Ops[] = { N1, N2, N3, N4 };
5572 return getNode(Opcode, DL, VTList, Ops);
5575 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5576 SDValue N1, SDValue N2, SDValue N3,
5577 SDValue N4, SDValue N5) {
5578 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5579 return getNode(Opcode, DL, VTList, Ops);
5582 SDVTList SelectionDAG::getVTList(EVT VT) {
5583 return makeVTList(SDNode::getValueTypeList(VT), 1);
5586 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5587 FoldingSetNodeID ID;
5589 ID.AddInteger(VT1.getRawBits());
5590 ID.AddInteger(VT2.getRawBits());
5593 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5595 EVT *Array = Allocator.Allocate<EVT>(2);
5598 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5599 VTListMap.InsertNode(Result, IP);
5601 return Result->getSDVTList();
5604 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5605 FoldingSetNodeID ID;
5607 ID.AddInteger(VT1.getRawBits());
5608 ID.AddInteger(VT2.getRawBits());
5609 ID.AddInteger(VT3.getRawBits());
5612 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5614 EVT *Array = Allocator.Allocate<EVT>(3);
5618 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5619 VTListMap.InsertNode(Result, IP);
5621 return Result->getSDVTList();
5624 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5625 FoldingSetNodeID ID;
5627 ID.AddInteger(VT1.getRawBits());
5628 ID.AddInteger(VT2.getRawBits());
5629 ID.AddInteger(VT3.getRawBits());
5630 ID.AddInteger(VT4.getRawBits());
5633 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5635 EVT *Array = Allocator.Allocate<EVT>(4);
5640 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5641 VTListMap.InsertNode(Result, IP);
5643 return Result->getSDVTList();
5646 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5647 unsigned NumVTs = VTs.size();
5648 FoldingSetNodeID ID;
5649 ID.AddInteger(NumVTs);
5650 for (unsigned index = 0; index < NumVTs; index++) {
5651 ID.AddInteger(VTs[index].getRawBits());
5655 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5657 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5658 std::copy(VTs.begin(), VTs.end(), Array);
5659 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5660 VTListMap.InsertNode(Result, IP);
5662 return Result->getSDVTList();
5666 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5667 /// specified operands. If the resultant node already exists in the DAG,
5668 /// this does not modify the specified node, instead it returns the node that
5669 /// already exists. If the resultant node does not exist in the DAG, the
5670 /// input node is returned. As a degenerate case, if you specify the same
5671 /// input operands as the node already has, the input node is returned.
5672 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5673 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5675 // Check to see if there is no change.
5676 if (Op == N->getOperand(0)) return N;
5678 // See if the modified node already exists.
5679 void *InsertPos = nullptr;
5680 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5683 // Nope it doesn't. Remove the node from its current place in the maps.
5685 if (!RemoveNodeFromCSEMaps(N))
5686 InsertPos = nullptr;
5688 // Now we update the operands.
5689 N->OperandList[0].set(Op);
5691 // If this gets put into a CSE map, add it.
5692 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5696 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5697 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5699 // Check to see if there is no change.
5700 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5701 return N; // No operands changed, just return the input node.
5703 // See if the modified node already exists.
5704 void *InsertPos = nullptr;
5705 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5708 // Nope it doesn't. Remove the node from its current place in the maps.
5710 if (!RemoveNodeFromCSEMaps(N))
5711 InsertPos = nullptr;
5713 // Now we update the operands.
5714 if (N->OperandList[0] != Op1)
5715 N->OperandList[0].set(Op1);
5716 if (N->OperandList[1] != Op2)
5717 N->OperandList[1].set(Op2);
5719 // If this gets put into a CSE map, add it.
5720 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5724 SDNode *SelectionDAG::
5725 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5726 SDValue Ops[] = { Op1, Op2, Op3 };
5727 return UpdateNodeOperands(N, Ops);
5730 SDNode *SelectionDAG::
5731 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5732 SDValue Op3, SDValue Op4) {
5733 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5734 return UpdateNodeOperands(N, Ops);
5737 SDNode *SelectionDAG::
5738 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5739 SDValue Op3, SDValue Op4, SDValue Op5) {
5740 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5741 return UpdateNodeOperands(N, Ops);
5744 SDNode *SelectionDAG::
5745 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5746 unsigned NumOps = Ops.size();
5747 assert(N->getNumOperands() == NumOps &&
5748 "Update with wrong number of operands");
5750 // If no operands changed just return the input node.
5751 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5754 // See if the modified node already exists.
5755 void *InsertPos = nullptr;
5756 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5759 // Nope it doesn't. Remove the node from its current place in the maps.
5761 if (!RemoveNodeFromCSEMaps(N))
5762 InsertPos = nullptr;
5764 // Now we update the operands.
5765 for (unsigned i = 0; i != NumOps; ++i)
5766 if (N->OperandList[i] != Ops[i])
5767 N->OperandList[i].set(Ops[i]);
5769 // If this gets put into a CSE map, add it.
5770 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5774 /// DropOperands - Release the operands and set this node to have
5776 void SDNode::DropOperands() {
5777 // Unlike the code in MorphNodeTo that does this, we don't need to
5778 // watch for dead nodes here.
5779 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5785 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5788 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5790 SDVTList VTs = getVTList(VT);
5791 return SelectNodeTo(N, MachineOpc, VTs, None);
5794 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5795 EVT VT, SDValue Op1) {
5796 SDVTList VTs = getVTList(VT);
5797 SDValue Ops[] = { Op1 };
5798 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5801 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5802 EVT VT, SDValue Op1,
5804 SDVTList VTs = getVTList(VT);
5805 SDValue Ops[] = { Op1, Op2 };
5806 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5809 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5810 EVT VT, SDValue Op1,
5811 SDValue Op2, SDValue Op3) {
5812 SDVTList VTs = getVTList(VT);
5813 SDValue Ops[] = { Op1, Op2, Op3 };
5814 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5817 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5818 EVT VT, ArrayRef<SDValue> Ops) {
5819 SDVTList VTs = getVTList(VT);
5820 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5823 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5824 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5825 SDVTList VTs = getVTList(VT1, VT2);
5826 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5829 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5831 SDVTList VTs = getVTList(VT1, VT2);
5832 return SelectNodeTo(N, MachineOpc, VTs, None);
5835 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5836 EVT VT1, EVT VT2, EVT VT3,
5837 ArrayRef<SDValue> Ops) {
5838 SDVTList VTs = getVTList(VT1, VT2, VT3);
5839 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5842 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5843 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5844 ArrayRef<SDValue> Ops) {
5845 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5846 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5849 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5852 SDVTList VTs = getVTList(VT1, VT2);
5853 SDValue Ops[] = { Op1 };
5854 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5857 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5859 SDValue Op1, SDValue Op2) {
5860 SDVTList VTs = getVTList(VT1, VT2);
5861 SDValue Ops[] = { Op1, Op2 };
5862 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5865 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5867 SDValue Op1, SDValue Op2,
5869 SDVTList VTs = getVTList(VT1, VT2);
5870 SDValue Ops[] = { Op1, Op2, Op3 };
5871 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5874 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5875 EVT VT1, EVT VT2, EVT VT3,
5876 SDValue Op1, SDValue Op2,
5878 SDVTList VTs = getVTList(VT1, VT2, VT3);
5879 SDValue Ops[] = { Op1, Op2, Op3 };
5880 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5883 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5884 SDVTList VTs,ArrayRef<SDValue> Ops) {
5885 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5886 // Reset the NodeID to -1.
5891 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5892 /// the line number information on the merged node since it is not possible to
5893 /// preserve the information that operation is associated with multiple lines.
5894 /// This will make the debugger working better at -O0, were there is a higher
5895 /// probability having other instructions associated with that line.
5897 /// For IROrder, we keep the smaller of the two
5898 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5899 DebugLoc NLoc = N->getDebugLoc();
5900 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5901 N->setDebugLoc(DebugLoc());
5903 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5904 N->setIROrder(Order);
5908 /// MorphNodeTo - This *mutates* the specified node to have the specified
5909 /// return type, opcode, and operands.
5911 /// Note that MorphNodeTo returns the resultant node. If there is already a
5912 /// node of the specified opcode and operands, it returns that node instead of
5913 /// the current one. Note that the SDLoc need not be the same.
5915 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5916 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5917 /// node, and because it doesn't require CSE recalculation for any of
5918 /// the node's users.
5920 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5921 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5922 /// the legalizer which maintain worklists that would need to be updated when
5923 /// deleting things.
5924 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5925 SDVTList VTs, ArrayRef<SDValue> Ops) {
5926 unsigned NumOps = Ops.size();
5927 // If an identical node already exists, use it.
5929 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5930 FoldingSetNodeID ID;
5931 AddNodeIDNode(ID, Opc, VTs, Ops);
5932 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5933 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5936 if (!RemoveNodeFromCSEMaps(N))
5939 // Start the morphing.
5941 N->ValueList = VTs.VTs;
5942 N->NumValues = VTs.NumVTs;
5944 // Clear the operands list, updating used nodes to remove this from their
5945 // use list. Keep track of any operands that become dead as a result.
5946 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5947 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5949 SDNode *Used = Use.getNode();
5951 if (Used->use_empty())
5952 DeadNodeSet.insert(Used);
5955 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5956 // Initialize the memory references information.
5957 MN->setMemRefs(nullptr, nullptr);
5958 // If NumOps is larger than the # of operands we can have in a
5959 // MachineSDNode, reallocate the operand list.
5960 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5961 if (MN->OperandsNeedDelete)
5962 delete[] MN->OperandList;
5963 if (NumOps > array_lengthof(MN->LocalOperands))
5964 // We're creating a final node that will live unmorphed for the
5965 // remainder of the current SelectionDAG iteration, so we can allocate
5966 // the operands directly out of a pool with no recycling metadata.
5967 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5968 Ops.data(), NumOps);
5970 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5971 MN->OperandsNeedDelete = false;
5973 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5975 // If NumOps is larger than the # of operands we currently have, reallocate
5976 // the operand list.
5977 if (NumOps > N->NumOperands) {
5978 if (N->OperandsNeedDelete)
5979 delete[] N->OperandList;
5980 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5981 N->OperandsNeedDelete = true;
5983 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5986 // Delete any nodes that are still dead after adding the uses for the
5988 if (!DeadNodeSet.empty()) {
5989 SmallVector<SDNode *, 16> DeadNodes;
5990 for (SDNode *N : DeadNodeSet)
5992 DeadNodes.push_back(N);
5993 RemoveDeadNodes(DeadNodes);
5997 CSEMap.InsertNode(N, IP); // Memoize the new node.
6002 /// getMachineNode - These are used for target selectors to create a new node
6003 /// with specified return type(s), MachineInstr opcode, and operands.
6005 /// Note that getMachineNode returns the resultant node. If there is already a
6006 /// node of the specified opcode and operands, it returns that node instead of
6007 /// the current one.
6009 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
6010 SDVTList VTs = getVTList(VT);
6011 return getMachineNode(Opcode, dl, VTs, None);
6015 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6016 SDVTList VTs = getVTList(VT);
6017 SDValue Ops[] = { Op1 };
6018 return getMachineNode(Opcode, dl, VTs, Ops);
6022 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6023 SDValue Op1, SDValue Op2) {
6024 SDVTList VTs = getVTList(VT);
6025 SDValue Ops[] = { Op1, Op2 };
6026 return getMachineNode(Opcode, dl, VTs, Ops);
6030 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6031 SDValue Op1, SDValue Op2, SDValue Op3) {
6032 SDVTList VTs = getVTList(VT);
6033 SDValue Ops[] = { Op1, Op2, Op3 };
6034 return getMachineNode(Opcode, dl, VTs, Ops);
6038 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6039 ArrayRef<SDValue> Ops) {
6040 SDVTList VTs = getVTList(VT);
6041 return getMachineNode(Opcode, dl, VTs, Ops);
6045 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6046 SDVTList VTs = getVTList(VT1, VT2);
6047 return getMachineNode(Opcode, dl, VTs, None);
6051 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6052 EVT VT1, EVT VT2, SDValue Op1) {
6053 SDVTList VTs = getVTList(VT1, VT2);
6054 SDValue Ops[] = { Op1 };
6055 return getMachineNode(Opcode, dl, VTs, Ops);
6059 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6060 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6061 SDVTList VTs = getVTList(VT1, VT2);
6062 SDValue Ops[] = { Op1, Op2 };
6063 return getMachineNode(Opcode, dl, VTs, Ops);
6067 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6068 EVT VT1, EVT VT2, SDValue Op1,
6069 SDValue Op2, SDValue Op3) {
6070 SDVTList VTs = getVTList(VT1, VT2);
6071 SDValue Ops[] = { Op1, Op2, Op3 };
6072 return getMachineNode(Opcode, dl, VTs, Ops);
6076 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6078 ArrayRef<SDValue> Ops) {
6079 SDVTList VTs = getVTList(VT1, VT2);
6080 return getMachineNode(Opcode, dl, VTs, Ops);
6084 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6085 EVT VT1, EVT VT2, EVT VT3,
6086 SDValue Op1, SDValue Op2) {
6087 SDVTList VTs = getVTList(VT1, VT2, VT3);
6088 SDValue Ops[] = { Op1, Op2 };
6089 return getMachineNode(Opcode, dl, VTs, Ops);
6093 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6094 EVT VT1, EVT VT2, EVT VT3,
6095 SDValue Op1, SDValue Op2, SDValue Op3) {
6096 SDVTList VTs = getVTList(VT1, VT2, VT3);
6097 SDValue Ops[] = { Op1, Op2, Op3 };
6098 return getMachineNode(Opcode, dl, VTs, Ops);
6102 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6103 EVT VT1, EVT VT2, EVT VT3,
6104 ArrayRef<SDValue> Ops) {
6105 SDVTList VTs = getVTList(VT1, VT2, VT3);
6106 return getMachineNode(Opcode, dl, VTs, Ops);
6110 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6111 EVT VT2, EVT VT3, EVT VT4,
6112 ArrayRef<SDValue> Ops) {
6113 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6114 return getMachineNode(Opcode, dl, VTs, Ops);
6118 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6119 ArrayRef<EVT> ResultTys,
6120 ArrayRef<SDValue> Ops) {
6121 SDVTList VTs = getVTList(ResultTys);
6122 return getMachineNode(Opcode, dl, VTs, Ops);
6126 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6127 ArrayRef<SDValue> OpsArray) {
6128 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6131 const SDValue *Ops = OpsArray.data();
6132 unsigned NumOps = OpsArray.size();
6135 FoldingSetNodeID ID;
6136 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6138 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6139 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6143 // Allocate a new MachineSDNode.
6144 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6145 DL.getDebugLoc(), VTs);
6147 // Initialize the operands list.
6148 if (NumOps > array_lengthof(N->LocalOperands))
6149 // We're creating a final node that will live unmorphed for the
6150 // remainder of the current SelectionDAG iteration, so we can allocate
6151 // the operands directly out of a pool with no recycling metadata.
6152 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6155 N->InitOperands(N->LocalOperands, Ops, NumOps);
6156 N->OperandsNeedDelete = false;
6159 CSEMap.InsertNode(N, IP);
6165 /// getTargetExtractSubreg - A convenience function for creating
6166 /// TargetOpcode::EXTRACT_SUBREG nodes.
6168 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6170 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6171 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6172 VT, Operand, SRIdxVal);
6173 return SDValue(Subreg, 0);
6176 /// getTargetInsertSubreg - A convenience function for creating
6177 /// TargetOpcode::INSERT_SUBREG nodes.
6179 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6180 SDValue Operand, SDValue Subreg) {
6181 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6182 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6183 VT, Operand, Subreg, SRIdxVal);
6184 return SDValue(Result, 0);
6187 /// getNodeIfExists - Get the specified node if it's already available, or
6188 /// else return NULL.
6189 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6190 ArrayRef<SDValue> Ops,
6191 const SDNodeFlags *Flags) {
6192 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6193 FoldingSetNodeID ID;
6194 AddNodeIDNode(ID, Opcode, VTList, Ops);
6195 AddNodeIDFlags(ID, Opcode, Flags);
6197 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6203 /// getDbgValue - Creates a SDDbgValue node.
6206 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6207 unsigned R, bool IsIndirect, uint64_t Off,
6208 DebugLoc DL, unsigned O) {
6209 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6210 "Expected inlined-at fields to agree");
6211 return new (DbgInfo->getAlloc())
6212 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6216 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6217 const Value *C, uint64_t Off,
6218 DebugLoc DL, unsigned O) {
6219 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6220 "Expected inlined-at fields to agree");
6221 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6225 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6226 unsigned FI, uint64_t Off,
6227 DebugLoc DL, unsigned O) {
6228 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6229 "Expected inlined-at fields to agree");
6230 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6235 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6236 /// pointed to by a use iterator is deleted, increment the use iterator
6237 /// so that it doesn't dangle.
6239 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6240 SDNode::use_iterator &UI;
6241 SDNode::use_iterator &UE;
6243 void NodeDeleted(SDNode *N, SDNode *E) override {
6244 // Increment the iterator as needed.
6245 while (UI != UE && N == *UI)
6250 RAUWUpdateListener(SelectionDAG &d,
6251 SDNode::use_iterator &ui,
6252 SDNode::use_iterator &ue)
6253 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6258 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6259 /// This can cause recursive merging of nodes in the DAG.
6261 /// This version assumes From has a single result value.
6263 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6264 SDNode *From = FromN.getNode();
6265 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6266 "Cannot replace with this method!");
6267 assert(From != To.getNode() && "Cannot replace uses of with self");
6269 // Iterate over all the existing uses of From. New uses will be added
6270 // to the beginning of the use list, which we avoid visiting.
6271 // This specifically avoids visiting uses of From that arise while the
6272 // replacement is happening, because any such uses would be the result
6273 // of CSE: If an existing node looks like From after one of its operands
6274 // is replaced by To, we don't want to replace of all its users with To
6275 // too. See PR3018 for more info.
6276 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6277 RAUWUpdateListener Listener(*this, UI, UE);
6281 // This node is about to morph, remove its old self from the CSE maps.
6282 RemoveNodeFromCSEMaps(User);
6284 // A user can appear in a use list multiple times, and when this
6285 // happens the uses are usually next to each other in the list.
6286 // To help reduce the number of CSE recomputations, process all
6287 // the uses of this user that we can find this way.
6289 SDUse &Use = UI.getUse();
6292 } while (UI != UE && *UI == User);
6294 // Now that we have modified User, add it back to the CSE maps. If it
6295 // already exists there, recursively merge the results together.
6296 AddModifiedNodeToCSEMaps(User);
6299 // If we just RAUW'd the root, take note.
6300 if (FromN == getRoot())
6304 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6305 /// This can cause recursive merging of nodes in the DAG.
6307 /// This version assumes that for each value of From, there is a
6308 /// corresponding value in To in the same position with the same type.
6310 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6312 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6313 assert((!From->hasAnyUseOfValue(i) ||
6314 From->getValueType(i) == To->getValueType(i)) &&
6315 "Cannot use this version of ReplaceAllUsesWith!");
6318 // Handle the trivial case.
6322 // Iterate over just the existing users of From. See the comments in
6323 // the ReplaceAllUsesWith above.
6324 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6325 RAUWUpdateListener Listener(*this, UI, UE);
6329 // This node is about to morph, remove its old self from the CSE maps.
6330 RemoveNodeFromCSEMaps(User);
6332 // A user can appear in a use list multiple times, and when this
6333 // happens the uses are usually next to each other in the list.
6334 // To help reduce the number of CSE recomputations, process all
6335 // the uses of this user that we can find this way.
6337 SDUse &Use = UI.getUse();
6340 } while (UI != UE && *UI == User);
6342 // Now that we have modified User, add it back to the CSE maps. If it
6343 // already exists there, recursively merge the results together.
6344 AddModifiedNodeToCSEMaps(User);
6347 // If we just RAUW'd the root, take note.
6348 if (From == getRoot().getNode())
6349 setRoot(SDValue(To, getRoot().getResNo()));
6352 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6353 /// This can cause recursive merging of nodes in the DAG.
6355 /// This version can replace From with any result values. To must match the
6356 /// number and types of values returned by From.
6357 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6358 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6359 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6361 // Iterate over just the existing users of From. See the comments in
6362 // the ReplaceAllUsesWith above.
6363 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6364 RAUWUpdateListener Listener(*this, UI, UE);
6368 // This node is about to morph, remove its old self from the CSE maps.
6369 RemoveNodeFromCSEMaps(User);
6371 // A user can appear in a use list multiple times, and when this
6372 // happens the uses are usually next to each other in the list.
6373 // To help reduce the number of CSE recomputations, process all
6374 // the uses of this user that we can find this way.
6376 SDUse &Use = UI.getUse();
6377 const SDValue &ToOp = To[Use.getResNo()];
6380 } while (UI != UE && *UI == User);
6382 // Now that we have modified User, add it back to the CSE maps. If it
6383 // already exists there, recursively merge the results together.
6384 AddModifiedNodeToCSEMaps(User);
6387 // If we just RAUW'd the root, take note.
6388 if (From == getRoot().getNode())
6389 setRoot(SDValue(To[getRoot().getResNo()]));
6392 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6393 /// uses of other values produced by From.getNode() alone. The Deleted
6394 /// vector is handled the same way as for ReplaceAllUsesWith.
6395 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6396 // Handle the really simple, really trivial case efficiently.
6397 if (From == To) return;
6399 // Handle the simple, trivial, case efficiently.
6400 if (From.getNode()->getNumValues() == 1) {
6401 ReplaceAllUsesWith(From, To);
6405 // Iterate over just the existing users of From. See the comments in
6406 // the ReplaceAllUsesWith above.
6407 SDNode::use_iterator UI = From.getNode()->use_begin(),
6408 UE = From.getNode()->use_end();
6409 RAUWUpdateListener Listener(*this, UI, UE);
6412 bool UserRemovedFromCSEMaps = false;
6414 // A user can appear in a use list multiple times, and when this
6415 // happens the uses are usually next to each other in the list.
6416 // To help reduce the number of CSE recomputations, process all
6417 // the uses of this user that we can find this way.
6419 SDUse &Use = UI.getUse();
6421 // Skip uses of different values from the same node.
6422 if (Use.getResNo() != From.getResNo()) {
6427 // If this node hasn't been modified yet, it's still in the CSE maps,
6428 // so remove its old self from the CSE maps.
6429 if (!UserRemovedFromCSEMaps) {
6430 RemoveNodeFromCSEMaps(User);
6431 UserRemovedFromCSEMaps = true;
6436 } while (UI != UE && *UI == User);
6438 // We are iterating over all uses of the From node, so if a use
6439 // doesn't use the specific value, no changes are made.
6440 if (!UserRemovedFromCSEMaps)
6443 // Now that we have modified User, add it back to the CSE maps. If it
6444 // already exists there, recursively merge the results together.
6445 AddModifiedNodeToCSEMaps(User);
6448 // If we just RAUW'd the root, take note.
6449 if (From == getRoot())
6454 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6455 /// to record information about a use.
6462 /// operator< - Sort Memos by User.
6463 bool operator<(const UseMemo &L, const UseMemo &R) {
6464 return (intptr_t)L.User < (intptr_t)R.User;
6468 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6469 /// uses of other values produced by From.getNode() alone. The same value
6470 /// may appear in both the From and To list. The Deleted vector is
6471 /// handled the same way as for ReplaceAllUsesWith.
6472 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6475 // Handle the simple, trivial case efficiently.
6477 return ReplaceAllUsesOfValueWith(*From, *To);
6479 // Read up all the uses and make records of them. This helps
6480 // processing new uses that are introduced during the
6481 // replacement process.
6482 SmallVector<UseMemo, 4> Uses;
6483 for (unsigned i = 0; i != Num; ++i) {
6484 unsigned FromResNo = From[i].getResNo();
6485 SDNode *FromNode = From[i].getNode();
6486 for (SDNode::use_iterator UI = FromNode->use_begin(),
6487 E = FromNode->use_end(); UI != E; ++UI) {
6488 SDUse &Use = UI.getUse();
6489 if (Use.getResNo() == FromResNo) {
6490 UseMemo Memo = { *UI, i, &Use };
6491 Uses.push_back(Memo);
6496 // Sort the uses, so that all the uses from a given User are together.
6497 std::sort(Uses.begin(), Uses.end());
6499 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6500 UseIndex != UseIndexEnd; ) {
6501 // We know that this user uses some value of From. If it is the right
6502 // value, update it.
6503 SDNode *User = Uses[UseIndex].User;
6505 // This node is about to morph, remove its old self from the CSE maps.
6506 RemoveNodeFromCSEMaps(User);
6508 // The Uses array is sorted, so all the uses for a given User
6509 // are next to each other in the list.
6510 // To help reduce the number of CSE recomputations, process all
6511 // the uses of this user that we can find this way.
6513 unsigned i = Uses[UseIndex].Index;
6514 SDUse &Use = *Uses[UseIndex].Use;
6518 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6520 // Now that we have modified User, add it back to the CSE maps. If it
6521 // already exists there, recursively merge the results together.
6522 AddModifiedNodeToCSEMaps(User);
6526 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6527 /// based on their topological order. It returns the maximum id and a vector
6528 /// of the SDNodes* in assigned order by reference.
6529 unsigned SelectionDAG::AssignTopologicalOrder() {
6531 unsigned DAGSize = 0;
6533 // SortedPos tracks the progress of the algorithm. Nodes before it are
6534 // sorted, nodes after it are unsorted. When the algorithm completes
6535 // it is at the end of the list.
6536 allnodes_iterator SortedPos = allnodes_begin();
6538 // Visit all the nodes. Move nodes with no operands to the front of
6539 // the list immediately. Annotate nodes that do have operands with their
6540 // operand count. Before we do this, the Node Id fields of the nodes
6541 // may contain arbitrary values. After, the Node Id fields for nodes
6542 // before SortedPos will contain the topological sort index, and the
6543 // Node Id fields for nodes At SortedPos and after will contain the
6544 // count of outstanding operands.
6545 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6547 checkForCycles(N, this);
6548 unsigned Degree = N->getNumOperands();
6550 // A node with no uses, add it to the result array immediately.
6551 N->setNodeId(DAGSize++);
6552 allnodes_iterator Q(N);
6554 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6555 assert(SortedPos != AllNodes.end() && "Overran node list");
6558 // Temporarily use the Node Id as scratch space for the degree count.
6559 N->setNodeId(Degree);
6563 // Visit all the nodes. As we iterate, move nodes into sorted order,
6564 // such that by the time the end is reached all nodes will be sorted.
6565 for (SDNode &Node : allnodes()) {
6567 checkForCycles(N, this);
6568 // N is in sorted position, so all its uses have one less operand
6569 // that needs to be sorted.
6570 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6573 unsigned Degree = P->getNodeId();
6574 assert(Degree != 0 && "Invalid node degree");
6577 // All of P's operands are sorted, so P may sorted now.
6578 P->setNodeId(DAGSize++);
6580 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6581 assert(SortedPos != AllNodes.end() && "Overran node list");
6584 // Update P's outstanding operand count.
6585 P->setNodeId(Degree);
6588 if (&Node == SortedPos) {
6590 allnodes_iterator I(N);
6592 dbgs() << "Overran sorted position:\n";
6593 S->dumprFull(this); dbgs() << "\n";
6594 dbgs() << "Checking if this is due to cycles\n";
6595 checkForCycles(this, true);
6597 llvm_unreachable(nullptr);
6601 assert(SortedPos == AllNodes.end() &&
6602 "Topological sort incomplete!");
6603 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6604 "First node in topological sort is not the entry token!");
6605 assert(AllNodes.front().getNodeId() == 0 &&
6606 "First node in topological sort has non-zero id!");
6607 assert(AllNodes.front().getNumOperands() == 0 &&
6608 "First node in topological sort has operands!");
6609 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6610 "Last node in topologic sort has unexpected id!");
6611 assert(AllNodes.back().use_empty() &&
6612 "Last node in topologic sort has users!");
6613 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6617 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6618 /// value is produced by SD.
6619 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6621 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6622 SD->setHasDebugValue(true);
6624 DbgInfo->add(DB, SD, isParameter);
6627 /// TransferDbgValues - Transfer SDDbgValues.
6628 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6629 if (From == To || !From.getNode()->getHasDebugValue())
6631 SDNode *FromNode = From.getNode();
6632 SDNode *ToNode = To.getNode();
6633 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6634 SmallVector<SDDbgValue *, 2> ClonedDVs;
6635 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6637 SDDbgValue *Dbg = *I;
6638 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6640 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6641 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6642 Dbg->getDebugLoc(), Dbg->getOrder());
6643 ClonedDVs.push_back(Clone);
6646 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6647 E = ClonedDVs.end(); I != E; ++I)
6648 AddDbgValue(*I, ToNode, false);
6651 //===----------------------------------------------------------------------===//
6653 //===----------------------------------------------------------------------===//
6655 HandleSDNode::~HandleSDNode() {
6659 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6660 DebugLoc DL, const GlobalValue *GA,
6661 EVT VT, int64_t o, unsigned char TF)
6662 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6666 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6667 SDValue X, unsigned SrcAS,
6669 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6670 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6672 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6673 EVT memvt, MachineMemOperand *mmo)
6674 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6675 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6676 MMO->isNonTemporal(), MMO->isInvariant());
6677 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6678 assert(isNonTemporal() == MMO->isNonTemporal() &&
6679 "Non-temporal encoding error!");
6680 // We check here that the size of the memory operand fits within the size of
6681 // the MMO. This is because the MMO might indicate only a possible address
6682 // range instead of specifying the affected memory addresses precisely.
6683 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6686 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6687 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6688 : SDNode(Opc, Order, dl, VTs, Ops),
6689 MemoryVT(memvt), MMO(mmo) {
6690 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6691 MMO->isNonTemporal(), MMO->isInvariant());
6692 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6693 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6696 /// Profile - Gather unique data for the node.
6698 void SDNode::Profile(FoldingSetNodeID &ID) const {
6699 AddNodeIDNode(ID, this);
6704 std::vector<EVT> VTs;
6707 VTs.reserve(MVT::LAST_VALUETYPE);
6708 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6709 VTs.push_back(MVT((MVT::SimpleValueType)i));
6714 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6715 static ManagedStatic<EVTArray> SimpleVTArray;
6716 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6718 /// getValueTypeList - Return a pointer to the specified value type.
6720 const EVT *SDNode::getValueTypeList(EVT VT) {
6721 if (VT.isExtended()) {
6722 sys::SmartScopedLock<true> Lock(*VTMutex);
6723 return &(*EVTs->insert(VT).first);
6725 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6726 "Value type out of range!");
6727 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6731 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6732 /// indicated value. This method ignores uses of other values defined by this
6734 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6735 assert(Value < getNumValues() && "Bad value!");
6737 // TODO: Only iterate over uses of a given value of the node
6738 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6739 if (UI.getUse().getResNo() == Value) {
6746 // Found exactly the right number of uses?
6751 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6752 /// value. This method ignores uses of other values defined by this operation.
6753 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6754 assert(Value < getNumValues() && "Bad value!");
6756 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6757 if (UI.getUse().getResNo() == Value)
6764 /// isOnlyUserOf - Return true if this node is the only use of N.
6766 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6768 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6779 /// isOperand - Return true if this node is an operand of N.
6781 bool SDValue::isOperandOf(const SDNode *N) const {
6782 for (const SDValue &Op : N->op_values())
6788 bool SDNode::isOperandOf(const SDNode *N) const {
6789 for (const SDValue &Op : N->op_values())
6790 if (this == Op.getNode())
6795 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6796 /// be a chain) reaches the specified operand without crossing any
6797 /// side-effecting instructions on any chain path. In practice, this looks
6798 /// through token factors and non-volatile loads. In order to remain efficient,
6799 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6800 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6801 unsigned Depth) const {
6802 if (*this == Dest) return true;
6804 // Don't search too deeply, we just want to be able to see through
6805 // TokenFactor's etc.
6806 if (Depth == 0) return false;
6808 // If this is a token factor, all inputs to the TF happen in parallel. If any
6809 // of the operands of the TF does not reach dest, then we cannot do the xform.
6810 if (getOpcode() == ISD::TokenFactor) {
6811 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6812 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6817 // Loads don't have side effects, look through them.
6818 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6819 if (!Ld->isVolatile())
6820 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6825 /// hasPredecessor - Return true if N is a predecessor of this node.
6826 /// N is either an operand of this node, or can be reached by recursively
6827 /// traversing up the operands.
6828 /// NOTE: This is an expensive method. Use it carefully.
6829 bool SDNode::hasPredecessor(const SDNode *N) const {
6830 SmallPtrSet<const SDNode *, 32> Visited;
6831 SmallVector<const SDNode *, 16> Worklist;
6832 return hasPredecessorHelper(N, Visited, Worklist);
6836 SDNode::hasPredecessorHelper(const SDNode *N,
6837 SmallPtrSetImpl<const SDNode *> &Visited,
6838 SmallVectorImpl<const SDNode *> &Worklist) const {
6839 if (Visited.empty()) {
6840 Worklist.push_back(this);
6842 // Take a look in the visited set. If we've already encountered this node
6843 // we needn't search further.
6844 if (Visited.count(N))
6848 // Haven't visited N yet. Continue the search.
6849 while (!Worklist.empty()) {
6850 const SDNode *M = Worklist.pop_back_val();
6851 for (const SDValue &OpV : M->op_values()) {
6852 SDNode *Op = OpV.getNode();
6853 if (Visited.insert(Op).second)
6854 Worklist.push_back(Op);
6863 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6864 assert(Num < NumOperands && "Invalid child # of SDNode!");
6865 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6868 const SDNodeFlags *SDNode::getFlags() const {
6869 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6870 return &FlagsNode->Flags;
6874 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6875 assert(N->getNumValues() == 1 &&
6876 "Can't unroll a vector with multiple results!");
6878 EVT VT = N->getValueType(0);
6879 unsigned NE = VT.getVectorNumElements();
6880 EVT EltVT = VT.getVectorElementType();
6883 SmallVector<SDValue, 8> Scalars;
6884 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6886 // If ResNE is 0, fully unroll the vector op.
6889 else if (NE > ResNE)
6893 for (i= 0; i != NE; ++i) {
6894 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6895 SDValue Operand = N->getOperand(j);
6896 EVT OperandVT = Operand.getValueType();
6897 if (OperandVT.isVector()) {
6898 // A vector operand; extract a single element.
6899 EVT OperandEltVT = OperandVT.getVectorElementType();
6901 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6902 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6904 // A scalar operand; just use it as is.
6905 Operands[j] = Operand;
6909 switch (N->getOpcode()) {
6911 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6916 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6923 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6924 getShiftAmountOperand(Operands[0].getValueType(),
6927 case ISD::SIGN_EXTEND_INREG:
6928 case ISD::FP_ROUND_INREG: {
6929 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6930 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6932 getValueType(ExtVT)));
6937 for (; i < ResNE; ++i)
6938 Scalars.push_back(getUNDEF(EltVT));
6940 return getNode(ISD::BUILD_VECTOR, dl,
6941 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6945 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6946 /// location that is 'Dist' units away from the location that the 'Base' load
6947 /// is loading from.
6948 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6949 unsigned Bytes, int Dist) const {
6950 if (LD->getChain() != Base->getChain())
6952 EVT VT = LD->getValueType(0);
6953 if (VT.getSizeInBits() / 8 != Bytes)
6956 SDValue Loc = LD->getOperand(1);
6957 SDValue BaseLoc = Base->getOperand(1);
6958 if (Loc.getOpcode() == ISD::FrameIndex) {
6959 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6961 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6962 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6963 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6964 int FS = MFI->getObjectSize(FI);
6965 int BFS = MFI->getObjectSize(BFI);
6966 if (FS != BFS || FS != (int)Bytes) return false;
6967 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6971 if (isBaseWithConstantOffset(Loc)) {
6972 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6973 if (Loc.getOperand(0) == BaseLoc) {
6974 // If the base location is a simple address with no offset itself, then
6975 // the second load's first add operand should be the base address.
6976 if (LocOffset == Dist * (int)Bytes)
6978 } else if (isBaseWithConstantOffset(BaseLoc)) {
6979 // The base location itself has an offset, so subtract that value from the
6980 // second load's offset before comparing to distance * size.
6982 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6983 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6984 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6989 const GlobalValue *GV1 = nullptr;
6990 const GlobalValue *GV2 = nullptr;
6991 int64_t Offset1 = 0;
6992 int64_t Offset2 = 0;
6993 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6994 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6995 if (isGA1 && isGA2 && GV1 == GV2)
6996 return Offset1 == (Offset2 + Dist*Bytes);
7001 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
7002 /// it cannot be inferred.
7003 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
7004 // If this is a GlobalAddress + cst, return the alignment.
7005 const GlobalValue *GV;
7006 int64_t GVOffset = 0;
7007 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
7008 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
7009 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
7010 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7012 unsigned AlignBits = KnownZero.countTrailingOnes();
7013 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7015 return MinAlign(Align, GVOffset);
7018 // If this is a direct reference to a stack slot, use information about the
7019 // stack slot's alignment.
7020 int FrameIdx = 1 << 31;
7021 int64_t FrameOffset = 0;
7022 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7023 FrameIdx = FI->getIndex();
7024 } else if (isBaseWithConstantOffset(Ptr) &&
7025 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7027 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7028 FrameOffset = Ptr.getConstantOperandVal(1);
7031 if (FrameIdx != (1 << 31)) {
7032 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7033 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7041 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7042 /// which is split (or expanded) into two not necessarily identical pieces.
7043 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7044 // Currently all types are split in half.
7046 if (!VT.isVector()) {
7047 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7049 unsigned NumElements = VT.getVectorNumElements();
7050 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7051 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7054 return std::make_pair(LoVT, HiVT);
7057 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7059 std::pair<SDValue, SDValue>
7060 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7062 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7063 N.getValueType().getVectorNumElements() &&
7064 "More vector elements requested than available!");
7066 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7067 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7068 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7069 getConstant(LoVT.getVectorNumElements(), DL,
7070 TLI->getVectorIdxTy(getDataLayout())));
7071 return std::make_pair(Lo, Hi);
7074 void SelectionDAG::ExtractVectorElements(SDValue Op,
7075 SmallVectorImpl<SDValue> &Args,
7076 unsigned Start, unsigned Count) {
7077 EVT VT = Op.getValueType();
7079 Count = VT.getVectorNumElements();
7081 EVT EltVT = VT.getVectorElementType();
7082 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7084 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7085 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7086 Op, getConstant(i, SL, IdxTy)));
7090 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7091 unsigned GlobalAddressSDNode::getAddressSpace() const {
7092 return getGlobal()->getType()->getAddressSpace();
7096 Type *ConstantPoolSDNode::getType() const {
7097 if (isMachineConstantPoolEntry())
7098 return Val.MachineCPVal->getType();
7099 return Val.ConstVal->getType();
7102 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7104 unsigned &SplatBitSize,
7106 unsigned MinSplatBits,
7107 bool isBigEndian) const {
7108 EVT VT = getValueType(0);
7109 assert(VT.isVector() && "Expected a vector type");
7110 unsigned sz = VT.getSizeInBits();
7111 if (MinSplatBits > sz)
7114 SplatValue = APInt(sz, 0);
7115 SplatUndef = APInt(sz, 0);
7117 // Get the bits. Bits with undefined values (when the corresponding element
7118 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7119 // in SplatValue. If any of the values are not constant, give up and return
7121 unsigned int nOps = getNumOperands();
7122 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7123 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7125 for (unsigned j = 0; j < nOps; ++j) {
7126 unsigned i = isBigEndian ? nOps-1-j : j;
7127 SDValue OpVal = getOperand(i);
7128 unsigned BitPos = j * EltBitSize;
7130 if (OpVal.getOpcode() == ISD::UNDEF)
7131 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7132 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7133 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7134 zextOrTrunc(sz) << BitPos;
7135 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7136 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7141 // The build_vector is all constants or undefs. Find the smallest element
7142 // size that splats the vector.
7144 HasAnyUndefs = (SplatUndef != 0);
7147 unsigned HalfSize = sz / 2;
7148 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7149 APInt LowValue = SplatValue.trunc(HalfSize);
7150 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7151 APInt LowUndef = SplatUndef.trunc(HalfSize);
7153 // If the two halves do not match (ignoring undef bits), stop here.
7154 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7155 MinSplatBits > HalfSize)
7158 SplatValue = HighValue | LowValue;
7159 SplatUndef = HighUndef & LowUndef;
7168 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7169 if (UndefElements) {
7170 UndefElements->clear();
7171 UndefElements->resize(getNumOperands());
7174 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7175 SDValue Op = getOperand(i);
7176 if (Op.getOpcode() == ISD::UNDEF) {
7178 (*UndefElements)[i] = true;
7179 } else if (!Splatted) {
7181 } else if (Splatted != Op) {
7187 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7188 "Can only have a splat without a constant for all undefs.");
7189 return getOperand(0);
7196 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7197 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7201 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7202 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7206 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7207 uint32_t BitWidth) const {
7208 if (ConstantFPSDNode *CN =
7209 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7211 APSInt IntVal(BitWidth);
7212 APFloat APF = CN->getValueAPF();
7213 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7218 return IntVal.exactLogBase2();
7223 bool BuildVectorSDNode::isConstant() const {
7224 for (const SDValue &Op : op_values()) {
7225 unsigned Opc = Op.getOpcode();
7226 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7232 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7233 // Find the first non-undef value in the shuffle mask.
7235 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7238 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7240 // Make sure all remaining elements are either undef or the same as the first
7242 for (int Idx = Mask[i]; i != e; ++i)
7243 if (Mask[i] >= 0 && Mask[i] != Idx)
7249 static void checkForCyclesHelper(const SDNode *N,
7250 SmallPtrSetImpl<const SDNode*> &Visited,
7251 SmallPtrSetImpl<const SDNode*> &Checked,
7252 const llvm::SelectionDAG *DAG) {
7253 // If this node has already been checked, don't check it again.
7254 if (Checked.count(N))
7257 // If a node has already been visited on this depth-first walk, reject it as
7259 if (!Visited.insert(N).second) {
7260 errs() << "Detected cycle in SelectionDAG\n";
7261 dbgs() << "Offending node:\n";
7262 N->dumprFull(DAG); dbgs() << "\n";
7266 for (const SDValue &Op : N->op_values())
7267 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7274 void llvm::checkForCycles(const llvm::SDNode *N,
7275 const llvm::SelectionDAG *DAG,
7283 assert(N && "Checking nonexistent SDNode");
7284 SmallPtrSet<const SDNode*, 32> visited;
7285 SmallPtrSet<const SDNode*, 32> checked;
7286 checkForCyclesHelper(N, visited, checked, DAG);
7291 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7292 checkForCycles(DAG->getRoot().getNode(), DAG, force);