1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
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 (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
206 SDValue Op = N->getOperand(i);
207 if (Op.getOpcode() == ISD::UNDEF)
209 if (!isa<ConstantFPSDNode>(Op))
215 /// isScalarToVector - Return true if the specified node is a
216 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
217 /// element is not an undef.
218 bool ISD::isScalarToVector(const SDNode *N) {
219 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
222 if (N->getOpcode() != ISD::BUILD_VECTOR)
224 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226 unsigned NumElems = N->getNumOperands();
229 for (unsigned i = 1; i < NumElems; ++i) {
230 SDValue V = N->getOperand(i);
231 if (V.getOpcode() != ISD::UNDEF)
237 /// allOperandsUndef - Return true if the node has at least one operand
238 /// and all operands of the specified node are ISD::UNDEF.
239 bool ISD::allOperandsUndef(const SDNode *N) {
240 // Return false if the node has no operands.
241 // This is "logically inconsistent" with the definition of "all" but
242 // is probably the desired behavior.
243 if (N->getNumOperands() == 0)
246 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
247 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
253 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
256 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258 return ISD::SIGN_EXTEND;
260 return ISD::ZERO_EXTEND;
265 llvm_unreachable("Invalid LoadExtType");
268 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
269 /// when given the operation for (X op Y).
270 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
271 // To perform this operation, we just need to swap the L and G bits of the
273 unsigned OldL = (Operation >> 2) & 1;
274 unsigned OldG = (Operation >> 1) & 1;
275 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
276 (OldL << 1) | // New G bit
277 (OldG << 2)); // New L bit.
280 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
281 /// 'op' is a valid SetCC operation.
282 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
283 unsigned Operation = Op;
285 Operation ^= 7; // Flip L, G, E bits, but not U.
287 Operation ^= 15; // Flip all of the condition bits.
289 if (Operation > ISD::SETTRUE2)
290 Operation &= ~8; // Don't let N and U bits get set.
292 return ISD::CondCode(Operation);
296 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
297 /// signed operation and 2 if the result is an unsigned comparison. Return zero
298 /// if the operation does not depend on the sign of the input (setne and seteq).
299 static int isSignedOp(ISD::CondCode Opcode) {
301 default: llvm_unreachable("Illegal integer setcc operation!");
303 case ISD::SETNE: return 0;
307 case ISD::SETGE: return 1;
311 case ISD::SETUGE: return 2;
315 /// getSetCCOrOperation - Return the result of a logical OR between different
316 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
317 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
322 // Cannot fold a signed integer setcc with an unsigned integer setcc.
323 return ISD::SETCC_INVALID;
325 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
327 // If the N and U bits get set then the resultant comparison DOES suddenly
328 // care about orderedness, and is true when ordered.
329 if (Op > ISD::SETTRUE2)
330 Op &= ~16; // Clear the U bit if the N bit is set.
332 // Canonicalize illegal integer setcc's.
333 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
336 return ISD::CondCode(Op);
339 /// getSetCCAndOperation - Return the result of a logical AND between different
340 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
341 /// function returns zero if it is not possible to represent the resultant
343 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
346 // Cannot fold a signed setcc with an unsigned setcc.
347 return ISD::SETCC_INVALID;
349 // Combine all of the condition bits.
350 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352 // Canonicalize illegal integer setcc's.
356 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
357 case ISD::SETOEQ: // SETEQ & SETU[LG]E
358 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
359 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
360 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
367 //===----------------------------------------------------------------------===//
368 // SDNode Profile Support
369 //===----------------------------------------------------------------------===//
371 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
377 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
378 /// solely with their pointer.
379 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
380 ID.AddPointer(VTList.VTs);
383 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 static void AddNodeIDOperands(FoldingSetNodeID &ID,
386 ArrayRef<SDValue> Ops) {
387 for (auto& Op : Ops) {
388 ID.AddPointer(Op.getNode());
389 ID.AddInteger(Op.getResNo());
393 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 static void AddNodeIDOperands(FoldingSetNodeID &ID,
396 ArrayRef<SDUse> Ops) {
397 for (auto& Op : Ops) {
398 ID.AddPointer(Op.getNode());
399 ID.AddInteger(Op.getResNo());
402 /// Add logical or fast math flag values to FoldingSetNodeID value.
403 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
404 const SDNodeFlags *Flags) {
405 if (!Flags || !isBinOpWithFlags(Opcode))
408 unsigned RawFlags = Flags->getRawFlags();
409 // If no flags are set, do not alter the ID. This saves time and allows
410 // a gradual increase in API usage of the optional optimization flags.
412 ID.AddInteger(RawFlags);
415 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
416 if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
417 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
420 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
421 SDVTList VTList, ArrayRef<SDValue> OpList) {
422 AddNodeIDOpcode(ID, OpC);
423 AddNodeIDValueTypes(ID, VTList);
424 AddNodeIDOperands(ID, OpList);
427 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
429 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
430 switch (N->getOpcode()) {
431 case ISD::TargetExternalSymbol:
432 case ISD::ExternalSymbol:
433 llvm_unreachable("Should only be used on nodes with operands");
434 default: break; // Normal nodes don't need extra info.
435 case ISD::TargetConstant:
436 case ISD::Constant: {
437 const ConstantSDNode *C = cast<ConstantSDNode>(N);
438 ID.AddPointer(C->getConstantIntValue());
439 ID.AddBoolean(C->isOpaque());
442 case ISD::TargetConstantFP:
443 case ISD::ConstantFP: {
444 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
447 case ISD::TargetGlobalAddress:
448 case ISD::GlobalAddress:
449 case ISD::TargetGlobalTLSAddress:
450 case ISD::GlobalTLSAddress: {
451 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
452 ID.AddPointer(GA->getGlobal());
453 ID.AddInteger(GA->getOffset());
454 ID.AddInteger(GA->getTargetFlags());
455 ID.AddInteger(GA->getAddressSpace());
458 case ISD::BasicBlock:
459 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
462 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
464 case ISD::RegisterMask:
465 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
468 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
470 case ISD::FrameIndex:
471 case ISD::TargetFrameIndex:
472 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
475 case ISD::TargetJumpTable:
476 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
477 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
479 case ISD::ConstantPool:
480 case ISD::TargetConstantPool: {
481 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
482 ID.AddInteger(CP->getAlignment());
483 ID.AddInteger(CP->getOffset());
484 if (CP->isMachineConstantPoolEntry())
485 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
487 ID.AddPointer(CP->getConstVal());
488 ID.AddInteger(CP->getTargetFlags());
491 case ISD::TargetIndex: {
492 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
493 ID.AddInteger(TI->getIndex());
494 ID.AddInteger(TI->getOffset());
495 ID.AddInteger(TI->getTargetFlags());
499 const LoadSDNode *LD = cast<LoadSDNode>(N);
500 ID.AddInteger(LD->getMemoryVT().getRawBits());
501 ID.AddInteger(LD->getRawSubclassData());
502 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
506 const StoreSDNode *ST = cast<StoreSDNode>(N);
507 ID.AddInteger(ST->getMemoryVT().getRawBits());
508 ID.AddInteger(ST->getRawSubclassData());
509 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
512 case ISD::ATOMIC_CMP_SWAP:
513 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
514 case ISD::ATOMIC_SWAP:
515 case ISD::ATOMIC_LOAD_ADD:
516 case ISD::ATOMIC_LOAD_SUB:
517 case ISD::ATOMIC_LOAD_AND:
518 case ISD::ATOMIC_LOAD_OR:
519 case ISD::ATOMIC_LOAD_XOR:
520 case ISD::ATOMIC_LOAD_NAND:
521 case ISD::ATOMIC_LOAD_MIN:
522 case ISD::ATOMIC_LOAD_MAX:
523 case ISD::ATOMIC_LOAD_UMIN:
524 case ISD::ATOMIC_LOAD_UMAX:
525 case ISD::ATOMIC_LOAD:
526 case ISD::ATOMIC_STORE: {
527 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
528 ID.AddInteger(AT->getMemoryVT().getRawBits());
529 ID.AddInteger(AT->getRawSubclassData());
530 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
533 case ISD::PREFETCH: {
534 const MemSDNode *PF = cast<MemSDNode>(N);
535 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
538 case ISD::VECTOR_SHUFFLE: {
539 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
540 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
542 ID.AddInteger(SVN->getMaskElt(i));
545 case ISD::TargetBlockAddress:
546 case ISD::BlockAddress: {
547 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
548 ID.AddPointer(BA->getBlockAddress());
549 ID.AddInteger(BA->getOffset());
550 ID.AddInteger(BA->getTargetFlags());
553 } // end switch (N->getOpcode())
555 AddNodeIDFlags(ID, N);
557 // Target specific memory nodes could also have address spaces to check.
558 if (N->isTargetMemoryOpcode())
559 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
562 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
564 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
565 AddNodeIDOpcode(ID, N->getOpcode());
566 // Add the return value info.
567 AddNodeIDValueTypes(ID, N->getVTList());
568 // Add the operand info.
569 AddNodeIDOperands(ID, N->ops());
571 // Handle SDNode leafs with special info.
572 AddNodeIDCustom(ID, N);
575 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
576 /// the CSE map that carries volatility, temporalness, indexing mode, and
577 /// extension/truncation information.
579 static inline unsigned
580 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
581 bool isNonTemporal, bool isInvariant) {
582 assert((ConvType & 3) == ConvType &&
583 "ConvType may not require more than 2 bits!");
584 assert((AM & 7) == AM &&
585 "AM may not require more than 3 bits!");
589 (isNonTemporal << 6) |
593 //===----------------------------------------------------------------------===//
594 // SelectionDAG Class
595 //===----------------------------------------------------------------------===//
597 /// doNotCSE - Return true if CSE should not be performed for this node.
598 static bool doNotCSE(SDNode *N) {
599 if (N->getValueType(0) == MVT::Glue)
600 return true; // Never CSE anything that produces a flag.
602 switch (N->getOpcode()) {
604 case ISD::HANDLENODE:
606 return true; // Never CSE these nodes.
609 // Check that remaining values produced are not flags.
610 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
611 if (N->getValueType(i) == MVT::Glue)
612 return true; // Never CSE anything that produces a flag.
617 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
619 void SelectionDAG::RemoveDeadNodes() {
620 // Create a dummy node (which is not added to allnodes), that adds a reference
621 // to the root node, preventing it from being deleted.
622 HandleSDNode Dummy(getRoot());
624 SmallVector<SDNode*, 128> DeadNodes;
626 // Add all obviously-dead nodes to the DeadNodes worklist.
627 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
629 DeadNodes.push_back(I);
631 RemoveDeadNodes(DeadNodes);
633 // If the root changed (e.g. it was a dead load, update the root).
634 setRoot(Dummy.getValue());
637 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
638 /// given list, and any nodes that become unreachable as a result.
639 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
641 // Process the worklist, deleting the nodes and adding their uses to the
643 while (!DeadNodes.empty()) {
644 SDNode *N = DeadNodes.pop_back_val();
646 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
647 DUL->NodeDeleted(N, nullptr);
649 // Take the node out of the appropriate CSE map.
650 RemoveNodeFromCSEMaps(N);
652 // Next, brutally remove the operand list. This is safe to do, as there are
653 // no cycles in the graph.
654 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
656 SDNode *Operand = Use.getNode();
659 // Now that we removed this operand, see if there are no uses of it left.
660 if (Operand->use_empty())
661 DeadNodes.push_back(Operand);
668 void SelectionDAG::RemoveDeadNode(SDNode *N){
669 SmallVector<SDNode*, 16> DeadNodes(1, N);
671 // Create a dummy node that adds a reference to the root node, preventing
672 // it from being deleted. (This matters if the root is an operand of the
674 HandleSDNode Dummy(getRoot());
676 RemoveDeadNodes(DeadNodes);
679 void SelectionDAG::DeleteNode(SDNode *N) {
680 // First take this out of the appropriate CSE map.
681 RemoveNodeFromCSEMaps(N);
683 // Finally, remove uses due to operands of this node, remove from the
684 // AllNodes list, and delete the node.
685 DeleteNodeNotInCSEMaps(N);
688 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
689 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
690 assert(N->use_empty() && "Cannot delete a node that is not dead!");
692 // Drop all of the operands and decrement used node's use counts.
698 void SDDbgInfo::erase(const SDNode *Node) {
699 DbgValMapType::iterator I = DbgValMap.find(Node);
700 if (I == DbgValMap.end())
702 for (auto &Val: I->second)
703 Val->setIsInvalidated();
707 void SelectionDAG::DeallocateNode(SDNode *N) {
708 if (N->OperandsNeedDelete)
709 delete[] N->OperandList;
711 // Set the opcode to DELETED_NODE to help catch bugs when node
712 // memory is reallocated.
713 N->NodeType = ISD::DELETED_NODE;
715 NodeAllocator.Deallocate(AllNodes.remove(N));
717 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
718 // them and forget about that node.
723 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
724 static void VerifySDNode(SDNode *N) {
725 switch (N->getOpcode()) {
728 case ISD::BUILD_PAIR: {
729 EVT VT = N->getValueType(0);
730 assert(N->getNumValues() == 1 && "Too many results!");
731 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
732 "Wrong return type!");
733 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
734 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
735 "Mismatched operand types!");
736 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
737 "Wrong operand type!");
738 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
739 "Wrong return type size");
742 case ISD::BUILD_VECTOR: {
743 assert(N->getNumValues() == 1 && "Too many results!");
744 assert(N->getValueType(0).isVector() && "Wrong return type!");
745 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
746 "Wrong number of operands!");
747 EVT EltVT = N->getValueType(0).getVectorElementType();
748 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
749 assert((I->getValueType() == EltVT ||
750 (EltVT.isInteger() && I->getValueType().isInteger() &&
751 EltVT.bitsLE(I->getValueType()))) &&
752 "Wrong operand type!");
753 assert(I->getValueType() == N->getOperand(0).getValueType() &&
754 "Operands must all have the same type");
762 /// \brief Insert a newly allocated node into the DAG.
764 /// Handles insertion into the all nodes list and CSE map, as well as
765 /// verification and other common operations when a new node is allocated.
766 void SelectionDAG::InsertNode(SDNode *N) {
767 AllNodes.push_back(N);
773 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
774 /// correspond to it. This is useful when we're about to delete or repurpose
775 /// the node. We don't want future request for structurally identical nodes
776 /// to return N anymore.
777 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
779 switch (N->getOpcode()) {
780 case ISD::HANDLENODE: return false; // noop.
782 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
783 "Cond code doesn't exist!");
784 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
785 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
787 case ISD::ExternalSymbol:
788 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
790 case ISD::TargetExternalSymbol: {
791 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
792 Erased = TargetExternalSymbols.erase(
793 std::pair<std::string,unsigned char>(ESN->getSymbol(),
794 ESN->getTargetFlags()));
797 case ISD::VALUETYPE: {
798 EVT VT = cast<VTSDNode>(N)->getVT();
799 if (VT.isExtended()) {
800 Erased = ExtendedValueTypeNodes.erase(VT);
802 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
803 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
808 // Remove it from the CSE Map.
809 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
810 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
811 Erased = CSEMap.RemoveNode(N);
815 // Verify that the node was actually in one of the CSE maps, unless it has a
816 // flag result (which cannot be CSE'd) or is one of the special cases that are
817 // not subject to CSE.
818 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
819 !N->isMachineOpcode() && !doNotCSE(N)) {
822 llvm_unreachable("Node is not in map!");
828 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
829 /// maps and modified in place. Add it back to the CSE maps, unless an identical
830 /// node already exists, in which case transfer all its users to the existing
831 /// node. This transfer can potentially trigger recursive merging.
834 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
835 // For node types that aren't CSE'd, just act as if no identical node
838 SDNode *Existing = CSEMap.GetOrInsertNode(N);
840 // If there was already an existing matching node, use ReplaceAllUsesWith
841 // to replace the dead one with the existing one. This can cause
842 // recursive merging of other unrelated nodes down the line.
843 ReplaceAllUsesWith(N, Existing);
845 // N is now dead. Inform the listeners and delete it.
846 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
847 DUL->NodeDeleted(N, Existing);
848 DeleteNodeNotInCSEMaps(N);
853 // If the node doesn't already exist, we updated it. Inform listeners.
854 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
858 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
859 /// were replaced with those specified. If this node is never memoized,
860 /// return null, otherwise return a pointer to the slot it would take. If a
861 /// node already exists with these operands, the slot will be non-null.
862 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
867 SDValue Ops[] = { Op };
869 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
870 AddNodeIDCustom(ID, N);
871 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
875 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
876 /// were replaced with those specified. If this node is never memoized,
877 /// return null, otherwise return a pointer to the slot it would take. If a
878 /// node already exists with these operands, the slot will be non-null.
879 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
880 SDValue Op1, SDValue Op2,
885 SDValue Ops[] = { Op1, Op2 };
887 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
888 AddNodeIDCustom(ID, N);
889 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
894 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
895 /// were replaced with those specified. If this node is never memoized,
896 /// return null, otherwise return a pointer to the slot it would take. If a
897 /// node already exists with these operands, the slot will be non-null.
898 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
904 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
905 AddNodeIDCustom(ID, N);
906 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
910 /// getEVTAlignment - Compute the default alignment value for the
913 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
914 Type *Ty = VT == MVT::iPTR ?
915 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
916 VT.getTypeForEVT(*getContext());
918 return TLI->getDataLayout()->getABITypeAlignment(Ty);
921 // EntryNode could meaningfully have debug info if we can find it...
922 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
923 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
924 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
925 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
926 UpdateListeners(nullptr) {
927 AllNodes.push_back(&EntryNode);
928 DbgInfo = new SDDbgInfo();
931 void SelectionDAG::init(MachineFunction &mf) {
933 TLI = getSubtarget().getTargetLowering();
934 TSI = getSubtarget().getSelectionDAGInfo();
935 Context = &mf.getFunction()->getContext();
938 SelectionDAG::~SelectionDAG() {
939 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
944 void SelectionDAG::allnodes_clear() {
945 assert(&*AllNodes.begin() == &EntryNode);
946 AllNodes.remove(AllNodes.begin());
947 while (!AllNodes.empty())
948 DeallocateNode(AllNodes.begin());
951 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
952 SDVTList VTs, SDValue N1,
954 const SDNodeFlags *Flags) {
955 if (isBinOpWithFlags(Opcode)) {
956 // If no flags were passed in, use a default flags object.
958 if (Flags == nullptr)
961 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
962 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
967 BinarySDNode *N = new (NodeAllocator)
968 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
972 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
974 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
976 switch (N->getOpcode()) {
979 case ISD::ConstantFP:
980 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
981 "debug location. Use another overload.");
987 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
988 DebugLoc DL, void *&InsertPos) {
989 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
991 switch (N->getOpcode()) {
992 default: break; // Process only regular (non-target) constant nodes.
994 case ISD::ConstantFP:
995 // Erase debug location from the node if the node is used at several
996 // different places to do not propagate one location to all uses as it
997 // leads to incorrect debug info.
998 if (N->getDebugLoc() != DL)
999 N->setDebugLoc(DebugLoc());
1006 void SelectionDAG::clear() {
1008 OperandAllocator.Reset();
1011 ExtendedValueTypeNodes.clear();
1012 ExternalSymbols.clear();
1013 TargetExternalSymbols.clear();
1014 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1015 static_cast<CondCodeSDNode*>(nullptr));
1016 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1017 static_cast<SDNode*>(nullptr));
1019 EntryNode.UseList = nullptr;
1020 AllNodes.push_back(&EntryNode);
1021 Root = getEntryNode();
1025 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1026 return VT.bitsGT(Op.getValueType()) ?
1027 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1028 getNode(ISD::TRUNCATE, DL, VT, Op);
1031 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1032 return VT.bitsGT(Op.getValueType()) ?
1033 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1034 getNode(ISD::TRUNCATE, DL, VT, Op);
1037 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1038 return VT.bitsGT(Op.getValueType()) ?
1039 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1040 getNode(ISD::TRUNCATE, DL, VT, Op);
1043 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1045 if (VT.bitsLE(Op.getValueType()))
1046 return getNode(ISD::TRUNCATE, SL, VT, Op);
1048 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1049 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1052 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1053 assert(!VT.isVector() &&
1054 "getZeroExtendInReg should use the vector element type instead of "
1055 "the vector type!");
1056 if (Op.getValueType() == VT) return Op;
1057 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1058 APInt Imm = APInt::getLowBitsSet(BitWidth,
1059 VT.getSizeInBits());
1060 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1061 getConstant(Imm, DL, Op.getValueType()));
1064 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1065 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1066 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1067 "The sizes of the input and result must match in order to perform the "
1068 "extend in-register.");
1069 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1070 "The destination vector type must have fewer lanes than the input.");
1071 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1074 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1075 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1076 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1077 "The sizes of the input and result must match in order to perform the "
1078 "extend in-register.");
1079 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1080 "The destination vector type must have fewer lanes than the input.");
1081 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1084 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1085 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1086 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1087 "The sizes of the input and result must match in order to perform the "
1088 "extend in-register.");
1089 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1090 "The destination vector type must have fewer lanes than the input.");
1091 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1094 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1096 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1097 EVT EltVT = VT.getScalarType();
1099 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1100 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1103 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1104 EVT EltVT = VT.getScalarType();
1106 switch (TLI->getBooleanContents(VT)) {
1107 case TargetLowering::ZeroOrOneBooleanContent:
1108 case TargetLowering::UndefinedBooleanContent:
1109 TrueValue = getConstant(1, DL, VT);
1111 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1112 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1116 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1119 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1121 EVT EltVT = VT.getScalarType();
1122 assert((EltVT.getSizeInBits() >= 64 ||
1123 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1124 "getConstant with a uint64_t value that doesn't fit in the type!");
1125 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1128 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1131 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1134 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1135 bool isT, bool isO) {
1136 assert(VT.isInteger() && "Cannot create FP integer constant!");
1138 EVT EltVT = VT.getScalarType();
1139 const ConstantInt *Elt = &Val;
1141 // In some cases the vector type is legal but the element type is illegal and
1142 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1143 // inserted value (the type does not need to match the vector element type).
1144 // Any extra bits introduced will be truncated away.
1145 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1146 TargetLowering::TypePromoteInteger) {
1147 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1148 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1149 Elt = ConstantInt::get(*getContext(), NewVal);
1151 // In other cases the element type is illegal and needs to be expanded, for
1152 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1153 // the value into n parts and use a vector type with n-times the elements.
1154 // Then bitcast to the type requested.
1155 // Legalizing constants too early makes the DAGCombiner's job harder so we
1156 // only legalize if the DAG tells us we must produce legal types.
1157 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1158 TLI->getTypeAction(*getContext(), EltVT) ==
1159 TargetLowering::TypeExpandInteger) {
1160 APInt NewVal = Elt->getValue();
1161 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1162 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1163 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1164 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1166 // Check the temporary vector is the correct size. If this fails then
1167 // getTypeToTransformTo() probably returned a type whose size (in bits)
1168 // isn't a power-of-2 factor of the requested type size.
1169 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1171 SmallVector<SDValue, 2> EltParts;
1172 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1173 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1174 .trunc(ViaEltSizeInBits), DL,
1175 ViaEltVT, isT, isO));
1178 // EltParts is currently in little endian order. If we actually want
1179 // big-endian order then reverse it now.
1180 if (TLI->isBigEndian())
1181 std::reverse(EltParts.begin(), EltParts.end());
1183 // The elements must be reversed when the element order is different
1184 // to the endianness of the elements (because the BITCAST is itself a
1185 // vector shuffle in this situation). However, we do not need any code to
1186 // perform this reversal because getConstant() is producing a vector
1188 // This situation occurs in MIPS MSA.
1190 SmallVector<SDValue, 8> Ops;
1191 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1192 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1194 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1195 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1200 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1201 "APInt size does not match type size!");
1202 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1203 FoldingSetNodeID ID;
1204 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1208 SDNode *N = nullptr;
1209 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1211 return SDValue(N, 0);
1214 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1216 CSEMap.InsertNode(N, IP);
1220 SDValue Result(N, 0);
1221 if (VT.isVector()) {
1222 SmallVector<SDValue, 8> Ops;
1223 Ops.assign(VT.getVectorNumElements(), Result);
1224 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1229 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1230 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1233 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1235 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1238 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1240 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1242 EVT EltVT = VT.getScalarType();
1244 // Do the map lookup using the actual bit pattern for the floating point
1245 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1246 // we don't have issues with SNANs.
1247 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1248 FoldingSetNodeID ID;
1249 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1252 SDNode *N = nullptr;
1253 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1255 return SDValue(N, 0);
1258 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1260 CSEMap.InsertNode(N, IP);
1264 SDValue Result(N, 0);
1265 if (VT.isVector()) {
1266 SmallVector<SDValue, 8> Ops;
1267 Ops.assign(VT.getVectorNumElements(), Result);
1268 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1273 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1275 EVT EltVT = VT.getScalarType();
1276 if (EltVT==MVT::f32)
1277 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1278 else if (EltVT==MVT::f64)
1279 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1280 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1283 APFloat apf = APFloat(Val);
1284 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1286 return getConstantFP(apf, DL, VT, isTarget);
1288 llvm_unreachable("Unsupported type in getConstantFP");
1291 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1292 EVT VT, int64_t Offset,
1294 unsigned char TargetFlags) {
1295 assert((TargetFlags == 0 || isTargetGA) &&
1296 "Cannot set target flags on target-independent globals");
1298 // Truncate (with sign-extension) the offset value to the pointer size.
1299 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1301 Offset = SignExtend64(Offset, BitWidth);
1304 if (GV->isThreadLocal())
1305 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1307 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1309 FoldingSetNodeID ID;
1310 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1312 ID.AddInteger(Offset);
1313 ID.AddInteger(TargetFlags);
1314 ID.AddInteger(GV->getType()->getAddressSpace());
1316 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1317 return SDValue(E, 0);
1319 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1320 DL.getDebugLoc(), GV, VT,
1321 Offset, TargetFlags);
1322 CSEMap.InsertNode(N, IP);
1324 return SDValue(N, 0);
1327 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1328 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1329 FoldingSetNodeID ID;
1330 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1333 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1334 return SDValue(E, 0);
1336 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1337 CSEMap.InsertNode(N, IP);
1339 return SDValue(N, 0);
1342 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent jump tables");
1346 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1347 FoldingSetNodeID ID;
1348 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1350 ID.AddInteger(TargetFlags);
1352 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1353 return SDValue(E, 0);
1355 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1357 CSEMap.InsertNode(N, IP);
1359 return SDValue(N, 0);
1362 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1363 unsigned Alignment, int Offset,
1365 unsigned char TargetFlags) {
1366 assert((TargetFlags == 0 || isTarget) &&
1367 "Cannot set target flags on target-independent globals");
1369 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1370 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1371 FoldingSetNodeID ID;
1372 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1373 ID.AddInteger(Alignment);
1374 ID.AddInteger(Offset);
1376 ID.AddInteger(TargetFlags);
1378 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1379 return SDValue(E, 0);
1381 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1382 Alignment, TargetFlags);
1383 CSEMap.InsertNode(N, IP);
1385 return SDValue(N, 0);
1389 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1390 unsigned Alignment, int Offset,
1392 unsigned char TargetFlags) {
1393 assert((TargetFlags == 0 || isTarget) &&
1394 "Cannot set target flags on target-independent globals");
1396 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1397 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1398 FoldingSetNodeID ID;
1399 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1400 ID.AddInteger(Alignment);
1401 ID.AddInteger(Offset);
1402 C->addSelectionDAGCSEId(ID);
1403 ID.AddInteger(TargetFlags);
1405 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1406 return SDValue(E, 0);
1408 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1409 Alignment, TargetFlags);
1410 CSEMap.InsertNode(N, IP);
1412 return SDValue(N, 0);
1415 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1416 unsigned char TargetFlags) {
1417 FoldingSetNodeID ID;
1418 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1419 ID.AddInteger(Index);
1420 ID.AddInteger(Offset);
1421 ID.AddInteger(TargetFlags);
1423 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1424 return SDValue(E, 0);
1426 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1428 CSEMap.InsertNode(N, IP);
1430 return SDValue(N, 0);
1433 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1434 FoldingSetNodeID ID;
1435 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1438 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1439 return SDValue(E, 0);
1441 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1442 CSEMap.InsertNode(N, IP);
1444 return SDValue(N, 0);
1447 SDValue SelectionDAG::getValueType(EVT VT) {
1448 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1449 ValueTypeNodes.size())
1450 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1452 SDNode *&N = VT.isExtended() ?
1453 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1455 if (N) return SDValue(N, 0);
1456 N = new (NodeAllocator) VTSDNode(VT);
1458 return SDValue(N, 0);
1461 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1462 SDNode *&N = ExternalSymbols[Sym];
1463 if (N) return SDValue(N, 0);
1464 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1466 return SDValue(N, 0);
1469 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1470 unsigned char TargetFlags) {
1472 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1474 if (N) return SDValue(N, 0);
1475 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1477 return SDValue(N, 0);
1480 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1481 if ((unsigned)Cond >= CondCodeNodes.size())
1482 CondCodeNodes.resize(Cond+1);
1484 if (!CondCodeNodes[Cond]) {
1485 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1486 CondCodeNodes[Cond] = N;
1490 return SDValue(CondCodeNodes[Cond], 0);
1493 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1494 // the shuffle mask M that point at N1 to point at N2, and indices that point
1495 // N2 to point at N1.
1496 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1498 ShuffleVectorSDNode::commuteMask(M);
1501 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1502 SDValue N2, const int *Mask) {
1503 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1504 "Invalid VECTOR_SHUFFLE");
1506 // Canonicalize shuffle undef, undef -> undef
1507 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1508 return getUNDEF(VT);
1510 // Validate that all indices in Mask are within the range of the elements
1511 // input to the shuffle.
1512 unsigned NElts = VT.getVectorNumElements();
1513 SmallVector<int, 8> MaskVec;
1514 for (unsigned i = 0; i != NElts; ++i) {
1515 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1516 MaskVec.push_back(Mask[i]);
1519 // Canonicalize shuffle v, v -> v, undef
1522 for (unsigned i = 0; i != NElts; ++i)
1523 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1526 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1527 if (N1.getOpcode() == ISD::UNDEF)
1528 commuteShuffle(N1, N2, MaskVec);
1530 // If shuffling a splat, try to blend the splat instead. We do this here so
1531 // that even when this arises during lowering we don't have to re-handle it.
1532 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1533 BitVector UndefElements;
1534 SDValue Splat = BV->getSplatValue(&UndefElements);
1538 for (int i = 0; i < (int)NElts; ++i) {
1539 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1542 // If this input comes from undef, mark it as such.
1543 if (UndefElements[MaskVec[i] - Offset]) {
1548 // If we can blend a non-undef lane, use that instead.
1549 if (!UndefElements[i])
1550 MaskVec[i] = i + Offset;
1553 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1554 BlendSplat(N1BV, 0);
1555 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1556 BlendSplat(N2BV, NElts);
1558 // Canonicalize all index into lhs, -> shuffle lhs, undef
1559 // Canonicalize all index into rhs, -> shuffle rhs, undef
1560 bool AllLHS = true, AllRHS = true;
1561 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1562 for (unsigned i = 0; i != NElts; ++i) {
1563 if (MaskVec[i] >= (int)NElts) {
1568 } else if (MaskVec[i] >= 0) {
1572 if (AllLHS && AllRHS)
1573 return getUNDEF(VT);
1574 if (AllLHS && !N2Undef)
1578 commuteShuffle(N1, N2, MaskVec);
1580 // Reset our undef status after accounting for the mask.
1581 N2Undef = N2.getOpcode() == ISD::UNDEF;
1582 // Re-check whether both sides ended up undef.
1583 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1584 return getUNDEF(VT);
1586 // If Identity shuffle return that node.
1587 bool Identity = true, AllSame = true;
1588 for (unsigned i = 0; i != NElts; ++i) {
1589 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1590 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1592 if (Identity && NElts)
1595 // Shuffling a constant splat doesn't change the result.
1599 // Look through any bitcasts. We check that these don't change the number
1600 // (and size) of elements and just changes their types.
1601 while (V.getOpcode() == ISD::BITCAST)
1602 V = V->getOperand(0);
1604 // A splat should always show up as a build vector node.
1605 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1606 BitVector UndefElements;
1607 SDValue Splat = BV->getSplatValue(&UndefElements);
1608 // If this is a splat of an undef, shuffling it is also undef.
1609 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1610 return getUNDEF(VT);
1613 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1615 // We only have a splat which can skip shuffles if there is a splatted
1616 // value and no undef lanes rearranged by the shuffle.
1617 if (Splat && UndefElements.none()) {
1618 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1619 // number of elements match or the value splatted is a zero constant.
1622 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1623 if (C->isNullValue())
1627 // If the shuffle itself creates a splat, build the vector directly.
1628 if (AllSame && SameNumElts) {
1629 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1630 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1632 EVT BuildVT = BV->getValueType(0);
1633 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1635 // We may have jumped through bitcasts, so the type of the
1636 // BUILD_VECTOR may not match the type of the shuffle.
1638 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1644 FoldingSetNodeID ID;
1645 SDValue Ops[2] = { N1, N2 };
1646 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1647 for (unsigned i = 0; i != NElts; ++i)
1648 ID.AddInteger(MaskVec[i]);
1651 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1652 return SDValue(E, 0);
1654 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1655 // SDNode doesn't have access to it. This memory will be "leaked" when
1656 // the node is deallocated, but recovered when the NodeAllocator is released.
1657 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1658 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1660 ShuffleVectorSDNode *N =
1661 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1662 dl.getDebugLoc(), N1, N2,
1664 CSEMap.InsertNode(N, IP);
1666 return SDValue(N, 0);
1669 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1670 MVT VT = SV.getSimpleValueType(0);
1671 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1672 ShuffleVectorSDNode::commuteMask(MaskVec);
1674 SDValue Op0 = SV.getOperand(0);
1675 SDValue Op1 = SV.getOperand(1);
1676 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1679 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1680 SDValue Val, SDValue DTy,
1681 SDValue STy, SDValue Rnd, SDValue Sat,
1682 ISD::CvtCode Code) {
1683 // If the src and dest types are the same and the conversion is between
1684 // integer types of the same sign or two floats, no conversion is necessary.
1686 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1689 FoldingSetNodeID ID;
1690 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1691 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1693 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1694 return SDValue(E, 0);
1696 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1699 CSEMap.InsertNode(N, IP);
1701 return SDValue(N, 0);
1704 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1705 FoldingSetNodeID ID;
1706 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1707 ID.AddInteger(RegNo);
1709 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1710 return SDValue(E, 0);
1712 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1713 CSEMap.InsertNode(N, IP);
1715 return SDValue(N, 0);
1718 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1719 FoldingSetNodeID ID;
1720 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1721 ID.AddPointer(RegMask);
1723 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1724 return SDValue(E, 0);
1726 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1727 CSEMap.InsertNode(N, IP);
1729 return SDValue(N, 0);
1732 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1733 FoldingSetNodeID ID;
1734 SDValue Ops[] = { Root };
1735 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1736 ID.AddPointer(Label);
1738 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1739 return SDValue(E, 0);
1741 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1742 dl.getDebugLoc(), Root, Label);
1743 CSEMap.InsertNode(N, IP);
1745 return SDValue(N, 0);
1749 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1752 unsigned char TargetFlags) {
1753 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1755 FoldingSetNodeID ID;
1756 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1758 ID.AddInteger(Offset);
1759 ID.AddInteger(TargetFlags);
1761 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1762 return SDValue(E, 0);
1764 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1766 CSEMap.InsertNode(N, IP);
1768 return SDValue(N, 0);
1771 SDValue SelectionDAG::getSrcValue(const Value *V) {
1772 assert((!V || V->getType()->isPointerTy()) &&
1773 "SrcValue is not a pointer?");
1775 FoldingSetNodeID ID;
1776 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1780 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1781 return SDValue(E, 0);
1783 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1784 CSEMap.InsertNode(N, IP);
1786 return SDValue(N, 0);
1789 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1790 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1791 FoldingSetNodeID ID;
1792 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1796 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1797 return SDValue(E, 0);
1799 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1800 CSEMap.InsertNode(N, IP);
1802 return SDValue(N, 0);
1805 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1806 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1807 unsigned SrcAS, unsigned DestAS) {
1808 SDValue Ops[] = {Ptr};
1809 FoldingSetNodeID ID;
1810 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1811 ID.AddInteger(SrcAS);
1812 ID.AddInteger(DestAS);
1815 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1816 return SDValue(E, 0);
1818 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1820 VT, Ptr, SrcAS, DestAS);
1821 CSEMap.InsertNode(N, IP);
1823 return SDValue(N, 0);
1826 /// getShiftAmountOperand - Return the specified value casted to
1827 /// the target's desired shift amount type.
1828 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1829 EVT OpTy = Op.getValueType();
1830 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1831 if (OpTy == ShTy || OpTy.isVector()) return Op;
1833 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1834 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1837 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1838 /// specified value type.
1839 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1840 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1841 unsigned ByteSize = VT.getStoreSize();
1842 Type *Ty = VT.getTypeForEVT(*getContext());
1843 unsigned StackAlign =
1844 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1846 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1847 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1850 /// CreateStackTemporary - Create a stack temporary suitable for holding
1851 /// either of the specified value types.
1852 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1853 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1854 VT2.getStoreSizeInBits())/8;
1855 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1856 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1857 const DataLayout *TD = TLI->getDataLayout();
1858 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1859 TD->getPrefTypeAlignment(Ty2));
1861 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1862 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1863 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1866 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1867 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1868 // These setcc operations always fold.
1872 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1874 case ISD::SETTRUE2: {
1875 TargetLowering::BooleanContent Cnt =
1876 TLI->getBooleanContents(N1->getValueType(0));
1878 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1892 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1896 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1897 const APInt &C2 = N2C->getAPIntValue();
1898 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1899 const APInt &C1 = N1C->getAPIntValue();
1902 default: llvm_unreachable("Unknown integer setcc!");
1903 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1904 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1905 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1906 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1907 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1908 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1909 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1910 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1911 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1912 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1916 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1917 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1918 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1921 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1922 return getUNDEF(VT);
1924 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1925 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1926 return getUNDEF(VT);
1928 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1929 R==APFloat::cmpLessThan, dl, VT);
1930 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1931 return getUNDEF(VT);
1933 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1934 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1935 return getUNDEF(VT);
1937 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1938 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1939 return getUNDEF(VT);
1941 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1942 R==APFloat::cmpEqual, dl, VT);
1943 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1944 return getUNDEF(VT);
1946 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1947 R==APFloat::cmpEqual, dl, VT);
1948 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1949 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1950 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1951 R==APFloat::cmpEqual, dl, VT);
1952 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1953 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1954 R==APFloat::cmpLessThan, dl, VT);
1955 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1956 R==APFloat::cmpUnordered, dl, VT);
1957 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1958 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1961 // Ensure that the constant occurs on the RHS.
1962 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1963 MVT CompVT = N1.getValueType().getSimpleVT();
1964 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1967 return getSetCC(dl, VT, N2, N1, SwappedCond);
1971 // Could not fold it.
1975 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1976 /// use this predicate to simplify operations downstream.
1977 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1978 // This predicate is not safe for vector operations.
1979 if (Op.getValueType().isVector())
1982 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1983 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1986 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1987 /// this predicate to simplify operations downstream. Mask is known to be zero
1988 /// for bits that V cannot have.
1989 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1990 unsigned Depth) const {
1991 APInt KnownZero, KnownOne;
1992 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1993 return (KnownZero & Mask) == Mask;
1996 /// Determine which bits of Op are known to be either zero or one and return
1997 /// them in the KnownZero/KnownOne bitsets.
1998 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1999 APInt &KnownOne, unsigned Depth) const {
2000 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2002 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2004 return; // Limit search depth.
2006 APInt KnownZero2, KnownOne2;
2008 switch (Op.getOpcode()) {
2010 // We know all of the bits for a constant!
2011 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2012 KnownZero = ~KnownOne;
2015 // If either the LHS or the RHS are Zero, the result is zero.
2016 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2017 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2019 // Output known-1 bits are only known if set in both the LHS & RHS.
2020 KnownOne &= KnownOne2;
2021 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2022 KnownZero |= KnownZero2;
2025 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2026 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2028 // Output known-0 bits are only known if clear in both the LHS & RHS.
2029 KnownZero &= KnownZero2;
2030 // Output known-1 are known to be set if set in either the LHS | RHS.
2031 KnownOne |= KnownOne2;
2034 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2035 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2037 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2038 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2039 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2040 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2041 KnownZero = KnownZeroOut;
2045 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2046 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2048 // If low bits are zero in either operand, output low known-0 bits.
2049 // Also compute a conserative estimate for high known-0 bits.
2050 // More trickiness is possible, but this is sufficient for the
2051 // interesting case of alignment computation.
2052 KnownOne.clearAllBits();
2053 unsigned TrailZ = KnownZero.countTrailingOnes() +
2054 KnownZero2.countTrailingOnes();
2055 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2056 KnownZero2.countLeadingOnes(),
2057 BitWidth) - BitWidth;
2059 TrailZ = std::min(TrailZ, BitWidth);
2060 LeadZ = std::min(LeadZ, BitWidth);
2061 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2062 APInt::getHighBitsSet(BitWidth, LeadZ);
2066 // For the purposes of computing leading zeros we can conservatively
2067 // treat a udiv as a logical right shift by the power of 2 known to
2068 // be less than the denominator.
2069 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2070 unsigned LeadZ = KnownZero2.countLeadingOnes();
2072 KnownOne2.clearAllBits();
2073 KnownZero2.clearAllBits();
2074 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2075 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2076 if (RHSUnknownLeadingOnes != BitWidth)
2077 LeadZ = std::min(BitWidth,
2078 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2080 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2084 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2085 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2087 // Only known if known in both the LHS and RHS.
2088 KnownOne &= KnownOne2;
2089 KnownZero &= KnownZero2;
2091 case ISD::SELECT_CC:
2092 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2093 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2095 // Only known if known in both the LHS and RHS.
2096 KnownOne &= KnownOne2;
2097 KnownZero &= KnownZero2;
2105 if (Op.getResNo() != 1)
2107 // The boolean result conforms to getBooleanContents.
2108 // If we know the result of a setcc has the top bits zero, use this info.
2109 // We know that we have an integer-based boolean since these operations
2110 // are only available for integer.
2111 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2112 TargetLowering::ZeroOrOneBooleanContent &&
2114 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2117 // If we know the result of a setcc has the top bits zero, use this info.
2118 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2119 TargetLowering::ZeroOrOneBooleanContent &&
2121 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2124 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2125 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2126 unsigned ShAmt = SA->getZExtValue();
2128 // If the shift count is an invalid immediate, don't do anything.
2129 if (ShAmt >= BitWidth)
2132 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2133 KnownZero <<= ShAmt;
2135 // low bits known zero.
2136 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2140 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2141 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2142 unsigned ShAmt = SA->getZExtValue();
2144 // If the shift count is an invalid immediate, don't do anything.
2145 if (ShAmt >= BitWidth)
2148 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2149 KnownZero = KnownZero.lshr(ShAmt);
2150 KnownOne = KnownOne.lshr(ShAmt);
2152 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2153 KnownZero |= HighBits; // High bits known zero.
2157 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2158 unsigned ShAmt = SA->getZExtValue();
2160 // If the shift count is an invalid immediate, don't do anything.
2161 if (ShAmt >= BitWidth)
2164 // If any of the demanded bits are produced by the sign extension, we also
2165 // demand the input sign bit.
2166 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2168 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2169 KnownZero = KnownZero.lshr(ShAmt);
2170 KnownOne = KnownOne.lshr(ShAmt);
2172 // Handle the sign bits.
2173 APInt SignBit = APInt::getSignBit(BitWidth);
2174 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2176 if (KnownZero.intersects(SignBit)) {
2177 KnownZero |= HighBits; // New bits are known zero.
2178 } else if (KnownOne.intersects(SignBit)) {
2179 KnownOne |= HighBits; // New bits are known one.
2183 case ISD::SIGN_EXTEND_INREG: {
2184 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2185 unsigned EBits = EVT.getScalarType().getSizeInBits();
2187 // Sign extension. Compute the demanded bits in the result that are not
2188 // present in the input.
2189 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2191 APInt InSignBit = APInt::getSignBit(EBits);
2192 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2194 // If the sign extended bits are demanded, we know that the sign
2196 InSignBit = InSignBit.zext(BitWidth);
2197 if (NewBits.getBoolValue())
2198 InputDemandedBits |= InSignBit;
2200 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2201 KnownOne &= InputDemandedBits;
2202 KnownZero &= InputDemandedBits;
2204 // If the sign bit of the input is known set or clear, then we know the
2205 // top bits of the result.
2206 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2207 KnownZero |= NewBits;
2208 KnownOne &= ~NewBits;
2209 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2210 KnownOne |= NewBits;
2211 KnownZero &= ~NewBits;
2212 } else { // Input sign bit unknown
2213 KnownZero &= ~NewBits;
2214 KnownOne &= ~NewBits;
2219 case ISD::CTTZ_ZERO_UNDEF:
2221 case ISD::CTLZ_ZERO_UNDEF:
2223 unsigned LowBits = Log2_32(BitWidth)+1;
2224 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2225 KnownOne.clearAllBits();
2229 LoadSDNode *LD = cast<LoadSDNode>(Op);
2230 // If this is a ZEXTLoad and we are looking at the loaded value.
2231 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2232 EVT VT = LD->getMemoryVT();
2233 unsigned MemBits = VT.getScalarType().getSizeInBits();
2234 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2235 } else if (const MDNode *Ranges = LD->getRanges()) {
2236 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2240 case ISD::ZERO_EXTEND: {
2241 EVT InVT = Op.getOperand(0).getValueType();
2242 unsigned InBits = InVT.getScalarType().getSizeInBits();
2243 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2244 KnownZero = KnownZero.trunc(InBits);
2245 KnownOne = KnownOne.trunc(InBits);
2246 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2247 KnownZero = KnownZero.zext(BitWidth);
2248 KnownOne = KnownOne.zext(BitWidth);
2249 KnownZero |= NewBits;
2252 case ISD::SIGN_EXTEND: {
2253 EVT InVT = Op.getOperand(0).getValueType();
2254 unsigned InBits = InVT.getScalarType().getSizeInBits();
2255 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2257 KnownZero = KnownZero.trunc(InBits);
2258 KnownOne = KnownOne.trunc(InBits);
2259 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2261 // Note if the sign bit is known to be zero or one.
2262 bool SignBitKnownZero = KnownZero.isNegative();
2263 bool SignBitKnownOne = KnownOne.isNegative();
2265 KnownZero = KnownZero.zext(BitWidth);
2266 KnownOne = KnownOne.zext(BitWidth);
2268 // If the sign bit is known zero or one, the top bits match.
2269 if (SignBitKnownZero)
2270 KnownZero |= NewBits;
2271 else if (SignBitKnownOne)
2272 KnownOne |= NewBits;
2275 case ISD::ANY_EXTEND: {
2276 EVT InVT = Op.getOperand(0).getValueType();
2277 unsigned InBits = InVT.getScalarType().getSizeInBits();
2278 KnownZero = KnownZero.trunc(InBits);
2279 KnownOne = KnownOne.trunc(InBits);
2280 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2281 KnownZero = KnownZero.zext(BitWidth);
2282 KnownOne = KnownOne.zext(BitWidth);
2285 case ISD::TRUNCATE: {
2286 EVT InVT = Op.getOperand(0).getValueType();
2287 unsigned InBits = InVT.getScalarType().getSizeInBits();
2288 KnownZero = KnownZero.zext(InBits);
2289 KnownOne = KnownOne.zext(InBits);
2290 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2291 KnownZero = KnownZero.trunc(BitWidth);
2292 KnownOne = KnownOne.trunc(BitWidth);
2295 case ISD::AssertZext: {
2296 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2297 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2298 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2299 KnownZero |= (~InMask);
2300 KnownOne &= (~KnownZero);
2304 // All bits are zero except the low bit.
2305 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2309 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2310 // We know that the top bits of C-X are clear if X contains less bits
2311 // than C (i.e. no wrap-around can happen). For example, 20-X is
2312 // positive if we can prove that X is >= 0 and < 16.
2313 if (CLHS->getAPIntValue().isNonNegative()) {
2314 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2315 // NLZ can't be BitWidth with no sign bit
2316 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2317 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2319 // If all of the MaskV bits are known to be zero, then we know the
2320 // output top bits are zero, because we now know that the output is
2322 if ((KnownZero2 & MaskV) == MaskV) {
2323 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2324 // Top bits known zero.
2325 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2333 // Output known-0 bits are known if clear or set in both the low clear bits
2334 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2335 // low 3 bits clear.
2336 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2337 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2339 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2340 KnownZeroOut = std::min(KnownZeroOut,
2341 KnownZero2.countTrailingOnes());
2343 if (Op.getOpcode() == ISD::ADD) {
2344 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2348 // With ADDE, a carry bit may be added in, so we can only use this
2349 // information if we know (at least) that the low two bits are clear. We
2350 // then return to the caller that the low bit is unknown but that other bits
2352 if (KnownZeroOut >= 2) // ADDE
2353 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2357 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2358 const APInt &RA = Rem->getAPIntValue().abs();
2359 if (RA.isPowerOf2()) {
2360 APInt LowBits = RA - 1;
2361 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2363 // The low bits of the first operand are unchanged by the srem.
2364 KnownZero = KnownZero2 & LowBits;
2365 KnownOne = KnownOne2 & LowBits;
2367 // If the first operand is non-negative or has all low bits zero, then
2368 // the upper bits are all zero.
2369 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2370 KnownZero |= ~LowBits;
2372 // If the first operand is negative and not all low bits are zero, then
2373 // the upper bits are all one.
2374 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2375 KnownOne |= ~LowBits;
2376 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2381 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2382 const APInt &RA = Rem->getAPIntValue();
2383 if (RA.isPowerOf2()) {
2384 APInt LowBits = (RA - 1);
2385 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2387 // The upper bits are all zero, the lower ones are unchanged.
2388 KnownZero = KnownZero2 | ~LowBits;
2389 KnownOne = KnownOne2 & LowBits;
2394 // Since the result is less than or equal to either operand, any leading
2395 // zero bits in either operand must also exist in the result.
2396 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2397 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2399 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2400 KnownZero2.countLeadingOnes());
2401 KnownOne.clearAllBits();
2402 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2405 case ISD::EXTRACT_ELEMENT: {
2406 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2407 const unsigned Index =
2408 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2409 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2411 // Remove low part of known bits mask
2412 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2413 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2415 // Remove high part of known bit mask
2416 KnownZero = KnownZero.trunc(BitWidth);
2417 KnownOne = KnownOne.trunc(BitWidth);
2420 case ISD::FrameIndex:
2421 case ISD::TargetFrameIndex:
2422 if (unsigned Align = InferPtrAlignment(Op)) {
2423 // The low bits are known zero if the pointer is aligned.
2424 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2430 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2433 case ISD::INTRINSIC_WO_CHAIN:
2434 case ISD::INTRINSIC_W_CHAIN:
2435 case ISD::INTRINSIC_VOID:
2436 // Allow the target to implement this method for its nodes.
2437 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2441 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2444 /// ComputeNumSignBits - Return the number of times the sign bit of the
2445 /// register is replicated into the other bits. We know that at least 1 bit
2446 /// is always equal to the sign bit (itself), but other cases can give us
2447 /// information. For example, immediately after an "SRA X, 2", we know that
2448 /// the top 3 bits are all equal to each other, so we return 3.
2449 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2450 EVT VT = Op.getValueType();
2451 assert(VT.isInteger() && "Invalid VT!");
2452 unsigned VTBits = VT.getScalarType().getSizeInBits();
2454 unsigned FirstAnswer = 1;
2457 return 1; // Limit search depth.
2459 switch (Op.getOpcode()) {
2461 case ISD::AssertSext:
2462 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2463 return VTBits-Tmp+1;
2464 case ISD::AssertZext:
2465 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2468 case ISD::Constant: {
2469 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2470 return Val.getNumSignBits();
2473 case ISD::SIGN_EXTEND:
2475 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2476 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2478 case ISD::SIGN_EXTEND_INREG:
2479 // Max of the input and what this extends.
2481 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2484 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2485 return std::max(Tmp, Tmp2);
2488 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2489 // SRA X, C -> adds C sign bits.
2490 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2491 Tmp += C->getZExtValue();
2492 if (Tmp > VTBits) Tmp = VTBits;
2496 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2497 // shl destroys sign bits.
2498 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2499 if (C->getZExtValue() >= VTBits || // Bad shift.
2500 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2501 return Tmp - C->getZExtValue();
2506 case ISD::XOR: // NOT is handled here.
2507 // Logical binary ops preserve the number of sign bits at the worst.
2508 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2510 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2511 FirstAnswer = std::min(Tmp, Tmp2);
2512 // We computed what we know about the sign bits as our first
2513 // answer. Now proceed to the generic code that uses
2514 // computeKnownBits, and pick whichever answer is better.
2519 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2520 if (Tmp == 1) return 1; // Early out.
2521 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2522 return std::min(Tmp, Tmp2);
2530 if (Op.getResNo() != 1)
2532 // The boolean result conforms to getBooleanContents. Fall through.
2533 // If setcc returns 0/-1, all bits are sign bits.
2534 // We know that we have an integer-based boolean since these operations
2535 // are only available for integer.
2536 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2537 TargetLowering::ZeroOrNegativeOneBooleanContent)
2541 // If setcc returns 0/-1, all bits are sign bits.
2542 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2543 TargetLowering::ZeroOrNegativeOneBooleanContent)
2548 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2549 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2551 // Handle rotate right by N like a rotate left by 32-N.
2552 if (Op.getOpcode() == ISD::ROTR)
2553 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2555 // If we aren't rotating out all of the known-in sign bits, return the
2556 // number that are left. This handles rotl(sext(x), 1) for example.
2557 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2558 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2562 // Add can have at most one carry bit. Thus we know that the output
2563 // is, at worst, one more bit than the inputs.
2564 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2565 if (Tmp == 1) return 1; // Early out.
2567 // Special case decrementing a value (ADD X, -1):
2568 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2569 if (CRHS->isAllOnesValue()) {
2570 APInt KnownZero, KnownOne;
2571 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2573 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2575 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2578 // If we are subtracting one from a positive number, there is no carry
2579 // out of the result.
2580 if (KnownZero.isNegative())
2584 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2585 if (Tmp2 == 1) return 1;
2586 return std::min(Tmp, Tmp2)-1;
2589 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2590 if (Tmp2 == 1) return 1;
2593 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2594 if (CLHS->isNullValue()) {
2595 APInt KnownZero, KnownOne;
2596 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2597 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2599 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2602 // If the input is known to be positive (the sign bit is known clear),
2603 // the output of the NEG has the same number of sign bits as the input.
2604 if (KnownZero.isNegative())
2607 // Otherwise, we treat this like a SUB.
2610 // Sub can have at most one carry bit. Thus we know that the output
2611 // is, at worst, one more bit than the inputs.
2612 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2613 if (Tmp == 1) return 1; // Early out.
2614 return std::min(Tmp, Tmp2)-1;
2616 // FIXME: it's tricky to do anything useful for this, but it is an important
2617 // case for targets like X86.
2619 case ISD::EXTRACT_ELEMENT: {
2620 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2621 const int BitWidth = Op.getValueType().getSizeInBits();
2623 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2625 // Get reverse index (starting from 1), Op1 value indexes elements from
2626 // little end. Sign starts at big end.
2627 const int rIndex = Items - 1 -
2628 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2630 // If the sign portion ends in our element the substraction gives correct
2631 // result. Otherwise it gives either negative or > bitwidth result
2632 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2636 // If we are looking at the loaded value of the SDNode.
2637 if (Op.getResNo() == 0) {
2638 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2639 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2640 unsigned ExtType = LD->getExtensionType();
2643 case ISD::SEXTLOAD: // '17' bits known
2644 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2645 return VTBits-Tmp+1;
2646 case ISD::ZEXTLOAD: // '16' bits known
2647 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2653 // Allow the target to implement this method for its nodes.
2654 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2655 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2656 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2657 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2658 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2659 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2662 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2663 // use this information.
2664 APInt KnownZero, KnownOne;
2665 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2668 if (KnownZero.isNegative()) { // sign bit is 0
2670 } else if (KnownOne.isNegative()) { // sign bit is 1;
2677 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2678 // the number of identical bits in the top of the input value.
2680 Mask <<= Mask.getBitWidth()-VTBits;
2681 // Return # leading zeros. We use 'min' here in case Val was zero before
2682 // shifting. We don't want to return '64' as for an i32 "0".
2683 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2686 /// isBaseWithConstantOffset - Return true if the specified operand is an
2687 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2688 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2689 /// semantics as an ADD. This handles the equivalence:
2690 /// X|Cst == X+Cst iff X&Cst = 0.
2691 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2692 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2693 !isa<ConstantSDNode>(Op.getOperand(1)))
2696 if (Op.getOpcode() == ISD::OR &&
2697 !MaskedValueIsZero(Op.getOperand(0),
2698 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2705 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2706 // If we're told that NaNs won't happen, assume they won't.
2707 if (getTarget().Options.NoNaNsFPMath)
2710 // If the value is a constant, we can obviously see if it is a NaN or not.
2711 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2712 return !C->getValueAPF().isNaN();
2714 // TODO: Recognize more cases here.
2719 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2720 // If the value is a constant, we can obviously see if it is a zero or not.
2721 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2722 return !C->isZero();
2724 // TODO: Recognize more cases here.
2725 switch (Op.getOpcode()) {
2728 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2729 return !C->isNullValue();
2736 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2737 // Check the obvious case.
2738 if (A == B) return true;
2740 // For for negative and positive zero.
2741 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2742 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2743 if (CA->isZero() && CB->isZero()) return true;
2745 // Otherwise they may not be equal.
2749 /// getNode - Gets or creates the specified node.
2751 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2752 FoldingSetNodeID ID;
2753 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2755 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2756 return SDValue(E, 0);
2758 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2759 DL.getDebugLoc(), getVTList(VT));
2760 CSEMap.InsertNode(N, IP);
2763 return SDValue(N, 0);
2766 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2767 EVT VT, SDValue Operand) {
2768 // Constant fold unary operations with an integer constant operand. Even
2769 // opaque constant will be folded, because the folding of unary operations
2770 // doesn't create new constants with different values. Nevertheless, the
2771 // opaque flag is preserved during folding to prevent future folding with
2773 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2774 const APInt &Val = C->getAPIntValue();
2777 case ISD::SIGN_EXTEND:
2778 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2779 C->isTargetOpcode(), C->isOpaque());
2780 case ISD::ANY_EXTEND:
2781 case ISD::ZERO_EXTEND:
2783 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2784 C->isTargetOpcode(), C->isOpaque());
2785 case ISD::UINT_TO_FP:
2786 case ISD::SINT_TO_FP: {
2787 APFloat apf(EVTToAPFloatSemantics(VT),
2788 APInt::getNullValue(VT.getSizeInBits()));
2789 (void)apf.convertFromAPInt(Val,
2790 Opcode==ISD::SINT_TO_FP,
2791 APFloat::rmNearestTiesToEven);
2792 return getConstantFP(apf, DL, VT);
2795 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2796 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2797 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2798 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2799 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2800 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2803 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2806 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2809 case ISD::CTLZ_ZERO_UNDEF:
2810 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2813 case ISD::CTTZ_ZERO_UNDEF:
2814 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2819 // Constant fold unary operations with a floating point constant operand.
2820 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2821 APFloat V = C->getValueAPF(); // make copy
2825 return getConstantFP(V, DL, VT);
2828 return getConstantFP(V, DL, VT);
2830 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2831 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2832 return getConstantFP(V, DL, VT);
2836 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2837 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2838 return getConstantFP(V, DL, VT);
2842 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2843 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2844 return getConstantFP(V, DL, VT);
2847 case ISD::FP_EXTEND: {
2849 // This can return overflow, underflow, or inexact; we don't care.
2850 // FIXME need to be more flexible about rounding mode.
2851 (void)V.convert(EVTToAPFloatSemantics(VT),
2852 APFloat::rmNearestTiesToEven, &ignored);
2853 return getConstantFP(V, DL, VT);
2855 case ISD::FP_TO_SINT:
2856 case ISD::FP_TO_UINT: {
2859 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2860 // FIXME need to be more flexible about rounding mode.
2861 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2862 Opcode==ISD::FP_TO_SINT,
2863 APFloat::rmTowardZero, &ignored);
2864 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2866 APInt api(VT.getSizeInBits(), x);
2867 return getConstant(api, DL, VT);
2870 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2871 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2872 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2873 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2874 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2875 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2880 // Constant fold unary operations with a vector integer or float operand.
2881 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2882 if (BV->isConstant()) {
2885 // FIXME: Entirely reasonable to perform folding of other unary
2886 // operations here as the need arises.
2893 case ISD::FP_EXTEND:
2894 case ISD::FP_TO_SINT:
2895 case ISD::FP_TO_UINT:
2897 case ISD::UINT_TO_FP:
2898 case ISD::SINT_TO_FP: {
2899 EVT SVT = VT.getScalarType();
2900 EVT InVT = BV->getValueType(0);
2901 EVT InSVT = InVT.getScalarType();
2903 // Find legal integer scalar type for constant promotion and
2904 // ensure that its scalar size is at least as large as source.
2906 if (SVT.isInteger()) {
2907 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2908 if (LegalSVT.bitsLT(SVT)) break;
2911 // Let the above scalar folding handle the folding of each element.
2912 SmallVector<SDValue, 8> Ops;
2913 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2914 SDValue OpN = BV->getOperand(i);
2915 EVT OpVT = OpN.getValueType();
2917 // Build vector (integer) scalar operands may need implicit
2918 // truncation - do this before constant folding.
2919 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2920 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2922 OpN = getNode(Opcode, DL, SVT, OpN);
2924 // Legalize the (integer) scalar constant if necessary.
2925 if (LegalSVT != SVT)
2926 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2928 if (OpN.getOpcode() != ISD::UNDEF &&
2929 OpN.getOpcode() != ISD::Constant &&
2930 OpN.getOpcode() != ISD::ConstantFP)
2934 if (Ops.size() == VT.getVectorNumElements())
2935 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2942 unsigned OpOpcode = Operand.getNode()->getOpcode();
2944 case ISD::TokenFactor:
2945 case ISD::MERGE_VALUES:
2946 case ISD::CONCAT_VECTORS:
2947 return Operand; // Factor, merge or concat of one node? No need.
2948 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2949 case ISD::FP_EXTEND:
2950 assert(VT.isFloatingPoint() &&
2951 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2952 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2953 assert((!VT.isVector() ||
2954 VT.getVectorNumElements() ==
2955 Operand.getValueType().getVectorNumElements()) &&
2956 "Vector element count mismatch!");
2957 if (Operand.getOpcode() == ISD::UNDEF)
2958 return getUNDEF(VT);
2960 case ISD::SIGN_EXTEND:
2961 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2962 "Invalid SIGN_EXTEND!");
2963 if (Operand.getValueType() == VT) return Operand; // noop extension
2964 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2965 "Invalid sext node, dst < src!");
2966 assert((!VT.isVector() ||
2967 VT.getVectorNumElements() ==
2968 Operand.getValueType().getVectorNumElements()) &&
2969 "Vector element count mismatch!");
2970 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2971 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2972 else if (OpOpcode == ISD::UNDEF)
2973 // sext(undef) = 0, because the top bits will all be the same.
2974 return getConstant(0, DL, VT);
2976 case ISD::ZERO_EXTEND:
2977 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2978 "Invalid ZERO_EXTEND!");
2979 if (Operand.getValueType() == VT) return Operand; // noop extension
2980 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2981 "Invalid zext node, dst < src!");
2982 assert((!VT.isVector() ||
2983 VT.getVectorNumElements() ==
2984 Operand.getValueType().getVectorNumElements()) &&
2985 "Vector element count mismatch!");
2986 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2987 return getNode(ISD::ZERO_EXTEND, DL, VT,
2988 Operand.getNode()->getOperand(0));
2989 else if (OpOpcode == ISD::UNDEF)
2990 // zext(undef) = 0, because the top bits will be zero.
2991 return getConstant(0, DL, VT);
2993 case ISD::ANY_EXTEND:
2994 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2995 "Invalid ANY_EXTEND!");
2996 if (Operand.getValueType() == VT) return Operand; // noop extension
2997 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2998 "Invalid anyext node, dst < src!");
2999 assert((!VT.isVector() ||
3000 VT.getVectorNumElements() ==
3001 Operand.getValueType().getVectorNumElements()) &&
3002 "Vector element count mismatch!");
3004 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3005 OpOpcode == ISD::ANY_EXTEND)
3006 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3007 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3008 else if (OpOpcode == ISD::UNDEF)
3009 return getUNDEF(VT);
3011 // (ext (trunx x)) -> x
3012 if (OpOpcode == ISD::TRUNCATE) {
3013 SDValue OpOp = Operand.getNode()->getOperand(0);
3014 if (OpOp.getValueType() == VT)
3019 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3020 "Invalid TRUNCATE!");
3021 if (Operand.getValueType() == VT) return Operand; // noop truncate
3022 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3023 "Invalid truncate node, src < dst!");
3024 assert((!VT.isVector() ||
3025 VT.getVectorNumElements() ==
3026 Operand.getValueType().getVectorNumElements()) &&
3027 "Vector element count mismatch!");
3028 if (OpOpcode == ISD::TRUNCATE)
3029 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3030 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3031 OpOpcode == ISD::ANY_EXTEND) {
3032 // If the source is smaller than the dest, we still need an extend.
3033 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3034 .bitsLT(VT.getScalarType()))
3035 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3036 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3037 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3038 return Operand.getNode()->getOperand(0);
3040 if (OpOpcode == ISD::UNDEF)
3041 return getUNDEF(VT);
3044 // Basic sanity checking.
3045 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3046 && "Cannot BITCAST between types of different sizes!");
3047 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3048 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3049 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3050 if (OpOpcode == ISD::UNDEF)
3051 return getUNDEF(VT);
3053 case ISD::SCALAR_TO_VECTOR:
3054 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3055 (VT.getVectorElementType() == Operand.getValueType() ||
3056 (VT.getVectorElementType().isInteger() &&
3057 Operand.getValueType().isInteger() &&
3058 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3059 "Illegal SCALAR_TO_VECTOR node!");
3060 if (OpOpcode == ISD::UNDEF)
3061 return getUNDEF(VT);
3062 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3063 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3064 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3065 Operand.getConstantOperandVal(1) == 0 &&
3066 Operand.getOperand(0).getValueType() == VT)
3067 return Operand.getOperand(0);
3070 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3071 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3072 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3073 Operand.getNode()->getOperand(0));
3074 if (OpOpcode == ISD::FNEG) // --X -> X
3075 return Operand.getNode()->getOperand(0);
3078 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3079 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3084 SDVTList VTs = getVTList(VT);
3085 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3086 FoldingSetNodeID ID;
3087 SDValue Ops[1] = { Operand };
3088 AddNodeIDNode(ID, Opcode, VTs, Ops);
3090 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3091 return SDValue(E, 0);
3093 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3094 DL.getDebugLoc(), VTs, Operand);
3095 CSEMap.InsertNode(N, IP);
3097 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3098 DL.getDebugLoc(), VTs, Operand);
3102 return SDValue(N, 0);
3105 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3106 SDNode *Cst1, SDNode *Cst2) {
3107 // If the opcode is a target-specific ISD node, there's nothing we can
3108 // do here and the operand rules may not line up with the below, so
3110 if (Opcode >= ISD::BUILTIN_OP_END)
3113 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3114 SmallVector<SDValue, 4> Outputs;
3115 EVT SVT = VT.getScalarType();
3117 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3118 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3119 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3122 if (Scalar1 && Scalar2)
3123 // Scalar instruction.
3124 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3126 // For vectors extract each constant element into Inputs so we can constant
3127 // fold them individually.
3128 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3129 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3133 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3135 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3136 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3137 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3138 if (!V1 || !V2) // Not a constant, bail.
3141 if (V1->isOpaque() || V2->isOpaque())
3144 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3145 // FIXME: This is valid and could be handled by truncating the APInts.
3146 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3149 Inputs.push_back(std::make_pair(V1, V2));
3153 // We have a number of constant values, constant fold them element by element.
3154 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3155 const APInt &C1 = Inputs[I].first->getAPIntValue();
3156 const APInt &C2 = Inputs[I].second->getAPIntValue();
3160 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3163 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3166 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3169 if (!C2.getBoolValue())
3171 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3174 if (!C2.getBoolValue())
3176 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3179 if (!C2.getBoolValue())
3181 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3184 if (!C2.getBoolValue())
3186 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3189 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3192 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3195 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3198 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3201 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3204 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3207 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3210 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3217 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3218 "Expected a scalar or vector!"));
3220 // Handle the scalar case first.
3222 return Outputs.back();
3224 // We may have a vector type but a scalar result. Create a splat.
3225 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3227 // Build a big vector out of the scalar elements we generated.
3228 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3231 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3232 SDValue N2, const SDNodeFlags *Flags) {
3233 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3234 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3237 case ISD::TokenFactor:
3238 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3239 N2.getValueType() == MVT::Other && "Invalid token factor!");
3240 // Fold trivial token factors.
3241 if (N1.getOpcode() == ISD::EntryToken) return N2;
3242 if (N2.getOpcode() == ISD::EntryToken) return N1;
3243 if (N1 == N2) return N1;
3245 case ISD::CONCAT_VECTORS:
3246 // Concat of UNDEFs is UNDEF.
3247 if (N1.getOpcode() == ISD::UNDEF &&
3248 N2.getOpcode() == ISD::UNDEF)
3249 return getUNDEF(VT);
3251 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3252 // one big BUILD_VECTOR.
3253 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3254 N2.getOpcode() == ISD::BUILD_VECTOR) {
3255 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3256 N1.getNode()->op_end());
3257 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3259 // BUILD_VECTOR requires all inputs to be of the same type, find the
3260 // maximum type and extend them all.
3261 EVT SVT = VT.getScalarType();
3262 for (SDValue Op : Elts)
3263 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3264 if (SVT.bitsGT(VT.getScalarType()))
3265 for (SDValue &Op : Elts)
3266 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3267 ? getZExtOrTrunc(Op, DL, SVT)
3268 : getSExtOrTrunc(Op, DL, SVT);
3270 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3274 assert(VT.isInteger() && "This operator does not apply to FP types!");
3275 assert(N1.getValueType() == N2.getValueType() &&
3276 N1.getValueType() == VT && "Binary operator types must match!");
3277 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3278 // worth handling here.
3279 if (N2C && N2C->isNullValue())
3281 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3288 assert(VT.isInteger() && "This operator does not apply to FP types!");
3289 assert(N1.getValueType() == N2.getValueType() &&
3290 N1.getValueType() == VT && "Binary operator types must match!");
3291 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3292 // it's worth handling here.
3293 if (N2C && N2C->isNullValue())
3303 assert(VT.isInteger() && "This operator does not apply to FP types!");
3304 assert(N1.getValueType() == N2.getValueType() &&
3305 N1.getValueType() == VT && "Binary operator types must match!");
3312 if (getTarget().Options.UnsafeFPMath) {
3313 if (Opcode == ISD::FADD) {
3315 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3316 if (CFP->getValueAPF().isZero())
3319 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3320 if (CFP->getValueAPF().isZero())
3322 } else if (Opcode == ISD::FSUB) {
3324 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3325 if (CFP->getValueAPF().isZero())
3327 } else if (Opcode == ISD::FMUL) {
3328 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3331 // If the first operand isn't the constant, try the second
3333 CFP = dyn_cast<ConstantFPSDNode>(N2);
3340 return SDValue(CFP,0);
3342 if (CFP->isExactlyValue(1.0))
3347 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3348 assert(N1.getValueType() == N2.getValueType() &&
3349 N1.getValueType() == VT && "Binary operator types must match!");
3351 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3352 assert(N1.getValueType() == VT &&
3353 N1.getValueType().isFloatingPoint() &&
3354 N2.getValueType().isFloatingPoint() &&
3355 "Invalid FCOPYSIGN!");
3362 assert(VT == N1.getValueType() &&
3363 "Shift operators return type must be the same as their first arg");
3364 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3365 "Shifts only work on integers");
3366 assert((!VT.isVector() || VT == N2.getValueType()) &&
3367 "Vector shift amounts must be in the same as their first arg");
3368 // Verify that the shift amount VT is bit enough to hold valid shift
3369 // amounts. This catches things like trying to shift an i1024 value by an
3370 // i8, which is easy to fall into in generic code that uses
3371 // TLI.getShiftAmount().
3372 assert(N2.getValueType().getSizeInBits() >=
3373 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3374 "Invalid use of small shift amount with oversized value!");
3376 // Always fold shifts of i1 values so the code generator doesn't need to
3377 // handle them. Since we know the size of the shift has to be less than the
3378 // size of the value, the shift/rotate count is guaranteed to be zero.
3381 if (N2C && N2C->isNullValue())
3384 case ISD::FP_ROUND_INREG: {
3385 EVT EVT = cast<VTSDNode>(N2)->getVT();
3386 assert(VT == N1.getValueType() && "Not an inreg round!");
3387 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3388 "Cannot FP_ROUND_INREG integer types");
3389 assert(EVT.isVector() == VT.isVector() &&
3390 "FP_ROUND_INREG type should be vector iff the operand "
3392 assert((!EVT.isVector() ||
3393 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3394 "Vector element counts must match in FP_ROUND_INREG");
3395 assert(EVT.bitsLE(VT) && "Not rounding down!");
3397 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3401 assert(VT.isFloatingPoint() &&
3402 N1.getValueType().isFloatingPoint() &&
3403 VT.bitsLE(N1.getValueType()) &&
3404 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3405 if (N1.getValueType() == VT) return N1; // noop conversion.
3407 case ISD::AssertSext:
3408 case ISD::AssertZext: {
3409 EVT EVT = cast<VTSDNode>(N2)->getVT();
3410 assert(VT == N1.getValueType() && "Not an inreg extend!");
3411 assert(VT.isInteger() && EVT.isInteger() &&
3412 "Cannot *_EXTEND_INREG FP types");
3413 assert(!EVT.isVector() &&
3414 "AssertSExt/AssertZExt type should be the vector element type "
3415 "rather than the vector type!");
3416 assert(EVT.bitsLE(VT) && "Not extending!");
3417 if (VT == EVT) return N1; // noop assertion.
3420 case ISD::SIGN_EXTEND_INREG: {
3421 EVT EVT = cast<VTSDNode>(N2)->getVT();
3422 assert(VT == N1.getValueType() && "Not an inreg extend!");
3423 assert(VT.isInteger() && EVT.isInteger() &&
3424 "Cannot *_EXTEND_INREG FP types");
3425 assert(EVT.isVector() == VT.isVector() &&
3426 "SIGN_EXTEND_INREG type should be vector iff the operand "
3428 assert((!EVT.isVector() ||
3429 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3430 "Vector element counts must match in SIGN_EXTEND_INREG");
3431 assert(EVT.bitsLE(VT) && "Not extending!");
3432 if (EVT == VT) return N1; // Not actually extending
3435 APInt Val = N1C->getAPIntValue();
3436 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3437 Val <<= Val.getBitWidth()-FromBits;
3438 Val = Val.ashr(Val.getBitWidth()-FromBits);
3439 return getConstant(Val, DL, VT);
3443 case ISD::EXTRACT_VECTOR_ELT:
3444 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3445 if (N1.getOpcode() == ISD::UNDEF)
3446 return getUNDEF(VT);
3448 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3449 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3450 return getUNDEF(VT);
3452 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3453 // expanding copies of large vectors from registers.
3455 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3456 N1.getNumOperands() > 0) {
3458 N1.getOperand(0).getValueType().getVectorNumElements();
3459 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3460 N1.getOperand(N2C->getZExtValue() / Factor),
3461 getConstant(N2C->getZExtValue() % Factor, DL,
3462 N2.getValueType()));
3465 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3466 // expanding large vector constants.
3467 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3468 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3470 if (VT != Elt.getValueType())
3471 // If the vector element type is not legal, the BUILD_VECTOR operands
3472 // are promoted and implicitly truncated, and the result implicitly
3473 // extended. Make that explicit here.
3474 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3479 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3480 // operations are lowered to scalars.
3481 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3482 // If the indices are the same, return the inserted element else
3483 // if the indices are known different, extract the element from
3484 // the original vector.
3485 SDValue N1Op2 = N1.getOperand(2);
3486 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3488 if (N1Op2C && N2C) {
3489 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3490 if (VT == N1.getOperand(1).getValueType())
3491 return N1.getOperand(1);
3493 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3496 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3500 case ISD::EXTRACT_ELEMENT:
3501 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3502 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3503 (N1.getValueType().isInteger() == VT.isInteger()) &&
3504 N1.getValueType() != VT &&
3505 "Wrong types for EXTRACT_ELEMENT!");
3507 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3508 // 64-bit integers into 32-bit parts. Instead of building the extract of
3509 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3510 if (N1.getOpcode() == ISD::BUILD_PAIR)
3511 return N1.getOperand(N2C->getZExtValue());
3513 // EXTRACT_ELEMENT of a constant int is also very common.
3514 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3515 unsigned ElementSize = VT.getSizeInBits();
3516 unsigned Shift = ElementSize * N2C->getZExtValue();
3517 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3518 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3521 case ISD::EXTRACT_SUBVECTOR: {
3523 if (VT.isSimple() && N1.getValueType().isSimple()) {
3524 assert(VT.isVector() && N1.getValueType().isVector() &&
3525 "Extract subvector VTs must be a vectors!");
3526 assert(VT.getVectorElementType() ==
3527 N1.getValueType().getVectorElementType() &&
3528 "Extract subvector VTs must have the same element type!");
3529 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3530 "Extract subvector must be from larger vector to smaller vector!");
3532 if (isa<ConstantSDNode>(Index.getNode())) {
3533 assert((VT.getVectorNumElements() +
3534 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3535 <= N1.getValueType().getVectorNumElements())
3536 && "Extract subvector overflow!");
3539 // Trivial extraction.
3540 if (VT.getSimpleVT() == N1.getSimpleValueType())
3547 // Perform trivial constant folding.
3549 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3552 // Canonicalize constant to RHS if commutative.
3553 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3554 std::swap(N1C, N2C);
3558 // Constant fold FP operations.
3559 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3560 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3561 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3563 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3564 // Canonicalize constant to RHS if commutative.
3565 std::swap(N1CFP, N2CFP);
3568 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3569 APFloat::opStatus s;
3572 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3573 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3574 return getConstantFP(V1, DL, VT);
3577 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3578 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3579 return getConstantFP(V1, DL, VT);
3582 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3583 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3584 return getConstantFP(V1, DL, VT);
3587 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3588 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3589 s!=APFloat::opDivByZero)) {
3590 return getConstantFP(V1, DL, VT);
3594 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3595 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3596 s!=APFloat::opDivByZero)) {
3597 return getConstantFP(V1, DL, VT);
3600 case ISD::FCOPYSIGN:
3602 return getConstantFP(V1, DL, VT);
3607 if (Opcode == ISD::FP_ROUND) {
3608 APFloat V = N1CFP->getValueAPF(); // make copy
3610 // This can return overflow, underflow, or inexact; we don't care.
3611 // FIXME need to be more flexible about rounding mode.
3612 (void)V.convert(EVTToAPFloatSemantics(VT),
3613 APFloat::rmNearestTiesToEven, &ignored);
3614 return getConstantFP(V, DL, VT);
3618 // Canonicalize an UNDEF to the RHS, even over a constant.
3619 if (N1.getOpcode() == ISD::UNDEF) {
3620 if (isCommutativeBinOp(Opcode)) {
3624 case ISD::FP_ROUND_INREG:
3625 case ISD::SIGN_EXTEND_INREG:
3631 return N1; // fold op(undef, arg2) -> undef
3639 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3640 // For vectors, we can't easily build an all zero vector, just return
3647 // Fold a bunch of operators when the RHS is undef.
3648 if (N2.getOpcode() == ISD::UNDEF) {
3651 if (N1.getOpcode() == ISD::UNDEF)
3652 // Handle undef ^ undef -> 0 special case. This is a common
3654 return getConstant(0, DL, VT);
3664 return N2; // fold op(arg1, undef) -> undef
3670 if (getTarget().Options.UnsafeFPMath)
3678 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3679 // For vectors, we can't easily build an all zero vector, just return
3684 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3685 // For vectors, we can't easily build an all one vector, just return
3693 // Memoize this node if possible.
3695 SDVTList VTs = getVTList(VT);
3696 if (VT != MVT::Glue) {
3697 SDValue Ops[] = {N1, N2};
3698 FoldingSetNodeID ID;
3699 AddNodeIDNode(ID, Opcode, VTs, Ops);
3700 AddNodeIDFlags(ID, Opcode, Flags);
3702 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3703 return SDValue(E, 0);
3705 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3707 CSEMap.InsertNode(N, IP);
3709 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3713 return SDValue(N, 0);
3716 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3717 SDValue N1, SDValue N2, SDValue N3) {
3718 // Perform various simplifications.
3719 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3722 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3723 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3724 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3725 if (N1CFP && N2CFP && N3CFP) {
3726 APFloat V1 = N1CFP->getValueAPF();
3727 const APFloat &V2 = N2CFP->getValueAPF();
3728 const APFloat &V3 = N3CFP->getValueAPF();
3729 APFloat::opStatus s =
3730 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3731 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3732 return getConstantFP(V1, DL, VT);
3736 case ISD::CONCAT_VECTORS:
3737 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3738 // one big BUILD_VECTOR.
3739 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3740 N2.getOpcode() == ISD::BUILD_VECTOR &&
3741 N3.getOpcode() == ISD::BUILD_VECTOR) {
3742 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3743 N1.getNode()->op_end());
3744 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3745 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3746 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3750 // Use FoldSetCC to simplify SETCC's.
3751 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3752 if (Simp.getNode()) return Simp;
3757 if (N1C->getZExtValue())
3758 return N2; // select true, X, Y -> X
3759 return N3; // select false, X, Y -> Y
3762 if (N2 == N3) return N2; // select C, X, X -> X
3764 case ISD::VECTOR_SHUFFLE:
3765 llvm_unreachable("should use getVectorShuffle constructor!");
3766 case ISD::INSERT_SUBVECTOR: {
3768 if (VT.isSimple() && N1.getValueType().isSimple()
3769 && N2.getValueType().isSimple()) {
3770 assert(VT.isVector() && N1.getValueType().isVector() &&
3771 N2.getValueType().isVector() &&
3772 "Insert subvector VTs must be a vectors");
3773 assert(VT == N1.getValueType() &&
3774 "Dest and insert subvector source types must match!");
3775 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3776 "Insert subvector must be from smaller vector to larger vector!");
3777 if (isa<ConstantSDNode>(Index.getNode())) {
3778 assert((N2.getValueType().getVectorNumElements() +
3779 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3780 <= VT.getVectorNumElements())
3781 && "Insert subvector overflow!");
3784 // Trivial insertion.
3785 if (VT.getSimpleVT() == N2.getSimpleValueType())
3791 // Fold bit_convert nodes from a type to themselves.
3792 if (N1.getValueType() == VT)
3797 // Memoize node if it doesn't produce a flag.
3799 SDVTList VTs = getVTList(VT);
3800 if (VT != MVT::Glue) {
3801 SDValue Ops[] = { N1, N2, N3 };
3802 FoldingSetNodeID ID;
3803 AddNodeIDNode(ID, Opcode, VTs, Ops);
3805 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3806 return SDValue(E, 0);
3808 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3809 DL.getDebugLoc(), VTs, N1, N2, N3);
3810 CSEMap.InsertNode(N, IP);
3812 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3813 DL.getDebugLoc(), VTs, N1, N2, N3);
3817 return SDValue(N, 0);
3820 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3821 SDValue N1, SDValue N2, SDValue N3,
3823 SDValue Ops[] = { N1, N2, N3, N4 };
3824 return getNode(Opcode, DL, VT, Ops);
3827 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3828 SDValue N1, SDValue N2, SDValue N3,
3829 SDValue N4, SDValue N5) {
3830 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3831 return getNode(Opcode, DL, VT, Ops);
3834 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3835 /// the incoming stack arguments to be loaded from the stack.
3836 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3837 SmallVector<SDValue, 8> ArgChains;
3839 // Include the original chain at the beginning of the list. When this is
3840 // used by target LowerCall hooks, this helps legalize find the
3841 // CALLSEQ_BEGIN node.
3842 ArgChains.push_back(Chain);
3844 // Add a chain value for each stack argument.
3845 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3846 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3847 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3848 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3849 if (FI->getIndex() < 0)
3850 ArgChains.push_back(SDValue(L, 1));
3852 // Build a tokenfactor for all the chains.
3853 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3856 /// getMemsetValue - Vectorized representation of the memset value
3858 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3860 assert(Value.getOpcode() != ISD::UNDEF);
3862 unsigned NumBits = VT.getScalarType().getSizeInBits();
3863 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3864 assert(C->getAPIntValue().getBitWidth() == 8);
3865 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3867 return DAG.getConstant(Val, dl, VT);
3868 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3872 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3873 EVT IntVT = VT.getScalarType();
3874 if (!IntVT.isInteger())
3875 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3877 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3879 // Use a multiplication with 0x010101... to extend the input to the
3881 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3882 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3883 DAG.getConstant(Magic, dl, IntVT));
3886 if (VT != Value.getValueType() && !VT.isInteger())
3887 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3888 if (VT != Value.getValueType()) {
3889 assert(VT.getVectorElementType() == Value.getValueType() &&
3890 "value type should be one vector element here");
3891 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3892 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3898 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3899 /// used when a memcpy is turned into a memset when the source is a constant
3901 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3902 const TargetLowering &TLI, StringRef Str) {
3903 // Handle vector with all elements zero.
3906 return DAG.getConstant(0, dl, VT);
3907 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3908 return DAG.getConstantFP(0.0, dl, VT);
3909 else if (VT.isVector()) {
3910 unsigned NumElts = VT.getVectorNumElements();
3911 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3912 return DAG.getNode(ISD::BITCAST, dl, VT,
3913 DAG.getConstant(0, dl,
3914 EVT::getVectorVT(*DAG.getContext(),
3917 llvm_unreachable("Expected type!");
3920 assert(!VT.isVector() && "Can't handle vector type here!");
3921 unsigned NumVTBits = VT.getSizeInBits();
3922 unsigned NumVTBytes = NumVTBits / 8;
3923 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3925 APInt Val(NumVTBits, 0);
3926 if (TLI.isLittleEndian()) {
3927 for (unsigned i = 0; i != NumBytes; ++i)
3928 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3930 for (unsigned i = 0; i != NumBytes; ++i)
3931 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3934 // If the "cost" of materializing the integer immediate is less than the cost
3935 // of a load, then it is cost effective to turn the load into the immediate.
3936 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3937 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3938 return DAG.getConstant(Val, dl, VT);
3939 return SDValue(nullptr, 0);
3942 /// getMemBasePlusOffset - Returns base and offset node for the
3944 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3945 SelectionDAG &DAG) {
3946 EVT VT = Base.getValueType();
3947 return DAG.getNode(ISD::ADD, dl,
3948 VT, Base, DAG.getConstant(Offset, dl, VT));
3951 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3953 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3954 unsigned SrcDelta = 0;
3955 GlobalAddressSDNode *G = nullptr;
3956 if (Src.getOpcode() == ISD::GlobalAddress)
3957 G = cast<GlobalAddressSDNode>(Src);
3958 else if (Src.getOpcode() == ISD::ADD &&
3959 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3960 Src.getOperand(1).getOpcode() == ISD::Constant) {
3961 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3962 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3967 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3970 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3971 /// to replace the memset / memcpy. Return true if the number of memory ops
3972 /// is below the threshold. It returns the types of the sequence of
3973 /// memory ops to perform memset / memcpy by reference.
3974 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3975 unsigned Limit, uint64_t Size,
3976 unsigned DstAlign, unsigned SrcAlign,
3982 const TargetLowering &TLI) {
3983 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3984 "Expecting memcpy / memset source to meet alignment requirement!");
3985 // If 'SrcAlign' is zero, that means the memory operation does not need to
3986 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3987 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3988 // is the specified alignment of the memory operation. If it is zero, that
3989 // means it's possible to change the alignment of the destination.
3990 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3991 // not need to be loaded.
3992 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3993 IsMemset, ZeroMemset, MemcpyStrSrc,
3994 DAG.getMachineFunction());
3996 if (VT == MVT::Other) {
3998 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3999 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4000 VT = TLI.getPointerTy();
4002 switch (DstAlign & 7) {
4003 case 0: VT = MVT::i64; break;
4004 case 4: VT = MVT::i32; break;
4005 case 2: VT = MVT::i16; break;
4006 default: VT = MVT::i8; break;
4011 while (!TLI.isTypeLegal(LVT))
4012 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4013 assert(LVT.isInteger());
4019 unsigned NumMemOps = 0;
4021 unsigned VTSize = VT.getSizeInBits() / 8;
4022 while (VTSize > Size) {
4023 // For now, only use non-vector load / store's for the left-over pieces.
4028 if (VT.isVector() || VT.isFloatingPoint()) {
4029 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4030 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4031 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4033 else if (NewVT == MVT::i64 &&
4034 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4035 TLI.isSafeMemOpType(MVT::f64)) {
4036 // i64 is usually not legal on 32-bit targets, but f64 may be.
4044 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4045 if (NewVT == MVT::i8)
4047 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4049 NewVTSize = NewVT.getSizeInBits() / 8;
4051 // If the new VT cannot cover all of the remaining bits, then consider
4052 // issuing a (or a pair of) unaligned and overlapping load / store.
4053 // FIXME: Only does this for 64-bit or more since we don't have proper
4054 // cost model for unaligned load / store.
4057 if (NumMemOps && AllowOverlap &&
4058 VTSize >= 8 && NewVTSize < Size &&
4059 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4067 if (++NumMemOps > Limit)
4070 MemOps.push_back(VT);
4077 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4078 SDValue Chain, SDValue Dst,
4079 SDValue Src, uint64_t Size,
4080 unsigned Align, bool isVol,
4082 MachinePointerInfo DstPtrInfo,
4083 MachinePointerInfo SrcPtrInfo) {
4084 // Turn a memcpy of undef to nop.
4085 if (Src.getOpcode() == ISD::UNDEF)
4088 // Expand memcpy to a series of load and store ops if the size operand falls
4089 // below a certain threshold.
4090 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4091 // rather than maybe a humongous number of loads and stores.
4092 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4093 std::vector<EVT> MemOps;
4094 bool DstAlignCanChange = false;
4095 MachineFunction &MF = DAG.getMachineFunction();
4096 MachineFrameInfo *MFI = MF.getFrameInfo();
4097 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4098 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4099 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4100 DstAlignCanChange = true;
4101 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4102 if (Align > SrcAlign)
4105 bool CopyFromStr = isMemSrcFromString(Src, Str);
4106 bool isZeroStr = CopyFromStr && Str.empty();
4107 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4109 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4110 (DstAlignCanChange ? 0 : Align),
4111 (isZeroStr ? 0 : SrcAlign),
4112 false, false, CopyFromStr, true, DAG, TLI))
4115 if (DstAlignCanChange) {
4116 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4117 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4119 // Don't promote to an alignment that would require dynamic stack
4121 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4122 if (!TRI->needsStackRealignment(MF))
4123 while (NewAlign > Align &&
4124 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4127 if (NewAlign > Align) {
4128 // Give the stack frame object a larger alignment if needed.
4129 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4130 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4135 SmallVector<SDValue, 8> OutChains;
4136 unsigned NumMemOps = MemOps.size();
4137 uint64_t SrcOff = 0, DstOff = 0;
4138 for (unsigned i = 0; i != NumMemOps; ++i) {
4140 unsigned VTSize = VT.getSizeInBits() / 8;
4141 SDValue Value, Store;
4143 if (VTSize > Size) {
4144 // Issuing an unaligned load / store pair that overlaps with the previous
4145 // pair. Adjust the offset accordingly.
4146 assert(i == NumMemOps-1 && i != 0);
4147 SrcOff -= VTSize - Size;
4148 DstOff -= VTSize - Size;
4152 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4153 // It's unlikely a store of a vector immediate can be done in a single
4154 // instruction. It would require a load from a constantpool first.
4155 // We only handle zero vectors here.
4156 // FIXME: Handle other cases where store of vector immediate is done in
4157 // a single instruction.
4158 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4159 if (Value.getNode())
4160 Store = DAG.getStore(Chain, dl, Value,
4161 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4162 DstPtrInfo.getWithOffset(DstOff), isVol,
4166 if (!Store.getNode()) {
4167 // The type might not be legal for the target. This should only happen
4168 // if the type is smaller than a legal type, as on PPC, so the right
4169 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4170 // to Load/Store if NVT==VT.
4171 // FIXME does the case above also need this?
4172 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4173 assert(NVT.bitsGE(VT));
4174 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4175 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4176 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4177 false, MinAlign(SrcAlign, SrcOff));
4178 Store = DAG.getTruncStore(Chain, dl, Value,
4179 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4180 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4183 OutChains.push_back(Store);
4189 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4192 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4193 SDValue Chain, SDValue Dst,
4194 SDValue Src, uint64_t Size,
4195 unsigned Align, bool isVol,
4197 MachinePointerInfo DstPtrInfo,
4198 MachinePointerInfo SrcPtrInfo) {
4199 // Turn a memmove of undef to nop.
4200 if (Src.getOpcode() == ISD::UNDEF)
4203 // Expand memmove to a series of load and store ops if the size operand falls
4204 // below a certain threshold.
4205 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4206 std::vector<EVT> MemOps;
4207 bool DstAlignCanChange = false;
4208 MachineFunction &MF = DAG.getMachineFunction();
4209 MachineFrameInfo *MFI = MF.getFrameInfo();
4210 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4211 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4212 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4213 DstAlignCanChange = true;
4214 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4215 if (Align > SrcAlign)
4217 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4219 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4220 (DstAlignCanChange ? 0 : Align), SrcAlign,
4221 false, false, false, false, DAG, TLI))
4224 if (DstAlignCanChange) {
4225 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4226 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4227 if (NewAlign > Align) {
4228 // Give the stack frame object a larger alignment if needed.
4229 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4230 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4235 uint64_t SrcOff = 0, DstOff = 0;
4236 SmallVector<SDValue, 8> LoadValues;
4237 SmallVector<SDValue, 8> LoadChains;
4238 SmallVector<SDValue, 8> OutChains;
4239 unsigned NumMemOps = MemOps.size();
4240 for (unsigned i = 0; i < NumMemOps; i++) {
4242 unsigned VTSize = VT.getSizeInBits() / 8;
4245 Value = DAG.getLoad(VT, dl, Chain,
4246 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4247 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4248 false, false, SrcAlign);
4249 LoadValues.push_back(Value);
4250 LoadChains.push_back(Value.getValue(1));
4253 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4255 for (unsigned i = 0; i < NumMemOps; i++) {
4257 unsigned VTSize = VT.getSizeInBits() / 8;
4260 Store = DAG.getStore(Chain, dl, LoadValues[i],
4261 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4262 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4263 OutChains.push_back(Store);
4267 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4270 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4273 /// \param DAG Selection DAG where lowered code is placed.
4274 /// \param dl Link to corresponding IR location.
4275 /// \param Chain Control flow dependency.
4276 /// \param Dst Pointer to destination memory location.
4277 /// \param Src Value of byte to write into the memory.
4278 /// \param Size Number of bytes to write.
4279 /// \param Align Alignment of the destination in bytes.
4280 /// \param isVol True if destination is volatile.
4281 /// \param DstPtrInfo IR information on the memory pointer.
4282 /// \returns New head in the control flow, if lowering was successful, empty
4283 /// SDValue otherwise.
4285 /// The function tries to replace 'llvm.memset' intrinsic with several store
4286 /// operations and value calculation code. This is usually profitable for small
4288 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4289 SDValue Chain, SDValue Dst,
4290 SDValue Src, uint64_t Size,
4291 unsigned Align, bool isVol,
4292 MachinePointerInfo DstPtrInfo) {
4293 // Turn a memset of undef to nop.
4294 if (Src.getOpcode() == ISD::UNDEF)
4297 // Expand memset to a series of load/store ops if the size operand
4298 // falls below a certain threshold.
4299 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4300 std::vector<EVT> MemOps;
4301 bool DstAlignCanChange = false;
4302 MachineFunction &MF = DAG.getMachineFunction();
4303 MachineFrameInfo *MFI = MF.getFrameInfo();
4304 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4305 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4306 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4307 DstAlignCanChange = true;
4309 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4310 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4311 Size, (DstAlignCanChange ? 0 : Align), 0,
4312 true, IsZeroVal, false, true, DAG, TLI))
4315 if (DstAlignCanChange) {
4316 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4317 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4318 if (NewAlign > Align) {
4319 // Give the stack frame object a larger alignment if needed.
4320 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4321 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4326 SmallVector<SDValue, 8> OutChains;
4327 uint64_t DstOff = 0;
4328 unsigned NumMemOps = MemOps.size();
4330 // Find the largest store and generate the bit pattern for it.
4331 EVT LargestVT = MemOps[0];
4332 for (unsigned i = 1; i < NumMemOps; i++)
4333 if (MemOps[i].bitsGT(LargestVT))
4334 LargestVT = MemOps[i];
4335 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4337 for (unsigned i = 0; i < NumMemOps; i++) {
4339 unsigned VTSize = VT.getSizeInBits() / 8;
4340 if (VTSize > Size) {
4341 // Issuing an unaligned load / store pair that overlaps with the previous
4342 // pair. Adjust the offset accordingly.
4343 assert(i == NumMemOps-1 && i != 0);
4344 DstOff -= VTSize - Size;
4347 // If this store is smaller than the largest store see whether we can get
4348 // the smaller value for free with a truncate.
4349 SDValue Value = MemSetValue;
4350 if (VT.bitsLT(LargestVT)) {
4351 if (!LargestVT.isVector() && !VT.isVector() &&
4352 TLI.isTruncateFree(LargestVT, VT))
4353 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4355 Value = getMemsetValue(Src, VT, DAG, dl);
4357 assert(Value.getValueType() == VT && "Value with wrong type.");
4358 SDValue Store = DAG.getStore(Chain, dl, Value,
4359 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4360 DstPtrInfo.getWithOffset(DstOff),
4361 isVol, false, Align);
4362 OutChains.push_back(Store);
4363 DstOff += VT.getSizeInBits() / 8;
4367 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4370 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4371 SDValue Src, SDValue Size,
4372 unsigned Align, bool isVol, bool AlwaysInline,
4373 bool isTailCall, MachinePointerInfo DstPtrInfo,
4374 MachinePointerInfo SrcPtrInfo) {
4375 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4377 // Check to see if we should lower the memcpy to loads and stores first.
4378 // For cases within the target-specified limits, this is the best choice.
4379 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4381 // Memcpy with size zero? Just return the original chain.
4382 if (ConstantSize->isNullValue())
4385 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4386 ConstantSize->getZExtValue(),Align,
4387 isVol, false, DstPtrInfo, SrcPtrInfo);
4388 if (Result.getNode())
4392 // Then check to see if we should lower the memcpy with target-specific
4393 // code. If the target chooses to do this, this is the next best.
4395 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4396 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4397 DstPtrInfo, SrcPtrInfo);
4398 if (Result.getNode())
4402 // If we really need inline code and the target declined to provide it,
4403 // use a (potentially long) sequence of loads and stores.
4405 assert(ConstantSize && "AlwaysInline requires a constant size!");
4406 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4407 ConstantSize->getZExtValue(), Align, isVol,
4408 true, DstPtrInfo, SrcPtrInfo);
4411 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4412 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4413 // respect volatile, so they may do things like read or write memory
4414 // beyond the given memory regions. But fixing this isn't easy, and most
4415 // people don't care.
4417 // Emit a library call.
4418 TargetLowering::ArgListTy Args;
4419 TargetLowering::ArgListEntry Entry;
4420 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4421 Entry.Node = Dst; Args.push_back(Entry);
4422 Entry.Node = Src; Args.push_back(Entry);
4423 Entry.Node = Size; Args.push_back(Entry);
4424 // FIXME: pass in SDLoc
4425 TargetLowering::CallLoweringInfo CLI(*this);
4426 CLI.setDebugLoc(dl).setChain(Chain)
4427 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4428 Type::getVoidTy(*getContext()),
4429 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4430 TLI->getPointerTy()), std::move(Args), 0)
4432 .setTailCall(isTailCall);
4434 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4435 return CallResult.second;
4438 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4439 SDValue Src, SDValue Size,
4440 unsigned Align, bool isVol, bool isTailCall,
4441 MachinePointerInfo DstPtrInfo,
4442 MachinePointerInfo SrcPtrInfo) {
4443 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4445 // Check to see if we should lower the memmove to loads and stores first.
4446 // For cases within the target-specified limits, this is the best choice.
4447 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4449 // Memmove with size zero? Just return the original chain.
4450 if (ConstantSize->isNullValue())
4454 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4455 ConstantSize->getZExtValue(), Align, isVol,
4456 false, DstPtrInfo, SrcPtrInfo);
4457 if (Result.getNode())
4461 // Then check to see if we should lower the memmove with target-specific
4462 // code. If the target chooses to do this, this is the next best.
4464 SDValue Result = TSI->EmitTargetCodeForMemmove(
4465 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4466 if (Result.getNode())
4470 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4471 // not be safe. See memcpy above for more details.
4473 // Emit a library call.
4474 TargetLowering::ArgListTy Args;
4475 TargetLowering::ArgListEntry Entry;
4476 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4477 Entry.Node = Dst; Args.push_back(Entry);
4478 Entry.Node = Src; Args.push_back(Entry);
4479 Entry.Node = Size; Args.push_back(Entry);
4480 // FIXME: pass in SDLoc
4481 TargetLowering::CallLoweringInfo CLI(*this);
4482 CLI.setDebugLoc(dl).setChain(Chain)
4483 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4484 Type::getVoidTy(*getContext()),
4485 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4486 TLI->getPointerTy()), std::move(Args), 0)
4488 .setTailCall(isTailCall);
4490 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4491 return CallResult.second;
4494 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4495 SDValue Src, SDValue Size,
4496 unsigned Align, bool isVol, bool isTailCall,
4497 MachinePointerInfo DstPtrInfo) {
4498 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4500 // Check to see if we should lower the memset to stores first.
4501 // For cases within the target-specified limits, this is the best choice.
4502 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4504 // Memset with size zero? Just return the original chain.
4505 if (ConstantSize->isNullValue())
4509 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4510 Align, isVol, DstPtrInfo);
4512 if (Result.getNode())
4516 // Then check to see if we should lower the memset with target-specific
4517 // code. If the target chooses to do this, this is the next best.
4519 SDValue Result = TSI->EmitTargetCodeForMemset(
4520 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4521 if (Result.getNode())
4525 // Emit a library call.
4526 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4527 TargetLowering::ArgListTy Args;
4528 TargetLowering::ArgListEntry Entry;
4529 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4530 Args.push_back(Entry);
4532 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4533 Args.push_back(Entry);
4535 Entry.Ty = IntPtrTy;
4536 Args.push_back(Entry);
4538 // FIXME: pass in SDLoc
4539 TargetLowering::CallLoweringInfo CLI(*this);
4540 CLI.setDebugLoc(dl).setChain(Chain)
4541 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4542 Type::getVoidTy(*getContext()),
4543 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4544 TLI->getPointerTy()), std::move(Args), 0)
4546 .setTailCall(isTailCall);
4548 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4549 return CallResult.second;
4552 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4553 SDVTList VTList, ArrayRef<SDValue> Ops,
4554 MachineMemOperand *MMO,
4555 AtomicOrdering SuccessOrdering,
4556 AtomicOrdering FailureOrdering,
4557 SynchronizationScope SynchScope) {
4558 FoldingSetNodeID ID;
4559 ID.AddInteger(MemVT.getRawBits());
4560 AddNodeIDNode(ID, Opcode, VTList, Ops);
4561 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4563 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4564 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4565 return SDValue(E, 0);
4568 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4569 // SDNode doesn't have access to it. This memory will be "leaked" when
4570 // the node is deallocated, but recovered when the allocator is released.
4571 // If the number of operands is less than 5 we use AtomicSDNode's internal
4573 unsigned NumOps = Ops.size();
4574 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4577 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4578 dl.getDebugLoc(), VTList, MemVT,
4579 Ops.data(), DynOps, NumOps, MMO,
4580 SuccessOrdering, FailureOrdering,
4582 CSEMap.InsertNode(N, IP);
4584 return SDValue(N, 0);
4587 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4588 SDVTList VTList, ArrayRef<SDValue> Ops,
4589 MachineMemOperand *MMO,
4590 AtomicOrdering Ordering,
4591 SynchronizationScope SynchScope) {
4592 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4593 Ordering, SynchScope);
4596 SDValue SelectionDAG::getAtomicCmpSwap(
4597 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4598 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4599 unsigned Alignment, AtomicOrdering SuccessOrdering,
4600 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4601 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4602 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4603 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4605 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4606 Alignment = getEVTAlignment(MemVT);
4608 MachineFunction &MF = getMachineFunction();
4610 // FIXME: Volatile isn't really correct; we should keep track of atomic
4611 // orderings in the memoperand.
4612 unsigned Flags = MachineMemOperand::MOVolatile;
4613 Flags |= MachineMemOperand::MOLoad;
4614 Flags |= MachineMemOperand::MOStore;
4616 MachineMemOperand *MMO =
4617 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4619 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4620 SuccessOrdering, FailureOrdering, SynchScope);
4623 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4624 SDVTList VTs, SDValue Chain, SDValue Ptr,
4625 SDValue Cmp, SDValue Swp,
4626 MachineMemOperand *MMO,
4627 AtomicOrdering SuccessOrdering,
4628 AtomicOrdering FailureOrdering,
4629 SynchronizationScope SynchScope) {
4630 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4631 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4632 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4634 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4635 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4636 SuccessOrdering, FailureOrdering, SynchScope);
4639 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4641 SDValue Ptr, SDValue Val,
4642 const Value* PtrVal,
4644 AtomicOrdering Ordering,
4645 SynchronizationScope SynchScope) {
4646 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4647 Alignment = getEVTAlignment(MemVT);
4649 MachineFunction &MF = getMachineFunction();
4650 // An atomic store does not load. An atomic load does not store.
4651 // (An atomicrmw obviously both loads and stores.)
4652 // For now, atomics are considered to be volatile always, and they are
4654 // FIXME: Volatile isn't really correct; we should keep track of atomic
4655 // orderings in the memoperand.
4656 unsigned Flags = MachineMemOperand::MOVolatile;
4657 if (Opcode != ISD::ATOMIC_STORE)
4658 Flags |= MachineMemOperand::MOLoad;
4659 if (Opcode != ISD::ATOMIC_LOAD)
4660 Flags |= MachineMemOperand::MOStore;
4662 MachineMemOperand *MMO =
4663 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4664 MemVT.getStoreSize(), Alignment);
4666 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4667 Ordering, SynchScope);
4670 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4672 SDValue Ptr, SDValue Val,
4673 MachineMemOperand *MMO,
4674 AtomicOrdering Ordering,
4675 SynchronizationScope SynchScope) {
4676 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4677 Opcode == ISD::ATOMIC_LOAD_SUB ||
4678 Opcode == ISD::ATOMIC_LOAD_AND ||
4679 Opcode == ISD::ATOMIC_LOAD_OR ||
4680 Opcode == ISD::ATOMIC_LOAD_XOR ||
4681 Opcode == ISD::ATOMIC_LOAD_NAND ||
4682 Opcode == ISD::ATOMIC_LOAD_MIN ||
4683 Opcode == ISD::ATOMIC_LOAD_MAX ||
4684 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4685 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4686 Opcode == ISD::ATOMIC_SWAP ||
4687 Opcode == ISD::ATOMIC_STORE) &&
4688 "Invalid Atomic Op");
4690 EVT VT = Val.getValueType();
4692 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4693 getVTList(VT, MVT::Other);
4694 SDValue Ops[] = {Chain, Ptr, Val};
4695 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4698 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4699 EVT VT, SDValue Chain,
4701 MachineMemOperand *MMO,
4702 AtomicOrdering Ordering,
4703 SynchronizationScope SynchScope) {
4704 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4706 SDVTList VTs = getVTList(VT, MVT::Other);
4707 SDValue Ops[] = {Chain, Ptr};
4708 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4711 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4712 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4713 if (Ops.size() == 1)
4716 SmallVector<EVT, 4> VTs;
4717 VTs.reserve(Ops.size());
4718 for (unsigned i = 0; i < Ops.size(); ++i)
4719 VTs.push_back(Ops[i].getValueType());
4720 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4724 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4725 ArrayRef<SDValue> Ops,
4726 EVT MemVT, MachinePointerInfo PtrInfo,
4727 unsigned Align, bool Vol,
4728 bool ReadMem, bool WriteMem, unsigned Size) {
4729 if (Align == 0) // Ensure that codegen never sees alignment 0
4730 Align = getEVTAlignment(MemVT);
4732 MachineFunction &MF = getMachineFunction();
4735 Flags |= MachineMemOperand::MOStore;
4737 Flags |= MachineMemOperand::MOLoad;
4739 Flags |= MachineMemOperand::MOVolatile;
4741 Size = MemVT.getStoreSize();
4742 MachineMemOperand *MMO =
4743 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4745 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4749 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4750 ArrayRef<SDValue> Ops, EVT MemVT,
4751 MachineMemOperand *MMO) {
4752 assert((Opcode == ISD::INTRINSIC_VOID ||
4753 Opcode == ISD::INTRINSIC_W_CHAIN ||
4754 Opcode == ISD::PREFETCH ||
4755 Opcode == ISD::LIFETIME_START ||
4756 Opcode == ISD::LIFETIME_END ||
4757 (Opcode <= INT_MAX &&
4758 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4759 "Opcode is not a memory-accessing opcode!");
4761 // Memoize the node unless it returns a flag.
4762 MemIntrinsicSDNode *N;
4763 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4764 FoldingSetNodeID ID;
4765 AddNodeIDNode(ID, Opcode, VTList, Ops);
4766 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4768 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4769 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4770 return SDValue(E, 0);
4773 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4774 dl.getDebugLoc(), VTList, Ops,
4776 CSEMap.InsertNode(N, IP);
4778 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4779 dl.getDebugLoc(), VTList, Ops,
4783 return SDValue(N, 0);
4786 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4787 /// MachinePointerInfo record from it. This is particularly useful because the
4788 /// code generator has many cases where it doesn't bother passing in a
4789 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4790 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4791 // If this is FI+Offset, we can model it.
4792 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4793 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4795 // If this is (FI+Offset1)+Offset2, we can model it.
4796 if (Ptr.getOpcode() != ISD::ADD ||
4797 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4798 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4799 return MachinePointerInfo();
4801 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4802 return MachinePointerInfo::getFixedStack(FI, Offset+
4803 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4806 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4807 /// MachinePointerInfo record from it. This is particularly useful because the
4808 /// code generator has many cases where it doesn't bother passing in a
4809 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4810 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4811 // If the 'Offset' value isn't a constant, we can't handle this.
4812 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4813 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4814 if (OffsetOp.getOpcode() == ISD::UNDEF)
4815 return InferPointerInfo(Ptr);
4816 return MachinePointerInfo();
4821 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4822 EVT VT, SDLoc dl, SDValue Chain,
4823 SDValue Ptr, SDValue Offset,
4824 MachinePointerInfo PtrInfo, EVT MemVT,
4825 bool isVolatile, bool isNonTemporal, bool isInvariant,
4826 unsigned Alignment, const AAMDNodes &AAInfo,
4827 const MDNode *Ranges) {
4828 assert(Chain.getValueType() == MVT::Other &&
4829 "Invalid chain type");
4830 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4831 Alignment = getEVTAlignment(VT);
4833 unsigned Flags = MachineMemOperand::MOLoad;
4835 Flags |= MachineMemOperand::MOVolatile;
4837 Flags |= MachineMemOperand::MONonTemporal;
4839 Flags |= MachineMemOperand::MOInvariant;
4841 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4843 if (PtrInfo.V.isNull())
4844 PtrInfo = InferPointerInfo(Ptr, Offset);
4846 MachineFunction &MF = getMachineFunction();
4847 MachineMemOperand *MMO =
4848 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4850 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4854 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4855 EVT VT, SDLoc dl, SDValue Chain,
4856 SDValue Ptr, SDValue Offset, EVT MemVT,
4857 MachineMemOperand *MMO) {
4859 ExtType = ISD::NON_EXTLOAD;
4860 } else if (ExtType == ISD::NON_EXTLOAD) {
4861 assert(VT == MemVT && "Non-extending load from different memory type!");
4864 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4865 "Should only be an extending load, not truncating!");
4866 assert(VT.isInteger() == MemVT.isInteger() &&
4867 "Cannot convert from FP to Int or Int -> FP!");
4868 assert(VT.isVector() == MemVT.isVector() &&
4869 "Cannot use an ext load to convert to or from a vector!");
4870 assert((!VT.isVector() ||
4871 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4872 "Cannot use an ext load to change the number of vector elements!");
4875 bool Indexed = AM != ISD::UNINDEXED;
4876 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4877 "Unindexed load with an offset!");
4879 SDVTList VTs = Indexed ?
4880 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4881 SDValue Ops[] = { Chain, Ptr, Offset };
4882 FoldingSetNodeID ID;
4883 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4884 ID.AddInteger(MemVT.getRawBits());
4885 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4886 MMO->isNonTemporal(),
4887 MMO->isInvariant()));
4888 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4890 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4891 cast<LoadSDNode>(E)->refineAlignment(MMO);
4892 return SDValue(E, 0);
4894 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4895 dl.getDebugLoc(), VTs, AM, ExtType,
4897 CSEMap.InsertNode(N, IP);
4899 return SDValue(N, 0);
4902 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4903 SDValue Chain, SDValue Ptr,
4904 MachinePointerInfo PtrInfo,
4905 bool isVolatile, bool isNonTemporal,
4906 bool isInvariant, unsigned Alignment,
4907 const AAMDNodes &AAInfo,
4908 const MDNode *Ranges) {
4909 SDValue Undef = getUNDEF(Ptr.getValueType());
4910 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4911 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4915 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4916 SDValue Chain, SDValue Ptr,
4917 MachineMemOperand *MMO) {
4918 SDValue Undef = getUNDEF(Ptr.getValueType());
4919 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4923 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4924 SDValue Chain, SDValue Ptr,
4925 MachinePointerInfo PtrInfo, EVT MemVT,
4926 bool isVolatile, bool isNonTemporal,
4927 bool isInvariant, unsigned Alignment,
4928 const AAMDNodes &AAInfo) {
4929 SDValue Undef = getUNDEF(Ptr.getValueType());
4930 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4931 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4936 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4937 SDValue Chain, SDValue Ptr, EVT MemVT,
4938 MachineMemOperand *MMO) {
4939 SDValue Undef = getUNDEF(Ptr.getValueType());
4940 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4945 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4946 SDValue Offset, ISD::MemIndexedMode AM) {
4947 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4948 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4949 "Load is already a indexed load!");
4950 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4951 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4952 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4953 false, LD->getAlignment());
4956 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4957 SDValue Ptr, MachinePointerInfo PtrInfo,
4958 bool isVolatile, bool isNonTemporal,
4959 unsigned Alignment, const AAMDNodes &AAInfo) {
4960 assert(Chain.getValueType() == MVT::Other &&
4961 "Invalid chain type");
4962 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4963 Alignment = getEVTAlignment(Val.getValueType());
4965 unsigned Flags = MachineMemOperand::MOStore;
4967 Flags |= MachineMemOperand::MOVolatile;
4969 Flags |= MachineMemOperand::MONonTemporal;
4971 if (PtrInfo.V.isNull())
4972 PtrInfo = InferPointerInfo(Ptr);
4974 MachineFunction &MF = getMachineFunction();
4975 MachineMemOperand *MMO =
4976 MF.getMachineMemOperand(PtrInfo, Flags,
4977 Val.getValueType().getStoreSize(), Alignment,
4980 return getStore(Chain, dl, Val, Ptr, MMO);
4983 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4984 SDValue Ptr, MachineMemOperand *MMO) {
4985 assert(Chain.getValueType() == MVT::Other &&
4986 "Invalid chain type");
4987 EVT VT = Val.getValueType();
4988 SDVTList VTs = getVTList(MVT::Other);
4989 SDValue Undef = getUNDEF(Ptr.getValueType());
4990 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4991 FoldingSetNodeID ID;
4992 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4993 ID.AddInteger(VT.getRawBits());
4994 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4995 MMO->isNonTemporal(), MMO->isInvariant()));
4996 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4998 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4999 cast<StoreSDNode>(E)->refineAlignment(MMO);
5000 return SDValue(E, 0);
5002 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5003 dl.getDebugLoc(), VTs,
5004 ISD::UNINDEXED, false, VT, MMO);
5005 CSEMap.InsertNode(N, IP);
5007 return SDValue(N, 0);
5010 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5011 SDValue Ptr, MachinePointerInfo PtrInfo,
5012 EVT SVT,bool isVolatile, bool isNonTemporal,
5014 const AAMDNodes &AAInfo) {
5015 assert(Chain.getValueType() == MVT::Other &&
5016 "Invalid chain type");
5017 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5018 Alignment = getEVTAlignment(SVT);
5020 unsigned Flags = MachineMemOperand::MOStore;
5022 Flags |= MachineMemOperand::MOVolatile;
5024 Flags |= MachineMemOperand::MONonTemporal;
5026 if (PtrInfo.V.isNull())
5027 PtrInfo = InferPointerInfo(Ptr);
5029 MachineFunction &MF = getMachineFunction();
5030 MachineMemOperand *MMO =
5031 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5034 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5037 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5038 SDValue Ptr, EVT SVT,
5039 MachineMemOperand *MMO) {
5040 EVT VT = Val.getValueType();
5042 assert(Chain.getValueType() == MVT::Other &&
5043 "Invalid chain type");
5045 return getStore(Chain, dl, Val, Ptr, MMO);
5047 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5048 "Should only be a truncating store, not extending!");
5049 assert(VT.isInteger() == SVT.isInteger() &&
5050 "Can't do FP-INT conversion!");
5051 assert(VT.isVector() == SVT.isVector() &&
5052 "Cannot use trunc store to convert to or from a vector!");
5053 assert((!VT.isVector() ||
5054 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5055 "Cannot use trunc store to change the number of vector elements!");
5057 SDVTList VTs = getVTList(MVT::Other);
5058 SDValue Undef = getUNDEF(Ptr.getValueType());
5059 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5060 FoldingSetNodeID ID;
5061 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5062 ID.AddInteger(SVT.getRawBits());
5063 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5064 MMO->isNonTemporal(), MMO->isInvariant()));
5065 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5067 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5068 cast<StoreSDNode>(E)->refineAlignment(MMO);
5069 return SDValue(E, 0);
5071 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5072 dl.getDebugLoc(), VTs,
5073 ISD::UNINDEXED, true, SVT, MMO);
5074 CSEMap.InsertNode(N, IP);
5076 return SDValue(N, 0);
5080 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5081 SDValue Offset, ISD::MemIndexedMode AM) {
5082 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5083 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5084 "Store is already a indexed store!");
5085 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5086 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5087 FoldingSetNodeID ID;
5088 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5089 ID.AddInteger(ST->getMemoryVT().getRawBits());
5090 ID.AddInteger(ST->getRawSubclassData());
5091 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5093 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5094 return SDValue(E, 0);
5096 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5097 dl.getDebugLoc(), VTs, AM,
5098 ST->isTruncatingStore(),
5100 ST->getMemOperand());
5101 CSEMap.InsertNode(N, IP);
5103 return SDValue(N, 0);
5107 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5108 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5109 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5111 SDVTList VTs = getVTList(VT, MVT::Other);
5112 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5113 FoldingSetNodeID ID;
5114 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5115 ID.AddInteger(VT.getRawBits());
5116 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5118 MMO->isNonTemporal(),
5119 MMO->isInvariant()));
5120 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5122 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5123 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5124 return SDValue(E, 0);
5126 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5127 dl.getDebugLoc(), Ops, 4, VTs,
5129 CSEMap.InsertNode(N, IP);
5131 return SDValue(N, 0);
5134 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5135 SDValue Ptr, SDValue Mask, EVT MemVT,
5136 MachineMemOperand *MMO, bool isTrunc) {
5137 assert(Chain.getValueType() == MVT::Other &&
5138 "Invalid chain type");
5139 EVT VT = Val.getValueType();
5140 SDVTList VTs = getVTList(MVT::Other);
5141 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5142 FoldingSetNodeID ID;
5143 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5144 ID.AddInteger(VT.getRawBits());
5145 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5146 MMO->isNonTemporal(), MMO->isInvariant()));
5147 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5149 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5150 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5151 return SDValue(E, 0);
5153 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5154 dl.getDebugLoc(), Ops, 4,
5155 VTs, isTrunc, MemVT, MMO);
5156 CSEMap.InsertNode(N, IP);
5158 return SDValue(N, 0);
5162 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5163 ArrayRef<SDValue> Ops,
5164 MachineMemOperand *MMO) {
5166 FoldingSetNodeID ID;
5167 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5168 ID.AddInteger(VT.getRawBits());
5169 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5171 MMO->isNonTemporal(),
5172 MMO->isInvariant()));
5173 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5175 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5176 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5177 return SDValue(E, 0);
5179 MaskedGatherSDNode *N =
5180 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5182 CSEMap.InsertNode(N, IP);
5184 return SDValue(N, 0);
5187 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5188 ArrayRef<SDValue> Ops,
5189 MachineMemOperand *MMO) {
5190 FoldingSetNodeID ID;
5191 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5192 ID.AddInteger(VT.getRawBits());
5193 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5194 MMO->isNonTemporal(),
5195 MMO->isInvariant()));
5196 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5198 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5199 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5200 return SDValue(E, 0);
5203 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5205 CSEMap.InsertNode(N, IP);
5207 return SDValue(N, 0);
5210 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5211 SDValue Chain, SDValue Ptr,
5214 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5215 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5218 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5219 ArrayRef<SDUse> Ops) {
5220 switch (Ops.size()) {
5221 case 0: return getNode(Opcode, DL, VT);
5222 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5223 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5224 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5228 // Copy from an SDUse array into an SDValue array for use with
5229 // the regular getNode logic.
5230 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5231 return getNode(Opcode, DL, VT, NewOps);
5234 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5235 ArrayRef<SDValue> Ops) {
5236 unsigned NumOps = Ops.size();
5238 case 0: return getNode(Opcode, DL, VT);
5239 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5240 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5241 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5247 case ISD::SELECT_CC: {
5248 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5249 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5250 "LHS and RHS of condition must have same type!");
5251 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5252 "True and False arms of SelectCC must have same type!");
5253 assert(Ops[2].getValueType() == VT &&
5254 "select_cc node must be of same type as true and false value!");
5258 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5259 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5260 "LHS/RHS of comparison should match types!");
5267 SDVTList VTs = getVTList(VT);
5269 if (VT != MVT::Glue) {
5270 FoldingSetNodeID ID;
5271 AddNodeIDNode(ID, Opcode, VTs, Ops);
5274 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5275 return SDValue(E, 0);
5277 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5279 CSEMap.InsertNode(N, IP);
5281 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5286 return SDValue(N, 0);
5289 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5290 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5291 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5294 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5295 ArrayRef<SDValue> Ops) {
5296 if (VTList.NumVTs == 1)
5297 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5301 // FIXME: figure out how to safely handle things like
5302 // int foo(int x) { return 1 << (x & 255); }
5303 // int bar() { return foo(256); }
5304 case ISD::SRA_PARTS:
5305 case ISD::SRL_PARTS:
5306 case ISD::SHL_PARTS:
5307 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5308 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5309 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5310 else if (N3.getOpcode() == ISD::AND)
5311 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5312 // If the and is only masking out bits that cannot effect the shift,
5313 // eliminate the and.
5314 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5315 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5316 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5322 // Memoize the node unless it returns a flag.
5324 unsigned NumOps = Ops.size();
5325 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5326 FoldingSetNodeID ID;
5327 AddNodeIDNode(ID, Opcode, VTList, Ops);
5329 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5330 return SDValue(E, 0);
5333 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5334 DL.getDebugLoc(), VTList, Ops[0]);
5335 } else if (NumOps == 2) {
5336 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5337 DL.getDebugLoc(), VTList, Ops[0],
5339 } else if (NumOps == 3) {
5340 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5341 DL.getDebugLoc(), VTList, Ops[0],
5344 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5347 CSEMap.InsertNode(N, IP);
5350 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5351 DL.getDebugLoc(), VTList, Ops[0]);
5352 } else if (NumOps == 2) {
5353 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5354 DL.getDebugLoc(), VTList, Ops[0],
5356 } else if (NumOps == 3) {
5357 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5358 DL.getDebugLoc(), VTList, Ops[0],
5361 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5366 return SDValue(N, 0);
5369 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5370 return getNode(Opcode, DL, VTList, None);
5373 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5375 SDValue Ops[] = { N1 };
5376 return getNode(Opcode, DL, VTList, Ops);
5379 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5380 SDValue N1, SDValue N2) {
5381 SDValue Ops[] = { N1, N2 };
5382 return getNode(Opcode, DL, VTList, Ops);
5385 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5386 SDValue N1, SDValue N2, SDValue N3) {
5387 SDValue Ops[] = { N1, N2, N3 };
5388 return getNode(Opcode, DL, VTList, Ops);
5391 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5392 SDValue N1, SDValue N2, SDValue N3,
5394 SDValue Ops[] = { N1, N2, N3, N4 };
5395 return getNode(Opcode, DL, VTList, Ops);
5398 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5399 SDValue N1, SDValue N2, SDValue N3,
5400 SDValue N4, SDValue N5) {
5401 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5402 return getNode(Opcode, DL, VTList, Ops);
5405 SDVTList SelectionDAG::getVTList(EVT VT) {
5406 return makeVTList(SDNode::getValueTypeList(VT), 1);
5409 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5410 FoldingSetNodeID ID;
5412 ID.AddInteger(VT1.getRawBits());
5413 ID.AddInteger(VT2.getRawBits());
5416 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5418 EVT *Array = Allocator.Allocate<EVT>(2);
5421 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5422 VTListMap.InsertNode(Result, IP);
5424 return Result->getSDVTList();
5427 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5428 FoldingSetNodeID ID;
5430 ID.AddInteger(VT1.getRawBits());
5431 ID.AddInteger(VT2.getRawBits());
5432 ID.AddInteger(VT3.getRawBits());
5435 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5437 EVT *Array = Allocator.Allocate<EVT>(3);
5441 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5442 VTListMap.InsertNode(Result, IP);
5444 return Result->getSDVTList();
5447 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5448 FoldingSetNodeID ID;
5450 ID.AddInteger(VT1.getRawBits());
5451 ID.AddInteger(VT2.getRawBits());
5452 ID.AddInteger(VT3.getRawBits());
5453 ID.AddInteger(VT4.getRawBits());
5456 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5458 EVT *Array = Allocator.Allocate<EVT>(4);
5463 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5464 VTListMap.InsertNode(Result, IP);
5466 return Result->getSDVTList();
5469 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5470 unsigned NumVTs = VTs.size();
5471 FoldingSetNodeID ID;
5472 ID.AddInteger(NumVTs);
5473 for (unsigned index = 0; index < NumVTs; index++) {
5474 ID.AddInteger(VTs[index].getRawBits());
5478 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5480 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5481 std::copy(VTs.begin(), VTs.end(), Array);
5482 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5483 VTListMap.InsertNode(Result, IP);
5485 return Result->getSDVTList();
5489 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5490 /// specified operands. If the resultant node already exists in the DAG,
5491 /// this does not modify the specified node, instead it returns the node that
5492 /// already exists. If the resultant node does not exist in the DAG, the
5493 /// input node is returned. As a degenerate case, if you specify the same
5494 /// input operands as the node already has, the input node is returned.
5495 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5496 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5498 // Check to see if there is no change.
5499 if (Op == N->getOperand(0)) return N;
5501 // See if the modified node already exists.
5502 void *InsertPos = nullptr;
5503 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5506 // Nope it doesn't. Remove the node from its current place in the maps.
5508 if (!RemoveNodeFromCSEMaps(N))
5509 InsertPos = nullptr;
5511 // Now we update the operands.
5512 N->OperandList[0].set(Op);
5514 // If this gets put into a CSE map, add it.
5515 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5519 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5520 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5522 // Check to see if there is no change.
5523 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5524 return N; // No operands changed, just return the input node.
5526 // See if the modified node already exists.
5527 void *InsertPos = nullptr;
5528 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5531 // Nope it doesn't. Remove the node from its current place in the maps.
5533 if (!RemoveNodeFromCSEMaps(N))
5534 InsertPos = nullptr;
5536 // Now we update the operands.
5537 if (N->OperandList[0] != Op1)
5538 N->OperandList[0].set(Op1);
5539 if (N->OperandList[1] != Op2)
5540 N->OperandList[1].set(Op2);
5542 // If this gets put into a CSE map, add it.
5543 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5547 SDNode *SelectionDAG::
5548 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5549 SDValue Ops[] = { Op1, Op2, Op3 };
5550 return UpdateNodeOperands(N, Ops);
5553 SDNode *SelectionDAG::
5554 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5555 SDValue Op3, SDValue Op4) {
5556 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5557 return UpdateNodeOperands(N, Ops);
5560 SDNode *SelectionDAG::
5561 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5562 SDValue Op3, SDValue Op4, SDValue Op5) {
5563 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5564 return UpdateNodeOperands(N, Ops);
5567 SDNode *SelectionDAG::
5568 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5569 unsigned NumOps = Ops.size();
5570 assert(N->getNumOperands() == NumOps &&
5571 "Update with wrong number of operands");
5573 // If no operands changed just return the input node.
5574 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5577 // See if the modified node already exists.
5578 void *InsertPos = nullptr;
5579 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5582 // Nope it doesn't. Remove the node from its current place in the maps.
5584 if (!RemoveNodeFromCSEMaps(N))
5585 InsertPos = nullptr;
5587 // Now we update the operands.
5588 for (unsigned i = 0; i != NumOps; ++i)
5589 if (N->OperandList[i] != Ops[i])
5590 N->OperandList[i].set(Ops[i]);
5592 // If this gets put into a CSE map, add it.
5593 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5597 /// DropOperands - Release the operands and set this node to have
5599 void SDNode::DropOperands() {
5600 // Unlike the code in MorphNodeTo that does this, we don't need to
5601 // watch for dead nodes here.
5602 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5608 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5611 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5613 SDVTList VTs = getVTList(VT);
5614 return SelectNodeTo(N, MachineOpc, VTs, None);
5617 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5618 EVT VT, SDValue Op1) {
5619 SDVTList VTs = getVTList(VT);
5620 SDValue Ops[] = { Op1 };
5621 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5624 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5625 EVT VT, SDValue Op1,
5627 SDVTList VTs = getVTList(VT);
5628 SDValue Ops[] = { Op1, Op2 };
5629 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5632 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5633 EVT VT, SDValue Op1,
5634 SDValue Op2, SDValue Op3) {
5635 SDVTList VTs = getVTList(VT);
5636 SDValue Ops[] = { Op1, Op2, Op3 };
5637 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5640 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5641 EVT VT, ArrayRef<SDValue> Ops) {
5642 SDVTList VTs = getVTList(VT);
5643 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5646 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5647 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5648 SDVTList VTs = getVTList(VT1, VT2);
5649 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5652 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5654 SDVTList VTs = getVTList(VT1, VT2);
5655 return SelectNodeTo(N, MachineOpc, VTs, None);
5658 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5659 EVT VT1, EVT VT2, EVT VT3,
5660 ArrayRef<SDValue> Ops) {
5661 SDVTList VTs = getVTList(VT1, VT2, VT3);
5662 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5665 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5666 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5667 ArrayRef<SDValue> Ops) {
5668 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5669 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5672 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5675 SDVTList VTs = getVTList(VT1, VT2);
5676 SDValue Ops[] = { Op1 };
5677 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5680 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5682 SDValue Op1, SDValue Op2) {
5683 SDVTList VTs = getVTList(VT1, VT2);
5684 SDValue Ops[] = { Op1, Op2 };
5685 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5688 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5690 SDValue Op1, SDValue Op2,
5692 SDVTList VTs = getVTList(VT1, VT2);
5693 SDValue Ops[] = { Op1, Op2, Op3 };
5694 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698 EVT VT1, EVT VT2, EVT VT3,
5699 SDValue Op1, SDValue Op2,
5701 SDVTList VTs = getVTList(VT1, VT2, VT3);
5702 SDValue Ops[] = { Op1, Op2, Op3 };
5703 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5706 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5707 SDVTList VTs,ArrayRef<SDValue> Ops) {
5708 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5709 // Reset the NodeID to -1.
5714 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5715 /// the line number information on the merged node since it is not possible to
5716 /// preserve the information that operation is associated with multiple lines.
5717 /// This will make the debugger working better at -O0, were there is a higher
5718 /// probability having other instructions associated with that line.
5720 /// For IROrder, we keep the smaller of the two
5721 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5722 DebugLoc NLoc = N->getDebugLoc();
5723 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5724 N->setDebugLoc(DebugLoc());
5726 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5727 N->setIROrder(Order);
5731 /// MorphNodeTo - This *mutates* the specified node to have the specified
5732 /// return type, opcode, and operands.
5734 /// Note that MorphNodeTo returns the resultant node. If there is already a
5735 /// node of the specified opcode and operands, it returns that node instead of
5736 /// the current one. Note that the SDLoc need not be the same.
5738 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5739 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5740 /// node, and because it doesn't require CSE recalculation for any of
5741 /// the node's users.
5743 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5744 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5745 /// the legalizer which maintain worklists that would need to be updated when
5746 /// deleting things.
5747 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5748 SDVTList VTs, ArrayRef<SDValue> Ops) {
5749 unsigned NumOps = Ops.size();
5750 // If an identical node already exists, use it.
5752 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5753 FoldingSetNodeID ID;
5754 AddNodeIDNode(ID, Opc, VTs, Ops);
5755 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5756 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5759 if (!RemoveNodeFromCSEMaps(N))
5762 // Start the morphing.
5764 N->ValueList = VTs.VTs;
5765 N->NumValues = VTs.NumVTs;
5767 // Clear the operands list, updating used nodes to remove this from their
5768 // use list. Keep track of any operands that become dead as a result.
5769 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5770 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5772 SDNode *Used = Use.getNode();
5774 if (Used->use_empty())
5775 DeadNodeSet.insert(Used);
5778 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5779 // Initialize the memory references information.
5780 MN->setMemRefs(nullptr, nullptr);
5781 // If NumOps is larger than the # of operands we can have in a
5782 // MachineSDNode, reallocate the operand list.
5783 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5784 if (MN->OperandsNeedDelete)
5785 delete[] MN->OperandList;
5786 if (NumOps > array_lengthof(MN->LocalOperands))
5787 // We're creating a final node that will live unmorphed for the
5788 // remainder of the current SelectionDAG iteration, so we can allocate
5789 // the operands directly out of a pool with no recycling metadata.
5790 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5791 Ops.data(), NumOps);
5793 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5794 MN->OperandsNeedDelete = false;
5796 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5798 // If NumOps is larger than the # of operands we currently have, reallocate
5799 // the operand list.
5800 if (NumOps > N->NumOperands) {
5801 if (N->OperandsNeedDelete)
5802 delete[] N->OperandList;
5803 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5804 N->OperandsNeedDelete = true;
5806 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5809 // Delete any nodes that are still dead after adding the uses for the
5811 if (!DeadNodeSet.empty()) {
5812 SmallVector<SDNode *, 16> DeadNodes;
5813 for (SDNode *N : DeadNodeSet)
5815 DeadNodes.push_back(N);
5816 RemoveDeadNodes(DeadNodes);
5820 CSEMap.InsertNode(N, IP); // Memoize the new node.
5825 /// getMachineNode - These are used for target selectors to create a new node
5826 /// with specified return type(s), MachineInstr opcode, and operands.
5828 /// Note that getMachineNode returns the resultant node. If there is already a
5829 /// node of the specified opcode and operands, it returns that node instead of
5830 /// the current one.
5832 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5833 SDVTList VTs = getVTList(VT);
5834 return getMachineNode(Opcode, dl, VTs, None);
5838 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5839 SDVTList VTs = getVTList(VT);
5840 SDValue Ops[] = { Op1 };
5841 return getMachineNode(Opcode, dl, VTs, Ops);
5845 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5846 SDValue Op1, SDValue Op2) {
5847 SDVTList VTs = getVTList(VT);
5848 SDValue Ops[] = { Op1, Op2 };
5849 return getMachineNode(Opcode, dl, VTs, Ops);
5853 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5854 SDValue Op1, SDValue Op2, SDValue Op3) {
5855 SDVTList VTs = getVTList(VT);
5856 SDValue Ops[] = { Op1, Op2, Op3 };
5857 return getMachineNode(Opcode, dl, VTs, Ops);
5861 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5862 ArrayRef<SDValue> Ops) {
5863 SDVTList VTs = getVTList(VT);
5864 return getMachineNode(Opcode, dl, VTs, Ops);
5868 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5869 SDVTList VTs = getVTList(VT1, VT2);
5870 return getMachineNode(Opcode, dl, VTs, None);
5874 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5875 EVT VT1, EVT VT2, SDValue Op1) {
5876 SDVTList VTs = getVTList(VT1, VT2);
5877 SDValue Ops[] = { Op1 };
5878 return getMachineNode(Opcode, dl, VTs, Ops);
5882 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5883 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5884 SDVTList VTs = getVTList(VT1, VT2);
5885 SDValue Ops[] = { Op1, Op2 };
5886 return getMachineNode(Opcode, dl, VTs, Ops);
5890 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5891 EVT VT1, EVT VT2, SDValue Op1,
5892 SDValue Op2, SDValue Op3) {
5893 SDVTList VTs = getVTList(VT1, VT2);
5894 SDValue Ops[] = { Op1, Op2, Op3 };
5895 return getMachineNode(Opcode, dl, VTs, Ops);
5899 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5901 ArrayRef<SDValue> Ops) {
5902 SDVTList VTs = getVTList(VT1, VT2);
5903 return getMachineNode(Opcode, dl, VTs, Ops);
5907 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5908 EVT VT1, EVT VT2, EVT VT3,
5909 SDValue Op1, SDValue Op2) {
5910 SDVTList VTs = getVTList(VT1, VT2, VT3);
5911 SDValue Ops[] = { Op1, Op2 };
5912 return getMachineNode(Opcode, dl, VTs, Ops);
5916 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5917 EVT VT1, EVT VT2, EVT VT3,
5918 SDValue Op1, SDValue Op2, SDValue Op3) {
5919 SDVTList VTs = getVTList(VT1, VT2, VT3);
5920 SDValue Ops[] = { Op1, Op2, Op3 };
5921 return getMachineNode(Opcode, dl, VTs, Ops);
5925 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5926 EVT VT1, EVT VT2, EVT VT3,
5927 ArrayRef<SDValue> Ops) {
5928 SDVTList VTs = getVTList(VT1, VT2, VT3);
5929 return getMachineNode(Opcode, dl, VTs, Ops);
5933 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5934 EVT VT2, EVT VT3, EVT VT4,
5935 ArrayRef<SDValue> Ops) {
5936 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5937 return getMachineNode(Opcode, dl, VTs, Ops);
5941 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5942 ArrayRef<EVT> ResultTys,
5943 ArrayRef<SDValue> Ops) {
5944 SDVTList VTs = getVTList(ResultTys);
5945 return getMachineNode(Opcode, dl, VTs, Ops);
5949 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5950 ArrayRef<SDValue> OpsArray) {
5951 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5954 const SDValue *Ops = OpsArray.data();
5955 unsigned NumOps = OpsArray.size();
5958 FoldingSetNodeID ID;
5959 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5961 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
5962 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5966 // Allocate a new MachineSDNode.
5967 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5968 DL.getDebugLoc(), VTs);
5970 // Initialize the operands list.
5971 if (NumOps > array_lengthof(N->LocalOperands))
5972 // We're creating a final node that will live unmorphed for the
5973 // remainder of the current SelectionDAG iteration, so we can allocate
5974 // the operands directly out of a pool with no recycling metadata.
5975 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5978 N->InitOperands(N->LocalOperands, Ops, NumOps);
5979 N->OperandsNeedDelete = false;
5982 CSEMap.InsertNode(N, IP);
5988 /// getTargetExtractSubreg - A convenience function for creating
5989 /// TargetOpcode::EXTRACT_SUBREG nodes.
5991 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5993 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5994 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5995 VT, Operand, SRIdxVal);
5996 return SDValue(Subreg, 0);
5999 /// getTargetInsertSubreg - A convenience function for creating
6000 /// TargetOpcode::INSERT_SUBREG nodes.
6002 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6003 SDValue Operand, SDValue Subreg) {
6004 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6005 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6006 VT, Operand, Subreg, SRIdxVal);
6007 return SDValue(Result, 0);
6010 /// getNodeIfExists - Get the specified node if it's already available, or
6011 /// else return NULL.
6012 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6013 ArrayRef<SDValue> Ops,
6014 const SDNodeFlags *Flags) {
6015 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6016 FoldingSetNodeID ID;
6017 AddNodeIDNode(ID, Opcode, VTList, Ops);
6018 AddNodeIDFlags(ID, Opcode, Flags);
6020 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6026 /// getDbgValue - Creates a SDDbgValue node.
6029 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6030 unsigned R, bool IsIndirect, uint64_t Off,
6031 DebugLoc DL, unsigned O) {
6032 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6033 "Expected inlined-at fields to agree");
6034 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6038 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6039 const Value *C, uint64_t Off,
6040 DebugLoc DL, unsigned O) {
6041 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6042 "Expected inlined-at fields to agree");
6043 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6047 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6048 unsigned FI, uint64_t Off,
6049 DebugLoc DL, unsigned O) {
6050 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6051 "Expected inlined-at fields to agree");
6052 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6057 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6058 /// pointed to by a use iterator is deleted, increment the use iterator
6059 /// so that it doesn't dangle.
6061 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6062 SDNode::use_iterator &UI;
6063 SDNode::use_iterator &UE;
6065 void NodeDeleted(SDNode *N, SDNode *E) override {
6066 // Increment the iterator as needed.
6067 while (UI != UE && N == *UI)
6072 RAUWUpdateListener(SelectionDAG &d,
6073 SDNode::use_iterator &ui,
6074 SDNode::use_iterator &ue)
6075 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6080 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6081 /// This can cause recursive merging of nodes in the DAG.
6083 /// This version assumes From has a single result value.
6085 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6086 SDNode *From = FromN.getNode();
6087 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6088 "Cannot replace with this method!");
6089 assert(From != To.getNode() && "Cannot replace uses of with self");
6091 // Iterate over all the existing uses of From. New uses will be added
6092 // to the beginning of the use list, which we avoid visiting.
6093 // This specifically avoids visiting uses of From that arise while the
6094 // replacement is happening, because any such uses would be the result
6095 // of CSE: If an existing node looks like From after one of its operands
6096 // is replaced by To, we don't want to replace of all its users with To
6097 // too. See PR3018 for more info.
6098 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6099 RAUWUpdateListener Listener(*this, UI, UE);
6103 // This node is about to morph, remove its old self from the CSE maps.
6104 RemoveNodeFromCSEMaps(User);
6106 // A user can appear in a use list multiple times, and when this
6107 // happens the uses are usually next to each other in the list.
6108 // To help reduce the number of CSE recomputations, process all
6109 // the uses of this user that we can find this way.
6111 SDUse &Use = UI.getUse();
6114 } while (UI != UE && *UI == User);
6116 // Now that we have modified User, add it back to the CSE maps. If it
6117 // already exists there, recursively merge the results together.
6118 AddModifiedNodeToCSEMaps(User);
6121 // If we just RAUW'd the root, take note.
6122 if (FromN == getRoot())
6126 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6127 /// This can cause recursive merging of nodes in the DAG.
6129 /// This version assumes that for each value of From, there is a
6130 /// corresponding value in To in the same position with the same type.
6132 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6134 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6135 assert((!From->hasAnyUseOfValue(i) ||
6136 From->getValueType(i) == To->getValueType(i)) &&
6137 "Cannot use this version of ReplaceAllUsesWith!");
6140 // Handle the trivial case.
6144 // Iterate over just the existing users of From. See the comments in
6145 // the ReplaceAllUsesWith above.
6146 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6147 RAUWUpdateListener Listener(*this, UI, UE);
6151 // This node is about to morph, remove its old self from the CSE maps.
6152 RemoveNodeFromCSEMaps(User);
6154 // A user can appear in a use list multiple times, and when this
6155 // happens the uses are usually next to each other in the list.
6156 // To help reduce the number of CSE recomputations, process all
6157 // the uses of this user that we can find this way.
6159 SDUse &Use = UI.getUse();
6162 } while (UI != UE && *UI == User);
6164 // Now that we have modified User, add it back to the CSE maps. If it
6165 // already exists there, recursively merge the results together.
6166 AddModifiedNodeToCSEMaps(User);
6169 // If we just RAUW'd the root, take note.
6170 if (From == getRoot().getNode())
6171 setRoot(SDValue(To, getRoot().getResNo()));
6174 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6175 /// This can cause recursive merging of nodes in the DAG.
6177 /// This version can replace From with any result values. To must match the
6178 /// number and types of values returned by From.
6179 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6180 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6181 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6183 // Iterate over just the existing users of From. See the comments in
6184 // the ReplaceAllUsesWith above.
6185 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6186 RAUWUpdateListener Listener(*this, UI, UE);
6190 // This node is about to morph, remove its old self from the CSE maps.
6191 RemoveNodeFromCSEMaps(User);
6193 // A user can appear in a use list multiple times, and when this
6194 // happens the uses are usually next to each other in the list.
6195 // To help reduce the number of CSE recomputations, process all
6196 // the uses of this user that we can find this way.
6198 SDUse &Use = UI.getUse();
6199 const SDValue &ToOp = To[Use.getResNo()];
6202 } while (UI != UE && *UI == User);
6204 // Now that we have modified User, add it back to the CSE maps. If it
6205 // already exists there, recursively merge the results together.
6206 AddModifiedNodeToCSEMaps(User);
6209 // If we just RAUW'd the root, take note.
6210 if (From == getRoot().getNode())
6211 setRoot(SDValue(To[getRoot().getResNo()]));
6214 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6215 /// uses of other values produced by From.getNode() alone. The Deleted
6216 /// vector is handled the same way as for ReplaceAllUsesWith.
6217 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6218 // Handle the really simple, really trivial case efficiently.
6219 if (From == To) return;
6221 // Handle the simple, trivial, case efficiently.
6222 if (From.getNode()->getNumValues() == 1) {
6223 ReplaceAllUsesWith(From, To);
6227 // Iterate over just the existing users of From. See the comments in
6228 // the ReplaceAllUsesWith above.
6229 SDNode::use_iterator UI = From.getNode()->use_begin(),
6230 UE = From.getNode()->use_end();
6231 RAUWUpdateListener Listener(*this, UI, UE);
6234 bool UserRemovedFromCSEMaps = false;
6236 // A user can appear in a use list multiple times, and when this
6237 // happens the uses are usually next to each other in the list.
6238 // To help reduce the number of CSE recomputations, process all
6239 // the uses of this user that we can find this way.
6241 SDUse &Use = UI.getUse();
6243 // Skip uses of different values from the same node.
6244 if (Use.getResNo() != From.getResNo()) {
6249 // If this node hasn't been modified yet, it's still in the CSE maps,
6250 // so remove its old self from the CSE maps.
6251 if (!UserRemovedFromCSEMaps) {
6252 RemoveNodeFromCSEMaps(User);
6253 UserRemovedFromCSEMaps = true;
6258 } while (UI != UE && *UI == User);
6260 // We are iterating over all uses of the From node, so if a use
6261 // doesn't use the specific value, no changes are made.
6262 if (!UserRemovedFromCSEMaps)
6265 // Now that we have modified User, add it back to the CSE maps. If it
6266 // already exists there, recursively merge the results together.
6267 AddModifiedNodeToCSEMaps(User);
6270 // If we just RAUW'd the root, take note.
6271 if (From == getRoot())
6276 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6277 /// to record information about a use.
6284 /// operator< - Sort Memos by User.
6285 bool operator<(const UseMemo &L, const UseMemo &R) {
6286 return (intptr_t)L.User < (intptr_t)R.User;
6290 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6291 /// uses of other values produced by From.getNode() alone. The same value
6292 /// may appear in both the From and To list. The Deleted vector is
6293 /// handled the same way as for ReplaceAllUsesWith.
6294 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6297 // Handle the simple, trivial case efficiently.
6299 return ReplaceAllUsesOfValueWith(*From, *To);
6301 // Read up all the uses and make records of them. This helps
6302 // processing new uses that are introduced during the
6303 // replacement process.
6304 SmallVector<UseMemo, 4> Uses;
6305 for (unsigned i = 0; i != Num; ++i) {
6306 unsigned FromResNo = From[i].getResNo();
6307 SDNode *FromNode = From[i].getNode();
6308 for (SDNode::use_iterator UI = FromNode->use_begin(),
6309 E = FromNode->use_end(); UI != E; ++UI) {
6310 SDUse &Use = UI.getUse();
6311 if (Use.getResNo() == FromResNo) {
6312 UseMemo Memo = { *UI, i, &Use };
6313 Uses.push_back(Memo);
6318 // Sort the uses, so that all the uses from a given User are together.
6319 std::sort(Uses.begin(), Uses.end());
6321 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6322 UseIndex != UseIndexEnd; ) {
6323 // We know that this user uses some value of From. If it is the right
6324 // value, update it.
6325 SDNode *User = Uses[UseIndex].User;
6327 // This node is about to morph, remove its old self from the CSE maps.
6328 RemoveNodeFromCSEMaps(User);
6330 // The Uses array is sorted, so all the uses for a given User
6331 // are next to each other in the list.
6332 // To help reduce the number of CSE recomputations, process all
6333 // the uses of this user that we can find this way.
6335 unsigned i = Uses[UseIndex].Index;
6336 SDUse &Use = *Uses[UseIndex].Use;
6340 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6342 // Now that we have modified User, add it back to the CSE maps. If it
6343 // already exists there, recursively merge the results together.
6344 AddModifiedNodeToCSEMaps(User);
6348 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6349 /// based on their topological order. It returns the maximum id and a vector
6350 /// of the SDNodes* in assigned order by reference.
6351 unsigned SelectionDAG::AssignTopologicalOrder() {
6353 unsigned DAGSize = 0;
6355 // SortedPos tracks the progress of the algorithm. Nodes before it are
6356 // sorted, nodes after it are unsorted. When the algorithm completes
6357 // it is at the end of the list.
6358 allnodes_iterator SortedPos = allnodes_begin();
6360 // Visit all the nodes. Move nodes with no operands to the front of
6361 // the list immediately. Annotate nodes that do have operands with their
6362 // operand count. Before we do this, the Node Id fields of the nodes
6363 // may contain arbitrary values. After, the Node Id fields for nodes
6364 // before SortedPos will contain the topological sort index, and the
6365 // Node Id fields for nodes At SortedPos and after will contain the
6366 // count of outstanding operands.
6367 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6369 checkForCycles(N, this);
6370 unsigned Degree = N->getNumOperands();
6372 // A node with no uses, add it to the result array immediately.
6373 N->setNodeId(DAGSize++);
6374 allnodes_iterator Q = N;
6376 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6377 assert(SortedPos != AllNodes.end() && "Overran node list");
6380 // Temporarily use the Node Id as scratch space for the degree count.
6381 N->setNodeId(Degree);
6385 // Visit all the nodes. As we iterate, move nodes into sorted order,
6386 // such that by the time the end is reached all nodes will be sorted.
6387 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6389 checkForCycles(N, this);
6390 // N is in sorted position, so all its uses have one less operand
6391 // that needs to be sorted.
6392 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6395 unsigned Degree = P->getNodeId();
6396 assert(Degree != 0 && "Invalid node degree");
6399 // All of P's operands are sorted, so P may sorted now.
6400 P->setNodeId(DAGSize++);
6402 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6403 assert(SortedPos != AllNodes.end() && "Overran node list");
6406 // Update P's outstanding operand count.
6407 P->setNodeId(Degree);
6410 if (I == SortedPos) {
6413 dbgs() << "Overran sorted position:\n";
6414 S->dumprFull(this); dbgs() << "\n";
6415 dbgs() << "Checking if this is due to cycles\n";
6416 checkForCycles(this, true);
6418 llvm_unreachable(nullptr);
6422 assert(SortedPos == AllNodes.end() &&
6423 "Topological sort incomplete!");
6424 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6425 "First node in topological sort is not the entry token!");
6426 assert(AllNodes.front().getNodeId() == 0 &&
6427 "First node in topological sort has non-zero id!");
6428 assert(AllNodes.front().getNumOperands() == 0 &&
6429 "First node in topological sort has operands!");
6430 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6431 "Last node in topologic sort has unexpected id!");
6432 assert(AllNodes.back().use_empty() &&
6433 "Last node in topologic sort has users!");
6434 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6438 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6439 /// value is produced by SD.
6440 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6442 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6443 SD->setHasDebugValue(true);
6445 DbgInfo->add(DB, SD, isParameter);
6448 /// TransferDbgValues - Transfer SDDbgValues.
6449 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6450 if (From == To || !From.getNode()->getHasDebugValue())
6452 SDNode *FromNode = From.getNode();
6453 SDNode *ToNode = To.getNode();
6454 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6455 SmallVector<SDDbgValue *, 2> ClonedDVs;
6456 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6458 SDDbgValue *Dbg = *I;
6459 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6461 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6462 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6463 Dbg->getDebugLoc(), Dbg->getOrder());
6464 ClonedDVs.push_back(Clone);
6467 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6468 E = ClonedDVs.end(); I != E; ++I)
6469 AddDbgValue(*I, ToNode, false);
6472 //===----------------------------------------------------------------------===//
6474 //===----------------------------------------------------------------------===//
6476 HandleSDNode::~HandleSDNode() {
6480 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6481 DebugLoc DL, const GlobalValue *GA,
6482 EVT VT, int64_t o, unsigned char TF)
6483 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6487 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6488 SDValue X, unsigned SrcAS,
6490 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6491 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6493 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6494 EVT memvt, MachineMemOperand *mmo)
6495 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6496 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6497 MMO->isNonTemporal(), MMO->isInvariant());
6498 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6499 assert(isNonTemporal() == MMO->isNonTemporal() &&
6500 "Non-temporal encoding error!");
6501 // We check here that the size of the memory operand fits within the size of
6502 // the MMO. This is because the MMO might indicate only a possible address
6503 // range instead of specifying the affected memory addresses precisely.
6504 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6507 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6508 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6509 : SDNode(Opc, Order, dl, VTs, Ops),
6510 MemoryVT(memvt), MMO(mmo) {
6511 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6512 MMO->isNonTemporal(), MMO->isInvariant());
6513 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6514 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6517 /// Profile - Gather unique data for the node.
6519 void SDNode::Profile(FoldingSetNodeID &ID) const {
6520 AddNodeIDNode(ID, this);
6525 std::vector<EVT> VTs;
6528 VTs.reserve(MVT::LAST_VALUETYPE);
6529 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6530 VTs.push_back(MVT((MVT::SimpleValueType)i));
6535 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6536 static ManagedStatic<EVTArray> SimpleVTArray;
6537 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6539 /// getValueTypeList - Return a pointer to the specified value type.
6541 const EVT *SDNode::getValueTypeList(EVT VT) {
6542 if (VT.isExtended()) {
6543 sys::SmartScopedLock<true> Lock(*VTMutex);
6544 return &(*EVTs->insert(VT).first);
6546 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6547 "Value type out of range!");
6548 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6552 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6553 /// indicated value. This method ignores uses of other values defined by this
6555 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6556 assert(Value < getNumValues() && "Bad value!");
6558 // TODO: Only iterate over uses of a given value of the node
6559 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6560 if (UI.getUse().getResNo() == Value) {
6567 // Found exactly the right number of uses?
6572 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6573 /// value. This method ignores uses of other values defined by this operation.
6574 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6575 assert(Value < getNumValues() && "Bad value!");
6577 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6578 if (UI.getUse().getResNo() == Value)
6585 /// isOnlyUserOf - Return true if this node is the only use of N.
6587 bool SDNode::isOnlyUserOf(SDNode *N) const {
6589 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6600 /// isOperand - Return true if this node is an operand of N.
6602 bool SDValue::isOperandOf(SDNode *N) const {
6603 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6604 if (*this == N->getOperand(i))
6609 bool SDNode::isOperandOf(SDNode *N) const {
6610 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6611 if (this == N->OperandList[i].getNode())
6616 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6617 /// be a chain) reaches the specified operand without crossing any
6618 /// side-effecting instructions on any chain path. In practice, this looks
6619 /// through token factors and non-volatile loads. In order to remain efficient,
6620 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6621 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6622 unsigned Depth) const {
6623 if (*this == Dest) return true;
6625 // Don't search too deeply, we just want to be able to see through
6626 // TokenFactor's etc.
6627 if (Depth == 0) return false;
6629 // If this is a token factor, all inputs to the TF happen in parallel. If any
6630 // of the operands of the TF does not reach dest, then we cannot do the xform.
6631 if (getOpcode() == ISD::TokenFactor) {
6632 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6633 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6638 // Loads don't have side effects, look through them.
6639 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6640 if (!Ld->isVolatile())
6641 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6646 /// hasPredecessor - Return true if N is a predecessor of this node.
6647 /// N is either an operand of this node, or can be reached by recursively
6648 /// traversing up the operands.
6649 /// NOTE: This is an expensive method. Use it carefully.
6650 bool SDNode::hasPredecessor(const SDNode *N) const {
6651 SmallPtrSet<const SDNode *, 32> Visited;
6652 SmallVector<const SDNode *, 16> Worklist;
6653 return hasPredecessorHelper(N, Visited, Worklist);
6657 SDNode::hasPredecessorHelper(const SDNode *N,
6658 SmallPtrSetImpl<const SDNode *> &Visited,
6659 SmallVectorImpl<const SDNode *> &Worklist) const {
6660 if (Visited.empty()) {
6661 Worklist.push_back(this);
6663 // Take a look in the visited set. If we've already encountered this node
6664 // we needn't search further.
6665 if (Visited.count(N))
6669 // Haven't visited N yet. Continue the search.
6670 while (!Worklist.empty()) {
6671 const SDNode *M = Worklist.pop_back_val();
6672 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6673 SDNode *Op = M->getOperand(i).getNode();
6674 if (Visited.insert(Op).second)
6675 Worklist.push_back(Op);
6684 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6685 assert(Num < NumOperands && "Invalid child # of SDNode!");
6686 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6689 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6690 assert(N->getNumValues() == 1 &&
6691 "Can't unroll a vector with multiple results!");
6693 EVT VT = N->getValueType(0);
6694 unsigned NE = VT.getVectorNumElements();
6695 EVT EltVT = VT.getVectorElementType();
6698 SmallVector<SDValue, 8> Scalars;
6699 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6701 // If ResNE is 0, fully unroll the vector op.
6704 else if (NE > ResNE)
6708 for (i= 0; i != NE; ++i) {
6709 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6710 SDValue Operand = N->getOperand(j);
6711 EVT OperandVT = Operand.getValueType();
6712 if (OperandVT.isVector()) {
6713 // A vector operand; extract a single element.
6714 EVT OperandEltVT = OperandVT.getVectorElementType();
6715 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6718 getConstant(i, dl, TLI->getVectorIdxTy()));
6720 // A scalar operand; just use it as is.
6721 Operands[j] = Operand;
6725 switch (N->getOpcode()) {
6727 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6730 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6737 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6738 getShiftAmountOperand(Operands[0].getValueType(),
6741 case ISD::SIGN_EXTEND_INREG:
6742 case ISD::FP_ROUND_INREG: {
6743 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6744 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6746 getValueType(ExtVT)));
6751 for (; i < ResNE; ++i)
6752 Scalars.push_back(getUNDEF(EltVT));
6754 return getNode(ISD::BUILD_VECTOR, dl,
6755 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6759 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6760 /// location that is 'Dist' units away from the location that the 'Base' load
6761 /// is loading from.
6762 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6763 unsigned Bytes, int Dist) const {
6764 if (LD->getChain() != Base->getChain())
6766 EVT VT = LD->getValueType(0);
6767 if (VT.getSizeInBits() / 8 != Bytes)
6770 SDValue Loc = LD->getOperand(1);
6771 SDValue BaseLoc = Base->getOperand(1);
6772 if (Loc.getOpcode() == ISD::FrameIndex) {
6773 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6775 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6776 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6777 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6778 int FS = MFI->getObjectSize(FI);
6779 int BFS = MFI->getObjectSize(BFI);
6780 if (FS != BFS || FS != (int)Bytes) return false;
6781 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6785 if (isBaseWithConstantOffset(Loc)) {
6786 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6787 if (Loc.getOperand(0) == BaseLoc) {
6788 // If the base location is a simple address with no offset itself, then
6789 // the second load's first add operand should be the base address.
6790 if (LocOffset == Dist * (int)Bytes)
6792 } else if (isBaseWithConstantOffset(BaseLoc)) {
6793 // The base location itself has an offset, so subtract that value from the
6794 // second load's offset before comparing to distance * size.
6796 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6797 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6798 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6803 const GlobalValue *GV1 = nullptr;
6804 const GlobalValue *GV2 = nullptr;
6805 int64_t Offset1 = 0;
6806 int64_t Offset2 = 0;
6807 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6808 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6809 if (isGA1 && isGA2 && GV1 == GV2)
6810 return Offset1 == (Offset2 + Dist*Bytes);
6815 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6816 /// it cannot be inferred.
6817 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6818 // If this is a GlobalAddress + cst, return the alignment.
6819 const GlobalValue *GV;
6820 int64_t GVOffset = 0;
6821 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6822 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6823 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6824 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6825 *TLI->getDataLayout());
6826 unsigned AlignBits = KnownZero.countTrailingOnes();
6827 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6829 return MinAlign(Align, GVOffset);
6832 // If this is a direct reference to a stack slot, use information about the
6833 // stack slot's alignment.
6834 int FrameIdx = 1 << 31;
6835 int64_t FrameOffset = 0;
6836 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6837 FrameIdx = FI->getIndex();
6838 } else if (isBaseWithConstantOffset(Ptr) &&
6839 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6841 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6842 FrameOffset = Ptr.getConstantOperandVal(1);
6845 if (FrameIdx != (1 << 31)) {
6846 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6847 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6855 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6856 /// which is split (or expanded) into two not necessarily identical pieces.
6857 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6858 // Currently all types are split in half.
6860 if (!VT.isVector()) {
6861 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6863 unsigned NumElements = VT.getVectorNumElements();
6864 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6865 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6868 return std::make_pair(LoVT, HiVT);
6871 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6873 std::pair<SDValue, SDValue>
6874 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6876 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6877 N.getValueType().getVectorNumElements() &&
6878 "More vector elements requested than available!");
6880 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6881 getConstant(0, DL, TLI->getVectorIdxTy()));
6882 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6883 getConstant(LoVT.getVectorNumElements(), DL,
6884 TLI->getVectorIdxTy()));
6885 return std::make_pair(Lo, Hi);
6888 void SelectionDAG::ExtractVectorElements(SDValue Op,
6889 SmallVectorImpl<SDValue> &Args,
6890 unsigned Start, unsigned Count) {
6891 EVT VT = Op.getValueType();
6893 Count = VT.getVectorNumElements();
6895 EVT EltVT = VT.getVectorElementType();
6896 EVT IdxTy = TLI->getVectorIdxTy();
6898 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6899 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6900 Op, getConstant(i, SL, IdxTy)));
6904 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6905 unsigned GlobalAddressSDNode::getAddressSpace() const {
6906 return getGlobal()->getType()->getAddressSpace();
6910 Type *ConstantPoolSDNode::getType() const {
6911 if (isMachineConstantPoolEntry())
6912 return Val.MachineCPVal->getType();
6913 return Val.ConstVal->getType();
6916 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6918 unsigned &SplatBitSize,
6920 unsigned MinSplatBits,
6921 bool isBigEndian) const {
6922 EVT VT = getValueType(0);
6923 assert(VT.isVector() && "Expected a vector type");
6924 unsigned sz = VT.getSizeInBits();
6925 if (MinSplatBits > sz)
6928 SplatValue = APInt(sz, 0);
6929 SplatUndef = APInt(sz, 0);
6931 // Get the bits. Bits with undefined values (when the corresponding element
6932 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6933 // in SplatValue. If any of the values are not constant, give up and return
6935 unsigned int nOps = getNumOperands();
6936 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6937 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6939 for (unsigned j = 0; j < nOps; ++j) {
6940 unsigned i = isBigEndian ? nOps-1-j : j;
6941 SDValue OpVal = getOperand(i);
6942 unsigned BitPos = j * EltBitSize;
6944 if (OpVal.getOpcode() == ISD::UNDEF)
6945 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6946 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6947 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6948 zextOrTrunc(sz) << BitPos;
6949 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6950 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6955 // The build_vector is all constants or undefs. Find the smallest element
6956 // size that splats the vector.
6958 HasAnyUndefs = (SplatUndef != 0);
6961 unsigned HalfSize = sz / 2;
6962 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6963 APInt LowValue = SplatValue.trunc(HalfSize);
6964 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6965 APInt LowUndef = SplatUndef.trunc(HalfSize);
6967 // If the two halves do not match (ignoring undef bits), stop here.
6968 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6969 MinSplatBits > HalfSize)
6972 SplatValue = HighValue | LowValue;
6973 SplatUndef = HighUndef & LowUndef;
6982 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6983 if (UndefElements) {
6984 UndefElements->clear();
6985 UndefElements->resize(getNumOperands());
6988 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6989 SDValue Op = getOperand(i);
6990 if (Op.getOpcode() == ISD::UNDEF) {
6992 (*UndefElements)[i] = true;
6993 } else if (!Splatted) {
6995 } else if (Splatted != Op) {
7001 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7002 "Can only have a splat without a constant for all undefs.");
7003 return getOperand(0);
7010 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7011 return dyn_cast_or_null<ConstantSDNode>(
7012 getSplatValue(UndefElements).getNode());
7016 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7017 return dyn_cast_or_null<ConstantFPSDNode>(
7018 getSplatValue(UndefElements).getNode());
7021 bool BuildVectorSDNode::isConstant() const {
7022 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7023 unsigned Opc = getOperand(i).getOpcode();
7024 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7030 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7031 // Find the first non-undef value in the shuffle mask.
7033 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7036 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7038 // Make sure all remaining elements are either undef or the same as the first
7040 for (int Idx = Mask[i]; i != e; ++i)
7041 if (Mask[i] >= 0 && Mask[i] != Idx)
7047 static void checkForCyclesHelper(const SDNode *N,
7048 SmallPtrSetImpl<const SDNode*> &Visited,
7049 SmallPtrSetImpl<const SDNode*> &Checked,
7050 const llvm::SelectionDAG *DAG) {
7051 // If this node has already been checked, don't check it again.
7052 if (Checked.count(N))
7055 // If a node has already been visited on this depth-first walk, reject it as
7057 if (!Visited.insert(N).second) {
7058 errs() << "Detected cycle in SelectionDAG\n";
7059 dbgs() << "Offending node:\n";
7060 N->dumprFull(DAG); dbgs() << "\n";
7064 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7065 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7072 void llvm::checkForCycles(const llvm::SDNode *N,
7073 const llvm::SelectionDAG *DAG,
7081 assert(N && "Checking nonexistent SDNode");
7082 SmallPtrSet<const SDNode*, 32> visited;
7083 SmallPtrSet<const SDNode*, 32> checked;
7084 checkForCyclesHelper(N, visited, checked, DAG);
7089 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7090 checkForCycles(DAG->getRoot().getNode(), DAG, force);