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"
56 /// makeVTList - Return an instance of the SDVTList struct initialized with the
57 /// specified members.
58 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
59 SDVTList Res = {VTs, NumVTs};
63 // Default null implementations of the callbacks.
64 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
65 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
67 //===----------------------------------------------------------------------===//
68 // ConstantFPSDNode Class
69 //===----------------------------------------------------------------------===//
71 /// isExactlyValue - We don't rely on operator== working on double values, as
72 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
73 /// As such, this method can be used to do an exact bit-for-bit comparison of
74 /// two floating point values.
75 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
76 return getValueAPF().bitwiseIsEqual(V);
79 bool ConstantFPSDNode::isValueValidForType(EVT VT,
81 assert(VT.isFloatingPoint() && "Can only convert between FP types");
83 // convert modifies in place, so make a copy.
84 APFloat Val2 = APFloat(Val);
86 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
87 APFloat::rmNearestTiesToEven,
92 //===----------------------------------------------------------------------===//
94 //===----------------------------------------------------------------------===//
96 /// isBuildVectorAllOnes - Return true if the specified node is a
97 /// BUILD_VECTOR where all of the elements are ~0 or undef.
98 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
99 // Look through a bit convert.
100 while (N->getOpcode() == ISD::BITCAST)
101 N = N->getOperand(0).getNode();
103 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
105 unsigned i = 0, e = N->getNumOperands();
107 // Skip over all of the undef values.
108 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
111 // Do not accept an all-undef vector.
112 if (i == e) return false;
114 // Do not accept build_vectors that aren't all constants or which have non-~0
115 // elements. We have to be a bit careful here, as the type of the constant
116 // may not be the same as the type of the vector elements due to type
117 // legalization (the elements are promoted to a legal type for the target and
118 // a vector of a type may be legal when the base element type is not).
119 // We only want to check enough bits to cover the vector elements, because
120 // we care if the resultant vector is all ones, not whether the individual
122 SDValue NotZero = N->getOperand(i);
123 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
124 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
125 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
127 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
128 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
133 // Okay, we have at least one ~0 value, check to see if the rest match or are
134 // undefs. Even with the above element type twiddling, this should be OK, as
135 // the same type legalization should have applied to all the elements.
136 for (++i; i != e; ++i)
137 if (N->getOperand(i) != NotZero &&
138 N->getOperand(i).getOpcode() != ISD::UNDEF)
144 /// isBuildVectorAllZeros - Return true if the specified node is a
145 /// BUILD_VECTOR where all of the elements are 0 or undef.
146 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
147 // Look through a bit convert.
148 while (N->getOpcode() == ISD::BITCAST)
149 N = N->getOperand(0).getNode();
151 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
153 bool IsAllUndef = true;
154 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) {
155 if (N->getOperand(i).getOpcode() == ISD::UNDEF)
158 // Do not accept build_vectors that aren't all constants or which have non-0
159 // elements. We have to be a bit careful here, as the type of the constant
160 // may not be the same as the type of the vector elements due to type
161 // legalization (the elements are promoted to a legal type for the target
162 // and a vector of a type may be legal when the base element type is not).
163 // We only want to check enough bits to cover the vector elements, because
164 // we care if the resultant vector is all zeros, not whether the individual
166 SDValue Zero = N->getOperand(i);
167 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
168 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
169 if (CN->getAPIntValue().countTrailingZeros() < EltSize)
171 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
172 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize)
178 // Do not accept an all-undef vector.
184 /// \brief Return true if the specified node is a BUILD_VECTOR node of
185 /// all ConstantSDNode or undef.
186 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
187 if (N->getOpcode() != ISD::BUILD_VECTOR)
190 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
191 SDValue Op = N->getOperand(i);
192 if (Op.getOpcode() == ISD::UNDEF)
194 if (!isa<ConstantSDNode>(Op))
200 /// \brief Return true if the specified node is a BUILD_VECTOR node of
201 /// all ConstantFPSDNode or undef.
202 bool ISD::isBuildVectorOfConstantFPSDNodes(const SDNode *N) {
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
206 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
207 SDValue Op = N->getOperand(i);
208 if (Op.getOpcode() == ISD::UNDEF)
210 if (!isa<ConstantFPSDNode>(Op))
216 /// isScalarToVector - Return true if the specified node is a
217 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
218 /// element is not an undef.
219 bool ISD::isScalarToVector(const SDNode *N) {
220 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
223 if (N->getOpcode() != ISD::BUILD_VECTOR)
225 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
227 unsigned NumElems = N->getNumOperands();
230 for (unsigned i = 1; i < NumElems; ++i) {
231 SDValue V = N->getOperand(i);
232 if (V.getOpcode() != ISD::UNDEF)
238 /// allOperandsUndef - Return true if the node has at least one operand
239 /// and all operands of the specified node are ISD::UNDEF.
240 bool ISD::allOperandsUndef(const SDNode *N) {
241 // Return false if the node has no operands.
242 // This is "logically inconsistent" with the definition of "all" but
243 // is probably the desired behavior.
244 if (N->getNumOperands() == 0)
247 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
248 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
254 ISD::NodeType ISD::getExtForLoadExtType(bool IsFP, ISD::LoadExtType ExtType) {
257 return IsFP ? ISD::FP_EXTEND : ISD::ANY_EXTEND;
259 return ISD::SIGN_EXTEND;
261 return ISD::ZERO_EXTEND;
266 llvm_unreachable("Invalid LoadExtType");
269 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
270 /// when given the operation for (X op Y).
271 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
272 // To perform this operation, we just need to swap the L and G bits of the
274 unsigned OldL = (Operation >> 2) & 1;
275 unsigned OldG = (Operation >> 1) & 1;
276 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
277 (OldL << 1) | // New G bit
278 (OldG << 2)); // New L bit.
281 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
282 /// 'op' is a valid SetCC operation.
283 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
284 unsigned Operation = Op;
286 Operation ^= 7; // Flip L, G, E bits, but not U.
288 Operation ^= 15; // Flip all of the condition bits.
290 if (Operation > ISD::SETTRUE2)
291 Operation &= ~8; // Don't let N and U bits get set.
293 return ISD::CondCode(Operation);
297 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
298 /// signed operation and 2 if the result is an unsigned comparison. Return zero
299 /// if the operation does not depend on the sign of the input (setne and seteq).
300 static int isSignedOp(ISD::CondCode Opcode) {
302 default: llvm_unreachable("Illegal integer setcc operation!");
304 case ISD::SETNE: return 0;
308 case ISD::SETGE: return 1;
312 case ISD::SETUGE: return 2;
316 /// getSetCCOrOperation - Return the result of a logical OR between different
317 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
318 /// returns SETCC_INVALID if it is not possible to represent the resultant
320 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
322 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
323 // Cannot fold a signed integer setcc with an unsigned integer setcc.
324 return ISD::SETCC_INVALID;
326 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
328 // If the N and U bits get set then the resultant comparison DOES suddenly
329 // care about orderedness, and is true when ordered.
330 if (Op > ISD::SETTRUE2)
331 Op &= ~16; // Clear the U bit if the N bit is set.
333 // Canonicalize illegal integer setcc's.
334 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
337 return ISD::CondCode(Op);
340 /// getSetCCAndOperation - Return the result of a logical AND between different
341 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
342 /// function returns zero if it is not possible to represent the resultant
344 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
346 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
347 // Cannot fold a signed setcc with an unsigned setcc.
348 return ISD::SETCC_INVALID;
350 // Combine all of the condition bits.
351 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
353 // Canonicalize illegal integer setcc's.
357 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
358 case ISD::SETOEQ: // SETEQ & SETU[LG]E
359 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
360 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
361 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
368 //===----------------------------------------------------------------------===//
369 // SDNode Profile Support
370 //===----------------------------------------------------------------------===//
372 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
374 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
378 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
379 /// solely with their pointer.
380 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
381 ID.AddPointer(VTList.VTs);
384 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
386 static void AddNodeIDOperands(FoldingSetNodeID &ID,
387 ArrayRef<SDValue> Ops) {
388 for (auto& Op : Ops) {
389 ID.AddPointer(Op.getNode());
390 ID.AddInteger(Op.getResNo());
394 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
396 static void AddNodeIDOperands(FoldingSetNodeID &ID,
397 ArrayRef<SDUse> Ops) {
398 for (auto& Op : Ops) {
399 ID.AddPointer(Op.getNode());
400 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 || !isBinOpWithFlags(Opcode))
409 unsigned RawFlags = Flags->getRawFlags();
410 // If no flags are set, do not alter the ID. We must match the ID of nodes
411 // that were created without explicitly specifying flags. This also saves time
412 // and allows a gradual increase in API usage of the optional optimization
415 ID.AddInteger(RawFlags);
418 static void AddNodeIDFlags(FoldingSetNodeID &ID, const SDNode *N) {
419 if (auto *Node = dyn_cast<BinaryWithFlagsSDNode>(N))
420 AddNodeIDFlags(ID, Node->getOpcode(), &Node->Flags);
423 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
424 SDVTList VTList, ArrayRef<SDValue> OpList) {
425 AddNodeIDOpcode(ID, OpC);
426 AddNodeIDValueTypes(ID, VTList);
427 AddNodeIDOperands(ID, OpList);
430 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
432 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
433 switch (N->getOpcode()) {
434 case ISD::TargetExternalSymbol:
435 case ISD::ExternalSymbol:
436 llvm_unreachable("Should only be used on nodes with operands");
437 default: break; // Normal nodes don't need extra info.
438 case ISD::TargetConstant:
439 case ISD::Constant: {
440 const ConstantSDNode *C = cast<ConstantSDNode>(N);
441 ID.AddPointer(C->getConstantIntValue());
442 ID.AddBoolean(C->isOpaque());
445 case ISD::TargetConstantFP:
446 case ISD::ConstantFP: {
447 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
450 case ISD::TargetGlobalAddress:
451 case ISD::GlobalAddress:
452 case ISD::TargetGlobalTLSAddress:
453 case ISD::GlobalTLSAddress: {
454 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
455 ID.AddPointer(GA->getGlobal());
456 ID.AddInteger(GA->getOffset());
457 ID.AddInteger(GA->getTargetFlags());
458 ID.AddInteger(GA->getAddressSpace());
461 case ISD::BasicBlock:
462 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
465 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
467 case ISD::RegisterMask:
468 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
471 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
473 case ISD::FrameIndex:
474 case ISD::TargetFrameIndex:
475 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
478 case ISD::TargetJumpTable:
479 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
480 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
482 case ISD::ConstantPool:
483 case ISD::TargetConstantPool: {
484 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
485 ID.AddInteger(CP->getAlignment());
486 ID.AddInteger(CP->getOffset());
487 if (CP->isMachineConstantPoolEntry())
488 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
490 ID.AddPointer(CP->getConstVal());
491 ID.AddInteger(CP->getTargetFlags());
494 case ISD::TargetIndex: {
495 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
496 ID.AddInteger(TI->getIndex());
497 ID.AddInteger(TI->getOffset());
498 ID.AddInteger(TI->getTargetFlags());
502 const LoadSDNode *LD = cast<LoadSDNode>(N);
503 ID.AddInteger(LD->getMemoryVT().getRawBits());
504 ID.AddInteger(LD->getRawSubclassData());
505 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
509 const StoreSDNode *ST = cast<StoreSDNode>(N);
510 ID.AddInteger(ST->getMemoryVT().getRawBits());
511 ID.AddInteger(ST->getRawSubclassData());
512 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
515 case ISD::ATOMIC_CMP_SWAP:
516 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
517 case ISD::ATOMIC_SWAP:
518 case ISD::ATOMIC_LOAD_ADD:
519 case ISD::ATOMIC_LOAD_SUB:
520 case ISD::ATOMIC_LOAD_AND:
521 case ISD::ATOMIC_LOAD_OR:
522 case ISD::ATOMIC_LOAD_XOR:
523 case ISD::ATOMIC_LOAD_NAND:
524 case ISD::ATOMIC_LOAD_MIN:
525 case ISD::ATOMIC_LOAD_MAX:
526 case ISD::ATOMIC_LOAD_UMIN:
527 case ISD::ATOMIC_LOAD_UMAX:
528 case ISD::ATOMIC_LOAD:
529 case ISD::ATOMIC_STORE: {
530 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
531 ID.AddInteger(AT->getMemoryVT().getRawBits());
532 ID.AddInteger(AT->getRawSubclassData());
533 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
536 case ISD::PREFETCH: {
537 const MemSDNode *PF = cast<MemSDNode>(N);
538 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
541 case ISD::VECTOR_SHUFFLE: {
542 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
543 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
545 ID.AddInteger(SVN->getMaskElt(i));
548 case ISD::TargetBlockAddress:
549 case ISD::BlockAddress: {
550 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
551 ID.AddPointer(BA->getBlockAddress());
552 ID.AddInteger(BA->getOffset());
553 ID.AddInteger(BA->getTargetFlags());
556 } // end switch (N->getOpcode())
558 AddNodeIDFlags(ID, N);
560 // Target specific memory nodes could also have address spaces to check.
561 if (N->isTargetMemoryOpcode())
562 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
565 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
567 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
568 AddNodeIDOpcode(ID, N->getOpcode());
569 // Add the return value info.
570 AddNodeIDValueTypes(ID, N->getVTList());
571 // Add the operand info.
572 AddNodeIDOperands(ID, N->ops());
574 // Handle SDNode leafs with special info.
575 AddNodeIDCustom(ID, N);
578 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
579 /// the CSE map that carries volatility, temporalness, indexing mode, and
580 /// extension/truncation information.
582 static inline unsigned
583 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
584 bool isNonTemporal, bool isInvariant) {
585 assert((ConvType & 3) == ConvType &&
586 "ConvType may not require more than 2 bits!");
587 assert((AM & 7) == AM &&
588 "AM may not require more than 3 bits!");
592 (isNonTemporal << 6) |
596 //===----------------------------------------------------------------------===//
597 // SelectionDAG Class
598 //===----------------------------------------------------------------------===//
600 /// doNotCSE - Return true if CSE should not be performed for this node.
601 static bool doNotCSE(SDNode *N) {
602 if (N->getValueType(0) == MVT::Glue)
603 return true; // Never CSE anything that produces a flag.
605 switch (N->getOpcode()) {
607 case ISD::HANDLENODE:
609 return true; // Never CSE these nodes.
612 // Check that remaining values produced are not flags.
613 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
614 if (N->getValueType(i) == MVT::Glue)
615 return true; // Never CSE anything that produces a flag.
620 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
622 void SelectionDAG::RemoveDeadNodes() {
623 // Create a dummy node (which is not added to allnodes), that adds a reference
624 // to the root node, preventing it from being deleted.
625 HandleSDNode Dummy(getRoot());
627 SmallVector<SDNode*, 128> DeadNodes;
629 // Add all obviously-dead nodes to the DeadNodes worklist.
630 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
632 DeadNodes.push_back(I);
634 RemoveDeadNodes(DeadNodes);
636 // If the root changed (e.g. it was a dead load, update the root).
637 setRoot(Dummy.getValue());
640 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
641 /// given list, and any nodes that become unreachable as a result.
642 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
644 // Process the worklist, deleting the nodes and adding their uses to the
646 while (!DeadNodes.empty()) {
647 SDNode *N = DeadNodes.pop_back_val();
649 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
650 DUL->NodeDeleted(N, nullptr);
652 // Take the node out of the appropriate CSE map.
653 RemoveNodeFromCSEMaps(N);
655 // Next, brutally remove the operand list. This is safe to do, as there are
656 // no cycles in the graph.
657 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
659 SDNode *Operand = Use.getNode();
662 // Now that we removed this operand, see if there are no uses of it left.
663 if (Operand->use_empty())
664 DeadNodes.push_back(Operand);
671 void SelectionDAG::RemoveDeadNode(SDNode *N){
672 SmallVector<SDNode*, 16> DeadNodes(1, N);
674 // Create a dummy node that adds a reference to the root node, preventing
675 // it from being deleted. (This matters if the root is an operand of the
677 HandleSDNode Dummy(getRoot());
679 RemoveDeadNodes(DeadNodes);
682 void SelectionDAG::DeleteNode(SDNode *N) {
683 // First take this out of the appropriate CSE map.
684 RemoveNodeFromCSEMaps(N);
686 // Finally, remove uses due to operands of this node, remove from the
687 // AllNodes list, and delete the node.
688 DeleteNodeNotInCSEMaps(N);
691 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
692 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
693 assert(N->use_empty() && "Cannot delete a node that is not dead!");
695 // Drop all of the operands and decrement used node's use counts.
701 void SDDbgInfo::erase(const SDNode *Node) {
702 DbgValMapType::iterator I = DbgValMap.find(Node);
703 if (I == DbgValMap.end())
705 for (auto &Val: I->second)
706 Val->setIsInvalidated();
710 void SelectionDAG::DeallocateNode(SDNode *N) {
711 if (N->OperandsNeedDelete)
712 delete[] N->OperandList;
714 // Set the opcode to DELETED_NODE to help catch bugs when node
715 // memory is reallocated.
716 N->NodeType = ISD::DELETED_NODE;
718 NodeAllocator.Deallocate(AllNodes.remove(N));
720 // If any of the SDDbgValue nodes refer to this SDNode, invalidate
721 // them and forget about that node.
726 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
727 static void VerifySDNode(SDNode *N) {
728 switch (N->getOpcode()) {
731 case ISD::BUILD_PAIR: {
732 EVT VT = N->getValueType(0);
733 assert(N->getNumValues() == 1 && "Too many results!");
734 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
735 "Wrong return type!");
736 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
737 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
738 "Mismatched operand types!");
739 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
740 "Wrong operand type!");
741 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
742 "Wrong return type size");
745 case ISD::BUILD_VECTOR: {
746 assert(N->getNumValues() == 1 && "Too many results!");
747 assert(N->getValueType(0).isVector() && "Wrong return type!");
748 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
749 "Wrong number of operands!");
750 EVT EltVT = N->getValueType(0).getVectorElementType();
751 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
752 assert((I->getValueType() == EltVT ||
753 (EltVT.isInteger() && I->getValueType().isInteger() &&
754 EltVT.bitsLE(I->getValueType()))) &&
755 "Wrong operand type!");
756 assert(I->getValueType() == N->getOperand(0).getValueType() &&
757 "Operands must all have the same type");
765 /// \brief Insert a newly allocated node into the DAG.
767 /// Handles insertion into the all nodes list and CSE map, as well as
768 /// verification and other common operations when a new node is allocated.
769 void SelectionDAG::InsertNode(SDNode *N) {
770 AllNodes.push_back(N);
776 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
777 /// correspond to it. This is useful when we're about to delete or repurpose
778 /// the node. We don't want future request for structurally identical nodes
779 /// to return N anymore.
780 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
782 switch (N->getOpcode()) {
783 case ISD::HANDLENODE: return false; // noop.
785 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
786 "Cond code doesn't exist!");
787 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
788 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
790 case ISD::ExternalSymbol:
791 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
793 case ISD::TargetExternalSymbol: {
794 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
795 Erased = TargetExternalSymbols.erase(
796 std::pair<std::string,unsigned char>(ESN->getSymbol(),
797 ESN->getTargetFlags()));
800 case ISD::VALUETYPE: {
801 EVT VT = cast<VTSDNode>(N)->getVT();
802 if (VT.isExtended()) {
803 Erased = ExtendedValueTypeNodes.erase(VT);
805 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
806 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
811 // Remove it from the CSE Map.
812 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
813 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
814 Erased = CSEMap.RemoveNode(N);
818 // Verify that the node was actually in one of the CSE maps, unless it has a
819 // flag result (which cannot be CSE'd) or is one of the special cases that are
820 // not subject to CSE.
821 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
822 !N->isMachineOpcode() && !doNotCSE(N)) {
825 llvm_unreachable("Node is not in map!");
831 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
832 /// maps and modified in place. Add it back to the CSE maps, unless an identical
833 /// node already exists, in which case transfer all its users to the existing
834 /// node. This transfer can potentially trigger recursive merging.
837 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
838 // For node types that aren't CSE'd, just act as if no identical node
841 SDNode *Existing = CSEMap.GetOrInsertNode(N);
843 // If there was already an existing matching node, use ReplaceAllUsesWith
844 // to replace the dead one with the existing one. This can cause
845 // recursive merging of other unrelated nodes down the line.
846 ReplaceAllUsesWith(N, Existing);
848 // N is now dead. Inform the listeners and delete it.
849 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
850 DUL->NodeDeleted(N, Existing);
851 DeleteNodeNotInCSEMaps(N);
856 // If the node doesn't already exist, we updated it. Inform listeners.
857 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
861 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
862 /// were replaced with those specified. If this node is never memoized,
863 /// return null, otherwise return a pointer to the slot it would take. If a
864 /// node already exists with these operands, the slot will be non-null.
865 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
870 SDValue Ops[] = { Op };
872 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
873 AddNodeIDCustom(ID, N);
874 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
878 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
879 /// were replaced with those specified. If this node is never memoized,
880 /// return null, otherwise return a pointer to the slot it would take. If a
881 /// node already exists with these operands, the slot will be non-null.
882 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
883 SDValue Op1, SDValue Op2,
888 SDValue Ops[] = { Op1, Op2 };
890 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
891 AddNodeIDCustom(ID, N);
892 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
897 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
898 /// were replaced with those specified. If this node is never memoized,
899 /// return null, otherwise return a pointer to the slot it would take. If a
900 /// node already exists with these operands, the slot will be non-null.
901 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
907 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
908 AddNodeIDCustom(ID, N);
909 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
913 /// getEVTAlignment - Compute the default alignment value for the
916 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
917 Type *Ty = VT == MVT::iPTR ?
918 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
919 VT.getTypeForEVT(*getContext());
921 return TLI->getDataLayout()->getABITypeAlignment(Ty);
924 // EntryNode could meaningfully have debug info if we can find it...
925 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
926 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
927 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
928 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
929 UpdateListeners(nullptr) {
930 AllNodes.push_back(&EntryNode);
931 DbgInfo = new SDDbgInfo();
934 void SelectionDAG::init(MachineFunction &mf) {
936 TLI = getSubtarget().getTargetLowering();
937 TSI = getSubtarget().getSelectionDAGInfo();
938 Context = &mf.getFunction()->getContext();
941 SelectionDAG::~SelectionDAG() {
942 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
947 void SelectionDAG::allnodes_clear() {
948 assert(&*AllNodes.begin() == &EntryNode);
949 AllNodes.remove(AllNodes.begin());
950 while (!AllNodes.empty())
951 DeallocateNode(AllNodes.begin());
954 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
955 SDVTList VTs, SDValue N1,
957 const SDNodeFlags *Flags) {
958 if (isBinOpWithFlags(Opcode)) {
959 // If no flags were passed in, use a default flags object.
961 if (Flags == nullptr)
964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
970 BinarySDNode *N = new (NodeAllocator)
971 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
975 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
977 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
979 switch (N->getOpcode()) {
982 case ISD::ConstantFP:
983 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
984 "debug location. Use another overload.");
990 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
991 DebugLoc DL, void *&InsertPos) {
992 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
994 switch (N->getOpcode()) {
995 default: break; // Process only regular (non-target) constant nodes.
997 case ISD::ConstantFP:
998 // Erase debug location from the node if the node is used at several
999 // different places to do not propagate one location to all uses as it
1000 // leads to incorrect debug info.
1001 if (N->getDebugLoc() != DL)
1002 N->setDebugLoc(DebugLoc());
1009 void SelectionDAG::clear() {
1011 OperandAllocator.Reset();
1014 ExtendedValueTypeNodes.clear();
1015 ExternalSymbols.clear();
1016 TargetExternalSymbols.clear();
1017 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1018 static_cast<CondCodeSDNode*>(nullptr));
1019 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1020 static_cast<SDNode*>(nullptr));
1022 EntryNode.UseList = nullptr;
1023 AllNodes.push_back(&EntryNode);
1024 Root = getEntryNode();
1028 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1029 return VT.bitsGT(Op.getValueType()) ?
1030 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1031 getNode(ISD::TRUNCATE, DL, VT, Op);
1034 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1035 return VT.bitsGT(Op.getValueType()) ?
1036 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1037 getNode(ISD::TRUNCATE, DL, VT, Op);
1040 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1041 return VT.bitsGT(Op.getValueType()) ?
1042 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1043 getNode(ISD::TRUNCATE, DL, VT, Op);
1046 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1048 if (VT.bitsLE(Op.getValueType()))
1049 return getNode(ISD::TRUNCATE, SL, VT, Op);
1051 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1052 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1055 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1056 assert(!VT.isVector() &&
1057 "getZeroExtendInReg should use the vector element type instead of "
1058 "the vector type!");
1059 if (Op.getValueType() == VT) return Op;
1060 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1061 APInt Imm = APInt::getLowBitsSet(BitWidth,
1062 VT.getSizeInBits());
1063 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1064 getConstant(Imm, DL, Op.getValueType()));
1067 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1068 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1069 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1070 "The sizes of the input and result must match in order to perform the "
1071 "extend in-register.");
1072 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1073 "The destination vector type must have fewer lanes than the input.");
1074 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1077 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1078 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1079 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1080 "The sizes of the input and result must match in order to perform the "
1081 "extend in-register.");
1082 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1083 "The destination vector type must have fewer lanes than the input.");
1084 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1087 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1088 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1089 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1090 "The sizes of the input and result must match in order to perform the "
1091 "extend in-register.");
1092 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1093 "The destination vector type must have fewer lanes than the input.");
1094 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1097 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1099 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1100 EVT EltVT = VT.getScalarType();
1102 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1103 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1106 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1107 EVT EltVT = VT.getScalarType();
1109 switch (TLI->getBooleanContents(VT)) {
1110 case TargetLowering::ZeroOrOneBooleanContent:
1111 case TargetLowering::UndefinedBooleanContent:
1112 TrueValue = getConstant(1, DL, VT);
1114 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1115 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1119 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1122 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1124 EVT EltVT = VT.getScalarType();
1125 assert((EltVT.getSizeInBits() >= 64 ||
1126 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1127 "getConstant with a uint64_t value that doesn't fit in the type!");
1128 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1131 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1134 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1137 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1138 bool isT, bool isO) {
1139 assert(VT.isInteger() && "Cannot create FP integer constant!");
1141 EVT EltVT = VT.getScalarType();
1142 const ConstantInt *Elt = &Val;
1144 // In some cases the vector type is legal but the element type is illegal and
1145 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1146 // inserted value (the type does not need to match the vector element type).
1147 // Any extra bits introduced will be truncated away.
1148 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1149 TargetLowering::TypePromoteInteger) {
1150 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1151 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1152 Elt = ConstantInt::get(*getContext(), NewVal);
1154 // In other cases the element type is illegal and needs to be expanded, for
1155 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1156 // the value into n parts and use a vector type with n-times the elements.
1157 // Then bitcast to the type requested.
1158 // Legalizing constants too early makes the DAGCombiner's job harder so we
1159 // only legalize if the DAG tells us we must produce legal types.
1160 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1161 TLI->getTypeAction(*getContext(), EltVT) ==
1162 TargetLowering::TypeExpandInteger) {
1163 APInt NewVal = Elt->getValue();
1164 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1165 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1166 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1167 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1169 // Check the temporary vector is the correct size. If this fails then
1170 // getTypeToTransformTo() probably returned a type whose size (in bits)
1171 // isn't a power-of-2 factor of the requested type size.
1172 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1174 SmallVector<SDValue, 2> EltParts;
1175 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1176 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1177 .trunc(ViaEltSizeInBits), DL,
1178 ViaEltVT, isT, isO));
1181 // EltParts is currently in little endian order. If we actually want
1182 // big-endian order then reverse it now.
1183 if (TLI->isBigEndian())
1184 std::reverse(EltParts.begin(), EltParts.end());
1186 // The elements must be reversed when the element order is different
1187 // to the endianness of the elements (because the BITCAST is itself a
1188 // vector shuffle in this situation). However, we do not need any code to
1189 // perform this reversal because getConstant() is producing a vector
1191 // This situation occurs in MIPS MSA.
1193 SmallVector<SDValue, 8> Ops;
1194 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1195 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1197 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1198 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1203 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1204 "APInt size does not match type size!");
1205 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1206 FoldingSetNodeID ID;
1207 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1211 SDNode *N = nullptr;
1212 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1214 return SDValue(N, 0);
1217 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1219 CSEMap.InsertNode(N, IP);
1223 SDValue Result(N, 0);
1224 if (VT.isVector()) {
1225 SmallVector<SDValue, 8> Ops;
1226 Ops.assign(VT.getVectorNumElements(), Result);
1227 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1232 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1233 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1236 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1238 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1241 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1243 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1245 EVT EltVT = VT.getScalarType();
1247 // Do the map lookup using the actual bit pattern for the floating point
1248 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1249 // we don't have issues with SNANs.
1250 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1251 FoldingSetNodeID ID;
1252 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1255 SDNode *N = nullptr;
1256 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1258 return SDValue(N, 0);
1261 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1263 CSEMap.InsertNode(N, IP);
1267 SDValue Result(N, 0);
1268 if (VT.isVector()) {
1269 SmallVector<SDValue, 8> Ops;
1270 Ops.assign(VT.getVectorNumElements(), Result);
1271 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1276 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1278 EVT EltVT = VT.getScalarType();
1279 if (EltVT==MVT::f32)
1280 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1281 else if (EltVT==MVT::f64)
1282 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1283 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1286 APFloat apf = APFloat(Val);
1287 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1289 return getConstantFP(apf, DL, VT, isTarget);
1291 llvm_unreachable("Unsupported type in getConstantFP");
1294 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1295 EVT VT, int64_t Offset,
1297 unsigned char TargetFlags) {
1298 assert((TargetFlags == 0 || isTargetGA) &&
1299 "Cannot set target flags on target-independent globals");
1301 // Truncate (with sign-extension) the offset value to the pointer size.
1302 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1304 Offset = SignExtend64(Offset, BitWidth);
1307 if (GV->isThreadLocal())
1308 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1310 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1312 FoldingSetNodeID ID;
1313 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1315 ID.AddInteger(Offset);
1316 ID.AddInteger(TargetFlags);
1317 ID.AddInteger(GV->getType()->getAddressSpace());
1319 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1320 return SDValue(E, 0);
1322 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1323 DL.getDebugLoc(), GV, VT,
1324 Offset, TargetFlags);
1325 CSEMap.InsertNode(N, IP);
1327 return SDValue(N, 0);
1330 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1331 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1332 FoldingSetNodeID ID;
1333 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1336 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1337 return SDValue(E, 0);
1339 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1340 CSEMap.InsertNode(N, IP);
1342 return SDValue(N, 0);
1345 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1346 unsigned char TargetFlags) {
1347 assert((TargetFlags == 0 || isTarget) &&
1348 "Cannot set target flags on target-independent jump tables");
1349 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1350 FoldingSetNodeID ID;
1351 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1353 ID.AddInteger(TargetFlags);
1355 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1356 return SDValue(E, 0);
1358 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1360 CSEMap.InsertNode(N, IP);
1362 return SDValue(N, 0);
1365 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1366 unsigned Alignment, int Offset,
1368 unsigned char TargetFlags) {
1369 assert((TargetFlags == 0 || isTarget) &&
1370 "Cannot set target flags on target-independent globals");
1372 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1373 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1374 FoldingSetNodeID ID;
1375 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1376 ID.AddInteger(Alignment);
1377 ID.AddInteger(Offset);
1379 ID.AddInteger(TargetFlags);
1381 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1382 return SDValue(E, 0);
1384 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1385 Alignment, TargetFlags);
1386 CSEMap.InsertNode(N, IP);
1388 return SDValue(N, 0);
1392 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1393 unsigned Alignment, int Offset,
1395 unsigned char TargetFlags) {
1396 assert((TargetFlags == 0 || isTarget) &&
1397 "Cannot set target flags on target-independent globals");
1399 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1400 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1401 FoldingSetNodeID ID;
1402 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1403 ID.AddInteger(Alignment);
1404 ID.AddInteger(Offset);
1405 C->addSelectionDAGCSEId(ID);
1406 ID.AddInteger(TargetFlags);
1408 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1409 return SDValue(E, 0);
1411 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1412 Alignment, TargetFlags);
1413 CSEMap.InsertNode(N, IP);
1415 return SDValue(N, 0);
1418 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1419 unsigned char TargetFlags) {
1420 FoldingSetNodeID ID;
1421 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1422 ID.AddInteger(Index);
1423 ID.AddInteger(Offset);
1424 ID.AddInteger(TargetFlags);
1426 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1427 return SDValue(E, 0);
1429 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1431 CSEMap.InsertNode(N, IP);
1433 return SDValue(N, 0);
1436 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1437 FoldingSetNodeID ID;
1438 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1441 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1442 return SDValue(E, 0);
1444 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1445 CSEMap.InsertNode(N, IP);
1447 return SDValue(N, 0);
1450 SDValue SelectionDAG::getValueType(EVT VT) {
1451 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1452 ValueTypeNodes.size())
1453 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1455 SDNode *&N = VT.isExtended() ?
1456 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1458 if (N) return SDValue(N, 0);
1459 N = new (NodeAllocator) VTSDNode(VT);
1461 return SDValue(N, 0);
1464 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1465 SDNode *&N = ExternalSymbols[Sym];
1466 if (N) return SDValue(N, 0);
1467 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1469 return SDValue(N, 0);
1472 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1473 unsigned char TargetFlags) {
1475 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1477 if (N) return SDValue(N, 0);
1478 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1480 return SDValue(N, 0);
1483 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1484 if ((unsigned)Cond >= CondCodeNodes.size())
1485 CondCodeNodes.resize(Cond+1);
1487 if (!CondCodeNodes[Cond]) {
1488 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1489 CondCodeNodes[Cond] = N;
1493 return SDValue(CondCodeNodes[Cond], 0);
1496 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1497 // the shuffle mask M that point at N1 to point at N2, and indices that point
1498 // N2 to point at N1.
1499 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1501 ShuffleVectorSDNode::commuteMask(M);
1504 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1505 SDValue N2, const int *Mask) {
1506 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1507 "Invalid VECTOR_SHUFFLE");
1509 // Canonicalize shuffle undef, undef -> undef
1510 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1511 return getUNDEF(VT);
1513 // Validate that all indices in Mask are within the range of the elements
1514 // input to the shuffle.
1515 unsigned NElts = VT.getVectorNumElements();
1516 SmallVector<int, 8> MaskVec;
1517 for (unsigned i = 0; i != NElts; ++i) {
1518 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1519 MaskVec.push_back(Mask[i]);
1522 // Canonicalize shuffle v, v -> v, undef
1525 for (unsigned i = 0; i != NElts; ++i)
1526 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1529 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1530 if (N1.getOpcode() == ISD::UNDEF)
1531 commuteShuffle(N1, N2, MaskVec);
1533 // If shuffling a splat, try to blend the splat instead. We do this here so
1534 // that even when this arises during lowering we don't have to re-handle it.
1535 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1536 BitVector UndefElements;
1537 SDValue Splat = BV->getSplatValue(&UndefElements);
1541 for (int i = 0; i < (int)NElts; ++i) {
1542 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1545 // If this input comes from undef, mark it as such.
1546 if (UndefElements[MaskVec[i] - Offset]) {
1551 // If we can blend a non-undef lane, use that instead.
1552 if (!UndefElements[i])
1553 MaskVec[i] = i + Offset;
1556 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1557 BlendSplat(N1BV, 0);
1558 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1559 BlendSplat(N2BV, NElts);
1561 // Canonicalize all index into lhs, -> shuffle lhs, undef
1562 // Canonicalize all index into rhs, -> shuffle rhs, undef
1563 bool AllLHS = true, AllRHS = true;
1564 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1565 for (unsigned i = 0; i != NElts; ++i) {
1566 if (MaskVec[i] >= (int)NElts) {
1571 } else if (MaskVec[i] >= 0) {
1575 if (AllLHS && AllRHS)
1576 return getUNDEF(VT);
1577 if (AllLHS && !N2Undef)
1581 commuteShuffle(N1, N2, MaskVec);
1583 // Reset our undef status after accounting for the mask.
1584 N2Undef = N2.getOpcode() == ISD::UNDEF;
1585 // Re-check whether both sides ended up undef.
1586 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1587 return getUNDEF(VT);
1589 // If Identity shuffle return that node.
1590 bool Identity = true, AllSame = true;
1591 for (unsigned i = 0; i != NElts; ++i) {
1592 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1593 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1595 if (Identity && NElts)
1598 // Shuffling a constant splat doesn't change the result.
1602 // Look through any bitcasts. We check that these don't change the number
1603 // (and size) of elements and just changes their types.
1604 while (V.getOpcode() == ISD::BITCAST)
1605 V = V->getOperand(0);
1607 // A splat should always show up as a build vector node.
1608 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1609 BitVector UndefElements;
1610 SDValue Splat = BV->getSplatValue(&UndefElements);
1611 // If this is a splat of an undef, shuffling it is also undef.
1612 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1613 return getUNDEF(VT);
1616 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1618 // We only have a splat which can skip shuffles if there is a splatted
1619 // value and no undef lanes rearranged by the shuffle.
1620 if (Splat && UndefElements.none()) {
1621 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1622 // number of elements match or the value splatted is a zero constant.
1625 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1626 if (C->isNullValue())
1630 // If the shuffle itself creates a splat, build the vector directly.
1631 if (AllSame && SameNumElts) {
1632 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1633 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1635 EVT BuildVT = BV->getValueType(0);
1636 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1638 // We may have jumped through bitcasts, so the type of the
1639 // BUILD_VECTOR may not match the type of the shuffle.
1641 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1647 FoldingSetNodeID ID;
1648 SDValue Ops[2] = { N1, N2 };
1649 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1650 for (unsigned i = 0; i != NElts; ++i)
1651 ID.AddInteger(MaskVec[i]);
1654 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1655 return SDValue(E, 0);
1657 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1658 // SDNode doesn't have access to it. This memory will be "leaked" when
1659 // the node is deallocated, but recovered when the NodeAllocator is released.
1660 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1661 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1663 ShuffleVectorSDNode *N =
1664 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1665 dl.getDebugLoc(), N1, N2,
1667 CSEMap.InsertNode(N, IP);
1669 return SDValue(N, 0);
1672 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1673 MVT VT = SV.getSimpleValueType(0);
1674 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1675 ShuffleVectorSDNode::commuteMask(MaskVec);
1677 SDValue Op0 = SV.getOperand(0);
1678 SDValue Op1 = SV.getOperand(1);
1679 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1682 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1683 SDValue Val, SDValue DTy,
1684 SDValue STy, SDValue Rnd, SDValue Sat,
1685 ISD::CvtCode Code) {
1686 // If the src and dest types are the same and the conversion is between
1687 // integer types of the same sign or two floats, no conversion is necessary.
1689 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1692 FoldingSetNodeID ID;
1693 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1694 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1696 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1697 return SDValue(E, 0);
1699 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1702 CSEMap.InsertNode(N, IP);
1704 return SDValue(N, 0);
1707 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1708 FoldingSetNodeID ID;
1709 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1710 ID.AddInteger(RegNo);
1712 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1713 return SDValue(E, 0);
1715 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1716 CSEMap.InsertNode(N, IP);
1718 return SDValue(N, 0);
1721 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1722 FoldingSetNodeID ID;
1723 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1724 ID.AddPointer(RegMask);
1726 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1727 return SDValue(E, 0);
1729 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1730 CSEMap.InsertNode(N, IP);
1732 return SDValue(N, 0);
1735 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1736 FoldingSetNodeID ID;
1737 SDValue Ops[] = { Root };
1738 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1739 ID.AddPointer(Label);
1741 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1742 return SDValue(E, 0);
1744 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1745 dl.getDebugLoc(), Root, Label);
1746 CSEMap.InsertNode(N, IP);
1748 return SDValue(N, 0);
1752 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1755 unsigned char TargetFlags) {
1756 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1758 FoldingSetNodeID ID;
1759 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1761 ID.AddInteger(Offset);
1762 ID.AddInteger(TargetFlags);
1764 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1765 return SDValue(E, 0);
1767 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1769 CSEMap.InsertNode(N, IP);
1771 return SDValue(N, 0);
1774 SDValue SelectionDAG::getSrcValue(const Value *V) {
1775 assert((!V || V->getType()->isPointerTy()) &&
1776 "SrcValue is not a pointer?");
1778 FoldingSetNodeID ID;
1779 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1783 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1784 return SDValue(E, 0);
1786 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1787 CSEMap.InsertNode(N, IP);
1789 return SDValue(N, 0);
1792 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1793 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1794 FoldingSetNodeID ID;
1795 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1799 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1800 return SDValue(E, 0);
1802 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1803 CSEMap.InsertNode(N, IP);
1805 return SDValue(N, 0);
1808 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1809 if (VT == V.getValueType())
1812 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1815 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1816 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1817 unsigned SrcAS, unsigned DestAS) {
1818 SDValue Ops[] = {Ptr};
1819 FoldingSetNodeID ID;
1820 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1821 ID.AddInteger(SrcAS);
1822 ID.AddInteger(DestAS);
1825 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1826 return SDValue(E, 0);
1828 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1830 VT, Ptr, SrcAS, DestAS);
1831 CSEMap.InsertNode(N, IP);
1833 return SDValue(N, 0);
1836 /// getShiftAmountOperand - Return the specified value casted to
1837 /// the target's desired shift amount type.
1838 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1839 EVT OpTy = Op.getValueType();
1840 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1841 if (OpTy == ShTy || OpTy.isVector()) return Op;
1843 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1844 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1847 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1848 /// specified value type.
1849 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1850 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1851 unsigned ByteSize = VT.getStoreSize();
1852 Type *Ty = VT.getTypeForEVT(*getContext());
1853 unsigned StackAlign =
1854 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1856 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1857 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1860 /// CreateStackTemporary - Create a stack temporary suitable for holding
1861 /// either of the specified value types.
1862 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1863 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1864 VT2.getStoreSizeInBits())/8;
1865 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1866 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1867 const DataLayout *TD = TLI->getDataLayout();
1868 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1869 TD->getPrefTypeAlignment(Ty2));
1871 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1872 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1873 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1876 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1877 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1878 // These setcc operations always fold.
1882 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1884 case ISD::SETTRUE2: {
1885 TargetLowering::BooleanContent Cnt =
1886 TLI->getBooleanContents(N1->getValueType(0));
1888 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1902 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1906 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1907 const APInt &C2 = N2C->getAPIntValue();
1908 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1909 const APInt &C1 = N1C->getAPIntValue();
1912 default: llvm_unreachable("Unknown integer setcc!");
1913 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1914 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1915 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1916 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1917 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1918 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1919 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1920 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1921 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1922 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1926 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1927 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1928 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1931 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1932 return getUNDEF(VT);
1934 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1935 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1936 return getUNDEF(VT);
1938 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1939 R==APFloat::cmpLessThan, dl, VT);
1940 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1941 return getUNDEF(VT);
1943 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1944 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1945 return getUNDEF(VT);
1947 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1948 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1949 return getUNDEF(VT);
1951 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1952 R==APFloat::cmpEqual, dl, VT);
1953 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1954 return getUNDEF(VT);
1956 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1957 R==APFloat::cmpEqual, dl, VT);
1958 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1959 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1960 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1961 R==APFloat::cmpEqual, dl, VT);
1962 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1963 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1964 R==APFloat::cmpLessThan, dl, VT);
1965 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1966 R==APFloat::cmpUnordered, dl, VT);
1967 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1968 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1971 // Ensure that the constant occurs on the RHS.
1972 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1973 MVT CompVT = N1.getValueType().getSimpleVT();
1974 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1977 return getSetCC(dl, VT, N2, N1, SwappedCond);
1981 // Could not fold it.
1985 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1986 /// use this predicate to simplify operations downstream.
1987 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1988 // This predicate is not safe for vector operations.
1989 if (Op.getValueType().isVector())
1992 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1993 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1996 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1997 /// this predicate to simplify operations downstream. Mask is known to be zero
1998 /// for bits that V cannot have.
1999 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2000 unsigned Depth) const {
2001 APInt KnownZero, KnownOne;
2002 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2003 return (KnownZero & Mask) == Mask;
2006 /// Determine which bits of Op are known to be either zero or one and return
2007 /// them in the KnownZero/KnownOne bitsets.
2008 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2009 APInt &KnownOne, unsigned Depth) const {
2010 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2012 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2014 return; // Limit search depth.
2016 APInt KnownZero2, KnownOne2;
2018 switch (Op.getOpcode()) {
2020 // We know all of the bits for a constant!
2021 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2022 KnownZero = ~KnownOne;
2025 // If either the LHS or the RHS are Zero, the result is zero.
2026 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2027 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2029 // Output known-1 bits are only known if set in both the LHS & RHS.
2030 KnownOne &= KnownOne2;
2031 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2032 KnownZero |= KnownZero2;
2035 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2036 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2038 // Output known-0 bits are only known if clear in both the LHS & RHS.
2039 KnownZero &= KnownZero2;
2040 // Output known-1 are known to be set if set in either the LHS | RHS.
2041 KnownOne |= KnownOne2;
2044 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2045 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2047 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2048 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2049 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2050 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2051 KnownZero = KnownZeroOut;
2055 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2056 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2058 // If low bits are zero in either operand, output low known-0 bits.
2059 // Also compute a conserative estimate for high known-0 bits.
2060 // More trickiness is possible, but this is sufficient for the
2061 // interesting case of alignment computation.
2062 KnownOne.clearAllBits();
2063 unsigned TrailZ = KnownZero.countTrailingOnes() +
2064 KnownZero2.countTrailingOnes();
2065 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2066 KnownZero2.countLeadingOnes(),
2067 BitWidth) - BitWidth;
2069 TrailZ = std::min(TrailZ, BitWidth);
2070 LeadZ = std::min(LeadZ, BitWidth);
2071 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2072 APInt::getHighBitsSet(BitWidth, LeadZ);
2076 // For the purposes of computing leading zeros we can conservatively
2077 // treat a udiv as a logical right shift by the power of 2 known to
2078 // be less than the denominator.
2079 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2080 unsigned LeadZ = KnownZero2.countLeadingOnes();
2082 KnownOne2.clearAllBits();
2083 KnownZero2.clearAllBits();
2084 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2085 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2086 if (RHSUnknownLeadingOnes != BitWidth)
2087 LeadZ = std::min(BitWidth,
2088 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2090 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2094 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2095 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2097 // Only known if known in both the LHS and RHS.
2098 KnownOne &= KnownOne2;
2099 KnownZero &= KnownZero2;
2101 case ISD::SELECT_CC:
2102 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2103 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2105 // Only known if known in both the LHS and RHS.
2106 KnownOne &= KnownOne2;
2107 KnownZero &= KnownZero2;
2115 if (Op.getResNo() != 1)
2117 // The boolean result conforms to getBooleanContents.
2118 // If we know the result of a setcc has the top bits zero, use this info.
2119 // We know that we have an integer-based boolean since these operations
2120 // are only available for integer.
2121 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2122 TargetLowering::ZeroOrOneBooleanContent &&
2124 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2127 // If we know the result of a setcc has the top bits zero, use this info.
2128 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2129 TargetLowering::ZeroOrOneBooleanContent &&
2131 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2134 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2135 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2136 unsigned ShAmt = SA->getZExtValue();
2138 // If the shift count is an invalid immediate, don't do anything.
2139 if (ShAmt >= BitWidth)
2142 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2143 KnownZero <<= ShAmt;
2145 // low bits known zero.
2146 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2150 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2151 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2152 unsigned ShAmt = SA->getZExtValue();
2154 // If the shift count is an invalid immediate, don't do anything.
2155 if (ShAmt >= BitWidth)
2158 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2159 KnownZero = KnownZero.lshr(ShAmt);
2160 KnownOne = KnownOne.lshr(ShAmt);
2162 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2163 KnownZero |= HighBits; // High bits known zero.
2167 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2168 unsigned ShAmt = SA->getZExtValue();
2170 // If the shift count is an invalid immediate, don't do anything.
2171 if (ShAmt >= BitWidth)
2174 // If any of the demanded bits are produced by the sign extension, we also
2175 // demand the input sign bit.
2176 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2178 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2179 KnownZero = KnownZero.lshr(ShAmt);
2180 KnownOne = KnownOne.lshr(ShAmt);
2182 // Handle the sign bits.
2183 APInt SignBit = APInt::getSignBit(BitWidth);
2184 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2186 if (KnownZero.intersects(SignBit)) {
2187 KnownZero |= HighBits; // New bits are known zero.
2188 } else if (KnownOne.intersects(SignBit)) {
2189 KnownOne |= HighBits; // New bits are known one.
2193 case ISD::SIGN_EXTEND_INREG: {
2194 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2195 unsigned EBits = EVT.getScalarType().getSizeInBits();
2197 // Sign extension. Compute the demanded bits in the result that are not
2198 // present in the input.
2199 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2201 APInt InSignBit = APInt::getSignBit(EBits);
2202 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2204 // If the sign extended bits are demanded, we know that the sign
2206 InSignBit = InSignBit.zext(BitWidth);
2207 if (NewBits.getBoolValue())
2208 InputDemandedBits |= InSignBit;
2210 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2211 KnownOne &= InputDemandedBits;
2212 KnownZero &= InputDemandedBits;
2214 // If the sign bit of the input is known set or clear, then we know the
2215 // top bits of the result.
2216 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2217 KnownZero |= NewBits;
2218 KnownOne &= ~NewBits;
2219 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2220 KnownOne |= NewBits;
2221 KnownZero &= ~NewBits;
2222 } else { // Input sign bit unknown
2223 KnownZero &= ~NewBits;
2224 KnownOne &= ~NewBits;
2229 case ISD::CTTZ_ZERO_UNDEF:
2231 case ISD::CTLZ_ZERO_UNDEF:
2233 unsigned LowBits = Log2_32(BitWidth)+1;
2234 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2235 KnownOne.clearAllBits();
2239 LoadSDNode *LD = cast<LoadSDNode>(Op);
2240 // If this is a ZEXTLoad and we are looking at the loaded value.
2241 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2242 EVT VT = LD->getMemoryVT();
2243 unsigned MemBits = VT.getScalarType().getSizeInBits();
2244 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2245 } else if (const MDNode *Ranges = LD->getRanges()) {
2246 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2250 case ISD::ZERO_EXTEND: {
2251 EVT InVT = Op.getOperand(0).getValueType();
2252 unsigned InBits = InVT.getScalarType().getSizeInBits();
2253 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2254 KnownZero = KnownZero.trunc(InBits);
2255 KnownOne = KnownOne.trunc(InBits);
2256 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2257 KnownZero = KnownZero.zext(BitWidth);
2258 KnownOne = KnownOne.zext(BitWidth);
2259 KnownZero |= NewBits;
2262 case ISD::SIGN_EXTEND: {
2263 EVT InVT = Op.getOperand(0).getValueType();
2264 unsigned InBits = InVT.getScalarType().getSizeInBits();
2265 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2267 KnownZero = KnownZero.trunc(InBits);
2268 KnownOne = KnownOne.trunc(InBits);
2269 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2271 // Note if the sign bit is known to be zero or one.
2272 bool SignBitKnownZero = KnownZero.isNegative();
2273 bool SignBitKnownOne = KnownOne.isNegative();
2275 KnownZero = KnownZero.zext(BitWidth);
2276 KnownOne = KnownOne.zext(BitWidth);
2278 // If the sign bit is known zero or one, the top bits match.
2279 if (SignBitKnownZero)
2280 KnownZero |= NewBits;
2281 else if (SignBitKnownOne)
2282 KnownOne |= NewBits;
2285 case ISD::ANY_EXTEND: {
2286 EVT InVT = Op.getOperand(0).getValueType();
2287 unsigned InBits = InVT.getScalarType().getSizeInBits();
2288 KnownZero = KnownZero.trunc(InBits);
2289 KnownOne = KnownOne.trunc(InBits);
2290 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2291 KnownZero = KnownZero.zext(BitWidth);
2292 KnownOne = KnownOne.zext(BitWidth);
2295 case ISD::TRUNCATE: {
2296 EVT InVT = Op.getOperand(0).getValueType();
2297 unsigned InBits = InVT.getScalarType().getSizeInBits();
2298 KnownZero = KnownZero.zext(InBits);
2299 KnownOne = KnownOne.zext(InBits);
2300 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2301 KnownZero = KnownZero.trunc(BitWidth);
2302 KnownOne = KnownOne.trunc(BitWidth);
2305 case ISD::AssertZext: {
2306 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2307 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2308 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2309 KnownZero |= (~InMask);
2310 KnownOne &= (~KnownZero);
2314 // All bits are zero except the low bit.
2315 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2319 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2320 // We know that the top bits of C-X are clear if X contains less bits
2321 // than C (i.e. no wrap-around can happen). For example, 20-X is
2322 // positive if we can prove that X is >= 0 and < 16.
2323 if (CLHS->getAPIntValue().isNonNegative()) {
2324 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2325 // NLZ can't be BitWidth with no sign bit
2326 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2327 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2329 // If all of the MaskV bits are known to be zero, then we know the
2330 // output top bits are zero, because we now know that the output is
2332 if ((KnownZero2 & MaskV) == MaskV) {
2333 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2334 // Top bits known zero.
2335 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2343 // Output known-0 bits are known if clear or set in both the low clear bits
2344 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2345 // low 3 bits clear.
2346 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2347 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2349 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2350 KnownZeroOut = std::min(KnownZeroOut,
2351 KnownZero2.countTrailingOnes());
2353 if (Op.getOpcode() == ISD::ADD) {
2354 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2358 // With ADDE, a carry bit may be added in, so we can only use this
2359 // information if we know (at least) that the low two bits are clear. We
2360 // then return to the caller that the low bit is unknown but that other bits
2362 if (KnownZeroOut >= 2) // ADDE
2363 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2367 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2368 const APInt &RA = Rem->getAPIntValue().abs();
2369 if (RA.isPowerOf2()) {
2370 APInt LowBits = RA - 1;
2371 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2373 // The low bits of the first operand are unchanged by the srem.
2374 KnownZero = KnownZero2 & LowBits;
2375 KnownOne = KnownOne2 & LowBits;
2377 // If the first operand is non-negative or has all low bits zero, then
2378 // the upper bits are all zero.
2379 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2380 KnownZero |= ~LowBits;
2382 // If the first operand is negative and not all low bits are zero, then
2383 // the upper bits are all one.
2384 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2385 KnownOne |= ~LowBits;
2386 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2391 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2392 const APInt &RA = Rem->getAPIntValue();
2393 if (RA.isPowerOf2()) {
2394 APInt LowBits = (RA - 1);
2395 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2397 // The upper bits are all zero, the lower ones are unchanged.
2398 KnownZero = KnownZero2 | ~LowBits;
2399 KnownOne = KnownOne2 & LowBits;
2404 // Since the result is less than or equal to either operand, any leading
2405 // zero bits in either operand must also exist in the result.
2406 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2407 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2409 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2410 KnownZero2.countLeadingOnes());
2411 KnownOne.clearAllBits();
2412 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2415 case ISD::EXTRACT_ELEMENT: {
2416 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2417 const unsigned Index =
2418 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2419 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2421 // Remove low part of known bits mask
2422 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2423 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2425 // Remove high part of known bit mask
2426 KnownZero = KnownZero.trunc(BitWidth);
2427 KnownOne = KnownOne.trunc(BitWidth);
2434 APInt Op0Zero, Op0One;
2435 APInt Op1Zero, Op1One;
2436 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2437 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2439 KnownZero = Op0Zero & Op1Zero;
2440 KnownOne = Op0One & Op1One;
2443 case ISD::FrameIndex:
2444 case ISD::TargetFrameIndex:
2445 if (unsigned Align = InferPtrAlignment(Op)) {
2446 // The low bits are known zero if the pointer is aligned.
2447 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2453 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2456 case ISD::INTRINSIC_WO_CHAIN:
2457 case ISD::INTRINSIC_W_CHAIN:
2458 case ISD::INTRINSIC_VOID:
2459 // Allow the target to implement this method for its nodes.
2460 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2464 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2467 /// ComputeNumSignBits - Return the number of times the sign bit of the
2468 /// register is replicated into the other bits. We know that at least 1 bit
2469 /// is always equal to the sign bit (itself), but other cases can give us
2470 /// information. For example, immediately after an "SRA X, 2", we know that
2471 /// the top 3 bits are all equal to each other, so we return 3.
2472 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2473 EVT VT = Op.getValueType();
2474 assert(VT.isInteger() && "Invalid VT!");
2475 unsigned VTBits = VT.getScalarType().getSizeInBits();
2477 unsigned FirstAnswer = 1;
2480 return 1; // Limit search depth.
2482 switch (Op.getOpcode()) {
2484 case ISD::AssertSext:
2485 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2486 return VTBits-Tmp+1;
2487 case ISD::AssertZext:
2488 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2491 case ISD::Constant: {
2492 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2493 return Val.getNumSignBits();
2496 case ISD::SIGN_EXTEND:
2498 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2499 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2501 case ISD::SIGN_EXTEND_INREG:
2502 // Max of the input and what this extends.
2504 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2507 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2508 return std::max(Tmp, Tmp2);
2511 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2512 // SRA X, C -> adds C sign bits.
2513 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2514 Tmp += C->getZExtValue();
2515 if (Tmp > VTBits) Tmp = VTBits;
2519 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2520 // shl destroys sign bits.
2521 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2522 if (C->getZExtValue() >= VTBits || // Bad shift.
2523 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2524 return Tmp - C->getZExtValue();
2529 case ISD::XOR: // NOT is handled here.
2530 // Logical binary ops preserve the number of sign bits at the worst.
2531 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2533 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2534 FirstAnswer = std::min(Tmp, Tmp2);
2535 // We computed what we know about the sign bits as our first
2536 // answer. Now proceed to the generic code that uses
2537 // computeKnownBits, and pick whichever answer is better.
2542 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2543 if (Tmp == 1) return 1; // Early out.
2544 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2545 return std::min(Tmp, Tmp2);
2550 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2552 return 1; // Early out.
2553 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2554 return std::min(Tmp, Tmp2);
2561 if (Op.getResNo() != 1)
2563 // The boolean result conforms to getBooleanContents. Fall through.
2564 // If setcc returns 0/-1, all bits are sign bits.
2565 // We know that we have an integer-based boolean since these operations
2566 // are only available for integer.
2567 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2568 TargetLowering::ZeroOrNegativeOneBooleanContent)
2572 // If setcc returns 0/-1, all bits are sign bits.
2573 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2574 TargetLowering::ZeroOrNegativeOneBooleanContent)
2579 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2580 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2582 // Handle rotate right by N like a rotate left by 32-N.
2583 if (Op.getOpcode() == ISD::ROTR)
2584 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2586 // If we aren't rotating out all of the known-in sign bits, return the
2587 // number that are left. This handles rotl(sext(x), 1) for example.
2588 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2589 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2593 // Add can have at most one carry bit. Thus we know that the output
2594 // is, at worst, one more bit than the inputs.
2595 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2596 if (Tmp == 1) return 1; // Early out.
2598 // Special case decrementing a value (ADD X, -1):
2599 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2600 if (CRHS->isAllOnesValue()) {
2601 APInt KnownZero, KnownOne;
2602 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2604 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2606 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2609 // If we are subtracting one from a positive number, there is no carry
2610 // out of the result.
2611 if (KnownZero.isNegative())
2615 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2616 if (Tmp2 == 1) return 1;
2617 return std::min(Tmp, Tmp2)-1;
2620 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2621 if (Tmp2 == 1) return 1;
2624 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2625 if (CLHS->isNullValue()) {
2626 APInt KnownZero, KnownOne;
2627 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2628 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2630 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2633 // If the input is known to be positive (the sign bit is known clear),
2634 // the output of the NEG has the same number of sign bits as the input.
2635 if (KnownZero.isNegative())
2638 // Otherwise, we treat this like a SUB.
2641 // Sub can have at most one carry bit. Thus we know that the output
2642 // is, at worst, one more bit than the inputs.
2643 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2644 if (Tmp == 1) return 1; // Early out.
2645 return std::min(Tmp, Tmp2)-1;
2647 // FIXME: it's tricky to do anything useful for this, but it is an important
2648 // case for targets like X86.
2650 case ISD::EXTRACT_ELEMENT: {
2651 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2652 const int BitWidth = Op.getValueType().getSizeInBits();
2654 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2656 // Get reverse index (starting from 1), Op1 value indexes elements from
2657 // little end. Sign starts at big end.
2658 const int rIndex = Items - 1 -
2659 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2661 // If the sign portion ends in our element the substraction gives correct
2662 // result. Otherwise it gives either negative or > bitwidth result
2663 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2667 // If we are looking at the loaded value of the SDNode.
2668 if (Op.getResNo() == 0) {
2669 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2670 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2671 unsigned ExtType = LD->getExtensionType();
2674 case ISD::SEXTLOAD: // '17' bits known
2675 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2676 return VTBits-Tmp+1;
2677 case ISD::ZEXTLOAD: // '16' bits known
2678 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2684 // Allow the target to implement this method for its nodes.
2685 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2686 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2687 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2688 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2689 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2690 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2693 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2694 // use this information.
2695 APInt KnownZero, KnownOne;
2696 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2699 if (KnownZero.isNegative()) { // sign bit is 0
2701 } else if (KnownOne.isNegative()) { // sign bit is 1;
2708 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2709 // the number of identical bits in the top of the input value.
2711 Mask <<= Mask.getBitWidth()-VTBits;
2712 // Return # leading zeros. We use 'min' here in case Val was zero before
2713 // shifting. We don't want to return '64' as for an i32 "0".
2714 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2717 /// isBaseWithConstantOffset - Return true if the specified operand is an
2718 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2719 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2720 /// semantics as an ADD. This handles the equivalence:
2721 /// X|Cst == X+Cst iff X&Cst = 0.
2722 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2723 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2724 !isa<ConstantSDNode>(Op.getOperand(1)))
2727 if (Op.getOpcode() == ISD::OR &&
2728 !MaskedValueIsZero(Op.getOperand(0),
2729 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2736 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2737 // If we're told that NaNs won't happen, assume they won't.
2738 if (getTarget().Options.NoNaNsFPMath)
2741 // If the value is a constant, we can obviously see if it is a NaN or not.
2742 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2743 return !C->getValueAPF().isNaN();
2745 // TODO: Recognize more cases here.
2750 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2751 // If the value is a constant, we can obviously see if it is a zero or not.
2752 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2753 return !C->isZero();
2755 // TODO: Recognize more cases here.
2756 switch (Op.getOpcode()) {
2759 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2760 return !C->isNullValue();
2767 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2768 // Check the obvious case.
2769 if (A == B) return true;
2771 // For for negative and positive zero.
2772 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2773 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2774 if (CA->isZero() && CB->isZero()) return true;
2776 // Otherwise they may not be equal.
2780 /// getNode - Gets or creates the specified node.
2782 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2783 FoldingSetNodeID ID;
2784 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2786 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2787 return SDValue(E, 0);
2789 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2790 DL.getDebugLoc(), getVTList(VT));
2791 CSEMap.InsertNode(N, IP);
2794 return SDValue(N, 0);
2797 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2798 EVT VT, SDValue Operand) {
2799 // Constant fold unary operations with an integer constant operand. Even
2800 // opaque constant will be folded, because the folding of unary operations
2801 // doesn't create new constants with different values. Nevertheless, the
2802 // opaque flag is preserved during folding to prevent future folding with
2804 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2805 const APInt &Val = C->getAPIntValue();
2808 case ISD::SIGN_EXTEND:
2809 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2810 C->isTargetOpcode(), C->isOpaque());
2811 case ISD::ANY_EXTEND:
2812 case ISD::ZERO_EXTEND:
2814 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2815 C->isTargetOpcode(), C->isOpaque());
2816 case ISD::UINT_TO_FP:
2817 case ISD::SINT_TO_FP: {
2818 APFloat apf(EVTToAPFloatSemantics(VT),
2819 APInt::getNullValue(VT.getSizeInBits()));
2820 (void)apf.convertFromAPInt(Val,
2821 Opcode==ISD::SINT_TO_FP,
2822 APFloat::rmNearestTiesToEven);
2823 return getConstantFP(apf, DL, VT);
2826 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2827 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2828 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2829 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2830 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2831 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2834 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2837 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2840 case ISD::CTLZ_ZERO_UNDEF:
2841 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2844 case ISD::CTTZ_ZERO_UNDEF:
2845 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2850 // Constant fold unary operations with a floating point constant operand.
2851 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2852 APFloat V = C->getValueAPF(); // make copy
2856 return getConstantFP(V, DL, VT);
2859 return getConstantFP(V, DL, VT);
2861 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2862 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2863 return getConstantFP(V, DL, VT);
2867 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2868 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2869 return getConstantFP(V, DL, VT);
2873 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2874 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2875 return getConstantFP(V, DL, VT);
2878 case ISD::FP_EXTEND: {
2880 // This can return overflow, underflow, or inexact; we don't care.
2881 // FIXME need to be more flexible about rounding mode.
2882 (void)V.convert(EVTToAPFloatSemantics(VT),
2883 APFloat::rmNearestTiesToEven, &ignored);
2884 return getConstantFP(V, DL, VT);
2886 case ISD::FP_TO_SINT:
2887 case ISD::FP_TO_UINT: {
2890 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2891 // FIXME need to be more flexible about rounding mode.
2892 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2893 Opcode==ISD::FP_TO_SINT,
2894 APFloat::rmTowardZero, &ignored);
2895 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2897 APInt api(VT.getSizeInBits(), x);
2898 return getConstant(api, DL, VT);
2901 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2902 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2903 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2904 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2905 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2906 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2911 // Constant fold unary operations with a vector integer or float operand.
2912 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2913 if (BV->isConstant()) {
2916 // FIXME: Entirely reasonable to perform folding of other unary
2917 // operations here as the need arises.
2924 case ISD::FP_EXTEND:
2925 case ISD::FP_TO_SINT:
2926 case ISD::FP_TO_UINT:
2928 case ISD::UINT_TO_FP:
2929 case ISD::SINT_TO_FP:
2932 case ISD::CTLZ_ZERO_UNDEF:
2934 case ISD::CTTZ_ZERO_UNDEF:
2936 EVT SVT = VT.getScalarType();
2937 EVT InVT = BV->getValueType(0);
2938 EVT InSVT = InVT.getScalarType();
2940 // Find legal integer scalar type for constant promotion and
2941 // ensure that its scalar size is at least as large as source.
2943 if (SVT.isInteger()) {
2944 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2945 if (LegalSVT.bitsLT(SVT)) break;
2948 // Let the above scalar folding handle the folding of each element.
2949 SmallVector<SDValue, 8> Ops;
2950 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2951 SDValue OpN = BV->getOperand(i);
2952 EVT OpVT = OpN.getValueType();
2954 // Build vector (integer) scalar operands may need implicit
2955 // truncation - do this before constant folding.
2956 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2957 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2959 OpN = getNode(Opcode, DL, SVT, OpN);
2961 // Legalize the (integer) scalar constant if necessary.
2962 if (LegalSVT != SVT)
2963 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2965 if (OpN.getOpcode() != ISD::UNDEF &&
2966 OpN.getOpcode() != ISD::Constant &&
2967 OpN.getOpcode() != ISD::ConstantFP)
2971 if (Ops.size() == VT.getVectorNumElements())
2972 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2979 unsigned OpOpcode = Operand.getNode()->getOpcode();
2981 case ISD::TokenFactor:
2982 case ISD::MERGE_VALUES:
2983 case ISD::CONCAT_VECTORS:
2984 return Operand; // Factor, merge or concat of one node? No need.
2985 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2986 case ISD::FP_EXTEND:
2987 assert(VT.isFloatingPoint() &&
2988 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2989 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2990 assert((!VT.isVector() ||
2991 VT.getVectorNumElements() ==
2992 Operand.getValueType().getVectorNumElements()) &&
2993 "Vector element count mismatch!");
2994 if (Operand.getOpcode() == ISD::UNDEF)
2995 return getUNDEF(VT);
2997 case ISD::SIGN_EXTEND:
2998 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2999 "Invalid SIGN_EXTEND!");
3000 if (Operand.getValueType() == VT) return Operand; // noop extension
3001 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3002 "Invalid sext node, dst < src!");
3003 assert((!VT.isVector() ||
3004 VT.getVectorNumElements() ==
3005 Operand.getValueType().getVectorNumElements()) &&
3006 "Vector element count mismatch!");
3007 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3008 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3009 else if (OpOpcode == ISD::UNDEF)
3010 // sext(undef) = 0, because the top bits will all be the same.
3011 return getConstant(0, DL, VT);
3013 case ISD::ZERO_EXTEND:
3014 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3015 "Invalid ZERO_EXTEND!");
3016 if (Operand.getValueType() == VT) return Operand; // noop extension
3017 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3018 "Invalid zext node, dst < src!");
3019 assert((!VT.isVector() ||
3020 VT.getVectorNumElements() ==
3021 Operand.getValueType().getVectorNumElements()) &&
3022 "Vector element count mismatch!");
3023 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3024 return getNode(ISD::ZERO_EXTEND, DL, VT,
3025 Operand.getNode()->getOperand(0));
3026 else if (OpOpcode == ISD::UNDEF)
3027 // zext(undef) = 0, because the top bits will be zero.
3028 return getConstant(0, DL, VT);
3030 case ISD::ANY_EXTEND:
3031 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3032 "Invalid ANY_EXTEND!");
3033 if (Operand.getValueType() == VT) return Operand; // noop extension
3034 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3035 "Invalid anyext node, dst < src!");
3036 assert((!VT.isVector() ||
3037 VT.getVectorNumElements() ==
3038 Operand.getValueType().getVectorNumElements()) &&
3039 "Vector element count mismatch!");
3041 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3042 OpOpcode == ISD::ANY_EXTEND)
3043 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3044 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3045 else if (OpOpcode == ISD::UNDEF)
3046 return getUNDEF(VT);
3048 // (ext (trunx x)) -> x
3049 if (OpOpcode == ISD::TRUNCATE) {
3050 SDValue OpOp = Operand.getNode()->getOperand(0);
3051 if (OpOp.getValueType() == VT)
3056 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3057 "Invalid TRUNCATE!");
3058 if (Operand.getValueType() == VT) return Operand; // noop truncate
3059 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3060 "Invalid truncate node, src < dst!");
3061 assert((!VT.isVector() ||
3062 VT.getVectorNumElements() ==
3063 Operand.getValueType().getVectorNumElements()) &&
3064 "Vector element count mismatch!");
3065 if (OpOpcode == ISD::TRUNCATE)
3066 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3067 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3068 OpOpcode == ISD::ANY_EXTEND) {
3069 // If the source is smaller than the dest, we still need an extend.
3070 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3071 .bitsLT(VT.getScalarType()))
3072 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3073 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3074 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3075 return Operand.getNode()->getOperand(0);
3077 if (OpOpcode == ISD::UNDEF)
3078 return getUNDEF(VT);
3081 assert(VT.isInteger() && VT == Operand.getValueType() &&
3083 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3084 "BSWAP types must be a multiple of 16 bits!");
3085 if (OpOpcode == ISD::UNDEF)
3086 return getUNDEF(VT);
3089 // Basic sanity checking.
3090 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3091 && "Cannot BITCAST between types of different sizes!");
3092 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3093 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3094 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3095 if (OpOpcode == ISD::UNDEF)
3096 return getUNDEF(VT);
3098 case ISD::SCALAR_TO_VECTOR:
3099 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3100 (VT.getVectorElementType() == Operand.getValueType() ||
3101 (VT.getVectorElementType().isInteger() &&
3102 Operand.getValueType().isInteger() &&
3103 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3104 "Illegal SCALAR_TO_VECTOR node!");
3105 if (OpOpcode == ISD::UNDEF)
3106 return getUNDEF(VT);
3107 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3108 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3109 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3110 Operand.getConstantOperandVal(1) == 0 &&
3111 Operand.getOperand(0).getValueType() == VT)
3112 return Operand.getOperand(0);
3115 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3116 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3117 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3118 Operand.getNode()->getOperand(0));
3119 if (OpOpcode == ISD::FNEG) // --X -> X
3120 return Operand.getNode()->getOperand(0);
3123 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3124 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3129 SDVTList VTs = getVTList(VT);
3130 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3131 FoldingSetNodeID ID;
3132 SDValue Ops[1] = { Operand };
3133 AddNodeIDNode(ID, Opcode, VTs, Ops);
3135 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3136 return SDValue(E, 0);
3138 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3139 DL.getDebugLoc(), VTs, Operand);
3140 CSEMap.InsertNode(N, IP);
3142 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3143 DL.getDebugLoc(), VTs, Operand);
3147 return SDValue(N, 0);
3150 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3153 case ISD::ADD: return std::make_pair(C1 + C2, true);
3154 case ISD::SUB: return std::make_pair(C1 - C2, true);
3155 case ISD::MUL: return std::make_pair(C1 * C2, true);
3156 case ISD::AND: return std::make_pair(C1 & C2, true);
3157 case ISD::OR: return std::make_pair(C1 | C2, true);
3158 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3159 case ISD::SHL: return std::make_pair(C1 << C2, true);
3160 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3161 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3162 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3163 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3165 if (!C2.getBoolValue())
3167 return std::make_pair(C1.udiv(C2), true);
3169 if (!C2.getBoolValue())
3171 return std::make_pair(C1.urem(C2), true);
3173 if (!C2.getBoolValue())
3175 return std::make_pair(C1.sdiv(C2), true);
3177 if (!C2.getBoolValue())
3179 return std::make_pair(C1.srem(C2), true);
3181 return std::make_pair(APInt(1, 0), false);
3184 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3185 const ConstantSDNode *Cst1,
3186 const ConstantSDNode *Cst2) {
3187 if (Cst1->isOpaque() || Cst2->isOpaque())
3190 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3191 Cst2->getAPIntValue());
3194 return getConstant(Folded.first, DL, VT);
3197 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3198 SDNode *Cst1, SDNode *Cst2) {
3199 // If the opcode is a target-specific ISD node, there's nothing we can
3200 // do here and the operand rules may not line up with the below, so
3202 if (Opcode >= ISD::BUILTIN_OP_END)
3205 // Handle the case of two scalars.
3206 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3207 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3208 if (SDValue Folded =
3209 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3212 SmallVector<SDValue, 4> Outputs;
3213 // We may have a vector type but a scalar result. Create a splat.
3214 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3215 // Build a big vector out of the scalar elements we generated.
3216 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3223 // For vectors extract each constant element into Inputs so we can constant
3224 // fold them individually.
3225 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3226 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3230 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3232 EVT SVT = VT.getScalarType();
3233 SmallVector<SDValue, 4> Outputs;
3234 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3235 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3236 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3237 if (!V1 || !V2) // Not a constant, bail.
3240 if (V1->isOpaque() || V2->isOpaque())
3243 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3244 // FIXME: This is valid and could be handled by truncating the APInts.
3245 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3248 // Fold one vector element.
3249 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3250 V2->getAPIntValue());
3253 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3256 assert(VT.getVectorNumElements() == Outputs.size() &&
3257 "Vector size mismatch!");
3259 // We may have a vector type but a scalar result. Create a splat.
3260 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3262 // Build a big vector out of the scalar elements we generated.
3263 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3266 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3267 SDValue N2, const SDNodeFlags *Flags) {
3268 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3269 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3272 case ISD::TokenFactor:
3273 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3274 N2.getValueType() == MVT::Other && "Invalid token factor!");
3275 // Fold trivial token factors.
3276 if (N1.getOpcode() == ISD::EntryToken) return N2;
3277 if (N2.getOpcode() == ISD::EntryToken) return N1;
3278 if (N1 == N2) return N1;
3280 case ISD::CONCAT_VECTORS:
3281 // Concat of UNDEFs is UNDEF.
3282 if (N1.getOpcode() == ISD::UNDEF &&
3283 N2.getOpcode() == ISD::UNDEF)
3284 return getUNDEF(VT);
3286 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3287 // one big BUILD_VECTOR.
3288 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3289 N2.getOpcode() == ISD::BUILD_VECTOR) {
3290 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3291 N1.getNode()->op_end());
3292 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3294 // BUILD_VECTOR requires all inputs to be of the same type, find the
3295 // maximum type and extend them all.
3296 EVT SVT = VT.getScalarType();
3297 for (SDValue Op : Elts)
3298 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3299 if (SVT.bitsGT(VT.getScalarType()))
3300 for (SDValue &Op : Elts)
3301 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3302 ? getZExtOrTrunc(Op, DL, SVT)
3303 : getSExtOrTrunc(Op, DL, SVT);
3305 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3309 assert(VT.isInteger() && "This operator does not apply to FP types!");
3310 assert(N1.getValueType() == N2.getValueType() &&
3311 N1.getValueType() == VT && "Binary operator types must match!");
3312 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3313 // worth handling here.
3314 if (N2C && N2C->isNullValue())
3316 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
3323 assert(VT.isInteger() && "This operator does not apply to FP types!");
3324 assert(N1.getValueType() == N2.getValueType() &&
3325 N1.getValueType() == VT && "Binary operator types must match!");
3326 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3327 // it's worth handling here.
3328 if (N2C && N2C->isNullValue())
3338 assert(VT.isInteger() && "This operator does not apply to FP types!");
3339 assert(N1.getValueType() == N2.getValueType() &&
3340 N1.getValueType() == VT && "Binary operator types must match!");
3347 if (getTarget().Options.UnsafeFPMath) {
3348 if (Opcode == ISD::FADD) {
3350 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3351 if (CFP->getValueAPF().isZero())
3354 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3355 if (CFP->getValueAPF().isZero())
3357 } else if (Opcode == ISD::FSUB) {
3359 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3360 if (CFP->getValueAPF().isZero())
3362 } else if (Opcode == ISD::FMUL) {
3363 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3366 // If the first operand isn't the constant, try the second
3368 CFP = dyn_cast<ConstantFPSDNode>(N2);
3375 return SDValue(CFP,0);
3377 if (CFP->isExactlyValue(1.0))
3382 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3383 assert(N1.getValueType() == N2.getValueType() &&
3384 N1.getValueType() == VT && "Binary operator types must match!");
3386 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3387 assert(N1.getValueType() == VT &&
3388 N1.getValueType().isFloatingPoint() &&
3389 N2.getValueType().isFloatingPoint() &&
3390 "Invalid FCOPYSIGN!");
3397 assert(VT == N1.getValueType() &&
3398 "Shift operators return type must be the same as their first arg");
3399 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3400 "Shifts only work on integers");
3401 assert((!VT.isVector() || VT == N2.getValueType()) &&
3402 "Vector shift amounts must be in the same as their first arg");
3403 // Verify that the shift amount VT is bit enough to hold valid shift
3404 // amounts. This catches things like trying to shift an i1024 value by an
3405 // i8, which is easy to fall into in generic code that uses
3406 // TLI.getShiftAmount().
3407 assert(N2.getValueType().getSizeInBits() >=
3408 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3409 "Invalid use of small shift amount with oversized value!");
3411 // Always fold shifts of i1 values so the code generator doesn't need to
3412 // handle them. Since we know the size of the shift has to be less than the
3413 // size of the value, the shift/rotate count is guaranteed to be zero.
3416 if (N2C && N2C->isNullValue())
3419 case ISD::FP_ROUND_INREG: {
3420 EVT EVT = cast<VTSDNode>(N2)->getVT();
3421 assert(VT == N1.getValueType() && "Not an inreg round!");
3422 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3423 "Cannot FP_ROUND_INREG integer types");
3424 assert(EVT.isVector() == VT.isVector() &&
3425 "FP_ROUND_INREG type should be vector iff the operand "
3427 assert((!EVT.isVector() ||
3428 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3429 "Vector element counts must match in FP_ROUND_INREG");
3430 assert(EVT.bitsLE(VT) && "Not rounding down!");
3432 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3436 assert(VT.isFloatingPoint() &&
3437 N1.getValueType().isFloatingPoint() &&
3438 VT.bitsLE(N1.getValueType()) &&
3439 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3440 if (N1.getValueType() == VT) return N1; // noop conversion.
3442 case ISD::AssertSext:
3443 case ISD::AssertZext: {
3444 EVT EVT = cast<VTSDNode>(N2)->getVT();
3445 assert(VT == N1.getValueType() && "Not an inreg extend!");
3446 assert(VT.isInteger() && EVT.isInteger() &&
3447 "Cannot *_EXTEND_INREG FP types");
3448 assert(!EVT.isVector() &&
3449 "AssertSExt/AssertZExt type should be the vector element type "
3450 "rather than the vector type!");
3451 assert(EVT.bitsLE(VT) && "Not extending!");
3452 if (VT == EVT) return N1; // noop assertion.
3455 case ISD::SIGN_EXTEND_INREG: {
3456 EVT EVT = cast<VTSDNode>(N2)->getVT();
3457 assert(VT == N1.getValueType() && "Not an inreg extend!");
3458 assert(VT.isInteger() && EVT.isInteger() &&
3459 "Cannot *_EXTEND_INREG FP types");
3460 assert(EVT.isVector() == VT.isVector() &&
3461 "SIGN_EXTEND_INREG type should be vector iff the operand "
3463 assert((!EVT.isVector() ||
3464 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3465 "Vector element counts must match in SIGN_EXTEND_INREG");
3466 assert(EVT.bitsLE(VT) && "Not extending!");
3467 if (EVT == VT) return N1; // Not actually extending
3469 auto SignExtendInReg = [&](APInt Val) {
3470 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3471 Val <<= Val.getBitWidth() - FromBits;
3472 Val = Val.ashr(Val.getBitWidth() - FromBits);
3473 return getConstant(Val, DL, VT.getScalarType());
3477 APInt Val = N1C->getAPIntValue();
3478 return SignExtendInReg(Val);
3480 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3481 SmallVector<SDValue, 8> Ops;
3482 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3483 SDValue Op = N1.getOperand(i);
3484 if (Op.getValueType() != VT.getScalarType()) break;
3485 if (Op.getOpcode() == ISD::UNDEF) {
3489 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3490 APInt Val = C->getAPIntValue();
3491 Ops.push_back(SignExtendInReg(Val));
3496 if (Ops.size() == VT.getVectorNumElements())
3497 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3501 case ISD::EXTRACT_VECTOR_ELT:
3502 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3503 if (N1.getOpcode() == ISD::UNDEF)
3504 return getUNDEF(VT);
3506 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3507 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3508 return getUNDEF(VT);
3510 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3511 // expanding copies of large vectors from registers.
3513 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3514 N1.getNumOperands() > 0) {
3516 N1.getOperand(0).getValueType().getVectorNumElements();
3517 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3518 N1.getOperand(N2C->getZExtValue() / Factor),
3519 getConstant(N2C->getZExtValue() % Factor, DL,
3520 N2.getValueType()));
3523 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3524 // expanding large vector constants.
3525 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3526 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3528 if (VT != Elt.getValueType())
3529 // If the vector element type is not legal, the BUILD_VECTOR operands
3530 // are promoted and implicitly truncated, and the result implicitly
3531 // extended. Make that explicit here.
3532 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3537 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3538 // operations are lowered to scalars.
3539 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3540 // If the indices are the same, return the inserted element else
3541 // if the indices are known different, extract the element from
3542 // the original vector.
3543 SDValue N1Op2 = N1.getOperand(2);
3544 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3546 if (N1Op2C && N2C) {
3547 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3548 if (VT == N1.getOperand(1).getValueType())
3549 return N1.getOperand(1);
3551 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3554 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3558 case ISD::EXTRACT_ELEMENT:
3559 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3560 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3561 (N1.getValueType().isInteger() == VT.isInteger()) &&
3562 N1.getValueType() != VT &&
3563 "Wrong types for EXTRACT_ELEMENT!");
3565 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3566 // 64-bit integers into 32-bit parts. Instead of building the extract of
3567 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3568 if (N1.getOpcode() == ISD::BUILD_PAIR)
3569 return N1.getOperand(N2C->getZExtValue());
3571 // EXTRACT_ELEMENT of a constant int is also very common.
3572 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3573 unsigned ElementSize = VT.getSizeInBits();
3574 unsigned Shift = ElementSize * N2C->getZExtValue();
3575 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3576 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3579 case ISD::EXTRACT_SUBVECTOR: {
3581 if (VT.isSimple() && N1.getValueType().isSimple()) {
3582 assert(VT.isVector() && N1.getValueType().isVector() &&
3583 "Extract subvector VTs must be a vectors!");
3584 assert(VT.getVectorElementType() ==
3585 N1.getValueType().getVectorElementType() &&
3586 "Extract subvector VTs must have the same element type!");
3587 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3588 "Extract subvector must be from larger vector to smaller vector!");
3590 if (isa<ConstantSDNode>(Index.getNode())) {
3591 assert((VT.getVectorNumElements() +
3592 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3593 <= N1.getValueType().getVectorNumElements())
3594 && "Extract subvector overflow!");
3597 // Trivial extraction.
3598 if (VT.getSimpleVT() == N1.getSimpleValueType())
3605 // Perform trivial constant folding.
3607 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3610 // Canonicalize constant to RHS if commutative.
3611 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3612 std::swap(N1C, N2C);
3616 // Constant fold FP operations.
3617 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3618 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3619 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3621 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3622 // Canonicalize constant to RHS if commutative.
3623 std::swap(N1CFP, N2CFP);
3626 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3627 APFloat::opStatus s;
3630 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3631 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3632 return getConstantFP(V1, DL, VT);
3635 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3636 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3637 return getConstantFP(V1, DL, VT);
3640 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3641 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3642 return getConstantFP(V1, DL, VT);
3645 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3646 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3647 s!=APFloat::opDivByZero)) {
3648 return getConstantFP(V1, DL, VT);
3652 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3653 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3654 s!=APFloat::opDivByZero)) {
3655 return getConstantFP(V1, DL, VT);
3658 case ISD::FCOPYSIGN:
3660 return getConstantFP(V1, DL, VT);
3665 if (Opcode == ISD::FP_ROUND) {
3666 APFloat V = N1CFP->getValueAPF(); // make copy
3668 // This can return overflow, underflow, or inexact; we don't care.
3669 // FIXME need to be more flexible about rounding mode.
3670 (void)V.convert(EVTToAPFloatSemantics(VT),
3671 APFloat::rmNearestTiesToEven, &ignored);
3672 return getConstantFP(V, DL, VT);
3676 // Canonicalize an UNDEF to the RHS, even over a constant.
3677 if (N1.getOpcode() == ISD::UNDEF) {
3678 if (isCommutativeBinOp(Opcode)) {
3682 case ISD::FP_ROUND_INREG:
3683 case ISD::SIGN_EXTEND_INREG:
3689 return N1; // fold op(undef, arg2) -> undef
3697 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3698 // For vectors, we can't easily build an all zero vector, just return
3705 // Fold a bunch of operators when the RHS is undef.
3706 if (N2.getOpcode() == ISD::UNDEF) {
3709 if (N1.getOpcode() == ISD::UNDEF)
3710 // Handle undef ^ undef -> 0 special case. This is a common
3712 return getConstant(0, DL, VT);
3722 return N2; // fold op(arg1, undef) -> undef
3728 if (getTarget().Options.UnsafeFPMath)
3736 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3737 // For vectors, we can't easily build an all zero vector, just return
3742 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3743 // For vectors, we can't easily build an all one vector, just return
3751 // Memoize this node if possible.
3753 SDVTList VTs = getVTList(VT);
3754 if (VT != MVT::Glue) {
3755 SDValue Ops[] = {N1, N2};
3756 FoldingSetNodeID ID;
3757 AddNodeIDNode(ID, Opcode, VTs, Ops);
3758 AddNodeIDFlags(ID, Opcode, Flags);
3760 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3761 return SDValue(E, 0);
3763 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3765 CSEMap.InsertNode(N, IP);
3767 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3771 return SDValue(N, 0);
3774 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3775 SDValue N1, SDValue N2, SDValue N3) {
3776 // Perform various simplifications.
3777 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3780 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3781 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3782 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3783 if (N1CFP && N2CFP && N3CFP) {
3784 APFloat V1 = N1CFP->getValueAPF();
3785 const APFloat &V2 = N2CFP->getValueAPF();
3786 const APFloat &V3 = N3CFP->getValueAPF();
3787 APFloat::opStatus s =
3788 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3789 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3790 return getConstantFP(V1, DL, VT);
3794 case ISD::CONCAT_VECTORS:
3795 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3796 // one big BUILD_VECTOR.
3797 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3798 N2.getOpcode() == ISD::BUILD_VECTOR &&
3799 N3.getOpcode() == ISD::BUILD_VECTOR) {
3800 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3801 N1.getNode()->op_end());
3802 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3803 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3804 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3808 // Use FoldSetCC to simplify SETCC's.
3809 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3810 if (Simp.getNode()) return Simp;
3815 if (N1C->getZExtValue())
3816 return N2; // select true, X, Y -> X
3817 return N3; // select false, X, Y -> Y
3820 if (N2 == N3) return N2; // select C, X, X -> X
3822 case ISD::VECTOR_SHUFFLE:
3823 llvm_unreachable("should use getVectorShuffle constructor!");
3824 case ISD::INSERT_SUBVECTOR: {
3826 if (VT.isSimple() && N1.getValueType().isSimple()
3827 && N2.getValueType().isSimple()) {
3828 assert(VT.isVector() && N1.getValueType().isVector() &&
3829 N2.getValueType().isVector() &&
3830 "Insert subvector VTs must be a vectors");
3831 assert(VT == N1.getValueType() &&
3832 "Dest and insert subvector source types must match!");
3833 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3834 "Insert subvector must be from smaller vector to larger vector!");
3835 if (isa<ConstantSDNode>(Index.getNode())) {
3836 assert((N2.getValueType().getVectorNumElements() +
3837 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3838 <= VT.getVectorNumElements())
3839 && "Insert subvector overflow!");
3842 // Trivial insertion.
3843 if (VT.getSimpleVT() == N2.getSimpleValueType())
3849 // Fold bit_convert nodes from a type to themselves.
3850 if (N1.getValueType() == VT)
3855 // Memoize node if it doesn't produce a flag.
3857 SDVTList VTs = getVTList(VT);
3858 if (VT != MVT::Glue) {
3859 SDValue Ops[] = { N1, N2, N3 };
3860 FoldingSetNodeID ID;
3861 AddNodeIDNode(ID, Opcode, VTs, Ops);
3863 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3864 return SDValue(E, 0);
3866 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3867 DL.getDebugLoc(), VTs, N1, N2, N3);
3868 CSEMap.InsertNode(N, IP);
3870 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3871 DL.getDebugLoc(), VTs, N1, N2, N3);
3875 return SDValue(N, 0);
3878 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3879 SDValue N1, SDValue N2, SDValue N3,
3881 SDValue Ops[] = { N1, N2, N3, N4 };
3882 return getNode(Opcode, DL, VT, Ops);
3885 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3886 SDValue N1, SDValue N2, SDValue N3,
3887 SDValue N4, SDValue N5) {
3888 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3889 return getNode(Opcode, DL, VT, Ops);
3892 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3893 /// the incoming stack arguments to be loaded from the stack.
3894 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3895 SmallVector<SDValue, 8> ArgChains;
3897 // Include the original chain at the beginning of the list. When this is
3898 // used by target LowerCall hooks, this helps legalize find the
3899 // CALLSEQ_BEGIN node.
3900 ArgChains.push_back(Chain);
3902 // Add a chain value for each stack argument.
3903 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3904 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3905 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3906 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3907 if (FI->getIndex() < 0)
3908 ArgChains.push_back(SDValue(L, 1));
3910 // Build a tokenfactor for all the chains.
3911 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3914 /// getMemsetValue - Vectorized representation of the memset value
3916 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3918 assert(Value.getOpcode() != ISD::UNDEF);
3920 unsigned NumBits = VT.getScalarType().getSizeInBits();
3921 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3922 assert(C->getAPIntValue().getBitWidth() == 8);
3923 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3925 return DAG.getConstant(Val, dl, VT);
3926 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3930 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3931 EVT IntVT = VT.getScalarType();
3932 if (!IntVT.isInteger())
3933 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3935 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3937 // Use a multiplication with 0x010101... to extend the input to the
3939 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3940 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3941 DAG.getConstant(Magic, dl, IntVT));
3944 if (VT != Value.getValueType() && !VT.isInteger())
3945 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3946 if (VT != Value.getValueType()) {
3947 assert(VT.getVectorElementType() == Value.getValueType() &&
3948 "value type should be one vector element here");
3949 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3950 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3956 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3957 /// used when a memcpy is turned into a memset when the source is a constant
3959 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3960 const TargetLowering &TLI, StringRef Str) {
3961 // Handle vector with all elements zero.
3964 return DAG.getConstant(0, dl, VT);
3965 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3966 return DAG.getConstantFP(0.0, dl, VT);
3967 else if (VT.isVector()) {
3968 unsigned NumElts = VT.getVectorNumElements();
3969 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3970 return DAG.getNode(ISD::BITCAST, dl, VT,
3971 DAG.getConstant(0, dl,
3972 EVT::getVectorVT(*DAG.getContext(),
3975 llvm_unreachable("Expected type!");
3978 assert(!VT.isVector() && "Can't handle vector type here!");
3979 unsigned NumVTBits = VT.getSizeInBits();
3980 unsigned NumVTBytes = NumVTBits / 8;
3981 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3983 APInt Val(NumVTBits, 0);
3984 if (TLI.isLittleEndian()) {
3985 for (unsigned i = 0; i != NumBytes; ++i)
3986 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3988 for (unsigned i = 0; i != NumBytes; ++i)
3989 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3992 // If the "cost" of materializing the integer immediate is less than the cost
3993 // of a load, then it is cost effective to turn the load into the immediate.
3994 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3995 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3996 return DAG.getConstant(Val, dl, VT);
3997 return SDValue(nullptr, 0);
4000 /// getMemBasePlusOffset - Returns base and offset node for the
4002 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4003 SelectionDAG &DAG) {
4004 EVT VT = Base.getValueType();
4005 return DAG.getNode(ISD::ADD, dl,
4006 VT, Base, DAG.getConstant(Offset, dl, VT));
4009 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4011 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4012 unsigned SrcDelta = 0;
4013 GlobalAddressSDNode *G = nullptr;
4014 if (Src.getOpcode() == ISD::GlobalAddress)
4015 G = cast<GlobalAddressSDNode>(Src);
4016 else if (Src.getOpcode() == ISD::ADD &&
4017 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4018 Src.getOperand(1).getOpcode() == ISD::Constant) {
4019 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4020 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4025 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4028 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
4029 /// to replace the memset / memcpy. Return true if the number of memory ops
4030 /// is below the threshold. It returns the types of the sequence of
4031 /// memory ops to perform memset / memcpy by reference.
4032 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4033 unsigned Limit, uint64_t Size,
4034 unsigned DstAlign, unsigned SrcAlign,
4040 const TargetLowering &TLI) {
4041 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4042 "Expecting memcpy / memset source to meet alignment requirement!");
4043 // If 'SrcAlign' is zero, that means the memory operation does not need to
4044 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4045 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4046 // is the specified alignment of the memory operation. If it is zero, that
4047 // means it's possible to change the alignment of the destination.
4048 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4049 // not need to be loaded.
4050 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4051 IsMemset, ZeroMemset, MemcpyStrSrc,
4052 DAG.getMachineFunction());
4054 if (VT == MVT::Other) {
4056 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4057 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4058 VT = TLI.getPointerTy();
4060 switch (DstAlign & 7) {
4061 case 0: VT = MVT::i64; break;
4062 case 4: VT = MVT::i32; break;
4063 case 2: VT = MVT::i16; break;
4064 default: VT = MVT::i8; break;
4069 while (!TLI.isTypeLegal(LVT))
4070 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4071 assert(LVT.isInteger());
4077 unsigned NumMemOps = 0;
4079 unsigned VTSize = VT.getSizeInBits() / 8;
4080 while (VTSize > Size) {
4081 // For now, only use non-vector load / store's for the left-over pieces.
4086 if (VT.isVector() || VT.isFloatingPoint()) {
4087 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4088 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4089 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4091 else if (NewVT == MVT::i64 &&
4092 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4093 TLI.isSafeMemOpType(MVT::f64)) {
4094 // i64 is usually not legal on 32-bit targets, but f64 may be.
4102 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4103 if (NewVT == MVT::i8)
4105 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4107 NewVTSize = NewVT.getSizeInBits() / 8;
4109 // If the new VT cannot cover all of the remaining bits, then consider
4110 // issuing a (or a pair of) unaligned and overlapping load / store.
4111 // FIXME: Only does this for 64-bit or more since we don't have proper
4112 // cost model for unaligned load / store.
4115 if (NumMemOps && AllowOverlap &&
4116 VTSize >= 8 && NewVTSize < Size &&
4117 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4125 if (++NumMemOps > Limit)
4128 MemOps.push_back(VT);
4135 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4136 SDValue Chain, SDValue Dst,
4137 SDValue Src, uint64_t Size,
4138 unsigned Align, bool isVol,
4140 MachinePointerInfo DstPtrInfo,
4141 MachinePointerInfo SrcPtrInfo) {
4142 // Turn a memcpy of undef to nop.
4143 if (Src.getOpcode() == ISD::UNDEF)
4146 // Expand memcpy to a series of load and store ops if the size operand falls
4147 // below a certain threshold.
4148 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4149 // rather than maybe a humongous number of loads and stores.
4150 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4151 std::vector<EVT> MemOps;
4152 bool DstAlignCanChange = false;
4153 MachineFunction &MF = DAG.getMachineFunction();
4154 MachineFrameInfo *MFI = MF.getFrameInfo();
4155 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4156 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4157 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4158 DstAlignCanChange = true;
4159 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4160 if (Align > SrcAlign)
4163 bool CopyFromStr = isMemSrcFromString(Src, Str);
4164 bool isZeroStr = CopyFromStr && Str.empty();
4165 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4167 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4168 (DstAlignCanChange ? 0 : Align),
4169 (isZeroStr ? 0 : SrcAlign),
4170 false, false, CopyFromStr, true, DAG, TLI))
4173 if (DstAlignCanChange) {
4174 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4175 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4177 // Don't promote to an alignment that would require dynamic stack
4179 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4180 if (!TRI->needsStackRealignment(MF))
4181 while (NewAlign > Align &&
4182 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4185 if (NewAlign > Align) {
4186 // Give the stack frame object a larger alignment if needed.
4187 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4188 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4193 SmallVector<SDValue, 8> OutChains;
4194 unsigned NumMemOps = MemOps.size();
4195 uint64_t SrcOff = 0, DstOff = 0;
4196 for (unsigned i = 0; i != NumMemOps; ++i) {
4198 unsigned VTSize = VT.getSizeInBits() / 8;
4199 SDValue Value, Store;
4201 if (VTSize > Size) {
4202 // Issuing an unaligned load / store pair that overlaps with the previous
4203 // pair. Adjust the offset accordingly.
4204 assert(i == NumMemOps-1 && i != 0);
4205 SrcOff -= VTSize - Size;
4206 DstOff -= VTSize - Size;
4210 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4211 // It's unlikely a store of a vector immediate can be done in a single
4212 // instruction. It would require a load from a constantpool first.
4213 // We only handle zero vectors here.
4214 // FIXME: Handle other cases where store of vector immediate is done in
4215 // a single instruction.
4216 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4217 if (Value.getNode())
4218 Store = DAG.getStore(Chain, dl, Value,
4219 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4220 DstPtrInfo.getWithOffset(DstOff), isVol,
4224 if (!Store.getNode()) {
4225 // The type might not be legal for the target. This should only happen
4226 // if the type is smaller than a legal type, as on PPC, so the right
4227 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4228 // to Load/Store if NVT==VT.
4229 // FIXME does the case above also need this?
4230 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4231 assert(NVT.bitsGE(VT));
4232 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4233 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4234 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4235 false, MinAlign(SrcAlign, SrcOff));
4236 Store = DAG.getTruncStore(Chain, dl, Value,
4237 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4238 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4241 OutChains.push_back(Store);
4247 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4250 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4251 SDValue Chain, SDValue Dst,
4252 SDValue Src, uint64_t Size,
4253 unsigned Align, bool isVol,
4255 MachinePointerInfo DstPtrInfo,
4256 MachinePointerInfo SrcPtrInfo) {
4257 // Turn a memmove of undef to nop.
4258 if (Src.getOpcode() == ISD::UNDEF)
4261 // Expand memmove to a series of load and store ops if the size operand falls
4262 // below a certain threshold.
4263 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4264 std::vector<EVT> MemOps;
4265 bool DstAlignCanChange = false;
4266 MachineFunction &MF = DAG.getMachineFunction();
4267 MachineFrameInfo *MFI = MF.getFrameInfo();
4268 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4269 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4270 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4271 DstAlignCanChange = true;
4272 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4273 if (Align > SrcAlign)
4275 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4277 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4278 (DstAlignCanChange ? 0 : Align), SrcAlign,
4279 false, false, false, false, DAG, TLI))
4282 if (DstAlignCanChange) {
4283 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4284 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4285 if (NewAlign > Align) {
4286 // Give the stack frame object a larger alignment if needed.
4287 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4288 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4293 uint64_t SrcOff = 0, DstOff = 0;
4294 SmallVector<SDValue, 8> LoadValues;
4295 SmallVector<SDValue, 8> LoadChains;
4296 SmallVector<SDValue, 8> OutChains;
4297 unsigned NumMemOps = MemOps.size();
4298 for (unsigned i = 0; i < NumMemOps; i++) {
4300 unsigned VTSize = VT.getSizeInBits() / 8;
4303 Value = DAG.getLoad(VT, dl, Chain,
4304 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4305 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4306 false, false, SrcAlign);
4307 LoadValues.push_back(Value);
4308 LoadChains.push_back(Value.getValue(1));
4311 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4313 for (unsigned i = 0; i < NumMemOps; i++) {
4315 unsigned VTSize = VT.getSizeInBits() / 8;
4318 Store = DAG.getStore(Chain, dl, LoadValues[i],
4319 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4320 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4321 OutChains.push_back(Store);
4325 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4328 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4331 /// \param DAG Selection DAG where lowered code is placed.
4332 /// \param dl Link to corresponding IR location.
4333 /// \param Chain Control flow dependency.
4334 /// \param Dst Pointer to destination memory location.
4335 /// \param Src Value of byte to write into the memory.
4336 /// \param Size Number of bytes to write.
4337 /// \param Align Alignment of the destination in bytes.
4338 /// \param isVol True if destination is volatile.
4339 /// \param DstPtrInfo IR information on the memory pointer.
4340 /// \returns New head in the control flow, if lowering was successful, empty
4341 /// SDValue otherwise.
4343 /// The function tries to replace 'llvm.memset' intrinsic with several store
4344 /// operations and value calculation code. This is usually profitable for small
4346 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4347 SDValue Chain, SDValue Dst,
4348 SDValue Src, uint64_t Size,
4349 unsigned Align, bool isVol,
4350 MachinePointerInfo DstPtrInfo) {
4351 // Turn a memset of undef to nop.
4352 if (Src.getOpcode() == ISD::UNDEF)
4355 // Expand memset to a series of load/store ops if the size operand
4356 // falls below a certain threshold.
4357 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4358 std::vector<EVT> MemOps;
4359 bool DstAlignCanChange = false;
4360 MachineFunction &MF = DAG.getMachineFunction();
4361 MachineFrameInfo *MFI = MF.getFrameInfo();
4362 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4363 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4364 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4365 DstAlignCanChange = true;
4367 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4368 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4369 Size, (DstAlignCanChange ? 0 : Align), 0,
4370 true, IsZeroVal, false, true, DAG, TLI))
4373 if (DstAlignCanChange) {
4374 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4375 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4376 if (NewAlign > Align) {
4377 // Give the stack frame object a larger alignment if needed.
4378 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4379 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4384 SmallVector<SDValue, 8> OutChains;
4385 uint64_t DstOff = 0;
4386 unsigned NumMemOps = MemOps.size();
4388 // Find the largest store and generate the bit pattern for it.
4389 EVT LargestVT = MemOps[0];
4390 for (unsigned i = 1; i < NumMemOps; i++)
4391 if (MemOps[i].bitsGT(LargestVT))
4392 LargestVT = MemOps[i];
4393 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4395 for (unsigned i = 0; i < NumMemOps; i++) {
4397 unsigned VTSize = VT.getSizeInBits() / 8;
4398 if (VTSize > Size) {
4399 // Issuing an unaligned load / store pair that overlaps with the previous
4400 // pair. Adjust the offset accordingly.
4401 assert(i == NumMemOps-1 && i != 0);
4402 DstOff -= VTSize - Size;
4405 // If this store is smaller than the largest store see whether we can get
4406 // the smaller value for free with a truncate.
4407 SDValue Value = MemSetValue;
4408 if (VT.bitsLT(LargestVT)) {
4409 if (!LargestVT.isVector() && !VT.isVector() &&
4410 TLI.isTruncateFree(LargestVT, VT))
4411 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4413 Value = getMemsetValue(Src, VT, DAG, dl);
4415 assert(Value.getValueType() == VT && "Value with wrong type.");
4416 SDValue Store = DAG.getStore(Chain, dl, Value,
4417 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4418 DstPtrInfo.getWithOffset(DstOff),
4419 isVol, false, Align);
4420 OutChains.push_back(Store);
4421 DstOff += VT.getSizeInBits() / 8;
4425 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4428 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4429 SDValue Src, SDValue Size,
4430 unsigned Align, bool isVol, bool AlwaysInline,
4431 bool isTailCall, MachinePointerInfo DstPtrInfo,
4432 MachinePointerInfo SrcPtrInfo) {
4433 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4435 // Check to see if we should lower the memcpy to loads and stores first.
4436 // For cases within the target-specified limits, this is the best choice.
4437 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4439 // Memcpy with size zero? Just return the original chain.
4440 if (ConstantSize->isNullValue())
4443 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4444 ConstantSize->getZExtValue(),Align,
4445 isVol, false, DstPtrInfo, SrcPtrInfo);
4446 if (Result.getNode())
4450 // Then check to see if we should lower the memcpy with target-specific
4451 // code. If the target chooses to do this, this is the next best.
4453 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4454 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4455 DstPtrInfo, SrcPtrInfo);
4456 if (Result.getNode())
4460 // If we really need inline code and the target declined to provide it,
4461 // use a (potentially long) sequence of loads and stores.
4463 assert(ConstantSize && "AlwaysInline requires a constant size!");
4464 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4465 ConstantSize->getZExtValue(), Align, isVol,
4466 true, DstPtrInfo, SrcPtrInfo);
4469 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4470 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4471 // respect volatile, so they may do things like read or write memory
4472 // beyond the given memory regions. But fixing this isn't easy, and most
4473 // people don't care.
4475 // Emit a library call.
4476 TargetLowering::ArgListTy Args;
4477 TargetLowering::ArgListEntry Entry;
4478 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4479 Entry.Node = Dst; Args.push_back(Entry);
4480 Entry.Node = Src; Args.push_back(Entry);
4481 Entry.Node = Size; Args.push_back(Entry);
4482 // FIXME: pass in SDLoc
4483 TargetLowering::CallLoweringInfo CLI(*this);
4484 CLI.setDebugLoc(dl).setChain(Chain)
4485 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4486 Type::getVoidTy(*getContext()),
4487 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4488 TLI->getPointerTy()), std::move(Args), 0)
4490 .setTailCall(isTailCall);
4492 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4493 return CallResult.second;
4496 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4497 SDValue Src, SDValue Size,
4498 unsigned Align, bool isVol, bool isTailCall,
4499 MachinePointerInfo DstPtrInfo,
4500 MachinePointerInfo SrcPtrInfo) {
4501 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4503 // Check to see if we should lower the memmove to loads and stores first.
4504 // For cases within the target-specified limits, this is the best choice.
4505 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4507 // Memmove with size zero? Just return the original chain.
4508 if (ConstantSize->isNullValue())
4512 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4513 ConstantSize->getZExtValue(), Align, isVol,
4514 false, DstPtrInfo, SrcPtrInfo);
4515 if (Result.getNode())
4519 // Then check to see if we should lower the memmove with target-specific
4520 // code. If the target chooses to do this, this is the next best.
4522 SDValue Result = TSI->EmitTargetCodeForMemmove(
4523 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4524 if (Result.getNode())
4528 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4529 // not be safe. See memcpy above for more details.
4531 // Emit a library call.
4532 TargetLowering::ArgListTy Args;
4533 TargetLowering::ArgListEntry Entry;
4534 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4535 Entry.Node = Dst; Args.push_back(Entry);
4536 Entry.Node = Src; Args.push_back(Entry);
4537 Entry.Node = Size; Args.push_back(Entry);
4538 // FIXME: pass in SDLoc
4539 TargetLowering::CallLoweringInfo CLI(*this);
4540 CLI.setDebugLoc(dl).setChain(Chain)
4541 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4542 Type::getVoidTy(*getContext()),
4543 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4544 TLI->getPointerTy()), std::move(Args), 0)
4546 .setTailCall(isTailCall);
4548 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4549 return CallResult.second;
4552 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4553 SDValue Src, SDValue Size,
4554 unsigned Align, bool isVol, bool isTailCall,
4555 MachinePointerInfo DstPtrInfo) {
4556 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4558 // Check to see if we should lower the memset to stores first.
4559 // For cases within the target-specified limits, this is the best choice.
4560 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4562 // Memset with size zero? Just return the original chain.
4563 if (ConstantSize->isNullValue())
4567 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4568 Align, isVol, DstPtrInfo);
4570 if (Result.getNode())
4574 // Then check to see if we should lower the memset with target-specific
4575 // code. If the target chooses to do this, this is the next best.
4577 SDValue Result = TSI->EmitTargetCodeForMemset(
4578 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4579 if (Result.getNode())
4583 // Emit a library call.
4584 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4585 TargetLowering::ArgListTy Args;
4586 TargetLowering::ArgListEntry Entry;
4587 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4588 Args.push_back(Entry);
4590 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4591 Args.push_back(Entry);
4593 Entry.Ty = IntPtrTy;
4594 Args.push_back(Entry);
4596 // FIXME: pass in SDLoc
4597 TargetLowering::CallLoweringInfo CLI(*this);
4598 CLI.setDebugLoc(dl).setChain(Chain)
4599 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4600 Type::getVoidTy(*getContext()),
4601 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4602 TLI->getPointerTy()), std::move(Args), 0)
4604 .setTailCall(isTailCall);
4606 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4607 return CallResult.second;
4610 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4611 SDVTList VTList, ArrayRef<SDValue> Ops,
4612 MachineMemOperand *MMO,
4613 AtomicOrdering SuccessOrdering,
4614 AtomicOrdering FailureOrdering,
4615 SynchronizationScope SynchScope) {
4616 FoldingSetNodeID ID;
4617 ID.AddInteger(MemVT.getRawBits());
4618 AddNodeIDNode(ID, Opcode, VTList, Ops);
4619 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4621 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4622 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4623 return SDValue(E, 0);
4626 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4627 // SDNode doesn't have access to it. This memory will be "leaked" when
4628 // the node is deallocated, but recovered when the allocator is released.
4629 // If the number of operands is less than 5 we use AtomicSDNode's internal
4631 unsigned NumOps = Ops.size();
4632 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4635 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4636 dl.getDebugLoc(), VTList, MemVT,
4637 Ops.data(), DynOps, NumOps, MMO,
4638 SuccessOrdering, FailureOrdering,
4640 CSEMap.InsertNode(N, IP);
4642 return SDValue(N, 0);
4645 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4646 SDVTList VTList, ArrayRef<SDValue> Ops,
4647 MachineMemOperand *MMO,
4648 AtomicOrdering Ordering,
4649 SynchronizationScope SynchScope) {
4650 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4651 Ordering, SynchScope);
4654 SDValue SelectionDAG::getAtomicCmpSwap(
4655 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4656 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4657 unsigned Alignment, AtomicOrdering SuccessOrdering,
4658 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4659 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4660 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4661 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4663 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4664 Alignment = getEVTAlignment(MemVT);
4666 MachineFunction &MF = getMachineFunction();
4668 // FIXME: Volatile isn't really correct; we should keep track of atomic
4669 // orderings in the memoperand.
4670 unsigned Flags = MachineMemOperand::MOVolatile;
4671 Flags |= MachineMemOperand::MOLoad;
4672 Flags |= MachineMemOperand::MOStore;
4674 MachineMemOperand *MMO =
4675 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4677 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4678 SuccessOrdering, FailureOrdering, SynchScope);
4681 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4682 SDVTList VTs, SDValue Chain, SDValue Ptr,
4683 SDValue Cmp, SDValue Swp,
4684 MachineMemOperand *MMO,
4685 AtomicOrdering SuccessOrdering,
4686 AtomicOrdering FailureOrdering,
4687 SynchronizationScope SynchScope) {
4688 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4689 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4690 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4692 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4693 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4694 SuccessOrdering, FailureOrdering, SynchScope);
4697 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4699 SDValue Ptr, SDValue Val,
4700 const Value* PtrVal,
4702 AtomicOrdering Ordering,
4703 SynchronizationScope SynchScope) {
4704 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4705 Alignment = getEVTAlignment(MemVT);
4707 MachineFunction &MF = getMachineFunction();
4708 // An atomic store does not load. An atomic load does not store.
4709 // (An atomicrmw obviously both loads and stores.)
4710 // For now, atomics are considered to be volatile always, and they are
4712 // FIXME: Volatile isn't really correct; we should keep track of atomic
4713 // orderings in the memoperand.
4714 unsigned Flags = MachineMemOperand::MOVolatile;
4715 if (Opcode != ISD::ATOMIC_STORE)
4716 Flags |= MachineMemOperand::MOLoad;
4717 if (Opcode != ISD::ATOMIC_LOAD)
4718 Flags |= MachineMemOperand::MOStore;
4720 MachineMemOperand *MMO =
4721 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4722 MemVT.getStoreSize(), Alignment);
4724 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4725 Ordering, SynchScope);
4728 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4730 SDValue Ptr, SDValue Val,
4731 MachineMemOperand *MMO,
4732 AtomicOrdering Ordering,
4733 SynchronizationScope SynchScope) {
4734 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4735 Opcode == ISD::ATOMIC_LOAD_SUB ||
4736 Opcode == ISD::ATOMIC_LOAD_AND ||
4737 Opcode == ISD::ATOMIC_LOAD_OR ||
4738 Opcode == ISD::ATOMIC_LOAD_XOR ||
4739 Opcode == ISD::ATOMIC_LOAD_NAND ||
4740 Opcode == ISD::ATOMIC_LOAD_MIN ||
4741 Opcode == ISD::ATOMIC_LOAD_MAX ||
4742 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4743 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4744 Opcode == ISD::ATOMIC_SWAP ||
4745 Opcode == ISD::ATOMIC_STORE) &&
4746 "Invalid Atomic Op");
4748 EVT VT = Val.getValueType();
4750 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4751 getVTList(VT, MVT::Other);
4752 SDValue Ops[] = {Chain, Ptr, Val};
4753 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4756 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4757 EVT VT, SDValue Chain,
4759 MachineMemOperand *MMO,
4760 AtomicOrdering Ordering,
4761 SynchronizationScope SynchScope) {
4762 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4764 SDVTList VTs = getVTList(VT, MVT::Other);
4765 SDValue Ops[] = {Chain, Ptr};
4766 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4769 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4770 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4771 if (Ops.size() == 1)
4774 SmallVector<EVT, 4> VTs;
4775 VTs.reserve(Ops.size());
4776 for (unsigned i = 0; i < Ops.size(); ++i)
4777 VTs.push_back(Ops[i].getValueType());
4778 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4782 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4783 ArrayRef<SDValue> Ops,
4784 EVT MemVT, MachinePointerInfo PtrInfo,
4785 unsigned Align, bool Vol,
4786 bool ReadMem, bool WriteMem, unsigned Size) {
4787 if (Align == 0) // Ensure that codegen never sees alignment 0
4788 Align = getEVTAlignment(MemVT);
4790 MachineFunction &MF = getMachineFunction();
4793 Flags |= MachineMemOperand::MOStore;
4795 Flags |= MachineMemOperand::MOLoad;
4797 Flags |= MachineMemOperand::MOVolatile;
4799 Size = MemVT.getStoreSize();
4800 MachineMemOperand *MMO =
4801 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4803 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4807 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4808 ArrayRef<SDValue> Ops, EVT MemVT,
4809 MachineMemOperand *MMO) {
4810 assert((Opcode == ISD::INTRINSIC_VOID ||
4811 Opcode == ISD::INTRINSIC_W_CHAIN ||
4812 Opcode == ISD::PREFETCH ||
4813 Opcode == ISD::LIFETIME_START ||
4814 Opcode == ISD::LIFETIME_END ||
4815 (Opcode <= INT_MAX &&
4816 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4817 "Opcode is not a memory-accessing opcode!");
4819 // Memoize the node unless it returns a flag.
4820 MemIntrinsicSDNode *N;
4821 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4822 FoldingSetNodeID ID;
4823 AddNodeIDNode(ID, Opcode, VTList, Ops);
4824 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4826 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4827 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4828 return SDValue(E, 0);
4831 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4832 dl.getDebugLoc(), VTList, Ops,
4834 CSEMap.InsertNode(N, IP);
4836 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4837 dl.getDebugLoc(), VTList, Ops,
4841 return SDValue(N, 0);
4844 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4845 /// MachinePointerInfo record from it. This is particularly useful because the
4846 /// code generator has many cases where it doesn't bother passing in a
4847 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4848 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4849 // If this is FI+Offset, we can model it.
4850 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4851 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4853 // If this is (FI+Offset1)+Offset2, we can model it.
4854 if (Ptr.getOpcode() != ISD::ADD ||
4855 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4856 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4857 return MachinePointerInfo();
4859 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4860 return MachinePointerInfo::getFixedStack(FI, Offset+
4861 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4864 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4865 /// MachinePointerInfo record from it. This is particularly useful because the
4866 /// code generator has many cases where it doesn't bother passing in a
4867 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4868 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4869 // If the 'Offset' value isn't a constant, we can't handle this.
4870 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4871 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4872 if (OffsetOp.getOpcode() == ISD::UNDEF)
4873 return InferPointerInfo(Ptr);
4874 return MachinePointerInfo();
4879 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4880 EVT VT, SDLoc dl, SDValue Chain,
4881 SDValue Ptr, SDValue Offset,
4882 MachinePointerInfo PtrInfo, EVT MemVT,
4883 bool isVolatile, bool isNonTemporal, bool isInvariant,
4884 unsigned Alignment, const AAMDNodes &AAInfo,
4885 const MDNode *Ranges) {
4886 assert(Chain.getValueType() == MVT::Other &&
4887 "Invalid chain type");
4888 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4889 Alignment = getEVTAlignment(VT);
4891 unsigned Flags = MachineMemOperand::MOLoad;
4893 Flags |= MachineMemOperand::MOVolatile;
4895 Flags |= MachineMemOperand::MONonTemporal;
4897 Flags |= MachineMemOperand::MOInvariant;
4899 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4901 if (PtrInfo.V.isNull())
4902 PtrInfo = InferPointerInfo(Ptr, Offset);
4904 MachineFunction &MF = getMachineFunction();
4905 MachineMemOperand *MMO =
4906 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4908 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4912 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4913 EVT VT, SDLoc dl, SDValue Chain,
4914 SDValue Ptr, SDValue Offset, EVT MemVT,
4915 MachineMemOperand *MMO) {
4917 ExtType = ISD::NON_EXTLOAD;
4918 } else if (ExtType == ISD::NON_EXTLOAD) {
4919 assert(VT == MemVT && "Non-extending load from different memory type!");
4922 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4923 "Should only be an extending load, not truncating!");
4924 assert(VT.isInteger() == MemVT.isInteger() &&
4925 "Cannot convert from FP to Int or Int -> FP!");
4926 assert(VT.isVector() == MemVT.isVector() &&
4927 "Cannot use an ext load to convert to or from a vector!");
4928 assert((!VT.isVector() ||
4929 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4930 "Cannot use an ext load to change the number of vector elements!");
4933 bool Indexed = AM != ISD::UNINDEXED;
4934 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4935 "Unindexed load with an offset!");
4937 SDVTList VTs = Indexed ?
4938 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4939 SDValue Ops[] = { Chain, Ptr, Offset };
4940 FoldingSetNodeID ID;
4941 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4942 ID.AddInteger(MemVT.getRawBits());
4943 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4944 MMO->isNonTemporal(),
4945 MMO->isInvariant()));
4946 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4948 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4949 cast<LoadSDNode>(E)->refineAlignment(MMO);
4950 return SDValue(E, 0);
4952 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4953 dl.getDebugLoc(), VTs, AM, ExtType,
4955 CSEMap.InsertNode(N, IP);
4957 return SDValue(N, 0);
4960 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4961 SDValue Chain, SDValue Ptr,
4962 MachinePointerInfo PtrInfo,
4963 bool isVolatile, bool isNonTemporal,
4964 bool isInvariant, unsigned Alignment,
4965 const AAMDNodes &AAInfo,
4966 const MDNode *Ranges) {
4967 SDValue Undef = getUNDEF(Ptr.getValueType());
4968 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4969 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4973 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4974 SDValue Chain, SDValue Ptr,
4975 MachineMemOperand *MMO) {
4976 SDValue Undef = getUNDEF(Ptr.getValueType());
4977 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4981 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4982 SDValue Chain, SDValue Ptr,
4983 MachinePointerInfo PtrInfo, EVT MemVT,
4984 bool isVolatile, bool isNonTemporal,
4985 bool isInvariant, unsigned Alignment,
4986 const AAMDNodes &AAInfo) {
4987 SDValue Undef = getUNDEF(Ptr.getValueType());
4988 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4989 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
4994 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4995 SDValue Chain, SDValue Ptr, EVT MemVT,
4996 MachineMemOperand *MMO) {
4997 SDValue Undef = getUNDEF(Ptr.getValueType());
4998 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5003 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5004 SDValue Offset, ISD::MemIndexedMode AM) {
5005 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5006 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5007 "Load is already a indexed load!");
5008 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5009 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5010 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5011 false, LD->getAlignment());
5014 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5015 SDValue Ptr, MachinePointerInfo PtrInfo,
5016 bool isVolatile, bool isNonTemporal,
5017 unsigned Alignment, const AAMDNodes &AAInfo) {
5018 assert(Chain.getValueType() == MVT::Other &&
5019 "Invalid chain type");
5020 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5021 Alignment = getEVTAlignment(Val.getValueType());
5023 unsigned Flags = MachineMemOperand::MOStore;
5025 Flags |= MachineMemOperand::MOVolatile;
5027 Flags |= MachineMemOperand::MONonTemporal;
5029 if (PtrInfo.V.isNull())
5030 PtrInfo = InferPointerInfo(Ptr);
5032 MachineFunction &MF = getMachineFunction();
5033 MachineMemOperand *MMO =
5034 MF.getMachineMemOperand(PtrInfo, Flags,
5035 Val.getValueType().getStoreSize(), Alignment,
5038 return getStore(Chain, dl, Val, Ptr, MMO);
5041 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5042 SDValue Ptr, MachineMemOperand *MMO) {
5043 assert(Chain.getValueType() == MVT::Other &&
5044 "Invalid chain type");
5045 EVT VT = Val.getValueType();
5046 SDVTList VTs = getVTList(MVT::Other);
5047 SDValue Undef = getUNDEF(Ptr.getValueType());
5048 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5049 FoldingSetNodeID ID;
5050 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5051 ID.AddInteger(VT.getRawBits());
5052 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5053 MMO->isNonTemporal(), MMO->isInvariant()));
5054 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5056 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5057 cast<StoreSDNode>(E)->refineAlignment(MMO);
5058 return SDValue(E, 0);
5060 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5061 dl.getDebugLoc(), VTs,
5062 ISD::UNINDEXED, false, VT, MMO);
5063 CSEMap.InsertNode(N, IP);
5065 return SDValue(N, 0);
5068 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5069 SDValue Ptr, MachinePointerInfo PtrInfo,
5070 EVT SVT,bool isVolatile, bool isNonTemporal,
5072 const AAMDNodes &AAInfo) {
5073 assert(Chain.getValueType() == MVT::Other &&
5074 "Invalid chain type");
5075 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5076 Alignment = getEVTAlignment(SVT);
5078 unsigned Flags = MachineMemOperand::MOStore;
5080 Flags |= MachineMemOperand::MOVolatile;
5082 Flags |= MachineMemOperand::MONonTemporal;
5084 if (PtrInfo.V.isNull())
5085 PtrInfo = InferPointerInfo(Ptr);
5087 MachineFunction &MF = getMachineFunction();
5088 MachineMemOperand *MMO =
5089 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5092 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5095 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5096 SDValue Ptr, EVT SVT,
5097 MachineMemOperand *MMO) {
5098 EVT VT = Val.getValueType();
5100 assert(Chain.getValueType() == MVT::Other &&
5101 "Invalid chain type");
5103 return getStore(Chain, dl, Val, Ptr, MMO);
5105 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5106 "Should only be a truncating store, not extending!");
5107 assert(VT.isInteger() == SVT.isInteger() &&
5108 "Can't do FP-INT conversion!");
5109 assert(VT.isVector() == SVT.isVector() &&
5110 "Cannot use trunc store to convert to or from a vector!");
5111 assert((!VT.isVector() ||
5112 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5113 "Cannot use trunc store to change the number of vector elements!");
5115 SDVTList VTs = getVTList(MVT::Other);
5116 SDValue Undef = getUNDEF(Ptr.getValueType());
5117 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5118 FoldingSetNodeID ID;
5119 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5120 ID.AddInteger(SVT.getRawBits());
5121 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5122 MMO->isNonTemporal(), MMO->isInvariant()));
5123 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5125 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5126 cast<StoreSDNode>(E)->refineAlignment(MMO);
5127 return SDValue(E, 0);
5129 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5130 dl.getDebugLoc(), VTs,
5131 ISD::UNINDEXED, true, SVT, MMO);
5132 CSEMap.InsertNode(N, IP);
5134 return SDValue(N, 0);
5138 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5139 SDValue Offset, ISD::MemIndexedMode AM) {
5140 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5141 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5142 "Store is already a indexed store!");
5143 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5144 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5145 FoldingSetNodeID ID;
5146 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5147 ID.AddInteger(ST->getMemoryVT().getRawBits());
5148 ID.AddInteger(ST->getRawSubclassData());
5149 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5151 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5152 return SDValue(E, 0);
5154 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5155 dl.getDebugLoc(), VTs, AM,
5156 ST->isTruncatingStore(),
5158 ST->getMemOperand());
5159 CSEMap.InsertNode(N, IP);
5161 return SDValue(N, 0);
5165 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5166 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5167 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5169 SDVTList VTs = getVTList(VT, MVT::Other);
5170 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5171 FoldingSetNodeID ID;
5172 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5173 ID.AddInteger(VT.getRawBits());
5174 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5176 MMO->isNonTemporal(),
5177 MMO->isInvariant()));
5178 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5180 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5181 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5182 return SDValue(E, 0);
5184 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5185 dl.getDebugLoc(), Ops, 4, VTs,
5187 CSEMap.InsertNode(N, IP);
5189 return SDValue(N, 0);
5192 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5193 SDValue Ptr, SDValue Mask, EVT MemVT,
5194 MachineMemOperand *MMO, bool isTrunc) {
5195 assert(Chain.getValueType() == MVT::Other &&
5196 "Invalid chain type");
5197 EVT VT = Val.getValueType();
5198 SDVTList VTs = getVTList(MVT::Other);
5199 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5200 FoldingSetNodeID ID;
5201 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5202 ID.AddInteger(VT.getRawBits());
5203 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5204 MMO->isNonTemporal(), MMO->isInvariant()));
5205 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5207 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5208 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5209 return SDValue(E, 0);
5211 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5212 dl.getDebugLoc(), Ops, 4,
5213 VTs, isTrunc, MemVT, MMO);
5214 CSEMap.InsertNode(N, IP);
5216 return SDValue(N, 0);
5220 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5221 ArrayRef<SDValue> Ops,
5222 MachineMemOperand *MMO) {
5224 FoldingSetNodeID ID;
5225 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5226 ID.AddInteger(VT.getRawBits());
5227 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5229 MMO->isNonTemporal(),
5230 MMO->isInvariant()));
5231 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5233 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5234 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5235 return SDValue(E, 0);
5237 MaskedGatherSDNode *N =
5238 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5240 CSEMap.InsertNode(N, IP);
5242 return SDValue(N, 0);
5245 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5246 ArrayRef<SDValue> Ops,
5247 MachineMemOperand *MMO) {
5248 FoldingSetNodeID ID;
5249 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5250 ID.AddInteger(VT.getRawBits());
5251 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5252 MMO->isNonTemporal(),
5253 MMO->isInvariant()));
5254 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5256 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5257 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5258 return SDValue(E, 0);
5261 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5263 CSEMap.InsertNode(N, IP);
5265 return SDValue(N, 0);
5268 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5269 SDValue Chain, SDValue Ptr,
5272 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5273 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5276 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5277 ArrayRef<SDUse> Ops) {
5278 switch (Ops.size()) {
5279 case 0: return getNode(Opcode, DL, VT);
5280 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5281 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5282 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5286 // Copy from an SDUse array into an SDValue array for use with
5287 // the regular getNode logic.
5288 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5289 return getNode(Opcode, DL, VT, NewOps);
5292 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5293 ArrayRef<SDValue> Ops) {
5294 unsigned NumOps = Ops.size();
5296 case 0: return getNode(Opcode, DL, VT);
5297 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5298 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5299 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5305 case ISD::SELECT_CC: {
5306 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5307 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5308 "LHS and RHS of condition must have same type!");
5309 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5310 "True and False arms of SelectCC must have same type!");
5311 assert(Ops[2].getValueType() == VT &&
5312 "select_cc node must be of same type as true and false value!");
5316 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5317 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5318 "LHS/RHS of comparison should match types!");
5325 SDVTList VTs = getVTList(VT);
5327 if (VT != MVT::Glue) {
5328 FoldingSetNodeID ID;
5329 AddNodeIDNode(ID, Opcode, VTs, Ops);
5332 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5333 return SDValue(E, 0);
5335 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5337 CSEMap.InsertNode(N, IP);
5339 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5344 return SDValue(N, 0);
5347 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5348 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5349 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5352 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5353 ArrayRef<SDValue> Ops) {
5354 if (VTList.NumVTs == 1)
5355 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5359 // FIXME: figure out how to safely handle things like
5360 // int foo(int x) { return 1 << (x & 255); }
5361 // int bar() { return foo(256); }
5362 case ISD::SRA_PARTS:
5363 case ISD::SRL_PARTS:
5364 case ISD::SHL_PARTS:
5365 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5366 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5367 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5368 else if (N3.getOpcode() == ISD::AND)
5369 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5370 // If the and is only masking out bits that cannot effect the shift,
5371 // eliminate the and.
5372 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5373 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5374 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5380 // Memoize the node unless it returns a flag.
5382 unsigned NumOps = Ops.size();
5383 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5384 FoldingSetNodeID ID;
5385 AddNodeIDNode(ID, Opcode, VTList, Ops);
5387 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5388 return SDValue(E, 0);
5391 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5392 DL.getDebugLoc(), VTList, Ops[0]);
5393 } else if (NumOps == 2) {
5394 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5395 DL.getDebugLoc(), VTList, Ops[0],
5397 } else if (NumOps == 3) {
5398 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5399 DL.getDebugLoc(), VTList, Ops[0],
5402 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5405 CSEMap.InsertNode(N, IP);
5408 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5409 DL.getDebugLoc(), VTList, Ops[0]);
5410 } else if (NumOps == 2) {
5411 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5412 DL.getDebugLoc(), VTList, Ops[0],
5414 } else if (NumOps == 3) {
5415 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5416 DL.getDebugLoc(), VTList, Ops[0],
5419 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5424 return SDValue(N, 0);
5427 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5428 return getNode(Opcode, DL, VTList, None);
5431 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5433 SDValue Ops[] = { N1 };
5434 return getNode(Opcode, DL, VTList, Ops);
5437 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5438 SDValue N1, SDValue N2) {
5439 SDValue Ops[] = { N1, N2 };
5440 return getNode(Opcode, DL, VTList, Ops);
5443 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5444 SDValue N1, SDValue N2, SDValue N3) {
5445 SDValue Ops[] = { N1, N2, N3 };
5446 return getNode(Opcode, DL, VTList, Ops);
5449 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5450 SDValue N1, SDValue N2, SDValue N3,
5452 SDValue Ops[] = { N1, N2, N3, N4 };
5453 return getNode(Opcode, DL, VTList, Ops);
5456 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5457 SDValue N1, SDValue N2, SDValue N3,
5458 SDValue N4, SDValue N5) {
5459 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5460 return getNode(Opcode, DL, VTList, Ops);
5463 SDVTList SelectionDAG::getVTList(EVT VT) {
5464 return makeVTList(SDNode::getValueTypeList(VT), 1);
5467 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5468 FoldingSetNodeID ID;
5470 ID.AddInteger(VT1.getRawBits());
5471 ID.AddInteger(VT2.getRawBits());
5474 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5476 EVT *Array = Allocator.Allocate<EVT>(2);
5479 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5480 VTListMap.InsertNode(Result, IP);
5482 return Result->getSDVTList();
5485 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5486 FoldingSetNodeID ID;
5488 ID.AddInteger(VT1.getRawBits());
5489 ID.AddInteger(VT2.getRawBits());
5490 ID.AddInteger(VT3.getRawBits());
5493 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5495 EVT *Array = Allocator.Allocate<EVT>(3);
5499 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5500 VTListMap.InsertNode(Result, IP);
5502 return Result->getSDVTList();
5505 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5506 FoldingSetNodeID ID;
5508 ID.AddInteger(VT1.getRawBits());
5509 ID.AddInteger(VT2.getRawBits());
5510 ID.AddInteger(VT3.getRawBits());
5511 ID.AddInteger(VT4.getRawBits());
5514 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5516 EVT *Array = Allocator.Allocate<EVT>(4);
5521 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5522 VTListMap.InsertNode(Result, IP);
5524 return Result->getSDVTList();
5527 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5528 unsigned NumVTs = VTs.size();
5529 FoldingSetNodeID ID;
5530 ID.AddInteger(NumVTs);
5531 for (unsigned index = 0; index < NumVTs; index++) {
5532 ID.AddInteger(VTs[index].getRawBits());
5536 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5538 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5539 std::copy(VTs.begin(), VTs.end(), Array);
5540 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5541 VTListMap.InsertNode(Result, IP);
5543 return Result->getSDVTList();
5547 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5548 /// specified operands. If the resultant node already exists in the DAG,
5549 /// this does not modify the specified node, instead it returns the node that
5550 /// already exists. If the resultant node does not exist in the DAG, the
5551 /// input node is returned. As a degenerate case, if you specify the same
5552 /// input operands as the node already has, the input node is returned.
5553 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5554 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5556 // Check to see if there is no change.
5557 if (Op == N->getOperand(0)) return N;
5559 // See if the modified node already exists.
5560 void *InsertPos = nullptr;
5561 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5564 // Nope it doesn't. Remove the node from its current place in the maps.
5566 if (!RemoveNodeFromCSEMaps(N))
5567 InsertPos = nullptr;
5569 // Now we update the operands.
5570 N->OperandList[0].set(Op);
5572 // If this gets put into a CSE map, add it.
5573 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5577 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5578 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5580 // Check to see if there is no change.
5581 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5582 return N; // No operands changed, just return the input node.
5584 // See if the modified node already exists.
5585 void *InsertPos = nullptr;
5586 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5589 // Nope it doesn't. Remove the node from its current place in the maps.
5591 if (!RemoveNodeFromCSEMaps(N))
5592 InsertPos = nullptr;
5594 // Now we update the operands.
5595 if (N->OperandList[0] != Op1)
5596 N->OperandList[0].set(Op1);
5597 if (N->OperandList[1] != Op2)
5598 N->OperandList[1].set(Op2);
5600 // If this gets put into a CSE map, add it.
5601 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5605 SDNode *SelectionDAG::
5606 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5607 SDValue Ops[] = { Op1, Op2, Op3 };
5608 return UpdateNodeOperands(N, Ops);
5611 SDNode *SelectionDAG::
5612 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5613 SDValue Op3, SDValue Op4) {
5614 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5615 return UpdateNodeOperands(N, Ops);
5618 SDNode *SelectionDAG::
5619 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5620 SDValue Op3, SDValue Op4, SDValue Op5) {
5621 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5622 return UpdateNodeOperands(N, Ops);
5625 SDNode *SelectionDAG::
5626 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5627 unsigned NumOps = Ops.size();
5628 assert(N->getNumOperands() == NumOps &&
5629 "Update with wrong number of operands");
5631 // If no operands changed just return the input node.
5632 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5635 // See if the modified node already exists.
5636 void *InsertPos = nullptr;
5637 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5640 // Nope it doesn't. Remove the node from its current place in the maps.
5642 if (!RemoveNodeFromCSEMaps(N))
5643 InsertPos = nullptr;
5645 // Now we update the operands.
5646 for (unsigned i = 0; i != NumOps; ++i)
5647 if (N->OperandList[i] != Ops[i])
5648 N->OperandList[i].set(Ops[i]);
5650 // If this gets put into a CSE map, add it.
5651 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5655 /// DropOperands - Release the operands and set this node to have
5657 void SDNode::DropOperands() {
5658 // Unlike the code in MorphNodeTo that does this, we don't need to
5659 // watch for dead nodes here.
5660 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5666 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5669 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5671 SDVTList VTs = getVTList(VT);
5672 return SelectNodeTo(N, MachineOpc, VTs, None);
5675 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5676 EVT VT, SDValue Op1) {
5677 SDVTList VTs = getVTList(VT);
5678 SDValue Ops[] = { Op1 };
5679 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5682 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5683 EVT VT, SDValue Op1,
5685 SDVTList VTs = getVTList(VT);
5686 SDValue Ops[] = { Op1, Op2 };
5687 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5690 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5691 EVT VT, SDValue Op1,
5692 SDValue Op2, SDValue Op3) {
5693 SDVTList VTs = getVTList(VT);
5694 SDValue Ops[] = { Op1, Op2, Op3 };
5695 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5698 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5699 EVT VT, ArrayRef<SDValue> Ops) {
5700 SDVTList VTs = getVTList(VT);
5701 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5704 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5705 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5706 SDVTList VTs = getVTList(VT1, VT2);
5707 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5710 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5712 SDVTList VTs = getVTList(VT1, VT2);
5713 return SelectNodeTo(N, MachineOpc, VTs, None);
5716 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5717 EVT VT1, EVT VT2, EVT VT3,
5718 ArrayRef<SDValue> Ops) {
5719 SDVTList VTs = getVTList(VT1, VT2, VT3);
5720 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5723 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5724 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5725 ArrayRef<SDValue> Ops) {
5726 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5727 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5730 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5733 SDVTList VTs = getVTList(VT1, VT2);
5734 SDValue Ops[] = { Op1 };
5735 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5738 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5740 SDValue Op1, SDValue Op2) {
5741 SDVTList VTs = getVTList(VT1, VT2);
5742 SDValue Ops[] = { Op1, Op2 };
5743 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5746 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5748 SDValue Op1, SDValue Op2,
5750 SDVTList VTs = getVTList(VT1, VT2);
5751 SDValue Ops[] = { Op1, Op2, Op3 };
5752 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5755 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5756 EVT VT1, EVT VT2, EVT VT3,
5757 SDValue Op1, SDValue Op2,
5759 SDVTList VTs = getVTList(VT1, VT2, VT3);
5760 SDValue Ops[] = { Op1, Op2, Op3 };
5761 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5764 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5765 SDVTList VTs,ArrayRef<SDValue> Ops) {
5766 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5767 // Reset the NodeID to -1.
5772 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5773 /// the line number information on the merged node since it is not possible to
5774 /// preserve the information that operation is associated with multiple lines.
5775 /// This will make the debugger working better at -O0, were there is a higher
5776 /// probability having other instructions associated with that line.
5778 /// For IROrder, we keep the smaller of the two
5779 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5780 DebugLoc NLoc = N->getDebugLoc();
5781 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5782 N->setDebugLoc(DebugLoc());
5784 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5785 N->setIROrder(Order);
5789 /// MorphNodeTo - This *mutates* the specified node to have the specified
5790 /// return type, opcode, and operands.
5792 /// Note that MorphNodeTo returns the resultant node. If there is already a
5793 /// node of the specified opcode and operands, it returns that node instead of
5794 /// the current one. Note that the SDLoc need not be the same.
5796 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5797 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5798 /// node, and because it doesn't require CSE recalculation for any of
5799 /// the node's users.
5801 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5802 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5803 /// the legalizer which maintain worklists that would need to be updated when
5804 /// deleting things.
5805 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5806 SDVTList VTs, ArrayRef<SDValue> Ops) {
5807 unsigned NumOps = Ops.size();
5808 // If an identical node already exists, use it.
5810 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5811 FoldingSetNodeID ID;
5812 AddNodeIDNode(ID, Opc, VTs, Ops);
5813 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5814 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5817 if (!RemoveNodeFromCSEMaps(N))
5820 // Start the morphing.
5822 N->ValueList = VTs.VTs;
5823 N->NumValues = VTs.NumVTs;
5825 // Clear the operands list, updating used nodes to remove this from their
5826 // use list. Keep track of any operands that become dead as a result.
5827 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5828 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5830 SDNode *Used = Use.getNode();
5832 if (Used->use_empty())
5833 DeadNodeSet.insert(Used);
5836 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5837 // Initialize the memory references information.
5838 MN->setMemRefs(nullptr, nullptr);
5839 // If NumOps is larger than the # of operands we can have in a
5840 // MachineSDNode, reallocate the operand list.
5841 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5842 if (MN->OperandsNeedDelete)
5843 delete[] MN->OperandList;
5844 if (NumOps > array_lengthof(MN->LocalOperands))
5845 // We're creating a final node that will live unmorphed for the
5846 // remainder of the current SelectionDAG iteration, so we can allocate
5847 // the operands directly out of a pool with no recycling metadata.
5848 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5849 Ops.data(), NumOps);
5851 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5852 MN->OperandsNeedDelete = false;
5854 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5856 // If NumOps is larger than the # of operands we currently have, reallocate
5857 // the operand list.
5858 if (NumOps > N->NumOperands) {
5859 if (N->OperandsNeedDelete)
5860 delete[] N->OperandList;
5861 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5862 N->OperandsNeedDelete = true;
5864 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5867 // Delete any nodes that are still dead after adding the uses for the
5869 if (!DeadNodeSet.empty()) {
5870 SmallVector<SDNode *, 16> DeadNodes;
5871 for (SDNode *N : DeadNodeSet)
5873 DeadNodes.push_back(N);
5874 RemoveDeadNodes(DeadNodes);
5878 CSEMap.InsertNode(N, IP); // Memoize the new node.
5883 /// getMachineNode - These are used for target selectors to create a new node
5884 /// with specified return type(s), MachineInstr opcode, and operands.
5886 /// Note that getMachineNode returns the resultant node. If there is already a
5887 /// node of the specified opcode and operands, it returns that node instead of
5888 /// the current one.
5890 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5891 SDVTList VTs = getVTList(VT);
5892 return getMachineNode(Opcode, dl, VTs, None);
5896 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5897 SDVTList VTs = getVTList(VT);
5898 SDValue Ops[] = { Op1 };
5899 return getMachineNode(Opcode, dl, VTs, Ops);
5903 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5904 SDValue Op1, SDValue Op2) {
5905 SDVTList VTs = getVTList(VT);
5906 SDValue Ops[] = { Op1, Op2 };
5907 return getMachineNode(Opcode, dl, VTs, Ops);
5911 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5912 SDValue Op1, SDValue Op2, SDValue Op3) {
5913 SDVTList VTs = getVTList(VT);
5914 SDValue Ops[] = { Op1, Op2, Op3 };
5915 return getMachineNode(Opcode, dl, VTs, Ops);
5919 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5920 ArrayRef<SDValue> Ops) {
5921 SDVTList VTs = getVTList(VT);
5922 return getMachineNode(Opcode, dl, VTs, Ops);
5926 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5927 SDVTList VTs = getVTList(VT1, VT2);
5928 return getMachineNode(Opcode, dl, VTs, None);
5932 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5933 EVT VT1, EVT VT2, SDValue Op1) {
5934 SDVTList VTs = getVTList(VT1, VT2);
5935 SDValue Ops[] = { Op1 };
5936 return getMachineNode(Opcode, dl, VTs, Ops);
5940 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5941 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5942 SDVTList VTs = getVTList(VT1, VT2);
5943 SDValue Ops[] = { Op1, Op2 };
5944 return getMachineNode(Opcode, dl, VTs, Ops);
5948 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5949 EVT VT1, EVT VT2, SDValue Op1,
5950 SDValue Op2, SDValue Op3) {
5951 SDVTList VTs = getVTList(VT1, VT2);
5952 SDValue Ops[] = { Op1, Op2, Op3 };
5953 return getMachineNode(Opcode, dl, VTs, Ops);
5957 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5959 ArrayRef<SDValue> Ops) {
5960 SDVTList VTs = getVTList(VT1, VT2);
5961 return getMachineNode(Opcode, dl, VTs, Ops);
5965 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5966 EVT VT1, EVT VT2, EVT VT3,
5967 SDValue Op1, SDValue Op2) {
5968 SDVTList VTs = getVTList(VT1, VT2, VT3);
5969 SDValue Ops[] = { Op1, Op2 };
5970 return getMachineNode(Opcode, dl, VTs, Ops);
5974 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5975 EVT VT1, EVT VT2, EVT VT3,
5976 SDValue Op1, SDValue Op2, SDValue Op3) {
5977 SDVTList VTs = getVTList(VT1, VT2, VT3);
5978 SDValue Ops[] = { Op1, Op2, Op3 };
5979 return getMachineNode(Opcode, dl, VTs, Ops);
5983 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5984 EVT VT1, EVT VT2, EVT VT3,
5985 ArrayRef<SDValue> Ops) {
5986 SDVTList VTs = getVTList(VT1, VT2, VT3);
5987 return getMachineNode(Opcode, dl, VTs, Ops);
5991 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5992 EVT VT2, EVT VT3, EVT VT4,
5993 ArrayRef<SDValue> Ops) {
5994 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5995 return getMachineNode(Opcode, dl, VTs, Ops);
5999 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6000 ArrayRef<EVT> ResultTys,
6001 ArrayRef<SDValue> Ops) {
6002 SDVTList VTs = getVTList(ResultTys);
6003 return getMachineNode(Opcode, dl, VTs, Ops);
6007 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6008 ArrayRef<SDValue> OpsArray) {
6009 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6012 const SDValue *Ops = OpsArray.data();
6013 unsigned NumOps = OpsArray.size();
6016 FoldingSetNodeID ID;
6017 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6019 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6020 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6024 // Allocate a new MachineSDNode.
6025 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6026 DL.getDebugLoc(), VTs);
6028 // Initialize the operands list.
6029 if (NumOps > array_lengthof(N->LocalOperands))
6030 // We're creating a final node that will live unmorphed for the
6031 // remainder of the current SelectionDAG iteration, so we can allocate
6032 // the operands directly out of a pool with no recycling metadata.
6033 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6036 N->InitOperands(N->LocalOperands, Ops, NumOps);
6037 N->OperandsNeedDelete = false;
6040 CSEMap.InsertNode(N, IP);
6046 /// getTargetExtractSubreg - A convenience function for creating
6047 /// TargetOpcode::EXTRACT_SUBREG nodes.
6049 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6051 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6052 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6053 VT, Operand, SRIdxVal);
6054 return SDValue(Subreg, 0);
6057 /// getTargetInsertSubreg - A convenience function for creating
6058 /// TargetOpcode::INSERT_SUBREG nodes.
6060 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6061 SDValue Operand, SDValue Subreg) {
6062 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6063 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6064 VT, Operand, Subreg, SRIdxVal);
6065 return SDValue(Result, 0);
6068 /// getNodeIfExists - Get the specified node if it's already available, or
6069 /// else return NULL.
6070 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6071 ArrayRef<SDValue> Ops,
6072 const SDNodeFlags *Flags) {
6073 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6074 FoldingSetNodeID ID;
6075 AddNodeIDNode(ID, Opcode, VTList, Ops);
6076 AddNodeIDFlags(ID, Opcode, Flags);
6078 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6084 /// getDbgValue - Creates a SDDbgValue node.
6087 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6088 unsigned R, bool IsIndirect, uint64_t Off,
6089 DebugLoc DL, unsigned O) {
6090 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6091 "Expected inlined-at fields to agree");
6092 return new (DbgInfo->getAlloc())
6093 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6097 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6098 const Value *C, uint64_t Off,
6099 DebugLoc DL, unsigned O) {
6100 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6101 "Expected inlined-at fields to agree");
6102 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6106 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6107 unsigned FI, uint64_t Off,
6108 DebugLoc DL, unsigned O) {
6109 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6110 "Expected inlined-at fields to agree");
6111 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6116 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6117 /// pointed to by a use iterator is deleted, increment the use iterator
6118 /// so that it doesn't dangle.
6120 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6121 SDNode::use_iterator &UI;
6122 SDNode::use_iterator &UE;
6124 void NodeDeleted(SDNode *N, SDNode *E) override {
6125 // Increment the iterator as needed.
6126 while (UI != UE && N == *UI)
6131 RAUWUpdateListener(SelectionDAG &d,
6132 SDNode::use_iterator &ui,
6133 SDNode::use_iterator &ue)
6134 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6139 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6140 /// This can cause recursive merging of nodes in the DAG.
6142 /// This version assumes From has a single result value.
6144 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6145 SDNode *From = FromN.getNode();
6146 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6147 "Cannot replace with this method!");
6148 assert(From != To.getNode() && "Cannot replace uses of with self");
6150 // Iterate over all the existing uses of From. New uses will be added
6151 // to the beginning of the use list, which we avoid visiting.
6152 // This specifically avoids visiting uses of From that arise while the
6153 // replacement is happening, because any such uses would be the result
6154 // of CSE: If an existing node looks like From after one of its operands
6155 // is replaced by To, we don't want to replace of all its users with To
6156 // too. See PR3018 for more info.
6157 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6158 RAUWUpdateListener Listener(*this, UI, UE);
6162 // This node is about to morph, remove its old self from the CSE maps.
6163 RemoveNodeFromCSEMaps(User);
6165 // A user can appear in a use list multiple times, and when this
6166 // happens the uses are usually next to each other in the list.
6167 // To help reduce the number of CSE recomputations, process all
6168 // the uses of this user that we can find this way.
6170 SDUse &Use = UI.getUse();
6173 } while (UI != UE && *UI == User);
6175 // Now that we have modified User, add it back to the CSE maps. If it
6176 // already exists there, recursively merge the results together.
6177 AddModifiedNodeToCSEMaps(User);
6180 // If we just RAUW'd the root, take note.
6181 if (FromN == getRoot())
6185 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6186 /// This can cause recursive merging of nodes in the DAG.
6188 /// This version assumes that for each value of From, there is a
6189 /// corresponding value in To in the same position with the same type.
6191 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6193 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6194 assert((!From->hasAnyUseOfValue(i) ||
6195 From->getValueType(i) == To->getValueType(i)) &&
6196 "Cannot use this version of ReplaceAllUsesWith!");
6199 // Handle the trivial case.
6203 // Iterate over just the existing users of From. See the comments in
6204 // the ReplaceAllUsesWith above.
6205 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6206 RAUWUpdateListener Listener(*this, UI, UE);
6210 // This node is about to morph, remove its old self from the CSE maps.
6211 RemoveNodeFromCSEMaps(User);
6213 // A user can appear in a use list multiple times, and when this
6214 // happens the uses are usually next to each other in the list.
6215 // To help reduce the number of CSE recomputations, process all
6216 // the uses of this user that we can find this way.
6218 SDUse &Use = UI.getUse();
6221 } while (UI != UE && *UI == User);
6223 // Now that we have modified User, add it back to the CSE maps. If it
6224 // already exists there, recursively merge the results together.
6225 AddModifiedNodeToCSEMaps(User);
6228 // If we just RAUW'd the root, take note.
6229 if (From == getRoot().getNode())
6230 setRoot(SDValue(To, getRoot().getResNo()));
6233 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6234 /// This can cause recursive merging of nodes in the DAG.
6236 /// This version can replace From with any result values. To must match the
6237 /// number and types of values returned by From.
6238 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6239 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6240 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6242 // Iterate over just the existing users of From. See the comments in
6243 // the ReplaceAllUsesWith above.
6244 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6245 RAUWUpdateListener Listener(*this, UI, UE);
6249 // This node is about to morph, remove its old self from the CSE maps.
6250 RemoveNodeFromCSEMaps(User);
6252 // A user can appear in a use list multiple times, and when this
6253 // happens the uses are usually next to each other in the list.
6254 // To help reduce the number of CSE recomputations, process all
6255 // the uses of this user that we can find this way.
6257 SDUse &Use = UI.getUse();
6258 const SDValue &ToOp = To[Use.getResNo()];
6261 } while (UI != UE && *UI == User);
6263 // Now that we have modified User, add it back to the CSE maps. If it
6264 // already exists there, recursively merge the results together.
6265 AddModifiedNodeToCSEMaps(User);
6268 // If we just RAUW'd the root, take note.
6269 if (From == getRoot().getNode())
6270 setRoot(SDValue(To[getRoot().getResNo()]));
6273 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6274 /// uses of other values produced by From.getNode() alone. The Deleted
6275 /// vector is handled the same way as for ReplaceAllUsesWith.
6276 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6277 // Handle the really simple, really trivial case efficiently.
6278 if (From == To) return;
6280 // Handle the simple, trivial, case efficiently.
6281 if (From.getNode()->getNumValues() == 1) {
6282 ReplaceAllUsesWith(From, To);
6286 // Iterate over just the existing users of From. See the comments in
6287 // the ReplaceAllUsesWith above.
6288 SDNode::use_iterator UI = From.getNode()->use_begin(),
6289 UE = From.getNode()->use_end();
6290 RAUWUpdateListener Listener(*this, UI, UE);
6293 bool UserRemovedFromCSEMaps = false;
6295 // A user can appear in a use list multiple times, and when this
6296 // happens the uses are usually next to each other in the list.
6297 // To help reduce the number of CSE recomputations, process all
6298 // the uses of this user that we can find this way.
6300 SDUse &Use = UI.getUse();
6302 // Skip uses of different values from the same node.
6303 if (Use.getResNo() != From.getResNo()) {
6308 // If this node hasn't been modified yet, it's still in the CSE maps,
6309 // so remove its old self from the CSE maps.
6310 if (!UserRemovedFromCSEMaps) {
6311 RemoveNodeFromCSEMaps(User);
6312 UserRemovedFromCSEMaps = true;
6317 } while (UI != UE && *UI == User);
6319 // We are iterating over all uses of the From node, so if a use
6320 // doesn't use the specific value, no changes are made.
6321 if (!UserRemovedFromCSEMaps)
6324 // Now that we have modified User, add it back to the CSE maps. If it
6325 // already exists there, recursively merge the results together.
6326 AddModifiedNodeToCSEMaps(User);
6329 // If we just RAUW'd the root, take note.
6330 if (From == getRoot())
6335 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6336 /// to record information about a use.
6343 /// operator< - Sort Memos by User.
6344 bool operator<(const UseMemo &L, const UseMemo &R) {
6345 return (intptr_t)L.User < (intptr_t)R.User;
6349 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6350 /// uses of other values produced by From.getNode() alone. The same value
6351 /// may appear in both the From and To list. The Deleted vector is
6352 /// handled the same way as for ReplaceAllUsesWith.
6353 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6356 // Handle the simple, trivial case efficiently.
6358 return ReplaceAllUsesOfValueWith(*From, *To);
6360 // Read up all the uses and make records of them. This helps
6361 // processing new uses that are introduced during the
6362 // replacement process.
6363 SmallVector<UseMemo, 4> Uses;
6364 for (unsigned i = 0; i != Num; ++i) {
6365 unsigned FromResNo = From[i].getResNo();
6366 SDNode *FromNode = From[i].getNode();
6367 for (SDNode::use_iterator UI = FromNode->use_begin(),
6368 E = FromNode->use_end(); UI != E; ++UI) {
6369 SDUse &Use = UI.getUse();
6370 if (Use.getResNo() == FromResNo) {
6371 UseMemo Memo = { *UI, i, &Use };
6372 Uses.push_back(Memo);
6377 // Sort the uses, so that all the uses from a given User are together.
6378 std::sort(Uses.begin(), Uses.end());
6380 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6381 UseIndex != UseIndexEnd; ) {
6382 // We know that this user uses some value of From. If it is the right
6383 // value, update it.
6384 SDNode *User = Uses[UseIndex].User;
6386 // This node is about to morph, remove its old self from the CSE maps.
6387 RemoveNodeFromCSEMaps(User);
6389 // The Uses array is sorted, so all the uses for a given User
6390 // are next to each other in the list.
6391 // To help reduce the number of CSE recomputations, process all
6392 // the uses of this user that we can find this way.
6394 unsigned i = Uses[UseIndex].Index;
6395 SDUse &Use = *Uses[UseIndex].Use;
6399 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6401 // Now that we have modified User, add it back to the CSE maps. If it
6402 // already exists there, recursively merge the results together.
6403 AddModifiedNodeToCSEMaps(User);
6407 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6408 /// based on their topological order. It returns the maximum id and a vector
6409 /// of the SDNodes* in assigned order by reference.
6410 unsigned SelectionDAG::AssignTopologicalOrder() {
6412 unsigned DAGSize = 0;
6414 // SortedPos tracks the progress of the algorithm. Nodes before it are
6415 // sorted, nodes after it are unsorted. When the algorithm completes
6416 // it is at the end of the list.
6417 allnodes_iterator SortedPos = allnodes_begin();
6419 // Visit all the nodes. Move nodes with no operands to the front of
6420 // the list immediately. Annotate nodes that do have operands with their
6421 // operand count. Before we do this, the Node Id fields of the nodes
6422 // may contain arbitrary values. After, the Node Id fields for nodes
6423 // before SortedPos will contain the topological sort index, and the
6424 // Node Id fields for nodes At SortedPos and after will contain the
6425 // count of outstanding operands.
6426 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6428 checkForCycles(N, this);
6429 unsigned Degree = N->getNumOperands();
6431 // A node with no uses, add it to the result array immediately.
6432 N->setNodeId(DAGSize++);
6433 allnodes_iterator Q = N;
6435 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6436 assert(SortedPos != AllNodes.end() && "Overran node list");
6439 // Temporarily use the Node Id as scratch space for the degree count.
6440 N->setNodeId(Degree);
6444 // Visit all the nodes. As we iterate, move nodes into sorted order,
6445 // such that by the time the end is reached all nodes will be sorted.
6446 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6448 checkForCycles(N, this);
6449 // N is in sorted position, so all its uses have one less operand
6450 // that needs to be sorted.
6451 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6454 unsigned Degree = P->getNodeId();
6455 assert(Degree != 0 && "Invalid node degree");
6458 // All of P's operands are sorted, so P may sorted now.
6459 P->setNodeId(DAGSize++);
6461 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6462 assert(SortedPos != AllNodes.end() && "Overran node list");
6465 // Update P's outstanding operand count.
6466 P->setNodeId(Degree);
6469 if (I == SortedPos) {
6472 dbgs() << "Overran sorted position:\n";
6473 S->dumprFull(this); dbgs() << "\n";
6474 dbgs() << "Checking if this is due to cycles\n";
6475 checkForCycles(this, true);
6477 llvm_unreachable(nullptr);
6481 assert(SortedPos == AllNodes.end() &&
6482 "Topological sort incomplete!");
6483 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6484 "First node in topological sort is not the entry token!");
6485 assert(AllNodes.front().getNodeId() == 0 &&
6486 "First node in topological sort has non-zero id!");
6487 assert(AllNodes.front().getNumOperands() == 0 &&
6488 "First node in topological sort has operands!");
6489 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6490 "Last node in topologic sort has unexpected id!");
6491 assert(AllNodes.back().use_empty() &&
6492 "Last node in topologic sort has users!");
6493 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6497 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6498 /// value is produced by SD.
6499 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6501 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6502 SD->setHasDebugValue(true);
6504 DbgInfo->add(DB, SD, isParameter);
6507 /// TransferDbgValues - Transfer SDDbgValues.
6508 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6509 if (From == To || !From.getNode()->getHasDebugValue())
6511 SDNode *FromNode = From.getNode();
6512 SDNode *ToNode = To.getNode();
6513 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6514 SmallVector<SDDbgValue *, 2> ClonedDVs;
6515 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6517 SDDbgValue *Dbg = *I;
6518 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6520 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6521 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6522 Dbg->getDebugLoc(), Dbg->getOrder());
6523 ClonedDVs.push_back(Clone);
6526 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6527 E = ClonedDVs.end(); I != E; ++I)
6528 AddDbgValue(*I, ToNode, false);
6531 //===----------------------------------------------------------------------===//
6533 //===----------------------------------------------------------------------===//
6535 HandleSDNode::~HandleSDNode() {
6539 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6540 DebugLoc DL, const GlobalValue *GA,
6541 EVT VT, int64_t o, unsigned char TF)
6542 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6546 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6547 SDValue X, unsigned SrcAS,
6549 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6550 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6552 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6553 EVT memvt, MachineMemOperand *mmo)
6554 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6555 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6556 MMO->isNonTemporal(), MMO->isInvariant());
6557 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6558 assert(isNonTemporal() == MMO->isNonTemporal() &&
6559 "Non-temporal encoding error!");
6560 // We check here that the size of the memory operand fits within the size of
6561 // the MMO. This is because the MMO might indicate only a possible address
6562 // range instead of specifying the affected memory addresses precisely.
6563 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6566 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6567 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6568 : SDNode(Opc, Order, dl, VTs, Ops),
6569 MemoryVT(memvt), MMO(mmo) {
6570 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6571 MMO->isNonTemporal(), MMO->isInvariant());
6572 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6573 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6576 /// Profile - Gather unique data for the node.
6578 void SDNode::Profile(FoldingSetNodeID &ID) const {
6579 AddNodeIDNode(ID, this);
6584 std::vector<EVT> VTs;
6587 VTs.reserve(MVT::LAST_VALUETYPE);
6588 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6589 VTs.push_back(MVT((MVT::SimpleValueType)i));
6594 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6595 static ManagedStatic<EVTArray> SimpleVTArray;
6596 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6598 /// getValueTypeList - Return a pointer to the specified value type.
6600 const EVT *SDNode::getValueTypeList(EVT VT) {
6601 if (VT.isExtended()) {
6602 sys::SmartScopedLock<true> Lock(*VTMutex);
6603 return &(*EVTs->insert(VT).first);
6605 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6606 "Value type out of range!");
6607 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6611 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6612 /// indicated value. This method ignores uses of other values defined by this
6614 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6615 assert(Value < getNumValues() && "Bad value!");
6617 // TODO: Only iterate over uses of a given value of the node
6618 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6619 if (UI.getUse().getResNo() == Value) {
6626 // Found exactly the right number of uses?
6631 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6632 /// value. This method ignores uses of other values defined by this operation.
6633 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6634 assert(Value < getNumValues() && "Bad value!");
6636 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6637 if (UI.getUse().getResNo() == Value)
6644 /// isOnlyUserOf - Return true if this node is the only use of N.
6646 bool SDNode::isOnlyUserOf(SDNode *N) const {
6648 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6659 /// isOperand - Return true if this node is an operand of N.
6661 bool SDValue::isOperandOf(SDNode *N) const {
6662 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6663 if (*this == N->getOperand(i))
6668 bool SDNode::isOperandOf(SDNode *N) const {
6669 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6670 if (this == N->OperandList[i].getNode())
6675 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6676 /// be a chain) reaches the specified operand without crossing any
6677 /// side-effecting instructions on any chain path. In practice, this looks
6678 /// through token factors and non-volatile loads. In order to remain efficient,
6679 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6680 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6681 unsigned Depth) const {
6682 if (*this == Dest) return true;
6684 // Don't search too deeply, we just want to be able to see through
6685 // TokenFactor's etc.
6686 if (Depth == 0) return false;
6688 // If this is a token factor, all inputs to the TF happen in parallel. If any
6689 // of the operands of the TF does not reach dest, then we cannot do the xform.
6690 if (getOpcode() == ISD::TokenFactor) {
6691 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6692 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6697 // Loads don't have side effects, look through them.
6698 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6699 if (!Ld->isVolatile())
6700 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6705 /// hasPredecessor - Return true if N is a predecessor of this node.
6706 /// N is either an operand of this node, or can be reached by recursively
6707 /// traversing up the operands.
6708 /// NOTE: This is an expensive method. Use it carefully.
6709 bool SDNode::hasPredecessor(const SDNode *N) const {
6710 SmallPtrSet<const SDNode *, 32> Visited;
6711 SmallVector<const SDNode *, 16> Worklist;
6712 return hasPredecessorHelper(N, Visited, Worklist);
6716 SDNode::hasPredecessorHelper(const SDNode *N,
6717 SmallPtrSetImpl<const SDNode *> &Visited,
6718 SmallVectorImpl<const SDNode *> &Worklist) const {
6719 if (Visited.empty()) {
6720 Worklist.push_back(this);
6722 // Take a look in the visited set. If we've already encountered this node
6723 // we needn't search further.
6724 if (Visited.count(N))
6728 // Haven't visited N yet. Continue the search.
6729 while (!Worklist.empty()) {
6730 const SDNode *M = Worklist.pop_back_val();
6731 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6732 SDNode *Op = M->getOperand(i).getNode();
6733 if (Visited.insert(Op).second)
6734 Worklist.push_back(Op);
6743 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6744 assert(Num < NumOperands && "Invalid child # of SDNode!");
6745 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6748 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6749 assert(N->getNumValues() == 1 &&
6750 "Can't unroll a vector with multiple results!");
6752 EVT VT = N->getValueType(0);
6753 unsigned NE = VT.getVectorNumElements();
6754 EVT EltVT = VT.getVectorElementType();
6757 SmallVector<SDValue, 8> Scalars;
6758 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6760 // If ResNE is 0, fully unroll the vector op.
6763 else if (NE > ResNE)
6767 for (i= 0; i != NE; ++i) {
6768 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6769 SDValue Operand = N->getOperand(j);
6770 EVT OperandVT = Operand.getValueType();
6771 if (OperandVT.isVector()) {
6772 // A vector operand; extract a single element.
6773 EVT OperandEltVT = OperandVT.getVectorElementType();
6774 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6777 getConstant(i, dl, TLI->getVectorIdxTy()));
6779 // A scalar operand; just use it as is.
6780 Operands[j] = Operand;
6784 switch (N->getOpcode()) {
6786 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6789 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6796 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6797 getShiftAmountOperand(Operands[0].getValueType(),
6800 case ISD::SIGN_EXTEND_INREG:
6801 case ISD::FP_ROUND_INREG: {
6802 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6803 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6805 getValueType(ExtVT)));
6810 for (; i < ResNE; ++i)
6811 Scalars.push_back(getUNDEF(EltVT));
6813 return getNode(ISD::BUILD_VECTOR, dl,
6814 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6818 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6819 /// location that is 'Dist' units away from the location that the 'Base' load
6820 /// is loading from.
6821 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6822 unsigned Bytes, int Dist) const {
6823 if (LD->getChain() != Base->getChain())
6825 EVT VT = LD->getValueType(0);
6826 if (VT.getSizeInBits() / 8 != Bytes)
6829 SDValue Loc = LD->getOperand(1);
6830 SDValue BaseLoc = Base->getOperand(1);
6831 if (Loc.getOpcode() == ISD::FrameIndex) {
6832 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6834 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6835 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6836 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6837 int FS = MFI->getObjectSize(FI);
6838 int BFS = MFI->getObjectSize(BFI);
6839 if (FS != BFS || FS != (int)Bytes) return false;
6840 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6844 if (isBaseWithConstantOffset(Loc)) {
6845 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6846 if (Loc.getOperand(0) == BaseLoc) {
6847 // If the base location is a simple address with no offset itself, then
6848 // the second load's first add operand should be the base address.
6849 if (LocOffset == Dist * (int)Bytes)
6851 } else if (isBaseWithConstantOffset(BaseLoc)) {
6852 // The base location itself has an offset, so subtract that value from the
6853 // second load's offset before comparing to distance * size.
6855 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6856 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6857 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6862 const GlobalValue *GV1 = nullptr;
6863 const GlobalValue *GV2 = nullptr;
6864 int64_t Offset1 = 0;
6865 int64_t Offset2 = 0;
6866 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6867 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6868 if (isGA1 && isGA2 && GV1 == GV2)
6869 return Offset1 == (Offset2 + Dist*Bytes);
6874 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6875 /// it cannot be inferred.
6876 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6877 // If this is a GlobalAddress + cst, return the alignment.
6878 const GlobalValue *GV;
6879 int64_t GVOffset = 0;
6880 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6881 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6882 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6883 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6884 *TLI->getDataLayout());
6885 unsigned AlignBits = KnownZero.countTrailingOnes();
6886 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6888 return MinAlign(Align, GVOffset);
6891 // If this is a direct reference to a stack slot, use information about the
6892 // stack slot's alignment.
6893 int FrameIdx = 1 << 31;
6894 int64_t FrameOffset = 0;
6895 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6896 FrameIdx = FI->getIndex();
6897 } else if (isBaseWithConstantOffset(Ptr) &&
6898 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6900 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6901 FrameOffset = Ptr.getConstantOperandVal(1);
6904 if (FrameIdx != (1 << 31)) {
6905 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6906 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6914 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6915 /// which is split (or expanded) into two not necessarily identical pieces.
6916 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6917 // Currently all types are split in half.
6919 if (!VT.isVector()) {
6920 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6922 unsigned NumElements = VT.getVectorNumElements();
6923 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6924 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6927 return std::make_pair(LoVT, HiVT);
6930 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6932 std::pair<SDValue, SDValue>
6933 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6935 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6936 N.getValueType().getVectorNumElements() &&
6937 "More vector elements requested than available!");
6939 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6940 getConstant(0, DL, TLI->getVectorIdxTy()));
6941 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6942 getConstant(LoVT.getVectorNumElements(), DL,
6943 TLI->getVectorIdxTy()));
6944 return std::make_pair(Lo, Hi);
6947 void SelectionDAG::ExtractVectorElements(SDValue Op,
6948 SmallVectorImpl<SDValue> &Args,
6949 unsigned Start, unsigned Count) {
6950 EVT VT = Op.getValueType();
6952 Count = VT.getVectorNumElements();
6954 EVT EltVT = VT.getVectorElementType();
6955 EVT IdxTy = TLI->getVectorIdxTy();
6957 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6958 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6959 Op, getConstant(i, SL, IdxTy)));
6963 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6964 unsigned GlobalAddressSDNode::getAddressSpace() const {
6965 return getGlobal()->getType()->getAddressSpace();
6969 Type *ConstantPoolSDNode::getType() const {
6970 if (isMachineConstantPoolEntry())
6971 return Val.MachineCPVal->getType();
6972 return Val.ConstVal->getType();
6975 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6977 unsigned &SplatBitSize,
6979 unsigned MinSplatBits,
6980 bool isBigEndian) const {
6981 EVT VT = getValueType(0);
6982 assert(VT.isVector() && "Expected a vector type");
6983 unsigned sz = VT.getSizeInBits();
6984 if (MinSplatBits > sz)
6987 SplatValue = APInt(sz, 0);
6988 SplatUndef = APInt(sz, 0);
6990 // Get the bits. Bits with undefined values (when the corresponding element
6991 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6992 // in SplatValue. If any of the values are not constant, give up and return
6994 unsigned int nOps = getNumOperands();
6995 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6996 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6998 for (unsigned j = 0; j < nOps; ++j) {
6999 unsigned i = isBigEndian ? nOps-1-j : j;
7000 SDValue OpVal = getOperand(i);
7001 unsigned BitPos = j * EltBitSize;
7003 if (OpVal.getOpcode() == ISD::UNDEF)
7004 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7005 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7006 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7007 zextOrTrunc(sz) << BitPos;
7008 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7009 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7014 // The build_vector is all constants or undefs. Find the smallest element
7015 // size that splats the vector.
7017 HasAnyUndefs = (SplatUndef != 0);
7020 unsigned HalfSize = sz / 2;
7021 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7022 APInt LowValue = SplatValue.trunc(HalfSize);
7023 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7024 APInt LowUndef = SplatUndef.trunc(HalfSize);
7026 // If the two halves do not match (ignoring undef bits), stop here.
7027 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7028 MinSplatBits > HalfSize)
7031 SplatValue = HighValue | LowValue;
7032 SplatUndef = HighUndef & LowUndef;
7041 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7042 if (UndefElements) {
7043 UndefElements->clear();
7044 UndefElements->resize(getNumOperands());
7047 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7048 SDValue Op = getOperand(i);
7049 if (Op.getOpcode() == ISD::UNDEF) {
7051 (*UndefElements)[i] = true;
7052 } else if (!Splatted) {
7054 } else if (Splatted != Op) {
7060 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7061 "Can only have a splat without a constant for all undefs.");
7062 return getOperand(0);
7069 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7070 return dyn_cast_or_null<ConstantSDNode>(
7071 getSplatValue(UndefElements).getNode());
7075 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7076 return dyn_cast_or_null<ConstantFPSDNode>(
7077 getSplatValue(UndefElements).getNode());
7080 bool BuildVectorSDNode::isConstant() const {
7081 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7082 unsigned Opc = getOperand(i).getOpcode();
7083 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7089 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7090 // Find the first non-undef value in the shuffle mask.
7092 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7095 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7097 // Make sure all remaining elements are either undef or the same as the first
7099 for (int Idx = Mask[i]; i != e; ++i)
7100 if (Mask[i] >= 0 && Mask[i] != Idx)
7106 static void checkForCyclesHelper(const SDNode *N,
7107 SmallPtrSetImpl<const SDNode*> &Visited,
7108 SmallPtrSetImpl<const SDNode*> &Checked,
7109 const llvm::SelectionDAG *DAG) {
7110 // If this node has already been checked, don't check it again.
7111 if (Checked.count(N))
7114 // If a node has already been visited on this depth-first walk, reject it as
7116 if (!Visited.insert(N).second) {
7117 errs() << "Detected cycle in SelectionDAG\n";
7118 dbgs() << "Offending node:\n";
7119 N->dumprFull(DAG); dbgs() << "\n";
7123 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7124 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7131 void llvm::checkForCycles(const llvm::SDNode *N,
7132 const llvm::SelectionDAG *DAG,
7140 assert(N && "Checking nonexistent SDNode");
7141 SmallPtrSet<const SDNode*, 32> visited;
7142 SmallPtrSet<const SDNode*, 32> checked;
7143 checkForCyclesHelper(N, visited, checked, DAG);
7148 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7149 checkForCycles(DAG->getRoot().getNode(), DAG, force);