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,
1017 if (VT.bitsLE(Op.getValueType()))
1018 return getNode(ISD::TRUNCATE, SL, VT, Op);
1020 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1021 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1024 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1025 assert(!VT.isVector() &&
1026 "getZeroExtendInReg should use the vector element type instead of "
1027 "the vector type!");
1028 if (Op.getValueType() == VT) return Op;
1029 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1030 APInt Imm = APInt::getLowBitsSet(BitWidth,
1031 VT.getSizeInBits());
1032 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1033 getConstant(Imm, Op.getValueType()));
1036 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1037 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1038 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1039 "The sizes of the input and result must match in order to perform the "
1040 "extend in-register.");
1041 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1042 "The destination vector type must have fewer lanes than the input.");
1043 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1046 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1047 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1048 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1049 "The sizes of the input and result must match in order to perform the "
1050 "extend in-register.");
1051 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1052 "The destination vector type must have fewer lanes than the input.");
1053 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1056 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1057 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1058 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1059 "The sizes of the input and result must match in order to perform the "
1060 "extend in-register.");
1061 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1062 "The destination vector type must have fewer lanes than the input.");
1063 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1066 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1068 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1069 EVT EltVT = VT.getScalarType();
1071 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
1072 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1075 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1076 EVT EltVT = VT.getScalarType();
1078 switch (TLI->getBooleanContents(VT)) {
1079 case TargetLowering::ZeroOrOneBooleanContent:
1080 case TargetLowering::UndefinedBooleanContent:
1081 TrueValue = getConstant(1, VT);
1083 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1084 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1088 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1091 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1092 EVT EltVT = VT.getScalarType();
1093 assert((EltVT.getSizeInBits() >= 64 ||
1094 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1095 "getConstant with a uint64_t value that doesn't fit in the type!");
1096 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1099 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1101 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1104 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1106 assert(VT.isInteger() && "Cannot create FP integer constant!");
1108 EVT EltVT = VT.getScalarType();
1109 const ConstantInt *Elt = &Val;
1111 const TargetLowering *TLI = TM.getTargetLowering();
1113 // In some cases the vector type is legal but the element type is illegal and
1114 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1115 // inserted value (the type does not need to match the vector element type).
1116 // Any extra bits introduced will be truncated away.
1117 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1118 TargetLowering::TypePromoteInteger) {
1119 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1120 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1121 Elt = ConstantInt::get(*getContext(), NewVal);
1123 // In other cases the element type is illegal and needs to be expanded, for
1124 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1125 // the value into n parts and use a vector type with n-times the elements.
1126 // Then bitcast to the type requested.
1127 // Legalizing constants too early makes the DAGCombiner's job harder so we
1128 // only legalize if the DAG tells us we must produce legal types.
1129 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1130 TLI->getTypeAction(*getContext(), EltVT) ==
1131 TargetLowering::TypeExpandInteger) {
1132 APInt NewVal = Elt->getValue();
1133 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1134 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1135 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1136 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1138 // Check the temporary vector is the correct size. If this fails then
1139 // getTypeToTransformTo() probably returned a type whose size (in bits)
1140 // isn't a power-of-2 factor of the requested type size.
1141 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1143 SmallVector<SDValue, 2> EltParts;
1144 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1145 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1146 .trunc(ViaEltSizeInBits),
1147 ViaEltVT, isT, isO));
1150 // EltParts is currently in little endian order. If we actually want
1151 // big-endian order then reverse it now.
1152 if (TLI->isBigEndian())
1153 std::reverse(EltParts.begin(), EltParts.end());
1155 // The elements must be reversed when the element order is different
1156 // to the endianness of the elements (because the BITCAST is itself a
1157 // vector shuffle in this situation). However, we do not need any code to
1158 // perform this reversal because getConstant() is producing a vector
1160 // This situation occurs in MIPS MSA.
1162 SmallVector<SDValue, 8> Ops;
1163 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1164 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1166 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1167 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1172 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1173 "APInt size does not match type size!");
1174 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1175 FoldingSetNodeID ID;
1176 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1180 SDNode *N = nullptr;
1181 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1183 return SDValue(N, 0);
1186 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1187 CSEMap.InsertNode(N, IP);
1188 AllNodes.push_back(N);
1191 SDValue Result(N, 0);
1192 if (VT.isVector()) {
1193 SmallVector<SDValue, 8> Ops;
1194 Ops.assign(VT.getVectorNumElements(), Result);
1195 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1200 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1201 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1205 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1206 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1209 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1210 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1212 EVT EltVT = VT.getScalarType();
1214 // Do the map lookup using the actual bit pattern for the floating point
1215 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1216 // we don't have issues with SNANs.
1217 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1218 FoldingSetNodeID ID;
1219 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1222 SDNode *N = nullptr;
1223 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1225 return SDValue(N, 0);
1228 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1229 CSEMap.InsertNode(N, IP);
1230 AllNodes.push_back(N);
1233 SDValue Result(N, 0);
1234 if (VT.isVector()) {
1235 SmallVector<SDValue, 8> Ops;
1236 Ops.assign(VT.getVectorNumElements(), Result);
1237 // FIXME SDLoc info might be appropriate here
1238 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1243 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1244 EVT EltVT = VT.getScalarType();
1245 if (EltVT==MVT::f32)
1246 return getConstantFP(APFloat((float)Val), VT, isTarget);
1247 else if (EltVT==MVT::f64)
1248 return getConstantFP(APFloat(Val), VT, isTarget);
1249 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1252 APFloat apf = APFloat(Val);
1253 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1255 return getConstantFP(apf, VT, isTarget);
1257 llvm_unreachable("Unsupported type in getConstantFP");
1260 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1261 EVT VT, int64_t Offset,
1263 unsigned char TargetFlags) {
1264 assert((TargetFlags == 0 || isTargetGA) &&
1265 "Cannot set target flags on target-independent globals");
1266 const TargetLowering *TLI = TM.getTargetLowering();
1268 // Truncate (with sign-extension) the offset value to the pointer size.
1269 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1271 Offset = SignExtend64(Offset, BitWidth);
1274 if (GV->isThreadLocal())
1275 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1277 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1279 FoldingSetNodeID ID;
1280 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1282 ID.AddInteger(Offset);
1283 ID.AddInteger(TargetFlags);
1284 ID.AddInteger(GV->getType()->getAddressSpace());
1286 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1287 return SDValue(E, 0);
1289 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1290 DL.getDebugLoc(), GV, VT,
1291 Offset, TargetFlags);
1292 CSEMap.InsertNode(N, IP);
1293 AllNodes.push_back(N);
1294 return SDValue(N, 0);
1297 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1298 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1299 FoldingSetNodeID ID;
1300 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1304 return SDValue(E, 0);
1306 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1307 CSEMap.InsertNode(N, IP);
1308 AllNodes.push_back(N);
1309 return SDValue(N, 0);
1312 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1313 unsigned char TargetFlags) {
1314 assert((TargetFlags == 0 || isTarget) &&
1315 "Cannot set target flags on target-independent jump tables");
1316 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1317 FoldingSetNodeID ID;
1318 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1320 ID.AddInteger(TargetFlags);
1322 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1327 CSEMap.InsertNode(N, IP);
1328 AllNodes.push_back(N);
1329 return SDValue(N, 0);
1332 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1333 unsigned Alignment, int Offset,
1335 unsigned char TargetFlags) {
1336 assert((TargetFlags == 0 || isTarget) &&
1337 "Cannot set target flags on target-independent globals");
1340 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1341 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1342 FoldingSetNodeID ID;
1343 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1344 ID.AddInteger(Alignment);
1345 ID.AddInteger(Offset);
1347 ID.AddInteger(TargetFlags);
1349 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1350 return SDValue(E, 0);
1352 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1353 Alignment, TargetFlags);
1354 CSEMap.InsertNode(N, IP);
1355 AllNodes.push_back(N);
1356 return SDValue(N, 0);
1360 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1361 unsigned Alignment, int Offset,
1363 unsigned char TargetFlags) {
1364 assert((TargetFlags == 0 || isTarget) &&
1365 "Cannot set target flags on target-independent globals");
1368 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1369 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1370 FoldingSetNodeID ID;
1371 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1372 ID.AddInteger(Alignment);
1373 ID.AddInteger(Offset);
1374 C->addSelectionDAGCSEId(ID);
1375 ID.AddInteger(TargetFlags);
1377 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1378 return SDValue(E, 0);
1380 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1381 Alignment, TargetFlags);
1382 CSEMap.InsertNode(N, IP);
1383 AllNodes.push_back(N);
1384 return SDValue(N, 0);
1387 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1388 unsigned char TargetFlags) {
1389 FoldingSetNodeID ID;
1390 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1391 ID.AddInteger(Index);
1392 ID.AddInteger(Offset);
1393 ID.AddInteger(TargetFlags);
1395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1396 return SDValue(E, 0);
1398 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1400 CSEMap.InsertNode(N, IP);
1401 AllNodes.push_back(N);
1402 return SDValue(N, 0);
1405 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1406 FoldingSetNodeID ID;
1407 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1410 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1411 return SDValue(E, 0);
1413 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1414 CSEMap.InsertNode(N, IP);
1415 AllNodes.push_back(N);
1416 return SDValue(N, 0);
1419 SDValue SelectionDAG::getValueType(EVT VT) {
1420 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1421 ValueTypeNodes.size())
1422 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1424 SDNode *&N = VT.isExtended() ?
1425 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1427 if (N) return SDValue(N, 0);
1428 N = new (NodeAllocator) VTSDNode(VT);
1429 AllNodes.push_back(N);
1430 return SDValue(N, 0);
1433 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1434 SDNode *&N = ExternalSymbols[Sym];
1435 if (N) return SDValue(N, 0);
1436 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1437 AllNodes.push_back(N);
1438 return SDValue(N, 0);
1441 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1442 unsigned char TargetFlags) {
1444 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1446 if (N) return SDValue(N, 0);
1447 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1448 AllNodes.push_back(N);
1449 return SDValue(N, 0);
1452 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1453 if ((unsigned)Cond >= CondCodeNodes.size())
1454 CondCodeNodes.resize(Cond+1);
1456 if (!CondCodeNodes[Cond]) {
1457 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1458 CondCodeNodes[Cond] = N;
1459 AllNodes.push_back(N);
1462 return SDValue(CondCodeNodes[Cond], 0);
1465 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1466 // the shuffle mask M that point at N1 to point at N2, and indices that point
1467 // N2 to point at N1.
1468 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1470 int NElts = M.size();
1471 for (int i = 0; i != NElts; ++i) {
1479 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1480 SDValue N2, const int *Mask) {
1481 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1482 "Invalid VECTOR_SHUFFLE");
1484 // Canonicalize shuffle undef, undef -> undef
1485 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1486 return getUNDEF(VT);
1488 // Validate that all indices in Mask are within the range of the elements
1489 // input to the shuffle.
1490 unsigned NElts = VT.getVectorNumElements();
1491 SmallVector<int, 8> MaskVec;
1492 for (unsigned i = 0; i != NElts; ++i) {
1493 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1494 MaskVec.push_back(Mask[i]);
1497 // Canonicalize shuffle v, v -> v, undef
1500 for (unsigned i = 0; i != NElts; ++i)
1501 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1504 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1505 if (N1.getOpcode() == ISD::UNDEF)
1506 commuteShuffle(N1, N2, MaskVec);
1508 // Canonicalize all index into lhs, -> shuffle lhs, undef
1509 // Canonicalize all index into rhs, -> shuffle rhs, undef
1510 bool AllLHS = true, AllRHS = true;
1511 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1512 for (unsigned i = 0; i != NElts; ++i) {
1513 if (MaskVec[i] >= (int)NElts) {
1518 } else if (MaskVec[i] >= 0) {
1522 if (AllLHS && AllRHS)
1523 return getUNDEF(VT);
1524 if (AllLHS && !N2Undef)
1528 commuteShuffle(N1, N2, MaskVec);
1530 // Reset our undef status after accounting for the mask.
1531 N2Undef = N2.getOpcode() == ISD::UNDEF;
1532 // Re-check whether both sides ended up undef.
1533 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1534 return getUNDEF(VT);
1536 // If Identity shuffle return that node.
1537 bool Identity = true;
1538 for (unsigned i = 0; i != NElts; ++i) {
1539 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1541 if (Identity && NElts)
1544 // Shuffling a constant splat doesn't change the result.
1548 // Look through any bitcasts. We check that these don't change the number
1549 // (and size) of elements and just changes their types.
1550 while (V.getOpcode() == ISD::BITCAST)
1551 V = V->getOperand(0);
1553 // A splat should always show up as a build vector node.
1554 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1555 BitVector UndefElements;
1556 SDValue Splat = BV->getSplatValue(&UndefElements);
1557 // If this is a splat of an undef, shuffling it is also undef.
1558 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1559 return getUNDEF(VT);
1561 // We only have a splat which can skip shuffles if there is a splatted
1562 // value and no undef lanes rearranged by the shuffle.
1563 if (Splat && UndefElements.none()) {
1564 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1565 // number of elements match or the value splatted is a zero constant.
1566 if (V.getValueType().getVectorNumElements() ==
1567 VT.getVectorNumElements())
1569 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1570 if (C->isNullValue())
1576 FoldingSetNodeID ID;
1577 SDValue Ops[2] = { N1, N2 };
1578 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1579 for (unsigned i = 0; i != NElts; ++i)
1580 ID.AddInteger(MaskVec[i]);
1583 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1584 return SDValue(E, 0);
1586 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1587 // SDNode doesn't have access to it. This memory will be "leaked" when
1588 // the node is deallocated, but recovered when the NodeAllocator is released.
1589 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1590 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1592 ShuffleVectorSDNode *N =
1593 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1594 dl.getDebugLoc(), N1, N2,
1596 CSEMap.InsertNode(N, IP);
1597 AllNodes.push_back(N);
1598 return SDValue(N, 0);
1601 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1602 MVT VT = SV.getSimpleValueType(0);
1603 unsigned NumElems = VT.getVectorNumElements();
1604 SmallVector<int, 8> MaskVec;
1606 for (unsigned i = 0; i != NumElems; ++i) {
1607 int Idx = SV.getMaskElt(i);
1609 if (Idx < (int)NumElems)
1614 MaskVec.push_back(Idx);
1617 SDValue Op0 = SV.getOperand(0);
1618 SDValue Op1 = SV.getOperand(1);
1619 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1622 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1623 SDValue Val, SDValue DTy,
1624 SDValue STy, SDValue Rnd, SDValue Sat,
1625 ISD::CvtCode Code) {
1626 // If the src and dest types are the same and the conversion is between
1627 // integer types of the same sign or two floats, no conversion is necessary.
1629 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1632 FoldingSetNodeID ID;
1633 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1634 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1636 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1637 return SDValue(E, 0);
1639 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1642 CSEMap.InsertNode(N, IP);
1643 AllNodes.push_back(N);
1644 return SDValue(N, 0);
1647 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1648 FoldingSetNodeID ID;
1649 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1650 ID.AddInteger(RegNo);
1652 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1653 return SDValue(E, 0);
1655 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1656 CSEMap.InsertNode(N, IP);
1657 AllNodes.push_back(N);
1658 return SDValue(N, 0);
1661 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1662 FoldingSetNodeID ID;
1663 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1664 ID.AddPointer(RegMask);
1666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1667 return SDValue(E, 0);
1669 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1670 CSEMap.InsertNode(N, IP);
1671 AllNodes.push_back(N);
1672 return SDValue(N, 0);
1675 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1676 FoldingSetNodeID ID;
1677 SDValue Ops[] = { Root };
1678 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1679 ID.AddPointer(Label);
1681 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1682 return SDValue(E, 0);
1684 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1685 dl.getDebugLoc(), Root, Label);
1686 CSEMap.InsertNode(N, IP);
1687 AllNodes.push_back(N);
1688 return SDValue(N, 0);
1692 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1695 unsigned char TargetFlags) {
1696 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1698 FoldingSetNodeID ID;
1699 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1701 ID.AddInteger(Offset);
1702 ID.AddInteger(TargetFlags);
1704 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1705 return SDValue(E, 0);
1707 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1709 CSEMap.InsertNode(N, IP);
1710 AllNodes.push_back(N);
1711 return SDValue(N, 0);
1714 SDValue SelectionDAG::getSrcValue(const Value *V) {
1715 assert((!V || V->getType()->isPointerTy()) &&
1716 "SrcValue is not a pointer?");
1718 FoldingSetNodeID ID;
1719 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1723 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1724 return SDValue(E, 0);
1726 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1727 CSEMap.InsertNode(N, IP);
1728 AllNodes.push_back(N);
1729 return SDValue(N, 0);
1732 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1733 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1734 FoldingSetNodeID ID;
1735 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1739 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1740 return SDValue(E, 0);
1742 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1743 CSEMap.InsertNode(N, IP);
1744 AllNodes.push_back(N);
1745 return SDValue(N, 0);
1748 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1749 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1750 unsigned SrcAS, unsigned DestAS) {
1751 SDValue Ops[] = {Ptr};
1752 FoldingSetNodeID ID;
1753 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1754 ID.AddInteger(SrcAS);
1755 ID.AddInteger(DestAS);
1758 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1759 return SDValue(E, 0);
1761 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1763 VT, Ptr, SrcAS, DestAS);
1764 CSEMap.InsertNode(N, IP);
1765 AllNodes.push_back(N);
1766 return SDValue(N, 0);
1769 /// getShiftAmountOperand - Return the specified value casted to
1770 /// the target's desired shift amount type.
1771 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1772 EVT OpTy = Op.getValueType();
1773 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1774 if (OpTy == ShTy || OpTy.isVector()) return Op;
1776 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1777 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1780 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1781 /// specified value type.
1782 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1783 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1784 unsigned ByteSize = VT.getStoreSize();
1785 Type *Ty = VT.getTypeForEVT(*getContext());
1786 const TargetLowering *TLI = TM.getTargetLowering();
1787 unsigned StackAlign =
1788 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1790 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1791 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1794 /// CreateStackTemporary - Create a stack temporary suitable for holding
1795 /// either of the specified value types.
1796 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1797 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1798 VT2.getStoreSizeInBits())/8;
1799 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1800 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1801 const TargetLowering *TLI = TM.getTargetLowering();
1802 const DataLayout *TD = TLI->getDataLayout();
1803 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1804 TD->getPrefTypeAlignment(Ty2));
1806 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1807 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1808 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1811 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1812 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1813 // These setcc operations always fold.
1817 case ISD::SETFALSE2: return getConstant(0, VT);
1819 case ISD::SETTRUE2: {
1820 const TargetLowering *TLI = TM.getTargetLowering();
1821 TargetLowering::BooleanContent Cnt =
1822 TLI->getBooleanContents(N1->getValueType(0));
1824 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1837 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1841 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1842 const APInt &C2 = N2C->getAPIntValue();
1843 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1844 const APInt &C1 = N1C->getAPIntValue();
1847 default: llvm_unreachable("Unknown integer setcc!");
1848 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1849 case ISD::SETNE: return getConstant(C1 != C2, VT);
1850 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1851 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1852 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1853 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1854 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1855 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1856 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1857 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1861 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1862 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1863 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1866 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1867 return getUNDEF(VT);
1869 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1870 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1871 return getUNDEF(VT);
1873 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1874 R==APFloat::cmpLessThan, VT);
1875 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1876 return getUNDEF(VT);
1878 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1879 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1880 return getUNDEF(VT);
1882 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1883 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1884 return getUNDEF(VT);
1886 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1887 R==APFloat::cmpEqual, VT);
1888 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1889 return getUNDEF(VT);
1891 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1892 R==APFloat::cmpEqual, VT);
1893 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1894 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1895 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1896 R==APFloat::cmpEqual, VT);
1897 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1898 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1899 R==APFloat::cmpLessThan, VT);
1900 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1901 R==APFloat::cmpUnordered, VT);
1902 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1903 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1906 // Ensure that the constant occurs on the RHS.
1907 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1908 MVT CompVT = N1.getValueType().getSimpleVT();
1909 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1912 return getSetCC(dl, VT, N2, N1, SwappedCond);
1916 // Could not fold it.
1920 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1921 /// use this predicate to simplify operations downstream.
1922 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1923 // This predicate is not safe for vector operations.
1924 if (Op.getValueType().isVector())
1927 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1928 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1931 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1932 /// this predicate to simplify operations downstream. Mask is known to be zero
1933 /// for bits that V cannot have.
1934 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1935 unsigned Depth) const {
1936 APInt KnownZero, KnownOne;
1937 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1938 return (KnownZero & Mask) == Mask;
1941 /// Determine which bits of Op are known to be either zero or one and return
1942 /// them in the KnownZero/KnownOne bitsets.
1943 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1944 APInt &KnownOne, unsigned Depth) const {
1945 const TargetLowering *TLI = TM.getTargetLowering();
1946 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1948 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1950 return; // Limit search depth.
1952 APInt KnownZero2, KnownOne2;
1954 switch (Op.getOpcode()) {
1956 // We know all of the bits for a constant!
1957 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1958 KnownZero = ~KnownOne;
1961 // If either the LHS or the RHS are Zero, the result is zero.
1962 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1963 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1965 // Output known-1 bits are only known if set in both the LHS & RHS.
1966 KnownOne &= KnownOne2;
1967 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1968 KnownZero |= KnownZero2;
1971 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1972 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1974 // Output known-0 bits are only known if clear in both the LHS & RHS.
1975 KnownZero &= KnownZero2;
1976 // Output known-1 are known to be set if set in either the LHS | RHS.
1977 KnownOne |= KnownOne2;
1980 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1981 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1983 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1984 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1985 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1986 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1987 KnownZero = KnownZeroOut;
1991 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1992 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1994 // If low bits are zero in either operand, output low known-0 bits.
1995 // Also compute a conserative estimate for high known-0 bits.
1996 // More trickiness is possible, but this is sufficient for the
1997 // interesting case of alignment computation.
1998 KnownOne.clearAllBits();
1999 unsigned TrailZ = KnownZero.countTrailingOnes() +
2000 KnownZero2.countTrailingOnes();
2001 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2002 KnownZero2.countLeadingOnes(),
2003 BitWidth) - BitWidth;
2005 TrailZ = std::min(TrailZ, BitWidth);
2006 LeadZ = std::min(LeadZ, BitWidth);
2007 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2008 APInt::getHighBitsSet(BitWidth, LeadZ);
2012 // For the purposes of computing leading zeros we can conservatively
2013 // treat a udiv as a logical right shift by the power of 2 known to
2014 // be less than the denominator.
2015 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2016 unsigned LeadZ = KnownZero2.countLeadingOnes();
2018 KnownOne2.clearAllBits();
2019 KnownZero2.clearAllBits();
2020 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2021 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2022 if (RHSUnknownLeadingOnes != BitWidth)
2023 LeadZ = std::min(BitWidth,
2024 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2026 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2030 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2031 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2033 // Only known if known in both the LHS and RHS.
2034 KnownOne &= KnownOne2;
2035 KnownZero &= KnownZero2;
2037 case ISD::SELECT_CC:
2038 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2039 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2041 // Only known if known in both the LHS and RHS.
2042 KnownOne &= KnownOne2;
2043 KnownZero &= KnownZero2;
2051 if (Op.getResNo() != 1)
2053 // The boolean result conforms to getBooleanContents.
2054 // If we know the result of a setcc has the top bits zero, use this info.
2055 // We know that we have an integer-based boolean since these operations
2056 // are only available for integer.
2057 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2058 TargetLowering::ZeroOrOneBooleanContent &&
2060 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2063 // If we know the result of a setcc has the top bits zero, use this info.
2064 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2065 TargetLowering::ZeroOrOneBooleanContent &&
2067 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2070 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2071 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2072 unsigned ShAmt = SA->getZExtValue();
2074 // If the shift count is an invalid immediate, don't do anything.
2075 if (ShAmt >= BitWidth)
2078 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2079 KnownZero <<= ShAmt;
2081 // low bits known zero.
2082 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2086 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2087 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2088 unsigned ShAmt = SA->getZExtValue();
2090 // If the shift count is an invalid immediate, don't do anything.
2091 if (ShAmt >= BitWidth)
2094 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2095 KnownZero = KnownZero.lshr(ShAmt);
2096 KnownOne = KnownOne.lshr(ShAmt);
2098 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2099 KnownZero |= HighBits; // High bits known zero.
2103 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2104 unsigned ShAmt = SA->getZExtValue();
2106 // If the shift count is an invalid immediate, don't do anything.
2107 if (ShAmt >= BitWidth)
2110 // If any of the demanded bits are produced by the sign extension, we also
2111 // demand the input sign bit.
2112 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2114 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2115 KnownZero = KnownZero.lshr(ShAmt);
2116 KnownOne = KnownOne.lshr(ShAmt);
2118 // Handle the sign bits.
2119 APInt SignBit = APInt::getSignBit(BitWidth);
2120 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2122 if (KnownZero.intersects(SignBit)) {
2123 KnownZero |= HighBits; // New bits are known zero.
2124 } else if (KnownOne.intersects(SignBit)) {
2125 KnownOne |= HighBits; // New bits are known one.
2129 case ISD::SIGN_EXTEND_INREG: {
2130 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2131 unsigned EBits = EVT.getScalarType().getSizeInBits();
2133 // Sign extension. Compute the demanded bits in the result that are not
2134 // present in the input.
2135 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2137 APInt InSignBit = APInt::getSignBit(EBits);
2138 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2140 // If the sign extended bits are demanded, we know that the sign
2142 InSignBit = InSignBit.zext(BitWidth);
2143 if (NewBits.getBoolValue())
2144 InputDemandedBits |= InSignBit;
2146 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2147 KnownOne &= InputDemandedBits;
2148 KnownZero &= InputDemandedBits;
2150 // If the sign bit of the input is known set or clear, then we know the
2151 // top bits of the result.
2152 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2153 KnownZero |= NewBits;
2154 KnownOne &= ~NewBits;
2155 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2156 KnownOne |= NewBits;
2157 KnownZero &= ~NewBits;
2158 } else { // Input sign bit unknown
2159 KnownZero &= ~NewBits;
2160 KnownOne &= ~NewBits;
2165 case ISD::CTTZ_ZERO_UNDEF:
2167 case ISD::CTLZ_ZERO_UNDEF:
2169 unsigned LowBits = Log2_32(BitWidth)+1;
2170 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2171 KnownOne.clearAllBits();
2175 LoadSDNode *LD = cast<LoadSDNode>(Op);
2176 // If this is a ZEXTLoad and we are looking at the loaded value.
2177 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2178 EVT VT = LD->getMemoryVT();
2179 unsigned MemBits = VT.getScalarType().getSizeInBits();
2180 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2181 } else if (const MDNode *Ranges = LD->getRanges()) {
2182 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2186 case ISD::ZERO_EXTEND: {
2187 EVT InVT = Op.getOperand(0).getValueType();
2188 unsigned InBits = InVT.getScalarType().getSizeInBits();
2189 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2190 KnownZero = KnownZero.trunc(InBits);
2191 KnownOne = KnownOne.trunc(InBits);
2192 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2193 KnownZero = KnownZero.zext(BitWidth);
2194 KnownOne = KnownOne.zext(BitWidth);
2195 KnownZero |= NewBits;
2198 case ISD::SIGN_EXTEND: {
2199 EVT InVT = Op.getOperand(0).getValueType();
2200 unsigned InBits = InVT.getScalarType().getSizeInBits();
2201 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2203 KnownZero = KnownZero.trunc(InBits);
2204 KnownOne = KnownOne.trunc(InBits);
2205 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2207 // Note if the sign bit is known to be zero or one.
2208 bool SignBitKnownZero = KnownZero.isNegative();
2209 bool SignBitKnownOne = KnownOne.isNegative();
2211 KnownZero = KnownZero.zext(BitWidth);
2212 KnownOne = KnownOne.zext(BitWidth);
2214 // If the sign bit is known zero or one, the top bits match.
2215 if (SignBitKnownZero)
2216 KnownZero |= NewBits;
2217 else if (SignBitKnownOne)
2218 KnownOne |= NewBits;
2221 case ISD::ANY_EXTEND: {
2222 EVT InVT = Op.getOperand(0).getValueType();
2223 unsigned InBits = InVT.getScalarType().getSizeInBits();
2224 KnownZero = KnownZero.trunc(InBits);
2225 KnownOne = KnownOne.trunc(InBits);
2226 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2227 KnownZero = KnownZero.zext(BitWidth);
2228 KnownOne = KnownOne.zext(BitWidth);
2231 case ISD::TRUNCATE: {
2232 EVT InVT = Op.getOperand(0).getValueType();
2233 unsigned InBits = InVT.getScalarType().getSizeInBits();
2234 KnownZero = KnownZero.zext(InBits);
2235 KnownOne = KnownOne.zext(InBits);
2236 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2237 KnownZero = KnownZero.trunc(BitWidth);
2238 KnownOne = KnownOne.trunc(BitWidth);
2241 case ISD::AssertZext: {
2242 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2243 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2244 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2245 KnownZero |= (~InMask);
2246 KnownOne &= (~KnownZero);
2250 // All bits are zero except the low bit.
2251 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2255 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2256 // We know that the top bits of C-X are clear if X contains less bits
2257 // than C (i.e. no wrap-around can happen). For example, 20-X is
2258 // positive if we can prove that X is >= 0 and < 16.
2259 if (CLHS->getAPIntValue().isNonNegative()) {
2260 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2261 // NLZ can't be BitWidth with no sign bit
2262 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2263 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2265 // If all of the MaskV bits are known to be zero, then we know the
2266 // output top bits are zero, because we now know that the output is
2268 if ((KnownZero2 & MaskV) == MaskV) {
2269 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2270 // Top bits known zero.
2271 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2279 // Output known-0 bits are known if clear or set in both the low clear bits
2280 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2281 // low 3 bits clear.
2282 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2283 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2285 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2286 KnownZeroOut = std::min(KnownZeroOut,
2287 KnownZero2.countTrailingOnes());
2289 if (Op.getOpcode() == ISD::ADD) {
2290 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2294 // With ADDE, a carry bit may be added in, so we can only use this
2295 // information if we know (at least) that the low two bits are clear. We
2296 // then return to the caller that the low bit is unknown but that other bits
2298 if (KnownZeroOut >= 2) // ADDE
2299 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2303 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2304 const APInt &RA = Rem->getAPIntValue().abs();
2305 if (RA.isPowerOf2()) {
2306 APInt LowBits = RA - 1;
2307 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2309 // The low bits of the first operand are unchanged by the srem.
2310 KnownZero = KnownZero2 & LowBits;
2311 KnownOne = KnownOne2 & LowBits;
2313 // If the first operand is non-negative or has all low bits zero, then
2314 // the upper bits are all zero.
2315 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2316 KnownZero |= ~LowBits;
2318 // If the first operand is negative and not all low bits are zero, then
2319 // the upper bits are all one.
2320 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2321 KnownOne |= ~LowBits;
2322 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2327 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2328 const APInt &RA = Rem->getAPIntValue();
2329 if (RA.isPowerOf2()) {
2330 APInt LowBits = (RA - 1);
2331 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2333 // The upper bits are all zero, the lower ones are unchanged.
2334 KnownZero = KnownZero2 | ~LowBits;
2335 KnownOne = KnownOne2 & LowBits;
2340 // Since the result is less than or equal to either operand, any leading
2341 // zero bits in either operand must also exist in the result.
2342 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2343 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2345 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2346 KnownZero2.countLeadingOnes());
2347 KnownOne.clearAllBits();
2348 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2351 case ISD::FrameIndex:
2352 case ISD::TargetFrameIndex:
2353 if (unsigned Align = InferPtrAlignment(Op)) {
2354 // The low bits are known zero if the pointer is aligned.
2355 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2361 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2364 case ISD::INTRINSIC_WO_CHAIN:
2365 case ISD::INTRINSIC_W_CHAIN:
2366 case ISD::INTRINSIC_VOID:
2367 // Allow the target to implement this method for its nodes.
2368 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2372 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2375 /// ComputeNumSignBits - Return the number of times the sign bit of the
2376 /// register is replicated into the other bits. We know that at least 1 bit
2377 /// is always equal to the sign bit (itself), but other cases can give us
2378 /// information. For example, immediately after an "SRA X, 2", we know that
2379 /// the top 3 bits are all equal to each other, so we return 3.
2380 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2381 const TargetLowering *TLI = TM.getTargetLowering();
2382 EVT VT = Op.getValueType();
2383 assert(VT.isInteger() && "Invalid VT!");
2384 unsigned VTBits = VT.getScalarType().getSizeInBits();
2386 unsigned FirstAnswer = 1;
2389 return 1; // Limit search depth.
2391 switch (Op.getOpcode()) {
2393 case ISD::AssertSext:
2394 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2395 return VTBits-Tmp+1;
2396 case ISD::AssertZext:
2397 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2400 case ISD::Constant: {
2401 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2402 return Val.getNumSignBits();
2405 case ISD::SIGN_EXTEND:
2407 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2408 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2410 case ISD::SIGN_EXTEND_INREG:
2411 // Max of the input and what this extends.
2413 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2416 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2417 return std::max(Tmp, Tmp2);
2420 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2421 // SRA X, C -> adds C sign bits.
2422 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2423 Tmp += C->getZExtValue();
2424 if (Tmp > VTBits) Tmp = VTBits;
2428 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2429 // shl destroys sign bits.
2430 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2431 if (C->getZExtValue() >= VTBits || // Bad shift.
2432 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2433 return Tmp - C->getZExtValue();
2438 case ISD::XOR: // NOT is handled here.
2439 // Logical binary ops preserve the number of sign bits at the worst.
2440 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2442 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2443 FirstAnswer = std::min(Tmp, Tmp2);
2444 // We computed what we know about the sign bits as our first
2445 // answer. Now proceed to the generic code that uses
2446 // computeKnownBits, and pick whichever answer is better.
2451 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2452 if (Tmp == 1) return 1; // Early out.
2453 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2454 return std::min(Tmp, Tmp2);
2462 if (Op.getResNo() != 1)
2464 // The boolean result conforms to getBooleanContents. Fall through.
2465 // If setcc returns 0/-1, all bits are sign bits.
2466 // We know that we have an integer-based boolean since these operations
2467 // are only available for integer.
2468 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2469 TargetLowering::ZeroOrNegativeOneBooleanContent)
2473 // If setcc returns 0/-1, all bits are sign bits.
2474 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2475 TargetLowering::ZeroOrNegativeOneBooleanContent)
2480 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2481 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2483 // Handle rotate right by N like a rotate left by 32-N.
2484 if (Op.getOpcode() == ISD::ROTR)
2485 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2487 // If we aren't rotating out all of the known-in sign bits, return the
2488 // number that are left. This handles rotl(sext(x), 1) for example.
2489 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2490 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2494 // Add can have at most one carry bit. Thus we know that the output
2495 // is, at worst, one more bit than the inputs.
2496 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2497 if (Tmp == 1) return 1; // Early out.
2499 // Special case decrementing a value (ADD X, -1):
2500 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2501 if (CRHS->isAllOnesValue()) {
2502 APInt KnownZero, KnownOne;
2503 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2505 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2507 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2510 // If we are subtracting one from a positive number, there is no carry
2511 // out of the result.
2512 if (KnownZero.isNegative())
2516 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2517 if (Tmp2 == 1) return 1;
2518 return std::min(Tmp, Tmp2)-1;
2521 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2522 if (Tmp2 == 1) return 1;
2525 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2526 if (CLHS->isNullValue()) {
2527 APInt KnownZero, KnownOne;
2528 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2529 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2531 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2534 // If the input is known to be positive (the sign bit is known clear),
2535 // the output of the NEG has the same number of sign bits as the input.
2536 if (KnownZero.isNegative())
2539 // Otherwise, we treat this like a SUB.
2542 // Sub can have at most one carry bit. Thus we know that the output
2543 // is, at worst, one more bit than the inputs.
2544 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2545 if (Tmp == 1) return 1; // Early out.
2546 return std::min(Tmp, Tmp2)-1;
2548 // FIXME: it's tricky to do anything useful for this, but it is an important
2549 // case for targets like X86.
2553 // If we are looking at the loaded value of the SDNode.
2554 if (Op.getResNo() == 0) {
2555 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2556 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2557 unsigned ExtType = LD->getExtensionType();
2560 case ISD::SEXTLOAD: // '17' bits known
2561 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2562 return VTBits-Tmp+1;
2563 case ISD::ZEXTLOAD: // '16' bits known
2564 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2570 // Allow the target to implement this method for its nodes.
2571 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2572 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2573 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2574 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2575 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2576 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2579 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2580 // use this information.
2581 APInt KnownZero, KnownOne;
2582 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2585 if (KnownZero.isNegative()) { // sign bit is 0
2587 } else if (KnownOne.isNegative()) { // sign bit is 1;
2594 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2595 // the number of identical bits in the top of the input value.
2597 Mask <<= Mask.getBitWidth()-VTBits;
2598 // Return # leading zeros. We use 'min' here in case Val was zero before
2599 // shifting. We don't want to return '64' as for an i32 "0".
2600 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2603 /// isBaseWithConstantOffset - Return true if the specified operand is an
2604 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2605 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2606 /// semantics as an ADD. This handles the equivalence:
2607 /// X|Cst == X+Cst iff X&Cst = 0.
2608 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2609 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2610 !isa<ConstantSDNode>(Op.getOperand(1)))
2613 if (Op.getOpcode() == ISD::OR &&
2614 !MaskedValueIsZero(Op.getOperand(0),
2615 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2622 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2623 // If we're told that NaNs won't happen, assume they won't.
2624 if (getTarget().Options.NoNaNsFPMath)
2627 // If the value is a constant, we can obviously see if it is a NaN or not.
2628 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2629 return !C->getValueAPF().isNaN();
2631 // TODO: Recognize more cases here.
2636 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2637 // If the value is a constant, we can obviously see if it is a zero or not.
2638 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2639 return !C->isZero();
2641 // TODO: Recognize more cases here.
2642 switch (Op.getOpcode()) {
2645 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2646 return !C->isNullValue();
2653 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2654 // Check the obvious case.
2655 if (A == B) return true;
2657 // For for negative and positive zero.
2658 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2659 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2660 if (CA->isZero() && CB->isZero()) return true;
2662 // Otherwise they may not be equal.
2666 /// getNode - Gets or creates the specified node.
2668 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2669 FoldingSetNodeID ID;
2670 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2672 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2673 return SDValue(E, 0);
2675 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2676 DL.getDebugLoc(), getVTList(VT));
2677 CSEMap.InsertNode(N, IP);
2679 AllNodes.push_back(N);
2683 return SDValue(N, 0);
2686 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2687 EVT VT, SDValue Operand) {
2688 // Constant fold unary operations with an integer constant operand. Even
2689 // opaque constant will be folded, because the folding of unary operations
2690 // doesn't create new constants with different values. Nevertheless, the
2691 // opaque flag is preserved during folding to prevent future folding with
2693 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2694 const APInt &Val = C->getAPIntValue();
2697 case ISD::SIGN_EXTEND:
2698 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2699 C->isTargetOpcode(), C->isOpaque());
2700 case ISD::ANY_EXTEND:
2701 case ISD::ZERO_EXTEND:
2703 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2704 C->isTargetOpcode(), C->isOpaque());
2705 case ISD::UINT_TO_FP:
2706 case ISD::SINT_TO_FP: {
2707 APFloat apf(EVTToAPFloatSemantics(VT),
2708 APInt::getNullValue(VT.getSizeInBits()));
2709 (void)apf.convertFromAPInt(Val,
2710 Opcode==ISD::SINT_TO_FP,
2711 APFloat::rmNearestTiesToEven);
2712 return getConstantFP(apf, VT);
2715 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2716 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2717 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2718 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2721 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2724 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2727 case ISD::CTLZ_ZERO_UNDEF:
2728 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2731 case ISD::CTTZ_ZERO_UNDEF:
2732 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2737 // Constant fold unary operations with a floating point constant operand.
2738 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2739 APFloat V = C->getValueAPF(); // make copy
2743 return getConstantFP(V, VT);
2746 return getConstantFP(V, VT);
2748 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2749 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2750 return getConstantFP(V, VT);
2754 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2755 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2756 return getConstantFP(V, VT);
2760 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2761 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2762 return getConstantFP(V, VT);
2765 case ISD::FP_EXTEND: {
2767 // This can return overflow, underflow, or inexact; we don't care.
2768 // FIXME need to be more flexible about rounding mode.
2769 (void)V.convert(EVTToAPFloatSemantics(VT),
2770 APFloat::rmNearestTiesToEven, &ignored);
2771 return getConstantFP(V, VT);
2773 case ISD::FP_TO_SINT:
2774 case ISD::FP_TO_UINT: {
2777 assert(integerPartWidth >= 64);
2778 // FIXME need to be more flexible about rounding mode.
2779 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2780 Opcode==ISD::FP_TO_SINT,
2781 APFloat::rmTowardZero, &ignored);
2782 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2784 APInt api(VT.getSizeInBits(), x);
2785 return getConstant(api, VT);
2788 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2789 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2790 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2791 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2796 // Constant fold unary operations with a vector integer operand.
2797 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2800 unsigned SplatBitSize;
2801 bool DummyHasUndefs;
2802 if (BV->isConstantSplat(Val, DummyUndefs, SplatBitSize, DummyHasUndefs)) {
2805 // FIXME: Entirely reasonable to perform folding of other unary
2806 // operations here as the need arises.
2808 case ISD::UINT_TO_FP:
2809 case ISD::SINT_TO_FP: {
2811 EVTToAPFloatSemantics(VT.getVectorElementType()),
2812 APInt::getNullValue(VT.getVectorElementType().getSizeInBits()));
2813 (void)APF.convertFromAPInt(Val, Opcode == ISD::SINT_TO_FP,
2814 APFloat::rmNearestTiesToEven);
2816 return getConstantFP(APF, VT);
2822 unsigned OpOpcode = Operand.getNode()->getOpcode();
2824 case ISD::TokenFactor:
2825 case ISD::MERGE_VALUES:
2826 case ISD::CONCAT_VECTORS:
2827 return Operand; // Factor, merge or concat of one node? No need.
2828 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2829 case ISD::FP_EXTEND:
2830 assert(VT.isFloatingPoint() &&
2831 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2832 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2833 assert((!VT.isVector() ||
2834 VT.getVectorNumElements() ==
2835 Operand.getValueType().getVectorNumElements()) &&
2836 "Vector element count mismatch!");
2837 if (Operand.getOpcode() == ISD::UNDEF)
2838 return getUNDEF(VT);
2840 case ISD::SIGN_EXTEND:
2841 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2842 "Invalid SIGN_EXTEND!");
2843 if (Operand.getValueType() == VT) return Operand; // noop extension
2844 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2845 "Invalid sext node, dst < src!");
2846 assert((!VT.isVector() ||
2847 VT.getVectorNumElements() ==
2848 Operand.getValueType().getVectorNumElements()) &&
2849 "Vector element count mismatch!");
2850 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2851 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2852 else if (OpOpcode == ISD::UNDEF)
2853 // sext(undef) = 0, because the top bits will all be the same.
2854 return getConstant(0, VT);
2856 case ISD::ZERO_EXTEND:
2857 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2858 "Invalid ZERO_EXTEND!");
2859 if (Operand.getValueType() == VT) return Operand; // noop extension
2860 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2861 "Invalid zext node, dst < src!");
2862 assert((!VT.isVector() ||
2863 VT.getVectorNumElements() ==
2864 Operand.getValueType().getVectorNumElements()) &&
2865 "Vector element count mismatch!");
2866 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2867 return getNode(ISD::ZERO_EXTEND, DL, VT,
2868 Operand.getNode()->getOperand(0));
2869 else if (OpOpcode == ISD::UNDEF)
2870 // zext(undef) = 0, because the top bits will be zero.
2871 return getConstant(0, VT);
2873 case ISD::ANY_EXTEND:
2874 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2875 "Invalid ANY_EXTEND!");
2876 if (Operand.getValueType() == VT) return Operand; // noop extension
2877 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2878 "Invalid anyext node, dst < src!");
2879 assert((!VT.isVector() ||
2880 VT.getVectorNumElements() ==
2881 Operand.getValueType().getVectorNumElements()) &&
2882 "Vector element count mismatch!");
2884 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2885 OpOpcode == ISD::ANY_EXTEND)
2886 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2887 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2888 else if (OpOpcode == ISD::UNDEF)
2889 return getUNDEF(VT);
2891 // (ext (trunx x)) -> x
2892 if (OpOpcode == ISD::TRUNCATE) {
2893 SDValue OpOp = Operand.getNode()->getOperand(0);
2894 if (OpOp.getValueType() == VT)
2899 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2900 "Invalid TRUNCATE!");
2901 if (Operand.getValueType() == VT) return Operand; // noop truncate
2902 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2903 "Invalid truncate node, src < dst!");
2904 assert((!VT.isVector() ||
2905 VT.getVectorNumElements() ==
2906 Operand.getValueType().getVectorNumElements()) &&
2907 "Vector element count mismatch!");
2908 if (OpOpcode == ISD::TRUNCATE)
2909 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2910 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2911 OpOpcode == ISD::ANY_EXTEND) {
2912 // If the source is smaller than the dest, we still need an extend.
2913 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2914 .bitsLT(VT.getScalarType()))
2915 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2916 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2917 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2918 return Operand.getNode()->getOperand(0);
2920 if (OpOpcode == ISD::UNDEF)
2921 return getUNDEF(VT);
2924 // Basic sanity checking.
2925 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2926 && "Cannot BITCAST between types of different sizes!");
2927 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2928 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2929 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2930 if (OpOpcode == ISD::UNDEF)
2931 return getUNDEF(VT);
2933 case ISD::SCALAR_TO_VECTOR:
2934 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2935 (VT.getVectorElementType() == Operand.getValueType() ||
2936 (VT.getVectorElementType().isInteger() &&
2937 Operand.getValueType().isInteger() &&
2938 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2939 "Illegal SCALAR_TO_VECTOR node!");
2940 if (OpOpcode == ISD::UNDEF)
2941 return getUNDEF(VT);
2942 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2943 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2944 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2945 Operand.getConstantOperandVal(1) == 0 &&
2946 Operand.getOperand(0).getValueType() == VT)
2947 return Operand.getOperand(0);
2950 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2951 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2952 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2953 Operand.getNode()->getOperand(0));
2954 if (OpOpcode == ISD::FNEG) // --X -> X
2955 return Operand.getNode()->getOperand(0);
2958 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2959 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2964 SDVTList VTs = getVTList(VT);
2965 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2966 FoldingSetNodeID ID;
2967 SDValue Ops[1] = { Operand };
2968 AddNodeIDNode(ID, Opcode, VTs, Ops);
2970 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2971 return SDValue(E, 0);
2973 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2974 DL.getDebugLoc(), VTs, Operand);
2975 CSEMap.InsertNode(N, IP);
2977 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2978 DL.getDebugLoc(), VTs, Operand);
2981 AllNodes.push_back(N);
2985 return SDValue(N, 0);
2988 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2989 SDNode *Cst1, SDNode *Cst2) {
2990 // If the opcode is a target-specific ISD node, there's nothing we can
2991 // do here and the operand rules may not line up with the below, so
2993 if (Opcode >= ISD::BUILTIN_OP_END)
2996 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2997 SmallVector<SDValue, 4> Outputs;
2998 EVT SVT = VT.getScalarType();
3000 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3001 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3002 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3005 if (Scalar1 && Scalar2)
3006 // Scalar instruction.
3007 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3009 // For vectors extract each constant element into Inputs so we can constant
3010 // fold them individually.
3011 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3012 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3016 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3018 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3019 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3020 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3021 if (!V1 || !V2) // Not a constant, bail.
3024 if (V1->isOpaque() || V2->isOpaque())
3027 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3028 // FIXME: This is valid and could be handled by truncating the APInts.
3029 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3032 Inputs.push_back(std::make_pair(V1, V2));
3036 // We have a number of constant values, constant fold them element by element.
3037 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3038 const APInt &C1 = Inputs[I].first->getAPIntValue();
3039 const APInt &C2 = Inputs[I].second->getAPIntValue();
3043 Outputs.push_back(getConstant(C1 + C2, SVT));
3046 Outputs.push_back(getConstant(C1 - C2, SVT));
3049 Outputs.push_back(getConstant(C1 * C2, SVT));
3052 if (!C2.getBoolValue())
3054 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
3057 if (!C2.getBoolValue())
3059 Outputs.push_back(getConstant(C1.urem(C2), SVT));
3062 if (!C2.getBoolValue())
3064 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
3067 if (!C2.getBoolValue())
3069 Outputs.push_back(getConstant(C1.srem(C2), SVT));
3072 Outputs.push_back(getConstant(C1 & C2, SVT));
3075 Outputs.push_back(getConstant(C1 | C2, SVT));
3078 Outputs.push_back(getConstant(C1 ^ C2, SVT));
3081 Outputs.push_back(getConstant(C1 << C2, SVT));
3084 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
3087 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
3090 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
3093 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
3100 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3101 "Expected a scalar or vector!"));
3103 // Handle the scalar case first.
3105 return Outputs.back();
3107 // We may have a vector type but a scalar result. Create a splat.
3108 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3110 // Build a big vector out of the scalar elements we generated.
3111 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3114 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3115 SDValue N2, bool nuw, bool nsw, bool exact) {
3116 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3117 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3120 case ISD::TokenFactor:
3121 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3122 N2.getValueType() == MVT::Other && "Invalid token factor!");
3123 // Fold trivial token factors.
3124 if (N1.getOpcode() == ISD::EntryToken) return N2;
3125 if (N2.getOpcode() == ISD::EntryToken) return N1;
3126 if (N1 == N2) return N1;
3128 case ISD::CONCAT_VECTORS:
3129 // Concat of UNDEFs is UNDEF.
3130 if (N1.getOpcode() == ISD::UNDEF &&
3131 N2.getOpcode() == ISD::UNDEF)
3132 return getUNDEF(VT);
3134 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3135 // one big BUILD_VECTOR.
3136 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3137 N2.getOpcode() == ISD::BUILD_VECTOR) {
3138 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3139 N1.getNode()->op_end());
3140 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3141 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3145 assert(VT.isInteger() && "This operator does not apply to FP types!");
3146 assert(N1.getValueType() == N2.getValueType() &&
3147 N1.getValueType() == VT && "Binary operator types must match!");
3148 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3149 // worth handling here.
3150 if (N2C && N2C->isNullValue())
3152 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3159 assert(VT.isInteger() && "This operator does not apply to FP types!");
3160 assert(N1.getValueType() == N2.getValueType() &&
3161 N1.getValueType() == VT && "Binary operator types must match!");
3162 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3163 // it's worth handling here.
3164 if (N2C && N2C->isNullValue())
3174 assert(VT.isInteger() && "This operator does not apply to FP types!");
3175 assert(N1.getValueType() == N2.getValueType() &&
3176 N1.getValueType() == VT && "Binary operator types must match!");
3183 if (getTarget().Options.UnsafeFPMath) {
3184 if (Opcode == ISD::FADD) {
3186 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3187 if (CFP->getValueAPF().isZero())
3190 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3191 if (CFP->getValueAPF().isZero())
3193 } else if (Opcode == ISD::FSUB) {
3195 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3196 if (CFP->getValueAPF().isZero())
3198 } else if (Opcode == ISD::FMUL) {
3199 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3202 // If the first operand isn't the constant, try the second
3204 CFP = dyn_cast<ConstantFPSDNode>(N2);
3211 return SDValue(CFP,0);
3213 if (CFP->isExactlyValue(1.0))
3218 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3219 assert(N1.getValueType() == N2.getValueType() &&
3220 N1.getValueType() == VT && "Binary operator types must match!");
3222 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3223 assert(N1.getValueType() == VT &&
3224 N1.getValueType().isFloatingPoint() &&
3225 N2.getValueType().isFloatingPoint() &&
3226 "Invalid FCOPYSIGN!");
3233 assert(VT == N1.getValueType() &&
3234 "Shift operators return type must be the same as their first arg");
3235 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3236 "Shifts only work on integers");
3237 assert((!VT.isVector() || VT == N2.getValueType()) &&
3238 "Vector shift amounts must be in the same as their first arg");
3239 // Verify that the shift amount VT is bit enough to hold valid shift
3240 // amounts. This catches things like trying to shift an i1024 value by an
3241 // i8, which is easy to fall into in generic code that uses
3242 // TLI.getShiftAmount().
3243 assert(N2.getValueType().getSizeInBits() >=
3244 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3245 "Invalid use of small shift amount with oversized value!");
3247 // Always fold shifts of i1 values so the code generator doesn't need to
3248 // handle them. Since we know the size of the shift has to be less than the
3249 // size of the value, the shift/rotate count is guaranteed to be zero.
3252 if (N2C && N2C->isNullValue())
3255 case ISD::FP_ROUND_INREG: {
3256 EVT EVT = cast<VTSDNode>(N2)->getVT();
3257 assert(VT == N1.getValueType() && "Not an inreg round!");
3258 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3259 "Cannot FP_ROUND_INREG integer types");
3260 assert(EVT.isVector() == VT.isVector() &&
3261 "FP_ROUND_INREG type should be vector iff the operand "
3263 assert((!EVT.isVector() ||
3264 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3265 "Vector element counts must match in FP_ROUND_INREG");
3266 assert(EVT.bitsLE(VT) && "Not rounding down!");
3268 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3272 assert(VT.isFloatingPoint() &&
3273 N1.getValueType().isFloatingPoint() &&
3274 VT.bitsLE(N1.getValueType()) &&
3275 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3276 if (N1.getValueType() == VT) return N1; // noop conversion.
3278 case ISD::AssertSext:
3279 case ISD::AssertZext: {
3280 EVT EVT = cast<VTSDNode>(N2)->getVT();
3281 assert(VT == N1.getValueType() && "Not an inreg extend!");
3282 assert(VT.isInteger() && EVT.isInteger() &&
3283 "Cannot *_EXTEND_INREG FP types");
3284 assert(!EVT.isVector() &&
3285 "AssertSExt/AssertZExt type should be the vector element type "
3286 "rather than the vector type!");
3287 assert(EVT.bitsLE(VT) && "Not extending!");
3288 if (VT == EVT) return N1; // noop assertion.
3291 case ISD::SIGN_EXTEND_INREG: {
3292 EVT EVT = cast<VTSDNode>(N2)->getVT();
3293 assert(VT == N1.getValueType() && "Not an inreg extend!");
3294 assert(VT.isInteger() && EVT.isInteger() &&
3295 "Cannot *_EXTEND_INREG FP types");
3296 assert(EVT.isVector() == VT.isVector() &&
3297 "SIGN_EXTEND_INREG type should be vector iff the operand "
3299 assert((!EVT.isVector() ||
3300 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3301 "Vector element counts must match in SIGN_EXTEND_INREG");
3302 assert(EVT.bitsLE(VT) && "Not extending!");
3303 if (EVT == VT) return N1; // Not actually extending
3306 APInt Val = N1C->getAPIntValue();
3307 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3308 Val <<= Val.getBitWidth()-FromBits;
3309 Val = Val.ashr(Val.getBitWidth()-FromBits);
3310 return getConstant(Val, VT);
3314 case ISD::EXTRACT_VECTOR_ELT:
3315 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3316 if (N1.getOpcode() == ISD::UNDEF)
3317 return getUNDEF(VT);
3319 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3320 // expanding copies of large vectors from registers.
3322 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3323 N1.getNumOperands() > 0) {
3325 N1.getOperand(0).getValueType().getVectorNumElements();
3326 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3327 N1.getOperand(N2C->getZExtValue() / Factor),
3328 getConstant(N2C->getZExtValue() % Factor,
3329 N2.getValueType()));
3332 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3333 // expanding large vector constants.
3334 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3335 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3337 if (VT != Elt.getValueType())
3338 // If the vector element type is not legal, the BUILD_VECTOR operands
3339 // are promoted and implicitly truncated, and the result implicitly
3340 // extended. Make that explicit here.
3341 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3346 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3347 // operations are lowered to scalars.
3348 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3349 // If the indices are the same, return the inserted element else
3350 // if the indices are known different, extract the element from
3351 // the original vector.
3352 SDValue N1Op2 = N1.getOperand(2);
3353 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3355 if (N1Op2C && N2C) {
3356 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3357 if (VT == N1.getOperand(1).getValueType())
3358 return N1.getOperand(1);
3360 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3363 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3367 case ISD::EXTRACT_ELEMENT:
3368 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3369 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3370 (N1.getValueType().isInteger() == VT.isInteger()) &&
3371 N1.getValueType() != VT &&
3372 "Wrong types for EXTRACT_ELEMENT!");
3374 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3375 // 64-bit integers into 32-bit parts. Instead of building the extract of
3376 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3377 if (N1.getOpcode() == ISD::BUILD_PAIR)
3378 return N1.getOperand(N2C->getZExtValue());
3380 // EXTRACT_ELEMENT of a constant int is also very common.
3381 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3382 unsigned ElementSize = VT.getSizeInBits();
3383 unsigned Shift = ElementSize * N2C->getZExtValue();
3384 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3385 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3388 case ISD::EXTRACT_SUBVECTOR: {
3390 if (VT.isSimple() && N1.getValueType().isSimple()) {
3391 assert(VT.isVector() && N1.getValueType().isVector() &&
3392 "Extract subvector VTs must be a vectors!");
3393 assert(VT.getVectorElementType() ==
3394 N1.getValueType().getVectorElementType() &&
3395 "Extract subvector VTs must have the same element type!");
3396 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3397 "Extract subvector must be from larger vector to smaller vector!");
3399 if (isa<ConstantSDNode>(Index.getNode())) {
3400 assert((VT.getVectorNumElements() +
3401 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3402 <= N1.getValueType().getVectorNumElements())
3403 && "Extract subvector overflow!");
3406 // Trivial extraction.
3407 if (VT.getSimpleVT() == N1.getSimpleValueType())
3414 // Perform trivial constant folding.
3415 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3416 if (SV.getNode()) return SV;
3418 // Canonicalize constant to RHS if commutative.
3419 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3420 std::swap(N1C, N2C);
3424 // Constant fold FP operations.
3425 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3426 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3428 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3429 // Canonicalize constant to RHS if commutative.
3430 std::swap(N1CFP, N2CFP);
3433 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3434 APFloat::opStatus s;
3437 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3438 if (s != APFloat::opInvalidOp)
3439 return getConstantFP(V1, VT);
3442 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3443 if (s!=APFloat::opInvalidOp)
3444 return getConstantFP(V1, VT);
3447 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3448 if (s!=APFloat::opInvalidOp)
3449 return getConstantFP(V1, VT);
3452 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3453 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3454 return getConstantFP(V1, VT);
3457 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3458 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3459 return getConstantFP(V1, VT);
3461 case ISD::FCOPYSIGN:
3463 return getConstantFP(V1, VT);
3468 if (Opcode == ISD::FP_ROUND) {
3469 APFloat V = N1CFP->getValueAPF(); // make copy
3471 // This can return overflow, underflow, or inexact; we don't care.
3472 // FIXME need to be more flexible about rounding mode.
3473 (void)V.convert(EVTToAPFloatSemantics(VT),
3474 APFloat::rmNearestTiesToEven, &ignored);
3475 return getConstantFP(V, VT);
3479 // Canonicalize an UNDEF to the RHS, even over a constant.
3480 if (N1.getOpcode() == ISD::UNDEF) {
3481 if (isCommutativeBinOp(Opcode)) {
3485 case ISD::FP_ROUND_INREG:
3486 case ISD::SIGN_EXTEND_INREG:
3492 return N1; // fold op(undef, arg2) -> undef
3500 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3501 // For vectors, we can't easily build an all zero vector, just return
3508 // Fold a bunch of operators when the RHS is undef.
3509 if (N2.getOpcode() == ISD::UNDEF) {
3512 if (N1.getOpcode() == ISD::UNDEF)
3513 // Handle undef ^ undef -> 0 special case. This is a common
3515 return getConstant(0, VT);
3525 return N2; // fold op(arg1, undef) -> undef
3531 if (getTarget().Options.UnsafeFPMath)
3539 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3540 // For vectors, we can't easily build an all zero vector, just return
3545 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3546 // For vectors, we can't easily build an all one vector, just return
3554 // Memoize this node if possible.
3556 SDVTList VTs = getVTList(VT);
3557 const bool BinOpHasFlags = isBinOpWithFlags(Opcode);
3558 if (VT != MVT::Glue) {
3559 SDValue Ops[] = {N1, N2};
3560 FoldingSetNodeID ID;
3561 AddNodeIDNode(ID, Opcode, VTs, Ops);
3563 AddBinaryNodeIDCustom(ID, Opcode, nuw, nsw, exact);
3565 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3566 return SDValue(E, 0);
3568 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3570 CSEMap.InsertNode(N, IP);
3573 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, nuw, nsw, exact);
3576 AllNodes.push_back(N);
3580 return SDValue(N, 0);
3583 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3584 SDValue N1, SDValue N2, SDValue N3) {
3585 // Perform various simplifications.
3586 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3589 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3590 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3591 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3592 if (N1CFP && N2CFP && N3CFP) {
3593 APFloat V1 = N1CFP->getValueAPF();
3594 const APFloat &V2 = N2CFP->getValueAPF();
3595 const APFloat &V3 = N3CFP->getValueAPF();
3596 APFloat::opStatus s =
3597 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3598 if (s != APFloat::opInvalidOp)
3599 return getConstantFP(V1, VT);
3603 case ISD::CONCAT_VECTORS:
3604 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3605 // one big BUILD_VECTOR.
3606 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3607 N2.getOpcode() == ISD::BUILD_VECTOR &&
3608 N3.getOpcode() == ISD::BUILD_VECTOR) {
3609 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3610 N1.getNode()->op_end());
3611 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3612 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3613 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3617 // Use FoldSetCC to simplify SETCC's.
3618 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3619 if (Simp.getNode()) return Simp;
3624 if (N1C->getZExtValue())
3625 return N2; // select true, X, Y -> X
3626 return N3; // select false, X, Y -> Y
3629 if (N2 == N3) return N2; // select C, X, X -> X
3631 case ISD::VECTOR_SHUFFLE:
3632 llvm_unreachable("should use getVectorShuffle constructor!");
3633 case ISD::INSERT_SUBVECTOR: {
3635 if (VT.isSimple() && N1.getValueType().isSimple()
3636 && N2.getValueType().isSimple()) {
3637 assert(VT.isVector() && N1.getValueType().isVector() &&
3638 N2.getValueType().isVector() &&
3639 "Insert subvector VTs must be a vectors");
3640 assert(VT == N1.getValueType() &&
3641 "Dest and insert subvector source types must match!");
3642 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3643 "Insert subvector must be from smaller vector to larger vector!");
3644 if (isa<ConstantSDNode>(Index.getNode())) {
3645 assert((N2.getValueType().getVectorNumElements() +
3646 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3647 <= VT.getVectorNumElements())
3648 && "Insert subvector overflow!");
3651 // Trivial insertion.
3652 if (VT.getSimpleVT() == N2.getSimpleValueType())
3658 // Fold bit_convert nodes from a type to themselves.
3659 if (N1.getValueType() == VT)
3664 // Memoize node if it doesn't produce a flag.
3666 SDVTList VTs = getVTList(VT);
3667 if (VT != MVT::Glue) {
3668 SDValue Ops[] = { N1, N2, N3 };
3669 FoldingSetNodeID ID;
3670 AddNodeIDNode(ID, Opcode, VTs, Ops);
3672 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3673 return SDValue(E, 0);
3675 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3676 DL.getDebugLoc(), VTs, N1, N2, N3);
3677 CSEMap.InsertNode(N, IP);
3679 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3680 DL.getDebugLoc(), VTs, N1, N2, N3);
3683 AllNodes.push_back(N);
3687 return SDValue(N, 0);
3690 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3691 SDValue N1, SDValue N2, SDValue N3,
3693 SDValue Ops[] = { N1, N2, N3, N4 };
3694 return getNode(Opcode, DL, VT, Ops);
3697 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3698 SDValue N1, SDValue N2, SDValue N3,
3699 SDValue N4, SDValue N5) {
3700 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3701 return getNode(Opcode, DL, VT, Ops);
3704 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3705 /// the incoming stack arguments to be loaded from the stack.
3706 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3707 SmallVector<SDValue, 8> ArgChains;
3709 // Include the original chain at the beginning of the list. When this is
3710 // used by target LowerCall hooks, this helps legalize find the
3711 // CALLSEQ_BEGIN node.
3712 ArgChains.push_back(Chain);
3714 // Add a chain value for each stack argument.
3715 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3716 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3717 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3718 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3719 if (FI->getIndex() < 0)
3720 ArgChains.push_back(SDValue(L, 1));
3722 // Build a tokenfactor for all the chains.
3723 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3726 /// getMemsetValue - Vectorized representation of the memset value
3728 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3730 assert(Value.getOpcode() != ISD::UNDEF);
3732 unsigned NumBits = VT.getScalarType().getSizeInBits();
3733 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3734 assert(C->getAPIntValue().getBitWidth() == 8);
3735 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3737 return DAG.getConstant(Val, VT);
3738 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3741 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3743 // Use a multiplication with 0x010101... to extend the input to the
3745 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3746 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3752 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3753 /// used when a memcpy is turned into a memset when the source is a constant
3755 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3756 const TargetLowering &TLI, StringRef Str) {
3757 // Handle vector with all elements zero.
3760 return DAG.getConstant(0, VT);
3761 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3762 return DAG.getConstantFP(0.0, VT);
3763 else if (VT.isVector()) {
3764 unsigned NumElts = VT.getVectorNumElements();
3765 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3766 return DAG.getNode(ISD::BITCAST, dl, VT,
3767 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3770 llvm_unreachable("Expected type!");
3773 assert(!VT.isVector() && "Can't handle vector type here!");
3774 unsigned NumVTBits = VT.getSizeInBits();
3775 unsigned NumVTBytes = NumVTBits / 8;
3776 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3778 APInt Val(NumVTBits, 0);
3779 if (TLI.isLittleEndian()) {
3780 for (unsigned i = 0; i != NumBytes; ++i)
3781 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3783 for (unsigned i = 0; i != NumBytes; ++i)
3784 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3787 // If the "cost" of materializing the integer immediate is less than the cost
3788 // of a load, then it is cost effective to turn the load into the immediate.
3789 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3790 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3791 return DAG.getConstant(Val, VT);
3792 return SDValue(nullptr, 0);
3795 /// getMemBasePlusOffset - Returns base and offset node for the
3797 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3798 SelectionDAG &DAG) {
3799 EVT VT = Base.getValueType();
3800 return DAG.getNode(ISD::ADD, dl,
3801 VT, Base, DAG.getConstant(Offset, VT));
3804 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3806 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3807 unsigned SrcDelta = 0;
3808 GlobalAddressSDNode *G = nullptr;
3809 if (Src.getOpcode() == ISD::GlobalAddress)
3810 G = cast<GlobalAddressSDNode>(Src);
3811 else if (Src.getOpcode() == ISD::ADD &&
3812 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3813 Src.getOperand(1).getOpcode() == ISD::Constant) {
3814 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3815 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3820 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3823 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3824 /// to replace the memset / memcpy. Return true if the number of memory ops
3825 /// is below the threshold. It returns the types of the sequence of
3826 /// memory ops to perform memset / memcpy by reference.
3827 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3828 unsigned Limit, uint64_t Size,
3829 unsigned DstAlign, unsigned SrcAlign,
3835 const TargetLowering &TLI) {
3836 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3837 "Expecting memcpy / memset source to meet alignment requirement!");
3838 // If 'SrcAlign' is zero, that means the memory operation does not need to
3839 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3840 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3841 // is the specified alignment of the memory operation. If it is zero, that
3842 // means it's possible to change the alignment of the destination.
3843 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3844 // not need to be loaded.
3845 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3846 IsMemset, ZeroMemset, MemcpyStrSrc,
3847 DAG.getMachineFunction());
3849 if (VT == MVT::Other) {
3851 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3852 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3853 VT = TLI.getPointerTy();
3855 switch (DstAlign & 7) {
3856 case 0: VT = MVT::i64; break;
3857 case 4: VT = MVT::i32; break;
3858 case 2: VT = MVT::i16; break;
3859 default: VT = MVT::i8; break;
3864 while (!TLI.isTypeLegal(LVT))
3865 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3866 assert(LVT.isInteger());
3872 unsigned NumMemOps = 0;
3874 unsigned VTSize = VT.getSizeInBits() / 8;
3875 while (VTSize > Size) {
3876 // For now, only use non-vector load / store's for the left-over pieces.
3881 if (VT.isVector() || VT.isFloatingPoint()) {
3882 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3883 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3884 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3886 else if (NewVT == MVT::i64 &&
3887 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3888 TLI.isSafeMemOpType(MVT::f64)) {
3889 // i64 is usually not legal on 32-bit targets, but f64 may be.
3897 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3898 if (NewVT == MVT::i8)
3900 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3902 NewVTSize = NewVT.getSizeInBits() / 8;
3904 // If the new VT cannot cover all of the remaining bits, then consider
3905 // issuing a (or a pair of) unaligned and overlapping load / store.
3906 // FIXME: Only does this for 64-bit or more since we don't have proper
3907 // cost model for unaligned load / store.
3910 if (NumMemOps && AllowOverlap &&
3911 VTSize >= 8 && NewVTSize < Size &&
3912 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3920 if (++NumMemOps > Limit)
3923 MemOps.push_back(VT);
3930 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3931 SDValue Chain, SDValue Dst,
3932 SDValue Src, uint64_t Size,
3933 unsigned Align, bool isVol,
3935 MachinePointerInfo DstPtrInfo,
3936 MachinePointerInfo SrcPtrInfo) {
3937 // Turn a memcpy of undef to nop.
3938 if (Src.getOpcode() == ISD::UNDEF)
3941 // Expand memcpy to a series of load and store ops if the size operand falls
3942 // below a certain threshold.
3943 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3944 // rather than maybe a humongous number of loads and stores.
3945 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3946 std::vector<EVT> MemOps;
3947 bool DstAlignCanChange = false;
3948 MachineFunction &MF = DAG.getMachineFunction();
3949 MachineFrameInfo *MFI = MF.getFrameInfo();
3951 MF.getFunction()->getAttributes().
3952 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3953 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3954 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3955 DstAlignCanChange = true;
3956 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3957 if (Align > SrcAlign)
3960 bool CopyFromStr = isMemSrcFromString(Src, Str);
3961 bool isZeroStr = CopyFromStr && Str.empty();
3962 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3964 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3965 (DstAlignCanChange ? 0 : Align),
3966 (isZeroStr ? 0 : SrcAlign),
3967 false, false, CopyFromStr, true, DAG, TLI))
3970 if (DstAlignCanChange) {
3971 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3972 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3974 // Don't promote to an alignment that would require dynamic stack
3976 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3977 if (!TRI->needsStackRealignment(MF))
3978 while (NewAlign > Align &&
3979 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3982 if (NewAlign > Align) {
3983 // Give the stack frame object a larger alignment if needed.
3984 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3985 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3990 SmallVector<SDValue, 8> OutChains;
3991 unsigned NumMemOps = MemOps.size();
3992 uint64_t SrcOff = 0, DstOff = 0;
3993 for (unsigned i = 0; i != NumMemOps; ++i) {
3995 unsigned VTSize = VT.getSizeInBits() / 8;
3996 SDValue Value, Store;
3998 if (VTSize > Size) {
3999 // Issuing an unaligned load / store pair that overlaps with the previous
4000 // pair. Adjust the offset accordingly.
4001 assert(i == NumMemOps-1 && i != 0);
4002 SrcOff -= VTSize - Size;
4003 DstOff -= VTSize - Size;
4007 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4008 // It's unlikely a store of a vector immediate can be done in a single
4009 // instruction. It would require a load from a constantpool first.
4010 // We only handle zero vectors here.
4011 // FIXME: Handle other cases where store of vector immediate is done in
4012 // a single instruction.
4013 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4014 if (Value.getNode())
4015 Store = DAG.getStore(Chain, dl, Value,
4016 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4017 DstPtrInfo.getWithOffset(DstOff), isVol,
4021 if (!Store.getNode()) {
4022 // The type might not be legal for the target. This should only happen
4023 // if the type is smaller than a legal type, as on PPC, so the right
4024 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4025 // to Load/Store if NVT==VT.
4026 // FIXME does the case above also need this?
4027 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4028 assert(NVT.bitsGE(VT));
4029 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4030 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4031 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4032 MinAlign(SrcAlign, SrcOff));
4033 Store = DAG.getTruncStore(Chain, dl, Value,
4034 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4035 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4038 OutChains.push_back(Store);
4044 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4047 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4048 SDValue Chain, SDValue Dst,
4049 SDValue Src, uint64_t Size,
4050 unsigned Align, bool isVol,
4052 MachinePointerInfo DstPtrInfo,
4053 MachinePointerInfo SrcPtrInfo) {
4054 // Turn a memmove of undef to nop.
4055 if (Src.getOpcode() == ISD::UNDEF)
4058 // Expand memmove to a series of load and store ops if the size operand falls
4059 // below a certain threshold.
4060 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4061 std::vector<EVT> MemOps;
4062 bool DstAlignCanChange = false;
4063 MachineFunction &MF = DAG.getMachineFunction();
4064 MachineFrameInfo *MFI = MF.getFrameInfo();
4065 bool OptSize = MF.getFunction()->getAttributes().
4066 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4067 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4068 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4069 DstAlignCanChange = true;
4070 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4071 if (Align > SrcAlign)
4073 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4075 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4076 (DstAlignCanChange ? 0 : Align), SrcAlign,
4077 false, false, false, false, DAG, TLI))
4080 if (DstAlignCanChange) {
4081 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4082 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4083 if (NewAlign > Align) {
4084 // Give the stack frame object a larger alignment if needed.
4085 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4086 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4091 uint64_t SrcOff = 0, DstOff = 0;
4092 SmallVector<SDValue, 8> LoadValues;
4093 SmallVector<SDValue, 8> LoadChains;
4094 SmallVector<SDValue, 8> OutChains;
4095 unsigned NumMemOps = MemOps.size();
4096 for (unsigned i = 0; i < NumMemOps; i++) {
4098 unsigned VTSize = VT.getSizeInBits() / 8;
4101 Value = DAG.getLoad(VT, dl, Chain,
4102 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4103 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4104 false, false, SrcAlign);
4105 LoadValues.push_back(Value);
4106 LoadChains.push_back(Value.getValue(1));
4109 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4111 for (unsigned i = 0; i < NumMemOps; i++) {
4113 unsigned VTSize = VT.getSizeInBits() / 8;
4116 Store = DAG.getStore(Chain, dl, LoadValues[i],
4117 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4118 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4119 OutChains.push_back(Store);
4123 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4126 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4129 /// \param DAG Selection DAG where lowered code is placed.
4130 /// \param dl Link to corresponding IR location.
4131 /// \param Chain Control flow dependency.
4132 /// \param Dst Pointer to destination memory location.
4133 /// \param Src Value of byte to write into the memory.
4134 /// \param Size Number of bytes to write.
4135 /// \param Align Alignment of the destination in bytes.
4136 /// \param isVol True if destination is volatile.
4137 /// \param DstPtrInfo IR information on the memory pointer.
4138 /// \returns New head in the control flow, if lowering was successful, empty
4139 /// SDValue otherwise.
4141 /// The function tries to replace 'llvm.memset' intrinsic with several store
4142 /// operations and value calculation code. This is usually profitable for small
4144 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4145 SDValue Chain, SDValue Dst,
4146 SDValue Src, uint64_t Size,
4147 unsigned Align, bool isVol,
4148 MachinePointerInfo DstPtrInfo) {
4149 // Turn a memset of undef to nop.
4150 if (Src.getOpcode() == ISD::UNDEF)
4153 // Expand memset to a series of load/store ops if the size operand
4154 // falls below a certain threshold.
4155 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4156 std::vector<EVT> MemOps;
4157 bool DstAlignCanChange = false;
4158 MachineFunction &MF = DAG.getMachineFunction();
4159 MachineFrameInfo *MFI = MF.getFrameInfo();
4160 bool OptSize = MF.getFunction()->getAttributes().
4161 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
4162 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4163 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4164 DstAlignCanChange = true;
4166 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4167 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4168 Size, (DstAlignCanChange ? 0 : Align), 0,
4169 true, IsZeroVal, false, true, DAG, TLI))
4172 if (DstAlignCanChange) {
4173 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4174 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4175 if (NewAlign > Align) {
4176 // Give the stack frame object a larger alignment if needed.
4177 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4178 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4183 SmallVector<SDValue, 8> OutChains;
4184 uint64_t DstOff = 0;
4185 unsigned NumMemOps = MemOps.size();
4187 // Find the largest store and generate the bit pattern for it.
4188 EVT LargestVT = MemOps[0];
4189 for (unsigned i = 1; i < NumMemOps; i++)
4190 if (MemOps[i].bitsGT(LargestVT))
4191 LargestVT = MemOps[i];
4192 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4194 for (unsigned i = 0; i < NumMemOps; i++) {
4196 unsigned VTSize = VT.getSizeInBits() / 8;
4197 if (VTSize > Size) {
4198 // Issuing an unaligned load / store pair that overlaps with the previous
4199 // pair. Adjust the offset accordingly.
4200 assert(i == NumMemOps-1 && i != 0);
4201 DstOff -= VTSize - Size;
4204 // If this store is smaller than the largest store see whether we can get
4205 // the smaller value for free with a truncate.
4206 SDValue Value = MemSetValue;
4207 if (VT.bitsLT(LargestVT)) {
4208 if (!LargestVT.isVector() && !VT.isVector() &&
4209 TLI.isTruncateFree(LargestVT, VT))
4210 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4212 Value = getMemsetValue(Src, VT, DAG, dl);
4214 assert(Value.getValueType() == VT && "Value with wrong type.");
4215 SDValue Store = DAG.getStore(Chain, dl, Value,
4216 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4217 DstPtrInfo.getWithOffset(DstOff),
4218 isVol, false, Align);
4219 OutChains.push_back(Store);
4220 DstOff += VT.getSizeInBits() / 8;
4224 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4227 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4228 SDValue Src, SDValue Size,
4229 unsigned Align, bool isVol, bool AlwaysInline,
4230 MachinePointerInfo DstPtrInfo,
4231 MachinePointerInfo SrcPtrInfo) {
4232 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4234 // Check to see if we should lower the memcpy to loads and stores first.
4235 // For cases within the target-specified limits, this is the best choice.
4236 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4238 // Memcpy with size zero? Just return the original chain.
4239 if (ConstantSize->isNullValue())
4242 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4243 ConstantSize->getZExtValue(),Align,
4244 isVol, false, DstPtrInfo, SrcPtrInfo);
4245 if (Result.getNode())
4249 // Then check to see if we should lower the memcpy with target-specific
4250 // code. If the target chooses to do this, this is the next best.
4252 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4253 isVol, AlwaysInline,
4254 DstPtrInfo, SrcPtrInfo);
4255 if (Result.getNode())
4258 // If we really need inline code and the target declined to provide it,
4259 // use a (potentially long) sequence of loads and stores.
4261 assert(ConstantSize && "AlwaysInline requires a constant size!");
4262 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4263 ConstantSize->getZExtValue(), Align, isVol,
4264 true, DstPtrInfo, SrcPtrInfo);
4267 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4268 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4269 // respect volatile, so they may do things like read or write memory
4270 // beyond the given memory regions. But fixing this isn't easy, and most
4271 // people don't care.
4273 const TargetLowering *TLI = TM.getTargetLowering();
4275 // Emit a library call.
4276 TargetLowering::ArgListTy Args;
4277 TargetLowering::ArgListEntry Entry;
4278 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4279 Entry.Node = Dst; Args.push_back(Entry);
4280 Entry.Node = Src; Args.push_back(Entry);
4281 Entry.Node = Size; Args.push_back(Entry);
4282 // FIXME: pass in SDLoc
4283 TargetLowering::CallLoweringInfo CLI(*this);
4284 CLI.setDebugLoc(dl).setChain(Chain)
4285 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4286 Type::getVoidTy(*getContext()),
4287 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4288 TLI->getPointerTy()), std::move(Args), 0)
4289 .setDiscardResult();
4290 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4292 return CallResult.second;
4295 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4296 SDValue Src, SDValue Size,
4297 unsigned Align, bool isVol,
4298 MachinePointerInfo DstPtrInfo,
4299 MachinePointerInfo SrcPtrInfo) {
4300 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4302 // Check to see if we should lower the memmove to loads and stores first.
4303 // For cases within the target-specified limits, this is the best choice.
4304 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4306 // Memmove with size zero? Just return the original chain.
4307 if (ConstantSize->isNullValue())
4311 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4312 ConstantSize->getZExtValue(), Align, isVol,
4313 false, DstPtrInfo, SrcPtrInfo);
4314 if (Result.getNode())
4318 // Then check to see if we should lower the memmove with target-specific
4319 // code. If the target chooses to do this, this is the next best.
4321 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4322 DstPtrInfo, SrcPtrInfo);
4323 if (Result.getNode())
4326 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4327 // not be safe. See memcpy above for more details.
4329 const TargetLowering *TLI = TM.getTargetLowering();
4331 // Emit a library call.
4332 TargetLowering::ArgListTy Args;
4333 TargetLowering::ArgListEntry Entry;
4334 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4335 Entry.Node = Dst; Args.push_back(Entry);
4336 Entry.Node = Src; Args.push_back(Entry);
4337 Entry.Node = Size; Args.push_back(Entry);
4338 // FIXME: pass in SDLoc
4339 TargetLowering::CallLoweringInfo CLI(*this);
4340 CLI.setDebugLoc(dl).setChain(Chain)
4341 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4342 Type::getVoidTy(*getContext()),
4343 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4344 TLI->getPointerTy()), std::move(Args), 0)
4345 .setDiscardResult();
4346 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4348 return CallResult.second;
4351 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4352 SDValue Src, SDValue Size,
4353 unsigned Align, bool isVol,
4354 MachinePointerInfo DstPtrInfo) {
4355 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4357 // Check to see if we should lower the memset to stores first.
4358 // For cases within the target-specified limits, this is the best choice.
4359 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4361 // Memset with size zero? Just return the original chain.
4362 if (ConstantSize->isNullValue())
4366 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4367 Align, isVol, DstPtrInfo);
4369 if (Result.getNode())
4373 // Then check to see if we should lower the memset with target-specific
4374 // code. If the target chooses to do this, this is the next best.
4376 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4378 if (Result.getNode())
4381 // Emit a library call.
4382 const TargetLowering *TLI = TM.getTargetLowering();
4383 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4384 TargetLowering::ArgListTy Args;
4385 TargetLowering::ArgListEntry Entry;
4386 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4387 Args.push_back(Entry);
4388 // Extend or truncate the argument to be an i32 value for the call.
4389 if (Src.getValueType().bitsGT(MVT::i32))
4390 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4392 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4394 Entry.Ty = Type::getInt32Ty(*getContext());
4395 Entry.isSExt = true;
4396 Args.push_back(Entry);
4398 Entry.Ty = IntPtrTy;
4399 Entry.isSExt = false;
4400 Args.push_back(Entry);
4402 // FIXME: pass in SDLoc
4403 TargetLowering::CallLoweringInfo CLI(*this);
4404 CLI.setDebugLoc(dl).setChain(Chain)
4405 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4406 Type::getVoidTy(*getContext()),
4407 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4408 TLI->getPointerTy()), std::move(Args), 0)
4409 .setDiscardResult();
4411 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4412 return CallResult.second;
4415 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4416 SDVTList VTList, ArrayRef<SDValue> Ops,
4417 MachineMemOperand *MMO,
4418 AtomicOrdering SuccessOrdering,
4419 AtomicOrdering FailureOrdering,
4420 SynchronizationScope SynchScope) {
4421 FoldingSetNodeID ID;
4422 ID.AddInteger(MemVT.getRawBits());
4423 AddNodeIDNode(ID, Opcode, VTList, Ops);
4424 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4426 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4427 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4428 return SDValue(E, 0);
4431 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4432 // SDNode doesn't have access to it. This memory will be "leaked" when
4433 // the node is deallocated, but recovered when the allocator is released.
4434 // If the number of operands is less than 5 we use AtomicSDNode's internal
4436 unsigned NumOps = Ops.size();
4437 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4440 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4441 dl.getDebugLoc(), VTList, MemVT,
4442 Ops.data(), DynOps, NumOps, MMO,
4443 SuccessOrdering, FailureOrdering,
4445 CSEMap.InsertNode(N, IP);
4446 AllNodes.push_back(N);
4447 return SDValue(N, 0);
4450 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4451 SDVTList VTList, ArrayRef<SDValue> Ops,
4452 MachineMemOperand *MMO,
4453 AtomicOrdering Ordering,
4454 SynchronizationScope SynchScope) {
4455 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4456 Ordering, SynchScope);
4459 SDValue SelectionDAG::getAtomicCmpSwap(
4460 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4461 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4462 unsigned Alignment, AtomicOrdering SuccessOrdering,
4463 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4464 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4465 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4466 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4468 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4469 Alignment = getEVTAlignment(MemVT);
4471 MachineFunction &MF = getMachineFunction();
4473 // FIXME: Volatile isn't really correct; we should keep track of atomic
4474 // orderings in the memoperand.
4475 unsigned Flags = MachineMemOperand::MOVolatile;
4476 Flags |= MachineMemOperand::MOLoad;
4477 Flags |= MachineMemOperand::MOStore;
4479 MachineMemOperand *MMO =
4480 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4482 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4483 SuccessOrdering, FailureOrdering, SynchScope);
4486 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4487 SDVTList VTs, SDValue Chain, SDValue Ptr,
4488 SDValue Cmp, SDValue Swp,
4489 MachineMemOperand *MMO,
4490 AtomicOrdering SuccessOrdering,
4491 AtomicOrdering FailureOrdering,
4492 SynchronizationScope SynchScope) {
4493 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4494 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4495 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4497 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4498 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4499 SuccessOrdering, FailureOrdering, SynchScope);
4502 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4504 SDValue Ptr, SDValue Val,
4505 const Value* PtrVal,
4507 AtomicOrdering Ordering,
4508 SynchronizationScope SynchScope) {
4509 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4510 Alignment = getEVTAlignment(MemVT);
4512 MachineFunction &MF = getMachineFunction();
4513 // An atomic store does not load. An atomic load does not store.
4514 // (An atomicrmw obviously both loads and stores.)
4515 // For now, atomics are considered to be volatile always, and they are
4517 // FIXME: Volatile isn't really correct; we should keep track of atomic
4518 // orderings in the memoperand.
4519 unsigned Flags = MachineMemOperand::MOVolatile;
4520 if (Opcode != ISD::ATOMIC_STORE)
4521 Flags |= MachineMemOperand::MOLoad;
4522 if (Opcode != ISD::ATOMIC_LOAD)
4523 Flags |= MachineMemOperand::MOStore;
4525 MachineMemOperand *MMO =
4526 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4527 MemVT.getStoreSize(), Alignment);
4529 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4530 Ordering, SynchScope);
4533 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4535 SDValue Ptr, SDValue Val,
4536 MachineMemOperand *MMO,
4537 AtomicOrdering Ordering,
4538 SynchronizationScope SynchScope) {
4539 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4540 Opcode == ISD::ATOMIC_LOAD_SUB ||
4541 Opcode == ISD::ATOMIC_LOAD_AND ||
4542 Opcode == ISD::ATOMIC_LOAD_OR ||
4543 Opcode == ISD::ATOMIC_LOAD_XOR ||
4544 Opcode == ISD::ATOMIC_LOAD_NAND ||
4545 Opcode == ISD::ATOMIC_LOAD_MIN ||
4546 Opcode == ISD::ATOMIC_LOAD_MAX ||
4547 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4548 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4549 Opcode == ISD::ATOMIC_SWAP ||
4550 Opcode == ISD::ATOMIC_STORE) &&
4551 "Invalid Atomic Op");
4553 EVT VT = Val.getValueType();
4555 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4556 getVTList(VT, MVT::Other);
4557 SDValue Ops[] = {Chain, Ptr, Val};
4558 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4561 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4562 EVT VT, SDValue Chain,
4564 MachineMemOperand *MMO,
4565 AtomicOrdering Ordering,
4566 SynchronizationScope SynchScope) {
4567 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4569 SDVTList VTs = getVTList(VT, MVT::Other);
4570 SDValue Ops[] = {Chain, Ptr};
4571 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4574 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4575 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4576 if (Ops.size() == 1)
4579 SmallVector<EVT, 4> VTs;
4580 VTs.reserve(Ops.size());
4581 for (unsigned i = 0; i < Ops.size(); ++i)
4582 VTs.push_back(Ops[i].getValueType());
4583 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4587 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4588 ArrayRef<SDValue> Ops,
4589 EVT MemVT, MachinePointerInfo PtrInfo,
4590 unsigned Align, bool Vol,
4591 bool ReadMem, bool WriteMem) {
4592 if (Align == 0) // Ensure that codegen never sees alignment 0
4593 Align = getEVTAlignment(MemVT);
4595 MachineFunction &MF = getMachineFunction();
4598 Flags |= MachineMemOperand::MOStore;
4600 Flags |= MachineMemOperand::MOLoad;
4602 Flags |= MachineMemOperand::MOVolatile;
4603 MachineMemOperand *MMO =
4604 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4606 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4610 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4611 ArrayRef<SDValue> Ops, EVT MemVT,
4612 MachineMemOperand *MMO) {
4613 assert((Opcode == ISD::INTRINSIC_VOID ||
4614 Opcode == ISD::INTRINSIC_W_CHAIN ||
4615 Opcode == ISD::PREFETCH ||
4616 Opcode == ISD::LIFETIME_START ||
4617 Opcode == ISD::LIFETIME_END ||
4618 (Opcode <= INT_MAX &&
4619 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4620 "Opcode is not a memory-accessing opcode!");
4622 // Memoize the node unless it returns a flag.
4623 MemIntrinsicSDNode *N;
4624 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4625 FoldingSetNodeID ID;
4626 AddNodeIDNode(ID, Opcode, VTList, Ops);
4627 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4629 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4630 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4631 return SDValue(E, 0);
4634 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4635 dl.getDebugLoc(), VTList, Ops,
4637 CSEMap.InsertNode(N, IP);
4639 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4640 dl.getDebugLoc(), VTList, Ops,
4643 AllNodes.push_back(N);
4644 return SDValue(N, 0);
4647 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4648 /// MachinePointerInfo record from it. This is particularly useful because the
4649 /// code generator has many cases where it doesn't bother passing in a
4650 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4651 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4652 // If this is FI+Offset, we can model it.
4653 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4654 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4656 // If this is (FI+Offset1)+Offset2, we can model it.
4657 if (Ptr.getOpcode() != ISD::ADD ||
4658 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4659 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4660 return MachinePointerInfo();
4662 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4663 return MachinePointerInfo::getFixedStack(FI, Offset+
4664 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4667 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4668 /// MachinePointerInfo record from it. This is particularly useful because the
4669 /// code generator has many cases where it doesn't bother passing in a
4670 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4671 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4672 // If the 'Offset' value isn't a constant, we can't handle this.
4673 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4674 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4675 if (OffsetOp.getOpcode() == ISD::UNDEF)
4676 return InferPointerInfo(Ptr);
4677 return MachinePointerInfo();
4682 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4683 EVT VT, SDLoc dl, SDValue Chain,
4684 SDValue Ptr, SDValue Offset,
4685 MachinePointerInfo PtrInfo, EVT MemVT,
4686 bool isVolatile, bool isNonTemporal, bool isInvariant,
4687 unsigned Alignment, const MDNode *TBAAInfo,
4688 const MDNode *Ranges) {
4689 assert(Chain.getValueType() == MVT::Other &&
4690 "Invalid chain type");
4691 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4692 Alignment = getEVTAlignment(VT);
4694 unsigned Flags = MachineMemOperand::MOLoad;
4696 Flags |= MachineMemOperand::MOVolatile;
4698 Flags |= MachineMemOperand::MONonTemporal;
4700 Flags |= MachineMemOperand::MOInvariant;
4702 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4704 if (PtrInfo.V.isNull())
4705 PtrInfo = InferPointerInfo(Ptr, Offset);
4707 MachineFunction &MF = getMachineFunction();
4708 MachineMemOperand *MMO =
4709 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4711 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4715 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4716 EVT VT, SDLoc dl, SDValue Chain,
4717 SDValue Ptr, SDValue Offset, EVT MemVT,
4718 MachineMemOperand *MMO) {
4720 ExtType = ISD::NON_EXTLOAD;
4721 } else if (ExtType == ISD::NON_EXTLOAD) {
4722 assert(VT == MemVT && "Non-extending load from different memory type!");
4725 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4726 "Should only be an extending load, not truncating!");
4727 assert(VT.isInteger() == MemVT.isInteger() &&
4728 "Cannot convert from FP to Int or Int -> FP!");
4729 assert(VT.isVector() == MemVT.isVector() &&
4730 "Cannot use trunc store to convert to or from a vector!");
4731 assert((!VT.isVector() ||
4732 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4733 "Cannot use trunc store to change the number of vector elements!");
4736 bool Indexed = AM != ISD::UNINDEXED;
4737 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4738 "Unindexed load with an offset!");
4740 SDVTList VTs = Indexed ?
4741 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4742 SDValue Ops[] = { Chain, Ptr, Offset };
4743 FoldingSetNodeID ID;
4744 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4745 ID.AddInteger(MemVT.getRawBits());
4746 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4747 MMO->isNonTemporal(),
4748 MMO->isInvariant()));
4749 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4751 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4752 cast<LoadSDNode>(E)->refineAlignment(MMO);
4753 return SDValue(E, 0);
4755 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4756 dl.getDebugLoc(), VTs, AM, ExtType,
4758 CSEMap.InsertNode(N, IP);
4759 AllNodes.push_back(N);
4760 return SDValue(N, 0);
4763 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4764 SDValue Chain, SDValue Ptr,
4765 MachinePointerInfo PtrInfo,
4766 bool isVolatile, bool isNonTemporal,
4767 bool isInvariant, unsigned Alignment,
4768 const MDNode *TBAAInfo,
4769 const MDNode *Ranges) {
4770 SDValue Undef = getUNDEF(Ptr.getValueType());
4771 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4772 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4776 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4777 SDValue Chain, SDValue Ptr,
4778 MachineMemOperand *MMO) {
4779 SDValue Undef = getUNDEF(Ptr.getValueType());
4780 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4784 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4785 SDValue Chain, SDValue Ptr,
4786 MachinePointerInfo PtrInfo, EVT MemVT,
4787 bool isVolatile, bool isNonTemporal,
4788 unsigned Alignment, const MDNode *TBAAInfo) {
4789 SDValue Undef = getUNDEF(Ptr.getValueType());
4790 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4791 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4796 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4797 SDValue Chain, SDValue Ptr, EVT MemVT,
4798 MachineMemOperand *MMO) {
4799 SDValue Undef = getUNDEF(Ptr.getValueType());
4800 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4805 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4806 SDValue Offset, ISD::MemIndexedMode AM) {
4807 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4808 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4809 "Load is already a indexed load!");
4810 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4811 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4812 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4813 false, LD->getAlignment());
4816 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4817 SDValue Ptr, MachinePointerInfo PtrInfo,
4818 bool isVolatile, bool isNonTemporal,
4819 unsigned Alignment, const MDNode *TBAAInfo) {
4820 assert(Chain.getValueType() == MVT::Other &&
4821 "Invalid chain type");
4822 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4823 Alignment = getEVTAlignment(Val.getValueType());
4825 unsigned Flags = MachineMemOperand::MOStore;
4827 Flags |= MachineMemOperand::MOVolatile;
4829 Flags |= MachineMemOperand::MONonTemporal;
4831 if (PtrInfo.V.isNull())
4832 PtrInfo = InferPointerInfo(Ptr);
4834 MachineFunction &MF = getMachineFunction();
4835 MachineMemOperand *MMO =
4836 MF.getMachineMemOperand(PtrInfo, Flags,
4837 Val.getValueType().getStoreSize(), Alignment,
4840 return getStore(Chain, dl, Val, Ptr, MMO);
4843 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4844 SDValue Ptr, MachineMemOperand *MMO) {
4845 assert(Chain.getValueType() == MVT::Other &&
4846 "Invalid chain type");
4847 EVT VT = Val.getValueType();
4848 SDVTList VTs = getVTList(MVT::Other);
4849 SDValue Undef = getUNDEF(Ptr.getValueType());
4850 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4851 FoldingSetNodeID ID;
4852 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4853 ID.AddInteger(VT.getRawBits());
4854 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4855 MMO->isNonTemporal(), MMO->isInvariant()));
4856 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4858 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4859 cast<StoreSDNode>(E)->refineAlignment(MMO);
4860 return SDValue(E, 0);
4862 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4863 dl.getDebugLoc(), VTs,
4864 ISD::UNINDEXED, false, VT, MMO);
4865 CSEMap.InsertNode(N, IP);
4866 AllNodes.push_back(N);
4867 return SDValue(N, 0);
4870 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4871 SDValue Ptr, MachinePointerInfo PtrInfo,
4872 EVT SVT,bool isVolatile, bool isNonTemporal,
4874 const MDNode *TBAAInfo) {
4875 assert(Chain.getValueType() == MVT::Other &&
4876 "Invalid chain type");
4877 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4878 Alignment = getEVTAlignment(SVT);
4880 unsigned Flags = MachineMemOperand::MOStore;
4882 Flags |= MachineMemOperand::MOVolatile;
4884 Flags |= MachineMemOperand::MONonTemporal;
4886 if (PtrInfo.V.isNull())
4887 PtrInfo = InferPointerInfo(Ptr);
4889 MachineFunction &MF = getMachineFunction();
4890 MachineMemOperand *MMO =
4891 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4894 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4897 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4898 SDValue Ptr, EVT SVT,
4899 MachineMemOperand *MMO) {
4900 EVT VT = Val.getValueType();
4902 assert(Chain.getValueType() == MVT::Other &&
4903 "Invalid chain type");
4905 return getStore(Chain, dl, Val, Ptr, MMO);
4907 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4908 "Should only be a truncating store, not extending!");
4909 assert(VT.isInteger() == SVT.isInteger() &&
4910 "Can't do FP-INT conversion!");
4911 assert(VT.isVector() == SVT.isVector() &&
4912 "Cannot use trunc store to convert to or from a vector!");
4913 assert((!VT.isVector() ||
4914 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4915 "Cannot use trunc store to change the number of vector elements!");
4917 SDVTList VTs = getVTList(MVT::Other);
4918 SDValue Undef = getUNDEF(Ptr.getValueType());
4919 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4920 FoldingSetNodeID ID;
4921 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4922 ID.AddInteger(SVT.getRawBits());
4923 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4924 MMO->isNonTemporal(), MMO->isInvariant()));
4925 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4927 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4928 cast<StoreSDNode>(E)->refineAlignment(MMO);
4929 return SDValue(E, 0);
4931 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4932 dl.getDebugLoc(), VTs,
4933 ISD::UNINDEXED, true, SVT, MMO);
4934 CSEMap.InsertNode(N, IP);
4935 AllNodes.push_back(N);
4936 return SDValue(N, 0);
4940 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4941 SDValue Offset, ISD::MemIndexedMode AM) {
4942 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4943 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4944 "Store is already a indexed store!");
4945 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4946 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4947 FoldingSetNodeID ID;
4948 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4949 ID.AddInteger(ST->getMemoryVT().getRawBits());
4950 ID.AddInteger(ST->getRawSubclassData());
4951 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4953 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4954 return SDValue(E, 0);
4956 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4957 dl.getDebugLoc(), VTs, AM,
4958 ST->isTruncatingStore(),
4960 ST->getMemOperand());
4961 CSEMap.InsertNode(N, IP);
4962 AllNodes.push_back(N);
4963 return SDValue(N, 0);
4966 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4967 SDValue Chain, SDValue Ptr,
4970 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4971 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4974 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4975 ArrayRef<SDUse> Ops) {
4976 switch (Ops.size()) {
4977 case 0: return getNode(Opcode, DL, VT);
4978 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4979 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4980 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4984 // Copy from an SDUse array into an SDValue array for use with
4985 // the regular getNode logic.
4986 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4987 return getNode(Opcode, DL, VT, NewOps);
4990 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4991 ArrayRef<SDValue> Ops) {
4992 unsigned NumOps = Ops.size();
4994 case 0: return getNode(Opcode, DL, VT);
4995 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4996 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4997 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5003 case ISD::SELECT_CC: {
5004 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5005 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5006 "LHS and RHS of condition must have same type!");
5007 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5008 "True and False arms of SelectCC must have same type!");
5009 assert(Ops[2].getValueType() == VT &&
5010 "select_cc node must be of same type as true and false value!");
5014 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5015 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5016 "LHS/RHS of comparison should match types!");
5023 SDVTList VTs = getVTList(VT);
5025 if (VT != MVT::Glue) {
5026 FoldingSetNodeID ID;
5027 AddNodeIDNode(ID, Opcode, VTs, Ops);
5030 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5031 return SDValue(E, 0);
5033 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5035 CSEMap.InsertNode(N, IP);
5037 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5041 AllNodes.push_back(N);
5045 return SDValue(N, 0);
5048 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5049 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5050 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5053 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5054 ArrayRef<SDValue> Ops) {
5055 if (VTList.NumVTs == 1)
5056 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5060 // FIXME: figure out how to safely handle things like
5061 // int foo(int x) { return 1 << (x & 255); }
5062 // int bar() { return foo(256); }
5063 case ISD::SRA_PARTS:
5064 case ISD::SRL_PARTS:
5065 case ISD::SHL_PARTS:
5066 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5067 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5068 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5069 else if (N3.getOpcode() == ISD::AND)
5070 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5071 // If the and is only masking out bits that cannot effect the shift,
5072 // eliminate the and.
5073 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5074 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5075 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5081 // Memoize the node unless it returns a flag.
5083 unsigned NumOps = Ops.size();
5084 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5085 FoldingSetNodeID ID;
5086 AddNodeIDNode(ID, Opcode, VTList, Ops);
5088 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5089 return SDValue(E, 0);
5092 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5093 DL.getDebugLoc(), VTList, Ops[0]);
5094 } else if (NumOps == 2) {
5095 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5096 DL.getDebugLoc(), VTList, Ops[0],
5098 } else if (NumOps == 3) {
5099 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5100 DL.getDebugLoc(), VTList, Ops[0],
5103 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5106 CSEMap.InsertNode(N, IP);
5109 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5110 DL.getDebugLoc(), VTList, Ops[0]);
5111 } else if (NumOps == 2) {
5112 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5113 DL.getDebugLoc(), VTList, Ops[0],
5115 } else if (NumOps == 3) {
5116 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5117 DL.getDebugLoc(), VTList, Ops[0],
5120 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5124 AllNodes.push_back(N);
5128 return SDValue(N, 0);
5131 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5132 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
5135 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5137 SDValue Ops[] = { N1 };
5138 return getNode(Opcode, DL, VTList, Ops);
5141 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5142 SDValue N1, SDValue N2) {
5143 SDValue Ops[] = { N1, N2 };
5144 return getNode(Opcode, DL, VTList, Ops);
5147 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5148 SDValue N1, SDValue N2, SDValue N3) {
5149 SDValue Ops[] = { N1, N2, N3 };
5150 return getNode(Opcode, DL, VTList, Ops);
5153 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5154 SDValue N1, SDValue N2, SDValue N3,
5156 SDValue Ops[] = { N1, N2, N3, N4 };
5157 return getNode(Opcode, DL, VTList, Ops);
5160 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5161 SDValue N1, SDValue N2, SDValue N3,
5162 SDValue N4, SDValue N5) {
5163 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5164 return getNode(Opcode, DL, VTList, Ops);
5167 SDVTList SelectionDAG::getVTList(EVT VT) {
5168 return makeVTList(SDNode::getValueTypeList(VT), 1);
5171 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5172 FoldingSetNodeID ID;
5174 ID.AddInteger(VT1.getRawBits());
5175 ID.AddInteger(VT2.getRawBits());
5178 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5180 EVT *Array = Allocator.Allocate<EVT>(2);
5183 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5184 VTListMap.InsertNode(Result, IP);
5186 return Result->getSDVTList();
5189 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5190 FoldingSetNodeID ID;
5192 ID.AddInteger(VT1.getRawBits());
5193 ID.AddInteger(VT2.getRawBits());
5194 ID.AddInteger(VT3.getRawBits());
5197 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5199 EVT *Array = Allocator.Allocate<EVT>(3);
5203 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5204 VTListMap.InsertNode(Result, IP);
5206 return Result->getSDVTList();
5209 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5210 FoldingSetNodeID ID;
5212 ID.AddInteger(VT1.getRawBits());
5213 ID.AddInteger(VT2.getRawBits());
5214 ID.AddInteger(VT3.getRawBits());
5215 ID.AddInteger(VT4.getRawBits());
5218 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5220 EVT *Array = Allocator.Allocate<EVT>(4);
5225 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5226 VTListMap.InsertNode(Result, IP);
5228 return Result->getSDVTList();
5231 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5232 unsigned NumVTs = VTs.size();
5233 FoldingSetNodeID ID;
5234 ID.AddInteger(NumVTs);
5235 for (unsigned index = 0; index < NumVTs; index++) {
5236 ID.AddInteger(VTs[index].getRawBits());
5240 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5242 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5243 std::copy(VTs.begin(), VTs.end(), Array);
5244 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5245 VTListMap.InsertNode(Result, IP);
5247 return Result->getSDVTList();
5251 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5252 /// specified operands. If the resultant node already exists in the DAG,
5253 /// this does not modify the specified node, instead it returns the node that
5254 /// already exists. If the resultant node does not exist in the DAG, the
5255 /// input node is returned. As a degenerate case, if you specify the same
5256 /// input operands as the node already has, the input node is returned.
5257 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5258 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5260 // Check to see if there is no change.
5261 if (Op == N->getOperand(0)) return N;
5263 // See if the modified node already exists.
5264 void *InsertPos = nullptr;
5265 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5268 // Nope it doesn't. Remove the node from its current place in the maps.
5270 if (!RemoveNodeFromCSEMaps(N))
5271 InsertPos = nullptr;
5273 // Now we update the operands.
5274 N->OperandList[0].set(Op);
5276 // If this gets put into a CSE map, add it.
5277 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5281 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5282 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5284 // Check to see if there is no change.
5285 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5286 return N; // No operands changed, just return the input node.
5288 // See if the modified node already exists.
5289 void *InsertPos = nullptr;
5290 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5293 // Nope it doesn't. Remove the node from its current place in the maps.
5295 if (!RemoveNodeFromCSEMaps(N))
5296 InsertPos = nullptr;
5298 // Now we update the operands.
5299 if (N->OperandList[0] != Op1)
5300 N->OperandList[0].set(Op1);
5301 if (N->OperandList[1] != Op2)
5302 N->OperandList[1].set(Op2);
5304 // If this gets put into a CSE map, add it.
5305 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5309 SDNode *SelectionDAG::
5310 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5311 SDValue Ops[] = { Op1, Op2, Op3 };
5312 return UpdateNodeOperands(N, Ops);
5315 SDNode *SelectionDAG::
5316 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5317 SDValue Op3, SDValue Op4) {
5318 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5319 return UpdateNodeOperands(N, Ops);
5322 SDNode *SelectionDAG::
5323 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5324 SDValue Op3, SDValue Op4, SDValue Op5) {
5325 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5326 return UpdateNodeOperands(N, Ops);
5329 SDNode *SelectionDAG::
5330 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5331 unsigned NumOps = Ops.size();
5332 assert(N->getNumOperands() == NumOps &&
5333 "Update with wrong number of operands");
5335 // Check to see if there is no change.
5336 bool AnyChange = false;
5337 for (unsigned i = 0; i != NumOps; ++i) {
5338 if (Ops[i] != N->getOperand(i)) {
5344 // No operands changed, just return the input node.
5345 if (!AnyChange) return N;
5347 // See if the modified node already exists.
5348 void *InsertPos = nullptr;
5349 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5352 // Nope it doesn't. Remove the node from its current place in the maps.
5354 if (!RemoveNodeFromCSEMaps(N))
5355 InsertPos = nullptr;
5357 // Now we update the operands.
5358 for (unsigned i = 0; i != NumOps; ++i)
5359 if (N->OperandList[i] != Ops[i])
5360 N->OperandList[i].set(Ops[i]);
5362 // If this gets put into a CSE map, add it.
5363 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5367 /// DropOperands - Release the operands and set this node to have
5369 void SDNode::DropOperands() {
5370 // Unlike the code in MorphNodeTo that does this, we don't need to
5371 // watch for dead nodes here.
5372 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5378 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5381 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5383 SDVTList VTs = getVTList(VT);
5384 return SelectNodeTo(N, MachineOpc, VTs, None);
5387 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5388 EVT VT, SDValue Op1) {
5389 SDVTList VTs = getVTList(VT);
5390 SDValue Ops[] = { Op1 };
5391 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5394 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5395 EVT VT, SDValue Op1,
5397 SDVTList VTs = getVTList(VT);
5398 SDValue Ops[] = { Op1, Op2 };
5399 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5402 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5403 EVT VT, SDValue Op1,
5404 SDValue Op2, SDValue Op3) {
5405 SDVTList VTs = getVTList(VT);
5406 SDValue Ops[] = { Op1, Op2, Op3 };
5407 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5410 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5411 EVT VT, ArrayRef<SDValue> Ops) {
5412 SDVTList VTs = getVTList(VT);
5413 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5416 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5417 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5418 SDVTList VTs = getVTList(VT1, VT2);
5419 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5422 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5424 SDVTList VTs = getVTList(VT1, VT2);
5425 return SelectNodeTo(N, MachineOpc, VTs, None);
5428 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5429 EVT VT1, EVT VT2, EVT VT3,
5430 ArrayRef<SDValue> Ops) {
5431 SDVTList VTs = getVTList(VT1, VT2, VT3);
5432 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5435 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5436 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5437 ArrayRef<SDValue> Ops) {
5438 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5439 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5442 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5445 SDVTList VTs = getVTList(VT1, VT2);
5446 SDValue Ops[] = { Op1 };
5447 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5450 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5452 SDValue Op1, SDValue Op2) {
5453 SDVTList VTs = getVTList(VT1, VT2);
5454 SDValue Ops[] = { Op1, Op2 };
5455 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5458 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5460 SDValue Op1, SDValue Op2,
5462 SDVTList VTs = getVTList(VT1, VT2);
5463 SDValue Ops[] = { Op1, Op2, Op3 };
5464 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5467 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5468 EVT VT1, EVT VT2, EVT VT3,
5469 SDValue Op1, SDValue Op2,
5471 SDVTList VTs = getVTList(VT1, VT2, VT3);
5472 SDValue Ops[] = { Op1, Op2, Op3 };
5473 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5476 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5477 SDVTList VTs,ArrayRef<SDValue> Ops) {
5478 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5479 // Reset the NodeID to -1.
5484 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5485 /// the line number information on the merged node since it is not possible to
5486 /// preserve the information that operation is associated with multiple lines.
5487 /// This will make the debugger working better at -O0, were there is a higher
5488 /// probability having other instructions associated with that line.
5490 /// For IROrder, we keep the smaller of the two
5491 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5492 DebugLoc NLoc = N->getDebugLoc();
5493 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5494 (OLoc.getDebugLoc() != NLoc)) {
5495 N->setDebugLoc(DebugLoc());
5497 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5498 N->setIROrder(Order);
5502 /// MorphNodeTo - This *mutates* the specified node to have the specified
5503 /// return type, opcode, and operands.
5505 /// Note that MorphNodeTo returns the resultant node. If there is already a
5506 /// node of the specified opcode and operands, it returns that node instead of
5507 /// the current one. Note that the SDLoc need not be the same.
5509 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5510 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5511 /// node, and because it doesn't require CSE recalculation for any of
5512 /// the node's users.
5514 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5515 SDVTList VTs, ArrayRef<SDValue> Ops) {
5516 unsigned NumOps = Ops.size();
5517 // If an identical node already exists, use it.
5519 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5520 FoldingSetNodeID ID;
5521 AddNodeIDNode(ID, Opc, VTs, Ops);
5522 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5523 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5526 if (!RemoveNodeFromCSEMaps(N))
5529 // Start the morphing.
5531 N->ValueList = VTs.VTs;
5532 N->NumValues = VTs.NumVTs;
5534 // Clear the operands list, updating used nodes to remove this from their
5535 // use list. Keep track of any operands that become dead as a result.
5536 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5537 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5539 SDNode *Used = Use.getNode();
5541 if (Used->use_empty())
5542 DeadNodeSet.insert(Used);
5545 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5546 // Initialize the memory references information.
5547 MN->setMemRefs(nullptr, nullptr);
5548 // If NumOps is larger than the # of operands we can have in a
5549 // MachineSDNode, reallocate the operand list.
5550 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5551 if (MN->OperandsNeedDelete)
5552 delete[] MN->OperandList;
5553 if (NumOps > array_lengthof(MN->LocalOperands))
5554 // We're creating a final node that will live unmorphed for the
5555 // remainder of the current SelectionDAG iteration, so we can allocate
5556 // the operands directly out of a pool with no recycling metadata.
5557 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5558 Ops.data(), NumOps);
5560 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5561 MN->OperandsNeedDelete = false;
5563 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5565 // If NumOps is larger than the # of operands we currently have, reallocate
5566 // the operand list.
5567 if (NumOps > N->NumOperands) {
5568 if (N->OperandsNeedDelete)
5569 delete[] N->OperandList;
5570 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5571 N->OperandsNeedDelete = true;
5573 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5576 // Delete any nodes that are still dead after adding the uses for the
5578 if (!DeadNodeSet.empty()) {
5579 SmallVector<SDNode *, 16> DeadNodes;
5580 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5581 E = DeadNodeSet.end(); I != E; ++I)
5582 if ((*I)->use_empty())
5583 DeadNodes.push_back(*I);
5584 RemoveDeadNodes(DeadNodes);
5588 CSEMap.InsertNode(N, IP); // Memoize the new node.
5593 /// getMachineNode - These are used for target selectors to create a new node
5594 /// with specified return type(s), MachineInstr opcode, and operands.
5596 /// Note that getMachineNode returns the resultant node. If there is already a
5597 /// node of the specified opcode and operands, it returns that node instead of
5598 /// the current one.
5600 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5601 SDVTList VTs = getVTList(VT);
5602 return getMachineNode(Opcode, dl, VTs, None);
5606 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5607 SDVTList VTs = getVTList(VT);
5608 SDValue Ops[] = { Op1 };
5609 return getMachineNode(Opcode, dl, VTs, Ops);
5613 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5614 SDValue Op1, SDValue Op2) {
5615 SDVTList VTs = getVTList(VT);
5616 SDValue Ops[] = { Op1, Op2 };
5617 return getMachineNode(Opcode, dl, VTs, Ops);
5621 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5622 SDValue Op1, SDValue Op2, SDValue Op3) {
5623 SDVTList VTs = getVTList(VT);
5624 SDValue Ops[] = { Op1, Op2, Op3 };
5625 return getMachineNode(Opcode, dl, VTs, Ops);
5629 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5630 ArrayRef<SDValue> Ops) {
5631 SDVTList VTs = getVTList(VT);
5632 return getMachineNode(Opcode, dl, VTs, Ops);
5636 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5637 SDVTList VTs = getVTList(VT1, VT2);
5638 return getMachineNode(Opcode, dl, VTs, None);
5642 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5643 EVT VT1, EVT VT2, SDValue Op1) {
5644 SDVTList VTs = getVTList(VT1, VT2);
5645 SDValue Ops[] = { Op1 };
5646 return getMachineNode(Opcode, dl, VTs, Ops);
5650 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5651 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5652 SDVTList VTs = getVTList(VT1, VT2);
5653 SDValue Ops[] = { Op1, Op2 };
5654 return getMachineNode(Opcode, dl, VTs, Ops);
5658 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5659 EVT VT1, EVT VT2, SDValue Op1,
5660 SDValue Op2, SDValue Op3) {
5661 SDVTList VTs = getVTList(VT1, VT2);
5662 SDValue Ops[] = { Op1, Op2, Op3 };
5663 return getMachineNode(Opcode, dl, VTs, Ops);
5667 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5669 ArrayRef<SDValue> Ops) {
5670 SDVTList VTs = getVTList(VT1, VT2);
5671 return getMachineNode(Opcode, dl, VTs, Ops);
5675 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5676 EVT VT1, EVT VT2, EVT VT3,
5677 SDValue Op1, SDValue Op2) {
5678 SDVTList VTs = getVTList(VT1, VT2, VT3);
5679 SDValue Ops[] = { Op1, Op2 };
5680 return getMachineNode(Opcode, dl, VTs, Ops);
5684 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5685 EVT VT1, EVT VT2, EVT VT3,
5686 SDValue Op1, SDValue Op2, SDValue Op3) {
5687 SDVTList VTs = getVTList(VT1, VT2, VT3);
5688 SDValue Ops[] = { Op1, Op2, Op3 };
5689 return getMachineNode(Opcode, dl, VTs, Ops);
5693 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5694 EVT VT1, EVT VT2, EVT VT3,
5695 ArrayRef<SDValue> Ops) {
5696 SDVTList VTs = getVTList(VT1, VT2, VT3);
5697 return getMachineNode(Opcode, dl, VTs, Ops);
5701 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5702 EVT VT2, EVT VT3, EVT VT4,
5703 ArrayRef<SDValue> Ops) {
5704 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5705 return getMachineNode(Opcode, dl, VTs, Ops);
5709 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5710 ArrayRef<EVT> ResultTys,
5711 ArrayRef<SDValue> Ops) {
5712 SDVTList VTs = getVTList(ResultTys);
5713 return getMachineNode(Opcode, dl, VTs, Ops);
5717 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5718 ArrayRef<SDValue> OpsArray) {
5719 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5722 const SDValue *Ops = OpsArray.data();
5723 unsigned NumOps = OpsArray.size();
5726 FoldingSetNodeID ID;
5727 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5729 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5730 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5734 // Allocate a new MachineSDNode.
5735 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5736 DL.getDebugLoc(), VTs);
5738 // Initialize the operands list.
5739 if (NumOps > array_lengthof(N->LocalOperands))
5740 // We're creating a final node that will live unmorphed for the
5741 // remainder of the current SelectionDAG iteration, so we can allocate
5742 // the operands directly out of a pool with no recycling metadata.
5743 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5746 N->InitOperands(N->LocalOperands, Ops, NumOps);
5747 N->OperandsNeedDelete = false;
5750 CSEMap.InsertNode(N, IP);
5752 AllNodes.push_back(N);
5754 VerifyMachineNode(N);
5759 /// getTargetExtractSubreg - A convenience function for creating
5760 /// TargetOpcode::EXTRACT_SUBREG nodes.
5762 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5764 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5765 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5766 VT, Operand, SRIdxVal);
5767 return SDValue(Subreg, 0);
5770 /// getTargetInsertSubreg - A convenience function for creating
5771 /// TargetOpcode::INSERT_SUBREG nodes.
5773 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5774 SDValue Operand, SDValue Subreg) {
5775 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5776 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5777 VT, Operand, Subreg, SRIdxVal);
5778 return SDValue(Result, 0);
5781 /// getNodeIfExists - Get the specified node if it's already available, or
5782 /// else return NULL.
5783 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5784 ArrayRef<SDValue> Ops, bool nuw, bool nsw,
5786 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5787 FoldingSetNodeID ID;
5788 AddNodeIDNode(ID, Opcode, VTList, Ops);
5789 if (isBinOpWithFlags(Opcode))
5790 AddBinaryNodeIDCustom(ID, nuw, nsw, exact);
5792 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5798 /// getDbgValue - Creates a SDDbgValue node.
5802 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5803 bool IsIndirect, uint64_t Off,
5804 DebugLoc DL, unsigned O) {
5805 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5810 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5812 DebugLoc DL, unsigned O) {
5813 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5818 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5819 DebugLoc DL, unsigned O) {
5820 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5825 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5826 /// pointed to by a use iterator is deleted, increment the use iterator
5827 /// so that it doesn't dangle.
5829 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5830 SDNode::use_iterator &UI;
5831 SDNode::use_iterator &UE;
5833 void NodeDeleted(SDNode *N, SDNode *E) override {
5834 // Increment the iterator as needed.
5835 while (UI != UE && N == *UI)
5840 RAUWUpdateListener(SelectionDAG &d,
5841 SDNode::use_iterator &ui,
5842 SDNode::use_iterator &ue)
5843 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5848 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5849 /// This can cause recursive merging of nodes in the DAG.
5851 /// This version assumes From has a single result value.
5853 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5854 SDNode *From = FromN.getNode();
5855 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5856 "Cannot replace with this method!");
5857 assert(From != To.getNode() && "Cannot replace uses of with self");
5859 // Iterate over all the existing uses of From. New uses will be added
5860 // to the beginning of the use list, which we avoid visiting.
5861 // This specifically avoids visiting uses of From that arise while the
5862 // replacement is happening, because any such uses would be the result
5863 // of CSE: If an existing node looks like From after one of its operands
5864 // is replaced by To, we don't want to replace of all its users with To
5865 // too. See PR3018 for more info.
5866 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5867 RAUWUpdateListener Listener(*this, UI, UE);
5871 // This node is about to morph, remove its old self from the CSE maps.
5872 RemoveNodeFromCSEMaps(User);
5874 // A user can appear in a use list multiple times, and when this
5875 // happens the uses are usually next to each other in the list.
5876 // To help reduce the number of CSE recomputations, process all
5877 // the uses of this user that we can find this way.
5879 SDUse &Use = UI.getUse();
5882 } while (UI != UE && *UI == User);
5884 // Now that we have modified User, add it back to the CSE maps. If it
5885 // already exists there, recursively merge the results together.
5886 AddModifiedNodeToCSEMaps(User);
5889 // If we just RAUW'd the root, take note.
5890 if (FromN == getRoot())
5894 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5895 /// This can cause recursive merging of nodes in the DAG.
5897 /// This version assumes that for each value of From, there is a
5898 /// corresponding value in To in the same position with the same type.
5900 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5902 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5903 assert((!From->hasAnyUseOfValue(i) ||
5904 From->getValueType(i) == To->getValueType(i)) &&
5905 "Cannot use this version of ReplaceAllUsesWith!");
5908 // Handle the trivial case.
5912 // Iterate over just the existing users of From. See the comments in
5913 // the ReplaceAllUsesWith above.
5914 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5915 RAUWUpdateListener Listener(*this, UI, UE);
5919 // This node is about to morph, remove its old self from the CSE maps.
5920 RemoveNodeFromCSEMaps(User);
5922 // A user can appear in a use list multiple times, and when this
5923 // happens the uses are usually next to each other in the list.
5924 // To help reduce the number of CSE recomputations, process all
5925 // the uses of this user that we can find this way.
5927 SDUse &Use = UI.getUse();
5930 } while (UI != UE && *UI == User);
5932 // Now that we have modified User, add it back to the CSE maps. If it
5933 // already exists there, recursively merge the results together.
5934 AddModifiedNodeToCSEMaps(User);
5937 // If we just RAUW'd the root, take note.
5938 if (From == getRoot().getNode())
5939 setRoot(SDValue(To, getRoot().getResNo()));
5942 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5943 /// This can cause recursive merging of nodes in the DAG.
5945 /// This version can replace From with any result values. To must match the
5946 /// number and types of values returned by From.
5947 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5948 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5949 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5951 // Iterate over just the existing users of From. See the comments in
5952 // the ReplaceAllUsesWith above.
5953 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5954 RAUWUpdateListener Listener(*this, UI, UE);
5958 // This node is about to morph, remove its old self from the CSE maps.
5959 RemoveNodeFromCSEMaps(User);
5961 // A user can appear in a use list multiple times, and when this
5962 // happens the uses are usually next to each other in the list.
5963 // To help reduce the number of CSE recomputations, process all
5964 // the uses of this user that we can find this way.
5966 SDUse &Use = UI.getUse();
5967 const SDValue &ToOp = To[Use.getResNo()];
5970 } while (UI != UE && *UI == User);
5972 // Now that we have modified User, add it back to the CSE maps. If it
5973 // already exists there, recursively merge the results together.
5974 AddModifiedNodeToCSEMaps(User);
5977 // If we just RAUW'd the root, take note.
5978 if (From == getRoot().getNode())
5979 setRoot(SDValue(To[getRoot().getResNo()]));
5982 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5983 /// uses of other values produced by From.getNode() alone. The Deleted
5984 /// vector is handled the same way as for ReplaceAllUsesWith.
5985 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5986 // Handle the really simple, really trivial case efficiently.
5987 if (From == To) return;
5989 // Handle the simple, trivial, case efficiently.
5990 if (From.getNode()->getNumValues() == 1) {
5991 ReplaceAllUsesWith(From, To);
5995 // Iterate over just the existing users of From. See the comments in
5996 // the ReplaceAllUsesWith above.
5997 SDNode::use_iterator UI = From.getNode()->use_begin(),
5998 UE = From.getNode()->use_end();
5999 RAUWUpdateListener Listener(*this, UI, UE);
6002 bool UserRemovedFromCSEMaps = false;
6004 // A user can appear in a use list multiple times, and when this
6005 // happens the uses are usually next to each other in the list.
6006 // To help reduce the number of CSE recomputations, process all
6007 // the uses of this user that we can find this way.
6009 SDUse &Use = UI.getUse();
6011 // Skip uses of different values from the same node.
6012 if (Use.getResNo() != From.getResNo()) {
6017 // If this node hasn't been modified yet, it's still in the CSE maps,
6018 // so remove its old self from the CSE maps.
6019 if (!UserRemovedFromCSEMaps) {
6020 RemoveNodeFromCSEMaps(User);
6021 UserRemovedFromCSEMaps = true;
6026 } while (UI != UE && *UI == User);
6028 // We are iterating over all uses of the From node, so if a use
6029 // doesn't use the specific value, no changes are made.
6030 if (!UserRemovedFromCSEMaps)
6033 // Now that we have modified User, add it back to the CSE maps. If it
6034 // already exists there, recursively merge the results together.
6035 AddModifiedNodeToCSEMaps(User);
6038 // If we just RAUW'd the root, take note.
6039 if (From == getRoot())
6044 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6045 /// to record information about a use.
6052 /// operator< - Sort Memos by User.
6053 bool operator<(const UseMemo &L, const UseMemo &R) {
6054 return (intptr_t)L.User < (intptr_t)R.User;
6058 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6059 /// uses of other values produced by From.getNode() alone. The same value
6060 /// may appear in both the From and To list. The Deleted vector is
6061 /// handled the same way as for ReplaceAllUsesWith.
6062 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6065 // Handle the simple, trivial case efficiently.
6067 return ReplaceAllUsesOfValueWith(*From, *To);
6069 // Read up all the uses and make records of them. This helps
6070 // processing new uses that are introduced during the
6071 // replacement process.
6072 SmallVector<UseMemo, 4> Uses;
6073 for (unsigned i = 0; i != Num; ++i) {
6074 unsigned FromResNo = From[i].getResNo();
6075 SDNode *FromNode = From[i].getNode();
6076 for (SDNode::use_iterator UI = FromNode->use_begin(),
6077 E = FromNode->use_end(); UI != E; ++UI) {
6078 SDUse &Use = UI.getUse();
6079 if (Use.getResNo() == FromResNo) {
6080 UseMemo Memo = { *UI, i, &Use };
6081 Uses.push_back(Memo);
6086 // Sort the uses, so that all the uses from a given User are together.
6087 std::sort(Uses.begin(), Uses.end());
6089 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6090 UseIndex != UseIndexEnd; ) {
6091 // We know that this user uses some value of From. If it is the right
6092 // value, update it.
6093 SDNode *User = Uses[UseIndex].User;
6095 // This node is about to morph, remove its old self from the CSE maps.
6096 RemoveNodeFromCSEMaps(User);
6098 // The Uses array is sorted, so all the uses for a given User
6099 // are next to each other in the list.
6100 // To help reduce the number of CSE recomputations, process all
6101 // the uses of this user that we can find this way.
6103 unsigned i = Uses[UseIndex].Index;
6104 SDUse &Use = *Uses[UseIndex].Use;
6108 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6110 // Now that we have modified User, add it back to the CSE maps. If it
6111 // already exists there, recursively merge the results together.
6112 AddModifiedNodeToCSEMaps(User);
6116 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6117 /// based on their topological order. It returns the maximum id and a vector
6118 /// of the SDNodes* in assigned order by reference.
6119 unsigned SelectionDAG::AssignTopologicalOrder() {
6121 unsigned DAGSize = 0;
6123 // SortedPos tracks the progress of the algorithm. Nodes before it are
6124 // sorted, nodes after it are unsorted. When the algorithm completes
6125 // it is at the end of the list.
6126 allnodes_iterator SortedPos = allnodes_begin();
6128 // Visit all the nodes. Move nodes with no operands to the front of
6129 // the list immediately. Annotate nodes that do have operands with their
6130 // operand count. Before we do this, the Node Id fields of the nodes
6131 // may contain arbitrary values. After, the Node Id fields for nodes
6132 // before SortedPos will contain the topological sort index, and the
6133 // Node Id fields for nodes At SortedPos and after will contain the
6134 // count of outstanding operands.
6135 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6137 checkForCycles(N, this);
6138 unsigned Degree = N->getNumOperands();
6140 // A node with no uses, add it to the result array immediately.
6141 N->setNodeId(DAGSize++);
6142 allnodes_iterator Q = N;
6144 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6145 assert(SortedPos != AllNodes.end() && "Overran node list");
6148 // Temporarily use the Node Id as scratch space for the degree count.
6149 N->setNodeId(Degree);
6153 // Visit all the nodes. As we iterate, move nodes into sorted order,
6154 // such that by the time the end is reached all nodes will be sorted.
6155 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6157 checkForCycles(N, this);
6158 // N is in sorted position, so all its uses have one less operand
6159 // that needs to be sorted.
6160 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6163 unsigned Degree = P->getNodeId();
6164 assert(Degree != 0 && "Invalid node degree");
6167 // All of P's operands are sorted, so P may sorted now.
6168 P->setNodeId(DAGSize++);
6170 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6171 assert(SortedPos != AllNodes.end() && "Overran node list");
6174 // Update P's outstanding operand count.
6175 P->setNodeId(Degree);
6178 if (I == SortedPos) {
6181 dbgs() << "Overran sorted position:\n";
6182 S->dumprFull(this); dbgs() << "\n";
6183 dbgs() << "Checking if this is due to cycles\n";
6184 checkForCycles(this, true);
6186 llvm_unreachable(nullptr);
6190 assert(SortedPos == AllNodes.end() &&
6191 "Topological sort incomplete!");
6192 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6193 "First node in topological sort is not the entry token!");
6194 assert(AllNodes.front().getNodeId() == 0 &&
6195 "First node in topological sort has non-zero id!");
6196 assert(AllNodes.front().getNumOperands() == 0 &&
6197 "First node in topological sort has operands!");
6198 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6199 "Last node in topologic sort has unexpected id!");
6200 assert(AllNodes.back().use_empty() &&
6201 "Last node in topologic sort has users!");
6202 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6206 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6207 /// value is produced by SD.
6208 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6209 DbgInfo->add(DB, SD, isParameter);
6211 SD->setHasDebugValue(true);
6214 /// TransferDbgValues - Transfer SDDbgValues.
6215 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6216 if (From == To || !From.getNode()->getHasDebugValue())
6218 SDNode *FromNode = From.getNode();
6219 SDNode *ToNode = To.getNode();
6220 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6221 SmallVector<SDDbgValue *, 2> ClonedDVs;
6222 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6224 SDDbgValue *Dbg = *I;
6225 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6226 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6228 Dbg->getOffset(), Dbg->getDebugLoc(),
6230 ClonedDVs.push_back(Clone);
6233 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6234 E = ClonedDVs.end(); I != E; ++I)
6235 AddDbgValue(*I, ToNode, false);
6238 //===----------------------------------------------------------------------===//
6240 //===----------------------------------------------------------------------===//
6242 HandleSDNode::~HandleSDNode() {
6246 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6247 DebugLoc DL, const GlobalValue *GA,
6248 EVT VT, int64_t o, unsigned char TF)
6249 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6253 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6254 SDValue X, unsigned SrcAS,
6256 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6257 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6259 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6260 EVT memvt, MachineMemOperand *mmo)
6261 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6262 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6263 MMO->isNonTemporal(), MMO->isInvariant());
6264 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6265 assert(isNonTemporal() == MMO->isNonTemporal() &&
6266 "Non-temporal encoding error!");
6267 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6270 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6271 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6272 : SDNode(Opc, Order, dl, VTs, Ops),
6273 MemoryVT(memvt), MMO(mmo) {
6274 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6275 MMO->isNonTemporal(), MMO->isInvariant());
6276 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6277 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6280 /// Profile - Gather unique data for the node.
6282 void SDNode::Profile(FoldingSetNodeID &ID) const {
6283 AddNodeIDNode(ID, this);
6288 std::vector<EVT> VTs;
6291 VTs.reserve(MVT::LAST_VALUETYPE);
6292 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6293 VTs.push_back(MVT((MVT::SimpleValueType)i));
6298 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6299 static ManagedStatic<EVTArray> SimpleVTArray;
6300 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6302 /// getValueTypeList - Return a pointer to the specified value type.
6304 const EVT *SDNode::getValueTypeList(EVT VT) {
6305 if (VT.isExtended()) {
6306 sys::SmartScopedLock<true> Lock(*VTMutex);
6307 return &(*EVTs->insert(VT).first);
6309 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6310 "Value type out of range!");
6311 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6315 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6316 /// indicated value. This method ignores uses of other values defined by this
6318 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6319 assert(Value < getNumValues() && "Bad value!");
6321 // TODO: Only iterate over uses of a given value of the node
6322 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6323 if (UI.getUse().getResNo() == Value) {
6330 // Found exactly the right number of uses?
6335 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6336 /// value. This method ignores uses of other values defined by this operation.
6337 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6338 assert(Value < getNumValues() && "Bad value!");
6340 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6341 if (UI.getUse().getResNo() == Value)
6348 /// isOnlyUserOf - Return true if this node is the only use of N.
6350 bool SDNode::isOnlyUserOf(SDNode *N) const {
6352 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6363 /// isOperand - Return true if this node is an operand of N.
6365 bool SDValue::isOperandOf(SDNode *N) const {
6366 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6367 if (*this == N->getOperand(i))
6372 bool SDNode::isOperandOf(SDNode *N) const {
6373 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6374 if (this == N->OperandList[i].getNode())
6379 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6380 /// be a chain) reaches the specified operand without crossing any
6381 /// side-effecting instructions on any chain path. In practice, this looks
6382 /// through token factors and non-volatile loads. In order to remain efficient,
6383 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6384 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6385 unsigned Depth) const {
6386 if (*this == Dest) return true;
6388 // Don't search too deeply, we just want to be able to see through
6389 // TokenFactor's etc.
6390 if (Depth == 0) return false;
6392 // If this is a token factor, all inputs to the TF happen in parallel. If any
6393 // of the operands of the TF does not reach dest, then we cannot do the xform.
6394 if (getOpcode() == ISD::TokenFactor) {
6395 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6396 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6401 // Loads don't have side effects, look through them.
6402 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6403 if (!Ld->isVolatile())
6404 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6409 /// hasPredecessor - Return true if N is a predecessor of this node.
6410 /// N is either an operand of this node, or can be reached by recursively
6411 /// traversing up the operands.
6412 /// NOTE: This is an expensive method. Use it carefully.
6413 bool SDNode::hasPredecessor(const SDNode *N) const {
6414 SmallPtrSet<const SDNode *, 32> Visited;
6415 SmallVector<const SDNode *, 16> Worklist;
6416 return hasPredecessorHelper(N, Visited, Worklist);
6420 SDNode::hasPredecessorHelper(const SDNode *N,
6421 SmallPtrSet<const SDNode *, 32> &Visited,
6422 SmallVectorImpl<const SDNode *> &Worklist) const {
6423 if (Visited.empty()) {
6424 Worklist.push_back(this);
6426 // Take a look in the visited set. If we've already encountered this node
6427 // we needn't search further.
6428 if (Visited.count(N))
6432 // Haven't visited N yet. Continue the search.
6433 while (!Worklist.empty()) {
6434 const SDNode *M = Worklist.pop_back_val();
6435 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6436 SDNode *Op = M->getOperand(i).getNode();
6437 if (Visited.insert(Op))
6438 Worklist.push_back(Op);
6447 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6448 assert(Num < NumOperands && "Invalid child # of SDNode!");
6449 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6452 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6453 assert(N->getNumValues() == 1 &&
6454 "Can't unroll a vector with multiple results!");
6456 EVT VT = N->getValueType(0);
6457 unsigned NE = VT.getVectorNumElements();
6458 EVT EltVT = VT.getVectorElementType();
6461 SmallVector<SDValue, 8> Scalars;
6462 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6464 // If ResNE is 0, fully unroll the vector op.
6467 else if (NE > ResNE)
6471 for (i= 0; i != NE; ++i) {
6472 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6473 SDValue Operand = N->getOperand(j);
6474 EVT OperandVT = Operand.getValueType();
6475 if (OperandVT.isVector()) {
6476 // A vector operand; extract a single element.
6477 const TargetLowering *TLI = TM.getTargetLowering();
6478 EVT OperandEltVT = OperandVT.getVectorElementType();
6479 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6482 getConstant(i, TLI->getVectorIdxTy()));
6484 // A scalar operand; just use it as is.
6485 Operands[j] = Operand;
6489 switch (N->getOpcode()) {
6491 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6494 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6501 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6502 getShiftAmountOperand(Operands[0].getValueType(),
6505 case ISD::SIGN_EXTEND_INREG:
6506 case ISD::FP_ROUND_INREG: {
6507 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6508 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6510 getValueType(ExtVT)));
6515 for (; i < ResNE; ++i)
6516 Scalars.push_back(getUNDEF(EltVT));
6518 return getNode(ISD::BUILD_VECTOR, dl,
6519 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6523 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6524 /// location that is 'Dist' units away from the location that the 'Base' load
6525 /// is loading from.
6526 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6527 unsigned Bytes, int Dist) const {
6528 if (LD->getChain() != Base->getChain())
6530 EVT VT = LD->getValueType(0);
6531 if (VT.getSizeInBits() / 8 != Bytes)
6534 SDValue Loc = LD->getOperand(1);
6535 SDValue BaseLoc = Base->getOperand(1);
6536 if (Loc.getOpcode() == ISD::FrameIndex) {
6537 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6539 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6540 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6541 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6542 int FS = MFI->getObjectSize(FI);
6543 int BFS = MFI->getObjectSize(BFI);
6544 if (FS != BFS || FS != (int)Bytes) return false;
6545 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6549 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6550 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6553 const GlobalValue *GV1 = nullptr;
6554 const GlobalValue *GV2 = nullptr;
6555 int64_t Offset1 = 0;
6556 int64_t Offset2 = 0;
6557 const TargetLowering *TLI = TM.getTargetLowering();
6558 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6559 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6560 if (isGA1 && isGA2 && GV1 == GV2)
6561 return Offset1 == (Offset2 + Dist*Bytes);
6566 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6567 /// it cannot be inferred.
6568 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6569 // If this is a GlobalAddress + cst, return the alignment.
6570 const GlobalValue *GV;
6571 int64_t GVOffset = 0;
6572 const TargetLowering *TLI = TM.getTargetLowering();
6573 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6574 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6575 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6576 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6577 TLI->getDataLayout());
6578 unsigned AlignBits = KnownZero.countTrailingOnes();
6579 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6581 return MinAlign(Align, GVOffset);
6584 // If this is a direct reference to a stack slot, use information about the
6585 // stack slot's alignment.
6586 int FrameIdx = 1 << 31;
6587 int64_t FrameOffset = 0;
6588 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6589 FrameIdx = FI->getIndex();
6590 } else if (isBaseWithConstantOffset(Ptr) &&
6591 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6593 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6594 FrameOffset = Ptr.getConstantOperandVal(1);
6597 if (FrameIdx != (1 << 31)) {
6598 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6599 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6607 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6608 /// which is split (or expanded) into two not necessarily identical pieces.
6609 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6610 // Currently all types are split in half.
6612 if (!VT.isVector()) {
6613 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6615 unsigned NumElements = VT.getVectorNumElements();
6616 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6617 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6620 return std::make_pair(LoVT, HiVT);
6623 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6625 std::pair<SDValue, SDValue>
6626 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6628 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6629 N.getValueType().getVectorNumElements() &&
6630 "More vector elements requested than available!");
6632 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6633 getConstant(0, TLI->getVectorIdxTy()));
6634 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6635 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6636 return std::make_pair(Lo, Hi);
6639 void SelectionDAG::ExtractVectorElements(SDValue Op,
6640 SmallVectorImpl<SDValue> &Args,
6641 unsigned Start, unsigned Count) {
6642 EVT VT = Op.getValueType();
6644 Count = VT.getVectorNumElements();
6646 EVT EltVT = VT.getVectorElementType();
6647 EVT IdxTy = TLI->getVectorIdxTy();
6649 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6650 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6651 Op, getConstant(i, IdxTy)));
6655 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6656 unsigned GlobalAddressSDNode::getAddressSpace() const {
6657 return getGlobal()->getType()->getAddressSpace();
6661 Type *ConstantPoolSDNode::getType() const {
6662 if (isMachineConstantPoolEntry())
6663 return Val.MachineCPVal->getType();
6664 return Val.ConstVal->getType();
6667 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6669 unsigned &SplatBitSize,
6671 unsigned MinSplatBits,
6672 bool isBigEndian) const {
6673 EVT VT = getValueType(0);
6674 assert(VT.isVector() && "Expected a vector type");
6675 unsigned sz = VT.getSizeInBits();
6676 if (MinSplatBits > sz)
6679 SplatValue = APInt(sz, 0);
6680 SplatUndef = APInt(sz, 0);
6682 // Get the bits. Bits with undefined values (when the corresponding element
6683 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6684 // in SplatValue. If any of the values are not constant, give up and return
6686 unsigned int nOps = getNumOperands();
6687 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6688 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6690 for (unsigned j = 0; j < nOps; ++j) {
6691 unsigned i = isBigEndian ? nOps-1-j : j;
6692 SDValue OpVal = getOperand(i);
6693 unsigned BitPos = j * EltBitSize;
6695 if (OpVal.getOpcode() == ISD::UNDEF)
6696 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6697 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6698 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6699 zextOrTrunc(sz) << BitPos;
6700 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6701 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6706 // The build_vector is all constants or undefs. Find the smallest element
6707 // size that splats the vector.
6709 HasAnyUndefs = (SplatUndef != 0);
6712 unsigned HalfSize = sz / 2;
6713 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6714 APInt LowValue = SplatValue.trunc(HalfSize);
6715 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6716 APInt LowUndef = SplatUndef.trunc(HalfSize);
6718 // If the two halves do not match (ignoring undef bits), stop here.
6719 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6720 MinSplatBits > HalfSize)
6723 SplatValue = HighValue | LowValue;
6724 SplatUndef = HighUndef & LowUndef;
6733 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6734 if (UndefElements) {
6735 UndefElements->clear();
6736 UndefElements->resize(getNumOperands());
6739 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6740 SDValue Op = getOperand(i);
6741 if (Op.getOpcode() == ISD::UNDEF) {
6743 (*UndefElements)[i] = true;
6744 } else if (!Splatted) {
6746 } else if (Splatted != Op) {
6752 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6753 "Can only have a splat without a constant for all undefs.");
6754 return getOperand(0);
6761 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6762 return dyn_cast_or_null<ConstantSDNode>(
6763 getSplatValue(UndefElements).getNode());
6767 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6768 return dyn_cast_or_null<ConstantFPSDNode>(
6769 getSplatValue(UndefElements).getNode());
6772 bool BuildVectorSDNode::isConstant() const {
6773 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6774 unsigned Opc = getOperand(i).getOpcode();
6775 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6781 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6782 // Find the first non-undef value in the shuffle mask.
6784 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6787 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6789 // Make sure all remaining elements are either undef or the same as the first
6791 for (int Idx = Mask[i]; i != e; ++i)
6792 if (Mask[i] >= 0 && Mask[i] != Idx)
6798 static void checkForCyclesHelper(const SDNode *N,
6799 SmallPtrSet<const SDNode*, 32> &Visited,
6800 SmallPtrSet<const SDNode*, 32> &Checked,
6801 const llvm::SelectionDAG *DAG) {
6802 // If this node has already been checked, don't check it again.
6803 if (Checked.count(N))
6806 // If a node has already been visited on this depth-first walk, reject it as
6808 if (!Visited.insert(N)) {
6809 errs() << "Detected cycle in SelectionDAG\n";
6810 dbgs() << "Offending node:\n";
6811 N->dumprFull(DAG); dbgs() << "\n";
6815 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6816 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6823 void llvm::checkForCycles(const llvm::SDNode *N,
6824 const llvm::SelectionDAG *DAG,
6832 assert(N && "Checking nonexistent SDNode");
6833 SmallPtrSet<const SDNode*, 32> visited;
6834 SmallPtrSet<const SDNode*, 32> checked;
6835 checkForCyclesHelper(N, visited, checked, DAG);
6840 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6841 checkForCycles(DAG->getRoot().getNode(), DAG, force);