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::getBasicBlock(MachineBasicBlock *MBB) {
1402 FoldingSetNodeID ID;
1403 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1406 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1407 return SDValue(E, 0);
1409 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1410 CSEMap.InsertNode(N, IP);
1412 return SDValue(N, 0);
1415 SDValue SelectionDAG::getValueType(EVT VT) {
1416 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1417 ValueTypeNodes.size())
1418 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1420 SDNode *&N = VT.isExtended() ?
1421 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1423 if (N) return SDValue(N, 0);
1424 N = new (NodeAllocator) VTSDNode(VT);
1426 return SDValue(N, 0);
1429 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1430 SDNode *&N = ExternalSymbols[Sym];
1431 if (N) return SDValue(N, 0);
1432 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1434 return SDValue(N, 0);
1437 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1438 SDNode *&N = MCSymbols[Sym];
1440 return SDValue(N, 0);
1441 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1443 return SDValue(N, 0);
1446 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1447 unsigned char TargetFlags) {
1449 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1451 if (N) return SDValue(N, 0);
1452 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1454 return SDValue(N, 0);
1457 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1458 if ((unsigned)Cond >= CondCodeNodes.size())
1459 CondCodeNodes.resize(Cond+1);
1461 if (!CondCodeNodes[Cond]) {
1462 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1463 CondCodeNodes[Cond] = N;
1467 return SDValue(CondCodeNodes[Cond], 0);
1470 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1471 // the shuffle mask M that point at N1 to point at N2, and indices that point
1472 // N2 to point at N1.
1473 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1475 ShuffleVectorSDNode::commuteMask(M);
1478 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1479 SDValue N2, const int *Mask) {
1480 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1481 "Invalid VECTOR_SHUFFLE");
1483 // Canonicalize shuffle undef, undef -> undef
1484 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1485 return getUNDEF(VT);
1487 // Validate that all indices in Mask are within the range of the elements
1488 // input to the shuffle.
1489 unsigned NElts = VT.getVectorNumElements();
1490 SmallVector<int, 8> MaskVec;
1491 for (unsigned i = 0; i != NElts; ++i) {
1492 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1493 MaskVec.push_back(Mask[i]);
1496 // Canonicalize shuffle v, v -> v, undef
1499 for (unsigned i = 0; i != NElts; ++i)
1500 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1503 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1504 if (N1.getOpcode() == ISD::UNDEF)
1505 commuteShuffle(N1, N2, MaskVec);
1507 // If shuffling a splat, try to blend the splat instead. We do this here so
1508 // that even when this arises during lowering we don't have to re-handle it.
1509 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1510 BitVector UndefElements;
1511 SDValue Splat = BV->getSplatValue(&UndefElements);
1515 for (int i = 0; i < (int)NElts; ++i) {
1516 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1519 // If this input comes from undef, mark it as such.
1520 if (UndefElements[MaskVec[i] - Offset]) {
1525 // If we can blend a non-undef lane, use that instead.
1526 if (!UndefElements[i])
1527 MaskVec[i] = i + Offset;
1530 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1531 BlendSplat(N1BV, 0);
1532 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1533 BlendSplat(N2BV, NElts);
1535 // Canonicalize all index into lhs, -> shuffle lhs, undef
1536 // Canonicalize all index into rhs, -> shuffle rhs, undef
1537 bool AllLHS = true, AllRHS = true;
1538 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1539 for (unsigned i = 0; i != NElts; ++i) {
1540 if (MaskVec[i] >= (int)NElts) {
1545 } else if (MaskVec[i] >= 0) {
1549 if (AllLHS && AllRHS)
1550 return getUNDEF(VT);
1551 if (AllLHS && !N2Undef)
1555 commuteShuffle(N1, N2, MaskVec);
1557 // Reset our undef status after accounting for the mask.
1558 N2Undef = N2.getOpcode() == ISD::UNDEF;
1559 // Re-check whether both sides ended up undef.
1560 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1561 return getUNDEF(VT);
1563 // If Identity shuffle return that node.
1564 bool Identity = true, AllSame = true;
1565 for (unsigned i = 0; i != NElts; ++i) {
1566 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1567 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1569 if (Identity && NElts)
1572 // Shuffling a constant splat doesn't change the result.
1576 // Look through any bitcasts. We check that these don't change the number
1577 // (and size) of elements and just changes their types.
1578 while (V.getOpcode() == ISD::BITCAST)
1579 V = V->getOperand(0);
1581 // A splat should always show up as a build vector node.
1582 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1583 BitVector UndefElements;
1584 SDValue Splat = BV->getSplatValue(&UndefElements);
1585 // If this is a splat of an undef, shuffling it is also undef.
1586 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1587 return getUNDEF(VT);
1590 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1592 // We only have a splat which can skip shuffles if there is a splatted
1593 // value and no undef lanes rearranged by the shuffle.
1594 if (Splat && UndefElements.none()) {
1595 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1596 // number of elements match or the value splatted is a zero constant.
1599 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1600 if (C->isNullValue())
1604 // If the shuffle itself creates a splat, build the vector directly.
1605 if (AllSame && SameNumElts) {
1606 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1607 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1609 EVT BuildVT = BV->getValueType(0);
1610 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1612 // We may have jumped through bitcasts, so the type of the
1613 // BUILD_VECTOR may not match the type of the shuffle.
1615 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1621 FoldingSetNodeID ID;
1622 SDValue Ops[2] = { N1, N2 };
1623 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1624 for (unsigned i = 0; i != NElts; ++i)
1625 ID.AddInteger(MaskVec[i]);
1628 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1629 return SDValue(E, 0);
1631 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1632 // SDNode doesn't have access to it. This memory will be "leaked" when
1633 // the node is deallocated, but recovered when the NodeAllocator is released.
1634 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1635 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1637 ShuffleVectorSDNode *N =
1638 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1639 dl.getDebugLoc(), N1, N2,
1641 CSEMap.InsertNode(N, IP);
1643 return SDValue(N, 0);
1646 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1647 MVT VT = SV.getSimpleValueType(0);
1648 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1649 ShuffleVectorSDNode::commuteMask(MaskVec);
1651 SDValue Op0 = SV.getOperand(0);
1652 SDValue Op1 = SV.getOperand(1);
1653 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1656 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1657 SDValue Val, SDValue DTy,
1658 SDValue STy, SDValue Rnd, SDValue Sat,
1659 ISD::CvtCode Code) {
1660 // If the src and dest types are the same and the conversion is between
1661 // integer types of the same sign or two floats, no conversion is necessary.
1663 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1666 FoldingSetNodeID ID;
1667 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1668 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1670 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1671 return SDValue(E, 0);
1673 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1676 CSEMap.InsertNode(N, IP);
1678 return SDValue(N, 0);
1681 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1682 FoldingSetNodeID ID;
1683 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1684 ID.AddInteger(RegNo);
1686 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1687 return SDValue(E, 0);
1689 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1690 CSEMap.InsertNode(N, IP);
1692 return SDValue(N, 0);
1695 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1696 FoldingSetNodeID ID;
1697 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1698 ID.AddPointer(RegMask);
1700 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1701 return SDValue(E, 0);
1703 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1704 CSEMap.InsertNode(N, IP);
1706 return SDValue(N, 0);
1709 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1710 FoldingSetNodeID ID;
1711 SDValue Ops[] = { Root };
1712 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1713 ID.AddPointer(Label);
1715 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1716 return SDValue(E, 0);
1718 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1719 dl.getDebugLoc(), Root, Label);
1720 CSEMap.InsertNode(N, IP);
1722 return SDValue(N, 0);
1726 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1729 unsigned char TargetFlags) {
1730 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1732 FoldingSetNodeID ID;
1733 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1735 ID.AddInteger(Offset);
1736 ID.AddInteger(TargetFlags);
1738 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1739 return SDValue(E, 0);
1741 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1743 CSEMap.InsertNode(N, IP);
1745 return SDValue(N, 0);
1748 SDValue SelectionDAG::getSrcValue(const Value *V) {
1749 assert((!V || V->getType()->isPointerTy()) &&
1750 "SrcValue is not a pointer?");
1752 FoldingSetNodeID ID;
1753 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1757 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1758 return SDValue(E, 0);
1760 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1761 CSEMap.InsertNode(N, IP);
1763 return SDValue(N, 0);
1766 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1767 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1768 FoldingSetNodeID ID;
1769 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1773 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1774 return SDValue(E, 0);
1776 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1777 CSEMap.InsertNode(N, IP);
1779 return SDValue(N, 0);
1782 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1783 if (VT == V.getValueType())
1786 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1789 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1790 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1791 unsigned SrcAS, unsigned DestAS) {
1792 SDValue Ops[] = {Ptr};
1793 FoldingSetNodeID ID;
1794 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1795 ID.AddInteger(SrcAS);
1796 ID.AddInteger(DestAS);
1799 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1800 return SDValue(E, 0);
1802 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1804 VT, Ptr, SrcAS, DestAS);
1805 CSEMap.InsertNode(N, IP);
1807 return SDValue(N, 0);
1810 /// getShiftAmountOperand - Return the specified value casted to
1811 /// the target's desired shift amount type.
1812 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1813 EVT OpTy = Op.getValueType();
1814 EVT ShTy = TLI->getShiftAmountTy(LHSTy, getDataLayout());
1815 if (OpTy == ShTy || OpTy.isVector()) return Op;
1817 return getZExtOrTrunc(Op, SDLoc(Op), ShTy);
1820 SDValue SelectionDAG::expandVAArg(SDNode *Node) {
1822 const TargetLowering &TLI = getTargetLoweringInfo();
1823 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
1824 EVT VT = Node->getValueType(0);
1825 SDValue Tmp1 = Node->getOperand(0);
1826 SDValue Tmp2 = Node->getOperand(1);
1827 unsigned Align = Node->getConstantOperandVal(3);
1829 SDValue VAListLoad =
1830 getLoad(TLI.getPointerTy(getDataLayout()), dl, Tmp1, Tmp2,
1831 MachinePointerInfo(V), false, false, false, 0);
1832 SDValue VAList = VAListLoad;
1834 if (Align > TLI.getMinStackArgumentAlignment()) {
1835 assert(((Align & (Align-1)) == 0) && "Expected Align to be a power of 2");
1837 VAList = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1838 getConstant(Align - 1, dl, VAList.getValueType()));
1840 VAList = getNode(ISD::AND, dl, VAList.getValueType(), VAList,
1841 getConstant(-(int64_t)Align, dl, VAList.getValueType()));
1844 // Increment the pointer, VAList, to the next vaarg
1845 Tmp1 = getNode(ISD::ADD, dl, VAList.getValueType(), VAList,
1846 getConstant(getDataLayout().getTypeAllocSize(
1847 VT.getTypeForEVT(*getContext())),
1848 dl, VAList.getValueType()));
1849 // Store the incremented VAList to the legalized pointer
1850 Tmp1 = getStore(VAListLoad.getValue(1), dl, Tmp1, Tmp2,
1851 MachinePointerInfo(V), false, false, 0);
1852 // Load the actual argument out of the pointer VAList
1853 return getLoad(VT, dl, Tmp1, VAList, MachinePointerInfo(),
1854 false, false, false, 0);
1857 SDValue SelectionDAG::expandVACopy(SDNode *Node) {
1859 const TargetLowering &TLI = getTargetLoweringInfo();
1860 // This defaults to loading a pointer from the input and storing it to the
1861 // output, returning the chain.
1862 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
1863 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
1864 SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
1865 Node->getOperand(0), Node->getOperand(2),
1866 MachinePointerInfo(VS), false, false, false, 0);
1867 return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
1868 MachinePointerInfo(VD), false, false, 0);
1871 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1872 /// specified value type.
1873 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1874 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1875 unsigned ByteSize = VT.getStoreSize();
1876 Type *Ty = VT.getTypeForEVT(*getContext());
1877 unsigned StackAlign =
1878 std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
1880 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1881 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1884 /// CreateStackTemporary - Create a stack temporary suitable for holding
1885 /// either of the specified value types.
1886 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1887 unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
1888 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1889 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1890 const DataLayout &DL = getDataLayout();
1892 std::max(DL.getPrefTypeAlignment(Ty1), DL.getPrefTypeAlignment(Ty2));
1894 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1895 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1896 return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
1899 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1900 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1901 // These setcc operations always fold.
1905 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1907 case ISD::SETTRUE2: {
1908 TargetLowering::BooleanContent Cnt =
1909 TLI->getBooleanContents(N1->getValueType(0));
1911 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1925 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1929 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2)) {
1930 const APInt &C2 = N2C->getAPIntValue();
1931 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
1932 const APInt &C1 = N1C->getAPIntValue();
1935 default: llvm_unreachable("Unknown integer setcc!");
1936 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1937 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1938 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1939 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1940 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1941 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1942 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1943 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1944 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1945 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1949 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1)) {
1950 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2)) {
1951 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1954 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1955 return getUNDEF(VT);
1957 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1958 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1959 return getUNDEF(VT);
1961 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1962 R==APFloat::cmpLessThan, dl, VT);
1963 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1964 return getUNDEF(VT);
1966 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1967 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1968 return getUNDEF(VT);
1970 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1971 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1972 return getUNDEF(VT);
1974 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1975 R==APFloat::cmpEqual, dl, VT);
1976 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1977 return getUNDEF(VT);
1979 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1980 R==APFloat::cmpEqual, dl, VT);
1981 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1982 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1983 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1984 R==APFloat::cmpEqual, dl, VT);
1985 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1986 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1987 R==APFloat::cmpLessThan, dl, VT);
1988 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1989 R==APFloat::cmpUnordered, dl, VT);
1990 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1991 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1994 // Ensure that the constant occurs on the RHS.
1995 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1996 MVT CompVT = N1.getValueType().getSimpleVT();
1997 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
2000 return getSetCC(dl, VT, N2, N1, SwappedCond);
2004 // Could not fold it.
2008 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2009 /// use this predicate to simplify operations downstream.
2010 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2011 // This predicate is not safe for vector operations.
2012 if (Op.getValueType().isVector())
2015 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2016 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2019 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2020 /// this predicate to simplify operations downstream. Mask is known to be zero
2021 /// for bits that V cannot have.
2022 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2023 unsigned Depth) const {
2024 APInt KnownZero, KnownOne;
2025 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2026 return (KnownZero & Mask) == Mask;
2029 /// Determine which bits of Op are known to be either zero or one and return
2030 /// them in the KnownZero/KnownOne bitsets.
2031 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2032 APInt &KnownOne, unsigned Depth) const {
2033 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2035 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2037 return; // Limit search depth.
2039 APInt KnownZero2, KnownOne2;
2041 switch (Op.getOpcode()) {
2043 // We know all of the bits for a constant!
2044 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2045 KnownZero = ~KnownOne;
2048 // If either the LHS or the RHS are Zero, the result is zero.
2049 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2050 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2052 // Output known-1 bits are only known if set in both the LHS & RHS.
2053 KnownOne &= KnownOne2;
2054 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2055 KnownZero |= KnownZero2;
2058 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2059 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2061 // Output known-0 bits are only known if clear in both the LHS & RHS.
2062 KnownZero &= KnownZero2;
2063 // Output known-1 are known to be set if set in either the LHS | RHS.
2064 KnownOne |= KnownOne2;
2067 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2068 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2070 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2071 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2072 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2073 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2074 KnownZero = KnownZeroOut;
2078 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2079 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2081 // If low bits are zero in either operand, output low known-0 bits.
2082 // Also compute a conserative estimate for high known-0 bits.
2083 // More trickiness is possible, but this is sufficient for the
2084 // interesting case of alignment computation.
2085 KnownOne.clearAllBits();
2086 unsigned TrailZ = KnownZero.countTrailingOnes() +
2087 KnownZero2.countTrailingOnes();
2088 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2089 KnownZero2.countLeadingOnes(),
2090 BitWidth) - BitWidth;
2092 TrailZ = std::min(TrailZ, BitWidth);
2093 LeadZ = std::min(LeadZ, BitWidth);
2094 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2095 APInt::getHighBitsSet(BitWidth, LeadZ);
2099 // For the purposes of computing leading zeros we can conservatively
2100 // treat a udiv as a logical right shift by the power of 2 known to
2101 // be less than the denominator.
2102 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2103 unsigned LeadZ = KnownZero2.countLeadingOnes();
2105 KnownOne2.clearAllBits();
2106 KnownZero2.clearAllBits();
2107 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2108 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2109 if (RHSUnknownLeadingOnes != BitWidth)
2110 LeadZ = std::min(BitWidth,
2111 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2113 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2117 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2118 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2120 // Only known if known in both the LHS and RHS.
2121 KnownOne &= KnownOne2;
2122 KnownZero &= KnownZero2;
2124 case ISD::SELECT_CC:
2125 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2126 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2128 // Only known if known in both the LHS and RHS.
2129 KnownOne &= KnownOne2;
2130 KnownZero &= KnownZero2;
2138 if (Op.getResNo() != 1)
2140 // The boolean result conforms to getBooleanContents.
2141 // If we know the result of a setcc has the top bits zero, use this info.
2142 // We know that we have an integer-based boolean since these operations
2143 // are only available for integer.
2144 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2145 TargetLowering::ZeroOrOneBooleanContent &&
2147 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2150 // If we know the result of a setcc has the top bits zero, use this info.
2151 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2152 TargetLowering::ZeroOrOneBooleanContent &&
2154 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2157 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2158 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2159 unsigned ShAmt = SA->getZExtValue();
2161 // If the shift count is an invalid immediate, don't do anything.
2162 if (ShAmt >= BitWidth)
2165 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2166 KnownZero <<= ShAmt;
2168 // low bits known zero.
2169 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2173 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2174 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2175 unsigned ShAmt = SA->getZExtValue();
2177 // If the shift count is an invalid immediate, don't do anything.
2178 if (ShAmt >= BitWidth)
2181 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2182 KnownZero = KnownZero.lshr(ShAmt);
2183 KnownOne = KnownOne.lshr(ShAmt);
2185 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2186 KnownZero |= HighBits; // High bits known zero.
2190 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2191 unsigned ShAmt = SA->getZExtValue();
2193 // If the shift count is an invalid immediate, don't do anything.
2194 if (ShAmt >= BitWidth)
2197 // If any of the demanded bits are produced by the sign extension, we also
2198 // demand the input sign bit.
2199 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2201 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2202 KnownZero = KnownZero.lshr(ShAmt);
2203 KnownOne = KnownOne.lshr(ShAmt);
2205 // Handle the sign bits.
2206 APInt SignBit = APInt::getSignBit(BitWidth);
2207 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2209 if (KnownZero.intersects(SignBit)) {
2210 KnownZero |= HighBits; // New bits are known zero.
2211 } else if (KnownOne.intersects(SignBit)) {
2212 KnownOne |= HighBits; // New bits are known one.
2216 case ISD::SIGN_EXTEND_INREG: {
2217 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2218 unsigned EBits = EVT.getScalarType().getSizeInBits();
2220 // Sign extension. Compute the demanded bits in the result that are not
2221 // present in the input.
2222 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2224 APInt InSignBit = APInt::getSignBit(EBits);
2225 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2227 // If the sign extended bits are demanded, we know that the sign
2229 InSignBit = InSignBit.zext(BitWidth);
2230 if (NewBits.getBoolValue())
2231 InputDemandedBits |= InSignBit;
2233 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2234 KnownOne &= InputDemandedBits;
2235 KnownZero &= InputDemandedBits;
2237 // If the sign bit of the input is known set or clear, then we know the
2238 // top bits of the result.
2239 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2240 KnownZero |= NewBits;
2241 KnownOne &= ~NewBits;
2242 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2243 KnownOne |= NewBits;
2244 KnownZero &= ~NewBits;
2245 } else { // Input sign bit unknown
2246 KnownZero &= ~NewBits;
2247 KnownOne &= ~NewBits;
2252 case ISD::CTTZ_ZERO_UNDEF:
2254 case ISD::CTLZ_ZERO_UNDEF:
2256 unsigned LowBits = Log2_32(BitWidth)+1;
2257 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2258 KnownOne.clearAllBits();
2262 LoadSDNode *LD = cast<LoadSDNode>(Op);
2263 // If this is a ZEXTLoad and we are looking at the loaded value.
2264 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2265 EVT VT = LD->getMemoryVT();
2266 unsigned MemBits = VT.getScalarType().getSizeInBits();
2267 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2268 } else if (const MDNode *Ranges = LD->getRanges()) {
2269 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2273 case ISD::ZERO_EXTEND: {
2274 EVT InVT = Op.getOperand(0).getValueType();
2275 unsigned InBits = InVT.getScalarType().getSizeInBits();
2276 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2277 KnownZero = KnownZero.trunc(InBits);
2278 KnownOne = KnownOne.trunc(InBits);
2279 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2280 KnownZero = KnownZero.zext(BitWidth);
2281 KnownOne = KnownOne.zext(BitWidth);
2282 KnownZero |= NewBits;
2285 case ISD::SIGN_EXTEND: {
2286 EVT InVT = Op.getOperand(0).getValueType();
2287 unsigned InBits = InVT.getScalarType().getSizeInBits();
2288 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2290 KnownZero = KnownZero.trunc(InBits);
2291 KnownOne = KnownOne.trunc(InBits);
2292 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2294 // Note if the sign bit is known to be zero or one.
2295 bool SignBitKnownZero = KnownZero.isNegative();
2296 bool SignBitKnownOne = KnownOne.isNegative();
2298 KnownZero = KnownZero.zext(BitWidth);
2299 KnownOne = KnownOne.zext(BitWidth);
2301 // If the sign bit is known zero or one, the top bits match.
2302 if (SignBitKnownZero)
2303 KnownZero |= NewBits;
2304 else if (SignBitKnownOne)
2305 KnownOne |= NewBits;
2308 case ISD::ANY_EXTEND: {
2309 EVT InVT = Op.getOperand(0).getValueType();
2310 unsigned InBits = InVT.getScalarType().getSizeInBits();
2311 KnownZero = KnownZero.trunc(InBits);
2312 KnownOne = KnownOne.trunc(InBits);
2313 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2314 KnownZero = KnownZero.zext(BitWidth);
2315 KnownOne = KnownOne.zext(BitWidth);
2318 case ISD::TRUNCATE: {
2319 EVT InVT = Op.getOperand(0).getValueType();
2320 unsigned InBits = InVT.getScalarType().getSizeInBits();
2321 KnownZero = KnownZero.zext(InBits);
2322 KnownOne = KnownOne.zext(InBits);
2323 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2324 KnownZero = KnownZero.trunc(BitWidth);
2325 KnownOne = KnownOne.trunc(BitWidth);
2328 case ISD::AssertZext: {
2329 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2330 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2331 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2332 KnownZero |= (~InMask);
2333 KnownOne &= (~KnownZero);
2337 // All bits are zero except the low bit.
2338 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2342 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2343 // We know that the top bits of C-X are clear if X contains less bits
2344 // than C (i.e. no wrap-around can happen). For example, 20-X is
2345 // positive if we can prove that X is >= 0 and < 16.
2346 if (CLHS->getAPIntValue().isNonNegative()) {
2347 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2348 // NLZ can't be BitWidth with no sign bit
2349 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2350 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2352 // If all of the MaskV bits are known to be zero, then we know the
2353 // output top bits are zero, because we now know that the output is
2355 if ((KnownZero2 & MaskV) == MaskV) {
2356 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2357 // Top bits known zero.
2358 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2366 // Output known-0 bits are known if clear or set in both the low clear bits
2367 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2368 // low 3 bits clear.
2369 // Output known-0 bits are also known if the top bits of each input are
2370 // known to be clear. For example, if one input has the top 10 bits clear
2371 // and the other has the top 8 bits clear, we know the top 7 bits of the
2372 // output must be clear.
2373 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2374 unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
2375 unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
2377 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2378 KnownZeroHigh = std::min(KnownZeroHigh,
2379 KnownZero2.countLeadingOnes());
2380 KnownZeroLow = std::min(KnownZeroLow,
2381 KnownZero2.countTrailingOnes());
2383 if (Op.getOpcode() == ISD::ADD) {
2384 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
2385 if (KnownZeroHigh > 1)
2386 KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
2390 // With ADDE, a carry bit may be added in, so we can only use this
2391 // information if we know (at least) that the low two bits are clear. We
2392 // then return to the caller that the low bit is unknown but that other bits
2394 if (KnownZeroLow >= 2) // ADDE
2395 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
2399 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2400 const APInt &RA = Rem->getAPIntValue().abs();
2401 if (RA.isPowerOf2()) {
2402 APInt LowBits = RA - 1;
2403 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2405 // The low bits of the first operand are unchanged by the srem.
2406 KnownZero = KnownZero2 & LowBits;
2407 KnownOne = KnownOne2 & LowBits;
2409 // If the first operand is non-negative or has all low bits zero, then
2410 // the upper bits are all zero.
2411 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2412 KnownZero |= ~LowBits;
2414 // If the first operand is negative and not all low bits are zero, then
2415 // the upper bits are all one.
2416 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2417 KnownOne |= ~LowBits;
2418 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2423 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2424 const APInt &RA = Rem->getAPIntValue();
2425 if (RA.isPowerOf2()) {
2426 APInt LowBits = (RA - 1);
2427 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2429 // The upper bits are all zero, the lower ones are unchanged.
2430 KnownZero = KnownZero2 | ~LowBits;
2431 KnownOne = KnownOne2 & LowBits;
2436 // Since the result is less than or equal to either operand, any leading
2437 // zero bits in either operand must also exist in the result.
2438 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2439 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2441 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2442 KnownZero2.countLeadingOnes());
2443 KnownOne.clearAllBits();
2444 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2447 case ISD::EXTRACT_ELEMENT: {
2448 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2449 const unsigned Index =
2450 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2451 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2453 // Remove low part of known bits mask
2454 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2455 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2457 // Remove high part of known bit mask
2458 KnownZero = KnownZero.trunc(BitWidth);
2459 KnownOne = KnownOne.trunc(BitWidth);
2466 APInt Op0Zero, Op0One;
2467 APInt Op1Zero, Op1One;
2468 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2469 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2471 KnownZero = Op0Zero & Op1Zero;
2472 KnownOne = Op0One & Op1One;
2475 case ISD::FrameIndex:
2476 case ISD::TargetFrameIndex:
2477 if (unsigned Align = InferPtrAlignment(Op)) {
2478 // The low bits are known zero if the pointer is aligned.
2479 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2485 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2488 case ISD::INTRINSIC_WO_CHAIN:
2489 case ISD::INTRINSIC_W_CHAIN:
2490 case ISD::INTRINSIC_VOID:
2491 // Allow the target to implement this method for its nodes.
2492 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2496 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2499 /// ComputeNumSignBits - Return the number of times the sign bit of the
2500 /// register is replicated into the other bits. We know that at least 1 bit
2501 /// is always equal to the sign bit (itself), but other cases can give us
2502 /// information. For example, immediately after an "SRA X, 2", we know that
2503 /// the top 3 bits are all equal to each other, so we return 3.
2504 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2505 EVT VT = Op.getValueType();
2506 assert(VT.isInteger() && "Invalid VT!");
2507 unsigned VTBits = VT.getScalarType().getSizeInBits();
2509 unsigned FirstAnswer = 1;
2512 return 1; // Limit search depth.
2514 switch (Op.getOpcode()) {
2516 case ISD::AssertSext:
2517 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2518 return VTBits-Tmp+1;
2519 case ISD::AssertZext:
2520 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2523 case ISD::Constant: {
2524 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2525 return Val.getNumSignBits();
2528 case ISD::SIGN_EXTEND:
2530 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2531 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2533 case ISD::SIGN_EXTEND_INREG:
2534 // Max of the input and what this extends.
2536 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2539 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2540 return std::max(Tmp, Tmp2);
2543 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2544 // SRA X, C -> adds C sign bits.
2545 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2546 Tmp += C->getZExtValue();
2547 if (Tmp > VTBits) Tmp = VTBits;
2551 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2552 // shl destroys sign bits.
2553 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2554 if (C->getZExtValue() >= VTBits || // Bad shift.
2555 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2556 return Tmp - C->getZExtValue();
2561 case ISD::XOR: // NOT is handled here.
2562 // Logical binary ops preserve the number of sign bits at the worst.
2563 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2565 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2566 FirstAnswer = std::min(Tmp, Tmp2);
2567 // We computed what we know about the sign bits as our first
2568 // answer. Now proceed to the generic code that uses
2569 // computeKnownBits, and pick whichever answer is better.
2574 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2575 if (Tmp == 1) return 1; // Early out.
2576 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2577 return std::min(Tmp, Tmp2);
2578 case ISD::SELECT_CC:
2579 Tmp = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2580 if (Tmp == 1) return 1; // Early out.
2581 Tmp2 = ComputeNumSignBits(Op.getOperand(3), Depth+1);
2582 return std::min(Tmp, Tmp2);
2587 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2589 return 1; // Early out.
2590 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2591 return std::min(Tmp, Tmp2);
2598 if (Op.getResNo() != 1)
2600 // The boolean result conforms to getBooleanContents. Fall through.
2601 // If setcc returns 0/-1, all bits are sign bits.
2602 // We know that we have an integer-based boolean since these operations
2603 // are only available for integer.
2604 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2605 TargetLowering::ZeroOrNegativeOneBooleanContent)
2609 // If setcc returns 0/-1, all bits are sign bits.
2610 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2611 TargetLowering::ZeroOrNegativeOneBooleanContent)
2616 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2617 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2619 // Handle rotate right by N like a rotate left by 32-N.
2620 if (Op.getOpcode() == ISD::ROTR)
2621 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2623 // If we aren't rotating out all of the known-in sign bits, return the
2624 // number that are left. This handles rotl(sext(x), 1) for example.
2625 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2626 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2630 // Add can have at most one carry bit. Thus we know that the output
2631 // is, at worst, one more bit than the inputs.
2632 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2633 if (Tmp == 1) return 1; // Early out.
2635 // Special case decrementing a value (ADD X, -1):
2636 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2637 if (CRHS->isAllOnesValue()) {
2638 APInt KnownZero, KnownOne;
2639 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2641 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2643 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2646 // If we are subtracting one from a positive number, there is no carry
2647 // out of the result.
2648 if (KnownZero.isNegative())
2652 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2653 if (Tmp2 == 1) return 1;
2654 return std::min(Tmp, Tmp2)-1;
2657 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2658 if (Tmp2 == 1) return 1;
2661 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2662 if (CLHS->isNullValue()) {
2663 APInt KnownZero, KnownOne;
2664 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2665 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2667 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2670 // If the input is known to be positive (the sign bit is known clear),
2671 // the output of the NEG has the same number of sign bits as the input.
2672 if (KnownZero.isNegative())
2675 // Otherwise, we treat this like a SUB.
2678 // Sub can have at most one carry bit. Thus we know that the output
2679 // is, at worst, one more bit than the inputs.
2680 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2681 if (Tmp == 1) return 1; // Early out.
2682 return std::min(Tmp, Tmp2)-1;
2684 // FIXME: it's tricky to do anything useful for this, but it is an important
2685 // case for targets like X86.
2687 case ISD::EXTRACT_ELEMENT: {
2688 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2689 const int BitWidth = Op.getValueType().getSizeInBits();
2691 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2693 // Get reverse index (starting from 1), Op1 value indexes elements from
2694 // little end. Sign starts at big end.
2695 const int rIndex = Items - 1 -
2696 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2698 // If the sign portion ends in our element the subtraction gives correct
2699 // result. Otherwise it gives either negative or > bitwidth result
2700 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2704 // If we are looking at the loaded value of the SDNode.
2705 if (Op.getResNo() == 0) {
2706 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2707 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2708 unsigned ExtType = LD->getExtensionType();
2711 case ISD::SEXTLOAD: // '17' bits known
2712 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2713 return VTBits-Tmp+1;
2714 case ISD::ZEXTLOAD: // '16' bits known
2715 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2721 // Allow the target to implement this method for its nodes.
2722 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2723 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2724 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2725 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2726 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2727 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2730 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2731 // use this information.
2732 APInt KnownZero, KnownOne;
2733 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2736 if (KnownZero.isNegative()) { // sign bit is 0
2738 } else if (KnownOne.isNegative()) { // sign bit is 1;
2745 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2746 // the number of identical bits in the top of the input value.
2748 Mask <<= Mask.getBitWidth()-VTBits;
2749 // Return # leading zeros. We use 'min' here in case Val was zero before
2750 // shifting. We don't want to return '64' as for an i32 "0".
2751 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2754 /// isBaseWithConstantOffset - Return true if the specified operand is an
2755 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2756 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2757 /// semantics as an ADD. This handles the equivalence:
2758 /// X|Cst == X+Cst iff X&Cst = 0.
2759 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2760 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2761 !isa<ConstantSDNode>(Op.getOperand(1)))
2764 if (Op.getOpcode() == ISD::OR &&
2765 !MaskedValueIsZero(Op.getOperand(0),
2766 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2773 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2774 // If we're told that NaNs won't happen, assume they won't.
2775 if (getTarget().Options.NoNaNsFPMath)
2778 // If the value is a constant, we can obviously see if it is a NaN or not.
2779 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2780 return !C->getValueAPF().isNaN();
2782 // TODO: Recognize more cases here.
2787 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2788 // If the value is a constant, we can obviously see if it is a zero or not.
2789 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2790 return !C->isZero();
2792 // TODO: Recognize more cases here.
2793 switch (Op.getOpcode()) {
2796 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2797 return !C->isNullValue();
2804 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2805 // Check the obvious case.
2806 if (A == B) return true;
2808 // For for negative and positive zero.
2809 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2810 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2811 if (CA->isZero() && CB->isZero()) return true;
2813 // Otherwise they may not be equal.
2817 /// getNode - Gets or creates the specified node.
2819 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2820 FoldingSetNodeID ID;
2821 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2823 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2824 return SDValue(E, 0);
2826 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2827 DL.getDebugLoc(), getVTList(VT));
2828 CSEMap.InsertNode(N, IP);
2831 return SDValue(N, 0);
2834 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2835 EVT VT, SDValue Operand) {
2836 // Constant fold unary operations with an integer constant operand. Even
2837 // opaque constant will be folded, because the folding of unary operations
2838 // doesn't create new constants with different values. Nevertheless, the
2839 // opaque flag is preserved during folding to prevent future folding with
2841 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand)) {
2842 const APInt &Val = C->getAPIntValue();
2845 case ISD::SIGN_EXTEND:
2846 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2847 C->isTargetOpcode(), C->isOpaque());
2848 case ISD::ANY_EXTEND:
2849 case ISD::ZERO_EXTEND:
2851 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2852 C->isTargetOpcode(), C->isOpaque());
2853 case ISD::UINT_TO_FP:
2854 case ISD::SINT_TO_FP: {
2855 APFloat apf(EVTToAPFloatSemantics(VT),
2856 APInt::getNullValue(VT.getSizeInBits()));
2857 (void)apf.convertFromAPInt(Val,
2858 Opcode==ISD::SINT_TO_FP,
2859 APFloat::rmNearestTiesToEven);
2860 return getConstantFP(apf, DL, VT);
2863 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2864 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2865 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2866 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2867 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2868 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2871 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2874 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2877 case ISD::CTLZ_ZERO_UNDEF:
2878 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2881 case ISD::CTTZ_ZERO_UNDEF:
2882 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2887 // Constant fold unary operations with a floating point constant operand.
2888 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand)) {
2889 APFloat V = C->getValueAPF(); // make copy
2893 return getConstantFP(V, DL, VT);
2896 return getConstantFP(V, DL, VT);
2898 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2899 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2900 return getConstantFP(V, DL, VT);
2904 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2905 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2906 return getConstantFP(V, DL, VT);
2910 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2911 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2912 return getConstantFP(V, DL, VT);
2915 case ISD::FP_EXTEND: {
2917 // This can return overflow, underflow, or inexact; we don't care.
2918 // FIXME need to be more flexible about rounding mode.
2919 (void)V.convert(EVTToAPFloatSemantics(VT),
2920 APFloat::rmNearestTiesToEven, &ignored);
2921 return getConstantFP(V, DL, VT);
2923 case ISD::FP_TO_SINT:
2924 case ISD::FP_TO_UINT: {
2927 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2928 // FIXME need to be more flexible about rounding mode.
2929 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2930 Opcode==ISD::FP_TO_SINT,
2931 APFloat::rmTowardZero, &ignored);
2932 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2934 APInt api(VT.getSizeInBits(), x);
2935 return getConstant(api, DL, VT);
2938 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2939 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2940 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2941 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2942 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2943 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2948 // Constant fold unary operations with a vector integer or float operand.
2949 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand)) {
2950 if (BV->isConstant()) {
2953 // FIXME: Entirely reasonable to perform folding of other unary
2954 // operations here as the need arises.
2961 case ISD::FP_EXTEND:
2962 case ISD::FP_TO_SINT:
2963 case ISD::FP_TO_UINT:
2965 case ISD::UINT_TO_FP:
2966 case ISD::SINT_TO_FP:
2969 case ISD::CTLZ_ZERO_UNDEF:
2971 case ISD::CTTZ_ZERO_UNDEF:
2973 SDValue Ops = { Operand };
2974 if (SDValue Fold = FoldConstantVectorArithmetic(Opcode, DL, VT, Ops))
2981 unsigned OpOpcode = Operand.getNode()->getOpcode();
2983 case ISD::TokenFactor:
2984 case ISD::MERGE_VALUES:
2985 case ISD::CONCAT_VECTORS:
2986 return Operand; // Factor, merge or concat of one node? No need.
2987 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2988 case ISD::FP_EXTEND:
2989 assert(VT.isFloatingPoint() &&
2990 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2991 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2992 assert((!VT.isVector() ||
2993 VT.getVectorNumElements() ==
2994 Operand.getValueType().getVectorNumElements()) &&
2995 "Vector element count mismatch!");
2996 assert(Operand.getValueType().bitsLT(VT) &&
2997 "Invalid fpext node, dst < src!");
2998 if (Operand.getOpcode() == ISD::UNDEF)
2999 return getUNDEF(VT);
3001 case ISD::SIGN_EXTEND:
3002 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3003 "Invalid SIGN_EXTEND!");
3004 if (Operand.getValueType() == VT) return Operand; // noop extension
3005 assert((!VT.isVector() ||
3006 VT.getVectorNumElements() ==
3007 Operand.getValueType().getVectorNumElements()) &&
3008 "Vector element count mismatch!");
3009 assert(Operand.getValueType().bitsLT(VT) &&
3010 "Invalid sext node, dst < src!");
3011 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3012 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3013 else if (OpOpcode == ISD::UNDEF)
3014 // sext(undef) = 0, because the top bits will all be the same.
3015 return getConstant(0, DL, VT);
3017 case ISD::ZERO_EXTEND:
3018 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3019 "Invalid ZERO_EXTEND!");
3020 if (Operand.getValueType() == VT) return Operand; // noop extension
3021 assert((!VT.isVector() ||
3022 VT.getVectorNumElements() ==
3023 Operand.getValueType().getVectorNumElements()) &&
3024 "Vector element count mismatch!");
3025 assert(Operand.getValueType().bitsLT(VT) &&
3026 "Invalid zext node, dst < src!");
3027 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3028 return getNode(ISD::ZERO_EXTEND, DL, VT,
3029 Operand.getNode()->getOperand(0));
3030 else if (OpOpcode == ISD::UNDEF)
3031 // zext(undef) = 0, because the top bits will be zero.
3032 return getConstant(0, DL, VT);
3034 case ISD::ANY_EXTEND:
3035 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3036 "Invalid ANY_EXTEND!");
3037 if (Operand.getValueType() == VT) return Operand; // noop extension
3038 assert((!VT.isVector() ||
3039 VT.getVectorNumElements() ==
3040 Operand.getValueType().getVectorNumElements()) &&
3041 "Vector element count mismatch!");
3042 assert(Operand.getValueType().bitsLT(VT) &&
3043 "Invalid anyext node, dst < src!");
3045 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3046 OpOpcode == ISD::ANY_EXTEND)
3047 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3048 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3049 else if (OpOpcode == ISD::UNDEF)
3050 return getUNDEF(VT);
3052 // (ext (trunx x)) -> x
3053 if (OpOpcode == ISD::TRUNCATE) {
3054 SDValue OpOp = Operand.getNode()->getOperand(0);
3055 if (OpOp.getValueType() == VT)
3060 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3061 "Invalid TRUNCATE!");
3062 if (Operand.getValueType() == VT) return Operand; // noop truncate
3063 assert((!VT.isVector() ||
3064 VT.getVectorNumElements() ==
3065 Operand.getValueType().getVectorNumElements()) &&
3066 "Vector element count mismatch!");
3067 assert(Operand.getValueType().bitsGT(VT) &&
3068 "Invalid truncate node, src < dst!");
3069 if (OpOpcode == ISD::TRUNCATE)
3070 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3071 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3072 OpOpcode == ISD::ANY_EXTEND) {
3073 // If the source is smaller than the dest, we still need an extend.
3074 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3075 .bitsLT(VT.getScalarType()))
3076 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3077 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3078 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3079 return Operand.getNode()->getOperand(0);
3081 if (OpOpcode == ISD::UNDEF)
3082 return getUNDEF(VT);
3085 assert(VT.isInteger() && VT == Operand.getValueType() &&
3087 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3088 "BSWAP types must be a multiple of 16 bits!");
3089 if (OpOpcode == ISD::UNDEF)
3090 return getUNDEF(VT);
3093 // Basic sanity checking.
3094 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3095 && "Cannot BITCAST between types of different sizes!");
3096 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3097 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3098 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3099 if (OpOpcode == ISD::UNDEF)
3100 return getUNDEF(VT);
3102 case ISD::SCALAR_TO_VECTOR:
3103 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3104 (VT.getVectorElementType() == Operand.getValueType() ||
3105 (VT.getVectorElementType().isInteger() &&
3106 Operand.getValueType().isInteger() &&
3107 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3108 "Illegal SCALAR_TO_VECTOR node!");
3109 if (OpOpcode == ISD::UNDEF)
3110 return getUNDEF(VT);
3111 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3112 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3113 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3114 Operand.getConstantOperandVal(1) == 0 &&
3115 Operand.getOperand(0).getValueType() == VT)
3116 return Operand.getOperand(0);
3119 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3120 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3121 // FIXME: FNEG has no fast-math-flags to propagate; use the FSUB's flags?
3122 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3123 Operand.getNode()->getOperand(0),
3124 &cast<BinaryWithFlagsSDNode>(Operand.getNode())->Flags);
3125 if (OpOpcode == ISD::FNEG) // --X -> X
3126 return Operand.getNode()->getOperand(0);
3129 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3130 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3135 SDVTList VTs = getVTList(VT);
3136 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3137 FoldingSetNodeID ID;
3138 SDValue Ops[1] = { Operand };
3139 AddNodeIDNode(ID, Opcode, VTs, Ops);
3141 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3142 return SDValue(E, 0);
3144 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3145 DL.getDebugLoc(), VTs, Operand);
3146 CSEMap.InsertNode(N, IP);
3148 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3149 DL.getDebugLoc(), VTs, Operand);
3153 return SDValue(N, 0);
3156 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3159 case ISD::ADD: return std::make_pair(C1 + C2, true);
3160 case ISD::SUB: return std::make_pair(C1 - C2, true);
3161 case ISD::MUL: return std::make_pair(C1 * C2, true);
3162 case ISD::AND: return std::make_pair(C1 & C2, true);
3163 case ISD::OR: return std::make_pair(C1 | C2, true);
3164 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3165 case ISD::SHL: return std::make_pair(C1 << C2, true);
3166 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3167 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3168 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3169 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3170 case ISD::SMIN: return std::make_pair(C1.sle(C2) ? C1 : C2, true);
3171 case ISD::SMAX: return std::make_pair(C1.sge(C2) ? C1 : C2, true);
3172 case ISD::UMIN: return std::make_pair(C1.ule(C2) ? C1 : C2, true);
3173 case ISD::UMAX: return std::make_pair(C1.uge(C2) ? C1 : C2, true);
3175 if (!C2.getBoolValue())
3177 return std::make_pair(C1.udiv(C2), true);
3179 if (!C2.getBoolValue())
3181 return std::make_pair(C1.urem(C2), true);
3183 if (!C2.getBoolValue())
3185 return std::make_pair(C1.sdiv(C2), true);
3187 if (!C2.getBoolValue())
3189 return std::make_pair(C1.srem(C2), true);
3191 return std::make_pair(APInt(1, 0), false);
3194 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3195 const ConstantSDNode *Cst1,
3196 const ConstantSDNode *Cst2) {
3197 if (Cst1->isOpaque() || Cst2->isOpaque())
3200 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3201 Cst2->getAPIntValue());
3204 return getConstant(Folded.first, DL, VT);
3207 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3208 SDNode *Cst1, SDNode *Cst2) {
3209 // If the opcode is a target-specific ISD node, there's nothing we can
3210 // do here and the operand rules may not line up with the below, so
3212 if (Opcode >= ISD::BUILTIN_OP_END)
3215 // Handle the case of two scalars.
3216 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3217 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3218 if (SDValue Folded =
3219 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3222 SmallVector<SDValue, 4> Outputs;
3223 // We may have a vector type but a scalar result. Create a splat.
3224 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3225 // Build a big vector out of the scalar elements we generated.
3226 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3233 // For vectors extract each constant element into Inputs so we can constant
3234 // fold them individually.
3235 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3236 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3240 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3242 EVT SVT = VT.getScalarType();
3243 SmallVector<SDValue, 4> Outputs;
3244 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3245 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3246 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3247 if (!V1 || !V2) // Not a constant, bail.
3250 if (V1->isOpaque() || V2->isOpaque())
3253 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3254 // FIXME: This is valid and could be handled by truncating the APInts.
3255 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3258 // Fold one vector element.
3259 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3260 V2->getAPIntValue());
3263 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3266 assert(VT.getVectorNumElements() == Outputs.size() &&
3267 "Vector size mismatch!");
3269 // We may have a vector type but a scalar result. Create a splat.
3270 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3272 // Build a big vector out of the scalar elements we generated.
3273 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3276 SDValue SelectionDAG::FoldConstantVectorArithmetic(unsigned Opcode, SDLoc DL,
3278 ArrayRef<SDValue> Ops,
3279 const SDNodeFlags *Flags) {
3280 // If the opcode is a target-specific ISD node, there's nothing we can
3281 // do here and the operand rules may not line up with the below, so
3283 if (Opcode >= ISD::BUILTIN_OP_END)
3286 // We can only fold vectors - maybe merge with FoldConstantArithmetic someday?
3290 unsigned NumElts = VT.getVectorNumElements();
3292 auto IsSameVectorSize = [&](const SDValue &Op) {
3293 return Op.getValueType().isVector() &&
3294 Op.getValueType().getVectorNumElements() == NumElts;
3297 auto IsConstantBuildVectorOrUndef = [&](const SDValue &Op) {
3298 BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Op);
3299 return (Op.getOpcode() == ISD::UNDEF) || (BV && BV->isConstant());
3302 // All operands must be vector types with the same number of elements as
3303 // the result type and must be either UNDEF or a build vector of constant
3304 // or UNDEF scalars.
3305 if (!std::all_of(Ops.begin(), Ops.end(), IsConstantBuildVectorOrUndef) ||
3306 !std::all_of(Ops.begin(), Ops.end(), IsSameVectorSize))
3309 // Find legal integer scalar type for constant promotion and
3310 // ensure that its scalar size is at least as large as source.
3311 EVT SVT = VT.getScalarType();
3313 if (SVT.isInteger()) {
3314 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
3315 if (LegalSVT.bitsLT(SVT))
3319 // Constant fold each scalar lane separately.
3320 SmallVector<SDValue, 4> ScalarResults;
3321 for (unsigned i = 0; i != NumElts; i++) {
3322 SmallVector<SDValue, 4> ScalarOps;
3323 for (SDValue Op : Ops) {
3324 EVT InSVT = Op.getValueType().getScalarType();
3325 BuildVectorSDNode *InBV = dyn_cast<BuildVectorSDNode>(Op);
3327 // We've checked that this is UNDEF above.
3328 ScalarOps.push_back(getUNDEF(InSVT));
3332 SDValue ScalarOp = InBV->getOperand(i);
3333 EVT ScalarVT = ScalarOp.getValueType();
3335 // Build vector (integer) scalar operands may need implicit
3336 // truncation - do this before constant folding.
3337 if (ScalarVT.isInteger() && ScalarVT.bitsGT(InSVT))
3338 ScalarOp = getNode(ISD::TRUNCATE, DL, InSVT, ScalarOp);
3340 ScalarOps.push_back(ScalarOp);
3343 // Constant fold the scalar operands.
3344 SDValue ScalarResult = getNode(Opcode, DL, SVT, ScalarOps, Flags);
3346 // Legalize the (integer) scalar constant if necessary.
3347 if (LegalSVT != SVT)
3348 ScalarResult = getNode(ISD::ANY_EXTEND, DL, LegalSVT, ScalarResult);
3350 // Scalar folding only succeeded if the result is a constant or UNDEF.
3351 if (ScalarResult.getOpcode() != ISD::UNDEF &&
3352 ScalarResult.getOpcode() != ISD::Constant &&
3353 ScalarResult.getOpcode() != ISD::ConstantFP)
3355 ScalarResults.push_back(ScalarResult);
3358 assert(ScalarResults.size() == NumElts &&
3359 "Unexpected number of scalar results for BUILD_VECTOR");
3360 return getNode(ISD::BUILD_VECTOR, DL, VT, ScalarResults);
3363 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3364 SDValue N2, const SDNodeFlags *Flags) {
3365 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3366 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
3368 // Canonicalize constant to RHS if commutative.
3369 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3370 std::swap(N1C, N2C);
3376 case ISD::TokenFactor:
3377 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3378 N2.getValueType() == MVT::Other && "Invalid token factor!");
3379 // Fold trivial token factors.
3380 if (N1.getOpcode() == ISD::EntryToken) return N2;
3381 if (N2.getOpcode() == ISD::EntryToken) return N1;
3382 if (N1 == N2) return N1;
3384 case ISD::CONCAT_VECTORS:
3385 // Concat of UNDEFs is UNDEF.
3386 if (N1.getOpcode() == ISD::UNDEF &&
3387 N2.getOpcode() == ISD::UNDEF)
3388 return getUNDEF(VT);
3390 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3391 // one big BUILD_VECTOR.
3392 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3393 N2.getOpcode() == ISD::BUILD_VECTOR) {
3394 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3395 N1.getNode()->op_end());
3396 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3398 // BUILD_VECTOR requires all inputs to be of the same type, find the
3399 // maximum type and extend them all.
3400 EVT SVT = VT.getScalarType();
3401 for (SDValue Op : Elts)
3402 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3403 if (SVT.bitsGT(VT.getScalarType()))
3404 for (SDValue &Op : Elts)
3405 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3406 ? getZExtOrTrunc(Op, DL, SVT)
3407 : getSExtOrTrunc(Op, DL, SVT);
3409 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3413 assert(VT.isInteger() && "This operator does not apply to FP types!");
3414 assert(N1.getValueType() == N2.getValueType() &&
3415 N1.getValueType() == VT && "Binary operator types must match!");
3416 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3417 // worth handling here.
3418 if (N2C && N2C->isNullValue())
3420 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3427 assert(VT.isInteger() && "This operator does not apply to FP types!");
3428 assert(N1.getValueType() == N2.getValueType() &&
3429 N1.getValueType() == VT && "Binary operator types must match!");
3430 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3431 // it's worth handling here.
3432 if (N2C && N2C->isNullValue())
3446 assert(VT.isInteger() && "This operator does not apply to FP types!");
3447 assert(N1.getValueType() == N2.getValueType() &&
3448 N1.getValueType() == VT && "Binary operator types must match!");
3455 if (getTarget().Options.UnsafeFPMath) {
3456 if (Opcode == ISD::FADD) {
3458 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3459 if (CFP->getValueAPF().isZero())
3462 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3463 if (CFP->getValueAPF().isZero())
3465 } else if (Opcode == ISD::FSUB) {
3467 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3468 if (CFP->getValueAPF().isZero())
3470 } else if (Opcode == ISD::FMUL) {
3471 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3474 // If the first operand isn't the constant, try the second
3476 CFP = dyn_cast<ConstantFPSDNode>(N2);
3483 return SDValue(CFP,0);
3485 if (CFP->isExactlyValue(1.0))
3490 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3491 assert(N1.getValueType() == N2.getValueType() &&
3492 N1.getValueType() == VT && "Binary operator types must match!");
3494 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3495 assert(N1.getValueType() == VT &&
3496 N1.getValueType().isFloatingPoint() &&
3497 N2.getValueType().isFloatingPoint() &&
3498 "Invalid FCOPYSIGN!");
3505 assert(VT == N1.getValueType() &&
3506 "Shift operators return type must be the same as their first arg");
3507 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3508 "Shifts only work on integers");
3509 assert((!VT.isVector() || VT == N2.getValueType()) &&
3510 "Vector shift amounts must be in the same as their first arg");
3511 // Verify that the shift amount VT is bit enough to hold valid shift
3512 // amounts. This catches things like trying to shift an i1024 value by an
3513 // i8, which is easy to fall into in generic code that uses
3514 // TLI.getShiftAmount().
3515 assert(N2.getValueType().getSizeInBits() >=
3516 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3517 "Invalid use of small shift amount with oversized value!");
3519 // Always fold shifts of i1 values so the code generator doesn't need to
3520 // handle them. Since we know the size of the shift has to be less than the
3521 // size of the value, the shift/rotate count is guaranteed to be zero.
3524 if (N2C && N2C->isNullValue())
3527 case ISD::FP_ROUND_INREG: {
3528 EVT EVT = cast<VTSDNode>(N2)->getVT();
3529 assert(VT == N1.getValueType() && "Not an inreg round!");
3530 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3531 "Cannot FP_ROUND_INREG integer types");
3532 assert(EVT.isVector() == VT.isVector() &&
3533 "FP_ROUND_INREG type should be vector iff the operand "
3535 assert((!EVT.isVector() ||
3536 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3537 "Vector element counts must match in FP_ROUND_INREG");
3538 assert(EVT.bitsLE(VT) && "Not rounding down!");
3540 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3544 assert(VT.isFloatingPoint() &&
3545 N1.getValueType().isFloatingPoint() &&
3546 VT.bitsLE(N1.getValueType()) &&
3547 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3548 if (N1.getValueType() == VT) return N1; // noop conversion.
3550 case ISD::AssertSext:
3551 case ISD::AssertZext: {
3552 EVT EVT = cast<VTSDNode>(N2)->getVT();
3553 assert(VT == N1.getValueType() && "Not an inreg extend!");
3554 assert(VT.isInteger() && EVT.isInteger() &&
3555 "Cannot *_EXTEND_INREG FP types");
3556 assert(!EVT.isVector() &&
3557 "AssertSExt/AssertZExt type should be the vector element type "
3558 "rather than the vector type!");
3559 assert(EVT.bitsLE(VT) && "Not extending!");
3560 if (VT == EVT) return N1; // noop assertion.
3563 case ISD::SIGN_EXTEND_INREG: {
3564 EVT EVT = cast<VTSDNode>(N2)->getVT();
3565 assert(VT == N1.getValueType() && "Not an inreg extend!");
3566 assert(VT.isInteger() && EVT.isInteger() &&
3567 "Cannot *_EXTEND_INREG FP types");
3568 assert(EVT.isVector() == VT.isVector() &&
3569 "SIGN_EXTEND_INREG type should be vector iff the operand "
3571 assert((!EVT.isVector() ||
3572 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3573 "Vector element counts must match in SIGN_EXTEND_INREG");
3574 assert(EVT.bitsLE(VT) && "Not extending!");
3575 if (EVT == VT) return N1; // Not actually extending
3577 auto SignExtendInReg = [&](APInt Val) {
3578 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3579 Val <<= Val.getBitWidth() - FromBits;
3580 Val = Val.ashr(Val.getBitWidth() - FromBits);
3581 return getConstant(Val, DL, VT.getScalarType());
3585 APInt Val = N1C->getAPIntValue();
3586 return SignExtendInReg(Val);
3588 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3589 SmallVector<SDValue, 8> Ops;
3590 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3591 SDValue Op = N1.getOperand(i);
3592 if (Op.getOpcode() == ISD::UNDEF) {
3593 Ops.push_back(getUNDEF(VT.getScalarType()));
3596 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op)) {
3597 APInt Val = C->getAPIntValue();
3598 Val = Val.zextOrTrunc(VT.getScalarSizeInBits());
3599 Ops.push_back(SignExtendInReg(Val));
3604 if (Ops.size() == VT.getVectorNumElements())
3605 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3609 case ISD::EXTRACT_VECTOR_ELT:
3610 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3611 if (N1.getOpcode() == ISD::UNDEF)
3612 return getUNDEF(VT);
3614 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3615 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3616 return getUNDEF(VT);
3618 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3619 // expanding copies of large vectors from registers.
3621 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3622 N1.getNumOperands() > 0) {
3624 N1.getOperand(0).getValueType().getVectorNumElements();
3625 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3626 N1.getOperand(N2C->getZExtValue() / Factor),
3627 getConstant(N2C->getZExtValue() % Factor, DL,
3628 N2.getValueType()));
3631 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3632 // expanding large vector constants.
3633 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3634 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3636 if (VT != Elt.getValueType())
3637 // If the vector element type is not legal, the BUILD_VECTOR operands
3638 // are promoted and implicitly truncated, and the result implicitly
3639 // extended. Make that explicit here.
3640 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3645 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3646 // operations are lowered to scalars.
3647 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3648 // If the indices are the same, return the inserted element else
3649 // if the indices are known different, extract the element from
3650 // the original vector.
3651 SDValue N1Op2 = N1.getOperand(2);
3652 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2);
3654 if (N1Op2C && N2C) {
3655 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3656 if (VT == N1.getOperand(1).getValueType())
3657 return N1.getOperand(1);
3659 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3662 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3666 case ISD::EXTRACT_ELEMENT:
3667 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3668 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3669 (N1.getValueType().isInteger() == VT.isInteger()) &&
3670 N1.getValueType() != VT &&
3671 "Wrong types for EXTRACT_ELEMENT!");
3673 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3674 // 64-bit integers into 32-bit parts. Instead of building the extract of
3675 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3676 if (N1.getOpcode() == ISD::BUILD_PAIR)
3677 return N1.getOperand(N2C->getZExtValue());
3679 // EXTRACT_ELEMENT of a constant int is also very common.
3680 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3681 unsigned ElementSize = VT.getSizeInBits();
3682 unsigned Shift = ElementSize * N2C->getZExtValue();
3683 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3684 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3687 case ISD::EXTRACT_SUBVECTOR: {
3689 if (VT.isSimple() && N1.getValueType().isSimple()) {
3690 assert(VT.isVector() && N1.getValueType().isVector() &&
3691 "Extract subvector VTs must be a vectors!");
3692 assert(VT.getVectorElementType() ==
3693 N1.getValueType().getVectorElementType() &&
3694 "Extract subvector VTs must have the same element type!");
3695 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3696 "Extract subvector must be from larger vector to smaller vector!");
3698 if (isa<ConstantSDNode>(Index)) {
3699 assert((VT.getVectorNumElements() +
3700 cast<ConstantSDNode>(Index)->getZExtValue()
3701 <= N1.getValueType().getVectorNumElements())
3702 && "Extract subvector overflow!");
3705 // Trivial extraction.
3706 if (VT.getSimpleVT() == N1.getSimpleValueType())
3713 // Perform trivial constant folding.
3715 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3718 // Constant fold FP operations.
3719 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3720 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3721 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3723 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3724 // Canonicalize constant to RHS if commutative.
3725 std::swap(N1CFP, N2CFP);
3728 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3729 APFloat::opStatus s;
3732 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3733 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3734 return getConstantFP(V1, DL, VT);
3737 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3738 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3739 return getConstantFP(V1, DL, VT);
3742 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3743 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3744 return getConstantFP(V1, DL, VT);
3747 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3748 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3749 s!=APFloat::opDivByZero)) {
3750 return getConstantFP(V1, DL, VT);
3755 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3756 s!=APFloat::opDivByZero)) {
3757 return getConstantFP(V1, DL, VT);
3760 case ISD::FCOPYSIGN:
3762 return getConstantFP(V1, DL, VT);
3767 if (Opcode == ISD::FP_ROUND) {
3768 APFloat V = N1CFP->getValueAPF(); // make copy
3770 // This can return overflow, underflow, or inexact; we don't care.
3771 // FIXME need to be more flexible about rounding mode.
3772 (void)V.convert(EVTToAPFloatSemantics(VT),
3773 APFloat::rmNearestTiesToEven, &ignored);
3774 return getConstantFP(V, DL, VT);
3778 // Canonicalize an UNDEF to the RHS, even over a constant.
3779 if (N1.getOpcode() == ISD::UNDEF) {
3780 if (isCommutativeBinOp(Opcode)) {
3784 case ISD::FP_ROUND_INREG:
3785 case ISD::SIGN_EXTEND_INREG:
3791 return N1; // fold op(undef, arg2) -> undef
3799 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3800 // For vectors, we can't easily build an all zero vector, just return
3807 // Fold a bunch of operators when the RHS is undef.
3808 if (N2.getOpcode() == ISD::UNDEF) {
3811 if (N1.getOpcode() == ISD::UNDEF)
3812 // Handle undef ^ undef -> 0 special case. This is a common
3814 return getConstant(0, DL, VT);
3824 return N2; // fold op(arg1, undef) -> undef
3830 if (getTarget().Options.UnsafeFPMath)
3838 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3839 // For vectors, we can't easily build an all zero vector, just return
3844 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3845 // For vectors, we can't easily build an all one vector, just return
3853 // Memoize this node if possible.
3855 SDVTList VTs = getVTList(VT);
3856 if (VT != MVT::Glue) {
3857 SDValue Ops[] = {N1, N2};
3858 FoldingSetNodeID ID;
3859 AddNodeIDNode(ID, Opcode, VTs, Ops);
3860 AddNodeIDFlags(ID, Opcode, Flags);
3862 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3863 return SDValue(E, 0);
3865 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3867 CSEMap.InsertNode(N, IP);
3869 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3873 return SDValue(N, 0);
3876 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3877 SDValue N1, SDValue N2, SDValue N3) {
3878 // Perform various simplifications.
3879 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3882 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3883 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3884 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3885 if (N1CFP && N2CFP && N3CFP) {
3886 APFloat V1 = N1CFP->getValueAPF();
3887 const APFloat &V2 = N2CFP->getValueAPF();
3888 const APFloat &V3 = N3CFP->getValueAPF();
3889 APFloat::opStatus s =
3890 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3891 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3892 return getConstantFP(V1, DL, VT);
3896 case ISD::CONCAT_VECTORS:
3897 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3898 // one big BUILD_VECTOR.
3899 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3900 N2.getOpcode() == ISD::BUILD_VECTOR &&
3901 N3.getOpcode() == ISD::BUILD_VECTOR) {
3902 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3903 N1.getNode()->op_end());
3904 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3905 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3906 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3910 // Use FoldSetCC to simplify SETCC's.
3911 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3912 if (Simp.getNode()) return Simp;
3917 if (N1C->getZExtValue())
3918 return N2; // select true, X, Y -> X
3919 return N3; // select false, X, Y -> Y
3922 if (N2 == N3) return N2; // select C, X, X -> X
3924 case ISD::VECTOR_SHUFFLE:
3925 llvm_unreachable("should use getVectorShuffle constructor!");
3926 case ISD::INSERT_SUBVECTOR: {
3928 if (VT.isSimple() && N1.getValueType().isSimple()
3929 && N2.getValueType().isSimple()) {
3930 assert(VT.isVector() && N1.getValueType().isVector() &&
3931 N2.getValueType().isVector() &&
3932 "Insert subvector VTs must be a vectors");
3933 assert(VT == N1.getValueType() &&
3934 "Dest and insert subvector source types must match!");
3935 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3936 "Insert subvector must be from smaller vector to larger vector!");
3937 if (isa<ConstantSDNode>(Index)) {
3938 assert((N2.getValueType().getVectorNumElements() +
3939 cast<ConstantSDNode>(Index)->getZExtValue()
3940 <= VT.getVectorNumElements())
3941 && "Insert subvector overflow!");
3944 // Trivial insertion.
3945 if (VT.getSimpleVT() == N2.getSimpleValueType())
3951 // Fold bit_convert nodes from a type to themselves.
3952 if (N1.getValueType() == VT)
3957 // Memoize node if it doesn't produce a flag.
3959 SDVTList VTs = getVTList(VT);
3960 if (VT != MVT::Glue) {
3961 SDValue Ops[] = { N1, N2, N3 };
3962 FoldingSetNodeID ID;
3963 AddNodeIDNode(ID, Opcode, VTs, Ops);
3965 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3966 return SDValue(E, 0);
3968 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3969 DL.getDebugLoc(), VTs, N1, N2, N3);
3970 CSEMap.InsertNode(N, IP);
3972 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3973 DL.getDebugLoc(), VTs, N1, N2, N3);
3977 return SDValue(N, 0);
3980 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3981 SDValue N1, SDValue N2, SDValue N3,
3983 SDValue Ops[] = { N1, N2, N3, N4 };
3984 return getNode(Opcode, DL, VT, Ops);
3987 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3988 SDValue N1, SDValue N2, SDValue N3,
3989 SDValue N4, SDValue N5) {
3990 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3991 return getNode(Opcode, DL, VT, Ops);
3994 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3995 /// the incoming stack arguments to be loaded from the stack.
3996 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3997 SmallVector<SDValue, 8> ArgChains;
3999 // Include the original chain at the beginning of the list. When this is
4000 // used by target LowerCall hooks, this helps legalize find the
4001 // CALLSEQ_BEGIN node.
4002 ArgChains.push_back(Chain);
4004 // Add a chain value for each stack argument.
4005 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
4006 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
4007 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
4008 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
4009 if (FI->getIndex() < 0)
4010 ArgChains.push_back(SDValue(L, 1));
4012 // Build a tokenfactor for all the chains.
4013 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
4016 /// getMemsetValue - Vectorized representation of the memset value
4018 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
4020 assert(Value.getOpcode() != ISD::UNDEF);
4022 unsigned NumBits = VT.getScalarType().getSizeInBits();
4023 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
4024 assert(C->getAPIntValue().getBitWidth() == 8);
4025 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
4027 return DAG.getConstant(Val, dl, VT);
4028 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
4032 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
4033 EVT IntVT = VT.getScalarType();
4034 if (!IntVT.isInteger())
4035 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
4037 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
4039 // Use a multiplication with 0x010101... to extend the input to the
4041 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
4042 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
4043 DAG.getConstant(Magic, dl, IntVT));
4046 if (VT != Value.getValueType() && !VT.isInteger())
4047 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
4048 if (VT != Value.getValueType()) {
4049 assert(VT.getVectorElementType() == Value.getValueType() &&
4050 "value type should be one vector element here");
4051 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
4052 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
4058 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
4059 /// used when a memcpy is turned into a memset when the source is a constant
4061 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
4062 const TargetLowering &TLI, StringRef Str) {
4063 // Handle vector with all elements zero.
4066 return DAG.getConstant(0, dl, VT);
4067 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
4068 return DAG.getConstantFP(0.0, dl, VT);
4069 else if (VT.isVector()) {
4070 unsigned NumElts = VT.getVectorNumElements();
4071 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
4072 return DAG.getNode(ISD::BITCAST, dl, VT,
4073 DAG.getConstant(0, dl,
4074 EVT::getVectorVT(*DAG.getContext(),
4077 llvm_unreachable("Expected type!");
4080 assert(!VT.isVector() && "Can't handle vector type here!");
4081 unsigned NumVTBits = VT.getSizeInBits();
4082 unsigned NumVTBytes = NumVTBits / 8;
4083 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
4085 APInt Val(NumVTBits, 0);
4086 if (DAG.getDataLayout().isLittleEndian()) {
4087 for (unsigned i = 0; i != NumBytes; ++i)
4088 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4090 for (unsigned i = 0; i != NumBytes; ++i)
4091 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4094 // If the "cost" of materializing the integer immediate is less than the cost
4095 // of a load, then it is cost effective to turn the load into the immediate.
4096 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4097 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4098 return DAG.getConstant(Val, dl, VT);
4099 return SDValue(nullptr, 0);
4102 /// getMemBasePlusOffset - Returns base and offset node for the
4104 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4105 SelectionDAG &DAG) {
4106 EVT VT = Base.getValueType();
4107 return DAG.getNode(ISD::ADD, dl,
4108 VT, Base, DAG.getConstant(Offset, dl, VT));
4111 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4113 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4114 unsigned SrcDelta = 0;
4115 GlobalAddressSDNode *G = nullptr;
4116 if (Src.getOpcode() == ISD::GlobalAddress)
4117 G = cast<GlobalAddressSDNode>(Src);
4118 else if (Src.getOpcode() == ISD::ADD &&
4119 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4120 Src.getOperand(1).getOpcode() == ISD::Constant) {
4121 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4122 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4127 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4130 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4131 /// Return true if the number of memory ops is below the threshold (Limit).
4132 /// It returns the types of the sequence of memory ops to perform
4133 /// memset / memcpy by reference.
4134 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4135 unsigned Limit, uint64_t Size,
4136 unsigned DstAlign, unsigned SrcAlign,
4142 const TargetLowering &TLI) {
4143 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4144 "Expecting memcpy / memset source to meet alignment requirement!");
4145 // If 'SrcAlign' is zero, that means the memory operation does not need to
4146 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4147 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4148 // is the specified alignment of the memory operation. If it is zero, that
4149 // means it's possible to change the alignment of the destination.
4150 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4151 // not need to be loaded.
4152 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4153 IsMemset, ZeroMemset, MemcpyStrSrc,
4154 DAG.getMachineFunction());
4156 if (VT == MVT::Other) {
4158 if (DstAlign >= DAG.getDataLayout().getPointerPrefAlignment(AS) ||
4159 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4160 VT = TLI.getPointerTy(DAG.getDataLayout());
4162 switch (DstAlign & 7) {
4163 case 0: VT = MVT::i64; break;
4164 case 4: VT = MVT::i32; break;
4165 case 2: VT = MVT::i16; break;
4166 default: VT = MVT::i8; break;
4171 while (!TLI.isTypeLegal(LVT))
4172 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4173 assert(LVT.isInteger());
4179 unsigned NumMemOps = 0;
4181 unsigned VTSize = VT.getSizeInBits() / 8;
4182 while (VTSize > Size) {
4183 // For now, only use non-vector load / store's for the left-over pieces.
4188 if (VT.isVector() || VT.isFloatingPoint()) {
4189 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4190 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4191 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4193 else if (NewVT == MVT::i64 &&
4194 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4195 TLI.isSafeMemOpType(MVT::f64)) {
4196 // i64 is usually not legal on 32-bit targets, but f64 may be.
4204 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4205 if (NewVT == MVT::i8)
4207 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4209 NewVTSize = NewVT.getSizeInBits() / 8;
4211 // If the new VT cannot cover all of the remaining bits, then consider
4212 // issuing a (or a pair of) unaligned and overlapping load / store.
4213 // FIXME: Only does this for 64-bit or more since we don't have proper
4214 // cost model for unaligned load / store.
4217 if (NumMemOps && AllowOverlap &&
4218 VTSize >= 8 && NewVTSize < Size &&
4219 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4227 if (++NumMemOps > Limit)
4230 MemOps.push_back(VT);
4237 static bool shouldLowerMemFuncForSize(const MachineFunction &MF) {
4238 // On Darwin, -Os means optimize for size without hurting performance, so
4239 // only really optimize for size when -Oz (MinSize) is used.
4240 if (MF.getTarget().getTargetTriple().isOSDarwin())
4241 return MF.getFunction()->optForMinSize();
4242 return MF.getFunction()->optForSize();
4245 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4246 SDValue Chain, SDValue Dst,
4247 SDValue Src, uint64_t Size,
4248 unsigned Align, bool isVol,
4250 MachinePointerInfo DstPtrInfo,
4251 MachinePointerInfo SrcPtrInfo) {
4252 // Turn a memcpy of undef to nop.
4253 if (Src.getOpcode() == ISD::UNDEF)
4256 // Expand memcpy to a series of load and store ops if the size operand falls
4257 // below a certain threshold.
4258 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4259 // rather than maybe a humongous number of loads and stores.
4260 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4261 std::vector<EVT> MemOps;
4262 bool DstAlignCanChange = false;
4263 MachineFunction &MF = DAG.getMachineFunction();
4264 MachineFrameInfo *MFI = MF.getFrameInfo();
4265 bool OptSize = shouldLowerMemFuncForSize(MF);
4266 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4267 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4268 DstAlignCanChange = true;
4269 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4270 if (Align > SrcAlign)
4273 bool CopyFromStr = isMemSrcFromString(Src, Str);
4274 bool isZeroStr = CopyFromStr && Str.empty();
4275 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4277 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4278 (DstAlignCanChange ? 0 : Align),
4279 (isZeroStr ? 0 : SrcAlign),
4280 false, false, CopyFromStr, true, DAG, TLI))
4283 if (DstAlignCanChange) {
4284 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4285 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4287 // Don't promote to an alignment that would require dynamic stack
4289 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4290 if (!TRI->needsStackRealignment(MF))
4291 while (NewAlign > Align &&
4292 DAG.getDataLayout().exceedsNaturalStackAlignment(NewAlign))
4295 if (NewAlign > Align) {
4296 // Give the stack frame object a larger alignment if needed.
4297 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4298 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4303 SmallVector<SDValue, 8> OutChains;
4304 unsigned NumMemOps = MemOps.size();
4305 uint64_t SrcOff = 0, DstOff = 0;
4306 for (unsigned i = 0; i != NumMemOps; ++i) {
4308 unsigned VTSize = VT.getSizeInBits() / 8;
4309 SDValue Value, Store;
4311 if (VTSize > Size) {
4312 // Issuing an unaligned load / store pair that overlaps with the previous
4313 // pair. Adjust the offset accordingly.
4314 assert(i == NumMemOps-1 && i != 0);
4315 SrcOff -= VTSize - Size;
4316 DstOff -= VTSize - Size;
4320 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4321 // It's unlikely a store of a vector immediate can be done in a single
4322 // instruction. It would require a load from a constantpool first.
4323 // We only handle zero vectors here.
4324 // FIXME: Handle other cases where store of vector immediate is done in
4325 // a single instruction.
4326 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4327 if (Value.getNode())
4328 Store = DAG.getStore(Chain, dl, Value,
4329 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4330 DstPtrInfo.getWithOffset(DstOff), isVol,
4334 if (!Store.getNode()) {
4335 // The type might not be legal for the target. This should only happen
4336 // if the type is smaller than a legal type, as on PPC, so the right
4337 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4338 // to Load/Store if NVT==VT.
4339 // FIXME does the case above also need this?
4340 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4341 assert(NVT.bitsGE(VT));
4342 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4343 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4344 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4345 false, MinAlign(SrcAlign, SrcOff));
4346 Store = DAG.getTruncStore(Chain, dl, Value,
4347 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4348 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4351 OutChains.push_back(Store);
4357 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4360 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4361 SDValue Chain, SDValue Dst,
4362 SDValue Src, uint64_t Size,
4363 unsigned Align, bool isVol,
4365 MachinePointerInfo DstPtrInfo,
4366 MachinePointerInfo SrcPtrInfo) {
4367 // Turn a memmove of undef to nop.
4368 if (Src.getOpcode() == ISD::UNDEF)
4371 // Expand memmove to a series of load and store ops if the size operand falls
4372 // below a certain threshold.
4373 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4374 std::vector<EVT> MemOps;
4375 bool DstAlignCanChange = false;
4376 MachineFunction &MF = DAG.getMachineFunction();
4377 MachineFrameInfo *MFI = MF.getFrameInfo();
4378 bool OptSize = shouldLowerMemFuncForSize(MF);
4379 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4380 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4381 DstAlignCanChange = true;
4382 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4383 if (Align > SrcAlign)
4385 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4387 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4388 (DstAlignCanChange ? 0 : Align), SrcAlign,
4389 false, false, false, false, DAG, TLI))
4392 if (DstAlignCanChange) {
4393 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4394 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4395 if (NewAlign > Align) {
4396 // Give the stack frame object a larger alignment if needed.
4397 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4398 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4403 uint64_t SrcOff = 0, DstOff = 0;
4404 SmallVector<SDValue, 8> LoadValues;
4405 SmallVector<SDValue, 8> LoadChains;
4406 SmallVector<SDValue, 8> OutChains;
4407 unsigned NumMemOps = MemOps.size();
4408 for (unsigned i = 0; i < NumMemOps; i++) {
4410 unsigned VTSize = VT.getSizeInBits() / 8;
4413 Value = DAG.getLoad(VT, dl, Chain,
4414 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4415 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4416 false, false, SrcAlign);
4417 LoadValues.push_back(Value);
4418 LoadChains.push_back(Value.getValue(1));
4421 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4423 for (unsigned i = 0; i < NumMemOps; i++) {
4425 unsigned VTSize = VT.getSizeInBits() / 8;
4428 Store = DAG.getStore(Chain, dl, LoadValues[i],
4429 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4430 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4431 OutChains.push_back(Store);
4435 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4438 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4441 /// \param DAG Selection DAG where lowered code is placed.
4442 /// \param dl Link to corresponding IR location.
4443 /// \param Chain Control flow dependency.
4444 /// \param Dst Pointer to destination memory location.
4445 /// \param Src Value of byte to write into the memory.
4446 /// \param Size Number of bytes to write.
4447 /// \param Align Alignment of the destination in bytes.
4448 /// \param isVol True if destination is volatile.
4449 /// \param DstPtrInfo IR information on the memory pointer.
4450 /// \returns New head in the control flow, if lowering was successful, empty
4451 /// SDValue otherwise.
4453 /// The function tries to replace 'llvm.memset' intrinsic with several store
4454 /// operations and value calculation code. This is usually profitable for small
4456 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4457 SDValue Chain, SDValue Dst,
4458 SDValue Src, uint64_t Size,
4459 unsigned Align, bool isVol,
4460 MachinePointerInfo DstPtrInfo) {
4461 // Turn a memset of undef to nop.
4462 if (Src.getOpcode() == ISD::UNDEF)
4465 // Expand memset to a series of load/store ops if the size operand
4466 // falls below a certain threshold.
4467 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4468 std::vector<EVT> MemOps;
4469 bool DstAlignCanChange = false;
4470 MachineFunction &MF = DAG.getMachineFunction();
4471 MachineFrameInfo *MFI = MF.getFrameInfo();
4472 bool OptSize = shouldLowerMemFuncForSize(MF);
4473 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4474 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4475 DstAlignCanChange = true;
4477 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4478 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4479 Size, (DstAlignCanChange ? 0 : Align), 0,
4480 true, IsZeroVal, false, true, DAG, TLI))
4483 if (DstAlignCanChange) {
4484 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4485 unsigned NewAlign = (unsigned)DAG.getDataLayout().getABITypeAlignment(Ty);
4486 if (NewAlign > Align) {
4487 // Give the stack frame object a larger alignment if needed.
4488 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4489 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4494 SmallVector<SDValue, 8> OutChains;
4495 uint64_t DstOff = 0;
4496 unsigned NumMemOps = MemOps.size();
4498 // Find the largest store and generate the bit pattern for it.
4499 EVT LargestVT = MemOps[0];
4500 for (unsigned i = 1; i < NumMemOps; i++)
4501 if (MemOps[i].bitsGT(LargestVT))
4502 LargestVT = MemOps[i];
4503 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4505 for (unsigned i = 0; i < NumMemOps; i++) {
4507 unsigned VTSize = VT.getSizeInBits() / 8;
4508 if (VTSize > Size) {
4509 // Issuing an unaligned load / store pair that overlaps with the previous
4510 // pair. Adjust the offset accordingly.
4511 assert(i == NumMemOps-1 && i != 0);
4512 DstOff -= VTSize - Size;
4515 // If this store is smaller than the largest store see whether we can get
4516 // the smaller value for free with a truncate.
4517 SDValue Value = MemSetValue;
4518 if (VT.bitsLT(LargestVT)) {
4519 if (!LargestVT.isVector() && !VT.isVector() &&
4520 TLI.isTruncateFree(LargestVT, VT))
4521 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4523 Value = getMemsetValue(Src, VT, DAG, dl);
4525 assert(Value.getValueType() == VT && "Value with wrong type.");
4526 SDValue Store = DAG.getStore(Chain, dl, Value,
4527 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4528 DstPtrInfo.getWithOffset(DstOff),
4529 isVol, false, Align);
4530 OutChains.push_back(Store);
4531 DstOff += VT.getSizeInBits() / 8;
4535 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4538 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4539 SDValue Src, SDValue Size,
4540 unsigned Align, bool isVol, bool AlwaysInline,
4541 bool isTailCall, MachinePointerInfo DstPtrInfo,
4542 MachinePointerInfo SrcPtrInfo) {
4543 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4545 // Check to see if we should lower the memcpy to loads and stores first.
4546 // For cases within the target-specified limits, this is the best choice.
4547 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4549 // Memcpy with size zero? Just return the original chain.
4550 if (ConstantSize->isNullValue())
4553 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4554 ConstantSize->getZExtValue(),Align,
4555 isVol, false, DstPtrInfo, SrcPtrInfo);
4556 if (Result.getNode())
4560 // Then check to see if we should lower the memcpy with target-specific
4561 // code. If the target chooses to do this, this is the next best.
4563 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4564 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4565 DstPtrInfo, SrcPtrInfo);
4566 if (Result.getNode())
4570 // If we really need inline code and the target declined to provide it,
4571 // use a (potentially long) sequence of loads and stores.
4573 assert(ConstantSize && "AlwaysInline requires a constant size!");
4574 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4575 ConstantSize->getZExtValue(), Align, isVol,
4576 true, DstPtrInfo, SrcPtrInfo);
4579 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4580 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4581 // respect volatile, so they may do things like read or write memory
4582 // beyond the given memory regions. But fixing this isn't easy, and most
4583 // people don't care.
4585 // Emit a library call.
4586 TargetLowering::ArgListTy Args;
4587 TargetLowering::ArgListEntry Entry;
4588 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4589 Entry.Node = Dst; Args.push_back(Entry);
4590 Entry.Node = Src; Args.push_back(Entry);
4591 Entry.Node = Size; Args.push_back(Entry);
4592 // FIXME: pass in SDLoc
4593 TargetLowering::CallLoweringInfo CLI(*this);
4596 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4597 Type::getVoidTy(*getContext()),
4598 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4599 TLI->getPointerTy(getDataLayout())),
4602 .setTailCall(isTailCall);
4604 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4605 return CallResult.second;
4608 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4609 SDValue Src, SDValue Size,
4610 unsigned Align, bool isVol, bool isTailCall,
4611 MachinePointerInfo DstPtrInfo,
4612 MachinePointerInfo SrcPtrInfo) {
4613 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4615 // Check to see if we should lower the memmove to loads and stores first.
4616 // For cases within the target-specified limits, this is the best choice.
4617 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4619 // Memmove with size zero? Just return the original chain.
4620 if (ConstantSize->isNullValue())
4624 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4625 ConstantSize->getZExtValue(), Align, isVol,
4626 false, DstPtrInfo, SrcPtrInfo);
4627 if (Result.getNode())
4631 // Then check to see if we should lower the memmove with target-specific
4632 // code. If the target chooses to do this, this is the next best.
4634 SDValue Result = TSI->EmitTargetCodeForMemmove(
4635 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4636 if (Result.getNode())
4640 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4641 // not be safe. See memcpy above for more details.
4643 // Emit a library call.
4644 TargetLowering::ArgListTy Args;
4645 TargetLowering::ArgListEntry Entry;
4646 Entry.Ty = getDataLayout().getIntPtrType(*getContext());
4647 Entry.Node = Dst; Args.push_back(Entry);
4648 Entry.Node = Src; Args.push_back(Entry);
4649 Entry.Node = Size; Args.push_back(Entry);
4650 // FIXME: pass in SDLoc
4651 TargetLowering::CallLoweringInfo CLI(*this);
4654 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4655 Type::getVoidTy(*getContext()),
4656 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4657 TLI->getPointerTy(getDataLayout())),
4660 .setTailCall(isTailCall);
4662 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4663 return CallResult.second;
4666 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4667 SDValue Src, SDValue Size,
4668 unsigned Align, bool isVol, bool isTailCall,
4669 MachinePointerInfo DstPtrInfo) {
4670 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4672 // Check to see if we should lower the memset to stores first.
4673 // For cases within the target-specified limits, this is the best choice.
4674 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4676 // Memset with size zero? Just return the original chain.
4677 if (ConstantSize->isNullValue())
4681 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4682 Align, isVol, DstPtrInfo);
4684 if (Result.getNode())
4688 // Then check to see if we should lower the memset with target-specific
4689 // code. If the target chooses to do this, this is the next best.
4691 SDValue Result = TSI->EmitTargetCodeForMemset(
4692 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4693 if (Result.getNode())
4697 // Emit a library call.
4698 Type *IntPtrTy = getDataLayout().getIntPtrType(*getContext());
4699 TargetLowering::ArgListTy Args;
4700 TargetLowering::ArgListEntry Entry;
4701 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4702 Args.push_back(Entry);
4704 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4705 Args.push_back(Entry);
4707 Entry.Ty = IntPtrTy;
4708 Args.push_back(Entry);
4710 // FIXME: pass in SDLoc
4711 TargetLowering::CallLoweringInfo CLI(*this);
4714 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4715 Type::getVoidTy(*getContext()),
4716 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4717 TLI->getPointerTy(getDataLayout())),
4720 .setTailCall(isTailCall);
4722 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4723 return CallResult.second;
4726 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4727 SDVTList VTList, ArrayRef<SDValue> Ops,
4728 MachineMemOperand *MMO,
4729 AtomicOrdering SuccessOrdering,
4730 AtomicOrdering FailureOrdering,
4731 SynchronizationScope SynchScope) {
4732 FoldingSetNodeID ID;
4733 ID.AddInteger(MemVT.getRawBits());
4734 AddNodeIDNode(ID, Opcode, VTList, Ops);
4735 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4737 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4738 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4739 return SDValue(E, 0);
4742 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4743 // SDNode doesn't have access to it. This memory will be "leaked" when
4744 // the node is deallocated, but recovered when the allocator is released.
4745 // If the number of operands is less than 5 we use AtomicSDNode's internal
4747 unsigned NumOps = Ops.size();
4748 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4751 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4752 dl.getDebugLoc(), VTList, MemVT,
4753 Ops.data(), DynOps, NumOps, MMO,
4754 SuccessOrdering, FailureOrdering,
4756 CSEMap.InsertNode(N, IP);
4758 return SDValue(N, 0);
4761 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4762 SDVTList VTList, ArrayRef<SDValue> Ops,
4763 MachineMemOperand *MMO,
4764 AtomicOrdering Ordering,
4765 SynchronizationScope SynchScope) {
4766 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4767 Ordering, SynchScope);
4770 SDValue SelectionDAG::getAtomicCmpSwap(
4771 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4772 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4773 unsigned Alignment, AtomicOrdering SuccessOrdering,
4774 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4775 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4776 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4777 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4779 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4780 Alignment = getEVTAlignment(MemVT);
4782 MachineFunction &MF = getMachineFunction();
4784 // FIXME: Volatile isn't really correct; we should keep track of atomic
4785 // orderings in the memoperand.
4786 unsigned Flags = MachineMemOperand::MOVolatile;
4787 Flags |= MachineMemOperand::MOLoad;
4788 Flags |= MachineMemOperand::MOStore;
4790 MachineMemOperand *MMO =
4791 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4793 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4794 SuccessOrdering, FailureOrdering, SynchScope);
4797 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4798 SDVTList VTs, SDValue Chain, SDValue Ptr,
4799 SDValue Cmp, SDValue Swp,
4800 MachineMemOperand *MMO,
4801 AtomicOrdering SuccessOrdering,
4802 AtomicOrdering FailureOrdering,
4803 SynchronizationScope SynchScope) {
4804 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4805 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4806 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4808 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4809 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4810 SuccessOrdering, FailureOrdering, SynchScope);
4813 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4815 SDValue Ptr, SDValue Val,
4816 const Value* PtrVal,
4818 AtomicOrdering Ordering,
4819 SynchronizationScope SynchScope) {
4820 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4821 Alignment = getEVTAlignment(MemVT);
4823 MachineFunction &MF = getMachineFunction();
4824 // An atomic store does not load. An atomic load does not store.
4825 // (An atomicrmw obviously both loads and stores.)
4826 // For now, atomics are considered to be volatile always, and they are
4828 // FIXME: Volatile isn't really correct; we should keep track of atomic
4829 // orderings in the memoperand.
4830 unsigned Flags = MachineMemOperand::MOVolatile;
4831 if (Opcode != ISD::ATOMIC_STORE)
4832 Flags |= MachineMemOperand::MOLoad;
4833 if (Opcode != ISD::ATOMIC_LOAD)
4834 Flags |= MachineMemOperand::MOStore;
4836 MachineMemOperand *MMO =
4837 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4838 MemVT.getStoreSize(), Alignment);
4840 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4841 Ordering, SynchScope);
4844 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4846 SDValue Ptr, SDValue Val,
4847 MachineMemOperand *MMO,
4848 AtomicOrdering Ordering,
4849 SynchronizationScope SynchScope) {
4850 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4851 Opcode == ISD::ATOMIC_LOAD_SUB ||
4852 Opcode == ISD::ATOMIC_LOAD_AND ||
4853 Opcode == ISD::ATOMIC_LOAD_OR ||
4854 Opcode == ISD::ATOMIC_LOAD_XOR ||
4855 Opcode == ISD::ATOMIC_LOAD_NAND ||
4856 Opcode == ISD::ATOMIC_LOAD_MIN ||
4857 Opcode == ISD::ATOMIC_LOAD_MAX ||
4858 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4859 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4860 Opcode == ISD::ATOMIC_SWAP ||
4861 Opcode == ISD::ATOMIC_STORE) &&
4862 "Invalid Atomic Op");
4864 EVT VT = Val.getValueType();
4866 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4867 getVTList(VT, MVT::Other);
4868 SDValue Ops[] = {Chain, Ptr, Val};
4869 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4872 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4873 EVT VT, SDValue Chain,
4875 MachineMemOperand *MMO,
4876 AtomicOrdering Ordering,
4877 SynchronizationScope SynchScope) {
4878 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4880 SDVTList VTs = getVTList(VT, MVT::Other);
4881 SDValue Ops[] = {Chain, Ptr};
4882 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4885 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4886 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4887 if (Ops.size() == 1)
4890 SmallVector<EVT, 4> VTs;
4891 VTs.reserve(Ops.size());
4892 for (unsigned i = 0; i < Ops.size(); ++i)
4893 VTs.push_back(Ops[i].getValueType());
4894 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4898 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4899 ArrayRef<SDValue> Ops,
4900 EVT MemVT, MachinePointerInfo PtrInfo,
4901 unsigned Align, bool Vol,
4902 bool ReadMem, bool WriteMem, unsigned Size) {
4903 if (Align == 0) // Ensure that codegen never sees alignment 0
4904 Align = getEVTAlignment(MemVT);
4906 MachineFunction &MF = getMachineFunction();
4909 Flags |= MachineMemOperand::MOStore;
4911 Flags |= MachineMemOperand::MOLoad;
4913 Flags |= MachineMemOperand::MOVolatile;
4915 Size = MemVT.getStoreSize();
4916 MachineMemOperand *MMO =
4917 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4919 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4923 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4924 ArrayRef<SDValue> Ops, EVT MemVT,
4925 MachineMemOperand *MMO) {
4926 assert((Opcode == ISD::INTRINSIC_VOID ||
4927 Opcode == ISD::INTRINSIC_W_CHAIN ||
4928 Opcode == ISD::PREFETCH ||
4929 Opcode == ISD::LIFETIME_START ||
4930 Opcode == ISD::LIFETIME_END ||
4931 (Opcode <= INT_MAX &&
4932 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4933 "Opcode is not a memory-accessing opcode!");
4935 // Memoize the node unless it returns a flag.
4936 MemIntrinsicSDNode *N;
4937 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4938 FoldingSetNodeID ID;
4939 AddNodeIDNode(ID, Opcode, VTList, Ops);
4940 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4942 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4943 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4944 return SDValue(E, 0);
4947 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4948 dl.getDebugLoc(), VTList, Ops,
4950 CSEMap.InsertNode(N, IP);
4952 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4953 dl.getDebugLoc(), VTList, Ops,
4957 return SDValue(N, 0);
4960 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4961 /// MachinePointerInfo record from it. This is particularly useful because the
4962 /// code generator has many cases where it doesn't bother passing in a
4963 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4964 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4965 int64_t Offset = 0) {
4966 // If this is FI+Offset, we can model it.
4967 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4968 return MachinePointerInfo::getFixedStack(DAG.getMachineFunction(),
4969 FI->getIndex(), Offset);
4971 // If this is (FI+Offset1)+Offset2, we can model it.
4972 if (Ptr.getOpcode() != ISD::ADD ||
4973 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4974 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4975 return MachinePointerInfo();
4977 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4978 return MachinePointerInfo::getFixedStack(
4979 DAG.getMachineFunction(), FI,
4980 Offset + cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4983 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4984 /// MachinePointerInfo record from it. This is particularly useful because the
4985 /// code generator has many cases where it doesn't bother passing in a
4986 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4987 static MachinePointerInfo InferPointerInfo(SelectionDAG &DAG, SDValue Ptr,
4989 // If the 'Offset' value isn't a constant, we can't handle this.
4990 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4991 return InferPointerInfo(DAG, Ptr, OffsetNode->getSExtValue());
4992 if (OffsetOp.getOpcode() == ISD::UNDEF)
4993 return InferPointerInfo(DAG, Ptr);
4994 return MachinePointerInfo();
4999 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5000 EVT VT, SDLoc dl, SDValue Chain,
5001 SDValue Ptr, SDValue Offset,
5002 MachinePointerInfo PtrInfo, EVT MemVT,
5003 bool isVolatile, bool isNonTemporal, bool isInvariant,
5004 unsigned Alignment, const AAMDNodes &AAInfo,
5005 const MDNode *Ranges) {
5006 assert(Chain.getValueType() == MVT::Other &&
5007 "Invalid chain type");
5008 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5009 Alignment = getEVTAlignment(VT);
5011 unsigned Flags = MachineMemOperand::MOLoad;
5013 Flags |= MachineMemOperand::MOVolatile;
5015 Flags |= MachineMemOperand::MONonTemporal;
5017 Flags |= MachineMemOperand::MOInvariant;
5019 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
5021 if (PtrInfo.V.isNull())
5022 PtrInfo = InferPointerInfo(*this, Ptr, Offset);
5024 MachineFunction &MF = getMachineFunction();
5025 MachineMemOperand *MMO =
5026 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
5028 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
5032 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
5033 EVT VT, SDLoc dl, SDValue Chain,
5034 SDValue Ptr, SDValue Offset, EVT MemVT,
5035 MachineMemOperand *MMO) {
5037 ExtType = ISD::NON_EXTLOAD;
5038 } else if (ExtType == ISD::NON_EXTLOAD) {
5039 assert(VT == MemVT && "Non-extending load from different memory type!");
5042 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
5043 "Should only be an extending load, not truncating!");
5044 assert(VT.isInteger() == MemVT.isInteger() &&
5045 "Cannot convert from FP to Int or Int -> FP!");
5046 assert(VT.isVector() == MemVT.isVector() &&
5047 "Cannot use an ext load to convert to or from a vector!");
5048 assert((!VT.isVector() ||
5049 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
5050 "Cannot use an ext load to change the number of vector elements!");
5053 bool Indexed = AM != ISD::UNINDEXED;
5054 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
5055 "Unindexed load with an offset!");
5057 SDVTList VTs = Indexed ?
5058 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
5059 SDValue Ops[] = { Chain, Ptr, Offset };
5060 FoldingSetNodeID ID;
5061 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
5062 ID.AddInteger(MemVT.getRawBits());
5063 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
5064 MMO->isNonTemporal(),
5065 MMO->isInvariant()));
5066 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5068 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5069 cast<LoadSDNode>(E)->refineAlignment(MMO);
5070 return SDValue(E, 0);
5072 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
5073 dl.getDebugLoc(), VTs, AM, ExtType,
5075 CSEMap.InsertNode(N, IP);
5077 return SDValue(N, 0);
5080 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5081 SDValue Chain, SDValue Ptr,
5082 MachinePointerInfo PtrInfo,
5083 bool isVolatile, bool isNonTemporal,
5084 bool isInvariant, unsigned Alignment,
5085 const AAMDNodes &AAInfo,
5086 const MDNode *Ranges) {
5087 SDValue Undef = getUNDEF(Ptr.getValueType());
5088 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5089 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
5093 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
5094 SDValue Chain, SDValue Ptr,
5095 MachineMemOperand *MMO) {
5096 SDValue Undef = getUNDEF(Ptr.getValueType());
5097 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
5101 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5102 SDValue Chain, SDValue Ptr,
5103 MachinePointerInfo PtrInfo, EVT MemVT,
5104 bool isVolatile, bool isNonTemporal,
5105 bool isInvariant, unsigned Alignment,
5106 const AAMDNodes &AAInfo) {
5107 SDValue Undef = getUNDEF(Ptr.getValueType());
5108 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5109 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5114 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5115 SDValue Chain, SDValue Ptr, EVT MemVT,
5116 MachineMemOperand *MMO) {
5117 SDValue Undef = getUNDEF(Ptr.getValueType());
5118 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5123 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5124 SDValue Offset, ISD::MemIndexedMode AM) {
5125 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5126 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5127 "Load is already a indexed load!");
5128 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5129 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5130 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5131 false, LD->getAlignment());
5134 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5135 SDValue Ptr, MachinePointerInfo PtrInfo,
5136 bool isVolatile, bool isNonTemporal,
5137 unsigned Alignment, const AAMDNodes &AAInfo) {
5138 assert(Chain.getValueType() == MVT::Other &&
5139 "Invalid chain type");
5140 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5141 Alignment = getEVTAlignment(Val.getValueType());
5143 unsigned Flags = MachineMemOperand::MOStore;
5145 Flags |= MachineMemOperand::MOVolatile;
5147 Flags |= MachineMemOperand::MONonTemporal;
5149 if (PtrInfo.V.isNull())
5150 PtrInfo = InferPointerInfo(*this, Ptr);
5152 MachineFunction &MF = getMachineFunction();
5153 MachineMemOperand *MMO =
5154 MF.getMachineMemOperand(PtrInfo, Flags,
5155 Val.getValueType().getStoreSize(), Alignment,
5158 return getStore(Chain, dl, Val, Ptr, MMO);
5161 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5162 SDValue Ptr, MachineMemOperand *MMO) {
5163 assert(Chain.getValueType() == MVT::Other &&
5164 "Invalid chain type");
5165 EVT VT = Val.getValueType();
5166 SDVTList VTs = getVTList(MVT::Other);
5167 SDValue Undef = getUNDEF(Ptr.getValueType());
5168 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5169 FoldingSetNodeID ID;
5170 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5171 ID.AddInteger(VT.getRawBits());
5172 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5173 MMO->isNonTemporal(), MMO->isInvariant()));
5174 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5176 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5177 cast<StoreSDNode>(E)->refineAlignment(MMO);
5178 return SDValue(E, 0);
5180 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5181 dl.getDebugLoc(), VTs,
5182 ISD::UNINDEXED, false, VT, MMO);
5183 CSEMap.InsertNode(N, IP);
5185 return SDValue(N, 0);
5188 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5189 SDValue Ptr, MachinePointerInfo PtrInfo,
5190 EVT SVT,bool isVolatile, bool isNonTemporal,
5192 const AAMDNodes &AAInfo) {
5193 assert(Chain.getValueType() == MVT::Other &&
5194 "Invalid chain type");
5195 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5196 Alignment = getEVTAlignment(SVT);
5198 unsigned Flags = MachineMemOperand::MOStore;
5200 Flags |= MachineMemOperand::MOVolatile;
5202 Flags |= MachineMemOperand::MONonTemporal;
5204 if (PtrInfo.V.isNull())
5205 PtrInfo = InferPointerInfo(*this, Ptr);
5207 MachineFunction &MF = getMachineFunction();
5208 MachineMemOperand *MMO =
5209 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5212 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5215 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5216 SDValue Ptr, EVT SVT,
5217 MachineMemOperand *MMO) {
5218 EVT VT = Val.getValueType();
5220 assert(Chain.getValueType() == MVT::Other &&
5221 "Invalid chain type");
5223 return getStore(Chain, dl, Val, Ptr, MMO);
5225 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5226 "Should only be a truncating store, not extending!");
5227 assert(VT.isInteger() == SVT.isInteger() &&
5228 "Can't do FP-INT conversion!");
5229 assert(VT.isVector() == SVT.isVector() &&
5230 "Cannot use trunc store to convert to or from a vector!");
5231 assert((!VT.isVector() ||
5232 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5233 "Cannot use trunc store to change the number of vector elements!");
5235 SDVTList VTs = getVTList(MVT::Other);
5236 SDValue Undef = getUNDEF(Ptr.getValueType());
5237 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5238 FoldingSetNodeID ID;
5239 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5240 ID.AddInteger(SVT.getRawBits());
5241 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5242 MMO->isNonTemporal(), MMO->isInvariant()));
5243 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5245 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5246 cast<StoreSDNode>(E)->refineAlignment(MMO);
5247 return SDValue(E, 0);
5249 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5250 dl.getDebugLoc(), VTs,
5251 ISD::UNINDEXED, true, SVT, MMO);
5252 CSEMap.InsertNode(N, IP);
5254 return SDValue(N, 0);
5258 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5259 SDValue Offset, ISD::MemIndexedMode AM) {
5260 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5261 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5262 "Store is already a indexed store!");
5263 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5264 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5265 FoldingSetNodeID ID;
5266 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5267 ID.AddInteger(ST->getMemoryVT().getRawBits());
5268 ID.AddInteger(ST->getRawSubclassData());
5269 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5271 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5272 return SDValue(E, 0);
5274 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5275 dl.getDebugLoc(), VTs, AM,
5276 ST->isTruncatingStore(),
5278 ST->getMemOperand());
5279 CSEMap.InsertNode(N, IP);
5281 return SDValue(N, 0);
5285 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5286 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5287 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5289 SDVTList VTs = getVTList(VT, MVT::Other);
5290 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5291 FoldingSetNodeID ID;
5292 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5293 ID.AddInteger(VT.getRawBits());
5294 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5296 MMO->isNonTemporal(),
5297 MMO->isInvariant()));
5298 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5300 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5301 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5302 return SDValue(E, 0);
5304 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5305 dl.getDebugLoc(), Ops, 4, VTs,
5307 CSEMap.InsertNode(N, IP);
5309 return SDValue(N, 0);
5312 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5313 SDValue Ptr, SDValue Mask, EVT MemVT,
5314 MachineMemOperand *MMO, bool isTrunc) {
5315 assert(Chain.getValueType() == MVT::Other &&
5316 "Invalid chain type");
5317 EVT VT = Val.getValueType();
5318 SDVTList VTs = getVTList(MVT::Other);
5319 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5320 FoldingSetNodeID ID;
5321 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5322 ID.AddInteger(VT.getRawBits());
5323 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5324 MMO->isNonTemporal(), MMO->isInvariant()));
5325 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5327 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5328 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5329 return SDValue(E, 0);
5331 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5332 dl.getDebugLoc(), Ops, 4,
5333 VTs, isTrunc, MemVT, MMO);
5334 CSEMap.InsertNode(N, IP);
5336 return SDValue(N, 0);
5340 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5341 ArrayRef<SDValue> Ops,
5342 MachineMemOperand *MMO) {
5344 FoldingSetNodeID ID;
5345 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5346 ID.AddInteger(VT.getRawBits());
5347 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5349 MMO->isNonTemporal(),
5350 MMO->isInvariant()));
5351 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5353 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5354 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5355 return SDValue(E, 0);
5357 MaskedGatherSDNode *N =
5358 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5360 CSEMap.InsertNode(N, IP);
5362 return SDValue(N, 0);
5365 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5366 ArrayRef<SDValue> Ops,
5367 MachineMemOperand *MMO) {
5368 FoldingSetNodeID ID;
5369 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5370 ID.AddInteger(VT.getRawBits());
5371 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5372 MMO->isNonTemporal(),
5373 MMO->isInvariant()));
5374 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5376 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5377 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5378 return SDValue(E, 0);
5381 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5383 CSEMap.InsertNode(N, IP);
5385 return SDValue(N, 0);
5388 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5389 SDValue Chain, SDValue Ptr,
5392 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5393 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5396 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5397 ArrayRef<SDUse> Ops) {
5398 switch (Ops.size()) {
5399 case 0: return getNode(Opcode, DL, VT);
5400 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5401 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5402 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5406 // Copy from an SDUse array into an SDValue array for use with
5407 // the regular getNode logic.
5408 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5409 return getNode(Opcode, DL, VT, NewOps);
5412 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5413 ArrayRef<SDValue> Ops, const SDNodeFlags *Flags) {
5414 unsigned NumOps = Ops.size();
5416 case 0: return getNode(Opcode, DL, VT);
5417 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5418 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Flags);
5419 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5425 case ISD::SELECT_CC: {
5426 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5427 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5428 "LHS and RHS of condition must have same type!");
5429 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5430 "True and False arms of SelectCC must have same type!");
5431 assert(Ops[2].getValueType() == VT &&
5432 "select_cc node must be of same type as true and false value!");
5436 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5437 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5438 "LHS/RHS of comparison should match types!");
5445 SDVTList VTs = getVTList(VT);
5447 if (VT != MVT::Glue) {
5448 FoldingSetNodeID ID;
5449 AddNodeIDNode(ID, Opcode, VTs, Ops);
5452 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5453 return SDValue(E, 0);
5455 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5457 CSEMap.InsertNode(N, IP);
5459 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5464 return SDValue(N, 0);
5467 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5468 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5469 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5472 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5473 ArrayRef<SDValue> Ops) {
5474 if (VTList.NumVTs == 1)
5475 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5479 // FIXME: figure out how to safely handle things like
5480 // int foo(int x) { return 1 << (x & 255); }
5481 // int bar() { return foo(256); }
5482 case ISD::SRA_PARTS:
5483 case ISD::SRL_PARTS:
5484 case ISD::SHL_PARTS:
5485 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5486 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5487 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5488 else if (N3.getOpcode() == ISD::AND)
5489 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5490 // If the and is only masking out bits that cannot effect the shift,
5491 // eliminate the and.
5492 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5493 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5494 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5500 // Memoize the node unless it returns a flag.
5502 unsigned NumOps = Ops.size();
5503 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5504 FoldingSetNodeID ID;
5505 AddNodeIDNode(ID, Opcode, VTList, Ops);
5507 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5508 return SDValue(E, 0);
5511 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5512 DL.getDebugLoc(), VTList, Ops[0]);
5513 } else if (NumOps == 2) {
5514 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5515 DL.getDebugLoc(), VTList, Ops[0],
5517 } else if (NumOps == 3) {
5518 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5519 DL.getDebugLoc(), VTList, Ops[0],
5522 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5525 CSEMap.InsertNode(N, IP);
5528 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5529 DL.getDebugLoc(), VTList, Ops[0]);
5530 } else if (NumOps == 2) {
5531 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5532 DL.getDebugLoc(), VTList, Ops[0],
5534 } else if (NumOps == 3) {
5535 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5536 DL.getDebugLoc(), VTList, Ops[0],
5539 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5544 return SDValue(N, 0);
5547 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5548 return getNode(Opcode, DL, VTList, None);
5551 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5553 SDValue Ops[] = { N1 };
5554 return getNode(Opcode, DL, VTList, Ops);
5557 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5558 SDValue N1, SDValue N2) {
5559 SDValue Ops[] = { N1, N2 };
5560 return getNode(Opcode, DL, VTList, Ops);
5563 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5564 SDValue N1, SDValue N2, SDValue N3) {
5565 SDValue Ops[] = { N1, N2, N3 };
5566 return getNode(Opcode, DL, VTList, Ops);
5569 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5570 SDValue N1, SDValue N2, SDValue N3,
5572 SDValue Ops[] = { N1, N2, N3, N4 };
5573 return getNode(Opcode, DL, VTList, Ops);
5576 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5577 SDValue N1, SDValue N2, SDValue N3,
5578 SDValue N4, SDValue N5) {
5579 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5580 return getNode(Opcode, DL, VTList, Ops);
5583 SDVTList SelectionDAG::getVTList(EVT VT) {
5584 return makeVTList(SDNode::getValueTypeList(VT), 1);
5587 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5588 FoldingSetNodeID ID;
5590 ID.AddInteger(VT1.getRawBits());
5591 ID.AddInteger(VT2.getRawBits());
5594 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5596 EVT *Array = Allocator.Allocate<EVT>(2);
5599 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5600 VTListMap.InsertNode(Result, IP);
5602 return Result->getSDVTList();
5605 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5606 FoldingSetNodeID ID;
5608 ID.AddInteger(VT1.getRawBits());
5609 ID.AddInteger(VT2.getRawBits());
5610 ID.AddInteger(VT3.getRawBits());
5613 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5615 EVT *Array = Allocator.Allocate<EVT>(3);
5619 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5620 VTListMap.InsertNode(Result, IP);
5622 return Result->getSDVTList();
5625 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5626 FoldingSetNodeID ID;
5628 ID.AddInteger(VT1.getRawBits());
5629 ID.AddInteger(VT2.getRawBits());
5630 ID.AddInteger(VT3.getRawBits());
5631 ID.AddInteger(VT4.getRawBits());
5634 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5636 EVT *Array = Allocator.Allocate<EVT>(4);
5641 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5642 VTListMap.InsertNode(Result, IP);
5644 return Result->getSDVTList();
5647 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5648 unsigned NumVTs = VTs.size();
5649 FoldingSetNodeID ID;
5650 ID.AddInteger(NumVTs);
5651 for (unsigned index = 0; index < NumVTs; index++) {
5652 ID.AddInteger(VTs[index].getRawBits());
5656 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5658 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5659 std::copy(VTs.begin(), VTs.end(), Array);
5660 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5661 VTListMap.InsertNode(Result, IP);
5663 return Result->getSDVTList();
5667 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5668 /// specified operands. If the resultant node already exists in the DAG,
5669 /// this does not modify the specified node, instead it returns the node that
5670 /// already exists. If the resultant node does not exist in the DAG, the
5671 /// input node is returned. As a degenerate case, if you specify the same
5672 /// input operands as the node already has, the input node is returned.
5673 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5674 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5676 // Check to see if there is no change.
5677 if (Op == N->getOperand(0)) return N;
5679 // See if the modified node already exists.
5680 void *InsertPos = nullptr;
5681 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5684 // Nope it doesn't. Remove the node from its current place in the maps.
5686 if (!RemoveNodeFromCSEMaps(N))
5687 InsertPos = nullptr;
5689 // Now we update the operands.
5690 N->OperandList[0].set(Op);
5692 // If this gets put into a CSE map, add it.
5693 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5697 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5698 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5700 // Check to see if there is no change.
5701 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5702 return N; // No operands changed, just return the input node.
5704 // See if the modified node already exists.
5705 void *InsertPos = nullptr;
5706 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5709 // Nope it doesn't. Remove the node from its current place in the maps.
5711 if (!RemoveNodeFromCSEMaps(N))
5712 InsertPos = nullptr;
5714 // Now we update the operands.
5715 if (N->OperandList[0] != Op1)
5716 N->OperandList[0].set(Op1);
5717 if (N->OperandList[1] != Op2)
5718 N->OperandList[1].set(Op2);
5720 // If this gets put into a CSE map, add it.
5721 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5725 SDNode *SelectionDAG::
5726 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5727 SDValue Ops[] = { Op1, Op2, Op3 };
5728 return UpdateNodeOperands(N, Ops);
5731 SDNode *SelectionDAG::
5732 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5733 SDValue Op3, SDValue Op4) {
5734 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5735 return UpdateNodeOperands(N, Ops);
5738 SDNode *SelectionDAG::
5739 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5740 SDValue Op3, SDValue Op4, SDValue Op5) {
5741 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5742 return UpdateNodeOperands(N, Ops);
5745 SDNode *SelectionDAG::
5746 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5747 unsigned NumOps = Ops.size();
5748 assert(N->getNumOperands() == NumOps &&
5749 "Update with wrong number of operands");
5751 // If no operands changed just return the input node.
5752 if (std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5755 // See if the modified node already exists.
5756 void *InsertPos = nullptr;
5757 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5760 // Nope it doesn't. Remove the node from its current place in the maps.
5762 if (!RemoveNodeFromCSEMaps(N))
5763 InsertPos = nullptr;
5765 // Now we update the operands.
5766 for (unsigned i = 0; i != NumOps; ++i)
5767 if (N->OperandList[i] != Ops[i])
5768 N->OperandList[i].set(Ops[i]);
5770 // If this gets put into a CSE map, add it.
5771 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5775 /// DropOperands - Release the operands and set this node to have
5777 void SDNode::DropOperands() {
5778 // Unlike the code in MorphNodeTo that does this, we don't need to
5779 // watch for dead nodes here.
5780 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5786 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5789 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5791 SDVTList VTs = getVTList(VT);
5792 return SelectNodeTo(N, MachineOpc, VTs, None);
5795 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5796 EVT VT, SDValue Op1) {
5797 SDVTList VTs = getVTList(VT);
5798 SDValue Ops[] = { Op1 };
5799 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5802 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5803 EVT VT, SDValue Op1,
5805 SDVTList VTs = getVTList(VT);
5806 SDValue Ops[] = { Op1, Op2 };
5807 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5810 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5811 EVT VT, SDValue Op1,
5812 SDValue Op2, SDValue Op3) {
5813 SDVTList VTs = getVTList(VT);
5814 SDValue Ops[] = { Op1, Op2, Op3 };
5815 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5818 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5819 EVT VT, ArrayRef<SDValue> Ops) {
5820 SDVTList VTs = getVTList(VT);
5821 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5824 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5825 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5826 SDVTList VTs = getVTList(VT1, VT2);
5827 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5830 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5832 SDVTList VTs = getVTList(VT1, VT2);
5833 return SelectNodeTo(N, MachineOpc, VTs, None);
5836 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5837 EVT VT1, EVT VT2, EVT VT3,
5838 ArrayRef<SDValue> Ops) {
5839 SDVTList VTs = getVTList(VT1, VT2, VT3);
5840 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5843 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5844 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5845 ArrayRef<SDValue> Ops) {
5846 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5847 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5850 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5853 SDVTList VTs = getVTList(VT1, VT2);
5854 SDValue Ops[] = { Op1 };
5855 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5858 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5860 SDValue Op1, SDValue Op2) {
5861 SDVTList VTs = getVTList(VT1, VT2);
5862 SDValue Ops[] = { Op1, Op2 };
5863 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5866 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5868 SDValue Op1, SDValue Op2,
5870 SDVTList VTs = getVTList(VT1, VT2);
5871 SDValue Ops[] = { Op1, Op2, Op3 };
5872 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5875 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5876 EVT VT1, EVT VT2, EVT VT3,
5877 SDValue Op1, SDValue Op2,
5879 SDVTList VTs = getVTList(VT1, VT2, VT3);
5880 SDValue Ops[] = { Op1, Op2, Op3 };
5881 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5884 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5885 SDVTList VTs,ArrayRef<SDValue> Ops) {
5886 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5887 // Reset the NodeID to -1.
5892 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5893 /// the line number information on the merged node since it is not possible to
5894 /// preserve the information that operation is associated with multiple lines.
5895 /// This will make the debugger working better at -O0, were there is a higher
5896 /// probability having other instructions associated with that line.
5898 /// For IROrder, we keep the smaller of the two
5899 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5900 DebugLoc NLoc = N->getDebugLoc();
5901 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5902 N->setDebugLoc(DebugLoc());
5904 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5905 N->setIROrder(Order);
5909 /// MorphNodeTo - This *mutates* the specified node to have the specified
5910 /// return type, opcode, and operands.
5912 /// Note that MorphNodeTo returns the resultant node. If there is already a
5913 /// node of the specified opcode and operands, it returns that node instead of
5914 /// the current one. Note that the SDLoc need not be the same.
5916 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5917 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5918 /// node, and because it doesn't require CSE recalculation for any of
5919 /// the node's users.
5921 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5922 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5923 /// the legalizer which maintain worklists that would need to be updated when
5924 /// deleting things.
5925 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5926 SDVTList VTs, ArrayRef<SDValue> Ops) {
5927 unsigned NumOps = Ops.size();
5928 // If an identical node already exists, use it.
5930 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5931 FoldingSetNodeID ID;
5932 AddNodeIDNode(ID, Opc, VTs, Ops);
5933 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5934 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5937 if (!RemoveNodeFromCSEMaps(N))
5940 // Start the morphing.
5942 N->ValueList = VTs.VTs;
5943 N->NumValues = VTs.NumVTs;
5945 // Clear the operands list, updating used nodes to remove this from their
5946 // use list. Keep track of any operands that become dead as a result.
5947 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5948 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5950 SDNode *Used = Use.getNode();
5952 if (Used->use_empty())
5953 DeadNodeSet.insert(Used);
5956 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5957 // Initialize the memory references information.
5958 MN->setMemRefs(nullptr, nullptr);
5959 // If NumOps is larger than the # of operands we can have in a
5960 // MachineSDNode, reallocate the operand list.
5961 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5962 if (MN->OperandsNeedDelete)
5963 delete[] MN->OperandList;
5964 if (NumOps > array_lengthof(MN->LocalOperands))
5965 // We're creating a final node that will live unmorphed for the
5966 // remainder of the current SelectionDAG iteration, so we can allocate
5967 // the operands directly out of a pool with no recycling metadata.
5968 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5969 Ops.data(), NumOps);
5971 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5972 MN->OperandsNeedDelete = false;
5974 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5976 // If NumOps is larger than the # of operands we currently have, reallocate
5977 // the operand list.
5978 if (NumOps > N->NumOperands) {
5979 if (N->OperandsNeedDelete)
5980 delete[] N->OperandList;
5981 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5982 N->OperandsNeedDelete = true;
5984 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5987 // Delete any nodes that are still dead after adding the uses for the
5989 if (!DeadNodeSet.empty()) {
5990 SmallVector<SDNode *, 16> DeadNodes;
5991 for (SDNode *N : DeadNodeSet)
5993 DeadNodes.push_back(N);
5994 RemoveDeadNodes(DeadNodes);
5998 CSEMap.InsertNode(N, IP); // Memoize the new node.
6003 /// getMachineNode - These are used for target selectors to create a new node
6004 /// with specified return type(s), MachineInstr opcode, and operands.
6006 /// Note that getMachineNode returns the resultant node. If there is already a
6007 /// node of the specified opcode and operands, it returns that node instead of
6008 /// the current one.
6010 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
6011 SDVTList VTs = getVTList(VT);
6012 return getMachineNode(Opcode, dl, VTs, None);
6016 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
6017 SDVTList VTs = getVTList(VT);
6018 SDValue Ops[] = { Op1 };
6019 return getMachineNode(Opcode, dl, VTs, Ops);
6023 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6024 SDValue Op1, SDValue Op2) {
6025 SDVTList VTs = getVTList(VT);
6026 SDValue Ops[] = { Op1, Op2 };
6027 return getMachineNode(Opcode, dl, VTs, Ops);
6031 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6032 SDValue Op1, SDValue Op2, SDValue Op3) {
6033 SDVTList VTs = getVTList(VT);
6034 SDValue Ops[] = { Op1, Op2, Op3 };
6035 return getMachineNode(Opcode, dl, VTs, Ops);
6039 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
6040 ArrayRef<SDValue> Ops) {
6041 SDVTList VTs = getVTList(VT);
6042 return getMachineNode(Opcode, dl, VTs, Ops);
6046 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
6047 SDVTList VTs = getVTList(VT1, VT2);
6048 return getMachineNode(Opcode, dl, VTs, None);
6052 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6053 EVT VT1, EVT VT2, SDValue Op1) {
6054 SDVTList VTs = getVTList(VT1, VT2);
6055 SDValue Ops[] = { Op1 };
6056 return getMachineNode(Opcode, dl, VTs, Ops);
6060 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6061 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
6062 SDVTList VTs = getVTList(VT1, VT2);
6063 SDValue Ops[] = { Op1, Op2 };
6064 return getMachineNode(Opcode, dl, VTs, Ops);
6068 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6069 EVT VT1, EVT VT2, SDValue Op1,
6070 SDValue Op2, SDValue Op3) {
6071 SDVTList VTs = getVTList(VT1, VT2);
6072 SDValue Ops[] = { Op1, Op2, Op3 };
6073 return getMachineNode(Opcode, dl, VTs, Ops);
6077 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6079 ArrayRef<SDValue> Ops) {
6080 SDVTList VTs = getVTList(VT1, VT2);
6081 return getMachineNode(Opcode, dl, VTs, Ops);
6085 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6086 EVT VT1, EVT VT2, EVT VT3,
6087 SDValue Op1, SDValue Op2) {
6088 SDVTList VTs = getVTList(VT1, VT2, VT3);
6089 SDValue Ops[] = { Op1, Op2 };
6090 return getMachineNode(Opcode, dl, VTs, Ops);
6094 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6095 EVT VT1, EVT VT2, EVT VT3,
6096 SDValue Op1, SDValue Op2, SDValue Op3) {
6097 SDVTList VTs = getVTList(VT1, VT2, VT3);
6098 SDValue Ops[] = { Op1, Op2, Op3 };
6099 return getMachineNode(Opcode, dl, VTs, Ops);
6103 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6104 EVT VT1, EVT VT2, EVT VT3,
6105 ArrayRef<SDValue> Ops) {
6106 SDVTList VTs = getVTList(VT1, VT2, VT3);
6107 return getMachineNode(Opcode, dl, VTs, Ops);
6111 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6112 EVT VT2, EVT VT3, EVT VT4,
6113 ArrayRef<SDValue> Ops) {
6114 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6115 return getMachineNode(Opcode, dl, VTs, Ops);
6119 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6120 ArrayRef<EVT> ResultTys,
6121 ArrayRef<SDValue> Ops) {
6122 SDVTList VTs = getVTList(ResultTys);
6123 return getMachineNode(Opcode, dl, VTs, Ops);
6127 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6128 ArrayRef<SDValue> OpsArray) {
6129 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6132 const SDValue *Ops = OpsArray.data();
6133 unsigned NumOps = OpsArray.size();
6136 FoldingSetNodeID ID;
6137 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6139 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6140 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6144 // Allocate a new MachineSDNode.
6145 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6146 DL.getDebugLoc(), VTs);
6148 // Initialize the operands list.
6149 if (NumOps > array_lengthof(N->LocalOperands))
6150 // We're creating a final node that will live unmorphed for the
6151 // remainder of the current SelectionDAG iteration, so we can allocate
6152 // the operands directly out of a pool with no recycling metadata.
6153 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6156 N->InitOperands(N->LocalOperands, Ops, NumOps);
6157 N->OperandsNeedDelete = false;
6160 CSEMap.InsertNode(N, IP);
6166 /// getTargetExtractSubreg - A convenience function for creating
6167 /// TargetOpcode::EXTRACT_SUBREG nodes.
6169 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6171 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6172 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6173 VT, Operand, SRIdxVal);
6174 return SDValue(Subreg, 0);
6177 /// getTargetInsertSubreg - A convenience function for creating
6178 /// TargetOpcode::INSERT_SUBREG nodes.
6180 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6181 SDValue Operand, SDValue Subreg) {
6182 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6183 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6184 VT, Operand, Subreg, SRIdxVal);
6185 return SDValue(Result, 0);
6188 /// getNodeIfExists - Get the specified node if it's already available, or
6189 /// else return NULL.
6190 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6191 ArrayRef<SDValue> Ops,
6192 const SDNodeFlags *Flags) {
6193 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6194 FoldingSetNodeID ID;
6195 AddNodeIDNode(ID, Opcode, VTList, Ops);
6196 AddNodeIDFlags(ID, Opcode, Flags);
6198 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6204 /// getDbgValue - Creates a SDDbgValue node.
6207 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6208 unsigned R, bool IsIndirect, uint64_t Off,
6209 DebugLoc DL, unsigned O) {
6210 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6211 "Expected inlined-at fields to agree");
6212 return new (DbgInfo->getAlloc())
6213 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6217 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6218 const Value *C, uint64_t Off,
6219 DebugLoc DL, unsigned O) {
6220 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6221 "Expected inlined-at fields to agree");
6222 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6226 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6227 unsigned FI, uint64_t Off,
6228 DebugLoc DL, unsigned O) {
6229 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6230 "Expected inlined-at fields to agree");
6231 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6236 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6237 /// pointed to by a use iterator is deleted, increment the use iterator
6238 /// so that it doesn't dangle.
6240 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6241 SDNode::use_iterator &UI;
6242 SDNode::use_iterator &UE;
6244 void NodeDeleted(SDNode *N, SDNode *E) override {
6245 // Increment the iterator as needed.
6246 while (UI != UE && N == *UI)
6251 RAUWUpdateListener(SelectionDAG &d,
6252 SDNode::use_iterator &ui,
6253 SDNode::use_iterator &ue)
6254 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6259 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6260 /// This can cause recursive merging of nodes in the DAG.
6262 /// This version assumes From has a single result value.
6264 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6265 SDNode *From = FromN.getNode();
6266 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6267 "Cannot replace with this method!");
6268 assert(From != To.getNode() && "Cannot replace uses of with self");
6270 // Iterate over all the existing uses of From. New uses will be added
6271 // to the beginning of the use list, which we avoid visiting.
6272 // This specifically avoids visiting uses of From that arise while the
6273 // replacement is happening, because any such uses would be the result
6274 // of CSE: If an existing node looks like From after one of its operands
6275 // is replaced by To, we don't want to replace of all its users with To
6276 // too. See PR3018 for more info.
6277 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6278 RAUWUpdateListener Listener(*this, UI, UE);
6282 // This node is about to morph, remove its old self from the CSE maps.
6283 RemoveNodeFromCSEMaps(User);
6285 // A user can appear in a use list multiple times, and when this
6286 // happens the uses are usually next to each other in the list.
6287 // To help reduce the number of CSE recomputations, process all
6288 // the uses of this user that we can find this way.
6290 SDUse &Use = UI.getUse();
6293 } while (UI != UE && *UI == User);
6295 // Now that we have modified User, add it back to the CSE maps. If it
6296 // already exists there, recursively merge the results together.
6297 AddModifiedNodeToCSEMaps(User);
6300 // If we just RAUW'd the root, take note.
6301 if (FromN == getRoot())
6305 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6306 /// This can cause recursive merging of nodes in the DAG.
6308 /// This version assumes that for each value of From, there is a
6309 /// corresponding value in To in the same position with the same type.
6311 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6313 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6314 assert((!From->hasAnyUseOfValue(i) ||
6315 From->getValueType(i) == To->getValueType(i)) &&
6316 "Cannot use this version of ReplaceAllUsesWith!");
6319 // Handle the trivial case.
6323 // Iterate over just the existing users of From. See the comments in
6324 // the ReplaceAllUsesWith above.
6325 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6326 RAUWUpdateListener Listener(*this, UI, UE);
6330 // This node is about to morph, remove its old self from the CSE maps.
6331 RemoveNodeFromCSEMaps(User);
6333 // A user can appear in a use list multiple times, and when this
6334 // happens the uses are usually next to each other in the list.
6335 // To help reduce the number of CSE recomputations, process all
6336 // the uses of this user that we can find this way.
6338 SDUse &Use = UI.getUse();
6341 } while (UI != UE && *UI == User);
6343 // Now that we have modified User, add it back to the CSE maps. If it
6344 // already exists there, recursively merge the results together.
6345 AddModifiedNodeToCSEMaps(User);
6348 // If we just RAUW'd the root, take note.
6349 if (From == getRoot().getNode())
6350 setRoot(SDValue(To, getRoot().getResNo()));
6353 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6354 /// This can cause recursive merging of nodes in the DAG.
6356 /// This version can replace From with any result values. To must match the
6357 /// number and types of values returned by From.
6358 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6359 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6360 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6362 // Iterate over just the existing users of From. See the comments in
6363 // the ReplaceAllUsesWith above.
6364 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6365 RAUWUpdateListener Listener(*this, UI, UE);
6369 // This node is about to morph, remove its old self from the CSE maps.
6370 RemoveNodeFromCSEMaps(User);
6372 // A user can appear in a use list multiple times, and when this
6373 // happens the uses are usually next to each other in the list.
6374 // To help reduce the number of CSE recomputations, process all
6375 // the uses of this user that we can find this way.
6377 SDUse &Use = UI.getUse();
6378 const SDValue &ToOp = To[Use.getResNo()];
6381 } while (UI != UE && *UI == User);
6383 // Now that we have modified User, add it back to the CSE maps. If it
6384 // already exists there, recursively merge the results together.
6385 AddModifiedNodeToCSEMaps(User);
6388 // If we just RAUW'd the root, take note.
6389 if (From == getRoot().getNode())
6390 setRoot(SDValue(To[getRoot().getResNo()]));
6393 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6394 /// uses of other values produced by From.getNode() alone. The Deleted
6395 /// vector is handled the same way as for ReplaceAllUsesWith.
6396 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6397 // Handle the really simple, really trivial case efficiently.
6398 if (From == To) return;
6400 // Handle the simple, trivial, case efficiently.
6401 if (From.getNode()->getNumValues() == 1) {
6402 ReplaceAllUsesWith(From, To);
6406 // Iterate over just the existing users of From. See the comments in
6407 // the ReplaceAllUsesWith above.
6408 SDNode::use_iterator UI = From.getNode()->use_begin(),
6409 UE = From.getNode()->use_end();
6410 RAUWUpdateListener Listener(*this, UI, UE);
6413 bool UserRemovedFromCSEMaps = false;
6415 // A user can appear in a use list multiple times, and when this
6416 // happens the uses are usually next to each other in the list.
6417 // To help reduce the number of CSE recomputations, process all
6418 // the uses of this user that we can find this way.
6420 SDUse &Use = UI.getUse();
6422 // Skip uses of different values from the same node.
6423 if (Use.getResNo() != From.getResNo()) {
6428 // If this node hasn't been modified yet, it's still in the CSE maps,
6429 // so remove its old self from the CSE maps.
6430 if (!UserRemovedFromCSEMaps) {
6431 RemoveNodeFromCSEMaps(User);
6432 UserRemovedFromCSEMaps = true;
6437 } while (UI != UE && *UI == User);
6439 // We are iterating over all uses of the From node, so if a use
6440 // doesn't use the specific value, no changes are made.
6441 if (!UserRemovedFromCSEMaps)
6444 // Now that we have modified User, add it back to the CSE maps. If it
6445 // already exists there, recursively merge the results together.
6446 AddModifiedNodeToCSEMaps(User);
6449 // If we just RAUW'd the root, take note.
6450 if (From == getRoot())
6455 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6456 /// to record information about a use.
6463 /// operator< - Sort Memos by User.
6464 bool operator<(const UseMemo &L, const UseMemo &R) {
6465 return (intptr_t)L.User < (intptr_t)R.User;
6469 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6470 /// uses of other values produced by From.getNode() alone. The same value
6471 /// may appear in both the From and To list. The Deleted vector is
6472 /// handled the same way as for ReplaceAllUsesWith.
6473 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6476 // Handle the simple, trivial case efficiently.
6478 return ReplaceAllUsesOfValueWith(*From, *To);
6480 // Read up all the uses and make records of them. This helps
6481 // processing new uses that are introduced during the
6482 // replacement process.
6483 SmallVector<UseMemo, 4> Uses;
6484 for (unsigned i = 0; i != Num; ++i) {
6485 unsigned FromResNo = From[i].getResNo();
6486 SDNode *FromNode = From[i].getNode();
6487 for (SDNode::use_iterator UI = FromNode->use_begin(),
6488 E = FromNode->use_end(); UI != E; ++UI) {
6489 SDUse &Use = UI.getUse();
6490 if (Use.getResNo() == FromResNo) {
6491 UseMemo Memo = { *UI, i, &Use };
6492 Uses.push_back(Memo);
6497 // Sort the uses, so that all the uses from a given User are together.
6498 std::sort(Uses.begin(), Uses.end());
6500 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6501 UseIndex != UseIndexEnd; ) {
6502 // We know that this user uses some value of From. If it is the right
6503 // value, update it.
6504 SDNode *User = Uses[UseIndex].User;
6506 // This node is about to morph, remove its old self from the CSE maps.
6507 RemoveNodeFromCSEMaps(User);
6509 // The Uses array is sorted, so all the uses for a given User
6510 // are next to each other in the list.
6511 // To help reduce the number of CSE recomputations, process all
6512 // the uses of this user that we can find this way.
6514 unsigned i = Uses[UseIndex].Index;
6515 SDUse &Use = *Uses[UseIndex].Use;
6519 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6521 // Now that we have modified User, add it back to the CSE maps. If it
6522 // already exists there, recursively merge the results together.
6523 AddModifiedNodeToCSEMaps(User);
6527 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6528 /// based on their topological order. It returns the maximum id and a vector
6529 /// of the SDNodes* in assigned order by reference.
6530 unsigned SelectionDAG::AssignTopologicalOrder() {
6532 unsigned DAGSize = 0;
6534 // SortedPos tracks the progress of the algorithm. Nodes before it are
6535 // sorted, nodes after it are unsorted. When the algorithm completes
6536 // it is at the end of the list.
6537 allnodes_iterator SortedPos = allnodes_begin();
6539 // Visit all the nodes. Move nodes with no operands to the front of
6540 // the list immediately. Annotate nodes that do have operands with their
6541 // operand count. Before we do this, the Node Id fields of the nodes
6542 // may contain arbitrary values. After, the Node Id fields for nodes
6543 // before SortedPos will contain the topological sort index, and the
6544 // Node Id fields for nodes At SortedPos and after will contain the
6545 // count of outstanding operands.
6546 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6548 checkForCycles(N, this);
6549 unsigned Degree = N->getNumOperands();
6551 // A node with no uses, add it to the result array immediately.
6552 N->setNodeId(DAGSize++);
6553 allnodes_iterator Q(N);
6555 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6556 assert(SortedPos != AllNodes.end() && "Overran node list");
6559 // Temporarily use the Node Id as scratch space for the degree count.
6560 N->setNodeId(Degree);
6564 // Visit all the nodes. As we iterate, move nodes into sorted order,
6565 // such that by the time the end is reached all nodes will be sorted.
6566 for (SDNode &Node : allnodes()) {
6568 checkForCycles(N, this);
6569 // N is in sorted position, so all its uses have one less operand
6570 // that needs to be sorted.
6571 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6574 unsigned Degree = P->getNodeId();
6575 assert(Degree != 0 && "Invalid node degree");
6578 // All of P's operands are sorted, so P may sorted now.
6579 P->setNodeId(DAGSize++);
6581 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6582 assert(SortedPos != AllNodes.end() && "Overran node list");
6585 // Update P's outstanding operand count.
6586 P->setNodeId(Degree);
6589 if (&Node == SortedPos) {
6591 allnodes_iterator I(N);
6593 dbgs() << "Overran sorted position:\n";
6594 S->dumprFull(this); dbgs() << "\n";
6595 dbgs() << "Checking if this is due to cycles\n";
6596 checkForCycles(this, true);
6598 llvm_unreachable(nullptr);
6602 assert(SortedPos == AllNodes.end() &&
6603 "Topological sort incomplete!");
6604 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6605 "First node in topological sort is not the entry token!");
6606 assert(AllNodes.front().getNodeId() == 0 &&
6607 "First node in topological sort has non-zero id!");
6608 assert(AllNodes.front().getNumOperands() == 0 &&
6609 "First node in topological sort has operands!");
6610 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6611 "Last node in topologic sort has unexpected id!");
6612 assert(AllNodes.back().use_empty() &&
6613 "Last node in topologic sort has users!");
6614 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6618 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6619 /// value is produced by SD.
6620 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6622 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6623 SD->setHasDebugValue(true);
6625 DbgInfo->add(DB, SD, isParameter);
6628 /// TransferDbgValues - Transfer SDDbgValues.
6629 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6630 if (From == To || !From.getNode()->getHasDebugValue())
6632 SDNode *FromNode = From.getNode();
6633 SDNode *ToNode = To.getNode();
6634 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6635 SmallVector<SDDbgValue *, 2> ClonedDVs;
6636 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6638 SDDbgValue *Dbg = *I;
6639 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6641 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6642 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6643 Dbg->getDebugLoc(), Dbg->getOrder());
6644 ClonedDVs.push_back(Clone);
6647 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6648 E = ClonedDVs.end(); I != E; ++I)
6649 AddDbgValue(*I, ToNode, false);
6652 //===----------------------------------------------------------------------===//
6654 //===----------------------------------------------------------------------===//
6656 HandleSDNode::~HandleSDNode() {
6660 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6661 DebugLoc DL, const GlobalValue *GA,
6662 EVT VT, int64_t o, unsigned char TF)
6663 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6667 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6668 SDValue X, unsigned SrcAS,
6670 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6671 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6673 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6674 EVT memvt, MachineMemOperand *mmo)
6675 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6676 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6677 MMO->isNonTemporal(), MMO->isInvariant());
6678 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6679 assert(isNonTemporal() == MMO->isNonTemporal() &&
6680 "Non-temporal encoding error!");
6681 // We check here that the size of the memory operand fits within the size of
6682 // the MMO. This is because the MMO might indicate only a possible address
6683 // range instead of specifying the affected memory addresses precisely.
6684 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6687 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6688 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6689 : SDNode(Opc, Order, dl, VTs, Ops),
6690 MemoryVT(memvt), MMO(mmo) {
6691 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6692 MMO->isNonTemporal(), MMO->isInvariant());
6693 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6694 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6697 /// Profile - Gather unique data for the node.
6699 void SDNode::Profile(FoldingSetNodeID &ID) const {
6700 AddNodeIDNode(ID, this);
6705 std::vector<EVT> VTs;
6708 VTs.reserve(MVT::LAST_VALUETYPE);
6709 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6710 VTs.push_back(MVT((MVT::SimpleValueType)i));
6715 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6716 static ManagedStatic<EVTArray> SimpleVTArray;
6717 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6719 /// getValueTypeList - Return a pointer to the specified value type.
6721 const EVT *SDNode::getValueTypeList(EVT VT) {
6722 if (VT.isExtended()) {
6723 sys::SmartScopedLock<true> Lock(*VTMutex);
6724 return &(*EVTs->insert(VT).first);
6726 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6727 "Value type out of range!");
6728 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6732 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6733 /// indicated value. This method ignores uses of other values defined by this
6735 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6736 assert(Value < getNumValues() && "Bad value!");
6738 // TODO: Only iterate over uses of a given value of the node
6739 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6740 if (UI.getUse().getResNo() == Value) {
6747 // Found exactly the right number of uses?
6752 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6753 /// value. This method ignores uses of other values defined by this operation.
6754 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6755 assert(Value < getNumValues() && "Bad value!");
6757 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6758 if (UI.getUse().getResNo() == Value)
6765 /// isOnlyUserOf - Return true if this node is the only use of N.
6767 bool SDNode::isOnlyUserOf(const SDNode *N) const {
6769 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6780 /// isOperand - Return true if this node is an operand of N.
6782 bool SDValue::isOperandOf(const SDNode *N) const {
6783 for (const SDValue &Op : N->op_values())
6789 bool SDNode::isOperandOf(const SDNode *N) const {
6790 for (const SDValue &Op : N->op_values())
6791 if (this == Op.getNode())
6796 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6797 /// be a chain) reaches the specified operand without crossing any
6798 /// side-effecting instructions on any chain path. In practice, this looks
6799 /// through token factors and non-volatile loads. In order to remain efficient,
6800 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6801 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6802 unsigned Depth) const {
6803 if (*this == Dest) return true;
6805 // Don't search too deeply, we just want to be able to see through
6806 // TokenFactor's etc.
6807 if (Depth == 0) return false;
6809 // If this is a token factor, all inputs to the TF happen in parallel. If any
6810 // of the operands of the TF does not reach dest, then we cannot do the xform.
6811 if (getOpcode() == ISD::TokenFactor) {
6812 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6813 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6818 // Loads don't have side effects, look through them.
6819 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6820 if (!Ld->isVolatile())
6821 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6826 /// hasPredecessor - Return true if N is a predecessor of this node.
6827 /// N is either an operand of this node, or can be reached by recursively
6828 /// traversing up the operands.
6829 /// NOTE: This is an expensive method. Use it carefully.
6830 bool SDNode::hasPredecessor(const SDNode *N) const {
6831 SmallPtrSet<const SDNode *, 32> Visited;
6832 SmallVector<const SDNode *, 16> Worklist;
6833 return hasPredecessorHelper(N, Visited, Worklist);
6837 SDNode::hasPredecessorHelper(const SDNode *N,
6838 SmallPtrSetImpl<const SDNode *> &Visited,
6839 SmallVectorImpl<const SDNode *> &Worklist) const {
6840 if (Visited.empty()) {
6841 Worklist.push_back(this);
6843 // Take a look in the visited set. If we've already encountered this node
6844 // we needn't search further.
6845 if (Visited.count(N))
6849 // Haven't visited N yet. Continue the search.
6850 while (!Worklist.empty()) {
6851 const SDNode *M = Worklist.pop_back_val();
6852 for (const SDValue &OpV : M->op_values()) {
6853 SDNode *Op = OpV.getNode();
6854 if (Visited.insert(Op).second)
6855 Worklist.push_back(Op);
6864 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6865 assert(Num < NumOperands && "Invalid child # of SDNode!");
6866 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6869 const SDNodeFlags *SDNode::getFlags() const {
6870 if (auto *FlagsNode = dyn_cast<BinaryWithFlagsSDNode>(this))
6871 return &FlagsNode->Flags;
6875 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6876 assert(N->getNumValues() == 1 &&
6877 "Can't unroll a vector with multiple results!");
6879 EVT VT = N->getValueType(0);
6880 unsigned NE = VT.getVectorNumElements();
6881 EVT EltVT = VT.getVectorElementType();
6884 SmallVector<SDValue, 8> Scalars;
6885 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6887 // If ResNE is 0, fully unroll the vector op.
6890 else if (NE > ResNE)
6894 for (i= 0; i != NE; ++i) {
6895 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6896 SDValue Operand = N->getOperand(j);
6897 EVT OperandVT = Operand.getValueType();
6898 if (OperandVT.isVector()) {
6899 // A vector operand; extract a single element.
6900 EVT OperandEltVT = OperandVT.getVectorElementType();
6902 getNode(ISD::EXTRACT_VECTOR_ELT, dl, OperandEltVT, Operand,
6903 getConstant(i, dl, TLI->getVectorIdxTy(getDataLayout())));
6905 // A scalar operand; just use it as is.
6906 Operands[j] = Operand;
6910 switch (N->getOpcode()) {
6912 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands,
6917 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6924 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6925 getShiftAmountOperand(Operands[0].getValueType(),
6928 case ISD::SIGN_EXTEND_INREG:
6929 case ISD::FP_ROUND_INREG: {
6930 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6931 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6933 getValueType(ExtVT)));
6938 for (; i < ResNE; ++i)
6939 Scalars.push_back(getUNDEF(EltVT));
6941 return getNode(ISD::BUILD_VECTOR, dl,
6942 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6946 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6947 /// location that is 'Dist' units away from the location that the 'Base' load
6948 /// is loading from.
6949 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6950 unsigned Bytes, int Dist) const {
6951 if (LD->getChain() != Base->getChain())
6953 EVT VT = LD->getValueType(0);
6954 if (VT.getSizeInBits() / 8 != Bytes)
6957 SDValue Loc = LD->getOperand(1);
6958 SDValue BaseLoc = Base->getOperand(1);
6959 if (Loc.getOpcode() == ISD::FrameIndex) {
6960 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6962 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6963 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6964 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6965 int FS = MFI->getObjectSize(FI);
6966 int BFS = MFI->getObjectSize(BFI);
6967 if (FS != BFS || FS != (int)Bytes) return false;
6968 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6972 if (isBaseWithConstantOffset(Loc)) {
6973 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6974 if (Loc.getOperand(0) == BaseLoc) {
6975 // If the base location is a simple address with no offset itself, then
6976 // the second load's first add operand should be the base address.
6977 if (LocOffset == Dist * (int)Bytes)
6979 } else if (isBaseWithConstantOffset(BaseLoc)) {
6980 // The base location itself has an offset, so subtract that value from the
6981 // second load's offset before comparing to distance * size.
6983 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6984 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6985 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6990 const GlobalValue *GV1 = nullptr;
6991 const GlobalValue *GV2 = nullptr;
6992 int64_t Offset1 = 0;
6993 int64_t Offset2 = 0;
6994 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6995 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6996 if (isGA1 && isGA2 && GV1 == GV2)
6997 return Offset1 == (Offset2 + Dist*Bytes);
7002 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
7003 /// it cannot be inferred.
7004 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
7005 // If this is a GlobalAddress + cst, return the alignment.
7006 const GlobalValue *GV;
7007 int64_t GVOffset = 0;
7008 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
7009 unsigned PtrWidth = getDataLayout().getPointerTypeSizeInBits(GV->getType());
7010 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
7011 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
7013 unsigned AlignBits = KnownZero.countTrailingOnes();
7014 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
7016 return MinAlign(Align, GVOffset);
7019 // If this is a direct reference to a stack slot, use information about the
7020 // stack slot's alignment.
7021 int FrameIdx = 1 << 31;
7022 int64_t FrameOffset = 0;
7023 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
7024 FrameIdx = FI->getIndex();
7025 } else if (isBaseWithConstantOffset(Ptr) &&
7026 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
7028 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
7029 FrameOffset = Ptr.getConstantOperandVal(1);
7032 if (FrameIdx != (1 << 31)) {
7033 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
7034 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
7042 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
7043 /// which is split (or expanded) into two not necessarily identical pieces.
7044 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
7045 // Currently all types are split in half.
7047 if (!VT.isVector()) {
7048 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
7050 unsigned NumElements = VT.getVectorNumElements();
7051 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
7052 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
7055 return std::make_pair(LoVT, HiVT);
7058 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
7060 std::pair<SDValue, SDValue>
7061 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
7063 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
7064 N.getValueType().getVectorNumElements() &&
7065 "More vector elements requested than available!");
7067 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
7068 getConstant(0, DL, TLI->getVectorIdxTy(getDataLayout())));
7069 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
7070 getConstant(LoVT.getVectorNumElements(), DL,
7071 TLI->getVectorIdxTy(getDataLayout())));
7072 return std::make_pair(Lo, Hi);
7075 void SelectionDAG::ExtractVectorElements(SDValue Op,
7076 SmallVectorImpl<SDValue> &Args,
7077 unsigned Start, unsigned Count) {
7078 EVT VT = Op.getValueType();
7080 Count = VT.getVectorNumElements();
7082 EVT EltVT = VT.getVectorElementType();
7083 EVT IdxTy = TLI->getVectorIdxTy(getDataLayout());
7085 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
7086 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
7087 Op, getConstant(i, SL, IdxTy)));
7091 // getAddressSpace - Return the address space this GlobalAddress belongs to.
7092 unsigned GlobalAddressSDNode::getAddressSpace() const {
7093 return getGlobal()->getType()->getAddressSpace();
7097 Type *ConstantPoolSDNode::getType() const {
7098 if (isMachineConstantPoolEntry())
7099 return Val.MachineCPVal->getType();
7100 return Val.ConstVal->getType();
7103 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
7105 unsigned &SplatBitSize,
7107 unsigned MinSplatBits,
7108 bool isBigEndian) const {
7109 EVT VT = getValueType(0);
7110 assert(VT.isVector() && "Expected a vector type");
7111 unsigned sz = VT.getSizeInBits();
7112 if (MinSplatBits > sz)
7115 SplatValue = APInt(sz, 0);
7116 SplatUndef = APInt(sz, 0);
7118 // Get the bits. Bits with undefined values (when the corresponding element
7119 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7120 // in SplatValue. If any of the values are not constant, give up and return
7122 unsigned int nOps = getNumOperands();
7123 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7124 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7126 for (unsigned j = 0; j < nOps; ++j) {
7127 unsigned i = isBigEndian ? nOps-1-j : j;
7128 SDValue OpVal = getOperand(i);
7129 unsigned BitPos = j * EltBitSize;
7131 if (OpVal.getOpcode() == ISD::UNDEF)
7132 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7133 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7134 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7135 zextOrTrunc(sz) << BitPos;
7136 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7137 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7142 // The build_vector is all constants or undefs. Find the smallest element
7143 // size that splats the vector.
7145 HasAnyUndefs = (SplatUndef != 0);
7148 unsigned HalfSize = sz / 2;
7149 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7150 APInt LowValue = SplatValue.trunc(HalfSize);
7151 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7152 APInt LowUndef = SplatUndef.trunc(HalfSize);
7154 // If the two halves do not match (ignoring undef bits), stop here.
7155 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7156 MinSplatBits > HalfSize)
7159 SplatValue = HighValue | LowValue;
7160 SplatUndef = HighUndef & LowUndef;
7169 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7170 if (UndefElements) {
7171 UndefElements->clear();
7172 UndefElements->resize(getNumOperands());
7175 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7176 SDValue Op = getOperand(i);
7177 if (Op.getOpcode() == ISD::UNDEF) {
7179 (*UndefElements)[i] = true;
7180 } else if (!Splatted) {
7182 } else if (Splatted != Op) {
7188 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7189 "Can only have a splat without a constant for all undefs.");
7190 return getOperand(0);
7197 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7198 return dyn_cast_or_null<ConstantSDNode>(getSplatValue(UndefElements));
7202 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7203 return dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements));
7207 BuildVectorSDNode::getConstantFPSplatPow2ToLog2Int(BitVector *UndefElements,
7208 uint32_t BitWidth) const {
7209 if (ConstantFPSDNode *CN =
7210 dyn_cast_or_null<ConstantFPSDNode>(getSplatValue(UndefElements))) {
7212 APSInt IntVal(BitWidth);
7213 APFloat APF = CN->getValueAPF();
7214 if (APF.convertToInteger(IntVal, APFloat::rmTowardZero, &IsExact) !=
7219 return IntVal.exactLogBase2();
7224 bool BuildVectorSDNode::isConstant() const {
7225 for (const SDValue &Op : op_values()) {
7226 unsigned Opc = Op.getOpcode();
7227 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7233 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7234 // Find the first non-undef value in the shuffle mask.
7236 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7239 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7241 // Make sure all remaining elements are either undef or the same as the first
7243 for (int Idx = Mask[i]; i != e; ++i)
7244 if (Mask[i] >= 0 && Mask[i] != Idx)
7250 static void checkForCyclesHelper(const SDNode *N,
7251 SmallPtrSetImpl<const SDNode*> &Visited,
7252 SmallPtrSetImpl<const SDNode*> &Checked,
7253 const llvm::SelectionDAG *DAG) {
7254 // If this node has already been checked, don't check it again.
7255 if (Checked.count(N))
7258 // If a node has already been visited on this depth-first walk, reject it as
7260 if (!Visited.insert(N).second) {
7261 errs() << "Detected cycle in SelectionDAG\n";
7262 dbgs() << "Offending node:\n";
7263 N->dumprFull(DAG); dbgs() << "\n";
7267 for (const SDValue &Op : N->op_values())
7268 checkForCyclesHelper(Op.getNode(), Visited, Checked, DAG);
7275 void llvm::checkForCycles(const llvm::SDNode *N,
7276 const llvm::SelectionDAG *DAG,
7284 assert(N && "Checking nonexistent SDNode");
7285 SmallPtrSet<const SDNode*, 32> visited;
7286 SmallPtrSet<const SDNode*, 32> checked;
7287 checkForCyclesHelper(N, visited, checked, DAG);
7292 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7293 checkForCycles(DAG->getRoot().getNode(), DAG, force);