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::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
967 assert(!VT.isVector() &&
968 "getZeroExtendInReg should use the vector element type instead of "
970 if (Op.getValueType() == VT) return Op;
971 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
972 APInt Imm = APInt::getLowBitsSet(BitWidth,
974 return getNode(ISD::AND, DL, Op.getValueType(), Op,
975 getConstant(Imm, Op.getValueType()));
978 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
980 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
981 EVT EltVT = VT.getScalarType();
983 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
984 return getNode(ISD::XOR, DL, VT, Val, NegOne);
987 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) {
988 EVT EltVT = VT.getScalarType();
989 assert((EltVT.getSizeInBits() >= 64 ||
990 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) &&
991 "getConstant with a uint64_t value that doesn't fit in the type!");
992 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO);
995 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO)
997 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO);
1000 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT,
1002 assert(VT.isInteger() && "Cannot create FP integer constant!");
1004 EVT EltVT = VT.getScalarType();
1005 const ConstantInt *Elt = &Val;
1007 const TargetLowering *TLI = TM.getTargetLowering();
1009 // In some cases the vector type is legal but the element type is illegal and
1010 // needs to be promoted, for example v8i8 on ARM. In this case, promote the
1011 // inserted value (the type does not need to match the vector element type).
1012 // Any extra bits introduced will be truncated away.
1013 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) ==
1014 TargetLowering::TypePromoteInteger) {
1015 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1016 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits());
1017 Elt = ConstantInt::get(*getContext(), NewVal);
1019 // In other cases the element type is illegal and needs to be expanded, for
1020 // example v2i64 on MIPS32. In this case, find the nearest legal type, split
1021 // the value into n parts and use a vector type with n-times the elements.
1022 // Then bitcast to the type requested.
1023 // Legalizing constants too early makes the DAGCombiner's job harder so we
1024 // only legalize if the DAG tells us we must produce legal types.
1025 else if (NewNodesMustHaveLegalTypes && VT.isVector() &&
1026 TLI->getTypeAction(*getContext(), EltVT) ==
1027 TargetLowering::TypeExpandInteger) {
1028 APInt NewVal = Elt->getValue();
1029 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT);
1030 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits();
1031 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits;
1032 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts);
1034 // Check the temporary vector is the correct size. If this fails then
1035 // getTypeToTransformTo() probably returned a type whose size (in bits)
1036 // isn't a power-of-2 factor of the requested type size.
1037 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits());
1039 SmallVector<SDValue, 2> EltParts;
1040 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) {
1041 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits)
1042 .trunc(ViaEltSizeInBits),
1043 ViaEltVT, isT, isO));
1046 // EltParts is currently in little endian order. If we actually want
1047 // big-endian order then reverse it now.
1048 if (TLI->isBigEndian())
1049 std::reverse(EltParts.begin(), EltParts.end());
1051 // The elements must be reversed when the element order is different
1052 // to the endianness of the elements (because the BITCAST is itself a
1053 // vector shuffle in this situation). However, we do not need any code to
1054 // perform this reversal because getConstant() is producing a vector
1056 // This situation occurs in MIPS MSA.
1058 SmallVector<SDValue, 8> Ops;
1059 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i)
1060 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end());
1062 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT,
1063 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT,
1068 assert(Elt->getBitWidth() == EltVT.getSizeInBits() &&
1069 "APInt size does not match type size!");
1070 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
1071 FoldingSetNodeID ID;
1072 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1076 SDNode *N = nullptr;
1077 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1079 return SDValue(N, 0);
1082 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT);
1083 CSEMap.InsertNode(N, IP);
1084 AllNodes.push_back(N);
1087 SDValue Result(N, 0);
1088 if (VT.isVector()) {
1089 SmallVector<SDValue, 8> Ops;
1090 Ops.assign(VT.getVectorNumElements(), Result);
1091 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1096 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
1097 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget);
1101 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) {
1102 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget);
1105 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){
1106 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!");
1108 EVT EltVT = VT.getScalarType();
1110 // Do the map lookup using the actual bit pattern for the floating point
1111 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
1112 // we don't have issues with SNANs.
1113 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
1114 FoldingSetNodeID ID;
1115 AddNodeIDNode(ID, Opc, getVTList(EltVT), None);
1118 SDNode *N = nullptr;
1119 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
1121 return SDValue(N, 0);
1124 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT);
1125 CSEMap.InsertNode(N, IP);
1126 AllNodes.push_back(N);
1129 SDValue Result(N, 0);
1130 if (VT.isVector()) {
1131 SmallVector<SDValue, 8> Ops;
1132 Ops.assign(VT.getVectorNumElements(), Result);
1133 // FIXME SDLoc info might be appropriate here
1134 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops);
1139 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) {
1140 EVT EltVT = VT.getScalarType();
1141 if (EltVT==MVT::f32)
1142 return getConstantFP(APFloat((float)Val), VT, isTarget);
1143 else if (EltVT==MVT::f64)
1144 return getConstantFP(APFloat(Val), VT, isTarget);
1145 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 ||
1148 APFloat apf = APFloat(Val);
1149 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven,
1151 return getConstantFP(apf, VT, isTarget);
1153 llvm_unreachable("Unsupported type in getConstantFP");
1156 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL,
1157 EVT VT, int64_t Offset,
1159 unsigned char TargetFlags) {
1160 assert((TargetFlags == 0 || isTargetGA) &&
1161 "Cannot set target flags on target-independent globals");
1162 const TargetLowering *TLI = TM.getTargetLowering();
1164 // Truncate (with sign-extension) the offset value to the pointer size.
1165 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType());
1167 Offset = SignExtend64(Offset, BitWidth);
1169 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
1171 // If GV is an alias then use the aliasee for determining thread-localness.
1172 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
1173 GVar = dyn_cast_or_null<GlobalVariable>(GA->getAliasedGlobal());
1177 if (GVar && GVar->isThreadLocal())
1178 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
1180 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
1182 FoldingSetNodeID ID;
1183 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1185 ID.AddInteger(Offset);
1186 ID.AddInteger(TargetFlags);
1187 ID.AddInteger(GV->getType()->getAddressSpace());
1189 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1190 return SDValue(E, 0);
1192 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(),
1193 DL.getDebugLoc(), GV, VT,
1194 Offset, TargetFlags);
1195 CSEMap.InsertNode(N, IP);
1196 AllNodes.push_back(N);
1197 return SDValue(N, 0);
1200 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) {
1201 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
1202 FoldingSetNodeID ID;
1203 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1206 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1207 return SDValue(E, 0);
1209 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget);
1210 CSEMap.InsertNode(N, IP);
1211 AllNodes.push_back(N);
1212 return SDValue(N, 0);
1215 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget,
1216 unsigned char TargetFlags) {
1217 assert((TargetFlags == 0 || isTarget) &&
1218 "Cannot set target flags on target-independent jump tables");
1219 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
1220 FoldingSetNodeID ID;
1221 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1223 ID.AddInteger(TargetFlags);
1225 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1226 return SDValue(E, 0);
1228 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget,
1230 CSEMap.InsertNode(N, IP);
1231 AllNodes.push_back(N);
1232 return SDValue(N, 0);
1235 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT,
1236 unsigned Alignment, int Offset,
1238 unsigned char TargetFlags) {
1239 assert((TargetFlags == 0 || isTarget) &&
1240 "Cannot set target flags on target-independent globals");
1243 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1244 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1245 FoldingSetNodeID ID;
1246 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1247 ID.AddInteger(Alignment);
1248 ID.AddInteger(Offset);
1250 ID.AddInteger(TargetFlags);
1252 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1253 return SDValue(E, 0);
1255 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1256 Alignment, TargetFlags);
1257 CSEMap.InsertNode(N, IP);
1258 AllNodes.push_back(N);
1259 return SDValue(N, 0);
1263 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT,
1264 unsigned Alignment, int Offset,
1266 unsigned char TargetFlags) {
1267 assert((TargetFlags == 0 || isTarget) &&
1268 "Cannot set target flags on target-independent globals");
1271 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType());
1272 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
1273 FoldingSetNodeID ID;
1274 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1275 ID.AddInteger(Alignment);
1276 ID.AddInteger(Offset);
1277 C->addSelectionDAGCSEId(ID);
1278 ID.AddInteger(TargetFlags);
1280 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1281 return SDValue(E, 0);
1283 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset,
1284 Alignment, TargetFlags);
1285 CSEMap.InsertNode(N, IP);
1286 AllNodes.push_back(N);
1287 return SDValue(N, 0);
1290 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset,
1291 unsigned char TargetFlags) {
1292 FoldingSetNodeID ID;
1293 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None);
1294 ID.AddInteger(Index);
1295 ID.AddInteger(Offset);
1296 ID.AddInteger(TargetFlags);
1298 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1299 return SDValue(E, 0);
1301 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset,
1303 CSEMap.InsertNode(N, IP);
1304 AllNodes.push_back(N);
1305 return SDValue(N, 0);
1308 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
1309 FoldingSetNodeID ID;
1310 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None);
1313 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1314 return SDValue(E, 0);
1316 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB);
1317 CSEMap.InsertNode(N, IP);
1318 AllNodes.push_back(N);
1319 return SDValue(N, 0);
1322 SDValue SelectionDAG::getValueType(EVT VT) {
1323 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >=
1324 ValueTypeNodes.size())
1325 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1);
1327 SDNode *&N = VT.isExtended() ?
1328 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy];
1330 if (N) return SDValue(N, 0);
1331 N = new (NodeAllocator) VTSDNode(VT);
1332 AllNodes.push_back(N);
1333 return SDValue(N, 0);
1336 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) {
1337 SDNode *&N = ExternalSymbols[Sym];
1338 if (N) return SDValue(N, 0);
1339 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT);
1340 AllNodes.push_back(N);
1341 return SDValue(N, 0);
1344 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT,
1345 unsigned char TargetFlags) {
1347 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym,
1349 if (N) return SDValue(N, 0);
1350 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT);
1351 AllNodes.push_back(N);
1352 return SDValue(N, 0);
1355 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) {
1356 if ((unsigned)Cond >= CondCodeNodes.size())
1357 CondCodeNodes.resize(Cond+1);
1359 if (!CondCodeNodes[Cond]) {
1360 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond);
1361 CondCodeNodes[Cond] = N;
1362 AllNodes.push_back(N);
1365 return SDValue(CondCodeNodes[Cond], 0);
1368 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in
1369 // the shuffle mask M that point at N1 to point at N2, and indices that point
1370 // N2 to point at N1.
1371 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) {
1373 int NElts = M.size();
1374 for (int i = 0; i != NElts; ++i) {
1382 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1,
1383 SDValue N2, const int *Mask) {
1384 assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1385 "Invalid VECTOR_SHUFFLE");
1387 // Canonicalize shuffle undef, undef -> undef
1388 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF)
1389 return getUNDEF(VT);
1391 // Validate that all indices in Mask are within the range of the elements
1392 // input to the shuffle.
1393 unsigned NElts = VT.getVectorNumElements();
1394 SmallVector<int, 8> MaskVec;
1395 for (unsigned i = 0; i != NElts; ++i) {
1396 assert(Mask[i] < (int)(NElts * 2) && "Index out of range");
1397 MaskVec.push_back(Mask[i]);
1400 // Canonicalize shuffle v, v -> v, undef
1403 for (unsigned i = 0; i != NElts; ++i)
1404 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts;
1407 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask.
1408 if (N1.getOpcode() == ISD::UNDEF)
1409 commuteShuffle(N1, N2, MaskVec);
1411 // Canonicalize all index into lhs, -> shuffle lhs, undef
1412 // Canonicalize all index into rhs, -> shuffle rhs, undef
1413 bool AllLHS = true, AllRHS = true;
1414 bool N2Undef = N2.getOpcode() == ISD::UNDEF;
1415 for (unsigned i = 0; i != NElts; ++i) {
1416 if (MaskVec[i] >= (int)NElts) {
1421 } else if (MaskVec[i] >= 0) {
1425 if (AllLHS && AllRHS)
1426 return getUNDEF(VT);
1427 if (AllLHS && !N2Undef)
1431 commuteShuffle(N1, N2, MaskVec);
1434 // If Identity shuffle return that node.
1435 bool Identity = true;
1436 for (unsigned i = 0; i != NElts; ++i) {
1437 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false;
1439 if (Identity && NElts)
1442 // Shuffling a constant splat doesn't change the result.
1443 if (N2Undef && N1.getOpcode() == ISD::BUILD_VECTOR)
1444 if (cast<BuildVectorSDNode>(N1)->getConstantSplatValue())
1447 FoldingSetNodeID ID;
1448 SDValue Ops[2] = { N1, N2 };
1449 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops);
1450 for (unsigned i = 0; i != NElts; ++i)
1451 ID.AddInteger(MaskVec[i]);
1454 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1455 return SDValue(E, 0);
1457 // Allocate the mask array for the node out of the BumpPtrAllocator, since
1458 // SDNode doesn't have access to it. This memory will be "leaked" when
1459 // the node is deallocated, but recovered when the NodeAllocator is released.
1460 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts);
1461 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int));
1463 ShuffleVectorSDNode *N =
1464 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(),
1465 dl.getDebugLoc(), N1, N2,
1467 CSEMap.InsertNode(N, IP);
1468 AllNodes.push_back(N);
1469 return SDValue(N, 0);
1472 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl,
1473 SDValue Val, SDValue DTy,
1474 SDValue STy, SDValue Rnd, SDValue Sat,
1475 ISD::CvtCode Code) {
1476 // If the src and dest types are the same and the conversion is between
1477 // integer types of the same sign or two floats, no conversion is necessary.
1479 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF))
1482 FoldingSetNodeID ID;
1483 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat };
1484 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops);
1486 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1487 return SDValue(E, 0);
1489 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(),
1492 CSEMap.InsertNode(N, IP);
1493 AllNodes.push_back(N);
1494 return SDValue(N, 0);
1497 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) {
1498 FoldingSetNodeID ID;
1499 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None);
1500 ID.AddInteger(RegNo);
1502 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1503 return SDValue(E, 0);
1505 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT);
1506 CSEMap.InsertNode(N, IP);
1507 AllNodes.push_back(N);
1508 return SDValue(N, 0);
1511 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) {
1512 FoldingSetNodeID ID;
1513 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None);
1514 ID.AddPointer(RegMask);
1516 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1517 return SDValue(E, 0);
1519 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask);
1520 CSEMap.InsertNode(N, IP);
1521 AllNodes.push_back(N);
1522 return SDValue(N, 0);
1525 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) {
1526 FoldingSetNodeID ID;
1527 SDValue Ops[] = { Root };
1528 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops);
1529 ID.AddPointer(Label);
1531 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1532 return SDValue(E, 0);
1534 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(),
1535 dl.getDebugLoc(), Root, Label);
1536 CSEMap.InsertNode(N, IP);
1537 AllNodes.push_back(N);
1538 return SDValue(N, 0);
1542 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT,
1545 unsigned char TargetFlags) {
1546 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress;
1548 FoldingSetNodeID ID;
1549 AddNodeIDNode(ID, Opc, getVTList(VT), None);
1551 ID.AddInteger(Offset);
1552 ID.AddInteger(TargetFlags);
1554 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1555 return SDValue(E, 0);
1557 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset,
1559 CSEMap.InsertNode(N, IP);
1560 AllNodes.push_back(N);
1561 return SDValue(N, 0);
1564 SDValue SelectionDAG::getSrcValue(const Value *V) {
1565 assert((!V || V->getType()->isPointerTy()) &&
1566 "SrcValue is not a pointer?");
1568 FoldingSetNodeID ID;
1569 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None);
1573 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1574 return SDValue(E, 0);
1576 SDNode *N = new (NodeAllocator) SrcValueSDNode(V);
1577 CSEMap.InsertNode(N, IP);
1578 AllNodes.push_back(N);
1579 return SDValue(N, 0);
1582 /// getMDNode - Return an MDNodeSDNode which holds an MDNode.
1583 SDValue SelectionDAG::getMDNode(const MDNode *MD) {
1584 FoldingSetNodeID ID;
1585 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None);
1589 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1590 return SDValue(E, 0);
1592 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD);
1593 CSEMap.InsertNode(N, IP);
1594 AllNodes.push_back(N);
1595 return SDValue(N, 0);
1598 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode.
1599 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr,
1600 unsigned SrcAS, unsigned DestAS) {
1601 SDValue Ops[] = {Ptr};
1602 FoldingSetNodeID ID;
1603 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops);
1604 ID.AddInteger(SrcAS);
1605 ID.AddInteger(DestAS);
1608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1609 return SDValue(E, 0);
1611 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(),
1613 VT, Ptr, SrcAS, DestAS);
1614 CSEMap.InsertNode(N, IP);
1615 AllNodes.push_back(N);
1616 return SDValue(N, 0);
1619 /// getShiftAmountOperand - Return the specified value casted to
1620 /// the target's desired shift amount type.
1621 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) {
1622 EVT OpTy = Op.getValueType();
1623 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy);
1624 if (OpTy == ShTy || OpTy.isVector()) return Op;
1626 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND;
1627 return getNode(Opcode, SDLoc(Op), ShTy, Op);
1630 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1631 /// specified value type.
1632 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
1633 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1634 unsigned ByteSize = VT.getStoreSize();
1635 Type *Ty = VT.getTypeForEVT(*getContext());
1636 const TargetLowering *TLI = TM.getTargetLowering();
1637 unsigned StackAlign =
1638 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign);
1640 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
1641 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1644 /// CreateStackTemporary - Create a stack temporary suitable for holding
1645 /// either of the specified value types.
1646 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
1647 unsigned Bytes = std::max(VT1.getStoreSizeInBits(),
1648 VT2.getStoreSizeInBits())/8;
1649 Type *Ty1 = VT1.getTypeForEVT(*getContext());
1650 Type *Ty2 = VT2.getTypeForEVT(*getContext());
1651 const TargetLowering *TLI = TM.getTargetLowering();
1652 const DataLayout *TD = TLI->getDataLayout();
1653 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1),
1654 TD->getPrefTypeAlignment(Ty2));
1656 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1657 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false);
1658 return getFrameIndex(FrameIdx, TLI->getPointerTy());
1661 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1,
1662 SDValue N2, ISD::CondCode Cond, SDLoc dl) {
1663 // These setcc operations always fold.
1667 case ISD::SETFALSE2: return getConstant(0, VT);
1669 case ISD::SETTRUE2: {
1670 const TargetLowering *TLI = TM.getTargetLowering();
1671 TargetLowering::BooleanContent Cnt = TLI->getBooleanContents(VT.isVector());
1673 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT);
1686 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!");
1690 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) {
1691 const APInt &C2 = N2C->getAPIntValue();
1692 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
1693 const APInt &C1 = N1C->getAPIntValue();
1696 default: llvm_unreachable("Unknown integer setcc!");
1697 case ISD::SETEQ: return getConstant(C1 == C2, VT);
1698 case ISD::SETNE: return getConstant(C1 != C2, VT);
1699 case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1700 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1701 case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1702 case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1703 case ISD::SETLT: return getConstant(C1.slt(C2), VT);
1704 case ISD::SETGT: return getConstant(C1.sgt(C2), VT);
1705 case ISD::SETLE: return getConstant(C1.sle(C2), VT);
1706 case ISD::SETGE: return getConstant(C1.sge(C2), VT);
1710 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) {
1711 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) {
1712 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1715 case ISD::SETEQ: if (R==APFloat::cmpUnordered)
1716 return getUNDEF(VT);
1718 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1719 case ISD::SETNE: if (R==APFloat::cmpUnordered)
1720 return getUNDEF(VT);
1722 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1723 R==APFloat::cmpLessThan, VT);
1724 case ISD::SETLT: if (R==APFloat::cmpUnordered)
1725 return getUNDEF(VT);
1727 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1728 case ISD::SETGT: if (R==APFloat::cmpUnordered)
1729 return getUNDEF(VT);
1731 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1732 case ISD::SETLE: if (R==APFloat::cmpUnordered)
1733 return getUNDEF(VT);
1735 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1736 R==APFloat::cmpEqual, VT);
1737 case ISD::SETGE: if (R==APFloat::cmpUnordered)
1738 return getUNDEF(VT);
1740 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1741 R==APFloat::cmpEqual, VT);
1742 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT);
1743 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT);
1744 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1745 R==APFloat::cmpEqual, VT);
1746 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1747 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1748 R==APFloat::cmpLessThan, VT);
1749 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1750 R==APFloat::cmpUnordered, VT);
1751 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1752 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1755 // Ensure that the constant occurs on the RHS.
1756 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond);
1757 MVT CompVT = N1.getValueType().getSimpleVT();
1758 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT))
1761 return getSetCC(dl, VT, N2, N1, SwappedCond);
1765 // Could not fold it.
1769 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We
1770 /// use this predicate to simplify operations downstream.
1771 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
1772 // This predicate is not safe for vector operations.
1773 if (Op.getValueType().isVector())
1776 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1777 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1780 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use
1781 /// this predicate to simplify operations downstream. Mask is known to be zero
1782 /// for bits that V cannot have.
1783 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask,
1784 unsigned Depth) const {
1785 APInt KnownZero, KnownOne;
1786 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
1787 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1788 return (KnownZero & Mask) == Mask;
1791 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1792 /// known to be either zero or one and return them in the KnownZero/KnownOne
1793 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit
1795 void SelectionDAG::ComputeMaskedBits(SDValue Op, APInt &KnownZero,
1796 APInt &KnownOne, unsigned Depth) const {
1797 const TargetLowering *TLI = TM.getTargetLowering();
1798 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
1800 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything.
1802 return; // Limit search depth.
1804 APInt KnownZero2, KnownOne2;
1806 switch (Op.getOpcode()) {
1808 // We know all of the bits for a constant!
1809 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue();
1810 KnownZero = ~KnownOne;
1813 // If either the LHS or the RHS are Zero, the result is zero.
1814 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1815 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1816 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1817 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1819 // Output known-1 bits are only known if set in both the LHS & RHS.
1820 KnownOne &= KnownOne2;
1821 // Output known-0 are known to be clear if zero in either the LHS | RHS.
1822 KnownZero |= KnownZero2;
1825 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1826 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1827 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1828 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1830 // Output known-0 bits are only known if clear in both the LHS & RHS.
1831 KnownZero &= KnownZero2;
1832 // Output known-1 are known to be set if set in either the LHS | RHS.
1833 KnownOne |= KnownOne2;
1836 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1837 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1838 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1839 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1841 // Output known-0 bits are known if clear or set in both the LHS & RHS.
1842 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1843 // Output known-1 are known to be set if set in only one of the LHS, RHS.
1844 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1845 KnownZero = KnownZeroOut;
1849 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
1850 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1851 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1852 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1854 // If low bits are zero in either operand, output low known-0 bits.
1855 // Also compute a conserative estimate for high known-0 bits.
1856 // More trickiness is possible, but this is sufficient for the
1857 // interesting case of alignment computation.
1858 KnownOne.clearAllBits();
1859 unsigned TrailZ = KnownZero.countTrailingOnes() +
1860 KnownZero2.countTrailingOnes();
1861 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() +
1862 KnownZero2.countLeadingOnes(),
1863 BitWidth) - BitWidth;
1865 TrailZ = std::min(TrailZ, BitWidth);
1866 LeadZ = std::min(LeadZ, BitWidth);
1867 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1868 APInt::getHighBitsSet(BitWidth, LeadZ);
1872 // For the purposes of computing leading zeros we can conservatively
1873 // treat a udiv as a logical right shift by the power of 2 known to
1874 // be less than the denominator.
1875 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
1876 unsigned LeadZ = KnownZero2.countLeadingOnes();
1878 KnownOne2.clearAllBits();
1879 KnownZero2.clearAllBits();
1880 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1881 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1882 if (RHSUnknownLeadingOnes != BitWidth)
1883 LeadZ = std::min(BitWidth,
1884 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1886 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ);
1890 ComputeMaskedBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1);
1891 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
1892 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1893 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1895 // Only known if known in both the LHS and RHS.
1896 KnownOne &= KnownOne2;
1897 KnownZero &= KnownZero2;
1899 case ISD::SELECT_CC:
1900 ComputeMaskedBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1);
1901 ComputeMaskedBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
1902 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1903 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1905 // Only known if known in both the LHS and RHS.
1906 KnownOne &= KnownOne2;
1907 KnownZero &= KnownZero2;
1915 if (Op.getResNo() != 1)
1917 // The boolean result conforms to getBooleanContents. Fall through.
1919 // If we know the result of a setcc has the top bits zero, use this info.
1920 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
1921 TargetLowering::ZeroOrOneBooleanContent && BitWidth > 1)
1922 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1925 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0
1926 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1927 unsigned ShAmt = SA->getZExtValue();
1929 // If the shift count is an invalid immediate, don't do anything.
1930 if (ShAmt >= BitWidth)
1933 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1934 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1935 KnownZero <<= ShAmt;
1937 // low bits known zero.
1938 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1942 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0
1943 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1944 unsigned ShAmt = SA->getZExtValue();
1946 // If the shift count is an invalid immediate, don't do anything.
1947 if (ShAmt >= BitWidth)
1950 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1951 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
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 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
1972 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1973 KnownZero = KnownZero.lshr(ShAmt);
1974 KnownOne = KnownOne.lshr(ShAmt);
1976 // Handle the sign bits.
1977 APInt SignBit = APInt::getSignBit(BitWidth);
1978 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask.
1980 if (KnownZero.intersects(SignBit)) {
1981 KnownZero |= HighBits; // New bits are known zero.
1982 } else if (KnownOne.intersects(SignBit)) {
1983 KnownOne |= HighBits; // New bits are known one.
1987 case ISD::SIGN_EXTEND_INREG: {
1988 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1989 unsigned EBits = EVT.getScalarType().getSizeInBits();
1991 // Sign extension. Compute the demanded bits in the result that are not
1992 // present in the input.
1993 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits);
1995 APInt InSignBit = APInt::getSignBit(EBits);
1996 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits);
1998 // If the sign extended bits are demanded, we know that the sign
2000 InSignBit = InSignBit.zext(BitWidth);
2001 if (NewBits.getBoolValue())
2002 InputDemandedBits |= InSignBit;
2004 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2005 KnownOne &= InputDemandedBits;
2006 KnownZero &= InputDemandedBits;
2007 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2009 // If the sign bit of the input is known set or clear, then we know the
2010 // top bits of the result.
2011 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear
2012 KnownZero |= NewBits;
2013 KnownOne &= ~NewBits;
2014 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set
2015 KnownOne |= NewBits;
2016 KnownZero &= ~NewBits;
2017 } else { // Input sign bit unknown
2018 KnownZero &= ~NewBits;
2019 KnownOne &= ~NewBits;
2024 case ISD::CTTZ_ZERO_UNDEF:
2026 case ISD::CTLZ_ZERO_UNDEF:
2028 unsigned LowBits = Log2_32(BitWidth)+1;
2029 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
2030 KnownOne.clearAllBits();
2034 LoadSDNode *LD = cast<LoadSDNode>(Op);
2035 // If this is a ZEXTLoad and we are looking at the loaded value.
2036 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) {
2037 EVT VT = LD->getMemoryVT();
2038 unsigned MemBits = VT.getScalarType().getSizeInBits();
2039 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits);
2040 } else if (const MDNode *Ranges = LD->getRanges()) {
2041 computeMaskedBitsLoad(*Ranges, KnownZero);
2045 case ISD::ZERO_EXTEND: {
2046 EVT InVT = Op.getOperand(0).getValueType();
2047 unsigned InBits = InVT.getScalarType().getSizeInBits();
2048 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2049 KnownZero = KnownZero.trunc(InBits);
2050 KnownOne = KnownOne.trunc(InBits);
2051 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2052 KnownZero = KnownZero.zext(BitWidth);
2053 KnownOne = KnownOne.zext(BitWidth);
2054 KnownZero |= NewBits;
2057 case ISD::SIGN_EXTEND: {
2058 EVT InVT = Op.getOperand(0).getValueType();
2059 unsigned InBits = InVT.getScalarType().getSizeInBits();
2060 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits);
2062 KnownZero = KnownZero.trunc(InBits);
2063 KnownOne = KnownOne.trunc(InBits);
2064 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2066 // Note if the sign bit is known to be zero or one.
2067 bool SignBitKnownZero = KnownZero.isNegative();
2068 bool SignBitKnownOne = KnownOne.isNegative();
2069 assert(!(SignBitKnownZero && SignBitKnownOne) &&
2070 "Sign bit can't be known to be both zero and one!");
2072 KnownZero = KnownZero.zext(BitWidth);
2073 KnownOne = KnownOne.zext(BitWidth);
2075 // If the sign bit is known zero or one, the top bits match.
2076 if (SignBitKnownZero)
2077 KnownZero |= NewBits;
2078 else if (SignBitKnownOne)
2079 KnownOne |= NewBits;
2082 case ISD::ANY_EXTEND: {
2083 EVT InVT = Op.getOperand(0).getValueType();
2084 unsigned InBits = InVT.getScalarType().getSizeInBits();
2085 KnownZero = KnownZero.trunc(InBits);
2086 KnownOne = KnownOne.trunc(InBits);
2087 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2088 KnownZero = KnownZero.zext(BitWidth);
2089 KnownOne = KnownOne.zext(BitWidth);
2092 case ISD::TRUNCATE: {
2093 EVT InVT = Op.getOperand(0).getValueType();
2094 unsigned InBits = InVT.getScalarType().getSizeInBits();
2095 KnownZero = KnownZero.zext(InBits);
2096 KnownOne = KnownOne.zext(InBits);
2097 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2098 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
2099 KnownZero = KnownZero.trunc(BitWidth);
2100 KnownOne = KnownOne.trunc(BitWidth);
2103 case ISD::AssertZext: {
2104 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
2105 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits());
2106 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2107 KnownZero |= (~InMask);
2108 KnownOne &= (~KnownZero);
2112 // All bits are zero except the low bit.
2113 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
2117 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
2118 // We know that the top bits of C-X are clear if X contains less bits
2119 // than C (i.e. no wrap-around can happen). For example, 20-X is
2120 // positive if we can prove that X is >= 0 and < 16.
2121 if (CLHS->getAPIntValue().isNonNegative()) {
2122 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
2123 // NLZ can't be BitWidth with no sign bit
2124 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
2125 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2127 // If all of the MaskV bits are known to be zero, then we know the
2128 // output top bits are zero, because we now know that the output is
2130 if ((KnownZero2 & MaskV) == MaskV) {
2131 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
2132 // Top bits known zero.
2133 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
2141 // Output known-0 bits are known if clear or set in both the low clear bits
2142 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
2143 // low 3 bits clear.
2144 ComputeMaskedBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1);
2145 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2146 unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
2148 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2149 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
2150 KnownZeroOut = std::min(KnownZeroOut,
2151 KnownZero2.countTrailingOnes());
2153 if (Op.getOpcode() == ISD::ADD) {
2154 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
2158 // With ADDE, a carry bit may be added in, so we can only use this
2159 // information if we know (at least) that the low two bits are clear. We
2160 // then return to the caller that the low bit is unknown but that other bits
2162 if (KnownZeroOut >= 2) // ADDE
2163 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut);
2167 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2168 const APInt &RA = Rem->getAPIntValue().abs();
2169 if (RA.isPowerOf2()) {
2170 APInt LowBits = RA - 1;
2171 ComputeMaskedBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1);
2173 // The low bits of the first operand are unchanged by the srem.
2174 KnownZero = KnownZero2 & LowBits;
2175 KnownOne = KnownOne2 & LowBits;
2177 // If the first operand is non-negative or has all low bits zero, then
2178 // the upper bits are all zero.
2179 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
2180 KnownZero |= ~LowBits;
2182 // If the first operand is negative and not all low bits are zero, then
2183 // the upper bits are all one.
2184 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0))
2185 KnownOne |= ~LowBits;
2186 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2191 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2192 const APInt &RA = Rem->getAPIntValue();
2193 if (RA.isPowerOf2()) {
2194 APInt LowBits = (RA - 1);
2195 KnownZero |= ~LowBits;
2196 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne,Depth+1);
2197 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
2202 // Since the result is less than or equal to either operand, any leading
2203 // zero bits in either operand must also exist in the result.
2204 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2205 ComputeMaskedBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1);
2207 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
2208 KnownZero2.countLeadingOnes());
2209 KnownOne.clearAllBits();
2210 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders);
2213 case ISD::FrameIndex:
2214 case ISD::TargetFrameIndex:
2215 if (unsigned Align = InferPtrAlignment(Op)) {
2216 // The low bits are known zero if the pointer is aligned.
2217 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align));
2223 if (Op.getOpcode() < ISD::BUILTIN_OP_END)
2226 case ISD::INTRINSIC_WO_CHAIN:
2227 case ISD::INTRINSIC_W_CHAIN:
2228 case ISD::INTRINSIC_VOID:
2229 // Allow the target to implement this method for its nodes.
2230 TLI->computeMaskedBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
2235 /// ComputeNumSignBits - Return the number of times the sign bit of the
2236 /// register is replicated into the other bits. We know that at least 1 bit
2237 /// is always equal to the sign bit (itself), but other cases can give us
2238 /// information. For example, immediately after an "SRA X, 2", we know that
2239 /// the top 3 bits are all equal to each other, so we return 3.
2240 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{
2241 const TargetLowering *TLI = TM.getTargetLowering();
2242 EVT VT = Op.getValueType();
2243 assert(VT.isInteger() && "Invalid VT!");
2244 unsigned VTBits = VT.getScalarType().getSizeInBits();
2246 unsigned FirstAnswer = 1;
2249 return 1; // Limit search depth.
2251 switch (Op.getOpcode()) {
2253 case ISD::AssertSext:
2254 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2255 return VTBits-Tmp+1;
2256 case ISD::AssertZext:
2257 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
2260 case ISD::Constant: {
2261 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
2262 return Val.getNumSignBits();
2265 case ISD::SIGN_EXTEND:
2267 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits();
2268 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
2270 case ISD::SIGN_EXTEND_INREG:
2271 // Max of the input and what this extends.
2273 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits();
2276 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2277 return std::max(Tmp, Tmp2);
2280 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2281 // SRA X, C -> adds C sign bits.
2282 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2283 Tmp += C->getZExtValue();
2284 if (Tmp > VTBits) Tmp = VTBits;
2288 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2289 // shl destroys sign bits.
2290 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2291 if (C->getZExtValue() >= VTBits || // Bad shift.
2292 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out.
2293 return Tmp - C->getZExtValue();
2298 case ISD::XOR: // NOT is handled here.
2299 // Logical binary ops preserve the number of sign bits at the worst.
2300 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2302 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2303 FirstAnswer = std::min(Tmp, Tmp2);
2304 // We computed what we know about the sign bits as our first
2305 // answer. Now proceed to the generic code that uses
2306 // ComputeMaskedBits, and pick whichever answer is better.
2311 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2312 if (Tmp == 1) return 1; // Early out.
2313 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1);
2314 return std::min(Tmp, Tmp2);
2322 if (Op.getResNo() != 1)
2324 // The boolean result conforms to getBooleanContents. Fall through.
2326 // If setcc returns 0/-1, all bits are sign bits.
2327 if (TLI->getBooleanContents(Op.getValueType().isVector()) ==
2328 TargetLowering::ZeroOrNegativeOneBooleanContent)
2333 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
2334 unsigned RotAmt = C->getZExtValue() & (VTBits-1);
2336 // Handle rotate right by N like a rotate left by 32-N.
2337 if (Op.getOpcode() == ISD::ROTR)
2338 RotAmt = (VTBits-RotAmt) & (VTBits-1);
2340 // If we aren't rotating out all of the known-in sign bits, return the
2341 // number that are left. This handles rotl(sext(x), 1) for example.
2342 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2343 if (Tmp > RotAmt+1) return Tmp-RotAmt;
2347 // Add can have at most one carry bit. Thus we know that the output
2348 // is, at worst, one more bit than the inputs.
2349 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2350 if (Tmp == 1) return 1; // Early out.
2352 // Special case decrementing a value (ADD X, -1):
2353 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2354 if (CRHS->isAllOnesValue()) {
2355 APInt KnownZero, KnownOne;
2356 ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1);
2358 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2360 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2363 // If we are subtracting one from a positive number, there is no carry
2364 // out of the result.
2365 if (KnownZero.isNegative())
2369 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2370 if (Tmp2 == 1) return 1;
2371 return std::min(Tmp, Tmp2)-1;
2374 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
2375 if (Tmp2 == 1) return 1;
2378 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
2379 if (CLHS->isNullValue()) {
2380 APInt KnownZero, KnownOne;
2381 ComputeMaskedBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1);
2382 // If the input is known to be 0 or 1, the output is 0/-1, which is all
2384 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue())
2387 // If the input is known to be positive (the sign bit is known clear),
2388 // the output of the NEG has the same number of sign bits as the input.
2389 if (KnownZero.isNegative())
2392 // Otherwise, we treat this like a SUB.
2395 // Sub can have at most one carry bit. Thus we know that the output
2396 // is, at worst, one more bit than the inputs.
2397 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
2398 if (Tmp == 1) return 1; // Early out.
2399 return std::min(Tmp, Tmp2)-1;
2401 // FIXME: it's tricky to do anything useful for this, but it is an important
2402 // case for targets like X86.
2406 // If we are looking at the loaded value of the SDNode.
2407 if (Op.getResNo() == 0) {
2408 // Handle LOADX separately here. EXTLOAD case will fallthrough.
2409 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
2410 unsigned ExtType = LD->getExtensionType();
2413 case ISD::SEXTLOAD: // '17' bits known
2414 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2415 return VTBits-Tmp+1;
2416 case ISD::ZEXTLOAD: // '16' bits known
2417 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits();
2423 // Allow the target to implement this method for its nodes.
2424 if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
2425 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
2426 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
2427 Op.getOpcode() == ISD::INTRINSIC_VOID) {
2428 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth);
2429 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits);
2432 // Finally, if we can prove that the top bits of the result are 0's or 1's,
2433 // use this information.
2434 APInt KnownZero, KnownOne;
2435 ComputeMaskedBits(Op, KnownZero, KnownOne, Depth);
2438 if (KnownZero.isNegative()) { // sign bit is 0
2440 } else if (KnownOne.isNegative()) { // sign bit is 1;
2447 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine
2448 // the number of identical bits in the top of the input value.
2450 Mask <<= Mask.getBitWidth()-VTBits;
2451 // Return # leading zeros. We use 'min' here in case Val was zero before
2452 // shifting. We don't want to return '64' as for an i32 "0".
2453 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros()));
2456 /// isBaseWithConstantOffset - Return true if the specified operand is an
2457 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an
2458 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same
2459 /// semantics as an ADD. This handles the equivalence:
2460 /// X|Cst == X+Cst iff X&Cst = 0.
2461 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const {
2462 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) ||
2463 !isa<ConstantSDNode>(Op.getOperand(1)))
2466 if (Op.getOpcode() == ISD::OR &&
2467 !MaskedValueIsZero(Op.getOperand(0),
2468 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue()))
2475 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const {
2476 // If we're told that NaNs won't happen, assume they won't.
2477 if (getTarget().Options.NoNaNsFPMath)
2480 // If the value is a constant, we can obviously see if it is a NaN or not.
2481 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2482 return !C->getValueAPF().isNaN();
2484 // TODO: Recognize more cases here.
2489 bool SelectionDAG::isKnownNeverZero(SDValue Op) const {
2490 // If the value is a constant, we can obviously see if it is a zero or not.
2491 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op))
2492 return !C->isZero();
2494 // TODO: Recognize more cases here.
2495 switch (Op.getOpcode()) {
2498 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
2499 return !C->isNullValue();
2506 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const {
2507 // Check the obvious case.
2508 if (A == B) return true;
2510 // For for negative and positive zero.
2511 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A))
2512 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B))
2513 if (CA->isZero() && CB->isZero()) return true;
2515 // Otherwise they may not be equal.
2519 /// getNode - Gets or creates the specified node.
2521 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) {
2522 FoldingSetNodeID ID;
2523 AddNodeIDNode(ID, Opcode, getVTList(VT), None);
2525 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2526 return SDValue(E, 0);
2528 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(),
2529 DL.getDebugLoc(), getVTList(VT));
2530 CSEMap.InsertNode(N, IP);
2532 AllNodes.push_back(N);
2536 return SDValue(N, 0);
2539 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
2540 EVT VT, SDValue Operand) {
2541 // Constant fold unary operations with an integer constant operand. Even
2542 // opaque constant will be folded, because the folding of unary operations
2543 // doesn't create new constants with different values. Nevertheless, the
2544 // opaque flag is preserved during folding to prevent future folding with
2546 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) {
2547 const APInt &Val = C->getAPIntValue();
2550 case ISD::SIGN_EXTEND:
2551 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT,
2552 C->isTargetOpcode(), C->isOpaque());
2553 case ISD::ANY_EXTEND:
2554 case ISD::ZERO_EXTEND:
2556 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT,
2557 C->isTargetOpcode(), C->isOpaque());
2558 case ISD::UINT_TO_FP:
2559 case ISD::SINT_TO_FP: {
2560 APFloat apf(EVTToAPFloatSemantics(VT),
2561 APInt::getNullValue(VT.getSizeInBits()));
2562 (void)apf.convertFromAPInt(Val,
2563 Opcode==ISD::SINT_TO_FP,
2564 APFloat::rmNearestTiesToEven);
2565 return getConstantFP(apf, VT);
2568 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
2569 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT);
2570 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
2571 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT);
2574 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(),
2577 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(),
2580 case ISD::CTLZ_ZERO_UNDEF:
2581 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(),
2584 case ISD::CTTZ_ZERO_UNDEF:
2585 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(),
2590 // Constant fold unary operations with a floating point constant operand.
2591 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) {
2592 APFloat V = C->getValueAPF(); // make copy
2596 return getConstantFP(V, VT);
2599 return getConstantFP(V, VT);
2601 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive);
2602 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2603 return getConstantFP(V, VT);
2607 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero);
2608 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2609 return getConstantFP(V, VT);
2613 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative);
2614 if (fs == APFloat::opOK || fs == APFloat::opInexact)
2615 return getConstantFP(V, VT);
2618 case ISD::FP_EXTEND: {
2620 // This can return overflow, underflow, or inexact; we don't care.
2621 // FIXME need to be more flexible about rounding mode.
2622 (void)V.convert(EVTToAPFloatSemantics(VT),
2623 APFloat::rmNearestTiesToEven, &ignored);
2624 return getConstantFP(V, VT);
2626 case ISD::FP_TO_SINT:
2627 case ISD::FP_TO_UINT: {
2630 assert(integerPartWidth >= 64);
2631 // FIXME need to be more flexible about rounding mode.
2632 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(),
2633 Opcode==ISD::FP_TO_SINT,
2634 APFloat::rmTowardZero, &ignored);
2635 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual
2637 APInt api(VT.getSizeInBits(), x);
2638 return getConstant(api, VT);
2641 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
2642 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT);
2643 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
2644 return getConstant(V.bitcastToAPInt().getZExtValue(), VT);
2649 unsigned OpOpcode = Operand.getNode()->getOpcode();
2651 case ISD::TokenFactor:
2652 case ISD::MERGE_VALUES:
2653 case ISD::CONCAT_VECTORS:
2654 return Operand; // Factor, merge or concat of one node? No need.
2655 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node");
2656 case ISD::FP_EXTEND:
2657 assert(VT.isFloatingPoint() &&
2658 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!");
2659 if (Operand.getValueType() == VT) return Operand; // noop conversion.
2660 assert((!VT.isVector() ||
2661 VT.getVectorNumElements() ==
2662 Operand.getValueType().getVectorNumElements()) &&
2663 "Vector element count mismatch!");
2664 if (Operand.getOpcode() == ISD::UNDEF)
2665 return getUNDEF(VT);
2667 case ISD::SIGN_EXTEND:
2668 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2669 "Invalid SIGN_EXTEND!");
2670 if (Operand.getValueType() == VT) return Operand; // noop extension
2671 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2672 "Invalid sext node, dst < src!");
2673 assert((!VT.isVector() ||
2674 VT.getVectorNumElements() ==
2675 Operand.getValueType().getVectorNumElements()) &&
2676 "Vector element count mismatch!");
2677 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
2678 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2679 else if (OpOpcode == ISD::UNDEF)
2680 // sext(undef) = 0, because the top bits will all be the same.
2681 return getConstant(0, VT);
2683 case ISD::ZERO_EXTEND:
2684 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2685 "Invalid ZERO_EXTEND!");
2686 if (Operand.getValueType() == VT) return Operand; // noop extension
2687 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2688 "Invalid zext node, dst < src!");
2689 assert((!VT.isVector() ||
2690 VT.getVectorNumElements() ==
2691 Operand.getValueType().getVectorNumElements()) &&
2692 "Vector element count mismatch!");
2693 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x)
2694 return getNode(ISD::ZERO_EXTEND, DL, VT,
2695 Operand.getNode()->getOperand(0));
2696 else if (OpOpcode == ISD::UNDEF)
2697 // zext(undef) = 0, because the top bits will be zero.
2698 return getConstant(0, VT);
2700 case ISD::ANY_EXTEND:
2701 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2702 "Invalid ANY_EXTEND!");
2703 if (Operand.getValueType() == VT) return Operand; // noop extension
2704 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) &&
2705 "Invalid anyext node, dst < src!");
2706 assert((!VT.isVector() ||
2707 VT.getVectorNumElements() ==
2708 Operand.getValueType().getVectorNumElements()) &&
2709 "Vector element count mismatch!");
2711 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2712 OpOpcode == ISD::ANY_EXTEND)
2713 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x)
2714 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2715 else if (OpOpcode == ISD::UNDEF)
2716 return getUNDEF(VT);
2718 // (ext (trunx x)) -> x
2719 if (OpOpcode == ISD::TRUNCATE) {
2720 SDValue OpOp = Operand.getNode()->getOperand(0);
2721 if (OpOp.getValueType() == VT)
2726 assert(VT.isInteger() && Operand.getValueType().isInteger() &&
2727 "Invalid TRUNCATE!");
2728 if (Operand.getValueType() == VT) return Operand; // noop truncate
2729 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) &&
2730 "Invalid truncate node, src < dst!");
2731 assert((!VT.isVector() ||
2732 VT.getVectorNumElements() ==
2733 Operand.getValueType().getVectorNumElements()) &&
2734 "Vector element count mismatch!");
2735 if (OpOpcode == ISD::TRUNCATE)
2736 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2737 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
2738 OpOpcode == ISD::ANY_EXTEND) {
2739 // If the source is smaller than the dest, we still need an extend.
2740 if (Operand.getNode()->getOperand(0).getValueType().getScalarType()
2741 .bitsLT(VT.getScalarType()))
2742 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0));
2743 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT))
2744 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0));
2745 return Operand.getNode()->getOperand(0);
2747 if (OpOpcode == ISD::UNDEF)
2748 return getUNDEF(VT);
2751 // Basic sanity checking.
2752 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits()
2753 && "Cannot BITCAST between types of different sizes!");
2754 if (VT == Operand.getValueType()) return Operand; // noop conversion.
2755 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x)
2756 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0));
2757 if (OpOpcode == ISD::UNDEF)
2758 return getUNDEF(VT);
2760 case ISD::SCALAR_TO_VECTOR:
2761 assert(VT.isVector() && !Operand.getValueType().isVector() &&
2762 (VT.getVectorElementType() == Operand.getValueType() ||
2763 (VT.getVectorElementType().isInteger() &&
2764 Operand.getValueType().isInteger() &&
2765 VT.getVectorElementType().bitsLE(Operand.getValueType()))) &&
2766 "Illegal SCALAR_TO_VECTOR node!");
2767 if (OpOpcode == ISD::UNDEF)
2768 return getUNDEF(VT);
2769 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2770 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2771 isa<ConstantSDNode>(Operand.getOperand(1)) &&
2772 Operand.getConstantOperandVal(1) == 0 &&
2773 Operand.getOperand(0).getValueType() == VT)
2774 return Operand.getOperand(0);
2777 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0
2778 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB)
2779 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1),
2780 Operand.getNode()->getOperand(0));
2781 if (OpOpcode == ISD::FNEG) // --X -> X
2782 return Operand.getNode()->getOperand(0);
2785 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X)
2786 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0));
2791 SDVTList VTs = getVTList(VT);
2792 if (VT != MVT::Glue) { // Don't CSE flag producing nodes
2793 FoldingSetNodeID ID;
2794 SDValue Ops[1] = { Operand };
2795 AddNodeIDNode(ID, Opcode, VTs, Ops);
2797 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2798 return SDValue(E, 0);
2800 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2801 DL.getDebugLoc(), VTs, Operand);
2802 CSEMap.InsertNode(N, IP);
2804 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
2805 DL.getDebugLoc(), VTs, Operand);
2808 AllNodes.push_back(N);
2812 return SDValue(N, 0);
2815 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT,
2816 SDNode *Cst1, SDNode *Cst2) {
2817 // If the opcode is a target-specific ISD node, there's nothing we can
2818 // do here and the operand rules may not line up with the below, so
2820 if (Opcode >= ISD::BUILTIN_OP_END)
2823 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs;
2824 SmallVector<SDValue, 4> Outputs;
2825 EVT SVT = VT.getScalarType();
2827 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1);
2828 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2);
2829 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque()))
2832 if (Scalar1 && Scalar2)
2833 // Scalar instruction.
2834 Inputs.push_back(std::make_pair(Scalar1, Scalar2));
2836 // For vectors extract each constant element into Inputs so we can constant
2837 // fold them individually.
2838 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1);
2839 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2);
2843 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!");
2845 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) {
2846 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I));
2847 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I));
2848 if (!V1 || !V2) // Not a constant, bail.
2851 if (V1->isOpaque() || V2->isOpaque())
2854 // Avoid BUILD_VECTOR nodes that perform implicit truncation.
2855 // FIXME: This is valid and could be handled by truncating the APInts.
2856 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT)
2859 Inputs.push_back(std::make_pair(V1, V2));
2863 // We have a number of constant values, constant fold them element by element.
2864 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) {
2865 const APInt &C1 = Inputs[I].first->getAPIntValue();
2866 const APInt &C2 = Inputs[I].second->getAPIntValue();
2870 Outputs.push_back(getConstant(C1 + C2, SVT));
2873 Outputs.push_back(getConstant(C1 - C2, SVT));
2876 Outputs.push_back(getConstant(C1 * C2, SVT));
2879 if (!C2.getBoolValue())
2881 Outputs.push_back(getConstant(C1.udiv(C2), SVT));
2884 if (!C2.getBoolValue())
2886 Outputs.push_back(getConstant(C1.urem(C2), SVT));
2889 if (!C2.getBoolValue())
2891 Outputs.push_back(getConstant(C1.sdiv(C2), SVT));
2894 if (!C2.getBoolValue())
2896 Outputs.push_back(getConstant(C1.srem(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 << C2, SVT));
2911 Outputs.push_back(getConstant(C1.lshr(C2), SVT));
2914 Outputs.push_back(getConstant(C1.ashr(C2), SVT));
2917 Outputs.push_back(getConstant(C1.rotl(C2), SVT));
2920 Outputs.push_back(getConstant(C1.rotr(C2), SVT));
2927 // Handle the scalar case first.
2928 if (Scalar1 && Scalar2)
2929 return Outputs.back();
2931 // Otherwise build a big vector out of the scalar elements we generated.
2932 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs);
2935 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1,
2937 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
2938 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
2941 case ISD::TokenFactor:
2942 assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2943 N2.getValueType() == MVT::Other && "Invalid token factor!");
2944 // Fold trivial token factors.
2945 if (N1.getOpcode() == ISD::EntryToken) return N2;
2946 if (N2.getOpcode() == ISD::EntryToken) return N1;
2947 if (N1 == N2) return N1;
2949 case ISD::CONCAT_VECTORS:
2950 // Concat of UNDEFs is UNDEF.
2951 if (N1.getOpcode() == ISD::UNDEF &&
2952 N2.getOpcode() == ISD::UNDEF)
2953 return getUNDEF(VT);
2955 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
2956 // one big BUILD_VECTOR.
2957 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
2958 N2.getOpcode() == ISD::BUILD_VECTOR) {
2959 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
2960 N1.getNode()->op_end());
2961 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
2962 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
2966 assert(VT.isInteger() && "This operator does not apply to FP types!");
2967 assert(N1.getValueType() == N2.getValueType() &&
2968 N1.getValueType() == VT && "Binary operator types must match!");
2969 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's
2970 // worth handling here.
2971 if (N2C && N2C->isNullValue())
2973 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X
2980 assert(VT.isInteger() && "This operator does not apply to FP types!");
2981 assert(N1.getValueType() == N2.getValueType() &&
2982 N1.getValueType() == VT && "Binary operator types must match!");
2983 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so
2984 // it's worth handling here.
2985 if (N2C && N2C->isNullValue())
2995 assert(VT.isInteger() && "This operator does not apply to FP types!");
2996 assert(N1.getValueType() == N2.getValueType() &&
2997 N1.getValueType() == VT && "Binary operator types must match!");
3004 if (getTarget().Options.UnsafeFPMath) {
3005 if (Opcode == ISD::FADD) {
3007 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1))
3008 if (CFP->getValueAPF().isZero())
3011 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3012 if (CFP->getValueAPF().isZero())
3014 } else if (Opcode == ISD::FSUB) {
3016 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2))
3017 if (CFP->getValueAPF().isZero())
3019 } else if (Opcode == ISD::FMUL) {
3020 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1);
3023 // If the first operand isn't the constant, try the second
3025 CFP = dyn_cast<ConstantFPSDNode>(N2);
3032 return SDValue(CFP,0);
3034 if (CFP->isExactlyValue(1.0))
3039 assert(VT.isFloatingPoint() && "This operator only applies to FP types!");
3040 assert(N1.getValueType() == N2.getValueType() &&
3041 N1.getValueType() == VT && "Binary operator types must match!");
3043 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match.
3044 assert(N1.getValueType() == VT &&
3045 N1.getValueType().isFloatingPoint() &&
3046 N2.getValueType().isFloatingPoint() &&
3047 "Invalid FCOPYSIGN!");
3054 assert(VT == N1.getValueType() &&
3055 "Shift operators return type must be the same as their first arg");
3056 assert(VT.isInteger() && N2.getValueType().isInteger() &&
3057 "Shifts only work on integers");
3058 assert((!VT.isVector() || VT == N2.getValueType()) &&
3059 "Vector shift amounts must be in the same as their first arg");
3060 // Verify that the shift amount VT is bit enough to hold valid shift
3061 // amounts. This catches things like trying to shift an i1024 value by an
3062 // i8, which is easy to fall into in generic code that uses
3063 // TLI.getShiftAmount().
3064 assert(N2.getValueType().getSizeInBits() >=
3065 Log2_32_Ceil(N1.getValueType().getSizeInBits()) &&
3066 "Invalid use of small shift amount with oversized value!");
3068 // Always fold shifts of i1 values so the code generator doesn't need to
3069 // handle them. Since we know the size of the shift has to be less than the
3070 // size of the value, the shift/rotate count is guaranteed to be zero.
3073 if (N2C && N2C->isNullValue())
3076 case ISD::FP_ROUND_INREG: {
3077 EVT EVT = cast<VTSDNode>(N2)->getVT();
3078 assert(VT == N1.getValueType() && "Not an inreg round!");
3079 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() &&
3080 "Cannot FP_ROUND_INREG integer types");
3081 assert(EVT.isVector() == VT.isVector() &&
3082 "FP_ROUND_INREG type should be vector iff the operand "
3084 assert((!EVT.isVector() ||
3085 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3086 "Vector element counts must match in FP_ROUND_INREG");
3087 assert(EVT.bitsLE(VT) && "Not rounding down!");
3089 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding.
3093 assert(VT.isFloatingPoint() &&
3094 N1.getValueType().isFloatingPoint() &&
3095 VT.bitsLE(N1.getValueType()) &&
3096 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
3097 if (N1.getValueType() == VT) return N1; // noop conversion.
3099 case ISD::AssertSext:
3100 case ISD::AssertZext: {
3101 EVT EVT = cast<VTSDNode>(N2)->getVT();
3102 assert(VT == N1.getValueType() && "Not an inreg extend!");
3103 assert(VT.isInteger() && EVT.isInteger() &&
3104 "Cannot *_EXTEND_INREG FP types");
3105 assert(!EVT.isVector() &&
3106 "AssertSExt/AssertZExt type should be the vector element type "
3107 "rather than the vector type!");
3108 assert(EVT.bitsLE(VT) && "Not extending!");
3109 if (VT == EVT) return N1; // noop assertion.
3112 case ISD::SIGN_EXTEND_INREG: {
3113 EVT EVT = cast<VTSDNode>(N2)->getVT();
3114 assert(VT == N1.getValueType() && "Not an inreg extend!");
3115 assert(VT.isInteger() && EVT.isInteger() &&
3116 "Cannot *_EXTEND_INREG FP types");
3117 assert(EVT.isVector() == VT.isVector() &&
3118 "SIGN_EXTEND_INREG type should be vector iff the operand "
3120 assert((!EVT.isVector() ||
3121 EVT.getVectorNumElements() == VT.getVectorNumElements()) &&
3122 "Vector element counts must match in SIGN_EXTEND_INREG");
3123 assert(EVT.bitsLE(VT) && "Not extending!");
3124 if (EVT == VT) return N1; // Not actually extending
3127 APInt Val = N1C->getAPIntValue();
3128 unsigned FromBits = EVT.getScalarType().getSizeInBits();
3129 Val <<= Val.getBitWidth()-FromBits;
3130 Val = Val.ashr(Val.getBitWidth()-FromBits);
3131 return getConstant(Val, VT);
3135 case ISD::EXTRACT_VECTOR_ELT:
3136 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
3137 if (N1.getOpcode() == ISD::UNDEF)
3138 return getUNDEF(VT);
3140 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
3141 // expanding copies of large vectors from registers.
3143 N1.getOpcode() == ISD::CONCAT_VECTORS &&
3144 N1.getNumOperands() > 0) {
3146 N1.getOperand(0).getValueType().getVectorNumElements();
3147 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT,
3148 N1.getOperand(N2C->getZExtValue() / Factor),
3149 getConstant(N2C->getZExtValue() % Factor,
3150 N2.getValueType()));
3153 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
3154 // expanding large vector constants.
3155 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) {
3156 SDValue Elt = N1.getOperand(N2C->getZExtValue());
3158 if (VT != Elt.getValueType())
3159 // If the vector element type is not legal, the BUILD_VECTOR operands
3160 // are promoted and implicitly truncated, and the result implicitly
3161 // extended. Make that explicit here.
3162 Elt = getAnyExtOrTrunc(Elt, DL, VT);
3167 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
3168 // operations are lowered to scalars.
3169 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) {
3170 // If the indices are the same, return the inserted element else
3171 // if the indices are known different, extract the element from
3172 // the original vector.
3173 SDValue N1Op2 = N1.getOperand(2);
3174 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode());
3176 if (N1Op2C && N2C) {
3177 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) {
3178 if (VT == N1.getOperand(1).getValueType())
3179 return N1.getOperand(1);
3181 return getSExtOrTrunc(N1.getOperand(1), DL, VT);
3184 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2);
3188 case ISD::EXTRACT_ELEMENT:
3189 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!");
3190 assert(!N1.getValueType().isVector() && !VT.isVector() &&
3191 (N1.getValueType().isInteger() == VT.isInteger()) &&
3192 N1.getValueType() != VT &&
3193 "Wrong types for EXTRACT_ELEMENT!");
3195 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
3196 // 64-bit integers into 32-bit parts. Instead of building the extract of
3197 // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
3198 if (N1.getOpcode() == ISD::BUILD_PAIR)
3199 return N1.getOperand(N2C->getZExtValue());
3201 // EXTRACT_ELEMENT of a constant int is also very common.
3202 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3203 unsigned ElementSize = VT.getSizeInBits();
3204 unsigned Shift = ElementSize * N2C->getZExtValue();
3205 APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
3206 return getConstant(ShiftedVal.trunc(ElementSize), VT);
3209 case ISD::EXTRACT_SUBVECTOR: {
3211 if (VT.isSimple() && N1.getValueType().isSimple()) {
3212 assert(VT.isVector() && N1.getValueType().isVector() &&
3213 "Extract subvector VTs must be a vectors!");
3214 assert(VT.getVectorElementType() ==
3215 N1.getValueType().getVectorElementType() &&
3216 "Extract subvector VTs must have the same element type!");
3217 assert(VT.getSimpleVT() <= N1.getSimpleValueType() &&
3218 "Extract subvector must be from larger vector to smaller vector!");
3220 if (isa<ConstantSDNode>(Index.getNode())) {
3221 assert((VT.getVectorNumElements() +
3222 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3223 <= N1.getValueType().getVectorNumElements())
3224 && "Extract subvector overflow!");
3227 // Trivial extraction.
3228 if (VT.getSimpleVT() == N1.getSimpleValueType())
3235 // Perform trivial constant folding.
3236 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1.getNode(), N2.getNode());
3237 if (SV.getNode()) return SV;
3239 // Canonicalize constant to RHS if commutative.
3240 if (N1C && !N2C && isCommutativeBinOp(Opcode)) {
3241 std::swap(N1C, N2C);
3245 // Constant fold FP operations.
3246 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode());
3247 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode());
3249 if (!N2CFP && isCommutativeBinOp(Opcode)) {
3250 // Canonicalize constant to RHS if commutative.
3251 std::swap(N1CFP, N2CFP);
3254 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
3255 APFloat::opStatus s;
3258 s = V1.add(V2, APFloat::rmNearestTiesToEven);
3259 if (s != APFloat::opInvalidOp)
3260 return getConstantFP(V1, VT);
3263 s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
3264 if (s!=APFloat::opInvalidOp)
3265 return getConstantFP(V1, VT);
3268 s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
3269 if (s!=APFloat::opInvalidOp)
3270 return getConstantFP(V1, VT);
3273 s = V1.divide(V2, APFloat::rmNearestTiesToEven);
3274 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3275 return getConstantFP(V1, VT);
3278 s = V1.mod(V2, APFloat::rmNearestTiesToEven);
3279 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
3280 return getConstantFP(V1, VT);
3282 case ISD::FCOPYSIGN:
3284 return getConstantFP(V1, VT);
3289 if (Opcode == ISD::FP_ROUND) {
3290 APFloat V = N1CFP->getValueAPF(); // make copy
3292 // This can return overflow, underflow, or inexact; we don't care.
3293 // FIXME need to be more flexible about rounding mode.
3294 (void)V.convert(EVTToAPFloatSemantics(VT),
3295 APFloat::rmNearestTiesToEven, &ignored);
3296 return getConstantFP(V, VT);
3300 // Canonicalize an UNDEF to the RHS, even over a constant.
3301 if (N1.getOpcode() == ISD::UNDEF) {
3302 if (isCommutativeBinOp(Opcode)) {
3306 case ISD::FP_ROUND_INREG:
3307 case ISD::SIGN_EXTEND_INREG:
3313 return N1; // fold op(undef, arg2) -> undef
3321 return getConstant(0, VT); // fold op(undef, arg2) -> 0
3322 // For vectors, we can't easily build an all zero vector, just return
3329 // Fold a bunch of operators when the RHS is undef.
3330 if (N2.getOpcode() == ISD::UNDEF) {
3333 if (N1.getOpcode() == ISD::UNDEF)
3334 // Handle undef ^ undef -> 0 special case. This is a common
3336 return getConstant(0, VT);
3346 return N2; // fold op(arg1, undef) -> undef
3352 if (getTarget().Options.UnsafeFPMath)
3360 return getConstant(0, VT); // fold op(arg1, undef) -> 0
3361 // For vectors, we can't easily build an all zero vector, just return
3366 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT);
3367 // For vectors, we can't easily build an all one vector, just return
3375 // Memoize this node if possible.
3377 SDVTList VTs = getVTList(VT);
3378 if (VT != MVT::Glue) {
3379 SDValue Ops[] = { N1, N2 };
3380 FoldingSetNodeID ID;
3381 AddNodeIDNode(ID, Opcode, VTs, Ops);
3383 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3384 return SDValue(E, 0);
3386 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3387 DL.getDebugLoc(), VTs, N1, N2);
3388 CSEMap.InsertNode(N, IP);
3390 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
3391 DL.getDebugLoc(), VTs, N1, N2);
3394 AllNodes.push_back(N);
3398 return SDValue(N, 0);
3401 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3402 SDValue N1, SDValue N2, SDValue N3) {
3403 // Perform various simplifications.
3404 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
3407 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
3408 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
3409 ConstantFPSDNode *N3CFP = dyn_cast<ConstantFPSDNode>(N3);
3410 if (N1CFP && N2CFP && N3CFP) {
3411 APFloat V1 = N1CFP->getValueAPF();
3412 const APFloat &V2 = N2CFP->getValueAPF();
3413 const APFloat &V3 = N3CFP->getValueAPF();
3414 APFloat::opStatus s =
3415 V1.fusedMultiplyAdd(V2, V3, APFloat::rmNearestTiesToEven);
3416 if (s != APFloat::opInvalidOp)
3417 return getConstantFP(V1, VT);
3421 case ISD::CONCAT_VECTORS:
3422 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to
3423 // one big BUILD_VECTOR.
3424 if (N1.getOpcode() == ISD::BUILD_VECTOR &&
3425 N2.getOpcode() == ISD::BUILD_VECTOR &&
3426 N3.getOpcode() == ISD::BUILD_VECTOR) {
3427 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(),
3428 N1.getNode()->op_end());
3429 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end());
3430 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end());
3431 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts);
3435 // Use FoldSetCC to simplify SETCC's.
3436 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL);
3437 if (Simp.getNode()) return Simp;
3442 if (N1C->getZExtValue())
3443 return N2; // select true, X, Y -> X
3444 return N3; // select false, X, Y -> Y
3447 if (N2 == N3) return N2; // select C, X, X -> X
3449 case ISD::VECTOR_SHUFFLE:
3450 llvm_unreachable("should use getVectorShuffle constructor!");
3451 case ISD::INSERT_SUBVECTOR: {
3453 if (VT.isSimple() && N1.getValueType().isSimple()
3454 && N2.getValueType().isSimple()) {
3455 assert(VT.isVector() && N1.getValueType().isVector() &&
3456 N2.getValueType().isVector() &&
3457 "Insert subvector VTs must be a vectors");
3458 assert(VT == N1.getValueType() &&
3459 "Dest and insert subvector source types must match!");
3460 assert(N2.getSimpleValueType() <= N1.getSimpleValueType() &&
3461 "Insert subvector must be from smaller vector to larger vector!");
3462 if (isa<ConstantSDNode>(Index.getNode())) {
3463 assert((N2.getValueType().getVectorNumElements() +
3464 cast<ConstantSDNode>(Index.getNode())->getZExtValue()
3465 <= VT.getVectorNumElements())
3466 && "Insert subvector overflow!");
3469 // Trivial insertion.
3470 if (VT.getSimpleVT() == N2.getSimpleValueType())
3476 // Fold bit_convert nodes from a type to themselves.
3477 if (N1.getValueType() == VT)
3482 // Memoize node if it doesn't produce a flag.
3484 SDVTList VTs = getVTList(VT);
3485 if (VT != MVT::Glue) {
3486 SDValue Ops[] = { N1, N2, N3 };
3487 FoldingSetNodeID ID;
3488 AddNodeIDNode(ID, Opcode, VTs, Ops);
3490 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3491 return SDValue(E, 0);
3493 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3494 DL.getDebugLoc(), VTs, N1, N2, N3);
3495 CSEMap.InsertNode(N, IP);
3497 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
3498 DL.getDebugLoc(), VTs, N1, N2, N3);
3501 AllNodes.push_back(N);
3505 return SDValue(N, 0);
3508 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3509 SDValue N1, SDValue N2, SDValue N3,
3511 SDValue Ops[] = { N1, N2, N3, N4 };
3512 return getNode(Opcode, DL, VT, Ops);
3515 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
3516 SDValue N1, SDValue N2, SDValue N3,
3517 SDValue N4, SDValue N5) {
3518 SDValue Ops[] = { N1, N2, N3, N4, N5 };
3519 return getNode(Opcode, DL, VT, Ops);
3522 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all
3523 /// the incoming stack arguments to be loaded from the stack.
3524 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) {
3525 SmallVector<SDValue, 8> ArgChains;
3527 // Include the original chain at the beginning of the list. When this is
3528 // used by target LowerCall hooks, this helps legalize find the
3529 // CALLSEQ_BEGIN node.
3530 ArgChains.push_back(Chain);
3532 // Add a chain value for each stack argument.
3533 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(),
3534 UE = getEntryNode().getNode()->use_end(); U != UE; ++U)
3535 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U))
3536 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr()))
3537 if (FI->getIndex() < 0)
3538 ArgChains.push_back(SDValue(L, 1));
3540 // Build a tokenfactor for all the chains.
3541 return getNode(ISD::TokenFactor, SDLoc(Chain), MVT::Other, ArgChains);
3544 /// getMemsetValue - Vectorized representation of the memset value
3546 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG,
3548 assert(Value.getOpcode() != ISD::UNDEF);
3550 unsigned NumBits = VT.getScalarType().getSizeInBits();
3551 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
3552 assert(C->getAPIntValue().getBitWidth() == 8);
3553 APInt Val = APInt::getSplat(NumBits, C->getAPIntValue());
3555 return DAG.getConstant(Val, VT);
3556 return DAG.getConstantFP(APFloat(DAG.EVTToAPFloatSemantics(VT), Val), VT);
3559 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value);
3561 // Use a multiplication with 0x010101... to extend the input to the
3563 APInt Magic = APInt::getSplat(NumBits, APInt(8, 0x01));
3564 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT));
3570 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
3571 /// used when a memcpy is turned into a memset when the source is a constant
3573 static SDValue getMemsetStringVal(EVT VT, SDLoc dl, SelectionDAG &DAG,
3574 const TargetLowering &TLI, StringRef Str) {
3575 // Handle vector with all elements zero.
3578 return DAG.getConstant(0, VT);
3579 else if (VT == MVT::f32 || VT == MVT::f64)
3580 return DAG.getConstantFP(0.0, VT);
3581 else if (VT.isVector()) {
3582 unsigned NumElts = VT.getVectorNumElements();
3583 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64;
3584 return DAG.getNode(ISD::BITCAST, dl, VT,
3585 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(),
3588 llvm_unreachable("Expected type!");
3591 assert(!VT.isVector() && "Can't handle vector type here!");
3592 unsigned NumVTBits = VT.getSizeInBits();
3593 unsigned NumVTBytes = NumVTBits / 8;
3594 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size()));
3596 APInt Val(NumVTBits, 0);
3597 if (TLI.isLittleEndian()) {
3598 for (unsigned i = 0; i != NumBytes; ++i)
3599 Val |= (uint64_t)(unsigned char)Str[i] << i*8;
3601 for (unsigned i = 0; i != NumBytes; ++i)
3602 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8;
3605 // If the "cost" of materializing the integer immediate is less than the cost
3606 // of a load, then it is cost effective to turn the load into the immediate.
3607 Type *Ty = VT.getTypeForEVT(*DAG.getContext());
3608 if (TLI.shouldConvertConstantLoadToIntImm(Val, Ty))
3609 return DAG.getConstant(Val, VT);
3610 return SDValue(nullptr, 0);
3613 /// getMemBasePlusOffset - Returns base and offset node for the
3615 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, SDLoc dl,
3616 SelectionDAG &DAG) {
3617 EVT VT = Base.getValueType();
3618 return DAG.getNode(ISD::ADD, dl,
3619 VT, Base, DAG.getConstant(Offset, VT));
3622 /// isMemSrcFromString - Returns true if memcpy source is a string constant.
3624 static bool isMemSrcFromString(SDValue Src, StringRef &Str) {
3625 unsigned SrcDelta = 0;
3626 GlobalAddressSDNode *G = nullptr;
3627 if (Src.getOpcode() == ISD::GlobalAddress)
3628 G = cast<GlobalAddressSDNode>(Src);
3629 else if (Src.getOpcode() == ISD::ADD &&
3630 Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
3631 Src.getOperand(1).getOpcode() == ISD::Constant) {
3632 G = cast<GlobalAddressSDNode>(Src.getOperand(0));
3633 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue();
3638 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false);
3641 /// FindOptimalMemOpLowering - Determines the optimial series memory ops
3642 /// to replace the memset / memcpy. Return true if the number of memory ops
3643 /// is below the threshold. It returns the types of the sequence of
3644 /// memory ops to perform memset / memcpy by reference.
3645 static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps,
3646 unsigned Limit, uint64_t Size,
3647 unsigned DstAlign, unsigned SrcAlign,
3653 const TargetLowering &TLI) {
3654 assert((SrcAlign == 0 || SrcAlign >= DstAlign) &&
3655 "Expecting memcpy / memset source to meet alignment requirement!");
3656 // If 'SrcAlign' is zero, that means the memory operation does not need to
3657 // load the value, i.e. memset or memcpy from constant string. Otherwise,
3658 // it's the inferred alignment of the source. 'DstAlign', on the other hand,
3659 // is the specified alignment of the memory operation. If it is zero, that
3660 // means it's possible to change the alignment of the destination.
3661 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does
3662 // not need to be loaded.
3663 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign,
3664 IsMemset, ZeroMemset, MemcpyStrSrc,
3665 DAG.getMachineFunction());
3667 if (VT == MVT::Other) {
3669 if (DstAlign >= TLI.getDataLayout()->getPointerPrefAlignment(AS) ||
3670 TLI.allowsUnalignedMemoryAccesses(VT, AS)) {
3671 VT = TLI.getPointerTy();
3673 switch (DstAlign & 7) {
3674 case 0: VT = MVT::i64; break;
3675 case 4: VT = MVT::i32; break;
3676 case 2: VT = MVT::i16; break;
3677 default: VT = MVT::i8; break;
3682 while (!TLI.isTypeLegal(LVT))
3683 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1);
3684 assert(LVT.isInteger());
3690 unsigned NumMemOps = 0;
3692 unsigned VTSize = VT.getSizeInBits() / 8;
3693 while (VTSize > Size) {
3694 // For now, only use non-vector load / store's for the left-over pieces.
3699 if (VT.isVector() || VT.isFloatingPoint()) {
3700 NewVT = (VT.getSizeInBits() > 64) ? MVT::i64 : MVT::i32;
3701 if (TLI.isOperationLegalOrCustom(ISD::STORE, NewVT) &&
3702 TLI.isSafeMemOpType(NewVT.getSimpleVT()))
3704 else if (NewVT == MVT::i64 &&
3705 TLI.isOperationLegalOrCustom(ISD::STORE, MVT::f64) &&
3706 TLI.isSafeMemOpType(MVT::f64)) {
3707 // i64 is usually not legal on 32-bit targets, but f64 may be.
3715 NewVT = (MVT::SimpleValueType)(NewVT.getSimpleVT().SimpleTy - 1);
3716 if (NewVT == MVT::i8)
3718 } while (!TLI.isSafeMemOpType(NewVT.getSimpleVT()));
3720 NewVTSize = NewVT.getSizeInBits() / 8;
3722 // If the new VT cannot cover all of the remaining bits, then consider
3723 // issuing a (or a pair of) unaligned and overlapping load / store.
3724 // FIXME: Only does this for 64-bit or more since we don't have proper
3725 // cost model for unaligned load / store.
3728 if (NumMemOps && AllowOverlap &&
3729 VTSize >= 8 && NewVTSize < Size &&
3730 TLI.allowsUnalignedMemoryAccesses(VT, AS, &Fast) && Fast)
3738 if (++NumMemOps > Limit)
3741 MemOps.push_back(VT);
3748 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3749 SDValue Chain, SDValue Dst,
3750 SDValue Src, uint64_t Size,
3751 unsigned Align, bool isVol,
3753 MachinePointerInfo DstPtrInfo,
3754 MachinePointerInfo SrcPtrInfo) {
3755 // Turn a memcpy of undef to nop.
3756 if (Src.getOpcode() == ISD::UNDEF)
3759 // Expand memcpy to a series of load and store ops if the size operand falls
3760 // below a certain threshold.
3761 // TODO: In the AlwaysInline case, if the size is big then generate a loop
3762 // rather than maybe a humongous number of loads and stores.
3763 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3764 std::vector<EVT> MemOps;
3765 bool DstAlignCanChange = false;
3766 MachineFunction &MF = DAG.getMachineFunction();
3767 MachineFrameInfo *MFI = MF.getFrameInfo();
3769 MF.getFunction()->getAttributes().
3770 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3771 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3772 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3773 DstAlignCanChange = true;
3774 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3775 if (Align > SrcAlign)
3778 bool CopyFromStr = isMemSrcFromString(Src, Str);
3779 bool isZeroStr = CopyFromStr && Str.empty();
3780 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize);
3782 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3783 (DstAlignCanChange ? 0 : Align),
3784 (isZeroStr ? 0 : SrcAlign),
3785 false, false, CopyFromStr, true, DAG, TLI))
3788 if (DstAlignCanChange) {
3789 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3790 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3792 // Don't promote to an alignment that would require dynamic stack
3794 const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo();
3795 if (!TRI->needsStackRealignment(MF))
3796 while (NewAlign > Align &&
3797 TLI.getDataLayout()->exceedsNaturalStackAlignment(NewAlign))
3800 if (NewAlign > Align) {
3801 // Give the stack frame object a larger alignment if needed.
3802 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3803 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3808 SmallVector<SDValue, 8> OutChains;
3809 unsigned NumMemOps = MemOps.size();
3810 uint64_t SrcOff = 0, DstOff = 0;
3811 for (unsigned i = 0; i != NumMemOps; ++i) {
3813 unsigned VTSize = VT.getSizeInBits() / 8;
3814 SDValue Value, Store;
3816 if (VTSize > Size) {
3817 // Issuing an unaligned load / store pair that overlaps with the previous
3818 // pair. Adjust the offset accordingly.
3819 assert(i == NumMemOps-1 && i != 0);
3820 SrcOff -= VTSize - Size;
3821 DstOff -= VTSize - Size;
3825 (isZeroStr || (VT.isInteger() && !VT.isVector()))) {
3826 // It's unlikely a store of a vector immediate can be done in a single
3827 // instruction. It would require a load from a constantpool first.
3828 // We only handle zero vectors here.
3829 // FIXME: Handle other cases where store of vector immediate is done in
3830 // a single instruction.
3831 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff));
3832 if (Value.getNode())
3833 Store = DAG.getStore(Chain, dl, Value,
3834 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3835 DstPtrInfo.getWithOffset(DstOff), isVol,
3839 if (!Store.getNode()) {
3840 // The type might not be legal for the target. This should only happen
3841 // if the type is smaller than a legal type, as on PPC, so the right
3842 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify
3843 // to Load/Store if NVT==VT.
3844 // FIXME does the case above also need this?
3845 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT);
3846 assert(NVT.bitsGE(VT));
3847 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain,
3848 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3849 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false,
3850 MinAlign(SrcAlign, SrcOff));
3851 Store = DAG.getTruncStore(Chain, dl, Value,
3852 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3853 DstPtrInfo.getWithOffset(DstOff), VT, isVol,
3856 OutChains.push_back(Store);
3862 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3865 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, SDLoc dl,
3866 SDValue Chain, SDValue Dst,
3867 SDValue Src, uint64_t Size,
3868 unsigned Align, bool isVol,
3870 MachinePointerInfo DstPtrInfo,
3871 MachinePointerInfo SrcPtrInfo) {
3872 // Turn a memmove of undef to nop.
3873 if (Src.getOpcode() == ISD::UNDEF)
3876 // Expand memmove to a series of load and store ops if the size operand falls
3877 // below a certain threshold.
3878 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3879 std::vector<EVT> MemOps;
3880 bool DstAlignCanChange = false;
3881 MachineFunction &MF = DAG.getMachineFunction();
3882 MachineFrameInfo *MFI = MF.getFrameInfo();
3883 bool OptSize = MF.getFunction()->getAttributes().
3884 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3885 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3886 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3887 DstAlignCanChange = true;
3888 unsigned SrcAlign = DAG.InferPtrAlignment(Src);
3889 if (Align > SrcAlign)
3891 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize);
3893 if (!FindOptimalMemOpLowering(MemOps, Limit, Size,
3894 (DstAlignCanChange ? 0 : Align), SrcAlign,
3895 false, false, false, false, DAG, TLI))
3898 if (DstAlignCanChange) {
3899 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3900 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3901 if (NewAlign > Align) {
3902 // Give the stack frame object a larger alignment if needed.
3903 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3904 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
3909 uint64_t SrcOff = 0, DstOff = 0;
3910 SmallVector<SDValue, 8> LoadValues;
3911 SmallVector<SDValue, 8> LoadChains;
3912 SmallVector<SDValue, 8> OutChains;
3913 unsigned NumMemOps = MemOps.size();
3914 for (unsigned i = 0; i < NumMemOps; i++) {
3916 unsigned VTSize = VT.getSizeInBits() / 8;
3919 Value = DAG.getLoad(VT, dl, Chain,
3920 getMemBasePlusOffset(Src, SrcOff, dl, DAG),
3921 SrcPtrInfo.getWithOffset(SrcOff), isVol,
3922 false, false, SrcAlign);
3923 LoadValues.push_back(Value);
3924 LoadChains.push_back(Value.getValue(1));
3927 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, LoadChains);
3929 for (unsigned i = 0; i < NumMemOps; i++) {
3931 unsigned VTSize = VT.getSizeInBits() / 8;
3934 Store = DAG.getStore(Chain, dl, LoadValues[i],
3935 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
3936 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align);
3937 OutChains.push_back(Store);
3941 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
3944 /// \brief Lower the call to 'memset' intrinsic function into a series of store
3947 /// \param DAG Selection DAG where lowered code is placed.
3948 /// \param dl Link to corresponding IR location.
3949 /// \param Chain Control flow dependency.
3950 /// \param Dst Pointer to destination memory location.
3951 /// \param Src Value of byte to write into the memory.
3952 /// \param Size Number of bytes to write.
3953 /// \param Align Alignment of the destination in bytes.
3954 /// \param isVol True if destination is volatile.
3955 /// \param DstPtrInfo IR information on the memory pointer.
3956 /// \returns New head in the control flow, if lowering was successful, empty
3957 /// SDValue otherwise.
3959 /// The function tries to replace 'llvm.memset' intrinsic with several store
3960 /// operations and value calculation code. This is usually profitable for small
3962 static SDValue getMemsetStores(SelectionDAG &DAG, SDLoc dl,
3963 SDValue Chain, SDValue Dst,
3964 SDValue Src, uint64_t Size,
3965 unsigned Align, bool isVol,
3966 MachinePointerInfo DstPtrInfo) {
3967 // Turn a memset of undef to nop.
3968 if (Src.getOpcode() == ISD::UNDEF)
3971 // Expand memset to a series of load/store ops if the size operand
3972 // falls below a certain threshold.
3973 const TargetLowering &TLI = DAG.getTargetLoweringInfo();
3974 std::vector<EVT> MemOps;
3975 bool DstAlignCanChange = false;
3976 MachineFunction &MF = DAG.getMachineFunction();
3977 MachineFrameInfo *MFI = MF.getFrameInfo();
3978 bool OptSize = MF.getFunction()->getAttributes().
3979 hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize);
3980 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst);
3981 if (FI && !MFI->isFixedObjectIndex(FI->getIndex()))
3982 DstAlignCanChange = true;
3984 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue();
3985 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize),
3986 Size, (DstAlignCanChange ? 0 : Align), 0,
3987 true, IsZeroVal, false, true, DAG, TLI))
3990 if (DstAlignCanChange) {
3991 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext());
3992 unsigned NewAlign = (unsigned) TLI.getDataLayout()->getABITypeAlignment(Ty);
3993 if (NewAlign > Align) {
3994 // Give the stack frame object a larger alignment if needed.
3995 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign)
3996 MFI->setObjectAlignment(FI->getIndex(), NewAlign);
4001 SmallVector<SDValue, 8> OutChains;
4002 uint64_t DstOff = 0;
4003 unsigned NumMemOps = MemOps.size();
4005 // Find the largest store and generate the bit pattern for it.
4006 EVT LargestVT = MemOps[0];
4007 for (unsigned i = 1; i < NumMemOps; i++)
4008 if (MemOps[i].bitsGT(LargestVT))
4009 LargestVT = MemOps[i];
4010 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl);
4012 for (unsigned i = 0; i < NumMemOps; i++) {
4014 unsigned VTSize = VT.getSizeInBits() / 8;
4015 if (VTSize > Size) {
4016 // Issuing an unaligned load / store pair that overlaps with the previous
4017 // pair. Adjust the offset accordingly.
4018 assert(i == NumMemOps-1 && i != 0);
4019 DstOff -= VTSize - Size;
4022 // If this store is smaller than the largest store see whether we can get
4023 // the smaller value for free with a truncate.
4024 SDValue Value = MemSetValue;
4025 if (VT.bitsLT(LargestVT)) {
4026 if (!LargestVT.isVector() && !VT.isVector() &&
4027 TLI.isTruncateFree(LargestVT, VT))
4028 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue);
4030 Value = getMemsetValue(Src, VT, DAG, dl);
4032 assert(Value.getValueType() == VT && "Value with wrong type.");
4033 SDValue Store = DAG.getStore(Chain, dl, Value,
4034 getMemBasePlusOffset(Dst, DstOff, dl, DAG),
4035 DstPtrInfo.getWithOffset(DstOff),
4036 isVol, false, Align);
4037 OutChains.push_back(Store);
4038 DstOff += VT.getSizeInBits() / 8;
4042 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, OutChains);
4045 SDValue SelectionDAG::getMemcpy(SDValue Chain, SDLoc dl, SDValue Dst,
4046 SDValue Src, SDValue Size,
4047 unsigned Align, bool isVol, bool AlwaysInline,
4048 MachinePointerInfo DstPtrInfo,
4049 MachinePointerInfo SrcPtrInfo) {
4050 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4052 // Check to see if we should lower the memcpy to loads and stores first.
4053 // For cases within the target-specified limits, this is the best choice.
4054 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4056 // Memcpy with size zero? Just return the original chain.
4057 if (ConstantSize->isNullValue())
4060 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4061 ConstantSize->getZExtValue(),Align,
4062 isVol, false, DstPtrInfo, SrcPtrInfo);
4063 if (Result.getNode())
4067 // Then check to see if we should lower the memcpy with target-specific
4068 // code. If the target chooses to do this, this is the next best.
4070 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align,
4071 isVol, AlwaysInline,
4072 DstPtrInfo, SrcPtrInfo);
4073 if (Result.getNode())
4076 // If we really need inline code and the target declined to provide it,
4077 // use a (potentially long) sequence of loads and stores.
4079 assert(ConstantSize && "AlwaysInline requires a constant size!");
4080 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src,
4081 ConstantSize->getZExtValue(), Align, isVol,
4082 true, DstPtrInfo, SrcPtrInfo);
4085 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc
4086 // memcpy is not guaranteed to be safe. libc memcpys aren't required to
4087 // respect volatile, so they may do things like read or write memory
4088 // beyond the given memory regions. But fixing this isn't easy, and most
4089 // people don't care.
4091 const TargetLowering *TLI = TM.getTargetLowering();
4093 // Emit a library call.
4094 TargetLowering::ArgListTy Args;
4095 TargetLowering::ArgListEntry Entry;
4096 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4097 Entry.Node = Dst; Args.push_back(Entry);
4098 Entry.Node = Src; Args.push_back(Entry);
4099 Entry.Node = Size; Args.push_back(Entry);
4100 // FIXME: pass in SDLoc
4102 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4103 false, false, false, false, 0,
4104 TLI->getLibcallCallingConv(RTLIB::MEMCPY),
4105 /*isTailCall=*/false,
4106 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4107 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMCPY),
4108 TLI->getPointerTy()),
4110 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4112 return CallResult.second;
4115 SDValue SelectionDAG::getMemmove(SDValue Chain, SDLoc dl, SDValue Dst,
4116 SDValue Src, SDValue Size,
4117 unsigned Align, bool isVol,
4118 MachinePointerInfo DstPtrInfo,
4119 MachinePointerInfo SrcPtrInfo) {
4120 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4122 // Check to see if we should lower the memmove to loads and stores first.
4123 // For cases within the target-specified limits, this is the best choice.
4124 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4126 // Memmove with size zero? Just return the original chain.
4127 if (ConstantSize->isNullValue())
4131 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src,
4132 ConstantSize->getZExtValue(), Align, isVol,
4133 false, DstPtrInfo, SrcPtrInfo);
4134 if (Result.getNode())
4138 // Then check to see if we should lower the memmove with target-specific
4139 // code. If the target chooses to do this, this is the next best.
4141 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4142 DstPtrInfo, SrcPtrInfo);
4143 if (Result.getNode())
4146 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may
4147 // not be safe. See memcpy above for more details.
4149 const TargetLowering *TLI = TM.getTargetLowering();
4151 // Emit a library call.
4152 TargetLowering::ArgListTy Args;
4153 TargetLowering::ArgListEntry Entry;
4154 Entry.Ty = TLI->getDataLayout()->getIntPtrType(*getContext());
4155 Entry.Node = Dst; Args.push_back(Entry);
4156 Entry.Node = Src; Args.push_back(Entry);
4157 Entry.Node = Size; Args.push_back(Entry);
4158 // FIXME: pass in SDLoc
4160 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4161 false, false, false, false, 0,
4162 TLI->getLibcallCallingConv(RTLIB::MEMMOVE),
4163 /*isTailCall=*/false,
4164 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false,
4165 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMMOVE),
4166 TLI->getPointerTy()),
4168 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4170 return CallResult.second;
4173 SDValue SelectionDAG::getMemset(SDValue Chain, SDLoc dl, SDValue Dst,
4174 SDValue Src, SDValue Size,
4175 unsigned Align, bool isVol,
4176 MachinePointerInfo DstPtrInfo) {
4177 assert(Align && "The SDAG layer expects explicit alignment and reserves 0");
4179 // Check to see if we should lower the memset to stores first.
4180 // For cases within the target-specified limits, this is the best choice.
4181 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
4183 // Memset with size zero? Just return the original chain.
4184 if (ConstantSize->isNullValue())
4188 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(),
4189 Align, isVol, DstPtrInfo);
4191 if (Result.getNode())
4195 // Then check to see if we should lower the memset with target-specific
4196 // code. If the target chooses to do this, this is the next best.
4198 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol,
4200 if (Result.getNode())
4203 // Emit a library call.
4204 const TargetLowering *TLI = TM.getTargetLowering();
4205 Type *IntPtrTy = TLI->getDataLayout()->getIntPtrType(*getContext());
4206 TargetLowering::ArgListTy Args;
4207 TargetLowering::ArgListEntry Entry;
4208 Entry.Node = Dst; Entry.Ty = IntPtrTy;
4209 Args.push_back(Entry);
4210 // Extend or truncate the argument to be an i32 value for the call.
4211 if (Src.getValueType().bitsGT(MVT::i32))
4212 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src);
4214 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src);
4216 Entry.Ty = Type::getInt32Ty(*getContext());
4217 Entry.isSExt = true;
4218 Args.push_back(Entry);
4220 Entry.Ty = IntPtrTy;
4221 Entry.isSExt = false;
4222 Args.push_back(Entry);
4223 // FIXME: pass in SDLoc
4225 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()),
4226 false, false, false, false, 0,
4227 TLI->getLibcallCallingConv(RTLIB::MEMSET),
4228 /*isTailCall=*/false,
4229 /*doesNotReturn*/false, /*isReturnValueUsed=*/false,
4230 getExternalSymbol(TLI->getLibcallName(RTLIB::MEMSET),
4231 TLI->getPointerTy()),
4233 std::pair<SDValue,SDValue> CallResult = TLI->LowerCallTo(CLI);
4235 return CallResult.second;
4238 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4239 SDVTList VTList, ArrayRef<SDValue> Ops,
4240 MachineMemOperand *MMO,
4241 AtomicOrdering SuccessOrdering,
4242 AtomicOrdering FailureOrdering,
4243 SynchronizationScope SynchScope) {
4244 FoldingSetNodeID ID;
4245 ID.AddInteger(MemVT.getRawBits());
4246 AddNodeIDNode(ID, Opcode, VTList, Ops);
4247 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4249 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4250 cast<AtomicSDNode>(E)->refineAlignment(MMO);
4251 return SDValue(E, 0);
4254 // Allocate the operands array for the node out of the BumpPtrAllocator, since
4255 // SDNode doesn't have access to it. This memory will be "leaked" when
4256 // the node is deallocated, but recovered when the allocator is released.
4257 // If the number of operands is less than 5 we use AtomicSDNode's internal
4259 unsigned NumOps = Ops.size();
4260 SDUse *DynOps = NumOps > 4 ? OperandAllocator.Allocate<SDUse>(NumOps)
4263 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl.getIROrder(),
4264 dl.getDebugLoc(), VTList, MemVT,
4265 Ops.data(), DynOps, NumOps, MMO,
4266 SuccessOrdering, FailureOrdering,
4268 CSEMap.InsertNode(N, IP);
4269 AllNodes.push_back(N);
4270 return SDValue(N, 0);
4273 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4274 SDVTList VTList, ArrayRef<SDValue> Ops,
4275 MachineMemOperand *MMO,
4276 AtomicOrdering Ordering,
4277 SynchronizationScope SynchScope) {
4278 return getAtomic(Opcode, dl, MemVT, VTList, Ops, MMO, Ordering,
4279 Ordering, SynchScope);
4282 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4283 SDValue Chain, SDValue Ptr, SDValue Cmp,
4284 SDValue Swp, MachinePointerInfo PtrInfo,
4286 AtomicOrdering SuccessOrdering,
4287 AtomicOrdering FailureOrdering,
4288 SynchronizationScope SynchScope) {
4289 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4290 Alignment = getEVTAlignment(MemVT);
4292 MachineFunction &MF = getMachineFunction();
4294 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE.
4295 // For now, atomics are considered to be volatile always.
4296 // FIXME: Volatile isn't really correct; we should keep track of atomic
4297 // orderings in the memoperand.
4298 unsigned Flags = MachineMemOperand::MOVolatile;
4299 if (Opcode != ISD::ATOMIC_STORE)
4300 Flags |= MachineMemOperand::MOLoad;
4301 if (Opcode != ISD::ATOMIC_LOAD)
4302 Flags |= MachineMemOperand::MOStore;
4304 MachineMemOperand *MMO =
4305 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment);
4307 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO,
4308 SuccessOrdering, FailureOrdering, SynchScope);
4311 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4313 SDValue Ptr, SDValue Cmp,
4314 SDValue Swp, MachineMemOperand *MMO,
4315 AtomicOrdering SuccessOrdering,
4316 AtomicOrdering FailureOrdering,
4317 SynchronizationScope SynchScope) {
4318 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op");
4319 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
4321 EVT VT = Cmp.getValueType();
4323 SDVTList VTs = getVTList(VT, MVT::Other);
4324 SDValue Ops[] = {Chain, Ptr, Cmp, Swp};
4325 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, SuccessOrdering,
4326 FailureOrdering, SynchScope);
4329 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4331 SDValue Ptr, SDValue Val,
4332 const Value* PtrVal,
4334 AtomicOrdering Ordering,
4335 SynchronizationScope SynchScope) {
4336 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4337 Alignment = getEVTAlignment(MemVT);
4339 MachineFunction &MF = getMachineFunction();
4340 // An atomic store does not load. An atomic load does not store.
4341 // (An atomicrmw obviously both loads and stores.)
4342 // For now, atomics are considered to be volatile always, and they are
4344 // FIXME: Volatile isn't really correct; we should keep track of atomic
4345 // orderings in the memoperand.
4346 unsigned Flags = MachineMemOperand::MOVolatile;
4347 if (Opcode != ISD::ATOMIC_STORE)
4348 Flags |= MachineMemOperand::MOLoad;
4349 if (Opcode != ISD::ATOMIC_LOAD)
4350 Flags |= MachineMemOperand::MOStore;
4352 MachineMemOperand *MMO =
4353 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags,
4354 MemVT.getStoreSize(), Alignment);
4356 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO,
4357 Ordering, SynchScope);
4360 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4362 SDValue Ptr, SDValue Val,
4363 MachineMemOperand *MMO,
4364 AtomicOrdering Ordering,
4365 SynchronizationScope SynchScope) {
4366 assert((Opcode == ISD::ATOMIC_LOAD_ADD ||
4367 Opcode == ISD::ATOMIC_LOAD_SUB ||
4368 Opcode == ISD::ATOMIC_LOAD_AND ||
4369 Opcode == ISD::ATOMIC_LOAD_OR ||
4370 Opcode == ISD::ATOMIC_LOAD_XOR ||
4371 Opcode == ISD::ATOMIC_LOAD_NAND ||
4372 Opcode == ISD::ATOMIC_LOAD_MIN ||
4373 Opcode == ISD::ATOMIC_LOAD_MAX ||
4374 Opcode == ISD::ATOMIC_LOAD_UMIN ||
4375 Opcode == ISD::ATOMIC_LOAD_UMAX ||
4376 Opcode == ISD::ATOMIC_SWAP ||
4377 Opcode == ISD::ATOMIC_STORE) &&
4378 "Invalid Atomic Op");
4380 EVT VT = Val.getValueType();
4382 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) :
4383 getVTList(VT, MVT::Other);
4384 SDValue Ops[] = {Chain, Ptr, Val};
4385 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4388 SDValue SelectionDAG::getAtomic(unsigned Opcode, SDLoc dl, EVT MemVT,
4389 EVT VT, SDValue Chain,
4391 MachineMemOperand *MMO,
4392 AtomicOrdering Ordering,
4393 SynchronizationScope SynchScope) {
4394 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op");
4396 SDVTList VTs = getVTList(VT, MVT::Other);
4397 SDValue Ops[] = {Chain, Ptr};
4398 return getAtomic(Opcode, dl, MemVT, VTs, Ops, MMO, Ordering, SynchScope);
4401 /// getMergeValues - Create a MERGE_VALUES node from the given operands.
4402 SDValue SelectionDAG::getMergeValues(ArrayRef<SDValue> Ops, SDLoc dl) {
4403 if (Ops.size() == 1)
4406 SmallVector<EVT, 4> VTs;
4407 VTs.reserve(Ops.size());
4408 for (unsigned i = 0; i < Ops.size(); ++i)
4409 VTs.push_back(Ops[i].getValueType());
4410 return getNode(ISD::MERGE_VALUES, dl, getVTList(VTs), Ops);
4414 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4415 ArrayRef<SDValue> Ops,
4416 EVT MemVT, MachinePointerInfo PtrInfo,
4417 unsigned Align, bool Vol,
4418 bool ReadMem, bool WriteMem) {
4419 if (Align == 0) // Ensure that codegen never sees alignment 0
4420 Align = getEVTAlignment(MemVT);
4422 MachineFunction &MF = getMachineFunction();
4425 Flags |= MachineMemOperand::MOStore;
4427 Flags |= MachineMemOperand::MOLoad;
4429 Flags |= MachineMemOperand::MOVolatile;
4430 MachineMemOperand *MMO =
4431 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align);
4433 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, MemVT, MMO);
4437 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, SDLoc dl, SDVTList VTList,
4438 ArrayRef<SDValue> Ops, EVT MemVT,
4439 MachineMemOperand *MMO) {
4440 assert((Opcode == ISD::INTRINSIC_VOID ||
4441 Opcode == ISD::INTRINSIC_W_CHAIN ||
4442 Opcode == ISD::PREFETCH ||
4443 Opcode == ISD::LIFETIME_START ||
4444 Opcode == ISD::LIFETIME_END ||
4445 (Opcode <= INT_MAX &&
4446 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) &&
4447 "Opcode is not a memory-accessing opcode!");
4449 // Memoize the node unless it returns a flag.
4450 MemIntrinsicSDNode *N;
4451 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4452 FoldingSetNodeID ID;
4453 AddNodeIDNode(ID, Opcode, VTList, Ops);
4454 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4456 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4457 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO);
4458 return SDValue(E, 0);
4461 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4462 dl.getDebugLoc(), VTList, Ops,
4464 CSEMap.InsertNode(N, IP);
4466 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl.getIROrder(),
4467 dl.getDebugLoc(), VTList, Ops,
4470 AllNodes.push_back(N);
4471 return SDValue(N, 0);
4474 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4475 /// MachinePointerInfo record from it. This is particularly useful because the
4476 /// code generator has many cases where it doesn't bother passing in a
4477 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4478 static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) {
4479 // If this is FI+Offset, we can model it.
4480 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr))
4481 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset);
4483 // If this is (FI+Offset1)+Offset2, we can model it.
4484 if (Ptr.getOpcode() != ISD::ADD ||
4485 !isa<ConstantSDNode>(Ptr.getOperand(1)) ||
4486 !isa<FrameIndexSDNode>(Ptr.getOperand(0)))
4487 return MachinePointerInfo();
4489 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex();
4490 return MachinePointerInfo::getFixedStack(FI, Offset+
4491 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue());
4494 /// InferPointerInfo - If the specified ptr/offset is a frame index, infer a
4495 /// MachinePointerInfo record from it. This is particularly useful because the
4496 /// code generator has many cases where it doesn't bother passing in a
4497 /// MachinePointerInfo to getLoad or getStore when it has "FI+Cst".
4498 static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) {
4499 // If the 'Offset' value isn't a constant, we can't handle this.
4500 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp))
4501 return InferPointerInfo(Ptr, OffsetNode->getSExtValue());
4502 if (OffsetOp.getOpcode() == ISD::UNDEF)
4503 return InferPointerInfo(Ptr);
4504 return MachinePointerInfo();
4509 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4510 EVT VT, SDLoc dl, SDValue Chain,
4511 SDValue Ptr, SDValue Offset,
4512 MachinePointerInfo PtrInfo, EVT MemVT,
4513 bool isVolatile, bool isNonTemporal, bool isInvariant,
4514 unsigned Alignment, const MDNode *TBAAInfo,
4515 const MDNode *Ranges) {
4516 assert(Chain.getValueType() == MVT::Other &&
4517 "Invalid chain type");
4518 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4519 Alignment = getEVTAlignment(VT);
4521 unsigned Flags = MachineMemOperand::MOLoad;
4523 Flags |= MachineMemOperand::MOVolatile;
4525 Flags |= MachineMemOperand::MONonTemporal;
4527 Flags |= MachineMemOperand::MOInvariant;
4529 // If we don't have a PtrInfo, infer the trivial frame index case to simplify
4531 if (PtrInfo.V.isNull())
4532 PtrInfo = InferPointerInfo(Ptr, Offset);
4534 MachineFunction &MF = getMachineFunction();
4535 MachineMemOperand *MMO =
4536 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment,
4538 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO);
4542 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
4543 EVT VT, SDLoc dl, SDValue Chain,
4544 SDValue Ptr, SDValue Offset, EVT MemVT,
4545 MachineMemOperand *MMO) {
4547 ExtType = ISD::NON_EXTLOAD;
4548 } else if (ExtType == ISD::NON_EXTLOAD) {
4549 assert(VT == MemVT && "Non-extending load from different memory type!");
4552 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) &&
4553 "Should only be an extending load, not truncating!");
4554 assert(VT.isInteger() == MemVT.isInteger() &&
4555 "Cannot convert from FP to Int or Int -> FP!");
4556 assert(VT.isVector() == MemVT.isVector() &&
4557 "Cannot use trunc store to convert to or from a vector!");
4558 assert((!VT.isVector() ||
4559 VT.getVectorNumElements() == MemVT.getVectorNumElements()) &&
4560 "Cannot use trunc store to change the number of vector elements!");
4563 bool Indexed = AM != ISD::UNINDEXED;
4564 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) &&
4565 "Unindexed load with an offset!");
4567 SDVTList VTs = Indexed ?
4568 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
4569 SDValue Ops[] = { Chain, Ptr, Offset };
4570 FoldingSetNodeID ID;
4571 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops);
4572 ID.AddInteger(MemVT.getRawBits());
4573 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(),
4574 MMO->isNonTemporal(),
4575 MMO->isInvariant()));
4576 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4578 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4579 cast<LoadSDNode>(E)->refineAlignment(MMO);
4580 return SDValue(E, 0);
4582 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl.getIROrder(),
4583 dl.getDebugLoc(), VTs, AM, ExtType,
4585 CSEMap.InsertNode(N, IP);
4586 AllNodes.push_back(N);
4587 return SDValue(N, 0);
4590 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4591 SDValue Chain, SDValue Ptr,
4592 MachinePointerInfo PtrInfo,
4593 bool isVolatile, bool isNonTemporal,
4594 bool isInvariant, unsigned Alignment,
4595 const MDNode *TBAAInfo,
4596 const MDNode *Ranges) {
4597 SDValue Undef = getUNDEF(Ptr.getValueType());
4598 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4599 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment,
4603 SDValue SelectionDAG::getLoad(EVT VT, SDLoc dl,
4604 SDValue Chain, SDValue Ptr,
4605 MachineMemOperand *MMO) {
4606 SDValue Undef = getUNDEF(Ptr.getValueType());
4607 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef,
4611 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4612 SDValue Chain, SDValue Ptr,
4613 MachinePointerInfo PtrInfo, EVT MemVT,
4614 bool isVolatile, bool isNonTemporal,
4615 unsigned Alignment, const MDNode *TBAAInfo) {
4616 SDValue Undef = getUNDEF(Ptr.getValueType());
4617 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4618 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment,
4623 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, SDLoc dl, EVT VT,
4624 SDValue Chain, SDValue Ptr, EVT MemVT,
4625 MachineMemOperand *MMO) {
4626 SDValue Undef = getUNDEF(Ptr.getValueType());
4627 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef,
4632 SelectionDAG::getIndexedLoad(SDValue OrigLoad, SDLoc dl, SDValue Base,
4633 SDValue Offset, ISD::MemIndexedMode AM) {
4634 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
4635 assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
4636 "Load is already a indexed load!");
4637 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl,
4638 LD->getChain(), Base, Offset, LD->getPointerInfo(),
4639 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(),
4640 false, LD->getAlignment());
4643 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4644 SDValue Ptr, MachinePointerInfo PtrInfo,
4645 bool isVolatile, bool isNonTemporal,
4646 unsigned Alignment, const MDNode *TBAAInfo) {
4647 assert(Chain.getValueType() == MVT::Other &&
4648 "Invalid chain type");
4649 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4650 Alignment = getEVTAlignment(Val.getValueType());
4652 unsigned Flags = MachineMemOperand::MOStore;
4654 Flags |= MachineMemOperand::MOVolatile;
4656 Flags |= MachineMemOperand::MONonTemporal;
4658 if (PtrInfo.V.isNull())
4659 PtrInfo = InferPointerInfo(Ptr);
4661 MachineFunction &MF = getMachineFunction();
4662 MachineMemOperand *MMO =
4663 MF.getMachineMemOperand(PtrInfo, Flags,
4664 Val.getValueType().getStoreSize(), Alignment,
4667 return getStore(Chain, dl, Val, Ptr, MMO);
4670 SDValue SelectionDAG::getStore(SDValue Chain, SDLoc dl, SDValue Val,
4671 SDValue Ptr, MachineMemOperand *MMO) {
4672 assert(Chain.getValueType() == MVT::Other &&
4673 "Invalid chain type");
4674 EVT VT = Val.getValueType();
4675 SDVTList VTs = getVTList(MVT::Other);
4676 SDValue Undef = getUNDEF(Ptr.getValueType());
4677 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4678 FoldingSetNodeID ID;
4679 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4680 ID.AddInteger(VT.getRawBits());
4681 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(),
4682 MMO->isNonTemporal(), MMO->isInvariant()));
4683 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4685 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4686 cast<StoreSDNode>(E)->refineAlignment(MMO);
4687 return SDValue(E, 0);
4689 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4690 dl.getDebugLoc(), VTs,
4691 ISD::UNINDEXED, false, VT, MMO);
4692 CSEMap.InsertNode(N, IP);
4693 AllNodes.push_back(N);
4694 return SDValue(N, 0);
4697 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4698 SDValue Ptr, MachinePointerInfo PtrInfo,
4699 EVT SVT,bool isVolatile, bool isNonTemporal,
4701 const MDNode *TBAAInfo) {
4702 assert(Chain.getValueType() == MVT::Other &&
4703 "Invalid chain type");
4704 if (Alignment == 0) // Ensure that codegen never sees alignment 0
4705 Alignment = getEVTAlignment(SVT);
4707 unsigned Flags = MachineMemOperand::MOStore;
4709 Flags |= MachineMemOperand::MOVolatile;
4711 Flags |= MachineMemOperand::MONonTemporal;
4713 if (PtrInfo.V.isNull())
4714 PtrInfo = InferPointerInfo(Ptr);
4716 MachineFunction &MF = getMachineFunction();
4717 MachineMemOperand *MMO =
4718 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment,
4721 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO);
4724 SDValue SelectionDAG::getTruncStore(SDValue Chain, SDLoc dl, SDValue Val,
4725 SDValue Ptr, EVT SVT,
4726 MachineMemOperand *MMO) {
4727 EVT VT = Val.getValueType();
4729 assert(Chain.getValueType() == MVT::Other &&
4730 "Invalid chain type");
4732 return getStore(Chain, dl, Val, Ptr, MMO);
4734 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) &&
4735 "Should only be a truncating store, not extending!");
4736 assert(VT.isInteger() == SVT.isInteger() &&
4737 "Can't do FP-INT conversion!");
4738 assert(VT.isVector() == SVT.isVector() &&
4739 "Cannot use trunc store to convert to or from a vector!");
4740 assert((!VT.isVector() ||
4741 VT.getVectorNumElements() == SVT.getVectorNumElements()) &&
4742 "Cannot use trunc store to change the number of vector elements!");
4744 SDVTList VTs = getVTList(MVT::Other);
4745 SDValue Undef = getUNDEF(Ptr.getValueType());
4746 SDValue Ops[] = { Chain, Val, Ptr, Undef };
4747 FoldingSetNodeID ID;
4748 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4749 ID.AddInteger(SVT.getRawBits());
4750 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(),
4751 MMO->isNonTemporal(), MMO->isInvariant()));
4752 ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
4754 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
4755 cast<StoreSDNode>(E)->refineAlignment(MMO);
4756 return SDValue(E, 0);
4758 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4759 dl.getDebugLoc(), VTs,
4760 ISD::UNINDEXED, true, SVT, MMO);
4761 CSEMap.InsertNode(N, IP);
4762 AllNodes.push_back(N);
4763 return SDValue(N, 0);
4767 SelectionDAG::getIndexedStore(SDValue OrigStore, SDLoc dl, SDValue Base,
4768 SDValue Offset, ISD::MemIndexedMode AM) {
4769 StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
4770 assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
4771 "Store is already a indexed store!");
4772 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
4773 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
4774 FoldingSetNodeID ID;
4775 AddNodeIDNode(ID, ISD::STORE, VTs, Ops);
4776 ID.AddInteger(ST->getMemoryVT().getRawBits());
4777 ID.AddInteger(ST->getRawSubclassData());
4778 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
4780 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4781 return SDValue(E, 0);
4783 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl.getIROrder(),
4784 dl.getDebugLoc(), VTs, AM,
4785 ST->isTruncatingStore(),
4787 ST->getMemOperand());
4788 CSEMap.InsertNode(N, IP);
4789 AllNodes.push_back(N);
4790 return SDValue(N, 0);
4793 SDValue SelectionDAG::getVAArg(EVT VT, SDLoc dl,
4794 SDValue Chain, SDValue Ptr,
4797 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) };
4798 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops);
4801 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4802 ArrayRef<SDUse> Ops) {
4803 switch (Ops.size()) {
4804 case 0: return getNode(Opcode, DL, VT);
4805 case 1: return getNode(Opcode, DL, VT, static_cast<const SDValue>(Ops[0]));
4806 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4807 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4811 // Copy from an SDUse array into an SDValue array for use with
4812 // the regular getNode logic.
4813 SmallVector<SDValue, 8> NewOps(Ops.begin(), Ops.end());
4814 return getNode(Opcode, DL, VT, NewOps);
4817 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT,
4818 ArrayRef<SDValue> Ops) {
4819 unsigned NumOps = Ops.size();
4821 case 0: return getNode(Opcode, DL, VT);
4822 case 1: return getNode(Opcode, DL, VT, Ops[0]);
4823 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]);
4824 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]);
4830 case ISD::SELECT_CC: {
4831 assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
4832 assert(Ops[0].getValueType() == Ops[1].getValueType() &&
4833 "LHS and RHS of condition must have same type!");
4834 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4835 "True and False arms of SelectCC must have same type!");
4836 assert(Ops[2].getValueType() == VT &&
4837 "select_cc node must be of same type as true and false value!");
4841 assert(NumOps == 5 && "BR_CC takes 5 operands!");
4842 assert(Ops[2].getValueType() == Ops[3].getValueType() &&
4843 "LHS/RHS of comparison should match types!");
4850 SDVTList VTs = getVTList(VT);
4852 if (VT != MVT::Glue) {
4853 FoldingSetNodeID ID;
4854 AddNodeIDNode(ID, Opcode, VTs, Ops);
4857 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4858 return SDValue(E, 0);
4860 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4862 CSEMap.InsertNode(N, IP);
4864 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4868 AllNodes.push_back(N);
4872 return SDValue(N, 0);
4875 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL,
4876 ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops) {
4877 return getNode(Opcode, DL, getVTList(ResultTys), Ops);
4880 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4881 ArrayRef<SDValue> Ops) {
4882 if (VTList.NumVTs == 1)
4883 return getNode(Opcode, DL, VTList.VTs[0], Ops);
4887 // FIXME: figure out how to safely handle things like
4888 // int foo(int x) { return 1 << (x & 255); }
4889 // int bar() { return foo(256); }
4890 case ISD::SRA_PARTS:
4891 case ISD::SRL_PARTS:
4892 case ISD::SHL_PARTS:
4893 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
4894 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
4895 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4896 else if (N3.getOpcode() == ISD::AND)
4897 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
4898 // If the and is only masking out bits that cannot effect the shift,
4899 // eliminate the and.
4900 unsigned NumBits = VT.getScalarType().getSizeInBits()*2;
4901 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
4902 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0));
4908 // Memoize the node unless it returns a flag.
4910 unsigned NumOps = Ops.size();
4911 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
4912 FoldingSetNodeID ID;
4913 AddNodeIDNode(ID, Opcode, VTList, Ops);
4915 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
4916 return SDValue(E, 0);
4919 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4920 DL.getDebugLoc(), VTList, Ops[0]);
4921 } else if (NumOps == 2) {
4922 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4923 DL.getDebugLoc(), VTList, Ops[0],
4925 } else if (NumOps == 3) {
4926 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4927 DL.getDebugLoc(), VTList, Ops[0],
4930 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4933 CSEMap.InsertNode(N, IP);
4936 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(),
4937 DL.getDebugLoc(), VTList, Ops[0]);
4938 } else if (NumOps == 2) {
4939 N = new (NodeAllocator) BinarySDNode(Opcode, DL.getIROrder(),
4940 DL.getDebugLoc(), VTList, Ops[0],
4942 } else if (NumOps == 3) {
4943 N = new (NodeAllocator) TernarySDNode(Opcode, DL.getIROrder(),
4944 DL.getDebugLoc(), VTList, Ops[0],
4947 N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(),
4951 AllNodes.push_back(N);
4955 return SDValue(N, 0);
4958 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList) {
4959 return getNode(Opcode, DL, VTList, ArrayRef<SDValue>());
4962 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4964 SDValue Ops[] = { N1 };
4965 return getNode(Opcode, DL, VTList, Ops);
4968 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4969 SDValue N1, SDValue N2) {
4970 SDValue Ops[] = { N1, N2 };
4971 return getNode(Opcode, DL, VTList, Ops);
4974 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4975 SDValue N1, SDValue N2, SDValue N3) {
4976 SDValue Ops[] = { N1, N2, N3 };
4977 return getNode(Opcode, DL, VTList, Ops);
4980 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4981 SDValue N1, SDValue N2, SDValue N3,
4983 SDValue Ops[] = { N1, N2, N3, N4 };
4984 return getNode(Opcode, DL, VTList, Ops);
4987 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, SDVTList VTList,
4988 SDValue N1, SDValue N2, SDValue N3,
4989 SDValue N4, SDValue N5) {
4990 SDValue Ops[] = { N1, N2, N3, N4, N5 };
4991 return getNode(Opcode, DL, VTList, Ops);
4994 SDVTList SelectionDAG::getVTList(EVT VT) {
4995 return makeVTList(SDNode::getValueTypeList(VT), 1);
4998 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) {
4999 FoldingSetNodeID ID;
5001 ID.AddInteger(VT1.getRawBits());
5002 ID.AddInteger(VT2.getRawBits());
5005 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5007 EVT *Array = Allocator.Allocate<EVT>(2);
5010 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 2);
5011 VTListMap.InsertNode(Result, IP);
5013 return Result->getSDVTList();
5016 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) {
5017 FoldingSetNodeID ID;
5019 ID.AddInteger(VT1.getRawBits());
5020 ID.AddInteger(VT2.getRawBits());
5021 ID.AddInteger(VT3.getRawBits());
5024 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5026 EVT *Array = Allocator.Allocate<EVT>(3);
5030 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 3);
5031 VTListMap.InsertNode(Result, IP);
5033 return Result->getSDVTList();
5036 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) {
5037 FoldingSetNodeID ID;
5039 ID.AddInteger(VT1.getRawBits());
5040 ID.AddInteger(VT2.getRawBits());
5041 ID.AddInteger(VT3.getRawBits());
5042 ID.AddInteger(VT4.getRawBits());
5045 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5047 EVT *Array = Allocator.Allocate<EVT>(4);
5052 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, 4);
5053 VTListMap.InsertNode(Result, IP);
5055 return Result->getSDVTList();
5058 SDVTList SelectionDAG::getVTList(ArrayRef<EVT> VTs) {
5059 unsigned NumVTs = VTs.size();
5060 FoldingSetNodeID ID;
5061 ID.AddInteger(NumVTs);
5062 for (unsigned index = 0; index < NumVTs; index++) {
5063 ID.AddInteger(VTs[index].getRawBits());
5067 SDVTListNode *Result = VTListMap.FindNodeOrInsertPos(ID, IP);
5069 EVT *Array = Allocator.Allocate<EVT>(NumVTs);
5070 std::copy(VTs.begin(), VTs.end(), Array);
5071 Result = new (Allocator) SDVTListNode(ID.Intern(Allocator), Array, NumVTs);
5072 VTListMap.InsertNode(Result, IP);
5074 return Result->getSDVTList();
5078 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
5079 /// specified operands. If the resultant node already exists in the DAG,
5080 /// this does not modify the specified node, instead it returns the node that
5081 /// already exists. If the resultant node does not exist in the DAG, the
5082 /// input node is returned. As a degenerate case, if you specify the same
5083 /// input operands as the node already has, the input node is returned.
5084 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) {
5085 assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
5087 // Check to see if there is no change.
5088 if (Op == N->getOperand(0)) return N;
5090 // See if the modified node already exists.
5091 void *InsertPos = nullptr;
5092 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
5095 // Nope it doesn't. Remove the node from its current place in the maps.
5097 if (!RemoveNodeFromCSEMaps(N))
5098 InsertPos = nullptr;
5100 // Now we update the operands.
5101 N->OperandList[0].set(Op);
5103 // If this gets put into a CSE map, add it.
5104 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5108 SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) {
5109 assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
5111 // Check to see if there is no change.
5112 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
5113 return N; // No operands changed, just return the input node.
5115 // See if the modified node already exists.
5116 void *InsertPos = nullptr;
5117 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
5120 // Nope it doesn't. Remove the node from its current place in the maps.
5122 if (!RemoveNodeFromCSEMaps(N))
5123 InsertPos = nullptr;
5125 // Now we update the operands.
5126 if (N->OperandList[0] != Op1)
5127 N->OperandList[0].set(Op1);
5128 if (N->OperandList[1] != Op2)
5129 N->OperandList[1].set(Op2);
5131 // If this gets put into a CSE map, add it.
5132 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5136 SDNode *SelectionDAG::
5137 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) {
5138 SDValue Ops[] = { Op1, Op2, Op3 };
5139 return UpdateNodeOperands(N, Ops);
5142 SDNode *SelectionDAG::
5143 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5144 SDValue Op3, SDValue Op4) {
5145 SDValue Ops[] = { Op1, Op2, Op3, Op4 };
5146 return UpdateNodeOperands(N, Ops);
5149 SDNode *SelectionDAG::
5150 UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
5151 SDValue Op3, SDValue Op4, SDValue Op5) {
5152 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 };
5153 return UpdateNodeOperands(N, Ops);
5156 SDNode *SelectionDAG::
5157 UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops) {
5158 unsigned NumOps = Ops.size();
5159 assert(N->getNumOperands() == NumOps &&
5160 "Update with wrong number of operands");
5162 // Check to see if there is no change.
5163 bool AnyChange = false;
5164 for (unsigned i = 0; i != NumOps; ++i) {
5165 if (Ops[i] != N->getOperand(i)) {
5171 // No operands changed, just return the input node.
5172 if (!AnyChange) return N;
5174 // See if the modified node already exists.
5175 void *InsertPos = nullptr;
5176 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, InsertPos))
5179 // Nope it doesn't. Remove the node from its current place in the maps.
5181 if (!RemoveNodeFromCSEMaps(N))
5182 InsertPos = nullptr;
5184 // Now we update the operands.
5185 for (unsigned i = 0; i != NumOps; ++i)
5186 if (N->OperandList[i] != Ops[i])
5187 N->OperandList[i].set(Ops[i]);
5189 // If this gets put into a CSE map, add it.
5190 if (InsertPos) CSEMap.InsertNode(N, InsertPos);
5194 /// DropOperands - Release the operands and set this node to have
5196 void SDNode::DropOperands() {
5197 // Unlike the code in MorphNodeTo that does this, we don't need to
5198 // watch for dead nodes here.
5199 for (op_iterator I = op_begin(), E = op_end(); I != E; ) {
5205 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a
5208 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5210 SDVTList VTs = getVTList(VT);
5211 return SelectNodeTo(N, MachineOpc, VTs, None);
5214 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5215 EVT VT, SDValue Op1) {
5216 SDVTList VTs = getVTList(VT);
5217 SDValue Ops[] = { Op1 };
5218 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5221 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5222 EVT VT, SDValue Op1,
5224 SDVTList VTs = getVTList(VT);
5225 SDValue Ops[] = { Op1, Op2 };
5226 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5229 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5230 EVT VT, SDValue Op1,
5231 SDValue Op2, SDValue Op3) {
5232 SDVTList VTs = getVTList(VT);
5233 SDValue Ops[] = { Op1, Op2, Op3 };
5234 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5237 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5238 EVT VT, ArrayRef<SDValue> Ops) {
5239 SDVTList VTs = getVTList(VT);
5240 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5243 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5244 EVT VT1, EVT VT2, ArrayRef<SDValue> Ops) {
5245 SDVTList VTs = getVTList(VT1, VT2);
5246 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5249 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5251 SDVTList VTs = getVTList(VT1, VT2);
5252 return SelectNodeTo(N, MachineOpc, VTs, None);
5255 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5256 EVT VT1, EVT VT2, EVT VT3,
5257 ArrayRef<SDValue> Ops) {
5258 SDVTList VTs = getVTList(VT1, VT2, VT3);
5259 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5262 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5263 EVT VT1, EVT VT2, EVT VT3, EVT VT4,
5264 ArrayRef<SDValue> Ops) {
5265 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5266 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5269 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5272 SDVTList VTs = getVTList(VT1, VT2);
5273 SDValue Ops[] = { Op1 };
5274 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5277 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5279 SDValue Op1, SDValue Op2) {
5280 SDVTList VTs = getVTList(VT1, VT2);
5281 SDValue Ops[] = { Op1, Op2 };
5282 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5285 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5287 SDValue Op1, SDValue Op2,
5289 SDVTList VTs = getVTList(VT1, VT2);
5290 SDValue Ops[] = { Op1, Op2, Op3 };
5291 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5294 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5295 EVT VT1, EVT VT2, EVT VT3,
5296 SDValue Op1, SDValue Op2,
5298 SDVTList VTs = getVTList(VT1, VT2, VT3);
5299 SDValue Ops[] = { Op1, Op2, Op3 };
5300 return SelectNodeTo(N, MachineOpc, VTs, Ops);
5303 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc,
5304 SDVTList VTs,ArrayRef<SDValue> Ops) {
5305 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops);
5306 // Reset the NodeID to -1.
5311 /// UpdadeSDLocOnMergedSDNode - If the opt level is -O0 then it throws away
5312 /// the line number information on the merged node since it is not possible to
5313 /// preserve the information that operation is associated with multiple lines.
5314 /// This will make the debugger working better at -O0, were there is a higher
5315 /// probability having other instructions associated with that line.
5317 /// For IROrder, we keep the smaller of the two
5318 SDNode *SelectionDAG::UpdadeSDLocOnMergedSDNode(SDNode *N, SDLoc OLoc) {
5319 DebugLoc NLoc = N->getDebugLoc();
5320 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) &&
5321 (OLoc.getDebugLoc() != NLoc)) {
5322 N->setDebugLoc(DebugLoc());
5324 unsigned Order = std::min(N->getIROrder(), OLoc.getIROrder());
5325 N->setIROrder(Order);
5329 /// MorphNodeTo - This *mutates* the specified node to have the specified
5330 /// return type, opcode, and operands.
5332 /// Note that MorphNodeTo returns the resultant node. If there is already a
5333 /// node of the specified opcode and operands, it returns that node instead of
5334 /// the current one. Note that the SDLoc need not be the same.
5336 /// Using MorphNodeTo is faster than creating a new node and swapping it in
5337 /// with ReplaceAllUsesWith both because it often avoids allocating a new
5338 /// node, and because it doesn't require CSE recalculation for any of
5339 /// the node's users.
5341 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc,
5342 SDVTList VTs, ArrayRef<SDValue> Ops) {
5343 unsigned NumOps = Ops.size();
5344 // If an identical node already exists, use it.
5346 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) {
5347 FoldingSetNodeID ID;
5348 AddNodeIDNode(ID, Opc, VTs, Ops);
5349 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
5350 return UpdadeSDLocOnMergedSDNode(ON, SDLoc(N));
5353 if (!RemoveNodeFromCSEMaps(N))
5356 // Start the morphing.
5358 N->ValueList = VTs.VTs;
5359 N->NumValues = VTs.NumVTs;
5361 // Clear the operands list, updating used nodes to remove this from their
5362 // use list. Keep track of any operands that become dead as a result.
5363 SmallPtrSet<SDNode*, 16> DeadNodeSet;
5364 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) {
5366 SDNode *Used = Use.getNode();
5368 if (Used->use_empty())
5369 DeadNodeSet.insert(Used);
5372 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) {
5373 // Initialize the memory references information.
5374 MN->setMemRefs(nullptr, nullptr);
5375 // If NumOps is larger than the # of operands we can have in a
5376 // MachineSDNode, reallocate the operand list.
5377 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) {
5378 if (MN->OperandsNeedDelete)
5379 delete[] MN->OperandList;
5380 if (NumOps > array_lengthof(MN->LocalOperands))
5381 // We're creating a final node that will live unmorphed for the
5382 // remainder of the current SelectionDAG iteration, so we can allocate
5383 // the operands directly out of a pool with no recycling metadata.
5384 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5385 Ops.data(), NumOps);
5387 MN->InitOperands(MN->LocalOperands, Ops.data(), NumOps);
5388 MN->OperandsNeedDelete = false;
5390 MN->InitOperands(MN->OperandList, Ops.data(), NumOps);
5392 // If NumOps is larger than the # of operands we currently have, reallocate
5393 // the operand list.
5394 if (NumOps > N->NumOperands) {
5395 if (N->OperandsNeedDelete)
5396 delete[] N->OperandList;
5397 N->InitOperands(new SDUse[NumOps], Ops.data(), NumOps);
5398 N->OperandsNeedDelete = true;
5400 N->InitOperands(N->OperandList, Ops.data(), NumOps);
5403 // Delete any nodes that are still dead after adding the uses for the
5405 if (!DeadNodeSet.empty()) {
5406 SmallVector<SDNode *, 16> DeadNodes;
5407 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(),
5408 E = DeadNodeSet.end(); I != E; ++I)
5409 if ((*I)->use_empty())
5410 DeadNodes.push_back(*I);
5411 RemoveDeadNodes(DeadNodes);
5415 CSEMap.InsertNode(N, IP); // Memoize the new node.
5420 /// getMachineNode - These are used for target selectors to create a new node
5421 /// with specified return type(s), MachineInstr opcode, and operands.
5423 /// Note that getMachineNode returns the resultant node. If there is already a
5424 /// node of the specified opcode and operands, it returns that node instead of
5425 /// the current one.
5427 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT) {
5428 SDVTList VTs = getVTList(VT);
5429 return getMachineNode(Opcode, dl, VTs, None);
5433 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT, SDValue Op1) {
5434 SDVTList VTs = getVTList(VT);
5435 SDValue Ops[] = { Op1 };
5436 return getMachineNode(Opcode, dl, VTs, Ops);
5440 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5441 SDValue Op1, SDValue Op2) {
5442 SDVTList VTs = getVTList(VT);
5443 SDValue Ops[] = { Op1, Op2 };
5444 return getMachineNode(Opcode, dl, VTs, Ops);
5448 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5449 SDValue Op1, SDValue Op2, SDValue Op3) {
5450 SDVTList VTs = getVTList(VT);
5451 SDValue Ops[] = { Op1, Op2, Op3 };
5452 return getMachineNode(Opcode, dl, VTs, Ops);
5456 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT,
5457 ArrayRef<SDValue> Ops) {
5458 SDVTList VTs = getVTList(VT);
5459 return getMachineNode(Opcode, dl, VTs, Ops);
5463 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1, EVT VT2) {
5464 SDVTList VTs = getVTList(VT1, VT2);
5465 return getMachineNode(Opcode, dl, VTs, None);
5469 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5470 EVT VT1, EVT VT2, SDValue Op1) {
5471 SDVTList VTs = getVTList(VT1, VT2);
5472 SDValue Ops[] = { Op1 };
5473 return getMachineNode(Opcode, dl, VTs, Ops);
5477 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5478 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) {
5479 SDVTList VTs = getVTList(VT1, VT2);
5480 SDValue Ops[] = { Op1, Op2 };
5481 return getMachineNode(Opcode, dl, VTs, Ops);
5485 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5486 EVT VT1, EVT VT2, SDValue Op1,
5487 SDValue Op2, SDValue Op3) {
5488 SDVTList VTs = getVTList(VT1, VT2);
5489 SDValue Ops[] = { Op1, Op2, Op3 };
5490 return getMachineNode(Opcode, dl, VTs, Ops);
5494 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5496 ArrayRef<SDValue> Ops) {
5497 SDVTList VTs = getVTList(VT1, VT2);
5498 return getMachineNode(Opcode, dl, VTs, Ops);
5502 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5503 EVT VT1, EVT VT2, EVT VT3,
5504 SDValue Op1, SDValue Op2) {
5505 SDVTList VTs = getVTList(VT1, VT2, VT3);
5506 SDValue Ops[] = { Op1, Op2 };
5507 return getMachineNode(Opcode, dl, VTs, Ops);
5511 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5512 EVT VT1, EVT VT2, EVT VT3,
5513 SDValue Op1, SDValue Op2, SDValue Op3) {
5514 SDVTList VTs = getVTList(VT1, VT2, VT3);
5515 SDValue Ops[] = { Op1, Op2, Op3 };
5516 return getMachineNode(Opcode, dl, VTs, Ops);
5520 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5521 EVT VT1, EVT VT2, EVT VT3,
5522 ArrayRef<SDValue> Ops) {
5523 SDVTList VTs = getVTList(VT1, VT2, VT3);
5524 return getMachineNode(Opcode, dl, VTs, Ops);
5528 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl, EVT VT1,
5529 EVT VT2, EVT VT3, EVT VT4,
5530 ArrayRef<SDValue> Ops) {
5531 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4);
5532 return getMachineNode(Opcode, dl, VTs, Ops);
5536 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc dl,
5537 ArrayRef<EVT> ResultTys,
5538 ArrayRef<SDValue> Ops) {
5539 SDVTList VTs = getVTList(ResultTys);
5540 return getMachineNode(Opcode, dl, VTs, Ops);
5544 SelectionDAG::getMachineNode(unsigned Opcode, SDLoc DL, SDVTList VTs,
5545 ArrayRef<SDValue> OpsArray) {
5546 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue;
5549 const SDValue *Ops = OpsArray.data();
5550 unsigned NumOps = OpsArray.size();
5553 FoldingSetNodeID ID;
5554 AddNodeIDNode(ID, ~Opcode, VTs, OpsArray);
5556 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) {
5557 return cast<MachineSDNode>(UpdadeSDLocOnMergedSDNode(E, DL));
5561 // Allocate a new MachineSDNode.
5562 N = new (NodeAllocator) MachineSDNode(~Opcode, DL.getIROrder(),
5563 DL.getDebugLoc(), VTs);
5565 // Initialize the operands list.
5566 if (NumOps > array_lengthof(N->LocalOperands))
5567 // We're creating a final node that will live unmorphed for the
5568 // remainder of the current SelectionDAG iteration, so we can allocate
5569 // the operands directly out of a pool with no recycling metadata.
5570 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps),
5573 N->InitOperands(N->LocalOperands, Ops, NumOps);
5574 N->OperandsNeedDelete = false;
5577 CSEMap.InsertNode(N, IP);
5579 AllNodes.push_back(N);
5581 VerifyMachineNode(N);
5586 /// getTargetExtractSubreg - A convenience function for creating
5587 /// TargetOpcode::EXTRACT_SUBREG nodes.
5589 SelectionDAG::getTargetExtractSubreg(int SRIdx, SDLoc DL, EVT VT,
5591 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5592 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL,
5593 VT, Operand, SRIdxVal);
5594 return SDValue(Subreg, 0);
5597 /// getTargetInsertSubreg - A convenience function for creating
5598 /// TargetOpcode::INSERT_SUBREG nodes.
5600 SelectionDAG::getTargetInsertSubreg(int SRIdx, SDLoc DL, EVT VT,
5601 SDValue Operand, SDValue Subreg) {
5602 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32);
5603 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL,
5604 VT, Operand, Subreg, SRIdxVal);
5605 return SDValue(Result, 0);
5608 /// getNodeIfExists - Get the specified node if it's already available, or
5609 /// else return NULL.
5610 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
5611 ArrayRef<SDValue> Ops) {
5612 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) {
5613 FoldingSetNodeID ID;
5614 AddNodeIDNode(ID, Opcode, VTList, Ops);
5616 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
5622 /// getDbgValue - Creates a SDDbgValue node.
5626 SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R,
5627 bool IsIndirect, uint64_t Off,
5628 DebugLoc DL, unsigned O) {
5629 return new (Allocator) SDDbgValue(MDPtr, N, R, IsIndirect, Off, DL, O);
5634 SelectionDAG::getConstantDbgValue(MDNode *MDPtr, const Value *C,
5636 DebugLoc DL, unsigned O) {
5637 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O);
5642 SelectionDAG::getFrameIndexDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off,
5643 DebugLoc DL, unsigned O) {
5644 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O);
5649 /// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node
5650 /// pointed to by a use iterator is deleted, increment the use iterator
5651 /// so that it doesn't dangle.
5653 class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener {
5654 SDNode::use_iterator &UI;
5655 SDNode::use_iterator &UE;
5657 void NodeDeleted(SDNode *N, SDNode *E) override {
5658 // Increment the iterator as needed.
5659 while (UI != UE && N == *UI)
5664 RAUWUpdateListener(SelectionDAG &d,
5665 SDNode::use_iterator &ui,
5666 SDNode::use_iterator &ue)
5667 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {}
5672 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5673 /// This can cause recursive merging of nodes in the DAG.
5675 /// This version assumes From has a single result value.
5677 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) {
5678 SDNode *From = FromN.getNode();
5679 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 &&
5680 "Cannot replace with this method!");
5681 assert(From != To.getNode() && "Cannot replace uses of with self");
5683 // Iterate over all the existing uses of From. New uses will be added
5684 // to the beginning of the use list, which we avoid visiting.
5685 // This specifically avoids visiting uses of From that arise while the
5686 // replacement is happening, because any such uses would be the result
5687 // of CSE: If an existing node looks like From after one of its operands
5688 // is replaced by To, we don't want to replace of all its users with To
5689 // too. See PR3018 for more info.
5690 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5691 RAUWUpdateListener Listener(*this, UI, UE);
5695 // This node is about to morph, remove its old self from the CSE maps.
5696 RemoveNodeFromCSEMaps(User);
5698 // A user can appear in a use list multiple times, and when this
5699 // happens the uses are usually next to each other in the list.
5700 // To help reduce the number of CSE recomputations, process all
5701 // the uses of this user that we can find this way.
5703 SDUse &Use = UI.getUse();
5706 } while (UI != UE && *UI == User);
5708 // Now that we have modified User, add it back to the CSE maps. If it
5709 // already exists there, recursively merge the results together.
5710 AddModifiedNodeToCSEMaps(User);
5713 // If we just RAUW'd the root, take note.
5714 if (FromN == getRoot())
5718 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5719 /// This can cause recursive merging of nodes in the DAG.
5721 /// This version assumes that for each value of From, there is a
5722 /// corresponding value in To in the same position with the same type.
5724 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) {
5726 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i)
5727 assert((!From->hasAnyUseOfValue(i) ||
5728 From->getValueType(i) == To->getValueType(i)) &&
5729 "Cannot use this version of ReplaceAllUsesWith!");
5732 // Handle the trivial case.
5736 // Iterate over just the existing users of From. See the comments in
5737 // the ReplaceAllUsesWith above.
5738 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5739 RAUWUpdateListener Listener(*this, UI, UE);
5743 // This node is about to morph, remove its old self from the CSE maps.
5744 RemoveNodeFromCSEMaps(User);
5746 // A user can appear in a use list multiple times, and when this
5747 // happens the uses are usually next to each other in the list.
5748 // To help reduce the number of CSE recomputations, process all
5749 // the uses of this user that we can find this way.
5751 SDUse &Use = UI.getUse();
5754 } while (UI != UE && *UI == User);
5756 // Now that we have modified User, add it back to the CSE maps. If it
5757 // already exists there, recursively merge the results together.
5758 AddModifiedNodeToCSEMaps(User);
5761 // If we just RAUW'd the root, take note.
5762 if (From == getRoot().getNode())
5763 setRoot(SDValue(To, getRoot().getResNo()));
5766 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
5767 /// This can cause recursive merging of nodes in the DAG.
5769 /// This version can replace From with any result values. To must match the
5770 /// number and types of values returned by From.
5771 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) {
5772 if (From->getNumValues() == 1) // Handle the simple case efficiently.
5773 return ReplaceAllUsesWith(SDValue(From, 0), To[0]);
5775 // Iterate over just the existing users of From. See the comments in
5776 // the ReplaceAllUsesWith above.
5777 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end();
5778 RAUWUpdateListener Listener(*this, UI, UE);
5782 // This node is about to morph, remove its old self from the CSE maps.
5783 RemoveNodeFromCSEMaps(User);
5785 // A user can appear in a use list multiple times, and when this
5786 // happens the uses are usually next to each other in the list.
5787 // To help reduce the number of CSE recomputations, process all
5788 // the uses of this user that we can find this way.
5790 SDUse &Use = UI.getUse();
5791 const SDValue &ToOp = To[Use.getResNo()];
5794 } while (UI != UE && *UI == User);
5796 // Now that we have modified User, add it back to the CSE maps. If it
5797 // already exists there, recursively merge the results together.
5798 AddModifiedNodeToCSEMaps(User);
5801 // If we just RAUW'd the root, take note.
5802 if (From == getRoot().getNode())
5803 setRoot(SDValue(To[getRoot().getResNo()]));
5806 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
5807 /// uses of other values produced by From.getNode() alone. The Deleted
5808 /// vector is handled the same way as for ReplaceAllUsesWith.
5809 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){
5810 // Handle the really simple, really trivial case efficiently.
5811 if (From == To) return;
5813 // Handle the simple, trivial, case efficiently.
5814 if (From.getNode()->getNumValues() == 1) {
5815 ReplaceAllUsesWith(From, To);
5819 // Iterate over just the existing users of From. See the comments in
5820 // the ReplaceAllUsesWith above.
5821 SDNode::use_iterator UI = From.getNode()->use_begin(),
5822 UE = From.getNode()->use_end();
5823 RAUWUpdateListener Listener(*this, UI, UE);
5826 bool UserRemovedFromCSEMaps = false;
5828 // A user can appear in a use list multiple times, and when this
5829 // happens the uses are usually next to each other in the list.
5830 // To help reduce the number of CSE recomputations, process all
5831 // the uses of this user that we can find this way.
5833 SDUse &Use = UI.getUse();
5835 // Skip uses of different values from the same node.
5836 if (Use.getResNo() != From.getResNo()) {
5841 // If this node hasn't been modified yet, it's still in the CSE maps,
5842 // so remove its old self from the CSE maps.
5843 if (!UserRemovedFromCSEMaps) {
5844 RemoveNodeFromCSEMaps(User);
5845 UserRemovedFromCSEMaps = true;
5850 } while (UI != UE && *UI == User);
5852 // We are iterating over all uses of the From node, so if a use
5853 // doesn't use the specific value, no changes are made.
5854 if (!UserRemovedFromCSEMaps)
5857 // Now that we have modified User, add it back to the CSE maps. If it
5858 // already exists there, recursively merge the results together.
5859 AddModifiedNodeToCSEMaps(User);
5862 // If we just RAUW'd the root, take note.
5863 if (From == getRoot())
5868 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith
5869 /// to record information about a use.
5876 /// operator< - Sort Memos by User.
5877 bool operator<(const UseMemo &L, const UseMemo &R) {
5878 return (intptr_t)L.User < (intptr_t)R.User;
5882 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving
5883 /// uses of other values produced by From.getNode() alone. The same value
5884 /// may appear in both the From and To list. The Deleted vector is
5885 /// handled the same way as for ReplaceAllUsesWith.
5886 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From,
5889 // Handle the simple, trivial case efficiently.
5891 return ReplaceAllUsesOfValueWith(*From, *To);
5893 // Read up all the uses and make records of them. This helps
5894 // processing new uses that are introduced during the
5895 // replacement process.
5896 SmallVector<UseMemo, 4> Uses;
5897 for (unsigned i = 0; i != Num; ++i) {
5898 unsigned FromResNo = From[i].getResNo();
5899 SDNode *FromNode = From[i].getNode();
5900 for (SDNode::use_iterator UI = FromNode->use_begin(),
5901 E = FromNode->use_end(); UI != E; ++UI) {
5902 SDUse &Use = UI.getUse();
5903 if (Use.getResNo() == FromResNo) {
5904 UseMemo Memo = { *UI, i, &Use };
5905 Uses.push_back(Memo);
5910 // Sort the uses, so that all the uses from a given User are together.
5911 std::sort(Uses.begin(), Uses.end());
5913 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size();
5914 UseIndex != UseIndexEnd; ) {
5915 // We know that this user uses some value of From. If it is the right
5916 // value, update it.
5917 SDNode *User = Uses[UseIndex].User;
5919 // This node is about to morph, remove its old self from the CSE maps.
5920 RemoveNodeFromCSEMaps(User);
5922 // The Uses array is sorted, so all the uses for a given User
5923 // are next to each other in the list.
5924 // To help reduce the number of CSE recomputations, process all
5925 // the uses of this user that we can find this way.
5927 unsigned i = Uses[UseIndex].Index;
5928 SDUse &Use = *Uses[UseIndex].Use;
5932 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User);
5934 // Now that we have modified User, add it back to the CSE maps. If it
5935 // already exists there, recursively merge the results together.
5936 AddModifiedNodeToCSEMaps(User);
5940 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
5941 /// based on their topological order. It returns the maximum id and a vector
5942 /// of the SDNodes* in assigned order by reference.
5943 unsigned SelectionDAG::AssignTopologicalOrder() {
5945 unsigned DAGSize = 0;
5947 // SortedPos tracks the progress of the algorithm. Nodes before it are
5948 // sorted, nodes after it are unsorted. When the algorithm completes
5949 // it is at the end of the list.
5950 allnodes_iterator SortedPos = allnodes_begin();
5952 // Visit all the nodes. Move nodes with no operands to the front of
5953 // the list immediately. Annotate nodes that do have operands with their
5954 // operand count. Before we do this, the Node Id fields of the nodes
5955 // may contain arbitrary values. After, the Node Id fields for nodes
5956 // before SortedPos will contain the topological sort index, and the
5957 // Node Id fields for nodes At SortedPos and after will contain the
5958 // count of outstanding operands.
5959 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) {
5962 unsigned Degree = N->getNumOperands();
5964 // A node with no uses, add it to the result array immediately.
5965 N->setNodeId(DAGSize++);
5966 allnodes_iterator Q = N;
5968 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q));
5969 assert(SortedPos != AllNodes.end() && "Overran node list");
5972 // Temporarily use the Node Id as scratch space for the degree count.
5973 N->setNodeId(Degree);
5977 // Visit all the nodes. As we iterate, move nodes into sorted order,
5978 // such that by the time the end is reached all nodes will be sorted.
5979 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) {
5982 // N is in sorted position, so all its uses have one less operand
5983 // that needs to be sorted.
5984 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
5987 unsigned Degree = P->getNodeId();
5988 assert(Degree != 0 && "Invalid node degree");
5991 // All of P's operands are sorted, so P may sorted now.
5992 P->setNodeId(DAGSize++);
5994 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P));
5995 assert(SortedPos != AllNodes.end() && "Overran node list");
5998 // Update P's outstanding operand count.
5999 P->setNodeId(Degree);
6002 if (I == SortedPos) {
6005 dbgs() << "Overran sorted position:\n";
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::ComputeMaskedBits(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 // If this node has already been checked, don't check it again.
6597 if (Checked.count(N))
6600 // If a node has already been visited on this depth-first walk, reject it as
6602 if (!Visited.insert(N)) {
6603 dbgs() << "Offending node:\n";
6605 errs() << "Detected cycle in SelectionDAG\n";
6609 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
6610 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked);
6617 void llvm::checkForCycles(const llvm::SDNode *N) {
6619 assert(N && "Checking nonexistent SDNode");
6620 SmallPtrSet<const SDNode*, 32> visited;
6621 SmallPtrSet<const SDNode*, 32> checked;
6622 checkForCyclesHelper(N, visited, checked);
6626 void llvm::checkForCycles(const llvm::SelectionDAG *DAG) {
6627 checkForCycles(DAG->getRoot().getNode());