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 bool SelectionDAG::haveNoCommonBitsSet(SDValue A, SDValue B) const {
2837 assert(A.getValueType() == B.getValueType() &&
2838 "Values must have the same type");
2841 computeKnownBits(A, AZero, AOne);
2842 computeKnownBits(B, BZero, BOne);
2843 return (AZero | BZero).isAllOnesValue();
2846 static SDValue FoldCONCAT_VECTORS(SDLoc DL, EVT VT, ArrayRef<SDValue> Ops,
2847 llvm::SelectionDAG &DAG) {
2848 if (Ops.size() == 1)
2851 // Concat of UNDEFs is UNDEF.
2852 if (std::all_of(Ops.begin(), Ops.end(),
2853 [](SDValue Op) { return Op.isUndef(); }))
2854 return DAG.getUNDEF(VT);
2856 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified
2857 // to one big BUILD_VECTOR.
2858 // FIXME: Add support for UNDEF and SCALAR_TO_VECTOR as well.
2859 if (!std::all_of(Ops.begin(), Ops.end(), [](SDValue Op) {
2860 return Op.getOpcode() == ISD::BUILD_VECTOR;
2864 EVT SVT = VT.getScalarType();
2865 SmallVector<SDValue, 16> Elts;
2866 for (SDValue Op : Ops)
2867 Elts.append(Op->op_begin(), Op->op_end());
2869 // BUILD_VECTOR requires all inputs to be of the same type, find the
2870 // maximum type and extend them all.
2871 for (SDValue Op : Elts)
2872 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
2874 if (SVT.bitsGT(VT.getScalarType()))
2875 for (SDValue &Op : Elts)
2876 Op = DAG.getTargetLoweringInfo().isZExtFree(Op.getValueType(), SVT)
2877 ? DAG.getZExtOrTrunc(Op, DL, SVT)
2878 : DAG.getSExtOrTrunc(Op, DL, SVT);
2880 return DAG.getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2883 /// getNode - Gets or creates the specified node.
2885 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2886 FoldingSetNodeID ID;
2887 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2889 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2890 return SDValue(E, 0);
2892 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2893 DL.getDebugLoc(), getVTList(VT));
2894 CSEMap.InsertNode(N, IP);
2897 return SDValue(N, 0);
2900 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2901 EVT VT, SDValue Operand) {
2902 // Constant fold unary operations with an integer constant operand. Even
2903 // opaque constant will be folded, because the folding of unary operations
2904 // doesn't create new constants with different values. Nevertheless, the
2905 // opaque flag is preserved during folding to prevent future folding with
2907 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2908 const APInt &Val = C->getAPIntValue();
2911 case ISD::SIGN_EXTEND:
2912 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2913 C->isTargetOpcode(), C->isOpaque());
2914 case ISD::ANY_EXTEND:
2915 case ISD::ZERO_EXTEND:
2917 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2918 C->isTargetOpcode(), C->isOpaque());
2919 case ISD::UINT_TO_FP:
2920 case ISD::SINT_TO_FP: {
2921 APFloat apf(EVTToAPFloatSemantics(VT),
2922 APInt::getNullValue(VT.getSizeInBits()));
2923 (void)apf.convertFromAPInt(Val,
2924 Opcode==ISD::SINT_TO_FP,
2925 APFloat::rmNearestTiesToEven);
2926 return getConstantFP(apf, DL, VT);
2929 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2930 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2931 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2932 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2933 if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2934 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2935 if (VT == MVT::f128 && C->getValueType(0) == MVT::i128)
2936 return getConstantFP(APFloat(APFloat::IEEEquad, Val), DL, VT);
2939 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2942 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2945 case ISD::CTLZ_ZERO_UNDEF:
2946 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2949 case ISD::CTTZ_ZERO_UNDEF:
2950 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2955 // Constant fold unary operations with a floating point constant operand.
2956 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2957 APFloat V = C->getValueAPF(); // make copy
2961 return getConstantFP(V, DL, VT);
2964 return getConstantFP(V, DL, VT);
2966 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2967 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2968 return getConstantFP(V, DL, VT);
2972 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2973 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2974 return getConstantFP(V, DL, VT);
2978 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2979 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2980 return getConstantFP(V, DL, VT);
2983 case ISD::FP_EXTEND: {
2985 // This can return overflow, underflow, or inexact; we don't care.
2986 // FIXME need to be more flexible about rounding mode.
2987 (void)V.convert(EVTToAPFloatSemantics(VT),
2988 APFloat::rmNearestTiesToEven, &ignored);
2989 return getConstantFP(V, DL, VT);
2991 case ISD::FP_TO_SINT:
2992 case ISD::FP_TO_UINT: {
2995 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2996 // FIXME need to be more flexible about rounding mode.
2997 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2998 Opcode==ISD::FP_TO_SINT,
2999 APFloat::rmTowardZero, &ignored);
3000 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
3002 APInt api(VT.getSizeInBits(), x);
3003 return getConstant(api, DL, VT);
3006 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
3007 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
3008 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
3009 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
3010 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
3011 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
3016 // Constant fold unary operations with a vector integer or float operand.
3017 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
3018 if (BV->isConstant()) {
3021 // FIXME: Entirely reasonable to perform folding of other unary
3022 // operations here as the need arises.
3029 case ISD::FP_EXTEND:
3030 case ISD::FP_TO_SINT:
3031 case ISD::FP_TO_UINT:
3033 case ISD::UINT_TO_FP:
3034 case ISD::SINT_TO_FP:
3037 case ISD::CTLZ_ZERO_UNDEF:
3039 case ISD::CTTZ_ZERO_UNDEF:
3041 SDValue Ops = { Operand };
3042 if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
3049 unsigned OpOpcode = Operand.getNode()->getOpcode();
3051 case ISD::TokenFactor:
3052 case ISD::MERGE_VALUES:
3053 case ISD::CONCAT_VECTORS:
3054 return Operand; // Factor, merge or concat of one node? No need.
3055 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3056 case ISD::FP_EXTEND:
3057 assert(VT.isFloatingPoint() &&
3058 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3059 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3060 assert((!VT.isVector() ||
3061 VT.getVectorNumElements() ==
3062 Operand.getValueType().getVectorNumElements()) &&
3063 "Vector element count mismatch!");
3064 assert(Operand.getValueType().bitsLT(VT) &&
3065 "Invalid fpext node, dst < src!");
3066 if (Operand.getOpcode() == ISD::UNDEF)
3067 return getUNDEF(VT);
3069 case ISD::SIGN_EXTEND:
3070 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3071 "Invalid SIGN_EXTEND!");
3072 if (Operand.getValueType() == VT) return Operand; // noop extension
3073 assert((!VT.isVector() ||
3074 VT.getVectorNumElements() ==
3075 Operand.getValueType().getVectorNumElements()) &&
3076 "Vector element count mismatch!");
3077 assert(Operand.getValueType().bitsLT(VT) &&
3078 "Invalid sext node, dst < src!");
3079 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3080 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3081 else if (OpOpcode == ISD::UNDEF)
3082 // sext(undef) = 0, because the top bits will all be the same.
3083 return getConstant(0, DL, VT);
3085 case ISD::ZERO_EXTEND:
3086 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3087 "Invalid ZERO_EXTEND!");
3088 if (Operand.getValueType() == VT) return Operand; // noop extension
3089 assert((!VT.isVector() ||
3090 VT.getVectorNumElements() ==
3091 Operand.getValueType().getVectorNumElements()) &&
3092 "Vector element count mismatch!");
3093 assert(Operand.getValueType().bitsLT(VT) &&
3094 "Invalid zext node, dst < src!");
3095 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3096 return getNode(ISD::ZERO_EXTEND, DL, VT,
3097 Operand.getNode()->getOperand(0));
3098 else if (OpOpcode == ISD::UNDEF)
3099 // zext(undef) = 0, because the top bits will be zero.
3100 return getConstant(0, DL, VT);
3102 case ISD::ANY_EXTEND:
3103 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3104 "Invalid ANY_EXTEND!");
3105 if (Operand.getValueType() == VT) return Operand; // noop extension
3106 assert((!VT.isVector() ||
3107 VT.getVectorNumElements() ==
3108 Operand.getValueType().getVectorNumElements()) &&
3109 "Vector element count mismatch!");
3110 assert(Operand.getValueType().bitsLT(VT) &&
3111 "Invalid anyext node, dst < src!");
3113 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3114 OpOpcode == ISD::ANY_EXTEND)
3115 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3116 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3117 else if (OpOpcode == ISD::UNDEF)
3118 return getUNDEF(VT);
3120 // (ext (trunx x)) -> x
3121 if (OpOpcode == ISD::TRUNCATE) {
3122 SDValue OpOp = Operand.getNode()->getOperand(0);
3123 if (OpOp.getValueType() == VT)
3128 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3129 "Invalid TRUNCATE!");
3130 if (Operand.getValueType() == VT) return Operand; // noop truncate
3131 assert((!VT.isVector() ||
3132 VT.getVectorNumElements() ==
3133 Operand.getValueType().getVectorNumElements()) &&
3134 "Vector element count mismatch!");
3135 assert(Operand.getValueType().bitsGT(VT) &&
3136 "Invalid truncate node, src < dst!");
3137 if (OpOpcode == ISD::TRUNCATE)
3138 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3139 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3140 OpOpcode == ISD::ANY_EXTEND) {
3141 // If the source is smaller than the dest, we still need an extend.
3142 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3143 .bitsLT(VT.getScalarType()))
3144 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3145 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3146 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3147 return Operand.getNode()->getOperand(0);
3149 if (OpOpcode == ISD::UNDEF)
3150 return getUNDEF(VT);
3153 assert(VT.isInteger() && VT == Operand.getValueType() &&
3155 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3156 "BSWAP types must be a multiple of 16 bits!");
3157 if (OpOpcode == ISD::UNDEF)
3158 return getUNDEF(VT);
3161 // Basic sanity checking.
3162 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3163 && "Cannot BITCAST between types of different sizes!");
3164 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3165 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3166 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3167 if (OpOpcode == ISD::UNDEF)
3168 return getUNDEF(VT);
3170 case ISD::SCALAR_TO_VECTOR:
3171 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3172 (VT.getVectorElementType() == Operand.getValueType() ||
3173 (VT.getVectorElementType().isInteger() &&
3174 Operand.getValueType().isInteger() &&
3175 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3176 "Illegal SCALAR_TO_VECTOR node!");
3177 if (OpOpcode == ISD::UNDEF)
3178 return getUNDEF(VT);
3179 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3180 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3181 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3182 Operand.getConstantOperandVal(1) == 0 &&
3183 Operand.getOperand(0).getValueType() == VT)
3184 return Operand.getOperand(0);
3187 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3188 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3189 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3190 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3191 Operand.getNode()->getOperand(0),
3192 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3193 if (OpOpcode == ISD::FNEG) // --X -> X
3194 return Operand.getNode()->getOperand(0);
3197 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3198 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3203 SDVTList VTs = getVTList(VT);
3204 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3205 FoldingSetNodeID ID;
3206 SDValue Ops[1] = { Operand };
3207 AddNodeIDNode(ID, Opcode, VTs, Ops);
3209 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3210 return SDValue(E, 0);
3212 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3213 DL.getDebugLoc(), VTs, Operand);
3214 CSEMap.InsertNode(N, IP);
3216 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3217 DL.getDebugLoc(), VTs, Operand);
3221 return SDValue(N, 0);
3224 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3227 case ISD::ADD: return std::make_pair(C1 + C2, true);
3228 case ISD::SUB: return std::make_pair(C1 - C2, true);
3229 case ISD::MUL: return std::make_pair(C1 * C2, true);
3230 case ISD::AND: return std::make_pair(C1 & C2, true);
3231 case ISD::OR: return std::make_pair(C1 | C2, true);
3232 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3233 case ISD::SHL: return std::make_pair(C1 << C2, true);
3234 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3235 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3236 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3237 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3238 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3239 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3240 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3241 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3243 if (!C2.getBoolValue())
3245 return std::make_pair(C1.udiv(C2), true);
3247 if (!C2.getBoolValue())
3249 return std::make_pair(C1.urem(C2), true);
3251 if (!C2.getBoolValue())
3253 return std::make_pair(C1.sdiv(C2), true);
3255 if (!C2.getBoolValue())
3257 return std::make_pair(C1.srem(C2), true);
3259 return std::make_pair(APInt(1, 0), false);
3262 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3263 const ConstantSDNode *Cst1,
3264 const ConstantSDNode *Cst2) {
3265 if (Cst1->isOpaque() || Cst2->isOpaque())
3268 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3269 Cst2->getAPIntValue());
3272 return getConstant(Folded.first, DL, VT);
3275 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3276 SDNode *Cst1, SDNode *Cst2) {
3277 // If the opcode is a target-specific ISD node, there's nothing we can
3278 // do here and the operand rules may not line up with the below, so
3280 if (Opcode >= ISD::BUILTIN_OP_END)
3283 // Handle the case of two scalars.
3284 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3285 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3286 if (SDValue Folded =
3287 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3290 SmallVector<SDValue, 4> Outputs;
3291 // We may have a vector type but a scalar result. Create a splat.
3292 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3293 // Build a big vector out of the scalar elements we generated.
3294 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3301 // For vectors extract each constant element into Inputs so we can constant
3302 // fold them individually.
3303 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3304 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3308 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3310 EVT SVT = VT.getScalarType();
3311 SmallVector<SDValue, 4> Outputs;
3312 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3313 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3314 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3315 if (!V1 || !V2) // Not a constant, bail.
3318 if (V1->isOpaque() || V2->isOpaque())
3321 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3322 // FIXME: This is valid and could be handled by truncating the APInts.
3323 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3326 // Fold one vector element.
3327 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3328 V2->getAPIntValue());
3331 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3334 assert(VT.getVectorNumElements() == Outputs.size() &&
3335 "Vector size mismatch!");
3337 // We may have a vector type but a scalar result. Create a splat.
3338 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3340 // Build a big vector out of the scalar elements we generated.
3341 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3344 SDValue SelectionDAG::FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
3346 ArrayRef<SDValue> Ops,
3347 const SDNodeFlags *Flags) {
3348 // If the opcode is a target-specific ISD node, there's nothing we can
3349 // do here and the operand rules may not line up with the below, so
3351 if (Opcode >= ISD::BUILTIN_OP_END)
3354 // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
3358 unsigned NumElts = VT.getVectorNumElements();
3360 auto IsScalarOrSameVectorSize = [&](const SDValue &Op) {
3361 return !Op.getValueType().isVector() ||
3362 Op.getValueType().getVectorNumElements() == NumElts;
3365 auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
3366 BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Op);
3367 return (Op.getOpcode() == ISD::UNDEF) ||
3368 (Op.getOpcode() == ISD::CONDCODE) || (BV && BV->isConstant());
3371 // All operands must be vector types with the same number of elements as
3372 // the result type and must be either UNDEF or a build vector of constant
3373 // or UNDEF scalars.
3374 if (!std::all_of(Ops.begin(), Ops.end(), IsConstantBuildVectorOrUndef) ||
3375 !std::all_of(Ops.begin(), Ops.end(), IsScalarOrSameVectorSize))
3378 // If we are comparing vectors, then the result needs to be a i1 boolean
3379 // that is then sign-extended back to the legal result type.
3380 EVT SVT = (Opcode == ISD::SETCC ? MVT::i1 : VT.getScalarType());
3382 // Find legal integer scalar type for constant promotion and
3383 // ensure that its scalar size is at least as large as source.
3384 EVT LegalSVT = VT.getScalarType();
3385 if (LegalSVT.isInteger()) {
3386 LegalSVT = TLI->getTypeToTransformTo(*getContext(), LegalSVT);
3387 if (LegalSVT.bitsLT(SVT))
3391 // Constant fold each scalar lane separately.
3392 SmallVector<SDValue, 4> ScalarResults;
3393 for (unsigned i = 0; i != NumElts; i++) {
3394 SmallVector<SDValue, 4> ScalarOps;
3395 for (SDValue Op : Ops) {
3396 EVT InSVT = Op.getValueType().getScalarType();
3397 BuildVectorSDNode *InBV = dyn_cast<BuildVectorSDNode>(Op);
3399 // We've checked that this is UNDEF or a constant of some kind.
3401 ScalarOps.push_back(getUNDEF(InSVT));
3403 ScalarOps.push_back(Op);
3407 SDValue ScalarOp = InBV->getOperand(i);
3408 EVT ScalarVT = ScalarOp.getValueType();
3410 // Build vector (integer) scalar operands may need implicit
3411 // truncation - do this before constant folding.
3412 if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
3413 ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
3415 ScalarOps.push_back(ScalarOp);
3418 // Constant fold the scalar operands.
3419 SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
3421 // Legalize the (integer) scalar constant if necessary.
3422 if (LegalSVT != SVT)
3423 ScalarResult = getNode(ISD::SIGN_EXTEND, DL, LegalSVT, ScalarResult);
3425 // Scalar folding only succeeded if the result is a constant or UNDEF.
3426 if (ScalarResult.getOpcode() != ISD::UNDEF &&
3427 ScalarResult.getOpcode() != ISD::Constant &&
3428 ScalarResult.getOpcode() != ISD::ConstantFP)
3430 ScalarResults.push_back(ScalarResult);
3433 assert(ScalarResults.size() == NumElts &&
3434 "Unexpected number of scalar results for BUILD_VECTOR");
3435 return getNode(ISD::BUILD_VECTOR, DL, VT, ScalarResults);
3438 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3439 SDValue N2, const SDNodeFlags *Flags) {
3440 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3441 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3442 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3443 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3445 // Canonicalize constant to RHS if commutative.
3446 if (isCommutativeBinOp(Opcode)) {
3448 std::swap(N1C, N2C);
3450 } else if (N1CFP && !N2CFP) {
3451 std::swap(N1CFP, N2CFP);
3458 case ISD::TokenFactor:
3459 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3460 N2.getValueType() == MVT::Other && "Invalid token factor!");
3461 // Fold trivial token factors.
3462 if (N1.getOpcode() == ISD::EntryToken) return N2;
3463 if (N2.getOpcode() == ISD::EntryToken) return N1;
3464 if (N1 == N2) return N1;
3466 case ISD::CONCAT_VECTORS: {
3467 // Attempt to fold CONCAT_VECTORS into BUILD_VECTOR or UNDEF.
3468 SDValue Ops[] = {N1, N2};
3469 if (SDValue V = FoldCONCAT_VECTORS(DL, VT, Ops, *this))
3474 assert(VT.isInteger() && "This operator does not apply to FP types!");
3475 assert(N1.getValueType() == N2.getValueType() &&
3476 N1.getValueType() == VT && "Binary operator types must match!");
3477 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3478 // worth handling here.
3479 if (N2C && N2C->isNullValue())
3481 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3488 assert(VT.isInteger() && "This operator does not apply to FP types!");
3489 assert(N1.getValueType() == N2.getValueType() &&
3490 N1.getValueType() == VT && "Binary operator types must match!");
3491 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3492 // it's worth handling here.
3493 if (N2C && N2C->isNullValue())
3507 assert(VT.isInteger() && "This operator does not apply to FP types!");
3508 assert(N1.getValueType() == N2.getValueType() &&
3509 N1.getValueType() == VT && "Binary operator types must match!");
3516 if (getTarget().Options.UnsafeFPMath) {
3517 if (Opcode == ISD::FADD) {
3519 if (N2CFP && N2CFP->getValueAPF().isZero())
3521 } else if (Opcode == ISD::FSUB) {
3523 if (N2CFP && N2CFP->getValueAPF().isZero())
3525 } else if (Opcode == ISD::FMUL) {
3527 if (N2CFP && N2CFP->isZero())
3530 if (N2CFP && N2CFP->isExactlyValue(1.0))
3534 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3535 assert(N1.getValueType() == N2.getValueType() &&
3536 N1.getValueType() == VT && "Binary operator types must match!");
3538 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3539 assert(N1.getValueType() == VT &&
3540 N1.getValueType().isFloatingPoint() &&
3541 N2.getValueType().isFloatingPoint() &&
3542 "Invalid FCOPYSIGN!");
3549 assert(VT == N1.getValueType() &&
3550 "Shift operators return type must be the same as their first arg");
3551 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3552 "Shifts only work on integers");
3553 assert((!VT.isVector() || VT == N2.getValueType()) &&
3554 "Vector shift amounts must be in the same as their first arg");
3555 // Verify that the shift amount VT is bit enough to hold valid shift
3556 // amounts. This catches things like trying to shift an i1024 value by an
3557 // i8, which is easy to fall into in generic code that uses
3558 // TLI.getShiftAmount().
3559 assert(N2.getValueType().getSizeInBits() >=
3560 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3561 "Invalid use of small shift amount with oversized value!");
3563 // Always fold shifts of i1 values so the code generator doesn't need to
3564 // handle them. Since we know the size of the shift has to be less than the
3565 // size of the value, the shift/rotate count is guaranteed to be zero.
3568 if (N2C && N2C->isNullValue())
3571 case ISD::FP_ROUND_INREG: {
3572 EVT EVT = cast<VTSDNode>(N2)->getVT();
3573 assert(VT == N1.getValueType() && "Not an inreg round!");
3574 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3575 "Cannot FP_ROUND_INREG integer types");
3576 assert(EVT.isVector() == VT.isVector() &&
3577 "FP_ROUND_INREG type should be vector iff the operand "
3579 assert((!EVT.isVector() ||
3580 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3581 "Vector element counts must match in FP_ROUND_INREG");
3582 assert(EVT.bitsLE(VT) && "Not rounding down!");
3584 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3588 assert(VT.isFloatingPoint() &&
3589 N1.getValueType().isFloatingPoint() &&
3590 VT.bitsLE(N1.getValueType()) &&
3591 N2C && "Invalid FP_ROUND!");
3592 if (N1.getValueType() == VT) return N1; // noop conversion.
3594 case ISD::AssertSext:
3595 case ISD::AssertZext: {
3596 EVT EVT = cast<VTSDNode>(N2)->getVT();
3597 assert(VT == N1.getValueType() && "Not an inreg extend!");
3598 assert(VT.isInteger() && EVT.isInteger() &&
3599 "Cannot *_EXTEND_INREG FP types");
3600 assert(!EVT.isVector() &&
3601 "AssertSExt/AssertZExt type should be the vector element type "
3602 "rather than the vector type!");
3603 assert(EVT.bitsLE(VT) && "Not extending!");
3604 if (VT == EVT) return N1; // noop assertion.
3607 case ISD::SIGN_EXTEND_INREG: {
3608 EVT EVT = cast<VTSDNode>(N2)->getVT();
3609 assert(VT == N1.getValueType() && "Not an inreg extend!");
3610 assert(VT.isInteger() && EVT.isInteger() &&
3611 "Cannot *_EXTEND_INREG FP types");
3612 assert(EVT.isVector() == VT.isVector() &&
3613 "SIGN_EXTEND_INREG type should be vector iff the operand "
3615 assert((!EVT.isVector() ||
3616 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3617 "Vector element counts must match in SIGN_EXTEND_INREG");
3618 assert(EVT.bitsLE(VT) && "Not extending!");
3619 if (EVT == VT) return N1; // Not actually extending
3621 auto SignExtendInReg = [&](APInt Val) {
3622 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3623 Val <<= Val.getBitWidth() - FromBits;
3624 Val = Val.ashr(Val.getBitWidth() - FromBits);
3625 return getConstant(Val, DL, VT.getScalarType());
3629 APInt Val = N1C->getAPIntValue();
3630 return SignExtendInReg(Val);
3632 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3633 SmallVector<SDValue, 8> Ops;
3634 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3635 SDValue Op = N1.getOperand(i);
3636 if (Op.getOpcode() == ISD::UNDEF) {
3637 Ops.push_back(getUNDEF(VT.getScalarType()));
3640 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3641 APInt Val = C->getAPIntValue();
3642 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3643 Ops.push_back(SignExtendInReg(Val));
3648 if (Ops.size() == VT.getVectorNumElements())
3649 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3653 case ISD::EXTRACT_VECTOR_ELT:
3654 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3655 if (N1.getOpcode() == ISD::UNDEF)
3656 return getUNDEF(VT);
3658 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3659 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3660 return getUNDEF(VT);
3662 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3663 // expanding copies of large vectors from registers.
3665 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3666 N1.getNumOperands() > 0) {
3668 N1.getOperand(0).getValueType().getVectorNumElements();
3669 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3670 N1.getOperand(N2C->getZExtValue() / Factor),
3671 getConstant(N2C->getZExtValue() % Factor, DL,
3672 N2.getValueType()));
3675 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3676 // expanding large vector constants.
3677 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3678 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3680 if (VT != Elt.getValueType())
3681 // If the vector element type is not legal, the BUILD_VECTOR operands
3682 // are promoted and implicitly truncated, and the result implicitly
3683 // extended. Make that explicit here.
3684 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3689 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3690 // operations are lowered to scalars.
3691 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3692 // If the indices are the same, return the inserted element else
3693 // if the indices are known different, extract the element from
3694 // the original vector.
3695 SDValue N1Op2 = N1.getOperand(2);
3696 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3698 if (N1Op2C && N2C) {
3699 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3700 if (VT == N1.getOperand(1).getValueType())
3701 return N1.getOperand(1);
3703 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3706 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3710 case ISD::EXTRACT_ELEMENT:
3711 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3712 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3713 (N1.getValueType().isInteger() == VT.isInteger()) &&
3714 N1.getValueType() != VT &&
3715 "Wrong types for EXTRACT_ELEMENT!");
3717 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3718 // 64-bit integers into 32-bit parts. Instead of building the extract of
3719 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3720 if (N1.getOpcode() == ISD::BUILD_PAIR)
3721 return N1.getOperand(N2C->getZExtValue());
3723 // EXTRACT_ELEMENT of a constant int is also very common.
3725 unsigned ElementSize = VT.getSizeInBits();
3726 unsigned Shift = ElementSize * N2C->getZExtValue();
3727 APInt ShiftedVal = N1C->getAPIntValue().lshr(Shift);
3728 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3731 case ISD::EXTRACT_SUBVECTOR:
3732 if (VT.isSimple() && N1.getValueType().isSimple()) {
3733 assert(VT.isVector() && N1.getValueType().isVector() &&
3734 "Extract subvector VTs must be a vectors!");
3735 assert(VT.getVectorElementType() ==
3736 N1.getValueType().getVectorElementType() &&
3737 "Extract subvector VTs must have the same element type!");
3738 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3739 "Extract subvector must be from larger vector to smaller vector!");
3742 assert((VT.getVectorNumElements() + N2C->getZExtValue()
3743 <= N1.getValueType().getVectorNumElements())
3744 && "Extract subvector overflow!");
3747 // Trivial extraction.
3748 if (VT.getSimpleVT() == N1.getSimpleValueType())
3754 // Perform trivial constant folding.
3756 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3759 // Constant fold FP operations.
3760 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3763 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3764 APFloat::opStatus s;
3767 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3768 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3769 return getConstantFP(V1, DL, VT);
3772 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3773 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3774 return getConstantFP(V1, DL, VT);
3777 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3778 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3779 return getConstantFP(V1, DL, VT);
3782 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3783 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3784 s!=APFloat::opDivByZero)) {
3785 return getConstantFP(V1, DL, VT);
3790 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3791 s!=APFloat::opDivByZero)) {
3792 return getConstantFP(V1, DL, VT);
3795 case ISD::FCOPYSIGN:
3797 return getConstantFP(V1, DL, VT);
3802 if (Opcode == ISD::FP_ROUND) {
3803 APFloat V = N1CFP->getValueAPF(); // make copy
3805 // This can return overflow, underflow, or inexact; we don't care.
3806 // FIXME need to be more flexible about rounding mode.
3807 (void)V.convert(EVTToAPFloatSemantics(VT),
3808 APFloat::rmNearestTiesToEven, &ignored);
3809 return getConstantFP(V, DL, VT);
3813 // Canonicalize an UNDEF to the RHS, even over a constant.
3814 if (N1.getOpcode() == ISD::UNDEF) {
3815 if (isCommutativeBinOp(Opcode)) {
3819 case ISD::FP_ROUND_INREG:
3820 case ISD::SIGN_EXTEND_INREG:
3826 return N1; // fold op(undef, arg2) -> undef
3834 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3835 // For vectors, we can't easily build an all zero vector, just return
3842 // Fold a bunch of operators when the RHS is undef.
3843 if (N2.getOpcode() == ISD::UNDEF) {
3846 if (N1.getOpcode() == ISD::UNDEF)
3847 // Handle undef ^ undef -> 0 special case. This is a common
3849 return getConstant(0, DL, VT);
3859 return N2; // fold op(arg1, undef) -> undef
3865 if (getTarget().Options.UnsafeFPMath)
3873 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3874 // For vectors, we can't easily build an all zero vector, just return
3879 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3880 // For vectors, we can't easily build an all one vector, just return
3888 // Memoize this node if possible.
3890 SDVTList VTs = getVTList(VT);
3891 if (VT != MVT::Glue) {
3892 SDValue Ops[] = {N1, N2};
3893 FoldingSetNodeID ID;
3894 AddNodeIDNode(ID, Opcode, VTs, Ops);
3895 AddNodeIDFlags(ID, Opcode, Flags);
3897 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3898 return SDValue(E, 0);
3900 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3902 CSEMap.InsertNode(N, IP);
3904 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3908 return SDValue(N, 0);
3911 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3912 SDValue N1, SDValue N2, SDValue N3) {
3913 // Perform various simplifications.
3916 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3917 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3918 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3919 if (N1CFP && N2CFP && N3CFP) {
3920 APFloat V1 = N1CFP->getValueAPF();
3921 const APFloat &V2 = N2CFP->getValueAPF();
3922 const APFloat &V3 = N3CFP->getValueAPF();
3923 APFloat::opStatus s =
3924 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3925 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3926 return getConstantFP(V1, DL, VT);
3930 case ISD::CONCAT_VECTORS: {
3931 // Attempt to fold CONCAT_VECTORS into BUILD_VECTOR or UNDEF.
3932 SDValue Ops[] = {N1, N2, N3};
3933 if (SDValue V = FoldCONCAT_VECTORS(DL, VT, Ops, *this))
3938 // Use FoldSetCC to simplify SETCC's.
3939 if (SDValue V = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL))
3941 // Vector constant folding.
3942 SDValue Ops[] = {N1, N2, N3};
3943 if (SDValue V = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
3948 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
3949 if (N1C->getZExtValue())
3950 return N2; // select true, X, Y -> X
3951 return N3; // select false, X, Y -> Y
3954 if (N2 == N3) return N2; // select C, X, X -> X
3956 case ISD::VECTOR_SHUFFLE:
3957 llvm_unreachable("should use getVectorShuffle constructor!");
3958 case ISD::INSERT_SUBVECTOR: {
3960 if (VT.isSimple() && N1.getValueType().isSimple()
3961 && N2.getValueType().isSimple()) {
3962 assert(VT.isVector() && N1.getValueType().isVector() &&
3963 N2.getValueType().isVector() &&
3964 "Insert subvector VTs must be a vectors");
3965 assert(VT == N1.getValueType() &&
3966 "Dest and insert subvector source types must match!");
3967 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3968 "Insert subvector must be from smaller vector to larger vector!");
3969 if (isa<ConstantSDNode>(Index)) {
3970 assert((N2.getValueType().getVectorNumElements() +
3971 cast<ConstantSDNode>(Index)->getZExtValue()
3972 <= VT.getVectorNumElements())
3973 && "Insert subvector overflow!");
3976 // Trivial insertion.
3977 if (VT.getSimpleVT() == N2.getSimpleValueType())
3983 // Fold bit_convert nodes from a type to themselves.
3984 if (N1.getValueType() == VT)
3989 // Memoize node if it doesn't produce a flag.
3991 SDVTList VTs = getVTList(VT);
3992 if (VT != MVT::Glue) {
3993 SDValue Ops[] = { N1, N2, N3 };
3994 FoldingSetNodeID ID;
3995 AddNodeIDNode(ID, Opcode, VTs, Ops);
3997 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3998 return SDValue(E, 0);
4000 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4001 DL.getDebugLoc(), VTs, N1, N2, N3);
4002 CSEMap.InsertNode(N, IP);
4004 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4005 DL.getDebugLoc(), VTs, N1, N2, N3);
4009 return SDValue(N, 0);
4012 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4013 SDValue N1, SDValue N2, SDValue N3,
4015 SDValue Ops[] = { N1, N2, N3, N4 };
4016 return getNode(Opcode, DL, VT, Ops);
4019 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4020 SDValue N1, SDValue N2, SDValue N3,
4021 SDValue N4, SDValue N5) {
4022 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4023 return getNode(Opcode, DL, VT, Ops);
4026 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
4027 /// the incoming stack arguments to be loaded from the stack.
4028 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
4029 SmallVector<SDValue, 8> ArgChains;
4031 // Include the original chain at the beginning of the list. When this is
4032 // used by target LowerCall hooks, this helps legalize find the
4033 // CALLSEQ_BEGIN node.
4034 ArgChains.push_back(Chain);
4036 // Add a chain value for each stack argument.
4037 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
4038 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
4039 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
4040 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
4041 if (FI->getIndex() < 0)
4042 ArgChains.push_back(SDValue(L, 1));
4044 // Build a tokenfactor for all the chains.
4045 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4048 /// getMemsetValue - Vectorized representation of the memset value
4050 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4052 assert(Value.getOpcode() != ISD::UNDEF);
4054 unsigned NumBits = VT.getScalarType().getSizeInBits();
4055 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4056 assert(C->getAPIntValue().getBitWidth() == 8);
4057 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4059 return DAG.getConstant(Val, dl, VT);
4060 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4064 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4065 EVT IntVT = VT.getScalarType();
4066 if (!IntVT.isInteger())
4067 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4069 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4071 // Use a multiplication with 0x010101... to extend the input to the
4073 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4074 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4075 DAG.getConstant(Magic, dl, IntVT));
4078 if (VT != Value.getValueType() && !VT.isInteger())
4079 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4080 if (VT != Value.getValueType()) {
4081 assert(VT.getVectorElementType() == Value.getValueType() &&
4082 "value type should be one vector element here");
4083 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4084 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4090 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4091 /// used when a memcpy is turned into a memset when the source is a constant
4093 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4094 const TargetLowering &TLI, StringRef Str) {
4095 // Handle vector with all elements zero.
4098 return DAG.getConstant(0, dl, VT);
4099 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4100 return DAG.getConstantFP(0.0, dl, VT);
4101 else if (VT.isVector()) {
4102 unsigned NumElts = VT.getVectorNumElements();
4103 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4104 return DAG.getNode(ISD::BITCAST, dl, VT,
4105 DAG.getConstant(0, dl,
4106 EVT::getVectorVT(*DAG.getContext(),
4109 llvm_unreachable("Expected type!");
4112 assert(!VT.isVector() && "Can't handle vector type here!");
4113 unsigned NumVTBits = VT.getSizeInBits();
4114 unsigned NumVTBytes = NumVTBits / 8;
4115 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4117 APInt Val(NumVTBits, 0);
4118 if (DAG.getDataLayout().isLittleEndian()) {
4119 for (unsigned i = 0; i != NumBytes; ++i)
4120 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4122 for (unsigned i = 0; i != NumBytes; ++i)
4123 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4126 // If the "cost" of materializing the integer immediate is less than the cost
4127 // of a load, then it is cost effective to turn the load into the immediate.
4128 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4129 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4130 return DAG.getConstant(Val, dl, VT);
4131 return SDValue(nullptr, 0);
4134 /// getMemBasePlusOffset - Returns base and offset node for the
4136 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4137 SelectionDAG &DAG) {
4138 EVT VT = Base.getValueType();
4139 return DAG.getNode(ISD::ADD, dl,
4140 VT, Base, DAG.getConstant(Offset, dl, VT));
4143 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4145 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4146 unsigned SrcDelta = 0;
4147 GlobalAddressSDNode *G = nullptr;
4148 if (Src.getOpcode() == ISD::GlobalAddress)
4149 G = cast<GlobalAddressSDNode>(Src);
4150 else if (Src.getOpcode() == ISD::ADD &&
4151 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4152 Src.getOperand(1).getOpcode() == ISD::Constant) {
4153 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4154 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4159 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4162 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4163 /// Return true if the number of memory ops is below the threshold (Limit).
4164 /// It returns the types of the sequence of memory ops to perform
4165 /// memset / memcpy by reference.
4166 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4167 unsigned Limit, uint64_t Size,
4168 unsigned DstAlign, unsigned SrcAlign,
4174 const TargetLowering &TLI) {
4175 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4176 "Expecting memcpy / memset source to meet alignment requirement!");
4177 // If 'SrcAlign' is zero, that means the memory operation does not need to
4178 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4179 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4180 // is the specified alignment of the memory operation. If it is zero, that
4181 // means it's possible to change the alignment of the destination.
4182 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4183 // not need to be loaded.
4184 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4185 IsMemset, ZeroMemset, MemcpyStrSrc,
4186 DAG.getMachineFunction());
4188 if (VT == MVT::Other) {
4190 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4191 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4192 VT = TLI.getPointerTy(DAG.getDataLayout());
4194 switch (DstAlign & 7) {
4195 case 0: VT = MVT::i64; break;
4196 case 4: VT = MVT::i32; break;
4197 case 2: VT = MVT::i16; break;
4198 default: VT = MVT::i8; break;
4203 while (!TLI.isTypeLegal(LVT))
4204 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4205 assert(LVT.isInteger());
4211 unsigned NumMemOps = 0;
4213 unsigned VTSize = VT.getSizeInBits() / 8;
4214 while (VTSize > Size) {
4215 // For now, only use non-vector load / store's for the left-over pieces.
4220 if (VT.isVector() || VT.isFloatingPoint()) {
4221 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4222 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4223 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4225 else if (NewVT == MVT::i64 &&
4226 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4227 TLI.isSafeMemOpType(MVT::f64)) {
4228 // i64 is usually not legal on 32-bit targets, but f64 may be.
4236 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4237 if (NewVT == MVT::i8)
4239 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4241 NewVTSize = NewVT.getSizeInBits() / 8;
4243 // If the new VT cannot cover all of the remaining bits, then consider
4244 // issuing a (or a pair of) unaligned and overlapping load / store.
4245 // FIXME: Only does this for 64-bit or more since we don't have proper
4246 // cost model for unaligned load / store.
4249 if (NumMemOps && AllowOverlap &&
4250 VTSize >= 8 && NewVTSize < Size &&
4251 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4259 if (++NumMemOps > Limit)
4262 MemOps.push_back(VT);
4269 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4270 // On Darwin, -Os means optimize for size without hurting performance, so
4271 // only really optimize for size when -Oz (MinSize) is used.
4272 if (MF.getTarget().getTargetTriple().isOSDarwin())
4273 return MF.getFunction()->optForMinSize();
4274 return MF.getFunction()->optForSize();
4277 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4278 SDValue Chain, SDValue Dst,
4279 SDValue Src, uint64_t Size,
4280 unsigned Align, bool isVol,
4282 MachinePointerInfo DstPtrInfo,
4283 MachinePointerInfo SrcPtrInfo) {
4284 // Turn a memcpy of undef to nop.
4285 if (Src.getOpcode() == ISD::UNDEF)
4288 // Expand memcpy to a series of load and store ops if the size operand falls
4289 // below a certain threshold.
4290 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4291 // rather than maybe a humongous number of loads and stores.
4292 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4293 std::vector<EVT> MemOps;
4294 bool DstAlignCanChange = false;
4295 MachineFunction &MF = DAG.getMachineFunction();
4296 MachineFrameInfo *MFI = MF.getFrameInfo();
4297 bool OptSize = shouldLowerMemFuncForSize(MF);
4298 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4299 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4300 DstAlignCanChange = true;
4301 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4302 if (Align > SrcAlign)
4305 bool CopyFromStr = isMemSrcFromString(Src, Str);
4306 bool isZeroStr = CopyFromStr && Str.empty();
4307 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4309 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4310 (DstAlignCanChange ? 0 : Align),
4311 (isZeroStr ? 0 : SrcAlign),
4312 false, false, CopyFromStr, true, DAG, TLI))
4315 if (DstAlignCanChange) {
4316 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4317 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4319 // Don't promote to an alignment that would require dynamic stack
4321 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4322 if (!TRI->needsStackRealignment(MF))
4323 while (NewAlign > Align &&
4324 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4327 if (NewAlign > Align) {
4328 // Give the stack frame object a larger alignment if needed.
4329 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4330 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4335 SmallVector<SDValue, 8> OutChains;
4336 unsigned NumMemOps = MemOps.size();
4337 uint64_t SrcOff = 0, DstOff = 0;
4338 for (unsigned i = 0; i != NumMemOps; ++i) {
4340 unsigned VTSize = VT.getSizeInBits() / 8;
4341 SDValue Value, Store;
4343 if (VTSize > Size) {
4344 // Issuing an unaligned load / store pair that overlaps with the previous
4345 // pair. Adjust the offset accordingly.
4346 assert(i == NumMemOps-1 && i != 0);
4347 SrcOff -= VTSize - Size;
4348 DstOff -= VTSize - Size;
4352 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4353 // It's unlikely a store of a vector immediate can be done in a single
4354 // instruction. It would require a load from a constantpool first.
4355 // We only handle zero vectors here.
4356 // FIXME: Handle other cases where store of vector immediate is done in
4357 // a single instruction.
4358 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4359 if (Value.getNode())
4360 Store = DAG.getStore(Chain, dl, Value,
4361 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4362 DstPtrInfo.getWithOffset(DstOff), isVol,
4366 if (!Store.getNode()) {
4367 // The type might not be legal for the target. This should only happen
4368 // if the type is smaller than a legal type, as on PPC, so the right
4369 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4370 // to Load/Store if NVT==VT.
4371 // FIXME does the case above also need this?
4372 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4373 assert(NVT.bitsGE(VT));
4374 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4375 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4376 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4377 false, MinAlign(SrcAlign, SrcOff));
4378 Store = DAG.getTruncStore(Chain, dl, Value,
4379 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4380 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4383 OutChains.push_back(Store);
4389 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4392 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4393 SDValue Chain, SDValue Dst,
4394 SDValue Src, uint64_t Size,
4395 unsigned Align, bool isVol,
4397 MachinePointerInfo DstPtrInfo,
4398 MachinePointerInfo SrcPtrInfo) {
4399 // Turn a memmove of undef to nop.
4400 if (Src.getOpcode() == ISD::UNDEF)
4403 // Expand memmove to a series of load and store ops if the size operand falls
4404 // below a certain threshold.
4405 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4406 std::vector<EVT> MemOps;
4407 bool DstAlignCanChange = false;
4408 MachineFunction &MF = DAG.getMachineFunction();
4409 MachineFrameInfo *MFI = MF.getFrameInfo();
4410 bool OptSize = shouldLowerMemFuncForSize(MF);
4411 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4412 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4413 DstAlignCanChange = true;
4414 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4415 if (Align > SrcAlign)
4417 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4419 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4420 (DstAlignCanChange ? 0 : Align), SrcAlign,
4421 false, false, false, false, DAG, TLI))
4424 if (DstAlignCanChange) {
4425 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4426 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4427 if (NewAlign > Align) {
4428 // Give the stack frame object a larger alignment if needed.
4429 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4430 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4435 uint64_t SrcOff = 0, DstOff = 0;
4436 SmallVector<SDValue, 8> LoadValues;
4437 SmallVector<SDValue, 8> LoadChains;
4438 SmallVector<SDValue, 8> OutChains;
4439 unsigned NumMemOps = MemOps.size();
4440 for (unsigned i = 0; i < NumMemOps; i++) {
4442 unsigned VTSize = VT.getSizeInBits() / 8;
4445 Value = DAG.getLoad(VT, dl, Chain,
4446 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4447 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4448 false, false, SrcAlign);
4449 LoadValues.push_back(Value);
4450 LoadChains.push_back(Value.getValue(1));
4453 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4455 for (unsigned i = 0; i < NumMemOps; i++) {
4457 unsigned VTSize = VT.getSizeInBits() / 8;
4460 Store = DAG.getStore(Chain, dl, LoadValues[i],
4461 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4462 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4463 OutChains.push_back(Store);
4467 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4470 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4473 /// \param DAG Selection DAG where lowered code is placed.
4474 /// \param dl Link to corresponding IR location.
4475 /// \param Chain Control flow dependency.
4476 /// \param Dst Pointer to destination memory location.
4477 /// \param Src Value of byte to write into the memory.
4478 /// \param Size Number of bytes to write.
4479 /// \param Align Alignment of the destination in bytes.
4480 /// \param isVol True if destination is volatile.
4481 /// \param DstPtrInfo IR information on the memory pointer.
4482 /// \returns New head in the control flow, if lowering was successful, empty
4483 /// SDValue otherwise.
4485 /// The function tries to replace 'llvm.memset' intrinsic with several store
4486 /// operations and value calculation code. This is usually profitable for small
4488 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4489 SDValue Chain, SDValue Dst,
4490 SDValue Src, uint64_t Size,
4491 unsigned Align, bool isVol,
4492 MachinePointerInfo DstPtrInfo) {
4493 // Turn a memset of undef to nop.
4494 if (Src.getOpcode() == ISD::UNDEF)
4497 // Expand memset to a series of load/store ops if the size operand
4498 // falls below a certain threshold.
4499 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4500 std::vector<EVT> MemOps;
4501 bool DstAlignCanChange = false;
4502 MachineFunction &MF = DAG.getMachineFunction();
4503 MachineFrameInfo *MFI = MF.getFrameInfo();
4504 bool OptSize = shouldLowerMemFuncForSize(MF);
4505 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4506 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4507 DstAlignCanChange = true;
4509 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4510 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4511 Size, (DstAlignCanChange ? 0 : Align), 0,
4512 true, IsZeroVal, false, true, DAG, TLI))
4515 if (DstAlignCanChange) {
4516 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4517 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4518 if (NewAlign > Align) {
4519 // Give the stack frame object a larger alignment if needed.
4520 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4521 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4526 SmallVector<SDValue, 8> OutChains;
4527 uint64_t DstOff = 0;
4528 unsigned NumMemOps = MemOps.size();
4530 // Find the largest store and generate the bit pattern for it.
4531 EVT LargestVT = MemOps[0];
4532 for (unsigned i = 1; i < NumMemOps; i++)
4533 if (MemOps[i].bitsGT(LargestVT))
4534 LargestVT = MemOps[i];
4535 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4537 for (unsigned i = 0; i < NumMemOps; i++) {
4539 unsigned VTSize = VT.getSizeInBits() / 8;
4540 if (VTSize > Size) {
4541 // Issuing an unaligned load / store pair that overlaps with the previous
4542 // pair. Adjust the offset accordingly.
4543 assert(i == NumMemOps-1 && i != 0);
4544 DstOff -= VTSize - Size;
4547 // If this store is smaller than the largest store see whether we can get
4548 // the smaller value for free with a truncate.
4549 SDValue Value = MemSetValue;
4550 if (VT.bitsLT(LargestVT)) {
4551 if (!LargestVT.isVector() && !VT.isVector() &&
4552 TLI.isTruncateFree(LargestVT, VT))
4553 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4555 Value = getMemsetValue(Src, VT, DAG, dl);
4557 assert(Value.getValueType() == VT && "Value with wrong type.");
4558 SDValue Store = DAG.getStore(Chain, dl, Value,
4559 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4560 DstPtrInfo.getWithOffset(DstOff),
4561 isVol, false, Align);
4562 OutChains.push_back(Store);
4563 DstOff += VT.getSizeInBits() / 8;
4567 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4570 static void checkAddrSpaceIsValidForLibcall(const TargetLowering *TLI,
4572 // Lowering memcpy / memset / memmove intrinsics to calls is only valid if all
4573 // pointer operands can be losslessly bitcasted to pointers of address space 0
4574 if (AS != 0 && !TLI->isNoopAddrSpaceCast(AS, 0)) {
4575 report_fatal_error("cannot lower memory intrinsic in address space " +
4580 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4581 SDValue Src, SDValue Size,
4582 unsigned Align, bool isVol, bool AlwaysInline,
4583 bool isTailCall, MachinePointerInfo DstPtrInfo,
4584 MachinePointerInfo SrcPtrInfo) {
4585 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4587 // Check to see if we should lower the memcpy to loads and stores first.
4588 // For cases within the target-specified limits, this is the best choice.
4589 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4591 // Memcpy with size zero? Just return the original chain.
4592 if (ConstantSize->isNullValue())
4595 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4596 ConstantSize->getZExtValue(),Align,
4597 isVol, false, DstPtrInfo, SrcPtrInfo);
4598 if (Result.getNode())
4602 // Then check to see if we should lower the memcpy with target-specific
4603 // code. If the target chooses to do this, this is the next best.
4605 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4606 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4607 DstPtrInfo, SrcPtrInfo);
4608 if (Result.getNode())
4612 // If we really need inline code and the target declined to provide it,
4613 // use a (potentially long) sequence of loads and stores.
4615 assert(ConstantSize && "AlwaysInline requires a constant size!");
4616 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4617 ConstantSize->getZExtValue(), Align, isVol,
4618 true, DstPtrInfo, SrcPtrInfo);
4621 checkAddrSpaceIsValidForLibcall(TLI, DstPtrInfo.getAddrSpace());
4622 checkAddrSpaceIsValidForLibcall(TLI, SrcPtrInfo.getAddrSpace());
4624 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4625 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4626 // respect volatile, so they may do things like read or write memory
4627 // beyond the given memory regions. But fixing this isn't easy, and most
4628 // people don't care.
4630 // Emit a library call.
4631 TargetLowering::ArgListTy Args;
4632 TargetLowering::ArgListEntry Entry;
4633 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4634 Entry.Node = Dst; Args.push_back(Entry);
4635 Entry.Node = Src; Args.push_back(Entry);
4636 Entry.Node = Size; Args.push_back(Entry);
4637 // FIXME: pass in SDLoc
4638 TargetLowering::CallLoweringInfo CLI(*this);
4641 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4642 Type::getVoidTy(*getContext()),
4643 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4644 TLI->getPointerTy(getDataLayout())),
4647 .setTailCall(isTailCall);
4649 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4650 return CallResult.second;
4653 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4654 SDValue Src, SDValue Size,
4655 unsigned Align, bool isVol, bool isTailCall,
4656 MachinePointerInfo DstPtrInfo,
4657 MachinePointerInfo SrcPtrInfo) {
4658 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4660 // Check to see if we should lower the memmove to loads and stores first.
4661 // For cases within the target-specified limits, this is the best choice.
4662 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4664 // Memmove with size zero? Just return the original chain.
4665 if (ConstantSize->isNullValue())
4669 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4670 ConstantSize->getZExtValue(), Align, isVol,
4671 false, DstPtrInfo, SrcPtrInfo);
4672 if (Result.getNode())
4676 // Then check to see if we should lower the memmove with target-specific
4677 // code. If the target chooses to do this, this is the next best.
4679 SDValue Result = TSI->EmitTargetCodeForMemmove(
4680 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4681 if (Result.getNode())
4685 checkAddrSpaceIsValidForLibcall(TLI, DstPtrInfo.getAddrSpace());
4686 checkAddrSpaceIsValidForLibcall(TLI, SrcPtrInfo.getAddrSpace());
4688 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4689 // not be safe. See memcpy above for more details.
4691 // Emit a library call.
4692 TargetLowering::ArgListTy Args;
4693 TargetLowering::ArgListEntry Entry;
4694 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4695 Entry.Node = Dst; Args.push_back(Entry);
4696 Entry.Node = Src; Args.push_back(Entry);
4697 Entry.Node = Size; Args.push_back(Entry);
4698 // FIXME: pass in SDLoc
4699 TargetLowering::CallLoweringInfo CLI(*this);
4702 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4703 Type::getVoidTy(*getContext()),
4704 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4705 TLI->getPointerTy(getDataLayout())),
4708 .setTailCall(isTailCall);
4710 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4711 return CallResult.second;
4714 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4715 SDValue Src, SDValue Size,
4716 unsigned Align, bool isVol, bool isTailCall,
4717 MachinePointerInfo DstPtrInfo) {
4718 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4720 // Check to see if we should lower the memset to stores first.
4721 // For cases within the target-specified limits, this is the best choice.
4722 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4724 // Memset with size zero? Just return the original chain.
4725 if (ConstantSize->isNullValue())
4729 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4730 Align, isVol, DstPtrInfo);
4732 if (Result.getNode())
4736 // Then check to see if we should lower the memset with target-specific
4737 // code. If the target chooses to do this, this is the next best.
4739 SDValue Result = TSI->EmitTargetCodeForMemset(
4740 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4741 if (Result.getNode())
4745 checkAddrSpaceIsValidForLibcall(TLI, DstPtrInfo.getAddrSpace());
4747 // Emit a library call.
4748 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4749 TargetLowering::ArgListTy Args;
4750 TargetLowering::ArgListEntry Entry;
4751 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4752 Args.push_back(Entry);
4754 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4755 Args.push_back(Entry);
4757 Entry.Ty = IntPtrTy;
4758 Args.push_back(Entry);
4760 // FIXME: pass in SDLoc
4761 TargetLowering::CallLoweringInfo CLI(*this);
4764 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4765 Type::getVoidTy(*getContext()),
4766 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4767 TLI->getPointerTy(getDataLayout())),
4770 .setTailCall(isTailCall);
4772 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4773 return CallResult.second;
4776 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4777 SDVTList VTList, ArrayRef<SDValue> Ops,
4778 MachineMemOperand *MMO,
4779 AtomicOrdering SuccessOrdering,
4780 AtomicOrdering FailureOrdering,
4781 SynchronizationScope SynchScope) {
4782 FoldingSetNodeID ID;
4783 ID.AddInteger(MemVT.getRawBits());
4784 AddNodeIDNode(ID, Opcode, VTList, Ops);
4785 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4787 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4788 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4789 return SDValue(E, 0);
4792 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4793 // SDNode doesn't have access to it. This memory will be "leaked" when
4794 // the node is deallocated, but recovered when the allocator is released.
4795 // If the number of operands is less than 5 we use AtomicSDNode's internal
4797 unsigned NumOps = Ops.size();
4798 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4801 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4802 dl.getDebugLoc(), VTList, MemVT,
4803 Ops.data(), DynOps, NumOps, MMO,
4804 SuccessOrdering, FailureOrdering,
4806 CSEMap.InsertNode(N, IP);
4808 return SDValue(N, 0);
4811 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4812 SDVTList VTList, ArrayRef<SDValue> Ops,
4813 MachineMemOperand *MMO,
4814 AtomicOrdering Ordering,
4815 SynchronizationScope SynchScope) {
4816 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4817 Ordering, SynchScope);
4820 SDValue SelectionDAG::getAtomicCmpSwap(
4821 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4822 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4823 unsigned Alignment, AtomicOrdering SuccessOrdering,
4824 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4825 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4826 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4827 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4829 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4830 Alignment = getEVTAlignment(MemVT);
4832 MachineFunction &MF = getMachineFunction();
4834 // FIXME: Volatile isn't really correct; we should keep track of atomic
4835 // orderings in the memoperand.
4836 unsigned Flags = MachineMemOperand::MOVolatile;
4837 Flags |= MachineMemOperand::MOLoad;
4838 Flags |= MachineMemOperand::MOStore;
4840 MachineMemOperand *MMO =
4841 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4843 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4844 SuccessOrdering, FailureOrdering, SynchScope);
4847 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4848 SDVTList VTs, SDValue Chain, SDValue Ptr,
4849 SDValue Cmp, SDValue Swp,
4850 MachineMemOperand *MMO,
4851 AtomicOrdering SuccessOrdering,
4852 AtomicOrdering FailureOrdering,
4853 SynchronizationScope SynchScope) {
4854 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4855 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4856 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4858 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4859 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4860 SuccessOrdering, FailureOrdering, SynchScope);
4863 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4865 SDValue Ptr, SDValue Val,
4866 const Value* PtrVal,
4868 AtomicOrdering Ordering,
4869 SynchronizationScope SynchScope) {
4870 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4871 Alignment = getEVTAlignment(MemVT);
4873 MachineFunction &MF = getMachineFunction();
4874 // An atomic store does not load. An atomic load does not store.
4875 // (An atomicrmw obviously both loads and stores.)
4876 // For now, atomics are considered to be volatile always, and they are
4878 // FIXME: Volatile isn't really correct; we should keep track of atomic
4879 // orderings in the memoperand.
4880 unsigned Flags = MachineMemOperand::MOVolatile;
4881 if (Opcode != ISD::ATOMIC_STORE)
4882 Flags |= MachineMemOperand::MOLoad;
4883 if (Opcode != ISD::ATOMIC_LOAD)
4884 Flags |= MachineMemOperand::MOStore;
4886 MachineMemOperand *MMO =
4887 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4888 MemVT.getStoreSize(), Alignment);
4890 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4891 Ordering, SynchScope);
4894 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4896 SDValue Ptr, SDValue Val,
4897 MachineMemOperand *MMO,
4898 AtomicOrdering Ordering,
4899 SynchronizationScope SynchScope) {
4900 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4901 Opcode == ISD::ATOMIC_LOAD_SUB ||
4902 Opcode == ISD::ATOMIC_LOAD_AND ||
4903 Opcode == ISD::ATOMIC_LOAD_OR ||
4904 Opcode == ISD::ATOMIC_LOAD_XOR ||
4905 Opcode == ISD::ATOMIC_LOAD_NAND ||
4906 Opcode == ISD::ATOMIC_LOAD_MIN ||
4907 Opcode == ISD::ATOMIC_LOAD_MAX ||
4908 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4909 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4910 Opcode == ISD::ATOMIC_SWAP ||
4911 Opcode == ISD::ATOMIC_STORE) &&
4912 "Invalid Atomic Op");
4914 EVT VT = Val.getValueType();
4916 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4917 getVTList(VT, MVT::Other);
4918 SDValue Ops[] = {Chain, Ptr, Val};
4919 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4922 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4923 EVT VT, SDValue Chain,
4925 MachineMemOperand *MMO,
4926 AtomicOrdering Ordering,
4927 SynchronizationScope SynchScope) {
4928 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4930 SDVTList VTs = getVTList(VT, MVT::Other);
4931 SDValue Ops[] = {Chain, Ptr};
4932 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4935 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4936 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4937 if (Ops.size() == 1)
4940 SmallVector<EVT, 4> VTs;
4941 VTs.reserve(Ops.size());
4942 for (unsigned i = 0; i < Ops.size(); ++i)
4943 VTs.push_back(Ops[i].getValueType());
4944 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4948 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4949 ArrayRef<SDValue> Ops,
4950 EVT MemVT, MachinePointerInfo PtrInfo,
4951 unsigned Align, bool Vol,
4952 bool ReadMem, bool WriteMem, unsigned Size) {
4953 if (Align == 0) // Ensure that codegen never sees alignment 0
4954 Align = getEVTAlignment(MemVT);
4956 MachineFunction &MF = getMachineFunction();
4959 Flags |= MachineMemOperand::MOStore;
4961 Flags |= MachineMemOperand::MOLoad;
4963 Flags |= MachineMemOperand::MOVolatile;
4965 Size = MemVT.getStoreSize();
4966 MachineMemOperand *MMO =
4967 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4969 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4973 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4974 ArrayRef<SDValue> Ops, EVT MemVT,
4975 MachineMemOperand *MMO) {
4976 assert((Opcode == ISD::INTRINSIC_VOID ||
4977 Opcode == ISD::INTRINSIC_W_CHAIN ||
4978 Opcode == ISD::PREFETCH ||
4979 Opcode == ISD::LIFETIME_START ||
4980 Opcode == ISD::LIFETIME_END ||
4981 (Opcode <= INT_MAX &&
4982 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4983 "Opcode is not a memory-accessing opcode!");
4985 // Memoize the node unless it returns a flag.
4986 MemIntrinsicSDNode *N;
4987 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4988 FoldingSetNodeID ID;
4989 AddNodeIDNode(ID, Opcode, VTList, Ops);
4990 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4992 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4993 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4994 return SDValue(E, 0);
4997 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4998 dl.getDebugLoc(), VTList, Ops,
5000 CSEMap.InsertNode(N, IP);
5002 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
5003 dl.getDebugLoc(), VTList, Ops,
5007 return SDValue(N, 0);
5010 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
5011 /// MachinePointerInfo record from it. This is particularly useful because the
5012 /// code generator has many cases where it doesn't bother passing in a
5013 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
5014 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
5015 int64_t Offset = 0) {
5016 // If this is FI+Offset, we can model it.
5017 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
5018 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
5019 FI->getIndex(), Offset);
5021 // If this is (FI+Offset1)+Offset2, we can model it.
5022 if (Ptr.getOpcode() != ISD::ADD ||
5023 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
5024 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
5025 return MachinePointerInfo();
5027 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
5028 return MachinePointerInfo::getFixedStack(
5029 DAG.getMachineFunction(), FI,
5030 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
5033 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
5034 /// MachinePointerInfo record from it. This is particularly useful because the
5035 /// code generator has many cases where it doesn't bother passing in a
5036 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
5037 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
5039 // If the 'Offset' value isn't a constant, we can't handle this.
5040 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
5041 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
5042 if (OffsetOp.getOpcode() == ISD::UNDEF)
5043 return InferPointerInfo(DAG, Ptr);
5044 return MachinePointerInfo();
5049 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5050 EVT VT, SDLoc dl, SDValue Chain,
5051 SDValue Ptr, SDValue Offset,
5052 MachinePointerInfo PtrInfo, EVT MemVT,
5053 bool isVolatile, bool isNonTemporal, bool isInvariant,
5054 unsigned Alignment, const AAMDNodes &AAInfo,
5055 const MDNode *Ranges) {
5056 assert(Chain.getValueType() == MVT::Other &&
5057 "Invalid chain type");
5058 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5059 Alignment = getEVTAlignment(VT);
5061 unsigned Flags = MachineMemOperand::MOLoad;
5063 Flags |= MachineMemOperand::MOVolatile;
5065 Flags |= MachineMemOperand::MONonTemporal;
5067 Flags |= MachineMemOperand::MOInvariant;
5069 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5071 if (PtrInfo.V.isNull())
5072 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5074 MachineFunction &MF = getMachineFunction();
5075 MachineMemOperand *MMO =
5076 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5078 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5082 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5083 EVT VT, SDLoc dl, SDValue Chain,
5084 SDValue Ptr, SDValue Offset, EVT MemVT,
5085 MachineMemOperand *MMO) {
5087 ExtType = ISD::NON_EXTLOAD;
5088 } else if (ExtType == ISD::NON_EXTLOAD) {
5089 assert(VT == MemVT && "Non-extending load from different memory type!");
5092 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5093 "Should only be an extending load, not truncating!");
5094 assert(VT.isInteger() == MemVT.isInteger() &&
5095 "Cannot convert from FP to Int or Int -> FP!");
5096 assert(VT.isVector() == MemVT.isVector() &&
5097 "Cannot use an ext load to convert to or from a vector!");
5098 assert((!VT.isVector() ||
5099 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5100 "Cannot use an ext load to change the number of vector elements!");
5103 bool Indexed = AM != ISD::UNINDEXED;
5104 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5105 "Unindexed load with an offset!");
5107 SDVTList VTs = Indexed ?
5108 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5109 SDValue Ops[] = { Chain, Ptr, Offset };
5110 FoldingSetNodeID ID;
5111 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5112 ID.AddInteger(MemVT.getRawBits());
5113 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5114 MMO->isNonTemporal(),
5115 MMO->isInvariant()));
5116 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5118 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5119 cast<LoadSDNode>(E)->refineAlignment(MMO);
5120 return SDValue(E, 0);
5122 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5123 dl.getDebugLoc(), VTs, AM, ExtType,
5125 CSEMap.InsertNode(N, IP);
5127 return SDValue(N, 0);
5130 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5131 SDValue Chain, SDValue Ptr,
5132 MachinePointerInfo PtrInfo,
5133 bool isVolatile, bool isNonTemporal,
5134 bool isInvariant, unsigned Alignment,
5135 const AAMDNodes &AAInfo,
5136 const MDNode *Ranges) {
5137 SDValue Undef = getUNDEF(Ptr.getValueType());
5138 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5139 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5143 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5144 SDValue Chain, SDValue Ptr,
5145 MachineMemOperand *MMO) {
5146 SDValue Undef = getUNDEF(Ptr.getValueType());
5147 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5151 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5152 SDValue Chain, SDValue Ptr,
5153 MachinePointerInfo PtrInfo, EVT MemVT,
5154 bool isVolatile, bool isNonTemporal,
5155 bool isInvariant, unsigned Alignment,
5156 const AAMDNodes &AAInfo) {
5157 SDValue Undef = getUNDEF(Ptr.getValueType());
5158 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5159 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5164 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5165 SDValue Chain, SDValue Ptr, EVT MemVT,
5166 MachineMemOperand *MMO) {
5167 SDValue Undef = getUNDEF(Ptr.getValueType());
5168 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5173 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5174 SDValue Offset, ISD::MemIndexedMode AM) {
5175 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5176 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5177 "Load is already a indexed load!");
5178 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5179 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5180 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5181 false, LD->getAlignment());
5184 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5185 SDValue Ptr, MachinePointerInfo PtrInfo,
5186 bool isVolatile, bool isNonTemporal,
5187 unsigned Alignment, const AAMDNodes &AAInfo) {
5188 assert(Chain.getValueType() == MVT::Other &&
5189 "Invalid chain type");
5190 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5191 Alignment = getEVTAlignment(Val.getValueType());
5193 unsigned Flags = MachineMemOperand::MOStore;
5195 Flags |= MachineMemOperand::MOVolatile;
5197 Flags |= MachineMemOperand::MONonTemporal;
5199 if (PtrInfo.V.isNull())
5200 PtrInfo = InferPointerInfo(*this, Ptr);
5202 MachineFunction &MF = getMachineFunction();
5203 MachineMemOperand *MMO =
5204 MF.getMachineMemOperand(PtrInfo, Flags,
5205 Val.getValueType().getStoreSize(), Alignment,
5208 return getStore(Chain, dl, Val, Ptr, MMO);
5211 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5212 SDValue Ptr, MachineMemOperand *MMO) {
5213 assert(Chain.getValueType() == MVT::Other &&
5214 "Invalid chain type");
5215 EVT VT = Val.getValueType();
5216 SDVTList VTs = getVTList(MVT::Other);
5217 SDValue Undef = getUNDEF(Ptr.getValueType());
5218 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5219 FoldingSetNodeID ID;
5220 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5221 ID.AddInteger(VT.getRawBits());
5222 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5223 MMO->isNonTemporal(), MMO->isInvariant()));
5224 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5226 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5227 cast<StoreSDNode>(E)->refineAlignment(MMO);
5228 return SDValue(E, 0);
5230 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5231 dl.getDebugLoc(), VTs,
5232 ISD::UNINDEXED, false, VT, MMO);
5233 CSEMap.InsertNode(N, IP);
5235 return SDValue(N, 0);
5238 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5239 SDValue Ptr, MachinePointerInfo PtrInfo,
5240 EVT SVT,bool isVolatile, bool isNonTemporal,
5242 const AAMDNodes &AAInfo) {
5243 assert(Chain.getValueType() == MVT::Other &&
5244 "Invalid chain type");
5245 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5246 Alignment = getEVTAlignment(SVT);
5248 unsigned Flags = MachineMemOperand::MOStore;
5250 Flags |= MachineMemOperand::MOVolatile;
5252 Flags |= MachineMemOperand::MONonTemporal;
5254 if (PtrInfo.V.isNull())
5255 PtrInfo = InferPointerInfo(*this, Ptr);
5257 MachineFunction &MF = getMachineFunction();
5258 MachineMemOperand *MMO =
5259 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5262 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5265 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5266 SDValue Ptr, EVT SVT,
5267 MachineMemOperand *MMO) {
5268 EVT VT = Val.getValueType();
5270 assert(Chain.getValueType() == MVT::Other &&
5271 "Invalid chain type");
5273 return getStore(Chain, dl, Val, Ptr, MMO);
5275 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5276 "Should only be a truncating store, not extending!");
5277 assert(VT.isInteger() == SVT.isInteger() &&
5278 "Can't do FP-INT conversion!");
5279 assert(VT.isVector() == SVT.isVector() &&
5280 "Cannot use trunc store to convert to or from a vector!");
5281 assert((!VT.isVector() ||
5282 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5283 "Cannot use trunc store to change the number of vector elements!");
5285 SDVTList VTs = getVTList(MVT::Other);
5286 SDValue Undef = getUNDEF(Ptr.getValueType());
5287 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5288 FoldingSetNodeID ID;
5289 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5290 ID.AddInteger(SVT.getRawBits());
5291 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5292 MMO->isNonTemporal(), MMO->isInvariant()));
5293 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5295 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5296 cast<StoreSDNode>(E)->refineAlignment(MMO);
5297 return SDValue(E, 0);
5299 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5300 dl.getDebugLoc(), VTs,
5301 ISD::UNINDEXED, true, SVT, MMO);
5302 CSEMap.InsertNode(N, IP);
5304 return SDValue(N, 0);
5308 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5309 SDValue Offset, ISD::MemIndexedMode AM) {
5310 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5311 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5312 "Store is already a indexed store!");
5313 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5314 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5315 FoldingSetNodeID ID;
5316 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5317 ID.AddInteger(ST->getMemoryVT().getRawBits());
5318 ID.AddInteger(ST->getRawSubclassData());
5319 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5321 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5322 return SDValue(E, 0);
5324 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5325 dl.getDebugLoc(), VTs, AM,
5326 ST->isTruncatingStore(),
5328 ST->getMemOperand());
5329 CSEMap.InsertNode(N, IP);
5331 return SDValue(N, 0);
5335 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5336 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5337 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5339 SDVTList VTs = getVTList(VT, MVT::Other);
5340 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5341 FoldingSetNodeID ID;
5342 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5343 ID.AddInteger(VT.getRawBits());
5344 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5346 MMO->isNonTemporal(),
5347 MMO->isInvariant()));
5348 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5350 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5351 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5352 return SDValue(E, 0);
5354 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5355 dl.getDebugLoc(), Ops, 4, VTs,
5357 CSEMap.InsertNode(N, IP);
5359 return SDValue(N, 0);
5362 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5363 SDValue Ptr, SDValue Mask, EVT MemVT,
5364 MachineMemOperand *MMO, bool isTrunc) {
5365 assert(Chain.getValueType() == MVT::Other &&
5366 "Invalid chain type");
5367 EVT VT = Val.getValueType();
5368 SDVTList VTs = getVTList(MVT::Other);
5369 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5370 FoldingSetNodeID ID;
5371 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5372 ID.AddInteger(VT.getRawBits());
5373 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5374 MMO->isNonTemporal(), MMO->isInvariant()));
5375 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5377 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5378 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5379 return SDValue(E, 0);
5381 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5382 dl.getDebugLoc(), Ops, 4,
5383 VTs, isTrunc, MemVT, MMO);
5384 CSEMap.InsertNode(N, IP);
5386 return SDValue(N, 0);
5390 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5391 ArrayRef<SDValue> Ops,
5392 MachineMemOperand *MMO) {
5394 FoldingSetNodeID ID;
5395 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5396 ID.AddInteger(VT.getRawBits());
5397 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5399 MMO->isNonTemporal(),
5400 MMO->isInvariant()));
5401 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5403 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5404 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5405 return SDValue(E, 0);
5407 MaskedGatherSDNode *N =
5408 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5410 CSEMap.InsertNode(N, IP);
5412 return SDValue(N, 0);
5415 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5416 ArrayRef<SDValue> Ops,
5417 MachineMemOperand *MMO) {
5418 FoldingSetNodeID ID;
5419 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5420 ID.AddInteger(VT.getRawBits());
5421 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5422 MMO->isNonTemporal(),
5423 MMO->isInvariant()));
5424 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5426 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5427 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5428 return SDValue(E, 0);
5431 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5433 CSEMap.InsertNode(N, IP);
5435 return SDValue(N, 0);
5438 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5439 SDValue Chain, SDValue Ptr,
5442 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5443 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5446 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5447 ArrayRef<SDUse> Ops) {
5448 switch (Ops.size()) {
5449 case 0: return getNode(Opcode, DL, VT);
5450 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5451 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5452 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5456 // Copy from an SDUse array into an SDValue array for use with
5457 // the regular getNode logic.
5458 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5459 return getNode(Opcode, DL, VT, NewOps);
5462 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5463 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5464 unsigned NumOps = Ops.size();
5466 case 0: return getNode(Opcode, DL, VT);
5467 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5468 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5469 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5475 case ISD::CONCAT_VECTORS: {
5476 // Attempt to fold CONCAT_VECTORS into BUILD_VECTOR or UNDEF.
5477 if (SDValue V = FoldCONCAT_VECTORS(DL, VT, Ops, *this))
5481 case ISD::SELECT_CC: {
5482 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5483 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5484 "LHS and RHS of condition must have same type!");
5485 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5486 "True and False arms of SelectCC must have same type!");
5487 assert(Ops[2].getValueType() == VT &&
5488 "select_cc node must be of same type as true and false value!");
5492 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5493 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5494 "LHS/RHS of comparison should match types!");
5501 SDVTList VTs = getVTList(VT);
5503 if (VT != MVT::Glue) {
5504 FoldingSetNodeID ID;
5505 AddNodeIDNode(ID, Opcode, VTs, Ops);
5508 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5509 return SDValue(E, 0);
5511 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5513 CSEMap.InsertNode(N, IP);
5515 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5520 return SDValue(N, 0);
5523 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5524 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5525 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5528 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5529 ArrayRef<SDValue> Ops) {
5530 if (VTList.NumVTs == 1)
5531 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5535 // FIXME: figure out how to safely handle things like
5536 // int foo(int x) { return 1 << (x & 255); }
5537 // int bar() { return foo(256); }
5538 case ISD::SRA_PARTS:
5539 case ISD::SRL_PARTS:
5540 case ISD::SHL_PARTS:
5541 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5542 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5543 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5544 else if (N3.getOpcode() == ISD::AND)
5545 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5546 // If the and is only masking out bits that cannot effect the shift,
5547 // eliminate the and.
5548 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5549 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5550 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5556 // Memoize the node unless it returns a flag.
5558 unsigned NumOps = Ops.size();
5559 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5560 FoldingSetNodeID ID;
5561 AddNodeIDNode(ID, Opcode, VTList, Ops);
5563 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5564 return SDValue(E, 0);
5567 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5568 DL.getDebugLoc(), VTList, Ops[0]);
5569 } else if (NumOps == 2) {
5570 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5571 DL.getDebugLoc(), VTList, Ops[0],
5573 } else if (NumOps == 3) {
5574 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5575 DL.getDebugLoc(), VTList, Ops[0],
5578 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5581 CSEMap.InsertNode(N, IP);
5584 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5585 DL.getDebugLoc(), VTList, Ops[0]);
5586 } else if (NumOps == 2) {
5587 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5588 DL.getDebugLoc(), VTList, Ops[0],
5590 } else if (NumOps == 3) {
5591 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5592 DL.getDebugLoc(), VTList, Ops[0],
5595 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5600 return SDValue(N, 0);
5603 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5604 return getNode(Opcode, DL, VTList, None);
5607 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5609 SDValue Ops[] = { N1 };
5610 return getNode(Opcode, DL, VTList, Ops);
5613 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5614 SDValue N1, SDValue N2) {
5615 SDValue Ops[] = { N1, N2 };
5616 return getNode(Opcode, DL, VTList, Ops);
5619 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5620 SDValue N1, SDValue N2, SDValue N3) {
5621 SDValue Ops[] = { N1, N2, N3 };
5622 return getNode(Opcode, DL, VTList, Ops);
5625 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5626 SDValue N1, SDValue N2, SDValue N3,
5628 SDValue Ops[] = { N1, N2, N3, N4 };
5629 return getNode(Opcode, DL, VTList, Ops);
5632 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5633 SDValue N1, SDValue N2, SDValue N3,
5634 SDValue N4, SDValue N5) {
5635 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5636 return getNode(Opcode, DL, VTList, Ops);
5639 SDVTList SelectionDAG::getVTList(EVT VT) {
5640 return makeVTList(SDNode::getValueTypeList(VT), 1);
5643 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5644 FoldingSetNodeID ID;
5646 ID.AddInteger(VT1.getRawBits());
5647 ID.AddInteger(VT2.getRawBits());
5650 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5652 EVT *Array = Allocator.Allocate<EVT>(2);
5655 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5656 VTListMap.InsertNode(Result, IP);
5658 return Result->getSDVTList();
5661 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5662 FoldingSetNodeID ID;
5664 ID.AddInteger(VT1.getRawBits());
5665 ID.AddInteger(VT2.getRawBits());
5666 ID.AddInteger(VT3.getRawBits());
5669 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5671 EVT *Array = Allocator.Allocate<EVT>(3);
5675 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5676 VTListMap.InsertNode(Result, IP);
5678 return Result->getSDVTList();
5681 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5682 FoldingSetNodeID ID;
5684 ID.AddInteger(VT1.getRawBits());
5685 ID.AddInteger(VT2.getRawBits());
5686 ID.AddInteger(VT3.getRawBits());
5687 ID.AddInteger(VT4.getRawBits());
5690 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5692 EVT *Array = Allocator.Allocate<EVT>(4);
5697 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5698 VTListMap.InsertNode(Result, IP);
5700 return Result->getSDVTList();
5703 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5704 unsigned NumVTs = VTs.size();
5705 FoldingSetNodeID ID;
5706 ID.AddInteger(NumVTs);
5707 for (unsigned index = 0; index < NumVTs; index++) {
5708 ID.AddInteger(VTs[index].getRawBits());
5712 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5714 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5715 std::copy(VTs.begin(), VTs.end(), Array);
5716 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5717 VTListMap.InsertNode(Result, IP);
5719 return Result->getSDVTList();
5723 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5724 /// specified operands. If the resultant node already exists in the DAG,
5725 /// this does not modify the specified node, instead it returns the node that
5726 /// already exists. If the resultant node does not exist in the DAG, the
5727 /// input node is returned. As a degenerate case, if you specify the same
5728 /// input operands as the node already has, the input node is returned.
5729 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5730 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5732 // Check to see if there is no change.
5733 if (Op == N->getOperand(0)) return N;
5735 // See if the modified node already exists.
5736 void *InsertPos = nullptr;
5737 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5740 // Nope it doesn't. Remove the node from its current place in the maps.
5742 if (!RemoveNodeFromCSEMaps(N))
5743 InsertPos = nullptr;
5745 // Now we update the operands.
5746 N->OperandList[0].set(Op);
5748 // If this gets put into a CSE map, add it.
5749 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5753 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5754 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5756 // Check to see if there is no change.
5757 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5758 return N; // No operands changed, just return the input node.
5760 // See if the modified node already exists.
5761 void *InsertPos = nullptr;
5762 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5765 // Nope it doesn't. Remove the node from its current place in the maps.
5767 if (!RemoveNodeFromCSEMaps(N))
5768 InsertPos = nullptr;
5770 // Now we update the operands.
5771 if (N->OperandList[0] != Op1)
5772 N->OperandList[0].set(Op1);
5773 if (N->OperandList[1] != Op2)
5774 N->OperandList[1].set(Op2);
5776 // If this gets put into a CSE map, add it.
5777 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5781 SDNode *SelectionDAG::
5782 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5783 SDValue Ops[] = { Op1, Op2, Op3 };
5784 return UpdateNodeOperands(N, Ops);
5787 SDNode *SelectionDAG::
5788 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5789 SDValue Op3, SDValue Op4) {
5790 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5791 return UpdateNodeOperands(N, Ops);
5794 SDNode *SelectionDAG::
5795 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5796 SDValue Op3, SDValue Op4, SDValue Op5) {
5797 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5798 return UpdateNodeOperands(N, Ops);
5801 SDNode *SelectionDAG::
5802 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5803 unsigned NumOps = Ops.size();
5804 assert(N->getNumOperands() == NumOps &&
5805 "Update with wrong number of operands");
5807 // If no operands changed just return the input node.
5808 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5811 // See if the modified node already exists.
5812 void *InsertPos = nullptr;
5813 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5816 // Nope it doesn't. Remove the node from its current place in the maps.
5818 if (!RemoveNodeFromCSEMaps(N))
5819 InsertPos = nullptr;
5821 // Now we update the operands.
5822 for (unsigned i = 0; i != NumOps; ++i)
5823 if (N->OperandList[i] != Ops[i])
5824 N->OperandList[i].set(Ops[i]);
5826 // If this gets put into a CSE map, add it.
5827 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5831 /// DropOperands - Release the operands and set this node to have
5833 void SDNode::DropOperands() {
5834 // Unlike the code in MorphNodeTo that does this, we don't need to
5835 // watch for dead nodes here.
5836 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5842 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5845 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5847 SDVTList VTs = getVTList(VT);
5848 return SelectNodeTo(N, MachineOpc, VTs, None);
5851 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5852 EVT VT, SDValue Op1) {
5853 SDVTList VTs = getVTList(VT);
5854 SDValue Ops[] = { Op1 };
5855 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5858 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5859 EVT VT, SDValue Op1,
5861 SDVTList VTs = getVTList(VT);
5862 SDValue Ops[] = { Op1, Op2 };
5863 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5866 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5867 EVT VT, SDValue Op1,
5868 SDValue Op2, SDValue Op3) {
5869 SDVTList VTs = getVTList(VT);
5870 SDValue Ops[] = { Op1, Op2, Op3 };
5871 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5874 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5875 EVT VT, ArrayRef<SDValue> Ops) {
5876 SDVTList VTs = getVTList(VT);
5877 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5880 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5881 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5882 SDVTList VTs = getVTList(VT1, VT2);
5883 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5886 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5888 SDVTList VTs = getVTList(VT1, VT2);
5889 return SelectNodeTo(N, MachineOpc, VTs, None);
5892 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5893 EVT VT1, EVT VT2, EVT VT3,
5894 ArrayRef<SDValue> Ops) {
5895 SDVTList VTs = getVTList(VT1, VT2, VT3);
5896 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5899 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5900 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5901 ArrayRef<SDValue> Ops) {
5902 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5903 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5906 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5909 SDVTList VTs = getVTList(VT1, VT2);
5910 SDValue Ops[] = { Op1 };
5911 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5914 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5916 SDValue Op1, SDValue Op2) {
5917 SDVTList VTs = getVTList(VT1, VT2);
5918 SDValue Ops[] = { Op1, Op2 };
5919 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5922 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5924 SDValue Op1, SDValue Op2,
5926 SDVTList VTs = getVTList(VT1, VT2);
5927 SDValue Ops[] = { Op1, Op2, Op3 };
5928 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5931 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5932 EVT VT1, EVT VT2, EVT VT3,
5933 SDValue Op1, SDValue Op2,
5935 SDVTList VTs = getVTList(VT1, VT2, VT3);
5936 SDValue Ops[] = { Op1, Op2, Op3 };
5937 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5940 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5941 SDVTList VTs,ArrayRef<SDValue> Ops) {
5942 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5943 // Reset the NodeID to -1.
5948 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5949 /// the line number information on the merged node since it is not possible to
5950 /// preserve the information that operation is associated with multiple lines.
5951 /// This will make the debugger working better at -O0, were there is a higher
5952 /// probability having other instructions associated with that line.
5954 /// For IROrder, we keep the smaller of the two
5955 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5956 DebugLoc NLoc = N->getDebugLoc();
5957 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5958 N->setDebugLoc(DebugLoc());
5960 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5961 N->setIROrder(Order);
5965 /// MorphNodeTo - This *mutates* the specified node to have the specified
5966 /// return type, opcode, and operands.
5968 /// Note that MorphNodeTo returns the resultant node. If there is already a
5969 /// node of the specified opcode and operands, it returns that node instead of
5970 /// the current one. Note that the SDLoc need not be the same.
5972 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5973 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5974 /// node, and because it doesn't require CSE recalculation for any of
5975 /// the node's users.
5977 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5978 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5979 /// the legalizer which maintain worklists that would need to be updated when
5980 /// deleting things.
5981 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5982 SDVTList VTs, ArrayRef<SDValue> Ops) {
5983 unsigned NumOps = Ops.size();
5984 // If an identical node already exists, use it.
5986 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5987 FoldingSetNodeID ID;
5988 AddNodeIDNode(ID, Opc, VTs, Ops);
5989 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5990 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5993 if (!RemoveNodeFromCSEMaps(N))
5996 // Start the morphing.
5998 N->ValueList = VTs.VTs;
5999 N->NumValues = VTs.NumVTs;
6001 // Clear the operands list, updating used nodes to remove this from their
6002 // use list. Keep track of any operands that become dead as a result.
6003 SmallPtrSet<SDNode*, 16> DeadNodeSet;
6004 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
6006 SDNode *Used = Use.getNode();
6008 if (Used->use_empty())
6009 DeadNodeSet.insert(Used);
6012 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
6013 // Initialize the memory references information.
6014 MN->setMemRefs(nullptr, nullptr);
6015 // If NumOps is larger than the # of operands we can have in a
6016 // MachineSDNode, reallocate the operand list.
6017 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
6018 if (MN->OperandsNeedDelete)
6019 delete[] MN->OperandList;
6020 if (NumOps > array_lengthof(MN->LocalOperands))
6021 // We're creating a final node that will live unmorphed for the
6022 // remainder of the current SelectionDAG iteration, so we can allocate
6023 // the operands directly out of a pool with no recycling metadata.
6024 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6025 Ops.data(), NumOps);
6027 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
6028 MN->OperandsNeedDelete = false;
6030 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
6032 // If NumOps is larger than the # of operands we currently have, reallocate
6033 // the operand list.
6034 if (NumOps > N->NumOperands) {
6035 if (N->OperandsNeedDelete)
6036 delete[] N->OperandList;
6037 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
6038 N->OperandsNeedDelete = true;
6040 N->InitOperands(N->OperandList, Ops.data(), NumOps);
6043 // Delete any nodes that are still dead after adding the uses for the
6045 if (!DeadNodeSet.empty()) {
6046 SmallVector<SDNode *, 16> DeadNodes;
6047 for (SDNode *N : DeadNodeSet)
6049 DeadNodes.push_back(N);
6050 RemoveDeadNodes(DeadNodes);
6054 CSEMap.InsertNode(N, IP); // Memoize the new node.
6059 /// getMachineNode - These are used for target selectors to create a new node
6060 /// with specified return type(s), MachineInstr opcode, and operands.
6062 /// Note that getMachineNode returns the resultant node. If there is already a
6063 /// node of the specified opcode and operands, it returns that node instead of
6064 /// the current one.
6066 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
6067 SDVTList VTs = getVTList(VT);
6068 return getMachineNode(Opcode, dl, VTs, None);
6072 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6073 SDVTList VTs = getVTList(VT);
6074 SDValue Ops[] = { Op1 };
6075 return getMachineNode(Opcode, dl, VTs, Ops);
6079 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6080 SDValue Op1, SDValue Op2) {
6081 SDVTList VTs = getVTList(VT);
6082 SDValue Ops[] = { Op1, Op2 };
6083 return getMachineNode(Opcode, dl, VTs, Ops);
6087 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6088 SDValue Op1, SDValue Op2, SDValue Op3) {
6089 SDVTList VTs = getVTList(VT);
6090 SDValue Ops[] = { Op1, Op2, Op3 };
6091 return getMachineNode(Opcode, dl, VTs, Ops);
6095 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6096 ArrayRef<SDValue> Ops) {
6097 SDVTList VTs = getVTList(VT);
6098 return getMachineNode(Opcode, dl, VTs, Ops);
6102 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6103 SDVTList VTs = getVTList(VT1, VT2);
6104 return getMachineNode(Opcode, dl, VTs, None);
6108 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6109 EVT VT1, EVT VT2, SDValue Op1) {
6110 SDVTList VTs = getVTList(VT1, VT2);
6111 SDValue Ops[] = { Op1 };
6112 return getMachineNode(Opcode, dl, VTs, Ops);
6116 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6117 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6118 SDVTList VTs = getVTList(VT1, VT2);
6119 SDValue Ops[] = { Op1, Op2 };
6120 return getMachineNode(Opcode, dl, VTs, Ops);
6124 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6125 EVT VT1, EVT VT2, SDValue Op1,
6126 SDValue Op2, SDValue Op3) {
6127 SDVTList VTs = getVTList(VT1, VT2);
6128 SDValue Ops[] = { Op1, Op2, Op3 };
6129 return getMachineNode(Opcode, dl, VTs, Ops);
6133 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6135 ArrayRef<SDValue> Ops) {
6136 SDVTList VTs = getVTList(VT1, VT2);
6137 return getMachineNode(Opcode, dl, VTs, Ops);
6141 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6142 EVT VT1, EVT VT2, EVT VT3,
6143 SDValue Op1, SDValue Op2) {
6144 SDVTList VTs = getVTList(VT1, VT2, VT3);
6145 SDValue Ops[] = { Op1, Op2 };
6146 return getMachineNode(Opcode, dl, VTs, Ops);
6150 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6151 EVT VT1, EVT VT2, EVT VT3,
6152 SDValue Op1, SDValue Op2, SDValue Op3) {
6153 SDVTList VTs = getVTList(VT1, VT2, VT3);
6154 SDValue Ops[] = { Op1, Op2, Op3 };
6155 return getMachineNode(Opcode, dl, VTs, Ops);
6159 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6160 EVT VT1, EVT VT2, EVT VT3,
6161 ArrayRef<SDValue> Ops) {
6162 SDVTList VTs = getVTList(VT1, VT2, VT3);
6163 return getMachineNode(Opcode, dl, VTs, Ops);
6167 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6168 EVT VT2, EVT VT3, EVT VT4,
6169 ArrayRef<SDValue> Ops) {
6170 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6171 return getMachineNode(Opcode, dl, VTs, Ops);
6175 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6176 ArrayRef<EVT> ResultTys,
6177 ArrayRef<SDValue> Ops) {
6178 SDVTList VTs = getVTList(ResultTys);
6179 return getMachineNode(Opcode, dl, VTs, Ops);
6183 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6184 ArrayRef<SDValue> OpsArray) {
6185 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6188 const SDValue *Ops = OpsArray.data();
6189 unsigned NumOps = OpsArray.size();
6192 FoldingSetNodeID ID;
6193 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6195 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6196 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6200 // Allocate a new MachineSDNode.
6201 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6202 DL.getDebugLoc(), VTs);
6204 // Initialize the operands list.
6205 if (NumOps > array_lengthof(N->LocalOperands))
6206 // We're creating a final node that will live unmorphed for the
6207 // remainder of the current SelectionDAG iteration, so we can allocate
6208 // the operands directly out of a pool with no recycling metadata.
6209 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6212 N->InitOperands(N->LocalOperands, Ops, NumOps);
6213 N->OperandsNeedDelete = false;
6216 CSEMap.InsertNode(N, IP);
6222 /// getTargetExtractSubreg - A convenience function for creating
6223 /// TargetOpcode::EXTRACT_SUBREG nodes.
6225 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6227 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6228 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6229 VT, Operand, SRIdxVal);
6230 return SDValue(Subreg, 0);
6233 /// getTargetInsertSubreg - A convenience function for creating
6234 /// TargetOpcode::INSERT_SUBREG nodes.
6236 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6237 SDValue Operand, SDValue Subreg) {
6238 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6239 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6240 VT, Operand, Subreg, SRIdxVal);
6241 return SDValue(Result, 0);
6244 /// getNodeIfExists - Get the specified node if it's already available, or
6245 /// else return NULL.
6246 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6247 ArrayRef<SDValue> Ops,
6248 const SDNodeFlags *Flags) {
6249 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6250 FoldingSetNodeID ID;
6251 AddNodeIDNode(ID, Opcode, VTList, Ops);
6252 AddNodeIDFlags(ID, Opcode, Flags);
6254 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6260 /// getDbgValue - Creates a SDDbgValue node.
6263 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6264 unsigned R, bool IsIndirect, uint64_t Off,
6265 DebugLoc DL, unsigned O) {
6266 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6267 "Expected inlined-at fields to agree");
6268 return new (DbgInfo->getAlloc())
6269 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6273 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6274 const Value *C, uint64_t Off,
6275 DebugLoc DL, unsigned O) {
6276 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6277 "Expected inlined-at fields to agree");
6278 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6282 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6283 unsigned FI, uint64_t Off,
6284 DebugLoc DL, unsigned O) {
6285 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6286 "Expected inlined-at fields to agree");
6287 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6292 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6293 /// pointed to by a use iterator is deleted, increment the use iterator
6294 /// so that it doesn't dangle.
6296 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6297 SDNode::use_iterator &UI;
6298 SDNode::use_iterator &UE;
6300 void NodeDeleted(SDNode *N, SDNode *E) override {
6301 // Increment the iterator as needed.
6302 while (UI != UE && N == *UI)
6307 RAUWUpdateListener(SelectionDAG &d,
6308 SDNode::use_iterator &ui,
6309 SDNode::use_iterator &ue)
6310 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6315 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6316 /// This can cause recursive merging of nodes in the DAG.
6318 /// This version assumes From has a single result value.
6320 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6321 SDNode *From = FromN.getNode();
6322 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6323 "Cannot replace with this method!");
6324 assert(From != To.getNode() && "Cannot replace uses of with self");
6326 // Iterate over all the existing uses of From. New uses will be added
6327 // to the beginning of the use list, which we avoid visiting.
6328 // This specifically avoids visiting uses of From that arise while the
6329 // replacement is happening, because any such uses would be the result
6330 // of CSE: If an existing node looks like From after one of its operands
6331 // is replaced by To, we don't want to replace of all its users with To
6332 // too. See PR3018 for more info.
6333 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6334 RAUWUpdateListener Listener(*this, UI, UE);
6338 // This node is about to morph, remove its old self from the CSE maps.
6339 RemoveNodeFromCSEMaps(User);
6341 // A user can appear in a use list multiple times, and when this
6342 // happens the uses are usually next to each other in the list.
6343 // To help reduce the number of CSE recomputations, process all
6344 // the uses of this user that we can find this way.
6346 SDUse &Use = UI.getUse();
6349 } while (UI != UE && *UI == User);
6351 // Now that we have modified User, add it back to the CSE maps. If it
6352 // already exists there, recursively merge the results together.
6353 AddModifiedNodeToCSEMaps(User);
6356 // If we just RAUW'd the root, take note.
6357 if (FromN == getRoot())
6361 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6362 /// This can cause recursive merging of nodes in the DAG.
6364 /// This version assumes that for each value of From, there is a
6365 /// corresponding value in To in the same position with the same type.
6367 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6369 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6370 assert((!From->hasAnyUseOfValue(i) ||
6371 From->getValueType(i) == To->getValueType(i)) &&
6372 "Cannot use this version of ReplaceAllUsesWith!");
6375 // Handle the trivial case.
6379 // Iterate over just the existing users of From. See the comments in
6380 // the ReplaceAllUsesWith above.
6381 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6382 RAUWUpdateListener Listener(*this, UI, UE);
6386 // This node is about to morph, remove its old self from the CSE maps.
6387 RemoveNodeFromCSEMaps(User);
6389 // A user can appear in a use list multiple times, and when this
6390 // happens the uses are usually next to each other in the list.
6391 // To help reduce the number of CSE recomputations, process all
6392 // the uses of this user that we can find this way.
6394 SDUse &Use = UI.getUse();
6397 } while (UI != UE && *UI == User);
6399 // Now that we have modified User, add it back to the CSE maps. If it
6400 // already exists there, recursively merge the results together.
6401 AddModifiedNodeToCSEMaps(User);
6404 // If we just RAUW'd the root, take note.
6405 if (From == getRoot().getNode())
6406 setRoot(SDValue(To, getRoot().getResNo()));
6409 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6410 /// This can cause recursive merging of nodes in the DAG.
6412 /// This version can replace From with any result values. To must match the
6413 /// number and types of values returned by From.
6414 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6415 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6416 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6418 // Iterate over just the existing users of From. See the comments in
6419 // the ReplaceAllUsesWith above.
6420 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6421 RAUWUpdateListener Listener(*this, UI, UE);
6425 // This node is about to morph, remove its old self from the CSE maps.
6426 RemoveNodeFromCSEMaps(User);
6428 // A user can appear in a use list multiple times, and when this
6429 // happens the uses are usually next to each other in the list.
6430 // To help reduce the number of CSE recomputations, process all
6431 // the uses of this user that we can find this way.
6433 SDUse &Use = UI.getUse();
6434 const SDValue &ToOp = To[Use.getResNo()];
6437 } while (UI != UE && *UI == User);
6439 // Now that we have modified User, add it back to the CSE maps. If it
6440 // already exists there, recursively merge the results together.
6441 AddModifiedNodeToCSEMaps(User);
6444 // If we just RAUW'd the root, take note.
6445 if (From == getRoot().getNode())
6446 setRoot(SDValue(To[getRoot().getResNo()]));
6449 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6450 /// uses of other values produced by From.getNode() alone. The Deleted
6451 /// vector is handled the same way as for ReplaceAllUsesWith.
6452 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6453 // Handle the really simple, really trivial case efficiently.
6454 if (From == To) return;
6456 // Handle the simple, trivial, case efficiently.
6457 if (From.getNode()->getNumValues() == 1) {
6458 ReplaceAllUsesWith(From, To);
6462 // Iterate over just the existing users of From. See the comments in
6463 // the ReplaceAllUsesWith above.
6464 SDNode::use_iterator UI = From.getNode()->use_begin(),
6465 UE = From.getNode()->use_end();
6466 RAUWUpdateListener Listener(*this, UI, UE);
6469 bool UserRemovedFromCSEMaps = false;
6471 // A user can appear in a use list multiple times, and when this
6472 // happens the uses are usually next to each other in the list.
6473 // To help reduce the number of CSE recomputations, process all
6474 // the uses of this user that we can find this way.
6476 SDUse &Use = UI.getUse();
6478 // Skip uses of different values from the same node.
6479 if (Use.getResNo() != From.getResNo()) {
6484 // If this node hasn't been modified yet, it's still in the CSE maps,
6485 // so remove its old self from the CSE maps.
6486 if (!UserRemovedFromCSEMaps) {
6487 RemoveNodeFromCSEMaps(User);
6488 UserRemovedFromCSEMaps = true;
6493 } while (UI != UE && *UI == User);
6495 // We are iterating over all uses of the From node, so if a use
6496 // doesn't use the specific value, no changes are made.
6497 if (!UserRemovedFromCSEMaps)
6500 // Now that we have modified User, add it back to the CSE maps. If it
6501 // already exists there, recursively merge the results together.
6502 AddModifiedNodeToCSEMaps(User);
6505 // If we just RAUW'd the root, take note.
6506 if (From == getRoot())
6511 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6512 /// to record information about a use.
6519 /// operator< - Sort Memos by User.
6520 bool operator<(const UseMemo &L, const UseMemo &R) {
6521 return (intptr_t)L.User < (intptr_t)R.User;
6525 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6526 /// uses of other values produced by From.getNode() alone. The same value
6527 /// may appear in both the From and To list. The Deleted vector is
6528 /// handled the same way as for ReplaceAllUsesWith.
6529 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6532 // Handle the simple, trivial case efficiently.
6534 return ReplaceAllUsesOfValueWith(*From, *To);
6536 // Read up all the uses and make records of them. This helps
6537 // processing new uses that are introduced during the
6538 // replacement process.
6539 SmallVector<UseMemo, 4> Uses;
6540 for (unsigned i = 0; i != Num; ++i) {
6541 unsigned FromResNo = From[i].getResNo();
6542 SDNode *FromNode = From[i].getNode();
6543 for (SDNode::use_iterator UI = FromNode->use_begin(),
6544 E = FromNode->use_end(); UI != E; ++UI) {
6545 SDUse &Use = UI.getUse();
6546 if (Use.getResNo() == FromResNo) {
6547 UseMemo Memo = { *UI, i, &Use };
6548 Uses.push_back(Memo);
6553 // Sort the uses, so that all the uses from a given User are together.
6554 std::sort(Uses.begin(), Uses.end());
6556 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6557 UseIndex != UseIndexEnd; ) {
6558 // We know that this user uses some value of From. If it is the right
6559 // value, update it.
6560 SDNode *User = Uses[UseIndex].User;
6562 // This node is about to morph, remove its old self from the CSE maps.
6563 RemoveNodeFromCSEMaps(User);
6565 // The Uses array is sorted, so all the uses for a given User
6566 // are next to each other in the list.
6567 // To help reduce the number of CSE recomputations, process all
6568 // the uses of this user that we can find this way.
6570 unsigned i = Uses[UseIndex].Index;
6571 SDUse &Use = *Uses[UseIndex].Use;
6575 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6577 // Now that we have modified User, add it back to the CSE maps. If it
6578 // already exists there, recursively merge the results together.
6579 AddModifiedNodeToCSEMaps(User);
6583 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6584 /// based on their topological order. It returns the maximum id and a vector
6585 /// of the SDNodes* in assigned order by reference.
6586 unsigned SelectionDAG::AssignTopologicalOrder() {
6588 unsigned DAGSize = 0;
6590 // SortedPos tracks the progress of the algorithm. Nodes before it are
6591 // sorted, nodes after it are unsorted. When the algorithm completes
6592 // it is at the end of the list.
6593 allnodes_iterator SortedPos = allnodes_begin();
6595 // Visit all the nodes. Move nodes with no operands to the front of
6596 // the list immediately. Annotate nodes that do have operands with their
6597 // operand count. Before we do this, the Node Id fields of the nodes
6598 // may contain arbitrary values. After, the Node Id fields for nodes
6599 // before SortedPos will contain the topological sort index, and the
6600 // Node Id fields for nodes At SortedPos and after will contain the
6601 // count of outstanding operands.
6602 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6604 checkForCycles(N, this);
6605 unsigned Degree = N->getNumOperands();
6607 // A node with no uses, add it to the result array immediately.
6608 N->setNodeId(DAGSize++);
6609 allnodes_iterator Q(N);
6611 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6612 assert(SortedPos != AllNodes.end() && "Overran node list");
6615 // Temporarily use the Node Id as scratch space for the degree count.
6616 N->setNodeId(Degree);
6620 // Visit all the nodes. As we iterate, move nodes into sorted order,
6621 // such that by the time the end is reached all nodes will be sorted.
6622 for (SDNode &Node : allnodes()) {
6624 checkForCycles(N, this);
6625 // N is in sorted position, so all its uses have one less operand
6626 // that needs to be sorted.
6627 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6630 unsigned Degree = P->getNodeId();
6631 assert(Degree != 0 && "Invalid node degree");
6634 // All of P's operands are sorted, so P may sorted now.
6635 P->setNodeId(DAGSize++);
6637 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6638 assert(SortedPos != AllNodes.end() && "Overran node list");
6641 // Update P's outstanding operand count.
6642 P->setNodeId(Degree);
6645 if (&Node == SortedPos) {
6647 allnodes_iterator I(N);
6649 dbgs() << "Overran sorted position:\n";
6650 S->dumprFull(this); dbgs() << "\n";
6651 dbgs() << "Checking if this is due to cycles\n";
6652 checkForCycles(this, true);
6654 llvm_unreachable(nullptr);
6658 assert(SortedPos == AllNodes.end() &&
6659 "Topological sort incomplete!");
6660 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6661 "First node in topological sort is not the entry token!");
6662 assert(AllNodes.front().getNodeId() == 0 &&
6663 "First node in topological sort has non-zero id!");
6664 assert(AllNodes.front().getNumOperands() == 0 &&
6665 "First node in topological sort has operands!");
6666 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6667 "Last node in topologic sort has unexpected id!");
6668 assert(AllNodes.back().use_empty() &&
6669 "Last node in topologic sort has users!");
6670 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6674 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6675 /// value is produced by SD.
6676 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6678 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6679 SD->setHasDebugValue(true);
6681 DbgInfo->add(DB, SD, isParameter);
6684 /// TransferDbgValues - Transfer SDDbgValues.
6685 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6686 if (From == To || !From.getNode()->getHasDebugValue())
6688 SDNode *FromNode = From.getNode();
6689 SDNode *ToNode = To.getNode();
6690 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6691 SmallVector<SDDbgValue *, 2> ClonedDVs;
6692 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6694 SDDbgValue *Dbg = *I;
6695 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6697 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6698 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6699 Dbg->getDebugLoc(), Dbg->getOrder());
6700 ClonedDVs.push_back(Clone);
6703 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6704 E = ClonedDVs.end(); I != E; ++I)
6705 AddDbgValue(*I, ToNode, false);
6708 //===----------------------------------------------------------------------===//
6710 //===----------------------------------------------------------------------===//
6712 bool llvm::isNullConstant(SDValue V) {
6713 ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
6714 return Const != nullptr && Const->isNullValue();
6717 bool llvm::isNullFPConstant(SDValue V) {
6718 ConstantFPSDNode *Const = dyn_cast<ConstantFPSDNode>(V);
6719 return Const != nullptr && Const->isZero() && !Const->isNegative();
6722 bool llvm::isAllOnesConstant(SDValue V) {
6723 ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
6724 return Const != nullptr && Const->isAllOnesValue();
6727 bool llvm::isOneConstant(SDValue V) {
6728 ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
6729 return Const != nullptr && Const->isOne();
6732 HandleSDNode::~HandleSDNode() {
6736 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6737 DebugLoc DL, const GlobalValue *GA,
6738 EVT VT, int64_t o, unsigned char TF)
6739 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6743 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6744 SDValue X, unsigned SrcAS,
6746 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6747 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6749 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6750 EVT memvt, MachineMemOperand *mmo)
6751 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6752 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6753 MMO->isNonTemporal(), MMO->isInvariant());
6754 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6755 assert(isNonTemporal() == MMO->isNonTemporal() &&
6756 "Non-temporal encoding error!");
6757 // We check here that the size of the memory operand fits within the size of
6758 // the MMO. This is because the MMO might indicate only a possible address
6759 // range instead of specifying the affected memory addresses precisely.
6760 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6763 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6764 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6765 : SDNode(Opc, Order, dl, VTs, Ops),
6766 MemoryVT(memvt), MMO(mmo) {
6767 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6768 MMO->isNonTemporal(), MMO->isInvariant());
6769 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6770 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6773 /// Profile - Gather unique data for the node.
6775 void SDNode::Profile(FoldingSetNodeID &ID) const {
6776 AddNodeIDNode(ID, this);
6781 std::vector<EVT> VTs;
6784 VTs.reserve(MVT::LAST_VALUETYPE);
6785 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6786 VTs.push_back(MVT((MVT::SimpleValueType)i));
6791 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6792 static ManagedStatic<EVTArray> SimpleVTArray;
6793 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6795 /// getValueTypeList - Return a pointer to the specified value type.
6797 const EVT *SDNode::getValueTypeList(EVT VT) {
6798 if (VT.isExtended()) {
6799 sys::SmartScopedLock<true> Lock(*VTMutex);
6800 return &(*EVTs->insert(VT).first);
6802 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6803 "Value type out of range!");
6804 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6808 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6809 /// indicated value. This method ignores uses of other values defined by this
6811 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6812 assert(Value < getNumValues() && "Bad value!");
6814 // TODO: Only iterate over uses of a given value of the node
6815 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6816 if (UI.getUse().getResNo() == Value) {
6823 // Found exactly the right number of uses?
6828 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6829 /// value. This method ignores uses of other values defined by this operation.
6830 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6831 assert(Value < getNumValues() && "Bad value!");
6833 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6834 if (UI.getUse().getResNo() == Value)
6841 /// isOnlyUserOf - Return true if this node is the only use of N.
6843 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6845 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6856 /// isOperand - Return true if this node is an operand of N.
6858 bool SDValue::isOperandOf(const SDNode *N) const {
6859 for (const SDValue &Op : N->op_values())
6865 bool SDNode::isOperandOf(const SDNode *N) const {
6866 for (const SDValue &Op : N->op_values())
6867 if (this == Op.getNode())
6872 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6873 /// be a chain) reaches the specified operand without crossing any
6874 /// side-effecting instructions on any chain path. In practice, this looks
6875 /// through token factors and non-volatile loads. In order to remain efficient,
6876 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6877 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6878 unsigned Depth) const {
6879 if (*this == Dest) return true;
6881 // Don't search too deeply, we just want to be able to see through
6882 // TokenFactor's etc.
6883 if (Depth == 0) return false;
6885 // If this is a token factor, all inputs to the TF happen in parallel. If any
6886 // of the operands of the TF does not reach dest, then we cannot do the xform.
6887 if (getOpcode() == ISD::TokenFactor) {
6888 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6889 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6894 // Loads don't have side effects, look through them.
6895 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6896 if (!Ld->isVolatile())
6897 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6902 /// hasPredecessor - Return true if N is a predecessor of this node.
6903 /// N is either an operand of this node, or can be reached by recursively
6904 /// traversing up the operands.
6905 /// NOTE: This is an expensive method. Use it carefully.
6906 bool SDNode::hasPredecessor(const SDNode *N) const {
6907 SmallPtrSet<const SDNode *, 32> Visited;
6908 SmallVector<const SDNode *, 16> Worklist;
6909 return hasPredecessorHelper(N, Visited, Worklist);
6913 SDNode::hasPredecessorHelper(const SDNode *N,
6914 SmallPtrSetImpl<const SDNode *> &Visited,
6915 SmallVectorImpl<const SDNode *> &Worklist) const {
6916 if (Visited.empty()) {
6917 Worklist.push_back(this);
6919 // Take a look in the visited set. If we've already encountered this node
6920 // we needn't search further.
6921 if (Visited.count(N))
6925 // Haven't visited N yet. Continue the search.
6926 while (!Worklist.empty()) {
6927 const SDNode *M = Worklist.pop_back_val();
6928 for (const SDValue &OpV : M->op_values()) {
6929 SDNode *Op = OpV.getNode();
6930 if (Visited.insert(Op).second)
6931 Worklist.push_back(Op);
6940 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6941 assert(Num < NumOperands && "Invalid child # of SDNode!");
6942 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6945 const SDNodeFlags *SDNode::getFlags() const {
6946 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6947 return &FlagsNode->Flags;
6951 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6952 assert(N->getNumValues() == 1 &&
6953 "Can't unroll a vector with multiple results!");
6955 EVT VT = N->getValueType(0);
6956 unsigned NE = VT.getVectorNumElements();
6957 EVT EltVT = VT.getVectorElementType();
6960 SmallVector<SDValue, 8> Scalars;
6961 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6963 // If ResNE is 0, fully unroll the vector op.
6966 else if (NE > ResNE)
6970 for (i= 0; i != NE; ++i) {
6971 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6972 SDValue Operand = N->getOperand(j);
6973 EVT OperandVT = Operand.getValueType();
6974 if (OperandVT.isVector()) {
6975 // A vector operand; extract a single element.
6976 EVT OperandEltVT = OperandVT.getVectorElementType();
6978 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6979 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6981 // A scalar operand; just use it as is.
6982 Operands[j] = Operand;
6986 switch (N->getOpcode()) {
6988 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6993 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
7000 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
7001 getShiftAmountOperand(Operands[0].getValueType(),
7004 case ISD::SIGN_EXTEND_INREG:
7005 case ISD::FP_ROUND_INREG: {
7006 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
7007 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
7009 getValueType(ExtVT)));
7014 for (; i < ResNE; ++i)
7015 Scalars.push_back(getUNDEF(EltVT));
7017 return getNode(ISD::BUILD_VECTOR, dl,
7018 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
7022 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
7023 /// location that is 'Dist' units away from the location that the 'Base' load
7024 /// is loading from.
7025 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
7026 unsigned Bytes, int Dist) const {
7027 if (LD->getChain() != Base->getChain())
7029 EVT VT = LD->getValueType(0);
7030 if (VT.getSizeInBits() / 8 != Bytes)
7033 SDValue Loc = LD->getOperand(1);
7034 SDValue BaseLoc = Base->getOperand(1);
7035 if (Loc.getOpcode() == ISD::FrameIndex) {
7036 if (BaseLoc.getOpcode() != ISD::FrameIndex)
7038 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
7039 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
7040 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
7041 int FS = MFI->getObjectSize(FI);
7042 int BFS = MFI->getObjectSize(BFI);
7043 if (FS != BFS || FS != (int)Bytes) return false;
7044 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
7048 if (isBaseWithConstantOffset(Loc)) {
7049 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
7050 if (Loc.getOperand(0) == BaseLoc) {
7051 // If the base location is a simple address with no offset itself, then
7052 // the second load's first add operand should be the base address.
7053 if (LocOffset == Dist * (int)Bytes)
7055 } else if (isBaseWithConstantOffset(BaseLoc)) {
7056 // The base location itself has an offset, so subtract that value from the
7057 // second load's offset before comparing to distance * size.
7059 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
7060 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
7061 if ((LocOffset - BOffset) == Dist * (int)Bytes)
7066 const GlobalValue *GV1 = nullptr;
7067 const GlobalValue *GV2 = nullptr;
7068 int64_t Offset1 = 0;
7069 int64_t Offset2 = 0;
7070 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
7071 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
7072 if (isGA1 && isGA2 && GV1 == GV2)
7073 return Offset1 == (Offset2 + Dist*Bytes);
7078 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
7079 /// it cannot be inferred.
7080 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
7081 // If this is a GlobalAddress + cst, return the alignment.
7082 const GlobalValue *GV;
7083 int64_t GVOffset = 0;
7084 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
7085 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
7086 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
7087 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7089 unsigned AlignBits = KnownZero.countTrailingOnes();
7090 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7092 return MinAlign(Align, GVOffset);
7095 // If this is a direct reference to a stack slot, use information about the
7096 // stack slot's alignment.
7097 int FrameIdx = 1 << 31;
7098 int64_t FrameOffset = 0;
7099 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7100 FrameIdx = FI->getIndex();
7101 } else if (isBaseWithConstantOffset(Ptr) &&
7102 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7104 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7105 FrameOffset = Ptr.getConstantOperandVal(1);
7108 if (FrameIdx != (1 << 31)) {
7109 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7110 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7118 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7119 /// which is split (or expanded) into two not necessarily identical pieces.
7120 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7121 // Currently all types are split in half.
7123 if (!VT.isVector()) {
7124 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7126 unsigned NumElements = VT.getVectorNumElements();
7127 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7128 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7131 return std::make_pair(LoVT, HiVT);
7134 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7136 std::pair<SDValue, SDValue>
7137 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7139 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7140 N.getValueType().getVectorNumElements() &&
7141 "More vector elements requested than available!");
7143 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7144 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7145 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7146 getConstant(LoVT.getVectorNumElements(), DL,
7147 TLI->getVectorIdxTy(getDataLayout())));
7148 return std::make_pair(Lo, Hi);
7151 void SelectionDAG::ExtractVectorElements(SDValue Op,
7152 SmallVectorImpl<SDValue> &Args,
7153 unsigned Start, unsigned Count) {
7154 EVT VT = Op.getValueType();
7156 Count = VT.getVectorNumElements();
7158 EVT EltVT = VT.getVectorElementType();
7159 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7161 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7162 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7163 Op, getConstant(i, SL, IdxTy)));
7167 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7168 unsigned GlobalAddressSDNode::getAddressSpace() const {
7169 return getGlobal()->getType()->getAddressSpace();
7173 Type *ConstantPoolSDNode::getType() const {
7174 if (isMachineConstantPoolEntry())
7175 return Val.MachineCPVal->getType();
7176 return Val.ConstVal->getType();
7179 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7181 unsigned &SplatBitSize,
7183 unsigned MinSplatBits,
7184 bool isBigEndian) const {
7185 EVT VT = getValueType(0);
7186 assert(VT.isVector() && "Expected a vector type");
7187 unsigned sz = VT.getSizeInBits();
7188 if (MinSplatBits > sz)
7191 SplatValue = APInt(sz, 0);
7192 SplatUndef = APInt(sz, 0);
7194 // Get the bits. Bits with undefined values (when the corresponding element
7195 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7196 // in SplatValue. If any of the values are not constant, give up and return
7198 unsigned int nOps = getNumOperands();
7199 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7200 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7202 for (unsigned j = 0; j < nOps; ++j) {
7203 unsigned i = isBigEndian ? nOps-1-j : j;
7204 SDValue OpVal = getOperand(i);
7205 unsigned BitPos = j * EltBitSize;
7207 if (OpVal.getOpcode() == ISD::UNDEF)
7208 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7209 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7210 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7211 zextOrTrunc(sz) << BitPos;
7212 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7213 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7218 // The build_vector is all constants or undefs. Find the smallest element
7219 // size that splats the vector.
7221 HasAnyUndefs = (SplatUndef != 0);
7224 unsigned HalfSize = sz / 2;
7225 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7226 APInt LowValue = SplatValue.trunc(HalfSize);
7227 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7228 APInt LowUndef = SplatUndef.trunc(HalfSize);
7230 // If the two halves do not match (ignoring undef bits), stop here.
7231 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7232 MinSplatBits > HalfSize)
7235 SplatValue = HighValue | LowValue;
7236 SplatUndef = HighUndef & LowUndef;
7245 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7246 if (UndefElements) {
7247 UndefElements->clear();
7248 UndefElements->resize(getNumOperands());
7251 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7252 SDValue Op = getOperand(i);
7253 if (Op.getOpcode() == ISD::UNDEF) {
7255 (*UndefElements)[i] = true;
7256 } else if (!Splatted) {
7258 } else if (Splatted != Op) {
7264 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7265 "Can only have a splat without a constant for all undefs.");
7266 return getOperand(0);
7273 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7274 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7278 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7279 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7283 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7284 uint32_t BitWidth) const {
7285 if (ConstantFPSDNode *CN =
7286 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7288 APSInt IntVal(BitWidth);
7289 APFloat APF = CN->getValueAPF();
7290 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7295 return IntVal.exactLogBase2();
7300 bool BuildVectorSDNode::isConstant() const {
7301 for (const SDValue &Op : op_values()) {
7302 unsigned Opc = Op.getOpcode();
7303 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7309 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7310 // Find the first non-undef value in the shuffle mask.
7312 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7315 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7317 // Make sure all remaining elements are either undef or the same as the first
7319 for (int Idx = Mask[i]; i != e; ++i)
7320 if (Mask[i] >= 0 && Mask[i] != Idx)
7326 static void checkForCyclesHelper(const SDNode *N,
7327 SmallPtrSetImpl<const SDNode*> &Visited,
7328 SmallPtrSetImpl<const SDNode*> &Checked,
7329 const llvm::SelectionDAG *DAG) {
7330 // If this node has already been checked, don't check it again.
7331 if (Checked.count(N))
7334 // If a node has already been visited on this depth-first walk, reject it as
7336 if (!Visited.insert(N).second) {
7337 errs() << "Detected cycle in SelectionDAG\n";
7338 dbgs() << "Offending node:\n";
7339 N->dumprFull(DAG); dbgs() << "\n";
7343 for (const SDValue &Op : N->op_values())
7344 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7351 void llvm::checkForCycles(const llvm::SDNode *N,
7352 const llvm::SelectionDAG *DAG,
7360 assert(N && "Checking nonexistent SDNode");
7361 SmallPtrSet<const SDNode*, 32> visited;
7362 SmallPtrSet<const SDNode*, 32> checked;
7363 checkForCyclesHelper(N, visited, checked, DAG);
7368 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7369 checkForCycles(DAG->getRoot().getNode(), DAG, force);