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 /// If this is an SDNode with special info, add this info to the NodeID data.
431 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
432 switch (N->getOpcode()) {
433 case ISD::TargetExternalSymbol:
434 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::MCSymbol: {
801 auto *MCSN = cast<MCSymbolSDNode>(N);
802 Erased = MCSymbols.erase(MCSN->getMCSymbol());
805 case ISD::VALUETYPE: {
806 EVT VT = cast<VTSDNode>(N)->getVT();
807 if (VT.isExtended()) {
808 Erased = ExtendedValueTypeNodes.erase(VT);
810 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
811 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
816 // Remove it from the CSE Map.
817 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
818 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
819 Erased = CSEMap.RemoveNode(N);
823 // Verify that the node was actually in one of the CSE maps, unless it has a
824 // flag result (which cannot be CSE'd) or is one of the special cases that are
825 // not subject to CSE.
826 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
827 !N->isMachineOpcode() && !doNotCSE(N)) {
830 llvm_unreachable("Node is not in map!");
836 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
837 /// maps and modified in place. Add it back to the CSE maps, unless an identical
838 /// node already exists, in which case transfer all its users to the existing
839 /// node. This transfer can potentially trigger recursive merging.
842 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
843 // For node types that aren't CSE'd, just act as if no identical node
846 SDNode *Existing = CSEMap.GetOrInsertNode(N);
848 // If there was already an existing matching node, use ReplaceAllUsesWith
849 // to replace the dead one with the existing one. This can cause
850 // recursive merging of other unrelated nodes down the line.
851 ReplaceAllUsesWith(N, Existing);
853 // N is now dead. Inform the listeners and delete it.
854 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
855 DUL->NodeDeleted(N, Existing);
856 DeleteNodeNotInCSEMaps(N);
861 // If the node doesn't already exist, we updated it. Inform listeners.
862 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
866 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
867 /// were replaced with those specified. If this node is never memoized,
868 /// return null, otherwise return a pointer to the slot it would take. If a
869 /// node already exists with these operands, the slot will be non-null.
870 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
875 SDValue Ops[] = { Op };
877 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
878 AddNodeIDCustom(ID, N);
879 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
883 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
884 /// were replaced with those specified. If this node is never memoized,
885 /// return null, otherwise return a pointer to the slot it would take. If a
886 /// node already exists with these operands, the slot will be non-null.
887 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
888 SDValue Op1, SDValue Op2,
893 SDValue Ops[] = { Op1, Op2 };
895 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
896 AddNodeIDCustom(ID, N);
897 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
902 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
903 /// were replaced with those specified. If this node is never memoized,
904 /// return null, otherwise return a pointer to the slot it would take. If a
905 /// node already exists with these operands, the slot will be non-null.
906 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
912 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
913 AddNodeIDCustom(ID, N);
914 SDNode *Node = FindNodeOrInsertPos(ID, N->getDebugLoc(), InsertPos);
918 /// getEVTAlignment - Compute the default alignment value for the
921 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
922 Type *Ty = VT == MVT::iPTR ?
923 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
924 VT.getTypeForEVT(*getContext());
926 return TLI->getDataLayout()->getABITypeAlignment(Ty);
929 // EntryNode could meaningfully have debug info if we can find it...
930 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
931 : TM(tm), TSI(nullptr), TLI(nullptr), OptLevel(OL),
932 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
933 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
934 UpdateListeners(nullptr) {
935 AllNodes.push_back(&EntryNode);
936 DbgInfo = new SDDbgInfo();
939 void SelectionDAG::init(MachineFunction &mf) {
941 TLI = getSubtarget().getTargetLowering();
942 TSI = getSubtarget().getSelectionDAGInfo();
943 Context = &mf.getFunction()->getContext();
946 SelectionDAG::~SelectionDAG() {
947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
952 void SelectionDAG::allnodes_clear() {
953 assert(&*AllNodes.begin() == &EntryNode);
954 AllNodes.remove(AllNodes.begin());
955 while (!AllNodes.empty())
956 DeallocateNode(AllNodes.begin());
959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL,
960 SDVTList VTs, SDValue N1,
962 const SDNodeFlags *Flags) {
963 if (isBinOpWithFlags(Opcode)) {
964 // If no flags were passed in, use a default flags object.
966 if (Flags == nullptr)
969 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode(
970 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2, *Flags);
975 BinarySDNode *N = new (NodeAllocator)
976 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2);
980 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
982 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
984 switch (N->getOpcode()) {
987 case ISD::ConstantFP:
988 llvm_unreachable("Querying for Constant and ConstantFP nodes requires "
989 "debug location. Use another overload.");
995 SDNode *SelectionDAG::FindNodeOrInsertPos(const FoldingSetNodeID &ID,
996 DebugLoc DL, void *&InsertPos) {
997 SDNode *N = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
999 switch (N->getOpcode()) {
1000 default: break; // Process only regular (non-target) constant nodes.
1002 case ISD::ConstantFP:
1003 // Erase debug location from the node if the node is used at several
1004 // different places to do not propagate one location to all uses as it
1005 // leads to incorrect debug info.
1006 if (N->getDebugLoc() != DL)
1007 N->setDebugLoc(DebugLoc());
1014 void SelectionDAG::clear() {
1016 OperandAllocator.Reset();
1019 ExtendedValueTypeNodes.clear();
1020 ExternalSymbols.clear();
1021 TargetExternalSymbols.clear();
1023 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1024 static_cast<CondCodeSDNode*>(nullptr));
1025 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1026 static_cast<SDNode*>(nullptr));
1028 EntryNode.UseList = nullptr;
1029 AllNodes.push_back(&EntryNode);
1030 Root = getEntryNode();
1034 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1035 return VT.bitsGT(Op.getValueType()) ?
1036 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
1037 getNode(ISD::TRUNCATE, DL, VT, Op);
1040 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1041 return VT.bitsGT(Op.getValueType()) ?
1042 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
1043 getNode(ISD::TRUNCATE, DL, VT, Op);
1046 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
1047 return VT.bitsGT(Op.getValueType()) ?
1048 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
1049 getNode(ISD::TRUNCATE, DL, VT, Op);
1052 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT,
1054 if (VT.bitsLE(Op.getValueType()))
1055 return getNode(ISD::TRUNCATE, SL, VT, Op);
1057 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT);
1058 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
1061 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
1062 assert(!VT.isVector() &&
1063 "getZeroExtendInReg should use the vector element type instead of "
1064 "the vector type!");
1065 if (Op.getValueType() == VT) return Op;
1066 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1067 APInt Imm = APInt::getLowBitsSet(BitWidth,
1068 VT.getSizeInBits());
1069 return getNode(ISD::AND, DL, Op.getValueType(), Op,
1070 getConstant(Imm, DL, Op.getValueType()));
1073 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1074 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1075 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1076 "The sizes of the input and result must match in order to perform the "
1077 "extend in-register.");
1078 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1079 "The destination vector type must have fewer lanes than the input.");
1080 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op);
1083 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1084 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1085 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1086 "The sizes of the input and result must match in order to perform the "
1087 "extend in-register.");
1088 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1089 "The destination vector type must have fewer lanes than the input.");
1090 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op);
1093 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
1094 assert(VT.isVector() && "This DAG node is restricted to vector types.");
1095 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() &&
1096 "The sizes of the input and result must match in order to perform the "
1097 "extend in-register.");
1098 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
1099 "The destination vector type must have fewer lanes than the input.");
1100 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
1103 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
1105 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
1106 EVT EltVT = VT.getScalarType();
1108 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL, VT);
1109 return getNode(ISD::XOR, DL, VT, Val, NegOne);
1112 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
1113 EVT EltVT = VT.getScalarType();
1115 switch (TLI->getBooleanContents(VT)) {
1116 case TargetLowering::ZeroOrOneBooleanContent:
1117 case TargetLowering::UndefinedBooleanContent:
1118 TrueValue = getConstant(1, DL, VT);
1120 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1121 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), DL,
1125 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1128 SDValue SelectionDAG::getConstant(uint64_t Val, SDLoc DL, EVT VT, bool isT,
1130 EVT EltVT = VT.getScalarType();
1131 assert((EltVT.getSizeInBits() >= 64 ||
1132 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1133 "getConstant with a uint64_t value that doesn't fit in the type!");
1134 return getConstant(APInt(EltVT.getSizeInBits(), Val), DL, VT, isT, isO);
1137 SDValue SelectionDAG::getConstant(const APInt &Val, SDLoc DL, EVT VT, bool isT,
1140 return getConstant(*ConstantInt::get(*Context, Val), DL, VT, isT, isO);
1143 SDValue SelectionDAG::getConstant(const ConstantInt &Val, SDLoc DL, EVT VT,
1144 bool isT, bool isO) {
1145 assert(VT.isInteger() && "Cannot create FP integer constant!");
1147 EVT EltVT = VT.getScalarType();
1148 const ConstantInt *Elt = &Val;
1150 // In some cases the vector type is legal but the element type is illegal and
1151 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1152 // inserted value (the type does not need to match the vector element type).
1153 // Any extra bits introduced will be truncated away.
1154 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1155 TargetLowering::TypePromoteInteger) {
1156 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1157 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1158 Elt = ConstantInt::get(*getContext(), NewVal);
1160 // In other cases the element type is illegal and needs to be expanded, for
1161 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1162 // the value into n parts and use a vector type with n-times the elements.
1163 // Then bitcast to the type requested.
1164 // Legalizing constants too early makes the DAGCombiner's job harder so we
1165 // only legalize if the DAG tells us we must produce legal types.
1166 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1167 TLI->getTypeAction(*getContext(), EltVT) ==
1168 TargetLowering::TypeExpandInteger) {
1169 APInt NewVal = Elt->getValue();
1170 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1171 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1172 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1173 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1175 // Check the temporary vector is the correct size. If this fails then
1176 // getTypeToTransformTo() probably returned a type whose size (in bits)
1177 // isn't a power-of-2 factor of the requested type size.
1178 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1180 SmallVector<SDValue, 2> EltParts;
1181 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1182 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1183 .trunc(ViaEltSizeInBits), DL,
1184 ViaEltVT, isT, isO));
1187 // EltParts is currently in little endian order. If we actually want
1188 // big-endian order then reverse it now.
1189 if (TLI->isBigEndian())
1190 std::reverse(EltParts.begin(), EltParts.end());
1192 // The elements must be reversed when the element order is different
1193 // to the endianness of the elements (because the BITCAST is itself a
1194 // vector shuffle in this situation). However, we do not need any code to
1195 // perform this reversal because getConstant() is producing a vector
1197 // This situation occurs in MIPS MSA.
1199 SmallVector<SDValue, 8> Ops;
1200 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1201 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1203 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1204 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1209 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1210 "APInt size does not match type size!");
1211 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1212 FoldingSetNodeID ID;
1213 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1217 SDNode *N = nullptr;
1218 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1220 return SDValue(N, 0);
1223 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, DL.getDebugLoc(),
1225 CSEMap.InsertNode(N, IP);
1229 SDValue Result(N, 0);
1230 if (VT.isVector()) {
1231 SmallVector<SDValue, 8> Ops;
1232 Ops.assign(VT.getVectorNumElements(), Result);
1233 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1238 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, SDLoc DL, bool isTarget) {
1239 return getConstant(Val, DL, TLI->getPointerTy(), isTarget);
1242 SDValue SelectionDAG::getConstantFP(const APFloat& V, SDLoc DL, EVT VT,
1244 return getConstantFP(*ConstantFP::get(*getContext(), V), DL, VT, isTarget);
1247 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, SDLoc DL, EVT VT,
1249 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1251 EVT EltVT = VT.getScalarType();
1253 // Do the map lookup using the actual bit pattern for the floating point
1254 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1255 // we don't have issues with SNANs.
1256 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1257 FoldingSetNodeID ID;
1258 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1261 SDNode *N = nullptr;
1262 if ((N = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)))
1264 return SDValue(N, 0);
1267 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, DL.getDebugLoc(),
1269 CSEMap.InsertNode(N, IP);
1273 SDValue Result(N, 0);
1274 if (VT.isVector()) {
1275 SmallVector<SDValue, 8> Ops;
1276 Ops.assign(VT.getVectorNumElements(), Result);
1277 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1282 SDValue SelectionDAG::getConstantFP(double Val, SDLoc DL, EVT VT,
1284 EVT EltVT = VT.getScalarType();
1285 if (EltVT==MVT::f32)
1286 return getConstantFP(APFloat((float)Val), DL, VT, isTarget);
1287 else if (EltVT==MVT::f64)
1288 return getConstantFP(APFloat(Val), DL, VT, isTarget);
1289 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1292 APFloat apf = APFloat(Val);
1293 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1295 return getConstantFP(apf, DL, VT, isTarget);
1297 llvm_unreachable("Unsupported type in getConstantFP");
1300 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1301 EVT VT, int64_t Offset,
1303 unsigned char TargetFlags) {
1304 assert((TargetFlags == 0 || isTargetGA) &&
1305 "Cannot set target flags on target-independent globals");
1307 // Truncate (with sign-extension) the offset value to the pointer size.
1308 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1310 Offset = SignExtend64(Offset, BitWidth);
1313 if (GV->isThreadLocal())
1314 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1316 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1318 FoldingSetNodeID ID;
1319 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1321 ID.AddInteger(Offset);
1322 ID.AddInteger(TargetFlags);
1323 ID.AddInteger(GV->getType()->getAddressSpace());
1325 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
1326 return SDValue(E, 0);
1328 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1329 DL.getDebugLoc(), GV, VT,
1330 Offset, TargetFlags);
1331 CSEMap.InsertNode(N, IP);
1333 return SDValue(N, 0);
1336 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1337 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1338 FoldingSetNodeID ID;
1339 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1342 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1343 return SDValue(E, 0);
1345 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1346 CSEMap.InsertNode(N, IP);
1348 return SDValue(N, 0);
1351 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1352 unsigned char TargetFlags) {
1353 assert((TargetFlags == 0 || isTarget) &&
1354 "Cannot set target flags on target-independent jump tables");
1355 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1356 FoldingSetNodeID ID;
1357 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1359 ID.AddInteger(TargetFlags);
1361 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1362 return SDValue(E, 0);
1364 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1366 CSEMap.InsertNode(N, IP);
1368 return SDValue(N, 0);
1371 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1372 unsigned Alignment, int Offset,
1374 unsigned char TargetFlags) {
1375 assert((TargetFlags == 0 || isTarget) &&
1376 "Cannot set target flags on target-independent globals");
1378 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1379 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1380 FoldingSetNodeID ID;
1381 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1382 ID.AddInteger(Alignment);
1383 ID.AddInteger(Offset);
1385 ID.AddInteger(TargetFlags);
1387 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1388 return SDValue(E, 0);
1390 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1391 Alignment, TargetFlags);
1392 CSEMap.InsertNode(N, IP);
1394 return SDValue(N, 0);
1398 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1399 unsigned Alignment, int Offset,
1401 unsigned char TargetFlags) {
1402 assert((TargetFlags == 0 || isTarget) &&
1403 "Cannot set target flags on target-independent globals");
1405 Alignment = TLI->getDataLayout()->getPrefTypeAlignment(C->getType());
1406 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1407 FoldingSetNodeID ID;
1408 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1409 ID.AddInteger(Alignment);
1410 ID.AddInteger(Offset);
1411 C->addSelectionDAGCSEId(ID);
1412 ID.AddInteger(TargetFlags);
1414 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1415 return SDValue(E, 0);
1417 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1418 Alignment, TargetFlags);
1419 CSEMap.InsertNode(N, IP);
1421 return SDValue(N, 0);
1424 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1425 unsigned char TargetFlags) {
1426 FoldingSetNodeID ID;
1427 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1428 ID.AddInteger(Index);
1429 ID.AddInteger(Offset);
1430 ID.AddInteger(TargetFlags);
1432 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1433 return SDValue(E, 0);
1435 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1437 CSEMap.InsertNode(N, IP);
1439 return SDValue(N, 0);
1442 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1443 FoldingSetNodeID ID;
1444 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1447 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1448 return SDValue(E, 0);
1450 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1451 CSEMap.InsertNode(N, IP);
1453 return SDValue(N, 0);
1456 SDValue SelectionDAG::getValueType(EVT VT) {
1457 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1458 ValueTypeNodes.size())
1459 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1461 SDNode *&N = VT.isExtended() ?
1462 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1464 if (N) return SDValue(N, 0);
1465 N = new (NodeAllocator) VTSDNode(VT);
1467 return SDValue(N, 0);
1470 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1471 SDNode *&N = ExternalSymbols[Sym];
1472 if (N) return SDValue(N, 0);
1473 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1475 return SDValue(N, 0);
1478 SDValue SelectionDAG::getMCSymbol(MCSymbol *Sym, EVT VT) {
1479 SDNode *&N = MCSymbols[Sym];
1481 return SDValue(N, 0);
1482 N = new (NodeAllocator) MCSymbolSDNode(Sym, VT);
1484 return SDValue(N, 0);
1487 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1488 unsigned char TargetFlags) {
1490 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1492 if (N) return SDValue(N, 0);
1493 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1495 return SDValue(N, 0);
1498 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1499 if ((unsigned)Cond >= CondCodeNodes.size())
1500 CondCodeNodes.resize(Cond+1);
1502 if (!CondCodeNodes[Cond]) {
1503 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1504 CondCodeNodes[Cond] = N;
1508 return SDValue(CondCodeNodes[Cond], 0);
1511 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1512 // the shuffle mask M that point at N1 to point at N2, and indices that point
1513 // N2 to point at N1.
1514 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1516 ShuffleVectorSDNode::commuteMask(M);
1519 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1520 SDValue N2, const int *Mask) {
1521 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1522 "Invalid VECTOR_SHUFFLE");
1524 // Canonicalize shuffle undef, undef -> undef
1525 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1526 return getUNDEF(VT);
1528 // Validate that all indices in Mask are within the range of the elements
1529 // input to the shuffle.
1530 unsigned NElts = VT.getVectorNumElements();
1531 SmallVector<int, 8> MaskVec;
1532 for (unsigned i = 0; i != NElts; ++i) {
1533 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1534 MaskVec.push_back(Mask[i]);
1537 // Canonicalize shuffle v, v -> v, undef
1540 for (unsigned i = 0; i != NElts; ++i)
1541 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1544 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1545 if (N1.getOpcode() == ISD::UNDEF)
1546 commuteShuffle(N1, N2, MaskVec);
1548 // If shuffling a splat, try to blend the splat instead. We do this here so
1549 // that even when this arises during lowering we don't have to re-handle it.
1550 auto BlendSplat = [&](BuildVectorSDNode *BV, int Offset) {
1551 BitVector UndefElements;
1552 SDValue Splat = BV->getSplatValue(&UndefElements);
1556 for (int i = 0; i < (int)NElts; ++i) {
1557 if (MaskVec[i] < Offset || MaskVec[i] >= (Offset + (int)NElts))
1560 // If this input comes from undef, mark it as such.
1561 if (UndefElements[MaskVec[i] - Offset]) {
1566 // If we can blend a non-undef lane, use that instead.
1567 if (!UndefElements[i])
1568 MaskVec[i] = i + Offset;
1571 if (auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
1572 BlendSplat(N1BV, 0);
1573 if (auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
1574 BlendSplat(N2BV, NElts);
1576 // Canonicalize all index into lhs, -> shuffle lhs, undef
1577 // Canonicalize all index into rhs, -> shuffle rhs, undef
1578 bool AllLHS = true, AllRHS = true;
1579 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1580 for (unsigned i = 0; i != NElts; ++i) {
1581 if (MaskVec[i] >= (int)NElts) {
1586 } else if (MaskVec[i] >= 0) {
1590 if (AllLHS && AllRHS)
1591 return getUNDEF(VT);
1592 if (AllLHS && !N2Undef)
1596 commuteShuffle(N1, N2, MaskVec);
1598 // Reset our undef status after accounting for the mask.
1599 N2Undef = N2.getOpcode() == ISD::UNDEF;
1600 // Re-check whether both sides ended up undef.
1601 if (N1.getOpcode() == ISD::UNDEF && N2Undef)
1602 return getUNDEF(VT);
1604 // If Identity shuffle return that node.
1605 bool Identity = true, AllSame = true;
1606 for (unsigned i = 0; i != NElts; ++i) {
1607 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1608 if (MaskVec[i] != MaskVec[0]) AllSame = false;
1610 if (Identity && NElts)
1613 // Shuffling a constant splat doesn't change the result.
1617 // Look through any bitcasts. We check that these don't change the number
1618 // (and size) of elements and just changes their types.
1619 while (V.getOpcode() == ISD::BITCAST)
1620 V = V->getOperand(0);
1622 // A splat should always show up as a build vector node.
1623 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
1624 BitVector UndefElements;
1625 SDValue Splat = BV->getSplatValue(&UndefElements);
1626 // If this is a splat of an undef, shuffling it is also undef.
1627 if (Splat && Splat.getOpcode() == ISD::UNDEF)
1628 return getUNDEF(VT);
1631 V.getValueType().getVectorNumElements() == VT.getVectorNumElements();
1633 // We only have a splat which can skip shuffles if there is a splatted
1634 // value and no undef lanes rearranged by the shuffle.
1635 if (Splat && UndefElements.none()) {
1636 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the
1637 // number of elements match or the value splatted is a zero constant.
1640 if (auto *C = dyn_cast<ConstantSDNode>(Splat))
1641 if (C->isNullValue())
1645 // If the shuffle itself creates a splat, build the vector directly.
1646 if (AllSame && SameNumElts) {
1647 const SDValue &Splatted = BV->getOperand(MaskVec[0]);
1648 SmallVector<SDValue, 8> Ops(NElts, Splatted);
1650 EVT BuildVT = BV->getValueType(0);
1651 SDValue NewBV = getNode(ISD::BUILD_VECTOR, dl, BuildVT, Ops);
1653 // We may have jumped through bitcasts, so the type of the
1654 // BUILD_VECTOR may not match the type of the shuffle.
1656 NewBV = getNode(ISD::BITCAST, dl, VT, NewBV);
1662 FoldingSetNodeID ID;
1663 SDValue Ops[2] = { N1, N2 };
1664 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1665 for (unsigned i = 0; i != NElts; ++i)
1666 ID.AddInteger(MaskVec[i]);
1669 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1670 return SDValue(E, 0);
1672 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1673 // SDNode doesn't have access to it. This memory will be "leaked" when
1674 // the node is deallocated, but recovered when the NodeAllocator is released.
1675 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1676 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1678 ShuffleVectorSDNode *N =
1679 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1680 dl.getDebugLoc(), N1, N2,
1682 CSEMap.InsertNode(N, IP);
1684 return SDValue(N, 0);
1687 SDValue SelectionDAG::getCommutedVectorShuffle(const ShuffleVectorSDNode &SV) {
1688 MVT VT = SV.getSimpleValueType(0);
1689 SmallVector<int, 8> MaskVec(SV.getMask().begin(), SV.getMask().end());
1690 ShuffleVectorSDNode::commuteMask(MaskVec);
1692 SDValue Op0 = SV.getOperand(0);
1693 SDValue Op1 = SV.getOperand(1);
1694 return getVectorShuffle(VT, SDLoc(&SV), Op1, Op0, &MaskVec[0]);
1697 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1698 SDValue Val, SDValue DTy,
1699 SDValue STy, SDValue Rnd, SDValue Sat,
1700 ISD::CvtCode Code) {
1701 // If the src and dest types are the same and the conversion is between
1702 // integer types of the same sign or two floats, no conversion is necessary.
1704 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1707 FoldingSetNodeID ID;
1708 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1709 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1711 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1712 return SDValue(E, 0);
1714 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1717 CSEMap.InsertNode(N, IP);
1719 return SDValue(N, 0);
1722 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1723 FoldingSetNodeID ID;
1724 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1725 ID.AddInteger(RegNo);
1727 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1728 return SDValue(E, 0);
1730 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1731 CSEMap.InsertNode(N, IP);
1733 return SDValue(N, 0);
1736 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1737 FoldingSetNodeID ID;
1738 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1739 ID.AddPointer(RegMask);
1741 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1742 return SDValue(E, 0);
1744 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1745 CSEMap.InsertNode(N, IP);
1747 return SDValue(N, 0);
1750 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1751 FoldingSetNodeID ID;
1752 SDValue Ops[] = { Root };
1753 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1754 ID.AddPointer(Label);
1756 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1757 return SDValue(E, 0);
1759 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1760 dl.getDebugLoc(), Root, Label);
1761 CSEMap.InsertNode(N, IP);
1763 return SDValue(N, 0);
1767 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1770 unsigned char TargetFlags) {
1771 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1773 FoldingSetNodeID ID;
1774 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1776 ID.AddInteger(Offset);
1777 ID.AddInteger(TargetFlags);
1779 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1780 return SDValue(E, 0);
1782 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1784 CSEMap.InsertNode(N, IP);
1786 return SDValue(N, 0);
1789 SDValue SelectionDAG::getSrcValue(const Value *V) {
1790 assert((!V || V->getType()->isPointerTy()) &&
1791 "SrcValue is not a pointer?");
1793 FoldingSetNodeID ID;
1794 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1798 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1799 return SDValue(E, 0);
1801 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1802 CSEMap.InsertNode(N, IP);
1804 return SDValue(N, 0);
1807 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1808 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1809 FoldingSetNodeID ID;
1810 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1814 if (SDNode *E = FindNodeOrInsertPos(ID, IP))
1815 return SDValue(E, 0);
1817 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1818 CSEMap.InsertNode(N, IP);
1820 return SDValue(N, 0);
1823 SDValue SelectionDAG::getBitcast(EVT VT, SDValue V) {
1824 if (VT == V.getValueType())
1827 return getNode(ISD::BITCAST, SDLoc(V), VT, V);
1830 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1831 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1832 unsigned SrcAS, unsigned DestAS) {
1833 SDValue Ops[] = {Ptr};
1834 FoldingSetNodeID ID;
1835 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1836 ID.AddInteger(SrcAS);
1837 ID.AddInteger(DestAS);
1840 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
1841 return SDValue(E, 0);
1843 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1845 VT, Ptr, SrcAS, DestAS);
1846 CSEMap.InsertNode(N, IP);
1848 return SDValue(N, 0);
1851 /// getShiftAmountOperand - Return the specified value casted to
1852 /// the target's desired shift amount type.
1853 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1854 EVT OpTy = Op.getValueType();
1855 EVT ShTy = TLI->getShiftAmountTy(LHSTy);
1856 if (OpTy == ShTy || OpTy.isVector()) return Op;
1858 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1859 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1862 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1863 /// specified value type.
1864 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1865 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1866 unsigned ByteSize = VT.getStoreSize();
1867 Type *Ty = VT.getTypeForEVT(*getContext());
1868 unsigned StackAlign =
1869 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1871 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1872 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1875 /// CreateStackTemporary - Create a stack temporary suitable for holding
1876 /// either of the specified value types.
1877 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1878 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1879 VT2.getStoreSizeInBits())/8;
1880 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1881 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1882 const DataLayout *TD = TLI->getDataLayout();
1883 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1884 TD->getPrefTypeAlignment(Ty2));
1886 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1887 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1888 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1891 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1892 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1893 // These setcc operations always fold.
1897 case ISD::SETFALSE2: return getConstant(0, dl, VT);
1899 case ISD::SETTRUE2: {
1900 TargetLowering::BooleanContent Cnt =
1901 TLI->getBooleanContents(N1->getValueType(0));
1903 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, dl,
1917 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1921 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1922 const APInt &C2 = N2C->getAPIntValue();
1923 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1924 const APInt &C1 = N1C->getAPIntValue();
1927 default: llvm_unreachable("Unknown integer setcc!");
1928 case ISD::SETEQ: return getConstant(C1 == C2, dl, VT);
1929 case ISD::SETNE: return getConstant(C1 != C2, dl, VT);
1930 case ISD::SETULT: return getConstant(C1.ult(C2), dl, VT);
1931 case ISD::SETUGT: return getConstant(C1.ugt(C2), dl, VT);
1932 case ISD::SETULE: return getConstant(C1.ule(C2), dl, VT);
1933 case ISD::SETUGE: return getConstant(C1.uge(C2), dl, VT);
1934 case ISD::SETLT: return getConstant(C1.slt(C2), dl, VT);
1935 case ISD::SETGT: return getConstant(C1.sgt(C2), dl, VT);
1936 case ISD::SETLE: return getConstant(C1.sle(C2), dl, VT);
1937 case ISD::SETGE: return getConstant(C1.sge(C2), dl, VT);
1941 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1942 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1943 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1946 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1947 return getUNDEF(VT);
1949 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, dl, VT);
1950 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1951 return getUNDEF(VT);
1953 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1954 R==APFloat::cmpLessThan, dl, VT);
1955 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1956 return getUNDEF(VT);
1958 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, dl, VT);
1959 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1960 return getUNDEF(VT);
1962 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, dl, VT);
1963 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1964 return getUNDEF(VT);
1966 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1967 R==APFloat::cmpEqual, dl, VT);
1968 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1969 return getUNDEF(VT);
1971 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1972 R==APFloat::cmpEqual, dl, VT);
1973 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, dl, VT);
1974 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, dl, VT);
1975 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1976 R==APFloat::cmpEqual, dl, VT);
1977 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, dl, VT);
1978 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1979 R==APFloat::cmpLessThan, dl, VT);
1980 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1981 R==APFloat::cmpUnordered, dl, VT);
1982 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, dl, VT);
1983 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, dl, VT);
1986 // Ensure that the constant occurs on the RHS.
1987 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1988 MVT CompVT = N1.getValueType().getSimpleVT();
1989 if (!TLI->isCondCodeLegal(SwappedCond, CompVT))
1992 return getSetCC(dl, VT, N2, N1, SwappedCond);
1996 // Could not fold it.
2000 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
2001 /// use this predicate to simplify operations downstream.
2002 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
2003 // This predicate is not safe for vector operations.
2004 if (Op.getValueType().isVector())
2007 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2008 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
2011 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
2012 /// this predicate to simplify operations downstream. Mask is known to be zero
2013 /// for bits that V cannot have.
2014 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
2015 unsigned Depth) const {
2016 APInt KnownZero, KnownOne;
2017 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2018 return (KnownZero & Mask) == Mask;
2021 /// Determine which bits of Op are known to be either zero or one and return
2022 /// them in the KnownZero/KnownOne bitsets.
2023 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
2024 APInt &KnownOne, unsigned Depth) const {
2025 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
2027 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
2029 return; // Limit search depth.
2031 APInt KnownZero2, KnownOne2;
2033 switch (Op.getOpcode()) {
2035 // We know all of the bits for a constant!
2036 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
2037 KnownZero = ~KnownOne;
2040 // If either the LHS or the RHS are Zero, the result is zero.
2041 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2042 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2044 // Output known-1 bits are only known if set in both the LHS & RHS.
2045 KnownOne &= KnownOne2;
2046 // Output known-0 are known to be clear if zero in either the LHS | RHS.
2047 KnownZero |= KnownZero2;
2050 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2051 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2053 // Output known-0 bits are only known if clear in both the LHS & RHS.
2054 KnownZero &= KnownZero2;
2055 // Output known-1 are known to be set if set in either the LHS | RHS.
2056 KnownOne |= KnownOne2;
2059 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2060 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2062 // Output known-0 bits are known if clear or set in both the LHS & RHS.
2063 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
2064 // Output known-1 are known to be set if set in only one of the LHS, RHS.
2065 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
2066 KnownZero = KnownZeroOut;
2070 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2071 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2073 // If low bits are zero in either operand, output low known-0 bits.
2074 // Also compute a conserative estimate for high known-0 bits.
2075 // More trickiness is possible, but this is sufficient for the
2076 // interesting case of alignment computation.
2077 KnownOne.clearAllBits();
2078 unsigned TrailZ = KnownZero.countTrailingOnes() +
2079 KnownZero2.countTrailingOnes();
2080 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
2081 KnownZero2.countLeadingOnes(),
2082 BitWidth) - BitWidth;
2084 TrailZ = std::min(TrailZ, BitWidth);
2085 LeadZ = std::min(LeadZ, BitWidth);
2086 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
2087 APInt::getHighBitsSet(BitWidth, LeadZ);
2091 // For the purposes of computing leading zeros we can conservatively
2092 // treat a udiv as a logical right shift by the power of 2 known to
2093 // be less than the denominator.
2094 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2095 unsigned LeadZ = KnownZero2.countLeadingOnes();
2097 KnownOne2.clearAllBits();
2098 KnownZero2.clearAllBits();
2099 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2100 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
2101 if (RHSUnknownLeadingOnes != BitWidth)
2102 LeadZ = std::min(BitWidth,
2103 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
2105 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
2109 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
2110 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2112 // Only known if known in both the LHS and RHS.
2113 KnownOne &= KnownOne2;
2114 KnownZero &= KnownZero2;
2116 case ISD::SELECT_CC:
2117 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
2118 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
2120 // Only known if known in both the LHS and RHS.
2121 KnownOne &= KnownOne2;
2122 KnownZero &= KnownZero2;
2130 if (Op.getResNo() != 1)
2132 // The boolean result conforms to getBooleanContents.
2133 // If we know the result of a setcc has the top bits zero, use this info.
2134 // We know that we have an integer-based boolean since these operations
2135 // are only available for integer.
2136 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2137 TargetLowering::ZeroOrOneBooleanContent &&
2139 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2142 // If we know the result of a setcc has the top bits zero, use this info.
2143 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2144 TargetLowering::ZeroOrOneBooleanContent &&
2146 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2149 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
2150 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2151 unsigned ShAmt = SA->getZExtValue();
2153 // If the shift count is an invalid immediate, don't do anything.
2154 if (ShAmt >= BitWidth)
2157 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2158 KnownZero <<= ShAmt;
2160 // low bits known zero.
2161 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
2165 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
2166 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2167 unsigned ShAmt = SA->getZExtValue();
2169 // If the shift count is an invalid immediate, don't do anything.
2170 if (ShAmt >= BitWidth)
2173 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2174 KnownZero = KnownZero.lshr(ShAmt);
2175 KnownOne = KnownOne.lshr(ShAmt);
2177 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2178 KnownZero |= HighBits; // High bits known zero.
2182 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2183 unsigned ShAmt = SA->getZExtValue();
2185 // If the shift count is an invalid immediate, don't do anything.
2186 if (ShAmt >= BitWidth)
2189 // If any of the demanded bits are produced by the sign extension, we also
2190 // demand the input sign bit.
2191 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
2193 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2194 KnownZero = KnownZero.lshr(ShAmt);
2195 KnownOne = KnownOne.lshr(ShAmt);
2197 // Handle the sign bits.
2198 APInt SignBit = APInt::getSignBit(BitWidth);
2199 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
2201 if (KnownZero.intersects(SignBit)) {
2202 KnownZero |= HighBits; // New bits are known zero.
2203 } else if (KnownOne.intersects(SignBit)) {
2204 KnownOne |= HighBits; // New bits are known one.
2208 case ISD::SIGN_EXTEND_INREG: {
2209 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2210 unsigned EBits = EVT.getScalarType().getSizeInBits();
2212 // Sign extension. Compute the demanded bits in the result that are not
2213 // present in the input.
2214 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2216 APInt InSignBit = APInt::getSignBit(EBits);
2217 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2219 // If the sign extended bits are demanded, we know that the sign
2221 InSignBit = InSignBit.zext(BitWidth);
2222 if (NewBits.getBoolValue())
2223 InputDemandedBits |= InSignBit;
2225 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2226 KnownOne &= InputDemandedBits;
2227 KnownZero &= InputDemandedBits;
2229 // If the sign bit of the input is known set or clear, then we know the
2230 // top bits of the result.
2231 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2232 KnownZero |= NewBits;
2233 KnownOne &= ~NewBits;
2234 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2235 KnownOne |= NewBits;
2236 KnownZero &= ~NewBits;
2237 } else { // Input sign bit unknown
2238 KnownZero &= ~NewBits;
2239 KnownOne &= ~NewBits;
2244 case ISD::CTTZ_ZERO_UNDEF:
2246 case ISD::CTLZ_ZERO_UNDEF:
2248 unsigned LowBits = Log2_32(BitWidth)+1;
2249 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2250 KnownOne.clearAllBits();
2254 LoadSDNode *LD = cast<LoadSDNode>(Op);
2255 // If this is a ZEXTLoad and we are looking at the loaded value.
2256 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2257 EVT VT = LD->getMemoryVT();
2258 unsigned MemBits = VT.getScalarType().getSizeInBits();
2259 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2260 } else if (const MDNode *Ranges = LD->getRanges()) {
2261 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero);
2265 case ISD::ZERO_EXTEND: {
2266 EVT InVT = Op.getOperand(0).getValueType();
2267 unsigned InBits = InVT.getScalarType().getSizeInBits();
2268 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2269 KnownZero = KnownZero.trunc(InBits);
2270 KnownOne = KnownOne.trunc(InBits);
2271 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2272 KnownZero = KnownZero.zext(BitWidth);
2273 KnownOne = KnownOne.zext(BitWidth);
2274 KnownZero |= NewBits;
2277 case ISD::SIGN_EXTEND: {
2278 EVT InVT = Op.getOperand(0).getValueType();
2279 unsigned InBits = InVT.getScalarType().getSizeInBits();
2280 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2282 KnownZero = KnownZero.trunc(InBits);
2283 KnownOne = KnownOne.trunc(InBits);
2284 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2286 // Note if the sign bit is known to be zero or one.
2287 bool SignBitKnownZero = KnownZero.isNegative();
2288 bool SignBitKnownOne = KnownOne.isNegative();
2290 KnownZero = KnownZero.zext(BitWidth);
2291 KnownOne = KnownOne.zext(BitWidth);
2293 // If the sign bit is known zero or one, the top bits match.
2294 if (SignBitKnownZero)
2295 KnownZero |= NewBits;
2296 else if (SignBitKnownOne)
2297 KnownOne |= NewBits;
2300 case ISD::ANY_EXTEND: {
2301 EVT InVT = Op.getOperand(0).getValueType();
2302 unsigned InBits = InVT.getScalarType().getSizeInBits();
2303 KnownZero = KnownZero.trunc(InBits);
2304 KnownOne = KnownOne.trunc(InBits);
2305 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2306 KnownZero = KnownZero.zext(BitWidth);
2307 KnownOne = KnownOne.zext(BitWidth);
2310 case ISD::TRUNCATE: {
2311 EVT InVT = Op.getOperand(0).getValueType();
2312 unsigned InBits = InVT.getScalarType().getSizeInBits();
2313 KnownZero = KnownZero.zext(InBits);
2314 KnownOne = KnownOne.zext(InBits);
2315 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2316 KnownZero = KnownZero.trunc(BitWidth);
2317 KnownOne = KnownOne.trunc(BitWidth);
2320 case ISD::AssertZext: {
2321 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2322 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2323 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2324 KnownZero |= (~InMask);
2325 KnownOne &= (~KnownZero);
2329 // All bits are zero except the low bit.
2330 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2334 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2335 // We know that the top bits of C-X are clear if X contains less bits
2336 // than C (i.e. no wrap-around can happen). For example, 20-X is
2337 // positive if we can prove that X is >= 0 and < 16.
2338 if (CLHS->getAPIntValue().isNonNegative()) {
2339 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2340 // NLZ can't be BitWidth with no sign bit
2341 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2342 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2344 // If all of the MaskV bits are known to be zero, then we know the
2345 // output top bits are zero, because we now know that the output is
2347 if ((KnownZero2 & MaskV) == MaskV) {
2348 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2349 // Top bits known zero.
2350 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2358 // Output known-0 bits are known if clear or set in both the low clear bits
2359 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2360 // low 3 bits clear.
2361 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2362 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2364 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2365 KnownZeroOut = std::min(KnownZeroOut,
2366 KnownZero2.countTrailingOnes());
2368 if (Op.getOpcode() == ISD::ADD) {
2369 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2373 // With ADDE, a carry bit may be added in, so we can only use this
2374 // information if we know (at least) that the low two bits are clear. We
2375 // then return to the caller that the low bit is unknown but that other bits
2377 if (KnownZeroOut >= 2) // ADDE
2378 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2382 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2383 const APInt &RA = Rem->getAPIntValue().abs();
2384 if (RA.isPowerOf2()) {
2385 APInt LowBits = RA - 1;
2386 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2388 // The low bits of the first operand are unchanged by the srem.
2389 KnownZero = KnownZero2 & LowBits;
2390 KnownOne = KnownOne2 & LowBits;
2392 // If the first operand is non-negative or has all low bits zero, then
2393 // the upper bits are all zero.
2394 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2395 KnownZero |= ~LowBits;
2397 // If the first operand is negative and not all low bits are zero, then
2398 // the upper bits are all one.
2399 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2400 KnownOne |= ~LowBits;
2401 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2406 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2407 const APInt &RA = Rem->getAPIntValue();
2408 if (RA.isPowerOf2()) {
2409 APInt LowBits = (RA - 1);
2410 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2412 // The upper bits are all zero, the lower ones are unchanged.
2413 KnownZero = KnownZero2 | ~LowBits;
2414 KnownOne = KnownOne2 & LowBits;
2419 // Since the result is less than or equal to either operand, any leading
2420 // zero bits in either operand must also exist in the result.
2421 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2422 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2424 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2425 KnownZero2.countLeadingOnes());
2426 KnownOne.clearAllBits();
2427 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2430 case ISD::EXTRACT_ELEMENT: {
2431 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2432 const unsigned Index =
2433 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2434 const unsigned BitWidth = Op.getValueType().getSizeInBits();
2436 // Remove low part of known bits mask
2437 KnownZero = KnownZero.getHiBits(KnownZero.getBitWidth() - Index * BitWidth);
2438 KnownOne = KnownOne.getHiBits(KnownOne.getBitWidth() - Index * BitWidth);
2440 // Remove high part of known bit mask
2441 KnownZero = KnownZero.trunc(BitWidth);
2442 KnownOne = KnownOne.trunc(BitWidth);
2449 APInt Op0Zero, Op0One;
2450 APInt Op1Zero, Op1One;
2451 computeKnownBits(Op.getOperand(0), Op0Zero, Op0One, Depth);
2452 computeKnownBits(Op.getOperand(1), Op1Zero, Op1One, Depth);
2454 KnownZero = Op0Zero & Op1Zero;
2455 KnownOne = Op0One & Op1One;
2458 case ISD::FrameIndex:
2459 case ISD::TargetFrameIndex:
2460 if (unsigned Align = InferPtrAlignment(Op)) {
2461 // The low bits are known zero if the pointer is aligned.
2462 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2468 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2471 case ISD::INTRINSIC_WO_CHAIN:
2472 case ISD::INTRINSIC_W_CHAIN:
2473 case ISD::INTRINSIC_VOID:
2474 // Allow the target to implement this method for its nodes.
2475 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2479 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2482 /// ComputeNumSignBits - Return the number of times the sign bit of the
2483 /// register is replicated into the other bits. We know that at least 1 bit
2484 /// is always equal to the sign bit (itself), but other cases can give us
2485 /// information. For example, immediately after an "SRA X, 2", we know that
2486 /// the top 3 bits are all equal to each other, so we return 3.
2487 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2488 EVT VT = Op.getValueType();
2489 assert(VT.isInteger() && "Invalid VT!");
2490 unsigned VTBits = VT.getScalarType().getSizeInBits();
2492 unsigned FirstAnswer = 1;
2495 return 1; // Limit search depth.
2497 switch (Op.getOpcode()) {
2499 case ISD::AssertSext:
2500 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2501 return VTBits-Tmp+1;
2502 case ISD::AssertZext:
2503 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2506 case ISD::Constant: {
2507 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2508 return Val.getNumSignBits();
2511 case ISD::SIGN_EXTEND:
2513 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2514 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2516 case ISD::SIGN_EXTEND_INREG:
2517 // Max of the input and what this extends.
2519 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2522 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2523 return std::max(Tmp, Tmp2);
2526 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2527 // SRA X, C -> adds C sign bits.
2528 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2529 Tmp += C->getZExtValue();
2530 if (Tmp > VTBits) Tmp = VTBits;
2534 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2535 // shl destroys sign bits.
2536 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2537 if (C->getZExtValue() >= VTBits || // Bad shift.
2538 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2539 return Tmp - C->getZExtValue();
2544 case ISD::XOR: // NOT is handled here.
2545 // Logical binary ops preserve the number of sign bits at the worst.
2546 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2548 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2549 FirstAnswer = std::min(Tmp, Tmp2);
2550 // We computed what we know about the sign bits as our first
2551 // answer. Now proceed to the generic code that uses
2552 // computeKnownBits, and pick whichever answer is better.
2557 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2558 if (Tmp == 1) return 1; // Early out.
2559 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2560 return std::min(Tmp, Tmp2);
2565 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth + 1);
2567 return 1; // Early out.
2568 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth + 1);
2569 return std::min(Tmp, Tmp2);
2576 if (Op.getResNo() != 1)
2578 // The boolean result conforms to getBooleanContents. Fall through.
2579 // If setcc returns 0/-1, all bits are sign bits.
2580 // We know that we have an integer-based boolean since these operations
2581 // are only available for integer.
2582 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) ==
2583 TargetLowering::ZeroOrNegativeOneBooleanContent)
2587 // If setcc returns 0/-1, all bits are sign bits.
2588 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
2589 TargetLowering::ZeroOrNegativeOneBooleanContent)
2594 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2595 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2597 // Handle rotate right by N like a rotate left by 32-N.
2598 if (Op.getOpcode() == ISD::ROTR)
2599 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2601 // If we aren't rotating out all of the known-in sign bits, return the
2602 // number that are left. This handles rotl(sext(x), 1) for example.
2603 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2604 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2608 // Add can have at most one carry bit. Thus we know that the output
2609 // is, at worst, one more bit than the inputs.
2610 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2611 if (Tmp == 1) return 1; // Early out.
2613 // Special case decrementing a value (ADD X, -1):
2614 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2615 if (CRHS->isAllOnesValue()) {
2616 APInt KnownZero, KnownOne;
2617 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2619 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2621 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2624 // If we are subtracting one from a positive number, there is no carry
2625 // out of the result.
2626 if (KnownZero.isNegative())
2630 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2631 if (Tmp2 == 1) return 1;
2632 return std::min(Tmp, Tmp2)-1;
2635 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2636 if (Tmp2 == 1) return 1;
2639 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2640 if (CLHS->isNullValue()) {
2641 APInt KnownZero, KnownOne;
2642 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2643 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2645 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2648 // If the input is known to be positive (the sign bit is known clear),
2649 // the output of the NEG has the same number of sign bits as the input.
2650 if (KnownZero.isNegative())
2653 // Otherwise, we treat this like a SUB.
2656 // Sub can have at most one carry bit. Thus we know that the output
2657 // is, at worst, one more bit than the inputs.
2658 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2659 if (Tmp == 1) return 1; // Early out.
2660 return std::min(Tmp, Tmp2)-1;
2662 // FIXME: it's tricky to do anything useful for this, but it is an important
2663 // case for targets like X86.
2665 case ISD::EXTRACT_ELEMENT: {
2666 const int KnownSign = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2667 const int BitWidth = Op.getValueType().getSizeInBits();
2669 Op.getOperand(0).getValueType().getSizeInBits() / BitWidth;
2671 // Get reverse index (starting from 1), Op1 value indexes elements from
2672 // little end. Sign starts at big end.
2673 const int rIndex = Items - 1 -
2674 cast<ConstantSDNode>(Op.getOperand(1))->getZExtValue();
2676 // If the sign portion ends in our element the substraction gives correct
2677 // result. Otherwise it gives either negative or > bitwidth result
2678 return std::max(std::min(KnownSign - rIndex * BitWidth, BitWidth), 0);
2682 // If we are looking at the loaded value of the SDNode.
2683 if (Op.getResNo() == 0) {
2684 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2685 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2686 unsigned ExtType = LD->getExtensionType();
2689 case ISD::SEXTLOAD: // '17' bits known
2690 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2691 return VTBits-Tmp+1;
2692 case ISD::ZEXTLOAD: // '16' bits known
2693 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2699 // Allow the target to implement this method for its nodes.
2700 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2701 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2702 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2703 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2704 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2705 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2708 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2709 // use this information.
2710 APInt KnownZero, KnownOne;
2711 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2714 if (KnownZero.isNegative()) { // sign bit is 0
2716 } else if (KnownOne.isNegative()) { // sign bit is 1;
2723 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2724 // the number of identical bits in the top of the input value.
2726 Mask <<= Mask.getBitWidth()-VTBits;
2727 // Return # leading zeros. We use 'min' here in case Val was zero before
2728 // shifting. We don't want to return '64' as for an i32 "0".
2729 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2732 /// isBaseWithConstantOffset - Return true if the specified operand is an
2733 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2734 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2735 /// semantics as an ADD. This handles the equivalence:
2736 /// X|Cst == X+Cst iff X&Cst = 0.
2737 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2738 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2739 !isa<ConstantSDNode>(Op.getOperand(1)))
2742 if (Op.getOpcode() == ISD::OR &&
2743 !MaskedValueIsZero(Op.getOperand(0),
2744 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2751 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2752 // If we're told that NaNs won't happen, assume they won't.
2753 if (getTarget().Options.NoNaNsFPMath)
2756 // If the value is a constant, we can obviously see if it is a NaN or not.
2757 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2758 return !C->getValueAPF().isNaN();
2760 // TODO: Recognize more cases here.
2765 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2766 // If the value is a constant, we can obviously see if it is a zero or not.
2767 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2768 return !C->isZero();
2770 // TODO: Recognize more cases here.
2771 switch (Op.getOpcode()) {
2774 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2775 return !C->isNullValue();
2782 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2783 // Check the obvious case.
2784 if (A == B) return true;
2786 // For for negative and positive zero.
2787 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2788 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2789 if (CA->isZero() && CB->isZero()) return true;
2791 // Otherwise they may not be equal.
2795 /// getNode - Gets or creates the specified node.
2797 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2798 FoldingSetNodeID ID;
2799 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2801 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
2802 return SDValue(E, 0);
2804 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2805 DL.getDebugLoc(), getVTList(VT));
2806 CSEMap.InsertNode(N, IP);
2809 return SDValue(N, 0);
2812 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2813 EVT VT, SDValue Operand) {
2814 // Constant fold unary operations with an integer constant operand. Even
2815 // opaque constant will be folded, because the folding of unary operations
2816 // doesn't create new constants with different values. Nevertheless, the
2817 // opaque flag is preserved during folding to prevent future folding with
2819 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2820 const APInt &Val = C->getAPIntValue();
2823 case ISD::SIGN_EXTEND:
2824 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), DL, VT,
2825 C->isTargetOpcode(), C->isOpaque());
2826 case ISD::ANY_EXTEND:
2827 case ISD::ZERO_EXTEND:
2829 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), DL, VT,
2830 C->isTargetOpcode(), C->isOpaque());
2831 case ISD::UINT_TO_FP:
2832 case ISD::SINT_TO_FP: {
2833 APFloat apf(EVTToAPFloatSemantics(VT),
2834 APInt::getNullValue(VT.getSizeInBits()));
2835 (void)apf.convertFromAPInt(Val,
2836 Opcode==ISD::SINT_TO_FP,
2837 APFloat::rmNearestTiesToEven);
2838 return getConstantFP(apf, DL, VT);
2841 if (VT == MVT::f16 && C->getValueType(0) == MVT::i16)
2842 return getConstantFP(APFloat(APFloat::IEEEhalf, Val), DL, VT);
2843 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2844 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), DL, VT);
2845 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2846 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), DL, VT);
2849 return getConstant(Val.byteSwap(), DL, VT, C->isTargetOpcode(),
2852 return getConstant(Val.countPopulation(), DL, VT, C->isTargetOpcode(),
2855 case ISD::CTLZ_ZERO_UNDEF:
2856 return getConstant(Val.countLeadingZeros(), DL, VT, C->isTargetOpcode(),
2859 case ISD::CTTZ_ZERO_UNDEF:
2860 return getConstant(Val.countTrailingZeros(), DL, VT, C->isTargetOpcode(),
2865 // Constant fold unary operations with a floating point constant operand.
2866 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2867 APFloat V = C->getValueAPF(); // make copy
2871 return getConstantFP(V, DL, VT);
2874 return getConstantFP(V, DL, VT);
2876 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2877 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2878 return getConstantFP(V, DL, VT);
2882 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2883 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2884 return getConstantFP(V, DL, VT);
2888 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2889 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2890 return getConstantFP(V, DL, VT);
2893 case ISD::FP_EXTEND: {
2895 // This can return overflow, underflow, or inexact; we don't care.
2896 // FIXME need to be more flexible about rounding mode.
2897 (void)V.convert(EVTToAPFloatSemantics(VT),
2898 APFloat::rmNearestTiesToEven, &ignored);
2899 return getConstantFP(V, DL, VT);
2901 case ISD::FP_TO_SINT:
2902 case ISD::FP_TO_UINT: {
2905 static_assert(integerPartWidth >= 64, "APFloat parts too small!");
2906 // FIXME need to be more flexible about rounding mode.
2907 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2908 Opcode==ISD::FP_TO_SINT,
2909 APFloat::rmTowardZero, &ignored);
2910 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2912 APInt api(VT.getSizeInBits(), x);
2913 return getConstant(api, DL, VT);
2916 if (VT == MVT::i16 && C->getValueType(0) == MVT::f16)
2917 return getConstant((uint16_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2918 else if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2919 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), DL, VT);
2920 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2921 return getConstant(V.bitcastToAPInt().getZExtValue(), DL, VT);
2926 // Constant fold unary operations with a vector integer or float operand.
2927 if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(Operand.getNode())) {
2928 if (BV->isConstant()) {
2931 // FIXME: Entirely reasonable to perform folding of other unary
2932 // operations here as the need arises.
2939 case ISD::FP_EXTEND:
2940 case ISD::FP_TO_SINT:
2941 case ISD::FP_TO_UINT:
2943 case ISD::UINT_TO_FP:
2944 case ISD::SINT_TO_FP:
2947 case ISD::CTLZ_ZERO_UNDEF:
2949 case ISD::CTTZ_ZERO_UNDEF:
2951 EVT SVT = VT.getScalarType();
2952 EVT InVT = BV->getValueType(0);
2953 EVT InSVT = InVT.getScalarType();
2955 // Find legal integer scalar type for constant promotion and
2956 // ensure that its scalar size is at least as large as source.
2958 if (SVT.isInteger()) {
2959 LegalSVT = TLI->getTypeToTransformTo(*getContext(), SVT);
2960 if (LegalSVT.bitsLT(SVT)) break;
2963 // Let the above scalar folding handle the folding of each element.
2964 SmallVector<SDValue, 8> Ops;
2965 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
2966 SDValue OpN = BV->getOperand(i);
2967 EVT OpVT = OpN.getValueType();
2969 // Build vector (integer) scalar operands may need implicit
2970 // truncation - do this before constant folding.
2971 if (OpVT.isInteger() && OpVT.bitsGT(InSVT))
2972 OpN = getNode(ISD::TRUNCATE, DL, InSVT, OpN);
2974 OpN = getNode(Opcode, DL, SVT, OpN);
2976 // Legalize the (integer) scalar constant if necessary.
2977 if (LegalSVT != SVT)
2978 OpN = getNode(ISD::ANY_EXTEND, DL, LegalSVT, OpN);
2980 if (OpN.getOpcode() != ISD::UNDEF &&
2981 OpN.getOpcode() != ISD::Constant &&
2982 OpN.getOpcode() != ISD::ConstantFP)
2986 if (Ops.size() == VT.getVectorNumElements())
2987 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
2994 unsigned OpOpcode = Operand.getNode()->getOpcode();
2996 case ISD::TokenFactor:
2997 case ISD::MERGE_VALUES:
2998 case ISD::CONCAT_VECTORS:
2999 return Operand; // Factor, merge or concat of one node? No need.
3000 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
3001 case ISD::FP_EXTEND:
3002 assert(VT.isFloatingPoint() &&
3003 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
3004 if (Operand.getValueType() == VT) return Operand; // noop conversion.
3005 assert((!VT.isVector() ||
3006 VT.getVectorNumElements() ==
3007 Operand.getValueType().getVectorNumElements()) &&
3008 "Vector element count mismatch!");
3009 if (Operand.getOpcode() == ISD::UNDEF)
3010 return getUNDEF(VT);
3012 case ISD::SIGN_EXTEND:
3013 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3014 "Invalid SIGN_EXTEND!");
3015 if (Operand.getValueType() == VT) return Operand; // noop extension
3016 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3017 "Invalid sext node, dst < src!");
3018 assert((!VT.isVector() ||
3019 VT.getVectorNumElements() ==
3020 Operand.getValueType().getVectorNumElements()) &&
3021 "Vector element count mismatch!");
3022 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
3023 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3024 else if (OpOpcode == ISD::UNDEF)
3025 // sext(undef) = 0, because the top bits will all be the same.
3026 return getConstant(0, DL, VT);
3028 case ISD::ZERO_EXTEND:
3029 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3030 "Invalid ZERO_EXTEND!");
3031 if (Operand.getValueType() == VT) return Operand; // noop extension
3032 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3033 "Invalid zext node, dst < src!");
3034 assert((!VT.isVector() ||
3035 VT.getVectorNumElements() ==
3036 Operand.getValueType().getVectorNumElements()) &&
3037 "Vector element count mismatch!");
3038 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
3039 return getNode(ISD::ZERO_EXTEND, DL, VT,
3040 Operand.getNode()->getOperand(0));
3041 else if (OpOpcode == ISD::UNDEF)
3042 // zext(undef) = 0, because the top bits will be zero.
3043 return getConstant(0, DL, VT);
3045 case ISD::ANY_EXTEND:
3046 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3047 "Invalid ANY_EXTEND!");
3048 if (Operand.getValueType() == VT) return Operand; // noop extension
3049 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
3050 "Invalid anyext node, dst < src!");
3051 assert((!VT.isVector() ||
3052 VT.getVectorNumElements() ==
3053 Operand.getValueType().getVectorNumElements()) &&
3054 "Vector element count mismatch!");
3056 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3057 OpOpcode == ISD::ANY_EXTEND)
3058 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
3059 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3060 else if (OpOpcode == ISD::UNDEF)
3061 return getUNDEF(VT);
3063 // (ext (trunx x)) -> x
3064 if (OpOpcode == ISD::TRUNCATE) {
3065 SDValue OpOp = Operand.getNode()->getOperand(0);
3066 if (OpOp.getValueType() == VT)
3071 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
3072 "Invalid TRUNCATE!");
3073 if (Operand.getValueType() == VT) return Operand; // noop truncate
3074 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
3075 "Invalid truncate node, src < dst!");
3076 assert((!VT.isVector() ||
3077 VT.getVectorNumElements() ==
3078 Operand.getValueType().getVectorNumElements()) &&
3079 "Vector element count mismatch!");
3080 if (OpOpcode == ISD::TRUNCATE)
3081 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3082 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
3083 OpOpcode == ISD::ANY_EXTEND) {
3084 // If the source is smaller than the dest, we still need an extend.
3085 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
3086 .bitsLT(VT.getScalarType()))
3087 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
3088 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
3089 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
3090 return Operand.getNode()->getOperand(0);
3092 if (OpOpcode == ISD::UNDEF)
3093 return getUNDEF(VT);
3096 assert(VT.isInteger() && VT == Operand.getValueType() &&
3098 assert((VT.getScalarSizeInBits() % 16 == 0) &&
3099 "BSWAP types must be a multiple of 16 bits!");
3100 if (OpOpcode == ISD::UNDEF)
3101 return getUNDEF(VT);
3104 // Basic sanity checking.
3105 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
3106 && "Cannot BITCAST between types of different sizes!");
3107 if (VT == Operand.getValueType()) return Operand; // noop conversion.
3108 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
3109 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
3110 if (OpOpcode == ISD::UNDEF)
3111 return getUNDEF(VT);
3113 case ISD::SCALAR_TO_VECTOR:
3114 assert(VT.isVector() && !Operand.getValueType().isVector() &&
3115 (VT.getVectorElementType() == Operand.getValueType() ||
3116 (VT.getVectorElementType().isInteger() &&
3117 Operand.getValueType().isInteger() &&
3118 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
3119 "Illegal SCALAR_TO_VECTOR node!");
3120 if (OpOpcode == ISD::UNDEF)
3121 return getUNDEF(VT);
3122 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
3123 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
3124 isa<ConstantSDNode>(Operand.getOperand(1)) &&
3125 Operand.getConstantOperandVal(1) == 0 &&
3126 Operand.getOperand(0).getValueType() == VT)
3127 return Operand.getOperand(0);
3130 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
3131 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
3132 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
3133 Operand.getNode()->getOperand(0));
3134 if (OpOpcode == ISD::FNEG) // --X -> X
3135 return Operand.getNode()->getOperand(0);
3138 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
3139 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
3144 SDVTList VTs = getVTList(VT);
3145 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
3146 FoldingSetNodeID ID;
3147 SDValue Ops[1] = { Operand };
3148 AddNodeIDNode(ID, Opcode, VTs, Ops);
3150 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3151 return SDValue(E, 0);
3153 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3154 DL.getDebugLoc(), VTs, Operand);
3155 CSEMap.InsertNode(N, IP);
3157 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
3158 DL.getDebugLoc(), VTs, Operand);
3162 return SDValue(N, 0);
3165 static std::pair<APInt, bool> FoldValue(unsigned Opcode, const APInt &C1,
3168 case ISD::ADD: return std::make_pair(C1 + C2, true);
3169 case ISD::SUB: return std::make_pair(C1 - C2, true);
3170 case ISD::MUL: return std::make_pair(C1 * C2, true);
3171 case ISD::AND: return std::make_pair(C1 & C2, true);
3172 case ISD::OR: return std::make_pair(C1 | C2, true);
3173 case ISD::XOR: return std::make_pair(C1 ^ C2, true);
3174 case ISD::SHL: return std::make_pair(C1 << C2, true);
3175 case ISD::SRL: return std::make_pair(C1.lshr(C2), true);
3176 case ISD::SRA: return std::make_pair(C1.ashr(C2), true);
3177 case ISD::ROTL: return std::make_pair(C1.rotl(C2), true);
3178 case ISD::ROTR: return std::make_pair(C1.rotr(C2), true);
3180 if (!C2.getBoolValue())
3182 return std::make_pair(C1.udiv(C2), true);
3184 if (!C2.getBoolValue())
3186 return std::make_pair(C1.urem(C2), true);
3188 if (!C2.getBoolValue())
3190 return std::make_pair(C1.sdiv(C2), true);
3192 if (!C2.getBoolValue())
3194 return std::make_pair(C1.srem(C2), true);
3196 return std::make_pair(APInt(1, 0), false);
3199 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3200 const ConstantSDNode *Cst1,
3201 const ConstantSDNode *Cst2) {
3202 if (Cst1->isOpaque() || Cst2->isOpaque())
3205 std::pair<APInt, bool> Folded = FoldValue(Opcode, Cst1->getAPIntValue(),
3206 Cst2->getAPIntValue());
3209 return getConstant(Folded.first, DL, VT);
3212 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
3213 SDNode *Cst1, SDNode *Cst2) {
3214 // If the opcode is a target-specific ISD node, there's nothing we can
3215 // do here and the operand rules may not line up with the below, so
3217 if (Opcode >= ISD::BUILTIN_OP_END)
3220 // Handle the case of two scalars.
3221 if (const ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1)) {
3222 if (const ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2)) {
3223 if (SDValue Folded =
3224 FoldConstantArithmetic(Opcode, DL, VT, Scalar1, Scalar2)) {
3227 SmallVector<SDValue, 4> Outputs;
3228 // We may have a vector type but a scalar result. Create a splat.
3229 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3230 // Build a big vector out of the scalar elements we generated.
3231 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3238 // For vectors extract each constant element into Inputs so we can constant
3239 // fold them individually.
3240 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
3241 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
3245 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
3247 EVT SVT = VT.getScalarType();
3248 SmallVector<SDValue, 4> Outputs;
3249 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
3250 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
3251 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
3252 if (!V1 || !V2) // Not a constant, bail.
3255 if (V1->isOpaque() || V2->isOpaque())
3258 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
3259 // FIXME: This is valid and could be handled by truncating the APInts.
3260 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
3263 // Fold one vector element.
3264 std::pair<APInt, bool> Folded = FoldValue(Opcode, V1->getAPIntValue(),
3265 V2->getAPIntValue());
3268 Outputs.push_back(getConstant(Folded.first, DL, SVT));
3271 assert(VT.getVectorNumElements() == Outputs.size() &&
3272 "Vector size mismatch!");
3274 // We may have a vector type but a scalar result. Create a splat.
3275 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
3277 // Build a big vector out of the scalar elements we generated.
3278 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
3281 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
3282 SDValue N2, const SDNodeFlags *Flags) {
3283 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3284 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
3287 case ISD::TokenFactor:
3288 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
3289 N2.getValueType() == MVT::Other && "Invalid token factor!");
3290 // Fold trivial token factors.
3291 if (N1.getOpcode() == ISD::EntryToken) return N2;
3292 if (N2.getOpcode() == ISD::EntryToken) return N1;
3293 if (N1 == N2) return N1;
3295 case ISD::CONCAT_VECTORS:
3296 // Concat of UNDEFs is UNDEF.
3297 if (N1.getOpcode() == ISD::UNDEF &&
3298 N2.getOpcode() == ISD::UNDEF)
3299 return getUNDEF(VT);
3301 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3302 // one big BUILD_VECTOR.
3303 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3304 N2.getOpcode() == ISD::BUILD_VECTOR) {
3305 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3306 N1.getNode()->op_end());
3307 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3309 // BUILD_VECTOR requires all inputs to be of the same type, find the
3310 // maximum type and extend them all.
3311 EVT SVT = VT.getScalarType();
3312 for (SDValue Op : Elts)
3313 SVT = (SVT.bitsLT(Op.getValueType()) ? Op.getValueType() : SVT);
3314 if (SVT.bitsGT(VT.getScalarType()))
3315 for (SDValue &Op : Elts)
3316 Op = TLI->isZExtFree(Op.getValueType(), SVT)
3317 ? getZExtOrTrunc(Op, DL, SVT)
3318 : getSExtOrTrunc(Op, DL, SVT);
3320 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3324 assert(VT.isInteger() && "This operator does not apply to FP types!");
3325 assert(N1.getValueType() == N2.getValueType() &&
3326 N1.getValueType() == VT && "Binary operator types must match!");
3327 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
3328 // worth handling here.
3329 if (N2C && N2C->isNullValue())
3331 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
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!");
3341 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
3342 // it's worth handling here.
3343 if (N2C && N2C->isNullValue())
3353 assert(VT.isInteger() && "This operator does not apply to FP types!");
3354 assert(N1.getValueType() == N2.getValueType() &&
3355 N1.getValueType() == VT && "Binary operator types must match!");
3362 if (getTarget().Options.UnsafeFPMath) {
3363 if (Opcode == ISD::FADD) {
3365 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3366 if (CFP->getValueAPF().isZero())
3369 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3370 if (CFP->getValueAPF().isZero())
3372 } else if (Opcode == ISD::FSUB) {
3374 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3375 if (CFP->getValueAPF().isZero())
3377 } else if (Opcode == ISD::FMUL) {
3378 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3381 // If the first operand isn't the constant, try the second
3383 CFP = dyn_cast<ConstantFPSDNode>(N2);
3390 return SDValue(CFP,0);
3392 if (CFP->isExactlyValue(1.0))
3397 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3398 assert(N1.getValueType() == N2.getValueType() &&
3399 N1.getValueType() == VT && "Binary operator types must match!");
3401 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3402 assert(N1.getValueType() == VT &&
3403 N1.getValueType().isFloatingPoint() &&
3404 N2.getValueType().isFloatingPoint() &&
3405 "Invalid FCOPYSIGN!");
3412 assert(VT == N1.getValueType() &&
3413 "Shift operators return type must be the same as their first arg");
3414 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3415 "Shifts only work on integers");
3416 assert((!VT.isVector() || VT == N2.getValueType()) &&
3417 "Vector shift amounts must be in the same as their first arg");
3418 // Verify that the shift amount VT is bit enough to hold valid shift
3419 // amounts. This catches things like trying to shift an i1024 value by an
3420 // i8, which is easy to fall into in generic code that uses
3421 // TLI.getShiftAmount().
3422 assert(N2.getValueType().getSizeInBits() >=
3423 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3424 "Invalid use of small shift amount with oversized value!");
3426 // Always fold shifts of i1 values so the code generator doesn't need to
3427 // handle them. Since we know the size of the shift has to be less than the
3428 // size of the value, the shift/rotate count is guaranteed to be zero.
3431 if (N2C && N2C->isNullValue())
3434 case ISD::FP_ROUND_INREG: {
3435 EVT EVT = cast<VTSDNode>(N2)->getVT();
3436 assert(VT == N1.getValueType() && "Not an inreg round!");
3437 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3438 "Cannot FP_ROUND_INREG integer types");
3439 assert(EVT.isVector() == VT.isVector() &&
3440 "FP_ROUND_INREG type should be vector iff the operand "
3442 assert((!EVT.isVector() ||
3443 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3444 "Vector element counts must match in FP_ROUND_INREG");
3445 assert(EVT.bitsLE(VT) && "Not rounding down!");
3447 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3451 assert(VT.isFloatingPoint() &&
3452 N1.getValueType().isFloatingPoint() &&
3453 VT.bitsLE(N1.getValueType()) &&
3454 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3455 if (N1.getValueType() == VT) return N1; // noop conversion.
3457 case ISD::AssertSext:
3458 case ISD::AssertZext: {
3459 EVT EVT = cast<VTSDNode>(N2)->getVT();
3460 assert(VT == N1.getValueType() && "Not an inreg extend!");
3461 assert(VT.isInteger() && EVT.isInteger() &&
3462 "Cannot *_EXTEND_INREG FP types");
3463 assert(!EVT.isVector() &&
3464 "AssertSExt/AssertZExt type should be the vector element type "
3465 "rather than the vector type!");
3466 assert(EVT.bitsLE(VT) && "Not extending!");
3467 if (VT == EVT) return N1; // noop assertion.
3470 case ISD::SIGN_EXTEND_INREG: {
3471 EVT EVT = cast<VTSDNode>(N2)->getVT();
3472 assert(VT == N1.getValueType() && "Not an inreg extend!");
3473 assert(VT.isInteger() && EVT.isInteger() &&
3474 "Cannot *_EXTEND_INREG FP types");
3475 assert(EVT.isVector() == VT.isVector() &&
3476 "SIGN_EXTEND_INREG type should be vector iff the operand "
3478 assert((!EVT.isVector() ||
3479 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3480 "Vector element counts must match in SIGN_EXTEND_INREG");
3481 assert(EVT.bitsLE(VT) && "Not extending!");
3482 if (EVT == VT) return N1; // Not actually extending
3484 auto SignExtendInReg = [&](APInt Val) {
3485 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3486 Val <<= Val.getBitWidth() - FromBits;
3487 Val = Val.ashr(Val.getBitWidth() - FromBits);
3488 return getConstant(Val, DL, VT.getScalarType());
3492 APInt Val = N1C->getAPIntValue();
3493 return SignExtendInReg(Val);
3495 if (ISD::isBuildVectorOfConstantSDNodes(N1.getNode())) {
3496 SmallVector<SDValue, 8> Ops;
3497 for (int i = 0, e = VT.getVectorNumElements(); i != e; ++i) {
3498 SDValue Op = N1.getOperand(i);
3499 if (Op.getValueType() != VT.getScalarType()) break;
3500 if (Op.getOpcode() == ISD::UNDEF) {
3504 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getNode())) {
3505 APInt Val = C->getAPIntValue();
3506 Ops.push_back(SignExtendInReg(Val));
3511 if (Ops.size() == VT.getVectorNumElements())
3512 return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
3516 case ISD::EXTRACT_VECTOR_ELT:
3517 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3518 if (N1.getOpcode() == ISD::UNDEF)
3519 return getUNDEF(VT);
3521 // EXTRACT_VECTOR_ELT of out-of-bounds element is an UNDEF
3522 if (N2C && N2C->getZExtValue() >= N1.getValueType().getVectorNumElements())
3523 return getUNDEF(VT);
3525 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3526 // expanding copies of large vectors from registers.
3528 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3529 N1.getNumOperands() > 0) {
3531 N1.getOperand(0).getValueType().getVectorNumElements();
3532 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3533 N1.getOperand(N2C->getZExtValue() / Factor),
3534 getConstant(N2C->getZExtValue() % Factor, DL,
3535 N2.getValueType()));
3538 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3539 // expanding large vector constants.
3540 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3541 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3543 if (VT != Elt.getValueType())
3544 // If the vector element type is not legal, the BUILD_VECTOR operands
3545 // are promoted and implicitly truncated, and the result implicitly
3546 // extended. Make that explicit here.
3547 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3552 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3553 // operations are lowered to scalars.
3554 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3555 // If the indices are the same, return the inserted element else
3556 // if the indices are known different, extract the element from
3557 // the original vector.
3558 SDValue N1Op2 = N1.getOperand(2);
3559 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3561 if (N1Op2C && N2C) {
3562 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3563 if (VT == N1.getOperand(1).getValueType())
3564 return N1.getOperand(1);
3566 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3569 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3573 case ISD::EXTRACT_ELEMENT:
3574 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3575 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3576 (N1.getValueType().isInteger() == VT.isInteger()) &&
3577 N1.getValueType() != VT &&
3578 "Wrong types for EXTRACT_ELEMENT!");
3580 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3581 // 64-bit integers into 32-bit parts. Instead of building the extract of
3582 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3583 if (N1.getOpcode() == ISD::BUILD_PAIR)
3584 return N1.getOperand(N2C->getZExtValue());
3586 // EXTRACT_ELEMENT of a constant int is also very common.
3587 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3588 unsigned ElementSize = VT.getSizeInBits();
3589 unsigned Shift = ElementSize * N2C->getZExtValue();
3590 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3591 return getConstant(ShiftedVal.trunc(ElementSize), DL, VT);
3594 case ISD::EXTRACT_SUBVECTOR: {
3596 if (VT.isSimple() && N1.getValueType().isSimple()) {
3597 assert(VT.isVector() && N1.getValueType().isVector() &&
3598 "Extract subvector VTs must be a vectors!");
3599 assert(VT.getVectorElementType() ==
3600 N1.getValueType().getVectorElementType() &&
3601 "Extract subvector VTs must have the same element type!");
3602 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3603 "Extract subvector must be from larger vector to smaller vector!");
3605 if (isa<ConstantSDNode>(Index.getNode())) {
3606 assert((VT.getVectorNumElements() +
3607 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3608 <= N1.getValueType().getVectorNumElements())
3609 && "Extract subvector overflow!");
3612 // Trivial extraction.
3613 if (VT.getSimpleVT() == N1.getSimpleValueType())
3620 // Perform trivial constant folding.
3622 FoldConstantArithmetic(Opcode, DL, VT, N1.getNode(), N2.getNode()))
3625 // Canonicalize constant to RHS if commutative.
3626 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3627 std::swap(N1C, N2C);
3631 // Constant fold FP operations.
3632 bool HasFPExceptions = TLI->hasFloatingPointExceptions();
3633 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3634 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3636 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3637 // Canonicalize constant to RHS if commutative.
3638 std::swap(N1CFP, N2CFP);
3641 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3642 APFloat::opStatus s;
3645 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3646 if (!HasFPExceptions || s != APFloat::opInvalidOp)
3647 return getConstantFP(V1, DL, VT);
3650 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3651 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3652 return getConstantFP(V1, DL, VT);
3655 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3656 if (!HasFPExceptions || s!=APFloat::opInvalidOp)
3657 return getConstantFP(V1, DL, VT);
3660 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3661 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3662 s!=APFloat::opDivByZero)) {
3663 return getConstantFP(V1, DL, VT);
3667 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3668 if (!HasFPExceptions || (s!=APFloat::opInvalidOp &&
3669 s!=APFloat::opDivByZero)) {
3670 return getConstantFP(V1, DL, VT);
3673 case ISD::FCOPYSIGN:
3675 return getConstantFP(V1, DL, VT);
3680 if (Opcode == ISD::FP_ROUND) {
3681 APFloat V = N1CFP->getValueAPF(); // make copy
3683 // This can return overflow, underflow, or inexact; we don't care.
3684 // FIXME need to be more flexible about rounding mode.
3685 (void)V.convert(EVTToAPFloatSemantics(VT),
3686 APFloat::rmNearestTiesToEven, &ignored);
3687 return getConstantFP(V, DL, VT);
3691 // Canonicalize an UNDEF to the RHS, even over a constant.
3692 if (N1.getOpcode() == ISD::UNDEF) {
3693 if (isCommutativeBinOp(Opcode)) {
3697 case ISD::FP_ROUND_INREG:
3698 case ISD::SIGN_EXTEND_INREG:
3704 return N1; // fold op(undef, arg2) -> undef
3712 return getConstant(0, DL, VT); // fold op(undef, arg2) -> 0
3713 // For vectors, we can't easily build an all zero vector, just return
3720 // Fold a bunch of operators when the RHS is undef.
3721 if (N2.getOpcode() == ISD::UNDEF) {
3724 if (N1.getOpcode() == ISD::UNDEF)
3725 // Handle undef ^ undef -> 0 special case. This is a common
3727 return getConstant(0, DL, VT);
3737 return N2; // fold op(arg1, undef) -> undef
3743 if (getTarget().Options.UnsafeFPMath)
3751 return getConstant(0, DL, VT); // fold op(arg1, undef) -> 0
3752 // For vectors, we can't easily build an all zero vector, just return
3757 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL, VT);
3758 // For vectors, we can't easily build an all one vector, just return
3766 // Memoize this node if possible.
3768 SDVTList VTs = getVTList(VT);
3769 if (VT != MVT::Glue) {
3770 SDValue Ops[] = {N1, N2};
3771 FoldingSetNodeID ID;
3772 AddNodeIDNode(ID, Opcode, VTs, Ops);
3773 AddNodeIDFlags(ID, Opcode, Flags);
3775 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3776 return SDValue(E, 0);
3778 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3780 CSEMap.InsertNode(N, IP);
3782 N = GetBinarySDNode(Opcode, DL, VTs, N1, N2, Flags);
3786 return SDValue(N, 0);
3789 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3790 SDValue N1, SDValue N2, SDValue N3) {
3791 // Perform various simplifications.
3792 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3795 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3796 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3797 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3798 if (N1CFP && N2CFP && N3CFP) {
3799 APFloat V1 = N1CFP->getValueAPF();
3800 const APFloat &V2 = N2CFP->getValueAPF();
3801 const APFloat &V3 = N3CFP->getValueAPF();
3802 APFloat::opStatus s =
3803 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3804 if (!TLI->hasFloatingPointExceptions() || s != APFloat::opInvalidOp)
3805 return getConstantFP(V1, DL, VT);
3809 case ISD::CONCAT_VECTORS:
3810 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3811 // one big BUILD_VECTOR.
3812 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3813 N2.getOpcode() == ISD::BUILD_VECTOR &&
3814 N3.getOpcode() == ISD::BUILD_VECTOR) {
3815 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3816 N1.getNode()->op_end());
3817 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3818 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3819 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3823 // Use FoldSetCC to simplify SETCC's.
3824 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3825 if (Simp.getNode()) return Simp;
3830 if (N1C->getZExtValue())
3831 return N2; // select true, X, Y -> X
3832 return N3; // select false, X, Y -> Y
3835 if (N2 == N3) return N2; // select C, X, X -> X
3837 case ISD::VECTOR_SHUFFLE:
3838 llvm_unreachable("should use getVectorShuffle constructor!");
3839 case ISD::INSERT_SUBVECTOR: {
3841 if (VT.isSimple() && N1.getValueType().isSimple()
3842 && N2.getValueType().isSimple()) {
3843 assert(VT.isVector() && N1.getValueType().isVector() &&
3844 N2.getValueType().isVector() &&
3845 "Insert subvector VTs must be a vectors");
3846 assert(VT == N1.getValueType() &&
3847 "Dest and insert subvector source types must match!");
3848 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3849 "Insert subvector must be from smaller vector to larger vector!");
3850 if (isa<ConstantSDNode>(Index.getNode())) {
3851 assert((N2.getValueType().getVectorNumElements() +
3852 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3853 <= VT.getVectorNumElements())
3854 && "Insert subvector overflow!");
3857 // Trivial insertion.
3858 if (VT.getSimpleVT() == N2.getSimpleValueType())
3864 // Fold bit_convert nodes from a type to themselves.
3865 if (N1.getValueType() == VT)
3870 // Memoize node if it doesn't produce a flag.
3872 SDVTList VTs = getVTList(VT);
3873 if (VT != MVT::Glue) {
3874 SDValue Ops[] = { N1, N2, N3 };
3875 FoldingSetNodeID ID;
3876 AddNodeIDNode(ID, Opcode, VTs, Ops);
3878 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
3879 return SDValue(E, 0);
3881 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3882 DL.getDebugLoc(), VTs, N1, N2, N3);
3883 CSEMap.InsertNode(N, IP);
3885 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3886 DL.getDebugLoc(), VTs, N1, N2, N3);
3890 return SDValue(N, 0);
3893 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3894 SDValue N1, SDValue N2, SDValue N3,
3896 SDValue Ops[] = { N1, N2, N3, N4 };
3897 return getNode(Opcode, DL, VT, Ops);
3900 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3901 SDValue N1, SDValue N2, SDValue N3,
3902 SDValue N4, SDValue N5) {
3903 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3904 return getNode(Opcode, DL, VT, Ops);
3907 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3908 /// the incoming stack arguments to be loaded from the stack.
3909 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3910 SmallVector<SDValue, 8> ArgChains;
3912 // Include the original chain at the beginning of the list. When this is
3913 // used by target LowerCall hooks, this helps legalize find the
3914 // CALLSEQ_BEGIN node.
3915 ArgChains.push_back(Chain);
3917 // Add a chain value for each stack argument.
3918 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3919 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3920 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3921 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3922 if (FI->getIndex() < 0)
3923 ArgChains.push_back(SDValue(L, 1));
3925 // Build a tokenfactor for all the chains.
3926 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3929 /// getMemsetValue - Vectorized representation of the memset value
3931 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3933 assert(Value.getOpcode() != ISD::UNDEF);
3935 unsigned NumBits = VT.getScalarType().getSizeInBits();
3936 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3937 assert(C->getAPIntValue().getBitWidth() == 8);
3938 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3940 return DAG.getConstant(Val, dl, VT);
3941 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), dl,
3945 assert(Value.getValueType() == MVT::i8 && "memset with non-byte fill value?");
3946 EVT IntVT = VT.getScalarType();
3947 if (!IntVT.isInteger())
3948 IntVT = EVT::getIntegerVT(*DAG.getContext(), IntVT.getSizeInBits());
3950 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, IntVT, Value);
3952 // Use a multiplication with 0x010101... to extend the input to the
3954 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3955 Value = DAG.getNode(ISD::MUL, dl, IntVT, Value,
3956 DAG.getConstant(Magic, dl, IntVT));
3959 if (VT != Value.getValueType() && !VT.isInteger())
3960 Value = DAG.getNode(ISD::BITCAST, dl, VT.getScalarType(), Value);
3961 if (VT != Value.getValueType()) {
3962 assert(VT.getVectorElementType() == Value.getValueType() &&
3963 "value type should be one vector element here");
3964 SmallVector<SDValue, 8> BVOps(VT.getVectorNumElements(), Value);
3965 Value = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, BVOps);
3971 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3972 /// used when a memcpy is turned into a memset when the source is a constant
3974 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3975 const TargetLowering &TLI, StringRef Str) {
3976 // Handle vector with all elements zero.
3979 return DAG.getConstant(0, dl, VT);
3980 else if (VT == MVT::f32 || VT == MVT::f64 || VT == MVT::f128)
3981 return DAG.getConstantFP(0.0, dl, VT);
3982 else if (VT.isVector()) {
3983 unsigned NumElts = VT.getVectorNumElements();
3984 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3985 return DAG.getNode(ISD::BITCAST, dl, VT,
3986 DAG.getConstant(0, dl,
3987 EVT::getVectorVT(*DAG.getContext(),
3990 llvm_unreachable("Expected type!");
3993 assert(!VT.isVector() && "Can't handle vector type here!");
3994 unsigned NumVTBits = VT.getSizeInBits();
3995 unsigned NumVTBytes = NumVTBits / 8;
3996 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3998 APInt Val(NumVTBits, 0);
3999 if (TLI.isLittleEndian()) {
4000 for (unsigned i = 0; i != NumBytes; ++i)
4001 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
4003 for (unsigned i = 0; i != NumBytes; ++i)
4004 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
4007 // If the "cost" of materializing the integer immediate is less than the cost
4008 // of a load, then it is cost effective to turn the load into the immediate.
4009 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
4010 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
4011 return DAG.getConstant(Val, dl, VT);
4012 return SDValue(nullptr, 0);
4015 /// getMemBasePlusOffset - Returns base and offset node for the
4017 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
4018 SelectionDAG &DAG) {
4019 EVT VT = Base.getValueType();
4020 return DAG.getNode(ISD::ADD, dl,
4021 VT, Base, DAG.getConstant(Offset, dl, VT));
4024 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
4026 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
4027 unsigned SrcDelta = 0;
4028 GlobalAddressSDNode *G = nullptr;
4029 if (Src.getOpcode() == ISD::GlobalAddress)
4030 G = cast<GlobalAddressSDNode>(Src);
4031 else if (Src.getOpcode() == ISD::ADD &&
4032 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
4033 Src.getOperand(1).getOpcode() == ISD::Constant) {
4034 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
4035 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
4040 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
4043 /// Determines the optimal series of memory ops to replace the memset / memcpy.
4044 /// Return true if the number of memory ops is below the threshold (Limit).
4045 /// It returns the types of the sequence of memory ops to perform
4046 /// memset / memcpy by reference.
4047 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
4048 unsigned Limit, uint64_t Size,
4049 unsigned DstAlign, unsigned SrcAlign,
4055 const TargetLowering &TLI) {
4056 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
4057 "Expecting memcpy / memset source to meet alignment requirement!");
4058 // If 'SrcAlign' is zero, that means the memory operation does not need to
4059 // load the value, i.e. memset or memcpy from constant string. Otherwise,
4060 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
4061 // is the specified alignment of the memory operation. If it is zero, that
4062 // means it's possible to change the alignment of the destination.
4063 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
4064 // not need to be loaded.
4065 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
4066 IsMemset, ZeroMemset, MemcpyStrSrc,
4067 DAG.getMachineFunction());
4069 if (VT == MVT::Other) {
4071 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
4072 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign)) {
4073 VT = TLI.getPointerTy();
4075 switch (DstAlign & 7) {
4076 case 0: VT = MVT::i64; break;
4077 case 4: VT = MVT::i32; break;
4078 case 2: VT = MVT::i16; break;
4079 default: VT = MVT::i8; break;
4084 while (!TLI.isTypeLegal(LVT))
4085 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
4086 assert(LVT.isInteger());
4092 unsigned NumMemOps = 0;
4094 unsigned VTSize = VT.getSizeInBits() / 8;
4095 while (VTSize > Size) {
4096 // For now, only use non-vector load / store's for the left-over pieces.
4101 if (VT.isVector() || VT.isFloatingPoint()) {
4102 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
4103 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
4104 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
4106 else if (NewVT == MVT::i64 &&
4107 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
4108 TLI.isSafeMemOpType(MVT::f64)) {
4109 // i64 is usually not legal on 32-bit targets, but f64 may be.
4117 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
4118 if (NewVT == MVT::i8)
4120 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
4122 NewVTSize = NewVT.getSizeInBits() / 8;
4124 // If the new VT cannot cover all of the remaining bits, then consider
4125 // issuing a (or a pair of) unaligned and overlapping load / store.
4126 // FIXME: Only does this for 64-bit or more since we don't have proper
4127 // cost model for unaligned load / store.
4130 if (NumMemOps && AllowOverlap &&
4131 VTSize >= 8 && NewVTSize < Size &&
4132 TLI.allowsMisalignedMemoryAccesses(VT, AS, DstAlign, &Fast) && Fast)
4140 if (++NumMemOps > Limit)
4143 MemOps.push_back(VT);
4150 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4151 SDValue Chain, SDValue Dst,
4152 SDValue Src, uint64_t Size,
4153 unsigned Align, bool isVol,
4155 MachinePointerInfo DstPtrInfo,
4156 MachinePointerInfo SrcPtrInfo) {
4157 // Turn a memcpy of undef to nop.
4158 if (Src.getOpcode() == ISD::UNDEF)
4161 // Expand memcpy to a series of load and store ops if the size operand falls
4162 // below a certain threshold.
4163 // TODO: In the AlwaysInline case, if the size is big then generate a loop
4164 // rather than maybe a humongous number of loads and stores.
4165 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4166 std::vector<EVT> MemOps;
4167 bool DstAlignCanChange = false;
4168 MachineFunction &MF = DAG.getMachineFunction();
4169 MachineFrameInfo *MFI = MF.getFrameInfo();
4170 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4171 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4172 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4173 DstAlignCanChange = true;
4174 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4175 if (Align > SrcAlign)
4178 bool CopyFromStr = isMemSrcFromString(Src, Str);
4179 bool isZeroStr = CopyFromStr && Str.empty();
4180 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
4182 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4183 (DstAlignCanChange ? 0 : Align),
4184 (isZeroStr ? 0 : SrcAlign),
4185 false, false, CopyFromStr, true, DAG, TLI))
4188 if (DstAlignCanChange) {
4189 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4190 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4192 // Don't promote to an alignment that would require dynamic stack
4194 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
4195 if (!TRI->needsStackRealignment(MF))
4196 while (NewAlign > Align &&
4197 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
4200 if (NewAlign > Align) {
4201 // Give the stack frame object a larger alignment if needed.
4202 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4203 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4208 SmallVector<SDValue, 8> OutChains;
4209 unsigned NumMemOps = MemOps.size();
4210 uint64_t SrcOff = 0, DstOff = 0;
4211 for (unsigned i = 0; i != NumMemOps; ++i) {
4213 unsigned VTSize = VT.getSizeInBits() / 8;
4214 SDValue Value, Store;
4216 if (VTSize > Size) {
4217 // Issuing an unaligned load / store pair that overlaps with the previous
4218 // pair. Adjust the offset accordingly.
4219 assert(i == NumMemOps-1 && i != 0);
4220 SrcOff -= VTSize - Size;
4221 DstOff -= VTSize - Size;
4225 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
4226 // It's unlikely a store of a vector immediate can be done in a single
4227 // instruction. It would require a load from a constantpool first.
4228 // We only handle zero vectors here.
4229 // FIXME: Handle other cases where store of vector immediate is done in
4230 // a single instruction.
4231 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
4232 if (Value.getNode())
4233 Store = DAG.getStore(Chain, dl, Value,
4234 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4235 DstPtrInfo.getWithOffset(DstOff), isVol,
4239 if (!Store.getNode()) {
4240 // The type might not be legal for the target. This should only happen
4241 // if the type is smaller than a legal type, as on PPC, so the right
4242 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
4243 // to Load/Store if NVT==VT.
4244 // FIXME does the case above also need this?
4245 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
4246 assert(NVT.bitsGE(VT));
4247 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
4248 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4249 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
4250 false, MinAlign(SrcAlign, SrcOff));
4251 Store = DAG.getTruncStore(Chain, dl, Value,
4252 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4253 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
4256 OutChains.push_back(Store);
4262 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4265 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
4266 SDValue Chain, SDValue Dst,
4267 SDValue Src, uint64_t Size,
4268 unsigned Align, bool isVol,
4270 MachinePointerInfo DstPtrInfo,
4271 MachinePointerInfo SrcPtrInfo) {
4272 // Turn a memmove of undef to nop.
4273 if (Src.getOpcode() == ISD::UNDEF)
4276 // Expand memmove to a series of load and store ops if the size operand falls
4277 // below a certain threshold.
4278 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4279 std::vector<EVT> MemOps;
4280 bool DstAlignCanChange = false;
4281 MachineFunction &MF = DAG.getMachineFunction();
4282 MachineFrameInfo *MFI = MF.getFrameInfo();
4283 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4284 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4285 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4286 DstAlignCanChange = true;
4287 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
4288 if (Align > SrcAlign)
4290 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
4292 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
4293 (DstAlignCanChange ? 0 : Align), SrcAlign,
4294 false, false, false, false, DAG, TLI))
4297 if (DstAlignCanChange) {
4298 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4299 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4300 if (NewAlign > Align) {
4301 // Give the stack frame object a larger alignment if needed.
4302 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4303 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4308 uint64_t SrcOff = 0, DstOff = 0;
4309 SmallVector<SDValue, 8> LoadValues;
4310 SmallVector<SDValue, 8> LoadChains;
4311 SmallVector<SDValue, 8> OutChains;
4312 unsigned NumMemOps = MemOps.size();
4313 for (unsigned i = 0; i < NumMemOps; i++) {
4315 unsigned VTSize = VT.getSizeInBits() / 8;
4318 Value = DAG.getLoad(VT, dl, Chain,
4319 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
4320 SrcPtrInfo.getWithOffset(SrcOff), isVol,
4321 false, false, SrcAlign);
4322 LoadValues.push_back(Value);
4323 LoadChains.push_back(Value.getValue(1));
4326 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
4328 for (unsigned i = 0; i < NumMemOps; i++) {
4330 unsigned VTSize = VT.getSizeInBits() / 8;
4333 Store = DAG.getStore(Chain, dl, LoadValues[i],
4334 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4335 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
4336 OutChains.push_back(Store);
4340 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4343 /// \brief Lower the call to 'memset' intrinsic function into a series of store
4346 /// \param DAG Selection DAG where lowered code is placed.
4347 /// \param dl Link to corresponding IR location.
4348 /// \param Chain Control flow dependency.
4349 /// \param Dst Pointer to destination memory location.
4350 /// \param Src Value of byte to write into the memory.
4351 /// \param Size Number of bytes to write.
4352 /// \param Align Alignment of the destination in bytes.
4353 /// \param isVol True if destination is volatile.
4354 /// \param DstPtrInfo IR information on the memory pointer.
4355 /// \returns New head in the control flow, if lowering was successful, empty
4356 /// SDValue otherwise.
4358 /// The function tries to replace 'llvm.memset' intrinsic with several store
4359 /// operations and value calculation code. This is usually profitable for small
4361 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
4362 SDValue Chain, SDValue Dst,
4363 SDValue Src, uint64_t Size,
4364 unsigned Align, bool isVol,
4365 MachinePointerInfo DstPtrInfo) {
4366 // Turn a memset of undef to nop.
4367 if (Src.getOpcode() == ISD::UNDEF)
4370 // Expand memset to a series of load/store ops if the size operand
4371 // falls below a certain threshold.
4372 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4373 std::vector<EVT> MemOps;
4374 bool DstAlignCanChange = false;
4375 MachineFunction &MF = DAG.getMachineFunction();
4376 MachineFrameInfo *MFI = MF.getFrameInfo();
4377 bool OptSize = MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize);
4378 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
4379 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
4380 DstAlignCanChange = true;
4382 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
4383 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
4384 Size, (DstAlignCanChange ? 0 : Align), 0,
4385 true, IsZeroVal, false, true, DAG, TLI))
4388 if (DstAlignCanChange) {
4389 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
4390 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4391 if (NewAlign > Align) {
4392 // Give the stack frame object a larger alignment if needed.
4393 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4394 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4399 SmallVector<SDValue, 8> OutChains;
4400 uint64_t DstOff = 0;
4401 unsigned NumMemOps = MemOps.size();
4403 // Find the largest store and generate the bit pattern for it.
4404 EVT LargestVT = MemOps[0];
4405 for (unsigned i = 1; i < NumMemOps; i++)
4406 if (MemOps[i].bitsGT(LargestVT))
4407 LargestVT = MemOps[i];
4408 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4410 for (unsigned i = 0; i < NumMemOps; i++) {
4412 unsigned VTSize = VT.getSizeInBits() / 8;
4413 if (VTSize > Size) {
4414 // Issuing an unaligned load / store pair that overlaps with the previous
4415 // pair. Adjust the offset accordingly.
4416 assert(i == NumMemOps-1 && i != 0);
4417 DstOff -= VTSize - Size;
4420 // If this store is smaller than the largest store see whether we can get
4421 // the smaller value for free with a truncate.
4422 SDValue Value = MemSetValue;
4423 if (VT.bitsLT(LargestVT)) {
4424 if (!LargestVT.isVector() && !VT.isVector() &&
4425 TLI.isTruncateFree(LargestVT, VT))
4426 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4428 Value = getMemsetValue(Src, VT, DAG, dl);
4430 assert(Value.getValueType() == VT && "Value with wrong type.");
4431 SDValue Store = DAG.getStore(Chain, dl, Value,
4432 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4433 DstPtrInfo.getWithOffset(DstOff),
4434 isVol, false, Align);
4435 OutChains.push_back(Store);
4436 DstOff += VT.getSizeInBits() / 8;
4440 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4443 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4444 SDValue Src, SDValue Size,
4445 unsigned Align, bool isVol, bool AlwaysInline,
4446 bool isTailCall, MachinePointerInfo DstPtrInfo,
4447 MachinePointerInfo SrcPtrInfo) {
4448 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4450 // Check to see if we should lower the memcpy to loads and stores first.
4451 // For cases within the target-specified limits, this is the best choice.
4452 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4454 // Memcpy with size zero? Just return the original chain.
4455 if (ConstantSize->isNullValue())
4458 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4459 ConstantSize->getZExtValue(),Align,
4460 isVol, false, DstPtrInfo, SrcPtrInfo);
4461 if (Result.getNode())
4465 // Then check to see if we should lower the memcpy with target-specific
4466 // code. If the target chooses to do this, this is the next best.
4468 SDValue Result = TSI->EmitTargetCodeForMemcpy(
4469 *this, dl, Chain, Dst, Src, Size, Align, isVol, AlwaysInline,
4470 DstPtrInfo, SrcPtrInfo);
4471 if (Result.getNode())
4475 // If we really need inline code and the target declined to provide it,
4476 // use a (potentially long) sequence of loads and stores.
4478 assert(ConstantSize && "AlwaysInline requires a constant size!");
4479 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4480 ConstantSize->getZExtValue(), Align, isVol,
4481 true, DstPtrInfo, SrcPtrInfo);
4484 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4485 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4486 // respect volatile, so they may do things like read or write memory
4487 // beyond the given memory regions. But fixing this isn't easy, and most
4488 // people don't care.
4490 // Emit a library call.
4491 TargetLowering::ArgListTy Args;
4492 TargetLowering::ArgListEntry Entry;
4493 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4494 Entry.Node = Dst; Args.push_back(Entry);
4495 Entry.Node = Src; Args.push_back(Entry);
4496 Entry.Node = Size; Args.push_back(Entry);
4497 // FIXME: pass in SDLoc
4498 TargetLowering::CallLoweringInfo CLI(*this);
4499 CLI.setDebugLoc(dl).setChain(Chain)
4500 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4501 Type::getVoidTy(*getContext()),
4502 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4503 TLI->getPointerTy()), std::move(Args), 0)
4505 .setTailCall(isTailCall);
4507 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4508 return CallResult.second;
4511 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4512 SDValue Src, SDValue Size,
4513 unsigned Align, bool isVol, bool isTailCall,
4514 MachinePointerInfo DstPtrInfo,
4515 MachinePointerInfo SrcPtrInfo) {
4516 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4518 // Check to see if we should lower the memmove to loads and stores first.
4519 // For cases within the target-specified limits, this is the best choice.
4520 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4522 // Memmove with size zero? Just return the original chain.
4523 if (ConstantSize->isNullValue())
4527 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4528 ConstantSize->getZExtValue(), Align, isVol,
4529 false, DstPtrInfo, SrcPtrInfo);
4530 if (Result.getNode())
4534 // Then check to see if we should lower the memmove with target-specific
4535 // code. If the target chooses to do this, this is the next best.
4537 SDValue Result = TSI->EmitTargetCodeForMemmove(
4538 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo, SrcPtrInfo);
4539 if (Result.getNode())
4543 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4544 // not be safe. See memcpy above for more details.
4546 // Emit a library call.
4547 TargetLowering::ArgListTy Args;
4548 TargetLowering::ArgListEntry Entry;
4549 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4550 Entry.Node = Dst; Args.push_back(Entry);
4551 Entry.Node = Src; Args.push_back(Entry);
4552 Entry.Node = Size; Args.push_back(Entry);
4553 // FIXME: pass in SDLoc
4554 TargetLowering::CallLoweringInfo CLI(*this);
4555 CLI.setDebugLoc(dl).setChain(Chain)
4556 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4557 Type::getVoidTy(*getContext()),
4558 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4559 TLI->getPointerTy()), std::move(Args), 0)
4561 .setTailCall(isTailCall);
4563 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4564 return CallResult.second;
4567 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4568 SDValue Src, SDValue Size,
4569 unsigned Align, bool isVol, bool isTailCall,
4570 MachinePointerInfo DstPtrInfo) {
4571 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4573 // Check to see if we should lower the memset to stores first.
4574 // For cases within the target-specified limits, this is the best choice.
4575 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4577 // Memset with size zero? Just return the original chain.
4578 if (ConstantSize->isNullValue())
4582 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4583 Align, isVol, DstPtrInfo);
4585 if (Result.getNode())
4589 // Then check to see if we should lower the memset with target-specific
4590 // code. If the target chooses to do this, this is the next best.
4592 SDValue Result = TSI->EmitTargetCodeForMemset(
4593 *this, dl, Chain, Dst, Src, Size, Align, isVol, DstPtrInfo);
4594 if (Result.getNode())
4598 // Emit a library call.
4599 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4600 TargetLowering::ArgListTy Args;
4601 TargetLowering::ArgListEntry Entry;
4602 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4603 Args.push_back(Entry);
4605 Entry.Ty = Src.getValueType().getTypeForEVT(*getContext());
4606 Args.push_back(Entry);
4608 Entry.Ty = IntPtrTy;
4609 Args.push_back(Entry);
4611 // FIXME: pass in SDLoc
4612 TargetLowering::CallLoweringInfo CLI(*this);
4613 CLI.setDebugLoc(dl).setChain(Chain)
4614 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4615 Type::getVoidTy(*getContext()),
4616 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4617 TLI->getPointerTy()), std::move(Args), 0)
4619 .setTailCall(isTailCall);
4621 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4622 return CallResult.second;
4625 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4626 SDVTList VTList, ArrayRef<SDValue> Ops,
4627 MachineMemOperand *MMO,
4628 AtomicOrdering SuccessOrdering,
4629 AtomicOrdering FailureOrdering,
4630 SynchronizationScope SynchScope) {
4631 FoldingSetNodeID ID;
4632 ID.AddInteger(MemVT.getRawBits());
4633 AddNodeIDNode(ID, Opcode, VTList, Ops);
4634 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4636 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4637 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4638 return SDValue(E, 0);
4641 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4642 // SDNode doesn't have access to it. This memory will be "leaked" when
4643 // the node is deallocated, but recovered when the allocator is released.
4644 // If the number of operands is less than 5 we use AtomicSDNode's internal
4646 unsigned NumOps = Ops.size();
4647 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4650 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4651 dl.getDebugLoc(), VTList, MemVT,
4652 Ops.data(), DynOps, NumOps, MMO,
4653 SuccessOrdering, FailureOrdering,
4655 CSEMap.InsertNode(N, IP);
4657 return SDValue(N, 0);
4660 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4661 SDVTList VTList, ArrayRef<SDValue> Ops,
4662 MachineMemOperand *MMO,
4663 AtomicOrdering Ordering,
4664 SynchronizationScope SynchScope) {
4665 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4666 Ordering, SynchScope);
4669 SDValue SelectionDAG::getAtomicCmpSwap(
4670 unsigned Opcode, SDLoc dl, EVT MemVT, SDVTList VTs, SDValue Chain,
4671 SDValue Ptr, SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
4672 unsigned Alignment, AtomicOrdering SuccessOrdering,
4673 AtomicOrdering FailureOrdering, SynchronizationScope SynchScope) {
4674 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4675 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4676 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4678 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4679 Alignment = getEVTAlignment(MemVT);
4681 MachineFunction &MF = getMachineFunction();
4683 // FIXME: Volatile isn't really correct; we should keep track of atomic
4684 // orderings in the memoperand.
4685 unsigned Flags = MachineMemOperand::MOVolatile;
4686 Flags |= MachineMemOperand::MOLoad;
4687 Flags |= MachineMemOperand::MOStore;
4689 MachineMemOperand *MMO =
4690 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4692 return getAtomicCmpSwap(Opcode, dl, MemVT, VTs, Chain, Ptr, Cmp, Swp, MMO,
4693 SuccessOrdering, FailureOrdering, SynchScope);
4696 SDValue SelectionDAG::getAtomicCmpSwap(unsigned Opcode, SDLoc dl, EVT MemVT,
4697 SDVTList VTs, SDValue Chain, SDValue Ptr,
4698 SDValue Cmp, SDValue Swp,
4699 MachineMemOperand *MMO,
4700 AtomicOrdering SuccessOrdering,
4701 AtomicOrdering FailureOrdering,
4702 SynchronizationScope SynchScope) {
4703 assert(Opcode == ISD::ATOMIC_CMP_SWAP ||
4704 Opcode == ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS);
4705 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4707 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4708 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO,
4709 SuccessOrdering, FailureOrdering, SynchScope);
4712 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4714 SDValue Ptr, SDValue Val,
4715 const Value* PtrVal,
4717 AtomicOrdering Ordering,
4718 SynchronizationScope SynchScope) {
4719 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4720 Alignment = getEVTAlignment(MemVT);
4722 MachineFunction &MF = getMachineFunction();
4723 // An atomic store does not load. An atomic load does not store.
4724 // (An atomicrmw obviously both loads and stores.)
4725 // For now, atomics are considered to be volatile always, and they are
4727 // FIXME: Volatile isn't really correct; we should keep track of atomic
4728 // orderings in the memoperand.
4729 unsigned Flags = MachineMemOperand::MOVolatile;
4730 if (Opcode != ISD::ATOMIC_STORE)
4731 Flags |= MachineMemOperand::MOLoad;
4732 if (Opcode != ISD::ATOMIC_LOAD)
4733 Flags |= MachineMemOperand::MOStore;
4735 MachineMemOperand *MMO =
4736 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4737 MemVT.getStoreSize(), Alignment);
4739 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4740 Ordering, SynchScope);
4743 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4745 SDValue Ptr, SDValue Val,
4746 MachineMemOperand *MMO,
4747 AtomicOrdering Ordering,
4748 SynchronizationScope SynchScope) {
4749 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4750 Opcode == ISD::ATOMIC_LOAD_SUB ||
4751 Opcode == ISD::ATOMIC_LOAD_AND ||
4752 Opcode == ISD::ATOMIC_LOAD_OR ||
4753 Opcode == ISD::ATOMIC_LOAD_XOR ||
4754 Opcode == ISD::ATOMIC_LOAD_NAND ||
4755 Opcode == ISD::ATOMIC_LOAD_MIN ||
4756 Opcode == ISD::ATOMIC_LOAD_MAX ||
4757 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4758 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4759 Opcode == ISD::ATOMIC_SWAP ||
4760 Opcode == ISD::ATOMIC_STORE) &&
4761 "Invalid Atomic Op");
4763 EVT VT = Val.getValueType();
4765 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4766 getVTList(VT, MVT::Other);
4767 SDValue Ops[] = {Chain, Ptr, Val};
4768 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4771 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4772 EVT VT, SDValue Chain,
4774 MachineMemOperand *MMO,
4775 AtomicOrdering Ordering,
4776 SynchronizationScope SynchScope) {
4777 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4779 SDVTList VTs = getVTList(VT, MVT::Other);
4780 SDValue Ops[] = {Chain, Ptr};
4781 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4784 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4785 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4786 if (Ops.size() == 1)
4789 SmallVector<EVT, 4> VTs;
4790 VTs.reserve(Ops.size());
4791 for (unsigned i = 0; i < Ops.size(); ++i)
4792 VTs.push_back(Ops[i].getValueType());
4793 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4797 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4798 ArrayRef<SDValue> Ops,
4799 EVT MemVT, MachinePointerInfo PtrInfo,
4800 unsigned Align, bool Vol,
4801 bool ReadMem, bool WriteMem, unsigned Size) {
4802 if (Align == 0) // Ensure that codegen never sees alignment 0
4803 Align = getEVTAlignment(MemVT);
4805 MachineFunction &MF = getMachineFunction();
4808 Flags |= MachineMemOperand::MOStore;
4810 Flags |= MachineMemOperand::MOLoad;
4812 Flags |= MachineMemOperand::MOVolatile;
4814 Size = MemVT.getStoreSize();
4815 MachineMemOperand *MMO =
4816 MF.getMachineMemOperand(PtrInfo, Flags, Size, Align);
4818 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4822 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4823 ArrayRef<SDValue> Ops, EVT MemVT,
4824 MachineMemOperand *MMO) {
4825 assert((Opcode == ISD::INTRINSIC_VOID ||
4826 Opcode == ISD::INTRINSIC_W_CHAIN ||
4827 Opcode == ISD::PREFETCH ||
4828 Opcode == ISD::LIFETIME_START ||
4829 Opcode == ISD::LIFETIME_END ||
4830 (Opcode <= INT_MAX &&
4831 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4832 "Opcode is not a memory-accessing opcode!");
4834 // Memoize the node unless it returns a flag.
4835 MemIntrinsicSDNode *N;
4836 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4837 FoldingSetNodeID ID;
4838 AddNodeIDNode(ID, Opcode, VTList, Ops);
4839 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4841 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4842 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4843 return SDValue(E, 0);
4846 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4847 dl.getDebugLoc(), VTList, Ops,
4849 CSEMap.InsertNode(N, IP);
4851 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4852 dl.getDebugLoc(), VTList, Ops,
4856 return SDValue(N, 0);
4859 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4860 /// MachinePointerInfo record from it. This is particularly useful because the
4861 /// code generator has many cases where it doesn't bother passing in a
4862 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4863 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4864 // If this is FI+Offset, we can model it.
4865 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4866 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4868 // If this is (FI+Offset1)+Offset2, we can model it.
4869 if (Ptr.getOpcode() != ISD::ADD ||
4870 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4871 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4872 return MachinePointerInfo();
4874 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4875 return MachinePointerInfo::getFixedStack(FI, Offset+
4876 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4879 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4880 /// MachinePointerInfo record from it. This is particularly useful because the
4881 /// code generator has many cases where it doesn't bother passing in a
4882 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4883 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4884 // If the 'Offset' value isn't a constant, we can't handle this.
4885 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4886 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4887 if (OffsetOp.getOpcode() == ISD::UNDEF)
4888 return InferPointerInfo(Ptr);
4889 return MachinePointerInfo();
4894 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4895 EVT VT, SDLoc dl, SDValue Chain,
4896 SDValue Ptr, SDValue Offset,
4897 MachinePointerInfo PtrInfo, EVT MemVT,
4898 bool isVolatile, bool isNonTemporal, bool isInvariant,
4899 unsigned Alignment, const AAMDNodes &AAInfo,
4900 const MDNode *Ranges) {
4901 assert(Chain.getValueType() == MVT::Other &&
4902 "Invalid chain type");
4903 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4904 Alignment = getEVTAlignment(VT);
4906 unsigned Flags = MachineMemOperand::MOLoad;
4908 Flags |= MachineMemOperand::MOVolatile;
4910 Flags |= MachineMemOperand::MONonTemporal;
4912 Flags |= MachineMemOperand::MOInvariant;
4914 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4916 if (PtrInfo.V.isNull())
4917 PtrInfo = InferPointerInfo(Ptr, Offset);
4919 MachineFunction &MF = getMachineFunction();
4920 MachineMemOperand *MMO =
4921 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4923 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4927 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4928 EVT VT, SDLoc dl, SDValue Chain,
4929 SDValue Ptr, SDValue Offset, EVT MemVT,
4930 MachineMemOperand *MMO) {
4932 ExtType = ISD::NON_EXTLOAD;
4933 } else if (ExtType == ISD::NON_EXTLOAD) {
4934 assert(VT == MemVT && "Non-extending load from different memory type!");
4937 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4938 "Should only be an extending load, not truncating!");
4939 assert(VT.isInteger() == MemVT.isInteger() &&
4940 "Cannot convert from FP to Int or Int -> FP!");
4941 assert(VT.isVector() == MemVT.isVector() &&
4942 "Cannot use an ext load to convert to or from a vector!");
4943 assert((!VT.isVector() ||
4944 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4945 "Cannot use an ext load to change the number of vector elements!");
4948 bool Indexed = AM != ISD::UNINDEXED;
4949 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4950 "Unindexed load with an offset!");
4952 SDVTList VTs = Indexed ?
4953 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4954 SDValue Ops[] = { Chain, Ptr, Offset };
4955 FoldingSetNodeID ID;
4956 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4957 ID.AddInteger(MemVT.getRawBits());
4958 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4959 MMO->isNonTemporal(),
4960 MMO->isInvariant()));
4961 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4963 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
4964 cast<LoadSDNode>(E)->refineAlignment(MMO);
4965 return SDValue(E, 0);
4967 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4968 dl.getDebugLoc(), VTs, AM, ExtType,
4970 CSEMap.InsertNode(N, IP);
4972 return SDValue(N, 0);
4975 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4976 SDValue Chain, SDValue Ptr,
4977 MachinePointerInfo PtrInfo,
4978 bool isVolatile, bool isNonTemporal,
4979 bool isInvariant, unsigned Alignment,
4980 const AAMDNodes &AAInfo,
4981 const MDNode *Ranges) {
4982 SDValue Undef = getUNDEF(Ptr.getValueType());
4983 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4984 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4988 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4989 SDValue Chain, SDValue Ptr,
4990 MachineMemOperand *MMO) {
4991 SDValue Undef = getUNDEF(Ptr.getValueType());
4992 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4996 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4997 SDValue Chain, SDValue Ptr,
4998 MachinePointerInfo PtrInfo, EVT MemVT,
4999 bool isVolatile, bool isNonTemporal,
5000 bool isInvariant, unsigned Alignment,
5001 const AAMDNodes &AAInfo) {
5002 SDValue Undef = getUNDEF(Ptr.getValueType());
5003 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5004 PtrInfo, MemVT, isVolatile, isNonTemporal, isInvariant,
5009 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
5010 SDValue Chain, SDValue Ptr, EVT MemVT,
5011 MachineMemOperand *MMO) {
5012 SDValue Undef = getUNDEF(Ptr.getValueType());
5013 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
5018 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
5019 SDValue Offset, ISD::MemIndexedMode AM) {
5020 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
5021 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
5022 "Load is already a indexed load!");
5023 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
5024 LD->getChain(), Base, Offset, LD->getPointerInfo(),
5025 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
5026 false, LD->getAlignment());
5029 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5030 SDValue Ptr, MachinePointerInfo PtrInfo,
5031 bool isVolatile, bool isNonTemporal,
5032 unsigned Alignment, const AAMDNodes &AAInfo) {
5033 assert(Chain.getValueType() == MVT::Other &&
5034 "Invalid chain type");
5035 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5036 Alignment = getEVTAlignment(Val.getValueType());
5038 unsigned Flags = MachineMemOperand::MOStore;
5040 Flags |= MachineMemOperand::MOVolatile;
5042 Flags |= MachineMemOperand::MONonTemporal;
5044 if (PtrInfo.V.isNull())
5045 PtrInfo = InferPointerInfo(Ptr);
5047 MachineFunction &MF = getMachineFunction();
5048 MachineMemOperand *MMO =
5049 MF.getMachineMemOperand(PtrInfo, Flags,
5050 Val.getValueType().getStoreSize(), Alignment,
5053 return getStore(Chain, dl, Val, Ptr, MMO);
5056 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
5057 SDValue Ptr, MachineMemOperand *MMO) {
5058 assert(Chain.getValueType() == MVT::Other &&
5059 "Invalid chain type");
5060 EVT VT = Val.getValueType();
5061 SDVTList VTs = getVTList(MVT::Other);
5062 SDValue Undef = getUNDEF(Ptr.getValueType());
5063 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5064 FoldingSetNodeID ID;
5065 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5066 ID.AddInteger(VT.getRawBits());
5067 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5068 MMO->isNonTemporal(), MMO->isInvariant()));
5069 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5071 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5072 cast<StoreSDNode>(E)->refineAlignment(MMO);
5073 return SDValue(E, 0);
5075 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5076 dl.getDebugLoc(), VTs,
5077 ISD::UNINDEXED, false, VT, MMO);
5078 CSEMap.InsertNode(N, IP);
5080 return SDValue(N, 0);
5083 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5084 SDValue Ptr, MachinePointerInfo PtrInfo,
5085 EVT SVT,bool isVolatile, bool isNonTemporal,
5087 const AAMDNodes &AAInfo) {
5088 assert(Chain.getValueType() == MVT::Other &&
5089 "Invalid chain type");
5090 if (Alignment == 0) // Ensure that codegen never sees alignment 0
5091 Alignment = getEVTAlignment(SVT);
5093 unsigned Flags = MachineMemOperand::MOStore;
5095 Flags |= MachineMemOperand::MOVolatile;
5097 Flags |= MachineMemOperand::MONonTemporal;
5099 if (PtrInfo.V.isNull())
5100 PtrInfo = InferPointerInfo(Ptr);
5102 MachineFunction &MF = getMachineFunction();
5103 MachineMemOperand *MMO =
5104 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
5107 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
5110 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
5111 SDValue Ptr, EVT SVT,
5112 MachineMemOperand *MMO) {
5113 EVT VT = Val.getValueType();
5115 assert(Chain.getValueType() == MVT::Other &&
5116 "Invalid chain type");
5118 return getStore(Chain, dl, Val, Ptr, MMO);
5120 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
5121 "Should only be a truncating store, not extending!");
5122 assert(VT.isInteger() == SVT.isInteger() &&
5123 "Can't do FP-INT conversion!");
5124 assert(VT.isVector() == SVT.isVector() &&
5125 "Cannot use trunc store to convert to or from a vector!");
5126 assert((!VT.isVector() ||
5127 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
5128 "Cannot use trunc store to change the number of vector elements!");
5130 SDVTList VTs = getVTList(MVT::Other);
5131 SDValue Undef = getUNDEF(Ptr.getValueType());
5132 SDValue Ops[] = { Chain, Val, Ptr, Undef };
5133 FoldingSetNodeID ID;
5134 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5135 ID.AddInteger(SVT.getRawBits());
5136 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
5137 MMO->isNonTemporal(), MMO->isInvariant()));
5138 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5140 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5141 cast<StoreSDNode>(E)->refineAlignment(MMO);
5142 return SDValue(E, 0);
5144 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5145 dl.getDebugLoc(), VTs,
5146 ISD::UNINDEXED, true, SVT, MMO);
5147 CSEMap.InsertNode(N, IP);
5149 return SDValue(N, 0);
5153 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
5154 SDValue Offset, ISD::MemIndexedMode AM) {
5155 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
5156 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
5157 "Store is already a indexed store!");
5158 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
5159 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
5160 FoldingSetNodeID ID;
5161 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
5162 ID.AddInteger(ST->getMemoryVT().getRawBits());
5163 ID.AddInteger(ST->getRawSubclassData());
5164 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
5166 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP))
5167 return SDValue(E, 0);
5169 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
5170 dl.getDebugLoc(), VTs, AM,
5171 ST->isTruncatingStore(),
5173 ST->getMemOperand());
5174 CSEMap.InsertNode(N, IP);
5176 return SDValue(N, 0);
5180 SelectionDAG::getMaskedLoad(EVT VT, SDLoc dl, SDValue Chain,
5181 SDValue Ptr, SDValue Mask, SDValue Src0, EVT MemVT,
5182 MachineMemOperand *MMO, ISD::LoadExtType ExtTy) {
5184 SDVTList VTs = getVTList(VT, MVT::Other);
5185 SDValue Ops[] = { Chain, Ptr, Mask, Src0 };
5186 FoldingSetNodeID ID;
5187 AddNodeIDNode(ID, ISD::MLOAD, VTs, Ops);
5188 ID.AddInteger(VT.getRawBits());
5189 ID.AddInteger(encodeMemSDNodeFlags(ExtTy, ISD::UNINDEXED,
5191 MMO->isNonTemporal(),
5192 MMO->isInvariant()));
5193 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5195 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5196 cast<MaskedLoadSDNode>(E)->refineAlignment(MMO);
5197 return SDValue(E, 0);
5199 SDNode *N = new (NodeAllocator) MaskedLoadSDNode(dl.getIROrder(),
5200 dl.getDebugLoc(), Ops, 4, VTs,
5202 CSEMap.InsertNode(N, IP);
5204 return SDValue(N, 0);
5207 SDValue SelectionDAG::getMaskedStore(SDValue Chain, SDLoc dl, SDValue Val,
5208 SDValue Ptr, SDValue Mask, EVT MemVT,
5209 MachineMemOperand *MMO, bool isTrunc) {
5210 assert(Chain.getValueType() == MVT::Other &&
5211 "Invalid chain type");
5212 EVT VT = Val.getValueType();
5213 SDVTList VTs = getVTList(MVT::Other);
5214 SDValue Ops[] = { Chain, Ptr, Mask, Val };
5215 FoldingSetNodeID ID;
5216 AddNodeIDNode(ID, ISD::MSTORE, VTs, Ops);
5217 ID.AddInteger(VT.getRawBits());
5218 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5219 MMO->isNonTemporal(), MMO->isInvariant()));
5220 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5222 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5223 cast<MaskedStoreSDNode>(E)->refineAlignment(MMO);
5224 return SDValue(E, 0);
5226 SDNode *N = new (NodeAllocator) MaskedStoreSDNode(dl.getIROrder(),
5227 dl.getDebugLoc(), Ops, 4,
5228 VTs, isTrunc, MemVT, MMO);
5229 CSEMap.InsertNode(N, IP);
5231 return SDValue(N, 0);
5235 SelectionDAG::getMaskedGather(SDVTList VTs, EVT VT, SDLoc dl,
5236 ArrayRef<SDValue> Ops,
5237 MachineMemOperand *MMO) {
5239 FoldingSetNodeID ID;
5240 AddNodeIDNode(ID, ISD::MGATHER, VTs, Ops);
5241 ID.AddInteger(VT.getRawBits());
5242 ID.AddInteger(encodeMemSDNodeFlags(ISD::NON_EXTLOAD, ISD::UNINDEXED,
5244 MMO->isNonTemporal(),
5245 MMO->isInvariant()));
5246 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5248 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5249 cast<MaskedGatherSDNode>(E)->refineAlignment(MMO);
5250 return SDValue(E, 0);
5252 MaskedGatherSDNode *N =
5253 new (NodeAllocator) MaskedGatherSDNode(dl.getIROrder(), dl.getDebugLoc(),
5255 CSEMap.InsertNode(N, IP);
5257 return SDValue(N, 0);
5260 SDValue SelectionDAG::getMaskedScatter(SDVTList VTs, EVT VT, SDLoc dl,
5261 ArrayRef<SDValue> Ops,
5262 MachineMemOperand *MMO) {
5263 FoldingSetNodeID ID;
5264 AddNodeIDNode(ID, ISD::MSCATTER, VTs, Ops);
5265 ID.AddInteger(VT.getRawBits());
5266 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
5267 MMO->isNonTemporal(),
5268 MMO->isInvariant()));
5269 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
5271 if (SDNode *E = FindNodeOrInsertPos(ID, dl.getDebugLoc(), IP)) {
5272 cast<MaskedScatterSDNode>(E)->refineAlignment(MMO);
5273 return SDValue(E, 0);
5276 new (NodeAllocator) MaskedScatterSDNode(dl.getIROrder(), dl.getDebugLoc(),
5278 CSEMap.InsertNode(N, IP);
5280 return SDValue(N, 0);
5283 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
5284 SDValue Chain, SDValue Ptr,
5287 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, dl, MVT::i32) };
5288 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
5291 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5292 ArrayRef<SDUse> Ops) {
5293 switch (Ops.size()) {
5294 case 0: return getNode(Opcode, DL, VT);
5295 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
5296 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5297 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5301 // Copy from an SDUse array into an SDValue array for use with
5302 // the regular getNode logic.
5303 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
5304 return getNode(Opcode, DL, VT, NewOps);
5307 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
5308 ArrayRef<SDValue> Ops) {
5309 unsigned NumOps = Ops.size();
5311 case 0: return getNode(Opcode, DL, VT);
5312 case 1: return getNode(Opcode, DL, VT, Ops[0]);
5313 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
5314 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
5320 case ISD::SELECT_CC: {
5321 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
5322 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
5323 "LHS and RHS of condition must have same type!");
5324 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5325 "True and False arms of SelectCC must have same type!");
5326 assert(Ops[2].getValueType() == VT &&
5327 "select_cc node must be of same type as true and false value!");
5331 assert(NumOps == 5 && "BR_CC takes 5 operands!");
5332 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
5333 "LHS/RHS of comparison should match types!");
5340 SDVTList VTs = getVTList(VT);
5342 if (VT != MVT::Glue) {
5343 FoldingSetNodeID ID;
5344 AddNodeIDNode(ID, Opcode, VTs, Ops);
5347 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5348 return SDValue(E, 0);
5350 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5352 CSEMap.InsertNode(N, IP);
5354 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5359 return SDValue(N, 0);
5362 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
5363 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
5364 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
5367 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5368 ArrayRef<SDValue> Ops) {
5369 if (VTList.NumVTs == 1)
5370 return getNode(Opcode, DL, VTList.VTs[0], Ops);
5374 // FIXME: figure out how to safely handle things like
5375 // int foo(int x) { return 1 << (x & 255); }
5376 // int bar() { return foo(256); }
5377 case ISD::SRA_PARTS:
5378 case ISD::SRL_PARTS:
5379 case ISD::SHL_PARTS:
5380 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
5381 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
5382 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5383 else if (N3.getOpcode() == ISD::AND)
5384 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
5385 // If the and is only masking out bits that cannot effect the shift,
5386 // eliminate the and.
5387 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
5388 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
5389 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
5395 // Memoize the node unless it returns a flag.
5397 unsigned NumOps = Ops.size();
5398 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5399 FoldingSetNodeID ID;
5400 AddNodeIDNode(ID, Opcode, VTList, Ops);
5402 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP))
5403 return SDValue(E, 0);
5406 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5407 DL.getDebugLoc(), VTList, Ops[0]);
5408 } else if (NumOps == 2) {
5409 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5410 DL.getDebugLoc(), VTList, Ops[0],
5412 } else if (NumOps == 3) {
5413 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5414 DL.getDebugLoc(), VTList, Ops[0],
5417 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5420 CSEMap.InsertNode(N, IP);
5423 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
5424 DL.getDebugLoc(), VTList, Ops[0]);
5425 } else if (NumOps == 2) {
5426 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
5427 DL.getDebugLoc(), VTList, Ops[0],
5429 } else if (NumOps == 3) {
5430 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
5431 DL.getDebugLoc(), VTList, Ops[0],
5434 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
5439 return SDValue(N, 0);
5442 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
5443 return getNode(Opcode, DL, VTList, None);
5446 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5448 SDValue Ops[] = { N1 };
5449 return getNode(Opcode, DL, VTList, Ops);
5452 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5453 SDValue N1, SDValue N2) {
5454 SDValue Ops[] = { N1, N2 };
5455 return getNode(Opcode, DL, VTList, Ops);
5458 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5459 SDValue N1, SDValue N2, SDValue N3) {
5460 SDValue Ops[] = { N1, N2, N3 };
5461 return getNode(Opcode, DL, VTList, Ops);
5464 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5465 SDValue N1, SDValue N2, SDValue N3,
5467 SDValue Ops[] = { N1, N2, N3, N4 };
5468 return getNode(Opcode, DL, VTList, Ops);
5471 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
5472 SDValue N1, SDValue N2, SDValue N3,
5473 SDValue N4, SDValue N5) {
5474 SDValue Ops[] = { N1, N2, N3, N4, N5 };
5475 return getNode(Opcode, DL, VTList, Ops);
5478 SDVTList SelectionDAG::getVTList(EVT VT) {
5479 return makeVTList(SDNode::getValueTypeList(VT), 1);
5482 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5483 FoldingSetNodeID ID;
5485 ID.AddInteger(VT1.getRawBits());
5486 ID.AddInteger(VT2.getRawBits());
5489 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5491 EVT *Array = Allocator.Allocate<EVT>(2);
5494 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5495 VTListMap.InsertNode(Result, IP);
5497 return Result->getSDVTList();
5500 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5501 FoldingSetNodeID ID;
5503 ID.AddInteger(VT1.getRawBits());
5504 ID.AddInteger(VT2.getRawBits());
5505 ID.AddInteger(VT3.getRawBits());
5508 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5510 EVT *Array = Allocator.Allocate<EVT>(3);
5514 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5515 VTListMap.InsertNode(Result, IP);
5517 return Result->getSDVTList();
5520 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5521 FoldingSetNodeID ID;
5523 ID.AddInteger(VT1.getRawBits());
5524 ID.AddInteger(VT2.getRawBits());
5525 ID.AddInteger(VT3.getRawBits());
5526 ID.AddInteger(VT4.getRawBits());
5529 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5531 EVT *Array = Allocator.Allocate<EVT>(4);
5536 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5537 VTListMap.InsertNode(Result, IP);
5539 return Result->getSDVTList();
5542 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5543 unsigned NumVTs = VTs.size();
5544 FoldingSetNodeID ID;
5545 ID.AddInteger(NumVTs);
5546 for (unsigned index = 0; index < NumVTs; index++) {
5547 ID.AddInteger(VTs[index].getRawBits());
5551 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5553 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5554 std::copy(VTs.begin(), VTs.end(), Array);
5555 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5556 VTListMap.InsertNode(Result, IP);
5558 return Result->getSDVTList();
5562 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5563 /// specified operands. If the resultant node already exists in the DAG,
5564 /// this does not modify the specified node, instead it returns the node that
5565 /// already exists. If the resultant node does not exist in the DAG, the
5566 /// input node is returned. As a degenerate case, if you specify the same
5567 /// input operands as the node already has, the input node is returned.
5568 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5569 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5571 // Check to see if there is no change.
5572 if (Op == N->getOperand(0)) return N;
5574 // See if the modified node already exists.
5575 void *InsertPos = nullptr;
5576 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5579 // Nope it doesn't. Remove the node from its current place in the maps.
5581 if (!RemoveNodeFromCSEMaps(N))
5582 InsertPos = nullptr;
5584 // Now we update the operands.
5585 N->OperandList[0].set(Op);
5587 // If this gets put into a CSE map, add it.
5588 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5592 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5593 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5595 // Check to see if there is no change.
5596 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5597 return N; // No operands changed, just return the input node.
5599 // See if the modified node already exists.
5600 void *InsertPos = nullptr;
5601 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5604 // Nope it doesn't. Remove the node from its current place in the maps.
5606 if (!RemoveNodeFromCSEMaps(N))
5607 InsertPos = nullptr;
5609 // Now we update the operands.
5610 if (N->OperandList[0] != Op1)
5611 N->OperandList[0].set(Op1);
5612 if (N->OperandList[1] != Op2)
5613 N->OperandList[1].set(Op2);
5615 // If this gets put into a CSE map, add it.
5616 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5620 SDNode *SelectionDAG::
5621 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5622 SDValue Ops[] = { Op1, Op2, Op3 };
5623 return UpdateNodeOperands(N, Ops);
5626 SDNode *SelectionDAG::
5627 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5628 SDValue Op3, SDValue Op4) {
5629 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5630 return UpdateNodeOperands(N, Ops);
5633 SDNode *SelectionDAG::
5634 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5635 SDValue Op3, SDValue Op4, SDValue Op5) {
5636 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5637 return UpdateNodeOperands(N, Ops);
5640 SDNode *SelectionDAG::
5641 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5642 unsigned NumOps = Ops.size();
5643 assert(N->getNumOperands() == NumOps &&
5644 "Update with wrong number of operands");
5646 // If no operands changed just return the input node.
5647 if (Ops.empty() || std::equal(Ops.begin(), Ops.end(), N->op_begin()))
5650 // See if the modified node already exists.
5651 void *InsertPos = nullptr;
5652 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5655 // Nope it doesn't. Remove the node from its current place in the maps.
5657 if (!RemoveNodeFromCSEMaps(N))
5658 InsertPos = nullptr;
5660 // Now we update the operands.
5661 for (unsigned i = 0; i != NumOps; ++i)
5662 if (N->OperandList[i] != Ops[i])
5663 N->OperandList[i].set(Ops[i]);
5665 // If this gets put into a CSE map, add it.
5666 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5670 /// DropOperands - Release the operands and set this node to have
5672 void SDNode::DropOperands() {
5673 // Unlike the code in MorphNodeTo that does this, we don't need to
5674 // watch for dead nodes here.
5675 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5681 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5684 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5686 SDVTList VTs = getVTList(VT);
5687 return SelectNodeTo(N, MachineOpc, VTs, None);
5690 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5691 EVT VT, SDValue Op1) {
5692 SDVTList VTs = getVTList(VT);
5693 SDValue Ops[] = { Op1 };
5694 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5697 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5698 EVT VT, SDValue Op1,
5700 SDVTList VTs = getVTList(VT);
5701 SDValue Ops[] = { Op1, Op2 };
5702 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5705 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5706 EVT VT, SDValue Op1,
5707 SDValue Op2, SDValue Op3) {
5708 SDVTList VTs = getVTList(VT);
5709 SDValue Ops[] = { Op1, Op2, Op3 };
5710 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5713 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5714 EVT VT, ArrayRef<SDValue> Ops) {
5715 SDVTList VTs = getVTList(VT);
5716 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5719 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5720 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5721 SDVTList VTs = getVTList(VT1, VT2);
5722 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5725 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5727 SDVTList VTs = getVTList(VT1, VT2);
5728 return SelectNodeTo(N, MachineOpc, VTs, None);
5731 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5732 EVT VT1, EVT VT2, EVT VT3,
5733 ArrayRef<SDValue> Ops) {
5734 SDVTList VTs = getVTList(VT1, VT2, VT3);
5735 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5738 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5739 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5740 ArrayRef<SDValue> Ops) {
5741 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5742 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5745 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5748 SDVTList VTs = getVTList(VT1, VT2);
5749 SDValue Ops[] = { Op1 };
5750 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5753 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5755 SDValue Op1, SDValue Op2) {
5756 SDVTList VTs = getVTList(VT1, VT2);
5757 SDValue Ops[] = { Op1, Op2 };
5758 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5761 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5763 SDValue Op1, SDValue Op2,
5765 SDVTList VTs = getVTList(VT1, VT2);
5766 SDValue Ops[] = { Op1, Op2, Op3 };
5767 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5770 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5771 EVT VT1, EVT VT2, EVT VT3,
5772 SDValue Op1, SDValue Op2,
5774 SDVTList VTs = getVTList(VT1, VT2, VT3);
5775 SDValue Ops[] = { Op1, Op2, Op3 };
5776 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5779 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5780 SDVTList VTs,ArrayRef<SDValue> Ops) {
5781 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5782 // Reset the NodeID to -1.
5787 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5788 /// the line number information on the merged node since it is not possible to
5789 /// preserve the information that operation is associated with multiple lines.
5790 /// This will make the debugger working better at -O0, were there is a higher
5791 /// probability having other instructions associated with that line.
5793 /// For IROrder, we keep the smaller of the two
5794 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5795 DebugLoc NLoc = N->getDebugLoc();
5796 if (NLoc && OptLevel == CodeGenOpt::None && OLoc.getDebugLoc() != NLoc) {
5797 N->setDebugLoc(DebugLoc());
5799 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5800 N->setIROrder(Order);
5804 /// MorphNodeTo - This *mutates* the specified node to have the specified
5805 /// return type, opcode, and operands.
5807 /// Note that MorphNodeTo returns the resultant node. If there is already a
5808 /// node of the specified opcode and operands, it returns that node instead of
5809 /// the current one. Note that the SDLoc need not be the same.
5811 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5812 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5813 /// node, and because it doesn't require CSE recalculation for any of
5814 /// the node's users.
5816 /// However, note that MorphNodeTo recursively deletes dead nodes from the DAG.
5817 /// As a consequence it isn't appropriate to use from within the DAG combiner or
5818 /// the legalizer which maintain worklists that would need to be updated when
5819 /// deleting things.
5820 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5821 SDVTList VTs, ArrayRef<SDValue> Ops) {
5822 unsigned NumOps = Ops.size();
5823 // If an identical node already exists, use it.
5825 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5826 FoldingSetNodeID ID;
5827 AddNodeIDNode(ID, Opc, VTs, Ops);
5828 if (SDNode *ON = FindNodeOrInsertPos(ID, N->getDebugLoc(), IP))
5829 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5832 if (!RemoveNodeFromCSEMaps(N))
5835 // Start the morphing.
5837 N->ValueList = VTs.VTs;
5838 N->NumValues = VTs.NumVTs;
5840 // Clear the operands list, updating used nodes to remove this from their
5841 // use list. Keep track of any operands that become dead as a result.
5842 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5843 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5845 SDNode *Used = Use.getNode();
5847 if (Used->use_empty())
5848 DeadNodeSet.insert(Used);
5851 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5852 // Initialize the memory references information.
5853 MN->setMemRefs(nullptr, nullptr);
5854 // If NumOps is larger than the # of operands we can have in a
5855 // MachineSDNode, reallocate the operand list.
5856 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5857 if (MN->OperandsNeedDelete)
5858 delete[] MN->OperandList;
5859 if (NumOps > array_lengthof(MN->LocalOperands))
5860 // We're creating a final node that will live unmorphed for the
5861 // remainder of the current SelectionDAG iteration, so we can allocate
5862 // the operands directly out of a pool with no recycling metadata.
5863 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5864 Ops.data(), NumOps);
5866 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5867 MN->OperandsNeedDelete = false;
5869 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5871 // If NumOps is larger than the # of operands we currently have, reallocate
5872 // the operand list.
5873 if (NumOps > N->NumOperands) {
5874 if (N->OperandsNeedDelete)
5875 delete[] N->OperandList;
5876 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5877 N->OperandsNeedDelete = true;
5879 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5882 // Delete any nodes that are still dead after adding the uses for the
5884 if (!DeadNodeSet.empty()) {
5885 SmallVector<SDNode *, 16> DeadNodes;
5886 for (SDNode *N : DeadNodeSet)
5888 DeadNodes.push_back(N);
5889 RemoveDeadNodes(DeadNodes);
5893 CSEMap.InsertNode(N, IP); // Memoize the new node.
5898 /// getMachineNode - These are used for target selectors to create a new node
5899 /// with specified return type(s), MachineInstr opcode, and operands.
5901 /// Note that getMachineNode returns the resultant node. If there is already a
5902 /// node of the specified opcode and operands, it returns that node instead of
5903 /// the current one.
5905 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5906 SDVTList VTs = getVTList(VT);
5907 return getMachineNode(Opcode, dl, VTs, None);
5911 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5912 SDVTList VTs = getVTList(VT);
5913 SDValue Ops[] = { Op1 };
5914 return getMachineNode(Opcode, dl, VTs, Ops);
5918 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5919 SDValue Op1, SDValue Op2) {
5920 SDVTList VTs = getVTList(VT);
5921 SDValue Ops[] = { Op1, Op2 };
5922 return getMachineNode(Opcode, dl, VTs, Ops);
5926 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5927 SDValue Op1, SDValue Op2, SDValue Op3) {
5928 SDVTList VTs = getVTList(VT);
5929 SDValue Ops[] = { Op1, Op2, Op3 };
5930 return getMachineNode(Opcode, dl, VTs, Ops);
5934 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5935 ArrayRef<SDValue> Ops) {
5936 SDVTList VTs = getVTList(VT);
5937 return getMachineNode(Opcode, dl, VTs, Ops);
5941 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5942 SDVTList VTs = getVTList(VT1, VT2);
5943 return getMachineNode(Opcode, dl, VTs, None);
5947 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5948 EVT VT1, EVT VT2, SDValue Op1) {
5949 SDVTList VTs = getVTList(VT1, VT2);
5950 SDValue Ops[] = { Op1 };
5951 return getMachineNode(Opcode, dl, VTs, Ops);
5955 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5956 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5957 SDVTList VTs = getVTList(VT1, VT2);
5958 SDValue Ops[] = { Op1, Op2 };
5959 return getMachineNode(Opcode, dl, VTs, Ops);
5963 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5964 EVT VT1, EVT VT2, SDValue Op1,
5965 SDValue Op2, SDValue Op3) {
5966 SDVTList VTs = getVTList(VT1, VT2);
5967 SDValue Ops[] = { Op1, Op2, Op3 };
5968 return getMachineNode(Opcode, dl, VTs, Ops);
5972 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5974 ArrayRef<SDValue> Ops) {
5975 SDVTList VTs = getVTList(VT1, VT2);
5976 return getMachineNode(Opcode, dl, VTs, Ops);
5980 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5981 EVT VT1, EVT VT2, EVT VT3,
5982 SDValue Op1, SDValue Op2) {
5983 SDVTList VTs = getVTList(VT1, VT2, VT3);
5984 SDValue Ops[] = { Op1, Op2 };
5985 return getMachineNode(Opcode, dl, VTs, Ops);
5989 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5990 EVT VT1, EVT VT2, EVT VT3,
5991 SDValue Op1, SDValue Op2, SDValue Op3) {
5992 SDVTList VTs = getVTList(VT1, VT2, VT3);
5993 SDValue Ops[] = { Op1, Op2, Op3 };
5994 return getMachineNode(Opcode, dl, VTs, Ops);
5998 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5999 EVT VT1, EVT VT2, EVT VT3,
6000 ArrayRef<SDValue> Ops) {
6001 SDVTList VTs = getVTList(VT1, VT2, VT3);
6002 return getMachineNode(Opcode, dl, VTs, Ops);
6006 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
6007 EVT VT2, EVT VT3, EVT VT4,
6008 ArrayRef<SDValue> Ops) {
6009 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
6010 return getMachineNode(Opcode, dl, VTs, Ops);
6014 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
6015 ArrayRef<EVT> ResultTys,
6016 ArrayRef<SDValue> Ops) {
6017 SDVTList VTs = getVTList(ResultTys);
6018 return getMachineNode(Opcode, dl, VTs, Ops);
6022 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
6023 ArrayRef<SDValue> OpsArray) {
6024 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
6027 const SDValue *Ops = OpsArray.data();
6028 unsigned NumOps = OpsArray.size();
6031 FoldingSetNodeID ID;
6032 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
6034 if (SDNode *E = FindNodeOrInsertPos(ID, DL.getDebugLoc(), IP)) {
6035 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
6039 // Allocate a new MachineSDNode.
6040 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
6041 DL.getDebugLoc(), VTs);
6043 // Initialize the operands list.
6044 if (NumOps > array_lengthof(N->LocalOperands))
6045 // We're creating a final node that will live unmorphed for the
6046 // remainder of the current SelectionDAG iteration, so we can allocate
6047 // the operands directly out of a pool with no recycling metadata.
6048 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
6051 N->InitOperands(N->LocalOperands, Ops, NumOps);
6052 N->OperandsNeedDelete = false;
6055 CSEMap.InsertNode(N, IP);
6061 /// getTargetExtractSubreg - A convenience function for creating
6062 /// TargetOpcode::EXTRACT_SUBREG nodes.
6064 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
6066 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6067 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
6068 VT, Operand, SRIdxVal);
6069 return SDValue(Subreg, 0);
6072 /// getTargetInsertSubreg - A convenience function for creating
6073 /// TargetOpcode::INSERT_SUBREG nodes.
6075 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
6076 SDValue Operand, SDValue Subreg) {
6077 SDValue SRIdxVal = getTargetConstant(SRIdx, DL, MVT::i32);
6078 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
6079 VT, Operand, Subreg, SRIdxVal);
6080 return SDValue(Result, 0);
6083 /// getNodeIfExists - Get the specified node if it's already available, or
6084 /// else return NULL.
6085 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
6086 ArrayRef<SDValue> Ops,
6087 const SDNodeFlags *Flags) {
6088 if (VTList.VTs[VTList.NumVTs - 1] != MVT::Glue) {
6089 FoldingSetNodeID ID;
6090 AddNodeIDNode(ID, Opcode, VTList, Ops);
6091 AddNodeIDFlags(ID, Opcode, Flags);
6093 if (SDNode *E = FindNodeOrInsertPos(ID, DebugLoc(), IP))
6099 /// getDbgValue - Creates a SDDbgValue node.
6102 SDDbgValue *SelectionDAG::getDbgValue(MDNode *Var, MDNode *Expr, SDNode *N,
6103 unsigned R, bool IsIndirect, uint64_t Off,
6104 DebugLoc DL, unsigned O) {
6105 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6106 "Expected inlined-at fields to agree");
6107 return new (DbgInfo->getAlloc())
6108 SDDbgValue(Var, Expr, N, R, IsIndirect, Off, DL, O);
6112 SDDbgValue *SelectionDAG::getConstantDbgValue(MDNode *Var, MDNode *Expr,
6113 const Value *C, uint64_t Off,
6114 DebugLoc DL, unsigned O) {
6115 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6116 "Expected inlined-at fields to agree");
6117 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, C, Off, DL, O);
6121 SDDbgValue *SelectionDAG::getFrameIndexDbgValue(MDNode *Var, MDNode *Expr,
6122 unsigned FI, uint64_t Off,
6123 DebugLoc DL, unsigned O) {
6124 assert(cast<DILocalVariable>(Var)->isValidLocationForIntrinsic(DL) &&
6125 "Expected inlined-at fields to agree");
6126 return new (DbgInfo->getAlloc()) SDDbgValue(Var, Expr, FI, Off, DL, O);
6131 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
6132 /// pointed to by a use iterator is deleted, increment the use iterator
6133 /// so that it doesn't dangle.
6135 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
6136 SDNode::use_iterator &UI;
6137 SDNode::use_iterator &UE;
6139 void NodeDeleted(SDNode *N, SDNode *E) override {
6140 // Increment the iterator as needed.
6141 while (UI != UE && N == *UI)
6146 RAUWUpdateListener(SelectionDAG &d,
6147 SDNode::use_iterator &ui,
6148 SDNode::use_iterator &ue)
6149 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
6154 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6155 /// This can cause recursive merging of nodes in the DAG.
6157 /// This version assumes From has a single result value.
6159 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
6160 SDNode *From = FromN.getNode();
6161 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
6162 "Cannot replace with this method!");
6163 assert(From != To.getNode() && "Cannot replace uses of with self");
6165 // Iterate over all the existing uses of From. New uses will be added
6166 // to the beginning of the use list, which we avoid visiting.
6167 // This specifically avoids visiting uses of From that arise while the
6168 // replacement is happening, because any such uses would be the result
6169 // of CSE: If an existing node looks like From after one of its operands
6170 // is replaced by To, we don't want to replace of all its users with To
6171 // too. See PR3018 for more info.
6172 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6173 RAUWUpdateListener Listener(*this, UI, UE);
6177 // This node is about to morph, remove its old self from the CSE maps.
6178 RemoveNodeFromCSEMaps(User);
6180 // A user can appear in a use list multiple times, and when this
6181 // happens the uses are usually next to each other in the list.
6182 // To help reduce the number of CSE recomputations, process all
6183 // the uses of this user that we can find this way.
6185 SDUse &Use = UI.getUse();
6188 } while (UI != UE && *UI == User);
6190 // Now that we have modified User, add it back to the CSE maps. If it
6191 // already exists there, recursively merge the results together.
6192 AddModifiedNodeToCSEMaps(User);
6195 // If we just RAUW'd the root, take note.
6196 if (FromN == getRoot())
6200 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6201 /// This can cause recursive merging of nodes in the DAG.
6203 /// This version assumes that for each value of From, there is a
6204 /// corresponding value in To in the same position with the same type.
6206 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
6208 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
6209 assert((!From->hasAnyUseOfValue(i) ||
6210 From->getValueType(i) == To->getValueType(i)) &&
6211 "Cannot use this version of ReplaceAllUsesWith!");
6214 // Handle the trivial case.
6218 // Iterate over just the existing users of From. See the comments in
6219 // the ReplaceAllUsesWith above.
6220 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6221 RAUWUpdateListener Listener(*this, UI, UE);
6225 // This node is about to morph, remove its old self from the CSE maps.
6226 RemoveNodeFromCSEMaps(User);
6228 // A user can appear in a use list multiple times, and when this
6229 // happens the uses are usually next to each other in the list.
6230 // To help reduce the number of CSE recomputations, process all
6231 // the uses of this user that we can find this way.
6233 SDUse &Use = UI.getUse();
6236 } while (UI != UE && *UI == User);
6238 // Now that we have modified User, add it back to the CSE maps. If it
6239 // already exists there, recursively merge the results together.
6240 AddModifiedNodeToCSEMaps(User);
6243 // If we just RAUW'd the root, take note.
6244 if (From == getRoot().getNode())
6245 setRoot(SDValue(To, getRoot().getResNo()));
6248 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
6249 /// This can cause recursive merging of nodes in the DAG.
6251 /// This version can replace From with any result values. To must match the
6252 /// number and types of values returned by From.
6253 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
6254 if (From->getNumValues() == 1) // Handle the simple case efficiently.
6255 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
6257 // Iterate over just the existing users of From. See the comments in
6258 // the ReplaceAllUsesWith above.
6259 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
6260 RAUWUpdateListener Listener(*this, UI, UE);
6264 // This node is about to morph, remove its old self from the CSE maps.
6265 RemoveNodeFromCSEMaps(User);
6267 // A user can appear in a use list multiple times, and when this
6268 // happens the uses are usually next to each other in the list.
6269 // To help reduce the number of CSE recomputations, process all
6270 // the uses of this user that we can find this way.
6272 SDUse &Use = UI.getUse();
6273 const SDValue &ToOp = To[Use.getResNo()];
6276 } while (UI != UE && *UI == User);
6278 // Now that we have modified User, add it back to the CSE maps. If it
6279 // already exists there, recursively merge the results together.
6280 AddModifiedNodeToCSEMaps(User);
6283 // If we just RAUW'd the root, take note.
6284 if (From == getRoot().getNode())
6285 setRoot(SDValue(To[getRoot().getResNo()]));
6288 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
6289 /// uses of other values produced by From.getNode() alone. The Deleted
6290 /// vector is handled the same way as for ReplaceAllUsesWith.
6291 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
6292 // Handle the really simple, really trivial case efficiently.
6293 if (From == To) return;
6295 // Handle the simple, trivial, case efficiently.
6296 if (From.getNode()->getNumValues() == 1) {
6297 ReplaceAllUsesWith(From, To);
6301 // Iterate over just the existing users of From. See the comments in
6302 // the ReplaceAllUsesWith above.
6303 SDNode::use_iterator UI = From.getNode()->use_begin(),
6304 UE = From.getNode()->use_end();
6305 RAUWUpdateListener Listener(*this, UI, UE);
6308 bool UserRemovedFromCSEMaps = false;
6310 // A user can appear in a use list multiple times, and when this
6311 // happens the uses are usually next to each other in the list.
6312 // To help reduce the number of CSE recomputations, process all
6313 // the uses of this user that we can find this way.
6315 SDUse &Use = UI.getUse();
6317 // Skip uses of different values from the same node.
6318 if (Use.getResNo() != From.getResNo()) {
6323 // If this node hasn't been modified yet, it's still in the CSE maps,
6324 // so remove its old self from the CSE maps.
6325 if (!UserRemovedFromCSEMaps) {
6326 RemoveNodeFromCSEMaps(User);
6327 UserRemovedFromCSEMaps = true;
6332 } while (UI != UE && *UI == User);
6334 // We are iterating over all uses of the From node, so if a use
6335 // doesn't use the specific value, no changes are made.
6336 if (!UserRemovedFromCSEMaps)
6339 // Now that we have modified User, add it back to the CSE maps. If it
6340 // already exists there, recursively merge the results together.
6341 AddModifiedNodeToCSEMaps(User);
6344 // If we just RAUW'd the root, take note.
6345 if (From == getRoot())
6350 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
6351 /// to record information about a use.
6358 /// operator< - Sort Memos by User.
6359 bool operator<(const UseMemo &L, const UseMemo &R) {
6360 return (intptr_t)L.User < (intptr_t)R.User;
6364 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
6365 /// uses of other values produced by From.getNode() alone. The same value
6366 /// may appear in both the From and To list. The Deleted vector is
6367 /// handled the same way as for ReplaceAllUsesWith.
6368 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
6371 // Handle the simple, trivial case efficiently.
6373 return ReplaceAllUsesOfValueWith(*From, *To);
6375 // Read up all the uses and make records of them. This helps
6376 // processing new uses that are introduced during the
6377 // replacement process.
6378 SmallVector<UseMemo, 4> Uses;
6379 for (unsigned i = 0; i != Num; ++i) {
6380 unsigned FromResNo = From[i].getResNo();
6381 SDNode *FromNode = From[i].getNode();
6382 for (SDNode::use_iterator UI = FromNode->use_begin(),
6383 E = FromNode->use_end(); UI != E; ++UI) {
6384 SDUse &Use = UI.getUse();
6385 if (Use.getResNo() == FromResNo) {
6386 UseMemo Memo = { *UI, i, &Use };
6387 Uses.push_back(Memo);
6392 // Sort the uses, so that all the uses from a given User are together.
6393 std::sort(Uses.begin(), Uses.end());
6395 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
6396 UseIndex != UseIndexEnd; ) {
6397 // We know that this user uses some value of From. If it is the right
6398 // value, update it.
6399 SDNode *User = Uses[UseIndex].User;
6401 // This node is about to morph, remove its old self from the CSE maps.
6402 RemoveNodeFromCSEMaps(User);
6404 // The Uses array is sorted, so all the uses for a given User
6405 // are next to each other in the list.
6406 // To help reduce the number of CSE recomputations, process all
6407 // the uses of this user that we can find this way.
6409 unsigned i = Uses[UseIndex].Index;
6410 SDUse &Use = *Uses[UseIndex].Use;
6414 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
6416 // Now that we have modified User, add it back to the CSE maps. If it
6417 // already exists there, recursively merge the results together.
6418 AddModifiedNodeToCSEMaps(User);
6422 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
6423 /// based on their topological order. It returns the maximum id and a vector
6424 /// of the SDNodes* in assigned order by reference.
6425 unsigned SelectionDAG::AssignTopologicalOrder() {
6427 unsigned DAGSize = 0;
6429 // SortedPos tracks the progress of the algorithm. Nodes before it are
6430 // sorted, nodes after it are unsorted. When the algorithm completes
6431 // it is at the end of the list.
6432 allnodes_iterator SortedPos = allnodes_begin();
6434 // Visit all the nodes. Move nodes with no operands to the front of
6435 // the list immediately. Annotate nodes that do have operands with their
6436 // operand count. Before we do this, the Node Id fields of the nodes
6437 // may contain arbitrary values. After, the Node Id fields for nodes
6438 // before SortedPos will contain the topological sort index, and the
6439 // Node Id fields for nodes At SortedPos and after will contain the
6440 // count of outstanding operands.
6441 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
6443 checkForCycles(N, this);
6444 unsigned Degree = N->getNumOperands();
6446 // A node with no uses, add it to the result array immediately.
6447 N->setNodeId(DAGSize++);
6448 allnodes_iterator Q = N;
6450 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
6451 assert(SortedPos != AllNodes.end() && "Overran node list");
6454 // Temporarily use the Node Id as scratch space for the degree count.
6455 N->setNodeId(Degree);
6459 // Visit all the nodes. As we iterate, move nodes into sorted order,
6460 // such that by the time the end is reached all nodes will be sorted.
6461 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
6463 checkForCycles(N, this);
6464 // N is in sorted position, so all its uses have one less operand
6465 // that needs to be sorted.
6466 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
6469 unsigned Degree = P->getNodeId();
6470 assert(Degree != 0 && "Invalid node degree");
6473 // All of P's operands are sorted, so P may sorted now.
6474 P->setNodeId(DAGSize++);
6476 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6477 assert(SortedPos != AllNodes.end() && "Overran node list");
6480 // Update P's outstanding operand count.
6481 P->setNodeId(Degree);
6484 if (I == SortedPos) {
6487 dbgs() << "Overran sorted position:\n";
6488 S->dumprFull(this); dbgs() << "\n";
6489 dbgs() << "Checking if this is due to cycles\n";
6490 checkForCycles(this, true);
6492 llvm_unreachable(nullptr);
6496 assert(SortedPos == AllNodes.end() &&
6497 "Topological sort incomplete!");
6498 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6499 "First node in topological sort is not the entry token!");
6500 assert(AllNodes.front().getNodeId() == 0 &&
6501 "First node in topological sort has non-zero id!");
6502 assert(AllNodes.front().getNumOperands() == 0 &&
6503 "First node in topological sort has operands!");
6504 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6505 "Last node in topologic sort has unexpected id!");
6506 assert(AllNodes.back().use_empty() &&
6507 "Last node in topologic sort has users!");
6508 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6512 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6513 /// value is produced by SD.
6514 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6516 assert(DbgInfo->getSDDbgValues(SD).empty() || SD->getHasDebugValue());
6517 SD->setHasDebugValue(true);
6519 DbgInfo->add(DB, SD, isParameter);
6522 /// TransferDbgValues - Transfer SDDbgValues.
6523 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6524 if (From == To || !From.getNode()->getHasDebugValue())
6526 SDNode *FromNode = From.getNode();
6527 SDNode *ToNode = To.getNode();
6528 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6529 SmallVector<SDDbgValue *, 2> ClonedDVs;
6530 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6532 SDDbgValue *Dbg = *I;
6533 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6535 getDbgValue(Dbg->getVariable(), Dbg->getExpression(), ToNode,
6536 To.getResNo(), Dbg->isIndirect(), Dbg->getOffset(),
6537 Dbg->getDebugLoc(), Dbg->getOrder());
6538 ClonedDVs.push_back(Clone);
6541 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6542 E = ClonedDVs.end(); I != E; ++I)
6543 AddDbgValue(*I, ToNode, false);
6546 //===----------------------------------------------------------------------===//
6548 //===----------------------------------------------------------------------===//
6550 HandleSDNode::~HandleSDNode() {
6554 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6555 DebugLoc DL, const GlobalValue *GA,
6556 EVT VT, int64_t o, unsigned char TF)
6557 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6561 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6562 SDValue X, unsigned SrcAS,
6564 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6565 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6567 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6568 EVT memvt, MachineMemOperand *mmo)
6569 : SDNode(Opc, Order, dl, VTs), 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(isNonTemporal() == MMO->isNonTemporal() &&
6574 "Non-temporal encoding error!");
6575 // We check here that the size of the memory operand fits within the size of
6576 // the MMO. This is because the MMO might indicate only a possible address
6577 // range instead of specifying the affected memory addresses precisely.
6578 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6581 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6582 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6583 : SDNode(Opc, Order, dl, VTs, Ops),
6584 MemoryVT(memvt), MMO(mmo) {
6585 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6586 MMO->isNonTemporal(), MMO->isInvariant());
6587 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6588 assert(memvt.getStoreSize() <= MMO->getSize() && "Size mismatch!");
6591 /// Profile - Gather unique data for the node.
6593 void SDNode::Profile(FoldingSetNodeID &ID) const {
6594 AddNodeIDNode(ID, this);
6599 std::vector<EVT> VTs;
6602 VTs.reserve(MVT::LAST_VALUETYPE);
6603 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6604 VTs.push_back(MVT((MVT::SimpleValueType)i));
6609 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6610 static ManagedStatic<EVTArray> SimpleVTArray;
6611 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6613 /// getValueTypeList - Return a pointer to the specified value type.
6615 const EVT *SDNode::getValueTypeList(EVT VT) {
6616 if (VT.isExtended()) {
6617 sys::SmartScopedLock<true> Lock(*VTMutex);
6618 return &(*EVTs->insert(VT).first);
6620 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6621 "Value type out of range!");
6622 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6626 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6627 /// indicated value. This method ignores uses of other values defined by this
6629 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6630 assert(Value < getNumValues() && "Bad value!");
6632 // TODO: Only iterate over uses of a given value of the node
6633 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6634 if (UI.getUse().getResNo() == Value) {
6641 // Found exactly the right number of uses?
6646 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6647 /// value. This method ignores uses of other values defined by this operation.
6648 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6649 assert(Value < getNumValues() && "Bad value!");
6651 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6652 if (UI.getUse().getResNo() == Value)
6659 /// isOnlyUserOf - Return true if this node is the only use of N.
6661 bool SDNode::isOnlyUserOf(SDNode *N) const {
6663 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6674 /// isOperand - Return true if this node is an operand of N.
6676 bool SDValue::isOperandOf(SDNode *N) const {
6677 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6678 if (*this == N->getOperand(i))
6683 bool SDNode::isOperandOf(SDNode *N) const {
6684 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6685 if (this == N->OperandList[i].getNode())
6690 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6691 /// be a chain) reaches the specified operand without crossing any
6692 /// side-effecting instructions on any chain path. In practice, this looks
6693 /// through token factors and non-volatile loads. In order to remain efficient,
6694 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6695 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6696 unsigned Depth) const {
6697 if (*this == Dest) return true;
6699 // Don't search too deeply, we just want to be able to see through
6700 // TokenFactor's etc.
6701 if (Depth == 0) return false;
6703 // If this is a token factor, all inputs to the TF happen in parallel. If any
6704 // of the operands of the TF does not reach dest, then we cannot do the xform.
6705 if (getOpcode() == ISD::TokenFactor) {
6706 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6707 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6712 // Loads don't have side effects, look through them.
6713 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6714 if (!Ld->isVolatile())
6715 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6720 /// hasPredecessor - Return true if N is a predecessor of this node.
6721 /// N is either an operand of this node, or can be reached by recursively
6722 /// traversing up the operands.
6723 /// NOTE: This is an expensive method. Use it carefully.
6724 bool SDNode::hasPredecessor(const SDNode *N) const {
6725 SmallPtrSet<const SDNode *, 32> Visited;
6726 SmallVector<const SDNode *, 16> Worklist;
6727 return hasPredecessorHelper(N, Visited, Worklist);
6731 SDNode::hasPredecessorHelper(const SDNode *N,
6732 SmallPtrSetImpl<const SDNode *> &Visited,
6733 SmallVectorImpl<const SDNode *> &Worklist) const {
6734 if (Visited.empty()) {
6735 Worklist.push_back(this);
6737 // Take a look in the visited set. If we've already encountered this node
6738 // we needn't search further.
6739 if (Visited.count(N))
6743 // Haven't visited N yet. Continue the search.
6744 while (!Worklist.empty()) {
6745 const SDNode *M = Worklist.pop_back_val();
6746 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6747 SDNode *Op = M->getOperand(i).getNode();
6748 if (Visited.insert(Op).second)
6749 Worklist.push_back(Op);
6758 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6759 assert(Num < NumOperands && "Invalid child # of SDNode!");
6760 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6763 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6764 assert(N->getNumValues() == 1 &&
6765 "Can't unroll a vector with multiple results!");
6767 EVT VT = N->getValueType(0);
6768 unsigned NE = VT.getVectorNumElements();
6769 EVT EltVT = VT.getVectorElementType();
6772 SmallVector<SDValue, 8> Scalars;
6773 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6775 // If ResNE is 0, fully unroll the vector op.
6778 else if (NE > ResNE)
6782 for (i= 0; i != NE; ++i) {
6783 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6784 SDValue Operand = N->getOperand(j);
6785 EVT OperandVT = Operand.getValueType();
6786 if (OperandVT.isVector()) {
6787 // A vector operand; extract a single element.
6788 EVT OperandEltVT = OperandVT.getVectorElementType();
6789 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6792 getConstant(i, dl, TLI->getVectorIdxTy()));
6794 // A scalar operand; just use it as is.
6795 Operands[j] = Operand;
6799 switch (N->getOpcode()) {
6801 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6804 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6811 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6812 getShiftAmountOperand(Operands[0].getValueType(),
6815 case ISD::SIGN_EXTEND_INREG:
6816 case ISD::FP_ROUND_INREG: {
6817 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6818 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6820 getValueType(ExtVT)));
6825 for (; i < ResNE; ++i)
6826 Scalars.push_back(getUNDEF(EltVT));
6828 return getNode(ISD::BUILD_VECTOR, dl,
6829 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6833 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6834 /// location that is 'Dist' units away from the location that the 'Base' load
6835 /// is loading from.
6836 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6837 unsigned Bytes, int Dist) const {
6838 if (LD->getChain() != Base->getChain())
6840 EVT VT = LD->getValueType(0);
6841 if (VT.getSizeInBits() / 8 != Bytes)
6844 SDValue Loc = LD->getOperand(1);
6845 SDValue BaseLoc = Base->getOperand(1);
6846 if (Loc.getOpcode() == ISD::FrameIndex) {
6847 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6849 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6850 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6851 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6852 int FS = MFI->getObjectSize(FI);
6853 int BFS = MFI->getObjectSize(BFI);
6854 if (FS != BFS || FS != (int)Bytes) return false;
6855 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6859 if (isBaseWithConstantOffset(Loc)) {
6860 int64_t LocOffset = cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue();
6861 if (Loc.getOperand(0) == BaseLoc) {
6862 // If the base location is a simple address with no offset itself, then
6863 // the second load's first add operand should be the base address.
6864 if (LocOffset == Dist * (int)Bytes)
6866 } else if (isBaseWithConstantOffset(BaseLoc)) {
6867 // The base location itself has an offset, so subtract that value from the
6868 // second load's offset before comparing to distance * size.
6870 cast<ConstantSDNode>(BaseLoc.getOperand(1))->getSExtValue();
6871 if (Loc.getOperand(0) == BaseLoc.getOperand(0)) {
6872 if ((LocOffset - BOffset) == Dist * (int)Bytes)
6877 const GlobalValue *GV1 = nullptr;
6878 const GlobalValue *GV2 = nullptr;
6879 int64_t Offset1 = 0;
6880 int64_t Offset2 = 0;
6881 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6882 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6883 if (isGA1 && isGA2 && GV1 == GV2)
6884 return Offset1 == (Offset2 + Dist*Bytes);
6889 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6890 /// it cannot be inferred.
6891 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6892 // If this is a GlobalAddress + cst, return the alignment.
6893 const GlobalValue *GV;
6894 int64_t GVOffset = 0;
6895 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6896 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6897 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6898 llvm::computeKnownBits(const_cast<GlobalValue *>(GV), KnownZero, KnownOne,
6899 *TLI->getDataLayout());
6900 unsigned AlignBits = KnownZero.countTrailingOnes();
6901 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6903 return MinAlign(Align, GVOffset);
6906 // If this is a direct reference to a stack slot, use information about the
6907 // stack slot's alignment.
6908 int FrameIdx = 1 << 31;
6909 int64_t FrameOffset = 0;
6910 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6911 FrameIdx = FI->getIndex();
6912 } else if (isBaseWithConstantOffset(Ptr) &&
6913 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6915 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6916 FrameOffset = Ptr.getConstantOperandVal(1);
6919 if (FrameIdx != (1 << 31)) {
6920 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6921 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6929 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6930 /// which is split (or expanded) into two not necessarily identical pieces.
6931 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6932 // Currently all types are split in half.
6934 if (!VT.isVector()) {
6935 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6937 unsigned NumElements = VT.getVectorNumElements();
6938 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6939 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6942 return std::make_pair(LoVT, HiVT);
6945 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6947 std::pair<SDValue, SDValue>
6948 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6950 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6951 N.getValueType().getVectorNumElements() &&
6952 "More vector elements requested than available!");
6954 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6955 getConstant(0, DL, TLI->getVectorIdxTy()));
6956 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6957 getConstant(LoVT.getVectorNumElements(), DL,
6958 TLI->getVectorIdxTy()));
6959 return std::make_pair(Lo, Hi);
6962 void SelectionDAG::ExtractVectorElements(SDValue Op,
6963 SmallVectorImpl<SDValue> &Args,
6964 unsigned Start, unsigned Count) {
6965 EVT VT = Op.getValueType();
6967 Count = VT.getVectorNumElements();
6969 EVT EltVT = VT.getVectorElementType();
6970 EVT IdxTy = TLI->getVectorIdxTy();
6972 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6973 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6974 Op, getConstant(i, SL, IdxTy)));
6978 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6979 unsigned GlobalAddressSDNode::getAddressSpace() const {
6980 return getGlobal()->getType()->getAddressSpace();
6984 Type *ConstantPoolSDNode::getType() const {
6985 if (isMachineConstantPoolEntry())
6986 return Val.MachineCPVal->getType();
6987 return Val.ConstVal->getType();
6990 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6992 unsigned &SplatBitSize,
6994 unsigned MinSplatBits,
6995 bool isBigEndian) const {
6996 EVT VT = getValueType(0);
6997 assert(VT.isVector() && "Expected a vector type");
6998 unsigned sz = VT.getSizeInBits();
6999 if (MinSplatBits > sz)
7002 SplatValue = APInt(sz, 0);
7003 SplatUndef = APInt(sz, 0);
7005 // Get the bits. Bits with undefined values (when the corresponding element
7006 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
7007 // in SplatValue. If any of the values are not constant, give up and return
7009 unsigned int nOps = getNumOperands();
7010 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
7011 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
7013 for (unsigned j = 0; j < nOps; ++j) {
7014 unsigned i = isBigEndian ? nOps-1-j : j;
7015 SDValue OpVal = getOperand(i);
7016 unsigned BitPos = j * EltBitSize;
7018 if (OpVal.getOpcode() == ISD::UNDEF)
7019 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
7020 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
7021 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
7022 zextOrTrunc(sz) << BitPos;
7023 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
7024 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
7029 // The build_vector is all constants or undefs. Find the smallest element
7030 // size that splats the vector.
7032 HasAnyUndefs = (SplatUndef != 0);
7035 unsigned HalfSize = sz / 2;
7036 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
7037 APInt LowValue = SplatValue.trunc(HalfSize);
7038 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
7039 APInt LowUndef = SplatUndef.trunc(HalfSize);
7041 // If the two halves do not match (ignoring undef bits), stop here.
7042 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
7043 MinSplatBits > HalfSize)
7046 SplatValue = HighValue | LowValue;
7047 SplatUndef = HighUndef & LowUndef;
7056 SDValue BuildVectorSDNode::getSplatValue(BitVector *UndefElements) const {
7057 if (UndefElements) {
7058 UndefElements->clear();
7059 UndefElements->resize(getNumOperands());
7062 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7063 SDValue Op = getOperand(i);
7064 if (Op.getOpcode() == ISD::UNDEF) {
7066 (*UndefElements)[i] = true;
7067 } else if (!Splatted) {
7069 } else if (Splatted != Op) {
7075 assert(getOperand(0).getOpcode() == ISD::UNDEF &&
7076 "Can only have a splat without a constant for all undefs.");
7077 return getOperand(0);
7084 BuildVectorSDNode::getConstantSplatNode(BitVector *UndefElements) const {
7085 return dyn_cast_or_null<ConstantSDNode>(
7086 getSplatValue(UndefElements).getNode());
7090 BuildVectorSDNode::getConstantFPSplatNode(BitVector *UndefElements) const {
7091 return dyn_cast_or_null<ConstantFPSDNode>(
7092 getSplatValue(UndefElements).getNode());
7095 bool BuildVectorSDNode::isConstant() const {
7096 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
7097 unsigned Opc = getOperand(i).getOpcode();
7098 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
7104 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
7105 // Find the first non-undef value in the shuffle mask.
7107 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
7110 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
7112 // Make sure all remaining elements are either undef or the same as the first
7114 for (int Idx = Mask[i]; i != e; ++i)
7115 if (Mask[i] >= 0 && Mask[i] != Idx)
7121 static void checkForCyclesHelper(const SDNode *N,
7122 SmallPtrSetImpl<const SDNode*> &Visited,
7123 SmallPtrSetImpl<const SDNode*> &Checked,
7124 const llvm::SelectionDAG *DAG) {
7125 // If this node has already been checked, don't check it again.
7126 if (Checked.count(N))
7129 // If a node has already been visited on this depth-first walk, reject it as
7131 if (!Visited.insert(N).second) {
7132 errs() << "Detected cycle in SelectionDAG\n";
7133 dbgs() << "Offending node:\n";
7134 N->dumprFull(DAG); dbgs() << "\n";
7138 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
7139 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
7146 void llvm::checkForCycles(const llvm::SDNode *N,
7147 const llvm::SelectionDAG *DAG,
7155 assert(N && "Checking nonexistent SDNode");
7156 SmallPtrSet<const SDNode*, 32> visited;
7157 SmallPtrSet<const SDNode*, 32> checked;
7158 checkForCyclesHelper(N, visited, checked, DAG);
7163 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
7164 checkForCycles(DAG->getRoot().getNode(), DAG, force);