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"
54 /// makeVTList - Return an instance of the SDVTList struct initialized with the
55 /// specified members.
56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
57 SDVTList Res = {VTs, NumVTs};
61 // Default null implementations of the callbacks.
62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
65 //===----------------------------------------------------------------------===//
66 // ConstantFPSDNode Class
67 //===----------------------------------------------------------------------===//
69 /// isExactlyValue - We don't rely on operator== working on double values, as
70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
71 /// As such, this method can be used to do an exact bit-for-bit comparison of
72 /// two floating point values.
73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
74 return getValueAPF().bitwiseIsEqual(V);
77 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 assert(VT.isFloatingPoint() && "Can only convert between FP types");
81 // convert modifies in place, so make a copy.
82 APFloat Val2 = APFloat(Val);
84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
85 APFloat::rmNearestTiesToEven,
90 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
94 /// isBuildVectorAllOnes - Return true if the specified node is a
95 /// BUILD_VECTOR where all of the elements are ~0 or undef.
96 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
97 // Look through a bit convert.
98 if (N->getOpcode() == ISD::BITCAST)
99 N = N->getOperand(0).getNode();
101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
103 unsigned i = 0, e = N->getNumOperands();
105 // Skip over all of the undef values.
106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109 // Do not accept an all-undef vector.
110 if (i == e) return false;
112 // Do not accept build_vectors that aren't all constants or which have non-~0
113 // elements. We have to be a bit careful here, as the type of the constant
114 // may not be the same as the type of the vector elements due to type
115 // legalization (the elements are promoted to a legal type for the target and
116 // a vector of a type may be legal when the base element type is not).
117 // We only want to check enough bits to cover the vector elements, because
118 // we care if the resultant vector is all ones, not whether the individual
120 SDValue NotZero = N->getOperand(i);
121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
123 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
131 // Okay, we have at least one ~0 value, check to see if the rest match or are
132 // undefs. Even with the above element type twiddling, this should be OK, as
133 // the same type legalization should have applied to all the elements.
134 for (++i; i != e; ++i)
135 if (N->getOperand(i) != NotZero &&
136 N->getOperand(i).getOpcode() != ISD::UNDEF)
142 /// isBuildVectorAllZeros - Return true if the specified node is a
143 /// BUILD_VECTOR where all of the elements are 0 or undef.
144 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
145 // Look through a bit convert.
146 if (N->getOpcode() == ISD::BITCAST)
147 N = N->getOperand(0).getNode();
149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
151 bool IsAllUndef = true;
152 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
153 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept build_vectors that aren't all constants or which have non-0
157 // elements. We have to be a bit careful here, as the type of the constant
158 // may not be the same as the type of the vector elements due to type
159 // legalization (the elements are promoted to a legal type for the target
160 // and a vector of a type may be legal when the base element type is not).
161 // We only want to check enough bits to cover the vector elements, because
162 // we care if the resultant vector is all zeros, not whether the individual
164 SDValue Zero = N->getOperand(i);
165 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
166 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
167 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
170 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
176 // Do not accept an all-undef vector.
182 /// \brief Return true if the specified node is a BUILD_VECTOR node of
183 /// all ConstantSDNode or undef.
184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
185 if (N->getOpcode() != ISD::BUILD_VECTOR)
188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
189 SDValue Op = N->getOperand(i);
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// isScalarToVector - Return true if the specified node is a
199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
200 /// element is not an undef.
201 bool ISD::isScalarToVector(const SDNode *N) {
202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
205 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 unsigned NumElems = N->getNumOperands();
212 for (unsigned i = 1; i < NumElems; ++i) {
213 SDValue V = N->getOperand(i);
214 if (V.getOpcode() != ISD::UNDEF)
220 /// allOperandsUndef - Return true if the node has at least one operand
221 /// and all operands of the specified node are ISD::UNDEF.
222 bool ISD::allOperandsUndef(const SDNode *N) {
223 // Return false if the node has no operands.
224 // This is "logically inconsistent" with the definition of "all" but
225 // is probably the desired behavior.
226 if (N->getNumOperands() == 0)
229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
230 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
236 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
239 return ISD::ANY_EXTEND;
241 return ISD::SIGN_EXTEND;
243 return ISD::ZERO_EXTEND;
248 llvm_unreachable("Invalid LoadExtType");
251 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
252 /// when given the operation for (X op Y).
253 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
254 // To perform this operation, we just need to swap the L and G bits of the
256 unsigned OldL = (Operation >> 2) & 1;
257 unsigned OldG = (Operation >> 1) & 1;
258 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
259 (OldL << 1) | // New G bit
260 (OldG << 2)); // New L bit.
263 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
264 /// 'op' is a valid SetCC operation.
265 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
266 unsigned Operation = Op;
268 Operation ^= 7; // Flip L, G, E bits, but not U.
270 Operation ^= 15; // Flip all of the condition bits.
272 if (Operation > ISD::SETTRUE2)
273 Operation &= ~8; // Don't let N and U bits get set.
275 return ISD::CondCode(Operation);
279 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
280 /// signed operation and 2 if the result is an unsigned comparison. Return zero
281 /// if the operation does not depend on the sign of the input (setne and seteq).
282 static int isSignedOp(ISD::CondCode Opcode) {
284 default: llvm_unreachable("Illegal integer setcc operation!");
286 case ISD::SETNE: return 0;
290 case ISD::SETGE: return 1;
294 case ISD::SETUGE: return 2;
298 /// getSetCCOrOperation - Return the result of a logical OR between different
299 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
300 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
305 // Cannot fold a signed integer setcc with an unsigned integer setcc.
306 return ISD::SETCC_INVALID;
308 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
310 // If the N and U bits get set then the resultant comparison DOES suddenly
311 // care about orderedness, and is true when ordered.
312 if (Op > ISD::SETTRUE2)
313 Op &= ~16; // Clear the U bit if the N bit is set.
315 // Canonicalize illegal integer setcc's.
316 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
319 return ISD::CondCode(Op);
322 /// getSetCCAndOperation - Return the result of a logical AND between different
323 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
324 /// function returns zero if it is not possible to represent the resultant
326 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
329 // Cannot fold a signed setcc with an unsigned setcc.
330 return ISD::SETCC_INVALID;
332 // Combine all of the condition bits.
333 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
335 // Canonicalize illegal integer setcc's.
339 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
340 case ISD::SETOEQ: // SETEQ & SETU[LG]E
341 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
342 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
343 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
350 //===----------------------------------------------------------------------===//
351 // SDNode Profile Support
352 //===----------------------------------------------------------------------===//
354 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
360 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
361 /// solely with their pointer.
362 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
363 ID.AddPointer(VTList.VTs);
366 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 static void AddNodeIDOperands(FoldingSetNodeID &ID,
369 ArrayRef<SDValue> Ops) {
370 for (auto& Op : Ops) {
371 ID.AddPointer(Op.getNode());
372 ID.AddInteger(Op.getResNo());
376 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 static void AddNodeIDOperands(FoldingSetNodeID &ID,
379 ArrayRef<SDUse> Ops) {
380 for (auto& Op : Ops) {
381 ID.AddPointer(Op.getNode());
382 ID.AddInteger(Op.getResNo());
386 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
390 ID.AddBoolean(exact);
393 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
394 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
395 bool nuw, bool nsw, bool exact) {
396 if (isBinOpWithFlags(Opcode))
397 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
400 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
401 SDVTList VTList, ArrayRef<SDValue> OpList) {
402 AddNodeIDOpcode(ID, OpC);
403 AddNodeIDValueTypes(ID, VTList);
404 AddNodeIDOperands(ID, OpList);
407 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
410 switch (N->getOpcode()) {
411 case ISD::TargetExternalSymbol:
412 case ISD::ExternalSymbol:
413 llvm_unreachable("Should only be used on nodes with operands");
414 default: break; // Normal nodes don't need extra info.
415 case ISD::TargetConstant:
416 case ISD::Constant: {
417 const ConstantSDNode *C = cast<ConstantSDNode>(N);
418 ID.AddPointer(C->getConstantIntValue());
419 ID.AddBoolean(C->isOpaque());
422 case ISD::TargetConstantFP:
423 case ISD::ConstantFP: {
424 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
427 case ISD::TargetGlobalAddress:
428 case ISD::GlobalAddress:
429 case ISD::TargetGlobalTLSAddress:
430 case ISD::GlobalTLSAddress: {
431 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
432 ID.AddPointer(GA->getGlobal());
433 ID.AddInteger(GA->getOffset());
434 ID.AddInteger(GA->getTargetFlags());
435 ID.AddInteger(GA->getAddressSpace());
438 case ISD::BasicBlock:
439 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
442 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444 case ISD::RegisterMask:
445 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
448 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450 case ISD::FrameIndex:
451 case ISD::TargetFrameIndex:
452 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
455 case ISD::TargetJumpTable:
456 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459 case ISD::ConstantPool:
460 case ISD::TargetConstantPool: {
461 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
462 ID.AddInteger(CP->getAlignment());
463 ID.AddInteger(CP->getOffset());
464 if (CP->isMachineConstantPoolEntry())
465 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467 ID.AddPointer(CP->getConstVal());
468 ID.AddInteger(CP->getTargetFlags());
471 case ISD::TargetIndex: {
472 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
473 ID.AddInteger(TI->getIndex());
474 ID.AddInteger(TI->getOffset());
475 ID.AddInteger(TI->getTargetFlags());
479 const LoadSDNode *LD = cast<LoadSDNode>(N);
480 ID.AddInteger(LD->getMemoryVT().getRawBits());
481 ID.AddInteger(LD->getRawSubclassData());
482 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
486 const StoreSDNode *ST = cast<StoreSDNode>(N);
487 ID.AddInteger(ST->getMemoryVT().getRawBits());
488 ID.AddInteger(ST->getRawSubclassData());
489 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
500 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
501 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
502 BinNode->hasNoSignedWrap(), BinNode->isExact());
505 case ISD::ATOMIC_CMP_SWAP:
506 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
507 case ISD::ATOMIC_SWAP:
508 case ISD::ATOMIC_LOAD_ADD:
509 case ISD::ATOMIC_LOAD_SUB:
510 case ISD::ATOMIC_LOAD_AND:
511 case ISD::ATOMIC_LOAD_OR:
512 case ISD::ATOMIC_LOAD_XOR:
513 case ISD::ATOMIC_LOAD_NAND:
514 case ISD::ATOMIC_LOAD_MIN:
515 case ISD::ATOMIC_LOAD_MAX:
516 case ISD::ATOMIC_LOAD_UMIN:
517 case ISD::ATOMIC_LOAD_UMAX:
518 case ISD::ATOMIC_LOAD:
519 case ISD::ATOMIC_STORE: {
520 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
521 ID.AddInteger(AT->getMemoryVT().getRawBits());
522 ID.AddInteger(AT->getRawSubclassData());
523 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
526 case ISD::PREFETCH: {
527 const MemSDNode *PF = cast<MemSDNode>(N);
528 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
531 case ISD::VECTOR_SHUFFLE: {
532 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
533 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535 ID.AddInteger(SVN->getMaskElt(i));
538 case ISD::TargetBlockAddress:
539 case ISD::BlockAddress: {
540 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
541 ID.AddPointer(BA->getBlockAddress());
542 ID.AddInteger(BA->getOffset());
543 ID.AddInteger(BA->getTargetFlags());
546 } // end switch (N->getOpcode())
548 // Target specific memory nodes could also have address spaces to check.
549 if (N->isTargetMemoryOpcode())
550 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
553 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
556 AddNodeIDOpcode(ID, N->getOpcode());
557 // Add the return value info.
558 AddNodeIDValueTypes(ID, N->getVTList());
559 // Add the operand info.
560 AddNodeIDOperands(ID, N->ops());
562 // Handle SDNode leafs with special info.
563 AddNodeIDCustom(ID, N);
566 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
567 /// the CSE map that carries volatility, temporalness, indexing mode, and
568 /// extension/truncation information.
570 static inline unsigned
571 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
572 bool isNonTemporal, bool isInvariant) {
573 assert((ConvType & 3) == ConvType &&
574 "ConvType may not require more than 2 bits!");
575 assert((AM & 7) == AM &&
576 "AM may not require more than 3 bits!");
580 (isNonTemporal << 6) |
584 //===----------------------------------------------------------------------===//
585 // SelectionDAG Class
586 //===----------------------------------------------------------------------===//
588 /// doNotCSE - Return true if CSE should not be performed for this node.
589 static bool doNotCSE(SDNode *N) {
590 if (N->getValueType(0) == MVT::Glue)
591 return true; // Never CSE anything that produces a flag.
593 switch (N->getOpcode()) {
595 case ISD::HANDLENODE:
597 return true; // Never CSE these nodes.
600 // Check that remaining values produced are not flags.
601 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
602 if (N->getValueType(i) == MVT::Glue)
603 return true; // Never CSE anything that produces a flag.
608 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 void SelectionDAG::RemoveDeadNodes() {
611 // Create a dummy node (which is not added to allnodes), that adds a reference
612 // to the root node, preventing it from being deleted.
613 HandleSDNode Dummy(getRoot());
615 SmallVector<SDNode*, 128> DeadNodes;
617 // Add all obviously-dead nodes to the DeadNodes worklist.
618 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620 DeadNodes.push_back(I);
622 RemoveDeadNodes(DeadNodes);
624 // If the root changed (e.g. it was a dead load, update the root).
625 setRoot(Dummy.getValue());
628 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
629 /// given list, and any nodes that become unreachable as a result.
630 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
632 // Process the worklist, deleting the nodes and adding their uses to the
634 while (!DeadNodes.empty()) {
635 SDNode *N = DeadNodes.pop_back_val();
637 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
638 DUL->NodeDeleted(N, nullptr);
640 // Take the node out of the appropriate CSE map.
641 RemoveNodeFromCSEMaps(N);
643 // Next, brutally remove the operand list. This is safe to do, as there are
644 // no cycles in the graph.
645 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647 SDNode *Operand = Use.getNode();
650 // Now that we removed this operand, see if there are no uses of it left.
651 if (Operand->use_empty())
652 DeadNodes.push_back(Operand);
659 void SelectionDAG::RemoveDeadNode(SDNode *N){
660 SmallVector<SDNode*, 16> DeadNodes(1, N);
662 // Create a dummy node that adds a reference to the root node, preventing
663 // it from being deleted. (This matters if the root is an operand of the
665 HandleSDNode Dummy(getRoot());
667 RemoveDeadNodes(DeadNodes);
670 void SelectionDAG::DeleteNode(SDNode *N) {
671 // First take this out of the appropriate CSE map.
672 RemoveNodeFromCSEMaps(N);
674 // Finally, remove uses due to operands of this node, remove from the
675 // AllNodes list, and delete the node.
676 DeleteNodeNotInCSEMaps(N);
679 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
680 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
681 assert(N->use_empty() && "Cannot delete a node that is not dead!");
683 // Drop all of the operands and decrement used node's use counts.
689 void SDDbgInfo::erase(const SDNode *Node) {
690 DbgValMapType::iterator I = DbgValMap.find(Node);
691 if (I == DbgValMap.end())
693 for (unsigned J = 0, N = I->second.size(); J != N; ++J)
694 I->second[J]->setIsInvalidated();
698 void SelectionDAG::DeallocateNode(SDNode *N) {
699 if (N->OperandsNeedDelete)
700 delete[] N->OperandList;
702 // Set the opcode to DELETED_NODE to help catch bugs when node
703 // memory is reallocated.
704 N->NodeType = ISD::DELETED_NODE;
706 NodeAllocator.Deallocate(AllNodes.remove(N));
708 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
709 // them and forget about that node.
713 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
714 /// correspond to it. This is useful when we're about to delete or repurpose
715 /// the node. We don't want future request for structurally identical nodes
716 /// to return N anymore.
717 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
719 switch (N->getOpcode()) {
720 case ISD::HANDLENODE: return false; // noop.
722 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
723 "Cond code doesn't exist!");
724 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
725 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
727 case ISD::ExternalSymbol:
728 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
730 case ISD::TargetExternalSymbol: {
731 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
732 Erased = TargetExternalSymbols.erase(
733 std::pair<std::string,unsigned char>(ESN->getSymbol(),
734 ESN->getTargetFlags()));
737 case ISD::VALUETYPE: {
738 EVT VT = cast<VTSDNode>(N)->getVT();
739 if (VT.isExtended()) {
740 Erased = ExtendedValueTypeNodes.erase(VT);
742 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
743 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
748 // Remove it from the CSE Map.
749 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
750 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
751 Erased = CSEMap.RemoveNode(N);
755 // Verify that the node was actually in one of the CSE maps, unless it has a
756 // flag result (which cannot be CSE'd) or is one of the special cases that are
757 // not subject to CSE.
758 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
759 !N->isMachineOpcode() && !doNotCSE(N)) {
762 llvm_unreachable("Node is not in map!");
768 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
769 /// maps and modified in place. Add it back to the CSE maps, unless an identical
770 /// node already exists, in which case transfer all its users to the existing
771 /// node. This transfer can potentially trigger recursive merging.
774 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
775 // For node types that aren't CSE'd, just act as if no identical node
778 SDNode *Existing = CSEMap.GetOrInsertNode(N);
780 // If there was already an existing matching node, use ReplaceAllUsesWith
781 // to replace the dead one with the existing one. This can cause
782 // recursive merging of other unrelated nodes down the line.
783 ReplaceAllUsesWith(N, Existing);
785 // N is now dead. Inform the listeners and delete it.
786 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
787 DUL->NodeDeleted(N, Existing);
788 DeleteNodeNotInCSEMaps(N);
793 // If the node doesn't already exist, we updated it. Inform listeners.
794 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
798 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
799 /// were replaced with those specified. If this node is never memoized,
800 /// return null, otherwise return a pointer to the slot it would take. If a
801 /// node already exists with these operands, the slot will be non-null.
802 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
807 SDValue Ops[] = { Op };
809 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
810 AddNodeIDCustom(ID, N);
811 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
815 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
816 /// were replaced with those specified. If this node is never memoized,
817 /// return null, otherwise return a pointer to the slot it would take. If a
818 /// node already exists with these operands, the slot will be non-null.
819 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
820 SDValue Op1, SDValue Op2,
825 SDValue Ops[] = { Op1, Op2 };
827 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
828 AddNodeIDCustom(ID, N);
829 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
834 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
835 /// were replaced with those specified. If this node is never memoized,
836 /// return null, otherwise return a pointer to the slot it would take. If a
837 /// node already exists with these operands, the slot will be non-null.
838 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
844 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
845 AddNodeIDCustom(ID, N);
846 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
851 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
852 static void VerifyNodeCommon(SDNode *N) {
853 switch (N->getOpcode()) {
856 case ISD::BUILD_PAIR: {
857 EVT VT = N->getValueType(0);
858 assert(N->getNumValues() == 1 && "Too many results!");
859 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
860 "Wrong return type!");
861 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
862 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
863 "Mismatched operand types!");
864 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
865 "Wrong operand type!");
866 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
867 "Wrong return type size");
870 case ISD::BUILD_VECTOR: {
871 assert(N->getNumValues() == 1 && "Too many results!");
872 assert(N->getValueType(0).isVector() && "Wrong return type!");
873 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
874 "Wrong number of operands!");
875 EVT EltVT = N->getValueType(0).getVectorElementType();
876 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
877 assert((I->getValueType() == EltVT ||
878 (EltVT.isInteger() && I->getValueType().isInteger() &&
879 EltVT.bitsLE(I->getValueType()))) &&
880 "Wrong operand type!");
881 assert(I->getValueType() == N->getOperand(0).getValueType() &&
882 "Operands must all have the same type");
889 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
890 static void VerifySDNode(SDNode *N) {
891 // The SDNode allocators cannot be used to allocate nodes with fields that are
892 // not present in an SDNode!
893 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
894 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
895 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
896 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
897 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
898 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
899 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
900 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
901 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
902 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
903 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
904 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
905 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
906 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
907 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
908 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
909 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
910 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
911 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
916 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
918 static void VerifyMachineNode(SDNode *N) {
919 // The MachineNode allocators cannot be used to allocate nodes with fields
920 // that are not present in a MachineNode!
921 // Currently there are no such nodes.
927 /// getEVTAlignment - Compute the default alignment value for the
930 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
931 Type *Ty = VT == MVT::iPTR ?
932 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
933 VT.getTypeForEVT(*getContext());
935 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
938 // EntryNode could meaningfully have debug info if we can find it...
939 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
940 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
941 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
942 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
943 UpdateListeners(nullptr) {
944 AllNodes.push_back(&EntryNode);
945 DbgInfo = new SDDbgInfo();
948 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
951 Context = &mf.getFunction()->getContext();
954 SelectionDAG::~SelectionDAG() {
955 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
960 void SelectionDAG::allnodes_clear() {
961 assert(&*AllNodes.begin() == &EntryNode);
962 AllNodes.remove(AllNodes.begin());
963 while (!AllNodes.empty())
964 DeallocateNode(AllNodes.begin());
967 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
968 SDVTList VTs, SDValue N1,
969 SDValue N2, bool nuw, bool nsw,
971 if (isBinOpWithFlags(Opcode)) {
972 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
973 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
974 FN->setHasNoUnsignedWrap(nuw);
975 FN->setHasNoSignedWrap(nsw);
976 FN->setIsExact(exact);
981 BinarySDNode *N = new (NodeAllocator)
982 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
986 void SelectionDAG::clear() {
988 OperandAllocator.Reset();
991 ExtendedValueTypeNodes.clear();
992 ExternalSymbols.clear();
993 TargetExternalSymbols.clear();
994 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
995 static_cast<CondCodeSDNode*>(nullptr));
996 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
997 static_cast<SDNode*>(nullptr));
999 EntryNode.UseList = nullptr;
1000 AllNodes.push_back(&EntryNode);
1001 Root = getEntryNode();
1005 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1006 return VT.bitsGT(Op.getValueType()) ?
1007 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1008 getNode(ISD::TRUNCATE, DL, VT, Op);
1011 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1012 return VT.bitsGT(Op.getValueType()) ?
1013 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1014 getNode(ISD::TRUNCATE, DL, VT, Op);
1017 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1018 return VT.bitsGT(Op.getValueType()) ?
1019 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1020 getNode(ISD::TRUNCATE, DL, VT, Op);
1023 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1025 if (VT.bitsLE(Op.getValueType()))
1026 return getNode(ISD::TRUNCATE, SL, VT, Op);
1028 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1029 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1032 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1033 assert(!VT.isVector() &&
1034 "getZeroExtendInReg should use the vector element type instead of "
1035 "the vector type!");
1036 if (Op.getValueType() == VT) return Op;
1037 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1038 APInt Imm = APInt::getLowBitsSet(BitWidth,
1039 VT.getSizeInBits());
1040 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1041 getConstant(Imm, Op.getValueType()));
1044 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1045 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1046 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1047 "The sizes of the input and result must match in order to perform the "
1048 "extend in-register.");
1049 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1050 "The destination vector type must have fewer lanes than the input.");
1051 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1054 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1055 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1056 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1057 "The sizes of the input and result must match in order to perform the "
1058 "extend in-register.");
1059 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1060 "The destination vector type must have fewer lanes than the input.");
1061 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1064 SDValue SelectionDAG::getZeroExtendVectorInReg(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::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1074 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1076 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1077 EVT EltVT = VT.getScalarType();
1079 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1080 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1083 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1084 EVT EltVT = VT.getScalarType();
1086 switch (TLI->getBooleanContents(VT)) {
1087 case TargetLowering::ZeroOrOneBooleanContent:
1088 case TargetLowering::UndefinedBooleanContent:
1089 TrueValue = getConstant(1, VT);
1091 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1092 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1096 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1099 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1100 EVT EltVT = VT.getScalarType();
1101 assert((EltVT.getSizeInBits() >= 64 ||
1102 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1103 "getConstant with a uint64_t value that doesn't fit in the type!");
1104 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1107 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1109 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1112 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1114 assert(VT.isInteger() && "Cannot create FP integer constant!");
1116 EVT EltVT = VT.getScalarType();
1117 const ConstantInt *Elt = &Val;
1119 const TargetLowering *TLI = TM.getTargetLowering();
1121 // In some cases the vector type is legal but the element type is illegal and
1122 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1123 // inserted value (the type does not need to match the vector element type).
1124 // Any extra bits introduced will be truncated away.
1125 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1126 TargetLowering::TypePromoteInteger) {
1127 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1128 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1129 Elt = ConstantInt::get(*getContext(), NewVal);
1131 // In other cases the element type is illegal and needs to be expanded, for
1132 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1133 // the value into n parts and use a vector type with n-times the elements.
1134 // Then bitcast to the type requested.
1135 // Legalizing constants too early makes the DAGCombiner's job harder so we
1136 // only legalize if the DAG tells us we must produce legal types.
1137 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1138 TLI->getTypeAction(*getContext(), EltVT) ==
1139 TargetLowering::TypeExpandInteger) {
1140 APInt NewVal = Elt->getValue();
1141 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1142 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1143 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1144 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1146 // Check the temporary vector is the correct size. If this fails then
1147 // getTypeToTransformTo() probably returned a type whose size (in bits)
1148 // isn't a power-of-2 factor of the requested type size.
1149 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1151 SmallVector<SDValue, 2> EltParts;
1152 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1153 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1154 .trunc(ViaEltSizeInBits),
1155 ViaEltVT, isT, isO));
1158 // EltParts is currently in little endian order. If we actually want
1159 // big-endian order then reverse it now.
1160 if (TLI->isBigEndian())
1161 std::reverse(EltParts.begin(), EltParts.end());
1163 // The elements must be reversed when the element order is different
1164 // to the endianness of the elements (because the BITCAST is itself a
1165 // vector shuffle in this situation). However, we do not need any code to
1166 // perform this reversal because getConstant() is producing a vector
1168 // This situation occurs in MIPS MSA.
1170 SmallVector<SDValue, 8> Ops;
1171 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1172 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1174 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1175 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1180 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1181 "APInt size does not match type size!");
1182 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1183 FoldingSetNodeID ID;
1184 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1188 SDNode *N = nullptr;
1189 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1191 return SDValue(N, 0);
1194 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1195 CSEMap.InsertNode(N, IP);
1196 AllNodes.push_back(N);
1199 SDValue Result(N, 0);
1200 if (VT.isVector()) {
1201 SmallVector<SDValue, 8> Ops;
1202 Ops.assign(VT.getVectorNumElements(), Result);
1203 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1208 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1209 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1213 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1214 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1217 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1218 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1220 EVT EltVT = VT.getScalarType();
1222 // Do the map lookup using the actual bit pattern for the floating point
1223 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1224 // we don't have issues with SNANs.
1225 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1226 FoldingSetNodeID ID;
1227 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1230 SDNode *N = nullptr;
1231 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1233 return SDValue(N, 0);
1236 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1237 CSEMap.InsertNode(N, IP);
1238 AllNodes.push_back(N);
1241 SDValue Result(N, 0);
1242 if (VT.isVector()) {
1243 SmallVector<SDValue, 8> Ops;
1244 Ops.assign(VT.getVectorNumElements(), Result);
1245 // FIXME SDLoc info might be appropriate here
1246 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1251 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1252 EVT EltVT = VT.getScalarType();
1253 if (EltVT==MVT::f32)
1254 return getConstantFP(APFloat((float)Val), VT, isTarget);
1255 else if (EltVT==MVT::f64)
1256 return getConstantFP(APFloat(Val), VT, isTarget);
1257 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1260 APFloat apf = APFloat(Val);
1261 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1263 return getConstantFP(apf, VT, isTarget);
1265 llvm_unreachable("Unsupported type in getConstantFP");
1268 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1269 EVT VT, int64_t Offset,
1271 unsigned char TargetFlags) {
1272 assert((TargetFlags == 0 || isTargetGA) &&
1273 "Cannot set target flags on target-independent globals");
1274 const TargetLowering *TLI = TM.getTargetLowering();
1276 // Truncate (with sign-extension) the offset value to the pointer size.
1277 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1279 Offset = SignExtend64(Offset, BitWidth);
1282 if (GV->isThreadLocal())
1283 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1285 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1287 FoldingSetNodeID ID;
1288 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1290 ID.AddInteger(Offset);
1291 ID.AddInteger(TargetFlags);
1292 ID.AddInteger(GV->getType()->getAddressSpace());
1294 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1295 return SDValue(E, 0);
1297 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1298 DL.getDebugLoc(), GV, VT,
1299 Offset, TargetFlags);
1300 CSEMap.InsertNode(N, IP);
1301 AllNodes.push_back(N);
1302 return SDValue(N, 0);
1305 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1306 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1307 FoldingSetNodeID ID;
1308 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1311 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1312 return SDValue(E, 0);
1314 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1315 CSEMap.InsertNode(N, IP);
1316 AllNodes.push_back(N);
1317 return SDValue(N, 0);
1320 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1321 unsigned char TargetFlags) {
1322 assert((TargetFlags == 0 || isTarget) &&
1323 "Cannot set target flags on target-independent jump tables");
1324 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1325 FoldingSetNodeID ID;
1326 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1328 ID.AddInteger(TargetFlags);
1330 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1331 return SDValue(E, 0);
1333 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1335 CSEMap.InsertNode(N, IP);
1336 AllNodes.push_back(N);
1337 return SDValue(N, 0);
1340 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1341 unsigned Alignment, int Offset,
1343 unsigned char TargetFlags) {
1344 assert((TargetFlags == 0 || isTarget) &&
1345 "Cannot set target flags on target-independent globals");
1348 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1349 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1350 FoldingSetNodeID ID;
1351 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1352 ID.AddInteger(Alignment);
1353 ID.AddInteger(Offset);
1355 ID.AddInteger(TargetFlags);
1357 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1358 return SDValue(E, 0);
1360 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1361 Alignment, TargetFlags);
1362 CSEMap.InsertNode(N, IP);
1363 AllNodes.push_back(N);
1364 return SDValue(N, 0);
1368 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1369 unsigned Alignment, int Offset,
1371 unsigned char TargetFlags) {
1372 assert((TargetFlags == 0 || isTarget) &&
1373 "Cannot set target flags on target-independent globals");
1376 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1377 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1378 FoldingSetNodeID ID;
1379 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1380 ID.AddInteger(Alignment);
1381 ID.AddInteger(Offset);
1382 C->addSelectionDAGCSEId(ID);
1383 ID.AddInteger(TargetFlags);
1385 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1386 return SDValue(E, 0);
1388 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1389 Alignment, TargetFlags);
1390 CSEMap.InsertNode(N, IP);
1391 AllNodes.push_back(N);
1392 return SDValue(N, 0);
1395 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1396 unsigned char TargetFlags) {
1397 FoldingSetNodeID ID;
1398 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1399 ID.AddInteger(Index);
1400 ID.AddInteger(Offset);
1401 ID.AddInteger(TargetFlags);
1403 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1404 return SDValue(E, 0);
1406 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1408 CSEMap.InsertNode(N, IP);
1409 AllNodes.push_back(N);
1410 return SDValue(N, 0);
1413 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1414 FoldingSetNodeID ID;
1415 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1418 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1419 return SDValue(E, 0);
1421 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1422 CSEMap.InsertNode(N, IP);
1423 AllNodes.push_back(N);
1424 return SDValue(N, 0);
1427 SDValue SelectionDAG::getValueType(EVT VT) {
1428 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1429 ValueTypeNodes.size())
1430 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1432 SDNode *&N = VT.isExtended() ?
1433 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1435 if (N) return SDValue(N, 0);
1436 N = new (NodeAllocator) VTSDNode(VT);
1437 AllNodes.push_back(N);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1442 SDNode *&N = ExternalSymbols[Sym];
1443 if (N) return SDValue(N, 0);
1444 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1445 AllNodes.push_back(N);
1446 return SDValue(N, 0);
1449 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1450 unsigned char TargetFlags) {
1452 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1454 if (N) return SDValue(N, 0);
1455 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1456 AllNodes.push_back(N);
1457 return SDValue(N, 0);
1460 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1461 if ((unsigned)Cond >= CondCodeNodes.size())
1462 CondCodeNodes.resize(Cond+1);
1464 if (!CondCodeNodes[Cond]) {
1465 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1466 CondCodeNodes[Cond] = N;
1467 AllNodes.push_back(N);
1470 return SDValue(CondCodeNodes[Cond], 0);
1473 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1474 // the shuffle mask M that point at N1 to point at N2, and indices that point
1475 // N2 to point at N1.
1476 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1478 int NElts = M.size();
1479 for (int i = 0; i != NElts; ++i) {
1487 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1488 SDValue N2, const int *Mask) {
1489 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1490 "Invalid VECTOR_SHUFFLE");
1492 // Canonicalize shuffle undef, undef -> undef
1493 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1494 return getUNDEF(VT);
1496 // Validate that all indices in Mask are within the range of the elements
1497 // input to the shuffle.
1498 unsigned NElts = VT.getVectorNumElements();
1499 SmallVector<int, 8> MaskVec;
1500 for (unsigned i = 0; i != NElts; ++i) {
1501 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1502 MaskVec.push_back(Mask[i]);
1505 // Canonicalize shuffle v, v -> v, undef
1508 for (unsigned i = 0; i != NElts; ++i)
1509 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1512 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1513 if (N1.getOpcode() == ISD::UNDEF)
1514 commuteShuffle(N1, N2, MaskVec);
1516 // Canonicalize all index into lhs, -> shuffle lhs, undef
1517 // Canonicalize all index into rhs, -> shuffle rhs, undef
1518 bool AllLHS = true, AllRHS = true;
1519 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1520 for (unsigned i = 0; i != NElts; ++i) {
1521 if (MaskVec[i] >= (int)NElts) {
1526 } else if (MaskVec[i] >= 0) {
1530 if (AllLHS && AllRHS)
1531 return getUNDEF(VT);
1532 if (AllLHS && !N2Undef)
1536 commuteShuffle(N1, N2, MaskVec);
1538 // Reset our undef status after accounting for the mask.
1539 N2Undef = N2.getOpcode() == ISD::UNDEF;
1540 // Re-check whether both sides ended up undef.
1541 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1542 return getUNDEF(VT);
1544 // If Identity shuffle return that node.
1545 bool Identity = true;
1546 for (unsigned i = 0; i != NElts; ++i) {
1547 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1549 if (Identity && NElts)
1552 // Shuffling a constant splat doesn't change the result.
1556 // Look through any bitcasts. We check that these don't change the number
1557 // (and size) of elements and just changes their types.
1558 while (V.getOpcode() == ISD::BITCAST)
1559 V = V->getOperand(0);
1561 // A splat should always show up as a build vector node.
1562 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1563 BitVector UndefElements;
1564 SDValue Splat = BV->getSplatValue(&UndefElements);
1565 // If this is a splat of an undef, shuffling it is also undef.
1566 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1567 return getUNDEF(VT);
1569 // We only have a splat which can skip shuffles if there is a splatted
1570 // value and no undef lanes rearranged by the shuffle.
1571 if (Splat && UndefElements.none()) {
1572 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1573 // number of elements match or the value splatted is a zero constant.
1574 if (V.getValueType().getVectorNumElements() ==
1575 VT.getVectorNumElements())
1577 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1578 if (C->isNullValue())
1584 FoldingSetNodeID ID;
1585 SDValue Ops[2] = { N1, N2 };
1586 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1587 for (unsigned i = 0; i != NElts; ++i)
1588 ID.AddInteger(MaskVec[i]);
1591 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1592 return SDValue(E, 0);
1594 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1595 // SDNode doesn't have access to it. This memory will be "leaked" when
1596 // the node is deallocated, but recovered when the NodeAllocator is released.
1597 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1598 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1600 ShuffleVectorSDNode *N =
1601 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1602 dl.getDebugLoc(), N1, N2,
1604 CSEMap.InsertNode(N, IP);
1605 AllNodes.push_back(N);
1606 return SDValue(N, 0);
1609 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1610 MVT VT = SV.getSimpleValueType(0);
1611 unsigned NumElems = VT.getVectorNumElements();
1612 SmallVector<int, 8> MaskVec;
1614 for (unsigned i = 0; i != NumElems; ++i) {
1615 int Idx = SV.getMaskElt(i);
1617 if (Idx < (int)NumElems)
1622 MaskVec.push_back(Idx);
1625 SDValue Op0 = SV.getOperand(0);
1626 SDValue Op1 = SV.getOperand(1);
1627 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1630 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1631 SDValue Val, SDValue DTy,
1632 SDValue STy, SDValue Rnd, SDValue Sat,
1633 ISD::CvtCode Code) {
1634 // If the src and dest types are the same and the conversion is between
1635 // integer types of the same sign or two floats, no conversion is necessary.
1637 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1640 FoldingSetNodeID ID;
1641 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1642 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1644 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1645 return SDValue(E, 0);
1647 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1650 CSEMap.InsertNode(N, IP);
1651 AllNodes.push_back(N);
1652 return SDValue(N, 0);
1655 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1656 FoldingSetNodeID ID;
1657 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1658 ID.AddInteger(RegNo);
1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1661 return SDValue(E, 0);
1663 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1664 CSEMap.InsertNode(N, IP);
1665 AllNodes.push_back(N);
1666 return SDValue(N, 0);
1669 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1670 FoldingSetNodeID ID;
1671 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1672 ID.AddPointer(RegMask);
1674 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1675 return SDValue(E, 0);
1677 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1678 CSEMap.InsertNode(N, IP);
1679 AllNodes.push_back(N);
1680 return SDValue(N, 0);
1683 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1684 FoldingSetNodeID ID;
1685 SDValue Ops[] = { Root };
1686 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1687 ID.AddPointer(Label);
1689 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1690 return SDValue(E, 0);
1692 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1693 dl.getDebugLoc(), Root, Label);
1694 CSEMap.InsertNode(N, IP);
1695 AllNodes.push_back(N);
1696 return SDValue(N, 0);
1700 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1703 unsigned char TargetFlags) {
1704 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1706 FoldingSetNodeID ID;
1707 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1709 ID.AddInteger(Offset);
1710 ID.AddInteger(TargetFlags);
1712 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1713 return SDValue(E, 0);
1715 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1717 CSEMap.InsertNode(N, IP);
1718 AllNodes.push_back(N);
1719 return SDValue(N, 0);
1722 SDValue SelectionDAG::getSrcValue(const Value *V) {
1723 assert((!V || V->getType()->isPointerTy()) &&
1724 "SrcValue is not a pointer?");
1726 FoldingSetNodeID ID;
1727 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1731 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1732 return SDValue(E, 0);
1734 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1735 CSEMap.InsertNode(N, IP);
1736 AllNodes.push_back(N);
1737 return SDValue(N, 0);
1740 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1741 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1742 FoldingSetNodeID ID;
1743 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1747 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1748 return SDValue(E, 0);
1750 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1751 CSEMap.InsertNode(N, IP);
1752 AllNodes.push_back(N);
1753 return SDValue(N, 0);
1756 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1757 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1758 unsigned SrcAS, unsigned DestAS) {
1759 SDValue Ops[] = {Ptr};
1760 FoldingSetNodeID ID;
1761 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1762 ID.AddInteger(SrcAS);
1763 ID.AddInteger(DestAS);
1766 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1767 return SDValue(E, 0);
1769 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1771 VT, Ptr, SrcAS, DestAS);
1772 CSEMap.InsertNode(N, IP);
1773 AllNodes.push_back(N);
1774 return SDValue(N, 0);
1777 /// getShiftAmountOperand - Return the specified value casted to
1778 /// the target's desired shift amount type.
1779 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1780 EVT OpTy = Op.getValueType();
1781 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1782 if (OpTy == ShTy || OpTy.isVector()) return Op;
1784 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1785 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1788 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1789 /// specified value type.
1790 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1791 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1792 unsigned ByteSize = VT.getStoreSize();
1793 Type *Ty = VT.getTypeForEVT(*getContext());
1794 const TargetLowering *TLI = TM.getTargetLowering();
1795 unsigned StackAlign =
1796 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1798 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1799 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1802 /// CreateStackTemporary - Create a stack temporary suitable for holding
1803 /// either of the specified value types.
1804 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1805 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1806 VT2.getStoreSizeInBits())/8;
1807 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1808 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1809 const TargetLowering *TLI = TM.getTargetLowering();
1810 const DataLayout *TD = TLI->getDataLayout();
1811 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1812 TD->getPrefTypeAlignment(Ty2));
1814 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1815 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1816 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1819 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1820 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1821 // These setcc operations always fold.
1825 case ISD::SETFALSE2: return getConstant(0, VT);
1827 case ISD::SETTRUE2: {
1828 const TargetLowering *TLI = TM.getTargetLowering();
1829 TargetLowering::BooleanContent Cnt =
1830 TLI->getBooleanContents(N1->getValueType(0));
1832 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1845 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1849 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1850 const APInt &C2 = N2C->getAPIntValue();
1851 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1852 const APInt &C1 = N1C->getAPIntValue();
1855 default: llvm_unreachable("Unknown integer setcc!");
1856 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1857 case ISD::SETNE: return getConstant(C1 != C2, VT);
1858 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1859 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1860 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1861 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1862 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1863 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1864 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1865 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1869 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1870 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1871 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1874 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1875 return getUNDEF(VT);
1877 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1878 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1879 return getUNDEF(VT);
1881 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1882 R==APFloat::cmpLessThan, VT);
1883 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1884 return getUNDEF(VT);
1886 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1887 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1888 return getUNDEF(VT);
1890 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1891 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1892 return getUNDEF(VT);
1894 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1895 R==APFloat::cmpEqual, VT);
1896 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1897 return getUNDEF(VT);
1899 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1900 R==APFloat::cmpEqual, VT);
1901 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1902 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1903 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1904 R==APFloat::cmpEqual, VT);
1905 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1906 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1907 R==APFloat::cmpLessThan, VT);
1908 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1909 R==APFloat::cmpUnordered, VT);
1910 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1911 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1914 // Ensure that the constant occurs on the RHS.
1915 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1916 MVT CompVT = N1.getValueType().getSimpleVT();
1917 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1920 return getSetCC(dl, VT, N2, N1, SwappedCond);
1924 // Could not fold it.
1928 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1929 /// use this predicate to simplify operations downstream.
1930 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1931 // This predicate is not safe for vector operations.
1932 if (Op.getValueType().isVector())
1935 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1936 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1939 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1940 /// this predicate to simplify operations downstream. Mask is known to be zero
1941 /// for bits that V cannot have.
1942 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1943 unsigned Depth) const {
1944 APInt KnownZero, KnownOne;
1945 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1946 return (KnownZero & Mask) == Mask;
1949 /// Determine which bits of Op are known to be either zero or one and return
1950 /// them in the KnownZero/KnownOne bitsets.
1951 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1952 APInt &KnownOne, unsigned Depth) const {
1953 const TargetLowering *TLI = TM.getTargetLowering();
1954 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1956 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1958 return; // Limit search depth.
1960 APInt KnownZero2, KnownOne2;
1962 switch (Op.getOpcode()) {
1964 // We know all of the bits for a constant!
1965 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1966 KnownZero = ~KnownOne;
1969 // If either the LHS or the RHS are Zero, the result is zero.
1970 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1971 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1973 // Output known-1 bits are only known if set in both the LHS & RHS.
1974 KnownOne &= KnownOne2;
1975 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1976 KnownZero |= KnownZero2;
1979 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1980 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1982 // Output known-0 bits are only known if clear in both the LHS & RHS.
1983 KnownZero &= KnownZero2;
1984 // Output known-1 are known to be set if set in either the LHS | RHS.
1985 KnownOne |= KnownOne2;
1988 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1989 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1991 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1992 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1993 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1994 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1995 KnownZero = KnownZeroOut;
1999 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2000 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2002 // If low bits are zero in either operand, output low known-0 bits.
2003 // Also compute a conserative estimate for high known-0 bits.
2004 // More trickiness is possible, but this is sufficient for the
2005 // interesting case of alignment computation.
2006 KnownOne.clearAllBits();
2007 unsigned TrailZ = KnownZero.countTrailingOnes() +
2008 KnownZero2.countTrailingOnes();
2009 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2010 KnownZero2.countLeadingOnes(),
2011 BitWidth) - BitWidth;
2013 TrailZ = std::min(TrailZ, BitWidth);
2014 LeadZ = std::min(LeadZ, BitWidth);
2015 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2016 APInt::getHighBitsSet(BitWidth, LeadZ);
2020 // For the purposes of computing leading zeros we can conservatively
2021 // treat a udiv as a logical right shift by the power of 2 known to
2022 // be less than the denominator.
2023 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2024 unsigned LeadZ = KnownZero2.countLeadingOnes();
2026 KnownOne2.clearAllBits();
2027 KnownZero2.clearAllBits();
2028 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2029 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2030 if (RHSUnknownLeadingOnes != BitWidth)
2031 LeadZ = std::min(BitWidth,
2032 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2034 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2038 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2039 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2041 // Only known if known in both the LHS and RHS.
2042 KnownOne &= KnownOne2;
2043 KnownZero &= KnownZero2;
2045 case ISD::SELECT_CC:
2046 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2047 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2049 // Only known if known in both the LHS and RHS.
2050 KnownOne &= KnownOne2;
2051 KnownZero &= KnownZero2;
2059 if (Op.getResNo() != 1)
2061 // The boolean result conforms to getBooleanContents.
2062 // If we know the result of a setcc has the top bits zero, use this info.
2063 // We know that we have an integer-based boolean since these operations
2064 // are only available for integer.
2065 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2066 TargetLowering::ZeroOrOneBooleanContent &&
2068 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2071 // If we know the result of a setcc has the top bits zero, use this info.
2072 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2073 TargetLowering::ZeroOrOneBooleanContent &&
2075 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2078 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2079 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2080 unsigned ShAmt = SA->getZExtValue();
2082 // If the shift count is an invalid immediate, don't do anything.
2083 if (ShAmt >= BitWidth)
2086 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2087 KnownZero <<= ShAmt;
2089 // low bits known zero.
2090 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2094 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2095 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2096 unsigned ShAmt = SA->getZExtValue();
2098 // If the shift count is an invalid immediate, don't do anything.
2099 if (ShAmt >= BitWidth)
2102 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2103 KnownZero = KnownZero.lshr(ShAmt);
2104 KnownOne = KnownOne.lshr(ShAmt);
2106 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2107 KnownZero |= HighBits; // High bits known zero.
2111 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2112 unsigned ShAmt = SA->getZExtValue();
2114 // If the shift count is an invalid immediate, don't do anything.
2115 if (ShAmt >= BitWidth)
2118 // If any of the demanded bits are produced by the sign extension, we also
2119 // demand the input sign bit.
2120 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2122 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2123 KnownZero = KnownZero.lshr(ShAmt);
2124 KnownOne = KnownOne.lshr(ShAmt);
2126 // Handle the sign bits.
2127 APInt SignBit = APInt::getSignBit(BitWidth);
2128 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2130 if (KnownZero.intersects(SignBit)) {
2131 KnownZero |= HighBits; // New bits are known zero.
2132 } else if (KnownOne.intersects(SignBit)) {
2133 KnownOne |= HighBits; // New bits are known one.
2137 case ISD::SIGN_EXTEND_INREG: {
2138 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2139 unsigned EBits = EVT.getScalarType().getSizeInBits();
2141 // Sign extension. Compute the demanded bits in the result that are not
2142 // present in the input.
2143 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2145 APInt InSignBit = APInt::getSignBit(EBits);
2146 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2148 // If the sign extended bits are demanded, we know that the sign
2150 InSignBit = InSignBit.zext(BitWidth);
2151 if (NewBits.getBoolValue())
2152 InputDemandedBits |= InSignBit;
2154 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2155 KnownOne &= InputDemandedBits;
2156 KnownZero &= InputDemandedBits;
2158 // If the sign bit of the input is known set or clear, then we know the
2159 // top bits of the result.
2160 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2161 KnownZero |= NewBits;
2162 KnownOne &= ~NewBits;
2163 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2164 KnownOne |= NewBits;
2165 KnownZero &= ~NewBits;
2166 } else { // Input sign bit unknown
2167 KnownZero &= ~NewBits;
2168 KnownOne &= ~NewBits;
2173 case ISD::CTTZ_ZERO_UNDEF:
2175 case ISD::CTLZ_ZERO_UNDEF:
2177 unsigned LowBits = Log2_32(BitWidth)+1;
2178 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2179 KnownOne.clearAllBits();
2183 LoadSDNode *LD = cast<LoadSDNode>(Op);
2184 // If this is a ZEXTLoad and we are looking at the loaded value.
2185 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2186 EVT VT = LD->getMemoryVT();
2187 unsigned MemBits = VT.getScalarType().getSizeInBits();
2188 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2189 } else if (const MDNode *Ranges = LD->getRanges()) {
2190 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2194 case ISD::ZERO_EXTEND: {
2195 EVT InVT = Op.getOperand(0).getValueType();
2196 unsigned InBits = InVT.getScalarType().getSizeInBits();
2197 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2198 KnownZero = KnownZero.trunc(InBits);
2199 KnownOne = KnownOne.trunc(InBits);
2200 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2201 KnownZero = KnownZero.zext(BitWidth);
2202 KnownOne = KnownOne.zext(BitWidth);
2203 KnownZero |= NewBits;
2206 case ISD::SIGN_EXTEND: {
2207 EVT InVT = Op.getOperand(0).getValueType();
2208 unsigned InBits = InVT.getScalarType().getSizeInBits();
2209 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2211 KnownZero = KnownZero.trunc(InBits);
2212 KnownOne = KnownOne.trunc(InBits);
2213 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2215 // Note if the sign bit is known to be zero or one.
2216 bool SignBitKnownZero = KnownZero.isNegative();
2217 bool SignBitKnownOne = KnownOne.isNegative();
2219 KnownZero = KnownZero.zext(BitWidth);
2220 KnownOne = KnownOne.zext(BitWidth);
2222 // If the sign bit is known zero or one, the top bits match.
2223 if (SignBitKnownZero)
2224 KnownZero |= NewBits;
2225 else if (SignBitKnownOne)
2226 KnownOne |= NewBits;
2229 case ISD::ANY_EXTEND: {
2230 EVT InVT = Op.getOperand(0).getValueType();
2231 unsigned InBits = InVT.getScalarType().getSizeInBits();
2232 KnownZero = KnownZero.trunc(InBits);
2233 KnownOne = KnownOne.trunc(InBits);
2234 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2235 KnownZero = KnownZero.zext(BitWidth);
2236 KnownOne = KnownOne.zext(BitWidth);
2239 case ISD::TRUNCATE: {
2240 EVT InVT = Op.getOperand(0).getValueType();
2241 unsigned InBits = InVT.getScalarType().getSizeInBits();
2242 KnownZero = KnownZero.zext(InBits);
2243 KnownOne = KnownOne.zext(InBits);
2244 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2245 KnownZero = KnownZero.trunc(BitWidth);
2246 KnownOne = KnownOne.trunc(BitWidth);
2249 case ISD::AssertZext: {
2250 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2251 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2252 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2253 KnownZero |= (~InMask);
2254 KnownOne &= (~KnownZero);
2258 // All bits are zero except the low bit.
2259 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2263 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2264 // We know that the top bits of C-X are clear if X contains less bits
2265 // than C (i.e. no wrap-around can happen). For example, 20-X is
2266 // positive if we can prove that X is >= 0 and < 16.
2267 if (CLHS->getAPIntValue().isNonNegative()) {
2268 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2269 // NLZ can't be BitWidth with no sign bit
2270 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2271 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2273 // If all of the MaskV bits are known to be zero, then we know the
2274 // output top bits are zero, because we now know that the output is
2276 if ((KnownZero2 & MaskV) == MaskV) {
2277 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2278 // Top bits known zero.
2279 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2287 // Output known-0 bits are known if clear or set in both the low clear bits
2288 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2289 // low 3 bits clear.
2290 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2291 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2293 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2294 KnownZeroOut = std::min(KnownZeroOut,
2295 KnownZero2.countTrailingOnes());
2297 if (Op.getOpcode() == ISD::ADD) {
2298 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2302 // With ADDE, a carry bit may be added in, so we can only use this
2303 // information if we know (at least) that the low two bits are clear. We
2304 // then return to the caller that the low bit is unknown but that other bits
2306 if (KnownZeroOut >= 2) // ADDE
2307 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2311 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2312 const APInt &RA = Rem->getAPIntValue().abs();
2313 if (RA.isPowerOf2()) {
2314 APInt LowBits = RA - 1;
2315 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2317 // The low bits of the first operand are unchanged by the srem.
2318 KnownZero = KnownZero2 & LowBits;
2319 KnownOne = KnownOne2 & LowBits;
2321 // If the first operand is non-negative or has all low bits zero, then
2322 // the upper bits are all zero.
2323 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2324 KnownZero |= ~LowBits;
2326 // If the first operand is negative and not all low bits are zero, then
2327 // the upper bits are all one.
2328 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2329 KnownOne |= ~LowBits;
2330 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2335 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2336 const APInt &RA = Rem->getAPIntValue();
2337 if (RA.isPowerOf2()) {
2338 APInt LowBits = (RA - 1);
2339 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2341 // The upper bits are all zero, the lower ones are unchanged.
2342 KnownZero = KnownZero2 | ~LowBits;
2343 KnownOne = KnownOne2 & LowBits;
2348 // Since the result is less than or equal to either operand, any leading
2349 // zero bits in either operand must also exist in the result.
2350 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2351 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2353 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2354 KnownZero2.countLeadingOnes());
2355 KnownOne.clearAllBits();
2356 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2359 case ISD::FrameIndex:
2360 case ISD::TargetFrameIndex:
2361 if (unsigned Align = InferPtrAlignment(Op)) {
2362 // The low bits are known zero if the pointer is aligned.
2363 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2369 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2372 case ISD::INTRINSIC_WO_CHAIN:
2373 case ISD::INTRINSIC_W_CHAIN:
2374 case ISD::INTRINSIC_VOID:
2375 // Allow the target to implement this method for its nodes.
2376 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2380 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2383 /// ComputeNumSignBits - Return the number of times the sign bit of the
2384 /// register is replicated into the other bits. We know that at least 1 bit
2385 /// is always equal to the sign bit (itself), but other cases can give us
2386 /// information. For example, immediately after an "SRA X, 2", we know that
2387 /// the top 3 bits are all equal to each other, so we return 3.
2388 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2389 const TargetLowering *TLI = TM.getTargetLowering();
2390 EVT VT = Op.getValueType();
2391 assert(VT.isInteger() && "Invalid VT!");
2392 unsigned VTBits = VT.getScalarType().getSizeInBits();
2394 unsigned FirstAnswer = 1;
2397 return 1; // Limit search depth.
2399 switch (Op.getOpcode()) {
2401 case ISD::AssertSext:
2402 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2403 return VTBits-Tmp+1;
2404 case ISD::AssertZext:
2405 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2408 case ISD::Constant: {
2409 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2410 return Val.getNumSignBits();
2413 case ISD::SIGN_EXTEND:
2415 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2416 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2418 case ISD::SIGN_EXTEND_INREG:
2419 // Max of the input and what this extends.
2421 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2424 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2425 return std::max(Tmp, Tmp2);
2428 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2429 // SRA X, C -> adds C sign bits.
2430 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2431 Tmp += C->getZExtValue();
2432 if (Tmp > VTBits) Tmp = VTBits;
2436 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2437 // shl destroys sign bits.
2438 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2439 if (C->getZExtValue() >= VTBits || // Bad shift.
2440 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2441 return Tmp - C->getZExtValue();
2446 case ISD::XOR: // NOT is handled here.
2447 // Logical binary ops preserve the number of sign bits at the worst.
2448 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2450 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2451 FirstAnswer = std::min(Tmp, Tmp2);
2452 // We computed what we know about the sign bits as our first
2453 // answer. Now proceed to the generic code that uses
2454 // computeKnownBits, and pick whichever answer is better.
2459 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2460 if (Tmp == 1) return 1; // Early out.
2461 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2462 return std::min(Tmp, Tmp2);
2470 if (Op.getResNo() != 1)
2472 // The boolean result conforms to getBooleanContents. Fall through.
2473 // If setcc returns 0/-1, all bits are sign bits.
2474 // We know that we have an integer-based boolean since these operations
2475 // are only available for integer.
2476 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2477 TargetLowering::ZeroOrNegativeOneBooleanContent)
2481 // If setcc returns 0/-1, all bits are sign bits.
2482 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2483 TargetLowering::ZeroOrNegativeOneBooleanContent)
2488 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2489 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2491 // Handle rotate right by N like a rotate left by 32-N.
2492 if (Op.getOpcode() == ISD::ROTR)
2493 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2495 // If we aren't rotating out all of the known-in sign bits, return the
2496 // number that are left. This handles rotl(sext(x), 1) for example.
2497 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2498 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2502 // Add can have at most one carry bit. Thus we know that the output
2503 // is, at worst, one more bit than the inputs.
2504 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2505 if (Tmp == 1) return 1; // Early out.
2507 // Special case decrementing a value (ADD X, -1):
2508 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2509 if (CRHS->isAllOnesValue()) {
2510 APInt KnownZero, KnownOne;
2511 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2513 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2515 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2518 // If we are subtracting one from a positive number, there is no carry
2519 // out of the result.
2520 if (KnownZero.isNegative())
2524 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2525 if (Tmp2 == 1) return 1;
2526 return std::min(Tmp, Tmp2)-1;
2529 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2530 if (Tmp2 == 1) return 1;
2533 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2534 if (CLHS->isNullValue()) {
2535 APInt KnownZero, KnownOne;
2536 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2537 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2539 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2542 // If the input is known to be positive (the sign bit is known clear),
2543 // the output of the NEG has the same number of sign bits as the input.
2544 if (KnownZero.isNegative())
2547 // Otherwise, we treat this like a SUB.
2550 // Sub can have at most one carry bit. Thus we know that the output
2551 // is, at worst, one more bit than the inputs.
2552 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2553 if (Tmp == 1) return 1; // Early out.
2554 return std::min(Tmp, Tmp2)-1;
2556 // FIXME: it's tricky to do anything useful for this, but it is an important
2557 // case for targets like X86.
2561 // If we are looking at the loaded value of the SDNode.
2562 if (Op.getResNo() == 0) {
2563 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2564 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2565 unsigned ExtType = LD->getExtensionType();
2568 case ISD::SEXTLOAD: // '17' bits known
2569 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2570 return VTBits-Tmp+1;
2571 case ISD::ZEXTLOAD: // '16' bits known
2572 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2578 // Allow the target to implement this method for its nodes.
2579 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2580 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2581 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2582 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2583 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2584 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2587 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2588 // use this information.
2589 APInt KnownZero, KnownOne;
2590 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2593 if (KnownZero.isNegative()) { // sign bit is 0
2595 } else if (KnownOne.isNegative()) { // sign bit is 1;
2602 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2603 // the number of identical bits in the top of the input value.
2605 Mask <<= Mask.getBitWidth()-VTBits;
2606 // Return # leading zeros. We use 'min' here in case Val was zero before
2607 // shifting. We don't want to return '64' as for an i32 "0".
2608 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2611 /// isBaseWithConstantOffset - Return true if the specified operand is an
2612 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2613 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2614 /// semantics as an ADD. This handles the equivalence:
2615 /// X|Cst == X+Cst iff X&Cst = 0.
2616 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2617 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2618 !isa<ConstantSDNode>(Op.getOperand(1)))
2621 if (Op.getOpcode() == ISD::OR &&
2622 !MaskedValueIsZero(Op.getOperand(0),
2623 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2630 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2631 // If we're told that NaNs won't happen, assume they won't.
2632 if (getTarget().Options.NoNaNsFPMath)
2635 // If the value is a constant, we can obviously see if it is a NaN or not.
2636 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2637 return !C->getValueAPF().isNaN();
2639 // TODO: Recognize more cases here.
2644 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2645 // If the value is a constant, we can obviously see if it is a zero or not.
2646 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2647 return !C->isZero();
2649 // TODO: Recognize more cases here.
2650 switch (Op.getOpcode()) {
2653 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2654 return !C->isNullValue();
2661 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2662 // Check the obvious case.
2663 if (A == B) return true;
2665 // For for negative and positive zero.
2666 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2667 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2668 if (CA->isZero() && CB->isZero()) return true;
2670 // Otherwise they may not be equal.
2674 /// getNode - Gets or creates the specified node.
2676 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2677 FoldingSetNodeID ID;
2678 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2680 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2681 return SDValue(E, 0);
2683 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2684 DL.getDebugLoc(), getVTList(VT));
2685 CSEMap.InsertNode(N, IP);
2687 AllNodes.push_back(N);
2691 return SDValue(N, 0);
2694 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2695 EVT VT, SDValue Operand) {
2696 // Constant fold unary operations with an integer constant operand. Even
2697 // opaque constant will be folded, because the folding of unary operations
2698 // doesn't create new constants with different values. Nevertheless, the
2699 // opaque flag is preserved during folding to prevent future folding with
2701 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2702 const APInt &Val = C->getAPIntValue();
2705 case ISD::SIGN_EXTEND:
2706 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2707 C->isTargetOpcode(), C->isOpaque());
2708 case ISD::ANY_EXTEND:
2709 case ISD::ZERO_EXTEND:
2711 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2712 C->isTargetOpcode(), C->isOpaque());
2713 case ISD::UINT_TO_FP:
2714 case ISD::SINT_TO_FP: {
2715 APFloat apf(EVTToAPFloatSemantics(VT),
2716 APInt::getNullValue(VT.getSizeInBits()));
2717 (void)apf.convertFromAPInt(Val,
2718 Opcode==ISD::SINT_TO_FP,
2719 APFloat::rmNearestTiesToEven);
2720 return getConstantFP(apf, VT);
2723 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2724 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2725 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2726 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2729 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2732 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2735 case ISD::CTLZ_ZERO_UNDEF:
2736 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2739 case ISD::CTTZ_ZERO_UNDEF:
2740 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2745 // Constant fold unary operations with a floating point constant operand.
2746 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2747 APFloat V = C->getValueAPF(); // make copy
2751 return getConstantFP(V, VT);
2754 return getConstantFP(V, VT);
2756 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2757 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2758 return getConstantFP(V, VT);
2762 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2763 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2764 return getConstantFP(V, VT);
2768 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2769 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2770 return getConstantFP(V, VT);
2773 case ISD::FP_EXTEND: {
2775 // This can return overflow, underflow, or inexact; we don't care.
2776 // FIXME need to be more flexible about rounding mode.
2777 (void)V.convert(EVTToAPFloatSemantics(VT),
2778 APFloat::rmNearestTiesToEven, &ignored);
2779 return getConstantFP(V, VT);
2781 case ISD::FP_TO_SINT:
2782 case ISD::FP_TO_UINT: {
2785 assert(integerPartWidth >= 64);
2786 // FIXME need to be more flexible about rounding mode.
2787 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2788 Opcode==ISD::FP_TO_SINT,
2789 APFloat::rmTowardZero, &ignored);
2790 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2792 APInt api(VT.getSizeInBits(), x);
2793 return getConstant(api, VT);
2796 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2797 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2798 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2799 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2804 // Constant fold unary operations with a vector integer operand.
2805 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2806 if (BV->isConstant()) {
2809 // FIXME: Entirely reasonable to perform folding of other unary
2810 // operations here as the need arises.
2812 case ISD::UINT_TO_FP:
2813 case ISD::SINT_TO_FP: {
2814 SmallVector<SDValue, 8> Ops;
2815 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2816 SDValue OpN = BV->getOperand(i);
2817 // Let the above scalar folding handle the conversion of each
2819 OpN = getNode(ISD::SINT_TO_FP, DL, VT.getVectorElementType(),
2823 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2829 unsigned OpOpcode = Operand.getNode()->getOpcode();
2831 case ISD::TokenFactor:
2832 case ISD::MERGE_VALUES:
2833 case ISD::CONCAT_VECTORS:
2834 return Operand; // Factor, merge or concat of one node? No need.
2835 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2836 case ISD::FP_EXTEND:
2837 assert(VT.isFloatingPoint() &&
2838 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2839 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2840 assert((!VT.isVector() ||
2841 VT.getVectorNumElements() ==
2842 Operand.getValueType().getVectorNumElements()) &&
2843 "Vector element count mismatch!");
2844 if (Operand.getOpcode() == ISD::UNDEF)
2845 return getUNDEF(VT);
2847 case ISD::SIGN_EXTEND:
2848 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2849 "Invalid SIGN_EXTEND!");
2850 if (Operand.getValueType() == VT) return Operand; // noop extension
2851 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2852 "Invalid sext node, dst < src!");
2853 assert((!VT.isVector() ||
2854 VT.getVectorNumElements() ==
2855 Operand.getValueType().getVectorNumElements()) &&
2856 "Vector element count mismatch!");
2857 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2858 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2859 else if (OpOpcode == ISD::UNDEF)
2860 // sext(undef) = 0, because the top bits will all be the same.
2861 return getConstant(0, VT);
2863 case ISD::ZERO_EXTEND:
2864 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2865 "Invalid ZERO_EXTEND!");
2866 if (Operand.getValueType() == VT) return Operand; // noop extension
2867 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2868 "Invalid zext node, dst < src!");
2869 assert((!VT.isVector() ||
2870 VT.getVectorNumElements() ==
2871 Operand.getValueType().getVectorNumElements()) &&
2872 "Vector element count mismatch!");
2873 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2874 return getNode(ISD::ZERO_EXTEND, DL, VT,
2875 Operand.getNode()->getOperand(0));
2876 else if (OpOpcode == ISD::UNDEF)
2877 // zext(undef) = 0, because the top bits will be zero.
2878 return getConstant(0, VT);
2880 case ISD::ANY_EXTEND:
2881 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2882 "Invalid ANY_EXTEND!");
2883 if (Operand.getValueType() == VT) return Operand; // noop extension
2884 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2885 "Invalid anyext node, dst < src!");
2886 assert((!VT.isVector() ||
2887 VT.getVectorNumElements() ==
2888 Operand.getValueType().getVectorNumElements()) &&
2889 "Vector element count mismatch!");
2891 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2892 OpOpcode == ISD::ANY_EXTEND)
2893 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2894 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2895 else if (OpOpcode == ISD::UNDEF)
2896 return getUNDEF(VT);
2898 // (ext (trunx x)) -> x
2899 if (OpOpcode == ISD::TRUNCATE) {
2900 SDValue OpOp = Operand.getNode()->getOperand(0);
2901 if (OpOp.getValueType() == VT)
2906 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2907 "Invalid TRUNCATE!");
2908 if (Operand.getValueType() == VT) return Operand; // noop truncate
2909 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2910 "Invalid truncate node, src < dst!");
2911 assert((!VT.isVector() ||
2912 VT.getVectorNumElements() ==
2913 Operand.getValueType().getVectorNumElements()) &&
2914 "Vector element count mismatch!");
2915 if (OpOpcode == ISD::TRUNCATE)
2916 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2917 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2918 OpOpcode == ISD::ANY_EXTEND) {
2919 // If the source is smaller than the dest, we still need an extend.
2920 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2921 .bitsLT(VT.getScalarType()))
2922 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2923 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2924 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2925 return Operand.getNode()->getOperand(0);
2927 if (OpOpcode == ISD::UNDEF)
2928 return getUNDEF(VT);
2931 // Basic sanity checking.
2932 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2933 && "Cannot BITCAST between types of different sizes!");
2934 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2935 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2936 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2937 if (OpOpcode == ISD::UNDEF)
2938 return getUNDEF(VT);
2940 case ISD::SCALAR_TO_VECTOR:
2941 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2942 (VT.getVectorElementType() == Operand.getValueType() ||
2943 (VT.getVectorElementType().isInteger() &&
2944 Operand.getValueType().isInteger() &&
2945 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2946 "Illegal SCALAR_TO_VECTOR node!");
2947 if (OpOpcode == ISD::UNDEF)
2948 return getUNDEF(VT);
2949 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2950 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2951 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2952 Operand.getConstantOperandVal(1) == 0 &&
2953 Operand.getOperand(0).getValueType() == VT)
2954 return Operand.getOperand(0);
2957 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2958 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2959 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2960 Operand.getNode()->getOperand(0));
2961 if (OpOpcode == ISD::FNEG) // --X -> X
2962 return Operand.getNode()->getOperand(0);
2965 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2966 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2971 SDVTList VTs = getVTList(VT);
2972 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2973 FoldingSetNodeID ID;
2974 SDValue Ops[1] = { Operand };
2975 AddNodeIDNode(ID, Opcode, VTs, Ops);
2977 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2978 return SDValue(E, 0);
2980 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2981 DL.getDebugLoc(), VTs, Operand);
2982 CSEMap.InsertNode(N, IP);
2984 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2985 DL.getDebugLoc(), VTs, Operand);
2988 AllNodes.push_back(N);
2992 return SDValue(N, 0);
2995 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2996 SDNode *Cst1, SDNode *Cst2) {
2997 // If the opcode is a target-specific ISD node, there's nothing we can
2998 // do here and the operand rules may not line up with the below, so
3000 if (Opcode >= ISD::BUILTIN_OP_END)
3003 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3004 SmallVector<SDValue, 4> Outputs;
3005 EVT SVT = VT.getScalarType();
3007 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3008 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3009 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3012 if (Scalar1 && Scalar2)
3013 // Scalar instruction.
3014 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3016 // For vectors extract each constant element into Inputs so we can constant
3017 // fold them individually.
3018 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3019 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3023 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3025 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3026 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3027 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3028 if (!V1 || !V2) // Not a constant, bail.
3031 if (V1->isOpaque() || V2->isOpaque())
3034 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3035 // FIXME: This is valid and could be handled by truncating the APInts.
3036 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3039 Inputs.push_back(std::make_pair(V1, V2));
3043 // We have a number of constant values, constant fold them element by element.
3044 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3045 const APInt &C1 = Inputs[I].first->getAPIntValue();
3046 const APInt &C2 = Inputs[I].second->getAPIntValue();
3050 Outputs.push_back(getConstant(C1 + C2, SVT));
3053 Outputs.push_back(getConstant(C1 - C2, SVT));
3056 Outputs.push_back(getConstant(C1 * C2, SVT));
3059 if (!C2.getBoolValue())
3061 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3064 if (!C2.getBoolValue())
3066 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3069 if (!C2.getBoolValue())
3071 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3074 if (!C2.getBoolValue())
3076 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3079 Outputs.push_back(getConstant(C1 & C2, SVT));
3082 Outputs.push_back(getConstant(C1 | C2, SVT));
3085 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3088 Outputs.push_back(getConstant(C1 << C2, SVT));
3091 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3094 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3097 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3100 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3107 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3108 "Expected a scalar or vector!"));
3110 // Handle the scalar case first.
3112 return Outputs.back();
3114 // We may have a vector type but a scalar result. Create a splat.
3115 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3117 // Build a big vector out of the scalar elements we generated.
3118 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3121 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3122 SDValue N2, bool nuw, bool nsw, bool exact) {
3123 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3124 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3127 case ISD::TokenFactor:
3128 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3129 N2.getValueType() == MVT::Other && "Invalid token factor!");
3130 // Fold trivial token factors.
3131 if (N1.getOpcode() == ISD::EntryToken) return N2;
3132 if (N2.getOpcode() == ISD::EntryToken) return N1;
3133 if (N1 == N2) return N1;
3135 case ISD::CONCAT_VECTORS:
3136 // Concat of UNDEFs is UNDEF.
3137 if (N1.getOpcode() == ISD::UNDEF &&
3138 N2.getOpcode() == ISD::UNDEF)
3139 return getUNDEF(VT);
3141 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3142 // one big BUILD_VECTOR.
3143 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3144 N2.getOpcode() == ISD::BUILD_VECTOR) {
3145 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3146 N1.getNode()->op_end());
3147 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3148 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3152 assert(VT.isInteger() && "This operator does not apply to FP types!");
3153 assert(N1.getValueType() == N2.getValueType() &&
3154 N1.getValueType() == VT && "Binary operator types must match!");
3155 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3156 // worth handling here.
3157 if (N2C && N2C->isNullValue())
3159 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3166 assert(VT.isInteger() && "This operator does not apply to FP types!");
3167 assert(N1.getValueType() == N2.getValueType() &&
3168 N1.getValueType() == VT && "Binary operator types must match!");
3169 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3170 // it's worth handling here.
3171 if (N2C && N2C->isNullValue())
3181 assert(VT.isInteger() && "This operator does not apply to FP types!");
3182 assert(N1.getValueType() == N2.getValueType() &&
3183 N1.getValueType() == VT && "Binary operator types must match!");
3190 if (getTarget().Options.UnsafeFPMath) {
3191 if (Opcode == ISD::FADD) {
3193 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3194 if (CFP->getValueAPF().isZero())
3197 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3198 if (CFP->getValueAPF().isZero())
3200 } else if (Opcode == ISD::FSUB) {
3202 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3203 if (CFP->getValueAPF().isZero())
3205 } else if (Opcode == ISD::FMUL) {
3206 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3209 // If the first operand isn't the constant, try the second
3211 CFP = dyn_cast<ConstantFPSDNode>(N2);
3218 return SDValue(CFP,0);
3220 if (CFP->isExactlyValue(1.0))
3225 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3226 assert(N1.getValueType() == N2.getValueType() &&
3227 N1.getValueType() == VT && "Binary operator types must match!");
3229 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3230 assert(N1.getValueType() == VT &&
3231 N1.getValueType().isFloatingPoint() &&
3232 N2.getValueType().isFloatingPoint() &&
3233 "Invalid FCOPYSIGN!");
3240 assert(VT == N1.getValueType() &&
3241 "Shift operators return type must be the same as their first arg");
3242 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3243 "Shifts only work on integers");
3244 assert((!VT.isVector() || VT == N2.getValueType()) &&
3245 "Vector shift amounts must be in the same as their first arg");
3246 // Verify that the shift amount VT is bit enough to hold valid shift
3247 // amounts. This catches things like trying to shift an i1024 value by an
3248 // i8, which is easy to fall into in generic code that uses
3249 // TLI.getShiftAmount().
3250 assert(N2.getValueType().getSizeInBits() >=
3251 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3252 "Invalid use of small shift amount with oversized value!");
3254 // Always fold shifts of i1 values so the code generator doesn't need to
3255 // handle them. Since we know the size of the shift has to be less than the
3256 // size of the value, the shift/rotate count is guaranteed to be zero.
3259 if (N2C && N2C->isNullValue())
3262 case ISD::FP_ROUND_INREG: {
3263 EVT EVT = cast<VTSDNode>(N2)->getVT();
3264 assert(VT == N1.getValueType() && "Not an inreg round!");
3265 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3266 "Cannot FP_ROUND_INREG integer types");
3267 assert(EVT.isVector() == VT.isVector() &&
3268 "FP_ROUND_INREG type should be vector iff the operand "
3270 assert((!EVT.isVector() ||
3271 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3272 "Vector element counts must match in FP_ROUND_INREG");
3273 assert(EVT.bitsLE(VT) && "Not rounding down!");
3275 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3279 assert(VT.isFloatingPoint() &&
3280 N1.getValueType().isFloatingPoint() &&
3281 VT.bitsLE(N1.getValueType()) &&
3282 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3283 if (N1.getValueType() == VT) return N1; // noop conversion.
3285 case ISD::AssertSext:
3286 case ISD::AssertZext: {
3287 EVT EVT = cast<VTSDNode>(N2)->getVT();
3288 assert(VT == N1.getValueType() && "Not an inreg extend!");
3289 assert(VT.isInteger() && EVT.isInteger() &&
3290 "Cannot *_EXTEND_INREG FP types");
3291 assert(!EVT.isVector() &&
3292 "AssertSExt/AssertZExt type should be the vector element type "
3293 "rather than the vector type!");
3294 assert(EVT.bitsLE(VT) && "Not extending!");
3295 if (VT == EVT) return N1; // noop assertion.
3298 case ISD::SIGN_EXTEND_INREG: {
3299 EVT EVT = cast<VTSDNode>(N2)->getVT();
3300 assert(VT == N1.getValueType() && "Not an inreg extend!");
3301 assert(VT.isInteger() && EVT.isInteger() &&
3302 "Cannot *_EXTEND_INREG FP types");
3303 assert(EVT.isVector() == VT.isVector() &&
3304 "SIGN_EXTEND_INREG type should be vector iff the operand "
3306 assert((!EVT.isVector() ||
3307 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3308 "Vector element counts must match in SIGN_EXTEND_INREG");
3309 assert(EVT.bitsLE(VT) && "Not extending!");
3310 if (EVT == VT) return N1; // Not actually extending
3313 APInt Val = N1C->getAPIntValue();
3314 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3315 Val <<= Val.getBitWidth()-FromBits;
3316 Val = Val.ashr(Val.getBitWidth()-FromBits);
3317 return getConstant(Val, VT);
3321 case ISD::EXTRACT_VECTOR_ELT:
3322 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3323 if (N1.getOpcode() == ISD::UNDEF)
3324 return getUNDEF(VT);
3326 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3327 // expanding copies of large vectors from registers.
3329 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3330 N1.getNumOperands() > 0) {
3332 N1.getOperand(0).getValueType().getVectorNumElements();
3333 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3334 N1.getOperand(N2C->getZExtValue() / Factor),
3335 getConstant(N2C->getZExtValue() % Factor,
3336 N2.getValueType()));
3339 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3340 // expanding large vector constants.
3341 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3342 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3344 if (VT != Elt.getValueType())
3345 // If the vector element type is not legal, the BUILD_VECTOR operands
3346 // are promoted and implicitly truncated, and the result implicitly
3347 // extended. Make that explicit here.
3348 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3353 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3354 // operations are lowered to scalars.
3355 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3356 // If the indices are the same, return the inserted element else
3357 // if the indices are known different, extract the element from
3358 // the original vector.
3359 SDValue N1Op2 = N1.getOperand(2);
3360 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3362 if (N1Op2C && N2C) {
3363 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3364 if (VT == N1.getOperand(1).getValueType())
3365 return N1.getOperand(1);
3367 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3370 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3374 case ISD::EXTRACT_ELEMENT:
3375 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3376 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3377 (N1.getValueType().isInteger() == VT.isInteger()) &&
3378 N1.getValueType() != VT &&
3379 "Wrong types for EXTRACT_ELEMENT!");
3381 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3382 // 64-bit integers into 32-bit parts. Instead of building the extract of
3383 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3384 if (N1.getOpcode() == ISD::BUILD_PAIR)
3385 return N1.getOperand(N2C->getZExtValue());
3387 // EXTRACT_ELEMENT of a constant int is also very common.
3388 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3389 unsigned ElementSize = VT.getSizeInBits();
3390 unsigned Shift = ElementSize * N2C->getZExtValue();
3391 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3392 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3395 case ISD::EXTRACT_SUBVECTOR: {
3397 if (VT.isSimple() && N1.getValueType().isSimple()) {
3398 assert(VT.isVector() && N1.getValueType().isVector() &&
3399 "Extract subvector VTs must be a vectors!");
3400 assert(VT.getVectorElementType() ==
3401 N1.getValueType().getVectorElementType() &&
3402 "Extract subvector VTs must have the same element type!");
3403 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3404 "Extract subvector must be from larger vector to smaller vector!");
3406 if (isa<ConstantSDNode>(Index.getNode())) {
3407 assert((VT.getVectorNumElements() +
3408 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3409 <= N1.getValueType().getVectorNumElements())
3410 && "Extract subvector overflow!");
3413 // Trivial extraction.
3414 if (VT.getSimpleVT() == N1.getSimpleValueType())
3421 // Perform trivial constant folding.
3422 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3423 if (SV.getNode()) return SV;
3425 // Canonicalize constant to RHS if commutative.
3426 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3427 std::swap(N1C, N2C);
3431 // Constant fold FP operations.
3432 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3433 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3435 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3436 // Canonicalize constant to RHS if commutative.
3437 std::swap(N1CFP, N2CFP);
3440 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3441 APFloat::opStatus s;
3444 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3445 if (s != APFloat::opInvalidOp)
3446 return getConstantFP(V1, VT);
3449 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3450 if (s!=APFloat::opInvalidOp)
3451 return getConstantFP(V1, VT);
3454 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3455 if (s!=APFloat::opInvalidOp)
3456 return getConstantFP(V1, VT);
3459 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3460 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3461 return getConstantFP(V1, VT);
3464 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3465 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3466 return getConstantFP(V1, VT);
3468 case ISD::FCOPYSIGN:
3470 return getConstantFP(V1, VT);
3475 if (Opcode == ISD::FP_ROUND) {
3476 APFloat V = N1CFP->getValueAPF(); // make copy
3478 // This can return overflow, underflow, or inexact; we don't care.
3479 // FIXME need to be more flexible about rounding mode.
3480 (void)V.convert(EVTToAPFloatSemantics(VT),
3481 APFloat::rmNearestTiesToEven, &ignored);
3482 return getConstantFP(V, VT);
3486 // Canonicalize an UNDEF to the RHS, even over a constant.
3487 if (N1.getOpcode() == ISD::UNDEF) {
3488 if (isCommutativeBinOp(Opcode)) {
3492 case ISD::FP_ROUND_INREG:
3493 case ISD::SIGN_EXTEND_INREG:
3499 return N1; // fold op(undef, arg2) -> undef
3507 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3508 // For vectors, we can't easily build an all zero vector, just return
3515 // Fold a bunch of operators when the RHS is undef.
3516 if (N2.getOpcode() == ISD::UNDEF) {
3519 if (N1.getOpcode() == ISD::UNDEF)
3520 // Handle undef ^ undef -> 0 special case. This is a common
3522 return getConstant(0, VT);
3532 return N2; // fold op(arg1, undef) -> undef
3538 if (getTarget().Options.UnsafeFPMath)
3546 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3547 // For vectors, we can't easily build an all zero vector, just return
3552 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3553 // For vectors, we can't easily build an all one vector, just return
3561 // Memoize this node if possible.
3563 SDVTList VTs = getVTList(VT);
3564 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3565 if (VT != MVT::Glue) {
3566 SDValue Ops[] = {N1, N2};
3567 FoldingSetNodeID ID;
3568 AddNodeIDNode(ID, Opcode, VTs, Ops);
3570 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3572 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3573 return SDValue(E, 0);
3575 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3577 CSEMap.InsertNode(N, IP);
3580 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3583 AllNodes.push_back(N);
3587 return SDValue(N, 0);
3590 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3591 SDValue N1, SDValue N2, SDValue N3) {
3592 // Perform various simplifications.
3593 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3596 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3597 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3598 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3599 if (N1CFP && N2CFP && N3CFP) {
3600 APFloat V1 = N1CFP->getValueAPF();
3601 const APFloat &V2 = N2CFP->getValueAPF();
3602 const APFloat &V3 = N3CFP->getValueAPF();
3603 APFloat::opStatus s =
3604 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3605 if (s != APFloat::opInvalidOp)
3606 return getConstantFP(V1, VT);
3610 case ISD::CONCAT_VECTORS:
3611 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3612 // one big BUILD_VECTOR.
3613 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3614 N2.getOpcode() == ISD::BUILD_VECTOR &&
3615 N3.getOpcode() == ISD::BUILD_VECTOR) {
3616 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3617 N1.getNode()->op_end());
3618 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3619 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3620 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3624 // Use FoldSetCC to simplify SETCC's.
3625 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3626 if (Simp.getNode()) return Simp;
3631 if (N1C->getZExtValue())
3632 return N2; // select true, X, Y -> X
3633 return N3; // select false, X, Y -> Y
3636 if (N2 == N3) return N2; // select C, X, X -> X
3638 case ISD::VECTOR_SHUFFLE:
3639 llvm_unreachable("should use getVectorShuffle constructor!");
3640 case ISD::INSERT_SUBVECTOR: {
3642 if (VT.isSimple() && N1.getValueType().isSimple()
3643 && N2.getValueType().isSimple()) {
3644 assert(VT.isVector() && N1.getValueType().isVector() &&
3645 N2.getValueType().isVector() &&
3646 "Insert subvector VTs must be a vectors");
3647 assert(VT == N1.getValueType() &&
3648 "Dest and insert subvector source types must match!");
3649 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3650 "Insert subvector must be from smaller vector to larger vector!");
3651 if (isa<ConstantSDNode>(Index.getNode())) {
3652 assert((N2.getValueType().getVectorNumElements() +
3653 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3654 <= VT.getVectorNumElements())
3655 && "Insert subvector overflow!");
3658 // Trivial insertion.
3659 if (VT.getSimpleVT() == N2.getSimpleValueType())
3665 // Fold bit_convert nodes from a type to themselves.
3666 if (N1.getValueType() == VT)
3671 // Memoize node if it doesn't produce a flag.
3673 SDVTList VTs = getVTList(VT);
3674 if (VT != MVT::Glue) {
3675 SDValue Ops[] = { N1, N2, N3 };
3676 FoldingSetNodeID ID;
3677 AddNodeIDNode(ID, Opcode, VTs, Ops);
3679 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3680 return SDValue(E, 0);
3682 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3683 DL.getDebugLoc(), VTs, N1, N2, N3);
3684 CSEMap.InsertNode(N, IP);
3686 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3687 DL.getDebugLoc(), VTs, N1, N2, N3);
3690 AllNodes.push_back(N);
3694 return SDValue(N, 0);
3697 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3698 SDValue N1, SDValue N2, SDValue N3,
3700 SDValue Ops[] = { N1, N2, N3, N4 };
3701 return getNode(Opcode, DL, VT, Ops);
3704 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3705 SDValue N1, SDValue N2, SDValue N3,
3706 SDValue N4, SDValue N5) {
3707 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3708 return getNode(Opcode, DL, VT, Ops);
3711 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3712 /// the incoming stack arguments to be loaded from the stack.
3713 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3714 SmallVector<SDValue, 8> ArgChains;
3716 // Include the original chain at the beginning of the list. When this is
3717 // used by target LowerCall hooks, this helps legalize find the
3718 // CALLSEQ_BEGIN node.
3719 ArgChains.push_back(Chain);
3721 // Add a chain value for each stack argument.
3722 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3723 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3724 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3725 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3726 if (FI->getIndex() < 0)
3727 ArgChains.push_back(SDValue(L, 1));
3729 // Build a tokenfactor for all the chains.
3730 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3733 /// getMemsetValue - Vectorized representation of the memset value
3735 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3737 assert(Value.getOpcode() != ISD::UNDEF);
3739 unsigned NumBits = VT.getScalarType().getSizeInBits();
3740 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3741 assert(C->getAPIntValue().getBitWidth() == 8);
3742 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3744 return DAG.getConstant(Val, VT);
3745 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3748 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3750 // Use a multiplication with 0x010101... to extend the input to the
3752 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3753 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3759 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3760 /// used when a memcpy is turned into a memset when the source is a constant
3762 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3763 const TargetLowering &TLI, StringRef Str) {
3764 // Handle vector with all elements zero.
3767 return DAG.getConstant(0, VT);
3768 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3769 return DAG.getConstantFP(0.0, VT);
3770 else if (VT.isVector()) {
3771 unsigned NumElts = VT.getVectorNumElements();
3772 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3773 return DAG.getNode(ISD::BITCAST, dl, VT,
3774 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3777 llvm_unreachable("Expected type!");
3780 assert(!VT.isVector() && "Can't handle vector type here!");
3781 unsigned NumVTBits = VT.getSizeInBits();
3782 unsigned NumVTBytes = NumVTBits / 8;
3783 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3785 APInt Val(NumVTBits, 0);
3786 if (TLI.isLittleEndian()) {
3787 for (unsigned i = 0; i != NumBytes; ++i)
3788 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3790 for (unsigned i = 0; i != NumBytes; ++i)
3791 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3794 // If the "cost" of materializing the integer immediate is less than the cost
3795 // of a load, then it is cost effective to turn the load into the immediate.
3796 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3797 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3798 return DAG.getConstant(Val, VT);
3799 return SDValue(nullptr, 0);
3802 /// getMemBasePlusOffset - Returns base and offset node for the
3804 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3805 SelectionDAG &DAG) {
3806 EVT VT = Base.getValueType();
3807 return DAG.getNode(ISD::ADD, dl,
3808 VT, Base, DAG.getConstant(Offset, VT));
3811 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3813 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3814 unsigned SrcDelta = 0;
3815 GlobalAddressSDNode *G = nullptr;
3816 if (Src.getOpcode() == ISD::GlobalAddress)
3817 G = cast<GlobalAddressSDNode>(Src);
3818 else if (Src.getOpcode() == ISD::ADD &&
3819 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3820 Src.getOperand(1).getOpcode() == ISD::Constant) {
3821 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3822 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3827 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3830 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3831 /// to replace the memset / memcpy. Return true if the number of memory ops
3832 /// is below the threshold. It returns the types of the sequence of
3833 /// memory ops to perform memset / memcpy by reference.
3834 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3835 unsigned Limit, uint64_t Size,
3836 unsigned DstAlign, unsigned SrcAlign,
3842 const TargetLowering &TLI) {
3843 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3844 "Expecting memcpy / memset source to meet alignment requirement!");
3845 // If 'SrcAlign' is zero, that means the memory operation does not need to
3846 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3847 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3848 // is the specified alignment of the memory operation. If it is zero, that
3849 // means it's possible to change the alignment of the destination.
3850 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3851 // not need to be loaded.
3852 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3853 IsMemset, ZeroMemset, MemcpyStrSrc,
3854 DAG.getMachineFunction());
3856 if (VT == MVT::Other) {
3858 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3859 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3860 VT = TLI.getPointerTy();
3862 switch (DstAlign & 7) {
3863 case 0: VT = MVT::i64; break;
3864 case 4: VT = MVT::i32; break;
3865 case 2: VT = MVT::i16; break;
3866 default: VT = MVT::i8; break;
3871 while (!TLI.isTypeLegal(LVT))
3872 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3873 assert(LVT.isInteger());
3879 unsigned NumMemOps = 0;
3881 unsigned VTSize = VT.getSizeInBits() / 8;
3882 while (VTSize > Size) {
3883 // For now, only use non-vector load / store's for the left-over pieces.
3888 if (VT.isVector() || VT.isFloatingPoint()) {
3889 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3890 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3891 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3893 else if (NewVT == MVT::i64 &&
3894 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3895 TLI.isSafeMemOpType(MVT::f64)) {
3896 // i64 is usually not legal on 32-bit targets, but f64 may be.
3904 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3905 if (NewVT == MVT::i8)
3907 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3909 NewVTSize = NewVT.getSizeInBits() / 8;
3911 // If the new VT cannot cover all of the remaining bits, then consider
3912 // issuing a (or a pair of) unaligned and overlapping load / store.
3913 // FIXME: Only does this for 64-bit or more since we don't have proper
3914 // cost model for unaligned load / store.
3917 if (NumMemOps && AllowOverlap &&
3918 VTSize >= 8 && NewVTSize < Size &&
3919 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3927 if (++NumMemOps > Limit)
3930 MemOps.push_back(VT);
3937 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3938 SDValue Chain, SDValue Dst,
3939 SDValue Src, uint64_t Size,
3940 unsigned Align, bool isVol,
3942 MachinePointerInfo DstPtrInfo,
3943 MachinePointerInfo SrcPtrInfo) {
3944 // Turn a memcpy of undef to nop.
3945 if (Src.getOpcode() == ISD::UNDEF)
3948 // Expand memcpy to a series of load and store ops if the size operand falls
3949 // below a certain threshold.
3950 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3951 // rather than maybe a humongous number of loads and stores.
3952 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3953 std::vector<EVT> MemOps;
3954 bool DstAlignCanChange = false;
3955 MachineFunction &MF = DAG.getMachineFunction();
3956 MachineFrameInfo *MFI = MF.getFrameInfo();
3958 MF.getFunction()->getAttributes().
3959 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3960 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3961 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3962 DstAlignCanChange = true;
3963 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3964 if (Align > SrcAlign)
3967 bool CopyFromStr = isMemSrcFromString(Src, Str);
3968 bool isZeroStr = CopyFromStr && Str.empty();
3969 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3971 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3972 (DstAlignCanChange ? 0 : Align),
3973 (isZeroStr ? 0 : SrcAlign),
3974 false, false, CopyFromStr, true, DAG, TLI))
3977 if (DstAlignCanChange) {
3978 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3979 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3981 // Don't promote to an alignment that would require dynamic stack
3983 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3984 if (!TRI->needsStackRealignment(MF))
3985 while (NewAlign > Align &&
3986 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3989 if (NewAlign > Align) {
3990 // Give the stack frame object a larger alignment if needed.
3991 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3992 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3997 SmallVector<SDValue, 8> OutChains;
3998 unsigned NumMemOps = MemOps.size();
3999 uint64_t SrcOff = 0, DstOff = 0;
4000 for (unsigned i = 0; i != NumMemOps; ++i) {
4002 unsigned VTSize = VT.getSizeInBits() / 8;
4003 SDValue Value, Store;
4005 if (VTSize > Size) {
4006 // Issuing an unaligned load / store pair that overlaps with the previous
4007 // pair. Adjust the offset accordingly.
4008 assert(i == NumMemOps-1 && i != 0);
4009 SrcOff -= VTSize - Size;
4010 DstOff -= VTSize - Size;
4014 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4015 // It's unlikely a store of a vector immediate can be done in a single
4016 // instruction. It would require a load from a constantpool first.
4017 // We only handle zero vectors here.
4018 // FIXME: Handle other cases where store of vector immediate is done in
4019 // a single instruction.
4020 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4021 if (Value.getNode())
4022 Store = DAG.getStore(Chain, dl, Value,
4023 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4024 DstPtrInfo.getWithOffset(DstOff), isVol,
4028 if (!Store.getNode()) {
4029 // The type might not be legal for the target. This should only happen
4030 // if the type is smaller than a legal type, as on PPC, so the right
4031 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4032 // to Load/Store if NVT==VT.
4033 // FIXME does the case above also need this?
4034 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4035 assert(NVT.bitsGE(VT));
4036 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4037 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4038 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4039 MinAlign(SrcAlign, SrcOff));
4040 Store = DAG.getTruncStore(Chain, dl, Value,
4041 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4042 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4045 OutChains.push_back(Store);
4051 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4054 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4055 SDValue Chain, SDValue Dst,
4056 SDValue Src, uint64_t Size,
4057 unsigned Align, bool isVol,
4059 MachinePointerInfo DstPtrInfo,
4060 MachinePointerInfo SrcPtrInfo) {
4061 // Turn a memmove of undef to nop.
4062 if (Src.getOpcode() == ISD::UNDEF)
4065 // Expand memmove to a series of load and store ops if the size operand falls
4066 // below a certain threshold.
4067 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4068 std::vector<EVT> MemOps;
4069 bool DstAlignCanChange = false;
4070 MachineFunction &MF = DAG.getMachineFunction();
4071 MachineFrameInfo *MFI = MF.getFrameInfo();
4072 bool OptSize = MF.getFunction()->getAttributes().
4073 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4074 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4075 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4076 DstAlignCanChange = true;
4077 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4078 if (Align > SrcAlign)
4080 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4082 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4083 (DstAlignCanChange ? 0 : Align), SrcAlign,
4084 false, false, false, false, DAG, TLI))
4087 if (DstAlignCanChange) {
4088 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4089 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4090 if (NewAlign > Align) {
4091 // Give the stack frame object a larger alignment if needed.
4092 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4093 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4098 uint64_t SrcOff = 0, DstOff = 0;
4099 SmallVector<SDValue, 8> LoadValues;
4100 SmallVector<SDValue, 8> LoadChains;
4101 SmallVector<SDValue, 8> OutChains;
4102 unsigned NumMemOps = MemOps.size();
4103 for (unsigned i = 0; i < NumMemOps; i++) {
4105 unsigned VTSize = VT.getSizeInBits() / 8;
4108 Value = DAG.getLoad(VT, dl, Chain,
4109 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4110 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4111 false, false, SrcAlign);
4112 LoadValues.push_back(Value);
4113 LoadChains.push_back(Value.getValue(1));
4116 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4118 for (unsigned i = 0; i < NumMemOps; i++) {
4120 unsigned VTSize = VT.getSizeInBits() / 8;
4123 Store = DAG.getStore(Chain, dl, LoadValues[i],
4124 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4125 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4126 OutChains.push_back(Store);
4130 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4133 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4136 /// \param DAG Selection DAG where lowered code is placed.
4137 /// \param dl Link to corresponding IR location.
4138 /// \param Chain Control flow dependency.
4139 /// \param Dst Pointer to destination memory location.
4140 /// \param Src Value of byte to write into the memory.
4141 /// \param Size Number of bytes to write.
4142 /// \param Align Alignment of the destination in bytes.
4143 /// \param isVol True if destination is volatile.
4144 /// \param DstPtrInfo IR information on the memory pointer.
4145 /// \returns New head in the control flow, if lowering was successful, empty
4146 /// SDValue otherwise.
4148 /// The function tries to replace 'llvm.memset' intrinsic with several store
4149 /// operations and value calculation code. This is usually profitable for small
4151 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4152 SDValue Chain, SDValue Dst,
4153 SDValue Src, uint64_t Size,
4154 unsigned Align, bool isVol,
4155 MachinePointerInfo DstPtrInfo) {
4156 // Turn a memset of undef to nop.
4157 if (Src.getOpcode() == ISD::UNDEF)
4160 // Expand memset to a series of load/store ops if the size operand
4161 // falls below a certain threshold.
4162 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4163 std::vector<EVT> MemOps;
4164 bool DstAlignCanChange = false;
4165 MachineFunction &MF = DAG.getMachineFunction();
4166 MachineFrameInfo *MFI = MF.getFrameInfo();
4167 bool OptSize = MF.getFunction()->getAttributes().
4168 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4169 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4170 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4171 DstAlignCanChange = true;
4173 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4174 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4175 Size, (DstAlignCanChange ? 0 : Align), 0,
4176 true, IsZeroVal, false, true, DAG, TLI))
4179 if (DstAlignCanChange) {
4180 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4181 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4182 if (NewAlign > Align) {
4183 // Give the stack frame object a larger alignment if needed.
4184 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4185 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4190 SmallVector<SDValue, 8> OutChains;
4191 uint64_t DstOff = 0;
4192 unsigned NumMemOps = MemOps.size();
4194 // Find the largest store and generate the bit pattern for it.
4195 EVT LargestVT = MemOps[0];
4196 for (unsigned i = 1; i < NumMemOps; i++)
4197 if (MemOps[i].bitsGT(LargestVT))
4198 LargestVT = MemOps[i];
4199 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4201 for (unsigned i = 0; i < NumMemOps; i++) {
4203 unsigned VTSize = VT.getSizeInBits() / 8;
4204 if (VTSize > Size) {
4205 // Issuing an unaligned load / store pair that overlaps with the previous
4206 // pair. Adjust the offset accordingly.
4207 assert(i == NumMemOps-1 && i != 0);
4208 DstOff -= VTSize - Size;
4211 // If this store is smaller than the largest store see whether we can get
4212 // the smaller value for free with a truncate.
4213 SDValue Value = MemSetValue;
4214 if (VT.bitsLT(LargestVT)) {
4215 if (!LargestVT.isVector() && !VT.isVector() &&
4216 TLI.isTruncateFree(LargestVT, VT))
4217 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4219 Value = getMemsetValue(Src, VT, DAG, dl);
4221 assert(Value.getValueType() == VT && "Value with wrong type.");
4222 SDValue Store = DAG.getStore(Chain, dl, Value,
4223 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4224 DstPtrInfo.getWithOffset(DstOff),
4225 isVol, false, Align);
4226 OutChains.push_back(Store);
4227 DstOff += VT.getSizeInBits() / 8;
4231 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4234 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4235 SDValue Src, SDValue Size,
4236 unsigned Align, bool isVol, bool AlwaysInline,
4237 MachinePointerInfo DstPtrInfo,
4238 MachinePointerInfo SrcPtrInfo) {
4239 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4241 // Check to see if we should lower the memcpy to loads and stores first.
4242 // For cases within the target-specified limits, this is the best choice.
4243 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4245 // Memcpy with size zero? Just return the original chain.
4246 if (ConstantSize->isNullValue())
4249 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4250 ConstantSize->getZExtValue(),Align,
4251 isVol, false, DstPtrInfo, SrcPtrInfo);
4252 if (Result.getNode())
4256 // Then check to see if we should lower the memcpy with target-specific
4257 // code. If the target chooses to do this, this is the next best.
4259 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4260 isVol, AlwaysInline,
4261 DstPtrInfo, SrcPtrInfo);
4262 if (Result.getNode())
4265 // If we really need inline code and the target declined to provide it,
4266 // use a (potentially long) sequence of loads and stores.
4268 assert(ConstantSize && "AlwaysInline requires a constant size!");
4269 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4270 ConstantSize->getZExtValue(), Align, isVol,
4271 true, DstPtrInfo, SrcPtrInfo);
4274 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4275 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4276 // respect volatile, so they may do things like read or write memory
4277 // beyond the given memory regions. But fixing this isn't easy, and most
4278 // people don't care.
4280 const TargetLowering *TLI = TM.getTargetLowering();
4282 // Emit a library call.
4283 TargetLowering::ArgListTy Args;
4284 TargetLowering::ArgListEntry Entry;
4285 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4286 Entry.Node = Dst; Args.push_back(Entry);
4287 Entry.Node = Src; Args.push_back(Entry);
4288 Entry.Node = Size; Args.push_back(Entry);
4289 // FIXME: pass in SDLoc
4290 TargetLowering::CallLoweringInfo CLI(*this);
4291 CLI.setDebugLoc(dl).setChain(Chain)
4292 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4293 Type::getVoidTy(*getContext()),
4294 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4295 TLI->getPointerTy()), std::move(Args), 0)
4296 .setDiscardResult();
4297 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4299 return CallResult.second;
4302 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4303 SDValue Src, SDValue Size,
4304 unsigned Align, bool isVol,
4305 MachinePointerInfo DstPtrInfo,
4306 MachinePointerInfo SrcPtrInfo) {
4307 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4309 // Check to see if we should lower the memmove to loads and stores first.
4310 // For cases within the target-specified limits, this is the best choice.
4311 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4313 // Memmove with size zero? Just return the original chain.
4314 if (ConstantSize->isNullValue())
4318 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4319 ConstantSize->getZExtValue(), Align, isVol,
4320 false, DstPtrInfo, SrcPtrInfo);
4321 if (Result.getNode())
4325 // Then check to see if we should lower the memmove with target-specific
4326 // code. If the target chooses to do this, this is the next best.
4328 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4329 DstPtrInfo, SrcPtrInfo);
4330 if (Result.getNode())
4333 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4334 // not be safe. See memcpy above for more details.
4336 const TargetLowering *TLI = TM.getTargetLowering();
4338 // Emit a library call.
4339 TargetLowering::ArgListTy Args;
4340 TargetLowering::ArgListEntry Entry;
4341 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4342 Entry.Node = Dst; Args.push_back(Entry);
4343 Entry.Node = Src; Args.push_back(Entry);
4344 Entry.Node = Size; Args.push_back(Entry);
4345 // FIXME: pass in SDLoc
4346 TargetLowering::CallLoweringInfo CLI(*this);
4347 CLI.setDebugLoc(dl).setChain(Chain)
4348 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4349 Type::getVoidTy(*getContext()),
4350 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4351 TLI->getPointerTy()), std::move(Args), 0)
4352 .setDiscardResult();
4353 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4355 return CallResult.second;
4358 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4359 SDValue Src, SDValue Size,
4360 unsigned Align, bool isVol,
4361 MachinePointerInfo DstPtrInfo) {
4362 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4364 // Check to see if we should lower the memset to stores first.
4365 // For cases within the target-specified limits, this is the best choice.
4366 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4368 // Memset with size zero? Just return the original chain.
4369 if (ConstantSize->isNullValue())
4373 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4374 Align, isVol, DstPtrInfo);
4376 if (Result.getNode())
4380 // Then check to see if we should lower the memset with target-specific
4381 // code. If the target chooses to do this, this is the next best.
4383 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4385 if (Result.getNode())
4388 // Emit a library call.
4389 const TargetLowering *TLI = TM.getTargetLowering();
4390 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4391 TargetLowering::ArgListTy Args;
4392 TargetLowering::ArgListEntry Entry;
4393 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4394 Args.push_back(Entry);
4395 // Extend or truncate the argument to be an i32 value for the call.
4396 if (Src.getValueType().bitsGT(MVT::i32))
4397 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4399 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4401 Entry.Ty = Type::getInt32Ty(*getContext());
4402 Entry.isSExt = true;
4403 Args.push_back(Entry);
4405 Entry.Ty = IntPtrTy;
4406 Entry.isSExt = false;
4407 Args.push_back(Entry);
4409 // FIXME: pass in SDLoc
4410 TargetLowering::CallLoweringInfo CLI(*this);
4411 CLI.setDebugLoc(dl).setChain(Chain)
4412 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4413 Type::getVoidTy(*getContext()),
4414 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4415 TLI->getPointerTy()), std::move(Args), 0)
4416 .setDiscardResult();
4418 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4419 return CallResult.second;
4422 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4423 SDVTList VTList, ArrayRef<SDValue> Ops,
4424 MachineMemOperand *MMO,
4425 AtomicOrdering SuccessOrdering,
4426 AtomicOrdering FailureOrdering,
4427 SynchronizationScope SynchScope) {
4428 FoldingSetNodeID ID;
4429 ID.AddInteger(MemVT.getRawBits());
4430 AddNodeIDNode(ID, Opcode, VTList, Ops);
4431 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4433 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4434 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4435 return SDValue(E, 0);
4438 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4439 // SDNode doesn't have access to it. This memory will be "leaked" when
4440 // the node is deallocated, but recovered when the allocator is released.
4441 // If the number of operands is less than 5 we use AtomicSDNode's internal
4443 unsigned NumOps = Ops.size();
4444 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4447 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4448 dl.getDebugLoc(), VTList, MemVT,
4449 Ops.data(), DynOps, NumOps, MMO,
4450 SuccessOrdering, FailureOrdering,
4452 CSEMap.InsertNode(N, IP);
4453 AllNodes.push_back(N);
4454 return SDValue(N, 0);
4457 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4458 SDVTList VTList, ArrayRef<SDValue> Ops,
4459 MachineMemOperand *MMO,
4460 AtomicOrdering Ordering,
4461 SynchronizationScope SynchScope) {
4462 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4463 Ordering, SynchScope);
4466 SDValue SelectionDAG::getAtomicCmpSwap(
4467 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4468 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4469 unsigned Alignment, AtomicOrdering SuccessOrdering,
4470 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4471 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4472 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4473 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4475 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4476 Alignment = getEVTAlignment(MemVT);
4478 MachineFunction &MF = getMachineFunction();
4480 // FIXME: Volatile isn't really correct; we should keep track of atomic
4481 // orderings in the memoperand.
4482 unsigned Flags = MachineMemOperand::MOVolatile;
4483 Flags |= MachineMemOperand::MOLoad;
4484 Flags |= MachineMemOperand::MOStore;
4486 MachineMemOperand *MMO =
4487 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4489 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4490 SuccessOrdering, FailureOrdering, SynchScope);
4493 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4494 SDVTList VTs, SDValue Chain, SDValue Ptr,
4495 SDValue Cmp, SDValue Swp,
4496 MachineMemOperand *MMO,
4497 AtomicOrdering SuccessOrdering,
4498 AtomicOrdering FailureOrdering,
4499 SynchronizationScope SynchScope) {
4500 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4501 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4502 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4504 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4505 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4506 SuccessOrdering, FailureOrdering, SynchScope);
4509 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4511 SDValue Ptr, SDValue Val,
4512 const Value* PtrVal,
4514 AtomicOrdering Ordering,
4515 SynchronizationScope SynchScope) {
4516 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4517 Alignment = getEVTAlignment(MemVT);
4519 MachineFunction &MF = getMachineFunction();
4520 // An atomic store does not load. An atomic load does not store.
4521 // (An atomicrmw obviously both loads and stores.)
4522 // For now, atomics are considered to be volatile always, and they are
4524 // FIXME: Volatile isn't really correct; we should keep track of atomic
4525 // orderings in the memoperand.
4526 unsigned Flags = MachineMemOperand::MOVolatile;
4527 if (Opcode != ISD::ATOMIC_STORE)
4528 Flags |= MachineMemOperand::MOLoad;
4529 if (Opcode != ISD::ATOMIC_LOAD)
4530 Flags |= MachineMemOperand::MOStore;
4532 MachineMemOperand *MMO =
4533 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4534 MemVT.getStoreSize(), Alignment);
4536 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4537 Ordering, SynchScope);
4540 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4542 SDValue Ptr, SDValue Val,
4543 MachineMemOperand *MMO,
4544 AtomicOrdering Ordering,
4545 SynchronizationScope SynchScope) {
4546 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4547 Opcode == ISD::ATOMIC_LOAD_SUB ||
4548 Opcode == ISD::ATOMIC_LOAD_AND ||
4549 Opcode == ISD::ATOMIC_LOAD_OR ||
4550 Opcode == ISD::ATOMIC_LOAD_XOR ||
4551 Opcode == ISD::ATOMIC_LOAD_NAND ||
4552 Opcode == ISD::ATOMIC_LOAD_MIN ||
4553 Opcode == ISD::ATOMIC_LOAD_MAX ||
4554 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4555 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4556 Opcode == ISD::ATOMIC_SWAP ||
4557 Opcode == ISD::ATOMIC_STORE) &&
4558 "Invalid Atomic Op");
4560 EVT VT = Val.getValueType();
4562 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4563 getVTList(VT, MVT::Other);
4564 SDValue Ops[] = {Chain, Ptr, Val};
4565 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4568 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4569 EVT VT, SDValue Chain,
4571 MachineMemOperand *MMO,
4572 AtomicOrdering Ordering,
4573 SynchronizationScope SynchScope) {
4574 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4576 SDVTList VTs = getVTList(VT, MVT::Other);
4577 SDValue Ops[] = {Chain, Ptr};
4578 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4581 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4582 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4583 if (Ops.size() == 1)
4586 SmallVector<EVT, 4> VTs;
4587 VTs.reserve(Ops.size());
4588 for (unsigned i = 0; i < Ops.size(); ++i)
4589 VTs.push_back(Ops[i].getValueType());
4590 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4594 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4595 ArrayRef<SDValue> Ops,
4596 EVT MemVT, MachinePointerInfo PtrInfo,
4597 unsigned Align, bool Vol,
4598 bool ReadMem, bool WriteMem) {
4599 if (Align == 0) // Ensure that codegen never sees alignment 0
4600 Align = getEVTAlignment(MemVT);
4602 MachineFunction &MF = getMachineFunction();
4605 Flags |= MachineMemOperand::MOStore;
4607 Flags |= MachineMemOperand::MOLoad;
4609 Flags |= MachineMemOperand::MOVolatile;
4610 MachineMemOperand *MMO =
4611 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4613 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4617 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4618 ArrayRef<SDValue> Ops, EVT MemVT,
4619 MachineMemOperand *MMO) {
4620 assert((Opcode == ISD::INTRINSIC_VOID ||
4621 Opcode == ISD::INTRINSIC_W_CHAIN ||
4622 Opcode == ISD::PREFETCH ||
4623 Opcode == ISD::LIFETIME_START ||
4624 Opcode == ISD::LIFETIME_END ||
4625 (Opcode <= INT_MAX &&
4626 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4627 "Opcode is not a memory-accessing opcode!");
4629 // Memoize the node unless it returns a flag.
4630 MemIntrinsicSDNode *N;
4631 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4632 FoldingSetNodeID ID;
4633 AddNodeIDNode(ID, Opcode, VTList, Ops);
4634 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4636 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4637 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4638 return SDValue(E, 0);
4641 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4642 dl.getDebugLoc(), VTList, Ops,
4644 CSEMap.InsertNode(N, IP);
4646 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4647 dl.getDebugLoc(), VTList, Ops,
4650 AllNodes.push_back(N);
4651 return SDValue(N, 0);
4654 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4655 /// MachinePointerInfo record from it. This is particularly useful because the
4656 /// code generator has many cases where it doesn't bother passing in a
4657 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4658 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4659 // If this is FI+Offset, we can model it.
4660 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4661 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4663 // If this is (FI+Offset1)+Offset2, we can model it.
4664 if (Ptr.getOpcode() != ISD::ADD ||
4665 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4666 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4667 return MachinePointerInfo();
4669 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4670 return MachinePointerInfo::getFixedStack(FI, Offset+
4671 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4674 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4675 /// MachinePointerInfo record from it. This is particularly useful because the
4676 /// code generator has many cases where it doesn't bother passing in a
4677 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4678 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4679 // If the 'Offset' value isn't a constant, we can't handle this.
4680 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4681 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4682 if (OffsetOp.getOpcode() == ISD::UNDEF)
4683 return InferPointerInfo(Ptr);
4684 return MachinePointerInfo();
4689 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4690 EVT VT, SDLoc dl, SDValue Chain,
4691 SDValue Ptr, SDValue Offset,
4692 MachinePointerInfo PtrInfo, EVT MemVT,
4693 bool isVolatile, bool isNonTemporal, bool isInvariant,
4694 unsigned Alignment, const MDNode *TBAAInfo,
4695 const MDNode *Ranges) {
4696 assert(Chain.getValueType() == MVT::Other &&
4697 "Invalid chain type");
4698 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4699 Alignment = getEVTAlignment(VT);
4701 unsigned Flags = MachineMemOperand::MOLoad;
4703 Flags |= MachineMemOperand::MOVolatile;
4705 Flags |= MachineMemOperand::MONonTemporal;
4707 Flags |= MachineMemOperand::MOInvariant;
4709 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4711 if (PtrInfo.V.isNull())
4712 PtrInfo = InferPointerInfo(Ptr, Offset);
4714 MachineFunction &MF = getMachineFunction();
4715 MachineMemOperand *MMO =
4716 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4718 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4722 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4723 EVT VT, SDLoc dl, SDValue Chain,
4724 SDValue Ptr, SDValue Offset, EVT MemVT,
4725 MachineMemOperand *MMO) {
4727 ExtType = ISD::NON_EXTLOAD;
4728 } else if (ExtType == ISD::NON_EXTLOAD) {
4729 assert(VT == MemVT && "Non-extending load from different memory type!");
4732 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4733 "Should only be an extending load, not truncating!");
4734 assert(VT.isInteger() == MemVT.isInteger() &&
4735 "Cannot convert from FP to Int or Int -> FP!");
4736 assert(VT.isVector() == MemVT.isVector() &&
4737 "Cannot use trunc store to convert to or from a vector!");
4738 assert((!VT.isVector() ||
4739 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4740 "Cannot use trunc store to change the number of vector elements!");
4743 bool Indexed = AM != ISD::UNINDEXED;
4744 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4745 "Unindexed load with an offset!");
4747 SDVTList VTs = Indexed ?
4748 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4749 SDValue Ops[] = { Chain, Ptr, Offset };
4750 FoldingSetNodeID ID;
4751 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4752 ID.AddInteger(MemVT.getRawBits());
4753 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4754 MMO->isNonTemporal(),
4755 MMO->isInvariant()));
4756 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4758 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4759 cast<LoadSDNode>(E)->refineAlignment(MMO);
4760 return SDValue(E, 0);
4762 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4763 dl.getDebugLoc(), VTs, AM, ExtType,
4765 CSEMap.InsertNode(N, IP);
4766 AllNodes.push_back(N);
4767 return SDValue(N, 0);
4770 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4771 SDValue Chain, SDValue Ptr,
4772 MachinePointerInfo PtrInfo,
4773 bool isVolatile, bool isNonTemporal,
4774 bool isInvariant, unsigned Alignment,
4775 const MDNode *TBAAInfo,
4776 const MDNode *Ranges) {
4777 SDValue Undef = getUNDEF(Ptr.getValueType());
4778 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4779 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4783 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4784 SDValue Chain, SDValue Ptr,
4785 MachineMemOperand *MMO) {
4786 SDValue Undef = getUNDEF(Ptr.getValueType());
4787 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4791 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4792 SDValue Chain, SDValue Ptr,
4793 MachinePointerInfo PtrInfo, EVT MemVT,
4794 bool isVolatile, bool isNonTemporal,
4795 unsigned Alignment, const MDNode *TBAAInfo) {
4796 SDValue Undef = getUNDEF(Ptr.getValueType());
4797 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4798 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4803 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4804 SDValue Chain, SDValue Ptr, EVT MemVT,
4805 MachineMemOperand *MMO) {
4806 SDValue Undef = getUNDEF(Ptr.getValueType());
4807 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4812 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4813 SDValue Offset, ISD::MemIndexedMode AM) {
4814 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4815 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4816 "Load is already a indexed load!");
4817 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4818 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4819 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4820 false, LD->getAlignment());
4823 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4824 SDValue Ptr, MachinePointerInfo PtrInfo,
4825 bool isVolatile, bool isNonTemporal,
4826 unsigned Alignment, const MDNode *TBAAInfo) {
4827 assert(Chain.getValueType() == MVT::Other &&
4828 "Invalid chain type");
4829 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4830 Alignment = getEVTAlignment(Val.getValueType());
4832 unsigned Flags = MachineMemOperand::MOStore;
4834 Flags |= MachineMemOperand::MOVolatile;
4836 Flags |= MachineMemOperand::MONonTemporal;
4838 if (PtrInfo.V.isNull())
4839 PtrInfo = InferPointerInfo(Ptr);
4841 MachineFunction &MF = getMachineFunction();
4842 MachineMemOperand *MMO =
4843 MF.getMachineMemOperand(PtrInfo, Flags,
4844 Val.getValueType().getStoreSize(), Alignment,
4847 return getStore(Chain, dl, Val, Ptr, MMO);
4850 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4851 SDValue Ptr, MachineMemOperand *MMO) {
4852 assert(Chain.getValueType() == MVT::Other &&
4853 "Invalid chain type");
4854 EVT VT = Val.getValueType();
4855 SDVTList VTs = getVTList(MVT::Other);
4856 SDValue Undef = getUNDEF(Ptr.getValueType());
4857 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4858 FoldingSetNodeID ID;
4859 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4860 ID.AddInteger(VT.getRawBits());
4861 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4862 MMO->isNonTemporal(), MMO->isInvariant()));
4863 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4865 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4866 cast<StoreSDNode>(E)->refineAlignment(MMO);
4867 return SDValue(E, 0);
4869 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4870 dl.getDebugLoc(), VTs,
4871 ISD::UNINDEXED, false, VT, MMO);
4872 CSEMap.InsertNode(N, IP);
4873 AllNodes.push_back(N);
4874 return SDValue(N, 0);
4877 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4878 SDValue Ptr, MachinePointerInfo PtrInfo,
4879 EVT SVT,bool isVolatile, bool isNonTemporal,
4881 const MDNode *TBAAInfo) {
4882 assert(Chain.getValueType() == MVT::Other &&
4883 "Invalid chain type");
4884 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4885 Alignment = getEVTAlignment(SVT);
4887 unsigned Flags = MachineMemOperand::MOStore;
4889 Flags |= MachineMemOperand::MOVolatile;
4891 Flags |= MachineMemOperand::MONonTemporal;
4893 if (PtrInfo.V.isNull())
4894 PtrInfo = InferPointerInfo(Ptr);
4896 MachineFunction &MF = getMachineFunction();
4897 MachineMemOperand *MMO =
4898 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4901 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4904 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4905 SDValue Ptr, EVT SVT,
4906 MachineMemOperand *MMO) {
4907 EVT VT = Val.getValueType();
4909 assert(Chain.getValueType() == MVT::Other &&
4910 "Invalid chain type");
4912 return getStore(Chain, dl, Val, Ptr, MMO);
4914 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4915 "Should only be a truncating store, not extending!");
4916 assert(VT.isInteger() == SVT.isInteger() &&
4917 "Can't do FP-INT conversion!");
4918 assert(VT.isVector() == SVT.isVector() &&
4919 "Cannot use trunc store to convert to or from a vector!");
4920 assert((!VT.isVector() ||
4921 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4922 "Cannot use trunc store to change the number of vector elements!");
4924 SDVTList VTs = getVTList(MVT::Other);
4925 SDValue Undef = getUNDEF(Ptr.getValueType());
4926 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4927 FoldingSetNodeID ID;
4928 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4929 ID.AddInteger(SVT.getRawBits());
4930 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4931 MMO->isNonTemporal(), MMO->isInvariant()));
4932 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4934 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4935 cast<StoreSDNode>(E)->refineAlignment(MMO);
4936 return SDValue(E, 0);
4938 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4939 dl.getDebugLoc(), VTs,
4940 ISD::UNINDEXED, true, SVT, MMO);
4941 CSEMap.InsertNode(N, IP);
4942 AllNodes.push_back(N);
4943 return SDValue(N, 0);
4947 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4948 SDValue Offset, ISD::MemIndexedMode AM) {
4949 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4950 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4951 "Store is already a indexed store!");
4952 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4953 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4954 FoldingSetNodeID ID;
4955 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4956 ID.AddInteger(ST->getMemoryVT().getRawBits());
4957 ID.AddInteger(ST->getRawSubclassData());
4958 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4960 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4961 return SDValue(E, 0);
4963 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4964 dl.getDebugLoc(), VTs, AM,
4965 ST->isTruncatingStore(),
4967 ST->getMemOperand());
4968 CSEMap.InsertNode(N, IP);
4969 AllNodes.push_back(N);
4970 return SDValue(N, 0);
4973 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4974 SDValue Chain, SDValue Ptr,
4977 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4978 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4981 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4982 ArrayRef<SDUse> Ops) {
4983 switch (Ops.size()) {
4984 case 0: return getNode(Opcode, DL, VT);
4985 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4986 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4987 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4991 // Copy from an SDUse array into an SDValue array for use with
4992 // the regular getNode logic.
4993 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4994 return getNode(Opcode, DL, VT, NewOps);
4997 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4998 ArrayRef<SDValue> Ops) {
4999 unsigned NumOps = Ops.size();
5001 case 0: return getNode(Opcode, DL, VT);
5002 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5003 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5004 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5010 case ISD::SELECT_CC: {
5011 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5012 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5013 "LHS and RHS of condition must have same type!");
5014 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5015 "True and False arms of SelectCC must have same type!");
5016 assert(Ops[2].getValueType() == VT &&
5017 "select_cc node must be of same type as true and false value!");
5021 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5022 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5023 "LHS/RHS of comparison should match types!");
5030 SDVTList VTs = getVTList(VT);
5032 if (VT != MVT::Glue) {
5033 FoldingSetNodeID ID;
5034 AddNodeIDNode(ID, Opcode, VTs, Ops);
5037 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5038 return SDValue(E, 0);
5040 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5042 CSEMap.InsertNode(N, IP);
5044 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5048 AllNodes.push_back(N);
5052 return SDValue(N, 0);
5055 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5056 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5057 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5060 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5061 ArrayRef<SDValue> Ops) {
5062 if (VTList.NumVTs == 1)
5063 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5067 // FIXME: figure out how to safely handle things like
5068 // int foo(int x) { return 1 << (x & 255); }
5069 // int bar() { return foo(256); }
5070 case ISD::SRA_PARTS:
5071 case ISD::SRL_PARTS:
5072 case ISD::SHL_PARTS:
5073 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5074 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5075 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5076 else if (N3.getOpcode() == ISD::AND)
5077 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5078 // If the and is only masking out bits that cannot effect the shift,
5079 // eliminate the and.
5080 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5081 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5082 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5088 // Memoize the node unless it returns a flag.
5090 unsigned NumOps = Ops.size();
5091 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5092 FoldingSetNodeID ID;
5093 AddNodeIDNode(ID, Opcode, VTList, Ops);
5095 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5096 return SDValue(E, 0);
5099 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5100 DL.getDebugLoc(), VTList, Ops[0]);
5101 } else if (NumOps == 2) {
5102 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5103 DL.getDebugLoc(), VTList, Ops[0],
5105 } else if (NumOps == 3) {
5106 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5107 DL.getDebugLoc(), VTList, Ops[0],
5110 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5113 CSEMap.InsertNode(N, IP);
5116 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5117 DL.getDebugLoc(), VTList, Ops[0]);
5118 } else if (NumOps == 2) {
5119 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5120 DL.getDebugLoc(), VTList, Ops[0],
5122 } else if (NumOps == 3) {
5123 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5124 DL.getDebugLoc(), VTList, Ops[0],
5127 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5131 AllNodes.push_back(N);
5135 return SDValue(N, 0);
5138 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5139 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5142 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5144 SDValue Ops[] = { N1 };
5145 return getNode(Opcode, DL, VTList, Ops);
5148 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5149 SDValue N1, SDValue N2) {
5150 SDValue Ops[] = { N1, N2 };
5151 return getNode(Opcode, DL, VTList, Ops);
5154 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5155 SDValue N1, SDValue N2, SDValue N3) {
5156 SDValue Ops[] = { N1, N2, N3 };
5157 return getNode(Opcode, DL, VTList, Ops);
5160 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5161 SDValue N1, SDValue N2, SDValue N3,
5163 SDValue Ops[] = { N1, N2, N3, N4 };
5164 return getNode(Opcode, DL, VTList, Ops);
5167 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5168 SDValue N1, SDValue N2, SDValue N3,
5169 SDValue N4, SDValue N5) {
5170 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5171 return getNode(Opcode, DL, VTList, Ops);
5174 SDVTList SelectionDAG::getVTList(EVT VT) {
5175 return makeVTList(SDNode::getValueTypeList(VT), 1);
5178 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5179 FoldingSetNodeID ID;
5181 ID.AddInteger(VT1.getRawBits());
5182 ID.AddInteger(VT2.getRawBits());
5185 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5187 EVT *Array = Allocator.Allocate<EVT>(2);
5190 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5191 VTListMap.InsertNode(Result, IP);
5193 return Result->getSDVTList();
5196 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5197 FoldingSetNodeID ID;
5199 ID.AddInteger(VT1.getRawBits());
5200 ID.AddInteger(VT2.getRawBits());
5201 ID.AddInteger(VT3.getRawBits());
5204 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5206 EVT *Array = Allocator.Allocate<EVT>(3);
5210 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5211 VTListMap.InsertNode(Result, IP);
5213 return Result->getSDVTList();
5216 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5217 FoldingSetNodeID ID;
5219 ID.AddInteger(VT1.getRawBits());
5220 ID.AddInteger(VT2.getRawBits());
5221 ID.AddInteger(VT3.getRawBits());
5222 ID.AddInteger(VT4.getRawBits());
5225 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5227 EVT *Array = Allocator.Allocate<EVT>(4);
5232 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5233 VTListMap.InsertNode(Result, IP);
5235 return Result->getSDVTList();
5238 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5239 unsigned NumVTs = VTs.size();
5240 FoldingSetNodeID ID;
5241 ID.AddInteger(NumVTs);
5242 for (unsigned index = 0; index < NumVTs; index++) {
5243 ID.AddInteger(VTs[index].getRawBits());
5247 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5249 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5250 std::copy(VTs.begin(), VTs.end(), Array);
5251 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5252 VTListMap.InsertNode(Result, IP);
5254 return Result->getSDVTList();
5258 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5259 /// specified operands. If the resultant node already exists in the DAG,
5260 /// this does not modify the specified node, instead it returns the node that
5261 /// already exists. If the resultant node does not exist in the DAG, the
5262 /// input node is returned. As a degenerate case, if you specify the same
5263 /// input operands as the node already has, the input node is returned.
5264 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5265 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5267 // Check to see if there is no change.
5268 if (Op == N->getOperand(0)) return N;
5270 // See if the modified node already exists.
5271 void *InsertPos = nullptr;
5272 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5275 // Nope it doesn't. Remove the node from its current place in the maps.
5277 if (!RemoveNodeFromCSEMaps(N))
5278 InsertPos = nullptr;
5280 // Now we update the operands.
5281 N->OperandList[0].set(Op);
5283 // If this gets put into a CSE map, add it.
5284 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5288 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5289 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5291 // Check to see if there is no change.
5292 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5293 return N; // No operands changed, just return the input node.
5295 // See if the modified node already exists.
5296 void *InsertPos = nullptr;
5297 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5300 // Nope it doesn't. Remove the node from its current place in the maps.
5302 if (!RemoveNodeFromCSEMaps(N))
5303 InsertPos = nullptr;
5305 // Now we update the operands.
5306 if (N->OperandList[0] != Op1)
5307 N->OperandList[0].set(Op1);
5308 if (N->OperandList[1] != Op2)
5309 N->OperandList[1].set(Op2);
5311 // If this gets put into a CSE map, add it.
5312 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5316 SDNode *SelectionDAG::
5317 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5318 SDValue Ops[] = { Op1, Op2, Op3 };
5319 return UpdateNodeOperands(N, Ops);
5322 SDNode *SelectionDAG::
5323 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5324 SDValue Op3, SDValue Op4) {
5325 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5326 return UpdateNodeOperands(N, Ops);
5329 SDNode *SelectionDAG::
5330 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5331 SDValue Op3, SDValue Op4, SDValue Op5) {
5332 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5333 return UpdateNodeOperands(N, Ops);
5336 SDNode *SelectionDAG::
5337 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5338 unsigned NumOps = Ops.size();
5339 assert(N->getNumOperands() == NumOps &&
5340 "Update with wrong number of operands");
5342 // Check to see if there is no change.
5343 bool AnyChange = false;
5344 for (unsigned i = 0; i != NumOps; ++i) {
5345 if (Ops[i] != N->getOperand(i)) {
5351 // No operands changed, just return the input node.
5352 if (!AnyChange) return N;
5354 // See if the modified node already exists.
5355 void *InsertPos = nullptr;
5356 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5359 // Nope it doesn't. Remove the node from its current place in the maps.
5361 if (!RemoveNodeFromCSEMaps(N))
5362 InsertPos = nullptr;
5364 // Now we update the operands.
5365 for (unsigned i = 0; i != NumOps; ++i)
5366 if (N->OperandList[i] != Ops[i])
5367 N->OperandList[i].set(Ops[i]);
5369 // If this gets put into a CSE map, add it.
5370 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5374 /// DropOperands - Release the operands and set this node to have
5376 void SDNode::DropOperands() {
5377 // Unlike the code in MorphNodeTo that does this, we don't need to
5378 // watch for dead nodes here.
5379 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5385 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5388 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5390 SDVTList VTs = getVTList(VT);
5391 return SelectNodeTo(N, MachineOpc, VTs, None);
5394 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5395 EVT VT, SDValue Op1) {
5396 SDVTList VTs = getVTList(VT);
5397 SDValue Ops[] = { Op1 };
5398 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5401 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5402 EVT VT, SDValue Op1,
5404 SDVTList VTs = getVTList(VT);
5405 SDValue Ops[] = { Op1, Op2 };
5406 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5409 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5410 EVT VT, SDValue Op1,
5411 SDValue Op2, SDValue Op3) {
5412 SDVTList VTs = getVTList(VT);
5413 SDValue Ops[] = { Op1, Op2, Op3 };
5414 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5417 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5418 EVT VT, ArrayRef<SDValue> Ops) {
5419 SDVTList VTs = getVTList(VT);
5420 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5423 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5424 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5425 SDVTList VTs = getVTList(VT1, VT2);
5426 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5429 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5431 SDVTList VTs = getVTList(VT1, VT2);
5432 return SelectNodeTo(N, MachineOpc, VTs, None);
5435 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5436 EVT VT1, EVT VT2, EVT VT3,
5437 ArrayRef<SDValue> Ops) {
5438 SDVTList VTs = getVTList(VT1, VT2, VT3);
5439 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5442 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5443 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5444 ArrayRef<SDValue> Ops) {
5445 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5446 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5449 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5452 SDVTList VTs = getVTList(VT1, VT2);
5453 SDValue Ops[] = { Op1 };
5454 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5457 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5459 SDValue Op1, SDValue Op2) {
5460 SDVTList VTs = getVTList(VT1, VT2);
5461 SDValue Ops[] = { Op1, Op2 };
5462 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5465 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5467 SDValue Op1, SDValue Op2,
5469 SDVTList VTs = getVTList(VT1, VT2);
5470 SDValue Ops[] = { Op1, Op2, Op3 };
5471 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5474 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5475 EVT VT1, EVT VT2, EVT VT3,
5476 SDValue Op1, SDValue Op2,
5478 SDVTList VTs = getVTList(VT1, VT2, VT3);
5479 SDValue Ops[] = { Op1, Op2, Op3 };
5480 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5483 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5484 SDVTList VTs,ArrayRef<SDValue> Ops) {
5485 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5486 // Reset the NodeID to -1.
5491 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5492 /// the line number information on the merged node since it is not possible to
5493 /// preserve the information that operation is associated with multiple lines.
5494 /// This will make the debugger working better at -O0, were there is a higher
5495 /// probability having other instructions associated with that line.
5497 /// For IROrder, we keep the smaller of the two
5498 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5499 DebugLoc NLoc = N->getDebugLoc();
5500 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5501 (OLoc.getDebugLoc() != NLoc)) {
5502 N->setDebugLoc(DebugLoc());
5504 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5505 N->setIROrder(Order);
5509 /// MorphNodeTo - This *mutates* the specified node to have the specified
5510 /// return type, opcode, and operands.
5512 /// Note that MorphNodeTo returns the resultant node. If there is already a
5513 /// node of the specified opcode and operands, it returns that node instead of
5514 /// the current one. Note that the SDLoc need not be the same.
5516 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5517 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5518 /// node, and because it doesn't require CSE recalculation for any of
5519 /// the node's users.
5521 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5522 SDVTList VTs, ArrayRef<SDValue> Ops) {
5523 unsigned NumOps = Ops.size();
5524 // If an identical node already exists, use it.
5526 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5527 FoldingSetNodeID ID;
5528 AddNodeIDNode(ID, Opc, VTs, Ops);
5529 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5530 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5533 if (!RemoveNodeFromCSEMaps(N))
5536 // Start the morphing.
5538 N->ValueList = VTs.VTs;
5539 N->NumValues = VTs.NumVTs;
5541 // Clear the operands list, updating used nodes to remove this from their
5542 // use list. Keep track of any operands that become dead as a result.
5543 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5544 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5546 SDNode *Used = Use.getNode();
5548 if (Used->use_empty())
5549 DeadNodeSet.insert(Used);
5552 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5553 // Initialize the memory references information.
5554 MN->setMemRefs(nullptr, nullptr);
5555 // If NumOps is larger than the # of operands we can have in a
5556 // MachineSDNode, reallocate the operand list.
5557 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5558 if (MN->OperandsNeedDelete)
5559 delete[] MN->OperandList;
5560 if (NumOps > array_lengthof(MN->LocalOperands))
5561 // We're creating a final node that will live unmorphed for the
5562 // remainder of the current SelectionDAG iteration, so we can allocate
5563 // the operands directly out of a pool with no recycling metadata.
5564 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5565 Ops.data(), NumOps);
5567 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5568 MN->OperandsNeedDelete = false;
5570 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5572 // If NumOps is larger than the # of operands we currently have, reallocate
5573 // the operand list.
5574 if (NumOps > N->NumOperands) {
5575 if (N->OperandsNeedDelete)
5576 delete[] N->OperandList;
5577 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5578 N->OperandsNeedDelete = true;
5580 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5583 // Delete any nodes that are still dead after adding the uses for the
5585 if (!DeadNodeSet.empty()) {
5586 SmallVector<SDNode *, 16> DeadNodes;
5587 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5588 E = DeadNodeSet.end(); I != E; ++I)
5589 if ((*I)->use_empty())
5590 DeadNodes.push_back(*I);
5591 RemoveDeadNodes(DeadNodes);
5595 CSEMap.InsertNode(N, IP); // Memoize the new node.
5600 /// getMachineNode - These are used for target selectors to create a new node
5601 /// with specified return type(s), MachineInstr opcode, and operands.
5603 /// Note that getMachineNode returns the resultant node. If there is already a
5604 /// node of the specified opcode and operands, it returns that node instead of
5605 /// the current one.
5607 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5608 SDVTList VTs = getVTList(VT);
5609 return getMachineNode(Opcode, dl, VTs, None);
5613 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5614 SDVTList VTs = getVTList(VT);
5615 SDValue Ops[] = { Op1 };
5616 return getMachineNode(Opcode, dl, VTs, Ops);
5620 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5621 SDValue Op1, SDValue Op2) {
5622 SDVTList VTs = getVTList(VT);
5623 SDValue Ops[] = { Op1, Op2 };
5624 return getMachineNode(Opcode, dl, VTs, Ops);
5628 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5629 SDValue Op1, SDValue Op2, SDValue Op3) {
5630 SDVTList VTs = getVTList(VT);
5631 SDValue Ops[] = { Op1, Op2, Op3 };
5632 return getMachineNode(Opcode, dl, VTs, Ops);
5636 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5637 ArrayRef<SDValue> Ops) {
5638 SDVTList VTs = getVTList(VT);
5639 return getMachineNode(Opcode, dl, VTs, Ops);
5643 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5644 SDVTList VTs = getVTList(VT1, VT2);
5645 return getMachineNode(Opcode, dl, VTs, None);
5649 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5650 EVT VT1, EVT VT2, SDValue Op1) {
5651 SDVTList VTs = getVTList(VT1, VT2);
5652 SDValue Ops[] = { Op1 };
5653 return getMachineNode(Opcode, dl, VTs, Ops);
5657 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5658 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5659 SDVTList VTs = getVTList(VT1, VT2);
5660 SDValue Ops[] = { Op1, Op2 };
5661 return getMachineNode(Opcode, dl, VTs, Ops);
5665 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5666 EVT VT1, EVT VT2, SDValue Op1,
5667 SDValue Op2, SDValue Op3) {
5668 SDVTList VTs = getVTList(VT1, VT2);
5669 SDValue Ops[] = { Op1, Op2, Op3 };
5670 return getMachineNode(Opcode, dl, VTs, Ops);
5674 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5676 ArrayRef<SDValue> Ops) {
5677 SDVTList VTs = getVTList(VT1, VT2);
5678 return getMachineNode(Opcode, dl, VTs, Ops);
5682 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5683 EVT VT1, EVT VT2, EVT VT3,
5684 SDValue Op1, SDValue Op2) {
5685 SDVTList VTs = getVTList(VT1, VT2, VT3);
5686 SDValue Ops[] = { Op1, Op2 };
5687 return getMachineNode(Opcode, dl, VTs, Ops);
5691 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5692 EVT VT1, EVT VT2, EVT VT3,
5693 SDValue Op1, SDValue Op2, SDValue Op3) {
5694 SDVTList VTs = getVTList(VT1, VT2, VT3);
5695 SDValue Ops[] = { Op1, Op2, Op3 };
5696 return getMachineNode(Opcode, dl, VTs, Ops);
5700 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5701 EVT VT1, EVT VT2, EVT VT3,
5702 ArrayRef<SDValue> Ops) {
5703 SDVTList VTs = getVTList(VT1, VT2, VT3);
5704 return getMachineNode(Opcode, dl, VTs, Ops);
5708 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5709 EVT VT2, EVT VT3, EVT VT4,
5710 ArrayRef<SDValue> Ops) {
5711 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5712 return getMachineNode(Opcode, dl, VTs, Ops);
5716 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5717 ArrayRef<EVT> ResultTys,
5718 ArrayRef<SDValue> Ops) {
5719 SDVTList VTs = getVTList(ResultTys);
5720 return getMachineNode(Opcode, dl, VTs, Ops);
5724 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5725 ArrayRef<SDValue> OpsArray) {
5726 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5729 const SDValue *Ops = OpsArray.data();
5730 unsigned NumOps = OpsArray.size();
5733 FoldingSetNodeID ID;
5734 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5736 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5737 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5741 // Allocate a new MachineSDNode.
5742 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5743 DL.getDebugLoc(), VTs);
5745 // Initialize the operands list.
5746 if (NumOps > array_lengthof(N->LocalOperands))
5747 // We're creating a final node that will live unmorphed for the
5748 // remainder of the current SelectionDAG iteration, so we can allocate
5749 // the operands directly out of a pool with no recycling metadata.
5750 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5753 N->InitOperands(N->LocalOperands, Ops, NumOps);
5754 N->OperandsNeedDelete = false;
5757 CSEMap.InsertNode(N, IP);
5759 AllNodes.push_back(N);
5761 VerifyMachineNode(N);
5766 /// getTargetExtractSubreg - A convenience function for creating
5767 /// TargetOpcode::EXTRACT_SUBREG nodes.
5769 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5771 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5772 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5773 VT, Operand, SRIdxVal);
5774 return SDValue(Subreg, 0);
5777 /// getTargetInsertSubreg - A convenience function for creating
5778 /// TargetOpcode::INSERT_SUBREG nodes.
5780 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5781 SDValue Operand, SDValue Subreg) {
5782 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5783 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5784 VT, Operand, Subreg, SRIdxVal);
5785 return SDValue(Result, 0);
5788 /// getNodeIfExists - Get the specified node if it's already available, or
5789 /// else return NULL.
5790 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5791 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5793 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5794 FoldingSetNodeID ID;
5795 AddNodeIDNode(ID, Opcode, VTList, Ops);
5796 if (isBinOpWithFlags(Opcode))
5797 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5799 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5805 /// getDbgValue - Creates a SDDbgValue node.
5809 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5810 bool IsIndirect, uint64_t Off,
5811 DebugLoc DL, unsigned O) {
5812 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5817 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5819 DebugLoc DL, unsigned O) {
5820 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5825 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5826 DebugLoc DL, unsigned O) {
5827 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5832 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5833 /// pointed to by a use iterator is deleted, increment the use iterator
5834 /// so that it doesn't dangle.
5836 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5837 SDNode::use_iterator &UI;
5838 SDNode::use_iterator &UE;
5840 void NodeDeleted(SDNode *N, SDNode *E) override {
5841 // Increment the iterator as needed.
5842 while (UI != UE && N == *UI)
5847 RAUWUpdateListener(SelectionDAG &d,
5848 SDNode::use_iterator &ui,
5849 SDNode::use_iterator &ue)
5850 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5855 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5856 /// This can cause recursive merging of nodes in the DAG.
5858 /// This version assumes From has a single result value.
5860 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5861 SDNode *From = FromN.getNode();
5862 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5863 "Cannot replace with this method!");
5864 assert(From != To.getNode() && "Cannot replace uses of with self");
5866 // Iterate over all the existing uses of From. New uses will be added
5867 // to the beginning of the use list, which we avoid visiting.
5868 // This specifically avoids visiting uses of From that arise while the
5869 // replacement is happening, because any such uses would be the result
5870 // of CSE: If an existing node looks like From after one of its operands
5871 // is replaced by To, we don't want to replace of all its users with To
5872 // too. See PR3018 for more info.
5873 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5874 RAUWUpdateListener Listener(*this, UI, UE);
5878 // This node is about to morph, remove its old self from the CSE maps.
5879 RemoveNodeFromCSEMaps(User);
5881 // A user can appear in a use list multiple times, and when this
5882 // happens the uses are usually next to each other in the list.
5883 // To help reduce the number of CSE recomputations, process all
5884 // the uses of this user that we can find this way.
5886 SDUse &Use = UI.getUse();
5889 } while (UI != UE && *UI == User);
5891 // Now that we have modified User, add it back to the CSE maps. If it
5892 // already exists there, recursively merge the results together.
5893 AddModifiedNodeToCSEMaps(User);
5896 // If we just RAUW'd the root, take note.
5897 if (FromN == getRoot())
5901 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5902 /// This can cause recursive merging of nodes in the DAG.
5904 /// This version assumes that for each value of From, there is a
5905 /// corresponding value in To in the same position with the same type.
5907 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5909 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5910 assert((!From->hasAnyUseOfValue(i) ||
5911 From->getValueType(i) == To->getValueType(i)) &&
5912 "Cannot use this version of ReplaceAllUsesWith!");
5915 // Handle the trivial case.
5919 // Iterate over just the existing users of From. See the comments in
5920 // the ReplaceAllUsesWith above.
5921 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5922 RAUWUpdateListener Listener(*this, UI, UE);
5926 // This node is about to morph, remove its old self from the CSE maps.
5927 RemoveNodeFromCSEMaps(User);
5929 // A user can appear in a use list multiple times, and when this
5930 // happens the uses are usually next to each other in the list.
5931 // To help reduce the number of CSE recomputations, process all
5932 // the uses of this user that we can find this way.
5934 SDUse &Use = UI.getUse();
5937 } while (UI != UE && *UI == User);
5939 // Now that we have modified User, add it back to the CSE maps. If it
5940 // already exists there, recursively merge the results together.
5941 AddModifiedNodeToCSEMaps(User);
5944 // If we just RAUW'd the root, take note.
5945 if (From == getRoot().getNode())
5946 setRoot(SDValue(To, getRoot().getResNo()));
5949 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5950 /// This can cause recursive merging of nodes in the DAG.
5952 /// This version can replace From with any result values. To must match the
5953 /// number and types of values returned by From.
5954 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5955 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5956 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5958 // Iterate over just the existing users of From. See the comments in
5959 // the ReplaceAllUsesWith above.
5960 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5961 RAUWUpdateListener Listener(*this, UI, UE);
5965 // This node is about to morph, remove its old self from the CSE maps.
5966 RemoveNodeFromCSEMaps(User);
5968 // A user can appear in a use list multiple times, and when this
5969 // happens the uses are usually next to each other in the list.
5970 // To help reduce the number of CSE recomputations, process all
5971 // the uses of this user that we can find this way.
5973 SDUse &Use = UI.getUse();
5974 const SDValue &ToOp = To[Use.getResNo()];
5977 } while (UI != UE && *UI == User);
5979 // Now that we have modified User, add it back to the CSE maps. If it
5980 // already exists there, recursively merge the results together.
5981 AddModifiedNodeToCSEMaps(User);
5984 // If we just RAUW'd the root, take note.
5985 if (From == getRoot().getNode())
5986 setRoot(SDValue(To[getRoot().getResNo()]));
5989 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5990 /// uses of other values produced by From.getNode() alone. The Deleted
5991 /// vector is handled the same way as for ReplaceAllUsesWith.
5992 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5993 // Handle the really simple, really trivial case efficiently.
5994 if (From == To) return;
5996 // Handle the simple, trivial, case efficiently.
5997 if (From.getNode()->getNumValues() == 1) {
5998 ReplaceAllUsesWith(From, To);
6002 // Iterate over just the existing users of From. See the comments in
6003 // the ReplaceAllUsesWith above.
6004 SDNode::use_iterator UI = From.getNode()->use_begin(),
6005 UE = From.getNode()->use_end();
6006 RAUWUpdateListener Listener(*this, UI, UE);
6009 bool UserRemovedFromCSEMaps = false;
6011 // A user can appear in a use list multiple times, and when this
6012 // happens the uses are usually next to each other in the list.
6013 // To help reduce the number of CSE recomputations, process all
6014 // the uses of this user that we can find this way.
6016 SDUse &Use = UI.getUse();
6018 // Skip uses of different values from the same node.
6019 if (Use.getResNo() != From.getResNo()) {
6024 // If this node hasn't been modified yet, it's still in the CSE maps,
6025 // so remove its old self from the CSE maps.
6026 if (!UserRemovedFromCSEMaps) {
6027 RemoveNodeFromCSEMaps(User);
6028 UserRemovedFromCSEMaps = true;
6033 } while (UI != UE && *UI == User);
6035 // We are iterating over all uses of the From node, so if a use
6036 // doesn't use the specific value, no changes are made.
6037 if (!UserRemovedFromCSEMaps)
6040 // Now that we have modified User, add it back to the CSE maps. If it
6041 // already exists there, recursively merge the results together.
6042 AddModifiedNodeToCSEMaps(User);
6045 // If we just RAUW'd the root, take note.
6046 if (From == getRoot())
6051 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6052 /// to record information about a use.
6059 /// operator< - Sort Memos by User.
6060 bool operator<(const UseMemo &L, const UseMemo &R) {
6061 return (intptr_t)L.User < (intptr_t)R.User;
6065 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6066 /// uses of other values produced by From.getNode() alone. The same value
6067 /// may appear in both the From and To list. The Deleted vector is
6068 /// handled the same way as for ReplaceAllUsesWith.
6069 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6072 // Handle the simple, trivial case efficiently.
6074 return ReplaceAllUsesOfValueWith(*From, *To);
6076 // Read up all the uses and make records of them. This helps
6077 // processing new uses that are introduced during the
6078 // replacement process.
6079 SmallVector<UseMemo, 4> Uses;
6080 for (unsigned i = 0; i != Num; ++i) {
6081 unsigned FromResNo = From[i].getResNo();
6082 SDNode *FromNode = From[i].getNode();
6083 for (SDNode::use_iterator UI = FromNode->use_begin(),
6084 E = FromNode->use_end(); UI != E; ++UI) {
6085 SDUse &Use = UI.getUse();
6086 if (Use.getResNo() == FromResNo) {
6087 UseMemo Memo = { *UI, i, &Use };
6088 Uses.push_back(Memo);
6093 // Sort the uses, so that all the uses from a given User are together.
6094 std::sort(Uses.begin(), Uses.end());
6096 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6097 UseIndex != UseIndexEnd; ) {
6098 // We know that this user uses some value of From. If it is the right
6099 // value, update it.
6100 SDNode *User = Uses[UseIndex].User;
6102 // This node is about to morph, remove its old self from the CSE maps.
6103 RemoveNodeFromCSEMaps(User);
6105 // The Uses array is sorted, so all the uses for a given User
6106 // are next to each other in the list.
6107 // To help reduce the number of CSE recomputations, process all
6108 // the uses of this user that we can find this way.
6110 unsigned i = Uses[UseIndex].Index;
6111 SDUse &Use = *Uses[UseIndex].Use;
6115 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6117 // Now that we have modified User, add it back to the CSE maps. If it
6118 // already exists there, recursively merge the results together.
6119 AddModifiedNodeToCSEMaps(User);
6123 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6124 /// based on their topological order. It returns the maximum id and a vector
6125 /// of the SDNodes* in assigned order by reference.
6126 unsigned SelectionDAG::AssignTopologicalOrder() {
6128 unsigned DAGSize = 0;
6130 // SortedPos tracks the progress of the algorithm. Nodes before it are
6131 // sorted, nodes after it are unsorted. When the algorithm completes
6132 // it is at the end of the list.
6133 allnodes_iterator SortedPos = allnodes_begin();
6135 // Visit all the nodes. Move nodes with no operands to the front of
6136 // the list immediately. Annotate nodes that do have operands with their
6137 // operand count. Before we do this, the Node Id fields of the nodes
6138 // may contain arbitrary values. After, the Node Id fields for nodes
6139 // before SortedPos will contain the topological sort index, and the
6140 // Node Id fields for nodes At SortedPos and after will contain the
6141 // count of outstanding operands.
6142 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6144 checkForCycles(N, this);
6145 unsigned Degree = N->getNumOperands();
6147 // A node with no uses, add it to the result array immediately.
6148 N->setNodeId(DAGSize++);
6149 allnodes_iterator Q = N;
6151 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6152 assert(SortedPos != AllNodes.end() && "Overran node list");
6155 // Temporarily use the Node Id as scratch space for the degree count.
6156 N->setNodeId(Degree);
6160 // Visit all the nodes. As we iterate, move nodes into sorted order,
6161 // such that by the time the end is reached all nodes will be sorted.
6162 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6164 checkForCycles(N, this);
6165 // N is in sorted position, so all its uses have one less operand
6166 // that needs to be sorted.
6167 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6170 unsigned Degree = P->getNodeId();
6171 assert(Degree != 0 && "Invalid node degree");
6174 // All of P's operands are sorted, so P may sorted now.
6175 P->setNodeId(DAGSize++);
6177 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6178 assert(SortedPos != AllNodes.end() && "Overran node list");
6181 // Update P's outstanding operand count.
6182 P->setNodeId(Degree);
6185 if (I == SortedPos) {
6188 dbgs() << "Overran sorted position:\n";
6189 S->dumprFull(this); dbgs() << "\n";
6190 dbgs() << "Checking if this is due to cycles\n";
6191 checkForCycles(this, true);
6193 llvm_unreachable(nullptr);
6197 assert(SortedPos == AllNodes.end() &&
6198 "Topological sort incomplete!");
6199 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6200 "First node in topological sort is not the entry token!");
6201 assert(AllNodes.front().getNodeId() == 0 &&
6202 "First node in topological sort has non-zero id!");
6203 assert(AllNodes.front().getNumOperands() == 0 &&
6204 "First node in topological sort has operands!");
6205 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6206 "Last node in topologic sort has unexpected id!");
6207 assert(AllNodes.back().use_empty() &&
6208 "Last node in topologic sort has users!");
6209 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6213 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6214 /// value is produced by SD.
6215 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6216 DbgInfo->add(DB, SD, isParameter);
6218 SD->setHasDebugValue(true);
6221 /// TransferDbgValues - Transfer SDDbgValues.
6222 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6223 if (From == To || !From.getNode()->getHasDebugValue())
6225 SDNode *FromNode = From.getNode();
6226 SDNode *ToNode = To.getNode();
6227 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6228 SmallVector<SDDbgValue *, 2> ClonedDVs;
6229 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6231 SDDbgValue *Dbg = *I;
6232 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6233 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6235 Dbg->getOffset(), Dbg->getDebugLoc(),
6237 ClonedDVs.push_back(Clone);
6240 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6241 E = ClonedDVs.end(); I != E; ++I)
6242 AddDbgValue(*I, ToNode, false);
6245 //===----------------------------------------------------------------------===//
6247 //===----------------------------------------------------------------------===//
6249 HandleSDNode::~HandleSDNode() {
6253 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6254 DebugLoc DL, const GlobalValue *GA,
6255 EVT VT, int64_t o, unsigned char TF)
6256 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6260 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6261 SDValue X, unsigned SrcAS,
6263 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6264 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6266 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6267 EVT memvt, MachineMemOperand *mmo)
6268 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6269 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6270 MMO->isNonTemporal(), MMO->isInvariant());
6271 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6272 assert(isNonTemporal() == MMO->isNonTemporal() &&
6273 "Non-temporal encoding error!");
6274 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6277 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6278 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6279 : SDNode(Opc, Order, dl, VTs, Ops),
6280 MemoryVT(memvt), MMO(mmo) {
6281 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6282 MMO->isNonTemporal(), MMO->isInvariant());
6283 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6284 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6287 /// Profile - Gather unique data for the node.
6289 void SDNode::Profile(FoldingSetNodeID &ID) const {
6290 AddNodeIDNode(ID, this);
6295 std::vector<EVT> VTs;
6298 VTs.reserve(MVT::LAST_VALUETYPE);
6299 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6300 VTs.push_back(MVT((MVT::SimpleValueType)i));
6305 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6306 static ManagedStatic<EVTArray> SimpleVTArray;
6307 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6309 /// getValueTypeList - Return a pointer to the specified value type.
6311 const EVT *SDNode::getValueTypeList(EVT VT) {
6312 if (VT.isExtended()) {
6313 sys::SmartScopedLock<true> Lock(*VTMutex);
6314 return &(*EVTs->insert(VT).first);
6316 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6317 "Value type out of range!");
6318 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6322 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6323 /// indicated value. This method ignores uses of other values defined by this
6325 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6326 assert(Value < getNumValues() && "Bad value!");
6328 // TODO: Only iterate over uses of a given value of the node
6329 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6330 if (UI.getUse().getResNo() == Value) {
6337 // Found exactly the right number of uses?
6342 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6343 /// value. This method ignores uses of other values defined by this operation.
6344 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6345 assert(Value < getNumValues() && "Bad value!");
6347 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6348 if (UI.getUse().getResNo() == Value)
6355 /// isOnlyUserOf - Return true if this node is the only use of N.
6357 bool SDNode::isOnlyUserOf(SDNode *N) const {
6359 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6370 /// isOperand - Return true if this node is an operand of N.
6372 bool SDValue::isOperandOf(SDNode *N) const {
6373 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6374 if (*this == N->getOperand(i))
6379 bool SDNode::isOperandOf(SDNode *N) const {
6380 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6381 if (this == N->OperandList[i].getNode())
6386 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6387 /// be a chain) reaches the specified operand without crossing any
6388 /// side-effecting instructions on any chain path. In practice, this looks
6389 /// through token factors and non-volatile loads. In order to remain efficient,
6390 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6391 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6392 unsigned Depth) const {
6393 if (*this == Dest) return true;
6395 // Don't search too deeply, we just want to be able to see through
6396 // TokenFactor's etc.
6397 if (Depth == 0) return false;
6399 // If this is a token factor, all inputs to the TF happen in parallel. If any
6400 // of the operands of the TF does not reach dest, then we cannot do the xform.
6401 if (getOpcode() == ISD::TokenFactor) {
6402 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6403 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6408 // Loads don't have side effects, look through them.
6409 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6410 if (!Ld->isVolatile())
6411 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6416 /// hasPredecessor - Return true if N is a predecessor of this node.
6417 /// N is either an operand of this node, or can be reached by recursively
6418 /// traversing up the operands.
6419 /// NOTE: This is an expensive method. Use it carefully.
6420 bool SDNode::hasPredecessor(const SDNode *N) const {
6421 SmallPtrSet<const SDNode *, 32> Visited;
6422 SmallVector<const SDNode *, 16> Worklist;
6423 return hasPredecessorHelper(N, Visited, Worklist);
6427 SDNode::hasPredecessorHelper(const SDNode *N,
6428 SmallPtrSet<const SDNode *, 32> &Visited,
6429 SmallVectorImpl<const SDNode *> &Worklist) const {
6430 if (Visited.empty()) {
6431 Worklist.push_back(this);
6433 // Take a look in the visited set. If we've already encountered this node
6434 // we needn't search further.
6435 if (Visited.count(N))
6439 // Haven't visited N yet. Continue the search.
6440 while (!Worklist.empty()) {
6441 const SDNode *M = Worklist.pop_back_val();
6442 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6443 SDNode *Op = M->getOperand(i).getNode();
6444 if (Visited.insert(Op))
6445 Worklist.push_back(Op);
6454 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6455 assert(Num < NumOperands && "Invalid child # of SDNode!");
6456 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6459 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6460 assert(N->getNumValues() == 1 &&
6461 "Can't unroll a vector with multiple results!");
6463 EVT VT = N->getValueType(0);
6464 unsigned NE = VT.getVectorNumElements();
6465 EVT EltVT = VT.getVectorElementType();
6468 SmallVector<SDValue, 8> Scalars;
6469 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6471 // If ResNE is 0, fully unroll the vector op.
6474 else if (NE > ResNE)
6478 for (i= 0; i != NE; ++i) {
6479 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6480 SDValue Operand = N->getOperand(j);
6481 EVT OperandVT = Operand.getValueType();
6482 if (OperandVT.isVector()) {
6483 // A vector operand; extract a single element.
6484 const TargetLowering *TLI = TM.getTargetLowering();
6485 EVT OperandEltVT = OperandVT.getVectorElementType();
6486 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6489 getConstant(i, TLI->getVectorIdxTy()));
6491 // A scalar operand; just use it as is.
6492 Operands[j] = Operand;
6496 switch (N->getOpcode()) {
6498 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6501 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6508 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6509 getShiftAmountOperand(Operands[0].getValueType(),
6512 case ISD::SIGN_EXTEND_INREG:
6513 case ISD::FP_ROUND_INREG: {
6514 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6515 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6517 getValueType(ExtVT)));
6522 for (; i < ResNE; ++i)
6523 Scalars.push_back(getUNDEF(EltVT));
6525 return getNode(ISD::BUILD_VECTOR, dl,
6526 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6530 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6531 /// location that is 'Dist' units away from the location that the 'Base' load
6532 /// is loading from.
6533 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6534 unsigned Bytes, int Dist) const {
6535 if (LD->getChain() != Base->getChain())
6537 EVT VT = LD->getValueType(0);
6538 if (VT.getSizeInBits() / 8 != Bytes)
6541 SDValue Loc = LD->getOperand(1);
6542 SDValue BaseLoc = Base->getOperand(1);
6543 if (Loc.getOpcode() == ISD::FrameIndex) {
6544 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6546 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6547 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6548 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6549 int FS = MFI->getObjectSize(FI);
6550 int BFS = MFI->getObjectSize(BFI);
6551 if (FS != BFS || FS != (int)Bytes) return false;
6552 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6556 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6557 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6560 const GlobalValue *GV1 = nullptr;
6561 const GlobalValue *GV2 = nullptr;
6562 int64_t Offset1 = 0;
6563 int64_t Offset2 = 0;
6564 const TargetLowering *TLI = TM.getTargetLowering();
6565 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6566 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6567 if (isGA1 && isGA2 && GV1 == GV2)
6568 return Offset1 == (Offset2 + Dist*Bytes);
6573 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6574 /// it cannot be inferred.
6575 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6576 // If this is a GlobalAddress + cst, return the alignment.
6577 const GlobalValue *GV;
6578 int64_t GVOffset = 0;
6579 const TargetLowering *TLI = TM.getTargetLowering();
6580 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6581 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6582 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6583 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6584 TLI->getDataLayout());
6585 unsigned AlignBits = KnownZero.countTrailingOnes();
6586 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6588 return MinAlign(Align, GVOffset);
6591 // If this is a direct reference to a stack slot, use information about the
6592 // stack slot's alignment.
6593 int FrameIdx = 1 << 31;
6594 int64_t FrameOffset = 0;
6595 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6596 FrameIdx = FI->getIndex();
6597 } else if (isBaseWithConstantOffset(Ptr) &&
6598 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6600 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6601 FrameOffset = Ptr.getConstantOperandVal(1);
6604 if (FrameIdx != (1 << 31)) {
6605 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6606 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6614 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6615 /// which is split (or expanded) into two not necessarily identical pieces.
6616 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6617 // Currently all types are split in half.
6619 if (!VT.isVector()) {
6620 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6622 unsigned NumElements = VT.getVectorNumElements();
6623 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6624 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6627 return std::make_pair(LoVT, HiVT);
6630 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6632 std::pair<SDValue, SDValue>
6633 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6635 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6636 N.getValueType().getVectorNumElements() &&
6637 "More vector elements requested than available!");
6639 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6640 getConstant(0, TLI->getVectorIdxTy()));
6641 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6642 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6643 return std::make_pair(Lo, Hi);
6646 void SelectionDAG::ExtractVectorElements(SDValue Op,
6647 SmallVectorImpl<SDValue> &Args,
6648 unsigned Start, unsigned Count) {
6649 EVT VT = Op.getValueType();
6651 Count = VT.getVectorNumElements();
6653 EVT EltVT = VT.getVectorElementType();
6654 EVT IdxTy = TLI->getVectorIdxTy();
6656 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6657 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6658 Op, getConstant(i, IdxTy)));
6662 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6663 unsigned GlobalAddressSDNode::getAddressSpace() const {
6664 return getGlobal()->getType()->getAddressSpace();
6668 Type *ConstantPoolSDNode::getType() const {
6669 if (isMachineConstantPoolEntry())
6670 return Val.MachineCPVal->getType();
6671 return Val.ConstVal->getType();
6674 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6676 unsigned &SplatBitSize,
6678 unsigned MinSplatBits,
6679 bool isBigEndian) const {
6680 EVT VT = getValueType(0);
6681 assert(VT.isVector() && "Expected a vector type");
6682 unsigned sz = VT.getSizeInBits();
6683 if (MinSplatBits > sz)
6686 SplatValue = APInt(sz, 0);
6687 SplatUndef = APInt(sz, 0);
6689 // Get the bits. Bits with undefined values (when the corresponding element
6690 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6691 // in SplatValue. If any of the values are not constant, give up and return
6693 unsigned int nOps = getNumOperands();
6694 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6695 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6697 for (unsigned j = 0; j < nOps; ++j) {
6698 unsigned i = isBigEndian ? nOps-1-j : j;
6699 SDValue OpVal = getOperand(i);
6700 unsigned BitPos = j * EltBitSize;
6702 if (OpVal.getOpcode() == ISD::UNDEF)
6703 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6704 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6705 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6706 zextOrTrunc(sz) << BitPos;
6707 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6708 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6713 // The build_vector is all constants or undefs. Find the smallest element
6714 // size that splats the vector.
6716 HasAnyUndefs = (SplatUndef != 0);
6719 unsigned HalfSize = sz / 2;
6720 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6721 APInt LowValue = SplatValue.trunc(HalfSize);
6722 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6723 APInt LowUndef = SplatUndef.trunc(HalfSize);
6725 // If the two halves do not match (ignoring undef bits), stop here.
6726 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6727 MinSplatBits > HalfSize)
6730 SplatValue = HighValue | LowValue;
6731 SplatUndef = HighUndef & LowUndef;
6740 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6741 if (UndefElements) {
6742 UndefElements->clear();
6743 UndefElements->resize(getNumOperands());
6746 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6747 SDValue Op = getOperand(i);
6748 if (Op.getOpcode() == ISD::UNDEF) {
6750 (*UndefElements)[i] = true;
6751 } else if (!Splatted) {
6753 } else if (Splatted != Op) {
6759 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6760 "Can only have a splat without a constant for all undefs.");
6761 return getOperand(0);
6768 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6769 return dyn_cast_or_null<ConstantSDNode>(
6770 getSplatValue(UndefElements).getNode());
6774 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6775 return dyn_cast_or_null<ConstantFPSDNode>(
6776 getSplatValue(UndefElements).getNode());
6779 bool BuildVectorSDNode::isConstant() const {
6780 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6781 unsigned Opc = getOperand(i).getOpcode();
6782 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6788 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6789 // Find the first non-undef value in the shuffle mask.
6791 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6794 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6796 // Make sure all remaining elements are either undef or the same as the first
6798 for (int Idx = Mask[i]; i != e; ++i)
6799 if (Mask[i] >= 0 && Mask[i] != Idx)
6805 static void checkForCyclesHelper(const SDNode *N,
6806 SmallPtrSet<const SDNode*, 32> &Visited,
6807 SmallPtrSet<const SDNode*, 32> &Checked,
6808 const llvm::SelectionDAG *DAG) {
6809 // If this node has already been checked, don't check it again.
6810 if (Checked.count(N))
6813 // If a node has already been visited on this depth-first walk, reject it as
6815 if (!Visited.insert(N)) {
6816 errs() << "Detected cycle in SelectionDAG\n";
6817 dbgs() << "Offending node:\n";
6818 N->dumprFull(DAG); dbgs() << "\n";
6822 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6823 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6830 void llvm::checkForCycles(const llvm::SDNode *N,
6831 const llvm::SelectionDAG *DAG,
6839 assert(N && "Checking nonexistent SDNode");
6840 SmallPtrSet<const SDNode*, 32> visited;
6841 SmallPtrSet<const SDNode*, 32> checked;
6842 checkForCyclesHelper(N, visited, checked, DAG);
6847 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6848 checkForCycles(DAG->getRoot().getNode(), DAG, force);