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"
49 #include "llvm/Target/TargetSubtargetInfo.h"
55 /// makeVTList - Return an instance of the SDVTList struct initialized with the
56 /// specified members.
57 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
58 SDVTList Res = {VTs, NumVTs};
62 // Default null implementations of the callbacks.
63 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
64 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
66 //===----------------------------------------------------------------------===//
67 // ConstantFPSDNode Class
68 //===----------------------------------------------------------------------===//
70 /// isExactlyValue - We don't rely on operator== working on double values, as
71 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
72 /// As such, this method can be used to do an exact bit-for-bit comparison of
73 /// two floating point values.
74 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
75 return getValueAPF().bitwiseIsEqual(V);
78 bool ConstantFPSDNode::isValueValidForType(EVT VT,
80 assert(VT.isFloatingPoint() && "Can only convert between FP types");
82 // convert modifies in place, so make a copy.
83 APFloat Val2 = APFloat(Val);
85 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
86 APFloat::rmNearestTiesToEven,
91 //===----------------------------------------------------------------------===//
93 //===----------------------------------------------------------------------===//
95 /// isBuildVectorAllOnes - Return true if the specified node is a
96 /// BUILD_VECTOR where all of the elements are ~0 or undef.
97 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
98 // Look through a bit convert.
99 while (N->getOpcode() == ISD::BITCAST)
100 N = N->getOperand(0).getNode();
102 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
104 unsigned i = 0, e = N->getNumOperands();
106 // Skip over all of the undef values.
107 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
110 // Do not accept an all-undef vector.
111 if (i == e) return false;
113 // Do not accept build_vectors that aren't all constants or which have non-~0
114 // elements. We have to be a bit careful here, as the type of the constant
115 // may not be the same as the type of the vector elements due to type
116 // legalization (the elements are promoted to a legal type for the target and
117 // a vector of a type may be legal when the base element type is not).
118 // We only want to check enough bits to cover the vector elements, because
119 // we care if the resultant vector is all ones, not whether the individual
121 SDValue NotZero = N->getOperand(i);
122 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
123 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
124 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
126 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
127 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
132 // Okay, we have at least one ~0 value, check to see if the rest match or are
133 // undefs. Even with the above element type twiddling, this should be OK, as
134 // the same type legalization should have applied to all the elements.
135 for (++i; i != e; ++i)
136 if (N->getOperand(i) != NotZero &&
137 N->getOperand(i).getOpcode() != ISD::UNDEF)
143 /// isBuildVectorAllZeros - Return true if the specified node is a
144 /// BUILD_VECTOR where all of the elements are 0 or undef.
145 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
146 // Look through a bit convert.
147 while (N->getOpcode() == ISD::BITCAST)
148 N = N->getOperand(0).getNode();
150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
152 bool IsAllUndef = true;
153 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
154 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
157 // Do not accept build_vectors that aren't all constants or which have non-0
158 // elements. We have to be a bit careful here, as the type of the constant
159 // may not be the same as the type of the vector elements due to type
160 // legalization (the elements are promoted to a legal type for the target
161 // and a vector of a type may be legal when the base element type is not).
162 // We only want to check enough bits to cover the vector elements, because
163 // we care if the resultant vector is all zeros, not whether the individual
165 SDValue Zero = N->getOperand(i);
166 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
167 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
168 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
170 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
171 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
177 // Do not accept an all-undef vector.
183 /// \brief Return true if the specified node is a BUILD_VECTOR node of
184 /// all ConstantSDNode or undef.
185 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
186 if (N->getOpcode() != ISD::BUILD_VECTOR)
189 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
190 SDValue Op = N->getOperand(i);
191 if (Op.getOpcode() == ISD::UNDEF)
193 if (!isa<ConstantSDNode>(Op))
199 /// \brief Return true if the specified node is a BUILD_VECTOR node of
200 /// all ConstantFPSDNode or undef.
201 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
202 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
206 SDValue Op = N->getOperand(i);
207 if (Op.getOpcode() == ISD::UNDEF)
209 if (!isa<ConstantFPSDNode>(Op))
215 /// isScalarToVector - Return true if the specified node is a
216 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
217 /// element is not an undef.
218 bool ISD::isScalarToVector(const SDNode *N) {
219 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
222 if (N->getOpcode() != ISD::BUILD_VECTOR)
224 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
226 unsigned NumElems = N->getNumOperands();
229 for (unsigned i = 1; i < NumElems; ++i) {
230 SDValue V = N->getOperand(i);
231 if (V.getOpcode() != ISD::UNDEF)
237 /// allOperandsUndef - Return true if the node has at least one operand
238 /// and all operands of the specified node are ISD::UNDEF.
239 bool ISD::allOperandsUndef(const SDNode *N) {
240 // Return false if the node has no operands.
241 // This is "logically inconsistent" with the definition of "all" but
242 // is probably the desired behavior.
243 if (N->getNumOperands() == 0)
246 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
247 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
253 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
256 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
258 return ISD::SIGN_EXTEND;
260 return ISD::ZERO_EXTEND;
265 llvm_unreachable("Invalid LoadExtType");
268 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
269 /// when given the operation for (X op Y).
270 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
271 // To perform this operation, we just need to swap the L and G bits of the
273 unsigned OldL = (Operation >> 2) & 1;
274 unsigned OldG = (Operation >> 1) & 1;
275 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
276 (OldL << 1) | // New G bit
277 (OldG << 2)); // New L bit.
280 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
281 /// 'op' is a valid SetCC operation.
282 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
283 unsigned Operation = Op;
285 Operation ^= 7; // Flip L, G, E bits, but not U.
287 Operation ^= 15; // Flip all of the condition bits.
289 if (Operation > ISD::SETTRUE2)
290 Operation &= ~8; // Don't let N and U bits get set.
292 return ISD::CondCode(Operation);
296 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
297 /// signed operation and 2 if the result is an unsigned comparison. Return zero
298 /// if the operation does not depend on the sign of the input (setne and seteq).
299 static int isSignedOp(ISD::CondCode Opcode) {
301 default: llvm_unreachable("Illegal integer setcc operation!");
303 case ISD::SETNE: return 0;
307 case ISD::SETGE: return 1;
311 case ISD::SETUGE: return 2;
315 /// getSetCCOrOperation - Return the result of a logical OR between different
316 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
317 /// returns SETCC_INVALID if it is not possible to represent the resultant
319 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
321 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
322 // Cannot fold a signed integer setcc with an unsigned integer setcc.
323 return ISD::SETCC_INVALID;
325 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
327 // If the N and U bits get set then the resultant comparison DOES suddenly
328 // care about orderedness, and is true when ordered.
329 if (Op > ISD::SETTRUE2)
330 Op &= ~16; // Clear the U bit if the N bit is set.
332 // Canonicalize illegal integer setcc's.
333 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
336 return ISD::CondCode(Op);
339 /// getSetCCAndOperation - Return the result of a logical AND between different
340 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
341 /// function returns zero if it is not possible to represent the resultant
343 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
345 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
346 // Cannot fold a signed setcc with an unsigned setcc.
347 return ISD::SETCC_INVALID;
349 // Combine all of the condition bits.
350 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
352 // Canonicalize illegal integer setcc's.
356 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
357 case ISD::SETOEQ: // SETEQ & SETU[LG]E
358 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
359 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
360 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
367 //===----------------------------------------------------------------------===//
368 // SDNode Profile Support
369 //===----------------------------------------------------------------------===//
371 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
373 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
377 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
378 /// solely with their pointer.
379 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
380 ID.AddPointer(VTList.VTs);
383 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
385 static void AddNodeIDOperands(FoldingSetNodeID &ID,
386 ArrayRef<SDValue> Ops) {
387 for (auto& Op : Ops) {
388 ID.AddPointer(Op.getNode());
389 ID.AddInteger(Op.getResNo());
393 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
395 static void AddNodeIDOperands(FoldingSetNodeID &ID,
396 ArrayRef<SDUse> Ops) {
397 for (auto& Op : Ops) {
398 ID.AddPointer(Op.getNode());
399 ID.AddInteger(Op.getResNo());
403 /// Add logical or fast math flag values to FoldingSetNodeID value.
404 static void AddNodeIDFlags(FoldingSetNodeID &ID, unsigned Opcode,
405 const SDNodeFlags *Flags) {
406 if (!Flags || !mayHaveOptimizationFlags(Opcode))
409 unsigned RawFlags = Flags->getRawFlags();
410 // If no flags are set, do not alter the ID. This saves time and allows
411 // a gradual increase in API usage of the optional optimization flags.
413 ID.AddInteger(RawFlags);
416 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
417 if (auto *Node = dyn_cast<SDNodeWithFlags>(N))
418 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
421 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
422 SDVTList VTList, ArrayRef<SDValue> OpList) {
423 AddNodeIDOpcode(ID, OpC);
424 AddNodeIDValueTypes(ID, VTList);
425 AddNodeIDOperands(ID, OpList);
428 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
430 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
431 switch (N->getOpcode()) {
432 case ISD::TargetExternalSymbol:
433 case ISD::ExternalSymbol:
434 llvm_unreachable("Should only be used on nodes with operands");
435 default: break; // Normal nodes don't need extra info.
436 case ISD::TargetConstant:
437 case ISD::Constant: {
438 const ConstantSDNode *C = cast<ConstantSDNode>(N);
439 ID.AddPointer(C->getConstantIntValue());
440 ID.AddBoolean(C->isOpaque());
443 case ISD::TargetConstantFP:
444 case ISD::ConstantFP: {
445 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
448 case ISD::TargetGlobalAddress:
449 case ISD::GlobalAddress:
450 case ISD::TargetGlobalTLSAddress:
451 case ISD::GlobalTLSAddress: {
452 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
453 ID.AddPointer(GA->getGlobal());
454 ID.AddInteger(GA->getOffset());
455 ID.AddInteger(GA->getTargetFlags());
456 ID.AddInteger(GA->getAddressSpace());
459 case ISD::BasicBlock:
460 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
463 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
465 case ISD::RegisterMask:
466 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
469 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
471 case ISD::FrameIndex:
472 case ISD::TargetFrameIndex:
473 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
476 case ISD::TargetJumpTable:
477 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
478 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
480 case ISD::ConstantPool:
481 case ISD::TargetConstantPool: {
482 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
483 ID.AddInteger(CP->getAlignment());
484 ID.AddInteger(CP->getOffset());
485 if (CP->isMachineConstantPoolEntry())
486 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
488 ID.AddPointer(CP->getConstVal());
489 ID.AddInteger(CP->getTargetFlags());
492 case ISD::TargetIndex: {
493 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
494 ID.AddInteger(TI->getIndex());
495 ID.AddInteger(TI->getOffset());
496 ID.AddInteger(TI->getTargetFlags());
500 const LoadSDNode *LD = cast<LoadSDNode>(N);
501 ID.AddInteger(LD->getMemoryVT().getRawBits());
502 ID.AddInteger(LD->getRawSubclassData());
503 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
507 const StoreSDNode *ST = cast<StoreSDNode>(N);
508 ID.AddInteger(ST->getMemoryVT().getRawBits());
509 ID.AddInteger(ST->getRawSubclassData());
510 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
513 case ISD::ATOMIC_CMP_SWAP:
514 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
515 case ISD::ATOMIC_SWAP:
516 case ISD::ATOMIC_LOAD_ADD:
517 case ISD::ATOMIC_LOAD_SUB:
518 case ISD::ATOMIC_LOAD_AND:
519 case ISD::ATOMIC_LOAD_OR:
520 case ISD::ATOMIC_LOAD_XOR:
521 case ISD::ATOMIC_LOAD_NAND:
522 case ISD::ATOMIC_LOAD_MIN:
523 case ISD::ATOMIC_LOAD_MAX:
524 case ISD::ATOMIC_LOAD_UMIN:
525 case ISD::ATOMIC_LOAD_UMAX:
526 case ISD::ATOMIC_LOAD:
527 case ISD::ATOMIC_STORE: {
528 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
529 ID.AddInteger(AT->getMemoryVT().getRawBits());
530 ID.AddInteger(AT->getRawSubclassData());
531 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
534 case ISD::PREFETCH: {
535 const MemSDNode *PF = cast<MemSDNode>(N);
536 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
539 case ISD::VECTOR_SHUFFLE: {
540 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
541 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
543 ID.AddInteger(SVN->getMaskElt(i));
546 case ISD::TargetBlockAddress:
547 case ISD::BlockAddress: {
548 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
549 ID.AddPointer(BA->getBlockAddress());
550 ID.AddInteger(BA->getOffset());
551 ID.AddInteger(BA->getTargetFlags());
554 } // end switch (N->getOpcode())
556 AddNodeIDFlags(ID, N);
558 // Target specific memory nodes could also have address spaces to check.
559 if (N->isTargetMemoryOpcode())
560 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
563 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
565 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
566 AddNodeIDOpcode(ID, N->getOpcode());
567 // Add the return value info.
568 AddNodeIDValueTypes(ID, N->getVTList());
569 // Add the operand info.
570 AddNodeIDOperands(ID, N->ops());
572 // Handle SDNode leafs with special info.
573 AddNodeIDCustom(ID, N);
576 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
577 /// the CSE map that carries volatility, temporalness, indexing mode, and
578 /// extension/truncation information.
580 static inline unsigned
581 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
582 bool isNonTemporal, bool isInvariant) {
583 assert((ConvType & 3) == ConvType &&
584 "ConvType may not require more than 2 bits!");
585 assert((AM & 7) == AM &&
586 "AM may not require more than 3 bits!");
590 (isNonTemporal << 6) |
594 //===----------------------------------------------------------------------===//
595 // SelectionDAG Class
596 //===----------------------------------------------------------------------===//
598 /// doNotCSE - Return true if CSE should not be performed for this node.
599 static bool doNotCSE(SDNode *N) {
600 if (N->getValueType(0) == MVT::Glue)
601 return true; // Never CSE anything that produces a flag.
603 switch (N->getOpcode()) {
605 case ISD::HANDLENODE:
607 return true; // Never CSE these nodes.
610 // Check that remaining values produced are not flags.
611 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
612 if (N->getValueType(i) == MVT::Glue)
613 return true; // Never CSE anything that produces a flag.
618 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
620 void SelectionDAG::RemoveDeadNodes() {
621 // Create a dummy node (which is not added to allnodes), that adds a reference
622 // to the root node, preventing it from being deleted.
623 HandleSDNode Dummy(getRoot());
625 SmallVector<SDNode*, 128> DeadNodes;
627 // Add all obviously-dead nodes to the DeadNodes worklist.
628 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
630 DeadNodes.push_back(I);
632 RemoveDeadNodes(DeadNodes);
634 // If the root changed (e.g. it was a dead load, update the root).
635 setRoot(Dummy.getValue());
638 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
639 /// given list, and any nodes that become unreachable as a result.
640 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
642 // Process the worklist, deleting the nodes and adding their uses to the
644 while (!DeadNodes.empty()) {
645 SDNode *N = DeadNodes.pop_back_val();
647 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
648 DUL->NodeDeleted(N, nullptr);
650 // Take the node out of the appropriate CSE map.
651 RemoveNodeFromCSEMaps(N);
653 // Next, brutally remove the operand list. This is safe to do, as there are
654 // no cycles in the graph.
655 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
657 SDNode *Operand = Use.getNode();
660 // Now that we removed this operand, see if there are no uses of it left.
661 if (Operand->use_empty())
662 DeadNodes.push_back(Operand);
669 void SelectionDAG::RemoveDeadNode(SDNode *N){
670 SmallVector<SDNode*, 16> DeadNodes(1, N);
672 // Create a dummy node that adds a reference to the root node, preventing
673 // it from being deleted. (This matters if the root is an operand of the
675 HandleSDNode Dummy(getRoot());
677 RemoveDeadNodes(DeadNodes);
680 void SelectionDAG::DeleteNode(SDNode *N) {
681 // First take this out of the appropriate CSE map.
682 RemoveNodeFromCSEMaps(N);
684 // Finally, remove uses due to operands of this node, remove from the
685 // AllNodes list, and delete the node.
686 DeleteNodeNotInCSEMaps(N);
689 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
690 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
691 assert(N->use_empty() && "Cannot delete a node that is not dead!");
693 // Drop all of the operands and decrement used node's use counts.
699 void SDDbgInfo::erase(const SDNode *Node) {
700 DbgValMapType::iterator I = DbgValMap.find(Node);
701 if (I == DbgValMap.end())
703 for (auto &Val: I->second)
704 Val->setIsInvalidated();
708 void SelectionDAG::DeallocateNode(SDNode *N) {
709 if (N->OperandsNeedDelete)
710 delete[] N->OperandList;
712 // Set the opcode to DELETED_NODE to help catch bugs when node
713 // memory is reallocated.
714 N->NodeType = ISD::DELETED_NODE;
716 NodeAllocator.Deallocate(AllNodes.remove(N));
718 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
719 // them and forget about that node.
724 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
725 static void VerifySDNode(SDNode *N) {
726 switch (N->getOpcode()) {
729 case ISD::BUILD_PAIR: {
730 EVT VT = N->getValueType(0);
731 assert(N->getNumValues() == 1 && "Too many results!");
732 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
733 "Wrong return type!");
734 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
735 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
736 "Mismatched operand types!");
737 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
738 "Wrong operand type!");
739 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
740 "Wrong return type size");
743 case ISD::BUILD_VECTOR: {
744 assert(N->getNumValues() == 1 && "Too many results!");
745 assert(N->getValueType(0).isVector() && "Wrong return type!");
746 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
747 "Wrong number of operands!");
748 EVT EltVT = N->getValueType(0).getVectorElementType();
749 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
750 assert((I->getValueType() == EltVT ||
751 (EltVT.isInteger() && I->getValueType().isInteger() &&
752 EltVT.bitsLE(I->getValueType()))) &&
753 "Wrong operand type!");
754 assert(I->getValueType() == N->getOperand(0).getValueType() &&
755 "Operands must all have the same type");
763 /// \brief Insert a newly allocated node into the DAG.
765 /// Handles insertion into the all nodes list and CSE map, as well as
766 /// verification and other common operations when a new node is allocated.
767 void SelectionDAG::InsertNode(SDNode *N) {
768 AllNodes.push_back(N);
774 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
775 /// correspond to it. This is useful when we're about to delete or repurpose
776 /// the node. We don't want future request for structurally identical nodes
777 /// to return N anymore.
778 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
780 switch (N->getOpcode()) {
781 case ISD::HANDLENODE: return false; // noop.
783 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
784 "Cond code doesn't exist!");
785 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
786 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
788 case ISD::ExternalSymbol:
789 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
791 case ISD::TargetExternalSymbol: {
792 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
793 Erased = TargetExternalSymbols.erase(
794 std::pair<std::string,unsigned char>(ESN->getSymbol(),
795 ESN->getTargetFlags()));
798 case ISD::VALUETYPE: {
799 EVT VT = cast<VTSDNode>(N)->getVT();
800 if (VT.isExtended()) {
801 Erased = ExtendedValueTypeNodes.erase(VT);
803 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
804 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
809 // Remove it from the CSE Map.
810 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
811 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
812 Erased = CSEMap.RemoveNode(N);
816 // Verify that the node was actually in one of the CSE maps, unless it has a
817 // flag result (which cannot be CSE'd) or is one of the special cases that are
818 // not subject to CSE.
819 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
820 !N->isMachineOpcode() && !doNotCSE(N)) {
823 llvm_unreachable("Node is not in map!");
829 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
830 /// maps and modified in place. Add it back to the CSE maps, unless an identical
831 /// node already exists, in which case transfer all its users to the existing
832 /// node. This transfer can potentially trigger recursive merging.
835 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
836 // For node types that aren't CSE'd, just act as if no identical node
839 SDNode *Existing = CSEMap.GetOrInsertNode(N);
841 // If there was already an existing matching node, use ReplaceAllUsesWith
842 // to replace the dead one with the existing one. This can cause
843 // recursive merging of other unrelated nodes down the line.
844 ReplaceAllUsesWith(N, Existing);
846 // N is now dead. Inform the listeners and delete it.
847 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
848 DUL->NodeDeleted(N, Existing);
849 DeleteNodeNotInCSEMaps(N);
854 // If the node doesn't already exist, we updated it. Inform listeners.
855 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
859 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
860 /// were replaced with those specified. If this node is never memoized,
861 /// return null, otherwise return a pointer to the slot it would take. If a
862 /// node already exists with these operands, the slot will be non-null.
863 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
868 SDValue Ops[] = { Op };
870 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
871 AddNodeIDCustom(ID, N);
872 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
876 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
877 /// were replaced with those specified. If this node is never memoized,
878 /// return null, otherwise return a pointer to the slot it would take. If a
879 /// node already exists with these operands, the slot will be non-null.
880 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
881 SDValue Op1, SDValue Op2,
886 SDValue Ops[] = { Op1, Op2 };
888 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
889 AddNodeIDCustom(ID, N);
890 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
895 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
896 /// were replaced with those specified. If this node is never memoized,
897 /// return null, otherwise return a pointer to the slot it would take. If a
898 /// node already exists with these operands, the slot will be non-null.
899 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
905 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
906 AddNodeIDCustom(ID, N);
907 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
911 /// getEVTAlignment - Compute the default alignment value for the
914 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
915 Type *Ty = VT == MVT::iPTR ?
916 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
917 VT.getTypeForEVT(*getContext());
919 return TLI->getDataLayout()->getABITypeAlignment(Ty);
922 // EntryNode could meaningfully have debug info if we can find it...
923 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
924 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
925 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
926 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
927 UpdateListeners(nullptr) {
928 AllNodes.push_back(&EntryNode);
929 DbgInfo = new SDDbgInfo();
932 void SelectionDAG::init(MachineFunction &mf) {
934 TLI = getSubtarget().getTargetLowering();
935 TSI = getSubtarget().getSelectionDAGInfo();
936 Context = &mf.getFunction()->getContext();
939 SelectionDAG::~SelectionDAG() {
940 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
945 void SelectionDAG::allnodes_clear() {
946 assert(&*AllNodes.begin() == &EntryNode);
947 AllNodes.remove(AllNodes.begin());
948 while (!AllNodes.empty())
949 DeallocateNode(AllNodes.begin());
952 SDNode *SelectionDAG::GetSDNodeWithFlags(unsigned Opcode, SDLoc DL,
953 SDVTList VTs, ArrayRef<SDValue> Ops,
954 const SDNodeFlags *Flags) {
955 if (mayHaveOptimizationFlags(Opcode)) {
956 // If no flags were passed in, use a default flags object.
958 if (Flags == nullptr)
961 SDNodeWithFlags *NodeWithFlags = new (NodeAllocator) SDNodeWithFlags(
962 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, Ops, *Flags);
963 return NodeWithFlags;
966 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
967 DL.getDebugLoc(), VTs, Ops);
971 void SelectionDAG::clear() {
973 OperandAllocator.Reset();
976 ExtendedValueTypeNodes.clear();
977 ExternalSymbols.clear();
978 TargetExternalSymbols.clear();
979 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
980 static_cast<CondCodeSDNode*>(nullptr));
981 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
982 static_cast<SDNode*>(nullptr));
984 EntryNode.UseList = nullptr;
985 AllNodes.push_back(&EntryNode);
986 Root = getEntryNode();
990 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
991 return VT.bitsGT(Op.getValueType()) ?
992 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
993 getNode(ISD::TRUNCATE, DL, VT, Op);
996 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
997 return VT.bitsGT(Op.getValueType()) ?
998 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
999 getNode(ISD::TRUNCATE, DL, VT, Op);
1002 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1003 return VT.bitsGT(Op.getValueType()) ?
1004 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1005 getNode(ISD::TRUNCATE, DL, VT, Op);
1008 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1010 if (VT.bitsLE(Op.getValueType()))
1011 return getNode(ISD::TRUNCATE, SL, VT, Op);
1013 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1014 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1017 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1018 assert(!VT.isVector() &&
1019 "getZeroExtendInReg should use the vector element type instead of "
1020 "the vector type!");
1021 if (Op.getValueType() == VT) return Op;
1022 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1023 APInt Imm = APInt::getLowBitsSet(BitWidth,
1024 VT.getSizeInBits());
1025 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1026 getConstant(Imm, DL, Op.getValueType()));
1029 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1030 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1031 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1032 "The sizes of the input and result must match in order to perform the "
1033 "extend in-register.");
1034 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1035 "The destination vector type must have fewer lanes than the input.");
1036 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1039 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1040 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1041 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1042 "The sizes of the input and result must match in order to perform the "
1043 "extend in-register.");
1044 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1045 "The destination vector type must have fewer lanes than the input.");
1046 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1049 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1050 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1051 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1052 "The sizes of the input and result must match in order to perform the "
1053 "extend in-register.");
1054 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1055 "The destination vector type must have fewer lanes than the input.");
1056 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1059 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1061 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1062 EVT EltVT = VT.getScalarType();
1064 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1065 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1068 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1069 EVT EltVT = VT.getScalarType();
1071 switch (TLI->getBooleanContents(VT)) {
1072 case TargetLowering::ZeroOrOneBooleanContent:
1073 case TargetLowering::UndefinedBooleanContent:
1074 TrueValue = getConstant(1, DL, VT);
1076 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1077 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1081 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1084 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1086 EVT EltVT = VT.getScalarType();
1087 assert((EltVT.getSizeInBits() >= 64 ||
1088 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1089 "getConstant with a uint64_t value that doesn't fit in the type!");
1090 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1093 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1096 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1099 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1100 bool isT, bool isO) {
1101 assert(VT.isInteger() && "Cannot create FP integer constant!");
1103 EVT EltVT = VT.getScalarType();
1104 const ConstantInt *Elt = &Val;
1106 // In some cases the vector type is legal but the element type is illegal and
1107 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1108 // inserted value (the type does not need to match the vector element type).
1109 // Any extra bits introduced will be truncated away.
1110 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1111 TargetLowering::TypePromoteInteger) {
1112 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1113 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1114 Elt = ConstantInt::get(*getContext(), NewVal);
1116 // In other cases the element type is illegal and needs to be expanded, for
1117 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1118 // the value into n parts and use a vector type with n-times the elements.
1119 // Then bitcast to the type requested.
1120 // Legalizing constants too early makes the DAGCombiner's job harder so we
1121 // only legalize if the DAG tells us we must produce legal types.
1122 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1123 TLI->getTypeAction(*getContext(), EltVT) ==
1124 TargetLowering::TypeExpandInteger) {
1125 APInt NewVal = Elt->getValue();
1126 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1127 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1128 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1129 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1131 // Check the temporary vector is the correct size. If this fails then
1132 // getTypeToTransformTo() probably returned a type whose size (in bits)
1133 // isn't a power-of-2 factor of the requested type size.
1134 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1136 SmallVector<SDValue, 2> EltParts;
1137 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1138 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1139 .trunc(ViaEltSizeInBits), DL,
1140 ViaEltVT, isT, isO));
1143 // EltParts is currently in little endian order. If we actually want
1144 // big-endian order then reverse it now.
1145 if (TLI->isBigEndian())
1146 std::reverse(EltParts.begin(), EltParts.end());
1148 // The elements must be reversed when the element order is different
1149 // to the endianness of the elements (because the BITCAST is itself a
1150 // vector shuffle in this situation). However, we do not need any code to
1151 // perform this reversal because getConstant() is producing a vector
1153 // This situation occurs in MIPS MSA.
1155 SmallVector<SDValue, 8> Ops;
1156 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1157 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1159 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1160 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1165 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1166 "APInt size does not match type size!");
1167 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1168 FoldingSetNodeID ID;
1169 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1173 SDNode *N = nullptr;
1174 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1176 return SDValue(N, 0);
1179 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1181 CSEMap.InsertNode(N, IP);
1185 SDValue Result(N, 0);
1186 if (VT.isVector()) {
1187 SmallVector<SDValue, 8> Ops;
1188 Ops.assign(VT.getVectorNumElements(), Result);
1189 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1194 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1195 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1198 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1200 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1203 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1205 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1207 EVT EltVT = VT.getScalarType();
1209 // Do the map lookup using the actual bit pattern for the floating point
1210 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1211 // we don't have issues with SNANs.
1212 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1213 FoldingSetNodeID ID;
1214 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1217 SDNode *N = nullptr;
1218 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1220 return SDValue(N, 0);
1223 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1224 CSEMap.InsertNode(N, IP);
1228 SDValue Result(N, 0);
1229 if (VT.isVector()) {
1230 SmallVector<SDValue, 8> Ops;
1231 Ops.assign(VT.getVectorNumElements(), Result);
1232 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1237 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1239 EVT EltVT = VT.getScalarType();
1240 if (EltVT==MVT::f32)
1241 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1242 else if (EltVT==MVT::f64)
1243 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1244 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1247 APFloat apf = APFloat(Val);
1248 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1250 return getConstantFP(apf, DL, VT, isTarget);
1252 llvm_unreachable("Unsupported type in getConstantFP");
1255 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1256 EVT VT, int64_t Offset,
1258 unsigned char TargetFlags) {
1259 assert((TargetFlags == 0 || isTargetGA) &&
1260 "Cannot set target flags on target-independent globals");
1262 // Truncate (with sign-extension) the offset value to the pointer size.
1263 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1265 Offset = SignExtend64(Offset, BitWidth);
1268 if (GV->isThreadLocal())
1269 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1271 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1273 FoldingSetNodeID ID;
1274 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1276 ID.AddInteger(Offset);
1277 ID.AddInteger(TargetFlags);
1278 ID.AddInteger(GV->getType()->getAddressSpace());
1280 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1281 return SDValue(E, 0);
1283 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1284 DL.getDebugLoc(), GV, VT,
1285 Offset, TargetFlags);
1286 CSEMap.InsertNode(N, IP);
1288 return SDValue(N, 0);
1291 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1292 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1293 FoldingSetNodeID ID;
1294 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1297 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1298 return SDValue(E, 0);
1300 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1301 CSEMap.InsertNode(N, IP);
1303 return SDValue(N, 0);
1306 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1307 unsigned char TargetFlags) {
1308 assert((TargetFlags == 0 || isTarget) &&
1309 "Cannot set target flags on target-independent jump tables");
1310 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1311 FoldingSetNodeID ID;
1312 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1314 ID.AddInteger(TargetFlags);
1316 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1317 return SDValue(E, 0);
1319 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1321 CSEMap.InsertNode(N, IP);
1323 return SDValue(N, 0);
1326 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1327 unsigned Alignment, int Offset,
1329 unsigned char TargetFlags) {
1330 assert((TargetFlags == 0 || isTarget) &&
1331 "Cannot set target flags on target-independent globals");
1333 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1334 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1335 FoldingSetNodeID ID;
1336 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1337 ID.AddInteger(Alignment);
1338 ID.AddInteger(Offset);
1340 ID.AddInteger(TargetFlags);
1342 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1343 return SDValue(E, 0);
1345 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1346 Alignment, TargetFlags);
1347 CSEMap.InsertNode(N, IP);
1349 return SDValue(N, 0);
1353 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1354 unsigned Alignment, int Offset,
1356 unsigned char TargetFlags) {
1357 assert((TargetFlags == 0 || isTarget) &&
1358 "Cannot set target flags on target-independent globals");
1360 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1361 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1362 FoldingSetNodeID ID;
1363 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1364 ID.AddInteger(Alignment);
1365 ID.AddInteger(Offset);
1366 C->addSelectionDAGCSEId(ID);
1367 ID.AddInteger(TargetFlags);
1369 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1370 return SDValue(E, 0);
1372 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1373 Alignment, TargetFlags);
1374 CSEMap.InsertNode(N, IP);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1380 unsigned char TargetFlags) {
1381 FoldingSetNodeID ID;
1382 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1383 ID.AddInteger(Index);
1384 ID.AddInteger(Offset);
1385 ID.AddInteger(TargetFlags);
1387 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1388 return SDValue(E, 0);
1390 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1392 CSEMap.InsertNode(N, IP);
1394 return SDValue(N, 0);
1397 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1398 FoldingSetNodeID ID;
1399 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1402 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1403 return SDValue(E, 0);
1405 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1406 CSEMap.InsertNode(N, IP);
1408 return SDValue(N, 0);
1411 SDValue SelectionDAG::getValueType(EVT VT) {
1412 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1413 ValueTypeNodes.size())
1414 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1416 SDNode *&N = VT.isExtended() ?
1417 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1419 if (N) return SDValue(N, 0);
1420 N = new (NodeAllocator) VTSDNode(VT);
1422 return SDValue(N, 0);
1425 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1426 SDNode *&N = ExternalSymbols[Sym];
1427 if (N) return SDValue(N, 0);
1428 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1430 return SDValue(N, 0);
1433 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1434 unsigned char TargetFlags) {
1436 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1438 if (N) return SDValue(N, 0);
1439 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1441 return SDValue(N, 0);
1444 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1445 if ((unsigned)Cond >= CondCodeNodes.size())
1446 CondCodeNodes.resize(Cond+1);
1448 if (!CondCodeNodes[Cond]) {
1449 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1450 CondCodeNodes[Cond] = N;
1454 return SDValue(CondCodeNodes[Cond], 0);
1457 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1458 // the shuffle mask M that point at N1 to point at N2, and indices that point
1459 // N2 to point at N1.
1460 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1462 ShuffleVectorSDNode::commuteMask(M);
1465 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1466 SDValue N2, const int *Mask) {
1467 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1468 "Invalid VECTOR_SHUFFLE");
1470 // Canonicalize shuffle undef, undef -> undef
1471 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1472 return getUNDEF(VT);
1474 // Validate that all indices in Mask are within the range of the elements
1475 // input to the shuffle.
1476 unsigned NElts = VT.getVectorNumElements();
1477 SmallVector<int, 8> MaskVec;
1478 for (unsigned i = 0; i != NElts; ++i) {
1479 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1480 MaskVec.push_back(Mask[i]);
1483 // Canonicalize shuffle v, v -> v, undef
1486 for (unsigned i = 0; i != NElts; ++i)
1487 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1490 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1491 if (N1.getOpcode() == ISD::UNDEF)
1492 commuteShuffle(N1, N2, MaskVec);
1494 // If shuffling a splat, try to blend the splat instead. We do this here so
1495 // that even when this arises during lowering we don't have to re-handle it.
1496 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1497 BitVector UndefElements;
1498 SDValue Splat = BV->getSplatValue(&UndefElements);
1502 for (int i = 0; i < (int)NElts; ++i) {
1503 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1506 // If this input comes from undef, mark it as such.
1507 if (UndefElements[MaskVec[i] - Offset]) {
1512 // If we can blend a non-undef lane, use that instead.
1513 if (!UndefElements[i])
1514 MaskVec[i] = i + Offset;
1517 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1518 BlendSplat(N1BV, 0);
1519 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1520 BlendSplat(N2BV, NElts);
1522 // Canonicalize all index into lhs, -> shuffle lhs, undef
1523 // Canonicalize all index into rhs, -> shuffle rhs, undef
1524 bool AllLHS = true, AllRHS = true;
1525 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1526 for (unsigned i = 0; i != NElts; ++i) {
1527 if (MaskVec[i] >= (int)NElts) {
1532 } else if (MaskVec[i] >= 0) {
1536 if (AllLHS && AllRHS)
1537 return getUNDEF(VT);
1538 if (AllLHS && !N2Undef)
1542 commuteShuffle(N1, N2, MaskVec);
1544 // Reset our undef status after accounting for the mask.
1545 N2Undef = N2.getOpcode() == ISD::UNDEF;
1546 // Re-check whether both sides ended up undef.
1547 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1548 return getUNDEF(VT);
1550 // If Identity shuffle return that node.
1551 bool Identity = true, AllSame = true;
1552 for (unsigned i = 0; i != NElts; ++i) {
1553 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1554 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1556 if (Identity && NElts)
1559 // Shuffling a constant splat doesn't change the result.
1563 // Look through any bitcasts. We check that these don't change the number
1564 // (and size) of elements and just changes their types.
1565 while (V.getOpcode() == ISD::BITCAST)
1566 V = V->getOperand(0);
1568 // A splat should always show up as a build vector node.
1569 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1570 BitVector UndefElements;
1571 SDValue Splat = BV->getSplatValue(&UndefElements);
1572 // If this is a splat of an undef, shuffling it is also undef.
1573 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1574 return getUNDEF(VT);
1577 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1579 // We only have a splat which can skip shuffles if there is a splatted
1580 // value and no undef lanes rearranged by the shuffle.
1581 if (Splat && UndefElements.none()) {
1582 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1583 // number of elements match or the value splatted is a zero constant.
1586 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1587 if (C->isNullValue())
1591 // If the shuffle itself creates a splat, build the vector directly.
1592 if (AllSame && SameNumElts) {
1593 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1594 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1596 EVT BuildVT = BV->getValueType(0);
1597 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1599 // We may have jumped through bitcasts, so the type of the
1600 // BUILD_VECTOR may not match the type of the shuffle.
1602 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1608 FoldingSetNodeID ID;
1609 SDValue Ops[2] = { N1, N2 };
1610 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1611 for (unsigned i = 0; i != NElts; ++i)
1612 ID.AddInteger(MaskVec[i]);
1615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1616 return SDValue(E, 0);
1618 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1619 // SDNode doesn't have access to it. This memory will be "leaked" when
1620 // the node is deallocated, but recovered when the NodeAllocator is released.
1621 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1622 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1624 ShuffleVectorSDNode *N =
1625 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1626 dl.getDebugLoc(), N1, N2,
1628 CSEMap.InsertNode(N, IP);
1630 return SDValue(N, 0);
1633 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1634 MVT VT = SV.getSimpleValueType(0);
1635 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1636 ShuffleVectorSDNode::commuteMask(MaskVec);
1638 SDValue Op0 = SV.getOperand(0);
1639 SDValue Op1 = SV.getOperand(1);
1640 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1643 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1644 SDValue Val, SDValue DTy,
1645 SDValue STy, SDValue Rnd, SDValue Sat,
1646 ISD::CvtCode Code) {
1647 // If the src and dest types are the same and the conversion is between
1648 // integer types of the same sign or two floats, no conversion is necessary.
1650 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1653 FoldingSetNodeID ID;
1654 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1655 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1657 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1658 return SDValue(E, 0);
1660 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1663 CSEMap.InsertNode(N, IP);
1665 return SDValue(N, 0);
1668 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1669 FoldingSetNodeID ID;
1670 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1671 ID.AddInteger(RegNo);
1673 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1674 return SDValue(E, 0);
1676 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1677 CSEMap.InsertNode(N, IP);
1679 return SDValue(N, 0);
1682 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1683 FoldingSetNodeID ID;
1684 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1685 ID.AddPointer(RegMask);
1687 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1688 return SDValue(E, 0);
1690 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1691 CSEMap.InsertNode(N, IP);
1693 return SDValue(N, 0);
1696 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1697 FoldingSetNodeID ID;
1698 SDValue Ops[] = { Root };
1699 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1700 ID.AddPointer(Label);
1702 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1703 return SDValue(E, 0);
1705 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1706 dl.getDebugLoc(), Root, Label);
1707 CSEMap.InsertNode(N, IP);
1709 return SDValue(N, 0);
1713 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1716 unsigned char TargetFlags) {
1717 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1719 FoldingSetNodeID ID;
1720 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1722 ID.AddInteger(Offset);
1723 ID.AddInteger(TargetFlags);
1725 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1726 return SDValue(E, 0);
1728 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1730 CSEMap.InsertNode(N, IP);
1732 return SDValue(N, 0);
1735 SDValue SelectionDAG::getSrcValue(const Value *V) {
1736 assert((!V || V->getType()->isPointerTy()) &&
1737 "SrcValue is not a pointer?");
1739 FoldingSetNodeID ID;
1740 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1744 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1745 return SDValue(E, 0);
1747 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1748 CSEMap.InsertNode(N, IP);
1750 return SDValue(N, 0);
1753 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1754 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1755 FoldingSetNodeID ID;
1756 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1760 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1761 return SDValue(E, 0);
1763 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1764 CSEMap.InsertNode(N, IP);
1766 return SDValue(N, 0);
1769 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1770 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1771 unsigned SrcAS, unsigned DestAS) {
1772 SDValue Ops[] = {Ptr};
1773 FoldingSetNodeID ID;
1774 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1775 ID.AddInteger(SrcAS);
1776 ID.AddInteger(DestAS);
1779 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1780 return SDValue(E, 0);
1782 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1784 VT, Ptr, SrcAS, DestAS);
1785 CSEMap.InsertNode(N, IP);
1787 return SDValue(N, 0);
1790 /// getShiftAmountOperand - Return the specified value casted to
1791 /// the target's desired shift amount type.
1792 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1793 EVT OpTy = Op.getValueType();
1794 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1795 if (OpTy == ShTy || OpTy.isVector()) return Op;
1797 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1798 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1801 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1802 /// specified value type.
1803 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1804 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1805 unsigned ByteSize = VT.getStoreSize();
1806 Type *Ty = VT.getTypeForEVT(*getContext());
1807 unsigned StackAlign =
1808 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1810 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1811 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1814 /// CreateStackTemporary - Create a stack temporary suitable for holding
1815 /// either of the specified value types.
1816 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1817 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1818 VT2.getStoreSizeInBits())/8;
1819 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1820 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1821 const DataLayout *TD = TLI->getDataLayout();
1822 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1823 TD->getPrefTypeAlignment(Ty2));
1825 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1826 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1827 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1830 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1831 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1832 // These setcc operations always fold.
1836 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1838 case ISD::SETTRUE2: {
1839 TargetLowering::BooleanContent Cnt =
1840 TLI->getBooleanContents(N1->getValueType(0));
1842 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1856 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1860 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1861 const APInt &C2 = N2C->getAPIntValue();
1862 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1863 const APInt &C1 = N1C->getAPIntValue();
1866 default: llvm_unreachable("Unknown integer setcc!");
1867 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1868 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1869 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1870 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1871 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1872 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1873 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1874 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1875 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1876 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1880 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1881 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1882 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1885 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1886 return getUNDEF(VT);
1888 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1889 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1890 return getUNDEF(VT);
1892 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1893 R==APFloat::cmpLessThan, dl, VT);
1894 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1895 return getUNDEF(VT);
1897 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1898 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1899 return getUNDEF(VT);
1901 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1902 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1903 return getUNDEF(VT);
1905 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1906 R==APFloat::cmpEqual, dl, VT);
1907 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1908 return getUNDEF(VT);
1910 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1911 R==APFloat::cmpEqual, dl, VT);
1912 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1913 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1914 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1915 R==APFloat::cmpEqual, dl, VT);
1916 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1917 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1918 R==APFloat::cmpLessThan, dl, VT);
1919 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1920 R==APFloat::cmpUnordered, dl, VT);
1921 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1922 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1925 // Ensure that the constant occurs on the RHS.
1926 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1927 MVT CompVT = N1.getValueType().getSimpleVT();
1928 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1931 return getSetCC(dl, VT, N2, N1, SwappedCond);
1935 // Could not fold it.
1939 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1940 /// use this predicate to simplify operations downstream.
1941 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1942 // This predicate is not safe for vector operations.
1943 if (Op.getValueType().isVector())
1946 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1947 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1950 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1951 /// this predicate to simplify operations downstream. Mask is known to be zero
1952 /// for bits that V cannot have.
1953 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1954 unsigned Depth) const {
1955 APInt KnownZero, KnownOne;
1956 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1957 return (KnownZero & Mask) == Mask;
1960 /// Determine which bits of Op are known to be either zero or one and return
1961 /// them in the KnownZero/KnownOne bitsets.
1962 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1963 APInt &KnownOne, unsigned Depth) const {
1964 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1966 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1968 return; // Limit search depth.
1970 APInt KnownZero2, KnownOne2;
1972 switch (Op.getOpcode()) {
1974 // We know all of the bits for a constant!
1975 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1976 KnownZero = ~KnownOne;
1979 // If either the LHS or the RHS are Zero, the result is zero.
1980 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1981 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1983 // Output known-1 bits are only known if set in both the LHS & RHS.
1984 KnownOne &= KnownOne2;
1985 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1986 KnownZero |= KnownZero2;
1989 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1990 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1992 // Output known-0 bits are only known if clear in both the LHS & RHS.
1993 KnownZero &= KnownZero2;
1994 // Output known-1 are known to be set if set in either the LHS | RHS.
1995 KnownOne |= KnownOne2;
1998 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1999 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2001 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2002 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2003 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2004 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2005 KnownZero = KnownZeroOut;
2009 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2010 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2012 // If low bits are zero in either operand, output low known-0 bits.
2013 // Also compute a conserative estimate for high known-0 bits.
2014 // More trickiness is possible, but this is sufficient for the
2015 // interesting case of alignment computation.
2016 KnownOne.clearAllBits();
2017 unsigned TrailZ = KnownZero.countTrailingOnes() +
2018 KnownZero2.countTrailingOnes();
2019 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2020 KnownZero2.countLeadingOnes(),
2021 BitWidth) - BitWidth;
2023 TrailZ = std::min(TrailZ, BitWidth);
2024 LeadZ = std::min(LeadZ, BitWidth);
2025 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2026 APInt::getHighBitsSet(BitWidth, LeadZ);
2030 // For the purposes of computing leading zeros we can conservatively
2031 // treat a udiv as a logical right shift by the power of 2 known to
2032 // be less than the denominator.
2033 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2034 unsigned LeadZ = KnownZero2.countLeadingOnes();
2036 KnownOne2.clearAllBits();
2037 KnownZero2.clearAllBits();
2038 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2039 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2040 if (RHSUnknownLeadingOnes != BitWidth)
2041 LeadZ = std::min(BitWidth,
2042 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2044 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2048 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2049 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2051 // Only known if known in both the LHS and RHS.
2052 KnownOne &= KnownOne2;
2053 KnownZero &= KnownZero2;
2055 case ISD::SELECT_CC:
2056 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2057 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2059 // Only known if known in both the LHS and RHS.
2060 KnownOne &= KnownOne2;
2061 KnownZero &= KnownZero2;
2069 if (Op.getResNo() != 1)
2071 // The boolean result conforms to getBooleanContents.
2072 // If we know the result of a setcc has the top bits zero, use this info.
2073 // We know that we have an integer-based boolean since these operations
2074 // are only available for integer.
2075 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2076 TargetLowering::ZeroOrOneBooleanContent &&
2078 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2081 // If we know the result of a setcc has the top bits zero, use this info.
2082 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2083 TargetLowering::ZeroOrOneBooleanContent &&
2085 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2088 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2089 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2090 unsigned ShAmt = SA->getZExtValue();
2092 // If the shift count is an invalid immediate, don't do anything.
2093 if (ShAmt >= BitWidth)
2096 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2097 KnownZero <<= ShAmt;
2099 // low bits known zero.
2100 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2104 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2105 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2106 unsigned ShAmt = SA->getZExtValue();
2108 // If the shift count is an invalid immediate, don't do anything.
2109 if (ShAmt >= BitWidth)
2112 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2113 KnownZero = KnownZero.lshr(ShAmt);
2114 KnownOne = KnownOne.lshr(ShAmt);
2116 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2117 KnownZero |= HighBits; // High bits known zero.
2121 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2122 unsigned ShAmt = SA->getZExtValue();
2124 // If the shift count is an invalid immediate, don't do anything.
2125 if (ShAmt >= BitWidth)
2128 // If any of the demanded bits are produced by the sign extension, we also
2129 // demand the input sign bit.
2130 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2132 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2133 KnownZero = KnownZero.lshr(ShAmt);
2134 KnownOne = KnownOne.lshr(ShAmt);
2136 // Handle the sign bits.
2137 APInt SignBit = APInt::getSignBit(BitWidth);
2138 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2140 if (KnownZero.intersects(SignBit)) {
2141 KnownZero |= HighBits; // New bits are known zero.
2142 } else if (KnownOne.intersects(SignBit)) {
2143 KnownOne |= HighBits; // New bits are known one.
2147 case ISD::SIGN_EXTEND_INREG: {
2148 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2149 unsigned EBits = EVT.getScalarType().getSizeInBits();
2151 // Sign extension. Compute the demanded bits in the result that are not
2152 // present in the input.
2153 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2155 APInt InSignBit = APInt::getSignBit(EBits);
2156 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2158 // If the sign extended bits are demanded, we know that the sign
2160 InSignBit = InSignBit.zext(BitWidth);
2161 if (NewBits.getBoolValue())
2162 InputDemandedBits |= InSignBit;
2164 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2165 KnownOne &= InputDemandedBits;
2166 KnownZero &= InputDemandedBits;
2168 // If the sign bit of the input is known set or clear, then we know the
2169 // top bits of the result.
2170 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2171 KnownZero |= NewBits;
2172 KnownOne &= ~NewBits;
2173 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2174 KnownOne |= NewBits;
2175 KnownZero &= ~NewBits;
2176 } else { // Input sign bit unknown
2177 KnownZero &= ~NewBits;
2178 KnownOne &= ~NewBits;
2183 case ISD::CTTZ_ZERO_UNDEF:
2185 case ISD::CTLZ_ZERO_UNDEF:
2187 unsigned LowBits = Log2_32(BitWidth)+1;
2188 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2189 KnownOne.clearAllBits();
2193 LoadSDNode *LD = cast<LoadSDNode>(Op);
2194 // If this is a ZEXTLoad and we are looking at the loaded value.
2195 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2196 EVT VT = LD->getMemoryVT();
2197 unsigned MemBits = VT.getScalarType().getSizeInBits();
2198 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2199 } else if (const MDNode *Ranges = LD->getRanges()) {
2200 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2204 case ISD::ZERO_EXTEND: {
2205 EVT InVT = Op.getOperand(0).getValueType();
2206 unsigned InBits = InVT.getScalarType().getSizeInBits();
2207 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2208 KnownZero = KnownZero.trunc(InBits);
2209 KnownOne = KnownOne.trunc(InBits);
2210 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 KnownZero = KnownZero.zext(BitWidth);
2212 KnownOne = KnownOne.zext(BitWidth);
2213 KnownZero |= NewBits;
2216 case ISD::SIGN_EXTEND: {
2217 EVT InVT = Op.getOperand(0).getValueType();
2218 unsigned InBits = InVT.getScalarType().getSizeInBits();
2219 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2221 KnownZero = KnownZero.trunc(InBits);
2222 KnownOne = KnownOne.trunc(InBits);
2223 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2225 // Note if the sign bit is known to be zero or one.
2226 bool SignBitKnownZero = KnownZero.isNegative();
2227 bool SignBitKnownOne = KnownOne.isNegative();
2229 KnownZero = KnownZero.zext(BitWidth);
2230 KnownOne = KnownOne.zext(BitWidth);
2232 // If the sign bit is known zero or one, the top bits match.
2233 if (SignBitKnownZero)
2234 KnownZero |= NewBits;
2235 else if (SignBitKnownOne)
2236 KnownOne |= NewBits;
2239 case ISD::ANY_EXTEND: {
2240 EVT InVT = Op.getOperand(0).getValueType();
2241 unsigned InBits = InVT.getScalarType().getSizeInBits();
2242 KnownZero = KnownZero.trunc(InBits);
2243 KnownOne = KnownOne.trunc(InBits);
2244 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2245 KnownZero = KnownZero.zext(BitWidth);
2246 KnownOne = KnownOne.zext(BitWidth);
2249 case ISD::TRUNCATE: {
2250 EVT InVT = Op.getOperand(0).getValueType();
2251 unsigned InBits = InVT.getScalarType().getSizeInBits();
2252 KnownZero = KnownZero.zext(InBits);
2253 KnownOne = KnownOne.zext(InBits);
2254 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2255 KnownZero = KnownZero.trunc(BitWidth);
2256 KnownOne = KnownOne.trunc(BitWidth);
2259 case ISD::AssertZext: {
2260 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2261 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2262 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2263 KnownZero |= (~InMask);
2264 KnownOne &= (~KnownZero);
2268 // All bits are zero except the low bit.
2269 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2273 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2274 // We know that the top bits of C-X are clear if X contains less bits
2275 // than C (i.e. no wrap-around can happen). For example, 20-X is
2276 // positive if we can prove that X is >= 0 and < 16.
2277 if (CLHS->getAPIntValue().isNonNegative()) {
2278 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2279 // NLZ can't be BitWidth with no sign bit
2280 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2281 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2283 // If all of the MaskV bits are known to be zero, then we know the
2284 // output top bits are zero, because we now know that the output is
2286 if ((KnownZero2 & MaskV) == MaskV) {
2287 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2288 // Top bits known zero.
2289 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2297 // Output known-0 bits are known if clear or set in both the low clear bits
2298 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2299 // low 3 bits clear.
2300 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2301 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2303 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2304 KnownZeroOut = std::min(KnownZeroOut,
2305 KnownZero2.countTrailingOnes());
2307 if (Op.getOpcode() == ISD::ADD) {
2308 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2312 // With ADDE, a carry bit may be added in, so we can only use this
2313 // information if we know (at least) that the low two bits are clear. We
2314 // then return to the caller that the low bit is unknown but that other bits
2316 if (KnownZeroOut >= 2) // ADDE
2317 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2321 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2322 const APInt &RA = Rem->getAPIntValue().abs();
2323 if (RA.isPowerOf2()) {
2324 APInt LowBits = RA - 1;
2325 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2327 // The low bits of the first operand are unchanged by the srem.
2328 KnownZero = KnownZero2 & LowBits;
2329 KnownOne = KnownOne2 & LowBits;
2331 // If the first operand is non-negative or has all low bits zero, then
2332 // the upper bits are all zero.
2333 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2334 KnownZero |= ~LowBits;
2336 // If the first operand is negative and not all low bits are zero, then
2337 // the upper bits are all one.
2338 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2339 KnownOne |= ~LowBits;
2340 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2345 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2346 const APInt &RA = Rem->getAPIntValue();
2347 if (RA.isPowerOf2()) {
2348 APInt LowBits = (RA - 1);
2349 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2351 // The upper bits are all zero, the lower ones are unchanged.
2352 KnownZero = KnownZero2 | ~LowBits;
2353 KnownOne = KnownOne2 & LowBits;
2358 // Since the result is less than or equal to either operand, any leading
2359 // zero bits in either operand must also exist in the result.
2360 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2361 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2363 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2364 KnownZero2.countLeadingOnes());
2365 KnownOne.clearAllBits();
2366 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2369 case ISD::EXTRACT_ELEMENT: {
2370 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2371 const unsigned Index =
2372 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2373 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2375 // Remove low part of known bits mask
2376 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2377 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2379 // Remove high part of known bit mask
2380 KnownZero = KnownZero.trunc(BitWidth);
2381 KnownOne = KnownOne.trunc(BitWidth);
2384 case ISD::FrameIndex:
2385 case ISD::TargetFrameIndex:
2386 if (unsigned Align = InferPtrAlignment(Op)) {
2387 // The low bits are known zero if the pointer is aligned.
2388 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2394 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2397 case ISD::INTRINSIC_WO_CHAIN:
2398 case ISD::INTRINSIC_W_CHAIN:
2399 case ISD::INTRINSIC_VOID:
2400 // Allow the target to implement this method for its nodes.
2401 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2405 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2408 /// ComputeNumSignBits - Return the number of times the sign bit of the
2409 /// register is replicated into the other bits. We know that at least 1 bit
2410 /// is always equal to the sign bit (itself), but other cases can give us
2411 /// information. For example, immediately after an "SRA X, 2", we know that
2412 /// the top 3 bits are all equal to each other, so we return 3.
2413 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2414 EVT VT = Op.getValueType();
2415 assert(VT.isInteger() && "Invalid VT!");
2416 unsigned VTBits = VT.getScalarType().getSizeInBits();
2418 unsigned FirstAnswer = 1;
2421 return 1; // Limit search depth.
2423 switch (Op.getOpcode()) {
2425 case ISD::AssertSext:
2426 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2427 return VTBits-Tmp+1;
2428 case ISD::AssertZext:
2429 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2432 case ISD::Constant: {
2433 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2434 return Val.getNumSignBits();
2437 case ISD::SIGN_EXTEND:
2439 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2440 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2442 case ISD::SIGN_EXTEND_INREG:
2443 // Max of the input and what this extends.
2445 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2448 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2449 return std::max(Tmp, Tmp2);
2452 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2453 // SRA X, C -> adds C sign bits.
2454 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2455 Tmp += C->getZExtValue();
2456 if (Tmp > VTBits) Tmp = VTBits;
2460 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2461 // shl destroys sign bits.
2462 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2463 if (C->getZExtValue() >= VTBits || // Bad shift.
2464 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2465 return Tmp - C->getZExtValue();
2470 case ISD::XOR: // NOT is handled here.
2471 // Logical binary ops preserve the number of sign bits at the worst.
2472 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2474 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2475 FirstAnswer = std::min(Tmp, Tmp2);
2476 // We computed what we know about the sign bits as our first
2477 // answer. Now proceed to the generic code that uses
2478 // computeKnownBits, and pick whichever answer is better.
2483 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2484 if (Tmp == 1) return 1; // Early out.
2485 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2486 return std::min(Tmp, Tmp2);
2494 if (Op.getResNo() != 1)
2496 // The boolean result conforms to getBooleanContents. Fall through.
2497 // If setcc returns 0/-1, all bits are sign bits.
2498 // We know that we have an integer-based boolean since these operations
2499 // are only available for integer.
2500 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2501 TargetLowering::ZeroOrNegativeOneBooleanContent)
2505 // If setcc returns 0/-1, all bits are sign bits.
2506 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2507 TargetLowering::ZeroOrNegativeOneBooleanContent)
2512 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2513 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2515 // Handle rotate right by N like a rotate left by 32-N.
2516 if (Op.getOpcode() == ISD::ROTR)
2517 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2519 // If we aren't rotating out all of the known-in sign bits, return the
2520 // number that are left. This handles rotl(sext(x), 1) for example.
2521 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2522 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2526 // Add can have at most one carry bit. Thus we know that the output
2527 // is, at worst, one more bit than the inputs.
2528 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2529 if (Tmp == 1) return 1; // Early out.
2531 // Special case decrementing a value (ADD X, -1):
2532 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2533 if (CRHS->isAllOnesValue()) {
2534 APInt KnownZero, KnownOne;
2535 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2537 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2539 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2542 // If we are subtracting one from a positive number, there is no carry
2543 // out of the result.
2544 if (KnownZero.isNegative())
2548 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2549 if (Tmp2 == 1) return 1;
2550 return std::min(Tmp, Tmp2)-1;
2553 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2554 if (Tmp2 == 1) return 1;
2557 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2558 if (CLHS->isNullValue()) {
2559 APInt KnownZero, KnownOne;
2560 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2561 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2563 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2566 // If the input is known to be positive (the sign bit is known clear),
2567 // the output of the NEG has the same number of sign bits as the input.
2568 if (KnownZero.isNegative())
2571 // Otherwise, we treat this like a SUB.
2574 // Sub can have at most one carry bit. Thus we know that the output
2575 // is, at worst, one more bit than the inputs.
2576 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2577 if (Tmp == 1) return 1; // Early out.
2578 return std::min(Tmp, Tmp2)-1;
2580 // FIXME: it's tricky to do anything useful for this, but it is an important
2581 // case for targets like X86.
2583 case ISD::EXTRACT_ELEMENT: {
2584 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2585 const int BitWidth = Op.getValueType().getSizeInBits();
2587 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2589 // Get reverse index (starting from 1), Op1 value indexes elements from
2590 // little end. Sign starts at big end.
2591 const int rIndex = Items - 1 -
2592 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2594 // If the sign portion ends in our element the substraction gives correct
2595 // result. Otherwise it gives either negative or > bitwidth result
2596 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2600 // If we are looking at the loaded value of the SDNode.
2601 if (Op.getResNo() == 0) {
2602 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2603 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2604 unsigned ExtType = LD->getExtensionType();
2607 case ISD::SEXTLOAD: // '17' bits known
2608 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2609 return VTBits-Tmp+1;
2610 case ISD::ZEXTLOAD: // '16' bits known
2611 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2617 // Allow the target to implement this method for its nodes.
2618 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2619 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2620 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2621 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2622 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2623 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2626 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2627 // use this information.
2628 APInt KnownZero, KnownOne;
2629 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2632 if (KnownZero.isNegative()) { // sign bit is 0
2634 } else if (KnownOne.isNegative()) { // sign bit is 1;
2641 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2642 // the number of identical bits in the top of the input value.
2644 Mask <<= Mask.getBitWidth()-VTBits;
2645 // Return # leading zeros. We use 'min' here in case Val was zero before
2646 // shifting. We don't want to return '64' as for an i32 "0".
2647 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2650 /// isBaseWithConstantOffset - Return true if the specified operand is an
2651 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2652 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2653 /// semantics as an ADD. This handles the equivalence:
2654 /// X|Cst == X+Cst iff X&Cst = 0.
2655 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2656 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2657 !isa<ConstantSDNode>(Op.getOperand(1)))
2660 if (Op.getOpcode() == ISD::OR &&
2661 !MaskedValueIsZero(Op.getOperand(0),
2662 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2669 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2670 // If we're told that NaNs won't happen, assume they won't.
2671 if (getTarget().Options.NoNaNsFPMath)
2674 // If the value is a constant, we can obviously see if it is a NaN or not.
2675 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2676 return !C->getValueAPF().isNaN();
2678 // TODO: Recognize more cases here.
2683 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2684 // If the value is a constant, we can obviously see if it is a zero or not.
2685 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2686 return !C->isZero();
2688 // TODO: Recognize more cases here.
2689 switch (Op.getOpcode()) {
2692 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2693 return !C->isNullValue();
2700 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2701 // Check the obvious case.
2702 if (A == B) return true;
2704 // For for negative and positive zero.
2705 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2706 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2707 if (CA->isZero() && CB->isZero()) return true;
2709 // Otherwise they may not be equal.
2713 /// getNode - Gets or creates the specified node.
2715 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2716 FoldingSetNodeID ID;
2717 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2719 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2720 return SDValue(E, 0);
2722 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2723 DL.getDebugLoc(), getVTList(VT));
2724 CSEMap.InsertNode(N, IP);
2727 return SDValue(N, 0);
2730 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2731 EVT VT, SDValue Operand) {
2732 // Constant fold unary operations with an integer constant operand. Even
2733 // opaque constant will be folded, because the folding of unary operations
2734 // doesn't create new constants with different values. Nevertheless, the
2735 // opaque flag is preserved during folding to prevent future folding with
2737 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2738 const APInt &Val = C->getAPIntValue();
2741 case ISD::SIGN_EXTEND:
2742 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2743 C->isTargetOpcode(), C->isOpaque());
2744 case ISD::ANY_EXTEND:
2745 case ISD::ZERO_EXTEND:
2747 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2748 C->isTargetOpcode(), C->isOpaque());
2749 case ISD::UINT_TO_FP:
2750 case ISD::SINT_TO_FP: {
2751 APFloat apf(EVTToAPFloatSemantics(VT),
2752 APInt::getNullValue(VT.getSizeInBits()));
2753 (void)apf.convertFromAPInt(Val,
2754 Opcode==ISD::SINT_TO_FP,
2755 APFloat::rmNearestTiesToEven);
2756 return getConstantFP(apf, DL, VT);
2759 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2760 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2761 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2762 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2763 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2764 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2767 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2770 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2773 case ISD::CTLZ_ZERO_UNDEF:
2774 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2777 case ISD::CTTZ_ZERO_UNDEF:
2778 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2783 // Constant fold unary operations with a floating point constant operand.
2784 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2785 APFloat V = C->getValueAPF(); // make copy
2789 return getConstantFP(V, DL, VT);
2792 return getConstantFP(V, DL, VT);
2794 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2795 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2796 return getConstantFP(V, DL, VT);
2800 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2801 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2802 return getConstantFP(V, DL, VT);
2806 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2807 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2808 return getConstantFP(V, DL, VT);
2811 case ISD::FP_EXTEND: {
2813 // This can return overflow, underflow, or inexact; we don't care.
2814 // FIXME need to be more flexible about rounding mode.
2815 (void)V.convert(EVTToAPFloatSemantics(VT),
2816 APFloat::rmNearestTiesToEven, &ignored);
2817 return getConstantFP(V, DL, VT);
2819 case ISD::FP_TO_SINT:
2820 case ISD::FP_TO_UINT: {
2823 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2824 // FIXME need to be more flexible about rounding mode.
2825 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2826 Opcode==ISD::FP_TO_SINT,
2827 APFloat::rmTowardZero, &ignored);
2828 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2830 APInt api(VT.getSizeInBits(), x);
2831 return getConstant(api, DL, VT);
2834 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2835 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2836 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2837 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2838 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2839 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2844 // Constant fold unary operations with a vector integer or float operand.
2845 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2846 if (BV->isConstant()) {
2849 // FIXME: Entirely reasonable to perform folding of other unary
2850 // operations here as the need arises.
2857 case ISD::FP_EXTEND:
2858 case ISD::FP_TO_SINT:
2859 case ISD::FP_TO_UINT:
2861 case ISD::UINT_TO_FP:
2862 case ISD::SINT_TO_FP: {
2863 EVT SVT = VT.getScalarType();
2864 EVT InVT = BV->getValueType(0);
2865 EVT InSVT = InVT.getScalarType();
2867 // Find legal integer scalar type for constant promotion.
2869 if (SVT.isInteger()) {
2870 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2871 assert(LegalSVT.bitsGE(SVT) && "Unexpected legal scalar type size");
2874 // Let the above scalar folding handle the folding of each element.
2875 SmallVector<SDValue, 8> Ops;
2876 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2877 SDValue OpN = BV->getOperand(i);
2878 EVT OpVT = OpN.getValueType();
2880 // Build vector (integer) scalar operands may need implicit
2881 // truncation - do this before constant folding.
2882 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2883 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2885 OpN = getNode(Opcode, DL, SVT, OpN);
2887 // Legalize the (integer) scalar constant if necessary.
2888 if (LegalSVT != SVT)
2889 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2891 if (OpN.getOpcode() != ISD::UNDEF &&
2892 OpN.getOpcode() != ISD::Constant &&
2893 OpN.getOpcode() != ISD::ConstantFP)
2897 if (Ops.size() == VT.getVectorNumElements())
2898 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2905 unsigned OpOpcode = Operand.getNode()->getOpcode();
2907 case ISD::TokenFactor:
2908 case ISD::MERGE_VALUES:
2909 case ISD::CONCAT_VECTORS:
2910 return Operand; // Factor, merge or concat of one node? No need.
2911 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2912 case ISD::FP_EXTEND:
2913 assert(VT.isFloatingPoint() &&
2914 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2915 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2916 assert((!VT.isVector() ||
2917 VT.getVectorNumElements() ==
2918 Operand.getValueType().getVectorNumElements()) &&
2919 "Vector element count mismatch!");
2920 if (Operand.getOpcode() == ISD::UNDEF)
2921 return getUNDEF(VT);
2923 case ISD::SIGN_EXTEND:
2924 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2925 "Invalid SIGN_EXTEND!");
2926 if (Operand.getValueType() == VT) return Operand; // noop extension
2927 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2928 "Invalid sext node, dst < src!");
2929 assert((!VT.isVector() ||
2930 VT.getVectorNumElements() ==
2931 Operand.getValueType().getVectorNumElements()) &&
2932 "Vector element count mismatch!");
2933 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2934 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2935 else if (OpOpcode == ISD::UNDEF)
2936 // sext(undef) = 0, because the top bits will all be the same.
2937 return getConstant(0, DL, VT);
2939 case ISD::ZERO_EXTEND:
2940 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2941 "Invalid ZERO_EXTEND!");
2942 if (Operand.getValueType() == VT) return Operand; // noop extension
2943 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2944 "Invalid zext node, dst < src!");
2945 assert((!VT.isVector() ||
2946 VT.getVectorNumElements() ==
2947 Operand.getValueType().getVectorNumElements()) &&
2948 "Vector element count mismatch!");
2949 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2950 return getNode(ISD::ZERO_EXTEND, DL, VT,
2951 Operand.getNode()->getOperand(0));
2952 else if (OpOpcode == ISD::UNDEF)
2953 // zext(undef) = 0, because the top bits will be zero.
2954 return getConstant(0, DL, VT);
2956 case ISD::ANY_EXTEND:
2957 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2958 "Invalid ANY_EXTEND!");
2959 if (Operand.getValueType() == VT) return Operand; // noop extension
2960 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2961 "Invalid anyext node, dst < src!");
2962 assert((!VT.isVector() ||
2963 VT.getVectorNumElements() ==
2964 Operand.getValueType().getVectorNumElements()) &&
2965 "Vector element count mismatch!");
2967 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2968 OpOpcode == ISD::ANY_EXTEND)
2969 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2970 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2971 else if (OpOpcode == ISD::UNDEF)
2972 return getUNDEF(VT);
2974 // (ext (trunx x)) -> x
2975 if (OpOpcode == ISD::TRUNCATE) {
2976 SDValue OpOp = Operand.getNode()->getOperand(0);
2977 if (OpOp.getValueType() == VT)
2982 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2983 "Invalid TRUNCATE!");
2984 if (Operand.getValueType() == VT) return Operand; // noop truncate
2985 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2986 "Invalid truncate node, src < dst!");
2987 assert((!VT.isVector() ||
2988 VT.getVectorNumElements() ==
2989 Operand.getValueType().getVectorNumElements()) &&
2990 "Vector element count mismatch!");
2991 if (OpOpcode == ISD::TRUNCATE)
2992 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2993 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2994 OpOpcode == ISD::ANY_EXTEND) {
2995 // If the source is smaller than the dest, we still need an extend.
2996 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2997 .bitsLT(VT.getScalarType()))
2998 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2999 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3000 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3001 return Operand.getNode()->getOperand(0);
3003 if (OpOpcode == ISD::UNDEF)
3004 return getUNDEF(VT);
3007 // Basic sanity checking.
3008 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3009 && "Cannot BITCAST between types of different sizes!");
3010 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3011 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3012 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3013 if (OpOpcode == ISD::UNDEF)
3014 return getUNDEF(VT);
3016 case ISD::SCALAR_TO_VECTOR:
3017 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3018 (VT.getVectorElementType() == Operand.getValueType() ||
3019 (VT.getVectorElementType().isInteger() &&
3020 Operand.getValueType().isInteger() &&
3021 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3022 "Illegal SCALAR_TO_VECTOR node!");
3023 if (OpOpcode == ISD::UNDEF)
3024 return getUNDEF(VT);
3025 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3026 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3027 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3028 Operand.getConstantOperandVal(1) == 0 &&
3029 Operand.getOperand(0).getValueType() == VT)
3030 return Operand.getOperand(0);
3033 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3034 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3035 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3036 Operand.getNode()->getOperand(0));
3037 if (OpOpcode == ISD::FNEG) // --X -> X
3038 return Operand.getNode()->getOperand(0);
3041 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3042 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3047 SDVTList VTs = getVTList(VT);
3048 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3049 FoldingSetNodeID ID;
3050 SDValue Ops[1] = { Operand };
3051 AddNodeIDNode(ID, Opcode, VTs, Ops);
3053 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3054 return SDValue(E, 0);
3056 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3057 DL.getDebugLoc(), VTs, Operand);
3058 CSEMap.InsertNode(N, IP);
3060 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3061 DL.getDebugLoc(), VTs, Operand);
3065 return SDValue(N, 0);
3068 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3069 SDNode *Cst1, SDNode *Cst2) {
3070 // If the opcode is a target-specific ISD node, there's nothing we can
3071 // do here and the operand rules may not line up with the below, so
3073 if (Opcode >= ISD::BUILTIN_OP_END)
3076 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
3077 SmallVector<SDValue, 4> Outputs;
3078 EVT SVT = VT.getScalarType();
3080 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
3081 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
3082 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
3085 if (Scalar1 && Scalar2)
3086 // Scalar instruction.
3087 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
3089 // For vectors extract each constant element into Inputs so we can constant
3090 // fold them individually.
3091 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3092 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3096 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3098 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3099 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3100 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3101 if (!V1 || !V2) // Not a constant, bail.
3104 if (V1->isOpaque() || V2->isOpaque())
3107 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3108 // FIXME: This is valid and could be handled by truncating the APInts.
3109 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3112 Inputs.push_back(std::make_pair(V1, V2));
3116 // We have a number of constant values, constant fold them element by element.
3117 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
3118 const APInt &C1 = Inputs[I].first->getAPIntValue();
3119 const APInt &C2 = Inputs[I].second->getAPIntValue();
3123 Outputs.push_back(getConstant(C1 + C2, DL, SVT));
3126 Outputs.push_back(getConstant(C1 - C2, DL, SVT));
3129 Outputs.push_back(getConstant(C1 * C2, DL, SVT));
3132 if (!C2.getBoolValue())
3134 Outputs.push_back(getConstant(C1.udiv(C2), DL, SVT));
3137 if (!C2.getBoolValue())
3139 Outputs.push_back(getConstant(C1.urem(C2), DL, SVT));
3142 if (!C2.getBoolValue())
3144 Outputs.push_back(getConstant(C1.sdiv(C2), DL, SVT));
3147 if (!C2.getBoolValue())
3149 Outputs.push_back(getConstant(C1.srem(C2), DL, SVT));
3152 Outputs.push_back(getConstant(C1 & C2, DL, SVT));
3155 Outputs.push_back(getConstant(C1 | C2, DL, SVT));
3158 Outputs.push_back(getConstant(C1 ^ C2, DL, SVT));
3161 Outputs.push_back(getConstant(C1 << C2, DL, SVT));
3164 Outputs.push_back(getConstant(C1.lshr(C2), DL, SVT));
3167 Outputs.push_back(getConstant(C1.ashr(C2), DL, SVT));
3170 Outputs.push_back(getConstant(C1.rotl(C2), DL, SVT));
3173 Outputs.push_back(getConstant(C1.rotr(C2), DL, SVT));
3180 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
3181 "Expected a scalar or vector!"));
3183 // Handle the scalar case first.
3185 return Outputs.back();
3187 // We may have a vector type but a scalar result. Create a splat.
3188 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3190 // Build a big vector out of the scalar elements we generated.
3191 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3194 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3195 SDValue N2, const SDNodeFlags *Flags) {
3196 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3197 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3200 case ISD::TokenFactor:
3201 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3202 N2.getValueType() == MVT::Other && "Invalid token factor!");
3203 // Fold trivial token factors.
3204 if (N1.getOpcode() == ISD::EntryToken) return N2;
3205 if (N2.getOpcode() == ISD::EntryToken) return N1;
3206 if (N1 == N2) return N1;
3208 case ISD::CONCAT_VECTORS:
3209 // Concat of UNDEFs is UNDEF.
3210 if (N1.getOpcode() == ISD::UNDEF &&
3211 N2.getOpcode() == ISD::UNDEF)
3212 return getUNDEF(VT);
3214 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3215 // one big BUILD_VECTOR.
3216 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3217 N2.getOpcode() == ISD::BUILD_VECTOR) {
3218 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3219 N1.getNode()->op_end());
3220 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3222 // BUILD_VECTOR requires all inputs to be of the same type, find the
3223 // maximum type and extend them all.
3224 EVT SVT = VT.getScalarType();
3225 for (SDValue Op : Elts)
3226 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3227 if (SVT.bitsGT(VT.getScalarType()))
3228 for (SDValue &Op : Elts)
3229 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3230 ? getZExtOrTrunc(Op, DL, SVT)
3231 : getSExtOrTrunc(Op, DL, SVT);
3233 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3237 assert(VT.isInteger() && "This operator does not apply to FP types!");
3238 assert(N1.getValueType() == N2.getValueType() &&
3239 N1.getValueType() == VT && "Binary operator types must match!");
3240 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3241 // worth handling here.
3242 if (N2C && N2C->isNullValue())
3244 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3251 assert(VT.isInteger() && "This operator does not apply to FP types!");
3252 assert(N1.getValueType() == N2.getValueType() &&
3253 N1.getValueType() == VT && "Binary operator types must match!");
3254 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3255 // it's worth handling here.
3256 if (N2C && N2C->isNullValue())
3266 assert(VT.isInteger() && "This operator does not apply to FP types!");
3267 assert(N1.getValueType() == N2.getValueType() &&
3268 N1.getValueType() == VT && "Binary operator types must match!");
3275 if (getTarget().Options.UnsafeFPMath) {
3276 if (Opcode == ISD::FADD) {
3278 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3279 if (CFP->getValueAPF().isZero())
3282 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3283 if (CFP->getValueAPF().isZero())
3285 } else if (Opcode == ISD::FSUB) {
3287 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3288 if (CFP->getValueAPF().isZero())
3290 } else if (Opcode == ISD::FMUL) {
3291 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3294 // If the first operand isn't the constant, try the second
3296 CFP = dyn_cast<ConstantFPSDNode>(N2);
3303 return SDValue(CFP,0);
3305 if (CFP->isExactlyValue(1.0))
3310 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3311 assert(N1.getValueType() == N2.getValueType() &&
3312 N1.getValueType() == VT && "Binary operator types must match!");
3314 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3315 assert(N1.getValueType() == VT &&
3316 N1.getValueType().isFloatingPoint() &&
3317 N2.getValueType().isFloatingPoint() &&
3318 "Invalid FCOPYSIGN!");
3325 assert(VT == N1.getValueType() &&
3326 "Shift operators return type must be the same as their first arg");
3327 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3328 "Shifts only work on integers");
3329 assert((!VT.isVector() || VT == N2.getValueType()) &&
3330 "Vector shift amounts must be in the same as their first arg");
3331 // Verify that the shift amount VT is bit enough to hold valid shift
3332 // amounts. This catches things like trying to shift an i1024 value by an
3333 // i8, which is easy to fall into in generic code that uses
3334 // TLI.getShiftAmount().
3335 assert(N2.getValueType().getSizeInBits() >=
3336 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3337 "Invalid use of small shift amount with oversized value!");
3339 // Always fold shifts of i1 values so the code generator doesn't need to
3340 // handle them. Since we know the size of the shift has to be less than the
3341 // size of the value, the shift/rotate count is guaranteed to be zero.
3344 if (N2C && N2C->isNullValue())
3347 case ISD::FP_ROUND_INREG: {
3348 EVT EVT = cast<VTSDNode>(N2)->getVT();
3349 assert(VT == N1.getValueType() && "Not an inreg round!");
3350 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3351 "Cannot FP_ROUND_INREG integer types");
3352 assert(EVT.isVector() == VT.isVector() &&
3353 "FP_ROUND_INREG type should be vector iff the operand "
3355 assert((!EVT.isVector() ||
3356 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3357 "Vector element counts must match in FP_ROUND_INREG");
3358 assert(EVT.bitsLE(VT) && "Not rounding down!");
3360 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3364 assert(VT.isFloatingPoint() &&
3365 N1.getValueType().isFloatingPoint() &&
3366 VT.bitsLE(N1.getValueType()) &&
3367 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3368 if (N1.getValueType() == VT) return N1; // noop conversion.
3370 case ISD::AssertSext:
3371 case ISD::AssertZext: {
3372 EVT EVT = cast<VTSDNode>(N2)->getVT();
3373 assert(VT == N1.getValueType() && "Not an inreg extend!");
3374 assert(VT.isInteger() && EVT.isInteger() &&
3375 "Cannot *_EXTEND_INREG FP types");
3376 assert(!EVT.isVector() &&
3377 "AssertSExt/AssertZExt type should be the vector element type "
3378 "rather than the vector type!");
3379 assert(EVT.bitsLE(VT) && "Not extending!");
3380 if (VT == EVT) return N1; // noop assertion.
3383 case ISD::SIGN_EXTEND_INREG: {
3384 EVT EVT = cast<VTSDNode>(N2)->getVT();
3385 assert(VT == N1.getValueType() && "Not an inreg extend!");
3386 assert(VT.isInteger() && EVT.isInteger() &&
3387 "Cannot *_EXTEND_INREG FP types");
3388 assert(EVT.isVector() == VT.isVector() &&
3389 "SIGN_EXTEND_INREG type should be vector iff the operand "
3391 assert((!EVT.isVector() ||
3392 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3393 "Vector element counts must match in SIGN_EXTEND_INREG");
3394 assert(EVT.bitsLE(VT) && "Not extending!");
3395 if (EVT == VT) return N1; // Not actually extending
3398 APInt Val = N1C->getAPIntValue();
3399 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3400 Val <<= Val.getBitWidth()-FromBits;
3401 Val = Val.ashr(Val.getBitWidth()-FromBits);
3402 return getConstant(Val, DL, VT);
3406 case ISD::EXTRACT_VECTOR_ELT:
3407 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3408 if (N1.getOpcode() == ISD::UNDEF)
3409 return getUNDEF(VT);
3411 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3412 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3413 return getUNDEF(VT);
3415 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3416 // expanding copies of large vectors from registers.
3418 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3419 N1.getNumOperands() > 0) {
3421 N1.getOperand(0).getValueType().getVectorNumElements();
3422 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3423 N1.getOperand(N2C->getZExtValue() / Factor),
3424 getConstant(N2C->getZExtValue() % Factor, DL,
3425 N2.getValueType()));
3428 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3429 // expanding large vector constants.
3430 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3431 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3433 if (VT != Elt.getValueType())
3434 // If the vector element type is not legal, the BUILD_VECTOR operands
3435 // are promoted and implicitly truncated, and the result implicitly
3436 // extended. Make that explicit here.
3437 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3442 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3443 // operations are lowered to scalars.
3444 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3445 // If the indices are the same, return the inserted element else
3446 // if the indices are known different, extract the element from
3447 // the original vector.
3448 SDValue N1Op2 = N1.getOperand(2);
3449 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3451 if (N1Op2C && N2C) {
3452 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3453 if (VT == N1.getOperand(1).getValueType())
3454 return N1.getOperand(1);
3456 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3459 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3463 case ISD::EXTRACT_ELEMENT:
3464 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3465 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3466 (N1.getValueType().isInteger() == VT.isInteger()) &&
3467 N1.getValueType() != VT &&
3468 "Wrong types for EXTRACT_ELEMENT!");
3470 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3471 // 64-bit integers into 32-bit parts. Instead of building the extract of
3472 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3473 if (N1.getOpcode() == ISD::BUILD_PAIR)
3474 return N1.getOperand(N2C->getZExtValue());
3476 // EXTRACT_ELEMENT of a constant int is also very common.
3477 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3478 unsigned ElementSize = VT.getSizeInBits();
3479 unsigned Shift = ElementSize * N2C->getZExtValue();
3480 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3481 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3484 case ISD::EXTRACT_SUBVECTOR: {
3486 if (VT.isSimple() && N1.getValueType().isSimple()) {
3487 assert(VT.isVector() && N1.getValueType().isVector() &&
3488 "Extract subvector VTs must be a vectors!");
3489 assert(VT.getVectorElementType() ==
3490 N1.getValueType().getVectorElementType() &&
3491 "Extract subvector VTs must have the same element type!");
3492 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3493 "Extract subvector must be from larger vector to smaller vector!");
3495 if (isa<ConstantSDNode>(Index.getNode())) {
3496 assert((VT.getVectorNumElements() +
3497 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3498 <= N1.getValueType().getVectorNumElements())
3499 && "Extract subvector overflow!");
3502 // Trivial extraction.
3503 if (VT.getSimpleVT() == N1.getSimpleValueType())
3510 // Perform trivial constant folding.
3512 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3515 // Canonicalize constant to RHS if commutative.
3516 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3517 std::swap(N1C, N2C);
3521 // Constant fold FP operations.
3522 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3523 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3524 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3526 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3527 // Canonicalize constant to RHS if commutative.
3528 std::swap(N1CFP, N2CFP);
3531 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3532 APFloat::opStatus s;
3535 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3536 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3537 return getConstantFP(V1, DL, VT);
3540 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3541 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3542 return getConstantFP(V1, DL, VT);
3545 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3546 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3547 return getConstantFP(V1, DL, VT);
3550 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3551 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3552 s!=APFloat::opDivByZero)) {
3553 return getConstantFP(V1, DL, VT);
3557 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3558 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3559 s!=APFloat::opDivByZero)) {
3560 return getConstantFP(V1, DL, VT);
3563 case ISD::FCOPYSIGN:
3565 return getConstantFP(V1, DL, VT);
3570 if (Opcode == ISD::FP_ROUND) {
3571 APFloat V = N1CFP->getValueAPF(); // make copy
3573 // This can return overflow, underflow, or inexact; we don't care.
3574 // FIXME need to be more flexible about rounding mode.
3575 (void)V.convert(EVTToAPFloatSemantics(VT),
3576 APFloat::rmNearestTiesToEven, &ignored);
3577 return getConstantFP(V, DL, VT);
3581 // Canonicalize an UNDEF to the RHS, even over a constant.
3582 if (N1.getOpcode() == ISD::UNDEF) {
3583 if (isCommutativeBinOp(Opcode)) {
3587 case ISD::FP_ROUND_INREG:
3588 case ISD::SIGN_EXTEND_INREG:
3594 return N1; // fold op(undef, arg2) -> undef
3602 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3603 // For vectors, we can't easily build an all zero vector, just return
3610 // Fold a bunch of operators when the RHS is undef.
3611 if (N2.getOpcode() == ISD::UNDEF) {
3614 if (N1.getOpcode() == ISD::UNDEF)
3615 // Handle undef ^ undef -> 0 special case. This is a common
3617 return getConstant(0, DL, VT);
3627 return N2; // fold op(arg1, undef) -> undef
3633 if (getTarget().Options.UnsafeFPMath)
3641 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3642 // For vectors, we can't easily build an all zero vector, just return
3647 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3648 // For vectors, we can't easily build an all one vector, just return
3656 // Memoize this node if possible.
3658 SDVTList VTs = getVTList(VT);
3659 SDValue Ops[] = { N1, N2 };
3660 if (VT != MVT::Glue) {
3661 SDValue Ops[] = {N1, N2};
3662 FoldingSetNodeID ID;
3663 AddNodeIDNode(ID, Opcode, VTs, Ops);
3664 AddNodeIDFlags(ID, Opcode, Flags);
3666 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3667 return SDValue(E, 0);
3669 N = GetSDNodeWithFlags(Opcode, DL, VTs, Ops, Flags);
3671 CSEMap.InsertNode(N, IP);
3673 N = GetSDNodeWithFlags(Opcode, DL, VTs, Ops, Flags);
3677 return SDValue(N, 0);
3680 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3681 SDValue N1, SDValue N2, SDValue N3) {
3682 // Perform various simplifications.
3683 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3686 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3687 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3688 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3689 if (N1CFP && N2CFP && N3CFP) {
3690 APFloat V1 = N1CFP->getValueAPF();
3691 const APFloat &V2 = N2CFP->getValueAPF();
3692 const APFloat &V3 = N3CFP->getValueAPF();
3693 APFloat::opStatus s =
3694 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3695 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3696 return getConstantFP(V1, DL, VT);
3700 case ISD::CONCAT_VECTORS:
3701 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3702 // one big BUILD_VECTOR.
3703 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3704 N2.getOpcode() == ISD::BUILD_VECTOR &&
3705 N3.getOpcode() == ISD::BUILD_VECTOR) {
3706 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3707 N1.getNode()->op_end());
3708 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3709 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3710 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3714 // Use FoldSetCC to simplify SETCC's.
3715 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3716 if (Simp.getNode()) return Simp;
3721 if (N1C->getZExtValue())
3722 return N2; // select true, X, Y -> X
3723 return N3; // select false, X, Y -> Y
3726 if (N2 == N3) return N2; // select C, X, X -> X
3728 case ISD::VECTOR_SHUFFLE:
3729 llvm_unreachable("should use getVectorShuffle constructor!");
3730 case ISD::INSERT_SUBVECTOR: {
3732 if (VT.isSimple() && N1.getValueType().isSimple()
3733 && N2.getValueType().isSimple()) {
3734 assert(VT.isVector() && N1.getValueType().isVector() &&
3735 N2.getValueType().isVector() &&
3736 "Insert subvector VTs must be a vectors");
3737 assert(VT == N1.getValueType() &&
3738 "Dest and insert subvector source types must match!");
3739 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3740 "Insert subvector must be from smaller vector to larger vector!");
3741 if (isa<ConstantSDNode>(Index.getNode())) {
3742 assert((N2.getValueType().getVectorNumElements() +
3743 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3744 <= VT.getVectorNumElements())
3745 && "Insert subvector overflow!");
3748 // Trivial insertion.
3749 if (VT.getSimpleVT() == N2.getSimpleValueType())
3755 // Fold bit_convert nodes from a type to themselves.
3756 if (N1.getValueType() == VT)
3761 // Memoize node if it doesn't produce a flag.
3763 SDVTList VTs = getVTList(VT);
3764 if (VT != MVT::Glue) {
3765 SDValue Ops[] = { N1, N2, N3 };
3766 FoldingSetNodeID ID;
3767 AddNodeIDNode(ID, Opcode, VTs, Ops);
3769 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3770 return SDValue(E, 0);
3772 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3773 DL.getDebugLoc(), VTs, N1, N2, N3);
3774 CSEMap.InsertNode(N, IP);
3776 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3777 DL.getDebugLoc(), VTs, N1, N2, N3);
3781 return SDValue(N, 0);
3784 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3785 SDValue N1, SDValue N2, SDValue N3,
3787 SDValue Ops[] = { N1, N2, N3, N4 };
3788 return getNode(Opcode, DL, VT, Ops);
3791 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3792 SDValue N1, SDValue N2, SDValue N3,
3793 SDValue N4, SDValue N5) {
3794 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3795 return getNode(Opcode, DL, VT, Ops);
3798 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3799 /// the incoming stack arguments to be loaded from the stack.
3800 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3801 SmallVector<SDValue, 8> ArgChains;
3803 // Include the original chain at the beginning of the list. When this is
3804 // used by target LowerCall hooks, this helps legalize find the
3805 // CALLSEQ_BEGIN node.
3806 ArgChains.push_back(Chain);
3808 // Add a chain value for each stack argument.
3809 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3810 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3811 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3812 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3813 if (FI->getIndex() < 0)
3814 ArgChains.push_back(SDValue(L, 1));
3816 // Build a tokenfactor for all the chains.
3817 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3820 /// getMemsetValue - Vectorized representation of the memset value
3822 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3824 assert(Value.getOpcode() != ISD::UNDEF);
3826 unsigned NumBits = VT.getScalarType().getSizeInBits();
3827 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3828 assert(C->getAPIntValue().getBitWidth() == 8);
3829 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3831 return DAG.getConstant(Val, dl, VT);
3832 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3836 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3837 EVT IntVT = VT.getScalarType();
3838 if (!IntVT.isInteger())
3839 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3841 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3843 // Use a multiplication with 0x010101... to extend the input to the
3845 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3846 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3847 DAG.getConstant(Magic, dl, IntVT));
3850 if (VT != Value.getValueType() && !VT.isInteger())
3851 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3852 if (VT != Value.getValueType()) {
3853 assert(VT.getVectorElementType() == Value.getValueType() &&
3854 "value type should be one vector element here");
3855 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3856 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3862 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3863 /// used when a memcpy is turned into a memset when the source is a constant
3865 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3866 const TargetLowering &TLI, StringRef Str) {
3867 // Handle vector with all elements zero.
3870 return DAG.getConstant(0, dl, VT);
3871 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3872 return DAG.getConstantFP(0.0, dl, VT);
3873 else if (VT.isVector()) {
3874 unsigned NumElts = VT.getVectorNumElements();
3875 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3876 return DAG.getNode(ISD::BITCAST, dl, VT,
3877 DAG.getConstant(0, dl,
3878 EVT::getVectorVT(*DAG.getContext(),
3881 llvm_unreachable("Expected type!");
3884 assert(!VT.isVector() && "Can't handle vector type here!");
3885 unsigned NumVTBits = VT.getSizeInBits();
3886 unsigned NumVTBytes = NumVTBits / 8;
3887 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3889 APInt Val(NumVTBits, 0);
3890 if (TLI.isLittleEndian()) {
3891 for (unsigned i = 0; i != NumBytes; ++i)
3892 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3894 for (unsigned i = 0; i != NumBytes; ++i)
3895 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3898 // If the "cost" of materializing the integer immediate is less than the cost
3899 // of a load, then it is cost effective to turn the load into the immediate.
3900 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3901 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3902 return DAG.getConstant(Val, dl, VT);
3903 return SDValue(nullptr, 0);
3906 /// getMemBasePlusOffset - Returns base and offset node for the
3908 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3909 SelectionDAG &DAG) {
3910 EVT VT = Base.getValueType();
3911 return DAG.getNode(ISD::ADD, dl,
3912 VT, Base, DAG.getConstant(Offset, dl, VT));
3915 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3917 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3918 unsigned SrcDelta = 0;
3919 GlobalAddressSDNode *G = nullptr;
3920 if (Src.getOpcode() == ISD::GlobalAddress)
3921 G = cast<GlobalAddressSDNode>(Src);
3922 else if (Src.getOpcode() == ISD::ADD &&
3923 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3924 Src.getOperand(1).getOpcode() == ISD::Constant) {
3925 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3926 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3931 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3934 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3935 /// to replace the memset / memcpy. Return true if the number of memory ops
3936 /// is below the threshold. It returns the types of the sequence of
3937 /// memory ops to perform memset / memcpy by reference.
3938 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3939 unsigned Limit, uint64_t Size,
3940 unsigned DstAlign, unsigned SrcAlign,
3946 const TargetLowering &TLI) {
3947 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3948 "Expecting memcpy / memset source to meet alignment requirement!");
3949 // If 'SrcAlign' is zero, that means the memory operation does not need to
3950 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3951 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3952 // is the specified alignment of the memory operation. If it is zero, that
3953 // means it's possible to change the alignment of the destination.
3954 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3955 // not need to be loaded.
3956 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3957 IsMemset, ZeroMemset, MemcpyStrSrc,
3958 DAG.getMachineFunction());
3960 if (VT == MVT::Other) {
3962 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3963 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3964 VT = TLI.getPointerTy();
3966 switch (DstAlign & 7) {
3967 case 0: VT = MVT::i64; break;
3968 case 4: VT = MVT::i32; break;
3969 case 2: VT = MVT::i16; break;
3970 default: VT = MVT::i8; break;
3975 while (!TLI.isTypeLegal(LVT))
3976 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3977 assert(LVT.isInteger());
3983 unsigned NumMemOps = 0;
3985 unsigned VTSize = VT.getSizeInBits() / 8;
3986 while (VTSize > Size) {
3987 // For now, only use non-vector load / store's for the left-over pieces.
3992 if (VT.isVector() || VT.isFloatingPoint()) {
3993 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3994 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3995 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3997 else if (NewVT == MVT::i64 &&
3998 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3999 TLI.isSafeMemOpType(MVT::f64)) {
4000 // i64 is usually not legal on 32-bit targets, but f64 may be.
4008 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4009 if (NewVT == MVT::i8)
4011 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4013 NewVTSize = NewVT.getSizeInBits() / 8;
4015 // If the new VT cannot cover all of the remaining bits, then consider
4016 // issuing a (or a pair of) unaligned and overlapping load / store.
4017 // FIXME: Only does this for 64-bit or more since we don't have proper
4018 // cost model for unaligned load / store.
4021 if (NumMemOps && AllowOverlap &&
4022 VTSize >= 8 && NewVTSize < Size &&
4023 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4031 if (++NumMemOps > Limit)
4034 MemOps.push_back(VT);
4041 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4042 SDValue Chain, SDValue Dst,
4043 SDValue Src, uint64_t Size,
4044 unsigned Align, bool isVol,
4046 MachinePointerInfo DstPtrInfo,
4047 MachinePointerInfo SrcPtrInfo) {
4048 // Turn a memcpy of undef to nop.
4049 if (Src.getOpcode() == ISD::UNDEF)
4052 // Expand memcpy to a series of load and store ops if the size operand falls
4053 // below a certain threshold.
4054 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4055 // rather than maybe a humongous number of loads and stores.
4056 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4057 std::vector<EVT> MemOps;
4058 bool DstAlignCanChange = false;
4059 MachineFunction &MF = DAG.getMachineFunction();
4060 MachineFrameInfo *MFI = MF.getFrameInfo();
4061 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4062 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4063 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4064 DstAlignCanChange = true;
4065 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4066 if (Align > SrcAlign)
4069 bool CopyFromStr = isMemSrcFromString(Src, Str);
4070 bool isZeroStr = CopyFromStr && Str.empty();
4071 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4073 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4074 (DstAlignCanChange ? 0 : Align),
4075 (isZeroStr ? 0 : SrcAlign),
4076 false, false, CopyFromStr, true, DAG, TLI))
4079 if (DstAlignCanChange) {
4080 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4081 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4083 // Don't promote to an alignment that would require dynamic stack
4085 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4086 if (!TRI->needsStackRealignment(MF))
4087 while (NewAlign > Align &&
4088 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4091 if (NewAlign > Align) {
4092 // Give the stack frame object a larger alignment if needed.
4093 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4094 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4099 SmallVector<SDValue, 8> OutChains;
4100 unsigned NumMemOps = MemOps.size();
4101 uint64_t SrcOff = 0, DstOff = 0;
4102 for (unsigned i = 0; i != NumMemOps; ++i) {
4104 unsigned VTSize = VT.getSizeInBits() / 8;
4105 SDValue Value, Store;
4107 if (VTSize > Size) {
4108 // Issuing an unaligned load / store pair that overlaps with the previous
4109 // pair. Adjust the offset accordingly.
4110 assert(i == NumMemOps-1 && i != 0);
4111 SrcOff -= VTSize - Size;
4112 DstOff -= VTSize - Size;
4116 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4117 // It's unlikely a store of a vector immediate can be done in a single
4118 // instruction. It would require a load from a constantpool first.
4119 // We only handle zero vectors here.
4120 // FIXME: Handle other cases where store of vector immediate is done in
4121 // a single instruction.
4122 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4123 if (Value.getNode())
4124 Store = DAG.getStore(Chain, dl, Value,
4125 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4126 DstPtrInfo.getWithOffset(DstOff), isVol,
4130 if (!Store.getNode()) {
4131 // The type might not be legal for the target. This should only happen
4132 // if the type is smaller than a legal type, as on PPC, so the right
4133 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4134 // to Load/Store if NVT==VT.
4135 // FIXME does the case above also need this?
4136 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4137 assert(NVT.bitsGE(VT));
4138 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4139 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4140 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4141 false, MinAlign(SrcAlign, SrcOff));
4142 Store = DAG.getTruncStore(Chain, dl, Value,
4143 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4144 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4147 OutChains.push_back(Store);
4153 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4156 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4157 SDValue Chain, SDValue Dst,
4158 SDValue Src, uint64_t Size,
4159 unsigned Align, bool isVol,
4161 MachinePointerInfo DstPtrInfo,
4162 MachinePointerInfo SrcPtrInfo) {
4163 // Turn a memmove of undef to nop.
4164 if (Src.getOpcode() == ISD::UNDEF)
4167 // Expand memmove to a series of load and store ops if the size operand falls
4168 // below a certain threshold.
4169 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4170 std::vector<EVT> MemOps;
4171 bool DstAlignCanChange = false;
4172 MachineFunction &MF = DAG.getMachineFunction();
4173 MachineFrameInfo *MFI = MF.getFrameInfo();
4174 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4175 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4176 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4177 DstAlignCanChange = true;
4178 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4179 if (Align > SrcAlign)
4181 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4183 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4184 (DstAlignCanChange ? 0 : Align), SrcAlign,
4185 false, false, false, false, DAG, TLI))
4188 if (DstAlignCanChange) {
4189 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4190 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4191 if (NewAlign > Align) {
4192 // Give the stack frame object a larger alignment if needed.
4193 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4194 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4199 uint64_t SrcOff = 0, DstOff = 0;
4200 SmallVector<SDValue, 8> LoadValues;
4201 SmallVector<SDValue, 8> LoadChains;
4202 SmallVector<SDValue, 8> OutChains;
4203 unsigned NumMemOps = MemOps.size();
4204 for (unsigned i = 0; i < NumMemOps; i++) {
4206 unsigned VTSize = VT.getSizeInBits() / 8;
4209 Value = DAG.getLoad(VT, dl, Chain,
4210 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4211 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4212 false, false, SrcAlign);
4213 LoadValues.push_back(Value);
4214 LoadChains.push_back(Value.getValue(1));
4217 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4219 for (unsigned i = 0; i < NumMemOps; i++) {
4221 unsigned VTSize = VT.getSizeInBits() / 8;
4224 Store = DAG.getStore(Chain, dl, LoadValues[i],
4225 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4226 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4227 OutChains.push_back(Store);
4231 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4234 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4237 /// \param DAG Selection DAG where lowered code is placed.
4238 /// \param dl Link to corresponding IR location.
4239 /// \param Chain Control flow dependency.
4240 /// \param Dst Pointer to destination memory location.
4241 /// \param Src Value of byte to write into the memory.
4242 /// \param Size Number of bytes to write.
4243 /// \param Align Alignment of the destination in bytes.
4244 /// \param isVol True if destination is volatile.
4245 /// \param DstPtrInfo IR information on the memory pointer.
4246 /// \returns New head in the control flow, if lowering was successful, empty
4247 /// SDValue otherwise.
4249 /// The function tries to replace 'llvm.memset' intrinsic with several store
4250 /// operations and value calculation code. This is usually profitable for small
4252 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4253 SDValue Chain, SDValue Dst,
4254 SDValue Src, uint64_t Size,
4255 unsigned Align, bool isVol,
4256 MachinePointerInfo DstPtrInfo) {
4257 // Turn a memset of undef to nop.
4258 if (Src.getOpcode() == ISD::UNDEF)
4261 // Expand memset to a series of load/store ops if the size operand
4262 // falls below a certain threshold.
4263 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4264 std::vector<EVT> MemOps;
4265 bool DstAlignCanChange = false;
4266 MachineFunction &MF = DAG.getMachineFunction();
4267 MachineFrameInfo *MFI = MF.getFrameInfo();
4268 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4269 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4270 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4271 DstAlignCanChange = true;
4273 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4274 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4275 Size, (DstAlignCanChange ? 0 : Align), 0,
4276 true, IsZeroVal, false, true, DAG, TLI))
4279 if (DstAlignCanChange) {
4280 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4281 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4282 if (NewAlign > Align) {
4283 // Give the stack frame object a larger alignment if needed.
4284 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4285 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4290 SmallVector<SDValue, 8> OutChains;
4291 uint64_t DstOff = 0;
4292 unsigned NumMemOps = MemOps.size();
4294 // Find the largest store and generate the bit pattern for it.
4295 EVT LargestVT = MemOps[0];
4296 for (unsigned i = 1; i < NumMemOps; i++)
4297 if (MemOps[i].bitsGT(LargestVT))
4298 LargestVT = MemOps[i];
4299 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4301 for (unsigned i = 0; i < NumMemOps; i++) {
4303 unsigned VTSize = VT.getSizeInBits() / 8;
4304 if (VTSize > Size) {
4305 // Issuing an unaligned load / store pair that overlaps with the previous
4306 // pair. Adjust the offset accordingly.
4307 assert(i == NumMemOps-1 && i != 0);
4308 DstOff -= VTSize - Size;
4311 // If this store is smaller than the largest store see whether we can get
4312 // the smaller value for free with a truncate.
4313 SDValue Value = MemSetValue;
4314 if (VT.bitsLT(LargestVT)) {
4315 if (!LargestVT.isVector() && !VT.isVector() &&
4316 TLI.isTruncateFree(LargestVT, VT))
4317 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4319 Value = getMemsetValue(Src, VT, DAG, dl);
4321 assert(Value.getValueType() == VT && "Value with wrong type.");
4322 SDValue Store = DAG.getStore(Chain, dl, Value,
4323 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4324 DstPtrInfo.getWithOffset(DstOff),
4325 isVol, false, Align);
4326 OutChains.push_back(Store);
4327 DstOff += VT.getSizeInBits() / 8;
4331 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4334 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4335 SDValue Src, SDValue Size,
4336 unsigned Align, bool isVol, bool AlwaysInline,
4337 bool isTailCall, MachinePointerInfo DstPtrInfo,
4338 MachinePointerInfo SrcPtrInfo) {
4339 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4341 // Check to see if we should lower the memcpy to loads and stores first.
4342 // For cases within the target-specified limits, this is the best choice.
4343 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4345 // Memcpy with size zero? Just return the original chain.
4346 if (ConstantSize->isNullValue())
4349 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4350 ConstantSize->getZExtValue(),Align,
4351 isVol, false, DstPtrInfo, SrcPtrInfo);
4352 if (Result.getNode())
4356 // Then check to see if we should lower the memcpy with target-specific
4357 // code. If the target chooses to do this, this is the next best.
4359 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4360 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4361 DstPtrInfo, SrcPtrInfo);
4362 if (Result.getNode())
4366 // If we really need inline code and the target declined to provide it,
4367 // use a (potentially long) sequence of loads and stores.
4369 assert(ConstantSize && "AlwaysInline requires a constant size!");
4370 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4371 ConstantSize->getZExtValue(), Align, isVol,
4372 true, DstPtrInfo, SrcPtrInfo);
4375 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4376 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4377 // respect volatile, so they may do things like read or write memory
4378 // beyond the given memory regions. But fixing this isn't easy, and most
4379 // people don't care.
4381 // Emit a library call.
4382 TargetLowering::ArgListTy Args;
4383 TargetLowering::ArgListEntry Entry;
4384 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4385 Entry.Node = Dst; Args.push_back(Entry);
4386 Entry.Node = Src; Args.push_back(Entry);
4387 Entry.Node = Size; Args.push_back(Entry);
4388 // FIXME: pass in SDLoc
4389 TargetLowering::CallLoweringInfo CLI(*this);
4390 CLI.setDebugLoc(dl).setChain(Chain)
4391 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4392 Type::getVoidTy(*getContext()),
4393 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4394 TLI->getPointerTy()), std::move(Args), 0)
4396 .setTailCall(isTailCall);
4398 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4399 return CallResult.second;
4402 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4403 SDValue Src, SDValue Size,
4404 unsigned Align, bool isVol, bool isTailCall,
4405 MachinePointerInfo DstPtrInfo,
4406 MachinePointerInfo SrcPtrInfo) {
4407 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4409 // Check to see if we should lower the memmove to loads and stores first.
4410 // For cases within the target-specified limits, this is the best choice.
4411 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4413 // Memmove with size zero? Just return the original chain.
4414 if (ConstantSize->isNullValue())
4418 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4419 ConstantSize->getZExtValue(), Align, isVol,
4420 false, DstPtrInfo, SrcPtrInfo);
4421 if (Result.getNode())
4425 // Then check to see if we should lower the memmove with target-specific
4426 // code. If the target chooses to do this, this is the next best.
4428 SDValue Result = TSI->EmitTargetCodeForMemmove(
4429 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4430 if (Result.getNode())
4434 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4435 // not be safe. See memcpy above for more details.
4437 // Emit a library call.
4438 TargetLowering::ArgListTy Args;
4439 TargetLowering::ArgListEntry Entry;
4440 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4441 Entry.Node = Dst; Args.push_back(Entry);
4442 Entry.Node = Src; Args.push_back(Entry);
4443 Entry.Node = Size; Args.push_back(Entry);
4444 // FIXME: pass in SDLoc
4445 TargetLowering::CallLoweringInfo CLI(*this);
4446 CLI.setDebugLoc(dl).setChain(Chain)
4447 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4448 Type::getVoidTy(*getContext()),
4449 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4450 TLI->getPointerTy()), std::move(Args), 0)
4452 .setTailCall(isTailCall);
4454 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4455 return CallResult.second;
4458 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4459 SDValue Src, SDValue Size,
4460 unsigned Align, bool isVol, bool isTailCall,
4461 MachinePointerInfo DstPtrInfo) {
4462 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4464 // Check to see if we should lower the memset to stores first.
4465 // For cases within the target-specified limits, this is the best choice.
4466 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4468 // Memset with size zero? Just return the original chain.
4469 if (ConstantSize->isNullValue())
4473 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4474 Align, isVol, DstPtrInfo);
4476 if (Result.getNode())
4480 // Then check to see if we should lower the memset with target-specific
4481 // code. If the target chooses to do this, this is the next best.
4483 SDValue Result = TSI->EmitTargetCodeForMemset(
4484 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4485 if (Result.getNode())
4489 // Emit a library call.
4490 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4491 TargetLowering::ArgListTy Args;
4492 TargetLowering::ArgListEntry Entry;
4493 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4494 Args.push_back(Entry);
4496 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4497 Args.push_back(Entry);
4499 Entry.Ty = IntPtrTy;
4500 Args.push_back(Entry);
4502 // FIXME: pass in SDLoc
4503 TargetLowering::CallLoweringInfo CLI(*this);
4504 CLI.setDebugLoc(dl).setChain(Chain)
4505 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4506 Type::getVoidTy(*getContext()),
4507 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4508 TLI->getPointerTy()), std::move(Args), 0)
4510 .setTailCall(isTailCall);
4512 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4513 return CallResult.second;
4516 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4517 SDVTList VTList, ArrayRef<SDValue> Ops,
4518 MachineMemOperand *MMO,
4519 AtomicOrdering SuccessOrdering,
4520 AtomicOrdering FailureOrdering,
4521 SynchronizationScope SynchScope) {
4522 FoldingSetNodeID ID;
4523 ID.AddInteger(MemVT.getRawBits());
4524 AddNodeIDNode(ID, Opcode, VTList, Ops);
4525 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4527 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4528 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4529 return SDValue(E, 0);
4532 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4533 // SDNode doesn't have access to it. This memory will be "leaked" when
4534 // the node is deallocated, but recovered when the allocator is released.
4535 // If the number of operands is less than 5 we use AtomicSDNode's internal
4537 unsigned NumOps = Ops.size();
4538 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4541 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4542 dl.getDebugLoc(), VTList, MemVT,
4543 Ops.data(), DynOps, NumOps, MMO,
4544 SuccessOrdering, FailureOrdering,
4546 CSEMap.InsertNode(N, IP);
4548 return SDValue(N, 0);
4551 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4552 SDVTList VTList, ArrayRef<SDValue> Ops,
4553 MachineMemOperand *MMO,
4554 AtomicOrdering Ordering,
4555 SynchronizationScope SynchScope) {
4556 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4557 Ordering, SynchScope);
4560 SDValue SelectionDAG::getAtomicCmpSwap(
4561 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4562 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4563 unsigned Alignment, AtomicOrdering SuccessOrdering,
4564 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4565 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4566 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4567 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4569 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4570 Alignment = getEVTAlignment(MemVT);
4572 MachineFunction &MF = getMachineFunction();
4574 // FIXME: Volatile isn't really correct; we should keep track of atomic
4575 // orderings in the memoperand.
4576 unsigned Flags = MachineMemOperand::MOVolatile;
4577 Flags |= MachineMemOperand::MOLoad;
4578 Flags |= MachineMemOperand::MOStore;
4580 MachineMemOperand *MMO =
4581 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4583 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4584 SuccessOrdering, FailureOrdering, SynchScope);
4587 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4588 SDVTList VTs, SDValue Chain, SDValue Ptr,
4589 SDValue Cmp, SDValue Swp,
4590 MachineMemOperand *MMO,
4591 AtomicOrdering SuccessOrdering,
4592 AtomicOrdering FailureOrdering,
4593 SynchronizationScope SynchScope) {
4594 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4595 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4596 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4598 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4599 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4600 SuccessOrdering, FailureOrdering, SynchScope);
4603 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4605 SDValue Ptr, SDValue Val,
4606 const Value* PtrVal,
4608 AtomicOrdering Ordering,
4609 SynchronizationScope SynchScope) {
4610 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4611 Alignment = getEVTAlignment(MemVT);
4613 MachineFunction &MF = getMachineFunction();
4614 // An atomic store does not load. An atomic load does not store.
4615 // (An atomicrmw obviously both loads and stores.)
4616 // For now, atomics are considered to be volatile always, and they are
4618 // FIXME: Volatile isn't really correct; we should keep track of atomic
4619 // orderings in the memoperand.
4620 unsigned Flags = MachineMemOperand::MOVolatile;
4621 if (Opcode != ISD::ATOMIC_STORE)
4622 Flags |= MachineMemOperand::MOLoad;
4623 if (Opcode != ISD::ATOMIC_LOAD)
4624 Flags |= MachineMemOperand::MOStore;
4626 MachineMemOperand *MMO =
4627 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4628 MemVT.getStoreSize(), Alignment);
4630 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4631 Ordering, SynchScope);
4634 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4636 SDValue Ptr, SDValue Val,
4637 MachineMemOperand *MMO,
4638 AtomicOrdering Ordering,
4639 SynchronizationScope SynchScope) {
4640 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4641 Opcode == ISD::ATOMIC_LOAD_SUB ||
4642 Opcode == ISD::ATOMIC_LOAD_AND ||
4643 Opcode == ISD::ATOMIC_LOAD_OR ||
4644 Opcode == ISD::ATOMIC_LOAD_XOR ||
4645 Opcode == ISD::ATOMIC_LOAD_NAND ||
4646 Opcode == ISD::ATOMIC_LOAD_MIN ||
4647 Opcode == ISD::ATOMIC_LOAD_MAX ||
4648 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4649 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4650 Opcode == ISD::ATOMIC_SWAP ||
4651 Opcode == ISD::ATOMIC_STORE) &&
4652 "Invalid Atomic Op");
4654 EVT VT = Val.getValueType();
4656 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4657 getVTList(VT, MVT::Other);
4658 SDValue Ops[] = {Chain, Ptr, Val};
4659 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4662 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4663 EVT VT, SDValue Chain,
4665 MachineMemOperand *MMO,
4666 AtomicOrdering Ordering,
4667 SynchronizationScope SynchScope) {
4668 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4670 SDVTList VTs = getVTList(VT, MVT::Other);
4671 SDValue Ops[] = {Chain, Ptr};
4672 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4675 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4676 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4677 if (Ops.size() == 1)
4680 SmallVector<EVT, 4> VTs;
4681 VTs.reserve(Ops.size());
4682 for (unsigned i = 0; i < Ops.size(); ++i)
4683 VTs.push_back(Ops[i].getValueType());
4684 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4688 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4689 ArrayRef<SDValue> Ops,
4690 EVT MemVT, MachinePointerInfo PtrInfo,
4691 unsigned Align, bool Vol,
4692 bool ReadMem, bool WriteMem, unsigned Size) {
4693 if (Align == 0) // Ensure that codegen never sees alignment 0
4694 Align = getEVTAlignment(MemVT);
4696 MachineFunction &MF = getMachineFunction();
4699 Flags |= MachineMemOperand::MOStore;
4701 Flags |= MachineMemOperand::MOLoad;
4703 Flags |= MachineMemOperand::MOVolatile;
4705 Size = MemVT.getStoreSize();
4706 MachineMemOperand *MMO =
4707 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4709 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4713 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4714 ArrayRef<SDValue> Ops, EVT MemVT,
4715 MachineMemOperand *MMO) {
4716 assert((Opcode == ISD::INTRINSIC_VOID ||
4717 Opcode == ISD::INTRINSIC_W_CHAIN ||
4718 Opcode == ISD::PREFETCH ||
4719 Opcode == ISD::LIFETIME_START ||
4720 Opcode == ISD::LIFETIME_END ||
4721 (Opcode <= INT_MAX &&
4722 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4723 "Opcode is not a memory-accessing opcode!");
4725 // Memoize the node unless it returns a flag.
4726 MemIntrinsicSDNode *N;
4727 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4728 FoldingSetNodeID ID;
4729 AddNodeIDNode(ID, Opcode, VTList, Ops);
4730 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4732 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4733 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4734 return SDValue(E, 0);
4737 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4738 dl.getDebugLoc(), VTList, Ops,
4740 CSEMap.InsertNode(N, IP);
4742 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4743 dl.getDebugLoc(), VTList, Ops,
4747 return SDValue(N, 0);
4750 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4751 /// MachinePointerInfo record from it. This is particularly useful because the
4752 /// code generator has many cases where it doesn't bother passing in a
4753 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4754 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4755 // If this is FI+Offset, we can model it.
4756 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4757 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4759 // If this is (FI+Offset1)+Offset2, we can model it.
4760 if (Ptr.getOpcode() != ISD::ADD ||
4761 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4762 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4763 return MachinePointerInfo();
4765 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4766 return MachinePointerInfo::getFixedStack(FI, Offset+
4767 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4770 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4771 /// MachinePointerInfo record from it. This is particularly useful because the
4772 /// code generator has many cases where it doesn't bother passing in a
4773 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4774 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4775 // If the 'Offset' value isn't a constant, we can't handle this.
4776 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4777 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4778 if (OffsetOp.getOpcode() == ISD::UNDEF)
4779 return InferPointerInfo(Ptr);
4780 return MachinePointerInfo();
4785 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4786 EVT VT, SDLoc dl, SDValue Chain,
4787 SDValue Ptr, SDValue Offset,
4788 MachinePointerInfo PtrInfo, EVT MemVT,
4789 bool isVolatile, bool isNonTemporal, bool isInvariant,
4790 unsigned Alignment, const AAMDNodes &AAInfo,
4791 const MDNode *Ranges) {
4792 assert(Chain.getValueType() == MVT::Other &&
4793 "Invalid chain type");
4794 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4795 Alignment = getEVTAlignment(VT);
4797 unsigned Flags = MachineMemOperand::MOLoad;
4799 Flags |= MachineMemOperand::MOVolatile;
4801 Flags |= MachineMemOperand::MONonTemporal;
4803 Flags |= MachineMemOperand::MOInvariant;
4805 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4807 if (PtrInfo.V.isNull())
4808 PtrInfo = InferPointerInfo(Ptr, Offset);
4810 MachineFunction &MF = getMachineFunction();
4811 MachineMemOperand *MMO =
4812 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4814 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4818 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4819 EVT VT, SDLoc dl, SDValue Chain,
4820 SDValue Ptr, SDValue Offset, EVT MemVT,
4821 MachineMemOperand *MMO) {
4823 ExtType = ISD::NON_EXTLOAD;
4824 } else if (ExtType == ISD::NON_EXTLOAD) {
4825 assert(VT == MemVT && "Non-extending load from different memory type!");
4828 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4829 "Should only be an extending load, not truncating!");
4830 assert(VT.isInteger() == MemVT.isInteger() &&
4831 "Cannot convert from FP to Int or Int -> FP!");
4832 assert(VT.isVector() == MemVT.isVector() &&
4833 "Cannot use an ext load to convert to or from a vector!");
4834 assert((!VT.isVector() ||
4835 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4836 "Cannot use an ext load to change the number of vector elements!");
4839 bool Indexed = AM != ISD::UNINDEXED;
4840 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4841 "Unindexed load with an offset!");
4843 SDVTList VTs = Indexed ?
4844 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4845 SDValue Ops[] = { Chain, Ptr, Offset };
4846 FoldingSetNodeID ID;
4847 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4848 ID.AddInteger(MemVT.getRawBits());
4849 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4850 MMO->isNonTemporal(),
4851 MMO->isInvariant()));
4852 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4854 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4855 cast<LoadSDNode>(E)->refineAlignment(MMO);
4856 return SDValue(E, 0);
4858 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4859 dl.getDebugLoc(), VTs, AM, ExtType,
4861 CSEMap.InsertNode(N, IP);
4863 return SDValue(N, 0);
4866 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4867 SDValue Chain, SDValue Ptr,
4868 MachinePointerInfo PtrInfo,
4869 bool isVolatile, bool isNonTemporal,
4870 bool isInvariant, unsigned Alignment,
4871 const AAMDNodes &AAInfo,
4872 const MDNode *Ranges) {
4873 SDValue Undef = getUNDEF(Ptr.getValueType());
4874 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4875 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4879 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4880 SDValue Chain, SDValue Ptr,
4881 MachineMemOperand *MMO) {
4882 SDValue Undef = getUNDEF(Ptr.getValueType());
4883 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4887 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4888 SDValue Chain, SDValue Ptr,
4889 MachinePointerInfo PtrInfo, EVT MemVT,
4890 bool isVolatile, bool isNonTemporal,
4891 bool isInvariant, unsigned Alignment,
4892 const AAMDNodes &AAInfo) {
4893 SDValue Undef = getUNDEF(Ptr.getValueType());
4894 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4895 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4900 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4901 SDValue Chain, SDValue Ptr, EVT MemVT,
4902 MachineMemOperand *MMO) {
4903 SDValue Undef = getUNDEF(Ptr.getValueType());
4904 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4909 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4910 SDValue Offset, ISD::MemIndexedMode AM) {
4911 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4912 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4913 "Load is already a indexed load!");
4914 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4915 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4916 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4917 false, LD->getAlignment());
4920 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4921 SDValue Ptr, MachinePointerInfo PtrInfo,
4922 bool isVolatile, bool isNonTemporal,
4923 unsigned Alignment, const AAMDNodes &AAInfo) {
4924 assert(Chain.getValueType() == MVT::Other &&
4925 "Invalid chain type");
4926 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4927 Alignment = getEVTAlignment(Val.getValueType());
4929 unsigned Flags = MachineMemOperand::MOStore;
4931 Flags |= MachineMemOperand::MOVolatile;
4933 Flags |= MachineMemOperand::MONonTemporal;
4935 if (PtrInfo.V.isNull())
4936 PtrInfo = InferPointerInfo(Ptr);
4938 MachineFunction &MF = getMachineFunction();
4939 MachineMemOperand *MMO =
4940 MF.getMachineMemOperand(PtrInfo, Flags,
4941 Val.getValueType().getStoreSize(), Alignment,
4944 return getStore(Chain, dl, Val, Ptr, MMO);
4947 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4948 SDValue Ptr, MachineMemOperand *MMO) {
4949 assert(Chain.getValueType() == MVT::Other &&
4950 "Invalid chain type");
4951 EVT VT = Val.getValueType();
4952 SDVTList VTs = getVTList(MVT::Other);
4953 SDValue Undef = getUNDEF(Ptr.getValueType());
4954 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4955 FoldingSetNodeID ID;
4956 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4957 ID.AddInteger(VT.getRawBits());
4958 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4959 MMO->isNonTemporal(), MMO->isInvariant()));
4960 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4962 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4963 cast<StoreSDNode>(E)->refineAlignment(MMO);
4964 return SDValue(E, 0);
4966 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4967 dl.getDebugLoc(), VTs,
4968 ISD::UNINDEXED, false, VT, MMO);
4969 CSEMap.InsertNode(N, IP);
4971 return SDValue(N, 0);
4974 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4975 SDValue Ptr, MachinePointerInfo PtrInfo,
4976 EVT SVT,bool isVolatile, bool isNonTemporal,
4978 const AAMDNodes &AAInfo) {
4979 assert(Chain.getValueType() == MVT::Other &&
4980 "Invalid chain type");
4981 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4982 Alignment = getEVTAlignment(SVT);
4984 unsigned Flags = MachineMemOperand::MOStore;
4986 Flags |= MachineMemOperand::MOVolatile;
4988 Flags |= MachineMemOperand::MONonTemporal;
4990 if (PtrInfo.V.isNull())
4991 PtrInfo = InferPointerInfo(Ptr);
4993 MachineFunction &MF = getMachineFunction();
4994 MachineMemOperand *MMO =
4995 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4998 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5001 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5002 SDValue Ptr, EVT SVT,
5003 MachineMemOperand *MMO) {
5004 EVT VT = Val.getValueType();
5006 assert(Chain.getValueType() == MVT::Other &&
5007 "Invalid chain type");
5009 return getStore(Chain, dl, Val, Ptr, MMO);
5011 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5012 "Should only be a truncating store, not extending!");
5013 assert(VT.isInteger() == SVT.isInteger() &&
5014 "Can't do FP-INT conversion!");
5015 assert(VT.isVector() == SVT.isVector() &&
5016 "Cannot use trunc store to convert to or from a vector!");
5017 assert((!VT.isVector() ||
5018 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5019 "Cannot use trunc store to change the number of vector elements!");
5021 SDVTList VTs = getVTList(MVT::Other);
5022 SDValue Undef = getUNDEF(Ptr.getValueType());
5023 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5024 FoldingSetNodeID ID;
5025 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5026 ID.AddInteger(SVT.getRawBits());
5027 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5028 MMO->isNonTemporal(), MMO->isInvariant()));
5029 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5031 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5032 cast<StoreSDNode>(E)->refineAlignment(MMO);
5033 return SDValue(E, 0);
5035 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5036 dl.getDebugLoc(), VTs,
5037 ISD::UNINDEXED, true, SVT, MMO);
5038 CSEMap.InsertNode(N, IP);
5040 return SDValue(N, 0);
5044 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5045 SDValue Offset, ISD::MemIndexedMode AM) {
5046 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5047 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5048 "Store is already a indexed store!");
5049 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5050 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5051 FoldingSetNodeID ID;
5052 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5053 ID.AddInteger(ST->getMemoryVT().getRawBits());
5054 ID.AddInteger(ST->getRawSubclassData());
5055 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5057 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5058 return SDValue(E, 0);
5060 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5061 dl.getDebugLoc(), VTs, AM,
5062 ST->isTruncatingStore(),
5064 ST->getMemOperand());
5065 CSEMap.InsertNode(N, IP);
5067 return SDValue(N, 0);
5071 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5072 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5073 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5075 SDVTList VTs = getVTList(VT, MVT::Other);
5076 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5077 FoldingSetNodeID ID;
5078 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5079 ID.AddInteger(VT.getRawBits());
5080 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5082 MMO->isNonTemporal(),
5083 MMO->isInvariant()));
5084 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5086 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5087 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5088 return SDValue(E, 0);
5090 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5091 dl.getDebugLoc(), Ops, 4, VTs,
5093 CSEMap.InsertNode(N, IP);
5095 return SDValue(N, 0);
5098 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5099 SDValue Ptr, SDValue Mask, EVT MemVT,
5100 MachineMemOperand *MMO, bool isTrunc) {
5101 assert(Chain.getValueType() == MVT::Other &&
5102 "Invalid chain type");
5103 EVT VT = Val.getValueType();
5104 SDVTList VTs = getVTList(MVT::Other);
5105 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5106 FoldingSetNodeID ID;
5107 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5108 ID.AddInteger(VT.getRawBits());
5109 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5110 MMO->isNonTemporal(), MMO->isInvariant()));
5111 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5113 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5114 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5115 return SDValue(E, 0);
5117 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5118 dl.getDebugLoc(), Ops, 4,
5119 VTs, isTrunc, MemVT, MMO);
5120 CSEMap.InsertNode(N, IP);
5122 return SDValue(N, 0);
5126 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5127 ArrayRef<SDValue> Ops,
5128 MachineMemOperand *MMO) {
5130 FoldingSetNodeID ID;
5131 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5132 ID.AddInteger(VT.getRawBits());
5133 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5135 MMO->isNonTemporal(),
5136 MMO->isInvariant()));
5137 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5139 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5140 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5141 return SDValue(E, 0);
5143 MaskedGatherSDNode *N =
5144 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5146 CSEMap.InsertNode(N, IP);
5148 return SDValue(N, 0);
5151 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5152 ArrayRef<SDValue> Ops,
5153 MachineMemOperand *MMO) {
5154 FoldingSetNodeID ID;
5155 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5156 ID.AddInteger(VT.getRawBits());
5157 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5158 MMO->isNonTemporal(),
5159 MMO->isInvariant()));
5160 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5162 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5163 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5164 return SDValue(E, 0);
5167 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5169 CSEMap.InsertNode(N, IP);
5171 return SDValue(N, 0);
5174 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5175 SDValue Chain, SDValue Ptr,
5178 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5179 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5182 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5183 ArrayRef<SDUse> Ops) {
5184 switch (Ops.size()) {
5185 case 0: return getNode(Opcode, DL, VT);
5186 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5187 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5188 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5192 // Copy from an SDUse array into an SDValue array for use with
5193 // the regular getNode logic.
5194 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5195 return getNode(Opcode, DL, VT, NewOps);
5198 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5199 ArrayRef<SDValue> Ops) {
5200 unsigned NumOps = Ops.size();
5202 case 0: return getNode(Opcode, DL, VT);
5203 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5204 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5205 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5211 case ISD::SELECT_CC: {
5212 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5213 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5214 "LHS and RHS of condition must have same type!");
5215 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5216 "True and False arms of SelectCC must have same type!");
5217 assert(Ops[2].getValueType() == VT &&
5218 "select_cc node must be of same type as true and false value!");
5222 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5223 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5224 "LHS/RHS of comparison should match types!");
5231 SDVTList VTs = getVTList(VT);
5233 if (VT != MVT::Glue) {
5234 FoldingSetNodeID ID;
5235 AddNodeIDNode(ID, Opcode, VTs, Ops);
5238 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5239 return SDValue(E, 0);
5241 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5243 CSEMap.InsertNode(N, IP);
5245 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5250 return SDValue(N, 0);
5253 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5254 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5255 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5258 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5259 ArrayRef<SDValue> Ops) {
5260 if (VTList.NumVTs == 1)
5261 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5265 // FIXME: figure out how to safely handle things like
5266 // int foo(int x) { return 1 << (x & 255); }
5267 // int bar() { return foo(256); }
5268 case ISD::SRA_PARTS:
5269 case ISD::SRL_PARTS:
5270 case ISD::SHL_PARTS:
5271 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5272 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5273 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5274 else if (N3.getOpcode() == ISD::AND)
5275 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5276 // If the and is only masking out bits that cannot effect the shift,
5277 // eliminate the and.
5278 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5279 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5280 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5286 // Memoize the node unless it returns a flag.
5288 unsigned NumOps = Ops.size();
5289 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5290 FoldingSetNodeID ID;
5291 AddNodeIDNode(ID, Opcode, VTList, Ops);
5293 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5294 return SDValue(E, 0);
5297 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5298 DL.getDebugLoc(), VTList, Ops[0]);
5299 } else if (NumOps == 2) {
5300 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5301 DL.getDebugLoc(), VTList, Ops[0],
5303 } else if (NumOps == 3) {
5304 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5305 DL.getDebugLoc(), VTList, Ops[0],
5308 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5311 CSEMap.InsertNode(N, IP);
5314 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5315 DL.getDebugLoc(), VTList, Ops[0]);
5316 } else if (NumOps == 2) {
5317 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5318 DL.getDebugLoc(), VTList, Ops[0],
5320 } else if (NumOps == 3) {
5321 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5322 DL.getDebugLoc(), VTList, Ops[0],
5325 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5330 return SDValue(N, 0);
5333 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5334 return getNode(Opcode, DL, VTList, None);
5337 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5339 SDValue Ops[] = { N1 };
5340 return getNode(Opcode, DL, VTList, Ops);
5343 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5344 SDValue N1, SDValue N2) {
5345 SDValue Ops[] = { N1, N2 };
5346 return getNode(Opcode, DL, VTList, Ops);
5349 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5350 SDValue N1, SDValue N2, SDValue N3) {
5351 SDValue Ops[] = { N1, N2, N3 };
5352 return getNode(Opcode, DL, VTList, Ops);
5355 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5356 SDValue N1, SDValue N2, SDValue N3,
5358 SDValue Ops[] = { N1, N2, N3, N4 };
5359 return getNode(Opcode, DL, VTList, Ops);
5362 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5363 SDValue N1, SDValue N2, SDValue N3,
5364 SDValue N4, SDValue N5) {
5365 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5366 return getNode(Opcode, DL, VTList, Ops);
5369 SDVTList SelectionDAG::getVTList(EVT VT) {
5370 return makeVTList(SDNode::getValueTypeList(VT), 1);
5373 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5374 FoldingSetNodeID ID;
5376 ID.AddInteger(VT1.getRawBits());
5377 ID.AddInteger(VT2.getRawBits());
5380 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5382 EVT *Array = Allocator.Allocate<EVT>(2);
5385 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5386 VTListMap.InsertNode(Result, IP);
5388 return Result->getSDVTList();
5391 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5392 FoldingSetNodeID ID;
5394 ID.AddInteger(VT1.getRawBits());
5395 ID.AddInteger(VT2.getRawBits());
5396 ID.AddInteger(VT3.getRawBits());
5399 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5401 EVT *Array = Allocator.Allocate<EVT>(3);
5405 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5406 VTListMap.InsertNode(Result, IP);
5408 return Result->getSDVTList();
5411 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5412 FoldingSetNodeID ID;
5414 ID.AddInteger(VT1.getRawBits());
5415 ID.AddInteger(VT2.getRawBits());
5416 ID.AddInteger(VT3.getRawBits());
5417 ID.AddInteger(VT4.getRawBits());
5420 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5422 EVT *Array = Allocator.Allocate<EVT>(4);
5427 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5428 VTListMap.InsertNode(Result, IP);
5430 return Result->getSDVTList();
5433 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5434 unsigned NumVTs = VTs.size();
5435 FoldingSetNodeID ID;
5436 ID.AddInteger(NumVTs);
5437 for (unsigned index = 0; index < NumVTs; index++) {
5438 ID.AddInteger(VTs[index].getRawBits());
5442 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5444 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5445 std::copy(VTs.begin(), VTs.end(), Array);
5446 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5447 VTListMap.InsertNode(Result, IP);
5449 return Result->getSDVTList();
5453 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5454 /// specified operands. If the resultant node already exists in the DAG,
5455 /// this does not modify the specified node, instead it returns the node that
5456 /// already exists. If the resultant node does not exist in the DAG, the
5457 /// input node is returned. As a degenerate case, if you specify the same
5458 /// input operands as the node already has, the input node is returned.
5459 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5460 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5462 // Check to see if there is no change.
5463 if (Op == N->getOperand(0)) return N;
5465 // See if the modified node already exists.
5466 void *InsertPos = nullptr;
5467 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5470 // Nope it doesn't. Remove the node from its current place in the maps.
5472 if (!RemoveNodeFromCSEMaps(N))
5473 InsertPos = nullptr;
5475 // Now we update the operands.
5476 N->OperandList[0].set(Op);
5478 // If this gets put into a CSE map, add it.
5479 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5483 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5484 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5486 // Check to see if there is no change.
5487 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5488 return N; // No operands changed, just return the input node.
5490 // See if the modified node already exists.
5491 void *InsertPos = nullptr;
5492 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5495 // Nope it doesn't. Remove the node from its current place in the maps.
5497 if (!RemoveNodeFromCSEMaps(N))
5498 InsertPos = nullptr;
5500 // Now we update the operands.
5501 if (N->OperandList[0] != Op1)
5502 N->OperandList[0].set(Op1);
5503 if (N->OperandList[1] != Op2)
5504 N->OperandList[1].set(Op2);
5506 // If this gets put into a CSE map, add it.
5507 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5511 SDNode *SelectionDAG::
5512 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5513 SDValue Ops[] = { Op1, Op2, Op3 };
5514 return UpdateNodeOperands(N, Ops);
5517 SDNode *SelectionDAG::
5518 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5519 SDValue Op3, SDValue Op4) {
5520 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5521 return UpdateNodeOperands(N, Ops);
5524 SDNode *SelectionDAG::
5525 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5526 SDValue Op3, SDValue Op4, SDValue Op5) {
5527 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5528 return UpdateNodeOperands(N, Ops);
5531 SDNode *SelectionDAG::
5532 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5533 unsigned NumOps = Ops.size();
5534 assert(N->getNumOperands() == NumOps &&
5535 "Update with wrong number of operands");
5537 // If no operands changed just return the input node.
5538 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5541 // See if the modified node already exists.
5542 void *InsertPos = nullptr;
5543 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5546 // Nope it doesn't. Remove the node from its current place in the maps.
5548 if (!RemoveNodeFromCSEMaps(N))
5549 InsertPos = nullptr;
5551 // Now we update the operands.
5552 for (unsigned i = 0; i != NumOps; ++i)
5553 if (N->OperandList[i] != Ops[i])
5554 N->OperandList[i].set(Ops[i]);
5556 // If this gets put into a CSE map, add it.
5557 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5561 /// DropOperands - Release the operands and set this node to have
5563 void SDNode::DropOperands() {
5564 // Unlike the code in MorphNodeTo that does this, we don't need to
5565 // watch for dead nodes here.
5566 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5572 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5575 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5577 SDVTList VTs = getVTList(VT);
5578 return SelectNodeTo(N, MachineOpc, VTs, None);
5581 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5582 EVT VT, SDValue Op1) {
5583 SDVTList VTs = getVTList(VT);
5584 SDValue Ops[] = { Op1 };
5585 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5588 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5589 EVT VT, SDValue Op1,
5591 SDVTList VTs = getVTList(VT);
5592 SDValue Ops[] = { Op1, Op2 };
5593 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5596 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5597 EVT VT, SDValue Op1,
5598 SDValue Op2, SDValue Op3) {
5599 SDVTList VTs = getVTList(VT);
5600 SDValue Ops[] = { Op1, Op2, Op3 };
5601 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5604 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5605 EVT VT, ArrayRef<SDValue> Ops) {
5606 SDVTList VTs = getVTList(VT);
5607 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5610 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5611 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5612 SDVTList VTs = getVTList(VT1, VT2);
5613 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5616 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5618 SDVTList VTs = getVTList(VT1, VT2);
5619 return SelectNodeTo(N, MachineOpc, VTs, None);
5622 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5623 EVT VT1, EVT VT2, EVT VT3,
5624 ArrayRef<SDValue> Ops) {
5625 SDVTList VTs = getVTList(VT1, VT2, VT3);
5626 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5629 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5630 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5631 ArrayRef<SDValue> Ops) {
5632 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5633 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5636 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5639 SDVTList VTs = getVTList(VT1, VT2);
5640 SDValue Ops[] = { Op1 };
5641 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5644 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5646 SDValue Op1, SDValue Op2) {
5647 SDVTList VTs = getVTList(VT1, VT2);
5648 SDValue Ops[] = { Op1, Op2 };
5649 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5652 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5654 SDValue Op1, SDValue Op2,
5656 SDVTList VTs = getVTList(VT1, VT2);
5657 SDValue Ops[] = { Op1, Op2, Op3 };
5658 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5661 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5662 EVT VT1, EVT VT2, EVT VT3,
5663 SDValue Op1, SDValue Op2,
5665 SDVTList VTs = getVTList(VT1, VT2, VT3);
5666 SDValue Ops[] = { Op1, Op2, Op3 };
5667 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5670 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5671 SDVTList VTs,ArrayRef<SDValue> Ops) {
5672 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5673 // Reset the NodeID to -1.
5678 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5679 /// the line number information on the merged node since it is not possible to
5680 /// preserve the information that operation is associated with multiple lines.
5681 /// This will make the debugger working better at -O0, were there is a higher
5682 /// probability having other instructions associated with that line.
5684 /// For IROrder, we keep the smaller of the two
5685 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5686 DebugLoc NLoc = N->getDebugLoc();
5687 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5688 N->setDebugLoc(DebugLoc());
5690 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5691 N->setIROrder(Order);
5695 /// MorphNodeTo - This *mutates* the specified node to have the specified
5696 /// return type, opcode, and operands.
5698 /// Note that MorphNodeTo returns the resultant node. If there is already a
5699 /// node of the specified opcode and operands, it returns that node instead of
5700 /// the current one. Note that the SDLoc need not be the same.
5702 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5703 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5704 /// node, and because it doesn't require CSE recalculation for any of
5705 /// the node's users.
5707 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5708 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5709 /// the legalizer which maintain worklists that would need to be updated when
5710 /// deleting things.
5711 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5712 SDVTList VTs, ArrayRef<SDValue> Ops) {
5713 unsigned NumOps = Ops.size();
5714 // If an identical node already exists, use it.
5716 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5717 FoldingSetNodeID ID;
5718 AddNodeIDNode(ID, Opc, VTs, Ops);
5719 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5720 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5723 if (!RemoveNodeFromCSEMaps(N))
5726 // Start the morphing.
5728 N->ValueList = VTs.VTs;
5729 N->NumValues = VTs.NumVTs;
5731 // Clear the operands list, updating used nodes to remove this from their
5732 // use list. Keep track of any operands that become dead as a result.
5733 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5734 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5736 SDNode *Used = Use.getNode();
5738 if (Used->use_empty())
5739 DeadNodeSet.insert(Used);
5742 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5743 // Initialize the memory references information.
5744 MN->setMemRefs(nullptr, nullptr);
5745 // If NumOps is larger than the # of operands we can have in a
5746 // MachineSDNode, reallocate the operand list.
5747 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5748 if (MN->OperandsNeedDelete)
5749 delete[] MN->OperandList;
5750 if (NumOps > array_lengthof(MN->LocalOperands))
5751 // We're creating a final node that will live unmorphed for the
5752 // remainder of the current SelectionDAG iteration, so we can allocate
5753 // the operands directly out of a pool with no recycling metadata.
5754 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5755 Ops.data(), NumOps);
5757 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5758 MN->OperandsNeedDelete = false;
5760 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5762 // If NumOps is larger than the # of operands we currently have, reallocate
5763 // the operand list.
5764 if (NumOps > N->NumOperands) {
5765 if (N->OperandsNeedDelete)
5766 delete[] N->OperandList;
5767 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5768 N->OperandsNeedDelete = true;
5770 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5773 // Delete any nodes that are still dead after adding the uses for the
5775 if (!DeadNodeSet.empty()) {
5776 SmallVector<SDNode *, 16> DeadNodes;
5777 for (SDNode *N : DeadNodeSet)
5779 DeadNodes.push_back(N);
5780 RemoveDeadNodes(DeadNodes);
5784 CSEMap.InsertNode(N, IP); // Memoize the new node.
5789 /// getMachineNode - These are used for target selectors to create a new node
5790 /// with specified return type(s), MachineInstr opcode, and operands.
5792 /// Note that getMachineNode returns the resultant node. If there is already a
5793 /// node of the specified opcode and operands, it returns that node instead of
5794 /// the current one.
5796 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5797 SDVTList VTs = getVTList(VT);
5798 return getMachineNode(Opcode, dl, VTs, None);
5802 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5803 SDVTList VTs = getVTList(VT);
5804 SDValue Ops[] = { Op1 };
5805 return getMachineNode(Opcode, dl, VTs, Ops);
5809 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5810 SDValue Op1, SDValue Op2) {
5811 SDVTList VTs = getVTList(VT);
5812 SDValue Ops[] = { Op1, Op2 };
5813 return getMachineNode(Opcode, dl, VTs, Ops);
5817 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5818 SDValue Op1, SDValue Op2, SDValue Op3) {
5819 SDVTList VTs = getVTList(VT);
5820 SDValue Ops[] = { Op1, Op2, Op3 };
5821 return getMachineNode(Opcode, dl, VTs, Ops);
5825 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5826 ArrayRef<SDValue> Ops) {
5827 SDVTList VTs = getVTList(VT);
5828 return getMachineNode(Opcode, dl, VTs, Ops);
5832 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5833 SDVTList VTs = getVTList(VT1, VT2);
5834 return getMachineNode(Opcode, dl, VTs, None);
5838 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5839 EVT VT1, EVT VT2, SDValue Op1) {
5840 SDVTList VTs = getVTList(VT1, VT2);
5841 SDValue Ops[] = { Op1 };
5842 return getMachineNode(Opcode, dl, VTs, Ops);
5846 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5847 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5848 SDVTList VTs = getVTList(VT1, VT2);
5849 SDValue Ops[] = { Op1, Op2 };
5850 return getMachineNode(Opcode, dl, VTs, Ops);
5854 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5855 EVT VT1, EVT VT2, SDValue Op1,
5856 SDValue Op2, SDValue Op3) {
5857 SDVTList VTs = getVTList(VT1, VT2);
5858 SDValue Ops[] = { Op1, Op2, Op3 };
5859 return getMachineNode(Opcode, dl, VTs, Ops);
5863 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5865 ArrayRef<SDValue> Ops) {
5866 SDVTList VTs = getVTList(VT1, VT2);
5867 return getMachineNode(Opcode, dl, VTs, Ops);
5871 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5872 EVT VT1, EVT VT2, EVT VT3,
5873 SDValue Op1, SDValue Op2) {
5874 SDVTList VTs = getVTList(VT1, VT2, VT3);
5875 SDValue Ops[] = { Op1, Op2 };
5876 return getMachineNode(Opcode, dl, VTs, Ops);
5880 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5881 EVT VT1, EVT VT2, EVT VT3,
5882 SDValue Op1, SDValue Op2, SDValue Op3) {
5883 SDVTList VTs = getVTList(VT1, VT2, VT3);
5884 SDValue Ops[] = { Op1, Op2, Op3 };
5885 return getMachineNode(Opcode, dl, VTs, Ops);
5889 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5890 EVT VT1, EVT VT2, EVT VT3,
5891 ArrayRef<SDValue> Ops) {
5892 SDVTList VTs = getVTList(VT1, VT2, VT3);
5893 return getMachineNode(Opcode, dl, VTs, Ops);
5897 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5898 EVT VT2, EVT VT3, EVT VT4,
5899 ArrayRef<SDValue> Ops) {
5900 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5901 return getMachineNode(Opcode, dl, VTs, Ops);
5905 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5906 ArrayRef<EVT> ResultTys,
5907 ArrayRef<SDValue> Ops) {
5908 SDVTList VTs = getVTList(ResultTys);
5909 return getMachineNode(Opcode, dl, VTs, Ops);
5913 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5914 ArrayRef<SDValue> OpsArray) {
5915 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5918 const SDValue *Ops = OpsArray.data();
5919 unsigned NumOps = OpsArray.size();
5922 FoldingSetNodeID ID;
5923 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5925 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5926 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5930 // Allocate a new MachineSDNode.
5931 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5932 DL.getDebugLoc(), VTs);
5934 // Initialize the operands list.
5935 if (NumOps > array_lengthof(N->LocalOperands))
5936 // We're creating a final node that will live unmorphed for the
5937 // remainder of the current SelectionDAG iteration, so we can allocate
5938 // the operands directly out of a pool with no recycling metadata.
5939 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5942 N->InitOperands(N->LocalOperands, Ops, NumOps);
5943 N->OperandsNeedDelete = false;
5946 CSEMap.InsertNode(N, IP);
5952 /// getTargetExtractSubreg - A convenience function for creating
5953 /// TargetOpcode::EXTRACT_SUBREG nodes.
5955 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5957 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5958 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5959 VT, Operand, SRIdxVal);
5960 return SDValue(Subreg, 0);
5963 /// getTargetInsertSubreg - A convenience function for creating
5964 /// TargetOpcode::INSERT_SUBREG nodes.
5966 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5967 SDValue Operand, SDValue Subreg) {
5968 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5969 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5970 VT, Operand, Subreg, SRIdxVal);
5971 return SDValue(Result, 0);
5974 /// getNodeIfExists - Get the specified node if it's already available, or
5975 /// else return NULL.
5976 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5977 ArrayRef<SDValue> Ops,
5978 const SDNodeFlags *Flags) {
5979 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5980 FoldingSetNodeID ID;
5981 AddNodeIDNode(ID, Opcode, VTList, Ops);
5982 AddNodeIDFlags(ID, Opcode, Flags);
5984 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5990 /// getDbgValue - Creates a SDDbgValue node.
5993 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5994 unsigned R, bool IsIndirect, uint64_t Off,
5995 DebugLoc DL, unsigned O) {
5996 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5997 "Expected inlined-at fields to agree");
5998 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6002 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6003 const Value *C, uint64_t Off,
6004 DebugLoc DL, unsigned O) {
6005 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6006 "Expected inlined-at fields to agree");
6007 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6011 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6012 unsigned FI, uint64_t Off,
6013 DebugLoc DL, unsigned O) {
6014 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6015 "Expected inlined-at fields to agree");
6016 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6021 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6022 /// pointed to by a use iterator is deleted, increment the use iterator
6023 /// so that it doesn't dangle.
6025 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6026 SDNode::use_iterator &UI;
6027 SDNode::use_iterator &UE;
6029 void NodeDeleted(SDNode *N, SDNode *E) override {
6030 // Increment the iterator as needed.
6031 while (UI != UE && N == *UI)
6036 RAUWUpdateListener(SelectionDAG &d,
6037 SDNode::use_iterator &ui,
6038 SDNode::use_iterator &ue)
6039 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6044 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6045 /// This can cause recursive merging of nodes in the DAG.
6047 /// This version assumes From has a single result value.
6049 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6050 SDNode *From = FromN.getNode();
6051 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6052 "Cannot replace with this method!");
6053 assert(From != To.getNode() && "Cannot replace uses of with self");
6055 // Iterate over all the existing uses of From. New uses will be added
6056 // to the beginning of the use list, which we avoid visiting.
6057 // This specifically avoids visiting uses of From that arise while the
6058 // replacement is happening, because any such uses would be the result
6059 // of CSE: If an existing node looks like From after one of its operands
6060 // is replaced by To, we don't want to replace of all its users with To
6061 // too. See PR3018 for more info.
6062 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6063 RAUWUpdateListener Listener(*this, UI, UE);
6067 // This node is about to morph, remove its old self from the CSE maps.
6068 RemoveNodeFromCSEMaps(User);
6070 // A user can appear in a use list multiple times, and when this
6071 // happens the uses are usually next to each other in the list.
6072 // To help reduce the number of CSE recomputations, process all
6073 // the uses of this user that we can find this way.
6075 SDUse &Use = UI.getUse();
6078 } while (UI != UE && *UI == User);
6080 // Now that we have modified User, add it back to the CSE maps. If it
6081 // already exists there, recursively merge the results together.
6082 AddModifiedNodeToCSEMaps(User);
6085 // If we just RAUW'd the root, take note.
6086 if (FromN == getRoot())
6090 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6091 /// This can cause recursive merging of nodes in the DAG.
6093 /// This version assumes that for each value of From, there is a
6094 /// corresponding value in To in the same position with the same type.
6096 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6098 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6099 assert((!From->hasAnyUseOfValue(i) ||
6100 From->getValueType(i) == To->getValueType(i)) &&
6101 "Cannot use this version of ReplaceAllUsesWith!");
6104 // Handle the trivial case.
6108 // Iterate over just the existing users of From. See the comments in
6109 // the ReplaceAllUsesWith above.
6110 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6111 RAUWUpdateListener Listener(*this, UI, UE);
6115 // This node is about to morph, remove its old self from the CSE maps.
6116 RemoveNodeFromCSEMaps(User);
6118 // A user can appear in a use list multiple times, and when this
6119 // happens the uses are usually next to each other in the list.
6120 // To help reduce the number of CSE recomputations, process all
6121 // the uses of this user that we can find this way.
6123 SDUse &Use = UI.getUse();
6126 } while (UI != UE && *UI == User);
6128 // Now that we have modified User, add it back to the CSE maps. If it
6129 // already exists there, recursively merge the results together.
6130 AddModifiedNodeToCSEMaps(User);
6133 // If we just RAUW'd the root, take note.
6134 if (From == getRoot().getNode())
6135 setRoot(SDValue(To, getRoot().getResNo()));
6138 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6139 /// This can cause recursive merging of nodes in the DAG.
6141 /// This version can replace From with any result values. To must match the
6142 /// number and types of values returned by From.
6143 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6144 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6145 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6147 // Iterate over just the existing users of From. See the comments in
6148 // the ReplaceAllUsesWith above.
6149 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6150 RAUWUpdateListener Listener(*this, UI, UE);
6154 // This node is about to morph, remove its old self from the CSE maps.
6155 RemoveNodeFromCSEMaps(User);
6157 // A user can appear in a use list multiple times, and when this
6158 // happens the uses are usually next to each other in the list.
6159 // To help reduce the number of CSE recomputations, process all
6160 // the uses of this user that we can find this way.
6162 SDUse &Use = UI.getUse();
6163 const SDValue &ToOp = To[Use.getResNo()];
6166 } while (UI != UE && *UI == User);
6168 // Now that we have modified User, add it back to the CSE maps. If it
6169 // already exists there, recursively merge the results together.
6170 AddModifiedNodeToCSEMaps(User);
6173 // If we just RAUW'd the root, take note.
6174 if (From == getRoot().getNode())
6175 setRoot(SDValue(To[getRoot().getResNo()]));
6178 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6179 /// uses of other values produced by From.getNode() alone. The Deleted
6180 /// vector is handled the same way as for ReplaceAllUsesWith.
6181 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6182 // Handle the really simple, really trivial case efficiently.
6183 if (From == To) return;
6185 // Handle the simple, trivial, case efficiently.
6186 if (From.getNode()->getNumValues() == 1) {
6187 ReplaceAllUsesWith(From, To);
6191 // Iterate over just the existing users of From. See the comments in
6192 // the ReplaceAllUsesWith above.
6193 SDNode::use_iterator UI = From.getNode()->use_begin(),
6194 UE = From.getNode()->use_end();
6195 RAUWUpdateListener Listener(*this, UI, UE);
6198 bool UserRemovedFromCSEMaps = false;
6200 // A user can appear in a use list multiple times, and when this
6201 // happens the uses are usually next to each other in the list.
6202 // To help reduce the number of CSE recomputations, process all
6203 // the uses of this user that we can find this way.
6205 SDUse &Use = UI.getUse();
6207 // Skip uses of different values from the same node.
6208 if (Use.getResNo() != From.getResNo()) {
6213 // If this node hasn't been modified yet, it's still in the CSE maps,
6214 // so remove its old self from the CSE maps.
6215 if (!UserRemovedFromCSEMaps) {
6216 RemoveNodeFromCSEMaps(User);
6217 UserRemovedFromCSEMaps = true;
6222 } while (UI != UE && *UI == User);
6224 // We are iterating over all uses of the From node, so if a use
6225 // doesn't use the specific value, no changes are made.
6226 if (!UserRemovedFromCSEMaps)
6229 // Now that we have modified User, add it back to the CSE maps. If it
6230 // already exists there, recursively merge the results together.
6231 AddModifiedNodeToCSEMaps(User);
6234 // If we just RAUW'd the root, take note.
6235 if (From == getRoot())
6240 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6241 /// to record information about a use.
6248 /// operator< - Sort Memos by User.
6249 bool operator<(const UseMemo &L, const UseMemo &R) {
6250 return (intptr_t)L.User < (intptr_t)R.User;
6254 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6255 /// uses of other values produced by From.getNode() alone. The same value
6256 /// may appear in both the From and To list. The Deleted vector is
6257 /// handled the same way as for ReplaceAllUsesWith.
6258 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6261 // Handle the simple, trivial case efficiently.
6263 return ReplaceAllUsesOfValueWith(*From, *To);
6265 // Read up all the uses and make records of them. This helps
6266 // processing new uses that are introduced during the
6267 // replacement process.
6268 SmallVector<UseMemo, 4> Uses;
6269 for (unsigned i = 0; i != Num; ++i) {
6270 unsigned FromResNo = From[i].getResNo();
6271 SDNode *FromNode = From[i].getNode();
6272 for (SDNode::use_iterator UI = FromNode->use_begin(),
6273 E = FromNode->use_end(); UI != E; ++UI) {
6274 SDUse &Use = UI.getUse();
6275 if (Use.getResNo() == FromResNo) {
6276 UseMemo Memo = { *UI, i, &Use };
6277 Uses.push_back(Memo);
6282 // Sort the uses, so that all the uses from a given User are together.
6283 std::sort(Uses.begin(), Uses.end());
6285 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6286 UseIndex != UseIndexEnd; ) {
6287 // We know that this user uses some value of From. If it is the right
6288 // value, update it.
6289 SDNode *User = Uses[UseIndex].User;
6291 // This node is about to morph, remove its old self from the CSE maps.
6292 RemoveNodeFromCSEMaps(User);
6294 // The Uses array is sorted, so all the uses for a given User
6295 // are next to each other in the list.
6296 // To help reduce the number of CSE recomputations, process all
6297 // the uses of this user that we can find this way.
6299 unsigned i = Uses[UseIndex].Index;
6300 SDUse &Use = *Uses[UseIndex].Use;
6304 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6306 // Now that we have modified User, add it back to the CSE maps. If it
6307 // already exists there, recursively merge the results together.
6308 AddModifiedNodeToCSEMaps(User);
6312 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6313 /// based on their topological order. It returns the maximum id and a vector
6314 /// of the SDNodes* in assigned order by reference.
6315 unsigned SelectionDAG::AssignTopologicalOrder() {
6317 unsigned DAGSize = 0;
6319 // SortedPos tracks the progress of the algorithm. Nodes before it are
6320 // sorted, nodes after it are unsorted. When the algorithm completes
6321 // it is at the end of the list.
6322 allnodes_iterator SortedPos = allnodes_begin();
6324 // Visit all the nodes. Move nodes with no operands to the front of
6325 // the list immediately. Annotate nodes that do have operands with their
6326 // operand count. Before we do this, the Node Id fields of the nodes
6327 // may contain arbitrary values. After, the Node Id fields for nodes
6328 // before SortedPos will contain the topological sort index, and the
6329 // Node Id fields for nodes At SortedPos and after will contain the
6330 // count of outstanding operands.
6331 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6333 checkForCycles(N, this);
6334 unsigned Degree = N->getNumOperands();
6336 // A node with no uses, add it to the result array immediately.
6337 N->setNodeId(DAGSize++);
6338 allnodes_iterator Q = N;
6340 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6341 assert(SortedPos != AllNodes.end() && "Overran node list");
6344 // Temporarily use the Node Id as scratch space for the degree count.
6345 N->setNodeId(Degree);
6349 // Visit all the nodes. As we iterate, move nodes into sorted order,
6350 // such that by the time the end is reached all nodes will be sorted.
6351 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6353 checkForCycles(N, this);
6354 // N is in sorted position, so all its uses have one less operand
6355 // that needs to be sorted.
6356 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6359 unsigned Degree = P->getNodeId();
6360 assert(Degree != 0 && "Invalid node degree");
6363 // All of P's operands are sorted, so P may sorted now.
6364 P->setNodeId(DAGSize++);
6366 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6367 assert(SortedPos != AllNodes.end() && "Overran node list");
6370 // Update P's outstanding operand count.
6371 P->setNodeId(Degree);
6374 if (I == SortedPos) {
6377 dbgs() << "Overran sorted position:\n";
6378 S->dumprFull(this); dbgs() << "\n";
6379 dbgs() << "Checking if this is due to cycles\n";
6380 checkForCycles(this, true);
6382 llvm_unreachable(nullptr);
6386 assert(SortedPos == AllNodes.end() &&
6387 "Topological sort incomplete!");
6388 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6389 "First node in topological sort is not the entry token!");
6390 assert(AllNodes.front().getNodeId() == 0 &&
6391 "First node in topological sort has non-zero id!");
6392 assert(AllNodes.front().getNumOperands() == 0 &&
6393 "First node in topological sort has operands!");
6394 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6395 "Last node in topologic sort has unexpected id!");
6396 assert(AllNodes.back().use_empty() &&
6397 "Last node in topologic sort has users!");
6398 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6402 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6403 /// value is produced by SD.
6404 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6406 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6407 SD->setHasDebugValue(true);
6409 DbgInfo->add(DB, SD, isParameter);
6412 /// TransferDbgValues - Transfer SDDbgValues.
6413 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6414 if (From == To || !From.getNode()->getHasDebugValue())
6416 SDNode *FromNode = From.getNode();
6417 SDNode *ToNode = To.getNode();
6418 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6419 SmallVector<SDDbgValue *, 2> ClonedDVs;
6420 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6422 SDDbgValue *Dbg = *I;
6423 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6425 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6426 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6427 Dbg->getDebugLoc(), Dbg->getOrder());
6428 ClonedDVs.push_back(Clone);
6431 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6432 E = ClonedDVs.end(); I != E; ++I)
6433 AddDbgValue(*I, ToNode, false);
6436 //===----------------------------------------------------------------------===//
6438 //===----------------------------------------------------------------------===//
6440 HandleSDNode::~HandleSDNode() {
6444 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6445 DebugLoc DL, const GlobalValue *GA,
6446 EVT VT, int64_t o, unsigned char TF)
6447 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6451 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6452 SDValue X, unsigned SrcAS,
6454 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6455 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6457 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6458 EVT memvt, MachineMemOperand *mmo)
6459 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6460 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6461 MMO->isNonTemporal(), MMO->isInvariant());
6462 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6463 assert(isNonTemporal() == MMO->isNonTemporal() &&
6464 "Non-temporal encoding error!");
6465 // We check here that the size of the memory operand fits within the size of
6466 // the MMO. This is because the MMO might indicate only a possible address
6467 // range instead of specifying the affected memory addresses precisely.
6468 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6471 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6472 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6473 : SDNode(Opc, Order, dl, VTs, Ops),
6474 MemoryVT(memvt), MMO(mmo) {
6475 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6476 MMO->isNonTemporal(), MMO->isInvariant());
6477 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6478 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6481 /// Profile - Gather unique data for the node.
6483 void SDNode::Profile(FoldingSetNodeID &ID) const {
6484 AddNodeIDNode(ID, this);
6489 std::vector<EVT> VTs;
6492 VTs.reserve(MVT::LAST_VALUETYPE);
6493 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6494 VTs.push_back(MVT((MVT::SimpleValueType)i));
6499 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6500 static ManagedStatic<EVTArray> SimpleVTArray;
6501 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6503 /// getValueTypeList - Return a pointer to the specified value type.
6505 const EVT *SDNode::getValueTypeList(EVT VT) {
6506 if (VT.isExtended()) {
6507 sys::SmartScopedLock<true> Lock(*VTMutex);
6508 return &(*EVTs->insert(VT).first);
6510 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6511 "Value type out of range!");
6512 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6516 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6517 /// indicated value. This method ignores uses of other values defined by this
6519 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6520 assert(Value < getNumValues() && "Bad value!");
6522 // TODO: Only iterate over uses of a given value of the node
6523 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6524 if (UI.getUse().getResNo() == Value) {
6531 // Found exactly the right number of uses?
6536 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6537 /// value. This method ignores uses of other values defined by this operation.
6538 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6539 assert(Value < getNumValues() && "Bad value!");
6541 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6542 if (UI.getUse().getResNo() == Value)
6549 /// isOnlyUserOf - Return true if this node is the only use of N.
6551 bool SDNode::isOnlyUserOf(SDNode *N) const {
6553 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6564 /// isOperand - Return true if this node is an operand of N.
6566 bool SDValue::isOperandOf(SDNode *N) const {
6567 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6568 if (*this == N->getOperand(i))
6573 bool SDNode::isOperandOf(SDNode *N) const {
6574 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6575 if (this == N->OperandList[i].getNode())
6580 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6581 /// be a chain) reaches the specified operand without crossing any
6582 /// side-effecting instructions on any chain path. In practice, this looks
6583 /// through token factors and non-volatile loads. In order to remain efficient,
6584 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6585 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6586 unsigned Depth) const {
6587 if (*this == Dest) return true;
6589 // Don't search too deeply, we just want to be able to see through
6590 // TokenFactor's etc.
6591 if (Depth == 0) return false;
6593 // If this is a token factor, all inputs to the TF happen in parallel. If any
6594 // of the operands of the TF does not reach dest, then we cannot do the xform.
6595 if (getOpcode() == ISD::TokenFactor) {
6596 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6597 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6602 // Loads don't have side effects, look through them.
6603 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6604 if (!Ld->isVolatile())
6605 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6610 /// hasPredecessor - Return true if N is a predecessor of this node.
6611 /// N is either an operand of this node, or can be reached by recursively
6612 /// traversing up the operands.
6613 /// NOTE: This is an expensive method. Use it carefully.
6614 bool SDNode::hasPredecessor(const SDNode *N) const {
6615 SmallPtrSet<const SDNode *, 32> Visited;
6616 SmallVector<const SDNode *, 16> Worklist;
6617 return hasPredecessorHelper(N, Visited, Worklist);
6621 SDNode::hasPredecessorHelper(const SDNode *N,
6622 SmallPtrSetImpl<const SDNode *> &Visited,
6623 SmallVectorImpl<const SDNode *> &Worklist) const {
6624 if (Visited.empty()) {
6625 Worklist.push_back(this);
6627 // Take a look in the visited set. If we've already encountered this node
6628 // we needn't search further.
6629 if (Visited.count(N))
6633 // Haven't visited N yet. Continue the search.
6634 while (!Worklist.empty()) {
6635 const SDNode *M = Worklist.pop_back_val();
6636 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6637 SDNode *Op = M->getOperand(i).getNode();
6638 if (Visited.insert(Op).second)
6639 Worklist.push_back(Op);
6648 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6649 assert(Num < NumOperands && "Invalid child # of SDNode!");
6650 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6653 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6654 assert(N->getNumValues() == 1 &&
6655 "Can't unroll a vector with multiple results!");
6657 EVT VT = N->getValueType(0);
6658 unsigned NE = VT.getVectorNumElements();
6659 EVT EltVT = VT.getVectorElementType();
6662 SmallVector<SDValue, 8> Scalars;
6663 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6665 // If ResNE is 0, fully unroll the vector op.
6668 else if (NE > ResNE)
6672 for (i= 0; i != NE; ++i) {
6673 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6674 SDValue Operand = N->getOperand(j);
6675 EVT OperandVT = Operand.getValueType();
6676 if (OperandVT.isVector()) {
6677 // A vector operand; extract a single element.
6678 EVT OperandEltVT = OperandVT.getVectorElementType();
6679 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6682 getConstant(i, dl, TLI->getVectorIdxTy()));
6684 // A scalar operand; just use it as is.
6685 Operands[j] = Operand;
6689 switch (N->getOpcode()) {
6691 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6694 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6701 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6702 getShiftAmountOperand(Operands[0].getValueType(),
6705 case ISD::SIGN_EXTEND_INREG:
6706 case ISD::FP_ROUND_INREG: {
6707 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6708 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6710 getValueType(ExtVT)));
6715 for (; i < ResNE; ++i)
6716 Scalars.push_back(getUNDEF(EltVT));
6718 return getNode(ISD::BUILD_VECTOR, dl,
6719 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6723 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6724 /// location that is 'Dist' units away from the location that the 'Base' load
6725 /// is loading from.
6726 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6727 unsigned Bytes, int Dist) const {
6728 if (LD->getChain() != Base->getChain())
6730 EVT VT = LD->getValueType(0);
6731 if (VT.getSizeInBits() / 8 != Bytes)
6734 SDValue Loc = LD->getOperand(1);
6735 SDValue BaseLoc = Base->getOperand(1);
6736 if (Loc.getOpcode() == ISD::FrameIndex) {
6737 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6739 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6740 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6741 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6742 int FS = MFI->getObjectSize(FI);
6743 int BFS = MFI->getObjectSize(BFI);
6744 if (FS != BFS || FS != (int)Bytes) return false;
6745 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6749 if (isBaseWithConstantOffset(Loc)) {
6750 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6751 if (Loc.getOperand(0) == BaseLoc) {
6752 // If the base location is a simple address with no offset itself, then
6753 // the second load's first add operand should be the base address.
6754 if (LocOffset == Dist * (int)Bytes)
6756 } else if (isBaseWithConstantOffset(BaseLoc)) {
6757 // The base location itself has an offset, so subtract that value from the
6758 // second load's offset before comparing to distance * size.
6760 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6761 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6762 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6767 const GlobalValue *GV1 = nullptr;
6768 const GlobalValue *GV2 = nullptr;
6769 int64_t Offset1 = 0;
6770 int64_t Offset2 = 0;
6771 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6772 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6773 if (isGA1 && isGA2 && GV1 == GV2)
6774 return Offset1 == (Offset2 + Dist*Bytes);
6779 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6780 /// it cannot be inferred.
6781 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6782 // If this is a GlobalAddress + cst, return the alignment.
6783 const GlobalValue *GV;
6784 int64_t GVOffset = 0;
6785 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6786 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6787 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6788 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6789 *TLI->getDataLayout());
6790 unsigned AlignBits = KnownZero.countTrailingOnes();
6791 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6793 return MinAlign(Align, GVOffset);
6796 // If this is a direct reference to a stack slot, use information about the
6797 // stack slot's alignment.
6798 int FrameIdx = 1 << 31;
6799 int64_t FrameOffset = 0;
6800 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6801 FrameIdx = FI->getIndex();
6802 } else if (isBaseWithConstantOffset(Ptr) &&
6803 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6805 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6806 FrameOffset = Ptr.getConstantOperandVal(1);
6809 if (FrameIdx != (1 << 31)) {
6810 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6811 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6819 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6820 /// which is split (or expanded) into two not necessarily identical pieces.
6821 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6822 // Currently all types are split in half.
6824 if (!VT.isVector()) {
6825 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6827 unsigned NumElements = VT.getVectorNumElements();
6828 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6829 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6832 return std::make_pair(LoVT, HiVT);
6835 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6837 std::pair<SDValue, SDValue>
6838 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6840 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6841 N.getValueType().getVectorNumElements() &&
6842 "More vector elements requested than available!");
6844 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6845 getConstant(0, DL, TLI->getVectorIdxTy()));
6846 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6847 getConstant(LoVT.getVectorNumElements(), DL,
6848 TLI->getVectorIdxTy()));
6849 return std::make_pair(Lo, Hi);
6852 void SelectionDAG::ExtractVectorElements(SDValue Op,
6853 SmallVectorImpl<SDValue> &Args,
6854 unsigned Start, unsigned Count) {
6855 EVT VT = Op.getValueType();
6857 Count = VT.getVectorNumElements();
6859 EVT EltVT = VT.getVectorElementType();
6860 EVT IdxTy = TLI->getVectorIdxTy();
6862 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6863 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6864 Op, getConstant(i, SL, IdxTy)));
6868 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6869 unsigned GlobalAddressSDNode::getAddressSpace() const {
6870 return getGlobal()->getType()->getAddressSpace();
6874 Type *ConstantPoolSDNode::getType() const {
6875 if (isMachineConstantPoolEntry())
6876 return Val.MachineCPVal->getType();
6877 return Val.ConstVal->getType();
6880 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6882 unsigned &SplatBitSize,
6884 unsigned MinSplatBits,
6885 bool isBigEndian) const {
6886 EVT VT = getValueType(0);
6887 assert(VT.isVector() && "Expected a vector type");
6888 unsigned sz = VT.getSizeInBits();
6889 if (MinSplatBits > sz)
6892 SplatValue = APInt(sz, 0);
6893 SplatUndef = APInt(sz, 0);
6895 // Get the bits. Bits with undefined values (when the corresponding element
6896 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6897 // in SplatValue. If any of the values are not constant, give up and return
6899 unsigned int nOps = getNumOperands();
6900 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6901 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6903 for (unsigned j = 0; j < nOps; ++j) {
6904 unsigned i = isBigEndian ? nOps-1-j : j;
6905 SDValue OpVal = getOperand(i);
6906 unsigned BitPos = j * EltBitSize;
6908 if (OpVal.getOpcode() == ISD::UNDEF)
6909 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6910 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6911 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6912 zextOrTrunc(sz) << BitPos;
6913 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6914 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6919 // The build_vector is all constants or undefs. Find the smallest element
6920 // size that splats the vector.
6922 HasAnyUndefs = (SplatUndef != 0);
6925 unsigned HalfSize = sz / 2;
6926 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6927 APInt LowValue = SplatValue.trunc(HalfSize);
6928 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6929 APInt LowUndef = SplatUndef.trunc(HalfSize);
6931 // If the two halves do not match (ignoring undef bits), stop here.
6932 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6933 MinSplatBits > HalfSize)
6936 SplatValue = HighValue | LowValue;
6937 SplatUndef = HighUndef & LowUndef;
6946 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6947 if (UndefElements) {
6948 UndefElements->clear();
6949 UndefElements->resize(getNumOperands());
6952 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6953 SDValue Op = getOperand(i);
6954 if (Op.getOpcode() == ISD::UNDEF) {
6956 (*UndefElements)[i] = true;
6957 } else if (!Splatted) {
6959 } else if (Splatted != Op) {
6965 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6966 "Can only have a splat without a constant for all undefs.");
6967 return getOperand(0);
6974 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6975 return dyn_cast_or_null<ConstantSDNode>(
6976 getSplatValue(UndefElements).getNode());
6980 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6981 return dyn_cast_or_null<ConstantFPSDNode>(
6982 getSplatValue(UndefElements).getNode());
6985 bool BuildVectorSDNode::isConstant() const {
6986 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6987 unsigned Opc = getOperand(i).getOpcode();
6988 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6994 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6995 // Find the first non-undef value in the shuffle mask.
6997 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7000 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7002 // Make sure all remaining elements are either undef or the same as the first
7004 for (int Idx = Mask[i]; i != e; ++i)
7005 if (Mask[i] >= 0 && Mask[i] != Idx)
7011 static void checkForCyclesHelper(const SDNode *N,
7012 SmallPtrSetImpl<const SDNode*> &Visited,
7013 SmallPtrSetImpl<const SDNode*> &Checked,
7014 const llvm::SelectionDAG *DAG) {
7015 // If this node has already been checked, don't check it again.
7016 if (Checked.count(N))
7019 // If a node has already been visited on this depth-first walk, reject it as
7021 if (!Visited.insert(N).second) {
7022 errs() << "Detected cycle in SelectionDAG\n";
7023 dbgs() << "Offending node:\n";
7024 N->dumprFull(DAG); dbgs() << "\n";
7028 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7029 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7036 void llvm::checkForCycles(const llvm::SDNode *N,
7037 const llvm::SelectionDAG *DAG,
7045 assert(N && "Checking nonexistent SDNode");
7046 SmallPtrSet<const SDNode*, 32> visited;
7047 SmallPtrSet<const SDNode*, 32> checked;
7048 checkForCyclesHelper(N, visited, checked, DAG);
7053 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7054 checkForCycles(DAG->getRoot().getNode(), DAG, force);