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 CONCAT_VECTORS is often formed while lowering is
3412 // expanding copies of large vectors from registers.
3414 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3415 N1.getNumOperands() > 0) {
3417 N1.getOperand(0).getValueType().getVectorNumElements();
3418 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3419 N1.getOperand(N2C->getZExtValue() / Factor),
3420 getConstant(N2C->getZExtValue() % Factor, DL,
3421 N2.getValueType()));
3424 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3425 // expanding large vector constants.
3426 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3427 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3429 if (VT != Elt.getValueType())
3430 // If the vector element type is not legal, the BUILD_VECTOR operands
3431 // are promoted and implicitly truncated, and the result implicitly
3432 // extended. Make that explicit here.
3433 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3438 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3439 // operations are lowered to scalars.
3440 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3441 // If the indices are the same, return the inserted element else
3442 // if the indices are known different, extract the element from
3443 // the original vector.
3444 SDValue N1Op2 = N1.getOperand(2);
3445 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3447 if (N1Op2C && N2C) {
3448 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3449 if (VT == N1.getOperand(1).getValueType())
3450 return N1.getOperand(1);
3452 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3455 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3459 case ISD::EXTRACT_ELEMENT:
3460 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3461 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3462 (N1.getValueType().isInteger() == VT.isInteger()) &&
3463 N1.getValueType() != VT &&
3464 "Wrong types for EXTRACT_ELEMENT!");
3466 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3467 // 64-bit integers into 32-bit parts. Instead of building the extract of
3468 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3469 if (N1.getOpcode() == ISD::BUILD_PAIR)
3470 return N1.getOperand(N2C->getZExtValue());
3472 // EXTRACT_ELEMENT of a constant int is also very common.
3473 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3474 unsigned ElementSize = VT.getSizeInBits();
3475 unsigned Shift = ElementSize * N2C->getZExtValue();
3476 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3477 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3480 case ISD::EXTRACT_SUBVECTOR: {
3482 if (VT.isSimple() && N1.getValueType().isSimple()) {
3483 assert(VT.isVector() && N1.getValueType().isVector() &&
3484 "Extract subvector VTs must be a vectors!");
3485 assert(VT.getVectorElementType() ==
3486 N1.getValueType().getVectorElementType() &&
3487 "Extract subvector VTs must have the same element type!");
3488 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3489 "Extract subvector must be from larger vector to smaller vector!");
3491 if (isa<ConstantSDNode>(Index.getNode())) {
3492 assert((VT.getVectorNumElements() +
3493 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3494 <= N1.getValueType().getVectorNumElements())
3495 && "Extract subvector overflow!");
3498 // Trivial extraction.
3499 if (VT.getSimpleVT() == N1.getSimpleValueType())
3506 // Perform trivial constant folding.
3508 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3511 // Canonicalize constant to RHS if commutative.
3512 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3513 std::swap(N1C, N2C);
3517 // Constant fold FP operations.
3518 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3519 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3520 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3522 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3523 // Canonicalize constant to RHS if commutative.
3524 std::swap(N1CFP, N2CFP);
3527 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3528 APFloat::opStatus s;
3531 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3532 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3533 return getConstantFP(V1, DL, VT);
3536 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3537 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3538 return getConstantFP(V1, DL, VT);
3541 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3542 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3543 return getConstantFP(V1, DL, VT);
3546 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3547 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3548 s!=APFloat::opDivByZero)) {
3549 return getConstantFP(V1, DL, VT);
3553 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3554 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3555 s!=APFloat::opDivByZero)) {
3556 return getConstantFP(V1, DL, VT);
3559 case ISD::FCOPYSIGN:
3561 return getConstantFP(V1, DL, VT);
3566 if (Opcode == ISD::FP_ROUND) {
3567 APFloat V = N1CFP->getValueAPF(); // make copy
3569 // This can return overflow, underflow, or inexact; we don't care.
3570 // FIXME need to be more flexible about rounding mode.
3571 (void)V.convert(EVTToAPFloatSemantics(VT),
3572 APFloat::rmNearestTiesToEven, &ignored);
3573 return getConstantFP(V, DL, VT);
3577 // Canonicalize an UNDEF to the RHS, even over a constant.
3578 if (N1.getOpcode() == ISD::UNDEF) {
3579 if (isCommutativeBinOp(Opcode)) {
3583 case ISD::FP_ROUND_INREG:
3584 case ISD::SIGN_EXTEND_INREG:
3590 return N1; // fold op(undef, arg2) -> undef
3598 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3599 // For vectors, we can't easily build an all zero vector, just return
3606 // Fold a bunch of operators when the RHS is undef.
3607 if (N2.getOpcode() == ISD::UNDEF) {
3610 if (N1.getOpcode() == ISD::UNDEF)
3611 // Handle undef ^ undef -> 0 special case. This is a common
3613 return getConstant(0, DL, VT);
3623 return N2; // fold op(arg1, undef) -> undef
3629 if (getTarget().Options.UnsafeFPMath)
3637 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3638 // For vectors, we can't easily build an all zero vector, just return
3643 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3644 // For vectors, we can't easily build an all one vector, just return
3652 // Memoize this node if possible.
3654 SDVTList VTs = getVTList(VT);
3655 SDValue Ops[] = { N1, N2 };
3656 if (VT != MVT::Glue) {
3657 SDValue Ops[] = {N1, N2};
3658 FoldingSetNodeID ID;
3659 AddNodeIDNode(ID, Opcode, VTs, Ops);
3660 AddNodeIDFlags(ID, Opcode, Flags);
3662 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3663 return SDValue(E, 0);
3665 N = GetSDNodeWithFlags(Opcode, DL, VTs, Ops, Flags);
3667 CSEMap.InsertNode(N, IP);
3669 N = GetSDNodeWithFlags(Opcode, DL, VTs, Ops, Flags);
3673 return SDValue(N, 0);
3676 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3677 SDValue N1, SDValue N2, SDValue N3) {
3678 // Perform various simplifications.
3679 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3682 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3683 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3684 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3685 if (N1CFP && N2CFP && N3CFP) {
3686 APFloat V1 = N1CFP->getValueAPF();
3687 const APFloat &V2 = N2CFP->getValueAPF();
3688 const APFloat &V3 = N3CFP->getValueAPF();
3689 APFloat::opStatus s =
3690 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3691 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3692 return getConstantFP(V1, DL, VT);
3696 case ISD::CONCAT_VECTORS:
3697 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3698 // one big BUILD_VECTOR.
3699 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3700 N2.getOpcode() == ISD::BUILD_VECTOR &&
3701 N3.getOpcode() == ISD::BUILD_VECTOR) {
3702 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3703 N1.getNode()->op_end());
3704 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3705 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3706 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3710 // Use FoldSetCC to simplify SETCC's.
3711 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3712 if (Simp.getNode()) return Simp;
3717 if (N1C->getZExtValue())
3718 return N2; // select true, X, Y -> X
3719 return N3; // select false, X, Y -> Y
3722 if (N2 == N3) return N2; // select C, X, X -> X
3724 case ISD::VECTOR_SHUFFLE:
3725 llvm_unreachable("should use getVectorShuffle constructor!");
3726 case ISD::INSERT_SUBVECTOR: {
3728 if (VT.isSimple() && N1.getValueType().isSimple()
3729 && N2.getValueType().isSimple()) {
3730 assert(VT.isVector() && N1.getValueType().isVector() &&
3731 N2.getValueType().isVector() &&
3732 "Insert subvector VTs must be a vectors");
3733 assert(VT == N1.getValueType() &&
3734 "Dest and insert subvector source types must match!");
3735 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3736 "Insert subvector must be from smaller vector to larger vector!");
3737 if (isa<ConstantSDNode>(Index.getNode())) {
3738 assert((N2.getValueType().getVectorNumElements() +
3739 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3740 <= VT.getVectorNumElements())
3741 && "Insert subvector overflow!");
3744 // Trivial insertion.
3745 if (VT.getSimpleVT() == N2.getSimpleValueType())
3751 // Fold bit_convert nodes from a type to themselves.
3752 if (N1.getValueType() == VT)
3757 // Memoize node if it doesn't produce a flag.
3759 SDVTList VTs = getVTList(VT);
3760 if (VT != MVT::Glue) {
3761 SDValue Ops[] = { N1, N2, N3 };
3762 FoldingSetNodeID ID;
3763 AddNodeIDNode(ID, Opcode, VTs, Ops);
3765 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3766 return SDValue(E, 0);
3768 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3769 DL.getDebugLoc(), VTs, N1, N2, N3);
3770 CSEMap.InsertNode(N, IP);
3772 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3773 DL.getDebugLoc(), VTs, N1, N2, N3);
3777 return SDValue(N, 0);
3780 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3781 SDValue N1, SDValue N2, SDValue N3,
3783 SDValue Ops[] = { N1, N2, N3, N4 };
3784 return getNode(Opcode, DL, VT, Ops);
3787 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3788 SDValue N1, SDValue N2, SDValue N3,
3789 SDValue N4, SDValue N5) {
3790 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3791 return getNode(Opcode, DL, VT, Ops);
3794 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3795 /// the incoming stack arguments to be loaded from the stack.
3796 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3797 SmallVector<SDValue, 8> ArgChains;
3799 // Include the original chain at the beginning of the list. When this is
3800 // used by target LowerCall hooks, this helps legalize find the
3801 // CALLSEQ_BEGIN node.
3802 ArgChains.push_back(Chain);
3804 // Add a chain value for each stack argument.
3805 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3806 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3807 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3808 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3809 if (FI->getIndex() < 0)
3810 ArgChains.push_back(SDValue(L, 1));
3812 // Build a tokenfactor for all the chains.
3813 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3816 /// getMemsetValue - Vectorized representation of the memset value
3818 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3820 assert(Value.getOpcode() != ISD::UNDEF);
3822 unsigned NumBits = VT.getScalarType().getSizeInBits();
3823 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3824 assert(C->getAPIntValue().getBitWidth() == 8);
3825 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3827 return DAG.getConstant(Val, dl, VT);
3828 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3832 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3833 EVT IntVT = VT.getScalarType();
3834 if (!IntVT.isInteger())
3835 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3837 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3839 // Use a multiplication with 0x010101... to extend the input to the
3841 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3842 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3843 DAG.getConstant(Magic, dl, IntVT));
3846 if (VT != Value.getValueType() && !VT.isInteger())
3847 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3848 if (VT != Value.getValueType()) {
3849 assert(VT.getVectorElementType() == Value.getValueType() &&
3850 "value type should be one vector element here");
3851 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3852 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3858 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3859 /// used when a memcpy is turned into a memset when the source is a constant
3861 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3862 const TargetLowering &TLI, StringRef Str) {
3863 // Handle vector with all elements zero.
3866 return DAG.getConstant(0, dl, VT);
3867 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3868 return DAG.getConstantFP(0.0, dl, VT);
3869 else if (VT.isVector()) {
3870 unsigned NumElts = VT.getVectorNumElements();
3871 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3872 return DAG.getNode(ISD::BITCAST, dl, VT,
3873 DAG.getConstant(0, dl,
3874 EVT::getVectorVT(*DAG.getContext(),
3877 llvm_unreachable("Expected type!");
3880 assert(!VT.isVector() && "Can't handle vector type here!");
3881 unsigned NumVTBits = VT.getSizeInBits();
3882 unsigned NumVTBytes = NumVTBits / 8;
3883 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3885 APInt Val(NumVTBits, 0);
3886 if (TLI.isLittleEndian()) {
3887 for (unsigned i = 0; i != NumBytes; ++i)
3888 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3890 for (unsigned i = 0; i != NumBytes; ++i)
3891 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3894 // If the "cost" of materializing the integer immediate is less than the cost
3895 // of a load, then it is cost effective to turn the load into the immediate.
3896 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3897 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3898 return DAG.getConstant(Val, dl, VT);
3899 return SDValue(nullptr, 0);
3902 /// getMemBasePlusOffset - Returns base and offset node for the
3904 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3905 SelectionDAG &DAG) {
3906 EVT VT = Base.getValueType();
3907 return DAG.getNode(ISD::ADD, dl,
3908 VT, Base, DAG.getConstant(Offset, dl, VT));
3911 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3913 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3914 unsigned SrcDelta = 0;
3915 GlobalAddressSDNode *G = nullptr;
3916 if (Src.getOpcode() == ISD::GlobalAddress)
3917 G = cast<GlobalAddressSDNode>(Src);
3918 else if (Src.getOpcode() == ISD::ADD &&
3919 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3920 Src.getOperand(1).getOpcode() == ISD::Constant) {
3921 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3922 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3927 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3930 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3931 /// to replace the memset / memcpy. Return true if the number of memory ops
3932 /// is below the threshold. It returns the types of the sequence of
3933 /// memory ops to perform memset / memcpy by reference.
3934 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3935 unsigned Limit, uint64_t Size,
3936 unsigned DstAlign, unsigned SrcAlign,
3942 const TargetLowering &TLI) {
3943 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3944 "Expecting memcpy / memset source to meet alignment requirement!");
3945 // If 'SrcAlign' is zero, that means the memory operation does not need to
3946 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3947 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3948 // is the specified alignment of the memory operation. If it is zero, that
3949 // means it's possible to change the alignment of the destination.
3950 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3951 // not need to be loaded.
3952 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3953 IsMemset, ZeroMemset, MemcpyStrSrc,
3954 DAG.getMachineFunction());
3956 if (VT == MVT::Other) {
3958 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3959 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
3960 VT = TLI.getPointerTy();
3962 switch (DstAlign & 7) {
3963 case 0: VT = MVT::i64; break;
3964 case 4: VT = MVT::i32; break;
3965 case 2: VT = MVT::i16; break;
3966 default: VT = MVT::i8; break;
3971 while (!TLI.isTypeLegal(LVT))
3972 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3973 assert(LVT.isInteger());
3979 unsigned NumMemOps = 0;
3981 unsigned VTSize = VT.getSizeInBits() / 8;
3982 while (VTSize > Size) {
3983 // For now, only use non-vector load / store's for the left-over pieces.
3988 if (VT.isVector() || VT.isFloatingPoint()) {
3989 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3990 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3991 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3993 else if (NewVT == MVT::i64 &&
3994 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3995 TLI.isSafeMemOpType(MVT::f64)) {
3996 // i64 is usually not legal on 32-bit targets, but f64 may be.
4004 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4005 if (NewVT == MVT::i8)
4007 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4009 NewVTSize = NewVT.getSizeInBits() / 8;
4011 // If the new VT cannot cover all of the remaining bits, then consider
4012 // issuing a (or a pair of) unaligned and overlapping load / store.
4013 // FIXME: Only does this for 64-bit or more since we don't have proper
4014 // cost model for unaligned load / store.
4017 if (NumMemOps && AllowOverlap &&
4018 VTSize >= 8 && NewVTSize < Size &&
4019 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4027 if (++NumMemOps > Limit)
4030 MemOps.push_back(VT);
4037 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4038 SDValue Chain, SDValue Dst,
4039 SDValue Src, uint64_t Size,
4040 unsigned Align, bool isVol,
4042 MachinePointerInfo DstPtrInfo,
4043 MachinePointerInfo SrcPtrInfo) {
4044 // Turn a memcpy of undef to nop.
4045 if (Src.getOpcode() == ISD::UNDEF)
4048 // Expand memcpy to a series of load and store ops if the size operand falls
4049 // below a certain threshold.
4050 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4051 // rather than maybe a humongous number of loads and stores.
4052 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4053 std::vector<EVT> MemOps;
4054 bool DstAlignCanChange = false;
4055 MachineFunction &MF = DAG.getMachineFunction();
4056 MachineFrameInfo *MFI = MF.getFrameInfo();
4057 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4058 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4059 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4060 DstAlignCanChange = true;
4061 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4062 if (Align > SrcAlign)
4065 bool CopyFromStr = isMemSrcFromString(Src, Str);
4066 bool isZeroStr = CopyFromStr && Str.empty();
4067 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4069 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4070 (DstAlignCanChange ? 0 : Align),
4071 (isZeroStr ? 0 : SrcAlign),
4072 false, false, CopyFromStr, true, DAG, TLI))
4075 if (DstAlignCanChange) {
4076 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4077 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4079 // Don't promote to an alignment that would require dynamic stack
4081 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4082 if (!TRI->needsStackRealignment(MF))
4083 while (NewAlign > Align &&
4084 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4087 if (NewAlign > Align) {
4088 // Give the stack frame object a larger alignment if needed.
4089 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4090 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4095 SmallVector<SDValue, 8> OutChains;
4096 unsigned NumMemOps = MemOps.size();
4097 uint64_t SrcOff = 0, DstOff = 0;
4098 for (unsigned i = 0; i != NumMemOps; ++i) {
4100 unsigned VTSize = VT.getSizeInBits() / 8;
4101 SDValue Value, Store;
4103 if (VTSize > Size) {
4104 // Issuing an unaligned load / store pair that overlaps with the previous
4105 // pair. Adjust the offset accordingly.
4106 assert(i == NumMemOps-1 && i != 0);
4107 SrcOff -= VTSize - Size;
4108 DstOff -= VTSize - Size;
4112 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4113 // It's unlikely a store of a vector immediate can be done in a single
4114 // instruction. It would require a load from a constantpool first.
4115 // We only handle zero vectors here.
4116 // FIXME: Handle other cases where store of vector immediate is done in
4117 // a single instruction.
4118 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4119 if (Value.getNode())
4120 Store = DAG.getStore(Chain, dl, Value,
4121 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4122 DstPtrInfo.getWithOffset(DstOff), isVol,
4126 if (!Store.getNode()) {
4127 // The type might not be legal for the target. This should only happen
4128 // if the type is smaller than a legal type, as on PPC, so the right
4129 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4130 // to Load/Store if NVT==VT.
4131 // FIXME does the case above also need this?
4132 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4133 assert(NVT.bitsGE(VT));
4134 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4135 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4136 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4137 false, MinAlign(SrcAlign, SrcOff));
4138 Store = DAG.getTruncStore(Chain, dl, Value,
4139 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4140 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4143 OutChains.push_back(Store);
4149 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4152 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4153 SDValue Chain, SDValue Dst,
4154 SDValue Src, uint64_t Size,
4155 unsigned Align, bool isVol,
4157 MachinePointerInfo DstPtrInfo,
4158 MachinePointerInfo SrcPtrInfo) {
4159 // Turn a memmove of undef to nop.
4160 if (Src.getOpcode() == ISD::UNDEF)
4163 // Expand memmove to a series of load and store ops if the size operand falls
4164 // below a certain threshold.
4165 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4166 std::vector<EVT> MemOps;
4167 bool DstAlignCanChange = false;
4168 MachineFunction &MF = DAG.getMachineFunction();
4169 MachineFrameInfo *MFI = MF.getFrameInfo();
4170 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4171 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4172 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4173 DstAlignCanChange = true;
4174 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4175 if (Align > SrcAlign)
4177 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4179 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4180 (DstAlignCanChange ? 0 : Align), SrcAlign,
4181 false, false, false, false, DAG, TLI))
4184 if (DstAlignCanChange) {
4185 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4186 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4187 if (NewAlign > Align) {
4188 // Give the stack frame object a larger alignment if needed.
4189 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4190 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4195 uint64_t SrcOff = 0, DstOff = 0;
4196 SmallVector<SDValue, 8> LoadValues;
4197 SmallVector<SDValue, 8> LoadChains;
4198 SmallVector<SDValue, 8> OutChains;
4199 unsigned NumMemOps = MemOps.size();
4200 for (unsigned i = 0; i < NumMemOps; i++) {
4202 unsigned VTSize = VT.getSizeInBits() / 8;
4205 Value = DAG.getLoad(VT, dl, Chain,
4206 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4207 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4208 false, false, SrcAlign);
4209 LoadValues.push_back(Value);
4210 LoadChains.push_back(Value.getValue(1));
4213 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4215 for (unsigned i = 0; i < NumMemOps; i++) {
4217 unsigned VTSize = VT.getSizeInBits() / 8;
4220 Store = DAG.getStore(Chain, dl, LoadValues[i],
4221 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4222 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4223 OutChains.push_back(Store);
4227 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4230 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4233 /// \param DAG Selection DAG where lowered code is placed.
4234 /// \param dl Link to corresponding IR location.
4235 /// \param Chain Control flow dependency.
4236 /// \param Dst Pointer to destination memory location.
4237 /// \param Src Value of byte to write into the memory.
4238 /// \param Size Number of bytes to write.
4239 /// \param Align Alignment of the destination in bytes.
4240 /// \param isVol True if destination is volatile.
4241 /// \param DstPtrInfo IR information on the memory pointer.
4242 /// \returns New head in the control flow, if lowering was successful, empty
4243 /// SDValue otherwise.
4245 /// The function tries to replace 'llvm.memset' intrinsic with several store
4246 /// operations and value calculation code. This is usually profitable for small
4248 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4249 SDValue Chain, SDValue Dst,
4250 SDValue Src, uint64_t Size,
4251 unsigned Align, bool isVol,
4252 MachinePointerInfo DstPtrInfo) {
4253 // Turn a memset of undef to nop.
4254 if (Src.getOpcode() == ISD::UNDEF)
4257 // Expand memset to a series of load/store ops if the size operand
4258 // falls below a certain threshold.
4259 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4260 std::vector<EVT> MemOps;
4261 bool DstAlignCanChange = false;
4262 MachineFunction &MF = DAG.getMachineFunction();
4263 MachineFrameInfo *MFI = MF.getFrameInfo();
4264 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4265 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4266 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4267 DstAlignCanChange = true;
4269 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4270 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4271 Size, (DstAlignCanChange ? 0 : Align), 0,
4272 true, IsZeroVal, false, true, DAG, TLI))
4275 if (DstAlignCanChange) {
4276 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4277 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4278 if (NewAlign > Align) {
4279 // Give the stack frame object a larger alignment if needed.
4280 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4281 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4286 SmallVector<SDValue, 8> OutChains;
4287 uint64_t DstOff = 0;
4288 unsigned NumMemOps = MemOps.size();
4290 // Find the largest store and generate the bit pattern for it.
4291 EVT LargestVT = MemOps[0];
4292 for (unsigned i = 1; i < NumMemOps; i++)
4293 if (MemOps[i].bitsGT(LargestVT))
4294 LargestVT = MemOps[i];
4295 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4297 for (unsigned i = 0; i < NumMemOps; i++) {
4299 unsigned VTSize = VT.getSizeInBits() / 8;
4300 if (VTSize > Size) {
4301 // Issuing an unaligned load / store pair that overlaps with the previous
4302 // pair. Adjust the offset accordingly.
4303 assert(i == NumMemOps-1 && i != 0);
4304 DstOff -= VTSize - Size;
4307 // If this store is smaller than the largest store see whether we can get
4308 // the smaller value for free with a truncate.
4309 SDValue Value = MemSetValue;
4310 if (VT.bitsLT(LargestVT)) {
4311 if (!LargestVT.isVector() && !VT.isVector() &&
4312 TLI.isTruncateFree(LargestVT, VT))
4313 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4315 Value = getMemsetValue(Src, VT, DAG, dl);
4317 assert(Value.getValueType() == VT && "Value with wrong type.");
4318 SDValue Store = DAG.getStore(Chain, dl, Value,
4319 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4320 DstPtrInfo.getWithOffset(DstOff),
4321 isVol, false, Align);
4322 OutChains.push_back(Store);
4323 DstOff += VT.getSizeInBits() / 8;
4327 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4330 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4331 SDValue Src, SDValue Size,
4332 unsigned Align, bool isVol, bool AlwaysInline,
4333 bool isTailCall, MachinePointerInfo DstPtrInfo,
4334 MachinePointerInfo SrcPtrInfo) {
4335 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4337 // Check to see if we should lower the memcpy to loads and stores first.
4338 // For cases within the target-specified limits, this is the best choice.
4339 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4341 // Memcpy with size zero? Just return the original chain.
4342 if (ConstantSize->isNullValue())
4345 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4346 ConstantSize->getZExtValue(),Align,
4347 isVol, false, DstPtrInfo, SrcPtrInfo);
4348 if (Result.getNode())
4352 // Then check to see if we should lower the memcpy with target-specific
4353 // code. If the target chooses to do this, this is the next best.
4355 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4356 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4357 DstPtrInfo, SrcPtrInfo);
4358 if (Result.getNode())
4362 // If we really need inline code and the target declined to provide it,
4363 // use a (potentially long) sequence of loads and stores.
4365 assert(ConstantSize && "AlwaysInline requires a constant size!");
4366 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4367 ConstantSize->getZExtValue(), Align, isVol,
4368 true, DstPtrInfo, SrcPtrInfo);
4371 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4372 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4373 // respect volatile, so they may do things like read or write memory
4374 // beyond the given memory regions. But fixing this isn't easy, and most
4375 // people don't care.
4377 // Emit a library call.
4378 TargetLowering::ArgListTy Args;
4379 TargetLowering::ArgListEntry Entry;
4380 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4381 Entry.Node = Dst; Args.push_back(Entry);
4382 Entry.Node = Src; Args.push_back(Entry);
4383 Entry.Node = Size; Args.push_back(Entry);
4384 // FIXME: pass in SDLoc
4385 TargetLowering::CallLoweringInfo CLI(*this);
4386 CLI.setDebugLoc(dl).setChain(Chain)
4387 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4388 Type::getVoidTy(*getContext()),
4389 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4390 TLI->getPointerTy()), std::move(Args), 0)
4392 .setTailCall(isTailCall);
4394 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4395 return CallResult.second;
4398 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4399 SDValue Src, SDValue Size,
4400 unsigned Align, bool isVol, bool isTailCall,
4401 MachinePointerInfo DstPtrInfo,
4402 MachinePointerInfo SrcPtrInfo) {
4403 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4405 // Check to see if we should lower the memmove to loads and stores first.
4406 // For cases within the target-specified limits, this is the best choice.
4407 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4409 // Memmove with size zero? Just return the original chain.
4410 if (ConstantSize->isNullValue())
4414 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4415 ConstantSize->getZExtValue(), Align, isVol,
4416 false, DstPtrInfo, SrcPtrInfo);
4417 if (Result.getNode())
4421 // Then check to see if we should lower the memmove with target-specific
4422 // code. If the target chooses to do this, this is the next best.
4424 SDValue Result = TSI->EmitTargetCodeForMemmove(
4425 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4426 if (Result.getNode())
4430 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4431 // not be safe. See memcpy above for more details.
4433 // Emit a library call.
4434 TargetLowering::ArgListTy Args;
4435 TargetLowering::ArgListEntry Entry;
4436 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4437 Entry.Node = Dst; Args.push_back(Entry);
4438 Entry.Node = Src; Args.push_back(Entry);
4439 Entry.Node = Size; Args.push_back(Entry);
4440 // FIXME: pass in SDLoc
4441 TargetLowering::CallLoweringInfo CLI(*this);
4442 CLI.setDebugLoc(dl).setChain(Chain)
4443 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4444 Type::getVoidTy(*getContext()),
4445 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4446 TLI->getPointerTy()), std::move(Args), 0)
4448 .setTailCall(isTailCall);
4450 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4451 return CallResult.second;
4454 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4455 SDValue Src, SDValue Size,
4456 unsigned Align, bool isVol, bool isTailCall,
4457 MachinePointerInfo DstPtrInfo) {
4458 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4460 // Check to see if we should lower the memset to stores first.
4461 // For cases within the target-specified limits, this is the best choice.
4462 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4464 // Memset with size zero? Just return the original chain.
4465 if (ConstantSize->isNullValue())
4469 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4470 Align, isVol, DstPtrInfo);
4472 if (Result.getNode())
4476 // Then check to see if we should lower the memset with target-specific
4477 // code. If the target chooses to do this, this is the next best.
4479 SDValue Result = TSI->EmitTargetCodeForMemset(
4480 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4481 if (Result.getNode())
4485 // Emit a library call.
4486 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4487 TargetLowering::ArgListTy Args;
4488 TargetLowering::ArgListEntry Entry;
4489 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4490 Args.push_back(Entry);
4492 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4493 Args.push_back(Entry);
4495 Entry.Ty = IntPtrTy;
4496 Args.push_back(Entry);
4498 // FIXME: pass in SDLoc
4499 TargetLowering::CallLoweringInfo CLI(*this);
4500 CLI.setDebugLoc(dl).setChain(Chain)
4501 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4502 Type::getVoidTy(*getContext()),
4503 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4504 TLI->getPointerTy()), std::move(Args), 0)
4506 .setTailCall(isTailCall);
4508 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4509 return CallResult.second;
4512 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4513 SDVTList VTList, ArrayRef<SDValue> Ops,
4514 MachineMemOperand *MMO,
4515 AtomicOrdering SuccessOrdering,
4516 AtomicOrdering FailureOrdering,
4517 SynchronizationScope SynchScope) {
4518 FoldingSetNodeID ID;
4519 ID.AddInteger(MemVT.getRawBits());
4520 AddNodeIDNode(ID, Opcode, VTList, Ops);
4521 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4523 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4524 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4525 return SDValue(E, 0);
4528 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4529 // SDNode doesn't have access to it. This memory will be "leaked" when
4530 // the node is deallocated, but recovered when the allocator is released.
4531 // If the number of operands is less than 5 we use AtomicSDNode's internal
4533 unsigned NumOps = Ops.size();
4534 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4537 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4538 dl.getDebugLoc(), VTList, MemVT,
4539 Ops.data(), DynOps, NumOps, MMO,
4540 SuccessOrdering, FailureOrdering,
4542 CSEMap.InsertNode(N, IP);
4544 return SDValue(N, 0);
4547 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4548 SDVTList VTList, ArrayRef<SDValue> Ops,
4549 MachineMemOperand *MMO,
4550 AtomicOrdering Ordering,
4551 SynchronizationScope SynchScope) {
4552 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4553 Ordering, SynchScope);
4556 SDValue SelectionDAG::getAtomicCmpSwap(
4557 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4558 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4559 unsigned Alignment, AtomicOrdering SuccessOrdering,
4560 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4561 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4562 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4563 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4565 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4566 Alignment = getEVTAlignment(MemVT);
4568 MachineFunction &MF = getMachineFunction();
4570 // FIXME: Volatile isn't really correct; we should keep track of atomic
4571 // orderings in the memoperand.
4572 unsigned Flags = MachineMemOperand::MOVolatile;
4573 Flags |= MachineMemOperand::MOLoad;
4574 Flags |= MachineMemOperand::MOStore;
4576 MachineMemOperand *MMO =
4577 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4579 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4580 SuccessOrdering, FailureOrdering, SynchScope);
4583 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4584 SDVTList VTs, SDValue Chain, SDValue Ptr,
4585 SDValue Cmp, SDValue Swp,
4586 MachineMemOperand *MMO,
4587 AtomicOrdering SuccessOrdering,
4588 AtomicOrdering FailureOrdering,
4589 SynchronizationScope SynchScope) {
4590 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4591 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4592 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4594 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4595 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4596 SuccessOrdering, FailureOrdering, SynchScope);
4599 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4601 SDValue Ptr, SDValue Val,
4602 const Value* PtrVal,
4604 AtomicOrdering Ordering,
4605 SynchronizationScope SynchScope) {
4606 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4607 Alignment = getEVTAlignment(MemVT);
4609 MachineFunction &MF = getMachineFunction();
4610 // An atomic store does not load. An atomic load does not store.
4611 // (An atomicrmw obviously both loads and stores.)
4612 // For now, atomics are considered to be volatile always, and they are
4614 // FIXME: Volatile isn't really correct; we should keep track of atomic
4615 // orderings in the memoperand.
4616 unsigned Flags = MachineMemOperand::MOVolatile;
4617 if (Opcode != ISD::ATOMIC_STORE)
4618 Flags |= MachineMemOperand::MOLoad;
4619 if (Opcode != ISD::ATOMIC_LOAD)
4620 Flags |= MachineMemOperand::MOStore;
4622 MachineMemOperand *MMO =
4623 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4624 MemVT.getStoreSize(), Alignment);
4626 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4627 Ordering, SynchScope);
4630 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4632 SDValue Ptr, SDValue Val,
4633 MachineMemOperand *MMO,
4634 AtomicOrdering Ordering,
4635 SynchronizationScope SynchScope) {
4636 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4637 Opcode == ISD::ATOMIC_LOAD_SUB ||
4638 Opcode == ISD::ATOMIC_LOAD_AND ||
4639 Opcode == ISD::ATOMIC_LOAD_OR ||
4640 Opcode == ISD::ATOMIC_LOAD_XOR ||
4641 Opcode == ISD::ATOMIC_LOAD_NAND ||
4642 Opcode == ISD::ATOMIC_LOAD_MIN ||
4643 Opcode == ISD::ATOMIC_LOAD_MAX ||
4644 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4645 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4646 Opcode == ISD::ATOMIC_SWAP ||
4647 Opcode == ISD::ATOMIC_STORE) &&
4648 "Invalid Atomic Op");
4650 EVT VT = Val.getValueType();
4652 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4653 getVTList(VT, MVT::Other);
4654 SDValue Ops[] = {Chain, Ptr, Val};
4655 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4658 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4659 EVT VT, SDValue Chain,
4661 MachineMemOperand *MMO,
4662 AtomicOrdering Ordering,
4663 SynchronizationScope SynchScope) {
4664 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4666 SDVTList VTs = getVTList(VT, MVT::Other);
4667 SDValue Ops[] = {Chain, Ptr};
4668 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4671 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4672 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4673 if (Ops.size() == 1)
4676 SmallVector<EVT, 4> VTs;
4677 VTs.reserve(Ops.size());
4678 for (unsigned i = 0; i < Ops.size(); ++i)
4679 VTs.push_back(Ops[i].getValueType());
4680 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4684 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4685 ArrayRef<SDValue> Ops,
4686 EVT MemVT, MachinePointerInfo PtrInfo,
4687 unsigned Align, bool Vol,
4688 bool ReadMem, bool WriteMem, unsigned Size) {
4689 if (Align == 0) // Ensure that codegen never sees alignment 0
4690 Align = getEVTAlignment(MemVT);
4692 MachineFunction &MF = getMachineFunction();
4695 Flags |= MachineMemOperand::MOStore;
4697 Flags |= MachineMemOperand::MOLoad;
4699 Flags |= MachineMemOperand::MOVolatile;
4701 Size = MemVT.getStoreSize();
4702 MachineMemOperand *MMO =
4703 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4705 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4709 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4710 ArrayRef<SDValue> Ops, EVT MemVT,
4711 MachineMemOperand *MMO) {
4712 assert((Opcode == ISD::INTRINSIC_VOID ||
4713 Opcode == ISD::INTRINSIC_W_CHAIN ||
4714 Opcode == ISD::PREFETCH ||
4715 Opcode == ISD::LIFETIME_START ||
4716 Opcode == ISD::LIFETIME_END ||
4717 (Opcode <= INT_MAX &&
4718 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4719 "Opcode is not a memory-accessing opcode!");
4721 // Memoize the node unless it returns a flag.
4722 MemIntrinsicSDNode *N;
4723 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4724 FoldingSetNodeID ID;
4725 AddNodeIDNode(ID, Opcode, VTList, Ops);
4726 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4728 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4729 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4730 return SDValue(E, 0);
4733 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4734 dl.getDebugLoc(), VTList, Ops,
4736 CSEMap.InsertNode(N, IP);
4738 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4739 dl.getDebugLoc(), VTList, Ops,
4743 return SDValue(N, 0);
4746 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4747 /// MachinePointerInfo record from it. This is particularly useful because the
4748 /// code generator has many cases where it doesn't bother passing in a
4749 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4750 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4751 // If this is FI+Offset, we can model it.
4752 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4753 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4755 // If this is (FI+Offset1)+Offset2, we can model it.
4756 if (Ptr.getOpcode() != ISD::ADD ||
4757 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4758 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4759 return MachinePointerInfo();
4761 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4762 return MachinePointerInfo::getFixedStack(FI, Offset+
4763 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4766 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4767 /// MachinePointerInfo record from it. This is particularly useful because the
4768 /// code generator has many cases where it doesn't bother passing in a
4769 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4770 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4771 // If the 'Offset' value isn't a constant, we can't handle this.
4772 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4773 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4774 if (OffsetOp.getOpcode() == ISD::UNDEF)
4775 return InferPointerInfo(Ptr);
4776 return MachinePointerInfo();
4781 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4782 EVT VT, SDLoc dl, SDValue Chain,
4783 SDValue Ptr, SDValue Offset,
4784 MachinePointerInfo PtrInfo, EVT MemVT,
4785 bool isVolatile, bool isNonTemporal, bool isInvariant,
4786 unsigned Alignment, const AAMDNodes &AAInfo,
4787 const MDNode *Ranges) {
4788 assert(Chain.getValueType() == MVT::Other &&
4789 "Invalid chain type");
4790 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4791 Alignment = getEVTAlignment(VT);
4793 unsigned Flags = MachineMemOperand::MOLoad;
4795 Flags |= MachineMemOperand::MOVolatile;
4797 Flags |= MachineMemOperand::MONonTemporal;
4799 Flags |= MachineMemOperand::MOInvariant;
4801 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4803 if (PtrInfo.V.isNull())
4804 PtrInfo = InferPointerInfo(Ptr, Offset);
4806 MachineFunction &MF = getMachineFunction();
4807 MachineMemOperand *MMO =
4808 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4810 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4814 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4815 EVT VT, SDLoc dl, SDValue Chain,
4816 SDValue Ptr, SDValue Offset, EVT MemVT,
4817 MachineMemOperand *MMO) {
4819 ExtType = ISD::NON_EXTLOAD;
4820 } else if (ExtType == ISD::NON_EXTLOAD) {
4821 assert(VT == MemVT && "Non-extending load from different memory type!");
4824 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4825 "Should only be an extending load, not truncating!");
4826 assert(VT.isInteger() == MemVT.isInteger() &&
4827 "Cannot convert from FP to Int or Int -> FP!");
4828 assert(VT.isVector() == MemVT.isVector() &&
4829 "Cannot use an ext load to convert to or from a vector!");
4830 assert((!VT.isVector() ||
4831 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4832 "Cannot use an ext load to change the number of vector elements!");
4835 bool Indexed = AM != ISD::UNINDEXED;
4836 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4837 "Unindexed load with an offset!");
4839 SDVTList VTs = Indexed ?
4840 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4841 SDValue Ops[] = { Chain, Ptr, Offset };
4842 FoldingSetNodeID ID;
4843 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4844 ID.AddInteger(MemVT.getRawBits());
4845 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4846 MMO->isNonTemporal(),
4847 MMO->isInvariant()));
4848 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4850 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4851 cast<LoadSDNode>(E)->refineAlignment(MMO);
4852 return SDValue(E, 0);
4854 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4855 dl.getDebugLoc(), VTs, AM, ExtType,
4857 CSEMap.InsertNode(N, IP);
4859 return SDValue(N, 0);
4862 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4863 SDValue Chain, SDValue Ptr,
4864 MachinePointerInfo PtrInfo,
4865 bool isVolatile, bool isNonTemporal,
4866 bool isInvariant, unsigned Alignment,
4867 const AAMDNodes &AAInfo,
4868 const MDNode *Ranges) {
4869 SDValue Undef = getUNDEF(Ptr.getValueType());
4870 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4871 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4875 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4876 SDValue Chain, SDValue Ptr,
4877 MachineMemOperand *MMO) {
4878 SDValue Undef = getUNDEF(Ptr.getValueType());
4879 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4883 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4884 SDValue Chain, SDValue Ptr,
4885 MachinePointerInfo PtrInfo, EVT MemVT,
4886 bool isVolatile, bool isNonTemporal,
4887 bool isInvariant, unsigned Alignment,
4888 const AAMDNodes &AAInfo) {
4889 SDValue Undef = getUNDEF(Ptr.getValueType());
4890 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4891 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4896 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4897 SDValue Chain, SDValue Ptr, EVT MemVT,
4898 MachineMemOperand *MMO) {
4899 SDValue Undef = getUNDEF(Ptr.getValueType());
4900 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4905 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4906 SDValue Offset, ISD::MemIndexedMode AM) {
4907 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4908 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4909 "Load is already a indexed load!");
4910 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4911 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4912 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4913 false, LD->getAlignment());
4916 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4917 SDValue Ptr, MachinePointerInfo PtrInfo,
4918 bool isVolatile, bool isNonTemporal,
4919 unsigned Alignment, const AAMDNodes &AAInfo) {
4920 assert(Chain.getValueType() == MVT::Other &&
4921 "Invalid chain type");
4922 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4923 Alignment = getEVTAlignment(Val.getValueType());
4925 unsigned Flags = MachineMemOperand::MOStore;
4927 Flags |= MachineMemOperand::MOVolatile;
4929 Flags |= MachineMemOperand::MONonTemporal;
4931 if (PtrInfo.V.isNull())
4932 PtrInfo = InferPointerInfo(Ptr);
4934 MachineFunction &MF = getMachineFunction();
4935 MachineMemOperand *MMO =
4936 MF.getMachineMemOperand(PtrInfo, Flags,
4937 Val.getValueType().getStoreSize(), Alignment,
4940 return getStore(Chain, dl, Val, Ptr, MMO);
4943 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4944 SDValue Ptr, MachineMemOperand *MMO) {
4945 assert(Chain.getValueType() == MVT::Other &&
4946 "Invalid chain type");
4947 EVT VT = Val.getValueType();
4948 SDVTList VTs = getVTList(MVT::Other);
4949 SDValue Undef = getUNDEF(Ptr.getValueType());
4950 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4951 FoldingSetNodeID ID;
4952 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4953 ID.AddInteger(VT.getRawBits());
4954 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4955 MMO->isNonTemporal(), MMO->isInvariant()));
4956 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4958 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4959 cast<StoreSDNode>(E)->refineAlignment(MMO);
4960 return SDValue(E, 0);
4962 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4963 dl.getDebugLoc(), VTs,
4964 ISD::UNINDEXED, false, VT, MMO);
4965 CSEMap.InsertNode(N, IP);
4967 return SDValue(N, 0);
4970 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4971 SDValue Ptr, MachinePointerInfo PtrInfo,
4972 EVT SVT,bool isVolatile, bool isNonTemporal,
4974 const AAMDNodes &AAInfo) {
4975 assert(Chain.getValueType() == MVT::Other &&
4976 "Invalid chain type");
4977 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4978 Alignment = getEVTAlignment(SVT);
4980 unsigned Flags = MachineMemOperand::MOStore;
4982 Flags |= MachineMemOperand::MOVolatile;
4984 Flags |= MachineMemOperand::MONonTemporal;
4986 if (PtrInfo.V.isNull())
4987 PtrInfo = InferPointerInfo(Ptr);
4989 MachineFunction &MF = getMachineFunction();
4990 MachineMemOperand *MMO =
4991 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4994 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4997 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4998 SDValue Ptr, EVT SVT,
4999 MachineMemOperand *MMO) {
5000 EVT VT = Val.getValueType();
5002 assert(Chain.getValueType() == MVT::Other &&
5003 "Invalid chain type");
5005 return getStore(Chain, dl, Val, Ptr, MMO);
5007 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5008 "Should only be a truncating store, not extending!");
5009 assert(VT.isInteger() == SVT.isInteger() &&
5010 "Can't do FP-INT conversion!");
5011 assert(VT.isVector() == SVT.isVector() &&
5012 "Cannot use trunc store to convert to or from a vector!");
5013 assert((!VT.isVector() ||
5014 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5015 "Cannot use trunc store to change the number of vector elements!");
5017 SDVTList VTs = getVTList(MVT::Other);
5018 SDValue Undef = getUNDEF(Ptr.getValueType());
5019 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5020 FoldingSetNodeID ID;
5021 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5022 ID.AddInteger(SVT.getRawBits());
5023 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5024 MMO->isNonTemporal(), MMO->isInvariant()));
5025 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5027 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5028 cast<StoreSDNode>(E)->refineAlignment(MMO);
5029 return SDValue(E, 0);
5031 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5032 dl.getDebugLoc(), VTs,
5033 ISD::UNINDEXED, true, SVT, MMO);
5034 CSEMap.InsertNode(N, IP);
5036 return SDValue(N, 0);
5040 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5041 SDValue Offset, ISD::MemIndexedMode AM) {
5042 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5043 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5044 "Store is already a indexed store!");
5045 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5046 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5047 FoldingSetNodeID ID;
5048 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5049 ID.AddInteger(ST->getMemoryVT().getRawBits());
5050 ID.AddInteger(ST->getRawSubclassData());
5051 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5053 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5054 return SDValue(E, 0);
5056 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5057 dl.getDebugLoc(), VTs, AM,
5058 ST->isTruncatingStore(),
5060 ST->getMemOperand());
5061 CSEMap.InsertNode(N, IP);
5063 return SDValue(N, 0);
5067 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5068 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5069 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5071 SDVTList VTs = getVTList(VT, MVT::Other);
5072 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5073 FoldingSetNodeID ID;
5074 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5075 ID.AddInteger(VT.getRawBits());
5076 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5078 MMO->isNonTemporal(),
5079 MMO->isInvariant()));
5080 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5082 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5083 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5084 return SDValue(E, 0);
5086 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5087 dl.getDebugLoc(), Ops, 4, VTs,
5089 CSEMap.InsertNode(N, IP);
5091 return SDValue(N, 0);
5094 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5095 SDValue Ptr, SDValue Mask, EVT MemVT,
5096 MachineMemOperand *MMO, bool isTrunc) {
5097 assert(Chain.getValueType() == MVT::Other &&
5098 "Invalid chain type");
5099 EVT VT = Val.getValueType();
5100 SDVTList VTs = getVTList(MVT::Other);
5101 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5102 FoldingSetNodeID ID;
5103 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5104 ID.AddInteger(VT.getRawBits());
5105 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5106 MMO->isNonTemporal(), MMO->isInvariant()));
5107 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5109 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5110 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5111 return SDValue(E, 0);
5113 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5114 dl.getDebugLoc(), Ops, 4,
5115 VTs, isTrunc, MemVT, MMO);
5116 CSEMap.InsertNode(N, IP);
5118 return SDValue(N, 0);
5122 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5123 ArrayRef<SDValue> Ops,
5124 MachineMemOperand *MMO) {
5126 FoldingSetNodeID ID;
5127 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5128 ID.AddInteger(VT.getRawBits());
5129 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5131 MMO->isNonTemporal(),
5132 MMO->isInvariant()));
5133 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5135 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5136 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5137 return SDValue(E, 0);
5139 MaskedGatherSDNode *N =
5140 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5142 CSEMap.InsertNode(N, IP);
5144 return SDValue(N, 0);
5147 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5148 ArrayRef<SDValue> Ops,
5149 MachineMemOperand *MMO) {
5150 FoldingSetNodeID ID;
5151 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5152 ID.AddInteger(VT.getRawBits());
5153 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5154 MMO->isNonTemporal(),
5155 MMO->isInvariant()));
5156 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5158 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5159 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5160 return SDValue(E, 0);
5163 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5165 CSEMap.InsertNode(N, IP);
5167 return SDValue(N, 0);
5170 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5171 SDValue Chain, SDValue Ptr,
5174 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5175 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5178 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5179 ArrayRef<SDUse> Ops) {
5180 switch (Ops.size()) {
5181 case 0: return getNode(Opcode, DL, VT);
5182 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5183 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5184 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5188 // Copy from an SDUse array into an SDValue array for use with
5189 // the regular getNode logic.
5190 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5191 return getNode(Opcode, DL, VT, NewOps);
5194 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5195 ArrayRef<SDValue> Ops) {
5196 unsigned NumOps = Ops.size();
5198 case 0: return getNode(Opcode, DL, VT);
5199 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5200 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5201 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5207 case ISD::SELECT_CC: {
5208 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5209 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5210 "LHS and RHS of condition must have same type!");
5211 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5212 "True and False arms of SelectCC must have same type!");
5213 assert(Ops[2].getValueType() == VT &&
5214 "select_cc node must be of same type as true and false value!");
5218 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5219 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5220 "LHS/RHS of comparison should match types!");
5227 SDVTList VTs = getVTList(VT);
5229 if (VT != MVT::Glue) {
5230 FoldingSetNodeID ID;
5231 AddNodeIDNode(ID, Opcode, VTs, Ops);
5234 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5235 return SDValue(E, 0);
5237 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5239 CSEMap.InsertNode(N, IP);
5241 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5246 return SDValue(N, 0);
5249 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5250 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5251 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5254 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5255 ArrayRef<SDValue> Ops) {
5256 if (VTList.NumVTs == 1)
5257 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5261 // FIXME: figure out how to safely handle things like
5262 // int foo(int x) { return 1 << (x & 255); }
5263 // int bar() { return foo(256); }
5264 case ISD::SRA_PARTS:
5265 case ISD::SRL_PARTS:
5266 case ISD::SHL_PARTS:
5267 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5268 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5269 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5270 else if (N3.getOpcode() == ISD::AND)
5271 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5272 // If the and is only masking out bits that cannot effect the shift,
5273 // eliminate the and.
5274 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5275 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5276 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5282 // Memoize the node unless it returns a flag.
5284 unsigned NumOps = Ops.size();
5285 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5286 FoldingSetNodeID ID;
5287 AddNodeIDNode(ID, Opcode, VTList, Ops);
5289 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5290 return SDValue(E, 0);
5293 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5294 DL.getDebugLoc(), VTList, Ops[0]);
5295 } else if (NumOps == 2) {
5296 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5297 DL.getDebugLoc(), VTList, Ops[0],
5299 } else if (NumOps == 3) {
5300 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5301 DL.getDebugLoc(), VTList, Ops[0],
5304 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5307 CSEMap.InsertNode(N, IP);
5310 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5311 DL.getDebugLoc(), VTList, Ops[0]);
5312 } else if (NumOps == 2) {
5313 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5314 DL.getDebugLoc(), VTList, Ops[0],
5316 } else if (NumOps == 3) {
5317 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5318 DL.getDebugLoc(), VTList, Ops[0],
5321 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5326 return SDValue(N, 0);
5329 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5330 return getNode(Opcode, DL, VTList, None);
5333 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5335 SDValue Ops[] = { N1 };
5336 return getNode(Opcode, DL, VTList, Ops);
5339 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5340 SDValue N1, SDValue N2) {
5341 SDValue Ops[] = { N1, N2 };
5342 return getNode(Opcode, DL, VTList, Ops);
5345 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5346 SDValue N1, SDValue N2, SDValue N3) {
5347 SDValue Ops[] = { N1, N2, N3 };
5348 return getNode(Opcode, DL, VTList, Ops);
5351 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5352 SDValue N1, SDValue N2, SDValue N3,
5354 SDValue Ops[] = { N1, N2, N3, N4 };
5355 return getNode(Opcode, DL, VTList, Ops);
5358 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5359 SDValue N1, SDValue N2, SDValue N3,
5360 SDValue N4, SDValue N5) {
5361 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5362 return getNode(Opcode, DL, VTList, Ops);
5365 SDVTList SelectionDAG::getVTList(EVT VT) {
5366 return makeVTList(SDNode::getValueTypeList(VT), 1);
5369 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5370 FoldingSetNodeID ID;
5372 ID.AddInteger(VT1.getRawBits());
5373 ID.AddInteger(VT2.getRawBits());
5376 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5378 EVT *Array = Allocator.Allocate<EVT>(2);
5381 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5382 VTListMap.InsertNode(Result, IP);
5384 return Result->getSDVTList();
5387 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5388 FoldingSetNodeID ID;
5390 ID.AddInteger(VT1.getRawBits());
5391 ID.AddInteger(VT2.getRawBits());
5392 ID.AddInteger(VT3.getRawBits());
5395 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5397 EVT *Array = Allocator.Allocate<EVT>(3);
5401 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5402 VTListMap.InsertNode(Result, IP);
5404 return Result->getSDVTList();
5407 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5408 FoldingSetNodeID ID;
5410 ID.AddInteger(VT1.getRawBits());
5411 ID.AddInteger(VT2.getRawBits());
5412 ID.AddInteger(VT3.getRawBits());
5413 ID.AddInteger(VT4.getRawBits());
5416 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5418 EVT *Array = Allocator.Allocate<EVT>(4);
5423 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5424 VTListMap.InsertNode(Result, IP);
5426 return Result->getSDVTList();
5429 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5430 unsigned NumVTs = VTs.size();
5431 FoldingSetNodeID ID;
5432 ID.AddInteger(NumVTs);
5433 for (unsigned index = 0; index < NumVTs; index++) {
5434 ID.AddInteger(VTs[index].getRawBits());
5438 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5440 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5441 std::copy(VTs.begin(), VTs.end(), Array);
5442 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5443 VTListMap.InsertNode(Result, IP);
5445 return Result->getSDVTList();
5449 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5450 /// specified operands. If the resultant node already exists in the DAG,
5451 /// this does not modify the specified node, instead it returns the node that
5452 /// already exists. If the resultant node does not exist in the DAG, the
5453 /// input node is returned. As a degenerate case, if you specify the same
5454 /// input operands as the node already has, the input node is returned.
5455 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5456 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5458 // Check to see if there is no change.
5459 if (Op == N->getOperand(0)) return N;
5461 // See if the modified node already exists.
5462 void *InsertPos = nullptr;
5463 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5466 // Nope it doesn't. Remove the node from its current place in the maps.
5468 if (!RemoveNodeFromCSEMaps(N))
5469 InsertPos = nullptr;
5471 // Now we update the operands.
5472 N->OperandList[0].set(Op);
5474 // If this gets put into a CSE map, add it.
5475 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5479 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5480 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5482 // Check to see if there is no change.
5483 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5484 return N; // No operands changed, just return the input node.
5486 // See if the modified node already exists.
5487 void *InsertPos = nullptr;
5488 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5491 // Nope it doesn't. Remove the node from its current place in the maps.
5493 if (!RemoveNodeFromCSEMaps(N))
5494 InsertPos = nullptr;
5496 // Now we update the operands.
5497 if (N->OperandList[0] != Op1)
5498 N->OperandList[0].set(Op1);
5499 if (N->OperandList[1] != Op2)
5500 N->OperandList[1].set(Op2);
5502 // If this gets put into a CSE map, add it.
5503 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5507 SDNode *SelectionDAG::
5508 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5509 SDValue Ops[] = { Op1, Op2, Op3 };
5510 return UpdateNodeOperands(N, Ops);
5513 SDNode *SelectionDAG::
5514 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5515 SDValue Op3, SDValue Op4) {
5516 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5517 return UpdateNodeOperands(N, Ops);
5520 SDNode *SelectionDAG::
5521 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5522 SDValue Op3, SDValue Op4, SDValue Op5) {
5523 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5524 return UpdateNodeOperands(N, Ops);
5527 SDNode *SelectionDAG::
5528 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5529 unsigned NumOps = Ops.size();
5530 assert(N->getNumOperands() == NumOps &&
5531 "Update with wrong number of operands");
5533 // If no operands changed just return the input node.
5534 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5537 // See if the modified node already exists.
5538 void *InsertPos = nullptr;
5539 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5542 // Nope it doesn't. Remove the node from its current place in the maps.
5544 if (!RemoveNodeFromCSEMaps(N))
5545 InsertPos = nullptr;
5547 // Now we update the operands.
5548 for (unsigned i = 0; i != NumOps; ++i)
5549 if (N->OperandList[i] != Ops[i])
5550 N->OperandList[i].set(Ops[i]);
5552 // If this gets put into a CSE map, add it.
5553 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5557 /// DropOperands - Release the operands and set this node to have
5559 void SDNode::DropOperands() {
5560 // Unlike the code in MorphNodeTo that does this, we don't need to
5561 // watch for dead nodes here.
5562 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5568 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5571 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5573 SDVTList VTs = getVTList(VT);
5574 return SelectNodeTo(N, MachineOpc, VTs, None);
5577 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5578 EVT VT, SDValue Op1) {
5579 SDVTList VTs = getVTList(VT);
5580 SDValue Ops[] = { Op1 };
5581 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5584 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5585 EVT VT, SDValue Op1,
5587 SDVTList VTs = getVTList(VT);
5588 SDValue Ops[] = { Op1, Op2 };
5589 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5592 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5593 EVT VT, SDValue Op1,
5594 SDValue Op2, SDValue Op3) {
5595 SDVTList VTs = getVTList(VT);
5596 SDValue Ops[] = { Op1, Op2, Op3 };
5597 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5600 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5601 EVT VT, ArrayRef<SDValue> Ops) {
5602 SDVTList VTs = getVTList(VT);
5603 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5606 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5607 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5608 SDVTList VTs = getVTList(VT1, VT2);
5609 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5612 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5614 SDVTList VTs = getVTList(VT1, VT2);
5615 return SelectNodeTo(N, MachineOpc, VTs, None);
5618 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5619 EVT VT1, EVT VT2, EVT VT3,
5620 ArrayRef<SDValue> Ops) {
5621 SDVTList VTs = getVTList(VT1, VT2, VT3);
5622 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5625 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5626 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5627 ArrayRef<SDValue> Ops) {
5628 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5629 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5632 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5635 SDVTList VTs = getVTList(VT1, VT2);
5636 SDValue Ops[] = { Op1 };
5637 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5640 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5642 SDValue Op1, SDValue Op2) {
5643 SDVTList VTs = getVTList(VT1, VT2);
5644 SDValue Ops[] = { Op1, Op2 };
5645 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5648 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5650 SDValue Op1, SDValue Op2,
5652 SDVTList VTs = getVTList(VT1, VT2);
5653 SDValue Ops[] = { Op1, Op2, Op3 };
5654 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5657 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5658 EVT VT1, EVT VT2, EVT VT3,
5659 SDValue Op1, SDValue Op2,
5661 SDVTList VTs = getVTList(VT1, VT2, VT3);
5662 SDValue Ops[] = { Op1, Op2, Op3 };
5663 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5666 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5667 SDVTList VTs,ArrayRef<SDValue> Ops) {
5668 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5669 // Reset the NodeID to -1.
5674 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5675 /// the line number information on the merged node since it is not possible to
5676 /// preserve the information that operation is associated with multiple lines.
5677 /// This will make the debugger working better at -O0, were there is a higher
5678 /// probability having other instructions associated with that line.
5680 /// For IROrder, we keep the smaller of the two
5681 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5682 DebugLoc NLoc = N->getDebugLoc();
5683 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5684 N->setDebugLoc(DebugLoc());
5686 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5687 N->setIROrder(Order);
5691 /// MorphNodeTo - This *mutates* the specified node to have the specified
5692 /// return type, opcode, and operands.
5694 /// Note that MorphNodeTo returns the resultant node. If there is already a
5695 /// node of the specified opcode and operands, it returns that node instead of
5696 /// the current one. Note that the SDLoc need not be the same.
5698 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5699 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5700 /// node, and because it doesn't require CSE recalculation for any of
5701 /// the node's users.
5703 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5704 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5705 /// the legalizer which maintain worklists that would need to be updated when
5706 /// deleting things.
5707 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5708 SDVTList VTs, ArrayRef<SDValue> Ops) {
5709 unsigned NumOps = Ops.size();
5710 // If an identical node already exists, use it.
5712 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5713 FoldingSetNodeID ID;
5714 AddNodeIDNode(ID, Opc, VTs, Ops);
5715 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5716 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5719 if (!RemoveNodeFromCSEMaps(N))
5722 // Start the morphing.
5724 N->ValueList = VTs.VTs;
5725 N->NumValues = VTs.NumVTs;
5727 // Clear the operands list, updating used nodes to remove this from their
5728 // use list. Keep track of any operands that become dead as a result.
5729 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5730 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5732 SDNode *Used = Use.getNode();
5734 if (Used->use_empty())
5735 DeadNodeSet.insert(Used);
5738 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5739 // Initialize the memory references information.
5740 MN->setMemRefs(nullptr, nullptr);
5741 // If NumOps is larger than the # of operands we can have in a
5742 // MachineSDNode, reallocate the operand list.
5743 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5744 if (MN->OperandsNeedDelete)
5745 delete[] MN->OperandList;
5746 if (NumOps > array_lengthof(MN->LocalOperands))
5747 // We're creating a final node that will live unmorphed for the
5748 // remainder of the current SelectionDAG iteration, so we can allocate
5749 // the operands directly out of a pool with no recycling metadata.
5750 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5751 Ops.data(), NumOps);
5753 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5754 MN->OperandsNeedDelete = false;
5756 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5758 // If NumOps is larger than the # of operands we currently have, reallocate
5759 // the operand list.
5760 if (NumOps > N->NumOperands) {
5761 if (N->OperandsNeedDelete)
5762 delete[] N->OperandList;
5763 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5764 N->OperandsNeedDelete = true;
5766 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5769 // Delete any nodes that are still dead after adding the uses for the
5771 if (!DeadNodeSet.empty()) {
5772 SmallVector<SDNode *, 16> DeadNodes;
5773 for (SDNode *N : DeadNodeSet)
5775 DeadNodes.push_back(N);
5776 RemoveDeadNodes(DeadNodes);
5780 CSEMap.InsertNode(N, IP); // Memoize the new node.
5785 /// getMachineNode - These are used for target selectors to create a new node
5786 /// with specified return type(s), MachineInstr opcode, and operands.
5788 /// Note that getMachineNode returns the resultant node. If there is already a
5789 /// node of the specified opcode and operands, it returns that node instead of
5790 /// the current one.
5792 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5793 SDVTList VTs = getVTList(VT);
5794 return getMachineNode(Opcode, dl, VTs, None);
5798 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5799 SDVTList VTs = getVTList(VT);
5800 SDValue Ops[] = { Op1 };
5801 return getMachineNode(Opcode, dl, VTs, Ops);
5805 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5806 SDValue Op1, SDValue Op2) {
5807 SDVTList VTs = getVTList(VT);
5808 SDValue Ops[] = { Op1, Op2 };
5809 return getMachineNode(Opcode, dl, VTs, Ops);
5813 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5814 SDValue Op1, SDValue Op2, SDValue Op3) {
5815 SDVTList VTs = getVTList(VT);
5816 SDValue Ops[] = { Op1, Op2, Op3 };
5817 return getMachineNode(Opcode, dl, VTs, Ops);
5821 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5822 ArrayRef<SDValue> Ops) {
5823 SDVTList VTs = getVTList(VT);
5824 return getMachineNode(Opcode, dl, VTs, Ops);
5828 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5829 SDVTList VTs = getVTList(VT1, VT2);
5830 return getMachineNode(Opcode, dl, VTs, None);
5834 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5835 EVT VT1, EVT VT2, SDValue Op1) {
5836 SDVTList VTs = getVTList(VT1, VT2);
5837 SDValue Ops[] = { Op1 };
5838 return getMachineNode(Opcode, dl, VTs, Ops);
5842 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5843 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5844 SDVTList VTs = getVTList(VT1, VT2);
5845 SDValue Ops[] = { Op1, Op2 };
5846 return getMachineNode(Opcode, dl, VTs, Ops);
5850 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5851 EVT VT1, EVT VT2, SDValue Op1,
5852 SDValue Op2, SDValue Op3) {
5853 SDVTList VTs = getVTList(VT1, VT2);
5854 SDValue Ops[] = { Op1, Op2, Op3 };
5855 return getMachineNode(Opcode, dl, VTs, Ops);
5859 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5861 ArrayRef<SDValue> Ops) {
5862 SDVTList VTs = getVTList(VT1, VT2);
5863 return getMachineNode(Opcode, dl, VTs, Ops);
5867 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5868 EVT VT1, EVT VT2, EVT VT3,
5869 SDValue Op1, SDValue Op2) {
5870 SDVTList VTs = getVTList(VT1, VT2, VT3);
5871 SDValue Ops[] = { Op1, Op2 };
5872 return getMachineNode(Opcode, dl, VTs, Ops);
5876 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5877 EVT VT1, EVT VT2, EVT VT3,
5878 SDValue Op1, SDValue Op2, SDValue Op3) {
5879 SDVTList VTs = getVTList(VT1, VT2, VT3);
5880 SDValue Ops[] = { Op1, Op2, Op3 };
5881 return getMachineNode(Opcode, dl, VTs, Ops);
5885 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5886 EVT VT1, EVT VT2, EVT VT3,
5887 ArrayRef<SDValue> Ops) {
5888 SDVTList VTs = getVTList(VT1, VT2, VT3);
5889 return getMachineNode(Opcode, dl, VTs, Ops);
5893 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5894 EVT VT2, EVT VT3, EVT VT4,
5895 ArrayRef<SDValue> Ops) {
5896 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5897 return getMachineNode(Opcode, dl, VTs, Ops);
5901 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5902 ArrayRef<EVT> ResultTys,
5903 ArrayRef<SDValue> Ops) {
5904 SDVTList VTs = getVTList(ResultTys);
5905 return getMachineNode(Opcode, dl, VTs, Ops);
5909 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5910 ArrayRef<SDValue> OpsArray) {
5911 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5914 const SDValue *Ops = OpsArray.data();
5915 unsigned NumOps = OpsArray.size();
5918 FoldingSetNodeID ID;
5919 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5921 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5922 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5926 // Allocate a new MachineSDNode.
5927 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5928 DL.getDebugLoc(), VTs);
5930 // Initialize the operands list.
5931 if (NumOps > array_lengthof(N->LocalOperands))
5932 // We're creating a final node that will live unmorphed for the
5933 // remainder of the current SelectionDAG iteration, so we can allocate
5934 // the operands directly out of a pool with no recycling metadata.
5935 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5938 N->InitOperands(N->LocalOperands, Ops, NumOps);
5939 N->OperandsNeedDelete = false;
5942 CSEMap.InsertNode(N, IP);
5948 /// getTargetExtractSubreg - A convenience function for creating
5949 /// TargetOpcode::EXTRACT_SUBREG nodes.
5951 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5953 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5954 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5955 VT, Operand, SRIdxVal);
5956 return SDValue(Subreg, 0);
5959 /// getTargetInsertSubreg - A convenience function for creating
5960 /// TargetOpcode::INSERT_SUBREG nodes.
5962 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5963 SDValue Operand, SDValue Subreg) {
5964 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
5965 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5966 VT, Operand, Subreg, SRIdxVal);
5967 return SDValue(Result, 0);
5970 /// getNodeIfExists - Get the specified node if it's already available, or
5971 /// else return NULL.
5972 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5973 ArrayRef<SDValue> Ops,
5974 const SDNodeFlags *Flags) {
5975 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
5976 FoldingSetNodeID ID;
5977 AddNodeIDNode(ID, Opcode, VTList, Ops);
5978 AddNodeIDFlags(ID, Opcode, Flags);
5980 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5986 /// getDbgValue - Creates a SDDbgValue node.
5989 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
5990 unsigned R, bool IsIndirect, uint64_t Off,
5991 DebugLoc DL, unsigned O) {
5992 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
5993 "Expected inlined-at fields to agree");
5994 return new (Allocator) SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
5998 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
5999 const Value *C, uint64_t Off,
6000 DebugLoc DL, unsigned O) {
6001 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6002 "Expected inlined-at fields to agree");
6003 return new (Allocator) SDDbgValue(Var, Expr, C, Off, DL, O);
6007 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6008 unsigned FI, uint64_t Off,
6009 DebugLoc DL, unsigned O) {
6010 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6011 "Expected inlined-at fields to agree");
6012 return new (Allocator) SDDbgValue(Var, Expr, FI, Off, DL, O);
6017 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6018 /// pointed to by a use iterator is deleted, increment the use iterator
6019 /// so that it doesn't dangle.
6021 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6022 SDNode::use_iterator &UI;
6023 SDNode::use_iterator &UE;
6025 void NodeDeleted(SDNode *N, SDNode *E) override {
6026 // Increment the iterator as needed.
6027 while (UI != UE && N == *UI)
6032 RAUWUpdateListener(SelectionDAG &d,
6033 SDNode::use_iterator &ui,
6034 SDNode::use_iterator &ue)
6035 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6040 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6041 /// This can cause recursive merging of nodes in the DAG.
6043 /// This version assumes From has a single result value.
6045 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6046 SDNode *From = FromN.getNode();
6047 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6048 "Cannot replace with this method!");
6049 assert(From != To.getNode() && "Cannot replace uses of with self");
6051 // Iterate over all the existing uses of From. New uses will be added
6052 // to the beginning of the use list, which we avoid visiting.
6053 // This specifically avoids visiting uses of From that arise while the
6054 // replacement is happening, because any such uses would be the result
6055 // of CSE: If an existing node looks like From after one of its operands
6056 // is replaced by To, we don't want to replace of all its users with To
6057 // too. See PR3018 for more info.
6058 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6059 RAUWUpdateListener Listener(*this, UI, UE);
6063 // This node is about to morph, remove its old self from the CSE maps.
6064 RemoveNodeFromCSEMaps(User);
6066 // A user can appear in a use list multiple times, and when this
6067 // happens the uses are usually next to each other in the list.
6068 // To help reduce the number of CSE recomputations, process all
6069 // the uses of this user that we can find this way.
6071 SDUse &Use = UI.getUse();
6074 } while (UI != UE && *UI == User);
6076 // Now that we have modified User, add it back to the CSE maps. If it
6077 // already exists there, recursively merge the results together.
6078 AddModifiedNodeToCSEMaps(User);
6081 // If we just RAUW'd the root, take note.
6082 if (FromN == getRoot())
6086 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6087 /// This can cause recursive merging of nodes in the DAG.
6089 /// This version assumes that for each value of From, there is a
6090 /// corresponding value in To in the same position with the same type.
6092 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6094 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6095 assert((!From->hasAnyUseOfValue(i) ||
6096 From->getValueType(i) == To->getValueType(i)) &&
6097 "Cannot use this version of ReplaceAllUsesWith!");
6100 // Handle the trivial case.
6104 // Iterate over just the existing users of From. See the comments in
6105 // the ReplaceAllUsesWith above.
6106 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6107 RAUWUpdateListener Listener(*this, UI, UE);
6111 // This node is about to morph, remove its old self from the CSE maps.
6112 RemoveNodeFromCSEMaps(User);
6114 // A user can appear in a use list multiple times, and when this
6115 // happens the uses are usually next to each other in the list.
6116 // To help reduce the number of CSE recomputations, process all
6117 // the uses of this user that we can find this way.
6119 SDUse &Use = UI.getUse();
6122 } while (UI != UE && *UI == User);
6124 // Now that we have modified User, add it back to the CSE maps. If it
6125 // already exists there, recursively merge the results together.
6126 AddModifiedNodeToCSEMaps(User);
6129 // If we just RAUW'd the root, take note.
6130 if (From == getRoot().getNode())
6131 setRoot(SDValue(To, getRoot().getResNo()));
6134 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6135 /// This can cause recursive merging of nodes in the DAG.
6137 /// This version can replace From with any result values. To must match the
6138 /// number and types of values returned by From.
6139 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6140 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6141 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6143 // Iterate over just the existing users of From. See the comments in
6144 // the ReplaceAllUsesWith above.
6145 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6146 RAUWUpdateListener Listener(*this, UI, UE);
6150 // This node is about to morph, remove its old self from the CSE maps.
6151 RemoveNodeFromCSEMaps(User);
6153 // A user can appear in a use list multiple times, and when this
6154 // happens the uses are usually next to each other in the list.
6155 // To help reduce the number of CSE recomputations, process all
6156 // the uses of this user that we can find this way.
6158 SDUse &Use = UI.getUse();
6159 const SDValue &ToOp = To[Use.getResNo()];
6162 } while (UI != UE && *UI == User);
6164 // Now that we have modified User, add it back to the CSE maps. If it
6165 // already exists there, recursively merge the results together.
6166 AddModifiedNodeToCSEMaps(User);
6169 // If we just RAUW'd the root, take note.
6170 if (From == getRoot().getNode())
6171 setRoot(SDValue(To[getRoot().getResNo()]));
6174 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6175 /// uses of other values produced by From.getNode() alone. The Deleted
6176 /// vector is handled the same way as for ReplaceAllUsesWith.
6177 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6178 // Handle the really simple, really trivial case efficiently.
6179 if (From == To) return;
6181 // Handle the simple, trivial, case efficiently.
6182 if (From.getNode()->getNumValues() == 1) {
6183 ReplaceAllUsesWith(From, To);
6187 // Iterate over just the existing users of From. See the comments in
6188 // the ReplaceAllUsesWith above.
6189 SDNode::use_iterator UI = From.getNode()->use_begin(),
6190 UE = From.getNode()->use_end();
6191 RAUWUpdateListener Listener(*this, UI, UE);
6194 bool UserRemovedFromCSEMaps = false;
6196 // A user can appear in a use list multiple times, and when this
6197 // happens the uses are usually next to each other in the list.
6198 // To help reduce the number of CSE recomputations, process all
6199 // the uses of this user that we can find this way.
6201 SDUse &Use = UI.getUse();
6203 // Skip uses of different values from the same node.
6204 if (Use.getResNo() != From.getResNo()) {
6209 // If this node hasn't been modified yet, it's still in the CSE maps,
6210 // so remove its old self from the CSE maps.
6211 if (!UserRemovedFromCSEMaps) {
6212 RemoveNodeFromCSEMaps(User);
6213 UserRemovedFromCSEMaps = true;
6218 } while (UI != UE && *UI == User);
6220 // We are iterating over all uses of the From node, so if a use
6221 // doesn't use the specific value, no changes are made.
6222 if (!UserRemovedFromCSEMaps)
6225 // Now that we have modified User, add it back to the CSE maps. If it
6226 // already exists there, recursively merge the results together.
6227 AddModifiedNodeToCSEMaps(User);
6230 // If we just RAUW'd the root, take note.
6231 if (From == getRoot())
6236 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6237 /// to record information about a use.
6244 /// operator< - Sort Memos by User.
6245 bool operator<(const UseMemo &L, const UseMemo &R) {
6246 return (intptr_t)L.User < (intptr_t)R.User;
6250 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6251 /// uses of other values produced by From.getNode() alone. The same value
6252 /// may appear in both the From and To list. The Deleted vector is
6253 /// handled the same way as for ReplaceAllUsesWith.
6254 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6257 // Handle the simple, trivial case efficiently.
6259 return ReplaceAllUsesOfValueWith(*From, *To);
6261 // Read up all the uses and make records of them. This helps
6262 // processing new uses that are introduced during the
6263 // replacement process.
6264 SmallVector<UseMemo, 4> Uses;
6265 for (unsigned i = 0; i != Num; ++i) {
6266 unsigned FromResNo = From[i].getResNo();
6267 SDNode *FromNode = From[i].getNode();
6268 for (SDNode::use_iterator UI = FromNode->use_begin(),
6269 E = FromNode->use_end(); UI != E; ++UI) {
6270 SDUse &Use = UI.getUse();
6271 if (Use.getResNo() == FromResNo) {
6272 UseMemo Memo = { *UI, i, &Use };
6273 Uses.push_back(Memo);
6278 // Sort the uses, so that all the uses from a given User are together.
6279 std::sort(Uses.begin(), Uses.end());
6281 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6282 UseIndex != UseIndexEnd; ) {
6283 // We know that this user uses some value of From. If it is the right
6284 // value, update it.
6285 SDNode *User = Uses[UseIndex].User;
6287 // This node is about to morph, remove its old self from the CSE maps.
6288 RemoveNodeFromCSEMaps(User);
6290 // The Uses array is sorted, so all the uses for a given User
6291 // are next to each other in the list.
6292 // To help reduce the number of CSE recomputations, process all
6293 // the uses of this user that we can find this way.
6295 unsigned i = Uses[UseIndex].Index;
6296 SDUse &Use = *Uses[UseIndex].Use;
6300 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6302 // Now that we have modified User, add it back to the CSE maps. If it
6303 // already exists there, recursively merge the results together.
6304 AddModifiedNodeToCSEMaps(User);
6308 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6309 /// based on their topological order. It returns the maximum id and a vector
6310 /// of the SDNodes* in assigned order by reference.
6311 unsigned SelectionDAG::AssignTopologicalOrder() {
6313 unsigned DAGSize = 0;
6315 // SortedPos tracks the progress of the algorithm. Nodes before it are
6316 // sorted, nodes after it are unsorted. When the algorithm completes
6317 // it is at the end of the list.
6318 allnodes_iterator SortedPos = allnodes_begin();
6320 // Visit all the nodes. Move nodes with no operands to the front of
6321 // the list immediately. Annotate nodes that do have operands with their
6322 // operand count. Before we do this, the Node Id fields of the nodes
6323 // may contain arbitrary values. After, the Node Id fields for nodes
6324 // before SortedPos will contain the topological sort index, and the
6325 // Node Id fields for nodes At SortedPos and after will contain the
6326 // count of outstanding operands.
6327 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6329 checkForCycles(N, this);
6330 unsigned Degree = N->getNumOperands();
6332 // A node with no uses, add it to the result array immediately.
6333 N->setNodeId(DAGSize++);
6334 allnodes_iterator Q = N;
6336 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6337 assert(SortedPos != AllNodes.end() && "Overran node list");
6340 // Temporarily use the Node Id as scratch space for the degree count.
6341 N->setNodeId(Degree);
6345 // Visit all the nodes. As we iterate, move nodes into sorted order,
6346 // such that by the time the end is reached all nodes will be sorted.
6347 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6349 checkForCycles(N, this);
6350 // N is in sorted position, so all its uses have one less operand
6351 // that needs to be sorted.
6352 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6355 unsigned Degree = P->getNodeId();
6356 assert(Degree != 0 && "Invalid node degree");
6359 // All of P's operands are sorted, so P may sorted now.
6360 P->setNodeId(DAGSize++);
6362 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6363 assert(SortedPos != AllNodes.end() && "Overran node list");
6366 // Update P's outstanding operand count.
6367 P->setNodeId(Degree);
6370 if (I == SortedPos) {
6373 dbgs() << "Overran sorted position:\n";
6374 S->dumprFull(this); dbgs() << "\n";
6375 dbgs() << "Checking if this is due to cycles\n";
6376 checkForCycles(this, true);
6378 llvm_unreachable(nullptr);
6382 assert(SortedPos == AllNodes.end() &&
6383 "Topological sort incomplete!");
6384 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6385 "First node in topological sort is not the entry token!");
6386 assert(AllNodes.front().getNodeId() == 0 &&
6387 "First node in topological sort has non-zero id!");
6388 assert(AllNodes.front().getNumOperands() == 0 &&
6389 "First node in topological sort has operands!");
6390 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6391 "Last node in topologic sort has unexpected id!");
6392 assert(AllNodes.back().use_empty() &&
6393 "Last node in topologic sort has users!");
6394 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6398 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6399 /// value is produced by SD.
6400 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6402 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6403 SD->setHasDebugValue(true);
6405 DbgInfo->add(DB, SD, isParameter);
6408 /// TransferDbgValues - Transfer SDDbgValues.
6409 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6410 if (From == To || !From.getNode()->getHasDebugValue())
6412 SDNode *FromNode = From.getNode();
6413 SDNode *ToNode = To.getNode();
6414 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6415 SmallVector<SDDbgValue *, 2> ClonedDVs;
6416 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6418 SDDbgValue *Dbg = *I;
6419 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6421 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6422 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6423 Dbg->getDebugLoc(), Dbg->getOrder());
6424 ClonedDVs.push_back(Clone);
6427 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6428 E = ClonedDVs.end(); I != E; ++I)
6429 AddDbgValue(*I, ToNode, false);
6432 //===----------------------------------------------------------------------===//
6434 //===----------------------------------------------------------------------===//
6436 HandleSDNode::~HandleSDNode() {
6440 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6441 DebugLoc DL, const GlobalValue *GA,
6442 EVT VT, int64_t o, unsigned char TF)
6443 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6447 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6448 SDValue X, unsigned SrcAS,
6450 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6451 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6453 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6454 EVT memvt, MachineMemOperand *mmo)
6455 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6456 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6457 MMO->isNonTemporal(), MMO->isInvariant());
6458 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6459 assert(isNonTemporal() == MMO->isNonTemporal() &&
6460 "Non-temporal encoding error!");
6461 // We check here that the size of the memory operand fits within the size of
6462 // the MMO. This is because the MMO might indicate only a possible address
6463 // range instead of specifying the affected memory addresses precisely.
6464 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6467 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6468 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6469 : SDNode(Opc, Order, dl, VTs, Ops),
6470 MemoryVT(memvt), MMO(mmo) {
6471 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6472 MMO->isNonTemporal(), MMO->isInvariant());
6473 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6474 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6477 /// Profile - Gather unique data for the node.
6479 void SDNode::Profile(FoldingSetNodeID &ID) const {
6480 AddNodeIDNode(ID, this);
6485 std::vector<EVT> VTs;
6488 VTs.reserve(MVT::LAST_VALUETYPE);
6489 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6490 VTs.push_back(MVT((MVT::SimpleValueType)i));
6495 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6496 static ManagedStatic<EVTArray> SimpleVTArray;
6497 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6499 /// getValueTypeList - Return a pointer to the specified value type.
6501 const EVT *SDNode::getValueTypeList(EVT VT) {
6502 if (VT.isExtended()) {
6503 sys::SmartScopedLock<true> Lock(*VTMutex);
6504 return &(*EVTs->insert(VT).first);
6506 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6507 "Value type out of range!");
6508 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6512 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6513 /// indicated value. This method ignores uses of other values defined by this
6515 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6516 assert(Value < getNumValues() && "Bad value!");
6518 // TODO: Only iterate over uses of a given value of the node
6519 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6520 if (UI.getUse().getResNo() == Value) {
6527 // Found exactly the right number of uses?
6532 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6533 /// value. This method ignores uses of other values defined by this operation.
6534 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6535 assert(Value < getNumValues() && "Bad value!");
6537 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6538 if (UI.getUse().getResNo() == Value)
6545 /// isOnlyUserOf - Return true if this node is the only use of N.
6547 bool SDNode::isOnlyUserOf(SDNode *N) const {
6549 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6560 /// isOperand - Return true if this node is an operand of N.
6562 bool SDValue::isOperandOf(SDNode *N) const {
6563 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6564 if (*this == N->getOperand(i))
6569 bool SDNode::isOperandOf(SDNode *N) const {
6570 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6571 if (this == N->OperandList[i].getNode())
6576 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6577 /// be a chain) reaches the specified operand without crossing any
6578 /// side-effecting instructions on any chain path. In practice, this looks
6579 /// through token factors and non-volatile loads. In order to remain efficient,
6580 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6581 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6582 unsigned Depth) const {
6583 if (*this == Dest) return true;
6585 // Don't search too deeply, we just want to be able to see through
6586 // TokenFactor's etc.
6587 if (Depth == 0) return false;
6589 // If this is a token factor, all inputs to the TF happen in parallel. If any
6590 // of the operands of the TF does not reach dest, then we cannot do the xform.
6591 if (getOpcode() == ISD::TokenFactor) {
6592 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6593 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6598 // Loads don't have side effects, look through them.
6599 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6600 if (!Ld->isVolatile())
6601 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6606 /// hasPredecessor - Return true if N is a predecessor of this node.
6607 /// N is either an operand of this node, or can be reached by recursively
6608 /// traversing up the operands.
6609 /// NOTE: This is an expensive method. Use it carefully.
6610 bool SDNode::hasPredecessor(const SDNode *N) const {
6611 SmallPtrSet<const SDNode *, 32> Visited;
6612 SmallVector<const SDNode *, 16> Worklist;
6613 return hasPredecessorHelper(N, Visited, Worklist);
6617 SDNode::hasPredecessorHelper(const SDNode *N,
6618 SmallPtrSetImpl<const SDNode *> &Visited,
6619 SmallVectorImpl<const SDNode *> &Worklist) const {
6620 if (Visited.empty()) {
6621 Worklist.push_back(this);
6623 // Take a look in the visited set. If we've already encountered this node
6624 // we needn't search further.
6625 if (Visited.count(N))
6629 // Haven't visited N yet. Continue the search.
6630 while (!Worklist.empty()) {
6631 const SDNode *M = Worklist.pop_back_val();
6632 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6633 SDNode *Op = M->getOperand(i).getNode();
6634 if (Visited.insert(Op).second)
6635 Worklist.push_back(Op);
6644 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6645 assert(Num < NumOperands && "Invalid child # of SDNode!");
6646 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6649 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6650 assert(N->getNumValues() == 1 &&
6651 "Can't unroll a vector with multiple results!");
6653 EVT VT = N->getValueType(0);
6654 unsigned NE = VT.getVectorNumElements();
6655 EVT EltVT = VT.getVectorElementType();
6658 SmallVector<SDValue, 8> Scalars;
6659 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6661 // If ResNE is 0, fully unroll the vector op.
6664 else if (NE > ResNE)
6668 for (i= 0; i != NE; ++i) {
6669 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6670 SDValue Operand = N->getOperand(j);
6671 EVT OperandVT = Operand.getValueType();
6672 if (OperandVT.isVector()) {
6673 // A vector operand; extract a single element.
6674 EVT OperandEltVT = OperandVT.getVectorElementType();
6675 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6678 getConstant(i, dl, TLI->getVectorIdxTy()));
6680 // A scalar operand; just use it as is.
6681 Operands[j] = Operand;
6685 switch (N->getOpcode()) {
6687 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6690 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6697 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6698 getShiftAmountOperand(Operands[0].getValueType(),
6701 case ISD::SIGN_EXTEND_INREG:
6702 case ISD::FP_ROUND_INREG: {
6703 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6704 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6706 getValueType(ExtVT)));
6711 for (; i < ResNE; ++i)
6712 Scalars.push_back(getUNDEF(EltVT));
6714 return getNode(ISD::BUILD_VECTOR, dl,
6715 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6719 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6720 /// location that is 'Dist' units away from the location that the 'Base' load
6721 /// is loading from.
6722 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6723 unsigned Bytes, int Dist) const {
6724 if (LD->getChain() != Base->getChain())
6726 EVT VT = LD->getValueType(0);
6727 if (VT.getSizeInBits() / 8 != Bytes)
6730 SDValue Loc = LD->getOperand(1);
6731 SDValue BaseLoc = Base->getOperand(1);
6732 if (Loc.getOpcode() == ISD::FrameIndex) {
6733 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6735 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6736 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6737 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6738 int FS = MFI->getObjectSize(FI);
6739 int BFS = MFI->getObjectSize(BFI);
6740 if (FS != BFS || FS != (int)Bytes) return false;
6741 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6745 if (isBaseWithConstantOffset(Loc)) {
6746 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6747 if (Loc.getOperand(0) == BaseLoc) {
6748 // If the base location is a simple address with no offset itself, then
6749 // the second load's first add operand should be the base address.
6750 if (LocOffset == Dist * (int)Bytes)
6752 } else if (isBaseWithConstantOffset(BaseLoc)) {
6753 // The base location itself has an offset, so subtract that value from the
6754 // second load's offset before comparing to distance * size.
6756 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6757 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6758 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6763 const GlobalValue *GV1 = nullptr;
6764 const GlobalValue *GV2 = nullptr;
6765 int64_t Offset1 = 0;
6766 int64_t Offset2 = 0;
6767 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6768 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6769 if (isGA1 && isGA2 && GV1 == GV2)
6770 return Offset1 == (Offset2 + Dist*Bytes);
6775 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6776 /// it cannot be inferred.
6777 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6778 // If this is a GlobalAddress + cst, return the alignment.
6779 const GlobalValue *GV;
6780 int64_t GVOffset = 0;
6781 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6782 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6783 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6784 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6785 *TLI->getDataLayout());
6786 unsigned AlignBits = KnownZero.countTrailingOnes();
6787 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6789 return MinAlign(Align, GVOffset);
6792 // If this is a direct reference to a stack slot, use information about the
6793 // stack slot's alignment.
6794 int FrameIdx = 1 << 31;
6795 int64_t FrameOffset = 0;
6796 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6797 FrameIdx = FI->getIndex();
6798 } else if (isBaseWithConstantOffset(Ptr) &&
6799 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6801 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6802 FrameOffset = Ptr.getConstantOperandVal(1);
6805 if (FrameIdx != (1 << 31)) {
6806 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6807 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6815 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6816 /// which is split (or expanded) into two not necessarily identical pieces.
6817 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6818 // Currently all types are split in half.
6820 if (!VT.isVector()) {
6821 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6823 unsigned NumElements = VT.getVectorNumElements();
6824 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6825 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6828 return std::make_pair(LoVT, HiVT);
6831 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6833 std::pair<SDValue, SDValue>
6834 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6836 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6837 N.getValueType().getVectorNumElements() &&
6838 "More vector elements requested than available!");
6840 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6841 getConstant(0, DL, TLI->getVectorIdxTy()));
6842 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6843 getConstant(LoVT.getVectorNumElements(), DL,
6844 TLI->getVectorIdxTy()));
6845 return std::make_pair(Lo, Hi);
6848 void SelectionDAG::ExtractVectorElements(SDValue Op,
6849 SmallVectorImpl<SDValue> &Args,
6850 unsigned Start, unsigned Count) {
6851 EVT VT = Op.getValueType();
6853 Count = VT.getVectorNumElements();
6855 EVT EltVT = VT.getVectorElementType();
6856 EVT IdxTy = TLI->getVectorIdxTy();
6858 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6859 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6860 Op, getConstant(i, SL, IdxTy)));
6864 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6865 unsigned GlobalAddressSDNode::getAddressSpace() const {
6866 return getGlobal()->getType()->getAddressSpace();
6870 Type *ConstantPoolSDNode::getType() const {
6871 if (isMachineConstantPoolEntry())
6872 return Val.MachineCPVal->getType();
6873 return Val.ConstVal->getType();
6876 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6878 unsigned &SplatBitSize,
6880 unsigned MinSplatBits,
6881 bool isBigEndian) const {
6882 EVT VT = getValueType(0);
6883 assert(VT.isVector() && "Expected a vector type");
6884 unsigned sz = VT.getSizeInBits();
6885 if (MinSplatBits > sz)
6888 SplatValue = APInt(sz, 0);
6889 SplatUndef = APInt(sz, 0);
6891 // Get the bits. Bits with undefined values (when the corresponding element
6892 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6893 // in SplatValue. If any of the values are not constant, give up and return
6895 unsigned int nOps = getNumOperands();
6896 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6897 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6899 for (unsigned j = 0; j < nOps; ++j) {
6900 unsigned i = isBigEndian ? nOps-1-j : j;
6901 SDValue OpVal = getOperand(i);
6902 unsigned BitPos = j * EltBitSize;
6904 if (OpVal.getOpcode() == ISD::UNDEF)
6905 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6906 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6907 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6908 zextOrTrunc(sz) << BitPos;
6909 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6910 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6915 // The build_vector is all constants or undefs. Find the smallest element
6916 // size that splats the vector.
6918 HasAnyUndefs = (SplatUndef != 0);
6921 unsigned HalfSize = sz / 2;
6922 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6923 APInt LowValue = SplatValue.trunc(HalfSize);
6924 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6925 APInt LowUndef = SplatUndef.trunc(HalfSize);
6927 // If the two halves do not match (ignoring undef bits), stop here.
6928 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6929 MinSplatBits > HalfSize)
6932 SplatValue = HighValue | LowValue;
6933 SplatUndef = HighUndef & LowUndef;
6942 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
6943 if (UndefElements) {
6944 UndefElements->clear();
6945 UndefElements->resize(getNumOperands());
6948 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6949 SDValue Op = getOperand(i);
6950 if (Op.getOpcode() == ISD::UNDEF) {
6952 (*UndefElements)[i] = true;
6953 } else if (!Splatted) {
6955 } else if (Splatted != Op) {
6961 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
6962 "Can only have a splat without a constant for all undefs.");
6963 return getOperand(0);
6970 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
6971 return dyn_cast_or_null<ConstantSDNode>(
6972 getSplatValue(UndefElements).getNode());
6976 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
6977 return dyn_cast_or_null<ConstantFPSDNode>(
6978 getSplatValue(UndefElements).getNode());
6981 bool BuildVectorSDNode::isConstant() const {
6982 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6983 unsigned Opc = getOperand(i).getOpcode();
6984 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6990 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6991 // Find the first non-undef value in the shuffle mask.
6993 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6996 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6998 // Make sure all remaining elements are either undef or the same as the first
7000 for (int Idx = Mask[i]; i != e; ++i)
7001 if (Mask[i] >= 0 && Mask[i] != Idx)
7007 static void checkForCyclesHelper(const SDNode *N,
7008 SmallPtrSetImpl<const SDNode*> &Visited,
7009 SmallPtrSetImpl<const SDNode*> &Checked,
7010 const llvm::SelectionDAG *DAG) {
7011 // If this node has already been checked, don't check it again.
7012 if (Checked.count(N))
7015 // If a node has already been visited on this depth-first walk, reject it as
7017 if (!Visited.insert(N).second) {
7018 errs() << "Detected cycle in SelectionDAG\n";
7019 dbgs() << "Offending node:\n";
7020 N->dumprFull(DAG); dbgs() << "\n";
7024 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7025 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7032 void llvm::checkForCycles(const llvm::SDNode *N,
7033 const llvm::SelectionDAG *DAG,
7041 assert(N && "Checking nonexistent SDNode");
7042 SmallPtrSet<const SDNode*, 32> visited;
7043 SmallPtrSet<const SDNode*, 32> checked;
7044 checkForCyclesHelper(N, visited, checked, DAG);
7049 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7050 checkForCycles(DAG->getRoot().getNode(), DAG, force);