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"
53 /// makeVTList - Return an instance of the SDVTList struct initialized with the
54 /// specified members.
55 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) {
56 SDVTList Res = {VTs, NumVTs};
60 // Default null implementations of the callbacks.
61 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {}
62 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {}
64 //===----------------------------------------------------------------------===//
65 // ConstantFPSDNode Class
66 //===----------------------------------------------------------------------===//
68 /// isExactlyValue - We don't rely on operator== working on double values, as
69 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
70 /// As such, this method can be used to do an exact bit-for-bit comparison of
71 /// two floating point values.
72 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
73 return getValueAPF().bitwiseIsEqual(V);
76 bool ConstantFPSDNode::isValueValidForType(EVT VT,
78 assert(VT.isFloatingPoint() && "Can only convert between FP types");
80 // convert modifies in place, so make a copy.
81 APFloat Val2 = APFloat(Val);
83 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT),
84 APFloat::rmNearestTiesToEven,
89 //===----------------------------------------------------------------------===//
91 //===----------------------------------------------------------------------===//
93 /// isBuildVectorAllOnes - Return true if the specified node is a
94 /// BUILD_VECTOR where all of the elements are ~0 or undef.
95 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
96 // Look through a bit convert.
97 if (N->getOpcode() == ISD::BITCAST)
98 N = N->getOperand(0).getNode();
100 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
102 unsigned i = 0, e = N->getNumOperands();
104 // Skip over all of the undef values.
105 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
108 // Do not accept an all-undef vector.
109 if (i == e) return false;
111 // Do not accept build_vectors that aren't all constants or which have non-~0
112 // elements. We have to be a bit careful here, as the type of the constant
113 // may not be the same as the type of the vector elements due to type
114 // legalization (the elements are promoted to a legal type for the target and
115 // a vector of a type may be legal when the base element type is not).
116 // We only want to check enough bits to cover the vector elements, because
117 // we care if the resultant vector is all ones, not whether the individual
119 SDValue NotZero = N->getOperand(i);
120 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits();
121 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) {
122 if (CN->getAPIntValue().countTrailingOnes() < EltSize)
124 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) {
125 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize)
130 // Okay, we have at least one ~0 value, check to see if the rest match or are
131 // undefs. Even with the above element type twiddling, this should be OK, as
132 // the same type legalization should have applied to all the elements.
133 for (++i; i != e; ++i)
134 if (N->getOperand(i) != NotZero &&
135 N->getOperand(i).getOpcode() != ISD::UNDEF)
141 /// isBuildVectorAllZeros - Return true if the specified node is a
142 /// BUILD_VECTOR where all of the elements are 0 or undef.
143 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
144 // Look through a bit convert.
145 if (N->getOpcode() == ISD::BITCAST)
146 N = N->getOperand(0).getNode();
148 if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
150 unsigned i = 0, e = N->getNumOperands();
152 // Skip over all of the undef values.
153 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
156 // Do not accept an all-undef vector.
157 if (i == e) return false;
159 // Do not accept build_vectors that aren't all constants or which have non-0
161 SDValue Zero = N->getOperand(i);
162 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) {
163 if (!CN->isNullValue())
165 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) {
166 if (!CFPN->getValueAPF().isPosZero())
171 // Okay, we have at least one 0 value, check to see if the rest match or are
173 for (++i; i != e; ++i)
174 if (N->getOperand(i) != Zero &&
175 N->getOperand(i).getOpcode() != ISD::UNDEF)
180 /// \brief Return true if the specified node is a BUILD_VECTOR node of
181 /// all ConstantSDNode or undef.
182 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) {
183 if (N->getOpcode() != ISD::BUILD_VECTOR)
186 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
187 SDValue Op = N->getOperand(i);
188 if (Op.getOpcode() == ISD::UNDEF)
190 if (!isa<ConstantSDNode>(Op))
196 /// isScalarToVector - Return true if the specified node is a
197 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
198 /// element is not an undef.
199 bool ISD::isScalarToVector(const SDNode *N) {
200 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
203 if (N->getOpcode() != ISD::BUILD_VECTOR)
205 if (N->getOperand(0).getOpcode() == ISD::UNDEF)
207 unsigned NumElems = N->getNumOperands();
210 for (unsigned i = 1; i < NumElems; ++i) {
211 SDValue V = N->getOperand(i);
212 if (V.getOpcode() != ISD::UNDEF)
218 /// allOperandsUndef - Return true if the node has at least one operand
219 /// and all operands of the specified node are ISD::UNDEF.
220 bool ISD::allOperandsUndef(const SDNode *N) {
221 // Return false if the node has no operands.
222 // This is "logically inconsistent" with the definition of "all" but
223 // is probably the desired behavior.
224 if (N->getNumOperands() == 0)
227 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i)
228 if (N->getOperand(i).getOpcode() != ISD::UNDEF)
234 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) {
237 return ISD::ANY_EXTEND;
239 return ISD::SIGN_EXTEND;
241 return ISD::ZERO_EXTEND;
246 llvm_unreachable("Invalid LoadExtType");
249 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
250 /// when given the operation for (X op Y).
251 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
252 // To perform this operation, we just need to swap the L and G bits of the
254 unsigned OldL = (Operation >> 2) & 1;
255 unsigned OldG = (Operation >> 1) & 1;
256 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits
257 (OldL << 1) | // New G bit
258 (OldG << 2)); // New L bit.
261 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
262 /// 'op' is a valid SetCC operation.
263 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
264 unsigned Operation = Op;
266 Operation ^= 7; // Flip L, G, E bits, but not U.
268 Operation ^= 15; // Flip all of the condition bits.
270 if (Operation > ISD::SETTRUE2)
271 Operation &= ~8; // Don't let N and U bits get set.
273 return ISD::CondCode(Operation);
277 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
278 /// signed operation and 2 if the result is an unsigned comparison. Return zero
279 /// if the operation does not depend on the sign of the input (setne and seteq).
280 static int isSignedOp(ISD::CondCode Opcode) {
282 default: llvm_unreachable("Illegal integer setcc operation!");
284 case ISD::SETNE: return 0;
288 case ISD::SETGE: return 1;
292 case ISD::SETUGE: return 2;
296 /// getSetCCOrOperation - Return the result of a logical OR between different
297 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function
298 /// returns SETCC_INVALID if it is not possible to represent the resultant
300 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
302 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
303 // Cannot fold a signed integer setcc with an unsigned integer setcc.
304 return ISD::SETCC_INVALID;
306 unsigned Op = Op1 | Op2; // Combine all of the condition bits.
308 // If the N and U bits get set then the resultant comparison DOES suddenly
309 // care about orderedness, and is true when ordered.
310 if (Op > ISD::SETTRUE2)
311 Op &= ~16; // Clear the U bit if the N bit is set.
313 // Canonicalize illegal integer setcc's.
314 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT
317 return ISD::CondCode(Op);
320 /// getSetCCAndOperation - Return the result of a logical AND between different
321 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This
322 /// function returns zero if it is not possible to represent the resultant
324 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
326 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
327 // Cannot fold a signed setcc with an unsigned setcc.
328 return ISD::SETCC_INVALID;
330 // Combine all of the condition bits.
331 ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
333 // Canonicalize illegal integer setcc's.
337 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT
338 case ISD::SETOEQ: // SETEQ & SETU[LG]E
339 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE
340 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE
341 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE
348 //===----------------------------------------------------------------------===//
349 // SDNode Profile Support
350 //===----------------------------------------------------------------------===//
352 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
354 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) {
358 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
359 /// solely with their pointer.
360 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
361 ID.AddPointer(VTList.VTs);
364 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
366 static void AddNodeIDOperands(FoldingSetNodeID &ID,
367 ArrayRef<SDValue> Ops) {
368 for (auto& Op : Ops) {
369 ID.AddPointer(Op.getNode());
370 ID.AddInteger(Op.getResNo());
374 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
376 static void AddNodeIDOperands(FoldingSetNodeID &ID,
377 ArrayRef<SDUse> Ops) {
378 for (auto& Op : Ops) {
379 ID.AddPointer(Op.getNode());
380 ID.AddInteger(Op.getResNo());
384 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC,
385 SDVTList VTList, ArrayRef<SDValue> OpList) {
386 AddNodeIDOpcode(ID, OpC);
387 AddNodeIDValueTypes(ID, VTList);
388 AddNodeIDOperands(ID, OpList);
391 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to
393 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) {
394 switch (N->getOpcode()) {
395 case ISD::TargetExternalSymbol:
396 case ISD::ExternalSymbol:
397 llvm_unreachable("Should only be used on nodes with operands");
398 default: break; // Normal nodes don't need extra info.
399 case ISD::TargetConstant:
400 case ISD::Constant: {
401 const ConstantSDNode *C = cast<ConstantSDNode>(N);
402 ID.AddPointer(C->getConstantIntValue());
403 ID.AddBoolean(C->isOpaque());
406 case ISD::TargetConstantFP:
407 case ISD::ConstantFP: {
408 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue());
411 case ISD::TargetGlobalAddress:
412 case ISD::GlobalAddress:
413 case ISD::TargetGlobalTLSAddress:
414 case ISD::GlobalTLSAddress: {
415 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
416 ID.AddPointer(GA->getGlobal());
417 ID.AddInteger(GA->getOffset());
418 ID.AddInteger(GA->getTargetFlags());
419 ID.AddInteger(GA->getAddressSpace());
422 case ISD::BasicBlock:
423 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
426 ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
428 case ISD::RegisterMask:
429 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask());
432 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
434 case ISD::FrameIndex:
435 case ISD::TargetFrameIndex:
436 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
439 case ISD::TargetJumpTable:
440 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
441 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags());
443 case ISD::ConstantPool:
444 case ISD::TargetConstantPool: {
445 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
446 ID.AddInteger(CP->getAlignment());
447 ID.AddInteger(CP->getOffset());
448 if (CP->isMachineConstantPoolEntry())
449 CP->getMachineCPVal()->addSelectionDAGCSEId(ID);
451 ID.AddPointer(CP->getConstVal());
452 ID.AddInteger(CP->getTargetFlags());
455 case ISD::TargetIndex: {
456 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N);
457 ID.AddInteger(TI->getIndex());
458 ID.AddInteger(TI->getOffset());
459 ID.AddInteger(TI->getTargetFlags());
463 const LoadSDNode *LD = cast<LoadSDNode>(N);
464 ID.AddInteger(LD->getMemoryVT().getRawBits());
465 ID.AddInteger(LD->getRawSubclassData());
466 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
470 const StoreSDNode *ST = cast<StoreSDNode>(N);
471 ID.AddInteger(ST->getMemoryVT().getRawBits());
472 ID.AddInteger(ST->getRawSubclassData());
473 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
476 case ISD::ATOMIC_CMP_SWAP:
477 case ISD::ATOMIC_SWAP:
478 case ISD::ATOMIC_LOAD_ADD:
479 case ISD::ATOMIC_LOAD_SUB:
480 case ISD::ATOMIC_LOAD_AND:
481 case ISD::ATOMIC_LOAD_OR:
482 case ISD::ATOMIC_LOAD_XOR:
483 case ISD::ATOMIC_LOAD_NAND:
484 case ISD::ATOMIC_LOAD_MIN:
485 case ISD::ATOMIC_LOAD_MAX:
486 case ISD::ATOMIC_LOAD_UMIN:
487 case ISD::ATOMIC_LOAD_UMAX:
488 case ISD::ATOMIC_LOAD:
489 case ISD::ATOMIC_STORE: {
490 const AtomicSDNode *AT = cast<AtomicSDNode>(N);
491 ID.AddInteger(AT->getMemoryVT().getRawBits());
492 ID.AddInteger(AT->getRawSubclassData());
493 ID.AddInteger(AT->getPointerInfo().getAddrSpace());
496 case ISD::PREFETCH: {
497 const MemSDNode *PF = cast<MemSDNode>(N);
498 ID.AddInteger(PF->getPointerInfo().getAddrSpace());
501 case ISD::VECTOR_SHUFFLE: {
502 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N);
503 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements();
505 ID.AddInteger(SVN->getMaskElt(i));
508 case ISD::TargetBlockAddress:
509 case ISD::BlockAddress: {
510 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N);
511 ID.AddPointer(BA->getBlockAddress());
512 ID.AddInteger(BA->getOffset());
513 ID.AddInteger(BA->getTargetFlags());
516 } // end switch (N->getOpcode())
518 // Target specific memory nodes could also have address spaces to check.
519 if (N->isTargetMemoryOpcode())
520 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace());
523 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
525 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) {
526 AddNodeIDOpcode(ID, N->getOpcode());
527 // Add the return value info.
528 AddNodeIDValueTypes(ID, N->getVTList());
529 // Add the operand info.
530 AddNodeIDOperands(ID, makeArrayRef(N->op_begin(), N->op_end()));
532 // Handle SDNode leafs with special info.
533 AddNodeIDCustom(ID, N);
536 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in
537 /// the CSE map that carries volatility, temporalness, indexing mode, and
538 /// extension/truncation information.
540 static inline unsigned
541 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile,
542 bool isNonTemporal, bool isInvariant) {
543 assert((ConvType & 3) == ConvType &&
544 "ConvType may not require more than 2 bits!");
545 assert((AM & 7) == AM &&
546 "AM may not require more than 3 bits!");
550 (isNonTemporal << 6) |
554 //===----------------------------------------------------------------------===//
555 // SelectionDAG Class
556 //===----------------------------------------------------------------------===//
558 /// doNotCSE - Return true if CSE should not be performed for this node.
559 static bool doNotCSE(SDNode *N) {
560 if (N->getValueType(0) == MVT::Glue)
561 return true; // Never CSE anything that produces a flag.
563 switch (N->getOpcode()) {
565 case ISD::HANDLENODE:
567 return true; // Never CSE these nodes.
570 // Check that remaining values produced are not flags.
571 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
572 if (N->getValueType(i) == MVT::Glue)
573 return true; // Never CSE anything that produces a flag.
578 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
580 void SelectionDAG::RemoveDeadNodes() {
581 // Create a dummy node (which is not added to allnodes), that adds a reference
582 // to the root node, preventing it from being deleted.
583 HandleSDNode Dummy(getRoot());
585 SmallVector<SDNode*, 128> DeadNodes;
587 // Add all obviously-dead nodes to the DeadNodes worklist.
588 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
590 DeadNodes.push_back(I);
592 RemoveDeadNodes(DeadNodes);
594 // If the root changed (e.g. it was a dead load, update the root).
595 setRoot(Dummy.getValue());
598 /// RemoveDeadNodes - This method deletes the unreachable nodes in the
599 /// given list, and any nodes that become unreachable as a result.
600 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) {
602 // Process the worklist, deleting the nodes and adding their uses to the
604 while (!DeadNodes.empty()) {
605 SDNode *N = DeadNodes.pop_back_val();
607 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
608 DUL->NodeDeleted(N, nullptr);
610 // Take the node out of the appropriate CSE map.
611 RemoveNodeFromCSEMaps(N);
613 // Next, brutally remove the operand list. This is safe to do, as there are
614 // no cycles in the graph.
615 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
617 SDNode *Operand = Use.getNode();
620 // Now that we removed this operand, see if there are no uses of it left.
621 if (Operand->use_empty())
622 DeadNodes.push_back(Operand);
629 void SelectionDAG::RemoveDeadNode(SDNode *N){
630 SmallVector<SDNode*, 16> DeadNodes(1, N);
632 // Create a dummy node that adds a reference to the root node, preventing
633 // it from being deleted. (This matters if the root is an operand of the
635 HandleSDNode Dummy(getRoot());
637 RemoveDeadNodes(DeadNodes);
640 void SelectionDAG::DeleteNode(SDNode *N) {
641 // First take this out of the appropriate CSE map.
642 RemoveNodeFromCSEMaps(N);
644 // Finally, remove uses due to operands of this node, remove from the
645 // AllNodes list, and delete the node.
646 DeleteNodeNotInCSEMaps(N);
649 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
650 assert(N != AllNodes.begin() && "Cannot delete the entry node!");
651 assert(N->use_empty() && "Cannot delete a node that is not dead!");
653 // Drop all of the operands and decrement used node's use counts.
659 void SelectionDAG::DeallocateNode(SDNode *N) {
660 if (N->OperandsNeedDelete)
661 delete[] N->OperandList;
663 // Set the opcode to DELETED_NODE to help catch bugs when node
664 // memory is reallocated.
665 N->NodeType = ISD::DELETED_NODE;
667 NodeAllocator.Deallocate(AllNodes.remove(N));
669 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them.
670 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N);
671 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i)
672 DbgVals[i]->setIsInvalidated();
675 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
676 /// correspond to it. This is useful when we're about to delete or repurpose
677 /// the node. We don't want future request for structurally identical nodes
678 /// to return N anymore.
679 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
681 switch (N->getOpcode()) {
682 case ISD::HANDLENODE: return false; // noop.
684 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
685 "Cond code doesn't exist!");
686 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr;
687 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr;
689 case ISD::ExternalSymbol:
690 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
692 case ISD::TargetExternalSymbol: {
693 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N);
694 Erased = TargetExternalSymbols.erase(
695 std::pair<std::string,unsigned char>(ESN->getSymbol(),
696 ESN->getTargetFlags()));
699 case ISD::VALUETYPE: {
700 EVT VT = cast<VTSDNode>(N)->getVT();
701 if (VT.isExtended()) {
702 Erased = ExtendedValueTypeNodes.erase(VT);
704 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr;
705 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr;
710 // Remove it from the CSE Map.
711 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!");
712 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!");
713 Erased = CSEMap.RemoveNode(N);
717 // Verify that the node was actually in one of the CSE maps, unless it has a
718 // flag result (which cannot be CSE'd) or is one of the special cases that are
719 // not subject to CSE.
720 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue &&
721 !N->isMachineOpcode() && !doNotCSE(N)) {
724 llvm_unreachable("Node is not in map!");
730 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE
731 /// maps and modified in place. Add it back to the CSE maps, unless an identical
732 /// node already exists, in which case transfer all its users to the existing
733 /// node. This transfer can potentially trigger recursive merging.
736 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) {
737 // For node types that aren't CSE'd, just act as if no identical node
740 SDNode *Existing = CSEMap.GetOrInsertNode(N);
742 // If there was already an existing matching node, use ReplaceAllUsesWith
743 // to replace the dead one with the existing one. This can cause
744 // recursive merging of other unrelated nodes down the line.
745 ReplaceAllUsesWith(N, Existing);
747 // N is now dead. Inform the listeners and delete it.
748 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
749 DUL->NodeDeleted(N, Existing);
750 DeleteNodeNotInCSEMaps(N);
755 // If the node doesn't already exist, we updated it. Inform listeners.
756 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
760 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
761 /// were replaced with those specified. If this node is never memoized,
762 /// return null, otherwise return a pointer to the slot it would take. If a
763 /// node already exists with these operands, the slot will be non-null.
764 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op,
769 SDValue Ops[] = { Op };
771 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
772 AddNodeIDCustom(ID, N);
773 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
777 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
778 /// were replaced with those specified. If this node is never memoized,
779 /// return null, otherwise return a pointer to the slot it would take. If a
780 /// node already exists with these operands, the slot will be non-null.
781 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
782 SDValue Op1, SDValue Op2,
787 SDValue Ops[] = { Op1, Op2 };
789 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
790 AddNodeIDCustom(ID, N);
791 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
796 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
797 /// were replaced with those specified. If this node is never memoized,
798 /// return null, otherwise return a pointer to the slot it would take. If a
799 /// node already exists with these operands, the slot will be non-null.
800 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
806 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops);
807 AddNodeIDCustom(ID, N);
808 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos);
813 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid.
814 static void VerifyNodeCommon(SDNode *N) {
815 switch (N->getOpcode()) {
818 case ISD::BUILD_PAIR: {
819 EVT VT = N->getValueType(0);
820 assert(N->getNumValues() == 1 && "Too many results!");
821 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) &&
822 "Wrong return type!");
823 assert(N->getNumOperands() == 2 && "Wrong number of operands!");
824 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() &&
825 "Mismatched operand types!");
826 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() &&
827 "Wrong operand type!");
828 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() &&
829 "Wrong return type size");
832 case ISD::BUILD_VECTOR: {
833 assert(N->getNumValues() == 1 && "Too many results!");
834 assert(N->getValueType(0).isVector() && "Wrong return type!");
835 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() &&
836 "Wrong number of operands!");
837 EVT EltVT = N->getValueType(0).getVectorElementType();
838 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
839 assert((I->getValueType() == EltVT ||
840 (EltVT.isInteger() && I->getValueType().isInteger() &&
841 EltVT.bitsLE(I->getValueType()))) &&
842 "Wrong operand type!");
843 assert(I->getValueType() == N->getOperand(0).getValueType() &&
844 "Operands must all have the same type");
851 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid.
852 static void VerifySDNode(SDNode *N) {
853 // The SDNode allocators cannot be used to allocate nodes with fields that are
854 // not present in an SDNode!
855 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!");
856 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!");
857 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!");
858 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!");
859 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!");
860 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!");
861 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!");
862 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!");
863 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!");
864 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!");
865 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!");
866 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!");
867 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!");
868 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!");
869 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!");
870 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!");
871 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!");
872 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!");
873 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!");
878 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is
880 static void VerifyMachineNode(SDNode *N) {
881 // The MachineNode allocators cannot be used to allocate nodes with fields
882 // that are not present in a MachineNode!
883 // Currently there are no such nodes.
889 /// getEVTAlignment - Compute the default alignment value for the
892 unsigned SelectionDAG::getEVTAlignment(EVT VT) const {
893 Type *Ty = VT == MVT::iPTR ?
894 PointerType::get(Type::getInt8Ty(*getContext()), 0) :
895 VT.getTypeForEVT(*getContext());
897 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty);
900 // EntryNode could meaningfully have debug info if we can find it...
901 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL)
902 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL),
903 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)),
904 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false),
905 UpdateListeners(nullptr) {
906 AllNodes.push_back(&EntryNode);
907 DbgInfo = new SDDbgInfo();
910 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) {
913 Context = &mf.getFunction()->getContext();
916 SelectionDAG::~SelectionDAG() {
917 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners");
922 void SelectionDAG::allnodes_clear() {
923 assert(&*AllNodes.begin() == &EntryNode);
924 AllNodes.remove(AllNodes.begin());
925 while (!AllNodes.empty())
926 DeallocateNode(AllNodes.begin());
929 void SelectionDAG::clear() {
931 OperandAllocator.Reset();
934 ExtendedValueTypeNodes.clear();
935 ExternalSymbols.clear();
936 TargetExternalSymbols.clear();
937 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
938 static_cast<CondCodeSDNode*>(nullptr));
939 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
940 static_cast<SDNode*>(nullptr));
942 EntryNode.UseList = nullptr;
943 AllNodes.push_back(&EntryNode);
944 Root = getEntryNode();
948 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
949 return VT.bitsGT(Op.getValueType()) ?
950 getNode(ISD::ANY_EXTEND, DL, VT, Op) :
951 getNode(ISD::TRUNCATE, DL, VT, Op);
954 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
955 return VT.bitsGT(Op.getValueType()) ?
956 getNode(ISD::SIGN_EXTEND, DL, VT, Op) :
957 getNode(ISD::TRUNCATE, DL, VT, Op);
960 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) {
961 return VT.bitsGT(Op.getValueType()) ?
962 getNode(ISD::ZERO_EXTEND, DL, VT, Op) :
963 getNode(ISD::TRUNCATE, DL, VT, Op);
966 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT) {
967 if (VT.bitsLE(Op.getValueType()))
968 return getNode(ISD::TRUNCATE, SL, VT, Op);
970 TargetLowering::BooleanContent BType = TLI->getBooleanContents(VT.isVector());
971 return getNode(TLI->getExtendForContent(BType), SL, VT, Op);
974 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
975 assert(!VT.isVector() &&
976 "getZeroExtendInReg should use the vector element type instead of "
978 if (Op.getValueType() == VT) return Op;
979 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
980 APInt Imm = APInt::getLowBitsSet(BitWidth,
982 return getNode(ISD::AND, DL, Op.getValueType(), Op,
983 getConstant(Imm, Op.getValueType()));
986 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
988 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
989 EVT EltVT = VT.getScalarType();
991 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
992 return getNode(ISD::XOR, DL, VT, Val, NegOne);
995 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) {
996 EVT EltVT = VT.getScalarType();
998 switch (TLI->getBooleanContents(VT.isVector())) {
999 case TargetLowering::ZeroOrOneBooleanContent:
1000 case TargetLowering::UndefinedBooleanContent:
1001 TrueValue = getConstant(1, VT);
1003 case TargetLowering::ZeroOrNegativeOneBooleanContent:
1004 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()),
1008 return getNode(ISD::XOR, DL, VT, Val, TrueValue);
1011 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
1012 EVT EltVT = VT.getScalarType();
1013 assert((EltVT.getSizeInBits() >= 64 ||
1014 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
1015 "getConstant with a uint64_t value that doesn't fit in the type!");
1016 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
1019 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
1021 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1024 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1026 assert(VT.isInteger() && "Cannot create FP integer constant!");
1028 EVT EltVT = VT.getScalarType();
1029 const ConstantInt *Elt = &Val;
1031 const TargetLowering *TLI = TM.getTargetLowering();
1033 // In some cases the vector type is legal but the element type is illegal and
1034 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1035 // inserted value (the type does not need to match the vector element type).
1036 // Any extra bits introduced will be truncated away.
1037 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1038 TargetLowering::TypePromoteInteger) {
1039 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1040 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1041 Elt = ConstantInt::get(*getContext(), NewVal);
1043 // In other cases the element type is illegal and needs to be expanded, for
1044 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1045 // the value into n parts and use a vector type with n-times the elements.
1046 // Then bitcast to the type requested.
1047 // Legalizing constants too early makes the DAGCombiner's job harder so we
1048 // only legalize if the DAG tells us we must produce legal types.
1049 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1050 TLI->getTypeAction(*getContext(), EltVT) ==
1051 TargetLowering::TypeExpandInteger) {
1052 APInt NewVal = Elt->getValue();
1053 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1054 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1055 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1056 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1058 // Check the temporary vector is the correct size. If this fails then
1059 // getTypeToTransformTo() probably returned a type whose size (in bits)
1060 // isn't a power-of-2 factor of the requested type size.
1061 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1063 SmallVector<SDValue, 2> EltParts;
1064 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1065 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1066 .trunc(ViaEltSizeInBits),
1067 ViaEltVT, isT, isO));
1070 // EltParts is currently in little endian order. If we actually want
1071 // big-endian order then reverse it now.
1072 if (TLI->isBigEndian())
1073 std::reverse(EltParts.begin(), EltParts.end());
1075 // The elements must be reversed when the element order is different
1076 // to the endianness of the elements (because the BITCAST is itself a
1077 // vector shuffle in this situation). However, we do not need any code to
1078 // perform this reversal because getConstant() is producing a vector
1080 // This situation occurs in MIPS MSA.
1082 SmallVector<SDValue, 8> Ops;
1083 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1084 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1086 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1087 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1092 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1093 "APInt size does not match type size!");
1094 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1095 FoldingSetNodeID ID;
1096 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1100 SDNode *N = nullptr;
1101 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1103 return SDValue(N, 0);
1106 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1107 CSEMap.InsertNode(N, IP);
1108 AllNodes.push_back(N);
1111 SDValue Result(N, 0);
1112 if (VT.isVector()) {
1113 SmallVector<SDValue, 8> Ops;
1114 Ops.assign(VT.getVectorNumElements(), Result);
1115 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1120 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1121 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1125 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1126 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1129 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1130 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1132 EVT EltVT = VT.getScalarType();
1134 // Do the map lookup using the actual bit pattern for the floating point
1135 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1136 // we don't have issues with SNANs.
1137 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1138 FoldingSetNodeID ID;
1139 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1142 SDNode *N = nullptr;
1143 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1145 return SDValue(N, 0);
1148 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1149 CSEMap.InsertNode(N, IP);
1150 AllNodes.push_back(N);
1153 SDValue Result(N, 0);
1154 if (VT.isVector()) {
1155 SmallVector<SDValue, 8> Ops;
1156 Ops.assign(VT.getVectorNumElements(), Result);
1157 // FIXME SDLoc info might be appropriate here
1158 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1163 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1164 EVT EltVT = VT.getScalarType();
1165 if (EltVT==MVT::f32)
1166 return getConstantFP(APFloat((float)Val), VT, isTarget);
1167 else if (EltVT==MVT::f64)
1168 return getConstantFP(APFloat(Val), VT, isTarget);
1169 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1172 APFloat apf = APFloat(Val);
1173 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1175 return getConstantFP(apf, VT, isTarget);
1177 llvm_unreachable("Unsupported type in getConstantFP");
1180 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1181 EVT VT, int64_t Offset,
1183 unsigned char TargetFlags) {
1184 assert((TargetFlags == 0 || isTargetGA) &&
1185 "Cannot set target flags on target-independent globals");
1186 const TargetLowering *TLI = TM.getTargetLowering();
1188 // Truncate (with sign-extension) the offset value to the pointer size.
1189 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1191 Offset = SignExtend64(Offset, BitWidth);
1193 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1195 // If GV is an alias then use the aliasee for determining thread-localness.
1196 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1197 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1201 if (GVar && GVar->isThreadLocal())
1202 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1204 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1206 FoldingSetNodeID ID;
1207 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1209 ID.AddInteger(Offset);
1210 ID.AddInteger(TargetFlags);
1211 ID.AddInteger(GV->getType()->getAddressSpace());
1213 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1214 return SDValue(E, 0);
1216 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1217 DL.getDebugLoc(), GV, VT,
1218 Offset, TargetFlags);
1219 CSEMap.InsertNode(N, IP);
1220 AllNodes.push_back(N);
1221 return SDValue(N, 0);
1224 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1225 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1226 FoldingSetNodeID ID;
1227 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1230 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1231 return SDValue(E, 0);
1233 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1234 CSEMap.InsertNode(N, IP);
1235 AllNodes.push_back(N);
1236 return SDValue(N, 0);
1239 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1240 unsigned char TargetFlags) {
1241 assert((TargetFlags == 0 || isTarget) &&
1242 "Cannot set target flags on target-independent jump tables");
1243 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1244 FoldingSetNodeID ID;
1245 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1247 ID.AddInteger(TargetFlags);
1249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1250 return SDValue(E, 0);
1252 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1254 CSEMap.InsertNode(N, IP);
1255 AllNodes.push_back(N);
1256 return SDValue(N, 0);
1259 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1260 unsigned Alignment, int Offset,
1262 unsigned char TargetFlags) {
1263 assert((TargetFlags == 0 || isTarget) &&
1264 "Cannot set target flags on target-independent globals");
1267 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1268 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1269 FoldingSetNodeID ID;
1270 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1271 ID.AddInteger(Alignment);
1272 ID.AddInteger(Offset);
1274 ID.AddInteger(TargetFlags);
1276 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1277 return SDValue(E, 0);
1279 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1280 Alignment, TargetFlags);
1281 CSEMap.InsertNode(N, IP);
1282 AllNodes.push_back(N);
1283 return SDValue(N, 0);
1287 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1288 unsigned Alignment, int Offset,
1290 unsigned char TargetFlags) {
1291 assert((TargetFlags == 0 || isTarget) &&
1292 "Cannot set target flags on target-independent globals");
1295 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1296 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1297 FoldingSetNodeID ID;
1298 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1299 ID.AddInteger(Alignment);
1300 ID.AddInteger(Offset);
1301 C->addSelectionDAGCSEId(ID);
1302 ID.AddInteger(TargetFlags);
1304 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1305 return SDValue(E, 0);
1307 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1308 Alignment, TargetFlags);
1309 CSEMap.InsertNode(N, IP);
1310 AllNodes.push_back(N);
1311 return SDValue(N, 0);
1314 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1315 unsigned char TargetFlags) {
1316 FoldingSetNodeID ID;
1317 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1318 ID.AddInteger(Index);
1319 ID.AddInteger(Offset);
1320 ID.AddInteger(TargetFlags);
1322 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1323 return SDValue(E, 0);
1325 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1327 CSEMap.InsertNode(N, IP);
1328 AllNodes.push_back(N);
1329 return SDValue(N, 0);
1332 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1333 FoldingSetNodeID ID;
1334 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1337 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1338 return SDValue(E, 0);
1340 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1341 CSEMap.InsertNode(N, IP);
1342 AllNodes.push_back(N);
1343 return SDValue(N, 0);
1346 SDValue SelectionDAG::getValueType(EVT VT) {
1347 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1348 ValueTypeNodes.size())
1349 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1351 SDNode *&N = VT.isExtended() ?
1352 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1354 if (N) return SDValue(N, 0);
1355 N = new (NodeAllocator) VTSDNode(VT);
1356 AllNodes.push_back(N);
1357 return SDValue(N, 0);
1360 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1361 SDNode *&N = ExternalSymbols[Sym];
1362 if (N) return SDValue(N, 0);
1363 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1364 AllNodes.push_back(N);
1365 return SDValue(N, 0);
1368 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1369 unsigned char TargetFlags) {
1371 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1373 if (N) return SDValue(N, 0);
1374 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1375 AllNodes.push_back(N);
1376 return SDValue(N, 0);
1379 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1380 if ((unsigned)Cond >= CondCodeNodes.size())
1381 CondCodeNodes.resize(Cond+1);
1383 if (!CondCodeNodes[Cond]) {
1384 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1385 CondCodeNodes[Cond] = N;
1386 AllNodes.push_back(N);
1389 return SDValue(CondCodeNodes[Cond], 0);
1392 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1393 // the shuffle mask M that point at N1 to point at N2, and indices that point
1394 // N2 to point at N1.
1395 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1397 int NElts = M.size();
1398 for (int i = 0; i != NElts; ++i) {
1406 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1407 SDValue N2, const int *Mask) {
1408 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1409 "Invalid VECTOR_SHUFFLE");
1411 // Canonicalize shuffle undef, undef -> undef
1412 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1413 return getUNDEF(VT);
1415 // Validate that all indices in Mask are within the range of the elements
1416 // input to the shuffle.
1417 unsigned NElts = VT.getVectorNumElements();
1418 SmallVector<int, 8> MaskVec;
1419 for (unsigned i = 0; i != NElts; ++i) {
1420 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1421 MaskVec.push_back(Mask[i]);
1424 // Canonicalize shuffle v, v -> v, undef
1427 for (unsigned i = 0; i != NElts; ++i)
1428 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1431 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1432 if (N1.getOpcode() == ISD::UNDEF)
1433 commuteShuffle(N1, N2, MaskVec);
1435 // Canonicalize all index into lhs, -> shuffle lhs, undef
1436 // Canonicalize all index into rhs, -> shuffle rhs, undef
1437 bool AllLHS = true, AllRHS = true;
1438 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1439 for (unsigned i = 0; i != NElts; ++i) {
1440 if (MaskVec[i] >= (int)NElts) {
1445 } else if (MaskVec[i] >= 0) {
1449 if (AllLHS && AllRHS)
1450 return getUNDEF(VT);
1451 if (AllLHS && !N2Undef)
1455 commuteShuffle(N1, N2, MaskVec);
1458 // If Identity shuffle return that node.
1459 bool Identity = true;
1460 for (unsigned i = 0; i != NElts; ++i) {
1461 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1463 if (Identity && NElts)
1466 // Shuffling a constant splat doesn't change the result.
1467 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1468 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1471 FoldingSetNodeID ID;
1472 SDValue Ops[2] = { N1, N2 };
1473 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1474 for (unsigned i = 0; i != NElts; ++i)
1475 ID.AddInteger(MaskVec[i]);
1478 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1479 return SDValue(E, 0);
1481 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1482 // SDNode doesn't have access to it. This memory will be "leaked" when
1483 // the node is deallocated, but recovered when the NodeAllocator is released.
1484 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1485 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1487 ShuffleVectorSDNode *N =
1488 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1489 dl.getDebugLoc(), N1, N2,
1491 CSEMap.InsertNode(N, IP);
1492 AllNodes.push_back(N);
1493 return SDValue(N, 0);
1496 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1497 SDValue Val, SDValue DTy,
1498 SDValue STy, SDValue Rnd, SDValue Sat,
1499 ISD::CvtCode Code) {
1500 // If the src and dest types are the same and the conversion is between
1501 // integer types of the same sign or two floats, no conversion is necessary.
1503 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1506 FoldingSetNodeID ID;
1507 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1508 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1510 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1511 return SDValue(E, 0);
1513 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1516 CSEMap.InsertNode(N, IP);
1517 AllNodes.push_back(N);
1518 return SDValue(N, 0);
1521 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1522 FoldingSetNodeID ID;
1523 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1524 ID.AddInteger(RegNo);
1526 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1527 return SDValue(E, 0);
1529 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1530 CSEMap.InsertNode(N, IP);
1531 AllNodes.push_back(N);
1532 return SDValue(N, 0);
1535 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1536 FoldingSetNodeID ID;
1537 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1538 ID.AddPointer(RegMask);
1540 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1541 return SDValue(E, 0);
1543 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1544 CSEMap.InsertNode(N, IP);
1545 AllNodes.push_back(N);
1546 return SDValue(N, 0);
1549 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1550 FoldingSetNodeID ID;
1551 SDValue Ops[] = { Root };
1552 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1553 ID.AddPointer(Label);
1555 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1556 return SDValue(E, 0);
1558 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1559 dl.getDebugLoc(), Root, Label);
1560 CSEMap.InsertNode(N, IP);
1561 AllNodes.push_back(N);
1562 return SDValue(N, 0);
1566 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1569 unsigned char TargetFlags) {
1570 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1572 FoldingSetNodeID ID;
1573 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1575 ID.AddInteger(Offset);
1576 ID.AddInteger(TargetFlags);
1578 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1579 return SDValue(E, 0);
1581 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1583 CSEMap.InsertNode(N, IP);
1584 AllNodes.push_back(N);
1585 return SDValue(N, 0);
1588 SDValue SelectionDAG::getSrcValue(const Value *V) {
1589 assert((!V || V->getType()->isPointerTy()) &&
1590 "SrcValue is not a pointer?");
1592 FoldingSetNodeID ID;
1593 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1597 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1598 return SDValue(E, 0);
1600 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1601 CSEMap.InsertNode(N, IP);
1602 AllNodes.push_back(N);
1603 return SDValue(N, 0);
1606 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1607 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1608 FoldingSetNodeID ID;
1609 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1613 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1614 return SDValue(E, 0);
1616 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1617 CSEMap.InsertNode(N, IP);
1618 AllNodes.push_back(N);
1619 return SDValue(N, 0);
1622 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1623 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1624 unsigned SrcAS, unsigned DestAS) {
1625 SDValue Ops[] = {Ptr};
1626 FoldingSetNodeID ID;
1627 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1628 ID.AddInteger(SrcAS);
1629 ID.AddInteger(DestAS);
1632 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1633 return SDValue(E, 0);
1635 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1637 VT, Ptr, SrcAS, DestAS);
1638 CSEMap.InsertNode(N, IP);
1639 AllNodes.push_back(N);
1640 return SDValue(N, 0);
1643 /// getShiftAmountOperand - Return the specified value casted to
1644 /// the target's desired shift amount type.
1645 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1646 EVT OpTy = Op.getValueType();
1647 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1648 if (OpTy == ShTy || OpTy.isVector()) return Op;
1650 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1651 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1654 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1655 /// specified value type.
1656 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1657 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1658 unsigned ByteSize = VT.getStoreSize();
1659 Type *Ty = VT.getTypeForEVT(*getContext());
1660 const TargetLowering *TLI = TM.getTargetLowering();
1661 unsigned StackAlign =
1662 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1664 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1665 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1668 /// CreateStackTemporary - Create a stack temporary suitable for holding
1669 /// either of the specified value types.
1670 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1671 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1672 VT2.getStoreSizeInBits())/8;
1673 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1674 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1675 const TargetLowering *TLI = TM.getTargetLowering();
1676 const DataLayout *TD = TLI->getDataLayout();
1677 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1678 TD->getPrefTypeAlignment(Ty2));
1680 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1681 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1682 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1685 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1686 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1687 // These setcc operations always fold.
1691 case ISD::SETFALSE2: return getConstant(0, VT);
1693 case ISD::SETTRUE2: {
1694 const TargetLowering *TLI = TM.getTargetLowering();
1695 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1697 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1710 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1714 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1715 const APInt &C2 = N2C->getAPIntValue();
1716 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1717 const APInt &C1 = N1C->getAPIntValue();
1720 default: llvm_unreachable("Unknown integer setcc!");
1721 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1722 case ISD::SETNE: return getConstant(C1 != C2, VT);
1723 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1724 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1725 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1726 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1727 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1728 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1729 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1730 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1734 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1735 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1736 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1739 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1740 return getUNDEF(VT);
1742 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1743 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1744 return getUNDEF(VT);
1746 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1747 R==APFloat::cmpLessThan, VT);
1748 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1749 return getUNDEF(VT);
1751 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1752 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1753 return getUNDEF(VT);
1755 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1756 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1757 return getUNDEF(VT);
1759 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1760 R==APFloat::cmpEqual, VT);
1761 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1762 return getUNDEF(VT);
1764 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1765 R==APFloat::cmpEqual, VT);
1766 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1767 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1768 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1769 R==APFloat::cmpEqual, VT);
1770 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1771 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1772 R==APFloat::cmpLessThan, VT);
1773 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1774 R==APFloat::cmpUnordered, VT);
1775 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1776 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1779 // Ensure that the constant occurs on the RHS.
1780 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1781 MVT CompVT = N1.getValueType().getSimpleVT();
1782 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1785 return getSetCC(dl, VT, N2, N1, SwappedCond);
1789 // Could not fold it.
1793 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1794 /// use this predicate to simplify operations downstream.
1795 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1796 // This predicate is not safe for vector operations.
1797 if (Op.getValueType().isVector())
1800 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1801 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1804 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1805 /// this predicate to simplify operations downstream. Mask is known to be zero
1806 /// for bits that V cannot have.
1807 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1808 unsigned Depth) const {
1809 APInt KnownZero, KnownOne;
1810 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1811 return (KnownZero & Mask) == Mask;
1814 /// Determine which bits of Op are known to be either zero or one and return
1815 /// them in the KnownZero/KnownOne bitsets.
1816 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1817 APInt &KnownOne, unsigned Depth) const {
1818 const TargetLowering *TLI = TM.getTargetLowering();
1819 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1821 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1823 return; // Limit search depth.
1825 APInt KnownZero2, KnownOne2;
1827 switch (Op.getOpcode()) {
1829 // We know all of the bits for a constant!
1830 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1831 KnownZero = ~KnownOne;
1834 // If either the LHS or the RHS are Zero, the result is zero.
1835 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1836 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1838 // Output known-1 bits are only known if set in both the LHS & RHS.
1839 KnownOne &= KnownOne2;
1840 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1841 KnownZero |= KnownZero2;
1844 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1845 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1847 // Output known-0 bits are only known if clear in both the LHS & RHS.
1848 KnownZero &= KnownZero2;
1849 // Output known-1 are known to be set if set in either the LHS | RHS.
1850 KnownOne |= KnownOne2;
1853 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1854 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1856 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1857 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1858 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1859 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1860 KnownZero = KnownZeroOut;
1864 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1865 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1867 // If low bits are zero in either operand, output low known-0 bits.
1868 // Also compute a conserative estimate for high known-0 bits.
1869 // More trickiness is possible, but this is sufficient for the
1870 // interesting case of alignment computation.
1871 KnownOne.clearAllBits();
1872 unsigned TrailZ = KnownZero.countTrailingOnes() +
1873 KnownZero2.countTrailingOnes();
1874 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1875 KnownZero2.countLeadingOnes(),
1876 BitWidth) - BitWidth;
1878 TrailZ = std::min(TrailZ, BitWidth);
1879 LeadZ = std::min(LeadZ, BitWidth);
1880 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1881 APInt::getHighBitsSet(BitWidth, LeadZ);
1885 // For the purposes of computing leading zeros we can conservatively
1886 // treat a udiv as a logical right shift by the power of 2 known to
1887 // be less than the denominator.
1888 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1889 unsigned LeadZ = KnownZero2.countLeadingOnes();
1891 KnownOne2.clearAllBits();
1892 KnownZero2.clearAllBits();
1893 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1894 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1895 if (RHSUnknownLeadingOnes != BitWidth)
1896 LeadZ = std::min(BitWidth,
1897 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1899 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1903 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1904 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1906 // Only known if known in both the LHS and RHS.
1907 KnownOne &= KnownOne2;
1908 KnownZero &= KnownZero2;
1910 case ISD::SELECT_CC:
1911 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1912 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1914 // Only known if known in both the LHS and RHS.
1915 KnownOne &= KnownOne2;
1916 KnownZero &= KnownZero2;
1924 if (Op.getResNo() != 1)
1926 // The boolean result conforms to getBooleanContents. Fall through.
1928 // If we know the result of a setcc has the top bits zero, use this info.
1929 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1930 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1931 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1934 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1935 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1936 unsigned ShAmt = SA->getZExtValue();
1938 // If the shift count is an invalid immediate, don't do anything.
1939 if (ShAmt >= BitWidth)
1942 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1943 KnownZero <<= ShAmt;
1945 // low bits known zero.
1946 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1950 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1951 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1952 unsigned ShAmt = SA->getZExtValue();
1954 // If the shift count is an invalid immediate, don't do anything.
1955 if (ShAmt >= BitWidth)
1958 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1959 KnownZero = KnownZero.lshr(ShAmt);
1960 KnownOne = KnownOne.lshr(ShAmt);
1962 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1963 KnownZero |= HighBits; // High bits known zero.
1967 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1968 unsigned ShAmt = SA->getZExtValue();
1970 // If the shift count is an invalid immediate, don't do anything.
1971 if (ShAmt >= BitWidth)
1974 // If any of the demanded bits are produced by the sign extension, we also
1975 // demand the input sign bit.
1976 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1978 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1979 KnownZero = KnownZero.lshr(ShAmt);
1980 KnownOne = KnownOne.lshr(ShAmt);
1982 // Handle the sign bits.
1983 APInt SignBit = APInt::getSignBit(BitWidth);
1984 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1986 if (KnownZero.intersects(SignBit)) {
1987 KnownZero |= HighBits; // New bits are known zero.
1988 } else if (KnownOne.intersects(SignBit)) {
1989 KnownOne |= HighBits; // New bits are known one.
1993 case ISD::SIGN_EXTEND_INREG: {
1994 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1995 unsigned EBits = EVT.getScalarType().getSizeInBits();
1997 // Sign extension. Compute the demanded bits in the result that are not
1998 // present in the input.
1999 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
2001 APInt InSignBit = APInt::getSignBit(EBits);
2002 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
2004 // If the sign extended bits are demanded, we know that the sign
2006 InSignBit = InSignBit.zext(BitWidth);
2007 if (NewBits.getBoolValue())
2008 InputDemandedBits |= InSignBit;
2010 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2011 KnownOne &= InputDemandedBits;
2012 KnownZero &= InputDemandedBits;
2014 // If the sign bit of the input is known set or clear, then we know the
2015 // top bits of the result.
2016 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2017 KnownZero |= NewBits;
2018 KnownOne &= ~NewBits;
2019 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2020 KnownOne |= NewBits;
2021 KnownZero &= ~NewBits;
2022 } else { // Input sign bit unknown
2023 KnownZero &= ~NewBits;
2024 KnownOne &= ~NewBits;
2029 case ISD::CTTZ_ZERO_UNDEF:
2031 case ISD::CTLZ_ZERO_UNDEF:
2033 unsigned LowBits = Log2_32(BitWidth)+1;
2034 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2035 KnownOne.clearAllBits();
2039 LoadSDNode *LD = cast<LoadSDNode>(Op);
2040 // If this is a ZEXTLoad and we are looking at the loaded value.
2041 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2042 EVT VT = LD->getMemoryVT();
2043 unsigned MemBits = VT.getScalarType().getSizeInBits();
2044 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2045 } else if (const MDNode *Ranges = LD->getRanges()) {
2046 computeKnownBitsLoad(*Ranges, KnownZero);
2050 case ISD::ZERO_EXTEND: {
2051 EVT InVT = Op.getOperand(0).getValueType();
2052 unsigned InBits = InVT.getScalarType().getSizeInBits();
2053 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2054 KnownZero = KnownZero.trunc(InBits);
2055 KnownOne = KnownOne.trunc(InBits);
2056 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2057 KnownZero = KnownZero.zext(BitWidth);
2058 KnownOne = KnownOne.zext(BitWidth);
2059 KnownZero |= NewBits;
2062 case ISD::SIGN_EXTEND: {
2063 EVT InVT = Op.getOperand(0).getValueType();
2064 unsigned InBits = InVT.getScalarType().getSizeInBits();
2065 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2067 KnownZero = KnownZero.trunc(InBits);
2068 KnownOne = KnownOne.trunc(InBits);
2069 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2071 // Note if the sign bit is known to be zero or one.
2072 bool SignBitKnownZero = KnownZero.isNegative();
2073 bool SignBitKnownOne = KnownOne.isNegative();
2075 KnownZero = KnownZero.zext(BitWidth);
2076 KnownOne = KnownOne.zext(BitWidth);
2078 // If the sign bit is known zero or one, the top bits match.
2079 if (SignBitKnownZero)
2080 KnownZero |= NewBits;
2081 else if (SignBitKnownOne)
2082 KnownOne |= NewBits;
2085 case ISD::ANY_EXTEND: {
2086 EVT InVT = Op.getOperand(0).getValueType();
2087 unsigned InBits = InVT.getScalarType().getSizeInBits();
2088 KnownZero = KnownZero.trunc(InBits);
2089 KnownOne = KnownOne.trunc(InBits);
2090 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2091 KnownZero = KnownZero.zext(BitWidth);
2092 KnownOne = KnownOne.zext(BitWidth);
2095 case ISD::TRUNCATE: {
2096 EVT InVT = Op.getOperand(0).getValueType();
2097 unsigned InBits = InVT.getScalarType().getSizeInBits();
2098 KnownZero = KnownZero.zext(InBits);
2099 KnownOne = KnownOne.zext(InBits);
2100 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2101 KnownZero = KnownZero.trunc(BitWidth);
2102 KnownOne = KnownOne.trunc(BitWidth);
2105 case ISD::AssertZext: {
2106 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2107 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2108 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2109 KnownZero |= (~InMask);
2110 KnownOne &= (~KnownZero);
2114 // All bits are zero except the low bit.
2115 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2119 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2120 // We know that the top bits of C-X are clear if X contains less bits
2121 // than C (i.e. no wrap-around can happen). For example, 20-X is
2122 // positive if we can prove that X is >= 0 and < 16.
2123 if (CLHS->getAPIntValue().isNonNegative()) {
2124 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2125 // NLZ can't be BitWidth with no sign bit
2126 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2127 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2129 // If all of the MaskV bits are known to be zero, then we know the
2130 // output top bits are zero, because we now know that the output is
2132 if ((KnownZero2 & MaskV) == MaskV) {
2133 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2134 // Top bits known zero.
2135 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2143 // Output known-0 bits are known if clear or set in both the low clear bits
2144 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2145 // low 3 bits clear.
2146 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2147 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2149 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2150 KnownZeroOut = std::min(KnownZeroOut,
2151 KnownZero2.countTrailingOnes());
2153 if (Op.getOpcode() == ISD::ADD) {
2154 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2158 // With ADDE, a carry bit may be added in, so we can only use this
2159 // information if we know (at least) that the low two bits are clear. We
2160 // then return to the caller that the low bit is unknown but that other bits
2162 if (KnownZeroOut >= 2) // ADDE
2163 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2167 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2168 const APInt &RA = Rem->getAPIntValue().abs();
2169 if (RA.isPowerOf2()) {
2170 APInt LowBits = RA - 1;
2171 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2173 // The low bits of the first operand are unchanged by the srem.
2174 KnownZero = KnownZero2 & LowBits;
2175 KnownOne = KnownOne2 & LowBits;
2177 // If the first operand is non-negative or has all low bits zero, then
2178 // the upper bits are all zero.
2179 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2180 KnownZero |= ~LowBits;
2182 // If the first operand is negative and not all low bits are zero, then
2183 // the upper bits are all one.
2184 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2185 KnownOne |= ~LowBits;
2186 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2191 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 const APInt &RA = Rem->getAPIntValue();
2193 if (RA.isPowerOf2()) {
2194 APInt LowBits = (RA - 1);
2195 KnownZero |= ~LowBits;
2196 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2201 // Since the result is less than or equal to either operand, any leading
2202 // zero bits in either operand must also exist in the result.
2203 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2204 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2206 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2207 KnownZero2.countLeadingOnes());
2208 KnownOne.clearAllBits();
2209 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2212 case ISD::FrameIndex:
2213 case ISD::TargetFrameIndex:
2214 if (unsigned Align = InferPtrAlignment(Op)) {
2215 // The low bits are known zero if the pointer is aligned.
2216 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2222 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2225 case ISD::INTRINSIC_WO_CHAIN:
2226 case ISD::INTRINSIC_W_CHAIN:
2227 case ISD::INTRINSIC_VOID:
2228 // Allow the target to implement this method for its nodes.
2229 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2233 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2236 /// ComputeNumSignBits - Return the number of times the sign bit of the
2237 /// register is replicated into the other bits. We know that at least 1 bit
2238 /// is always equal to the sign bit (itself), but other cases can give us
2239 /// information. For example, immediately after an "SRA X, 2", we know that
2240 /// the top 3 bits are all equal to each other, so we return 3.
2241 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2242 const TargetLowering *TLI = TM.getTargetLowering();
2243 EVT VT = Op.getValueType();
2244 assert(VT.isInteger() && "Invalid VT!");
2245 unsigned VTBits = VT.getScalarType().getSizeInBits();
2247 unsigned FirstAnswer = 1;
2250 return 1; // Limit search depth.
2252 switch (Op.getOpcode()) {
2254 case ISD::AssertSext:
2255 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2256 return VTBits-Tmp+1;
2257 case ISD::AssertZext:
2258 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2261 case ISD::Constant: {
2262 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2263 return Val.getNumSignBits();
2266 case ISD::SIGN_EXTEND:
2268 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2269 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2271 case ISD::SIGN_EXTEND_INREG:
2272 // Max of the input and what this extends.
2274 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2277 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2278 return std::max(Tmp, Tmp2);
2281 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2282 // SRA X, C -> adds C sign bits.
2283 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2284 Tmp += C->getZExtValue();
2285 if (Tmp > VTBits) Tmp = VTBits;
2289 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2290 // shl destroys sign bits.
2291 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2292 if (C->getZExtValue() >= VTBits || // Bad shift.
2293 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2294 return Tmp - C->getZExtValue();
2299 case ISD::XOR: // NOT is handled here.
2300 // Logical binary ops preserve the number of sign bits at the worst.
2301 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2303 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2304 FirstAnswer = std::min(Tmp, Tmp2);
2305 // We computed what we know about the sign bits as our first
2306 // answer. Now proceed to the generic code that uses
2307 // computeKnownBits, and pick whichever answer is better.
2312 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2313 if (Tmp == 1) return 1; // Early out.
2314 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2315 return std::min(Tmp, Tmp2);
2323 if (Op.getResNo() != 1)
2325 // The boolean result conforms to getBooleanContents. Fall through.
2327 // If setcc returns 0/-1, all bits are sign bits.
2328 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2329 TargetLowering::ZeroOrNegativeOneBooleanContent)
2334 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2335 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2337 // Handle rotate right by N like a rotate left by 32-N.
2338 if (Op.getOpcode() == ISD::ROTR)
2339 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2341 // If we aren't rotating out all of the known-in sign bits, return the
2342 // number that are left. This handles rotl(sext(x), 1) for example.
2343 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2344 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2348 // Add can have at most one carry bit. Thus we know that the output
2349 // is, at worst, one more bit than the inputs.
2350 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2351 if (Tmp == 1) return 1; // Early out.
2353 // Special case decrementing a value (ADD X, -1):
2354 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2355 if (CRHS->isAllOnesValue()) {
2356 APInt KnownZero, KnownOne;
2357 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2359 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2361 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2364 // If we are subtracting one from a positive number, there is no carry
2365 // out of the result.
2366 if (KnownZero.isNegative())
2370 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2371 if (Tmp2 == 1) return 1;
2372 return std::min(Tmp, Tmp2)-1;
2375 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2376 if (Tmp2 == 1) return 1;
2379 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2380 if (CLHS->isNullValue()) {
2381 APInt KnownZero, KnownOne;
2382 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2383 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2385 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2388 // If the input is known to be positive (the sign bit is known clear),
2389 // the output of the NEG has the same number of sign bits as the input.
2390 if (KnownZero.isNegative())
2393 // Otherwise, we treat this like a SUB.
2396 // Sub can have at most one carry bit. Thus we know that the output
2397 // is, at worst, one more bit than the inputs.
2398 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2399 if (Tmp == 1) return 1; // Early out.
2400 return std::min(Tmp, Tmp2)-1;
2402 // FIXME: it's tricky to do anything useful for this, but it is an important
2403 // case for targets like X86.
2407 // If we are looking at the loaded value of the SDNode.
2408 if (Op.getResNo() == 0) {
2409 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2410 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2411 unsigned ExtType = LD->getExtensionType();
2414 case ISD::SEXTLOAD: // '17' bits known
2415 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2416 return VTBits-Tmp+1;
2417 case ISD::ZEXTLOAD: // '16' bits known
2418 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2424 // Allow the target to implement this method for its nodes.
2425 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2426 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2427 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2428 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2429 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2430 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2433 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2434 // use this information.
2435 APInt KnownZero, KnownOne;
2436 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2439 if (KnownZero.isNegative()) { // sign bit is 0
2441 } else if (KnownOne.isNegative()) { // sign bit is 1;
2448 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2449 // the number of identical bits in the top of the input value.
2451 Mask <<= Mask.getBitWidth()-VTBits;
2452 // Return # leading zeros. We use 'min' here in case Val was zero before
2453 // shifting. We don't want to return '64' as for an i32 "0".
2454 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2457 /// isBaseWithConstantOffset - Return true if the specified operand is an
2458 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2459 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2460 /// semantics as an ADD. This handles the equivalence:
2461 /// X|Cst == X+Cst iff X&Cst = 0.
2462 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2463 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2464 !isa<ConstantSDNode>(Op.getOperand(1)))
2467 if (Op.getOpcode() == ISD::OR &&
2468 !MaskedValueIsZero(Op.getOperand(0),
2469 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2476 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2477 // If we're told that NaNs won't happen, assume they won't.
2478 if (getTarget().Options.NoNaNsFPMath)
2481 // If the value is a constant, we can obviously see if it is a NaN or not.
2482 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2483 return !C->getValueAPF().isNaN();
2485 // TODO: Recognize more cases here.
2490 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2491 // If the value is a constant, we can obviously see if it is a zero or not.
2492 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2493 return !C->isZero();
2495 // TODO: Recognize more cases here.
2496 switch (Op.getOpcode()) {
2499 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2500 return !C->isNullValue();
2507 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2508 // Check the obvious case.
2509 if (A == B) return true;
2511 // For for negative and positive zero.
2512 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2513 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2514 if (CA->isZero() && CB->isZero()) return true;
2516 // Otherwise they may not be equal.
2520 /// getNode - Gets or creates the specified node.
2522 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2523 FoldingSetNodeID ID;
2524 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2526 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2527 return SDValue(E, 0);
2529 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2530 DL.getDebugLoc(), getVTList(VT));
2531 CSEMap.InsertNode(N, IP);
2533 AllNodes.push_back(N);
2537 return SDValue(N, 0);
2540 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2541 EVT VT, SDValue Operand) {
2542 // Constant fold unary operations with an integer constant operand. Even
2543 // opaque constant will be folded, because the folding of unary operations
2544 // doesn't create new constants with different values. Nevertheless, the
2545 // opaque flag is preserved during folding to prevent future folding with
2547 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2548 const APInt &Val = C->getAPIntValue();
2551 case ISD::SIGN_EXTEND:
2552 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2553 C->isTargetOpcode(), C->isOpaque());
2554 case ISD::ANY_EXTEND:
2555 case ISD::ZERO_EXTEND:
2557 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2558 C->isTargetOpcode(), C->isOpaque());
2559 case ISD::UINT_TO_FP:
2560 case ISD::SINT_TO_FP: {
2561 APFloat apf(EVTToAPFloatSemantics(VT),
2562 APInt::getNullValue(VT.getSizeInBits()));
2563 (void)apf.convertFromAPInt(Val,
2564 Opcode==ISD::SINT_TO_FP,
2565 APFloat::rmNearestTiesToEven);
2566 return getConstantFP(apf, VT);
2569 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2570 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2571 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2572 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2575 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2578 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2581 case ISD::CTLZ_ZERO_UNDEF:
2582 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2585 case ISD::CTTZ_ZERO_UNDEF:
2586 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2591 // Constant fold unary operations with a floating point constant operand.
2592 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2593 APFloat V = C->getValueAPF(); // make copy
2597 return getConstantFP(V, VT);
2600 return getConstantFP(V, VT);
2602 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2603 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2604 return getConstantFP(V, VT);
2608 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2609 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2610 return getConstantFP(V, VT);
2614 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2615 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2616 return getConstantFP(V, VT);
2619 case ISD::FP_EXTEND: {
2621 // This can return overflow, underflow, or inexact; we don't care.
2622 // FIXME need to be more flexible about rounding mode.
2623 (void)V.convert(EVTToAPFloatSemantics(VT),
2624 APFloat::rmNearestTiesToEven, &ignored);
2625 return getConstantFP(V, VT);
2627 case ISD::FP_TO_SINT:
2628 case ISD::FP_TO_UINT: {
2631 assert(integerPartWidth >= 64);
2632 // FIXME need to be more flexible about rounding mode.
2633 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2634 Opcode==ISD::FP_TO_SINT,
2635 APFloat::rmTowardZero, &ignored);
2636 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2638 APInt api(VT.getSizeInBits(), x);
2639 return getConstant(api, VT);
2642 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2643 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2644 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2645 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2650 unsigned OpOpcode = Operand.getNode()->getOpcode();
2652 case ISD::TokenFactor:
2653 case ISD::MERGE_VALUES:
2654 case ISD::CONCAT_VECTORS:
2655 return Operand; // Factor, merge or concat of one node? No need.
2656 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2657 case ISD::FP_EXTEND:
2658 assert(VT.isFloatingPoint() &&
2659 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2660 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2661 assert((!VT.isVector() ||
2662 VT.getVectorNumElements() ==
2663 Operand.getValueType().getVectorNumElements()) &&
2664 "Vector element count mismatch!");
2665 if (Operand.getOpcode() == ISD::UNDEF)
2666 return getUNDEF(VT);
2668 case ISD::SIGN_EXTEND:
2669 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2670 "Invalid SIGN_EXTEND!");
2671 if (Operand.getValueType() == VT) return Operand; // noop extension
2672 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2673 "Invalid sext node, dst < src!");
2674 assert((!VT.isVector() ||
2675 VT.getVectorNumElements() ==
2676 Operand.getValueType().getVectorNumElements()) &&
2677 "Vector element count mismatch!");
2678 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2679 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2680 else if (OpOpcode == ISD::UNDEF)
2681 // sext(undef) = 0, because the top bits will all be the same.
2682 return getConstant(0, VT);
2684 case ISD::ZERO_EXTEND:
2685 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2686 "Invalid ZERO_EXTEND!");
2687 if (Operand.getValueType() == VT) return Operand; // noop extension
2688 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2689 "Invalid zext node, dst < src!");
2690 assert((!VT.isVector() ||
2691 VT.getVectorNumElements() ==
2692 Operand.getValueType().getVectorNumElements()) &&
2693 "Vector element count mismatch!");
2694 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2695 return getNode(ISD::ZERO_EXTEND, DL, VT,
2696 Operand.getNode()->getOperand(0));
2697 else if (OpOpcode == ISD::UNDEF)
2698 // zext(undef) = 0, because the top bits will be zero.
2699 return getConstant(0, VT);
2701 case ISD::ANY_EXTEND:
2702 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2703 "Invalid ANY_EXTEND!");
2704 if (Operand.getValueType() == VT) return Operand; // noop extension
2705 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2706 "Invalid anyext node, dst < src!");
2707 assert((!VT.isVector() ||
2708 VT.getVectorNumElements() ==
2709 Operand.getValueType().getVectorNumElements()) &&
2710 "Vector element count mismatch!");
2712 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2713 OpOpcode == ISD::ANY_EXTEND)
2714 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2715 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2716 else if (OpOpcode == ISD::UNDEF)
2717 return getUNDEF(VT);
2719 // (ext (trunx x)) -> x
2720 if (OpOpcode == ISD::TRUNCATE) {
2721 SDValue OpOp = Operand.getNode()->getOperand(0);
2722 if (OpOp.getValueType() == VT)
2727 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2728 "Invalid TRUNCATE!");
2729 if (Operand.getValueType() == VT) return Operand; // noop truncate
2730 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2731 "Invalid truncate node, src < dst!");
2732 assert((!VT.isVector() ||
2733 VT.getVectorNumElements() ==
2734 Operand.getValueType().getVectorNumElements()) &&
2735 "Vector element count mismatch!");
2736 if (OpOpcode == ISD::TRUNCATE)
2737 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2738 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2739 OpOpcode == ISD::ANY_EXTEND) {
2740 // If the source is smaller than the dest, we still need an extend.
2741 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2742 .bitsLT(VT.getScalarType()))
2743 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2744 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2745 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2746 return Operand.getNode()->getOperand(0);
2748 if (OpOpcode == ISD::UNDEF)
2749 return getUNDEF(VT);
2752 // Basic sanity checking.
2753 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2754 && "Cannot BITCAST between types of different sizes!");
2755 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2756 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2757 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2758 if (OpOpcode == ISD::UNDEF)
2759 return getUNDEF(VT);
2761 case ISD::SCALAR_TO_VECTOR:
2762 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2763 (VT.getVectorElementType() == Operand.getValueType() ||
2764 (VT.getVectorElementType().isInteger() &&
2765 Operand.getValueType().isInteger() &&
2766 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2767 "Illegal SCALAR_TO_VECTOR node!");
2768 if (OpOpcode == ISD::UNDEF)
2769 return getUNDEF(VT);
2770 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2771 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2772 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2773 Operand.getConstantOperandVal(1) == 0 &&
2774 Operand.getOperand(0).getValueType() == VT)
2775 return Operand.getOperand(0);
2778 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2779 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2780 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2781 Operand.getNode()->getOperand(0));
2782 if (OpOpcode == ISD::FNEG) // --X -> X
2783 return Operand.getNode()->getOperand(0);
2786 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2787 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2792 SDVTList VTs = getVTList(VT);
2793 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2794 FoldingSetNodeID ID;
2795 SDValue Ops[1] = { Operand };
2796 AddNodeIDNode(ID, Opcode, VTs, Ops);
2798 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2799 return SDValue(E, 0);
2801 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2802 DL.getDebugLoc(), VTs, Operand);
2803 CSEMap.InsertNode(N, IP);
2805 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2806 DL.getDebugLoc(), VTs, Operand);
2809 AllNodes.push_back(N);
2813 return SDValue(N, 0);
2816 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2817 SDNode *Cst1, SDNode *Cst2) {
2818 // If the opcode is a target-specific ISD node, there's nothing we can
2819 // do here and the operand rules may not line up with the below, so
2821 if (Opcode >= ISD::BUILTIN_OP_END)
2824 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2825 SmallVector<SDValue, 4> Outputs;
2826 EVT SVT = VT.getScalarType();
2828 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2829 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2830 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2833 if (Scalar1 && Scalar2)
2834 // Scalar instruction.
2835 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2837 // For vectors extract each constant element into Inputs so we can constant
2838 // fold them individually.
2839 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2840 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2844 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2846 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2847 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2848 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2849 if (!V1 || !V2) // Not a constant, bail.
2852 if (V1->isOpaque() || V2->isOpaque())
2855 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2856 // FIXME: This is valid and could be handled by truncating the APInts.
2857 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2860 Inputs.push_back(std::make_pair(V1, V2));
2864 // We have a number of constant values, constant fold them element by element.
2865 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2866 const APInt &C1 = Inputs[I].first->getAPIntValue();
2867 const APInt &C2 = Inputs[I].second->getAPIntValue();
2871 Outputs.push_back(getConstant(C1 + C2, SVT));
2874 Outputs.push_back(getConstant(C1 - C2, SVT));
2877 Outputs.push_back(getConstant(C1 * C2, SVT));
2880 if (!C2.getBoolValue())
2882 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2885 if (!C2.getBoolValue())
2887 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2890 if (!C2.getBoolValue())
2892 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2895 if (!C2.getBoolValue())
2897 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2900 Outputs.push_back(getConstant(C1 & C2, SVT));
2903 Outputs.push_back(getConstant(C1 | C2, SVT));
2906 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2909 Outputs.push_back(getConstant(C1 << C2, SVT));
2912 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2915 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2918 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2921 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2928 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2929 "Expected a scalar or vector!"));
2931 // Handle the scalar case first.
2933 return Outputs.back();
2935 // We may have a vector type but a scalar result. Create a splat.
2936 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2938 // Build a big vector out of the scalar elements we generated.
2939 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2942 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2944 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2945 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2948 case ISD::TokenFactor:
2949 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2950 N2.getValueType() == MVT::Other && "Invalid token factor!");
2951 // Fold trivial token factors.
2952 if (N1.getOpcode() == ISD::EntryToken) return N2;
2953 if (N2.getOpcode() == ISD::EntryToken) return N1;
2954 if (N1 == N2) return N1;
2956 case ISD::CONCAT_VECTORS:
2957 // Concat of UNDEFs is UNDEF.
2958 if (N1.getOpcode() == ISD::UNDEF &&
2959 N2.getOpcode() == ISD::UNDEF)
2960 return getUNDEF(VT);
2962 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2963 // one big BUILD_VECTOR.
2964 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2965 N2.getOpcode() == ISD::BUILD_VECTOR) {
2966 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2967 N1.getNode()->op_end());
2968 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2969 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2973 assert(VT.isInteger() && "This operator does not apply to FP types!");
2974 assert(N1.getValueType() == N2.getValueType() &&
2975 N1.getValueType() == VT && "Binary operator types must match!");
2976 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2977 // worth handling here.
2978 if (N2C && N2C->isNullValue())
2980 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2987 assert(VT.isInteger() && "This operator does not apply to FP types!");
2988 assert(N1.getValueType() == N2.getValueType() &&
2989 N1.getValueType() == VT && "Binary operator types must match!");
2990 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2991 // it's worth handling here.
2992 if (N2C && N2C->isNullValue())
3002 assert(VT.isInteger() && "This operator does not apply to FP types!");
3003 assert(N1.getValueType() == N2.getValueType() &&
3004 N1.getValueType() == VT && "Binary operator types must match!");
3011 if (getTarget().Options.UnsafeFPMath) {
3012 if (Opcode == ISD::FADD) {
3014 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3015 if (CFP->getValueAPF().isZero())
3018 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3019 if (CFP->getValueAPF().isZero())
3021 } else if (Opcode == ISD::FSUB) {
3023 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3024 if (CFP->getValueAPF().isZero())
3026 } else if (Opcode == ISD::FMUL) {
3027 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3030 // If the first operand isn't the constant, try the second
3032 CFP = dyn_cast<ConstantFPSDNode>(N2);
3039 return SDValue(CFP,0);
3041 if (CFP->isExactlyValue(1.0))
3046 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3047 assert(N1.getValueType() == N2.getValueType() &&
3048 N1.getValueType() == VT && "Binary operator types must match!");
3050 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3051 assert(N1.getValueType() == VT &&
3052 N1.getValueType().isFloatingPoint() &&
3053 N2.getValueType().isFloatingPoint() &&
3054 "Invalid FCOPYSIGN!");
3061 assert(VT == N1.getValueType() &&
3062 "Shift operators return type must be the same as their first arg");
3063 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3064 "Shifts only work on integers");
3065 assert((!VT.isVector() || VT == N2.getValueType()) &&
3066 "Vector shift amounts must be in the same as their first arg");
3067 // Verify that the shift amount VT is bit enough to hold valid shift
3068 // amounts. This catches things like trying to shift an i1024 value by an
3069 // i8, which is easy to fall into in generic code that uses
3070 // TLI.getShiftAmount().
3071 assert(N2.getValueType().getSizeInBits() >=
3072 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3073 "Invalid use of small shift amount with oversized value!");
3075 // Always fold shifts of i1 values so the code generator doesn't need to
3076 // handle them. Since we know the size of the shift has to be less than the
3077 // size of the value, the shift/rotate count is guaranteed to be zero.
3080 if (N2C && N2C->isNullValue())
3083 case ISD::FP_ROUND_INREG: {
3084 EVT EVT = cast<VTSDNode>(N2)->getVT();
3085 assert(VT == N1.getValueType() && "Not an inreg round!");
3086 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3087 "Cannot FP_ROUND_INREG integer types");
3088 assert(EVT.isVector() == VT.isVector() &&
3089 "FP_ROUND_INREG type should be vector iff the operand "
3091 assert((!EVT.isVector() ||
3092 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3093 "Vector element counts must match in FP_ROUND_INREG");
3094 assert(EVT.bitsLE(VT) && "Not rounding down!");
3096 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3100 assert(VT.isFloatingPoint() &&
3101 N1.getValueType().isFloatingPoint() &&
3102 VT.bitsLE(N1.getValueType()) &&
3103 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3104 if (N1.getValueType() == VT) return N1; // noop conversion.
3106 case ISD::AssertSext:
3107 case ISD::AssertZext: {
3108 EVT EVT = cast<VTSDNode>(N2)->getVT();
3109 assert(VT == N1.getValueType() && "Not an inreg extend!");
3110 assert(VT.isInteger() && EVT.isInteger() &&
3111 "Cannot *_EXTEND_INREG FP types");
3112 assert(!EVT.isVector() &&
3113 "AssertSExt/AssertZExt type should be the vector element type "
3114 "rather than the vector type!");
3115 assert(EVT.bitsLE(VT) && "Not extending!");
3116 if (VT == EVT) return N1; // noop assertion.
3119 case ISD::SIGN_EXTEND_INREG: {
3120 EVT EVT = cast<VTSDNode>(N2)->getVT();
3121 assert(VT == N1.getValueType() && "Not an inreg extend!");
3122 assert(VT.isInteger() && EVT.isInteger() &&
3123 "Cannot *_EXTEND_INREG FP types");
3124 assert(EVT.isVector() == VT.isVector() &&
3125 "SIGN_EXTEND_INREG type should be vector iff the operand "
3127 assert((!EVT.isVector() ||
3128 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3129 "Vector element counts must match in SIGN_EXTEND_INREG");
3130 assert(EVT.bitsLE(VT) && "Not extending!");
3131 if (EVT == VT) return N1; // Not actually extending
3134 APInt Val = N1C->getAPIntValue();
3135 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3136 Val <<= Val.getBitWidth()-FromBits;
3137 Val = Val.ashr(Val.getBitWidth()-FromBits);
3138 return getConstant(Val, VT);
3142 case ISD::EXTRACT_VECTOR_ELT:
3143 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3144 if (N1.getOpcode() == ISD::UNDEF)
3145 return getUNDEF(VT);
3147 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3148 // expanding copies of large vectors from registers.
3150 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3151 N1.getNumOperands() > 0) {
3153 N1.getOperand(0).getValueType().getVectorNumElements();
3154 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3155 N1.getOperand(N2C->getZExtValue() / Factor),
3156 getConstant(N2C->getZExtValue() % Factor,
3157 N2.getValueType()));
3160 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3161 // expanding large vector constants.
3162 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3163 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3165 if (VT != Elt.getValueType())
3166 // If the vector element type is not legal, the BUILD_VECTOR operands
3167 // are promoted and implicitly truncated, and the result implicitly
3168 // extended. Make that explicit here.
3169 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3174 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3175 // operations are lowered to scalars.
3176 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3177 // If the indices are the same, return the inserted element else
3178 // if the indices are known different, extract the element from
3179 // the original vector.
3180 SDValue N1Op2 = N1.getOperand(2);
3181 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3183 if (N1Op2C && N2C) {
3184 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3185 if (VT == N1.getOperand(1).getValueType())
3186 return N1.getOperand(1);
3188 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3191 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3195 case ISD::EXTRACT_ELEMENT:
3196 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3197 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3198 (N1.getValueType().isInteger() == VT.isInteger()) &&
3199 N1.getValueType() != VT &&
3200 "Wrong types for EXTRACT_ELEMENT!");
3202 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3203 // 64-bit integers into 32-bit parts. Instead of building the extract of
3204 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3205 if (N1.getOpcode() == ISD::BUILD_PAIR)
3206 return N1.getOperand(N2C->getZExtValue());
3208 // EXTRACT_ELEMENT of a constant int is also very common.
3209 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3210 unsigned ElementSize = VT.getSizeInBits();
3211 unsigned Shift = ElementSize * N2C->getZExtValue();
3212 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3213 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3216 case ISD::EXTRACT_SUBVECTOR: {
3218 if (VT.isSimple() && N1.getValueType().isSimple()) {
3219 assert(VT.isVector() && N1.getValueType().isVector() &&
3220 "Extract subvector VTs must be a vectors!");
3221 assert(VT.getVectorElementType() ==
3222 N1.getValueType().getVectorElementType() &&
3223 "Extract subvector VTs must have the same element type!");
3224 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3225 "Extract subvector must be from larger vector to smaller vector!");
3227 if (isa<ConstantSDNode>(Index.getNode())) {
3228 assert((VT.getVectorNumElements() +
3229 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3230 <= N1.getValueType().getVectorNumElements())
3231 && "Extract subvector overflow!");
3234 // Trivial extraction.
3235 if (VT.getSimpleVT() == N1.getSimpleValueType())
3242 // Perform trivial constant folding.
3243 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3244 if (SV.getNode()) return SV;
3246 // Canonicalize constant to RHS if commutative.
3247 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3248 std::swap(N1C, N2C);
3252 // Constant fold FP operations.
3253 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3254 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3256 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3257 // Canonicalize constant to RHS if commutative.
3258 std::swap(N1CFP, N2CFP);
3261 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3262 APFloat::opStatus s;
3265 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3266 if (s != APFloat::opInvalidOp)
3267 return getConstantFP(V1, VT);
3270 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3271 if (s!=APFloat::opInvalidOp)
3272 return getConstantFP(V1, VT);
3275 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3276 if (s!=APFloat::opInvalidOp)
3277 return getConstantFP(V1, VT);
3280 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3281 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3282 return getConstantFP(V1, VT);
3285 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3286 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3287 return getConstantFP(V1, VT);
3289 case ISD::FCOPYSIGN:
3291 return getConstantFP(V1, VT);
3296 if (Opcode == ISD::FP_ROUND) {
3297 APFloat V = N1CFP->getValueAPF(); // make copy
3299 // This can return overflow, underflow, or inexact; we don't care.
3300 // FIXME need to be more flexible about rounding mode.
3301 (void)V.convert(EVTToAPFloatSemantics(VT),
3302 APFloat::rmNearestTiesToEven, &ignored);
3303 return getConstantFP(V, VT);
3307 // Canonicalize an UNDEF to the RHS, even over a constant.
3308 if (N1.getOpcode() == ISD::UNDEF) {
3309 if (isCommutativeBinOp(Opcode)) {
3313 case ISD::FP_ROUND_INREG:
3314 case ISD::SIGN_EXTEND_INREG:
3320 return N1; // fold op(undef, arg2) -> undef
3328 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3329 // For vectors, we can't easily build an all zero vector, just return
3336 // Fold a bunch of operators when the RHS is undef.
3337 if (N2.getOpcode() == ISD::UNDEF) {
3340 if (N1.getOpcode() == ISD::UNDEF)
3341 // Handle undef ^ undef -> 0 special case. This is a common
3343 return getConstant(0, VT);
3353 return N2; // fold op(arg1, undef) -> undef
3359 if (getTarget().Options.UnsafeFPMath)
3367 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3368 // For vectors, we can't easily build an all zero vector, just return
3373 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3374 // For vectors, we can't easily build an all one vector, just return
3382 // Memoize this node if possible.
3384 SDVTList VTs = getVTList(VT);
3385 if (VT != MVT::Glue) {
3386 SDValue Ops[] = { N1, N2 };
3387 FoldingSetNodeID ID;
3388 AddNodeIDNode(ID, Opcode, VTs, Ops);
3390 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3391 return SDValue(E, 0);
3393 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3394 DL.getDebugLoc(), VTs, N1, N2);
3395 CSEMap.InsertNode(N, IP);
3397 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3398 DL.getDebugLoc(), VTs, N1, N2);
3401 AllNodes.push_back(N);
3405 return SDValue(N, 0);
3408 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3409 SDValue N1, SDValue N2, SDValue N3) {
3410 // Perform various simplifications.
3411 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3414 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3415 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3416 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3417 if (N1CFP && N2CFP && N3CFP) {
3418 APFloat V1 = N1CFP->getValueAPF();
3419 const APFloat &V2 = N2CFP->getValueAPF();
3420 const APFloat &V3 = N3CFP->getValueAPF();
3421 APFloat::opStatus s =
3422 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3423 if (s != APFloat::opInvalidOp)
3424 return getConstantFP(V1, VT);
3428 case ISD::CONCAT_VECTORS:
3429 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3430 // one big BUILD_VECTOR.
3431 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3432 N2.getOpcode() == ISD::BUILD_VECTOR &&
3433 N3.getOpcode() == ISD::BUILD_VECTOR) {
3434 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3435 N1.getNode()->op_end());
3436 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3437 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3438 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3442 // Use FoldSetCC to simplify SETCC's.
3443 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3444 if (Simp.getNode()) return Simp;
3449 if (N1C->getZExtValue())
3450 return N2; // select true, X, Y -> X
3451 return N3; // select false, X, Y -> Y
3454 if (N2 == N3) return N2; // select C, X, X -> X
3456 case ISD::VECTOR_SHUFFLE:
3457 llvm_unreachable("should use getVectorShuffle constructor!");
3458 case ISD::INSERT_SUBVECTOR: {
3460 if (VT.isSimple() && N1.getValueType().isSimple()
3461 && N2.getValueType().isSimple()) {
3462 assert(VT.isVector() && N1.getValueType().isVector() &&
3463 N2.getValueType().isVector() &&
3464 "Insert subvector VTs must be a vectors");
3465 assert(VT == N1.getValueType() &&
3466 "Dest and insert subvector source types must match!");
3467 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3468 "Insert subvector must be from smaller vector to larger vector!");
3469 if (isa<ConstantSDNode>(Index.getNode())) {
3470 assert((N2.getValueType().getVectorNumElements() +
3471 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3472 <= VT.getVectorNumElements())
3473 && "Insert subvector overflow!");
3476 // Trivial insertion.
3477 if (VT.getSimpleVT() == N2.getSimpleValueType())
3483 // Fold bit_convert nodes from a type to themselves.
3484 if (N1.getValueType() == VT)
3489 // Memoize node if it doesn't produce a flag.
3491 SDVTList VTs = getVTList(VT);
3492 if (VT != MVT::Glue) {
3493 SDValue Ops[] = { N1, N2, N3 };
3494 FoldingSetNodeID ID;
3495 AddNodeIDNode(ID, Opcode, VTs, Ops);
3497 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3498 return SDValue(E, 0);
3500 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3501 DL.getDebugLoc(), VTs, N1, N2, N3);
3502 CSEMap.InsertNode(N, IP);
3504 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3505 DL.getDebugLoc(), VTs, N1, N2, N3);
3508 AllNodes.push_back(N);
3512 return SDValue(N, 0);
3515 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3516 SDValue N1, SDValue N2, SDValue N3,
3518 SDValue Ops[] = { N1, N2, N3, N4 };
3519 return getNode(Opcode, DL, VT, Ops);
3522 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3523 SDValue N1, SDValue N2, SDValue N3,
3524 SDValue N4, SDValue N5) {
3525 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3526 return getNode(Opcode, DL, VT, Ops);
3529 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3530 /// the incoming stack arguments to be loaded from the stack.
3531 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3532 SmallVector<SDValue, 8> ArgChains;
3534 // Include the original chain at the beginning of the list. When this is
3535 // used by target LowerCall hooks, this helps legalize find the
3536 // CALLSEQ_BEGIN node.
3537 ArgChains.push_back(Chain);
3539 // Add a chain value for each stack argument.
3540 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3541 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3542 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3543 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3544 if (FI->getIndex() < 0)
3545 ArgChains.push_back(SDValue(L, 1));
3547 // Build a tokenfactor for all the chains.
3548 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3551 /// getMemsetValue - Vectorized representation of the memset value
3553 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3555 assert(Value.getOpcode() != ISD::UNDEF);
3557 unsigned NumBits = VT.getScalarType().getSizeInBits();
3558 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3559 assert(C->getAPIntValue().getBitWidth() == 8);
3560 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3562 return DAG.getConstant(Val, VT);
3563 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3566 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3568 // Use a multiplication with 0x010101... to extend the input to the
3570 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3571 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3577 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3578 /// used when a memcpy is turned into a memset when the source is a constant
3580 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3581 const TargetLowering &TLI, StringRef Str) {
3582 // Handle vector with all elements zero.
3585 return DAG.getConstant(0, VT);
3586 else if (VT == MVT::f32 || VT == MVT::f64)
3587 return DAG.getConstantFP(0.0, VT);
3588 else if (VT.isVector()) {
3589 unsigned NumElts = VT.getVectorNumElements();
3590 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3591 return DAG.getNode(ISD::BITCAST, dl, VT,
3592 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3595 llvm_unreachable("Expected type!");
3598 assert(!VT.isVector() && "Can't handle vector type here!");
3599 unsigned NumVTBits = VT.getSizeInBits();
3600 unsigned NumVTBytes = NumVTBits / 8;
3601 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3603 APInt Val(NumVTBits, 0);
3604 if (TLI.isLittleEndian()) {
3605 for (unsigned i = 0; i != NumBytes; ++i)
3606 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3608 for (unsigned i = 0; i != NumBytes; ++i)
3609 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3612 // If the "cost" of materializing the integer immediate is less than the cost
3613 // of a load, then it is cost effective to turn the load into the immediate.
3614 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3615 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3616 return DAG.getConstant(Val, VT);
3617 return SDValue(nullptr, 0);
3620 /// getMemBasePlusOffset - Returns base and offset node for the
3622 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3623 SelectionDAG &DAG) {
3624 EVT VT = Base.getValueType();
3625 return DAG.getNode(ISD::ADD, dl,
3626 VT, Base, DAG.getConstant(Offset, VT));
3629 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3631 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3632 unsigned SrcDelta = 0;
3633 GlobalAddressSDNode *G = nullptr;
3634 if (Src.getOpcode() == ISD::GlobalAddress)
3635 G = cast<GlobalAddressSDNode>(Src);
3636 else if (Src.getOpcode() == ISD::ADD &&
3637 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3638 Src.getOperand(1).getOpcode() == ISD::Constant) {
3639 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3640 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3645 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3648 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3649 /// to replace the memset / memcpy. Return true if the number of memory ops
3650 /// is below the threshold. It returns the types of the sequence of
3651 /// memory ops to perform memset / memcpy by reference.
3652 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3653 unsigned Limit, uint64_t Size,
3654 unsigned DstAlign, unsigned SrcAlign,
3660 const TargetLowering &TLI) {
3661 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3662 "Expecting memcpy / memset source to meet alignment requirement!");
3663 // If 'SrcAlign' is zero, that means the memory operation does not need to
3664 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3665 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3666 // is the specified alignment of the memory operation. If it is zero, that
3667 // means it's possible to change the alignment of the destination.
3668 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3669 // not need to be loaded.
3670 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3671 IsMemset, ZeroMemset, MemcpyStrSrc,
3672 DAG.getMachineFunction());
3674 if (VT == MVT::Other) {
3676 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3677 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3678 VT = TLI.getPointerTy();
3680 switch (DstAlign & 7) {
3681 case 0: VT = MVT::i64; break;
3682 case 4: VT = MVT::i32; break;
3683 case 2: VT = MVT::i16; break;
3684 default: VT = MVT::i8; break;
3689 while (!TLI.isTypeLegal(LVT))
3690 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3691 assert(LVT.isInteger());
3697 unsigned NumMemOps = 0;
3699 unsigned VTSize = VT.getSizeInBits() / 8;
3700 while (VTSize > Size) {
3701 // For now, only use non-vector load / store's for the left-over pieces.
3706 if (VT.isVector() || VT.isFloatingPoint()) {
3707 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3708 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3709 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3711 else if (NewVT == MVT::i64 &&
3712 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3713 TLI.isSafeMemOpType(MVT::f64)) {
3714 // i64 is usually not legal on 32-bit targets, but f64 may be.
3722 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3723 if (NewVT == MVT::i8)
3725 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3727 NewVTSize = NewVT.getSizeInBits() / 8;
3729 // If the new VT cannot cover all of the remaining bits, then consider
3730 // issuing a (or a pair of) unaligned and overlapping load / store.
3731 // FIXME: Only does this for 64-bit or more since we don't have proper
3732 // cost model for unaligned load / store.
3735 if (NumMemOps && AllowOverlap &&
3736 VTSize >= 8 && NewVTSize < Size &&
3737 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3745 if (++NumMemOps > Limit)
3748 MemOps.push_back(VT);
3755 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3756 SDValue Chain, SDValue Dst,
3757 SDValue Src, uint64_t Size,
3758 unsigned Align, bool isVol,
3760 MachinePointerInfo DstPtrInfo,
3761 MachinePointerInfo SrcPtrInfo) {
3762 // Turn a memcpy of undef to nop.
3763 if (Src.getOpcode() == ISD::UNDEF)
3766 // Expand memcpy to a series of load and store ops if the size operand falls
3767 // below a certain threshold.
3768 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3769 // rather than maybe a humongous number of loads and stores.
3770 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3771 std::vector<EVT> MemOps;
3772 bool DstAlignCanChange = false;
3773 MachineFunction &MF = DAG.getMachineFunction();
3774 MachineFrameInfo *MFI = MF.getFrameInfo();
3776 MF.getFunction()->getAttributes().
3777 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3778 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3779 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3780 DstAlignCanChange = true;
3781 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3782 if (Align > SrcAlign)
3785 bool CopyFromStr = isMemSrcFromString(Src, Str);
3786 bool isZeroStr = CopyFromStr && Str.empty();
3787 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3789 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3790 (DstAlignCanChange ? 0 : Align),
3791 (isZeroStr ? 0 : SrcAlign),
3792 false, false, CopyFromStr, true, DAG, TLI))
3795 if (DstAlignCanChange) {
3796 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3797 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3799 // Don't promote to an alignment that would require dynamic stack
3801 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3802 if (!TRI->needsStackRealignment(MF))
3803 while (NewAlign > Align &&
3804 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3807 if (NewAlign > Align) {
3808 // Give the stack frame object a larger alignment if needed.
3809 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3810 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3815 SmallVector<SDValue, 8> OutChains;
3816 unsigned NumMemOps = MemOps.size();
3817 uint64_t SrcOff = 0, DstOff = 0;
3818 for (unsigned i = 0; i != NumMemOps; ++i) {
3820 unsigned VTSize = VT.getSizeInBits() / 8;
3821 SDValue Value, Store;
3823 if (VTSize > Size) {
3824 // Issuing an unaligned load / store pair that overlaps with the previous
3825 // pair. Adjust the offset accordingly.
3826 assert(i == NumMemOps-1 && i != 0);
3827 SrcOff -= VTSize - Size;
3828 DstOff -= VTSize - Size;
3832 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3833 // It's unlikely a store of a vector immediate can be done in a single
3834 // instruction. It would require a load from a constantpool first.
3835 // We only handle zero vectors here.
3836 // FIXME: Handle other cases where store of vector immediate is done in
3837 // a single instruction.
3838 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3839 if (Value.getNode())
3840 Store = DAG.getStore(Chain, dl, Value,
3841 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3842 DstPtrInfo.getWithOffset(DstOff), isVol,
3846 if (!Store.getNode()) {
3847 // The type might not be legal for the target. This should only happen
3848 // if the type is smaller than a legal type, as on PPC, so the right
3849 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3850 // to Load/Store if NVT==VT.
3851 // FIXME does the case above also need this?
3852 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3853 assert(NVT.bitsGE(VT));
3854 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3855 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3856 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3857 MinAlign(SrcAlign, SrcOff));
3858 Store = DAG.getTruncStore(Chain, dl, Value,
3859 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3860 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3863 OutChains.push_back(Store);
3869 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3872 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3873 SDValue Chain, SDValue Dst,
3874 SDValue Src, uint64_t Size,
3875 unsigned Align, bool isVol,
3877 MachinePointerInfo DstPtrInfo,
3878 MachinePointerInfo SrcPtrInfo) {
3879 // Turn a memmove of undef to nop.
3880 if (Src.getOpcode() == ISD::UNDEF)
3883 // Expand memmove to a series of load and store ops if the size operand falls
3884 // below a certain threshold.
3885 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3886 std::vector<EVT> MemOps;
3887 bool DstAlignCanChange = false;
3888 MachineFunction &MF = DAG.getMachineFunction();
3889 MachineFrameInfo *MFI = MF.getFrameInfo();
3890 bool OptSize = MF.getFunction()->getAttributes().
3891 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3892 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3893 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3894 DstAlignCanChange = true;
3895 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3896 if (Align > SrcAlign)
3898 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3900 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3901 (DstAlignCanChange ? 0 : Align), SrcAlign,
3902 false, false, false, false, DAG, TLI))
3905 if (DstAlignCanChange) {
3906 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3907 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3908 if (NewAlign > Align) {
3909 // Give the stack frame object a larger alignment if needed.
3910 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3911 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3916 uint64_t SrcOff = 0, DstOff = 0;
3917 SmallVector<SDValue, 8> LoadValues;
3918 SmallVector<SDValue, 8> LoadChains;
3919 SmallVector<SDValue, 8> OutChains;
3920 unsigned NumMemOps = MemOps.size();
3921 for (unsigned i = 0; i < NumMemOps; i++) {
3923 unsigned VTSize = VT.getSizeInBits() / 8;
3926 Value = DAG.getLoad(VT, dl, Chain,
3927 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3928 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3929 false, false, SrcAlign);
3930 LoadValues.push_back(Value);
3931 LoadChains.push_back(Value.getValue(1));
3934 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3936 for (unsigned i = 0; i < NumMemOps; i++) {
3938 unsigned VTSize = VT.getSizeInBits() / 8;
3941 Store = DAG.getStore(Chain, dl, LoadValues[i],
3942 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3943 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3944 OutChains.push_back(Store);
3948 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3951 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3954 /// \param DAG Selection DAG where lowered code is placed.
3955 /// \param dl Link to corresponding IR location.
3956 /// \param Chain Control flow dependency.
3957 /// \param Dst Pointer to destination memory location.
3958 /// \param Src Value of byte to write into the memory.
3959 /// \param Size Number of bytes to write.
3960 /// \param Align Alignment of the destination in bytes.
3961 /// \param isVol True if destination is volatile.
3962 /// \param DstPtrInfo IR information on the memory pointer.
3963 /// \returns New head in the control flow, if lowering was successful, empty
3964 /// SDValue otherwise.
3966 /// The function tries to replace 'llvm.memset' intrinsic with several store
3967 /// operations and value calculation code. This is usually profitable for small
3969 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3970 SDValue Chain, SDValue Dst,
3971 SDValue Src, uint64_t Size,
3972 unsigned Align, bool isVol,
3973 MachinePointerInfo DstPtrInfo) {
3974 // Turn a memset of undef to nop.
3975 if (Src.getOpcode() == ISD::UNDEF)
3978 // Expand memset to a series of load/store ops if the size operand
3979 // falls below a certain threshold.
3980 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3981 std::vector<EVT> MemOps;
3982 bool DstAlignCanChange = false;
3983 MachineFunction &MF = DAG.getMachineFunction();
3984 MachineFrameInfo *MFI = MF.getFrameInfo();
3985 bool OptSize = MF.getFunction()->getAttributes().
3986 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3987 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3988 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3989 DstAlignCanChange = true;
3991 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3992 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3993 Size, (DstAlignCanChange ? 0 : Align), 0,
3994 true, IsZeroVal, false, true, DAG, TLI))
3997 if (DstAlignCanChange) {
3998 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3999 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
4000 if (NewAlign > Align) {
4001 // Give the stack frame object a larger alignment if needed.
4002 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
4003 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4008 SmallVector<SDValue, 8> OutChains;
4009 uint64_t DstOff = 0;
4010 unsigned NumMemOps = MemOps.size();
4012 // Find the largest store and generate the bit pattern for it.
4013 EVT LargestVT = MemOps[0];
4014 for (unsigned i = 1; i < NumMemOps; i++)
4015 if (MemOps[i].bitsGT(LargestVT))
4016 LargestVT = MemOps[i];
4017 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4019 for (unsigned i = 0; i < NumMemOps; i++) {
4021 unsigned VTSize = VT.getSizeInBits() / 8;
4022 if (VTSize > Size) {
4023 // Issuing an unaligned load / store pair that overlaps with the previous
4024 // pair. Adjust the offset accordingly.
4025 assert(i == NumMemOps-1 && i != 0);
4026 DstOff -= VTSize - Size;
4029 // If this store is smaller than the largest store see whether we can get
4030 // the smaller value for free with a truncate.
4031 SDValue Value = MemSetValue;
4032 if (VT.bitsLT(LargestVT)) {
4033 if (!LargestVT.isVector() && !VT.isVector() &&
4034 TLI.isTruncateFree(LargestVT, VT))
4035 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4037 Value = getMemsetValue(Src, VT, DAG, dl);
4039 assert(Value.getValueType() == VT && "Value with wrong type.");
4040 SDValue Store = DAG.getStore(Chain, dl, Value,
4041 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4042 DstPtrInfo.getWithOffset(DstOff),
4043 isVol, false, Align);
4044 OutChains.push_back(Store);
4045 DstOff += VT.getSizeInBits() / 8;
4049 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4052 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4053 SDValue Src, SDValue Size,
4054 unsigned Align, bool isVol, bool AlwaysInline,
4055 MachinePointerInfo DstPtrInfo,
4056 MachinePointerInfo SrcPtrInfo) {
4057 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4059 // Check to see if we should lower the memcpy to loads and stores first.
4060 // For cases within the target-specified limits, this is the best choice.
4061 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4063 // Memcpy with size zero? Just return the original chain.
4064 if (ConstantSize->isNullValue())
4067 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4068 ConstantSize->getZExtValue(),Align,
4069 isVol, false, DstPtrInfo, SrcPtrInfo);
4070 if (Result.getNode())
4074 // Then check to see if we should lower the memcpy with target-specific
4075 // code. If the target chooses to do this, this is the next best.
4077 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4078 isVol, AlwaysInline,
4079 DstPtrInfo, SrcPtrInfo);
4080 if (Result.getNode())
4083 // If we really need inline code and the target declined to provide it,
4084 // use a (potentially long) sequence of loads and stores.
4086 assert(ConstantSize && "AlwaysInline requires a constant size!");
4087 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4088 ConstantSize->getZExtValue(), Align, isVol,
4089 true, DstPtrInfo, SrcPtrInfo);
4092 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4093 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4094 // respect volatile, so they may do things like read or write memory
4095 // beyond the given memory regions. But fixing this isn't easy, and most
4096 // people don't care.
4098 const TargetLowering *TLI = TM.getTargetLowering();
4100 // Emit a library call.
4101 TargetLowering::ArgListTy Args;
4102 TargetLowering::ArgListEntry Entry;
4103 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4104 Entry.Node = Dst; Args.push_back(Entry);
4105 Entry.Node = Src; Args.push_back(Entry);
4106 Entry.Node = Size; Args.push_back(Entry);
4107 // FIXME: pass in SDLoc
4109 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4110 false, false, false, false, 0,
4111 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4112 /*isTailCall=*/false,
4113 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4114 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4115 TLI->getPointerTy()),
4117 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4119 return CallResult.second;
4122 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4123 SDValue Src, SDValue Size,
4124 unsigned Align, bool isVol,
4125 MachinePointerInfo DstPtrInfo,
4126 MachinePointerInfo SrcPtrInfo) {
4127 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4129 // Check to see if we should lower the memmove to loads and stores first.
4130 // For cases within the target-specified limits, this is the best choice.
4131 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4133 // Memmove with size zero? Just return the original chain.
4134 if (ConstantSize->isNullValue())
4138 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4139 ConstantSize->getZExtValue(), Align, isVol,
4140 false, DstPtrInfo, SrcPtrInfo);
4141 if (Result.getNode())
4145 // Then check to see if we should lower the memmove with target-specific
4146 // code. If the target chooses to do this, this is the next best.
4148 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4149 DstPtrInfo, SrcPtrInfo);
4150 if (Result.getNode())
4153 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4154 // not be safe. See memcpy above for more details.
4156 const TargetLowering *TLI = TM.getTargetLowering();
4158 // Emit a library call.
4159 TargetLowering::ArgListTy Args;
4160 TargetLowering::ArgListEntry Entry;
4161 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4162 Entry.Node = Dst; Args.push_back(Entry);
4163 Entry.Node = Src; Args.push_back(Entry);
4164 Entry.Node = Size; Args.push_back(Entry);
4165 // FIXME: pass in SDLoc
4167 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4168 false, false, false, false, 0,
4169 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4170 /*isTailCall=*/false,
4171 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4172 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4173 TLI->getPointerTy()),
4175 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4177 return CallResult.second;
4180 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4181 SDValue Src, SDValue Size,
4182 unsigned Align, bool isVol,
4183 MachinePointerInfo DstPtrInfo) {
4184 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4186 // Check to see if we should lower the memset to stores first.
4187 // For cases within the target-specified limits, this is the best choice.
4188 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4190 // Memset with size zero? Just return the original chain.
4191 if (ConstantSize->isNullValue())
4195 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4196 Align, isVol, DstPtrInfo);
4198 if (Result.getNode())
4202 // Then check to see if we should lower the memset with target-specific
4203 // code. If the target chooses to do this, this is the next best.
4205 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4207 if (Result.getNode())
4210 // Emit a library call.
4211 const TargetLowering *TLI = TM.getTargetLowering();
4212 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4213 TargetLowering::ArgListTy Args;
4214 TargetLowering::ArgListEntry Entry;
4215 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4216 Args.push_back(Entry);
4217 // Extend or truncate the argument to be an i32 value for the call.
4218 if (Src.getValueType().bitsGT(MVT::i32))
4219 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4221 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4223 Entry.Ty = Type::getInt32Ty(*getContext());
4224 Entry.isSExt = true;
4225 Args.push_back(Entry);
4227 Entry.Ty = IntPtrTy;
4228 Entry.isSExt = false;
4229 Args.push_back(Entry);
4230 // FIXME: pass in SDLoc
4232 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4233 false, false, false, false, 0,
4234 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4235 /*isTailCall=*/false,
4236 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4237 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4238 TLI->getPointerTy()),
4240 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4242 return CallResult.second;
4245 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4246 SDVTList VTList, ArrayRef<SDValue> Ops,
4247 MachineMemOperand *MMO,
4248 AtomicOrdering SuccessOrdering,
4249 AtomicOrdering FailureOrdering,
4250 SynchronizationScope SynchScope) {
4251 FoldingSetNodeID ID;
4252 ID.AddInteger(MemVT.getRawBits());
4253 AddNodeIDNode(ID, Opcode, VTList, Ops);
4254 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4256 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4257 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4258 return SDValue(E, 0);
4261 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4262 // SDNode doesn't have access to it. This memory will be "leaked" when
4263 // the node is deallocated, but recovered when the allocator is released.
4264 // If the number of operands is less than 5 we use AtomicSDNode's internal
4266 unsigned NumOps = Ops.size();
4267 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4270 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4271 dl.getDebugLoc(), VTList, MemVT,
4272 Ops.data(), DynOps, NumOps, MMO,
4273 SuccessOrdering, FailureOrdering,
4275 CSEMap.InsertNode(N, IP);
4276 AllNodes.push_back(N);
4277 return SDValue(N, 0);
4280 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4281 SDVTList VTList, ArrayRef<SDValue> Ops,
4282 MachineMemOperand *MMO,
4283 AtomicOrdering Ordering,
4284 SynchronizationScope SynchScope) {
4285 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4286 Ordering, SynchScope);
4289 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4290 SDValue Chain, SDValue Ptr, SDValue Cmp,
4291 SDValue Swp, MachinePointerInfo PtrInfo,
4293 AtomicOrdering SuccessOrdering,
4294 AtomicOrdering FailureOrdering,
4295 SynchronizationScope SynchScope) {
4296 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4297 Alignment = getEVTAlignment(MemVT);
4299 MachineFunction &MF = getMachineFunction();
4301 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4302 // For now, atomics are considered to be volatile always.
4303 // FIXME: Volatile isn't really correct; we should keep track of atomic
4304 // orderings in the memoperand.
4305 unsigned Flags = MachineMemOperand::MOVolatile;
4306 if (Opcode != ISD::ATOMIC_STORE)
4307 Flags |= MachineMemOperand::MOLoad;
4308 if (Opcode != ISD::ATOMIC_LOAD)
4309 Flags |= MachineMemOperand::MOStore;
4311 MachineMemOperand *MMO =
4312 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4314 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4315 SuccessOrdering, FailureOrdering, SynchScope);
4318 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4320 SDValue Ptr, SDValue Cmp,
4321 SDValue Swp, MachineMemOperand *MMO,
4322 AtomicOrdering SuccessOrdering,
4323 AtomicOrdering FailureOrdering,
4324 SynchronizationScope SynchScope) {
4325 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4326 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4328 EVT VT = Cmp.getValueType();
4330 SDVTList VTs = getVTList(VT, MVT::Other);
4331 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4332 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4333 FailureOrdering, SynchScope);
4336 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4338 SDValue Ptr, SDValue Val,
4339 const Value* PtrVal,
4341 AtomicOrdering Ordering,
4342 SynchronizationScope SynchScope) {
4343 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4344 Alignment = getEVTAlignment(MemVT);
4346 MachineFunction &MF = getMachineFunction();
4347 // An atomic store does not load. An atomic load does not store.
4348 // (An atomicrmw obviously both loads and stores.)
4349 // For now, atomics are considered to be volatile always, and they are
4351 // FIXME: Volatile isn't really correct; we should keep track of atomic
4352 // orderings in the memoperand.
4353 unsigned Flags = MachineMemOperand::MOVolatile;
4354 if (Opcode != ISD::ATOMIC_STORE)
4355 Flags |= MachineMemOperand::MOLoad;
4356 if (Opcode != ISD::ATOMIC_LOAD)
4357 Flags |= MachineMemOperand::MOStore;
4359 MachineMemOperand *MMO =
4360 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4361 MemVT.getStoreSize(), Alignment);
4363 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4364 Ordering, SynchScope);
4367 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4369 SDValue Ptr, SDValue Val,
4370 MachineMemOperand *MMO,
4371 AtomicOrdering Ordering,
4372 SynchronizationScope SynchScope) {
4373 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4374 Opcode == ISD::ATOMIC_LOAD_SUB ||
4375 Opcode == ISD::ATOMIC_LOAD_AND ||
4376 Opcode == ISD::ATOMIC_LOAD_OR ||
4377 Opcode == ISD::ATOMIC_LOAD_XOR ||
4378 Opcode == ISD::ATOMIC_LOAD_NAND ||
4379 Opcode == ISD::ATOMIC_LOAD_MIN ||
4380 Opcode == ISD::ATOMIC_LOAD_MAX ||
4381 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4382 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4383 Opcode == ISD::ATOMIC_SWAP ||
4384 Opcode == ISD::ATOMIC_STORE) &&
4385 "Invalid Atomic Op");
4387 EVT VT = Val.getValueType();
4389 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4390 getVTList(VT, MVT::Other);
4391 SDValue Ops[] = {Chain, Ptr, Val};
4392 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4395 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4396 EVT VT, SDValue Chain,
4398 MachineMemOperand *MMO,
4399 AtomicOrdering Ordering,
4400 SynchronizationScope SynchScope) {
4401 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4403 SDVTList VTs = getVTList(VT, MVT::Other);
4404 SDValue Ops[] = {Chain, Ptr};
4405 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4408 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4409 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4410 if (Ops.size() == 1)
4413 SmallVector<EVT, 4> VTs;
4414 VTs.reserve(Ops.size());
4415 for (unsigned i = 0; i < Ops.size(); ++i)
4416 VTs.push_back(Ops[i].getValueType());
4417 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4421 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4422 ArrayRef<SDValue> Ops,
4423 EVT MemVT, MachinePointerInfo PtrInfo,
4424 unsigned Align, bool Vol,
4425 bool ReadMem, bool WriteMem) {
4426 if (Align == 0) // Ensure that codegen never sees alignment 0
4427 Align = getEVTAlignment(MemVT);
4429 MachineFunction &MF = getMachineFunction();
4432 Flags |= MachineMemOperand::MOStore;
4434 Flags |= MachineMemOperand::MOLoad;
4436 Flags |= MachineMemOperand::MOVolatile;
4437 MachineMemOperand *MMO =
4438 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4440 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4444 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4445 ArrayRef<SDValue> Ops, EVT MemVT,
4446 MachineMemOperand *MMO) {
4447 assert((Opcode == ISD::INTRINSIC_VOID ||
4448 Opcode == ISD::INTRINSIC_W_CHAIN ||
4449 Opcode == ISD::PREFETCH ||
4450 Opcode == ISD::LIFETIME_START ||
4451 Opcode == ISD::LIFETIME_END ||
4452 (Opcode <= INT_MAX &&
4453 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4454 "Opcode is not a memory-accessing opcode!");
4456 // Memoize the node unless it returns a flag.
4457 MemIntrinsicSDNode *N;
4458 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4459 FoldingSetNodeID ID;
4460 AddNodeIDNode(ID, Opcode, VTList, Ops);
4461 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4463 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4464 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4465 return SDValue(E, 0);
4468 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4469 dl.getDebugLoc(), VTList, Ops,
4471 CSEMap.InsertNode(N, IP);
4473 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4474 dl.getDebugLoc(), VTList, Ops,
4477 AllNodes.push_back(N);
4478 return SDValue(N, 0);
4481 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4482 /// MachinePointerInfo record from it. This is particularly useful because the
4483 /// code generator has many cases where it doesn't bother passing in a
4484 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4485 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4486 // If this is FI+Offset, we can model it.
4487 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4488 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4490 // If this is (FI+Offset1)+Offset2, we can model it.
4491 if (Ptr.getOpcode() != ISD::ADD ||
4492 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4493 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4494 return MachinePointerInfo();
4496 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4497 return MachinePointerInfo::getFixedStack(FI, Offset+
4498 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4501 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4502 /// MachinePointerInfo record from it. This is particularly useful because the
4503 /// code generator has many cases where it doesn't bother passing in a
4504 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4505 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4506 // If the 'Offset' value isn't a constant, we can't handle this.
4507 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4508 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4509 if (OffsetOp.getOpcode() == ISD::UNDEF)
4510 return InferPointerInfo(Ptr);
4511 return MachinePointerInfo();
4516 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4517 EVT VT, SDLoc dl, SDValue Chain,
4518 SDValue Ptr, SDValue Offset,
4519 MachinePointerInfo PtrInfo, EVT MemVT,
4520 bool isVolatile, bool isNonTemporal, bool isInvariant,
4521 unsigned Alignment, const MDNode *TBAAInfo,
4522 const MDNode *Ranges) {
4523 assert(Chain.getValueType() == MVT::Other &&
4524 "Invalid chain type");
4525 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4526 Alignment = getEVTAlignment(VT);
4528 unsigned Flags = MachineMemOperand::MOLoad;
4530 Flags |= MachineMemOperand::MOVolatile;
4532 Flags |= MachineMemOperand::MONonTemporal;
4534 Flags |= MachineMemOperand::MOInvariant;
4536 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4538 if (PtrInfo.V.isNull())
4539 PtrInfo = InferPointerInfo(Ptr, Offset);
4541 MachineFunction &MF = getMachineFunction();
4542 MachineMemOperand *MMO =
4543 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4545 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4549 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4550 EVT VT, SDLoc dl, SDValue Chain,
4551 SDValue Ptr, SDValue Offset, EVT MemVT,
4552 MachineMemOperand *MMO) {
4554 ExtType = ISD::NON_EXTLOAD;
4555 } else if (ExtType == ISD::NON_EXTLOAD) {
4556 assert(VT == MemVT && "Non-extending load from different memory type!");
4559 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4560 "Should only be an extending load, not truncating!");
4561 assert(VT.isInteger() == MemVT.isInteger() &&
4562 "Cannot convert from FP to Int or Int -> FP!");
4563 assert(VT.isVector() == MemVT.isVector() &&
4564 "Cannot use trunc store to convert to or from a vector!");
4565 assert((!VT.isVector() ||
4566 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4567 "Cannot use trunc store to change the number of vector elements!");
4570 bool Indexed = AM != ISD::UNINDEXED;
4571 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4572 "Unindexed load with an offset!");
4574 SDVTList VTs = Indexed ?
4575 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4576 SDValue Ops[] = { Chain, Ptr, Offset };
4577 FoldingSetNodeID ID;
4578 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4579 ID.AddInteger(MemVT.getRawBits());
4580 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4581 MMO->isNonTemporal(),
4582 MMO->isInvariant()));
4583 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4585 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4586 cast<LoadSDNode>(E)->refineAlignment(MMO);
4587 return SDValue(E, 0);
4589 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4590 dl.getDebugLoc(), VTs, AM, ExtType,
4592 CSEMap.InsertNode(N, IP);
4593 AllNodes.push_back(N);
4594 return SDValue(N, 0);
4597 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4598 SDValue Chain, SDValue Ptr,
4599 MachinePointerInfo PtrInfo,
4600 bool isVolatile, bool isNonTemporal,
4601 bool isInvariant, unsigned Alignment,
4602 const MDNode *TBAAInfo,
4603 const MDNode *Ranges) {
4604 SDValue Undef = getUNDEF(Ptr.getValueType());
4605 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4606 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4610 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4611 SDValue Chain, SDValue Ptr,
4612 MachineMemOperand *MMO) {
4613 SDValue Undef = getUNDEF(Ptr.getValueType());
4614 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4618 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4619 SDValue Chain, SDValue Ptr,
4620 MachinePointerInfo PtrInfo, EVT MemVT,
4621 bool isVolatile, bool isNonTemporal,
4622 unsigned Alignment, const MDNode *TBAAInfo) {
4623 SDValue Undef = getUNDEF(Ptr.getValueType());
4624 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4625 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4630 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4631 SDValue Chain, SDValue Ptr, EVT MemVT,
4632 MachineMemOperand *MMO) {
4633 SDValue Undef = getUNDEF(Ptr.getValueType());
4634 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4639 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4640 SDValue Offset, ISD::MemIndexedMode AM) {
4641 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4642 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4643 "Load is already a indexed load!");
4644 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4645 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4646 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4647 false, LD->getAlignment());
4650 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4651 SDValue Ptr, MachinePointerInfo PtrInfo,
4652 bool isVolatile, bool isNonTemporal,
4653 unsigned Alignment, const MDNode *TBAAInfo) {
4654 assert(Chain.getValueType() == MVT::Other &&
4655 "Invalid chain type");
4656 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4657 Alignment = getEVTAlignment(Val.getValueType());
4659 unsigned Flags = MachineMemOperand::MOStore;
4661 Flags |= MachineMemOperand::MOVolatile;
4663 Flags |= MachineMemOperand::MONonTemporal;
4665 if (PtrInfo.V.isNull())
4666 PtrInfo = InferPointerInfo(Ptr);
4668 MachineFunction &MF = getMachineFunction();
4669 MachineMemOperand *MMO =
4670 MF.getMachineMemOperand(PtrInfo, Flags,
4671 Val.getValueType().getStoreSize(), Alignment,
4674 return getStore(Chain, dl, Val, Ptr, MMO);
4677 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4678 SDValue Ptr, MachineMemOperand *MMO) {
4679 assert(Chain.getValueType() == MVT::Other &&
4680 "Invalid chain type");
4681 EVT VT = Val.getValueType();
4682 SDVTList VTs = getVTList(MVT::Other);
4683 SDValue Undef = getUNDEF(Ptr.getValueType());
4684 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4685 FoldingSetNodeID ID;
4686 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4687 ID.AddInteger(VT.getRawBits());
4688 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4689 MMO->isNonTemporal(), MMO->isInvariant()));
4690 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4692 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4693 cast<StoreSDNode>(E)->refineAlignment(MMO);
4694 return SDValue(E, 0);
4696 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4697 dl.getDebugLoc(), VTs,
4698 ISD::UNINDEXED, false, VT, MMO);
4699 CSEMap.InsertNode(N, IP);
4700 AllNodes.push_back(N);
4701 return SDValue(N, 0);
4704 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4705 SDValue Ptr, MachinePointerInfo PtrInfo,
4706 EVT SVT,bool isVolatile, bool isNonTemporal,
4708 const MDNode *TBAAInfo) {
4709 assert(Chain.getValueType() == MVT::Other &&
4710 "Invalid chain type");
4711 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4712 Alignment = getEVTAlignment(SVT);
4714 unsigned Flags = MachineMemOperand::MOStore;
4716 Flags |= MachineMemOperand::MOVolatile;
4718 Flags |= MachineMemOperand::MONonTemporal;
4720 if (PtrInfo.V.isNull())
4721 PtrInfo = InferPointerInfo(Ptr);
4723 MachineFunction &MF = getMachineFunction();
4724 MachineMemOperand *MMO =
4725 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4728 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4731 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4732 SDValue Ptr, EVT SVT,
4733 MachineMemOperand *MMO) {
4734 EVT VT = Val.getValueType();
4736 assert(Chain.getValueType() == MVT::Other &&
4737 "Invalid chain type");
4739 return getStore(Chain, dl, Val, Ptr, MMO);
4741 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4742 "Should only be a truncating store, not extending!");
4743 assert(VT.isInteger() == SVT.isInteger() &&
4744 "Can't do FP-INT conversion!");
4745 assert(VT.isVector() == SVT.isVector() &&
4746 "Cannot use trunc store to convert to or from a vector!");
4747 assert((!VT.isVector() ||
4748 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4749 "Cannot use trunc store to change the number of vector elements!");
4751 SDVTList VTs = getVTList(MVT::Other);
4752 SDValue Undef = getUNDEF(Ptr.getValueType());
4753 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4754 FoldingSetNodeID ID;
4755 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4756 ID.AddInteger(SVT.getRawBits());
4757 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4758 MMO->isNonTemporal(), MMO->isInvariant()));
4759 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4761 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4762 cast<StoreSDNode>(E)->refineAlignment(MMO);
4763 return SDValue(E, 0);
4765 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4766 dl.getDebugLoc(), VTs,
4767 ISD::UNINDEXED, true, SVT, MMO);
4768 CSEMap.InsertNode(N, IP);
4769 AllNodes.push_back(N);
4770 return SDValue(N, 0);
4774 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4775 SDValue Offset, ISD::MemIndexedMode AM) {
4776 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4777 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4778 "Store is already a indexed store!");
4779 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4780 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4781 FoldingSetNodeID ID;
4782 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4783 ID.AddInteger(ST->getMemoryVT().getRawBits());
4784 ID.AddInteger(ST->getRawSubclassData());
4785 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4787 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4788 return SDValue(E, 0);
4790 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4791 dl.getDebugLoc(), VTs, AM,
4792 ST->isTruncatingStore(),
4794 ST->getMemOperand());
4795 CSEMap.InsertNode(N, IP);
4796 AllNodes.push_back(N);
4797 return SDValue(N, 0);
4800 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4801 SDValue Chain, SDValue Ptr,
4804 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4805 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4808 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4809 ArrayRef<SDUse> Ops) {
4810 switch (Ops.size()) {
4811 case 0: return getNode(Opcode, DL, VT);
4812 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4813 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4814 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4818 // Copy from an SDUse array into an SDValue array for use with
4819 // the regular getNode logic.
4820 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4821 return getNode(Opcode, DL, VT, NewOps);
4824 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4825 ArrayRef<SDValue> Ops) {
4826 unsigned NumOps = Ops.size();
4828 case 0: return getNode(Opcode, DL, VT);
4829 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4830 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4831 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4837 case ISD::SELECT_CC: {
4838 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4839 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4840 "LHS and RHS of condition must have same type!");
4841 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4842 "True and False arms of SelectCC must have same type!");
4843 assert(Ops[2].getValueType() == VT &&
4844 "select_cc node must be of same type as true and false value!");
4848 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4849 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4850 "LHS/RHS of comparison should match types!");
4857 SDVTList VTs = getVTList(VT);
4859 if (VT != MVT::Glue) {
4860 FoldingSetNodeID ID;
4861 AddNodeIDNode(ID, Opcode, VTs, Ops);
4864 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4865 return SDValue(E, 0);
4867 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4869 CSEMap.InsertNode(N, IP);
4871 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4875 AllNodes.push_back(N);
4879 return SDValue(N, 0);
4882 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4883 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4884 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4887 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4888 ArrayRef<SDValue> Ops) {
4889 if (VTList.NumVTs == 1)
4890 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4894 // FIXME: figure out how to safely handle things like
4895 // int foo(int x) { return 1 << (x & 255); }
4896 // int bar() { return foo(256); }
4897 case ISD::SRA_PARTS:
4898 case ISD::SRL_PARTS:
4899 case ISD::SHL_PARTS:
4900 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4901 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4902 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4903 else if (N3.getOpcode() == ISD::AND)
4904 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4905 // If the and is only masking out bits that cannot effect the shift,
4906 // eliminate the and.
4907 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4908 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4909 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4915 // Memoize the node unless it returns a flag.
4917 unsigned NumOps = Ops.size();
4918 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4919 FoldingSetNodeID ID;
4920 AddNodeIDNode(ID, Opcode, VTList, Ops);
4922 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4923 return SDValue(E, 0);
4926 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4927 DL.getDebugLoc(), VTList, Ops[0]);
4928 } else if (NumOps == 2) {
4929 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4930 DL.getDebugLoc(), VTList, Ops[0],
4932 } else if (NumOps == 3) {
4933 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4934 DL.getDebugLoc(), VTList, Ops[0],
4937 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4940 CSEMap.InsertNode(N, IP);
4943 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4944 DL.getDebugLoc(), VTList, Ops[0]);
4945 } else if (NumOps == 2) {
4946 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4947 DL.getDebugLoc(), VTList, Ops[0],
4949 } else if (NumOps == 3) {
4950 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4951 DL.getDebugLoc(), VTList, Ops[0],
4954 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4958 AllNodes.push_back(N);
4962 return SDValue(N, 0);
4965 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4966 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4969 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4971 SDValue Ops[] = { N1 };
4972 return getNode(Opcode, DL, VTList, Ops);
4975 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4976 SDValue N1, SDValue N2) {
4977 SDValue Ops[] = { N1, N2 };
4978 return getNode(Opcode, DL, VTList, Ops);
4981 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4982 SDValue N1, SDValue N2, SDValue N3) {
4983 SDValue Ops[] = { N1, N2, N3 };
4984 return getNode(Opcode, DL, VTList, Ops);
4987 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4988 SDValue N1, SDValue N2, SDValue N3,
4990 SDValue Ops[] = { N1, N2, N3, N4 };
4991 return getNode(Opcode, DL, VTList, Ops);
4994 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4995 SDValue N1, SDValue N2, SDValue N3,
4996 SDValue N4, SDValue N5) {
4997 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4998 return getNode(Opcode, DL, VTList, Ops);
5001 SDVTList SelectionDAG::getVTList(EVT VT) {
5002 return makeVTList(SDNode::getValueTypeList(VT), 1);
5005 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
5006 FoldingSetNodeID ID;
5008 ID.AddInteger(VT1.getRawBits());
5009 ID.AddInteger(VT2.getRawBits());
5012 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5014 EVT *Array = Allocator.Allocate<EVT>(2);
5017 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5018 VTListMap.InsertNode(Result, IP);
5020 return Result->getSDVTList();
5023 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5024 FoldingSetNodeID ID;
5026 ID.AddInteger(VT1.getRawBits());
5027 ID.AddInteger(VT2.getRawBits());
5028 ID.AddInteger(VT3.getRawBits());
5031 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5033 EVT *Array = Allocator.Allocate<EVT>(3);
5037 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5038 VTListMap.InsertNode(Result, IP);
5040 return Result->getSDVTList();
5043 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5044 FoldingSetNodeID ID;
5046 ID.AddInteger(VT1.getRawBits());
5047 ID.AddInteger(VT2.getRawBits());
5048 ID.AddInteger(VT3.getRawBits());
5049 ID.AddInteger(VT4.getRawBits());
5052 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5054 EVT *Array = Allocator.Allocate<EVT>(4);
5059 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5060 VTListMap.InsertNode(Result, IP);
5062 return Result->getSDVTList();
5065 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5066 unsigned NumVTs = VTs.size();
5067 FoldingSetNodeID ID;
5068 ID.AddInteger(NumVTs);
5069 for (unsigned index = 0; index < NumVTs; index++) {
5070 ID.AddInteger(VTs[index].getRawBits());
5074 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5076 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5077 std::copy(VTs.begin(), VTs.end(), Array);
5078 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5079 VTListMap.InsertNode(Result, IP);
5081 return Result->getSDVTList();
5085 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5086 /// specified operands. If the resultant node already exists in the DAG,
5087 /// this does not modify the specified node, instead it returns the node that
5088 /// already exists. If the resultant node does not exist in the DAG, the
5089 /// input node is returned. As a degenerate case, if you specify the same
5090 /// input operands as the node already has, the input node is returned.
5091 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5092 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5094 // Check to see if there is no change.
5095 if (Op == N->getOperand(0)) return N;
5097 // See if the modified node already exists.
5098 void *InsertPos = nullptr;
5099 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5102 // Nope it doesn't. Remove the node from its current place in the maps.
5104 if (!RemoveNodeFromCSEMaps(N))
5105 InsertPos = nullptr;
5107 // Now we update the operands.
5108 N->OperandList[0].set(Op);
5110 // If this gets put into a CSE map, add it.
5111 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5115 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5116 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5118 // Check to see if there is no change.
5119 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5120 return N; // No operands changed, just return the input node.
5122 // See if the modified node already exists.
5123 void *InsertPos = nullptr;
5124 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5127 // Nope it doesn't. Remove the node from its current place in the maps.
5129 if (!RemoveNodeFromCSEMaps(N))
5130 InsertPos = nullptr;
5132 // Now we update the operands.
5133 if (N->OperandList[0] != Op1)
5134 N->OperandList[0].set(Op1);
5135 if (N->OperandList[1] != Op2)
5136 N->OperandList[1].set(Op2);
5138 // If this gets put into a CSE map, add it.
5139 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5143 SDNode *SelectionDAG::
5144 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5145 SDValue Ops[] = { Op1, Op2, Op3 };
5146 return UpdateNodeOperands(N, Ops);
5149 SDNode *SelectionDAG::
5150 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5151 SDValue Op3, SDValue Op4) {
5152 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5153 return UpdateNodeOperands(N, Ops);
5156 SDNode *SelectionDAG::
5157 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5158 SDValue Op3, SDValue Op4, SDValue Op5) {
5159 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5160 return UpdateNodeOperands(N, Ops);
5163 SDNode *SelectionDAG::
5164 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5165 unsigned NumOps = Ops.size();
5166 assert(N->getNumOperands() == NumOps &&
5167 "Update with wrong number of operands");
5169 // Check to see if there is no change.
5170 bool AnyChange = false;
5171 for (unsigned i = 0; i != NumOps; ++i) {
5172 if (Ops[i] != N->getOperand(i)) {
5178 // No operands changed, just return the input node.
5179 if (!AnyChange) return N;
5181 // See if the modified node already exists.
5182 void *InsertPos = nullptr;
5183 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5186 // Nope it doesn't. Remove the node from its current place in the maps.
5188 if (!RemoveNodeFromCSEMaps(N))
5189 InsertPos = nullptr;
5191 // Now we update the operands.
5192 for (unsigned i = 0; i != NumOps; ++i)
5193 if (N->OperandList[i] != Ops[i])
5194 N->OperandList[i].set(Ops[i]);
5196 // If this gets put into a CSE map, add it.
5197 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5201 /// DropOperands - Release the operands and set this node to have
5203 void SDNode::DropOperands() {
5204 // Unlike the code in MorphNodeTo that does this, we don't need to
5205 // watch for dead nodes here.
5206 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5212 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5215 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5217 SDVTList VTs = getVTList(VT);
5218 return SelectNodeTo(N, MachineOpc, VTs, None);
5221 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5222 EVT VT, SDValue Op1) {
5223 SDVTList VTs = getVTList(VT);
5224 SDValue Ops[] = { Op1 };
5225 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5228 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5229 EVT VT, SDValue Op1,
5231 SDVTList VTs = getVTList(VT);
5232 SDValue Ops[] = { Op1, Op2 };
5233 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5236 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5237 EVT VT, SDValue Op1,
5238 SDValue Op2, SDValue Op3) {
5239 SDVTList VTs = getVTList(VT);
5240 SDValue Ops[] = { Op1, Op2, Op3 };
5241 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5244 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5245 EVT VT, ArrayRef<SDValue> Ops) {
5246 SDVTList VTs = getVTList(VT);
5247 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5250 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5251 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5252 SDVTList VTs = getVTList(VT1, VT2);
5253 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5256 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5258 SDVTList VTs = getVTList(VT1, VT2);
5259 return SelectNodeTo(N, MachineOpc, VTs, None);
5262 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5263 EVT VT1, EVT VT2, EVT VT3,
5264 ArrayRef<SDValue> Ops) {
5265 SDVTList VTs = getVTList(VT1, VT2, VT3);
5266 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5271 ArrayRef<SDValue> Ops) {
5272 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5273 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5276 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5279 SDVTList VTs = getVTList(VT1, VT2);
5280 SDValue Ops[] = { Op1 };
5281 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5284 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5286 SDValue Op1, SDValue Op2) {
5287 SDVTList VTs = getVTList(VT1, VT2);
5288 SDValue Ops[] = { Op1, Op2 };
5289 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5294 SDValue Op1, SDValue Op2,
5296 SDVTList VTs = getVTList(VT1, VT2);
5297 SDValue Ops[] = { Op1, Op2, Op3 };
5298 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5301 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 EVT VT1, EVT VT2, EVT VT3,
5303 SDValue Op1, SDValue Op2,
5305 SDVTList VTs = getVTList(VT1, VT2, VT3);
5306 SDValue Ops[] = { Op1, Op2, Op3 };
5307 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5310 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5311 SDVTList VTs,ArrayRef<SDValue> Ops) {
5312 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5313 // Reset the NodeID to -1.
5318 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5319 /// the line number information on the merged node since it is not possible to
5320 /// preserve the information that operation is associated with multiple lines.
5321 /// This will make the debugger working better at -O0, were there is a higher
5322 /// probability having other instructions associated with that line.
5324 /// For IROrder, we keep the smaller of the two
5325 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5326 DebugLoc NLoc = N->getDebugLoc();
5327 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5328 (OLoc.getDebugLoc() != NLoc)) {
5329 N->setDebugLoc(DebugLoc());
5331 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5332 N->setIROrder(Order);
5336 /// MorphNodeTo - This *mutates* the specified node to have the specified
5337 /// return type, opcode, and operands.
5339 /// Note that MorphNodeTo returns the resultant node. If there is already a
5340 /// node of the specified opcode and operands, it returns that node instead of
5341 /// the current one. Note that the SDLoc need not be the same.
5343 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5344 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5345 /// node, and because it doesn't require CSE recalculation for any of
5346 /// the node's users.
5348 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5349 SDVTList VTs, ArrayRef<SDValue> Ops) {
5350 unsigned NumOps = Ops.size();
5351 // If an identical node already exists, use it.
5353 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5354 FoldingSetNodeID ID;
5355 AddNodeIDNode(ID, Opc, VTs, Ops);
5356 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5357 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5360 if (!RemoveNodeFromCSEMaps(N))
5363 // Start the morphing.
5365 N->ValueList = VTs.VTs;
5366 N->NumValues = VTs.NumVTs;
5368 // Clear the operands list, updating used nodes to remove this from their
5369 // use list. Keep track of any operands that become dead as a result.
5370 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5371 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5373 SDNode *Used = Use.getNode();
5375 if (Used->use_empty())
5376 DeadNodeSet.insert(Used);
5379 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5380 // Initialize the memory references information.
5381 MN->setMemRefs(nullptr, nullptr);
5382 // If NumOps is larger than the # of operands we can have in a
5383 // MachineSDNode, reallocate the operand list.
5384 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5385 if (MN->OperandsNeedDelete)
5386 delete[] MN->OperandList;
5387 if (NumOps > array_lengthof(MN->LocalOperands))
5388 // We're creating a final node that will live unmorphed for the
5389 // remainder of the current SelectionDAG iteration, so we can allocate
5390 // the operands directly out of a pool with no recycling metadata.
5391 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5392 Ops.data(), NumOps);
5394 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5395 MN->OperandsNeedDelete = false;
5397 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5399 // If NumOps is larger than the # of operands we currently have, reallocate
5400 // the operand list.
5401 if (NumOps > N->NumOperands) {
5402 if (N->OperandsNeedDelete)
5403 delete[] N->OperandList;
5404 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5405 N->OperandsNeedDelete = true;
5407 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5410 // Delete any nodes that are still dead after adding the uses for the
5412 if (!DeadNodeSet.empty()) {
5413 SmallVector<SDNode *, 16> DeadNodes;
5414 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5415 E = DeadNodeSet.end(); I != E; ++I)
5416 if ((*I)->use_empty())
5417 DeadNodes.push_back(*I);
5418 RemoveDeadNodes(DeadNodes);
5422 CSEMap.InsertNode(N, IP); // Memoize the new node.
5427 /// getMachineNode - These are used for target selectors to create a new node
5428 /// with specified return type(s), MachineInstr opcode, and operands.
5430 /// Note that getMachineNode returns the resultant node. If there is already a
5431 /// node of the specified opcode and operands, it returns that node instead of
5432 /// the current one.
5434 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5435 SDVTList VTs = getVTList(VT);
5436 return getMachineNode(Opcode, dl, VTs, None);
5440 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5441 SDVTList VTs = getVTList(VT);
5442 SDValue Ops[] = { Op1 };
5443 return getMachineNode(Opcode, dl, VTs, Ops);
5447 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5448 SDValue Op1, SDValue Op2) {
5449 SDVTList VTs = getVTList(VT);
5450 SDValue Ops[] = { Op1, Op2 };
5451 return getMachineNode(Opcode, dl, VTs, Ops);
5455 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5456 SDValue Op1, SDValue Op2, SDValue Op3) {
5457 SDVTList VTs = getVTList(VT);
5458 SDValue Ops[] = { Op1, Op2, Op3 };
5459 return getMachineNode(Opcode, dl, VTs, Ops);
5463 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5464 ArrayRef<SDValue> Ops) {
5465 SDVTList VTs = getVTList(VT);
5466 return getMachineNode(Opcode, dl, VTs, Ops);
5470 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5471 SDVTList VTs = getVTList(VT1, VT2);
5472 return getMachineNode(Opcode, dl, VTs, None);
5476 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5477 EVT VT1, EVT VT2, SDValue Op1) {
5478 SDVTList VTs = getVTList(VT1, VT2);
5479 SDValue Ops[] = { Op1 };
5480 return getMachineNode(Opcode, dl, VTs, Ops);
5484 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5485 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5486 SDVTList VTs = getVTList(VT1, VT2);
5487 SDValue Ops[] = { Op1, Op2 };
5488 return getMachineNode(Opcode, dl, VTs, Ops);
5492 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5493 EVT VT1, EVT VT2, SDValue Op1,
5494 SDValue Op2, SDValue Op3) {
5495 SDVTList VTs = getVTList(VT1, VT2);
5496 SDValue Ops[] = { Op1, Op2, Op3 };
5497 return getMachineNode(Opcode, dl, VTs, Ops);
5501 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5503 ArrayRef<SDValue> Ops) {
5504 SDVTList VTs = getVTList(VT1, VT2);
5505 return getMachineNode(Opcode, dl, VTs, Ops);
5509 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5510 EVT VT1, EVT VT2, EVT VT3,
5511 SDValue Op1, SDValue Op2) {
5512 SDVTList VTs = getVTList(VT1, VT2, VT3);
5513 SDValue Ops[] = { Op1, Op2 };
5514 return getMachineNode(Opcode, dl, VTs, Ops);
5518 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5519 EVT VT1, EVT VT2, EVT VT3,
5520 SDValue Op1, SDValue Op2, SDValue Op3) {
5521 SDVTList VTs = getVTList(VT1, VT2, VT3);
5522 SDValue Ops[] = { Op1, Op2, Op3 };
5523 return getMachineNode(Opcode, dl, VTs, Ops);
5527 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5528 EVT VT1, EVT VT2, EVT VT3,
5529 ArrayRef<SDValue> Ops) {
5530 SDVTList VTs = getVTList(VT1, VT2, VT3);
5531 return getMachineNode(Opcode, dl, VTs, Ops);
5535 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5536 EVT VT2, EVT VT3, EVT VT4,
5537 ArrayRef<SDValue> Ops) {
5538 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5539 return getMachineNode(Opcode, dl, VTs, Ops);
5543 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5544 ArrayRef<EVT> ResultTys,
5545 ArrayRef<SDValue> Ops) {
5546 SDVTList VTs = getVTList(ResultTys);
5547 return getMachineNode(Opcode, dl, VTs, Ops);
5551 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5552 ArrayRef<SDValue> OpsArray) {
5553 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5556 const SDValue *Ops = OpsArray.data();
5557 unsigned NumOps = OpsArray.size();
5560 FoldingSetNodeID ID;
5561 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5563 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5564 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5568 // Allocate a new MachineSDNode.
5569 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5570 DL.getDebugLoc(), VTs);
5572 // Initialize the operands list.
5573 if (NumOps > array_lengthof(N->LocalOperands))
5574 // We're creating a final node that will live unmorphed for the
5575 // remainder of the current SelectionDAG iteration, so we can allocate
5576 // the operands directly out of a pool with no recycling metadata.
5577 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5580 N->InitOperands(N->LocalOperands, Ops, NumOps);
5581 N->OperandsNeedDelete = false;
5584 CSEMap.InsertNode(N, IP);
5586 AllNodes.push_back(N);
5588 VerifyMachineNode(N);
5593 /// getTargetExtractSubreg - A convenience function for creating
5594 /// TargetOpcode::EXTRACT_SUBREG nodes.
5596 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5598 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5599 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5600 VT, Operand, SRIdxVal);
5601 return SDValue(Subreg, 0);
5604 /// getTargetInsertSubreg - A convenience function for creating
5605 /// TargetOpcode::INSERT_SUBREG nodes.
5607 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5608 SDValue Operand, SDValue Subreg) {
5609 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5610 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5611 VT, Operand, Subreg, SRIdxVal);
5612 return SDValue(Result, 0);
5615 /// getNodeIfExists - Get the specified node if it's already available, or
5616 /// else return NULL.
5617 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5618 ArrayRef<SDValue> Ops) {
5619 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5620 FoldingSetNodeID ID;
5621 AddNodeIDNode(ID, Opcode, VTList, Ops);
5623 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5629 /// getDbgValue - Creates a SDDbgValue node.
5633 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5634 bool IsIndirect, uint64_t Off,
5635 DebugLoc DL, unsigned O) {
5636 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5641 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5643 DebugLoc DL, unsigned O) {
5644 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5649 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5650 DebugLoc DL, unsigned O) {
5651 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5656 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5657 /// pointed to by a use iterator is deleted, increment the use iterator
5658 /// so that it doesn't dangle.
5660 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5661 SDNode::use_iterator &UI;
5662 SDNode::use_iterator &UE;
5664 void NodeDeleted(SDNode *N, SDNode *E) override {
5665 // Increment the iterator as needed.
5666 while (UI != UE && N == *UI)
5671 RAUWUpdateListener(SelectionDAG &d,
5672 SDNode::use_iterator &ui,
5673 SDNode::use_iterator &ue)
5674 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5679 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5680 /// This can cause recursive merging of nodes in the DAG.
5682 /// This version assumes From has a single result value.
5684 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5685 SDNode *From = FromN.getNode();
5686 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5687 "Cannot replace with this method!");
5688 assert(From != To.getNode() && "Cannot replace uses of with self");
5690 // Iterate over all the existing uses of From. New uses will be added
5691 // to the beginning of the use list, which we avoid visiting.
5692 // This specifically avoids visiting uses of From that arise while the
5693 // replacement is happening, because any such uses would be the result
5694 // of CSE: If an existing node looks like From after one of its operands
5695 // is replaced by To, we don't want to replace of all its users with To
5696 // too. See PR3018 for more info.
5697 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5698 RAUWUpdateListener Listener(*this, UI, UE);
5702 // This node is about to morph, remove its old self from the CSE maps.
5703 RemoveNodeFromCSEMaps(User);
5705 // A user can appear in a use list multiple times, and when this
5706 // happens the uses are usually next to each other in the list.
5707 // To help reduce the number of CSE recomputations, process all
5708 // the uses of this user that we can find this way.
5710 SDUse &Use = UI.getUse();
5713 } while (UI != UE && *UI == User);
5715 // Now that we have modified User, add it back to the CSE maps. If it
5716 // already exists there, recursively merge the results together.
5717 AddModifiedNodeToCSEMaps(User);
5720 // If we just RAUW'd the root, take note.
5721 if (FromN == getRoot())
5725 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5726 /// This can cause recursive merging of nodes in the DAG.
5728 /// This version assumes that for each value of From, there is a
5729 /// corresponding value in To in the same position with the same type.
5731 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5733 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5734 assert((!From->hasAnyUseOfValue(i) ||
5735 From->getValueType(i) == To->getValueType(i)) &&
5736 "Cannot use this version of ReplaceAllUsesWith!");
5739 // Handle the trivial case.
5743 // Iterate over just the existing users of From. See the comments in
5744 // the ReplaceAllUsesWith above.
5745 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5746 RAUWUpdateListener Listener(*this, UI, UE);
5750 // This node is about to morph, remove its old self from the CSE maps.
5751 RemoveNodeFromCSEMaps(User);
5753 // A user can appear in a use list multiple times, and when this
5754 // happens the uses are usually next to each other in the list.
5755 // To help reduce the number of CSE recomputations, process all
5756 // the uses of this user that we can find this way.
5758 SDUse &Use = UI.getUse();
5761 } while (UI != UE && *UI == User);
5763 // Now that we have modified User, add it back to the CSE maps. If it
5764 // already exists there, recursively merge the results together.
5765 AddModifiedNodeToCSEMaps(User);
5768 // If we just RAUW'd the root, take note.
5769 if (From == getRoot().getNode())
5770 setRoot(SDValue(To, getRoot().getResNo()));
5773 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5774 /// This can cause recursive merging of nodes in the DAG.
5776 /// This version can replace From with any result values. To must match the
5777 /// number and types of values returned by From.
5778 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5779 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5780 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5782 // Iterate over just the existing users of From. See the comments in
5783 // the ReplaceAllUsesWith above.
5784 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5785 RAUWUpdateListener Listener(*this, UI, UE);
5789 // This node is about to morph, remove its old self from the CSE maps.
5790 RemoveNodeFromCSEMaps(User);
5792 // A user can appear in a use list multiple times, and when this
5793 // happens the uses are usually next to each other in the list.
5794 // To help reduce the number of CSE recomputations, process all
5795 // the uses of this user that we can find this way.
5797 SDUse &Use = UI.getUse();
5798 const SDValue &ToOp = To[Use.getResNo()];
5801 } while (UI != UE && *UI == User);
5803 // Now that we have modified User, add it back to the CSE maps. If it
5804 // already exists there, recursively merge the results together.
5805 AddModifiedNodeToCSEMaps(User);
5808 // If we just RAUW'd the root, take note.
5809 if (From == getRoot().getNode())
5810 setRoot(SDValue(To[getRoot().getResNo()]));
5813 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5814 /// uses of other values produced by From.getNode() alone. The Deleted
5815 /// vector is handled the same way as for ReplaceAllUsesWith.
5816 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5817 // Handle the really simple, really trivial case efficiently.
5818 if (From == To) return;
5820 // Handle the simple, trivial, case efficiently.
5821 if (From.getNode()->getNumValues() == 1) {
5822 ReplaceAllUsesWith(From, To);
5826 // Iterate over just the existing users of From. See the comments in
5827 // the ReplaceAllUsesWith above.
5828 SDNode::use_iterator UI = From.getNode()->use_begin(),
5829 UE = From.getNode()->use_end();
5830 RAUWUpdateListener Listener(*this, UI, UE);
5833 bool UserRemovedFromCSEMaps = false;
5835 // A user can appear in a use list multiple times, and when this
5836 // happens the uses are usually next to each other in the list.
5837 // To help reduce the number of CSE recomputations, process all
5838 // the uses of this user that we can find this way.
5840 SDUse &Use = UI.getUse();
5842 // Skip uses of different values from the same node.
5843 if (Use.getResNo() != From.getResNo()) {
5848 // If this node hasn't been modified yet, it's still in the CSE maps,
5849 // so remove its old self from the CSE maps.
5850 if (!UserRemovedFromCSEMaps) {
5851 RemoveNodeFromCSEMaps(User);
5852 UserRemovedFromCSEMaps = true;
5857 } while (UI != UE && *UI == User);
5859 // We are iterating over all uses of the From node, so if a use
5860 // doesn't use the specific value, no changes are made.
5861 if (!UserRemovedFromCSEMaps)
5864 // Now that we have modified User, add it back to the CSE maps. If it
5865 // already exists there, recursively merge the results together.
5866 AddModifiedNodeToCSEMaps(User);
5869 // If we just RAUW'd the root, take note.
5870 if (From == getRoot())
5875 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5876 /// to record information about a use.
5883 /// operator< - Sort Memos by User.
5884 bool operator<(const UseMemo &L, const UseMemo &R) {
5885 return (intptr_t)L.User < (intptr_t)R.User;
5889 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5890 /// uses of other values produced by From.getNode() alone. The same value
5891 /// may appear in both the From and To list. The Deleted vector is
5892 /// handled the same way as for ReplaceAllUsesWith.
5893 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5896 // Handle the simple, trivial case efficiently.
5898 return ReplaceAllUsesOfValueWith(*From, *To);
5900 // Read up all the uses and make records of them. This helps
5901 // processing new uses that are introduced during the
5902 // replacement process.
5903 SmallVector<UseMemo, 4> Uses;
5904 for (unsigned i = 0; i != Num; ++i) {
5905 unsigned FromResNo = From[i].getResNo();
5906 SDNode *FromNode = From[i].getNode();
5907 for (SDNode::use_iterator UI = FromNode->use_begin(),
5908 E = FromNode->use_end(); UI != E; ++UI) {
5909 SDUse &Use = UI.getUse();
5910 if (Use.getResNo() == FromResNo) {
5911 UseMemo Memo = { *UI, i, &Use };
5912 Uses.push_back(Memo);
5917 // Sort the uses, so that all the uses from a given User are together.
5918 std::sort(Uses.begin(), Uses.end());
5920 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5921 UseIndex != UseIndexEnd; ) {
5922 // We know that this user uses some value of From. If it is the right
5923 // value, update it.
5924 SDNode *User = Uses[UseIndex].User;
5926 // This node is about to morph, remove its old self from the CSE maps.
5927 RemoveNodeFromCSEMaps(User);
5929 // The Uses array is sorted, so all the uses for a given User
5930 // are next to each other in the list.
5931 // To help reduce the number of CSE recomputations, process all
5932 // the uses of this user that we can find this way.
5934 unsigned i = Uses[UseIndex].Index;
5935 SDUse &Use = *Uses[UseIndex].Use;
5939 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5941 // Now that we have modified User, add it back to the CSE maps. If it
5942 // already exists there, recursively merge the results together.
5943 AddModifiedNodeToCSEMaps(User);
5947 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5948 /// based on their topological order. It returns the maximum id and a vector
5949 /// of the SDNodes* in assigned order by reference.
5950 unsigned SelectionDAG::AssignTopologicalOrder() {
5952 unsigned DAGSize = 0;
5954 // SortedPos tracks the progress of the algorithm. Nodes before it are
5955 // sorted, nodes after it are unsorted. When the algorithm completes
5956 // it is at the end of the list.
5957 allnodes_iterator SortedPos = allnodes_begin();
5959 // Visit all the nodes. Move nodes with no operands to the front of
5960 // the list immediately. Annotate nodes that do have operands with their
5961 // operand count. Before we do this, the Node Id fields of the nodes
5962 // may contain arbitrary values. After, the Node Id fields for nodes
5963 // before SortedPos will contain the topological sort index, and the
5964 // Node Id fields for nodes At SortedPos and after will contain the
5965 // count of outstanding operands.
5966 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5969 unsigned Degree = N->getNumOperands();
5971 // A node with no uses, add it to the result array immediately.
5972 N->setNodeId(DAGSize++);
5973 allnodes_iterator Q = N;
5975 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5976 assert(SortedPos != AllNodes.end() && "Overran node list");
5979 // Temporarily use the Node Id as scratch space for the degree count.
5980 N->setNodeId(Degree);
5984 // Visit all the nodes. As we iterate, move nodes into sorted order,
5985 // such that by the time the end is reached all nodes will be sorted.
5986 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5989 // N is in sorted position, so all its uses have one less operand
5990 // that needs to be sorted.
5991 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5994 unsigned Degree = P->getNodeId();
5995 assert(Degree != 0 && "Invalid node degree");
5998 // All of P's operands are sorted, so P may sorted now.
5999 P->setNodeId(DAGSize++);
6001 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
6002 assert(SortedPos != AllNodes.end() && "Overran node list");
6005 // Update P's outstanding operand count.
6006 P->setNodeId(Degree);
6009 if (I == SortedPos) {
6012 dbgs() << "Overran sorted position:\n";
6015 llvm_unreachable(nullptr);
6019 assert(SortedPos == AllNodes.end() &&
6020 "Topological sort incomplete!");
6021 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6022 "First node in topological sort is not the entry token!");
6023 assert(AllNodes.front().getNodeId() == 0 &&
6024 "First node in topological sort has non-zero id!");
6025 assert(AllNodes.front().getNumOperands() == 0 &&
6026 "First node in topological sort has operands!");
6027 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6028 "Last node in topologic sort has unexpected id!");
6029 assert(AllNodes.back().use_empty() &&
6030 "Last node in topologic sort has users!");
6031 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6035 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6036 /// value is produced by SD.
6037 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6038 DbgInfo->add(DB, SD, isParameter);
6040 SD->setHasDebugValue(true);
6043 /// TransferDbgValues - Transfer SDDbgValues.
6044 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6045 if (From == To || !From.getNode()->getHasDebugValue())
6047 SDNode *FromNode = From.getNode();
6048 SDNode *ToNode = To.getNode();
6049 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6050 SmallVector<SDDbgValue *, 2> ClonedDVs;
6051 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6053 SDDbgValue *Dbg = *I;
6054 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6055 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6057 Dbg->getOffset(), Dbg->getDebugLoc(),
6059 ClonedDVs.push_back(Clone);
6062 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6063 E = ClonedDVs.end(); I != E; ++I)
6064 AddDbgValue(*I, ToNode, false);
6067 //===----------------------------------------------------------------------===//
6069 //===----------------------------------------------------------------------===//
6071 HandleSDNode::~HandleSDNode() {
6075 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6076 DebugLoc DL, const GlobalValue *GA,
6077 EVT VT, int64_t o, unsigned char TF)
6078 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6082 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6083 SDValue X, unsigned SrcAS,
6085 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6086 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6088 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6089 EVT memvt, MachineMemOperand *mmo)
6090 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6091 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6092 MMO->isNonTemporal(), MMO->isInvariant());
6093 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6094 assert(isNonTemporal() == MMO->isNonTemporal() &&
6095 "Non-temporal encoding error!");
6096 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6099 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6100 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6101 : SDNode(Opc, Order, dl, VTs, Ops),
6102 MemoryVT(memvt), MMO(mmo) {
6103 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6104 MMO->isNonTemporal(), MMO->isInvariant());
6105 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6106 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6109 /// Profile - Gather unique data for the node.
6111 void SDNode::Profile(FoldingSetNodeID &ID) const {
6112 AddNodeIDNode(ID, this);
6117 std::vector<EVT> VTs;
6120 VTs.reserve(MVT::LAST_VALUETYPE);
6121 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6122 VTs.push_back(MVT((MVT::SimpleValueType)i));
6127 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6128 static ManagedStatic<EVTArray> SimpleVTArray;
6129 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6131 /// getValueTypeList - Return a pointer to the specified value type.
6133 const EVT *SDNode::getValueTypeList(EVT VT) {
6134 if (VT.isExtended()) {
6135 sys::SmartScopedLock<true> Lock(*VTMutex);
6136 return &(*EVTs->insert(VT).first);
6138 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6139 "Value type out of range!");
6140 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6144 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6145 /// indicated value. This method ignores uses of other values defined by this
6147 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6148 assert(Value < getNumValues() && "Bad value!");
6150 // TODO: Only iterate over uses of a given value of the node
6151 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6152 if (UI.getUse().getResNo() == Value) {
6159 // Found exactly the right number of uses?
6164 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6165 /// value. This method ignores uses of other values defined by this operation.
6166 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6167 assert(Value < getNumValues() && "Bad value!");
6169 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6170 if (UI.getUse().getResNo() == Value)
6177 /// isOnlyUserOf - Return true if this node is the only use of N.
6179 bool SDNode::isOnlyUserOf(SDNode *N) const {
6181 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6192 /// isOperand - Return true if this node is an operand of N.
6194 bool SDValue::isOperandOf(SDNode *N) const {
6195 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6196 if (*this == N->getOperand(i))
6201 bool SDNode::isOperandOf(SDNode *N) const {
6202 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6203 if (this == N->OperandList[i].getNode())
6208 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6209 /// be a chain) reaches the specified operand without crossing any
6210 /// side-effecting instructions on any chain path. In practice, this looks
6211 /// through token factors and non-volatile loads. In order to remain efficient,
6212 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6213 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6214 unsigned Depth) const {
6215 if (*this == Dest) return true;
6217 // Don't search too deeply, we just want to be able to see through
6218 // TokenFactor's etc.
6219 if (Depth == 0) return false;
6221 // If this is a token factor, all inputs to the TF happen in parallel. If any
6222 // of the operands of the TF does not reach dest, then we cannot do the xform.
6223 if (getOpcode() == ISD::TokenFactor) {
6224 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6225 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6230 // Loads don't have side effects, look through them.
6231 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6232 if (!Ld->isVolatile())
6233 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6238 /// hasPredecessor - Return true if N is a predecessor of this node.
6239 /// N is either an operand of this node, or can be reached by recursively
6240 /// traversing up the operands.
6241 /// NOTE: This is an expensive method. Use it carefully.
6242 bool SDNode::hasPredecessor(const SDNode *N) const {
6243 SmallPtrSet<const SDNode *, 32> Visited;
6244 SmallVector<const SDNode *, 16> Worklist;
6245 return hasPredecessorHelper(N, Visited, Worklist);
6249 SDNode::hasPredecessorHelper(const SDNode *N,
6250 SmallPtrSet<const SDNode *, 32> &Visited,
6251 SmallVectorImpl<const SDNode *> &Worklist) const {
6252 if (Visited.empty()) {
6253 Worklist.push_back(this);
6255 // Take a look in the visited set. If we've already encountered this node
6256 // we needn't search further.
6257 if (Visited.count(N))
6261 // Haven't visited N yet. Continue the search.
6262 while (!Worklist.empty()) {
6263 const SDNode *M = Worklist.pop_back_val();
6264 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6265 SDNode *Op = M->getOperand(i).getNode();
6266 if (Visited.insert(Op))
6267 Worklist.push_back(Op);
6276 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6277 assert(Num < NumOperands && "Invalid child # of SDNode!");
6278 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6281 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6282 assert(N->getNumValues() == 1 &&
6283 "Can't unroll a vector with multiple results!");
6285 EVT VT = N->getValueType(0);
6286 unsigned NE = VT.getVectorNumElements();
6287 EVT EltVT = VT.getVectorElementType();
6290 SmallVector<SDValue, 8> Scalars;
6291 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6293 // If ResNE is 0, fully unroll the vector op.
6296 else if (NE > ResNE)
6300 for (i= 0; i != NE; ++i) {
6301 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6302 SDValue Operand = N->getOperand(j);
6303 EVT OperandVT = Operand.getValueType();
6304 if (OperandVT.isVector()) {
6305 // A vector operand; extract a single element.
6306 const TargetLowering *TLI = TM.getTargetLowering();
6307 EVT OperandEltVT = OperandVT.getVectorElementType();
6308 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6311 getConstant(i, TLI->getVectorIdxTy()));
6313 // A scalar operand; just use it as is.
6314 Operands[j] = Operand;
6318 switch (N->getOpcode()) {
6320 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6323 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6330 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6331 getShiftAmountOperand(Operands[0].getValueType(),
6334 case ISD::SIGN_EXTEND_INREG:
6335 case ISD::FP_ROUND_INREG: {
6336 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6337 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6339 getValueType(ExtVT)));
6344 for (; i < ResNE; ++i)
6345 Scalars.push_back(getUNDEF(EltVT));
6347 return getNode(ISD::BUILD_VECTOR, dl,
6348 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6352 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6353 /// location that is 'Dist' units away from the location that the 'Base' load
6354 /// is loading from.
6355 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6356 unsigned Bytes, int Dist) const {
6357 if (LD->getChain() != Base->getChain())
6359 EVT VT = LD->getValueType(0);
6360 if (VT.getSizeInBits() / 8 != Bytes)
6363 SDValue Loc = LD->getOperand(1);
6364 SDValue BaseLoc = Base->getOperand(1);
6365 if (Loc.getOpcode() == ISD::FrameIndex) {
6366 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6368 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6369 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6370 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6371 int FS = MFI->getObjectSize(FI);
6372 int BFS = MFI->getObjectSize(BFI);
6373 if (FS != BFS || FS != (int)Bytes) return false;
6374 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6378 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6379 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6382 const GlobalValue *GV1 = nullptr;
6383 const GlobalValue *GV2 = nullptr;
6384 int64_t Offset1 = 0;
6385 int64_t Offset2 = 0;
6386 const TargetLowering *TLI = TM.getTargetLowering();
6387 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6388 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6389 if (isGA1 && isGA2 && GV1 == GV2)
6390 return Offset1 == (Offset2 + Dist*Bytes);
6395 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6396 /// it cannot be inferred.
6397 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6398 // If this is a GlobalAddress + cst, return the alignment.
6399 const GlobalValue *GV;
6400 int64_t GVOffset = 0;
6401 const TargetLowering *TLI = TM.getTargetLowering();
6402 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6403 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6404 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6405 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6406 TLI->getDataLayout());
6407 unsigned AlignBits = KnownZero.countTrailingOnes();
6408 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6410 return MinAlign(Align, GVOffset);
6413 // If this is a direct reference to a stack slot, use information about the
6414 // stack slot's alignment.
6415 int FrameIdx = 1 << 31;
6416 int64_t FrameOffset = 0;
6417 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6418 FrameIdx = FI->getIndex();
6419 } else if (isBaseWithConstantOffset(Ptr) &&
6420 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6422 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6423 FrameOffset = Ptr.getConstantOperandVal(1);
6426 if (FrameIdx != (1 << 31)) {
6427 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6428 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6436 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6437 /// which is split (or expanded) into two not necessarily identical pieces.
6438 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6439 // Currently all types are split in half.
6441 if (!VT.isVector()) {
6442 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6444 unsigned NumElements = VT.getVectorNumElements();
6445 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6446 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6449 return std::make_pair(LoVT, HiVT);
6452 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6454 std::pair<SDValue, SDValue>
6455 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6457 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6458 N.getValueType().getVectorNumElements() &&
6459 "More vector elements requested than available!");
6461 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6462 getConstant(0, TLI->getVectorIdxTy()));
6463 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6464 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6465 return std::make_pair(Lo, Hi);
6468 void SelectionDAG::ExtractVectorElements(SDValue Op,
6469 SmallVectorImpl<SDValue> &Args,
6470 unsigned Start, unsigned Count) {
6471 EVT VT = Op.getValueType();
6473 Count = VT.getVectorNumElements();
6475 EVT EltVT = VT.getVectorElementType();
6476 EVT IdxTy = TLI->getVectorIdxTy();
6478 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6479 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6480 Op, getConstant(i, IdxTy)));
6484 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6485 unsigned GlobalAddressSDNode::getAddressSpace() const {
6486 return getGlobal()->getType()->getAddressSpace();
6490 Type *ConstantPoolSDNode::getType() const {
6491 if (isMachineConstantPoolEntry())
6492 return Val.MachineCPVal->getType();
6493 return Val.ConstVal->getType();
6496 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6498 unsigned &SplatBitSize,
6500 unsigned MinSplatBits,
6501 bool isBigEndian) const {
6502 EVT VT = getValueType(0);
6503 assert(VT.isVector() && "Expected a vector type");
6504 unsigned sz = VT.getSizeInBits();
6505 if (MinSplatBits > sz)
6508 SplatValue = APInt(sz, 0);
6509 SplatUndef = APInt(sz, 0);
6511 // Get the bits. Bits with undefined values (when the corresponding element
6512 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6513 // in SplatValue. If any of the values are not constant, give up and return
6515 unsigned int nOps = getNumOperands();
6516 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6517 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6519 for (unsigned j = 0; j < nOps; ++j) {
6520 unsigned i = isBigEndian ? nOps-1-j : j;
6521 SDValue OpVal = getOperand(i);
6522 unsigned BitPos = j * EltBitSize;
6524 if (OpVal.getOpcode() == ISD::UNDEF)
6525 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6526 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6527 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6528 zextOrTrunc(sz) << BitPos;
6529 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6530 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6535 // The build_vector is all constants or undefs. Find the smallest element
6536 // size that splats the vector.
6538 HasAnyUndefs = (SplatUndef != 0);
6541 unsigned HalfSize = sz / 2;
6542 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6543 APInt LowValue = SplatValue.trunc(HalfSize);
6544 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6545 APInt LowUndef = SplatUndef.trunc(HalfSize);
6547 // If the two halves do not match (ignoring undef bits), stop here.
6548 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6549 MinSplatBits > HalfSize)
6552 SplatValue = HighValue | LowValue;
6553 SplatUndef = HighUndef & LowUndef;
6562 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6563 SDValue Op0 = getOperand(0);
6564 if (Op0.getOpcode() != ISD::Constant)
6567 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6568 if (getOperand(i) != Op0)
6571 return cast<ConstantSDNode>(Op0);
6574 bool BuildVectorSDNode::isConstant() const {
6575 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6576 unsigned Opc = getOperand(i).getOpcode();
6577 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6583 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6584 // Find the first non-undef value in the shuffle mask.
6586 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6589 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6591 // Make sure all remaining elements are either undef or the same as the first
6593 for (int Idx = Mask[i]; i != e; ++i)
6594 if (Mask[i] >= 0 && Mask[i] != Idx)
6600 static void checkForCyclesHelper(const SDNode *N,
6601 SmallPtrSet<const SDNode*, 32> &Visited,
6602 SmallPtrSet<const SDNode*, 32> &Checked) {
6603 // If this node has already been checked, don't check it again.
6604 if (Checked.count(N))
6607 // If a node has already been visited on this depth-first walk, reject it as
6609 if (!Visited.insert(N)) {
6610 dbgs() << "Offending node:\n";
6612 errs() << "Detected cycle in SelectionDAG\n";
6616 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6617 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6624 void llvm::checkForCycles(const llvm::SDNode *N) {
6626 assert(N && "Checking nonexistent SDNode");
6627 SmallPtrSet<const SDNode*, 32> visited;
6628 SmallPtrSet<const SDNode*, 32> checked;
6629 checkForCyclesHelper(N, visited, checked);
6633 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6634 checkForCycles(DAG->getRoot().getNode());