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 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
844 static void VerifySDNode(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");
882 /// getEVTAlignment - Compute the default alignment value for the
885 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
886 Type *Ty = VT == MVT::iPTR ?
887 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
888 VT.getTypeForEVT(*getContext());
890 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
893 // EntryNode could meaningfully have debug info if we can find it...
894 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
895 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
896 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
897 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
898 UpdateListeners(nullptr) {
899 AllNodes.push_back(&EntryNode);
900 DbgInfo = new SDDbgInfo();
903 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
906 Context = &mf.getFunction()->getContext();
909 SelectionDAG::~SelectionDAG() {
910 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
915 void SelectionDAG::allnodes_clear() {
916 assert(&*AllNodes.begin() == &EntryNode);
917 AllNodes.remove(AllNodes.begin());
918 while (!AllNodes.empty())
919 DeallocateNode(AllNodes.begin());
922 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
923 SDVTList VTs, SDValue N1,
924 SDValue N2, bool nuw, bool nsw,
926 if (isBinOpWithFlags(Opcode)) {
927 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
928 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
929 FN->setHasNoUnsignedWrap(nuw);
930 FN->setHasNoSignedWrap(nsw);
931 FN->setIsExact(exact);
936 BinarySDNode *N = new (NodeAllocator)
937 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
941 void SelectionDAG::clear() {
943 OperandAllocator.Reset();
946 ExtendedValueTypeNodes.clear();
947 ExternalSymbols.clear();
948 TargetExternalSymbols.clear();
949 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
950 static_cast<CondCodeSDNode*>(nullptr));
951 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
952 static_cast<SDNode*>(nullptr));
954 EntryNode.UseList = nullptr;
955 AllNodes.push_back(&EntryNode);
956 Root = getEntryNode();
960 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
961 return VT.bitsGT(Op.getValueType()) ?
962 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
963 getNode(ISD::TRUNCATE, DL, VT, Op);
966 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
967 return VT.bitsGT(Op.getValueType()) ?
968 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
969 getNode(ISD::TRUNCATE, DL, VT, Op);
972 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
973 return VT.bitsGT(Op.getValueType()) ?
974 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
975 getNode(ISD::TRUNCATE, DL, VT, Op);
978 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
980 if (VT.bitsLE(Op.getValueType()))
981 return getNode(ISD::TRUNCATE, SL, VT, Op);
983 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
984 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
987 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
988 assert(!VT.isVector() &&
989 "getZeroExtendInReg should use the vector element type instead of "
991 if (Op.getValueType() == VT) return Op;
992 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
993 APInt Imm = APInt::getLowBitsSet(BitWidth,
995 return getNode(ISD::AND, DL, Op.getValueType(), Op,
996 getConstant(Imm, Op.getValueType()));
999 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1000 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1001 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1002 "The sizes of the input and result must match in order to perform the "
1003 "extend in-register.");
1004 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1005 "The destination vector type must have fewer lanes than the input.");
1006 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1009 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1010 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1011 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1012 "The sizes of the input and result must match in order to perform the "
1013 "extend in-register.");
1014 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1015 "The destination vector type must have fewer lanes than the input.");
1016 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1019 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1020 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1021 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1022 "The sizes of the input and result must match in order to perform the "
1023 "extend in-register.");
1024 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1025 "The destination vector type must have fewer lanes than the input.");
1026 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1029 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1031 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1032 EVT EltVT = VT.getScalarType();
1034 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1035 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1038 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1039 EVT EltVT = VT.getScalarType();
1041 switch (TLI->getBooleanContents(VT)) {
1042 case TargetLowering::ZeroOrOneBooleanContent:
1043 case TargetLowering::UndefinedBooleanContent:
1044 TrueValue = getConstant(1, VT);
1046 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1047 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1051 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1054 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1055 EVT EltVT = VT.getScalarType();
1056 assert((EltVT.getSizeInBits() >= 64 ||
1057 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1058 "getConstant with a uint64_t value that doesn't fit in the type!");
1059 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1062 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1064 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1067 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1069 assert(VT.isInteger() && "Cannot create FP integer constant!");
1071 EVT EltVT = VT.getScalarType();
1072 const ConstantInt *Elt = &Val;
1074 const TargetLowering *TLI = TM.getTargetLowering();
1076 // In some cases the vector type is legal but the element type is illegal and
1077 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1078 // inserted value (the type does not need to match the vector element type).
1079 // Any extra bits introduced will be truncated away.
1080 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1081 TargetLowering::TypePromoteInteger) {
1082 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1083 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1084 Elt = ConstantInt::get(*getContext(), NewVal);
1086 // In other cases the element type is illegal and needs to be expanded, for
1087 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1088 // the value into n parts and use a vector type with n-times the elements.
1089 // Then bitcast to the type requested.
1090 // Legalizing constants too early makes the DAGCombiner's job harder so we
1091 // only legalize if the DAG tells us we must produce legal types.
1092 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1093 TLI->getTypeAction(*getContext(), EltVT) ==
1094 TargetLowering::TypeExpandInteger) {
1095 APInt NewVal = Elt->getValue();
1096 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1097 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1098 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1099 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1101 // Check the temporary vector is the correct size. If this fails then
1102 // getTypeToTransformTo() probably returned a type whose size (in bits)
1103 // isn't a power-of-2 factor of the requested type size.
1104 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1106 SmallVector<SDValue, 2> EltParts;
1107 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1108 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1109 .trunc(ViaEltSizeInBits),
1110 ViaEltVT, isT, isO));
1113 // EltParts is currently in little endian order. If we actually want
1114 // big-endian order then reverse it now.
1115 if (TLI->isBigEndian())
1116 std::reverse(EltParts.begin(), EltParts.end());
1118 // The elements must be reversed when the element order is different
1119 // to the endianness of the elements (because the BITCAST is itself a
1120 // vector shuffle in this situation). However, we do not need any code to
1121 // perform this reversal because getConstant() is producing a vector
1123 // This situation occurs in MIPS MSA.
1125 SmallVector<SDValue, 8> Ops;
1126 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1127 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1129 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1130 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1135 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1136 "APInt size does not match type size!");
1137 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1138 FoldingSetNodeID ID;
1139 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1143 SDNode *N = nullptr;
1144 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1146 return SDValue(N, 0);
1149 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1150 CSEMap.InsertNode(N, IP);
1151 AllNodes.push_back(N);
1154 SDValue Result(N, 0);
1155 if (VT.isVector()) {
1156 SmallVector<SDValue, 8> Ops;
1157 Ops.assign(VT.getVectorNumElements(), Result);
1158 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1163 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1164 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1168 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1169 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1172 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1173 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1175 EVT EltVT = VT.getScalarType();
1177 // Do the map lookup using the actual bit pattern for the floating point
1178 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1179 // we don't have issues with SNANs.
1180 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1181 FoldingSetNodeID ID;
1182 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1185 SDNode *N = nullptr;
1186 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1188 return SDValue(N, 0);
1191 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1192 CSEMap.InsertNode(N, IP);
1193 AllNodes.push_back(N);
1196 SDValue Result(N, 0);
1197 if (VT.isVector()) {
1198 SmallVector<SDValue, 8> Ops;
1199 Ops.assign(VT.getVectorNumElements(), Result);
1200 // FIXME SDLoc info might be appropriate here
1201 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1206 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1207 EVT EltVT = VT.getScalarType();
1208 if (EltVT==MVT::f32)
1209 return getConstantFP(APFloat((float)Val), VT, isTarget);
1210 else if (EltVT==MVT::f64)
1211 return getConstantFP(APFloat(Val), VT, isTarget);
1212 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1215 APFloat apf = APFloat(Val);
1216 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1218 return getConstantFP(apf, VT, isTarget);
1220 llvm_unreachable("Unsupported type in getConstantFP");
1223 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1224 EVT VT, int64_t Offset,
1226 unsigned char TargetFlags) {
1227 assert((TargetFlags == 0 || isTargetGA) &&
1228 "Cannot set target flags on target-independent globals");
1229 const TargetLowering *TLI = TM.getTargetLowering();
1231 // Truncate (with sign-extension) the offset value to the pointer size.
1232 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1234 Offset = SignExtend64(Offset, BitWidth);
1237 if (GV->isThreadLocal())
1238 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1240 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1242 FoldingSetNodeID ID;
1243 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1245 ID.AddInteger(Offset);
1246 ID.AddInteger(TargetFlags);
1247 ID.AddInteger(GV->getType()->getAddressSpace());
1249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1250 return SDValue(E, 0);
1252 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1253 DL.getDebugLoc(), GV, VT,
1254 Offset, TargetFlags);
1255 CSEMap.InsertNode(N, IP);
1256 AllNodes.push_back(N);
1257 return SDValue(N, 0);
1260 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1261 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1262 FoldingSetNodeID ID;
1263 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1266 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1267 return SDValue(E, 0);
1269 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1270 CSEMap.InsertNode(N, IP);
1271 AllNodes.push_back(N);
1272 return SDValue(N, 0);
1275 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1276 unsigned char TargetFlags) {
1277 assert((TargetFlags == 0 || isTarget) &&
1278 "Cannot set target flags on target-independent jump tables");
1279 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1280 FoldingSetNodeID ID;
1281 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1283 ID.AddInteger(TargetFlags);
1285 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1286 return SDValue(E, 0);
1288 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1290 CSEMap.InsertNode(N, IP);
1291 AllNodes.push_back(N);
1292 return SDValue(N, 0);
1295 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1296 unsigned Alignment, int Offset,
1298 unsigned char TargetFlags) {
1299 assert((TargetFlags == 0 || isTarget) &&
1300 "Cannot set target flags on target-independent globals");
1303 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1304 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1305 FoldingSetNodeID ID;
1306 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1307 ID.AddInteger(Alignment);
1308 ID.AddInteger(Offset);
1310 ID.AddInteger(TargetFlags);
1312 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1313 return SDValue(E, 0);
1315 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1316 Alignment, TargetFlags);
1317 CSEMap.InsertNode(N, IP);
1318 AllNodes.push_back(N);
1319 return SDValue(N, 0);
1323 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1324 unsigned Alignment, int Offset,
1326 unsigned char TargetFlags) {
1327 assert((TargetFlags == 0 || isTarget) &&
1328 "Cannot set target flags on target-independent globals");
1331 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1332 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1333 FoldingSetNodeID ID;
1334 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1335 ID.AddInteger(Alignment);
1336 ID.AddInteger(Offset);
1337 C->addSelectionDAGCSEId(ID);
1338 ID.AddInteger(TargetFlags);
1340 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1341 return SDValue(E, 0);
1343 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1344 Alignment, TargetFlags);
1345 CSEMap.InsertNode(N, IP);
1346 AllNodes.push_back(N);
1347 return SDValue(N, 0);
1350 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1351 unsigned char TargetFlags) {
1352 FoldingSetNodeID ID;
1353 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1354 ID.AddInteger(Index);
1355 ID.AddInteger(Offset);
1356 ID.AddInteger(TargetFlags);
1358 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1359 return SDValue(E, 0);
1361 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1363 CSEMap.InsertNode(N, IP);
1364 AllNodes.push_back(N);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1369 FoldingSetNodeID ID;
1370 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1373 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1374 return SDValue(E, 0);
1376 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1377 CSEMap.InsertNode(N, IP);
1378 AllNodes.push_back(N);
1379 return SDValue(N, 0);
1382 SDValue SelectionDAG::getValueType(EVT VT) {
1383 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1384 ValueTypeNodes.size())
1385 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1387 SDNode *&N = VT.isExtended() ?
1388 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1390 if (N) return SDValue(N, 0);
1391 N = new (NodeAllocator) VTSDNode(VT);
1392 AllNodes.push_back(N);
1393 return SDValue(N, 0);
1396 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1397 SDNode *&N = ExternalSymbols[Sym];
1398 if (N) return SDValue(N, 0);
1399 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1400 AllNodes.push_back(N);
1401 return SDValue(N, 0);
1404 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1405 unsigned char TargetFlags) {
1407 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1409 if (N) return SDValue(N, 0);
1410 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1411 AllNodes.push_back(N);
1412 return SDValue(N, 0);
1415 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1416 if ((unsigned)Cond >= CondCodeNodes.size())
1417 CondCodeNodes.resize(Cond+1);
1419 if (!CondCodeNodes[Cond]) {
1420 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1421 CondCodeNodes[Cond] = N;
1422 AllNodes.push_back(N);
1425 return SDValue(CondCodeNodes[Cond], 0);
1428 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1429 // the shuffle mask M that point at N1 to point at N2, and indices that point
1430 // N2 to point at N1.
1431 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1433 int NElts = M.size();
1434 for (int i = 0; i != NElts; ++i) {
1442 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1443 SDValue N2, const int *Mask) {
1444 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1445 "Invalid VECTOR_SHUFFLE");
1447 // Canonicalize shuffle undef, undef -> undef
1448 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1449 return getUNDEF(VT);
1451 // Validate that all indices in Mask are within the range of the elements
1452 // input to the shuffle.
1453 unsigned NElts = VT.getVectorNumElements();
1454 SmallVector<int, 8> MaskVec;
1455 for (unsigned i = 0; i != NElts; ++i) {
1456 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1457 MaskVec.push_back(Mask[i]);
1460 // Canonicalize shuffle v, v -> v, undef
1463 for (unsigned i = 0; i != NElts; ++i)
1464 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1467 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1468 if (N1.getOpcode() == ISD::UNDEF)
1469 commuteShuffle(N1, N2, MaskVec);
1471 // Canonicalize all index into lhs, -> shuffle lhs, undef
1472 // Canonicalize all index into rhs, -> shuffle rhs, undef
1473 bool AllLHS = true, AllRHS = true;
1474 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1475 for (unsigned i = 0; i != NElts; ++i) {
1476 if (MaskVec[i] >= (int)NElts) {
1481 } else if (MaskVec[i] >= 0) {
1485 if (AllLHS && AllRHS)
1486 return getUNDEF(VT);
1487 if (AllLHS && !N2Undef)
1491 commuteShuffle(N1, N2, MaskVec);
1493 // Reset our undef status after accounting for the mask.
1494 N2Undef = N2.getOpcode() == ISD::UNDEF;
1495 // Re-check whether both sides ended up undef.
1496 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1497 return getUNDEF(VT);
1499 // If Identity shuffle return that node.
1500 bool Identity = true;
1501 for (unsigned i = 0; i != NElts; ++i) {
1502 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1504 if (Identity && NElts)
1507 // Shuffling a constant splat doesn't change the result.
1511 // Look through any bitcasts. We check that these don't change the number
1512 // (and size) of elements and just changes their types.
1513 while (V.getOpcode() == ISD::BITCAST)
1514 V = V->getOperand(0);
1516 // A splat should always show up as a build vector node.
1517 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1518 BitVector UndefElements;
1519 SDValue Splat = BV->getSplatValue(&UndefElements);
1520 // If this is a splat of an undef, shuffling it is also undef.
1521 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1522 return getUNDEF(VT);
1524 // We only have a splat which can skip shuffles if there is a splatted
1525 // value and no undef lanes rearranged by the shuffle.
1526 if (Splat && UndefElements.none()) {
1527 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1528 // number of elements match or the value splatted is a zero constant.
1529 if (V.getValueType().getVectorNumElements() ==
1530 VT.getVectorNumElements())
1532 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1533 if (C->isNullValue())
1539 FoldingSetNodeID ID;
1540 SDValue Ops[2] = { N1, N2 };
1541 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1542 for (unsigned i = 0; i != NElts; ++i)
1543 ID.AddInteger(MaskVec[i]);
1546 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1547 return SDValue(E, 0);
1549 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1550 // SDNode doesn't have access to it. This memory will be "leaked" when
1551 // the node is deallocated, but recovered when the NodeAllocator is released.
1552 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1553 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1555 ShuffleVectorSDNode *N =
1556 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1557 dl.getDebugLoc(), N1, N2,
1559 CSEMap.InsertNode(N, IP);
1560 AllNodes.push_back(N);
1561 return SDValue(N, 0);
1564 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1565 MVT VT = SV.getSimpleValueType(0);
1566 unsigned NumElems = VT.getVectorNumElements();
1567 SmallVector<int, 8> MaskVec;
1569 for (unsigned i = 0; i != NumElems; ++i) {
1570 int Idx = SV.getMaskElt(i);
1572 if (Idx < (int)NumElems)
1577 MaskVec.push_back(Idx);
1580 SDValue Op0 = SV.getOperand(0);
1581 SDValue Op1 = SV.getOperand(1);
1582 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1585 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1586 SDValue Val, SDValue DTy,
1587 SDValue STy, SDValue Rnd, SDValue Sat,
1588 ISD::CvtCode Code) {
1589 // If the src and dest types are the same and the conversion is between
1590 // integer types of the same sign or two floats, no conversion is necessary.
1592 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1595 FoldingSetNodeID ID;
1596 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1597 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1599 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1600 return SDValue(E, 0);
1602 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1605 CSEMap.InsertNode(N, IP);
1606 AllNodes.push_back(N);
1607 return SDValue(N, 0);
1610 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1611 FoldingSetNodeID ID;
1612 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1613 ID.AddInteger(RegNo);
1615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1616 return SDValue(E, 0);
1618 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1619 CSEMap.InsertNode(N, IP);
1620 AllNodes.push_back(N);
1621 return SDValue(N, 0);
1624 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1625 FoldingSetNodeID ID;
1626 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1627 ID.AddPointer(RegMask);
1629 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1630 return SDValue(E, 0);
1632 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1633 CSEMap.InsertNode(N, IP);
1634 AllNodes.push_back(N);
1635 return SDValue(N, 0);
1638 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1639 FoldingSetNodeID ID;
1640 SDValue Ops[] = { Root };
1641 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1642 ID.AddPointer(Label);
1644 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1645 return SDValue(E, 0);
1647 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1648 dl.getDebugLoc(), Root, Label);
1649 CSEMap.InsertNode(N, IP);
1650 AllNodes.push_back(N);
1651 return SDValue(N, 0);
1655 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1658 unsigned char TargetFlags) {
1659 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1661 FoldingSetNodeID ID;
1662 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1664 ID.AddInteger(Offset);
1665 ID.AddInteger(TargetFlags);
1667 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1668 return SDValue(E, 0);
1670 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1672 CSEMap.InsertNode(N, IP);
1673 AllNodes.push_back(N);
1674 return SDValue(N, 0);
1677 SDValue SelectionDAG::getSrcValue(const Value *V) {
1678 assert((!V || V->getType()->isPointerTy()) &&
1679 "SrcValue is not a pointer?");
1681 FoldingSetNodeID ID;
1682 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1686 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1687 return SDValue(E, 0);
1689 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1690 CSEMap.InsertNode(N, IP);
1691 AllNodes.push_back(N);
1692 return SDValue(N, 0);
1695 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1696 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1697 FoldingSetNodeID ID;
1698 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1702 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1703 return SDValue(E, 0);
1705 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1706 CSEMap.InsertNode(N, IP);
1707 AllNodes.push_back(N);
1708 return SDValue(N, 0);
1711 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1712 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1713 unsigned SrcAS, unsigned DestAS) {
1714 SDValue Ops[] = {Ptr};
1715 FoldingSetNodeID ID;
1716 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1717 ID.AddInteger(SrcAS);
1718 ID.AddInteger(DestAS);
1721 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1722 return SDValue(E, 0);
1724 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1726 VT, Ptr, SrcAS, DestAS);
1727 CSEMap.InsertNode(N, IP);
1728 AllNodes.push_back(N);
1729 return SDValue(N, 0);
1732 /// getShiftAmountOperand - Return the specified value casted to
1733 /// the target's desired shift amount type.
1734 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1735 EVT OpTy = Op.getValueType();
1736 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1737 if (OpTy == ShTy || OpTy.isVector()) return Op;
1739 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1740 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1743 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1744 /// specified value type.
1745 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1746 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1747 unsigned ByteSize = VT.getStoreSize();
1748 Type *Ty = VT.getTypeForEVT(*getContext());
1749 const TargetLowering *TLI = TM.getTargetLowering();
1750 unsigned StackAlign =
1751 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1753 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1754 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1757 /// CreateStackTemporary - Create a stack temporary suitable for holding
1758 /// either of the specified value types.
1759 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1760 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1761 VT2.getStoreSizeInBits())/8;
1762 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1763 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1764 const TargetLowering *TLI = TM.getTargetLowering();
1765 const DataLayout *TD = TLI->getDataLayout();
1766 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1767 TD->getPrefTypeAlignment(Ty2));
1769 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1770 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1771 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1774 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1775 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1776 // These setcc operations always fold.
1780 case ISD::SETFALSE2: return getConstant(0, VT);
1782 case ISD::SETTRUE2: {
1783 const TargetLowering *TLI = TM.getTargetLowering();
1784 TargetLowering::BooleanContent Cnt =
1785 TLI->getBooleanContents(N1->getValueType(0));
1787 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1800 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1804 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1805 const APInt &C2 = N2C->getAPIntValue();
1806 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1807 const APInt &C1 = N1C->getAPIntValue();
1810 default: llvm_unreachable("Unknown integer setcc!");
1811 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1812 case ISD::SETNE: return getConstant(C1 != C2, VT);
1813 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1814 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1815 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1816 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1817 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1818 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1819 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1820 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1824 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1825 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1826 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1829 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1830 return getUNDEF(VT);
1832 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1833 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1834 return getUNDEF(VT);
1836 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1837 R==APFloat::cmpLessThan, VT);
1838 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1839 return getUNDEF(VT);
1841 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1842 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1843 return getUNDEF(VT);
1845 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1846 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1847 return getUNDEF(VT);
1849 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1850 R==APFloat::cmpEqual, VT);
1851 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1852 return getUNDEF(VT);
1854 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1855 R==APFloat::cmpEqual, VT);
1856 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1857 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1858 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1859 R==APFloat::cmpEqual, VT);
1860 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1861 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1862 R==APFloat::cmpLessThan, VT);
1863 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1864 R==APFloat::cmpUnordered, VT);
1865 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1866 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1869 // Ensure that the constant occurs on the RHS.
1870 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1871 MVT CompVT = N1.getValueType().getSimpleVT();
1872 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1875 return getSetCC(dl, VT, N2, N1, SwappedCond);
1879 // Could not fold it.
1883 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1884 /// use this predicate to simplify operations downstream.
1885 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1886 // This predicate is not safe for vector operations.
1887 if (Op.getValueType().isVector())
1890 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1891 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1894 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1895 /// this predicate to simplify operations downstream. Mask is known to be zero
1896 /// for bits that V cannot have.
1897 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1898 unsigned Depth) const {
1899 APInt KnownZero, KnownOne;
1900 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1901 return (KnownZero & Mask) == Mask;
1904 /// Determine which bits of Op are known to be either zero or one and return
1905 /// them in the KnownZero/KnownOne bitsets.
1906 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1907 APInt &KnownOne, unsigned Depth) const {
1908 const TargetLowering *TLI = TM.getTargetLowering();
1909 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1911 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1913 return; // Limit search depth.
1915 APInt KnownZero2, KnownOne2;
1917 switch (Op.getOpcode()) {
1919 // We know all of the bits for a constant!
1920 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1921 KnownZero = ~KnownOne;
1924 // If either the LHS or the RHS are Zero, the result is zero.
1925 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1926 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1928 // Output known-1 bits are only known if set in both the LHS & RHS.
1929 KnownOne &= KnownOne2;
1930 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1931 KnownZero |= KnownZero2;
1934 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1935 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1937 // Output known-0 bits are only known if clear in both the LHS & RHS.
1938 KnownZero &= KnownZero2;
1939 // Output known-1 are known to be set if set in either the LHS | RHS.
1940 KnownOne |= KnownOne2;
1943 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1944 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1946 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1947 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1948 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1949 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1950 KnownZero = KnownZeroOut;
1954 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1955 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1957 // If low bits are zero in either operand, output low known-0 bits.
1958 // Also compute a conserative estimate for high known-0 bits.
1959 // More trickiness is possible, but this is sufficient for the
1960 // interesting case of alignment computation.
1961 KnownOne.clearAllBits();
1962 unsigned TrailZ = KnownZero.countTrailingOnes() +
1963 KnownZero2.countTrailingOnes();
1964 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1965 KnownZero2.countLeadingOnes(),
1966 BitWidth) - BitWidth;
1968 TrailZ = std::min(TrailZ, BitWidth);
1969 LeadZ = std::min(LeadZ, BitWidth);
1970 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1971 APInt::getHighBitsSet(BitWidth, LeadZ);
1975 // For the purposes of computing leading zeros we can conservatively
1976 // treat a udiv as a logical right shift by the power of 2 known to
1977 // be less than the denominator.
1978 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1979 unsigned LeadZ = KnownZero2.countLeadingOnes();
1981 KnownOne2.clearAllBits();
1982 KnownZero2.clearAllBits();
1983 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1984 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1985 if (RHSUnknownLeadingOnes != BitWidth)
1986 LeadZ = std::min(BitWidth,
1987 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1989 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1993 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1994 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1996 // Only known if known in both the LHS and RHS.
1997 KnownOne &= KnownOne2;
1998 KnownZero &= KnownZero2;
2000 case ISD::SELECT_CC:
2001 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2002 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2004 // Only known if known in both the LHS and RHS.
2005 KnownOne &= KnownOne2;
2006 KnownZero &= KnownZero2;
2014 if (Op.getResNo() != 1)
2016 // The boolean result conforms to getBooleanContents.
2017 // If we know the result of a setcc has the top bits zero, use this info.
2018 // We know that we have an integer-based boolean since these operations
2019 // are only available for integer.
2020 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2021 TargetLowering::ZeroOrOneBooleanContent &&
2023 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2026 // If we know the result of a setcc has the top bits zero, use this info.
2027 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2028 TargetLowering::ZeroOrOneBooleanContent &&
2030 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2033 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2034 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2035 unsigned ShAmt = SA->getZExtValue();
2037 // If the shift count is an invalid immediate, don't do anything.
2038 if (ShAmt >= BitWidth)
2041 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2042 KnownZero <<= ShAmt;
2044 // low bits known zero.
2045 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2049 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2050 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2051 unsigned ShAmt = SA->getZExtValue();
2053 // If the shift count is an invalid immediate, don't do anything.
2054 if (ShAmt >= BitWidth)
2057 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2058 KnownZero = KnownZero.lshr(ShAmt);
2059 KnownOne = KnownOne.lshr(ShAmt);
2061 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2062 KnownZero |= HighBits; // High bits known zero.
2066 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2067 unsigned ShAmt = SA->getZExtValue();
2069 // If the shift count is an invalid immediate, don't do anything.
2070 if (ShAmt >= BitWidth)
2073 // If any of the demanded bits are produced by the sign extension, we also
2074 // demand the input sign bit.
2075 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2077 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2078 KnownZero = KnownZero.lshr(ShAmt);
2079 KnownOne = KnownOne.lshr(ShAmt);
2081 // Handle the sign bits.
2082 APInt SignBit = APInt::getSignBit(BitWidth);
2083 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2085 if (KnownZero.intersects(SignBit)) {
2086 KnownZero |= HighBits; // New bits are known zero.
2087 } else if (KnownOne.intersects(SignBit)) {
2088 KnownOne |= HighBits; // New bits are known one.
2092 case ISD::SIGN_EXTEND_INREG: {
2093 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2094 unsigned EBits = EVT.getScalarType().getSizeInBits();
2096 // Sign extension. Compute the demanded bits in the result that are not
2097 // present in the input.
2098 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2100 APInt InSignBit = APInt::getSignBit(EBits);
2101 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2103 // If the sign extended bits are demanded, we know that the sign
2105 InSignBit = InSignBit.zext(BitWidth);
2106 if (NewBits.getBoolValue())
2107 InputDemandedBits |= InSignBit;
2109 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2110 KnownOne &= InputDemandedBits;
2111 KnownZero &= InputDemandedBits;
2113 // If the sign bit of the input is known set or clear, then we know the
2114 // top bits of the result.
2115 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2116 KnownZero |= NewBits;
2117 KnownOne &= ~NewBits;
2118 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2119 KnownOne |= NewBits;
2120 KnownZero &= ~NewBits;
2121 } else { // Input sign bit unknown
2122 KnownZero &= ~NewBits;
2123 KnownOne &= ~NewBits;
2128 case ISD::CTTZ_ZERO_UNDEF:
2130 case ISD::CTLZ_ZERO_UNDEF:
2132 unsigned LowBits = Log2_32(BitWidth)+1;
2133 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2134 KnownOne.clearAllBits();
2138 LoadSDNode *LD = cast<LoadSDNode>(Op);
2139 // If this is a ZEXTLoad and we are looking at the loaded value.
2140 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2141 EVT VT = LD->getMemoryVT();
2142 unsigned MemBits = VT.getScalarType().getSizeInBits();
2143 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2144 } else if (const MDNode *Ranges = LD->getRanges()) {
2145 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2149 case ISD::ZERO_EXTEND: {
2150 EVT InVT = Op.getOperand(0).getValueType();
2151 unsigned InBits = InVT.getScalarType().getSizeInBits();
2152 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2153 KnownZero = KnownZero.trunc(InBits);
2154 KnownOne = KnownOne.trunc(InBits);
2155 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2156 KnownZero = KnownZero.zext(BitWidth);
2157 KnownOne = KnownOne.zext(BitWidth);
2158 KnownZero |= NewBits;
2161 case ISD::SIGN_EXTEND: {
2162 EVT InVT = Op.getOperand(0).getValueType();
2163 unsigned InBits = InVT.getScalarType().getSizeInBits();
2164 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2166 KnownZero = KnownZero.trunc(InBits);
2167 KnownOne = KnownOne.trunc(InBits);
2168 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2170 // Note if the sign bit is known to be zero or one.
2171 bool SignBitKnownZero = KnownZero.isNegative();
2172 bool SignBitKnownOne = KnownOne.isNegative();
2174 KnownZero = KnownZero.zext(BitWidth);
2175 KnownOne = KnownOne.zext(BitWidth);
2177 // If the sign bit is known zero or one, the top bits match.
2178 if (SignBitKnownZero)
2179 KnownZero |= NewBits;
2180 else if (SignBitKnownOne)
2181 KnownOne |= NewBits;
2184 case ISD::ANY_EXTEND: {
2185 EVT InVT = Op.getOperand(0).getValueType();
2186 unsigned InBits = InVT.getScalarType().getSizeInBits();
2187 KnownZero = KnownZero.trunc(InBits);
2188 KnownOne = KnownOne.trunc(InBits);
2189 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2190 KnownZero = KnownZero.zext(BitWidth);
2191 KnownOne = KnownOne.zext(BitWidth);
2194 case ISD::TRUNCATE: {
2195 EVT InVT = Op.getOperand(0).getValueType();
2196 unsigned InBits = InVT.getScalarType().getSizeInBits();
2197 KnownZero = KnownZero.zext(InBits);
2198 KnownOne = KnownOne.zext(InBits);
2199 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2200 KnownZero = KnownZero.trunc(BitWidth);
2201 KnownOne = KnownOne.trunc(BitWidth);
2204 case ISD::AssertZext: {
2205 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2206 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2207 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2208 KnownZero |= (~InMask);
2209 KnownOne &= (~KnownZero);
2213 // All bits are zero except the low bit.
2214 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2218 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2219 // We know that the top bits of C-X are clear if X contains less bits
2220 // than C (i.e. no wrap-around can happen). For example, 20-X is
2221 // positive if we can prove that X is >= 0 and < 16.
2222 if (CLHS->getAPIntValue().isNonNegative()) {
2223 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2224 // NLZ can't be BitWidth with no sign bit
2225 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2226 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2228 // If all of the MaskV bits are known to be zero, then we know the
2229 // output top bits are zero, because we now know that the output is
2231 if ((KnownZero2 & MaskV) == MaskV) {
2232 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2233 // Top bits known zero.
2234 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2242 // Output known-0 bits are known if clear or set in both the low clear bits
2243 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2244 // low 3 bits clear.
2245 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2246 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2248 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2249 KnownZeroOut = std::min(KnownZeroOut,
2250 KnownZero2.countTrailingOnes());
2252 if (Op.getOpcode() == ISD::ADD) {
2253 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2257 // With ADDE, a carry bit may be added in, so we can only use this
2258 // information if we know (at least) that the low two bits are clear. We
2259 // then return to the caller that the low bit is unknown but that other bits
2261 if (KnownZeroOut >= 2) // ADDE
2262 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2266 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2267 const APInt &RA = Rem->getAPIntValue().abs();
2268 if (RA.isPowerOf2()) {
2269 APInt LowBits = RA - 1;
2270 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2272 // The low bits of the first operand are unchanged by the srem.
2273 KnownZero = KnownZero2 & LowBits;
2274 KnownOne = KnownOne2 & LowBits;
2276 // If the first operand is non-negative or has all low bits zero, then
2277 // the upper bits are all zero.
2278 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2279 KnownZero |= ~LowBits;
2281 // If the first operand is negative and not all low bits are zero, then
2282 // the upper bits are all one.
2283 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2284 KnownOne |= ~LowBits;
2285 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2290 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2291 const APInt &RA = Rem->getAPIntValue();
2292 if (RA.isPowerOf2()) {
2293 APInt LowBits = (RA - 1);
2294 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2296 // The upper bits are all zero, the lower ones are unchanged.
2297 KnownZero = KnownZero2 | ~LowBits;
2298 KnownOne = KnownOne2 & LowBits;
2303 // Since the result is less than or equal to either operand, any leading
2304 // zero bits in either operand must also exist in the result.
2305 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2306 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2308 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2309 KnownZero2.countLeadingOnes());
2310 KnownOne.clearAllBits();
2311 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2314 case ISD::FrameIndex:
2315 case ISD::TargetFrameIndex:
2316 if (unsigned Align = InferPtrAlignment(Op)) {
2317 // The low bits are known zero if the pointer is aligned.
2318 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2324 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2327 case ISD::INTRINSIC_WO_CHAIN:
2328 case ISD::INTRINSIC_W_CHAIN:
2329 case ISD::INTRINSIC_VOID:
2330 // Allow the target to implement this method for its nodes.
2331 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2335 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2338 /// ComputeNumSignBits - Return the number of times the sign bit of the
2339 /// register is replicated into the other bits. We know that at least 1 bit
2340 /// is always equal to the sign bit (itself), but other cases can give us
2341 /// information. For example, immediately after an "SRA X, 2", we know that
2342 /// the top 3 bits are all equal to each other, so we return 3.
2343 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2344 const TargetLowering *TLI = TM.getTargetLowering();
2345 EVT VT = Op.getValueType();
2346 assert(VT.isInteger() && "Invalid VT!");
2347 unsigned VTBits = VT.getScalarType().getSizeInBits();
2349 unsigned FirstAnswer = 1;
2352 return 1; // Limit search depth.
2354 switch (Op.getOpcode()) {
2356 case ISD::AssertSext:
2357 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2358 return VTBits-Tmp+1;
2359 case ISD::AssertZext:
2360 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2363 case ISD::Constant: {
2364 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2365 return Val.getNumSignBits();
2368 case ISD::SIGN_EXTEND:
2370 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2371 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2373 case ISD::SIGN_EXTEND_INREG:
2374 // Max of the input and what this extends.
2376 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2379 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2380 return std::max(Tmp, Tmp2);
2383 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2384 // SRA X, C -> adds C sign bits.
2385 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2386 Tmp += C->getZExtValue();
2387 if (Tmp > VTBits) Tmp = VTBits;
2391 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2392 // shl destroys sign bits.
2393 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2394 if (C->getZExtValue() >= VTBits || // Bad shift.
2395 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2396 return Tmp - C->getZExtValue();
2401 case ISD::XOR: // NOT is handled here.
2402 // Logical binary ops preserve the number of sign bits at the worst.
2403 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2405 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2406 FirstAnswer = std::min(Tmp, Tmp2);
2407 // We computed what we know about the sign bits as our first
2408 // answer. Now proceed to the generic code that uses
2409 // computeKnownBits, and pick whichever answer is better.
2414 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2415 if (Tmp == 1) return 1; // Early out.
2416 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2417 return std::min(Tmp, Tmp2);
2425 if (Op.getResNo() != 1)
2427 // The boolean result conforms to getBooleanContents. Fall through.
2428 // If setcc returns 0/-1, all bits are sign bits.
2429 // We know that we have an integer-based boolean since these operations
2430 // are only available for integer.
2431 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2432 TargetLowering::ZeroOrNegativeOneBooleanContent)
2436 // If setcc returns 0/-1, all bits are sign bits.
2437 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2438 TargetLowering::ZeroOrNegativeOneBooleanContent)
2443 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2444 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2446 // Handle rotate right by N like a rotate left by 32-N.
2447 if (Op.getOpcode() == ISD::ROTR)
2448 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2450 // If we aren't rotating out all of the known-in sign bits, return the
2451 // number that are left. This handles rotl(sext(x), 1) for example.
2452 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2453 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2457 // Add can have at most one carry bit. Thus we know that the output
2458 // is, at worst, one more bit than the inputs.
2459 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2460 if (Tmp == 1) return 1; // Early out.
2462 // Special case decrementing a value (ADD X, -1):
2463 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2464 if (CRHS->isAllOnesValue()) {
2465 APInt KnownZero, KnownOne;
2466 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2468 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2470 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2473 // If we are subtracting one from a positive number, there is no carry
2474 // out of the result.
2475 if (KnownZero.isNegative())
2479 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2480 if (Tmp2 == 1) return 1;
2481 return std::min(Tmp, Tmp2)-1;
2484 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2485 if (Tmp2 == 1) return 1;
2488 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2489 if (CLHS->isNullValue()) {
2490 APInt KnownZero, KnownOne;
2491 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2492 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2494 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2497 // If the input is known to be positive (the sign bit is known clear),
2498 // the output of the NEG has the same number of sign bits as the input.
2499 if (KnownZero.isNegative())
2502 // Otherwise, we treat this like a SUB.
2505 // Sub can have at most one carry bit. Thus we know that the output
2506 // is, at worst, one more bit than the inputs.
2507 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2508 if (Tmp == 1) return 1; // Early out.
2509 return std::min(Tmp, Tmp2)-1;
2511 // FIXME: it's tricky to do anything useful for this, but it is an important
2512 // case for targets like X86.
2516 // If we are looking at the loaded value of the SDNode.
2517 if (Op.getResNo() == 0) {
2518 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2519 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2520 unsigned ExtType = LD->getExtensionType();
2523 case ISD::SEXTLOAD: // '17' bits known
2524 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2525 return VTBits-Tmp+1;
2526 case ISD::ZEXTLOAD: // '16' bits known
2527 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2533 // Allow the target to implement this method for its nodes.
2534 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2535 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2536 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2537 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2538 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2539 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2542 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2543 // use this information.
2544 APInt KnownZero, KnownOne;
2545 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2548 if (KnownZero.isNegative()) { // sign bit is 0
2550 } else if (KnownOne.isNegative()) { // sign bit is 1;
2557 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2558 // the number of identical bits in the top of the input value.
2560 Mask <<= Mask.getBitWidth()-VTBits;
2561 // Return # leading zeros. We use 'min' here in case Val was zero before
2562 // shifting. We don't want to return '64' as for an i32 "0".
2563 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2566 /// isBaseWithConstantOffset - Return true if the specified operand is an
2567 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2568 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2569 /// semantics as an ADD. This handles the equivalence:
2570 /// X|Cst == X+Cst iff X&Cst = 0.
2571 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2572 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2573 !isa<ConstantSDNode>(Op.getOperand(1)))
2576 if (Op.getOpcode() == ISD::OR &&
2577 !MaskedValueIsZero(Op.getOperand(0),
2578 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2585 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2586 // If we're told that NaNs won't happen, assume they won't.
2587 if (getTarget().Options.NoNaNsFPMath)
2590 // If the value is a constant, we can obviously see if it is a NaN or not.
2591 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2592 return !C->getValueAPF().isNaN();
2594 // TODO: Recognize more cases here.
2599 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2600 // If the value is a constant, we can obviously see if it is a zero or not.
2601 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2602 return !C->isZero();
2604 // TODO: Recognize more cases here.
2605 switch (Op.getOpcode()) {
2608 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2609 return !C->isNullValue();
2616 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2617 // Check the obvious case.
2618 if (A == B) return true;
2620 // For for negative and positive zero.
2621 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2622 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2623 if (CA->isZero() && CB->isZero()) return true;
2625 // Otherwise they may not be equal.
2629 /// getNode - Gets or creates the specified node.
2631 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2632 FoldingSetNodeID ID;
2633 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2635 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2636 return SDValue(E, 0);
2638 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2639 DL.getDebugLoc(), getVTList(VT));
2640 CSEMap.InsertNode(N, IP);
2642 AllNodes.push_back(N);
2646 return SDValue(N, 0);
2649 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2650 EVT VT, SDValue Operand) {
2651 // Constant fold unary operations with an integer constant operand. Even
2652 // opaque constant will be folded, because the folding of unary operations
2653 // doesn't create new constants with different values. Nevertheless, the
2654 // opaque flag is preserved during folding to prevent future folding with
2656 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2657 const APInt &Val = C->getAPIntValue();
2660 case ISD::SIGN_EXTEND:
2661 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2662 C->isTargetOpcode(), C->isOpaque());
2663 case ISD::ANY_EXTEND:
2664 case ISD::ZERO_EXTEND:
2666 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2667 C->isTargetOpcode(), C->isOpaque());
2668 case ISD::UINT_TO_FP:
2669 case ISD::SINT_TO_FP: {
2670 APFloat apf(EVTToAPFloatSemantics(VT),
2671 APInt::getNullValue(VT.getSizeInBits()));
2672 (void)apf.convertFromAPInt(Val,
2673 Opcode==ISD::SINT_TO_FP,
2674 APFloat::rmNearestTiesToEven);
2675 return getConstantFP(apf, VT);
2678 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2679 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2680 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2681 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2684 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2687 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2690 case ISD::CTLZ_ZERO_UNDEF:
2691 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2694 case ISD::CTTZ_ZERO_UNDEF:
2695 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2700 // Constant fold unary operations with a floating point constant operand.
2701 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2702 APFloat V = C->getValueAPF(); // make copy
2706 return getConstantFP(V, VT);
2709 return getConstantFP(V, VT);
2711 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2712 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2713 return getConstantFP(V, VT);
2717 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2718 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2719 return getConstantFP(V, VT);
2723 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2724 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2725 return getConstantFP(V, VT);
2728 case ISD::FP_EXTEND: {
2730 // This can return overflow, underflow, or inexact; we don't care.
2731 // FIXME need to be more flexible about rounding mode.
2732 (void)V.convert(EVTToAPFloatSemantics(VT),
2733 APFloat::rmNearestTiesToEven, &ignored);
2734 return getConstantFP(V, VT);
2736 case ISD::FP_TO_SINT:
2737 case ISD::FP_TO_UINT: {
2740 assert(integerPartWidth >= 64);
2741 // FIXME need to be more flexible about rounding mode.
2742 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2743 Opcode==ISD::FP_TO_SINT,
2744 APFloat::rmTowardZero, &ignored);
2745 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2747 APInt api(VT.getSizeInBits(), x);
2748 return getConstant(api, VT);
2751 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2752 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2753 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2754 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2759 // Constant fold unary operations with a vector integer operand.
2760 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2763 unsigned SplatBitSize;
2764 bool DummyHasUndefs;
2765 if (BV->isConstantSplat(Val, DummyUndefs, SplatBitSize, DummyHasUndefs)) {
2768 // FIXME: Entirely reasonable to perform folding of other unary
2769 // operations here as the need arises.
2771 case ISD::UINT_TO_FP:
2772 case ISD::SINT_TO_FP: {
2774 EVTToAPFloatSemantics(VT.getVectorElementType()),
2775 APInt::getNullValue(VT.getVectorElementType().getSizeInBits()));
2776 (void)APF.convertFromAPInt(Val, Opcode == ISD::SINT_TO_FP,
2777 APFloat::rmNearestTiesToEven);
2779 return getConstantFP(APF, VT);
2785 unsigned OpOpcode = Operand.getNode()->getOpcode();
2787 case ISD::TokenFactor:
2788 case ISD::MERGE_VALUES:
2789 case ISD::CONCAT_VECTORS:
2790 return Operand; // Factor, merge or concat of one node? No need.
2791 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2792 case ISD::FP_EXTEND:
2793 assert(VT.isFloatingPoint() &&
2794 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2795 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2796 assert((!VT.isVector() ||
2797 VT.getVectorNumElements() ==
2798 Operand.getValueType().getVectorNumElements()) &&
2799 "Vector element count mismatch!");
2800 if (Operand.getOpcode() == ISD::UNDEF)
2801 return getUNDEF(VT);
2803 case ISD::SIGN_EXTEND:
2804 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2805 "Invalid SIGN_EXTEND!");
2806 if (Operand.getValueType() == VT) return Operand; // noop extension
2807 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2808 "Invalid sext node, dst < src!");
2809 assert((!VT.isVector() ||
2810 VT.getVectorNumElements() ==
2811 Operand.getValueType().getVectorNumElements()) &&
2812 "Vector element count mismatch!");
2813 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2814 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2815 else if (OpOpcode == ISD::UNDEF)
2816 // sext(undef) = 0, because the top bits will all be the same.
2817 return getConstant(0, VT);
2819 case ISD::ZERO_EXTEND:
2820 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2821 "Invalid ZERO_EXTEND!");
2822 if (Operand.getValueType() == VT) return Operand; // noop extension
2823 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2824 "Invalid zext node, dst < src!");
2825 assert((!VT.isVector() ||
2826 VT.getVectorNumElements() ==
2827 Operand.getValueType().getVectorNumElements()) &&
2828 "Vector element count mismatch!");
2829 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2830 return getNode(ISD::ZERO_EXTEND, DL, VT,
2831 Operand.getNode()->getOperand(0));
2832 else if (OpOpcode == ISD::UNDEF)
2833 // zext(undef) = 0, because the top bits will be zero.
2834 return getConstant(0, VT);
2836 case ISD::ANY_EXTEND:
2837 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2838 "Invalid ANY_EXTEND!");
2839 if (Operand.getValueType() == VT) return Operand; // noop extension
2840 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2841 "Invalid anyext node, dst < src!");
2842 assert((!VT.isVector() ||
2843 VT.getVectorNumElements() ==
2844 Operand.getValueType().getVectorNumElements()) &&
2845 "Vector element count mismatch!");
2847 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2848 OpOpcode == ISD::ANY_EXTEND)
2849 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2850 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2851 else if (OpOpcode == ISD::UNDEF)
2852 return getUNDEF(VT);
2854 // (ext (trunx x)) -> x
2855 if (OpOpcode == ISD::TRUNCATE) {
2856 SDValue OpOp = Operand.getNode()->getOperand(0);
2857 if (OpOp.getValueType() == VT)
2862 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2863 "Invalid TRUNCATE!");
2864 if (Operand.getValueType() == VT) return Operand; // noop truncate
2865 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2866 "Invalid truncate node, src < dst!");
2867 assert((!VT.isVector() ||
2868 VT.getVectorNumElements() ==
2869 Operand.getValueType().getVectorNumElements()) &&
2870 "Vector element count mismatch!");
2871 if (OpOpcode == ISD::TRUNCATE)
2872 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2873 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2874 OpOpcode == ISD::ANY_EXTEND) {
2875 // If the source is smaller than the dest, we still need an extend.
2876 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2877 .bitsLT(VT.getScalarType()))
2878 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2879 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2880 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2881 return Operand.getNode()->getOperand(0);
2883 if (OpOpcode == ISD::UNDEF)
2884 return getUNDEF(VT);
2887 // Basic sanity checking.
2888 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2889 && "Cannot BITCAST between types of different sizes!");
2890 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2891 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2892 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2893 if (OpOpcode == ISD::UNDEF)
2894 return getUNDEF(VT);
2896 case ISD::SCALAR_TO_VECTOR:
2897 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2898 (VT.getVectorElementType() == Operand.getValueType() ||
2899 (VT.getVectorElementType().isInteger() &&
2900 Operand.getValueType().isInteger() &&
2901 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2902 "Illegal SCALAR_TO_VECTOR node!");
2903 if (OpOpcode == ISD::UNDEF)
2904 return getUNDEF(VT);
2905 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2906 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2907 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2908 Operand.getConstantOperandVal(1) == 0 &&
2909 Operand.getOperand(0).getValueType() == VT)
2910 return Operand.getOperand(0);
2913 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2914 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2915 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2916 Operand.getNode()->getOperand(0));
2917 if (OpOpcode == ISD::FNEG) // --X -> X
2918 return Operand.getNode()->getOperand(0);
2921 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2922 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2927 SDVTList VTs = getVTList(VT);
2928 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2929 FoldingSetNodeID ID;
2930 SDValue Ops[1] = { Operand };
2931 AddNodeIDNode(ID, Opcode, VTs, Ops);
2933 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2934 return SDValue(E, 0);
2936 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2937 DL.getDebugLoc(), VTs, Operand);
2938 CSEMap.InsertNode(N, IP);
2940 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2941 DL.getDebugLoc(), VTs, Operand);
2944 AllNodes.push_back(N);
2948 return SDValue(N, 0);
2951 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2952 SDNode *Cst1, SDNode *Cst2) {
2953 // If the opcode is a target-specific ISD node, there's nothing we can
2954 // do here and the operand rules may not line up with the below, so
2956 if (Opcode >= ISD::BUILTIN_OP_END)
2959 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2960 SmallVector<SDValue, 4> Outputs;
2961 EVT SVT = VT.getScalarType();
2963 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2964 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2965 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2968 if (Scalar1 && Scalar2)
2969 // Scalar instruction.
2970 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2972 // For vectors extract each constant element into Inputs so we can constant
2973 // fold them individually.
2974 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2975 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2979 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2981 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2982 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2983 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2984 if (!V1 || !V2) // Not a constant, bail.
2987 if (V1->isOpaque() || V2->isOpaque())
2990 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2991 // FIXME: This is valid and could be handled by truncating the APInts.
2992 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2995 Inputs.push_back(std::make_pair(V1, V2));
2999 // We have a number of constant values, constant fold them element by element.
3000 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3001 const APInt &C1 = Inputs[I].first->getAPIntValue();
3002 const APInt &C2 = Inputs[I].second->getAPIntValue();
3006 Outputs.push_back(getConstant(C1 + C2, SVT));
3009 Outputs.push_back(getConstant(C1 - C2, SVT));
3012 Outputs.push_back(getConstant(C1 * C2, SVT));
3015 if (!C2.getBoolValue())
3017 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3020 if (!C2.getBoolValue())
3022 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3025 if (!C2.getBoolValue())
3027 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3030 if (!C2.getBoolValue())
3032 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3035 Outputs.push_back(getConstant(C1 & C2, SVT));
3038 Outputs.push_back(getConstant(C1 | C2, SVT));
3041 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3044 Outputs.push_back(getConstant(C1 << C2, SVT));
3047 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3050 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3053 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3056 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3063 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3064 "Expected a scalar or vector!"));
3066 // Handle the scalar case first.
3068 return Outputs.back();
3070 // We may have a vector type but a scalar result. Create a splat.
3071 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3073 // Build a big vector out of the scalar elements we generated.
3074 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3077 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3078 SDValue N2, bool nuw, bool nsw, bool exact) {
3079 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3080 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3083 case ISD::TokenFactor:
3084 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3085 N2.getValueType() == MVT::Other && "Invalid token factor!");
3086 // Fold trivial token factors.
3087 if (N1.getOpcode() == ISD::EntryToken) return N2;
3088 if (N2.getOpcode() == ISD::EntryToken) return N1;
3089 if (N1 == N2) return N1;
3091 case ISD::CONCAT_VECTORS:
3092 // Concat of UNDEFs is UNDEF.
3093 if (N1.getOpcode() == ISD::UNDEF &&
3094 N2.getOpcode() == ISD::UNDEF)
3095 return getUNDEF(VT);
3097 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3098 // one big BUILD_VECTOR.
3099 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3100 N2.getOpcode() == ISD::BUILD_VECTOR) {
3101 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3102 N1.getNode()->op_end());
3103 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3104 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3108 assert(VT.isInteger() && "This operator does not apply to FP types!");
3109 assert(N1.getValueType() == N2.getValueType() &&
3110 N1.getValueType() == VT && "Binary operator types must match!");
3111 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3112 // worth handling here.
3113 if (N2C && N2C->isNullValue())
3115 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3122 assert(VT.isInteger() && "This operator does not apply to FP types!");
3123 assert(N1.getValueType() == N2.getValueType() &&
3124 N1.getValueType() == VT && "Binary operator types must match!");
3125 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3126 // it's worth handling here.
3127 if (N2C && N2C->isNullValue())
3137 assert(VT.isInteger() && "This operator does not apply to FP types!");
3138 assert(N1.getValueType() == N2.getValueType() &&
3139 N1.getValueType() == VT && "Binary operator types must match!");
3146 if (getTarget().Options.UnsafeFPMath) {
3147 if (Opcode == ISD::FADD) {
3149 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3150 if (CFP->getValueAPF().isZero())
3153 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3154 if (CFP->getValueAPF().isZero())
3156 } else if (Opcode == ISD::FSUB) {
3158 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3159 if (CFP->getValueAPF().isZero())
3161 } else if (Opcode == ISD::FMUL) {
3162 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3165 // If the first operand isn't the constant, try the second
3167 CFP = dyn_cast<ConstantFPSDNode>(N2);
3174 return SDValue(CFP,0);
3176 if (CFP->isExactlyValue(1.0))
3181 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3182 assert(N1.getValueType() == N2.getValueType() &&
3183 N1.getValueType() == VT && "Binary operator types must match!");
3185 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3186 assert(N1.getValueType() == VT &&
3187 N1.getValueType().isFloatingPoint() &&
3188 N2.getValueType().isFloatingPoint() &&
3189 "Invalid FCOPYSIGN!");
3196 assert(VT == N1.getValueType() &&
3197 "Shift operators return type must be the same as their first arg");
3198 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3199 "Shifts only work on integers");
3200 assert((!VT.isVector() || VT == N2.getValueType()) &&
3201 "Vector shift amounts must be in the same as their first arg");
3202 // Verify that the shift amount VT is bit enough to hold valid shift
3203 // amounts. This catches things like trying to shift an i1024 value by an
3204 // i8, which is easy to fall into in generic code that uses
3205 // TLI.getShiftAmount().
3206 assert(N2.getValueType().getSizeInBits() >=
3207 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3208 "Invalid use of small shift amount with oversized value!");
3210 // Always fold shifts of i1 values so the code generator doesn't need to
3211 // handle them. Since we know the size of the shift has to be less than the
3212 // size of the value, the shift/rotate count is guaranteed to be zero.
3215 if (N2C && N2C->isNullValue())
3218 case ISD::FP_ROUND_INREG: {
3219 EVT EVT = cast<VTSDNode>(N2)->getVT();
3220 assert(VT == N1.getValueType() && "Not an inreg round!");
3221 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3222 "Cannot FP_ROUND_INREG integer types");
3223 assert(EVT.isVector() == VT.isVector() &&
3224 "FP_ROUND_INREG type should be vector iff the operand "
3226 assert((!EVT.isVector() ||
3227 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3228 "Vector element counts must match in FP_ROUND_INREG");
3229 assert(EVT.bitsLE(VT) && "Not rounding down!");
3231 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3235 assert(VT.isFloatingPoint() &&
3236 N1.getValueType().isFloatingPoint() &&
3237 VT.bitsLE(N1.getValueType()) &&
3238 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3239 if (N1.getValueType() == VT) return N1; // noop conversion.
3241 case ISD::AssertSext:
3242 case ISD::AssertZext: {
3243 EVT EVT = cast<VTSDNode>(N2)->getVT();
3244 assert(VT == N1.getValueType() && "Not an inreg extend!");
3245 assert(VT.isInteger() && EVT.isInteger() &&
3246 "Cannot *_EXTEND_INREG FP types");
3247 assert(!EVT.isVector() &&
3248 "AssertSExt/AssertZExt type should be the vector element type "
3249 "rather than the vector type!");
3250 assert(EVT.bitsLE(VT) && "Not extending!");
3251 if (VT == EVT) return N1; // noop assertion.
3254 case ISD::SIGN_EXTEND_INREG: {
3255 EVT EVT = cast<VTSDNode>(N2)->getVT();
3256 assert(VT == N1.getValueType() && "Not an inreg extend!");
3257 assert(VT.isInteger() && EVT.isInteger() &&
3258 "Cannot *_EXTEND_INREG FP types");
3259 assert(EVT.isVector() == VT.isVector() &&
3260 "SIGN_EXTEND_INREG type should be vector iff the operand "
3262 assert((!EVT.isVector() ||
3263 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3264 "Vector element counts must match in SIGN_EXTEND_INREG");
3265 assert(EVT.bitsLE(VT) && "Not extending!");
3266 if (EVT == VT) return N1; // Not actually extending
3269 APInt Val = N1C->getAPIntValue();
3270 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3271 Val <<= Val.getBitWidth()-FromBits;
3272 Val = Val.ashr(Val.getBitWidth()-FromBits);
3273 return getConstant(Val, VT);
3277 case ISD::EXTRACT_VECTOR_ELT:
3278 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3279 if (N1.getOpcode() == ISD::UNDEF)
3280 return getUNDEF(VT);
3282 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3283 // expanding copies of large vectors from registers.
3285 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3286 N1.getNumOperands() > 0) {
3288 N1.getOperand(0).getValueType().getVectorNumElements();
3289 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3290 N1.getOperand(N2C->getZExtValue() / Factor),
3291 getConstant(N2C->getZExtValue() % Factor,
3292 N2.getValueType()));
3295 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3296 // expanding large vector constants.
3297 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3298 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3300 if (VT != Elt.getValueType())
3301 // If the vector element type is not legal, the BUILD_VECTOR operands
3302 // are promoted and implicitly truncated, and the result implicitly
3303 // extended. Make that explicit here.
3304 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3309 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3310 // operations are lowered to scalars.
3311 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3312 // If the indices are the same, return the inserted element else
3313 // if the indices are known different, extract the element from
3314 // the original vector.
3315 SDValue N1Op2 = N1.getOperand(2);
3316 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3318 if (N1Op2C && N2C) {
3319 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3320 if (VT == N1.getOperand(1).getValueType())
3321 return N1.getOperand(1);
3323 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3326 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3330 case ISD::EXTRACT_ELEMENT:
3331 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3332 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3333 (N1.getValueType().isInteger() == VT.isInteger()) &&
3334 N1.getValueType() != VT &&
3335 "Wrong types for EXTRACT_ELEMENT!");
3337 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3338 // 64-bit integers into 32-bit parts. Instead of building the extract of
3339 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3340 if (N1.getOpcode() == ISD::BUILD_PAIR)
3341 return N1.getOperand(N2C->getZExtValue());
3343 // EXTRACT_ELEMENT of a constant int is also very common.
3344 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3345 unsigned ElementSize = VT.getSizeInBits();
3346 unsigned Shift = ElementSize * N2C->getZExtValue();
3347 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3348 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3351 case ISD::EXTRACT_SUBVECTOR: {
3353 if (VT.isSimple() && N1.getValueType().isSimple()) {
3354 assert(VT.isVector() && N1.getValueType().isVector() &&
3355 "Extract subvector VTs must be a vectors!");
3356 assert(VT.getVectorElementType() ==
3357 N1.getValueType().getVectorElementType() &&
3358 "Extract subvector VTs must have the same element type!");
3359 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3360 "Extract subvector must be from larger vector to smaller vector!");
3362 if (isa<ConstantSDNode>(Index.getNode())) {
3363 assert((VT.getVectorNumElements() +
3364 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3365 <= N1.getValueType().getVectorNumElements())
3366 && "Extract subvector overflow!");
3369 // Trivial extraction.
3370 if (VT.getSimpleVT() == N1.getSimpleValueType())
3377 // Perform trivial constant folding.
3378 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3379 if (SV.getNode()) return SV;
3381 // Canonicalize constant to RHS if commutative.
3382 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3383 std::swap(N1C, N2C);
3387 // Constant fold FP operations.
3388 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3389 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3391 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3392 // Canonicalize constant to RHS if commutative.
3393 std::swap(N1CFP, N2CFP);
3396 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3397 APFloat::opStatus s;
3400 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3401 if (s != APFloat::opInvalidOp)
3402 return getConstantFP(V1, VT);
3405 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3406 if (s!=APFloat::opInvalidOp)
3407 return getConstantFP(V1, VT);
3410 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3411 if (s!=APFloat::opInvalidOp)
3412 return getConstantFP(V1, VT);
3415 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3416 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3417 return getConstantFP(V1, VT);
3420 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3421 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3422 return getConstantFP(V1, VT);
3424 case ISD::FCOPYSIGN:
3426 return getConstantFP(V1, VT);
3431 if (Opcode == ISD::FP_ROUND) {
3432 APFloat V = N1CFP->getValueAPF(); // make copy
3434 // This can return overflow, underflow, or inexact; we don't care.
3435 // FIXME need to be more flexible about rounding mode.
3436 (void)V.convert(EVTToAPFloatSemantics(VT),
3437 APFloat::rmNearestTiesToEven, &ignored);
3438 return getConstantFP(V, VT);
3442 // Canonicalize an UNDEF to the RHS, even over a constant.
3443 if (N1.getOpcode() == ISD::UNDEF) {
3444 if (isCommutativeBinOp(Opcode)) {
3448 case ISD::FP_ROUND_INREG:
3449 case ISD::SIGN_EXTEND_INREG:
3455 return N1; // fold op(undef, arg2) -> undef
3463 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3464 // For vectors, we can't easily build an all zero vector, just return
3471 // Fold a bunch of operators when the RHS is undef.
3472 if (N2.getOpcode() == ISD::UNDEF) {
3475 if (N1.getOpcode() == ISD::UNDEF)
3476 // Handle undef ^ undef -> 0 special case. This is a common
3478 return getConstant(0, VT);
3488 return N2; // fold op(arg1, undef) -> undef
3494 if (getTarget().Options.UnsafeFPMath)
3502 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3503 // For vectors, we can't easily build an all zero vector, just return
3508 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3509 // For vectors, we can't easily build an all one vector, just return
3517 // Memoize this node if possible.
3519 SDVTList VTs = getVTList(VT);
3520 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3521 if (VT != MVT::Glue) {
3522 SDValue Ops[] = {N1, N2};
3523 FoldingSetNodeID ID;
3524 AddNodeIDNode(ID, Opcode, VTs, Ops);
3526 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3528 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3529 return SDValue(E, 0);
3531 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3533 CSEMap.InsertNode(N, IP);
3536 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3539 AllNodes.push_back(N);
3543 return SDValue(N, 0);
3546 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3547 SDValue N1, SDValue N2, SDValue N3) {
3548 // Perform various simplifications.
3549 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3552 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3553 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3554 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3555 if (N1CFP && N2CFP && N3CFP) {
3556 APFloat V1 = N1CFP->getValueAPF();
3557 const APFloat &V2 = N2CFP->getValueAPF();
3558 const APFloat &V3 = N3CFP->getValueAPF();
3559 APFloat::opStatus s =
3560 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3561 if (s != APFloat::opInvalidOp)
3562 return getConstantFP(V1, VT);
3566 case ISD::CONCAT_VECTORS:
3567 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3568 // one big BUILD_VECTOR.
3569 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3570 N2.getOpcode() == ISD::BUILD_VECTOR &&
3571 N3.getOpcode() == ISD::BUILD_VECTOR) {
3572 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3573 N1.getNode()->op_end());
3574 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3575 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3576 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3580 // Use FoldSetCC to simplify SETCC's.
3581 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3582 if (Simp.getNode()) return Simp;
3587 if (N1C->getZExtValue())
3588 return N2; // select true, X, Y -> X
3589 return N3; // select false, X, Y -> Y
3592 if (N2 == N3) return N2; // select C, X, X -> X
3594 case ISD::VECTOR_SHUFFLE:
3595 llvm_unreachable("should use getVectorShuffle constructor!");
3596 case ISD::INSERT_SUBVECTOR: {
3598 if (VT.isSimple() && N1.getValueType().isSimple()
3599 && N2.getValueType().isSimple()) {
3600 assert(VT.isVector() && N1.getValueType().isVector() &&
3601 N2.getValueType().isVector() &&
3602 "Insert subvector VTs must be a vectors");
3603 assert(VT == N1.getValueType() &&
3604 "Dest and insert subvector source types must match!");
3605 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3606 "Insert subvector must be from smaller vector to larger vector!");
3607 if (isa<ConstantSDNode>(Index.getNode())) {
3608 assert((N2.getValueType().getVectorNumElements() +
3609 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3610 <= VT.getVectorNumElements())
3611 && "Insert subvector overflow!");
3614 // Trivial insertion.
3615 if (VT.getSimpleVT() == N2.getSimpleValueType())
3621 // Fold bit_convert nodes from a type to themselves.
3622 if (N1.getValueType() == VT)
3627 // Memoize node if it doesn't produce a flag.
3629 SDVTList VTs = getVTList(VT);
3630 if (VT != MVT::Glue) {
3631 SDValue Ops[] = { N1, N2, N3 };
3632 FoldingSetNodeID ID;
3633 AddNodeIDNode(ID, Opcode, VTs, Ops);
3635 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3636 return SDValue(E, 0);
3638 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3639 DL.getDebugLoc(), VTs, N1, N2, N3);
3640 CSEMap.InsertNode(N, IP);
3642 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3643 DL.getDebugLoc(), VTs, N1, N2, N3);
3646 AllNodes.push_back(N);
3650 return SDValue(N, 0);
3653 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3654 SDValue N1, SDValue N2, SDValue N3,
3656 SDValue Ops[] = { N1, N2, N3, N4 };
3657 return getNode(Opcode, DL, VT, Ops);
3660 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3661 SDValue N1, SDValue N2, SDValue N3,
3662 SDValue N4, SDValue N5) {
3663 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3664 return getNode(Opcode, DL, VT, Ops);
3667 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3668 /// the incoming stack arguments to be loaded from the stack.
3669 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3670 SmallVector<SDValue, 8> ArgChains;
3672 // Include the original chain at the beginning of the list. When this is
3673 // used by target LowerCall hooks, this helps legalize find the
3674 // CALLSEQ_BEGIN node.
3675 ArgChains.push_back(Chain);
3677 // Add a chain value for each stack argument.
3678 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3679 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3680 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3681 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3682 if (FI->getIndex() < 0)
3683 ArgChains.push_back(SDValue(L, 1));
3685 // Build a tokenfactor for all the chains.
3686 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3689 /// getMemsetValue - Vectorized representation of the memset value
3691 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3693 assert(Value.getOpcode() != ISD::UNDEF);
3695 unsigned NumBits = VT.getScalarType().getSizeInBits();
3696 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3697 assert(C->getAPIntValue().getBitWidth() == 8);
3698 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3700 return DAG.getConstant(Val, VT);
3701 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3704 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3706 // Use a multiplication with 0x010101... to extend the input to the
3708 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3709 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3715 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3716 /// used when a memcpy is turned into a memset when the source is a constant
3718 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3719 const TargetLowering &TLI, StringRef Str) {
3720 // Handle vector with all elements zero.
3723 return DAG.getConstant(0, VT);
3724 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3725 return DAG.getConstantFP(0.0, VT);
3726 else if (VT.isVector()) {
3727 unsigned NumElts = VT.getVectorNumElements();
3728 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3729 return DAG.getNode(ISD::BITCAST, dl, VT,
3730 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3733 llvm_unreachable("Expected type!");
3736 assert(!VT.isVector() && "Can't handle vector type here!");
3737 unsigned NumVTBits = VT.getSizeInBits();
3738 unsigned NumVTBytes = NumVTBits / 8;
3739 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3741 APInt Val(NumVTBits, 0);
3742 if (TLI.isLittleEndian()) {
3743 for (unsigned i = 0; i != NumBytes; ++i)
3744 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3746 for (unsigned i = 0; i != NumBytes; ++i)
3747 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3750 // If the "cost" of materializing the integer immediate is less than the cost
3751 // of a load, then it is cost effective to turn the load into the immediate.
3752 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3753 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3754 return DAG.getConstant(Val, VT);
3755 return SDValue(nullptr, 0);
3758 /// getMemBasePlusOffset - Returns base and offset node for the
3760 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3761 SelectionDAG &DAG) {
3762 EVT VT = Base.getValueType();
3763 return DAG.getNode(ISD::ADD, dl,
3764 VT, Base, DAG.getConstant(Offset, VT));
3767 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3769 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3770 unsigned SrcDelta = 0;
3771 GlobalAddressSDNode *G = nullptr;
3772 if (Src.getOpcode() == ISD::GlobalAddress)
3773 G = cast<GlobalAddressSDNode>(Src);
3774 else if (Src.getOpcode() == ISD::ADD &&
3775 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3776 Src.getOperand(1).getOpcode() == ISD::Constant) {
3777 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3778 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3783 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3786 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3787 /// to replace the memset / memcpy. Return true if the number of memory ops
3788 /// is below the threshold. It returns the types of the sequence of
3789 /// memory ops to perform memset / memcpy by reference.
3790 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3791 unsigned Limit, uint64_t Size,
3792 unsigned DstAlign, unsigned SrcAlign,
3798 const TargetLowering &TLI) {
3799 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3800 "Expecting memcpy / memset source to meet alignment requirement!");
3801 // If 'SrcAlign' is zero, that means the memory operation does not need to
3802 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3803 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3804 // is the specified alignment of the memory operation. If it is zero, that
3805 // means it's possible to change the alignment of the destination.
3806 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3807 // not need to be loaded.
3808 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3809 IsMemset, ZeroMemset, MemcpyStrSrc,
3810 DAG.getMachineFunction());
3812 if (VT == MVT::Other) {
3814 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3815 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3816 VT = TLI.getPointerTy();
3818 switch (DstAlign & 7) {
3819 case 0: VT = MVT::i64; break;
3820 case 4: VT = MVT::i32; break;
3821 case 2: VT = MVT::i16; break;
3822 default: VT = MVT::i8; break;
3827 while (!TLI.isTypeLegal(LVT))
3828 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3829 assert(LVT.isInteger());
3835 unsigned NumMemOps = 0;
3837 unsigned VTSize = VT.getSizeInBits() / 8;
3838 while (VTSize > Size) {
3839 // For now, only use non-vector load / store's for the left-over pieces.
3844 if (VT.isVector() || VT.isFloatingPoint()) {
3845 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3846 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3847 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3849 else if (NewVT == MVT::i64 &&
3850 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3851 TLI.isSafeMemOpType(MVT::f64)) {
3852 // i64 is usually not legal on 32-bit targets, but f64 may be.
3860 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3861 if (NewVT == MVT::i8)
3863 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3865 NewVTSize = NewVT.getSizeInBits() / 8;
3867 // If the new VT cannot cover all of the remaining bits, then consider
3868 // issuing a (or a pair of) unaligned and overlapping load / store.
3869 // FIXME: Only does this for 64-bit or more since we don't have proper
3870 // cost model for unaligned load / store.
3873 if (NumMemOps && AllowOverlap &&
3874 VTSize >= 8 && NewVTSize < Size &&
3875 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3883 if (++NumMemOps > Limit)
3886 MemOps.push_back(VT);
3893 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3894 SDValue Chain, SDValue Dst,
3895 SDValue Src, uint64_t Size,
3896 unsigned Align, bool isVol,
3898 MachinePointerInfo DstPtrInfo,
3899 MachinePointerInfo SrcPtrInfo) {
3900 // Turn a memcpy of undef to nop.
3901 if (Src.getOpcode() == ISD::UNDEF)
3904 // Expand memcpy to a series of load and store ops if the size operand falls
3905 // below a certain threshold.
3906 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3907 // rather than maybe a humongous number of loads and stores.
3908 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3909 std::vector<EVT> MemOps;
3910 bool DstAlignCanChange = false;
3911 MachineFunction &MF = DAG.getMachineFunction();
3912 MachineFrameInfo *MFI = MF.getFrameInfo();
3914 MF.getFunction()->getAttributes().
3915 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3916 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3917 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3918 DstAlignCanChange = true;
3919 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3920 if (Align > SrcAlign)
3923 bool CopyFromStr = isMemSrcFromString(Src, Str);
3924 bool isZeroStr = CopyFromStr && Str.empty();
3925 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3927 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3928 (DstAlignCanChange ? 0 : Align),
3929 (isZeroStr ? 0 : SrcAlign),
3930 false, false, CopyFromStr, true, DAG, TLI))
3933 if (DstAlignCanChange) {
3934 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3935 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3937 // Don't promote to an alignment that would require dynamic stack
3939 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3940 if (!TRI->needsStackRealignment(MF))
3941 while (NewAlign > Align &&
3942 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3945 if (NewAlign > Align) {
3946 // Give the stack frame object a larger alignment if needed.
3947 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3948 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3953 SmallVector<SDValue, 8> OutChains;
3954 unsigned NumMemOps = MemOps.size();
3955 uint64_t SrcOff = 0, DstOff = 0;
3956 for (unsigned i = 0; i != NumMemOps; ++i) {
3958 unsigned VTSize = VT.getSizeInBits() / 8;
3959 SDValue Value, Store;
3961 if (VTSize > Size) {
3962 // Issuing an unaligned load / store pair that overlaps with the previous
3963 // pair. Adjust the offset accordingly.
3964 assert(i == NumMemOps-1 && i != 0);
3965 SrcOff -= VTSize - Size;
3966 DstOff -= VTSize - Size;
3970 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3971 // It's unlikely a store of a vector immediate can be done in a single
3972 // instruction. It would require a load from a constantpool first.
3973 // We only handle zero vectors here.
3974 // FIXME: Handle other cases where store of vector immediate is done in
3975 // a single instruction.
3976 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3977 if (Value.getNode())
3978 Store = DAG.getStore(Chain, dl, Value,
3979 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3980 DstPtrInfo.getWithOffset(DstOff), isVol,
3984 if (!Store.getNode()) {
3985 // The type might not be legal for the target. This should only happen
3986 // if the type is smaller than a legal type, as on PPC, so the right
3987 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3988 // to Load/Store if NVT==VT.
3989 // FIXME does the case above also need this?
3990 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3991 assert(NVT.bitsGE(VT));
3992 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3993 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3994 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3995 MinAlign(SrcAlign, SrcOff));
3996 Store = DAG.getTruncStore(Chain, dl, Value,
3997 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3998 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4001 OutChains.push_back(Store);
4007 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4010 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4011 SDValue Chain, SDValue Dst,
4012 SDValue Src, uint64_t Size,
4013 unsigned Align, bool isVol,
4015 MachinePointerInfo DstPtrInfo,
4016 MachinePointerInfo SrcPtrInfo) {
4017 // Turn a memmove of undef to nop.
4018 if (Src.getOpcode() == ISD::UNDEF)
4021 // Expand memmove to a series of load and store ops if the size operand falls
4022 // below a certain threshold.
4023 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4024 std::vector<EVT> MemOps;
4025 bool DstAlignCanChange = false;
4026 MachineFunction &MF = DAG.getMachineFunction();
4027 MachineFrameInfo *MFI = MF.getFrameInfo();
4028 bool OptSize = MF.getFunction()->getAttributes().
4029 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4030 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4031 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4032 DstAlignCanChange = true;
4033 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4034 if (Align > SrcAlign)
4036 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4038 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4039 (DstAlignCanChange ? 0 : Align), SrcAlign,
4040 false, false, false, false, DAG, TLI))
4043 if (DstAlignCanChange) {
4044 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4045 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4046 if (NewAlign > Align) {
4047 // Give the stack frame object a larger alignment if needed.
4048 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4049 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4054 uint64_t SrcOff = 0, DstOff = 0;
4055 SmallVector<SDValue, 8> LoadValues;
4056 SmallVector<SDValue, 8> LoadChains;
4057 SmallVector<SDValue, 8> OutChains;
4058 unsigned NumMemOps = MemOps.size();
4059 for (unsigned i = 0; i < NumMemOps; i++) {
4061 unsigned VTSize = VT.getSizeInBits() / 8;
4064 Value = DAG.getLoad(VT, dl, Chain,
4065 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4066 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4067 false, false, SrcAlign);
4068 LoadValues.push_back(Value);
4069 LoadChains.push_back(Value.getValue(1));
4072 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4074 for (unsigned i = 0; i < NumMemOps; i++) {
4076 unsigned VTSize = VT.getSizeInBits() / 8;
4079 Store = DAG.getStore(Chain, dl, LoadValues[i],
4080 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4081 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4082 OutChains.push_back(Store);
4086 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4089 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4092 /// \param DAG Selection DAG where lowered code is placed.
4093 /// \param dl Link to corresponding IR location.
4094 /// \param Chain Control flow dependency.
4095 /// \param Dst Pointer to destination memory location.
4096 /// \param Src Value of byte to write into the memory.
4097 /// \param Size Number of bytes to write.
4098 /// \param Align Alignment of the destination in bytes.
4099 /// \param isVol True if destination is volatile.
4100 /// \param DstPtrInfo IR information on the memory pointer.
4101 /// \returns New head in the control flow, if lowering was successful, empty
4102 /// SDValue otherwise.
4104 /// The function tries to replace 'llvm.memset' intrinsic with several store
4105 /// operations and value calculation code. This is usually profitable for small
4107 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4108 SDValue Chain, SDValue Dst,
4109 SDValue Src, uint64_t Size,
4110 unsigned Align, bool isVol,
4111 MachinePointerInfo DstPtrInfo) {
4112 // Turn a memset of undef to nop.
4113 if (Src.getOpcode() == ISD::UNDEF)
4116 // Expand memset to a series of load/store ops if the size operand
4117 // falls below a certain threshold.
4118 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4119 std::vector<EVT> MemOps;
4120 bool DstAlignCanChange = false;
4121 MachineFunction &MF = DAG.getMachineFunction();
4122 MachineFrameInfo *MFI = MF.getFrameInfo();
4123 bool OptSize = MF.getFunction()->getAttributes().
4124 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4125 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4126 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4127 DstAlignCanChange = true;
4129 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4130 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4131 Size, (DstAlignCanChange ? 0 : Align), 0,
4132 true, IsZeroVal, false, true, DAG, TLI))
4135 if (DstAlignCanChange) {
4136 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4137 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4138 if (NewAlign > Align) {
4139 // Give the stack frame object a larger alignment if needed.
4140 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4141 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4146 SmallVector<SDValue, 8> OutChains;
4147 uint64_t DstOff = 0;
4148 unsigned NumMemOps = MemOps.size();
4150 // Find the largest store and generate the bit pattern for it.
4151 EVT LargestVT = MemOps[0];
4152 for (unsigned i = 1; i < NumMemOps; i++)
4153 if (MemOps[i].bitsGT(LargestVT))
4154 LargestVT = MemOps[i];
4155 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4157 for (unsigned i = 0; i < NumMemOps; i++) {
4159 unsigned VTSize = VT.getSizeInBits() / 8;
4160 if (VTSize > Size) {
4161 // Issuing an unaligned load / store pair that overlaps with the previous
4162 // pair. Adjust the offset accordingly.
4163 assert(i == NumMemOps-1 && i != 0);
4164 DstOff -= VTSize - Size;
4167 // If this store is smaller than the largest store see whether we can get
4168 // the smaller value for free with a truncate.
4169 SDValue Value = MemSetValue;
4170 if (VT.bitsLT(LargestVT)) {
4171 if (!LargestVT.isVector() && !VT.isVector() &&
4172 TLI.isTruncateFree(LargestVT, VT))
4173 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4175 Value = getMemsetValue(Src, VT, DAG, dl);
4177 assert(Value.getValueType() == VT && "Value with wrong type.");
4178 SDValue Store = DAG.getStore(Chain, dl, Value,
4179 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4180 DstPtrInfo.getWithOffset(DstOff),
4181 isVol, false, Align);
4182 OutChains.push_back(Store);
4183 DstOff += VT.getSizeInBits() / 8;
4187 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4190 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4191 SDValue Src, SDValue Size,
4192 unsigned Align, bool isVol, bool AlwaysInline,
4193 MachinePointerInfo DstPtrInfo,
4194 MachinePointerInfo SrcPtrInfo) {
4195 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4197 // Check to see if we should lower the memcpy to loads and stores first.
4198 // For cases within the target-specified limits, this is the best choice.
4199 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4201 // Memcpy with size zero? Just return the original chain.
4202 if (ConstantSize->isNullValue())
4205 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4206 ConstantSize->getZExtValue(),Align,
4207 isVol, false, DstPtrInfo, SrcPtrInfo);
4208 if (Result.getNode())
4212 // Then check to see if we should lower the memcpy with target-specific
4213 // code. If the target chooses to do this, this is the next best.
4215 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4216 isVol, AlwaysInline,
4217 DstPtrInfo, SrcPtrInfo);
4218 if (Result.getNode())
4221 // If we really need inline code and the target declined to provide it,
4222 // use a (potentially long) sequence of loads and stores.
4224 assert(ConstantSize && "AlwaysInline requires a constant size!");
4225 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4226 ConstantSize->getZExtValue(), Align, isVol,
4227 true, DstPtrInfo, SrcPtrInfo);
4230 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4231 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4232 // respect volatile, so they may do things like read or write memory
4233 // beyond the given memory regions. But fixing this isn't easy, and most
4234 // people don't care.
4236 const TargetLowering *TLI = TM.getTargetLowering();
4238 // Emit a library call.
4239 TargetLowering::ArgListTy Args;
4240 TargetLowering::ArgListEntry Entry;
4241 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4242 Entry.Node = Dst; Args.push_back(Entry);
4243 Entry.Node = Src; Args.push_back(Entry);
4244 Entry.Node = Size; Args.push_back(Entry);
4245 // FIXME: pass in SDLoc
4246 TargetLowering::CallLoweringInfo CLI(*this);
4247 CLI.setDebugLoc(dl).setChain(Chain)
4248 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4249 Type::getVoidTy(*getContext()),
4250 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4251 TLI->getPointerTy()), std::move(Args), 0)
4252 .setDiscardResult();
4253 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4255 return CallResult.second;
4258 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4259 SDValue Src, SDValue Size,
4260 unsigned Align, bool isVol,
4261 MachinePointerInfo DstPtrInfo,
4262 MachinePointerInfo SrcPtrInfo) {
4263 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4265 // Check to see if we should lower the memmove to loads and stores first.
4266 // For cases within the target-specified limits, this is the best choice.
4267 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4269 // Memmove with size zero? Just return the original chain.
4270 if (ConstantSize->isNullValue())
4274 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4275 ConstantSize->getZExtValue(), Align, isVol,
4276 false, DstPtrInfo, SrcPtrInfo);
4277 if (Result.getNode())
4281 // Then check to see if we should lower the memmove with target-specific
4282 // code. If the target chooses to do this, this is the next best.
4284 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4285 DstPtrInfo, SrcPtrInfo);
4286 if (Result.getNode())
4289 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4290 // not be safe. See memcpy above for more details.
4292 const TargetLowering *TLI = TM.getTargetLowering();
4294 // Emit a library call.
4295 TargetLowering::ArgListTy Args;
4296 TargetLowering::ArgListEntry Entry;
4297 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4298 Entry.Node = Dst; Args.push_back(Entry);
4299 Entry.Node = Src; Args.push_back(Entry);
4300 Entry.Node = Size; Args.push_back(Entry);
4301 // FIXME: pass in SDLoc
4302 TargetLowering::CallLoweringInfo CLI(*this);
4303 CLI.setDebugLoc(dl).setChain(Chain)
4304 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4305 Type::getVoidTy(*getContext()),
4306 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4307 TLI->getPointerTy()), std::move(Args), 0)
4308 .setDiscardResult();
4309 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4311 return CallResult.second;
4314 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4315 SDValue Src, SDValue Size,
4316 unsigned Align, bool isVol,
4317 MachinePointerInfo DstPtrInfo) {
4318 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4320 // Check to see if we should lower the memset to stores first.
4321 // For cases within the target-specified limits, this is the best choice.
4322 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4324 // Memset with size zero? Just return the original chain.
4325 if (ConstantSize->isNullValue())
4329 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4330 Align, isVol, DstPtrInfo);
4332 if (Result.getNode())
4336 // Then check to see if we should lower the memset with target-specific
4337 // code. If the target chooses to do this, this is the next best.
4339 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4341 if (Result.getNode())
4344 // Emit a library call.
4345 const TargetLowering *TLI = TM.getTargetLowering();
4346 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4347 TargetLowering::ArgListTy Args;
4348 TargetLowering::ArgListEntry Entry;
4349 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4350 Args.push_back(Entry);
4351 // Extend or truncate the argument to be an i32 value for the call.
4352 if (Src.getValueType().bitsGT(MVT::i32))
4353 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4355 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4357 Entry.Ty = Type::getInt32Ty(*getContext());
4358 Entry.isSExt = true;
4359 Args.push_back(Entry);
4361 Entry.Ty = IntPtrTy;
4362 Entry.isSExt = false;
4363 Args.push_back(Entry);
4365 // FIXME: pass in SDLoc
4366 TargetLowering::CallLoweringInfo CLI(*this);
4367 CLI.setDebugLoc(dl).setChain(Chain)
4368 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4369 Type::getVoidTy(*getContext()),
4370 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4371 TLI->getPointerTy()), std::move(Args), 0)
4372 .setDiscardResult();
4374 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4375 return CallResult.second;
4378 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4379 SDVTList VTList, ArrayRef<SDValue> Ops,
4380 MachineMemOperand *MMO,
4381 AtomicOrdering SuccessOrdering,
4382 AtomicOrdering FailureOrdering,
4383 SynchronizationScope SynchScope) {
4384 FoldingSetNodeID ID;
4385 ID.AddInteger(MemVT.getRawBits());
4386 AddNodeIDNode(ID, Opcode, VTList, Ops);
4387 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4389 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4390 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4391 return SDValue(E, 0);
4394 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4395 // SDNode doesn't have access to it. This memory will be "leaked" when
4396 // the node is deallocated, but recovered when the allocator is released.
4397 // If the number of operands is less than 5 we use AtomicSDNode's internal
4399 unsigned NumOps = Ops.size();
4400 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4403 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4404 dl.getDebugLoc(), VTList, MemVT,
4405 Ops.data(), DynOps, NumOps, MMO,
4406 SuccessOrdering, FailureOrdering,
4408 CSEMap.InsertNode(N, IP);
4409 AllNodes.push_back(N);
4410 return SDValue(N, 0);
4413 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4414 SDVTList VTList, ArrayRef<SDValue> Ops,
4415 MachineMemOperand *MMO,
4416 AtomicOrdering Ordering,
4417 SynchronizationScope SynchScope) {
4418 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4419 Ordering, SynchScope);
4422 SDValue SelectionDAG::getAtomicCmpSwap(
4423 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4424 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4425 unsigned Alignment, AtomicOrdering SuccessOrdering,
4426 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4427 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4428 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4429 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4431 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4432 Alignment = getEVTAlignment(MemVT);
4434 MachineFunction &MF = getMachineFunction();
4436 // FIXME: Volatile isn't really correct; we should keep track of atomic
4437 // orderings in the memoperand.
4438 unsigned Flags = MachineMemOperand::MOVolatile;
4439 Flags |= MachineMemOperand::MOLoad;
4440 Flags |= MachineMemOperand::MOStore;
4442 MachineMemOperand *MMO =
4443 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4445 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4446 SuccessOrdering, FailureOrdering, SynchScope);
4449 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4450 SDVTList VTs, SDValue Chain, SDValue Ptr,
4451 SDValue Cmp, SDValue Swp,
4452 MachineMemOperand *MMO,
4453 AtomicOrdering SuccessOrdering,
4454 AtomicOrdering FailureOrdering,
4455 SynchronizationScope SynchScope) {
4456 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4457 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4458 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4460 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4461 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4462 SuccessOrdering, FailureOrdering, SynchScope);
4465 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4467 SDValue Ptr, SDValue Val,
4468 const Value* PtrVal,
4470 AtomicOrdering Ordering,
4471 SynchronizationScope SynchScope) {
4472 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4473 Alignment = getEVTAlignment(MemVT);
4475 MachineFunction &MF = getMachineFunction();
4476 // An atomic store does not load. An atomic load does not store.
4477 // (An atomicrmw obviously both loads and stores.)
4478 // For now, atomics are considered to be volatile always, and they are
4480 // FIXME: Volatile isn't really correct; we should keep track of atomic
4481 // orderings in the memoperand.
4482 unsigned Flags = MachineMemOperand::MOVolatile;
4483 if (Opcode != ISD::ATOMIC_STORE)
4484 Flags |= MachineMemOperand::MOLoad;
4485 if (Opcode != ISD::ATOMIC_LOAD)
4486 Flags |= MachineMemOperand::MOStore;
4488 MachineMemOperand *MMO =
4489 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4490 MemVT.getStoreSize(), Alignment);
4492 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4493 Ordering, SynchScope);
4496 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4498 SDValue Ptr, SDValue Val,
4499 MachineMemOperand *MMO,
4500 AtomicOrdering Ordering,
4501 SynchronizationScope SynchScope) {
4502 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4503 Opcode == ISD::ATOMIC_LOAD_SUB ||
4504 Opcode == ISD::ATOMIC_LOAD_AND ||
4505 Opcode == ISD::ATOMIC_LOAD_OR ||
4506 Opcode == ISD::ATOMIC_LOAD_XOR ||
4507 Opcode == ISD::ATOMIC_LOAD_NAND ||
4508 Opcode == ISD::ATOMIC_LOAD_MIN ||
4509 Opcode == ISD::ATOMIC_LOAD_MAX ||
4510 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4511 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4512 Opcode == ISD::ATOMIC_SWAP ||
4513 Opcode == ISD::ATOMIC_STORE) &&
4514 "Invalid Atomic Op");
4516 EVT VT = Val.getValueType();
4518 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4519 getVTList(VT, MVT::Other);
4520 SDValue Ops[] = {Chain, Ptr, Val};
4521 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4524 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4525 EVT VT, SDValue Chain,
4527 MachineMemOperand *MMO,
4528 AtomicOrdering Ordering,
4529 SynchronizationScope SynchScope) {
4530 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4532 SDVTList VTs = getVTList(VT, MVT::Other);
4533 SDValue Ops[] = {Chain, Ptr};
4534 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4537 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4538 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4539 if (Ops.size() == 1)
4542 SmallVector<EVT, 4> VTs;
4543 VTs.reserve(Ops.size());
4544 for (unsigned i = 0; i < Ops.size(); ++i)
4545 VTs.push_back(Ops[i].getValueType());
4546 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4550 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4551 ArrayRef<SDValue> Ops,
4552 EVT MemVT, MachinePointerInfo PtrInfo,
4553 unsigned Align, bool Vol,
4554 bool ReadMem, bool WriteMem) {
4555 if (Align == 0) // Ensure that codegen never sees alignment 0
4556 Align = getEVTAlignment(MemVT);
4558 MachineFunction &MF = getMachineFunction();
4561 Flags |= MachineMemOperand::MOStore;
4563 Flags |= MachineMemOperand::MOLoad;
4565 Flags |= MachineMemOperand::MOVolatile;
4566 MachineMemOperand *MMO =
4567 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4569 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4573 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4574 ArrayRef<SDValue> Ops, EVT MemVT,
4575 MachineMemOperand *MMO) {
4576 assert((Opcode == ISD::INTRINSIC_VOID ||
4577 Opcode == ISD::INTRINSIC_W_CHAIN ||
4578 Opcode == ISD::PREFETCH ||
4579 Opcode == ISD::LIFETIME_START ||
4580 Opcode == ISD::LIFETIME_END ||
4581 (Opcode <= INT_MAX &&
4582 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4583 "Opcode is not a memory-accessing opcode!");
4585 // Memoize the node unless it returns a flag.
4586 MemIntrinsicSDNode *N;
4587 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4588 FoldingSetNodeID ID;
4589 AddNodeIDNode(ID, Opcode, VTList, Ops);
4590 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4592 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4593 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4594 return SDValue(E, 0);
4597 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4598 dl.getDebugLoc(), VTList, Ops,
4600 CSEMap.InsertNode(N, IP);
4602 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4603 dl.getDebugLoc(), VTList, Ops,
4606 AllNodes.push_back(N);
4607 return SDValue(N, 0);
4610 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4611 /// MachinePointerInfo record from it. This is particularly useful because the
4612 /// code generator has many cases where it doesn't bother passing in a
4613 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4614 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4615 // If this is FI+Offset, we can model it.
4616 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4617 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4619 // If this is (FI+Offset1)+Offset2, we can model it.
4620 if (Ptr.getOpcode() != ISD::ADD ||
4621 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4622 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4623 return MachinePointerInfo();
4625 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4626 return MachinePointerInfo::getFixedStack(FI, Offset+
4627 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4630 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4631 /// MachinePointerInfo record from it. This is particularly useful because the
4632 /// code generator has many cases where it doesn't bother passing in a
4633 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4634 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4635 // If the 'Offset' value isn't a constant, we can't handle this.
4636 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4637 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4638 if (OffsetOp.getOpcode() == ISD::UNDEF)
4639 return InferPointerInfo(Ptr);
4640 return MachinePointerInfo();
4645 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4646 EVT VT, SDLoc dl, SDValue Chain,
4647 SDValue Ptr, SDValue Offset,
4648 MachinePointerInfo PtrInfo, EVT MemVT,
4649 bool isVolatile, bool isNonTemporal, bool isInvariant,
4650 unsigned Alignment, const MDNode *TBAAInfo,
4651 const MDNode *Ranges) {
4652 assert(Chain.getValueType() == MVT::Other &&
4653 "Invalid chain type");
4654 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4655 Alignment = getEVTAlignment(VT);
4657 unsigned Flags = MachineMemOperand::MOLoad;
4659 Flags |= MachineMemOperand::MOVolatile;
4661 Flags |= MachineMemOperand::MONonTemporal;
4663 Flags |= MachineMemOperand::MOInvariant;
4665 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4667 if (PtrInfo.V.isNull())
4668 PtrInfo = InferPointerInfo(Ptr, Offset);
4670 MachineFunction &MF = getMachineFunction();
4671 MachineMemOperand *MMO =
4672 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4674 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4678 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4679 EVT VT, SDLoc dl, SDValue Chain,
4680 SDValue Ptr, SDValue Offset, EVT MemVT,
4681 MachineMemOperand *MMO) {
4683 ExtType = ISD::NON_EXTLOAD;
4684 } else if (ExtType == ISD::NON_EXTLOAD) {
4685 assert(VT == MemVT && "Non-extending load from different memory type!");
4688 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4689 "Should only be an extending load, not truncating!");
4690 assert(VT.isInteger() == MemVT.isInteger() &&
4691 "Cannot convert from FP to Int or Int -> FP!");
4692 assert(VT.isVector() == MemVT.isVector() &&
4693 "Cannot use trunc store to convert to or from a vector!");
4694 assert((!VT.isVector() ||
4695 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4696 "Cannot use trunc store to change the number of vector elements!");
4699 bool Indexed = AM != ISD::UNINDEXED;
4700 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4701 "Unindexed load with an offset!");
4703 SDVTList VTs = Indexed ?
4704 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4705 SDValue Ops[] = { Chain, Ptr, Offset };
4706 FoldingSetNodeID ID;
4707 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4708 ID.AddInteger(MemVT.getRawBits());
4709 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4710 MMO->isNonTemporal(),
4711 MMO->isInvariant()));
4712 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4714 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4715 cast<LoadSDNode>(E)->refineAlignment(MMO);
4716 return SDValue(E, 0);
4718 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4719 dl.getDebugLoc(), VTs, AM, ExtType,
4721 CSEMap.InsertNode(N, IP);
4722 AllNodes.push_back(N);
4723 return SDValue(N, 0);
4726 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4727 SDValue Chain, SDValue Ptr,
4728 MachinePointerInfo PtrInfo,
4729 bool isVolatile, bool isNonTemporal,
4730 bool isInvariant, unsigned Alignment,
4731 const MDNode *TBAAInfo,
4732 const MDNode *Ranges) {
4733 SDValue Undef = getUNDEF(Ptr.getValueType());
4734 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4735 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4739 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4740 SDValue Chain, SDValue Ptr,
4741 MachineMemOperand *MMO) {
4742 SDValue Undef = getUNDEF(Ptr.getValueType());
4743 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4747 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4748 SDValue Chain, SDValue Ptr,
4749 MachinePointerInfo PtrInfo, EVT MemVT,
4750 bool isVolatile, bool isNonTemporal,
4751 unsigned Alignment, const MDNode *TBAAInfo) {
4752 SDValue Undef = getUNDEF(Ptr.getValueType());
4753 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4754 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4759 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4760 SDValue Chain, SDValue Ptr, EVT MemVT,
4761 MachineMemOperand *MMO) {
4762 SDValue Undef = getUNDEF(Ptr.getValueType());
4763 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4768 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4769 SDValue Offset, ISD::MemIndexedMode AM) {
4770 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4771 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4772 "Load is already a indexed load!");
4773 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4774 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4775 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4776 false, LD->getAlignment());
4779 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4780 SDValue Ptr, MachinePointerInfo PtrInfo,
4781 bool isVolatile, bool isNonTemporal,
4782 unsigned Alignment, const MDNode *TBAAInfo) {
4783 assert(Chain.getValueType() == MVT::Other &&
4784 "Invalid chain type");
4785 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4786 Alignment = getEVTAlignment(Val.getValueType());
4788 unsigned Flags = MachineMemOperand::MOStore;
4790 Flags |= MachineMemOperand::MOVolatile;
4792 Flags |= MachineMemOperand::MONonTemporal;
4794 if (PtrInfo.V.isNull())
4795 PtrInfo = InferPointerInfo(Ptr);
4797 MachineFunction &MF = getMachineFunction();
4798 MachineMemOperand *MMO =
4799 MF.getMachineMemOperand(PtrInfo, Flags,
4800 Val.getValueType().getStoreSize(), Alignment,
4803 return getStore(Chain, dl, Val, Ptr, MMO);
4806 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4807 SDValue Ptr, MachineMemOperand *MMO) {
4808 assert(Chain.getValueType() == MVT::Other &&
4809 "Invalid chain type");
4810 EVT VT = Val.getValueType();
4811 SDVTList VTs = getVTList(MVT::Other);
4812 SDValue Undef = getUNDEF(Ptr.getValueType());
4813 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4814 FoldingSetNodeID ID;
4815 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4816 ID.AddInteger(VT.getRawBits());
4817 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4818 MMO->isNonTemporal(), MMO->isInvariant()));
4819 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4821 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4822 cast<StoreSDNode>(E)->refineAlignment(MMO);
4823 return SDValue(E, 0);
4825 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4826 dl.getDebugLoc(), VTs,
4827 ISD::UNINDEXED, false, VT, MMO);
4828 CSEMap.InsertNode(N, IP);
4829 AllNodes.push_back(N);
4830 return SDValue(N, 0);
4833 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4834 SDValue Ptr, MachinePointerInfo PtrInfo,
4835 EVT SVT,bool isVolatile, bool isNonTemporal,
4837 const MDNode *TBAAInfo) {
4838 assert(Chain.getValueType() == MVT::Other &&
4839 "Invalid chain type");
4840 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4841 Alignment = getEVTAlignment(SVT);
4843 unsigned Flags = MachineMemOperand::MOStore;
4845 Flags |= MachineMemOperand::MOVolatile;
4847 Flags |= MachineMemOperand::MONonTemporal;
4849 if (PtrInfo.V.isNull())
4850 PtrInfo = InferPointerInfo(Ptr);
4852 MachineFunction &MF = getMachineFunction();
4853 MachineMemOperand *MMO =
4854 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4857 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4860 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4861 SDValue Ptr, EVT SVT,
4862 MachineMemOperand *MMO) {
4863 EVT VT = Val.getValueType();
4865 assert(Chain.getValueType() == MVT::Other &&
4866 "Invalid chain type");
4868 return getStore(Chain, dl, Val, Ptr, MMO);
4870 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4871 "Should only be a truncating store, not extending!");
4872 assert(VT.isInteger() == SVT.isInteger() &&
4873 "Can't do FP-INT conversion!");
4874 assert(VT.isVector() == SVT.isVector() &&
4875 "Cannot use trunc store to convert to or from a vector!");
4876 assert((!VT.isVector() ||
4877 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4878 "Cannot use trunc store to change the number of vector elements!");
4880 SDVTList VTs = getVTList(MVT::Other);
4881 SDValue Undef = getUNDEF(Ptr.getValueType());
4882 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4883 FoldingSetNodeID ID;
4884 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4885 ID.AddInteger(SVT.getRawBits());
4886 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4887 MMO->isNonTemporal(), MMO->isInvariant()));
4888 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4890 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4891 cast<StoreSDNode>(E)->refineAlignment(MMO);
4892 return SDValue(E, 0);
4894 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4895 dl.getDebugLoc(), VTs,
4896 ISD::UNINDEXED, true, SVT, MMO);
4897 CSEMap.InsertNode(N, IP);
4898 AllNodes.push_back(N);
4899 return SDValue(N, 0);
4903 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4904 SDValue Offset, ISD::MemIndexedMode AM) {
4905 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4906 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4907 "Store is already a indexed store!");
4908 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4909 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4910 FoldingSetNodeID ID;
4911 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4912 ID.AddInteger(ST->getMemoryVT().getRawBits());
4913 ID.AddInteger(ST->getRawSubclassData());
4914 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4916 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4917 return SDValue(E, 0);
4919 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4920 dl.getDebugLoc(), VTs, AM,
4921 ST->isTruncatingStore(),
4923 ST->getMemOperand());
4924 CSEMap.InsertNode(N, IP);
4925 AllNodes.push_back(N);
4926 return SDValue(N, 0);
4929 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4930 SDValue Chain, SDValue Ptr,
4933 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4934 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4937 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4938 ArrayRef<SDUse> Ops) {
4939 switch (Ops.size()) {
4940 case 0: return getNode(Opcode, DL, VT);
4941 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4942 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4943 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4947 // Copy from an SDUse array into an SDValue array for use with
4948 // the regular getNode logic.
4949 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4950 return getNode(Opcode, DL, VT, NewOps);
4953 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4954 ArrayRef<SDValue> Ops) {
4955 unsigned NumOps = Ops.size();
4957 case 0: return getNode(Opcode, DL, VT);
4958 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4959 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4960 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4966 case ISD::SELECT_CC: {
4967 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4968 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4969 "LHS and RHS of condition must have same type!");
4970 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4971 "True and False arms of SelectCC must have same type!");
4972 assert(Ops[2].getValueType() == VT &&
4973 "select_cc node must be of same type as true and false value!");
4977 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4978 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4979 "LHS/RHS of comparison should match types!");
4986 SDVTList VTs = getVTList(VT);
4988 if (VT != MVT::Glue) {
4989 FoldingSetNodeID ID;
4990 AddNodeIDNode(ID, Opcode, VTs, Ops);
4993 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4994 return SDValue(E, 0);
4996 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4998 CSEMap.InsertNode(N, IP);
5000 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5004 AllNodes.push_back(N);
5008 return SDValue(N, 0);
5011 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5012 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5013 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5016 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5017 ArrayRef<SDValue> Ops) {
5018 if (VTList.NumVTs == 1)
5019 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5023 // FIXME: figure out how to safely handle things like
5024 // int foo(int x) { return 1 << (x & 255); }
5025 // int bar() { return foo(256); }
5026 case ISD::SRA_PARTS:
5027 case ISD::SRL_PARTS:
5028 case ISD::SHL_PARTS:
5029 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5030 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5031 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5032 else if (N3.getOpcode() == ISD::AND)
5033 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5034 // If the and is only masking out bits that cannot effect the shift,
5035 // eliminate the and.
5036 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5037 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5038 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5044 // Memoize the node unless it returns a flag.
5046 unsigned NumOps = Ops.size();
5047 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5048 FoldingSetNodeID ID;
5049 AddNodeIDNode(ID, Opcode, VTList, Ops);
5051 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5052 return SDValue(E, 0);
5055 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5056 DL.getDebugLoc(), VTList, Ops[0]);
5057 } else if (NumOps == 2) {
5058 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5059 DL.getDebugLoc(), VTList, Ops[0],
5061 } else if (NumOps == 3) {
5062 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5063 DL.getDebugLoc(), VTList, Ops[0],
5066 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5069 CSEMap.InsertNode(N, IP);
5072 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5073 DL.getDebugLoc(), VTList, Ops[0]);
5074 } else if (NumOps == 2) {
5075 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5076 DL.getDebugLoc(), VTList, Ops[0],
5078 } else if (NumOps == 3) {
5079 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5080 DL.getDebugLoc(), VTList, Ops[0],
5083 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5087 AllNodes.push_back(N);
5091 return SDValue(N, 0);
5094 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5095 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5098 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5100 SDValue Ops[] = { N1 };
5101 return getNode(Opcode, DL, VTList, Ops);
5104 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5105 SDValue N1, SDValue N2) {
5106 SDValue Ops[] = { N1, N2 };
5107 return getNode(Opcode, DL, VTList, Ops);
5110 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5111 SDValue N1, SDValue N2, SDValue N3) {
5112 SDValue Ops[] = { N1, N2, N3 };
5113 return getNode(Opcode, DL, VTList, Ops);
5116 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5117 SDValue N1, SDValue N2, SDValue N3,
5119 SDValue Ops[] = { N1, N2, N3, N4 };
5120 return getNode(Opcode, DL, VTList, Ops);
5123 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5124 SDValue N1, SDValue N2, SDValue N3,
5125 SDValue N4, SDValue N5) {
5126 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5127 return getNode(Opcode, DL, VTList, Ops);
5130 SDVTList SelectionDAG::getVTList(EVT VT) {
5131 return makeVTList(SDNode::getValueTypeList(VT), 1);
5134 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5135 FoldingSetNodeID ID;
5137 ID.AddInteger(VT1.getRawBits());
5138 ID.AddInteger(VT2.getRawBits());
5141 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5143 EVT *Array = Allocator.Allocate<EVT>(2);
5146 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5147 VTListMap.InsertNode(Result, IP);
5149 return Result->getSDVTList();
5152 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5153 FoldingSetNodeID ID;
5155 ID.AddInteger(VT1.getRawBits());
5156 ID.AddInteger(VT2.getRawBits());
5157 ID.AddInteger(VT3.getRawBits());
5160 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5162 EVT *Array = Allocator.Allocate<EVT>(3);
5166 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5167 VTListMap.InsertNode(Result, IP);
5169 return Result->getSDVTList();
5172 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5173 FoldingSetNodeID ID;
5175 ID.AddInteger(VT1.getRawBits());
5176 ID.AddInteger(VT2.getRawBits());
5177 ID.AddInteger(VT3.getRawBits());
5178 ID.AddInteger(VT4.getRawBits());
5181 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5183 EVT *Array = Allocator.Allocate<EVT>(4);
5188 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5189 VTListMap.InsertNode(Result, IP);
5191 return Result->getSDVTList();
5194 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5195 unsigned NumVTs = VTs.size();
5196 FoldingSetNodeID ID;
5197 ID.AddInteger(NumVTs);
5198 for (unsigned index = 0; index < NumVTs; index++) {
5199 ID.AddInteger(VTs[index].getRawBits());
5203 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5205 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5206 std::copy(VTs.begin(), VTs.end(), Array);
5207 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5208 VTListMap.InsertNode(Result, IP);
5210 return Result->getSDVTList();
5214 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5215 /// specified operands. If the resultant node already exists in the DAG,
5216 /// this does not modify the specified node, instead it returns the node that
5217 /// already exists. If the resultant node does not exist in the DAG, the
5218 /// input node is returned. As a degenerate case, if you specify the same
5219 /// input operands as the node already has, the input node is returned.
5220 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5221 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5223 // Check to see if there is no change.
5224 if (Op == N->getOperand(0)) return N;
5226 // See if the modified node already exists.
5227 void *InsertPos = nullptr;
5228 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5231 // Nope it doesn't. Remove the node from its current place in the maps.
5233 if (!RemoveNodeFromCSEMaps(N))
5234 InsertPos = nullptr;
5236 // Now we update the operands.
5237 N->OperandList[0].set(Op);
5239 // If this gets put into a CSE map, add it.
5240 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5244 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5245 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5247 // Check to see if there is no change.
5248 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5249 return N; // No operands changed, just return the input node.
5251 // See if the modified node already exists.
5252 void *InsertPos = nullptr;
5253 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5256 // Nope it doesn't. Remove the node from its current place in the maps.
5258 if (!RemoveNodeFromCSEMaps(N))
5259 InsertPos = nullptr;
5261 // Now we update the operands.
5262 if (N->OperandList[0] != Op1)
5263 N->OperandList[0].set(Op1);
5264 if (N->OperandList[1] != Op2)
5265 N->OperandList[1].set(Op2);
5267 // If this gets put into a CSE map, add it.
5268 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5272 SDNode *SelectionDAG::
5273 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5274 SDValue Ops[] = { Op1, Op2, Op3 };
5275 return UpdateNodeOperands(N, Ops);
5278 SDNode *SelectionDAG::
5279 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5280 SDValue Op3, SDValue Op4) {
5281 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5282 return UpdateNodeOperands(N, Ops);
5285 SDNode *SelectionDAG::
5286 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5287 SDValue Op3, SDValue Op4, SDValue Op5) {
5288 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5289 return UpdateNodeOperands(N, Ops);
5292 SDNode *SelectionDAG::
5293 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5294 unsigned NumOps = Ops.size();
5295 assert(N->getNumOperands() == NumOps &&
5296 "Update with wrong number of operands");
5298 // Check to see if there is no change.
5299 bool AnyChange = false;
5300 for (unsigned i = 0; i != NumOps; ++i) {
5301 if (Ops[i] != N->getOperand(i)) {
5307 // No operands changed, just return the input node.
5308 if (!AnyChange) return N;
5310 // See if the modified node already exists.
5311 void *InsertPos = nullptr;
5312 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5315 // Nope it doesn't. Remove the node from its current place in the maps.
5317 if (!RemoveNodeFromCSEMaps(N))
5318 InsertPos = nullptr;
5320 // Now we update the operands.
5321 for (unsigned i = 0; i != NumOps; ++i)
5322 if (N->OperandList[i] != Ops[i])
5323 N->OperandList[i].set(Ops[i]);
5325 // If this gets put into a CSE map, add it.
5326 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5330 /// DropOperands - Release the operands and set this node to have
5332 void SDNode::DropOperands() {
5333 // Unlike the code in MorphNodeTo that does this, we don't need to
5334 // watch for dead nodes here.
5335 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5341 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5344 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5346 SDVTList VTs = getVTList(VT);
5347 return SelectNodeTo(N, MachineOpc, VTs, None);
5350 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5351 EVT VT, SDValue Op1) {
5352 SDVTList VTs = getVTList(VT);
5353 SDValue Ops[] = { Op1 };
5354 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5357 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5358 EVT VT, SDValue Op1,
5360 SDVTList VTs = getVTList(VT);
5361 SDValue Ops[] = { Op1, Op2 };
5362 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5365 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5366 EVT VT, SDValue Op1,
5367 SDValue Op2, SDValue Op3) {
5368 SDVTList VTs = getVTList(VT);
5369 SDValue Ops[] = { Op1, Op2, Op3 };
5370 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5373 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5374 EVT VT, ArrayRef<SDValue> Ops) {
5375 SDVTList VTs = getVTList(VT);
5376 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5379 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5380 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5381 SDVTList VTs = getVTList(VT1, VT2);
5382 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5385 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5387 SDVTList VTs = getVTList(VT1, VT2);
5388 return SelectNodeTo(N, MachineOpc, VTs, None);
5391 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5392 EVT VT1, EVT VT2, EVT VT3,
5393 ArrayRef<SDValue> Ops) {
5394 SDVTList VTs = getVTList(VT1, VT2, VT3);
5395 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5398 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5399 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5400 ArrayRef<SDValue> Ops) {
5401 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5402 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5405 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5408 SDVTList VTs = getVTList(VT1, VT2);
5409 SDValue Ops[] = { Op1 };
5410 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5413 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5415 SDValue Op1, SDValue Op2) {
5416 SDVTList VTs = getVTList(VT1, VT2);
5417 SDValue Ops[] = { Op1, Op2 };
5418 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5421 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5423 SDValue Op1, SDValue Op2,
5425 SDVTList VTs = getVTList(VT1, VT2);
5426 SDValue Ops[] = { Op1, Op2, Op3 };
5427 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5430 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5431 EVT VT1, EVT VT2, EVT VT3,
5432 SDValue Op1, SDValue Op2,
5434 SDVTList VTs = getVTList(VT1, VT2, VT3);
5435 SDValue Ops[] = { Op1, Op2, Op3 };
5436 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5439 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5440 SDVTList VTs,ArrayRef<SDValue> Ops) {
5441 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5442 // Reset the NodeID to -1.
5447 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5448 /// the line number information on the merged node since it is not possible to
5449 /// preserve the information that operation is associated with multiple lines.
5450 /// This will make the debugger working better at -O0, were there is a higher
5451 /// probability having other instructions associated with that line.
5453 /// For IROrder, we keep the smaller of the two
5454 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5455 DebugLoc NLoc = N->getDebugLoc();
5456 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5457 (OLoc.getDebugLoc() != NLoc)) {
5458 N->setDebugLoc(DebugLoc());
5460 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5461 N->setIROrder(Order);
5465 /// MorphNodeTo - This *mutates* the specified node to have the specified
5466 /// return type, opcode, and operands.
5468 /// Note that MorphNodeTo returns the resultant node. If there is already a
5469 /// node of the specified opcode and operands, it returns that node instead of
5470 /// the current one. Note that the SDLoc need not be the same.
5472 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5473 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5474 /// node, and because it doesn't require CSE recalculation for any of
5475 /// the node's users.
5477 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5478 SDVTList VTs, ArrayRef<SDValue> Ops) {
5479 unsigned NumOps = Ops.size();
5480 // If an identical node already exists, use it.
5482 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5483 FoldingSetNodeID ID;
5484 AddNodeIDNode(ID, Opc, VTs, Ops);
5485 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5486 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5489 if (!RemoveNodeFromCSEMaps(N))
5492 // Start the morphing.
5494 N->ValueList = VTs.VTs;
5495 N->NumValues = VTs.NumVTs;
5497 // Clear the operands list, updating used nodes to remove this from their
5498 // use list. Keep track of any operands that become dead as a result.
5499 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5500 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5502 SDNode *Used = Use.getNode();
5504 if (Used->use_empty())
5505 DeadNodeSet.insert(Used);
5508 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5509 // Initialize the memory references information.
5510 MN->setMemRefs(nullptr, nullptr);
5511 // If NumOps is larger than the # of operands we can have in a
5512 // MachineSDNode, reallocate the operand list.
5513 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5514 if (MN->OperandsNeedDelete)
5515 delete[] MN->OperandList;
5516 if (NumOps > array_lengthof(MN->LocalOperands))
5517 // We're creating a final node that will live unmorphed for the
5518 // remainder of the current SelectionDAG iteration, so we can allocate
5519 // the operands directly out of a pool with no recycling metadata.
5520 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5521 Ops.data(), NumOps);
5523 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5524 MN->OperandsNeedDelete = false;
5526 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5528 // If NumOps is larger than the # of operands we currently have, reallocate
5529 // the operand list.
5530 if (NumOps > N->NumOperands) {
5531 if (N->OperandsNeedDelete)
5532 delete[] N->OperandList;
5533 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5534 N->OperandsNeedDelete = true;
5536 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5539 // Delete any nodes that are still dead after adding the uses for the
5541 if (!DeadNodeSet.empty()) {
5542 SmallVector<SDNode *, 16> DeadNodes;
5543 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5544 E = DeadNodeSet.end(); I != E; ++I)
5545 if ((*I)->use_empty())
5546 DeadNodes.push_back(*I);
5547 RemoveDeadNodes(DeadNodes);
5551 CSEMap.InsertNode(N, IP); // Memoize the new node.
5556 /// getMachineNode - These are used for target selectors to create a new node
5557 /// with specified return type(s), MachineInstr opcode, and operands.
5559 /// Note that getMachineNode returns the resultant node. If there is already a
5560 /// node of the specified opcode and operands, it returns that node instead of
5561 /// the current one.
5563 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5564 SDVTList VTs = getVTList(VT);
5565 return getMachineNode(Opcode, dl, VTs, None);
5569 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5570 SDVTList VTs = getVTList(VT);
5571 SDValue Ops[] = { Op1 };
5572 return getMachineNode(Opcode, dl, VTs, Ops);
5576 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5577 SDValue Op1, SDValue Op2) {
5578 SDVTList VTs = getVTList(VT);
5579 SDValue Ops[] = { Op1, Op2 };
5580 return getMachineNode(Opcode, dl, VTs, Ops);
5584 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5585 SDValue Op1, SDValue Op2, SDValue Op3) {
5586 SDVTList VTs = getVTList(VT);
5587 SDValue Ops[] = { Op1, Op2, Op3 };
5588 return getMachineNode(Opcode, dl, VTs, Ops);
5592 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5593 ArrayRef<SDValue> Ops) {
5594 SDVTList VTs = getVTList(VT);
5595 return getMachineNode(Opcode, dl, VTs, Ops);
5599 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5600 SDVTList VTs = getVTList(VT1, VT2);
5601 return getMachineNode(Opcode, dl, VTs, None);
5605 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5606 EVT VT1, EVT VT2, SDValue Op1) {
5607 SDVTList VTs = getVTList(VT1, VT2);
5608 SDValue Ops[] = { Op1 };
5609 return getMachineNode(Opcode, dl, VTs, Ops);
5613 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5614 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5615 SDVTList VTs = getVTList(VT1, VT2);
5616 SDValue Ops[] = { Op1, Op2 };
5617 return getMachineNode(Opcode, dl, VTs, Ops);
5621 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5622 EVT VT1, EVT VT2, SDValue Op1,
5623 SDValue Op2, SDValue Op3) {
5624 SDVTList VTs = getVTList(VT1, VT2);
5625 SDValue Ops[] = { Op1, Op2, Op3 };
5626 return getMachineNode(Opcode, dl, VTs, Ops);
5630 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5632 ArrayRef<SDValue> Ops) {
5633 SDVTList VTs = getVTList(VT1, VT2);
5634 return getMachineNode(Opcode, dl, VTs, Ops);
5638 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5639 EVT VT1, EVT VT2, EVT VT3,
5640 SDValue Op1, SDValue Op2) {
5641 SDVTList VTs = getVTList(VT1, VT2, VT3);
5642 SDValue Ops[] = { Op1, Op2 };
5643 return getMachineNode(Opcode, dl, VTs, Ops);
5647 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5648 EVT VT1, EVT VT2, EVT VT3,
5649 SDValue Op1, SDValue Op2, SDValue Op3) {
5650 SDVTList VTs = getVTList(VT1, VT2, VT3);
5651 SDValue Ops[] = { Op1, Op2, Op3 };
5652 return getMachineNode(Opcode, dl, VTs, Ops);
5656 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5657 EVT VT1, EVT VT2, EVT VT3,
5658 ArrayRef<SDValue> Ops) {
5659 SDVTList VTs = getVTList(VT1, VT2, VT3);
5660 return getMachineNode(Opcode, dl, VTs, Ops);
5664 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5665 EVT VT2, EVT VT3, EVT VT4,
5666 ArrayRef<SDValue> Ops) {
5667 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5668 return getMachineNode(Opcode, dl, VTs, Ops);
5672 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5673 ArrayRef<EVT> ResultTys,
5674 ArrayRef<SDValue> Ops) {
5675 SDVTList VTs = getVTList(ResultTys);
5676 return getMachineNode(Opcode, dl, VTs, Ops);
5680 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5681 ArrayRef<SDValue> OpsArray) {
5682 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5685 const SDValue *Ops = OpsArray.data();
5686 unsigned NumOps = OpsArray.size();
5689 FoldingSetNodeID ID;
5690 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5692 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5693 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5697 // Allocate a new MachineSDNode.
5698 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5699 DL.getDebugLoc(), VTs);
5701 // Initialize the operands list.
5702 if (NumOps > array_lengthof(N->LocalOperands))
5703 // We're creating a final node that will live unmorphed for the
5704 // remainder of the current SelectionDAG iteration, so we can allocate
5705 // the operands directly out of a pool with no recycling metadata.
5706 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5709 N->InitOperands(N->LocalOperands, Ops, NumOps);
5710 N->OperandsNeedDelete = false;
5713 CSEMap.InsertNode(N, IP);
5715 AllNodes.push_back(N);
5722 /// getTargetExtractSubreg - A convenience function for creating
5723 /// TargetOpcode::EXTRACT_SUBREG nodes.
5725 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5727 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5728 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5729 VT, Operand, SRIdxVal);
5730 return SDValue(Subreg, 0);
5733 /// getTargetInsertSubreg - A convenience function for creating
5734 /// TargetOpcode::INSERT_SUBREG nodes.
5736 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5737 SDValue Operand, SDValue Subreg) {
5738 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5739 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5740 VT, Operand, Subreg, SRIdxVal);
5741 return SDValue(Result, 0);
5744 /// getNodeIfExists - Get the specified node if it's already available, or
5745 /// else return NULL.
5746 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5747 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5749 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5750 FoldingSetNodeID ID;
5751 AddNodeIDNode(ID, Opcode, VTList, Ops);
5752 if (isBinOpWithFlags(Opcode))
5753 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5755 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5761 /// getDbgValue - Creates a SDDbgValue node.
5765 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5766 bool IsIndirect, uint64_t Off,
5767 DebugLoc DL, unsigned O) {
5768 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5773 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5775 DebugLoc DL, unsigned O) {
5776 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5781 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5782 DebugLoc DL, unsigned O) {
5783 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5788 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5789 /// pointed to by a use iterator is deleted, increment the use iterator
5790 /// so that it doesn't dangle.
5792 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5793 SDNode::use_iterator &UI;
5794 SDNode::use_iterator &UE;
5796 void NodeDeleted(SDNode *N, SDNode *E) override {
5797 // Increment the iterator as needed.
5798 while (UI != UE && N == *UI)
5803 RAUWUpdateListener(SelectionDAG &d,
5804 SDNode::use_iterator &ui,
5805 SDNode::use_iterator &ue)
5806 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5811 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5812 /// This can cause recursive merging of nodes in the DAG.
5814 /// This version assumes From has a single result value.
5816 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5817 SDNode *From = FromN.getNode();
5818 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5819 "Cannot replace with this method!");
5820 assert(From != To.getNode() && "Cannot replace uses of with self");
5822 // Iterate over all the existing uses of From. New uses will be added
5823 // to the beginning of the use list, which we avoid visiting.
5824 // This specifically avoids visiting uses of From that arise while the
5825 // replacement is happening, because any such uses would be the result
5826 // of CSE: If an existing node looks like From after one of its operands
5827 // is replaced by To, we don't want to replace of all its users with To
5828 // too. See PR3018 for more info.
5829 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5830 RAUWUpdateListener Listener(*this, UI, UE);
5834 // This node is about to morph, remove its old self from the CSE maps.
5835 RemoveNodeFromCSEMaps(User);
5837 // A user can appear in a use list multiple times, and when this
5838 // happens the uses are usually next to each other in the list.
5839 // To help reduce the number of CSE recomputations, process all
5840 // the uses of this user that we can find this way.
5842 SDUse &Use = UI.getUse();
5845 } while (UI != UE && *UI == User);
5847 // Now that we have modified User, add it back to the CSE maps. If it
5848 // already exists there, recursively merge the results together.
5849 AddModifiedNodeToCSEMaps(User);
5852 // If we just RAUW'd the root, take note.
5853 if (FromN == getRoot())
5857 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5858 /// This can cause recursive merging of nodes in the DAG.
5860 /// This version assumes that for each value of From, there is a
5861 /// corresponding value in To in the same position with the same type.
5863 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5865 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5866 assert((!From->hasAnyUseOfValue(i) ||
5867 From->getValueType(i) == To->getValueType(i)) &&
5868 "Cannot use this version of ReplaceAllUsesWith!");
5871 // Handle the trivial case.
5875 // Iterate over just the existing users of From. See the comments in
5876 // the ReplaceAllUsesWith above.
5877 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5878 RAUWUpdateListener Listener(*this, UI, UE);
5882 // This node is about to morph, remove its old self from the CSE maps.
5883 RemoveNodeFromCSEMaps(User);
5885 // A user can appear in a use list multiple times, and when this
5886 // happens the uses are usually next to each other in the list.
5887 // To help reduce the number of CSE recomputations, process all
5888 // the uses of this user that we can find this way.
5890 SDUse &Use = UI.getUse();
5893 } while (UI != UE && *UI == User);
5895 // Now that we have modified User, add it back to the CSE maps. If it
5896 // already exists there, recursively merge the results together.
5897 AddModifiedNodeToCSEMaps(User);
5900 // If we just RAUW'd the root, take note.
5901 if (From == getRoot().getNode())
5902 setRoot(SDValue(To, getRoot().getResNo()));
5905 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5906 /// This can cause recursive merging of nodes in the DAG.
5908 /// This version can replace From with any result values. To must match the
5909 /// number and types of values returned by From.
5910 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5911 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5912 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5914 // Iterate over just the existing users of From. See the comments in
5915 // the ReplaceAllUsesWith above.
5916 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5917 RAUWUpdateListener Listener(*this, UI, UE);
5921 // This node is about to morph, remove its old self from the CSE maps.
5922 RemoveNodeFromCSEMaps(User);
5924 // A user can appear in a use list multiple times, and when this
5925 // happens the uses are usually next to each other in the list.
5926 // To help reduce the number of CSE recomputations, process all
5927 // the uses of this user that we can find this way.
5929 SDUse &Use = UI.getUse();
5930 const SDValue &ToOp = To[Use.getResNo()];
5933 } while (UI != UE && *UI == User);
5935 // Now that we have modified User, add it back to the CSE maps. If it
5936 // already exists there, recursively merge the results together.
5937 AddModifiedNodeToCSEMaps(User);
5940 // If we just RAUW'd the root, take note.
5941 if (From == getRoot().getNode())
5942 setRoot(SDValue(To[getRoot().getResNo()]));
5945 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5946 /// uses of other values produced by From.getNode() alone. The Deleted
5947 /// vector is handled the same way as for ReplaceAllUsesWith.
5948 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5949 // Handle the really simple, really trivial case efficiently.
5950 if (From == To) return;
5952 // Handle the simple, trivial, case efficiently.
5953 if (From.getNode()->getNumValues() == 1) {
5954 ReplaceAllUsesWith(From, To);
5958 // Iterate over just the existing users of From. See the comments in
5959 // the ReplaceAllUsesWith above.
5960 SDNode::use_iterator UI = From.getNode()->use_begin(),
5961 UE = From.getNode()->use_end();
5962 RAUWUpdateListener Listener(*this, UI, UE);
5965 bool UserRemovedFromCSEMaps = false;
5967 // A user can appear in a use list multiple times, and when this
5968 // happens the uses are usually next to each other in the list.
5969 // To help reduce the number of CSE recomputations, process all
5970 // the uses of this user that we can find this way.
5972 SDUse &Use = UI.getUse();
5974 // Skip uses of different values from the same node.
5975 if (Use.getResNo() != From.getResNo()) {
5980 // If this node hasn't been modified yet, it's still in the CSE maps,
5981 // so remove its old self from the CSE maps.
5982 if (!UserRemovedFromCSEMaps) {
5983 RemoveNodeFromCSEMaps(User);
5984 UserRemovedFromCSEMaps = true;
5989 } while (UI != UE && *UI == User);
5991 // We are iterating over all uses of the From node, so if a use
5992 // doesn't use the specific value, no changes are made.
5993 if (!UserRemovedFromCSEMaps)
5996 // Now that we have modified User, add it back to the CSE maps. If it
5997 // already exists there, recursively merge the results together.
5998 AddModifiedNodeToCSEMaps(User);
6001 // If we just RAUW'd the root, take note.
6002 if (From == getRoot())
6007 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6008 /// to record information about a use.
6015 /// operator< - Sort Memos by User.
6016 bool operator<(const UseMemo &L, const UseMemo &R) {
6017 return (intptr_t)L.User < (intptr_t)R.User;
6021 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6022 /// uses of other values produced by From.getNode() alone. The same value
6023 /// may appear in both the From and To list. The Deleted vector is
6024 /// handled the same way as for ReplaceAllUsesWith.
6025 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6028 // Handle the simple, trivial case efficiently.
6030 return ReplaceAllUsesOfValueWith(*From, *To);
6032 // Read up all the uses and make records of them. This helps
6033 // processing new uses that are introduced during the
6034 // replacement process.
6035 SmallVector<UseMemo, 4> Uses;
6036 for (unsigned i = 0; i != Num; ++i) {
6037 unsigned FromResNo = From[i].getResNo();
6038 SDNode *FromNode = From[i].getNode();
6039 for (SDNode::use_iterator UI = FromNode->use_begin(),
6040 E = FromNode->use_end(); UI != E; ++UI) {
6041 SDUse &Use = UI.getUse();
6042 if (Use.getResNo() == FromResNo) {
6043 UseMemo Memo = { *UI, i, &Use };
6044 Uses.push_back(Memo);
6049 // Sort the uses, so that all the uses from a given User are together.
6050 std::sort(Uses.begin(), Uses.end());
6052 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6053 UseIndex != UseIndexEnd; ) {
6054 // We know that this user uses some value of From. If it is the right
6055 // value, update it.
6056 SDNode *User = Uses[UseIndex].User;
6058 // This node is about to morph, remove its old self from the CSE maps.
6059 RemoveNodeFromCSEMaps(User);
6061 // The Uses array is sorted, so all the uses for a given User
6062 // are next to each other in the list.
6063 // To help reduce the number of CSE recomputations, process all
6064 // the uses of this user that we can find this way.
6066 unsigned i = Uses[UseIndex].Index;
6067 SDUse &Use = *Uses[UseIndex].Use;
6071 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6073 // Now that we have modified User, add it back to the CSE maps. If it
6074 // already exists there, recursively merge the results together.
6075 AddModifiedNodeToCSEMaps(User);
6079 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6080 /// based on their topological order. It returns the maximum id and a vector
6081 /// of the SDNodes* in assigned order by reference.
6082 unsigned SelectionDAG::AssignTopologicalOrder() {
6084 unsigned DAGSize = 0;
6086 // SortedPos tracks the progress of the algorithm. Nodes before it are
6087 // sorted, nodes after it are unsorted. When the algorithm completes
6088 // it is at the end of the list.
6089 allnodes_iterator SortedPos = allnodes_begin();
6091 // Visit all the nodes. Move nodes with no operands to the front of
6092 // the list immediately. Annotate nodes that do have operands with their
6093 // operand count. Before we do this, the Node Id fields of the nodes
6094 // may contain arbitrary values. After, the Node Id fields for nodes
6095 // before SortedPos will contain the topological sort index, and the
6096 // Node Id fields for nodes At SortedPos and after will contain the
6097 // count of outstanding operands.
6098 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6100 checkForCycles(N, this);
6101 unsigned Degree = N->getNumOperands();
6103 // A node with no uses, add it to the result array immediately.
6104 N->setNodeId(DAGSize++);
6105 allnodes_iterator Q = N;
6107 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6108 assert(SortedPos != AllNodes.end() && "Overran node list");
6111 // Temporarily use the Node Id as scratch space for the degree count.
6112 N->setNodeId(Degree);
6116 // Visit all the nodes. As we iterate, move nodes into sorted order,
6117 // such that by the time the end is reached all nodes will be sorted.
6118 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6120 checkForCycles(N, this);
6121 // N is in sorted position, so all its uses have one less operand
6122 // that needs to be sorted.
6123 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6126 unsigned Degree = P->getNodeId();
6127 assert(Degree != 0 && "Invalid node degree");
6130 // All of P's operands are sorted, so P may sorted now.
6131 P->setNodeId(DAGSize++);
6133 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6134 assert(SortedPos != AllNodes.end() && "Overran node list");
6137 // Update P's outstanding operand count.
6138 P->setNodeId(Degree);
6141 if (I == SortedPos) {
6144 dbgs() << "Overran sorted position:\n";
6145 S->dumprFull(this); dbgs() << "\n";
6146 dbgs() << "Checking if this is due to cycles\n";
6147 checkForCycles(this, true);
6149 llvm_unreachable(nullptr);
6153 assert(SortedPos == AllNodes.end() &&
6154 "Topological sort incomplete!");
6155 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6156 "First node in topological sort is not the entry token!");
6157 assert(AllNodes.front().getNodeId() == 0 &&
6158 "First node in topological sort has non-zero id!");
6159 assert(AllNodes.front().getNumOperands() == 0 &&
6160 "First node in topological sort has operands!");
6161 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6162 "Last node in topologic sort has unexpected id!");
6163 assert(AllNodes.back().use_empty() &&
6164 "Last node in topologic sort has users!");
6165 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6169 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6170 /// value is produced by SD.
6171 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6172 DbgInfo->add(DB, SD, isParameter);
6174 SD->setHasDebugValue(true);
6177 /// TransferDbgValues - Transfer SDDbgValues.
6178 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6179 if (From == To || !From.getNode()->getHasDebugValue())
6181 SDNode *FromNode = From.getNode();
6182 SDNode *ToNode = To.getNode();
6183 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6184 SmallVector<SDDbgValue *, 2> ClonedDVs;
6185 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6187 SDDbgValue *Dbg = *I;
6188 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6189 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6191 Dbg->getOffset(), Dbg->getDebugLoc(),
6193 ClonedDVs.push_back(Clone);
6196 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6197 E = ClonedDVs.end(); I != E; ++I)
6198 AddDbgValue(*I, ToNode, false);
6201 //===----------------------------------------------------------------------===//
6203 //===----------------------------------------------------------------------===//
6205 HandleSDNode::~HandleSDNode() {
6209 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6210 DebugLoc DL, const GlobalValue *GA,
6211 EVT VT, int64_t o, unsigned char TF)
6212 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6216 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6217 SDValue X, unsigned SrcAS,
6219 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6220 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6222 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6223 EVT memvt, MachineMemOperand *mmo)
6224 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6225 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6226 MMO->isNonTemporal(), MMO->isInvariant());
6227 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6228 assert(isNonTemporal() == MMO->isNonTemporal() &&
6229 "Non-temporal encoding error!");
6230 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6233 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6234 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6235 : SDNode(Opc, Order, dl, VTs, Ops),
6236 MemoryVT(memvt), MMO(mmo) {
6237 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6238 MMO->isNonTemporal(), MMO->isInvariant());
6239 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6240 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6243 /// Profile - Gather unique data for the node.
6245 void SDNode::Profile(FoldingSetNodeID &ID) const {
6246 AddNodeIDNode(ID, this);
6251 std::vector<EVT> VTs;
6254 VTs.reserve(MVT::LAST_VALUETYPE);
6255 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6256 VTs.push_back(MVT((MVT::SimpleValueType)i));
6261 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6262 static ManagedStatic<EVTArray> SimpleVTArray;
6263 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6265 /// getValueTypeList - Return a pointer to the specified value type.
6267 const EVT *SDNode::getValueTypeList(EVT VT) {
6268 if (VT.isExtended()) {
6269 sys::SmartScopedLock<true> Lock(*VTMutex);
6270 return &(*EVTs->insert(VT).first);
6272 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6273 "Value type out of range!");
6274 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6278 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6279 /// indicated value. This method ignores uses of other values defined by this
6281 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6282 assert(Value < getNumValues() && "Bad value!");
6284 // TODO: Only iterate over uses of a given value of the node
6285 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6286 if (UI.getUse().getResNo() == Value) {
6293 // Found exactly the right number of uses?
6298 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6299 /// value. This method ignores uses of other values defined by this operation.
6300 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6301 assert(Value < getNumValues() && "Bad value!");
6303 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6304 if (UI.getUse().getResNo() == Value)
6311 /// isOnlyUserOf - Return true if this node is the only use of N.
6313 bool SDNode::isOnlyUserOf(SDNode *N) const {
6315 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6326 /// isOperand - Return true if this node is an operand of N.
6328 bool SDValue::isOperandOf(SDNode *N) const {
6329 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6330 if (*this == N->getOperand(i))
6335 bool SDNode::isOperandOf(SDNode *N) const {
6336 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6337 if (this == N->OperandList[i].getNode())
6342 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6343 /// be a chain) reaches the specified operand without crossing any
6344 /// side-effecting instructions on any chain path. In practice, this looks
6345 /// through token factors and non-volatile loads. In order to remain efficient,
6346 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6347 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6348 unsigned Depth) const {
6349 if (*this == Dest) return true;
6351 // Don't search too deeply, we just want to be able to see through
6352 // TokenFactor's etc.
6353 if (Depth == 0) return false;
6355 // If this is a token factor, all inputs to the TF happen in parallel. If any
6356 // of the operands of the TF does not reach dest, then we cannot do the xform.
6357 if (getOpcode() == ISD::TokenFactor) {
6358 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6359 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6364 // Loads don't have side effects, look through them.
6365 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6366 if (!Ld->isVolatile())
6367 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6372 /// hasPredecessor - Return true if N is a predecessor of this node.
6373 /// N is either an operand of this node, or can be reached by recursively
6374 /// traversing up the operands.
6375 /// NOTE: This is an expensive method. Use it carefully.
6376 bool SDNode::hasPredecessor(const SDNode *N) const {
6377 SmallPtrSet<const SDNode *, 32> Visited;
6378 SmallVector<const SDNode *, 16> Worklist;
6379 return hasPredecessorHelper(N, Visited, Worklist);
6383 SDNode::hasPredecessorHelper(const SDNode *N,
6384 SmallPtrSet<const SDNode *, 32> &Visited,
6385 SmallVectorImpl<const SDNode *> &Worklist) const {
6386 if (Visited.empty()) {
6387 Worklist.push_back(this);
6389 // Take a look in the visited set. If we've already encountered this node
6390 // we needn't search further.
6391 if (Visited.count(N))
6395 // Haven't visited N yet. Continue the search.
6396 while (!Worklist.empty()) {
6397 const SDNode *M = Worklist.pop_back_val();
6398 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6399 SDNode *Op = M->getOperand(i).getNode();
6400 if (Visited.insert(Op))
6401 Worklist.push_back(Op);
6410 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6411 assert(Num < NumOperands && "Invalid child # of SDNode!");
6412 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6415 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6416 assert(N->getNumValues() == 1 &&
6417 "Can't unroll a vector with multiple results!");
6419 EVT VT = N->getValueType(0);
6420 unsigned NE = VT.getVectorNumElements();
6421 EVT EltVT = VT.getVectorElementType();
6424 SmallVector<SDValue, 8> Scalars;
6425 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6427 // If ResNE is 0, fully unroll the vector op.
6430 else if (NE > ResNE)
6434 for (i= 0; i != NE; ++i) {
6435 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6436 SDValue Operand = N->getOperand(j);
6437 EVT OperandVT = Operand.getValueType();
6438 if (OperandVT.isVector()) {
6439 // A vector operand; extract a single element.
6440 const TargetLowering *TLI = TM.getTargetLowering();
6441 EVT OperandEltVT = OperandVT.getVectorElementType();
6442 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6445 getConstant(i, TLI->getVectorIdxTy()));
6447 // A scalar operand; just use it as is.
6448 Operands[j] = Operand;
6452 switch (N->getOpcode()) {
6454 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6457 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6464 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6465 getShiftAmountOperand(Operands[0].getValueType(),
6468 case ISD::SIGN_EXTEND_INREG:
6469 case ISD::FP_ROUND_INREG: {
6470 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6471 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6473 getValueType(ExtVT)));
6478 for (; i < ResNE; ++i)
6479 Scalars.push_back(getUNDEF(EltVT));
6481 return getNode(ISD::BUILD_VECTOR, dl,
6482 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6486 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6487 /// location that is 'Dist' units away from the location that the 'Base' load
6488 /// is loading from.
6489 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6490 unsigned Bytes, int Dist) const {
6491 if (LD->getChain() != Base->getChain())
6493 EVT VT = LD->getValueType(0);
6494 if (VT.getSizeInBits() / 8 != Bytes)
6497 SDValue Loc = LD->getOperand(1);
6498 SDValue BaseLoc = Base->getOperand(1);
6499 if (Loc.getOpcode() == ISD::FrameIndex) {
6500 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6502 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6503 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6504 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6505 int FS = MFI->getObjectSize(FI);
6506 int BFS = MFI->getObjectSize(BFI);
6507 if (FS != BFS || FS != (int)Bytes) return false;
6508 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6512 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6513 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6516 const GlobalValue *GV1 = nullptr;
6517 const GlobalValue *GV2 = nullptr;
6518 int64_t Offset1 = 0;
6519 int64_t Offset2 = 0;
6520 const TargetLowering *TLI = TM.getTargetLowering();
6521 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6522 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6523 if (isGA1 && isGA2 && GV1 == GV2)
6524 return Offset1 == (Offset2 + Dist*Bytes);
6529 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6530 /// it cannot be inferred.
6531 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6532 // If this is a GlobalAddress + cst, return the alignment.
6533 const GlobalValue *GV;
6534 int64_t GVOffset = 0;
6535 const TargetLowering *TLI = TM.getTargetLowering();
6536 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6537 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6538 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6539 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6540 TLI->getDataLayout());
6541 unsigned AlignBits = KnownZero.countTrailingOnes();
6542 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6544 return MinAlign(Align, GVOffset);
6547 // If this is a direct reference to a stack slot, use information about the
6548 // stack slot's alignment.
6549 int FrameIdx = 1 << 31;
6550 int64_t FrameOffset = 0;
6551 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6552 FrameIdx = FI->getIndex();
6553 } else if (isBaseWithConstantOffset(Ptr) &&
6554 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6556 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6557 FrameOffset = Ptr.getConstantOperandVal(1);
6560 if (FrameIdx != (1 << 31)) {
6561 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6562 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6570 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6571 /// which is split (or expanded) into two not necessarily identical pieces.
6572 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6573 // Currently all types are split in half.
6575 if (!VT.isVector()) {
6576 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6578 unsigned NumElements = VT.getVectorNumElements();
6579 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6580 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6583 return std::make_pair(LoVT, HiVT);
6586 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6588 std::pair<SDValue, SDValue>
6589 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6591 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6592 N.getValueType().getVectorNumElements() &&
6593 "More vector elements requested than available!");
6595 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6596 getConstant(0, TLI->getVectorIdxTy()));
6597 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6598 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6599 return std::make_pair(Lo, Hi);
6602 void SelectionDAG::ExtractVectorElements(SDValue Op,
6603 SmallVectorImpl<SDValue> &Args,
6604 unsigned Start, unsigned Count) {
6605 EVT VT = Op.getValueType();
6607 Count = VT.getVectorNumElements();
6609 EVT EltVT = VT.getVectorElementType();
6610 EVT IdxTy = TLI->getVectorIdxTy();
6612 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6613 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6614 Op, getConstant(i, IdxTy)));
6618 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6619 unsigned GlobalAddressSDNode::getAddressSpace() const {
6620 return getGlobal()->getType()->getAddressSpace();
6624 Type *ConstantPoolSDNode::getType() const {
6625 if (isMachineConstantPoolEntry())
6626 return Val.MachineCPVal->getType();
6627 return Val.ConstVal->getType();
6630 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6632 unsigned &SplatBitSize,
6634 unsigned MinSplatBits,
6635 bool isBigEndian) const {
6636 EVT VT = getValueType(0);
6637 assert(VT.isVector() && "Expected a vector type");
6638 unsigned sz = VT.getSizeInBits();
6639 if (MinSplatBits > sz)
6642 SplatValue = APInt(sz, 0);
6643 SplatUndef = APInt(sz, 0);
6645 // Get the bits. Bits with undefined values (when the corresponding element
6646 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6647 // in SplatValue. If any of the values are not constant, give up and return
6649 unsigned int nOps = getNumOperands();
6650 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6651 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6653 for (unsigned j = 0; j < nOps; ++j) {
6654 unsigned i = isBigEndian ? nOps-1-j : j;
6655 SDValue OpVal = getOperand(i);
6656 unsigned BitPos = j * EltBitSize;
6658 if (OpVal.getOpcode() == ISD::UNDEF)
6659 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6660 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6661 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6662 zextOrTrunc(sz) << BitPos;
6663 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6664 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6669 // The build_vector is all constants or undefs. Find the smallest element
6670 // size that splats the vector.
6672 HasAnyUndefs = (SplatUndef != 0);
6675 unsigned HalfSize = sz / 2;
6676 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6677 APInt LowValue = SplatValue.trunc(HalfSize);
6678 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6679 APInt LowUndef = SplatUndef.trunc(HalfSize);
6681 // If the two halves do not match (ignoring undef bits), stop here.
6682 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6683 MinSplatBits > HalfSize)
6686 SplatValue = HighValue | LowValue;
6687 SplatUndef = HighUndef & LowUndef;
6696 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6697 if (UndefElements) {
6698 UndefElements->clear();
6699 UndefElements->resize(getNumOperands());
6702 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6703 SDValue Op = getOperand(i);
6704 if (Op.getOpcode() == ISD::UNDEF) {
6706 (*UndefElements)[i] = true;
6707 } else if (!Splatted) {
6709 } else if (Splatted != Op) {
6715 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6716 "Can only have a splat without a constant for all undefs.");
6717 return getOperand(0);
6724 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6725 return dyn_cast_or_null<ConstantSDNode>(
6726 getSplatValue(UndefElements).getNode());
6730 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6731 return dyn_cast_or_null<ConstantFPSDNode>(
6732 getSplatValue(UndefElements).getNode());
6735 bool BuildVectorSDNode::isConstant() const {
6736 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6737 unsigned Opc = getOperand(i).getOpcode();
6738 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6744 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6745 // Find the first non-undef value in the shuffle mask.
6747 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6750 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6752 // Make sure all remaining elements are either undef or the same as the first
6754 for (int Idx = Mask[i]; i != e; ++i)
6755 if (Mask[i] >= 0 && Mask[i] != Idx)
6761 static void checkForCyclesHelper(const SDNode *N,
6762 SmallPtrSet<const SDNode*, 32> &Visited,
6763 SmallPtrSet<const SDNode*, 32> &Checked,
6764 const llvm::SelectionDAG *DAG) {
6765 // If this node has already been checked, don't check it again.
6766 if (Checked.count(N))
6769 // If a node has already been visited on this depth-first walk, reject it as
6771 if (!Visited.insert(N)) {
6772 errs() << "Detected cycle in SelectionDAG\n";
6773 dbgs() << "Offending node:\n";
6774 N->dumprFull(DAG); dbgs() << "\n";
6778 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6779 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6786 void llvm::checkForCycles(const llvm::SDNode *N,
6787 const llvm::SelectionDAG *DAG,
6795 assert(N && "Checking nonexistent SDNode");
6796 SmallPtrSet<const SDNode*, 32> visited;
6797 SmallPtrSet<const SDNode*, 32> checked;
6798 checkForCyclesHelper(N, visited, checked, DAG);
6803 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6804 checkForCycles(DAG->getRoot().getNode(), DAG, force);