1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAG class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/SelectionDAG.h"
15 #include "SDNodeDbgValue.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/Analysis/ValueTracking.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineConstantPool.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineModuleInfo.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DebugInfo.h"
30 #include "llvm/IR/DerivedTypes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/GlobalAlias.h"
33 #include "llvm/IR/GlobalVariable.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/Support/CommandLine.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Support/ManagedStatic.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Mutex.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include "llvm/Target/TargetInstrInfo.h"
43 #include "llvm/Target/TargetIntrinsicInfo.h"
44 #include "llvm/Target/TargetLowering.h"
45 #include "llvm/Target/TargetMachine.h"
46 #include "llvm/Target/TargetOptions.h"
47 #include "llvm/Target/TargetRegisterInfo.h"
48 #include "llvm/Target/TargetSelectionDAGInfo.h"
54 /// makeVTList - Return an instance of the SDVTList struct initialized with the
55 /// specified members.
56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
57 SDVTList Res = {VTs, NumVTs};
61 // Default null implementations of the callbacks.
62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
65 //===----------------------------------------------------------------------===//
66 // ConstantFPSDNode Class
67 //===----------------------------------------------------------------------===//
69 /// isExactlyValue - We don't rely on operator== working on double values, as
70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
71 /// As such, this method can be used to do an exact bit-for-bit comparison of
72 /// two floating point values.
73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
74 return getValueAPF().bitwiseIsEqual(V);
77 bool ConstantFPSDNode::isValueValidForType(EVT VT,
79 assert(VT.isFloatingPoint() && "Can only convert between FP types");
81 // convert modifies in place, so make a copy.
82 APFloat Val2 = APFloat(Val);
84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
85 APFloat::rmNearestTiesToEven,
90 //===----------------------------------------------------------------------===//
92 //===----------------------------------------------------------------------===//
94 /// isBuildVectorAllOnes - Return true if the specified node is a
95 /// BUILD_VECTOR where all of the elements are ~0 or undef.
96 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
97 // Look through a bit convert.
98 if (N->getOpcode() == ISD::BITCAST)
99 N = N->getOperand(0).getNode();
101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
103 unsigned i = 0, e = N->getNumOperands();
105 // Skip over all of the undef values.
106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
109 // Do not accept an all-undef vector.
110 if (i == e) return false;
112 // Do not accept build_vectors that aren't all constants or which have non-~0
113 // elements. We have to be a bit careful here, as the type of the constant
114 // may not be the same as the type of the vector elements due to type
115 // legalization (the elements are promoted to a legal type for the target and
116 // a vector of a type may be legal when the base element type is not).
117 // We only want to check enough bits to cover the vector elements, because
118 // we care if the resultant vector is all ones, not whether the individual
120 SDValue NotZero = N->getOperand(i);
121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
123 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
131 // Okay, we have at least one ~0 value, check to see if the rest match or are
132 // undefs. Even with the above element type twiddling, this should be OK, as
133 // the same type legalization should have applied to all the elements.
134 for (++i; i != e; ++i)
135 if (N->getOperand(i) != NotZero &&
136 N->getOperand(i).getOpcode() != ISD::UNDEF)
142 /// isBuildVectorAllZeros - Return true if the specified node is a
143 /// BUILD_VECTOR where all of the elements are 0 or undef.
144 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
145 // Look through a bit convert.
146 if (N->getOpcode() == ISD::BITCAST)
147 N = N->getOperand(0).getNode();
149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
151 bool IsAllUndef = true;
152 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
153 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept build_vectors that aren't all constants or which have non-0
157 // elements. We have to be a bit careful here, as the type of the constant
158 // may not be the same as the type of the vector elements due to type
159 // legalization (the elements are promoted to a legal type for the target
160 // and a vector of a type may be legal when the base element type is not).
161 // We only want to check enough bits to cover the vector elements, because
162 // we care if the resultant vector is all zeros, not whether the individual
164 SDValue Zero = N->getOperand(i);
165 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
166 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
167 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
169 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
170 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
176 // Do not accept an all-undef vector.
182 /// \brief Return true if the specified node is a BUILD_VECTOR node of
183 /// all ConstantSDNode or undef.
184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
185 if (N->getOpcode() != ISD::BUILD_VECTOR)
188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
189 SDValue Op = N->getOperand(i);
190 if (Op.getOpcode() == ISD::UNDEF)
192 if (!isa<ConstantSDNode>(Op))
198 /// isScalarToVector - Return true if the specified node is a
199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
200 /// element is not an undef.
201 bool ISD::isScalarToVector(const SDNode *N) {
202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
205 if (N->getOpcode() != ISD::BUILD_VECTOR)
207 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
209 unsigned NumElems = N->getNumOperands();
212 for (unsigned i = 1; i < NumElems; ++i) {
213 SDValue V = N->getOperand(i);
214 if (V.getOpcode() != ISD::UNDEF)
220 /// allOperandsUndef - Return true if the node has at least one operand
221 /// and all operands of the specified node are ISD::UNDEF.
222 bool ISD::allOperandsUndef(const SDNode *N) {
223 // Return false if the node has no operands.
224 // This is "logically inconsistent" with the definition of "all" but
225 // is probably the desired behavior.
226 if (N->getNumOperands() == 0)
229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
230 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
236 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
239 return ISD::ANY_EXTEND;
241 return ISD::SIGN_EXTEND;
243 return ISD::ZERO_EXTEND;
248 llvm_unreachable("Invalid LoadExtType");
251 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
252 /// when given the operation for (X op Y).
253 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
254 // To perform this operation, we just need to swap the L and G bits of the
256 unsigned OldL = (Operation >> 2) & 1;
257 unsigned OldG = (Operation >> 1) & 1;
258 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
259 (OldL << 1) | // New G bit
260 (OldG << 2)); // New L bit.
263 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
264 /// 'op' is a valid SetCC operation.
265 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
266 unsigned Operation = Op;
268 Operation ^= 7; // Flip L, G, E bits, but not U.
270 Operation ^= 15; // Flip all of the condition bits.
272 if (Operation > ISD::SETTRUE2)
273 Operation &= ~8; // Don't let N and U bits get set.
275 return ISD::CondCode(Operation);
279 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
280 /// signed operation and 2 if the result is an unsigned comparison. Return zero
281 /// if the operation does not depend on the sign of the input (setne and seteq).
282 static int isSignedOp(ISD::CondCode Opcode) {
284 default: llvm_unreachable("Illegal integer setcc operation!");
286 case ISD::SETNE: return 0;
290 case ISD::SETGE: return 1;
294 case ISD::SETUGE: return 2;
298 /// getSetCCOrOperation - Return the result of a logical OR between different
299 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
300 /// returns SETCC_INVALID if it is not possible to represent the resultant
302 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
304 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
305 // Cannot fold a signed integer setcc with an unsigned integer setcc.
306 return ISD::SETCC_INVALID;
308 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
310 // If the N and U bits get set then the resultant comparison DOES suddenly
311 // care about orderedness, and is true when ordered.
312 if (Op > ISD::SETTRUE2)
313 Op &= ~16; // Clear the U bit if the N bit is set.
315 // Canonicalize illegal integer setcc's.
316 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
319 return ISD::CondCode(Op);
322 /// getSetCCAndOperation - Return the result of a logical AND between different
323 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
324 /// function returns zero if it is not possible to represent the resultant
326 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
328 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
329 // Cannot fold a signed setcc with an unsigned setcc.
330 return ISD::SETCC_INVALID;
332 // Combine all of the condition bits.
333 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
335 // Canonicalize illegal integer setcc's.
339 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
340 case ISD::SETOEQ: // SETEQ & SETU[LG]E
341 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
342 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
343 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
350 //===----------------------------------------------------------------------===//
351 // SDNode Profile Support
352 //===----------------------------------------------------------------------===//
354 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
356 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
360 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
361 /// solely with their pointer.
362 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
363 ID.AddPointer(VTList.VTs);
366 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
368 static void AddNodeIDOperands(FoldingSetNodeID &ID,
369 ArrayRef<SDValue> Ops) {
370 for (auto& Op : Ops) {
371 ID.AddPointer(Op.getNode());
372 ID.AddInteger(Op.getResNo());
376 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
378 static void AddNodeIDOperands(FoldingSetNodeID &ID,
379 ArrayRef<SDUse> Ops) {
380 for (auto& Op : Ops) {
381 ID.AddPointer(Op.getNode());
382 ID.AddInteger(Op.getResNo());
386 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw,
390 ID.AddBoolean(exact);
393 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos
394 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode,
395 bool nuw, bool nsw, bool exact) {
396 if (isBinOpWithFlags(Opcode))
397 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
400 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
401 SDVTList VTList, ArrayRef<SDValue> OpList) {
402 AddNodeIDOpcode(ID, OpC);
403 AddNodeIDValueTypes(ID, VTList);
404 AddNodeIDOperands(ID, OpList);
407 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
409 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
410 switch (N->getOpcode()) {
411 case ISD::TargetExternalSymbol:
412 case ISD::ExternalSymbol:
413 llvm_unreachable("Should only be used on nodes with operands");
414 default: break; // Normal nodes don't need extra info.
415 case ISD::TargetConstant:
416 case ISD::Constant: {
417 const ConstantSDNode *C = cast<ConstantSDNode>(N);
418 ID.AddPointer(C->getConstantIntValue());
419 ID.AddBoolean(C->isOpaque());
422 case ISD::TargetConstantFP:
423 case ISD::ConstantFP: {
424 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
427 case ISD::TargetGlobalAddress:
428 case ISD::GlobalAddress:
429 case ISD::TargetGlobalTLSAddress:
430 case ISD::GlobalTLSAddress: {
431 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
432 ID.AddPointer(GA->getGlobal());
433 ID.AddInteger(GA->getOffset());
434 ID.AddInteger(GA->getTargetFlags());
435 ID.AddInteger(GA->getAddressSpace());
438 case ISD::BasicBlock:
439 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
442 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
444 case ISD::RegisterMask:
445 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
448 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
450 case ISD::FrameIndex:
451 case ISD::TargetFrameIndex:
452 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
455 case ISD::TargetJumpTable:
456 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
457 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
459 case ISD::ConstantPool:
460 case ISD::TargetConstantPool: {
461 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
462 ID.AddInteger(CP->getAlignment());
463 ID.AddInteger(CP->getOffset());
464 if (CP->isMachineConstantPoolEntry())
465 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
467 ID.AddPointer(CP->getConstVal());
468 ID.AddInteger(CP->getTargetFlags());
471 case ISD::TargetIndex: {
472 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
473 ID.AddInteger(TI->getIndex());
474 ID.AddInteger(TI->getOffset());
475 ID.AddInteger(TI->getTargetFlags());
479 const LoadSDNode *LD = cast<LoadSDNode>(N);
480 ID.AddInteger(LD->getMemoryVT().getRawBits());
481 ID.AddInteger(LD->getRawSubclassData());
482 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
486 const StoreSDNode *ST = cast<StoreSDNode>(N);
487 ID.AddInteger(ST->getMemoryVT().getRawBits());
488 ID.AddInteger(ST->getRawSubclassData());
489 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
500 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N);
501 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(),
502 BinNode->hasNoSignedWrap(), BinNode->isExact());
505 case ISD::ATOMIC_CMP_SWAP:
506 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
507 case ISD::ATOMIC_SWAP:
508 case ISD::ATOMIC_LOAD_ADD:
509 case ISD::ATOMIC_LOAD_SUB:
510 case ISD::ATOMIC_LOAD_AND:
511 case ISD::ATOMIC_LOAD_OR:
512 case ISD::ATOMIC_LOAD_XOR:
513 case ISD::ATOMIC_LOAD_NAND:
514 case ISD::ATOMIC_LOAD_MIN:
515 case ISD::ATOMIC_LOAD_MAX:
516 case ISD::ATOMIC_LOAD_UMIN:
517 case ISD::ATOMIC_LOAD_UMAX:
518 case ISD::ATOMIC_LOAD:
519 case ISD::ATOMIC_STORE: {
520 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
521 ID.AddInteger(AT->getMemoryVT().getRawBits());
522 ID.AddInteger(AT->getRawSubclassData());
523 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
526 case ISD::PREFETCH: {
527 const MemSDNode *PF = cast<MemSDNode>(N);
528 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
531 case ISD::VECTOR_SHUFFLE: {
532 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
533 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
535 ID.AddInteger(SVN->getMaskElt(i));
538 case ISD::TargetBlockAddress:
539 case ISD::BlockAddress: {
540 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
541 ID.AddPointer(BA->getBlockAddress());
542 ID.AddInteger(BA->getOffset());
543 ID.AddInteger(BA->getTargetFlags());
546 } // end switch (N->getOpcode())
548 // Target specific memory nodes could also have address spaces to check.
549 if (N->isTargetMemoryOpcode())
550 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
553 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
555 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
556 AddNodeIDOpcode(ID, N->getOpcode());
557 // Add the return value info.
558 AddNodeIDValueTypes(ID, N->getVTList());
559 // Add the operand info.
560 AddNodeIDOperands(ID, N->ops());
562 // Handle SDNode leafs with special info.
563 AddNodeIDCustom(ID, N);
566 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
567 /// the CSE map that carries volatility, temporalness, indexing mode, and
568 /// extension/truncation information.
570 static inline unsigned
571 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
572 bool isNonTemporal, bool isInvariant) {
573 assert((ConvType & 3) == ConvType &&
574 "ConvType may not require more than 2 bits!");
575 assert((AM & 7) == AM &&
576 "AM may not require more than 3 bits!");
580 (isNonTemporal << 6) |
584 //===----------------------------------------------------------------------===//
585 // SelectionDAG Class
586 //===----------------------------------------------------------------------===//
588 /// doNotCSE - Return true if CSE should not be performed for this node.
589 static bool doNotCSE(SDNode *N) {
590 if (N->getValueType(0) == MVT::Glue)
591 return true; // Never CSE anything that produces a flag.
593 switch (N->getOpcode()) {
595 case ISD::HANDLENODE:
597 return true; // Never CSE these nodes.
600 // Check that remaining values produced are not flags.
601 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
602 if (N->getValueType(i) == MVT::Glue)
603 return true; // Never CSE anything that produces a flag.
608 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
610 void SelectionDAG::RemoveDeadNodes() {
611 // Create a dummy node (which is not added to allnodes), that adds a reference
612 // to the root node, preventing it from being deleted.
613 HandleSDNode Dummy(getRoot());
615 SmallVector<SDNode*, 128> DeadNodes;
617 // Add all obviously-dead nodes to the DeadNodes worklist.
618 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
620 DeadNodes.push_back(I);
622 RemoveDeadNodes(DeadNodes);
624 // If the root changed (e.g. it was a dead load, update the root).
625 setRoot(Dummy.getValue());
628 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
629 /// given list, and any nodes that become unreachable as a result.
630 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
632 // Process the worklist, deleting the nodes and adding their uses to the
634 while (!DeadNodes.empty()) {
635 SDNode *N = DeadNodes.pop_back_val();
637 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
638 DUL->NodeDeleted(N, nullptr);
640 // Take the node out of the appropriate CSE map.
641 RemoveNodeFromCSEMaps(N);
643 // Next, brutally remove the operand list. This is safe to do, as there are
644 // no cycles in the graph.
645 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
647 SDNode *Operand = Use.getNode();
650 // Now that we removed this operand, see if there are no uses of it left.
651 if (Operand->use_empty())
652 DeadNodes.push_back(Operand);
659 void SelectionDAG::RemoveDeadNode(SDNode *N){
660 SmallVector<SDNode*, 16> DeadNodes(1, N);
662 // Create a dummy node that adds a reference to the root node, preventing
663 // it from being deleted. (This matters if the root is an operand of the
665 HandleSDNode Dummy(getRoot());
667 RemoveDeadNodes(DeadNodes);
670 void SelectionDAG::DeleteNode(SDNode *N) {
671 // First take this out of the appropriate CSE map.
672 RemoveNodeFromCSEMaps(N);
674 // Finally, remove uses due to operands of this node, remove from the
675 // AllNodes list, and delete the node.
676 DeleteNodeNotInCSEMaps(N);
679 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
680 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
681 assert(N->use_empty() && "Cannot delete a node that is not dead!");
683 // Drop all of the operands and decrement used node's use counts.
689 void SelectionDAG::DeallocateNode(SDNode *N) {
690 if (N->OperandsNeedDelete)
691 delete[] N->OperandList;
693 // Set the opcode to DELETED_NODE to help catch bugs when node
694 // memory is reallocated.
695 N->NodeType = ISD::DELETED_NODE;
697 NodeAllocator.Deallocate(AllNodes.remove(N));
699 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
700 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
701 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
702 DbgVals[i]->setIsInvalidated();
705 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
706 /// correspond to it. This is useful when we're about to delete or repurpose
707 /// the node. We don't want future request for structurally identical nodes
708 /// to return N anymore.
709 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
711 switch (N->getOpcode()) {
712 case ISD::HANDLENODE: return false; // noop.
714 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
715 "Cond code doesn't exist!");
716 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
717 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
719 case ISD::ExternalSymbol:
720 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
722 case ISD::TargetExternalSymbol: {
723 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
724 Erased = TargetExternalSymbols.erase(
725 std::pair<std::string,unsigned char>(ESN->getSymbol(),
726 ESN->getTargetFlags()));
729 case ISD::VALUETYPE: {
730 EVT VT = cast<VTSDNode>(N)->getVT();
731 if (VT.isExtended()) {
732 Erased = ExtendedValueTypeNodes.erase(VT);
734 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
735 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
740 // Remove it from the CSE Map.
741 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
742 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
743 Erased = CSEMap.RemoveNode(N);
747 // Verify that the node was actually in one of the CSE maps, unless it has a
748 // flag result (which cannot be CSE'd) or is one of the special cases that are
749 // not subject to CSE.
750 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
751 !N->isMachineOpcode() && !doNotCSE(N)) {
754 llvm_unreachable("Node is not in map!");
760 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
761 /// maps and modified in place. Add it back to the CSE maps, unless an identical
762 /// node already exists, in which case transfer all its users to the existing
763 /// node. This transfer can potentially trigger recursive merging.
766 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
767 // For node types that aren't CSE'd, just act as if no identical node
770 SDNode *Existing = CSEMap.GetOrInsertNode(N);
772 // If there was already an existing matching node, use ReplaceAllUsesWith
773 // to replace the dead one with the existing one. This can cause
774 // recursive merging of other unrelated nodes down the line.
775 ReplaceAllUsesWith(N, Existing);
777 // N is now dead. Inform the listeners and delete it.
778 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
779 DUL->NodeDeleted(N, Existing);
780 DeleteNodeNotInCSEMaps(N);
785 // If the node doesn't already exist, we updated it. Inform listeners.
786 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
790 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
791 /// were replaced with those specified. If this node is never memoized,
792 /// return null, otherwise return a pointer to the slot it would take. If a
793 /// node already exists with these operands, the slot will be non-null.
794 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
799 SDValue Ops[] = { Op };
801 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
802 AddNodeIDCustom(ID, N);
803 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
807 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
808 /// were replaced with those specified. If this node is never memoized,
809 /// return null, otherwise return a pointer to the slot it would take. If a
810 /// node already exists with these operands, the slot will be non-null.
811 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
812 SDValue Op1, SDValue Op2,
817 SDValue Ops[] = { Op1, Op2 };
819 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
820 AddNodeIDCustom(ID, N);
821 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
826 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
827 /// were replaced with those specified. If this node is never memoized,
828 /// return null, otherwise return a pointer to the slot it would take. If a
829 /// node already exists with these operands, the slot will be non-null.
830 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
836 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
837 AddNodeIDCustom(ID, N);
838 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
843 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
844 static void VerifyNodeCommon(SDNode *N) {
845 switch (N->getOpcode()) {
848 case ISD::BUILD_PAIR: {
849 EVT VT = N->getValueType(0);
850 assert(N->getNumValues() == 1 && "Too many results!");
851 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
852 "Wrong return type!");
853 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
854 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
855 "Mismatched operand types!");
856 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
857 "Wrong operand type!");
858 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
859 "Wrong return type size");
862 case ISD::BUILD_VECTOR: {
863 assert(N->getNumValues() == 1 && "Too many results!");
864 assert(N->getValueType(0).isVector() && "Wrong return type!");
865 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
866 "Wrong number of operands!");
867 EVT EltVT = N->getValueType(0).getVectorElementType();
868 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
869 assert((I->getValueType() == EltVT ||
870 (EltVT.isInteger() && I->getValueType().isInteger() &&
871 EltVT.bitsLE(I->getValueType()))) &&
872 "Wrong operand type!");
873 assert(I->getValueType() == N->getOperand(0).getValueType() &&
874 "Operands must all have the same type");
881 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
882 static void VerifySDNode(SDNode *N) {
883 // The SDNode allocators cannot be used to allocate nodes with fields that are
884 // not present in an SDNode!
885 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
886 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
887 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
888 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
889 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
890 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
891 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
892 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
893 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
894 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
895 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
896 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
897 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
898 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
899 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
900 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
901 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
902 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
903 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
908 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
910 static void VerifyMachineNode(SDNode *N) {
911 // The MachineNode allocators cannot be used to allocate nodes with fields
912 // that are not present in a MachineNode!
913 // Currently there are no such nodes.
919 /// getEVTAlignment - Compute the default alignment value for the
922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
923 Type *Ty = VT == MVT::iPTR ?
924 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
925 VT.getTypeForEVT(*getContext());
927 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
930 // EntryNode could meaningfully have debug info if we can find it...
931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
932 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
935 UpdateListeners(nullptr) {
936 AllNodes.push_back(&EntryNode);
937 DbgInfo = new SDDbgInfo();
940 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
943 Context = &mf.getFunction()->getContext();
946 SelectionDAG::~SelectionDAG() {
947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
952 void SelectionDAG::allnodes_clear() {
953 assert(&*AllNodes.begin() == &EntryNode);
954 AllNodes.remove(AllNodes.begin());
955 while (!AllNodes.empty())
956 DeallocateNode(AllNodes.begin());
959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
960 SDVTList VTs, SDValue N1,
961 SDValue N2, bool nuw, bool nsw,
963 if (isBinOpWithFlags(Opcode)) {
964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
966 FN->setHasNoUnsignedWrap(nuw);
967 FN->setHasNoSignedWrap(nsw);
968 FN->setIsExact(exact);
973 BinarySDNode *N = new (NodeAllocator)
974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
978 void SelectionDAG::clear() {
980 OperandAllocator.Reset();
983 ExtendedValueTypeNodes.clear();
984 ExternalSymbols.clear();
985 TargetExternalSymbols.clear();
986 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
987 static_cast<CondCodeSDNode*>(nullptr));
988 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
989 static_cast<SDNode*>(nullptr));
991 EntryNode.UseList = nullptr;
992 AllNodes.push_back(&EntryNode);
993 Root = getEntryNode();
997 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
998 return VT.bitsGT(Op.getValueType()) ?
999 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1000 getNode(ISD::TRUNCATE, DL, VT, Op);
1003 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1004 return VT.bitsGT(Op.getValueType()) ?
1005 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1006 getNode(ISD::TRUNCATE, DL, VT, Op);
1009 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1010 return VT.bitsGT(Op.getValueType()) ?
1011 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1012 getNode(ISD::TRUNCATE, DL, VT, Op);
1015 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
1016 if (VT.bitsLE(Op.getValueType()))
1017 return getNode(ISD::TRUNCATE, SL, VT, Op);
1019 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
1020 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1023 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1024 assert(!VT.isVector() &&
1025 "getZeroExtendInReg should use the vector element type instead of "
1026 "the vector type!");
1027 if (Op.getValueType() == VT) return Op;
1028 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1029 APInt Imm = APInt::getLowBitsSet(BitWidth,
1030 VT.getSizeInBits());
1031 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1032 getConstant(Imm, Op.getValueType()));
1035 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1037 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1038 EVT EltVT = VT.getScalarType();
1040 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1041 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1044 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1045 EVT EltVT = VT.getScalarType();
1047 switch (TLI->getBooleanContents(VT.isVector())) {
1048 case TargetLowering::ZeroOrOneBooleanContent:
1049 case TargetLowering::UndefinedBooleanContent:
1050 TrueValue = getConstant(1, VT);
1052 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1053 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1057 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1060 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1061 EVT EltVT = VT.getScalarType();
1062 assert((EltVT.getSizeInBits() >= 64 ||
1063 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1064 "getConstant with a uint64_t value that doesn't fit in the type!");
1065 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1068 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1070 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1073 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1075 assert(VT.isInteger() && "Cannot create FP integer constant!");
1077 EVT EltVT = VT.getScalarType();
1078 const ConstantInt *Elt = &Val;
1080 const TargetLowering *TLI = TM.getTargetLowering();
1082 // In some cases the vector type is legal but the element type is illegal and
1083 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1084 // inserted value (the type does not need to match the vector element type).
1085 // Any extra bits introduced will be truncated away.
1086 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1087 TargetLowering::TypePromoteInteger) {
1088 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1089 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1090 Elt = ConstantInt::get(*getContext(), NewVal);
1092 // In other cases the element type is illegal and needs to be expanded, for
1093 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1094 // the value into n parts and use a vector type with n-times the elements.
1095 // Then bitcast to the type requested.
1096 // Legalizing constants too early makes the DAGCombiner's job harder so we
1097 // only legalize if the DAG tells us we must produce legal types.
1098 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1099 TLI->getTypeAction(*getContext(), EltVT) ==
1100 TargetLowering::TypeExpandInteger) {
1101 APInt NewVal = Elt->getValue();
1102 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1103 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1104 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1105 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1107 // Check the temporary vector is the correct size. If this fails then
1108 // getTypeToTransformTo() probably returned a type whose size (in bits)
1109 // isn't a power-of-2 factor of the requested type size.
1110 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1112 SmallVector<SDValue, 2> EltParts;
1113 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1114 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1115 .trunc(ViaEltSizeInBits),
1116 ViaEltVT, isT, isO));
1119 // EltParts is currently in little endian order. If we actually want
1120 // big-endian order then reverse it now.
1121 if (TLI->isBigEndian())
1122 std::reverse(EltParts.begin(), EltParts.end());
1124 // The elements must be reversed when the element order is different
1125 // to the endianness of the elements (because the BITCAST is itself a
1126 // vector shuffle in this situation). However, we do not need any code to
1127 // perform this reversal because getConstant() is producing a vector
1129 // This situation occurs in MIPS MSA.
1131 SmallVector<SDValue, 8> Ops;
1132 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1133 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1135 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1136 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1141 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1142 "APInt size does not match type size!");
1143 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1144 FoldingSetNodeID ID;
1145 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1149 SDNode *N = nullptr;
1150 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1152 return SDValue(N, 0);
1155 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1156 CSEMap.InsertNode(N, IP);
1157 AllNodes.push_back(N);
1160 SDValue Result(N, 0);
1161 if (VT.isVector()) {
1162 SmallVector<SDValue, 8> Ops;
1163 Ops.assign(VT.getVectorNumElements(), Result);
1164 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1169 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1170 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1174 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1175 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1178 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1179 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1181 EVT EltVT = VT.getScalarType();
1183 // Do the map lookup using the actual bit pattern for the floating point
1184 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1185 // we don't have issues with SNANs.
1186 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1187 FoldingSetNodeID ID;
1188 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1191 SDNode *N = nullptr;
1192 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1194 return SDValue(N, 0);
1197 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1198 CSEMap.InsertNode(N, IP);
1199 AllNodes.push_back(N);
1202 SDValue Result(N, 0);
1203 if (VT.isVector()) {
1204 SmallVector<SDValue, 8> Ops;
1205 Ops.assign(VT.getVectorNumElements(), Result);
1206 // FIXME SDLoc info might be appropriate here
1207 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1212 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1213 EVT EltVT = VT.getScalarType();
1214 if (EltVT==MVT::f32)
1215 return getConstantFP(APFloat((float)Val), VT, isTarget);
1216 else if (EltVT==MVT::f64)
1217 return getConstantFP(APFloat(Val), VT, isTarget);
1218 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1221 APFloat apf = APFloat(Val);
1222 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1224 return getConstantFP(apf, VT, isTarget);
1226 llvm_unreachable("Unsupported type in getConstantFP");
1229 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1230 EVT VT, int64_t Offset,
1232 unsigned char TargetFlags) {
1233 assert((TargetFlags == 0 || isTargetGA) &&
1234 "Cannot set target flags on target-independent globals");
1235 const TargetLowering *TLI = TM.getTargetLowering();
1237 // Truncate (with sign-extension) the offset value to the pointer size.
1238 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1240 Offset = SignExtend64(Offset, BitWidth);
1243 if (GV->isThreadLocal())
1244 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1246 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1248 FoldingSetNodeID ID;
1249 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1251 ID.AddInteger(Offset);
1252 ID.AddInteger(TargetFlags);
1253 ID.AddInteger(GV->getType()->getAddressSpace());
1255 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1256 return SDValue(E, 0);
1258 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1259 DL.getDebugLoc(), GV, VT,
1260 Offset, TargetFlags);
1261 CSEMap.InsertNode(N, IP);
1262 AllNodes.push_back(N);
1263 return SDValue(N, 0);
1266 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1267 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1268 FoldingSetNodeID ID;
1269 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1272 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1273 return SDValue(E, 0);
1275 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1276 CSEMap.InsertNode(N, IP);
1277 AllNodes.push_back(N);
1278 return SDValue(N, 0);
1281 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1282 unsigned char TargetFlags) {
1283 assert((TargetFlags == 0 || isTarget) &&
1284 "Cannot set target flags on target-independent jump tables");
1285 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1286 FoldingSetNodeID ID;
1287 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1289 ID.AddInteger(TargetFlags);
1291 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1292 return SDValue(E, 0);
1294 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1296 CSEMap.InsertNode(N, IP);
1297 AllNodes.push_back(N);
1298 return SDValue(N, 0);
1301 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1302 unsigned Alignment, int Offset,
1304 unsigned char TargetFlags) {
1305 assert((TargetFlags == 0 || isTarget) &&
1306 "Cannot set target flags on target-independent globals");
1309 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1310 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1311 FoldingSetNodeID ID;
1312 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1313 ID.AddInteger(Alignment);
1314 ID.AddInteger(Offset);
1316 ID.AddInteger(TargetFlags);
1318 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1319 return SDValue(E, 0);
1321 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1322 Alignment, TargetFlags);
1323 CSEMap.InsertNode(N, IP);
1324 AllNodes.push_back(N);
1325 return SDValue(N, 0);
1329 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1330 unsigned Alignment, int Offset,
1332 unsigned char TargetFlags) {
1333 assert((TargetFlags == 0 || isTarget) &&
1334 "Cannot set target flags on target-independent globals");
1337 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1338 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1339 FoldingSetNodeID ID;
1340 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1341 ID.AddInteger(Alignment);
1342 ID.AddInteger(Offset);
1343 C->addSelectionDAGCSEId(ID);
1344 ID.AddInteger(TargetFlags);
1346 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1347 return SDValue(E, 0);
1349 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1350 Alignment, TargetFlags);
1351 CSEMap.InsertNode(N, IP);
1352 AllNodes.push_back(N);
1353 return SDValue(N, 0);
1356 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1357 unsigned char TargetFlags) {
1358 FoldingSetNodeID ID;
1359 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1360 ID.AddInteger(Index);
1361 ID.AddInteger(Offset);
1362 ID.AddInteger(TargetFlags);
1364 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1365 return SDValue(E, 0);
1367 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1369 CSEMap.InsertNode(N, IP);
1370 AllNodes.push_back(N);
1371 return SDValue(N, 0);
1374 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1375 FoldingSetNodeID ID;
1376 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1379 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1380 return SDValue(E, 0);
1382 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1383 CSEMap.InsertNode(N, IP);
1384 AllNodes.push_back(N);
1385 return SDValue(N, 0);
1388 SDValue SelectionDAG::getValueType(EVT VT) {
1389 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1390 ValueTypeNodes.size())
1391 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1393 SDNode *&N = VT.isExtended() ?
1394 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1396 if (N) return SDValue(N, 0);
1397 N = new (NodeAllocator) VTSDNode(VT);
1398 AllNodes.push_back(N);
1399 return SDValue(N, 0);
1402 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1403 SDNode *&N = ExternalSymbols[Sym];
1404 if (N) return SDValue(N, 0);
1405 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1406 AllNodes.push_back(N);
1407 return SDValue(N, 0);
1410 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1411 unsigned char TargetFlags) {
1413 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1415 if (N) return SDValue(N, 0);
1416 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1417 AllNodes.push_back(N);
1418 return SDValue(N, 0);
1421 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1422 if ((unsigned)Cond >= CondCodeNodes.size())
1423 CondCodeNodes.resize(Cond+1);
1425 if (!CondCodeNodes[Cond]) {
1426 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1427 CondCodeNodes[Cond] = N;
1428 AllNodes.push_back(N);
1431 return SDValue(CondCodeNodes[Cond], 0);
1434 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1435 // the shuffle mask M that point at N1 to point at N2, and indices that point
1436 // N2 to point at N1.
1437 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1439 int NElts = M.size();
1440 for (int i = 0; i != NElts; ++i) {
1448 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1449 SDValue N2, const int *Mask) {
1450 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1451 "Invalid VECTOR_SHUFFLE");
1453 // Canonicalize shuffle undef, undef -> undef
1454 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1455 return getUNDEF(VT);
1457 // Validate that all indices in Mask are within the range of the elements
1458 // input to the shuffle.
1459 unsigned NElts = VT.getVectorNumElements();
1460 SmallVector<int, 8> MaskVec;
1461 for (unsigned i = 0; i != NElts; ++i) {
1462 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1463 MaskVec.push_back(Mask[i]);
1466 // Canonicalize shuffle v, v -> v, undef
1469 for (unsigned i = 0; i != NElts; ++i)
1470 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1473 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1474 if (N1.getOpcode() == ISD::UNDEF)
1475 commuteShuffle(N1, N2, MaskVec);
1477 // Canonicalize all index into lhs, -> shuffle lhs, undef
1478 // Canonicalize all index into rhs, -> shuffle rhs, undef
1479 bool AllLHS = true, AllRHS = true;
1480 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1481 for (unsigned i = 0; i != NElts; ++i) {
1482 if (MaskVec[i] >= (int)NElts) {
1487 } else if (MaskVec[i] >= 0) {
1491 if (AllLHS && AllRHS)
1492 return getUNDEF(VT);
1493 if (AllLHS && !N2Undef)
1497 commuteShuffle(N1, N2, MaskVec);
1500 // If Identity shuffle return that node.
1501 bool Identity = true;
1502 for (unsigned i = 0; i != NElts; ++i) {
1503 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1505 if (Identity && NElts)
1508 // Shuffling a constant splat doesn't change the result.
1509 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1510 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1513 FoldingSetNodeID ID;
1514 SDValue Ops[2] = { N1, N2 };
1515 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1516 for (unsigned i = 0; i != NElts; ++i)
1517 ID.AddInteger(MaskVec[i]);
1520 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1521 return SDValue(E, 0);
1523 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1524 // SDNode doesn't have access to it. This memory will be "leaked" when
1525 // the node is deallocated, but recovered when the NodeAllocator is released.
1526 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1527 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1529 ShuffleVectorSDNode *N =
1530 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1531 dl.getDebugLoc(), N1, N2,
1533 CSEMap.InsertNode(N, IP);
1534 AllNodes.push_back(N);
1535 return SDValue(N, 0);
1538 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1539 SDValue Val, SDValue DTy,
1540 SDValue STy, SDValue Rnd, SDValue Sat,
1541 ISD::CvtCode Code) {
1542 // If the src and dest types are the same and the conversion is between
1543 // integer types of the same sign or two floats, no conversion is necessary.
1545 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1548 FoldingSetNodeID ID;
1549 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1550 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1552 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1553 return SDValue(E, 0);
1555 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1558 CSEMap.InsertNode(N, IP);
1559 AllNodes.push_back(N);
1560 return SDValue(N, 0);
1563 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1564 FoldingSetNodeID ID;
1565 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1566 ID.AddInteger(RegNo);
1568 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1569 return SDValue(E, 0);
1571 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1572 CSEMap.InsertNode(N, IP);
1573 AllNodes.push_back(N);
1574 return SDValue(N, 0);
1577 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1578 FoldingSetNodeID ID;
1579 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1580 ID.AddPointer(RegMask);
1582 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1583 return SDValue(E, 0);
1585 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1586 CSEMap.InsertNode(N, IP);
1587 AllNodes.push_back(N);
1588 return SDValue(N, 0);
1591 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1592 FoldingSetNodeID ID;
1593 SDValue Ops[] = { Root };
1594 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1595 ID.AddPointer(Label);
1597 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1598 return SDValue(E, 0);
1600 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1601 dl.getDebugLoc(), Root, Label);
1602 CSEMap.InsertNode(N, IP);
1603 AllNodes.push_back(N);
1604 return SDValue(N, 0);
1608 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1611 unsigned char TargetFlags) {
1612 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1614 FoldingSetNodeID ID;
1615 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1617 ID.AddInteger(Offset);
1618 ID.AddInteger(TargetFlags);
1620 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1621 return SDValue(E, 0);
1623 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1625 CSEMap.InsertNode(N, IP);
1626 AllNodes.push_back(N);
1627 return SDValue(N, 0);
1630 SDValue SelectionDAG::getSrcValue(const Value *V) {
1631 assert((!V || V->getType()->isPointerTy()) &&
1632 "SrcValue is not a pointer?");
1634 FoldingSetNodeID ID;
1635 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1639 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1640 return SDValue(E, 0);
1642 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1643 CSEMap.InsertNode(N, IP);
1644 AllNodes.push_back(N);
1645 return SDValue(N, 0);
1648 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1649 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1650 FoldingSetNodeID ID;
1651 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1655 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1656 return SDValue(E, 0);
1658 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1659 CSEMap.InsertNode(N, IP);
1660 AllNodes.push_back(N);
1661 return SDValue(N, 0);
1664 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1665 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1666 unsigned SrcAS, unsigned DestAS) {
1667 SDValue Ops[] = {Ptr};
1668 FoldingSetNodeID ID;
1669 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1670 ID.AddInteger(SrcAS);
1671 ID.AddInteger(DestAS);
1674 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1675 return SDValue(E, 0);
1677 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1679 VT, Ptr, SrcAS, DestAS);
1680 CSEMap.InsertNode(N, IP);
1681 AllNodes.push_back(N);
1682 return SDValue(N, 0);
1685 /// getShiftAmountOperand - Return the specified value casted to
1686 /// the target's desired shift amount type.
1687 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1688 EVT OpTy = Op.getValueType();
1689 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1690 if (OpTy == ShTy || OpTy.isVector()) return Op;
1692 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1693 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1696 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1697 /// specified value type.
1698 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1699 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1700 unsigned ByteSize = VT.getStoreSize();
1701 Type *Ty = VT.getTypeForEVT(*getContext());
1702 const TargetLowering *TLI = TM.getTargetLowering();
1703 unsigned StackAlign =
1704 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1706 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1707 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1710 /// CreateStackTemporary - Create a stack temporary suitable for holding
1711 /// either of the specified value types.
1712 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1713 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1714 VT2.getStoreSizeInBits())/8;
1715 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1716 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1717 const TargetLowering *TLI = TM.getTargetLowering();
1718 const DataLayout *TD = TLI->getDataLayout();
1719 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1720 TD->getPrefTypeAlignment(Ty2));
1722 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1723 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1724 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1727 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1728 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1729 // These setcc operations always fold.
1733 case ISD::SETFALSE2: return getConstant(0, VT);
1735 case ISD::SETTRUE2: {
1736 const TargetLowering *TLI = TM.getTargetLowering();
1737 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1739 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1752 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1756 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1757 const APInt &C2 = N2C->getAPIntValue();
1758 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1759 const APInt &C1 = N1C->getAPIntValue();
1762 default: llvm_unreachable("Unknown integer setcc!");
1763 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1764 case ISD::SETNE: return getConstant(C1 != C2, VT);
1765 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1766 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1767 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1768 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1769 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1770 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1771 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1772 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1776 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1777 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1778 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1781 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1782 return getUNDEF(VT);
1784 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1785 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1786 return getUNDEF(VT);
1788 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1789 R==APFloat::cmpLessThan, VT);
1790 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1791 return getUNDEF(VT);
1793 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1794 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1795 return getUNDEF(VT);
1797 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1798 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1799 return getUNDEF(VT);
1801 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1802 R==APFloat::cmpEqual, VT);
1803 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1804 return getUNDEF(VT);
1806 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1807 R==APFloat::cmpEqual, VT);
1808 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1809 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1810 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1811 R==APFloat::cmpEqual, VT);
1812 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1813 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1814 R==APFloat::cmpLessThan, VT);
1815 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1816 R==APFloat::cmpUnordered, VT);
1817 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1818 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1821 // Ensure that the constant occurs on the RHS.
1822 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1823 MVT CompVT = N1.getValueType().getSimpleVT();
1824 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1827 return getSetCC(dl, VT, N2, N1, SwappedCond);
1831 // Could not fold it.
1835 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1836 /// use this predicate to simplify operations downstream.
1837 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1838 // This predicate is not safe for vector operations.
1839 if (Op.getValueType().isVector())
1842 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1843 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1846 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1847 /// this predicate to simplify operations downstream. Mask is known to be zero
1848 /// for bits that V cannot have.
1849 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1850 unsigned Depth) const {
1851 APInt KnownZero, KnownOne;
1852 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1853 return (KnownZero & Mask) == Mask;
1856 /// Determine which bits of Op are known to be either zero or one and return
1857 /// them in the KnownZero/KnownOne bitsets.
1858 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1859 APInt &KnownOne, unsigned Depth) const {
1860 const TargetLowering *TLI = TM.getTargetLowering();
1861 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1863 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1865 return; // Limit search depth.
1867 APInt KnownZero2, KnownOne2;
1869 switch (Op.getOpcode()) {
1871 // We know all of the bits for a constant!
1872 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1873 KnownZero = ~KnownOne;
1876 // If either the LHS or the RHS are Zero, the result is zero.
1877 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1878 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1880 // Output known-1 bits are only known if set in both the LHS & RHS.
1881 KnownOne &= KnownOne2;
1882 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1883 KnownZero |= KnownZero2;
1886 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1887 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1889 // Output known-0 bits are only known if clear in both the LHS & RHS.
1890 KnownZero &= KnownZero2;
1891 // Output known-1 are known to be set if set in either the LHS | RHS.
1892 KnownOne |= KnownOne2;
1895 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1896 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1898 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1899 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1900 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1901 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1902 KnownZero = KnownZeroOut;
1906 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1907 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1909 // If low bits are zero in either operand, output low known-0 bits.
1910 // Also compute a conserative estimate for high known-0 bits.
1911 // More trickiness is possible, but this is sufficient for the
1912 // interesting case of alignment computation.
1913 KnownOne.clearAllBits();
1914 unsigned TrailZ = KnownZero.countTrailingOnes() +
1915 KnownZero2.countTrailingOnes();
1916 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1917 KnownZero2.countLeadingOnes(),
1918 BitWidth) - BitWidth;
1920 TrailZ = std::min(TrailZ, BitWidth);
1921 LeadZ = std::min(LeadZ, BitWidth);
1922 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1923 APInt::getHighBitsSet(BitWidth, LeadZ);
1927 // For the purposes of computing leading zeros we can conservatively
1928 // treat a udiv as a logical right shift by the power of 2 known to
1929 // be less than the denominator.
1930 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1931 unsigned LeadZ = KnownZero2.countLeadingOnes();
1933 KnownOne2.clearAllBits();
1934 KnownZero2.clearAllBits();
1935 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1936 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1937 if (RHSUnknownLeadingOnes != BitWidth)
1938 LeadZ = std::min(BitWidth,
1939 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1941 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1945 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1946 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1948 // Only known if known in both the LHS and RHS.
1949 KnownOne &= KnownOne2;
1950 KnownZero &= KnownZero2;
1952 case ISD::SELECT_CC:
1953 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1954 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1956 // Only known if known in both the LHS and RHS.
1957 KnownOne &= KnownOne2;
1958 KnownZero &= KnownZero2;
1966 if (Op.getResNo() != 1)
1968 // The boolean result conforms to getBooleanContents. Fall through.
1970 // If we know the result of a setcc has the top bits zero, use this info.
1971 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1972 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1973 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1976 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1977 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1978 unsigned ShAmt = SA->getZExtValue();
1980 // If the shift count is an invalid immediate, don't do anything.
1981 if (ShAmt >= BitWidth)
1984 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1985 KnownZero <<= ShAmt;
1987 // low bits known zero.
1988 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1992 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1993 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1994 unsigned ShAmt = SA->getZExtValue();
1996 // If the shift count is an invalid immediate, don't do anything.
1997 if (ShAmt >= BitWidth)
2000 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2001 KnownZero = KnownZero.lshr(ShAmt);
2002 KnownOne = KnownOne.lshr(ShAmt);
2004 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2005 KnownZero |= HighBits; // High bits known zero.
2009 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2010 unsigned ShAmt = SA->getZExtValue();
2012 // If the shift count is an invalid immediate, don't do anything.
2013 if (ShAmt >= BitWidth)
2016 // If any of the demanded bits are produced by the sign extension, we also
2017 // demand the input sign bit.
2018 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2020 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2021 KnownZero = KnownZero.lshr(ShAmt);
2022 KnownOne = KnownOne.lshr(ShAmt);
2024 // Handle the sign bits.
2025 APInt SignBit = APInt::getSignBit(BitWidth);
2026 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2028 if (KnownZero.intersects(SignBit)) {
2029 KnownZero |= HighBits; // New bits are known zero.
2030 } else if (KnownOne.intersects(SignBit)) {
2031 KnownOne |= HighBits; // New bits are known one.
2035 case ISD::SIGN_EXTEND_INREG: {
2036 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2037 unsigned EBits = EVT.getScalarType().getSizeInBits();
2039 // Sign extension. Compute the demanded bits in the result that are not
2040 // present in the input.
2041 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2043 APInt InSignBit = APInt::getSignBit(EBits);
2044 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2046 // If the sign extended bits are demanded, we know that the sign
2048 InSignBit = InSignBit.zext(BitWidth);
2049 if (NewBits.getBoolValue())
2050 InputDemandedBits |= InSignBit;
2052 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2053 KnownOne &= InputDemandedBits;
2054 KnownZero &= InputDemandedBits;
2056 // If the sign bit of the input is known set or clear, then we know the
2057 // top bits of the result.
2058 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2059 KnownZero |= NewBits;
2060 KnownOne &= ~NewBits;
2061 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2062 KnownOne |= NewBits;
2063 KnownZero &= ~NewBits;
2064 } else { // Input sign bit unknown
2065 KnownZero &= ~NewBits;
2066 KnownOne &= ~NewBits;
2071 case ISD::CTTZ_ZERO_UNDEF:
2073 case ISD::CTLZ_ZERO_UNDEF:
2075 unsigned LowBits = Log2_32(BitWidth)+1;
2076 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2077 KnownOne.clearAllBits();
2081 LoadSDNode *LD = cast<LoadSDNode>(Op);
2082 // If this is a ZEXTLoad and we are looking at the loaded value.
2083 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2084 EVT VT = LD->getMemoryVT();
2085 unsigned MemBits = VT.getScalarType().getSizeInBits();
2086 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2087 } else if (const MDNode *Ranges = LD->getRanges()) {
2088 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2092 case ISD::ZERO_EXTEND: {
2093 EVT InVT = Op.getOperand(0).getValueType();
2094 unsigned InBits = InVT.getScalarType().getSizeInBits();
2095 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2096 KnownZero = KnownZero.trunc(InBits);
2097 KnownOne = KnownOne.trunc(InBits);
2098 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2099 KnownZero = KnownZero.zext(BitWidth);
2100 KnownOne = KnownOne.zext(BitWidth);
2101 KnownZero |= NewBits;
2104 case ISD::SIGN_EXTEND: {
2105 EVT InVT = Op.getOperand(0).getValueType();
2106 unsigned InBits = InVT.getScalarType().getSizeInBits();
2107 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2109 KnownZero = KnownZero.trunc(InBits);
2110 KnownOne = KnownOne.trunc(InBits);
2111 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2113 // Note if the sign bit is known to be zero or one.
2114 bool SignBitKnownZero = KnownZero.isNegative();
2115 bool SignBitKnownOne = KnownOne.isNegative();
2117 KnownZero = KnownZero.zext(BitWidth);
2118 KnownOne = KnownOne.zext(BitWidth);
2120 // If the sign bit is known zero or one, the top bits match.
2121 if (SignBitKnownZero)
2122 KnownZero |= NewBits;
2123 else if (SignBitKnownOne)
2124 KnownOne |= NewBits;
2127 case ISD::ANY_EXTEND: {
2128 EVT InVT = Op.getOperand(0).getValueType();
2129 unsigned InBits = InVT.getScalarType().getSizeInBits();
2130 KnownZero = KnownZero.trunc(InBits);
2131 KnownOne = KnownOne.trunc(InBits);
2132 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2133 KnownZero = KnownZero.zext(BitWidth);
2134 KnownOne = KnownOne.zext(BitWidth);
2137 case ISD::TRUNCATE: {
2138 EVT InVT = Op.getOperand(0).getValueType();
2139 unsigned InBits = InVT.getScalarType().getSizeInBits();
2140 KnownZero = KnownZero.zext(InBits);
2141 KnownOne = KnownOne.zext(InBits);
2142 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2143 KnownZero = KnownZero.trunc(BitWidth);
2144 KnownOne = KnownOne.trunc(BitWidth);
2147 case ISD::AssertZext: {
2148 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2149 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2150 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2151 KnownZero |= (~InMask);
2152 KnownOne &= (~KnownZero);
2156 // All bits are zero except the low bit.
2157 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2161 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2162 // We know that the top bits of C-X are clear if X contains less bits
2163 // than C (i.e. no wrap-around can happen). For example, 20-X is
2164 // positive if we can prove that X is >= 0 and < 16.
2165 if (CLHS->getAPIntValue().isNonNegative()) {
2166 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2167 // NLZ can't be BitWidth with no sign bit
2168 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2169 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2171 // If all of the MaskV bits are known to be zero, then we know the
2172 // output top bits are zero, because we now know that the output is
2174 if ((KnownZero2 & MaskV) == MaskV) {
2175 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2176 // Top bits known zero.
2177 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2185 // Output known-0 bits are known if clear or set in both the low clear bits
2186 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2187 // low 3 bits clear.
2188 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2189 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2191 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2192 KnownZeroOut = std::min(KnownZeroOut,
2193 KnownZero2.countTrailingOnes());
2195 if (Op.getOpcode() == ISD::ADD) {
2196 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2200 // With ADDE, a carry bit may be added in, so we can only use this
2201 // information if we know (at least) that the low two bits are clear. We
2202 // then return to the caller that the low bit is unknown but that other bits
2204 if (KnownZeroOut >= 2) // ADDE
2205 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2209 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2210 const APInt &RA = Rem->getAPIntValue().abs();
2211 if (RA.isPowerOf2()) {
2212 APInt LowBits = RA - 1;
2213 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2215 // The low bits of the first operand are unchanged by the srem.
2216 KnownZero = KnownZero2 & LowBits;
2217 KnownOne = KnownOne2 & LowBits;
2219 // If the first operand is non-negative or has all low bits zero, then
2220 // the upper bits are all zero.
2221 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2222 KnownZero |= ~LowBits;
2224 // If the first operand is negative and not all low bits are zero, then
2225 // the upper bits are all one.
2226 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2227 KnownOne |= ~LowBits;
2228 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2233 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2234 const APInt &RA = Rem->getAPIntValue();
2235 if (RA.isPowerOf2()) {
2236 APInt LowBits = (RA - 1);
2237 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2239 // The upper bits are all zero, the lower ones are unchanged.
2240 KnownZero = KnownZero2 | ~LowBits;
2241 KnownOne = KnownOne2 & LowBits;
2246 // Since the result is less than or equal to either operand, any leading
2247 // zero bits in either operand must also exist in the result.
2248 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2249 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2251 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2252 KnownZero2.countLeadingOnes());
2253 KnownOne.clearAllBits();
2254 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2257 case ISD::FrameIndex:
2258 case ISD::TargetFrameIndex:
2259 if (unsigned Align = InferPtrAlignment(Op)) {
2260 // The low bits are known zero if the pointer is aligned.
2261 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2267 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2270 case ISD::INTRINSIC_WO_CHAIN:
2271 case ISD::INTRINSIC_W_CHAIN:
2272 case ISD::INTRINSIC_VOID:
2273 // Allow the target to implement this method for its nodes.
2274 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2278 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2281 /// ComputeNumSignBits - Return the number of times the sign bit of the
2282 /// register is replicated into the other bits. We know that at least 1 bit
2283 /// is always equal to the sign bit (itself), but other cases can give us
2284 /// information. For example, immediately after an "SRA X, 2", we know that
2285 /// the top 3 bits are all equal to each other, so we return 3.
2286 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2287 const TargetLowering *TLI = TM.getTargetLowering();
2288 EVT VT = Op.getValueType();
2289 assert(VT.isInteger() && "Invalid VT!");
2290 unsigned VTBits = VT.getScalarType().getSizeInBits();
2292 unsigned FirstAnswer = 1;
2295 return 1; // Limit search depth.
2297 switch (Op.getOpcode()) {
2299 case ISD::AssertSext:
2300 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2301 return VTBits-Tmp+1;
2302 case ISD::AssertZext:
2303 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2306 case ISD::Constant: {
2307 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2308 return Val.getNumSignBits();
2311 case ISD::SIGN_EXTEND:
2313 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2314 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2316 case ISD::SIGN_EXTEND_INREG:
2317 // Max of the input and what this extends.
2319 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2322 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2323 return std::max(Tmp, Tmp2);
2326 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2327 // SRA X, C -> adds C sign bits.
2328 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2329 Tmp += C->getZExtValue();
2330 if (Tmp > VTBits) Tmp = VTBits;
2334 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2335 // shl destroys sign bits.
2336 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2337 if (C->getZExtValue() >= VTBits || // Bad shift.
2338 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2339 return Tmp - C->getZExtValue();
2344 case ISD::XOR: // NOT is handled here.
2345 // Logical binary ops preserve the number of sign bits at the worst.
2346 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2348 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2349 FirstAnswer = std::min(Tmp, Tmp2);
2350 // We computed what we know about the sign bits as our first
2351 // answer. Now proceed to the generic code that uses
2352 // computeKnownBits, and pick whichever answer is better.
2357 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2358 if (Tmp == 1) return 1; // Early out.
2359 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2360 return std::min(Tmp, Tmp2);
2368 if (Op.getResNo() != 1)
2370 // The boolean result conforms to getBooleanContents. Fall through.
2372 // If setcc returns 0/-1, all bits are sign bits.
2373 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2374 TargetLowering::ZeroOrNegativeOneBooleanContent)
2379 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2380 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2382 // Handle rotate right by N like a rotate left by 32-N.
2383 if (Op.getOpcode() == ISD::ROTR)
2384 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2386 // If we aren't rotating out all of the known-in sign bits, return the
2387 // number that are left. This handles rotl(sext(x), 1) for example.
2388 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2389 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2393 // Add can have at most one carry bit. Thus we know that the output
2394 // is, at worst, one more bit than the inputs.
2395 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2396 if (Tmp == 1) return 1; // Early out.
2398 // Special case decrementing a value (ADD X, -1):
2399 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2400 if (CRHS->isAllOnesValue()) {
2401 APInt KnownZero, KnownOne;
2402 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2404 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2406 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2409 // If we are subtracting one from a positive number, there is no carry
2410 // out of the result.
2411 if (KnownZero.isNegative())
2415 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2416 if (Tmp2 == 1) return 1;
2417 return std::min(Tmp, Tmp2)-1;
2420 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2421 if (Tmp2 == 1) return 1;
2424 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2425 if (CLHS->isNullValue()) {
2426 APInt KnownZero, KnownOne;
2427 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2428 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2430 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2433 // If the input is known to be positive (the sign bit is known clear),
2434 // the output of the NEG has the same number of sign bits as the input.
2435 if (KnownZero.isNegative())
2438 // Otherwise, we treat this like a SUB.
2441 // Sub can have at most one carry bit. Thus we know that the output
2442 // is, at worst, one more bit than the inputs.
2443 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2444 if (Tmp == 1) return 1; // Early out.
2445 return std::min(Tmp, Tmp2)-1;
2447 // FIXME: it's tricky to do anything useful for this, but it is an important
2448 // case for targets like X86.
2452 // If we are looking at the loaded value of the SDNode.
2453 if (Op.getResNo() == 0) {
2454 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2455 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2456 unsigned ExtType = LD->getExtensionType();
2459 case ISD::SEXTLOAD: // '17' bits known
2460 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2461 return VTBits-Tmp+1;
2462 case ISD::ZEXTLOAD: // '16' bits known
2463 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2469 // Allow the target to implement this method for its nodes.
2470 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2471 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2472 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2473 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2474 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2475 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2478 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2479 // use this information.
2480 APInt KnownZero, KnownOne;
2481 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2484 if (KnownZero.isNegative()) { // sign bit is 0
2486 } else if (KnownOne.isNegative()) { // sign bit is 1;
2493 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2494 // the number of identical bits in the top of the input value.
2496 Mask <<= Mask.getBitWidth()-VTBits;
2497 // Return # leading zeros. We use 'min' here in case Val was zero before
2498 // shifting. We don't want to return '64' as for an i32 "0".
2499 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2502 /// isBaseWithConstantOffset - Return true if the specified operand is an
2503 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2504 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2505 /// semantics as an ADD. This handles the equivalence:
2506 /// X|Cst == X+Cst iff X&Cst = 0.
2507 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2508 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2509 !isa<ConstantSDNode>(Op.getOperand(1)))
2512 if (Op.getOpcode() == ISD::OR &&
2513 !MaskedValueIsZero(Op.getOperand(0),
2514 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2521 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2522 // If we're told that NaNs won't happen, assume they won't.
2523 if (getTarget().Options.NoNaNsFPMath)
2526 // If the value is a constant, we can obviously see if it is a NaN or not.
2527 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2528 return !C->getValueAPF().isNaN();
2530 // TODO: Recognize more cases here.
2535 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2536 // If the value is a constant, we can obviously see if it is a zero or not.
2537 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2538 return !C->isZero();
2540 // TODO: Recognize more cases here.
2541 switch (Op.getOpcode()) {
2544 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2545 return !C->isNullValue();
2552 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2553 // Check the obvious case.
2554 if (A == B) return true;
2556 // For for negative and positive zero.
2557 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2558 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2559 if (CA->isZero() && CB->isZero()) return true;
2561 // Otherwise they may not be equal.
2565 /// getNode - Gets or creates the specified node.
2567 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2568 FoldingSetNodeID ID;
2569 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2571 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2572 return SDValue(E, 0);
2574 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2575 DL.getDebugLoc(), getVTList(VT));
2576 CSEMap.InsertNode(N, IP);
2578 AllNodes.push_back(N);
2582 return SDValue(N, 0);
2585 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2586 EVT VT, SDValue Operand) {
2587 // Constant fold unary operations with an integer constant operand. Even
2588 // opaque constant will be folded, because the folding of unary operations
2589 // doesn't create new constants with different values. Nevertheless, the
2590 // opaque flag is preserved during folding to prevent future folding with
2592 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2593 const APInt &Val = C->getAPIntValue();
2596 case ISD::SIGN_EXTEND:
2597 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2598 C->isTargetOpcode(), C->isOpaque());
2599 case ISD::ANY_EXTEND:
2600 case ISD::ZERO_EXTEND:
2602 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2603 C->isTargetOpcode(), C->isOpaque());
2604 case ISD::UINT_TO_FP:
2605 case ISD::SINT_TO_FP: {
2606 APFloat apf(EVTToAPFloatSemantics(VT),
2607 APInt::getNullValue(VT.getSizeInBits()));
2608 (void)apf.convertFromAPInt(Val,
2609 Opcode==ISD::SINT_TO_FP,
2610 APFloat::rmNearestTiesToEven);
2611 return getConstantFP(apf, VT);
2614 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2615 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2616 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2617 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2620 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2623 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2626 case ISD::CTLZ_ZERO_UNDEF:
2627 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2630 case ISD::CTTZ_ZERO_UNDEF:
2631 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2636 // Constant fold unary operations with a floating point constant operand.
2637 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2638 APFloat V = C->getValueAPF(); // make copy
2642 return getConstantFP(V, VT);
2645 return getConstantFP(V, VT);
2647 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2648 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2649 return getConstantFP(V, VT);
2653 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2654 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2655 return getConstantFP(V, VT);
2659 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2660 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2661 return getConstantFP(V, VT);
2664 case ISD::FP_EXTEND: {
2666 // This can return overflow, underflow, or inexact; we don't care.
2667 // FIXME need to be more flexible about rounding mode.
2668 (void)V.convert(EVTToAPFloatSemantics(VT),
2669 APFloat::rmNearestTiesToEven, &ignored);
2670 return getConstantFP(V, VT);
2672 case ISD::FP_TO_SINT:
2673 case ISD::FP_TO_UINT: {
2676 assert(integerPartWidth >= 64);
2677 // FIXME need to be more flexible about rounding mode.
2678 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2679 Opcode==ISD::FP_TO_SINT,
2680 APFloat::rmTowardZero, &ignored);
2681 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2683 APInt api(VT.getSizeInBits(), x);
2684 return getConstant(api, VT);
2687 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2688 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2689 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2690 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2695 unsigned OpOpcode = Operand.getNode()->getOpcode();
2697 case ISD::TokenFactor:
2698 case ISD::MERGE_VALUES:
2699 case ISD::CONCAT_VECTORS:
2700 return Operand; // Factor, merge or concat of one node? No need.
2701 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2702 case ISD::FP_EXTEND:
2703 assert(VT.isFloatingPoint() &&
2704 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2705 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2706 assert((!VT.isVector() ||
2707 VT.getVectorNumElements() ==
2708 Operand.getValueType().getVectorNumElements()) &&
2709 "Vector element count mismatch!");
2710 if (Operand.getOpcode() == ISD::UNDEF)
2711 return getUNDEF(VT);
2713 case ISD::SIGN_EXTEND:
2714 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2715 "Invalid SIGN_EXTEND!");
2716 if (Operand.getValueType() == VT) return Operand; // noop extension
2717 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2718 "Invalid sext node, dst < src!");
2719 assert((!VT.isVector() ||
2720 VT.getVectorNumElements() ==
2721 Operand.getValueType().getVectorNumElements()) &&
2722 "Vector element count mismatch!");
2723 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2724 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2725 else if (OpOpcode == ISD::UNDEF)
2726 // sext(undef) = 0, because the top bits will all be the same.
2727 return getConstant(0, VT);
2729 case ISD::ZERO_EXTEND:
2730 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2731 "Invalid ZERO_EXTEND!");
2732 if (Operand.getValueType() == VT) return Operand; // noop extension
2733 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2734 "Invalid zext node, dst < src!");
2735 assert((!VT.isVector() ||
2736 VT.getVectorNumElements() ==
2737 Operand.getValueType().getVectorNumElements()) &&
2738 "Vector element count mismatch!");
2739 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2740 return getNode(ISD::ZERO_EXTEND, DL, VT,
2741 Operand.getNode()->getOperand(0));
2742 else if (OpOpcode == ISD::UNDEF)
2743 // zext(undef) = 0, because the top bits will be zero.
2744 return getConstant(0, VT);
2746 case ISD::ANY_EXTEND:
2747 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2748 "Invalid ANY_EXTEND!");
2749 if (Operand.getValueType() == VT) return Operand; // noop extension
2750 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2751 "Invalid anyext node, dst < src!");
2752 assert((!VT.isVector() ||
2753 VT.getVectorNumElements() ==
2754 Operand.getValueType().getVectorNumElements()) &&
2755 "Vector element count mismatch!");
2757 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2758 OpOpcode == ISD::ANY_EXTEND)
2759 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2760 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2761 else if (OpOpcode == ISD::UNDEF)
2762 return getUNDEF(VT);
2764 // (ext (trunx x)) -> x
2765 if (OpOpcode == ISD::TRUNCATE) {
2766 SDValue OpOp = Operand.getNode()->getOperand(0);
2767 if (OpOp.getValueType() == VT)
2772 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2773 "Invalid TRUNCATE!");
2774 if (Operand.getValueType() == VT) return Operand; // noop truncate
2775 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2776 "Invalid truncate node, src < dst!");
2777 assert((!VT.isVector() ||
2778 VT.getVectorNumElements() ==
2779 Operand.getValueType().getVectorNumElements()) &&
2780 "Vector element count mismatch!");
2781 if (OpOpcode == ISD::TRUNCATE)
2782 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2783 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2784 OpOpcode == ISD::ANY_EXTEND) {
2785 // If the source is smaller than the dest, we still need an extend.
2786 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2787 .bitsLT(VT.getScalarType()))
2788 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2789 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2790 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2791 return Operand.getNode()->getOperand(0);
2793 if (OpOpcode == ISD::UNDEF)
2794 return getUNDEF(VT);
2797 // Basic sanity checking.
2798 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2799 && "Cannot BITCAST between types of different sizes!");
2800 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2801 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2802 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2803 if (OpOpcode == ISD::UNDEF)
2804 return getUNDEF(VT);
2806 case ISD::SCALAR_TO_VECTOR:
2807 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2808 (VT.getVectorElementType() == Operand.getValueType() ||
2809 (VT.getVectorElementType().isInteger() &&
2810 Operand.getValueType().isInteger() &&
2811 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2812 "Illegal SCALAR_TO_VECTOR node!");
2813 if (OpOpcode == ISD::UNDEF)
2814 return getUNDEF(VT);
2815 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2816 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2817 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2818 Operand.getConstantOperandVal(1) == 0 &&
2819 Operand.getOperand(0).getValueType() == VT)
2820 return Operand.getOperand(0);
2823 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2824 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2825 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2826 Operand.getNode()->getOperand(0));
2827 if (OpOpcode == ISD::FNEG) // --X -> X
2828 return Operand.getNode()->getOperand(0);
2831 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2832 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2837 SDVTList VTs = getVTList(VT);
2838 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2839 FoldingSetNodeID ID;
2840 SDValue Ops[1] = { Operand };
2841 AddNodeIDNode(ID, Opcode, VTs, Ops);
2843 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2844 return SDValue(E, 0);
2846 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2847 DL.getDebugLoc(), VTs, Operand);
2848 CSEMap.InsertNode(N, IP);
2850 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2851 DL.getDebugLoc(), VTs, Operand);
2854 AllNodes.push_back(N);
2858 return SDValue(N, 0);
2861 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2862 SDNode *Cst1, SDNode *Cst2) {
2863 // If the opcode is a target-specific ISD node, there's nothing we can
2864 // do here and the operand rules may not line up with the below, so
2866 if (Opcode >= ISD::BUILTIN_OP_END)
2869 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2870 SmallVector<SDValue, 4> Outputs;
2871 EVT SVT = VT.getScalarType();
2873 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2874 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2875 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2878 if (Scalar1 && Scalar2)
2879 // Scalar instruction.
2880 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2882 // For vectors extract each constant element into Inputs so we can constant
2883 // fold them individually.
2884 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2885 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2889 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2891 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2892 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2893 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2894 if (!V1 || !V2) // Not a constant, bail.
2897 if (V1->isOpaque() || V2->isOpaque())
2900 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2901 // FIXME: This is valid and could be handled by truncating the APInts.
2902 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2905 Inputs.push_back(std::make_pair(V1, V2));
2909 // We have a number of constant values, constant fold them element by element.
2910 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2911 const APInt &C1 = Inputs[I].first->getAPIntValue();
2912 const APInt &C2 = Inputs[I].second->getAPIntValue();
2916 Outputs.push_back(getConstant(C1 + C2, SVT));
2919 Outputs.push_back(getConstant(C1 - C2, SVT));
2922 Outputs.push_back(getConstant(C1 * C2, SVT));
2925 if (!C2.getBoolValue())
2927 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2930 if (!C2.getBoolValue())
2932 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2935 if (!C2.getBoolValue())
2937 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2940 if (!C2.getBoolValue())
2942 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2945 Outputs.push_back(getConstant(C1 & C2, SVT));
2948 Outputs.push_back(getConstant(C1 | C2, SVT));
2951 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2954 Outputs.push_back(getConstant(C1 << C2, SVT));
2957 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2960 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2963 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2966 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2973 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2974 "Expected a scalar or vector!"));
2976 // Handle the scalar case first.
2978 return Outputs.back();
2980 // We may have a vector type but a scalar result. Create a splat.
2981 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2983 // Build a big vector out of the scalar elements we generated.
2984 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2987 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2988 SDValue N2, bool nuw, bool nsw, bool exact) {
2989 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2990 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2993 case ISD::TokenFactor:
2994 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2995 N2.getValueType() == MVT::Other && "Invalid token factor!");
2996 // Fold trivial token factors.
2997 if (N1.getOpcode() == ISD::EntryToken) return N2;
2998 if (N2.getOpcode() == ISD::EntryToken) return N1;
2999 if (N1 == N2) return N1;
3001 case ISD::CONCAT_VECTORS:
3002 // Concat of UNDEFs is UNDEF.
3003 if (N1.getOpcode() == ISD::UNDEF &&
3004 N2.getOpcode() == ISD::UNDEF)
3005 return getUNDEF(VT);
3007 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3008 // one big BUILD_VECTOR.
3009 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3010 N2.getOpcode() == ISD::BUILD_VECTOR) {
3011 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3012 N1.getNode()->op_end());
3013 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3014 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3018 assert(VT.isInteger() && "This operator does not apply to FP types!");
3019 assert(N1.getValueType() == N2.getValueType() &&
3020 N1.getValueType() == VT && "Binary operator types must match!");
3021 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3022 // worth handling here.
3023 if (N2C && N2C->isNullValue())
3025 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3032 assert(VT.isInteger() && "This operator does not apply to FP types!");
3033 assert(N1.getValueType() == N2.getValueType() &&
3034 N1.getValueType() == VT && "Binary operator types must match!");
3035 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3036 // it's worth handling here.
3037 if (N2C && N2C->isNullValue())
3047 assert(VT.isInteger() && "This operator does not apply to FP types!");
3048 assert(N1.getValueType() == N2.getValueType() &&
3049 N1.getValueType() == VT && "Binary operator types must match!");
3056 if (getTarget().Options.UnsafeFPMath) {
3057 if (Opcode == ISD::FADD) {
3059 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3060 if (CFP->getValueAPF().isZero())
3063 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3064 if (CFP->getValueAPF().isZero())
3066 } else if (Opcode == ISD::FSUB) {
3068 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3069 if (CFP->getValueAPF().isZero())
3071 } else if (Opcode == ISD::FMUL) {
3072 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3075 // If the first operand isn't the constant, try the second
3077 CFP = dyn_cast<ConstantFPSDNode>(N2);
3084 return SDValue(CFP,0);
3086 if (CFP->isExactlyValue(1.0))
3091 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3092 assert(N1.getValueType() == N2.getValueType() &&
3093 N1.getValueType() == VT && "Binary operator types must match!");
3095 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3096 assert(N1.getValueType() == VT &&
3097 N1.getValueType().isFloatingPoint() &&
3098 N2.getValueType().isFloatingPoint() &&
3099 "Invalid FCOPYSIGN!");
3106 assert(VT == N1.getValueType() &&
3107 "Shift operators return type must be the same as their first arg");
3108 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3109 "Shifts only work on integers");
3110 assert((!VT.isVector() || VT == N2.getValueType()) &&
3111 "Vector shift amounts must be in the same as their first arg");
3112 // Verify that the shift amount VT is bit enough to hold valid shift
3113 // amounts. This catches things like trying to shift an i1024 value by an
3114 // i8, which is easy to fall into in generic code that uses
3115 // TLI.getShiftAmount().
3116 assert(N2.getValueType().getSizeInBits() >=
3117 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3118 "Invalid use of small shift amount with oversized value!");
3120 // Always fold shifts of i1 values so the code generator doesn't need to
3121 // handle them. Since we know the size of the shift has to be less than the
3122 // size of the value, the shift/rotate count is guaranteed to be zero.
3125 if (N2C && N2C->isNullValue())
3128 case ISD::FP_ROUND_INREG: {
3129 EVT EVT = cast<VTSDNode>(N2)->getVT();
3130 assert(VT == N1.getValueType() && "Not an inreg round!");
3131 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3132 "Cannot FP_ROUND_INREG integer types");
3133 assert(EVT.isVector() == VT.isVector() &&
3134 "FP_ROUND_INREG type should be vector iff the operand "
3136 assert((!EVT.isVector() ||
3137 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3138 "Vector element counts must match in FP_ROUND_INREG");
3139 assert(EVT.bitsLE(VT) && "Not rounding down!");
3141 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3145 assert(VT.isFloatingPoint() &&
3146 N1.getValueType().isFloatingPoint() &&
3147 VT.bitsLE(N1.getValueType()) &&
3148 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3149 if (N1.getValueType() == VT) return N1; // noop conversion.
3151 case ISD::AssertSext:
3152 case ISD::AssertZext: {
3153 EVT EVT = cast<VTSDNode>(N2)->getVT();
3154 assert(VT == N1.getValueType() && "Not an inreg extend!");
3155 assert(VT.isInteger() && EVT.isInteger() &&
3156 "Cannot *_EXTEND_INREG FP types");
3157 assert(!EVT.isVector() &&
3158 "AssertSExt/AssertZExt type should be the vector element type "
3159 "rather than the vector type!");
3160 assert(EVT.bitsLE(VT) && "Not extending!");
3161 if (VT == EVT) return N1; // noop assertion.
3164 case ISD::SIGN_EXTEND_INREG: {
3165 EVT EVT = cast<VTSDNode>(N2)->getVT();
3166 assert(VT == N1.getValueType() && "Not an inreg extend!");
3167 assert(VT.isInteger() && EVT.isInteger() &&
3168 "Cannot *_EXTEND_INREG FP types");
3169 assert(EVT.isVector() == VT.isVector() &&
3170 "SIGN_EXTEND_INREG type should be vector iff the operand "
3172 assert((!EVT.isVector() ||
3173 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3174 "Vector element counts must match in SIGN_EXTEND_INREG");
3175 assert(EVT.bitsLE(VT) && "Not extending!");
3176 if (EVT == VT) return N1; // Not actually extending
3179 APInt Val = N1C->getAPIntValue();
3180 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3181 Val <<= Val.getBitWidth()-FromBits;
3182 Val = Val.ashr(Val.getBitWidth()-FromBits);
3183 return getConstant(Val, VT);
3187 case ISD::EXTRACT_VECTOR_ELT:
3188 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3189 if (N1.getOpcode() == ISD::UNDEF)
3190 return getUNDEF(VT);
3192 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3193 // expanding copies of large vectors from registers.
3195 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3196 N1.getNumOperands() > 0) {
3198 N1.getOperand(0).getValueType().getVectorNumElements();
3199 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3200 N1.getOperand(N2C->getZExtValue() / Factor),
3201 getConstant(N2C->getZExtValue() % Factor,
3202 N2.getValueType()));
3205 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3206 // expanding large vector constants.
3207 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3208 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3210 if (VT != Elt.getValueType())
3211 // If the vector element type is not legal, the BUILD_VECTOR operands
3212 // are promoted and implicitly truncated, and the result implicitly
3213 // extended. Make that explicit here.
3214 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3219 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3220 // operations are lowered to scalars.
3221 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3222 // If the indices are the same, return the inserted element else
3223 // if the indices are known different, extract the element from
3224 // the original vector.
3225 SDValue N1Op2 = N1.getOperand(2);
3226 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3228 if (N1Op2C && N2C) {
3229 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3230 if (VT == N1.getOperand(1).getValueType())
3231 return N1.getOperand(1);
3233 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3236 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3240 case ISD::EXTRACT_ELEMENT:
3241 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3242 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3243 (N1.getValueType().isInteger() == VT.isInteger()) &&
3244 N1.getValueType() != VT &&
3245 "Wrong types for EXTRACT_ELEMENT!");
3247 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3248 // 64-bit integers into 32-bit parts. Instead of building the extract of
3249 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3250 if (N1.getOpcode() == ISD::BUILD_PAIR)
3251 return N1.getOperand(N2C->getZExtValue());
3253 // EXTRACT_ELEMENT of a constant int is also very common.
3254 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3255 unsigned ElementSize = VT.getSizeInBits();
3256 unsigned Shift = ElementSize * N2C->getZExtValue();
3257 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3258 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3261 case ISD::EXTRACT_SUBVECTOR: {
3263 if (VT.isSimple() && N1.getValueType().isSimple()) {
3264 assert(VT.isVector() && N1.getValueType().isVector() &&
3265 "Extract subvector VTs must be a vectors!");
3266 assert(VT.getVectorElementType() ==
3267 N1.getValueType().getVectorElementType() &&
3268 "Extract subvector VTs must have the same element type!");
3269 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3270 "Extract subvector must be from larger vector to smaller vector!");
3272 if (isa<ConstantSDNode>(Index.getNode())) {
3273 assert((VT.getVectorNumElements() +
3274 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3275 <= N1.getValueType().getVectorNumElements())
3276 && "Extract subvector overflow!");
3279 // Trivial extraction.
3280 if (VT.getSimpleVT() == N1.getSimpleValueType())
3287 // Perform trivial constant folding.
3288 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3289 if (SV.getNode()) return SV;
3291 // Canonicalize constant to RHS if commutative.
3292 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3293 std::swap(N1C, N2C);
3297 // Constant fold FP operations.
3298 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3299 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3301 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3302 // Canonicalize constant to RHS if commutative.
3303 std::swap(N1CFP, N2CFP);
3306 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3307 APFloat::opStatus s;
3310 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3311 if (s != APFloat::opInvalidOp)
3312 return getConstantFP(V1, VT);
3315 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3316 if (s!=APFloat::opInvalidOp)
3317 return getConstantFP(V1, VT);
3320 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3321 if (s!=APFloat::opInvalidOp)
3322 return getConstantFP(V1, VT);
3325 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3326 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3327 return getConstantFP(V1, VT);
3330 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3331 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3332 return getConstantFP(V1, VT);
3334 case ISD::FCOPYSIGN:
3336 return getConstantFP(V1, VT);
3341 if (Opcode == ISD::FP_ROUND) {
3342 APFloat V = N1CFP->getValueAPF(); // make copy
3344 // This can return overflow, underflow, or inexact; we don't care.
3345 // FIXME need to be more flexible about rounding mode.
3346 (void)V.convert(EVTToAPFloatSemantics(VT),
3347 APFloat::rmNearestTiesToEven, &ignored);
3348 return getConstantFP(V, VT);
3352 // Canonicalize an UNDEF to the RHS, even over a constant.
3353 if (N1.getOpcode() == ISD::UNDEF) {
3354 if (isCommutativeBinOp(Opcode)) {
3358 case ISD::FP_ROUND_INREG:
3359 case ISD::SIGN_EXTEND_INREG:
3365 return N1; // fold op(undef, arg2) -> undef
3373 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3374 // For vectors, we can't easily build an all zero vector, just return
3381 // Fold a bunch of operators when the RHS is undef.
3382 if (N2.getOpcode() == ISD::UNDEF) {
3385 if (N1.getOpcode() == ISD::UNDEF)
3386 // Handle undef ^ undef -> 0 special case. This is a common
3388 return getConstant(0, VT);
3398 return N2; // fold op(arg1, undef) -> undef
3404 if (getTarget().Options.UnsafeFPMath)
3412 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3413 // For vectors, we can't easily build an all zero vector, just return
3418 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3419 // For vectors, we can't easily build an all one vector, just return
3427 // Memoize this node if possible.
3429 SDVTList VTs = getVTList(VT);
3430 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3431 if (VT != MVT::Glue) {
3432 SDValue Ops[] = {N1, N2};
3433 FoldingSetNodeID ID;
3434 AddNodeIDNode(ID, Opcode, VTs, Ops);
3436 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3438 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3439 return SDValue(E, 0);
3441 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3443 CSEMap.InsertNode(N, IP);
3446 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3449 AllNodes.push_back(N);
3453 return SDValue(N, 0);
3456 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3457 SDValue N1, SDValue N2, SDValue N3) {
3458 // Perform various simplifications.
3459 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3462 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3463 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3464 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3465 if (N1CFP && N2CFP && N3CFP) {
3466 APFloat V1 = N1CFP->getValueAPF();
3467 const APFloat &V2 = N2CFP->getValueAPF();
3468 const APFloat &V3 = N3CFP->getValueAPF();
3469 APFloat::opStatus s =
3470 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3471 if (s != APFloat::opInvalidOp)
3472 return getConstantFP(V1, VT);
3476 case ISD::CONCAT_VECTORS:
3477 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3478 // one big BUILD_VECTOR.
3479 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3480 N2.getOpcode() == ISD::BUILD_VECTOR &&
3481 N3.getOpcode() == ISD::BUILD_VECTOR) {
3482 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3483 N1.getNode()->op_end());
3484 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3485 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3486 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3490 // Use FoldSetCC to simplify SETCC's.
3491 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3492 if (Simp.getNode()) return Simp;
3497 if (N1C->getZExtValue())
3498 return N2; // select true, X, Y -> X
3499 return N3; // select false, X, Y -> Y
3502 if (N2 == N3) return N2; // select C, X, X -> X
3504 case ISD::VECTOR_SHUFFLE:
3505 llvm_unreachable("should use getVectorShuffle constructor!");
3506 case ISD::INSERT_SUBVECTOR: {
3508 if (VT.isSimple() && N1.getValueType().isSimple()
3509 && N2.getValueType().isSimple()) {
3510 assert(VT.isVector() && N1.getValueType().isVector() &&
3511 N2.getValueType().isVector() &&
3512 "Insert subvector VTs must be a vectors");
3513 assert(VT == N1.getValueType() &&
3514 "Dest and insert subvector source types must match!");
3515 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3516 "Insert subvector must be from smaller vector to larger vector!");
3517 if (isa<ConstantSDNode>(Index.getNode())) {
3518 assert((N2.getValueType().getVectorNumElements() +
3519 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3520 <= VT.getVectorNumElements())
3521 && "Insert subvector overflow!");
3524 // Trivial insertion.
3525 if (VT.getSimpleVT() == N2.getSimpleValueType())
3531 // Fold bit_convert nodes from a type to themselves.
3532 if (N1.getValueType() == VT)
3537 // Memoize node if it doesn't produce a flag.
3539 SDVTList VTs = getVTList(VT);
3540 if (VT != MVT::Glue) {
3541 SDValue Ops[] = { N1, N2, N3 };
3542 FoldingSetNodeID ID;
3543 AddNodeIDNode(ID, Opcode, VTs, Ops);
3545 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3546 return SDValue(E, 0);
3548 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3549 DL.getDebugLoc(), VTs, N1, N2, N3);
3550 CSEMap.InsertNode(N, IP);
3552 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3553 DL.getDebugLoc(), VTs, N1, N2, N3);
3556 AllNodes.push_back(N);
3560 return SDValue(N, 0);
3563 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3564 SDValue N1, SDValue N2, SDValue N3,
3566 SDValue Ops[] = { N1, N2, N3, N4 };
3567 return getNode(Opcode, DL, VT, Ops);
3570 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3571 SDValue N1, SDValue N2, SDValue N3,
3572 SDValue N4, SDValue N5) {
3573 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3574 return getNode(Opcode, DL, VT, Ops);
3577 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3578 /// the incoming stack arguments to be loaded from the stack.
3579 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3580 SmallVector<SDValue, 8> ArgChains;
3582 // Include the original chain at the beginning of the list. When this is
3583 // used by target LowerCall hooks, this helps legalize find the
3584 // CALLSEQ_BEGIN node.
3585 ArgChains.push_back(Chain);
3587 // Add a chain value for each stack argument.
3588 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3589 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3590 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3591 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3592 if (FI->getIndex() < 0)
3593 ArgChains.push_back(SDValue(L, 1));
3595 // Build a tokenfactor for all the chains.
3596 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3599 /// getMemsetValue - Vectorized representation of the memset value
3601 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3603 assert(Value.getOpcode() != ISD::UNDEF);
3605 unsigned NumBits = VT.getScalarType().getSizeInBits();
3606 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3607 assert(C->getAPIntValue().getBitWidth() == 8);
3608 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3610 return DAG.getConstant(Val, VT);
3611 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3614 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3616 // Use a multiplication with 0x010101... to extend the input to the
3618 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3619 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3625 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3626 /// used when a memcpy is turned into a memset when the source is a constant
3628 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3629 const TargetLowering &TLI, StringRef Str) {
3630 // Handle vector with all elements zero.
3633 return DAG.getConstant(0, VT);
3634 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3635 return DAG.getConstantFP(0.0, VT);
3636 else if (VT.isVector()) {
3637 unsigned NumElts = VT.getVectorNumElements();
3638 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3639 return DAG.getNode(ISD::BITCAST, dl, VT,
3640 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3643 llvm_unreachable("Expected type!");
3646 assert(!VT.isVector() && "Can't handle vector type here!");
3647 unsigned NumVTBits = VT.getSizeInBits();
3648 unsigned NumVTBytes = NumVTBits / 8;
3649 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3651 APInt Val(NumVTBits, 0);
3652 if (TLI.isLittleEndian()) {
3653 for (unsigned i = 0; i != NumBytes; ++i)
3654 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3656 for (unsigned i = 0; i != NumBytes; ++i)
3657 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3660 // If the "cost" of materializing the integer immediate is less than the cost
3661 // of a load, then it is cost effective to turn the load into the immediate.
3662 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3663 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3664 return DAG.getConstant(Val, VT);
3665 return SDValue(nullptr, 0);
3668 /// getMemBasePlusOffset - Returns base and offset node for the
3670 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3671 SelectionDAG &DAG) {
3672 EVT VT = Base.getValueType();
3673 return DAG.getNode(ISD::ADD, dl,
3674 VT, Base, DAG.getConstant(Offset, VT));
3677 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3679 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3680 unsigned SrcDelta = 0;
3681 GlobalAddressSDNode *G = nullptr;
3682 if (Src.getOpcode() == ISD::GlobalAddress)
3683 G = cast<GlobalAddressSDNode>(Src);
3684 else if (Src.getOpcode() == ISD::ADD &&
3685 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3686 Src.getOperand(1).getOpcode() == ISD::Constant) {
3687 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3688 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3693 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3696 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3697 /// to replace the memset / memcpy. Return true if the number of memory ops
3698 /// is below the threshold. It returns the types of the sequence of
3699 /// memory ops to perform memset / memcpy by reference.
3700 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3701 unsigned Limit, uint64_t Size,
3702 unsigned DstAlign, unsigned SrcAlign,
3708 const TargetLowering &TLI) {
3709 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3710 "Expecting memcpy / memset source to meet alignment requirement!");
3711 // If 'SrcAlign' is zero, that means the memory operation does not need to
3712 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3713 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3714 // is the specified alignment of the memory operation. If it is zero, that
3715 // means it's possible to change the alignment of the destination.
3716 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3717 // not need to be loaded.
3718 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3719 IsMemset, ZeroMemset, MemcpyStrSrc,
3720 DAG.getMachineFunction());
3722 if (VT == MVT::Other) {
3724 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3725 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3726 VT = TLI.getPointerTy();
3728 switch (DstAlign & 7) {
3729 case 0: VT = MVT::i64; break;
3730 case 4: VT = MVT::i32; break;
3731 case 2: VT = MVT::i16; break;
3732 default: VT = MVT::i8; break;
3737 while (!TLI.isTypeLegal(LVT))
3738 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3739 assert(LVT.isInteger());
3745 unsigned NumMemOps = 0;
3747 unsigned VTSize = VT.getSizeInBits() / 8;
3748 while (VTSize > Size) {
3749 // For now, only use non-vector load / store's for the left-over pieces.
3754 if (VT.isVector() || VT.isFloatingPoint()) {
3755 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3756 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3757 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3759 else if (NewVT == MVT::i64 &&
3760 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3761 TLI.isSafeMemOpType(MVT::f64)) {
3762 // i64 is usually not legal on 32-bit targets, but f64 may be.
3770 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3771 if (NewVT == MVT::i8)
3773 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3775 NewVTSize = NewVT.getSizeInBits() / 8;
3777 // If the new VT cannot cover all of the remaining bits, then consider
3778 // issuing a (or a pair of) unaligned and overlapping load / store.
3779 // FIXME: Only does this for 64-bit or more since we don't have proper
3780 // cost model for unaligned load / store.
3783 if (NumMemOps && AllowOverlap &&
3784 VTSize >= 8 && NewVTSize < Size &&
3785 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3793 if (++NumMemOps > Limit)
3796 MemOps.push_back(VT);
3803 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3804 SDValue Chain, SDValue Dst,
3805 SDValue Src, uint64_t Size,
3806 unsigned Align, bool isVol,
3808 MachinePointerInfo DstPtrInfo,
3809 MachinePointerInfo SrcPtrInfo) {
3810 // Turn a memcpy of undef to nop.
3811 if (Src.getOpcode() == ISD::UNDEF)
3814 // Expand memcpy to a series of load and store ops if the size operand falls
3815 // below a certain threshold.
3816 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3817 // rather than maybe a humongous number of loads and stores.
3818 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3819 std::vector<EVT> MemOps;
3820 bool DstAlignCanChange = false;
3821 MachineFunction &MF = DAG.getMachineFunction();
3822 MachineFrameInfo *MFI = MF.getFrameInfo();
3824 MF.getFunction()->getAttributes().
3825 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3826 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3827 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3828 DstAlignCanChange = true;
3829 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3830 if (Align > SrcAlign)
3833 bool CopyFromStr = isMemSrcFromString(Src, Str);
3834 bool isZeroStr = CopyFromStr && Str.empty();
3835 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3837 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3838 (DstAlignCanChange ? 0 : Align),
3839 (isZeroStr ? 0 : SrcAlign),
3840 false, false, CopyFromStr, true, DAG, TLI))
3843 if (DstAlignCanChange) {
3844 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3845 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3847 // Don't promote to an alignment that would require dynamic stack
3849 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3850 if (!TRI->needsStackRealignment(MF))
3851 while (NewAlign > Align &&
3852 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3855 if (NewAlign > Align) {
3856 // Give the stack frame object a larger alignment if needed.
3857 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3858 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3863 SmallVector<SDValue, 8> OutChains;
3864 unsigned NumMemOps = MemOps.size();
3865 uint64_t SrcOff = 0, DstOff = 0;
3866 for (unsigned i = 0; i != NumMemOps; ++i) {
3868 unsigned VTSize = VT.getSizeInBits() / 8;
3869 SDValue Value, Store;
3871 if (VTSize > Size) {
3872 // Issuing an unaligned load / store pair that overlaps with the previous
3873 // pair. Adjust the offset accordingly.
3874 assert(i == NumMemOps-1 && i != 0);
3875 SrcOff -= VTSize - Size;
3876 DstOff -= VTSize - Size;
3880 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3881 // It's unlikely a store of a vector immediate can be done in a single
3882 // instruction. It would require a load from a constantpool first.
3883 // We only handle zero vectors here.
3884 // FIXME: Handle other cases where store of vector immediate is done in
3885 // a single instruction.
3886 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3887 if (Value.getNode())
3888 Store = DAG.getStore(Chain, dl, Value,
3889 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3890 DstPtrInfo.getWithOffset(DstOff), isVol,
3894 if (!Store.getNode()) {
3895 // The type might not be legal for the target. This should only happen
3896 // if the type is smaller than a legal type, as on PPC, so the right
3897 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3898 // to Load/Store if NVT==VT.
3899 // FIXME does the case above also need this?
3900 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3901 assert(NVT.bitsGE(VT));
3902 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3903 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3904 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3905 MinAlign(SrcAlign, SrcOff));
3906 Store = DAG.getTruncStore(Chain, dl, Value,
3907 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3908 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3911 OutChains.push_back(Store);
3917 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3920 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3921 SDValue Chain, SDValue Dst,
3922 SDValue Src, uint64_t Size,
3923 unsigned Align, bool isVol,
3925 MachinePointerInfo DstPtrInfo,
3926 MachinePointerInfo SrcPtrInfo) {
3927 // Turn a memmove of undef to nop.
3928 if (Src.getOpcode() == ISD::UNDEF)
3931 // Expand memmove to a series of load and store ops if the size operand falls
3932 // below a certain threshold.
3933 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3934 std::vector<EVT> MemOps;
3935 bool DstAlignCanChange = false;
3936 MachineFunction &MF = DAG.getMachineFunction();
3937 MachineFrameInfo *MFI = MF.getFrameInfo();
3938 bool OptSize = MF.getFunction()->getAttributes().
3939 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3940 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3941 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3942 DstAlignCanChange = true;
3943 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3944 if (Align > SrcAlign)
3946 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3948 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3949 (DstAlignCanChange ? 0 : Align), SrcAlign,
3950 false, false, false, false, DAG, TLI))
3953 if (DstAlignCanChange) {
3954 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3955 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3956 if (NewAlign > Align) {
3957 // Give the stack frame object a larger alignment if needed.
3958 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3959 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3964 uint64_t SrcOff = 0, DstOff = 0;
3965 SmallVector<SDValue, 8> LoadValues;
3966 SmallVector<SDValue, 8> LoadChains;
3967 SmallVector<SDValue, 8> OutChains;
3968 unsigned NumMemOps = MemOps.size();
3969 for (unsigned i = 0; i < NumMemOps; i++) {
3971 unsigned VTSize = VT.getSizeInBits() / 8;
3974 Value = DAG.getLoad(VT, dl, Chain,
3975 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3976 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3977 false, false, SrcAlign);
3978 LoadValues.push_back(Value);
3979 LoadChains.push_back(Value.getValue(1));
3982 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3984 for (unsigned i = 0; i < NumMemOps; i++) {
3986 unsigned VTSize = VT.getSizeInBits() / 8;
3989 Store = DAG.getStore(Chain, dl, LoadValues[i],
3990 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3991 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3992 OutChains.push_back(Store);
3996 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3999 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4002 /// \param DAG Selection DAG where lowered code is placed.
4003 /// \param dl Link to corresponding IR location.
4004 /// \param Chain Control flow dependency.
4005 /// \param Dst Pointer to destination memory location.
4006 /// \param Src Value of byte to write into the memory.
4007 /// \param Size Number of bytes to write.
4008 /// \param Align Alignment of the destination in bytes.
4009 /// \param isVol True if destination is volatile.
4010 /// \param DstPtrInfo IR information on the memory pointer.
4011 /// \returns New head in the control flow, if lowering was successful, empty
4012 /// SDValue otherwise.
4014 /// The function tries to replace 'llvm.memset' intrinsic with several store
4015 /// operations and value calculation code. This is usually profitable for small
4017 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4018 SDValue Chain, SDValue Dst,
4019 SDValue Src, uint64_t Size,
4020 unsigned Align, bool isVol,
4021 MachinePointerInfo DstPtrInfo) {
4022 // Turn a memset of undef to nop.
4023 if (Src.getOpcode() == ISD::UNDEF)
4026 // Expand memset to a series of load/store ops if the size operand
4027 // falls below a certain threshold.
4028 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4029 std::vector<EVT> MemOps;
4030 bool DstAlignCanChange = false;
4031 MachineFunction &MF = DAG.getMachineFunction();
4032 MachineFrameInfo *MFI = MF.getFrameInfo();
4033 bool OptSize = MF.getFunction()->getAttributes().
4034 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4035 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4036 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4037 DstAlignCanChange = true;
4039 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4040 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4041 Size, (DstAlignCanChange ? 0 : Align), 0,
4042 true, IsZeroVal, false, true, DAG, TLI))
4045 if (DstAlignCanChange) {
4046 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4047 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4048 if (NewAlign > Align) {
4049 // Give the stack frame object a larger alignment if needed.
4050 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4051 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4056 SmallVector<SDValue, 8> OutChains;
4057 uint64_t DstOff = 0;
4058 unsigned NumMemOps = MemOps.size();
4060 // Find the largest store and generate the bit pattern for it.
4061 EVT LargestVT = MemOps[0];
4062 for (unsigned i = 1; i < NumMemOps; i++)
4063 if (MemOps[i].bitsGT(LargestVT))
4064 LargestVT = MemOps[i];
4065 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4067 for (unsigned i = 0; i < NumMemOps; i++) {
4069 unsigned VTSize = VT.getSizeInBits() / 8;
4070 if (VTSize > Size) {
4071 // Issuing an unaligned load / store pair that overlaps with the previous
4072 // pair. Adjust the offset accordingly.
4073 assert(i == NumMemOps-1 && i != 0);
4074 DstOff -= VTSize - Size;
4077 // If this store is smaller than the largest store see whether we can get
4078 // the smaller value for free with a truncate.
4079 SDValue Value = MemSetValue;
4080 if (VT.bitsLT(LargestVT)) {
4081 if (!LargestVT.isVector() && !VT.isVector() &&
4082 TLI.isTruncateFree(LargestVT, VT))
4083 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4085 Value = getMemsetValue(Src, VT, DAG, dl);
4087 assert(Value.getValueType() == VT && "Value with wrong type.");
4088 SDValue Store = DAG.getStore(Chain, dl, Value,
4089 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4090 DstPtrInfo.getWithOffset(DstOff),
4091 isVol, false, Align);
4092 OutChains.push_back(Store);
4093 DstOff += VT.getSizeInBits() / 8;
4097 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4100 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4101 SDValue Src, SDValue Size,
4102 unsigned Align, bool isVol, bool AlwaysInline,
4103 MachinePointerInfo DstPtrInfo,
4104 MachinePointerInfo SrcPtrInfo) {
4105 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4107 // Check to see if we should lower the memcpy to loads and stores first.
4108 // For cases within the target-specified limits, this is the best choice.
4109 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4111 // Memcpy with size zero? Just return the original chain.
4112 if (ConstantSize->isNullValue())
4115 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4116 ConstantSize->getZExtValue(),Align,
4117 isVol, false, DstPtrInfo, SrcPtrInfo);
4118 if (Result.getNode())
4122 // Then check to see if we should lower the memcpy with target-specific
4123 // code. If the target chooses to do this, this is the next best.
4125 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4126 isVol, AlwaysInline,
4127 DstPtrInfo, SrcPtrInfo);
4128 if (Result.getNode())
4131 // If we really need inline code and the target declined to provide it,
4132 // use a (potentially long) sequence of loads and stores.
4134 assert(ConstantSize && "AlwaysInline requires a constant size!");
4135 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4136 ConstantSize->getZExtValue(), Align, isVol,
4137 true, DstPtrInfo, SrcPtrInfo);
4140 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4141 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4142 // respect volatile, so they may do things like read or write memory
4143 // beyond the given memory regions. But fixing this isn't easy, and most
4144 // people don't care.
4146 const TargetLowering *TLI = TM.getTargetLowering();
4148 // Emit a library call.
4149 TargetLowering::ArgListTy Args;
4150 TargetLowering::ArgListEntry Entry;
4151 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4152 Entry.Node = Dst; Args.push_back(Entry);
4153 Entry.Node = Src; Args.push_back(Entry);
4154 Entry.Node = Size; Args.push_back(Entry);
4155 // FIXME: pass in SDLoc
4156 TargetLowering::CallLoweringInfo CLI(*this);
4157 CLI.setDebugLoc(dl).setChain(Chain)
4158 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4159 Type::getVoidTy(*getContext()),
4160 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4161 TLI->getPointerTy()), std::move(Args), 0)
4162 .setDiscardResult();
4163 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4165 return CallResult.second;
4168 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4169 SDValue Src, SDValue Size,
4170 unsigned Align, bool isVol,
4171 MachinePointerInfo DstPtrInfo,
4172 MachinePointerInfo SrcPtrInfo) {
4173 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4175 // Check to see if we should lower the memmove to loads and stores first.
4176 // For cases within the target-specified limits, this is the best choice.
4177 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4179 // Memmove with size zero? Just return the original chain.
4180 if (ConstantSize->isNullValue())
4184 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4185 ConstantSize->getZExtValue(), Align, isVol,
4186 false, DstPtrInfo, SrcPtrInfo);
4187 if (Result.getNode())
4191 // Then check to see if we should lower the memmove with target-specific
4192 // code. If the target chooses to do this, this is the next best.
4194 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4195 DstPtrInfo, SrcPtrInfo);
4196 if (Result.getNode())
4199 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4200 // not be safe. See memcpy above for more details.
4202 const TargetLowering *TLI = TM.getTargetLowering();
4204 // Emit a library call.
4205 TargetLowering::ArgListTy Args;
4206 TargetLowering::ArgListEntry Entry;
4207 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4208 Entry.Node = Dst; Args.push_back(Entry);
4209 Entry.Node = Src; Args.push_back(Entry);
4210 Entry.Node = Size; Args.push_back(Entry);
4211 // FIXME: pass in SDLoc
4212 TargetLowering::CallLoweringInfo CLI(*this);
4213 CLI.setDebugLoc(dl).setChain(Chain)
4214 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4215 Type::getVoidTy(*getContext()),
4216 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4217 TLI->getPointerTy()), std::move(Args), 0)
4218 .setDiscardResult();
4219 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4221 return CallResult.second;
4224 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4225 SDValue Src, SDValue Size,
4226 unsigned Align, bool isVol,
4227 MachinePointerInfo DstPtrInfo) {
4228 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4230 // Check to see if we should lower the memset to stores first.
4231 // For cases within the target-specified limits, this is the best choice.
4232 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4234 // Memset with size zero? Just return the original chain.
4235 if (ConstantSize->isNullValue())
4239 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4240 Align, isVol, DstPtrInfo);
4242 if (Result.getNode())
4246 // Then check to see if we should lower the memset with target-specific
4247 // code. If the target chooses to do this, this is the next best.
4249 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4251 if (Result.getNode())
4254 // Emit a library call.
4255 const TargetLowering *TLI = TM.getTargetLowering();
4256 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4257 TargetLowering::ArgListTy Args;
4258 TargetLowering::ArgListEntry Entry;
4259 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4260 Args.push_back(Entry);
4261 // Extend or truncate the argument to be an i32 value for the call.
4262 if (Src.getValueType().bitsGT(MVT::i32))
4263 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4265 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4267 Entry.Ty = Type::getInt32Ty(*getContext());
4268 Entry.isSExt = true;
4269 Args.push_back(Entry);
4271 Entry.Ty = IntPtrTy;
4272 Entry.isSExt = false;
4273 Args.push_back(Entry);
4275 // FIXME: pass in SDLoc
4276 TargetLowering::CallLoweringInfo CLI(*this);
4277 CLI.setDebugLoc(dl).setChain(Chain)
4278 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4279 Type::getVoidTy(*getContext()),
4280 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4281 TLI->getPointerTy()), std::move(Args), 0)
4282 .setDiscardResult();
4284 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4285 return CallResult.second;
4288 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4289 SDVTList VTList, ArrayRef<SDValue> Ops,
4290 MachineMemOperand *MMO,
4291 AtomicOrdering SuccessOrdering,
4292 AtomicOrdering FailureOrdering,
4293 SynchronizationScope SynchScope) {
4294 FoldingSetNodeID ID;
4295 ID.AddInteger(MemVT.getRawBits());
4296 AddNodeIDNode(ID, Opcode, VTList, Ops);
4297 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4299 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4300 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4301 return SDValue(E, 0);
4304 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4305 // SDNode doesn't have access to it. This memory will be "leaked" when
4306 // the node is deallocated, but recovered when the allocator is released.
4307 // If the number of operands is less than 5 we use AtomicSDNode's internal
4309 unsigned NumOps = Ops.size();
4310 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4313 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4314 dl.getDebugLoc(), VTList, MemVT,
4315 Ops.data(), DynOps, NumOps, MMO,
4316 SuccessOrdering, FailureOrdering,
4318 CSEMap.InsertNode(N, IP);
4319 AllNodes.push_back(N);
4320 return SDValue(N, 0);
4323 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4324 SDVTList VTList, ArrayRef<SDValue> Ops,
4325 MachineMemOperand *MMO,
4326 AtomicOrdering Ordering,
4327 SynchronizationScope SynchScope) {
4328 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4329 Ordering, SynchScope);
4332 SDValue SelectionDAG::getAtomicCmpSwap(
4333 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4334 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4335 unsigned Alignment, AtomicOrdering SuccessOrdering,
4336 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4337 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4338 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4339 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4341 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4342 Alignment = getEVTAlignment(MemVT);
4344 MachineFunction &MF = getMachineFunction();
4346 // FIXME: Volatile isn't really correct; we should keep track of atomic
4347 // orderings in the memoperand.
4348 unsigned Flags = MachineMemOperand::MOVolatile;
4349 Flags |= MachineMemOperand::MOLoad;
4350 Flags |= MachineMemOperand::MOStore;
4352 MachineMemOperand *MMO =
4353 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4355 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4356 SuccessOrdering, FailureOrdering, SynchScope);
4359 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4360 SDVTList VTs, SDValue Chain, SDValue Ptr,
4361 SDValue Cmp, SDValue Swp,
4362 MachineMemOperand *MMO,
4363 AtomicOrdering SuccessOrdering,
4364 AtomicOrdering FailureOrdering,
4365 SynchronizationScope SynchScope) {
4366 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4367 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4368 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4370 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4371 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4372 SuccessOrdering, FailureOrdering, SynchScope);
4375 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4377 SDValue Ptr, SDValue Val,
4378 const Value* PtrVal,
4380 AtomicOrdering Ordering,
4381 SynchronizationScope SynchScope) {
4382 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4383 Alignment = getEVTAlignment(MemVT);
4385 MachineFunction &MF = getMachineFunction();
4386 // An atomic store does not load. An atomic load does not store.
4387 // (An atomicrmw obviously both loads and stores.)
4388 // For now, atomics are considered to be volatile always, and they are
4390 // FIXME: Volatile isn't really correct; we should keep track of atomic
4391 // orderings in the memoperand.
4392 unsigned Flags = MachineMemOperand::MOVolatile;
4393 if (Opcode != ISD::ATOMIC_STORE)
4394 Flags |= MachineMemOperand::MOLoad;
4395 if (Opcode != ISD::ATOMIC_LOAD)
4396 Flags |= MachineMemOperand::MOStore;
4398 MachineMemOperand *MMO =
4399 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4400 MemVT.getStoreSize(), Alignment);
4402 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4403 Ordering, SynchScope);
4406 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4408 SDValue Ptr, SDValue Val,
4409 MachineMemOperand *MMO,
4410 AtomicOrdering Ordering,
4411 SynchronizationScope SynchScope) {
4412 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4413 Opcode == ISD::ATOMIC_LOAD_SUB ||
4414 Opcode == ISD::ATOMIC_LOAD_AND ||
4415 Opcode == ISD::ATOMIC_LOAD_OR ||
4416 Opcode == ISD::ATOMIC_LOAD_XOR ||
4417 Opcode == ISD::ATOMIC_LOAD_NAND ||
4418 Opcode == ISD::ATOMIC_LOAD_MIN ||
4419 Opcode == ISD::ATOMIC_LOAD_MAX ||
4420 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4421 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4422 Opcode == ISD::ATOMIC_SWAP ||
4423 Opcode == ISD::ATOMIC_STORE) &&
4424 "Invalid Atomic Op");
4426 EVT VT = Val.getValueType();
4428 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4429 getVTList(VT, MVT::Other);
4430 SDValue Ops[] = {Chain, Ptr, Val};
4431 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4434 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4435 EVT VT, SDValue Chain,
4437 MachineMemOperand *MMO,
4438 AtomicOrdering Ordering,
4439 SynchronizationScope SynchScope) {
4440 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4442 SDVTList VTs = getVTList(VT, MVT::Other);
4443 SDValue Ops[] = {Chain, Ptr};
4444 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4447 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4448 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4449 if (Ops.size() == 1)
4452 SmallVector<EVT, 4> VTs;
4453 VTs.reserve(Ops.size());
4454 for (unsigned i = 0; i < Ops.size(); ++i)
4455 VTs.push_back(Ops[i].getValueType());
4456 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4460 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4461 ArrayRef<SDValue> Ops,
4462 EVT MemVT, MachinePointerInfo PtrInfo,
4463 unsigned Align, bool Vol,
4464 bool ReadMem, bool WriteMem) {
4465 if (Align == 0) // Ensure that codegen never sees alignment 0
4466 Align = getEVTAlignment(MemVT);
4468 MachineFunction &MF = getMachineFunction();
4471 Flags |= MachineMemOperand::MOStore;
4473 Flags |= MachineMemOperand::MOLoad;
4475 Flags |= MachineMemOperand::MOVolatile;
4476 MachineMemOperand *MMO =
4477 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4479 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4483 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4484 ArrayRef<SDValue> Ops, EVT MemVT,
4485 MachineMemOperand *MMO) {
4486 assert((Opcode == ISD::INTRINSIC_VOID ||
4487 Opcode == ISD::INTRINSIC_W_CHAIN ||
4488 Opcode == ISD::PREFETCH ||
4489 Opcode == ISD::LIFETIME_START ||
4490 Opcode == ISD::LIFETIME_END ||
4491 (Opcode <= INT_MAX &&
4492 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4493 "Opcode is not a memory-accessing opcode!");
4495 // Memoize the node unless it returns a flag.
4496 MemIntrinsicSDNode *N;
4497 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4498 FoldingSetNodeID ID;
4499 AddNodeIDNode(ID, Opcode, VTList, Ops);
4500 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4502 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4503 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4504 return SDValue(E, 0);
4507 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4508 dl.getDebugLoc(), VTList, Ops,
4510 CSEMap.InsertNode(N, IP);
4512 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4513 dl.getDebugLoc(), VTList, Ops,
4516 AllNodes.push_back(N);
4517 return SDValue(N, 0);
4520 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4521 /// MachinePointerInfo record from it. This is particularly useful because the
4522 /// code generator has many cases where it doesn't bother passing in a
4523 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4524 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4525 // If this is FI+Offset, we can model it.
4526 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4527 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4529 // If this is (FI+Offset1)+Offset2, we can model it.
4530 if (Ptr.getOpcode() != ISD::ADD ||
4531 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4532 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4533 return MachinePointerInfo();
4535 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4536 return MachinePointerInfo::getFixedStack(FI, Offset+
4537 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4540 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4541 /// MachinePointerInfo record from it. This is particularly useful because the
4542 /// code generator has many cases where it doesn't bother passing in a
4543 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4544 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4545 // If the 'Offset' value isn't a constant, we can't handle this.
4546 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4547 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4548 if (OffsetOp.getOpcode() == ISD::UNDEF)
4549 return InferPointerInfo(Ptr);
4550 return MachinePointerInfo();
4555 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4556 EVT VT, SDLoc dl, SDValue Chain,
4557 SDValue Ptr, SDValue Offset,
4558 MachinePointerInfo PtrInfo, EVT MemVT,
4559 bool isVolatile, bool isNonTemporal, bool isInvariant,
4560 unsigned Alignment, const MDNode *TBAAInfo,
4561 const MDNode *Ranges) {
4562 assert(Chain.getValueType() == MVT::Other &&
4563 "Invalid chain type");
4564 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4565 Alignment = getEVTAlignment(VT);
4567 unsigned Flags = MachineMemOperand::MOLoad;
4569 Flags |= MachineMemOperand::MOVolatile;
4571 Flags |= MachineMemOperand::MONonTemporal;
4573 Flags |= MachineMemOperand::MOInvariant;
4575 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4577 if (PtrInfo.V.isNull())
4578 PtrInfo = InferPointerInfo(Ptr, Offset);
4580 MachineFunction &MF = getMachineFunction();
4581 MachineMemOperand *MMO =
4582 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4584 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4588 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4589 EVT VT, SDLoc dl, SDValue Chain,
4590 SDValue Ptr, SDValue Offset, EVT MemVT,
4591 MachineMemOperand *MMO) {
4593 ExtType = ISD::NON_EXTLOAD;
4594 } else if (ExtType == ISD::NON_EXTLOAD) {
4595 assert(VT == MemVT && "Non-extending load from different memory type!");
4598 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4599 "Should only be an extending load, not truncating!");
4600 assert(VT.isInteger() == MemVT.isInteger() &&
4601 "Cannot convert from FP to Int or Int -> FP!");
4602 assert(VT.isVector() == MemVT.isVector() &&
4603 "Cannot use trunc store to convert to or from a vector!");
4604 assert((!VT.isVector() ||
4605 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4606 "Cannot use trunc store to change the number of vector elements!");
4609 bool Indexed = AM != ISD::UNINDEXED;
4610 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4611 "Unindexed load with an offset!");
4613 SDVTList VTs = Indexed ?
4614 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4615 SDValue Ops[] = { Chain, Ptr, Offset };
4616 FoldingSetNodeID ID;
4617 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4618 ID.AddInteger(MemVT.getRawBits());
4619 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4620 MMO->isNonTemporal(),
4621 MMO->isInvariant()));
4622 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4624 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4625 cast<LoadSDNode>(E)->refineAlignment(MMO);
4626 return SDValue(E, 0);
4628 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4629 dl.getDebugLoc(), VTs, AM, ExtType,
4631 CSEMap.InsertNode(N, IP);
4632 AllNodes.push_back(N);
4633 return SDValue(N, 0);
4636 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4637 SDValue Chain, SDValue Ptr,
4638 MachinePointerInfo PtrInfo,
4639 bool isVolatile, bool isNonTemporal,
4640 bool isInvariant, unsigned Alignment,
4641 const MDNode *TBAAInfo,
4642 const MDNode *Ranges) {
4643 SDValue Undef = getUNDEF(Ptr.getValueType());
4644 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4645 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4649 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4650 SDValue Chain, SDValue Ptr,
4651 MachineMemOperand *MMO) {
4652 SDValue Undef = getUNDEF(Ptr.getValueType());
4653 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4657 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4658 SDValue Chain, SDValue Ptr,
4659 MachinePointerInfo PtrInfo, EVT MemVT,
4660 bool isVolatile, bool isNonTemporal,
4661 unsigned Alignment, const MDNode *TBAAInfo) {
4662 SDValue Undef = getUNDEF(Ptr.getValueType());
4663 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4664 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4669 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4670 SDValue Chain, SDValue Ptr, EVT MemVT,
4671 MachineMemOperand *MMO) {
4672 SDValue Undef = getUNDEF(Ptr.getValueType());
4673 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4678 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4679 SDValue Offset, ISD::MemIndexedMode AM) {
4680 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4681 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4682 "Load is already a indexed load!");
4683 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4684 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4685 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4686 false, LD->getAlignment());
4689 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4690 SDValue Ptr, MachinePointerInfo PtrInfo,
4691 bool isVolatile, bool isNonTemporal,
4692 unsigned Alignment, const MDNode *TBAAInfo) {
4693 assert(Chain.getValueType() == MVT::Other &&
4694 "Invalid chain type");
4695 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4696 Alignment = getEVTAlignment(Val.getValueType());
4698 unsigned Flags = MachineMemOperand::MOStore;
4700 Flags |= MachineMemOperand::MOVolatile;
4702 Flags |= MachineMemOperand::MONonTemporal;
4704 if (PtrInfo.V.isNull())
4705 PtrInfo = InferPointerInfo(Ptr);
4707 MachineFunction &MF = getMachineFunction();
4708 MachineMemOperand *MMO =
4709 MF.getMachineMemOperand(PtrInfo, Flags,
4710 Val.getValueType().getStoreSize(), Alignment,
4713 return getStore(Chain, dl, Val, Ptr, MMO);
4716 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4717 SDValue Ptr, MachineMemOperand *MMO) {
4718 assert(Chain.getValueType() == MVT::Other &&
4719 "Invalid chain type");
4720 EVT VT = Val.getValueType();
4721 SDVTList VTs = getVTList(MVT::Other);
4722 SDValue Undef = getUNDEF(Ptr.getValueType());
4723 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4724 FoldingSetNodeID ID;
4725 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4726 ID.AddInteger(VT.getRawBits());
4727 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4728 MMO->isNonTemporal(), MMO->isInvariant()));
4729 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4731 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4732 cast<StoreSDNode>(E)->refineAlignment(MMO);
4733 return SDValue(E, 0);
4735 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4736 dl.getDebugLoc(), VTs,
4737 ISD::UNINDEXED, false, VT, MMO);
4738 CSEMap.InsertNode(N, IP);
4739 AllNodes.push_back(N);
4740 return SDValue(N, 0);
4743 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4744 SDValue Ptr, MachinePointerInfo PtrInfo,
4745 EVT SVT,bool isVolatile, bool isNonTemporal,
4747 const MDNode *TBAAInfo) {
4748 assert(Chain.getValueType() == MVT::Other &&
4749 "Invalid chain type");
4750 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4751 Alignment = getEVTAlignment(SVT);
4753 unsigned Flags = MachineMemOperand::MOStore;
4755 Flags |= MachineMemOperand::MOVolatile;
4757 Flags |= MachineMemOperand::MONonTemporal;
4759 if (PtrInfo.V.isNull())
4760 PtrInfo = InferPointerInfo(Ptr);
4762 MachineFunction &MF = getMachineFunction();
4763 MachineMemOperand *MMO =
4764 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4767 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4770 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4771 SDValue Ptr, EVT SVT,
4772 MachineMemOperand *MMO) {
4773 EVT VT = Val.getValueType();
4775 assert(Chain.getValueType() == MVT::Other &&
4776 "Invalid chain type");
4778 return getStore(Chain, dl, Val, Ptr, MMO);
4780 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4781 "Should only be a truncating store, not extending!");
4782 assert(VT.isInteger() == SVT.isInteger() &&
4783 "Can't do FP-INT conversion!");
4784 assert(VT.isVector() == SVT.isVector() &&
4785 "Cannot use trunc store to convert to or from a vector!");
4786 assert((!VT.isVector() ||
4787 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4788 "Cannot use trunc store to change the number of vector elements!");
4790 SDVTList VTs = getVTList(MVT::Other);
4791 SDValue Undef = getUNDEF(Ptr.getValueType());
4792 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4793 FoldingSetNodeID ID;
4794 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4795 ID.AddInteger(SVT.getRawBits());
4796 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4797 MMO->isNonTemporal(), MMO->isInvariant()));
4798 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4800 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4801 cast<StoreSDNode>(E)->refineAlignment(MMO);
4802 return SDValue(E, 0);
4804 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4805 dl.getDebugLoc(), VTs,
4806 ISD::UNINDEXED, true, SVT, MMO);
4807 CSEMap.InsertNode(N, IP);
4808 AllNodes.push_back(N);
4809 return SDValue(N, 0);
4813 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4814 SDValue Offset, ISD::MemIndexedMode AM) {
4815 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4816 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4817 "Store is already a indexed store!");
4818 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4819 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4820 FoldingSetNodeID ID;
4821 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4822 ID.AddInteger(ST->getMemoryVT().getRawBits());
4823 ID.AddInteger(ST->getRawSubclassData());
4824 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4826 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4827 return SDValue(E, 0);
4829 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4830 dl.getDebugLoc(), VTs, AM,
4831 ST->isTruncatingStore(),
4833 ST->getMemOperand());
4834 CSEMap.InsertNode(N, IP);
4835 AllNodes.push_back(N);
4836 return SDValue(N, 0);
4839 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4840 SDValue Chain, SDValue Ptr,
4843 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4844 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4847 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4848 ArrayRef<SDUse> Ops) {
4849 switch (Ops.size()) {
4850 case 0: return getNode(Opcode, DL, VT);
4851 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4852 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4853 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4857 // Copy from an SDUse array into an SDValue array for use with
4858 // the regular getNode logic.
4859 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4860 return getNode(Opcode, DL, VT, NewOps);
4863 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4864 ArrayRef<SDValue> Ops) {
4865 unsigned NumOps = Ops.size();
4867 case 0: return getNode(Opcode, DL, VT);
4868 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4869 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4870 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4876 case ISD::SELECT_CC: {
4877 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4878 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4879 "LHS and RHS of condition must have same type!");
4880 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4881 "True and False arms of SelectCC must have same type!");
4882 assert(Ops[2].getValueType() == VT &&
4883 "select_cc node must be of same type as true and false value!");
4887 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4888 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4889 "LHS/RHS of comparison should match types!");
4896 SDVTList VTs = getVTList(VT);
4898 if (VT != MVT::Glue) {
4899 FoldingSetNodeID ID;
4900 AddNodeIDNode(ID, Opcode, VTs, Ops);
4903 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4904 return SDValue(E, 0);
4906 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4908 CSEMap.InsertNode(N, IP);
4910 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4914 AllNodes.push_back(N);
4918 return SDValue(N, 0);
4921 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4922 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4923 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4926 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4927 ArrayRef<SDValue> Ops) {
4928 if (VTList.NumVTs == 1)
4929 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4933 // FIXME: figure out how to safely handle things like
4934 // int foo(int x) { return 1 << (x & 255); }
4935 // int bar() { return foo(256); }
4936 case ISD::SRA_PARTS:
4937 case ISD::SRL_PARTS:
4938 case ISD::SHL_PARTS:
4939 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4940 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4941 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4942 else if (N3.getOpcode() == ISD::AND)
4943 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4944 // If the and is only masking out bits that cannot effect the shift,
4945 // eliminate the and.
4946 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4947 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4948 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4954 // Memoize the node unless it returns a flag.
4956 unsigned NumOps = Ops.size();
4957 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4958 FoldingSetNodeID ID;
4959 AddNodeIDNode(ID, Opcode, VTList, Ops);
4961 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4962 return SDValue(E, 0);
4965 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4966 DL.getDebugLoc(), VTList, Ops[0]);
4967 } else if (NumOps == 2) {
4968 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4969 DL.getDebugLoc(), VTList, Ops[0],
4971 } else if (NumOps == 3) {
4972 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4973 DL.getDebugLoc(), VTList, Ops[0],
4976 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4979 CSEMap.InsertNode(N, IP);
4982 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4983 DL.getDebugLoc(), VTList, Ops[0]);
4984 } else if (NumOps == 2) {
4985 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4986 DL.getDebugLoc(), VTList, Ops[0],
4988 } else if (NumOps == 3) {
4989 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4990 DL.getDebugLoc(), VTList, Ops[0],
4993 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4997 AllNodes.push_back(N);
5001 return SDValue(N, 0);
5004 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5005 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5008 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5010 SDValue Ops[] = { N1 };
5011 return getNode(Opcode, DL, VTList, Ops);
5014 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5015 SDValue N1, SDValue N2) {
5016 SDValue Ops[] = { N1, N2 };
5017 return getNode(Opcode, DL, VTList, Ops);
5020 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5021 SDValue N1, SDValue N2, SDValue N3) {
5022 SDValue Ops[] = { N1, N2, N3 };
5023 return getNode(Opcode, DL, VTList, Ops);
5026 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5027 SDValue N1, SDValue N2, SDValue N3,
5029 SDValue Ops[] = { N1, N2, N3, N4 };
5030 return getNode(Opcode, DL, VTList, Ops);
5033 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5034 SDValue N1, SDValue N2, SDValue N3,
5035 SDValue N4, SDValue N5) {
5036 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5037 return getNode(Opcode, DL, VTList, Ops);
5040 SDVTList SelectionDAG::getVTList(EVT VT) {
5041 return makeVTList(SDNode::getValueTypeList(VT), 1);
5044 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5045 FoldingSetNodeID ID;
5047 ID.AddInteger(VT1.getRawBits());
5048 ID.AddInteger(VT2.getRawBits());
5051 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5053 EVT *Array = Allocator.Allocate<EVT>(2);
5056 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5057 VTListMap.InsertNode(Result, IP);
5059 return Result->getSDVTList();
5062 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5063 FoldingSetNodeID ID;
5065 ID.AddInteger(VT1.getRawBits());
5066 ID.AddInteger(VT2.getRawBits());
5067 ID.AddInteger(VT3.getRawBits());
5070 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5072 EVT *Array = Allocator.Allocate<EVT>(3);
5076 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5077 VTListMap.InsertNode(Result, IP);
5079 return Result->getSDVTList();
5082 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5083 FoldingSetNodeID ID;
5085 ID.AddInteger(VT1.getRawBits());
5086 ID.AddInteger(VT2.getRawBits());
5087 ID.AddInteger(VT3.getRawBits());
5088 ID.AddInteger(VT4.getRawBits());
5091 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5093 EVT *Array = Allocator.Allocate<EVT>(4);
5098 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5099 VTListMap.InsertNode(Result, IP);
5101 return Result->getSDVTList();
5104 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5105 unsigned NumVTs = VTs.size();
5106 FoldingSetNodeID ID;
5107 ID.AddInteger(NumVTs);
5108 for (unsigned index = 0; index < NumVTs; index++) {
5109 ID.AddInteger(VTs[index].getRawBits());
5113 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5115 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5116 std::copy(VTs.begin(), VTs.end(), Array);
5117 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5118 VTListMap.InsertNode(Result, IP);
5120 return Result->getSDVTList();
5124 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5125 /// specified operands. If the resultant node already exists in the DAG,
5126 /// this does not modify the specified node, instead it returns the node that
5127 /// already exists. If the resultant node does not exist in the DAG, the
5128 /// input node is returned. As a degenerate case, if you specify the same
5129 /// input operands as the node already has, the input node is returned.
5130 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5131 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5133 // Check to see if there is no change.
5134 if (Op == N->getOperand(0)) return N;
5136 // See if the modified node already exists.
5137 void *InsertPos = nullptr;
5138 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5141 // Nope it doesn't. Remove the node from its current place in the maps.
5143 if (!RemoveNodeFromCSEMaps(N))
5144 InsertPos = nullptr;
5146 // Now we update the operands.
5147 N->OperandList[0].set(Op);
5149 // If this gets put into a CSE map, add it.
5150 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5154 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5155 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5157 // Check to see if there is no change.
5158 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5159 return N; // No operands changed, just return the input node.
5161 // See if the modified node already exists.
5162 void *InsertPos = nullptr;
5163 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5166 // Nope it doesn't. Remove the node from its current place in the maps.
5168 if (!RemoveNodeFromCSEMaps(N))
5169 InsertPos = nullptr;
5171 // Now we update the operands.
5172 if (N->OperandList[0] != Op1)
5173 N->OperandList[0].set(Op1);
5174 if (N->OperandList[1] != Op2)
5175 N->OperandList[1].set(Op2);
5177 // If this gets put into a CSE map, add it.
5178 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5182 SDNode *SelectionDAG::
5183 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5184 SDValue Ops[] = { Op1, Op2, Op3 };
5185 return UpdateNodeOperands(N, Ops);
5188 SDNode *SelectionDAG::
5189 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5190 SDValue Op3, SDValue Op4) {
5191 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5192 return UpdateNodeOperands(N, Ops);
5195 SDNode *SelectionDAG::
5196 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5197 SDValue Op3, SDValue Op4, SDValue Op5) {
5198 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5199 return UpdateNodeOperands(N, Ops);
5202 SDNode *SelectionDAG::
5203 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5204 unsigned NumOps = Ops.size();
5205 assert(N->getNumOperands() == NumOps &&
5206 "Update with wrong number of operands");
5208 // Check to see if there is no change.
5209 bool AnyChange = false;
5210 for (unsigned i = 0; i != NumOps; ++i) {
5211 if (Ops[i] != N->getOperand(i)) {
5217 // No operands changed, just return the input node.
5218 if (!AnyChange) return N;
5220 // See if the modified node already exists.
5221 void *InsertPos = nullptr;
5222 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5225 // Nope it doesn't. Remove the node from its current place in the maps.
5227 if (!RemoveNodeFromCSEMaps(N))
5228 InsertPos = nullptr;
5230 // Now we update the operands.
5231 for (unsigned i = 0; i != NumOps; ++i)
5232 if (N->OperandList[i] != Ops[i])
5233 N->OperandList[i].set(Ops[i]);
5235 // If this gets put into a CSE map, add it.
5236 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5240 /// DropOperands - Release the operands and set this node to have
5242 void SDNode::DropOperands() {
5243 // Unlike the code in MorphNodeTo that does this, we don't need to
5244 // watch for dead nodes here.
5245 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5251 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5254 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5256 SDVTList VTs = getVTList(VT);
5257 return SelectNodeTo(N, MachineOpc, VTs, None);
5260 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5261 EVT VT, SDValue Op1) {
5262 SDVTList VTs = getVTList(VT);
5263 SDValue Ops[] = { Op1 };
5264 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5267 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5268 EVT VT, SDValue Op1,
5270 SDVTList VTs = getVTList(VT);
5271 SDValue Ops[] = { Op1, Op2 };
5272 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5275 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5276 EVT VT, SDValue Op1,
5277 SDValue Op2, SDValue Op3) {
5278 SDVTList VTs = getVTList(VT);
5279 SDValue Ops[] = { Op1, Op2, Op3 };
5280 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5284 EVT VT, ArrayRef<SDValue> Ops) {
5285 SDVTList VTs = getVTList(VT);
5286 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5289 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5290 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5291 SDVTList VTs = getVTList(VT1, VT2);
5292 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5295 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5297 SDVTList VTs = getVTList(VT1, VT2);
5298 return SelectNodeTo(N, MachineOpc, VTs, None);
5301 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 EVT VT1, EVT VT2, EVT VT3,
5303 ArrayRef<SDValue> Ops) {
5304 SDVTList VTs = getVTList(VT1, VT2, VT3);
5305 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5308 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5309 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5310 ArrayRef<SDValue> Ops) {
5311 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5312 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5315 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5318 SDVTList VTs = getVTList(VT1, VT2);
5319 SDValue Ops[] = { Op1 };
5320 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5323 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5325 SDValue Op1, SDValue Op2) {
5326 SDVTList VTs = getVTList(VT1, VT2);
5327 SDValue Ops[] = { Op1, Op2 };
5328 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5331 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5333 SDValue Op1, SDValue Op2,
5335 SDVTList VTs = getVTList(VT1, VT2);
5336 SDValue Ops[] = { Op1, Op2, Op3 };
5337 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5340 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5341 EVT VT1, EVT VT2, EVT VT3,
5342 SDValue Op1, SDValue Op2,
5344 SDVTList VTs = getVTList(VT1, VT2, VT3);
5345 SDValue Ops[] = { Op1, Op2, Op3 };
5346 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5349 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5350 SDVTList VTs,ArrayRef<SDValue> Ops) {
5351 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5352 // Reset the NodeID to -1.
5357 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5358 /// the line number information on the merged node since it is not possible to
5359 /// preserve the information that operation is associated with multiple lines.
5360 /// This will make the debugger working better at -O0, were there is a higher
5361 /// probability having other instructions associated with that line.
5363 /// For IROrder, we keep the smaller of the two
5364 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5365 DebugLoc NLoc = N->getDebugLoc();
5366 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5367 (OLoc.getDebugLoc() != NLoc)) {
5368 N->setDebugLoc(DebugLoc());
5370 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5371 N->setIROrder(Order);
5375 /// MorphNodeTo - This *mutates* the specified node to have the specified
5376 /// return type, opcode, and operands.
5378 /// Note that MorphNodeTo returns the resultant node. If there is already a
5379 /// node of the specified opcode and operands, it returns that node instead of
5380 /// the current one. Note that the SDLoc need not be the same.
5382 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5383 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5384 /// node, and because it doesn't require CSE recalculation for any of
5385 /// the node's users.
5387 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5388 SDVTList VTs, ArrayRef<SDValue> Ops) {
5389 unsigned NumOps = Ops.size();
5390 // If an identical node already exists, use it.
5392 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5393 FoldingSetNodeID ID;
5394 AddNodeIDNode(ID, Opc, VTs, Ops);
5395 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5396 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5399 if (!RemoveNodeFromCSEMaps(N))
5402 // Start the morphing.
5404 N->ValueList = VTs.VTs;
5405 N->NumValues = VTs.NumVTs;
5407 // Clear the operands list, updating used nodes to remove this from their
5408 // use list. Keep track of any operands that become dead as a result.
5409 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5410 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5412 SDNode *Used = Use.getNode();
5414 if (Used->use_empty())
5415 DeadNodeSet.insert(Used);
5418 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5419 // Initialize the memory references information.
5420 MN->setMemRefs(nullptr, nullptr);
5421 // If NumOps is larger than the # of operands we can have in a
5422 // MachineSDNode, reallocate the operand list.
5423 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5424 if (MN->OperandsNeedDelete)
5425 delete[] MN->OperandList;
5426 if (NumOps > array_lengthof(MN->LocalOperands))
5427 // We're creating a final node that will live unmorphed for the
5428 // remainder of the current SelectionDAG iteration, so we can allocate
5429 // the operands directly out of a pool with no recycling metadata.
5430 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5431 Ops.data(), NumOps);
5433 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5434 MN->OperandsNeedDelete = false;
5436 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5438 // If NumOps is larger than the # of operands we currently have, reallocate
5439 // the operand list.
5440 if (NumOps > N->NumOperands) {
5441 if (N->OperandsNeedDelete)
5442 delete[] N->OperandList;
5443 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5444 N->OperandsNeedDelete = true;
5446 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5449 // Delete any nodes that are still dead after adding the uses for the
5451 if (!DeadNodeSet.empty()) {
5452 SmallVector<SDNode *, 16> DeadNodes;
5453 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5454 E = DeadNodeSet.end(); I != E; ++I)
5455 if ((*I)->use_empty())
5456 DeadNodes.push_back(*I);
5457 RemoveDeadNodes(DeadNodes);
5461 CSEMap.InsertNode(N, IP); // Memoize the new node.
5466 /// getMachineNode - These are used for target selectors to create a new node
5467 /// with specified return type(s), MachineInstr opcode, and operands.
5469 /// Note that getMachineNode returns the resultant node. If there is already a
5470 /// node of the specified opcode and operands, it returns that node instead of
5471 /// the current one.
5473 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5474 SDVTList VTs = getVTList(VT);
5475 return getMachineNode(Opcode, dl, VTs, None);
5479 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5480 SDVTList VTs = getVTList(VT);
5481 SDValue Ops[] = { Op1 };
5482 return getMachineNode(Opcode, dl, VTs, Ops);
5486 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5487 SDValue Op1, SDValue Op2) {
5488 SDVTList VTs = getVTList(VT);
5489 SDValue Ops[] = { Op1, Op2 };
5490 return getMachineNode(Opcode, dl, VTs, Ops);
5494 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5495 SDValue Op1, SDValue Op2, SDValue Op3) {
5496 SDVTList VTs = getVTList(VT);
5497 SDValue Ops[] = { Op1, Op2, Op3 };
5498 return getMachineNode(Opcode, dl, VTs, Ops);
5502 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5503 ArrayRef<SDValue> Ops) {
5504 SDVTList VTs = getVTList(VT);
5505 return getMachineNode(Opcode, dl, VTs, Ops);
5509 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5510 SDVTList VTs = getVTList(VT1, VT2);
5511 return getMachineNode(Opcode, dl, VTs, None);
5515 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5516 EVT VT1, EVT VT2, SDValue Op1) {
5517 SDVTList VTs = getVTList(VT1, VT2);
5518 SDValue Ops[] = { Op1 };
5519 return getMachineNode(Opcode, dl, VTs, Ops);
5523 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5524 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5525 SDVTList VTs = getVTList(VT1, VT2);
5526 SDValue Ops[] = { Op1, Op2 };
5527 return getMachineNode(Opcode, dl, VTs, Ops);
5531 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5532 EVT VT1, EVT VT2, SDValue Op1,
5533 SDValue Op2, SDValue Op3) {
5534 SDVTList VTs = getVTList(VT1, VT2);
5535 SDValue Ops[] = { Op1, Op2, Op3 };
5536 return getMachineNode(Opcode, dl, VTs, Ops);
5540 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5542 ArrayRef<SDValue> Ops) {
5543 SDVTList VTs = getVTList(VT1, VT2);
5544 return getMachineNode(Opcode, dl, VTs, Ops);
5548 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5549 EVT VT1, EVT VT2, EVT VT3,
5550 SDValue Op1, SDValue Op2) {
5551 SDVTList VTs = getVTList(VT1, VT2, VT3);
5552 SDValue Ops[] = { Op1, Op2 };
5553 return getMachineNode(Opcode, dl, VTs, Ops);
5557 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5558 EVT VT1, EVT VT2, EVT VT3,
5559 SDValue Op1, SDValue Op2, SDValue Op3) {
5560 SDVTList VTs = getVTList(VT1, VT2, VT3);
5561 SDValue Ops[] = { Op1, Op2, Op3 };
5562 return getMachineNode(Opcode, dl, VTs, Ops);
5566 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5567 EVT VT1, EVT VT2, EVT VT3,
5568 ArrayRef<SDValue> Ops) {
5569 SDVTList VTs = getVTList(VT1, VT2, VT3);
5570 return getMachineNode(Opcode, dl, VTs, Ops);
5574 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5575 EVT VT2, EVT VT3, EVT VT4,
5576 ArrayRef<SDValue> Ops) {
5577 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5578 return getMachineNode(Opcode, dl, VTs, Ops);
5582 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5583 ArrayRef<EVT> ResultTys,
5584 ArrayRef<SDValue> Ops) {
5585 SDVTList VTs = getVTList(ResultTys);
5586 return getMachineNode(Opcode, dl, VTs, Ops);
5590 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5591 ArrayRef<SDValue> OpsArray) {
5592 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5595 const SDValue *Ops = OpsArray.data();
5596 unsigned NumOps = OpsArray.size();
5599 FoldingSetNodeID ID;
5600 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5602 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5603 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5607 // Allocate a new MachineSDNode.
5608 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5609 DL.getDebugLoc(), VTs);
5611 // Initialize the operands list.
5612 if (NumOps > array_lengthof(N->LocalOperands))
5613 // We're creating a final node that will live unmorphed for the
5614 // remainder of the current SelectionDAG iteration, so we can allocate
5615 // the operands directly out of a pool with no recycling metadata.
5616 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5619 N->InitOperands(N->LocalOperands, Ops, NumOps);
5620 N->OperandsNeedDelete = false;
5623 CSEMap.InsertNode(N, IP);
5625 AllNodes.push_back(N);
5627 VerifyMachineNode(N);
5632 /// getTargetExtractSubreg - A convenience function for creating
5633 /// TargetOpcode::EXTRACT_SUBREG nodes.
5635 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5637 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5638 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5639 VT, Operand, SRIdxVal);
5640 return SDValue(Subreg, 0);
5643 /// getTargetInsertSubreg - A convenience function for creating
5644 /// TargetOpcode::INSERT_SUBREG nodes.
5646 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5647 SDValue Operand, SDValue Subreg) {
5648 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5649 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5650 VT, Operand, Subreg, SRIdxVal);
5651 return SDValue(Result, 0);
5654 /// getNodeIfExists - Get the specified node if it's already available, or
5655 /// else return NULL.
5656 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5657 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5659 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5660 FoldingSetNodeID ID;
5661 AddNodeIDNode(ID, Opcode, VTList, Ops);
5662 if (isBinOpWithFlags(Opcode))
5663 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5665 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5671 /// getDbgValue - Creates a SDDbgValue node.
5675 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5676 bool IsIndirect, uint64_t Off,
5677 DebugLoc DL, unsigned O) {
5678 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5683 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5685 DebugLoc DL, unsigned O) {
5686 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5691 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5692 DebugLoc DL, unsigned O) {
5693 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5698 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5699 /// pointed to by a use iterator is deleted, increment the use iterator
5700 /// so that it doesn't dangle.
5702 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5703 SDNode::use_iterator &UI;
5704 SDNode::use_iterator &UE;
5706 void NodeDeleted(SDNode *N, SDNode *E) override {
5707 // Increment the iterator as needed.
5708 while (UI != UE && N == *UI)
5713 RAUWUpdateListener(SelectionDAG &d,
5714 SDNode::use_iterator &ui,
5715 SDNode::use_iterator &ue)
5716 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5721 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5722 /// This can cause recursive merging of nodes in the DAG.
5724 /// This version assumes From has a single result value.
5726 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5727 SDNode *From = FromN.getNode();
5728 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5729 "Cannot replace with this method!");
5730 assert(From != To.getNode() && "Cannot replace uses of with self");
5732 // Iterate over all the existing uses of From. New uses will be added
5733 // to the beginning of the use list, which we avoid visiting.
5734 // This specifically avoids visiting uses of From that arise while the
5735 // replacement is happening, because any such uses would be the result
5736 // of CSE: If an existing node looks like From after one of its operands
5737 // is replaced by To, we don't want to replace of all its users with To
5738 // too. See PR3018 for more info.
5739 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5740 RAUWUpdateListener Listener(*this, UI, UE);
5744 // This node is about to morph, remove its old self from the CSE maps.
5745 RemoveNodeFromCSEMaps(User);
5747 // A user can appear in a use list multiple times, and when this
5748 // happens the uses are usually next to each other in the list.
5749 // To help reduce the number of CSE recomputations, process all
5750 // the uses of this user that we can find this way.
5752 SDUse &Use = UI.getUse();
5755 } while (UI != UE && *UI == User);
5757 // Now that we have modified User, add it back to the CSE maps. If it
5758 // already exists there, recursively merge the results together.
5759 AddModifiedNodeToCSEMaps(User);
5762 // If we just RAUW'd the root, take note.
5763 if (FromN == getRoot())
5767 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5768 /// This can cause recursive merging of nodes in the DAG.
5770 /// This version assumes that for each value of From, there is a
5771 /// corresponding value in To in the same position with the same type.
5773 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5775 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5776 assert((!From->hasAnyUseOfValue(i) ||
5777 From->getValueType(i) == To->getValueType(i)) &&
5778 "Cannot use this version of ReplaceAllUsesWith!");
5781 // Handle the trivial case.
5785 // Iterate over just the existing users of From. See the comments in
5786 // the ReplaceAllUsesWith above.
5787 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5788 RAUWUpdateListener Listener(*this, UI, UE);
5792 // This node is about to morph, remove its old self from the CSE maps.
5793 RemoveNodeFromCSEMaps(User);
5795 // A user can appear in a use list multiple times, and when this
5796 // happens the uses are usually next to each other in the list.
5797 // To help reduce the number of CSE recomputations, process all
5798 // the uses of this user that we can find this way.
5800 SDUse &Use = UI.getUse();
5803 } while (UI != UE && *UI == User);
5805 // Now that we have modified User, add it back to the CSE maps. If it
5806 // already exists there, recursively merge the results together.
5807 AddModifiedNodeToCSEMaps(User);
5810 // If we just RAUW'd the root, take note.
5811 if (From == getRoot().getNode())
5812 setRoot(SDValue(To, getRoot().getResNo()));
5815 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5816 /// This can cause recursive merging of nodes in the DAG.
5818 /// This version can replace From with any result values. To must match the
5819 /// number and types of values returned by From.
5820 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5821 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5822 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5824 // Iterate over just the existing users of From. See the comments in
5825 // the ReplaceAllUsesWith above.
5826 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5827 RAUWUpdateListener Listener(*this, UI, UE);
5831 // This node is about to morph, remove its old self from the CSE maps.
5832 RemoveNodeFromCSEMaps(User);
5834 // A user can appear in a use list multiple times, and when this
5835 // happens the uses are usually next to each other in the list.
5836 // To help reduce the number of CSE recomputations, process all
5837 // the uses of this user that we can find this way.
5839 SDUse &Use = UI.getUse();
5840 const SDValue &ToOp = To[Use.getResNo()];
5843 } while (UI != UE && *UI == User);
5845 // Now that we have modified User, add it back to the CSE maps. If it
5846 // already exists there, recursively merge the results together.
5847 AddModifiedNodeToCSEMaps(User);
5850 // If we just RAUW'd the root, take note.
5851 if (From == getRoot().getNode())
5852 setRoot(SDValue(To[getRoot().getResNo()]));
5855 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5856 /// uses of other values produced by From.getNode() alone. The Deleted
5857 /// vector is handled the same way as for ReplaceAllUsesWith.
5858 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5859 // Handle the really simple, really trivial case efficiently.
5860 if (From == To) return;
5862 // Handle the simple, trivial, case efficiently.
5863 if (From.getNode()->getNumValues() == 1) {
5864 ReplaceAllUsesWith(From, To);
5868 // Iterate over just the existing users of From. See the comments in
5869 // the ReplaceAllUsesWith above.
5870 SDNode::use_iterator UI = From.getNode()->use_begin(),
5871 UE = From.getNode()->use_end();
5872 RAUWUpdateListener Listener(*this, UI, UE);
5875 bool UserRemovedFromCSEMaps = false;
5877 // A user can appear in a use list multiple times, and when this
5878 // happens the uses are usually next to each other in the list.
5879 // To help reduce the number of CSE recomputations, process all
5880 // the uses of this user that we can find this way.
5882 SDUse &Use = UI.getUse();
5884 // Skip uses of different values from the same node.
5885 if (Use.getResNo() != From.getResNo()) {
5890 // If this node hasn't been modified yet, it's still in the CSE maps,
5891 // so remove its old self from the CSE maps.
5892 if (!UserRemovedFromCSEMaps) {
5893 RemoveNodeFromCSEMaps(User);
5894 UserRemovedFromCSEMaps = true;
5899 } while (UI != UE && *UI == User);
5901 // We are iterating over all uses of the From node, so if a use
5902 // doesn't use the specific value, no changes are made.
5903 if (!UserRemovedFromCSEMaps)
5906 // Now that we have modified User, add it back to the CSE maps. If it
5907 // already exists there, recursively merge the results together.
5908 AddModifiedNodeToCSEMaps(User);
5911 // If we just RAUW'd the root, take note.
5912 if (From == getRoot())
5917 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5918 /// to record information about a use.
5925 /// operator< - Sort Memos by User.
5926 bool operator<(const UseMemo &L, const UseMemo &R) {
5927 return (intptr_t)L.User < (intptr_t)R.User;
5931 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5932 /// uses of other values produced by From.getNode() alone. The same value
5933 /// may appear in both the From and To list. The Deleted vector is
5934 /// handled the same way as for ReplaceAllUsesWith.
5935 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5938 // Handle the simple, trivial case efficiently.
5940 return ReplaceAllUsesOfValueWith(*From, *To);
5942 // Read up all the uses and make records of them. This helps
5943 // processing new uses that are introduced during the
5944 // replacement process.
5945 SmallVector<UseMemo, 4> Uses;
5946 for (unsigned i = 0; i != Num; ++i) {
5947 unsigned FromResNo = From[i].getResNo();
5948 SDNode *FromNode = From[i].getNode();
5949 for (SDNode::use_iterator UI = FromNode->use_begin(),
5950 E = FromNode->use_end(); UI != E; ++UI) {
5951 SDUse &Use = UI.getUse();
5952 if (Use.getResNo() == FromResNo) {
5953 UseMemo Memo = { *UI, i, &Use };
5954 Uses.push_back(Memo);
5959 // Sort the uses, so that all the uses from a given User are together.
5960 std::sort(Uses.begin(), Uses.end());
5962 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5963 UseIndex != UseIndexEnd; ) {
5964 // We know that this user uses some value of From. If it is the right
5965 // value, update it.
5966 SDNode *User = Uses[UseIndex].User;
5968 // This node is about to morph, remove its old self from the CSE maps.
5969 RemoveNodeFromCSEMaps(User);
5971 // The Uses array is sorted, so all the uses for a given User
5972 // are next to each other in the list.
5973 // To help reduce the number of CSE recomputations, process all
5974 // the uses of this user that we can find this way.
5976 unsigned i = Uses[UseIndex].Index;
5977 SDUse &Use = *Uses[UseIndex].Use;
5981 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5983 // Now that we have modified User, add it back to the CSE maps. If it
5984 // already exists there, recursively merge the results together.
5985 AddModifiedNodeToCSEMaps(User);
5989 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5990 /// based on their topological order. It returns the maximum id and a vector
5991 /// of the SDNodes* in assigned order by reference.
5992 unsigned SelectionDAG::AssignTopologicalOrder() {
5994 unsigned DAGSize = 0;
5996 // SortedPos tracks the progress of the algorithm. Nodes before it are
5997 // sorted, nodes after it are unsorted. When the algorithm completes
5998 // it is at the end of the list.
5999 allnodes_iterator SortedPos = allnodes_begin();
6001 // Visit all the nodes. Move nodes with no operands to the front of
6002 // the list immediately. Annotate nodes that do have operands with their
6003 // operand count. Before we do this, the Node Id fields of the nodes
6004 // may contain arbitrary values. After, the Node Id fields for nodes
6005 // before SortedPos will contain the topological sort index, and the
6006 // Node Id fields for nodes At SortedPos and after will contain the
6007 // count of outstanding operands.
6008 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6010 checkForCycles(N, this);
6011 unsigned Degree = N->getNumOperands();
6013 // A node with no uses, add it to the result array immediately.
6014 N->setNodeId(DAGSize++);
6015 allnodes_iterator Q = N;
6017 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6018 assert(SortedPos != AllNodes.end() && "Overran node list");
6021 // Temporarily use the Node Id as scratch space for the degree count.
6022 N->setNodeId(Degree);
6026 // Visit all the nodes. As we iterate, move nodes into sorted order,
6027 // such that by the time the end is reached all nodes will be sorted.
6028 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6030 checkForCycles(N, this);
6031 // N is in sorted position, so all its uses have one less operand
6032 // that needs to be sorted.
6033 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6036 unsigned Degree = P->getNodeId();
6037 assert(Degree != 0 && "Invalid node degree");
6040 // All of P's operands are sorted, so P may sorted now.
6041 P->setNodeId(DAGSize++);
6043 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6044 assert(SortedPos != AllNodes.end() && "Overran node list");
6047 // Update P's outstanding operand count.
6048 P->setNodeId(Degree);
6051 if (I == SortedPos) {
6054 dbgs() << "Overran sorted position:\n";
6055 S->dumprFull(this); dbgs() << "\n";
6056 dbgs() << "Checking if this is due to cycles\n";
6057 checkForCycles(this, true);
6059 llvm_unreachable(nullptr);
6063 assert(SortedPos == AllNodes.end() &&
6064 "Topological sort incomplete!");
6065 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6066 "First node in topological sort is not the entry token!");
6067 assert(AllNodes.front().getNodeId() == 0 &&
6068 "First node in topological sort has non-zero id!");
6069 assert(AllNodes.front().getNumOperands() == 0 &&
6070 "First node in topological sort has operands!");
6071 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6072 "Last node in topologic sort has unexpected id!");
6073 assert(AllNodes.back().use_empty() &&
6074 "Last node in topologic sort has users!");
6075 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6079 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6080 /// value is produced by SD.
6081 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6082 DbgInfo->add(DB, SD, isParameter);
6084 SD->setHasDebugValue(true);
6087 /// TransferDbgValues - Transfer SDDbgValues.
6088 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6089 if (From == To || !From.getNode()->getHasDebugValue())
6091 SDNode *FromNode = From.getNode();
6092 SDNode *ToNode = To.getNode();
6093 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6094 SmallVector<SDDbgValue *, 2> ClonedDVs;
6095 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6097 SDDbgValue *Dbg = *I;
6098 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6099 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6101 Dbg->getOffset(), Dbg->getDebugLoc(),
6103 ClonedDVs.push_back(Clone);
6106 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6107 E = ClonedDVs.end(); I != E; ++I)
6108 AddDbgValue(*I, ToNode, false);
6111 //===----------------------------------------------------------------------===//
6113 //===----------------------------------------------------------------------===//
6115 HandleSDNode::~HandleSDNode() {
6119 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6120 DebugLoc DL, const GlobalValue *GA,
6121 EVT VT, int64_t o, unsigned char TF)
6122 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6126 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6127 SDValue X, unsigned SrcAS,
6129 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6130 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6132 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6133 EVT memvt, MachineMemOperand *mmo)
6134 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6135 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6136 MMO->isNonTemporal(), MMO->isInvariant());
6137 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6138 assert(isNonTemporal() == MMO->isNonTemporal() &&
6139 "Non-temporal encoding error!");
6140 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6143 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6144 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6145 : SDNode(Opc, Order, dl, VTs, Ops),
6146 MemoryVT(memvt), MMO(mmo) {
6147 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6148 MMO->isNonTemporal(), MMO->isInvariant());
6149 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6150 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6153 /// Profile - Gather unique data for the node.
6155 void SDNode::Profile(FoldingSetNodeID &ID) const {
6156 AddNodeIDNode(ID, this);
6161 std::vector<EVT> VTs;
6164 VTs.reserve(MVT::LAST_VALUETYPE);
6165 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6166 VTs.push_back(MVT((MVT::SimpleValueType)i));
6171 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6172 static ManagedStatic<EVTArray> SimpleVTArray;
6173 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6175 /// getValueTypeList - Return a pointer to the specified value type.
6177 const EVT *SDNode::getValueTypeList(EVT VT) {
6178 if (VT.isExtended()) {
6179 sys::SmartScopedLock<true> Lock(*VTMutex);
6180 return &(*EVTs->insert(VT).first);
6182 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6183 "Value type out of range!");
6184 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6188 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6189 /// indicated value. This method ignores uses of other values defined by this
6191 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6192 assert(Value < getNumValues() && "Bad value!");
6194 // TODO: Only iterate over uses of a given value of the node
6195 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6196 if (UI.getUse().getResNo() == Value) {
6203 // Found exactly the right number of uses?
6208 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6209 /// value. This method ignores uses of other values defined by this operation.
6210 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6211 assert(Value < getNumValues() && "Bad value!");
6213 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6214 if (UI.getUse().getResNo() == Value)
6221 /// isOnlyUserOf - Return true if this node is the only use of N.
6223 bool SDNode::isOnlyUserOf(SDNode *N) const {
6225 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6236 /// isOperand - Return true if this node is an operand of N.
6238 bool SDValue::isOperandOf(SDNode *N) const {
6239 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6240 if (*this == N->getOperand(i))
6245 bool SDNode::isOperandOf(SDNode *N) const {
6246 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6247 if (this == N->OperandList[i].getNode())
6252 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6253 /// be a chain) reaches the specified operand without crossing any
6254 /// side-effecting instructions on any chain path. In practice, this looks
6255 /// through token factors and non-volatile loads. In order to remain efficient,
6256 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6257 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6258 unsigned Depth) const {
6259 if (*this == Dest) return true;
6261 // Don't search too deeply, we just want to be able to see through
6262 // TokenFactor's etc.
6263 if (Depth == 0) return false;
6265 // If this is a token factor, all inputs to the TF happen in parallel. If any
6266 // of the operands of the TF does not reach dest, then we cannot do the xform.
6267 if (getOpcode() == ISD::TokenFactor) {
6268 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6269 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6274 // Loads don't have side effects, look through them.
6275 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6276 if (!Ld->isVolatile())
6277 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6282 /// hasPredecessor - Return true if N is a predecessor of this node.
6283 /// N is either an operand of this node, or can be reached by recursively
6284 /// traversing up the operands.
6285 /// NOTE: This is an expensive method. Use it carefully.
6286 bool SDNode::hasPredecessor(const SDNode *N) const {
6287 SmallPtrSet<const SDNode *, 32> Visited;
6288 SmallVector<const SDNode *, 16> Worklist;
6289 return hasPredecessorHelper(N, Visited, Worklist);
6293 SDNode::hasPredecessorHelper(const SDNode *N,
6294 SmallPtrSet<const SDNode *, 32> &Visited,
6295 SmallVectorImpl<const SDNode *> &Worklist) const {
6296 if (Visited.empty()) {
6297 Worklist.push_back(this);
6299 // Take a look in the visited set. If we've already encountered this node
6300 // we needn't search further.
6301 if (Visited.count(N))
6305 // Haven't visited N yet. Continue the search.
6306 while (!Worklist.empty()) {
6307 const SDNode *M = Worklist.pop_back_val();
6308 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6309 SDNode *Op = M->getOperand(i).getNode();
6310 if (Visited.insert(Op))
6311 Worklist.push_back(Op);
6320 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6321 assert(Num < NumOperands && "Invalid child # of SDNode!");
6322 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6325 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6326 assert(N->getNumValues() == 1 &&
6327 "Can't unroll a vector with multiple results!");
6329 EVT VT = N->getValueType(0);
6330 unsigned NE = VT.getVectorNumElements();
6331 EVT EltVT = VT.getVectorElementType();
6334 SmallVector<SDValue, 8> Scalars;
6335 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6337 // If ResNE is 0, fully unroll the vector op.
6340 else if (NE > ResNE)
6344 for (i= 0; i != NE; ++i) {
6345 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6346 SDValue Operand = N->getOperand(j);
6347 EVT OperandVT = Operand.getValueType();
6348 if (OperandVT.isVector()) {
6349 // A vector operand; extract a single element.
6350 const TargetLowering *TLI = TM.getTargetLowering();
6351 EVT OperandEltVT = OperandVT.getVectorElementType();
6352 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6355 getConstant(i, TLI->getVectorIdxTy()));
6357 // A scalar operand; just use it as is.
6358 Operands[j] = Operand;
6362 switch (N->getOpcode()) {
6364 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6367 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6374 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6375 getShiftAmountOperand(Operands[0].getValueType(),
6378 case ISD::SIGN_EXTEND_INREG:
6379 case ISD::FP_ROUND_INREG: {
6380 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6381 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6383 getValueType(ExtVT)));
6388 for (; i < ResNE; ++i)
6389 Scalars.push_back(getUNDEF(EltVT));
6391 return getNode(ISD::BUILD_VECTOR, dl,
6392 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6396 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6397 /// location that is 'Dist' units away from the location that the 'Base' load
6398 /// is loading from.
6399 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6400 unsigned Bytes, int Dist) const {
6401 if (LD->getChain() != Base->getChain())
6403 EVT VT = LD->getValueType(0);
6404 if (VT.getSizeInBits() / 8 != Bytes)
6407 SDValue Loc = LD->getOperand(1);
6408 SDValue BaseLoc = Base->getOperand(1);
6409 if (Loc.getOpcode() == ISD::FrameIndex) {
6410 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6412 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6413 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6414 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6415 int FS = MFI->getObjectSize(FI);
6416 int BFS = MFI->getObjectSize(BFI);
6417 if (FS != BFS || FS != (int)Bytes) return false;
6418 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6422 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6423 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6426 const GlobalValue *GV1 = nullptr;
6427 const GlobalValue *GV2 = nullptr;
6428 int64_t Offset1 = 0;
6429 int64_t Offset2 = 0;
6430 const TargetLowering *TLI = TM.getTargetLowering();
6431 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6432 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6433 if (isGA1 && isGA2 && GV1 == GV2)
6434 return Offset1 == (Offset2 + Dist*Bytes);
6439 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6440 /// it cannot be inferred.
6441 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6442 // If this is a GlobalAddress + cst, return the alignment.
6443 const GlobalValue *GV;
6444 int64_t GVOffset = 0;
6445 const TargetLowering *TLI = TM.getTargetLowering();
6446 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6447 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6448 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6449 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6450 TLI->getDataLayout());
6451 unsigned AlignBits = KnownZero.countTrailingOnes();
6452 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6454 return MinAlign(Align, GVOffset);
6457 // If this is a direct reference to a stack slot, use information about the
6458 // stack slot's alignment.
6459 int FrameIdx = 1 << 31;
6460 int64_t FrameOffset = 0;
6461 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6462 FrameIdx = FI->getIndex();
6463 } else if (isBaseWithConstantOffset(Ptr) &&
6464 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6466 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6467 FrameOffset = Ptr.getConstantOperandVal(1);
6470 if (FrameIdx != (1 << 31)) {
6471 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6472 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6480 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6481 /// which is split (or expanded) into two not necessarily identical pieces.
6482 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6483 // Currently all types are split in half.
6485 if (!VT.isVector()) {
6486 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6488 unsigned NumElements = VT.getVectorNumElements();
6489 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6490 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6493 return std::make_pair(LoVT, HiVT);
6496 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6498 std::pair<SDValue, SDValue>
6499 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6501 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6502 N.getValueType().getVectorNumElements() &&
6503 "More vector elements requested than available!");
6505 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6506 getConstant(0, TLI->getVectorIdxTy()));
6507 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6508 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6509 return std::make_pair(Lo, Hi);
6512 void SelectionDAG::ExtractVectorElements(SDValue Op,
6513 SmallVectorImpl<SDValue> &Args,
6514 unsigned Start, unsigned Count) {
6515 EVT VT = Op.getValueType();
6517 Count = VT.getVectorNumElements();
6519 EVT EltVT = VT.getVectorElementType();
6520 EVT IdxTy = TLI->getVectorIdxTy();
6522 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6523 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6524 Op, getConstant(i, IdxTy)));
6528 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6529 unsigned GlobalAddressSDNode::getAddressSpace() const {
6530 return getGlobal()->getType()->getAddressSpace();
6534 Type *ConstantPoolSDNode::getType() const {
6535 if (isMachineConstantPoolEntry())
6536 return Val.MachineCPVal->getType();
6537 return Val.ConstVal->getType();
6540 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6542 unsigned &SplatBitSize,
6544 unsigned MinSplatBits,
6545 bool isBigEndian) const {
6546 EVT VT = getValueType(0);
6547 assert(VT.isVector() && "Expected a vector type");
6548 unsigned sz = VT.getSizeInBits();
6549 if (MinSplatBits > sz)
6552 SplatValue = APInt(sz, 0);
6553 SplatUndef = APInt(sz, 0);
6555 // Get the bits. Bits with undefined values (when the corresponding element
6556 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6557 // in SplatValue. If any of the values are not constant, give up and return
6559 unsigned int nOps = getNumOperands();
6560 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6561 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6563 for (unsigned j = 0; j < nOps; ++j) {
6564 unsigned i = isBigEndian ? nOps-1-j : j;
6565 SDValue OpVal = getOperand(i);
6566 unsigned BitPos = j * EltBitSize;
6568 if (OpVal.getOpcode() == ISD::UNDEF)
6569 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6570 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6571 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6572 zextOrTrunc(sz) << BitPos;
6573 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6574 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6579 // The build_vector is all constants or undefs. Find the smallest element
6580 // size that splats the vector.
6582 HasAnyUndefs = (SplatUndef != 0);
6585 unsigned HalfSize = sz / 2;
6586 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6587 APInt LowValue = SplatValue.trunc(HalfSize);
6588 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6589 APInt LowUndef = SplatUndef.trunc(HalfSize);
6591 // If the two halves do not match (ignoring undef bits), stop here.
6592 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6593 MinSplatBits > HalfSize)
6596 SplatValue = HighValue | LowValue;
6597 SplatUndef = HighUndef & LowUndef;
6606 SDValue BuildVectorSDNode::getConstantSplatValue() const {
6608 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6609 SDValue Op = getOperand(i);
6610 if (Op.getOpcode() == ISD::UNDEF)
6612 if (Op.getOpcode() != ISD::Constant && Op.getOpcode() != ISD::ConstantFP)
6617 else if (Splatted != Op)
6622 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6623 "Can only have a splat without a constant for all undefs.");
6624 return getOperand(0);
6630 bool BuildVectorSDNode::isConstant() const {
6631 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6632 unsigned Opc = getOperand(i).getOpcode();
6633 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6639 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6640 // Find the first non-undef value in the shuffle mask.
6642 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6645 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6647 // Make sure all remaining elements are either undef or the same as the first
6649 for (int Idx = Mask[i]; i != e; ++i)
6650 if (Mask[i] >= 0 && Mask[i] != Idx)
6656 static void checkForCyclesHelper(const SDNode *N,
6657 SmallPtrSet<const SDNode*, 32> &Visited,
6658 SmallPtrSet<const SDNode*, 32> &Checked,
6659 const llvm::SelectionDAG *DAG) {
6660 // If this node has already been checked, don't check it again.
6661 if (Checked.count(N))
6664 // If a node has already been visited on this depth-first walk, reject it as
6666 if (!Visited.insert(N)) {
6667 errs() << "Detected cycle in SelectionDAG\n";
6668 dbgs() << "Offending node:\n";
6669 N->dumprFull(DAG); dbgs() << "\n";
6673 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6674 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6681 void llvm::checkForCycles(const llvm::SDNode *N,
6682 const llvm::SelectionDAG *DAG,
6690 assert(N && "Checking nonexistent SDNode");
6691 SmallPtrSet<const SDNode*, 32> visited;
6692 SmallPtrSet<const SDNode*, 32> checked;
6693 checkForCyclesHelper(N, visited, checked, DAG);
6698 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6699 checkForCycles(DAG->getRoot().getNode(), DAG, force);