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);
1194 if (GV->isThreadLocal())
1195 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1197 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1199 FoldingSetNodeID ID;
1200 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1202 ID.AddInteger(Offset);
1203 ID.AddInteger(TargetFlags);
1204 ID.AddInteger(GV->getType()->getAddressSpace());
1206 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1207 return SDValue(E, 0);
1209 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1210 DL.getDebugLoc(), GV, VT,
1211 Offset, TargetFlags);
1212 CSEMap.InsertNode(N, IP);
1213 AllNodes.push_back(N);
1214 return SDValue(N, 0);
1217 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1218 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1219 FoldingSetNodeID ID;
1220 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1223 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1224 return SDValue(E, 0);
1226 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1227 CSEMap.InsertNode(N, IP);
1228 AllNodes.push_back(N);
1229 return SDValue(N, 0);
1232 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1233 unsigned char TargetFlags) {
1234 assert((TargetFlags == 0 || isTarget) &&
1235 "Cannot set target flags on target-independent jump tables");
1236 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1237 FoldingSetNodeID ID;
1238 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1240 ID.AddInteger(TargetFlags);
1242 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1243 return SDValue(E, 0);
1245 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1247 CSEMap.InsertNode(N, IP);
1248 AllNodes.push_back(N);
1249 return SDValue(N, 0);
1252 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1253 unsigned Alignment, int Offset,
1255 unsigned char TargetFlags) {
1256 assert((TargetFlags == 0 || isTarget) &&
1257 "Cannot set target flags on target-independent globals");
1260 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1261 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1262 FoldingSetNodeID ID;
1263 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1264 ID.AddInteger(Alignment);
1265 ID.AddInteger(Offset);
1267 ID.AddInteger(TargetFlags);
1269 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1270 return SDValue(E, 0);
1272 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1273 Alignment, TargetFlags);
1274 CSEMap.InsertNode(N, IP);
1275 AllNodes.push_back(N);
1276 return SDValue(N, 0);
1280 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1281 unsigned Alignment, int Offset,
1283 unsigned char TargetFlags) {
1284 assert((TargetFlags == 0 || isTarget) &&
1285 "Cannot set target flags on target-independent globals");
1288 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1289 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1290 FoldingSetNodeID ID;
1291 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1292 ID.AddInteger(Alignment);
1293 ID.AddInteger(Offset);
1294 C->addSelectionDAGCSEId(ID);
1295 ID.AddInteger(TargetFlags);
1297 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1298 return SDValue(E, 0);
1300 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1301 Alignment, TargetFlags);
1302 CSEMap.InsertNode(N, IP);
1303 AllNodes.push_back(N);
1304 return SDValue(N, 0);
1307 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1308 unsigned char TargetFlags) {
1309 FoldingSetNodeID ID;
1310 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1311 ID.AddInteger(Index);
1312 ID.AddInteger(Offset);
1313 ID.AddInteger(TargetFlags);
1315 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1316 return SDValue(E, 0);
1318 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1320 CSEMap.InsertNode(N, IP);
1321 AllNodes.push_back(N);
1322 return SDValue(N, 0);
1325 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1326 FoldingSetNodeID ID;
1327 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1330 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1331 return SDValue(E, 0);
1333 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1334 CSEMap.InsertNode(N, IP);
1335 AllNodes.push_back(N);
1336 return SDValue(N, 0);
1339 SDValue SelectionDAG::getValueType(EVT VT) {
1340 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1341 ValueTypeNodes.size())
1342 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1344 SDNode *&N = VT.isExtended() ?
1345 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1347 if (N) return SDValue(N, 0);
1348 N = new (NodeAllocator) VTSDNode(VT);
1349 AllNodes.push_back(N);
1350 return SDValue(N, 0);
1353 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1354 SDNode *&N = ExternalSymbols[Sym];
1355 if (N) return SDValue(N, 0);
1356 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1357 AllNodes.push_back(N);
1358 return SDValue(N, 0);
1361 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1362 unsigned char TargetFlags) {
1364 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1366 if (N) return SDValue(N, 0);
1367 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1368 AllNodes.push_back(N);
1369 return SDValue(N, 0);
1372 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1373 if ((unsigned)Cond >= CondCodeNodes.size())
1374 CondCodeNodes.resize(Cond+1);
1376 if (!CondCodeNodes[Cond]) {
1377 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1378 CondCodeNodes[Cond] = N;
1379 AllNodes.push_back(N);
1382 return SDValue(CondCodeNodes[Cond], 0);
1385 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1386 // the shuffle mask M that point at N1 to point at N2, and indices that point
1387 // N2 to point at N1.
1388 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1390 int NElts = M.size();
1391 for (int i = 0; i != NElts; ++i) {
1399 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1400 SDValue N2, const int *Mask) {
1401 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1402 "Invalid VECTOR_SHUFFLE");
1404 // Canonicalize shuffle undef, undef -> undef
1405 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1406 return getUNDEF(VT);
1408 // Validate that all indices in Mask are within the range of the elements
1409 // input to the shuffle.
1410 unsigned NElts = VT.getVectorNumElements();
1411 SmallVector<int, 8> MaskVec;
1412 for (unsigned i = 0; i != NElts; ++i) {
1413 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1414 MaskVec.push_back(Mask[i]);
1417 // Canonicalize shuffle v, v -> v, undef
1420 for (unsigned i = 0; i != NElts; ++i)
1421 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1424 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1425 if (N1.getOpcode() == ISD::UNDEF)
1426 commuteShuffle(N1, N2, MaskVec);
1428 // Canonicalize all index into lhs, -> shuffle lhs, undef
1429 // Canonicalize all index into rhs, -> shuffle rhs, undef
1430 bool AllLHS = true, AllRHS = true;
1431 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1432 for (unsigned i = 0; i != NElts; ++i) {
1433 if (MaskVec[i] >= (int)NElts) {
1438 } else if (MaskVec[i] >= 0) {
1442 if (AllLHS && AllRHS)
1443 return getUNDEF(VT);
1444 if (AllLHS && !N2Undef)
1448 commuteShuffle(N1, N2, MaskVec);
1451 // If Identity shuffle return that node.
1452 bool Identity = true;
1453 for (unsigned i = 0; i != NElts; ++i) {
1454 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1456 if (Identity && NElts)
1459 // Shuffling a constant splat doesn't change the result.
1460 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1461 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1464 FoldingSetNodeID ID;
1465 SDValue Ops[2] = { N1, N2 };
1466 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1467 for (unsigned i = 0; i != NElts; ++i)
1468 ID.AddInteger(MaskVec[i]);
1471 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1472 return SDValue(E, 0);
1474 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1475 // SDNode doesn't have access to it. This memory will be "leaked" when
1476 // the node is deallocated, but recovered when the NodeAllocator is released.
1477 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1478 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1480 ShuffleVectorSDNode *N =
1481 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1482 dl.getDebugLoc(), N1, N2,
1484 CSEMap.InsertNode(N, IP);
1485 AllNodes.push_back(N);
1486 return SDValue(N, 0);
1489 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1490 SDValue Val, SDValue DTy,
1491 SDValue STy, SDValue Rnd, SDValue Sat,
1492 ISD::CvtCode Code) {
1493 // If the src and dest types are the same and the conversion is between
1494 // integer types of the same sign or two floats, no conversion is necessary.
1496 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1499 FoldingSetNodeID ID;
1500 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1501 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1503 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1504 return SDValue(E, 0);
1506 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1509 CSEMap.InsertNode(N, IP);
1510 AllNodes.push_back(N);
1511 return SDValue(N, 0);
1514 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1515 FoldingSetNodeID ID;
1516 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1517 ID.AddInteger(RegNo);
1519 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1520 return SDValue(E, 0);
1522 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1523 CSEMap.InsertNode(N, IP);
1524 AllNodes.push_back(N);
1525 return SDValue(N, 0);
1528 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1529 FoldingSetNodeID ID;
1530 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1531 ID.AddPointer(RegMask);
1533 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1534 return SDValue(E, 0);
1536 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1537 CSEMap.InsertNode(N, IP);
1538 AllNodes.push_back(N);
1539 return SDValue(N, 0);
1542 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1543 FoldingSetNodeID ID;
1544 SDValue Ops[] = { Root };
1545 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1546 ID.AddPointer(Label);
1548 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1549 return SDValue(E, 0);
1551 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1552 dl.getDebugLoc(), Root, Label);
1553 CSEMap.InsertNode(N, IP);
1554 AllNodes.push_back(N);
1555 return SDValue(N, 0);
1559 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1562 unsigned char TargetFlags) {
1563 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1565 FoldingSetNodeID ID;
1566 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1568 ID.AddInteger(Offset);
1569 ID.AddInteger(TargetFlags);
1571 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1572 return SDValue(E, 0);
1574 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1576 CSEMap.InsertNode(N, IP);
1577 AllNodes.push_back(N);
1578 return SDValue(N, 0);
1581 SDValue SelectionDAG::getSrcValue(const Value *V) {
1582 assert((!V || V->getType()->isPointerTy()) &&
1583 "SrcValue is not a pointer?");
1585 FoldingSetNodeID ID;
1586 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1590 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1591 return SDValue(E, 0);
1593 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1594 CSEMap.InsertNode(N, IP);
1595 AllNodes.push_back(N);
1596 return SDValue(N, 0);
1599 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1600 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1601 FoldingSetNodeID ID;
1602 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1606 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1607 return SDValue(E, 0);
1609 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1610 CSEMap.InsertNode(N, IP);
1611 AllNodes.push_back(N);
1612 return SDValue(N, 0);
1615 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1616 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1617 unsigned SrcAS, unsigned DestAS) {
1618 SDValue Ops[] = {Ptr};
1619 FoldingSetNodeID ID;
1620 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1621 ID.AddInteger(SrcAS);
1622 ID.AddInteger(DestAS);
1625 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1626 return SDValue(E, 0);
1628 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1630 VT, Ptr, SrcAS, DestAS);
1631 CSEMap.InsertNode(N, IP);
1632 AllNodes.push_back(N);
1633 return SDValue(N, 0);
1636 /// getShiftAmountOperand - Return the specified value casted to
1637 /// the target's desired shift amount type.
1638 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1639 EVT OpTy = Op.getValueType();
1640 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1641 if (OpTy == ShTy || OpTy.isVector()) return Op;
1643 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1644 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1647 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1648 /// specified value type.
1649 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1650 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1651 unsigned ByteSize = VT.getStoreSize();
1652 Type *Ty = VT.getTypeForEVT(*getContext());
1653 const TargetLowering *TLI = TM.getTargetLowering();
1654 unsigned StackAlign =
1655 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1657 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1658 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1661 /// CreateStackTemporary - Create a stack temporary suitable for holding
1662 /// either of the specified value types.
1663 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1664 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1665 VT2.getStoreSizeInBits())/8;
1666 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1667 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1668 const TargetLowering *TLI = TM.getTargetLowering();
1669 const DataLayout *TD = TLI->getDataLayout();
1670 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1671 TD->getPrefTypeAlignment(Ty2));
1673 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1674 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1675 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1678 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1679 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1680 // These setcc operations always fold.
1684 case ISD::SETFALSE2: return getConstant(0, VT);
1686 case ISD::SETTRUE2: {
1687 const TargetLowering *TLI = TM.getTargetLowering();
1688 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1690 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1703 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1707 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1708 const APInt &C2 = N2C->getAPIntValue();
1709 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1710 const APInt &C1 = N1C->getAPIntValue();
1713 default: llvm_unreachable("Unknown integer setcc!");
1714 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1715 case ISD::SETNE: return getConstant(C1 != C2, VT);
1716 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1717 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1718 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1719 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1720 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1721 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1722 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1723 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1727 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1728 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1729 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1732 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1733 return getUNDEF(VT);
1735 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1736 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1737 return getUNDEF(VT);
1739 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1740 R==APFloat::cmpLessThan, VT);
1741 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1742 return getUNDEF(VT);
1744 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1745 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1746 return getUNDEF(VT);
1748 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1749 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1750 return getUNDEF(VT);
1752 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1753 R==APFloat::cmpEqual, VT);
1754 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1755 return getUNDEF(VT);
1757 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1758 R==APFloat::cmpEqual, VT);
1759 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1760 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1761 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1762 R==APFloat::cmpEqual, VT);
1763 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1764 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1765 R==APFloat::cmpLessThan, VT);
1766 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1767 R==APFloat::cmpUnordered, VT);
1768 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1769 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1772 // Ensure that the constant occurs on the RHS.
1773 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1774 MVT CompVT = N1.getValueType().getSimpleVT();
1775 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1778 return getSetCC(dl, VT, N2, N1, SwappedCond);
1782 // Could not fold it.
1786 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1787 /// use this predicate to simplify operations downstream.
1788 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1789 // This predicate is not safe for vector operations.
1790 if (Op.getValueType().isVector())
1793 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1794 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1797 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1798 /// this predicate to simplify operations downstream. Mask is known to be zero
1799 /// for bits that V cannot have.
1800 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1801 unsigned Depth) const {
1802 APInt KnownZero, KnownOne;
1803 computeKnownBits(Op, KnownZero, KnownOne, Depth);
1804 return (KnownZero & Mask) == Mask;
1807 /// Determine which bits of Op are known to be either zero or one and return
1808 /// them in the KnownZero/KnownOne bitsets.
1809 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero,
1810 APInt &KnownOne, unsigned Depth) const {
1811 const TargetLowering *TLI = TM.getTargetLowering();
1812 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1814 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1816 return; // Limit search depth.
1818 APInt KnownZero2, KnownOne2;
1820 switch (Op.getOpcode()) {
1822 // We know all of the bits for a constant!
1823 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1824 KnownZero = ~KnownOne;
1827 // If either the LHS or the RHS are Zero, the result is zero.
1828 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1829 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1831 // Output known-1 bits are only known if set in both the LHS & RHS.
1832 KnownOne &= KnownOne2;
1833 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1834 KnownZero |= KnownZero2;
1837 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1838 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1840 // Output known-0 bits are only known if clear in both the LHS & RHS.
1841 KnownZero &= KnownZero2;
1842 // Output known-1 are known to be set if set in either the LHS | RHS.
1843 KnownOne |= KnownOne2;
1846 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1847 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1849 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1850 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1851 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1852 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1853 KnownZero = KnownZeroOut;
1857 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1858 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1860 // If low bits are zero in either operand, output low known-0 bits.
1861 // Also compute a conserative estimate for high known-0 bits.
1862 // More trickiness is possible, but this is sufficient for the
1863 // interesting case of alignment computation.
1864 KnownOne.clearAllBits();
1865 unsigned TrailZ = KnownZero.countTrailingOnes() +
1866 KnownZero2.countTrailingOnes();
1867 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1868 KnownZero2.countLeadingOnes(),
1869 BitWidth) - BitWidth;
1871 TrailZ = std::min(TrailZ, BitWidth);
1872 LeadZ = std::min(LeadZ, BitWidth);
1873 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1874 APInt::getHighBitsSet(BitWidth, LeadZ);
1878 // For the purposes of computing leading zeros we can conservatively
1879 // treat a udiv as a logical right shift by the power of 2 known to
1880 // be less than the denominator.
1881 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1882 unsigned LeadZ = KnownZero2.countLeadingOnes();
1884 KnownOne2.clearAllBits();
1885 KnownZero2.clearAllBits();
1886 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1887 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1888 if (RHSUnknownLeadingOnes != BitWidth)
1889 LeadZ = std::min(BitWidth,
1890 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1892 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1896 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1897 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1899 // Only known if known in both the LHS and RHS.
1900 KnownOne &= KnownOne2;
1901 KnownZero &= KnownZero2;
1903 case ISD::SELECT_CC:
1904 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1905 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1907 // Only known if known in both the LHS and RHS.
1908 KnownOne &= KnownOne2;
1909 KnownZero &= KnownZero2;
1917 if (Op.getResNo() != 1)
1919 // The boolean result conforms to getBooleanContents. Fall through.
1921 // If we know the result of a setcc has the top bits zero, use this info.
1922 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1923 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1924 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1927 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1928 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1929 unsigned ShAmt = SA->getZExtValue();
1931 // If the shift count is an invalid immediate, don't do anything.
1932 if (ShAmt >= BitWidth)
1935 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1936 KnownZero <<= ShAmt;
1938 // low bits known zero.
1939 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1943 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1944 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1945 unsigned ShAmt = SA->getZExtValue();
1947 // If the shift count is an invalid immediate, don't do anything.
1948 if (ShAmt >= BitWidth)
1951 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1952 KnownZero = KnownZero.lshr(ShAmt);
1953 KnownOne = KnownOne.lshr(ShAmt);
1955 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1956 KnownZero |= HighBits; // High bits known zero.
1960 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1961 unsigned ShAmt = SA->getZExtValue();
1963 // If the shift count is an invalid immediate, don't do anything.
1964 if (ShAmt >= BitWidth)
1967 // If any of the demanded bits are produced by the sign extension, we also
1968 // demand the input sign bit.
1969 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt);
1971 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1972 KnownZero = KnownZero.lshr(ShAmt);
1973 KnownOne = KnownOne.lshr(ShAmt);
1975 // Handle the sign bits.
1976 APInt SignBit = APInt::getSignBit(BitWidth);
1977 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1979 if (KnownZero.intersects(SignBit)) {
1980 KnownZero |= HighBits; // New bits are known zero.
1981 } else if (KnownOne.intersects(SignBit)) {
1982 KnownOne |= HighBits; // New bits are known one.
1986 case ISD::SIGN_EXTEND_INREG: {
1987 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1988 unsigned EBits = EVT.getScalarType().getSizeInBits();
1990 // Sign extension. Compute the demanded bits in the result that are not
1991 // present in the input.
1992 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1994 APInt InSignBit = APInt::getSignBit(EBits);
1995 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1997 // If the sign extended bits are demanded, we know that the sign
1999 InSignBit = InSignBit.zext(BitWidth);
2000 if (NewBits.getBoolValue())
2001 InputDemandedBits |= InSignBit;
2003 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2004 KnownOne &= InputDemandedBits;
2005 KnownZero &= InputDemandedBits;
2007 // If the sign bit of the input is known set or clear, then we know the
2008 // top bits of the result.
2009 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2010 KnownZero |= NewBits;
2011 KnownOne &= ~NewBits;
2012 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2013 KnownOne |= NewBits;
2014 KnownZero &= ~NewBits;
2015 } else { // Input sign bit unknown
2016 KnownZero &= ~NewBits;
2017 KnownOne &= ~NewBits;
2022 case ISD::CTTZ_ZERO_UNDEF:
2024 case ISD::CTLZ_ZERO_UNDEF:
2026 unsigned LowBits = Log2_32(BitWidth)+1;
2027 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2028 KnownOne.clearAllBits();
2032 LoadSDNode *LD = cast<LoadSDNode>(Op);
2033 // If this is a ZEXTLoad and we are looking at the loaded value.
2034 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2035 EVT VT = LD->getMemoryVT();
2036 unsigned MemBits = VT.getScalarType().getSizeInBits();
2037 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2038 } else if (const MDNode *Ranges = LD->getRanges()) {
2039 computeKnownBitsLoad(*Ranges, KnownZero);
2043 case ISD::ZERO_EXTEND: {
2044 EVT InVT = Op.getOperand(0).getValueType();
2045 unsigned InBits = InVT.getScalarType().getSizeInBits();
2046 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2047 KnownZero = KnownZero.trunc(InBits);
2048 KnownOne = KnownOne.trunc(InBits);
2049 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2050 KnownZero = KnownZero.zext(BitWidth);
2051 KnownOne = KnownOne.zext(BitWidth);
2052 KnownZero |= NewBits;
2055 case ISD::SIGN_EXTEND: {
2056 EVT InVT = Op.getOperand(0).getValueType();
2057 unsigned InBits = InVT.getScalarType().getSizeInBits();
2058 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2060 KnownZero = KnownZero.trunc(InBits);
2061 KnownOne = KnownOne.trunc(InBits);
2062 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2064 // Note if the sign bit is known to be zero or one.
2065 bool SignBitKnownZero = KnownZero.isNegative();
2066 bool SignBitKnownOne = KnownOne.isNegative();
2068 KnownZero = KnownZero.zext(BitWidth);
2069 KnownOne = KnownOne.zext(BitWidth);
2071 // If the sign bit is known zero or one, the top bits match.
2072 if (SignBitKnownZero)
2073 KnownZero |= NewBits;
2074 else if (SignBitKnownOne)
2075 KnownOne |= NewBits;
2078 case ISD::ANY_EXTEND: {
2079 EVT InVT = Op.getOperand(0).getValueType();
2080 unsigned InBits = InVT.getScalarType().getSizeInBits();
2081 KnownZero = KnownZero.trunc(InBits);
2082 KnownOne = KnownOne.trunc(InBits);
2083 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2084 KnownZero = KnownZero.zext(BitWidth);
2085 KnownOne = KnownOne.zext(BitWidth);
2088 case ISD::TRUNCATE: {
2089 EVT InVT = Op.getOperand(0).getValueType();
2090 unsigned InBits = InVT.getScalarType().getSizeInBits();
2091 KnownZero = KnownZero.zext(InBits);
2092 KnownOne = KnownOne.zext(InBits);
2093 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2094 KnownZero = KnownZero.trunc(BitWidth);
2095 KnownOne = KnownOne.trunc(BitWidth);
2098 case ISD::AssertZext: {
2099 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2100 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2101 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2102 KnownZero |= (~InMask);
2103 KnownOne &= (~KnownZero);
2107 // All bits are zero except the low bit.
2108 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2112 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2113 // We know that the top bits of C-X are clear if X contains less bits
2114 // than C (i.e. no wrap-around can happen). For example, 20-X is
2115 // positive if we can prove that X is >= 0 and < 16.
2116 if (CLHS->getAPIntValue().isNonNegative()) {
2117 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2118 // NLZ can't be BitWidth with no sign bit
2119 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2120 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2122 // If all of the MaskV bits are known to be zero, then we know the
2123 // output top bits are zero, because we now know that the output is
2125 if ((KnownZero2 & MaskV) == MaskV) {
2126 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2127 // Top bits known zero.
2128 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2136 // Output known-0 bits are known if clear or set in both the low clear bits
2137 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2138 // low 3 bits clear.
2139 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2140 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2142 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2143 KnownZeroOut = std::min(KnownZeroOut,
2144 KnownZero2.countTrailingOnes());
2146 if (Op.getOpcode() == ISD::ADD) {
2147 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2151 // With ADDE, a carry bit may be added in, so we can only use this
2152 // information if we know (at least) that the low two bits are clear. We
2153 // then return to the caller that the low bit is unknown but that other bits
2155 if (KnownZeroOut >= 2) // ADDE
2156 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2160 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2161 const APInt &RA = Rem->getAPIntValue().abs();
2162 if (RA.isPowerOf2()) {
2163 APInt LowBits = RA - 1;
2164 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2166 // The low bits of the first operand are unchanged by the srem.
2167 KnownZero = KnownZero2 & LowBits;
2168 KnownOne = KnownOne2 & LowBits;
2170 // If the first operand is non-negative or has all low bits zero, then
2171 // the upper bits are all zero.
2172 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2173 KnownZero |= ~LowBits;
2175 // If the first operand is negative and not all low bits are zero, then
2176 // the upper bits are all one.
2177 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2178 KnownOne |= ~LowBits;
2179 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2184 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2185 const APInt &RA = Rem->getAPIntValue();
2186 if (RA.isPowerOf2()) {
2187 APInt LowBits = (RA - 1);
2188 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1);
2190 // The upper bits are all zero, the lower ones are unchanged.
2191 KnownZero = KnownZero2 | ~LowBits;
2192 KnownOne = KnownOne2 & LowBits;
2197 // Since the result is less than or equal to either operand, any leading
2198 // zero bits in either operand must also exist in the result.
2199 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2200 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2202 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2203 KnownZero2.countLeadingOnes());
2204 KnownOne.clearAllBits();
2205 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2208 case ISD::FrameIndex:
2209 case ISD::TargetFrameIndex:
2210 if (unsigned Align = InferPtrAlignment(Op)) {
2211 // The low bits are known zero if the pointer is aligned.
2212 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2218 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2221 case ISD::INTRINSIC_WO_CHAIN:
2222 case ISD::INTRINSIC_W_CHAIN:
2223 case ISD::INTRINSIC_VOID:
2224 // Allow the target to implement this method for its nodes.
2225 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2229 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2232 /// ComputeNumSignBits - Return the number of times the sign bit of the
2233 /// register is replicated into the other bits. We know that at least 1 bit
2234 /// is always equal to the sign bit (itself), but other cases can give us
2235 /// information. For example, immediately after an "SRA X, 2", we know that
2236 /// the top 3 bits are all equal to each other, so we return 3.
2237 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2238 const TargetLowering *TLI = TM.getTargetLowering();
2239 EVT VT = Op.getValueType();
2240 assert(VT.isInteger() && "Invalid VT!");
2241 unsigned VTBits = VT.getScalarType().getSizeInBits();
2243 unsigned FirstAnswer = 1;
2246 return 1; // Limit search depth.
2248 switch (Op.getOpcode()) {
2250 case ISD::AssertSext:
2251 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2252 return VTBits-Tmp+1;
2253 case ISD::AssertZext:
2254 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2257 case ISD::Constant: {
2258 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2259 return Val.getNumSignBits();
2262 case ISD::SIGN_EXTEND:
2264 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2265 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2267 case ISD::SIGN_EXTEND_INREG:
2268 // Max of the input and what this extends.
2270 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2273 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2274 return std::max(Tmp, Tmp2);
2277 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2278 // SRA X, C -> adds C sign bits.
2279 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2280 Tmp += C->getZExtValue();
2281 if (Tmp > VTBits) Tmp = VTBits;
2285 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2286 // shl destroys sign bits.
2287 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2288 if (C->getZExtValue() >= VTBits || // Bad shift.
2289 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2290 return Tmp - C->getZExtValue();
2295 case ISD::XOR: // NOT is handled here.
2296 // Logical binary ops preserve the number of sign bits at the worst.
2297 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2299 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2300 FirstAnswer = std::min(Tmp, Tmp2);
2301 // We computed what we know about the sign bits as our first
2302 // answer. Now proceed to the generic code that uses
2303 // computeKnownBits, and pick whichever answer is better.
2308 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2309 if (Tmp == 1) return 1; // Early out.
2310 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2311 return std::min(Tmp, Tmp2);
2319 if (Op.getResNo() != 1)
2321 // The boolean result conforms to getBooleanContents. Fall through.
2323 // If setcc returns 0/-1, all bits are sign bits.
2324 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2325 TargetLowering::ZeroOrNegativeOneBooleanContent)
2330 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2331 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2333 // Handle rotate right by N like a rotate left by 32-N.
2334 if (Op.getOpcode() == ISD::ROTR)
2335 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2337 // If we aren't rotating out all of the known-in sign bits, return the
2338 // number that are left. This handles rotl(sext(x), 1) for example.
2339 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2340 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2344 // Add can have at most one carry bit. Thus we know that the output
2345 // is, at worst, one more bit than the inputs.
2346 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2347 if (Tmp == 1) return 1; // Early out.
2349 // Special case decrementing a value (ADD X, -1):
2350 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2351 if (CRHS->isAllOnesValue()) {
2352 APInt KnownZero, KnownOne;
2353 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2355 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2357 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2360 // If we are subtracting one from a positive number, there is no carry
2361 // out of the result.
2362 if (KnownZero.isNegative())
2366 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2367 if (Tmp2 == 1) return 1;
2368 return std::min(Tmp, Tmp2)-1;
2371 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2372 if (Tmp2 == 1) return 1;
2375 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2376 if (CLHS->isNullValue()) {
2377 APInt KnownZero, KnownOne;
2378 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2379 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2381 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2384 // If the input is known to be positive (the sign bit is known clear),
2385 // the output of the NEG has the same number of sign bits as the input.
2386 if (KnownZero.isNegative())
2389 // Otherwise, we treat this like a SUB.
2392 // Sub can have at most one carry bit. Thus we know that the output
2393 // is, at worst, one more bit than the inputs.
2394 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2395 if (Tmp == 1) return 1; // Early out.
2396 return std::min(Tmp, Tmp2)-1;
2398 // FIXME: it's tricky to do anything useful for this, but it is an important
2399 // case for targets like X86.
2403 // If we are looking at the loaded value of the SDNode.
2404 if (Op.getResNo() == 0) {
2405 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2406 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2407 unsigned ExtType = LD->getExtensionType();
2410 case ISD::SEXTLOAD: // '17' bits known
2411 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2412 return VTBits-Tmp+1;
2413 case ISD::ZEXTLOAD: // '16' bits known
2414 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2420 // Allow the target to implement this method for its nodes.
2421 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2422 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2423 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2424 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2425 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2426 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2429 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2430 // use this information.
2431 APInt KnownZero, KnownOne;
2432 computeKnownBits(Op, KnownZero, KnownOne, Depth);
2435 if (KnownZero.isNegative()) { // sign bit is 0
2437 } else if (KnownOne.isNegative()) { // sign bit is 1;
2444 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2445 // the number of identical bits in the top of the input value.
2447 Mask <<= Mask.getBitWidth()-VTBits;
2448 // Return # leading zeros. We use 'min' here in case Val was zero before
2449 // shifting. We don't want to return '64' as for an i32 "0".
2450 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2453 /// isBaseWithConstantOffset - Return true if the specified operand is an
2454 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2455 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2456 /// semantics as an ADD. This handles the equivalence:
2457 /// X|Cst == X+Cst iff X&Cst = 0.
2458 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2459 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2460 !isa<ConstantSDNode>(Op.getOperand(1)))
2463 if (Op.getOpcode() == ISD::OR &&
2464 !MaskedValueIsZero(Op.getOperand(0),
2465 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2472 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2473 // If we're told that NaNs won't happen, assume they won't.
2474 if (getTarget().Options.NoNaNsFPMath)
2477 // If the value is a constant, we can obviously see if it is a NaN or not.
2478 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2479 return !C->getValueAPF().isNaN();
2481 // TODO: Recognize more cases here.
2486 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2487 // If the value is a constant, we can obviously see if it is a zero or not.
2488 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2489 return !C->isZero();
2491 // TODO: Recognize more cases here.
2492 switch (Op.getOpcode()) {
2495 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2496 return !C->isNullValue();
2503 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2504 // Check the obvious case.
2505 if (A == B) return true;
2507 // For for negative and positive zero.
2508 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2509 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2510 if (CA->isZero() && CB->isZero()) return true;
2512 // Otherwise they may not be equal.
2516 /// getNode - Gets or creates the specified node.
2518 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2519 FoldingSetNodeID ID;
2520 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2522 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2523 return SDValue(E, 0);
2525 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2526 DL.getDebugLoc(), getVTList(VT));
2527 CSEMap.InsertNode(N, IP);
2529 AllNodes.push_back(N);
2533 return SDValue(N, 0);
2536 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2537 EVT VT, SDValue Operand) {
2538 // Constant fold unary operations with an integer constant operand. Even
2539 // opaque constant will be folded, because the folding of unary operations
2540 // doesn't create new constants with different values. Nevertheless, the
2541 // opaque flag is preserved during folding to prevent future folding with
2543 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2544 const APInt &Val = C->getAPIntValue();
2547 case ISD::SIGN_EXTEND:
2548 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2549 C->isTargetOpcode(), C->isOpaque());
2550 case ISD::ANY_EXTEND:
2551 case ISD::ZERO_EXTEND:
2553 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2554 C->isTargetOpcode(), C->isOpaque());
2555 case ISD::UINT_TO_FP:
2556 case ISD::SINT_TO_FP: {
2557 APFloat apf(EVTToAPFloatSemantics(VT),
2558 APInt::getNullValue(VT.getSizeInBits()));
2559 (void)apf.convertFromAPInt(Val,
2560 Opcode==ISD::SINT_TO_FP,
2561 APFloat::rmNearestTiesToEven);
2562 return getConstantFP(apf, VT);
2565 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2566 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2567 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2568 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2571 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2574 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2577 case ISD::CTLZ_ZERO_UNDEF:
2578 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2581 case ISD::CTTZ_ZERO_UNDEF:
2582 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2587 // Constant fold unary operations with a floating point constant operand.
2588 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2589 APFloat V = C->getValueAPF(); // make copy
2593 return getConstantFP(V, VT);
2596 return getConstantFP(V, VT);
2598 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2599 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2600 return getConstantFP(V, VT);
2604 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2605 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2606 return getConstantFP(V, VT);
2610 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2611 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2612 return getConstantFP(V, VT);
2615 case ISD::FP_EXTEND: {
2617 // This can return overflow, underflow, or inexact; we don't care.
2618 // FIXME need to be more flexible about rounding mode.
2619 (void)V.convert(EVTToAPFloatSemantics(VT),
2620 APFloat::rmNearestTiesToEven, &ignored);
2621 return getConstantFP(V, VT);
2623 case ISD::FP_TO_SINT:
2624 case ISD::FP_TO_UINT: {
2627 assert(integerPartWidth >= 64);
2628 // FIXME need to be more flexible about rounding mode.
2629 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2630 Opcode==ISD::FP_TO_SINT,
2631 APFloat::rmTowardZero, &ignored);
2632 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2634 APInt api(VT.getSizeInBits(), x);
2635 return getConstant(api, VT);
2638 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2639 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2640 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2641 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2646 unsigned OpOpcode = Operand.getNode()->getOpcode();
2648 case ISD::TokenFactor:
2649 case ISD::MERGE_VALUES:
2650 case ISD::CONCAT_VECTORS:
2651 return Operand; // Factor, merge or concat of one node? No need.
2652 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2653 case ISD::FP_EXTEND:
2654 assert(VT.isFloatingPoint() &&
2655 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2656 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2657 assert((!VT.isVector() ||
2658 VT.getVectorNumElements() ==
2659 Operand.getValueType().getVectorNumElements()) &&
2660 "Vector element count mismatch!");
2661 if (Operand.getOpcode() == ISD::UNDEF)
2662 return getUNDEF(VT);
2664 case ISD::SIGN_EXTEND:
2665 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2666 "Invalid SIGN_EXTEND!");
2667 if (Operand.getValueType() == VT) return Operand; // noop extension
2668 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2669 "Invalid sext node, dst < src!");
2670 assert((!VT.isVector() ||
2671 VT.getVectorNumElements() ==
2672 Operand.getValueType().getVectorNumElements()) &&
2673 "Vector element count mismatch!");
2674 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2675 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2676 else if (OpOpcode == ISD::UNDEF)
2677 // sext(undef) = 0, because the top bits will all be the same.
2678 return getConstant(0, VT);
2680 case ISD::ZERO_EXTEND:
2681 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2682 "Invalid ZERO_EXTEND!");
2683 if (Operand.getValueType() == VT) return Operand; // noop extension
2684 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2685 "Invalid zext node, dst < src!");
2686 assert((!VT.isVector() ||
2687 VT.getVectorNumElements() ==
2688 Operand.getValueType().getVectorNumElements()) &&
2689 "Vector element count mismatch!");
2690 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2691 return getNode(ISD::ZERO_EXTEND, DL, VT,
2692 Operand.getNode()->getOperand(0));
2693 else if (OpOpcode == ISD::UNDEF)
2694 // zext(undef) = 0, because the top bits will be zero.
2695 return getConstant(0, VT);
2697 case ISD::ANY_EXTEND:
2698 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2699 "Invalid ANY_EXTEND!");
2700 if (Operand.getValueType() == VT) return Operand; // noop extension
2701 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2702 "Invalid anyext node, dst < src!");
2703 assert((!VT.isVector() ||
2704 VT.getVectorNumElements() ==
2705 Operand.getValueType().getVectorNumElements()) &&
2706 "Vector element count mismatch!");
2708 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2709 OpOpcode == ISD::ANY_EXTEND)
2710 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2711 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2712 else if (OpOpcode == ISD::UNDEF)
2713 return getUNDEF(VT);
2715 // (ext (trunx x)) -> x
2716 if (OpOpcode == ISD::TRUNCATE) {
2717 SDValue OpOp = Operand.getNode()->getOperand(0);
2718 if (OpOp.getValueType() == VT)
2723 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2724 "Invalid TRUNCATE!");
2725 if (Operand.getValueType() == VT) return Operand; // noop truncate
2726 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2727 "Invalid truncate node, src < dst!");
2728 assert((!VT.isVector() ||
2729 VT.getVectorNumElements() ==
2730 Operand.getValueType().getVectorNumElements()) &&
2731 "Vector element count mismatch!");
2732 if (OpOpcode == ISD::TRUNCATE)
2733 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2734 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2735 OpOpcode == ISD::ANY_EXTEND) {
2736 // If the source is smaller than the dest, we still need an extend.
2737 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2738 .bitsLT(VT.getScalarType()))
2739 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2740 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2741 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2742 return Operand.getNode()->getOperand(0);
2744 if (OpOpcode == ISD::UNDEF)
2745 return getUNDEF(VT);
2748 // Basic sanity checking.
2749 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2750 && "Cannot BITCAST between types of different sizes!");
2751 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2752 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2753 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2754 if (OpOpcode == ISD::UNDEF)
2755 return getUNDEF(VT);
2757 case ISD::SCALAR_TO_VECTOR:
2758 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2759 (VT.getVectorElementType() == Operand.getValueType() ||
2760 (VT.getVectorElementType().isInteger() &&
2761 Operand.getValueType().isInteger() &&
2762 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2763 "Illegal SCALAR_TO_VECTOR node!");
2764 if (OpOpcode == ISD::UNDEF)
2765 return getUNDEF(VT);
2766 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2767 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2768 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2769 Operand.getConstantOperandVal(1) == 0 &&
2770 Operand.getOperand(0).getValueType() == VT)
2771 return Operand.getOperand(0);
2774 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2775 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2776 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2777 Operand.getNode()->getOperand(0));
2778 if (OpOpcode == ISD::FNEG) // --X -> X
2779 return Operand.getNode()->getOperand(0);
2782 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2783 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2788 SDVTList VTs = getVTList(VT);
2789 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2790 FoldingSetNodeID ID;
2791 SDValue Ops[1] = { Operand };
2792 AddNodeIDNode(ID, Opcode, VTs, Ops);
2794 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2795 return SDValue(E, 0);
2797 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2798 DL.getDebugLoc(), VTs, Operand);
2799 CSEMap.InsertNode(N, IP);
2801 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2802 DL.getDebugLoc(), VTs, Operand);
2805 AllNodes.push_back(N);
2809 return SDValue(N, 0);
2812 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2813 SDNode *Cst1, SDNode *Cst2) {
2814 // If the opcode is a target-specific ISD node, there's nothing we can
2815 // do here and the operand rules may not line up with the below, so
2817 if (Opcode >= ISD::BUILTIN_OP_END)
2820 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2821 SmallVector<SDValue, 4> Outputs;
2822 EVT SVT = VT.getScalarType();
2824 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2825 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2826 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2829 if (Scalar1 && Scalar2)
2830 // Scalar instruction.
2831 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2833 // For vectors extract each constant element into Inputs so we can constant
2834 // fold them individually.
2835 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2836 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2840 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2842 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2843 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2844 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2845 if (!V1 || !V2) // Not a constant, bail.
2848 if (V1->isOpaque() || V2->isOpaque())
2851 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2852 // FIXME: This is valid and could be handled by truncating the APInts.
2853 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2856 Inputs.push_back(std::make_pair(V1, V2));
2860 // We have a number of constant values, constant fold them element by element.
2861 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2862 const APInt &C1 = Inputs[I].first->getAPIntValue();
2863 const APInt &C2 = Inputs[I].second->getAPIntValue();
2867 Outputs.push_back(getConstant(C1 + C2, SVT));
2870 Outputs.push_back(getConstant(C1 - C2, SVT));
2873 Outputs.push_back(getConstant(C1 * C2, SVT));
2876 if (!C2.getBoolValue())
2878 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2881 if (!C2.getBoolValue())
2883 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2886 if (!C2.getBoolValue())
2888 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2891 if (!C2.getBoolValue())
2893 Outputs.push_back(getConstant(C1.srem(C2), SVT));
2896 Outputs.push_back(getConstant(C1 & C2, SVT));
2899 Outputs.push_back(getConstant(C1 | C2, SVT));
2902 Outputs.push_back(getConstant(C1 ^ C2, SVT));
2905 Outputs.push_back(getConstant(C1 << C2, SVT));
2908 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2911 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2914 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2917 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2924 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() &&
2925 "Expected a scalar or vector!"));
2927 // Handle the scalar case first.
2929 return Outputs.back();
2931 // We may have a vector type but a scalar result. Create a splat.
2932 Outputs.resize(VT.getVectorNumElements(), Outputs.back());
2934 // Build a big vector out of the scalar elements we generated.
2935 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2938 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2940 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2941 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2944 case ISD::TokenFactor:
2945 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2946 N2.getValueType() == MVT::Other && "Invalid token factor!");
2947 // Fold trivial token factors.
2948 if (N1.getOpcode() == ISD::EntryToken) return N2;
2949 if (N2.getOpcode() == ISD::EntryToken) return N1;
2950 if (N1 == N2) return N1;
2952 case ISD::CONCAT_VECTORS:
2953 // Concat of UNDEFs is UNDEF.
2954 if (N1.getOpcode() == ISD::UNDEF &&
2955 N2.getOpcode() == ISD::UNDEF)
2956 return getUNDEF(VT);
2958 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2959 // one big BUILD_VECTOR.
2960 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2961 N2.getOpcode() == ISD::BUILD_VECTOR) {
2962 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2963 N1.getNode()->op_end());
2964 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2965 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2969 assert(VT.isInteger() && "This operator does not apply to FP types!");
2970 assert(N1.getValueType() == N2.getValueType() &&
2971 N1.getValueType() == VT && "Binary operator types must match!");
2972 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2973 // worth handling here.
2974 if (N2C && N2C->isNullValue())
2976 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2983 assert(VT.isInteger() && "This operator does not apply to FP types!");
2984 assert(N1.getValueType() == N2.getValueType() &&
2985 N1.getValueType() == VT && "Binary operator types must match!");
2986 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2987 // it's worth handling here.
2988 if (N2C && N2C->isNullValue())
2998 assert(VT.isInteger() && "This operator does not apply to FP types!");
2999 assert(N1.getValueType() == N2.getValueType() &&
3000 N1.getValueType() == VT && "Binary operator types must match!");
3007 if (getTarget().Options.UnsafeFPMath) {
3008 if (Opcode == ISD::FADD) {
3010 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3011 if (CFP->getValueAPF().isZero())
3014 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3015 if (CFP->getValueAPF().isZero())
3017 } else if (Opcode == ISD::FSUB) {
3019 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3020 if (CFP->getValueAPF().isZero())
3022 } else if (Opcode == ISD::FMUL) {
3023 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3026 // If the first operand isn't the constant, try the second
3028 CFP = dyn_cast<ConstantFPSDNode>(N2);
3035 return SDValue(CFP,0);
3037 if (CFP->isExactlyValue(1.0))
3042 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3043 assert(N1.getValueType() == N2.getValueType() &&
3044 N1.getValueType() == VT && "Binary operator types must match!");
3046 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3047 assert(N1.getValueType() == VT &&
3048 N1.getValueType().isFloatingPoint() &&
3049 N2.getValueType().isFloatingPoint() &&
3050 "Invalid FCOPYSIGN!");
3057 assert(VT == N1.getValueType() &&
3058 "Shift operators return type must be the same as their first arg");
3059 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3060 "Shifts only work on integers");
3061 assert((!VT.isVector() || VT == N2.getValueType()) &&
3062 "Vector shift amounts must be in the same as their first arg");
3063 // Verify that the shift amount VT is bit enough to hold valid shift
3064 // amounts. This catches things like trying to shift an i1024 value by an
3065 // i8, which is easy to fall into in generic code that uses
3066 // TLI.getShiftAmount().
3067 assert(N2.getValueType().getSizeInBits() >=
3068 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3069 "Invalid use of small shift amount with oversized value!");
3071 // Always fold shifts of i1 values so the code generator doesn't need to
3072 // handle them. Since we know the size of the shift has to be less than the
3073 // size of the value, the shift/rotate count is guaranteed to be zero.
3076 if (N2C && N2C->isNullValue())
3079 case ISD::FP_ROUND_INREG: {
3080 EVT EVT = cast<VTSDNode>(N2)->getVT();
3081 assert(VT == N1.getValueType() && "Not an inreg round!");
3082 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3083 "Cannot FP_ROUND_INREG integer types");
3084 assert(EVT.isVector() == VT.isVector() &&
3085 "FP_ROUND_INREG type should be vector iff the operand "
3087 assert((!EVT.isVector() ||
3088 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3089 "Vector element counts must match in FP_ROUND_INREG");
3090 assert(EVT.bitsLE(VT) && "Not rounding down!");
3092 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3096 assert(VT.isFloatingPoint() &&
3097 N1.getValueType().isFloatingPoint() &&
3098 VT.bitsLE(N1.getValueType()) &&
3099 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3100 if (N1.getValueType() == VT) return N1; // noop conversion.
3102 case ISD::AssertSext:
3103 case ISD::AssertZext: {
3104 EVT EVT = cast<VTSDNode>(N2)->getVT();
3105 assert(VT == N1.getValueType() && "Not an inreg extend!");
3106 assert(VT.isInteger() && EVT.isInteger() &&
3107 "Cannot *_EXTEND_INREG FP types");
3108 assert(!EVT.isVector() &&
3109 "AssertSExt/AssertZExt type should be the vector element type "
3110 "rather than the vector type!");
3111 assert(EVT.bitsLE(VT) && "Not extending!");
3112 if (VT == EVT) return N1; // noop assertion.
3115 case ISD::SIGN_EXTEND_INREG: {
3116 EVT EVT = cast<VTSDNode>(N2)->getVT();
3117 assert(VT == N1.getValueType() && "Not an inreg extend!");
3118 assert(VT.isInteger() && EVT.isInteger() &&
3119 "Cannot *_EXTEND_INREG FP types");
3120 assert(EVT.isVector() == VT.isVector() &&
3121 "SIGN_EXTEND_INREG type should be vector iff the operand "
3123 assert((!EVT.isVector() ||
3124 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3125 "Vector element counts must match in SIGN_EXTEND_INREG");
3126 assert(EVT.bitsLE(VT) && "Not extending!");
3127 if (EVT == VT) return N1; // Not actually extending
3130 APInt Val = N1C->getAPIntValue();
3131 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3132 Val <<= Val.getBitWidth()-FromBits;
3133 Val = Val.ashr(Val.getBitWidth()-FromBits);
3134 return getConstant(Val, VT);
3138 case ISD::EXTRACT_VECTOR_ELT:
3139 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3140 if (N1.getOpcode() == ISD::UNDEF)
3141 return getUNDEF(VT);
3143 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3144 // expanding copies of large vectors from registers.
3146 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3147 N1.getNumOperands() > 0) {
3149 N1.getOperand(0).getValueType().getVectorNumElements();
3150 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3151 N1.getOperand(N2C->getZExtValue() / Factor),
3152 getConstant(N2C->getZExtValue() % Factor,
3153 N2.getValueType()));
3156 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3157 // expanding large vector constants.
3158 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3159 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3161 if (VT != Elt.getValueType())
3162 // If the vector element type is not legal, the BUILD_VECTOR operands
3163 // are promoted and implicitly truncated, and the result implicitly
3164 // extended. Make that explicit here.
3165 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3170 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3171 // operations are lowered to scalars.
3172 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3173 // If the indices are the same, return the inserted element else
3174 // if the indices are known different, extract the element from
3175 // the original vector.
3176 SDValue N1Op2 = N1.getOperand(2);
3177 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3179 if (N1Op2C && N2C) {
3180 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3181 if (VT == N1.getOperand(1).getValueType())
3182 return N1.getOperand(1);
3184 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3187 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3191 case ISD::EXTRACT_ELEMENT:
3192 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3193 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3194 (N1.getValueType().isInteger() == VT.isInteger()) &&
3195 N1.getValueType() != VT &&
3196 "Wrong types for EXTRACT_ELEMENT!");
3198 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3199 // 64-bit integers into 32-bit parts. Instead of building the extract of
3200 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3201 if (N1.getOpcode() == ISD::BUILD_PAIR)
3202 return N1.getOperand(N2C->getZExtValue());
3204 // EXTRACT_ELEMENT of a constant int is also very common.
3205 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3206 unsigned ElementSize = VT.getSizeInBits();
3207 unsigned Shift = ElementSize * N2C->getZExtValue();
3208 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3209 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3212 case ISD::EXTRACT_SUBVECTOR: {
3214 if (VT.isSimple() && N1.getValueType().isSimple()) {
3215 assert(VT.isVector() && N1.getValueType().isVector() &&
3216 "Extract subvector VTs must be a vectors!");
3217 assert(VT.getVectorElementType() ==
3218 N1.getValueType().getVectorElementType() &&
3219 "Extract subvector VTs must have the same element type!");
3220 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3221 "Extract subvector must be from larger vector to smaller vector!");
3223 if (isa<ConstantSDNode>(Index.getNode())) {
3224 assert((VT.getVectorNumElements() +
3225 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3226 <= N1.getValueType().getVectorNumElements())
3227 && "Extract subvector overflow!");
3230 // Trivial extraction.
3231 if (VT.getSimpleVT() == N1.getSimpleValueType())
3238 // Perform trivial constant folding.
3239 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3240 if (SV.getNode()) return SV;
3242 // Canonicalize constant to RHS if commutative.
3243 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3244 std::swap(N1C, N2C);
3248 // Constant fold FP operations.
3249 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3250 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3252 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3253 // Canonicalize constant to RHS if commutative.
3254 std::swap(N1CFP, N2CFP);
3257 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3258 APFloat::opStatus s;
3261 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3262 if (s != APFloat::opInvalidOp)
3263 return getConstantFP(V1, VT);
3266 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3267 if (s!=APFloat::opInvalidOp)
3268 return getConstantFP(V1, VT);
3271 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3272 if (s!=APFloat::opInvalidOp)
3273 return getConstantFP(V1, VT);
3276 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3277 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3278 return getConstantFP(V1, VT);
3281 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3282 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3283 return getConstantFP(V1, VT);
3285 case ISD::FCOPYSIGN:
3287 return getConstantFP(V1, VT);
3292 if (Opcode == ISD::FP_ROUND) {
3293 APFloat V = N1CFP->getValueAPF(); // make copy
3295 // This can return overflow, underflow, or inexact; we don't care.
3296 // FIXME need to be more flexible about rounding mode.
3297 (void)V.convert(EVTToAPFloatSemantics(VT),
3298 APFloat::rmNearestTiesToEven, &ignored);
3299 return getConstantFP(V, VT);
3303 // Canonicalize an UNDEF to the RHS, even over a constant.
3304 if (N1.getOpcode() == ISD::UNDEF) {
3305 if (isCommutativeBinOp(Opcode)) {
3309 case ISD::FP_ROUND_INREG:
3310 case ISD::SIGN_EXTEND_INREG:
3316 return N1; // fold op(undef, arg2) -> undef
3324 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3325 // For vectors, we can't easily build an all zero vector, just return
3332 // Fold a bunch of operators when the RHS is undef.
3333 if (N2.getOpcode() == ISD::UNDEF) {
3336 if (N1.getOpcode() == ISD::UNDEF)
3337 // Handle undef ^ undef -> 0 special case. This is a common
3339 return getConstant(0, VT);
3349 return N2; // fold op(arg1, undef) -> undef
3355 if (getTarget().Options.UnsafeFPMath)
3363 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3364 // For vectors, we can't easily build an all zero vector, just return
3369 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3370 // For vectors, we can't easily build an all one vector, just return
3378 // Memoize this node if possible.
3380 SDVTList VTs = getVTList(VT);
3381 if (VT != MVT::Glue) {
3382 SDValue Ops[] = { N1, N2 };
3383 FoldingSetNodeID ID;
3384 AddNodeIDNode(ID, Opcode, VTs, Ops);
3386 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3387 return SDValue(E, 0);
3389 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3390 DL.getDebugLoc(), VTs, N1, N2);
3391 CSEMap.InsertNode(N, IP);
3393 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3394 DL.getDebugLoc(), VTs, N1, N2);
3397 AllNodes.push_back(N);
3401 return SDValue(N, 0);
3404 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3405 SDValue N1, SDValue N2, SDValue N3) {
3406 // Perform various simplifications.
3407 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3410 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3411 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3412 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3413 if (N1CFP && N2CFP && N3CFP) {
3414 APFloat V1 = N1CFP->getValueAPF();
3415 const APFloat &V2 = N2CFP->getValueAPF();
3416 const APFloat &V3 = N3CFP->getValueAPF();
3417 APFloat::opStatus s =
3418 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3419 if (s != APFloat::opInvalidOp)
3420 return getConstantFP(V1, VT);
3424 case ISD::CONCAT_VECTORS:
3425 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3426 // one big BUILD_VECTOR.
3427 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3428 N2.getOpcode() == ISD::BUILD_VECTOR &&
3429 N3.getOpcode() == ISD::BUILD_VECTOR) {
3430 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3431 N1.getNode()->op_end());
3432 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3433 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3434 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3438 // Use FoldSetCC to simplify SETCC's.
3439 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3440 if (Simp.getNode()) return Simp;
3445 if (N1C->getZExtValue())
3446 return N2; // select true, X, Y -> X
3447 return N3; // select false, X, Y -> Y
3450 if (N2 == N3) return N2; // select C, X, X -> X
3452 case ISD::VECTOR_SHUFFLE:
3453 llvm_unreachable("should use getVectorShuffle constructor!");
3454 case ISD::INSERT_SUBVECTOR: {
3456 if (VT.isSimple() && N1.getValueType().isSimple()
3457 && N2.getValueType().isSimple()) {
3458 assert(VT.isVector() && N1.getValueType().isVector() &&
3459 N2.getValueType().isVector() &&
3460 "Insert subvector VTs must be a vectors");
3461 assert(VT == N1.getValueType() &&
3462 "Dest and insert subvector source types must match!");
3463 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3464 "Insert subvector must be from smaller vector to larger vector!");
3465 if (isa<ConstantSDNode>(Index.getNode())) {
3466 assert((N2.getValueType().getVectorNumElements() +
3467 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3468 <= VT.getVectorNumElements())
3469 && "Insert subvector overflow!");
3472 // Trivial insertion.
3473 if (VT.getSimpleVT() == N2.getSimpleValueType())
3479 // Fold bit_convert nodes from a type to themselves.
3480 if (N1.getValueType() == VT)
3485 // Memoize node if it doesn't produce a flag.
3487 SDVTList VTs = getVTList(VT);
3488 if (VT != MVT::Glue) {
3489 SDValue Ops[] = { N1, N2, N3 };
3490 FoldingSetNodeID ID;
3491 AddNodeIDNode(ID, Opcode, VTs, Ops);
3493 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3494 return SDValue(E, 0);
3496 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3497 DL.getDebugLoc(), VTs, N1, N2, N3);
3498 CSEMap.InsertNode(N, IP);
3500 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3501 DL.getDebugLoc(), VTs, N1, N2, N3);
3504 AllNodes.push_back(N);
3508 return SDValue(N, 0);
3511 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3512 SDValue N1, SDValue N2, SDValue N3,
3514 SDValue Ops[] = { N1, N2, N3, N4 };
3515 return getNode(Opcode, DL, VT, Ops);
3518 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3519 SDValue N1, SDValue N2, SDValue N3,
3520 SDValue N4, SDValue N5) {
3521 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3522 return getNode(Opcode, DL, VT, Ops);
3525 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3526 /// the incoming stack arguments to be loaded from the stack.
3527 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3528 SmallVector<SDValue, 8> ArgChains;
3530 // Include the original chain at the beginning of the list. When this is
3531 // used by target LowerCall hooks, this helps legalize find the
3532 // CALLSEQ_BEGIN node.
3533 ArgChains.push_back(Chain);
3535 // Add a chain value for each stack argument.
3536 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3537 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3538 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3539 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3540 if (FI->getIndex() < 0)
3541 ArgChains.push_back(SDValue(L, 1));
3543 // Build a tokenfactor for all the chains.
3544 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3547 /// getMemsetValue - Vectorized representation of the memset value
3549 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3551 assert(Value.getOpcode() != ISD::UNDEF);
3553 unsigned NumBits = VT.getScalarType().getSizeInBits();
3554 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3555 assert(C->getAPIntValue().getBitWidth() == 8);
3556 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3558 return DAG.getConstant(Val, VT);
3559 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3562 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3564 // Use a multiplication with 0x010101... to extend the input to the
3566 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3567 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3573 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3574 /// used when a memcpy is turned into a memset when the source is a constant
3576 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3577 const TargetLowering &TLI, StringRef Str) {
3578 // Handle vector with all elements zero.
3581 return DAG.getConstant(0, VT);
3582 else if (VT == MVT::f32 || VT == MVT::f64)
3583 return DAG.getConstantFP(0.0, VT);
3584 else if (VT.isVector()) {
3585 unsigned NumElts = VT.getVectorNumElements();
3586 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3587 return DAG.getNode(ISD::BITCAST, dl, VT,
3588 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3591 llvm_unreachable("Expected type!");
3594 assert(!VT.isVector() && "Can't handle vector type here!");
3595 unsigned NumVTBits = VT.getSizeInBits();
3596 unsigned NumVTBytes = NumVTBits / 8;
3597 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3599 APInt Val(NumVTBits, 0);
3600 if (TLI.isLittleEndian()) {
3601 for (unsigned i = 0; i != NumBytes; ++i)
3602 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3604 for (unsigned i = 0; i != NumBytes; ++i)
3605 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3608 // If the "cost" of materializing the integer immediate is less than the cost
3609 // of a load, then it is cost effective to turn the load into the immediate.
3610 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3611 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3612 return DAG.getConstant(Val, VT);
3613 return SDValue(nullptr, 0);
3616 /// getMemBasePlusOffset - Returns base and offset node for the
3618 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3619 SelectionDAG &DAG) {
3620 EVT VT = Base.getValueType();
3621 return DAG.getNode(ISD::ADD, dl,
3622 VT, Base, DAG.getConstant(Offset, VT));
3625 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3627 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3628 unsigned SrcDelta = 0;
3629 GlobalAddressSDNode *G = nullptr;
3630 if (Src.getOpcode() == ISD::GlobalAddress)
3631 G = cast<GlobalAddressSDNode>(Src);
3632 else if (Src.getOpcode() == ISD::ADD &&
3633 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3634 Src.getOperand(1).getOpcode() == ISD::Constant) {
3635 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3636 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3641 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3644 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3645 /// to replace the memset / memcpy. Return true if the number of memory ops
3646 /// is below the threshold. It returns the types of the sequence of
3647 /// memory ops to perform memset / memcpy by reference.
3648 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3649 unsigned Limit, uint64_t Size,
3650 unsigned DstAlign, unsigned SrcAlign,
3656 const TargetLowering &TLI) {
3657 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3658 "Expecting memcpy / memset source to meet alignment requirement!");
3659 // If 'SrcAlign' is zero, that means the memory operation does not need to
3660 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3661 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3662 // is the specified alignment of the memory operation. If it is zero, that
3663 // means it's possible to change the alignment of the destination.
3664 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3665 // not need to be loaded.
3666 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3667 IsMemset, ZeroMemset, MemcpyStrSrc,
3668 DAG.getMachineFunction());
3670 if (VT == MVT::Other) {
3672 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3673 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3674 VT = TLI.getPointerTy();
3676 switch (DstAlign & 7) {
3677 case 0: VT = MVT::i64; break;
3678 case 4: VT = MVT::i32; break;
3679 case 2: VT = MVT::i16; break;
3680 default: VT = MVT::i8; break;
3685 while (!TLI.isTypeLegal(LVT))
3686 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3687 assert(LVT.isInteger());
3693 unsigned NumMemOps = 0;
3695 unsigned VTSize = VT.getSizeInBits() / 8;
3696 while (VTSize > Size) {
3697 // For now, only use non-vector load / store's for the left-over pieces.
3702 if (VT.isVector() || VT.isFloatingPoint()) {
3703 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3704 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3705 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3707 else if (NewVT == MVT::i64 &&
3708 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3709 TLI.isSafeMemOpType(MVT::f64)) {
3710 // i64 is usually not legal on 32-bit targets, but f64 may be.
3718 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3719 if (NewVT == MVT::i8)
3721 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3723 NewVTSize = NewVT.getSizeInBits() / 8;
3725 // If the new VT cannot cover all of the remaining bits, then consider
3726 // issuing a (or a pair of) unaligned and overlapping load / store.
3727 // FIXME: Only does this for 64-bit or more since we don't have proper
3728 // cost model for unaligned load / store.
3731 if (NumMemOps && AllowOverlap &&
3732 VTSize >= 8 && NewVTSize < Size &&
3733 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3741 if (++NumMemOps > Limit)
3744 MemOps.push_back(VT);
3751 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3752 SDValue Chain, SDValue Dst,
3753 SDValue Src, uint64_t Size,
3754 unsigned Align, bool isVol,
3756 MachinePointerInfo DstPtrInfo,
3757 MachinePointerInfo SrcPtrInfo) {
3758 // Turn a memcpy of undef to nop.
3759 if (Src.getOpcode() == ISD::UNDEF)
3762 // Expand memcpy to a series of load and store ops if the size operand falls
3763 // below a certain threshold.
3764 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3765 // rather than maybe a humongous number of loads and stores.
3766 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3767 std::vector<EVT> MemOps;
3768 bool DstAlignCanChange = false;
3769 MachineFunction &MF = DAG.getMachineFunction();
3770 MachineFrameInfo *MFI = MF.getFrameInfo();
3772 MF.getFunction()->getAttributes().
3773 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3774 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3775 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3776 DstAlignCanChange = true;
3777 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3778 if (Align > SrcAlign)
3781 bool CopyFromStr = isMemSrcFromString(Src, Str);
3782 bool isZeroStr = CopyFromStr && Str.empty();
3783 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3785 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3786 (DstAlignCanChange ? 0 : Align),
3787 (isZeroStr ? 0 : SrcAlign),
3788 false, false, CopyFromStr, true, DAG, TLI))
3791 if (DstAlignCanChange) {
3792 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3793 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3795 // Don't promote to an alignment that would require dynamic stack
3797 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3798 if (!TRI->needsStackRealignment(MF))
3799 while (NewAlign > Align &&
3800 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3803 if (NewAlign > Align) {
3804 // Give the stack frame object a larger alignment if needed.
3805 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3806 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3811 SmallVector<SDValue, 8> OutChains;
3812 unsigned NumMemOps = MemOps.size();
3813 uint64_t SrcOff = 0, DstOff = 0;
3814 for (unsigned i = 0; i != NumMemOps; ++i) {
3816 unsigned VTSize = VT.getSizeInBits() / 8;
3817 SDValue Value, Store;
3819 if (VTSize > Size) {
3820 // Issuing an unaligned load / store pair that overlaps with the previous
3821 // pair. Adjust the offset accordingly.
3822 assert(i == NumMemOps-1 && i != 0);
3823 SrcOff -= VTSize - Size;
3824 DstOff -= VTSize - Size;
3828 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3829 // It's unlikely a store of a vector immediate can be done in a single
3830 // instruction. It would require a load from a constantpool first.
3831 // We only handle zero vectors here.
3832 // FIXME: Handle other cases where store of vector immediate is done in
3833 // a single instruction.
3834 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3835 if (Value.getNode())
3836 Store = DAG.getStore(Chain, dl, Value,
3837 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3838 DstPtrInfo.getWithOffset(DstOff), isVol,
3842 if (!Store.getNode()) {
3843 // The type might not be legal for the target. This should only happen
3844 // if the type is smaller than a legal type, as on PPC, so the right
3845 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3846 // to Load/Store if NVT==VT.
3847 // FIXME does the case above also need this?
3848 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3849 assert(NVT.bitsGE(VT));
3850 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3851 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3852 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3853 MinAlign(SrcAlign, SrcOff));
3854 Store = DAG.getTruncStore(Chain, dl, Value,
3855 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3856 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3859 OutChains.push_back(Store);
3865 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3868 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3869 SDValue Chain, SDValue Dst,
3870 SDValue Src, uint64_t Size,
3871 unsigned Align, bool isVol,
3873 MachinePointerInfo DstPtrInfo,
3874 MachinePointerInfo SrcPtrInfo) {
3875 // Turn a memmove of undef to nop.
3876 if (Src.getOpcode() == ISD::UNDEF)
3879 // Expand memmove to a series of load and store ops if the size operand falls
3880 // below a certain threshold.
3881 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3882 std::vector<EVT> MemOps;
3883 bool DstAlignCanChange = false;
3884 MachineFunction &MF = DAG.getMachineFunction();
3885 MachineFrameInfo *MFI = MF.getFrameInfo();
3886 bool OptSize = MF.getFunction()->getAttributes().
3887 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3888 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3889 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3890 DstAlignCanChange = true;
3891 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3892 if (Align > SrcAlign)
3894 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3896 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3897 (DstAlignCanChange ? 0 : Align), SrcAlign,
3898 false, false, false, false, DAG, TLI))
3901 if (DstAlignCanChange) {
3902 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3903 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3904 if (NewAlign > Align) {
3905 // Give the stack frame object a larger alignment if needed.
3906 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3907 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3912 uint64_t SrcOff = 0, DstOff = 0;
3913 SmallVector<SDValue, 8> LoadValues;
3914 SmallVector<SDValue, 8> LoadChains;
3915 SmallVector<SDValue, 8> OutChains;
3916 unsigned NumMemOps = MemOps.size();
3917 for (unsigned i = 0; i < NumMemOps; i++) {
3919 unsigned VTSize = VT.getSizeInBits() / 8;
3922 Value = DAG.getLoad(VT, dl, Chain,
3923 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3924 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3925 false, false, SrcAlign);
3926 LoadValues.push_back(Value);
3927 LoadChains.push_back(Value.getValue(1));
3930 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3932 for (unsigned i = 0; i < NumMemOps; i++) {
3934 unsigned VTSize = VT.getSizeInBits() / 8;
3937 Store = DAG.getStore(Chain, dl, LoadValues[i],
3938 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3939 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3940 OutChains.push_back(Store);
3944 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3947 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3950 /// \param DAG Selection DAG where lowered code is placed.
3951 /// \param dl Link to corresponding IR location.
3952 /// \param Chain Control flow dependency.
3953 /// \param Dst Pointer to destination memory location.
3954 /// \param Src Value of byte to write into the memory.
3955 /// \param Size Number of bytes to write.
3956 /// \param Align Alignment of the destination in bytes.
3957 /// \param isVol True if destination is volatile.
3958 /// \param DstPtrInfo IR information on the memory pointer.
3959 /// \returns New head in the control flow, if lowering was successful, empty
3960 /// SDValue otherwise.
3962 /// The function tries to replace 'llvm.memset' intrinsic with several store
3963 /// operations and value calculation code. This is usually profitable for small
3965 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3966 SDValue Chain, SDValue Dst,
3967 SDValue Src, uint64_t Size,
3968 unsigned Align, bool isVol,
3969 MachinePointerInfo DstPtrInfo) {
3970 // Turn a memset of undef to nop.
3971 if (Src.getOpcode() == ISD::UNDEF)
3974 // Expand memset to a series of load/store ops if the size operand
3975 // falls below a certain threshold.
3976 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3977 std::vector<EVT> MemOps;
3978 bool DstAlignCanChange = false;
3979 MachineFunction &MF = DAG.getMachineFunction();
3980 MachineFrameInfo *MFI = MF.getFrameInfo();
3981 bool OptSize = MF.getFunction()->getAttributes().
3982 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3983 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3984 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3985 DstAlignCanChange = true;
3987 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3988 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3989 Size, (DstAlignCanChange ? 0 : Align), 0,
3990 true, IsZeroVal, false, true, DAG, TLI))
3993 if (DstAlignCanChange) {
3994 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3995 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3996 if (NewAlign > Align) {
3997 // Give the stack frame object a larger alignment if needed.
3998 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3999 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4004 SmallVector<SDValue, 8> OutChains;
4005 uint64_t DstOff = 0;
4006 unsigned NumMemOps = MemOps.size();
4008 // Find the largest store and generate the bit pattern for it.
4009 EVT LargestVT = MemOps[0];
4010 for (unsigned i = 1; i < NumMemOps; i++)
4011 if (MemOps[i].bitsGT(LargestVT))
4012 LargestVT = MemOps[i];
4013 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4015 for (unsigned i = 0; i < NumMemOps; i++) {
4017 unsigned VTSize = VT.getSizeInBits() / 8;
4018 if (VTSize > Size) {
4019 // Issuing an unaligned load / store pair that overlaps with the previous
4020 // pair. Adjust the offset accordingly.
4021 assert(i == NumMemOps-1 && i != 0);
4022 DstOff -= VTSize - Size;
4025 // If this store is smaller than the largest store see whether we can get
4026 // the smaller value for free with a truncate.
4027 SDValue Value = MemSetValue;
4028 if (VT.bitsLT(LargestVT)) {
4029 if (!LargestVT.isVector() && !VT.isVector() &&
4030 TLI.isTruncateFree(LargestVT, VT))
4031 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4033 Value = getMemsetValue(Src, VT, DAG, dl);
4035 assert(Value.getValueType() == VT && "Value with wrong type.");
4036 SDValue Store = DAG.getStore(Chain, dl, Value,
4037 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4038 DstPtrInfo.getWithOffset(DstOff),
4039 isVol, false, Align);
4040 OutChains.push_back(Store);
4041 DstOff += VT.getSizeInBits() / 8;
4045 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4048 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4049 SDValue Src, SDValue Size,
4050 unsigned Align, bool isVol, bool AlwaysInline,
4051 MachinePointerInfo DstPtrInfo,
4052 MachinePointerInfo SrcPtrInfo) {
4053 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4055 // Check to see if we should lower the memcpy to loads and stores first.
4056 // For cases within the target-specified limits, this is the best choice.
4057 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4059 // Memcpy with size zero? Just return the original chain.
4060 if (ConstantSize->isNullValue())
4063 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4064 ConstantSize->getZExtValue(),Align,
4065 isVol, false, DstPtrInfo, SrcPtrInfo);
4066 if (Result.getNode())
4070 // Then check to see if we should lower the memcpy with target-specific
4071 // code. If the target chooses to do this, this is the next best.
4073 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4074 isVol, AlwaysInline,
4075 DstPtrInfo, SrcPtrInfo);
4076 if (Result.getNode())
4079 // If we really need inline code and the target declined to provide it,
4080 // use a (potentially long) sequence of loads and stores.
4082 assert(ConstantSize && "AlwaysInline requires a constant size!");
4083 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4084 ConstantSize->getZExtValue(), Align, isVol,
4085 true, DstPtrInfo, SrcPtrInfo);
4088 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4089 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4090 // respect volatile, so they may do things like read or write memory
4091 // beyond the given memory regions. But fixing this isn't easy, and most
4092 // people don't care.
4094 const TargetLowering *TLI = TM.getTargetLowering();
4096 // Emit a library call.
4097 TargetLowering::ArgListTy Args;
4098 TargetLowering::ArgListEntry Entry;
4099 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4100 Entry.Node = Dst; Args.push_back(Entry);
4101 Entry.Node = Src; Args.push_back(Entry);
4102 Entry.Node = Size; Args.push_back(Entry);
4103 // FIXME: pass in SDLoc
4104 TargetLowering::CallLoweringInfo CLI(*this);
4105 CLI.setDebugLoc(dl).setChain(Chain)
4106 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4107 Type::getVoidTy(*getContext()),
4108 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4109 TLI->getPointerTy()), &Args, 0)
4110 .setDiscardResult();
4111 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4113 return CallResult.second;
4116 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4117 SDValue Src, SDValue Size,
4118 unsigned Align, bool isVol,
4119 MachinePointerInfo DstPtrInfo,
4120 MachinePointerInfo SrcPtrInfo) {
4121 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4123 // Check to see if we should lower the memmove to loads and stores first.
4124 // For cases within the target-specified limits, this is the best choice.
4125 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4127 // Memmove with size zero? Just return the original chain.
4128 if (ConstantSize->isNullValue())
4132 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4133 ConstantSize->getZExtValue(), Align, isVol,
4134 false, DstPtrInfo, SrcPtrInfo);
4135 if (Result.getNode())
4139 // Then check to see if we should lower the memmove with target-specific
4140 // code. If the target chooses to do this, this is the next best.
4142 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4143 DstPtrInfo, SrcPtrInfo);
4144 if (Result.getNode())
4147 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4148 // not be safe. See memcpy above for more details.
4150 const TargetLowering *TLI = TM.getTargetLowering();
4152 // Emit a library call.
4153 TargetLowering::ArgListTy Args;
4154 TargetLowering::ArgListEntry Entry;
4155 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4156 Entry.Node = Dst; Args.push_back(Entry);
4157 Entry.Node = Src; Args.push_back(Entry);
4158 Entry.Node = Size; Args.push_back(Entry);
4159 // FIXME: pass in SDLoc
4160 TargetLowering::CallLoweringInfo CLI(*this);
4161 CLI.setDebugLoc(dl).setChain(Chain)
4162 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4163 Type::getVoidTy(*getContext()),
4164 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4165 TLI->getPointerTy()), &Args, 0)
4166 .setDiscardResult();
4167 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4169 return CallResult.second;
4172 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4173 SDValue Src, SDValue Size,
4174 unsigned Align, bool isVol,
4175 MachinePointerInfo DstPtrInfo) {
4176 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4178 // Check to see if we should lower the memset to stores first.
4179 // For cases within the target-specified limits, this is the best choice.
4180 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4182 // Memset with size zero? Just return the original chain.
4183 if (ConstantSize->isNullValue())
4187 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4188 Align, isVol, DstPtrInfo);
4190 if (Result.getNode())
4194 // Then check to see if we should lower the memset with target-specific
4195 // code. If the target chooses to do this, this is the next best.
4197 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4199 if (Result.getNode())
4202 // Emit a library call.
4203 const TargetLowering *TLI = TM.getTargetLowering();
4204 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4205 TargetLowering::ArgListTy Args;
4206 TargetLowering::ArgListEntry Entry;
4207 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4208 Args.push_back(Entry);
4209 // Extend or truncate the argument to be an i32 value for the call.
4210 if (Src.getValueType().bitsGT(MVT::i32))
4211 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4213 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4215 Entry.Ty = Type::getInt32Ty(*getContext());
4216 Entry.isSExt = true;
4217 Args.push_back(Entry);
4219 Entry.Ty = IntPtrTy;
4220 Entry.isSExt = false;
4221 Args.push_back(Entry);
4223 // FIXME: pass in SDLoc
4224 TargetLowering::CallLoweringInfo CLI(*this);
4225 CLI.setDebugLoc(dl).setChain(Chain)
4226 .setCallee(TLI->getLibcallCallingConv(RTLIB::MEMSET),
4227 Type::getVoidTy(*getContext()),
4228 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4229 TLI->getPointerTy()), &Args, 0)
4230 .setDiscardResult();
4232 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4233 return CallResult.second;
4236 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4237 SDVTList VTList, ArrayRef<SDValue> Ops,
4238 MachineMemOperand *MMO,
4239 AtomicOrdering SuccessOrdering,
4240 AtomicOrdering FailureOrdering,
4241 SynchronizationScope SynchScope) {
4242 FoldingSetNodeID ID;
4243 ID.AddInteger(MemVT.getRawBits());
4244 AddNodeIDNode(ID, Opcode, VTList, Ops);
4245 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4247 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4248 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4249 return SDValue(E, 0);
4252 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4253 // SDNode doesn't have access to it. This memory will be "leaked" when
4254 // the node is deallocated, but recovered when the allocator is released.
4255 // If the number of operands is less than 5 we use AtomicSDNode's internal
4257 unsigned NumOps = Ops.size();
4258 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4261 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4262 dl.getDebugLoc(), VTList, MemVT,
4263 Ops.data(), DynOps, NumOps, MMO,
4264 SuccessOrdering, FailureOrdering,
4266 CSEMap.InsertNode(N, IP);
4267 AllNodes.push_back(N);
4268 return SDValue(N, 0);
4271 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4272 SDVTList VTList, ArrayRef<SDValue> Ops,
4273 MachineMemOperand *MMO,
4274 AtomicOrdering Ordering,
4275 SynchronizationScope SynchScope) {
4276 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4277 Ordering, SynchScope);
4280 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4281 SDValue Chain, SDValue Ptr, SDValue Cmp,
4282 SDValue Swp, MachinePointerInfo PtrInfo,
4284 AtomicOrdering SuccessOrdering,
4285 AtomicOrdering FailureOrdering,
4286 SynchronizationScope SynchScope) {
4287 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4288 Alignment = getEVTAlignment(MemVT);
4290 MachineFunction &MF = getMachineFunction();
4292 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4293 // For now, atomics are considered to be volatile always.
4294 // FIXME: Volatile isn't really correct; we should keep track of atomic
4295 // orderings in the memoperand.
4296 unsigned Flags = MachineMemOperand::MOVolatile;
4297 if (Opcode != ISD::ATOMIC_STORE)
4298 Flags |= MachineMemOperand::MOLoad;
4299 if (Opcode != ISD::ATOMIC_LOAD)
4300 Flags |= MachineMemOperand::MOStore;
4302 MachineMemOperand *MMO =
4303 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4305 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4306 SuccessOrdering, FailureOrdering, SynchScope);
4309 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4311 SDValue Ptr, SDValue Cmp,
4312 SDValue Swp, MachineMemOperand *MMO,
4313 AtomicOrdering SuccessOrdering,
4314 AtomicOrdering FailureOrdering,
4315 SynchronizationScope SynchScope) {
4316 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4317 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4319 EVT VT = Cmp.getValueType();
4321 SDVTList VTs = getVTList(VT, MVT::Other);
4322 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4323 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4324 FailureOrdering, SynchScope);
4327 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4329 SDValue Ptr, SDValue Val,
4330 const Value* PtrVal,
4332 AtomicOrdering Ordering,
4333 SynchronizationScope SynchScope) {
4334 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4335 Alignment = getEVTAlignment(MemVT);
4337 MachineFunction &MF = getMachineFunction();
4338 // An atomic store does not load. An atomic load does not store.
4339 // (An atomicrmw obviously both loads and stores.)
4340 // For now, atomics are considered to be volatile always, and they are
4342 // FIXME: Volatile isn't really correct; we should keep track of atomic
4343 // orderings in the memoperand.
4344 unsigned Flags = MachineMemOperand::MOVolatile;
4345 if (Opcode != ISD::ATOMIC_STORE)
4346 Flags |= MachineMemOperand::MOLoad;
4347 if (Opcode != ISD::ATOMIC_LOAD)
4348 Flags |= MachineMemOperand::MOStore;
4350 MachineMemOperand *MMO =
4351 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4352 MemVT.getStoreSize(), Alignment);
4354 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4355 Ordering, SynchScope);
4358 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4360 SDValue Ptr, SDValue Val,
4361 MachineMemOperand *MMO,
4362 AtomicOrdering Ordering,
4363 SynchronizationScope SynchScope) {
4364 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4365 Opcode == ISD::ATOMIC_LOAD_SUB ||
4366 Opcode == ISD::ATOMIC_LOAD_AND ||
4367 Opcode == ISD::ATOMIC_LOAD_OR ||
4368 Opcode == ISD::ATOMIC_LOAD_XOR ||
4369 Opcode == ISD::ATOMIC_LOAD_NAND ||
4370 Opcode == ISD::ATOMIC_LOAD_MIN ||
4371 Opcode == ISD::ATOMIC_LOAD_MAX ||
4372 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4373 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4374 Opcode == ISD::ATOMIC_SWAP ||
4375 Opcode == ISD::ATOMIC_STORE) &&
4376 "Invalid Atomic Op");
4378 EVT VT = Val.getValueType();
4380 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4381 getVTList(VT, MVT::Other);
4382 SDValue Ops[] = {Chain, Ptr, Val};
4383 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4386 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4387 EVT VT, SDValue Chain,
4389 MachineMemOperand *MMO,
4390 AtomicOrdering Ordering,
4391 SynchronizationScope SynchScope) {
4392 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4394 SDVTList VTs = getVTList(VT, MVT::Other);
4395 SDValue Ops[] = {Chain, Ptr};
4396 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4399 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4400 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4401 if (Ops.size() == 1)
4404 SmallVector<EVT, 4> VTs;
4405 VTs.reserve(Ops.size());
4406 for (unsigned i = 0; i < Ops.size(); ++i)
4407 VTs.push_back(Ops[i].getValueType());
4408 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4412 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4413 ArrayRef<SDValue> Ops,
4414 EVT MemVT, MachinePointerInfo PtrInfo,
4415 unsigned Align, bool Vol,
4416 bool ReadMem, bool WriteMem) {
4417 if (Align == 0) // Ensure that codegen never sees alignment 0
4418 Align = getEVTAlignment(MemVT);
4420 MachineFunction &MF = getMachineFunction();
4423 Flags |= MachineMemOperand::MOStore;
4425 Flags |= MachineMemOperand::MOLoad;
4427 Flags |= MachineMemOperand::MOVolatile;
4428 MachineMemOperand *MMO =
4429 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4431 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4435 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4436 ArrayRef<SDValue> Ops, EVT MemVT,
4437 MachineMemOperand *MMO) {
4438 assert((Opcode == ISD::INTRINSIC_VOID ||
4439 Opcode == ISD::INTRINSIC_W_CHAIN ||
4440 Opcode == ISD::PREFETCH ||
4441 Opcode == ISD::LIFETIME_START ||
4442 Opcode == ISD::LIFETIME_END ||
4443 (Opcode <= INT_MAX &&
4444 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4445 "Opcode is not a memory-accessing opcode!");
4447 // Memoize the node unless it returns a flag.
4448 MemIntrinsicSDNode *N;
4449 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4450 FoldingSetNodeID ID;
4451 AddNodeIDNode(ID, Opcode, VTList, Ops);
4452 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4454 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4455 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4456 return SDValue(E, 0);
4459 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4460 dl.getDebugLoc(), VTList, Ops,
4462 CSEMap.InsertNode(N, IP);
4464 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4465 dl.getDebugLoc(), VTList, Ops,
4468 AllNodes.push_back(N);
4469 return SDValue(N, 0);
4472 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4473 /// MachinePointerInfo record from it. This is particularly useful because the
4474 /// code generator has many cases where it doesn't bother passing in a
4475 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4476 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4477 // If this is FI+Offset, we can model it.
4478 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4479 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4481 // If this is (FI+Offset1)+Offset2, we can model it.
4482 if (Ptr.getOpcode() != ISD::ADD ||
4483 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4484 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4485 return MachinePointerInfo();
4487 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4488 return MachinePointerInfo::getFixedStack(FI, Offset+
4489 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4492 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4493 /// MachinePointerInfo record from it. This is particularly useful because the
4494 /// code generator has many cases where it doesn't bother passing in a
4495 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4496 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4497 // If the 'Offset' value isn't a constant, we can't handle this.
4498 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4499 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4500 if (OffsetOp.getOpcode() == ISD::UNDEF)
4501 return InferPointerInfo(Ptr);
4502 return MachinePointerInfo();
4507 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4508 EVT VT, SDLoc dl, SDValue Chain,
4509 SDValue Ptr, SDValue Offset,
4510 MachinePointerInfo PtrInfo, EVT MemVT,
4511 bool isVolatile, bool isNonTemporal, bool isInvariant,
4512 unsigned Alignment, const MDNode *TBAAInfo,
4513 const MDNode *Ranges) {
4514 assert(Chain.getValueType() == MVT::Other &&
4515 "Invalid chain type");
4516 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4517 Alignment = getEVTAlignment(VT);
4519 unsigned Flags = MachineMemOperand::MOLoad;
4521 Flags |= MachineMemOperand::MOVolatile;
4523 Flags |= MachineMemOperand::MONonTemporal;
4525 Flags |= MachineMemOperand::MOInvariant;
4527 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4529 if (PtrInfo.V.isNull())
4530 PtrInfo = InferPointerInfo(Ptr, Offset);
4532 MachineFunction &MF = getMachineFunction();
4533 MachineMemOperand *MMO =
4534 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4536 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4540 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4541 EVT VT, SDLoc dl, SDValue Chain,
4542 SDValue Ptr, SDValue Offset, EVT MemVT,
4543 MachineMemOperand *MMO) {
4545 ExtType = ISD::NON_EXTLOAD;
4546 } else if (ExtType == ISD::NON_EXTLOAD) {
4547 assert(VT == MemVT && "Non-extending load from different memory type!");
4550 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4551 "Should only be an extending load, not truncating!");
4552 assert(VT.isInteger() == MemVT.isInteger() &&
4553 "Cannot convert from FP to Int or Int -> FP!");
4554 assert(VT.isVector() == MemVT.isVector() &&
4555 "Cannot use trunc store to convert to or from a vector!");
4556 assert((!VT.isVector() ||
4557 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4558 "Cannot use trunc store to change the number of vector elements!");
4561 bool Indexed = AM != ISD::UNINDEXED;
4562 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4563 "Unindexed load with an offset!");
4565 SDVTList VTs = Indexed ?
4566 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4567 SDValue Ops[] = { Chain, Ptr, Offset };
4568 FoldingSetNodeID ID;
4569 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4570 ID.AddInteger(MemVT.getRawBits());
4571 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4572 MMO->isNonTemporal(),
4573 MMO->isInvariant()));
4574 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4576 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4577 cast<LoadSDNode>(E)->refineAlignment(MMO);
4578 return SDValue(E, 0);
4580 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4581 dl.getDebugLoc(), VTs, AM, ExtType,
4583 CSEMap.InsertNode(N, IP);
4584 AllNodes.push_back(N);
4585 return SDValue(N, 0);
4588 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4589 SDValue Chain, SDValue Ptr,
4590 MachinePointerInfo PtrInfo,
4591 bool isVolatile, bool isNonTemporal,
4592 bool isInvariant, unsigned Alignment,
4593 const MDNode *TBAAInfo,
4594 const MDNode *Ranges) {
4595 SDValue Undef = getUNDEF(Ptr.getValueType());
4596 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4597 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4601 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4602 SDValue Chain, SDValue Ptr,
4603 MachineMemOperand *MMO) {
4604 SDValue Undef = getUNDEF(Ptr.getValueType());
4605 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4609 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4610 SDValue Chain, SDValue Ptr,
4611 MachinePointerInfo PtrInfo, EVT MemVT,
4612 bool isVolatile, bool isNonTemporal,
4613 unsigned Alignment, const MDNode *TBAAInfo) {
4614 SDValue Undef = getUNDEF(Ptr.getValueType());
4615 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4616 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4621 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4622 SDValue Chain, SDValue Ptr, EVT MemVT,
4623 MachineMemOperand *MMO) {
4624 SDValue Undef = getUNDEF(Ptr.getValueType());
4625 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4630 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4631 SDValue Offset, ISD::MemIndexedMode AM) {
4632 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4633 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4634 "Load is already a indexed load!");
4635 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4636 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4637 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4638 false, LD->getAlignment());
4641 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4642 SDValue Ptr, MachinePointerInfo PtrInfo,
4643 bool isVolatile, bool isNonTemporal,
4644 unsigned Alignment, const MDNode *TBAAInfo) {
4645 assert(Chain.getValueType() == MVT::Other &&
4646 "Invalid chain type");
4647 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4648 Alignment = getEVTAlignment(Val.getValueType());
4650 unsigned Flags = MachineMemOperand::MOStore;
4652 Flags |= MachineMemOperand::MOVolatile;
4654 Flags |= MachineMemOperand::MONonTemporal;
4656 if (PtrInfo.V.isNull())
4657 PtrInfo = InferPointerInfo(Ptr);
4659 MachineFunction &MF = getMachineFunction();
4660 MachineMemOperand *MMO =
4661 MF.getMachineMemOperand(PtrInfo, Flags,
4662 Val.getValueType().getStoreSize(), Alignment,
4665 return getStore(Chain, dl, Val, Ptr, MMO);
4668 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4669 SDValue Ptr, MachineMemOperand *MMO) {
4670 assert(Chain.getValueType() == MVT::Other &&
4671 "Invalid chain type");
4672 EVT VT = Val.getValueType();
4673 SDVTList VTs = getVTList(MVT::Other);
4674 SDValue Undef = getUNDEF(Ptr.getValueType());
4675 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4676 FoldingSetNodeID ID;
4677 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4678 ID.AddInteger(VT.getRawBits());
4679 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4680 MMO->isNonTemporal(), MMO->isInvariant()));
4681 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4683 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4684 cast<StoreSDNode>(E)->refineAlignment(MMO);
4685 return SDValue(E, 0);
4687 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4688 dl.getDebugLoc(), VTs,
4689 ISD::UNINDEXED, false, VT, MMO);
4690 CSEMap.InsertNode(N, IP);
4691 AllNodes.push_back(N);
4692 return SDValue(N, 0);
4695 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4696 SDValue Ptr, MachinePointerInfo PtrInfo,
4697 EVT SVT,bool isVolatile, bool isNonTemporal,
4699 const MDNode *TBAAInfo) {
4700 assert(Chain.getValueType() == MVT::Other &&
4701 "Invalid chain type");
4702 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4703 Alignment = getEVTAlignment(SVT);
4705 unsigned Flags = MachineMemOperand::MOStore;
4707 Flags |= MachineMemOperand::MOVolatile;
4709 Flags |= MachineMemOperand::MONonTemporal;
4711 if (PtrInfo.V.isNull())
4712 PtrInfo = InferPointerInfo(Ptr);
4714 MachineFunction &MF = getMachineFunction();
4715 MachineMemOperand *MMO =
4716 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4719 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4722 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4723 SDValue Ptr, EVT SVT,
4724 MachineMemOperand *MMO) {
4725 EVT VT = Val.getValueType();
4727 assert(Chain.getValueType() == MVT::Other &&
4728 "Invalid chain type");
4730 return getStore(Chain, dl, Val, Ptr, MMO);
4732 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4733 "Should only be a truncating store, not extending!");
4734 assert(VT.isInteger() == SVT.isInteger() &&
4735 "Can't do FP-INT conversion!");
4736 assert(VT.isVector() == SVT.isVector() &&
4737 "Cannot use trunc store to convert to or from a vector!");
4738 assert((!VT.isVector() ||
4739 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4740 "Cannot use trunc store to change the number of vector elements!");
4742 SDVTList VTs = getVTList(MVT::Other);
4743 SDValue Undef = getUNDEF(Ptr.getValueType());
4744 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4745 FoldingSetNodeID ID;
4746 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4747 ID.AddInteger(SVT.getRawBits());
4748 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4749 MMO->isNonTemporal(), MMO->isInvariant()));
4750 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4752 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4753 cast<StoreSDNode>(E)->refineAlignment(MMO);
4754 return SDValue(E, 0);
4756 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4757 dl.getDebugLoc(), VTs,
4758 ISD::UNINDEXED, true, SVT, MMO);
4759 CSEMap.InsertNode(N, IP);
4760 AllNodes.push_back(N);
4761 return SDValue(N, 0);
4765 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4766 SDValue Offset, ISD::MemIndexedMode AM) {
4767 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4768 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4769 "Store is already a indexed store!");
4770 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4771 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4772 FoldingSetNodeID ID;
4773 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4774 ID.AddInteger(ST->getMemoryVT().getRawBits());
4775 ID.AddInteger(ST->getRawSubclassData());
4776 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4778 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4779 return SDValue(E, 0);
4781 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4782 dl.getDebugLoc(), VTs, AM,
4783 ST->isTruncatingStore(),
4785 ST->getMemOperand());
4786 CSEMap.InsertNode(N, IP);
4787 AllNodes.push_back(N);
4788 return SDValue(N, 0);
4791 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4792 SDValue Chain, SDValue Ptr,
4795 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4796 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4799 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4800 ArrayRef<SDUse> Ops) {
4801 switch (Ops.size()) {
4802 case 0: return getNode(Opcode, DL, VT);
4803 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4804 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4805 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4809 // Copy from an SDUse array into an SDValue array for use with
4810 // the regular getNode logic.
4811 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4812 return getNode(Opcode, DL, VT, NewOps);
4815 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4816 ArrayRef<SDValue> Ops) {
4817 unsigned NumOps = Ops.size();
4819 case 0: return getNode(Opcode, DL, VT);
4820 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4821 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4822 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4828 case ISD::SELECT_CC: {
4829 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4830 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4831 "LHS and RHS of condition must have same type!");
4832 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4833 "True and False arms of SelectCC must have same type!");
4834 assert(Ops[2].getValueType() == VT &&
4835 "select_cc node must be of same type as true and false value!");
4839 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4840 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4841 "LHS/RHS of comparison should match types!");
4848 SDVTList VTs = getVTList(VT);
4850 if (VT != MVT::Glue) {
4851 FoldingSetNodeID ID;
4852 AddNodeIDNode(ID, Opcode, VTs, Ops);
4855 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4856 return SDValue(E, 0);
4858 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4860 CSEMap.InsertNode(N, IP);
4862 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4866 AllNodes.push_back(N);
4870 return SDValue(N, 0);
4873 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4874 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4875 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4878 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4879 ArrayRef<SDValue> Ops) {
4880 if (VTList.NumVTs == 1)
4881 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4885 // FIXME: figure out how to safely handle things like
4886 // int foo(int x) { return 1 << (x & 255); }
4887 // int bar() { return foo(256); }
4888 case ISD::SRA_PARTS:
4889 case ISD::SRL_PARTS:
4890 case ISD::SHL_PARTS:
4891 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4892 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4893 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4894 else if (N3.getOpcode() == ISD::AND)
4895 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4896 // If the and is only masking out bits that cannot effect the shift,
4897 // eliminate the and.
4898 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4899 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4900 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4906 // Memoize the node unless it returns a flag.
4908 unsigned NumOps = Ops.size();
4909 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4910 FoldingSetNodeID ID;
4911 AddNodeIDNode(ID, Opcode, VTList, Ops);
4913 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4914 return SDValue(E, 0);
4917 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4918 DL.getDebugLoc(), VTList, Ops[0]);
4919 } else if (NumOps == 2) {
4920 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4921 DL.getDebugLoc(), VTList, Ops[0],
4923 } else if (NumOps == 3) {
4924 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4925 DL.getDebugLoc(), VTList, Ops[0],
4928 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4931 CSEMap.InsertNode(N, IP);
4934 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4935 DL.getDebugLoc(), VTList, Ops[0]);
4936 } else if (NumOps == 2) {
4937 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4938 DL.getDebugLoc(), VTList, Ops[0],
4940 } else if (NumOps == 3) {
4941 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4942 DL.getDebugLoc(), VTList, Ops[0],
4945 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4949 AllNodes.push_back(N);
4953 return SDValue(N, 0);
4956 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4957 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4960 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4962 SDValue Ops[] = { N1 };
4963 return getNode(Opcode, DL, VTList, Ops);
4966 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4967 SDValue N1, SDValue N2) {
4968 SDValue Ops[] = { N1, N2 };
4969 return getNode(Opcode, DL, VTList, Ops);
4972 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4973 SDValue N1, SDValue N2, SDValue N3) {
4974 SDValue Ops[] = { N1, N2, N3 };
4975 return getNode(Opcode, DL, VTList, Ops);
4978 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4979 SDValue N1, SDValue N2, SDValue N3,
4981 SDValue Ops[] = { N1, N2, N3, N4 };
4982 return getNode(Opcode, DL, VTList, Ops);
4985 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4986 SDValue N1, SDValue N2, SDValue N3,
4987 SDValue N4, SDValue N5) {
4988 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4989 return getNode(Opcode, DL, VTList, Ops);
4992 SDVTList SelectionDAG::getVTList(EVT VT) {
4993 return makeVTList(SDNode::getValueTypeList(VT), 1);
4996 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4997 FoldingSetNodeID ID;
4999 ID.AddInteger(VT1.getRawBits());
5000 ID.AddInteger(VT2.getRawBits());
5003 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5005 EVT *Array = Allocator.Allocate<EVT>(2);
5008 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5009 VTListMap.InsertNode(Result, IP);
5011 return Result->getSDVTList();
5014 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5015 FoldingSetNodeID ID;
5017 ID.AddInteger(VT1.getRawBits());
5018 ID.AddInteger(VT2.getRawBits());
5019 ID.AddInteger(VT3.getRawBits());
5022 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5024 EVT *Array = Allocator.Allocate<EVT>(3);
5028 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5029 VTListMap.InsertNode(Result, IP);
5031 return Result->getSDVTList();
5034 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5035 FoldingSetNodeID ID;
5037 ID.AddInteger(VT1.getRawBits());
5038 ID.AddInteger(VT2.getRawBits());
5039 ID.AddInteger(VT3.getRawBits());
5040 ID.AddInteger(VT4.getRawBits());
5043 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5045 EVT *Array = Allocator.Allocate<EVT>(4);
5050 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5051 VTListMap.InsertNode(Result, IP);
5053 return Result->getSDVTList();
5056 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5057 unsigned NumVTs = VTs.size();
5058 FoldingSetNodeID ID;
5059 ID.AddInteger(NumVTs);
5060 for (unsigned index = 0; index < NumVTs; index++) {
5061 ID.AddInteger(VTs[index].getRawBits());
5065 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5067 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5068 std::copy(VTs.begin(), VTs.end(), Array);
5069 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5070 VTListMap.InsertNode(Result, IP);
5072 return Result->getSDVTList();
5076 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5077 /// specified operands. If the resultant node already exists in the DAG,
5078 /// this does not modify the specified node, instead it returns the node that
5079 /// already exists. If the resultant node does not exist in the DAG, the
5080 /// input node is returned. As a degenerate case, if you specify the same
5081 /// input operands as the node already has, the input node is returned.
5082 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5083 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5085 // Check to see if there is no change.
5086 if (Op == N->getOperand(0)) return N;
5088 // See if the modified node already exists.
5089 void *InsertPos = nullptr;
5090 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5093 // Nope it doesn't. Remove the node from its current place in the maps.
5095 if (!RemoveNodeFromCSEMaps(N))
5096 InsertPos = nullptr;
5098 // Now we update the operands.
5099 N->OperandList[0].set(Op);
5101 // If this gets put into a CSE map, add it.
5102 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5106 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5107 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5109 // Check to see if there is no change.
5110 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5111 return N; // No operands changed, just return the input node.
5113 // See if the modified node already exists.
5114 void *InsertPos = nullptr;
5115 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5118 // Nope it doesn't. Remove the node from its current place in the maps.
5120 if (!RemoveNodeFromCSEMaps(N))
5121 InsertPos = nullptr;
5123 // Now we update the operands.
5124 if (N->OperandList[0] != Op1)
5125 N->OperandList[0].set(Op1);
5126 if (N->OperandList[1] != Op2)
5127 N->OperandList[1].set(Op2);
5129 // If this gets put into a CSE map, add it.
5130 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5134 SDNode *SelectionDAG::
5135 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5136 SDValue Ops[] = { Op1, Op2, Op3 };
5137 return UpdateNodeOperands(N, Ops);
5140 SDNode *SelectionDAG::
5141 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5142 SDValue Op3, SDValue Op4) {
5143 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5144 return UpdateNodeOperands(N, Ops);
5147 SDNode *SelectionDAG::
5148 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5149 SDValue Op3, SDValue Op4, SDValue Op5) {
5150 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5151 return UpdateNodeOperands(N, Ops);
5154 SDNode *SelectionDAG::
5155 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5156 unsigned NumOps = Ops.size();
5157 assert(N->getNumOperands() == NumOps &&
5158 "Update with wrong number of operands");
5160 // Check to see if there is no change.
5161 bool AnyChange = false;
5162 for (unsigned i = 0; i != NumOps; ++i) {
5163 if (Ops[i] != N->getOperand(i)) {
5169 // No operands changed, just return the input node.
5170 if (!AnyChange) return N;
5172 // See if the modified node already exists.
5173 void *InsertPos = nullptr;
5174 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5177 // Nope it doesn't. Remove the node from its current place in the maps.
5179 if (!RemoveNodeFromCSEMaps(N))
5180 InsertPos = nullptr;
5182 // Now we update the operands.
5183 for (unsigned i = 0; i != NumOps; ++i)
5184 if (N->OperandList[i] != Ops[i])
5185 N->OperandList[i].set(Ops[i]);
5187 // If this gets put into a CSE map, add it.
5188 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5192 /// DropOperands - Release the operands and set this node to have
5194 void SDNode::DropOperands() {
5195 // Unlike the code in MorphNodeTo that does this, we don't need to
5196 // watch for dead nodes here.
5197 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5203 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5206 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5208 SDVTList VTs = getVTList(VT);
5209 return SelectNodeTo(N, MachineOpc, VTs, None);
5212 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5213 EVT VT, SDValue Op1) {
5214 SDVTList VTs = getVTList(VT);
5215 SDValue Ops[] = { Op1 };
5216 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5219 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5220 EVT VT, SDValue Op1,
5222 SDVTList VTs = getVTList(VT);
5223 SDValue Ops[] = { Op1, Op2 };
5224 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5227 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5228 EVT VT, SDValue Op1,
5229 SDValue Op2, SDValue Op3) {
5230 SDVTList VTs = getVTList(VT);
5231 SDValue Ops[] = { Op1, Op2, Op3 };
5232 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5235 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5236 EVT VT, ArrayRef<SDValue> Ops) {
5237 SDVTList VTs = getVTList(VT);
5238 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5241 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5242 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5243 SDVTList VTs = getVTList(VT1, VT2);
5244 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5247 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5249 SDVTList VTs = getVTList(VT1, VT2);
5250 return SelectNodeTo(N, MachineOpc, VTs, None);
5253 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5254 EVT VT1, EVT VT2, EVT VT3,
5255 ArrayRef<SDValue> Ops) {
5256 SDVTList VTs = getVTList(VT1, VT2, VT3);
5257 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5260 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5261 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5262 ArrayRef<SDValue> Ops) {
5263 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5264 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5267 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5270 SDVTList VTs = getVTList(VT1, VT2);
5271 SDValue Ops[] = { Op1 };
5272 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5275 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5277 SDValue Op1, SDValue Op2) {
5278 SDVTList VTs = getVTList(VT1, VT2);
5279 SDValue Ops[] = { Op1, Op2 };
5280 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5283 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5285 SDValue Op1, SDValue Op2,
5287 SDVTList VTs = getVTList(VT1, VT2);
5288 SDValue Ops[] = { Op1, Op2, Op3 };
5289 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5292 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5293 EVT VT1, EVT VT2, EVT VT3,
5294 SDValue Op1, SDValue Op2,
5296 SDVTList VTs = getVTList(VT1, VT2, VT3);
5297 SDValue Ops[] = { Op1, Op2, Op3 };
5298 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5301 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5302 SDVTList VTs,ArrayRef<SDValue> Ops) {
5303 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5304 // Reset the NodeID to -1.
5309 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5310 /// the line number information on the merged node since it is not possible to
5311 /// preserve the information that operation is associated with multiple lines.
5312 /// This will make the debugger working better at -O0, were there is a higher
5313 /// probability having other instructions associated with that line.
5315 /// For IROrder, we keep the smaller of the two
5316 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5317 DebugLoc NLoc = N->getDebugLoc();
5318 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5319 (OLoc.getDebugLoc() != NLoc)) {
5320 N->setDebugLoc(DebugLoc());
5322 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5323 N->setIROrder(Order);
5327 /// MorphNodeTo - This *mutates* the specified node to have the specified
5328 /// return type, opcode, and operands.
5330 /// Note that MorphNodeTo returns the resultant node. If there is already a
5331 /// node of the specified opcode and operands, it returns that node instead of
5332 /// the current one. Note that the SDLoc need not be the same.
5334 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5335 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5336 /// node, and because it doesn't require CSE recalculation for any of
5337 /// the node's users.
5339 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5340 SDVTList VTs, ArrayRef<SDValue> Ops) {
5341 unsigned NumOps = Ops.size();
5342 // If an identical node already exists, use it.
5344 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5345 FoldingSetNodeID ID;
5346 AddNodeIDNode(ID, Opc, VTs, Ops);
5347 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5348 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5351 if (!RemoveNodeFromCSEMaps(N))
5354 // Start the morphing.
5356 N->ValueList = VTs.VTs;
5357 N->NumValues = VTs.NumVTs;
5359 // Clear the operands list, updating used nodes to remove this from their
5360 // use list. Keep track of any operands that become dead as a result.
5361 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5362 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5364 SDNode *Used = Use.getNode();
5366 if (Used->use_empty())
5367 DeadNodeSet.insert(Used);
5370 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5371 // Initialize the memory references information.
5372 MN->setMemRefs(nullptr, nullptr);
5373 // If NumOps is larger than the # of operands we can have in a
5374 // MachineSDNode, reallocate the operand list.
5375 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5376 if (MN->OperandsNeedDelete)
5377 delete[] MN->OperandList;
5378 if (NumOps > array_lengthof(MN->LocalOperands))
5379 // We're creating a final node that will live unmorphed for the
5380 // remainder of the current SelectionDAG iteration, so we can allocate
5381 // the operands directly out of a pool with no recycling metadata.
5382 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5383 Ops.data(), NumOps);
5385 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5386 MN->OperandsNeedDelete = false;
5388 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5390 // If NumOps is larger than the # of operands we currently have, reallocate
5391 // the operand list.
5392 if (NumOps > N->NumOperands) {
5393 if (N->OperandsNeedDelete)
5394 delete[] N->OperandList;
5395 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5396 N->OperandsNeedDelete = true;
5398 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5401 // Delete any nodes that are still dead after adding the uses for the
5403 if (!DeadNodeSet.empty()) {
5404 SmallVector<SDNode *, 16> DeadNodes;
5405 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5406 E = DeadNodeSet.end(); I != E; ++I)
5407 if ((*I)->use_empty())
5408 DeadNodes.push_back(*I);
5409 RemoveDeadNodes(DeadNodes);
5413 CSEMap.InsertNode(N, IP); // Memoize the new node.
5418 /// getMachineNode - These are used for target selectors to create a new node
5419 /// with specified return type(s), MachineInstr opcode, and operands.
5421 /// Note that getMachineNode returns the resultant node. If there is already a
5422 /// node of the specified opcode and operands, it returns that node instead of
5423 /// the current one.
5425 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5426 SDVTList VTs = getVTList(VT);
5427 return getMachineNode(Opcode, dl, VTs, None);
5431 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5432 SDVTList VTs = getVTList(VT);
5433 SDValue Ops[] = { Op1 };
5434 return getMachineNode(Opcode, dl, VTs, Ops);
5438 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5439 SDValue Op1, SDValue Op2) {
5440 SDVTList VTs = getVTList(VT);
5441 SDValue Ops[] = { Op1, Op2 };
5442 return getMachineNode(Opcode, dl, VTs, Ops);
5446 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5447 SDValue Op1, SDValue Op2, SDValue Op3) {
5448 SDVTList VTs = getVTList(VT);
5449 SDValue Ops[] = { Op1, Op2, Op3 };
5450 return getMachineNode(Opcode, dl, VTs, Ops);
5454 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5455 ArrayRef<SDValue> Ops) {
5456 SDVTList VTs = getVTList(VT);
5457 return getMachineNode(Opcode, dl, VTs, Ops);
5461 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5462 SDVTList VTs = getVTList(VT1, VT2);
5463 return getMachineNode(Opcode, dl, VTs, None);
5467 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5468 EVT VT1, EVT VT2, SDValue Op1) {
5469 SDVTList VTs = getVTList(VT1, VT2);
5470 SDValue Ops[] = { Op1 };
5471 return getMachineNode(Opcode, dl, VTs, Ops);
5475 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5476 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5477 SDVTList VTs = getVTList(VT1, VT2);
5478 SDValue Ops[] = { Op1, Op2 };
5479 return getMachineNode(Opcode, dl, VTs, Ops);
5483 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5484 EVT VT1, EVT VT2, SDValue Op1,
5485 SDValue Op2, SDValue Op3) {
5486 SDVTList VTs = getVTList(VT1, VT2);
5487 SDValue Ops[] = { Op1, Op2, Op3 };
5488 return getMachineNode(Opcode, dl, VTs, Ops);
5492 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5494 ArrayRef<SDValue> Ops) {
5495 SDVTList VTs = getVTList(VT1, VT2);
5496 return getMachineNode(Opcode, dl, VTs, Ops);
5500 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5501 EVT VT1, EVT VT2, EVT VT3,
5502 SDValue Op1, SDValue Op2) {
5503 SDVTList VTs = getVTList(VT1, VT2, VT3);
5504 SDValue Ops[] = { Op1, Op2 };
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, SDValue Op3) {
5512 SDVTList VTs = getVTList(VT1, VT2, VT3);
5513 SDValue Ops[] = { Op1, Op2, Op3 };
5514 return getMachineNode(Opcode, dl, VTs, Ops);
5518 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5519 EVT VT1, EVT VT2, EVT VT3,
5520 ArrayRef<SDValue> Ops) {
5521 SDVTList VTs = getVTList(VT1, VT2, VT3);
5522 return getMachineNode(Opcode, dl, VTs, Ops);
5526 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5527 EVT VT2, EVT VT3, EVT VT4,
5528 ArrayRef<SDValue> Ops) {
5529 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5530 return getMachineNode(Opcode, dl, VTs, Ops);
5534 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5535 ArrayRef<EVT> ResultTys,
5536 ArrayRef<SDValue> Ops) {
5537 SDVTList VTs = getVTList(ResultTys);
5538 return getMachineNode(Opcode, dl, VTs, Ops);
5542 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5543 ArrayRef<SDValue> OpsArray) {
5544 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5547 const SDValue *Ops = OpsArray.data();
5548 unsigned NumOps = OpsArray.size();
5551 FoldingSetNodeID ID;
5552 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5555 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5559 // Allocate a new MachineSDNode.
5560 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5561 DL.getDebugLoc(), VTs);
5563 // Initialize the operands list.
5564 if (NumOps > array_lengthof(N->LocalOperands))
5565 // We're creating a final node that will live unmorphed for the
5566 // remainder of the current SelectionDAG iteration, so we can allocate
5567 // the operands directly out of a pool with no recycling metadata.
5568 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5571 N->InitOperands(N->LocalOperands, Ops, NumOps);
5572 N->OperandsNeedDelete = false;
5575 CSEMap.InsertNode(N, IP);
5577 AllNodes.push_back(N);
5579 VerifyMachineNode(N);
5584 /// getTargetExtractSubreg - A convenience function for creating
5585 /// TargetOpcode::EXTRACT_SUBREG nodes.
5587 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5589 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5590 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5591 VT, Operand, SRIdxVal);
5592 return SDValue(Subreg, 0);
5595 /// getTargetInsertSubreg - A convenience function for creating
5596 /// TargetOpcode::INSERT_SUBREG nodes.
5598 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5599 SDValue Operand, SDValue Subreg) {
5600 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5601 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5602 VT, Operand, Subreg, SRIdxVal);
5603 return SDValue(Result, 0);
5606 /// getNodeIfExists - Get the specified node if it's already available, or
5607 /// else return NULL.
5608 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5609 ArrayRef<SDValue> Ops) {
5610 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5611 FoldingSetNodeID ID;
5612 AddNodeIDNode(ID, Opcode, VTList, Ops);
5614 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5620 /// getDbgValue - Creates a SDDbgValue node.
5624 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5625 bool IsIndirect, uint64_t Off,
5626 DebugLoc DL, unsigned O) {
5627 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5632 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5634 DebugLoc DL, unsigned O) {
5635 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5640 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5641 DebugLoc DL, unsigned O) {
5642 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5647 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5648 /// pointed to by a use iterator is deleted, increment the use iterator
5649 /// so that it doesn't dangle.
5651 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5652 SDNode::use_iterator &UI;
5653 SDNode::use_iterator &UE;
5655 void NodeDeleted(SDNode *N, SDNode *E) override {
5656 // Increment the iterator as needed.
5657 while (UI != UE && N == *UI)
5662 RAUWUpdateListener(SelectionDAG &d,
5663 SDNode::use_iterator &ui,
5664 SDNode::use_iterator &ue)
5665 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5670 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5671 /// This can cause recursive merging of nodes in the DAG.
5673 /// This version assumes From has a single result value.
5675 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5676 SDNode *From = FromN.getNode();
5677 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5678 "Cannot replace with this method!");
5679 assert(From != To.getNode() && "Cannot replace uses of with self");
5681 // Iterate over all the existing uses of From. New uses will be added
5682 // to the beginning of the use list, which we avoid visiting.
5683 // This specifically avoids visiting uses of From that arise while the
5684 // replacement is happening, because any such uses would be the result
5685 // of CSE: If an existing node looks like From after one of its operands
5686 // is replaced by To, we don't want to replace of all its users with To
5687 // too. See PR3018 for more info.
5688 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5689 RAUWUpdateListener Listener(*this, UI, UE);
5693 // This node is about to morph, remove its old self from the CSE maps.
5694 RemoveNodeFromCSEMaps(User);
5696 // A user can appear in a use list multiple times, and when this
5697 // happens the uses are usually next to each other in the list.
5698 // To help reduce the number of CSE recomputations, process all
5699 // the uses of this user that we can find this way.
5701 SDUse &Use = UI.getUse();
5704 } while (UI != UE && *UI == User);
5706 // Now that we have modified User, add it back to the CSE maps. If it
5707 // already exists there, recursively merge the results together.
5708 AddModifiedNodeToCSEMaps(User);
5711 // If we just RAUW'd the root, take note.
5712 if (FromN == getRoot())
5716 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5717 /// This can cause recursive merging of nodes in the DAG.
5719 /// This version assumes that for each value of From, there is a
5720 /// corresponding value in To in the same position with the same type.
5722 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5724 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5725 assert((!From->hasAnyUseOfValue(i) ||
5726 From->getValueType(i) == To->getValueType(i)) &&
5727 "Cannot use this version of ReplaceAllUsesWith!");
5730 // Handle the trivial case.
5734 // Iterate over just the existing users of From. See the comments in
5735 // the ReplaceAllUsesWith above.
5736 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5737 RAUWUpdateListener Listener(*this, UI, UE);
5741 // This node is about to morph, remove its old self from the CSE maps.
5742 RemoveNodeFromCSEMaps(User);
5744 // A user can appear in a use list multiple times, and when this
5745 // happens the uses are usually next to each other in the list.
5746 // To help reduce the number of CSE recomputations, process all
5747 // the uses of this user that we can find this way.
5749 SDUse &Use = UI.getUse();
5752 } while (UI != UE && *UI == User);
5754 // Now that we have modified User, add it back to the CSE maps. If it
5755 // already exists there, recursively merge the results together.
5756 AddModifiedNodeToCSEMaps(User);
5759 // If we just RAUW'd the root, take note.
5760 if (From == getRoot().getNode())
5761 setRoot(SDValue(To, getRoot().getResNo()));
5764 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5765 /// This can cause recursive merging of nodes in the DAG.
5767 /// This version can replace From with any result values. To must match the
5768 /// number and types of values returned by From.
5769 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5770 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5771 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5773 // Iterate over just the existing users of From. See the comments in
5774 // the ReplaceAllUsesWith above.
5775 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5776 RAUWUpdateListener Listener(*this, UI, UE);
5780 // This node is about to morph, remove its old self from the CSE maps.
5781 RemoveNodeFromCSEMaps(User);
5783 // A user can appear in a use list multiple times, and when this
5784 // happens the uses are usually next to each other in the list.
5785 // To help reduce the number of CSE recomputations, process all
5786 // the uses of this user that we can find this way.
5788 SDUse &Use = UI.getUse();
5789 const SDValue &ToOp = To[Use.getResNo()];
5792 } while (UI != UE && *UI == User);
5794 // Now that we have modified User, add it back to the CSE maps. If it
5795 // already exists there, recursively merge the results together.
5796 AddModifiedNodeToCSEMaps(User);
5799 // If we just RAUW'd the root, take note.
5800 if (From == getRoot().getNode())
5801 setRoot(SDValue(To[getRoot().getResNo()]));
5804 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5805 /// uses of other values produced by From.getNode() alone. The Deleted
5806 /// vector is handled the same way as for ReplaceAllUsesWith.
5807 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5808 // Handle the really simple, really trivial case efficiently.
5809 if (From == To) return;
5811 // Handle the simple, trivial, case efficiently.
5812 if (From.getNode()->getNumValues() == 1) {
5813 ReplaceAllUsesWith(From, To);
5817 // Iterate over just the existing users of From. See the comments in
5818 // the ReplaceAllUsesWith above.
5819 SDNode::use_iterator UI = From.getNode()->use_begin(),
5820 UE = From.getNode()->use_end();
5821 RAUWUpdateListener Listener(*this, UI, UE);
5824 bool UserRemovedFromCSEMaps = false;
5826 // A user can appear in a use list multiple times, and when this
5827 // happens the uses are usually next to each other in the list.
5828 // To help reduce the number of CSE recomputations, process all
5829 // the uses of this user that we can find this way.
5831 SDUse &Use = UI.getUse();
5833 // Skip uses of different values from the same node.
5834 if (Use.getResNo() != From.getResNo()) {
5839 // If this node hasn't been modified yet, it's still in the CSE maps,
5840 // so remove its old self from the CSE maps.
5841 if (!UserRemovedFromCSEMaps) {
5842 RemoveNodeFromCSEMaps(User);
5843 UserRemovedFromCSEMaps = true;
5848 } while (UI != UE && *UI == User);
5850 // We are iterating over all uses of the From node, so if a use
5851 // doesn't use the specific value, no changes are made.
5852 if (!UserRemovedFromCSEMaps)
5855 // Now that we have modified User, add it back to the CSE maps. If it
5856 // already exists there, recursively merge the results together.
5857 AddModifiedNodeToCSEMaps(User);
5860 // If we just RAUW'd the root, take note.
5861 if (From == getRoot())
5866 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5867 /// to record information about a use.
5874 /// operator< - Sort Memos by User.
5875 bool operator<(const UseMemo &L, const UseMemo &R) {
5876 return (intptr_t)L.User < (intptr_t)R.User;
5880 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5881 /// uses of other values produced by From.getNode() alone. The same value
5882 /// may appear in both the From and To list. The Deleted vector is
5883 /// handled the same way as for ReplaceAllUsesWith.
5884 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5887 // Handle the simple, trivial case efficiently.
5889 return ReplaceAllUsesOfValueWith(*From, *To);
5891 // Read up all the uses and make records of them. This helps
5892 // processing new uses that are introduced during the
5893 // replacement process.
5894 SmallVector<UseMemo, 4> Uses;
5895 for (unsigned i = 0; i != Num; ++i) {
5896 unsigned FromResNo = From[i].getResNo();
5897 SDNode *FromNode = From[i].getNode();
5898 for (SDNode::use_iterator UI = FromNode->use_begin(),
5899 E = FromNode->use_end(); UI != E; ++UI) {
5900 SDUse &Use = UI.getUse();
5901 if (Use.getResNo() == FromResNo) {
5902 UseMemo Memo = { *UI, i, &Use };
5903 Uses.push_back(Memo);
5908 // Sort the uses, so that all the uses from a given User are together.
5909 std::sort(Uses.begin(), Uses.end());
5911 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5912 UseIndex != UseIndexEnd; ) {
5913 // We know that this user uses some value of From. If it is the right
5914 // value, update it.
5915 SDNode *User = Uses[UseIndex].User;
5917 // This node is about to morph, remove its old self from the CSE maps.
5918 RemoveNodeFromCSEMaps(User);
5920 // The Uses array is sorted, so all the uses for a given User
5921 // are next to each other in the list.
5922 // To help reduce the number of CSE recomputations, process all
5923 // the uses of this user that we can find this way.
5925 unsigned i = Uses[UseIndex].Index;
5926 SDUse &Use = *Uses[UseIndex].Use;
5930 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5932 // Now that we have modified User, add it back to the CSE maps. If it
5933 // already exists there, recursively merge the results together.
5934 AddModifiedNodeToCSEMaps(User);
5938 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5939 /// based on their topological order. It returns the maximum id and a vector
5940 /// of the SDNodes* in assigned order by reference.
5941 unsigned SelectionDAG::AssignTopologicalOrder() {
5943 unsigned DAGSize = 0;
5945 // SortedPos tracks the progress of the algorithm. Nodes before it are
5946 // sorted, nodes after it are unsorted. When the algorithm completes
5947 // it is at the end of the list.
5948 allnodes_iterator SortedPos = allnodes_begin();
5950 // Visit all the nodes. Move nodes with no operands to the front of
5951 // the list immediately. Annotate nodes that do have operands with their
5952 // operand count. Before we do this, the Node Id fields of the nodes
5953 // may contain arbitrary values. After, the Node Id fields for nodes
5954 // before SortedPos will contain the topological sort index, and the
5955 // Node Id fields for nodes At SortedPos and after will contain the
5956 // count of outstanding operands.
5957 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5959 checkForCycles(N, this);
5960 unsigned Degree = N->getNumOperands();
5962 // A node with no uses, add it to the result array immediately.
5963 N->setNodeId(DAGSize++);
5964 allnodes_iterator Q = N;
5966 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5967 assert(SortedPos != AllNodes.end() && "Overran node list");
5970 // Temporarily use the Node Id as scratch space for the degree count.
5971 N->setNodeId(Degree);
5975 // Visit all the nodes. As we iterate, move nodes into sorted order,
5976 // such that by the time the end is reached all nodes will be sorted.
5977 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5979 checkForCycles(N, this);
5980 // N is in sorted position, so all its uses have one less operand
5981 // that needs to be sorted.
5982 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5985 unsigned Degree = P->getNodeId();
5986 assert(Degree != 0 && "Invalid node degree");
5989 // All of P's operands are sorted, so P may sorted now.
5990 P->setNodeId(DAGSize++);
5992 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5993 assert(SortedPos != AllNodes.end() && "Overran node list");
5996 // Update P's outstanding operand count.
5997 P->setNodeId(Degree);
6000 if (I == SortedPos) {
6003 dbgs() << "Overran sorted position:\n";
6004 S->dumprFull(this); dbgs() << "\n";
6005 dbgs() << "Checking if this is due to cycles\n";
6006 checkForCycles(this, true);
6008 llvm_unreachable(nullptr);
6012 assert(SortedPos == AllNodes.end() &&
6013 "Topological sort incomplete!");
6014 assert(AllNodes.front().getOpcode() == ISD::EntryToken &&
6015 "First node in topological sort is not the entry token!");
6016 assert(AllNodes.front().getNodeId() == 0 &&
6017 "First node in topological sort has non-zero id!");
6018 assert(AllNodes.front().getNumOperands() == 0 &&
6019 "First node in topological sort has operands!");
6020 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 &&
6021 "Last node in topologic sort has unexpected id!");
6022 assert(AllNodes.back().use_empty() &&
6023 "Last node in topologic sort has users!");
6024 assert(DAGSize == allnodes_size() && "Node count mismatch!");
6028 /// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the
6029 /// value is produced by SD.
6030 void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) {
6031 DbgInfo->add(DB, SD, isParameter);
6033 SD->setHasDebugValue(true);
6036 /// TransferDbgValues - Transfer SDDbgValues.
6037 void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) {
6038 if (From == To || !From.getNode()->getHasDebugValue())
6040 SDNode *FromNode = From.getNode();
6041 SDNode *ToNode = To.getNode();
6042 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode);
6043 SmallVector<SDDbgValue *, 2> ClonedDVs;
6044 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end();
6046 SDDbgValue *Dbg = *I;
6047 if (Dbg->getKind() == SDDbgValue::SDNODE) {
6048 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(),
6050 Dbg->getOffset(), Dbg->getDebugLoc(),
6052 ClonedDVs.push_back(Clone);
6055 for (SmallVectorImpl<SDDbgValue *>::iterator I = ClonedDVs.begin(),
6056 E = ClonedDVs.end(); I != E; ++I)
6057 AddDbgValue(*I, ToNode, false);
6060 //===----------------------------------------------------------------------===//
6062 //===----------------------------------------------------------------------===//
6064 HandleSDNode::~HandleSDNode() {
6068 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, unsigned Order,
6069 DebugLoc DL, const GlobalValue *GA,
6070 EVT VT, int64_t o, unsigned char TF)
6071 : SDNode(Opc, Order, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) {
6075 AddrSpaceCastSDNode::AddrSpaceCastSDNode(unsigned Order, DebugLoc dl, EVT VT,
6076 SDValue X, unsigned SrcAS,
6078 : UnarySDNode(ISD::ADDRSPACECAST, Order, dl, getSDVTList(VT), X),
6079 SrcAddrSpace(SrcAS), DestAddrSpace(DestAS) {}
6081 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6082 EVT memvt, MachineMemOperand *mmo)
6083 : SDNode(Opc, Order, dl, VTs), MemoryVT(memvt), MMO(mmo) {
6084 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6085 MMO->isNonTemporal(), MMO->isInvariant());
6086 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6087 assert(isNonTemporal() == MMO->isNonTemporal() &&
6088 "Non-temporal encoding error!");
6089 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6092 MemSDNode::MemSDNode(unsigned Opc, unsigned Order, DebugLoc dl, SDVTList VTs,
6093 ArrayRef<SDValue> Ops, EVT memvt, MachineMemOperand *mmo)
6094 : SDNode(Opc, Order, dl, VTs, Ops),
6095 MemoryVT(memvt), MMO(mmo) {
6096 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(),
6097 MMO->isNonTemporal(), MMO->isInvariant());
6098 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!");
6099 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!");
6102 /// Profile - Gather unique data for the node.
6104 void SDNode::Profile(FoldingSetNodeID &ID) const {
6105 AddNodeIDNode(ID, this);
6110 std::vector<EVT> VTs;
6113 VTs.reserve(MVT::LAST_VALUETYPE);
6114 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i)
6115 VTs.push_back(MVT((MVT::SimpleValueType)i));
6120 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs;
6121 static ManagedStatic<EVTArray> SimpleVTArray;
6122 static ManagedStatic<sys::SmartMutex<true> > VTMutex;
6124 /// getValueTypeList - Return a pointer to the specified value type.
6126 const EVT *SDNode::getValueTypeList(EVT VT) {
6127 if (VT.isExtended()) {
6128 sys::SmartScopedLock<true> Lock(*VTMutex);
6129 return &(*EVTs->insert(VT).first);
6131 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE &&
6132 "Value type out of range!");
6133 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy];
6137 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
6138 /// indicated value. This method ignores uses of other values defined by this
6140 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
6141 assert(Value < getNumValues() && "Bad value!");
6143 // TODO: Only iterate over uses of a given value of the node
6144 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
6145 if (UI.getUse().getResNo() == Value) {
6152 // Found exactly the right number of uses?
6157 /// hasAnyUseOfValue - Return true if there are any use of the indicated
6158 /// value. This method ignores uses of other values defined by this operation.
6159 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
6160 assert(Value < getNumValues() && "Bad value!");
6162 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI)
6163 if (UI.getUse().getResNo() == Value)
6170 /// isOnlyUserOf - Return true if this node is the only use of N.
6172 bool SDNode::isOnlyUserOf(SDNode *N) const {
6174 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
6185 /// isOperand - Return true if this node is an operand of N.
6187 bool SDValue::isOperandOf(SDNode *N) const {
6188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6189 if (*this == N->getOperand(i))
6194 bool SDNode::isOperandOf(SDNode *N) const {
6195 for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
6196 if (this == N->OperandList[i].getNode())
6201 /// reachesChainWithoutSideEffects - Return true if this operand (which must
6202 /// be a chain) reaches the specified operand without crossing any
6203 /// side-effecting instructions on any chain path. In practice, this looks
6204 /// through token factors and non-volatile loads. In order to remain efficient,
6205 /// this only looks a couple of nodes in, it does not do an exhaustive search.
6206 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest,
6207 unsigned Depth) const {
6208 if (*this == Dest) return true;
6210 // Don't search too deeply, we just want to be able to see through
6211 // TokenFactor's etc.
6212 if (Depth == 0) return false;
6214 // If this is a token factor, all inputs to the TF happen in parallel. If any
6215 // of the operands of the TF does not reach dest, then we cannot do the xform.
6216 if (getOpcode() == ISD::TokenFactor) {
6217 for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
6218 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
6223 // Loads don't have side effects, look through them.
6224 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
6225 if (!Ld->isVolatile())
6226 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
6231 /// hasPredecessor - Return true if N is a predecessor of this node.
6232 /// N is either an operand of this node, or can be reached by recursively
6233 /// traversing up the operands.
6234 /// NOTE: This is an expensive method. Use it carefully.
6235 bool SDNode::hasPredecessor(const SDNode *N) const {
6236 SmallPtrSet<const SDNode *, 32> Visited;
6237 SmallVector<const SDNode *, 16> Worklist;
6238 return hasPredecessorHelper(N, Visited, Worklist);
6242 SDNode::hasPredecessorHelper(const SDNode *N,
6243 SmallPtrSet<const SDNode *, 32> &Visited,
6244 SmallVectorImpl<const SDNode *> &Worklist) const {
6245 if (Visited.empty()) {
6246 Worklist.push_back(this);
6248 // Take a look in the visited set. If we've already encountered this node
6249 // we needn't search further.
6250 if (Visited.count(N))
6254 // Haven't visited N yet. Continue the search.
6255 while (!Worklist.empty()) {
6256 const SDNode *M = Worklist.pop_back_val();
6257 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) {
6258 SDNode *Op = M->getOperand(i).getNode();
6259 if (Visited.insert(Op))
6260 Worklist.push_back(Op);
6269 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
6270 assert(Num < NumOperands && "Invalid child # of SDNode!");
6271 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue();
6274 SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) {
6275 assert(N->getNumValues() == 1 &&
6276 "Can't unroll a vector with multiple results!");
6278 EVT VT = N->getValueType(0);
6279 unsigned NE = VT.getVectorNumElements();
6280 EVT EltVT = VT.getVectorElementType();
6283 SmallVector<SDValue, 8> Scalars;
6284 SmallVector<SDValue, 4> Operands(N->getNumOperands());
6286 // If ResNE is 0, fully unroll the vector op.
6289 else if (NE > ResNE)
6293 for (i= 0; i != NE; ++i) {
6294 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) {
6295 SDValue Operand = N->getOperand(j);
6296 EVT OperandVT = Operand.getValueType();
6297 if (OperandVT.isVector()) {
6298 // A vector operand; extract a single element.
6299 const TargetLowering *TLI = TM.getTargetLowering();
6300 EVT OperandEltVT = OperandVT.getVectorElementType();
6301 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl,
6304 getConstant(i, TLI->getVectorIdxTy()));
6306 // A scalar operand; just use it as is.
6307 Operands[j] = Operand;
6311 switch (N->getOpcode()) {
6313 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands));
6316 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, Operands));
6323 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0],
6324 getShiftAmountOperand(Operands[0].getValueType(),
6327 case ISD::SIGN_EXTEND_INREG:
6328 case ISD::FP_ROUND_INREG: {
6329 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType();
6330 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT,
6332 getValueType(ExtVT)));
6337 for (; i < ResNE; ++i)
6338 Scalars.push_back(getUNDEF(EltVT));
6340 return getNode(ISD::BUILD_VECTOR, dl,
6341 EVT::getVectorVT(*getContext(), EltVT, ResNE), Scalars);
6345 /// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a
6346 /// location that is 'Dist' units away from the location that the 'Base' load
6347 /// is loading from.
6348 bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base,
6349 unsigned Bytes, int Dist) const {
6350 if (LD->getChain() != Base->getChain())
6352 EVT VT = LD->getValueType(0);
6353 if (VT.getSizeInBits() / 8 != Bytes)
6356 SDValue Loc = LD->getOperand(1);
6357 SDValue BaseLoc = Base->getOperand(1);
6358 if (Loc.getOpcode() == ISD::FrameIndex) {
6359 if (BaseLoc.getOpcode() != ISD::FrameIndex)
6361 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo();
6362 int FI = cast<FrameIndexSDNode>(Loc)->getIndex();
6363 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex();
6364 int FS = MFI->getObjectSize(FI);
6365 int BFS = MFI->getObjectSize(BFI);
6366 if (FS != BFS || FS != (int)Bytes) return false;
6367 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes);
6371 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc &&
6372 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes)
6375 const GlobalValue *GV1 = nullptr;
6376 const GlobalValue *GV2 = nullptr;
6377 int64_t Offset1 = 0;
6378 int64_t Offset2 = 0;
6379 const TargetLowering *TLI = TM.getTargetLowering();
6380 bool isGA1 = TLI->isGAPlusOffset(Loc.getNode(), GV1, Offset1);
6381 bool isGA2 = TLI->isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2);
6382 if (isGA1 && isGA2 && GV1 == GV2)
6383 return Offset1 == (Offset2 + Dist*Bytes);
6388 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if
6389 /// it cannot be inferred.
6390 unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const {
6391 // If this is a GlobalAddress + cst, return the alignment.
6392 const GlobalValue *GV;
6393 int64_t GVOffset = 0;
6394 const TargetLowering *TLI = TM.getTargetLowering();
6395 if (TLI->isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) {
6396 unsigned PtrWidth = TLI->getPointerTypeSizeInBits(GV->getType());
6397 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0);
6398 llvm::computeKnownBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne,
6399 TLI->getDataLayout());
6400 unsigned AlignBits = KnownZero.countTrailingOnes();
6401 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0;
6403 return MinAlign(Align, GVOffset);
6406 // If this is a direct reference to a stack slot, use information about the
6407 // stack slot's alignment.
6408 int FrameIdx = 1 << 31;
6409 int64_t FrameOffset = 0;
6410 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) {
6411 FrameIdx = FI->getIndex();
6412 } else if (isBaseWithConstantOffset(Ptr) &&
6413 isa<FrameIndexSDNode>(Ptr.getOperand(0))) {
6415 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
6416 FrameOffset = Ptr.getConstantOperandVal(1);
6419 if (FrameIdx != (1 << 31)) {
6420 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo();
6421 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx),
6429 /// GetSplitDestVTs - Compute the VTs needed for the low/hi parts of a type
6430 /// which is split (or expanded) into two not necessarily identical pieces.
6431 std::pair<EVT, EVT> SelectionDAG::GetSplitDestVTs(const EVT &VT) const {
6432 // Currently all types are split in half.
6434 if (!VT.isVector()) {
6435 LoVT = HiVT = TLI->getTypeToTransformTo(*getContext(), VT);
6437 unsigned NumElements = VT.getVectorNumElements();
6438 assert(!(NumElements & 1) && "Splitting vector, but not in half!");
6439 LoVT = HiVT = EVT::getVectorVT(*getContext(), VT.getVectorElementType(),
6442 return std::make_pair(LoVT, HiVT);
6445 /// SplitVector - Split the vector with EXTRACT_SUBVECTOR and return the
6447 std::pair<SDValue, SDValue>
6448 SelectionDAG::SplitVector(const SDValue &N, const SDLoc &DL, const EVT &LoVT,
6450 assert(LoVT.getVectorNumElements() + HiVT.getVectorNumElements() <=
6451 N.getValueType().getVectorNumElements() &&
6452 "More vector elements requested than available!");
6454 Lo = getNode(ISD::EXTRACT_SUBVECTOR, DL, LoVT, N,
6455 getConstant(0, TLI->getVectorIdxTy()));
6456 Hi = getNode(ISD::EXTRACT_SUBVECTOR, DL, HiVT, N,
6457 getConstant(LoVT.getVectorNumElements(), TLI->getVectorIdxTy()));
6458 return std::make_pair(Lo, Hi);
6461 void SelectionDAG::ExtractVectorElements(SDValue Op,
6462 SmallVectorImpl<SDValue> &Args,
6463 unsigned Start, unsigned Count) {
6464 EVT VT = Op.getValueType();
6466 Count = VT.getVectorNumElements();
6468 EVT EltVT = VT.getVectorElementType();
6469 EVT IdxTy = TLI->getVectorIdxTy();
6471 for (unsigned i = Start, e = Start + Count; i != e; ++i) {
6472 Args.push_back(getNode(ISD::EXTRACT_VECTOR_ELT, SL, EltVT,
6473 Op, getConstant(i, IdxTy)));
6477 // getAddressSpace - Return the address space this GlobalAddress belongs to.
6478 unsigned GlobalAddressSDNode::getAddressSpace() const {
6479 return getGlobal()->getType()->getAddressSpace();
6483 Type *ConstantPoolSDNode::getType() const {
6484 if (isMachineConstantPoolEntry())
6485 return Val.MachineCPVal->getType();
6486 return Val.ConstVal->getType();
6489 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue,
6491 unsigned &SplatBitSize,
6493 unsigned MinSplatBits,
6494 bool isBigEndian) const {
6495 EVT VT = getValueType(0);
6496 assert(VT.isVector() && "Expected a vector type");
6497 unsigned sz = VT.getSizeInBits();
6498 if (MinSplatBits > sz)
6501 SplatValue = APInt(sz, 0);
6502 SplatUndef = APInt(sz, 0);
6504 // Get the bits. Bits with undefined values (when the corresponding element
6505 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared
6506 // in SplatValue. If any of the values are not constant, give up and return
6508 unsigned int nOps = getNumOperands();
6509 assert(nOps > 0 && "isConstantSplat has 0-size build vector");
6510 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits();
6512 for (unsigned j = 0; j < nOps; ++j) {
6513 unsigned i = isBigEndian ? nOps-1-j : j;
6514 SDValue OpVal = getOperand(i);
6515 unsigned BitPos = j * EltBitSize;
6517 if (OpVal.getOpcode() == ISD::UNDEF)
6518 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize);
6519 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal))
6520 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize).
6521 zextOrTrunc(sz) << BitPos;
6522 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal))
6523 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos;
6528 // The build_vector is all constants or undefs. Find the smallest element
6529 // size that splats the vector.
6531 HasAnyUndefs = (SplatUndef != 0);
6534 unsigned HalfSize = sz / 2;
6535 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize);
6536 APInt LowValue = SplatValue.trunc(HalfSize);
6537 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize);
6538 APInt LowUndef = SplatUndef.trunc(HalfSize);
6540 // If the two halves do not match (ignoring undef bits), stop here.
6541 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) ||
6542 MinSplatBits > HalfSize)
6545 SplatValue = HighValue | LowValue;
6546 SplatUndef = HighUndef & LowUndef;
6555 ConstantSDNode *BuildVectorSDNode::getConstantSplatValue() const {
6556 SDValue Op0 = getOperand(0);
6557 if (Op0.getOpcode() != ISD::Constant)
6560 for (unsigned i = 1, e = getNumOperands(); i != e; ++i)
6561 if (getOperand(i) != Op0)
6564 return cast<ConstantSDNode>(Op0);
6567 bool BuildVectorSDNode::isConstant() const {
6568 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
6569 unsigned Opc = getOperand(i).getOpcode();
6570 if (Opc != ISD::UNDEF && Opc != ISD::Constant && Opc != ISD::ConstantFP)
6576 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) {
6577 // Find the first non-undef value in the shuffle mask.
6579 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i)
6582 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!");
6584 // Make sure all remaining elements are either undef or the same as the first
6586 for (int Idx = Mask[i]; i != e; ++i)
6587 if (Mask[i] >= 0 && Mask[i] != Idx)
6593 static void checkForCyclesHelper(const SDNode *N,
6594 SmallPtrSet<const SDNode*, 32> &Visited,
6595 SmallPtrSet<const SDNode*, 32> &Checked,
6596 const llvm::SelectionDAG *DAG) {
6597 // If this node has already been checked, don't check it again.
6598 if (Checked.count(N))
6601 // If a node has already been visited on this depth-first walk, reject it as
6603 if (!Visited.insert(N)) {
6604 errs() << "Detected cycle in SelectionDAG\n";
6605 dbgs() << "Offending node:\n";
6606 N->dumprFull(DAG); dbgs() << "\n";
6610 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6611 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked, DAG);
6618 void llvm::checkForCycles(const llvm::SDNode *N,
6619 const llvm::SelectionDAG *DAG,
6627 assert(N && "Checking nonexistent SDNode");
6628 SmallPtrSet<const SDNode*, 32> visited;
6629 SmallPtrSet<const SDNode*, 32> checked;
6630 checkForCyclesHelper(N, visited, checked, DAG);
6635 void llvm::checkForCycles(const llvm::SelectionDAG *DAG, bool force) {
6636 checkForCycles(DAG->getRoot().getNode(), DAG, force);