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 SelectionDAG::DeallocateNode(SDNode *N) {
690 if (N->OperandsNeedDelete)
691 delete[] N->OperandList;
693 // Set the opcode to DELETED_NODE to help catch bugs when node
694 // memory is reallocated.
695 N->NodeType = ISD::DELETED_NODE;
697 NodeAllocator.Deallocate(AllNodes.remove(N));
699 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
700 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
701 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
702 DbgVals[i]->setIsInvalidated();
705 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
706 /// correspond to it. This is useful when we're about to delete or repurpose
707 /// the node. We don't want future request for structurally identical nodes
708 /// to return N anymore.
709 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
711 switch (N->getOpcode()) {
712 case ISD::HANDLENODE: return false; // noop.
714 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
715 "Cond code doesn't exist!");
716 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
717 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
719 case ISD::ExternalSymbol:
720 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
722 case ISD::TargetExternalSymbol: {
723 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
724 Erased = TargetExternalSymbols.erase(
725 std::pair<std::string,unsigned char>(ESN->getSymbol(),
726 ESN->getTargetFlags()));
729 case ISD::VALUETYPE: {
730 EVT VT = cast<VTSDNode>(N)->getVT();
731 if (VT.isExtended()) {
732 Erased = ExtendedValueTypeNodes.erase(VT);
734 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
735 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
740 // Remove it from the CSE Map.
741 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
742 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
743 Erased = CSEMap.RemoveNode(N);
747 // Verify that the node was actually in one of the CSE maps, unless it has a
748 // flag result (which cannot be CSE'd) or is one of the special cases that are
749 // not subject to CSE.
750 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
751 !N->isMachineOpcode() && !doNotCSE(N)) {
754 llvm_unreachable("Node is not in map!");
760 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
761 /// maps and modified in place. Add it back to the CSE maps, unless an identical
762 /// node already exists, in which case transfer all its users to the existing
763 /// node. This transfer can potentially trigger recursive merging.
766 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
767 // For node types that aren't CSE'd, just act as if no identical node
770 SDNode *Existing = CSEMap.GetOrInsertNode(N);
772 // If there was already an existing matching node, use ReplaceAllUsesWith
773 // to replace the dead one with the existing one. This can cause
774 // recursive merging of other unrelated nodes down the line.
775 ReplaceAllUsesWith(N, Existing);
777 // N is now dead. Inform the listeners and delete it.
778 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
779 DUL->NodeDeleted(N, Existing);
780 DeleteNodeNotInCSEMaps(N);
785 // If the node doesn't already exist, we updated it. Inform listeners.
786 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
790 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
791 /// were replaced with those specified. If this node is never memoized,
792 /// return null, otherwise return a pointer to the slot it would take. If a
793 /// node already exists with these operands, the slot will be non-null.
794 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
799 SDValue Ops[] = { Op };
801 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
802 AddNodeIDCustom(ID, N);
803 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
807 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
808 /// were replaced with those specified. If this node is never memoized,
809 /// return null, otherwise return a pointer to the slot it would take. If a
810 /// node already exists with these operands, the slot will be non-null.
811 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
812 SDValue Op1, SDValue Op2,
817 SDValue Ops[] = { Op1, Op2 };
819 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
820 AddNodeIDCustom(ID, N);
821 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
826 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
827 /// were replaced with those specified. If this node is never memoized,
828 /// return null, otherwise return a pointer to the slot it would take. If a
829 /// node already exists with these operands, the slot will be non-null.
830 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
836 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
837 AddNodeIDCustom(ID, N);
838 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
843 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
844 static void VerifyNodeCommon(SDNode *N) {
845 switch (N->getOpcode()) {
848 case ISD::BUILD_PAIR: {
849 EVT VT = N->getValueType(0);
850 assert(N->getNumValues() == 1 && "Too many results!");
851 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
852 "Wrong return type!");
853 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
854 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
855 "Mismatched operand types!");
856 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
857 "Wrong operand type!");
858 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
859 "Wrong return type size");
862 case ISD::BUILD_VECTOR: {
863 assert(N->getNumValues() == 1 && "Too many results!");
864 assert(N->getValueType(0).isVector() && "Wrong return type!");
865 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
866 "Wrong number of operands!");
867 EVT EltVT = N->getValueType(0).getVectorElementType();
868 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
869 assert((I->getValueType() == EltVT ||
870 (EltVT.isInteger() && I->getValueType().isInteger() &&
871 EltVT.bitsLE(I->getValueType()))) &&
872 "Wrong operand type!");
873 assert(I->getValueType() == N->getOperand(0).getValueType() &&
874 "Operands must all have the same type");
881 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
882 static void VerifySDNode(SDNode *N) {
883 // The SDNode allocators cannot be used to allocate nodes with fields that are
884 // not present in an SDNode!
885 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
886 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
887 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
888 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
889 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
890 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
891 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
892 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
893 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
894 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
895 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
896 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
897 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
898 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
899 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
900 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
901 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
902 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
903 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
908 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
910 static void VerifyMachineNode(SDNode *N) {
911 // The MachineNode allocators cannot be used to allocate nodes with fields
912 // that are not present in a MachineNode!
913 // Currently there are no such nodes.
919 /// getEVTAlignment - Compute the default alignment value for the
922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
923 Type *Ty = VT == MVT::iPTR ?
924 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
925 VT.getTypeForEVT(*getContext());
927 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
930 // EntryNode could meaningfully have debug info if we can find it...
931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
932 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
935 UpdateListeners(nullptr) {
936 AllNodes.push_back(&EntryNode);
937 DbgInfo = new SDDbgInfo();
940 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
943 Context = &mf.getFunction()->getContext();
946 SelectionDAG::~SelectionDAG() {
947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
952 void SelectionDAG::allnodes_clear() {
953 assert(&*AllNodes.begin() == &EntryNode);
954 AllNodes.remove(AllNodes.begin());
955 while (!AllNodes.empty())
956 DeallocateNode(AllNodes.begin());
959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
960 SDVTList VTs, SDValue N1,
961 SDValue N2, bool nuw, bool nsw,
963 if (isBinOpWithFlags(Opcode)) {
964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
966 FN->setHasNoUnsignedWrap(nuw);
967 FN->setHasNoSignedWrap(nsw);
968 FN->setIsExact(exact);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 void SelectionDAG::clear() {
980 OperandAllocator.Reset();
983 ExtendedValueTypeNodes.clear();
984 ExternalSymbols.clear();
985 TargetExternalSymbols.clear();
986 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
987 static_cast<CondCodeSDNode*>(nullptr));
988 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
989 static_cast<SDNode*>(nullptr));
991 EntryNode.UseList = nullptr;
992 AllNodes.push_back(&EntryNode);
993 Root = getEntryNode();
997 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
998 return VT.bitsGT(Op.getValueType()) ?
999 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1000 getNode(ISD::TRUNCATE, DL, VT, Op);
1003 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1004 return VT.bitsGT(Op.getValueType()) ?
1005 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1006 getNode(ISD::TRUNCATE, DL, VT, Op);
1009 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1010 return VT.bitsGT(Op.getValueType()) ?
1011 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1012 getNode(ISD::TRUNCATE, DL, VT, Op);
1015 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
1016 if (VT.bitsLE(Op.getValueType()))
1017 return getNode(ISD::TRUNCATE, SL, VT, Op);
1019 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
1020 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1023 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1024 assert(!VT.isVector() &&
1025 "getZeroExtendInReg should use the vector element type instead of "
1026 "the vector type!");
1027 if (Op.getValueType() == VT) return Op;
1028 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1029 APInt Imm = APInt::getLowBitsSet(BitWidth,
1030 VT.getSizeInBits());
1031 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1032 getConstant(Imm, Op.getValueType()));
1035 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1037 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1038 EVT EltVT = VT.getScalarType();
1040 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1041 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1044 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1045 EVT EltVT = VT.getScalarType();
1047 switch (TLI->getBooleanContents(VT.isVector())) {
1048 case TargetLowering::ZeroOrOneBooleanContent:
1049 case TargetLowering::UndefinedBooleanContent:
1050 TrueValue = getConstant(1, VT);
1052 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1053 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1057 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1060 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1061 EVT EltVT = VT.getScalarType();
1062 assert((EltVT.getSizeInBits() >= 64 ||
1063 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1064 "getConstant with a uint64_t value that doesn't fit in the type!");
1065 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1068 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1070 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1073 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1075 assert(VT.isInteger() && "Cannot create FP integer constant!");
1077 EVT EltVT = VT.getScalarType();
1078 const ConstantInt *Elt = &Val;
1080 const TargetLowering *TLI = TM.getTargetLowering();
1082 // In some cases the vector type is legal but the element type is illegal and
1083 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1084 // inserted value (the type does not need to match the vector element type).
1085 // Any extra bits introduced will be truncated away.
1086 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1087 TargetLowering::TypePromoteInteger) {
1088 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1089 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1090 Elt = ConstantInt::get(*getContext(), NewVal);
1092 // In other cases the element type is illegal and needs to be expanded, for
1093 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1094 // the value into n parts and use a vector type with n-times the elements.
1095 // Then bitcast to the type requested.
1096 // Legalizing constants too early makes the DAGCombiner's job harder so we
1097 // only legalize if the DAG tells us we must produce legal types.
1098 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1099 TLI->getTypeAction(*getContext(), EltVT) ==
1100 TargetLowering::TypeExpandInteger) {
1101 APInt NewVal = Elt->getValue();
1102 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1103 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1104 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1105 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1107 // Check the temporary vector is the correct size. If this fails then
1108 // getTypeToTransformTo() probably returned a type whose size (in bits)
1109 // isn't a power-of-2 factor of the requested type size.
1110 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1112 SmallVector<SDValue, 2> EltParts;
1113 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1114 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1115 .trunc(ViaEltSizeInBits),
1116 ViaEltVT, isT, isO));
1119 // EltParts is currently in little endian order. If we actually want
1120 // big-endian order then reverse it now.
1121 if (TLI->isBigEndian())
1122 std::reverse(EltParts.begin(), EltParts.end());
1124 // The elements must be reversed when the element order is different
1125 // to the endianness of the elements (because the BITCAST is itself a
1126 // vector shuffle in this situation). However, we do not need any code to
1127 // perform this reversal because getConstant() is producing a vector
1129 // This situation occurs in MIPS MSA.
1131 SmallVector<SDValue, 8> Ops;
1132 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1133 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1135 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1136 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1141 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1142 "APInt size does not match type size!");
1143 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1144 FoldingSetNodeID ID;
1145 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1149 SDNode *N = nullptr;
1150 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1152 return SDValue(N, 0);
1155 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1156 CSEMap.InsertNode(N, IP);
1157 AllNodes.push_back(N);
1160 SDValue Result(N, 0);
1161 if (VT.isVector()) {
1162 SmallVector<SDValue, 8> Ops;
1163 Ops.assign(VT.getVectorNumElements(), Result);
1164 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1169 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1170 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1174 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1175 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1178 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1179 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1181 EVT EltVT = VT.getScalarType();
1183 // Do the map lookup using the actual bit pattern for the floating point
1184 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1185 // we don't have issues with SNANs.
1186 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1187 FoldingSetNodeID ID;
1188 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1191 SDNode *N = nullptr;
1192 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1194 return SDValue(N, 0);
1197 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1198 CSEMap.InsertNode(N, IP);
1199 AllNodes.push_back(N);
1202 SDValue Result(N, 0);
1203 if (VT.isVector()) {
1204 SmallVector<SDValue, 8> Ops;
1205 Ops.assign(VT.getVectorNumElements(), Result);
1206 // FIXME SDLoc info might be appropriate here
1207 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1212 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1213 EVT EltVT = VT.getScalarType();
1214 if (EltVT==MVT::f32)
1215 return getConstantFP(APFloat((float)Val), VT, isTarget);
1216 else if (EltVT==MVT::f64)
1217 return getConstantFP(APFloat(Val), VT, isTarget);
1218 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1221 APFloat apf = APFloat(Val);
1222 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1224 return getConstantFP(apf, VT, isTarget);
1226 llvm_unreachable("Unsupported type in getConstantFP");
1229 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1230 EVT VT, int64_t Offset,
1232 unsigned char TargetFlags) {
1233 assert((TargetFlags == 0 || isTargetGA) &&
1234 "Cannot set target flags on target-independent globals");
1235 const TargetLowering *TLI = TM.getTargetLowering();
1237 // Truncate (with sign-extension) the offset value to the pointer size.
1238 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1240 Offset = SignExtend64(Offset, BitWidth);
1243 if (GV->isThreadLocal())
1244 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1246 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1248 FoldingSetNodeID ID;
1249 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1251 ID.AddInteger(Offset);
1252 ID.AddInteger(TargetFlags);
1253 ID.AddInteger(GV->getType()->getAddressSpace());
1255 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1256 return SDValue(E, 0);
1258 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1259 DL.getDebugLoc(), GV, VT,
1260 Offset, TargetFlags);
1261 CSEMap.InsertNode(N, IP);
1262 AllNodes.push_back(N);
1263 return SDValue(N, 0);
1266 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1267 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1268 FoldingSetNodeID ID;
1269 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1272 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1273 return SDValue(E, 0);
1275 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1276 CSEMap.InsertNode(N, IP);
1277 AllNodes.push_back(N);
1278 return SDValue(N, 0);
1281 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1282 unsigned char TargetFlags) {
1283 assert((TargetFlags == 0 || isTarget) &&
1284 "Cannot set target flags on target-independent jump tables");
1285 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1286 FoldingSetNodeID ID;
1287 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1289 ID.AddInteger(TargetFlags);
1291 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1292 return SDValue(E, 0);
1294 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1296 CSEMap.InsertNode(N, IP);
1297 AllNodes.push_back(N);
1298 return SDValue(N, 0);
1301 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1302 unsigned Alignment, int Offset,
1304 unsigned char TargetFlags) {
1305 assert((TargetFlags == 0 || isTarget) &&
1306 "Cannot set target flags on target-independent globals");
1309 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1310 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1311 FoldingSetNodeID ID;
1312 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1313 ID.AddInteger(Alignment);
1314 ID.AddInteger(Offset);
1316 ID.AddInteger(TargetFlags);
1318 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1319 return SDValue(E, 0);
1321 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1322 Alignment, TargetFlags);
1323 CSEMap.InsertNode(N, IP);
1324 AllNodes.push_back(N);
1325 return SDValue(N, 0);
1329 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1330 unsigned Alignment, int Offset,
1332 unsigned char TargetFlags) {
1333 assert((TargetFlags == 0 || isTarget) &&
1334 "Cannot set target flags on target-independent globals");
1337 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1338 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1339 FoldingSetNodeID ID;
1340 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 ID.AddInteger(Alignment);
1342 ID.AddInteger(Offset);
1343 C->addSelectionDAGCSEId(ID);
1344 ID.AddInteger(TargetFlags);
1346 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1347 return SDValue(E, 0);
1349 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1350 Alignment, TargetFlags);
1351 CSEMap.InsertNode(N, IP);
1352 AllNodes.push_back(N);
1353 return SDValue(N, 0);
1356 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1357 unsigned char TargetFlags) {
1358 FoldingSetNodeID ID;
1359 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1360 ID.AddInteger(Index);
1361 ID.AddInteger(Offset);
1362 ID.AddInteger(TargetFlags);
1364 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1365 return SDValue(E, 0);
1367 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1369 CSEMap.InsertNode(N, IP);
1370 AllNodes.push_back(N);
1371 return SDValue(N, 0);
1374 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1375 FoldingSetNodeID ID;
1376 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1379 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1380 return SDValue(E, 0);
1382 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1383 CSEMap.InsertNode(N, IP);
1384 AllNodes.push_back(N);
1385 return SDValue(N, 0);
1388 SDValue SelectionDAG::getValueType(EVT VT) {
1389 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1390 ValueTypeNodes.size())
1391 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1393 SDNode *&N = VT.isExtended() ?
1394 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1396 if (N) return SDValue(N, 0);
1397 N = new (NodeAllocator) VTSDNode(VT);
1398 AllNodes.push_back(N);
1399 return SDValue(N, 0);
1402 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1403 SDNode *&N = ExternalSymbols[Sym];
1404 if (N) return SDValue(N, 0);
1405 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1406 AllNodes.push_back(N);
1407 return SDValue(N, 0);
1410 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1411 unsigned char TargetFlags) {
1413 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1415 if (N) return SDValue(N, 0);
1416 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1417 AllNodes.push_back(N);
1418 return SDValue(N, 0);
1421 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1422 if ((unsigned)Cond >= CondCodeNodes.size())
1423 CondCodeNodes.resize(Cond+1);
1425 if (!CondCodeNodes[Cond]) {
1426 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1427 CondCodeNodes[Cond] = N;
1428 AllNodes.push_back(N);
1431 return SDValue(CondCodeNodes[Cond], 0);
1434 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1435 // the shuffle mask M that point at N1 to point at N2, and indices that point
1436 // N2 to point at N1.
1437 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1439 int NElts = M.size();
1440 for (int i = 0; i != NElts; ++i) {
1448 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1449 SDValue N2, const int *Mask) {
1450 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1451 "Invalid VECTOR_SHUFFLE");
1453 // Canonicalize shuffle undef, undef -> undef
1454 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1455 return getUNDEF(VT);
1457 // Validate that all indices in Mask are within the range of the elements
1458 // input to the shuffle.
1459 unsigned NElts = VT.getVectorNumElements();
1460 SmallVector<int, 8> MaskVec;
1461 for (unsigned i = 0; i != NElts; ++i) {
1462 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1463 MaskVec.push_back(Mask[i]);
1466 // Canonicalize shuffle v, v -> v, undef
1469 for (unsigned i = 0; i != NElts; ++i)
1470 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1473 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1474 if (N1.getOpcode() == ISD::UNDEF)
1475 commuteShuffle(N1, N2, MaskVec);
1477 // Canonicalize all index into lhs, -> shuffle lhs, undef
1478 // Canonicalize all index into rhs, -> shuffle rhs, undef
1479 bool AllLHS = true, AllRHS = true;
1480 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1481 for (unsigned i = 0; i != NElts; ++i) {
1482 if (MaskVec[i] >= (int)NElts) {
1487 } else if (MaskVec[i] >= 0) {
1491 if (AllLHS && AllRHS)
1492 return getUNDEF(VT);
1493 if (AllLHS && !N2Undef)
1497 commuteShuffle(N1, N2, MaskVec);
1499 // Reset our undef status after accounting for the mask.
1500 N2Undef = N2.getOpcode() == ISD::UNDEF;
1501 // Re-check whether both sides ended up undef.
1502 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1503 return getUNDEF(VT);
1505 // If Identity shuffle return that node.
1506 bool Identity = true;
1507 for (unsigned i = 0; i != NElts; ++i) {
1508 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1510 if (Identity && NElts)
1513 // Shuffling a constant splat doesn't change the result.
1517 // Look through any bitcasts. We check that these don't change the number
1518 // (and size) of elements and just changes their types.
1519 while (V.getOpcode() == ISD::BITCAST)
1520 V = V->getOperand(0);
1522 // A splat should always show up as a build vector node.
1523 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1524 BitVector UndefElements;
1525 SDValue Splat = BV->getSplatValue(&UndefElements);
1526 // If this is a splat of an undef, shuffling it is also undef.
1527 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1528 return getUNDEF(VT);
1530 // We only have a splat which can skip shuffles if there is a splatted
1531 // value and no undef lanes rearranged by the shuffle.
1532 if (Splat && UndefElements.none()) {
1533 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1534 // number of elements match or the value splatted is a zero constant.
1535 if (V.getValueType().getVectorNumElements() ==
1536 VT.getVectorNumElements())
1538 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1539 if (C->isNullValue())
1545 FoldingSetNodeID ID;
1546 SDValue Ops[2] = { N1, N2 };
1547 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1548 for (unsigned i = 0; i != NElts; ++i)
1549 ID.AddInteger(MaskVec[i]);
1552 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1553 return SDValue(E, 0);
1555 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1556 // SDNode doesn't have access to it. This memory will be "leaked" when
1557 // the node is deallocated, but recovered when the NodeAllocator is released.
1558 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1559 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1561 ShuffleVectorSDNode *N =
1562 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1563 dl.getDebugLoc(), N1, N2,
1565 CSEMap.InsertNode(N, IP);
1566 AllNodes.push_back(N);
1567 return SDValue(N, 0);
1570 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1571 SDValue Val, SDValue DTy,
1572 SDValue STy, SDValue Rnd, SDValue Sat,
1573 ISD::CvtCode Code) {
1574 // If the src and dest types are the same and the conversion is between
1575 // integer types of the same sign or two floats, no conversion is necessary.
1577 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1580 FoldingSetNodeID ID;
1581 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1582 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1584 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1585 return SDValue(E, 0);
1587 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1590 CSEMap.InsertNode(N, IP);
1591 AllNodes.push_back(N);
1592 return SDValue(N, 0);
1595 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1596 FoldingSetNodeID ID;
1597 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1598 ID.AddInteger(RegNo);
1600 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1601 return SDValue(E, 0);
1603 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1604 CSEMap.InsertNode(N, IP);
1605 AllNodes.push_back(N);
1606 return SDValue(N, 0);
1609 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1610 FoldingSetNodeID ID;
1611 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1612 ID.AddPointer(RegMask);
1614 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1615 return SDValue(E, 0);
1617 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1618 CSEMap.InsertNode(N, IP);
1619 AllNodes.push_back(N);
1620 return SDValue(N, 0);
1623 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1624 FoldingSetNodeID ID;
1625 SDValue Ops[] = { Root };
1626 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1627 ID.AddPointer(Label);
1629 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1630 return SDValue(E, 0);
1632 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1633 dl.getDebugLoc(), Root, Label);
1634 CSEMap.InsertNode(N, IP);
1635 AllNodes.push_back(N);
1636 return SDValue(N, 0);
1640 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1643 unsigned char TargetFlags) {
1644 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1646 FoldingSetNodeID ID;
1647 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1649 ID.AddInteger(Offset);
1650 ID.AddInteger(TargetFlags);
1652 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1653 return SDValue(E, 0);
1655 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1657 CSEMap.InsertNode(N, IP);
1658 AllNodes.push_back(N);
1659 return SDValue(N, 0);
1662 SDValue SelectionDAG::getSrcValue(const Value *V) {
1663 assert((!V || V->getType()->isPointerTy()) &&
1664 "SrcValue is not a pointer?");
1666 FoldingSetNodeID ID;
1667 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1671 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1672 return SDValue(E, 0);
1674 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1675 CSEMap.InsertNode(N, IP);
1676 AllNodes.push_back(N);
1677 return SDValue(N, 0);
1680 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1681 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1682 FoldingSetNodeID ID;
1683 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1687 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1688 return SDValue(E, 0);
1690 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1691 CSEMap.InsertNode(N, IP);
1692 AllNodes.push_back(N);
1693 return SDValue(N, 0);
1696 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1697 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1698 unsigned SrcAS, unsigned DestAS) {
1699 SDValue Ops[] = {Ptr};
1700 FoldingSetNodeID ID;
1701 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1702 ID.AddInteger(SrcAS);
1703 ID.AddInteger(DestAS);
1706 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1707 return SDValue(E, 0);
1709 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1711 VT, Ptr, SrcAS, DestAS);
1712 CSEMap.InsertNode(N, IP);
1713 AllNodes.push_back(N);
1714 return SDValue(N, 0);
1717 /// getShiftAmountOperand - Return the specified value casted to
1718 /// the target's desired shift amount type.
1719 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1720 EVT OpTy = Op.getValueType();
1721 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1722 if (OpTy == ShTy || OpTy.isVector()) return Op;
1724 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1725 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1728 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1729 /// specified value type.
1730 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1731 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1732 unsigned ByteSize = VT.getStoreSize();
1733 Type *Ty = VT.getTypeForEVT(*getContext());
1734 const TargetLowering *TLI = TM.getTargetLowering();
1735 unsigned StackAlign =
1736 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1738 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1739 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1742 /// CreateStackTemporary - Create a stack temporary suitable for holding
1743 /// either of the specified value types.
1744 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1745 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1746 VT2.getStoreSizeInBits())/8;
1747 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1748 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1749 const TargetLowering *TLI = TM.getTargetLowering();
1750 const DataLayout *TD = TLI->getDataLayout();
1751 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1752 TD->getPrefTypeAlignment(Ty2));
1754 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1755 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1756 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1759 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1760 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1761 // These setcc operations always fold.
1765 case ISD::SETFALSE2: return getConstant(0, VT);
1767 case ISD::SETTRUE2: {
1768 const TargetLowering *TLI = TM.getTargetLowering();
1769 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1771 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1784 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1788 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1789 const APInt &C2 = N2C->getAPIntValue();
1790 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1791 const APInt &C1 = N1C->getAPIntValue();
1794 default: llvm_unreachable("Unknown integer setcc!");
1795 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1796 case ISD::SETNE: return getConstant(C1 != C2, VT);
1797 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1798 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1799 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1800 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1801 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1802 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1803 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1804 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1808 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1809 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1810 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1813 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1814 return getUNDEF(VT);
1816 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1817 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1818 return getUNDEF(VT);
1820 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1821 R==APFloat::cmpLessThan, VT);
1822 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1823 return getUNDEF(VT);
1825 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1826 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1827 return getUNDEF(VT);
1829 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1830 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1831 return getUNDEF(VT);
1833 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1834 R==APFloat::cmpEqual, VT);
1835 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1836 return getUNDEF(VT);
1838 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1839 R==APFloat::cmpEqual, VT);
1840 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1841 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1842 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1843 R==APFloat::cmpEqual, VT);
1844 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1845 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1846 R==APFloat::cmpLessThan, VT);
1847 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1848 R==APFloat::cmpUnordered, VT);
1849 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1850 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1853 // Ensure that the constant occurs on the RHS.
1854 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1855 MVT CompVT = N1.getValueType().getSimpleVT();
1856 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1859 return getSetCC(dl, VT, N2, N1, SwappedCond);
1863 // Could not fold it.
1867 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1868 /// use this predicate to simplify operations downstream.
1869 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1870 // This predicate is not safe for vector operations.
1871 if (Op.getValueType().isVector())
1874 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1875 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1878 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1879 /// this predicate to simplify operations downstream. Mask is known to be zero
1880 /// for bits that V cannot have.
1881 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1882 unsigned Depth) const {
1883 APInt KnownZero, KnownOne;
1884 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1885 return (KnownZero & Mask) == Mask;
1888 /// Determine which bits of Op are known to be either zero or one and return
1889 /// them in the KnownZero/KnownOne bitsets.
1890 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1891 APInt &KnownOne, unsigned Depth) const {
1892 const TargetLowering *TLI = TM.getTargetLowering();
1893 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1895 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1897 return; // Limit search depth.
1899 APInt KnownZero2, KnownOne2;
1901 switch (Op.getOpcode()) {
1903 // We know all of the bits for a constant!
1904 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1905 KnownZero = ~KnownOne;
1908 // If either the LHS or the RHS are Zero, the result is zero.
1909 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1910 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1912 // Output known-1 bits are only known if set in both the LHS & RHS.
1913 KnownOne &= KnownOne2;
1914 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1915 KnownZero |= KnownZero2;
1918 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1919 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1921 // Output known-0 bits are only known if clear in both the LHS & RHS.
1922 KnownZero &= KnownZero2;
1923 // Output known-1 are known to be set if set in either the LHS | RHS.
1924 KnownOne |= KnownOne2;
1927 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1928 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1930 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1931 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1932 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1933 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1934 KnownZero = KnownZeroOut;
1938 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1939 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1941 // If low bits are zero in either operand, output low known-0 bits.
1942 // Also compute a conserative estimate for high known-0 bits.
1943 // More trickiness is possible, but this is sufficient for the
1944 // interesting case of alignment computation.
1945 KnownOne.clearAllBits();
1946 unsigned TrailZ = KnownZero.countTrailingOnes() +
1947 KnownZero2.countTrailingOnes();
1948 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1949 KnownZero2.countLeadingOnes(),
1950 BitWidth) - BitWidth;
1952 TrailZ = std::min(TrailZ, BitWidth);
1953 LeadZ = std::min(LeadZ, BitWidth);
1954 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1955 APInt::getHighBitsSet(BitWidth, LeadZ);
1959 // For the purposes of computing leading zeros we can conservatively
1960 // treat a udiv as a logical right shift by the power of 2 known to
1961 // be less than the denominator.
1962 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1963 unsigned LeadZ = KnownZero2.countLeadingOnes();
1965 KnownOne2.clearAllBits();
1966 KnownZero2.clearAllBits();
1967 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1968 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1969 if (RHSUnknownLeadingOnes != BitWidth)
1970 LeadZ = std::min(BitWidth,
1971 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1973 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1977 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1978 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1980 // Only known if known in both the LHS and RHS.
1981 KnownOne &= KnownOne2;
1982 KnownZero &= KnownZero2;
1984 case ISD::SELECT_CC:
1985 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1986 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1988 // Only known if known in both the LHS and RHS.
1989 KnownOne &= KnownOne2;
1990 KnownZero &= KnownZero2;
1998 if (Op.getResNo() != 1)
2000 // The boolean result conforms to getBooleanContents. Fall through.
2002 // If we know the result of a setcc has the top bits zero, use this info.
2003 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2004 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
2005 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2008 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2009 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2010 unsigned ShAmt = SA->getZExtValue();
2012 // If the shift count is an invalid immediate, don't do anything.
2013 if (ShAmt >= BitWidth)
2016 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2017 KnownZero <<= ShAmt;
2019 // low bits known zero.
2020 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2024 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2025 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2026 unsigned ShAmt = SA->getZExtValue();
2028 // If the shift count is an invalid immediate, don't do anything.
2029 if (ShAmt >= BitWidth)
2032 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2033 KnownZero = KnownZero.lshr(ShAmt);
2034 KnownOne = KnownOne.lshr(ShAmt);
2036 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2037 KnownZero |= HighBits; // High bits known zero.
2041 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2042 unsigned ShAmt = SA->getZExtValue();
2044 // If the shift count is an invalid immediate, don't do anything.
2045 if (ShAmt >= BitWidth)
2048 // If any of the demanded bits are produced by the sign extension, we also
2049 // demand the input sign bit.
2050 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2052 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2053 KnownZero = KnownZero.lshr(ShAmt);
2054 KnownOne = KnownOne.lshr(ShAmt);
2056 // Handle the sign bits.
2057 APInt SignBit = APInt::getSignBit(BitWidth);
2058 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2060 if (KnownZero.intersects(SignBit)) {
2061 KnownZero |= HighBits; // New bits are known zero.
2062 } else if (KnownOne.intersects(SignBit)) {
2063 KnownOne |= HighBits; // New bits are known one.
2067 case ISD::SIGN_EXTEND_INREG: {
2068 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2069 unsigned EBits = EVT.getScalarType().getSizeInBits();
2071 // Sign extension. Compute the demanded bits in the result that are not
2072 // present in the input.
2073 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2075 APInt InSignBit = APInt::getSignBit(EBits);
2076 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2078 // If the sign extended bits are demanded, we know that the sign
2080 InSignBit = InSignBit.zext(BitWidth);
2081 if (NewBits.getBoolValue())
2082 InputDemandedBits |= InSignBit;
2084 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2085 KnownOne &= InputDemandedBits;
2086 KnownZero &= InputDemandedBits;
2088 // If the sign bit of the input is known set or clear, then we know the
2089 // top bits of the result.
2090 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2091 KnownZero |= NewBits;
2092 KnownOne &= ~NewBits;
2093 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2094 KnownOne |= NewBits;
2095 KnownZero &= ~NewBits;
2096 } else { // Input sign bit unknown
2097 KnownZero &= ~NewBits;
2098 KnownOne &= ~NewBits;
2103 case ISD::CTTZ_ZERO_UNDEF:
2105 case ISD::CTLZ_ZERO_UNDEF:
2107 unsigned LowBits = Log2_32(BitWidth)+1;
2108 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2109 KnownOne.clearAllBits();
2113 LoadSDNode *LD = cast<LoadSDNode>(Op);
2114 // If this is a ZEXTLoad and we are looking at the loaded value.
2115 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2116 EVT VT = LD->getMemoryVT();
2117 unsigned MemBits = VT.getScalarType().getSizeInBits();
2118 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2119 } else if (const MDNode *Ranges = LD->getRanges()) {
2120 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2124 case ISD::ZERO_EXTEND: {
2125 EVT InVT = Op.getOperand(0).getValueType();
2126 unsigned InBits = InVT.getScalarType().getSizeInBits();
2127 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2128 KnownZero = KnownZero.trunc(InBits);
2129 KnownOne = KnownOne.trunc(InBits);
2130 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2131 KnownZero = KnownZero.zext(BitWidth);
2132 KnownOne = KnownOne.zext(BitWidth);
2133 KnownZero |= NewBits;
2136 case ISD::SIGN_EXTEND: {
2137 EVT InVT = Op.getOperand(0).getValueType();
2138 unsigned InBits = InVT.getScalarType().getSizeInBits();
2139 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2141 KnownZero = KnownZero.trunc(InBits);
2142 KnownOne = KnownOne.trunc(InBits);
2143 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2145 // Note if the sign bit is known to be zero or one.
2146 bool SignBitKnownZero = KnownZero.isNegative();
2147 bool SignBitKnownOne = KnownOne.isNegative();
2149 KnownZero = KnownZero.zext(BitWidth);
2150 KnownOne = KnownOne.zext(BitWidth);
2152 // If the sign bit is known zero or one, the top bits match.
2153 if (SignBitKnownZero)
2154 KnownZero |= NewBits;
2155 else if (SignBitKnownOne)
2156 KnownOne |= NewBits;
2159 case ISD::ANY_EXTEND: {
2160 EVT InVT = Op.getOperand(0).getValueType();
2161 unsigned InBits = InVT.getScalarType().getSizeInBits();
2162 KnownZero = KnownZero.trunc(InBits);
2163 KnownOne = KnownOne.trunc(InBits);
2164 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2165 KnownZero = KnownZero.zext(BitWidth);
2166 KnownOne = KnownOne.zext(BitWidth);
2169 case ISD::TRUNCATE: {
2170 EVT InVT = Op.getOperand(0).getValueType();
2171 unsigned InBits = InVT.getScalarType().getSizeInBits();
2172 KnownZero = KnownZero.zext(InBits);
2173 KnownOne = KnownOne.zext(InBits);
2174 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2175 KnownZero = KnownZero.trunc(BitWidth);
2176 KnownOne = KnownOne.trunc(BitWidth);
2179 case ISD::AssertZext: {
2180 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2181 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2182 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2183 KnownZero |= (~InMask);
2184 KnownOne &= (~KnownZero);
2188 // All bits are zero except the low bit.
2189 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2193 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2194 // We know that the top bits of C-X are clear if X contains less bits
2195 // than C (i.e. no wrap-around can happen). For example, 20-X is
2196 // positive if we can prove that X is >= 0 and < 16.
2197 if (CLHS->getAPIntValue().isNonNegative()) {
2198 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2199 // NLZ can't be BitWidth with no sign bit
2200 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2201 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2203 // If all of the MaskV bits are known to be zero, then we know the
2204 // output top bits are zero, because we now know that the output is
2206 if ((KnownZero2 & MaskV) == MaskV) {
2207 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2208 // Top bits known zero.
2209 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2217 // Output known-0 bits are known if clear or set in both the low clear bits
2218 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2219 // low 3 bits clear.
2220 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2221 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2223 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2224 KnownZeroOut = std::min(KnownZeroOut,
2225 KnownZero2.countTrailingOnes());
2227 if (Op.getOpcode() == ISD::ADD) {
2228 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2232 // With ADDE, a carry bit may be added in, so we can only use this
2233 // information if we know (at least) that the low two bits are clear. We
2234 // then return to the caller that the low bit is unknown but that other bits
2236 if (KnownZeroOut >= 2) // ADDE
2237 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2241 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2242 const APInt &RA = Rem->getAPIntValue().abs();
2243 if (RA.isPowerOf2()) {
2244 APInt LowBits = RA - 1;
2245 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2247 // The low bits of the first operand are unchanged by the srem.
2248 KnownZero = KnownZero2 & LowBits;
2249 KnownOne = KnownOne2 & LowBits;
2251 // If the first operand is non-negative or has all low bits zero, then
2252 // the upper bits are all zero.
2253 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2254 KnownZero |= ~LowBits;
2256 // If the first operand is negative and not all low bits are zero, then
2257 // the upper bits are all one.
2258 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2259 KnownOne |= ~LowBits;
2260 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2265 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2266 const APInt &RA = Rem->getAPIntValue();
2267 if (RA.isPowerOf2()) {
2268 APInt LowBits = (RA - 1);
2269 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2271 // The upper bits are all zero, the lower ones are unchanged.
2272 KnownZero = KnownZero2 | ~LowBits;
2273 KnownOne = KnownOne2 & LowBits;
2278 // Since the result is less than or equal to either operand, any leading
2279 // zero bits in either operand must also exist in the result.
2280 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2281 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2283 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2284 KnownZero2.countLeadingOnes());
2285 KnownOne.clearAllBits();
2286 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2289 case ISD::FrameIndex:
2290 case ISD::TargetFrameIndex:
2291 if (unsigned Align = InferPtrAlignment(Op)) {
2292 // The low bits are known zero if the pointer is aligned.
2293 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2299 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2302 case ISD::INTRINSIC_WO_CHAIN:
2303 case ISD::INTRINSIC_W_CHAIN:
2304 case ISD::INTRINSIC_VOID:
2305 // Allow the target to implement this method for its nodes.
2306 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2310 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2313 /// ComputeNumSignBits - Return the number of times the sign bit of the
2314 /// register is replicated into the other bits. We know that at least 1 bit
2315 /// is always equal to the sign bit (itself), but other cases can give us
2316 /// information. For example, immediately after an "SRA X, 2", we know that
2317 /// the top 3 bits are all equal to each other, so we return 3.
2318 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2319 const TargetLowering *TLI = TM.getTargetLowering();
2320 EVT VT = Op.getValueType();
2321 assert(VT.isInteger() && "Invalid VT!");
2322 unsigned VTBits = VT.getScalarType().getSizeInBits();
2324 unsigned FirstAnswer = 1;
2327 return 1; // Limit search depth.
2329 switch (Op.getOpcode()) {
2331 case ISD::AssertSext:
2332 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2333 return VTBits-Tmp+1;
2334 case ISD::AssertZext:
2335 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2338 case ISD::Constant: {
2339 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2340 return Val.getNumSignBits();
2343 case ISD::SIGN_EXTEND:
2345 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2346 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2348 case ISD::SIGN_EXTEND_INREG:
2349 // Max of the input and what this extends.
2351 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2354 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2355 return std::max(Tmp, Tmp2);
2358 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2359 // SRA X, C -> adds C sign bits.
2360 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2361 Tmp += C->getZExtValue();
2362 if (Tmp > VTBits) Tmp = VTBits;
2366 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2367 // shl destroys sign bits.
2368 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2369 if (C->getZExtValue() >= VTBits || // Bad shift.
2370 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2371 return Tmp - C->getZExtValue();
2376 case ISD::XOR: // NOT is handled here.
2377 // Logical binary ops preserve the number of sign bits at the worst.
2378 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2380 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2381 FirstAnswer = std::min(Tmp, Tmp2);
2382 // We computed what we know about the sign bits as our first
2383 // answer. Now proceed to the generic code that uses
2384 // computeKnownBits, and pick whichever answer is better.
2389 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2390 if (Tmp == 1) return 1; // Early out.
2391 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2392 return std::min(Tmp, Tmp2);
2400 if (Op.getResNo() != 1)
2402 // The boolean result conforms to getBooleanContents. Fall through.
2404 // If setcc returns 0/-1, all bits are sign bits.
2405 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2406 TargetLowering::ZeroOrNegativeOneBooleanContent)
2411 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2412 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2414 // Handle rotate right by N like a rotate left by 32-N.
2415 if (Op.getOpcode() == ISD::ROTR)
2416 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2418 // If we aren't rotating out all of the known-in sign bits, return the
2419 // number that are left. This handles rotl(sext(x), 1) for example.
2420 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2421 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2425 // Add can have at most one carry bit. Thus we know that the output
2426 // is, at worst, one more bit than the inputs.
2427 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2428 if (Tmp == 1) return 1; // Early out.
2430 // Special case decrementing a value (ADD X, -1):
2431 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2432 if (CRHS->isAllOnesValue()) {
2433 APInt KnownZero, KnownOne;
2434 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2436 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2438 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2441 // If we are subtracting one from a positive number, there is no carry
2442 // out of the result.
2443 if (KnownZero.isNegative())
2447 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2448 if (Tmp2 == 1) return 1;
2449 return std::min(Tmp, Tmp2)-1;
2452 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2453 if (Tmp2 == 1) return 1;
2456 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2457 if (CLHS->isNullValue()) {
2458 APInt KnownZero, KnownOne;
2459 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2460 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2462 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2465 // If the input is known to be positive (the sign bit is known clear),
2466 // the output of the NEG has the same number of sign bits as the input.
2467 if (KnownZero.isNegative())
2470 // Otherwise, we treat this like a SUB.
2473 // Sub can have at most one carry bit. Thus we know that the output
2474 // is, at worst, one more bit than the inputs.
2475 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2476 if (Tmp == 1) return 1; // Early out.
2477 return std::min(Tmp, Tmp2)-1;
2479 // FIXME: it's tricky to do anything useful for this, but it is an important
2480 // case for targets like X86.
2484 // If we are looking at the loaded value of the SDNode.
2485 if (Op.getResNo() == 0) {
2486 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2487 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2488 unsigned ExtType = LD->getExtensionType();
2491 case ISD::SEXTLOAD: // '17' bits known
2492 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2493 return VTBits-Tmp+1;
2494 case ISD::ZEXTLOAD: // '16' bits known
2495 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2501 // Allow the target to implement this method for its nodes.
2502 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2503 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2504 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2505 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2506 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2507 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2510 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2511 // use this information.
2512 APInt KnownZero, KnownOne;
2513 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2516 if (KnownZero.isNegative()) { // sign bit is 0
2518 } else if (KnownOne.isNegative()) { // sign bit is 1;
2525 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2526 // the number of identical bits in the top of the input value.
2528 Mask <<= Mask.getBitWidth()-VTBits;
2529 // Return # leading zeros. We use 'min' here in case Val was zero before
2530 // shifting. We don't want to return '64' as for an i32 "0".
2531 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2534 /// isBaseWithConstantOffset - Return true if the specified operand is an
2535 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2536 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2537 /// semantics as an ADD. This handles the equivalence:
2538 /// X|Cst == X+Cst iff X&Cst = 0.
2539 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2540 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2541 !isa<ConstantSDNode>(Op.getOperand(1)))
2544 if (Op.getOpcode() == ISD::OR &&
2545 !MaskedValueIsZero(Op.getOperand(0),
2546 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2553 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2554 // If we're told that NaNs won't happen, assume they won't.
2555 if (getTarget().Options.NoNaNsFPMath)
2558 // If the value is a constant, we can obviously see if it is a NaN or not.
2559 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2560 return !C->getValueAPF().isNaN();
2562 // TODO: Recognize more cases here.
2567 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2568 // If the value is a constant, we can obviously see if it is a zero or not.
2569 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2570 return !C->isZero();
2572 // TODO: Recognize more cases here.
2573 switch (Op.getOpcode()) {
2576 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2577 return !C->isNullValue();
2584 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2585 // Check the obvious case.
2586 if (A == B) return true;
2588 // For for negative and positive zero.
2589 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2590 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2591 if (CA->isZero() && CB->isZero()) return true;
2593 // Otherwise they may not be equal.
2597 /// getNode - Gets or creates the specified node.
2599 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2600 FoldingSetNodeID ID;
2601 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2603 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2604 return SDValue(E, 0);
2606 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2607 DL.getDebugLoc(), getVTList(VT));
2608 CSEMap.InsertNode(N, IP);
2610 AllNodes.push_back(N);
2614 return SDValue(N, 0);
2617 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2618 EVT VT, SDValue Operand) {
2619 // Constant fold unary operations with an integer constant operand. Even
2620 // opaque constant will be folded, because the folding of unary operations
2621 // doesn't create new constants with different values. Nevertheless, the
2622 // opaque flag is preserved during folding to prevent future folding with
2624 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2625 const APInt &Val = C->getAPIntValue();
2628 case ISD::SIGN_EXTEND:
2629 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2630 C->isTargetOpcode(), C->isOpaque());
2631 case ISD::ANY_EXTEND:
2632 case ISD::ZERO_EXTEND:
2634 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2635 C->isTargetOpcode(), C->isOpaque());
2636 case ISD::UINT_TO_FP:
2637 case ISD::SINT_TO_FP: {
2638 APFloat apf(EVTToAPFloatSemantics(VT),
2639 APInt::getNullValue(VT.getSizeInBits()));
2640 (void)apf.convertFromAPInt(Val,
2641 Opcode==ISD::SINT_TO_FP,
2642 APFloat::rmNearestTiesToEven);
2643 return getConstantFP(apf, VT);
2646 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2647 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2648 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2649 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2652 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2655 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2658 case ISD::CTLZ_ZERO_UNDEF:
2659 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2662 case ISD::CTTZ_ZERO_UNDEF:
2663 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2668 // Constant fold unary operations with a floating point constant operand.
2669 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2670 APFloat V = C->getValueAPF(); // make copy
2674 return getConstantFP(V, VT);
2677 return getConstantFP(V, VT);
2679 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2680 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2681 return getConstantFP(V, VT);
2685 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2686 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2687 return getConstantFP(V, VT);
2691 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2692 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2693 return getConstantFP(V, VT);
2696 case ISD::FP_EXTEND: {
2698 // This can return overflow, underflow, or inexact; we don't care.
2699 // FIXME need to be more flexible about rounding mode.
2700 (void)V.convert(EVTToAPFloatSemantics(VT),
2701 APFloat::rmNearestTiesToEven, &ignored);
2702 return getConstantFP(V, VT);
2704 case ISD::FP_TO_SINT:
2705 case ISD::FP_TO_UINT: {
2708 assert(integerPartWidth >= 64);
2709 // FIXME need to be more flexible about rounding mode.
2710 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2711 Opcode==ISD::FP_TO_SINT,
2712 APFloat::rmTowardZero, &ignored);
2713 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2715 APInt api(VT.getSizeInBits(), x);
2716 return getConstant(api, VT);
2719 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2720 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2721 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2722 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2727 unsigned OpOpcode = Operand.getNode()->getOpcode();
2729 case ISD::TokenFactor:
2730 case ISD::MERGE_VALUES:
2731 case ISD::CONCAT_VECTORS:
2732 return Operand; // Factor, merge or concat of one node? No need.
2733 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2734 case ISD::FP_EXTEND:
2735 assert(VT.isFloatingPoint() &&
2736 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2737 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2738 assert((!VT.isVector() ||
2739 VT.getVectorNumElements() ==
2740 Operand.getValueType().getVectorNumElements()) &&
2741 "Vector element count mismatch!");
2742 if (Operand.getOpcode() == ISD::UNDEF)
2743 return getUNDEF(VT);
2745 case ISD::SIGN_EXTEND:
2746 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2747 "Invalid SIGN_EXTEND!");
2748 if (Operand.getValueType() == VT) return Operand; // noop extension
2749 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2750 "Invalid sext node, dst < src!");
2751 assert((!VT.isVector() ||
2752 VT.getVectorNumElements() ==
2753 Operand.getValueType().getVectorNumElements()) &&
2754 "Vector element count mismatch!");
2755 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2756 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2757 else if (OpOpcode == ISD::UNDEF)
2758 // sext(undef) = 0, because the top bits will all be the same.
2759 return getConstant(0, VT);
2761 case ISD::ZERO_EXTEND:
2762 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2763 "Invalid ZERO_EXTEND!");
2764 if (Operand.getValueType() == VT) return Operand; // noop extension
2765 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2766 "Invalid zext node, dst < src!");
2767 assert((!VT.isVector() ||
2768 VT.getVectorNumElements() ==
2769 Operand.getValueType().getVectorNumElements()) &&
2770 "Vector element count mismatch!");
2771 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2772 return getNode(ISD::ZERO_EXTEND, DL, VT,
2773 Operand.getNode()->getOperand(0));
2774 else if (OpOpcode == ISD::UNDEF)
2775 // zext(undef) = 0, because the top bits will be zero.
2776 return getConstant(0, VT);
2778 case ISD::ANY_EXTEND:
2779 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2780 "Invalid ANY_EXTEND!");
2781 if (Operand.getValueType() == VT) return Operand; // noop extension
2782 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2783 "Invalid anyext node, dst < src!");
2784 assert((!VT.isVector() ||
2785 VT.getVectorNumElements() ==
2786 Operand.getValueType().getVectorNumElements()) &&
2787 "Vector element count mismatch!");
2789 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2790 OpOpcode == ISD::ANY_EXTEND)
2791 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2792 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2793 else if (OpOpcode == ISD::UNDEF)
2794 return getUNDEF(VT);
2796 // (ext (trunx x)) -> x
2797 if (OpOpcode == ISD::TRUNCATE) {
2798 SDValue OpOp = Operand.getNode()->getOperand(0);
2799 if (OpOp.getValueType() == VT)
2804 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2805 "Invalid TRUNCATE!");
2806 if (Operand.getValueType() == VT) return Operand; // noop truncate
2807 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2808 "Invalid truncate node, src < dst!");
2809 assert((!VT.isVector() ||
2810 VT.getVectorNumElements() ==
2811 Operand.getValueType().getVectorNumElements()) &&
2812 "Vector element count mismatch!");
2813 if (OpOpcode == ISD::TRUNCATE)
2814 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2815 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2816 OpOpcode == ISD::ANY_EXTEND) {
2817 // If the source is smaller than the dest, we still need an extend.
2818 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2819 .bitsLT(VT.getScalarType()))
2820 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2821 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2822 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2823 return Operand.getNode()->getOperand(0);
2825 if (OpOpcode == ISD::UNDEF)
2826 return getUNDEF(VT);
2829 // Basic sanity checking.
2830 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2831 && "Cannot BITCAST between types of different sizes!");
2832 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2833 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2834 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2835 if (OpOpcode == ISD::UNDEF)
2836 return getUNDEF(VT);
2838 case ISD::SCALAR_TO_VECTOR:
2839 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2840 (VT.getVectorElementType() == Operand.getValueType() ||
2841 (VT.getVectorElementType().isInteger() &&
2842 Operand.getValueType().isInteger() &&
2843 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2844 "Illegal SCALAR_TO_VECTOR node!");
2845 if (OpOpcode == ISD::UNDEF)
2846 return getUNDEF(VT);
2847 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2848 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2849 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2850 Operand.getConstantOperandVal(1) == 0 &&
2851 Operand.getOperand(0).getValueType() == VT)
2852 return Operand.getOperand(0);
2855 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2856 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2857 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2858 Operand.getNode()->getOperand(0));
2859 if (OpOpcode == ISD::FNEG) // --X -> X
2860 return Operand.getNode()->getOperand(0);
2863 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2864 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2869 SDVTList VTs = getVTList(VT);
2870 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2871 FoldingSetNodeID ID;
2872 SDValue Ops[1] = { Operand };
2873 AddNodeIDNode(ID, Opcode, VTs, Ops);
2875 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2876 return SDValue(E, 0);
2878 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2879 DL.getDebugLoc(), VTs, Operand);
2880 CSEMap.InsertNode(N, IP);
2882 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2883 DL.getDebugLoc(), VTs, Operand);
2886 AllNodes.push_back(N);
2890 return SDValue(N, 0);
2893 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2894 SDNode *Cst1, SDNode *Cst2) {
2895 // If the opcode is a target-specific ISD node, there's nothing we can
2896 // do here and the operand rules may not line up with the below, so
2898 if (Opcode >= ISD::BUILTIN_OP_END)
2901 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2902 SmallVector<SDValue, 4> Outputs;
2903 EVT SVT = VT.getScalarType();
2905 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2906 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2907 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2910 if (Scalar1 && Scalar2)
2911 // Scalar instruction.
2912 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2914 // For vectors extract each constant element into Inputs so we can constant
2915 // fold them individually.
2916 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2917 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2921 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2923 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2924 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2925 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2926 if (!V1 || !V2) // Not a constant, bail.
2929 if (V1->isOpaque() || V2->isOpaque())
2932 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2933 // FIXME: This is valid and could be handled by truncating the APInts.
2934 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2937 Inputs.push_back(std::make_pair(V1, V2));
2941 // We have a number of constant values, constant fold them element by element.
2942 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2943 const APInt &C1 = Inputs[I].first->getAPIntValue();
2944 const APInt &C2 = Inputs[I].second->getAPIntValue();
2948 Outputs.push_back(getConstant(C1 + C2, SVT));
2951 Outputs.push_back(getConstant(C1 - C2, SVT));
2954 Outputs.push_back(getConstant(C1 * C2, SVT));
2957 if (!C2.getBoolValue())
2959 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2962 if (!C2.getBoolValue())
2964 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2967 if (!C2.getBoolValue())
2969 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2972 if (!C2.getBoolValue())
2974 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2977 Outputs.push_back(getConstant(C1 & C2, SVT));
2980 Outputs.push_back(getConstant(C1 | C2, SVT));
2983 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2986 Outputs.push_back(getConstant(C1 << C2, SVT));
2989 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2992 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2995 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2998 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3005 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3006 "Expected a scalar or vector!"));
3008 // Handle the scalar case first.
3010 return Outputs.back();
3012 // We may have a vector type but a scalar result. Create a splat.
3013 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3015 // Build a big vector out of the scalar elements we generated.
3016 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3019 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3020 SDValue N2, bool nuw, bool nsw, bool exact) {
3021 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3022 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3025 case ISD::TokenFactor:
3026 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3027 N2.getValueType() == MVT::Other && "Invalid token factor!");
3028 // Fold trivial token factors.
3029 if (N1.getOpcode() == ISD::EntryToken) return N2;
3030 if (N2.getOpcode() == ISD::EntryToken) return N1;
3031 if (N1 == N2) return N1;
3033 case ISD::CONCAT_VECTORS:
3034 // Concat of UNDEFs is UNDEF.
3035 if (N1.getOpcode() == ISD::UNDEF &&
3036 N2.getOpcode() == ISD::UNDEF)
3037 return getUNDEF(VT);
3039 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3040 // one big BUILD_VECTOR.
3041 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3042 N2.getOpcode() == ISD::BUILD_VECTOR) {
3043 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3044 N1.getNode()->op_end());
3045 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3046 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3050 assert(VT.isInteger() && "This operator does not apply to FP types!");
3051 assert(N1.getValueType() == N2.getValueType() &&
3052 N1.getValueType() == VT && "Binary operator types must match!");
3053 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3054 // worth handling here.
3055 if (N2C && N2C->isNullValue())
3057 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3064 assert(VT.isInteger() && "This operator does not apply to FP types!");
3065 assert(N1.getValueType() == N2.getValueType() &&
3066 N1.getValueType() == VT && "Binary operator types must match!");
3067 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3068 // it's worth handling here.
3069 if (N2C && N2C->isNullValue())
3079 assert(VT.isInteger() && "This operator does not apply to FP types!");
3080 assert(N1.getValueType() == N2.getValueType() &&
3081 N1.getValueType() == VT && "Binary operator types must match!");
3088 if (getTarget().Options.UnsafeFPMath) {
3089 if (Opcode == ISD::FADD) {
3091 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3092 if (CFP->getValueAPF().isZero())
3095 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3096 if (CFP->getValueAPF().isZero())
3098 } else if (Opcode == ISD::FSUB) {
3100 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3101 if (CFP->getValueAPF().isZero())
3103 } else if (Opcode == ISD::FMUL) {
3104 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3107 // If the first operand isn't the constant, try the second
3109 CFP = dyn_cast<ConstantFPSDNode>(N2);
3116 return SDValue(CFP,0);
3118 if (CFP->isExactlyValue(1.0))
3123 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3124 assert(N1.getValueType() == N2.getValueType() &&
3125 N1.getValueType() == VT && "Binary operator types must match!");
3127 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3128 assert(N1.getValueType() == VT &&
3129 N1.getValueType().isFloatingPoint() &&
3130 N2.getValueType().isFloatingPoint() &&
3131 "Invalid FCOPYSIGN!");
3138 assert(VT == N1.getValueType() &&
3139 "Shift operators return type must be the same as their first arg");
3140 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3141 "Shifts only work on integers");
3142 assert((!VT.isVector() || VT == N2.getValueType()) &&
3143 "Vector shift amounts must be in the same as their first arg");
3144 // Verify that the shift amount VT is bit enough to hold valid shift
3145 // amounts. This catches things like trying to shift an i1024 value by an
3146 // i8, which is easy to fall into in generic code that uses
3147 // TLI.getShiftAmount().
3148 assert(N2.getValueType().getSizeInBits() >=
3149 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3150 "Invalid use of small shift amount with oversized value!");
3152 // Always fold shifts of i1 values so the code generator doesn't need to
3153 // handle them. Since we know the size of the shift has to be less than the
3154 // size of the value, the shift/rotate count is guaranteed to be zero.
3157 if (N2C && N2C->isNullValue())
3160 case ISD::FP_ROUND_INREG: {
3161 EVT EVT = cast<VTSDNode>(N2)->getVT();
3162 assert(VT == N1.getValueType() && "Not an inreg round!");
3163 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3164 "Cannot FP_ROUND_INREG integer types");
3165 assert(EVT.isVector() == VT.isVector() &&
3166 "FP_ROUND_INREG type should be vector iff the operand "
3168 assert((!EVT.isVector() ||
3169 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3170 "Vector element counts must match in FP_ROUND_INREG");
3171 assert(EVT.bitsLE(VT) && "Not rounding down!");
3173 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3177 assert(VT.isFloatingPoint() &&
3178 N1.getValueType().isFloatingPoint() &&
3179 VT.bitsLE(N1.getValueType()) &&
3180 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3181 if (N1.getValueType() == VT) return N1; // noop conversion.
3183 case ISD::AssertSext:
3184 case ISD::AssertZext: {
3185 EVT EVT = cast<VTSDNode>(N2)->getVT();
3186 assert(VT == N1.getValueType() && "Not an inreg extend!");
3187 assert(VT.isInteger() && EVT.isInteger() &&
3188 "Cannot *_EXTEND_INREG FP types");
3189 assert(!EVT.isVector() &&
3190 "AssertSExt/AssertZExt type should be the vector element type "
3191 "rather than the vector type!");
3192 assert(EVT.bitsLE(VT) && "Not extending!");
3193 if (VT == EVT) return N1; // noop assertion.
3196 case ISD::SIGN_EXTEND_INREG: {
3197 EVT EVT = cast<VTSDNode>(N2)->getVT();
3198 assert(VT == N1.getValueType() && "Not an inreg extend!");
3199 assert(VT.isInteger() && EVT.isInteger() &&
3200 "Cannot *_EXTEND_INREG FP types");
3201 assert(EVT.isVector() == VT.isVector() &&
3202 "SIGN_EXTEND_INREG type should be vector iff the operand "
3204 assert((!EVT.isVector() ||
3205 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3206 "Vector element counts must match in SIGN_EXTEND_INREG");
3207 assert(EVT.bitsLE(VT) && "Not extending!");
3208 if (EVT == VT) return N1; // Not actually extending
3211 APInt Val = N1C->getAPIntValue();
3212 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3213 Val <<= Val.getBitWidth()-FromBits;
3214 Val = Val.ashr(Val.getBitWidth()-FromBits);
3215 return getConstant(Val, VT);
3219 case ISD::EXTRACT_VECTOR_ELT:
3220 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3221 if (N1.getOpcode() == ISD::UNDEF)
3222 return getUNDEF(VT);
3224 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3225 // expanding copies of large vectors from registers.
3227 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3228 N1.getNumOperands() > 0) {
3230 N1.getOperand(0).getValueType().getVectorNumElements();
3231 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3232 N1.getOperand(N2C->getZExtValue() / Factor),
3233 getConstant(N2C->getZExtValue() % Factor,
3234 N2.getValueType()));
3237 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3238 // expanding large vector constants.
3239 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3240 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3242 if (VT != Elt.getValueType())
3243 // If the vector element type is not legal, the BUILD_VECTOR operands
3244 // are promoted and implicitly truncated, and the result implicitly
3245 // extended. Make that explicit here.
3246 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3251 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3252 // operations are lowered to scalars.
3253 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3254 // If the indices are the same, return the inserted element else
3255 // if the indices are known different, extract the element from
3256 // the original vector.
3257 SDValue N1Op2 = N1.getOperand(2);
3258 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3260 if (N1Op2C && N2C) {
3261 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3262 if (VT == N1.getOperand(1).getValueType())
3263 return N1.getOperand(1);
3265 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3268 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3272 case ISD::EXTRACT_ELEMENT:
3273 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3274 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3275 (N1.getValueType().isInteger() == VT.isInteger()) &&
3276 N1.getValueType() != VT &&
3277 "Wrong types for EXTRACT_ELEMENT!");
3279 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3280 // 64-bit integers into 32-bit parts. Instead of building the extract of
3281 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3282 if (N1.getOpcode() == ISD::BUILD_PAIR)
3283 return N1.getOperand(N2C->getZExtValue());
3285 // EXTRACT_ELEMENT of a constant int is also very common.
3286 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3287 unsigned ElementSize = VT.getSizeInBits();
3288 unsigned Shift = ElementSize * N2C->getZExtValue();
3289 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3290 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3293 case ISD::EXTRACT_SUBVECTOR: {
3295 if (VT.isSimple() && N1.getValueType().isSimple()) {
3296 assert(VT.isVector() && N1.getValueType().isVector() &&
3297 "Extract subvector VTs must be a vectors!");
3298 assert(VT.getVectorElementType() ==
3299 N1.getValueType().getVectorElementType() &&
3300 "Extract subvector VTs must have the same element type!");
3301 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3302 "Extract subvector must be from larger vector to smaller vector!");
3304 if (isa<ConstantSDNode>(Index.getNode())) {
3305 assert((VT.getVectorNumElements() +
3306 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3307 <= N1.getValueType().getVectorNumElements())
3308 && "Extract subvector overflow!");
3311 // Trivial extraction.
3312 if (VT.getSimpleVT() == N1.getSimpleValueType())
3319 // Perform trivial constant folding.
3320 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3321 if (SV.getNode()) return SV;
3323 // Canonicalize constant to RHS if commutative.
3324 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3325 std::swap(N1C, N2C);
3329 // Constant fold FP operations.
3330 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3331 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3333 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3334 // Canonicalize constant to RHS if commutative.
3335 std::swap(N1CFP, N2CFP);
3338 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3339 APFloat::opStatus s;
3342 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3343 if (s != APFloat::opInvalidOp)
3344 return getConstantFP(V1, VT);
3347 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3348 if (s!=APFloat::opInvalidOp)
3349 return getConstantFP(V1, VT);
3352 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3353 if (s!=APFloat::opInvalidOp)
3354 return getConstantFP(V1, VT);
3357 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3358 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3359 return getConstantFP(V1, VT);
3362 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3363 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3364 return getConstantFP(V1, VT);
3366 case ISD::FCOPYSIGN:
3368 return getConstantFP(V1, VT);
3373 if (Opcode == ISD::FP_ROUND) {
3374 APFloat V = N1CFP->getValueAPF(); // make copy
3376 // This can return overflow, underflow, or inexact; we don't care.
3377 // FIXME need to be more flexible about rounding mode.
3378 (void)V.convert(EVTToAPFloatSemantics(VT),
3379 APFloat::rmNearestTiesToEven, &ignored);
3380 return getConstantFP(V, VT);
3384 // Canonicalize an UNDEF to the RHS, even over a constant.
3385 if (N1.getOpcode() == ISD::UNDEF) {
3386 if (isCommutativeBinOp(Opcode)) {
3390 case ISD::FP_ROUND_INREG:
3391 case ISD::SIGN_EXTEND_INREG:
3397 return N1; // fold op(undef, arg2) -> undef
3405 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3406 // For vectors, we can't easily build an all zero vector, just return
3413 // Fold a bunch of operators when the RHS is undef.
3414 if (N2.getOpcode() == ISD::UNDEF) {
3417 if (N1.getOpcode() == ISD::UNDEF)
3418 // Handle undef ^ undef -> 0 special case. This is a common
3420 return getConstant(0, VT);
3430 return N2; // fold op(arg1, undef) -> undef
3436 if (getTarget().Options.UnsafeFPMath)
3444 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3445 // For vectors, we can't easily build an all zero vector, just return
3450 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3451 // For vectors, we can't easily build an all one vector, just return
3459 // Memoize this node if possible.
3461 SDVTList VTs = getVTList(VT);
3462 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3463 if (VT != MVT::Glue) {
3464 SDValue Ops[] = {N1, N2};
3465 FoldingSetNodeID ID;
3466 AddNodeIDNode(ID, Opcode, VTs, Ops);
3468 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3470 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3471 return SDValue(E, 0);
3473 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3475 CSEMap.InsertNode(N, IP);
3478 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3481 AllNodes.push_back(N);
3485 return SDValue(N, 0);
3488 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3489 SDValue N1, SDValue N2, SDValue N3) {
3490 // Perform various simplifications.
3491 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3494 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3495 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3496 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3497 if (N1CFP && N2CFP && N3CFP) {
3498 APFloat V1 = N1CFP->getValueAPF();
3499 const APFloat &V2 = N2CFP->getValueAPF();
3500 const APFloat &V3 = N3CFP->getValueAPF();
3501 APFloat::opStatus s =
3502 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3503 if (s != APFloat::opInvalidOp)
3504 return getConstantFP(V1, VT);
3508 case ISD::CONCAT_VECTORS:
3509 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3510 // one big BUILD_VECTOR.
3511 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3512 N2.getOpcode() == ISD::BUILD_VECTOR &&
3513 N3.getOpcode() == ISD::BUILD_VECTOR) {
3514 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3515 N1.getNode()->op_end());
3516 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3517 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3518 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3522 // Use FoldSetCC to simplify SETCC's.
3523 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3524 if (Simp.getNode()) return Simp;
3529 if (N1C->getZExtValue())
3530 return N2; // select true, X, Y -> X
3531 return N3; // select false, X, Y -> Y
3534 if (N2 == N3) return N2; // select C, X, X -> X
3536 case ISD::VECTOR_SHUFFLE:
3537 llvm_unreachable("should use getVectorShuffle constructor!");
3538 case ISD::INSERT_SUBVECTOR: {
3540 if (VT.isSimple() && N1.getValueType().isSimple()
3541 && N2.getValueType().isSimple()) {
3542 assert(VT.isVector() && N1.getValueType().isVector() &&
3543 N2.getValueType().isVector() &&
3544 "Insert subvector VTs must be a vectors");
3545 assert(VT == N1.getValueType() &&
3546 "Dest and insert subvector source types must match!");
3547 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3548 "Insert subvector must be from smaller vector to larger vector!");
3549 if (isa<ConstantSDNode>(Index.getNode())) {
3550 assert((N2.getValueType().getVectorNumElements() +
3551 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3552 <= VT.getVectorNumElements())
3553 && "Insert subvector overflow!");
3556 // Trivial insertion.
3557 if (VT.getSimpleVT() == N2.getSimpleValueType())
3563 // Fold bit_convert nodes from a type to themselves.
3564 if (N1.getValueType() == VT)
3569 // Memoize node if it doesn't produce a flag.
3571 SDVTList VTs = getVTList(VT);
3572 if (VT != MVT::Glue) {
3573 SDValue Ops[] = { N1, N2, N3 };
3574 FoldingSetNodeID ID;
3575 AddNodeIDNode(ID, Opcode, VTs, Ops);
3577 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3578 return SDValue(E, 0);
3580 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3581 DL.getDebugLoc(), VTs, N1, N2, N3);
3582 CSEMap.InsertNode(N, IP);
3584 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3585 DL.getDebugLoc(), VTs, N1, N2, N3);
3588 AllNodes.push_back(N);
3592 return SDValue(N, 0);
3595 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3596 SDValue N1, SDValue N2, SDValue N3,
3598 SDValue Ops[] = { N1, N2, N3, N4 };
3599 return getNode(Opcode, DL, VT, Ops);
3602 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3603 SDValue N1, SDValue N2, SDValue N3,
3604 SDValue N4, SDValue N5) {
3605 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3606 return getNode(Opcode, DL, VT, Ops);
3609 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3610 /// the incoming stack arguments to be loaded from the stack.
3611 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3612 SmallVector<SDValue, 8> ArgChains;
3614 // Include the original chain at the beginning of the list. When this is
3615 // used by target LowerCall hooks, this helps legalize find the
3616 // CALLSEQ_BEGIN node.
3617 ArgChains.push_back(Chain);
3619 // Add a chain value for each stack argument.
3620 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3621 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3622 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3623 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3624 if (FI->getIndex() < 0)
3625 ArgChains.push_back(SDValue(L, 1));
3627 // Build a tokenfactor for all the chains.
3628 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3631 /// getMemsetValue - Vectorized representation of the memset value
3633 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3635 assert(Value.getOpcode() != ISD::UNDEF);
3637 unsigned NumBits = VT.getScalarType().getSizeInBits();
3638 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3639 assert(C->getAPIntValue().getBitWidth() == 8);
3640 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3642 return DAG.getConstant(Val, VT);
3643 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3646 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3648 // Use a multiplication with 0x010101... to extend the input to the
3650 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3651 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3657 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3658 /// used when a memcpy is turned into a memset when the source is a constant
3660 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3661 const TargetLowering &TLI, StringRef Str) {
3662 // Handle vector with all elements zero.
3665 return DAG.getConstant(0, VT);
3666 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3667 return DAG.getConstantFP(0.0, VT);
3668 else if (VT.isVector()) {
3669 unsigned NumElts = VT.getVectorNumElements();
3670 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3671 return DAG.getNode(ISD::BITCAST, dl, VT,
3672 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3675 llvm_unreachable("Expected type!");
3678 assert(!VT.isVector() && "Can't handle vector type here!");
3679 unsigned NumVTBits = VT.getSizeInBits();
3680 unsigned NumVTBytes = NumVTBits / 8;
3681 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3683 APInt Val(NumVTBits, 0);
3684 if (TLI.isLittleEndian()) {
3685 for (unsigned i = 0; i != NumBytes; ++i)
3686 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3688 for (unsigned i = 0; i != NumBytes; ++i)
3689 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3692 // If the "cost" of materializing the integer immediate is less than the cost
3693 // of a load, then it is cost effective to turn the load into the immediate.
3694 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3695 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3696 return DAG.getConstant(Val, VT);
3697 return SDValue(nullptr, 0);
3700 /// getMemBasePlusOffset - Returns base and offset node for the
3702 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3703 SelectionDAG &DAG) {
3704 EVT VT = Base.getValueType();
3705 return DAG.getNode(ISD::ADD, dl,
3706 VT, Base, DAG.getConstant(Offset, VT));
3709 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3711 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3712 unsigned SrcDelta = 0;
3713 GlobalAddressSDNode *G = nullptr;
3714 if (Src.getOpcode() == ISD::GlobalAddress)
3715 G = cast<GlobalAddressSDNode>(Src);
3716 else if (Src.getOpcode() == ISD::ADD &&
3717 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3718 Src.getOperand(1).getOpcode() == ISD::Constant) {
3719 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3720 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3725 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3728 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3729 /// to replace the memset / memcpy. Return true if the number of memory ops
3730 /// is below the threshold. It returns the types of the sequence of
3731 /// memory ops to perform memset / memcpy by reference.
3732 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3733 unsigned Limit, uint64_t Size,
3734 unsigned DstAlign, unsigned SrcAlign,
3740 const TargetLowering &TLI) {
3741 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3742 "Expecting memcpy / memset source to meet alignment requirement!");
3743 // If 'SrcAlign' is zero, that means the memory operation does not need to
3744 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3745 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3746 // is the specified alignment of the memory operation. If it is zero, that
3747 // means it's possible to change the alignment of the destination.
3748 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3749 // not need to be loaded.
3750 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3751 IsMemset, ZeroMemset, MemcpyStrSrc,
3752 DAG.getMachineFunction());
3754 if (VT == MVT::Other) {
3756 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3757 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3758 VT = TLI.getPointerTy();
3760 switch (DstAlign & 7) {
3761 case 0: VT = MVT::i64; break;
3762 case 4: VT = MVT::i32; break;
3763 case 2: VT = MVT::i16; break;
3764 default: VT = MVT::i8; break;
3769 while (!TLI.isTypeLegal(LVT))
3770 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3771 assert(LVT.isInteger());
3777 unsigned NumMemOps = 0;
3779 unsigned VTSize = VT.getSizeInBits() / 8;
3780 while (VTSize > Size) {
3781 // For now, only use non-vector load / store's for the left-over pieces.
3786 if (VT.isVector() || VT.isFloatingPoint()) {
3787 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3788 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3789 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3791 else if (NewVT == MVT::i64 &&
3792 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3793 TLI.isSafeMemOpType(MVT::f64)) {
3794 // i64 is usually not legal on 32-bit targets, but f64 may be.
3802 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3803 if (NewVT == MVT::i8)
3805 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3807 NewVTSize = NewVT.getSizeInBits() / 8;
3809 // If the new VT cannot cover all of the remaining bits, then consider
3810 // issuing a (or a pair of) unaligned and overlapping load / store.
3811 // FIXME: Only does this for 64-bit or more since we don't have proper
3812 // cost model for unaligned load / store.
3815 if (NumMemOps && AllowOverlap &&
3816 VTSize >= 8 && NewVTSize < Size &&
3817 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3825 if (++NumMemOps > Limit)
3828 MemOps.push_back(VT);
3835 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3836 SDValue Chain, SDValue Dst,
3837 SDValue Src, uint64_t Size,
3838 unsigned Align, bool isVol,
3840 MachinePointerInfo DstPtrInfo,
3841 MachinePointerInfo SrcPtrInfo) {
3842 // Turn a memcpy of undef to nop.
3843 if (Src.getOpcode() == ISD::UNDEF)
3846 // Expand memcpy to a series of load and store ops if the size operand falls
3847 // below a certain threshold.
3848 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3849 // rather than maybe a humongous number of loads and stores.
3850 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3851 std::vector<EVT> MemOps;
3852 bool DstAlignCanChange = false;
3853 MachineFunction &MF = DAG.getMachineFunction();
3854 MachineFrameInfo *MFI = MF.getFrameInfo();
3856 MF.getFunction()->getAttributes().
3857 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3858 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3859 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3860 DstAlignCanChange = true;
3861 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3862 if (Align > SrcAlign)
3865 bool CopyFromStr = isMemSrcFromString(Src, Str);
3866 bool isZeroStr = CopyFromStr && Str.empty();
3867 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3869 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3870 (DstAlignCanChange ? 0 : Align),
3871 (isZeroStr ? 0 : SrcAlign),
3872 false, false, CopyFromStr, true, DAG, TLI))
3875 if (DstAlignCanChange) {
3876 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3877 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3879 // Don't promote to an alignment that would require dynamic stack
3881 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3882 if (!TRI->needsStackRealignment(MF))
3883 while (NewAlign > Align &&
3884 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3887 if (NewAlign > Align) {
3888 // Give the stack frame object a larger alignment if needed.
3889 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3890 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3895 SmallVector<SDValue, 8> OutChains;
3896 unsigned NumMemOps = MemOps.size();
3897 uint64_t SrcOff = 0, DstOff = 0;
3898 for (unsigned i = 0; i != NumMemOps; ++i) {
3900 unsigned VTSize = VT.getSizeInBits() / 8;
3901 SDValue Value, Store;
3903 if (VTSize > Size) {
3904 // Issuing an unaligned load / store pair that overlaps with the previous
3905 // pair. Adjust the offset accordingly.
3906 assert(i == NumMemOps-1 && i != 0);
3907 SrcOff -= VTSize - Size;
3908 DstOff -= VTSize - Size;
3912 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3913 // It's unlikely a store of a vector immediate can be done in a single
3914 // instruction. It would require a load from a constantpool first.
3915 // We only handle zero vectors here.
3916 // FIXME: Handle other cases where store of vector immediate is done in
3917 // a single instruction.
3918 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3919 if (Value.getNode())
3920 Store = DAG.getStore(Chain, dl, Value,
3921 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3922 DstPtrInfo.getWithOffset(DstOff), isVol,
3926 if (!Store.getNode()) {
3927 // The type might not be legal for the target. This should only happen
3928 // if the type is smaller than a legal type, as on PPC, so the right
3929 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3930 // to Load/Store if NVT==VT.
3931 // FIXME does the case above also need this?
3932 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3933 assert(NVT.bitsGE(VT));
3934 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3935 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3936 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3937 MinAlign(SrcAlign, SrcOff));
3938 Store = DAG.getTruncStore(Chain, dl, Value,
3939 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3940 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3943 OutChains.push_back(Store);
3949 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3952 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3953 SDValue Chain, SDValue Dst,
3954 SDValue Src, uint64_t Size,
3955 unsigned Align, bool isVol,
3957 MachinePointerInfo DstPtrInfo,
3958 MachinePointerInfo SrcPtrInfo) {
3959 // Turn a memmove of undef to nop.
3960 if (Src.getOpcode() == ISD::UNDEF)
3963 // Expand memmove to a series of load and store ops if the size operand falls
3964 // below a certain threshold.
3965 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3966 std::vector<EVT> MemOps;
3967 bool DstAlignCanChange = false;
3968 MachineFunction &MF = DAG.getMachineFunction();
3969 MachineFrameInfo *MFI = MF.getFrameInfo();
3970 bool OptSize = MF.getFunction()->getAttributes().
3971 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3972 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3973 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3974 DstAlignCanChange = true;
3975 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3976 if (Align > SrcAlign)
3978 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3980 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3981 (DstAlignCanChange ? 0 : Align), SrcAlign,
3982 false, false, false, false, DAG, TLI))
3985 if (DstAlignCanChange) {
3986 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3987 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3988 if (NewAlign > Align) {
3989 // Give the stack frame object a larger alignment if needed.
3990 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3991 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3996 uint64_t SrcOff = 0, DstOff = 0;
3997 SmallVector<SDValue, 8> LoadValues;
3998 SmallVector<SDValue, 8> LoadChains;
3999 SmallVector<SDValue, 8> OutChains;
4000 unsigned NumMemOps = MemOps.size();
4001 for (unsigned i = 0; i < NumMemOps; i++) {
4003 unsigned VTSize = VT.getSizeInBits() / 8;
4006 Value = DAG.getLoad(VT, dl, Chain,
4007 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4008 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4009 false, false, SrcAlign);
4010 LoadValues.push_back(Value);
4011 LoadChains.push_back(Value.getValue(1));
4014 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4016 for (unsigned i = 0; i < NumMemOps; i++) {
4018 unsigned VTSize = VT.getSizeInBits() / 8;
4021 Store = DAG.getStore(Chain, dl, LoadValues[i],
4022 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4023 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4024 OutChains.push_back(Store);
4028 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4031 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4034 /// \param DAG Selection DAG where lowered code is placed.
4035 /// \param dl Link to corresponding IR location.
4036 /// \param Chain Control flow dependency.
4037 /// \param Dst Pointer to destination memory location.
4038 /// \param Src Value of byte to write into the memory.
4039 /// \param Size Number of bytes to write.
4040 /// \param Align Alignment of the destination in bytes.
4041 /// \param isVol True if destination is volatile.
4042 /// \param DstPtrInfo IR information on the memory pointer.
4043 /// \returns New head in the control flow, if lowering was successful, empty
4044 /// SDValue otherwise.
4046 /// The function tries to replace 'llvm.memset' intrinsic with several store
4047 /// operations and value calculation code. This is usually profitable for small
4049 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4050 SDValue Chain, SDValue Dst,
4051 SDValue Src, uint64_t Size,
4052 unsigned Align, bool isVol,
4053 MachinePointerInfo DstPtrInfo) {
4054 // Turn a memset of undef to nop.
4055 if (Src.getOpcode() == ISD::UNDEF)
4058 // Expand memset to a series of load/store ops if the size operand
4059 // falls below a certain threshold.
4060 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4061 std::vector<EVT> MemOps;
4062 bool DstAlignCanChange = false;
4063 MachineFunction &MF = DAG.getMachineFunction();
4064 MachineFrameInfo *MFI = MF.getFrameInfo();
4065 bool OptSize = MF.getFunction()->getAttributes().
4066 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4067 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4068 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4069 DstAlignCanChange = true;
4071 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4072 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4073 Size, (DstAlignCanChange ? 0 : Align), 0,
4074 true, IsZeroVal, false, true, DAG, TLI))
4077 if (DstAlignCanChange) {
4078 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4079 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4080 if (NewAlign > Align) {
4081 // Give the stack frame object a larger alignment if needed.
4082 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4083 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4088 SmallVector<SDValue, 8> OutChains;
4089 uint64_t DstOff = 0;
4090 unsigned NumMemOps = MemOps.size();
4092 // Find the largest store and generate the bit pattern for it.
4093 EVT LargestVT = MemOps[0];
4094 for (unsigned i = 1; i < NumMemOps; i++)
4095 if (MemOps[i].bitsGT(LargestVT))
4096 LargestVT = MemOps[i];
4097 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4099 for (unsigned i = 0; i < NumMemOps; i++) {
4101 unsigned VTSize = VT.getSizeInBits() / 8;
4102 if (VTSize > Size) {
4103 // Issuing an unaligned load / store pair that overlaps with the previous
4104 // pair. Adjust the offset accordingly.
4105 assert(i == NumMemOps-1 && i != 0);
4106 DstOff -= VTSize - Size;
4109 // If this store is smaller than the largest store see whether we can get
4110 // the smaller value for free with a truncate.
4111 SDValue Value = MemSetValue;
4112 if (VT.bitsLT(LargestVT)) {
4113 if (!LargestVT.isVector() && !VT.isVector() &&
4114 TLI.isTruncateFree(LargestVT, VT))
4115 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4117 Value = getMemsetValue(Src, VT, DAG, dl);
4119 assert(Value.getValueType() == VT && "Value with wrong type.");
4120 SDValue Store = DAG.getStore(Chain, dl, Value,
4121 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4122 DstPtrInfo.getWithOffset(DstOff),
4123 isVol, false, Align);
4124 OutChains.push_back(Store);
4125 DstOff += VT.getSizeInBits() / 8;
4129 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4132 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4133 SDValue Src, SDValue Size,
4134 unsigned Align, bool isVol, bool AlwaysInline,
4135 MachinePointerInfo DstPtrInfo,
4136 MachinePointerInfo SrcPtrInfo) {
4137 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4139 // Check to see if we should lower the memcpy to loads and stores first.
4140 // For cases within the target-specified limits, this is the best choice.
4141 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4143 // Memcpy with size zero? Just return the original chain.
4144 if (ConstantSize->isNullValue())
4147 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4148 ConstantSize->getZExtValue(),Align,
4149 isVol, false, DstPtrInfo, SrcPtrInfo);
4150 if (Result.getNode())
4154 // Then check to see if we should lower the memcpy with target-specific
4155 // code. If the target chooses to do this, this is the next best.
4157 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4158 isVol, AlwaysInline,
4159 DstPtrInfo, SrcPtrInfo);
4160 if (Result.getNode())
4163 // If we really need inline code and the target declined to provide it,
4164 // use a (potentially long) sequence of loads and stores.
4166 assert(ConstantSize && "AlwaysInline requires a constant size!");
4167 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4168 ConstantSize->getZExtValue(), Align, isVol,
4169 true, DstPtrInfo, SrcPtrInfo);
4172 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4173 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4174 // respect volatile, so they may do things like read or write memory
4175 // beyond the given memory regions. But fixing this isn't easy, and most
4176 // people don't care.
4178 const TargetLowering *TLI = TM.getTargetLowering();
4180 // Emit a library call.
4181 TargetLowering::ArgListTy Args;
4182 TargetLowering::ArgListEntry Entry;
4183 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4184 Entry.Node = Dst; Args.push_back(Entry);
4185 Entry.Node = Src; Args.push_back(Entry);
4186 Entry.Node = Size; Args.push_back(Entry);
4187 // FIXME: pass in SDLoc
4188 TargetLowering::CallLoweringInfo CLI(*this);
4189 CLI.setDebugLoc(dl).setChain(Chain)
4190 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4191 Type::getVoidTy(*getContext()),
4192 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4193 TLI->getPointerTy()), std::move(Args), 0)
4194 .setDiscardResult();
4195 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4197 return CallResult.second;
4200 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4201 SDValue Src, SDValue Size,
4202 unsigned Align, bool isVol,
4203 MachinePointerInfo DstPtrInfo,
4204 MachinePointerInfo SrcPtrInfo) {
4205 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4207 // Check to see if we should lower the memmove to loads and stores first.
4208 // For cases within the target-specified limits, this is the best choice.
4209 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4211 // Memmove with size zero? Just return the original chain.
4212 if (ConstantSize->isNullValue())
4216 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4217 ConstantSize->getZExtValue(), Align, isVol,
4218 false, DstPtrInfo, SrcPtrInfo);
4219 if (Result.getNode())
4223 // Then check to see if we should lower the memmove with target-specific
4224 // code. If the target chooses to do this, this is the next best.
4226 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4227 DstPtrInfo, SrcPtrInfo);
4228 if (Result.getNode())
4231 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4232 // not be safe. See memcpy above for more details.
4234 const TargetLowering *TLI = TM.getTargetLowering();
4236 // Emit a library call.
4237 TargetLowering::ArgListTy Args;
4238 TargetLowering::ArgListEntry Entry;
4239 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4240 Entry.Node = Dst; Args.push_back(Entry);
4241 Entry.Node = Src; Args.push_back(Entry);
4242 Entry.Node = Size; Args.push_back(Entry);
4243 // FIXME: pass in SDLoc
4244 TargetLowering::CallLoweringInfo CLI(*this);
4245 CLI.setDebugLoc(dl).setChain(Chain)
4246 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4247 Type::getVoidTy(*getContext()),
4248 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4249 TLI->getPointerTy()), std::move(Args), 0)
4250 .setDiscardResult();
4251 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4253 return CallResult.second;
4256 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4257 SDValue Src, SDValue Size,
4258 unsigned Align, bool isVol,
4259 MachinePointerInfo DstPtrInfo) {
4260 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4262 // Check to see if we should lower the memset to stores first.
4263 // For cases within the target-specified limits, this is the best choice.
4264 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4266 // Memset with size zero? Just return the original chain.
4267 if (ConstantSize->isNullValue())
4271 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4272 Align, isVol, DstPtrInfo);
4274 if (Result.getNode())
4278 // Then check to see if we should lower the memset with target-specific
4279 // code. If the target chooses to do this, this is the next best.
4281 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4283 if (Result.getNode())
4286 // Emit a library call.
4287 const TargetLowering *TLI = TM.getTargetLowering();
4288 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4289 TargetLowering::ArgListTy Args;
4290 TargetLowering::ArgListEntry Entry;
4291 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4292 Args.push_back(Entry);
4293 // Extend or truncate the argument to be an i32 value for the call.
4294 if (Src.getValueType().bitsGT(MVT::i32))
4295 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4297 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4299 Entry.Ty = Type::getInt32Ty(*getContext());
4300 Entry.isSExt = true;
4301 Args.push_back(Entry);
4303 Entry.Ty = IntPtrTy;
4304 Entry.isSExt = false;
4305 Args.push_back(Entry);
4307 // FIXME: pass in SDLoc
4308 TargetLowering::CallLoweringInfo CLI(*this);
4309 CLI.setDebugLoc(dl).setChain(Chain)
4310 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4311 Type::getVoidTy(*getContext()),
4312 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4313 TLI->getPointerTy()), std::move(Args), 0)
4314 .setDiscardResult();
4316 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4317 return CallResult.second;
4320 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4321 SDVTList VTList, ArrayRef<SDValue> Ops,
4322 MachineMemOperand *MMO,
4323 AtomicOrdering SuccessOrdering,
4324 AtomicOrdering FailureOrdering,
4325 SynchronizationScope SynchScope) {
4326 FoldingSetNodeID ID;
4327 ID.AddInteger(MemVT.getRawBits());
4328 AddNodeIDNode(ID, Opcode, VTList, Ops);
4329 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4331 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4332 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4333 return SDValue(E, 0);
4336 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4337 // SDNode doesn't have access to it. This memory will be "leaked" when
4338 // the node is deallocated, but recovered when the allocator is released.
4339 // If the number of operands is less than 5 we use AtomicSDNode's internal
4341 unsigned NumOps = Ops.size();
4342 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4345 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4346 dl.getDebugLoc(), VTList, MemVT,
4347 Ops.data(), DynOps, NumOps, MMO,
4348 SuccessOrdering, FailureOrdering,
4350 CSEMap.InsertNode(N, IP);
4351 AllNodes.push_back(N);
4352 return SDValue(N, 0);
4355 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4356 SDVTList VTList, ArrayRef<SDValue> Ops,
4357 MachineMemOperand *MMO,
4358 AtomicOrdering Ordering,
4359 SynchronizationScope SynchScope) {
4360 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4361 Ordering, SynchScope);
4364 SDValue SelectionDAG::getAtomicCmpSwap(
4365 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4366 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4367 unsigned Alignment, AtomicOrdering SuccessOrdering,
4368 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4369 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4370 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4371 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4373 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4374 Alignment = getEVTAlignment(MemVT);
4376 MachineFunction &MF = getMachineFunction();
4378 // FIXME: Volatile isn't really correct; we should keep track of atomic
4379 // orderings in the memoperand.
4380 unsigned Flags = MachineMemOperand::MOVolatile;
4381 Flags |= MachineMemOperand::MOLoad;
4382 Flags |= MachineMemOperand::MOStore;
4384 MachineMemOperand *MMO =
4385 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4387 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4388 SuccessOrdering, FailureOrdering, SynchScope);
4391 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4392 SDVTList VTs, SDValue Chain, SDValue Ptr,
4393 SDValue Cmp, SDValue Swp,
4394 MachineMemOperand *MMO,
4395 AtomicOrdering SuccessOrdering,
4396 AtomicOrdering FailureOrdering,
4397 SynchronizationScope SynchScope) {
4398 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4399 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4400 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4402 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4403 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4404 SuccessOrdering, FailureOrdering, SynchScope);
4407 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4409 SDValue Ptr, SDValue Val,
4410 const Value* PtrVal,
4412 AtomicOrdering Ordering,
4413 SynchronizationScope SynchScope) {
4414 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4415 Alignment = getEVTAlignment(MemVT);
4417 MachineFunction &MF = getMachineFunction();
4418 // An atomic store does not load. An atomic load does not store.
4419 // (An atomicrmw obviously both loads and stores.)
4420 // For now, atomics are considered to be volatile always, and they are
4422 // FIXME: Volatile isn't really correct; we should keep track of atomic
4423 // orderings in the memoperand.
4424 unsigned Flags = MachineMemOperand::MOVolatile;
4425 if (Opcode != ISD::ATOMIC_STORE)
4426 Flags |= MachineMemOperand::MOLoad;
4427 if (Opcode != ISD::ATOMIC_LOAD)
4428 Flags |= MachineMemOperand::MOStore;
4430 MachineMemOperand *MMO =
4431 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4432 MemVT.getStoreSize(), Alignment);
4434 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4435 Ordering, SynchScope);
4438 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4440 SDValue Ptr, SDValue Val,
4441 MachineMemOperand *MMO,
4442 AtomicOrdering Ordering,
4443 SynchronizationScope SynchScope) {
4444 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4445 Opcode == ISD::ATOMIC_LOAD_SUB ||
4446 Opcode == ISD::ATOMIC_LOAD_AND ||
4447 Opcode == ISD::ATOMIC_LOAD_OR ||
4448 Opcode == ISD::ATOMIC_LOAD_XOR ||
4449 Opcode == ISD::ATOMIC_LOAD_NAND ||
4450 Opcode == ISD::ATOMIC_LOAD_MIN ||
4451 Opcode == ISD::ATOMIC_LOAD_MAX ||
4452 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4453 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4454 Opcode == ISD::ATOMIC_SWAP ||
4455 Opcode == ISD::ATOMIC_STORE) &&
4456 "Invalid Atomic Op");
4458 EVT VT = Val.getValueType();
4460 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4461 getVTList(VT, MVT::Other);
4462 SDValue Ops[] = {Chain, Ptr, Val};
4463 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4466 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4467 EVT VT, SDValue Chain,
4469 MachineMemOperand *MMO,
4470 AtomicOrdering Ordering,
4471 SynchronizationScope SynchScope) {
4472 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4474 SDVTList VTs = getVTList(VT, MVT::Other);
4475 SDValue Ops[] = {Chain, Ptr};
4476 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4479 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4480 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4481 if (Ops.size() == 1)
4484 SmallVector<EVT, 4> VTs;
4485 VTs.reserve(Ops.size());
4486 for (unsigned i = 0; i < Ops.size(); ++i)
4487 VTs.push_back(Ops[i].getValueType());
4488 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4492 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4493 ArrayRef<SDValue> Ops,
4494 EVT MemVT, MachinePointerInfo PtrInfo,
4495 unsigned Align, bool Vol,
4496 bool ReadMem, bool WriteMem) {
4497 if (Align == 0) // Ensure that codegen never sees alignment 0
4498 Align = getEVTAlignment(MemVT);
4500 MachineFunction &MF = getMachineFunction();
4503 Flags |= MachineMemOperand::MOStore;
4505 Flags |= MachineMemOperand::MOLoad;
4507 Flags |= MachineMemOperand::MOVolatile;
4508 MachineMemOperand *MMO =
4509 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4511 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4515 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4516 ArrayRef<SDValue> Ops, EVT MemVT,
4517 MachineMemOperand *MMO) {
4518 assert((Opcode == ISD::INTRINSIC_VOID ||
4519 Opcode == ISD::INTRINSIC_W_CHAIN ||
4520 Opcode == ISD::PREFETCH ||
4521 Opcode == ISD::LIFETIME_START ||
4522 Opcode == ISD::LIFETIME_END ||
4523 (Opcode <= INT_MAX &&
4524 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4525 "Opcode is not a memory-accessing opcode!");
4527 // Memoize the node unless it returns a flag.
4528 MemIntrinsicSDNode *N;
4529 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4530 FoldingSetNodeID ID;
4531 AddNodeIDNode(ID, Opcode, VTList, Ops);
4532 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4534 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4535 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4536 return SDValue(E, 0);
4539 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4540 dl.getDebugLoc(), VTList, Ops,
4542 CSEMap.InsertNode(N, IP);
4544 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4545 dl.getDebugLoc(), VTList, Ops,
4548 AllNodes.push_back(N);
4549 return SDValue(N, 0);
4552 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4553 /// MachinePointerInfo record from it. This is particularly useful because the
4554 /// code generator has many cases where it doesn't bother passing in a
4555 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4556 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4557 // If this is FI+Offset, we can model it.
4558 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4559 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4561 // If this is (FI+Offset1)+Offset2, we can model it.
4562 if (Ptr.getOpcode() != ISD::ADD ||
4563 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4564 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4565 return MachinePointerInfo();
4567 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4568 return MachinePointerInfo::getFixedStack(FI, Offset+
4569 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4572 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4573 /// MachinePointerInfo record from it. This is particularly useful because the
4574 /// code generator has many cases where it doesn't bother passing in a
4575 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4576 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4577 // If the 'Offset' value isn't a constant, we can't handle this.
4578 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4579 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4580 if (OffsetOp.getOpcode() == ISD::UNDEF)
4581 return InferPointerInfo(Ptr);
4582 return MachinePointerInfo();
4587 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4588 EVT VT, SDLoc dl, SDValue Chain,
4589 SDValue Ptr, SDValue Offset,
4590 MachinePointerInfo PtrInfo, EVT MemVT,
4591 bool isVolatile, bool isNonTemporal, bool isInvariant,
4592 unsigned Alignment, const MDNode *TBAAInfo,
4593 const MDNode *Ranges) {
4594 assert(Chain.getValueType() == MVT::Other &&
4595 "Invalid chain type");
4596 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4597 Alignment = getEVTAlignment(VT);
4599 unsigned Flags = MachineMemOperand::MOLoad;
4601 Flags |= MachineMemOperand::MOVolatile;
4603 Flags |= MachineMemOperand::MONonTemporal;
4605 Flags |= MachineMemOperand::MOInvariant;
4607 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4609 if (PtrInfo.V.isNull())
4610 PtrInfo = InferPointerInfo(Ptr, Offset);
4612 MachineFunction &MF = getMachineFunction();
4613 MachineMemOperand *MMO =
4614 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4616 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4620 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4621 EVT VT, SDLoc dl, SDValue Chain,
4622 SDValue Ptr, SDValue Offset, EVT MemVT,
4623 MachineMemOperand *MMO) {
4625 ExtType = ISD::NON_EXTLOAD;
4626 } else if (ExtType == ISD::NON_EXTLOAD) {
4627 assert(VT == MemVT && "Non-extending load from different memory type!");
4630 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4631 "Should only be an extending load, not truncating!");
4632 assert(VT.isInteger() == MemVT.isInteger() &&
4633 "Cannot convert from FP to Int or Int -> FP!");
4634 assert(VT.isVector() == MemVT.isVector() &&
4635 "Cannot use trunc store to convert to or from a vector!");
4636 assert((!VT.isVector() ||
4637 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4638 "Cannot use trunc store to change the number of vector elements!");
4641 bool Indexed = AM != ISD::UNINDEXED;
4642 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4643 "Unindexed load with an offset!");
4645 SDVTList VTs = Indexed ?
4646 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4647 SDValue Ops[] = { Chain, Ptr, Offset };
4648 FoldingSetNodeID ID;
4649 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4650 ID.AddInteger(MemVT.getRawBits());
4651 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4652 MMO->isNonTemporal(),
4653 MMO->isInvariant()));
4654 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4656 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4657 cast<LoadSDNode>(E)->refineAlignment(MMO);
4658 return SDValue(E, 0);
4660 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4661 dl.getDebugLoc(), VTs, AM, ExtType,
4663 CSEMap.InsertNode(N, IP);
4664 AllNodes.push_back(N);
4665 return SDValue(N, 0);
4668 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4669 SDValue Chain, SDValue Ptr,
4670 MachinePointerInfo PtrInfo,
4671 bool isVolatile, bool isNonTemporal,
4672 bool isInvariant, unsigned Alignment,
4673 const MDNode *TBAAInfo,
4674 const MDNode *Ranges) {
4675 SDValue Undef = getUNDEF(Ptr.getValueType());
4676 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4677 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4681 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4682 SDValue Chain, SDValue Ptr,
4683 MachineMemOperand *MMO) {
4684 SDValue Undef = getUNDEF(Ptr.getValueType());
4685 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4689 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4690 SDValue Chain, SDValue Ptr,
4691 MachinePointerInfo PtrInfo, EVT MemVT,
4692 bool isVolatile, bool isNonTemporal,
4693 unsigned Alignment, const MDNode *TBAAInfo) {
4694 SDValue Undef = getUNDEF(Ptr.getValueType());
4695 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4696 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4701 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4702 SDValue Chain, SDValue Ptr, EVT MemVT,
4703 MachineMemOperand *MMO) {
4704 SDValue Undef = getUNDEF(Ptr.getValueType());
4705 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4710 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4711 SDValue Offset, ISD::MemIndexedMode AM) {
4712 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4713 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4714 "Load is already a indexed load!");
4715 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4716 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4717 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4718 false, LD->getAlignment());
4721 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4722 SDValue Ptr, MachinePointerInfo PtrInfo,
4723 bool isVolatile, bool isNonTemporal,
4724 unsigned Alignment, const MDNode *TBAAInfo) {
4725 assert(Chain.getValueType() == MVT::Other &&
4726 "Invalid chain type");
4727 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4728 Alignment = getEVTAlignment(Val.getValueType());
4730 unsigned Flags = MachineMemOperand::MOStore;
4732 Flags |= MachineMemOperand::MOVolatile;
4734 Flags |= MachineMemOperand::MONonTemporal;
4736 if (PtrInfo.V.isNull())
4737 PtrInfo = InferPointerInfo(Ptr);
4739 MachineFunction &MF = getMachineFunction();
4740 MachineMemOperand *MMO =
4741 MF.getMachineMemOperand(PtrInfo, Flags,
4742 Val.getValueType().getStoreSize(), Alignment,
4745 return getStore(Chain, dl, Val, Ptr, MMO);
4748 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4749 SDValue Ptr, MachineMemOperand *MMO) {
4750 assert(Chain.getValueType() == MVT::Other &&
4751 "Invalid chain type");
4752 EVT VT = Val.getValueType();
4753 SDVTList VTs = getVTList(MVT::Other);
4754 SDValue Undef = getUNDEF(Ptr.getValueType());
4755 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4756 FoldingSetNodeID ID;
4757 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4758 ID.AddInteger(VT.getRawBits());
4759 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4760 MMO->isNonTemporal(), MMO->isInvariant()));
4761 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4763 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4764 cast<StoreSDNode>(E)->refineAlignment(MMO);
4765 return SDValue(E, 0);
4767 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4768 dl.getDebugLoc(), VTs,
4769 ISD::UNINDEXED, false, VT, MMO);
4770 CSEMap.InsertNode(N, IP);
4771 AllNodes.push_back(N);
4772 return SDValue(N, 0);
4775 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4776 SDValue Ptr, MachinePointerInfo PtrInfo,
4777 EVT SVT,bool isVolatile, bool isNonTemporal,
4779 const MDNode *TBAAInfo) {
4780 assert(Chain.getValueType() == MVT::Other &&
4781 "Invalid chain type");
4782 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4783 Alignment = getEVTAlignment(SVT);
4785 unsigned Flags = MachineMemOperand::MOStore;
4787 Flags |= MachineMemOperand::MOVolatile;
4789 Flags |= MachineMemOperand::MONonTemporal;
4791 if (PtrInfo.V.isNull())
4792 PtrInfo = InferPointerInfo(Ptr);
4794 MachineFunction &MF = getMachineFunction();
4795 MachineMemOperand *MMO =
4796 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4799 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4802 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4803 SDValue Ptr, EVT SVT,
4804 MachineMemOperand *MMO) {
4805 EVT VT = Val.getValueType();
4807 assert(Chain.getValueType() == MVT::Other &&
4808 "Invalid chain type");
4810 return getStore(Chain, dl, Val, Ptr, MMO);
4812 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4813 "Should only be a truncating store, not extending!");
4814 assert(VT.isInteger() == SVT.isInteger() &&
4815 "Can't do FP-INT conversion!");
4816 assert(VT.isVector() == SVT.isVector() &&
4817 "Cannot use trunc store to convert to or from a vector!");
4818 assert((!VT.isVector() ||
4819 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4820 "Cannot use trunc store to change the number of vector elements!");
4822 SDVTList VTs = getVTList(MVT::Other);
4823 SDValue Undef = getUNDEF(Ptr.getValueType());
4824 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4825 FoldingSetNodeID ID;
4826 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4827 ID.AddInteger(SVT.getRawBits());
4828 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4829 MMO->isNonTemporal(), MMO->isInvariant()));
4830 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4832 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4833 cast<StoreSDNode>(E)->refineAlignment(MMO);
4834 return SDValue(E, 0);
4836 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4837 dl.getDebugLoc(), VTs,
4838 ISD::UNINDEXED, true, SVT, MMO);
4839 CSEMap.InsertNode(N, IP);
4840 AllNodes.push_back(N);
4841 return SDValue(N, 0);
4845 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4846 SDValue Offset, ISD::MemIndexedMode AM) {
4847 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4848 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4849 "Store is already a indexed store!");
4850 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4851 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4852 FoldingSetNodeID ID;
4853 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4854 ID.AddInteger(ST->getMemoryVT().getRawBits());
4855 ID.AddInteger(ST->getRawSubclassData());
4856 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4858 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4859 return SDValue(E, 0);
4861 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4862 dl.getDebugLoc(), VTs, AM,
4863 ST->isTruncatingStore(),
4865 ST->getMemOperand());
4866 CSEMap.InsertNode(N, IP);
4867 AllNodes.push_back(N);
4868 return SDValue(N, 0);
4871 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4872 SDValue Chain, SDValue Ptr,
4875 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4876 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4879 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4880 ArrayRef<SDUse> Ops) {
4881 switch (Ops.size()) {
4882 case 0: return getNode(Opcode, DL, VT);
4883 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4884 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4885 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4889 // Copy from an SDUse array into an SDValue array for use with
4890 // the regular getNode logic.
4891 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4892 return getNode(Opcode, DL, VT, NewOps);
4895 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4896 ArrayRef<SDValue> Ops) {
4897 unsigned NumOps = Ops.size();
4899 case 0: return getNode(Opcode, DL, VT);
4900 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4901 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4902 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4908 case ISD::SELECT_CC: {
4909 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4910 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4911 "LHS and RHS of condition must have same type!");
4912 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4913 "True and False arms of SelectCC must have same type!");
4914 assert(Ops[2].getValueType() == VT &&
4915 "select_cc node must be of same type as true and false value!");
4919 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4920 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4921 "LHS/RHS of comparison should match types!");
4928 SDVTList VTs = getVTList(VT);
4930 if (VT != MVT::Glue) {
4931 FoldingSetNodeID ID;
4932 AddNodeIDNode(ID, Opcode, VTs, Ops);
4935 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4936 return SDValue(E, 0);
4938 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4940 CSEMap.InsertNode(N, IP);
4942 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4946 AllNodes.push_back(N);
4950 return SDValue(N, 0);
4953 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4954 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4955 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4958 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4959 ArrayRef<SDValue> Ops) {
4960 if (VTList.NumVTs == 1)
4961 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4965 // FIXME: figure out how to safely handle things like
4966 // int foo(int x) { return 1 << (x & 255); }
4967 // int bar() { return foo(256); }
4968 case ISD::SRA_PARTS:
4969 case ISD::SRL_PARTS:
4970 case ISD::SHL_PARTS:
4971 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4972 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4973 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4974 else if (N3.getOpcode() == ISD::AND)
4975 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4976 // If the and is only masking out bits that cannot effect the shift,
4977 // eliminate the and.
4978 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4979 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4980 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4986 // Memoize the node unless it returns a flag.
4988 unsigned NumOps = Ops.size();
4989 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4990 FoldingSetNodeID ID;
4991 AddNodeIDNode(ID, Opcode, VTList, Ops);
4993 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4994 return SDValue(E, 0);
4997 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4998 DL.getDebugLoc(), VTList, Ops[0]);
4999 } else if (NumOps == 2) {
5000 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5001 DL.getDebugLoc(), VTList, Ops[0],
5003 } else if (NumOps == 3) {
5004 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5005 DL.getDebugLoc(), VTList, Ops[0],
5008 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5011 CSEMap.InsertNode(N, IP);
5014 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5015 DL.getDebugLoc(), VTList, Ops[0]);
5016 } else if (NumOps == 2) {
5017 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5018 DL.getDebugLoc(), VTList, Ops[0],
5020 } else if (NumOps == 3) {
5021 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5022 DL.getDebugLoc(), VTList, Ops[0],
5025 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5029 AllNodes.push_back(N);
5033 return SDValue(N, 0);
5036 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5037 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5040 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5042 SDValue Ops[] = { N1 };
5043 return getNode(Opcode, DL, VTList, Ops);
5046 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5047 SDValue N1, SDValue N2) {
5048 SDValue Ops[] = { N1, N2 };
5049 return getNode(Opcode, DL, VTList, Ops);
5052 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5053 SDValue N1, SDValue N2, SDValue N3) {
5054 SDValue Ops[] = { N1, N2, N3 };
5055 return getNode(Opcode, DL, VTList, Ops);
5058 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5059 SDValue N1, SDValue N2, SDValue N3,
5061 SDValue Ops[] = { N1, N2, N3, N4 };
5062 return getNode(Opcode, DL, VTList, Ops);
5065 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5066 SDValue N1, SDValue N2, SDValue N3,
5067 SDValue N4, SDValue N5) {
5068 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5069 return getNode(Opcode, DL, VTList, Ops);
5072 SDVTList SelectionDAG::getVTList(EVT VT) {
5073 return makeVTList(SDNode::getValueTypeList(VT), 1);
5076 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5077 FoldingSetNodeID ID;
5079 ID.AddInteger(VT1.getRawBits());
5080 ID.AddInteger(VT2.getRawBits());
5083 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5085 EVT *Array = Allocator.Allocate<EVT>(2);
5088 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5089 VTListMap.InsertNode(Result, IP);
5091 return Result->getSDVTList();
5094 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5095 FoldingSetNodeID ID;
5097 ID.AddInteger(VT1.getRawBits());
5098 ID.AddInteger(VT2.getRawBits());
5099 ID.AddInteger(VT3.getRawBits());
5102 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5104 EVT *Array = Allocator.Allocate<EVT>(3);
5108 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5109 VTListMap.InsertNode(Result, IP);
5111 return Result->getSDVTList();
5114 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5115 FoldingSetNodeID ID;
5117 ID.AddInteger(VT1.getRawBits());
5118 ID.AddInteger(VT2.getRawBits());
5119 ID.AddInteger(VT3.getRawBits());
5120 ID.AddInteger(VT4.getRawBits());
5123 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5125 EVT *Array = Allocator.Allocate<EVT>(4);
5130 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5131 VTListMap.InsertNode(Result, IP);
5133 return Result->getSDVTList();
5136 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5137 unsigned NumVTs = VTs.size();
5138 FoldingSetNodeID ID;
5139 ID.AddInteger(NumVTs);
5140 for (unsigned index = 0; index < NumVTs; index++) {
5141 ID.AddInteger(VTs[index].getRawBits());
5145 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5147 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5148 std::copy(VTs.begin(), VTs.end(), Array);
5149 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5150 VTListMap.InsertNode(Result, IP);
5152 return Result->getSDVTList();
5156 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5157 /// specified operands. If the resultant node already exists in the DAG,
5158 /// this does not modify the specified node, instead it returns the node that
5159 /// already exists. If the resultant node does not exist in the DAG, the
5160 /// input node is returned. As a degenerate case, if you specify the same
5161 /// input operands as the node already has, the input node is returned.
5162 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5163 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5165 // Check to see if there is no change.
5166 if (Op == N->getOperand(0)) return N;
5168 // See if the modified node already exists.
5169 void *InsertPos = nullptr;
5170 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5173 // Nope it doesn't. Remove the node from its current place in the maps.
5175 if (!RemoveNodeFromCSEMaps(N))
5176 InsertPos = nullptr;
5178 // Now we update the operands.
5179 N->OperandList[0].set(Op);
5181 // If this gets put into a CSE map, add it.
5182 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5186 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5187 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5189 // Check to see if there is no change.
5190 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5191 return N; // No operands changed, just return the input node.
5193 // See if the modified node already exists.
5194 void *InsertPos = nullptr;
5195 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5198 // Nope it doesn't. Remove the node from its current place in the maps.
5200 if (!RemoveNodeFromCSEMaps(N))
5201 InsertPos = nullptr;
5203 // Now we update the operands.
5204 if (N->OperandList[0] != Op1)
5205 N->OperandList[0].set(Op1);
5206 if (N->OperandList[1] != Op2)
5207 N->OperandList[1].set(Op2);
5209 // If this gets put into a CSE map, add it.
5210 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5214 SDNode *SelectionDAG::
5215 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5216 SDValue Ops[] = { Op1, Op2, Op3 };
5217 return UpdateNodeOperands(N, Ops);
5220 SDNode *SelectionDAG::
5221 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5222 SDValue Op3, SDValue Op4) {
5223 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5224 return UpdateNodeOperands(N, Ops);
5227 SDNode *SelectionDAG::
5228 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5229 SDValue Op3, SDValue Op4, SDValue Op5) {
5230 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5231 return UpdateNodeOperands(N, Ops);
5234 SDNode *SelectionDAG::
5235 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5236 unsigned NumOps = Ops.size();
5237 assert(N->getNumOperands() == NumOps &&
5238 "Update with wrong number of operands");
5240 // Check to see if there is no change.
5241 bool AnyChange = false;
5242 for (unsigned i = 0; i != NumOps; ++i) {
5243 if (Ops[i] != N->getOperand(i)) {
5249 // No operands changed, just return the input node.
5250 if (!AnyChange) return N;
5252 // See if the modified node already exists.
5253 void *InsertPos = nullptr;
5254 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5257 // Nope it doesn't. Remove the node from its current place in the maps.
5259 if (!RemoveNodeFromCSEMaps(N))
5260 InsertPos = nullptr;
5262 // Now we update the operands.
5263 for (unsigned i = 0; i != NumOps; ++i)
5264 if (N->OperandList[i] != Ops[i])
5265 N->OperandList[i].set(Ops[i]);
5267 // If this gets put into a CSE map, add it.
5268 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5272 /// DropOperands - Release the operands and set this node to have
5274 void SDNode::DropOperands() {
5275 // Unlike the code in MorphNodeTo that does this, we don't need to
5276 // watch for dead nodes here.
5277 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5283 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5286 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5288 SDVTList VTs = getVTList(VT);
5289 return SelectNodeTo(N, MachineOpc, VTs, None);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 EVT VT, SDValue Op1) {
5294 SDVTList VTs = getVTList(VT);
5295 SDValue Ops[] = { Op1 };
5296 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5299 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5300 EVT VT, SDValue Op1,
5302 SDVTList VTs = getVTList(VT);
5303 SDValue Ops[] = { Op1, Op2 };
5304 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5307 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5308 EVT VT, SDValue Op1,
5309 SDValue Op2, SDValue Op3) {
5310 SDVTList VTs = getVTList(VT);
5311 SDValue Ops[] = { Op1, Op2, Op3 };
5312 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5315 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5316 EVT VT, ArrayRef<SDValue> Ops) {
5317 SDVTList VTs = getVTList(VT);
5318 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5321 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5322 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5323 SDVTList VTs = getVTList(VT1, VT2);
5324 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5327 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5329 SDVTList VTs = getVTList(VT1, VT2);
5330 return SelectNodeTo(N, MachineOpc, VTs, None);
5333 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5334 EVT VT1, EVT VT2, EVT VT3,
5335 ArrayRef<SDValue> Ops) {
5336 SDVTList VTs = getVTList(VT1, VT2, VT3);
5337 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5340 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5341 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5342 ArrayRef<SDValue> Ops) {
5343 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5344 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5347 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5350 SDVTList VTs = getVTList(VT1, VT2);
5351 SDValue Ops[] = { Op1 };
5352 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5355 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5357 SDValue Op1, SDValue Op2) {
5358 SDVTList VTs = getVTList(VT1, VT2);
5359 SDValue Ops[] = { Op1, Op2 };
5360 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5363 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5365 SDValue Op1, SDValue Op2,
5367 SDVTList VTs = getVTList(VT1, VT2);
5368 SDValue Ops[] = { Op1, Op2, Op3 };
5369 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5372 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5373 EVT VT1, EVT VT2, EVT VT3,
5374 SDValue Op1, SDValue Op2,
5376 SDVTList VTs = getVTList(VT1, VT2, VT3);
5377 SDValue Ops[] = { Op1, Op2, Op3 };
5378 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5381 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5382 SDVTList VTs,ArrayRef<SDValue> Ops) {
5383 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5384 // Reset the NodeID to -1.
5389 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5390 /// the line number information on the merged node since it is not possible to
5391 /// preserve the information that operation is associated with multiple lines.
5392 /// This will make the debugger working better at -O0, were there is a higher
5393 /// probability having other instructions associated with that line.
5395 /// For IROrder, we keep the smaller of the two
5396 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5397 DebugLoc NLoc = N->getDebugLoc();
5398 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5399 (OLoc.getDebugLoc() != NLoc)) {
5400 N->setDebugLoc(DebugLoc());
5402 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5403 N->setIROrder(Order);
5407 /// MorphNodeTo - This *mutates* the specified node to have the specified
5408 /// return type, opcode, and operands.
5410 /// Note that MorphNodeTo returns the resultant node. If there is already a
5411 /// node of the specified opcode and operands, it returns that node instead of
5412 /// the current one. Note that the SDLoc need not be the same.
5414 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5415 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5416 /// node, and because it doesn't require CSE recalculation for any of
5417 /// the node's users.
5419 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5420 SDVTList VTs, ArrayRef<SDValue> Ops) {
5421 unsigned NumOps = Ops.size();
5422 // If an identical node already exists, use it.
5424 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5425 FoldingSetNodeID ID;
5426 AddNodeIDNode(ID, Opc, VTs, Ops);
5427 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5428 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5431 if (!RemoveNodeFromCSEMaps(N))
5434 // Start the morphing.
5436 N->ValueList = VTs.VTs;
5437 N->NumValues = VTs.NumVTs;
5439 // Clear the operands list, updating used nodes to remove this from their
5440 // use list. Keep track of any operands that become dead as a result.
5441 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5442 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5444 SDNode *Used = Use.getNode();
5446 if (Used->use_empty())
5447 DeadNodeSet.insert(Used);
5450 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5451 // Initialize the memory references information.
5452 MN->setMemRefs(nullptr, nullptr);
5453 // If NumOps is larger than the # of operands we can have in a
5454 // MachineSDNode, reallocate the operand list.
5455 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5456 if (MN->OperandsNeedDelete)
5457 delete[] MN->OperandList;
5458 if (NumOps > array_lengthof(MN->LocalOperands))
5459 // We're creating a final node that will live unmorphed for the
5460 // remainder of the current SelectionDAG iteration, so we can allocate
5461 // the operands directly out of a pool with no recycling metadata.
5462 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5463 Ops.data(), NumOps);
5465 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5466 MN->OperandsNeedDelete = false;
5468 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5470 // If NumOps is larger than the # of operands we currently have, reallocate
5471 // the operand list.
5472 if (NumOps > N->NumOperands) {
5473 if (N->OperandsNeedDelete)
5474 delete[] N->OperandList;
5475 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5476 N->OperandsNeedDelete = true;
5478 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5481 // Delete any nodes that are still dead after adding the uses for the
5483 if (!DeadNodeSet.empty()) {
5484 SmallVector<SDNode *, 16> DeadNodes;
5485 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5486 E = DeadNodeSet.end(); I != E; ++I)
5487 if ((*I)->use_empty())
5488 DeadNodes.push_back(*I);
5489 RemoveDeadNodes(DeadNodes);
5493 CSEMap.InsertNode(N, IP); // Memoize the new node.
5498 /// getMachineNode - These are used for target selectors to create a new node
5499 /// with specified return type(s), MachineInstr opcode, and operands.
5501 /// Note that getMachineNode returns the resultant node. If there is already a
5502 /// node of the specified opcode and operands, it returns that node instead of
5503 /// the current one.
5505 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5506 SDVTList VTs = getVTList(VT);
5507 return getMachineNode(Opcode, dl, VTs, None);
5511 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5512 SDVTList VTs = getVTList(VT);
5513 SDValue Ops[] = { Op1 };
5514 return getMachineNode(Opcode, dl, VTs, Ops);
5518 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5519 SDValue Op1, SDValue Op2) {
5520 SDVTList VTs = getVTList(VT);
5521 SDValue Ops[] = { Op1, Op2 };
5522 return getMachineNode(Opcode, dl, VTs, Ops);
5526 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5527 SDValue Op1, SDValue Op2, SDValue Op3) {
5528 SDVTList VTs = getVTList(VT);
5529 SDValue Ops[] = { Op1, Op2, Op3 };
5530 return getMachineNode(Opcode, dl, VTs, Ops);
5534 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5535 ArrayRef<SDValue> Ops) {
5536 SDVTList VTs = getVTList(VT);
5537 return getMachineNode(Opcode, dl, VTs, Ops);
5541 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5542 SDVTList VTs = getVTList(VT1, VT2);
5543 return getMachineNode(Opcode, dl, VTs, None);
5547 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5548 EVT VT1, EVT VT2, SDValue Op1) {
5549 SDVTList VTs = getVTList(VT1, VT2);
5550 SDValue Ops[] = { Op1 };
5551 return getMachineNode(Opcode, dl, VTs, Ops);
5555 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5556 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5557 SDVTList VTs = getVTList(VT1, VT2);
5558 SDValue Ops[] = { Op1, Op2 };
5559 return getMachineNode(Opcode, dl, VTs, Ops);
5563 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5564 EVT VT1, EVT VT2, SDValue Op1,
5565 SDValue Op2, SDValue Op3) {
5566 SDVTList VTs = getVTList(VT1, VT2);
5567 SDValue Ops[] = { Op1, Op2, Op3 };
5568 return getMachineNode(Opcode, dl, VTs, Ops);
5572 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5574 ArrayRef<SDValue> Ops) {
5575 SDVTList VTs = getVTList(VT1, VT2);
5576 return getMachineNode(Opcode, dl, VTs, Ops);
5580 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5581 EVT VT1, EVT VT2, EVT VT3,
5582 SDValue Op1, SDValue Op2) {
5583 SDVTList VTs = getVTList(VT1, VT2, VT3);
5584 SDValue Ops[] = { Op1, Op2 };
5585 return getMachineNode(Opcode, dl, VTs, Ops);
5589 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5590 EVT VT1, EVT VT2, EVT VT3,
5591 SDValue Op1, SDValue Op2, SDValue Op3) {
5592 SDVTList VTs = getVTList(VT1, VT2, VT3);
5593 SDValue Ops[] = { Op1, Op2, Op3 };
5594 return getMachineNode(Opcode, dl, VTs, Ops);
5598 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5599 EVT VT1, EVT VT2, EVT VT3,
5600 ArrayRef<SDValue> Ops) {
5601 SDVTList VTs = getVTList(VT1, VT2, VT3);
5602 return getMachineNode(Opcode, dl, VTs, Ops);
5606 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5607 EVT VT2, EVT VT3, EVT VT4,
5608 ArrayRef<SDValue> Ops) {
5609 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5610 return getMachineNode(Opcode, dl, VTs, Ops);
5614 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5615 ArrayRef<EVT> ResultTys,
5616 ArrayRef<SDValue> Ops) {
5617 SDVTList VTs = getVTList(ResultTys);
5618 return getMachineNode(Opcode, dl, VTs, Ops);
5622 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5623 ArrayRef<SDValue> OpsArray) {
5624 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5627 const SDValue *Ops = OpsArray.data();
5628 unsigned NumOps = OpsArray.size();
5631 FoldingSetNodeID ID;
5632 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5634 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5635 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5639 // Allocate a new MachineSDNode.
5640 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5641 DL.getDebugLoc(), VTs);
5643 // Initialize the operands list.
5644 if (NumOps > array_lengthof(N->LocalOperands))
5645 // We're creating a final node that will live unmorphed for the
5646 // remainder of the current SelectionDAG iteration, so we can allocate
5647 // the operands directly out of a pool with no recycling metadata.
5648 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5651 N->InitOperands(N->LocalOperands, Ops, NumOps);
5652 N->OperandsNeedDelete = false;
5655 CSEMap.InsertNode(N, IP);
5657 AllNodes.push_back(N);
5659 VerifyMachineNode(N);
5664 /// getTargetExtractSubreg - A convenience function for creating
5665 /// TargetOpcode::EXTRACT_SUBREG nodes.
5667 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5669 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5670 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5671 VT, Operand, SRIdxVal);
5672 return SDValue(Subreg, 0);
5675 /// getTargetInsertSubreg - A convenience function for creating
5676 /// TargetOpcode::INSERT_SUBREG nodes.
5678 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5679 SDValue Operand, SDValue Subreg) {
5680 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5681 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5682 VT, Operand, Subreg, SRIdxVal);
5683 return SDValue(Result, 0);
5686 /// getNodeIfExists - Get the specified node if it's already available, or
5687 /// else return NULL.
5688 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5689 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5691 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5692 FoldingSetNodeID ID;
5693 AddNodeIDNode(ID, Opcode, VTList, Ops);
5694 if (isBinOpWithFlags(Opcode))
5695 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5697 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5703 /// getDbgValue - Creates a SDDbgValue node.
5707 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5708 bool IsIndirect, uint64_t Off,
5709 DebugLoc DL, unsigned O) {
5710 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5715 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5717 DebugLoc DL, unsigned O) {
5718 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5723 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5724 DebugLoc DL, unsigned O) {
5725 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5730 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5731 /// pointed to by a use iterator is deleted, increment the use iterator
5732 /// so that it doesn't dangle.
5734 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5735 SDNode::use_iterator &UI;
5736 SDNode::use_iterator &UE;
5738 void NodeDeleted(SDNode *N, SDNode *E) override {
5739 // Increment the iterator as needed.
5740 while (UI != UE && N == *UI)
5745 RAUWUpdateListener(SelectionDAG &d,
5746 SDNode::use_iterator &ui,
5747 SDNode::use_iterator &ue)
5748 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5753 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5754 /// This can cause recursive merging of nodes in the DAG.
5756 /// This version assumes From has a single result value.
5758 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5759 SDNode *From = FromN.getNode();
5760 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5761 "Cannot replace with this method!");
5762 assert(From != To.getNode() && "Cannot replace uses of with self");
5764 // Iterate over all the existing uses of From. New uses will be added
5765 // to the beginning of the use list, which we avoid visiting.
5766 // This specifically avoids visiting uses of From that arise while the
5767 // replacement is happening, because any such uses would be the result
5768 // of CSE: If an existing node looks like From after one of its operands
5769 // is replaced by To, we don't want to replace of all its users with To
5770 // too. See PR3018 for more info.
5771 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5772 RAUWUpdateListener Listener(*this, UI, UE);
5776 // This node is about to morph, remove its old self from the CSE maps.
5777 RemoveNodeFromCSEMaps(User);
5779 // A user can appear in a use list multiple times, and when this
5780 // happens the uses are usually next to each other in the list.
5781 // To help reduce the number of CSE recomputations, process all
5782 // the uses of this user that we can find this way.
5784 SDUse &Use = UI.getUse();
5787 } while (UI != UE && *UI == User);
5789 // Now that we have modified User, add it back to the CSE maps. If it
5790 // already exists there, recursively merge the results together.
5791 AddModifiedNodeToCSEMaps(User);
5794 // If we just RAUW'd the root, take note.
5795 if (FromN == getRoot())
5799 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5800 /// This can cause recursive merging of nodes in the DAG.
5802 /// This version assumes that for each value of From, there is a
5803 /// corresponding value in To in the same position with the same type.
5805 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5807 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5808 assert((!From->hasAnyUseOfValue(i) ||
5809 From->getValueType(i) == To->getValueType(i)) &&
5810 "Cannot use this version of ReplaceAllUsesWith!");
5813 // Handle the trivial case.
5817 // Iterate over just the existing users of From. See the comments in
5818 // the ReplaceAllUsesWith above.
5819 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5820 RAUWUpdateListener Listener(*this, UI, UE);
5824 // This node is about to morph, remove its old self from the CSE maps.
5825 RemoveNodeFromCSEMaps(User);
5827 // A user can appear in a use list multiple times, and when this
5828 // happens the uses are usually next to each other in the list.
5829 // To help reduce the number of CSE recomputations, process all
5830 // the uses of this user that we can find this way.
5832 SDUse &Use = UI.getUse();
5835 } while (UI != UE && *UI == User);
5837 // Now that we have modified User, add it back to the CSE maps. If it
5838 // already exists there, recursively merge the results together.
5839 AddModifiedNodeToCSEMaps(User);
5842 // If we just RAUW'd the root, take note.
5843 if (From == getRoot().getNode())
5844 setRoot(SDValue(To, getRoot().getResNo()));
5847 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5848 /// This can cause recursive merging of nodes in the DAG.
5850 /// This version can replace From with any result values. To must match the
5851 /// number and types of values returned by From.
5852 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5853 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5854 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5856 // Iterate over just the existing users of From. See the comments in
5857 // the ReplaceAllUsesWith above.
5858 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5859 RAUWUpdateListener Listener(*this, UI, UE);
5863 // This node is about to morph, remove its old self from the CSE maps.
5864 RemoveNodeFromCSEMaps(User);
5866 // A user can appear in a use list multiple times, and when this
5867 // happens the uses are usually next to each other in the list.
5868 // To help reduce the number of CSE recomputations, process all
5869 // the uses of this user that we can find this way.
5871 SDUse &Use = UI.getUse();
5872 const SDValue &ToOp = To[Use.getResNo()];
5875 } while (UI != UE && *UI == User);
5877 // Now that we have modified User, add it back to the CSE maps. If it
5878 // already exists there, recursively merge the results together.
5879 AddModifiedNodeToCSEMaps(User);
5882 // If we just RAUW'd the root, take note.
5883 if (From == getRoot().getNode())
5884 setRoot(SDValue(To[getRoot().getResNo()]));
5887 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5888 /// uses of other values produced by From.getNode() alone. The Deleted
5889 /// vector is handled the same way as for ReplaceAllUsesWith.
5890 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5891 // Handle the really simple, really trivial case efficiently.
5892 if (From == To) return;
5894 // Handle the simple, trivial, case efficiently.
5895 if (From.getNode()->getNumValues() == 1) {
5896 ReplaceAllUsesWith(From, To);
5900 // Iterate over just the existing users of From. See the comments in
5901 // the ReplaceAllUsesWith above.
5902 SDNode::use_iterator UI = From.getNode()->use_begin(),
5903 UE = From.getNode()->use_end();
5904 RAUWUpdateListener Listener(*this, UI, UE);
5907 bool UserRemovedFromCSEMaps = false;
5909 // A user can appear in a use list multiple times, and when this
5910 // happens the uses are usually next to each other in the list.
5911 // To help reduce the number of CSE recomputations, process all
5912 // the uses of this user that we can find this way.
5914 SDUse &Use = UI.getUse();
5916 // Skip uses of different values from the same node.
5917 if (Use.getResNo() != From.getResNo()) {
5922 // If this node hasn't been modified yet, it's still in the CSE maps,
5923 // so remove its old self from the CSE maps.
5924 if (!UserRemovedFromCSEMaps) {
5925 RemoveNodeFromCSEMaps(User);
5926 UserRemovedFromCSEMaps = true;
5931 } while (UI != UE && *UI == User);
5933 // We are iterating over all uses of the From node, so if a use
5934 // doesn't use the specific value, no changes are made.
5935 if (!UserRemovedFromCSEMaps)
5938 // Now that we have modified User, add it back to the CSE maps. If it
5939 // already exists there, recursively merge the results together.
5940 AddModifiedNodeToCSEMaps(User);
5943 // If we just RAUW'd the root, take note.
5944 if (From == getRoot())
5949 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5950 /// to record information about a use.
5957 /// operator< - Sort Memos by User.
5958 bool operator<(const UseMemo &L, const UseMemo &R) {
5959 return (intptr_t)L.User < (intptr_t)R.User;
5963 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5964 /// uses of other values produced by From.getNode() alone. The same value
5965 /// may appear in both the From and To list. The Deleted vector is
5966 /// handled the same way as for ReplaceAllUsesWith.
5967 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5970 // Handle the simple, trivial case efficiently.
5972 return ReplaceAllUsesOfValueWith(*From, *To);
5974 // Read up all the uses and make records of them. This helps
5975 // processing new uses that are introduced during the
5976 // replacement process.
5977 SmallVector<UseMemo, 4> Uses;
5978 for (unsigned i = 0; i != Num; ++i) {
5979 unsigned FromResNo = From[i].getResNo();
5980 SDNode *FromNode = From[i].getNode();
5981 for (SDNode::use_iterator UI = FromNode->use_begin(),
5982 E = FromNode->use_end(); UI != E; ++UI) {
5983 SDUse &Use = UI.getUse();
5984 if (Use.getResNo() == FromResNo) {
5985 UseMemo Memo = { *UI, i, &Use };
5986 Uses.push_back(Memo);
5991 // Sort the uses, so that all the uses from a given User are together.
5992 std::sort(Uses.begin(), Uses.end());
5994 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5995 UseIndex != UseIndexEnd; ) {
5996 // We know that this user uses some value of From. If it is the right
5997 // value, update it.
5998 SDNode *User = Uses[UseIndex].User;
6000 // This node is about to morph, remove its old self from the CSE maps.
6001 RemoveNodeFromCSEMaps(User);
6003 // The Uses array is sorted, so all the uses for a given User
6004 // are next to each other in the list.
6005 // To help reduce the number of CSE recomputations, process all
6006 // the uses of this user that we can find this way.
6008 unsigned i = Uses[UseIndex].Index;
6009 SDUse &Use = *Uses[UseIndex].Use;
6013 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6015 // Now that we have modified User, add it back to the CSE maps. If it
6016 // already exists there, recursively merge the results together.
6017 AddModifiedNodeToCSEMaps(User);
6021 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6022 /// based on their topological order. It returns the maximum id and a vector
6023 /// of the SDNodes* in assigned order by reference.
6024 unsigned SelectionDAG::AssignTopologicalOrder() {
6026 unsigned DAGSize = 0;
6028 // SortedPos tracks the progress of the algorithm. Nodes before it are
6029 // sorted, nodes after it are unsorted. When the algorithm completes
6030 // it is at the end of the list.
6031 allnodes_iterator SortedPos = allnodes_begin();
6033 // Visit all the nodes. Move nodes with no operands to the front of
6034 // the list immediately. Annotate nodes that do have operands with their
6035 // operand count. Before we do this, the Node Id fields of the nodes
6036 // may contain arbitrary values. After, the Node Id fields for nodes
6037 // before SortedPos will contain the topological sort index, and the
6038 // Node Id fields for nodes At SortedPos and after will contain the
6039 // count of outstanding operands.
6040 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6042 checkForCycles(N, this);
6043 unsigned Degree = N->getNumOperands();
6045 // A node with no uses, add it to the result array immediately.
6046 N->setNodeId(DAGSize++);
6047 allnodes_iterator Q = N;
6049 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6050 assert(SortedPos != AllNodes.end() && "Overran node list");
6053 // Temporarily use the Node Id as scratch space for the degree count.
6054 N->setNodeId(Degree);
6058 // Visit all the nodes. As we iterate, move nodes into sorted order,
6059 // such that by the time the end is reached all nodes will be sorted.
6060 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6062 checkForCycles(N, this);
6063 // N is in sorted position, so all its uses have one less operand
6064 // that needs to be sorted.
6065 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6068 unsigned Degree = P->getNodeId();
6069 assert(Degree != 0 && "Invalid node degree");
6072 // All of P's operands are sorted, so P may sorted now.
6073 P->setNodeId(DAGSize++);
6075 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6076 assert(SortedPos != AllNodes.end() && "Overran node list");
6079 // Update P's outstanding operand count.
6080 P->setNodeId(Degree);
6083 if (I == SortedPos) {
6086 dbgs() << "Overran sorted position:\n";
6087 S->dumprFull(this); dbgs() << "\n";
6088 dbgs() << "Checking if this is due to cycles\n";
6089 checkForCycles(this, true);
6091 llvm_unreachable(nullptr);
6095 assert(SortedPos == AllNodes.end() &&
6096 "Topological sort incomplete!");
6097 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6098 "First node in topological sort is not the entry token!");
6099 assert(AllNodes.front().getNodeId() == 0 &&
6100 "First node in topological sort has non-zero id!");
6101 assert(AllNodes.front().getNumOperands() == 0 &&
6102 "First node in topological sort has operands!");
6103 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6104 "Last node in topologic sort has unexpected id!");
6105 assert(AllNodes.back().use_empty() &&
6106 "Last node in topologic sort has users!");
6107 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6111 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6112 /// value is produced by SD.
6113 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6114 DbgInfo->add(DB, SD, isParameter);
6116 SD->setHasDebugValue(true);
6119 /// TransferDbgValues - Transfer SDDbgValues.
6120 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6121 if (From == To || !From.getNode()->getHasDebugValue())
6123 SDNode *FromNode = From.getNode();
6124 SDNode *ToNode = To.getNode();
6125 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6126 SmallVector<SDDbgValue *, 2> ClonedDVs;
6127 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6129 SDDbgValue *Dbg = *I;
6130 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6131 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6133 Dbg->getOffset(), Dbg->getDebugLoc(),
6135 ClonedDVs.push_back(Clone);
6138 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6139 E = ClonedDVs.end(); I != E; ++I)
6140 AddDbgValue(*I, ToNode, false);
6143 //===----------------------------------------------------------------------===//
6145 //===----------------------------------------------------------------------===//
6147 HandleSDNode::~HandleSDNode() {
6151 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6152 DebugLoc DL, const GlobalValue *GA,
6153 EVT VT, int64_t o, unsigned char TF)
6154 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6158 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6159 SDValue X, unsigned SrcAS,
6161 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6162 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6164 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6165 EVT memvt, MachineMemOperand *mmo)
6166 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6167 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6168 MMO->isNonTemporal(), MMO->isInvariant());
6169 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6170 assert(isNonTemporal() == MMO->isNonTemporal() &&
6171 "Non-temporal encoding error!");
6172 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6175 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6176 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6177 : SDNode(Opc, Order, dl, VTs, Ops),
6178 MemoryVT(memvt), MMO(mmo) {
6179 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6180 MMO->isNonTemporal(), MMO->isInvariant());
6181 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6182 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6185 /// Profile - Gather unique data for the node.
6187 void SDNode::Profile(FoldingSetNodeID &ID) const {
6188 AddNodeIDNode(ID, this);
6193 std::vector<EVT> VTs;
6196 VTs.reserve(MVT::LAST_VALUETYPE);
6197 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6198 VTs.push_back(MVT((MVT::SimpleValueType)i));
6203 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6204 static ManagedStatic<EVTArray> SimpleVTArray;
6205 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6207 /// getValueTypeList - Return a pointer to the specified value type.
6209 const EVT *SDNode::getValueTypeList(EVT VT) {
6210 if (VT.isExtended()) {
6211 sys::SmartScopedLock<true> Lock(*VTMutex);
6212 return &(*EVTs->insert(VT).first);
6214 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6215 "Value type out of range!");
6216 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6220 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6221 /// indicated value. This method ignores uses of other values defined by this
6223 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6224 assert(Value < getNumValues() && "Bad value!");
6226 // TODO: Only iterate over uses of a given value of the node
6227 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6228 if (UI.getUse().getResNo() == Value) {
6235 // Found exactly the right number of uses?
6240 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6241 /// value. This method ignores uses of other values defined by this operation.
6242 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6243 assert(Value < getNumValues() && "Bad value!");
6245 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6246 if (UI.getUse().getResNo() == Value)
6253 /// isOnlyUserOf - Return true if this node is the only use of N.
6255 bool SDNode::isOnlyUserOf(SDNode *N) const {
6257 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6268 /// isOperand - Return true if this node is an operand of N.
6270 bool SDValue::isOperandOf(SDNode *N) const {
6271 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6272 if (*this == N->getOperand(i))
6277 bool SDNode::isOperandOf(SDNode *N) const {
6278 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6279 if (this == N->OperandList[i].getNode())
6284 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6285 /// be a chain) reaches the specified operand without crossing any
6286 /// side-effecting instructions on any chain path. In practice, this looks
6287 /// through token factors and non-volatile loads. In order to remain efficient,
6288 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6289 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6290 unsigned Depth) const {
6291 if (*this == Dest) return true;
6293 // Don't search too deeply, we just want to be able to see through
6294 // TokenFactor's etc.
6295 if (Depth == 0) return false;
6297 // If this is a token factor, all inputs to the TF happen in parallel. If any
6298 // of the operands of the TF does not reach dest, then we cannot do the xform.
6299 if (getOpcode() == ISD::TokenFactor) {
6300 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6301 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6306 // Loads don't have side effects, look through them.
6307 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6308 if (!Ld->isVolatile())
6309 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6314 /// hasPredecessor - Return true if N is a predecessor of this node.
6315 /// N is either an operand of this node, or can be reached by recursively
6316 /// traversing up the operands.
6317 /// NOTE: This is an expensive method. Use it carefully.
6318 bool SDNode::hasPredecessor(const SDNode *N) const {
6319 SmallPtrSet<const SDNode *, 32> Visited;
6320 SmallVector<const SDNode *, 16> Worklist;
6321 return hasPredecessorHelper(N, Visited, Worklist);
6325 SDNode::hasPredecessorHelper(const SDNode *N,
6326 SmallPtrSet<const SDNode *, 32> &Visited,
6327 SmallVectorImpl<const SDNode *> &Worklist) const {
6328 if (Visited.empty()) {
6329 Worklist.push_back(this);
6331 // Take a look in the visited set. If we've already encountered this node
6332 // we needn't search further.
6333 if (Visited.count(N))
6337 // Haven't visited N yet. Continue the search.
6338 while (!Worklist.empty()) {
6339 const SDNode *M = Worklist.pop_back_val();
6340 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6341 SDNode *Op = M->getOperand(i).getNode();
6342 if (Visited.insert(Op))
6343 Worklist.push_back(Op);
6352 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6353 assert(Num < NumOperands && "Invalid child # of SDNode!");
6354 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6357 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6358 assert(N->getNumValues() == 1 &&
6359 "Can't unroll a vector with multiple results!");
6361 EVT VT = N->getValueType(0);
6362 unsigned NE = VT.getVectorNumElements();
6363 EVT EltVT = VT.getVectorElementType();
6366 SmallVector<SDValue, 8> Scalars;
6367 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6369 // If ResNE is 0, fully unroll the vector op.
6372 else if (NE > ResNE)
6376 for (i= 0; i != NE; ++i) {
6377 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6378 SDValue Operand = N->getOperand(j);
6379 EVT OperandVT = Operand.getValueType();
6380 if (OperandVT.isVector()) {
6381 // A vector operand; extract a single element.
6382 const TargetLowering *TLI = TM.getTargetLowering();
6383 EVT OperandEltVT = OperandVT.getVectorElementType();
6384 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6387 getConstant(i, TLI->getVectorIdxTy()));
6389 // A scalar operand; just use it as is.
6390 Operands[j] = Operand;
6394 switch (N->getOpcode()) {
6396 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6399 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6406 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6407 getShiftAmountOperand(Operands[0].getValueType(),
6410 case ISD::SIGN_EXTEND_INREG:
6411 case ISD::FP_ROUND_INREG: {
6412 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6413 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6415 getValueType(ExtVT)));
6420 for (; i < ResNE; ++i)
6421 Scalars.push_back(getUNDEF(EltVT));
6423 return getNode(ISD::BUILD_VECTOR, dl,
6424 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6428 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6429 /// location that is 'Dist' units away from the location that the 'Base' load
6430 /// is loading from.
6431 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6432 unsigned Bytes, int Dist) const {
6433 if (LD->getChain() != Base->getChain())
6435 EVT VT = LD->getValueType(0);
6436 if (VT.getSizeInBits() / 8 != Bytes)
6439 SDValue Loc = LD->getOperand(1);
6440 SDValue BaseLoc = Base->getOperand(1);
6441 if (Loc.getOpcode() == ISD::FrameIndex) {
6442 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6444 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6445 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6446 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6447 int FS = MFI->getObjectSize(FI);
6448 int BFS = MFI->getObjectSize(BFI);
6449 if (FS != BFS || FS != (int)Bytes) return false;
6450 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6454 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6455 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6458 const GlobalValue *GV1 = nullptr;
6459 const GlobalValue *GV2 = nullptr;
6460 int64_t Offset1 = 0;
6461 int64_t Offset2 = 0;
6462 const TargetLowering *TLI = TM.getTargetLowering();
6463 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6464 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6465 if (isGA1 && isGA2 && GV1 == GV2)
6466 return Offset1 == (Offset2 + Dist*Bytes);
6471 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6472 /// it cannot be inferred.
6473 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6474 // If this is a GlobalAddress + cst, return the alignment.
6475 const GlobalValue *GV;
6476 int64_t GVOffset = 0;
6477 const TargetLowering *TLI = TM.getTargetLowering();
6478 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6479 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6480 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6481 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6482 TLI->getDataLayout());
6483 unsigned AlignBits = KnownZero.countTrailingOnes();
6484 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6486 return MinAlign(Align, GVOffset);
6489 // If this is a direct reference to a stack slot, use information about the
6490 // stack slot's alignment.
6491 int FrameIdx = 1 << 31;
6492 int64_t FrameOffset = 0;
6493 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6494 FrameIdx = FI->getIndex();
6495 } else if (isBaseWithConstantOffset(Ptr) &&
6496 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6498 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6499 FrameOffset = Ptr.getConstantOperandVal(1);
6502 if (FrameIdx != (1 << 31)) {
6503 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6504 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6512 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6513 /// which is split (or expanded) into two not necessarily identical pieces.
6514 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6515 // Currently all types are split in half.
6517 if (!VT.isVector()) {
6518 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6520 unsigned NumElements = VT.getVectorNumElements();
6521 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6522 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6525 return std::make_pair(LoVT, HiVT);
6528 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6530 std::pair<SDValue, SDValue>
6531 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6533 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6534 N.getValueType().getVectorNumElements() &&
6535 "More vector elements requested than available!");
6537 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6538 getConstant(0, TLI->getVectorIdxTy()));
6539 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6540 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6541 return std::make_pair(Lo, Hi);
6544 void SelectionDAG::ExtractVectorElements(SDValue Op,
6545 SmallVectorImpl<SDValue> &Args,
6546 unsigned Start, unsigned Count) {
6547 EVT VT = Op.getValueType();
6549 Count = VT.getVectorNumElements();
6551 EVT EltVT = VT.getVectorElementType();
6552 EVT IdxTy = TLI->getVectorIdxTy();
6554 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6555 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6556 Op, getConstant(i, IdxTy)));
6560 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6561 unsigned GlobalAddressSDNode::getAddressSpace() const {
6562 return getGlobal()->getType()->getAddressSpace();
6566 Type *ConstantPoolSDNode::getType() const {
6567 if (isMachineConstantPoolEntry())
6568 return Val.MachineCPVal->getType();
6569 return Val.ConstVal->getType();
6572 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6574 unsigned &SplatBitSize,
6576 unsigned MinSplatBits,
6577 bool isBigEndian) const {
6578 EVT VT = getValueType(0);
6579 assert(VT.isVector() && "Expected a vector type");
6580 unsigned sz = VT.getSizeInBits();
6581 if (MinSplatBits > sz)
6584 SplatValue = APInt(sz, 0);
6585 SplatUndef = APInt(sz, 0);
6587 // Get the bits. Bits with undefined values (when the corresponding element
6588 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6589 // in SplatValue. If any of the values are not constant, give up and return
6591 unsigned int nOps = getNumOperands();
6592 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6593 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6595 for (unsigned j = 0; j < nOps; ++j) {
6596 unsigned i = isBigEndian ? nOps-1-j : j;
6597 SDValue OpVal = getOperand(i);
6598 unsigned BitPos = j * EltBitSize;
6600 if (OpVal.getOpcode() == ISD::UNDEF)
6601 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6602 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6603 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6604 zextOrTrunc(sz) << BitPos;
6605 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6606 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6611 // The build_vector is all constants or undefs. Find the smallest element
6612 // size that splats the vector.
6614 HasAnyUndefs = (SplatUndef != 0);
6617 unsigned HalfSize = sz / 2;
6618 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6619 APInt LowValue = SplatValue.trunc(HalfSize);
6620 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6621 APInt LowUndef = SplatUndef.trunc(HalfSize);
6623 // If the two halves do not match (ignoring undef bits), stop here.
6624 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6625 MinSplatBits > HalfSize)
6628 SplatValue = HighValue | LowValue;
6629 SplatUndef = HighUndef & LowUndef;
6638 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6639 if (UndefElements) {
6640 UndefElements->clear();
6641 UndefElements->resize(getNumOperands());
6644 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6645 SDValue Op = getOperand(i);
6646 if (Op.getOpcode() == ISD::UNDEF) {
6648 (*UndefElements)[i] = true;
6649 } else if (!Splatted) {
6651 } else if (Splatted != Op) {
6657 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6658 "Can only have a splat without a constant for all undefs.");
6659 return getOperand(0);
6666 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6667 return dyn_cast_or_null<ConstantSDNode>(
6668 getSplatValue(UndefElements).getNode());
6672 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6673 return dyn_cast_or_null<ConstantFPSDNode>(
6674 getSplatValue(UndefElements).getNode());
6677 bool BuildVectorSDNode::isConstant() const {
6678 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6679 unsigned Opc = getOperand(i).getOpcode();
6680 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6686 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6687 // Find the first non-undef value in the shuffle mask.
6689 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6692 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6694 // Make sure all remaining elements are either undef or the same as the first
6696 for (int Idx = Mask[i]; i != e; ++i)
6697 if (Mask[i] >= 0 && Mask[i] != Idx)
6703 static void checkForCyclesHelper(const SDNode *N,
6704 SmallPtrSet<const SDNode*, 32> &Visited,
6705 SmallPtrSet<const SDNode*, 32> &Checked,
6706 const llvm::SelectionDAG *DAG) {
6707 // If this node has already been checked, don't check it again.
6708 if (Checked.count(N))
6711 // If a node has already been visited on this depth-first walk, reject it as
6713 if (!Visited.insert(N)) {
6714 errs() << "Detected cycle in SelectionDAG\n";
6715 dbgs() << "Offending node:\n";
6716 N->dumprFull(DAG); dbgs() << "\n";
6720 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6721 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6728 void llvm::checkForCycles(const llvm::SDNode *N,
6729 const llvm::SelectionDAG *DAG,
6737 assert(N && "Checking nonexistent SDNode");
6738 SmallPtrSet<const SDNode*, 32> visited;
6739 SmallPtrSet<const SDNode*, 32> checked;
6740 checkForCyclesHelper(N, visited, checked, DAG);
6745 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6746 checkForCycles(DAG->getRoot().getNode(), DAG, force);