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 bool SplatHasUndefs;
1510 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1511 if (cast<BuildVectorSDNode>(N1)->getConstantSplatNode(SplatHasUndefs) &&
1515 FoldingSetNodeID ID;
1516 SDValue Ops[2] = { N1, N2 };
1517 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1518 for (unsigned i = 0; i != NElts; ++i)
1519 ID.AddInteger(MaskVec[i]);
1522 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1523 return SDValue(E, 0);
1525 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1526 // SDNode doesn't have access to it. This memory will be "leaked" when
1527 // the node is deallocated, but recovered when the NodeAllocator is released.
1528 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1529 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1531 ShuffleVectorSDNode *N =
1532 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1533 dl.getDebugLoc(), N1, N2,
1535 CSEMap.InsertNode(N, IP);
1536 AllNodes.push_back(N);
1537 return SDValue(N, 0);
1540 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1541 SDValue Val, SDValue DTy,
1542 SDValue STy, SDValue Rnd, SDValue Sat,
1543 ISD::CvtCode Code) {
1544 // If the src and dest types are the same and the conversion is between
1545 // integer types of the same sign or two floats, no conversion is necessary.
1547 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1550 FoldingSetNodeID ID;
1551 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1552 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1555 return SDValue(E, 0);
1557 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1560 CSEMap.InsertNode(N, IP);
1561 AllNodes.push_back(N);
1562 return SDValue(N, 0);
1565 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1566 FoldingSetNodeID ID;
1567 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1568 ID.AddInteger(RegNo);
1570 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1571 return SDValue(E, 0);
1573 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1574 CSEMap.InsertNode(N, IP);
1575 AllNodes.push_back(N);
1576 return SDValue(N, 0);
1579 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1580 FoldingSetNodeID ID;
1581 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1582 ID.AddPointer(RegMask);
1584 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1585 return SDValue(E, 0);
1587 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1588 CSEMap.InsertNode(N, IP);
1589 AllNodes.push_back(N);
1590 return SDValue(N, 0);
1593 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1594 FoldingSetNodeID ID;
1595 SDValue Ops[] = { Root };
1596 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1597 ID.AddPointer(Label);
1599 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1600 return SDValue(E, 0);
1602 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1603 dl.getDebugLoc(), Root, Label);
1604 CSEMap.InsertNode(N, IP);
1605 AllNodes.push_back(N);
1606 return SDValue(N, 0);
1610 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1613 unsigned char TargetFlags) {
1614 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1616 FoldingSetNodeID ID;
1617 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1619 ID.AddInteger(Offset);
1620 ID.AddInteger(TargetFlags);
1622 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1623 return SDValue(E, 0);
1625 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1627 CSEMap.InsertNode(N, IP);
1628 AllNodes.push_back(N);
1629 return SDValue(N, 0);
1632 SDValue SelectionDAG::getSrcValue(const Value *V) {
1633 assert((!V || V->getType()->isPointerTy()) &&
1634 "SrcValue is not a pointer?");
1636 FoldingSetNodeID ID;
1637 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1641 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1642 return SDValue(E, 0);
1644 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1645 CSEMap.InsertNode(N, IP);
1646 AllNodes.push_back(N);
1647 return SDValue(N, 0);
1650 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1651 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1652 FoldingSetNodeID ID;
1653 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1657 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1658 return SDValue(E, 0);
1660 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1661 CSEMap.InsertNode(N, IP);
1662 AllNodes.push_back(N);
1663 return SDValue(N, 0);
1666 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1667 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1668 unsigned SrcAS, unsigned DestAS) {
1669 SDValue Ops[] = {Ptr};
1670 FoldingSetNodeID ID;
1671 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1672 ID.AddInteger(SrcAS);
1673 ID.AddInteger(DestAS);
1676 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1677 return SDValue(E, 0);
1679 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1681 VT, Ptr, SrcAS, DestAS);
1682 CSEMap.InsertNode(N, IP);
1683 AllNodes.push_back(N);
1684 return SDValue(N, 0);
1687 /// getShiftAmountOperand - Return the specified value casted to
1688 /// the target's desired shift amount type.
1689 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1690 EVT OpTy = Op.getValueType();
1691 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1692 if (OpTy == ShTy || OpTy.isVector()) return Op;
1694 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1695 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1698 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1699 /// specified value type.
1700 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1701 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1702 unsigned ByteSize = VT.getStoreSize();
1703 Type *Ty = VT.getTypeForEVT(*getContext());
1704 const TargetLowering *TLI = TM.getTargetLowering();
1705 unsigned StackAlign =
1706 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1708 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1709 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1712 /// CreateStackTemporary - Create a stack temporary suitable for holding
1713 /// either of the specified value types.
1714 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1715 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1716 VT2.getStoreSizeInBits())/8;
1717 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1718 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1719 const TargetLowering *TLI = TM.getTargetLowering();
1720 const DataLayout *TD = TLI->getDataLayout();
1721 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1722 TD->getPrefTypeAlignment(Ty2));
1724 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1725 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1726 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1729 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1730 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1731 // These setcc operations always fold.
1735 case ISD::SETFALSE2: return getConstant(0, VT);
1737 case ISD::SETTRUE2: {
1738 const TargetLowering *TLI = TM.getTargetLowering();
1739 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1741 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1754 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1758 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1759 const APInt &C2 = N2C->getAPIntValue();
1760 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1761 const APInt &C1 = N1C->getAPIntValue();
1764 default: llvm_unreachable("Unknown integer setcc!");
1765 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1766 case ISD::SETNE: return getConstant(C1 != C2, VT);
1767 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1768 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1769 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1770 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1771 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1772 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1773 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1774 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1778 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1779 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1780 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1783 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1784 return getUNDEF(VT);
1786 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1787 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1788 return getUNDEF(VT);
1790 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1791 R==APFloat::cmpLessThan, VT);
1792 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1793 return getUNDEF(VT);
1795 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1796 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1797 return getUNDEF(VT);
1799 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1800 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1801 return getUNDEF(VT);
1803 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1804 R==APFloat::cmpEqual, VT);
1805 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1806 return getUNDEF(VT);
1808 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1809 R==APFloat::cmpEqual, VT);
1810 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1811 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1812 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1813 R==APFloat::cmpEqual, VT);
1814 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1815 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1816 R==APFloat::cmpLessThan, VT);
1817 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1818 R==APFloat::cmpUnordered, VT);
1819 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1820 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1823 // Ensure that the constant occurs on the RHS.
1824 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1825 MVT CompVT = N1.getValueType().getSimpleVT();
1826 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1829 return getSetCC(dl, VT, N2, N1, SwappedCond);
1833 // Could not fold it.
1837 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1838 /// use this predicate to simplify operations downstream.
1839 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1840 // This predicate is not safe for vector operations.
1841 if (Op.getValueType().isVector())
1844 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1845 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1848 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1849 /// this predicate to simplify operations downstream. Mask is known to be zero
1850 /// for bits that V cannot have.
1851 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1852 unsigned Depth) const {
1853 APInt KnownZero, KnownOne;
1854 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1855 return (KnownZero & Mask) == Mask;
1858 /// Determine which bits of Op are known to be either zero or one and return
1859 /// them in the KnownZero/KnownOne bitsets.
1860 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1861 APInt &KnownOne, unsigned Depth) const {
1862 const TargetLowering *TLI = TM.getTargetLowering();
1863 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1865 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1867 return; // Limit search depth.
1869 APInt KnownZero2, KnownOne2;
1871 switch (Op.getOpcode()) {
1873 // We know all of the bits for a constant!
1874 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1875 KnownZero = ~KnownOne;
1878 // If either the LHS or the RHS are Zero, the result is zero.
1879 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1880 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1882 // Output known-1 bits are only known if set in both the LHS & RHS.
1883 KnownOne &= KnownOne2;
1884 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1885 KnownZero |= KnownZero2;
1888 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1889 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1891 // Output known-0 bits are only known if clear in both the LHS & RHS.
1892 KnownZero &= KnownZero2;
1893 // Output known-1 are known to be set if set in either the LHS | RHS.
1894 KnownOne |= KnownOne2;
1897 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1898 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1900 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1901 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1902 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1903 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1904 KnownZero = KnownZeroOut;
1908 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1909 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1911 // If low bits are zero in either operand, output low known-0 bits.
1912 // Also compute a conserative estimate for high known-0 bits.
1913 // More trickiness is possible, but this is sufficient for the
1914 // interesting case of alignment computation.
1915 KnownOne.clearAllBits();
1916 unsigned TrailZ = KnownZero.countTrailingOnes() +
1917 KnownZero2.countTrailingOnes();
1918 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1919 KnownZero2.countLeadingOnes(),
1920 BitWidth) - BitWidth;
1922 TrailZ = std::min(TrailZ, BitWidth);
1923 LeadZ = std::min(LeadZ, BitWidth);
1924 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1925 APInt::getHighBitsSet(BitWidth, LeadZ);
1929 // For the purposes of computing leading zeros we can conservatively
1930 // treat a udiv as a logical right shift by the power of 2 known to
1931 // be less than the denominator.
1932 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1933 unsigned LeadZ = KnownZero2.countLeadingOnes();
1935 KnownOne2.clearAllBits();
1936 KnownZero2.clearAllBits();
1937 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1938 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1939 if (RHSUnknownLeadingOnes != BitWidth)
1940 LeadZ = std::min(BitWidth,
1941 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1943 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1947 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1948 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1950 // Only known if known in both the LHS and RHS.
1951 KnownOne &= KnownOne2;
1952 KnownZero &= KnownZero2;
1954 case ISD::SELECT_CC:
1955 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1956 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1958 // Only known if known in both the LHS and RHS.
1959 KnownOne &= KnownOne2;
1960 KnownZero &= KnownZero2;
1968 if (Op.getResNo() != 1)
1970 // The boolean result conforms to getBooleanContents. Fall through.
1972 // If we know the result of a setcc has the top bits zero, use this info.
1973 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1974 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1975 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1978 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1979 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1980 unsigned ShAmt = SA->getZExtValue();
1982 // If the shift count is an invalid immediate, don't do anything.
1983 if (ShAmt >= BitWidth)
1986 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1987 KnownZero <<= ShAmt;
1989 // low bits known zero.
1990 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1994 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1995 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1996 unsigned ShAmt = SA->getZExtValue();
1998 // If the shift count is an invalid immediate, don't do anything.
1999 if (ShAmt >= BitWidth)
2002 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2003 KnownZero = KnownZero.lshr(ShAmt);
2004 KnownOne = KnownOne.lshr(ShAmt);
2006 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2007 KnownZero |= HighBits; // High bits known zero.
2011 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2012 unsigned ShAmt = SA->getZExtValue();
2014 // If the shift count is an invalid immediate, don't do anything.
2015 if (ShAmt >= BitWidth)
2018 // If any of the demanded bits are produced by the sign extension, we also
2019 // demand the input sign bit.
2020 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2022 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2023 KnownZero = KnownZero.lshr(ShAmt);
2024 KnownOne = KnownOne.lshr(ShAmt);
2026 // Handle the sign bits.
2027 APInt SignBit = APInt::getSignBit(BitWidth);
2028 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2030 if (KnownZero.intersects(SignBit)) {
2031 KnownZero |= HighBits; // New bits are known zero.
2032 } else if (KnownOne.intersects(SignBit)) {
2033 KnownOne |= HighBits; // New bits are known one.
2037 case ISD::SIGN_EXTEND_INREG: {
2038 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2039 unsigned EBits = EVT.getScalarType().getSizeInBits();
2041 // Sign extension. Compute the demanded bits in the result that are not
2042 // present in the input.
2043 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2045 APInt InSignBit = APInt::getSignBit(EBits);
2046 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2048 // If the sign extended bits are demanded, we know that the sign
2050 InSignBit = InSignBit.zext(BitWidth);
2051 if (NewBits.getBoolValue())
2052 InputDemandedBits |= InSignBit;
2054 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2055 KnownOne &= InputDemandedBits;
2056 KnownZero &= InputDemandedBits;
2058 // If the sign bit of the input is known set or clear, then we know the
2059 // top bits of the result.
2060 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2061 KnownZero |= NewBits;
2062 KnownOne &= ~NewBits;
2063 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2064 KnownOne |= NewBits;
2065 KnownZero &= ~NewBits;
2066 } else { // Input sign bit unknown
2067 KnownZero &= ~NewBits;
2068 KnownOne &= ~NewBits;
2073 case ISD::CTTZ_ZERO_UNDEF:
2075 case ISD::CTLZ_ZERO_UNDEF:
2077 unsigned LowBits = Log2_32(BitWidth)+1;
2078 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2079 KnownOne.clearAllBits();
2083 LoadSDNode *LD = cast<LoadSDNode>(Op);
2084 // If this is a ZEXTLoad and we are looking at the loaded value.
2085 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2086 EVT VT = LD->getMemoryVT();
2087 unsigned MemBits = VT.getScalarType().getSizeInBits();
2088 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2089 } else if (const MDNode *Ranges = LD->getRanges()) {
2090 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2094 case ISD::ZERO_EXTEND: {
2095 EVT InVT = Op.getOperand(0).getValueType();
2096 unsigned InBits = InVT.getScalarType().getSizeInBits();
2097 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2098 KnownZero = KnownZero.trunc(InBits);
2099 KnownOne = KnownOne.trunc(InBits);
2100 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2101 KnownZero = KnownZero.zext(BitWidth);
2102 KnownOne = KnownOne.zext(BitWidth);
2103 KnownZero |= NewBits;
2106 case ISD::SIGN_EXTEND: {
2107 EVT InVT = Op.getOperand(0).getValueType();
2108 unsigned InBits = InVT.getScalarType().getSizeInBits();
2109 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2111 KnownZero = KnownZero.trunc(InBits);
2112 KnownOne = KnownOne.trunc(InBits);
2113 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2115 // Note if the sign bit is known to be zero or one.
2116 bool SignBitKnownZero = KnownZero.isNegative();
2117 bool SignBitKnownOne = KnownOne.isNegative();
2119 KnownZero = KnownZero.zext(BitWidth);
2120 KnownOne = KnownOne.zext(BitWidth);
2122 // If the sign bit is known zero or one, the top bits match.
2123 if (SignBitKnownZero)
2124 KnownZero |= NewBits;
2125 else if (SignBitKnownOne)
2126 KnownOne |= NewBits;
2129 case ISD::ANY_EXTEND: {
2130 EVT InVT = Op.getOperand(0).getValueType();
2131 unsigned InBits = InVT.getScalarType().getSizeInBits();
2132 KnownZero = KnownZero.trunc(InBits);
2133 KnownOne = KnownOne.trunc(InBits);
2134 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2135 KnownZero = KnownZero.zext(BitWidth);
2136 KnownOne = KnownOne.zext(BitWidth);
2139 case ISD::TRUNCATE: {
2140 EVT InVT = Op.getOperand(0).getValueType();
2141 unsigned InBits = InVT.getScalarType().getSizeInBits();
2142 KnownZero = KnownZero.zext(InBits);
2143 KnownOne = KnownOne.zext(InBits);
2144 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2145 KnownZero = KnownZero.trunc(BitWidth);
2146 KnownOne = KnownOne.trunc(BitWidth);
2149 case ISD::AssertZext: {
2150 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2151 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2152 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2153 KnownZero |= (~InMask);
2154 KnownOne &= (~KnownZero);
2158 // All bits are zero except the low bit.
2159 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2163 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2164 // We know that the top bits of C-X are clear if X contains less bits
2165 // than C (i.e. no wrap-around can happen). For example, 20-X is
2166 // positive if we can prove that X is >= 0 and < 16.
2167 if (CLHS->getAPIntValue().isNonNegative()) {
2168 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2169 // NLZ can't be BitWidth with no sign bit
2170 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2171 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2173 // If all of the MaskV bits are known to be zero, then we know the
2174 // output top bits are zero, because we now know that the output is
2176 if ((KnownZero2 & MaskV) == MaskV) {
2177 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2178 // Top bits known zero.
2179 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2187 // Output known-0 bits are known if clear or set in both the low clear bits
2188 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2189 // low 3 bits clear.
2190 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2191 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2193 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2194 KnownZeroOut = std::min(KnownZeroOut,
2195 KnownZero2.countTrailingOnes());
2197 if (Op.getOpcode() == ISD::ADD) {
2198 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2202 // With ADDE, a carry bit may be added in, so we can only use this
2203 // information if we know (at least) that the low two bits are clear. We
2204 // then return to the caller that the low bit is unknown but that other bits
2206 if (KnownZeroOut >= 2) // ADDE
2207 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2211 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2212 const APInt &RA = Rem->getAPIntValue().abs();
2213 if (RA.isPowerOf2()) {
2214 APInt LowBits = RA - 1;
2215 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2217 // The low bits of the first operand are unchanged by the srem.
2218 KnownZero = KnownZero2 & LowBits;
2219 KnownOne = KnownOne2 & LowBits;
2221 // If the first operand is non-negative or has all low bits zero, then
2222 // the upper bits are all zero.
2223 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2224 KnownZero |= ~LowBits;
2226 // If the first operand is negative and not all low bits are zero, then
2227 // the upper bits are all one.
2228 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2229 KnownOne |= ~LowBits;
2230 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2235 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2236 const APInt &RA = Rem->getAPIntValue();
2237 if (RA.isPowerOf2()) {
2238 APInt LowBits = (RA - 1);
2239 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2241 // The upper bits are all zero, the lower ones are unchanged.
2242 KnownZero = KnownZero2 | ~LowBits;
2243 KnownOne = KnownOne2 & LowBits;
2248 // Since the result is less than or equal to either operand, any leading
2249 // zero bits in either operand must also exist in the result.
2250 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2251 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2253 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2254 KnownZero2.countLeadingOnes());
2255 KnownOne.clearAllBits();
2256 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2259 case ISD::FrameIndex:
2260 case ISD::TargetFrameIndex:
2261 if (unsigned Align = InferPtrAlignment(Op)) {
2262 // The low bits are known zero if the pointer is aligned.
2263 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2269 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2272 case ISD::INTRINSIC_WO_CHAIN:
2273 case ISD::INTRINSIC_W_CHAIN:
2274 case ISD::INTRINSIC_VOID:
2275 // Allow the target to implement this method for its nodes.
2276 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2280 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2283 /// ComputeNumSignBits - Return the number of times the sign bit of the
2284 /// register is replicated into the other bits. We know that at least 1 bit
2285 /// is always equal to the sign bit (itself), but other cases can give us
2286 /// information. For example, immediately after an "SRA X, 2", we know that
2287 /// the top 3 bits are all equal to each other, so we return 3.
2288 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2289 const TargetLowering *TLI = TM.getTargetLowering();
2290 EVT VT = Op.getValueType();
2291 assert(VT.isInteger() && "Invalid VT!");
2292 unsigned VTBits = VT.getScalarType().getSizeInBits();
2294 unsigned FirstAnswer = 1;
2297 return 1; // Limit search depth.
2299 switch (Op.getOpcode()) {
2301 case ISD::AssertSext:
2302 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2303 return VTBits-Tmp+1;
2304 case ISD::AssertZext:
2305 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2308 case ISD::Constant: {
2309 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2310 return Val.getNumSignBits();
2313 case ISD::SIGN_EXTEND:
2315 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2316 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2318 case ISD::SIGN_EXTEND_INREG:
2319 // Max of the input and what this extends.
2321 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2324 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2325 return std::max(Tmp, Tmp2);
2328 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2329 // SRA X, C -> adds C sign bits.
2330 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2331 Tmp += C->getZExtValue();
2332 if (Tmp > VTBits) Tmp = VTBits;
2336 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2337 // shl destroys sign bits.
2338 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2339 if (C->getZExtValue() >= VTBits || // Bad shift.
2340 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2341 return Tmp - C->getZExtValue();
2346 case ISD::XOR: // NOT is handled here.
2347 // Logical binary ops preserve the number of sign bits at the worst.
2348 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2350 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2351 FirstAnswer = std::min(Tmp, Tmp2);
2352 // We computed what we know about the sign bits as our first
2353 // answer. Now proceed to the generic code that uses
2354 // computeKnownBits, and pick whichever answer is better.
2359 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2360 if (Tmp == 1) return 1; // Early out.
2361 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2362 return std::min(Tmp, Tmp2);
2370 if (Op.getResNo() != 1)
2372 // The boolean result conforms to getBooleanContents. Fall through.
2374 // If setcc returns 0/-1, all bits are sign bits.
2375 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2376 TargetLowering::ZeroOrNegativeOneBooleanContent)
2381 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2382 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2384 // Handle rotate right by N like a rotate left by 32-N.
2385 if (Op.getOpcode() == ISD::ROTR)
2386 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2388 // If we aren't rotating out all of the known-in sign bits, return the
2389 // number that are left. This handles rotl(sext(x), 1) for example.
2390 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2391 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2395 // Add can have at most one carry bit. Thus we know that the output
2396 // is, at worst, one more bit than the inputs.
2397 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2398 if (Tmp == 1) return 1; // Early out.
2400 // Special case decrementing a value (ADD X, -1):
2401 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2402 if (CRHS->isAllOnesValue()) {
2403 APInt KnownZero, KnownOne;
2404 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2406 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2408 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2411 // If we are subtracting one from a positive number, there is no carry
2412 // out of the result.
2413 if (KnownZero.isNegative())
2417 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2418 if (Tmp2 == 1) return 1;
2419 return std::min(Tmp, Tmp2)-1;
2422 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2423 if (Tmp2 == 1) return 1;
2426 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2427 if (CLHS->isNullValue()) {
2428 APInt KnownZero, KnownOne;
2429 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2430 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2432 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2435 // If the input is known to be positive (the sign bit is known clear),
2436 // the output of the NEG has the same number of sign bits as the input.
2437 if (KnownZero.isNegative())
2440 // Otherwise, we treat this like a SUB.
2443 // Sub can have at most one carry bit. Thus we know that the output
2444 // is, at worst, one more bit than the inputs.
2445 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2446 if (Tmp == 1) return 1; // Early out.
2447 return std::min(Tmp, Tmp2)-1;
2449 // FIXME: it's tricky to do anything useful for this, but it is an important
2450 // case for targets like X86.
2454 // If we are looking at the loaded value of the SDNode.
2455 if (Op.getResNo() == 0) {
2456 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2457 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2458 unsigned ExtType = LD->getExtensionType();
2461 case ISD::SEXTLOAD: // '17' bits known
2462 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2463 return VTBits-Tmp+1;
2464 case ISD::ZEXTLOAD: // '16' bits known
2465 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2471 // Allow the target to implement this method for its nodes.
2472 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2473 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2474 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2475 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2476 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2477 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2480 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2481 // use this information.
2482 APInt KnownZero, KnownOne;
2483 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2486 if (KnownZero.isNegative()) { // sign bit is 0
2488 } else if (KnownOne.isNegative()) { // sign bit is 1;
2495 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2496 // the number of identical bits in the top of the input value.
2498 Mask <<= Mask.getBitWidth()-VTBits;
2499 // Return # leading zeros. We use 'min' here in case Val was zero before
2500 // shifting. We don't want to return '64' as for an i32 "0".
2501 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2504 /// isBaseWithConstantOffset - Return true if the specified operand is an
2505 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2506 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2507 /// semantics as an ADD. This handles the equivalence:
2508 /// X|Cst == X+Cst iff X&Cst = 0.
2509 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2510 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2511 !isa<ConstantSDNode>(Op.getOperand(1)))
2514 if (Op.getOpcode() == ISD::OR &&
2515 !MaskedValueIsZero(Op.getOperand(0),
2516 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2523 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2524 // If we're told that NaNs won't happen, assume they won't.
2525 if (getTarget().Options.NoNaNsFPMath)
2528 // If the value is a constant, we can obviously see if it is a NaN or not.
2529 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2530 return !C->getValueAPF().isNaN();
2532 // TODO: Recognize more cases here.
2537 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2538 // If the value is a constant, we can obviously see if it is a zero or not.
2539 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2540 return !C->isZero();
2542 // TODO: Recognize more cases here.
2543 switch (Op.getOpcode()) {
2546 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2547 return !C->isNullValue();
2554 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2555 // Check the obvious case.
2556 if (A == B) return true;
2558 // For for negative and positive zero.
2559 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2560 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2561 if (CA->isZero() && CB->isZero()) return true;
2563 // Otherwise they may not be equal.
2567 /// getNode - Gets or creates the specified node.
2569 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2570 FoldingSetNodeID ID;
2571 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2573 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2574 return SDValue(E, 0);
2576 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2577 DL.getDebugLoc(), getVTList(VT));
2578 CSEMap.InsertNode(N, IP);
2580 AllNodes.push_back(N);
2584 return SDValue(N, 0);
2587 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2588 EVT VT, SDValue Operand) {
2589 // Constant fold unary operations with an integer constant operand. Even
2590 // opaque constant will be folded, because the folding of unary operations
2591 // doesn't create new constants with different values. Nevertheless, the
2592 // opaque flag is preserved during folding to prevent future folding with
2594 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2595 const APInt &Val = C->getAPIntValue();
2598 case ISD::SIGN_EXTEND:
2599 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2600 C->isTargetOpcode(), C->isOpaque());
2601 case ISD::ANY_EXTEND:
2602 case ISD::ZERO_EXTEND:
2604 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2605 C->isTargetOpcode(), C->isOpaque());
2606 case ISD::UINT_TO_FP:
2607 case ISD::SINT_TO_FP: {
2608 APFloat apf(EVTToAPFloatSemantics(VT),
2609 APInt::getNullValue(VT.getSizeInBits()));
2610 (void)apf.convertFromAPInt(Val,
2611 Opcode==ISD::SINT_TO_FP,
2612 APFloat::rmNearestTiesToEven);
2613 return getConstantFP(apf, VT);
2616 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2617 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2618 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2619 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2622 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2625 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2628 case ISD::CTLZ_ZERO_UNDEF:
2629 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2632 case ISD::CTTZ_ZERO_UNDEF:
2633 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2638 // Constant fold unary operations with a floating point constant operand.
2639 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2640 APFloat V = C->getValueAPF(); // make copy
2644 return getConstantFP(V, VT);
2647 return getConstantFP(V, VT);
2649 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2650 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2651 return getConstantFP(V, VT);
2655 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2656 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2657 return getConstantFP(V, VT);
2661 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2662 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2663 return getConstantFP(V, VT);
2666 case ISD::FP_EXTEND: {
2668 // This can return overflow, underflow, or inexact; we don't care.
2669 // FIXME need to be more flexible about rounding mode.
2670 (void)V.convert(EVTToAPFloatSemantics(VT),
2671 APFloat::rmNearestTiesToEven, &ignored);
2672 return getConstantFP(V, VT);
2674 case ISD::FP_TO_SINT:
2675 case ISD::FP_TO_UINT: {
2678 assert(integerPartWidth >= 64);
2679 // FIXME need to be more flexible about rounding mode.
2680 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2681 Opcode==ISD::FP_TO_SINT,
2682 APFloat::rmTowardZero, &ignored);
2683 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2685 APInt api(VT.getSizeInBits(), x);
2686 return getConstant(api, VT);
2689 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2690 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2691 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2692 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2697 unsigned OpOpcode = Operand.getNode()->getOpcode();
2699 case ISD::TokenFactor:
2700 case ISD::MERGE_VALUES:
2701 case ISD::CONCAT_VECTORS:
2702 return Operand; // Factor, merge or concat of one node? No need.
2703 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2704 case ISD::FP_EXTEND:
2705 assert(VT.isFloatingPoint() &&
2706 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2707 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2708 assert((!VT.isVector() ||
2709 VT.getVectorNumElements() ==
2710 Operand.getValueType().getVectorNumElements()) &&
2711 "Vector element count mismatch!");
2712 if (Operand.getOpcode() == ISD::UNDEF)
2713 return getUNDEF(VT);
2715 case ISD::SIGN_EXTEND:
2716 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2717 "Invalid SIGN_EXTEND!");
2718 if (Operand.getValueType() == VT) return Operand; // noop extension
2719 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2720 "Invalid sext node, dst < src!");
2721 assert((!VT.isVector() ||
2722 VT.getVectorNumElements() ==
2723 Operand.getValueType().getVectorNumElements()) &&
2724 "Vector element count mismatch!");
2725 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2726 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2727 else if (OpOpcode == ISD::UNDEF)
2728 // sext(undef) = 0, because the top bits will all be the same.
2729 return getConstant(0, VT);
2731 case ISD::ZERO_EXTEND:
2732 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2733 "Invalid ZERO_EXTEND!");
2734 if (Operand.getValueType() == VT) return Operand; // noop extension
2735 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2736 "Invalid zext node, dst < src!");
2737 assert((!VT.isVector() ||
2738 VT.getVectorNumElements() ==
2739 Operand.getValueType().getVectorNumElements()) &&
2740 "Vector element count mismatch!");
2741 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2742 return getNode(ISD::ZERO_EXTEND, DL, VT,
2743 Operand.getNode()->getOperand(0));
2744 else if (OpOpcode == ISD::UNDEF)
2745 // zext(undef) = 0, because the top bits will be zero.
2746 return getConstant(0, VT);
2748 case ISD::ANY_EXTEND:
2749 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2750 "Invalid ANY_EXTEND!");
2751 if (Operand.getValueType() == VT) return Operand; // noop extension
2752 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2753 "Invalid anyext node, dst < src!");
2754 assert((!VT.isVector() ||
2755 VT.getVectorNumElements() ==
2756 Operand.getValueType().getVectorNumElements()) &&
2757 "Vector element count mismatch!");
2759 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2760 OpOpcode == ISD::ANY_EXTEND)
2761 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2762 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2763 else if (OpOpcode == ISD::UNDEF)
2764 return getUNDEF(VT);
2766 // (ext (trunx x)) -> x
2767 if (OpOpcode == ISD::TRUNCATE) {
2768 SDValue OpOp = Operand.getNode()->getOperand(0);
2769 if (OpOp.getValueType() == VT)
2774 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2775 "Invalid TRUNCATE!");
2776 if (Operand.getValueType() == VT) return Operand; // noop truncate
2777 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2778 "Invalid truncate node, src < dst!");
2779 assert((!VT.isVector() ||
2780 VT.getVectorNumElements() ==
2781 Operand.getValueType().getVectorNumElements()) &&
2782 "Vector element count mismatch!");
2783 if (OpOpcode == ISD::TRUNCATE)
2784 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2785 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2786 OpOpcode == ISD::ANY_EXTEND) {
2787 // If the source is smaller than the dest, we still need an extend.
2788 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2789 .bitsLT(VT.getScalarType()))
2790 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2791 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2792 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2793 return Operand.getNode()->getOperand(0);
2795 if (OpOpcode == ISD::UNDEF)
2796 return getUNDEF(VT);
2799 // Basic sanity checking.
2800 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2801 && "Cannot BITCAST between types of different sizes!");
2802 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2803 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2804 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2805 if (OpOpcode == ISD::UNDEF)
2806 return getUNDEF(VT);
2808 case ISD::SCALAR_TO_VECTOR:
2809 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2810 (VT.getVectorElementType() == Operand.getValueType() ||
2811 (VT.getVectorElementType().isInteger() &&
2812 Operand.getValueType().isInteger() &&
2813 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2814 "Illegal SCALAR_TO_VECTOR node!");
2815 if (OpOpcode == ISD::UNDEF)
2816 return getUNDEF(VT);
2817 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2818 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2819 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2820 Operand.getConstantOperandVal(1) == 0 &&
2821 Operand.getOperand(0).getValueType() == VT)
2822 return Operand.getOperand(0);
2825 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2826 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2827 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2828 Operand.getNode()->getOperand(0));
2829 if (OpOpcode == ISD::FNEG) // --X -> X
2830 return Operand.getNode()->getOperand(0);
2833 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2834 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2839 SDVTList VTs = getVTList(VT);
2840 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2841 FoldingSetNodeID ID;
2842 SDValue Ops[1] = { Operand };
2843 AddNodeIDNode(ID, Opcode, VTs, Ops);
2845 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2846 return SDValue(E, 0);
2848 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2849 DL.getDebugLoc(), VTs, Operand);
2850 CSEMap.InsertNode(N, IP);
2852 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2853 DL.getDebugLoc(), VTs, Operand);
2856 AllNodes.push_back(N);
2860 return SDValue(N, 0);
2863 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2864 SDNode *Cst1, SDNode *Cst2) {
2865 // If the opcode is a target-specific ISD node, there's nothing we can
2866 // do here and the operand rules may not line up with the below, so
2868 if (Opcode >= ISD::BUILTIN_OP_END)
2871 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2872 SmallVector<SDValue, 4> Outputs;
2873 EVT SVT = VT.getScalarType();
2875 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2876 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2877 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2880 if (Scalar1 && Scalar2)
2881 // Scalar instruction.
2882 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2884 // For vectors extract each constant element into Inputs so we can constant
2885 // fold them individually.
2886 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2887 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2891 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2893 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2894 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2895 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2896 if (!V1 || !V2) // Not a constant, bail.
2899 if (V1->isOpaque() || V2->isOpaque())
2902 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2903 // FIXME: This is valid and could be handled by truncating the APInts.
2904 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2907 Inputs.push_back(std::make_pair(V1, V2));
2911 // We have a number of constant values, constant fold them element by element.
2912 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2913 const APInt &C1 = Inputs[I].first->getAPIntValue();
2914 const APInt &C2 = Inputs[I].second->getAPIntValue();
2918 Outputs.push_back(getConstant(C1 + C2, SVT));
2921 Outputs.push_back(getConstant(C1 - C2, SVT));
2924 Outputs.push_back(getConstant(C1 * C2, SVT));
2927 if (!C2.getBoolValue())
2929 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2932 if (!C2.getBoolValue())
2934 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2937 if (!C2.getBoolValue())
2939 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2942 if (!C2.getBoolValue())
2944 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2947 Outputs.push_back(getConstant(C1 & C2, SVT));
2950 Outputs.push_back(getConstant(C1 | C2, SVT));
2953 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2956 Outputs.push_back(getConstant(C1 << C2, SVT));
2959 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2962 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2965 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2968 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2975 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2976 "Expected a scalar or vector!"));
2978 // Handle the scalar case first.
2980 return Outputs.back();
2982 // We may have a vector type but a scalar result. Create a splat.
2983 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2985 // Build a big vector out of the scalar elements we generated.
2986 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2989 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2990 SDValue N2, bool nuw, bool nsw, bool exact) {
2991 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2992 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2995 case ISD::TokenFactor:
2996 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2997 N2.getValueType() == MVT::Other && "Invalid token factor!");
2998 // Fold trivial token factors.
2999 if (N1.getOpcode() == ISD::EntryToken) return N2;
3000 if (N2.getOpcode() == ISD::EntryToken) return N1;
3001 if (N1 == N2) return N1;
3003 case ISD::CONCAT_VECTORS:
3004 // Concat of UNDEFs is UNDEF.
3005 if (N1.getOpcode() == ISD::UNDEF &&
3006 N2.getOpcode() == ISD::UNDEF)
3007 return getUNDEF(VT);
3009 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3010 // one big BUILD_VECTOR.
3011 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3012 N2.getOpcode() == ISD::BUILD_VECTOR) {
3013 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3014 N1.getNode()->op_end());
3015 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3016 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3020 assert(VT.isInteger() && "This operator does not apply to FP types!");
3021 assert(N1.getValueType() == N2.getValueType() &&
3022 N1.getValueType() == VT && "Binary operator types must match!");
3023 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3024 // worth handling here.
3025 if (N2C && N2C->isNullValue())
3027 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3034 assert(VT.isInteger() && "This operator does not apply to FP types!");
3035 assert(N1.getValueType() == N2.getValueType() &&
3036 N1.getValueType() == VT && "Binary operator types must match!");
3037 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3038 // it's worth handling here.
3039 if (N2C && N2C->isNullValue())
3049 assert(VT.isInteger() && "This operator does not apply to FP types!");
3050 assert(N1.getValueType() == N2.getValueType() &&
3051 N1.getValueType() == VT && "Binary operator types must match!");
3058 if (getTarget().Options.UnsafeFPMath) {
3059 if (Opcode == ISD::FADD) {
3061 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3062 if (CFP->getValueAPF().isZero())
3065 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3066 if (CFP->getValueAPF().isZero())
3068 } else if (Opcode == ISD::FSUB) {
3070 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3071 if (CFP->getValueAPF().isZero())
3073 } else if (Opcode == ISD::FMUL) {
3074 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3077 // If the first operand isn't the constant, try the second
3079 CFP = dyn_cast<ConstantFPSDNode>(N2);
3086 return SDValue(CFP,0);
3088 if (CFP->isExactlyValue(1.0))
3093 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3094 assert(N1.getValueType() == N2.getValueType() &&
3095 N1.getValueType() == VT && "Binary operator types must match!");
3097 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3098 assert(N1.getValueType() == VT &&
3099 N1.getValueType().isFloatingPoint() &&
3100 N2.getValueType().isFloatingPoint() &&
3101 "Invalid FCOPYSIGN!");
3108 assert(VT == N1.getValueType() &&
3109 "Shift operators return type must be the same as their first arg");
3110 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3111 "Shifts only work on integers");
3112 assert((!VT.isVector() || VT == N2.getValueType()) &&
3113 "Vector shift amounts must be in the same as their first arg");
3114 // Verify that the shift amount VT is bit enough to hold valid shift
3115 // amounts. This catches things like trying to shift an i1024 value by an
3116 // i8, which is easy to fall into in generic code that uses
3117 // TLI.getShiftAmount().
3118 assert(N2.getValueType().getSizeInBits() >=
3119 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3120 "Invalid use of small shift amount with oversized value!");
3122 // Always fold shifts of i1 values so the code generator doesn't need to
3123 // handle them. Since we know the size of the shift has to be less than the
3124 // size of the value, the shift/rotate count is guaranteed to be zero.
3127 if (N2C && N2C->isNullValue())
3130 case ISD::FP_ROUND_INREG: {
3131 EVT EVT = cast<VTSDNode>(N2)->getVT();
3132 assert(VT == N1.getValueType() && "Not an inreg round!");
3133 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3134 "Cannot FP_ROUND_INREG integer types");
3135 assert(EVT.isVector() == VT.isVector() &&
3136 "FP_ROUND_INREG type should be vector iff the operand "
3138 assert((!EVT.isVector() ||
3139 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3140 "Vector element counts must match in FP_ROUND_INREG");
3141 assert(EVT.bitsLE(VT) && "Not rounding down!");
3143 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3147 assert(VT.isFloatingPoint() &&
3148 N1.getValueType().isFloatingPoint() &&
3149 VT.bitsLE(N1.getValueType()) &&
3150 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3151 if (N1.getValueType() == VT) return N1; // noop conversion.
3153 case ISD::AssertSext:
3154 case ISD::AssertZext: {
3155 EVT EVT = cast<VTSDNode>(N2)->getVT();
3156 assert(VT == N1.getValueType() && "Not an inreg extend!");
3157 assert(VT.isInteger() && EVT.isInteger() &&
3158 "Cannot *_EXTEND_INREG FP types");
3159 assert(!EVT.isVector() &&
3160 "AssertSExt/AssertZExt type should be the vector element type "
3161 "rather than the vector type!");
3162 assert(EVT.bitsLE(VT) && "Not extending!");
3163 if (VT == EVT) return N1; // noop assertion.
3166 case ISD::SIGN_EXTEND_INREG: {
3167 EVT EVT = cast<VTSDNode>(N2)->getVT();
3168 assert(VT == N1.getValueType() && "Not an inreg extend!");
3169 assert(VT.isInteger() && EVT.isInteger() &&
3170 "Cannot *_EXTEND_INREG FP types");
3171 assert(EVT.isVector() == VT.isVector() &&
3172 "SIGN_EXTEND_INREG type should be vector iff the operand "
3174 assert((!EVT.isVector() ||
3175 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3176 "Vector element counts must match in SIGN_EXTEND_INREG");
3177 assert(EVT.bitsLE(VT) && "Not extending!");
3178 if (EVT == VT) return N1; // Not actually extending
3181 APInt Val = N1C->getAPIntValue();
3182 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3183 Val <<= Val.getBitWidth()-FromBits;
3184 Val = Val.ashr(Val.getBitWidth()-FromBits);
3185 return getConstant(Val, VT);
3189 case ISD::EXTRACT_VECTOR_ELT:
3190 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3191 if (N1.getOpcode() == ISD::UNDEF)
3192 return getUNDEF(VT);
3194 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3195 // expanding copies of large vectors from registers.
3197 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3198 N1.getNumOperands() > 0) {
3200 N1.getOperand(0).getValueType().getVectorNumElements();
3201 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3202 N1.getOperand(N2C->getZExtValue() / Factor),
3203 getConstant(N2C->getZExtValue() % Factor,
3204 N2.getValueType()));
3207 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3208 // expanding large vector constants.
3209 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3210 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3212 if (VT != Elt.getValueType())
3213 // If the vector element type is not legal, the BUILD_VECTOR operands
3214 // are promoted and implicitly truncated, and the result implicitly
3215 // extended. Make that explicit here.
3216 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3221 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3222 // operations are lowered to scalars.
3223 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3224 // If the indices are the same, return the inserted element else
3225 // if the indices are known different, extract the element from
3226 // the original vector.
3227 SDValue N1Op2 = N1.getOperand(2);
3228 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3230 if (N1Op2C && N2C) {
3231 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3232 if (VT == N1.getOperand(1).getValueType())
3233 return N1.getOperand(1);
3235 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3238 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3242 case ISD::EXTRACT_ELEMENT:
3243 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3244 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3245 (N1.getValueType().isInteger() == VT.isInteger()) &&
3246 N1.getValueType() != VT &&
3247 "Wrong types for EXTRACT_ELEMENT!");
3249 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3250 // 64-bit integers into 32-bit parts. Instead of building the extract of
3251 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3252 if (N1.getOpcode() == ISD::BUILD_PAIR)
3253 return N1.getOperand(N2C->getZExtValue());
3255 // EXTRACT_ELEMENT of a constant int is also very common.
3256 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3257 unsigned ElementSize = VT.getSizeInBits();
3258 unsigned Shift = ElementSize * N2C->getZExtValue();
3259 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3260 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3263 case ISD::EXTRACT_SUBVECTOR: {
3265 if (VT.isSimple() && N1.getValueType().isSimple()) {
3266 assert(VT.isVector() && N1.getValueType().isVector() &&
3267 "Extract subvector VTs must be a vectors!");
3268 assert(VT.getVectorElementType() ==
3269 N1.getValueType().getVectorElementType() &&
3270 "Extract subvector VTs must have the same element type!");
3271 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3272 "Extract subvector must be from larger vector to smaller vector!");
3274 if (isa<ConstantSDNode>(Index.getNode())) {
3275 assert((VT.getVectorNumElements() +
3276 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3277 <= N1.getValueType().getVectorNumElements())
3278 && "Extract subvector overflow!");
3281 // Trivial extraction.
3282 if (VT.getSimpleVT() == N1.getSimpleValueType())
3289 // Perform trivial constant folding.
3290 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3291 if (SV.getNode()) return SV;
3293 // Canonicalize constant to RHS if commutative.
3294 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3295 std::swap(N1C, N2C);
3299 // Constant fold FP operations.
3300 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3301 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3303 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3304 // Canonicalize constant to RHS if commutative.
3305 std::swap(N1CFP, N2CFP);
3308 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3309 APFloat::opStatus s;
3312 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3313 if (s != APFloat::opInvalidOp)
3314 return getConstantFP(V1, VT);
3317 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3318 if (s!=APFloat::opInvalidOp)
3319 return getConstantFP(V1, VT);
3322 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3323 if (s!=APFloat::opInvalidOp)
3324 return getConstantFP(V1, VT);
3327 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3328 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3329 return getConstantFP(V1, VT);
3332 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3333 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3334 return getConstantFP(V1, VT);
3336 case ISD::FCOPYSIGN:
3338 return getConstantFP(V1, VT);
3343 if (Opcode == ISD::FP_ROUND) {
3344 APFloat V = N1CFP->getValueAPF(); // make copy
3346 // This can return overflow, underflow, or inexact; we don't care.
3347 // FIXME need to be more flexible about rounding mode.
3348 (void)V.convert(EVTToAPFloatSemantics(VT),
3349 APFloat::rmNearestTiesToEven, &ignored);
3350 return getConstantFP(V, VT);
3354 // Canonicalize an UNDEF to the RHS, even over a constant.
3355 if (N1.getOpcode() == ISD::UNDEF) {
3356 if (isCommutativeBinOp(Opcode)) {
3360 case ISD::FP_ROUND_INREG:
3361 case ISD::SIGN_EXTEND_INREG:
3367 return N1; // fold op(undef, arg2) -> undef
3375 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3376 // For vectors, we can't easily build an all zero vector, just return
3383 // Fold a bunch of operators when the RHS is undef.
3384 if (N2.getOpcode() == ISD::UNDEF) {
3387 if (N1.getOpcode() == ISD::UNDEF)
3388 // Handle undef ^ undef -> 0 special case. This is a common
3390 return getConstant(0, VT);
3400 return N2; // fold op(arg1, undef) -> undef
3406 if (getTarget().Options.UnsafeFPMath)
3414 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3415 // For vectors, we can't easily build an all zero vector, just return
3420 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3421 // For vectors, we can't easily build an all one vector, just return
3429 // Memoize this node if possible.
3431 SDVTList VTs = getVTList(VT);
3432 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3433 if (VT != MVT::Glue) {
3434 SDValue Ops[] = {N1, N2};
3435 FoldingSetNodeID ID;
3436 AddNodeIDNode(ID, Opcode, VTs, Ops);
3438 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3440 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3441 return SDValue(E, 0);
3443 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3445 CSEMap.InsertNode(N, IP);
3448 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3451 AllNodes.push_back(N);
3455 return SDValue(N, 0);
3458 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3459 SDValue N1, SDValue N2, SDValue N3) {
3460 // Perform various simplifications.
3461 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3464 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3465 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3466 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3467 if (N1CFP && N2CFP && N3CFP) {
3468 APFloat V1 = N1CFP->getValueAPF();
3469 const APFloat &V2 = N2CFP->getValueAPF();
3470 const APFloat &V3 = N3CFP->getValueAPF();
3471 APFloat::opStatus s =
3472 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3473 if (s != APFloat::opInvalidOp)
3474 return getConstantFP(V1, VT);
3478 case ISD::CONCAT_VECTORS:
3479 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3480 // one big BUILD_VECTOR.
3481 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3482 N2.getOpcode() == ISD::BUILD_VECTOR &&
3483 N3.getOpcode() == ISD::BUILD_VECTOR) {
3484 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3485 N1.getNode()->op_end());
3486 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3487 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3488 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3492 // Use FoldSetCC to simplify SETCC's.
3493 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3494 if (Simp.getNode()) return Simp;
3499 if (N1C->getZExtValue())
3500 return N2; // select true, X, Y -> X
3501 return N3; // select false, X, Y -> Y
3504 if (N2 == N3) return N2; // select C, X, X -> X
3506 case ISD::VECTOR_SHUFFLE:
3507 llvm_unreachable("should use getVectorShuffle constructor!");
3508 case ISD::INSERT_SUBVECTOR: {
3510 if (VT.isSimple() && N1.getValueType().isSimple()
3511 && N2.getValueType().isSimple()) {
3512 assert(VT.isVector() && N1.getValueType().isVector() &&
3513 N2.getValueType().isVector() &&
3514 "Insert subvector VTs must be a vectors");
3515 assert(VT == N1.getValueType() &&
3516 "Dest and insert subvector source types must match!");
3517 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3518 "Insert subvector must be from smaller vector to larger vector!");
3519 if (isa<ConstantSDNode>(Index.getNode())) {
3520 assert((N2.getValueType().getVectorNumElements() +
3521 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3522 <= VT.getVectorNumElements())
3523 && "Insert subvector overflow!");
3526 // Trivial insertion.
3527 if (VT.getSimpleVT() == N2.getSimpleValueType())
3533 // Fold bit_convert nodes from a type to themselves.
3534 if (N1.getValueType() == VT)
3539 // Memoize node if it doesn't produce a flag.
3541 SDVTList VTs = getVTList(VT);
3542 if (VT != MVT::Glue) {
3543 SDValue Ops[] = { N1, N2, N3 };
3544 FoldingSetNodeID ID;
3545 AddNodeIDNode(ID, Opcode, VTs, Ops);
3547 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3548 return SDValue(E, 0);
3550 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3551 DL.getDebugLoc(), VTs, N1, N2, N3);
3552 CSEMap.InsertNode(N, IP);
3554 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3555 DL.getDebugLoc(), VTs, N1, N2, N3);
3558 AllNodes.push_back(N);
3562 return SDValue(N, 0);
3565 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3566 SDValue N1, SDValue N2, SDValue N3,
3568 SDValue Ops[] = { N1, N2, N3, N4 };
3569 return getNode(Opcode, DL, VT, Ops);
3572 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3573 SDValue N1, SDValue N2, SDValue N3,
3574 SDValue N4, SDValue N5) {
3575 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3576 return getNode(Opcode, DL, VT, Ops);
3579 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3580 /// the incoming stack arguments to be loaded from the stack.
3581 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3582 SmallVector<SDValue, 8> ArgChains;
3584 // Include the original chain at the beginning of the list. When this is
3585 // used by target LowerCall hooks, this helps legalize find the
3586 // CALLSEQ_BEGIN node.
3587 ArgChains.push_back(Chain);
3589 // Add a chain value for each stack argument.
3590 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3591 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3592 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3593 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3594 if (FI->getIndex() < 0)
3595 ArgChains.push_back(SDValue(L, 1));
3597 // Build a tokenfactor for all the chains.
3598 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3601 /// getMemsetValue - Vectorized representation of the memset value
3603 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3605 assert(Value.getOpcode() != ISD::UNDEF);
3607 unsigned NumBits = VT.getScalarType().getSizeInBits();
3608 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3609 assert(C->getAPIntValue().getBitWidth() == 8);
3610 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3612 return DAG.getConstant(Val, VT);
3613 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3616 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3618 // Use a multiplication with 0x010101... to extend the input to the
3620 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3621 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3627 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3628 /// used when a memcpy is turned into a memset when the source is a constant
3630 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3631 const TargetLowering &TLI, StringRef Str) {
3632 // Handle vector with all elements zero.
3635 return DAG.getConstant(0, VT);
3636 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3637 return DAG.getConstantFP(0.0, VT);
3638 else if (VT.isVector()) {
3639 unsigned NumElts = VT.getVectorNumElements();
3640 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3641 return DAG.getNode(ISD::BITCAST, dl, VT,
3642 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3645 llvm_unreachable("Expected type!");
3648 assert(!VT.isVector() && "Can't handle vector type here!");
3649 unsigned NumVTBits = VT.getSizeInBits();
3650 unsigned NumVTBytes = NumVTBits / 8;
3651 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3653 APInt Val(NumVTBits, 0);
3654 if (TLI.isLittleEndian()) {
3655 for (unsigned i = 0; i != NumBytes; ++i)
3656 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3658 for (unsigned i = 0; i != NumBytes; ++i)
3659 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3662 // If the "cost" of materializing the integer immediate is less than the cost
3663 // of a load, then it is cost effective to turn the load into the immediate.
3664 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3665 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3666 return DAG.getConstant(Val, VT);
3667 return SDValue(nullptr, 0);
3670 /// getMemBasePlusOffset - Returns base and offset node for the
3672 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3673 SelectionDAG &DAG) {
3674 EVT VT = Base.getValueType();
3675 return DAG.getNode(ISD::ADD, dl,
3676 VT, Base, DAG.getConstant(Offset, VT));
3679 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3681 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3682 unsigned SrcDelta = 0;
3683 GlobalAddressSDNode *G = nullptr;
3684 if (Src.getOpcode() == ISD::GlobalAddress)
3685 G = cast<GlobalAddressSDNode>(Src);
3686 else if (Src.getOpcode() == ISD::ADD &&
3687 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3688 Src.getOperand(1).getOpcode() == ISD::Constant) {
3689 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3690 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3695 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3698 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3699 /// to replace the memset / memcpy. Return true if the number of memory ops
3700 /// is below the threshold. It returns the types of the sequence of
3701 /// memory ops to perform memset / memcpy by reference.
3702 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3703 unsigned Limit, uint64_t Size,
3704 unsigned DstAlign, unsigned SrcAlign,
3710 const TargetLowering &TLI) {
3711 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3712 "Expecting memcpy / memset source to meet alignment requirement!");
3713 // If 'SrcAlign' is zero, that means the memory operation does not need to
3714 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3715 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3716 // is the specified alignment of the memory operation. If it is zero, that
3717 // means it's possible to change the alignment of the destination.
3718 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3719 // not need to be loaded.
3720 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3721 IsMemset, ZeroMemset, MemcpyStrSrc,
3722 DAG.getMachineFunction());
3724 if (VT == MVT::Other) {
3726 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3727 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3728 VT = TLI.getPointerTy();
3730 switch (DstAlign & 7) {
3731 case 0: VT = MVT::i64; break;
3732 case 4: VT = MVT::i32; break;
3733 case 2: VT = MVT::i16; break;
3734 default: VT = MVT::i8; break;
3739 while (!TLI.isTypeLegal(LVT))
3740 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3741 assert(LVT.isInteger());
3747 unsigned NumMemOps = 0;
3749 unsigned VTSize = VT.getSizeInBits() / 8;
3750 while (VTSize > Size) {
3751 // For now, only use non-vector load / store's for the left-over pieces.
3756 if (VT.isVector() || VT.isFloatingPoint()) {
3757 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3758 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3759 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3761 else if (NewVT == MVT::i64 &&
3762 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3763 TLI.isSafeMemOpType(MVT::f64)) {
3764 // i64 is usually not legal on 32-bit targets, but f64 may be.
3772 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3773 if (NewVT == MVT::i8)
3775 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3777 NewVTSize = NewVT.getSizeInBits() / 8;
3779 // If the new VT cannot cover all of the remaining bits, then consider
3780 // issuing a (or a pair of) unaligned and overlapping load / store.
3781 // FIXME: Only does this for 64-bit or more since we don't have proper
3782 // cost model for unaligned load / store.
3785 if (NumMemOps && AllowOverlap &&
3786 VTSize >= 8 && NewVTSize < Size &&
3787 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3795 if (++NumMemOps > Limit)
3798 MemOps.push_back(VT);
3805 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3806 SDValue Chain, SDValue Dst,
3807 SDValue Src, uint64_t Size,
3808 unsigned Align, bool isVol,
3810 MachinePointerInfo DstPtrInfo,
3811 MachinePointerInfo SrcPtrInfo) {
3812 // Turn a memcpy of undef to nop.
3813 if (Src.getOpcode() == ISD::UNDEF)
3816 // Expand memcpy to a series of load and store ops if the size operand falls
3817 // below a certain threshold.
3818 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3819 // rather than maybe a humongous number of loads and stores.
3820 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3821 std::vector<EVT> MemOps;
3822 bool DstAlignCanChange = false;
3823 MachineFunction &MF = DAG.getMachineFunction();
3824 MachineFrameInfo *MFI = MF.getFrameInfo();
3826 MF.getFunction()->getAttributes().
3827 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3828 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3829 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3830 DstAlignCanChange = true;
3831 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3832 if (Align > SrcAlign)
3835 bool CopyFromStr = isMemSrcFromString(Src, Str);
3836 bool isZeroStr = CopyFromStr && Str.empty();
3837 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3839 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3840 (DstAlignCanChange ? 0 : Align),
3841 (isZeroStr ? 0 : SrcAlign),
3842 false, false, CopyFromStr, true, DAG, TLI))
3845 if (DstAlignCanChange) {
3846 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3847 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3849 // Don't promote to an alignment that would require dynamic stack
3851 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3852 if (!TRI->needsStackRealignment(MF))
3853 while (NewAlign > Align &&
3854 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3857 if (NewAlign > Align) {
3858 // Give the stack frame object a larger alignment if needed.
3859 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3860 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3865 SmallVector<SDValue, 8> OutChains;
3866 unsigned NumMemOps = MemOps.size();
3867 uint64_t SrcOff = 0, DstOff = 0;
3868 for (unsigned i = 0; i != NumMemOps; ++i) {
3870 unsigned VTSize = VT.getSizeInBits() / 8;
3871 SDValue Value, Store;
3873 if (VTSize > Size) {
3874 // Issuing an unaligned load / store pair that overlaps with the previous
3875 // pair. Adjust the offset accordingly.
3876 assert(i == NumMemOps-1 && i != 0);
3877 SrcOff -= VTSize - Size;
3878 DstOff -= VTSize - Size;
3882 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3883 // It's unlikely a store of a vector immediate can be done in a single
3884 // instruction. It would require a load from a constantpool first.
3885 // We only handle zero vectors here.
3886 // FIXME: Handle other cases where store of vector immediate is done in
3887 // a single instruction.
3888 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3889 if (Value.getNode())
3890 Store = DAG.getStore(Chain, dl, Value,
3891 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3892 DstPtrInfo.getWithOffset(DstOff), isVol,
3896 if (!Store.getNode()) {
3897 // The type might not be legal for the target. This should only happen
3898 // if the type is smaller than a legal type, as on PPC, so the right
3899 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3900 // to Load/Store if NVT==VT.
3901 // FIXME does the case above also need this?
3902 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3903 assert(NVT.bitsGE(VT));
3904 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3905 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3906 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3907 MinAlign(SrcAlign, SrcOff));
3908 Store = DAG.getTruncStore(Chain, dl, Value,
3909 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3910 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3913 OutChains.push_back(Store);
3919 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3922 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3923 SDValue Chain, SDValue Dst,
3924 SDValue Src, uint64_t Size,
3925 unsigned Align, bool isVol,
3927 MachinePointerInfo DstPtrInfo,
3928 MachinePointerInfo SrcPtrInfo) {
3929 // Turn a memmove of undef to nop.
3930 if (Src.getOpcode() == ISD::UNDEF)
3933 // Expand memmove to a series of load and store ops if the size operand falls
3934 // below a certain threshold.
3935 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3936 std::vector<EVT> MemOps;
3937 bool DstAlignCanChange = false;
3938 MachineFunction &MF = DAG.getMachineFunction();
3939 MachineFrameInfo *MFI = MF.getFrameInfo();
3940 bool OptSize = MF.getFunction()->getAttributes().
3941 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3942 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3943 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3944 DstAlignCanChange = true;
3945 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3946 if (Align > SrcAlign)
3948 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3950 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3951 (DstAlignCanChange ? 0 : Align), SrcAlign,
3952 false, false, false, false, DAG, TLI))
3955 if (DstAlignCanChange) {
3956 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3957 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3958 if (NewAlign > Align) {
3959 // Give the stack frame object a larger alignment if needed.
3960 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3961 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3966 uint64_t SrcOff = 0, DstOff = 0;
3967 SmallVector<SDValue, 8> LoadValues;
3968 SmallVector<SDValue, 8> LoadChains;
3969 SmallVector<SDValue, 8> OutChains;
3970 unsigned NumMemOps = MemOps.size();
3971 for (unsigned i = 0; i < NumMemOps; i++) {
3973 unsigned VTSize = VT.getSizeInBits() / 8;
3976 Value = DAG.getLoad(VT, dl, Chain,
3977 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3978 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3979 false, false, SrcAlign);
3980 LoadValues.push_back(Value);
3981 LoadChains.push_back(Value.getValue(1));
3984 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3986 for (unsigned i = 0; i < NumMemOps; i++) {
3988 unsigned VTSize = VT.getSizeInBits() / 8;
3991 Store = DAG.getStore(Chain, dl, LoadValues[i],
3992 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3993 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3994 OutChains.push_back(Store);
3998 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4001 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4004 /// \param DAG Selection DAG where lowered code is placed.
4005 /// \param dl Link to corresponding IR location.
4006 /// \param Chain Control flow dependency.
4007 /// \param Dst Pointer to destination memory location.
4008 /// \param Src Value of byte to write into the memory.
4009 /// \param Size Number of bytes to write.
4010 /// \param Align Alignment of the destination in bytes.
4011 /// \param isVol True if destination is volatile.
4012 /// \param DstPtrInfo IR information on the memory pointer.
4013 /// \returns New head in the control flow, if lowering was successful, empty
4014 /// SDValue otherwise.
4016 /// The function tries to replace 'llvm.memset' intrinsic with several store
4017 /// operations and value calculation code. This is usually profitable for small
4019 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4020 SDValue Chain, SDValue Dst,
4021 SDValue Src, uint64_t Size,
4022 unsigned Align, bool isVol,
4023 MachinePointerInfo DstPtrInfo) {
4024 // Turn a memset of undef to nop.
4025 if (Src.getOpcode() == ISD::UNDEF)
4028 // Expand memset to a series of load/store ops if the size operand
4029 // falls below a certain threshold.
4030 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4031 std::vector<EVT> MemOps;
4032 bool DstAlignCanChange = false;
4033 MachineFunction &MF = DAG.getMachineFunction();
4034 MachineFrameInfo *MFI = MF.getFrameInfo();
4035 bool OptSize = MF.getFunction()->getAttributes().
4036 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4037 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4038 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4039 DstAlignCanChange = true;
4041 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4042 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4043 Size, (DstAlignCanChange ? 0 : Align), 0,
4044 true, IsZeroVal, false, true, DAG, TLI))
4047 if (DstAlignCanChange) {
4048 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4049 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4050 if (NewAlign > Align) {
4051 // Give the stack frame object a larger alignment if needed.
4052 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4053 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4058 SmallVector<SDValue, 8> OutChains;
4059 uint64_t DstOff = 0;
4060 unsigned NumMemOps = MemOps.size();
4062 // Find the largest store and generate the bit pattern for it.
4063 EVT LargestVT = MemOps[0];
4064 for (unsigned i = 1; i < NumMemOps; i++)
4065 if (MemOps[i].bitsGT(LargestVT))
4066 LargestVT = MemOps[i];
4067 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4069 for (unsigned i = 0; i < NumMemOps; i++) {
4071 unsigned VTSize = VT.getSizeInBits() / 8;
4072 if (VTSize > Size) {
4073 // Issuing an unaligned load / store pair that overlaps with the previous
4074 // pair. Adjust the offset accordingly.
4075 assert(i == NumMemOps-1 && i != 0);
4076 DstOff -= VTSize - Size;
4079 // If this store is smaller than the largest store see whether we can get
4080 // the smaller value for free with a truncate.
4081 SDValue Value = MemSetValue;
4082 if (VT.bitsLT(LargestVT)) {
4083 if (!LargestVT.isVector() && !VT.isVector() &&
4084 TLI.isTruncateFree(LargestVT, VT))
4085 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4087 Value = getMemsetValue(Src, VT, DAG, dl);
4089 assert(Value.getValueType() == VT && "Value with wrong type.");
4090 SDValue Store = DAG.getStore(Chain, dl, Value,
4091 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4092 DstPtrInfo.getWithOffset(DstOff),
4093 isVol, false, Align);
4094 OutChains.push_back(Store);
4095 DstOff += VT.getSizeInBits() / 8;
4099 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4102 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4103 SDValue Src, SDValue Size,
4104 unsigned Align, bool isVol, bool AlwaysInline,
4105 MachinePointerInfo DstPtrInfo,
4106 MachinePointerInfo SrcPtrInfo) {
4107 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4109 // Check to see if we should lower the memcpy to loads and stores first.
4110 // For cases within the target-specified limits, this is the best choice.
4111 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4113 // Memcpy with size zero? Just return the original chain.
4114 if (ConstantSize->isNullValue())
4117 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4118 ConstantSize->getZExtValue(),Align,
4119 isVol, false, DstPtrInfo, SrcPtrInfo);
4120 if (Result.getNode())
4124 // Then check to see if we should lower the memcpy with target-specific
4125 // code. If the target chooses to do this, this is the next best.
4127 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4128 isVol, AlwaysInline,
4129 DstPtrInfo, SrcPtrInfo);
4130 if (Result.getNode())
4133 // If we really need inline code and the target declined to provide it,
4134 // use a (potentially long) sequence of loads and stores.
4136 assert(ConstantSize && "AlwaysInline requires a constant size!");
4137 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4138 ConstantSize->getZExtValue(), Align, isVol,
4139 true, DstPtrInfo, SrcPtrInfo);
4142 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4143 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4144 // respect volatile, so they may do things like read or write memory
4145 // beyond the given memory regions. But fixing this isn't easy, and most
4146 // people don't care.
4148 const TargetLowering *TLI = TM.getTargetLowering();
4150 // Emit a library call.
4151 TargetLowering::ArgListTy Args;
4152 TargetLowering::ArgListEntry Entry;
4153 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4154 Entry.Node = Dst; Args.push_back(Entry);
4155 Entry.Node = Src; Args.push_back(Entry);
4156 Entry.Node = Size; Args.push_back(Entry);
4157 // FIXME: pass in SDLoc
4158 TargetLowering::CallLoweringInfo CLI(*this);
4159 CLI.setDebugLoc(dl).setChain(Chain)
4160 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4161 Type::getVoidTy(*getContext()),
4162 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4163 TLI->getPointerTy()), std::move(Args), 0)
4164 .setDiscardResult();
4165 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4167 return CallResult.second;
4170 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4171 SDValue Src, SDValue Size,
4172 unsigned Align, bool isVol,
4173 MachinePointerInfo DstPtrInfo,
4174 MachinePointerInfo SrcPtrInfo) {
4175 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4177 // Check to see if we should lower the memmove to loads and stores first.
4178 // For cases within the target-specified limits, this is the best choice.
4179 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4181 // Memmove with size zero? Just return the original chain.
4182 if (ConstantSize->isNullValue())
4186 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4187 ConstantSize->getZExtValue(), Align, isVol,
4188 false, DstPtrInfo, SrcPtrInfo);
4189 if (Result.getNode())
4193 // Then check to see if we should lower the memmove with target-specific
4194 // code. If the target chooses to do this, this is the next best.
4196 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4197 DstPtrInfo, SrcPtrInfo);
4198 if (Result.getNode())
4201 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4202 // not be safe. See memcpy above for more details.
4204 const TargetLowering *TLI = TM.getTargetLowering();
4206 // Emit a library call.
4207 TargetLowering::ArgListTy Args;
4208 TargetLowering::ArgListEntry Entry;
4209 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4210 Entry.Node = Dst; Args.push_back(Entry);
4211 Entry.Node = Src; Args.push_back(Entry);
4212 Entry.Node = Size; Args.push_back(Entry);
4213 // FIXME: pass in SDLoc
4214 TargetLowering::CallLoweringInfo CLI(*this);
4215 CLI.setDebugLoc(dl).setChain(Chain)
4216 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4217 Type::getVoidTy(*getContext()),
4218 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4219 TLI->getPointerTy()), std::move(Args), 0)
4220 .setDiscardResult();
4221 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4223 return CallResult.second;
4226 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4227 SDValue Src, SDValue Size,
4228 unsigned Align, bool isVol,
4229 MachinePointerInfo DstPtrInfo) {
4230 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4232 // Check to see if we should lower the memset to stores first.
4233 // For cases within the target-specified limits, this is the best choice.
4234 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4236 // Memset with size zero? Just return the original chain.
4237 if (ConstantSize->isNullValue())
4241 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4242 Align, isVol, DstPtrInfo);
4244 if (Result.getNode())
4248 // Then check to see if we should lower the memset with target-specific
4249 // code. If the target chooses to do this, this is the next best.
4251 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4253 if (Result.getNode())
4256 // Emit a library call.
4257 const TargetLowering *TLI = TM.getTargetLowering();
4258 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4259 TargetLowering::ArgListTy Args;
4260 TargetLowering::ArgListEntry Entry;
4261 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4262 Args.push_back(Entry);
4263 // Extend or truncate the argument to be an i32 value for the call.
4264 if (Src.getValueType().bitsGT(MVT::i32))
4265 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4267 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4269 Entry.Ty = Type::getInt32Ty(*getContext());
4270 Entry.isSExt = true;
4271 Args.push_back(Entry);
4273 Entry.Ty = IntPtrTy;
4274 Entry.isSExt = false;
4275 Args.push_back(Entry);
4277 // FIXME: pass in SDLoc
4278 TargetLowering::CallLoweringInfo CLI(*this);
4279 CLI.setDebugLoc(dl).setChain(Chain)
4280 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4281 Type::getVoidTy(*getContext()),
4282 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4283 TLI->getPointerTy()), std::move(Args), 0)
4284 .setDiscardResult();
4286 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4287 return CallResult.second;
4290 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4291 SDVTList VTList, ArrayRef<SDValue> Ops,
4292 MachineMemOperand *MMO,
4293 AtomicOrdering SuccessOrdering,
4294 AtomicOrdering FailureOrdering,
4295 SynchronizationScope SynchScope) {
4296 FoldingSetNodeID ID;
4297 ID.AddInteger(MemVT.getRawBits());
4298 AddNodeIDNode(ID, Opcode, VTList, Ops);
4299 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4301 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4302 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4303 return SDValue(E, 0);
4306 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4307 // SDNode doesn't have access to it. This memory will be "leaked" when
4308 // the node is deallocated, but recovered when the allocator is released.
4309 // If the number of operands is less than 5 we use AtomicSDNode's internal
4311 unsigned NumOps = Ops.size();
4312 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4315 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4316 dl.getDebugLoc(), VTList, MemVT,
4317 Ops.data(), DynOps, NumOps, MMO,
4318 SuccessOrdering, FailureOrdering,
4320 CSEMap.InsertNode(N, IP);
4321 AllNodes.push_back(N);
4322 return SDValue(N, 0);
4325 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4326 SDVTList VTList, ArrayRef<SDValue> Ops,
4327 MachineMemOperand *MMO,
4328 AtomicOrdering Ordering,
4329 SynchronizationScope SynchScope) {
4330 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4331 Ordering, SynchScope);
4334 SDValue SelectionDAG::getAtomicCmpSwap(
4335 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4336 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4337 unsigned Alignment, AtomicOrdering SuccessOrdering,
4338 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4339 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4340 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4341 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4343 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4344 Alignment = getEVTAlignment(MemVT);
4346 MachineFunction &MF = getMachineFunction();
4348 // FIXME: Volatile isn't really correct; we should keep track of atomic
4349 // orderings in the memoperand.
4350 unsigned Flags = MachineMemOperand::MOVolatile;
4351 Flags |= MachineMemOperand::MOLoad;
4352 Flags |= MachineMemOperand::MOStore;
4354 MachineMemOperand *MMO =
4355 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4357 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4358 SuccessOrdering, FailureOrdering, SynchScope);
4361 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4362 SDVTList VTs, SDValue Chain, SDValue Ptr,
4363 SDValue Cmp, SDValue Swp,
4364 MachineMemOperand *MMO,
4365 AtomicOrdering SuccessOrdering,
4366 AtomicOrdering FailureOrdering,
4367 SynchronizationScope SynchScope) {
4368 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4369 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4370 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4372 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4373 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4374 SuccessOrdering, FailureOrdering, SynchScope);
4377 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4379 SDValue Ptr, SDValue Val,
4380 const Value* PtrVal,
4382 AtomicOrdering Ordering,
4383 SynchronizationScope SynchScope) {
4384 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4385 Alignment = getEVTAlignment(MemVT);
4387 MachineFunction &MF = getMachineFunction();
4388 // An atomic store does not load. An atomic load does not store.
4389 // (An atomicrmw obviously both loads and stores.)
4390 // For now, atomics are considered to be volatile always, and they are
4392 // FIXME: Volatile isn't really correct; we should keep track of atomic
4393 // orderings in the memoperand.
4394 unsigned Flags = MachineMemOperand::MOVolatile;
4395 if (Opcode != ISD::ATOMIC_STORE)
4396 Flags |= MachineMemOperand::MOLoad;
4397 if (Opcode != ISD::ATOMIC_LOAD)
4398 Flags |= MachineMemOperand::MOStore;
4400 MachineMemOperand *MMO =
4401 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4402 MemVT.getStoreSize(), Alignment);
4404 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4405 Ordering, SynchScope);
4408 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4410 SDValue Ptr, SDValue Val,
4411 MachineMemOperand *MMO,
4412 AtomicOrdering Ordering,
4413 SynchronizationScope SynchScope) {
4414 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4415 Opcode == ISD::ATOMIC_LOAD_SUB ||
4416 Opcode == ISD::ATOMIC_LOAD_AND ||
4417 Opcode == ISD::ATOMIC_LOAD_OR ||
4418 Opcode == ISD::ATOMIC_LOAD_XOR ||
4419 Opcode == ISD::ATOMIC_LOAD_NAND ||
4420 Opcode == ISD::ATOMIC_LOAD_MIN ||
4421 Opcode == ISD::ATOMIC_LOAD_MAX ||
4422 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4423 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4424 Opcode == ISD::ATOMIC_SWAP ||
4425 Opcode == ISD::ATOMIC_STORE) &&
4426 "Invalid Atomic Op");
4428 EVT VT = Val.getValueType();
4430 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4431 getVTList(VT, MVT::Other);
4432 SDValue Ops[] = {Chain, Ptr, Val};
4433 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4436 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4437 EVT VT, SDValue Chain,
4439 MachineMemOperand *MMO,
4440 AtomicOrdering Ordering,
4441 SynchronizationScope SynchScope) {
4442 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4444 SDVTList VTs = getVTList(VT, MVT::Other);
4445 SDValue Ops[] = {Chain, Ptr};
4446 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4449 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4450 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4451 if (Ops.size() == 1)
4454 SmallVector<EVT, 4> VTs;
4455 VTs.reserve(Ops.size());
4456 for (unsigned i = 0; i < Ops.size(); ++i)
4457 VTs.push_back(Ops[i].getValueType());
4458 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4462 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4463 ArrayRef<SDValue> Ops,
4464 EVT MemVT, MachinePointerInfo PtrInfo,
4465 unsigned Align, bool Vol,
4466 bool ReadMem, bool WriteMem) {
4467 if (Align == 0) // Ensure that codegen never sees alignment 0
4468 Align = getEVTAlignment(MemVT);
4470 MachineFunction &MF = getMachineFunction();
4473 Flags |= MachineMemOperand::MOStore;
4475 Flags |= MachineMemOperand::MOLoad;
4477 Flags |= MachineMemOperand::MOVolatile;
4478 MachineMemOperand *MMO =
4479 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4481 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4485 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4486 ArrayRef<SDValue> Ops, EVT MemVT,
4487 MachineMemOperand *MMO) {
4488 assert((Opcode == ISD::INTRINSIC_VOID ||
4489 Opcode == ISD::INTRINSIC_W_CHAIN ||
4490 Opcode == ISD::PREFETCH ||
4491 Opcode == ISD::LIFETIME_START ||
4492 Opcode == ISD::LIFETIME_END ||
4493 (Opcode <= INT_MAX &&
4494 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4495 "Opcode is not a memory-accessing opcode!");
4497 // Memoize the node unless it returns a flag.
4498 MemIntrinsicSDNode *N;
4499 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4500 FoldingSetNodeID ID;
4501 AddNodeIDNode(ID, Opcode, VTList, Ops);
4502 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4504 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4505 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4506 return SDValue(E, 0);
4509 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4510 dl.getDebugLoc(), VTList, Ops,
4512 CSEMap.InsertNode(N, IP);
4514 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4515 dl.getDebugLoc(), VTList, Ops,
4518 AllNodes.push_back(N);
4519 return SDValue(N, 0);
4522 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4523 /// MachinePointerInfo record from it. This is particularly useful because the
4524 /// code generator has many cases where it doesn't bother passing in a
4525 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4526 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4527 // If this is FI+Offset, we can model it.
4528 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4529 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4531 // If this is (FI+Offset1)+Offset2, we can model it.
4532 if (Ptr.getOpcode() != ISD::ADD ||
4533 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4534 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4535 return MachinePointerInfo();
4537 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4538 return MachinePointerInfo::getFixedStack(FI, Offset+
4539 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4542 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4543 /// MachinePointerInfo record from it. This is particularly useful because the
4544 /// code generator has many cases where it doesn't bother passing in a
4545 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4546 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4547 // If the 'Offset' value isn't a constant, we can't handle this.
4548 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4549 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4550 if (OffsetOp.getOpcode() == ISD::UNDEF)
4551 return InferPointerInfo(Ptr);
4552 return MachinePointerInfo();
4557 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4558 EVT VT, SDLoc dl, SDValue Chain,
4559 SDValue Ptr, SDValue Offset,
4560 MachinePointerInfo PtrInfo, EVT MemVT,
4561 bool isVolatile, bool isNonTemporal, bool isInvariant,
4562 unsigned Alignment, const MDNode *TBAAInfo,
4563 const MDNode *Ranges) {
4564 assert(Chain.getValueType() == MVT::Other &&
4565 "Invalid chain type");
4566 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4567 Alignment = getEVTAlignment(VT);
4569 unsigned Flags = MachineMemOperand::MOLoad;
4571 Flags |= MachineMemOperand::MOVolatile;
4573 Flags |= MachineMemOperand::MONonTemporal;
4575 Flags |= MachineMemOperand::MOInvariant;
4577 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4579 if (PtrInfo.V.isNull())
4580 PtrInfo = InferPointerInfo(Ptr, Offset);
4582 MachineFunction &MF = getMachineFunction();
4583 MachineMemOperand *MMO =
4584 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4586 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4590 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4591 EVT VT, SDLoc dl, SDValue Chain,
4592 SDValue Ptr, SDValue Offset, EVT MemVT,
4593 MachineMemOperand *MMO) {
4595 ExtType = ISD::NON_EXTLOAD;
4596 } else if (ExtType == ISD::NON_EXTLOAD) {
4597 assert(VT == MemVT && "Non-extending load from different memory type!");
4600 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4601 "Should only be an extending load, not truncating!");
4602 assert(VT.isInteger() == MemVT.isInteger() &&
4603 "Cannot convert from FP to Int or Int -> FP!");
4604 assert(VT.isVector() == MemVT.isVector() &&
4605 "Cannot use trunc store to convert to or from a vector!");
4606 assert((!VT.isVector() ||
4607 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4608 "Cannot use trunc store to change the number of vector elements!");
4611 bool Indexed = AM != ISD::UNINDEXED;
4612 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4613 "Unindexed load with an offset!");
4615 SDVTList VTs = Indexed ?
4616 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4617 SDValue Ops[] = { Chain, Ptr, Offset };
4618 FoldingSetNodeID ID;
4619 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4620 ID.AddInteger(MemVT.getRawBits());
4621 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4622 MMO->isNonTemporal(),
4623 MMO->isInvariant()));
4624 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4626 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4627 cast<LoadSDNode>(E)->refineAlignment(MMO);
4628 return SDValue(E, 0);
4630 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4631 dl.getDebugLoc(), VTs, AM, ExtType,
4633 CSEMap.InsertNode(N, IP);
4634 AllNodes.push_back(N);
4635 return SDValue(N, 0);
4638 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4639 SDValue Chain, SDValue Ptr,
4640 MachinePointerInfo PtrInfo,
4641 bool isVolatile, bool isNonTemporal,
4642 bool isInvariant, unsigned Alignment,
4643 const MDNode *TBAAInfo,
4644 const MDNode *Ranges) {
4645 SDValue Undef = getUNDEF(Ptr.getValueType());
4646 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4647 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4651 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4652 SDValue Chain, SDValue Ptr,
4653 MachineMemOperand *MMO) {
4654 SDValue Undef = getUNDEF(Ptr.getValueType());
4655 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4659 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4660 SDValue Chain, SDValue Ptr,
4661 MachinePointerInfo PtrInfo, EVT MemVT,
4662 bool isVolatile, bool isNonTemporal,
4663 unsigned Alignment, const MDNode *TBAAInfo) {
4664 SDValue Undef = getUNDEF(Ptr.getValueType());
4665 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4666 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4671 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4672 SDValue Chain, SDValue Ptr, EVT MemVT,
4673 MachineMemOperand *MMO) {
4674 SDValue Undef = getUNDEF(Ptr.getValueType());
4675 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4680 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4681 SDValue Offset, ISD::MemIndexedMode AM) {
4682 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4683 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4684 "Load is already a indexed load!");
4685 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4686 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4687 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4688 false, LD->getAlignment());
4691 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4692 SDValue Ptr, MachinePointerInfo PtrInfo,
4693 bool isVolatile, bool isNonTemporal,
4694 unsigned Alignment, const MDNode *TBAAInfo) {
4695 assert(Chain.getValueType() == MVT::Other &&
4696 "Invalid chain type");
4697 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4698 Alignment = getEVTAlignment(Val.getValueType());
4700 unsigned Flags = MachineMemOperand::MOStore;
4702 Flags |= MachineMemOperand::MOVolatile;
4704 Flags |= MachineMemOperand::MONonTemporal;
4706 if (PtrInfo.V.isNull())
4707 PtrInfo = InferPointerInfo(Ptr);
4709 MachineFunction &MF = getMachineFunction();
4710 MachineMemOperand *MMO =
4711 MF.getMachineMemOperand(PtrInfo, Flags,
4712 Val.getValueType().getStoreSize(), Alignment,
4715 return getStore(Chain, dl, Val, Ptr, MMO);
4718 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4719 SDValue Ptr, MachineMemOperand *MMO) {
4720 assert(Chain.getValueType() == MVT::Other &&
4721 "Invalid chain type");
4722 EVT VT = Val.getValueType();
4723 SDVTList VTs = getVTList(MVT::Other);
4724 SDValue Undef = getUNDEF(Ptr.getValueType());
4725 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4726 FoldingSetNodeID ID;
4727 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4728 ID.AddInteger(VT.getRawBits());
4729 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4730 MMO->isNonTemporal(), MMO->isInvariant()));
4731 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4733 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4734 cast<StoreSDNode>(E)->refineAlignment(MMO);
4735 return SDValue(E, 0);
4737 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4738 dl.getDebugLoc(), VTs,
4739 ISD::UNINDEXED, false, VT, MMO);
4740 CSEMap.InsertNode(N, IP);
4741 AllNodes.push_back(N);
4742 return SDValue(N, 0);
4745 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4746 SDValue Ptr, MachinePointerInfo PtrInfo,
4747 EVT SVT,bool isVolatile, bool isNonTemporal,
4749 const MDNode *TBAAInfo) {
4750 assert(Chain.getValueType() == MVT::Other &&
4751 "Invalid chain type");
4752 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4753 Alignment = getEVTAlignment(SVT);
4755 unsigned Flags = MachineMemOperand::MOStore;
4757 Flags |= MachineMemOperand::MOVolatile;
4759 Flags |= MachineMemOperand::MONonTemporal;
4761 if (PtrInfo.V.isNull())
4762 PtrInfo = InferPointerInfo(Ptr);
4764 MachineFunction &MF = getMachineFunction();
4765 MachineMemOperand *MMO =
4766 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4769 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4772 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4773 SDValue Ptr, EVT SVT,
4774 MachineMemOperand *MMO) {
4775 EVT VT = Val.getValueType();
4777 assert(Chain.getValueType() == MVT::Other &&
4778 "Invalid chain type");
4780 return getStore(Chain, dl, Val, Ptr, MMO);
4782 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4783 "Should only be a truncating store, not extending!");
4784 assert(VT.isInteger() == SVT.isInteger() &&
4785 "Can't do FP-INT conversion!");
4786 assert(VT.isVector() == SVT.isVector() &&
4787 "Cannot use trunc store to convert to or from a vector!");
4788 assert((!VT.isVector() ||
4789 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4790 "Cannot use trunc store to change the number of vector elements!");
4792 SDVTList VTs = getVTList(MVT::Other);
4793 SDValue Undef = getUNDEF(Ptr.getValueType());
4794 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4795 FoldingSetNodeID ID;
4796 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4797 ID.AddInteger(SVT.getRawBits());
4798 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4799 MMO->isNonTemporal(), MMO->isInvariant()));
4800 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4802 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4803 cast<StoreSDNode>(E)->refineAlignment(MMO);
4804 return SDValue(E, 0);
4806 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4807 dl.getDebugLoc(), VTs,
4808 ISD::UNINDEXED, true, SVT, MMO);
4809 CSEMap.InsertNode(N, IP);
4810 AllNodes.push_back(N);
4811 return SDValue(N, 0);
4815 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4816 SDValue Offset, ISD::MemIndexedMode AM) {
4817 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4818 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4819 "Store is already a indexed store!");
4820 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4821 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4822 FoldingSetNodeID ID;
4823 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4824 ID.AddInteger(ST->getMemoryVT().getRawBits());
4825 ID.AddInteger(ST->getRawSubclassData());
4826 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4828 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4829 return SDValue(E, 0);
4831 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4832 dl.getDebugLoc(), VTs, AM,
4833 ST->isTruncatingStore(),
4835 ST->getMemOperand());
4836 CSEMap.InsertNode(N, IP);
4837 AllNodes.push_back(N);
4838 return SDValue(N, 0);
4841 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4842 SDValue Chain, SDValue Ptr,
4845 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4846 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4849 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4850 ArrayRef<SDUse> Ops) {
4851 switch (Ops.size()) {
4852 case 0: return getNode(Opcode, DL, VT);
4853 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4854 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4855 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4859 // Copy from an SDUse array into an SDValue array for use with
4860 // the regular getNode logic.
4861 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4862 return getNode(Opcode, DL, VT, NewOps);
4865 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4866 ArrayRef<SDValue> Ops) {
4867 unsigned NumOps = Ops.size();
4869 case 0: return getNode(Opcode, DL, VT);
4870 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4871 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4872 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4878 case ISD::SELECT_CC: {
4879 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4880 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4881 "LHS and RHS of condition must have same type!");
4882 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4883 "True and False arms of SelectCC must have same type!");
4884 assert(Ops[2].getValueType() == VT &&
4885 "select_cc node must be of same type as true and false value!");
4889 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4890 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4891 "LHS/RHS of comparison should match types!");
4898 SDVTList VTs = getVTList(VT);
4900 if (VT != MVT::Glue) {
4901 FoldingSetNodeID ID;
4902 AddNodeIDNode(ID, Opcode, VTs, Ops);
4905 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4906 return SDValue(E, 0);
4908 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4910 CSEMap.InsertNode(N, IP);
4912 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4916 AllNodes.push_back(N);
4920 return SDValue(N, 0);
4923 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4924 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4925 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4928 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4929 ArrayRef<SDValue> Ops) {
4930 if (VTList.NumVTs == 1)
4931 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4935 // FIXME: figure out how to safely handle things like
4936 // int foo(int x) { return 1 << (x & 255); }
4937 // int bar() { return foo(256); }
4938 case ISD::SRA_PARTS:
4939 case ISD::SRL_PARTS:
4940 case ISD::SHL_PARTS:
4941 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4942 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4943 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4944 else if (N3.getOpcode() == ISD::AND)
4945 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4946 // If the and is only masking out bits that cannot effect the shift,
4947 // eliminate the and.
4948 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4949 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4950 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4956 // Memoize the node unless it returns a flag.
4958 unsigned NumOps = Ops.size();
4959 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4960 FoldingSetNodeID ID;
4961 AddNodeIDNode(ID, Opcode, VTList, Ops);
4963 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4964 return SDValue(E, 0);
4967 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4968 DL.getDebugLoc(), VTList, Ops[0]);
4969 } else if (NumOps == 2) {
4970 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4971 DL.getDebugLoc(), VTList, Ops[0],
4973 } else if (NumOps == 3) {
4974 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4975 DL.getDebugLoc(), VTList, Ops[0],
4978 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4981 CSEMap.InsertNode(N, IP);
4984 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4985 DL.getDebugLoc(), VTList, Ops[0]);
4986 } else if (NumOps == 2) {
4987 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4988 DL.getDebugLoc(), VTList, Ops[0],
4990 } else if (NumOps == 3) {
4991 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4992 DL.getDebugLoc(), VTList, Ops[0],
4995 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4999 AllNodes.push_back(N);
5003 return SDValue(N, 0);
5006 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5007 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5010 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5012 SDValue Ops[] = { N1 };
5013 return getNode(Opcode, DL, VTList, Ops);
5016 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5017 SDValue N1, SDValue N2) {
5018 SDValue Ops[] = { N1, N2 };
5019 return getNode(Opcode, DL, VTList, Ops);
5022 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5023 SDValue N1, SDValue N2, SDValue N3) {
5024 SDValue Ops[] = { N1, N2, N3 };
5025 return getNode(Opcode, DL, VTList, Ops);
5028 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5029 SDValue N1, SDValue N2, SDValue N3,
5031 SDValue Ops[] = { N1, N2, N3, N4 };
5032 return getNode(Opcode, DL, VTList, Ops);
5035 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5036 SDValue N1, SDValue N2, SDValue N3,
5037 SDValue N4, SDValue N5) {
5038 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5039 return getNode(Opcode, DL, VTList, Ops);
5042 SDVTList SelectionDAG::getVTList(EVT VT) {
5043 return makeVTList(SDNode::getValueTypeList(VT), 1);
5046 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5047 FoldingSetNodeID ID;
5049 ID.AddInteger(VT1.getRawBits());
5050 ID.AddInteger(VT2.getRawBits());
5053 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5055 EVT *Array = Allocator.Allocate<EVT>(2);
5058 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5059 VTListMap.InsertNode(Result, IP);
5061 return Result->getSDVTList();
5064 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5065 FoldingSetNodeID ID;
5067 ID.AddInteger(VT1.getRawBits());
5068 ID.AddInteger(VT2.getRawBits());
5069 ID.AddInteger(VT3.getRawBits());
5072 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5074 EVT *Array = Allocator.Allocate<EVT>(3);
5078 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5079 VTListMap.InsertNode(Result, IP);
5081 return Result->getSDVTList();
5084 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5085 FoldingSetNodeID ID;
5087 ID.AddInteger(VT1.getRawBits());
5088 ID.AddInteger(VT2.getRawBits());
5089 ID.AddInteger(VT3.getRawBits());
5090 ID.AddInteger(VT4.getRawBits());
5093 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5095 EVT *Array = Allocator.Allocate<EVT>(4);
5100 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5101 VTListMap.InsertNode(Result, IP);
5103 return Result->getSDVTList();
5106 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5107 unsigned NumVTs = VTs.size();
5108 FoldingSetNodeID ID;
5109 ID.AddInteger(NumVTs);
5110 for (unsigned index = 0; index < NumVTs; index++) {
5111 ID.AddInteger(VTs[index].getRawBits());
5115 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5117 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5118 std::copy(VTs.begin(), VTs.end(), Array);
5119 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5120 VTListMap.InsertNode(Result, IP);
5122 return Result->getSDVTList();
5126 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5127 /// specified operands. If the resultant node already exists in the DAG,
5128 /// this does not modify the specified node, instead it returns the node that
5129 /// already exists. If the resultant node does not exist in the DAG, the
5130 /// input node is returned. As a degenerate case, if you specify the same
5131 /// input operands as the node already has, the input node is returned.
5132 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5133 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5135 // Check to see if there is no change.
5136 if (Op == N->getOperand(0)) return N;
5138 // See if the modified node already exists.
5139 void *InsertPos = nullptr;
5140 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5143 // Nope it doesn't. Remove the node from its current place in the maps.
5145 if (!RemoveNodeFromCSEMaps(N))
5146 InsertPos = nullptr;
5148 // Now we update the operands.
5149 N->OperandList[0].set(Op);
5151 // If this gets put into a CSE map, add it.
5152 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5156 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5157 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5159 // Check to see if there is no change.
5160 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5161 return N; // No operands changed, just return the input node.
5163 // See if the modified node already exists.
5164 void *InsertPos = nullptr;
5165 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5168 // Nope it doesn't. Remove the node from its current place in the maps.
5170 if (!RemoveNodeFromCSEMaps(N))
5171 InsertPos = nullptr;
5173 // Now we update the operands.
5174 if (N->OperandList[0] != Op1)
5175 N->OperandList[0].set(Op1);
5176 if (N->OperandList[1] != Op2)
5177 N->OperandList[1].set(Op2);
5179 // If this gets put into a CSE map, add it.
5180 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5184 SDNode *SelectionDAG::
5185 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5186 SDValue Ops[] = { Op1, Op2, Op3 };
5187 return UpdateNodeOperands(N, Ops);
5190 SDNode *SelectionDAG::
5191 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5192 SDValue Op3, SDValue Op4) {
5193 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5194 return UpdateNodeOperands(N, Ops);
5197 SDNode *SelectionDAG::
5198 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5199 SDValue Op3, SDValue Op4, SDValue Op5) {
5200 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5201 return UpdateNodeOperands(N, Ops);
5204 SDNode *SelectionDAG::
5205 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5206 unsigned NumOps = Ops.size();
5207 assert(N->getNumOperands() == NumOps &&
5208 "Update with wrong number of operands");
5210 // Check to see if there is no change.
5211 bool AnyChange = false;
5212 for (unsigned i = 0; i != NumOps; ++i) {
5213 if (Ops[i] != N->getOperand(i)) {
5219 // No operands changed, just return the input node.
5220 if (!AnyChange) return N;
5222 // See if the modified node already exists.
5223 void *InsertPos = nullptr;
5224 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5227 // Nope it doesn't. Remove the node from its current place in the maps.
5229 if (!RemoveNodeFromCSEMaps(N))
5230 InsertPos = nullptr;
5232 // Now we update the operands.
5233 for (unsigned i = 0; i != NumOps; ++i)
5234 if (N->OperandList[i] != Ops[i])
5235 N->OperandList[i].set(Ops[i]);
5237 // If this gets put into a CSE map, add it.
5238 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5242 /// DropOperands - Release the operands and set this node to have
5244 void SDNode::DropOperands() {
5245 // Unlike the code in MorphNodeTo that does this, we don't need to
5246 // watch for dead nodes here.
5247 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5253 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5256 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 SDVTList VTs = getVTList(VT);
5259 return SelectNodeTo(N, MachineOpc, VTs, None);
5262 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5263 EVT VT, SDValue Op1) {
5264 SDVTList VTs = getVTList(VT);
5265 SDValue Ops[] = { Op1 };
5266 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 EVT VT, SDValue Op1,
5272 SDVTList VTs = getVTList(VT);
5273 SDValue Ops[] = { Op1, Op2 };
5274 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5277 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5278 EVT VT, SDValue Op1,
5279 SDValue Op2, SDValue Op3) {
5280 SDVTList VTs = getVTList(VT);
5281 SDValue Ops[] = { Op1, Op2, Op3 };
5282 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5285 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 EVT VT, ArrayRef<SDValue> Ops) {
5287 SDVTList VTs = getVTList(VT);
5288 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5291 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5292 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5293 SDVTList VTs = getVTList(VT1, VT2);
5294 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5297 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5299 SDVTList VTs = getVTList(VT1, VT2);
5300 return SelectNodeTo(N, MachineOpc, VTs, None);
5303 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5304 EVT VT1, EVT VT2, EVT VT3,
5305 ArrayRef<SDValue> Ops) {
5306 SDVTList VTs = getVTList(VT1, VT2, VT3);
5307 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5310 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5311 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5312 ArrayRef<SDValue> Ops) {
5313 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5314 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5317 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5320 SDVTList VTs = getVTList(VT1, VT2);
5321 SDValue Ops[] = { Op1 };
5322 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5325 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5327 SDValue Op1, SDValue Op2) {
5328 SDVTList VTs = getVTList(VT1, VT2);
5329 SDValue Ops[] = { Op1, Op2 };
5330 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5333 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5335 SDValue Op1, SDValue Op2,
5337 SDVTList VTs = getVTList(VT1, VT2);
5338 SDValue Ops[] = { Op1, Op2, Op3 };
5339 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5342 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5343 EVT VT1, EVT VT2, EVT VT3,
5344 SDValue Op1, SDValue Op2,
5346 SDVTList VTs = getVTList(VT1, VT2, VT3);
5347 SDValue Ops[] = { Op1, Op2, Op3 };
5348 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5351 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5352 SDVTList VTs,ArrayRef<SDValue> Ops) {
5353 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5354 // Reset the NodeID to -1.
5359 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5360 /// the line number information on the merged node since it is not possible to
5361 /// preserve the information that operation is associated with multiple lines.
5362 /// This will make the debugger working better at -O0, were there is a higher
5363 /// probability having other instructions associated with that line.
5365 /// For IROrder, we keep the smaller of the two
5366 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5367 DebugLoc NLoc = N->getDebugLoc();
5368 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5369 (OLoc.getDebugLoc() != NLoc)) {
5370 N->setDebugLoc(DebugLoc());
5372 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5373 N->setIROrder(Order);
5377 /// MorphNodeTo - This *mutates* the specified node to have the specified
5378 /// return type, opcode, and operands.
5380 /// Note that MorphNodeTo returns the resultant node. If there is already a
5381 /// node of the specified opcode and operands, it returns that node instead of
5382 /// the current one. Note that the SDLoc need not be the same.
5384 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5385 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5386 /// node, and because it doesn't require CSE recalculation for any of
5387 /// the node's users.
5389 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5390 SDVTList VTs, ArrayRef<SDValue> Ops) {
5391 unsigned NumOps = Ops.size();
5392 // If an identical node already exists, use it.
5394 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5395 FoldingSetNodeID ID;
5396 AddNodeIDNode(ID, Opc, VTs, Ops);
5397 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5398 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5401 if (!RemoveNodeFromCSEMaps(N))
5404 // Start the morphing.
5406 N->ValueList = VTs.VTs;
5407 N->NumValues = VTs.NumVTs;
5409 // Clear the operands list, updating used nodes to remove this from their
5410 // use list. Keep track of any operands that become dead as a result.
5411 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5412 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5414 SDNode *Used = Use.getNode();
5416 if (Used->use_empty())
5417 DeadNodeSet.insert(Used);
5420 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5421 // Initialize the memory references information.
5422 MN->setMemRefs(nullptr, nullptr);
5423 // If NumOps is larger than the # of operands we can have in a
5424 // MachineSDNode, reallocate the operand list.
5425 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5426 if (MN->OperandsNeedDelete)
5427 delete[] MN->OperandList;
5428 if (NumOps > array_lengthof(MN->LocalOperands))
5429 // We're creating a final node that will live unmorphed for the
5430 // remainder of the current SelectionDAG iteration, so we can allocate
5431 // the operands directly out of a pool with no recycling metadata.
5432 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5433 Ops.data(), NumOps);
5435 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5436 MN->OperandsNeedDelete = false;
5438 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5440 // If NumOps is larger than the # of operands we currently have, reallocate
5441 // the operand list.
5442 if (NumOps > N->NumOperands) {
5443 if (N->OperandsNeedDelete)
5444 delete[] N->OperandList;
5445 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5446 N->OperandsNeedDelete = true;
5448 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5451 // Delete any nodes that are still dead after adding the uses for the
5453 if (!DeadNodeSet.empty()) {
5454 SmallVector<SDNode *, 16> DeadNodes;
5455 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5456 E = DeadNodeSet.end(); I != E; ++I)
5457 if ((*I)->use_empty())
5458 DeadNodes.push_back(*I);
5459 RemoveDeadNodes(DeadNodes);
5463 CSEMap.InsertNode(N, IP); // Memoize the new node.
5468 /// getMachineNode - These are used for target selectors to create a new node
5469 /// with specified return type(s), MachineInstr opcode, and operands.
5471 /// Note that getMachineNode returns the resultant node. If there is already a
5472 /// node of the specified opcode and operands, it returns that node instead of
5473 /// the current one.
5475 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5476 SDVTList VTs = getVTList(VT);
5477 return getMachineNode(Opcode, dl, VTs, None);
5481 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5482 SDVTList VTs = getVTList(VT);
5483 SDValue Ops[] = { Op1 };
5484 return getMachineNode(Opcode, dl, VTs, Ops);
5488 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5489 SDValue Op1, SDValue Op2) {
5490 SDVTList VTs = getVTList(VT);
5491 SDValue Ops[] = { Op1, Op2 };
5492 return getMachineNode(Opcode, dl, VTs, Ops);
5496 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5497 SDValue Op1, SDValue Op2, SDValue Op3) {
5498 SDVTList VTs = getVTList(VT);
5499 SDValue Ops[] = { Op1, Op2, Op3 };
5500 return getMachineNode(Opcode, dl, VTs, Ops);
5504 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5505 ArrayRef<SDValue> Ops) {
5506 SDVTList VTs = getVTList(VT);
5507 return getMachineNode(Opcode, dl, VTs, Ops);
5511 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5512 SDVTList VTs = getVTList(VT1, VT2);
5513 return getMachineNode(Opcode, dl, VTs, None);
5517 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5518 EVT VT1, EVT VT2, SDValue Op1) {
5519 SDVTList VTs = getVTList(VT1, VT2);
5520 SDValue Ops[] = { Op1 };
5521 return getMachineNode(Opcode, dl, VTs, Ops);
5525 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5526 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5527 SDVTList VTs = getVTList(VT1, VT2);
5528 SDValue Ops[] = { Op1, Op2 };
5529 return getMachineNode(Opcode, dl, VTs, Ops);
5533 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5534 EVT VT1, EVT VT2, SDValue Op1,
5535 SDValue Op2, SDValue Op3) {
5536 SDVTList VTs = getVTList(VT1, VT2);
5537 SDValue Ops[] = { Op1, Op2, Op3 };
5538 return getMachineNode(Opcode, dl, VTs, Ops);
5542 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5544 ArrayRef<SDValue> Ops) {
5545 SDVTList VTs = getVTList(VT1, VT2);
5546 return getMachineNode(Opcode, dl, VTs, Ops);
5550 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5551 EVT VT1, EVT VT2, EVT VT3,
5552 SDValue Op1, SDValue Op2) {
5553 SDVTList VTs = getVTList(VT1, VT2, VT3);
5554 SDValue Ops[] = { Op1, Op2 };
5555 return getMachineNode(Opcode, dl, VTs, Ops);
5559 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5560 EVT VT1, EVT VT2, EVT VT3,
5561 SDValue Op1, SDValue Op2, SDValue Op3) {
5562 SDVTList VTs = getVTList(VT1, VT2, VT3);
5563 SDValue Ops[] = { Op1, Op2, Op3 };
5564 return getMachineNode(Opcode, dl, VTs, Ops);
5568 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5569 EVT VT1, EVT VT2, EVT VT3,
5570 ArrayRef<SDValue> Ops) {
5571 SDVTList VTs = getVTList(VT1, VT2, VT3);
5572 return getMachineNode(Opcode, dl, VTs, Ops);
5576 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5577 EVT VT2, EVT VT3, EVT VT4,
5578 ArrayRef<SDValue> Ops) {
5579 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5580 return getMachineNode(Opcode, dl, VTs, Ops);
5584 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5585 ArrayRef<EVT> ResultTys,
5586 ArrayRef<SDValue> Ops) {
5587 SDVTList VTs = getVTList(ResultTys);
5588 return getMachineNode(Opcode, dl, VTs, Ops);
5592 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5593 ArrayRef<SDValue> OpsArray) {
5594 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5597 const SDValue *Ops = OpsArray.data();
5598 unsigned NumOps = OpsArray.size();
5601 FoldingSetNodeID ID;
5602 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5604 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5605 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5609 // Allocate a new MachineSDNode.
5610 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5611 DL.getDebugLoc(), VTs);
5613 // Initialize the operands list.
5614 if (NumOps > array_lengthof(N->LocalOperands))
5615 // We're creating a final node that will live unmorphed for the
5616 // remainder of the current SelectionDAG iteration, so we can allocate
5617 // the operands directly out of a pool with no recycling metadata.
5618 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5621 N->InitOperands(N->LocalOperands, Ops, NumOps);
5622 N->OperandsNeedDelete = false;
5625 CSEMap.InsertNode(N, IP);
5627 AllNodes.push_back(N);
5629 VerifyMachineNode(N);
5634 /// getTargetExtractSubreg - A convenience function for creating
5635 /// TargetOpcode::EXTRACT_SUBREG nodes.
5637 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5639 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5640 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5641 VT, Operand, SRIdxVal);
5642 return SDValue(Subreg, 0);
5645 /// getTargetInsertSubreg - A convenience function for creating
5646 /// TargetOpcode::INSERT_SUBREG nodes.
5648 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5649 SDValue Operand, SDValue Subreg) {
5650 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5651 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5652 VT, Operand, Subreg, SRIdxVal);
5653 return SDValue(Result, 0);
5656 /// getNodeIfExists - Get the specified node if it's already available, or
5657 /// else return NULL.
5658 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5659 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5661 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5662 FoldingSetNodeID ID;
5663 AddNodeIDNode(ID, Opcode, VTList, Ops);
5664 if (isBinOpWithFlags(Opcode))
5665 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5667 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5673 /// getDbgValue - Creates a SDDbgValue node.
5677 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5678 bool IsIndirect, uint64_t Off,
5679 DebugLoc DL, unsigned O) {
5680 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5685 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5687 DebugLoc DL, unsigned O) {
5688 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5693 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5694 DebugLoc DL, unsigned O) {
5695 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5700 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5701 /// pointed to by a use iterator is deleted, increment the use iterator
5702 /// so that it doesn't dangle.
5704 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5705 SDNode::use_iterator &UI;
5706 SDNode::use_iterator &UE;
5708 void NodeDeleted(SDNode *N, SDNode *E) override {
5709 // Increment the iterator as needed.
5710 while (UI != UE && N == *UI)
5715 RAUWUpdateListener(SelectionDAG &d,
5716 SDNode::use_iterator &ui,
5717 SDNode::use_iterator &ue)
5718 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5723 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5724 /// This can cause recursive merging of nodes in the DAG.
5726 /// This version assumes From has a single result value.
5728 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5729 SDNode *From = FromN.getNode();
5730 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5731 "Cannot replace with this method!");
5732 assert(From != To.getNode() && "Cannot replace uses of with self");
5734 // Iterate over all the existing uses of From. New uses will be added
5735 // to the beginning of the use list, which we avoid visiting.
5736 // This specifically avoids visiting uses of From that arise while the
5737 // replacement is happening, because any such uses would be the result
5738 // of CSE: If an existing node looks like From after one of its operands
5739 // is replaced by To, we don't want to replace of all its users with To
5740 // too. See PR3018 for more info.
5741 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5742 RAUWUpdateListener Listener(*this, UI, UE);
5746 // This node is about to morph, remove its old self from the CSE maps.
5747 RemoveNodeFromCSEMaps(User);
5749 // A user can appear in a use list multiple times, and when this
5750 // happens the uses are usually next to each other in the list.
5751 // To help reduce the number of CSE recomputations, process all
5752 // the uses of this user that we can find this way.
5754 SDUse &Use = UI.getUse();
5757 } while (UI != UE && *UI == User);
5759 // Now that we have modified User, add it back to the CSE maps. If it
5760 // already exists there, recursively merge the results together.
5761 AddModifiedNodeToCSEMaps(User);
5764 // If we just RAUW'd the root, take note.
5765 if (FromN == getRoot())
5769 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5770 /// This can cause recursive merging of nodes in the DAG.
5772 /// This version assumes that for each value of From, there is a
5773 /// corresponding value in To in the same position with the same type.
5775 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5777 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5778 assert((!From->hasAnyUseOfValue(i) ||
5779 From->getValueType(i) == To->getValueType(i)) &&
5780 "Cannot use this version of ReplaceAllUsesWith!");
5783 // Handle the trivial case.
5787 // Iterate over just the existing users of From. See the comments in
5788 // the ReplaceAllUsesWith above.
5789 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5790 RAUWUpdateListener Listener(*this, UI, UE);
5794 // This node is about to morph, remove its old self from the CSE maps.
5795 RemoveNodeFromCSEMaps(User);
5797 // A user can appear in a use list multiple times, and when this
5798 // happens the uses are usually next to each other in the list.
5799 // To help reduce the number of CSE recomputations, process all
5800 // the uses of this user that we can find this way.
5802 SDUse &Use = UI.getUse();
5805 } while (UI != UE && *UI == User);
5807 // Now that we have modified User, add it back to the CSE maps. If it
5808 // already exists there, recursively merge the results together.
5809 AddModifiedNodeToCSEMaps(User);
5812 // If we just RAUW'd the root, take note.
5813 if (From == getRoot().getNode())
5814 setRoot(SDValue(To, getRoot().getResNo()));
5817 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5818 /// This can cause recursive merging of nodes in the DAG.
5820 /// This version can replace From with any result values. To must match the
5821 /// number and types of values returned by From.
5822 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5823 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5824 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5826 // Iterate over just the existing users of From. See the comments in
5827 // the ReplaceAllUsesWith above.
5828 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5829 RAUWUpdateListener Listener(*this, UI, UE);
5833 // This node is about to morph, remove its old self from the CSE maps.
5834 RemoveNodeFromCSEMaps(User);
5836 // A user can appear in a use list multiple times, and when this
5837 // happens the uses are usually next to each other in the list.
5838 // To help reduce the number of CSE recomputations, process all
5839 // the uses of this user that we can find this way.
5841 SDUse &Use = UI.getUse();
5842 const SDValue &ToOp = To[Use.getResNo()];
5845 } while (UI != UE && *UI == User);
5847 // Now that we have modified User, add it back to the CSE maps. If it
5848 // already exists there, recursively merge the results together.
5849 AddModifiedNodeToCSEMaps(User);
5852 // If we just RAUW'd the root, take note.
5853 if (From == getRoot().getNode())
5854 setRoot(SDValue(To[getRoot().getResNo()]));
5857 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5858 /// uses of other values produced by From.getNode() alone. The Deleted
5859 /// vector is handled the same way as for ReplaceAllUsesWith.
5860 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5861 // Handle the really simple, really trivial case efficiently.
5862 if (From == To) return;
5864 // Handle the simple, trivial, case efficiently.
5865 if (From.getNode()->getNumValues() == 1) {
5866 ReplaceAllUsesWith(From, To);
5870 // Iterate over just the existing users of From. See the comments in
5871 // the ReplaceAllUsesWith above.
5872 SDNode::use_iterator UI = From.getNode()->use_begin(),
5873 UE = From.getNode()->use_end();
5874 RAUWUpdateListener Listener(*this, UI, UE);
5877 bool UserRemovedFromCSEMaps = false;
5879 // A user can appear in a use list multiple times, and when this
5880 // happens the uses are usually next to each other in the list.
5881 // To help reduce the number of CSE recomputations, process all
5882 // the uses of this user that we can find this way.
5884 SDUse &Use = UI.getUse();
5886 // Skip uses of different values from the same node.
5887 if (Use.getResNo() != From.getResNo()) {
5892 // If this node hasn't been modified yet, it's still in the CSE maps,
5893 // so remove its old self from the CSE maps.
5894 if (!UserRemovedFromCSEMaps) {
5895 RemoveNodeFromCSEMaps(User);
5896 UserRemovedFromCSEMaps = true;
5901 } while (UI != UE && *UI == User);
5903 // We are iterating over all uses of the From node, so if a use
5904 // doesn't use the specific value, no changes are made.
5905 if (!UserRemovedFromCSEMaps)
5908 // Now that we have modified User, add it back to the CSE maps. If it
5909 // already exists there, recursively merge the results together.
5910 AddModifiedNodeToCSEMaps(User);
5913 // If we just RAUW'd the root, take note.
5914 if (From == getRoot())
5919 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5920 /// to record information about a use.
5927 /// operator< - Sort Memos by User.
5928 bool operator<(const UseMemo &L, const UseMemo &R) {
5929 return (intptr_t)L.User < (intptr_t)R.User;
5933 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5934 /// uses of other values produced by From.getNode() alone. The same value
5935 /// may appear in both the From and To list. The Deleted vector is
5936 /// handled the same way as for ReplaceAllUsesWith.
5937 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5940 // Handle the simple, trivial case efficiently.
5942 return ReplaceAllUsesOfValueWith(*From, *To);
5944 // Read up all the uses and make records of them. This helps
5945 // processing new uses that are introduced during the
5946 // replacement process.
5947 SmallVector<UseMemo, 4> Uses;
5948 for (unsigned i = 0; i != Num; ++i) {
5949 unsigned FromResNo = From[i].getResNo();
5950 SDNode *FromNode = From[i].getNode();
5951 for (SDNode::use_iterator UI = FromNode->use_begin(),
5952 E = FromNode->use_end(); UI != E; ++UI) {
5953 SDUse &Use = UI.getUse();
5954 if (Use.getResNo() == FromResNo) {
5955 UseMemo Memo = { *UI, i, &Use };
5956 Uses.push_back(Memo);
5961 // Sort the uses, so that all the uses from a given User are together.
5962 std::sort(Uses.begin(), Uses.end());
5964 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5965 UseIndex != UseIndexEnd; ) {
5966 // We know that this user uses some value of From. If it is the right
5967 // value, update it.
5968 SDNode *User = Uses[UseIndex].User;
5970 // This node is about to morph, remove its old self from the CSE maps.
5971 RemoveNodeFromCSEMaps(User);
5973 // The Uses array is sorted, so all the uses for a given User
5974 // are next to each other in the list.
5975 // To help reduce the number of CSE recomputations, process all
5976 // the uses of this user that we can find this way.
5978 unsigned i = Uses[UseIndex].Index;
5979 SDUse &Use = *Uses[UseIndex].Use;
5983 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5985 // Now that we have modified User, add it back to the CSE maps. If it
5986 // already exists there, recursively merge the results together.
5987 AddModifiedNodeToCSEMaps(User);
5991 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5992 /// based on their topological order. It returns the maximum id and a vector
5993 /// of the SDNodes* in assigned order by reference.
5994 unsigned SelectionDAG::AssignTopologicalOrder() {
5996 unsigned DAGSize = 0;
5998 // SortedPos tracks the progress of the algorithm. Nodes before it are
5999 // sorted, nodes after it are unsorted. When the algorithm completes
6000 // it is at the end of the list.
6001 allnodes_iterator SortedPos = allnodes_begin();
6003 // Visit all the nodes. Move nodes with no operands to the front of
6004 // the list immediately. Annotate nodes that do have operands with their
6005 // operand count. Before we do this, the Node Id fields of the nodes
6006 // may contain arbitrary values. After, the Node Id fields for nodes
6007 // before SortedPos will contain the topological sort index, and the
6008 // Node Id fields for nodes At SortedPos and after will contain the
6009 // count of outstanding operands.
6010 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6012 checkForCycles(N, this);
6013 unsigned Degree = N->getNumOperands();
6015 // A node with no uses, add it to the result array immediately.
6016 N->setNodeId(DAGSize++);
6017 allnodes_iterator Q = N;
6019 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6020 assert(SortedPos != AllNodes.end() && "Overran node list");
6023 // Temporarily use the Node Id as scratch space for the degree count.
6024 N->setNodeId(Degree);
6028 // Visit all the nodes. As we iterate, move nodes into sorted order,
6029 // such that by the time the end is reached all nodes will be sorted.
6030 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6032 checkForCycles(N, this);
6033 // N is in sorted position, so all its uses have one less operand
6034 // that needs to be sorted.
6035 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6038 unsigned Degree = P->getNodeId();
6039 assert(Degree != 0 && "Invalid node degree");
6042 // All of P's operands are sorted, so P may sorted now.
6043 P->setNodeId(DAGSize++);
6045 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6046 assert(SortedPos != AllNodes.end() && "Overran node list");
6049 // Update P's outstanding operand count.
6050 P->setNodeId(Degree);
6053 if (I == SortedPos) {
6056 dbgs() << "Overran sorted position:\n";
6057 S->dumprFull(this); dbgs() << "\n";
6058 dbgs() << "Checking if this is due to cycles\n";
6059 checkForCycles(this, true);
6061 llvm_unreachable(nullptr);
6065 assert(SortedPos == AllNodes.end() &&
6066 "Topological sort incomplete!");
6067 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6068 "First node in topological sort is not the entry token!");
6069 assert(AllNodes.front().getNodeId() == 0 &&
6070 "First node in topological sort has non-zero id!");
6071 assert(AllNodes.front().getNumOperands() == 0 &&
6072 "First node in topological sort has operands!");
6073 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6074 "Last node in topologic sort has unexpected id!");
6075 assert(AllNodes.back().use_empty() &&
6076 "Last node in topologic sort has users!");
6077 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6081 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6082 /// value is produced by SD.
6083 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6084 DbgInfo->add(DB, SD, isParameter);
6086 SD->setHasDebugValue(true);
6089 /// TransferDbgValues - Transfer SDDbgValues.
6090 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6091 if (From == To || !From.getNode()->getHasDebugValue())
6093 SDNode *FromNode = From.getNode();
6094 SDNode *ToNode = To.getNode();
6095 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6096 SmallVector<SDDbgValue *, 2> ClonedDVs;
6097 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6099 SDDbgValue *Dbg = *I;
6100 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6101 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6103 Dbg->getOffset(), Dbg->getDebugLoc(),
6105 ClonedDVs.push_back(Clone);
6108 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6109 E = ClonedDVs.end(); I != E; ++I)
6110 AddDbgValue(*I, ToNode, false);
6113 //===----------------------------------------------------------------------===//
6115 //===----------------------------------------------------------------------===//
6117 HandleSDNode::~HandleSDNode() {
6121 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6122 DebugLoc DL, const GlobalValue *GA,
6123 EVT VT, int64_t o, unsigned char TF)
6124 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6128 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6129 SDValue X, unsigned SrcAS,
6131 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6132 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6134 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6135 EVT memvt, MachineMemOperand *mmo)
6136 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6137 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6138 MMO->isNonTemporal(), MMO->isInvariant());
6139 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6140 assert(isNonTemporal() == MMO->isNonTemporal() &&
6141 "Non-temporal encoding error!");
6142 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6145 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6146 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6147 : SDNode(Opc, Order, dl, VTs, Ops),
6148 MemoryVT(memvt), MMO(mmo) {
6149 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6150 MMO->isNonTemporal(), MMO->isInvariant());
6151 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6152 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6155 /// Profile - Gather unique data for the node.
6157 void SDNode::Profile(FoldingSetNodeID &ID) const {
6158 AddNodeIDNode(ID, this);
6163 std::vector<EVT> VTs;
6166 VTs.reserve(MVT::LAST_VALUETYPE);
6167 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6168 VTs.push_back(MVT((MVT::SimpleValueType)i));
6173 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6174 static ManagedStatic<EVTArray> SimpleVTArray;
6175 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6177 /// getValueTypeList - Return a pointer to the specified value type.
6179 const EVT *SDNode::getValueTypeList(EVT VT) {
6180 if (VT.isExtended()) {
6181 sys::SmartScopedLock<true> Lock(*VTMutex);
6182 return &(*EVTs->insert(VT).first);
6184 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6185 "Value type out of range!");
6186 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6190 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6191 /// indicated value. This method ignores uses of other values defined by this
6193 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6194 assert(Value < getNumValues() && "Bad value!");
6196 // TODO: Only iterate over uses of a given value of the node
6197 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6198 if (UI.getUse().getResNo() == Value) {
6205 // Found exactly the right number of uses?
6210 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6211 /// value. This method ignores uses of other values defined by this operation.
6212 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6213 assert(Value < getNumValues() && "Bad value!");
6215 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6216 if (UI.getUse().getResNo() == Value)
6223 /// isOnlyUserOf - Return true if this node is the only use of N.
6225 bool SDNode::isOnlyUserOf(SDNode *N) const {
6227 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6238 /// isOperand - Return true if this node is an operand of N.
6240 bool SDValue::isOperandOf(SDNode *N) const {
6241 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6242 if (*this == N->getOperand(i))
6247 bool SDNode::isOperandOf(SDNode *N) const {
6248 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6249 if (this == N->OperandList[i].getNode())
6254 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6255 /// be a chain) reaches the specified operand without crossing any
6256 /// side-effecting instructions on any chain path. In practice, this looks
6257 /// through token factors and non-volatile loads. In order to remain efficient,
6258 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6259 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6260 unsigned Depth) const {
6261 if (*this == Dest) return true;
6263 // Don't search too deeply, we just want to be able to see through
6264 // TokenFactor's etc.
6265 if (Depth == 0) return false;
6267 // If this is a token factor, all inputs to the TF happen in parallel. If any
6268 // of the operands of the TF does not reach dest, then we cannot do the xform.
6269 if (getOpcode() == ISD::TokenFactor) {
6270 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6271 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6276 // Loads don't have side effects, look through them.
6277 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6278 if (!Ld->isVolatile())
6279 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6284 /// hasPredecessor - Return true if N is a predecessor of this node.
6285 /// N is either an operand of this node, or can be reached by recursively
6286 /// traversing up the operands.
6287 /// NOTE: This is an expensive method. Use it carefully.
6288 bool SDNode::hasPredecessor(const SDNode *N) const {
6289 SmallPtrSet<const SDNode *, 32> Visited;
6290 SmallVector<const SDNode *, 16> Worklist;
6291 return hasPredecessorHelper(N, Visited, Worklist);
6295 SDNode::hasPredecessorHelper(const SDNode *N,
6296 SmallPtrSet<const SDNode *, 32> &Visited,
6297 SmallVectorImpl<const SDNode *> &Worklist) const {
6298 if (Visited.empty()) {
6299 Worklist.push_back(this);
6301 // Take a look in the visited set. If we've already encountered this node
6302 // we needn't search further.
6303 if (Visited.count(N))
6307 // Haven't visited N yet. Continue the search.
6308 while (!Worklist.empty()) {
6309 const SDNode *M = Worklist.pop_back_val();
6310 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6311 SDNode *Op = M->getOperand(i).getNode();
6312 if (Visited.insert(Op))
6313 Worklist.push_back(Op);
6322 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6323 assert(Num < NumOperands && "Invalid child # of SDNode!");
6324 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6327 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6328 assert(N->getNumValues() == 1 &&
6329 "Can't unroll a vector with multiple results!");
6331 EVT VT = N->getValueType(0);
6332 unsigned NE = VT.getVectorNumElements();
6333 EVT EltVT = VT.getVectorElementType();
6336 SmallVector<SDValue, 8> Scalars;
6337 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6339 // If ResNE is 0, fully unroll the vector op.
6342 else if (NE > ResNE)
6346 for (i= 0; i != NE; ++i) {
6347 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6348 SDValue Operand = N->getOperand(j);
6349 EVT OperandVT = Operand.getValueType();
6350 if (OperandVT.isVector()) {
6351 // A vector operand; extract a single element.
6352 const TargetLowering *TLI = TM.getTargetLowering();
6353 EVT OperandEltVT = OperandVT.getVectorElementType();
6354 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6357 getConstant(i, TLI->getVectorIdxTy()));
6359 // A scalar operand; just use it as is.
6360 Operands[j] = Operand;
6364 switch (N->getOpcode()) {
6366 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6369 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6376 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6377 getShiftAmountOperand(Operands[0].getValueType(),
6380 case ISD::SIGN_EXTEND_INREG:
6381 case ISD::FP_ROUND_INREG: {
6382 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6383 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6385 getValueType(ExtVT)));
6390 for (; i < ResNE; ++i)
6391 Scalars.push_back(getUNDEF(EltVT));
6393 return getNode(ISD::BUILD_VECTOR, dl,
6394 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6398 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6399 /// location that is 'Dist' units away from the location that the 'Base' load
6400 /// is loading from.
6401 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6402 unsigned Bytes, int Dist) const {
6403 if (LD->getChain() != Base->getChain())
6405 EVT VT = LD->getValueType(0);
6406 if (VT.getSizeInBits() / 8 != Bytes)
6409 SDValue Loc = LD->getOperand(1);
6410 SDValue BaseLoc = Base->getOperand(1);
6411 if (Loc.getOpcode() == ISD::FrameIndex) {
6412 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6414 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6415 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6416 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6417 int FS = MFI->getObjectSize(FI);
6418 int BFS = MFI->getObjectSize(BFI);
6419 if (FS != BFS || FS != (int)Bytes) return false;
6420 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6424 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6425 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6428 const GlobalValue *GV1 = nullptr;
6429 const GlobalValue *GV2 = nullptr;
6430 int64_t Offset1 = 0;
6431 int64_t Offset2 = 0;
6432 const TargetLowering *TLI = TM.getTargetLowering();
6433 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6434 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6435 if (isGA1 && isGA2 && GV1 == GV2)
6436 return Offset1 == (Offset2 + Dist*Bytes);
6441 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6442 /// it cannot be inferred.
6443 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6444 // If this is a GlobalAddress + cst, return the alignment.
6445 const GlobalValue *GV;
6446 int64_t GVOffset = 0;
6447 const TargetLowering *TLI = TM.getTargetLowering();
6448 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6449 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6450 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6451 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6452 TLI->getDataLayout());
6453 unsigned AlignBits = KnownZero.countTrailingOnes();
6454 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6456 return MinAlign(Align, GVOffset);
6459 // If this is a direct reference to a stack slot, use information about the
6460 // stack slot's alignment.
6461 int FrameIdx = 1 << 31;
6462 int64_t FrameOffset = 0;
6463 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6464 FrameIdx = FI->getIndex();
6465 } else if (isBaseWithConstantOffset(Ptr) &&
6466 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6468 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6469 FrameOffset = Ptr.getConstantOperandVal(1);
6472 if (FrameIdx != (1 << 31)) {
6473 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6474 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6482 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6483 /// which is split (or expanded) into two not necessarily identical pieces.
6484 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6485 // Currently all types are split in half.
6487 if (!VT.isVector()) {
6488 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6490 unsigned NumElements = VT.getVectorNumElements();
6491 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6492 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6495 return std::make_pair(LoVT, HiVT);
6498 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6500 std::pair<SDValue, SDValue>
6501 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6503 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6504 N.getValueType().getVectorNumElements() &&
6505 "More vector elements requested than available!");
6507 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6508 getConstant(0, TLI->getVectorIdxTy()));
6509 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6510 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6511 return std::make_pair(Lo, Hi);
6514 void SelectionDAG::ExtractVectorElements(SDValue Op,
6515 SmallVectorImpl<SDValue> &Args,
6516 unsigned Start, unsigned Count) {
6517 EVT VT = Op.getValueType();
6519 Count = VT.getVectorNumElements();
6521 EVT EltVT = VT.getVectorElementType();
6522 EVT IdxTy = TLI->getVectorIdxTy();
6524 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6525 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6526 Op, getConstant(i, IdxTy)));
6530 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6531 unsigned GlobalAddressSDNode::getAddressSpace() const {
6532 return getGlobal()->getType()->getAddressSpace();
6536 Type *ConstantPoolSDNode::getType() const {
6537 if (isMachineConstantPoolEntry())
6538 return Val.MachineCPVal->getType();
6539 return Val.ConstVal->getType();
6542 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6544 unsigned &SplatBitSize,
6546 unsigned MinSplatBits,
6547 bool isBigEndian) const {
6548 EVT VT = getValueType(0);
6549 assert(VT.isVector() && "Expected a vector type");
6550 unsigned sz = VT.getSizeInBits();
6551 if (MinSplatBits > sz)
6554 SplatValue = APInt(sz, 0);
6555 SplatUndef = APInt(sz, 0);
6557 // Get the bits. Bits with undefined values (when the corresponding element
6558 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6559 // in SplatValue. If any of the values are not constant, give up and return
6561 unsigned int nOps = getNumOperands();
6562 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6563 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6565 for (unsigned j = 0; j < nOps; ++j) {
6566 unsigned i = isBigEndian ? nOps-1-j : j;
6567 SDValue OpVal = getOperand(i);
6568 unsigned BitPos = j * EltBitSize;
6570 if (OpVal.getOpcode() == ISD::UNDEF)
6571 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6572 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6573 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6574 zextOrTrunc(sz) << BitPos;
6575 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6576 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6581 // The build_vector is all constants or undefs. Find the smallest element
6582 // size that splats the vector.
6584 HasAnyUndefs = (SplatUndef != 0);
6587 unsigned HalfSize = sz / 2;
6588 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6589 APInt LowValue = SplatValue.trunc(HalfSize);
6590 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6591 APInt LowUndef = SplatUndef.trunc(HalfSize);
6593 // If the two halves do not match (ignoring undef bits), stop here.
6594 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6595 MinSplatBits > HalfSize)
6598 SplatValue = HighValue | LowValue;
6599 SplatUndef = HighUndef & LowUndef;
6608 SDValue BuildVectorSDNode::getSplatValue(bool &HasUndefElements) const {
6609 HasUndefElements = false;
6611 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6612 SDValue Op = getOperand(i);
6613 if (Op.getOpcode() == ISD::UNDEF)
6614 HasUndefElements = true;
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);
6631 BuildVectorSDNode::getConstantSplatNode(bool &HasUndefElements) const {
6632 return dyn_cast_or_null<ConstantSDNode>(
6633 getSplatValue(HasUndefElements).getNode());
6637 BuildVectorSDNode::getConstantFPSplatNode(bool &HasUndefElements) const {
6638 return dyn_cast_or_null<ConstantFPSDNode>(
6639 getSplatValue(HasUndefElements).getNode());
6642 bool BuildVectorSDNode::isConstant() const {
6643 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6644 unsigned Opc = getOperand(i).getOpcode();
6645 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6651 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6652 // Find the first non-undef value in the shuffle mask.
6654 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6657 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6659 // Make sure all remaining elements are either undef or the same as the first
6661 for (int Idx = Mask[i]; i != e; ++i)
6662 if (Mask[i] >= 0 && Mask[i] != Idx)
6668 static void checkForCyclesHelper(const SDNode *N,
6669 SmallPtrSet<const SDNode*, 32> &Visited,
6670 SmallPtrSet<const SDNode*, 32> &Checked,
6671 const llvm::SelectionDAG *DAG) {
6672 // If this node has already been checked, don't check it again.
6673 if (Checked.count(N))
6676 // If a node has already been visited on this depth-first walk, reject it as
6678 if (!Visited.insert(N)) {
6679 errs() << "Detected cycle in SelectionDAG\n";
6680 dbgs() << "Offending node:\n";
6681 N->dumprFull(DAG); dbgs() << "\n";
6685 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6686 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6693 void llvm::checkForCycles(const llvm::SDNode *N,
6694 const llvm::SelectionDAG *DAG,
6702 assert(N && "Checking nonexistent SDNode");
6703 SmallPtrSet<const SDNode*, 32> visited;
6704 SmallPtrSet<const SDNode*, 32> checked;
6705 checkForCyclesHelper(N, visited, checked, DAG);
6710 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6711 checkForCycles(DAG->getRoot().getNode(), DAG, force);